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