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