Skip to content

Commit 7b2a8e4

Browse files
bmomjianbmomjian
committed
Currently,only the first column of multi-column indices
is used to find start scan position of Indexscan-s. To speed up finding scan start position,I have changed _bt_first() to use as many keys as possible. I'll attach the patch here. Regards. Hiroshi Inoue
1 parent 62045e6 commit 7b2a8e4

File tree

2 files changed

+92
-48
lines changed

2 files changed

+92
-48
lines changed

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

Lines changed: 84 additions & 46 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.53 1999/07/17 20:16:43 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.54 1999/09/27 18:20:21 momjian Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -727,11 +727,15 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
727727
RegProcedure proc;
728728
int result;
729729
BTScanOpaque so;
730-
ScanKeyData skdata;
731730
Size keysok;
732-
int i;
733-
int nKeyIndex = -1;
734731

732+
bool strategyCheck;
733+
ScanKey scankeys = 0;
734+
int keysCount = 0;
735+
int *nKeyIs = 0;
736+
int i, j;
737+
StrategyNumber strat_total;
738+
735739
rel = scan->relation;
736740
so = (BTScanOpaque) scan->opaque;
737741

@@ -742,38 +746,57 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
742746
so->numberOfFirstKeys = 0; /* may be changed by _bt_orderkeys */
743747
so->qual_ok = 1; /* may be changed by _bt_orderkeys */
744748
scan->scanFromEnd = false;
749+
strategyCheck = false;
745750
if (so->numberOfKeys > 0)
746751
{
747752
_bt_orderkeys(rel, so);
748753

749-
if (ScanDirectionIsBackward(dir))
754+
if (so->qual_ok)
755+
strategyCheck = true;
756+
}
757+
strat_total = BTEqualStrategyNumber;
758+
if (strategyCheck)
759+
{
760+
AttrNumber attno;
761+
762+
nKeyIs = (int *)palloc(so->numberOfKeys*sizeof(int));
763+
for (i=0; i < so->numberOfKeys; i++)
750764
{
751-
for (i = 0; i < so->numberOfKeys; i++)
765+
attno = so->keyData[i].sk_attno;
766+
if (attno == keysCount)
767+
continue;
768+
if (attno > keysCount + 1)
769+
break;
770+
strat = _bt_getstrat(rel, attno,
771+
so->keyData[i].sk_procedure);
772+
if (strat == strat_total ||
773+
strat == BTEqualStrategyNumber)
752774
{
753-
if (so->keyData[i].sk_attno != 1)
775+
nKeyIs[keysCount++] = i;
776+
continue;
777+
}
778+
if (ScanDirectionIsBackward(dir) &&
779+
(strat == BTLessStrategyNumber ||
780+
strat == BTLessEqualStrategyNumber) )
781+
{
782+
nKeyIs[keysCount++] = i;
783+
strat_total = strat;
784+
if (strat == BTLessStrategyNumber)
754785
break;
755-
strat = _bt_getstrat(rel, so->keyData[i].sk_attno,
756-
so->keyData[i].sk_procedure);
757-
if (strat == BTLessStrategyNumber ||
758-
strat == BTLessEqualStrategyNumber ||
759-
strat == BTEqualStrategyNumber)
760-
{
761-
nKeyIndex = i;
786+
continue;
787+
}
788+
if (ScanDirectionIsForward(dir) &&
789+
(strat == BTGreaterStrategyNumber ||
790+
strat == BTGreaterEqualStrategyNumber) )
791+
{
792+
nKeyIs[keysCount++] = i;
793+
strat_total = strat;
794+
if (strat == BTGreaterStrategyNumber)
762795
break;
763-
}
796+
continue;
764797
}
765798
}
766-
else
767-
{
768-
strat = _bt_getstrat(rel, 1, so->keyData[0].sk_procedure);
769-
770-
if (strat == BTLessStrategyNumber ||
771-
strat == BTLessEqualStrategyNumber)
772-
;
773-
else
774-
nKeyIndex = 0;
775-
}
776-
if (nKeyIndex < 0)
799+
if (!keysCount)
777800
scan->scanFromEnd = true;
778801
}
779802
else
@@ -784,7 +807,11 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
784807

785808
/* if we just need to walk down one edge of the tree, do that */
786809
if (scan->scanFromEnd)
810+
{
811+
if (nKeyIs)
812+
pfree(nKeyIs);
787813
return _bt_endpoint(scan, dir);
814+
}
788815

