8000 btree source code cleanups: · postgrespro/postgres_cluster@6f519ad · GitHub
[go: up one dir, main page]
Skip to content

Commit 6f519ad

Browse files
bmomjianbmomjian
committed
btree source code cleanups:
I refactored findsplitloc and checksplitloc so that the division of labor is more clear IMO. I pushed all the space calculation inside the loop to checksplitloc. I also fixed the off by 4 in free space calculation caused by PageGetFreeSpace subtracting sizeof(ItemIdData), even though it was harmless, because it was distracting and I felt it might come back to bite us in the future if we change the page layout or alignments. There's now a new function PageGetExactFreeSpace that doesn't do the subtraction. findsplitloc now tries the "just the new item to right page" split as well. If people don't like the refactoring, I can write a patch to just add that. Heikki Linnakangas
1 parent 526b1d6 commit 6f519ad

File tree

3 files changed

+121
-58
lines changed

3 files changed

+121
-58
lines changed

‎src/backend/access/nbtree/nbtinsert.c

Lines changed: 96 additions & 54 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.151 2007/02/08 13:52:55 alvherre Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.152 2007/02/21 20:02:17 momjian Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -29,6 +29,10 @@ typedef struct
2929
int fillfactor; /* needed when splitting rightmost page */
3030
bool is_leaf; /* T if splitting a leaf page */
3131
bool is_rightmost; /* T if splitting a rightmost page */
32+
OffsetNumber newitemoff; /* where the new item is to be inserted */
33+
int leftspace; /* space available for items on left page */
34+
int rightspace; /* space available for items on right page */
35+
int olddataitemstotal; /* space taken by old items */
3236

3337
bool have_split; /* found a valid split? */
3438

