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

Commit7ccaf13

Browse files
committed
Instead of using a numberOfRequiredKeys count to distinguish required
and non-required keys in a btree index scan, mark the required scankeyswith private flag bits SK_BT_REQFWD and/or SK_BT_REQBKWD. This seemsat least marginally clearer to me, and it eliminates a wired-into-the-data-structure assumption that required keys are consecutive. Even thoughthat assumption will remain true for the foreseeable future, having itin there makes the code seem more complex than necessary.
1 parentf6f43e7 commit7ccaf13

File tree

3 files changed

+92
-74
lines changed

3 files changed

+92
-74
lines changed

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.100 2006/01/17 00:09:01 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.101 2006/01/23 22:31:40 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -509,8 +509,8 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
509509
pgstat_count_index_scan(&scan->xs_pgstat_info);
510510

511511
/*
512-
* Examine the scan keys and eliminate any redundant keys; alsodiscover
513-
*how manykeys must be matched to continue the scan.
512+
* Examine the scan keys and eliminate any redundant keys; alsomark the
513+
* keys that must be matched to continue the scan.
514514
*/
515515
_bt_preprocess_keys(scan);
516516

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

Lines changed: 76 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtutils.c,v 1.68 2006/01/17 00:09:01 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/access/nbtree/nbtutils.c,v 1.69 2006/01/23 22:31:40 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -178,20 +178,21 @@ _bt_formitem(IndexTuple itup)
178178
* within each attribute may be done as a byproduct of the processing here,
179179
* but no other code depends on that.
180180
*
181-
*Aside from preparing so->keyData[], this routine sets
182-
*so->numberOfRequiredKeys to the number of quals that must be satisfied to
183-
*continue the scan. _bt_checkkeys usesthis. For example, if the quals
181+
*The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD
182+
*if they must be satisfied in order to continue the scan forward or backward
183+
*respectively. _bt_checkkeys usesthese flags. For example, if the quals
184184
* are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
185185
* (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
186186
* But once we reach tuples like (1,4,z) we can stop scanning because no
187-
* later tuples could match. This is reflected by setting
188-
* so->numberOfRequiredKeys to 2, the number of leading keys that must be
189-
* matched to continue the scan. In general, numberOfRequiredKeys is equal
190-
* to the number of keys for leading attributes with "=" keys, plus the
191-
* key(s) for the first non "=" attribute, which can be seen to be correct
192-
* by considering the above example. Note in particular that if there are no
193-
* keys for a given attribute, the keys for subsequent attributes can never
194-
* be required; for instance "WHERE y = 4" requires a full-index scan.
187+
* later tuples could match. This is reflected by marking the x and y keys,
188+
* but not the z key, with SK_BT_REQFWD. In general, the keys for leading
189+
* attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD.
190+
* For the first attribute without an "=" key, any "<" and "<=" keys are
191+
* marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD.
192+
* This can be seen to be correct by considering the above example. Note
193+
* in particular that if there are no keys for a given attribute, the keys for
194+
* subsequent attributes can never be required; for instance "WHERE y = 4"
195+
* requires a full-index scan.
195196
*
196197
* If possible, redundant keys are eliminated: we keep only the tightest
197198
* >/>= bound and the tightest </<= bound, and if there's an = key then
@@ -203,8 +204,9 @@ _bt_formitem(IndexTuple itup)
203204
* we could handle comparison of a RHS of the index datatype with a RHS of
204205
* another type, but that seems too much pain for too little gain.) So,
205206
* keys whose operator has a nondefault subtype (ie, its RHS is not of the
206-
* index datatype) are ignored here, except for noting whether they impose
207-
* an "=" condition or not.
207+
* index datatype) are ignored here, except for noting whether they include
208+
* an "=" condition or not. The logic about required keys still works if
209+
* we don't eliminate redundant keys.
208210
*
209211
* As a byproduct of this work, we can detect contradictory quals such
210212
* as "x = 1 AND x > 2". If we see that, we return so->quals_ok = FALSE,
@@ -239,7 +241,6 @@ _bt_preprocess_keys(IndexScanDesc scan)
239241
/* initialize result variables */
240242
so->qual_ok= true;
241243
so->numberOfKeys=0;
242-
so->numberOfRequiredKeys=0;
243244
scan->keys_are_unique= false;
244245

