PostgreSQL Source Code  git master
nbtutils.c
Go to the documentation of this file.
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  */
15 
16 #include "postgres.h"
17 
18 #include <time.h>
19 
20 #include "access/nbtree.h"
21 #include "access/reloptions.h"
22 #include "access/relscan.h"
23 #include "commands/progress.h"
24 #include "lib/qunique.h"
25 #include "miscadmin.h"
26 #include "utils/array.h"
27 #include "utils/datum.h"
28 #include "utils/lsyscache.h"
29 #include "utils/memutils.h"
30 #include "utils/rel.h"
31 
32 #define LOOK_AHEAD_REQUIRED_RECHECKS 3
33 #define LOOK_AHEAD_DEFAULT_DISTANCE 5
34 
35 typedef struct BTSortArrayContext
36 {
39  bool reverse;
41 
42 typedef struct BTScanKeyPreproc
43 {
45  int ikey;
46  int arrayidx;
48 
49 static void _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype,
50  FmgrInfo *orderproc, FmgrInfo **sortprocp);
52  Oid elemtype, StrategyNumber strat,
53  Datum *elems, int nelems);
54 static int _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc,
55  bool reverse, Datum *elems, int nelems);
56 static bool _bt_merge_arrays(IndexScanDesc scan, ScanKey skey,
57  FmgrInfo *sortproc, bool reverse,
58  Oid origelemtype, Oid nextelemtype,
59  Datum *elems_orig, int *nelems_orig,
60  Datum *elems_next, int nelems_next);
62  ScanKey arraysk, ScanKey skey,
63  FmgrInfo *orderproc, BTArrayKeyInfo *array,
64  bool *qual_ok);
66 static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap);
67 static int _bt_compare_array_elements(const void *a, const void *b, void *arg);
68 static inline int32 _bt_compare_array_skey(FmgrInfo *orderproc,
69  Datum tupdatum, bool tupnull,
70  Datum arrdatum, ScanKey cur);
71 static int _bt_binsrch_array_skey(FmgrInfo *orderproc,
72  bool cur_elem_trig, ScanDirection dir,
73  Datum tupdatum, bool tupnull,
74  BTArrayKeyInfo *array, ScanKey cur,
75  int32 *set_elem_result);
79  IndexTuple tuple, TupleDesc tupdesc, int tupnatts,
80  bool readpagetup, int sktrig, bool *scanBehind);
81 static bool _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate,
82  IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
83  int sktrig, bool sktrig_required);
84 #ifdef USE_ASSERT_CHECKING
85 static bool _bt_verify_arrays_bt_first(IndexScanDesc scan, ScanDirection dir);
86 static bool _bt_verify_keys_with_arraykeys(IndexScanDesc scan);
87 #endif
89  ScanKey leftarg, ScanKey rightarg,
90  BTArrayKeyInfo *array, FmgrInfo *orderproc,
91  bool *result);
92 static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption);
93 static void _bt_mark_scankey_required(ScanKey skey);
94 static bool _bt_check_compare(IndexScanDesc scan, ScanDirection dir,
95  IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
96  bool advancenonrequired, bool prechecked, bool firstmatch,
97  bool *continuescan, int *ikey);
98 static bool _bt_check_rowcompare(ScanKey skey,
99  IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
100  ScanDirection dir, bool *continuescan);
101 static void _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate,
102  int tupnatts, TupleDesc tupdesc);
103 static int _bt_keep_natts(Relation rel, IndexTuple lastleft,
104  IndexTuple firstright, BTScanInsert itup_key);
105 
106 
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  */
130 {
132  ScanKey skey;
133  TupleDesc itupdesc;
134  int indnkeyatts;
135  int16 *indoption;
136  int tupnatts;
137  int i;
138 
139  itupdesc = RelationGetDescr(rel);
140  indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
141  indoption = rel->rd_indoption;
142  tupnatts = itup ? BTreeTupleGetNAtts(itup, rel) : 0;
143 
144  Assert(tupnatts <= IndexRelationGetNumberOfAttributes(rel));
145 
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  */
151  key = palloc(offsetof(BTScanInsertData, scankeys) +
152  sizeof(ScanKeyData) * indnkeyatts);
153  if (itup)
154  _bt_metaversion(rel, &key->heapkeyspace, &key->allequalimage);
155  else
156  {
157  /* Utility statement callers can set these fields themselves */
158  key->heapkeyspace = true;
159  key->allequalimage = false;
160  }
161  key->anynullkeys = false; /* initial assumption */
162  key->nextkey = false; /* usual case, required by btinsert */
163  key->backward = false; /* usual case, required by btinsert */
164  key->keysz = Min(indnkeyatts, tupnatts);
165  key->scantid = key->heapkeyspace && itup ?
166  BTreeTupleGetHeapTID(itup) : NULL;
167  skey = key->scankeys;
168  for (i = 0; i < indnkeyatts; i++)
169  {
170  FmgrInfo *procinfo;
171  Datum arg;
172  bool null;
173  int flags;
174 
175  /*
176  * We can use the cached (default) support procs since no cross-type
177  * comparison can be needed.
178  */
179  procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
180 
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  */
186  if (i < tupnatts)
187  arg = index_getattr(itup, i + 1, itupdesc, &null);
188  else
189  {
190  arg = (Datum) 0;
191  null = true;
192  }
193  flags = (null ? SK_ISNULL : 0) | (indoption[i] << SK_BT_INDOPTION_SHIFT);
195  flags,
196  (AttrNumber) (i + 1),
198  InvalidOid,
199  rel->rd_indcollation[i],
200  procinfo,
201  arg);
202  /* Record if any key attribute is NULL (or truncated) */
203  if (null)
204  key->anynullkeys = true;
205  }
206 
207  /*
208  * In NULLS NOT DISTINCT mode, we pretend that there are no null keys, so
209  * that full uniqueness check is done.
210  */
211  if (rel->rd_index->indnullsnotdistinct)
212  key->anynullkeys = false;
213 
214  return key;
215 }
216 
217 /*
218  * free a retracement stack made by _bt_search.
219  */
220 void
222 {
223  BTStack ostack;
224 
225  while (stack != NULL)
226  {
227  ostack = stack;
228  stack = stack->bts_parent;
229  pfree(ostack);
230  }
231 }
232 
233 
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  * It is convenient for _bt_preprocess_keys caller to have to deal with no
252  * more than one equality strategy array scan key per index attribute. We'll
253  * always be able to set things up that way when complete opfamilies are used.
254  * Eliminated array scan keys can be recognized as those that have had their
255  * sk_strategy field set to InvalidStrategy here by us. Caller should avoid
256  * including these in the scan's so->keyData[] output array.
257  *
258  * We set the scan key references from the scan's BTArrayKeyInfo info array to
259  * offsets into the temp modified input array returned to caller. Scans that
260  * have array keys should call _bt_preprocess_array_keys_final when standard
261  * preprocessing steps are complete. This will convert the scan key offset
262  * references into references to the scan's so->keyData[] output scan keys.
263  *
264  * Note: the reason we need to return a temp scan key array, rather than just
265  * scribbling on scan->keyData, is that callers are permitted to call btrescan
266  * without supplying a new set of scankey data.
267  */
268 static ScanKey
270 {
271  BTScanOpaque so = (BTScanOpaque) scan->opaque;
272  Relation rel = scan->indexRelation;
273  int numberOfKeys = scan->numberOfKeys;
274  int16 *indoption = rel->rd_indoption;
275  int numArrayKeys;
276  int origarrayatt = InvalidAttrNumber,
277  origarraykey = -1;
278  Oid origelemtype = InvalidOid;
279  ScanKey cur;
280  MemoryContext oldContext;
281  ScanKey arrayKeyData; /* modified copy of scan->keyData */
282 
283  Assert(numberOfKeys);
284 
285  /* Quick check to see if there are any array keys */
286  numArrayKeys = 0;
287  for (int i = 0; i < numberOfKeys; i++)
288  {
289  cur = &scan->keyData[i];
290  if (cur->sk_flags & SK_SEARCHARRAY)
291  {
292  numArrayKeys++;
293  Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
294  /* If any arrays are null as a whole, we can quit right now. */
295  if (cur->sk_flags & SK_ISNULL)
296  {
297  so->qual_ok = false;
298  return NULL;
299  }
300  }
301  }
302 
303  /* Quit if nothing to do. */
304  if (numArrayKeys == 0)
305  return NULL;
306 
307  /*
308  * Make a scan-lifespan context to hold array-associated data, or reset it
309  * if we already have one from a previous rescan cycle.
310  */
311  if (so->arrayContext == NULL)
313  "BTree array context",
315  else
317 
318  oldContext = MemoryContextSwitchTo(so->arrayContext);
319 
320  /* Create modifiable copy of scan->keyData in the workspace context */
321  arrayKeyData = (ScanKey) palloc(numberOfKeys * sizeof(ScanKeyData));
322  memcpy(arrayKeyData, scan->keyData, numberOfKeys * sizeof(ScanKeyData));
323 
324  /* Allocate space for per-array data in the workspace context */
325  so->arrayKeys = (BTArrayKeyInfo *) palloc(numArrayKeys * sizeof(BTArrayKeyInfo));
326 
327  /* Allocate space for ORDER procs used to help _bt_checkkeys */
328  so->orderProcs = (FmgrInfo *) palloc(numberOfKeys * sizeof(FmgrInfo));
329 
330  /* Now process each array key */
331  numArrayKeys = 0;
332  for (int i = 0; i < numberOfKeys; i++)
333  {
334  FmgrInfo sortproc;
335  FmgrInfo *sortprocp = &sortproc;
336  Oid elemtype;
337  bool reverse;
338  ArrayType *arrayval;
339  int16 elmlen;
340  bool elmbyval;
341  char elmalign;
342  int num_elems;
343  Datum *elem_values;
344  bool *elem_nulls;
345  int num_nonnulls;
346  int j;
347 
348  cur = &arrayKeyData[i];
349  if (!(cur->sk_flags & SK_SEARCHARRAY))
350  continue;
351 
352  /*
353  * First, deconstruct the array into elements. Anything allocated
354  * here (including a possibly detoasted array value) is in the
355  * workspace context.
356  */
357  arrayval = DatumGetArrayTypeP(cur->sk_argument);
358  /* We could cache this data, but not clear it's worth it */
360  &elmlen, &elmbyval, &elmalign);
361  deconstruct_array(arrayval,
362  ARR_ELEMTYPE(arrayval),
363  elmlen, elmbyval, elmalign,
364  &elem_values, &elem_nulls, &num_elems);
365 
366  /*
367  * Compress out any null elements. We can ignore them since we assume
368  * all btree operators are strict.
369  */
370  num_nonnulls = 0;
371  for (j = 0; j < num_elems; j++)
372  {
373  if (!elem_nulls[j])
374  elem_values[num_nonnulls++] = elem_values[j];
375  }
376 
377  /* We could pfree(elem_nulls) now, but not worth the cycles */
378 
379  /* If there's no non-nulls, the scan qual is unsatisfiable */
380  if (num_nonnulls == 0)
381  {
382  so->qual_ok = false;
383  break;
384  }
385 
386  /*
387  * Determine the nominal datatype of the array elements. We have to
388  * support the convention that sk_subtype == InvalidOid means the
389  * opclass input type; this is a hack to simplify life for
390  * ScanKeyInit().
391  */
392  elemtype = cur->sk_subtype;
393  if (elemtype == InvalidOid)
394  elemtype = rel->rd_opcintype[cur->sk_attno - 1];
395 
396  /*
397  * If the comparison operator is not equality, then the array qual
398  * degenerates to a simple comparison against the smallest or largest
399  * non-null array element, as appropriate.
400  */
401  switch (cur->sk_strategy)
402  {
405  cur->sk_argument =
406  _bt_find_extreme_element(scan, cur, elemtype,
408  elem_values, num_nonnulls);
409  continue;
411  /* proceed with rest of loop */
412  break;
415  cur->sk_argument =
416  _bt_find_extreme_element(scan, cur, elemtype,
418  elem_values, num_nonnulls);
419  continue;
420  default:
421  elog(ERROR, "unrecognized StrategyNumber: %d",
422  (int) cur->sk_strategy);
423  break;
424  }
425 
426  /*
427  * We'll need a 3-way ORDER proc to perform binary searches for the
428  * next matching array element. Set that up now.
429  *
430  * Array scan keys with cross-type equality operators will require a
431  * separate same-type ORDER proc for sorting their array. Otherwise,
432  * sortproc just points to the same proc used during binary searches.
433  */
434  _bt_setup_array_cmp(scan, cur, elemtype,
435  &so->orderProcs[i], &sortprocp);
436 
437  /*
438  * Sort the non-null elements and eliminate any duplicates. We must
439  * sort in the same ordering used by the index column, so that the
440  * arrays can be advanced in lockstep with the scan's progress through
441  * the index's key space.
442  */
443  reverse = (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0;
444  num_elems = _bt_sort_array_elements(cur, sortprocp, reverse,
445  elem_values, num_nonnulls);
446 
447  if (origarrayatt == cur->sk_attno)
448  {
449  BTArrayKeyInfo *orig = &so->arrayKeys[origarraykey];
450 
451  /*
452  * This array scan key is redundant with a previous equality
453  * operator array scan key. Merge the two arrays together to
454  * eliminate contradictory non-intersecting elements (or try to).
455  *
456  * We merge this next array back into attribute's original array.
457  */
458  Assert(arrayKeyData[orig->scan_key].sk_attno == cur->sk_attno);
459  Assert(arrayKeyData[orig->scan_key].sk_collation ==
460  cur->sk_collation);
461  if (_bt_merge_arrays(scan, cur, sortprocp, reverse,
462  origelemtype, elemtype,
463  orig->elem_values, &orig->num_elems,
464  elem_values, num_elems))
465  {
466  /* Successfully eliminated this array */
467  pfree(elem_values);
468 
469  /*
470  * If no intersecting elements remain in the original array,
471  * the scan qual is unsatisfiable
472  */
473  if (orig->num_elems == 0)
474  {
475  so->qual_ok = false;
476  break;
477  }
478 
479  /*
480  * Indicate to _bt_preprocess_keys caller that it must ignore
481  * this scan key
482  */
483  cur->sk_strategy = InvalidStrategy;
484  continue;
485  }
486 
487  /*
488  * Unable to merge this array with previous array due to a lack of
489  * suitable cross-type opfamily support. Will need to keep both
490  * scan keys/arrays.
491  */
492  }
493  else
494  {
495  /*
496  * This array is the first for current index attribute.
497  *
498  * If it turns out to not be the last array (that is, if the next
499  * array is redundantly applied to this same index attribute),
500  * we'll then treat this array as the attribute's "original" array
501  * when merging.
502  */
503  origarrayatt = cur->sk_attno;
504  origarraykey = numArrayKeys;
505  origelemtype = elemtype;
506  }
507 
508  /*
509  * And set up the BTArrayKeyInfo data.
510  *
511  * Note: _bt_preprocess_array_keys_final will fix-up each array's
512  * scan_key field later on, after so->keyData[] has been finalized.
513  */
514  so->arrayKeys[numArrayKeys].scan_key = i;
515  so->arrayKeys[numArrayKeys].num_elems = num_elems;
516  so->arrayKeys[numArrayKeys].elem_values = elem_values;
517  numArrayKeys++;
518  }
519 
520  so->numArrayKeys = numArrayKeys;
521 
522  MemoryContextSwitchTo(oldContext);
523 
524  return arrayKeyData;
525 }
526 
527 /*
528  * _bt_preprocess_array_keys_final() -- fix up array scan key references
529  *
530  * When _bt_preprocess_array_keys performed initial array preprocessing, it
531  * set each array's array->scan_key to the array's arrayKeys[] entry offset
532  * (that also work as references into the original scan->keyData[] array).
533  * This function handles translation of the scan key references from the
534  * BTArrayKeyInfo info array, from input scan key references (to the keys in
535  * scan->keyData[]), into output references (to the keys in so->keyData[]).
536  * Caller's keyDataMap[] array tells us how to perform this remapping.
537  *
538  * Also finalizes so->orderProcs[] for the scan. Arrays already have an ORDER
539  * proc, which might need to be repositioned to its so->keyData[]-wise offset
540  * (very much like the remapping that we apply to array->scan_key references).
541  * Non-array equality strategy scan keys (that survived preprocessing) don't
542  * yet have an so->orderProcs[] entry, so we set one for them here.
543  *
544  * Also converts single-element array scan keys into equivalent non-array
545  * equality scan keys, which decrements so->numArrayKeys. It's possible that
546  * this will leave this new btrescan without any arrays at all. This isn't
547  * necessary for correctness; it's just an optimization. Non-array equality
548  * scan keys are slightly faster than equivalent array scan keys at runtime.
549  */
550 static void
552 {
553  BTScanOpaque so = (BTScanOpaque) scan->opaque;
554  Relation rel = scan->indexRelation;
555  int arrayidx = 0;
556  int last_equal_output_ikey PG_USED_FOR_ASSERTS_ONLY = -1;
557 
558  Assert(so->qual_ok);
559 
560  /*
561  * Nothing for us to do when _bt_preprocess_array_keys only had to deal
562  * with array inequalities
563  */
564  if (so->numArrayKeys == 0)
565  return;
566 
567  for (int output_ikey = 0; output_ikey < so->numberOfKeys; output_ikey++)
568  {
569  ScanKey outkey = so->keyData + output_ikey;
570  int input_ikey;
571  bool found PG_USED_FOR_ASSERTS_ONLY = false;
572 
573  Assert(outkey->sk_strategy != InvalidStrategy);
574 
575  if (outkey->sk_strategy != BTEqualStrategyNumber)
576  continue;
577 
578  input_ikey = keyDataMap[output_ikey];
579 
580  Assert(last_equal_output_ikey < output_ikey);
581  Assert(last_equal_output_ikey < input_ikey);
582  last_equal_output_ikey = output_ikey;
583 
584  /*
585  * We're lazy about looking up ORDER procs for non-array keys, since
586  * not all input keys become output keys. Take care of it now.
587  */
588  if (!(outkey->sk_flags & SK_SEARCHARRAY))
589  {
590  Oid elemtype;
591 
592  /* No need for an ORDER proc given an IS NULL scan key */
593  if (outkey->sk_flags & SK_SEARCHNULL)
594  continue;
595 
596  /*
597  * A non-required scan key doesn't need an ORDER proc, either
598  * (unless it's associated with an array, which this one isn't)
599  */
600  if (!(outkey->sk_flags & SK_BT_REQFWD))
601  continue;
602 
603  elemtype = outkey->sk_subtype;
604  if (elemtype == InvalidOid)
605  elemtype = rel->rd_opcintype[outkey->sk_attno - 1];
606 
607  _bt_setup_array_cmp(scan, outkey, elemtype,
608  &so->orderProcs[output_ikey], NULL);
609  continue;
610  }
611 
612  /*
613  * Reorder existing array scan key so->orderProcs[] entries.
614  *
615  * Doing this in-place is safe because preprocessing is required to
616  * output all equality strategy scan keys in original input order
617  * (among each group of entries against the same index attribute).
618  * This is also the order that the arrays themselves appear in.
619  */
620  so->orderProcs[output_ikey] = so->orderProcs[input_ikey];
621 
622  /* Fix-up array->scan_key references for arrays */
623  for (; arrayidx < so->numArrayKeys; arrayidx++)
624  {
625  BTArrayKeyInfo *array = &so->arrayKeys[arrayidx];
626 
627  Assert(array->num_elems > 0);
628 
629  if (array->scan_key == input_ikey)
630  {
631  /* found it */
632  array->scan_key = output_ikey;
633  found = true;
634 
635  /*
636  * Transform array scan keys that have exactly 1 element
637  * remaining (following all prior preprocessing) into
638  * equivalent non-array scan keys.
639  */
640  if (array->num_elems == 1)
641  {
642  outkey->sk_flags &= ~SK_SEARCHARRAY;
643  outkey->sk_argument = array->elem_values[0];
644  so->numArrayKeys--;
645 
646  /* If we're out of array keys, we can quit right away */
647  if (so->numArrayKeys == 0)
648  return;
649 
650  /* Shift other arrays forward */
651  memmove(array, array + 1,
652  sizeof(BTArrayKeyInfo) *
653  (so->numArrayKeys - arrayidx));
654 
655  /*
656  * Don't increment arrayidx (there was an entry that was
657  * just shifted forward to the offset at arrayidx, which
658  * will still need to be matched)
659  */
660  }
661  else
662  {
663  /* Match found, so done with this array */
664  arrayidx++;
665  }
666 
667  break;
668  }
669  }
670 
671  Assert(found);
672  }
673 
674  /*
675  * Parallel index scans require space in shared memory to store the
676  * current array elements (for arrays kept by preprocessing) to schedule
677  * the next primitive index scan. The underlying structure is protected
678  * using a spinlock, so defensively limit its size. In practice this can
679  * only affect parallel scans that use an incomplete opfamily.
680  */
681  if (scan->parallel_scan && so->numArrayKeys > INDEX_MAX_KEYS)
682  ereport(ERROR,
683  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
684  errmsg_internal("number of array scan keys left by preprocessing (%d) exceeds the maximum allowed by parallel btree index scans (%d)",
686 }
687 
688 /*
689  * _bt_setup_array_cmp() -- Set up array comparison functions
690  *
691  * Sets ORDER proc in caller's orderproc argument, which is used during binary
692  * searches of arrays during the index scan. Also sets a same-type ORDER proc
693  * in caller's *sortprocp argument, which is used when sorting the array.
694  *
695  * Preprocessing calls here with all equality strategy scan keys (when scan
696  * uses equality array keys), including those not associated with any array.
697  * See _bt_advance_array_keys for an explanation of why it'll need to treat
698  * simple scalar equality scan keys as degenerate single element arrays.
699  *
700  * Caller should pass an orderproc pointing to space that'll store the ORDER
701  * proc for the scan, and a *sortprocp pointing to its own separate space.
702  * When calling here for a non-array scan key, sortprocp arg should be NULL.
703  *
704  * In the common case where we don't need to deal with cross-type operators,
705  * only one ORDER proc is actually required by caller. We'll set *sortprocp
706  * to point to the same memory that caller's orderproc continues to point to.
707  * Otherwise, *sortprocp will continue to point to caller's own space. Either
708  * way, *sortprocp will point to a same-type ORDER proc (since that's the only
709  * safe way to sort/deduplicate the array associated with caller's scan key).
710  */
711 static void
713  FmgrInfo *orderproc, FmgrInfo **sortprocp)
714 {
715  BTScanOpaque so = (BTScanOpaque) scan->opaque;
716  Relation rel = scan->indexRelation;
717  RegProcedure cmp_proc;
718  Oid opcintype = rel->rd_opcintype[skey->sk_attno - 1];
719 
721  Assert(OidIsValid(elemtype));
722 
723  /*
724  * If scankey operator is not a cross-type comparison, we can use the
725  * cached comparison function; otherwise gotta look it up in the catalogs
726  */
727  if (elemtype == opcintype)
728  {
729  /* Set same-type ORDER procs for caller */
730  *orderproc = *index_getprocinfo(rel, skey->sk_attno, BTORDER_PROC);
731  if (sortprocp)
732  *sortprocp = orderproc;
733 
734  return;
735  }
736 
737  /*
738  * Look up the appropriate cross-type comparison function in the opfamily.
739  *
740  * Use the opclass input type as the left hand arg type, and the array
741  * element type as the right hand arg type (since binary searches use an
742  * index tuple's attribute value to search for a matching array element).
743  *
744  * Note: it's possible that this would fail, if the opfamily is
745  * incomplete, but only in cases where it's quite likely that _bt_first
746  * would fail in just the same way (had we not failed before it could).
747  */
748  cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
749  opcintype, elemtype, BTORDER_PROC);
750  if (!RegProcedureIsValid(cmp_proc))
751  elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
752  BTORDER_PROC, opcintype, elemtype, skey->sk_attno,
754 
755  /* Set cross-type ORDER proc for caller */
756  fmgr_info_cxt(cmp_proc, orderproc, so->arrayContext);
757 
758  /* Done if caller doesn't actually have an array they'll need to sort */
759  if (!sortprocp)
760  return;
761 
762  /*
763  * Look up the appropriate same-type comparison function in the opfamily.
764  *
765  * Note: it's possible that this would fail, if the opfamily is
766  * incomplete, but it seems quite unlikely that an opfamily would omit
767  * non-cross-type comparison procs for any datatype that it supports at
768  * all.
769  */
770  cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
771  elemtype, elemtype, BTORDER_PROC);
772  if (!RegProcedureIsValid(cmp_proc))
773  elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
774  BTORDER_PROC, elemtype, elemtype,
775  skey->sk_attno, RelationGetRelationName(rel));
776 
777  /* Set same-type ORDER proc for caller */
778  fmgr_info_cxt(cmp_proc, *sortprocp, so->arrayContext);
779 }
780 
781 /*
782  * _bt_find_extreme_element() -- get least or greatest array element
783  *
784  * scan and skey identify the index column, whose opfamily determines the
785  * comparison semantics. strat should be BTLessStrategyNumber to get the
786  * least element, or BTGreaterStrategyNumber to get the greatest.
787  */
788 static Datum
790  StrategyNumber strat,
791  Datum *elems, int nelems)
792 {
793  Relation rel = scan->indexRelation;
794  Oid cmp_op;
795  RegProcedure cmp_proc;
796  FmgrInfo flinfo;
797  Datum result;
798  int i;
799 
800  /*
801  * Look up the appropriate comparison operator in the opfamily.
802  *
803  * Note: it's possible that this would fail, if the opfamily is
804  * incomplete, but it seems quite unlikely that an opfamily would omit
805  * non-cross-type comparison operators for any datatype that it supports
806  * at all.
807  */
809  Assert(OidIsValid(elemtype));
810  cmp_op = get_opfamily_member(rel->rd_opfamily[skey->sk_attno - 1],
811  elemtype,
812  elemtype,
813  strat);
814  if (!OidIsValid(cmp_op))
815  elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
816  strat, elemtype, elemtype,
817  rel->rd_opfamily[skey->sk_attno - 1]);
818  cmp_proc = get_opcode(cmp_op);
819  if (!RegProcedureIsValid(cmp_proc))
820  elog(ERROR, "missing oprcode for operator %u", cmp_op);
821 
822  fmgr_info(cmp_proc, &flinfo);
823 
824  Assert(nelems > 0);
825  result = elems[0];
826  for (i = 1; i < nelems; i++)
827  {
828  if (DatumGetBool(FunctionCall2Coll(&flinfo,
829  skey->sk_collation,
830  elems[i],
831  result)))
832  result = elems[i];
833  }
834 
835  return result;
836 }
837 
838 /*
839  * _bt_sort_array_elements() -- sort and de-dup array elements
840  *
841  * The array elements are sorted in-place, and the new number of elements
842  * after duplicate removal is returned.
843  *
844  * skey identifies the index column whose opfamily determines the comparison
845  * semantics, and sortproc is a corresponding ORDER proc. If reverse is true,
846  * we sort in descending order.
847  */
848 static int
849 _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc, bool reverse,
850  Datum *elems, int nelems)
851 {
852  BTSortArrayContext cxt;
853 
854  if (nelems <= 1)
855  return nelems; /* no work to do */
856 
857  /* Sort the array elements */
858  cxt.sortproc = sortproc;
859  cxt.collation = skey->sk_collation;
860  cxt.reverse = reverse;
861  qsort_arg(elems, nelems, sizeof(Datum),
863 
864  /* Now scan the sorted elements and remove duplicates */
865  return qunique_arg(elems, nelems, sizeof(Datum),
867 }
868 
869 /*
870  * _bt_merge_arrays() -- merge next array's elements into an original array
871  *
872  * Called when preprocessing encounters a pair of array equality scan keys,
873  * both against the same index attribute (during initial array preprocessing).
874  * Merging reorganizes caller's original array (the left hand arg) in-place,
875  * without ever copying elements from one array into the other. (Mixing the
876  * elements together like this would be wrong, since they don't necessarily
877  * use the same underlying element type, despite all the other similarities.)
878  *
879  * Both arrays must have already been sorted and deduplicated by calling
880  * _bt_sort_array_elements. sortproc is the same-type ORDER proc that was
881  * just used to sort and deduplicate caller's "next" array. We'll usually be
882  * able to reuse that order PROC to merge the arrays together now. If not,
883  * then we'll perform a separate ORDER proc lookup.
884  *
885  * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
886  * may not be able to determine which elements are contradictory. If we have
887  * the required ORDER proc then we return true (and validly set *nelems_orig),
888  * guaranteeing that at least the next array can be considered redundant. We
889  * return false if the required comparisons cannot not be made (caller must
890  * keep both arrays when this happens).
891  */
892 static bool
894  bool reverse, Oid origelemtype, Oid nextelemtype,
895  Datum *elems_orig, int *nelems_orig,
896  Datum *elems_next, int nelems_next)
897 {
898  Relation rel = scan->indexRelation;
899  BTScanOpaque so = (BTScanOpaque) scan->opaque;
900  BTSortArrayContext cxt;
901  int nelems_orig_start = *nelems_orig,
902  nelems_orig_merged = 0;
903  FmgrInfo *mergeproc = sortproc;
904  FmgrInfo crosstypeproc;
905 
907  Assert(OidIsValid(origelemtype) && OidIsValid(nextelemtype));
908 
909  if (origelemtype != nextelemtype)
910  {
911  RegProcedure cmp_proc;
912 
913  /*
914  * Cross-array-element-type merging is required, so can't just reuse
915  * sortproc when merging
916  */
917  cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
918  origelemtype, nextelemtype, BTORDER_PROC);
919  if (!RegProcedureIsValid(cmp_proc))
920  {
921  /* Can't make the required comparisons */
922  return false;
923  }
924 
925  /* We have all we need to determine redundancy/contradictoriness */
926  mergeproc = &crosstypeproc;
927  fmgr_info_cxt(cmp_proc, mergeproc, so->arrayContext);
928  }
929 
930  cxt.sortproc = mergeproc;
931  cxt.collation = skey->sk_collation;
932  cxt.reverse = reverse;
933 
934  for (int i = 0, j = 0; i < nelems_orig_start && j < nelems_next;)
935  {
936  Datum *oelem = elems_orig + i,
937  *nelem = elems_next + j;
938  int res = _bt_compare_array_elements(oelem, nelem, &cxt);
939 
940  if (res == 0)
941  {
942  elems_orig[nelems_orig_merged++] = *oelem;
943  i++;
944  j++;
945  }
946  else if (res < 0)
947  i++;
948  else /* res > 0 */
949  j++;
950  }
951 
952  *nelems_orig = nelems_orig_merged;
953 
954  return true;
955 }
956 
957 /*
958  * Compare an array scan key to a scalar scan key, eliminating contradictory
959  * array elements such that the scalar scan key becomes redundant.
960  *
961  * Array elements can be eliminated as contradictory when excluded by some
962  * other operator on the same attribute. For example, with an index scan qual
963  * "WHERE a IN (1, 2, 3) AND a < 2", all array elements except the value "1"
964  * are eliminated, and the < scan key is eliminated as redundant. Cases where
965  * every array element is eliminated by a redundant scalar scan key have an
966  * unsatisfiable qual, which we handle by setting *qual_ok=false for caller.
967  *
968  * If the opfamily doesn't supply a complete set of cross-type ORDER procs we
969  * may not be able to determine which elements are contradictory. If we have
970  * the required ORDER proc then we return true (and validly set *qual_ok),
971  * guaranteeing that at least the scalar scan key can be considered redundant.
972  * We return false if the comparison could not be made (caller must keep both
973  * scan keys when this happens).
974  */
975 static bool
977  FmgrInfo *orderproc, BTArrayKeyInfo *array,
978  bool *qual_ok)
979 {
980  Relation rel = scan->indexRelation;
981  Oid opcintype = rel->rd_opcintype[arraysk->sk_attno - 1];
982  int cmpresult = 0,
983  cmpexact = 0,
984  matchelem,
985  new_nelems = 0;
986  FmgrInfo crosstypeproc;
987  FmgrInfo *orderprocp = orderproc;
988 
989  Assert(arraysk->sk_attno == skey->sk_attno);
990  Assert(array->num_elems > 0);
991  Assert(!(arraysk->sk_flags & (SK_ISNULL | SK_ROW_HEADER | SK_ROW_MEMBER)));
992  Assert((arraysk->sk_flags & SK_SEARCHARRAY) &&
993  arraysk->sk_strategy == BTEqualStrategyNumber);
995  Assert(!(skey->sk_flags & SK_SEARCHARRAY) ||
997 
998  /*
999  * _bt_binsrch_array_skey searches an array for the entry best matching a
1000  * datum of opclass input type for the index's attribute (on-disk type).
1001  * We can reuse the array's ORDER proc whenever the non-array scan key's
1002  * type is a match for the corresponding attribute's input opclass type.
1003  * Otherwise, we have to do another ORDER proc lookup so that our call to
1004  * _bt_binsrch_array_skey applies the correct comparator.
1005  *
1006  * Note: we have to support the convention that sk_subtype == InvalidOid
1007  * means the opclass input type; this is a hack to simplify life for
1008  * ScanKeyInit().
1009  */
1010  if (skey->sk_subtype != opcintype && skey->sk_subtype != InvalidOid)
1011  {
1012  RegProcedure cmp_proc;
1013  Oid arraysk_elemtype;
1014 
1015  /*
1016  * Need an ORDER proc lookup to detect redundancy/contradictoriness
1017  * with this pair of scankeys.
1018  *
1019  * Scalar scan key's argument will be passed to _bt_compare_array_skey
1020  * as its tupdatum/lefthand argument (rhs arg is for array elements).
1021  */
1022  arraysk_elemtype = arraysk->sk_subtype;
1023  if (arraysk_elemtype == InvalidOid)
1024  arraysk_elemtype = rel->rd_opcintype[arraysk->sk_attno - 1];
1025  cmp_proc = get_opfamily_proc(rel->rd_opfamily[arraysk->sk_attno - 1],
1026  skey->sk_subtype, arraysk_elemtype,
1027  BTORDER_PROC);
1028  if (!RegProcedureIsValid(cmp_proc))
1029  {
1030  /* Can't make the comparison */
1031  *qual_ok = false; /* suppress compiler warnings */
1032  return false;
1033  }
1034 
1035  /* We have all we need to determine redundancy/contradictoriness */
1036  orderprocp = &crosstypeproc;
1037  fmgr_info(cmp_proc, orderprocp);
1038  }
1039 
1040  matchelem = _bt_binsrch_array_skey(orderprocp, false,
1042  skey->sk_argument, false, array,
1043  arraysk, &cmpresult);
1044 
1045  switch (skey->sk_strategy)
1046  {
1047  case BTLessStrategyNumber:
1048  cmpexact = 1; /* exclude exact match, if any */
1049  /* FALL THRU */
1051  if (cmpresult >= cmpexact)
1052  matchelem++;
1053  /* Resize, keeping elements from the start of the array */
1054  new_nelems = matchelem;
1055  break;
1056  case BTEqualStrategyNumber:
1057  if (cmpresult != 0)
1058  {
1059  /* qual is unsatisfiable */
1060  new_nelems = 0;
1061  }
1062  else
1063  {
1064  /* Shift matching element to the start of the array, resize */
1065  array->elem_values[0] = array->elem_values[matchelem];
1066  new_nelems = 1;
1067  }
1068  break;
1070  cmpexact = 1; /* include exact match, if any */
1071  /* FALL THRU */
1073  if (cmpresult >= cmpexact)
1074  matchelem++;
1075  /* Shift matching elements to the start of the array, resize */
1076  new_nelems = array->num_elems - matchelem;
1077  memmove(array->elem_values, array->elem_values + matchelem,
1078  sizeof(Datum) * new_nelems);
1079  break;
1080  default:
1081  elog(ERROR, "unrecognized StrategyNumber: %d",
1082  (int) skey->sk_strategy);
1083  break;
1084  }
1085 
1086  Assert(new_nelems >= 0);
1087  Assert(new_nelems <= array->num_elems);
1088 
1089  array->num_elems = new_nelems;
1090  *qual_ok = new_nelems > 0;
1091 
1092  return true;
1093 }
1094 
1095 /*
1096  * qsort_arg comparator for sorting array elements
1097  */
1098 static int
1099 _bt_compare_array_elements(const void *a, const void *b, void *arg)
1100 {
1101  Datum da = *((const Datum *) a);
1102  Datum db = *((const Datum *) b);
1104  int32 compare;
1105 
1107  cxt->collation,
1108  da, db));
1109  if (cxt->reverse)
1111  return compare;
1112 }
1113 
1114 /*
1115  * _bt_compare_array_skey() -- apply array comparison function
1116  *
1117  * Compares caller's tuple attribute value to a scan key/array element.
1118  * Helper function used during binary searches of SK_SEARCHARRAY arrays.
1119  *
1120  * This routine returns:
1121  * <0 if tupdatum < arrdatum;
1122  * 0 if tupdatum == arrdatum;
1123  * >0 if tupdatum > arrdatum.
1124  *
1125  * This is essentially the same interface as _bt_compare: both functions
1126  * compare the value that they're searching for to a binary search pivot.
1127  * However, unlike _bt_compare, this function's "tuple argument" comes first,
1128  * while its "array/scankey argument" comes second.
1129 */
1130 static inline int32
1132  Datum tupdatum, bool tupnull,
1133  Datum arrdatum, ScanKey cur)
1134 {
1135  int32 result = 0;
1136 
1137  Assert(cur->sk_strategy == BTEqualStrategyNumber);
1138 
1139  if (tupnull) /* NULL tupdatum */
1140  {
1141  if (cur->sk_flags & SK_ISNULL)
1142  result = 0; /* NULL "=" NULL */
1143  else if (cur->sk_flags & SK_BT_NULLS_FIRST)
1144  result = -1; /* NULL "<" NOT_NULL */
1145  else
1146  result = 1; /* NULL ">" NOT_NULL */
1147  }
1148  else if (cur->sk_flags & SK_ISNULL) /* NOT_NULL tupdatum, NULL arrdatum */
1149  {
1150  if (cur->sk_flags & SK_BT_NULLS_FIRST)
1151  result = 1; /* NOT_NULL ">" NULL */
1152  else
1153  result = -1; /* NOT_NULL "<" NULL */
1154  }
1155  else
1156  {
1157  /*
1158  * Like _bt_compare, we need to be careful of cross-type comparisons,
1159  * so the left value has to be the value that came from an index tuple
1160  */
1161  result = DatumGetInt32(FunctionCall2Coll(orderproc, cur->sk_collation,
1162  tupdatum, arrdatum));
1163 
1164  /*
1165  * We flip the sign by following the obvious rule: flip whenever the
1166  * column is a DESC column.
1167  *
1168  * _bt_compare does it the wrong way around (flip when *ASC*) in order
1169  * to compensate for passing its orderproc arguments backwards. We
1170  * don't need to play these games because we find it natural to pass
1171  * tupdatum as the left value (and arrdatum as the right value).
1172  */
1173  if (cur->sk_flags & SK_BT_DESC)
1174  INVERT_COMPARE_RESULT(result);
1175  }
1176 
1177  return result;
1178 }
1179 
1180 /*
1181  * _bt_binsrch_array_skey() -- Binary search for next matching array key
1182  *
1183  * Returns an index to the first array element >= caller's tupdatum argument.
1184  * This convention is more natural for forwards scan callers, but that can't
1185  * really matter to backwards scan callers. Both callers require handling for
1186  * the case where the match we return is < tupdatum, and symmetric handling
1187  * for the case where our best match is > tupdatum.
1188  *
1189  * Also sets *set_elem_result to the result _bt_compare_array_skey returned
1190  * when we used it to compare the matching array element to tupdatum/tupnull.
1191  *
1192  * cur_elem_trig indicates if array advancement was triggered by this array's
1193  * scan key, and that the array is for a required scan key. We can apply this
1194  * information to find the next matching array element in the current scan
1195  * direction using far fewer comparisons (fewer on average, compared to naive
1196  * binary search). This scheme takes advantage of an important property of
1197  * required arrays: required arrays always advance in lockstep with the index
1198  * scan's progress through the index's key space.
1199  */
1200 static int
1202  bool cur_elem_trig, ScanDirection dir,
1203  Datum tupdatum, bool tupnull,
1204  BTArrayKeyInfo *array, ScanKey cur,
1205  int32 *set_elem_result)
1206 {
1207  int low_elem = 0,
1208  mid_elem = -1,
1209  high_elem = array->num_elems - 1,
1210  result = 0;
1211  Datum arrdatum;
1212 
1213  Assert(cur->sk_flags & SK_SEARCHARRAY);
1214  Assert(cur->sk_strategy == BTEqualStrategyNumber);
1215 
1216  if (cur_elem_trig)
1217  {
1219  Assert(cur->sk_flags & SK_BT_REQFWD);
1220 
1221  /*
1222  * When the scan key that triggered array advancement is a required
1223  * array scan key, it is now certain that the current array element
1224  * (plus all prior elements relative to the current scan direction)
1225  * cannot possibly be at or ahead of the corresponding tuple value.
1226  * (_bt_checkkeys must have called _bt_tuple_before_array_skeys, which
1227  * makes sure this is true as a condition of advancing the arrays.)
1228  *
1229  * This makes it safe to exclude array elements up to and including
1230  * the former-current array element from our search.
1231  *
1232  * Separately, when array advancement was triggered by a required scan
1233  * key, the array element immediately after the former-current element
1234  * is often either an exact tupdatum match, or a "close by" near-match
1235  * (a near-match tupdatum is one whose key space falls _between_ the
1236  * former-current and new-current array elements). We'll detect both
1237  * cases via an optimistic comparison of the new search lower bound
1238  * (or new search upper bound in the case of backwards scans).
1239  */
1240  if (ScanDirectionIsForward(dir))
1241  {
1242  low_elem = array->cur_elem + 1; /* old cur_elem exhausted */
1243 
1244  /* Compare prospective new cur_elem (also the new lower bound) */
1245  if (high_elem >= low_elem)
1246  {
1247  arrdatum = array->elem_values[low_elem];
1248  result = _bt_compare_array_skey(orderproc, tupdatum, tupnull,
1249  arrdatum, cur);
1250 
1251  if (result <= 0)
1252  {
1253  /* Optimistic comparison optimization worked out */
1254  *set_elem_result = result;
1255  return low_elem;
1256  }
1257  mid_elem = low_elem;
1258  low_elem++; /* this cur_elem exhausted, too */
1259  }
1260 
1261  if (high_elem < low_elem)
1262  {
1263  /* Caller needs to perform "beyond end" array advancement */
1264  *set_elem_result = 1;
1265  return high_elem;
1266  }
1267  }
1268  else
1269  {
1270  high_elem = array->cur_elem - 1; /* old cur_elem exhausted */
1271 
1272  /* Compare prospective new cur_elem (also the new upper bound) */
1273  if (high_elem >= low_elem)
1274  {
1275  arrdatum = array->elem_values[high_elem];
1276  result = _bt_compare_array_skey(orderproc, tupdatum, tupnull,
1277  arrdatum, cur);
1278 
1279  if (result >= 0)
1280  {
1281  /* Optimistic comparison optimization worked out */
1282  *set_elem_result = result;
1283  return high_elem;
1284  }
1285  mid_elem = high_elem;
1286  high_elem--; /* this cur_elem exhausted, too */
1287  }
1288 
1289  if (high_elem < low_elem)
1290  {
1291  /* Caller needs to perform "beyond end" array advancement */
1292  *set_elem_result = -1;
1293  return low_elem;
1294  }
1295  }
1296  }
1297 
1298  while (high_elem > low_elem)
1299  {
1300  mid_elem = low_elem + ((high_elem - low_elem) / 2);
1301  arrdatum = array->elem_values[mid_elem];
1302 
1303  result = _bt_compare_array_skey(orderproc, tupdatum, tupnull,
1304  arrdatum, cur);
1305 
1306  if (result == 0)
1307  {
1308  /*
1309  * It's safe to quit as soon as we see an equal array element.
1310  * This often saves an extra comparison or two...
1311  */
1312  low_elem = mid_elem;
1313  break;
1314  }
1315 
1316  if (result > 0)
1317  low_elem = mid_elem + 1;
1318  else
1319  high_elem = mid_elem;
1320  }
1321 
1322  /*
1323  * ...but our caller also cares about how its searched-for tuple datum
1324  * compares to the low_elem datum. Must always set *set_elem_result with
1325  * the result of that comparison specifically.
1326  */
1327  if (low_elem != mid_elem)
1328  result = _bt_compare_array_skey(orderproc, tupdatum, tupnull,
1329  array->elem_values[low_elem], cur);
1330 
1331  *set_elem_result = result;
1332 
1333  return low_elem;
1334 }
1335 
1336 /*
1337  * _bt_start_array_keys() -- Initialize array keys at start of a scan
1338  *
1339  * Set up the cur_elem counters and fill in the first sk_argument value for
1340  * each array scankey.
1341  */
1342 void
1344 {
1345  BTScanOpaque so = (BTScanOpaque) scan->opaque;
1346  int i;
1347 
1348  Assert(so->numArrayKeys);
1349  Assert(so->qual_ok);
1350 
1351  for (i = 0; i < so->numArrayKeys; i++)
1352  {
1353  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
1354  ScanKey skey = &so->keyData[curArrayKey->scan_key];
1355 
1356  Assert(curArrayKey->num_elems > 0);
1357  Assert(skey->sk_flags & SK_SEARCHARRAY);
1358 
1359  if (ScanDirectionIsBackward(dir))
1360  curArrayKey->cur_elem = curArrayKey->num_elems - 1;
1361  else
1362  curArrayKey->cur_elem = 0;
1363  skey->sk_argument = curArrayKey->elem_values[curArrayKey->cur_elem];
1364  }
1365  so->scanBehind = false;
1366 }
1367 
1368 /*
1369  * _bt_advance_array_keys_increment() -- Advance to next set of array elements
1370  *
1371  * Advances the array keys by a single increment in the current scan
1372  * direction. When there are multiple array keys this can roll over from the
1373  * lowest order array to higher order arrays.
1374  *
1375  * Returns true if there is another set of values to consider, false if not.
1376  * On true result, the scankeys are initialized with the next set of values.
1377  * On false result, the scankeys stay the same, and the array keys are not
1378  * advanced (every array remains at its final element for scan direction).
1379  */
1380 static bool
1382 {
1383  BTScanOpaque so = (BTScanOpaque) scan->opaque;
1384 
1385  /*
1386  * We must advance the last array key most quickly, since it will
1387  * correspond to the lowest-order index column among the available
1388  * qualifications
1389  */
1390  for (int i = so->numArrayKeys - 1; i >= 0; i--)
1391  {
1392  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
1393  ScanKey skey = &so->keyData[curArrayKey->scan_key];
1394  int cur_elem = curArrayKey->cur_elem;
1395  int num_elems = curArrayKey->num_elems;
1396  bool rolled = false;
1397 
1398  if (ScanDirectionIsForward(dir) && ++cur_elem >= num_elems)
1399  {
1400  cur_elem = 0;
1401  rolled = true;
1402  }
1403  else if (ScanDirectionIsBackward(dir) && --cur_elem < 0)
1404  {
1405  cur_elem = num_elems - 1;
1406  rolled = true;
1407  }
1408 
1409  curArrayKey->cur_elem = cur_elem;
1410  skey->sk_argument = curArrayKey->elem_values[cur_elem];
1411  if (!rolled)
1412  return true;
1413 
1414  /* Need to advance next array key, if any */
1415  }
1416 
1417  /*
1418  * The array keys are now exhausted. (There isn't actually a distinct
1419  * state that represents array exhaustion, since index scans don't always
1420  * end after btgettuple returns "false".)
1421  *
1422  * Restore the array keys to the state they were in immediately before we
1423  * were called. This ensures that the arrays only ever ratchet in the
1424  * current scan direction. Without this, scans would overlook matching
1425  * tuples if and when the scan's direction was subsequently reversed.
1426  */
1427  _bt_start_array_keys(scan, -dir);
1428 
1429  return false;
1430 }
1431 
1432 /*
1433  * _bt_rewind_nonrequired_arrays() -- Rewind non-required arrays
1434  *
1435  * Called when _bt_advance_array_keys decides to start a new primitive index
1436  * scan on the basis of the current scan position being before the position
1437  * that _bt_first is capable of repositioning the scan to by applying an
1438  * inequality operator required in the opposite-to-scan direction only.
1439  *
1440  * Although equality strategy scan keys (for both arrays and non-arrays alike)
1441  * are either marked required in both directions or in neither direction,
1442  * there is a sense in which non-required arrays behave like required arrays.
1443  * With a qual such as "WHERE a IN (100, 200) AND b >= 3 AND c IN (5, 6, 7)",
1444  * the scan key on "c" is non-required, but nevertheless enables positioning
1445  * the scan at the first tuple >= "(100, 3, 5)" on the leaf level during the
1446  * first descent of the tree by _bt_first. Later on, there could also be a
1447  * second descent, that places the scan right before tuples >= "(200, 3, 5)".
1448  * _bt_first must never be allowed to build an insertion scan key whose "c"
1449  * entry is set to a value other than 5, the "c" array's first element/value.
1450  * (Actually, it's the first in the current scan direction. This example uses
1451  * a forward scan.)
1452  *
1453  * Calling here resets the array scan key elements for the scan's non-required
1454  * arrays. This is strictly necessary for correctness in a subset of cases
1455  * involving "required in opposite direction"-triggered primitive index scans.
1456  * Not all callers are at risk of _bt_first using a non-required array like
1457  * this, but advancement always resets the arrays when another primitive scan
1458  * is scheduled, just to keep things simple. Array advancement even makes
1459  * sure to reset non-required arrays during scans that have no inequalities.
1460  * (Advancement still won't call here when there are no inequalities, though
1461  * that's just because it's all handled indirectly instead.)
1462  *
1463  * Note: _bt_verify_arrays_bt_first is called by an assertion to enforce that
1464  * everybody got this right.
1465  */
1466 static void
1468 {
1469  BTScanOpaque so = (BTScanOpaque) scan->opaque;
1470  int arrayidx = 0;
1471 
1472  for (int ikey = 0; ikey < so->numberOfKeys; ikey++)
1473  {
1474  ScanKey cur = so->keyData + ikey;
1475  BTArrayKeyInfo *array = NULL;
1476  int first_elem_dir;
1477 
1478  if (!(cur->sk_flags & SK_SEARCHARRAY) ||
1479  cur->sk_strategy != BTEqualStrategyNumber)
1480  continue;
1481 
1482  array = &so->arrayKeys[arrayidx++];
1483  Assert(array->scan_key == ikey);
1484 
1485  if ((cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)))
1486  continue;
1487 
1488  if (ScanDirectionIsForward(dir))
1489  first_elem_dir = 0;
1490  else
1491  first_elem_dir = array->num_elems - 1;
1492 
1493  if (array->cur_elem != first_elem_dir)
1494  {
1495  array->cur_elem = first_elem_dir;
1496  cur->sk_argument = array->elem_values[first_elem_dir];
1497  }
1498  }
1499 }
1500 
1501 /*
1502  * _bt_tuple_before_array_skeys() -- too early to advance required arrays?
1503  *
1504  * We always compare the tuple using the current array keys (which we assume
1505  * are already set in so->keyData[]). readpagetup indicates if tuple is the
1506  * scan's current _bt_readpage-wise tuple.
1507  *
1508  * readpagetup callers must only call here when _bt_check_compare already set
1509  * continuescan=false. We help these callers deal with _bt_check_compare's
1510  * inability to distinguishing between the < and > cases (it uses equality
1511  * operator scan keys, whereas we use 3-way ORDER procs). These callers pass
1512  * a _bt_check_compare-set sktrig value that indicates which scan key
1513  * triggered the call (!readpagetup callers just pass us sktrig=0 instead).
1514  * This information allows us to avoid wastefully checking earlier scan keys
1515  * that were already deemed to have been satisfied inside _bt_check_compare.
1516  *
1517  * Returns false when caller's tuple is >= the current required equality scan
1518  * keys (or <=, in the case of backwards scans). This happens to readpagetup
1519  * callers when the scan has reached the point of needing its array keys
1520  * advanced; caller will need to advance required and non-required arrays at
1521  * scan key offsets >= sktrig, plus scan keys < sktrig iff sktrig rolls over.
1522  * (When we return false to readpagetup callers, tuple can only be == current
1523  * required equality scan keys when caller's sktrig indicates that the arrays
1524  * need to be advanced due to an unsatisfied required inequality key trigger.)
1525  *
1526  * Returns true when caller passes a tuple that is < the current set of
1527  * equality keys for the most significant non-equal required scan key/column
1528  * (or > the keys, during backwards scans). This happens to readpagetup
1529  * callers when tuple is still before the start of matches for the scan's
1530  * required equality strategy scan keys. (sktrig can't have indicated that an
1531  * inequality strategy scan key wasn't satisfied in _bt_check_compare when we
1532  * return true. In fact, we automatically return false when passed such an
1533  * inequality sktrig by readpagetup callers -- _bt_check_compare's initial
1534  * continuescan=false doesn't really need to be confirmed here by us.)
1535  *
1536  * !readpagetup callers optionally pass us *scanBehind, which tracks whether
1537  * any missing truncated attributes might have affected array advancement
1538  * (compared to what would happen if it was shown the first non-pivot tuple on
1539  * the page to the right of caller's finaltup/high key tuple instead). It's
1540  * only possible that we'll set *scanBehind to true when caller passes us a
1541  * pivot tuple (with truncated -inf attributes) that we return false for.
1542  */
1543 static bool
1545  IndexTuple tuple, TupleDesc tupdesc, int tupnatts,
1546  bool readpagetup, int sktrig, bool *scanBehind)
1547 {
1548  BTScanOpaque so = (BTScanOpaque) scan->opaque;
1549 
1550  Assert(so->numArrayKeys);
1551  Assert(so->numberOfKeys);
1552  Assert(sktrig == 0 || readpagetup);
1553  Assert(!readpagetup || scanBehind == NULL);
1554 
1555  if (scanBehind)
1556  *scanBehind = false;
1557 
1558  for (int ikey = sktrig; ikey < so->numberOfKeys; ikey++)
1559  {
1560  ScanKey cur = so->keyData + ikey;
1561  Datum tupdatum;
1562  bool tupnull;
1563  int32 result;
1564 
1565  /* readpagetup calls require one ORDER proc comparison (at most) */
1566  Assert(!readpagetup || ikey == sktrig);
1567 
1568  /*
1569  * Once we reach a non-required scan key, we're completely done.
1570  *
1571  * Note: we deliberately don't consider the scan direction here.
1572  * _bt_advance_array_keys caller requires that we track *scanBehind
1573  * without concern for scan direction.
1574  */
1575  if ((cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) == 0)
1576  {
1577  Assert(!readpagetup);
1578  Assert(ikey > sktrig || ikey == 0);
1579  return false;
1580  }
1581 
1582  if (cur->sk_attno > tupnatts)
1583  {
1584  Assert(!readpagetup);
1585 
1586  /*
1587  * When we reach a high key's truncated attribute, assume that the
1588  * tuple attribute's value is >= the scan's equality constraint
1589  * scan keys (but set *scanBehind to let interested callers know
1590  * that a truncated attribute might have affected our answer).
1591  */
1592  if (scanBehind)
1593  *scanBehind = true;
1594 
1595  return false;
1596  }
1597 
1598  /*
1599  * Deal with inequality strategy scan keys that _bt_check_compare set
1600  * continuescan=false for
1601  */
1602  if (cur->sk_strategy != BTEqualStrategyNumber)
1603  {
1604  /*
1605  * When _bt_check_compare indicated that a required inequality
1606  * scan key wasn't satisfied, there's no need to verify anything;
1607  * caller always calls _bt_advance_array_keys with this sktrig.
1608  */
1609  if (readpagetup)
1610  return false;
1611 
1612  /*
1613  * Otherwise we can't give up, since we must check all required
1614  * scan keys (required in either direction) in order to correctly
1615  * track *scanBehind for caller
1616  */
1617  continue;
1618  }
1619 
1620  tupdatum = index_getattr(tuple, cur->sk_attno, tupdesc, &tupnull);
1621 
1622  result = _bt_compare_array_skey(&so->orderProcs[ikey],
1623  tupdatum, tupnull,
1624  cur->sk_argument, cur);
1625 
1626  /*
1627  * Does this comparison indicate that caller must _not_ advance the
1628  * scan's arrays just yet?
1629  */
1630  if ((ScanDirectionIsForward(dir) && result < 0) ||
1631  (ScanDirectionIsBackward(dir) && result > 0))
1632  return true;
1633 
1634  /*
1635  * Does this comparison indicate that caller should now advance the
1636  * scan's arrays? (Must be if we get here during a readpagetup call.)
1637  */
1638  if (readpagetup || result != 0)
1639  {
1640  Assert(result != 0);
1641  return false;
1642  }
1643 
1644  /*
1645  * Inconclusive -- need to check later scan keys, too.
1646  *
1647  * This must be a finaltup precheck, or a call made from an assertion.
1648  */
1649  Assert(result == 0);
1650  }
1651 
1652  Assert(!readpagetup);
1653 
1654  return false;
1655 }
1656 
1657 /*
1658  * _bt_start_prim_scan() -- start scheduled primitive index scan?
1659  *
1660  * Returns true if _bt_checkkeys scheduled another primitive index scan, just
1661  * as the last one ended. Otherwise returns false, indicating that the array
1662  * keys are now fully exhausted.
1663  *
1664  * Only call here during scans with one or more equality type array scan keys,
1665  * after _bt_first or _bt_next return false.
1666  */
1667 bool
1669 {
1670  BTScanOpaque so = (BTScanOpaque) scan->opaque;
1671 
1672  Assert(so->numArrayKeys);
1673 
1674  /* scanBehind flag doesn't persist across primitive index scans - reset */
1675  so->scanBehind = false;
1676 
1677  /*
1678  * Array keys are advanced within _bt_checkkeys when the scan reaches the
1679  * leaf level (more precisely, they're advanced when the scan reaches the
1680  * end of each distinct set of array elements). This process avoids
1681  * repeat access to leaf pages (across multiple primitive index scans) by
1682  * advancing the scan's array keys when it allows the primitive index scan
1683  * to find nearby matching tuples (or when it eliminates ranges of array
1684  * key space that can't possibly be satisfied by any index tuple).
1685  *
1686  * _bt_checkkeys sets a simple flag variable to schedule another primitive
1687  * index scan. The flag tells us what to do.
1688  *
1689  * We cannot rely on _bt_first always reaching _bt_checkkeys. There are
1690  * various cases where that won't happen. For example, if the index is
1691  * completely empty, then _bt_first won't call _bt_readpage/_bt_checkkeys.
1692  * We also don't expect a call to _bt_checkkeys during searches for a
1693  * non-existent value that happens to be lower/higher than any existing
1694  * value in the index.
1695  *
1696  * We don't require special handling for these cases -- we don't need to
1697  * be explicitly instructed to _not_ perform another primitive index scan.
1698  * It's up to code under the control of _bt_first to always set the flag
1699  * when another primitive index scan will be required.
1700  *
1701  * This works correctly, even with the tricky cases listed above, which
1702  * all involve access to leaf pages "near the boundaries of the key space"
1703  * (whether it's from a leftmost/rightmost page, or an imaginary empty
1704  * leaf root page). If _bt_checkkeys cannot be reached by a primitive
1705  * index scan for one set of array keys, then it also won't be reached for
1706  * any later set ("later" in terms of the direction that we scan the index
1707  * and advance the arrays). The array keys won't have advanced in these
1708  * cases, but that's the correct behavior (even _bt_advance_array_keys
1709  * won't always advance the arrays at the point they become "exhausted").
1710  */
1711  if (so->needPrimScan)
1712  {
1713  Assert(_bt_verify_arrays_bt_first(scan, dir));
1714 
1715  /*
1716  * Flag was set -- must call _bt_first again, which will reset the
1717  * scan's needPrimScan flag
1718  */
1719  return true;
1720  }
1721 
1722  /* The top-level index scan ran out of tuples in this scan direction */
1723  if (scan->parallel_scan != NULL)
1724  _bt_parallel_done(scan);
1725 
1726  return false;
1727 }
1728 
1729 /*
1730  * _bt_advance_array_keys() -- Advance array elements using a tuple
1731  *
1732  * The scan always gets a new qual as a consequence of calling here (except
1733  * when we determine that the top-level scan has run out of matching tuples).
1734  * All later _bt_check_compare calls also use the same new qual that was first
1735  * used here (at least until the next call here advances the keys once again).
1736  * It's convenient to structure _bt_check_compare rechecks of caller's tuple
1737  * (using the new qual) as one the steps of advancing the scan's array keys,
1738  * so this function works as a wrapper around _bt_check_compare.
1739  *
1740  * Like _bt_check_compare, we'll set pstate.continuescan on behalf of the
1741  * caller, and return a boolean indicating if caller's tuple satisfies the
1742  * scan's new qual. But unlike _bt_check_compare, we set so->needPrimScan
1743  * when we set continuescan=false, indicating if a new primitive index scan
1744  * has been scheduled (otherwise, the top-level scan has run out of tuples in
1745  * the current scan direction).
1746  *
1747  * Caller must use _bt_tuple_before_array_skeys to determine if the current
1748  * place in the scan is >= the current array keys _before_ calling here.
1749  * We're responsible for ensuring that caller's tuple is <= the newly advanced
1750  * required array keys once we return. We try to find an exact match, but
1751  * failing that we'll advance the array keys to whatever set of array elements
1752  * comes next in the key space for the current scan direction. Required array
1753  * keys "ratchet forwards" (or backwards). They can only advance as the scan
1754  * itself advances through the index/key space.
1755  *
1756  * (The rules are the same for backwards scans, except that the operators are
1757  * flipped: just replace the precondition's >= operator with a <=, and the
1758  * postcondition's <= operator with a >=. In other words, just swap the
1759  * precondition with the postcondition.)
1760  *
1761  * We also deal with "advancing" non-required arrays here. Callers whose
1762  * sktrig scan key is non-required specify sktrig_required=false. These calls
1763  * are the only exception to the general rule about always advancing the
1764  * required array keys (the scan may not even have a required array). These
1765  * callers should just pass a NULL pstate (since there is never any question
1766  * of stopping the scan). No call to _bt_tuple_before_array_skeys is required
1767  * ahead of these calls (it's already clear that any required scan keys must
1768  * be satisfied by caller's tuple).
1769  *
1770  * Note that we deal with non-array required equality strategy scan keys as
1771  * degenerate single element arrays here. Obviously, they can never really
1772  * advance in the way that real arrays can, but they must still affect how we
1773  * advance real array scan keys (exactly like true array equality scan keys).
1774  * We have to keep around a 3-way ORDER proc for these (using the "=" operator
1775  * won't do), since in general whether the tuple is < or > _any_ unsatisfied
1776  * required equality key influences how the scan's real arrays must advance.
1777  *
1778  * Note also that we may sometimes need to advance the array keys when the
1779  * existing required array keys (and other required equality keys) are already
1780  * an exact match for every corresponding value from caller's tuple. We must
1781  * do this for inequalities that _bt_check_compare set continuescan=false for.
1782  * They'll advance the array keys here, just like any other scan key that
1783  * _bt_check_compare stops on. (This can even happen _after_ we advance the
1784  * array keys, in which case we'll advance the array keys a second time. That
1785  * way _bt_checkkeys caller always has its required arrays advance to the
1786  * maximum possible extent that its tuple will allow.)
1787  */
1788 static bool
1790  IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
1791  int sktrig, bool sktrig_required)
1792 {
1793  BTScanOpaque so = (BTScanOpaque) scan->opaque;
1794  Relation rel = scan->indexRelation;
1795  ScanDirection dir = pstate ? pstate->dir : ForwardScanDirection;
1796  int arrayidx = 0;
1797  bool beyond_end_advance = false,
1798  has_required_opposite_direction_only = false,
1799  oppodir_inequality_sktrig = false,
1800  all_required_satisfied = true,
1801  all_satisfied = true;
1802 
1803  if (sktrig_required)
1804  {
1805  /*
1806  * Precondition array state assertion
1807  */
1808  Assert(!_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc,
1809  tupnatts, false, 0, NULL));
1810 
1811  so->scanBehind = false; /* reset */
1812 
1813  /*
1814  * Required scan key wasn't satisfied, so required arrays will have to
1815  * advance. Invalidate page-level state that tracks whether the
1816  * scan's required-in-opposite-direction-only keys are known to be
1817  * satisfied by page's remaining tuples.
1818  */
1819  pstate->firstmatch = false;
1820 
1821  /* Shouldn't have to invalidate 'prechecked', though */
1822  Assert(!pstate->prechecked);
1823 
1824  /*
1825  * Once we return we'll have a new set of required array keys, so
1826  * reset state used by "look ahead" optimization
1827  */
1828  pstate->rechecks = 0;
1829  pstate->targetdistance = 0;
1830  }
1831 
1832  Assert(_bt_verify_keys_with_arraykeys(scan));
1833 
1834  for (int ikey = 0; ikey < so->numberOfKeys; ikey++)
1835  {
1836  ScanKey cur = so->keyData + ikey;
1837  BTArrayKeyInfo *array = NULL;
1838  Datum tupdatum;
1839  bool required = false,
1840  required_opposite_direction_only = false,
1841  tupnull;
1842  int32 result;
1843  int set_elem = 0;
1844 
1845  if (cur->sk_strategy == BTEqualStrategyNumber)
1846  {
1847  /* Manage array state */
1848  if (cur->sk_flags & SK_SEARCHARRAY)
1849  {
1850  array = &so->arrayKeys[arrayidx++];
1851  Assert(array->scan_key == ikey);
1852  }
1853  }
1854  else
1855  {
1856  /*
1857  * Are any inequalities required in the opposite direction only
1858  * present here?
1859  */
1860  if (((ScanDirectionIsForward(dir) &&
1861  (cur->sk_flags & (SK_BT_REQBKWD))) ||
1862  (ScanDirectionIsBackward(dir) &&
1863  (cur->sk_flags & (SK_BT_REQFWD)))))
1864  has_required_opposite_direction_only =
1865  required_opposite_direction_only = true;
1866  }
1867 
1868  /* Optimization: skip over known-satisfied scan keys */
1869  if (ikey < sktrig)
1870  continue;
1871 
1872  if (cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))
1873  {
1874  Assert(sktrig_required);
1875 
1876  required = true;
1877 
1878  if (cur->sk_attno > tupnatts)
1879  {
1880  /* Set this just like _bt_tuple_before_array_skeys */
1881  Assert(sktrig < ikey);
1882  so->scanBehind = true;
1883  }
1884  }
1885 
1886  /*
1887  * Handle a required non-array scan key that the initial call to
1888  * _bt_check_compare indicated triggered array advancement, if any.
1889  *
1890  * The non-array scan key's strategy will be <, <=, or = during a
1891  * forwards scan (or any one of =, >=, or > during a backwards scan).
1892  * It follows that the corresponding tuple attribute's value must now
1893  * be either > or >= the scan key value (for backwards scans it must
1894  * be either < or <= that value).
1895  *
1896  * If this is a required equality strategy scan key, this is just an
1897  * optimization; _bt_tuple_before_array_skeys already confirmed that
1898  * this scan key places us ahead of caller's tuple. There's no need
1899  * to repeat that work now. (The same underlying principle also gets
1900  * applied by the cur_elem_trig optimization used to speed up searches
1901  * for the next array element.)
1902  *
1903  * If this is a required inequality strategy scan key, we _must_ rely
1904  * on _bt_check_compare like this; we aren't capable of directly
1905  * evaluating required inequality strategy scan keys here, on our own.
1906  */
1907  if (ikey == sktrig && !array)
1908  {
1909  Assert(sktrig_required && required && all_required_satisfied);
1910 
1911  /* Use "beyond end" advancement. See below for an explanation. */
1912  beyond_end_advance = true;
1913  all_satisfied = all_required_satisfied = false;
1914 
1915  /*
1916  * Set a flag that remembers that this was an inequality required
1917  * in the opposite scan direction only, that nevertheless
1918  * triggered the call here.
1919  *
1920  * This only happens when an inequality operator (which must be
1921  * strict) encounters a group of NULLs that indicate the end of
1922  * non-NULL values for tuples in the current scan direction.
1923  */
1924  if (unlikely(required_opposite_direction_only))
1925  oppodir_inequality_sktrig = true;
1926 
1927  continue;
1928  }
1929 
1930  /*
1931  * Nothing more for us to do with an inequality strategy scan key that
1932  * wasn't the one that _bt_check_compare stopped on, though.
1933  *
1934  * Note: if our later call to _bt_check_compare (to recheck caller's
1935  * tuple) sets continuescan=false due to finding this same inequality
1936  * unsatisfied (possible when it's required in the scan direction),
1937  * we'll deal with it via a recursive "second pass" call.
1938  */
1939  else if (cur->sk_strategy != BTEqualStrategyNumber)
1940  continue;
1941 
1942  /*
1943  * Nothing for us to do with an equality strategy scan key that isn't
1944  * marked required, either -- unless it's a non-required array
1945  */
1946  else if (!required && !array)
1947  continue;
1948 
1949  /*
1950  * Here we perform steps for all array scan keys after a required
1951  * array scan key whose binary search triggered "beyond end of array
1952  * element" array advancement due to encountering a tuple attribute
1953  * value > the closest matching array key (or < for backwards scans).
1954  */
1955  if (beyond_end_advance)
1956  {
1957  int final_elem_dir;
1958 
1959  if (ScanDirectionIsBackward(dir) || !array)
1960  final_elem_dir = 0;
1961  else
1962  final_elem_dir = array->num_elems - 1;
1963 
1964  if (array && array->cur_elem != final_elem_dir)
1965  {
1966  array->cur_elem = final_elem_dir;
1967  cur->sk_argument = array->elem_values[final_elem_dir];
1968  }
1969 
1970  continue;
1971  }
1972 
1973  /*
1974  * Here we perform steps for all array scan keys after a required
1975  * array scan key whose tuple attribute was < the closest matching
1976  * array key when we dealt with it (or > for backwards scans).
1977  *
1978  * This earlier required array key already puts us ahead of caller's
1979  * tuple in the key space (for the current scan direction). We must
1980  * make sure that subsequent lower-order array keys do not put us too
1981  * far ahead (ahead of tuples that have yet to be seen by our caller).
1982  * For example, when a tuple "(a, b) = (42, 5)" advances the array
1983  * keys on "a" from 40 to 45, we must also set "b" to whatever the
1984  * first array element for "b" is. It would be wrong to allow "b" to
1985  * be set based on the tuple value.
1986  *
1987  * Perform the same steps with truncated high key attributes. You can
1988  * think of this as a "binary search" for the element closest to the
1989  * value -inf. Again, the arrays must never get ahead of the scan.
1990  */
1991  if (!all_required_satisfied || cur->sk_attno > tupnatts)
1992  {
1993  int first_elem_dir;
1994 
1995  if (ScanDirectionIsForward(dir) || !array)
1996  first_elem_dir = 0;
1997  else
1998  first_elem_dir = array->num_elems - 1;
1999 
2000  if (array && array->cur_elem != first_elem_dir)
2001  {
2002  array->cur_elem = first_elem_dir;
2003  cur->sk_argument = array->elem_values[first_elem_dir];
2004  }
2005 
2006  continue;
2007  }
2008 
2009  /*
2010  * Search in scankey's array for the corresponding tuple attribute
2011  * value from caller's tuple
2012  */
2013  tupdatum = index_getattr(tuple, cur->sk_attno, tupdesc, &tupnull);
2014 
2015  if (array)
2016  {
2017  bool cur_elem_trig = (sktrig_required && ikey == sktrig);
2018 
2019  /*
2020  * Binary search for closest match that's available from the array
2021  */
2022  set_elem = _bt_binsrch_array_skey(&so->orderProcs[ikey],
2023  cur_elem_trig, dir,
2024  tupdatum, tupnull, array, cur,
2025  &result);
2026 
2027  Assert(set_elem >= 0 && set_elem < array->num_elems);
2028  }
2029  else
2030  {
2031  Assert(sktrig_required && required);
2032 
2033  /*
2034  * This is a required non-array equality strategy scan key, which
2035  * we'll treat as a degenerate single element array.
2036  *
2037  * This scan key's imaginary "array" can't really advance, but it
2038  * can still roll over like any other array. (Actually, this is
2039  * no different to real single value arrays, which never advance
2040  * without rolling over -- they can never truly advance, either.)
2041  */
2042  result = _bt_compare_array_skey(&so->orderProcs[ikey],
2043  tupdatum, tupnull,
2044  cur->sk_argument, cur);
2045  }
2046 
2047  /*
2048  * Consider "beyond end of array element" array advancement.
2049  *
2050  * When the tuple attribute value is > the closest matching array key
2051  * (or < in the backwards scan case), we need to ratchet this array
2052  * forward (backward) by one increment, so that caller's tuple ends up
2053  * being < final array value instead (or > final array value instead).
2054  * This process has to work for all of the arrays, not just this one:
2055  * it must "carry" to higher-order arrays when the set_elem that we
2056  * just found happens to be the final one for the scan's direction.
2057  * Incrementing (decrementing) set_elem itself isn't good enough.
2058  *
2059  * Our approach is to provisionally use set_elem as if it was an exact
2060  * match now, then set each later/less significant array to whatever
2061  * its final element is. Once outside the loop we'll then "increment
2062  * this array's set_elem" by calling _bt_advance_array_keys_increment.
2063  * That way the process rolls over to higher order arrays as needed.
2064  *
2065  * Under this scheme any required arrays only ever ratchet forwards
2066  * (or backwards), and always do so to the maximum possible extent
2067  * that we can know will be safe without seeing the scan's next tuple.
2068  * We don't need any special handling for required scan keys that lack
2069  * a real array to advance, nor for redundant scan keys that couldn't
2070  * be eliminated by _bt_preprocess_keys. It won't matter if some of
2071  * our "true" array scan keys (or even all of them) are non-required.
2072  */
2073  if (required &&
2074  ((ScanDirectionIsForward(dir) && result > 0) ||
2075  (ScanDirectionIsBackward(dir) && result < 0)))
2076  beyond_end_advance = true;
2077 
2078  Assert(all_required_satisfied && all_satisfied);
2079  if (result != 0)
2080  {
2081  /*
2082  * Track whether caller's tuple satisfies our new post-advancement
2083  * qual, for required scan keys, as well as for the entire set of
2084  * interesting scan keys (all required scan keys plus non-required
2085  * array scan keys are considered interesting.)
2086  */
2087  all_satisfied = false;
2088  if (required)
2089  all_required_satisfied = false;
2090  else
2091  {
2092  /*
2093  * There's no need to advance the arrays using the best
2094  * available match for a non-required array. Give up now.
2095  * (Though note that sktrig_required calls still have to do
2096  * all the usual post-advancement steps, including the recheck
2097  * call to _bt_check_compare.)
2098  */
2099  break;
2100  }
2101  }
2102 
2103  /* Advance array keys, even when set_elem isn't an exact match */
2104  if (array && array->cur_elem != set_elem)
2105  {
2106  array->cur_elem = set_elem;
2107  cur->sk_argument = array->elem_values[set_elem];
2108  }
2109  }
2110 
2111  /*
2112  * Advance the array keys incrementally whenever "beyond end of array
2113  * element" array advancement happens, so that advancement will carry to
2114  * higher-order arrays (might exhaust all the scan's arrays instead, which
2115  * ends the top-level scan).
2116  */
2117  if (beyond_end_advance && !_bt_advance_array_keys_increment(scan, dir))
2118  goto end_toplevel_scan;
2119 
2120  Assert(_bt_verify_keys_with_arraykeys(scan));
2121 
2122  /*
2123  * Does tuple now satisfy our new qual? Recheck with _bt_check_compare.
2124  *
2125  * Calls triggered by an unsatisfied required scan key, whose tuple now
2126  * satisfies all required scan keys, but not all nonrequired array keys,
2127  * will still require a recheck call to _bt_check_compare. They'll still
2128  * need its "second pass" handling of required inequality scan keys.
2129  * (Might have missed a still-unsatisfied required inequality scan key
2130  * that caller didn't detect as the sktrig scan key during its initial
2131  * _bt_check_compare call that used the old/original qual.)
2132  *
2133  * Calls triggered by an unsatisfied nonrequired array scan key never need
2134  * "second pass" handling of required inequalities (nor any other handling
2135  * of any required scan key). All that matters is whether caller's tuple
2136  * satisfies the new qual, so it's safe to just skip the _bt_check_compare
2137  * recheck when we've already determined that it can only return 'false'.
2138  */
2139  if ((sktrig_required && all_required_satisfied) ||
2140  (!sktrig_required && all_satisfied))
2141  {
2142  int nsktrig = sktrig + 1;
2143  bool continuescan;
2144 
2145  Assert(all_required_satisfied);
2146 
2147  /* Recheck _bt_check_compare on behalf of caller */
2148  if (_bt_check_compare(scan, dir, tuple, tupnatts, tupdesc,
2149  false, false, false,
2150  &continuescan, &nsktrig) &&
2151  !so->scanBehind)
2152  {
2153  /* This tuple satisfies the new qual */
2154  Assert(all_satisfied && continuescan);
2155 
2156  if (pstate)
2157  pstate->continuescan = true;
2158 
2159  return true;
2160  }
2161 
2162  /*
2163  * Consider "second pass" handling of required inequalities.
2164  *
2165  * It's possible that our _bt_check_compare call indicated that the
2166  * scan should end due to some unsatisfied inequality that wasn't
2167  * initially recognized as such by us. Handle this by calling
2168  * ourselves recursively, this time indicating that the trigger is the
2169  * inequality that we missed first time around (and using a set of
2170  * required array/equality keys that are now exact matches for tuple).
2171  *
2172  * We make a strong, general guarantee that every _bt_checkkeys call
2173  * here will advance the array keys to the maximum possible extent
2174  * that we can know to be safe based on caller's tuple alone. If we
2175  * didn't perform this step, then that guarantee wouldn't quite hold.
2176  */
2177  if (unlikely(!continuescan))
2178  {
2179  bool satisfied PG_USED_FOR_ASSERTS_ONLY;
2180 
2181  Assert(sktrig_required);
2183 
2184  /*
2185  * The tuple must use "beyond end" advancement during the
2186  * recursive call, so we cannot possibly end up back here when
2187  * recursing. We'll consume a small, fixed amount of stack space.
2188  */
2189  Assert(!beyond_end_advance);
2190 
2191  /* Advance the array keys a second time using same tuple */
2192  satisfied = _bt_advance_array_keys(scan, pstate, tuple, tupnatts,
2193  tupdesc, nsktrig, true);
2194 
2195  /* This tuple doesn't satisfy the inequality */
2196  Assert(!satisfied);
2197  return false;
2198  }
2199 
2200  /*
2201  * Some non-required scan key (from new qual) still not satisfied.
2202  *
2203  * All scan keys required in the current scan direction must still be
2204  * satisfied, though, so we can trust all_required_satisfied below.
2205  */
2206  }
2207 
2208  /*
2209  * When we were called just to deal with "advancing" non-required arrays,
2210  * this is as far as we can go (cannot stop the scan for these callers)
2211  */
2212  if (!sktrig_required)
2213  {
2214  /* Caller's tuple doesn't match any qual */
2215  return false;
2216  }
2217 
2218  /*
2219  * Postcondition array state assertion (for still-unsatisfied tuples).
2220  *
2221  * By here we have established that the scan's required arrays (scan must
2222  * have at least one required array) advanced, without becoming exhausted.
2223  *
2224  * Caller's tuple is now < the newly advanced array keys (or > when this
2225  * is a backwards scan), except in the case where we only got this far due
2226  * to an unsatisfied non-required scan key. Verify that with an assert.
2227  *
2228  * Note: we don't just quit at this point when all required scan keys were
2229  * found to be satisfied because we need to consider edge-cases involving
2230  * scan keys required in the opposite direction only; those aren't tracked
2231  * by all_required_satisfied. (Actually, oppodir_inequality_sktrig trigger
2232  * scan keys are tracked by all_required_satisfied, since it's convenient
2233  * for _bt_check_compare to behave as if they are required in the current
2234  * scan direction to deal with NULLs. We'll account for that separately.)
2235  */
2236  Assert(_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc, tupnatts,
2237  false, 0, NULL) ==
2238  !all_required_satisfied);
2239 
2240  /*
2241  * We generally permit primitive index scans to continue onto the next
2242  * sibling page when the page's finaltup satisfies all required scan keys
2243  * at the point where we're between pages.
2244  *
2245  * If caller's tuple is also the page's finaltup, and we see that required
2246  * scan keys still aren't satisfied, start a new primitive index scan.
2247  */
2248  if (!all_required_satisfied && pstate->finaltup == tuple)
2249  goto new_prim_scan;
2250 
2251  /*
2252  * Proactively check finaltup (don't wait until finaltup is reached by the
2253  * scan) when it might well turn out to not be satisfied later on.
2254  *
2255  * Note: if so->scanBehind hasn't already been set for finaltup by us,
2256  * it'll be set during this call to _bt_tuple_before_array_skeys. Either
2257  * way, it'll be set correctly (for the whole page) after this point.
2258  */
2259  if (!all_required_satisfied && pstate->finaltup &&
2260  _bt_tuple_before_array_skeys(scan, dir, pstate->finaltup, tupdesc,
2261  BTreeTupleGetNAtts(pstate->finaltup, rel),
2262  false, 0, &so->scanBehind))
2263  goto new_prim_scan;
2264 
2265  /*
2266  * When we encounter a truncated finaltup high key attribute, we're
2267  * optimistic about the chances of its corresponding required scan key
2268  * being satisfied when we go on to check it against tuples from this
2269  * page's right sibling leaf page. We consider truncated attributes to be
2270  * satisfied by required scan keys, which allows the primitive index scan
2271  * to continue to the next leaf page. We must set so->scanBehind to true
2272  * to remember that the last page's finaltup had "satisfied" required scan
2273  * keys for one or more truncated attribute values (scan keys required in
2274  * _either_ scan direction).
2275  *
2276  * There is a chance that _bt_checkkeys (which checks so->scanBehind) will
2277  * find that even the sibling leaf page's finaltup is < the new array
2278  * keys. When that happens, our optimistic policy will have incurred a
2279  * single extra leaf page access that could have been avoided.
2280  *
2281  * A pessimistic policy would give backward scans a gratuitous advantage
2282  * over forward scans. We'd punish forward scans for applying more
2283  * accurate information from the high key, rather than just using the
2284  * final non-pivot tuple as finaltup, in the style of backward scans.
2285  * Being pessimistic would also give some scans with non-required arrays a
2286  * perverse advantage over similar scans that use required arrays instead.
2287  *
2288  * You can think of this as a speculative bet on what the scan is likely
2289  * to find on the next page. It's not much of a gamble, though, since the
2290  * untruncated prefix of attributes must strictly satisfy the new qual
2291  * (though it's okay if any non-required scan keys fail to be satisfied).
2292  */
2293  if (so->scanBehind && has_required_opposite_direction_only)
2294  {
2295  /*
2296  * However, we avoid this behavior whenever the scan involves a scan
2297  * key required in the opposite direction to the scan only, along with
2298  * a finaltup with at least one truncated attribute that's associated
2299  * with a scan key marked required (required in either direction).
2300  *
2301  * _bt_check_compare simply won't stop the scan for a scan key that's
2302  * marked required in the opposite scan direction only. That leaves
2303  * us without any reliable way of reconsidering any opposite-direction
2304  * inequalities if it turns out that starting a new primitive index
2305  * scan will allow _bt_first to skip ahead by a great many leaf pages
2306  * (see next section for details of how that works).
2307  */
2308  goto new_prim_scan;
2309  }
2310 
2311  /*
2312  * Handle inequalities marked required in the opposite scan direction.
2313  * They can also signal that we should start a new primitive index scan.
2314  *
2315  * It's possible that the scan is now positioned where "matching" tuples
2316  * begin, and that caller's tuple satisfies all scan keys required in the
2317  * current scan direction. But if caller's tuple still doesn't satisfy
2318  * other scan keys that are required in the opposite scan direction only
2319  * (e.g., a required >= strategy scan key when scan direction is forward),
2320  * it's still possible that there are many leaf pages before the page that
2321  * _bt_first could skip straight to. Groveling through all those pages
2322  * will always give correct answers, but it can be very inefficient. We
2323  * must avoid needlessly scanning extra pages.
2324  *
2325  * Separately, it's possible that _bt_check_compare set continuescan=false
2326  * for a scan key that's required in the opposite direction only. This is
2327  * a special case, that happens only when _bt_check_compare sees that the
2328  * inequality encountered a NULL value. This signals the end of non-NULL
2329  * values in the current scan direction, which is reason enough to end the
2330  * (primitive) scan. If this happens at the start of a large group of
2331  * NULL values, then we shouldn't expect to be called again until after
2332  * the scan has already read indefinitely-many leaf pages full of tuples
2333  * with NULL suffix values. We need a separate test for this case so that
2334  * we don't miss our only opportunity to skip over such a group of pages.
2335  * (_bt_first is expected to skip over the group of NULLs by applying a
2336  * similar "deduce NOT NULL" rule, where it finishes its insertion scan
2337  * key by consing up an explicit SK_SEARCHNOTNULL key.)
2338  *
2339  * Apply a test against finaltup to detect and recover from these problem:
2340  * if even finaltup doesn't satisfy such an inequality, we just skip by
2341  * starting a new primitive index scan. When we skip, we know for sure
2342  * that all of the tuples on the current page following caller's tuple are
2343  * also before the _bt_first-wise start of tuples for our new qual. That
2344  * at least suggests many more skippable pages beyond the current page.
2345  */
2346  if (has_required_opposite_direction_only && pstate->finaltup &&
2347  (all_required_satisfied || oppodir_inequality_sktrig))
2348  {
2349  int nfinaltupatts = BTreeTupleGetNAtts(pstate->finaltup, rel);
2350  ScanDirection flipped;
2351  bool continuescanflip;
2352  int opsktrig;
2353 
2354  /*
2355  * We're checking finaltup (which is usually not caller's tuple), so
2356  * cannot reuse work from caller's earlier _bt_check_compare call.
2357  *
2358  * Flip the scan direction when calling _bt_check_compare this time,
2359  * so that it will set continuescanflip=false when it encounters an
2360  * inequality required in the opposite scan direction.
2361  */
2362  Assert(!so->scanBehind);
2363  opsktrig = 0;
2364  flipped = -dir;
2365  _bt_check_compare(scan, flipped,
2366  pstate->finaltup, nfinaltupatts, tupdesc,
2367  false, false, false,
2368  &continuescanflip, &opsktrig);
2369 
2370  /*
2371  * If we ended up here due to the all_required_satisfied criteria,
2372  * test opsktrig in a way that ensures that finaltup contains the same
2373  * prefix of key columns as caller's tuple (a prefix that satisfies
2374  * earlier required-in-current-direction scan keys).
2375  *
2376  * If we ended up here due to the oppodir_inequality_sktrig criteria,
2377  * test opsktrig in a way that ensures that the same scan key that our
2378  * caller found to be unsatisfied (by the scan's tuple) was also the
2379  * one unsatisfied just now (by finaltup). That way we'll only start
2380  * a new primitive scan when we're sure that both tuples _don't_ share
2381  * the same prefix of satisfied equality-constrained attribute values,
2382  * and that finaltup has a non-NULL attribute value indicated by the
2383  * unsatisfied scan key at offset opsktrig/sktrig. (This depends on
2384  * _bt_check_compare not caring about the direction that inequalities
2385  * are required in whenever NULL attribute values are unsatisfied. It
2386  * only cares about the scan direction, and its relationship to
2387  * whether NULLs are stored first or last relative to non-NULLs.)
2388  */
2389  Assert(all_required_satisfied != oppodir_inequality_sktrig);
2390  if (unlikely(!continuescanflip &&
2391  ((all_required_satisfied && opsktrig > sktrig) ||
2392  (oppodir_inequality_sktrig && opsktrig >= sktrig))))
2393  {
2394  Assert(so->keyData[opsktrig].sk_strategy != BTEqualStrategyNumber);
2395 
2396  /*
2397  * Make sure that any non-required arrays are set to the first
2398  * array element for the current scan direction
2399  */
2400  _bt_rewind_nonrequired_arrays(scan, dir);
2401 
2402  goto new_prim_scan;
2403  }
2404  }
2405 
2406  /*
2407  * Stick with the ongoing primitive index scan for now.
2408  *
2409  * It's possible that later tuples will also turn out to have values that
2410  * are still < the now-current array keys (or > the current array keys).
2411  * Our caller will handle this by performing what amounts to a linear
2412  * search of the page, implemented by calling _bt_check_compare and then
2413  * _bt_tuple_before_array_skeys for each tuple.
2414  *
2415  * This approach has various advantages over a binary search of the page.
2416  * Repeated binary searches of the page (one binary search for every array
2417  * advancement) won't outperform a continuous linear search. While there
2418  * are workloads that a naive linear search won't handle well, our caller
2419  * has a "look ahead" fallback mechanism to deal with that problem.
2420  */
2421  pstate->continuescan = true; /* Override _bt_check_compare */
2422  so->needPrimScan = false; /* _bt_readpage has more tuples to check */
2423 
2424  if (so->scanBehind)
2425  {
2426  /* Optimization: skip by setting "look ahead" mechanism's offnum */
2428  pstate->skip = pstate->maxoff + 1;
2429  }
2430 
2431  /* Caller's tuple doesn't match the new qual */
2432  return false;
2433 
2434 new_prim_scan:
2435 
2436  /*
2437  * End this primitive index scan, but schedule another.
2438  *
2439  * Note: If the scan direction happens to change, this scheduled primitive
2440  * index scan won't go ahead after all.
2441  */
2442  pstate->continuescan = false; /* Tell _bt_readpage we're done... */
2443  so->needPrimScan = true; /* ...but call _bt_first again */
2444 
2445  if (scan->parallel_scan)
2447 
2448  /* Caller's tuple doesn't match the new qual */
2449  return false;
2450 
2451 end_toplevel_scan:
2452 
2453  /*
2454  * End the current primitive index scan, but don't schedule another.
2455  *
2456  * This ends the entire top-level scan in the current scan direction.
2457  *
2458  * Note: The scan's arrays (including any non-required arrays) are now in
2459  * their final positions for the current scan direction. If the scan
2460  * direction happens to change, then the arrays will already be in their
2461  * first positions for what will then be the current scan direction.
2462  */
2463  pstate->continuescan = false; /* Tell _bt_readpage we're done... */
2464  so->needPrimScan = false; /* ...don't call _bt_first again, though */
2465 
2466  /* Caller's tuple doesn't match any qual */
2467  return false;
2468 }
2469 
2470 /*
2471  * _bt_preprocess_keys() -- Preprocess scan keys
2472  *
2473  * The given search-type keys (taken from scan->keyData[])
2474  * are copied to so->keyData[] with possible transformation.
2475  * scan->numberOfKeys is the number of input keys, so->numberOfKeys gets
2476  * the number of output keys (possibly less, never greater).
2477  *
2478  * The output keys are marked with additional sk_flags bits beyond the
2479  * system-standard bits supplied by the caller. The DESC and NULLS_FIRST
2480  * indoption bits for the relevant index attribute are copied into the flags.
2481  * Also, for a DESC column, we commute (flip) all the sk_strategy numbers
2482  * so that the index sorts in the desired direction.
2483  *
2484  * One key purpose of this routine is to discover which scan keys must be
2485  * satisfied to continue the scan. It also attempts to eliminate redundant
2486  * keys and detect contradictory keys. (If the index opfamily provides
2487  * incomplete sets of cross-type operators, we may fail to detect redundant
2488  * or contradictory keys, but we can survive that.)
2489  *
2490  * The output keys must be sorted by index attribute. Presently we expect
2491  * (but verify) that the input keys are already so sorted --- this is done
2492  * by match_clauses_to_index() in indxpath.c. Some reordering of the keys
2493  * within each attribute may be done as a byproduct of the processing here.
2494  * That process must leave array scan keys (within an attribute) in the same
2495  * order as corresponding entries from the scan's BTArrayKeyInfo array info.
2496  *
2497  * The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD
2498  * if they must be satisfied in order to continue the scan forward or backward
2499  * respectively. _bt_checkkeys uses these flags. For example, if the quals
2500  * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
2501  * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
2502  * But once we reach tuples like (1,4,z) we can stop scanning because no
2503  * later tuples could match. This is reflected by marking the x and y keys,
2504  * but not the z key, with SK_BT_REQFWD. In general, the keys for leading
2505  * attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD.
2506  * For the first attribute without an "=" key, any "<" and "<=" keys are
2507  * marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD.
2508  * This can be seen to be correct by considering the above example. Note
2509  * in particular that if there are no keys for a given attribute, the keys for
2510  * subsequent attributes can never be required; for instance "WHERE y = 4"
2511  * requires a full-index scan.
2512  *
2513  * If possible, redundant keys are eliminated: we keep only the tightest
2514  * >/>= bound and the tightest </<= bound, and if there's an = key then
2515  * that's the only one returned. (So, we return either a single = key,
2516  * or one or two boundary-condition keys for each attr.) However, if we
2517  * cannot compare two keys for lack of a suitable cross-type operator,
2518  * we cannot eliminate either. If there are two such keys of the same
2519  * operator strategy, the second one is just pushed into the output array
2520  * without further processing here. We may also emit both >/>= or both
2521  * </<= keys if we can't compare them. The logic about required keys still
2522  * works if we don't eliminate redundant keys.
2523  *
2524  * Note that one reason we need direction-sensitive required-key flags is
2525  * precisely that we may not be able to eliminate redundant keys. Suppose
2526  * we have "x > 4::int AND x > 10::bigint", and we are unable to determine
2527  * which key is more restrictive for lack of a suitable cross-type operator.
2528  * _bt_first will arbitrarily pick one of the keys to do the initial
2529  * positioning with. If it picks x > 4, then the x > 10 condition will fail
2530  * until we reach index entries > 10; but we can't stop the scan just because
2531  * x > 10 is failing. On the other hand, if we are scanning backwards, then
2532  * failure of either key is indeed enough to stop the scan. (In general, when
2533  * inequality keys are present, the initial-positioning code only promises to
2534  * position before the first possible match, not exactly at the first match,
2535  * for a forward scan; or after the last match for a backward scan.)
2536  *
2537  * As a byproduct of this work, we can detect contradictory quals such
2538  * as "x = 1 AND x > 2". If we see that, we return so->qual_ok = false,
2539  * indicating the scan need not be run at all since no tuples can match.
2540  * (In this case we do not bother completing the output key array!)
2541  * Again, missing cross-type operators might cause us to fail to prove the
2542  * quals contradictory when they really are, but the scan will work correctly.
2543  *
2544  * Row comparison keys are currently also treated without any smarts:
2545  * we just transfer them into the preprocessed array without any
2546  * editorialization. We can treat them the same as an ordinary inequality
2547  * comparison on the row's first index column, for the purposes of the logic
2548  * about required keys.
2549  *
2550  * Note: the reason we have to copy the preprocessed scan keys into private
2551  * storage is that we are modifying the array based on comparisons of the
2552  * key argument values, which could change on a rescan. Therefore we can't
2553  * overwrite the source data.
2554  */
2555 void
2557 {
2558  BTScanOpaque so = (BTScanOpaque) scan->opaque;
2559  int numberOfKeys = scan->numberOfKeys;
2560  int16 *indoption = scan->indexRelation->rd_indoption;
2561  int new_numberOfKeys;
2562  int numberOfEqualCols;
2563  ScanKey inkeys;
2564  ScanKey outkeys;
2565  ScanKey cur;
2567  bool test_result;
2568  int i,
2569  j;
2570  AttrNumber attno;
2571  ScanKey arrayKeyData;
2572  int *keyDataMap = NULL;
2573  int arrayidx = 0;
2574 
2575  if (so->numberOfKeys > 0)
2576  {
2577  /*
2578  * Only need to do preprocessing once per btrescan, at most. All
2579  * calls after the first are handled as no-ops.
2580  *
2581  * If there are array scan keys in so->keyData[], then the now-current
2582  * array elements must already be present in each array's scan key.
2583  * Verify that that happened using an assertion.
2584  */
2585  Assert(_bt_verify_keys_with_arraykeys(scan));
2586  return;
2587  }
2588 
2589  /* initialize result variables */
2590  so->qual_ok = true;
2591  so->numberOfKeys = 0;
2592 
2593  if (numberOfKeys < 1)
2594  return; /* done if qual-less scan */
2595 
2596  /* If any keys are SK_SEARCHARRAY type, set up array-key info */
2597  arrayKeyData = _bt_preprocess_array_keys(scan);
2598  if (!so->qual_ok)
2599  {
2600  /* unmatchable array, so give up */
2601  return;
2602  }
2603 
2604  /*
2605  * Treat arrayKeyData[] (a partially preprocessed copy of scan->keyData[])
2606  * as our input if _bt_preprocess_array_keys just allocated it, else just
2607  * use scan->keyData[]
2608  */
2609  if (arrayKeyData)
2610  {
2611  inkeys = arrayKeyData;
2612 
2613  /* Also maintain keyDataMap for remapping so->orderProc[] later */
2614  keyDataMap = MemoryContextAlloc(so->arrayContext,
2615  numberOfKeys * sizeof(int));
2616  }
2617  else
2618  inkeys = scan->keyData;
2619 
2620  outkeys = so->keyData;
2621  cur = &inkeys[0];
2622  /* we check that input keys are correctly ordered */
2623  if (cur->sk_attno < 1)
2624  elog(ERROR, "btree index keys must be ordered by attribute");
2625 
2626  /* We can short-circuit most of the work if there's just one key */
2627  if (numberOfKeys == 1)
2628  {
2629  /* Apply indoption to scankey (might change sk_strategy!) */
2630  if (!_bt_fix_scankey_strategy(cur, indoption))
2631  so->qual_ok = false;
2632  memcpy(outkeys, cur, sizeof(ScanKeyData));
2633  so->numberOfKeys = 1;
2634  /* We can mark the qual as required if it's for first index col */
2635  if (cur->sk_attno == 1)
2636  _bt_mark_scankey_required(outkeys);
2637  if (arrayKeyData)
2638  {
2639  /*
2640  * Don't call _bt_preprocess_array_keys_final in this fast path
2641  * (we'll miss out on the single value array transformation, but
2642  * that's not nearly as important when there's only one scan key)
2643  */
2644  Assert(cur->sk_flags & SK_SEARCHARRAY);
2645  Assert(cur->sk_strategy != BTEqualStrategyNumber ||
2646  (so->arrayKeys[0].scan_key == 0 &&
2647  OidIsValid(so->orderProcs[0].fn_oid)));
2648  }
2649 
2650  return;
2651  }
2652 
2653  /*
2654  * Otherwise, do the full set of pushups.
2655  */
2656  new_numberOfKeys = 0;
2657  numberOfEqualCols = 0;
2658 
2659  /*
2660  * Initialize for processing of keys for attr 1.
2661  *
2662  * xform[i] points to the currently best scan key of strategy type i+1; it
2663  * is NULL if we haven't yet found such a key for this attr.
2664  */
2665  attno = 1;
2666  memset(xform, 0, sizeof(xform));
2667 
2668  /*
2669  * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to
2670  * handle after-last-key processing. Actual exit from the loop is at the
2671  * "break" statement below.
2672  */
2673  for (i = 0;; cur++, i++)
2674  {
2675  if (i < numberOfKeys)
2676  {
2677  /* Apply indoption to scankey (might change sk_strategy!) */
2678  if (!_bt_fix_scankey_strategy(cur, indoption))
2679  {
2680  /* NULL can't be matched, so give up */
2681  so->qual_ok = false;
2682  return;
2683  }
2684  }
2685 
2686  /*
2687  * If we are at the end of the keys for a particular attr, finish up
2688  * processing and emit the cleaned-up keys.
2689  */
2690  if (i == numberOfKeys || cur->sk_attno != attno)
2691  {
2692  int priorNumberOfEqualCols = numberOfEqualCols;
2693 
2694  /* check input keys are correctly ordered */
2695  if (i < numberOfKeys && cur->sk_attno < attno)
2696  elog(ERROR, "btree index keys must be ordered by attribute");
2697 
2698  /*
2699  * If = has been specified, all other keys can be eliminated as
2700  * redundant. If we have a case like key = 1 AND key > 2, we can
2701  * set qual_ok to false and abandon further processing.
2702  *
2703  * We also have to deal with the case of "key IS NULL", which is
2704  * unsatisfiable in combination with any other index condition. By
2705  * the time we get here, that's been classified as an equality
2706  * check, and we've rejected any combination of it with a regular
2707  * equality condition; but not with other types of conditions.
2708  */
2709  if (xform[BTEqualStrategyNumber - 1].skey)
2710  {
2711  ScanKey eq = xform[BTEqualStrategyNumber - 1].skey;
2712  BTArrayKeyInfo *array = NULL;
2713  FmgrInfo *orderproc = NULL;
2714 
2715  if (arrayKeyData && (eq->sk_flags & SK_SEARCHARRAY))
2716  {
2717  int eq_in_ikey,
2718  eq_arrayidx;
2719 
2720  eq_in_ikey = xform[BTEqualStrategyNumber - 1].ikey;
2721  eq_arrayidx = xform[BTEqualStrategyNumber - 1].arrayidx;
2722  array = &so->arrayKeys[eq_arrayidx - 1];
2723  orderproc = so->orderProcs + eq_in_ikey;
2724 
2725  Assert(array->scan_key == eq_in_ikey);
2726  Assert(OidIsValid(orderproc->fn_oid));
2727  }
2728 
2729  for (j = BTMaxStrategyNumber; --j >= 0;)
2730  {
2731  ScanKey chk = xform[j].skey;
2732 
2733  if (!chk || j == (BTEqualStrategyNumber - 1))
2734  continue;
2735 
2736  if (eq->sk_flags & SK_SEARCHNULL)
2737  {
2738  /* IS NULL is contradictory to anything else */
2739  so->qual_ok = false;
2740  return;
2741  }
2742 
2743  if (_bt_compare_scankey_args(scan, chk, eq, chk,
2744  array, orderproc,
2745  &test_result))
2746  {
2747  if (!test_result)
2748  {
2749  /* keys proven mutually contradictory */
2750  so->qual_ok = false;
2751  return;
2752  }
2753  /* else discard the redundant non-equality key */
2754  Assert(!array || array->num_elems > 0);
2755  xform[j].skey = NULL;
2756  xform[j].ikey = -1;
2757  }
2758  /* else, cannot determine redundancy, keep both keys */
2759  }
2760  /* track number of attrs for which we have "=" keys */
2761  numberOfEqualCols++;
2762  }
2763 
2764  /* try to keep only one of <, <= */
2765  if (xform[BTLessStrategyNumber - 1].skey
2766  && xform[BTLessEqualStrategyNumber - 1].skey)
2767  {
2768  ScanKey lt = xform[BTLessStrategyNumber - 1].skey;
2769  ScanKey le = xform[BTLessEqualStrategyNumber - 1].skey;
2770 
2771  if (_bt_compare_scankey_args(scan, le, lt, le, NULL, NULL,
2772  &test_result))
2773  {
2774  if (test_result)
2775  xform[BTLessEqualStrategyNumber - 1].skey = NULL;
2776  else
2777  xform[BTLessStrategyNumber - 1].skey = NULL;
2778  }
2779  }
2780 
2781  /* try to keep only one of >, >= */
2782  if (xform[BTGreaterStrategyNumber - 1].skey
2783  && xform[BTGreaterEqualStrategyNumber - 1].skey)
2784  {
2785  ScanKey gt = xform[BTGreaterStrategyNumber - 1].skey;
2786  ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1].skey;
2787 
2788  if (_bt_compare_scankey_args(scan, ge, gt, ge, NULL, NULL,
2789  &test_result))
2790  {
2791  if (test_result)
2792  xform[BTGreaterEqualStrategyNumber - 1].skey = NULL;
2793  else
2794  xform[BTGreaterStrategyNumber - 1].skey = NULL;
2795  }
2796  }
2797 
2798  /*
2799  * Emit the cleaned-up keys into the outkeys[] array, and then
2800  * mark them if they are required. They are required (possibly
2801  * only in one direction) if all attrs before this one had "=".
2802  */
2803  for (j = BTMaxStrategyNumber; --j >= 0;)
2804  {
2805  if (xform[j].skey)
2806  {
2807  ScanKey outkey = &outkeys[new_numberOfKeys++];
2808 
2809  memcpy(outkey, xform[j].skey, sizeof(ScanKeyData));
2810  if (arrayKeyData)
2811  keyDataMap[new_numberOfKeys - 1] = xform[j].ikey;
2812  if (priorNumberOfEqualCols == attno - 1)
2813  _bt_mark_scankey_required(outkey);
2814  }
2815  }
2816 
2817  /*
2818  * Exit loop here if done.
2819  */
2820  if (i == numberOfKeys)
2821  break;
2822 
2823  /* Re-initialize for new attno */
2824  attno = cur->sk_attno;
2825  memset(xform, 0, sizeof(xform));
2826  }
2827 
2828  /* check strategy this key's operator corresponds to */
2829  j = cur->sk_strategy - 1;
2830 
2831  /* if row comparison, push it directly to the output array */
2832  if (cur->sk_flags & SK_ROW_HEADER)
2833  {
2834  ScanKey outkey = &outkeys[new_numberOfKeys++];
2835 
2836  memcpy(outkey, cur, sizeof(ScanKeyData));
2837  if (arrayKeyData)
2838  keyDataMap[new_numberOfKeys - 1] = i;
2839  if (numberOfEqualCols == attno - 1)
2840  _bt_mark_scankey_required(outkey);
2841 
2842  /*
2843  * We don't support RowCompare using equality; such a qual would
2844  * mess up the numberOfEqualCols tracking.
2845  */
2846  Assert(j != (BTEqualStrategyNumber - 1));
2847  continue;
2848  }
2849 
2850  /*
2851  * Does this input scan key require further processing as an array?
2852  */
2853  if (cur->sk_strategy == InvalidStrategy)
2854  {
2855  /* _bt_preprocess_array_keys marked this array key redundant */
2856  Assert(arrayKeyData);
2857  Assert(cur->sk_flags & SK_SEARCHARRAY);
2858  continue;
2859  }
2860 
2861  if (cur->sk_strategy == BTEqualStrategyNumber &&
2862  (cur->sk_flags & SK_SEARCHARRAY))
2863  {
2864  /* _bt_preprocess_array_keys kept this array key */
2865  Assert(arrayKeyData);
2866  arrayidx++;
2867  }
2868 
2869  /*
2870  * have we seen a scan key for this same attribute and using this same
2871  * operator strategy before now?
2872  */
2873  if (xform[j].skey == NULL)
2874  {
2875  /* nope, so this scan key wins by default (at least for now) */
2876  xform[j].skey = cur;
2877  xform[j].ikey = i;
2878  xform[j].arrayidx = arrayidx;
2879  }
2880  else
2881  {
2882  FmgrInfo *orderproc = NULL;
2883  BTArrayKeyInfo *array = NULL;
2884 
2885  /*
2886  * Seen one of these before, so keep only the more restrictive key
2887  * if possible
2888  */
2889  if (j == (BTEqualStrategyNumber - 1) && arrayKeyData)
2890  {
2891  /*
2892  * Have to set up array keys
2893  */
2894  if ((cur->sk_flags & SK_SEARCHARRAY))
2895  {
2896  array = &so->arrayKeys[arrayidx - 1];
2897  orderproc = so->orderProcs + i;
2898 
2899  Assert(array->scan_key == i);
2900  Assert(OidIsValid(orderproc->fn_oid));
2901  }
2902  else if ((xform[j].skey->sk_flags & SK_SEARCHARRAY))
2903  {
2904  array = &so->arrayKeys[xform[j].arrayidx - 1];
2905  orderproc = so->orderProcs + xform[j].ikey;
2906 
2907  Assert(array->scan_key == xform[j].ikey);
2908  Assert(OidIsValid(orderproc->fn_oid));
2909  }
2910 
2911  /*
2912  * Both scan keys might have arrays, in which case we'll
2913  * arbitrarily pass only one of the arrays. That won't
2914  * matter, since _bt_compare_scankey_args is aware that two
2915  * SEARCHARRAY scan keys mean that _bt_preprocess_array_keys
2916  * failed to eliminate redundant arrays through array merging.
2917  * _bt_compare_scankey_args just returns false when it sees
2918  * this; it won't even try to examine either array.
2919  */
2920  }
2921 
2922  if (_bt_compare_scankey_args(scan, cur, cur, xform[j].skey,
2923  array, orderproc, &test_result))
2924  {
2925  /* Have all we need to determine redundancy */
2926  if (test_result)
2927  {
2928  Assert(!array || array->num_elems > 0);
2929 
2930  /*
2931  * New key is more restrictive, and so replaces old key...
2932  */
2933  if (j != (BTEqualStrategyNumber - 1) ||
2934  !(xform[j].skey->sk_flags & SK_SEARCHARRAY))
2935  {
2936  xform[j].skey = cur;
2937  xform[j].ikey = i;
2938  xform[j].arrayidx = arrayidx;
2939  }
2940  else
2941  {
2942  /*
2943  * ...unless we have to keep the old key because it's
2944  * an array that rendered the new key redundant. We
2945  * need to make sure that we don't throw away an array
2946  * scan key. _bt_compare_scankey_args expects us to
2947  * always keep arrays (and discard non-arrays).
2948  */
2949  Assert(!(cur->sk_flags & SK_SEARCHARRAY));
2950  }
2951  }
2952  else if (j == (BTEqualStrategyNumber - 1))
2953  {
2954  /* key == a && key == b, but a != b */
2955  so->qual_ok = false;
2956  return;
2957  }
2958  /* else old key is more restrictive, keep it */
2959  }
2960  else
2961  {
2962  /*
2963  * We can't determine which key is more restrictive. Push
2964  * xform[j] directly to the output array, then set xform[j] to
2965  * the new scan key.
2966  *
2967  * Note: We do things this way around so that our arrays are
2968  * always in the same order as their corresponding scan keys,
2969  * even with incomplete opfamilies. _bt_advance_array_keys
2970  * depends on this.
2971  */
2972  ScanKey outkey = &outkeys[new_numberOfKeys++];
2973 
2974  memcpy(outkey, xform[j].skey, sizeof(ScanKeyData));
2975  if (arrayKeyData)
2976  keyDataMap[new_numberOfKeys - 1] = xform[j].ikey;
2977  if (numberOfEqualCols == attno - 1)
2978  _bt_mark_scankey_required(outkey);
2979  xform[j].skey = cur;
2980  xform[j].ikey = i;
2981  xform[j].arrayidx = arrayidx;
2982  }
2983  }
2984  }
2985 
2986  so->numberOfKeys = new_numberOfKeys;
2987 
2988  /*
2989  * Now that we've built a temporary mapping from so->keyData[] (output
2990  * scan keys) to scan->keyData[] (input scan keys), fix array->scan_key
2991  * references. Also consolidate the so->orderProc[] array such that it
2992  * can be subscripted using so->keyData[]-wise offsets.
2993  */
2994  if (arrayKeyData)
2995  _bt_preprocess_array_keys_final(scan, keyDataMap);
2996 
2997  /* Could pfree arrayKeyData/keyDataMap now, but not worth the cycles */
2998 }
2999 
3000 #ifdef USE_ASSERT_CHECKING
3001 /*
3002  * Verify that the scan's qual state matches what we expect at the point that
3003  * _bt_start_prim_scan is about to start a just-scheduled new primitive scan.
3004  *
3005  * We enforce a rule against non-required array scan keys: they must start out
3006  * with whatever element is the first for the scan's current scan direction.
3007  * See _bt_rewind_nonrequired_arrays comments for an explanation.
3008  */
3009 static bool
3010 _bt_verify_arrays_bt_first(IndexScanDesc scan, ScanDirection dir)
3011 {
3012  BTScanOpaque so = (BTScanOpaque) scan->opaque;
3013  int arrayidx = 0;
3014 
3015  for (int ikey = 0; ikey < so->numberOfKeys; ikey++)
3016  {
3017  ScanKey cur = so->keyData + ikey;
3018  BTArrayKeyInfo *array = NULL;
3019  int first_elem_dir;
3020 
3021  if (!(cur->sk_flags & SK_SEARCHARRAY) ||
3022  cur->sk_strategy != BTEqualStrategyNumber)
3023  continue;
3024 
3025  array = &so->arrayKeys[arrayidx++];
3026 
3027  if (((cur->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) ||
3028  ((cur->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
3029  continue;
3030 
3031  if (ScanDirectionIsForward(dir))
3032  first_elem_dir = 0;
3033  else
3034  first_elem_dir = array->num_elems - 1;
3035 
3036  if (array->cur_elem != first_elem_dir)
3037  return false;
3038  }
3039 
3040  return _bt_verify_keys_with_arraykeys(scan);
3041 }
3042 
3043 /*
3044  * Verify that the scan's "so->keyData[]" scan keys are in agreement with
3045  * its array key state
3046  */
3047 static bool
3048 _bt_verify_keys_with_arraykeys(IndexScanDesc scan)
3049 {
3050  BTScanOpaque so = (BTScanOpaque) scan->opaque;
3051  int last_sk_attno = InvalidAttrNumber,
3052  arrayidx = 0;
3053 
3054  if (!so->qual_ok)
3055  return false;
3056 
3057  for (int ikey = 0; ikey < so->numberOfKeys; ikey++)
3058  {
3059  ScanKey cur = so->keyData + ikey;
3060  BTArrayKeyInfo *array;
3061 
3062  if (cur->sk_strategy != BTEqualStrategyNumber ||
3063  !(cur->sk_flags & SK_SEARCHARRAY))
3064  continue;
3065 
3066  array = &so->arrayKeys[arrayidx++];
3067  if (array->scan_key != ikey)
3068  return false;
3069 
3070  if (array->num_elems <= 0)
3071  return false;
3072 
3073  if (cur->sk_argument != array->elem_values[array->cur_elem])
3074  return false;
3075  if (last_sk_attno > cur->sk_attno)
3076  return false;
3077  last_sk_attno = cur->sk_attno;
3078  }
3079 
3080  if (arrayidx != so->numArrayKeys)
3081  return false;
3082 
3083  return true;
3084 }
3085 #endif
3086 
3087 /*
3088  * Compare two scankey values using a specified operator.
3089  *
3090  * The test we want to perform is logically "leftarg op rightarg", where
3091  * leftarg and rightarg are the sk_argument values in those ScanKeys, and
3092  * the comparison operator is the one in the op ScanKey. However, in
3093  * cross-data-type situations we may need to look up the correct operator in
3094  * the index's opfamily: it is the one having amopstrategy = op->sk_strategy
3095  * and amoplefttype/amoprighttype equal to the two argument datatypes.
3096  *
3097  * If the opfamily doesn't supply a complete set of cross-type operators we
3098  * may not be able to make the comparison. If we can make the comparison
3099  * we store the operator result in *result and return true. We return false
3100  * if the comparison could not be made.
3101  *
3102  * If either leftarg or rightarg are an array, we'll apply array-specific
3103  * rules to determine which array elements are redundant on behalf of caller.
3104  * It is up to our caller to save whichever of the two scan keys is the array,
3105  * and discard the non-array scan key (the non-array scan key is guaranteed to
3106  * be redundant with any complete opfamily). Caller isn't expected to call
3107  * here with a pair of array scan keys provided we're dealing with a complete
3108  * opfamily (_bt_preprocess_array_keys will merge array keys together to make
3109  * sure of that).
3110  *
3111  * Note: we'll also shrink caller's array as needed to eliminate redundant
3112  * array elements. One reason why caller should prefer to discard non-array
3113  * scan keys is so that we'll have the opportunity to shrink the array
3114  * multiple times, in multiple calls (for each of several other scan keys on
3115  * the same index attribute).
3116  *
3117  * Note: op always points at the same ScanKey as either leftarg or rightarg.
3118  * Since we don't scribble on the scankeys themselves, this aliasing should
3119  * cause no trouble.
3120  *
3121  * Note: this routine needs to be insensitive to any DESC option applied
3122  * to the index column. For example, "x < 4" is a tighter constraint than
3123  * "x < 5" regardless of which way the index is sorted.
3124  */
3125 static bool
3127  ScanKey leftarg, ScanKey rightarg,
3128  BTArrayKeyInfo *array, FmgrInfo *orderproc,
3129  bool *result)
3130 {
3131  Relation rel = scan->indexRelation;
3132  Oid lefttype,
3133  righttype,
3134  optype,
3135  opcintype,
3136  cmp_op;
3137  StrategyNumber strat;
3138 
3139  /*
3140  * First, deal with cases where one or both args are NULL. This should
3141  * only happen when the scankeys represent IS NULL/NOT NULL conditions.
3142  */
3143  if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ISNULL)
3144  {
3145  bool leftnull,
3146  rightnull;
3147 
3148  if (leftarg->sk_flags & SK_ISNULL)
3149  {
3151  leftnull = true;
3152  }
3153  else
3154  leftnull = false;
3155  if (rightarg->sk_flags & SK_ISNULL)
3156  {
3157  Assert(rightarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
3158  rightnull = true;
3159  }
3160  else
3161  rightnull = false;
3162 
3163  /*
3164  * We treat NULL as either greater than or less than all other values.
3165  * Since true > false, the tests below work correctly for NULLS LAST
3166  * logic. If the index is NULLS FIRST, we need to flip the strategy.
3167  */
3168  strat = op->sk_strategy;
3169  if (op->sk_flags & SK_BT_NULLS_FIRST)
3170  strat = BTCommuteStrategyNumber(strat);
3171 
3172  switch (strat)
3173  {
3174  case BTLessStrategyNumber:
3175  *result = (leftnull < rightnull);
3176  break;
3178  *result = (leftnull <= rightnull);
3179  break;
3180  case BTEqualStrategyNumber:
3181  *result = (leftnull == rightnull);
3182  break;
3184  *result = (leftnull >= rightnull);
3185  break;
3187  *result = (leftnull > rightnull);
3188  break;
3189  default:
3190  elog(ERROR, "unrecognized StrategyNumber: %d", (int) strat);
3191  *result = false; /* keep compiler quiet */
3192  break;
3193  }
3194  return true;
3195  }
3196 
3197  /*
3198  * If either leftarg or rightarg are equality-type array scankeys, we need
3199  * specialized handling (since by now we know that IS NULL wasn't used)
3200  */
3201  if (array)
3202  {
3203  bool leftarray,
3204  rightarray;
3205 
3206  leftarray = ((leftarg->sk_flags & SK_SEARCHARRAY) &&
3207  leftarg->sk_strategy == BTEqualStrategyNumber);
3208  rightarray = ((rightarg->sk_flags & SK_SEARCHARRAY) &&
3209  rightarg->sk_strategy == BTEqualStrategyNumber);
3210 
3211  /*
3212  * _bt_preprocess_array_keys is responsible for merging together array
3213  * scan keys, and will do so whenever the opfamily has the required
3214  * cross-type support. If it failed to do that, we handle it just
3215  * like the case where we can't make the comparison ourselves.
3216  */
3217  if (leftarray && rightarray)
3218  {
3219  /* Can't make the comparison */
3220  *result = false; /* suppress compiler warnings */
3221  return false;
3222  }
3223 
3224  /*
3225  * Otherwise we need to determine if either one of leftarg or rightarg
3226  * uses an array, then pass this through to a dedicated helper
3227  * function.
3228  */
3229  if (leftarray)
3230  return _bt_compare_array_scankey_args(scan, leftarg, rightarg,
3231  orderproc, array, result);
3232  else if (rightarray)
3233  return _bt_compare_array_scankey_args(scan, rightarg, leftarg,
3234  orderproc, array, result);
3235 
3236  /* FALL THRU */
3237  }
3238 
3239  /*
3240  * The opfamily we need to worry about is identified by the index column.
3241  */
3242  Assert(leftarg->sk_attno == rightarg->sk_attno);
3243 
3244  opcintype = rel->rd_opcintype[leftarg->sk_attno - 1];
3245 
3246  /*
3247  * Determine the actual datatypes of the ScanKey arguments. We have to
3248  * support the convention that sk_subtype == InvalidOid means the opclass
3249  * input type; this is a hack to simplify life for ScanKeyInit().
3250  */
3251  lefttype = leftarg->sk_subtype;
3252  if (lefttype == InvalidOid)
3253  lefttype = opcintype;
3254  righttype = rightarg->sk_subtype;
3255  if (righttype == InvalidOid)
3256  righttype = opcintype;
3257  optype = op->sk_subtype;
3258  if (optype == InvalidOid)
3259  optype = opcintype;
3260 
3261  /*
3262  * If leftarg and rightarg match the types expected for the "op" scankey,
3263  * we can use its already-looked-up comparison function.
3264  */
3265  if (lefttype == opcintype && righttype == optype)
3266  {
3267  *result = DatumGetBool(FunctionCall2Coll(&op->sk_func,
3268  op->sk_collation,
3269  leftarg->sk_argument,
3270  rightarg->sk_argument));
3271  return true;
3272  }
3273 
3274  /*
3275  * Otherwise, we need to go to the syscache to find the appropriate
3276  * operator. (This cannot result in infinite recursion, since no
3277  * indexscan initiated by syscache lookup will use cross-data-type
3278  * operators.)
3279  *
3280  * If the sk_strategy was flipped by _bt_fix_scankey_strategy, we have to
3281  * un-flip it to get the correct opfamily member.
3282  */
3283  strat = op->sk_strategy;
3284  if (op->sk_flags & SK_BT_DESC)
3285  strat = BTCommuteStrategyNumber(strat);
3286 
3287  cmp_op = get_opfamily_member(rel->rd_opfamily[leftarg->sk_attno - 1],
3288  lefttype,
3289  righttype,
3290  strat);
3291  if (OidIsValid(cmp_op))
3292  {
3293  RegProcedure cmp_proc = get_opcode(cmp_op);
3294 
3295  if (RegProcedureIsValid(cmp_proc))
3296  {
3297  *result = DatumGetBool(OidFunctionCall2Coll(cmp_proc,
3298  op->sk_collation,
3299  leftarg->sk_argument,
3300  rightarg->sk_argument));
3301  return true;
3302  }
3303  }
3304 
3305  /* Can't make the comparison */
3306  *result = false; /* suppress compiler warnings */
3307  return false;
3308 }
3309 
3310 /*
3311  * Adjust a scankey's strategy and flags setting as needed for indoptions.
3312  *
3313  * We copy the appropriate indoption value into the scankey sk_flags
3314  * (shifting to avoid clobbering system-defined flag bits). Also, if
3315  * the DESC option is set, commute (flip) the operator strategy number.
3316  *
3317  * A secondary purpose is to check for IS NULL/NOT NULL scankeys and set up
3318  * the strategy field correctly for them.
3319  *
3320  * Lastly, for ordinary scankeys (not IS NULL/NOT NULL), we check for a
3321  * NULL comparison value. Since all btree operators are assumed strict,
3322  * a NULL means that the qual cannot be satisfied. We return true if the
3323  * comparison value isn't NULL, or false if the scan should be abandoned.
3324  *
3325  * This function is applied to the *input* scankey structure; therefore
3326  * on a rescan we will be looking at already-processed scankeys. Hence
3327  * we have to be careful not to re-commute the strategy if we already did it.
3328  * It's a bit ugly to modify the caller's copy of the scankey but in practice
3329  * there shouldn't be any problem, since the index's indoptions are certainly
3330  * not going to change while the scankey survives.
3331  */
3332 static bool
3334 {
3335  int addflags;
3336 
3337  addflags = indoption[skey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
3338 
3339  /*
3340  * We treat all btree operators as strict (even if they're not so marked
3341  * in pg_proc). This means that it is impossible for an operator condition
3342  * with a NULL comparison constant to succeed, and we can reject it right
3343  * away.
3344  *
3345  * However, we now also support "x IS NULL" clauses as search conditions,
3346  * so in that case keep going. The planner has not filled in any
3347  * particular strategy in this case, so set it to BTEqualStrategyNumber
3348  * --- we can treat IS NULL as an equality operator for purposes of search
3349  * strategy.
3350  *
3351  * Likewise, "x IS NOT NULL" is supported. We treat that as either "less
3352  * than NULL" in a NULLS LAST index, or "greater than NULL" in a NULLS
3353  * FIRST index.
3354  *
3355  * Note: someday we might have to fill in sk_collation from the index
3356  * column's collation. At the moment this is a non-issue because we'll
3357  * never actually call the comparison operator on a NULL.
3358  */
3359  if (skey->sk_flags & SK_ISNULL)
3360  {
3361  /* SK_ISNULL shouldn't be set in a row header scankey */
3362  Assert(!(skey->sk_flags & SK_ROW_HEADER));
3363 
3364  /* Set indoption flags in scankey (might be done already) */
3365  skey->sk_flags |= addflags;
3366 
3367  /* Set correct strategy for IS NULL or NOT NULL search */
3368  if (skey->sk_flags & SK_SEARCHNULL)
3369  {
3371  skey->sk_subtype = InvalidOid;
3372  skey->sk_collation = InvalidOid;
3373  }
3374  else if (skey->sk_flags & SK_SEARCHNOTNULL)
3375  {
3376  if (skey->sk_flags & SK_BT_NULLS_FIRST)
3378  else
3380  skey->sk_subtype = InvalidOid;
3381  skey->sk_collation = InvalidOid;
3382  }
3383  else
3384  {
3385  /* regular qual, so it cannot be satisfied */
3386  return false;
3387  }
3388 
3389  /* Needn't do the rest */
3390  return true;
3391  }
3392 
3393  if (skey->sk_strategy == InvalidStrategy)
3394  {
3395  /* Already-eliminated array scan key; don't need to fix anything */
3396  Assert(skey->sk_flags & SK_SEARCHARRAY);
3397  return true;
3398  }
3399 
3400  /* Adjust strategy for DESC, if we didn't already */
3401  if ((addflags & SK_BT_DESC) && !(skey->sk_flags & SK_BT_DESC))
3403  skey->sk_flags |= addflags;
3404 
3405  /* If it's a row header, fix row member flags and strategies similarly */
3406  if (skey->sk_flags & SK_ROW_HEADER)
3407  {
3408  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
3409 
3410  for (;;)
3411  {
3412  Assert(subkey->sk_flags & SK_ROW_MEMBER);
3413  addflags = indoption[subkey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
3414  if ((addflags & SK_BT_DESC) && !(subkey->sk_flags & SK_BT_DESC))
3415  subkey->sk_strategy = BTCommuteStrategyNumber(subkey->sk_strategy);
3416  subkey->sk_flags |= addflags;
3417  if (subkey->sk_flags & SK_ROW_END)
3418  break;
3419  subkey++;
3420  }
3421  }
3422 
3423  return true;
3424 }
3425 
3426 /*
3427  * Mark a scankey as "required to continue the scan".
3428  *
3429  * Depending on the operator type, the key may be required for both scan
3430  * directions or just one. Also, if the key is a row comparison header,
3431  * we have to mark its first subsidiary ScanKey as required. (Subsequent
3432  * subsidiary ScanKeys are normally for lower-order columns, and thus
3433  * cannot be required, since they're after the first non-equality scankey.)
3434  *
3435  * Note: when we set required-key flag bits in a subsidiary scankey, we are
3436  * scribbling on a data structure belonging to the index AM's caller, not on
3437  * our private copy. This should be OK because the marking will not change
3438  * from scan to scan within a query, and so we'd just re-mark the same way
3439  * anyway on a rescan. Something to keep an eye on though.
3440  */
3441 static void
3443 {
3444  int addflags;
3445 
3446  switch (skey->sk_strategy)
3447  {
3448  case BTLessStrategyNumber:
3450  addflags = SK_BT_REQFWD;
3451  break;
3452  case BTEqualStrategyNumber:
3453  addflags = SK_BT_REQFWD | SK_BT_REQBKWD;
3454  break;
3457  addflags = SK_BT_REQBKWD;
3458  break;
3459  default:
3460  elog(ERROR, "unrecognized StrategyNumber: %d",
3461  (int) skey->sk_strategy);
3462  addflags = 0; /* keep compiler quiet */
3463  break;
3464  }
3465 
3466  skey->sk_flags |= addflags;
3467 
3468  if (skey->sk_flags & SK_ROW_HEADER)
3469  {
3470  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
3471 
3472  /* First subkey should be same column/operator as the header */
3473  Assert(subkey->sk_flags & SK_ROW_MEMBER);
3474  Assert(subkey->sk_attno == skey->sk_attno);
3475  Assert(subkey->sk_strategy == skey->sk_strategy);
3476  subkey->sk_flags |= addflags;
3477  }
3478 }
3479 
3480 /*
3481  * Test whether an indextuple satisfies all the scankey conditions.
3482  *
3483  * Return true if so, false if not. If the tuple fails to pass the qual,
3484  * we also determine whether there's any need to continue the scan beyond
3485  * this tuple, and set pstate.continuescan accordingly. See comments for
3486  * _bt_preprocess_keys(), above, about how this is done.
3487  *
3488  * Forward scan callers can pass a high key tuple in the hopes of having
3489  * us set *continuescan to false, and avoiding an unnecessary visit to
3490  * the page to the right.
3491  *
3492  * Advances the scan's array keys when necessary for arrayKeys=true callers.
3493  * Caller can avoid all array related side-effects when calling just to do a
3494  * page continuescan precheck -- pass arrayKeys=false for that. Scans without
3495  * any arrays keys must always pass arrayKeys=false.
3496  *
3497  * Also stops and starts primitive index scans for arrayKeys=true callers.
3498  * Scans with array keys are required to set up page state that helps us with
3499  * this. The page's finaltup tuple (the page high key for a forward scan, or
3500  * the page's first non-pivot tuple for a backward scan) must be set in
3501  * pstate.finaltup ahead of the first call here for the page (or possibly the
3502  * first call after an initial continuescan-setting page precheck call). Set
3503  * this to NULL for rightmost page (or the leftmost page for backwards scans).
3504  *
3505  * scan: index scan descriptor (containing a search-type scankey)
3506  * pstate: page level input and output parameters
3507  * arrayKeys: should we advance the scan's array keys if necessary?
3508  * tuple: index tuple to test
3509  * tupnatts: number of attributes in tupnatts (high key may be truncated)
3510  */
3511 bool
3512 _bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys,
3513  IndexTuple tuple, int tupnatts)
3514 {
3515  TupleDesc tupdesc = RelationGetDescr(scan->indexRelation);
3516  BTScanOpaque so = (BTScanOpaque) scan->opaque;
3517  ScanDirection dir = pstate->dir;
3518  int ikey = 0;
3519  bool res;
3520 
3521  Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts);
3522 
3523  res = _bt_check_compare(scan, dir, tuple, tupnatts, tupdesc,
3524  arrayKeys, pstate->prechecked, pstate->firstmatch,
3525  &pstate->continuescan, &ikey);
3526 
3527 #ifdef USE_ASSERT_CHECKING
3528  if (!arrayKeys && so->numArrayKeys)
3529  {
3530  /*
3531  * This is a continuescan precheck call for a scan with array keys.
3532  *
3533  * Assert that the scan isn't in danger of becoming confused.
3534  */
3535  Assert(!so->scanBehind && !pstate->prechecked && !pstate->firstmatch);
3536  Assert(!_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc,
3537  tupnatts, false, 0, NULL));
3538  }
3539  if (pstate->prechecked || pstate->firstmatch)
3540  {
3541  bool dcontinuescan;
3542  int dikey = 0;
3543 
3544  /*
3545  * Call relied on continuescan/firstmatch prechecks -- assert that we
3546  * get the same answer without those optimizations
3547  */
3548  Assert(res == _bt_check_compare(scan, dir, tuple, tupnatts, tupdesc,
3549  false, false, false,
3550  &dcontinuescan, &dikey));
3551  Assert(pstate->continuescan == dcontinuescan);
3552  }
3553 #endif
3554 
3555  /*
3556  * Only one _bt_check_compare call is required in the common case where
3557  * there are no equality strategy array scan keys. Otherwise we can only
3558  * accept _bt_check_compare's answer unreservedly when it didn't set
3559  * pstate.continuescan=false.
3560  */
3561  if (!arrayKeys || pstate->continuescan)
3562  return res;
3563 
3564  /*
3565  * _bt_check_compare call set continuescan=false in the presence of
3566  * equality type array keys. This could mean that the tuple is just past
3567  * the end of matches for the current array keys.
3568  *
3569  * It's also possible that the scan is still _before_ the _start_ of
3570  * tuples matching the current set of array keys. Check for that first.
3571  */
3572  if (_bt_tuple_before_array_skeys(scan, dir, tuple, tupdesc, tupnatts, true,
3573  ikey, NULL))
3574  {
3575  /*
3576  * Tuple is still before the start of matches according to the scan's
3577  * required array keys (according to _all_ of its required equality
3578  * strategy keys, actually).
3579  *
3580  * _bt_advance_array_keys occasionally sets so->scanBehind to signal
3581  * that the scan's current position/tuples might be significantly
3582  * behind (multiple pages behind) its current array keys. When this
3583  * happens, we need to be prepared to recover by starting a new
3584  * primitive index scan here, on our own.
3585  */
3586  Assert(!so->scanBehind ||
3588  if (unlikely(so->scanBehind) && pstate->finaltup &&
3589  _bt_tuple_before_array_skeys(scan, dir, pstate->finaltup, tupdesc,
3590  BTreeTupleGetNAtts(pstate->finaltup,
3591  scan->indexRelation),
3592  false, 0, NULL))
3593  {
3594  /* Cut our losses -- start a new primitive index scan now */
3595  pstate->continuescan = false;
3596  so->needPrimScan = true;
3597  }
3598  else
3599  {
3600  /* Override _bt_check_compare, continue primitive scan */
3601  pstate->continuescan = true;
3602 
3603  /*
3604  * We will end up here repeatedly given a group of tuples > the
3605  * previous array keys and < the now-current keys (for a backwards
3606  * scan it's just the same, though the operators swap positions).
3607  *
3608  * We must avoid allowing this linear search process to scan very
3609  * many tuples from well before the start of tuples matching the
3610  * current array keys (or from well before the point where we'll
3611  * once again have to advance the scan's array keys).
3612  *
3613  * We keep the overhead under control by speculatively "looking
3614  * ahead" to later still-unscanned items from this same leaf page.
3615  * We'll only attempt this once the number of tuples that the
3616  * linear search process has examined starts to get out of hand.
3617  */
3618  pstate->rechecks++;
3619  if (pstate->rechecks >= LOOK_AHEAD_REQUIRED_RECHECKS)
3620  {
3621  /* See if we should skip ahead within the current leaf page */
3622  _bt_checkkeys_look_ahead(scan, pstate, tupnatts, tupdesc);
3623 
3624  /*
3625  * Might have set pstate.skip to a later page offset. When
3626  * that happens then _bt_readpage caller will inexpensively
3627  * skip ahead to a later tuple from the same page (the one
3628  * just after the tuple we successfully "looked ahead" to).
3629  */
3630  }
3631  }
3632 
3633  /* This indextuple doesn't match the current qual, in any case */
3634  return false;
3635  }
3636 
3637  /*
3638  * Caller's tuple is >= the current set of array keys and other equality
3639  * constraint scan keys (or <= if this is a backwards scan). It's now
3640  * clear that we _must_ advance any required array keys in lockstep with
3641  * the scan.
3642  */
3643  return _bt_advance_array_keys(scan, pstate, tuple, tupnatts, tupdesc,
3644  ikey, true);
3645 }
3646 
3647 /*
3648  * Test whether an indextuple satisfies current scan condition.
3649  *
3650  * Return true if so, false if not. If not, also sets *continuescan to false
3651  * when it's also not possible for any later tuples to pass the current qual
3652  * (with the scan's current set of array keys, in the current scan direction),
3653  * in addition to setting *ikey to the so->keyData[] subscript/offset for the
3654  * unsatisfied scan key (needed when caller must consider advancing the scan's
3655  * array keys).
3656  *
3657  * This is a subroutine for _bt_checkkeys. We provisionally assume that
3658  * reaching the end of the current set of required keys (in particular the
3659  * current required array keys) ends the ongoing (primitive) index scan.
3660  * Callers without array keys should just end the scan right away when they
3661  * find that continuescan has been set to false here by us. Things are more
3662  * complicated for callers with array keys.
3663  *
3664  * Callers with array keys must first consider advancing the arrays when
3665  * continuescan has been set to false here by us. They must then consider if
3666  * it really does make sense to end the current (primitive) index scan, in
3667  * light of everything that is known at that point. (In general when we set
3668  * continuescan=false for these callers it must be treated as provisional.)
3669  *
3670  * We deal with advancing unsatisfied non-required arrays directly, though.
3671  * This is safe, since by definition non-required keys can't end the scan.
3672  * This is just how we determine if non-required arrays are just unsatisfied
3673  * by the current array key, or if they're truly unsatisfied (that is, if
3674  * they're unsatisfied by every possible array key).
3675  *
3676  * Though we advance non-required array keys on our own, that shouldn't have
3677  * any lasting consequences for the scan. By definition, non-required arrays
3678  * have no fixed relationship with the scan's progress. (There are delicate
3679  * considerations for non-required arrays when the arrays need to be advanced
3680  * following our setting continuescan to false, but that doesn't concern us.)
3681  *
3682  * Pass advancenonrequired=false to avoid all array related side effects.
3683  * This allows _bt_advance_array_keys caller to avoid infinite recursion.
3684  */
3685 static bool
3687  IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
3688  bool advancenonrequired, bool prechecked, bool firstmatch,
3689  bool *continuescan, int *ikey)
3690 {
3691  BTScanOpaque so = (BTScanOpaque) scan->opaque;
3692 
3693  *continuescan = true; /* default assumption */
3694 
3695  for (; *ikey < so->numberOfKeys; (*ikey)++)
3696  {
3697  ScanKey key = so->keyData + *ikey;
3698  Datum datum;
3699  bool isNull;
3700  bool requiredSameDir = false,
3701  requiredOppositeDirOnly = false;
3702 
3703  /*
3704  * Check if the key is required in the current scan direction, in the
3705  * opposite scan direction _only_, or in neither direction
3706  */
3707  if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsForward(dir)) ||
3708  ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsBackward(dir)))
3709  requiredSameDir = true;
3710  else if (((key->sk_flags & SK_BT_REQFWD) && ScanDirectionIsBackward(dir)) ||
3711  ((key->sk_flags & SK_BT_REQBKWD) && ScanDirectionIsForward(dir)))
3712  requiredOppositeDirOnly = true;
3713 
3714  /*
3715  * If the caller told us the *continuescan flag is known to be true
3716  * for the last item on the page, then we know the keys required for
3717  * the current direction scan should be matched. Otherwise, the
3718  * *continuescan flag would be set for the current item and
3719  * subsequently the last item on the page accordingly.
3720  *
3721  * If the key is required for the opposite direction scan, we can skip
3722  * the check if the caller tells us there was already at least one
3723  * matching item on the page. Also, we require the *continuescan flag
3724  * to be true for the last item on the page to know there are no
3725  * NULLs.
3726  *
3727  * Both cases above work except for the row keys, where NULLs could be
3728  * found in the middle of matching values.
3729  */
3730  if (prechecked &&
3731  (requiredSameDir || (requiredOppositeDirOnly && firstmatch)) &&
3732  !(key->sk_flags & SK_ROW_HEADER))
3733  continue;
3734 
3735  if (key->sk_attno > tupnatts)
3736  {
3737  /*
3738  * This attribute is truncated (must be high key). The value for
3739  * this attribute in the first non-pivot tuple on the page to the
3740  * right could be any possible value. Assume that truncated
3741  * attribute passes the qual.
3742  */
3743  Assert(BTreeTupleIsPivot(tuple));
3744  continue;
3745  }
3746 
3747  /* row-comparison keys need special processing */
3748  if (key->sk_flags & SK_ROW_HEADER)
3749  {
3750  if (_bt_check_rowcompare(key, tuple, tupnatts, tupdesc, dir,
3751  continuescan))
3752  continue;
3753  return false;
3754  }
3755 
3756  datum = index_getattr(tuple,
3757  key->sk_attno,
3758  tupdesc,
3759  &isNull);
3760 
3761  if (key->sk_flags & SK_ISNULL)
3762  {
3763  /* Handle IS NULL/NOT NULL tests */
3764  if (key->sk_flags & SK_SEARCHNULL)
3765  {
3766  if (isNull)
3767  continue; /* tuple satisfies this qual */
3768  }
3769  else
3770  {
3771  Assert(key->sk_flags & SK_SEARCHNOTNULL);
3772  if (!isNull)
3773  continue; /* tuple satisfies this qual */
3774  }
3775 
3776  /*
3777  * Tuple fails this qual. If it's a required qual for the current
3778  * scan direction, then we can conclude no further tuples will
3779  * pass, either.
3780  */
3781  if (requiredSameDir)
3782  *continuescan = false;
3783 
3784  /*
3785  * In any case, this indextuple doesn't match the qual.
3786  */
3787  return false;
3788  }
3789 
3790  if (isNull)
3791  {
3792  if (key->sk_flags & SK_BT_NULLS_FIRST)
3793  {
3794  /*
3795  * Since NULLs are sorted before non-NULLs, we know we have
3796  * reached the lower limit of the range of values for this
3797  * index attr. On a backward scan, we can stop if this qual
3798  * is one of the "must match" subset. We can stop regardless
3799  * of whether the qual is > or <, so long as it's required,
3800  * because it's not possible for any future tuples to pass. On
3801  * a forward scan, however, we must keep going, because we may
3802  * have initially positioned to the start of the index.
3803  * (_bt_advance_array_keys also relies on this behavior during
3804  * forward scans.)
3805  */
3806  if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
3808  *continuescan = false;
3809  }
3810  else
3811  {
3812  /*
3813  * Since NULLs are sorted after non-NULLs, we know we have
3814  * reached the upper limit of the range of values for this
3815  * index attr. On a forward scan, we can stop if this qual is
3816  * one of the "must match" subset. We can stop regardless of
3817  * whether the qual is > or <, so long as it's required,
3818  * because it's not possible for any future tuples to pass. On
3819  * a backward scan, however, we must keep going, because we
3820  * may have initially positioned to the end of the index.
3821  * (_bt_advance_array_keys also relies on this behavior during
3822  * backward scans.)
3823  */
3824  if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
3826  *continuescan = false;
3827  }
3828 
3829  /*
3830  * In any case, this indextuple doesn't match the qual.
3831  */
3832  return false;
3833  }
3834 
3835  /*
3836  * Apply the key-checking function, though only if we must.
3837  *
3838  * When a key is required in the opposite-of-scan direction _only_,
3839  * then it must already be satisfied if firstmatch=true indicates that
3840  * an earlier tuple from this same page satisfied it earlier on.
3841  */
3842  if (!(requiredOppositeDirOnly && firstmatch) &&
3843  !DatumGetBool(FunctionCall2Coll(&key->sk_func, key->sk_collation,
3844  datum, key->sk_argument)))
3845  {
3846  /*
3847  * Tuple fails this qual. If it's a required qual for the current
3848  * scan direction, then we can conclude no further tuples will
3849  * pass, either.
3850  *
3851  * Note: because we stop the scan as soon as any required equality
3852  * qual fails, it is critical that equality quals be used for the
3853  * initial positioning in _bt_first() when they are available. See
3854  * comments in _bt_first().
3855  */
3856  if (requiredSameDir)
3857  *continuescan = false;
3858 
3859  /*
3860  * If this is a non-required equality-type array key, the tuple
3861  * needs to be checked against every possible array key. Handle
3862  * this by "advancing" the scan key's array to a matching value
3863  * (if we're successful then the tuple might match the qual).
3864  */
3865  else if (advancenonrequired &&
3866  key->sk_strategy == BTEqualStrategyNumber &&
3867  (key->sk_flags & SK_SEARCHARRAY))
3868  return _bt_advance_array_keys(scan, NULL, tuple, tupnatts,
3869  tupdesc, *ikey, false);
3870 
3871  /*
3872  * This indextuple doesn't match the qual.
3873  */
3874  return false;
3875  }
3876  }
3877 
3878  /* If we get here, the tuple passes all index quals. */
3879  return true;
3880 }
3881 
3882 /*
3883  * Test whether an indextuple satisfies a row-comparison scan condition.
3884  *
3885  * Return true if so, false if not. If not, also clear *continuescan if
3886  * it's not possible for any future tuples in the current scan direction
3887  * to pass the qual.
3888  *
3889  * This is a subroutine for _bt_checkkeys/_bt_check_compare.
3890  */
3891 static bool
3892 _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
3893  TupleDesc tupdesc, ScanDirection dir, bool *continuescan)
3894 {
3895  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
3896  int32 cmpresult = 0;
3897  bool result;
3898 
3899  /* First subkey should be same as the header says */
3900  Assert(subkey->sk_attno == skey->sk_attno);
3901 
3902  /* Loop over columns of the row condition */
3903  for (;;)
3904  {
3905  Datum datum;
3906  bool isNull;
3907 
3908  Assert(subkey->sk_flags & SK_ROW_MEMBER);
3909 
3910  if (subkey->sk_attno > tupnatts)
3911  {
3912  /*
3913  * This attribute is truncated (must be high key). The value for
3914  * this attribute in the first non-pivot tuple on the page to the
3915  * right could be any possible value. Assume that truncated
3916  * attribute passes the qual.
3917  */
3918  Assert(BTreeTupleIsPivot(tuple));
3919  cmpresult = 0;
3920  if (subkey->sk_flags & SK_ROW_END)
3921  break;
3922  subkey++;
3923  continue;
3924  }
3925 
3926  datum = index_getattr(tuple,
3927  subkey->sk_attno,
3928  tupdesc,
3929  &isNull);
3930 
3931  if (isNull)
3932  {
3933  if (subkey->sk_flags & SK_BT_NULLS_FIRST)
3934  {
3935  /*
3936  * Since NULLs are sorted before non-NULLs, we know we have
3937  * reached the lower limit of the range of values for this
3938  * index attr. On a backward scan, we can stop if this qual
3939  * is one of the "must match" subset. We can stop regardless
3940  * of whether the qual is > or <, so long as it's required,
3941  * because it's not possible for any future tuples to pass. On
3942  * a forward scan, however, we must keep going, because we may
3943  * have initially positioned to the start of the index.
3944  * (_bt_advance_array_keys also relies on this behavior during
3945  * forward scans.)
3946  */
3947  if ((subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
3949  *continuescan = false;
3950  }
3951  else
3952  {
3953  /*
3954  * Since NULLs are sorted after non-NULLs, we know we have
3955  * reached the upper limit of the range of values for this
3956  * index attr. On a forward scan, we can stop if this qual is
3957  * one of the "must match" subset. We can stop regardless of
3958  * whether the qual is > or <, so long as it's required,
3959  * because it's not possible for any future tuples to pass. On
3960  * a backward scan, however, we must keep going, because we
3961  * may have initially positioned to the end of the index.
3962  * (_bt_advance_array_keys also relies on this behavior during
3963  * backward scans.)
3964  */
3965  if ((subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
3967  *continuescan = false;
3968  }
3969 
3970  /*
3971  * In any case, this indextuple doesn't match the qual.
3972  */
3973  return false;
3974  }
3975 
3976  if (subkey->sk_flags & SK_ISNULL)
3977  {
3978  /*
3979  * Unlike the simple-scankey case, this isn't a disallowed case.
3980  * But it can never match. If all the earlier row comparison
3981  * columns are required for the scan direction, we can stop the
3982  * scan, because there can't be another tuple that will succeed.
3983  */
3984  if (subkey != (ScanKey) DatumGetPointer(skey->sk_argument))
3985  subkey--;
3986  if ((subkey->sk_flags & SK_BT_REQFWD) &&
3988  *continuescan = false;
3989  else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
3991  *continuescan = false;
3992  return false;
3993  }
3994 
3995  /* Perform the test --- three-way comparison not bool operator */
3996  cmpresult = DatumGetInt32(FunctionCall2Coll(&subkey->sk_func,
3997  subkey->sk_collation,
3998  datum,
3999  subkey->sk_argument));
4000 
4001  if (subkey->sk_flags & SK_BT_DESC)
4002  INVERT_COMPARE_RESULT(cmpresult);
4003 
4004  /* Done comparing if unequal, else advance to next column */
4005  if (cmpresult != 0)
4006  break;
4007 
4008  if (subkey->sk_flags & SK_ROW_END)
4009  break;
4010  subkey++;
4011  }
4012 
4013  /*
4014  * At this point cmpresult indicates the overall result of the row
4015  * comparison, and subkey points to the deciding column (or the last
4016  * column if the result is "=").
4017  */
4018  switch (subkey->sk_strategy)
4019  {
4020  /* EQ and NE cases aren't allowed here */
4021  case BTLessStrategyNumber:
4022  result = (cmpresult < 0);
4023  break;
4025  result = (cmpresult <= 0);
4026  break;
4028  result = (cmpresult >= 0);
4029  break;
4031  result = (cmpresult > 0);
4032  break;
4033  default:
4034  elog(ERROR, "unrecognized RowCompareType: %d",
4035  (int) subkey->sk_strategy);
4036  result = 0; /* keep compiler quiet */
4037  break;
4038  }
4039 
4040  if (!result)
4041  {
4042  /*
4043  * Tuple fails this qual. If it's a required qual for the current
4044  * scan direction, then we can conclude no further tuples will pass,
4045  * either. Note we have to look at the deciding column, not
4046  * necessarily the first or last column of the row condition.
4047  */
4048  if ((subkey->sk_flags & SK_BT_REQFWD) &&
4050  *continuescan = false;
4051  else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
4053  *continuescan = false;
4054  }
4055 
4056  return result;
4057 }
4058 
4059 /*
4060  * Determine if a scan with array keys should skip over uninteresting tuples.
4061  *
4062  * This is a subroutine for _bt_checkkeys. Called when _bt_readpage's linear
4063  * search process (started after it finishes reading an initial group of
4064  * matching tuples, used to locate the start of the next group of tuples
4065  * matching the next set of required array keys) has already scanned an
4066  * excessive number of tuples whose key space is "between arrays".
4067  *
4068  * When we perform look ahead successfully, we'll sets pstate.skip, which
4069  * instructs _bt_readpage to skip ahead to that tuple next (could be past the
4070  * end of the scan's leaf page). Pages where the optimization is effective
4071  * will generally still need to skip several times. Each call here performs
4072  * only a single "look ahead" comparison of a later tuple, whose distance from
4073  * the current tuple's offset number is determined by applying heuristics.
4074  */
4075 static void
4077  int tupnatts, TupleDesc tupdesc)
4078 {
4079  ScanDirection dir = pstate->dir;
4080  OffsetNumber aheadoffnum;
4081  IndexTuple ahead;
4082 
4083  /* Avoid looking ahead when comparing the page high key */
4084  if (pstate->offnum < pstate->minoff)
4085  return;
4086 
4087  /*
4088  * Don't look ahead when there aren't enough tuples remaining on the page
4089  * (in the current scan direction) for it to be worth our while
4090  */
4091  if (ScanDirectionIsForward(dir) &&
4092  pstate->offnum >= pstate->maxoff - LOOK_AHEAD_DEFAULT_DISTANCE)
4093  return;
4094  else if (ScanDirectionIsBackward(dir) &&
4095  pstate->offnum <= pstate->minoff + LOOK_AHEAD_DEFAULT_DISTANCE)
4096  return;
4097 
4098  /*
4099  * The look ahead distance starts small, and ramps up as each call here
4100  * allows _bt_readpage to skip over more tuples
4101  */
4102  if (!pstate->targetdistance)
4104  else
4105  pstate->targetdistance *= 2;
4106 
4107  /* Don't read past the end (or before the start) of the page, though */
4108  if (ScanDirectionIsForward(dir))
4109  aheadoffnum = Min((int) pstate->maxoff,
4110  (int) pstate->offnum + pstate->targetdistance);
4111  else
4112  aheadoffnum = Max((int) pstate->minoff,
4113  (int) pstate->offnum - pstate->targetdistance);
4114 
4115  ahead = (IndexTuple) PageGetItem(pstate->page,
4116  PageGetItemId(pstate->page, aheadoffnum));
4117  if (_bt_tuple_before_array_skeys(scan, dir, ahead, tupdesc, tupnatts,
4118  false, 0, NULL))
4119  {
4120  /*
4121  * Success -- instruct _bt_readpage to skip ahead to very next tuple
4122  * after the one we determined was still before the current array keys
4123  */
4124  if (ScanDirectionIsForward(dir))
4125  pstate->skip = aheadoffnum + 1;
4126  else
4127  pstate->skip = aheadoffnum - 1;
4128  }
4129  else
4130  {
4131  /*
4132  * Failure -- "ahead" tuple is too far ahead (we were too aggressive).
4133  *
4134  * Reset the number of rechecks, and aggressively reduce the target
4135  * distance (we're much more aggressive here than we were when the
4136  * distance was initially ramped up).
4137  */
4138  pstate->rechecks = 0;
4139  pstate->targetdistance = Max(pstate->targetdistance / 8, 1);
4140  }
4141 }
4142 
4143 /*
4144  * _bt_killitems - set LP_DEAD state for items an indexscan caller has
4145  * told us were killed
4146  *
4147  * scan->opaque, referenced locally through so, contains information about the
4148  * current page and killed tuples thereon (generally, this should only be
4149  * called if so->numKilled > 0).
4150  *
4151  * The caller does not have a lock on the page and may or may not have the
4152  * page pinned in a buffer. Note that read-lock is sufficient for setting
4153  * LP_DEAD status (which is only a hint).
4154  *
4155  * We match items by heap TID before assuming they are the right ones to
4156  * delete. We cope with cases where items have moved right due to insertions.
4157  * If an item has moved off the current page due to a split, we'll fail to
4158  * find it and do nothing (this is not an error case --- we assume the item
4159  * will eventually get marked in a future indexscan).
4160  *
4161  * Note that if we hold a pin on the target page continuously from initially
4162  * reading the items until applying this function, VACUUM cannot have deleted
4163  * any items from the page, and so there is no need to search left from the
4164  * recorded offset. (This observation also guarantees that the item is still
4165  * the right one to delete, which might otherwise be questionable since heap
4166  * TIDs can get recycled.) This holds true even if the page has been modified
4167  * by inserts and page splits, so there is no need to consult the LSN.
4168  *
4169  * If the pin was released after reading the page, then we re-read it. If it
4170  * has been modified since we read it (as determined by the LSN), we dare not
4171  * flag any entries because it is possible that the old entry was vacuumed
4172  * away and the TID was re-used by a completely different heap tuple.
4173  */
4174 void
4176 {
4177  BTScanOpaque so = (BTScanOpaque) scan->opaque;
4178  Page page;
4179  BTPageOpaque opaque;
4180  OffsetNumber minoff;
4181  OffsetNumber maxoff;
4182  int i;
4183  int numKilled = so->numKilled;
4184  bool killedsomething = false;
4185  bool droppedpin PG_USED_FOR_ASSERTS_ONLY;
4186 
4188 
4189  /*
4190  * Always reset the scan state, so we don't look for same items on other
4191  * pages.
4192  */
4193  so->numKilled = 0;
4194 
4195  if (BTScanPosIsPinned(so->currPos))
4196  {
4197  /*
4198  * We have held the pin on this page since we read the index tuples,
4199  * so all we need to do is lock it. The pin will have prevented
4200  * re-use of any TID on the page, so there is no need to check the
4201  * LSN.
4202  */
4203  droppedpin = false;
4205 
4206  page = BufferGetPage(so->currPos.buf);
4207  }
4208  else
4209  {
4210  Buffer buf;
4211 
4212  droppedpin = true;
4213  /* Attempt to re-read the buffer, getting pin and lock. */
4215 
4216  page = BufferGetPage(buf);
4217  if (BufferGetLSNAtomic(buf) == so->currPos.lsn)
4218  so->currPos.buf = buf;
4219  else
4220  {
4221  /* Modified while not pinned means hinting is not safe. */
4222  _bt_relbuf(scan->indexRelation, buf);
4223  return;
4224  }
4225  }
4226 
4227  opaque = BTPageGetOpaque(page);
4228  minoff = P_FIRSTDATAKEY(opaque);
4229  maxoff = PageGetMaxOffsetNumber(page);
4230 
4231  for (i = 0; i < numKilled; i++)
4232  {
4233  int itemIndex = so->killedItems[i];
4234  BTScanPosItem *kitem = &so->currPos.items[itemIndex];
4235  OffsetNumber offnum = kitem->indexOffset;
4236 
4237  Assert(itemIndex >= so->currPos.firstItem &&
4238  itemIndex <= so->currPos.lastItem);
4239  if (offnum < minoff)
4240  continue; /* pure paranoia */
4241  while (offnum <= maxoff)
4242  {
4243  ItemId iid = PageGetItemId(page, offnum);
4244  IndexTuple ituple = (IndexTuple) PageGetItem(page, iid);
4245  bool killtuple = false;
4246 
4247  if (BTreeTupleIsPosting(ituple))
4248  {
4249  int pi = i + 1;
4250  int nposting = BTreeTupleGetNPosting(ituple);
4251  int j;
4252 
4253  /*
4254  * We rely on the convention that heap TIDs in the scanpos
4255  * items array are stored in ascending heap TID order for a
4256  * group of TIDs that originally came from a posting list
4257  * tuple. This convention even applies during backwards
4258  * scans, where returning the TIDs in descending order might
4259  * seem more natural. This is about effectiveness, not
4260  * correctness.
4261  *
4262  * Note that the page may have been modified in almost any way
4263  * since we first read it (in the !droppedpin case), so it's
4264  * possible that this posting list tuple wasn't a posting list
4265  * tuple when we first encountered its heap TIDs.
4266  */
4267  for (j = 0; j < nposting; j++)
4268  {
4269  ItemPointer item = BTreeTupleGetPostingN(ituple, j);
4270 
4271  if (!ItemPointerEquals(item, &kitem->heapTid))
4272  break; /* out of posting list loop */
4273 
4274  /*
4275  * kitem must have matching offnum when heap TIDs match,
4276  * though only in the common case where the page can't
4277  * have been concurrently modified
4278  */
4279  Assert(kitem->indexOffset == offnum || !droppedpin);
4280 
4281  /*
4282  * Read-ahead to later kitems here.
4283  *
4284  * We rely on the assumption that not advancing kitem here
4285  * will prevent us from considering the posting list tuple
4286  * fully dead by not matching its next heap TID in next
4287  * loop iteration.
4288  *
4289  * If, on the other hand, this is the final heap TID in
4290  * the posting list tuple, then tuple gets killed
4291  * regardless (i.e. we handle the case where the last
4292  * kitem is also the last heap TID in the last index tuple
4293  * correctly -- posting tuple still gets killed).
4294  */
4295  if (pi < numKilled)
4296  kitem = &so->currPos.items[so->killedItems[pi++]];
4297  }
4298 
4299  /*
4300  * Don't bother advancing the outermost loop's int iterator to
4301  * avoid processing killed items that relate to the same
4302  * offnum/posting list tuple. This micro-optimization hardly
4303  * seems worth it. (Further iterations of the outermost loop
4304  * will fail to match on this same posting list's first heap
4305  * TID instead, so we'll advance to the next offnum/index
4306  * tuple pretty quickly.)
4307  */
4308  if (j == nposting)
4309  killtuple = true;
4310  }
4311  else if (ItemPointerEquals(&ituple->t_tid, &kitem->heapTid))
4312  killtuple = true;
4313 
4314  /*
4315  * Mark index item as dead, if it isn't already. Since this
4316  * happens while holding a buffer lock possibly in shared mode,
4317  * it's possible that multiple processes attempt to do this
4318  * simultaneously, leading to multiple full-page images being sent
4319  * to WAL (if wal_log_hints or data checksums are enabled), which
4320  * is undesirable.
4321  */
4322  if (killtuple && !ItemIdIsDead(iid))
4323  {
4324  /* found the item/all posting list items */
4325  ItemIdMarkDead(iid);
4326  killedsomething = true;
4327  break; /* out of inner search loop */
4328  }
4329  offnum = OffsetNumberNext(offnum);
4330  }
4331  }
4332 
4333  /*
4334  * Since this can be redone later if needed, mark as dirty hint.
4335  *
4336  * Whenever we mark anything LP_DEAD, we also set the page's
4337  * BTP_HAS_GARBAGE flag, which is likewise just a hint. (Note that we
4338  * only rely on the page-level flag in !heapkeyspace indexes.)
4339  */
4340  if (killedsomething)
4341  {
4342  opaque->btpo_flags |= BTP_HAS_GARBAGE;
4343  MarkBufferDirtyHint(so->currPos.buf, true);
4344  }
4345 
4346  _bt_unlockbuf(scan->indexRelation, so->currPos.buf);
4347 }
4348 
4349 
4350 /*
4351  * The following routines manage a shared-memory area in which we track
4352  * assignment of "vacuum cycle IDs" to currently-active btree vacuuming
4353  * operations. There is a single counter which increments each time we
4354  * start a vacuum to assign it a cycle ID. Since multiple vacuums could
4355  * be active concurrently, we have to track the cycle ID for each active
4356  * vacuum; this requires at most MaxBackends entries (usually far fewer).
4357  * We assume at most one vacuum can be active for a given index.
4358  *
4359  * Access to the shared memory area is controlled by BtreeVacuumLock.
4360  * In principle we could use a separate lmgr locktag for each index,
4361  * but a single LWLock is much cheaper, and given the short time that
4362  * the lock is ever held, the concurrency hit should be minimal.
4363  */
4364 
4365 typedef struct BTOneVacInfo
4366 {
4367  LockRelId relid; /* global identifier of an index */
4368  BTCycleId cycleid; /* cycle ID for its active VACUUM */
4370 
4371 typedef struct BTVacInfo
4372 {
4373  BTCycleId cycle_ctr; /* cycle ID most recently assigned */
4374  int num_vacuums; /* number of currently active VACUUMs */
4375  int max_vacuums; /* allocated length of vacuums[] array */
4378 
4380 
4381 
4382 /*
4383  * _bt_vacuum_cycleid --- get the active vacuum cycle ID for an index,
4384  * or zero if there is no active VACUUM
4385  *
4386  * Note: for correct interlocking, the caller must already hold pin and
4387  * exclusive lock on each buffer it will store the cycle ID into. This
4388  * ensures that even if a VACUUM starts immediately afterwards, it cannot
4389  * process those pages until the page split is complete.
4390  */
4391 BTCycleId
4393 {
4394  BTCycleId result = 0;
4395  int i;
4396 
4397  /* Share lock is enough since this is a read-only operation */
4398  LWLockAcquire(BtreeVacuumLock, LW_SHARED);
4399 
4400  for (i = 0; i < btvacinfo->num_vacuums; i++)
4401  {
4402  BTOneVacInfo *vac = &btvacinfo->vacuums[i];
4403 
4404  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
4405  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
4406  {
4407  result = vac->cycleid;
4408  break;
4409  }
4410  }
4411 
4412  LWLockRelease(BtreeVacuumLock);
4413  return result;
4414 }
4415 
4416 /*
4417  * _bt_start_vacuum --- assign a cycle ID to a just-starting VACUUM operation
4418  *
4419  * Note: the caller must guarantee that it will eventually call
4420  * _bt_end_vacuum, else we'll permanently leak an array slot. To ensure
4421  * that this happens even in elog(FATAL) scenarios, the appropriate coding
4422  * is not just a PG_TRY, but
4423  * PG_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel))
4424  */
4425 BTCycleId
4427 {
4428  BTCycleId result;
4429  int i;
4430  BTOneVacInfo *vac;
4431 
4432  LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
4433 
4434  /*
4435  * Assign the next cycle ID, being careful to avoid zero as well as the
4436  * reserved high values.
4437  */
4438  result = ++(btvacinfo->cycle_ctr);
4439  if (result == 0 || result > MAX_BT_CYCLE_ID)
4440  result = btvacinfo->cycle_ctr = 1;
4441 
4442  /* Let's just make sure there's no entry already for this index */
4443  for (i = 0; i < btvacinfo->num_vacuums; i++)
4444  {
4445  vac = &btvacinfo->vacuums[i];
4446  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
4447  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
4448  {
4449  /*
4450  * Unlike most places in the backend, we have to explicitly
4451  * release our LWLock before throwing an error. This is because
4452  * we expect _bt_end_vacuum() to be called before transaction
4453  * abort cleanup can run to release LWLocks.
4454  */
4455  LWLockRelease(BtreeVacuumLock);
4456  elog(ERROR, "multiple active vacuums for index \"%s\"",
4458  }
4459  }
4460 
4461  /* OK, add an entry */
4463  {
4464  LWLockRelease(BtreeVacuumLock);
4465  elog(ERROR, "out of btvacinfo slots");
4466  }
4468  vac->relid = rel->rd_lockInfo.lockRelId;
4469  vac->cycleid = result;
4471 
4472  LWLockRelease(BtreeVacuumLock);
4473  return result;
4474 }
4475 
4476 /*
4477  * _bt_end_vacuum --- mark a btree VACUUM operation as done
4478  *
4479  * Note: this is deliberately coded not to complain if no entry is found;
4480  * this allows the caller to put PG_TRY around the start_vacuum operation.
4481  */
4482 void
4484 {
4485  int i;
4486 
4487  LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
4488 
4489  /* Find the array entry */
4490  for (i = 0; i < btvacinfo->num_vacuums; i++)
4491  {
4492  BTOneVacInfo *vac = &btvacinfo->vacuums[i];
4493 
4494  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
4495  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
4496  {
4497  /* Remove it by shifting down the last entry */
4498  *vac = btvacinfo->vacuums[btvacinfo->num_vacuums - 1];
4500  break;
4501  }
4502  }
4503 
4504  LWLockRelease(BtreeVacuumLock);
4505 }
4506 
4507 /*
4508  * _bt_end_vacuum wrapped as an on_shmem_exit callback function
4509  */
4510 void
4512 {
4514 }
4515 
4516 /*
4517  * BTreeShmemSize --- report amount of shared memory space needed
4518  */
4519 Size
4521 {
4522  Size size;
4523 
4524  size = offsetof(BTVacInfo, vacuums);
4526  return size;
4527 }
4528 
4529 /*
4530  * BTreeShmemInit --- initialize this module's shared memory
4531  */
4532 void
4534 {
4535  bool found;
4536 
4537  btvacinfo = (BTVacInfo *) ShmemInitStruct("BTree Vacuum State",
4538  BTreeShmemSize(),
4539  &found);
4540 
4541  if (!IsUnderPostmaster)
4542  {
4543  /* Initialize shared memory area */
4544  Assert(!found);
4545 
4546  /*
4547  * It doesn't really matter what the cycle counter starts at, but
4548  * having it always start the same doesn't seem good. Seed with
4549  * low-order bits of time() instead.
4550  */
4551  btvacinfo->cycle_ctr = (BTCycleId) time(NULL);
4552 
4553  btvacinfo->num_vacuums = 0;
4555  }
4556  else
4557  Assert(found);
4558 }
4559 
4560 bytea *
4561 btoptions(Datum reloptions, bool validate)
4562 {
4563  static const relopt_parse_elt tab[] = {
4564  {"fillfactor", RELOPT_TYPE_INT, offsetof(BTOptions, fillfactor)},
4565  {"vacuum_cleanup_index_scale_factor", RELOPT_TYPE_REAL,
4566  offsetof(BTOptions, vacuum_cleanup_index_scale_factor)},
4567  {"deduplicate_items", RELOPT_TYPE_BOOL,
4568  offsetof(BTOptions, deduplicate_items)}
4569  };
4570 
4571  return (bytea *) build_reloptions(reloptions, validate,
4573  sizeof(BTOptions),
4574  tab, lengthof(tab));
4575 }
4576 
4577 /*
4578  * btproperty() -- Check boolean properties of indexes.
4579  *
4580  * This is optional, but handling AMPROP_RETURNABLE here saves opening the rel
4581  * to call btcanreturn.
4582  */
4583 bool
4584 btproperty(Oid index_oid, int attno,
4585  IndexAMProperty prop, const char *propname,
4586  bool *res, bool *isnull)
4587 {
4588  switch (prop)
4589  {
4590  case AMPROP_RETURNABLE:
4591  /* answer only for columns, not AM or whole index */
4592  if (attno == 0)
4593  return false;
4594  /* otherwise, btree can always return data */
4595  *res = true;
4596  return true;
4597 
4598  default:
4599  return false; /* punt to generic code */
4600  }
4601 }
4602 
4603 /*
4604  * btbuildphasename() -- Return name of index build phase.
4605  */
4606 char *
4607 btbuildphasename(int64 phasenum)
4608 {
4609  switch (phasenum)
4610  {
4612  return "initializing";
4614  return "scanning table";
4616  return "sorting live tuples";
4618  return "sorting dead tuples";
4620  return "loading tuples in tree";
4621  default:
4622  return NULL;
4623  }
4624 }
4625 
4626 /*
4627  * _bt_truncate() -- create tuple without unneeded suffix attributes.
4628  *
4629  * Returns truncated pivot index tuple allocated in caller's memory context,
4630  * with key attributes copied from caller's firstright argument. If rel is
4631  * an INCLUDE index, non-key attributes will definitely be truncated away,
4632  * since they're not part of the key space. More aggressive suffix
4633  * truncation can take place when it's clear that the returned tuple does not
4634  * need one or more suffix key attributes. We only need to keep firstright
4635  * attributes up to and including the first non-lastleft-equal attribute.
4636  * Caller's insertion scankey is used to compare the tuples; the scankey's
4637  * argument values are not considered here.
4638  *
4639  * Note that returned tuple's t_tid offset will hold the number of attributes
4640  * present, so the original item pointer offset is not represented. Caller
4641  * should only change truncated tuple's downlink. Note also that truncated
4642  * key attributes are treated as containing "minus infinity" values by
4643  * _bt_compare().
4644  *
4645  * In the worst case (when a heap TID must be appended to distinguish lastleft
4646  * from firstright), the size of the returned tuple is the size of firstright
4647  * plus the size of an additional MAXALIGN()'d item pointer. This guarantee
4648  * is important, since callers need to stay under the 1/3 of a page
4649  * restriction on tuple size. If this routine is ever taught to truncate
4650  * within an attribute/datum, it will need to avoid returning an enlarged
4651  * tuple to caller when truncation + TOAST compression ends up enlarging the
4652  * final datum.
4653  */
4654 IndexTuple
4655 _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
4656  BTScanInsert itup_key)
4657 {
4658  TupleDesc itupdesc = RelationGetDescr(rel);
4660  int keepnatts;
4661  IndexTuple pivot;
4662  IndexTuple tidpivot;
4663  ItemPointer pivotheaptid;
4664  Size newsize;
4665 
4666  /*
4667  * We should only ever truncate non-pivot tuples from leaf pages. It's
4668  * never okay to truncate when splitting an internal page.
4669  */
4670  Assert(!BTreeTupleIsPivot(lastleft) && !BTreeTupleIsPivot(firstright));
4671 
4672  /* Determine how many attributes must be kept in truncated tuple */
4673  keepnatts = _bt_keep_natts(rel, lastleft, firstright, itup_key);
4674 
4675 #ifdef DEBUG_NO_TRUNCATE
4676  /* Force truncation to be ineffective for testing purposes */
4677  keepnatts = nkeyatts + 1;
4678 #endif
4679 
4680  pivot = index_truncate_tuple(itupdesc, firstright,
4681  Min(keepnatts, nkeyatts));
4682 
4683  if (BTreeTupleIsPosting(pivot))
4684  {
4685  /*
4686  * index_truncate_tuple() just returns a straight copy of firstright
4687  * when it has no attributes to truncate. When that happens, we may
4688  * need to truncate away a posting list here instead.
4689  */
4690  Assert(keepnatts == nkeyatts || keepnatts == nkeyatts + 1);
4691  Assert(IndexRelationGetNumberOfAttributes(rel) == nkeyatts);
4692  pivot->t_info &= ~INDEX_SIZE_MASK;
4693  pivot->t_info |= MAXALIGN(BTreeTupleGetPostingOffset(firstright));
4694  }
4695 
4696  /*
4697  * If there is a distinguishing key attribute within pivot tuple, we're
4698  * done
4699  */
4700  if (keepnatts <= nkeyatts)
4701  {
4702  BTreeTupleSetNAtts(pivot, keepnatts, false);
4703  return pivot;
4704  }
4705 
4706  /*
4707  * We have to store a heap TID in the new pivot tuple, since no non-TID
4708  * key attribute value in firstright distinguishes the right side of the
4709  * split from the left side. nbtree conceptualizes this case as an
4710  * inability to truncate away any key attributes, since heap TID is
4711  * treated as just another key attribute (despite lacking a pg_attribute
4712  * entry).
4713  *
4714  * Use enlarged space that holds a copy of pivot. We need the extra space
4715  * to store a heap TID at the end (using the special pivot tuple
4716  * representation). Note that the original pivot already has firstright's
4717  * possible posting list/non-key attribute values removed at this point.
4718  */
4719  newsize = MAXALIGN(IndexTupleSize(pivot)) + MAXALIGN(sizeof(ItemPointerData));
4720  tidpivot = palloc0(newsize);
4721  memcpy(tidpivot, pivot, MAXALIGN(IndexTupleSize(pivot)));
4722  /* Cannot leak memory here */
4723  pfree(pivot);
4724 
4725  /*
4726  * Store all of firstright's key attribute values plus a tiebreaker heap
4727  * TID value in enlarged pivot tuple
4728  */
4729  tidpivot->t_info &= ~INDEX_SIZE_MASK;
4730  tidpivot->t_info |= newsize;
4731  BTreeTupleSetNAtts(tidpivot, nkeyatts, true);
4732  pivotheaptid = BTreeTupleGetHeapTID(tidpivot);
4733 
4734  /*
4735  * Lehman & Yao use lastleft as the leaf high key in all cases, but don't
4736  * consider suffix truncation. It seems like a good idea to follow that
4737  * example in cases where no truncation takes place -- use lastleft's heap
4738  * TID. (This is also the closest value to negative infinity that's
4739  * legally usable.)
4740  */
4741  ItemPointerCopy(BTreeTupleGetMaxHeapTID(lastleft), pivotheaptid);
4742 
4743  /*
4744  * We're done. Assert() that heap TID invariants hold before returning.
4745  *
4746  * Lehman and Yao require that the downlink to the right page, which is to
4747  * be inserted into the parent page in the second phase of a page split be
4748  * a strict lower bound on items on the right page, and a non-strict upper
4749  * bound for items on the left page. Assert that heap TIDs follow these
4750  * invariants, since a heap TID value is apparently needed as a
4751  * tiebreaker.
4752  */
4753 #ifndef DEBUG_NO_TRUNCATE
4755  BTreeTupleGetHeapTID(firstright)) < 0);
4756  Assert(ItemPointerCompare(pivotheaptid,
4757  BTreeTupleGetHeapTID(lastleft)) >= 0);
4758  Assert(ItemPointerCompare(pivotheaptid,
4759  BTreeTupleGetHeapTID(firstright)) < 0);
4760 #else
4761 
4762  /*
4763  * Those invariants aren't guaranteed to hold for lastleft + firstright
4764  * heap TID attribute values when they're considered here only because
4765  * DEBUG_NO_TRUNCATE is defined (a heap TID is probably not actually
4766  * needed as a tiebreaker). DEBUG_NO_TRUNCATE must therefore use a heap
4767  * TID value that always works as a strict lower bound for items to the
4768  * right. In particular, it must avoid using firstright's leading key
4769  * attribute values along with lastleft's heap TID value when lastleft's
4770  * TID happens to be greater than firstright's TID.
4771  */
4772  ItemPointerCopy(BTreeTupleGetHeapTID(firstright), pivotheaptid);
4773 
4774  /*
4775  * Pivot heap TID should never be fully equal to firstright. Note that
4776  * the pivot heap TID will still end up equal to lastleft's heap TID when
4777  * that's the only usable value.
4778  */
4779  ItemPointerSetOffsetNumber(pivotheaptid,
4781  Assert(ItemPointerCompare(pivotheaptid,
4782  BTreeTupleGetHeapTID(firstright)) < 0);
4783 #endif
4784 
4785  return tidpivot;
4786 }
4787 
4788 /*
4789  * _bt_keep_natts - how many key attributes to keep when truncating.
4790  *
4791  * Caller provides two tuples that enclose a split point. Caller's insertion
4792  * scankey is used to compare the tuples; the scankey's argument values are
4793  * not considered here.
4794  *
4795  * This can return a number of attributes that is one greater than the
4796  * number of key attributes for the index relation. This indicates that the
4797  * caller must use a heap TID as a unique-ifier in new pivot tuple.
4798  */
4799 static int
4800 _bt_keep_natts(Relation rel, IndexTuple lastleft, IndexTuple firstright,
4801  BTScanInsert itup_key)
4802 {
4803  int nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
4804  TupleDesc itupdesc = RelationGetDescr(rel);
4805  int keepnatts;
4806  ScanKey scankey;
4807 
4808  /*
4809  * _bt_compare() treats truncated key attributes as having the value minus
4810  * infinity, which would break searches within !heapkeyspace indexes. We
4811  * must still truncate away non-key attribute values, though.
4812  */
4813  if (!itup_key->heapkeyspace)
4814  return nkeyatts;
4815 
4816  scankey = itup_key->scankeys;
4817  keepnatts = 1;
4818  for (int attnum = 1; attnum <= nkeyatts; attnum++, scankey++)
4819  {
4820  Datum datum1,
4821  datum2;
4822  bool isNull1,
4823  isNull2;
4824 
4825  datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
4826  datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
4827 
4828  if (isNull1 != isNull2)
4829  break;
4830 
4831  if (!isNull1 &&
4833  scankey->sk_collation,
4834  datum1,
4835  datum2)) != 0)
4836  break;
4837 
4838  keepnatts++;
4839  }
4840 
4841  /*
4842  * Assert that _bt_keep_natts_fast() agrees with us in passing. This is
4843  * expected in an allequalimage index.
4844  */
4845  Assert(!itup_key->allequalimage ||
4846  keepnatts == _bt_keep_natts_fast(rel, lastleft, firstright));
4847 
4848  return keepnatts;
4849 }
4850 
4851 /*
4852  * _bt_keep_natts_fast - fast bitwise variant of _bt_keep_natts.
4853  *
4854  * This is exported so that a candidate split point can have its effect on
4855  * suffix truncation inexpensively evaluated ahead of time when finding a
4856  * split location. A naive bitwise approach to datum comparisons is used to
4857  * save cycles.
4858  *
4859  * The approach taken here usually provides the same answer as _bt_keep_natts
4860  * will (for the same pair of tuples from a heapkeyspace index), since the
4861  * majority of btree opclasses can never indicate that two datums are equal
4862  * unless they're bitwise equal after detoasting. When an index only has
4863  * "equal image" columns, routine is guaranteed to give the same result as
4864  * _bt_keep_natts would.
4865  *
4866  * Callers can rely on the fact that attributes considered equal here are
4867  * definitely also equal according to _bt_keep_natts, even when the index uses
4868  * an opclass or collation that is not "allequalimage"/deduplication-safe.
4869  * This weaker guarantee is good enough for nbtsplitloc.c caller, since false
4870  * negatives generally only have the effect of making leaf page splits use a
4871  * more balanced split point.
4872  */
4873 int
4875 {
4876  TupleDesc itupdesc = RelationGetDescr(rel);
4877  int keysz = IndexRelationGetNumberOfKeyAttributes(rel);
4878  int keepnatts;
4879 
4880  keepnatts = 1;
4881  for (int attnum = 1; attnum <= keysz; attnum++)
4882  {
4883  Datum datum1,
4884  datum2;
4885  bool isNull1,
4886  isNull2;
4887  Form_pg_attribute att;
4888 
4889  datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
4890  datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
4891  att = TupleDescAttr(itupdesc, attnum - 1);
4892 
4893  if (isNull1 != isNull2)
4894  break;
4895 
4896  if (!isNull1 &&
4897  !datum_image_eq(datum1, datum2, att->attbyval, att->attlen))
4898  break;
4899 
4900  keepnatts++;
4901  }
4902 
4903  return keepnatts;
4904 }
4905 
4906 /*
4907  * _bt_check_natts() -- Verify tuple has expected number of attributes.
4908  *
4909  * Returns value indicating if the expected number of attributes were found
4910  * for a particular offset on page. This can be used as a general purpose
4911  * sanity check.
4912  *
4913  * Testing a tuple directly with BTreeTupleGetNAtts() should generally be
4914  * preferred to calling here. That's usually more convenient, and is always
4915  * more explicit. Call here instead when offnum's tuple may be a negative
4916  * infinity tuple that uses the pre-v11 on-disk representation, or when a low
4917  * context check is appropriate. This routine is as strict as possible about
4918  * what is expected on each version of btree.
4919  */
4920 bool
4921 _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
4922 {
4925  BTPageOpaque opaque = BTPageGetOpaque(page);
4926  IndexTuple itup;
4927  int tupnatts;
4928 
4929  /*
4930  * We cannot reliably test a deleted or half-dead page, since they have
4931  * dummy high keys
4932  */
4933  if (P_IGNORE(opaque))
4934  return true;
4935 
4936  Assert(offnum >= FirstOffsetNumber &&
4937  offnum <= PageGetMaxOffsetNumber(page));
4938 
4939  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
4940  tupnatts = BTreeTupleGetNAtts(itup, rel);
4941 
4942  /* !heapkeyspace indexes do not support deduplication */
4943  if (!heapkeyspace && BTreeTupleIsPosting(itup))
4944  return false;
4945 
4946  /* Posting list tuples should never have "pivot heap TID" bit set */
4947  if (BTreeTupleIsPosting(itup) &&
4949  BT_PIVOT_HEAP_TID_ATTR) != 0)
4950  return false;
4951 
4952  /* INCLUDE indexes do not support deduplication */
4953  if (natts != nkeyatts && BTreeTupleIsPosting(itup))
4954  return false;
4955 
4956  if (P_ISLEAF(opaque))
4957  {
4958  if (offnum >= P_FIRSTDATAKEY(opaque))
4959  {
4960  /*
4961  * Non-pivot tuple should never be explicitly marked as a pivot
4962  * tuple
4963  */
4964  if (BTreeTupleIsPivot(itup))
4965  return false;
4966 
4967  /*
4968  * Leaf tuples that are not the page high key (non-pivot tuples)
4969  * should never be truncated. (Note that tupnatts must have been
4970  * inferred, even with a posting list tuple, because only pivot
4971  * tuples store tupnatts directly.)
4972  */
4973  return tupnatts == natts;
4974  }
4975  else
4976  {
4977  /*
4978  * Rightmost page doesn't contain a page high key, so tuple was
4979  * checked above as ordinary leaf tuple
4980  */
4981  Assert(!P_RIGHTMOST(opaque));
4982 
4983  /*
4984  * !heapkeyspace high key tuple contains only key attributes. Note
4985  * that tupnatts will only have been explicitly represented in
4986  * !heapkeyspace indexes that happen to have non-key attributes.
4987  */
4988  if (!heapkeyspace)
4989  return tupnatts == nkeyatts;
4990 
4991  /* Use generic heapkeyspace pivot tuple handling */
4992  }
4993  }
4994  else /* !P_ISLEAF(opaque) */
4995  {
4996  if (offnum == P_FIRSTDATAKEY(opaque))
4997  {
4998  /*
4999  * The first tuple on any internal page (possibly the first after
5000  * its high key) is its negative infinity tuple. Negative
5001  * infinity tuples are always truncated to zero attributes. They
5002  * are a particular kind of pivot tuple.
5003  */
5004  if (heapkeyspace)
5005  return tupnatts == 0;
5006 
5007  /*
5008  * The number of attributes won't be explicitly represented if the
5009  * negative infinity tuple was generated during a page split that
5010  * occurred with a version of Postgres before v11. There must be
5011  * a problem when there is an explicit representation that is
5012  * non-zero, or when there is no explicit representation and the
5013  * tuple is evidently not a pre-pg_upgrade tuple.
5014  *
5015  * Prior to v11, downlinks always had P_HIKEY as their offset.
5016  * Accept that as an alternative indication of a valid
5017  * !heapkeyspace negative infinity tuple.
5018  */
5019  return tupnatts == 0 ||
5021  }
5022  else
5023  {
5024  /*
5025  * !heapkeyspace downlink tuple with separator key contains only
5026  * key attributes. Note that tupnatts will only have been
5027  * explicitly represented in !heapkeyspace indexes that happen to
5028  * have non-key attributes.
5029  */
5030  if (!heapkeyspace)
5031  return tupnatts == nkeyatts;
5032 
5033  /* Use generic heapkeyspace pivot tuple handling */
5034  }
5035  }
5036 
5037  /* Handle heapkeyspace pivot tuples (excluding minus infinity items) */
5038  Assert(heapkeyspace);
5039 
5040  /*
5041  * Explicit representation of the number of attributes is mandatory with
5042  * heapkeyspace index pivot tuples, regardless of whether or not there are
5043  * non-key attributes.
5044  */
5045  if (!BTreeTupleIsPivot(itup))
5046  return false;
5047 
5048  /* Pivot tuple should not use posting list representation (redundant) */
5049  if (BTreeTupleIsPosting(itup))
5050  return false;
5051 
5052  /*
5053  * Heap TID is a tiebreaker key attribute, so it cannot be untruncated
5054  * when any other key attribute is truncated
5055  */
5056  if (BTreeTupleGetHeapTID(itup) != NULL && tupnatts != nkeyatts)
5057  return false;
5058 
5059  /*
5060  * Pivot tuple must have at least one untruncated key attribute (minus
5061  * infinity pivot tuples are the only exception). Pivot tuples can never
5062  * represent that there is a value present for a key attribute that
5063  * exceeds pg_index.indnkeyatts for the index.
5064  */
5065  return tupnatts > 0 && tupnatts <= nkeyatts;
5066 }
5067 
5068 /*
5069  *
5070  * _bt_check_third_page() -- check whether tuple fits on a btree page at all.
5071  *
5072  * We actually need to be able to fit three items on every page, so restrict
5073  * any one item to 1/3 the per-page available space. Note that itemsz should
5074  * not include the ItemId overhead.
5075  *
5076  * It might be useful to apply TOAST methods rather than throw an error here.
5077  * Using out of line storage would break assumptions made by suffix truncation
5078  * and by contrib/amcheck, though.
5079  */
5080 void
5081 _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace,
5082  Page page, IndexTuple newtup)
5083 {
5084  Size itemsz;
5085  BTPageOpaque opaque;
5086 
5087  itemsz = MAXALIGN(IndexTupleSize(newtup));
5088 
5089  /* Double check item size against limit */
5090  if (itemsz <= BTMaxItemSize(page))
5091  return;
5092 
5093  /*
5094  * Tuple is probably too large to fit on page, but it's possible that the
5095  * index uses version 2 or version 3, or that page is an internal page, in
5096  * which case a slightly higher limit applies.
5097  */
5098  if (!needheaptidspace && itemsz <= BTMaxItemSizeNoHeapTid(page))
5099  return;
5100 
5101  /*
5102  * Internal page insertions cannot fail here, because that would mean that
5103  * an earlier leaf level insertion that should have failed didn't
5104  */
5105  opaque = BTPageGetOpaque(page);
5106  if (!P_ISLEAF(opaque))
5107  elog(ERROR, "cannot insert oversized tuple of size %zu on internal page of index \"%s\"",
5108  itemsz, RelationGetRelationName(rel));
5109 
5110  ereport(ERROR,
5111  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
5112  errmsg("index row size %zu exceeds btree version %u maximum %zu for index \"%s\"",
5113  itemsz,
5114  needheaptidspace ? BTREE_VERSION : BTREE_NOVAC_VERSION,
5115  needheaptidspace ? BTMaxItemSize(page) :
5116  BTMaxItemSizeNoHeapTid(page),
5118  errdetail("Index row references tuple (%u,%u) in relation \"%s\".",
5121  RelationGetRelationName(heap)),
5122  errhint("Values larger than 1/3 of a buffer page cannot be indexed.\n"
5123  "Consider a function index of an MD5 hash of the value, "
5124  "or use full text indexing."),
5126 }
5127 
5128 /*
5129  * Are all attributes in rel "equality is image equality" attributes?
5130  *
5131  * We use each attribute's BTEQUALIMAGE_PROC opclass procedure. If any
5132  * opclass either lacks a BTEQUALIMAGE_PROC procedure or returns false, we
5133  * return false; otherwise we return true.
5134  *
5135  * Returned boolean value is stored in index metapage during index builds.
5136  * Deduplication can only be used when we return true.
5137  */
5138 bool
5139 _bt_allequalimage(Relation rel, bool debugmessage)
5140 {
5141  bool allequalimage = true;
5142 
5143  /* INCLUDE indexes can never support deduplication */
5146  return false;
5147 
5148  for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(rel); i++)
5149  {
5150  Oid opfamily = rel->rd_opfamily[i];
5151  Oid opcintype = rel->rd_opcintype[i];
5152  Oid collation = rel->rd_indcollation[i];
5153  Oid equalimageproc;
5154 
5155  equalimageproc = get_opfamily_proc(opfamily, opcintype, opcintype,
5157 
5158  /*
5159  * If there is no BTEQUALIMAGE_PROC then deduplication is assumed to
5160  * be unsafe. Otherwise, actually call proc and see what it says.
5161  */
5162  if (!OidIsValid(equalimageproc) ||
5163  !DatumGetBool(OidFunctionCall1Coll(equalimageproc, collation,
5164  ObjectIdGetDatum(opcintype))))
5165  {
5166  allequalimage = false;
5167  break;
5168  }
5169  }
5170 
5171  if (debugmessage)
5172  {
5173  if (allequalimage)
5174  elog(DEBUG1, "index \"%s\" can safely use deduplication",
5176  else
5177  elog(DEBUG1, "index \"%s\" cannot use deduplication",
5179  }
5180 
5181  return allequalimage;
5182 }
IndexAMProperty
Definition: amapi.h:35
@ AMPROP_RETURNABLE
Definition: amapi.h:43
#define DatumGetArrayTypeP(X)
Definition: array.h:261
#define ARR_ELEMTYPE(a)
Definition: array.h:292
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3612
int16 AttrNumber
Definition: attnum.h:21
#define InvalidAttrNumber
Definition: attnum.h:23
int Buffer
Definition: buf.h:23
XLogRecPtr BufferGetLSNAtomic(Buffer buffer)
Definition: bufmgr.c:3974
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:4960
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:404
Pointer Page
Definition: bufpage.h:78
static Item PageGetItem(Page page, ItemId itemId)
Definition: bufpage.h:351
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:240
static OffsetNumber PageGetMaxOffsetNumber(Page page)
Definition: bufpage.h:369
#define RegProcedureIsValid(p)
Definition: c.h:777
#define Min(x, y)
Definition: c.h:1004
#define INVERT_COMPARE_RESULT(var)
Definition: c.h:1106
signed short int16
Definition: c.h:493
#define MAXALIGN(LEN)
Definition: c.h:811
signed int int32
Definition: c.h:494
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:182
#define Max(x, y)
Definition: c.h:998
#define Assert(condition)
Definition: c.h:858
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:398
regproc RegProcedure
Definition: c.h:650
#define unlikely(x)
Definition: c.h:311
#define lengthof(array)
Definition: c.h:788
#define OidIsValid(objectId)
Definition: c.h:775
size_t Size
Definition: c.h:605
bool datum_image_eq(Datum value1, Datum value2, bool typByVal, int typLen)
Definition: datum.c:266
struct cursor * cur
Definition: ecpg.c:28
int errmsg_internal(const char *fmt,...)
Definition: elog.c:1157
int errdetail(const char *fmt,...)
Definition: elog.c:1203
int errhint(const char *fmt,...)
Definition: elog.c:1317
int errcode(int sqlerrcode)
Definition: elog.c:857
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define DEBUG1
Definition: elog.h:30
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
#define ereport(elevel,...)
Definition: elog.h:149
Datum OidFunctionCall2Coll(Oid functionId, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1421
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1149
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:127
void fmgr_info_cxt(Oid functionId, FmgrInfo *finfo, MemoryContext mcxt)
Definition: fmgr.c:137
Datum OidFunctionCall1Coll(Oid functionId, Oid collation, Datum arg1)
Definition: fmgr.c:1411
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
bool IsUnderPostmaster
Definition: globals.c:117
int MaxBackends
Definition: globals.c:143
for(;;)
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:860
IndexTuple index_truncate_tuple(TupleDesc sourceDescriptor, IndexTuple source, int leavenatts)
Definition: indextuple.c:576
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int j
Definition: isn.c:74
int i
Definition: isn.c:73
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
#define ItemIdMarkDead(itemId)
Definition: itemid.h:179
#define ItemIdIsDead(itemId)
Definition: itemid.h:113
int32 ItemPointerCompare(ItemPointer arg1, ItemPointer arg2)
Definition: itemptr.c:51
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:35
static void ItemPointerSetOffsetNumber(ItemPointerData *pointer, OffsetNumber offsetNumber)
Definition: itemptr.h:158
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static OffsetNumber ItemPointerGetOffsetNumberNoCheck(const ItemPointerData *pointer)
Definition: itemptr.h:114
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
static void ItemPointerCopy(const ItemPointerData *fromPointer, ItemPointerData *toPointer)
Definition: itemptr.h:172
IndexTupleData * IndexTuple
Definition: itup.h:53
#define IndexTupleSize(itup)
Definition: itup.h:70
static Datum index_getattr(IndexTuple tup, int attnum, TupleDesc tupleDesc, bool *isnull)
Definition: itup.h:117
#define INDEX_SIZE_MASK
Definition: itup.h:65
void get_typlenbyvalalign(Oid typid, int16 *typlen, bool *typbyval, char *typalign)
Definition: lsyscache.c:2271
Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, int16 procnum)
Definition: lsyscache.c:796
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1285
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:166
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1170
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1783
@ LW_SHARED
Definition: lwlock.h:115
@ LW_EXCLUSIVE
Definition: lwlock.h:114
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:383
void pfree(void *pointer)
Definition: mcxt.c:1520
void * palloc0(Size size)
Definition: mcxt.c:1346
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1180
void * palloc(Size size)
Definition: mcxt.c:1316
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_SMALL_SIZES
Definition: memutils.h:170
void _bt_relbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1023
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
Definition: nbtpage.c:739
Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access)
Definition: nbtpage.c:845
void _bt_unlockbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1070
void _bt_lockbuf(Relation rel, Buffer buf, int access)
Definition: nbtpage.c:1039
void _bt_parallel_done(IndexScanDesc scan)
Definition: nbtree.c:732
void _bt_parallel_primscan_schedule(IndexScanDesc scan, BlockNumber prev_scan_page)
Definition: nbtree.c:771
#define BTScanPosIsPinned(scanpos)
Definition: nbtree.h:999
#define BT_PIVOT_HEAP_TID_ATTR
Definition: nbtree.h:465
static uint16 BTreeTupleGetNPosting(IndexTuple posting)
Definition: nbtree.h:518
static bool BTreeTupleIsPivot(IndexTuple itup)
Definition: nbtree.h:480
#define P_ISLEAF(opaque)
Definition: nbtree.h:220
#define P_HIKEY
Definition: nbtree.h:367
#define PROGRESS_BTREE_PHASE_PERFORMSORT_2
Definition: nbtree.h:1159
#define BTMaxItemSizeNoHeapTid(page)
Definition: nbtree.h:169
#define PROGRESS_BTREE_PHASE_LEAF_LOAD
Definition: nbtree.h:1160
#define BTP_HAS_GARBAGE
Definition: nbtree.h:82
#define BTEQUALIMAGE_PROC
Definition: nbtree.h:710
#define BTORDER_PROC
Definition: nbtree.h:707
#define BTPageGetOpaque(page)
Definition: nbtree.h:73
#define BTREE_VERSION
Definition: nbtree.h:150
#define BTScanPosIsValid(scanpos)
Definition: nbtree.h:1016
#define PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN
Definition: nbtree.h:1157
#define SK_BT_INDOPTION_SHIFT
Definition: nbtree.h:1126
#define P_FIRSTDATAKEY(opaque)
Definition: nbtree.h:369
#define MAX_BT_CYCLE_ID
Definition: nbtree.h:93
#define PROGRESS_BTREE_PHASE_PERFORMSORT_1
Definition: nbtree.h:1158
uint16 BTCycleId
Definition: nbtree.h:29
static uint32 BTreeTupleGetPostingOffset(IndexTuple posting)
Definition: nbtree.h:529
#define SK_BT_REQBKWD
Definition: nbtree.h:1125
#define P_RIGHTMOST(opaque)
Definition: nbtree.h:219
#define BTMaxItemSize(page)
Definition: nbtree.h:164
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1128
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
Definition: nbtree.h:544
#define BT_READ
Definition: nbtree.h:719
#define SK_BT_REQFWD
Definition: nbtree.h:1124
#define SK_BT_DESC
Definition: nbtree.h:1127
#define P_IGNORE(opaque)
Definition: nbtree.h:225
#define BTCommuteStrategyNumber(strat)
Definition: nbtree.h:685
static ItemPointer BTreeTupleGetMaxHeapTID(IndexTuple itup)
Definition: nbtree.h:664
static bool BTreeTupleIsPosting(IndexTuple itup)
Definition: nbtree.h:492
#define BTREE_NOVAC_VERSION
Definition: nbtree.h:152
static ItemPointer BTreeTupleGetHeapTID(IndexTuple itup)
Definition: nbtree.h:638
static void BTreeTupleSetNAtts(IndexTuple itup, uint16 nkeyatts, bool heaptid)
Definition: nbtree.h:595
#define BTreeTupleGetNAtts(itup, rel)
Definition: nbtree.h:577
BTScanOpaqueData * BTScanOpaque
Definition: nbtree.h:1081
static bool _bt_merge_arrays(IndexScanDesc scan, ScanKey skey, FmgrInfo *sortproc, bool reverse, Oid origelemtype, Oid nextelemtype, Datum *elems_orig, int *nelems_orig, Datum *elems_next, int nelems_next)
Definition: nbtutils.c:893
static void _bt_rewind_nonrequired_arrays(IndexScanDesc scan, ScanDirection dir)
Definition: nbtutils.c:1467
void _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace, Page page, IndexTuple newtup)
Definition: nbtutils.c:5081
static bool _bt_check_compare(IndexScanDesc scan, ScanDirection dir, IndexTuple tuple, int tupnatts, TupleDesc tupdesc, bool advancenonrequired, bool prechecked, bool firstmatch, bool *continuescan, int *ikey)
Definition: nbtutils.c:3686
void _bt_end_vacuum(Relation rel)
Definition: nbtutils.c:4483
static ScanKey _bt_preprocess_array_keys(IndexScanDesc scan)
Definition: nbtutils.c:269
char * btbuildphasename(int64 phasenum)
Definition: nbtutils.c:4607
bool _bt_checkkeys(IndexScanDesc scan, BTReadPageState *pstate, bool arrayKeys, IndexTuple tuple, int tupnatts)
Definition: nbtutils.c:3512
void _bt_end_vacuum_callback(int code, Datum arg)
Definition: nbtutils.c:4511
static int _bt_binsrch_array_skey(FmgrInfo *orderproc, bool cur_elem_trig, ScanDirection dir, Datum tupdatum, bool tupnull, BTArrayKeyInfo *array, ScanKey cur, int32 *set_elem_result)
Definition: nbtutils.c:1201
struct BTScanKeyPreproc BTScanKeyPreproc
void _bt_freestack(BTStack stack)
Definition: nbtutils.c:221
void BTreeShmemInit(void)
Definition: nbtutils.c:4533
struct BTSortArrayContext BTSortArrayContext
static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey, Oid elemtype, StrategyNumber strat, Datum *elems, int nelems)
Definition: nbtutils.c:789
bytea * btoptions(Datum reloptions, bool validate)
Definition: nbtutils.c:4561
struct BTVacInfo BTVacInfo
BTCycleId _bt_vacuum_cycleid(Relation rel)
Definition: nbtutils.c:4392
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:129
void _bt_killitems(IndexScanDesc scan)
Definition: nbtutils.c:4175
static bool _bt_advance_array_keys(IndexScanDesc scan, BTReadPageState *pstate, IndexTuple tuple, int tupnatts, TupleDesc tupdesc, int sktrig, bool sktrig_required)
Definition: nbtutils.c:1789
bool _bt_start_prim_scan(IndexScanDesc scan, ScanDirection dir)
Definition: nbtutils.c:1668
static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
Definition: nbtutils.c:3333
bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
Definition: nbtutils.c:4921
IndexTuple _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
Definition: nbtutils.c:4655
#define LOOK_AHEAD_REQUIRED_RECHECKS
Definition: nbtutils.c:32
int _bt_keep_natts_fast(Relation rel, IndexTuple lastleft, IndexTuple firstright)
Definition: nbtutils.c:4874
#define LOOK_AHEAD_DEFAULT_DISTANCE
Definition: nbtutils.c:33
static BTVacInfo * btvacinfo
Definition: nbtutils.c:4379
static void _bt_mark_scankey_required(ScanKey skey)
Definition: nbtutils.c:3442
static int _bt_compare_array_elements(const void *a, const void *b, void *arg)
Definition: nbtutils.c:1099
static void _bt_preprocess_array_keys_final(IndexScanDesc scan, int *keyDataMap)
Definition: nbtutils.c:551
static bool _bt_tuple_before_array_skeys(IndexScanDesc scan, ScanDirection dir, IndexTuple tuple, TupleDesc tupdesc, int tupnatts, bool readpagetup, int sktrig, bool *scanBehind)
Definition: nbtutils.c:1544
static bool _bt_advance_array_keys_increment(IndexScanDesc scan, ScanDirection dir)
Definition: nbtutils.c:1381
Size BTreeShmemSize(void)
Definition: nbtutils.c:4520
static void _bt_setup_array_cmp(IndexScanDesc scan, ScanKey skey, Oid elemtype, FmgrInfo *orderproc, FmgrInfo **sortprocp)
Definition: nbtutils.c:712
static int _bt_keep_natts(Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
Definition: nbtutils.c:4800
static int _bt_sort_array_elements(ScanKey skey, FmgrInfo *sortproc, bool reverse, Datum *elems, int nelems)
Definition: nbtutils.c:849
bool btproperty(Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
Definition: nbtutils.c:4584
static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op, ScanKey leftarg, ScanKey rightarg, BTArrayKeyInfo *array, FmgrInfo *orderproc, bool *result)
Definition: nbtutils.c:3126
bool _bt_allequalimage(Relation rel, bool debugmessage)
Definition: nbtutils.c:5139
static bool _bt_compare_array_scankey_args(IndexScanDesc scan, ScanKey arraysk, ScanKey skey, FmgrInfo *orderproc, BTArrayKeyInfo *array, bool *qual_ok)
Definition: nbtutils.c:976
static void _bt_checkkeys_look_ahead(IndexScanDesc scan, BTReadPageState *pstate, int tupnatts, TupleDesc tupdesc)
Definition: nbtutils.c:4076
static int32 _bt_compare_array_skey(FmgrInfo *orderproc, Datum tupdatum, bool tupnull, Datum arrdatum, ScanKey cur)
Definition: nbtutils.c:1131
struct BTOneVacInfo BTOneVacInfo
void _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir)
Definition: nbtutils.c:1343
void _bt_preprocess_keys(IndexScanDesc scan)
Definition: nbtutils.c:2556
static bool _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts, TupleDesc tupdesc, ScanDirection dir, bool *continuescan)
Definition: nbtutils.c:3892
BTCycleId _bt_start_vacuum(Relation rel)
Definition: nbtutils.c:4426
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
uint16 OffsetNumber
Definition: off.h:24
#define FirstOffsetNumber
Definition: off.h:27
#define OffsetNumberPrev(offsetNumber)
Definition: off.h:54
int16 attnum
Definition: pg_attribute.h:74
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:209
void * arg
#define INDEX_MAX_KEYS
static char * buf
Definition: pg_test_fsync.c:73
int fillfactor
Definition: pgbench.c:187
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
static bool DatumGetBool(Datum X)
Definition: postgres.h:90
uintptr_t Datum
Definition: postgres.h:64
static Datum ObjectIdGetDatum(Oid X)
Definition: postgres.h:252
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
static int32 DatumGetInt32(Datum X)
Definition: postgres.h:202
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
#define PROGRESS_CREATEIDX_SUBPHASE_INITIALIZE
Definition: progress.h:106
static size_t qunique_arg(void *array, size_t elements, size_t width, int(*compare)(const void *, const void *, void *), void *arg)
Definition: qunique.h:46
MemoryContextSwitchTo(old_ctx)
#define RelationGetDescr(relation)
Definition: rel.h:531
#define RelationGetRelationName(relation)
Definition: rel.h:539
#define IndexRelationGetNumberOfAttributes(relation)
Definition: rel.h:517
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:524
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:6005
void * build_reloptions(Datum reloptions, bool validate, relopt_kind kind, Size relopt_struct_size, const relopt_parse_elt *relopt_elems, int num_relopt_elems)
Definition: reloptions.c:1908
@ RELOPT_KIND_BTREE
Definition: reloptions.h:44
@ RELOPT_TYPE_INT
Definition: reloptions.h:32
@ RELOPT_TYPE_BOOL
Definition: reloptions.h:31
@ RELOPT_TYPE_REAL
Definition: reloptions.h:33
void ScanKeyEntryInitializeWithInfo(ScanKey entry, int flags, AttrNumber attributeNumber, StrategyNumber strategy, Oid subtype, Oid collation, FmgrInfo *finfo, Datum argument)
Definition: scankey.c:101
#define ScanDirectionIsForward(direction)
Definition: sdir.h:64
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:50
#define ScanDirectionIsNoMovement(direction)
Definition: sdir.h:57
ScanDirection
Definition: sdir.h:25
@ NoMovementScanDirection
Definition: sdir.h:27
@ ForwardScanDirection
Definition: sdir.h:28
Size add_size(Size s1, Size s2)
Definition: shmem.c:493
void * ShmemInitStruct(const char *name, Size size, bool *foundPtr)
Definition: shmem.c:387
Size mul_size(Size s1, Size s2)
Definition: shmem.c:510
#define SK_ROW_HEADER
Definition: skey.h:117
#define SK_SEARCHARRAY
Definition: skey.h:120
#define SK_ROW_MEMBER
Definition: skey.h:118
#define SK_SEARCHNOTNULL
Definition: skey.h:122
#define SK_SEARCHNULL
Definition: skey.h:121
#define SK_ROW_END
Definition: skey.h:119
ScanKeyData * ScanKey
Definition: skey.h:75
#define SK_ISNULL
Definition: skey.h:115
static pg_noinline void Size size
Definition: slab.c:607
uint16 StrategyNumber
Definition: stratnum.h:22
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define InvalidStrategy
Definition: stratnum.h:24
#define BTMaxStrategyNumber
Definition: stratnum.h:35
#define BTLessStrategyNumber
Definition: stratnum.h:29
#define BTEqualStrategyNumber
Definition: stratnum.h:31
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
#define BTGreaterEqualStrategyNumber
Definition: stratnum.h:32
Datum * elem_values
Definition: nbtree.h:1037
BTCycleId cycleid
Definition: nbtutils.c:4368
LockRelId relid
Definition: nbtutils.c:4367
bool firstmatch
Definition: nbtree.h:1108
BlockNumber prev_scan_page
Definition: nbtree.h:1093
bool continuescan
Definition: nbtree.h:1101
IndexTuple finaltup
Definition: nbtree.h:1092
bool prechecked
Definition: nbtree.h:1107
ScanDirection dir
Definition: nbtree.h:1089
OffsetNumber minoff
Definition: nbtree.h:1090
int16 targetdistance
Definition: nbtree.h:1115
OffsetNumber offnum
Definition: nbtree.h:1097
int16 rechecks
Definition: nbtree.h:1114
OffsetNumber skip
Definition: nbtree.h:1100
OffsetNumber maxoff
Definition: nbtree.h:1091
bool allequalimage
Definition: nbtree.h:787
bool heapkeyspace
Definition: nbtree.h:786
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:793
ScanKey skey
Definition: nbtutils.c:44
bool needPrimScan
Definition: nbtree.h:1049
BTArrayKeyInfo * arrayKeys
Definition: nbtree.h:1051
FmgrInfo * orderProcs
Definition: nbtree.h:1052
BTScanPosData currPos
Definition: nbtree.h:1077
int * killedItems
Definition: nbtree.h:1056
ScanKey keyData
Definition: nbtree.h:1045
MemoryContext arrayContext
Definition: nbtree.h:1053
Buffer buf
Definition: nbtree.h:953
BlockNumber currPage
Definition: nbtree.h:956
int firstItem
Definition: nbtree.h:990
BTScanPosItem items[MaxTIDsPerBTreePage]
Definition: nbtree.h:994
XLogRecPtr lsn
Definition: nbtree.h:955
ItemPointerData heapTid
Definition: nbtree.h:946
OffsetNumber indexOffset
Definition: nbtree.h:947
FmgrInfo * sortproc
Definition: nbtutils.c:37
struct BTStackData * bts_parent
Definition: nbtree.h:736
BTCycleId cycle_ctr
Definition: nbtutils.c:4373
int num_vacuums
Definition: nbtutils.c:4374
BTOneVacInfo vacuums[FLEXIBLE_ARRAY_MEMBER]
Definition: nbtutils.c:4376
int max_vacuums
Definition: nbtutils.c:4375
Definition: fmgr.h:57
Oid fn_oid
Definition: fmgr.h:59
struct ScanKeyData * keyData
Definition: relscan.h:122
struct ParallelIndexScanDescData * parallel_scan
Definition: relscan.h:166
Relation indexRelation
Definition: relscan.h:118
ItemPointerData t_tid
Definition: itup.h:37
unsigned short t_info
Definition: itup.h:49
LockRelId lockRelId
Definition: rel.h:46
Definition: rel.h:39
Oid relId
Definition: rel.h:40
Oid dbId
Definition: rel.h:41
LockInfoData rd_lockInfo
Definition: rel.h:114
Oid * rd_opcintype
Definition: rel.h:208
int16 * rd_indoption
Definition: rel.h:211
Form_pg_index rd_index
Definition: rel.h:192
Oid * rd_opfamily
Definition: rel.h:207
Oid * rd_indcollation
Definition: rel.h:217
int sk_flags
Definition: skey.h:66
Datum sk_argument
Definition: skey.h:72
FmgrInfo sk_func
Definition: skey.h:71
Oid sk_subtype
Definition: skey.h:69
Oid sk_collation
Definition: skey.h:70
StrategyNumber sk_strategy
Definition: skey.h:68
AttrNumber sk_attno
Definition: