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

Commit1ea912e

Browse files
committed
Fix sloppiness about alignment requirements in findsplitloc() space
calculation, also make it stop when it has a 'good enough' split insteadof exhaustively trying all split points.
1 parent2f011a9 commit1ea912e

File tree

2 files changed

+101
-38
lines changed

2 files changed

+101
-38
lines changed

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

Lines changed: 53 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.60 2000/07/2106:42:32 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.61 2000/07/2119:21:00 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -377,6 +377,10 @@ _bt_insertonpg(Relation rel,
377377

378378
/*
379379
* Do we need to split the page to fit the item on it?
380+
*
381+
* Note: PageGetFreeSpace() subtracts sizeof(ItemIdData) from its
382+
* result, so this comparison is correct even though we appear to
383+
* be accounting only for the item and not for its line pointer.
380384
*/
381385
if (PageGetFreeSpace(page)<itemsz)
382386
{
@@ -743,11 +747,14 @@ _bt_findsplitloc(Relation rel,
743747
FindSplitDatastate;
744748
intleftspace,
745749
rightspace,
750+
goodenough,
746751
dataitemtotal,
747752
dataitemstoleft;
748753

749754
opaque= (BTPageOpaque)PageGetSpecialPointer(page);
750755

756+
/* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
757+
newitemsz+=sizeof(ItemIdData);
751758
state.newitemsz=newitemsz;
752759
state.non_leaf= !P_ISLEAF(opaque);
753760
state.have_split= false;
@@ -758,20 +765,31 @@ _bt_findsplitloc(Relation rel,
758765
MAXALIGN(sizeof(BTPageOpaqueData))
759766
+sizeof(ItemIdData);
760767

768+
/*
769+
* Finding the best possible split would require checking all the possible
770+
* split points, because of the high-key and left-key special cases.
771+
* That's probably more work than it's worth; instead, stop as soon as
772+
* we find a "good-enough" split, where good-enough is defined as an
773+
* imbalance in free space of no more than pagesize/16 (arbitrary...)
774+
* This should let us stop near the middle on most pages, instead of
775+
* plowing to the end.
776+
*/
777+
goodenough=leftspace /16;
778+
761779
/* The right page will have the same high key as the old page */
762780
if (!P_RIGHTMOST(opaque))
763781
{
764782
itemid=PageGetItemId(page,P_HIKEY);
765-
rightspace-= (int) (ItemIdGetLength(itemid)+sizeof(ItemIdData));
783+
rightspace-= (int) (MAXALIGN(ItemIdGetLength(itemid))+
784+
sizeof(ItemIdData));
766785
}
767786

768787
/* Count up total space in data items without actually scanning 'em */
769788
dataitemtotal=rightspace- (int)PageGetFreeSpace(page);
770789

771790
/*
772791
* Scan through the data items and calculate space usage for a split
773-
* at each possible position. XXX we could probably stop somewhere
774-
* near the middle...
792+
* at each possible position.
775793
*/
776794
dataitemstoleft=0;
777795
maxoff=PageGetMaxOffsetNumber(page);
@@ -785,44 +803,65 @@ _bt_findsplitloc(Relation rel,
785803
rightfree;
786804

787805
itemid=PageGetItemId(page,offnum);
788-
itemsz=ItemIdGetLength(itemid)+sizeof(ItemIdData);
806+
itemsz=MAXALIGN(ItemIdGetLength(itemid))+sizeof(ItemIdData);
789807

790808
/*
791809
* We have to allow for the current item becoming the high key of
792-
* the left page; therefore it counts against left space.
810+
* the left page; therefore it counts against left space as well
811+
* as right space.
793812
*/
794813
leftfree=leftspace-dataitemstoleft- (int)itemsz;
795814
rightfree=rightspace- (dataitemtotal-dataitemstoleft);
796-
if (offnum<newitemoff)
797-
_bt_checksplitloc(&state,offnum,leftfree,rightfree,
798-
false,itemsz);
799-
elseif (offnum>newitemoff)
815+
/*
816+
* Will the new item go to left or right of split?
817+
*/
818+
if (offnum>newitemoff)
800819
_bt_checksplitloc(&state,offnum,leftfree,rightfree,
801820
true,itemsz);
821+
elseif (offnum<newitemoff)
822+
_bt_checksplitloc(&state,offnum,leftfree,rightfree,
823+
false,itemsz);
802824
else
803825
{
804-
/* need to try it both ways!! */
805-
_bt_checksplitloc(&state,offnum,leftfree,rightfree,
806-
false,newitemsz);
826+
/* need to try it both ways! */
807827
_bt_checksplitloc(&state,offnum,leftfree,rightfree,
808828
true,itemsz);
829+
/* here we are contemplating newitem as first on right */
830+
_bt_checksplitloc(&state,offnum,leftfree,rightfree,
831+
false,newitemsz);
809832
}
810833

834+
/* Abort scan once we find a good-enough choice */
835+
if (state.have_split&&state.best_delta <=goodenough)
836+
break;
837+
811838
dataitemstoleft+=itemsz;
812839
}
813840

841+
/*
842+
* I believe it is not possible to fail to find a feasible split,
843+
* but just in case ...
844+
*/
814845
if (!state.have_split)
815846
elog(FATAL,"_bt_findsplitloc: can't find a feasible split point for %s",
816847
RelationGetRelationName(rel));
848+
817849
*newitemonleft=state.newitemonleft;
818850
returnstate.firstright;
819851
}
820852

853+
/*
854+
* Subroutine to analyze a particular possible split choice (ie, firstright
855+
* and newitemonleft settings), and record the best split so far in *state.
856+
*/
821857
staticvoid
822858
_bt_checksplitloc(FindSplitData*state,OffsetNumberfirstright,
823859
intleftfree,intrightfree,
824860
boolnewitemonleft,Sizefirstrightitemsz)
825861
{
862+
/*
863+
* Account for the new item on whichever side it is to be put.
864+
*/
826865
if (newitemonleft)
827866
leftfree-= (int)state->newitemsz;
828867
else
@@ -833,7 +872,7 @@ _bt_checksplitloc(FindSplitData *state, OffsetNumber firstright,
833872
*/
834873
if (state->non_leaf)
835874
rightfree+= (int)firstrightitemsz-
836-
(int) (sizeof(BTItemData)+sizeof(ItemIdData));
875+
(int) (MAXALIGN(sizeof(BTItemData))+sizeof(ItemIdData));
837876
/*
838877
* If feasible split point, remember best delta.
839878
*/

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

Lines changed: 48 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.38 2000/07/2106:42:33 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.39 2000/07/2119:21:00 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -103,6 +103,9 @@ _bt_freeskey(ScanKey skey)
103103
pfree(skey);
104104
}
105105

106+
/*
107+
* free a retracement stack made by _bt_search.
108+
*/
106109
void
107110
_bt_freestack(BTStackstack)
108111
{
@@ -116,12 +119,38 @@ _bt_freestack(BTStack stack)
116119
}
117120
}
118121

122+
/*
123+
* Construct a BTItem from a plain IndexTuple.
124+
*
125+
* This is now useless code, since a BTItem *is* an index tuple with
126+
* no extra stuff. We hang onto it for the moment to preserve the
127+
* notational distinction, in case we want to add some extra stuff
128+
* again someday.
129+
*/
130+
BTItem
131+
_bt_formitem(IndexTupleitup)
132+
{
133+
intnbytes_btitem;
134+
BTItembtitem;
135+
Sizetuplen;
136+
externOidnewoid();
137+
138+
/* make a copy of the index tuple with room for extra stuff */
139+
tuplen=IndexTupleSize(itup);
140+
nbytes_btitem=tuplen+ (sizeof(BTItemData)-sizeof(IndexTupleData));
141+
142+
btitem= (BTItem)palloc(nbytes_btitem);
143+
memcpy((char*)&(btitem->bti_itup), (char*)itup,tuplen);
144+
145+
returnbtitem;
146+
}
147+
119148
/*
120149
*_bt_orderkeys() -- Put keys in a sensible order for conjunctive quals.
121150
*
122151
*The order of the keys in the qual match the ordering imposed by
123-
*the index.This routine only needs to be called if thereare
124-
*more than one qualclauses using this index.
152+
*the index.This routine only needs to be called if thereis
153+
*more than one qualclause using this index.
125154
*/
126155
void
127156
_bt_orderkeys(Relationrelation,BTScanOpaqueso)
@@ -189,7 +218,8 @@ _bt_orderkeys(Relation relation, BTScanOpaque so)
189218
if (i==numberOfKeys||cur->sk_attno!=attno)
190219
{
191220
if (cur->sk_attno!=attno+1&&i<numberOfKeys)
192-
elog(ERROR,"_bt_orderkeys: key(s) for attribute %d missed",attno+1);
221+
elog(ERROR,"_bt_orderkeys: key(s) for attribute %d missed",
222+
attno+1);
193223

194224
underEqualStrategy= (!equalStrategyEnd);
195225

@@ -320,24 +350,18 @@ _bt_orderkeys(Relation relation, BTScanOpaque so)
320350
pfree(xform);
321351
}
322352

323-
BTItem
324-
_bt_formitem(IndexTupleitup)
325-
{
326-
intnbytes_btitem;
327-
BTItembtitem;
328-
Sizetuplen;
329-
externOidnewoid();
330-
331-
/* make a copy of the index tuple with room for the sequence number */
332-
tuplen=IndexTupleSize(itup);
333-
nbytes_btitem=tuplen+ (sizeof(BTItemData)-sizeof(IndexTupleData));
334-
335-
btitem= (BTItem)palloc(nbytes_btitem);
336-
memcpy((char*)&(btitem->bti_itup), (char*)itup,tuplen);
337-
338-
returnbtitem;
339-
}
340-
353+
/*
354+
* Test whether an indextuple satisfies all the scankey conditions
355+
*
356+
* If not ("false" return), the number of conditions satisfied is
357+
* returned in *keysok. Given proper ordering of the scankey conditions,
358+
* we can use this to determine whether it's worth continuing the scan.
359+
* See _bt_orderkeys().
360+
*
361+
* HACK: *keysok == (Size) -1 means we stopped evaluating because we found
362+
* a NULL value in the index tuple. It's not quite clear to me why this
363+
* case has to be treated specially --- tgl 7/00.
364+
*/
341365
bool
342366
_bt_checkkeys(IndexScanDescscan,IndexTupletuple,Size*keysok)
343367
{
@@ -389,9 +413,9 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, Size *keysok)
389413
if (DatumGetBool(test)== !!(key[0].sk_flags&SK_NEGATE))
390414
return false;
391415

392-
keysz-=1;
393-
key++;
394416
(*keysok)++;
417+
key++;
418+
keysz--;
395419
}
396420

397421
return true;

0 commit comments

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