Debian Codegraph @

src/backend/access/nbtree/nbtutils.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * nbtutils.c
4 * Utility code for Postgres btree implementation.
5 *
6 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/access/nbtree/nbtutils.c
12 *
13 *-------------------------------------------------------------------------
14 */
15
16 #include "postgres.h"
17
18 #include <time.h>
19
20 #include "access/nbtree.h"
21 #include "access/reloptions.h"
22 #include "commands/progress.h"
23 #include "miscadmin.h"
24 #include "utils/datum.h"
25 #include "utils/lsyscache.h"
26
27 #define LOOK_AHEAD_REQUIRED_RECHECKS 3
28 #define LOOK_AHEAD_DEFAULT_DISTANCE 5
29 #define NSKIPADVANCES_THRESHOLD 3
30
31 static inline int32 _bt_compare_array_skey(FmgrInfo *orderproc,
32 Datum tupdatum, bool tupnull,
33 Datum arrdatum, ScanKey cur);
34 static void _bt_binsrch_skiparray_skey(bool cur_elem_trig, ScanDirection dir,
35 Datum tupdatum, bool tupnull,
36 BTArrayKeyInfo *array, ScanKey cur,
37 int32 *set_elem_result);
38 static void _bt_skiparray_set_element(Relation rel, ScanKey skey, BTArrayKeyInfo *array,
39 int32 set_elem_result, Datum tupdatum, bool tupnull);
40 static void _bt_skiparray_set_isnull(Relation rel, ScanKey skey, BTArrayKeyInfo *array);
41 static void _bt_array_set_low_or_high(Relation rel, ScanKey skey,
42 BTArrayKeyInfo *array, bool low_not_high);
43 static bool _bt_array_decrement(Relation rel, ScanKey skey, BTArrayKeyInfo *array);
44 static bool _bt_array_increment(Relation rel, ScanKey skey, BTArrayKeyInfo *array);
45 static bool _bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir,
46 bool *skip_array_set);
47 static bool _bt_tuple_before_array_skeys(IndexScanDesc scan, ScanDirection dir,
48 IndexTuple tuple, TupleDesc tupdesc, int tupnatts,
49 bool readpagetup, int sktrig, bool *scanBehind);
50 static bool _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
51 IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
52 int sktrig, bool sktrig_required);
53 #ifdef USE_ASSERT_CHECKING
54 static bool _bt_verify_keys_with_arraykeys(IndexScanDesc scan);
55 #endif
56 static bool _bt_oppodir_checkkeys(IndexScanDesc scan, ScanDirection dir,
57 IndexTuple finaltup);
58 static bool _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
59 IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
60 bool advancenonrequired, bool forcenonrequired,
61 bool *continuescan, int *ikey);
62 static bool _bt_check_rowcompare(ScanKey header,
63 IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
64 ScanDirection dir, bool forcenonrequired, bool *continuescan);
65 static void _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate,
66 int tupnatts, TupleDesc tupdesc);
67 static int _bt_keep_natts(Relation rel, IndexTuple lastleft,
68 IndexTuple firstright, BTScanInsert itup_key);
69
70
71 /*
72 * _bt_mkscankey
73 * Build an insertion scan key that contains comparison data from itup
74 * as well as comparator routines appropriate to the key datatypes.
75 *
76 * The result is intended for use with _bt_compare() and _bt_truncate().
77 * Callers that don't need to fill out the insertion scankey arguments
78 * (e.g. they use an ad-hoc comparison routine, or only need a scankey
79 * for _bt_truncate()) can pass a NULL index tuple. The scankey will
80 * be initialized as if an "all truncated" pivot tuple was passed
81 * instead.
82 *
83 * Note that we may occasionally have to share lock the metapage to
84 * determine whether or not the keys in the index are expected to be
85 * unique (i.e. if this is a "heapkeyspace" index). We assume a
86 * heapkeyspace index when caller passes a NULL tuple, allowing index
87 * build callers to avoid accessing the non-existent metapage. We
88 * also assume that the index is _not_ allequalimage when a NULL tuple
89 * is passed; CREATE INDEX callers call _bt_allequalimage() to set the
90 * field themselves.
91 */
92 BTScanInsert
93 _bt_mkscankey(Relation rel, IndexTuple itup)
94 {
95 BTScanInsert key;
96 ScanKey skey;
97 TupleDesc itupdesc;
98 int indnkeyatts;
99 int16 *indoption;
100 int tupnatts;
101 int i;
102
103 itupdesc = RelationGetDescr(rel);
104 indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
105 indoption = rel->rd_indoption;
106 tupnatts = itup ? BTreeTupleGetNAtts(itup, rel) : 0;
107
108 Assert(tupnatts <= IndexRelationGetNumberOfAttributes(rel));
109
110 /*
111 * We'll execute search using scan key constructed on key columns.
112 * Truncated attributes and non-key attributes are omitted from the final
113 * scan key.
114 */
115 key = palloc(offsetof(BTScanInsertData, scankeys) +
116 sizeof(ScanKeyData) * indnkeyatts);
117 if (itup)
118 _bt_metaversion(rel, &key->heapkeyspace, &key->allequalimage);
119 else
120 {
121 /* Utility statement callers can set these fields themselves */
122 key->heapkeyspace = true;
123 key->allequalimage = false;
124 }
125 key->anynullkeys = false; /* initial assumption */
126 key->nextkey = false; /* usual case, required by btinsert */
127 key->backward = false; /* usual case, required by btinsert */
128 key->keysz = Min(indnkeyatts, tupnatts);
129 key->scantid = key->heapkeyspace && itup ?
130 BTreeTupleGetHeapTID(itup) : NULL;
131 skey = key->scankeys;
132 for (i = 0; i < indnkeyatts; i++)
133 {
134 FmgrInfo *procinfo;
135 Datum arg;
136 bool null;
137 int flags;
138
139 /*
140 * We can use the cached (default) support procs since no cross-type
141 * comparison can be needed.
142 */
143 procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
144
145 /*
146 * Key arguments built from truncated attributes (or when caller
147 * provides no tuple) are defensively represented as NULL values. They
148 * should never be used.
149 */
150 if (i < tupnatts)
151 arg = index_getattr(itup, i + 1, itupdesc, &null);
152 else
153 {
154 arg = (Datum) 0;
155 null = true;
156 }
157 flags = (null ? SK_ISNULL : 0) | (indoption[i] << SK_BT_INDOPTION_SHIFT);
158 ScanKeyEntryInitializeWithInfo(&skey[i],
159 flags,
160 (AttrNumber) (i + 1),
161 InvalidStrategy,
162 InvalidOid,
163 rel->rd_indcollation[i],
164 procinfo,
165 arg);
166 /* Record if any key attribute is NULL (or truncated) */
167 if (null)
168 key->anynullkeys = true;
169 }
170
171 /*
172 * In NULLS NOT DISTINCT mode, we pretend that there are no null keys, so
173 * that full uniqueness check is done.
174 */
175 if (rel->rd_index->indnullsnotdistinct)
176 key->anynullkeys = false;
177
178 return key;
179 }
180
181 /*
182 * free a retracement stack made by _bt_search.
183 */
184 void
185 _bt_freestack(BTStack stack)
186 {
187 BTStack ostack;
188
189 while (stack != NULL)
190 {
191 ostack = stack;
192 stack = stack->bts_parent;
193 pfree(ostack);
194 }
195 }
196
197 /*
198 * _bt_compare_array_skey() -- apply array comparison function
199 *
200 * Compares caller's tuple attribute value to a scan key/array element.
201 * Helper function used during binary searches of SK_SEARCHARRAY arrays.
202 *
203 * This routine returns:
204 * <0 if tupdatum < arrdatum;
205 * 0 if tupdatum == arrdatum;
206 * >0 if tupdatum > arrdatum.
207 *
208 * This is essentially the same interface as _bt_compare: both functions
209 * compare the value that they're searching for to a binary search pivot.
210 * However, unlike _bt_compare, this function's "tuple argument" comes first,
211 * while its "array/scankey argument" comes second.
212 */
213 static inline int32
214 _bt_compare_array_skey(FmgrInfo *orderproc,
215 Datum tupdatum, bool tupnull,
216 Datum arrdatum, ScanKey cur)
217 {
218 int32 result = 0;
219
220 Assert(cur->sk_strategy == BTEqualStrategyNumber);
221 Assert(!(cur->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL)));
222
223 if (tupnull) /* NULL tupdatum */
224 {
225 if (cur->sk_flags & SK_ISNULL)
226 result = 0; /* NULL "=" NULL */
227 else if (cur->sk_flags & SK_BT_NULLS_FIRST)
228 result = -1; /* NULL "<" NOT_NULL */
229 else
230 result = 1; /* NULL ">" NOT_NULL */
231 }
232 else if (cur->sk_flags & SK_ISNULL) /* NOT_NULL tupdatum, NULL arrdatum */
233 {
234 if (cur->sk_flags & SK_BT_NULLS_FIRST)
235 result = 1; /* NOT_NULL ">" NULL */
236 else
237 result = -1; /* NOT_NULL "<" NULL */
238 }
239 else
240 {
241 /*
242 * Like _bt_compare, we need to be careful of cross-type comparisons,
243 * so the left value has to be the value that came from an index tuple
244 */
245 result = DatumGetInt32(FunctionCall2Coll(orderproc, cur->sk_collation,
246 tupdatum, arrdatum));
247
248 /*
249 * We flip the sign by following the obvious rule: flip whenever the
250 * column is a DESC column.
251 *
252 * _bt_compare does it the wrong way around (flip when *ASC*) in order
253 * to compensate for passing its orderproc arguments backwards. We
254 * don't need to play these games because we find it natural to pass
255 * tupdatum as the left value (and arrdatum as the right value).
256 */
257 if (cur->sk_flags & SK_BT_DESC)
258 INVERT_COMPARE_RESULT(result);
259 }
260
261 return result;
262 }
263
264 /*
265 * _bt_binsrch_array_skey() -- Binary search for next matching array key
266 *
267 * Returns an index to the first array element >= caller's tupdatum argument.
268 * This convention is more natural for forwards scan callers, but that can't
269 * really matter to backwards scan callers. Both callers require handling for
270 * the case where the match we return is < tupdatum, and symmetric handling
271 * for the case where our best match is > tupdatum.
272 *
273 * Also sets *set_elem_result to the result _bt_compare_array_skey returned
274 * when we used it to compare the matching array element to tupdatum/tupnull.
275 *
276 * cur_elem_trig indicates if array advancement was triggered by this array's
277 * scan key, and that the array is for a required scan key. We can apply this
278 * information to find the next matching array element in the current scan
279 * direction using far fewer comparisons (fewer on average, compared to naive
280 * binary search). This scheme takes advantage of an important property of
281 * required arrays: required arrays always advance in lockstep with the index
282 * scan's progress through the index's key space.
283 */
284 int
285 _bt_binsrch_array_skey(FmgrInfo *orderproc,
286 bool cur_elem_trig, ScanDirection dir,
287 Datum tupdatum, bool tupnull,
288 BTArrayKeyInfo *array, ScanKey cur,
289 int32 *set_elem_result)
290 {
291 int low_elem = 0,
292 mid_elem = -1,
293 high_elem = array->num_elems - 1,
294 result = 0;
295 Datum arrdatum;
296
297 Assert(cur->sk_flags & SK_SEARCHARRAY);
298 Assert(!(cur->sk_flags & SK_BT_SKIP));
299 Assert(!(cur->sk_flags & SK_ISNULL)); /* SAOP arrays never have NULLs */
300 Assert(cur->sk_strategy == BTEqualStrategyNumber);
301
302 if (cur_elem_trig)
303 {
304 Assert(!ScanDirectionIsNoMovement(dir));
305 Assert(cur->sk_flags & SK_BT_REQFWD);
306
307 /*
308 * When the scan key that triggered array advancement is a required
309 * array scan key, it is now certain that the current array element
310 * (plus all prior elements relative to the current scan direction)
311 * cannot possibly be at or ahead of the corresponding tuple value.
312 * (_bt_checkkeys must have called _bt_tuple_before_array_skeys, which
313 * makes sure this is true as a condition of advancing the arrays.)
314 *
315 * This makes it safe to exclude array elements up to and including
316 * the former-current array element from our search.
317 *
318 * Separately, when array advancement was triggered by a required scan
319 * key, the array element immediately after the former-current element
320 * is often either an exact tupdatum match, or a "close by" near-match
321 * (a near-match tupdatum is one whose key space falls _between_ the
322 * former-current and new-current array elements). We'll detect both
323 * cases via an optimistic comparison of the new search lower bound
324 * (or new search upper bound in the case of backwards scans).
325 */
326 if (ScanDirectionIsForward(dir))
327 {
328 low_elem = array->cur_elem + 1; /* old cur_elem exhausted */
329
330 /* Compare prospective new cur_elem (also the new lower bound) */
331 if (high_elem >= low_elem)
332 {
333 arrdatum = array->elem_values[low_elem];
334 result = _bt_compare_array_skey(orderproc, tupdatum, tupnull,
335 arrdatum, cur);
336
337 if (result <= 0)
338 {
339 /* Optimistic comparison optimization worked out */
340 *set_elem_result = result;
341 return low_elem;
342 }
343 mid_elem = low_elem;
344 low_elem++; /* this cur_elem exhausted, too */
345 }
346
347 if (high_elem < low_elem)
348 {
349 /* Caller needs to perform "beyond end" array advancement */
350 *set_elem_result = 1;
351 return high_elem;
352 }
353 }
354 else
355 {
356 high_elem = array->cur_elem - 1; /* old cur_elem exhausted */
357
358 /* Compare prospective new cur_elem (also the new upper bound) */
359 if (high_elem >= low_elem)
360 {
361 arrdatum = array->elem_values[high_elem];
362 result = _bt_compare_array_skey(orderproc, tupdatum, tupnull,
363 arrdatum, cur);
364
365 if (result >= 0)
366 {
367 /* Optimistic comparison optimization worked out */
368 *set_elem_result = result;
369 return high_elem;
370 }
371 mid_elem = high_elem;
372 high_elem--; /* this cur_elem exhausted, too */
373 }
374
375 if (high_elem < low_elem)
376 {
377 /* Caller needs to perform "beyond end" array advancement */
378 *set_elem_result = -1;
379 return low_elem;
380 }
381 }
382 }
383
384 while (high_elem > low_elem)
385 {
386 mid_elem = low_elem + ((high_elem - low_elem) / 2);
387 arrdatum = array->elem_values[mid_elem];
388
389 result = _bt_compare_array_skey(orderproc, tupdatum, tupnull,
390 arrdatum, cur);
391
392 if (result == 0)
393 {
394 /*
395 * It's safe to quit as soon as we see an equal array element.
396 * This often saves an extra comparison or two...
397 */
398 low_elem = mid_elem;
399 break;
400 }
401
402 if (result > 0)
403 low_elem = mid_elem + 1;
404 else
405 high_elem = mid_elem;
406 }
407
408 /*
409 * ...but our caller also cares about how its searched-for tuple datum
410 * compares to the low_elem datum. Must always set *set_elem_result with
411 * the result of that comparison specifically.
412 */
413 if (low_elem != mid_elem)
414 result = _bt_compare_array_skey(orderproc, tupdatum, tupnull,
415 array->elem_values[low_elem], cur);
416
417 *set_elem_result = result;
418
419 return low_elem;
420 }
421
422 /*
423 * _bt_binsrch_skiparray_skey() -- "Binary search" within a skip array
424 *
425 * Does not return an index into the array, since skip arrays don't really
426 * contain elements (they generate their array elements procedurally instead).
427 * Our interface matches that of _bt_binsrch_array_skey in every other way.
428 *
429 * Sets *set_elem_result just like _bt_binsrch_array_skey would with a true
430 * array. The value 0 indicates that tupdatum/tupnull is within the range of
431 * the skip array. We return -1 when tupdatum/tupnull is lower that any value
432 * within the range of the array, and 1 when it is higher than every value.
433 * Caller should pass *set_elem_result to _bt_skiparray_set_element to advance
434 * the array.
435 *
436 * cur_elem_trig indicates if array advancement was triggered by this array's
437 * scan key. We use this to optimize-away comparisons that are known by our
438 * caller to be unnecessary from context, just like _bt_binsrch_array_skey.
439 */
440 static void
441 _bt_binsrch_skiparray_skey(bool cur_elem_trig, ScanDirection dir,
442 Datum tupdatum, bool tupnull,
443 BTArrayKeyInfo *array, ScanKey cur,
444 int32 *set_elem_result)
445 {
446 Assert(cur->sk_flags & SK_BT_SKIP);
447 Assert(cur->sk_flags & SK_SEARCHARRAY);
448 Assert(cur->sk_flags & SK_BT_REQFWD);
449 Assert(array->num_elems == -1);
450 Assert(!ScanDirectionIsNoMovement(dir));
451
452 if (array->null_elem)
453 {
454 Assert(!array->low_compare && !array->high_compare);
455
456 *set_elem_result = 0;
457 return;
458 }
459
460 if (tupnull) /* NULL tupdatum */
461 {
462 if (cur->sk_flags & SK_BT_NULLS_FIRST)
463 *set_elem_result = -1; /* NULL "<" NOT_NULL */
464 else
465 *set_elem_result = 1; /* NULL ">" NOT_NULL */
466 return;
467 }
468
469 /*
470 * Array inequalities determine whether tupdatum is within the range of
471 * caller's skip array
472 */
473 *set_elem_result = 0;
474 if (ScanDirectionIsForward(dir))
475 {
476 /*
477 * Evaluate low_compare first (unless cur_elem_trig tells us that it
478 * cannot possibly fail to be satisfied), then evaluate high_compare
479 */
480 if (!cur_elem_trig && array->low_compare &&
481 !DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func,
482 array->low_compare->sk_collation,
483 tupdatum,
484 array->low_compare->sk_argument)))
485 *set_elem_result = -1;
486 else if (array->high_compare &&
487 !DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func,
488 array->high_compare->sk_collation,
489 tupdatum,
490 array->high_compare->sk_argument)))
491 *set_elem_result = 1;
492 }
493 else
494 {
495 /*
496 * Evaluate high_compare first (unless cur_elem_trig tells us that it
497 * cannot possibly fail to be satisfied), then evaluate low_compare
498 */
499 if (!cur_elem_trig && array->high_compare &&
500 !DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func,
501 array->high_compare->sk_collation,
502 tupdatum,
503 array->high_compare->sk_argument)))
504 *set_elem_result = 1;
505 else if (array->low_compare &&
506 !DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func,
507 array->low_compare->sk_collation,
508 tupdatum,
509 array->low_compare->sk_argument)))
510 *set_elem_result = -1;
511 }
512
513 /*
514 * Assert that any keys that were assumed to be satisfied already (due to
515 * caller passing cur_elem_trig=true) really are satisfied as expected
516 */
517 #ifdef USE_ASSERT_CHECKING
518 if (cur_elem_trig)
519 {
520 if (ScanDirectionIsForward(dir) && array->low_compare)
521 Assert(DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func,
522 array->low_compare->sk_collation,
523 tupdatum,
524 array->low_compare->sk_argument)));
525
526 if (ScanDirectionIsBackward(dir) && array->high_compare)
527 Assert(DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func,
528 array->high_compare->sk_collation,
529 tupdatum,
530 array->high_compare->sk_argument)));
531 }
532 #endif
533 }
534
535 /*
536 * _bt_skiparray_set_element() -- Set skip array scan key's sk_argument
537 *
538 * Caller passes set_elem_result returned by _bt_binsrch_skiparray_skey for
539 * caller's tupdatum/tupnull.
540 *
541 * We copy tupdatum/tupnull into skey's sk_argument iff set_elem_result == 0.
542 * Otherwise, we set skey to either the lowest or highest value that's within
543 * the range of caller's skip array (whichever is the best available match to
544 * tupdatum/tupnull that is still within the range of the skip array according
545 * to _bt_binsrch_skiparray_skey/set_elem_result).
546 */
547 static void
548 _bt_skiparray_set_element(Relation rel, ScanKey skey, BTArrayKeyInfo *array,
549 int32 set_elem_result, Datum tupdatum, bool tupnull)
550 {
551 Assert(skey->sk_flags & SK_BT_SKIP);
552 Assert(skey->sk_flags & SK_SEARCHARRAY);
553
554 if (set_elem_result)
555 {
556 /* tupdatum/tupnull is out of the range of the skip array */
557 Assert(!array->null_elem);
558
559 _bt_array_set_low_or_high(rel, skey, array, set_elem_result < 0);
560 return;
561 }
562
563 /* Advance skip array to tupdatum (or tupnull) value */
564 if (unlikely(tupnull))
565 {
566 _bt_skiparray_set_isnull(rel, skey, array);
567 return;
568 }
569
570 /* Free memory previously allocated for sk_argument if needed */
571 if (!array->attbyval && skey->sk_argument)
572 pfree(DatumGetPointer(skey->sk_argument));
573
574 /* tupdatum becomes new sk_argument/new current element */
575 skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL |
576 SK_BT_MINVAL | SK_BT_MAXVAL |
577 SK_BT_NEXT | SK_BT_PRIOR);
578 skey->sk_argument = datumCopy(tupdatum, array->attbyval, array->attlen);
579 }
580
581 /*
582 * _bt_skiparray_set_isnull() -- set skip array scan key to NULL
583 */
584 static void
585 _bt_skiparray_set_isnull(Relation rel, ScanKey skey, BTArrayKeyInfo *array)
586 {
587 Assert(skey->sk_flags & SK_BT_SKIP);
588 Assert(skey->sk_flags & SK_SEARCHARRAY);
589 Assert(array->null_elem && !array->low_compare && !array->high_compare);
590
591 /* Free memory previously allocated for sk_argument if needed */
592 if (!array->attbyval && skey->sk_argument)
593 pfree(DatumGetPointer(skey->sk_argument));
594
595 /* NULL becomes new sk_argument/new current element */
596 skey->sk_argument = (Datum) 0;
597 skey->sk_flags &= ~(SK_BT_MINVAL | SK_BT_MAXVAL |
598 SK_BT_NEXT | SK_BT_PRIOR);
599 skey->sk_flags |= (SK_SEARCHNULL | SK_ISNULL);
600 }
601
602 /*
603 * _bt_start_array_keys() -- Initialize array keys at start of a scan
604 *
605 * Set up the cur_elem counters and fill in the first sk_argument value for
606 * each array scankey.
607 */
608 void
609 _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir)
610 {
611 Relation rel = scan->indexRelation;
612 BTScanOpaque so = (BTScanOpaque) scan->opaque;
613
614 Assert(so->numArrayKeys);
615 Assert(so->qual_ok);
616
617 for (int i = 0; i < so->numArrayKeys; i++)
618 {
619 BTArrayKeyInfo *array = &so->arrayKeys[i];
620 ScanKey skey = &so->keyData[array->scan_key];
621
622 Assert(skey->sk_flags & SK_SEARCHARRAY);
623
624 _bt_array_set_low_or_high(rel, skey, array,
625 ScanDirectionIsForward(dir));
626 }
627 so->scanBehind = so->oppositeDirCheck = false; /* reset */
628 }
629
630 /*
631 * _bt_array_set_low_or_high() -- Set array scan key to lowest/highest element
632 *
633 * Caller also passes associated scan key, which will have its argument set to
634 * the lowest/highest array value in passing.
635 */
636 static void
637 _bt_array_set_low_or_high(Relation rel, ScanKey skey, BTArrayKeyInfo *array,
638 bool low_not_high)
639 {
640 Assert(skey->sk_flags & SK_SEARCHARRAY);
641
642 if (array->num_elems != -1)
643 {
644 /* set low or high element for SAOP array */
645 int set_elem = 0;
646
647 Assert(!(skey->sk_flags & SK_BT_SKIP));
648
649 if (!low_not_high)
650 set_elem = array->num_elems - 1;
651
652 /*
653 * Just copy over array datum (only skip arrays require freeing and
654 * allocating memory for sk_argument)
655 */
656 array->cur_elem = set_elem;
657 skey->sk_argument = array->elem_values[set_elem];
658
659 return;
660 }
661
662 /* set low or high element for skip array */
663 Assert(skey->sk_flags & SK_BT_SKIP);
664 Assert(array->num_elems == -1);
665
666 /* Free memory previously allocated for sk_argument if needed */
667 if (!array->attbyval && skey->sk_argument)
668 pfree(DatumGetPointer(skey->sk_argument));
669
670 /* Reset flags */
671 skey->sk_argument = (Datum) 0;
672 skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL |
673 SK_BT_MINVAL | SK_BT_MAXVAL |
674 SK_BT_NEXT | SK_BT_PRIOR);
675
676 if (array->null_elem &&
677 (low_not_high == ((skey->sk_flags & SK_BT_NULLS_FIRST) != 0)))
678 {
679 /* Requested element (either lowest or highest) has the value NULL */
680 skey->sk_flags |= (SK_SEARCHNULL | SK_ISNULL);
681 }
682 else if (low_not_high)
683 {
684 /* Setting array to lowest element (according to low_compare) */
685 skey->sk_flags |= SK_BT_MINVAL;
686 }
687 else
688 {
689 /* Setting array to highest element (according to high_compare) */
690 skey->sk_flags |= SK_BT_MAXVAL;
691 }
692 }
693
694 /*
695 * _bt_array_decrement() -- decrement array scan key's sk_argument
696 *
697 * Return value indicates whether caller's array was successfully decremented.
698 * Cannot decrement an array whose current element is already the first one.
699 */
700 static bool
701 _bt_array_decrement(Relation rel, ScanKey skey, BTArrayKeyInfo *array)
702 {
703 bool uflow = false;
704 Datum dec_sk_argument;
705
706 Assert(skey->sk_flags & SK_SEARCHARRAY);
707 Assert(!(skey->sk_flags & (SK_BT_MAXVAL | SK_BT_NEXT | SK_BT_PRIOR)));
708
709 /* SAOP array? */
710 if (array->num_elems != -1)
711 {
712 Assert(!(skey->sk_flags & (SK_BT_SKIP | SK_BT_MINVAL | SK_BT_MAXVAL)));
713 if (array->cur_elem > 0)
714 {
715 /*
716 * Just decrement current element, and assign its datum to skey
717 * (only skip arrays need us to free existing sk_argument memory)
718 */
719 array->cur_elem--;
720 skey->sk_argument = array->elem_values[array->cur_elem];
721
722 /* Successfully decremented array */
723 return true;
724 }
725
726 /* Cannot decrement to before first array element */
727 return false;
728 }
729
730 /* Nope, this is a skip array */
731 Assert(skey->sk_flags & SK_BT_SKIP);
732
733 /*
734 * The sentinel value that represents the minimum value within the range
735 * of a skip array (often just -inf) is never decrementable
736 */
737 if (skey->sk_flags & SK_BT_MINVAL)
738 return false;
739
740 /*
741 * When the current array element is NULL, and the lowest sorting value in
742 * the index is also NULL, we cannot decrement before first array element
743 */
744 if ((skey->sk_flags & SK_ISNULL) && (skey->sk_flags & SK_BT_NULLS_FIRST))
745 return false;
746
747 /*
748 * Opclasses without skip support "decrement" the scan key's current
749 * element by setting the PRIOR flag. The true prior value is determined
750 * by repositioning to the last index tuple < existing sk_argument/current
751 * array element. Note that this works in the usual way when the scan key
752 * is already marked ISNULL (i.e. when the current element is NULL).
753 */
754 if (!array->sksup)
755 {
756 /* Successfully "decremented" array */
757 skey->sk_flags |= SK_BT_PRIOR;
758 return true;
759 }
760
761 /*
762 * Opclasses with skip support directly decrement sk_argument
763 */
764 if (skey->sk_flags & SK_ISNULL)
765 {
766 Assert(!(skey->sk_flags & SK_BT_NULLS_FIRST));
767
768 /*
769 * Existing sk_argument/array element is NULL (for an IS NULL qual).
770 *
771 * "Decrement" from NULL to the high_elem value provided by opclass
772 * skip support routine.
773 */
774 skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL);
775 skey->sk_argument = datumCopy(array->sksup->high_elem,
776 array->attbyval, array->attlen);
777 return true;
778 }
779
780 /*
781 * Ask opclass support routine to provide decremented copy of existing
782 * non-NULL sk_argument
783 */
784 dec_sk_argument = array->sksup->decrement(rel, skey->sk_argument, &uflow);
785 if (unlikely(uflow))
786 {
787 /* dec_sk_argument has undefined value (so no pfree) */
788 if (array->null_elem && (skey->sk_flags & SK_BT_NULLS_FIRST))
789 {
790 _bt_skiparray_set_isnull(rel, skey, array);
791
792 /* Successfully "decremented" array to NULL */
793 return true;
794 }
795
796 /* Cannot decrement to before first array element */
797 return false;
798 }
799
800 /*
801 * Successfully decremented sk_argument to a non-NULL value. Make sure
802 * that the decremented value is still within the range of the array.
803 */
804 if (array->low_compare &&
805 !DatumGetBool(FunctionCall2Coll(&array->low_compare->sk_func,
806 array->low_compare->sk_collation,
807 dec_sk_argument,
808 array->low_compare->sk_argument)))
809 {
810 /* Keep existing sk_argument after all */
811 if (!array->attbyval)
812 pfree(DatumGetPointer(dec_sk_argument));
813
814 /* Cannot decrement to before first array element */
815 return false;
816 }
817
818 /* Accept value returned by opclass decrement callback */
819 if (!array->attbyval && skey->sk_argument)
820 pfree(DatumGetPointer(skey->sk_argument));
821 skey->sk_argument = dec_sk_argument;
822
823 /* Successfully decremented array */
824 return true;
825 }
826
827 /*
828 * _bt_array_increment() -- increment array scan key's sk_argument
829 *
830 * Return value indicates whether caller's array was successfully incremented.
831 * Cannot increment an array whose current element is already the final one.
832 */
833 static bool
834 _bt_array_increment(Relation rel, ScanKey skey, BTArrayKeyInfo *array)
835 {
836 bool oflow = false;
837 Datum inc_sk_argument;
838
839 Assert(skey->sk_flags & SK_SEARCHARRAY);
840 Assert(!(skey->sk_flags & (SK_BT_MINVAL | SK_BT_NEXT | SK_BT_PRIOR)));
841
842 /* SAOP array? */
843 if (array->num_elems != -1)
844 {
845 Assert(!(skey->sk_flags & (SK_BT_SKIP | SK_BT_MINVAL | SK_BT_MAXVAL)));
846 if (array->cur_elem < array->num_elems - 1)
847 {
848 /*
849 * Just increment current element, and assign its datum to skey
850 * (only skip arrays need us to free existing sk_argument memory)
851 */
852 array->cur_elem++;
853 skey->sk_argument = array->elem_values[array->cur_elem];
854
855 /* Successfully incremented array */
856 return true;
857 }
858
859 /* Cannot increment past final array element */
860 return false;
861 }
862
863 /* Nope, this is a skip array */
864 Assert(skey->sk_flags & SK_BT_SKIP);
865
866 /*
867 * The sentinel value that represents the maximum value within the range
868 * of a skip array (often just +inf) is never incrementable
869 */
870 if (skey->sk_flags & SK_BT_MAXVAL)
871 return false;
872
873 /*
874 * When the current array element is NULL, and the highest sorting value
875 * in the index is also NULL, we cannot increment past the final element
876 */
877 if ((skey->sk_flags & SK_ISNULL) && !(skey->sk_flags & SK_BT_NULLS_FIRST))
878 return false;
879
880 /*
881 * Opclasses without skip support "increment" the scan key's current
882 * element by setting the NEXT flag. The true next value is determined by
883 * repositioning to the first index tuple > existing sk_argument/current
884 * array element. Note that this works in the usual way when the scan key
885 * is already marked ISNULL (i.e. when the current element is NULL).
886 */
887 if (!array->sksup)
888 {
889 /* Successfully "incremented" array */
890 skey->sk_flags |= SK_BT_NEXT;
891 return true;
892 }
893
894 /*
895 * Opclasses with skip support directly increment sk_argument
896 */
897 if (skey->sk_flags & SK_ISNULL)
898 {
899 Assert(skey->sk_flags & SK_BT_NULLS_FIRST);
900
901 /*
902 * Existing sk_argument/array element is NULL (for an IS NULL qual).
903 *
904 * "Increment" from NULL to the low_elem value provided by opclass
905 * skip support routine.
906 */
907 skey->sk_flags &= ~(SK_SEARCHNULL | SK_ISNULL);
908 skey->sk_argument = datumCopy(array->sksup->low_elem,
909 array->attbyval, array->attlen);
910 return true;
911 }
912
913 /*
914 * Ask opclass support routine to provide incremented copy of existing
915 * non-NULL sk_argument
916 */
917 inc_sk_argument = array->sksup->increment(rel, skey->sk_argument, &oflow);
918 if (unlikely(oflow))
919 {
920 /* inc_sk_argument has undefined value (so no pfree) */
921 if (array->null_elem && !(skey->sk_flags & SK_BT_NULLS_FIRST))
922 {
923 _bt_skiparray_set_isnull(rel, skey, array);
924
925 /* Successfully "incremented" array to NULL */
926 return true;
927 }
928
929 /* Cannot increment past final array element */
930 return false;
931 }
932
933 /*
934 * Successfully incremented sk_argument to a non-NULL value. Make sure
935 * that the incremented value is still within the range of the array.
936 */
937 if (array->high_compare &&
938 !DatumGetBool(FunctionCall2Coll(&array->high_compare->sk_func,
939 array->high_compare->sk_collation,
940 inc_sk_argument,
941 array->high_compare->sk_argument)))
942 {
943 /* Keep existing sk_argument after all */
944 if (!array->attbyval)
945 pfree(DatumGetPointer(inc_sk_argument));
946
947 /* Cannot increment past final array element */
948 return false;
949 }
950
951 /* Accept value returned by opclass increment callback */
952 if (!array->attbyval && skey->sk_argument)
953 pfree(DatumGetPointer(skey->sk_argument));
954 skey->sk_argument = inc_sk_argument;
955
956 /* Successfully incremented array */
957 return true;
958 }
959
960 /*
961 * _bt_advance_array_keys_increment() -- Advance to next set of array elements
962 *
963 * Advances the array keys by a single increment in the current scan
964 * direction. When there are multiple array keys this can roll over from the
965 * lowest order array to higher order arrays.
966 *
967 * Returns true if there is another set of values to consider, false if not.
968 * On true result, the scankeys are initialized with the next set of values.
969 * On false result, the scankeys stay the same, and the array keys are not
970 * advanced (every array remains at its final element for scan direction).
971 */
972 static bool
973 _bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir,
974 bool *skip_array_set)
975 {
976 Relation rel = scan->indexRelation;
977 BTScanOpaque so = (BTScanOpaque) scan->opaque;
978
979 /*
980 * We must advance the last array key most quickly, since it will
981 * correspond to the lowest-order index column among the available
982 * qualifications
983 */
984 for (int i = so->numArrayKeys - 1; i >= 0; i--)
985 {
986 BTArrayKeyInfo *array = &so->arrayKeys[i];
987 ScanKey skey = &so->keyData[array->scan_key];
988
989 if (array->num_elems == -1)
990 *skip_array_set = true;
991
992 if (ScanDirectionIsForward(dir))
993 {
994 if (_bt_array_increment(rel, skey, array))
995 return true;
996 }
997 else
998 {
999 if (_bt_array_decrement(rel, skey, array))
1000 return true;
1001 }
1002
1003 /*
1004 * Couldn't increment (or decrement) array. Handle array roll over.
1005 *
1006 * Start over at the array's lowest sorting value (or its highest
1007 * value, for backward scans)...
1008 */
1009 _bt_array_set_low_or_high(rel, skey, array,
1010 ScanDirectionIsForward(dir));
1011
1012 /* ...then increment (or decrement) next most significant array */
1013 }
1014
1015 /*
1016 * The array keys are now exhausted.
1017 *
1018 * Restore the array keys to the state they were in immediately before we
1019 * were called. This ensures that the arrays only ever ratchet in the
1020 * current scan direction.
1021 *
1022 * Without this, scans could overlook matching tuples when the scan
1023 * direction gets reversed just before btgettuple runs out of items to
1024 * return, but just after _bt_readpage prepares all the items from the
1025 * scan's final page in so->currPos. When we're on the final page it is
1026 * typical for so->currPos to get invalidated once btgettuple finally
1027 * returns false, which'll effectively invalidate the scan's array keys.
1028 * That hasn't happened yet, though -- and in general it may never happen.
1029 */
1030 _bt_start_array_keys(scan, -dir);
1031
1032 return false;
1033 }
1034
1035 /*
1036 * _bt_tuple_before_array_skeys() -- too early to advance required arrays?
1037 *
1038 * We always compare the tuple using the current array keys (which we assume
1039 * are already set in so->keyData[]). readpagetup indicates if tuple is the
1040 * scan's current _bt_readpage-wise tuple.
1041 *
1042 * readpagetup callers must only call here when _bt_check_compare already set
1043 * continuescan=false. We help these callers deal with _bt_check_compare's
1044 * inability to distinguish between the < and > cases (it uses equality
1045 * operator scan keys, whereas we use 3-way ORDER procs). These callers pass
1046 * a _bt_check_compare-set sktrig value that indicates which scan key
1047 * triggered the call (!readpagetup callers just pass us sktrig=0 instead).
1048 * This information allows us to avoid wastefully checking earlier scan keys
1049 * that were already deemed to have been satisfied inside _bt_check_compare.
1050 *
1051 * Returns false when caller's tuple is >= the current required equality scan
1052 * keys (or <=, in the case of backwards scans). This happens to readpagetup
1053 * callers when the scan has reached the point of needing its array keys
1054 * advanced; caller will need to advance required and non-required arrays at
1055 * scan key offsets >= sktrig, plus scan keys < sktrig iff sktrig rolls over.
1056 * (When we return false to readpagetup callers, tuple can only be == current
1057 * required equality scan keys when caller's sktrig indicates that the arrays
1058 * need to be advanced due to an unsatisfied required inequality key trigger.)
1059 *
1060 * Returns true when caller passes a tuple that is < the current set of
1061 * equality keys for the most significant non-equal required scan key/column
1062 * (or > the keys, during backwards scans). This happens to readpagetup
1063 * callers when tuple is still before the start of matches for the scan's
1064 * required equality strategy scan keys. (sktrig can't have indicated that an
1065 * inequality strategy scan key wasn't satisfied in _bt_check_compare when we
1066 * return true. In fact, we automatically return false when passed such an
1067 * inequality sktrig by readpagetup callers -- _bt_check_compare's initial
1068 * continuescan=false doesn't really need to be confirmed here by us.)
1069 *
1070 * !readpagetup callers optionally pass us *scanBehind, which tracks whether
1071 * any missing truncated attributes might have affected array advancement
1072 * (compared to what would happen if it was shown the first non-pivot tuple on
1073 * the page to the right of caller's finaltup/high key tuple instead). It's
1074 * only possible that we'll set *scanBehind to true when caller passes us a
1075 * pivot tuple (with truncated -inf attributes) that we return false for.
1076 */
1077 static bool
1078 _bt_tuple_before_array_skeys(IndexScanDesc scan, ScanDirection dir,
1079 IndexTuple tuple, TupleDesc tupdesc, int tupnatts,
1080 bool readpagetup, int sktrig, bool *scanBehind)
1081 {
1082 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1083
1084 Assert(so->numArrayKeys);
1085 Assert(so->numberOfKeys);
1086 Assert(sktrig == 0 || readpagetup);
1087 Assert(!readpagetup || scanBehind == NULL);
1088
1089 if (scanBehind)
1090 *scanBehind = false;
1091
1092 for (int ikey = sktrig; ikey < so->numberOfKeys; ikey++)
1093 {
1094 ScanKey cur = so->keyData + ikey;
1095 Datum tupdatum;
1096 bool tupnull;
1097 int32 result;
1098
1099 /* readpagetup calls require one ORDER proc comparison (at most) */
1100 Assert(!readpagetup || ikey == sktrig);
1101
1102 /*
1103 * Once we reach a non-required scan key, we're completely done.
1104 *
1105 * Note: we deliberately don't consider the scan direction here.
1106 * _bt_advance_array_keys caller requires that we track *scanBehind
1107 * without concern for scan direction.
1108 */
1109 if ((cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) == 0)
1110 {
1111 Assert(!readpagetup);
1112 Assert(ikey > sktrig || ikey == 0);
1113 return false;
1114 }
1115
1116 if (cur->sk_attno > tupnatts)
1117 {
1118 Assert(!readpagetup);
1119
1120 /*
1121 * When we reach a high key's truncated attribute, assume that the
1122 * tuple attribute's value is >= the scan's equality constraint
1123 * scan keys (but set *scanBehind to let interested callers know
1124 * that a truncated attribute might have affected our answer).
1125 */
1126 if (scanBehind)
1127 *scanBehind = true;
1128
1129 return false;
1130 }
1131
1132 /*
1133 * Deal with inequality strategy scan keys that _bt_check_compare set
1134 * continuescan=false for
1135 */
1136 if (cur->sk_strategy != BTEqualStrategyNumber)
1137 {
1138 /*
1139 * When _bt_check_compare indicated that a required inequality
1140 * scan key wasn't satisfied, there's no need to verify anything;
1141 * caller always calls _bt_advance_array_keys with this sktrig.
1142 */
1143 if (readpagetup)
1144 return false;
1145
1146 /*
1147 * Otherwise we can't give up, since we must check all required
1148 * scan keys (required in either direction) in order to correctly
1149 * track *scanBehind for caller
1150 */
1151 continue;
1152 }
1153
1154 tupdatum = index_getattr(tuple, cur->sk_attno, tupdesc, &tupnull);
1155
1156 if (likely(!(cur->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))))
1157 {
1158 /* Scankey has a valid/comparable sk_argument value */
1159 result = _bt_compare_array_skey(&so->orderProcs[ikey],
1160 tupdatum, tupnull,
1161 cur->sk_argument, cur);
1162
1163 if (result == 0)
1164 {
1165 /*
1166 * Interpret result in a way that takes NEXT/PRIOR into
1167 * account
1168 */
1169 if (cur->sk_flags & SK_BT_NEXT)
1170 result = -1;
1171 else if (cur->sk_flags & SK_BT_PRIOR)
1172 result = 1;
1173
1174 Assert(result == 0 || (cur->sk_flags & SK_BT_SKIP));
1175 }
1176 }
1177 else
1178 {
1179 BTArrayKeyInfo *array = NULL;
1180
1181 /*
1182 * Current array element/array = scan key value is a sentinel
1183 * value that represents the lowest (or highest) possible value
1184 * that's still within the range of the array.
1185 *
1186 * Like _bt_first, we only see MINVAL keys during forwards scans
1187 * (and similarly only see MAXVAL keys during backwards scans).
1188 * Even if the scan's direction changes, we'll stop at some higher
1189 * order key before we can ever reach any MAXVAL (or MINVAL) keys.
1190 * (However, unlike _bt_first we _can_ get to keys marked either
1191 * NEXT or PRIOR, regardless of the scan's current direction.)
1192 */
1193 Assert(ScanDirectionIsForward(dir) ?
1194 !(cur->sk_flags & SK_BT_MAXVAL) :
1195 !(cur->sk_flags & SK_BT_MINVAL));
1196
1197 /*
1198 * There are no valid sk_argument values in MINVAL/MAXVAL keys.
1199 * Check if tupdatum is within the range of skip array instead.
1200 */
1201 for (int arrayidx = 0; arrayidx < so->numArrayKeys; arrayidx++)
1202 {
1203 array = &so->arrayKeys[arrayidx];
1204 if (array->scan_key == ikey)
1205 break;
1206 }
1207
1208 _bt_binsrch_skiparray_skey(false, dir, tupdatum, tupnull,
1209 array, cur, &result);
1210
1211 if (result == 0)
1212 {
1213 /*
1214 * tupdatum satisfies both low_compare and high_compare, so
1215 * it's time to advance the array keys.
1216 *
1217 * Note: It's possible that the skip array will "advance" from
1218 * its MINVAL (or MAXVAL) representation to an alternative,
1219 * logically equivalent representation of the same value: a
1220 * representation where the = key gets a valid datum in its
1221 * sk_argument. This is only possible when low_compare uses
1222 * the >= strategy (or high_compare uses the <= strategy).
1223 */
1224 return false;
1225 }
1226 }
1227
1228 /*
1229 * Does this comparison indicate that caller must _not_ advance the
1230 * scan's arrays just yet?
1231 */
1232 if ((ScanDirectionIsForward(dir) && result < 0) ||
1233 (ScanDirectionIsBackward(dir) && result > 0))
1234 return true;
1235
1236 /*
1237 * Does this comparison indicate that caller should now advance the
1238 * scan's arrays? (Must be if we get here during a readpagetup call.)
1239 */
1240 if (readpagetup || result != 0)
1241 {
1242 Assert(result != 0);
1243 return false;
1244 }
1245
1246 /*
1247 * Inconclusive -- need to check later scan keys, too.
1248 *
1249 * This must be a finaltup precheck, or a call made from an assertion.
1250 */
1251 Assert(result == 0);
1252 }
1253
1254 Assert(!readpagetup);
1255
1256 return false;
1257 }
1258
1259 /*
1260 * _bt_start_prim_scan() -- start scheduled primitive index scan?
1261 *
1262 * Returns true if _bt_checkkeys scheduled another primitive index scan, just
1263 * as the last one ended. Otherwise returns false, indicating that the array
1264 * keys are now fully exhausted.
1265 *
1266 * Only call here during scans with one or more equality type array scan keys,
1267 * after _bt_first or _bt_next return false.
1268 */
1269 bool
1270 _bt_start_prim_scan(IndexScanDesc scan, ScanDirection dir)
1271 {
1272 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1273
1274 Assert(so->numArrayKeys);
1275
1276 so->scanBehind = so->oppositeDirCheck = false; /* reset */
1277
1278 /*
1279 * Array keys are advanced within _bt_checkkeys when the scan reaches the
1280 * leaf level (more precisely, they're advanced when the scan reaches the
1281 * end of each distinct set of array elements). This process avoids
1282 * repeat access to leaf pages (across multiple primitive index scans) by
1283 * advancing the scan's array keys when it allows the primitive index scan
1284 * to find nearby matching tuples (or when it eliminates ranges of array
1285 * key space that can't possibly be satisfied by any index tuple).
1286 *
1287 * _bt_checkkeys sets a simple flag variable to schedule another primitive
1288 * index scan. The flag tells us what to do.
1289 *
1290 * We cannot rely on _bt_first always reaching _bt_checkkeys. There are
1291 * various cases where that won't happen. For example, if the index is
1292 * completely empty, then _bt_first won't call _bt_readpage/_bt_checkkeys.
1293 * We also don't expect a call to _bt_checkkeys during searches for a
1294 * non-existent value that happens to be lower/higher than any existing
1295 * value in the index.
1296 *
1297 * We don't require special handling for these cases -- we don't need to
1298 * be explicitly instructed to _not_ perform another primitive index scan.
1299 * It's up to code under the control of _bt_first to always set the flag
1300 * when another primitive index scan will be required.
1301 *
1302 * This works correctly, even with the tricky cases listed above, which
1303 * all involve access to leaf pages "near the boundaries of the key space"
1304 * (whether it's from a leftmost/rightmost page, or an imaginary empty
1305 * leaf root page). If _bt_checkkeys cannot be reached by a primitive
1306 * index scan for one set of array keys, then it also won't be reached for
1307 * any later set ("later" in terms of the direction that we scan the index
1308 * and advance the arrays). The array keys won't have advanced in these
1309 * cases, but that's the correct behavior (even _bt_advance_array_keys
1310 * won't always advance the arrays at the point they become "exhausted").
1311 */
1312 if (so->needPrimScan)
1313 {
1314 /*
1315 * Flag was set -- must call _bt_first again, which will reset the
1316 * scan's needPrimScan flag
1317 */
1318 return true;
1319 }
1320
1321 /* The top-level index scan ran out of tuples in this scan direction */
1322 if (scan->parallel_scan != NULL)
1323 _bt_parallel_done(scan);
1324
1325 return false;
1326 }
1327
1328 /*
1329 * _bt_advance_array_keys() -- Advance array elements using a tuple
1330 *
1331 * The scan always gets a new qual as a consequence of calling here (except
1332 * when we determine that the top-level scan has run out of matching tuples).
1333 * All later _bt_check_compare calls also use the same new qual that was first
1334 * used here (at least until the next call here advances the keys once again).
1335 * It's convenient to structure _bt_check_compare rechecks of caller's tuple
1336 * (using the new qual) as one the steps of advancing the scan's array keys,
1337 * so this function works as a wrapper around _bt_check_compare.
1338 *
1339 * Like _bt_check_compare, we'll set pstate.continuescan on behalf of the
1340 * caller, and return a boolean indicating if caller's tuple satisfies the
1341 * scan's new qual. But unlike _bt_check_compare, we set so->needPrimScan
1342 * when we set continuescan=false, indicating if a new primitive index scan
1343 * has been scheduled (otherwise, the top-level scan has run out of tuples in
1344 * the current scan direction).
1345 *
1346 * Caller must use _bt_tuple_before_array_skeys to determine if the current
1347 * place in the scan is >= the current array keys _before_ calling here.
1348 * We're responsible for ensuring that caller's tuple is <= the newly advanced
1349 * required array keys once we return. We try to find an exact match, but
1350 * failing that we'll advance the array keys to whatever set of array elements
1351 * comes next in the key space for the current scan direction. Required array
1352 * keys "ratchet forwards" (or backwards). They can only advance as the scan
1353 * itself advances through the index/key space.
1354 *
1355 * (The rules are the same for backwards scans, except that the operators are
1356 * flipped: just replace the precondition's >= operator with a <=, and the
1357 * postcondition's <= operator with a >=. In other words, just swap the
1358 * precondition with the postcondition.)
1359 *
1360 * We also deal with "advancing" non-required arrays here (or arrays that are
1361 * treated as non-required for the duration of a _bt_readpage call). Callers
1362 * whose sktrig scan key is non-required specify sktrig_required=false. These
1363 * calls are the only exception to the general rule about always advancing the
1364 * required array keys (the scan may not even have a required array). These
1365 * callers should just pass a NULL pstate (since there is never any question
1366 * of stopping the scan). No call to _bt_tuple_before_array_skeys is required
1367 * ahead of these calls (it's already clear that any required scan keys must
1368 * be satisfied by caller's tuple).
1369 *
1370 * Note that we deal with non-array required equality strategy scan keys as
1371 * degenerate single element arrays here. Obviously, they can never really
1372 * advance in the way that real arrays can, but they must still affect how we
1373 * advance real array scan keys (exactly like true array equality scan keys).
1374 * We have to keep around a 3-way ORDER proc for these (using the "=" operator
1375 * won't do), since in general whether the tuple is < or > _any_ unsatisfied
1376 * required equality key influences how the scan's real arrays must advance.
1377 *
1378 * Note also that we may sometimes need to advance the array keys when the
1379 * existing required array keys (and other required equality keys) are already
1380 * an exact match for every corresponding value from caller's tuple. We must
1381 * do this for inequalities that _bt_check_compare set continuescan=false for.
1382 * They'll advance the array keys here, just like any other scan key that
1383 * _bt_check_compare stops on. (This can even happen _after_ we advance the
1384 * array keys, in which case we'll advance the array keys a second time. That
1385 * way _bt_checkkeys caller always has its required arrays advance to the
1386 * maximum possible extent that its tuple will allow.)
1387 */
1388 static bool
1389 _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
1390 IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
1391 int sktrig, bool sktrig_required)
1392 {
1393 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1394 Relation rel = scan->indexRelation;
1395 ScanDirection dir = so->currPos.dir;
1396 int arrayidx = 0;
1397 bool beyond_end_advance = false,
1398 skip_array_advanced = false,
1399 has_required_opposite_direction_only = false,
1400 all_required_satisfied = true,
1401 all_satisfied = true;
1402
1403 Assert(!so->needPrimScan && !so->scanBehind && !so->oppositeDirCheck);
1404 Assert(_bt_verify_keys_with_arraykeys(scan));
1405
1406 if (sktrig_required)
1407 {
1408 /*
1409 * Precondition array state assertion
1410 */
1411 Assert(!_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc,
1412 tupnatts, false, 0, NULL));
1413
1414 /*
1415 * Once we return we'll have a new set of required array keys, so
1416 * reset state used by "look ahead" optimization
1417 */
1418 pstate->rechecks = 0;
1419 pstate->targetdistance = 0;
1420 }
1421 else if (sktrig < so->numberOfKeys - 1 &&
1422 !(so->keyData[so->numberOfKeys - 1].sk_flags & SK_SEARCHARRAY))
1423 {
1424 int least_sign_ikey = so->numberOfKeys - 1;
1425 bool continuescan;
1426
1427 /*
1428 * Optimization: perform a precheck of the least significant key
1429 * during !sktrig_required calls when it isn't already our sktrig
1430 * (provided the precheck key is not itself an array).
1431 *
1432 * When the precheck works out we'll avoid an expensive binary search
1433 * of sktrig's array (plus any other arrays before least_sign_ikey).
1434 */
1435 Assert(so->keyData[sktrig].sk_flags & SK_SEARCHARRAY);
1436 if (!_bt_check_compare(scan, dir, tuple, tupnatts, tupdesc, false,
1437 false, &continuescan,
1438 &least_sign_ikey))
1439 return false;
1440 }
1441
1442 for (int ikey = 0; ikey < so->numberOfKeys; ikey++)
1443 {
1444 ScanKey cur = so->keyData + ikey;
1445 BTArrayKeyInfo *array = NULL;
1446 Datum tupdatum;
1447 bool required = false,
1448 tupnull;
1449 int32 result;
1450 int set_elem = 0;
1451
1452 if (cur->sk_strategy == BTEqualStrategyNumber)
1453 {
1454 /* Manage array state */
1455 if (cur->sk_flags & SK_SEARCHARRAY)
1456 {
1457 array = &so->arrayKeys[arrayidx++];
1458 Assert(array->scan_key == ikey);
1459 }
1460 }
1461 else
1462 {
1463 /*
1464 * Are any inequalities required in the opposite direction only
1465 * present here?
1466 */
1467 if (((ScanDirectionIsForward(dir) &&
1468 (cur->sk_flags & (SK_BT_REQBKWD))) ||
1469 (ScanDirectionIsBackward(dir) &&
1470 (cur->sk_flags & (SK_BT_REQFWD)))))
1471 has_required_opposite_direction_only = true;
1472 }
1473
1474 /* Optimization: skip over known-satisfied scan keys */
1475 if (ikey < sktrig)
1476 continue;
1477
1478 if (cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
1479 {
1480 required = true;
1481
1482 if (cur->sk_attno > tupnatts)
1483 {
1484 /* Set this just like _bt_tuple_before_array_skeys */
1485 Assert(sktrig < ikey);
1486 so->scanBehind = true;
1487 }
1488 }
1489
1490 /*
1491 * Handle a required non-array scan key that the initial call to
1492 * _bt_check_compare indicated triggered array advancement, if any.
1493 *
1494 * The non-array scan key's strategy will be <, <=, or = during a
1495 * forwards scan (or any one of =, >=, or > during a backwards scan).
1496 * It follows that the corresponding tuple attribute's value must now
1497 * be either > or >= the scan key value (for backwards scans it must
1498 * be either < or <= that value).
1499 *
1500 * If this is a required equality strategy scan key, this is just an
1501 * optimization; _bt_tuple_before_array_skeys already confirmed that
1502 * this scan key places us ahead of caller's tuple. There's no need
1503 * to repeat that work now. (The same underlying principle also gets
1504 * applied by the cur_elem_trig optimization used to speed up searches
1505 * for the next array element.)
1506 *
1507 * If this is a required inequality strategy scan key, we _must_ rely
1508 * on _bt_check_compare like this; we aren't capable of directly
1509 * evaluating required inequality strategy scan keys here, on our own.
1510 */
1511 if (ikey == sktrig && !array)
1512 {
1513 Assert(sktrig_required && required && all_required_satisfied);
1514
1515 /* Use "beyond end" advancement. See below for an explanation. */
1516 beyond_end_advance = true;
1517 all_satisfied = all_required_satisfied = false;
1518
1519 continue;
1520 }
1521
1522 /*
1523 * Nothing more for us to do with an inequality strategy scan key that
1524 * wasn't the one that _bt_check_compare stopped on, though.
1525 *
1526 * Note: if our later call to _bt_check_compare (to recheck caller's
1527 * tuple) sets continuescan=false due to finding this same inequality
1528 * unsatisfied (possible when it's required in the scan direction),
1529 * we'll deal with it via a recursive "second pass" call.
1530 */
1531 else if (cur->sk_strategy != BTEqualStrategyNumber)
1532 continue;
1533
1534 /*
1535 * Nothing for us to do with an equality strategy scan key that isn't
1536 * marked required, either -- unless it's a non-required array
1537 */
1538 else if (!required && !array)
1539 continue;
1540
1541 /*
1542 * Here we perform steps for all array scan keys after a required
1543 * array scan key whose binary search triggered "beyond end of array
1544 * element" array advancement due to encountering a tuple attribute
1545 * value > the closest matching array key (or < for backwards scans).
1546 */
1547 if (beyond_end_advance)
1548 {
1549 if (array)
1550 _bt_array_set_low_or_high(rel, cur, array,
1551 ScanDirectionIsBackward(dir));
1552
1553 continue;
1554 }
1555
1556 /*
1557 * Here we perform steps for all array scan keys after a required
1558 * array scan key whose tuple attribute was < the closest matching
1559 * array key when we dealt with it (or > for backwards scans).
1560 *
1561 * This earlier required array key already puts us ahead of caller's
1562 * tuple in the key space (for the current scan direction). We must
1563 * make sure that subsequent lower-order array keys do not put us too
1564 * far ahead (ahead of tuples that have yet to be seen by our caller).
1565 * For example, when a tuple "(a, b) = (42, 5)" advances the array
1566 * keys on "a" from 40 to 45, we must also set "b" to whatever the
1567 * first array element for "b" is. It would be wrong to allow "b" to
1568 * be set based on the tuple value.
1569 *
1570 * Perform the same steps with truncated high key attributes. You can
1571 * think of this as a "binary search" for the element closest to the
1572 * value -inf. Again, the arrays must never get ahead of the scan.
1573 */
1574 if (!all_required_satisfied || cur->sk_attno > tupnatts)
1575 {
1576 if (array)
1577 _bt_array_set_low_or_high(rel, cur, array,
1578 ScanDirectionIsForward(dir));
1579
1580 continue;
1581 }
1582
1583 /*
1584 * Search in scankey's array for the corresponding tuple attribute
1585 * value from caller's tuple
1586 */
1587 tupdatum = index_getattr(tuple, cur->sk_attno, tupdesc, &tupnull);
1588
1589 if (array)
1590 {
1591 bool cur_elem_trig = (sktrig_required && ikey == sktrig);
1592
1593 /*
1594 * "Binary search" by checking if tupdatum/tupnull are within the
1595 * range of the skip array
1596 */
1597 if (array->num_elems == -1)
1598 _bt_binsrch_skiparray_skey(cur_elem_trig, dir,
1599 tupdatum, tupnull, array, cur,
1600 &result);
1601
1602 /*
1603 * Binary search for the closest match from the SAOP array
1604 */
1605 else
1606 set_elem = _bt_binsrch_array_skey(&so->orderProcs[ikey],
1607 cur_elem_trig, dir,
1608 tupdatum, tupnull, array, cur,
1609 &result);
1610 }
1611 else
1612 {
1613 Assert(required);
1614
1615 /*
1616 * This is a required non-array equality strategy scan key, which
1617 * we'll treat as a degenerate single element array.
1618 *
1619 * This scan key's imaginary "array" can't really advance, but it
1620 * can still roll over like any other array. (Actually, this is
1621 * no different to real single value arrays, which never advance
1622 * without rolling over -- they can never truly advance, either.)
1623 */
1624 result = _bt_compare_array_skey(&so->orderProcs[ikey],
1625 tupdatum, tupnull,
1626 cur->sk_argument, cur);
1627 }
1628
1629 /*
1630 * Consider "beyond end of array element" array advancement.
1631 *
1632 * When the tuple attribute value is > the closest matching array key
1633 * (or < in the backwards scan case), we need to ratchet this array
1634 * forward (backward) by one increment, so that caller's tuple ends up
1635 * being < final array value instead (or > final array value instead).
1636 * This process has to work for all of the arrays, not just this one:
1637 * it must "carry" to higher-order arrays when the set_elem that we
1638 * just found happens to be the final one for the scan's direction.
1639 * Incrementing (decrementing) set_elem itself isn't good enough.
1640 *
1641 * Our approach is to provisionally use set_elem as if it was an exact
1642 * match now, then set each later/less significant array to whatever
1643 * its final element is. Once outside the loop we'll then "increment
1644 * this array's set_elem" by calling _bt_advance_array_keys_increment.
1645 * That way the process rolls over to higher order arrays as needed.
1646 *
1647 * Under this scheme any required arrays only ever ratchet forwards
1648 * (or backwards), and always do so to the maximum possible extent
1649 * that we can know will be safe without seeing the scan's next tuple.
1650 * We don't need any special handling for required scan keys that lack
1651 * a real array to advance, nor for redundant scan keys that couldn't
1652 * be eliminated by _bt_preprocess_keys. It won't matter if some of
1653 * our "true" array scan keys (or even all of them) are non-required.
1654 */
1655 if (sktrig_required && required &&
1656 ((ScanDirectionIsForward(dir) && result > 0) ||
1657 (ScanDirectionIsBackward(dir) && result < 0)))
1658 beyond_end_advance = true;
1659
1660 Assert(all_required_satisfied && all_satisfied);
1661 if (result != 0)
1662 {
1663 /*
1664 * Track whether caller's tuple satisfies our new post-advancement
1665 * qual, for required scan keys, as well as for the entire set of
1666 * interesting scan keys (all required scan keys plus non-required
1667 * array scan keys are considered interesting.)
1668 */
1669 all_satisfied = false;
1670 if (sktrig_required && required)
1671 all_required_satisfied = false;
1672 else
1673 {
1674 /*
1675 * There's no need to advance the arrays using the best
1676 * available match for a non-required array. Give up now.
1677 * (Though note that sktrig_required calls still have to do
1678 * all the usual post-advancement steps, including the recheck
1679 * call to _bt_check_compare.)
1680 */
1681 break;
1682 }
1683 }
1684
1685 /* Advance array keys, even when we don't have an exact match */
1686 if (array)
1687 {
1688 if (array->num_elems == -1)
1689 {
1690 /* Skip array's new element is tupdatum (or MINVAL/MAXVAL) */
1691 _bt_skiparray_set_element(rel, cur, array, result,
1692 tupdatum, tupnull);
1693 skip_array_advanced = true;
1694 }
1695 else if (array->cur_elem != set_elem)
1696 {
1697 /* SAOP array's new element is set_elem datum */
1698 array->cur_elem = set_elem;
1699 cur->sk_argument = array->elem_values[set_elem];
1700 }
1701 }
1702 }
1703
1704 /*
1705 * Advance the array keys incrementally whenever "beyond end of array
1706 * element" array advancement happens, so that advancement will carry to
1707 * higher-order arrays (might exhaust all the scan's arrays instead, which
1708 * ends the top-level scan).
1709 */
1710 if (beyond_end_advance &&
1711 !_bt_advance_array_keys_increment(scan, dir, &skip_array_advanced))
1712 goto end_toplevel_scan;
1713
1714 Assert(_bt_verify_keys_with_arraykeys(scan));
1715
1716 /*
1717 * Maintain a page-level count of the number of times the scan's array
1718 * keys advanced in a way that affected at least one skip array
1719 */
1720 if (sktrig_required && skip_array_advanced)
1721 pstate->nskipadvances++;
1722
1723 /*
1724 * Does tuple now satisfy our new qual? Recheck with _bt_check_compare.
1725 *
1726 * Calls triggered by an unsatisfied required scan key, whose tuple now
1727 * satisfies all required scan keys, but not all nonrequired array keys,
1728 * will still require a recheck call to _bt_check_compare. They'll still
1729 * need its "second pass" handling of required inequality scan keys.
1730 * (Might have missed a still-unsatisfied required inequality scan key
1731 * that caller didn't detect as the sktrig scan key during its initial
1732 * _bt_check_compare call that used the old/original qual.)
1733 *
1734 * Calls triggered by an unsatisfied nonrequired array scan key never need
1735 * "second pass" handling of required inequalities (nor any other handling
1736 * of any required scan key). All that matters is whether caller's tuple
1737 * satisfies the new qual, so it's safe to just skip the _bt_check_compare
1738 * recheck when we've already determined that it can only return 'false'.
1739 *
1740 * Note: In practice most scan keys are marked required by preprocessing,
1741 * if necessary by generating a preceding skip array. We nevertheless
1742 * often handle array keys marked required as if they were nonrequired.
1743 * This behavior is requested by our _bt_check_compare caller, though only
1744 * when it is passed "forcenonrequired=true" by _bt_checkkeys.
1745 */
1746 if ((sktrig_required && all_required_satisfied) ||
1747 (!sktrig_required && all_satisfied))
1748 {
1749 int nsktrig = sktrig + 1;
1750 bool continuescan;
1751
1752 Assert(all_required_satisfied);
1753
1754 /* Recheck _bt_check_compare on behalf of caller */
1755 if (_bt_check_compare(scan, dir, tuple, tupnatts, tupdesc, false,
1756 !sktrig_required, &continuescan,
1757 &nsktrig) &&
1758 !so->scanBehind)
1759 {
1760 /* This tuple satisfies the new qual */
1761 Assert(all_satisfied && continuescan);
1762
1763 if (pstate)
1764 pstate->continuescan = true;
1765
1766 return true;
1767 }
1768
1769 /*
1770 * Consider "second pass" handling of required inequalities.
1771 *
1772 * It's possible that our _bt_check_compare call indicated that the
1773 * scan should end due to some unsatisfied inequality that wasn't
1774 * initially recognized as such by us. Handle this by calling
1775 * ourselves recursively, this time indicating that the trigger is the
1776 * inequality that we missed first time around (and using a set of
1777 * required array/equality keys that are now exact matches for tuple).
1778 *
1779 * We make a strong, general guarantee that every _bt_checkkeys call
1780 * here will advance the array keys to the maximum possible extent
1781 * that we can know to be safe based on caller's tuple alone. If we
1782 * didn't perform this step, then that guarantee wouldn't quite hold.
1783 */
1784 if (unlikely(!continuescan))
1785 {
1786 bool satisfied PG_USED_FOR_ASSERTS_ONLY;
1787
1788 Assert(sktrig_required);
1789 Assert(so->keyData[nsktrig].sk_strategy != BTEqualStrategyNumber);
1790
1791 /*
1792 * The tuple must use "beyond end" advancement during the
1793 * recursive call, so we cannot possibly end up back here when
1794 * recursing. We'll consume a small, fixed amount of stack space.
1795 */
1796 Assert(!beyond_end_advance);
1797
1798 /* Advance the array keys a second time using same tuple */
1799 satisfied = _bt_advance_array_keys(scan, pstate, tuple, tupnatts,
1800 tupdesc, nsktrig, true);
1801
1802 /* This tuple doesn't satisfy the inequality */
1803 Assert(!satisfied);
1804 return false;
1805 }
1806
1807 /*
1808 * Some non-required scan key (from new qual) still not satisfied.
1809 *
1810 * All scan keys required in the current scan direction must still be
1811 * satisfied, though, so we can trust all_required_satisfied below.
1812 */
1813 }
1814
1815 /*
1816 * When we were called just to deal with "advancing" non-required arrays,
1817 * this is as far as we can go (cannot stop the scan for these callers)
1818 */
1819 if (!sktrig_required)
1820 {
1821 /* Caller's tuple doesn't match any qual */
1822 return false;
1823 }
1824
1825 /*
1826 * Postcondition array state assertion (for still-unsatisfied tuples).
1827 *
1828 * By here we have established that the scan's required arrays (scan must
1829 * have at least one required array) advanced, without becoming exhausted.
1830 *
1831 * Caller's tuple is now < the newly advanced array keys (or > when this
1832 * is a backwards scan), except in the case where we only got this far due
1833 * to an unsatisfied non-required scan key. Verify that with an assert.
1834 *
1835 * Note: we don't just quit at this point when all required scan keys were
1836 * found to be satisfied because we need to consider edge-cases involving
1837 * scan keys required in the opposite direction only; those aren't tracked
1838 * by all_required_satisfied.
1839 */
1840 Assert(_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc, tupnatts,
1841 false, 0, NULL) ==
1842 !all_required_satisfied);
1843
1844 /*
1845 * We generally permit primitive index scans to continue onto the next
1846 * sibling page when the page's finaltup satisfies all required scan keys
1847 * at the point where we're between pages.
1848 *
1849 * If caller's tuple is also the page's finaltup, and we see that required
1850 * scan keys still aren't satisfied, start a new primitive index scan.
1851 */
1852 if (!all_required_satisfied && pstate->finaltup == tuple)
1853 goto new_prim_scan;
1854
1855 /*
1856 * Proactively check finaltup (don't wait until finaltup is reached by the
1857 * scan) when it might well turn out to not be satisfied later on.
1858 *
1859 * Note: if so->scanBehind hasn't already been set for finaltup by us,
1860 * it'll be set during this call to _bt_tuple_before_array_skeys. Either
1861 * way, it'll be set correctly (for the whole page) after this point.
1862 */
1863 if (!all_required_satisfied && pstate->finaltup &&
1864 _bt_tuple_before_array_skeys(scan, dir, pstate->finaltup, tupdesc,
1865 BTreeTupleGetNAtts(pstate->finaltup, rel),
1866 false, 0, &so->scanBehind))
1867 goto new_prim_scan;
1868
1869 /*
1870 * When we encounter a truncated finaltup high key attribute, we're
1871 * optimistic about the chances of its corresponding required scan key
1872 * being satisfied when we go on to recheck it against tuples from this
1873 * page's right sibling leaf page. We consider truncated attributes to be
1874 * satisfied by required scan keys, which allows the primitive index scan
1875 * to continue to the next leaf page. We must set so->scanBehind to true
1876 * to remember that the last page's finaltup had "satisfied" required scan
1877 * keys for one or more truncated attribute values (scan keys required in
1878 * _either_ scan direction).
1879 *
1880 * There is a chance that _bt_readpage (which checks so->scanBehind) will
1881 * find that even the sibling leaf page's finaltup is < the new array
1882 * keys. When that happens, our optimistic policy will have incurred a
1883 * single extra leaf page access that could have been avoided.
1884 *
1885 * A pessimistic policy would give backward scans a gratuitous advantage
1886 * over forward scans. We'd punish forward scans for applying more
1887 * accurate information from the high key, rather than just using the
1888 * final non-pivot tuple as finaltup, in the style of backward scans.
1889 * Being pessimistic would also give some scans with non-required arrays a
1890 * perverse advantage over similar scans that use required arrays instead.
1891 *
1892 * This is similar to our scan-level heuristics, below. They also set
1893 * scanBehind to speculatively continue the primscan onto the next page.
1894 */
1895 if (so->scanBehind)
1896 {
1897 /* Truncated high key -- _bt_scanbehind_checkkeys recheck scheduled */
1898 }
1899
1900 /*
1901 * Handle inequalities marked required in the opposite scan direction.
1902 * They can also signal that we should start a new primitive index scan.
1903 *
1904 * It's possible that the scan is now positioned where "matching" tuples
1905 * begin, and that caller's tuple satisfies all scan keys required in the
1906 * current scan direction. But if caller's tuple still doesn't satisfy
1907 * other scan keys that are required in the opposite scan direction only
1908 * (e.g., a required >= strategy scan key when scan direction is forward),
1909 * it's still possible that there are many leaf pages before the page that
1910 * _bt_first could skip straight to. Groveling through all those pages
1911 * will always give correct answers, but it can be very inefficient. We
1912 * must avoid needlessly scanning extra pages.
1913 *
1914 * Separately, it's possible that _bt_check_compare set continuescan=false
1915 * for a scan key that's required in the opposite direction only. This is
1916 * a special case, that happens only when _bt_check_compare sees that the
1917 * inequality encountered a NULL value. This signals the end of non-NULL
1918 * values in the current scan direction, which is reason enough to end the
1919 * (primitive) scan. If this happens at the start of a large group of
1920 * NULL values, then we shouldn't expect to be called again until after
1921 * the scan has already read indefinitely-many leaf pages full of tuples
1922 * with NULL suffix values. (_bt_first is expected to skip over the group
1923 * of NULLs by applying a similar "deduce NOT NULL" rule of its own, which
1924 * involves consing up an explicit SK_SEARCHNOTNULL key.)
1925 *
1926 * Apply a test against finaltup to detect and recover from the problem:
1927 * if even finaltup doesn't satisfy such an inequality, we just skip by
1928 * starting a new primitive index scan. When we skip, we know for sure
1929 * that all of the tuples on the current page following caller's tuple are
1930 * also before the _bt_first-wise start of tuples for our new qual. That
1931 * at least suggests many more skippable pages beyond the current page.
1932 * (when so->scanBehind and so->oppositeDirCheck are set, this'll happen
1933 * when we test the next page's finaltup/high key instead.)
1934 */
1935 else if (has_required_opposite_direction_only && pstate->finaltup &&
1936 unlikely(!_bt_oppodir_checkkeys(scan, dir, pstate->finaltup)))
1937 goto new_prim_scan;
1938
1939 continue_scan:
1940
1941 /*
1942 * Stick with the ongoing primitive index scan for now.
1943 *
1944 * It's possible that later tuples will also turn out to have values that
1945 * are still < the now-current array keys (or > the current array keys).
1946 * Our caller will handle this by performing what amounts to a linear
1947 * search of the page, implemented by calling _bt_check_compare and then
1948 * _bt_tuple_before_array_skeys for each tuple.
1949 *
1950 * This approach has various advantages over a binary search of the page.
1951 * Repeated binary searches of the page (one binary search for every array
1952 * advancement) won't outperform a continuous linear search. While there
1953 * are workloads that a naive linear search won't handle well, our caller
1954 * has a "look ahead" fallback mechanism to deal with that problem.
1955 */
1956 pstate->continuescan = true; /* Override _bt_check_compare */
1957 so->needPrimScan = false; /* _bt_readpage has more tuples to check */
1958
1959 if (so->scanBehind)
1960 {
1961 /*
1962 * Remember if recheck needs to call _bt_oppodir_checkkeys for next
1963 * page's finaltup (see above comments about "Handle inequalities
1964 * marked required in the opposite scan direction" for why).
1965 */
1966 so->oppositeDirCheck = has_required_opposite_direction_only;
1967
1968 /*
1969 * skip by setting "look ahead" mechanism's offnum for forwards scans
1970 * (backwards scans check scanBehind flag directly instead)
1971 */
1972 if (ScanDirectionIsForward(dir))
1973 pstate->skip = pstate->maxoff + 1;
1974 }
1975
1976 /* Caller's tuple doesn't match the new qual */
1977 return false;
1978
1979 new_prim_scan:
1980
1981 Assert(pstate->finaltup); /* not on rightmost/leftmost page */
1982
1983 /*
1984 * Looks like another primitive index scan is required. But consider
1985 * continuing the current primscan based on scan-level heuristics.
1986 *
1987 * Continue the ongoing primitive scan (and schedule a recheck for when
1988 * the scan arrives on the next sibling leaf page) when it has already
1989 * read at least one leaf page before the one we're reading now. This
1990 * makes primscan scheduling more efficient when scanning subsets of an
1991 * index with many distinct attribute values matching many array elements.
1992 * It encourages fewer, larger primitive scans where that makes sense.
1993 * This will in turn encourage _bt_readpage to apply the pstate.startikey
1994 * optimization more often.
1995 *
1996 * Also continue the ongoing primitive index scan when it is still on the
1997 * first page if there have been more than NSKIPADVANCES_THRESHOLD calls
1998 * here that each advanced at least one of the scan's skip arrays
1999 * (deliberately ignore advancements that only affected SAOP arrays here).
2000 * A page that cycles through this many skip array elements is quite
2001 * likely to neighbor similar pages, that we'll also need to read.
2002 *
2003 * Note: These heuristics aren't as aggressive as you might think. We're
2004 * conservative about allowing a primitive scan to step from the first
2005 * leaf page it reads to the page's sibling page (we only allow it on
2006 * first pages whose finaltup strongly suggests that it'll work out, as
2007 * well as first pages that have a large number of skip array advances).
2008 * Clearing this first page finaltup hurdle is a strong signal in itself.
2009 *
2010 * Note: The NSKIPADVANCES_THRESHOLD heuristic exists only to avoid
2011 * pathological cases. Specifically, cases where a skip scan should just
2012 * behave like a traditional full index scan, but ends up "skipping" again
2013 * and again, descending to the prior leaf page's direct sibling leaf page
2014 * each time. This misbehavior would otherwise be possible during scans
2015 * that never quite manage to "clear the first page finaltup hurdle".
2016 */
2017 if (!pstate->firstpage || pstate->nskipadvances > NSKIPADVANCES_THRESHOLD)
2018 {
2019 /* Schedule a recheck once on the next (or previous) page */
2020 so->scanBehind = true;
2021
2022 /* Continue the current primitive scan after all */
2023 goto continue_scan;
2024 }
2025
2026 /*
2027 * End this primitive index scan, but schedule another.
2028 *
2029 * Note: We make a soft assumption that the current scan direction will
2030 * also be used within _bt_next, when it is asked to step off this page.
2031 * It is up to _bt_next to cancel this scheduled primitive index scan
2032 * whenever it steps to a page in the direction opposite currPos.dir.
2033 */
2034 pstate->continuescan = false; /* Tell _bt_readpage we're done... */
2035 so->needPrimScan = true; /* ...but call _bt_first again */
2036
2037 if (scan->parallel_scan)
2038 _bt_parallel_primscan_schedule(scan, so->currPos.currPage);
2039
2040 /* Caller's tuple doesn't match the new qual */
2041 return false;
2042
2043 end_toplevel_scan:
2044
2045 /*
2046 * End the current primitive index scan, but don't schedule another.
2047 *
2048 * This ends the entire top-level scan in the current scan direction.
2049 *
2050 * Note: The scan's arrays (including any non-required arrays) are now in
2051 * their final positions for the current scan direction. If the scan
2052 * direction happens to change, then the arrays will already be in their
2053 * first positions for what will then be the current scan direction.
2054 */
2055 pstate->continuescan = false; /* Tell _bt_readpage we're done... */
2056 so->needPrimScan = false; /* ...and don't call _bt_first again */
2057
2058 /* Caller's tuple doesn't match any qual */
2059 return false;
2060 }
2061
2062 #ifdef USE_ASSERT_CHECKING
2063 /*
2064 * Verify that the scan's "so->keyData[]" scan keys are in agreement with
2065 * its array key state
2066 */
2067 static bool
2068 _bt_verify_keys_with_arraykeys(IndexScanDesc scan)
2069 {
2070 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2071 int last_sk_attno = InvalidAttrNumber,
2072 arrayidx = 0;
2073 bool nonrequiredseen = false;
2074
2075 if (!so->qual_ok)
2076 return false;
2077
2078 for (int ikey = 0; ikey < so->numberOfKeys; ikey++)
2079 {
2080 ScanKey cur = so->keyData + ikey;
2081 BTArrayKeyInfo *array;
2082
2083 if (cur->sk_strategy != BTEqualStrategyNumber ||
2084 !(cur->sk_flags & SK_SEARCHARRAY))
2085 continue;
2086
2087 array = &so->arrayKeys[arrayidx++];
2088 if (array->scan_key != ikey)
2089 return false;
2090
2091 if (array->num_elems == 0 || array->num_elems < -1)
2092 return false;
2093
2094 if (array->num_elems != -1 &&
2095 cur->sk_argument != array->elem_values[array->cur_elem])
2096 return false;
2097 if (cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
2098 {
2099 if (last_sk_attno > cur->sk_attno)
2100 return false;
2101 if (nonrequiredseen)
2102 return false;
2103 }
2104 else
2105 nonrequiredseen = true;
2106
2107 last_sk_attno = cur->sk_attno;
2108 }
2109
2110 if (arrayidx != so->numArrayKeys)
2111 return false;
2112
2113 return true;
2114 }
2115 #endif
2116
2117 /*
2118 * Test whether an indextuple satisfies all the scankey conditions.
2119 *
2120 * Return true if so, false if not. If the tuple fails to pass the qual,
2121 * we also determine whether there's any need to continue the scan beyond
2122 * this tuple, and set pstate.continuescan accordingly. See comments for
2123 * _bt_preprocess_keys() about how this is done.
2124 *
2125 * Forward scan callers can pass a high key tuple in the hopes of having
2126 * us set *continuescan to false, and avoiding an unnecessary visit to
2127 * the page to the right.
2128 *
2129 * Advances the scan's array keys when necessary for arrayKeys=true callers.
2130 * Scans without any array keys must always pass arrayKeys=false.
2131 *
2132 * Also stops and starts primitive index scans for arrayKeys=true callers.
2133 * Scans with array keys are required to set up page state that helps us with
2134 * this. The page's finaltup tuple (the page high key for a forward scan, or
2135 * the page's first non-pivot tuple for a backward scan) must be set in
2136 * pstate.finaltup ahead of the first call here for the page. Set this to
2137 * NULL for rightmost page (or the leftmost page for backwards scans).
2138 *
2139 * scan: index scan descriptor (containing a search-type scankey)
2140 * pstate: page level input and output parameters
2141 * arrayKeys: should we advance the scan's array keys if necessary?
2142 * tuple: index tuple to test
2143 * tupnatts: number of attributes in tupnatts (high key may be truncated)
2144 */
2145 bool
2146 _bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys,
2147 IndexTuple tuple, int tupnatts)
2148 {
2149 TupleDesc tupdesc = RelationGetDescr(scan->indexRelation);
2150 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2151 ScanDirection dir = so->currPos.dir;
2152 int ikey = pstate->startikey;
2153 bool res;
2154
2155 Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts);
2156 Assert(!so->needPrimScan && !so->scanBehind && !so->oppositeDirCheck);
2157 Assert(arrayKeys || so->numArrayKeys == 0);
2158
2159 res = _bt_check_compare(scan, dir, tuple, tupnatts, tupdesc, arrayKeys,
2160 pstate->forcenonrequired, &pstate->continuescan,
2161 &ikey);
2162
2163 /*
2164 * If _bt_check_compare relied on the pstate.startikey optimization, call
2165 * again (in assert-enabled builds) to verify it didn't affect our answer.
2166 *
2167 * Note: we can't do this when !pstate.forcenonrequired, since any arrays
2168 * before pstate.startikey won't have advanced on this page at all.
2169 */
2170 Assert(!pstate->forcenonrequired || arrayKeys);
2171 #ifdef USE_ASSERT_CHECKING
2172 if (pstate->startikey > 0 && !pstate->forcenonrequired)
2173 {
2174 bool dres,
2175 dcontinuescan;
2176 int dikey = 0;
2177
2178 /* Pass arrayKeys=false to avoid array side-effects */
2179 dres = _bt_check_compare(scan, dir, tuple, tupnatts, tupdesc, false,
2180 pstate->forcenonrequired, &dcontinuescan,
2181 &dikey);
2182 Assert(res == dres);
2183 Assert(pstate->continuescan == dcontinuescan);
2184
2185 /*
2186 * Should also get the same ikey result. We need a slightly weaker
2187 * assertion during arrayKeys calls, since they might be using an
2188 * array that couldn't be marked required during preprocessing.
2189 */
2190 Assert(arrayKeys || ikey == dikey);
2191 Assert(ikey <= dikey);
2192 }
2193 #endif
2194
2195 /*
2196 * Only one _bt_check_compare call is required in the common case where
2197 * there are no equality strategy array scan keys. Otherwise we can only
2198 * accept _bt_check_compare's answer unreservedly when it didn't set
2199 * pstate.continuescan=false.
2200 */
2201 if (!arrayKeys || pstate->continuescan)
2202 return res;
2203
2204 /*
2205 * _bt_check_compare call set continuescan=false in the presence of
2206 * equality type array keys. This could mean that the tuple is just past
2207 * the end of matches for the current array keys.
2208 *
2209 * It's also possible that the scan is still _before_ the _start_ of
2210 * tuples matching the current set of array keys. Check for that first.
2211 */
2212 Assert(!pstate->forcenonrequired);
2213 if (_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc, tupnatts, true,
2214 ikey, NULL))
2215 {
2216 /* Override _bt_check_compare, continue primitive scan */
2217 pstate->continuescan = true;
2218
2219 /*
2220 * We will end up here repeatedly given a group of tuples > the
2221 * previous array keys and < the now-current keys (for a backwards
2222 * scan it's just the same, though the operators swap positions).
2223 *
2224 * We must avoid allowing this linear search process to scan very many
2225 * tuples from well before the start of tuples matching the current
2226 * array keys (or from well before the point where we'll once again
2227 * have to advance the scan's array keys).
2228 *
2229 * We keep the overhead under control by speculatively "looking ahead"
2230 * to later still-unscanned items from this same leaf page. We'll
2231 * only attempt this once the number of tuples that the linear search
2232 * process has examined starts to get out of hand.
2233 */
2234 pstate->rechecks++;
2235 if (pstate->rechecks >= LOOK_AHEAD_REQUIRED_RECHECKS)
2236 {
2237 /* See if we should skip ahead within the current leaf page */
2238 _bt_checkkeys_look_ahead(scan, pstate, tupnatts, tupdesc);
2239
2240 /*
2241 * Might have set pstate.skip to a later page offset. When that
2242 * happens then _bt_readpage caller will inexpensively skip ahead
2243 * to a later tuple from the same page (the one just after the
2244 * tuple we successfully "looked ahead" to).
2245 */
2246 }
2247
2248 /* This indextuple doesn't match the current qual, in any case */
2249 return false;
2250 }
2251
2252 /*
2253 * Caller's tuple is >= the current set of array keys and other equality
2254 * constraint scan keys (or <= if this is a backwards scan). It's now
2255 * clear that we _must_ advance any required array keys in lockstep with
2256 * the scan.
2257 */
2258 return _bt_advance_array_keys(scan, pstate, tuple, tupnatts, tupdesc,
2259 ikey, true);
2260 }
2261
2262 /*
2263 * Test whether caller's finaltup tuple is still before the start of matches
2264 * for the current array keys.
2265 *
2266 * Called at the start of reading a page during a scan with array keys, though
2267 * only when the so->scanBehind flag was set on the scan's prior page.
2268 *
2269 * Returns false if the tuple is still before the start of matches. When that
2270 * happens, caller should cut its losses and start a new primitive index scan.
2271 * Otherwise returns true.
2272 */
2273 bool
2274 _bt_scanbehind_checkkeys(IndexScanDesc scan, ScanDirection dir,
2275 IndexTuple finaltup)
2276 {
2277 Relation rel = scan->indexRelation;
2278 TupleDesc tupdesc = RelationGetDescr(rel);
2279 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2280 int nfinaltupatts = BTreeTupleGetNAtts(finaltup, rel);
2281 bool scanBehind;
2282
2283 Assert(so->numArrayKeys);
2284
2285 if (_bt_tuple_before_array_skeys(scan, dir, finaltup, tupdesc,
2286 nfinaltupatts, false, 0, &scanBehind))
2287 return false;
2288
2289 /*
2290 * If scanBehind was set, all of the untruncated attribute values from
2291 * finaltup that correspond to an array match the array's current element,
2292 * but there are other keys associated with truncated suffix attributes.
2293 * Array advancement must have incremented the scan's arrays on the
2294 * previous page, resulting in a set of array keys that happen to be an
2295 * exact match for the current page high key's untruncated prefix values.
2296 *
2297 * This page definitely doesn't contain tuples that the scan will need to
2298 * return. The next page may or may not contain relevant tuples. Handle
2299 * this by cutting our losses and starting a new primscan.
2300 */
2301 if (scanBehind)
2302 return false;
2303
2304 if (!so->oppositeDirCheck)
2305 return true;
2306
2307 return _bt_oppodir_checkkeys(scan, dir, finaltup);
2308 }
2309
2310 /*
2311 * Test whether an indextuple fails to satisfy an inequality required in the
2312 * opposite direction only.
2313 *
2314 * Caller's finaltup tuple is the page high key (for forwards scans), or the
2315 * first non-pivot tuple (for backwards scans). Called during scans with
2316 * required array keys and required opposite-direction inequalities.
2317 *
2318 * Returns false if an inequality scan key required in the opposite direction
2319 * only isn't satisfied (and any earlier required scan keys are satisfied).
2320 * Otherwise returns true.
2321 *
2322 * An unsatisfied inequality required in the opposite direction only might
2323 * well enable skipping over many leaf pages, provided another _bt_first call
2324 * takes place. This type of unsatisfied inequality won't usually cause
2325 * _bt_checkkeys to stop the scan to consider array advancement/starting a new
2326 * primitive index scan.
2327 */
2328 static bool
2329 _bt_oppodir_checkkeys(IndexScanDesc scan, ScanDirection dir,
2330 IndexTuple finaltup)
2331 {
2332 Relation rel = scan->indexRelation;
2333 TupleDesc tupdesc = RelationGetDescr(rel);
2334 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2335 int nfinaltupatts = BTreeTupleGetNAtts(finaltup, rel);
2336 bool continuescan;
2337 ScanDirection flipped = -dir;
2338 int ikey = 0;
2339
2340 Assert(so->numArrayKeys);
2341
2342 _bt_check_compare(scan, flipped, finaltup, nfinaltupatts, tupdesc, false,
2343 false, &continuescan,
2344 &ikey);
2345
2346 if (!continuescan && so->keyData[ikey].sk_strategy != BTEqualStrategyNumber)
2347 return false;
2348
2349 return true;
2350 }
2351
2352 /*
2353 * Determines an offset to the first scan key (an so->keyData[]-wise offset)
2354 * that is _not_ guaranteed to be satisfied by every tuple from pstate.page,
2355 * which is set in pstate.startikey for _bt_checkkeys calls for the page.
2356 * This allows caller to save cycles on comparisons of a prefix of keys while
2357 * reading pstate.page.
2358 *
2359 * Also determines if later calls to _bt_checkkeys (for pstate.page) should be
2360 * forced to treat all required scan keys >= pstate.startikey as nonrequired
2361 * (that is, if they're to be treated as if any SK_BT_REQFWD/SK_BT_REQBKWD
2362 * markings that were set by preprocessing were not set at all, for the
2363 * duration of _bt_checkkeys calls prior to the call for pstate.finaltup).
2364 * This is indicated to caller by setting pstate.forcenonrequired.
2365 *
2366 * Call here at the start of reading a leaf page beyond the first one for the
2367 * primitive index scan. We consider all non-pivot tuples, so it doesn't make
2368 * sense to call here when only a subset of those tuples can ever be read.
2369 * This is also a good idea on performance grounds; not calling here when on
2370 * the first page (first for the current primitive scan) avoids wasting cycles
2371 * during selective point queries. They typically don't stand to gain as much
2372 * when we can set pstate.startikey, and are likely to notice the overhead of
2373 * calling here. (Also, allowing pstate.forcenonrequired to be set on a
2374 * primscan's first page would mislead _bt_advance_array_keys, which expects
2375 * pstate.nskipadvances to be representative of every first page's key space.)
2376 *
2377 * Caller must call _bt_start_array_keys and reset startikey/forcenonrequired
2378 * ahead of the finaltup _bt_checkkeys call when we set forcenonrequired=true.
2379 * This will give _bt_checkkeys the opportunity to call _bt_advance_array_keys
2380 * with sktrig_required=true, restoring the invariant that the scan's required
2381 * arrays always track the scan's progress through the index's key space.
2382 * Caller won't need to do this on the rightmost/leftmost page in the index
2383 * (where pstate.finaltup isn't ever set), since forcenonrequired will never
2384 * be set here in the first place.
2385 */
2386 void
2387 _bt_set_startikey(IndexScanDesc scan, BTReadPageState *pstate)
2388 {
2389 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2390 Relation rel = scan->indexRelation;
2391 TupleDesc tupdesc = RelationGetDescr(rel);
2392 ItemId iid;
2393 IndexTuple firsttup,
2394 lasttup;
2395 int startikey = 0,
2396 arrayidx = 0,
2397 firstchangingattnum;
2398 bool start_past_saop_eq = false;
2399
2400 Assert(!so->scanBehind);
2401 Assert(pstate->minoff < pstate->maxoff);
2402 Assert(!pstate->firstpage);
2403 Assert(pstate->startikey == 0);
2404 Assert(!so->numArrayKeys || pstate->finaltup ||
2405 P_RIGHTMOST(BTPageGetOpaque(pstate->page)) ||
2406 P_LEFTMOST(BTPageGetOpaque(pstate->page)));
2407
2408 if (so->numberOfKeys == 0)
2409 return;
2410
2411 /* minoff is an offset to the lowest non-pivot tuple on the page */
2412 iid = PageGetItemId(pstate->page, pstate->minoff);
2413 firsttup = (IndexTuple) PageGetItem(pstate->page, iid);
2414
2415 /* maxoff is an offset to the highest non-pivot tuple on the page */
2416 iid = PageGetItemId(pstate->page, pstate->maxoff);
2417 lasttup = (IndexTuple) PageGetItem(pstate->page, iid);
2418
2419 /* Determine the first attribute whose values change on caller's page */
2420 firstchangingattnum = _bt_keep_natts_fast(rel, firsttup, lasttup);
2421
2422 for (; startikey < so->numberOfKeys; startikey++)
2423 {
2424 ScanKey key = so->keyData + startikey;
2425 BTArrayKeyInfo *array;
2426 Datum firstdatum,
2427 lastdatum;
2428 bool firstnull,
2429 lastnull;
2430 int32 result;
2431
2432 /*
2433 * Determine if it's safe to set pstate.startikey to an offset to a
2434 * key that comes after this key, by examining this key
2435 */
2436 if (!(key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)))
2437 {
2438 /* Scan key isn't marked required (corner case) */
2439 break; /* unsafe */
2440 }
2441 if (key->sk_flags & SK_ROW_HEADER)
2442 {
2443 /* RowCompare inequalities currently aren't supported */
2444 break; /* "unsafe" */
2445 }
2446 if (key->sk_strategy != BTEqualStrategyNumber)
2447 {
2448 /*
2449 * Scalar inequality key.
2450 *
2451 * It's definitely safe for _bt_checkkeys to avoid assessing this
2452 * inequality when the page's first and last non-pivot tuples both
2453 * satisfy the inequality (since the same must also be true of all
2454 * the tuples in between these two).
2455 *
2456 * Unlike the "=" case, it doesn't matter if this attribute has
2457 * more than one distinct value (though it _is_ necessary for any
2458 * and all _prior_ attributes to contain no more than one distinct
2459 * value amongst all of the tuples from pstate.page).
2460 */
2461 if (key->sk_attno > firstchangingattnum) /* >, not >= */
2462 break; /* unsafe, preceding attr has multiple
2463 * distinct values */
2464
2465 firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc, &firstnull);
2466 lastdatum = index_getattr(lasttup, key->sk_attno, tupdesc, &lastnull);
2467
2468 if (key->sk_flags & SK_ISNULL)
2469 {
2470 /* IS NOT NULL key */
2471 Assert(key->sk_flags & SK_SEARCHNOTNULL);
2472
2473 if (firstnull || lastnull)
2474 break; /* unsafe */
2475
2476 /* Safe, IS NOT NULL key satisfied by every tuple */
2477 continue;
2478 }
2479
2480 /* Test firsttup */
2481 if (firstnull ||
2482 !DatumGetBool(FunctionCall2Coll(&key->sk_func,
2483 key->sk_collation, firstdatum,
2484 key->sk_argument)))
2485 break; /* unsafe */
2486
2487 /* Test lasttup */
2488 if (lastnull ||
2489 !DatumGetBool(FunctionCall2Coll(&key->sk_func,
2490 key->sk_collation, lastdatum,
2491 key->sk_argument)))
2492 break; /* unsafe */
2493
2494 /* Safe, scalar inequality satisfied by every tuple */
2495 continue;
2496 }
2497
2498 /* Some = key (could be a scalar = key, could be an array = key) */
2499 Assert(key->sk_strategy == BTEqualStrategyNumber);
2500
2501 if (!(key->sk_flags & SK_SEARCHARRAY))
2502 {
2503 /*
2504 * Scalar = key (possibly an IS NULL key).
2505 *
2506 * It is unsafe to set pstate.startikey to an ikey beyond this
2507 * key, unless the = key is satisfied by every possible tuple on
2508 * the page (possible only when attribute has just one distinct
2509 * value among all tuples on the page).
2510 */
2511 if (key->sk_attno >= firstchangingattnum)
2512 break; /* unsafe, multiple distinct attr values */
2513
2514 firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc,
2515 &firstnull);
2516 if (key->sk_flags & SK_ISNULL)
2517 {
2518 /* IS NULL key */
2519 Assert(key->sk_flags & SK_SEARCHNULL);
2520
2521 if (!firstnull)
2522 break; /* unsafe */
2523
2524 /* Safe, IS NULL key satisfied by every tuple */
2525 continue;
2526 }
2527 if (firstnull ||
2528 !DatumGetBool(FunctionCall2Coll(&key->sk_func,
2529 key->sk_collation, firstdatum,
2530 key->sk_argument)))
2531 break; /* unsafe */
2532
2533 /* Safe, scalar = key satisfied by every tuple */
2534 continue;
2535 }
2536
2537 /* = array key (could be a SAOP array, could be a skip array) */
2538 array = &so->arrayKeys[arrayidx++];
2539 Assert(array->scan_key == startikey);
2540 if (array->num_elems != -1)
2541 {
2542 /*
2543 * SAOP array = key.
2544 *
2545 * Handle this like we handle scalar = keys (though binary search
2546 * for a matching element, to avoid relying on key's sk_argument).
2547 */
2548 if (key->sk_attno >= firstchangingattnum)
2549 break; /* unsafe, multiple distinct attr values */
2550
2551 firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc,
2552 &firstnull);
2553 _bt_binsrch_array_skey(&so->orderProcs[startikey],
2554 false, NoMovementScanDirection,
2555 firstdatum, firstnull, array, key,
2556 &result);
2557 if (result != 0)
2558 break; /* unsafe */
2559
2560 /* Safe, SAOP = key satisfied by every tuple */
2561 start_past_saop_eq = true;
2562 continue;
2563 }
2564
2565 /*
2566 * Skip array = key
2567 */
2568 Assert(key->sk_flags & SK_BT_SKIP);
2569 if (array->null_elem)
2570 {
2571 /*
2572 * Non-range skip array = key.
2573 *
2574 * Safe, non-range skip array "satisfied" by every tuple on page
2575 * (safe even when "key->sk_attno > firstchangingattnum").
2576 */
2577 continue;
2578 }
2579
2580 /*
2581 * Range skip array = key.
2582 *
2583 * Handle this like we handle scalar inequality keys (but avoid using
2584 * key's sk_argument directly, as in the SAOP array case).
2585 */
2586 if (key->sk_attno > firstchangingattnum) /* >, not >= */
2587 break; /* unsafe, preceding attr has multiple
2588 * distinct values */
2589
2590 firstdatum = index_getattr(firsttup, key->sk_attno, tupdesc, &firstnull);
2591 lastdatum = index_getattr(lasttup, key->sk_attno, tupdesc, &lastnull);
2592
2593 /* Test firsttup */
2594 _bt_binsrch_skiparray_skey(false, ForwardScanDirection,
2595 firstdatum, firstnull, array, key,
2596 &result);
2597 if (result != 0)
2598 break; /* unsafe */
2599
2600 /* Test lasttup */
2601 _bt_binsrch_skiparray_skey(false, ForwardScanDirection,
2602 lastdatum, lastnull, array, key,
2603 &result);
2604 if (result != 0)
2605 break; /* unsafe */
2606
2607 /* Safe, range skip array satisfied by every tuple on page */
2608 }
2609
2610 /*
2611 * Use of forcenonrequired is typically undesirable, since it'll force
2612 * _bt_readpage caller to read every tuple on the page -- even though, in
2613 * general, it might well be possible to end the scan on an earlier tuple.
2614 * However, caller must use forcenonrequired when start_past_saop_eq=true,
2615 * since the usual required array behavior might fail to roll over to the
2616 * SAOP array.
2617 *
2618 * We always prefer forcenonrequired=true during scans with skip arrays
2619 * (except on the first page of each primitive index scan), though -- even
2620 * when "startikey == 0". That way, _bt_advance_array_keys's low-order
2621 * key precheck optimization can always be used (unless on the first page
2622 * of the scan). It seems slightly preferable to check more tuples when
2623 * that allows us to do significantly less skip array maintenance.
2624 */
2625 pstate->forcenonrequired = (start_past_saop_eq || so->skipScan);
2626 pstate->startikey = startikey;
2627
2628 /*
2629 * _bt_readpage caller is required to call _bt_checkkeys against page's
2630 * finaltup with forcenonrequired=false whenever we initially set
2631 * forcenonrequired=true. That way the scan's arrays will reliably track
2632 * its progress through the index's key space.
2633 *
2634 * We don't expect this when _bt_readpage caller has no finaltup due to
2635 * its page being the rightmost (or the leftmost, during backwards scans).
2636 * When we see that _bt_readpage has no finaltup, back out of everything.
2637 */
2638 Assert(!pstate->forcenonrequired || so->numArrayKeys);
2639 if (pstate->forcenonrequired && !pstate->finaltup)
2640 {
2641 pstate->forcenonrequired = false;
2642 pstate->startikey = 0;
2643 }
2644 }
2645
2646 /*
2647 * Test whether an indextuple satisfies current scan condition.
2648 *
2649 * Return true if so, false if not. If not, also sets *continuescan to false
2650 * when it's also not possible for any later tuples to pass the current qual
2651 * (with the scan's current set of array keys, in the current scan direction),
2652 * in addition to setting *ikey to the so->keyData[] subscript/offset for the
2653 * unsatisfied scan key (needed when caller must consider advancing the scan's
2654 * array keys).
2655 *
2656 * This is a subroutine for _bt_checkkeys. We provisionally assume that
2657 * reaching the end of the current set of required keys (in particular the
2658 * current required array keys) ends the ongoing (primitive) index scan.
2659 * Callers without array keys should just end the scan right away when they
2660 * find that continuescan has been set to false here by us. Things are more
2661 * complicated for callers with array keys.
2662 *
2663 * Callers with array keys must first consider advancing the arrays when
2664 * continuescan has been set to false here by us. They must then consider if
2665 * it really does make sense to end the current (primitive) index scan, in
2666 * light of everything that is known at that point. (In general when we set
2667 * continuescan=false for these callers it must be treated as provisional.)
2668 *
2669 * We deal with advancing unsatisfied non-required arrays directly, though.
2670 * This is safe, since by definition non-required keys can't end the scan.
2671 * This is just how we determine if non-required arrays are just unsatisfied
2672 * by the current array key, or if they're truly unsatisfied (that is, if
2673 * they're unsatisfied by every possible array key).
2674 *
2675 * Pass advancenonrequired=false to avoid all array related side effects.
2676 * This allows _bt_advance_array_keys caller to avoid infinite recursion.
2677 *
2678 * Pass forcenonrequired=true to instruct us to treat all keys as nonrequired.
2679 * This is used to make it safe to temporarily stop properly maintaining the
2680 * scan's required arrays. _bt_checkkeys caller (_bt_readpage, actually)
2681 * determines a prefix of keys that must satisfy every possible corresponding
2682 * index attribute value from its page, which is passed to us via *ikey arg
2683 * (this is the first key that might be unsatisfied by tuples on the page).
2684 * Obviously, we won't maintain any array keys from before *ikey, so it's
2685 * quite possible for such arrays to "fall behind" the index's keyspace.
2686 * Caller will need to "catch up" by passing forcenonrequired=true (alongside
2687 * an *ikey=0) once the page's finaltup is reached.
2688 *
2689 * Note: it's safe to pass an *ikey > 0 with forcenonrequired=false, but only
2690 * when caller determines that it won't affect array maintenance.
2691 */
2692 static bool
2693 _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
2694 IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
2695 bool advancenonrequired, bool forcenonrequired,
2696 bool *continuescan, int *ikey)
2697 {
2698 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2699
2700 *continuescan = true; /* default assumption */
2701
2702 for (; *ikey < so->numberOfKeys; (*ikey)++)
2703 {
2704 ScanKey key = so->keyData + *ikey;
2705 Datum datum;
2706 bool isNull;
2707 bool requiredSameDir = false,
2708 requiredOppositeDirOnly = false;
2709
2710 /*
2711 * Check if the key is required in the current scan direction, in the
2712 * opposite scan direction _only_, or in neither direction (except
2713 * when we're forced to treat all scan keys as nonrequired)
2714 */
2715 if (forcenonrequired)
2716 {
2717 /* treating scan's keys as non-required */
2718 }
2719 else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) ||
2720 ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
2721 requiredSameDir = true;
2722 else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsBackward(dir)) ||
2723 ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsForward(dir)))
2724 requiredOppositeDirOnly = true;
2725
2726 if (key->sk_attno > tupnatts)
2727 {
2728 /*
2729 * This attribute is truncated (must be high key). The value for
2730 * this attribute in the first non-pivot tuple on the page to the
2731 * right could be any possible value. Assume that truncated
2732 * attribute passes the qual.
2733 */
2734 Assert(BTreeTupleIsPivot(tuple));
2735 continue;
2736 }
2737
2738 /*
2739 * A skip array scan key uses one of several sentinel values. We just
2740 * fall back on _bt_tuple_before_array_skeys when we see such a value.
2741 */
2742 if (key->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL |
2743 SK_BT_NEXT | SK_BT_PRIOR))
2744 {
2745 Assert(key->sk_flags & SK_SEARCHARRAY);
2746 Assert(key->sk_flags & SK_BT_SKIP);
2747 Assert(requiredSameDir || forcenonrequired);
2748
2749 /*
2750 * Cannot fall back on _bt_tuple_before_array_skeys when we're
2751 * treating the scan's keys as nonrequired, though. Just handle
2752 * this like any other non-required equality-type array key.
2753 */
2754 if (forcenonrequired)
2755 return _bt_advance_array_keys(scan, NULL, tuple, tupnatts,
2756 tupdesc, *ikey, false);
2757
2758 *continuescan = false;
2759 return false;
2760 }
2761
2762 /* row-comparison keys need special processing */
2763 if (key->sk_flags & SK_ROW_HEADER)
2764 {
2765 if (_bt_check_rowcompare(key, tuple, tupnatts, tupdesc, dir,
2766 forcenonrequired, continuescan))
2767 continue;
2768 return false;
2769 }
2770
2771 datum = index_getattr(tuple,
2772 key->sk_attno,
2773 tupdesc,
2774 &isNull);
2775
2776 if (key->sk_flags & SK_ISNULL)
2777 {
2778 /* Handle IS NULL/NOT NULL tests */
2779 if (key->sk_flags & SK_SEARCHNULL)
2780 {
2781 if (isNull)
2782 continue; /* tuple satisfies this qual */
2783 }
2784 else
2785 {
2786 Assert(key->sk_flags & SK_SEARCHNOTNULL);
2787 Assert(!(key->sk_flags & SK_BT_SKIP));
2788 if (!isNull)
2789 continue; /* tuple satisfies this qual */
2790 }
2791
2792 /*
2793 * Tuple fails this qual. If it's a required qual for the current
2794 * scan direction, then we can conclude no further tuples will
2795 * pass, either.
2796 */
2797 if (requiredSameDir)
2798 *continuescan = false;
2799 else if (unlikely(key->sk_flags & SK_BT_SKIP))
2800 {
2801 /*
2802 * If we're treating scan keys as nonrequired, and encounter a
2803 * skip array scan key whose current element is NULL, then it
2804 * must be a non-range skip array. It must be satisfied, so
2805 * there's no need to call _bt_advance_array_keys to check.
2806 */
2807 Assert(forcenonrequired && *ikey > 0);
2808 continue;
2809 }
2810
2811 /*
2812 * This indextuple doesn't match the qual.
2813 */
2814 return false;
2815 }
2816
2817 if (isNull)
2818 {
2819 /*
2820 * Scalar scan key isn't satisfied by NULL tuple value.
2821 *
2822 * If we're treating scan keys as nonrequired, and key is for a
2823 * skip array, then we must attempt to advance the array to NULL
2824 * (if we're successful then the tuple might match the qual).
2825 */
2826 if (unlikely(forcenonrequired && key->sk_flags & SK_BT_SKIP))
2827 return _bt_advance_array_keys(scan, NULL, tuple, tupnatts,
2828 tupdesc, *ikey, false);
2829
2830 if (key->sk_flags & SK_BT_NULLS_FIRST)
2831 {
2832 /*
2833 * Since NULLs are sorted before non-NULLs, we know we have
2834 * reached the lower limit of the range of values for this
2835 * index attr. On a backward scan, we can stop if this qual
2836 * is one of the "must match" subset. We can stop regardless
2837 * of whether the qual is > or <, so long as it's required,
2838 * because it's not possible for any future tuples to pass. On
2839 * a forward scan, however, we must keep going, because we may
2840 * have initially positioned to the start of the index.
2841 * (_bt_advance_array_keys also relies on this behavior during
2842 * forward scans.)
2843 */
2844 if ((requiredSameDir || requiredOppositeDirOnly) &&
2845 ScanDirectionIsBackward(dir))
2846 *continuescan = false;
2847 }
2848 else
2849 {
2850 /*
2851 * Since NULLs are sorted after non-NULLs, we know we have
2852 * reached the upper limit of the range of values for this
2853 * index attr. On a forward scan, we can stop if this qual is
2854 * one of the "must match" subset. We can stop regardless of
2855 * whether the qual is > or <, so long as it's required,
2856 * because it's not possible for any future tuples to pass. On
2857 * a backward scan, however, we must keep going, because we
2858 * may have initially positioned to the end of the index.
2859 * (_bt_advance_array_keys also relies on this behavior during
2860 * backward scans.)
2861 */
2862 if ((requiredSameDir || requiredOppositeDirOnly) &&
2863 ScanDirectionIsForward(dir))
2864 *continuescan = false;
2865 }
2866
2867 /*
2868 * This indextuple doesn't match the qual.
2869 */
2870 return false;
2871 }
2872
2873 if (!DatumGetBool(FunctionCall2Coll(&key->sk_func, key->sk_collation,
2874 datum, key->sk_argument)))
2875 {
2876 /*
2877 * Tuple fails this qual. If it's a required qual for the current
2878 * scan direction, then we can conclude no further tuples will
2879 * pass, either.
2880 */
2881 if (requiredSameDir)
2882 *continuescan = false;
2883
2884 /*
2885 * If this is a non-required equality-type array key, the tuple
2886 * needs to be checked against every possible array key. Handle
2887 * this by "advancing" the scan key's array to a matching value
2888 * (if we're successful then the tuple might match the qual).
2889 */
2890 else if (advancenonrequired &&
2891 key->sk_strategy == BTEqualStrategyNumber &&
2892 (key->sk_flags & SK_SEARCHARRAY))
2893 return _bt_advance_array_keys(scan, NULL, tuple, tupnatts,
2894 tupdesc, *ikey, false);
2895
2896 /*
2897 * This indextuple doesn't match the qual.
2898 */
2899 return false;
2900 }
2901 }
2902
2903 /* If we get here, the tuple passes all index quals. */
2904 return true;
2905 }
2906
2907 /*
2908 * Test whether an indextuple satisfies a row-comparison scan condition.
2909 *
2910 * Return true if so, false if not. If not, also clear *continuescan if
2911 * it's not possible for any future tuples in the current scan direction
2912 * to pass the qual.
2913 *
2914 * This is a subroutine for _bt_checkkeys/_bt_check_compare. Caller passes us
2915 * a row compare header key taken from so->keyData[].
2916 *
2917 * Row value comparisons can be described in terms of logical expansions that
2918 * use only scalar operators. Consider the following example row comparison:
2919 *
2920 * "(a, b, c) > (7, 'bar', 62)"
2921 *
2922 * This can be evaluated as:
2923 *
2924 * "(a = 7 AND b = 'bar' AND c > 62) OR (a = 7 AND b > 'bar') OR (a > 7)".
2925 *
2926 * Notice that this condition is satisfied by _all_ rows that satisfy "a > 7",
2927 * and by a subset of all rows that satisfy "a >= 7" (possibly all such rows).
2928 * It _can't_ be satisfied by other rows (where "a < 7" or where "a IS NULL").
2929 * A row comparison header key can therefore often be treated as if it was a
2930 * simple scalar inequality on the row compare's most significant column.
2931 * (For example, _bt_advance_array_keys and most preprocessing routines treat
2932 * row compares like any other same-strategy inequality on the same column.)
2933 *
2934 * Things get more complicated for our row compare given a row where "a = 7".
2935 * Note that a row compare isn't necessarily satisfied by _every_ tuple that
2936 * appears between the first and last satisfied tuple returned by the scan,
2937 * due to the way that its lower-order subkeys are only conditionally applied.
2938 * A forwards scan that uses our example qual might initially return a tuple
2939 * "(a, b, c) = (7, 'zebra', 54)". But it won't subsequently return a tuple
2940 * "(a, b, c) = (7, NULL, 1)" located to the right of the first matching tuple
2941 * (assume that "b" was declared NULLS LAST here). The scan will only return
2942 * additional matches upon reaching tuples where "a > 7". If you rereview our
2943 * example row comparison's logical expansion, you'll understand why this is.
2944 * (Here we assume that all subkeys could be marked required, guaranteeing
2945 * that row comparison order matches index order. This is the common case.)
2946 *
2947 * Note that a row comparison header key behaves _exactly_ the same as a
2948 * similar scalar inequality key on the row's most significant column once the
2949 * scan reaches the point where it no longer needs to evaluate lower-order
2950 * subkeys (or before the point where it starts needing to evaluate them).
2951 * For example, once a forwards scan that uses our example qual reaches the
2952 * first tuple "a > 7", we'll behave in just the same way as our caller would
2953 * behave with a similar scalar inequality "a > 7" for the remainder of the
2954 * scan (assuming that the scan never changes direction/never goes backwards).
2955 * We'll even set continuescan=false according to exactly the same rules as
2956 * the ones our caller applies with simple scalar inequalities, including the
2957 * rules it applies when NULL tuple values don't satisfy an inequality qual.
2958 */
2959 static bool
2960 _bt_check_rowcompare(ScanKey header, IndexTuple tuple, int tupnatts,
2961 TupleDesc tupdesc, ScanDirection dir,
2962 bool forcenonrequired, bool *continuescan)
2963 {
2964 ScanKey subkey = (ScanKey) DatumGetPointer(header->sk_argument);
2965 int32 cmpresult = 0;
2966 bool result;
2967
2968 /* First subkey should be same as the header says */
2969 Assert(header->sk_flags & SK_ROW_HEADER);
2970 Assert(subkey->sk_attno == header->sk_attno);
2971 Assert(subkey->sk_strategy == header->sk_strategy);
2972
2973 /* Loop over columns of the row condition */
2974 for (;;)
2975 {
2976 Datum datum;
2977 bool isNull;
2978
2979 Assert(subkey->sk_flags & SK_ROW_MEMBER);
2980
2981 /* When a NULL row member is compared, the row never matches */
2982 if (subkey->sk_flags & SK_ISNULL)
2983 {
2984 /*
2985 * Unlike the simple-scankey case, this isn't a disallowed case
2986 * (except when it's the first row element that has the NULL arg).
2987 * But it can never match. If all the earlier row comparison
2988 * columns are required for the scan direction, we can stop the
2989 * scan, because there can't be another tuple that will succeed.
2990 */
2991 Assert(subkey != (ScanKey) DatumGetPointer(header->sk_argument));
2992 subkey--;
2993 if (forcenonrequired)
2994 {
2995 /* treating scan's keys as non-required */
2996 }
2997 else if ((subkey->sk_flags & SK_BT_REQFWD) &&
2998 ScanDirectionIsForward(dir))
2999 *continuescan = false;
3000 else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
3001 ScanDirectionIsBackward(dir))
3002 *continuescan = false;
3003 return false;
3004 }
3005
3006 if (subkey->sk_attno > tupnatts)
3007 {
3008 /*
3009 * This attribute is truncated (must be high key). The value for
3010 * this attribute in the first non-pivot tuple on the page to the
3011 * right could be any possible value. Assume that truncated
3012 * attribute passes the qual.
3013 */
3014 Assert(BTreeTupleIsPivot(tuple));
3015 return true;
3016 }
3017
3018 datum = index_getattr(tuple,
3019 subkey->sk_attno,
3020 tupdesc,
3021 &isNull);
3022
3023 if (isNull)
3024 {
3025 int reqflags;
3026
3027 if (forcenonrequired)
3028 {
3029 /* treating scan's keys as non-required */
3030 }
3031 else if (subkey->sk_flags & SK_BT_NULLS_FIRST)
3032 {
3033 /*
3034 * Since NULLs are sorted before non-NULLs, we know we have
3035 * reached the lower limit of the range of values for this
3036 * index attr. On a backward scan, we can stop if this qual
3037 * is one of the "must match" subset. However, on a forwards
3038 * scan, we must keep going, because we may have initially
3039 * positioned to the start of the index.
3040 *
3041 * All required NULLS FIRST > row members can use NULL tuple
3042 * values to end backwards scans, just like with other values.
3043 * A qual "WHERE (a, b, c) > (9, 42, 'foo')" can terminate a
3044 * backwards scan upon reaching the index's rightmost "a = 9"
3045 * tuple whose "b" column contains a NULL (if not sooner).
3046 * Since "b" is NULLS FIRST, we can treat its NULLs as "<" 42.
3047 */
3048 reqflags = SK_BT_REQBKWD;
3049
3050 /*
3051 * When a most significant required NULLS FIRST < row compare
3052 * member sees NULL tuple values during a backwards scan, it
3053 * signals the end of matches for the whole row compare/scan.
3054 * A qual "WHERE (a, b, c) < (9, 42, 'foo')" will terminate a
3055 * backwards scan upon reaching the rightmost tuple whose "a"
3056 * column has a NULL. The "a" NULL value is "<" 9, and yet
3057 * our < row compare will still end the scan. (This isn't
3058 * safe with later/lower-order row members. Notice that it
3059 * can only happen with an "a" NULL some time after the scan
3060 * completely stops needing to use its "b" and "c" members.)
3061 */
3062 if (subkey == (ScanKey) DatumGetPointer(header->sk_argument))
3063 reqflags |= SK_BT_REQFWD; /* safe, first row member */
3064
3065 if ((subkey->sk_flags & reqflags) &&
3066 ScanDirectionIsBackward(dir))
3067 *continuescan = false;
3068 }
3069 else
3070 {
3071 /*
3072 * Since NULLs are sorted after non-NULLs, we know we have
3073 * reached the upper limit of the range of values for this
3074 * index attr. On a forward scan, we can stop if this qual is
3075 * one of the "must match" subset. However, on a backward
3076 * scan, we must keep going, because we may have initially
3077 * positioned to the end of the index.
3078 *
3079 * All required NULLS LAST < row members can use NULL tuple
3080 * values to end forwards scans, just like with other values.
3081 * A qual "WHERE (a, b, c) < (9, 42, 'foo')" can terminate a
3082 * forwards scan upon reaching the index's leftmost "a = 9"
3083 * tuple whose "b" column contains a NULL (if not sooner).
3084 * Since "b" is NULLS LAST, we can treat its NULLs as ">" 42.
3085 */
3086 reqflags = SK_BT_REQFWD;
3087
3088 /*
3089 * When a most significant required NULLS LAST > row compare
3090 * member sees NULL tuple values during a forwards scan, it
3091 * signals the end of matches for the whole row compare/scan.
3092 * A qual "WHERE (a, b, c) > (9, 42, 'foo')" will terminate a
3093 * forwards scan upon reaching the leftmost tuple whose "a"
3094 * column has a NULL. The "a" NULL value is ">" 9, and yet
3095 * our > row compare will end the scan. (This isn't safe with
3096 * later/lower-order row members. Notice that it can only
3097 * happen with an "a" NULL some time after the scan completely
3098 * stops needing to use its "b" and "c" members.)
3099 */
3100 if (subkey == (ScanKey) DatumGetPointer(header->sk_argument))
3101 reqflags |= SK_BT_REQBKWD; /* safe, first row member */
3102
3103 if ((subkey->sk_flags & reqflags) &&
3104 ScanDirectionIsForward(dir))
3105 *continuescan = false;
3106 }
3107
3108 /*
3109 * In any case, this indextuple doesn't match the qual.
3110 */
3111 return false;
3112 }
3113
3114 /* Perform the test --- three-way comparison not bool operator */
3115 cmpresult = DatumGetInt32(FunctionCall2Coll(&subkey->sk_func,
3116 subkey->sk_collation,
3117 datum,
3118 subkey->sk_argument));
3119
3120 if (subkey->sk_flags & SK_BT_DESC)
3121 INVERT_COMPARE_RESULT(cmpresult);
3122
3123 /* Done comparing if unequal, else advance to next column */
3124 if (cmpresult != 0)
3125 break;
3126
3127 if (subkey->sk_flags & SK_ROW_END)
3128 break;
3129 subkey++;
3130 }
3131
3132 /*
3133 * At this point cmpresult indicates the overall result of the row
3134 * comparison, and subkey points to the deciding column (or the last
3135 * column if the result is "=").
3136 */
3137 switch (subkey->sk_strategy)
3138 {
3139 /* EQ and NE cases aren't allowed here */
3140 case BTLessStrategyNumber:
3141 result = (cmpresult < 0);
3142 break;
3143 case BTLessEqualStrategyNumber:
3144 result = (cmpresult <= 0);
3145 break;
3146 case BTGreaterEqualStrategyNumber:
3147 result = (cmpresult >= 0);
3148 break;
3149 case BTGreaterStrategyNumber:
3150 result = (cmpresult > 0);
3151 break;
3152 default:
3153 elog(ERROR, "unexpected strategy number %d", subkey->sk_strategy);
3154 result = 0; /* keep compiler quiet */
3155 break;
3156 }
3157
3158 if (!result && !forcenonrequired)
3159 {
3160 /*
3161 * Tuple fails this qual. If it's a required qual for the current
3162 * scan direction, then we can conclude no further tuples will pass,
3163 * either. Note we have to look at the deciding column, not
3164 * necessarily the first or last column of the row condition.
3165 */
3166 if ((subkey->sk_flags & SK_BT_REQFWD) &&
3167 ScanDirectionIsForward(dir))
3168 *continuescan = false;
3169 else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
3170 ScanDirectionIsBackward(dir))
3171 *continuescan = false;
3172 }
3173
3174 return result;
3175 }
3176
3177 /*
3178 * Determine if a scan with array keys should skip over uninteresting tuples.
3179 *
3180 * This is a subroutine for _bt_checkkeys. Called when _bt_readpage's linear
3181 * search process (started after it finishes reading an initial group of
3182 * matching tuples, used to locate the start of the next group of tuples
3183 * matching the next set of required array keys) has already scanned an
3184 * excessive number of tuples whose key space is "between arrays".
3185 *
3186 * When we perform look ahead successfully, we'll sets pstate.skip, which
3187 * instructs _bt_readpage to skip ahead to that tuple next (could be past the
3188 * end of the scan's leaf page). Pages where the optimization is effective
3189 * will generally still need to skip several times. Each call here performs
3190 * only a single "look ahead" comparison of a later tuple, whose distance from
3191 * the current tuple's offset number is determined by applying heuristics.
3192 */
3193 static void
3194 _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate,
3195 int tupnatts, TupleDesc tupdesc)
3196 {
3197 BTScanOpaque so = (BTScanOpaque) scan->opaque;
3198 ScanDirection dir = so->currPos.dir;
3199 OffsetNumber aheadoffnum;
3200 IndexTuple ahead;
3201
3202 Assert(!pstate->forcenonrequired);
3203
3204 /* Avoid looking ahead when comparing the page high key */
3205 if (pstate->offnum < pstate->minoff)
3206 return;
3207
3208 /*
3209 * Don't look ahead when there aren't enough tuples remaining on the page
3210 * (in the current scan direction) for it to be worth our while
3211 */
3212 if (ScanDirectionIsForward(dir) &&
3213 pstate->offnum >= pstate->maxoff - LOOK_AHEAD_DEFAULT_DISTANCE)
3214 return;
3215 else if (ScanDirectionIsBackward(dir) &&
3216 pstate->offnum <= pstate->minoff + LOOK_AHEAD_DEFAULT_DISTANCE)
3217 return;
3218
3219 /*
3220 * The look ahead distance starts small, and ramps up as each call here
3221 * allows _bt_readpage to skip over more tuples
3222 */
3223 if (!pstate->targetdistance)
3224 pstate->targetdistance = LOOK_AHEAD_DEFAULT_DISTANCE;
3225 else if (pstate->targetdistance < MaxIndexTuplesPerPage / 2)
3226 pstate->targetdistance *= 2;
3227
3228 /* Don't read past the end (or before the start) of the page, though */
3229 if (ScanDirectionIsForward(dir))
3230 aheadoffnum = Min((int) pstate->maxoff,
3231 (int) pstate->offnum + pstate->targetdistance);
3232 else
3233 aheadoffnum = Max((int) pstate->minoff,
3234 (int) pstate->offnum - pstate->targetdistance);
3235
3236 ahead = (IndexTuple) PageGetItem(pstate->page,
3237 PageGetItemId(pstate->page, aheadoffnum));
3238 if (_bt_tuple_before_array_skeys(scan, dir, ahead, tupdesc, tupnatts,
3239 false, 0, NULL))
3240 {
3241 /*
3242 * Success -- instruct _bt_readpage to skip ahead to very next tuple
3243 * after the one we determined was still before the current array keys
3244 */
3245 if (ScanDirectionIsForward(dir))
3246 pstate->skip = aheadoffnum + 1;
3247 else
3248 pstate->skip = aheadoffnum - 1;
3249 }
3250 else
3251 {
3252 /*
3253 * Failure -- "ahead" tuple is too far ahead (we were too aggressive).
3254 *
3255 * Reset the number of rechecks, and aggressively reduce the target
3256 * distance (we're much more aggressive here than we were when the
3257 * distance was initially ramped up).
3258 */
3259 pstate->rechecks = 0;
3260 pstate->targetdistance = Max(pstate->targetdistance / 8, 1);
3261 }
3262 }
3263
3264 /*
3265 * _bt_killitems - set LP_DEAD state for items an indexscan caller has
3266 * told us were killed
3267 *
3268 * scan->opaque, referenced locally through so, contains information about the
3269 * current page and killed tuples thereon (generally, this should only be
3270 * called if so->numKilled > 0).
3271 *
3272 * Caller should not have a lock on the so->currPos page, but must hold a
3273 * buffer pin when !so->dropPin. When we return, it still won't be locked.
3274 * It'll continue to hold whatever pins were held before calling here.
3275 *
3276 * We match items by heap TID before assuming they are the right ones to set
3277 * LP_DEAD. If the scan is one that holds a buffer pin on the target page
3278 * continuously from initially reading the items until applying this function
3279 * (if it is a !so->dropPin scan), VACUUM cannot have deleted any items on the
3280 * page, so the page's TIDs can't have been recycled by now. There's no risk
3281 * that we'll confuse a new index tuple that happens to use a recycled TID
3282 * with a now-removed tuple with the same TID (that used to be on this same
3283 * page). We can't rely on that during scans that drop buffer pins eagerly
3284 * (so->dropPin scans), though, so we must condition setting LP_DEAD bits on
3285 * the page LSN having not changed since back when _bt_readpage saw the page.
3286 * We totally give up on setting LP_DEAD bits when the page LSN changed.
3287 *
3288 * We give up much less often during !so->dropPin scans, but it still happens.
3289 * We cope with cases where items have moved right due to insertions. If an
3290 * item has moved off the current page due to a split, we'll fail to find it
3291 * and just give up on it.
3292 */
3293 void
3294 _bt_killitems(IndexScanDesc scan)
3295 {
3296 Relation rel = scan->indexRelation;
3297 BTScanOpaque so = (BTScanOpaque) scan->opaque;
3298 Page page;
3299 BTPageOpaque opaque;
3300 OffsetNumber minoff;
3301 OffsetNumber maxoff;
3302 int numKilled = so->numKilled;
3303 bool killedsomething = false;
3304 Buffer buf;
3305
3306 Assert(numKilled > 0);
3307 Assert(BTScanPosIsValid(so->currPos));
3308 Assert(scan->heapRelation != NULL); /* can't be a bitmap index scan */
3309
3310 /* Always invalidate so->killedItems[] before leaving so->currPos */
3311 so->numKilled = 0;
3312
3313 if (!so->dropPin)
3314 {
3315 /*
3316 * We have held the pin on this page since we read the index tuples,
3317 * so all we need to do is lock it. The pin will have prevented
3318 * concurrent VACUUMs from recycling any of the TIDs on the page.
3319 */
3320 Assert(BTScanPosIsPinned(so->currPos));
3321 buf = so->currPos.buf;
3322 _bt_lockbuf(rel, buf, BT_READ);
3323 }
3324 else
3325 {
3326 XLogRecPtr latestlsn;
3327
3328 Assert(!BTScanPosIsPinned(so->currPos));
3329 Assert(RelationNeedsWAL(rel));
3330 buf = _bt_getbuf(rel, so->currPos.currPage, BT_READ);
3331
3332 latestlsn = BufferGetLSNAtomic(buf);
3333 Assert(so->currPos.lsn <= latestlsn);
3334 if (so->currPos.lsn != latestlsn)
3335 {
3336 /* Modified, give up on hinting */
3337 _bt_relbuf(rel, buf);
3338 return;
3339 }
3340
3341 /* Unmodified, hinting is safe */
3342 }
3343
3344 page = BufferGetPage(buf);
3345 opaque = BTPageGetOpaque(page);
3346 minoff = P_FIRSTDATAKEY(opaque);
3347 maxoff = PageGetMaxOffsetNumber(page);
3348
3349 for (int i = 0; i < numKilled; i++)
3350 {
3351 int itemIndex = so->killedItems[i];
3352 BTScanPosItem *kitem = &so->currPos.items[itemIndex];
3353 OffsetNumber offnum = kitem->indexOffset;
3354
3355 Assert(itemIndex >= so->currPos.firstItem &&
3356 itemIndex <= so->currPos.lastItem);
3357 if (offnum < minoff)
3358 continue; /* pure paranoia */
3359 while (offnum <= maxoff)
3360 {
3361 ItemId iid = PageGetItemId(page, offnum);
3362 IndexTuple ituple = (IndexTuple) PageGetItem(page, iid);
3363 bool killtuple = false;
3364
3365 if (BTreeTupleIsPosting(ituple))
3366 {
3367 int pi = i + 1;
3368 int nposting = BTreeTupleGetNPosting(ituple);
3369 int j;
3370
3371 /*
3372 * We rely on the convention that heap TIDs in the scanpos
3373 * items array are stored in ascending heap TID order for a
3374 * group of TIDs that originally came from a posting list
3375 * tuple. This convention even applies during backwards
3376 * scans, where returning the TIDs in descending order might
3377 * seem more natural. This is about effectiveness, not
3378 * correctness.
3379 *
3380 * Note that the page may have been modified in almost any way
3381 * since we first read it (in the !so->dropPin case), so it's
3382 * possible that this posting list tuple wasn't a posting list
3383 * tuple when we first encountered its heap TIDs.
3384 */
3385 for (j = 0; j < nposting; j++)
3386 {
3387 ItemPointer item = BTreeTupleGetPostingN(ituple, j);
3388
3389 if (!ItemPointerEquals(item, &kitem->heapTid))
3390 break; /* out of posting list loop */
3391
3392 /*
3393 * kitem must have matching offnum when heap TIDs match,
3394 * though only in the common case where the page can't
3395 * have been concurrently modified
3396 */
3397 Assert(kitem->indexOffset == offnum || !so->dropPin);
3398
3399 /*
3400 * Read-ahead to later kitems here.
3401 *
3402 * We rely on the assumption that not advancing kitem here
3403 * will prevent us from considering the posting list tuple
3404 * fully dead by not matching its next heap TID in next
3405 * loop iteration.
3406 *
3407 * If, on the other hand, this is the final heap TID in
3408 * the posting list tuple, then tuple gets killed
3409 * regardless (i.e. we handle the case where the last
3410 * kitem is also the last heap TID in the last index tuple
3411 * correctly -- posting tuple still gets killed).
3412 */
3413 if (pi < numKilled)
3414 kitem = &so->currPos.items[so->killedItems[pi++]];
3415 }
3416
3417 /*
3418 * Don't bother advancing the outermost loop's int iterator to
3419 * avoid processing killed items that relate to the same
3420 * offnum/posting list tuple. This micro-optimization hardly
3421 * seems worth it. (Further iterations of the outermost loop
3422 * will fail to match on this same posting list's first heap
3423 * TID instead, so we'll advance to the next offnum/index
3424 * tuple pretty quickly.)
3425 */
3426 if (j == nposting)
3427 killtuple = true;
3428 }
3429 else if (ItemPointerEquals(&ituple->t_tid, &kitem->heapTid))
3430 killtuple = true;
3431
3432 /*
3433 * Mark index item as dead, if it isn't already. Since this
3434 * happens while holding a buffer lock possibly in shared mode,
3435 * it's possible that multiple processes attempt to do this
3436 * simultaneously, leading to multiple full-page images being sent
3437 * to WAL (if wal_log_hints or data checksums are enabled), which
3438 * is undesirable.
3439 */
3440 if (killtuple && !ItemIdIsDead(iid))
3441 {
3442 /* found the item/all posting list items */
3443 ItemIdMarkDead(iid);
3444 killedsomething = true;
3445 break; /* out of inner search loop */
3446 }
3447 offnum = OffsetNumberNext(offnum);
3448 }
3449 }
3450
3451 /*
3452 * Since this can be redone later if needed, mark as dirty hint.
3453 *
3454 * Whenever we mark anything LP_DEAD, we also set the page's
3455 * BTP_HAS_GARBAGE flag, which is likewise just a hint. (Note that we
3456 * only rely on the page-level flag in !heapkeyspace indexes.)
3457 */
3458 if (killedsomething)
3459 {
3460 opaque->btpo_flags |= BTP_HAS_GARBAGE;
3461 MarkBufferDirtyHint(buf, true);
3462 }
3463
3464 if (!so->dropPin)
3465 _bt_unlockbuf(rel, buf);
3466 else
3467 _bt_relbuf(rel, buf);
3468 }
3469
3470
3471 /*
3472 * The following routines manage a shared-memory area in which we track
3473 * assignment of "vacuum cycle IDs" to currently-active btree vacuuming
3474 * operations. There is a single counter which increments each time we
3475 * start a vacuum to assign it a cycle ID. Since multiple vacuums could
3476 * be active concurrently, we have to track the cycle ID for each active
3477 * vacuum; this requires at most MaxBackends entries (usually far fewer).
3478 * We assume at most one vacuum can be active for a given index.
3479 *
3480 * Access to the shared memory area is controlled by BtreeVacuumLock.
3481 * In principle we could use a separate lmgr locktag for each index,
3482 * but a single LWLock is much cheaper, and given the short time that
3483 * the lock is ever held, the concurrency hit should be minimal.
3484 */
3485
3486 typedef struct BTOneVacInfo
3487 {
3488 LockRelId relid; /* global identifier of an index */
3489 BTCycleId cycleid; /* cycle ID for its active VACUUM */
3490 } BTOneVacInfo;
3491
3492 typedef struct BTVacInfo
3493 {
3494 BTCycleId cycle_ctr; /* cycle ID most recently assigned */
3495 int num_vacuums; /* number of currently active VACUUMs */
3496 int max_vacuums; /* allocated length of vacuums[] array */
3497 BTOneVacInfo vacuums[FLEXIBLE_ARRAY_MEMBER];
3498 } BTVacInfo;
3499
3500 static BTVacInfo *btvacinfo;
3501
3502
3503 /*
3504 * _bt_vacuum_cycleid --- get the active vacuum cycle ID for an index,
3505 * or zero if there is no active VACUUM
3506 *
3507 * Note: for correct interlocking, the caller must already hold pin and
3508 * exclusive lock on each buffer it will store the cycle ID into. This
3509 * ensures that even if a VACUUM starts immediately afterwards, it cannot
3510 * process those pages until the page split is complete.
3511 */
3512 BTCycleId
3513 _bt_vacuum_cycleid(Relation rel)
3514 {
3515 BTCycleId result = 0;
3516 int i;
3517
3518 /* Share lock is enough since this is a read-only operation */
3519 LWLockAcquire(BtreeVacuumLock, LW_SHARED);
3520
3521 for (i = 0; i < btvacinfo->num_vacuums; i++)
3522 {
3523 BTOneVacInfo *vac = &btvacinfo->vacuums[i];
3524
3525 if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
3526 vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
3527 {
3528 result = vac->cycleid;
3529 break;
3530 }
3531 }
3532
3533 LWLockRelease(BtreeVacuumLock);
3534 return result;
3535 }
3536
3537 /*
3538 * _bt_start_vacuum --- assign a cycle ID to a just-starting VACUUM operation
3539 *
3540 * Note: the caller must guarantee that it will eventually call
3541 * _bt_end_vacuum, else we'll permanently leak an array slot. To ensure
3542 * that this happens even in elog(FATAL) scenarios, the appropriate coding
3543 * is not just a PG_TRY, but
3544 * PG_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel))
3545 */
3546 BTCycleId
3547 _bt_start_vacuum(Relation rel)
3548 {
3549 BTCycleId result;
3550 int i;
3551 BTOneVacInfo *vac;
3552
3553 LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
3554
3555 /*
3556 * Assign the next cycle ID, being careful to avoid zero as well as the
3557 * reserved high values.
3558 */
3559 result = ++(btvacinfo->cycle_ctr);
3560 if (result == 0 || result > MAX_BT_CYCLE_ID)
3561 result = btvacinfo->cycle_ctr = 1;
3562
3563 /* Let's just make sure there's no entry already for this index */
3564 for (i = 0; i < btvacinfo->num_vacuums; i++)
3565 {
3566 vac = &btvacinfo->vacuums[i];
3567 if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
3568 vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
3569 {
3570 /*
3571 * Unlike most places in the backend, we have to explicitly
3572 * release our LWLock before throwing an error. This is because
3573 * we expect _bt_end_vacuum() to be called before transaction
3574 * abort cleanup can run to release LWLocks.
3575 */
3576 LWLockRelease(BtreeVacuumLock);
3577 elog(ERROR, "multiple active vacuums for index \"%s\"",
3578 RelationGetRelationName(rel));
3579 }
3580 }
3581
3582 /* OK, add an entry */
3583 if (btvacinfo->num_vacuums >= btvacinfo->max_vacuums)
3584 {
3585 LWLockRelease(BtreeVacuumLock);
3586 elog(ERROR, "out of btvacinfo slots");
3587 }
3588 vac = &btvacinfo->vacuums[btvacinfo->num_vacuums];
3589 vac->relid = rel->rd_lockInfo.lockRelId;
3590 vac->cycleid = result;
3591 btvacinfo->num_vacuums++;
3592
3593 LWLockRelease(BtreeVacuumLock);
3594 return result;
3595 }
3596
3597 /*
3598 * _bt_end_vacuum --- mark a btree VACUUM operation as done
3599 *
3600 * Note: this is deliberately coded not to complain if no entry is found;
3601 * this allows the caller to put PG_TRY around the start_vacuum operation.
3602 */
3603 void
3604 _bt_end_vacuum(Relation rel)
3605 {
3606 int i;
3607
3608 LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
3609
3610 /* Find the array entry */
3611 for (i = 0; i < btvacinfo->num_vacuums; i++)
3612 {
3613 BTOneVacInfo *vac = &btvacinfo->vacuums[i];
3614
3615 if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
3616 vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
3617 {
3618 /* Remove it by shifting down the last entry */
3619 *vac = btvacinfo->vacuums[btvacinfo->num_vacuums - 1];
3620 btvacinfo->num_vacuums--;
3621 break;
3622 }
3623 }
3624
3625 LWLockRelease(BtreeVacuumLock);
3626 }
3627
3628 /*
3629 * _bt_end_vacuum wrapped as an on_shmem_exit callback function
3630 */
3631 void
3632 _bt_end_vacuum_callback(int code, Datum arg)
3633 {
3634 _bt_end_vacuum((Relation) DatumGetPointer(arg));
3635 }
3636
3637 /*
3638 * BTreeShmemSize --- report amount of shared memory space needed
3639 */
3640 Size
3641 BTreeShmemSize(void)
3642 {
3643 Size size;
3644
3645 size = offsetof(BTVacInfo, vacuums);
3646 size = add_size(size, mul_size(MaxBackends, sizeof(BTOneVacInfo)));
3647 return size;
3648 }
3649
3650 /*
3651 * BTreeShmemInit --- initialize this module's shared memory
3652 */
3653 void
3654 BTreeShmemInit(void)
3655 {
3656 bool found;
3657
3658 btvacinfo = (BTVacInfo *) ShmemInitStruct("BTree Vacuum State",
3659 BTreeShmemSize(),
3660 &found);
3661
3662 if (!IsUnderPostmaster)
3663 {
3664 /* Initialize shared memory area */
3665 Assert(!found);
3666
3667 /*
3668 * It doesn't really matter what the cycle counter starts at, but
3669 * having it always start the same doesn't seem good. Seed with
3670 * low-order bits of time() instead.
3671 */
3672 btvacinfo->cycle_ctr = (BTCycleId) time(NULL);
3673
3674 btvacinfo->num_vacuums = 0;
3675 btvacinfo->max_vacuums = MaxBackends;
3676 }
3677 else
3678 Assert(found);
3679 }
3680
3681 bytea *
3682 btoptions(Datum reloptions, bool validate)
3683 {
3684 static const relopt_parse_elt tab[] = {
3685 {"fillfactor", RELOPT_TYPE_INT, offsetof(BTOptions, fillfactor)},
3686 {"vacuum_cleanup_index_scale_factor", RELOPT_TYPE_REAL,
3687 offsetof(BTOptions, vacuum_cleanup_index_scale_factor)},
3688 {"deduplicate_items", RELOPT_TYPE_BOOL,
3689 offsetof(BTOptions, deduplicate_items)}
3690 };
3691
3692 return (bytea *) build_reloptions(reloptions, validate,
3693 RELOPT_KIND_BTREE,
3694 sizeof(BTOptions),
3695 tab, lengthof(tab));
3696 }
3697
3698 /*
3699 * btproperty() -- Check boolean properties of indexes.
3700 *
3701 * This is optional, but handling AMPROP_RETURNABLE here saves opening the rel
3702 * to call btcanreturn.
3703 */
3704 bool
3705 btproperty(Oid index_oid, int attno,
3706 IndexAMProperty prop, const char *propname,
3707 bool *res, bool *isnull)
3708 {
3709 switch (prop)
3710 {
3711 case AMPROP_RETURNABLE:
3712 /* answer only for columns, not AM or whole index */
3713 if (attno == 0)
3714 return false;
3715 /* otherwise, btree can always return data */
3716 *res = true;
3717 return true;
3718
3719 default:
3720 return false; /* punt to generic code */
3721 }
3722 }
3723
3724 /*
3725 * btbuildphasename() -- Return name of index build phase.
3726 */
3727 char *
3728 btbuildphasename(int64 phasenum)
3729 {
3730 switch (phasenum)
3731 {
3732 case PROGRESS_CREATEIDX_SUBPHASE_INITIALIZE:
3733 return "initializing";
3734 case PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN:
3735 return "scanning table";
3736 case PROGRESS_BTREE_PHASE_PERFORMSORT_1:
3737 return "sorting live tuples";
3738 case PROGRESS_BTREE_PHASE_PERFORMSORT_2:
3739 return "sorting dead tuples";
3740 case PROGRESS_BTREE_PHASE_LEAF_LOAD:
3741 return "loading tuples in tree";
3742 default:
3743 return NULL;
3744 }
3745 }
3746
3747 /*
3748 * _bt_truncate() -- create tuple without unneeded suffix attributes.
3749 *
3750 * Returns truncated pivot index tuple allocated in caller's memory context,
3751 * with key attributes copied from caller's firstright argument. If rel is
3752 * an INCLUDE index, non-key attributes will definitely be truncated away,
3753 * since they're not part of the key space. More aggressive suffix
3754 * truncation can take place when it's clear that the returned tuple does not
3755 * need one or more suffix key attributes. We only need to keep firstright
3756 * attributes up to and including the first non-lastleft-equal attribute.
3757 * Caller's insertion scankey is used to compare the tuples; the scankey's
3758 * argument values are not considered here.
3759 *
3760 * Note that returned tuple's t_tid offset will hold the number of attributes
3761 * present, so the original item pointer offset is not represented. Caller
3762 * should only change truncated tuple's downlink. Note also that truncated
3763 * key attributes are treated as containing "minus infinity" values by
3764 * _bt_compare().
3765 *
3766 * In the worst case (when a heap TID must be appended to distinguish lastleft
3767 * from firstright), the size of the returned tuple is the size of firstright
3768 * plus the size of an additional MAXALIGN()'d item pointer. This guarantee
3769 * is important, since callers need to stay under the 1/3 of a page
3770 * restriction on tuple size. If this routine is ever taught to truncate
3771 * within an attribute/datum, it will need to avoid returning an enlarged
3772 * tuple to caller when truncation + TOAST compression ends up enlarging the
3773 * final datum.
3774 */
3775 IndexTuple
3776 _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
3777 BTScanInsert itup_key)
3778 {
3779 TupleDesc itupdesc = RelationGetDescr(rel);
3780 int16 nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
3781 int keepnatts;
3782 IndexTuple pivot;
3783 IndexTuple tidpivot;
3784 ItemPointer pivotheaptid;
3785 Size newsize;
3786
3787 /*
3788 * We should only ever truncate non-pivot tuples from leaf pages. It's
3789 * never okay to truncate when splitting an internal page.
3790 */
3791 Assert(!BTreeTupleIsPivot(lastleft) && !BTreeTupleIsPivot(firstright));
3792
3793 /* Determine how many attributes must be kept in truncated tuple */
3794 keepnatts = _bt_keep_natts(rel, lastleft, firstright, itup_key);
3795
3796 #ifdef DEBUG_NO_TRUNCATE
3797 /* Force truncation to be ineffective for testing purposes */
3798 keepnatts = nkeyatts + 1;
3799 #endif
3800
3801 pivot = index_truncate_tuple(itupdesc, firstright,
3802 Min(keepnatts, nkeyatts));
3803
3804 if (BTreeTupleIsPosting(pivot))
3805 {
3806 /*
3807 * index_truncate_tuple() just returns a straight copy of firstright
3808 * when it has no attributes to truncate. When that happens, we may
3809 * need to truncate away a posting list here instead.
3810 */
3811 Assert(keepnatts == nkeyatts || keepnatts == nkeyatts + 1);
3812 Assert(IndexRelationGetNumberOfAttributes(rel) == nkeyatts);
3813 pivot->t_info &= ~INDEX_SIZE_MASK;
3814 pivot->t_info |= MAXALIGN(BTreeTupleGetPostingOffset(firstright));
3815 }
3816
3817 /*
3818 * If there is a distinguishing key attribute within pivot tuple, we're
3819 * done
3820 */
3821 if (keepnatts <= nkeyatts)
3822 {
3823 BTreeTupleSetNAtts(pivot, keepnatts, false);
3824 return pivot;
3825 }
3826
3827 /*
3828 * We have to store a heap TID in the new pivot tuple, since no non-TID
3829 * key attribute value in firstright distinguishes the right side of the
3830 * split from the left side. nbtree conceptualizes this case as an
3831 * inability to truncate away any key attributes, since heap TID is
3832 * treated as just another key attribute (despite lacking a pg_attribute
3833 * entry).
3834 *
3835 * Use enlarged space that holds a copy of pivot. We need the extra space
3836 * to store a heap TID at the end (using the special pivot tuple
3837 * representation). Note that the original pivot already has firstright's
3838 * possible posting list/non-key attribute values removed at this point.
3839 */
3840 newsize = MAXALIGN(IndexTupleSize(pivot)) + MAXALIGN(sizeof(ItemPointerData));
3841 tidpivot = palloc0(newsize);
3842 memcpy(tidpivot, pivot, MAXALIGN(IndexTupleSize(pivot)));
3843 /* Cannot leak memory here */
3844 pfree(pivot);
3845
3846 /*
3847 * Store all of firstright's key attribute values plus a tiebreaker heap
3848 * TID value in enlarged pivot tuple
3849 */
3850 tidpivot->t_info &= ~INDEX_SIZE_MASK;
3851 tidpivot->t_info |= newsize;
3852 BTreeTupleSetNAtts(tidpivot, nkeyatts, true);
3853 pivotheaptid = BTreeTupleGetHeapTID(tidpivot);
3854
3855 /*
3856 * Lehman & Yao use lastleft as the leaf high key in all cases, but don't
3857 * consider suffix truncation. It seems like a good idea to follow that
3858 * example in cases where no truncation takes place -- use lastleft's heap
3859 * TID. (This is also the closest value to negative infinity that's
3860 * legally usable.)
3861 */
3862 ItemPointerCopy(BTreeTupleGetMaxHeapTID(lastleft), pivotheaptid);
3863
3864 /*
3865 * We're done. Assert() that heap TID invariants hold before returning.
3866 *
3867 * Lehman and Yao require that the downlink to the right page, which is to
3868 * be inserted into the parent page in the second phase of a page split be
3869 * a strict lower bound on items on the right page, and a non-strict upper
3870 * bound for items on the left page. Assert that heap TIDs follow these
3871 * invariants, since a heap TID value is apparently needed as a
3872 * tiebreaker.
3873 */
3874 #ifndef DEBUG_NO_TRUNCATE
3875 Assert(ItemPointerCompare(BTreeTupleGetMaxHeapTID(lastleft),
3876 BTreeTupleGetHeapTID(firstright)) < 0);
3877 Assert(ItemPointerCompare(pivotheaptid,
3878 BTreeTupleGetHeapTID(lastleft)) >= 0);
3879 Assert(ItemPointerCompare(pivotheaptid,
3880 BTreeTupleGetHeapTID(firstright)) < 0);
3881 #else
3882
3883 /*
3884 * Those invariants aren't guaranteed to hold for lastleft + firstright
3885 * heap TID attribute values when they're considered here only because
3886 * DEBUG_NO_TRUNCATE is defined (a heap TID is probably not actually
3887 * needed as a tiebreaker). DEBUG_NO_TRUNCATE must therefore use a heap
3888 * TID value that always works as a strict lower bound for items to the
3889 * right. In particular, it must avoid using firstright's leading key
3890 * attribute values along with lastleft's heap TID value when lastleft's
3891 * TID happens to be greater than firstright's TID.
3892 */
3893 ItemPointerCopy(BTreeTupleGetHeapTID(firstright), pivotheaptid);
3894
3895 /*
3896 * Pivot heap TID should never be fully equal to firstright. Note that
3897 * the pivot heap TID will still end up equal to lastleft's heap TID when
3898 * that's the only usable value.
3899 */
3900 ItemPointerSetOffsetNumber(pivotheaptid,
3901 OffsetNumberPrev(ItemPointerGetOffsetNumber(pivotheaptid)));
3902 Assert(ItemPointerCompare(pivotheaptid,
3903 BTreeTupleGetHeapTID(firstright)) < 0);
3904 #endif
3905
3906 return tidpivot;
3907 }
3908
3909 /*
3910 * _bt_keep_natts - how many key attributes to keep when truncating.
3911 *
3912 * Caller provides two tuples that enclose a split point. Caller's insertion
3913 * scankey is used to compare the tuples; the scankey's argument values are
3914 * not considered here.
3915 *
3916 * This can return a number of attributes that is one greater than the
3917 * number of key attributes for the index relation. This indicates that the
3918 * caller must use a heap TID as a unique-ifier in new pivot tuple.
3919 */
3920 static int
3921 _bt_keep_natts(Relation rel, IndexTuple lastleft, IndexTuple firstright,
3922 BTScanInsert itup_key)
3923 {
3924 int nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
3925 TupleDesc itupdesc = RelationGetDescr(rel);
3926 int keepnatts;
3927 ScanKey scankey;
3928
3929 /*
3930 * _bt_compare() treats truncated key attributes as having the value minus
3931 * infinity, which would break searches within !heapkeyspace indexes. We
3932 * must still truncate away non-key attribute values, though.
3933 */
3934 if (!itup_key->heapkeyspace)
3935 return nkeyatts;
3936
3937 scankey = itup_key->scankeys;
3938 keepnatts = 1;
3939 for (int attnum = 1; attnum <= nkeyatts; attnum++, scankey++)
3940 {
3941 Datum datum1,
3942 datum2;
3943 bool isNull1,
3944 isNull2;
3945
3946 datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
3947 datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
3948
3949 if (isNull1 != isNull2)
3950 break;
3951
3952 if (!isNull1 &&
3953 DatumGetInt32(FunctionCall2Coll(&scankey->sk_func,
3954 scankey->sk_collation,
3955 datum1,
3956 datum2)) != 0)
3957 break;
3958
3959 keepnatts++;
3960 }
3961
3962 /*
3963 * Assert that _bt_keep_natts_fast() agrees with us in passing. This is
3964 * expected in an allequalimage index.
3965 */
3966 Assert(!itup_key->allequalimage ||
3967 keepnatts == _bt_keep_natts_fast(rel, lastleft, firstright));
3968
3969 return keepnatts;
3970 }
3971
3972 /*
3973 * _bt_keep_natts_fast - fast bitwise variant of _bt_keep_natts.
3974 *
3975 * This is exported so that a candidate split point can have its effect on
3976 * suffix truncation inexpensively evaluated ahead of time when finding a
3977 * split location. A naive bitwise approach to datum comparisons is used to
3978 * save cycles.
3979 *
3980 * The approach taken here usually provides the same answer as _bt_keep_natts
3981 * will (for the same pair of tuples from a heapkeyspace index), since the
3982 * majority of btree opclasses can never indicate that two datums are equal
3983 * unless they're bitwise equal after detoasting. When an index only has
3984 * "equal image" columns, routine is guaranteed to give the same result as
3985 * _bt_keep_natts would.
3986 *
3987 * Callers can rely on the fact that attributes considered equal here are
3988 * definitely also equal according to _bt_keep_natts, even when the index uses
3989 * an opclass or collation that is not "allequalimage"/deduplication-safe.
3990 * This weaker guarantee is good enough for nbtsplitloc.c caller, since false
3991 * negatives generally only have the effect of making leaf page splits use a
3992 * more balanced split point.
3993 */
3994 int
3995 _bt_keep_natts_fast(Relation rel, IndexTuple lastleft, IndexTuple firstright)
3996 {
3997 TupleDesc itupdesc = RelationGetDescr(rel);
3998 int keysz = IndexRelationGetNumberOfKeyAttributes(rel);
3999 int keepnatts;
4000
4001 keepnatts = 1;
4002 for (int attnum = 1; attnum <= keysz; attnum++)
4003 {
4004 Datum datum1,
4005 datum2;
4006 bool isNull1,
4007 isNull2;
4008 CompactAttribute *att;
4009
4010 datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
4011 datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
4012 att = TupleDescCompactAttr(itupdesc, attnum - 1);
4013
4014 if (isNull1 != isNull2)
4015 break;
4016
4017 if (!isNull1 &&
4018 !datum_image_eq(datum1, datum2, att->attbyval, att->attlen))
4019 break;
4020
4021 keepnatts++;
4022 }
4023
4024 return keepnatts;
4025 }
4026
4027 /*
4028 * _bt_check_natts() -- Verify tuple has expected number of attributes.
4029 *
4030 * Returns value indicating if the expected number of attributes were found
4031 * for a particular offset on page. This can be used as a general purpose
4032 * sanity check.
4033 *
4034 * Testing a tuple directly with BTreeTupleGetNAtts() should generally be
4035 * preferred to calling here. That's usually more convenient, and is always
4036 * more explicit. Call here instead when offnum's tuple may be a negative
4037 * infinity tuple that uses the pre-v11 on-disk representation, or when a low
4038 * context check is appropriate. This routine is as strict as possible about
4039 * what is expected on each version of btree.
4040 */
4041 bool
4042 _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
4043 {
4044 int16 natts = IndexRelationGetNumberOfAttributes(rel);
4045 int16 nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
4046 BTPageOpaque opaque = BTPageGetOpaque(page);
4047 IndexTuple itup;
4048 int tupnatts;
4049
4050 /*
4051 * We cannot reliably test a deleted or half-dead page, since they have
4052 * dummy high keys
4053 */
4054 if (P_IGNORE(opaque))
4055 return true;
4056
4057 Assert(offnum >= FirstOffsetNumber &&
4058 offnum <= PageGetMaxOffsetNumber(page));
4059
4060 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
4061 tupnatts = BTreeTupleGetNAtts(itup, rel);
4062
4063 /* !heapkeyspace indexes do not support deduplication */
4064 if (!heapkeyspace && BTreeTupleIsPosting(itup))
4065 return false;
4066
4067 /* Posting list tuples should never have "pivot heap TID" bit set */
4068 if (BTreeTupleIsPosting(itup) &&
4069 (ItemPointerGetOffsetNumberNoCheck(&itup->t_tid) &
4070 BT_PIVOT_HEAP_TID_ATTR) != 0)
4071 return false;
4072
4073 /* INCLUDE indexes do not support deduplication */
4074 if (natts != nkeyatts && BTreeTupleIsPosting(itup))
4075 return false;
4076
4077 if (P_ISLEAF(opaque))
4078 {
4079 if (offnum >= P_FIRSTDATAKEY(opaque))
4080 {
4081 /*
4082 * Non-pivot tuple should never be explicitly marked as a pivot
4083 * tuple
4084 */
4085 if (BTreeTupleIsPivot(itup))
4086 return false;
4087
4088 /*
4089 * Leaf tuples that are not the page high key (non-pivot tuples)
4090 * should never be truncated. (Note that tupnatts must have been
4091 * inferred, even with a posting list tuple, because only pivot
4092 * tuples store tupnatts directly.)
4093 */
4094 return tupnatts == natts;
4095 }
4096 else
4097 {
4098 /*
4099 * Rightmost page doesn't contain a page high key, so tuple was
4100 * checked above as ordinary leaf tuple
4101 */
4102 Assert(!P_RIGHTMOST(opaque));
4103
4104 /*
4105 * !heapkeyspace high key tuple contains only key attributes. Note
4106 * that tupnatts will only have been explicitly represented in
4107 * !heapkeyspace indexes that happen to have non-key attributes.
4108 */
4109 if (!heapkeyspace)
4110 return tupnatts == nkeyatts;
4111
4112 /* Use generic heapkeyspace pivot tuple handling */
4113 }
4114 }
4115 else /* !P_ISLEAF(opaque) */
4116 {
4117 if (offnum == P_FIRSTDATAKEY(opaque))
4118 {
4119 /*
4120 * The first tuple on any internal page (possibly the first after
4121 * its high key) is its negative infinity tuple. Negative
4122 * infinity tuples are always truncated to zero attributes. They
4123 * are a particular kind of pivot tuple.
4124 */
4125 if (heapkeyspace)
4126 return tupnatts == 0;
4127
4128 /*
4129 * The number of attributes won't be explicitly represented if the
4130 * negative infinity tuple was generated during a page split that
4131 * occurred with a version of Postgres before v11. There must be
4132 * a problem when there is an explicit representation that is
4133 * non-zero, or when there is no explicit representation and the
4134 * tuple is evidently not a pre-pg_upgrade tuple.
4135 *
4136 * Prior to v11, downlinks always had P_HIKEY as their offset.
4137 * Accept that as an alternative indication of a valid
4138 * !heapkeyspace negative infinity tuple.
4139 */
4140 return tupnatts == 0 ||
4141 ItemPointerGetOffsetNumber(&(itup->t_tid)) == P_HIKEY;
4142 }
4143 else
4144 {
4145 /*
4146 * !heapkeyspace downlink tuple with separator key contains only
4147 * key attributes. Note that tupnatts will only have been
4148 * explicitly represented in !heapkeyspace indexes that happen to
4149 * have non-key attributes.
4150 */
4151 if (!heapkeyspace)
4152 return tupnatts == nkeyatts;
4153
4154 /* Use generic heapkeyspace pivot tuple handling */
4155 }
4156 }
4157
4158 /* Handle heapkeyspace pivot tuples (excluding minus infinity items) */
4159 Assert(heapkeyspace);
4160
4161 /*
4162 * Explicit representation of the number of attributes is mandatory with
4163 * heapkeyspace index pivot tuples, regardless of whether or not there are
4164 * non-key attributes.
4165 */
4166 if (!BTreeTupleIsPivot(itup))
4167 return false;
4168
4169 /* Pivot tuple should not use posting list representation (redundant) */
4170 if (BTreeTupleIsPosting(itup))
4171 return false;
4172
4173 /*
4174 * Heap TID is a tiebreaker key attribute, so it cannot be untruncated
4175 * when any other key attribute is truncated
4176 */
4177 if (BTreeTupleGetHeapTID(itup) != NULL && tupnatts != nkeyatts)
4178 return false;
4179
4180 /*
4181 * Pivot tuple must have at least one untruncated key attribute (minus
4182 * infinity pivot tuples are the only exception). Pivot tuples can never
4183 * represent that there is a value present for a key attribute that
4184 * exceeds pg_index.indnkeyatts for the index.
4185 */
4186 return tupnatts > 0 && tupnatts <= nkeyatts;
4187 }
4188
4189 /*
4190 *
4191 * _bt_check_third_page() -- check whether tuple fits on a btree page at all.
4192 *
4193 * We actually need to be able to fit three items on every page, so restrict
4194 * any one item to 1/3 the per-page available space. Note that itemsz should
4195 * not include the ItemId overhead.
4196 *
4197 * It might be useful to apply TOAST methods rather than throw an error here.
4198 * Using out of line storage would break assumptions made by suffix truncation
4199 * and by contrib/amcheck, though.
4200 */
4201 void
4202 _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace,
4203 Page page, IndexTuple newtup)
4204 {
4205 Size itemsz;
4206 BTPageOpaque opaque;
4207
4208 itemsz = MAXALIGN(IndexTupleSize(newtup));
4209
4210 /* Double check item size against limit */
4211 if (itemsz <= BTMaxItemSize)
4212 return;
4213
4214 /*
4215 * Tuple is probably too large to fit on page, but it's possible that the
4216 * index uses version 2 or version 3, or that page is an internal page, in
4217 * which case a slightly higher limit applies.
4218 */
4219 if (!needheaptidspace && itemsz <= BTMaxItemSizeNoHeapTid)
4220 return;
4221
4222 /*
4223 * Internal page insertions cannot fail here, because that would mean that
4224 * an earlier leaf level insertion that should have failed didn't
4225 */
4226 opaque = BTPageGetOpaque(page);
4227 if (!P_ISLEAF(opaque))
4228 elog(ERROR, "cannot insert oversized tuple of size %zu on internal page of index \"%s\"",
4229 itemsz, RelationGetRelationName(rel));
4230
4231 ereport(ERROR,
4232 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
4233 errmsg("index row size %zu exceeds btree version %u maximum %zu for index \"%s\"",
4234 itemsz,
4235 needheaptidspace ? BTREE_VERSION : BTREE_NOVAC_VERSION,
4236 needheaptidspace ? BTMaxItemSize : BTMaxItemSizeNoHeapTid,
4237 RelationGetRelationName(rel)),
4238 errdetail("Index row references tuple (%u,%u) in relation \"%s\".",
4239 ItemPointerGetBlockNumber(BTreeTupleGetHeapTID(newtup)),
4240 ItemPointerGetOffsetNumber(BTreeTupleGetHeapTID(newtup)),
4241 RelationGetRelationName(heap)),
4242 errhint("Values larger than 1/3 of a buffer page cannot be indexed.\n"
4243 "Consider a function index of an MD5 hash of the value, "
4244 "or use full text indexing."),
4245 errtableconstraint(heap, RelationGetRelationName(rel))));
4246 }
4247
4248 /*
4249 * Are all attributes in rel "equality is image equality" attributes?
4250 *
4251 * We use each attribute's BTEQUALIMAGE_PROC opclass procedure. If any
4252 * opclass either lacks a BTEQUALIMAGE_PROC procedure or returns false, we
4253 * return false; otherwise we return true.
4254 *
4255 * Returned boolean value is stored in index metapage during index builds.
4256 * Deduplication can only be used when we return true.
4257 */
4258 bool
4259 _bt_allequalimage(Relation rel, bool debugmessage)
4260 {
4261 bool allequalimage = true;
4262
4263 /* INCLUDE indexes can never support deduplication */
4264 if (IndexRelationGetNumberOfAttributes(rel) !=
4265 IndexRelationGetNumberOfKeyAttributes(rel))
4266 return false;
4267
4268 for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(rel); i++)
4269 {
4270 Oid opfamily = rel->rd_opfamily[i];
4271 Oid opcintype = rel->rd_opcintype[i];
4272 Oid collation = rel->rd_indcollation[i];
4273 Oid equalimageproc;
4274
4275 equalimageproc = get_opfamily_proc(opfamily, opcintype, opcintype,
4276 BTEQUALIMAGE_PROC);
4277
4278 /*
4279 * If there is no BTEQUALIMAGE_PROC then deduplication is assumed to
4280 * be unsafe. Otherwise, actually call proc and see what it says.
4281 */
4282 if (!OidIsValid(equalimageproc) ||
4283 !DatumGetBool(OidFunctionCall1Coll(equalimageproc, collation,
4284 ObjectIdGetDatum(opcintype))))
4285 {
4286 allequalimage = false;
4287 break;
4288 }
4289 }
4290
4291 if (debugmessage)
4292 {
4293 if (allequalimage)
4294 elog(DEBUG1, "index \"%s\" can safely use deduplication",
4295 RelationGetRelationName(rel));
4296 else
4297 elog(DEBUG1, "index \"%s\" cannot use deduplication",
4298 RelationGetRelationName(rel));
4299 }
4300
4301 return allequalimage;
4302 }