Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6f519ad

Browse files
committed
btree source code cleanups:
I refactored findsplitloc and checksplitloc so that the division oflabor is more clear IMO. I pushed all the space calculation inside theloop to checksplitloc.I also fixed the off by 4 in free space calculation caused byPageGetFreeSpace subtracting sizeof(ItemIdData), even though it washarmless, because it was distracting and I felt it might come back tobite us in the future if we change the page layout or alignments.There's now a new function PageGetExactFreeSpace that doesn't do thesubtraction.findsplitloc now tries the "just the new item to right page" split aswell. If people don't like the refactoring, I can write a patch to justadd that.Heikki Linnakangas
1 parent526b1d6 commit6f519ad

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
intfillfactor;/* needed when splitting rightmost page */
3030
boolis_leaf;/* T if splitting a leaf page */
3131
boolis_rightmost;/* T if splitting a rightmost page */
32+
OffsetNumbernewitemoff;/* where the new item is to be inserted */
33+
intleftspace;/* space available for items on left page */
34+
intrightspace;/* space available for items on right page */
35+
intolddataitemstotal;/* space taken by old items */
3236

3337
boolhave_split;/* found a valid split? */
3438

@@ -57,9 +61,9 @@ static OffsetNumber _bt_findsplitloc(Relation rel, Page page,
5761
OffsetNumbernewitemoff,
5862
Sizenewitemsz,
5963
bool*newitemonleft);
60-
staticvoid_bt_checksplitloc(FindSplitData*state,OffsetNumberfirstright,
61-
intleftfree,intrightfree,
62-
boolnewitemonleft,Sizefirstrightitemsz);
64+
staticvoid_bt_checksplitloc(FindSplitData*state,
65+
OffsetNumberfirstoldonright,boolnewitemonleft,
66+
intdataitemstoleft,Sizefirstoldonrightsz);
6367
staticvoid_bt_pgaddtup(Relationrel,Pagepage,
6468
Sizeitemsize,IndexTupleitup,
6569
OffsetNumberitup_off,constchar*where);
@@ -1101,13 +1105,31 @@ _bt_findsplitloc(Relation rel,
11011105
intleftspace,
11021106
rightspace,
11031107
goodenough,
1104-
dataitemtotal,
1105-
dataitemstoleft;
1108+
olddataitemstotal,
1109+
olddataitemstoleft;
1110+
boolgoodenoughfound;
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
Sizeitemsz;
1163-
intleftfree,
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
elseif (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
staticvoid
1225-
_bt_checksplitloc(FindSplitData*state,OffsetNumberfirstright,
1226-
intleftfree,intrightfree,
1227-
boolnewitemonleft,Sizefirstrightitemsz)
1241+
_bt_checksplitloc(FindSplitData*state,
1242+
OffsetNumberfirstoldonright,
1243+
boolnewitemonleft,
1244+
intolddataitemstoleft,
1245+
Sizefirstoldonrightsz)
12281246
{
1247+
intleftfree,
1248+
rightfree;
1249+
Sizefirstrightitemsz;
1250+
boolnewitemisfirstonright;
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(Pagepage)
@@ -434,7 +435,26 @@ PageGetFreeSpace(Page page)
434435

435436
if (space< (int)sizeof(ItemIdData))
436437
return0;
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(Pagepage)
449+
{
450+
intspace;
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
externvoidPageRestoreTempPage(PagetempPage,PageoldPage);
323323
externintPageRepairFragmentation(Pagepage,OffsetNumber*unused);
324324
externSizePageGetFreeSpace(Pagepage);
325+
externSizePageGetExactFreeSpace(Pagepage);
325326
externvoidPageIndexTupleDelete(Pagepage,OffsetNumberoffset);
326327
externvoidPageIndexMultiDelete(Pagepage,OffsetNumber*itemnos,intnitems);
327328

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp