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