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