diff options
| -rw-r--r-- | src/backend/access/nbtree/nbtinsert.c | 150 | ||||
| -rw-r--r-- | src/backend/storage/page/bufpage.c | 26 | ||||
| -rw-r--r-- | src/include/storage/bufpage.h | 3 |
3 files changed, 121 insertions, 58 deletions
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c index 98a46ab5857..e229083b8a1 100644 --- a/src/backend/access/nbtree/nbtinsert.c +++ b/src/backend/access/nbtree/nbtinsert.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.151 2007/02/08 13:52:55 alvherre Exp $ + * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.152 2007/02/21 20:02:17 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -29,6 +29,10 @@ typedef struct int fillfactor; /* needed when splitting rightmost page */ bool is_leaf; /* T if splitting a leaf page */ bool is_rightmost; /* T if splitting a rightmost page */ + OffsetNumber newitemoff; /* where the new item is to be inserted */ + int leftspace; /* space available for items on left page */ + int rightspace; /* space available for items on right page */ + int olddataitemstotal; /* space taken by old items */ bool have_split; /* found a valid split? */ @@ -57,9 +61,9 @@ static OffsetNumber _bt_findsplitloc(Relation rel, Page page, OffsetNumber newitemoff, Size newitemsz, bool *newitemonleft); -static void _bt_checksplitloc(FindSplitData *state, OffsetNumber firstright, - int leftfree, int rightfree, - bool newitemonleft, Size firstrightitemsz); +static void _bt_checksplitloc(FindSplitData *state, + OffsetNumber firstoldonright, bool newitemonleft, + int dataitemstoleft, Size firstoldonrightsz); static void _bt_pgaddtup(Relation rel, Page page, Size itemsize, IndexTuple itup, OffsetNumber itup_off, const char *where); @@ -1101,13 +1105,31 @@ _bt_findsplitloc(Relation rel, int leftspace, rightspace, goodenough, - dataitemtotal, - dataitemstoleft; + olddataitemstotal, + olddataitemstoleft; + bool goodenoughfound; opaque = (BTPageOpaque) PageGetSpecialPointer(page); /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */ newitemsz += sizeof(ItemIdData); + + /* Total free space available on a btree page, after fixed overhead */ + leftspace = rightspace = + PageGetPageSize(page) - SizeOfPageHeaderData - + MAXALIGN(sizeof(BTPageOpaqueData)); + + /* The right page will have the same high key as the old page */ + if (!P_RIGHTMOST(opaque)) + { + itemid = PageGetItemId(page, P_HIKEY); + rightspace -= (int) (MAXALIGN(ItemIdGetLength(itemid)) + + sizeof(ItemIdData)); + } + + /* Count up total space in data items without actually scanning 'em */ + olddataitemstotal = rightspace - (int) PageGetExactFreeSpace(page); + state.newitemsz = newitemsz; state.is_leaf = P_ISLEAF(opaque); state.is_rightmost = P_RIGHTMOST(opaque); @@ -1120,11 +1142,10 @@ _bt_findsplitloc(Relation rel, state.newitemonleft = false; /* these just to keep compiler quiet */ state.firstright = 0; state.best_delta = 0; - - /* Total free space available on a btree page, after fixed overhead */ - leftspace = rightspace = - PageGetPageSize(page) - SizeOfPageHeaderData - - MAXALIGN(sizeof(BTPageOpaqueData)); + state.leftspace = leftspace; + state.rightspace = rightspace; + state.olddataitemstotal = olddataitemstotal; + state.newitemoff = newitemoff; /* * Finding the best possible split would require checking all the possible @@ -1137,74 +1158,60 @@ _bt_findsplitloc(Relation rel, */ goodenough = leftspace / 16; - /* The right page will have the same high key as the old page */ - if (!P_RIGHTMOST(opaque)) - { - itemid = PageGetItemId(page, P_HIKEY); - rightspace -= (int) (MAXALIGN(ItemIdGetLength(itemid)) + - sizeof(ItemIdData)); - } - - /* Count up total space in data items without actually scanning 'em */ - dataitemtotal = rightspace - (int) PageGetFreeSpace(page); - /* * Scan through the data items and calculate space usage for a split at * each possible position. */ - dataitemstoleft = 0; + olddataitemstoleft = 0; + goodenoughfound = false; maxoff = PageGetMaxOffsetNumber(page); - + for (offnum = P_FIRSTDATAKEY(opaque); offnum <= maxoff; offnum = OffsetNumberNext(offnum)) { Size itemsz; - int leftfree, - rightfree; itemid = PageGetItemId(page, offnum); itemsz = MAXALIGN(ItemIdGetLength(itemid)) + sizeof(ItemIdData); /* - * We have to allow for the current item becoming the high key of the - * left page; therefore it counts against left space as well as right - * space. - */ - leftfree = leftspace - dataitemstoleft - (int) itemsz; - rightfree = rightspace - (dataitemtotal - dataitemstoleft); - - /* * Will the new item go to left or right of split? */ if (offnum > newitemoff) - _bt_checksplitloc(&state, offnum, leftfree, rightfree, - true, itemsz); + _bt_checksplitloc(&state, offnum, true, + olddataitemstoleft, itemsz); + else if (offnum < newitemoff) - _bt_checksplitloc(&state, offnum, leftfree, rightfree, - false, itemsz); + _bt_checksplitloc(&state, offnum, false, + olddataitemstoleft, itemsz); else { /* need to try it both ways! */ - _bt_checksplitloc(&state, offnum, leftfree, rightfree, - true, itemsz); - /* - * Here we are contemplating newitem as first on right. In this - * case it, not the current item, will become the high key of the - * left page, and so we have to correct the allowance made above. - */ - leftfree += (int) itemsz - (int) newitemsz; - _bt_checksplitloc(&state, offnum, leftfree, rightfree, - false, newitemsz); + _bt_checksplitloc(&state, offnum, true, + olddataitemstoleft, itemsz); + + _bt_checksplitloc(&state, offnum, false, + olddataitemstoleft, itemsz); } /* Abort scan once we find a good-enough choice */ if (state.have_split && state.best_delta <= goodenough) + { + goodenoughfound = true; break; + } - dataitemstoleft += itemsz; + olddataitemstoleft += itemsz; } + /* If the new item goes as the last item, check for splitting so that + * all the old items go to the left page and the new item goes to the + * right page. + */ + if (newitemoff > maxoff && !goodenoughfound) + _bt_checksplitloc(&state, newitemoff, false, olddataitemstotal, 0); + /* * I believe it is not possible to fail to find a feasible split, but just * in case ... @@ -1220,15 +1227,50 @@ _bt_findsplitloc(Relation rel, /* * Subroutine to analyze a particular possible split choice (ie, firstright * and newitemonleft settings), and record the best split so far in *state. + * + * firstoldonright is the offset of the first item on the original page + * that goes to the right page, and firstoldonrightsz is the size of that + * tuple. firstoldonright can be > max offset, which means that all the old + * items go to the left page and only the new item goes to the right page. + * In that case, firstoldonrightsz is not used. + * + * olddataitemstoleft is the total size of all old items to the left of + * firstoldonright. */ static void -_bt_checksplitloc(FindSplitData *state, OffsetNumber firstright, - int leftfree, int rightfree, - bool newitemonleft, Size firstrightitemsz) +_bt_checksplitloc(FindSplitData *state, + OffsetNumber firstoldonright, + bool newitemonleft, + int olddataitemstoleft, + Size firstoldonrightsz) { + int leftfree, + rightfree; + Size firstrightitemsz; + bool newitemisfirstonright; + + /* Is the new item going to be the first item on the right page? */ + newitemisfirstonright = (firstoldonright == state->newitemoff + && !newitemonleft); + + if(newitemisfirstonright) + firstrightitemsz = state->newitemsz; + else + firstrightitemsz = firstoldonrightsz; + + /* Account for all the old tuples */ + leftfree = state->leftspace - olddataitemstoleft; + rightfree = state->rightspace - + (state->olddataitemstotal - olddataitemstoleft); + /* - * Account for the new item on whichever side it is to be put. + * The first item on the right page becomes the high key of the + * left page; therefore it counts against left space as well as right + * space. */ + leftfree -= firstrightitemsz; + + /* account for the new item */ if (newitemonleft) leftfree -= (int) state->newitemsz; else @@ -1270,7 +1312,7 @@ _bt_checksplitloc(FindSplitData *state, OffsetNumber firstright, { state->have_split = true; state->newitemonleft = newitemonleft; - state->firstright = firstright; + state->firstright = firstoldonright; state->best_delta = delta; } } diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c index 2e5c7c412bf..8299f550d6e 100644 --- a/src/backend/storage/page/bufpage.c +++ b/src/backend/storage/page/bufpage.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/storage/page/bufpage.c,v 1.70 2007/01/05 22:19:38 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/storage/page/bufpage.c,v 1.71 2007/02/21 20:02:17 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -418,7 +418,8 @@ PageRepairFragmentation(Page page, OffsetNumber *unused) /* * PageGetFreeSpace - * Returns the size of the free (allocatable) space on a page. + * Returns the size of the free (allocatable) space on a page, + * deducted by the space needed for a new line pointer. */ Size PageGetFreeSpace(Page page) @@ -434,7 +435,26 @@ PageGetFreeSpace(Page page) if (space < (int) sizeof(ItemIdData)) return 0; - space -= sizeof(ItemIdData); /* XXX not always appropriate */ + space -= sizeof(ItemIdData); + + return (Size) space; +} + +/* + * PageGetExactFreeSpace + * Returns the size of the free (allocatable) space on a page. + */ +Size +PageGetExactFreeSpace(Page page) +{ + int space; + + /* + * Use signed arithmetic here so that we behave sensibly if pd_lower > + * pd_upper. + */ + space = (int) ((PageHeader) page)->pd_upper - + (int) ((PageHeader) page)->pd_lower; return (Size) space; } diff --git a/src/include/storage/bufpage.h b/src/include/storage/bufpage.h index abb51404a54..44ab48c9b8f 100644 --- a/src/include/storage/bufpage.h +++ b/src/include/storage/bufpage.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/storage/bufpage.h,v 1.70 2007/02/09 03:35:34 tgl Exp $ + * $PostgreSQL: pgsql/src/include/storage/bufpage.h,v 1.71 2007/02/21 20:02:17 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -322,6 +322,7 @@ extern Page PageGetTempPage(Page page, Size specialSize); extern void PageRestoreTempPage(Page tempPage, Page oldPage); extern int PageRepairFragmentation(Page page, OffsetNumber *unused); extern Size PageGetFreeSpace(Page page); +extern Size PageGetExactFreeSpace(Page page); extern void PageIndexTupleDelete(Page page, OffsetNumber offset); extern void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems); |