@@ -57,9 +61,9 @@ static OffsetNumber _bt_findsplitloc(Relation rel, Page page,
5761
OffsetNumber newitemoff,
5862
Size newitemsz,
5963
bool *newitemonleft);
60-
static void _bt_checksplitloc(FindSplitData *state, OffsetNumber firstright,
61-
int leftfree, int rightfree,
62-
bool newitemonleft, Size firstrightitemsz);
64+
static void _bt_checksplitloc(FindSplitData *state,
65+
OffsetNumber firstoldonright, bool newitemonleft,
66+
int dataitemstoleft, Size firstoldonrightsz);
6367
static void _bt_pgaddtup(Relation rel, Page page,
6468
Size itemsize, IndexTuple itup,
6569
OffsetNumber itup_off, const char *where);
@@ -1101,13 +1105,31 @@ _bt_findsplitloc(Relation rel,
11011105
int leftspace,
11021106
rightspace,
11031107
goodenough,
1104-
dataitemtotal,
1105-
dataitemstoleft;
1108+
olddataitemstotal,
1109+
olddataitemstoleft;
1110+
bool goodenoughfound;
11061111

11071112
opaque = (BTPageOpaque) PageGetSpecialPointer(page);
11081113

11091114
/* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
11101115
newitemsz += sizeof(ItemIdData);
1116+
1117+
/* Total free space available on a btree page, after fixed overhead */
1118+
leftspace = rightspace =
1119+
PageGetPageSize(page) - SizeOfPageHeaderData -
1120+
MAXALIGN(sizeof(BTPageOpaqueData));
1121+
1122+
/* The right page will have the same high key as the old page */
1123+
if (!P_RIGHTMOST(opaque))
1124+
{
1125+
itemid = PageGetItemId(page, P_HIKEY);
1126+
rightspace -= (int) (MAXALIGN(ItemIdGetLength(itemid)) +
1127+
sizeof(ItemIdData));
1128+
}
1129+
1130+
/* Count up total space in data items without actually scanning 'em */
1131+
olddataitemstotal = rightspace - (int) PageGetExactFreeSpace(page);
1132+
11111133
state.newitemsz = newitemsz;
11121134
state.is_leaf = P_ISLEAF(opaque);
11131135
state.is_rightmost = P_RIGHTMOST(opaque);
@@ -1120,11 +1142,10 @@ _bt_findsplitloc(Relation rel,
11201142
state.newitemonleft = false; /* these just to keep compiler quiet */
11211143
state.firstright = 0;
11221144
state.best_delta = 0;
1123-
1124-
/* Total free space available on a btree page, after fixed overhead */
1125-
leftspace = rightspace =
1126-
PageGetPageSize(page) - SizeOfPageHeaderData -
1127-
MAXALIGN(sizeof(BTPageOpaqueData));
1145+
state.leftspace = leftspace;
1146+
state.rightspace = rightspace;
1147+
state.olddataitemstotal = olddataitemstotal;
1148+
state.newitemoff = newitemoff;
11281149

11291150
/*
11301151
* Finding the best possible split would require checking all the possible
@@ -1137,74 +1158,60 @@ _bt_findsplitloc(Relation rel,
11371158
*/
11381159
goodenough = leftspace / 16;
11391160

1140-
/* The right page will have the same high key as the old page */
1141-
if (!P_RIGHTMOST(opaque))
1142-
{
1143-
itemid = PageGetItemId(page, P_HIKEY);
1144-
rightspace -= (int) (MAXALIGN(ItemIdGetLength(itemid)) +
1145-
sizeof(ItemIdData));
1146-
}
1147-
1148-
/* Count up total space in data items without actually scanning 'em */
1149-
dataitemtotal = rightspace - (int) PageGetFreeSpace(page);
1150-
11511161
/*
11521162
* Scan through the data items and calculate space usage for a split at
11531163
* each possible position.
11541164
*/
1155-
dataitemstoleft = 0;
1165+
olddataitemstoleft = 0;
1166+
goodenoughfound = false;
11561167
maxoff = PageGetMaxOffsetNumber(page);
1157-
1168+
11581169
for (offnum = P_FIRSTDATAKEY(opaque);
11591170
offnum <= maxoff;
11601171
offnum = OffsetNumberNext(offnum))
11611172
{
11621173
Size itemsz;
1163-
int leftfree,
1164-
rightfree;
11651174

11661175
itemid = PageGetItemId(page, offnum);
11671176
itemsz = MAXALIGN(ItemIdGetLength(itemid)) + sizeof(ItemIdData);
11681177

1169-
/*
1170-
* We have to allow for the current item becoming the high key of the
1171-
* left page; therefore it counts against left space as well as right
1172-
* space.
1173-
*/
1174-
leftfree = leftspace - dataitemstoleft - (int) itemsz;
1175-
rightfree = rightspace - (dataitemtotal - dataitemstoleft);
1176-
11771178
/*
11781179
* Will the new item go to left or right of split?
11791180
*/
11801181
if (offnum > newitemoff)
1181-
_bt_checksplitloc(&state, offnum, leftfree, rightfree,
1182-
true, itemsz);
1182+
_bt_checksplitloc(&state, offnum, true,
1183+
olddataitemstoleft, itemsz);
1184+
11831185
else if (offnum < newitemoff)
1184-
_bt_checksplitloc(&state, offnum, leftfree, rightfree,
1185-
false, itemsz);
1186+
_bt_checksplitloc(&state, offnum, false,
1187+
olddataitemstoleft, itemsz);
11861188
else
11871189
{
11881190
/* need to try it both ways! */
1189-
_bt_checksplitloc(&state, offnum, leftfree, rightfree,
1190-
true, itemsz);
1191-
/*
1192-
* Here we are contemplating newitem as first on right. In this
1193-
* case it, not the current item, will become the high key of the
1194-
* left page, and so we have to correct the allowance made above.
1195-
*/
1196-
leftfree += (int) itemsz - (int) newitemsz;
1197-
_bt_checksplitloc(&state, offnum, leftfree, rightfree,
1198-
false, newitemsz);
1191+
_bt_checksplitloc(&state, offnum, true,
1192+
olddataitemstoleft, itemsz);
1193+
1194+
_bt_checksplitloc(&state, offnum, false,
1195+
olddataitemstoleft, itemsz);
11991196
}
12001197

12011198
/* Abort scan once we find a good-enough choice */
12021199
if (state.have_split && state.best_delta <= goodenough)
1200+
{
1201+
goodenoughfound = true;
12031202
break;
1203+
}
12041204

1205-
dataitemstoleft += itemsz;
1205+
olddataitemstoleft += itemsz;
12061206
}
12071207

1208+
/* If the new item goes as the last item, check for splitting so that
1209+
* all the old items go to the left page and the new item goes to the
1210+
* right page.
1211+
*/
1212+
if (newitemoff > maxoff && !goodenoughfound)
1213+
_bt_checksplitloc(&state, newitemoff, false, olddataitemstotal, 0);
1214+
12081215
/*
12091216
* I believe it is not possible to fail to find a feasible split, but just
12101217
* in case ...
@@ -1220,15 +1227,50 @@ _bt_findsplitloc(Relation rel,
12201227
/*
12211228
* Subroutine to analyze a particular possible split choice (ie, firstright
12221229
* and newitemonleft settings), and record the best split so far in *state.
1230+
*
1231+
* firstoldonright is the offset of the first item on the original page
1232+
* that goes to the right page, and firstoldonrightsz is the size of that
1233+
* tuple. firstoldonright can be > max offset, which means that all the old
1234+
* items go to the left page and only the new item goes to the right page.
1235+
* In that case, firstoldonrightsz is not used.
1236+
*
1237+
* olddataitemstoleft is the total size of all old items to the left of
1238+
* firstoldonright.
12231239
*/
12241240
static void
1225-
_bt_checksplitloc(FindSplitData *state, OffsetNumber firstright,
1226-
int leftfree, int rightfree,
1227-
bool newitemonleft, Size firstrightitemsz)
1241+
_bt_checksplitloc(FindSplitData *state,
1242+
OffsetNumber firstoldonright,
1243+
bool newitemonleft,
1244+
int olddataitemstoleft,
1245+
Size firstoldonrightsz)
12281246
{
1247+
int leftfree,
1248+
rightfree;
1249+
Size firstrightitemsz;
1250+
bool newitemisfirstonright;
1251+
1252+
/* Is the new item going to be the first item on the right page? */
1253+
newitemisfirstonright = (firstoldonright == state->newitemoff
1254+
&& !newitemonleft);
1255+
1256+
if(newitemisfirstonright)
1257+
firstrightitemsz = state->newitemsz;
1258+
else
1259+
firstrightitemsz = firstoldonrightsz;
1260+
1261+
/* Account for all the old tuples */
1262+
leftfree = state->leftspace - olddataitemstoleft;
1263+
rightfree = state->rightspace -
1264+
(state->olddataitemstotal - olddataitemstoleft);
1265+
12291266
/*
1230-
* Account for the new item on whichever side it is to be put.
1267+
* The first item on the right page becomes the high key of the
1268+
* left page; therefore it counts against left space as well as right
1269+
* space.
12311270
*/
1271+
leftfree -= firstrightitemsz;
1272+
1273+
/* account for the new item */
12321274
if (newitemonleft)
12331275
leftfree -= (int) state->newitemsz;
12341276
else
@@ -1270,7 +1312,7 @@ _bt_checksplitloc(FindSplitData *state, OffsetNumber firstright,
12701312
{
12711313
state->have_split = true;
12721314
state->newitemonleft = newitemonleft;
1273-
state->firstright = firstright;
1315+
state->firstright = firstoldonright;
12741316
state->best_delta = delta;
12751317
}
12761318
}

‎src/backend/storage/page/bufpage.c

Lines changed: 23 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/storage/page/bufpage.c,v 1.70 2007/01/05 22:19:38 momjian Exp $
11+
* $PostgreSQL: pgsql/src/backend/storage/page/bufpage.c,v 1.71 2007/02/21 20:02:17 momjian Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -418,7 +418,8 @@ PageRepairFragmentation(Page page, OffsetNumber *unused)
418418

419419
/*
420420
* PageGetFreeSpace
421-
* Returns the size of the free (allocatable) space on a page.
421+
* Returns the size of the free (allocatable) space on a page,
422+
* deducted by the space needed for a new line pointer.
422423
*/
423424
Size
424425
PageGetFreeSpace(Page page)
@@ -434,7 +435,26 @@ PageGetFreeSpace(Page page)
434435

435436
if (space < (int) sizeof(ItemIdData))
436437
return 0;
437-
space -= sizeof(ItemIdData); /* XXX not always appropriate */
438+
space -= sizeof(ItemIdData);
439+
440+
return (Size) space;
441+
}
442+
443+
/*
444+
* PageGetExactFreeSpace
445+
* Returns the size of the free (allocatable) space on a page.
446+
*/
447+
Size
448+
PageGetExactFreeSpace(Page page)
449+
{
450+
int space;
451+
452+
/*
453+
* Use signed arithmetic here so that we behave sensibly if pd_lower >
454+
* pd_upper.
455+
*/
456+
space = (int) ((PageHeader) page)->pd_upper -
457+
(int) ((PageHeader) page)->pd_lower;
438458

439459
return (Size) space;
440460
}

‎src/include/storage/bufpage.h

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $PostgreSQL: pgsql/src/include/storage/bufpage.h,v 1.70 2007/02/09 03:35:34 tgl Exp $
10+
* $PostgreSQL: pgsql/src/include/storage/bufpage.h,v 1.71 2007/02/21 20:02:17 momjian Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -322,6 +322,7 @@ extern Page PageGetTempPage(Page page, Size specialSize);
322322
extern void PageRestoreTempPage(Page tempPage, Page oldPage);
323323
extern int PageRepairFragmentation(Page page, OffsetNumber *unused);
324324
extern Size PageGetFreeSpace(Page page);
325+
extern Size PageGetExactFreeSpace(Page page);
325326
extern void PageIndexTupleDelete(Page page, OffsetNumber offset);
326327
extern void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems);
327328

0 commit comments

Comments
 (0)
0