245246
if (numberOfKeys<1)
@@ -271,8 +272,27 @@ _bt_preprocess_keys(IndexScanDesc scan)
271272
}
272273
memcpy(outkeys,inkeys,sizeof(ScanKeyData));
273274
so->numberOfKeys=1;
274-
if (cur->sk_attno==1)
275-
so->numberOfRequiredKeys=1;
275+
/* We can mark the qual as required if it's for first index col */
276+
if (outkeys->sk_attno==1)
277+
{
278+
switch (outkeys->sk_strategy)
279+
{
280+
caseBTLessStrategyNumber:
281+
caseBTLessEqualStrategyNumber:
282+
outkeys->sk_flags |=SK_BT_REQFWD;
283+
break;
284+
caseBTEqualStrategyNumber:
285+
outkeys->sk_flags |= (SK_BT_REQFWD |SK_BT_REQBKWD);
286+
break;
287+
caseBTGreaterEqualStrategyNumber:
288+
caseBTGreaterStrategyNumber:
289+
outkeys->sk_flags |=SK_BT_REQBKWD;
290+
break;
291+
default:
292+
elog(ERROR,"unrecognized StrategyNumber: %d",
293+
(int)outkeys->sk_strategy);
294+
}
295+
}
276296
return;
277297
}
278298

@@ -400,21 +420,40 @@ _bt_preprocess_keys(IndexScanDesc scan)
400420
}
401421

402422
/*
403-
* Emit the cleaned-up keys into the outkeys[] array.
423+
* Emit the cleaned-up keys into the outkeys[] array, and then
424+
* mark them if they are required. They are required (possibly
425+
* only in one direction) if all attrs before this one had "=".
404426
*/
405427
for (j=BTMaxStrategyNumber;--j >=0;)
406428
{
407429
if (xform[j])
408-
memcpy(&outkeys[new_numberOfKeys++],xform[j],
409-
sizeof(ScanKeyData));
410-
}
430+
{
431+
ScanKeyoutkey=&outkeys[new_numberOfKeys++];
411432

412-
/*
413-
* If all attrs before this one had "=", include these keys into
414-
* the required-keys count.
415-
*/
416-
if (priorNumberOfEqualCols==attno-1)
417-
so->numberOfRequiredKeys=new_numberOfKeys;
433+
memcpy(outkey,xform[j],sizeof(ScanKeyData));
434+
if (priorNumberOfEqualCols==attno-1)
435+
{
436+
switch (outkey->sk_strategy)
437+
{
438+
caseBTLessStrategyNumber:
439+
caseBTLessEqualStrategyNumber:
440+
outkey->sk_flags |=SK_BT_REQFWD;
441+
break;
442+
caseBTEqualStrategyNumber:
443+
outkey->sk_flags |= (SK_BT_REQFWD |
444+
SK_BT_REQBKWD);
445+
break;
446+
caseBTGreaterEqualStrategyNumber:
447+
caseBTGreaterStrategyNumber:
448+
outkey->sk_flags |=SK_BT_REQBKWD;
449+
break;
450+
default:
451+
elog(ERROR,"unrecognized StrategyNumber: %d",
452+
(int)outkey->sk_strategy);
453+
}
454+
}
455+
}
456+
}
418457

419458
/*
420459
* Exit loop here if done.
@@ -578,8 +617,7 @@ _bt_checkkeys(IndexScanDesc scan,
578617
* match" subset. On a backward scan, however, we should keep
579618
* going.
580619
*/
581-
if (ikey<so->numberOfRequiredKeys&&
582-
ScanDirectionIsForward(dir))
620+
if ((key->sk_flags&SK_BT_REQFWD)&&ScanDirectionIsForward(dir))
583621
*continuescan= false;
584622