789816
itupdesc = RelationGetDescr(rel);
790817
current = &(scan->currentItemData);
@@ -796,16 +823,24 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
796823
* at the right place in the scan.
797824
*/
798825
/* _bt_orderkeys disallows it, but it's place to add some code latter */
799-
if (so->keyData[0].sk_flags & SK_ISNULL)
826+
scankeys = (ScanKey)palloc(keysCount*sizeof(ScanKeyData));
827+
for (i=0; i < keysCount; i++)
800828
{
801-
elog(ERROR, "_bt_first: btree doesn't support is(not)null, yet");
802-
return (RetrieveIndexResult) NULL;
829+
j = nKeyIs[i];
830+
if (so->keyData[j].sk_flags & SK_ISNULL)
831+
{
832+
pfree(nKeyIs);
833+
pfree(scankeys);
834+
elog(ERROR, "_bt_first: btree doesn't support is(not)null, yet");
835+
return ((RetrieveIndexResult) NULL);
836+
}
837+
proc = index_getprocid(rel, i+1, BTORDER_PROC);
838+
ScanKeyEntryInitialize(scankeys+i, so->keyData[j].sk_flags,
839+
i+1, proc, so->keyData[j].sk_argument);
803840
}
804-
proc = index_getprocid(rel, 1, BTORDER_PROC);
805-
ScanKeyEntryInitialize(&skdata, so->keyData[nKeyIndex].sk_flags,
806-
1, proc, so->keyData[nKeyIndex].sk_argument);
841+
if (nKeyIs) pfree(nKeyIs);
807842

808-
stack = _bt_search(rel, 1, &skdata, &buf);
843+
stack = _bt_search(rel, keysCount, scankeys, &buf);
809844
_bt_freestack(stack);
810845

811846
blkno = BufferGetBlockNumber(buf);
@@ -823,6 +858,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
823858
ItemPointerSetInvalid(current);
824859
so->btso_curbuf = InvalidBuffer;
825860
_bt_relbuf(rel, buf, BT_READ);
861+
pfree(scankeys);
826862
return (RetrieveIndexResult) NULL;
827863
}
828864
maxoff = PageGetMaxOffsetNumber(page);
@@ -835,7 +871,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
835871
*/
836872

837873
while (maxoff == P_HIKEY && !P_RIGHTMOST(pop) &&
838-
_bt_skeycmp(rel, 1, &skdata, page,
874+
_bt_skeycmp(rel, keysCount, scankeys, page,
839875
PageGetItemId(page, P_HIKEY),
840876
BTGreaterEqualStrategyNumber))
841877
{
@@ -849,6 +885,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
849885
ItemPointerSetInvalid(current);
850886
so->btso_curbuf = InvalidBuffer;
851887
_bt_relbuf(rel, buf, BT_READ);
888+
pfree(scankeys);
852889
return (RetrieveIndexResult) NULL;
853890
}
854891
maxoff = PageGetMaxOffsetNumber(page);
@@ -857,7 +894,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
857894

858895

859896
/* find the nearest match to the manufactured scan key on the page */
860-
offnum = _bt_binsrch(rel, buf, 1, &skdata, BT_DESCENT);
897+
offnum = _bt_binsrch(rel, buf, keysCount, scankeys, BT_DESCENT);
861898

862899
if (offnum > maxoff)
863900
{
@@ -872,12 +909,11 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
872909
* we're looking for minus the value we're looking at in the index.
873910
*/
874911

875-
result = _bt_compare(rel, itupdesc, page, 1, &skdata, offnum);
912+
result = _bt_compare(rel, itupdesc, page, keysCount, scankeys, offnum);
876913

877914
/* it's yet other place to add some code latter for is(not)null */
878915

879-
strat = _bt_getstrat(rel, 1, so->keyData[nKeyIndex].sk_procedure);
880-
916+
strat = strat_total;
881917
switch (strat)
882918
{
883919
case BTLessStrategyNumber:
@@ -890,7 +926,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
890926

891927
offnum = ItemPointerGetOffsetNumber(current);
892928
page = BufferGetPage(buf);
893-
result = _bt_compare(rel, itupdesc, page, 1, &skdata, offnum);
929+
result = _bt_compare(rel, itupdesc, page, keysCount, scankeys, offnum);
894930
} while (result <= 0);
895931

896932
}
@@ -906,12 +942,11 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
906942

907943
offnum = ItemPointerGetOffsetNumber(current);
908944
page = BufferGetPage(buf);
909-
result = _bt_compare(rel, itupdesc, page, 1, &skdata, offnum);
945+
result = _bt_compare(rel, itupdesc, page, keysCount, scankeys, offnum);
910946
} while (result >= 0);
911-
912-
if (result < 0)
913-
_bt_twostep(scan, &buf, BackwardScanDirection);
914947
}
948+
if (result < 0)
949+
_bt_twostep(scan, &buf, BackwardScanDirection);
915950
break;
916951

