Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * nbtpreprocesskeys.c
4 : * Preprocessing for Postgres btree scan keys.
5 : *
6 : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 : * Portions Copyright (c) 1994, Regents of the University of California
8 : *
9 : *
10 : * IDENTIFICATION
11 : * src/backend/access/nbtree/nbtpreprocesskeys.c
12 : *
13 : *-------------------------------------------------------------------------
14 : */
15 :
16 : #include "postgres.h"
17 :
18 : #include "access/nbtree.h"
19 : #include "lib/qunique.h"
20 : #include "utils/array.h"
21 : #include "utils/lsyscache.h"
22 : #include "utils/memutils.h"
23 :
24 : typedef struct BTScanKeyPreproc
25 : {
26 : ScanKey inkey;
27 : int inkeyi;
28 : int arrayidx;
29 : } BTScanKeyPreproc;
30 :
31 : typedef struct BTSortArrayContext
32 : {
33 : FmgrInfo *sortproc;
34 : Oid collation;
35 : bool reverse;
36 : } BTSortArrayContext;
37 :
38 : static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption);
39 : static void _bt_mark_scankey_required(ScanKey skey);
40 : static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
41 : ScanKey leftarg, ScanKey rightarg,
42 : BTArrayKeyInfo *array, FmgrInfo *orderproc,
43 : bool *result);
44 : static bool _bt_compare_array_scankey_args(IndexScanDesc scan,
45 : ScanKey arraysk, ScanKey skey,
46 : FmgrInfo *orderproc, BTArrayKeyInfo *array,
47 : bool *qual_ok);
48 : static ScanKey _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys);
49 : static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap);
50 : static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey,
51 : Oid elemtype, StrategyNumber strat,
52 : Datum *elems, int nelems);
53 : static void _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype,
54 : FmgrInfo *orderproc, FmgrInfo **sortprocp);
55 : static int _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc,
56 : bool reverse, Datum *elems, int nelems);
57 : static bool _bt_merge_arrays(IndexScanDesc scan, ScanKey skey,
58 : FmgrInfo *sortproc, bool reverse,
59 : Oid origelemtype, Oid nextelemtype,
60 : Datum *elems_orig, int *nelems_orig,
61 : Datum *elems_next, int nelems_next);
62 : static int _bt_compare_array_elements(const void *a, const void *b, void *arg);
63 :
64 :
65 : /*
66 : * _bt_preprocess_keys() -- Preprocess scan keys
67 : *
68 : * The given search-type keys (taken from scan->keyData[])
69 : * are copied to so->keyData[] with possible transformation.
70 : * scan->numberOfKeys is the number of input keys, so->numberOfKeys gets
71 : * the number of output keys. Calling here a second or subsequent time
72 : * (during the same btrescan) is a no-op.
73 : *
74 : * The output keys are marked with additional sk_flags bits beyond the
75 : * system-standard bits supplied by the caller. The DESC and NULLS_FIRST
76 : * indoption bits for the relevant index attribute are copied into the flags.
77 : * Also, for a DESC column, we commute (flip) all the sk_strategy numbers
78 : * so that the index sorts in the desired direction.
79 : *
80 : * One key purpose of this routine is to discover which scan keys must be
81 : * satisfied to continue the scan. It also attempts to eliminate redundant
82 : * keys and detect contradictory keys. (If the index opfamily provides
83 : * incomplete sets of cross-type operators, we may fail to detect redundant
84 : * or contradictory keys, but we can survive that.)
85 : *
86 : * The output keys must be sorted by index attribute. Presently we expect
87 : * (but verify) that the input keys are already so sorted --- this is done
88 : * by match_clauses_to_index() in indxpath.c. Some reordering of the keys
89 : * within each attribute may be done as a byproduct of the processing here.
90 : * That process must leave array scan keys (within an attribute) in the same
91 : * order as corresponding entries from the scan's BTArrayKeyInfo array info.
92 : *
93 : * The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD
94 : * if they must be satisfied in order to continue the scan forward or backward
95 : * respectively. _bt_checkkeys uses these flags. For example, if the quals
96 : * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
97 : * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
98 : * But once we reach tuples like (1,4,z) we can stop scanning because no
99 : * later tuples could match. This is reflected by marking the x and y keys,
100 : * but not the z key, with SK_BT_REQFWD. In general, the keys for leading
101 : * attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD.
102 : * For the first attribute without an "=" key, any "<" and "<=" keys are
103 : * marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD.
104 : * This can be seen to be correct by considering the above example. Note
105 : * in particular that if there are no keys for a given attribute, the keys for
106 : * subsequent attributes can never be required; for instance "WHERE y = 4"
107 : * requires a full-index scan.
108 : *
109 : * If possible, redundant keys are eliminated: we keep only the tightest
110 : * >/>= bound and the tightest </<= bound, and if there's an = key then
111 : * that's the only one returned. (So, we return either a single = key,
112 : * or one or two boundary-condition keys for each attr.) However, if we
113 : * cannot compare two keys for lack of a suitable cross-type operator,
114 : * we cannot eliminate either. If there are two such keys of the same
115 : * operator strategy, the second one is just pushed into the output array
116 : * without further processing here. We may also emit both >/>= or both
117 : * </<= keys if we can't compare them. The logic about required keys still
118 : * works if we don't eliminate redundant keys.
119 : *
120 : * Note that one reason we need direction-sensitive required-key flags is
121 : * precisely that we may not be able to eliminate redundant keys. Suppose
122 : * we have "x > 4::int AND x > 10::bigint", and we are unable to determine
123 : * which key is more restrictive for lack of a suitable cross-type operator.
124 : * _bt_first will arbitrarily pick one of the keys to do the initial
125 : * positioning with. If it picks x > 4, then the x > 10 condition will fail
126 : * until we reach index entries > 10; but we can't stop the scan just because
127 : * x > 10 is failing. On the other hand, if we are scanning backwards, then
128 : * failure of either key is indeed enough to stop the scan. (In general, when
129 : * inequality keys are present, the initial-positioning code only promises to
130 : * position before the first possible match, not exactly at the first match,
131 : * for a forward scan; or after the last match for a backward scan.)
132 : *
133 : * As a byproduct of this work, we can detect contradictory quals such
134 : * as "x = 1 AND x > 2". If we see that, we return so->qual_ok = false,
135 : * indicating the scan need not be run at all since no tuples can match.
136 : * (In this case we do not bother completing the output key array!)
137 : * Again, missing cross-type operators might cause us to fail to prove the
138 : * quals contradictory when they really are, but the scan will work correctly.
139 : *
140 : * Row comparison keys are currently also treated without any smarts:
141 : * we just transfer them into the preprocessed array without any
142 : * editorialization. We can treat them the same as an ordinary inequality
143 : * comparison on the row's first index column, for the purposes of the logic
144 : * about required keys.
145 : *
146 : * Note: the reason we have to copy the preprocessed scan keys into private
147 : * storage is that we are modifying the array based on comparisons of the
148 : * key argument values, which could change on a rescan. Therefore we can't
149 : * overwrite the source data.
150 : */
151 : void
152 13413216 : _bt_preprocess_keys(IndexScanDesc scan)
153 : {
154 13413216 : BTScanOpaque so = (BTScanOpaque) scan->opaque;
155 13413216 : int numberOfKeys = scan->numberOfKeys;
156 13413216 : int16 *indoption = scan->indexRelation->rd_indoption;
157 : int new_numberOfKeys;
158 : int numberOfEqualCols;
159 : ScanKey inkeys;
160 : BTScanKeyPreproc xform[BTMaxStrategyNumber];
161 : bool test_result;
162 : AttrNumber attno;
163 : ScanKey arrayKeyData;
164 13413216 : int *keyDataMap = NULL;
165 13413216 : int arrayidx = 0;
166 :
167 13413216 : if (so->numberOfKeys > 0)
168 : {
169 : /*
170 : * Only need to do preprocessing once per btrescan, at most. All
171 : * calls after the first are handled as no-ops.
172 : */
173 6805236 : return;
174 : }
175 :
176 : /* initialize result variables */
177 13412570 : so->qual_ok = true;
178 13412570 : so->numberOfKeys = 0;
179 :
180 13412570 : if (numberOfKeys < 1)
181 12496 : return; /* done if qual-less scan */
182 :
183 : /* If any keys are SK_SEARCHARRAY type, set up array-key info */
184 13400074 : arrayKeyData = _bt_preprocess_array_keys(scan, &numberOfKeys);
185 13400074 : if (!so->qual_ok)
186 : {
187 : /* unmatchable array, so give up */
188 6 : return;
189 : }
190 :
191 : /*
192 : * Treat arrayKeyData[] (a partially preprocessed copy of scan->keyData[])
193 : * as our input if _bt_preprocess_array_keys just allocated it, else just
194 : * use scan->keyData[]
195 : */
196 13400068 : if (arrayKeyData)
197 : {
198 1106 : inkeys = arrayKeyData;
199 :
200 : /* Also maintain keyDataMap for remapping so->orderProcs[] later */
201 1106 : keyDataMap = MemoryContextAlloc(so->arrayContext,
202 : numberOfKeys * sizeof(int));
203 : }
204 : else
205 13398962 : inkeys = scan->keyData;
206 :
207 : /* we check that input keys are correctly ordered */
208 13400068 : if (inkeys[0].sk_attno < 1)
209 0 : elog(ERROR, "btree index keys must be ordered by attribute");
210 :
211 : /* We can short-circuit most of the work if there's just one key */
212 13400068 : if (numberOfKeys == 1)
213 : {
214 : /* Apply indoption to scankey (might change sk_strategy!) */
215 6792028 : if (!_bt_fix_scankey_strategy(&inkeys[0], indoption))
216 978 : so->qual_ok = false;
217 6792028 : memcpy(&so->keyData[0], &inkeys[0], sizeof(ScanKeyData));
218 6792028 : so->numberOfKeys = 1;
219 : /* We can mark the qual as required if it's for first index col */
220 6792028 : if (inkeys[0].sk_attno == 1)
221 6789316 : _bt_mark_scankey_required(&so->keyData[0]);
222 : if (arrayKeyData)
223 : {
224 : /*
225 : * Don't call _bt_preprocess_array_keys_final in this fast path
226 : * (we'll miss out on the single value array transformation, but
227 : * that's not nearly as important when there's only one scan key)
228 : */
229 : Assert(so->keyData[0].sk_flags & SK_SEARCHARRAY);
230 : Assert(so->keyData[0].sk_strategy != BTEqualStrategyNumber ||
231 : (so->arrayKeys[0].scan_key == 0 &&
232 : OidIsValid(so->orderProcs[0].fn_oid)));
233 : }
234 :
235 6792028 : return;
236 : }
237 :
238 : /*
239 : * Otherwise, do the full set of pushups.
240 : */
241 6608040 : new_numberOfKeys = 0;
242 6608040 : numberOfEqualCols = 0;
243 :
244 : /*
245 : * Initialize for processing of keys for attr 1.
246 : *
247 : * xform[i] points to the currently best scan key of strategy type i+1; it
248 : * is NULL if we haven't yet found such a key for this attr.
249 : */
250 6608040 : attno = 1;
251 6608040 : memset(xform, 0, sizeof(xform));
252 :
253 : /*
254 : * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to
255 : * handle after-last-key processing. Actual exit from the loop is at the
256 : * "break" statement below.
257 : */
258 6608040 : for (int i = 0;; i++)
259 14573698 : {
260 21181738 : ScanKey inkey = inkeys + i;
261 : int j;
262 :
263 21181738 : if (i < numberOfKeys)
264 : {
265 : /* Apply indoption to scankey (might change sk_strategy!) */
266 14573722 : if (!_bt_fix_scankey_strategy(inkey, indoption))
267 : {
268 : /* NULL can't be matched, so give up */
269 18 : so->qual_ok = false;
270 18 : return;
271 : }
272 : }
273 :
274 : /*
275 : * If we are at the end of the keys for a particular attr, finish up
276 : * processing and emit the cleaned-up keys.
277 : */
278 21181720 : if (i == numberOfKeys || inkey->sk_attno != attno)
279 : {
280 14571564 : int priorNumberOfEqualCols = numberOfEqualCols;
281 :
282 : /* check input keys are correctly ordered */
283 14571564 : if (i < numberOfKeys && inkey->sk_attno < attno)
284 0 : elog(ERROR, "btree index keys must be ordered by attribute");
285 :
286 : /*
287 : * If = has been specified, all other keys can be eliminated as
288 : * redundant. Note that this is no less true if the = key is
289 : * SEARCHARRAY; the only real difference is that the inequality
290 : * key _becomes_ redundant by making _bt_compare_scankey_args
291 : * eliminate the subset of elements that won't need to be matched.
292 : *
293 : * If we have a case like "key = 1 AND key > 2", we set qual_ok to
294 : * false and abandon further processing. We'll do the same thing
295 : * given a case like "key IN (0, 1) AND key > 2".
296 : *
297 : * We also have to deal with the case of "key IS NULL", which is
298 : * unsatisfiable in combination with any other index condition. By
299 : * the time we get here, that's been classified as an equality
300 : * check, and we've rejected any combination of it with a regular
301 : * equality condition; but not with other types of conditions.
302 : */
303 14571564 : if (xform[BTEqualStrategyNumber - 1].inkey)
304 : {
305 13214512 : ScanKey eq = xform[BTEqualStrategyNumber - 1].inkey;
306 13214512 : BTArrayKeyInfo *array = NULL;
307 13214512 : FmgrInfo *orderproc = NULL;
308 :
309 13214512 : if (arrayKeyData && (eq->sk_flags & SK_SEARCHARRAY))
310 : {
311 : int eq_in_ikey,
312 : eq_arrayidx;
313 :
314 756 : eq_in_ikey = xform[BTEqualStrategyNumber - 1].inkeyi;
315 756 : eq_arrayidx = xform[BTEqualStrategyNumber - 1].arrayidx;
316 756 : array = &so->arrayKeys[eq_arrayidx - 1];
317 756 : orderproc = so->orderProcs + eq_in_ikey;
318 :
319 : Assert(array->scan_key == eq_in_ikey);
320 : Assert(OidIsValid(orderproc->fn_oid));
321 : }
322 :
323 79286916 : for (j = BTMaxStrategyNumber; --j >= 0;)
324 : {
325 66072440 : ScanKey chk = xform[j].inkey;
326 :
327 66072440 : if (!chk || j == (BTEqualStrategyNumber - 1))
328 66072210 : continue;
329 :
330 230 : if (eq->sk_flags & SK_SEARCHNULL)
331 : {
332 : /* IS NULL is contradictory to anything else */
333 24 : so->qual_ok = false;
334 24 : return;
335 : }
336 :
337 206 : if (_bt_compare_scankey_args(scan, chk, eq, chk,
338 : array, orderproc,
339 : &test_result))
340 : {
341 206 : if (!test_result)
342 : {
343 : /* keys proven mutually contradictory */
344 12 : so->qual_ok = false;
345 12 : return;
346 : }
347 : /* else discard the redundant non-equality key */
348 : Assert(!array || array->num_elems > 0);
349 194 : xform[j].inkey = NULL;
350 194 : xform[j].inkeyi = -1;
351 : }
352 : /* else, cannot determine redundancy, keep both keys */
353 : }
354 : /* track number of attrs for which we have "=" keys */
355 13214476 : numberOfEqualCols++;
356 : }
357 :
358 : /* try to keep only one of <, <= */
359 14571528 : if (xform[BTLessStrategyNumber - 1].inkey &&
360 1976 : xform[BTLessEqualStrategyNumber - 1].inkey)
361 : {
362 6 : ScanKey lt = xform[BTLessStrategyNumber - 1].inkey;
363 6 : ScanKey le = xform[BTLessEqualStrategyNumber - 1].inkey;
364 :
365 6 : if (_bt_compare_scankey_args(scan, le, lt, le, NULL, NULL,
366 : &test_result))
367 : {
368 6 : if (test_result)
369 6 : xform[BTLessEqualStrategyNumber - 1].inkey = NULL;
370 : else
371 0 : xform[BTLessStrategyNumber - 1].inkey = NULL;
372 : }
373 : }
374 :
375 : /* try to keep only one of >, >= */
376 14571528 : if (xform[BTGreaterStrategyNumber - 1].inkey &&
377 1352692 : xform[BTGreaterEqualStrategyNumber - 1].inkey)
378 : {
379 6 : ScanKey gt = xform[BTGreaterStrategyNumber - 1].inkey;
380 6 : ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1].inkey;
381 :
382 6 : if (_bt_compare_scankey_args(scan, ge, gt, ge, NULL, NULL,
383 : &test_result))
384 : {
385 6 : if (test_result)
386 0 : xform[BTGreaterEqualStrategyNumber - 1].inkey = NULL;
387 : else
388 6 : xform[BTGreaterStrategyNumber - 1].inkey = NULL;
389 : }
390 : }
391 :
392 : /*
393 : * Emit the cleaned-up keys into the so->keyData[] array, and then
394 : * mark them if they are required. They are required (possibly
395 : * only in one direction) if all attrs before this one had "=".
396 : */
397 87429168 : for (j = BTMaxStrategyNumber; --j >= 0;)
398 : {
399 72857640 : if (xform[j].inkey)
400 : {
401 14573342 : ScanKey outkey = &so->keyData[new_numberOfKeys++];
402 :
403 14573342 : memcpy(outkey, xform[j].inkey, sizeof(ScanKeyData));
404 14573342 : if (arrayKeyData)
405 1188 : keyDataMap[new_numberOfKeys - 1] = xform[j].inkeyi;
406 14573342 : if (priorNumberOfEqualCols == attno - 1)
407 14572496 : _bt_mark_scankey_required(outkey);
408 : }
409 : }
410 :
411 : /*
412 : * Exit loop here if done.
413 : */
414 14571528 : if (i == numberOfKeys)
415 6607980 : break;
416 :
417 : /* Re-initialize for new attno */
418 7963548 : attno = inkey->sk_attno;
419 7963548 : memset(xform, 0, sizeof(xform));
420 : }
421 :
422 : /* check strategy this key's operator corresponds to */
423 14573704 : j = inkey->sk_strategy - 1;
424 :
425 : /* if row comparison, push it directly to the output array */
426 14573704 : if (inkey->sk_flags & SK_ROW_HEADER)
427 : {
428 12 : ScanKey outkey = &so->keyData[new_numberOfKeys++];
429 :
430 12 : memcpy(outkey, inkey, sizeof(ScanKeyData));
431 12 : if (arrayKeyData)
432 0 : keyDataMap[new_numberOfKeys - 1] = i;
433 12 : if (numberOfEqualCols == attno - 1)
434 12 : _bt_mark_scankey_required(outkey);
435 :
436 : /*
437 : * We don't support RowCompare using equality; such a qual would
438 : * mess up the numberOfEqualCols tracking.
439 : */
440 : Assert(j != (BTEqualStrategyNumber - 1));
441 12 : continue;
442 : }
443 :
444 14573692 : if (inkey->sk_strategy == BTEqualStrategyNumber &&
445 13214554 : (inkey->sk_flags & SK_SEARCHARRAY))
446 : {
447 : /* must track how input scan keys map to arrays */
448 : Assert(arrayKeyData);
449 762 : arrayidx++;
450 : }
451 :
452 : /*
453 : * have we seen a scan key for this same attribute and using this same
454 : * operator strategy before now?
455 : */
456 14573692 : if (xform[j].inkey == NULL)
457 : {
458 : /* nope, so this scan key wins by default (at least for now) */
459 14573644 : xform[j].inkey = inkey;
460 14573644 : xform[j].inkeyi = i;
461 14573644 : xform[j].arrayidx = arrayidx;
462 : }
463 : else
464 : {
465 48 : FmgrInfo *orderproc = NULL;
466 48 : BTArrayKeyInfo *array = NULL;
467 :
468 : /*
469 : * Seen one of these before, so keep only the more restrictive key
470 : * if possible
471 : */
472 48 : if (j == (BTEqualStrategyNumber - 1) && arrayKeyData)
473 : {
474 : /*
475 : * Have to set up array keys
476 : */
477 12 : if (inkey->sk_flags & SK_SEARCHARRAY)
478 : {
479 0 : array = &so->arrayKeys[arrayidx - 1];
480 0 : orderproc = so->orderProcs + i;
481 :
482 : Assert(array->scan_key == i);
483 : Assert(OidIsValid(orderproc->fn_oid));
484 : }
485 12 : else if (xform[j].inkey->sk_flags & SK_SEARCHARRAY)
486 : {
487 12 : array = &so->arrayKeys[xform[j].arrayidx - 1];
488 12 : orderproc = so->orderProcs + xform[j].inkeyi;
489 :
490 : Assert(array->scan_key == xform[j].inkeyi);
491 : Assert(OidIsValid(orderproc->fn_oid));
492 : }
493 :
494 : /*
495 : * Both scan keys might have arrays, in which case we'll
496 : * arbitrarily pass only one of the arrays. That won't
497 : * matter, since _bt_compare_scankey_args is aware that two
498 : * SEARCHARRAY scan keys mean that _bt_preprocess_array_keys
499 : * failed to eliminate redundant arrays through array merging.
500 : * _bt_compare_scankey_args just returns false when it sees
501 : * this; it won't even try to examine either array.
502 : */
503 : }
504 :
505 48 : if (_bt_compare_scankey_args(scan, inkey, inkey, xform[j].inkey,
506 : array, orderproc, &test_result))
507 : {
508 : /* Have all we need to determine redundancy */
509 48 : if (test_result)
510 : {
511 : Assert(!array || array->num_elems > 0);
512 :
513 : /*
514 : * New key is more restrictive, and so replaces old key...
515 : */
516 42 : if (j != (BTEqualStrategyNumber - 1) ||
517 12 : !(xform[j].inkey->sk_flags & SK_SEARCHARRAY))
518 : {
519 36 : xform[j].inkey = inkey;
520 36 : xform[j].inkeyi = i;
521 36 : xform[j].arrayidx = arrayidx;
522 : }
523 : else
524 : {
525 : /*
526 : * ...unless we have to keep the old key because it's
527 : * an array that rendered the new key redundant. We
528 : * need to make sure that we don't throw away an array
529 : * scan key. _bt_preprocess_array_keys_final expects
530 : * us to keep all of the arrays that weren't already
531 : * eliminated by _bt_preprocess_array_keys earlier on.
532 : */
533 : Assert(!(inkey->sk_flags & SK_SEARCHARRAY));
534 : }
535 : }
536 6 : else if (j == (BTEqualStrategyNumber - 1))
537 : {
538 : /* key == a && key == b, but a != b */
539 6 : so->qual_ok = false;
540 6 : return;
541 : }
542 : /* else old key is more restrictive, keep it */
543 : }
544 : else
545 : {
546 : /*
547 : * We can't determine which key is more restrictive. Push
548 : * xform[j] directly to the output array, then set xform[j] to
549 : * the new scan key.
550 : *
551 : * Note: We do things this way around so that our arrays are
552 : * always in the same order as their corresponding scan keys,
553 : * even with incomplete opfamilies. _bt_advance_array_keys
554 : * depends on this.
555 : */
556 0 : ScanKey outkey = &so->keyData[new_numberOfKeys++];
557 :
558 0 : memcpy(outkey, xform[j].inkey, sizeof(ScanKeyData));
559 0 : if (arrayKeyData)
560 0 : keyDataMap[new_numberOfKeys - 1] = xform[j].inkeyi;
561 0 : if (numberOfEqualCols == attno - 1)
562 0 : _bt_mark_scankey_required(outkey);
563 0 : xform[j].inkey = inkey;
564 0 : xform[j].inkeyi = i;
565 0 : xform[j].arrayidx = arrayidx;
566 : }
567 : }
568 : }
569 :
570 6607980 : so->numberOfKeys = new_numberOfKeys;
571 :
572 : /*
573 : * Now that we've built a temporary mapping from so->keyData[] (output
574 : * scan keys) to arrayKeyData[] (our input scan keys), fix array->scan_key
575 : * references. Also consolidate the so->orderProcs[] array such that it
576 : * can be subscripted using so->keyData[]-wise offsets.
577 : */
578 6607980 : if (arrayKeyData)
579 582 : _bt_preprocess_array_keys_final(scan, keyDataMap);
580 :
581 : /* Could pfree arrayKeyData/keyDataMap now, but not worth the cycles */
582 : }
583 :
584 : /*
585 : * Adjust a scankey's strategy and flags setting as needed for indoptions.
586 : *
587 : * We copy the appropriate indoption value into the scankey sk_flags
588 : * (shifting to avoid clobbering system-defined flag bits). Also, if
589 : * the DESC option is set, commute (flip) the operator strategy number.
590 : *
591 : * A secondary purpose is to check for IS NULL/NOT NULL scankeys and set up
592 : * the strategy field correctly for them.
593 : *
594 : * Lastly, for ordinary scankeys (not IS NULL/NOT NULL), we check for a
595 : * NULL comparison value. Since all btree operators are assumed strict,
596 : * a NULL means that the qual cannot be satisfied. We return true if the
597 : * comparison value isn't NULL, or false if the scan should be abandoned.
598 : *
599 : * This function is applied to the *input* scankey structure; therefore
600 : * on a rescan we will be looking at already-processed scankeys. Hence
601 : * we have to be careful not to re-commute the strategy if we already did it.
602 : * It's a bit ugly to modify the caller's copy of the scankey but in practice
603 : * there shouldn't be any problem, since the index's indoptions are certainly
604 : * not going to change while the scankey survives.
605 : */
606 : static bool
607 21365750 : _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
608 : {
609 : int addflags;
610 :
611 21365750 : addflags = indoption[skey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
612 :
613 : /*
614 : * We treat all btree operators as strict (even if they're not so marked
615 : * in pg_proc). This means that it is impossible for an operator condition
616 : * with a NULL comparison constant to succeed, and we can reject it right
617 : * away.
618 : *
619 : * However, we now also support "x IS NULL" clauses as search conditions,
620 : * so in that case keep going. The planner has not filled in any
621 : * particular strategy in this case, so set it to BTEqualStrategyNumber
622 : * --- we can treat IS NULL as an equality operator for purposes of search
623 : * strategy.
624 : *
625 : * Likewise, "x IS NOT NULL" is supported. We treat that as either "less
626 : * than NULL" in a NULLS LAST index, or "greater than NULL" in a NULLS
627 : * FIRST index.
628 : *
629 : * Note: someday we might have to fill in sk_collation from the index
630 : * column's collation. At the moment this is a non-issue because we'll
631 : * never actually call the comparison operator on a NULL.
632 : */
633 21365750 : if (skey->sk_flags & SK_ISNULL)
634 : {
635 : /* SK_ISNULL shouldn't be set in a row header scankey */
636 : Assert(!(skey->sk_flags & SK_ROW_HEADER));
637 :
638 : /* Set indoption flags in scankey (might be done already) */
639 109900 : skey->sk_flags |= addflags;
640 :
641 : /* Set correct strategy for IS NULL or NOT NULL search */
642 109900 : if (skey->sk_flags & SK_SEARCHNULL)
643 : {
644 140 : skey->sk_strategy = BTEqualStrategyNumber;
645 140 : skey->sk_subtype = InvalidOid;
646 140 : skey->sk_collation = InvalidOid;
647 : }
648 109760 : else if (skey->sk_flags & SK_SEARCHNOTNULL)
649 : {
650 108770 : if (skey->sk_flags & SK_BT_NULLS_FIRST)
651 36 : skey->sk_strategy = BTGreaterStrategyNumber;
652 : else
653 108734 : skey->sk_strategy = BTLessStrategyNumber;
654 108770 : skey->sk_subtype = InvalidOid;
655 108770 : skey->sk_collation = InvalidOid;
656 : }
657 : else
658 : {
659 : /* regular qual, so it cannot be satisfied */
660 990 : return false;
661 : }
662 :
663 : /* Needn't do the rest */
664 108910 : return true;
665 : }
666 :
667 : /* Adjust strategy for DESC, if we didn't already */
668 21255850 : if ((addflags & SK_BT_DESC) && !(skey->sk_flags & SK_BT_DESC))
669 6 : skey->sk_strategy = BTCommuteStrategyNumber(skey->sk_strategy);
670 21255850 : skey->sk_flags |= addflags;
671 :
672 : /* If it's a row header, fix row member flags and strategies similarly */
673 21255850 : if (skey->sk_flags & SK_ROW_HEADER)
674 : {
675 66 : ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
676 :
677 66 : if (subkey->sk_flags & SK_ISNULL)
678 : {
679 : /* First row member is NULL, so RowCompare is unsatisfiable */
680 : Assert(subkey->sk_flags & SK_ROW_MEMBER);
681 6 : return false;
682 : }
683 :
684 : for (;;)
685 : {
686 60 : Assert(subkey->sk_flags & SK_ROW_MEMBER);
687 120 : addflags = indoption[subkey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
688 120 : if ((addflags & SK_BT_DESC) && !(subkey->sk_flags & SK_BT_DESC))
689 0 : subkey->sk_strategy = BTCommuteStrategyNumber(subkey->sk_strategy);
690 120 : subkey->sk_flags |= addflags;
691 120 : if (subkey->sk_flags & SK_ROW_END)
692 60 : break;
693 60 : subkey++;
694 : }
695 : }
696 :
697 21255844 : return true;
698 : }
699 :
700 : /*
701 : * Mark a scankey as "required to continue the scan".
702 : *
703 : * Depending on the operator type, the key may be required for both scan
704 : * directions or just one. Also, if the key is a row comparison header,
705 : * we have to mark its first subsidiary ScanKey as required. (Subsequent
706 : * subsidiary ScanKeys are normally for lower-order columns, and thus
707 : * cannot be required, since they're after the first non-equality scankey.)
708 : *
709 : * Note: when we set required-key flag bits in a subsidiary scankey, we are
710 : * scribbling on a data structure belonging to the index AM's caller, not on
711 : * our private copy. This should be OK because the marking will not change
712 : * from scan to scan within a query, and so we'd just re-mark the same way
713 : * anyway on a rescan. Something to keep an eye on though.
714 : */
715 : static void
716 21361824 : _bt_mark_scankey_required(ScanKey skey)
717 : {
718 : int addflags;
719 :
720 21361824 : switch (skey->sk_strategy)
721 : {
722 111654 : case BTLessStrategyNumber:
723 : case BTLessEqualStrategyNumber:
724 111654 : addflags = SK_BT_REQFWD;
725 111654 : break;
726 19892282 : case BTEqualStrategyNumber:
727 19892282 : addflags = SK_BT_REQFWD | SK_BT_REQBKWD;
728 19892282 : break;
729 1357888 : case BTGreaterEqualStrategyNumber:
730 : case BTGreaterStrategyNumber:
731 1357888 : addflags = SK_BT_REQBKWD;
732 1357888 : break;
733 0 : default:
734 0 : elog(ERROR, "unrecognized StrategyNumber: %d",
735 : (int) skey->sk_strategy);
736 : addflags = 0; /* keep compiler quiet */
737 : break;
738 : }
739 :
740 21361824 : skey->sk_flags |= addflags;
741 :
742 21361824 : if (skey->sk_flags & SK_ROW_HEADER)
743 : {
744 66 : ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
745 :
746 : /* First subkey should be same column/operator as the header */
747 : Assert(subkey->sk_flags & SK_ROW_MEMBER);
748 : Assert(subkey->sk_attno == skey->sk_attno);
749 : Assert(subkey->sk_strategy == skey->sk_strategy);
750 66 : subkey->sk_flags |= addflags;
751 : }
752 21361824 : }
753 :
754 : /*
755 : * Compare two scankey values using a specified operator.
756 : *
757 : * The test we want to perform is logically "leftarg op rightarg", where
758 : * leftarg and rightarg are the sk_argument values in those ScanKeys, and
759 : * the comparison operator is the one in the op ScanKey. However, in
760 : * cross-data-type situations we may need to look up the correct operator in
761 : * the index's opfamily: it is the one having amopstrategy = op->sk_strategy
762 : * and amoplefttype/amoprighttype equal to the two argument datatypes.
763 : *
764 : * If the opfamily doesn't supply a complete set of cross-type operators we
765 : * may not be able to make the comparison. If we can make the comparison
766 : * we store the operator result in *result and return true. We return false
767 : * if the comparison could not be made.
768 : *
769 : * If either leftarg or rightarg are an array, we'll apply array-specific
770 : * rules to determine which array elements are redundant on behalf of caller.
771 : * It is up to our caller to save whichever of the two scan keys is the array,
772 : * and discard the non-array scan key (the non-array scan key is guaranteed to
773 : * be redundant with any complete opfamily). Caller isn't expected to call
774 : * here with a pair of array scan keys provided we're dealing with a complete
775 : * opfamily (_bt_preprocess_array_keys will merge array keys together to make
776 : * sure of that).
777 : *
778 : * Note: we'll also shrink caller's array as needed to eliminate redundant
779 : * array elements. One reason why caller should prefer to discard non-array
780 : * scan keys is so that we'll have the opportunity to shrink the array
781 : * multiple times, in multiple calls (for each of several other scan keys on
782 : * the same index attribute).
783 : *
784 : * Note: op always points at the same ScanKey as either leftarg or rightarg.
785 : * Since we don't scribble on the scankeys themselves, this aliasing should
786 : * cause no trouble.
787 : *
788 : * Note: this routine needs to be insensitive to any DESC option applied
789 : * to the index column. For example, "x < 4" is a tighter constraint than
790 : * "x < 5" regardless of which way the index is sorted.
791 : */
792 : static bool
793 266 : _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
794 : ScanKey leftarg, ScanKey rightarg,
795 : BTArrayKeyInfo *array, FmgrInfo *orderproc,
796 : bool *result)
797 : {
798 266 : Relation rel = scan->indexRelation;
799 : Oid lefttype,
800 : righttype,
801 : optype,
802 : opcintype,
803 : cmp_op;
804 : StrategyNumber strat;
805 :
806 : /*
807 : * First, deal with cases where one or both args are NULL. This should
808 : * only happen when the scankeys represent IS NULL/NOT NULL conditions.
809 : */
810 266 : if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ISNULL)
811 : {
812 : bool leftnull,
813 : rightnull;
814 :
815 132 : if (leftarg->sk_flags & SK_ISNULL)
816 : {
817 : Assert(leftarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
818 0 : leftnull = true;
819 : }
820 : else
821 132 : leftnull = false;
822 132 : if (rightarg->sk_flags & SK_ISNULL)
823 : {
824 : Assert(rightarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
825 132 : rightnull = true;
826 : }
827 : else
828 0 : rightnull = false;
829 :
830 : /*
831 : * We treat NULL as either greater than or less than all other values.
832 : * Since true > false, the tests below work correctly for NULLS LAST
833 : * logic. If the index is NULLS FIRST, we need to flip the strategy.
834 : */
835 132 : strat = op->sk_strategy;
836 132 : if (op->sk_flags & SK_BT_NULLS_FIRST)
837 0 : strat = BTCommuteStrategyNumber(strat);
838 :
839 132 : switch (strat)
840 : {
841 132 : case BTLessStrategyNumber:
842 132 : *result = (leftnull < rightnull);
843 132 : break;
844 0 : case BTLessEqualStrategyNumber:
845 0 : *result = (leftnull <= rightnull);
846 0 : break;
847 0 : case BTEqualStrategyNumber:
848 0 : *result = (leftnull == rightnull);
849 0 : break;
850 0 : case BTGreaterEqualStrategyNumber:
851 0 : *result = (leftnull >= rightnull);
852 0 : break;
853 0 : case BTGreaterStrategyNumber:
854 0 : *result = (leftnull > rightnull);
855 0 : break;
856 0 : default:
857 0 : elog(ERROR, "unrecognized StrategyNumber: %d", (int) strat);
858 : *result = false; /* keep compiler quiet */
859 : break;
860 : }
861 132 : return true;
862 : }
863 :
864 : /*
865 : * If either leftarg or rightarg are equality-type array scankeys, we need
866 : * specialized handling (since by now we know that IS NULL wasn't used)
867 : */
868 134 : if (array)
869 : {
870 : bool leftarray,
871 : rightarray;
872 :
873 48 : leftarray = ((leftarg->sk_flags & SK_SEARCHARRAY) &&
874 18 : leftarg->sk_strategy == BTEqualStrategyNumber);
875 42 : rightarray = ((rightarg->sk_flags & SK_SEARCHARRAY) &&
876 12 : rightarg->sk_strategy == BTEqualStrategyNumber);
877 :
878 : /*
879 : * _bt_preprocess_array_keys is responsible for merging together array
880 : * scan keys, and will do so whenever the opfamily has the required
881 : * cross-type support. If it failed to do that, we handle it just
882 : * like the case where we can't make the comparison ourselves.
883 : */
884 30 : if (leftarray && rightarray)
885 : {
886 : /* Can't make the comparison */
887 0 : *result = false; /* suppress compiler warnings */
888 0 : return false;
889 : }
890 :
891 : /*
892 : * Otherwise we need to determine if either one of leftarg or rightarg
893 : * uses an array, then pass this through to a dedicated helper
894 : * function.
895 : */
896 30 : if (leftarray)
897 18 : return _bt_compare_array_scankey_args(scan, leftarg, rightarg,
898 : orderproc, array, result);
899 12 : else if (rightarray)
900 12 : return _bt_compare_array_scankey_args(scan, rightarg, leftarg,
901 : orderproc, array, result);
902 :
903 : /* FALL THRU */
904 : }
905 :
906 : /*
907 : * The opfamily we need to worry about is identified by the index column.
908 : */
909 : Assert(leftarg->sk_attno == rightarg->sk_attno);
910 :
911 104 : opcintype = rel->rd_opcintype[leftarg->sk_attno - 1];
912 :
913 : /*
914 : * Determine the actual datatypes of the ScanKey arguments. We have to
915 : * support the convention that sk_subtype == InvalidOid means the opclass
916 : * input type; this is a hack to simplify life for ScanKeyInit().
917 : */
918 104 : lefttype = leftarg->sk_subtype;
919 104 : if (lefttype == InvalidOid)
920 0 : lefttype = opcintype;
921 104 : righttype = rightarg->sk_subtype;
922 104 : if (righttype == InvalidOid)
923 0 : righttype = opcintype;
924 104 : optype = op->sk_subtype;
925 104 : if (optype == InvalidOid)
926 0 : optype = opcintype;
927 :
928 : /*
929 : * If leftarg and rightarg match the types expected for the "op" scankey,
930 : * we can use its already-looked-up comparison function.
931 : */
932 104 : if (lefttype == opcintype && righttype == optype)
933 : {
934 98 : *result = DatumGetBool(FunctionCall2Coll(&op->sk_func,
935 : op->sk_collation,
936 : leftarg->sk_argument,
937 : rightarg->sk_argument));
938 98 : return true;
939 : }
940 :
941 : /*
942 : * Otherwise, we need to go to the syscache to find the appropriate
943 : * operator. (This cannot result in infinite recursion, since no
944 : * indexscan initiated by syscache lookup will use cross-data-type
945 : * operators.)
946 : *
947 : * If the sk_strategy was flipped by _bt_fix_scankey_strategy, we have to
948 : * un-flip it to get the correct opfamily member.
949 : */
950 6 : strat = op->sk_strategy;
951 6 : if (op->sk_flags & SK_BT_DESC)
952 0 : strat = BTCommuteStrategyNumber(strat);
953 :
954 6 : cmp_op = get_opfamily_member(rel->rd_opfamily[leftarg->sk_attno - 1],
955 : lefttype,
956 : righttype,
957 : strat);
958 6 : if (OidIsValid(cmp_op))
959 : {
960 6 : RegProcedure cmp_proc = get_opcode(cmp_op);
961 :
962 6 : if (RegProcedureIsValid(cmp_proc))
963 : {
964 6 : *result = DatumGetBool(OidFunctionCall2Coll(cmp_proc,
965 : op->sk_collation,
966 : leftarg->sk_argument,
967 : rightarg->sk_argument));
968 6 : return true;
969 : }
970 : }
971 :
972 : /* Can't make the comparison */
973 0 : *result = false; /* suppress compiler warnings */
974 0 : return false;
975 : }
976 :
977 : /*
978 : * Compare an array scan key to a scalar scan key, eliminating contradictory
979 : * array elements such that the scalar scan key becomes redundant.
980 : *
981 : * Array elements can be eliminated as contradictory when excluded by some
982 : * other operator on the same attribute. For example, with an index scan qual
983 : * "WHERE a IN (1, 2, 3) AND a < 2", all array elements except the value "1"
984 : * are eliminated, and the < scan key is eliminated as redundant. Cases where
985 : * every array element is eliminated by a redundant scalar scan key have an
986 : * unsatisfiable qual, which we handle by setting *qual_ok=false for caller.
987 : *
988 : * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
989 : * may not be able to determine which elements are contradictory. If we have
990 : * the required ORDER proc then we return true (and validly set *qual_ok),
991 : * guaranteeing that at least the scalar scan key can be considered redundant.
992 : * We return false if the comparison could not be made (caller must keep both
993 : * scan keys when this happens).
994 : */
995 : static bool
996 30 : _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey,
997 : FmgrInfo *orderproc, BTArrayKeyInfo *array,
998 : bool *qual_ok)
999 : {
1000 30 : Relation rel = scan->indexRelation;
1001 30 : Oid opcintype = rel->rd_opcintype[arraysk->sk_attno - 1];
1002 30 : int cmpresult = 0,
1003 30 : cmpexact = 0,
1004 : matchelem,
1005 30 : new_nelems = 0;
1006 : FmgrInfo crosstypeproc;
1007 30 : FmgrInfo *orderprocp = orderproc;
1008 :
1009 : Assert(arraysk->sk_attno == skey->sk_attno);
1010 : Assert(array->num_elems > 0);
1011 : Assert(!(arraysk->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
1012 : Assert((arraysk->sk_flags & SK_SEARCHARRAY) &&
1013 : arraysk->sk_strategy == BTEqualStrategyNumber);
1014 : Assert(!(skey->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
1015 : Assert(!(skey->sk_flags & SK_SEARCHARRAY) ||
1016 : skey->sk_strategy != BTEqualStrategyNumber);
1017 :
1018 : /*
1019 : * _bt_binsrch_array_skey searches an array for the entry best matching a
1020 : * datum of opclass input type for the index's attribute (on-disk type).
1021 : * We can reuse the array's ORDER proc whenever the non-array scan key's
1022 : * type is a match for the corresponding attribute's input opclass type.
1023 : * Otherwise, we have to do another ORDER proc lookup so that our call to
1024 : * _bt_binsrch_array_skey applies the correct comparator.
1025 : *
1026 : * Note: we have to support the convention that sk_subtype == InvalidOid
1027 : * means the opclass input type; this is a hack to simplify life for
1028 : * ScanKeyInit().
1029 : */
1030 30 : if (skey->sk_subtype != opcintype && skey->sk_subtype != InvalidOid)
1031 : {
1032 : RegProcedure cmp_proc;
1033 : Oid arraysk_elemtype;
1034 :
1035 : /*
1036 : * Need an ORDER proc lookup to detect redundancy/contradictoriness
1037 : * with this pair of scankeys.
1038 : *
1039 : * Scalar scan key's argument will be passed to _bt_compare_array_skey
1040 : * as its tupdatum/lefthand argument (rhs arg is for array elements).
1041 : */
1042 6 : arraysk_elemtype = arraysk->sk_subtype;
1043 6 : if (arraysk_elemtype == InvalidOid)
1044 0 : arraysk_elemtype = rel->rd_opcintype[arraysk->sk_attno - 1];
1045 6 : cmp_proc = get_opfamily_proc(rel->rd_opfamily[arraysk->sk_attno - 1],
1046 : skey->sk_subtype, arraysk_elemtype,
1047 : BTORDER_PROC);
1048 6 : if (!RegProcedureIsValid(cmp_proc))
1049 : {
1050 : /* Can't make the comparison */
1051 0 : *qual_ok = false; /* suppress compiler warnings */
1052 0 : return false;
1053 : }
1054 :
1055 : /* We have all we need to determine redundancy/contradictoriness */
1056 6 : orderprocp = &crosstypeproc;
1057 6 : fmgr_info(cmp_proc, orderprocp);
1058 : }
1059 :
1060 30 : matchelem = _bt_binsrch_array_skey(orderprocp, false,
1061 : NoMovementScanDirection,
1062 : skey->sk_argument, false, array,
1063 : arraysk, &cmpresult);
1064 :
1065 30 : switch (skey->sk_strategy)
1066 : {
1067 6 : case BTLessStrategyNumber:
1068 6 : cmpexact = 1; /* exclude exact match, if any */
1069 : /* FALL THRU */
1070 6 : case BTLessEqualStrategyNumber:
1071 6 : if (cmpresult >= cmpexact)
1072 0 : matchelem++;
1073 : /* Resize, keeping elements from the start of the array */
1074 6 : new_nelems = matchelem;
1075 6 : break;
1076 12 : case BTEqualStrategyNumber:
1077 12 : if (cmpresult != 0)
1078 : {
1079 : /* qual is unsatisfiable */
1080 6 : new_nelems = 0;
1081 : }
1082 : else
1083 : {
1084 : /* Shift matching element to the start of the array, resize */
1085 6 : array->elem_values[0] = array->elem_values[matchelem];
1086 6 : new_nelems = 1;
1087 : }
1088 12 : break;
1089 6 : case BTGreaterEqualStrategyNumber:
1090 6 : cmpexact = 1; /* include exact match, if any */
1091 : /* FALL THRU */
1092 12 : case BTGreaterStrategyNumber:
1093 12 : if (cmpresult >= cmpexact)
1094 6 : matchelem++;
1095 : /* Shift matching elements to the start of the array, resize */
1096 12 : new_nelems = array->num_elems - matchelem;
1097 12 : memmove(array->elem_values, array->elem_values + matchelem,
1098 : sizeof(Datum) * new_nelems);
1099 12 : break;
1100 0 : default:
1101 0 : elog(ERROR, "unrecognized StrategyNumber: %d",
1102 : (int) skey->sk_strategy);
1103 : break;
1104 : }
1105 :
1106 : Assert(new_nelems >= 0);
1107 : Assert(new_nelems <= array->num_elems);
1108 :
1109 30 : array->num_elems = new_nelems;
1110 30 : *qual_ok = new_nelems > 0;
1111 :
1112 30 : return true;
1113 : }
1114 :
1115 : /*
1116 : * _bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys
1117 : *
1118 : * If there are any SK_SEARCHARRAY scan keys, deconstruct the array(s) and
1119 : * set up BTArrayKeyInfo info for each one that is an equality-type key.
1120 : * Returns modified scan keys as input for further, standard preprocessing.
1121 : *
1122 : * Currently we perform two kinds of preprocessing to deal with redundancies.
1123 : * For inequality array keys, it's sufficient to find the extreme element
1124 : * value and replace the whole array with that scalar value. This eliminates
1125 : * all but one array element as redundant. Similarly, we are capable of
1126 : * "merging together" multiple equality array keys (from two or more input
1127 : * scan keys) into a single output scan key containing only the intersecting
1128 : * array elements. This can eliminate many redundant array elements, as well
1129 : * as eliminating whole array scan keys as redundant. It can also allow us to
1130 : * detect contradictory quals.
1131 : *
1132 : * Caller must pass *new_numberOfKeys to give us a way to change the number of
1133 : * scan keys that caller treats as input to standard preprocessing steps. The
1134 : * returned array is smaller than scan->keyData[] when we could eliminate a
1135 : * redundant array scan key (redundant with another array scan key). It is
1136 : * convenient for _bt_preprocess_keys caller to have to deal with no more than
1137 : * one equality strategy array scan key per index attribute. We'll always be
1138 : * able to set things up that way when complete opfamilies are used.
1139 : *
1140 : * We set the scan key references from the scan's BTArrayKeyInfo info array to
1141 : * offsets into the temp modified input array returned to caller. Scans that
1142 : * have array keys should call _bt_preprocess_array_keys_final when standard
1143 : * preprocessing steps are complete. This will convert the scan key offset
1144 : * references into references to the scan's so->keyData[] output scan keys.
1145 : *
1146 : * Note: the reason we need to return a temp scan key array, rather than just
1147 : * scribbling on scan->keyData, is that callers are permitted to call btrescan
1148 : * without supplying a new set of scankey data.
1149 : */
1150 : static ScanKey
1151 13400074 : _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
1152 : {
1153 13400074 : BTScanOpaque so = (BTScanOpaque) scan->opaque;
1154 13400074 : Relation rel = scan->indexRelation;
1155 13400074 : int numberOfKeys = scan->numberOfKeys;
1156 13400074 : int16 *indoption = rel->rd_indoption;
1157 : int numArrayKeys,
1158 13400074 : output_ikey = 0;
1159 13400074 : int origarrayatt = InvalidAttrNumber,
1160 13400074 : origarraykey = -1;
1161 13400074 : Oid origelemtype = InvalidOid;
1162 : ScanKey cur;
1163 : MemoryContext oldContext;
1164 : ScanKey arrayKeyData; /* modified copy of scan->keyData */
1165 :
1166 : Assert(numberOfKeys);
1167 :
1168 : /* Quick check to see if there are any array keys */
1169 13400074 : numArrayKeys = 0;
1170 34765842 : for (int i = 0; i < numberOfKeys; i++)
1171 : {
1172 21365768 : cur = &scan->keyData[i];
1173 21365768 : if (cur->sk_flags & SK_SEARCHARRAY)
1174 : {
1175 1286 : numArrayKeys++;
1176 : Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
1177 : /* If any arrays are null as a whole, we can quit right now. */
1178 1286 : if (cur->sk_flags & SK_ISNULL)
1179 : {
1180 0 : so->qual_ok = false;
1181 0 : return NULL;
1182 : }
1183 : }
1184 : }
1185 :
1186 : /* Quit if nothing to do. */
1187 13400074 : if (numArrayKeys == 0)
1188 13398962 : return NULL;
1189 :
1190 : /*
1191 : * Make a scan-lifespan context to hold array-associated data, or reset it
1192 : * if we already have one from a previous rescan cycle.
1193 : */
1194 1112 : if (so->arrayContext == NULL)
1195 1112 : so->arrayContext = AllocSetContextCreate(CurrentMemoryContext,
1196 : "BTree array context",
1197 : ALLOCSET_SMALL_SIZES);
1198 : else
1199 0 : MemoryContextReset(so->arrayContext);
1200 :
1201 1112 : oldContext = MemoryContextSwitchTo(so->arrayContext);
1202 :
1203 : /* Create output scan keys in the workspace context */
1204 1112 : arrayKeyData = (ScanKey) palloc(numberOfKeys * sizeof(ScanKeyData));
1205 :
1206 : /* Allocate space for per-array data in the workspace context */
1207 1112 : so->arrayKeys = (BTArrayKeyInfo *) palloc(numArrayKeys * sizeof(BTArrayKeyInfo));
1208 :
1209 : /* Allocate space for ORDER procs used to help _bt_checkkeys */
1210 1112 : so->orderProcs = (FmgrInfo *) palloc(numberOfKeys * sizeof(FmgrInfo));
1211 :
1212 : /* Now process each array key */
1213 1112 : numArrayKeys = 0;
1214 2866 : for (int input_ikey = 0; input_ikey < numberOfKeys; input_ikey++)
1215 : {
1216 : FmgrInfo sortproc;
1217 1760 : FmgrInfo *sortprocp = &sortproc;
1218 : Oid elemtype;
1219 : bool reverse;
1220 : ArrayType *arrayval;
1221 : int16 elmlen;
1222 : bool elmbyval;
1223 : char elmalign;
1224 : int num_elems;
1225 : Datum *elem_values;
1226 : bool *elem_nulls;
1227 : int num_nonnulls;
1228 : int j;
1229 :
1230 : /*
1231 : * Provisionally copy scan key into arrayKeyData[] array we'll return
1232 : * to _bt_preprocess_keys caller
1233 : */
1234 1760 : cur = &arrayKeyData[output_ikey];
1235 1760 : *cur = scan->keyData[input_ikey];
1236 :
1237 1760 : if (!(cur->sk_flags & SK_SEARCHARRAY))
1238 : {
1239 474 : output_ikey++; /* keep this non-array scan key */
1240 492 : continue;
1241 : }
1242 :
1243 : /*
1244 : * Deconstruct the array into elements
1245 : */
1246 1286 : arrayval = DatumGetArrayTypeP(cur->sk_argument);
1247 : /* We could cache this data, but not clear it's worth it */
1248 1286 : get_typlenbyvalalign(ARR_ELEMTYPE(arrayval),
1249 : &elmlen, &elmbyval, &elmalign);
1250 1286 : deconstruct_array(arrayval,
1251 : ARR_ELEMTYPE(arrayval),
1252 : elmlen, elmbyval, elmalign,
1253 : &elem_values, &elem_nulls, &num_elems);
1254 :
1255 : /*
1256 : * Compress out any null elements. We can ignore them since we assume
1257 : * all btree operators are strict.
1258 : */
1259 1286 : num_nonnulls = 0;
1260 6238 : for (j = 0; j < num_elems; j++)
1261 : {
1262 4952 : if (!elem_nulls[j])
1263 4952 : elem_values[num_nonnulls++] = elem_values[j];
1264 : }
1265 :
1266 : /* We could pfree(elem_nulls) now, but not worth the cycles */
1267 :
1268 : /* If there's no non-nulls, the scan qual is unsatisfiable */
1269 1286 : if (num_nonnulls == 0)
1270 : {
1271 0 : so->qual_ok = false;
1272 6 : break;
1273 : }
1274 :
1275 : /*
1276 : * Determine the nominal datatype of the array elements. We have to
1277 : * support the convention that sk_subtype == InvalidOid means the
1278 : * opclass input type; this is a hack to simplify life for
1279 : * ScanKeyInit().
1280 : */
1281 1286 : elemtype = cur->sk_subtype;
1282 1286 : if (elemtype == InvalidOid)
1283 0 : elemtype = rel->rd_opcintype[cur->sk_attno - 1];
1284 :
1285 : /*
1286 : * If the comparison operator is not equality, then the array qual
1287 : * degenerates to a simple comparison against the smallest or largest
1288 : * non-null array element, as appropriate.
1289 : */
1290 1286 : switch (cur->sk_strategy)
1291 : {
1292 6 : case BTLessStrategyNumber:
1293 : case BTLessEqualStrategyNumber:
1294 6 : cur->sk_argument =
1295 6 : _bt_find_extreme_element(scan, cur, elemtype,
1296 : BTGreaterStrategyNumber,
1297 : elem_values, num_nonnulls);
1298 6 : output_ikey++; /* keep this transformed scan key */
1299 6 : continue;
1300 1274 : case BTEqualStrategyNumber:
1301 : /* proceed with rest of loop */
1302 1274 : break;
1303 6 : case BTGreaterEqualStrategyNumber:
1304 : case BTGreaterStrategyNumber:
1305 6 : cur->sk_argument =
1306 6 : _bt_find_extreme_element(scan, cur, elemtype,
1307 : BTLessStrategyNumber,
1308 : elem_values, num_nonnulls);
1309 6 : output_ikey++; /* keep this transformed scan key */
1310 6 : continue;
1311 0 : default:
1312 0 : elog(ERROR, "unrecognized StrategyNumber: %d",
1313 : (int) cur->sk_strategy);
1314 : break;
1315 : }
1316 :
1317 : /*
1318 : * We'll need a 3-way ORDER proc to perform binary searches for the
1319 : * next matching array element. Set that up now.
1320 : *
1321 : * Array scan keys with cross-type equality operators will require a
1322 : * separate same-type ORDER proc for sorting their array. Otherwise,
1323 : * sortproc just points to the same proc used during binary searches.
1324 : */
1325 1274 : _bt_setup_array_cmp(scan, cur, elemtype,
1326 1274 : &so->orderProcs[output_ikey], &sortprocp);
1327 :
1328 : /*
1329 : * Sort the non-null elements and eliminate any duplicates. We must
1330 : * sort in the same ordering used by the index column, so that the
1331 : * arrays can be advanced in lockstep with the scan's progress through
1332 : * the index's key space.
1333 : */
1334 1274 : reverse = (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0;
1335 1274 : num_elems = _bt_sort_array_elements(cur, sortprocp, reverse,
1336 : elem_values, num_nonnulls);
1337 :
1338 1274 : if (origarrayatt == cur->sk_attno)
1339 : {
1340 12 : BTArrayKeyInfo *orig = &so->arrayKeys[origarraykey];
1341 :
1342 : /*
1343 : * This array scan key is redundant with a previous equality
1344 : * operator array scan key. Merge the two arrays together to
1345 : * eliminate contradictory non-intersecting elements (or try to).
1346 : *
1347 : * We merge this next array back into attribute's original array.
1348 : */
1349 : Assert(arrayKeyData[orig->scan_key].sk_attno == cur->sk_attno);
1350 : Assert(arrayKeyData[orig->scan_key].sk_collation ==
1351 : cur->sk_collation);
1352 12 : if (_bt_merge_arrays(scan, cur, sortprocp, reverse,
1353 : origelemtype, elemtype,
1354 : orig->elem_values, &orig->num_elems,
1355 : elem_values, num_elems))
1356 : {
1357 : /* Successfully eliminated this array */
1358 12 : pfree(elem_values);
1359 :
1360 : /*
1361 : * If no intersecting elements remain in the original array,
1362 : * the scan qual is unsatisfiable
1363 : */
1364 12 : if (orig->num_elems == 0)
1365 : {
1366 6 : so->qual_ok = false;
1367 6 : break;
1368 : }
1369 :
1370 : /* Throw away this scan key/array */
1371 6 : continue;
1372 : }
1373 :
1374 : /*
1375 : * Unable to merge this array with previous array due to a lack of
1376 : * suitable cross-type opfamily support. Will need to keep both
1377 : * scan keys/arrays.
1378 : */
1379 : }
1380 : else
1381 : {
1382 : /*
1383 : * This array is the first for current index attribute.
1384 : *
1385 : * If it turns out to not be the last array (that is, if the next
1386 : * array is redundantly applied to this same index attribute),
1387 : * we'll then treat this array as the attribute's "original" array
1388 : * when merging.
1389 : */
1390 1262 : origarrayatt = cur->sk_attno;
1391 1262 : origarraykey = numArrayKeys;
1392 1262 : origelemtype = elemtype;
1393 : }
1394 :
1395 : /*
1396 : * And set up the BTArrayKeyInfo data.
1397 : *
1398 : * Note: _bt_preprocess_array_keys_final will fix-up each array's
1399 : * scan_key field later on, after so->keyData[] has been finalized.
1400 : */
1401 1262 : so->arrayKeys[numArrayKeys].scan_key = output_ikey;
1402 1262 : so->arrayKeys[numArrayKeys].num_elems = num_elems;
1403 1262 : so->arrayKeys[numArrayKeys].elem_values = elem_values;
1404 1262 : numArrayKeys++;
1405 1262 : output_ikey++; /* keep this scan key/array */
1406 : }
1407 :
1408 : /* Set final number of equality-type array keys */
1409 1112 : so->numArrayKeys = numArrayKeys;
1410 : /* Set number of scan keys remaining in arrayKeyData[] */
1411 1112 : *new_numberOfKeys = output_ikey;
1412 :
1413 1112 : MemoryContextSwitchTo(oldContext);
1414 :
1415 1112 : return arrayKeyData;
1416 : }
1417 :
1418 : /*
1419 : * _bt_preprocess_array_keys_final() -- fix up array scan key references
1420 : *
1421 : * When _bt_preprocess_array_keys performed initial array preprocessing, it
1422 : * set each array's array->scan_key to its scankey's arrayKeyData[] offset.
1423 : * This function handles translation of the scan key references from the
1424 : * BTArrayKeyInfo info array, from input scan key references (to the keys in
1425 : * arrayKeyData[]), into output references (to the keys in so->keyData[]).
1426 : * Caller's keyDataMap[] array tells us how to perform this remapping.
1427 : *
1428 : * Also finalizes so->orderProcs[] for the scan. Arrays already have an ORDER
1429 : * proc, which might need to be repositioned to its so->keyData[]-wise offset
1430 : * (very much like the remapping that we apply to array->scan_key references).
1431 : * Non-array equality strategy scan keys (that survived preprocessing) don't
1432 : * yet have an so->orderProcs[] entry, so we set one for them here.
1433 : *
1434 : * Also converts single-element array scan keys into equivalent non-array
1435 : * equality scan keys, which decrements so->numArrayKeys. It's possible that
1436 : * this will leave this new btrescan without any arrays at all. This isn't
1437 : * necessary for correctness; it's just an optimization. Non-array equality
1438 : * scan keys are slightly faster than equivalent array scan keys at runtime.
1439 : */
1440 : static void
1441 582 : _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
1442 : {
1443 582 : BTScanOpaque so = (BTScanOpaque) scan->opaque;
1444 582 : Relation rel = scan->indexRelation;
1445 582 : int arrayidx = 0;
1446 582 : int last_equal_output_ikey PG_USED_FOR_ASSERTS_ONLY = -1;
1447 :
1448 : Assert(so->qual_ok);
1449 :
1450 : /*
1451 : * Nothing for us to do when _bt_preprocess_array_keys only had to deal
1452 : * with array inequalities
1453 : */
1454 582 : if (so->numArrayKeys == 0)
1455 0 : return;
1456 :
1457 1758 : for (int output_ikey = 0; output_ikey < so->numberOfKeys; output_ikey++)
1458 : {
1459 1188 : ScanKey outkey = so->keyData + output_ikey;
1460 : int input_ikey;
1461 1188 : bool found PG_USED_FOR_ASSERTS_ONLY = false;
1462 :
1463 : Assert(outkey->sk_strategy != InvalidStrategy);
1464 :
1465 1188 : if (outkey->sk_strategy != BTEqualStrategyNumber)
1466 24 : continue;
1467 :
1468 1164 : input_ikey = keyDataMap[output_ikey];
1469 :
1470 : Assert(last_equal_output_ikey < output_ikey);
1471 : Assert(last_equal_output_ikey < input_ikey);
1472 1164 : last_equal_output_ikey = output_ikey;
1473 :
1474 : /*
1475 : * We're lazy about looking up ORDER procs for non-array keys, since
1476 : * not all input keys become output keys. Take care of it now.
1477 : */
1478 1164 : if (!(outkey->sk_flags & SK_SEARCHARRAY))
1479 : {
1480 : Oid elemtype;
1481 :
1482 : /* No need for an ORDER proc given an IS NULL scan key */
1483 420 : if (outkey->sk_flags & SK_SEARCHNULL)
1484 6 : continue;
1485 :
1486 : /*
1487 : * A non-required scan key doesn't need an ORDER proc, either
1488 : * (unless it's associated with an array, which this one isn't)
1489 : */
1490 414 : if (!(outkey->sk_flags & SK_BT_REQFWD))
1491 90 : continue;
1492 :
1493 324 : elemtype = outkey->sk_subtype;
1494 324 : if (elemtype == InvalidOid)
1495 0 : elemtype = rel->rd_opcintype[outkey->sk_attno - 1];
1496 :
1497 324 : _bt_setup_array_cmp(scan, outkey, elemtype,
1498 324 : &so->orderProcs[output_ikey], NULL);
1499 324 : continue;
1500 : }
1501 :
1502 : /*
1503 : * Reorder existing array scan key so->orderProcs[] entries.
1504 : *
1505 : * Doing this in-place is safe because preprocessing is required to
1506 : * output all equality strategy scan keys in original input order
1507 : * (among each group of entries against the same index attribute).
1508 : * This is also the order that the arrays themselves appear in.
1509 : */
1510 744 : so->orderProcs[output_ikey] = so->orderProcs[input_ikey];
1511 :
1512 : /* Fix-up array->scan_key references for arrays */
1513 744 : for (; arrayidx < so->numArrayKeys; arrayidx++)
1514 : {
1515 744 : BTArrayKeyInfo *array = &so->arrayKeys[arrayidx];
1516 :
1517 : Assert(array->num_elems > 0);
1518 :
1519 744 : if (array->scan_key == input_ikey)
1520 : {
1521 : /* found it */
1522 744 : array->scan_key = output_ikey;
1523 744 : found = true;
1524 :
1525 : /*
1526 : * Transform array scan keys that have exactly 1 element
1527 : * remaining (following all prior preprocessing) into
1528 : * equivalent non-array scan keys.
1529 : */
1530 744 : if (array->num_elems == 1)
1531 : {
1532 18 : outkey->sk_flags &= ~SK_SEARCHARRAY;
1533 18 : outkey->sk_argument = array->elem_values[0];
1534 18 : so->numArrayKeys--;
1535 :
1536 : /* If we're out of array keys, we can quit right away */
1537 18 : if (so->numArrayKeys == 0)
1538 12 : return;
1539 :
1540 : /* Shift other arrays forward */
1541 6 : memmove(array, array + 1,
1542 : sizeof(BTArrayKeyInfo) *
1543 6 : (so->numArrayKeys - arrayidx));
1544 :
1545 : /*
1546 : * Don't increment arrayidx (there was an entry that was
1547 : * just shifted forward to the offset at arrayidx, which
1548 : * will still need to be matched)
1549 : */
1550 : }
1551 : else
1552 : {
1553 : /* Match found, so done with this array */
1554 726 : arrayidx++;
1555 : }
1556 :
1557 732 : break;
1558 : }
1559 : }
1560 :
1561 : Assert(found);
1562 : }
1563 :
1564 : /*
1565 : * Parallel index scans require space in shared memory to store the
1566 : * current array elements (for arrays kept by preprocessing) to schedule
1567 : * the next primitive index scan. The underlying structure is protected
1568 : * using a spinlock, so defensively limit its size. In practice this can
1569 : * only affect parallel scans that use an incomplete opfamily.
1570 : */
1571 570 : if (scan->parallel_scan && so->numArrayKeys > INDEX_MAX_KEYS)
1572 0 : ereport(ERROR,
1573 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1574 : errmsg_internal("number of array scan keys left by preprocessing (%d) exceeds the maximum allowed by parallel btree index scans (%d)",
1575 : so->numArrayKeys, INDEX_MAX_KEYS)));
1576 : }
1577 :
1578 : /*
1579 : * _bt_find_extreme_element() -- get least or greatest array element
1580 : *
1581 : * scan and skey identify the index column, whose opfamily determines the
1582 : * comparison semantics. strat should be BTLessStrategyNumber to get the
1583 : * least element, or BTGreaterStrategyNumber to get the greatest.
1584 : */
1585 : static Datum
1586 12 : _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey, Oid elemtype,
1587 : StrategyNumber strat,
1588 : Datum *elems, int nelems)
1589 : {
1590 12 : Relation rel = scan->indexRelation;
1591 : Oid cmp_op;
1592 : RegProcedure cmp_proc;
1593 : FmgrInfo flinfo;
1594 : Datum result;
1595 : int i;
1596 :
1597 : /*
1598 : * Look up the appropriate comparison operator in the opfamily.
1599 : *
1600 : * Note: it's possible that this would fail, if the opfamily is
1601 : * incomplete, but it seems quite unlikely that an opfamily would omit
1602 : * non-cross-type comparison operators for any datatype that it supports
1603 : * at all.
1604 : */
1605 : Assert(skey->sk_strategy != BTEqualStrategyNumber);
1606 : Assert(OidIsValid(elemtype));
1607 12 : cmp_op = get_opfamily_member(rel->rd_opfamily[skey->sk_attno - 1],
1608 : elemtype,
1609 : elemtype,
1610 : strat);
1611 12 : if (!OidIsValid(cmp_op))
1612 0 : elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
1613 : strat, elemtype, elemtype,
1614 : rel->rd_opfamily[skey->sk_attno - 1]);
1615 12 : cmp_proc = get_opcode(cmp_op);
1616 12 : if (!RegProcedureIsValid(cmp_proc))
1617 0 : elog(ERROR, "missing oprcode for operator %u", cmp_op);
1618 :
1619 12 : fmgr_info(cmp_proc, &flinfo);
1620 :
1621 : Assert(nelems > 0);
1622 12 : result = elems[0];
1623 36 : for (i = 1; i < nelems; i++)
1624 : {
1625 24 : if (DatumGetBool(FunctionCall2Coll(&flinfo,
1626 : skey->sk_collation,
1627 24 : elems[i],
1628 : result)))
1629 6 : result = elems[i];
1630 : }
1631 :
1632 12 : return result;
1633 : }
1634 :
1635 : /*
1636 : * _bt_setup_array_cmp() -- Set up array comparison functions
1637 : *
1638 : * Sets ORDER proc in caller's orderproc argument, which is used during binary
1639 : * searches of arrays during the index scan. Also sets a same-type ORDER proc
1640 : * in caller's *sortprocp argument, which is used when sorting the array.
1641 : *
1642 : * Preprocessing calls here with all equality strategy scan keys (when scan
1643 : * uses equality array keys), including those not associated with any array.
1644 : * See _bt_advance_array_keys for an explanation of why it'll need to treat
1645 : * simple scalar equality scan keys as degenerate single element arrays.
1646 : *
1647 : * Caller should pass an orderproc pointing to space that'll store the ORDER
1648 : * proc for the scan, and a *sortprocp pointing to its own separate space.
1649 : * When calling here for a non-array scan key, sortprocp arg should be NULL.
1650 : *
1651 : * In the common case where we don't need to deal with cross-type operators,
1652 : * only one ORDER proc is actually required by caller. We'll set *sortprocp
1653 : * to point to the same memory that caller's orderproc continues to point to.
1654 : * Otherwise, *sortprocp will continue to point to caller's own space. Either
1655 : * way, *sortprocp will point to a same-type ORDER proc (since that's the only
1656 : * safe way to sort/deduplicate the array associated with caller's scan key).
1657 : */
1658 : static void
1659 1598 : _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype,
1660 : FmgrInfo *orderproc, FmgrInfo **sortprocp)
1661 : {
1662 1598 : BTScanOpaque so = (BTScanOpaque) scan->opaque;
1663 1598 : Relation rel = scan->indexRelation;
1664 : RegProcedure cmp_proc;
1665 1598 : Oid opcintype = rel->rd_opcintype[skey->sk_attno - 1];
1666 :
1667 : Assert(skey->sk_strategy == BTEqualStrategyNumber);
1668 : Assert(OidIsValid(elemtype));
1669 :
1670 : /*
1671 : * If scankey operator is not a cross-type comparison, we can use the
1672 : * cached comparison function; otherwise gotta look it up in the catalogs
1673 : */
1674 1598 : if (elemtype == opcintype)
1675 : {
1676 : /* Set same-type ORDER procs for caller */
1677 1592 : *orderproc = *index_getprocinfo(rel, skey->sk_attno, BTORDER_PROC);
1678 1592 : if (sortprocp)
1679 1268 : *sortprocp = orderproc;
1680 :
1681 1592 : return;
1682 : }
1683 :
1684 : /*
1685 : * Look up the appropriate cross-type comparison function in the opfamily.
1686 : *
1687 : * Use the opclass input type as the left hand arg type, and the array
1688 : * element type as the right hand arg type (since binary searches use an
1689 : * index tuple's attribute value to search for a matching array element).
1690 : *
1691 : * Note: it's possible that this would fail, if the opfamily is
1692 : * incomplete, but only in cases where it's quite likely that _bt_first
1693 : * would fail in just the same way (had we not failed before it could).
1694 : */
1695 6 : cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
1696 : opcintype, elemtype, BTORDER_PROC);
1697 6 : if (!RegProcedureIsValid(cmp_proc))
1698 0 : elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
1699 : BTORDER_PROC, opcintype, elemtype, skey->sk_attno,
1700 : RelationGetRelationName(rel));
1701 :
1702 : /* Set cross-type ORDER proc for caller */
1703 6 : fmgr_info_cxt(cmp_proc, orderproc, so->arrayContext);
1704 :
1705 : /* Done if caller doesn't actually have an array they'll need to sort */
1706 6 : if (!sortprocp)
1707 0 : return;
1708 :
1709 : /*
1710 : * Look up the appropriate same-type comparison function in the opfamily.
1711 : *
1712 : * Note: it's possible that this would fail, if the opfamily is
1713 : * incomplete, but it seems quite unlikely that an opfamily would omit
1714 : * non-cross-type comparison procs for any datatype that it supports at
1715 : * all.
1716 : */
1717 6 : cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
1718 : elemtype, elemtype, BTORDER_PROC);
1719 6 : if (!RegProcedureIsValid(cmp_proc))
1720 0 : elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
1721 : BTORDER_PROC, elemtype, elemtype,
1722 : skey->sk_attno, RelationGetRelationName(rel));
1723 :
1724 : /* Set same-type ORDER proc for caller */
1725 6 : fmgr_info_cxt(cmp_proc, *sortprocp, so->arrayContext);
1726 : }
1727 :
1728 : /*
1729 : * _bt_sort_array_elements() -- sort and de-dup array elements
1730 : *
1731 : * The array elements are sorted in-place, and the new number of elements
1732 : * after duplicate removal is returned.
1733 : *
1734 : * skey identifies the index column whose opfamily determines the comparison
1735 : * semantics, and sortproc is a corresponding ORDER proc. If reverse is true,
1736 : * we sort in descending order.
1737 : */
1738 : static int
1739 1274 : _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc, bool reverse,
1740 : Datum *elems, int nelems)
1741 : {
1742 : BTSortArrayContext cxt;
1743 :
1744 1274 : if (nelems <= 1)
1745 12 : return nelems; /* no work to do */
1746 :
1747 : /* Sort the array elements */
1748 1262 : cxt.sortproc = sortproc;
1749 1262 : cxt.collation = skey->sk_collation;
1750 1262 : cxt.reverse = reverse;
1751 1262 : qsort_arg(elems, nelems, sizeof(Datum),
1752 : _bt_compare_array_elements, &cxt);
1753 :
1754 : /* Now scan the sorted elements and remove duplicates */
1755 1262 : return qunique_arg(elems, nelems, sizeof(Datum),
1756 : _bt_compare_array_elements, &cxt);
1757 : }
1758 :
1759 : /*
1760 : * _bt_merge_arrays() -- merge next array's elements into an original array
1761 : *
1762 : * Called when preprocessing encounters a pair of array equality scan keys,
1763 : * both against the same index attribute (during initial array preprocessing).
1764 : * Merging reorganizes caller's original array (the left hand arg) in-place,
1765 : * without ever copying elements from one array into the other. (Mixing the
1766 : * elements together like this would be wrong, since they don't necessarily
1767 : * use the same underlying element type, despite all the other similarities.)
1768 : *
1769 : * Both arrays must have already been sorted and deduplicated by calling
1770 : * _bt_sort_array_elements. sortproc is the same-type ORDER proc that was
1771 : * just used to sort and deduplicate caller's "next" array. We'll usually be
1772 : * able to reuse that order PROC to merge the arrays together now. If not,
1773 : * then we'll perform a separate ORDER proc lookup.
1774 : *
1775 : * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
1776 : * may not be able to determine which elements are contradictory. If we have
1777 : * the required ORDER proc then we return true (and validly set *nelems_orig),
1778 : * guaranteeing that at least the next array can be considered redundant. We
1779 : * return false if the required comparisons cannot be made (caller must keep
1780 : * both arrays when this happens).
1781 : */
1782 : static bool
1783 12 : _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, FmgrInfo *sortproc,
1784 : bool reverse, Oid origelemtype, Oid nextelemtype,
1785 : Datum *elems_orig, int *nelems_orig,
1786 : Datum *elems_next, int nelems_next)
1787 : {
1788 12 : Relation rel = scan->indexRelation;
1789 12 : BTScanOpaque so = (BTScanOpaque) scan->opaque;
1790 : BTSortArrayContext cxt;
1791 12 : int nelems_orig_start = *nelems_orig,
1792 12 : nelems_orig_merged = 0;
1793 12 : FmgrInfo *mergeproc = sortproc;
1794 : FmgrInfo crosstypeproc;
1795 :
1796 : Assert(skey->sk_strategy == BTEqualStrategyNumber);
1797 : Assert(OidIsValid(origelemtype) && OidIsValid(nextelemtype));
1798 :
1799 12 : if (origelemtype != nextelemtype)
1800 : {
1801 : RegProcedure cmp_proc;
1802 :
1803 : /*
1804 : * Cross-array-element-type merging is required, so can't just reuse
1805 : * sortproc when merging
1806 : */
1807 6 : cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
1808 : origelemtype, nextelemtype, BTORDER_PROC);
1809 6 : if (!RegProcedureIsValid(cmp_proc))
1810 : {
1811 : /* Can't make the required comparisons */
1812 0 : return false;
1813 : }
1814 :
1815 : /* We have all we need to determine redundancy/contradictoriness */
1816 6 : mergeproc = &crosstypeproc;
1817 6 : fmgr_info_cxt(cmp_proc, mergeproc, so->arrayContext);
1818 : }
1819 :
1820 12 : cxt.sortproc = mergeproc;
1821 12 : cxt.collation = skey->sk_collation;
1822 12 : cxt.reverse = reverse;
1823 :
1824 54 : for (int i = 0, j = 0; i < nelems_orig_start && j < nelems_next;)
1825 : {
1826 42 : Datum *oelem = elems_orig + i,
1827 42 : *nelem = elems_next + j;
1828 42 : int res = _bt_compare_array_elements(oelem, nelem, &cxt);
1829 :
1830 42 : if (res == 0)
1831 : {
1832 6 : elems_orig[nelems_orig_merged++] = *oelem;
1833 6 : i++;
1834 6 : j++;
1835 : }
1836 36 : else if (res < 0)
1837 24 : i++;
1838 : else /* res > 0 */
1839 12 : j++;
1840 : }
1841 :
1842 12 : *nelems_orig = nelems_orig_merged;
1843 :
1844 12 : return true;
1845 : }
1846 :
1847 : /*
1848 : * qsort_arg comparator for sorting array elements
1849 : */
1850 : static int
1851 9498 : _bt_compare_array_elements(const void *a, const void *b, void *arg)
1852 : {
1853 9498 : Datum da = *((const Datum *) a);
1854 9498 : Datum db = *((const Datum *) b);
1855 9498 : BTSortArrayContext *cxt = (BTSortArrayContext *) arg;
1856 : int32 compare;
1857 :
1858 9498 : compare = DatumGetInt32(FunctionCall2Coll(cxt->sortproc,
1859 : cxt->collation,
1860 : da, db));
1861 9498 : if (cxt->reverse)
1862 30 : INVERT_COMPARE_RESULT(compare);
1863 9498 : return compare;
1864 : }
|
