1/*-------------------------------------------------------------------------
4 * Preprocessing for Postgres btree scan keys.
6 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/access/nbtree/nbtpreprocesskeys.c
13 *-------------------------------------------------------------------------
67 int *numSkipArrayKeys_out);
70 Datum *elems,
int nelems);
74 bool reverse,
Datum *elems,
int nelems);
77 Oid origelemtype,
Oid nextelemtype,
78 Datum *elems_orig,
int *nelems_orig,
79 Datum *elems_next,
int nelems_next);
84 * _bt_preprocess_keys() -- Preprocess scan keys
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.
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.
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.)
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.
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.
126 * If we never generated skip array scan keys, it would be possible for "gaps"
127 * to appear that make it unsafe to mark any subsequent input scan keys
128 * (copied from scan->keyData[]) as required to continue the scan. Prior to
129 * Postgres 18, a qual like "WHERE y = 4" always resulted in a full scan.
130 * This qual now becomes "WHERE x = ANY('{every possible x value}') and y = 4"
131 * on output. In other words, preprocessing now adds a skip array on "x".
132 * This has the potential to be much more efficient than a full index scan
133 * (though it behaves like a full scan when there's many distinct "x" values).
135 * Typically, redundant keys are eliminated: we keep only the tightest
136 * >/>= bound and the tightest </<= bound, and if there's an = key then
137 * that's the only one returned. (So, we return either a single = key,
138 * or one or two boundary-condition keys for each attr.) However, if we
139 * cannot compare two keys for lack of a suitable cross-type operator,
140 * we cannot eliminate either key.
142 * When all redundant keys could not be eliminated, we'll output a key array
143 * that can more or less be treated as if it had no redundant keys. Suppose
144 * we have "x > 4::int AND x > 10::bigint AND x < 70", and we are unable to
145 * determine which > key is more restrictive for lack of a suitable cross-type
146 * operator. We'll arbitrarily pick one of the > keys; the other > key won't
147 * be marked required. Obviously, the scan will be less efficient if we
148 * choose x > 4 over x > 10 -- but it can still largely proceed as if there
149 * was only a single > condition. "x > 10" will be placed at the end of the
150 * so->keyData[] output array. It'll always be evaluated last, after the keys
151 * that could be marked required in the usual way (after "x > 4 AND x < 70").
152 * This can sometimes result in so->keyData[] keys that aren't even in index
153 * attribute order (if the qual involves multiple attributes). The scan's
154 * required keys will still be in attribute order, though, so it can't matter.
156 * This scheme ensures that _bt_first always uses the same set of keys at the
157 * start of a forwards scan as those _bt_checkkeys uses to determine when to
158 * end a similar backwards scan (and vice-versa). _bt_advance_array_keys
159 * depends on this: it expects to be able to reliably predict what the next
160 * _bt_first call will do by testing whether _bt_checkkeys' routines report
161 * that the final tuple on the page is past the end of matches for the scan's
162 * keys with the scan direction flipped. If it is (if continuescan=false),
163 * then it follows that calling _bt_first will, at a minimum, relocate the
164 * scan to the very next leaf page (in the current scan direction).
166 * As a byproduct of this work, we can detect contradictory quals such
167 * as "x = 1 AND x > 2". If we see that, we return so->qual_ok = false,
168 * indicating the scan need not be run at all since no tuples can match.
169 * (In this case we do not bother completing the output key array!)
170 * Again, missing cross-type operators might cause us to fail to prove the
171 * quals contradictory when they really are, but the scan will work correctly.
173 * Skip array = keys will even be generated in the presence of "contradictory"
174 * inequality quals when it'll enable marking later input quals as required.
175 * We'll merge any such inequalities into the generated skip array by setting
176 * its array.low_compare or array.high_compare key field. The resulting skip
177 * array will generate its array elements from a range that's constrained by
178 * any merged input inequalities (which won't get output in so->keyData[]).
180 * Row comparison keys currently have a couple of notable limitations.
181 * Right now we just transfer them into the preprocessed array without any
182 * editorialization. We can treat them the same as an ordinary inequality
183 * comparison on the row's first index column, for the purposes of the logic
184 * about required keys. Also, we are unable to merge a row comparison key
185 * into a skip array (only ordinary inequalities are merged). A key that
186 * comes after a Row comparison key is therefore never marked as required.
188 * Note: the reason we have to copy the preprocessed scan keys into private
189 * storage is that we are modifying the array based on comparisons of the
190 * key argument values, which could change on a rescan. Therefore we can't
191 * overwrite the source data.
199 int new_numberOfKeys;
200 int numberOfEqualCols;
204 redundant_key_kept =
false;
207 int *keyDataMap = NULL;
213 * Only need to do preprocessing once per btrescan, at most. All
214 * calls after the first are handled as no-ops.
219 /* initialize result variables */
223 if (numberOfKeys < 1)
224 return;
/* done if qual-less scan */
226 /* If any keys are SK_SEARCHARRAY type, set up array-key info */
230 /* unmatchable array, so give up */
235 * Treat arrayKeyData[] (a partially preprocessed copy of scan->keyData[])
236 * as our input if _bt_preprocess_array_keys just allocated it, else just
237 * use scan->keyData[]
241 inkeys = arrayKeyData;
243 /* Also maintain keyDataMap for remapping so->orderProcs[] later */
245 numberOfKeys *
sizeof(
int));
248 * Also enlarge output array when it might otherwise not have room for
249 * a skip array's scan key
258 /* we check that input keys are correctly ordered */
259 if (inkeys[0].sk_attno < 1)
260 elog(
ERROR,
"btree index keys must be ordered by attribute");
262 /* We can short-circuit most of the work if there's just one key */
263 if (numberOfKeys == 1)
265 /* Apply indoption to scankey (might change sk_strategy!) */
270 /* We can mark the qual as required if it's for first index col */
271 if (inkeys[0].sk_attno == 1)
276 * Don't call _bt_preprocess_array_keys_final in this fast path
277 * (we'll miss out on the single value array transformation, but
278 * that's not nearly as important when there's only one scan key)
291 * Otherwise, do the full set of pushups.
293 new_numberOfKeys = 0;
294 numberOfEqualCols = 0;
297 * Initialize for processing of keys for attr 1.
299 * xform[i] points to the currently best scan key of strategy type i+1; it
300 * is NULL if we haven't yet found such a key for this attr.
303 memset(xform, 0,
sizeof(xform));
306 * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to
307 * handle after-last-key processing. Actual exit from the loop is at the
308 * "break" statement below.
310 for (
int i = 0;;
i++)
315 if (
i < numberOfKeys)
317 /* Apply indoption to scankey (might change sk_strategy!) */
320 /* NULL can't be matched, so give up */
327 * If we are at the end of the keys for a particular attr, finish up
328 * processing and emit the cleaned-up keys.
330 if (
i == numberOfKeys || inkey->
sk_attno != attno)
332 int priorNumberOfEqualCols = numberOfEqualCols;
334 /* check input keys are correctly ordered */
335 if (i < numberOfKeys && inkey->sk_attno < attno)
336 elog(
ERROR,
"btree index keys must be ordered by attribute");
339 * If = has been specified, all other keys can be eliminated as
340 * redundant. Note that this is no less true if the = key is
341 * SEARCHARRAY; the only real difference is that the inequality
342 * key _becomes_ redundant by making _bt_compare_scankey_args
343 * eliminate the subset of elements that won't need to be matched
344 * (with SAOP arrays and skip arrays alike).
346 * If we have a case like "key = 1 AND key > 2", we set qual_ok to
347 * false and abandon further processing. We'll do the same thing
348 * given a case like "key IN (0, 1) AND key > 2".
350 * We also have to deal with the case of "key IS NULL", which is
351 * unsatisfiable in combination with any other index condition. By
352 * the time we get here, that's been classified as an equality
353 * check, and we've rejected any combination of it with a regular
354 * equality condition; but not with other types of conditions.
385 /* IS NULL is contradictory to anything else */
396 /* keys proven mutually contradictory */
400 /* else discard the redundant non-equality key */
401 xform[
j].inkey = NULL;
402 xform[
j].inkeyi = -1;
405 redundant_key_kept =
true;
407 /* track number of attrs for which we have "=" keys */
411 /* try to keep only one of <, <= */
427 redundant_key_kept =
true;
430 /* try to keep only one of >, >= */
446 redundant_key_kept =
true;
450 * Emit the cleaned-up keys into the so->keyData[] array, and then
451 * mark them if they are required. They are required (possibly
452 * only in one direction) if all attrs before this one had "=".
454 * In practice we'll rarely output non-required scan keys here;
455 * typically, _bt_preprocess_array_keys has already added "=" keys
456 * sufficient to form an unbroken series of "=" constraints on all
457 * attrs prior to the attr from the final scan->keyData[] key.
467 keyDataMap[new_numberOfKeys - 1] = xform[
j].inkeyi;
468 if (priorNumberOfEqualCols == attno - 1)
474 * Exit loop here if done.
476 if (
i == numberOfKeys)
479 /* Re-initialize for new attno */
481 memset(xform, 0,
sizeof(xform));
484 /* check strategy this key's operator corresponds to */
490 /* must track how input scan keys map to arrays */
496 * have we seen a scan key for this same attribute and using this same
497 * operator strategy before now?
499 if (xform[
j].inkey == NULL)
501 /* nope, so this scan key wins by default (at least for now) */
502 xform[
j].inkey = inkey;
504 xform[
j].arrayidx = arrayidx;
512 * Seen one of these before, so keep only the more restrictive key
518 * Have to set up array keys
531 array = &so->
arrayKeys[xform[
j].arrayidx - 1];
540 * Both scan keys might have arrays, in which case we'll
541 * arbitrarily pass only one of the arrays. That won't
542 * matter, since _bt_compare_scankey_args is aware that two
543 * SEARCHARRAY scan keys mean that _bt_preprocess_array_keys
544 * failed to eliminate redundant arrays through array merging.
545 * _bt_compare_scankey_args just returns false when it sees
546 * this; it won't even try to examine either array.
551 array, orderproc, &test_result))
553 /* Have all we need to determine redundancy */
557 * New key is more restrictive, and so replaces old key...
562 xform[
j].inkey = inkey;
564 xform[
j].arrayidx = arrayidx;
569 * ...unless we have to keep the old key because it's
570 * an array that rendered the new key redundant. We
571 * need to make sure that we don't throw away an array
572 * scan key. _bt_preprocess_array_keys_final expects
573 * us to keep all of the arrays that weren't already
574 * eliminated by _bt_preprocess_array_keys earlier on.
581 /* key == a && key == b, but a != b */
585 /* else old key is more restrictive, keep it */
590 * We can't determine which key is more restrictive. Push
591 * xform[j] directly to the output array, then set xform[j] to
594 * Note: We do things this way around so that our arrays are
595 * always in the same order as their corresponding scan keys.
596 * _bt_preprocess_array_keys_final expects this.
602 keyDataMap[new_numberOfKeys - 1] = xform[
j].inkeyi;
603 if (numberOfEqualCols == attno - 1)
605 xform[
j].inkey = inkey;
607 xform[
j].arrayidx = arrayidx;
608 redundant_key_kept =
true;
616 * Now that we've built a temporary mapping from so->keyData[] (output
617 * scan keys) to arrayKeyData[] (our input scan keys), fix array->scan_key
618 * references. Also consolidate the so->orderProcs[] array such that it
619 * can be subscripted using so->keyData[]-wise offsets.
625 * If there are remaining redundant inequality keys, we must make sure
626 * that each index attribute has no more than one required >/>= key, and
627 * no more than one required </<= key. Attributes that have one or more
628 * required = keys now must keep only one required key (the first = key).
633 /* Could pfree arrayKeyData/keyDataMap now, but not worth the cycles */
637 * Adjust a scankey's strategy and flags setting as needed for indoptions.
639 * We copy the appropriate indoption value into the scankey sk_flags
640 * (shifting to avoid clobbering system-defined flag bits). Also, if
641 * the DESC option is set, commute (flip) the operator strategy number.
643 * A secondary purpose is to check for IS NULL/NOT NULL scankeys and set up
644 * the strategy field correctly for them.
646 * Lastly, for ordinary scankeys (not IS NULL/NOT NULL), we check for a
647 * NULL comparison value. Since all btree operators are assumed strict,
648 * a NULL means that the qual cannot be satisfied. We return true if the
649 * comparison value isn't NULL, or false if the scan should be abandoned.
651 * This function is applied to the *input* scankey structure; therefore
652 * on a rescan we will be looking at already-processed scankeys. Hence
653 * we have to be careful not to re-commute the strategy if we already did it.
654 * It's a bit ugly to modify the caller's copy of the scankey but in practice
655 * there shouldn't be any problem, since the index's indoptions are certainly
656 * not going to change while the scankey survives.
666 * We treat all btree operators as strict (even if they're not so marked
667 * in pg_proc). This means that it is impossible for an operator condition
668 * with a NULL comparison constant to succeed, and we can reject it right
671 * However, we now also support "x IS NULL" clauses as search conditions,
672 * so in that case keep going. The planner has not filled in any
673 * particular strategy in this case, so set it to BTEqualStrategyNumber
674 * --- we can treat IS NULL as an equality operator for purposes of search
677 * Likewise, "x IS NOT NULL" is supported. We treat that as either "less
678 * than NULL" in a NULLS LAST index, or "greater than NULL" in a NULLS
681 * Note: someday we might have to fill in sk_collation from the index
682 * column's collation. At the moment this is a non-issue because we'll
683 * never actually call the comparison operator on a NULL.
687 /* SK_ISNULL shouldn't be set in a row header scankey */
690 /* Set indoption flags in scankey (might be done already) */
693 /* Set correct strategy for IS NULL or NOT NULL search */
711 /* regular qual, so it cannot be satisfied */
715 /* Needn't do the rest */
719 /* Adjust strategy for DESC, if we didn't already */
724 /* If it's a row header, fix row member flags and strategies similarly */
731 /* First row member is NULL, so RowCompare is unsatisfiable */
753 * Mark a scankey as "required to continue the scan".
755 * Depending on the operator type, the key may be required for both scan
756 * directions or just one. Also, if the key is a row comparison header,
757 * we have to mark the appropriate subsidiary ScanKeys as required. In such
758 * cases, the first subsidiary key is required, but subsequent ones are
759 * required only as long as they correspond to successive index columns and
760 * match the leading column as to sort direction. Otherwise the row
761 * comparison ordering is different from the index ordering and so we can't
762 * stop the scan on the basis of those lower-order columns.
764 * Note: when we set required-key flag bits in a subsidiary scankey, we are
765 * scribbling on a data structure belonging to the index AM's caller, not on
766 * our private copy. This should be OK because the marking will not change
767 * from scan to scan within a query, and so we'd just re-mark the same way
768 * anyway on a rescan. Something to keep an eye on though.
789 elog(
ERROR,
"unrecognized StrategyNumber: %d",
791 addflags = 0;
/* keep compiler quiet */
802 /* First subkey should be same column/operator as the header */
810 break;
/* non-adjacent key, so not required */
812 break;
/* wrong direction, so not required */
823 * Compare two scankey values using a specified operator.
825 * The test we want to perform is logically "leftarg op rightarg", where
826 * leftarg and rightarg are the sk_argument values in those ScanKeys, and
827 * the comparison operator is the one in the op ScanKey. However, in
828 * cross-data-type situations we may need to look up the correct operator in
829 * the index's opfamily: it is the one having amopstrategy = op->sk_strategy
830 * and amoplefttype/amoprighttype equal to the two argument datatypes.
832 * If the opfamily doesn't supply a complete set of cross-type operators we
833 * may not be able to make the comparison. If we can make the comparison
834 * we store the operator result in *result and return true. We return false
835 * if the comparison could not be made.
837 * If either leftarg or rightarg are an array, we'll apply array-specific
838 * rules to determine which array elements are redundant on behalf of caller.
839 * It is up to our caller to save whichever of the two scan keys is the array,
840 * and discard the non-array scan key (the non-array scan key is guaranteed to
841 * be redundant with any complete opfamily). Caller isn't expected to call
842 * here with a pair of array scan keys provided we're dealing with a complete
843 * opfamily (_bt_preprocess_array_keys will merge array keys together to make
846 * Note: we'll also shrink caller's array as needed to eliminate redundant
847 * array elements. One reason why caller should prefer to discard non-array
848 * scan keys is so that we'll have the opportunity to shrink the array
849 * multiple times, in multiple calls (for each of several other scan keys on
850 * the same index attribute).
852 * Note: op always points at the same ScanKey as either leftarg or rightarg.
853 * Since we don't scribble on the scankeys themselves, this aliasing should
856 * Note: this routine needs to be insensitive to any DESC option applied
857 * to the index column. For example, "x < 4" is a tighter constraint than
858 * "x < 5" regardless of which way the index is sorted.
877 * First, deal with cases where one or both args are NULL. This should
878 * only happen when the scankeys represent IS NULL/NOT NULL conditions.
885 /* Handle skip array comparison with IS NOT NULL scan key */
888 /* Shouldn't generate skip array in presence of IS NULL key */
892 /* Skip array will have no NULL element/IS NULL scan key */
896 /* IS NOT NULL key (could be leftarg or rightarg) now redundant */
917 * We treat NULL as either greater than or less than all other values.
918 * Since true > false, the tests below work correctly for NULLS LAST
919 * logic. If the index is NULLS FIRST, we need to flip the strategy.
928 *result = (leftnull < rightnull);
931 *result = (leftnull <= rightnull);
934 *result = (leftnull == rightnull);
937 *result = (leftnull >= rightnull);
940 *result = (leftnull > rightnull);
943 elog(
ERROR,
"unrecognized StrategyNumber: %d", (
int) strat);
944 *result =
false;
/* keep compiler quiet */
951 * We don't yet know how to determine redundancy when it involves a row
952 * compare key (barring simple cases involving IS NULL/IS NOT NULL)
961 * If either leftarg or rightarg are equality-type array scankeys, we need
962 * specialized handling (since by now we know that IS NULL wasn't used)
975 * _bt_preprocess_array_keys is responsible for merging together array
976 * scan keys, and will do so whenever the opfamily has the required
977 * cross-type support. If it failed to do that, we handle it just
978 * like the case where we can't make the comparison ourselves.
980 if (leftarray && rightarray)
982 /* Can't make the comparison */
983 *result =
false;
/* suppress compiler warnings */
989 * Otherwise we need to determine if either one of leftarg or rightarg
990 * uses an array, then pass this through to a dedicated helper
995 orderproc, array, result);
998 orderproc, array, result);
1004 * The opfamily we need to worry about is identified by the index column.
1011 * Determine the actual datatypes of the ScanKey arguments. We have to
1012 * support the convention that sk_subtype == InvalidOid means the opclass
1013 * input type; this is a hack to simplify life for ScanKeyInit().
1017 lefttype = opcintype;
1020 righttype = opcintype;
1026 * If leftarg and rightarg match the types expected for the "op" scankey,
1027 * we can use its already-looked-up comparison function.
1029 if (lefttype == opcintype && righttype == optype)
1039 * Otherwise, we need to go to the syscache to find the appropriate
1040 * operator. (This cannot result in infinite recursion, since no
1041 * indexscan initiated by syscache lookup will use cross-data-type
1044 * If the sk_strategy was flipped by _bt_fix_scankey_strategy, we have to
1045 * un-flip it to get the correct opfamily member.
1069 /* Can't make the comparison */
1070 *result =
false;
/* suppress compiler warnings */
1075 * Compare an array scan key to a scalar scan key, eliminating contradictory
1076 * array elements such that the scalar scan key becomes redundant.
1078 * If the opfamily is incomplete we may not be able to determine which
1079 * elements are contradictory. When we return true we'll have validly set
1080 * *qual_ok, guaranteeing that at least the scalar scan key can be considered
1081 * redundant. We return false if the comparison could not be made (caller
1082 * must keep both scan keys when this happens).
1084 * Note: it's up to caller to deal with IS [NOT] NULL scan keys, as well as
1085 * row comparison scan keys. We only deal with scalar scan keys.
1096 /* don't expect to have to deal with NULLs/row comparison scan keys */
1102 * Just call the appropriate helper function based on whether it's a SAOP
1103 * array or a skip array. Both helpers will set *qual_ok in passing.
1113 * Preprocessing of SAOP array scan key, used to determine which array
1114 * elements are eliminated as contradictory by a non-array scalar key.
1116 * _bt_compare_array_scankey_args helper function.
1118 * Array elements can be eliminated as contradictory when excluded by some
1119 * other operator on the same attribute. For example, with an index scan qual
1120 * "WHERE a IN (1, 2, 3) AND a < 2", all array elements except the value "1"
1121 * are eliminated, and the < scan key is eliminated as redundant. Cases where
1122 * every array element is eliminated by a redundant scalar scan key have an
1123 * unsatisfiable qual, which we handle by setting *qual_ok=false for caller.
1142 * _bt_binsrch_array_skey searches an array for the entry best matching a
1143 * datum of opclass input type for the index's attribute (on-disk type).
1144 * We can reuse the array's ORDER proc whenever the non-array scan key's
1145 * type is a match for the corresponding attribute's input opclass type.
1146 * Otherwise, we have to do another ORDER proc lookup so that our call to
1147 * _bt_binsrch_array_skey applies the correct comparator.
1149 * Note: we have to support the convention that sk_subtype == InvalidOid
1150 * means the opclass input type; this is a hack to simplify life for
1156 Oid arraysk_elemtype;
1159 * Need an ORDER proc lookup to detect redundancy/contradictoriness
1160 * with this pair of scankeys.
1162 * Scalar scan key's argument will be passed to _bt_compare_array_skey
1163 * as its tupdatum/lefthand argument (rhs arg is for array elements).
1173 /* Can't make the comparison */
1174 *qual_ok =
false;
/* suppress compiler warnings */
1178 /* We have all we need to determine redundancy/contradictoriness */
1179 orderprocp = &crosstypeproc;
1186 arraysk, &cmpresult);
1191 cmpexact = 1;
/* exclude exact match, if any */
1194 if (cmpresult >= cmpexact)
1196 /* Resize, keeping elements from the start of the array */
1197 new_nelems = matchelem;
1202 /* qual is unsatisfiable */
1207 /* Shift matching element to the start of the array, resize */
1213 cmpexact = 1;
/* include exact match, if any */
1216 if (cmpresult >= cmpexact)
1218 /* Shift matching elements to the start of the array, resize */
1219 new_nelems = array->
num_elems - matchelem;
1221 sizeof(
Datum) * new_nelems);
1224 elog(
ERROR,
"unrecognized StrategyNumber: %d",
1230 Assert(new_nelems <= array->num_elems);
1233 *qual_ok = new_nelems > 0;
1239 * Preprocessing of skip array scan key, used to determine redundancy against
1240 * a non-array scalar scan key (must be an inequality).
1242 * _bt_compare_array_scankey_args helper function.
1244 * Skip arrays work by procedurally generating their elements as needed, so we
1245 * just store the inequality as the skip array's low_compare or high_compare
1246 * (except when there's already a more restrictive low_compare/high_compare).
1247 * The array's final elements are the range of values that still satisfy the
1248 * array's final low_compare and high_compare.
1259 * Array's index attribute will be constrained by a strict operator/key.
1260 * Array must not "contain a NULL element" (i.e. the scan must not apply
1261 * "IS NULL" qual when it reaches the end of the index that stores NULLs).
1267 * Consider if we should treat caller's scalar scan key as the skip
1268 * array's high_compare or low_compare.
1270 * In general the current array element must either be a copy of a value
1271 * taken from an index tuple, or a derivative value generated by opclass's
1272 * skip support function. That way the scan can always safely assume that
1273 * it's okay to use the only-input-opclass-type proc from so->orderProcs[]
1274 * (they can be cross-type with SAOP arrays, but never with skip arrays).
1276 * This approach is enabled by MINVAL/MAXVAL sentinel key markings, which
1277 * can be thought of as representing either the lowest or highest matching
1278 * array element (excluding the NULL element, where applicable, though as
1279 * just discussed it isn't applicable to this range skip array anyway).
1280 * Array keys marked MINVAL/MAXVAL never have a valid datum in their
1281 * sk_argument field. The scan directly applies the array's low_compare
1282 * key when it encounters MINVAL in the array key proper (just as it
1283 * applies high_compare when it sees MAXVAL set in the array key proper).
1284 * The scan must never use the array's so->orderProcs[] proc against
1285 * low_compare's/high_compare's sk_argument, either (so->orderProcs[] is
1286 * only intended to be used with rhs datums from the array proper/index).
1294 /* replace existing high_compare with caller's key? */
1298 return false;
/* can't determine more restrictive key */
1301 return true;
/* no, just discard caller's key */
1303 /* yes, replace existing high_compare with caller's key */
1306 /* caller's key becomes skip array's high_compare */
1313 /* replace existing low_compare with caller's key? */
1317 return false;
/* can't determine more restrictive key */
1320 return true;
/* no, just discard caller's key */
1322 /* yes, replace existing low_compare with caller's key */
1325 /* caller's key becomes skip array's low_compare */
1330 elog(
ERROR,
"unrecognized StrategyNumber: %d",
1339 * Applies the opfamily's skip support routine to convert the skip array's >
1340 * low_compare key (if any) into a >= key, and to convert its < high_compare
1341 * key (if any) into a <= key. Decrements the high_compare key's sk_argument,
1342 * and/or increments the low_compare key's sk_argument (also adjusts their
1343 * operator strategies, while changing the operator as appropriate).
1345 * This optional optimization reduces the number of descents required within
1346 * _bt_first. Whenever _bt_first is called with a skip array whose current
1347 * array element is the sentinel value MINVAL, using a transformed >= key
1348 * instead of using the original > key makes it safe to include lower-order
1349 * scan keys in the insertion scan key (there must be lower-order scan keys
1350 * after the skip array). We will avoid an extra _bt_first to find the first
1351 * value in the index > sk_argument -- at least when the first real matching
1352 * value in the index happens to be an exact match for the sk_argument value
1353 * that we produced here by incrementing the original input key's sk_argument.
1354 * (Backwards scans derive the same benefit when they encounter the sentinel
1355 * value MAXVAL, by converting the high_compare key from < to <=.)
1357 * Note: The transformation is only correct when it cannot allow the scan to
1358 * overlook matching tuples, but we don't have enough semantic information to
1359 * safely make sure that can't happen during scans with cross-type operators.
1360 * That's why we'll never apply the transformation in cross-type scenarios.
1361 * For example, if we attempted to convert "sales_ts > '2024年01月01日'::date"
1362 * into "sales_ts >= '2024年01月02日'::date" given a "sales_ts" attribute whose
1363 * input opclass is timestamp_ops, the scan would overlook almost all (or all)
1364 * tuples for sales that fell on '2024年01月01日'.
1366 * Note: We can safely modify array->low_compare/array->high_compare in place
1367 * because they just point to copies of our scan->keyData[] input scan keys
1368 * (namely the copies returned by _bt_preprocess_array_keys to be used as
1369 * input into the standard preprocessing steps in _bt_preprocess_keys).
1370 * Everything will be reset if there's a rescan.
1380 * Called last among all preprocessing steps, when the skip array's final
1381 * low_compare and high_compare have both been chosen
1400 * Convert skip array's > low_compare key into a >= key
1420 * Only perform the transformation when the operator type matches the
1421 * index attribute's input opclass type
1427 /* Decrement, handling underflow by marking the qual unsatisfiable */
1428 new_sk_argument = array->
sksup->
decrement(rel, orig_sk_argument, &uflow);
1438 * Look up <= operator (might fail), accounting for the fact that a
1439 * high_compare on a DESC column already had its strategy commuted
1450 /* Transform < high_compare key into <= key */
1458 * Convert skip array's < low_compare key into a <= key
1478 * Only perform the transformation when the operator type matches the
1479 * index attribute's input opclass type
1485 /* Increment, handling overflow by marking the qual unsatisfiable */
1486 new_sk_argument = array->
sksup->
increment(rel, orig_sk_argument, &oflow);
1496 * Look up >= operator (might fail), accounting for the fact that a
1497 * low_compare on a DESC column already had its strategy commuted
1508 /* Transform > low_compare key into >= key */
1516 * _bt_unmark_keys() -- make superfluous required keys nonrequired after all
1518 * When _bt_preprocess_keys fails to eliminate one or more redundant keys, it
1519 * calls here to make sure that no index attribute has more than one > or >=
1520 * key marked required, and no more than one required < or <= key. Attributes
1521 * with = keys will always get one = key as their required key. All other
1522 * keys that were initially marked required get "unmarked" here. That way,
1523 * _bt_first and _bt_checkkeys will reliably agree on which keys to use to
1524 * start and/or to end the scan.
1526 * We also relocate keys that become/started out nonrequired to the end of
1527 * so->keyData[]. That way, _bt_first and _bt_checkkeys cannot fail to reach
1528 * a required key due to some earlier nonrequired key getting in the way.
1530 * Only call here when _bt_compare_scankey_args returned false at least once
1531 * (otherwise, calling here will just waste cycles).
1546 *unmarkOrderProcs = NULL;
1552 * Do an initial pass over so->keyData[] that determines which keys to
1553 * keep as required. We expect so->keyData[] to still be in attribute
1554 * order when we're called (though we don't expect any particular order
1555 * among each attribute's keys).
1557 * When both equality and inequality keys remain on a single attribute, we
1558 * *must* make sure that exactly one of the equalities remains required.
1559 * Any requiredness markings that we might leave on later keys/attributes
1560 * are predicated on there being required = keys on all prior columns.
1565 /* Set things up for first key's attribute */
1568 haveReqEquals =
false;
1569 haveReqForward =
false;
1570 haveReqBackward =
false;
1577 /* Reset for next attribute */
1581 haveReqEquals =
false;
1582 haveReqForward =
false;
1583 haveReqBackward =
false;
1586 /* Equalities get priority over inequalities */
1590 * We already found the first "=" key for this attribute. We've
1591 * already decided that all its other keys will be unmarked.
1594 unmarkikey[
i] =
true;
1602 * Found the first "=" key for attno. All other attno keys will
1607 haveReqEquals =
true;
1608 for (
int j = firsti;
j <
i;
j++)
1610 /* Unmark any prior inequality keys on attno after all */
1613 unmarkikey[
j] =
true;
1620 /* Deal with inequalities next */
1623 haveReqForward =
true;
1628 haveReqBackward =
true;
1633 * We have either a redundant inequality key that will be unmarked, or
1634 * we have a key that wasn't marked required in the first place
1636 unmarkikey[
i] =
true;
1640 /* Should only be called when _bt_compare_scankey_args reported failure */
1644 * Next, allocate temp arrays: one for required keys that'll remain
1645 * required, the other for all remaining keys
1658 * Next, copy the contents of so->keyData[] into the appropriate temp
1661 * Scans with = array keys need us to maintain invariants around the order
1662 * of so->orderProcs[] and so->arrayKeys[] relative to so->keyData[]. See
1663 * _bt_preprocess_array_keys_final for a full explanation.
1673 * Key gets to keep its original requiredness markings.
1675 * Key will stay in its original position, unless we're going to
1676 * unmark an earlier key (in which case this key gets moved back).
1678 memcpy(keepKeys + nkept, origkey,
sizeof(
ScanKeyData));
1682 keyDataMap[
i] = nkept;
1683 memcpy(keepOrderProcs + nkept, &so->
orderProcs[
i],
1692 * Key will be unmarked as needed, and moved to the end of the array,
1693 * next to other keys that will become (or always were) nonrequired
1695 unmark = unmarkKeys + nunmarked;
1701 memcpy(&unmarkOrderProcs[nunmarked], &so->
orderProcs[
i],
1706 * Preprocessing only generates skip arrays when it knows that they'll
1707 * be the only required = key on the attr. We'll never unmark them.
1712 * Also shouldn't have to unmark an IS NULL or an IS NOT NULL key.
1713 * They aren't cross-type, so an incomplete opfamily can't matter.
1718 /* Clear requiredness flags on redundant key (and on any subkeys) */
1738 /* Copy both temp arrays back into so->keyData[] to reorder */
1740 Assert(nunmarked == nunmark);
1744 /* Done with temp arrays */
1750 * Now copy so->orderProcs[] temp entries needed by scans with = array
1751 * keys back (just like with the so->keyData[] temp arrays)
1756 memcpy(so->
orderProcs + nkept, unmarkOrderProcs,
1759 /* Also fix-up array->scan_key references */
1760 for (
int arridx = 0; arridx < so->
numArrayKeys; arridx++)
1768 * Sort so->arrayKeys[] based on its new BTArrayKeyInfo.scan_key
1769 * offsets, so that its order matches so->keyData[] order as expected
1774 /* Done with temp arrays */
1775 pfree(unmarkOrderProcs);
1776 pfree(keepOrderProcs);
1781 * qsort comparator for reordering so->arrayKeys[] BTArrayKeyInfo entries
1793 * _bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys
1795 * If there are any SK_SEARCHARRAY scan keys, deconstruct the array(s) and
1796 * set up BTArrayKeyInfo info for each one that is an equality-type key.
1797 * Returns modified scan keys as input for further, standard preprocessing.
1799 * Currently we perform two kinds of preprocessing to deal with redundancies.
1800 * For inequality array keys, it's sufficient to find the extreme element
1801 * value and replace the whole array with that scalar value. This eliminates
1802 * all but one array element as redundant. Similarly, we are capable of
1803 * "merging together" multiple equality array keys (from two or more input
1804 * scan keys) into a single output scan key containing only the intersecting
1805 * array elements. This can eliminate many redundant array elements, as well
1806 * as eliminating whole array scan keys as redundant. It can also allow us to
1807 * detect contradictory quals.
1809 * Caller must pass *new_numberOfKeys to give us a way to change the number of
1810 * scan keys that caller treats as input to standard preprocessing steps. The
1811 * returned array is smaller than scan->keyData[] when we could eliminate a
1812 * redundant array scan key (redundant with another array scan key). It is
1813 * convenient for _bt_preprocess_keys caller to have to deal with no more than
1814 * one equality strategy array scan key per index attribute. We'll always be
1815 * able to set things up that way when complete opfamilies are used.
1817 * We're also responsible for generating skip arrays (and their associated
1818 * scan keys) here. This enables skip scan. We do this for index attributes
1819 * that initially lacked an equality condition within scan->keyData[], iff
1820 * doing so allows a later scan key (that was passed to us in scan->keyData[])
1821 * to be marked required by our _bt_preprocess_keys caller.
1823 * We set the scan key references from the scan's BTArrayKeyInfo info array to
1824 * offsets into the temp modified input array returned to caller. Scans that
1825 * have array keys should call _bt_preprocess_array_keys_final when standard
1826 * preprocessing steps are complete. This will convert the scan key offset
1827 * references into references to the scan's so->keyData[] output scan keys.
1829 * Note: the reason we need to return a temp scan key array, rather than just
1830 * modifying scan->keyData[], is that callers are permitted to call btrescan
1831 * without supplying a new set of scankey data. Certain other preprocessing
1832 * routines (e.g., _bt_fix_scankey_strategy) _can_ modify scan->keyData[], but
1833 * we can't make that work here because our modifications are non-idempotent.
1850 ScanKey arrayKeyData;
/* modified copy of scan->keyData */
1853 * Check the number of input array keys within scan->keyData[] input keys
1854 * (also checks if we should add extra skip arrays based on input keys)
1857 so->
skipScan = (numSkipArrayKeys > 0);
1859 /* Quit if nothing to do. */
1860 if (numArrayKeys == 0)
1864 * Estimated final size of arrayKeyData[] array we'll return to our caller
1865 * is the size of the original scan->keyData[] input array, plus space for
1866 * any additional skip array scan keys we'll need to generate below
1868 numArrayKeyData = scan->
numberOfKeys + numSkipArrayKeys;
1871 * Make a scan-lifespan context to hold array-associated data, or reset it
1872 * if we already have one from a previous rescan cycle.
1876 "BTree array context",
1883 /* Create output scan keys in the workspace context */
1886 /* Allocate space for per-array data in the workspace context */
1889 /* Allocate space for ORDER procs used to help _bt_checkkeys */
1893 numArrayKeyData = 0;
1894 for (
int input_ikey = 0; input_ikey < scan->
numberOfKeys; input_ikey++)
1911 /* set up next output scan key */
1912 cur = &arrayKeyData[numArrayKeyData];
1914 /* Backfill skip arrays for attrs < or <= input key's attr? */
1915 while (numSkipArrayKeys && attno_skip <= inkey->sk_attno)
1917 Oid opfamily = rel->rd_opfamily[attno_skip - 1];
1918 Oid opcintype = rel->rd_opcintype[attno_skip - 1];
1919 Oid collation = rel->rd_indcollation[attno_skip - 1];
1920 Oid eq_op = skip_eq_ops[attno_skip - 1];
1927 * Attribute already has an = input key, so don't output a
1928 * skip array for attno_skip. Just copy attribute's = input
1929 * key into arrayKeyData[] once outside this inner loop.
1931 * Note: When we get here there must be a later attribute that
1932 * lacks an equality input key, and still needs a skip array
1933 * (if there wasn't then numSkipArrayKeys would be 0 by now).
1936 /* inkey can't be last input key to be marked required: */
1937 Assert(input_ikey < scan->numberOfKeys - 1);
1939 /* Could be a redundant input scan key, so can't do this: */
1950 elog(
ERROR,
"missing oprcode for skipping equals operator %u", eq_op);
1954 attno_skip,
/* skipped att number */
1957 collation,
/* index column's collation */
1958 cmp_proc,
/* equality operator's proc */
1959 (
Datum) 0);
/* constant */
1961 /* Initialize generic BTArrayKeyInfo fields */
1965 /* Initialize skip array specific BTArrayKeyInfo fields */
1967 reverse = (indoption[attno_skip - 1] & INDOPTION_DESC) != 0;
1977 * We'll need a 3-way ORDER proc. Set that up now.
1983 numArrayKeyData++;
/* keep this scan key/array */
1985 /* set up next output scan key */
1986 cur = &arrayKeyData[numArrayKeyData];
1988 /* remember having output this skip array and scan key */
1994 * Provisionally copy scan key into arrayKeyData[] array we'll return
1995 * to _bt_preprocess_keys caller
2001 numArrayKeyData++;
/* keep this non-array scan key */
2006 * Process SAOP array scan key
2010 /* If array is null as a whole, the scan qual is unsatisfiable */
2018 * Deconstruct the array into elements
2021 /* We could cache this data, but not clear it's worth it */
2023 &elmlen, &elmbyval, &elmalign);
2026 elmlen, elmbyval, elmalign,
2027 &elem_values, &elem_nulls, &num_elems);
2030 * Compress out any null elements. We can ignore them since we assume
2031 * all btree operators are strict.
2034 for (
int j = 0;
j < num_elems;
j++)
2037 elem_values[num_nonnulls++] = elem_values[
j];
2040 /* We could pfree(elem_nulls) now, but not worth the cycles */
2042 /* If there's no non-nulls, the scan qual is unsatisfiable */
2043 if (num_nonnulls == 0)
2050 * Determine the nominal datatype of the array elements. We have to
2051 * support the convention that sk_subtype == InvalidOid means the
2052 * opclass input type; this is a hack to simplify life for
2055 elemtype =
cur->sk_subtype;
2057 elemtype = rel->rd_opcintype[
cur->sk_attno - 1];
2060 * If the comparison operator is not equality, then the array qual
2061 * degenerates to a simple comparison against the smallest or largest
2062 * non-null array element, as appropriate.
2064 switch (
cur->sk_strategy)
2071 elem_values, num_nonnulls);
2072 numArrayKeyData++;
/* keep this transformed scan key */
2075 /* proceed with rest of loop */
2082 elem_values, num_nonnulls);
2083 numArrayKeyData++;
/* keep this transformed scan key */
2086 elog(
ERROR,
"unrecognized StrategyNumber: %d",
2087 (
int)
cur->sk_strategy);
2092 * We'll need a 3-way ORDER proc to perform binary searches for the
2093 * next matching array element. Set that up now.
2095 * Array scan keys with cross-type equality operators will require a
2096 * separate same-type ORDER proc for sorting their array. Otherwise,
2097 * sortproc just points to the same proc used during binary searches.
2100 &so->
orderProcs[numArrayKeyData], &sortprocp);
2103 * Sort the non-null elements and eliminate any duplicates. We must
2104 * sort in the same ordering used by the index column, so that the
2105 * arrays can be advanced in lockstep with the scan's progress through
2106 * the index's key space.
2108 reverse = (indoption[
cur->sk_attno - 1] & INDOPTION_DESC) != 0;
2110 elem_values, num_nonnulls);
2112 if (origarrayatt ==
cur->sk_attno)
2117 * This array scan key is redundant with a previous equality
2118 * operator array scan key. Merge the two arrays together to
2119 * eliminate contradictory non-intersecting elements (or try to).
2121 * We merge this next array back into attribute's original array.
2127 origelemtype, elemtype,
2129 elem_values, num_elems))
2131 /* Successfully eliminated this array */
2135 * If no intersecting elements remain in the original array,
2136 * the scan qual is unsatisfiable
2144 /* Throw away this scan key/array */
2149 * Unable to merge this array with previous array due to a lack of
2150 * suitable cross-type opfamily support. Will need to keep both
2157 * This array is the first for current index attribute.
2159 * If it turns out to not be the last array (that is, if the next
2160 * array is redundantly applied to this same index attribute),
2161 * we'll then treat this array as the attribute's "original" array
2164 origarrayatt =
cur->sk_attno;
2165 origarraykey = numArrayKeys;
2166 origelemtype = elemtype;
2169 /* Initialize generic BTArrayKeyInfo fields */
2173 /* Initialize SAOP array specific BTArrayKeyInfo fields */
2178 numArrayKeyData++;
/* keep this scan key/array */
2183 /* Set final number of equality-type array keys */
2185 /* Set number of scan keys in arrayKeyData[] */
2186 *new_numberOfKeys = numArrayKeyData;
2190 return arrayKeyData;
2194 * _bt_preprocess_array_keys_final() -- fix up array scan key references
2196 * When _bt_preprocess_array_keys performed initial array preprocessing, it
2197 * set each array's array->scan_key to its scankey's arrayKeyData[] offset.
2198 * This function handles translation of the scan key references from the
2199 * BTArrayKeyInfo info array, from input scan key references (to the keys in
2200 * arrayKeyData[]), into output references (to the keys in so->keyData[]).
2201 * Caller's keyDataMap[] array tells us how to perform this remapping.
2203 * Also finalizes so->orderProcs[] for the scan. Arrays already have an ORDER
2204 * proc, which might need to be repositioned to its so->keyData[]-wise offset
2205 * (very much like the remapping that we apply to array->scan_key references).
2206 * Non-array equality strategy scan keys (that survived preprocessing) don't
2207 * yet have an so->orderProcs[] entry, so we set one for them here.
2209 * Also converts single-element array scan keys into equivalent non-array
2210 * equality scan keys, which decrements so->numArrayKeys. It's possible that
2211 * this will leave this new btrescan without any arrays at all. This isn't
2212 * necessary for correctness; it's just an optimization. Non-array equality
2213 * scan keys are slightly faster than equivalent array scan keys at runtime.
2226 * Nothing for us to do when _bt_preprocess_array_keys only had to deal
2227 * with array inequalities
2232 for (
int output_ikey = 0; output_ikey < so->
numberOfKeys; output_ikey++)
2243 input_ikey = keyDataMap[output_ikey];
2245 Assert(last_equal_output_ikey < output_ikey);
2246 Assert(last_equal_output_ikey < input_ikey);
2247 last_equal_output_ikey = output_ikey;
2250 * We're lazy about looking up ORDER procs for non-array keys, since
2251 * not all input keys become output keys. Take care of it now.
2257 /* No need for an ORDER proc given an IS NULL scan key */
2262 * A non-required scan key doesn't need an ORDER proc, either
2263 * (unless it's associated with an array, which this one isn't)
2270 elemtype = rel->rd_opcintype[outkey->
sk_attno - 1];
2278 * Reorder existing array scan key so->orderProcs[] entries.
2280 * Doing this in-place is safe because preprocessing is required to
2281 * output all equality strategy scan keys in original input order
2282 * (among each group of entries against the same index attribute).
2283 * This is also the order that the arrays themselves appear in.
2287 /* Fix-up array->scan_key references for arrays */
2293 * All skip arrays must be marked required, and final column can
2294 * never have a skip array
2308 * Transform array scan keys that have exactly 1 element
2309 * remaining (following all prior preprocessing) into
2310 * equivalent non-array scan keys.
2314 outkey->
sk_flags &= ~SK_SEARCHARRAY;
2318 /* If we're out of array keys, we can quit right away */
2322 /* Shift other arrays forward */
2323 memmove(array, array + 1,
2328 * Don't increment arrayidx (there was an entry that was
2329 * just shifted forward to the offset at arrayidx, which
2330 * will still need to be matched)
2336 * Any skip array low_compare and high_compare scan keys
2337 * are now final. Transform the array's > low_compare key
2338 * into a >= key (and < high_compare keys into a <= key).
2344 /* Match found, so done with this array */
2356 * Parallel index scans require space in shared memory to store the
2357 * current array elements (for arrays kept by preprocessing) to schedule
2358 * the next primitive index scan. The underlying structure is protected
2359 * using an LWLock, so defensively limit its size. In practice this can
2360 * only affect parallel scans that use an incomplete opfamily.
2364 (
errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2365 errmsg_internal(
"number of array scan keys left by preprocessing (%d) exceeds the maximum allowed by parallel btree index scans (%d)",
2370 * _bt_num_array_keys() -- determine # of BTArrayKeyInfo entries
2372 * _bt_preprocess_array_keys helper function. Returns the estimated size of
2373 * the scan's BTArrayKeyInfo array, which is guaranteed to be large enough to
2374 * fit every so->arrayKeys[] entry.
2376 * Also sets *numSkipArrayKeys_out to the number of skip arrays caller must
2377 * add to the scan keys it'll output. Caller must add this many skip arrays:
2378 * one array for each of the most significant attributes that lack a = input
2379 * key (IS NULL keys count as = input keys here). The specific attributes
2380 * that need skip arrays are indicated by initializing skip_eq_ops_out[] arg
2381 * 0-based attribute offset to a valid = op strategy Oid. We'll only ever set
2382 * skip_eq_ops_out[] entries to InvalidOid for attributes that already have an
2383 * equality key in scan->keyData[] input keys -- and only when there's some
2384 * later "attribute gap" for us to "fill-in" with a skip array.
2386 * We're optimistic about skipping working out: we always add exactly the skip
2387 * arrays needed to maximize the number of input scan keys that can ultimately
2388 * be marked as required to continue the scan (but no more). Given a
2389 * multi-column index on (a, b, c, d), we add skip arrays as follows:
2391 * Input keys Output keys (after all preprocessing)
2392 * ---------- -------------------------------------
2393 * a = 1 a = 1 (no skip arrays)
2394 * b = 42 skip a AND b = 42
2395 * a = 1 AND b = 42 a = 1 AND b = 42 (no skip arrays)
2396 * a >= 1 AND b = 42 range skip a AND b = 42
2397 * a = 1 AND b > 42 a = 1 AND b > 42 (no skip arrays)
2398 * a >= 1 AND a <= 3 AND b = 42 range skip a AND b = 42
2399 * a = 1 AND c <= 27 a = 1 AND skip b AND c <= 27
2400 * a = 1 AND d >= 1 a = 1 AND skip b AND skip c AND d >= 1
2401 * a = 1 AND b >= 42 AND d > 1 a = 1 AND range skip b AND skip c AND d > 1
2405 int *numSkipArrayKeys_out)
2410 bool attno_has_equal =
false,
2411 attno_has_rowcompare =
false;
2412 int numSAOPArrayKeys,
2414 prev_numSkipArrayKeys;
2418 /* Initial pass over input scan keys counts the number of SAOP arrays */
2419 numSAOPArrayKeys = 0;
2420 *numSkipArrayKeys_out = prev_numSkipArrayKeys = numSkipArrayKeys = 0;
2429#ifdef DEBUG_DISABLE_SKIP_SCAN
2430 /* don't attempt to add skip arrays */
2431 return numSAOPArrayKeys;
2434 for (
int i = 0;;
i++)
2439 * Backfill skip arrays for any wholly omitted attributes prior to
2442 while (attno_skip < attno_inkey)
2447 /* Look up input opclass's equality operator (might fail) */
2448 skip_eq_ops_out[attno_skip - 1] =
2451 if (!
OidIsValid(skip_eq_ops_out[attno_skip - 1]))
2454 * Cannot generate a skip array for this or later attributes
2455 * (input opclass lacks an equality strategy operator)
2457 *numSkipArrayKeys_out = prev_numSkipArrayKeys;
2458 return numSAOPArrayKeys + prev_numSkipArrayKeys;
2461 /* plan on adding a backfill skip array for this attribute */
2466 prev_numSkipArrayKeys = numSkipArrayKeys;
2469 * Stop once past the final input scan key. We deliberately never add
2470 * a skip array for the last input scan key's attribute -- even when
2471 * there are only inequality keys on that attribute.
2477 * Later preprocessing steps cannot merge a RowCompare into a skip
2478 * array, so stop adding skip arrays once we see one. (Note that we
2479 * can backfill skip arrays before a RowCompare, which will allow keys
2480 * up to and including the RowCompare to be marked required.)
2482 * Skip arrays work by maintaining a current array element value,
2483 * which anchors lower-order keys via an implied equality constraint.
2484 * This is incompatible with the current nbtree row comparison design,
2485 * which compares all columns together, as an indivisible group.
2486 * Alternative designs that can be used alongside skip arrays are
2487 * possible, but it's not clear that they're really worth pursuing.
2489 * A RowCompare qual "(a, b, c) > (10, 'foo', 42)" is equivalent to
2490 * "(a=10 AND b='foo' AND c>42) OR (a=10 AND b>'foo') OR (a>10)".
2491 * Decomposing this RowCompare into these 3 disjuncts allows each
2492 * disjunct to be executed as a separate "single value" index scan.
2493 * That'll give all 3 scans the ability to add skip arrays in the
2494 * usual way (when there are any scalar keys after the RowCompare).
2495 * Under this scheme, a qual "(a, b, c) > (10, 'foo', 42) AND d = 99"
2496 * performs 3 separate scans, each of which can mark keys up to and
2497 * including its "d = 99" key as required to continue the scan.
2499 if (attno_has_rowcompare)
2503 * Now consider next attno_inkey (or keep going if this is an
2504 * additional scan key against the same attribute)
2506 if (attno_inkey < inkey->sk_attno)
2509 * Now add skip array for previous scan key's attribute, though
2510 * only if the attribute has no equality strategy scan keys
2512 if (attno_has_equal)
2514 /* Attributes with an = key must have InvalidOid eq_op set */
2515 skip_eq_ops_out[attno_skip - 1] =
InvalidOid;
2522 /* Look up input opclass's equality operator (might fail) */
2523 skip_eq_ops_out[attno_skip - 1] =
2527 if (!
OidIsValid(skip_eq_ops_out[attno_skip - 1]))
2530 * Input opclass lacks an equality strategy operator, so
2531 * don't generate a skip array that definitely won't work
2536 /* plan on adding a backfill skip array for this attribute */
2540 /* Set things up for this new attribute */
2543 attno_has_equal =
false;
2547 * Track if this attribute's scan keys include any equality strategy
2548 * scan keys (IS NULL keys count as equality keys here). Also track
2549 * if it has any RowCompare keys.
2553 attno_has_equal =
true;
2555 attno_has_rowcompare =
true;
2558 *numSkipArrayKeys_out = numSkipArrayKeys;
2559 return numSAOPArrayKeys + numSkipArrayKeys;
2563 * _bt_find_extreme_element() -- get least or greatest array element
2565 * scan and skey identify the index column, whose opfamily determines the
2566 * comparison semantics. strat should be BTLessStrategyNumber to get the
2567 * least element, or BTGreaterStrategyNumber to get the greatest.
2572 Datum *elems,
int nelems)
2582 * Look up the appropriate comparison operator in the opfamily.
2584 * Note: it's possible that this would fail, if the opfamily is
2585 * incomplete, but it seems quite unlikely that an opfamily would omit
2586 * non-cross-type comparison operators for any datatype that it supports
2596 elog(
ERROR,
"missing operator %d(%u,%u) in opfamily %u",
2597 strat, elemtype, elemtype,
2601 elog(
ERROR,
"missing oprcode for operator %u", cmp_op);
2607 for (
i = 1;
i < nelems;
i++)
2620 * _bt_setup_array_cmp() -- Set up array comparison functions
2622 * Sets ORDER proc in caller's orderproc argument, which is used during binary
2623 * searches of arrays during the index scan. Also sets a same-type ORDER proc
2624 * in caller's *sortprocp argument, which is used when sorting the array.
2626 * Preprocessing calls here with all equality strategy scan keys (when scan
2627 * uses equality array keys), including those not associated with any array.
2628 * See _bt_advance_array_keys for an explanation of why it'll need to treat
2629 * simple scalar equality scan keys as degenerate single element arrays.
2631 * Caller should pass an orderproc pointing to space that'll store the ORDER
2632 * proc for the scan, and a *sortprocp pointing to its own separate space.
2633 * When calling here for a non-array scan key, sortprocp arg should be NULL.
2635 * In the common case where we don't need to deal with cross-type operators,
2636 * only one ORDER proc is actually required by caller. We'll set *sortprocp
2637 * to point to the same memory that caller's orderproc continues to point to.
2638 * Otherwise, *sortprocp will continue to point to caller's own space. Either
2639 * way, *sortprocp will point to a same-type ORDER proc (since that's the only
2640 * safe way to sort/deduplicate the array associated with caller's scan key).
2655 * If scankey operator is not a cross-type comparison, we can use the
2656 * cached comparison function; otherwise gotta look it up in the catalogs
2658 if (elemtype == opcintype)
2660 /* Set same-type ORDER procs for caller */
2663 *sortprocp = orderproc;
2669 * Look up the appropriate cross-type comparison function in the opfamily.
2671 * Use the opclass input type as the left hand arg type, and the array
2672 * element type as the right hand arg type (since binary searches use an
2673 * index tuple's attribute value to search for a matching array element).
2675 * Note: it's possible that this would fail, if the opfamily is
2676 * incomplete, but only in cases where it's quite likely that _bt_first
2677 * would fail in just the same way (had we not failed before it could).
2682 elog(
ERROR,
"missing support function %d(%u,%u) for attribute %d of index \"%s\"",
2686 /* Set cross-type ORDER proc for caller */
2689 /* Done if caller doesn't actually have an array they'll need to sort */
2694 * Look up the appropriate same-type comparison function in the opfamily.
2696 * Note: it's possible that this would fail, if the opfamily is
2697 * incomplete, but it seems quite unlikely that an opfamily would omit
2698 * non-cross-type comparison procs for any datatype that it supports at
2704 elog(
ERROR,
"missing support function %d(%u,%u) for attribute %d of index \"%s\"",
2708 /* Set same-type ORDER proc for caller */
2713 * _bt_sort_array_elements() -- sort and de-dup array elements
2715 * The array elements are sorted in-place, and the new number of elements
2716 * after duplicate removal is returned.
2718 * skey identifies the index column whose opfamily determines the comparison
2719 * semantics, and sortproc is a corresponding ORDER proc. If reverse is true,
2720 * we sort in descending order.
2724 Datum *elems,
int nelems)
2729 return nelems;
/* no work to do */
2731 /* Sort the array elements */
2738 /* Now scan the sorted elements and remove duplicates */
2744 * _bt_merge_arrays() -- merge next array's elements into an original array
2746 * Called when preprocessing encounters a pair of array equality scan keys,
2747 * both against the same index attribute (during initial array preprocessing).
2748 * Merging reorganizes caller's original array (the left hand arg) in-place,
2749 * without ever copying elements from one array into the other. (Mixing the
2750 * elements together like this would be wrong, since they don't necessarily
2751 * use the same underlying element type, despite all the other similarities.)
2753 * Both arrays must have already been sorted and deduplicated by calling
2754 * _bt_sort_array_elements. sortproc is the same-type ORDER proc that was
2755 * just used to sort and deduplicate caller's "next" array. We'll usually be
2756 * able to reuse that order PROC to merge the arrays together now. If not,
2757 * then we'll perform a separate ORDER proc lookup.
2759 * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
2760 * may not be able to determine which elements are contradictory. If we have
2761 * the required ORDER proc then we return true (and validly set *nelems_orig),
2762 * guaranteeing that at least the next array can be considered redundant. We
2763 * return false if the required comparisons cannot be made (caller must keep
2764 * both arrays when this happens).
2768 bool reverse,
Oid origelemtype,
Oid nextelemtype,
2769 Datum *elems_orig,
int *nelems_orig,
2770 Datum *elems_next,
int nelems_next)
2775 int nelems_orig_start = *nelems_orig,
2776 nelems_orig_merged = 0;
2783 if (origelemtype != nextelemtype)
2788 * Cross-array-element-type merging is required, so can't just reuse
2789 * sortproc when merging
2795 /* Can't make the required comparisons */
2799 /* We have all we need to determine redundancy/contradictoriness */
2800 mergeproc = &crosstypeproc;
2804 cxt.sortproc = mergeproc;
2806 cxt.reverse = reverse;
2808 for (
int i = 0,
j = 0;
i < nelems_orig_start &&
j < nelems_next;)
2810 Datum *oelem = elems_orig +
i,
2811 *nelem = elems_next +
j;
2816 elems_orig[nelems_orig_merged++] = *oelem;
2826 *nelems_orig = nelems_orig_merged;
2832 * qsort_arg comparator for sorting array elements
#define DatumGetArrayTypeP(X)
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
#define InvalidAttrNumber
#define RegProcedureIsValid(p)
#define INVERT_COMPARE_RESULT(var)
#define PG_USED_FOR_ASSERTS_ONLY
#define OidIsValid(objectId)
int errmsg_internal(const char *fmt,...)
int errcode(int sqlerrcode)
#define ereport(elevel,...)
Datum OidFunctionCall2Coll(Oid functionId, Oid collation, Datum arg1, Datum arg2)
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
void fmgr_info(Oid functionId, FmgrInfo *finfo)
void fmgr_info_cxt(Oid functionId, FmgrInfo *finfo, MemoryContext mcxt)
static int compare(const void *arg1, const void *arg2)
Assert(PointerIsAligned(start, uint64))
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
static int pg_cmp_s32(int32 a, int32 b)
if(TABLE==NULL||TABLE_index==NULL)
void get_typlenbyvalalign(Oid typid, int16 *typlen, bool *typbyval, char *typalign)
Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, int16 procnum)
RegProcedure get_opcode(Oid opno)
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
void * MemoryContextAlloc(MemoryContext context, Size size)
void MemoryContextReset(MemoryContext context)
void * repalloc(void *pointer, Size size)
void pfree(void *pointer)
void * palloc0(Size size)
MemoryContext CurrentMemoryContext
#define AllocSetContextCreate
#define ALLOCSET_SMALL_SIZES
static bool _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, FmgrInfo *sortproc, bool reverse, Oid origelemtype, Oid nextelemtype, Datum *elems_orig, int *nelems_orig, Datum *elems_next, int nelems_next)
static void _bt_skiparray_strat_increment(IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)
static int _bt_num_array_keys(IndexScanDesc scan, Oid *skip_eq_ops_out, int *numSkipArrayKeys_out)
static bool _bt_saoparray_shrink(IndexScanDesc scan, ScanKey arraysk, ScanKey skey, FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
struct BTScanKeyPreproc BTScanKeyPreproc
static void _bt_skiparray_strat_adjust(IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)
struct BTSortArrayContext BTSortArrayContext
static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey, Oid elemtype, StrategyNumber strat, Datum *elems, int nelems)
static int _bt_reorder_array_cmp(const void *a, const void *b)
static bool _bt_skiparray_shrink(IndexScanDesc scan, ScanKey skey, BTArrayKeyInfo *array, bool *qual_ok)
static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
static void _bt_unmark_keys(IndexScanDesc scan, int *keyDataMap)
static void _bt_mark_scankey_required(ScanKey skey)
static ScanKey _bt_preprocess_array_keys(IndexScanDesc scan, int *new_numberOfKeys)
static int _bt_compare_array_elements(const void *a, const void *b, void *arg)
static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
static void _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype, FmgrInfo *orderproc, FmgrInfo **sortprocp)
static int _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc, bool reverse, Datum *elems, int nelems)
static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op, ScanKey leftarg, ScanKey rightarg, BTArrayKeyInfo *array, FmgrInfo *orderproc, bool *result)
static void _bt_skiparray_strat_decrement(IndexScanDesc scan, ScanKey arraysk, BTArrayKeyInfo *array)
static bool _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey, FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
void _bt_preprocess_keys(IndexScanDesc scan)
#define SK_BT_INDOPTION_SHIFT
#define SK_BT_NULLS_FIRST
#define BTCommuteStrategyNumber(strat)
BTScanOpaqueData * BTScanOpaque
int _bt_binsrch_array_skey(FmgrInfo *orderproc, bool cur_elem_trig, ScanDirection dir, Datum tupdatum, bool tupnull, BTArrayKeyInfo *array, ScanKey cur, int32 *set_elem_result)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
#define qsort(a, b, c, d)
static bool DatumGetBool(Datum X)
static Pointer DatumGetPointer(Datum X)
static int32 DatumGetInt32(Datum X)
static size_t qunique_arg(void *array, size_t elements, size_t width, int(*compare)(const void *, const void *, void *), void *arg)
#define RelationGetDescr(relation)
#define RelationGetRelationName(relation)
#define IndexRelationGetNumberOfKeyAttributes(relation)
void ScanKeyEntryInitialize(ScanKey entry, int flags, AttrNumber attributeNumber, StrategyNumber strategy, Oid subtype, Oid collation, RegProcedure procedure, Datum argument)
@ NoMovementScanDirection
SkipSupport PrepareSkipSupportFromOpclass(Oid opfamily, Oid opcintype, bool reverse)
#define BTGreaterStrategyNumber
#define BTMaxStrategyNumber
#define BTLessStrategyNumber
#define BTEqualStrategyNumber
#define BTLessEqualStrategyNumber
#define BTGreaterEqualStrategyNumber
BTArrayKeyInfo * arrayKeys
MemoryContext arrayContext
struct ScanKeyData * keyData
struct ParallelIndexScanDescData * parallel_scan
StrategyNumber sk_strategy
SkipSupportIncDec decrement
SkipSupportIncDec increment
static CompactAttribute * TupleDescCompactAttr(TupleDesc tupdesc, int i)