917952
case BTEqualStrategyNumber:
@@ -920,6 +955,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
920955
_bt_relbuf(scan->relation, buf, BT_READ);
921956
so->btso_curbuf = InvalidBuffer;
922957
ItemPointerSetInvalid(&(scan->currentItemData));
958+
pfree(scankeys);
923959
return (RetrieveIndexResult) NULL;
924960
}
925961
else if (ScanDirectionIsBackward(dir))
@@ -931,7 +967,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
931967

932968
offnum = ItemPointerGetOffsetNumber(current);
933969
page = BufferGetPage(buf);
934-
result = _bt_compare(rel, itupdesc, page, 1, &skdata, offnum);
970+
result = _bt_compare(rel, itupdesc, page, keysCount, scankeys, offnum);
935971
} while (result == 0);
936972

937973
if (result < 0)
@@ -950,6 +986,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
950986
_bt_relbuf(scan->relation, buf, BT_READ);
951987
so->btso_curbuf = InvalidBuffer;
952988
ItemPointerSetInvalid(&(scan->currentItemData));
989+
pfree(scankeys);
953990
return (RetrieveIndexResult) NULL;
954991
}
955992
}
@@ -974,7 +1011,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
9741011

9751012
page = BufferGetPage(buf);
9761013
offnum = ItemPointerGetOffsetNumber(current);
977-
result = _bt_compare(rel, itupdesc, page, 1, &skdata, offnum);
1014+
result = _bt_compare(rel, itupdesc, page, keysCount, scankeys, offnum);
9781015
} while (result < 0);
9791016

9801017
if (result > 0)
@@ -993,12 +1030,13 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
9931030

9941031
offnum = ItemPointerGetOffsetNumber(current);
9951032
page = BufferGetPage(buf);
996-
result = _bt_compare(rel, itupdesc, page, 1, &skdata, offnum);
1033+
result = _bt_compare(rel, itupdesc, page, keysCount, scankeys, offnum);
9971034
} while (result >= 0);
9981035
}
9991036
break;
10001037
}
10011038

1039+
pfree(scankeys);
10021040
/* okay, current item pointer for the scan is right */
10031041
offnum = ItemPointerGetOffsetNumber(current);
10041042
page = BufferGetPage(buf);

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

Lines changed: 8 additions & 2 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/nbtutils.c,v 1.32 1999/07/17 20:16:43 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.33 1999/09/27 18:20:21 momjian Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -101,6 +101,7 @@ _bt_orderkeys(Relation relation, BTScanOpaque so)
101101
uint16 numberOfKeys = so->numberOfKeys;
102102
uint16 new_numberOfKeys = 0;
103103
AttrNumber attno = 1;
104+
bool equalStrategyEnd, underEqualStrategy;
104105

105106
if (numberOfKeys < 1)
106107
return;
@@ -136,6 +137,8 @@ _bt_orderkeys(Relation relation, BTScanOpaque so)
136137
for (j = 0; j <= BTMaxStrategyNumber; j++)
137138
init[j] = 0;
138139

140+
equalStrategyEnd = false;
141+
underEqualStrategy = true;
139142
/* check each key passed in */
140143
for (i = 0;;)
141144
{
@@ -150,6 +153,7 @@ _bt_orderkeys(Relation relation, BTScanOpaque so)
150153
if (cur->sk_attno != attno + 1 && i < numberOfKeys)
151154
elog(ERROR, "_bt_orderkeys: key(s) for attribute %d missed", attno + 1);
152155

156+
underEqualStrategy = (!equalStrategyEnd);
153157
/*
154158
* If = has been specified, no other key will be used. In case
155159
* of key < 2 && key == 1 and so on we have to set qual_ok to
@@ -175,6 +179,8 @@ _bt_orderkeys(Relation relation, BTScanOpaque so)
175179
init[BTGreaterEqualStrategyNumber - 1] = 0;
176180
init[BTGreaterStrategyNumber - 1] = 0;
177181
}
182+
else
183+
equalStrategyEnd = true;
178184

179185
/* only one of <, <= */
180186
if (init[BTLessStrategyNumber - 1]
@@ -223,7 +229,7 @@ _bt_orderkeys(Relation relation, BTScanOpaque so)
223229
if (init[j])
224230
key[new_numberOfKeys++] = xform[j];
225231

226-
if (attno == 1)
232+
if (underEqualStrategy)
227233
so->numberOfFirstKeys = new_numberOfKeys;
228234

229235
if (i == numberOfKeys)

0 commit comments

Comments
 (0)