| blob | d7603250279d9a87fe9ae28e68fe44d9d3d3bd2b |
1 /*-------------------------------------------------------------------------
2 *
3 * nbtutils.c
4 * Utility code for Postgres btree implementation.
5 *
6 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/access/nbtree/nbtutils.c
12 *
13 *-------------------------------------------------------------------------
14 */
18 #include <time.h>
32 #define LOOK_AHEAD_REQUIRED_RECHECKS 3
33 #define LOOK_AHEAD_DEFAULT_DISTANCE 5
36 {
38 Oid collation;
43 {
44 ScanKey inkey;
84 #ifdef USE_ASSERT_CHECKING
87 #endif
107 /*
108 * _bt_mkscankey
109 * Build an insertion scan key that contains comparison data from itup
110 * as well as comparator routines appropriate to the key datatypes.
111 *
112 * The result is intended for use with _bt_compare() and _bt_truncate().
113 * Callers that don't need to fill out the insertion scankey arguments
114 * (e.g. they use an ad-hoc comparison routine, or only need a scankey
115 * for _bt_truncate()) can pass a NULL index tuple. The scankey will
116 * be initialized as if an "all truncated" pivot tuple was passed
117 * instead.
118 *
119 * Note that we may occasionally have to share lock the metapage to
120 * determine whether or not the keys in the index are expected to be
121 * unique (i.e. if this is a "heapkeyspace" index). We assume a
122 * heapkeyspace index when caller passes a NULL tuple, allowing index
123 * build callers to avoid accessing the non-existent metapage. We
124 * also assume that the index is _not_ allequalimage when a NULL tuple
125 * is passed; CREATE INDEX callers call _bt_allequalimage() to set the
126 * field themselves.
127 */
128 BTScanInsert
130 {
131 BTScanInsert key;
132 ScanKey skey;
133 TupleDesc itupdesc;
146 /*
147 * We'll execute search using scan key constructed on key columns.
148 * Truncated attributes and non-key attributes are omitted from the final
149 * scan key.
150 */
155 else
156 {
157 /* Utility statement callers can set these fields themselves */
160 }
169 {
171 Datum arg;
175 /*
176 * We can use the cached (default) support procs since no cross-type
177 * comparison can be needed.
178 */
181 /*
182 * Key arguments built from truncated attributes (or when caller
183 * provides no tuple) are defensively represented as NULL values. They
184 * should never be used.
185 */
188 else
189 {
192 }
195 flags,
197 InvalidStrategy,
198 InvalidOid,
200 procinfo,
201 arg);
202 /* Record if any key attribute is NULL (or truncated) */
205 }
207 /*
208 * In NULLS NOT DISTINCT mode, we pretend that there are no null keys, so
209 * that full uniqueness check is done.
210 */
215 }
217 /*
218 * free a retracement stack made by _bt_search.
219 */
220 void
222 {
223 BTStack ostack;
226 {
230 }
231 }
234 /*
235 * _bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys
236 *
237 * If there are any SK_SEARCHARRAY scan keys, deconstruct the array(s) and
238 * set up BTArrayKeyInfo info for each one that is an equality-type key.
239 * Returns modified scan keys as input for further, standard preprocessing.
240 *
241 * Currently we perform two kinds of preprocessing to deal with redundancies.
242 * For inequality array keys, it's sufficient to find the extreme element
243 * value and replace the whole array with that scalar value. This eliminates
244 * all but one array element as redundant. Similarly, we are capable of
245 * "merging together" multiple equality array keys (from two or more input
246 * scan keys) into a single output scan key containing only the intersecting
247 * array elements. This can eliminate many redundant array elements, as well
248 * as eliminating whole array scan keys as redundant. It can also allow us to
249 * detect contradictory quals.
250 *
251 * Caller must pass *new_numberOfKeys to give us a way to change the number of
252 * scan keys that caller treats as input to standard preprocessing steps. The
253 * returned array is smaller than scan->keyData[] when we could eliminate a
254 * redundant array scan key (redundant with another array scan key). It is
255 * convenient for _bt_preprocess_keys caller to have to deal with no more than
256 * one equality strategy array scan key per index attribute. We'll always be
257 * able to set things up that way when complete opfamilies are used.
258 *
259 * We set the scan key references from the scan's BTArrayKeyInfo info array to
260 * offsets into the temp modified input array returned to caller. Scans that
261 * have array keys should call _bt_preprocess_array_keys_final when standard
262 * preprocessing steps are complete. This will convert the scan key offset
263 * references into references to the scan's so->keyData[] output scan keys.
264 *
265 * Note: the reason we need to return a temp scan key array, rather than just
266 * scribbling on scan->keyData, is that callers are permitted to call btrescan
267 * without supplying a new set of scankey data.
268 */
269 static ScanKey
271 {
281 ScanKey cur;
282 MemoryContext oldContext;
287 /* Quick check to see if there are any array keys */
290 {
293 {
294 numArrayKeys++;
296 /* If any arrays are null as a whole, we can quit right now. */
298 {
301 }
302 }
303 }
305 /* Quit if nothing to do. */
309 /*
310 * Make a scan-lifespan context to hold array-associated data, or reset it
311 * if we already have one from a previous rescan cycle.
312 */
316 ALLOCSET_SMALL_SIZES);
317 else
322 /* Create output scan keys in the workspace context */
325 /* Allocate space for per-array data in the workspace context */
328 /* Allocate space for ORDER procs used to help _bt_checkkeys */
331 /* Now process each array key */
334 {
335 FmgrInfo sortproc;
337 Oid elemtype;
340 int16 elmlen;
349 /*
350 * Provisionally copy scan key into arrayKeyData[] array we'll return
351 * to _bt_preprocess_keys caller
352 */
357 {
360 }
362 /*
363 * Deconstruct the array into elements
364 */
366 /* We could cache this data, but not clear it's worth it */
374 /*
375 * Compress out any null elements. We can ignore them since we assume
376 * all btree operators are strict.
377 */
380 {
383 }
385 /* We could pfree(elem_nulls) now, but not worth the cycles */
387 /* If there's no non-nulls, the scan qual is unsatisfiable */
389 {
392 }
394 /*
395 * Determine the nominal datatype of the array elements. We have to
396 * support the convention that sk_subtype == InvalidOid means the
397 * opclass input type; this is a hack to simplify life for
398 * ScanKeyInit().
399 */
404 /*
405 * If the comparison operator is not equality, then the array qual
406 * degenerates to a simple comparison against the smallest or largest
407 * non-null array element, as appropriate.
408 */
410 {
415 BTGreaterStrategyNumber,
420 /* proceed with rest of loop */
426 BTLessStrategyNumber,
434 }
436 /*
437 * We'll need a 3-way ORDER proc to perform binary searches for the
438 * next matching array element. Set that up now.
439 *
440 * Array scan keys with cross-type equality operators will require a
441 * separate same-type ORDER proc for sorting their array. Otherwise,
442 * sortproc just points to the same proc used during binary searches.
443 */
447 /*
448 * Sort the non-null elements and eliminate any duplicates. We must
449 * sort in the same ordering used by the index column, so that the
450 * arrays can be advanced in lockstep with the scan's progress through
451 * the index's key space.
452 */
458 {
461 /*
462 * This array scan key is redundant with a previous equality
463 * operator array scan key. Merge the two arrays together to
464 * eliminate contradictory non-intersecting elements (or try to).
465 *
466 * We merge this next array back into attribute's original array.
467 */
475 {
476 /* Successfully eliminated this array */
479 /*
480 * If no intersecting elements remain in the original array,
481 * the scan qual is unsatisfiable
482 */
484 {
487 }
489 /* Throw away this scan key/array */
491 }
493 /*
494 * Unable to merge this array with previous array due to a lack of
495 * suitable cross-type opfamily support. Will need to keep both
496 * scan keys/arrays.
497 */
498 }
499 else
500 {
501 /*
502 * This array is the first for current index attribute.
503 *
504 * If it turns out to not be the last array (that is, if the next
505 * array is redundantly applied to this same index attribute),
506 * we'll then treat this array as the attribute's "original" array
507 * when merging.
508 */
512 }
514 /*
515 * And set up the BTArrayKeyInfo data.
516 *
517 * Note: _bt_preprocess_array_keys_final will fix-up each array's
518 * scan_key field later on, after so->keyData[] has been finalized.
519 */
523 numArrayKeys++;
525 }
527 /* Set final number of equality-type array keys */
529 /* Set number of scan keys remaining in arrayKeyData[] */
535 }
537 /*
538 * _bt_preprocess_array_keys_final() -- fix up array scan key references
539 *
540 * When _bt_preprocess_array_keys performed initial array preprocessing, it
541 * set each array's array->scan_key to its scankey's arrayKeyData[] offset.
542 * This function handles translation of the scan key references from the
543 * BTArrayKeyInfo info array, from input scan key references (to the keys in
544 * arrayKeyData[]), into output references (to the keys in so->keyData[]).
545 * Caller's keyDataMap[] array tells us how to perform this remapping.
546 *
547 * Also finalizes so->orderProcs[] for the scan. Arrays already have an ORDER
548 * proc, which might need to be repositioned to its so->keyData[]-wise offset
549 * (very much like the remapping that we apply to array->scan_key references).
550 * Non-array equality strategy scan keys (that survived preprocessing) don't
551 * yet have an so->orderProcs[] entry, so we set one for them here.
552 *
553 * Also converts single-element array scan keys into equivalent non-array
554 * equality scan keys, which decrements so->numArrayKeys. It's possible that
555 * this will leave this new btrescan without any arrays at all. This isn't
556 * necessary for correctness; it's just an optimization. Non-array equality
557 * scan keys are slightly faster than equivalent array scan keys at runtime.
558 */
559 static void
561 {
569 /*
570 * Nothing for us to do when _bt_preprocess_array_keys only had to deal
571 * with array inequalities
572 */
577 {
593 /*
594 * We're lazy about looking up ORDER procs for non-array keys, since
595 * not all input keys become output keys. Take care of it now.
596 */
598 {
599 Oid elemtype;
601 /* No need for an ORDER proc given an IS NULL scan key */
605 /*
606 * A non-required scan key doesn't need an ORDER proc, either
607 * (unless it's associated with an array, which this one isn't)
608 */
619 }
621 /*
622 * Reorder existing array scan key so->orderProcs[] entries.
623 *
624 * Doing this in-place is safe because preprocessing is required to
625 * output all equality strategy scan keys in original input order
626 * (among each group of entries against the same index attribute).
627 * This is also the order that the arrays themselves appear in.
628 */
631 /* Fix-up array->scan_key references for arrays */
633 {
639 {
640 /* found it */
644 /*
645 * Transform array scan keys that have exactly 1 element
646 * remaining (following all prior preprocessing) into
647 * equivalent non-array scan keys.
648 */
650 {
655 /* If we're out of array keys, we can quit right away */
659 /* Shift other arrays forward */
664 /*
665 * Don't increment arrayidx (there was an entry that was
666 * just shifted forward to the offset at arrayidx, which
667 * will still need to be matched)
668 */
669 }
670 else
671 {
672 /* Match found, so done with this array */
673 arrayidx++;
674 }
677 }
678 }
681 }
683 /*
684 * Parallel index scans require space in shared memory to store the
685 * current array elements (for arrays kept by preprocessing) to schedule
686 * the next primitive index scan. The underlying structure is protected
687 * using a spinlock, so defensively limit its size. In practice this can
688 * only affect parallel scans that use an incomplete opfamily.
689 */
693 errmsg_internal("number of array scan keys left by preprocessing (%d) exceeds the maximum allowed by parallel btree index scans (%d)",
695 }
697 /*
698 * _bt_setup_array_cmp() -- Set up array comparison functions
699 *
700 * Sets ORDER proc in caller's orderproc argument, which is used during binary
701 * searches of arrays during the index scan. Also sets a same-type ORDER proc
702 * in caller's *sortprocp argument, which is used when sorting the array.
703 *
704 * Preprocessing calls here with all equality strategy scan keys (when scan
705 * uses equality array keys), including those not associated with any array.
706 * See _bt_advance_array_keys for an explanation of why it'll need to treat
707 * simple scalar equality scan keys as degenerate single element arrays.
708 *
709 * Caller should pass an orderproc pointing to space that'll store the ORDER
710 * proc for the scan, and a *sortprocp pointing to its own separate space.
711 * When calling here for a non-array scan key, sortprocp arg should be NULL.
712 *
713 * In the common case where we don't need to deal with cross-type operators,
714 * only one ORDER proc is actually required by caller. We'll set *sortprocp
715 * to point to the same memory that caller's orderproc continues to point to.
716 * Otherwise, *sortprocp will continue to point to caller's own space. Either
717 * way, *sortprocp will point to a same-type ORDER proc (since that's the only
718 * safe way to sort/deduplicate the array associated with caller's scan key).
719 */
720 static void
723 {
726 RegProcedure cmp_proc;
732 /*
733 * If scankey operator is not a cross-type comparison, we can use the
734 * cached comparison function; otherwise gotta look it up in the catalogs
735 */
737 {
738 /* Set same-type ORDER procs for caller */
744 }
746 /*
747 * Look up the appropriate cross-type comparison function in the opfamily.
748 *
749 * Use the opclass input type as the left hand arg type, and the array
750 * element type as the right hand arg type (since binary searches use an
751 * index tuple's attribute value to search for a matching array element).
752 *
753 * Note: it's possible that this would fail, if the opfamily is
754 * incomplete, but only in cases where it's quite likely that _bt_first
755 * would fail in just the same way (had we not failed before it could).
756 */
764 /* Set cross-type ORDER proc for caller */
767 /* Done if caller doesn't actually have an array they'll need to sort */
771 /*
772 * Look up the appropriate same-type comparison function in the opfamily.
773 *
774 * Note: it's possible that this would fail, if the opfamily is
775 * incomplete, but it seems quite unlikely that an opfamily would omit
776 * non-cross-type comparison procs for any datatype that it supports at
777 * all.
778 */
786 /* Set same-type ORDER proc for caller */
788 }
790 /*
791 * _bt_find_extreme_element() -- get least or greatest array element
792 *
793 * scan and skey identify the index column, whose opfamily determines the
794 * comparison semantics. strat should be BTLessStrategyNumber to get the
795 * least element, or BTGreaterStrategyNumber to get the greatest.
796 */
797 static Datum
799 StrategyNumber strat,
801 {
803 Oid cmp_op;
804 RegProcedure cmp_proc;
805 FmgrInfo flinfo;
806 Datum result;
809 /*
810 * Look up the appropriate comparison operator in the opfamily.
811 *
812 * Note: it's possible that this would fail, if the opfamily is
813 * incomplete, but it seems quite unlikely that an opfamily would omit
814 * non-cross-type comparison operators for any datatype that it supports
815 * at all.
816 */
820 elemtype,
821 elemtype,
822 strat);
836 {
840 result)))
842 }
845 }
847 /*
848 * _bt_sort_array_elements() -- sort and de-dup array elements
849 *
850 * The array elements are sorted in-place, and the new number of elements
851 * after duplicate removal is returned.
852 *
853 * skey identifies the index column whose opfamily determines the comparison
854 * semantics, and sortproc is a corresponding ORDER proc. If reverse is true,
855 * we sort in descending order.
856 */
857 static int
860 {
861 BTSortArrayContext cxt;
866 /* Sort the array elements */
873 /* Now scan the sorted elements and remove duplicates */
876 }
878 /*
879 * _bt_merge_arrays() -- merge next array's elements into an original array
880 *
881 * Called when preprocessing encounters a pair of array equality scan keys,
882 * both against the same index attribute (during initial array preprocessing).
883 * Merging reorganizes caller's original array (the left hand arg) in-place,
884 * without ever copying elements from one array into the other. (Mixing the
885 * elements together like this would be wrong, since they don't necessarily
886 * use the same underlying element type, despite all the other similarities.)
887 *
888 * Both arrays must have already been sorted and deduplicated by calling
889 * _bt_sort_array_elements. sortproc is the same-type ORDER proc that was
890 * just used to sort and deduplicate caller's "next" array. We'll usually be
891 * able to reuse that order PROC to merge the arrays together now. If not,
892 * then we'll perform a separate ORDER proc lookup.
893 *
894 * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
895 * may not be able to determine which elements are contradictory. If we have
896 * the required ORDER proc then we return true (and validly set *nelems_orig),
897 * guaranteeing that at least the next array can be considered redundant. We
898 * return false if the required comparisons cannot not be made (caller must
899 * keep both arrays when this happens).
900 */
901 static bool
906 {
909 BTSortArrayContext cxt;
913 FmgrInfo crosstypeproc;
919 {
920 RegProcedure cmp_proc;
922 /*
923 * Cross-array-element-type merging is required, so can't just reuse
924 * sortproc when merging
925 */
929 {
930 /* Can't make the required comparisons */
932 }
934 /* We have all we need to determine redundancy/contradictoriness */
937 }
944 {
950 {
952 i++;
953 j++;
954 }
956 i++;
958 j++;
959 }
964 }
966 /*
967 * Compare an array scan key to a scalar scan key, eliminating contradictory
968 * array elements such that the scalar scan key becomes redundant.
969 *
970 * Array elements can be eliminated as contradictory when excluded by some
971 * other operator on the same attribute. For example, with an index scan qual
972 * "WHERE a IN (1, 2, 3) AND a < 2", all array elements except the value "1"
973 * are eliminated, and the < scan key is eliminated as redundant. Cases where
974 * every array element is eliminated by a redundant scalar scan key have an
975 * unsatisfiable qual, which we handle by setting *qual_ok=false for caller.
976 *
977 * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
978 * may not be able to determine which elements are contradictory. If we have
979 * the required ORDER proc then we return true (and validly set *qual_ok),
980 * guaranteeing that at least the scalar scan key can be considered redundant.
981 * We return false if the comparison could not be made (caller must keep both
982 * scan keys when this happens).
983 */
984 static bool
988 {
993 matchelem,
995 FmgrInfo crosstypeproc;
1007 /*
1008 * _bt_binsrch_array_skey searches an array for the entry best matching a
1009 * datum of opclass input type for the index's attribute (on-disk type).
1010 * We can reuse the array's ORDER proc whenever the non-array scan key's
1011 * type is a match for the corresponding attribute's input opclass type.
1012 * Otherwise, we have to do another ORDER proc lookup so that our call to
1013 * _bt_binsrch_array_skey applies the correct comparator.
1014 *
1015 * Note: we have to support the convention that sk_subtype == InvalidOid
1016 * means the opclass input type; this is a hack to simplify life for
1017 * ScanKeyInit().
1018 */
1020 {
1021 RegProcedure cmp_proc;
1022 Oid arraysk_elemtype;
1024 /*
1025 * Need an ORDER proc lookup to detect redundancy/contradictoriness
1026 * with this pair of scankeys.
1027 *
1028 * Scalar scan key's argument will be passed to _bt_compare_array_skey
1029 * as its tupdatum/lefthand argument (rhs arg is for array elements).
1030 */
1036 BTORDER_PROC);
1038 {
1039 /* Can't make the comparison */
1042 }
1044 /* We have all we need to determine redundancy/contradictoriness */
1047 }
1050 NoMovementScanDirection,
1055 {
1058 /* FALL THRU */
1061 matchelem++;
1062 /* Resize, keeping elements from the start of the array */
1067 {
1068 /* qual is unsatisfiable */
1070 }
1071 else
1072 {
1073 /* Shift matching element to the start of the array, resize */
1076 }
1080 /* FALL THRU */
1083 matchelem++;
1084 /* Shift matching elements to the start of the array, resize */
1093 }
1102 }
1104 /*
1105 * qsort_arg comparator for sorting array elements
1106 */
1107 static int
1109 {
1113 int32 compare;
1121 }
1123 /*
1124 * _bt_compare_array_skey() -- apply array comparison function
1125 *
1126 * Compares caller's tuple attribute value to a scan key/array element.
1127 * Helper function used during binary searches of SK_SEARCHARRAY arrays.
1128 *
1129 * This routine returns:
1130 * <0 if tupdatum < arrdatum;
1131 * 0 if tupdatum == arrdatum;
1132 * >0 if tupdatum > arrdatum.
1133 *
1134 * This is essentially the same interface as _bt_compare: both functions
1135 * compare the value that they're searching for to a binary search pivot.
1136 * However, unlike _bt_compare, this function's "tuple argument" comes first,
1137 * while its "array/scankey argument" comes second.
1138 */
1143 {
1149 {
1154 else
1156 }
1158 {
1161 else
1163 }
1164 else
1165 {
1166 /*
1167 * Like _bt_compare, we need to be careful of cross-type comparisons,
1168 * so the left value has to be the value that came from an index tuple
1169 */
1173 /*
1174 * We flip the sign by following the obvious rule: flip whenever the
1175 * column is a DESC column.
1176 *
1177 * _bt_compare does it the wrong way around (flip when *ASC*) in order
1178 * to compensate for passing its orderproc arguments backwards. We
1179 * don't need to play these games because we find it natural to pass
1180 * tupdatum as the left value (and arrdatum as the right value).
1181 */
1184 }
1187 }
1189 /*
1190 * _bt_binsrch_array_skey() -- Binary search for next matching array key
1191 *
1192 * Returns an index to the first array element >= caller's tupdatum argument.
1193 * This convention is more natural for forwards scan callers, but that can't
1194 * really matter to backwards scan callers. Both callers require handling for
1195 * the case where the match we return is < tupdatum, and symmetric handling
1196 * for the case where our best match is > tupdatum.
1197 *
1198 * Also sets *set_elem_result to the result _bt_compare_array_skey returned
1199 * when we used it to compare the matching array element to tupdatum/tupnull.
1200 *
1201 * cur_elem_trig indicates if array advancement was triggered by this array's
1202 * scan key, and that the array is for a required scan key. We can apply this
1203 * information to find the next matching array element in the current scan
1204 * direction using far fewer comparisons (fewer on average, compared to naive
1205 * binary search). This scheme takes advantage of an important property of
1206 * required arrays: required arrays always advance in lockstep with the index
1207 * scan's progress through the index's key space.
1208 */
1209 static int
1215 {
1220 Datum arrdatum;
1226 {
1230 /*
1231 * When the scan key that triggered array advancement is a required
1232 * array scan key, it is now certain that the current array element
1233 * (plus all prior elements relative to the current scan direction)
1234 * cannot possibly be at or ahead of the corresponding tuple value.
1235 * (_bt_checkkeys must have called _bt_tuple_before_array_skeys, which
1236 * makes sure this is true as a condition of advancing the arrays.)
1237 *
1238 * This makes it safe to exclude array elements up to and including
1239 * the former-current array element from our search.
1240 *
1241 * Separately, when array advancement was triggered by a required scan
1242 * key, the array element immediately after the former-current element
1243 * is often either an exact tupdatum match, or a "close by" near-match
1244 * (a near-match tupdatum is one whose key space falls _between_ the
1245 * former-current and new-current array elements). We'll detect both
1246 * cases via an optimistic comparison of the new search lower bound
1247 * (or new search upper bound in the case of backwards scans).
1248 */
1250 {
1253 /* Compare prospective new cur_elem (also the new lower bound) */
1255 {
1261 {
1262 /* Optimistic comparison optimization worked out */
1265 }
1268 }
1271 {
1272 /* Caller needs to perform "beyond end" array advancement */
1275 }
1276 }
1277 else
1278 {
1281 /* Compare prospective new cur_elem (also the new upper bound) */
1283 {
1289 {
1290 /* Optimistic comparison optimization worked out */
1293 }
1296 }
1299 {
1300 /* Caller needs to perform "beyond end" array advancement */
1303 }
1304 }
1305 }
1308 {
1316 {
1317 /*
1318 * It's safe to quit as soon as we see an equal array element.
1319 * This often saves an extra comparison or two...
1320 */
1323 }
1327 else
1329 }
1331 /*
1332 * ...but our caller also cares about how its searched-for tuple datum
1333 * compares to the low_elem datum. Must always set *set_elem_result with
1334 * the result of that comparison specifically.
1335 */
1343 }
1345 /*
1346 * _bt_start_array_keys() -- Initialize array keys at start of a scan
1347 *
1348 * Set up the cur_elem counters and fill in the first sk_argument value for
1349 * each array scankey.
1350 */
1351 void
1353 {
1361 {
1370 else
1373 }
1375 }
1377 /*
1378 * _bt_advance_array_keys_increment() -- Advance to next set of array elements
1379 *
1380 * Advances the array keys by a single increment in the current scan
1381 * direction. When there are multiple array keys this can roll over from the
1382 * lowest order array to higher order arrays.
1383 *
1384 * Returns true if there is another set of values to consider, false if not.
1385 * On true result, the scankeys are initialized with the next set of values.
1386 * On false result, the scankeys stay the same, and the array keys are not
1387 * advanced (every array remains at its final element for scan direction).
1388 */
1389 static bool
1391 {
1394 /*
1395 * We must advance the last array key most quickly, since it will
1396 * correspond to the lowest-order index column among the available
1397 * qualifications
1398 */
1400 {
1408 {
1411 }
1413 {
1416 }
1423 /* Need to advance next array key, if any */
1424 }
1426 /*
1427 * The array keys are now exhausted.
1428 *
1429 * Restore the array keys to the state they were in immediately before we
1430 * were called. This ensures that the arrays only ever ratchet in the
1431 * current scan direction.
1432 *
1433 * Without this, scans could overlook matching tuples when the scan
1434 * direction gets reversed just before btgettuple runs out of items to
1435 * return, but just after _bt_readpage prepares all the items from the
1436 * scan's final page in so->currPos. When we're on the final page it is
1437 * typical for so->currPos to get invalidated once btgettuple finally
1438 * returns false, which'll effectively invalidate the scan's array keys.
1439 * That hasn't happened yet, though -- and in general it may never happen.
1440 */
1444 }
1446 /*
1447 * _bt_rewind_nonrequired_arrays() -- Rewind non-required arrays
1448 *
1449 * Called when _bt_advance_array_keys decides to start a new primitive index
1450 * scan on the basis of the current scan position being before the position
1451 * that _bt_first is capable of repositioning the scan to by applying an
1452 * inequality operator required in the opposite-to-scan direction only.
1453 *
1454 * Although equality strategy scan keys (for both arrays and non-arrays alike)
1455 * are either marked required in both directions or in neither direction,
1456 * there is a sense in which non-required arrays behave like required arrays.
1457 * With a qual such as "WHERE a IN (100, 200) AND b >= 3 AND c IN (5, 6, 7)",
1458 * the scan key on "c" is non-required, but nevertheless enables positioning
1459 * the scan at the first tuple >= "(100, 3, 5)" on the leaf level during the
1460 * first descent of the tree by _bt_first. Later on, there could also be a
1461 * second descent, that places the scan right before tuples >= "(200, 3, 5)".
1462 * _bt_first must never be allowed to build an insertion scan key whose "c"
1463 * entry is set to a value other than 5, the "c" array's first element/value.
1464 * (Actually, it's the first in the current scan direction. This example uses
1465 * a forward scan.)
1466 *
1467 * Calling here resets the array scan key elements for the scan's non-required
1468 * arrays. This is strictly necessary for correctness in a subset of cases
1469 * involving "required in opposite direction"-triggered primitive index scans.
1470 * Not all callers are at risk of _bt_first using a non-required array like
1471 * this, but advancement always resets the arrays when another primitive scan
1472 * is scheduled, just to keep things simple. Array advancement even makes
1473 * sure to reset non-required arrays during scans that have no inequalities.
1474 * (Advancement still won't call here when there are no inequalities, though
1475 * that's just because it's all handled indirectly instead.)
1476 *
1477 * Note: _bt_verify_arrays_bt_first is called by an assertion to enforce that
1478 * everybody got this right.
1479 */
1480 static void
1482 {
1487 {
1504 else
1508 {
1511 }
1512 }
1513 }
1515 /*
1516 * _bt_tuple_before_array_skeys() -- too early to advance required arrays?
1517 *
1518 * We always compare the tuple using the current array keys (which we assume
1519 * are already set in so->keyData[]). readpagetup indicates if tuple is the
1520 * scan's current _bt_readpage-wise tuple.
1521 *
1522 * readpagetup callers must only call here when _bt_check_compare already set
1523 * continuescan=false. We help these callers deal with _bt_check_compare's
1524 * inability to distinguishing between the < and > cases (it uses equality
1525 * operator scan keys, whereas we use 3-way ORDER procs). These callers pass
1526 * a _bt_check_compare-set sktrig value that indicates which scan key
1527 * triggered the call (!readpagetup callers just pass us sktrig=0 instead).
1528 * This information allows us to avoid wastefully checking earlier scan keys
1529 * that were already deemed to have been satisfied inside _bt_check_compare.
1530 *
1531 * Returns false when caller's tuple is >= the current required equality scan
1532 * keys (or <=, in the case of backwards scans). This happens to readpagetup
1533 * callers when the scan has reached the point of needing its array keys
1534 * advanced; caller will need to advance required and non-required arrays at
1535 * scan key offsets >= sktrig, plus scan keys < sktrig iff sktrig rolls over.
1536 * (When we return false to readpagetup callers, tuple can only be == current
1537 * required equality scan keys when caller's sktrig indicates that the arrays
1538 * need to be advanced due to an unsatisfied required inequality key trigger.)
1539 *
1540 * Returns true when caller passes a tuple that is < the current set of
1541 * equality keys for the most significant non-equal required scan key/column
1542 * (or > the keys, during backwards scans). This happens to readpagetup
1543 * callers when tuple is still before the start of matches for the scan's
1544 * required equality strategy scan keys. (sktrig can't have indicated that an
1545 * inequality strategy scan key wasn't satisfied in _bt_check_compare when we
1546 * return true. In fact, we automatically return false when passed such an
1547 * inequality sktrig by readpagetup callers -- _bt_check_compare's initial
1548 * continuescan=false doesn't really need to be confirmed here by us.)
1549 *
1550 * !readpagetup callers optionally pass us *scanBehind, which tracks whether
1551 * any missing truncated attributes might have affected array advancement
1552 * (compared to what would happen if it was shown the first non-pivot tuple on
1553 * the page to the right of caller's finaltup/high key tuple instead). It's
1554 * only possible that we'll set *scanBehind to true when caller passes us a
1555 * pivot tuple (with truncated -inf attributes) that we return false for.
1556 */
1557 static bool
1561 {
1573 {
1575 Datum tupdatum;
1577 int32 result;
1579 /* readpagetup calls require one ORDER proc comparison (at most) */
1582 /*
1583 * Once we reach a non-required scan key, we're completely done.
1584 *
1585 * Note: we deliberately don't consider the scan direction here.
1586 * _bt_advance_array_keys caller requires that we track *scanBehind
1587 * without concern for scan direction.
1588 */
1590 {
1594 }
1597 {
1600 /*
1601 * When we reach a high key's truncated attribute, assume that the
1602 * tuple attribute's value is >= the scan's equality constraint
1603 * scan keys (but set *scanBehind to let interested callers know
1604 * that a truncated attribute might have affected our answer).
1605 */
1610 }
1612 /*
1613 * Deal with inequality strategy scan keys that _bt_check_compare set
1614 * continuescan=false for
1615 */
1617 {
1618 /*
1619 * When _bt_check_compare indicated that a required inequality
1620 * scan key wasn't satisfied, there's no need to verify anything;
1621 * caller always calls _bt_advance_array_keys with this sktrig.
1622 */
1626 /*
1627 * Otherwise we can't give up, since we must check all required
1628 * scan keys (required in either direction) in order to correctly
1629 * track *scanBehind for caller
1630 */
1632 }
1640 /*
1641 * Does this comparison indicate that caller must _not_ advance the
1642 * scan's arrays just yet?
1643 */
1648 /*
1649 * Does this comparison indicate that caller should now advance the
1650 * scan's arrays? (Must be if we get here during a readpagetup call.)
1651 */
1653 {
1656 }
1658 /*
1659 * Inconclusive -- need to check later scan keys, too.
1660 *
1661 * This must be a finaltup precheck, or a call made from an assertion.
1662 */
1664 }
1669 }
1671 /*
1672 * _bt_start_prim_scan() -- start scheduled primitive index scan?
1673 *
1674 * Returns true if _bt_checkkeys scheduled another primitive index scan, just
1675 * as the last one ended. Otherwise returns false, indicating that the array
1676 * keys are now fully exhausted.
1677 *
1678 * Only call here during scans with one or more equality type array scan keys,
1679 * after _bt_first or _bt_next return false.
1680 */
1681 bool
1683 {
1690 /*
1691 * Array keys are advanced within _bt_checkkeys when the scan reaches the
1692 * leaf level (more precisely, they're advanced when the scan reaches the
1693 * end of each distinct set of array elements). This process avoids
1694 * repeat access to leaf pages (across multiple primitive index scans) by
1695 * advancing the scan's array keys when it allows the primitive index scan
1696 * to find nearby matching tuples (or when it eliminates ranges of array
1697 * key space that can't possibly be satisfied by any index tuple).
1698 *
1699 * _bt_checkkeys sets a simple flag variable to schedule another primitive
1700 * index scan. The flag tells us what to do.
1701 *
1702 * We cannot rely on _bt_first always reaching _bt_checkkeys. There are
1703 * various cases where that won't happen. For example, if the index is
1704 * completely empty, then _bt_first won't call _bt_readpage/_bt_checkkeys.
1705 * We also don't expect a call to _bt_checkkeys during searches for a
1706 * non-existent value that happens to be lower/higher than any existing
1707 * value in the index.
1708 *
1709 * We don't require special handling for these cases -- we don't need to
1710 * be explicitly instructed to _not_ perform another primitive index scan.
1711 * It's up to code under the control of _bt_first to always set the flag
1712 * when another primitive index scan will be required.
1713 *
1714 * This works correctly, even with the tricky cases listed above, which
1715 * all involve access to leaf pages "near the boundaries of the key space"
1716 * (whether it's from a leftmost/rightmost page, or an imaginary empty
1717 * leaf root page). If _bt_checkkeys cannot be reached by a primitive
1718 * index scan for one set of array keys, then it also won't be reached for
1719 * any later set ("later" in terms of the direction that we scan the index
1720 * and advance the arrays). The array keys won't have advanced in these
1721 * cases, but that's the correct behavior (even _bt_advance_array_keys
1722 * won't always advance the arrays at the point they become "exhausted").
1723 */
1725 {
1728 /*
1729 * Flag was set -- must call _bt_first again, which will reset the
1730 * scan's needPrimScan flag
1731 */
1733 }
1735 /* The top-level index scan ran out of tuples in this scan direction */
1740 }
1742 /*
1743 * _bt_advance_array_keys() -- Advance array elements using a tuple
1744 *
1745 * The scan always gets a new qual as a consequence of calling here (except
1746 * when we determine that the top-level scan has run out of matching tuples).
1747 * All later _bt_check_compare calls also use the same new qual that was first
1748 * used here (at least until the next call here advances the keys once again).
1749 * It's convenient to structure _bt_check_compare rechecks of caller's tuple
1750 * (using the new qual) as one the steps of advancing the scan's array keys,
1751 * so this function works as a wrapper around _bt_check_compare.
1752 *
1753 * Like _bt_check_compare, we'll set pstate.continuescan on behalf of the
1754 * caller, and return a boolean indicating if caller's tuple satisfies the
1755 * scan's new qual. But unlike _bt_check_compare, we set so->needPrimScan
1756 * when we set continuescan=false, indicating if a new primitive index scan
1757 * has been scheduled (otherwise, the top-level scan has run out of tuples in
1758 * the current scan direction).
1759 *
1760 * Caller must use _bt_tuple_before_array_skeys to determine if the current
1761 * place in the scan is >= the current array keys _before_ calling here.
1762 * We're responsible for ensuring that caller's tuple is <= the newly advanced
1763 * required array keys once we return. We try to find an exact match, but
1764 * failing that we'll advance the array keys to whatever set of array elements
1765 * comes next in the key space for the current scan direction. Required array
1766 * keys "ratchet forwards" (or backwards). They can only advance as the scan
1767 * itself advances through the index/key space.
1768 *
1769 * (The rules are the same for backwards scans, except that the operators are
1770 * flipped: just replace the precondition's >= operator with a <=, and the
1771 * postcondition's <= operator with a >=. In other words, just swap the
1772 * precondition with the postcondition.)
1773 *
1774 * We also deal with "advancing" non-required arrays here. Callers whose
1775 * sktrig scan key is non-required specify sktrig_required=false. These calls
1776 * are the only exception to the general rule about always advancing the
1777 * required array keys (the scan may not even have a required array). These
1778 * callers should just pass a NULL pstate (since there is never any question
1779 * of stopping the scan). No call to _bt_tuple_before_array_skeys is required
1780 * ahead of these calls (it's already clear that any required scan keys must
1781 * be satisfied by caller's tuple).
1782 *
1783 * Note that we deal with non-array required equality strategy scan keys as
1784 * degenerate single element arrays here. Obviously, they can never really
1785 * advance in the way that real arrays can, but they must still affect how we
1786 * advance real array scan keys (exactly like true array equality scan keys).
1787 * We have to keep around a 3-way ORDER proc for these (using the "=" operator
1788 * won't do), since in general whether the tuple is < or > _any_ unsatisfied
1789 * required equality key influences how the scan's real arrays must advance.
1790 *
1791 * Note also that we may sometimes need to advance the array keys when the
1792 * existing required array keys (and other required equality keys) are already
1793 * an exact match for every corresponding value from caller's tuple. We must
1794 * do this for inequalities that _bt_check_compare set continuescan=false for.
1795 * They'll advance the array keys here, just like any other scan key that
1796 * _bt_check_compare stops on. (This can even happen _after_ we advance the
1797 * array keys, in which case we'll advance the array keys a second time. That
1798 * way _bt_checkkeys caller always has its required arrays advance to the
1799 * maximum possible extent that its tuple will allow.)
1800 */
1801 static bool
1805 {
1817 {
1818 /*
1819 * Precondition array state assertion
1820 */
1826 /*
1827 * Required scan key wasn't satisfied, so required arrays will have to
1828 * advance. Invalidate page-level state that tracks whether the
1829 * scan's required-in-opposite-direction-only keys are known to be
1830 * satisfied by page's remaining tuples.
1831 */
1834 /* Shouldn't have to invalidate 'prechecked', though */
1837 /*
1838 * Once we return we'll have a new set of required array keys, so
1839 * reset state used by "look ahead" optimization
1840 */
1843 }
1848 {
1851 Datum tupdatum;
1854 tupnull;
1855 int32 result;
1859 {
1860 /* Manage array state */
1862 {
1865 }
1866 }
1867 else
1868 {
1869 /*
1870 * Are any inequalities required in the opposite direction only
1871 * present here?
1872 */
1877 has_required_opposite_direction_only =
1879 }
1881 /* Optimization: skip over known-satisfied scan keys */
1886 {
1892 {
1893 /* Set this just like _bt_tuple_before_array_skeys */
1896 }
1897 }
1899 /*
1900 * Handle a required non-array scan key that the initial call to
1901 * _bt_check_compare indicated triggered array advancement, if any.
1902 *
1903 * The non-array scan key's strategy will be <, <=, or = during a
1904 * forwards scan (or any one of =, >=, or > during a backwards scan).
1905 * It follows that the corresponding tuple attribute's value must now
1906 * be either > or >= the scan key value (for backwards scans it must
1907 * be either < or <= that value).
1908 *
1909 * If this is a required equality strategy scan key, this is just an
1910 * optimization; _bt_tuple_before_array_skeys already confirmed that
1911 * this scan key places us ahead of caller's tuple. There's no need
1912 * to repeat that work now. (The same underlying principle also gets
1913 * applied by the cur_elem_trig optimization used to speed up searches
1914 * for the next array element.)
1915 *
1916 * If this is a required inequality strategy scan key, we _must_ rely
1917 * on _bt_check_compare like this; we aren't capable of directly
1918 * evaluating required inequality strategy scan keys here, on our own.
1919 */
1921 {
1924 /* Use "beyond end" advancement. See below for an explanation. */
1928 /*
1929 * Set a flag that remembers that this was an inequality required
1930 * in the opposite scan direction only, that nevertheless
1931 * triggered the call here.
1932 *
1933 * This only happens when an inequality operator (which must be
1934 * strict) encounters a group of NULLs that indicate the end of
1935 * non-NULL values for tuples in the current scan direction.
1936 */
1941 }
1943 /*
1944 * Nothing more for us to do with an inequality strategy scan key that
1945 * wasn't the one that _bt_check_compare stopped on, though.
1946 *
1947 * Note: if our later call to _bt_check_compare (to recheck caller's
1948 * tuple) sets continuescan=false due to finding this same inequality
1949 * unsatisfied (possible when it's required in the scan direction),
1950 * we'll deal with it via a recursive "second pass" call.
1951 */
1955 /*
1956 * Nothing for us to do with an equality strategy scan key that isn't
1957 * marked required, either -- unless it's a non-required array
1958 */
1962 /*
1963 * Here we perform steps for all array scan keys after a required
1964 * array scan key whose binary search triggered "beyond end of array
1965 * element" array advancement due to encountering a tuple attribute
1966 * value > the closest matching array key (or < for backwards scans).
1967 */
1969 {
1974 else
1978 {
1981 }
1984 }
1986 /*
1987 * Here we perform steps for all array scan keys after a required
1988 * array scan key whose tuple attribute was < the closest matching
1989 * array key when we dealt with it (or > for backwards scans).
1990 *
1991 * This earlier required array key already puts us ahead of caller's
1992 * tuple in the key space (for the current scan direction). We must
1993 * make sure that subsequent lower-order array keys do not put us too
1994 * far ahead (ahead of tuples that have yet to be seen by our caller).
1995 * For example, when a tuple "(a, b) = (42, 5)" advances the array
1996 * keys on "a" from 40 to 45, we must also set "b" to whatever the
1997 * first array element for "b" is. It would be wrong to allow "b" to
1998 * be set based on the tuple value.
1999 *
2000 * Perform the same steps with truncated high key attributes. You can
2001 * think of this as a "binary search" for the element closest to the
2002 * value -inf. Again, the arrays must never get ahead of the scan.
2003 */
2005 {
2010 else
2014 {
2017 }
2020 }
2022 /*
2023 * Search in scankey's array for the corresponding tuple attribute
2024 * value from caller's tuple
2025 */
2029 {
2032 /*
2033 * Binary search for closest match that's available from the array
2034 */
2041 }
2042 else
2043 {
2046 /*
2047 * This is a required non-array equality strategy scan key, which
2048 * we'll treat as a degenerate single element array.
2049 *
2050 * This scan key's imaginary "array" can't really advance, but it
2051 * can still roll over like any other array. (Actually, this is
2052 * no different to real single value arrays, which never advance
2053 * without rolling over -- they can never truly advance, either.)
2054 */
2058 }
2060 /*
2061 * Consider "beyond end of array element" array advancement.
2062 *
2063 * When the tuple attribute value is > the closest matching array key
2064 * (or < in the backwards scan case), we need to ratchet this array
2065 * forward (backward) by one increment, so that caller's tuple ends up
2066 * being < final array value instead (or > final array value instead).
2067 * This process has to work for all of the arrays, not just this one:
2068 * it must "carry" to higher-order arrays when the set_elem that we
2069 * just found happens to be the final one for the scan's direction.
2070 * Incrementing (decrementing) set_elem itself isn't good enough.
2071 *
2072 * Our approach is to provisionally use set_elem as if it was an exact
2073 * match now, then set each later/less significant array to whatever
2074 * its final element is. Once outside the loop we'll then "increment
2075 * this array's set_elem" by calling _bt_advance_array_keys_increment.
2076 * That way the process rolls over to higher order arrays as needed.
2077 *
2078 * Under this scheme any required arrays only ever ratchet forwards
2079 * (or backwards), and always do so to the maximum possible extent
2080 * that we can know will be safe without seeing the scan's next tuple.
2081 * We don't need any special handling for required scan keys that lack
2082 * a real array to advance, nor for redundant scan keys that couldn't
2083 * be eliminated by _bt_preprocess_keys. It won't matter if some of
2084 * our "true" array scan keys (or even all of them) are non-required.
2085 */
2093 {
2094 /*
2095 * Track whether caller's tuple satisfies our new post-advancement
2096 * qual, for required scan keys, as well as for the entire set of
2097 * interesting scan keys (all required scan keys plus non-required
2098 * array scan keys are considered interesting.)
2099 */
2103 else
2104 {
2105 /*
2106 * There's no need to advance the arrays using the best
2107 * available match for a non-required array. Give up now.
2108 * (Though note that sktrig_required calls still have to do
2109 * all the usual post-advancement steps, including the recheck
2110 * call to _bt_check_compare.)
2111 */
2113 }
2114 }
2116 /* Advance array keys, even when set_elem isn't an exact match */
2118 {
2121 }
2122 }
2124 /*
2125 * Advance the array keys incrementally whenever "beyond end of array
2126 * element" array advancement happens, so that advancement will carry to
2127 * higher-order arrays (might exhaust all the scan's arrays instead, which
2128 * ends the top-level scan).
2129 */
2135 /*
2136 * Does tuple now satisfy our new qual? Recheck with _bt_check_compare.
2137 *
2138 * Calls triggered by an unsatisfied required scan key, whose tuple now
2139 * satisfies all required scan keys, but not all nonrequired array keys,
2140 * will still require a recheck call to _bt_check_compare. They'll still
2141 * need its "second pass" handling of required inequality scan keys.
2142 * (Might have missed a still-unsatisfied required inequality scan key
2143 * that caller didn't detect as the sktrig scan key during its initial
2144 * _bt_check_compare call that used the old/original qual.)
2145 *
2146 * Calls triggered by an unsatisfied nonrequired array scan key never need
2147 * "second pass" handling of required inequalities (nor any other handling
2148 * of any required scan key). All that matters is whether caller's tuple
2149 * satisfies the new qual, so it's safe to just skip the _bt_check_compare
2150 * recheck when we've already determined that it can only return 'false'.
2151 */
2154 {
2160 /* Recheck _bt_check_compare on behalf of caller */
2165 {
2166 /* This tuple satisfies the new qual */
2173 }
2175 /*
2176 * Consider "second pass" handling of required inequalities.
2177 *
2178 * It's possible that our _bt_check_compare call indicated that the
2179 * scan should end due to some unsatisfied inequality that wasn't
2180 * initially recognized as such by us. Handle this by calling
2181 * ourselves recursively, this time indicating that the trigger is the
2182 * inequality that we missed first time around (and using a set of
2183 * required array/equality keys that are now exact matches for tuple).
2184 *
2185 * We make a strong, general guarantee that every _bt_checkkeys call
2186 * here will advance the array keys to the maximum possible extent
2187 * that we can know to be safe based on caller's tuple alone. If we
2188 * didn't perform this step, then that guarantee wouldn't quite hold.
2189 */
2191 {
2197 /*
2198 * The tuple must use "beyond end" advancement during the
2199 * recursive call, so we cannot possibly end up back here when
2200 * recursing. We'll consume a small, fixed amount of stack space.
2201 */
2204 /* Advance the array keys a second time using same tuple */
2208 /* This tuple doesn't satisfy the inequality */
2211 }
2213 /*
2214 * Some non-required scan key (from new qual) still not satisfied.
2215 *
2216 * All scan keys required in the current scan direction must still be
2217 * satisfied, though, so we can trust all_required_satisfied below.
2218 */
2219 }
2221 /*
2222 * When we were called just to deal with "advancing" non-required arrays,
2223 * this is as far as we can go (cannot stop the scan for these callers)
2224 */
2226 {
2227 /* Caller's tuple doesn't match any qual */
2229 }
2231 /*
2232 * Postcondition array state assertion (for still-unsatisfied tuples).
2233 *
2234 * By here we have established that the scan's required arrays (scan must
2235 * have at least one required array) advanced, without becoming exhausted.
2236 *
2237 * Caller's tuple is now < the newly advanced array keys (or > when this
2238 * is a backwards scan), except in the case where we only got this far due
2239 * to an unsatisfied non-required scan key. Verify that with an assert.
2240 *
2241 * Note: we don't just quit at this point when all required scan keys were
2242 * found to be satisfied because we need to consider edge-cases involving
2243 * scan keys required in the opposite direction only; those aren't tracked
2244 * by all_required_satisfied. (Actually, oppodir_inequality_sktrig trigger
2245 * scan keys are tracked by all_required_satisfied, since it's convenient
2246 * for _bt_check_compare to behave as if they are required in the current
2247 * scan direction to deal with NULLs. We'll account for that separately.)
2248 */
2253 /*
2254 * We generally permit primitive index scans to continue onto the next
2255 * sibling page when the page's finaltup satisfies all required scan keys
2256 * at the point where we're between pages.
2257 *
2258 * If caller's tuple is also the page's finaltup, and we see that required
2259 * scan keys still aren't satisfied, start a new primitive index scan.
2260 */
2264 /*
2265 * Proactively check finaltup (don't wait until finaltup is reached by the
2266 * scan) when it might well turn out to not be satisfied later on.
2267 *
2268 * Note: if so->scanBehind hasn't already been set for finaltup by us,
2269 * it'll be set during this call to _bt_tuple_before_array_skeys. Either
2270 * way, it'll be set correctly (for the whole page) after this point.
2271 */
2278 /*
2279 * When we encounter a truncated finaltup high key attribute, we're
2280 * optimistic about the chances of its corresponding required scan key
2281 * being satisfied when we go on to check it against tuples from this
2282 * page's right sibling leaf page. We consider truncated attributes to be
2283 * satisfied by required scan keys, which allows the primitive index scan
2284 * to continue to the next leaf page. We must set so->scanBehind to true
2285 * to remember that the last page's finaltup had "satisfied" required scan
2286 * keys for one or more truncated attribute values (scan keys required in
2287 * _either_ scan direction).
2288 *
2289 * There is a chance that _bt_checkkeys (which checks so->scanBehind) will
2290 * find that even the sibling leaf page's finaltup is < the new array
2291 * keys. When that happens, our optimistic policy will have incurred a
2292 * single extra leaf page access that could have been avoided.
2293 *
2294 * A pessimistic policy would give backward scans a gratuitous advantage
2295 * over forward scans. We'd punish forward scans for applying more
2296 * accurate information from the high key, rather than just using the
2297 * final non-pivot tuple as finaltup, in the style of backward scans.
2298 * Being pessimistic would also give some scans with non-required arrays a
2299 * perverse advantage over similar scans that use required arrays instead.
2300 *
2301 * You can think of this as a speculative bet on what the scan is likely
2302 * to find on the next page. It's not much of a gamble, though, since the
2303 * untruncated prefix of attributes must strictly satisfy the new qual
2304 * (though it's okay if any non-required scan keys fail to be satisfied).
2305 */
2307 {
2308 /*
2309 * However, we need to work harder whenever the scan involves a scan
2310 * key required in the opposite direction to the scan only, along with
2311 * a finaltup with at least one truncated attribute that's associated
2312 * with a scan key marked required (required in either direction).
2313 *
2314 * _bt_check_compare simply won't stop the scan for a scan key that's
2315 * marked required in the opposite scan direction only. That leaves
2316 * us without an automatic way of reconsidering any opposite-direction
2317 * inequalities if it turns out that starting a new primitive index
2318 * scan will allow _bt_first to skip ahead by a great many leaf pages.
2319 *
2320 * We deal with this by explicitly scheduling a finaltup recheck on
2321 * the right sibling page. _bt_readpage calls _bt_oppodir_checkkeys
2322 * for next page's finaltup (and we skip it for this page's finaltup).
2323 */
2325 }
2327 /*
2328 * Handle inequalities marked required in the opposite scan direction.
2329 * They can also signal that we should start a new primitive index scan.
2330 *
2331 * It's possible that the scan is now positioned where "matching" tuples
2332 * begin, and that caller's tuple satisfies all scan keys required in the
2333 * current scan direction. But if caller's tuple still doesn't satisfy
2334 * other scan keys that are required in the opposite scan direction only
2335 * (e.g., a required >= strategy scan key when scan direction is forward),
2336 * it's still possible that there are many leaf pages before the page that
2337 * _bt_first could skip straight to. Groveling through all those pages
2338 * will always give correct answers, but it can be very inefficient. We
2339 * must avoid needlessly scanning extra pages.
2340 *
2341 * Separately, it's possible that _bt_check_compare set continuescan=false
2342 * for a scan key that's required in the opposite direction only. This is
2343 * a special case, that happens only when _bt_check_compare sees that the
2344 * inequality encountered a NULL value. This signals the end of non-NULL
2345 * values in the current scan direction, which is reason enough to end the
2346 * (primitive) scan. If this happens at the start of a large group of
2347 * NULL values, then we shouldn't expect to be called again until after
2348 * the scan has already read indefinitely-many leaf pages full of tuples
2349 * with NULL suffix values. We need a separate test for this case so that
2350 * we don't miss our only opportunity to skip over such a group of pages.
2351 * (_bt_first is expected to skip over the group of NULLs by applying a
2352 * similar "deduce NOT NULL" rule, where it finishes its insertion scan
2353 * key by consing up an explicit SK_SEARCHNOTNULL key.)
2354 *
2355 * Apply a test against finaltup to detect and recover from the problem:
2356 * if even finaltup doesn't satisfy such an inequality, we just skip by
2357 * starting a new primitive index scan. When we skip, we know for sure
2358 * that all of the tuples on the current page following caller's tuple are
2359 * also before the _bt_first-wise start of tuples for our new qual. That
2360 * at least suggests many more skippable pages beyond the current page.
2361 * (when so->oppositeDirCheck was set, this'll happen on the next page.)
2362 */
2366 {
2367 /*
2368 * Make sure that any non-required arrays are set to the first array
2369 * element for the current scan direction
2370 */
2373 }
2375 /*
2376 * Stick with the ongoing primitive index scan for now.
2377 *
2378 * It's possible that later tuples will also turn out to have values that
2379 * are still < the now-current array keys (or > the current array keys).
2380 * Our caller will handle this by performing what amounts to a linear
2381 * search of the page, implemented by calling _bt_check_compare and then
2382 * _bt_tuple_before_array_skeys for each tuple.
2383 *
2384 * This approach has various advantages over a binary search of the page.
2385 * Repeated binary searches of the page (one binary search for every array
2386 * advancement) won't outperform a continuous linear search. While there
2387 * are workloads that a naive linear search won't handle well, our caller
2388 * has a "look ahead" fallback mechanism to deal with that problem.
2389 */
2394 {
2395 /* Optimization: skip by setting "look ahead" mechanism's offnum */
2398 }
2400 /* Caller's tuple doesn't match the new qual */
2403 new_prim_scan:
2407 /*
2408 * End this primitive index scan, but schedule another.
2409 *
2410 * Note: We make a soft assumption that the current scan direction will
2411 * also be used within _bt_next, when it is asked to step off this page.
2412 * It is up to _bt_next to cancel this scheduled primitive index scan
2413 * whenever it steps to a page in the direction opposite currPos.dir.
2414 */
2421 /* Caller's tuple doesn't match the new qual */
2424 end_toplevel_scan:
2426 /*
2427 * End the current primitive index scan, but don't schedule another.
2428 *
2429 * This ends the entire top-level scan in the current scan direction.
2430 *
2431 * Note: The scan's arrays (including any non-required arrays) are now in
2432 * their final positions for the current scan direction. If the scan
2433 * direction happens to change, then the arrays will already be in their
2434 * first positions for what will then be the current scan direction.
2435 */
2439 /* Caller's tuple doesn't match any qual */
2441 }
2443 /*
2444 * _bt_preprocess_keys() -- Preprocess scan keys
2445 *
2446 * The given search-type keys (taken from scan->keyData[])
2447 * are copied to so->keyData[] with possible transformation.
2448 * scan->numberOfKeys is the number of input keys, so->numberOfKeys gets
2449 * the number of output keys. Calling here a second or subsequent time
2450 * (during the same btrescan) is a no-op.
2451 *
2452 * The output keys are marked with additional sk_flags bits beyond the
2453 * system-standard bits supplied by the caller. The DESC and NULLS_FIRST
2454 * indoption bits for the relevant index attribute are copied into the flags.
2455 * Also, for a DESC column, we commute (flip) all the sk_strategy numbers
2456 * so that the index sorts in the desired direction.
2457 *
2458 * One key purpose of this routine is to discover which scan keys must be
2459 * satisfied to continue the scan. It also attempts to eliminate redundant
2460 * keys and detect contradictory keys. (If the index opfamily provides
2461 * incomplete sets of cross-type operators, we may fail to detect redundant
2462 * or contradictory keys, but we can survive that.)
2463 *
2464 * The output keys must be sorted by index attribute. Presently we expect
2465 * (but verify) that the input keys are already so sorted --- this is done
2466 * by match_clauses_to_index() in indxpath.c. Some reordering of the keys
2467 * within each attribute may be done as a byproduct of the processing here.
2468 * That process must leave array scan keys (within an attribute) in the same
2469 * order as corresponding entries from the scan's BTArrayKeyInfo array info.
2470 *
2471 * The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD
2472 * if they must be satisfied in order to continue the scan forward or backward
2473 * respectively. _bt_checkkeys uses these flags. For example, if the quals
2474 * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
2475 * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
2476 * But once we reach tuples like (1,4,z) we can stop scanning because no
2477 * later tuples could match. This is reflected by marking the x and y keys,
2478 * but not the z key, with SK_BT_REQFWD. In general, the keys for leading
2479 * attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD.
2480 * For the first attribute without an "=" key, any "<" and "<=" keys are
2481 * marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD.
2482 * This can be seen to be correct by considering the above example. Note
2483 * in particular that if there are no keys for a given attribute, the keys for
2484 * subsequent attributes can never be required; for instance "WHERE y = 4"
2485 * requires a full-index scan.
2486 *
2487 * If possible, redundant keys are eliminated: we keep only the tightest
2488 * >/>= bound and the tightest </<= bound, and if there's an = key then
2489 * that's the only one returned. (So, we return either a single = key,
2490 * or one or two boundary-condition keys for each attr.) However, if we
2491 * cannot compare two keys for lack of a suitable cross-type operator,
2492 * we cannot eliminate either. If there are two such keys of the same
2493 * operator strategy, the second one is just pushed into the output array
2494 * without further processing here. We may also emit both >/>= or both
2495 * </<= keys if we can't compare them. The logic about required keys still
2496 * works if we don't eliminate redundant keys.
2497 *
2498 * Note that one reason we need direction-sensitive required-key flags is
2499 * precisely that we may not be able to eliminate redundant keys. Suppose
2500 * we have "x > 4::int AND x > 10::bigint", and we are unable to determine
2501 * which key is more restrictive for lack of a suitable cross-type operator.
2502 * _bt_first will arbitrarily pick one of the keys to do the initial
2503 * positioning with. If it picks x > 4, then the x > 10 condition will fail
2504 * until we reach index entries > 10; but we can't stop the scan just because
2505 * x > 10 is failing. On the other hand, if we are scanning backwards, then
2506 * failure of either key is indeed enough to stop the scan. (In general, when
2507 * inequality keys are present, the initial-positioning code only promises to
2508 * position before the first possible match, not exactly at the first match,
2509 * for a forward scan; or after the last match for a backward scan.)
2510 *
2511 * As a byproduct of this work, we can detect contradictory quals such
2512 * as "x = 1 AND x > 2". If we see that, we return so->qual_ok = false,
2513 * indicating the scan need not be run at all since no tuples can match.
2514 * (In this case we do not bother completing the output key array!)
2515 * Again, missing cross-type operators might cause us to fail to prove the
2516 * quals contradictory when they really are, but the scan will work correctly.
2517 *
2518 * Row comparison keys are currently also treated without any smarts:
2519 * we just transfer them into the preprocessed array without any
2520 * editorialization. We can treat them the same as an ordinary inequality
2521 * comparison on the row's first index column, for the purposes of the logic
2522 * about required keys.
2523 *
2524 * Note: the reason we have to copy the preprocessed scan keys into private
2525 * storage is that we are modifying the array based on comparisons of the
2526 * key argument values, which could change on a rescan. Therefore we can't
2527 * overwrite the source data.
2528 */
2529 void
2531 {
2537 ScanKey inkeys;
2540 AttrNumber attno;
2541 ScanKey arrayKeyData;
2546 {
2547 /*
2548 * Only need to do preprocessing once per btrescan, at most. All
2549 * calls after the first are handled as no-ops.
2550 *
2551 * If there are array scan keys in so->keyData[], then the now-current
2552 * array elements must already be present in each array's scan key.
2553 * Verify that that happened using an assertion.
2554 */
2557 }
2559 /* initialize result variables */
2566 /* If any keys are SK_SEARCHARRAY type, set up array-key info */
2569 {
2570 /* unmatchable array, so give up */
2572 }
2574 /*
2575 * Treat arrayKeyData[] (a partially preprocessed copy of scan->keyData[])
2576 * as our input if _bt_preprocess_array_keys just allocated it, else just
2577 * use scan->keyData[]
2578 */
2580 {
2583 /* Also maintain keyDataMap for remapping so->orderProc[] later */
2586 }
2587 else
2590 /* we check that input keys are correctly ordered */
2594 /* We can short-circuit most of the work if there's just one key */
2596 {
2597 /* Apply indoption to scankey (might change sk_strategy!) */
2602 /* We can mark the qual as required if it's for first index col */
2606 {
2607 /*
2608 * Don't call _bt_preprocess_array_keys_final in this fast path
2609 * (we'll miss out on the single value array transformation, but
2610 * that's not nearly as important when there's only one scan key)
2611 */
2616 }
2619 }
2621 /*
2622 * Otherwise, do the full set of pushups.
2623 */
2627 /*
2628 * Initialize for processing of keys for attr 1.
2629 *
2630 * xform[i] points to the currently best scan key of strategy type i+1; it
2631 * is NULL if we haven't yet found such a key for this attr.
2632 */
2636 /*
2637 * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to
2638 * handle after-last-key processing. Actual exit from the loop is at the
2639 * "break" statement below.
2640 */
2642 {
2647 {
2648 /* Apply indoption to scankey (might change sk_strategy!) */
2650 {
2651 /* NULL can't be matched, so give up */
2654 }
2655 }
2657 /*
2658 * If we are at the end of the keys for a particular attr, finish up
2659 * processing and emit the cleaned-up keys.
2660 */
2662 {
2665 /* check input keys are correctly ordered */
2669 /*
2670 * If = has been specified, all other keys can be eliminated as
2671 * redundant. If we have a case like key = 1 AND key > 2, we can
2672 * set qual_ok to false and abandon further processing.
2673 *
2674 * We also have to deal with the case of "key IS NULL", which is
2675 * unsatisfiable in combination with any other index condition. By
2676 * the time we get here, that's been classified as an equality
2677 * check, and we've rejected any combination of it with a regular
2678 * equality condition; but not with other types of conditions.
2679 */
2681 {
2687 {
2689 eq_arrayidx;
2698 }
2701 {
2708 {
2709 /* IS NULL is contradictory to anything else */
2712 }
2717 {
2719 {
2720 /* keys proven mutually contradictory */
2723 }
2724 /* else discard the redundant non-equality key */
2728 }
2729 /* else, cannot determine redundancy, keep both keys */
2730 }
2731 /* track number of attrs for which we have "=" keys */
2732 numberOfEqualCols++;
2733 }
2735 /* try to keep only one of <, <= */
2738 {
2744 {
2747 else
2749 }
2750 }
2752 /* try to keep only one of >, >= */
2755 {
2761 {
2764 else
2766 }
2767 }
2769 /*
2770 * Emit the cleaned-up keys into the so->keyData[] array, and then
2771 * mark them if they are required. They are required (possibly
2772 * only in one direction) if all attrs before this one had "=".
2773 */
2775 {
2777 {
2785 }
2786 }
2788 /*
2789 * Exit loop here if done.
2790 */
2794 /* Re-initialize for new attno */
2797 }
2799 /* check strategy this key's operator corresponds to */
2802 /* if row comparison, push it directly to the output array */
2804 {
2813 /*
2814 * We don't support RowCompare using equality; such a qual would
2815 * mess up the numberOfEqualCols tracking.
2816 */
2819 }
2823 {
2824 /* must track how input scan keys map to arrays */
2826 arrayidx++;
2827 }
2829 /*
2830 * have we seen a scan key for this same attribute and using this same
2831 * operator strategy before now?
2832 */
2834 {
2835 /* nope, so this scan key wins by default (at least for now) */
2839 }
2840 else
2841 {
2845 /*
2846 * Seen one of these before, so keep only the more restrictive key
2847 * if possible
2848 */
2850 {
2851 /*
2852 * Have to set up array keys
2853 */
2855 {
2861 }
2863 {
2869 }
2871 /*
2872 * Both scan keys might have arrays, in which case we'll
2873 * arbitrarily pass only one of the arrays. That won't
2874 * matter, since _bt_compare_scankey_args is aware that two
2875 * SEARCHARRAY scan keys mean that _bt_preprocess_array_keys
2876 * failed to eliminate redundant arrays through array merging.
2877 * _bt_compare_scankey_args just returns false when it sees
2878 * this; it won't even try to examine either array.
2879 */
2880 }
2884 {
2885 /* Have all we need to determine redundancy */
2887 {
2890 /*
2891 * New key is more restrictive, and so replaces old key...
2892 */
2895 {
2899 }
2900 else
2901 {
2902 /*
2903 * ...unless we have to keep the old key because it's
2904 * an array that rendered the new key redundant. We
2905 * need to make sure that we don't throw away an array
2906 * scan key. _bt_preprocess_array_keys_final expects
2907 * us to keep all of the arrays that weren't already
2908 * eliminated by _bt_preprocess_array_keys earlier on.
2909 */
2911 }
2912 }
2914 {
2915 /* key == a && key == b, but a != b */
2918 }
2919 /* else old key is more restrictive, keep it */
2920 }
2921 else
2922 {
2923 /*
2924 * We can't determine which key is more restrictive. Push
2925 * xform[j] directly to the output array, then set xform[j] to
2926 * the new scan key.
2927 *
2928 * Note: We do things this way around so that our arrays are
2929 * always in the same order as their corresponding scan keys,
2930 * even with incomplete opfamilies. _bt_advance_array_keys
2931 * depends on this.
2932 */
2943 }
2944 }
2945 }
2949 /*
2950 * Now that we've built a temporary mapping from so->keyData[] (output
2951 * scan keys) to arrayKeyData[] (our input scan keys), fix array->scan_key
2952 * references. Also consolidate the so->orderProcs[] array such that it
2953 * can be subscripted using so->keyData[]-wise offsets.
2954 */
2958 /* Could pfree arrayKeyData/keyDataMap now, but not worth the cycles */
2959 }
2961 #ifdef USE_ASSERT_CHECKING
2962 /*
2963 * Verify that the scan's qual state matches what we expect at the point that
2964 * _bt_start_prim_scan is about to start a just-scheduled new primitive scan.
2965 *
2966 * We enforce a rule against non-required array scan keys: they must start out
2967 * with whatever element is the first for the scan's current scan direction.
2968 * See _bt_rewind_nonrequired_arrays comments for an explanation.
2969 */
2970 static bool
2972 {
2977 {
2994 else
2999 }
3002 }
3004 /*
3005 * Verify that the scan's "so->keyData[]" scan keys are in agreement with
3006 * its array key state
3007 */
3008 static bool
3010 {
3019 {
3039 }
3045 }
3046 #endif
3048 /*
3049 * Compare two scankey values using a specified operator.
3050 *
3051 * The test we want to perform is logically "leftarg op rightarg", where
3052 * leftarg and rightarg are the sk_argument values in those ScanKeys, and
3053 * the comparison operator is the one in the op ScanKey. However, in
3054 * cross-data-type situations we may need to look up the correct operator in
3055 * the index's opfamily: it is the one having amopstrategy = op->sk_strategy
3056 * and amoplefttype/amoprighttype equal to the two argument datatypes.
3057 *
3058 * If the opfamily doesn't supply a complete set of cross-type operators we
3059 * may not be able to make the comparison. If we can make the comparison
3060 * we store the operator result in *result and return true. We return false
3061 * if the comparison could not be made.
3062 *
3063 * If either leftarg or rightarg are an array, we'll apply array-specific
3064 * rules to determine which array elements are redundant on behalf of caller.
3065 * It is up to our caller to save whichever of the two scan keys is the array,
3066 * and discard the non-array scan key (the non-array scan key is guaranteed to
3067 * be redundant with any complete opfamily). Caller isn't expected to call
3068 * here with a pair of array scan keys provided we're dealing with a complete
3069 * opfamily (_bt_preprocess_array_keys will merge array keys together to make
3070 * sure of that).
3071 *
3072 * Note: we'll also shrink caller's array as needed to eliminate redundant
3073 * array elements. One reason why caller should prefer to discard non-array
3074 * scan keys is so that we'll have the opportunity to shrink the array
3075 * multiple times, in multiple calls (for each of several other scan keys on
3076 * the same index attribute).
3077 *
3078 * Note: op always points at the same ScanKey as either leftarg or rightarg.
3079 * Since we don't scribble on the scankeys themselves, this aliasing should
3080 * cause no trouble.
3081 *
3082 * Note: this routine needs to be insensitive to any DESC option applied
3083 * to the index column. For example, "x < 4" is a tighter constraint than
3084 * "x < 5" regardless of which way the index is sorted.
3085 */
3086 static bool
3091 {
3093 Oid lefttype,
3094 righttype,
3095 optype,
3096 opcintype,
3097 cmp_op;
3098 StrategyNumber strat;
3100 /*
3101 * First, deal with cases where one or both args are NULL. This should
3102 * only happen when the scankeys represent IS NULL/NOT NULL conditions.
3103 */
3105 {
3107 rightnull;
3110 {
3113 }
3114 else
3117 {
3120 }
3121 else
3124 /*
3125 * We treat NULL as either greater than or less than all other values.
3126 * Since true > false, the tests below work correctly for NULLS LAST
3127 * logic. If the index is NULLS FIRST, we need to flip the strategy.
3128 */
3134 {
3154 }
3156 }
3158 /*
3159 * If either leftarg or rightarg are equality-type array scankeys, we need
3160 * specialized handling (since by now we know that IS NULL wasn't used)
3161 */
3163 {
3165 rightarray;
3172 /*
3173 * _bt_preprocess_array_keys is responsible for merging together array
3174 * scan keys, and will do so whenever the opfamily has the required
3175 * cross-type support. If it failed to do that, we handle it just
3176 * like the case where we can't make the comparison ourselves.
3177 */
3179 {
3180 /* Can't make the comparison */
3183 }
3185 /*
3186 * Otherwise we need to determine if either one of leftarg or rightarg
3187 * uses an array, then pass this through to a dedicated helper
3188 * function.
3189 */
3197 /* FALL THRU */
3198 }
3200 /*
3201 * The opfamily we need to worry about is identified by the index column.
3202 */
3207 /*
3208 * Determine the actual datatypes of the ScanKey arguments. We have to
3209 * support the convention that sk_subtype == InvalidOid means the opclass
3210 * input type; this is a hack to simplify life for ScanKeyInit().
3211 */
3222 /*
3223 * If leftarg and rightarg match the types expected for the "op" scankey,
3224 * we can use its already-looked-up comparison function.
3225 */
3227 {
3233 }
3235 /*
3236 * Otherwise, we need to go to the syscache to find the appropriate
3237 * operator. (This cannot result in infinite recursion, since no
3238 * indexscan initiated by syscache lookup will use cross-data-type
3239 * operators.)
3240 *
3241 * If the sk_strategy was flipped by _bt_fix_scankey_strategy, we have to
3242 * un-flip it to get the correct opfamily member.
3243 */
3249 lefttype,
3250 righttype,
3251 strat);
3253 {
3257 {
3263 }
3264 }
3266 /* Can't make the comparison */
3269 }
3271 /*
3272 * Adjust a scankey's strategy and flags setting as needed for indoptions.
3273 *
3274 * We copy the appropriate indoption value into the scankey sk_flags
3275 * (shifting to avoid clobbering system-defined flag bits). Also, if
3276 * the DESC option is set, commute (flip) the operator strategy number.
3277 *
3278 * A secondary purpose is to check for IS NULL/NOT NULL scankeys and set up
3279 * the strategy field correctly for them.
3280 *
3281 * Lastly, for ordinary scankeys (not IS NULL/NOT NULL), we check for a
3282 * NULL comparison value. Since all btree operators are assumed strict,
3283 * a NULL means that the qual cannot be satisfied. We return true if the
3284 * comparison value isn't NULL, or false if the scan should be abandoned.
3285 *
3286 * This function is applied to the *input* scankey structure; therefore
3287 * on a rescan we will be looking at already-processed scankeys. Hence
3288 * we have to be careful not to re-commute the strategy if we already did it.
3289 * It's a bit ugly to modify the caller's copy of the scankey but in practice
3290 * there shouldn't be any problem, since the index's indoptions are certainly
3291 * not going to change while the scankey survives.
3292 */
3293 static bool
3295 {
3300 /*
3301 * We treat all btree operators as strict (even if they're not so marked
3302 * in pg_proc). This means that it is impossible for an operator condition
3303 * with a NULL comparison constant to succeed, and we can reject it right
3304 * away.
3305 *
3306 * However, we now also support "x IS NULL" clauses as search conditions,
3307 * so in that case keep going. The planner has not filled in any
3308 * particular strategy in this case, so set it to BTEqualStrategyNumber
3309 * --- we can treat IS NULL as an equality operator for purposes of search
3310 * strategy.
3311 *
3312 * Likewise, "x IS NOT NULL" is supported. We treat that as either "less
3313 * than NULL" in a NULLS LAST index, or "greater than NULL" in a NULLS
3314 * FIRST index.
3315 *
3316 * Note: someday we might have to fill in sk_collation from the index
3317 * column's collation. At the moment this is a non-issue because we'll
3318 * never actually call the comparison operator on a NULL.
3319 */
3321 {
3322 /* SK_ISNULL shouldn't be set in a row header scankey */
3325 /* Set indoption flags in scankey (might be done already) */
3328 /* Set correct strategy for IS NULL or NOT NULL search */
3330 {
3334 }
3336 {
3339 else
3343 }
3344 else
3345 {
3346 /* regular qual, so it cannot be satisfied */
3348 }
3350 /* Needn't do the rest */
3352 }
3354 /* Adjust strategy for DESC, if we didn't already */
3359 /* If it's a row header, fix row member flags and strategies similarly */
3361 {
3365 {
3373 subkey++;
3374 }
3375 }
3378 }
3380 /*
3381 * Mark a scankey as "required to continue the scan".
3382 *
3383 * Depending on the operator type, the key may be required for both scan
3384 * directions or just one. Also, if the key is a row comparison header,
3385 * we have to mark its first subsidiary ScanKey as required. (Subsequent
3386 * subsidiary ScanKeys are normally for lower-order columns, and thus
3387 * cannot be required, since they're after the first non-equality scankey.)
3388 *
3389 * Note: when we set required-key flag bits in a subsidiary scankey, we are
3390 * scribbling on a data structure belonging to the index AM's caller, not on
3391 * our private copy. This should be OK because the marking will not change
3392 * from scan to scan within a query, and so we'd just re-mark the same way
3393 * anyway on a rescan. Something to keep an eye on though.
3394 */
3395 static void
3397 {
3401 {
3418 }
3423 {
3426 /* First subkey should be same column/operator as the header */
3431 }
3432 }
3434 /*
3435 * Test whether an indextuple satisfies all the scankey conditions.
3436 *
3437 * Return true if so, false if not. If the tuple fails to pass the qual,
3438 * we also determine whether there's any need to continue the scan beyond
3439 * this tuple, and set pstate.continuescan accordingly. See comments for
3440 * _bt_preprocess_keys(), above, about how this is done.
3441 *
3442 * Forward scan callers can pass a high key tuple in the hopes of having
3443 * us set *continuescan to false, and avoiding an unnecessary visit to
3444 * the page to the right.
3445 *
3446 * Advances the scan's array keys when necessary for arrayKeys=true callers.
3447 * Caller can avoid all array related side-effects when calling just to do a
3448 * page continuescan precheck -- pass arrayKeys=false for that. Scans without
3449 * any arrays keys must always pass arrayKeys=false.
3450 *
3451 * Also stops and starts primitive index scans for arrayKeys=true callers.
3452 * Scans with array keys are required to set up page state that helps us with
3453 * this. The page's finaltup tuple (the page high key for a forward scan, or
3454 * the page's first non-pivot tuple for a backward scan) must be set in
3455 * pstate.finaltup ahead of the first call here for the page (or possibly the
3456 * first call after an initial continuescan-setting page precheck call). Set
3457 * this to NULL for rightmost page (or the leftmost page for backwards scans).
3458 *
3459 * scan: index scan descriptor (containing a search-type scankey)
3460 * pstate: page level input and output parameters
3461 * arrayKeys: should we advance the scan's array keys if necessary?
3462 * tuple: index tuple to test
3463 * tupnatts: number of attributes in tupnatts (high key may be truncated)
3464 */
3465 bool
3468 {
3481 #ifdef USE_ASSERT_CHECKING
3483 {
3484 /*
3485 * This is a continuescan precheck call for a scan with array keys.
3486 *
3487 * Assert that the scan isn't in danger of becoming confused.
3488 */
3493 }
3495 {
3499 /*
3500 * Call relied on continuescan/firstmatch prechecks -- assert that we
3501 * get the same answer without those optimizations
3502 */
3507 }
3508 #endif
3510 /*
3511 * Only one _bt_check_compare call is required in the common case where
3512 * there are no equality strategy array scan keys. Otherwise we can only
3513 * accept _bt_check_compare's answer unreservedly when it didn't set
3514 * pstate.continuescan=false.
3515 */
3519 /*
3520 * _bt_check_compare call set continuescan=false in the presence of
3521 * equality type array keys. This could mean that the tuple is just past
3522 * the end of matches for the current array keys.
3523 *
3524 * It's also possible that the scan is still _before_ the _start_ of
3525 * tuples matching the current set of array keys. Check for that first.
3526 */
3529 {
3530 /*
3531 * Tuple is still before the start of matches according to the scan's
3532 * required array keys (according to _all_ of its required equality
3533 * strategy keys, actually).
3534 *
3535 * _bt_advance_array_keys occasionally sets so->scanBehind to signal
3536 * that the scan's current position/tuples might be significantly
3537 * behind (multiple pages behind) its current array keys. When this
3538 * happens, we need to be prepared to recover by starting a new
3539 * primitive index scan here, on our own.
3540 */
3548 {
3549 /* Cut our losses -- start a new primitive index scan now */
3552 }
3553 else
3554 {
3555 /* Override _bt_check_compare, continue primitive scan */
3558 /*
3559 * We will end up here repeatedly given a group of tuples > the
3560 * previous array keys and < the now-current keys (for a backwards
3561 * scan it's just the same, though the operators swap positions).
3562 *
3563 * We must avoid allowing this linear search process to scan very
3564 * many tuples from well before the start of tuples matching the
3565 * current array keys (or from well before the point where we'll
3566 * once again have to advance the scan's array keys).
3567 *
3568 * We keep the overhead under control by speculatively "looking
3569 * ahead" to later still-unscanned items from this same leaf page.
3570 * We'll only attempt this once the number of tuples that the
3571 * linear search process has examined starts to get out of hand.
3572 */
3575 {
3576 /* See if we should skip ahead within the current leaf page */
3579 /*
3580 * Might have set pstate.skip to a later page offset. When
3581 * that happens then _bt_readpage caller will inexpensively
3582 * skip ahead to a later tuple from the same page (the one
3583 * just after the tuple we successfully "looked ahead" to).
3584 */
3585 }
3586 }
3588 /* This indextuple doesn't match the current qual, in any case */
3590 }
3592 /*
3593 * Caller's tuple is >= the current set of array keys and other equality
3594 * constraint scan keys (or <= if this is a backwards scan). It's now
3595 * clear that we _must_ advance any required array keys in lockstep with
3596 * the scan.
3597 */
3600 }
3602 /*
3603 * Test whether an indextuple fails to satisfy an inequality required in the
3604 * opposite direction only.
3605 *
3606 * Caller's finaltup tuple is the page high key (for forwards scans), or the
3607 * first non-pivot tuple (for backwards scans). Called during scans with
3608 * required array keys and required opposite-direction inequalities.
3609 *
3610 * Returns false if an inequality scan key required in the opposite direction
3611 * only isn't satisfied (and any earlier required scan keys are satisfied).
3612 * Otherwise returns true.
3613 *
3614 * An unsatisfied inequality required in the opposite direction only might
3615 * well enable skipping over many leaf pages, provided another _bt_first call
3616 * takes place. This type of unsatisfied inequality won't usually cause
3617 * _bt_checkkeys to stop the scan to consider array advancement/starting a new
3618 * primitive index scan.
3619 */
3620 bool
3622 IndexTuple finaltup)
3623 {
3641 }
3643 /*
3644 * Test whether an indextuple satisfies current scan condition.
3645 *
3646 * Return true if so, false if not. If not, also sets *continuescan to false
3647 * when it's also not possible for any later tuples to pass the current qual
3648 * (with the scan's current set of array keys, in the current scan direction),
3649 * in addition to setting *ikey to the so->keyData[] subscript/offset for the
3650 * unsatisfied scan key (needed when caller must consider advancing the scan's
3651 * array keys).
3652 *
3653 * This is a subroutine for _bt_checkkeys. We provisionally assume that
3654 * reaching the end of the current set of required keys (in particular the
3655 * current required array keys) ends the ongoing (primitive) index scan.
3656 * Callers without array keys should just end the scan right away when they
3657 * find that continuescan has been set to false here by us. Things are more
3658 * complicated for callers with array keys.
3659 *
3660 * Callers with array keys must first consider advancing the arrays when
3661 * continuescan has been set to false here by us. They must then consider if
3662 * it really does make sense to end the current (primitive) index scan, in
3663 * light of everything that is known at that point. (In general when we set
3664 * continuescan=false for these callers it must be treated as provisional.)
3665 *
3666 * We deal with advancing unsatisfied non-required arrays directly, though.
3667 * This is safe, since by definition non-required keys can't end the scan.
3668 * This is just how we determine if non-required arrays are just unsatisfied
3669 * by the current array key, or if they're truly unsatisfied (that is, if
3670 * they're unsatisfied by every possible array key).
3671 *
3672 * Though we advance non-required array keys on our own, that shouldn't have
3673 * any lasting consequences for the scan. By definition, non-required arrays
3674 * have no fixed relationship with the scan's progress. (There are delicate
3675 * considerations for non-required arrays when the arrays need to be advanced
3676 * following our setting continuescan to false, but that doesn't concern us.)
3677 *
3678 * Pass advancenonrequired=false to avoid all array related side effects.
3679 * This allows _bt_advance_array_keys caller to avoid infinite recursion.
3680 */
3681 static bool
3686 {
3692 {
3694 Datum datum;
3699 /*
3700 * Check if the key is required in the current scan direction, in the
3701 * opposite scan direction _only_, or in neither direction
3702 */
3710 /*
3711 * If the caller told us the *continuescan flag is known to be true
3712 * for the last item on the page, then we know the keys required for
3713 * the current direction scan should be matched. Otherwise, the
3714 * *continuescan flag would be set for the current item and
3715 * subsequently the last item on the page accordingly.
3716 *
3717 * If the key is required for the opposite direction scan, we can skip
3718 * the check if the caller tells us there was already at least one
3719 * matching item on the page. Also, we require the *continuescan flag
3720 * to be true for the last item on the page to know there are no
3721 * NULLs.
3722 *
3723 * Both cases above work except for the row keys, where NULLs could be
3724 * found in the middle of matching values.
3725 */
3732 {
3733 /*
3734 * This attribute is truncated (must be high key). The value for
3735 * this attribute in the first non-pivot tuple on the page to the
3736 * right could be any possible value. Assume that truncated
3737 * attribute passes the qual.
3738 */
3741 }
3743 /* row-comparison keys need special processing */
3745 {
3747 continuescan))
3750 }
3754 tupdesc,
3758 {
3759 /* Handle IS NULL/NOT NULL tests */
3761 {
3764 }
3765 else
3766 {
3770 }
3772 /*
3773 * Tuple fails this qual. If it's a required qual for the current
3774 * scan direction, then we can conclude no further tuples will
3775 * pass, either.
3776 */
3780 /*
3781 * In any case, this indextuple doesn't match the qual.
3782 */
3784 }
3787 {
3789 {
3790 /*
3791 * Since NULLs are sorted before non-NULLs, we know we have
3792 * reached the lower limit of the range of values for this
3793 * index attr. On a backward scan, we can stop if this qual
3794 * is one of the "must match" subset. We can stop regardless
3795 * of whether the qual is > or <, so long as it's required,
3796 * because it's not possible for any future tuples to pass. On
3797 * a forward scan, however, we must keep going, because we may
3798 * have initially positioned to the start of the index.
3799 * (_bt_advance_array_keys also relies on this behavior during
3800 * forward scans.)
3801 */
3805 }
3806 else
3807 {
3808 /*
3809 * Since NULLs are sorted after non-NULLs, we know we have
3810 * reached the upper limit of the range of values for this
3811 * index attr. On a forward scan, we can stop if this qual is
3812 * one of the "must match" subset. We can stop regardless of
3813 * whether the qual is > or <, so long as it's required,
3814 * because it's not possible for any future tuples to pass. On
3815 * a backward scan, however, we must keep going, because we
3816 * may have initially positioned to the end of the index.
3817 * (_bt_advance_array_keys also relies on this behavior during
3818 * backward scans.)
3819 */
3823 }
3825 /*
3826 * In any case, this indextuple doesn't match the qual.
3827 */
3829 }
3831 /*
3832 * Apply the key-checking function, though only if we must.
3833 *
3834 * When a key is required in the opposite-of-scan direction _only_,
3835 * then it must already be satisfied if firstmatch=true indicates that
3836 * an earlier tuple from this same page satisfied it earlier on.
3837 */
3841 {
3842 /*
3843 * Tuple fails this qual. If it's a required qual for the current
3844 * scan direction, then we can conclude no further tuples will
3845 * pass, either.
3846 *
3847 * Note: because we stop the scan as soon as any required equality
3848 * qual fails, it is critical that equality quals be used for the
3849 * initial positioning in _bt_first() when they are available. See
3850 * comments in _bt_first().
3851 */
3855 /*
3856 * If this is a non-required equality-type array key, the tuple
3857 * needs to be checked against every possible array key. Handle
3858 * this by "advancing" the scan key's array to a matching value
3859 * (if we're successful then the tuple might match the qual).
3860 */
3867 /*
3868 * This indextuple doesn't match the qual.
3869 */
3871 }
3872 }
3874 /* If we get here, the tuple passes all index quals. */
3876 }
3878 /*
3879 * Test whether an indextuple satisfies a row-comparison scan condition.
3880 *
3881 * Return true if so, false if not. If not, also clear *continuescan if
3882 * it's not possible for any future tuples in the current scan direction
3883 * to pass the qual.
3884 *
3885 * This is a subroutine for _bt_checkkeys/_bt_check_compare.
3886 */
3887 static bool
3890 {
3895 /* First subkey should be same as the header says */
3898 /* Loop over columns of the row condition */
3900 {
3901 Datum datum;
3907 {
3908 /*
3909 * This attribute is truncated (must be high key). The value for
3910 * this attribute in the first non-pivot tuple on the page to the
3911 * right could be any possible value. Assume that truncated
3912 * attribute passes the qual.
3913 */
3918 subkey++;
3920 }
3924 tupdesc,
3928 {
3930 {
3931 /*
3932 * Since NULLs are sorted before non-NULLs, we know we have
3933 * reached the lower limit of the range of values for this
3934 * index attr. On a backward scan, we can stop if this qual
3935 * is one of the "must match" subset. We can stop regardless
3936 * of whether the qual is > or <, so long as it's required,
3937 * because it's not possible for any future tuples to pass. On
3938 * a forward scan, however, we must keep going, because we may
3939 * have initially positioned to the start of the index.
3940 * (_bt_advance_array_keys also relies on this behavior during
3941 * forward scans.)
3942 */
3946 }
3947 else
3948 {
3949 /*
3950 * Since NULLs are sorted after non-NULLs, we know we have
3951 * reached the upper limit of the range of values for this
3952 * index attr. On a forward scan, we can stop if this qual is
3953 * one of the "must match" subset. We can stop regardless of
3954 * whether the qual is > or <, so long as it's required,
3955 * because it's not possible for any future tuples to pass. On
3956 * a backward scan, however, we must keep going, because we
3957 * may have initially positioned to the end of the index.
3958 * (_bt_advance_array_keys also relies on this behavior during
3959 * backward scans.)
3960 */
3964 }
3966 /*
3967 * In any case, this indextuple doesn't match the qual.
3968 */
3970 }
3973 {
3974 /*
3975 * Unlike the simple-scankey case, this isn't a disallowed case.
3976 * But it can never match. If all the earlier row comparison
3977 * columns are required for the scan direction, we can stop the
3978 * scan, because there can't be another tuple that will succeed.
3979 */
3981 subkey--;
3989 }
3991 /* Perform the test --- three-way comparison not bool operator */
3994 datum,
4000 /* Done comparing if unequal, else advance to next column */
4006 subkey++;
4007 }
4009 /*
4010 * At this point cmpresult indicates the overall result of the row
4011 * comparison, and subkey points to the deciding column (or the last
4012 * column if the result is "=").
4013 */
4015 {
4016 /* EQ and NE cases aren't allowed here */
4034 }
4037 {
4038 /*
4039 * Tuple fails this qual. If it's a required qual for the current
4040 * scan direction, then we can conclude no further tuples will pass,
4041 * either. Note we have to look at the deciding column, not
4042 * necessarily the first or last column of the row condition.
4043 */
4050 }
4053 }
4055 /*
4056 * Determine if a scan with array keys should skip over uninteresting tuples.
4057 *
4058 * This is a subroutine for _bt_checkkeys. Called when _bt_readpage's linear
4059 * search process (started after it finishes reading an initial group of
4060 * matching tuples, used to locate the start of the next group of tuples
4061 * matching the next set of required array keys) has already scanned an
4062 * excessive number of tuples whose key space is "between arrays".
4063 *
4064 * When we perform look ahead successfully, we'll sets pstate.skip, which
4065 * instructs _bt_readpage to skip ahead to that tuple next (could be past the
4066 * end of the scan's leaf page). Pages where the optimization is effective
4067 * will generally still need to skip several times. Each call here performs
4068 * only a single "look ahead" comparison of a later tuple, whose distance from
4069 * the current tuple's offset number is determined by applying heuristics.
4070 */
4071 static void
4074 {
4077 OffsetNumber aheadoffnum;
4078 IndexTuple ahead;
4080 /* Avoid looking ahead when comparing the page high key */
4084 /*
4085 * Don't look ahead when there aren't enough tuples remaining on the page
4086 * (in the current scan direction) for it to be worth our while
4087 */
4095 /*
4096 * The look ahead distance starts small, and ramps up as each call here
4097 * allows _bt_readpage to skip over more tuples
4098 */
4104 /* Don't read past the end (or before the start) of the page, though */
4108 else
4116 {
4117 /*
4118 * Success -- instruct _bt_readpage to skip ahead to very next tuple
4119 * after the one we determined was still before the current array keys
4120 */
4123 else
4125 }
4126 else
4127 {
4128 /*
4129 * Failure -- "ahead" tuple is too far ahead (we were too aggressive).
4130 *
4131 * Reset the number of rechecks, and aggressively reduce the target
4132 * distance (we're much more aggressive here than we were when the
4133 * distance was initially ramped up).
4134 */
4137 }
4138 }
4140 /*
4141 * _bt_killitems - set LP_DEAD state for items an indexscan caller has
4142 * told us were killed
4143 *
4144 * scan->opaque, referenced locally through so, contains information about the
4145 * current page and killed tuples thereon (generally, this should only be
4146 * called if so->numKilled > 0).
4147 *
4148 * The caller does not have a lock on the page and may or may not have the
4149 * page pinned in a buffer. Note that read-lock is sufficient for setting
4150 * LP_DEAD status (which is only a hint).
4151 *
4152 * We match items by heap TID before assuming they are the right ones to
4153 * delete. We cope with cases where items have moved right due to insertions.
4154 * If an item has moved off the current page due to a split, we'll fail to
4155 * find it and do nothing (this is not an error case --- we assume the item
4156 * will eventually get marked in a future indexscan).
4157 *
4158 * Note that if we hold a pin on the target page continuously from initially
4159 * reading the items until applying this function, VACUUM cannot have deleted
4160 * any items from the page, and so there is no need to search left from the
4161 * recorded offset. (This observation also guarantees that the item is still
4162 * the right one to delete, which might otherwise be questionable since heap
4163 * TIDs can get recycled.) This holds true even if the page has been modified
4164 * by inserts and page splits, so there is no need to consult the LSN.
4165 *
4166 * If the pin was released after reading the page, then we re-read it. If it
4167 * has been modified since we read it (as determined by the LSN), we dare not
4168 * flag any entries because it is possible that the old entry was vacuumed
4169 * away and the TID was re-used by a completely different heap tuple.
4170 */
4171 void
4173 {
4175 Page page;
4176 BTPageOpaque opaque;
4177 OffsetNumber minoff;
4178 OffsetNumber maxoff;
4186 /*
4187 * Always reset the scan state, so we don't look for same items on other
4188 * pages.
4189 */
4193 {
4194 /*
4195 * We have held the pin on this page since we read the index tuples,
4196 * so all we need to do is lock it. The pin will have prevented
4197 * re-use of any TID on the page, so there is no need to check the
4198 * LSN.
4199 */
4204 }
4205 else
4206 {
4207 Buffer buf;
4210 /* Attempt to re-read the buffer, getting pin and lock. */
4216 else
4217 {
4218 /* Modified while not pinned means hinting is not safe. */
4221 }
4222 }
4229 {
4239 {
4245 {
4250 /*
4251 * We rely on the convention that heap TIDs in the scanpos
4252 * items array are stored in ascending heap TID order for a
4253 * group of TIDs that originally came from a posting list
4254 * tuple. This convention even applies during backwards
4255 * scans, where returning the TIDs in descending order might
4256 * seem more natural. This is about effectiveness, not
4257 * correctness.
4258 *
4259 * Note that the page may have been modified in almost any way
4260 * since we first read it (in the !droppedpin case), so it's
4261 * possible that this posting list tuple wasn't a posting list
4262 * tuple when we first encountered its heap TIDs.
4263 */
4265 {
4271 /*
4272 * kitem must have matching offnum when heap TIDs match,
4273 * though only in the common case where the page can't
4274 * have been concurrently modified
4275 */
4278 /*
4279 * Read-ahead to later kitems here.
4280 *
4281 * We rely on the assumption that not advancing kitem here
4282 * will prevent us from considering the posting list tuple
4283 * fully dead by not matching its next heap TID in next
4284 * loop iteration.
4285 *
4286 * If, on the other hand, this is the final heap TID in
4287 * the posting list tuple, then tuple gets killed
4288 * regardless (i.e. we handle the case where the last
4289 * kitem is also the last heap TID in the last index tuple
4290 * correctly -- posting tuple still gets killed).
4291 */
4294 }
4296 /*
4297 * Don't bother advancing the outermost loop's int iterator to
4298 * avoid processing killed items that relate to the same
4299 * offnum/posting list tuple. This micro-optimization hardly
4300 * seems worth it. (Further iterations of the outermost loop
4301 * will fail to match on this same posting list's first heap
4302 * TID instead, so we'll advance to the next offnum/index
4303 * tuple pretty quickly.)
4304 */
4307 }
4311 /*
4312 * Mark index item as dead, if it isn't already. Since this
4313 * happens while holding a buffer lock possibly in shared mode,
4314 * it's possible that multiple processes attempt to do this
4315 * simultaneously, leading to multiple full-page images being sent
4316 * to WAL (if wal_log_hints or data checksums are enabled), which
4317 * is undesirable.
4318 */
4320 {
4321 /* found the item/all posting list items */
4325 }
4327 }
4328 }
4330 /*
4331 * Since this can be redone later if needed, mark as dirty hint.
4332 *
4333 * Whenever we mark anything LP_DEAD, we also set the page's
4334 * BTP_HAS_GARBAGE flag, which is likewise just a hint. (Note that we
4335 * only rely on the page-level flag in !heapkeyspace indexes.)
4336 */
4338 {
4341 }
4344 }
4347 /*
4348 * The following routines manage a shared-memory area in which we track
4349 * assignment of "vacuum cycle IDs" to currently-active btree vacuuming
4350 * operations. There is a single counter which increments each time we
4351 * start a vacuum to assign it a cycle ID. Since multiple vacuums could
4352 * be active concurrently, we have to track the cycle ID for each active
4353 * vacuum; this requires at most MaxBackends entries (usually far fewer).
4354 * We assume at most one vacuum can be active for a given index.
4355 *
4356 * Access to the shared memory area is controlled by BtreeVacuumLock.
4357 * In principle we could use a separate lmgr locktag for each index,
4358 * but a single LWLock is much cheaper, and given the short time that
4359 * the lock is ever held, the concurrency hit should be minimal.
4360 */
4363 {
4369 {
4379 /*
4380 * _bt_vacuum_cycleid --- get the active vacuum cycle ID for an index,
4381 * or zero if there is no active VACUUM
4382 *
4383 * Note: for correct interlocking, the caller must already hold pin and
4384 * exclusive lock on each buffer it will store the cycle ID into. This
4385 * ensures that even if a VACUUM starts immediately afterwards, it cannot
4386 * process those pages until the page split is complete.
4387 */
4388 BTCycleId
4390 {
4394 /* Share lock is enough since this is a read-only operation */
4398 {
4403 {
4406 }
4407 }
4411 }
4413 /*
4414 * _bt_start_vacuum --- assign a cycle ID to a just-starting VACUUM operation
4415 *
4416 * Note: the caller must guarantee that it will eventually call
4417 * _bt_end_vacuum, else we'll permanently leak an array slot. To ensure
4418 * that this happens even in elog(FATAL) scenarios, the appropriate coding
4419 * is not just a PG_TRY, but
4420 * PG_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel))
4421 */
4422 BTCycleId
4424 {
4425 BTCycleId result;
4431 /*
4432 * Assign the next cycle ID, being careful to avoid zero as well as the
4433 * reserved high values.
4434 */
4439 /* Let's just make sure there's no entry already for this index */
4441 {
4445 {
4446 /*
4447 * Unlike most places in the backend, we have to explicitly
4448 * release our LWLock before throwing an error. This is because
4449 * we expect _bt_end_vacuum() to be called before transaction
4450 * abort cleanup can run to release LWLocks.
4451 */
4455 }
4456 }
4458 /* OK, add an entry */
4460 {
4463 }
4471 }
4473 /*
4474 * _bt_end_vacuum --- mark a btree VACUUM operation as done
4475 *
4476 * Note: this is deliberately coded not to complain if no entry is found;
4477 * this allows the caller to put PG_TRY around the start_vacuum operation.
4478 */
4479 void
4481 {
4486 /* Find the array entry */
4488 {
4493 {
4494 /* Remove it by shifting down the last entry */
4498 }
4499 }
4502 }
4504 /*
4505 * _bt_end_vacuum wrapped as an on_shmem_exit callback function
4506 */
4507 void
4509 {
4511 }
4513 /*
4514 * BTreeShmemSize --- report amount of shared memory space needed
4515 */
4516 Size
4518 {
4519 Size size;
4524 }
4526 /*
4527 * BTreeShmemInit --- initialize this module's shared memory
4528 */
4529 void
4531 {
4539 {
4540 /* Initialize shared memory area */
4543 /*
4544 * It doesn't really matter what the cycle counter starts at, but
4545 * having it always start the same doesn't seem good. Seed with
4546 * low-order bits of time() instead.
4547 */
4552 }
4553 else
4555 }
4557 bytea *
4559 {
4566 };
4569 RELOPT_KIND_BTREE,
4572 }
4574 /*
4575 * btproperty() -- Check boolean properties of indexes.
4576 *
4577 * This is optional, but handling AMPROP_RETURNABLE here saves opening the rel
4578 * to call btcanreturn.
4579 */
4580 bool
4584 {
4586 {
4588 /* answer only for columns, not AM or whole index */
4591 /* otherwise, btree can always return data */
4597 }
4598 }
4600 /*
4601 * btbuildphasename() -- Return name of index build phase.
4602 */
4605 {
4607 {
4620 }
4621 }
4623 /*
4624 * _bt_truncate() -- create tuple without unneeded suffix attributes.
4625 *
4626 * Returns truncated pivot index tuple allocated in caller's memory context,
4627 * with key attributes copied from caller's firstright argument. If rel is
4628 * an INCLUDE index, non-key attributes will definitely be truncated away,
4629 * since they're not part of the key space. More aggressive suffix
4630 * truncation can take place when it's clear that the returned tuple does not
4631 * need one or more suffix key attributes. We only need to keep firstright
4632 * attributes up to and including the first non-lastleft-equal attribute.
4633 * Caller's insertion scankey is used to compare the tuples; the scankey's
4634 * argument values are not considered here.
4635 *
4636 * Note that returned tuple's t_tid offset will hold the number of attributes
4637 * present, so the original item pointer offset is not represented. Caller
4638 * should only change truncated tuple's downlink. Note also that truncated
4639 * key attributes are treated as containing "minus infinity" values by
4640 * _bt_compare().
4641 *
4642 * In the worst case (when a heap TID must be appended to distinguish lastleft
4643 * from firstright), the size of the returned tuple is the size of firstright
4644 * plus the size of an additional MAXALIGN()'d item pointer. This guarantee
4645 * is important, since callers need to stay under the 1/3 of a page
4646 * restriction on tuple size. If this routine is ever taught to truncate
4647 * within an attribute/datum, it will need to avoid returning an enlarged
4648 * tuple to caller when truncation + TOAST compression ends up enlarging the
4649 * final datum.
4650 */
4651 IndexTuple
4653 BTScanInsert itup_key)
4654 {
4658 IndexTuple pivot;
4659 IndexTuple tidpivot;
4660 ItemPointer pivotheaptid;
4661 Size newsize;
4663 /*
4664 * We should only ever truncate non-pivot tuples from leaf pages. It's
4665 * never okay to truncate when splitting an internal page.
4666 */
4669 /* Determine how many attributes must be kept in truncated tuple */
4672 #ifdef DEBUG_NO_TRUNCATE
4673 /* Force truncation to be ineffective for testing purposes */
4675 #endif
4681 {
4682 /*
4683 * index_truncate_tuple() just returns a straight copy of firstright
4684 * when it has no attributes to truncate. When that happens, we may
4685 * need to truncate away a posting list here instead.
4686 */
4691 }
4693 /*
4694 * If there is a distinguishing key attribute within pivot tuple, we're
4695 * done
4696 */
4698 {
4701 }
4703 /*
4704 * We have to store a heap TID in the new pivot tuple, since no non-TID
4705 * key attribute value in firstright distinguishes the right side of the
4706 * split from the left side. nbtree conceptualizes this case as an
4707 * inability to truncate away any key attributes, since heap TID is
4708 * treated as just another key attribute (despite lacking a pg_attribute
4709 * entry).
4710 *
4711 * Use enlarged space that holds a copy of pivot. We need the extra space
4712 * to store a heap TID at the end (using the special pivot tuple
4713 * representation). Note that the original pivot already has firstright's
4714 * possible posting list/non-key attribute values removed at this point.
4715 */
4719 /* Cannot leak memory here */
4722 /*
4723 * Store all of firstright's key attribute values plus a tiebreaker heap
4724 * TID value in enlarged pivot tuple
4725 */
4731 /*
4732 * Lehman & Yao use lastleft as the leaf high key in all cases, but don't
4733 * consider suffix truncation. It seems like a good idea to follow that
4734 * example in cases where no truncation takes place -- use lastleft's heap
4735 * TID. (This is also the closest value to negative infinity that's
4736 * legally usable.)
4737 */
4740 /*
4741 * We're done. Assert() that heap TID invariants hold before returning.
4742 *
4743 * Lehman and Yao require that the downlink to the right page, which is to
4744 * be inserted into the parent page in the second phase of a page split be
4745 * a strict lower bound on items on the right page, and a non-strict upper
4746 * bound for items on the left page. Assert that heap TIDs follow these
4747 * invariants, since a heap TID value is apparently needed as a
4748 * tiebreaker.
4749 */
4750 #ifndef DEBUG_NO_TRUNCATE
4757 #else
4759 /*
4760 * Those invariants aren't guaranteed to hold for lastleft + firstright
4761 * heap TID attribute values when they're considered here only because
4762 * DEBUG_NO_TRUNCATE is defined (a heap TID is probably not actually
4763 * needed as a tiebreaker). DEBUG_NO_TRUNCATE must therefore use a heap
4764 * TID value that always works as a strict lower bound for items to the
4765 * right. In particular, it must avoid using firstright's leading key
4766 * attribute values along with lastleft's heap TID value when lastleft's
4767 * TID happens to be greater than firstright's TID.
4768 */
4771 /*
4772 * Pivot heap TID should never be fully equal to firstright. Note that
4773 * the pivot heap TID will still end up equal to lastleft's heap TID when
4774 * that's the only usable value.
4775 */
4780 #endif
4783 }
4785 /*
4786 * _bt_keep_natts - how many key attributes to keep when truncating.
4787 *
4788 * Caller provides two tuples that enclose a split point. Caller's insertion
4789 * scankey is used to compare the tuples; the scankey's argument values are
4790 * not considered here.
4791 *
4792 * This can return a number of attributes that is one greater than the
4793 * number of key attributes for the index relation. This indicates that the
4794 * caller must use a heap TID as a unique-ifier in new pivot tuple.
4795 */
4796 static int
4798 BTScanInsert itup_key)
4799 {
4803 ScanKey scankey;
4805 /*
4806 * _bt_compare() treats truncated key attributes as having the value minus
4807 * infinity, which would break searches within !heapkeyspace indexes. We
4808 * must still truncate away non-key attribute values, though.
4809 */
4816 {
4817 Datum datum1,
4818 datum2;
4820 isNull2;
4831 datum1,
4835 keepnatts++;
4836 }
4838 /*
4839 * Assert that _bt_keep_natts_fast() agrees with us in passing. This is
4840 * expected in an allequalimage index.
4841 */
4846 }
4848 /*
4849 * _bt_keep_natts_fast - fast bitwise variant of _bt_keep_natts.
4850 *
4851 * This is exported so that a candidate split point can have its effect on
4852 * suffix truncation inexpensively evaluated ahead of time when finding a
4853 * split location. A naive bitwise approach to datum comparisons is used to
4854 * save cycles.
4855 *
4856 * The approach taken here usually provides the same answer as _bt_keep_natts
4857 * will (for the same pair of tuples from a heapkeyspace index), since the
4858 * majority of btree opclasses can never indicate that two datums are equal
4859 * unless they're bitwise equal after detoasting. When an index only has
4860 * "equal image" columns, routine is guaranteed to give the same result as
4861 * _bt_keep_natts would.
4862 *
4863 * Callers can rely on the fact that attributes considered equal here are
4864 * definitely also equal according to _bt_keep_natts, even when the index uses
4865 * an opclass or collation that is not "allequalimage"/deduplication-safe.
4866 * This weaker guarantee is good enough for nbtsplitloc.c caller, since false
4867 * negatives generally only have the effect of making leaf page splits use a
4868 * more balanced split point.
4869 */
4870 int
4872 {
4879 {
4880 Datum datum1,
4881 datum2;
4883 isNull2;
4884 Form_pg_attribute att;
4897 keepnatts++;
4898 }
4901 }
4903 /*
4904 * _bt_check_natts() -- Verify tuple has expected number of attributes.
4905 *
4906 * Returns value indicating if the expected number of attributes were found
4907 * for a particular offset on page. This can be used as a general purpose
4908 * sanity check.
4909 *
4910 * Testing a tuple directly with BTreeTupleGetNAtts() should generally be
4911 * preferred to calling here. That's usually more convenient, and is always
4912 * more explicit. Call here instead when offnum's tuple may be a negative
4913 * infinity tuple that uses the pre-v11 on-disk representation, or when a low
4914 * context check is appropriate. This routine is as strict as possible about
4915 * what is expected on each version of btree.
4916 */
4917 bool
4919 {
4923 IndexTuple itup;
4926 /*
4927 * We cannot reliably test a deleted or half-dead page, since they have
4928 * dummy high keys
4929 */
4939 /* !heapkeyspace indexes do not support deduplication */
4943 /* Posting list tuples should never have "pivot heap TID" bit set */
4949 /* INCLUDE indexes do not support deduplication */
4954 {
4956 {
4957 /*
4958 * Non-pivot tuple should never be explicitly marked as a pivot
4959 * tuple
4960 */
4964 /*
4965 * Leaf tuples that are not the page high key (non-pivot tuples)
4966 * should never be truncated. (Note that tupnatts must have been
4967 * inferred, even with a posting list tuple, because only pivot
4968 * tuples store tupnatts directly.)
4969 */
4971 }
4972 else
4973 {
4974 /*
4975 * Rightmost page doesn't contain a page high key, so tuple was
4976 * checked above as ordinary leaf tuple
4977 */
4980 /*
4981 * !heapkeyspace high key tuple contains only key attributes. Note
4982 * that tupnatts will only have been explicitly represented in
4983 * !heapkeyspace indexes that happen to have non-key attributes.
4984 */
4988 /* Use generic heapkeyspace pivot tuple handling */
4989 }
4990 }
4992 {
4994 {
4995 /*
4996 * The first tuple on any internal page (possibly the first after
4997 * its high key) is its negative infinity tuple. Negative
4998 * infinity tuples are always truncated to zero attributes. They
4999 * are a particular kind of pivot tuple.
5000 */
5004 /*
5005 * The number of attributes won't be explicitly represented if the
5006 * negative infinity tuple was generated during a page split that
5007 * occurred with a version of Postgres before v11. There must be
5008 * a problem when there is an explicit representation that is
5009 * non-zero, or when there is no explicit representation and the
5010 * tuple is evidently not a pre-pg_upgrade tuple.
5011 *
5012 * Prior to v11, downlinks always had P_HIKEY as their offset.
5013 * Accept that as an alternative indication of a valid
5014 * !heapkeyspace negative infinity tuple.
5015 */
5018 }
5019 else
5020 {
5021 /*
5022 * !heapkeyspace downlink tuple with separator key contains only
5023 * key attributes. Note that tupnatts will only have been
5024 * explicitly represented in !heapkeyspace indexes that happen to
5025 * have non-key attributes.
5026 */
5030 /* Use generic heapkeyspace pivot tuple handling */
5031 }
5032 }
5034 /* Handle heapkeyspace pivot tuples (excluding minus infinity items) */
5037 /*
5038 * Explicit representation of the number of attributes is mandatory with
5039 * heapkeyspace index pivot tuples, regardless of whether or not there are
5040 * non-key attributes.
5041 */
5045 /* Pivot tuple should not use posting list representation (redundant) */
5049 /*
5050 * Heap TID is a tiebreaker key attribute, so it cannot be untruncated
5051 * when any other key attribute is truncated
5052 */
5056 /*
5057 * Pivot tuple must have at least one untruncated key attribute (minus
5058 * infinity pivot tuples are the only exception). Pivot tuples can never
5059 * represent that there is a value present for a key attribute that
5060 * exceeds pg_index.indnkeyatts for the index.
5061 */
5063 }
5065 /*
5066 *
5067 * _bt_check_third_page() -- check whether tuple fits on a btree page at all.
5068 *
5069 * We actually need to be able to fit three items on every page, so restrict
5070 * any one item to 1/3 the per-page available space. Note that itemsz should
5071 * not include the ItemId overhead.
5072 *
5073 * It might be useful to apply TOAST methods rather than throw an error here.
5074 * Using out of line storage would break assumptions made by suffix truncation
5075 * and by contrib/amcheck, though.
5076 */
5077 void
5080 {
5081 Size itemsz;
5082 BTPageOpaque opaque;
5086 /* Double check item size against limit */
5090 /*
5091 * Tuple is probably too large to fit on page, but it's possible that the
5092 * index uses version 2 or version 3, or that page is an internal page, in
5093 * which case a slightly higher limit applies.
5094 */
5098 /*
5099 * Internal page insertions cannot fail here, because that would mean that
5100 * an earlier leaf level insertion that should have failed didn't
5101 */
5110 itemsz,
5120 "Consider a function index of an MD5 hash of the value, "
5123 }
5125 /*
5126 * Are all attributes in rel "equality is image equality" attributes?
5127 *
5128 * We use each attribute's BTEQUALIMAGE_PROC opclass procedure. If any
5129 * opclass either lacks a BTEQUALIMAGE_PROC procedure or returns false, we
5130 * return false; otherwise we return true.
5131 *
5132 * Returned boolean value is stored in index metapage during index builds.
5133 * Deduplication can only be used when we return true.
5134 */
5135 bool
5137 {
5140 /* INCLUDE indexes can never support deduplication */
5146 {
5150 Oid equalimageproc;
5153 BTEQUALIMAGE_PROC);
5155 /*
5156 * If there is no BTEQUALIMAGE_PROC then deduplication is assumed to
5157 * be unsafe. Otherwise, actually call proc and see what it says.
5158 */
5162 {
5165 }
5166 }
5169 {
5173 else
5176 }
5179 }