Debian Codegraph @

src/backend/access/nbtree/nbtpreprocesskeys.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * nbtpreprocesskeys.c
4 * Preprocessing for Postgres btree scan keys.
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/nbtpreprocesskeys.c
12 *
13 *-------------------------------------------------------------------------
14 */
15
16 #include "postgres.h"
17
18 #include "access/nbtree.h"
19 #include "common/int.h"
20 #include "lib/qunique.h"
21 #include "utils/array.h"
22 #include "utils/lsyscache.h"
23 #include "utils/memutils.h"
24
25 typedef struct BTScanKeyPreproc
26 {
27 ScanKey inkey;
28 int inkeyi;
29 int arrayidx;
30 } BTScanKeyPreproc;
31
32 typedef struct BTSortArrayContext
33 {
34 FmgrInfo *sortproc;
35 Oid collation;
36 bool reverse;
37 } BTSortArrayContext;
38
39 static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption);
40 static void _bt_mark_scankey_required(ScanKey skey);
41 static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
42 ScanKey leftarg, ScanKey rightarg,
43 BTArrayKeyInfo *array, FmgrInfo *orderproc,
44 bool *result);
45 static bool _bt_compare_array_scankey_args(IndexScanDesc scan,
46 ScanKey arraysk, ScanKey skey,
47 FmgrInfo *orderproc, BTArrayKeyInfo *array,
48 bool *qual_ok);
49 static bool _bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk,
50 ScanKey skey, FmgrInfo *orderproc,
51 BTArrayKeyInfo *array, bool *qual_ok);
52 static bool _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey,
53 BTArrayKeyInfo *array, bool *qual_ok);
54 static void _bt_skiparray_strat_adjust(IndexScanDesc scan, ScanKey arraysk,
55 BTArrayKeyInfo *array);
56 static void _bt_skiparray_strat_decrement(IndexScanDesc scan, ScanKey arraysk,
57 BTArrayKeyInfo *array);
58 static void _bt_skiparray_strat_increment(IndexScanDesc scan, ScanKey arraysk,
59 BTArrayKeyInfo *array);
60 static void _bt_unmark_keys(IndexScanDesc scan, int *keyDataMap);
61 static int _bt_reorder_array_cmp(const void *a, const void *b);
62 static ScanKey _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys);
63 static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap);
64 static int _bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out,
65 int *numSkipArrayKeys_out);
66 static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey,
67 Oid elemtype, StrategyNumber strat,
68 Datum *elems, int nelems);
69 static void _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype,
70 FmgrInfo *orderproc, FmgrInfo **sortprocp);
71 static int _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc,
72 bool reverse, Datum *elems, int nelems);
73 static bool _bt_merge_arrays(IndexScanDesc scan, ScanKey skey,
74 FmgrInfo *sortproc, bool reverse,
75 Oid origelemtype, Oid nextelemtype,
76 Datum *elems_orig, int *nelems_orig,
77 Datum *elems_next, int nelems_next);
78 static int _bt_compare_array_elements(const void *a, const void *b, void *arg);
79
80
81 /*
82 * _bt_preprocess_keys() -- Preprocess scan keys
83 *
84 * The given search-type keys (taken from scan->keyData[])
85 * are copied to so->keyData[] with possible transformation.
86 * scan->numberOfKeys is the number of input keys, so->numberOfKeys gets
87 * the number of output keys. Calling here a second or subsequent time
88 * (during the same btrescan) is a no-op.
89 *
90 * The output keys are marked with additional sk_flags bits beyond the
91 * system-standard bits supplied by the caller. The DESC and NULLS_FIRST
92 * indoption bits for the relevant index attribute are copied into the flags.
93 * Also, for a DESC column, we commute (flip) all the sk_strategy numbers
94 * so that the index sorts in the desired direction.
95 *
96 * One key purpose of this routine is to discover which scan keys must be
97 * satisfied to continue the scan. It also attempts to eliminate redundant
98 * keys and detect contradictory keys. (If the index opfamily provides
99 * incomplete sets of cross-type operators, we may fail to detect redundant
100 * or contradictory keys, but we can survive that.)
101 *
102 * Required output keys are sorted by index attribute. Presently we expect
103 * (but verify) that the input keys are already so sorted --- this is done
104 * by match_clauses_to_index() in indxpath.c. Some reordering of the keys
105 * within each attribute may be done as a byproduct of the processing here.
106 * That process must leave array scan keys (within an attribute) in the same
107 * order as corresponding entries from the scan's BTArrayKeyInfo array info.
108 * We might also construct skip array scan keys that weren't present in the
109 * original input keys; these are also output in standard attribute order.
110 *
111 * The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD
112 * if they must be satisfied in order to continue the scan forward or backward
113 * respectively. _bt_checkkeys uses these flags. For example, if the quals
114 * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
115 * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
116 * But once we reach tuples like (1,4,z) we can stop scanning because no
117 * later tuples could match. This is reflected by marking the x and y keys,
118 * but not the z key, with SK_BT_REQFWD. In general, the keys for leading
119 * attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD.
120 * For the first attribute without an "=" key, any "<" and "<=" keys are
121 * marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD.
122 * This can be seen to be correct by considering the above example.
123 * (Actually, the z key _will_ be marked SK_BT_REQFWD, since preprocessing
124 * will generate a skip array on y -- except when DEBUG_DISABLE_SKIP_SCAN.
125 * See below description of how and why we generate skip array = keys in the
126 * presence of a "contradictory" condition such as "y < 4".)
127 *
128 * If we never generated skip array scan keys, it would be possible for "gaps"
129 * to appear that make it unsafe to mark any subsequent input scan keys
130 * (copied from scan->keyData[]) as required to continue the scan. Prior to
131 * Postgres 18, a qual like "WHERE y = 4" always resulted in a full scan.
132 * This qual now becomes "WHERE x = ANY('{every possible x value}') and y = 4"
133 * on output. In other words, preprocessing now adds a skip array on "x".
134 * This has the potential to be much more efficient than a full index scan
135 * (though it behaves like a full scan when there's many distinct "x" values).
136 *
137 * Typically, redundant keys are eliminated: we keep only the tightest
138 * >/>= bound and the tightest </<= bound, and if there's an = key then
139 * that's the only one returned. (So, we return either a single = key,
140 * or one or two boundary-condition keys for each attr.) However, if we
141 * cannot compare two keys for lack of a suitable cross-type operator,
142 * we cannot eliminate either key.
143 *
144 * When all redundant keys could not be eliminated, we'll output a key array
145 * that can more or less be treated as if it had no redundant keys. Suppose
146 * we have "x > 4::int AND x > 10::bigint AND x < 70", and we are unable to
147 * determine which > key is more restrictive for lack of a suitable cross-type
148 * operator. We'll arbitrarily pick one of the > keys; the other > key won't
149 * be marked required. Obviously, the scan will be less efficient if we
150 * choose x > 4 over x > 10 -- but it can still largely proceed as if there
151 * was only a single > condition. "x > 10" will be placed at the end of the
152 * so->keyData[] output array. It'll always be evaluated last, after the keys
153 * that could be marked required in the usual way (after "x > 4 AND x < 70").
154 * This can sometimes result in so->keyData[] keys that aren't even in index
155 * attribute order (if the qual involves multiple attributes). The scan's
156 * required keys will still be in attribute order, though, so it can't matter.
157 *
158 * This scheme ensures that _bt_first always uses the same set of keys at the
159 * start of a forwards scan as those _bt_checkkeys uses to determine when to
160 * end a similar backwards scan (and vice-versa). _bt_advance_array_keys
161 * depends on this: it expects to be able to reliably predict what the next
162 * _bt_first call will do by testing whether _bt_checkkeys' routines report
163 * that the final tuple on the page is past the end of matches for the scan's
164 * keys with the scan direction flipped. If it is (if continuescan=false),
165 * then it follows that calling _bt_first will, at a minimum, relocate the
166 * scan to the very next leaf page (in the current scan direction).
167 *
168 * As a byproduct of this work, we can detect contradictory quals such
169 * as "x = 1 AND x > 2". If we see that, we return so->qual_ok = false,
170 * indicating the scan need not be run at all since no tuples can match.
171 * (In this case we do not bother completing the output key array!)
172 * Again, missing cross-type operators might cause us to fail to prove the
173 * quals contradictory when they really are, but the scan will work correctly.
174 *
175 * Skip array = keys will even be generated in the presence of "contradictory"
176 * inequality quals when it'll enable marking later input quals as required.
177 * We'll merge any such inequalities into the generated skip array by setting
178 * its array.low_compare or array.high_compare key field. The resulting skip
179 * array will generate its array elements from a range that's constrained by
180 * any merged input inequalities (which won't get output in so->keyData[]).
181 *
182 * Row compares are treated as ordinary inequality comparisons on the row's
183 * first index column whenever possible. We treat their first subkey as if it
184 * was a simple scalar inequality for the purposes of the logic about required
185 * keys. This also gives us limited ability to detect contradictory/redundant
186 * conditions involving a row compare: we can do so whenever it involves an
187 * SK_ISNULL condition on a row compare's first column (the same rules used
188 * with simple inequalities work just as well here). We have no ability to
189 * detect redundant/contradictory conditions in any other row compare case.
190 * Note in particular that we are unable to merge a row comparison key into a
191 * skip array (only ordinary inequalities are merged). Any so->keyData[] key
192 * on a column that comes after a row comparison's first column can therefore
193 * never be marked as required at present.
194 *
195 * Note: the reason we have to copy the preprocessed scan keys into private
196 * storage is that we are modifying the array based on comparisons of the
197 * key argument values, which could change on a rescan. Therefore we can't
198 * overwrite the source data.
199 */
200 void
201 _bt_preprocess_keys(IndexScanDesc scan)
202 {
203 BTScanOpaque so = (BTScanOpaque) scan->opaque;
204 int numberOfKeys = scan->numberOfKeys;
205 int16 *indoption = scan->indexRelation->rd_indoption;
206 int new_numberOfKeys;
207 int numberOfEqualCols;
208 ScanKey inkeys;
209 BTScanKeyPreproc xform[BTMaxStrategyNumber];
210 bool test_result,
211 redundant_key_kept = false;
212 AttrNumber attno;
213 ScanKey arrayKeyData;
214 int *keyDataMap = NULL;
215 int arrayidx = 0;
216
217 if (so->numberOfKeys > 0)
218 {
219 /*
220 * Only need to do preprocessing once per btrescan, at most. All
221 * calls after the first are handled as no-ops.
222 */
223 return;
224 }
225
226 /* initialize result variables */
227 so->qual_ok = true;
228 so->numberOfKeys = 0;
229
230 if (numberOfKeys < 1)
231 return; /* done if qual-less scan */
232
233 /* If any keys are SK_SEARCHARRAY type, set up array-key info */
234 arrayKeyData = _bt_preprocess_array_keys(scan, &numberOfKeys);
235 if (!so->qual_ok)
236 {
237 /* unmatchable array, so give up */
238 return;
239 }
240
241 /*
242 * Treat arrayKeyData[] (a partially preprocessed copy of scan->keyData[])
243 * as our input if _bt_preprocess_array_keys just allocated it, else just
244 * use scan->keyData[]
245 */
246 if (arrayKeyData)
247 {
248 inkeys = arrayKeyData;
249
250 /* Also maintain keyDataMap for remapping so->orderProcs[] later */
251 keyDataMap = MemoryContextAlloc(so->arrayContext,
252 numberOfKeys * sizeof(int));
253
254 /*
255 * Also enlarge output array when it might otherwise not have room for
256 * a skip array's scan key
257 */
258 if (numberOfKeys > scan->numberOfKeys)
259 so->keyData = repalloc(so->keyData,
260 numberOfKeys * sizeof(ScanKeyData));
261 }
262 else
263 inkeys = scan->keyData;
264
265 /* we check that input keys are correctly ordered */
266 if (inkeys[0].sk_attno < 1)
267 elog(ERROR, "btree index keys must be ordered by attribute");
268
269 /* We can short-circuit most of the work if there's just one key */
270 if (numberOfKeys == 1)
271 {
272 /* Apply indoption to scankey (might change sk_strategy!) */
273 if (!_bt_fix_scankey_strategy(&inkeys[0], indoption))
274 so->qual_ok = false;
275 memcpy(&so->keyData[0], &inkeys[0], sizeof(ScanKeyData));
276 so->numberOfKeys = 1;
277 /* We can mark the qual as required if it's for first index col */
278 if (inkeys[0].sk_attno == 1)
279 _bt_mark_scankey_required(&so->keyData[0]);
280 if (arrayKeyData)
281 {
282 /*
283 * Don't call _bt_preprocess_array_keys_final in this fast path
284 * (we'll miss out on the single value array transformation, but
285 * that's not nearly as important when there's only one scan key)
286 */
287 Assert(so->keyData[0].sk_flags & SK_SEARCHARRAY);
288 Assert(so->keyData[0].sk_strategy != BTEqualStrategyNumber ||
289 (so->arrayKeys[0].scan_key == 0 &&
290 !(so->keyData[0].sk_flags & SK_BT_SKIP) &&
291 OidIsValid(so->orderProcs[0].fn_oid)));
292 }
293
294 return;
295 }
296
297 /*
298 * Otherwise, do the full set of pushups.
299 */
300 new_numberOfKeys = 0;
301 numberOfEqualCols = 0;
302
303 /*
304 * Initialize for processing of keys for attr 1.
305 *
306 * xform[i] points to the currently best scan key of strategy type i+1; it
307 * is NULL if we haven't yet found such a key for this attr.
308 */
309 attno = 1;
310 memset(xform, 0, sizeof(xform));
311
312 /*
313 * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to
314 * handle after-last-key processing. Actual exit from the loop is at the
315 * "break" statement below.
316 */
317 for (int i = 0;; i++)
318 {
319 ScanKey inkey = inkeys + i;
320 int j;
321
322 if (i < numberOfKeys)
323 {
324 /* Apply indoption to scankey (might change sk_strategy!) */
325 if (!_bt_fix_scankey_strategy(inkey, indoption))
326 {
327 /* NULL can't be matched, so give up */
328 so->qual_ok = false;
329 return;
330 }
331 }
332
333 /*
334 * If we are at the end of the keys for a particular attr, finish up
335 * processing and emit the cleaned-up keys.
336 */
337 if (i == numberOfKeys || inkey->sk_attno != attno)
338 {
339 int priorNumberOfEqualCols = numberOfEqualCols;
340
341 /* check input keys are correctly ordered */
342 if (i < numberOfKeys && inkey->sk_attno < attno)
343 elog(ERROR, "btree index keys must be ordered by attribute");
344
345 /*
346 * If = has been specified, all other keys can be eliminated as
347 * redundant. Note that this is no less true if the = key is
348 * SEARCHARRAY; the only real difference is that the inequality
349 * key _becomes_ redundant by making _bt_compare_scankey_args
350 * eliminate the subset of elements that won't need to be matched
351 * (with SAOP arrays and skip arrays alike).
352 *
353 * If we have a case like "key = 1 AND key > 2", we set qual_ok to
354 * false and abandon further processing. We'll do the same thing
355 * given a case like "key IN (0, 1) AND key > 2".
356 *
357 * We also have to deal with the case of "key IS NULL", which is
358 * unsatisfiable in combination with any other index condition. By
359 * the time we get here, that's been classified as an equality
360 * check, and we've rejected any combination of it with a regular
361 * equality condition; but not with other types of conditions.
362 */
363 if (xform[BTEqualStrategyNumber - 1].inkey)
364 {
365 ScanKey eq = xform[BTEqualStrategyNumber - 1].inkey;
366 BTArrayKeyInfo *array = NULL;
367 FmgrInfo *orderproc = NULL;
368
369 if (arrayKeyData && (eq->sk_flags & SK_SEARCHARRAY))
370 {
371 int eq_in_ikey,
372 eq_arrayidx;
373
374 eq_in_ikey = xform[BTEqualStrategyNumber - 1].inkeyi;
375 eq_arrayidx = xform[BTEqualStrategyNumber - 1].arrayidx;
376 array = &so->arrayKeys[eq_arrayidx - 1];
377 orderproc = so->orderProcs + eq_in_ikey;
378
379 Assert(array->scan_key == eq_in_ikey);
380 Assert(OidIsValid(orderproc->fn_oid));
381 }
382
383 for (j = BTMaxStrategyNumber; --j >= 0;)
384 {
385 ScanKey chk = xform[j].inkey;
386
387 if (!chk || j == (BTEqualStrategyNumber - 1))
388 continue;
389
390 if (eq->sk_flags & SK_SEARCHNULL)
391 {
392 /* IS NULL is contradictory to anything else */
393 so->qual_ok = false;
394 return;
395 }
396
397 if (_bt_compare_scankey_args(scan, chk, eq, chk,
398 array, orderproc,
399 &test_result))
400 {
401 if (!test_result)
402 {
403 /* keys proven mutually contradictory */
404 so->qual_ok = false;
405 return;
406 }
407 /* else discard the redundant non-equality key */
408 xform[j].inkey = NULL;
409 xform[j].inkeyi = -1;
410 }
411 else
412 redundant_key_kept = true;
413 }
414 /* track number of attrs for which we have "=" keys */
415 numberOfEqualCols++;
416 }
417
418 /* try to keep only one of <, <= */
419 if (xform[BTLessStrategyNumber - 1].inkey &&
420 xform[BTLessEqualStrategyNumber - 1].inkey)
421 {
422 ScanKey lt = xform[BTLessStrategyNumber - 1].inkey;
423 ScanKey le = xform[BTLessEqualStrategyNumber - 1].inkey;
424
425 if (_bt_compare_scankey_args(scan, le, lt, le, NULL, NULL,
426 &test_result))
427 {
428 if (test_result)
429 xform[BTLessEqualStrategyNumber - 1].inkey = NULL;
430 else
431 xform[BTLessStrategyNumber - 1].inkey = NULL;
432 }
433 else
434 redundant_key_kept = true;
435 }
436
437 /* try to keep only one of >, >= */
438 if (xform[BTGreaterStrategyNumber - 1].inkey &&
439 xform[BTGreaterEqualStrategyNumber - 1].inkey)
440 {
441 ScanKey gt = xform[BTGreaterStrategyNumber - 1].inkey;
442 ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1].inkey;
443
444 if (_bt_compare_scankey_args(scan, ge, gt, ge, NULL, NULL,
445 &test_result))
446 {
447 if (test_result)
448 xform[BTGreaterEqualStrategyNumber - 1].inkey = NULL;
449 else
450 xform[BTGreaterStrategyNumber - 1].inkey = NULL;
451 }
452 else
453 redundant_key_kept = true;
454 }
455
456 /*
457 * Emit the cleaned-up keys into the so->keyData[] array, and then
458 * mark them if they are required. They are required (possibly
459 * only in one direction) if all attrs before this one had "=".
460 *
461 * In practice we'll rarely output non-required scan keys here;
462 * typically, _bt_preprocess_array_keys has already added "=" keys
463 * sufficient to form an unbroken series of "=" constraints on all
464 * attrs prior to the attr from the final scan->keyData[] key.
465 */
466 for (j = BTMaxStrategyNumber; --j >= 0;)
467 {
468 if (xform[j].inkey)
469 {
470 ScanKey outkey = &so->keyData[new_numberOfKeys++];
471
472 memcpy(outkey, xform[j].inkey, sizeof(ScanKeyData));
473 if (arrayKeyData)
474 keyDataMap[new_numberOfKeys - 1] = xform[j].inkeyi;
475 if (priorNumberOfEqualCols == attno - 1)
476 _bt_mark_scankey_required(outkey);
477 }
478 }
479
480 /*
481 * Exit loop here if done.
482 */
483 if (i == numberOfKeys)
484 break;
485
486 /* Re-initialize for new attno */
487 attno = inkey->sk_attno;
488 memset(xform, 0, sizeof(xform));
489 }
490
491 /* check strategy this key's operator corresponds to */
492 j = inkey->sk_strategy - 1;
493
494 if (inkey->sk_strategy == BTEqualStrategyNumber &&
495 (inkey->sk_flags & SK_SEARCHARRAY))
496 {
497 /* must track how input scan keys map to arrays */
498 Assert(arrayKeyData);
499 arrayidx++;
500 }
501
502 /*
503 * have we seen a scan key for this same attribute and using this same
504 * operator strategy before now?
505 */
506 if (xform[j].inkey == NULL)
507 {
508 /* nope, so this scan key wins by default (at least for now) */
509 xform[j].inkey = inkey;
510 xform[j].inkeyi = i;
511 xform[j].arrayidx = arrayidx;
512 }
513 else
514 {
515 FmgrInfo *orderproc = NULL;
516 BTArrayKeyInfo *array = NULL;
517
518 /*
519 * Seen one of these before, so keep only the more restrictive key
520 * if possible
521 */
522 if (j == (BTEqualStrategyNumber - 1) && arrayKeyData)
523 {
524 /*
525 * Have to set up array keys
526 */
527 if (inkey->sk_flags & SK_SEARCHARRAY)
528 {
529 array = &so->arrayKeys[arrayidx - 1];
530 orderproc = so->orderProcs + i;
531
532 Assert(array->scan_key == i);
533 Assert(OidIsValid(orderproc->fn_oid));
534 Assert(!(inkey->sk_flags & SK_BT_SKIP));
535 }
536 else if (xform[j].inkey->sk_flags & SK_SEARCHARRAY)
537 {
538 array = &so->arrayKeys[xform[j].arrayidx - 1];
539 orderproc = so->orderProcs + xform[j].inkeyi;
540
541 Assert(array->scan_key == xform[j].inkeyi);
542 Assert(OidIsValid(orderproc->fn_oid));
543 Assert(!(xform[j].inkey->sk_flags & SK_BT_SKIP));
544 }
545
546 /*
547 * Both scan keys might have arrays, in which case we'll
548 * arbitrarily pass only one of the arrays. That won't
549 * matter, since _bt_compare_scankey_args is aware that two
550 * SEARCHARRAY scan keys mean that _bt_preprocess_array_keys
551 * failed to eliminate redundant arrays through array merging.
552 * _bt_compare_scankey_args just returns false when it sees
553 * this; it won't even try to examine either array.
554 */
555 }
556
557 if (_bt_compare_scankey_args(scan, inkey, inkey, xform[j].inkey,
558 array, orderproc, &test_result))
559 {
560 /* Have all we need to determine redundancy */
561 if (test_result)
562 {
563 /*
564 * New key is more restrictive, and so replaces old key...
565 */
566 if (j != (BTEqualStrategyNumber - 1) ||
567 !(xform[j].inkey->sk_flags & SK_SEARCHARRAY))
568 {
569 xform[j].inkey = inkey;
570 xform[j].inkeyi = i;
571 xform[j].arrayidx = arrayidx;
572 }
573 else
574 {
575 /*
576 * ...unless we have to keep the old key because it's
577 * an array that rendered the new key redundant. We
578 * need to make sure that we don't throw away an array
579 * scan key. _bt_preprocess_array_keys_final expects
580 * us to keep all of the arrays that weren't already
581 * eliminated by _bt_preprocess_array_keys earlier on.
582 */
583 Assert(!(inkey->sk_flags & SK_SEARCHARRAY));
584 }
585 }
586 else if (j == (BTEqualStrategyNumber - 1))
587 {
588 /* key == a && key == b, but a != b */
589 so->qual_ok = false;
590 return;
591 }
592 /* else old key is more restrictive, keep it */
593 }
594 else
595 {
596 /*
597 * We can't determine which key is more restrictive. Push
598 * xform[j] directly to the output array, then set xform[j] to
599 * the new scan key.
600 *
601 * Note: We do things this way around so that our arrays are
602 * always in the same order as their corresponding scan keys.
603 * _bt_preprocess_array_keys_final expects this.
604 */
605 ScanKey outkey = &so->keyData[new_numberOfKeys++];
606
607 memcpy(outkey, xform[j].inkey, sizeof(ScanKeyData));
608 if (arrayKeyData)
609 keyDataMap[new_numberOfKeys - 1] = xform[j].inkeyi;
610 if (numberOfEqualCols == attno - 1)
611 _bt_mark_scankey_required(outkey);
612 xform[j].inkey = inkey;
613 xform[j].inkeyi = i;
614 xform[j].arrayidx = arrayidx;
615 redundant_key_kept = true;
616 }
617 }
618 }
619
620 so->numberOfKeys = new_numberOfKeys;
621
622 /*
623 * Now that we've built a temporary mapping from so->keyData[] (output
624 * scan keys) to arrayKeyData[] (our input scan keys), fix array->scan_key
625 * references. Also consolidate the so->orderProcs[] array such that it
626 * can be subscripted using so->keyData[]-wise offsets.
627 */
628 if (arrayKeyData)
629 _bt_preprocess_array_keys_final(scan, keyDataMap);
630
631 /*
632 * If there are remaining redundant inequality keys, we must make sure
633 * that each index attribute has no more than one required >/>= key, and
634 * no more than one required </<= key. Attributes that have one or more
635 * required = keys now must keep only one required key (the first = key).
636 */
637 if (unlikely(redundant_key_kept) && so->qual_ok)
638 _bt_unmark_keys(scan, keyDataMap);
639
640 /* Could pfree arrayKeyData/keyDataMap now, but not worth the cycles */
641 }
642
643 /*
644 * Adjust a scankey's strategy and flags setting as needed for indoptions.
645 *
646 * We copy the appropriate indoption value into the scankey sk_flags
647 * (shifting to avoid clobbering system-defined flag bits). Also, if
648 * the DESC option is set, commute (flip) the operator strategy number.
649 *
650 * A secondary purpose is to check for IS NULL/NOT NULL scankeys and set up
651 * the strategy field correctly for them.
652 *
653 * Lastly, for ordinary scankeys (not IS NULL/NOT NULL), we check for a
654 * NULL comparison value. Since all btree operators are assumed strict,
655 * a NULL means that the qual cannot be satisfied. We return true if the
656 * comparison value isn't NULL, or false if the scan should be abandoned.
657 *
658 * This function is applied to the *input* scankey structure; therefore
659 * on a rescan we will be looking at already-processed scankeys. Hence
660 * we have to be careful not to re-commute the strategy if we already did it.
661 * It's a bit ugly to modify the caller's copy of the scankey but in practice
662 * there shouldn't be any problem, since the index's indoptions are certainly
663 * not going to change while the scankey survives.
664 */
665 static bool
666 _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
667 {
668 int addflags;
669
670 addflags = indoption[skey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
671
672 /*
673 * We treat all btree operators as strict (even if they're not so marked
674 * in pg_proc). This means that it is impossible for an operator condition
675 * with a NULL comparison constant to succeed, and we can reject it right
676 * away.
677 *
678 * However, we now also support "x IS NULL" clauses as search conditions,
679 * so in that case keep going. The planner has not filled in any
680 * particular strategy in this case, so set it to BTEqualStrategyNumber
681 * --- we can treat IS NULL as an equality operator for purposes of search
682 * strategy.
683 *
684 * Likewise, "x IS NOT NULL" is supported. We treat that as either "less
685 * than NULL" in a NULLS LAST index, or "greater than NULL" in a NULLS
686 * FIRST index.
687 *
688 * Note: someday we might have to fill in sk_collation from the index
689 * column's collation. At the moment this is a non-issue because we'll
690 * never actually call the comparison operator on a NULL.
691 */
692 if (skey->sk_flags & SK_ISNULL)
693 {
694 /* SK_ISNULL shouldn't be set in a row header scankey */
695 Assert(!(skey->sk_flags & SK_ROW_HEADER));
696
697 /* Set indoption flags in scankey (might be done already) */
698 skey->sk_flags |= addflags;
699
700 /* Set correct strategy for IS NULL or NOT NULL search */
701 if (skey->sk_flags & SK_SEARCHNULL)
702 {
703 skey->sk_strategy = BTEqualStrategyNumber;
704 skey->sk_subtype = InvalidOid;
705 skey->sk_collation = InvalidOid;
706 }
707 else if (skey->sk_flags & SK_SEARCHNOTNULL)
708 {
709 if (skey->sk_flags & SK_BT_NULLS_FIRST)
710 skey->sk_strategy = BTGreaterStrategyNumber;
711 else
712 skey->sk_strategy = BTLessStrategyNumber;
713 skey->sk_subtype = InvalidOid;
714 skey->sk_collation = InvalidOid;
715 }
716 else
717 {
718 /* regular qual, so it cannot be satisfied */
719 return false;
720 }
721
722 /* Needn't do the rest */
723 return true;
724 }
725
726 /* Adjust strategy for DESC, if we didn't already */
727 if ((addflags & SK_BT_DESC) && !(skey->sk_flags & SK_BT_DESC))
728 skey->sk_strategy = BTCommuteStrategyNumber(skey->sk_strategy);
729 skey->sk_flags |= addflags;
730
731 /* If it's a row header, fix row member flags and strategies similarly */
732 if (skey->sk_flags & SK_ROW_HEADER)
733 {
734 ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
735
736 if (subkey->sk_flags & SK_ISNULL)
737 {
738 /* First row member is NULL, so RowCompare is unsatisfiable */
739 Assert(subkey->sk_flags & SK_ROW_MEMBER);
740 return false;
741 }
742
743 for (;;)
744 {
745 Assert(subkey->sk_flags & SK_ROW_MEMBER);
746 addflags = indoption[subkey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
747 if ((addflags & SK_BT_DESC) && !(subkey->sk_flags & SK_BT_DESC))
748 subkey->sk_strategy = BTCommuteStrategyNumber(subkey->sk_strategy);
749 subkey->sk_flags |= addflags;
750 if (subkey->sk_flags & SK_ROW_END)
751 break;
752 subkey++;
753 }
754 }
755
756 return true;
757 }
758
759 /*
760 * Mark a scankey as "required to continue the scan".
761 *
762 * Depending on the operator type, the key may be required for both scan
763 * directions or just one. Also, if the key is a row comparison header,
764 * we have to mark the appropriate subsidiary ScanKeys as required. In such
765 * cases, the first subsidiary key is required, but subsequent ones are
766 * required only as long as they correspond to successive index columns and
767 * match the leading column as to sort direction. Otherwise the row
768 * comparison ordering is different from the index ordering and so we can't
769 * stop the scan on the basis of those lower-order columns.
770 *
771 * Note: when we set required-key flag bits in a subsidiary scankey, we are
772 * scribbling on a data structure belonging to the index AM's caller, not on
773 * our private copy. This should be OK because the marking will not change
774 * from scan to scan within a query, and so we'd just re-mark the same way
775 * anyway on a rescan. Something to keep an eye on though.
776 */
777 static void
778 _bt_mark_scankey_required(ScanKey skey)
779 {
780 int addflags;
781
782 switch (skey->sk_strategy)
783 {
784 case BTLessStrategyNumber:
785 case BTLessEqualStrategyNumber:
786 addflags = SK_BT_REQFWD;
787 break;
788 case BTEqualStrategyNumber:
789 addflags = SK_BT_REQFWD | SK_BT_REQBKWD;
790 break;
791 case BTGreaterEqualStrategyNumber:
792 case BTGreaterStrategyNumber:
793 addflags = SK_BT_REQBKWD;
794 break;
795 default:
796 elog(ERROR, "unrecognized StrategyNumber: %d",
797 (int) skey->sk_strategy);
798 addflags = 0; /* keep compiler quiet */
799 break;
800 }
801
802 skey->sk_flags |= addflags;
803
804 if (skey->sk_flags & SK_ROW_HEADER)
805 {
806 ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
807 AttrNumber attno = skey->sk_attno;
808
809 /* First subkey should be same column/operator as the header */
810 Assert(subkey->sk_attno == attno);
811 Assert(subkey->sk_strategy == skey->sk_strategy);
812
813 for (;;)
814 {
815 Assert(subkey->sk_flags & SK_ROW_MEMBER);
816 if (subkey->sk_attno != attno)
817 break; /* non-adjacent key, so not required */
818 if (subkey->sk_strategy != skey->sk_strategy)
819 break; /* wrong direction, so not required */
820 subkey->sk_flags |= addflags;
821 if (subkey->sk_flags & SK_ROW_END)
822 break;
823 subkey++;
824 attno++;
825 }
826 }
827 }
828
829 /*
830 * Compare two scankey values using a specified operator.
831 *
832 * The test we want to perform is logically "leftarg op rightarg", where
833 * leftarg and rightarg are the sk_argument values in those ScanKeys, and
834 * the comparison operator is the one in the op ScanKey. However, in
835 * cross-data-type situations we may need to look up the correct operator in
836 * the index's opfamily: it is the one having amopstrategy = op->sk_strategy
837 * and amoplefttype/amoprighttype equal to the two argument datatypes.
838 *
839 * If the opfamily doesn't supply a complete set of cross-type operators we
840 * may not be able to make the comparison. If we can make the comparison
841 * we store the operator result in *result and return true. We return false
842 * if the comparison could not be made.
843 *
844 * If either leftarg or rightarg are an array, we'll apply array-specific
845 * rules to determine which array elements are redundant on behalf of caller.
846 * It is up to our caller to save whichever of the two scan keys is the array,
847 * and discard the non-array scan key (the non-array scan key is guaranteed to
848 * be redundant with any complete opfamily). Caller isn't expected to call
849 * here with a pair of array scan keys provided we're dealing with a complete
850 * opfamily (_bt_preprocess_array_keys will merge array keys together to make
851 * sure of that).
852 *
853 * Note: we'll also shrink caller's array as needed to eliminate redundant
854 * array elements. One reason why caller should prefer to discard non-array
855 * scan keys is so that we'll have the opportunity to shrink the array
856 * multiple times, in multiple calls (for each of several other scan keys on
857 * the same index attribute).
858 *
859 * Note: op always points at the same ScanKey as either leftarg or rightarg.
860 * Since we don't scribble on the scankeys themselves, this aliasing should
861 * cause no trouble.
862 *
863 * Note: this routine needs to be insensitive to any DESC option applied
864 * to the index column. For example, "x < 4" is a tighter constraint than
865 * "x < 5" regardless of which way the index is sorted.
866 */
867 static bool
868 _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
869 ScanKey leftarg, ScanKey rightarg,
870 BTArrayKeyInfo *array, FmgrInfo *orderproc,
871 bool *result)
872 {
873 Relation rel = scan->indexRelation;
874 Oid lefttype,
875 righttype,
876 optype,
877 opcintype,
878 cmp_op;
879 StrategyNumber strat;
880
881 Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_ROW_MEMBER));
882
883 /*
884 * First, deal with cases where one or both args are NULL. This should
885 * only happen when the scankeys represent IS NULL/NOT NULL conditions.
886 */
887 if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ISNULL)
888 {
889 bool leftnull,
890 rightnull;
891
892 /* Handle skip array comparison with IS NOT NULL scan key */
893 if ((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP)
894 {
895 /* Shouldn't generate skip array in presence of IS NULL key */
896 Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_SEARCHNULL));
897 Assert((leftarg->sk_flags | rightarg->sk_flags) & SK_SEARCHNOTNULL);
898
899 /* Skip array will have no NULL element/IS NULL scan key */
900 Assert(array->num_elems == -1);
901 array->null_elem = false;
902
903 /* IS NOT NULL key (could be leftarg or rightarg) now redundant */
904 *result = true;
905 return true;
906 }
907
908 if (leftarg->sk_flags & SK_ISNULL)
909 {
910 Assert(leftarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
911 leftnull = true;
912 }
913 else
914 leftnull = false;
915 if (rightarg->sk_flags & SK_ISNULL)
916 {
917 Assert(rightarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
918 rightnull = true;
919 }
920 else
921 rightnull = false;
922
923 /*
924 * We treat NULL as either greater than or less than all other values.
925 * Since true > false, the tests below work correctly for NULLS LAST
926 * logic. If the index is NULLS FIRST, we need to flip the strategy.
927 */
928 strat = op->sk_strategy;
929 if (op->sk_flags & SK_BT_NULLS_FIRST)
930 strat = BTCommuteStrategyNumber(strat);
931
932 switch (strat)
933 {
934 case BTLessStrategyNumber:
935 *result = (leftnull < rightnull);
936 break;
937 case BTLessEqualStrategyNumber:
938 *result = (leftnull <= rightnull);
939 break;
940 case BTEqualStrategyNumber:
941 *result = (leftnull == rightnull);
942 break;
943 case BTGreaterEqualStrategyNumber:
944 *result = (leftnull >= rightnull);
945 break;
946 case BTGreaterStrategyNumber:
947 *result = (leftnull > rightnull);
948 break;
949 default:
950 elog(ERROR, "unrecognized StrategyNumber: %d", (int) strat);
951 *result = false; /* keep compiler quiet */
952 break;
953 }
954 return true;
955 }
956
957 /*
958 * We don't yet know how to determine redundancy when it involves a row
959 * compare key (barring simple cases involving IS NULL/IS NOT NULL)
960 */
961 if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ROW_HEADER)
962 {
963 Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP));
964 return false;
965 }
966
967 /*
968 * If either leftarg or rightarg are equality-type array scankeys, we need
969 * specialized handling (since by now we know that IS NULL wasn't used)
970 */
971 if (array)
972 {
973 bool leftarray,
974 rightarray;
975
976 leftarray = ((leftarg->sk_flags & SK_SEARCHARRAY) &&
977 leftarg->sk_strategy == BTEqualStrategyNumber);
978 rightarray = ((rightarg->sk_flags & SK_SEARCHARRAY) &&
979 rightarg->sk_strategy == BTEqualStrategyNumber);
980
981 /*
982 * _bt_preprocess_array_keys is responsible for merging together array
983 * scan keys, and will do so whenever the opfamily has the required
984 * cross-type support. If it failed to do that, we handle it just
985 * like the case where we can't make the comparison ourselves.
986 */
987 if (leftarray && rightarray)
988 {
989 /* Can't make the comparison */
990 *result = false; /* suppress compiler warnings */
991 Assert(!((leftarg->sk_flags | rightarg->sk_flags) & SK_BT_SKIP));
992 return false;
993 }
994
995 /*
996 * Otherwise we need to determine if either one of leftarg or rightarg
997 * uses an array, then pass this through to a dedicated helper
998 * function.
999 */
1000 if (leftarray)
1001 return _bt_compare_array_scankey_args(scan, leftarg, rightarg,
1002 orderproc, array, result);
1003 else if (rightarray)
1004 return _bt_compare_array_scankey_args(scan, rightarg, leftarg,
1005 orderproc, array, result);
1006
1007 /* FALL THRU */
1008 }
1009
1010 /*
1011 * The opfamily we need to worry about is identified by the index column.
1012 */
1013 Assert(leftarg->sk_attno == rightarg->sk_attno);
1014
1015 opcintype = rel->rd_opcintype[leftarg->sk_attno - 1];
1016
1017 /*
1018 * Determine the actual datatypes of the ScanKey arguments. We have to
1019 * support the convention that sk_subtype == InvalidOid means the opclass
1020 * input type; this is a hack to simplify life for ScanKeyInit().
1021 */
1022 lefttype = leftarg->sk_subtype;
1023 if (lefttype == InvalidOid)
1024 lefttype = opcintype;
1025 righttype = rightarg->sk_subtype;
1026 if (righttype == InvalidOid)
1027 righttype = opcintype;
1028 optype = op->sk_subtype;
1029 if (optype == InvalidOid)
1030 optype = opcintype;
1031
1032 /*
1033 * If leftarg and rightarg match the types expected for the "op" scankey,
1034 * we can use its already-looked-up comparison function.
1035 */
1036 if (lefttype == opcintype && righttype == optype)
1037 {
1038 *result = DatumGetBool(FunctionCall2Coll(&op->sk_func,
1039 op->sk_collation,
1040 leftarg->sk_argument,
1041 rightarg->sk_argument));
1042 return true;
1043 }
1044
1045 /*
1046 * Otherwise, we need to go to the syscache to find the appropriate
1047 * operator. (This cannot result in infinite recursion, since no
1048 * indexscan initiated by syscache lookup will use cross-data-type
1049 * operators.)
1050 *
1051 * If the sk_strategy was flipped by _bt_fix_scankey_strategy, we have to
1052 * un-flip it to get the correct opfamily member.
1053 */
1054 strat = op->sk_strategy;
1055 if (op->sk_flags & SK_BT_DESC)
1056 strat = BTCommuteStrategyNumber(strat);
1057
1058 cmp_op = get_opfamily_member(rel->rd_opfamily[leftarg->sk_attno - 1],
1059 lefttype,
1060 righttype,
1061 strat);
1062 if (OidIsValid(cmp_op))
1063 {
1064 RegProcedure cmp_proc = get_opcode(cmp_op);
1065
1066 if (RegProcedureIsValid(cmp_proc))
1067 {
1068 *result = DatumGetBool(OidFunctionCall2Coll(cmp_proc,
1069 op->sk_collation,
1070 leftarg->sk_argument,
1071 rightarg->sk_argument));
1072 return true;
1073 }
1074 }
1075
1076 /* Can't make the comparison */
1077 *result = false; /* suppress compiler warnings */
1078 return false;
1079 }
1080
1081 /*
1082 * Compare an array scan key to a scalar scan key, eliminating contradictory
1083 * array elements such that the scalar scan key becomes redundant.
1084 *
1085 * If the opfamily is incomplete we may not be able to determine which
1086 * elements are contradictory. When we return true we'll have validly set
1087 * *qual_ok, guaranteeing that at least the scalar scan key can be considered
1088 * redundant. We return false if the comparison could not be made (caller
1089 * must keep both scan keys when this happens).
1090 *
1091 * Note: it's up to caller to deal with IS [NOT] NULL scan keys, as well as
1092 * row comparison scan keys. We only deal with scalar scan keys.
1093 */
1094 static bool
1095 _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
1096 FmgrInfo *orderproc, BTArrayKeyInfo *array,
1097 bool *qual_ok)
1098 {
1099 Assert(arraysk->sk_attno == skey->sk_attno);
1100 Assert(!(arraysk->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
1101 Assert((arraysk->sk_flags & SK_SEARCHARRAY) &&
1102 arraysk->sk_strategy == BTEqualStrategyNumber);
1103 /* don't expect to have to deal with NULLs/row comparison scan keys */
1104 Assert(!(skey->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
1105 Assert(!(skey->sk_flags & SK_SEARCHARRAY) ||
1106 skey->sk_strategy != BTEqualStrategyNumber);
1107
1108 /*
1109 * Just call the appropriate helper function based on whether it's a SAOP
1110 * array or a skip array. Both helpers will set *qual_ok in passing.
1111 */
1112 if (array->num_elems != -1)
1113 return _bt_saoparray_shrink(scan, arraysk, skey, orderproc, array,
1114 qual_ok);
1115 else
1116 return _bt_skiparray_shrink(scan, skey, array, qual_ok);
1117 }
1118
1119 /*
1120 * Preprocessing of SAOP array scan key, used to determine which array
1121 * elements are eliminated as contradictory by a non-array scalar key.
1122 *
1123 * _bt_compare_array_scankey_args helper function.
1124 *
1125 * Array elements can be eliminated as contradictory when excluded by some
1126 * other operator on the same attribute. For example, with an index scan qual
1127 * "WHERE a IN (1, 2, 3) AND a < 2", all array elements except the value "1"
1128 * are eliminated, and the < scan key is eliminated as redundant. Cases where
1129 * every array element is eliminated by a redundant scalar scan key have an
1130 * unsatisfiable qual, which we handle by setting *qual_ok=false for caller.
1131 */
1132 static bool
1133 _bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
1134 FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
1135 {
1136 Relation rel = scan->indexRelation;
1137 Oid opcintype = rel->rd_opcintype[arraysk->sk_attno - 1];
1138 int cmpresult = 0,
1139 cmpexact = 0,
1140 matchelem,
1141 new_nelems = 0;
1142 FmgrInfo crosstypeproc;
1143 FmgrInfo *orderprocp = orderproc;
1144
1145 Assert(array->num_elems > 0);
1146 Assert(!(arraysk->sk_flags & SK_BT_SKIP));
1147
1148 /*
1149 * _bt_binsrch_array_skey searches an array for the entry best matching a
1150 * datum of opclass input type for the index's attribute (on-disk type).
1151 * We can reuse the array's ORDER proc whenever the non-array scan key's
1152 * type is a match for the corresponding attribute's input opclass type.
1153 * Otherwise, we have to do another ORDER proc lookup so that our call to
1154 * _bt_binsrch_array_skey applies the correct comparator.
1155 *
1156 * Note: we have to support the convention that sk_subtype == InvalidOid
1157 * means the opclass input type; this is a hack to simplify life for
1158 * ScanKeyInit().
1159 */
1160 if (skey->sk_subtype != opcintype && skey->sk_subtype != InvalidOid)
1161 {
1162 RegProcedure cmp_proc;
1163 Oid arraysk_elemtype;
1164
1165 /*
1166 * Need an ORDER proc lookup to detect redundancy/contradictoriness
1167 * with this pair of scankeys.
1168 *
1169 * Scalar scan key's argument will be passed to _bt_compare_array_skey
1170 * as its tupdatum/lefthand argument (rhs arg is for array elements).
1171 */
1172 arraysk_elemtype = arraysk->sk_subtype;
1173 if (arraysk_elemtype == InvalidOid)
1174 arraysk_elemtype = rel->rd_opcintype[arraysk->sk_attno - 1];
1175 cmp_proc = get_opfamily_proc(rel->rd_opfamily[arraysk->sk_attno - 1],
1176 skey->sk_subtype, arraysk_elemtype,
1177 BTORDER_PROC);
1178 if (!RegProcedureIsValid(cmp_proc))
1179 {
1180 /* Can't make the comparison */
1181 *qual_ok = false; /* suppress compiler warnings */
1182 return false;
1183 }
1184
1185 /* We have all we need to determine redundancy/contradictoriness */
1186 orderprocp = &crosstypeproc;
1187 fmgr_info(cmp_proc, orderprocp);
1188 }
1189
1190 matchelem = _bt_binsrch_array_skey(orderprocp, false,
1191 NoMovementScanDirection,
1192 skey->sk_argument, false, array,
1193 arraysk, &cmpresult);
1194
1195 switch (skey->sk_strategy)
1196 {
1197 case BTLessStrategyNumber:
1198 cmpexact = 1; /* exclude exact match, if any */
1199 /* FALL THRU */
1200 case BTLessEqualStrategyNumber:
1201 if (cmpresult >= cmpexact)
1202 matchelem++;
1203 /* Resize, keeping elements from the start of the array */
1204 new_nelems = matchelem;
1205 break;
1206 case BTEqualStrategyNumber:
1207 if (cmpresult != 0)
1208 {
1209 /* qual is unsatisfiable */
1210 new_nelems = 0;
1211 }
1212 else
1213 {
1214 /* Shift matching element to the start of the array, resize */
1215 array->elem_values[0] = array->elem_values[matchelem];
1216 new_nelems = 1;
1217 }
1218 break;
1219 case BTGreaterEqualStrategyNumber:
1220 cmpexact = 1; /* include exact match, if any */
1221 /* FALL THRU */
1222 case BTGreaterStrategyNumber:
1223 if (cmpresult >= cmpexact)
1224 matchelem++;
1225 /* Shift matching elements to the start of the array, resize */
1226 new_nelems = array->num_elems - matchelem;
1227 memmove(array->elem_values, array->elem_values + matchelem,
1228 sizeof(Datum) * new_nelems);
1229 break;
1230 default:
1231 elog(ERROR, "unrecognized StrategyNumber: %d",
1232 (int) skey->sk_strategy);
1233 break;
1234 }
1235
1236 Assert(new_nelems >= 0);
1237 Assert(new_nelems <= array->num_elems);
1238
1239 array->num_elems = new_nelems;
1240 *qual_ok = new_nelems > 0;
1241
1242 return true;
1243 }
1244
1245 /*
1246 * Preprocessing of skip array scan key, used to determine redundancy against
1247 * a non-array scalar scan key (must be an inequality).
1248 *
1249 * _bt_compare_array_scankey_args helper function.
1250 *
1251 * Skip arrays work by procedurally generating their elements as needed, so we
1252 * just store the inequality as the skip array's low_compare or high_compare
1253 * (except when there's already a more restrictive low_compare/high_compare).
1254 * The array's final elements are the range of values that still satisfy the
1255 * array's final low_compare and high_compare.
1256 */
1257 static bool
1258 _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey, BTArrayKeyInfo *array,
1259 bool *qual_ok)
1260 {
1261 bool test_result;
1262
1263 Assert(array->num_elems == -1);
1264
1265 /*
1266 * Array's index attribute will be constrained by a strict operator/key.
1267 * Array must not "contain a NULL element" (i.e. the scan must not apply
1268 * "IS NULL" qual when it reaches the end of the index that stores NULLs).
1269 */
1270 array->null_elem = false;
1271 *qual_ok = true;
1272
1273 /*
1274 * Consider if we should treat caller's scalar scan key as the skip
1275 * array's high_compare or low_compare.
1276 *
1277 * In general the current array element must either be a copy of a value
1278 * taken from an index tuple, or a derivative value generated by opclass's
1279 * skip support function. That way the scan can always safely assume that
1280 * it's okay to use the only-input-opclass-type proc from so->orderProcs[]
1281 * (they can be cross-type with SAOP arrays, but never with skip arrays).
1282 *
1283 * This approach is enabled by MINVAL/MAXVAL sentinel key markings, which
1284 * can be thought of as representing either the lowest or highest matching
1285 * array element (excluding the NULL element, where applicable, though as
1286 * just discussed it isn't applicable to this range skip array anyway).
1287 * Array keys marked MINVAL/MAXVAL never have a valid datum in their
1288 * sk_argument field. The scan directly applies the array's low_compare
1289 * key when it encounters MINVAL in the array key proper (just as it
1290 * applies high_compare when it sees MAXVAL set in the array key proper).
1291 * The scan must never use the array's so->orderProcs[] proc against
1292 * low_compare's/high_compare's sk_argument, either (so->orderProcs[] is
1293 * only intended to be used with rhs datums from the array proper/index).
1294 */
1295 switch (skey->sk_strategy)
1296 {
1297 case BTLessStrategyNumber:
1298 case BTLessEqualStrategyNumber:
1299 if (array->high_compare)
1300 {
1301 /* replace existing high_compare with caller's key? */
1302 if (!_bt_compare_scankey_args(scan, array->high_compare, skey,
1303 array->high_compare, NULL, NULL,
1304 &test_result))
1305 return false; /* can't determine more restrictive key */
1306
1307 if (!test_result)
1308 return true; /* no, just discard caller's key */
1309
1310 /* yes, replace existing high_compare with caller's key */
1311 }
1312
1313 /* caller's key becomes skip array's high_compare */
1314 array->high_compare = skey;
1315 break;
1316 case BTGreaterEqualStrategyNumber:
1317 case BTGreaterStrategyNumber:
1318 if (array->low_compare)
1319 {
1320 /* replace existing low_compare with caller's key? */
1321 if (!_bt_compare_scankey_args(scan, array->low_compare, skey,
1322 array->low_compare, NULL, NULL,
1323 &test_result))
1324 return false; /* can't determine more restrictive key */
1325
1326 if (!test_result)
1327 return true; /* no, just discard caller's key */
1328
1329 /* yes, replace existing low_compare with caller's key */
1330 }
1331
1332 /* caller's key becomes skip array's low_compare */
1333 array->low_compare = skey;
1334 break;
1335 case BTEqualStrategyNumber:
1336 default:
1337 elog(ERROR, "unrecognized StrategyNumber: %d",
1338 (int) skey->sk_strategy);
1339 break;
1340 }
1341
1342 return true;
1343 }
1344
1345 /*
1346 * Applies the opfamily's skip support routine to convert the skip array's >
1347 * low_compare key (if any) into a >= key, and to convert its < high_compare
1348 * key (if any) into a <= key. Decrements the high_compare key's sk_argument,
1349 * and/or increments the low_compare key's sk_argument (also adjusts their
1350 * operator strategies, while changing the operator as appropriate).
1351 *
1352 * This optional optimization reduces the number of descents required within
1353 * _bt_first. Whenever _bt_first is called with a skip array whose current
1354 * array element is the sentinel value MINVAL, using a transformed >= key
1355 * instead of using the original > key makes it safe to include lower-order
1356 * scan keys in the insertion scan key (there must be lower-order scan keys
1357 * after the skip array). We will avoid an extra _bt_first to find the first
1358 * value in the index > sk_argument -- at least when the first real matching
1359 * value in the index happens to be an exact match for the sk_argument value
1360 * that we produced here by incrementing the original input key's sk_argument.
1361 * (Backwards scans derive the same benefit when they encounter the sentinel
1362 * value MAXVAL, by converting the high_compare key from < to <=.)
1363 *
1364 * Note: The transformation is only correct when it cannot allow the scan to
1365 * overlook matching tuples, but we don't have enough semantic information to
1366 * safely make sure that can't happen during scans with cross-type operators.
1367 * That's why we'll never apply the transformation in cross-type scenarios.
1368 * For example, if we attempted to convert "sales_ts > '2024-01-01'::date"
1369 * into "sales_ts >= '2024-01-02'::date" given a "sales_ts" attribute whose
1370 * input opclass is timestamp_ops, the scan would overlook almost all (or all)
1371 * tuples for sales that fell on '2024-01-01'.
1372 *
1373 * Note: We can safely modify array->low_compare/array->high_compare in place
1374 * because they just point to copies of our scan->keyData[] input scan keys
1375 * (namely the copies returned by _bt_preprocess_array_keys to be used as
1376 * input into the standard preprocessing steps in _bt_preprocess_keys).
1377 * Everything will be reset if there's a rescan.
1378 */
1379 static void
1380 _bt_skiparray_strat_adjust(IndexScanDesc scan, ScanKey arraysk,
1381 BTArrayKeyInfo *array)
1382 {
1383 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1384 MemoryContext oldContext;
1385
1386 /*
1387 * Called last among all preprocessing steps, when the skip array's final
1388 * low_compare and high_compare have both been chosen
1389 */
1390 Assert(arraysk->sk_flags & SK_BT_SKIP);
1391 Assert(array->num_elems == -1 && !array->null_elem && array->sksup);
1392
1393 oldContext = MemoryContextSwitchTo(so->arrayContext);
1394
1395 if (array->high_compare &&
1396 array->high_compare->sk_strategy == BTLessStrategyNumber)
1397 _bt_skiparray_strat_decrement(scan, arraysk, array);
1398
1399 if (array->low_compare &&
1400 array->low_compare->sk_strategy == BTGreaterStrategyNumber)
1401 _bt_skiparray_strat_increment(scan, arraysk, array);
1402
1403 MemoryContextSwitchTo(oldContext);
1404 }
1405
1406 /*
1407 * Convert skip array's < high_compare key into a <= key
1408 */
1409 static void
1410 _bt_skiparray_strat_decrement(IndexScanDesc scan, ScanKey arraysk,
1411 BTArrayKeyInfo *array)
1412 {
1413 Relation rel = scan->indexRelation;
1414 Oid opfamily = rel->rd_opfamily[arraysk->sk_attno - 1],
1415 opcintype = rel->rd_opcintype[arraysk->sk_attno - 1],
1416 leop;
1417 RegProcedure cmp_proc;
1418 ScanKey high_compare = array->high_compare;
1419 Datum orig_sk_argument = high_compare->sk_argument,
1420 new_sk_argument;
1421 bool uflow;
1422 int16 lookupstrat;
1423
1424 Assert(high_compare->sk_strategy == BTLessStrategyNumber);
1425
1426 /*
1427 * Only perform the transformation when the operator type matches the
1428 * index attribute's input opclass type
1429 */
1430 if (high_compare->sk_subtype != opcintype &&
1431 high_compare->sk_subtype != InvalidOid)
1432 return;
1433
1434 /* Decrement, handling underflow by marking the qual unsatisfiable */
1435 new_sk_argument = array->sksup->decrement(rel, orig_sk_argument, &uflow);
1436 if (uflow)
1437 {
1438 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1439
1440 so->qual_ok = false;
1441 return;
1442 }
1443
1444 /*
1445 * Look up <= operator (might fail), accounting for the fact that a
1446 * high_compare on a DESC column already had its strategy commuted
1447 */
1448 lookupstrat = BTLessEqualStrategyNumber;
1449 if (high_compare->sk_flags & SK_BT_DESC)
1450 lookupstrat = BTGreaterEqualStrategyNumber; /* commute this too */
1451 leop = get_opfamily_member(opfamily, opcintype, opcintype, lookupstrat);
1452 if (!OidIsValid(leop))
1453 return;
1454 cmp_proc = get_opcode(leop);
1455 if (RegProcedureIsValid(cmp_proc))
1456 {
1457 /* Transform < high_compare key into <= key */
1458 fmgr_info(cmp_proc, &high_compare->sk_func);
1459 high_compare->sk_argument = new_sk_argument;
1460 high_compare->sk_strategy = BTLessEqualStrategyNumber;
1461 }
1462 }
1463
1464 /*
1465 * Convert skip array's > low_compare key into a >= key
1466 */
1467 static void
1468 _bt_skiparray_strat_increment(IndexScanDesc scan, ScanKey arraysk,
1469 BTArrayKeyInfo *array)
1470 {
1471 Relation rel = scan->indexRelation;
1472 Oid opfamily = rel->rd_opfamily[arraysk->sk_attno - 1],
1473 opcintype = rel->rd_opcintype[arraysk->sk_attno - 1],
1474 geop;
1475 RegProcedure cmp_proc;
1476 ScanKey low_compare = array->low_compare;
1477 Datum orig_sk_argument = low_compare->sk_argument,
1478 new_sk_argument;
1479 bool oflow;
1480 int16 lookupstrat;
1481
1482 Assert(low_compare->sk_strategy == BTGreaterStrategyNumber);
1483
1484 /*
1485 * Only perform the transformation when the operator type matches the
1486 * index attribute's input opclass type
1487 */
1488 if (low_compare->sk_subtype != opcintype &&
1489 low_compare->sk_subtype != InvalidOid)
1490 return;
1491
1492 /* Increment, handling overflow by marking the qual unsatisfiable */
1493 new_sk_argument = array->sksup->increment(rel, orig_sk_argument, &oflow);
1494 if (oflow)
1495 {
1496 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1497
1498 so->qual_ok = false;
1499 return;
1500 }
1501
1502 /*
1503 * Look up >= operator (might fail), accounting for the fact that a
1504 * low_compare on a DESC column already had its strategy commuted
1505 */
1506 lookupstrat = BTGreaterEqualStrategyNumber;
1507 if (low_compare->sk_flags & SK_BT_DESC)
1508 lookupstrat = BTLessEqualStrategyNumber; /* commute this too */
1509 geop = get_opfamily_member(opfamily, opcintype, opcintype, lookupstrat);
1510 if (!OidIsValid(geop))
1511 return;
1512 cmp_proc = get_opcode(geop);
1513 if (RegProcedureIsValid(cmp_proc))
1514 {
1515 /* Transform > low_compare key into >= key */
1516 fmgr_info(cmp_proc, &low_compare->sk_func);
1517 low_compare->sk_argument = new_sk_argument;
1518 low_compare->sk_strategy = BTGreaterEqualStrategyNumber;
1519 }
1520 }
1521
1522 /*
1523 * _bt_unmark_keys() -- make superfluous required keys nonrequired after all
1524 *
1525 * When _bt_preprocess_keys fails to eliminate one or more redundant keys, it
1526 * calls here to make sure that no index attribute has more than one > or >=
1527 * key marked required, and no more than one required < or <= key. Attributes
1528 * with = keys will always get one = key as their required key. All other
1529 * keys that were initially marked required get "unmarked" here. That way,
1530 * _bt_first and _bt_checkkeys will reliably agree on which keys to use to
1531 * start and/or to end the scan.
1532 *
1533 * We also relocate keys that become/started out nonrequired to the end of
1534 * so->keyData[]. That way, _bt_first and _bt_checkkeys cannot fail to reach
1535 * a required key due to some earlier nonrequired key getting in the way.
1536 *
1537 * Only call here when _bt_compare_scankey_args returned false at least once
1538 * (otherwise, calling here will just waste cycles).
1539 */
1540 static void
1541 _bt_unmark_keys(IndexScanDesc scan, int *keyDataMap)
1542 {
1543 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1544 AttrNumber attno;
1545 bool *unmarkikey;
1546 int nunmark,
1547 nunmarked,
1548 nkept,
1549 firsti;
1550 ScanKey keepKeys,
1551 unmarkKeys;
1552 FmgrInfo *keepOrderProcs = NULL,
1553 *unmarkOrderProcs = NULL;
1554 bool haveReqEquals,
1555 haveReqForward,
1556 haveReqBackward;
1557
1558 /*
1559 * Do an initial pass over so->keyData[] that determines which keys to
1560 * keep as required. We expect so->keyData[] to still be in attribute
1561 * order when we're called (though we don't expect any particular order
1562 * among each attribute's keys).
1563 *
1564 * When both equality and inequality keys remain on a single attribute, we
1565 * *must* make sure that exactly one of the equalities remains required.
1566 * Any requiredness markings that we might leave on later keys/attributes
1567 * are predicated on there being required = keys on all prior columns.
1568 */
1569 unmarkikey = palloc0(so->numberOfKeys * sizeof(bool));
1570 nunmark = 0;
1571
1572 /* Set things up for first key's attribute */
1573 attno = so->keyData[0].sk_attno;
1574 firsti = 0;
1575 haveReqEquals = false;
1576 haveReqForward = false;
1577 haveReqBackward = false;
1578 for (int i = 0; i < so->numberOfKeys; i++)
1579 {
1580 ScanKey origkey = &so->keyData[i];
1581
1582 if (origkey->sk_attno != attno)
1583 {
1584 /* Reset for next attribute */
1585 attno = origkey->sk_attno;
1586 firsti = i;
1587
1588 haveReqEquals = false;
1589 haveReqForward = false;
1590 haveReqBackward = false;
1591 }
1592
1593 /* Equalities get priority over inequalities */
1594 if (haveReqEquals)
1595 {
1596 /*
1597 * We already found the first "=" key for this attribute. We've
1598 * already decided that all its other keys will be unmarked.
1599 */
1600 Assert(!(origkey->sk_flags & SK_SEARCHNULL));
1601 unmarkikey[i] = true;
1602 nunmark++;
1603 continue;
1604 }
1605 else if ((origkey->sk_flags & SK_BT_REQFWD) &&
1606 (origkey->sk_flags & SK_BT_REQBKWD))
1607 {
1608 /*
1609 * Found the first "=" key for attno. All other attno keys will
1610 * be unmarked.
1611 */
1612 Assert(origkey->sk_strategy == BTEqualStrategyNumber);
1613
1614 haveReqEquals = true;
1615 for (int j = firsti; j < i; j++)
1616 {
1617 /* Unmark any prior inequality keys on attno after all */
1618 if (!unmarkikey[j])
1619 {
1620 unmarkikey[j] = true;
1621 nunmark++;
1622 }
1623 }
1624 continue;
1625 }
1626
1627 /* Deal with inequalities next */
1628 if ((origkey->sk_flags & SK_BT_REQFWD) && !haveReqForward)
1629 {
1630 haveReqForward = true;
1631 continue;
1632 }
1633 else if ((origkey->sk_flags & SK_BT_REQBKWD) && !haveReqBackward)
1634 {
1635 haveReqBackward = true;
1636 continue;
1637 }
1638
1639 /*
1640 * We have either a redundant inequality key that will be unmarked, or
1641 * we have a key that wasn't marked required in the first place
1642 */
1643 unmarkikey[i] = true;
1644 nunmark++;
1645 }
1646
1647 /* Should only be called when _bt_compare_scankey_args reported failure */
1648 Assert(nunmark > 0);
1649
1650 /*
1651 * Next, allocate temp arrays: one for required keys that'll remain
1652 * required, the other for all remaining keys
1653 */
1654 unmarkKeys = palloc(nunmark * sizeof(ScanKeyData));
1655 keepKeys = palloc((so->numberOfKeys - nunmark) * sizeof(ScanKeyData));
1656 nunmarked = 0;
1657 nkept = 0;
1658 if (so->numArrayKeys)
1659 {
1660 unmarkOrderProcs = palloc(nunmark * sizeof(FmgrInfo));
1661 keepOrderProcs = palloc((so->numberOfKeys - nunmark) * sizeof(FmgrInfo));
1662 }
1663
1664 /*
1665 * Next, copy the contents of so->keyData[] into the appropriate temp
1666 * array.
1667 *
1668 * Scans with = array keys need us to maintain invariants around the order
1669 * of so->orderProcs[] and so->arrayKeys[] relative to so->keyData[]. See
1670 * _bt_preprocess_array_keys_final for a full explanation.
1671 */
1672 for (int i = 0; i < so->numberOfKeys; i++)
1673 {
1674 ScanKey origkey = &so->keyData[i];
1675 ScanKey unmark;
1676
1677 if (!unmarkikey[i])
1678 {
1679 /*
1680 * Key gets to keep its original requiredness markings.
1681 *
1682 * Key will stay in its original position, unless we're going to
1683 * unmark an earlier key (in which case this key gets moved back).
1684 */
1685 memcpy(keepKeys + nkept, origkey, sizeof(ScanKeyData));
1686
1687 if (so->numArrayKeys)
1688 {
1689 keyDataMap[i] = nkept;
1690 memcpy(keepOrderProcs + nkept, &so->orderProcs[i],
1691 sizeof(FmgrInfo));
1692 }
1693
1694 nkept++;
1695 continue;
1696 }
1697
1698 /*
1699 * Key will be unmarked as needed, and moved to the end of the array,
1700 * next to other keys that will become (or always were) nonrequired
1701 */
1702 unmark = unmarkKeys + nunmarked;
1703 memcpy(unmark, origkey, sizeof(ScanKeyData));
1704
1705 if (so->numArrayKeys)
1706 {
1707 keyDataMap[i] = (so->numberOfKeys - nunmark) + nunmarked;
1708 memcpy(&unmarkOrderProcs[nunmarked], &so->orderProcs[i],
1709 sizeof(FmgrInfo));
1710 }
1711
1712 /*
1713 * Preprocessing only generates skip arrays when it knows that they'll
1714 * be the only required = key on the attr. We'll never unmark them.
1715 */
1716 Assert(!(unmark->sk_flags & SK_BT_SKIP));
1717
1718 /*
1719 * Also shouldn't have to unmark an IS NULL or an IS NOT NULL key.
1720 * They aren't cross-type, so an incomplete opfamily can't matter.
1721 */
1722 Assert(!(unmark->sk_flags & SK_ISNULL) ||
1723 !(unmark->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)));
1724
1725 /* Clear requiredness flags on redundant key (and on any subkeys) */
1726 unmark->sk_flags &= ~(SK_BT_REQFWD | SK_BT_REQBKWD);
1727 if (unmark->sk_flags & SK_ROW_HEADER)
1728 {
1729 ScanKey subkey = (ScanKey) DatumGetPointer(unmark->sk_argument);
1730
1731 Assert(subkey->sk_strategy == unmark->sk_strategy);
1732 for (;;)
1733 {
1734 Assert(subkey->sk_flags & SK_ROW_MEMBER);
1735 subkey->sk_flags &= ~(SK_BT_REQFWD | SK_BT_REQBKWD);
1736 if (subkey->sk_flags & SK_ROW_END)
1737 break;
1738 subkey++;
1739 }
1740 }
1741
1742 nunmarked++;
1743 }
1744
1745 /* Copy both temp arrays back into so->keyData[] to reorder */
1746 Assert(nkept == so->numberOfKeys - nunmark);
1747 Assert(nunmarked == nunmark);
1748 memcpy(so->keyData, keepKeys, sizeof(ScanKeyData) * nkept);
1749 memcpy(so->keyData + nkept, unmarkKeys, sizeof(ScanKeyData) * nunmarked);
1750
1751 /* Done with temp arrays */
1752 pfree(unmarkikey);
1753 pfree(keepKeys);
1754 pfree(unmarkKeys);
1755
1756 /*
1757 * Now copy so->orderProcs[] temp entries needed by scans with = array
1758 * keys back (just like with the so->keyData[] temp arrays)
1759 */
1760 if (so->numArrayKeys)
1761 {
1762 memcpy(so->orderProcs, keepOrderProcs, sizeof(FmgrInfo) * nkept);
1763 memcpy(so->orderProcs + nkept, unmarkOrderProcs,
1764 sizeof(FmgrInfo) * nunmarked);
1765
1766 /* Also fix-up array->scan_key references */
1767 for (int arridx = 0; arridx < so->numArrayKeys; arridx++)
1768 {
1769 BTArrayKeyInfo *array = &so->arrayKeys[arridx];
1770
1771 array->scan_key = keyDataMap[array->scan_key];
1772 }
1773
1774 /*
1775 * Sort so->arrayKeys[] based on its new BTArrayKeyInfo.scan_key
1776 * offsets, so that its order matches so->keyData[] order as expected
1777 */
1778 qsort(so->arrayKeys, so->numArrayKeys, sizeof(BTArrayKeyInfo),
1779 _bt_reorder_array_cmp);
1780
1781 /* Done with temp arrays */
1782 pfree(unmarkOrderProcs);
1783 pfree(keepOrderProcs);
1784 }
1785 }
1786
1787 /*
1788 * qsort comparator for reordering so->arrayKeys[] BTArrayKeyInfo entries
1789 */
1790 static int
1791 _bt_reorder_array_cmp(const void *a, const void *b)
1792 {
1793 BTArrayKeyInfo *arraya = (BTArrayKeyInfo *) a;
1794 BTArrayKeyInfo *arrayb = (BTArrayKeyInfo *) b;
1795
1796 return pg_cmp_s32(arraya->scan_key, arrayb->scan_key);
1797 }
1798
1799 /*
1800 * _bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys
1801 *
1802 * If there are any SK_SEARCHARRAY scan keys, deconstruct the array(s) and
1803 * set up BTArrayKeyInfo info for each one that is an equality-type key.
1804 * Returns modified scan keys as input for further, standard preprocessing.
1805 *
1806 * Currently we perform two kinds of preprocessing to deal with redundancies.
1807 * For inequality array keys, it's sufficient to find the extreme element
1808 * value and replace the whole array with that scalar value. This eliminates
1809 * all but one array element as redundant. Similarly, we are capable of
1810 * "merging together" multiple equality array keys (from two or more input
1811 * scan keys) into a single output scan key containing only the intersecting
1812 * array elements. This can eliminate many redundant array elements, as well
1813 * as eliminating whole array scan keys as redundant. It can also allow us to
1814 * detect contradictory quals.
1815 *
1816 * Caller must pass *new_numberOfKeys to give us a way to change the number of
1817 * scan keys that caller treats as input to standard preprocessing steps. The
1818 * returned array is smaller than scan->keyData[] when we could eliminate a
1819 * redundant array scan key (redundant with another array scan key). It is
1820 * convenient for _bt_preprocess_keys caller to have to deal with no more than
1821 * one equality strategy array scan key per index attribute. We'll always be
1822 * able to set things up that way when complete opfamilies are used.
1823 *
1824 * We're also responsible for generating skip arrays (and their associated
1825 * scan keys) here. This enables skip scan. We do this for index attributes
1826 * that initially lacked an equality condition within scan->keyData[], iff
1827 * doing so allows a later scan key (that was passed to us in scan->keyData[])
1828 * to be marked required by our _bt_preprocess_keys caller.
1829 *
1830 * We set the scan key references from the scan's BTArrayKeyInfo info array to
1831 * offsets into the temp modified input array returned to caller. Scans that
1832 * have array keys should call _bt_preprocess_array_keys_final when standard
1833 * preprocessing steps are complete. This will convert the scan key offset
1834 * references into references to the scan's so->keyData[] output scan keys.
1835 *
1836 * Note: the reason we need to return a temp scan key array, rather than just
1837 * modifying scan->keyData[], is that callers are permitted to call btrescan
1838 * without supplying a new set of scankey data. Certain other preprocessing
1839 * routines (e.g., _bt_fix_scankey_strategy) _can_ modify scan->keyData[], but
1840 * we can't make that work here because our modifications are non-idempotent.
1841 */
1842 static ScanKey
1843 _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
1844 {
1845 BTScanOpaque so = (BTScanOpaque) scan->opaque;
1846 Relation rel = scan->indexRelation;
1847 int16 *indoption = rel->rd_indoption;
1848 Oid skip_eq_ops[INDEX_MAX_KEYS];
1849 int numArrayKeys,
1850 numSkipArrayKeys,
1851 numArrayKeyData;
1852 AttrNumber attno_skip = 1;
1853 int origarrayatt = InvalidAttrNumber,
1854 origarraykey = -1;
1855 Oid origelemtype = InvalidOid;
1856 MemoryContext oldContext;
1857 ScanKey arrayKeyData; /* modified copy of scan->keyData */
1858
1859 /*
1860 * Check the number of input array keys within scan->keyData[] input keys
1861 * (also checks if we should add extra skip arrays based on input keys)
1862 */
1863 numArrayKeys = _bt_num_array_keys(scan, skip_eq_ops, &numSkipArrayKeys);
1864 so->skipScan = (numSkipArrayKeys > 0);
1865
1866 /* Quit if nothing to do. */
1867 if (numArrayKeys == 0)
1868 return NULL;
1869
1870 /*
1871 * Estimated final size of arrayKeyData[] array we'll return to our caller
1872 * is the size of the original scan->keyData[] input array, plus space for
1873 * any additional skip array scan keys we'll need to generate below
1874 */
1875 numArrayKeyData = scan->numberOfKeys + numSkipArrayKeys;
1876
1877 /*
1878 * Make a scan-lifespan context to hold array-associated data, or reset it
1879 * if we already have one from a previous rescan cycle.
1880 */
1881 if (so->arrayContext == NULL)
1882 so->arrayContext = AllocSetContextCreate(CurrentMemoryContext,
1883 "BTree array context",
1884 ALLOCSET_SMALL_SIZES);
1885 else
1886 MemoryContextReset(so->arrayContext);
1887
1888 oldContext = MemoryContextSwitchTo(so->arrayContext);
1889
1890 /* Create output scan keys in the workspace context */
1891 arrayKeyData = (ScanKey) palloc(numArrayKeyData * sizeof(ScanKeyData));
1892
1893 /* Allocate space for per-array data in the workspace context */
1894 so->arrayKeys = (BTArrayKeyInfo *) palloc(numArrayKeys * sizeof(BTArrayKeyInfo));
1895
1896 /* Allocate space for ORDER procs used to help _bt_checkkeys */
1897 so->orderProcs = (FmgrInfo *) palloc(numArrayKeyData * sizeof(FmgrInfo));
1898
1899 numArrayKeys = 0;
1900 numArrayKeyData = 0;
1901 for (int input_ikey = 0; input_ikey < scan->numberOfKeys; input_ikey++)
1902 {
1903 ScanKey inkey = scan->keyData + input_ikey,
1904 cur;
1905 FmgrInfo sortproc;
1906 FmgrInfo *sortprocp = &sortproc;
1907 Oid elemtype;
1908 bool reverse;
1909 ArrayType *arrayval;
1910 int16 elmlen;
1911 bool elmbyval;
1912 char elmalign;
1913 int num_elems;
1914 Datum *elem_values;
1915 bool *elem_nulls;
1916 int num_nonnulls;
1917
1918 /* set up next output scan key */
1919 cur = &arrayKeyData[numArrayKeyData];
1920
1921 /* Backfill skip arrays for attrs < or <= input key's attr? */
1922 while (numSkipArrayKeys && attno_skip <= inkey->sk_attno)
1923 {
1924 Oid opfamily = rel->rd_opfamily[attno_skip - 1];
1925 Oid opcintype = rel->rd_opcintype[attno_skip - 1];
1926 Oid collation = rel->rd_indcollation[attno_skip - 1];
1927 Oid eq_op = skip_eq_ops[attno_skip - 1];
1928 CompactAttribute *attr;
1929 RegProcedure cmp_proc;
1930
1931 if (!OidIsValid(eq_op))
1932 {
1933 /*
1934 * Attribute already has an = input key, so don't output a
1935 * skip array for attno_skip. Just copy attribute's = input
1936 * key into arrayKeyData[] once outside this inner loop.
1937 *
1938 * Note: When we get here there must be a later attribute that
1939 * lacks an equality input key, and still needs a skip array
1940 * (if there wasn't then numSkipArrayKeys would be 0 by now).
1941 */
1942 Assert(attno_skip == inkey->sk_attno);
1943 /* inkey can't be last input key to be marked required: */
1944 Assert(input_ikey < scan->numberOfKeys - 1);
1945 #if 0
1946 /* Could be a redundant input scan key, so can't do this: */
1947 Assert(inkey->sk_strategy == BTEqualStrategyNumber ||
1948 (inkey->sk_flags & SK_SEARCHNULL));
1949 #endif
1950
1951 attno_skip++;
1952 break;
1953 }
1954
1955 cmp_proc = get_opcode(eq_op);
1956 if (!RegProcedureIsValid(cmp_proc))
1957 elog(ERROR, "missing oprcode for skipping equals operator %u", eq_op);
1958
1959 ScanKeyEntryInitialize(cur,
1960 SK_SEARCHARRAY | SK_BT_SKIP, /* flags */
1961 attno_skip, /* skipped att number */
1962 BTEqualStrategyNumber, /* equality strategy */
1963 InvalidOid, /* opclass input subtype */
1964 collation, /* index column's collation */
1965 cmp_proc, /* equality operator's proc */
1966 (Datum) 0); /* constant */
1967
1968 /* Initialize generic BTArrayKeyInfo fields */
1969 so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
1970 so->arrayKeys[numArrayKeys].num_elems = -1;
1971
1972 /* Initialize skip array specific BTArrayKeyInfo fields */
1973 attr = TupleDescCompactAttr(RelationGetDescr(rel), attno_skip - 1);
1974 reverse = (indoption[attno_skip - 1] & INDOPTION_DESC) != 0;
1975 so->arrayKeys[numArrayKeys].attlen = attr->attlen;
1976 so->arrayKeys[numArrayKeys].attbyval = attr->attbyval;
1977 so->arrayKeys[numArrayKeys].null_elem = true; /* for now */
1978 so->arrayKeys[numArrayKeys].sksup =
1979 PrepareSkipSupportFromOpclass(opfamily, opcintype, reverse);
1980 so->arrayKeys[numArrayKeys].low_compare = NULL; /* for now */
1981 so->arrayKeys[numArrayKeys].high_compare = NULL; /* for now */
1982
1983 /*
1984 * We'll need a 3-way ORDER proc. Set that up now.
1985 */
1986 _bt_setup_array_cmp(scan, cur, opcintype,
1987 &so->orderProcs[numArrayKeyData], NULL);
1988
1989 numArrayKeys++;
1990 numArrayKeyData++; /* keep this scan key/array */
1991
1992 /* set up next output scan key */
1993 cur = &arrayKeyData[numArrayKeyData];
1994
1995 /* remember having output this skip array and scan key */
1996 numSkipArrayKeys--;
1997 attno_skip++;
1998 }
1999
2000 /*
2001 * Provisionally copy scan key into arrayKeyData[] array we'll return
2002 * to _bt_preprocess_keys caller
2003 */
2004 *cur = *inkey;
2005
2006 if (!(cur->sk_flags & SK_SEARCHARRAY))
2007 {
2008 numArrayKeyData++; /* keep this non-array scan key */
2009 continue;
2010 }
2011
2012 /*
2013 * Process SAOP array scan key
2014 */
2015 Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
2016
2017 /* If array is null as a whole, the scan qual is unsatisfiable */
2018 if (cur->sk_flags & SK_ISNULL)
2019 {
2020 so->qual_ok = false;
2021 break;
2022 }
2023
2024 /*
2025 * Deconstruct the array into elements
2026 */
2027 arrayval = DatumGetArrayTypeP(cur->sk_argument);
2028 /* We could cache this data, but not clear it's worth it */
2029 get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
2030 &elmlen, &elmbyval, &elmalign);
2031 deconstruct_array(arrayval,
2032 ARR_ELEMTYPE(arrayval),
2033 elmlen, elmbyval, elmalign,
2034 &elem_values, &elem_nulls, &num_elems);
2035
2036 /*
2037 * Compress out any null elements. We can ignore them since we assume
2038 * all btree operators are strict.
2039 */
2040 num_nonnulls = 0;
2041 for (int j = 0; j < num_elems; j++)
2042 {
2043 if (!elem_nulls[j])
2044 elem_values[num_nonnulls++] = elem_values[j];
2045 }
2046
2047 /* We could pfree(elem_nulls) now, but not worth the cycles */
2048
2049 /* If there's no non-nulls, the scan qual is unsatisfiable */
2050 if (num_nonnulls == 0)
2051 {
2052 so->qual_ok = false;
2053 break;
2054 }
2055
2056 /*
2057 * Determine the nominal datatype of the array elements. We have to
2058 * support the convention that sk_subtype == InvalidOid means the
2059 * opclass input type; this is a hack to simplify life for
2060 * ScanKeyInit().
2061 */
2062 elemtype = cur->sk_subtype;
2063 if (elemtype == InvalidOid)
2064 elemtype = rel->rd_opcintype[cur->sk_attno - 1];
2065
2066 /*
2067 * If the comparison operator is not equality, then the array qual
2068 * degenerates to a simple comparison against the smallest or largest
2069 * non-null array element, as appropriate.
2070 */
2071 switch (cur->sk_strategy)
2072 {
2073 case BTLessStrategyNumber:
2074 case BTLessEqualStrategyNumber:
2075 cur->sk_argument =
2076 _bt_find_extreme_element(scan, cur, elemtype,
2077 BTGreaterStrategyNumber,
2078 elem_values, num_nonnulls);
2079 numArrayKeyData++; /* keep this transformed scan key */
2080 continue;
2081 case BTEqualStrategyNumber:
2082 /* proceed with rest of loop */
2083 break;
2084 case BTGreaterEqualStrategyNumber:
2085 case BTGreaterStrategyNumber:
2086 cur->sk_argument =
2087 _bt_find_extreme_element(scan, cur, elemtype,
2088 BTLessStrategyNumber,
2089 elem_values, num_nonnulls);
2090 numArrayKeyData++; /* keep this transformed scan key */
2091 continue;
2092 default:
2093 elog(ERROR, "unrecognized StrategyNumber: %d",
2094 (int) cur->sk_strategy);
2095 break;
2096 }
2097
2098 /*
2099 * We'll need a 3-way ORDER proc to perform binary searches for the
2100 * next matching array element. Set that up now.
2101 *
2102 * Array scan keys with cross-type equality operators will require a
2103 * separate same-type ORDER proc for sorting their array. Otherwise,
2104 * sortproc just points to the same proc used during binary searches.
2105 */
2106 _bt_setup_array_cmp(scan, cur, elemtype,
2107 &so->orderProcs[numArrayKeyData], &sortprocp);
2108
2109 /*
2110 * Sort the non-null elements and eliminate any duplicates. We must
2111 * sort in the same ordering used by the index column, so that the
2112 * arrays can be advanced in lockstep with the scan's progress through
2113 * the index's key space.
2114 */
2115 reverse = (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0;
2116 num_elems = _bt_sort_array_elements(cur, sortprocp, reverse,
2117 elem_values, num_nonnulls);
2118
2119 if (origarrayatt == cur->sk_attno)
2120 {
2121 BTArrayKeyInfo *orig = &so->arrayKeys[origarraykey];
2122
2123 /*
2124 * This array scan key is redundant with a previous equality
2125 * operator array scan key. Merge the two arrays together to
2126 * eliminate contradictory non-intersecting elements (or try to).
2127 *
2128 * We merge this next array back into attribute's original array.
2129 */
2130 Assert(arrayKeyData[orig->scan_key].sk_attno == cur->sk_attno);
2131 Assert(arrayKeyData[orig->scan_key].sk_collation ==
2132 cur->sk_collation);
2133 if (_bt_merge_arrays(scan, cur, sortprocp, reverse,
2134 origelemtype, elemtype,
2135 orig->elem_values, &orig->num_elems,
2136 elem_values, num_elems))
2137 {
2138 /* Successfully eliminated this array */
2139 pfree(elem_values);
2140
2141 /*
2142 * If no intersecting elements remain in the original array,
2143 * the scan qual is unsatisfiable
2144 */
2145 if (orig->num_elems == 0)
2146 {
2147 so->qual_ok = false;
2148 break;
2149 }
2150
2151 /* Throw away this scan key/array */
2152 continue;
2153 }
2154
2155 /*
2156 * Unable to merge this array with previous array due to a lack of
2157 * suitable cross-type opfamily support. Will need to keep both
2158 * scan keys/arrays.
2159 */
2160 }
2161 else
2162 {
2163 /*
2164 * This array is the first for current index attribute.
2165 *
2166 * If it turns out to not be the last array (that is, if the next
2167 * array is redundantly applied to this same index attribute),
2168 * we'll then treat this array as the attribute's "original" array
2169 * when merging.
2170 */
2171 origarrayatt = cur->sk_attno;
2172 origarraykey = numArrayKeys;
2173 origelemtype = elemtype;
2174 }
2175
2176 /* Initialize generic BTArrayKeyInfo fields */
2177 so->arrayKeys[numArrayKeys].scan_key = numArrayKeyData;
2178 so->arrayKeys[numArrayKeys].num_elems = num_elems;
2179
2180 /* Initialize SAOP array specific BTArrayKeyInfo fields */
2181 so->arrayKeys[numArrayKeys].elem_values = elem_values;
2182 so->arrayKeys[numArrayKeys].cur_elem = -1; /* i.e. invalid */
2183
2184 numArrayKeys++;
2185 numArrayKeyData++; /* keep this scan key/array */
2186 }
2187
2188 Assert(numSkipArrayKeys == 0 || !so->qual_ok);
2189
2190 /* Set final number of equality-type array keys */
2191 so->numArrayKeys = numArrayKeys;
2192 /* Set number of scan keys in arrayKeyData[] */
2193 *new_numberOfKeys = numArrayKeyData;
2194
2195 MemoryContextSwitchTo(oldContext);
2196
2197 return arrayKeyData;
2198 }
2199
2200 /*
2201 * _bt_preprocess_array_keys_final() -- fix up array scan key references
2202 *
2203 * When _bt_preprocess_array_keys performed initial array preprocessing, it
2204 * set each array's array->scan_key to its scankey's arrayKeyData[] offset.
2205 * This function handles translation of the scan key references from the
2206 * BTArrayKeyInfo info array, from input scan key references (to the keys in
2207 * arrayKeyData[]), into output references (to the keys in so->keyData[]).
2208 * Caller's keyDataMap[] array tells us how to perform this remapping.
2209 *
2210 * Also finalizes so->orderProcs[] for the scan. Arrays already have an ORDER
2211 * proc, which might need to be repositioned to its so->keyData[]-wise offset
2212 * (very much like the remapping that we apply to array->scan_key references).
2213 * Non-array equality strategy scan keys (that survived preprocessing) don't
2214 * yet have an so->orderProcs[] entry, so we set one for them here.
2215 *
2216 * Also converts single-element array scan keys into equivalent non-array
2217 * equality scan keys, which decrements so->numArrayKeys. It's possible that
2218 * this will leave this new btrescan without any arrays at all. This isn't
2219 * necessary for correctness; it's just an optimization. Non-array equality
2220 * scan keys are slightly faster than equivalent array scan keys at runtime.
2221 */
2222 static void
2223 _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
2224 {
2225 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2226 Relation rel = scan->indexRelation;
2227 int arrayidx = 0;
2228 int last_equal_output_ikey PG_USED_FOR_ASSERTS_ONLY = -1;
2229
2230 Assert(so->qual_ok);
2231
2232 /*
2233 * Nothing for us to do when _bt_preprocess_array_keys only had to deal
2234 * with array inequalities
2235 */
2236 if (so->numArrayKeys == 0)
2237 return;
2238
2239 for (int output_ikey = 0; output_ikey < so->numberOfKeys; output_ikey++)
2240 {
2241 ScanKey outkey = so->keyData + output_ikey;
2242 int input_ikey;
2243 bool found PG_USED_FOR_ASSERTS_ONLY = false;
2244
2245 Assert(outkey->sk_strategy != InvalidStrategy);
2246
2247 if (outkey->sk_strategy != BTEqualStrategyNumber)
2248 continue;
2249
2250 input_ikey = keyDataMap[output_ikey];
2251
2252 Assert(last_equal_output_ikey < output_ikey);
2253 Assert(last_equal_output_ikey < input_ikey);
2254 last_equal_output_ikey = output_ikey;
2255
2256 /*
2257 * We're lazy about looking up ORDER procs for non-array keys, since
2258 * not all input keys become output keys. Take care of it now.
2259 */
2260 if (!(outkey->sk_flags & SK_SEARCHARRAY))
2261 {
2262 Oid elemtype;
2263
2264 /* No need for an ORDER proc given an IS NULL scan key */
2265 if (outkey->sk_flags & SK_SEARCHNULL)
2266 continue;
2267
2268 /*
2269 * A non-required scan key doesn't need an ORDER proc, either
2270 * (unless it's associated with an array, which this one isn't)
2271 */
2272 if (!(outkey->sk_flags & SK_BT_REQFWD))
2273 continue;
2274
2275 elemtype = outkey->sk_subtype;
2276 if (elemtype == InvalidOid)
2277 elemtype = rel->rd_opcintype[outkey->sk_attno - 1];
2278
2279 _bt_setup_array_cmp(scan, outkey, elemtype,
2280 &so->orderProcs[output_ikey], NULL);
2281 continue;
2282 }
2283
2284 /*
2285 * Reorder existing array scan key so->orderProcs[] entries.
2286 *
2287 * Doing this in-place is safe because preprocessing is required to
2288 * output all equality strategy scan keys in original input order
2289 * (among each group of entries against the same index attribute).
2290 * This is also the order that the arrays themselves appear in.
2291 */
2292 so->orderProcs[output_ikey] = so->orderProcs[input_ikey];
2293
2294 /* Fix-up array->scan_key references for arrays */
2295 for (; arrayidx < so->numArrayKeys; arrayidx++)
2296 {
2297 BTArrayKeyInfo *array = &so->arrayKeys[arrayidx];
2298
2299 /*
2300 * All skip arrays must be marked required, and final column can
2301 * never have a skip array
2302 */
2303 Assert(array->num_elems > 0 || array->num_elems == -1);
2304 Assert(array->num_elems != -1 || outkey->sk_flags & SK_BT_REQFWD);
2305 Assert(array->num_elems != -1 ||
2306 outkey->sk_attno < IndexRelationGetNumberOfKeyAttributes(rel));
2307
2308 if (array->scan_key == input_ikey)
2309 {
2310 /* found it */
2311 array->scan_key = output_ikey;
2312 found = true;
2313
2314 /*
2315 * Transform array scan keys that have exactly 1 element
2316 * remaining (following all prior preprocessing) into
2317 * equivalent non-array scan keys.
2318 */
2319 if (array->num_elems == 1)
2320 {
2321 outkey->sk_flags &= ~SK_SEARCHARRAY;
2322 outkey->sk_argument = array->elem_values[0];
2323 so->numArrayKeys--;
2324
2325 /* If we're out of array keys, we can quit right away */
2326 if (so->numArrayKeys == 0)
2327 return;
2328
2329 /* Shift other arrays forward */
2330 memmove(array, array + 1,
2331 sizeof(BTArrayKeyInfo) *
2332 (so->numArrayKeys - arrayidx));
2333
2334 /*
2335 * Don't increment arrayidx (there was an entry that was
2336 * just shifted forward to the offset at arrayidx, which
2337 * will still need to be matched)
2338 */
2339 }
2340 else
2341 {
2342 /*
2343 * Any skip array low_compare and high_compare scan keys
2344 * are now final. Transform the array's > low_compare key
2345 * into a >= key (and < high_compare keys into a <= key).
2346 */
2347 if (array->num_elems == -1 && array->sksup &&
2348 !array->null_elem)
2349 _bt_skiparray_strat_adjust(scan, outkey, array);
2350
2351 /* Match found, so done with this array */
2352 arrayidx++;
2353 }
2354
2355 break;
2356 }
2357 }
2358
2359 Assert(found);
2360 }
2361
2362 /*
2363 * Parallel index scans require space in shared memory to store the
2364 * current array elements (for arrays kept by preprocessing) to schedule
2365 * the next primitive index scan. The underlying structure is protected
2366 * using an LWLock, so defensively limit its size. In practice this can
2367 * only affect parallel scans that use an incomplete opfamily.
2368 */
2369 if (scan->parallel_scan && so->numArrayKeys > INDEX_MAX_KEYS)
2370 ereport(ERROR,
2371 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2372 errmsg_internal("number of array scan keys left by preprocessing (%d) exceeds the maximum allowed by parallel btree index scans (%d)",
2373 so->numArrayKeys, INDEX_MAX_KEYS)));
2374 }
2375
2376 /*
2377 * _bt_num_array_keys() -- determine # of BTArrayKeyInfo entries
2378 *
2379 * _bt_preprocess_array_keys helper function. Returns the estimated size of
2380 * the scan's BTArrayKeyInfo array, which is guaranteed to be large enough to
2381 * fit every so->arrayKeys[] entry.
2382 *
2383 * Also sets *numSkipArrayKeys_out to the number of skip arrays caller must
2384 * add to the scan keys it'll output. Caller must add this many skip arrays:
2385 * one array for each of the most significant attributes that lack a = input
2386 * key (IS NULL keys count as = input keys here). The specific attributes
2387 * that need skip arrays are indicated by initializing skip_eq_ops_out[] arg
2388 * 0-based attribute offset to a valid = op strategy Oid. We'll only ever set
2389 * skip_eq_ops_out[] entries to InvalidOid for attributes that already have an
2390 * equality key in scan->keyData[] input keys -- and only when there's some
2391 * later "attribute gap" for us to "fill-in" with a skip array.
2392 *
2393 * We're optimistic about skipping working out: we always add exactly the skip
2394 * arrays needed to maximize the number of input scan keys that can ultimately
2395 * be marked as required to continue the scan (but no more). Given a
2396 * multi-column index on (a, b, c, d), we add skip arrays as follows:
2397 *
2398 * Input keys Output keys (after all preprocessing)
2399 * ---------- -------------------------------------
2400 * a = 1 a = 1 (no skip arrays)
2401 * b = 42 skip a AND b = 42
2402 * a = 1 AND b = 42 a = 1 AND b = 42 (no skip arrays)
2403 * a >= 1 AND b = 42 range skip a AND b = 42
2404 * a = 1 AND b > 42 a = 1 AND b > 42 (no skip arrays)
2405 * a >= 1 AND a <= 3 AND b = 42 range skip a AND b = 42
2406 * a = 1 AND c <= 27 a = 1 AND skip b AND c <= 27
2407 * a = 1 AND d >= 1 a = 1 AND skip b AND skip c AND d >= 1
2408 * a = 1 AND b >= 42 AND d > 1 a = 1 AND range skip b AND skip c AND d > 1
2409 */
2410 static int
2411 _bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out,
2412 int *numSkipArrayKeys_out)
2413 {
2414 Relation rel = scan->indexRelation;
2415 AttrNumber attno_skip = 1,
2416 attno_inkey = 1;
2417 bool attno_has_equal = false,
2418 attno_has_rowcompare = false;
2419 int numSAOPArrayKeys,
2420 numSkipArrayKeys,
2421 prev_numSkipArrayKeys;
2422
2423 Assert(scan->numberOfKeys);
2424
2425 /* Initial pass over input scan keys counts the number of SAOP arrays */
2426 numSAOPArrayKeys = 0;
2427 *numSkipArrayKeys_out = prev_numSkipArrayKeys = numSkipArrayKeys = 0;
2428 for (int i = 0; i < scan->numberOfKeys; i++)
2429 {
2430 ScanKey inkey = scan->keyData + i;
2431
2432 if (inkey->sk_flags & SK_SEARCHARRAY)
2433 numSAOPArrayKeys++;
2434 }
2435
2436 #ifdef DEBUG_DISABLE_SKIP_SCAN
2437 /* don't attempt to add skip arrays */
2438 return numSAOPArrayKeys;
2439 #endif
2440
2441 for (int i = 0;; i++)
2442 {
2443 ScanKey inkey = scan->keyData + i;
2444
2445 /*
2446 * Backfill skip arrays for any wholly omitted attributes prior to
2447 * attno_inkey
2448 */
2449 while (attno_skip < attno_inkey)
2450 {
2451 Oid opfamily = rel->rd_opfamily[attno_skip - 1];
2452 Oid opcintype = rel->rd_opcintype[attno_skip - 1];
2453
2454 /* Look up input opclass's equality operator (might fail) */
2455 skip_eq_ops_out[attno_skip - 1] =
2456 get_opfamily_member(opfamily, opcintype, opcintype,
2457 BTEqualStrategyNumber);
2458 if (!OidIsValid(skip_eq_ops_out[attno_skip - 1]))
2459 {
2460 /*
2461 * Cannot generate a skip array for this or later attributes
2462 * (input opclass lacks an equality strategy operator)
2463 */
2464 *numSkipArrayKeys_out = prev_numSkipArrayKeys;
2465 return numSAOPArrayKeys + prev_numSkipArrayKeys;
2466 }
2467
2468 /* plan on adding a backfill skip array for this attribute */
2469 numSkipArrayKeys++;
2470 attno_skip++;
2471 }
2472
2473 prev_numSkipArrayKeys = numSkipArrayKeys;
2474
2475 /*
2476 * Stop once past the final input scan key. We deliberately never add
2477 * a skip array for the last input scan key's attribute -- even when
2478 * there are only inequality keys on that attribute.
2479 */
2480 if (i == scan->numberOfKeys)
2481 break;
2482
2483 /*
2484 * Later preprocessing steps cannot merge a RowCompare into a skip
2485 * array, so stop adding skip arrays once we see one. (Note that we
2486 * can backfill skip arrays before a RowCompare, which will allow keys
2487 * up to and including the RowCompare to be marked required.)
2488 *
2489 * Skip arrays work by maintaining a current array element value,
2490 * which anchors lower-order keys via an implied equality constraint.
2491 * This is incompatible with the current nbtree row comparison design,
2492 * which compares all columns together, as an indivisible group.
2493 * Alternative designs that can be used alongside skip arrays are
2494 * possible, but it's not clear that they're really worth pursuing.
2495 *
2496 * A RowCompare qual "(a, b, c) > (10, 'foo', 42)" is equivalent to
2497 * "(a=10 AND b='foo' AND c>42) OR (a=10 AND b>'foo') OR (a>10)".
2498 * Decomposing this RowCompare into these 3 disjuncts allows each
2499 * disjunct to be executed as a separate "single value" index scan.
2500 * That'll give all 3 scans the ability to add skip arrays in the
2501 * usual way (when there are any scalar keys after the RowCompare).
2502 * Under this scheme, a qual "(a, b, c) > (10, 'foo', 42) AND d = 99"
2503 * performs 3 separate scans, each of which can mark keys up to and
2504 * including its "d = 99" key as required to continue the scan.
2505 */
2506 if (attno_has_rowcompare)
2507 break;
2508
2509 /*
2510 * Now consider next attno_inkey (or keep going if this is an
2511 * additional scan key against the same attribute)
2512 */
2513 if (attno_inkey < inkey->sk_attno)
2514 {
2515 /*
2516 * Now add skip array for previous scan key's attribute, though
2517 * only if the attribute has no equality strategy scan keys
2518 */
2519 if (attno_has_equal)
2520 {
2521 /* Attributes with an = key must have InvalidOid eq_op set */
2522 skip_eq_ops_out[attno_skip - 1] = InvalidOid;
2523 }
2524 else
2525 {
2526 Oid opfamily = rel->rd_opfamily[attno_skip - 1];
2527 Oid opcintype = rel->rd_opcintype[attno_skip - 1];
2528
2529 /* Look up input opclass's equality operator (might fail) */
2530 skip_eq_ops_out[attno_skip - 1] =
2531 get_opfamily_member(opfamily, opcintype, opcintype,
2532 BTEqualStrategyNumber);
2533
2534 if (!OidIsValid(skip_eq_ops_out[attno_skip - 1]))
2535 {
2536 /*
2537 * Input opclass lacks an equality strategy operator, so
2538 * don't generate a skip array that definitely won't work
2539 */
2540 break;
2541 }
2542
2543 /* plan on adding a backfill skip array for this attribute */
2544 numSkipArrayKeys++;
2545 }
2546
2547 /* Set things up for this new attribute */
2548 attno_skip++;
2549 attno_inkey = inkey->sk_attno;
2550 attno_has_equal = false;
2551 }
2552
2553 /*
2554 * Track if this attribute's scan keys include any equality strategy
2555 * scan keys (IS NULL keys count as equality keys here). Also track
2556 * if it has any RowCompare keys.
2557 */
2558 if (inkey->sk_strategy == BTEqualStrategyNumber ||
2559 (inkey->sk_flags & SK_SEARCHNULL))
2560 attno_has_equal = true;
2561 if (inkey->sk_flags & SK_ROW_HEADER)
2562 attno_has_rowcompare = true;
2563 }
2564
2565 *numSkipArrayKeys_out = numSkipArrayKeys;
2566 return numSAOPArrayKeys + numSkipArrayKeys;
2567 }
2568
2569 /*
2570 * _bt_find_extreme_element() -- get least or greatest array element
2571 *
2572 * scan and skey identify the index column, whose opfamily determines the
2573 * comparison semantics. strat should be BTLessStrategyNumber to get the
2574 * least element, or BTGreaterStrategyNumber to get the greatest.
2575 */
2576 static Datum
2577 _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey, Oid elemtype,
2578 StrategyNumber strat,
2579 Datum *elems, int nelems)
2580 {
2581 Relation rel = scan->indexRelation;
2582 Oid cmp_op;
2583 RegProcedure cmp_proc;
2584 FmgrInfo flinfo;
2585 Datum result;
2586 int i;
2587
2588 /*
2589 * Look up the appropriate comparison operator in the opfamily.
2590 *
2591 * Note: it's possible that this would fail, if the opfamily is
2592 * incomplete, but it seems quite unlikely that an opfamily would omit
2593 * non-cross-type comparison operators for any datatype that it supports
2594 * at all.
2595 */
2596 Assert(skey->sk_strategy != BTEqualStrategyNumber);
2597 Assert(OidIsValid(elemtype));
2598 cmp_op = get_opfamily_member(rel->rd_opfamily[skey->sk_attno - 1],
2599 elemtype,
2600 elemtype,
2601 strat);
2602 if (!OidIsValid(cmp_op))
2603 elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
2604 strat, elemtype, elemtype,
2605 rel->rd_opfamily[skey->sk_attno - 1]);
2606 cmp_proc = get_opcode(cmp_op);
2607 if (!RegProcedureIsValid(cmp_proc))
2608 elog(ERROR, "missing oprcode for operator %u", cmp_op);
2609
2610 fmgr_info(cmp_proc, &flinfo);
2611
2612 Assert(nelems > 0);
2613 result = elems[0];
2614 for (i = 1; i < nelems; i++)
2615 {
2616 if (DatumGetBool(FunctionCall2Coll(&flinfo,
2617 skey->sk_collation,
2618 elems[i],
2619 result)))
2620 result = elems[i];
2621 }
2622
2623 return result;
2624 }
2625
2626 /*
2627 * _bt_setup_array_cmp() -- Set up array comparison functions
2628 *
2629 * Sets ORDER proc in caller's orderproc argument, which is used during binary
2630 * searches of arrays during the index scan. Also sets a same-type ORDER proc
2631 * in caller's *sortprocp argument, which is used when sorting the array.
2632 *
2633 * Preprocessing calls here with all equality strategy scan keys (when scan
2634 * uses equality array keys), including those not associated with any array.
2635 * See _bt_advance_array_keys for an explanation of why it'll need to treat
2636 * simple scalar equality scan keys as degenerate single element arrays.
2637 *
2638 * Caller should pass an orderproc pointing to space that'll store the ORDER
2639 * proc for the scan, and a *sortprocp pointing to its own separate space.
2640 * When calling here for a non-array scan key, sortprocp arg should be NULL.
2641 *
2642 * In the common case where we don't need to deal with cross-type operators,
2643 * only one ORDER proc is actually required by caller. We'll set *sortprocp
2644 * to point to the same memory that caller's orderproc continues to point to.
2645 * Otherwise, *sortprocp will continue to point to caller's own space. Either
2646 * way, *sortprocp will point to a same-type ORDER proc (since that's the only
2647 * safe way to sort/deduplicate the array associated with caller's scan key).
2648 */
2649 static void
2650 _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype,
2651 FmgrInfo *orderproc, FmgrInfo **sortprocp)
2652 {
2653 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2654 Relation rel = scan->indexRelation;
2655 RegProcedure cmp_proc;
2656 Oid opcintype = rel->rd_opcintype[skey->sk_attno - 1];
2657
2658 Assert(skey->sk_strategy == BTEqualStrategyNumber);
2659 Assert(OidIsValid(elemtype));
2660
2661 /*
2662 * If scankey operator is not a cross-type comparison, we can use the
2663 * cached comparison function; otherwise gotta look it up in the catalogs
2664 */
2665 if (elemtype == opcintype)
2666 {
2667 /* Set same-type ORDER procs for caller */
2668 *orderproc = *index_getprocinfo(rel, skey->sk_attno, BTORDER_PROC);
2669 if (sortprocp)
2670 *sortprocp = orderproc;
2671
2672 return;
2673 }
2674
2675 /*
2676 * Look up the appropriate cross-type comparison function in the opfamily.
2677 *
2678 * Use the opclass input type as the left hand arg type, and the array
2679 * element type as the right hand arg type (since binary searches use an
2680 * index tuple's attribute value to search for a matching array element).
2681 *
2682 * Note: it's possible that this would fail, if the opfamily is
2683 * incomplete, but only in cases where it's quite likely that _bt_first
2684 * would fail in just the same way (had we not failed before it could).
2685 */
2686 cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
2687 opcintype, elemtype, BTORDER_PROC);
2688 if (!RegProcedureIsValid(cmp_proc))
2689 elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
2690 BTORDER_PROC, opcintype, elemtype, skey->sk_attno,
2691 RelationGetRelationName(rel));
2692
2693 /* Set cross-type ORDER proc for caller */
2694 fmgr_info_cxt(cmp_proc, orderproc, so->arrayContext);
2695
2696 /* Done if caller doesn't actually have an array they'll need to sort */
2697 if (!sortprocp)
2698 return;
2699
2700 /*
2701 * Look up the appropriate same-type comparison function in the opfamily.
2702 *
2703 * Note: it's possible that this would fail, if the opfamily is
2704 * incomplete, but it seems quite unlikely that an opfamily would omit
2705 * non-cross-type comparison procs for any datatype that it supports at
2706 * all.
2707 */
2708 cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
2709 elemtype, elemtype, BTORDER_PROC);
2710 if (!RegProcedureIsValid(cmp_proc))
2711 elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
2712 BTORDER_PROC, elemtype, elemtype,
2713 skey->sk_attno, RelationGetRelationName(rel));
2714
2715 /* Set same-type ORDER proc for caller */
2716 fmgr_info_cxt(cmp_proc, *sortprocp, so->arrayContext);
2717 }
2718
2719 /*
2720 * _bt_sort_array_elements() -- sort and de-dup array elements
2721 *
2722 * The array elements are sorted in-place, and the new number of elements
2723 * after duplicate removal is returned.
2724 *
2725 * skey identifies the index column whose opfamily determines the comparison
2726 * semantics, and sortproc is a corresponding ORDER proc. If reverse is true,
2727 * we sort in descending order.
2728 */
2729 static int
2730 _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc, bool reverse,
2731 Datum *elems, int nelems)
2732 {
2733 BTSortArrayContext cxt;
2734
2735 if (nelems <= 1)
2736 return nelems; /* no work to do */
2737
2738 /* Sort the array elements */
2739 cxt.sortproc = sortproc;
2740 cxt.collation = skey->sk_collation;
2741 cxt.reverse = reverse;
2742 qsort_arg(elems, nelems, sizeof(Datum),
2743 _bt_compare_array_elements, &cxt);
2744
2745 /* Now scan the sorted elements and remove duplicates */
2746 return qunique_arg(elems, nelems, sizeof(Datum),
2747 _bt_compare_array_elements, &cxt);
2748 }
2749
2750 /*
2751 * _bt_merge_arrays() -- merge next array's elements into an original array
2752 *
2753 * Called when preprocessing encounters a pair of array equality scan keys,
2754 * both against the same index attribute (during initial array preprocessing).
2755 * Merging reorganizes caller's original array (the left hand arg) in-place,
2756 * without ever copying elements from one array into the other. (Mixing the
2757 * elements together like this would be wrong, since they don't necessarily
2758 * use the same underlying element type, despite all the other similarities.)
2759 *
2760 * Both arrays must have already been sorted and deduplicated by calling
2761 * _bt_sort_array_elements. sortproc is the same-type ORDER proc that was
2762 * just used to sort and deduplicate caller's "next" array. We'll usually be
2763 * able to reuse that order PROC to merge the arrays together now. If not,
2764 * then we'll perform a separate ORDER proc lookup.
2765 *
2766 * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
2767 * may not be able to determine which elements are contradictory. If we have
2768 * the required ORDER proc then we return true (and validly set *nelems_orig),
2769 * guaranteeing that at least the next array can be considered redundant. We
2770 * return false if the required comparisons cannot be made (caller must keep
2771 * both arrays when this happens).
2772 */
2773 static bool
2774 _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, FmgrInfo *sortproc,
2775 bool reverse, Oid origelemtype, Oid nextelemtype,
2776 Datum *elems_orig, int *nelems_orig,
2777 Datum *elems_next, int nelems_next)
2778 {
2779 Relation rel = scan->indexRelation;
2780 BTScanOpaque so = (BTScanOpaque) scan->opaque;
2781 BTSortArrayContext cxt;
2782 int nelems_orig_start = *nelems_orig,
2783 nelems_orig_merged = 0;
2784 FmgrInfo *mergeproc = sortproc;
2785 FmgrInfo crosstypeproc;
2786
2787 Assert(skey->sk_strategy == BTEqualStrategyNumber);
2788 Assert(OidIsValid(origelemtype) && OidIsValid(nextelemtype));
2789
2790 if (origelemtype != nextelemtype)
2791 {
2792 RegProcedure cmp_proc;
2793
2794 /*
2795 * Cross-array-element-type merging is required, so can't just reuse
2796 * sortproc when merging
2797 */
2798 cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
2799 origelemtype, nextelemtype, BTORDER_PROC);
2800 if (!RegProcedureIsValid(cmp_proc))
2801 {
2802 /* Can't make the required comparisons */
2803 return false;
2804 }
2805
2806 /* We have all we need to determine redundancy/contradictoriness */
2807 mergeproc = &crosstypeproc;
2808 fmgr_info_cxt(cmp_proc, mergeproc, so->arrayContext);
2809 }
2810
2811 cxt.sortproc = mergeproc;
2812 cxt.collation = skey->sk_collation;
2813 cxt.reverse = reverse;
2814
2815 for (int i = 0, j = 0; i < nelems_orig_start && j < nelems_next;)
2816 {
2817 Datum *oelem = elems_orig + i,
2818 *nelem = elems_next + j;
2819 int res = _bt_compare_array_elements(oelem, nelem, &cxt);
2820
2821 if (res == 0)
2822 {
2823 elems_orig[nelems_orig_merged++] = *oelem;
2824 i++;
2825 j++;
2826 }
2827 else if (res < 0)
2828 i++;
2829 else /* res > 0 */
2830 j++;
2831 }
2832
2833 *nelems_orig = nelems_orig_merged;
2834
2835 return true;
2836 }
2837
2838 /*
2839 * qsort_arg comparator for sorting array elements
2840 */
2841 static int
2842 _bt_compare_array_elements(const void *a, const void *b, void *arg)
2843 {
2844 Datum da = *((const Datum *) a);
2845 Datum db = *((const Datum *) b);
2846 BTSortArrayContext *cxt = (BTSortArrayContext *) arg;
2847 int32 compare;
2848
2849 compare = DatumGetInt32(FunctionCall2Coll(cxt->sortproc,
2850 cxt->collation,
2851 da, db));
2852 if (cxt->reverse)
2853 INVERT_COMPARE_RESULT(compare);
2854 return compare;
2855 }