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

Commitbc9236b

Browse files
committed
Revise _bt_binsrch() so that its binary search loop takes
care of equal-key cases, eliminating bt_firsteq(). The linear searchformerly done by bt_firsteq() took a lot of time in the case where manyequal keys appear on the same page.
1 parent9679cb3 commitbc9236b

File tree

1 file changed

+85
-123
lines changed

1 file changed

+85
-123
lines changed

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

Lines changed: 85 additions & 123 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.50 1999/07/1604:58:30 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.51 1999/07/1622:17:06 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -26,8 +26,6 @@
2626

2727
staticBTStack_bt_searchr(Relationrel,intkeysz,ScanKeyscankey,
2828
Buffer*bufP,BTStackstack_in);
29-
staticOffsetNumber_bt_firsteq(Relationrel,TupleDescitupdesc,Pagepage,
30-
Sizekeysz,ScanKeyscankey,OffsetNumberoffnum);
3129
staticint_bt_compare(Relationrel,TupleDescitupdesc,Pagepage,
3230
intkeysz,ScanKeyscankey,OffsetNumberoffnum);
3331
staticbool
@@ -368,7 +366,9 @@ _bt_skeycmp(Relation rel,
368366
*comparison for every key in the scankey. _bt_binsrch() returns
369367
*the OffsetNumber of the first matching key on the page, or the
370368
*OffsetNumber at which the matching key would appear if it were
371-
*on this page.
369+
*on this page. (NOTE: in particular, this means it is possible to
370+
*return a value 1 greater than the number of keys on the page, if
371+
*the scankey is > all keys on the page.)
372372
*
373373
*By the time this procedure is called, we're sure we're looking
374374
*at the right page -- don't need to walk right. _bt_binsrch() has
@@ -385,8 +385,8 @@ _bt_binsrch(Relation rel,
385385
Pagepage;
386386
BTPageOpaqueopaque;
387387
OffsetNumberlow,
388-
mid,
389388
high;
389+
boolhaveEq;
390390
intnatts=rel->rd_rel->relnatts;
391391
intresult;
392392

@@ -395,148 +395,112 @@ _bt_binsrch(Relation rel,
395395
opaque= (BTPageOpaque)PageGetSpecialPointer(page);
396396

397397
/* by convention, item 1 on any non-rightmost page is the high key */
398-
low=mid=P_RIGHTMOST(opaque) ?P_HIKEY :P_FIRSTKEY;
398+
low=P_RIGHTMOST(opaque) ?P_HIKEY :P_FIRSTKEY;
399399

400400
high=PageGetMaxOffsetNumber(page);
401401

402402
/*
403-
* Since for non-rightmost pages, the first item on the page is the
404-
* high key, there are two notions of emptiness. One is if nothing
405-
* appears on the page. The other is if nothing but the high key
406-
* does. The reason we test high <= low, rather than high == low, is
407-
* that after vacuuming there may be nothing *but* the high key on a
408-
* page. In that case, given the scheme above, low = 2 and high = 1.
403+
* If there are no keys on the page, return the first available slot.
404+
* Note this covers two cases: the page is really empty (no keys),
405+
* or it contains only a high key. The latter case is possible after
406+
* vacuuming.
409407
*/
410-
411-
if (PageIsEmpty(page))
408+
if (high<low)
412409
returnlow;
413-
if ((!P_RIGHTMOST(opaque)&&high <=low))
414-
{
415-
if (high<low||
416-
(srchtype==BT_DESCENT&& !(opaque->btpo_flags&BTP_LEAF)))
417-
returnlow;
418-
/* It's insertion and high == low == 2 */
419-
result=_bt_compare(rel,itupdesc,page,keysz,scankey,low);
420-
if (result>0)
421-
returnOffsetNumberNext(low);
422-
returnlow;
423-
}
424410

425-
while ((high-low)>1)
411+
/*
412+
* Binary search to find the first key on the page >= scan key.
413+
* Loop invariant: all slots before 'low' are < scan key, all slots
414+
* at or after 'high' are >= scan key. Also, haveEq is true if the
415+
* tuple at 'high' is == scan key.
416+
* We can fall out when high == low.
417+
*/
418+
high++;/* establish the loop invariant for high */
419+
haveEq= false;
420+
421+
while (high>low)
426422
{
427-
mid=low+ ((high-low) /2);
423+
OffsetNumbermid=low+ ((high-low) /2);
424+
/* We have low <= mid < high, so mid points at a real slot */
425+
428426
result=_bt_compare(rel,itupdesc,page,keysz,scankey,mid);
429427

430428
if (result>0)
431-
low=mid;
432-
elseif (result<0)
433-
high=mid-1;
429+
low=mid+1;
434430
else
435431
{
436-
mid=_bt_firsteq(rel,itupdesc,page,keysz,scankey,mid);
437-
438-
/*
439-
* NOTE for multi-column indices: we may do scan using keys
440-
* not for all attrs. But we handle duplicates using all attrs
441-
* in _bt_insert/_bt_spool code. And so while searching on
442-
* internal pages having number of attrs > keysize we want to
443-
* point at the last item < the scankey, not at the first item
444-
* = the scankey (!!!), and let _bt_moveright decide later
445-
* whether to move right or not (see comments and example
446-
* there). Note also that INSERTions are not affected by this
447-
* code (natts == keysz). - vadim 04/15/97
448-
*/
449-
if (natts==keysz||opaque->btpo_flags&BTP_LEAF)
450-
returnmid;
451-
low=P_RIGHTMOST(opaque) ?P_HIKEY :P_FIRSTKEY;
452-
if (mid==low)
453-
returnmid;
454-
returnOffsetNumberPrev(mid);
432+
high=mid;
433+
haveEq= (result==0);
455434
}
456435
}
457436

458-
/*
459-
* We terminated because the endpoints got too close together.There
460-
* are two cases to take care of.
437+
/*--------------------
438+
* At this point we have high == low, but be careful: they could point
439+
* past the last slot on the page. We also know that haveEq is true
440+
* if and only if there is an equal key (in which case high&low point
441+
* at the first equal key).
461442
*
462-
* For non-insertion searches on internal pages, we want to point at the
463-
* last key <, or first key =, the scankey on the page. This
464-
* guarantees that we'll descend the tree correctly. (NOTE comments
465-
* above for multi-column indices).
466-
*
467-
* For all other cases, we want to point at the first key >= the scankey
468-
* on the page. This guarantees that scans and insertions will happen
469-
* correctly.
443+
* On a leaf page, we always return the first key >= scan key
444+
* (which could be the last slot + 1).
445+
*--------------------
470446
*/
471447

472-
if (!(opaque->btpo_flags&BTP_LEAF)&&srchtype==BT_DESCENT)
473-
{/* We want the last key <, or first key
474-
* ==, the scan key. */
475-
result=_bt_compare(rel,itupdesc,page,keysz,scankey,high);
448+
if (opaque->btpo_flags&BTP_LEAF)
449+
returnlow;
476450

477-
if (result==0)
478-
{
479-
mid=_bt_firsteq(rel,itupdesc,page,keysz,scankey,high);
451+
/*--------------------
452+
* On a non-leaf page, there are special cases:
453+
*
454+
* For an insertion (srchtype != BT_DESCENT and natts == keysz)
455+
* always return first key >= scan key (which could be off the end).
456+
*
457+
* For a standard search (srchtype == BT_DESCENT and natts == keysz)
458+
* return the first equal key if one exists, else the last lesser key
459+
* if one exists, else the first slot on the page.
460+
*
461+
* For a partial-match search (srchtype == BT_DESCENT and natts < keysz)
462+
* return the last lesser key if one exists, else the first slot.
463+
*
464+
* Old comments:
465+
*For multi-column indices, we may scan using keys
466+
*not for all attrs. But we handle duplicates using all attrs
467+
*in _bt_insert/_bt_spool code. And so while searching on
468+
*internal pages having number of attrs > keysize we want to
469+
*point at the last item < the scankey, not at the first item
470+
*= the scankey (!!!), and let _bt_moveright decide later
471+
*whether to move right or not (see comments and example
472+
*there). Note also that INSERTions are not affected by this
473+
*code (since natts == keysz for inserts). - vadim 04/15/97
474+
*--------------------
475+
*/
480476

481-
/*
482-
* If natts > keysz we want last item < the scan key. See
483-
* comments above for multi-column indices.
484-
*/
485-
if (natts==keysz)
486-
returnmid;
487-
low=P_RIGHTMOST(opaque) ?P_HIKEY :P_FIRSTKEY;
488-
if (mid==low)
489-
returnmid;
490-
returnOffsetNumberPrev(mid);
491-
}
492-
elseif (result>0)
493-
returnhigh;
494-
else
495-
returnlow;
477+
if (haveEq)
478+
{
479+
/*
480+
* There is an equal key. We return either the first equal key
481+
* (which we just found), or the last lesser key.
482+
*
483+
* We need not check srchtype != BT_DESCENT here, since if that
484+
* is true then natts == keysz by assumption.
485+
*/
486+
if (natts==keysz)
487+
returnlow;/* return first equal key */
496488
}
497489
else
498-
/* we want the first key >= the scan key */
499490
{
500-
result=_bt_compare(rel,itupdesc,page,keysz,scankey,low);
501-
if (result <=0)
502-
returnlow;
503-
else
504-
{
505-
if (low==high)
506-
returnOffsetNumberNext(low);
507-
508-
result=_bt_compare(rel,itupdesc,page,keysz,scankey,high);
509-
if (result <=0)
510-
returnhigh;
511-
else
512-
returnOffsetNumberNext(high);
513-
}
491+
/*
492+
* There is no equal key. We return either the first greater key
493+
* (which we just found), or the last lesser key.
494+
*/
495+
if (srchtype!=BT_DESCENT)
496+
returnlow;/* return first greater key */
514497
}
515-
}
516498

517-
staticOffsetNumber
518-
_bt_firsteq(Relationrel,
519-
TupleDescitupdesc,
520-
Pagepage,
521-
Sizekeysz,
522-
ScanKeyscankey,
523-
OffsetNumberoffnum)
524-
{
525-
BTPageOpaqueopaque;
526-
OffsetNumberlimit;
527499

528-
opaque= (BTPageOpaque)PageGetSpecialPointer(page);
500+
if (low== (P_RIGHTMOST(opaque) ?P_HIKEY :P_FIRSTKEY))
501+
returnlow;/* there is no prior item */
529502

530-
/* skip the high key, if any */
531-
limit=P_RIGHTMOST(opaque) ?P_HIKEY :P_FIRSTKEY;
532-
533-
/* walk backwards looking for the first key in the chain of duplicates */
534-
while (offnum>limit
535-
&&_bt_compare(rel,itupdesc,page,
536-
keysz,scankey,OffsetNumberPrev(offnum))==0)
537-
offnum=OffsetNumberPrev(offnum);
538-
539-
returnoffnum;
503+
returnOffsetNumberPrev(low);
540504
}
541505

542506
/*
@@ -571,7 +535,6 @@ _bt_compare(Relation rel,
571535
{
572536
Datumdatum;
573537
BTItembtitem;
574-
ItemIditemid;
575538
IndexTupleitup;
576539
BTPageOpaqueopaque;
577540
ScanKeyentry;
@@ -589,12 +552,11 @@ _bt_compare(Relation rel,
589552
*/
590553

591554
opaque= (BTPageOpaque)PageGetSpecialPointer(page);
555+
592556
if (!(opaque->btpo_flags&BTP_LEAF)
593557
&&P_LEFTMOST(opaque)
594558
&&offnum==P_HIKEY)
595559
{
596-
itemid=PageGetItemId(page,offnum);
597-
598560
/*
599561
* we just have to believe that this will only be called with
600562
* offnum == P_HIKEY when P_HIKEY is the OffsetNumber of the first
@@ -621,7 +583,7 @@ _bt_compare(Relation rel,
621583
* on the page is greater than anything.
622584
*/
623585

624-
if (_bt_skeycmp(rel,keysz,scankey,page,itemid,
586+
if (_bt_skeycmp(rel,keysz,scankey,page,PageGetItemId(page,offnum),
625587
BTEqualStrategyNumber))
626588
return0;
627589
return1;

0 commit comments

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