585623
/*
@@ -593,45 +631,21 @@ _bt_checkkeys(IndexScanDesc scan,
593631
if (!DatumGetBool(test))
594632
{
595633
/*
596-
* Tuple fails this qual. If it's a required qual, then we may be
597-
* able to conclude no further tuples will pass, either. We have
598-
* to look at the scan direction and the qual type.
599-
*
600-
* Note: the only case in which we would keep going after failing
601-
* a required qual is if there are partially-redundant quals that
602-
* _bt_preprocess_keys() was unable to eliminate. For example,
603-
* given "x > 4 AND x > 10" where both are cross-type comparisons
604-
* and so not removable, we might start the scan at the x = 4
605-
* boundary point.The "x > 10" condition will fail until we pass
606-
* x = 10, but we must not stop the scan on its account.
634+
* Tuple fails this qual. If it's a required qual for the current
635+
* scan direction, then we can conclude no further tuples will
636+
* pass, either.
607637
*
608638
* Note: because we stop the scan as soon as any required equality
609639
* qual fails, it is critical that equality quals be used for the
610640
* initial positioning in _bt_first() when they are available. See
611641
* comments in _bt_first().
612642
*/
613-
if (ikey<so->numberOfRequiredKeys)
614-
{
615-
switch (key->sk_strategy)
616-
{
617-
caseBTLessStrategyNumber:
618-
caseBTLessEqualStrategyNumber:
619-
if (ScanDirectionIsForward(dir))
620-
*continuescan= false;
621-
break;
622-
caseBTEqualStrategyNumber:
623-
*continuescan= false;
624-
break;
625-
caseBTGreaterEqualStrategyNumber:
626-
caseBTGreaterStrategyNumber:
627-
if (ScanDirectionIsBackward(dir))
628-
*continuescan= false;
629-
break;
630-
default:
631-
elog(ERROR,"unrecognized StrategyNumber: %d",
632-
key->sk_strategy);
633-
}
634-
}
643+
if ((key->sk_flags&SK_BT_REQFWD)&&
644+
ScanDirectionIsForward(dir))
645+
*continuescan= false;
646+
elseif ((key->sk_flags&SK_BT_REQBKWD)&&
647+
ScanDirectionIsBackward(dir))
648+
*continuescan= false;
635649

636650
/*
637651
* In any case, this indextuple doesn't match the qual.

‎src/include/access/nbtree.h

Lines changed: 13 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $PostgreSQL: pgsql/src/include/access/nbtree.h,v 1.89 2005/12/07 19:37:53 tgl Exp $
10+
* $PostgreSQL: pgsql/src/include/access/nbtree.h,v 1.90 2006/01/23 22:31:41 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -368,16 +368,15 @@ typedef BTStackData *BTStack;
368368

369369
/*
370370
*BTScanOpaqueData is used to remember which buffers we're currently
371-
*examining inthe scan.We keep these buffers pinned (but not locked,
372-
*see nbtree.c) and recorded in the opaque entry of the scan to avoid
371+
*examining inan indexscan. Between calls to btgettuple or btgetmulti,
372+
*we keep these buffers pinned (but not locked, see nbtree.c) to avoid
373373
*doing a ReadBuffer() for every tuple in the index.
374374
*
375-
*And it's used to remember actual scankey info (we need it
376-
*if some scankeys evaled at runtime).
375+
*We also store preprocessed versions of the scan keys in this structure.
376+
*See _bt_preprocess_keys() for details of the preprocessing.
377377
*
378378
*curHeapIptr & mrkHeapIptr are heap iptr-s from current/marked
379-
*index tuples: we don't adjust scans on insertions (and, if LLL
380-
*is ON, don't hold locks on index pages between passes) - we
379+
*index tuples: we don't adjust scans on insertions - instead we
381380
*use these pointers to restore index scan positions...
382381
*- vadim 07/29/98
383382
*/
@@ -391,13 +390,18 @@ typedef struct BTScanOpaqueData
391390
/* these fields are set by _bt_preprocess_keys(): */
392391
boolqual_ok;/* false if qual can never be satisfied */
393392
intnumberOfKeys;/* number of preprocessed scan keys */
394-
intnumberOfRequiredKeys;/* number of keys that must be matched
395-
* to continue the scan */
396393
ScanKeykeyData;/* array of preprocessed scan keys */
397394
}BTScanOpaqueData;
398395

399396
typedefBTScanOpaqueData*BTScanOpaque;
400397

398+
/*
399+
* We use these private sk_flags bits in preprocessed scan keys
400+
*/
401+
#defineSK_BT_REQFWD0x00010000/* required to continue forward scan */
402+
#defineSK_BT_REQBKWD0x00020000/* required to continue backward scan */
403+
404+
401405
/*
402406
* prototypes for functions in nbtree.c (external entry points for btree)
403407
*/

0 commit comments

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