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-2022, 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 "catalog/catalog.h"
24 #include "commands/progress.h"
25 #include "lib/qunique.h"
26 #include "miscadmin.h"
27 #include "utils/array.h"
28 #include "utils/datum.h"
29 #include "utils/lsyscache.h"
30 #include "utils/memutils.h"
31 #include "utils/rel.h"
32 
33 
34 typedef struct BTSortArrayContext
35 {
38  bool reverse;
40 
42  StrategyNumber strat,
43  Datum *elems, int nelems);
44 static int _bt_sort_array_elements(IndexScanDesc scan, ScanKey skey,
45  bool reverse,
46  Datum *elems, int nelems);
47 static int _bt_compare_array_elements(const void *a, const void *b, void *arg);
49  ScanKey leftarg, ScanKey rightarg,
50  bool *result);
51 static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption);
52 static void _bt_mark_scankey_required(ScanKey skey);
53 static bool _bt_check_rowcompare(ScanKey skey,
54  IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
55  ScanDirection dir, bool *continuescan);
56 static int _bt_keep_natts(Relation rel, IndexTuple lastleft,
57  IndexTuple firstright, BTScanInsert itup_key);
58 
59 
60 /*
61  * _bt_mkscankey
62  * Build an insertion scan key that contains comparison data from itup
63  * as well as comparator routines appropriate to the key datatypes.
64  *
65  * When itup is a non-pivot tuple, the returned insertion scan key is
66  * suitable for finding a place for it to go on the leaf level. Pivot
67  * tuples can be used to re-find leaf page with matching high key, but
68  * then caller needs to set scan key's pivotsearch field to true. This
69  * allows caller to search for a leaf page with a matching high key,
70  * which is usually to the left of the first leaf page a non-pivot match
71  * might appear on.
72  *
73  * The result is intended for use with _bt_compare() and _bt_truncate().
74  * Callers that don't need to fill out the insertion scankey arguments
75  * (e.g. they use an ad-hoc comparison routine, or only need a scankey
76  * for _bt_truncate()) can pass a NULL index tuple. The scankey will
77  * be initialized as if an "all truncated" pivot tuple was passed
78  * instead.
79  *
80  * Note that we may occasionally have to share lock the metapage to
81  * determine whether or not the keys in the index are expected to be
82  * unique (i.e. if this is a "heapkeyspace" index). We assume a
83  * heapkeyspace index when caller passes a NULL tuple, allowing index
84  * build callers to avoid accessing the non-existent metapage. We
85  * also assume that the index is _not_ allequalimage when a NULL tuple
86  * is passed; CREATE INDEX callers call _bt_allequalimage() to set the
87  * field themselves.
88  */
91 {
93  ScanKey skey;
94  TupleDesc itupdesc;
95  int indnkeyatts;
96  int16 *indoption;
97  int tupnatts;
98  int i;
99 
100  itupdesc = RelationGetDescr(rel);
101  indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
102  indoption = rel->rd_indoption;
103  tupnatts = itup ? BTreeTupleGetNAtts(itup, rel) : 0;
104 
105  Assert(tupnatts <= IndexRelationGetNumberOfAttributes(rel));
106 
107  /*
108  * We'll execute search using scan key constructed on key columns.
109  * Truncated attributes and non-key attributes are omitted from the final
110  * scan key.
111  */
112  key = palloc(offsetof(BTScanInsertData, scankeys) +
113  sizeof(ScanKeyData) * indnkeyatts);
114  if (itup)
115  _bt_metaversion(rel, &key->heapkeyspace, &key->allequalimage);
116  else
117  {
118  /* Utility statement callers can set these fields themselves */
119  key->heapkeyspace = true;
120  key->allequalimage = false;
121  }
122  key->anynullkeys = false; /* initial assumption */
123  key->nextkey = false;
124  key->pivotsearch = false;
125  key->keysz = Min(indnkeyatts, tupnatts);
126  key->scantid = key->heapkeyspace && itup ?
127  BTreeTupleGetHeapTID(itup) : NULL;
128  skey = key->scankeys;
129  for (i = 0; i < indnkeyatts; i++)
130  {
131  FmgrInfo *procinfo;
132  Datum arg;
133  bool null;
134  int flags;
135 
136  /*
137  * We can use the cached (default) support procs since no cross-type
138  * comparison can be needed.
139  */
140  procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
141 
142  /*
143  * Key arguments built from truncated attributes (or when caller
144  * provides no tuple) are defensively represented as NULL values. They
145  * should never be used.
146  */
147  if (i < tupnatts)
148  arg = index_getattr(itup, i + 1, itupdesc, &null);
149  else
150  {
151  arg = (Datum) 0;
152  null = true;
153  }
154  flags = (null ? SK_ISNULL : 0) | (indoption[i] << SK_BT_INDOPTION_SHIFT);
156  flags,
157  (AttrNumber) (i + 1),
159  InvalidOid,
160  rel->rd_indcollation[i],
161  procinfo,
162  arg);
163  /* Record if any key attribute is NULL (or truncated) */
164  if (null)
165  key->anynullkeys = true;
166  }
167 
168  /*
169  * In NULLS NOT DISTINCT mode, we pretend that there are no null keys, so
170  * that full uniqueness check is done.
171  */
172  if (rel->rd_index->indnullsnotdistinct)
173  key->anynullkeys = false;
174 
175  return key;
176 }
177 
178 /*
179  * free a retracement stack made by _bt_search.
180  */
181 void
183 {
184  BTStack ostack;
185 
186  while (stack != NULL)
187  {
188  ostack = stack;
189  stack = stack->bts_parent;
190  pfree(ostack);
191  }
192 }
193 
194 
195 /*
196  * _bt_preprocess_array_keys() -- Preprocess SK_SEARCHARRAY scan keys
197  *
198  * If there are any SK_SEARCHARRAY scan keys, deconstruct the array(s) and
199  * set up BTArrayKeyInfo info for each one that is an equality-type key.
200  * Prepare modified scan keys in so->arrayKeyData, which will hold the current
201  * array elements during each primitive indexscan operation. For inequality
202  * array keys, it's sufficient to find the extreme element value and replace
203  * the whole array with that scalar value.
204  *
205  * Note: the reason we need so->arrayKeyData, rather than just scribbling
206  * on scan->keyData, is that callers are permitted to call btrescan without
207  * supplying a new set of scankey data.
208  */
209 void
211 {
212  BTScanOpaque so = (BTScanOpaque) scan->opaque;
213  int numberOfKeys = scan->numberOfKeys;
214  int16 *indoption = scan->indexRelation->rd_indoption;
215  int numArrayKeys;
216  ScanKey cur;
217  int i;
218  MemoryContext oldContext;
219 
220  /* Quick check to see if there are any array keys */
221  numArrayKeys = 0;
222  for (i = 0; i < numberOfKeys; i++)
223  {
224  cur = &scan->keyData[i];
225  if (cur->sk_flags & SK_SEARCHARRAY)
226  {
227  numArrayKeys++;
228  Assert(!(cur->sk_flags & (SK_ROW_HEADER | SK_SEARCHNULL | SK_SEARCHNOTNULL)));
229  /* If any arrays are null as a whole, we can quit right now. */
230  if (cur->sk_flags & SK_ISNULL)
231  {
232  so->numArrayKeys = -1;
233  so->arrayKeyData = NULL;
234  return;
235  }
236  }
237  }
238 
239  /* Quit if nothing to do. */
240  if (numArrayKeys == 0)
241  {
242  so->numArrayKeys = 0;
243  so->arrayKeyData = NULL;
244  return;
245  }
246 
247  /*
248  * Make a scan-lifespan context to hold array-associated data, or reset it
249  * if we already have one from a previous rescan cycle.
250  */
251  if (so->arrayContext == NULL)
253  "BTree array context",
255  else
257 
258  oldContext = MemoryContextSwitchTo(so->arrayContext);
259 
260  /* Create modifiable copy of scan->keyData in the workspace context */
261  so->arrayKeyData = (ScanKey) palloc(scan->numberOfKeys * sizeof(ScanKeyData));
262  memcpy(so->arrayKeyData,
263  scan->keyData,
264  scan->numberOfKeys * sizeof(ScanKeyData));
265 
266  /* Allocate space for per-array data in the workspace context */
267  so->arrayKeys = (BTArrayKeyInfo *) palloc0(numArrayKeys * sizeof(BTArrayKeyInfo));
268 
269  /* Now process each array key */
270  numArrayKeys = 0;
271  for (i = 0; i < numberOfKeys; i++)
272  {
273  ArrayType *arrayval;
274  int16 elmlen;
275  bool elmbyval;
276  char elmalign;
277  int num_elems;
278  Datum *elem_values;
279  bool *elem_nulls;
280  int num_nonnulls;
281  int j;
282 
283  cur = &so->arrayKeyData[i];
284  if (!(cur->sk_flags & SK_SEARCHARRAY))
285  continue;
286 
287  /*
288  * First, deconstruct the array into elements. Anything allocated
289  * here (including a possibly detoasted array value) is in the
290  * workspace context.
291  */
292  arrayval = DatumGetArrayTypeP(cur->sk_argument);
293  /* We could cache this data, but not clear it's worth it */
295  &elmlen, &elmbyval, &elmalign);
296  deconstruct_array(arrayval,
297  ARR_ELEMTYPE(arrayval),
298  elmlen, elmbyval, elmalign,
299  &elem_values, &elem_nulls, &num_elems);
300 
301  /*
302  * Compress out any null elements. We can ignore them since we assume
303  * all btree operators are strict.
304  */
305  num_nonnulls = 0;
306  for (j = 0; j < num_elems; j++)
307  {
308  if (!elem_nulls[j])
309  elem_values[num_nonnulls++] = elem_values[j];
310  }
311 
312  /* We could pfree(elem_nulls) now, but not worth the cycles */
313 
314  /* If there's no non-nulls, the scan qual is unsatisfiable */
315  if (num_nonnulls == 0)
316  {
317  numArrayKeys = -1;
318  break;
319  }
320 
321  /*
322  * If the comparison operator is not equality, then the array qual
323  * degenerates to a simple comparison against the smallest or largest
324  * non-null array element, as appropriate.
325  */
326  switch (cur->sk_strategy)
327  {
330  cur->sk_argument =
333  elem_values, num_nonnulls);
334  continue;
336  /* proceed with rest of loop */
337  break;
340  cur->sk_argument =
343  elem_values, num_nonnulls);
344  continue;
345  default:
346  elog(ERROR, "unrecognized StrategyNumber: %d",
347  (int) cur->sk_strategy);
348  break;
349  }
350 
351  /*
352  * Sort the non-null elements and eliminate any duplicates. We must
353  * sort in the same ordering used by the index column, so that the
354  * successive primitive indexscans produce data in index order.
355  */
356  num_elems = _bt_sort_array_elements(scan, cur,
357  (indoption[cur->sk_attno - 1] & INDOPTION_DESC) != 0,
358  elem_values, num_nonnulls);
359 
360  /*
361  * And set up the BTArrayKeyInfo data.
362  */
363  so->arrayKeys[numArrayKeys].scan_key = i;
364  so->arrayKeys[numArrayKeys].num_elems = num_elems;
365  so->arrayKeys[numArrayKeys].elem_values = elem_values;
366  numArrayKeys++;
367  }
368 
369  so->numArrayKeys = numArrayKeys;
370 
371  MemoryContextSwitchTo(oldContext);
372 }
373 
374 /*
375  * _bt_find_extreme_element() -- get least or greatest array element
376  *
377  * scan and skey identify the index column, whose opfamily determines the
378  * comparison semantics. strat should be BTLessStrategyNumber to get the
379  * least element, or BTGreaterStrategyNumber to get the greatest.
380  */
381 static Datum
383  StrategyNumber strat,
384  Datum *elems, int nelems)
385 {
386  Relation rel = scan->indexRelation;
387  Oid elemtype,
388  cmp_op;
389  RegProcedure cmp_proc;
390  FmgrInfo flinfo;
391  Datum result;
392  int i;
393 
394  /*
395  * Determine the nominal datatype of the array elements. We have to
396  * support the convention that sk_subtype == InvalidOid means the opclass
397  * input type; this is a hack to simplify life for ScanKeyInit().
398  */
399  elemtype = skey->sk_subtype;
400  if (elemtype == InvalidOid)
401  elemtype = rel->rd_opcintype[skey->sk_attno - 1];
402 
403  /*
404  * Look up the appropriate comparison operator in the opfamily.
405  *
406  * Note: it's possible that this would fail, if the opfamily is
407  * incomplete, but it seems quite unlikely that an opfamily would omit
408  * non-cross-type comparison operators for any datatype that it supports
409  * at all.
410  */
411  cmp_op = get_opfamily_member(rel->rd_opfamily[skey->sk_attno - 1],
412  elemtype,
413  elemtype,
414  strat);
415  if (!OidIsValid(cmp_op))
416  elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
417  strat, elemtype, elemtype,
418  rel->rd_opfamily[skey->sk_attno - 1]);
419  cmp_proc = get_opcode(cmp_op);
420  if (!RegProcedureIsValid(cmp_proc))
421  elog(ERROR, "missing oprcode for operator %u", cmp_op);
422 
423  fmgr_info(cmp_proc, &flinfo);
424 
425  Assert(nelems > 0);
426  result = elems[0];
427  for (i = 1; i < nelems; i++)
428  {
429  if (DatumGetBool(FunctionCall2Coll(&flinfo,
430  skey->sk_collation,
431  elems[i],
432  result)))
433  result = elems[i];
434  }
435 
436  return result;
437 }
438 
439 /*
440  * _bt_sort_array_elements() -- sort and de-dup array elements
441  *
442  * The array elements are sorted in-place, and the new number of elements
443  * after duplicate removal is returned.
444  *
445  * scan and skey identify the index column, whose opfamily determines the
446  * comparison semantics. If reverse is true, we sort in descending order.
447  */
448 static int
450  bool reverse,
451  Datum *elems, int nelems)
452 {
453  Relation rel = scan->indexRelation;
454  Oid elemtype;
455  RegProcedure cmp_proc;
456  BTSortArrayContext cxt;
457 
458  if (nelems <= 1)
459  return nelems; /* no work to do */
460 
461  /*
462  * Determine the nominal datatype of the array elements. We have to
463  * support the convention that sk_subtype == InvalidOid means the opclass
464  * input type; this is a hack to simplify life for ScanKeyInit().
465  */
466  elemtype = skey->sk_subtype;
467  if (elemtype == InvalidOid)
468  elemtype = rel->rd_opcintype[skey->sk_attno - 1];
469 
470  /*
471  * Look up the appropriate comparison function in the opfamily.
472  *
473  * Note: it's possible that this would fail, if the opfamily is
474  * incomplete, but it seems quite unlikely that an opfamily would omit
475  * non-cross-type support functions for any datatype that it supports at
476  * all.
477  */
478  cmp_proc = get_opfamily_proc(rel->rd_opfamily[skey->sk_attno - 1],
479  elemtype,
480  elemtype,
481  BTORDER_PROC);
482  if (!RegProcedureIsValid(cmp_proc))
483  elog(ERROR, "missing support function %d(%u,%u) in opfamily %u",
484  BTORDER_PROC, elemtype, elemtype,
485  rel->rd_opfamily[skey->sk_attno - 1]);
486 
487  /* Sort the array elements */
488  fmgr_info(cmp_proc, &cxt.flinfo);
489  cxt.collation = skey->sk_collation;
490  cxt.reverse = reverse;
491  qsort_arg((void *) elems, nelems, sizeof(Datum),
492  _bt_compare_array_elements, (void *) &cxt);
493 
494  /* Now scan the sorted elements and remove duplicates */
495  return qunique_arg(elems, nelems, sizeof(Datum),
497 }
498 
499 /*
500  * qsort_arg comparator for sorting array elements
501  */
502 static int
503 _bt_compare_array_elements(const void *a, const void *b, void *arg)
504 {
505  Datum da = *((const Datum *) a);
506  Datum db = *((const Datum *) b);
508  int32 compare;
509 
511  cxt->collation,
512  da, db));
513  if (cxt->reverse)
515  return compare;
516 }
517 
518 /*
519  * _bt_start_array_keys() -- Initialize array keys at start of a scan
520  *
521  * Set up the cur_elem counters and fill in the first sk_argument value for
522  * each array scankey. We can't do this until we know the scan direction.
523  */
524 void
526 {
527  BTScanOpaque so = (BTScanOpaque) scan->opaque;
528  int i;
529 
530  for (i = 0; i < so->numArrayKeys; i++)
531  {
532  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
533  ScanKey skey = &so->arrayKeyData[curArrayKey->scan_key];
534 
535  Assert(curArrayKey->num_elems > 0);
536  if (ScanDirectionIsBackward(dir))
537  curArrayKey->cur_elem = curArrayKey->num_elems - 1;
538  else
539  curArrayKey->cur_elem = 0;
540  skey->sk_argument = curArrayKey->elem_values[curArrayKey->cur_elem];
541  }
542 }
543 
544 /*
545  * _bt_advance_array_keys() -- Advance to next set of array elements
546  *
547  * Returns true if there is another set of values to consider, false if not.
548  * On true result, the scankeys are initialized with the next set of values.
549  */
550 bool
552 {
553  BTScanOpaque so = (BTScanOpaque) scan->opaque;
554  bool found = false;
555  int i;
556 
557  /*
558  * We must advance the last array key most quickly, since it will
559  * correspond to the lowest-order index column among the available
560  * qualifications. This is necessary to ensure correct ordering of output
561  * when there are multiple array keys.
562  */
563  for (i = so->numArrayKeys - 1; i >= 0; i--)
564  {
565  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
566  ScanKey skey = &so->arrayKeyData[curArrayKey->scan_key];
567  int cur_elem = curArrayKey->cur_elem;
568  int num_elems = curArrayKey->num_elems;
569 
570  if (ScanDirectionIsBackward(dir))
571  {
572  if (--cur_elem < 0)
573  {
574  cur_elem = num_elems - 1;
575  found = false; /* need to advance next array key */
576  }
577  else
578  found = true;
579  }
580  else
581  {
582  if (++cur_elem >= num_elems)
583  {
584  cur_elem = 0;
585  found = false; /* need to advance next array key */
586  }
587  else
588  found = true;
589  }
590 
591  curArrayKey->cur_elem = cur_elem;
592  skey->sk_argument = curArrayKey->elem_values[cur_elem];
593  if (found)
594  break;
595  }
596 
597  /* advance parallel scan */
598  if (scan->parallel_scan != NULL)
600 
601  return found;
602 }
603 
604 /*
605  * _bt_mark_array_keys() -- Handle array keys during btmarkpos
606  *
607  * Save the current state of the array keys as the "mark" position.
608  */
609 void
611 {
612  BTScanOpaque so = (BTScanOpaque) scan->opaque;
613  int i;
614 
615  for (i = 0; i < so->numArrayKeys; i++)
616  {
617  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
618 
619  curArrayKey->mark_elem = curArrayKey->cur_elem;
620  }
621 }
622 
623 /*
624  * _bt_restore_array_keys() -- Handle array keys during btrestrpos
625  *
626  * Restore the array keys to where they were when the mark was set.
627  */
628 void
630 {
631  BTScanOpaque so = (BTScanOpaque) scan->opaque;
632  bool changed = false;
633  int i;
634 
635  /* Restore each array key to its position when the mark was set */
636  for (i = 0; i < so->numArrayKeys; i++)
637  {
638  BTArrayKeyInfo *curArrayKey = &so->arrayKeys[i];
639  ScanKey skey = &so->arrayKeyData[curArrayKey->scan_key];
640  int mark_elem = curArrayKey->mark_elem;
641 
642  if (curArrayKey->cur_elem != mark_elem)
643  {
644  curArrayKey->cur_elem = mark_elem;
645  skey->sk_argument = curArrayKey->elem_values[mark_elem];
646  changed = true;
647  }
648  }
649 
650  /*
651  * If we changed any keys, we must redo _bt_preprocess_keys. That might
652  * sound like overkill, but in cases with multiple keys per index column
653  * it seems necessary to do the full set of pushups.
654  */
655  if (changed)
656  {
657  _bt_preprocess_keys(scan);
658  /* The mark should have been set on a consistent set of keys... */
659  Assert(so->qual_ok);
660  }
661 }
662 
663 
664 /*
665  * _bt_preprocess_keys() -- Preprocess scan keys
666  *
667  * The given search-type keys (in scan->keyData[] or so->arrayKeyData[])
668  * are copied to so->keyData[] with possible transformation.
669  * scan->numberOfKeys is the number of input keys, so->numberOfKeys gets
670  * the number of output keys (possibly less, never greater).
671  *
672  * The output keys are marked with additional sk_flags bits beyond the
673  * system-standard bits supplied by the caller. The DESC and NULLS_FIRST
674  * indoption bits for the relevant index attribute are copied into the flags.
675  * Also, for a DESC column, we commute (flip) all the sk_strategy numbers
676  * so that the index sorts in the desired direction.
677  *
678  * One key purpose of this routine is to discover which scan keys must be
679  * satisfied to continue the scan. It also attempts to eliminate redundant
680  * keys and detect contradictory keys. (If the index opfamily provides
681  * incomplete sets of cross-type operators, we may fail to detect redundant
682  * or contradictory keys, but we can survive that.)
683  *
684  * The output keys must be sorted by index attribute. Presently we expect
685  * (but verify) that the input keys are already so sorted --- this is done
686  * by match_clauses_to_index() in indxpath.c. Some reordering of the keys
687  * within each attribute may be done as a byproduct of the processing here,
688  * but no other code depends on that.
689  *
690  * The output keys are marked with flags SK_BT_REQFWD and/or SK_BT_REQBKWD
691  * if they must be satisfied in order to continue the scan forward or backward
692  * respectively. _bt_checkkeys uses these flags. For example, if the quals
693  * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple
694  * (1,2,7), but we must continue the scan in case there are tuples (1,3,z).
695  * But once we reach tuples like (1,4,z) we can stop scanning because no
696  * later tuples could match. This is reflected by marking the x and y keys,
697  * but not the z key, with SK_BT_REQFWD. In general, the keys for leading
698  * attributes with "=" keys are marked both SK_BT_REQFWD and SK_BT_REQBKWD.
699  * For the first attribute without an "=" key, any "<" and "<=" keys are
700  * marked SK_BT_REQFWD while any ">" and ">=" keys are marked SK_BT_REQBKWD.
701  * This can be seen to be correct by considering the above example. Note
702  * in particular that if there are no keys for a given attribute, the keys for
703  * subsequent attributes can never be required; for instance "WHERE y = 4"
704  * requires a full-index scan.
705  *
706  * If possible, redundant keys are eliminated: we keep only the tightest
707  * >/>= bound and the tightest </<= bound, and if there's an = key then
708  * that's the only one returned. (So, we return either a single = key,
709  * or one or two boundary-condition keys for each attr.) However, if we
710  * cannot compare two keys for lack of a suitable cross-type operator,
711  * we cannot eliminate either. If there are two such keys of the same
712  * operator strategy, the second one is just pushed into the output array
713  * without further processing here. We may also emit both >/>= or both
714  * </<= keys if we can't compare them. The logic about required keys still
715  * works if we don't eliminate redundant keys.
716  *
717  * Note that one reason we need direction-sensitive required-key flags is
718  * precisely that we may not be able to eliminate redundant keys. Suppose
719  * we have "x > 4::int AND x > 10::bigint", and we are unable to determine
720  * which key is more restrictive for lack of a suitable cross-type operator.
721  * _bt_first will arbitrarily pick one of the keys to do the initial
722  * positioning with. If it picks x > 4, then the x > 10 condition will fail
723  * until we reach index entries > 10; but we can't stop the scan just because
724  * x > 10 is failing. On the other hand, if we are scanning backwards, then
725  * failure of either key is indeed enough to stop the scan. (In general, when
726  * inequality keys are present, the initial-positioning code only promises to
727  * position before the first possible match, not exactly at the first match,
728  * for a forward scan; or after the last match for a backward scan.)
729  *
730  * As a byproduct of this work, we can detect contradictory quals such
731  * as "x = 1 AND x > 2". If we see that, we return so->qual_ok = false,
732  * indicating the scan need not be run at all since no tuples can match.
733  * (In this case we do not bother completing the output key array!)
734  * Again, missing cross-type operators might cause us to fail to prove the
735  * quals contradictory when they really are, but the scan will work correctly.
736  *
737  * Row comparison keys are currently also treated without any smarts:
738  * we just transfer them into the preprocessed array without any
739  * editorialization. We can treat them the same as an ordinary inequality
740  * comparison on the row's first index column, for the purposes of the logic
741  * about required keys.
742  *
743  * Note: the reason we have to copy the preprocessed scan keys into private
744  * storage is that we are modifying the array based on comparisons of the
745  * key argument values, which could change on a rescan or after moving to
746  * new elements of array keys. Therefore we can't overwrite the source data.
747  */
748 void
750 {
751  BTScanOpaque so = (BTScanOpaque) scan->opaque;
752  int numberOfKeys = scan->numberOfKeys;
753  int16 *indoption = scan->indexRelation->rd_indoption;
754  int new_numberOfKeys;
755  int numberOfEqualCols;
756  ScanKey inkeys;
757  ScanKey outkeys;
758  ScanKey cur;
760  bool test_result;
761  int i,
762  j;
763  AttrNumber attno;
764 
765  /* initialize result variables */
766  so->qual_ok = true;
767  so->numberOfKeys = 0;
768 
769  if (numberOfKeys < 1)
770  return; /* done if qual-less scan */
771 
772  /*
773  * Read so->arrayKeyData if array keys are present, else scan->keyData
774  */
775  if (so->arrayKeyData != NULL)
776  inkeys = so->arrayKeyData;
777  else
778  inkeys = scan->keyData;
779 
780  outkeys = so->keyData;
781  cur = &inkeys[0];
782  /* we check that input keys are correctly ordered */
783  if (cur->sk_attno < 1)
784  elog(ERROR, "btree index keys must be ordered by attribute");
785 
786  /* We can short-circuit most of the work if there's just one key */
787  if (numberOfKeys == 1)
788  {
789  /* Apply indoption to scankey (might change sk_strategy!) */
790  if (!_bt_fix_scankey_strategy(cur, indoption))
791  so->qual_ok = false;
792  memcpy(outkeys, cur, sizeof(ScanKeyData));
793  so->numberOfKeys = 1;
794  /* We can mark the qual as required if it's for first index col */
795  if (cur->sk_attno == 1)
796  _bt_mark_scankey_required(outkeys);
797  return;
798  }
799 
800  /*
801  * Otherwise, do the full set of pushups.
802  */
803  new_numberOfKeys = 0;
804  numberOfEqualCols = 0;
805 
806  /*
807  * Initialize for processing of keys for attr 1.
808  *
809  * xform[i] points to the currently best scan key of strategy type i+1; it
810  * is NULL if we haven't yet found such a key for this attr.
811  */
812  attno = 1;
813  memset(xform, 0, sizeof(xform));
814 
815  /*
816  * Loop iterates from 0 to numberOfKeys inclusive; we use the last pass to
817  * handle after-last-key processing. Actual exit from the loop is at the
818  * "break" statement below.
819  */
820  for (i = 0;; cur++, i++)
821  {
822  if (i < numberOfKeys)
823  {
824  /* Apply indoption to scankey (might change sk_strategy!) */
825  if (!_bt_fix_scankey_strategy(cur, indoption))
826  {
827  /* NULL can't be matched, so give up */
828  so->qual_ok = false;
829  return;
830  }
831  }
832 
833  /*
834  * If we are at the end of the keys for a particular attr, finish up
835  * processing and emit the cleaned-up keys.
836  */
837  if (i == numberOfKeys || cur->sk_attno != attno)
838  {
839  int priorNumberOfEqualCols = numberOfEqualCols;
840 
841  /* check input keys are correctly ordered */
842  if (i < numberOfKeys && cur->sk_attno < attno)
843  elog(ERROR, "btree index keys must be ordered by attribute");
844 
845  /*
846  * If = has been specified, all other keys can be eliminated as
847  * redundant. If we have a case like key = 1 AND key > 2, we can
848  * set qual_ok to false and abandon further processing.
849  *
850  * We also have to deal with the case of "key IS NULL", which is
851  * unsatisfiable in combination with any other index condition. By
852  * the time we get here, that's been classified as an equality
853  * check, and we've rejected any combination of it with a regular
854  * equality condition; but not with other types of conditions.
855  */
856  if (xform[BTEqualStrategyNumber - 1])
857  {
858  ScanKey eq = xform[BTEqualStrategyNumber - 1];
859 
860  for (j = BTMaxStrategyNumber; --j >= 0;)
861  {
862  ScanKey chk = xform[j];
863 
864  if (!chk || j == (BTEqualStrategyNumber - 1))
865  continue;
866 
867  if (eq->sk_flags & SK_SEARCHNULL)
868  {
869  /* IS NULL is contradictory to anything else */
870  so->qual_ok = false;
871  return;
872  }
873 
874  if (_bt_compare_scankey_args(scan, chk, eq, chk,
875  &test_result))
876  {
877  if (!test_result)
878  {
879  /* keys proven mutually contradictory */
880  so->qual_ok = false;
881  return;
882  }
883  /* else discard the redundant non-equality key */
884  xform[j] = NULL;
885  }
886  /* else, cannot determine redundancy, keep both keys */
887  }
888  /* track number of attrs for which we have "=" keys */
889  numberOfEqualCols++;
890  }
891 
892  /* try to keep only one of <, <= */
893  if (xform[BTLessStrategyNumber - 1]
894  && xform[BTLessEqualStrategyNumber - 1])
895  {
896  ScanKey lt = xform[BTLessStrategyNumber - 1];
897  ScanKey le = xform[BTLessEqualStrategyNumber - 1];
898 
899  if (_bt_compare_scankey_args(scan, le, lt, le,
900  &test_result))
901  {
902  if (test_result)
903  xform[BTLessEqualStrategyNumber - 1] = NULL;
904  else
905  xform[BTLessStrategyNumber - 1] = NULL;
906  }
907  }
908 
909  /* try to keep only one of >, >= */
910  if (xform[BTGreaterStrategyNumber - 1]
911  && xform[BTGreaterEqualStrategyNumber - 1])
912  {
913  ScanKey gt = xform[BTGreaterStrategyNumber - 1];
914  ScanKey ge = xform[BTGreaterEqualStrategyNumber - 1];
915 
916  if (_bt_compare_scankey_args(scan, ge, gt, ge,
917  &test_result))
918  {
919  if (test_result)
920  xform[BTGreaterEqualStrategyNumber - 1] = NULL;
921  else
922  xform[BTGreaterStrategyNumber - 1] = NULL;
923  }
924  }
925 
926  /*
927  * Emit the cleaned-up keys into the outkeys[] array, and then
928  * mark them if they are required. They are required (possibly
929  * only in one direction) if all attrs before this one had "=".
930  */
931  for (j = BTMaxStrategyNumber; --j >= 0;)
932  {
933  if (xform[j])
934  {
935  ScanKey outkey = &outkeys[new_numberOfKeys++];
936 
937  memcpy(outkey, xform[j], sizeof(ScanKeyData));
938  if (priorNumberOfEqualCols == attno - 1)
940  }
941  }
942 
943  /*
944  * Exit loop here if done.
945  */
946  if (i == numberOfKeys)
947  break;
948 
949  /* Re-initialize for new attno */
950  attno = cur->sk_attno;
951  memset(xform, 0, sizeof(xform));
952  }
953 
954  /* check strategy this key's operator corresponds to */
955  j = cur->sk_strategy - 1;
956 
957  /* if row comparison, push it directly to the output array */
958  if (cur->sk_flags & SK_ROW_HEADER)
959  {
960  ScanKey outkey = &outkeys[new_numberOfKeys++];
961 
962  memcpy(outkey, cur, sizeof(ScanKeyData));
963  if (numberOfEqualCols == attno - 1)
965 
966  /*
967  * We don't support RowCompare using equality; such a qual would
968  * mess up the numberOfEqualCols tracking.
969  */
970  Assert(j != (BTEqualStrategyNumber - 1));
971  continue;
972  }
973 
974  /* have we seen one of these before? */
975  if (xform[j] == NULL)
976  {
977  /* nope, so remember this scankey */
978  xform[j] = cur;
979  }
980  else
981  {
982  /* yup, keep only the more restrictive key */
983  if (_bt_compare_scankey_args(scan, cur, cur, xform[j],
984  &test_result))
985  {
986  if (test_result)
987  xform[j] = cur;
988  else if (j == (BTEqualStrategyNumber - 1))
989  {
990  /* key == a && key == b, but a != b */
991  so->qual_ok = false;
992  return;
993  }
994  /* else old key is more restrictive, keep it */
995  }
996  else
997  {
998  /*
999  * We can't determine which key is more restrictive. Keep the
1000  * previous one in xform[j] and push this one directly to the
1001  * output array.
1002  */
1003  ScanKey outkey = &outkeys[new_numberOfKeys++];
1004 
1005  memcpy(outkey, cur, sizeof(ScanKeyData));
1006  if (numberOfEqualCols == attno - 1)
1007  _bt_mark_scankey_required(outkey);
1008  }
1009  }
1010  }
1011 
1012  so->numberOfKeys = new_numberOfKeys;
1013 }
1014 
1015 /*
1016  * Compare two scankey values using a specified operator.
1017  *
1018  * The test we want to perform is logically "leftarg op rightarg", where
1019  * leftarg and rightarg are the sk_argument values in those ScanKeys, and
1020  * the comparison operator is the one in the op ScanKey. However, in
1021  * cross-data-type situations we may need to look up the correct operator in
1022  * the index's opfamily: it is the one having amopstrategy = op->sk_strategy
1023  * and amoplefttype/amoprighttype equal to the two argument datatypes.
1024  *
1025  * If the opfamily doesn't supply a complete set of cross-type operators we
1026  * may not be able to make the comparison. If we can make the comparison
1027  * we store the operator result in *result and return true. We return false
1028  * if the comparison could not be made.
1029  *
1030  * Note: op always points at the same ScanKey as either leftarg or rightarg.
1031  * Since we don't scribble on the scankeys, this aliasing should cause no
1032  * trouble.
1033  *
1034  * Note: this routine needs to be insensitive to any DESC option applied
1035  * to the index column. For example, "x < 4" is a tighter constraint than
1036  * "x < 5" regardless of which way the index is sorted.
1037  */
1038 static bool
1040  ScanKey leftarg, ScanKey rightarg,
1041  bool *result)
1042 {
1043  Relation rel = scan->indexRelation;
1044  Oid lefttype,
1045  righttype,
1046  optype,
1047  opcintype,
1048  cmp_op;
1049  StrategyNumber strat;
1050 
1051  /*
1052  * First, deal with cases where one or both args are NULL. This should
1053  * only happen when the scankeys represent IS NULL/NOT NULL conditions.
1054  */
1055  if ((leftarg->sk_flags | rightarg->sk_flags) & SK_ISNULL)
1056  {
1057  bool leftnull,
1058  rightnull;
1059 
1060  if (leftarg->sk_flags & SK_ISNULL)
1061  {
1063  leftnull = true;
1064  }
1065  else
1066  leftnull = false;
1067  if (rightarg->sk_flags & SK_ISNULL)
1068  {
1069  Assert(rightarg->sk_flags & (SK_SEARCHNULL | SK_SEARCHNOTNULL));
1070  rightnull = true;
1071  }
1072  else
1073  rightnull = false;
1074 
1075  /*
1076  * We treat NULL as either greater than or less than all other values.
1077  * Since true > false, the tests below work correctly for NULLS LAST
1078  * logic. If the index is NULLS FIRST, we need to flip the strategy.
1079  */
1080  strat = op->sk_strategy;
1081  if (op->sk_flags & SK_BT_NULLS_FIRST)
1082  strat = BTCommuteStrategyNumber(strat);
1083 
1084  switch (strat)
1085  {
1086  case BTLessStrategyNumber:
1087  *result = (leftnull < rightnull);
1088  break;
1090  *result = (leftnull <= rightnull);
1091  break;
1092  case BTEqualStrategyNumber:
1093  *result = (leftnull == rightnull);
1094  break;
1096  *result = (leftnull >= rightnull);
1097  break;
1099  *result = (leftnull > rightnull);
1100  break;
1101  default:
1102  elog(ERROR, "unrecognized StrategyNumber: %d", (int) strat);
1103  *result = false; /* keep compiler quiet */
1104  break;
1105  }
1106  return true;
1107  }
1108 
1109  /*
1110  * The opfamily we need to worry about is identified by the index column.
1111  */
1112  Assert(leftarg->sk_attno == rightarg->sk_attno);
1113 
1114  opcintype = rel->rd_opcintype[leftarg->sk_attno - 1];
1115 
1116  /*
1117  * Determine the actual datatypes of the ScanKey arguments. We have to
1118  * support the convention that sk_subtype == InvalidOid means the opclass
1119  * input type; this is a hack to simplify life for ScanKeyInit().
1120  */
1121  lefttype = leftarg->sk_subtype;
1122  if (lefttype == InvalidOid)
1123  lefttype = opcintype;
1124  righttype = rightarg->sk_subtype;
1125  if (righttype == InvalidOid)
1126  righttype = opcintype;
1127  optype = op->sk_subtype;
1128  if (optype == InvalidOid)
1129  optype = opcintype;
1130 
1131  /*
1132  * If leftarg and rightarg match the types expected for the "op" scankey,
1133  * we can use its already-looked-up comparison function.
1134  */
1135  if (lefttype == opcintype && righttype == optype)
1136  {
1137  *result = DatumGetBool(FunctionCall2Coll(&op->sk_func,
1138  op->sk_collation,
1139  leftarg->sk_argument,
1140  rightarg->sk_argument));
1141  return true;
1142  }
1143 
1144  /*
1145  * Otherwise, we need to go to the syscache to find the appropriate
1146  * operator. (This cannot result in infinite recursion, since no
1147  * indexscan initiated by syscache lookup will use cross-data-type
1148  * operators.)
1149  *
1150  * If the sk_strategy was flipped by _bt_fix_scankey_strategy, we have to
1151  * un-flip it to get the correct opfamily member.
1152  */
1153  strat = op->sk_strategy;
1154  if (op->sk_flags & SK_BT_DESC)
1155  strat = BTCommuteStrategyNumber(strat);
1156 
1157  cmp_op = get_opfamily_member(rel->rd_opfamily[leftarg->sk_attno - 1],
1158  lefttype,
1159  righttype,
1160  strat);
1161  if (OidIsValid(cmp_op))
1162  {
1163  RegProcedure cmp_proc = get_opcode(cmp_op);
1164 
1165  if (RegProcedureIsValid(cmp_proc))
1166  {
1167  *result = DatumGetBool(OidFunctionCall2Coll(cmp_proc,
1168  op->sk_collation,
1169  leftarg->sk_argument,
1170  rightarg->sk_argument));
1171  return true;
1172  }
1173  }
1174 
1175  /* Can't make the comparison */
1176  *result = false; /* suppress compiler warnings */
1177  return false;
1178 }
1179 
1180 /*
1181  * Adjust a scankey's strategy and flags setting as needed for indoptions.
1182  *
1183  * We copy the appropriate indoption value into the scankey sk_flags
1184  * (shifting to avoid clobbering system-defined flag bits). Also, if
1185  * the DESC option is set, commute (flip) the operator strategy number.
1186  *
1187  * A secondary purpose is to check for IS NULL/NOT NULL scankeys and set up
1188  * the strategy field correctly for them.
1189  *
1190  * Lastly, for ordinary scankeys (not IS NULL/NOT NULL), we check for a
1191  * NULL comparison value. Since all btree operators are assumed strict,
1192  * a NULL means that the qual cannot be satisfied. We return true if the
1193  * comparison value isn't NULL, or false if the scan should be abandoned.
1194  *
1195  * This function is applied to the *input* scankey structure; therefore
1196  * on a rescan we will be looking at already-processed scankeys. Hence
1197  * we have to be careful not to re-commute the strategy if we already did it.
1198  * It's a bit ugly to modify the caller's copy of the scankey but in practice
1199  * there shouldn't be any problem, since the index's indoptions are certainly
1200  * not going to change while the scankey survives.
1201  */
1202 static bool
1204 {
1205  int addflags;
1206 
1207  addflags = indoption[skey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
1208 
1209  /*
1210  * We treat all btree operators as strict (even if they're not so marked
1211  * in pg_proc). This means that it is impossible for an operator condition
1212  * with a NULL comparison constant to succeed, and we can reject it right
1213  * away.
1214  *
1215  * However, we now also support "x IS NULL" clauses as search conditions,
1216  * so in that case keep going. The planner has not filled in any
1217  * particular strategy in this case, so set it to BTEqualStrategyNumber
1218  * --- we can treat IS NULL as an equality operator for purposes of search
1219  * strategy.
1220  *
1221  * Likewise, "x IS NOT NULL" is supported. We treat that as either "less
1222  * than NULL" in a NULLS LAST index, or "greater than NULL" in a NULLS
1223  * FIRST index.
1224  *
1225  * Note: someday we might have to fill in sk_collation from the index
1226  * column's collation. At the moment this is a non-issue because we'll
1227  * never actually call the comparison operator on a NULL.
1228  */
1229  if (skey->sk_flags & SK_ISNULL)
1230  {
1231  /* SK_ISNULL shouldn't be set in a row header scankey */
1232  Assert(!(skey->sk_flags & SK_ROW_HEADER));
1233 
1234  /* Set indoption flags in scankey (might be done already) */
1235  skey->sk_flags |= addflags;
1236 
1237  /* Set correct strategy for IS NULL or NOT NULL search */
1238  if (skey->sk_flags & SK_SEARCHNULL)
1239  {
1241  skey->sk_subtype = InvalidOid;
1242  skey->sk_collation = InvalidOid;
1243  }
1244  else if (skey->sk_flags & SK_SEARCHNOTNULL)
1245  {
1246  if (skey->sk_flags & SK_BT_NULLS_FIRST)
1248  else
1250  skey->sk_subtype = InvalidOid;
1251  skey->sk_collation = InvalidOid;
1252  }
1253  else
1254  {
1255  /* regular qual, so it cannot be satisfied */
1256  return false;
1257  }
1258 
1259  /* Needn't do the rest */
1260  return true;
1261  }
1262 
1263  /* Adjust strategy for DESC, if we didn't already */
1264  if ((addflags & SK_BT_DESC) && !(skey->sk_flags & SK_BT_DESC))
1266  skey->sk_flags |= addflags;
1267 
1268  /* If it's a row header, fix row member flags and strategies similarly */
1269  if (skey->sk_flags & SK_ROW_HEADER)
1270  {
1271  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
1272 
1273  for (;;)
1274  {
1275  Assert(subkey->sk_flags & SK_ROW_MEMBER);
1276  addflags = indoption[subkey->sk_attno - 1] << SK_BT_INDOPTION_SHIFT;
1277  if ((addflags & SK_BT_DESC) && !(subkey->sk_flags & SK_BT_DESC))
1278  subkey->sk_strategy = BTCommuteStrategyNumber(subkey->sk_strategy);
1279  subkey->sk_flags |= addflags;
1280  if (subkey->sk_flags & SK_ROW_END)
1281  break;
1282  subkey++;
1283  }
1284  }
1285 
1286  return true;
1287 }
1288 
1289 /*
1290  * Mark a scankey as "required to continue the scan".
1291  *
1292  * Depending on the operator type, the key may be required for both scan
1293  * directions or just one. Also, if the key is a row comparison header,
1294  * we have to mark its first subsidiary ScanKey as required. (Subsequent
1295  * subsidiary ScanKeys are normally for lower-order columns, and thus
1296  * cannot be required, since they're after the first non-equality scankey.)
1297  *
1298  * Note: when we set required-key flag bits in a subsidiary scankey, we are
1299  * scribbling on a data structure belonging to the index AM's caller, not on
1300  * our private copy. This should be OK because the marking will not change
1301  * from scan to scan within a query, and so we'd just re-mark the same way
1302  * anyway on a rescan. Something to keep an eye on though.
1303  */
1304 static void
1306 {
1307  int addflags;
1308 
1309  switch (skey->sk_strategy)
1310  {
1311  case BTLessStrategyNumber:
1313  addflags = SK_BT_REQFWD;
1314  break;
1315  case BTEqualStrategyNumber:
1316  addflags = SK_BT_REQFWD | SK_BT_REQBKWD;
1317  break;
1320  addflags = SK_BT_REQBKWD;
1321  break;
1322  default:
1323  elog(ERROR, "unrecognized StrategyNumber: %d",
1324  (int) skey->sk_strategy);
1325  addflags = 0; /* keep compiler quiet */
1326  break;
1327  }
1328 
1329  skey->sk_flags |= addflags;
1330 
1331  if (skey->sk_flags & SK_ROW_HEADER)
1332  {
1333  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
1334 
1335  /* First subkey should be same column/operator as the header */
1336  Assert(subkey->sk_flags & SK_ROW_MEMBER);
1337  Assert(subkey->sk_attno == skey->sk_attno);
1338  Assert(subkey->sk_strategy == skey->sk_strategy);
1339  subkey->sk_flags |= addflags;
1340  }
1341 }
1342 
1343 /*
1344  * Test whether an indextuple satisfies all the scankey conditions.
1345  *
1346  * Return true if so, false if not. If the tuple fails to pass the qual,
1347  * we also determine whether there's any need to continue the scan beyond
1348  * this tuple, and set *continuescan accordingly. See comments for
1349  * _bt_preprocess_keys(), above, about how this is done.
1350  *
1351  * Forward scan callers can pass a high key tuple in the hopes of having
1352  * us set *continuescan to false, and avoiding an unnecessary visit to
1353  * the page to the right.
1354  *
1355  * scan: index scan descriptor (containing a search-type scankey)
1356  * tuple: index tuple to test
1357  * tupnatts: number of attributes in tupnatts (high key may be truncated)
1358  * dir: direction we are scanning in
1359  * continuescan: output parameter (will be set correctly in all cases)
1360  */
1361 bool
1362 _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, int tupnatts,
1363  ScanDirection dir, bool *continuescan)
1364 {
1365  TupleDesc tupdesc;
1366  BTScanOpaque so;
1367  int keysz;
1368  int ikey;
1369  ScanKey key;
1370 
1371  Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts);
1372 
1373  *continuescan = true; /* default assumption */
1374 
1375  tupdesc = RelationGetDescr(scan->indexRelation);
1376  so = (BTScanOpaque) scan->opaque;
1377  keysz = so->numberOfKeys;
1378 
1379  for (key = so->keyData, ikey = 0; ikey < keysz; key++, ikey++)
1380  {
1381  Datum datum;
1382  bool isNull;
1383  Datum test;
1384 
1385  if (key->sk_attno > tupnatts)
1386  {
1387  /*
1388  * This attribute is truncated (must be high key). The value for
1389  * this attribute in the first non-pivot tuple on the page to the
1390  * right could be any possible value. Assume that truncated
1391  * attribute passes the qual.
1392  */
1394  Assert(BTreeTupleIsPivot(tuple));
1395  continue;
1396  }
1397 
1398  /* row-comparison keys need special processing */
1399  if (key->sk_flags & SK_ROW_HEADER)
1400  {
1401  if (_bt_check_rowcompare(key, tuple, tupnatts, tupdesc, dir,
1402  continuescan))
1403  continue;
1404  return false;
1405  }
1406 
1407  datum = index_getattr(tuple,
1408  key->sk_attno,
1409  tupdesc,
1410  &isNull);
1411 
1412  if (key->sk_flags & SK_ISNULL)
1413  {
1414  /* Handle IS NULL/NOT NULL tests */
1415  if (key->sk_flags & SK_SEARCHNULL)
1416  {
1417  if (isNull)
1418  continue; /* tuple satisfies this qual */
1419  }
1420  else
1421  {
1422  Assert(key->sk_flags & SK_SEARCHNOTNULL);
1423  if (!isNull)
1424  continue; /* tuple satisfies this qual */
1425  }
1426 
1427  /*
1428  * Tuple fails this qual. If it's a required qual for the current
1429  * scan direction, then we can conclude no further tuples will
1430  * pass, either.
1431  */
1432  if ((key->sk_flags & SK_BT_REQFWD) &&
1434  *continuescan = false;
1435  else if ((key->sk_flags & SK_BT_REQBKWD) &&
1437  *continuescan = false;
1438 
1439  /*
1440  * In any case, this indextuple doesn't match the qual.
1441  */
1442  return false;
1443  }
1444 
1445  if (isNull)
1446  {
1447  if (key->sk_flags & SK_BT_NULLS_FIRST)
1448  {
1449  /*
1450  * Since NULLs are sorted before non-NULLs, we know we have
1451  * reached the lower limit of the range of values for this
1452  * index attr. On a backward scan, we can stop if this qual
1453  * is one of the "must match" subset. We can stop regardless
1454  * of whether the qual is > or <, so long as it's required,
1455  * because it's not possible for any future tuples to pass. On
1456  * a forward scan, however, we must keep going, because we may
1457  * have initially positioned to the start of the index.
1458  */
1459  if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1461  *continuescan = false;
1462  }
1463  else
1464  {
1465  /*
1466  * Since NULLs are sorted after non-NULLs, we know we have
1467  * reached the upper limit of the range of values for this
1468  * index attr. On a forward scan, we can stop if this qual is
1469  * one of the "must match" subset. We can stop regardless of
1470  * whether the qual is > or <, so long as it's required,
1471  * because it's not possible for any future tuples to pass. On
1472  * a backward scan, however, we must keep going, because we
1473  * may have initially positioned to the end of the index.
1474  */
1475  if ((key->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1477  *continuescan = false;
1478  }
1479 
1480  /*
1481  * In any case, this indextuple doesn't match the qual.
1482  */
1483  return false;
1484  }
1485 
1486  test = FunctionCall2Coll(&key->sk_func, key->sk_collation,
1487  datum, key->sk_argument);
1488 
1489  if (!DatumGetBool(test))
1490  {
1491  /*
1492  * Tuple fails this qual. If it's a required qual for the current
1493  * scan direction, then we can conclude no further tuples will
1494  * pass, either.
1495  *
1496  * Note: because we stop the scan as soon as any required equality
1497  * qual fails, it is critical that equality quals be used for the
1498  * initial positioning in _bt_first() when they are available. See
1499  * comments in _bt_first().
1500  */
1501  if ((key->sk_flags & SK_BT_REQFWD) &&
1503  *continuescan = false;
1504  else if ((key->sk_flags & SK_BT_REQBKWD) &&
1506  *continuescan = false;
1507 
1508  /*
1509  * In any case, this indextuple doesn't match the qual.
1510  */
1511  return false;
1512  }
1513  }
1514 
1515  /* If we get here, the tuple passes all index quals. */
1516  return true;
1517 }
1518 
1519 /*
1520  * Test whether an indextuple satisfies a row-comparison scan condition.
1521  *
1522  * Return true if so, false if not. If not, also clear *continuescan if
1523  * it's not possible for any future tuples in the current scan direction
1524  * to pass the qual.
1525  *
1526  * This is a subroutine for _bt_checkkeys, which see for more info.
1527  */
1528 static bool
1529 _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
1530  TupleDesc tupdesc, ScanDirection dir, bool *continuescan)
1531 {
1532  ScanKey subkey = (ScanKey) DatumGetPointer(skey->sk_argument);
1533  int32 cmpresult = 0;
1534  bool result;
1535 
1536  /* First subkey should be same as the header says */
1537  Assert(subkey->sk_attno == skey->sk_attno);
1538 
1539  /* Loop over columns of the row condition */
1540  for (;;)
1541  {
1542  Datum datum;
1543  bool isNull;
1544 
1545  Assert(subkey->sk_flags & SK_ROW_MEMBER);
1546 
1547  if (subkey->sk_attno > tupnatts)
1548  {
1549  /*
1550  * This attribute is truncated (must be high key). The value for
1551  * this attribute in the first non-pivot tuple on the page to the
1552  * right could be any possible value. Assume that truncated
1553  * attribute passes the qual.
1554  */
1556  Assert(BTreeTupleIsPivot(tuple));
1557  cmpresult = 0;
1558  if (subkey->sk_flags & SK_ROW_END)
1559  break;
1560  subkey++;
1561  continue;
1562  }
1563 
1564  datum = index_getattr(tuple,
1565  subkey->sk_attno,
1566  tupdesc,
1567  &isNull);
1568 
1569  if (isNull)
1570  {
1571  if (subkey->sk_flags & SK_BT_NULLS_FIRST)
1572  {
1573  /*
1574  * Since NULLs are sorted before non-NULLs, we know we have
1575  * reached the lower limit of the range of values for this
1576  * index attr. On a backward scan, we can stop if this qual
1577  * is one of the "must match" subset. We can stop regardless
1578  * of whether the qual is > or <, so long as it's required,
1579  * because it's not possible for any future tuples to pass. On
1580  * a forward scan, however, we must keep going, because we may
1581  * have initially positioned to the start of the index.
1582  */
1583  if ((subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1585  *continuescan = false;
1586  }
1587  else
1588  {
1589  /*
1590  * Since NULLs are sorted after non-NULLs, we know we have
1591  * reached the upper limit of the range of values for this
1592  * index attr. On a forward scan, we can stop if this qual is
1593  * one of the "must match" subset. We can stop regardless of
1594  * whether the qual is > or <, so long as it's required,
1595  * because it's not possible for any future tuples to pass. On
1596  * a backward scan, however, we must keep going, because we
1597  * may have initially positioned to the end of the index.
1598  */
1599  if ((subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) &&
1601  *continuescan = false;
1602  }
1603 
1604  /*
1605  * In any case, this indextuple doesn't match the qual.
1606  */
1607  return false;
1608  }
1609 
1610  if (subkey->sk_flags & SK_ISNULL)
1611  {
1612  /*
1613  * Unlike the simple-scankey case, this isn't a disallowed case.
1614  * But it can never match. If all the earlier row comparison
1615  * columns are required for the scan direction, we can stop the
1616  * scan, because there can't be another tuple that will succeed.
1617  */
1618  if (subkey != (ScanKey) DatumGetPointer(skey->sk_argument))
1619  subkey--;
1620  if ((subkey->sk_flags & SK_BT_REQFWD) &&
1622  *continuescan = false;
1623  else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
1625  *continuescan = false;
1626  return false;
1627  }
1628 
1629  /* Perform the test --- three-way comparison not bool operator */
1630  cmpresult = DatumGetInt32(FunctionCall2Coll(&subkey->sk_func,
1631  subkey->sk_collation,
1632  datum,
1633  subkey->sk_argument));
1634 
1635  if (subkey->sk_flags & SK_BT_DESC)
1636  INVERT_COMPARE_RESULT(cmpresult);
1637 
1638  /* Done comparing if unequal, else advance to next column */
1639  if (cmpresult != 0)
1640  break;
1641 
1642  if (subkey->sk_flags & SK_ROW_END)
1643  break;
1644  subkey++;
1645  }
1646 
1647  /*
1648  * At this point cmpresult indicates the overall result of the row
1649  * comparison, and subkey points to the deciding column (or the last
1650  * column if the result is "=").
1651  */
1652  switch (subkey->sk_strategy)
1653  {
1654  /* EQ and NE cases aren't allowed here */
1655  case BTLessStrategyNumber:
1656  result = (cmpresult < 0);
1657  break;
1659  result = (cmpresult <= 0);
1660  break;
1662  result = (cmpresult >= 0);
1663  break;
1665  result = (cmpresult > 0);
1666  break;
1667  default:
1668  elog(ERROR, "unrecognized RowCompareType: %d",
1669  (int) subkey->sk_strategy);
1670  result = 0; /* keep compiler quiet */
1671  break;
1672  }
1673 
1674  if (!result)
1675  {
1676  /*
1677  * Tuple fails this qual. If it's a required qual for the current
1678  * scan direction, then we can conclude no further tuples will pass,
1679  * either. Note we have to look at the deciding column, not
1680  * necessarily the first or last column of the row condition.
1681  */
1682  if ((subkey->sk_flags & SK_BT_REQFWD) &&
1684  *continuescan = false;
1685  else if ((subkey->sk_flags & SK_BT_REQBKWD) &&
1687  *continuescan = false;
1688  }
1689 
1690  return result;
1691 }
1692 
1693 /*
1694  * _bt_killitems - set LP_DEAD state for items an indexscan caller has
1695  * told us were killed
1696  *
1697  * scan->opaque, referenced locally through so, contains information about the
1698  * current page and killed tuples thereon (generally, this should only be
1699  * called if so->numKilled > 0).
1700  *
1701  * The caller does not have a lock on the page and may or may not have the
1702  * page pinned in a buffer. Note that read-lock is sufficient for setting
1703  * LP_DEAD status (which is only a hint).
1704  *
1705  * We match items by heap TID before assuming they are the right ones to
1706  * delete. We cope with cases where items have moved right due to insertions.
1707  * If an item has moved off the current page due to a split, we'll fail to
1708  * find it and do nothing (this is not an error case --- we assume the item
1709  * will eventually get marked in a future indexscan).
1710  *
1711  * Note that if we hold a pin on the target page continuously from initially
1712  * reading the items until applying this function, VACUUM cannot have deleted
1713  * any items from the page, and so there is no need to search left from the
1714  * recorded offset. (This observation also guarantees that the item is still
1715  * the right one to delete, which might otherwise be questionable since heap
1716  * TIDs can get recycled.) This holds true even if the page has been modified
1717  * by inserts and page splits, so there is no need to consult the LSN.
1718  *
1719  * If the pin was released after reading the page, then we re-read it. If it
1720  * has been modified since we read it (as determined by the LSN), we dare not
1721  * flag any entries because it is possible that the old entry was vacuumed
1722  * away and the TID was re-used by a completely different heap tuple.
1723  */
1724 void
1726 {
1727  BTScanOpaque so = (BTScanOpaque) scan->opaque;
1728  Page page;
1729  BTPageOpaque opaque;
1730  OffsetNumber minoff;
1731  OffsetNumber maxoff;
1732  int i;
1733  int numKilled = so->numKilled;
1734  bool killedsomething = false;
1735  bool droppedpin PG_USED_FOR_ASSERTS_ONLY;
1736 
1738 
1739  /*
1740  * Always reset the scan state, so we don't look for same items on other
1741  * pages.
1742  */
1743  so->numKilled = 0;
1744 
1745  if (BTScanPosIsPinned(so->currPos))
1746  {
1747  /*
1748  * We have held the pin on this page since we read the index tuples,
1749  * so all we need to do is lock it. The pin will have prevented
1750  * re-use of any TID on the page, so there is no need to check the
1751  * LSN.
1752  */
1753  droppedpin = false;
1755 
1756  page = BufferGetPage(so->currPos.buf);
1757  }
1758  else
1759  {
1760  Buffer buf;
1761 
1762  droppedpin = true;
1763  /* Attempt to re-read the buffer, getting pin and lock. */
1765 
1766  page = BufferGetPage(buf);
1767  if (BufferGetLSNAtomic(buf) == so->currPos.lsn)
1768  so->currPos.buf = buf;
1769  else
1770  {
1771  /* Modified while not pinned means hinting is not safe. */
1772  _bt_relbuf(scan->indexRelation, buf);
1773  return;
1774  }
1775  }
1776 
1777  opaque = BTPageGetOpaque(page);
1778  minoff = P_FIRSTDATAKEY(opaque);
1779  maxoff = PageGetMaxOffsetNumber(page);
1780 
1781  for (i = 0; i < numKilled; i++)
1782  {
1783  int itemIndex = so->killedItems[i];
1784  BTScanPosItem *kitem = &so->currPos.items[itemIndex];
1785  OffsetNumber offnum = kitem->indexOffset;
1786 
1787  Assert(itemIndex >= so->currPos.firstItem &&
1788  itemIndex <= so->currPos.lastItem);
1789  if (offnum < minoff)
1790  continue; /* pure paranoia */
1791  while (offnum <= maxoff)
1792  {
1793  ItemId iid = PageGetItemId(page, offnum);
1794  IndexTuple ituple = (IndexTuple) PageGetItem(page, iid);
1795  bool killtuple = false;
1796 
1797  if (BTreeTupleIsPosting(ituple))
1798  {
1799  int pi = i + 1;
1800  int nposting = BTreeTupleGetNPosting(ituple);
1801  int j;
1802 
1803  /*
1804  * We rely on the convention that heap TIDs in the scanpos
1805  * items array are stored in ascending heap TID order for a
1806  * group of TIDs that originally came from a posting list
1807  * tuple. This convention even applies during backwards
1808  * scans, where returning the TIDs in descending order might
1809  * seem more natural. This is about effectiveness, not
1810  * correctness.
1811  *
1812  * Note that the page may have been modified in almost any way
1813  * since we first read it (in the !droppedpin case), so it's
1814  * possible that this posting list tuple wasn't a posting list
1815  * tuple when we first encountered its heap TIDs.
1816  */
1817  for (j = 0; j < nposting; j++)
1818  {
1819  ItemPointer item = BTreeTupleGetPostingN(ituple, j);
1820 
1821  if (!ItemPointerEquals(item, &kitem->heapTid))
1822  break; /* out of posting list loop */
1823 
1824  /*
1825  * kitem must have matching offnum when heap TIDs match,
1826  * though only in the common case where the page can't
1827  * have been concurrently modified
1828  */
1829  Assert(kitem->indexOffset == offnum || !droppedpin);
1830 
1831  /*
1832  * Read-ahead to later kitems here.
1833  *
1834  * We rely on the assumption that not advancing kitem here
1835  * will prevent us from considering the posting list tuple
1836  * fully dead by not matching its next heap TID in next
1837  * loop iteration.
1838  *
1839  * If, on the other hand, this is the final heap TID in
1840  * the posting list tuple, then tuple gets killed
1841  * regardless (i.e. we handle the case where the last
1842  * kitem is also the last heap TID in the last index tuple
1843  * correctly -- posting tuple still gets killed).
1844  */
1845  if (pi < numKilled)
1846  kitem = &so->currPos.items[so->killedItems[pi++]];
1847  }
1848 
1849  /*
1850  * Don't bother advancing the outermost loop's int iterator to
1851  * avoid processing killed items that relate to the same
1852  * offnum/posting list tuple. This micro-optimization hardly
1853  * seems worth it. (Further iterations of the outermost loop
1854  * will fail to match on this same posting list's first heap
1855  * TID instead, so we'll advance to the next offnum/index
1856  * tuple pretty quickly.)
1857  */
1858  if (j == nposting)
1859  killtuple = true;
1860  }
1861  else if (ItemPointerEquals(&ituple->t_tid, &kitem->heapTid))
1862  killtuple = true;
1863 
1864  /*
1865  * Mark index item as dead, if it isn't already. Since this
1866  * happens while holding a buffer lock possibly in shared mode,
1867  * it's possible that multiple processes attempt to do this
1868  * simultaneously, leading to multiple full-page images being sent
1869  * to WAL (if wal_log_hints or data checksums are enabled), which
1870  * is undesirable.
1871  */
1872  if (killtuple && !ItemIdIsDead(iid))
1873  {
1874  /* found the item/all posting list items */
1875  ItemIdMarkDead(iid);
1876  killedsomething = true;
1877  break; /* out of inner search loop */
1878  }
1879  offnum = OffsetNumberNext(offnum);
1880  }
1881  }
1882 
1883  /*
1884  * Since this can be redone later if needed, mark as dirty hint.
1885  *
1886  * Whenever we mark anything LP_DEAD, we also set the page's
1887  * BTP_HAS_GARBAGE flag, which is likewise just a hint. (Note that we
1888  * only rely on the page-level flag in !heapkeyspace indexes.)
1889  */
1890  if (killedsomething)
1891  {
1892  opaque->btpo_flags |= BTP_HAS_GARBAGE;
1893  MarkBufferDirtyHint(so->currPos.buf, true);
1894  }
1895 
1896  _bt_unlockbuf(scan->indexRelation, so->currPos.buf);
1897 }
1898 
1899 
1900 /*
1901  * The following routines manage a shared-memory area in which we track
1902  * assignment of "vacuum cycle IDs" to currently-active btree vacuuming
1903  * operations. There is a single counter which increments each time we
1904  * start a vacuum to assign it a cycle ID. Since multiple vacuums could
1905  * be active concurrently, we have to track the cycle ID for each active
1906  * vacuum; this requires at most MaxBackends entries (usually far fewer).
1907  * We assume at most one vacuum can be active for a given index.
1908  *
1909  * Access to the shared memory area is controlled by BtreeVacuumLock.
1910  * In principle we could use a separate lmgr locktag for each index,
1911  * but a single LWLock is much cheaper, and given the short time that
1912  * the lock is ever held, the concurrency hit should be minimal.
1913  */
1914 
1915 typedef struct BTOneVacInfo
1916 {
1917  LockRelId relid; /* global identifier of an index */
1918  BTCycleId cycleid; /* cycle ID for its active VACUUM */
1920 
1921 typedef struct BTVacInfo
1922 {
1923  BTCycleId cycle_ctr; /* cycle ID most recently assigned */
1924  int num_vacuums; /* number of currently active VACUUMs */
1925  int max_vacuums; /* allocated length of vacuums[] array */
1928 
1930 
1931 
1932 /*
1933  * _bt_vacuum_cycleid --- get the active vacuum cycle ID for an index,
1934  * or zero if there is no active VACUUM
1935  *
1936  * Note: for correct interlocking, the caller must already hold pin and
1937  * exclusive lock on each buffer it will store the cycle ID into. This
1938  * ensures that even if a VACUUM starts immediately afterwards, it cannot
1939  * process those pages until the page split is complete.
1940  */
1941 BTCycleId
1943 {
1944  BTCycleId result = 0;
1945  int i;
1946 
1947  /* Share lock is enough since this is a read-only operation */
1948  LWLockAcquire(BtreeVacuumLock, LW_SHARED);
1949 
1950  for (i = 0; i < btvacinfo->num_vacuums; i++)
1951  {
1952  BTOneVacInfo *vac = &btvacinfo->vacuums[i];
1953 
1954  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
1955  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
1956  {
1957  result = vac->cycleid;
1958  break;
1959  }
1960  }
1961 
1962  LWLockRelease(BtreeVacuumLock);
1963  return result;
1964 }
1965 
1966 /*
1967  * _bt_start_vacuum --- assign a cycle ID to a just-starting VACUUM operation
1968  *
1969  * Note: the caller must guarantee that it will eventually call
1970  * _bt_end_vacuum, else we'll permanently leak an array slot. To ensure
1971  * that this happens even in elog(FATAL) scenarios, the appropriate coding
1972  * is not just a PG_TRY, but
1973  * PG_ENSURE_ERROR_CLEANUP(_bt_end_vacuum_callback, PointerGetDatum(rel))
1974  */
1975 BTCycleId
1977 {
1978  BTCycleId result;
1979  int i;
1980  BTOneVacInfo *vac;
1981 
1982  LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
1983 
1984  /*
1985  * Assign the next cycle ID, being careful to avoid zero as well as the
1986  * reserved high values.
1987  */
1988  result = ++(btvacinfo->cycle_ctr);
1989  if (result == 0 || result > MAX_BT_CYCLE_ID)
1990  result = btvacinfo->cycle_ctr = 1;
1991 
1992  /* Let's just make sure there's no entry already for this index */
1993  for (i = 0; i < btvacinfo->num_vacuums; i++)
1994  {
1995  vac = &btvacinfo->vacuums[i];
1996  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
1997  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
1998  {
1999  /*
2000  * Unlike most places in the backend, we have to explicitly
2001  * release our LWLock before throwing an error. This is because
2002  * we expect _bt_end_vacuum() to be called before transaction
2003  * abort cleanup can run to release LWLocks.
2004  */
2005  LWLockRelease(BtreeVacuumLock);
2006  elog(ERROR, "multiple active vacuums for index \"%s\"",
2008  }
2009  }
2010 
2011  /* OK, add an entry */
2013  {
2014  LWLockRelease(BtreeVacuumLock);
2015  elog(ERROR, "out of btvacinfo slots");
2016  }
2018  vac->relid = rel->rd_lockInfo.lockRelId;
2019  vac->cycleid = result;
2021 
2022  LWLockRelease(BtreeVacuumLock);
2023  return result;
2024 }
2025 
2026 /*
2027  * _bt_end_vacuum --- mark a btree VACUUM operation as done
2028  *
2029  * Note: this is deliberately coded not to complain if no entry is found;
2030  * this allows the caller to put PG_TRY around the start_vacuum operation.
2031  */
2032 void
2034 {
2035  int i;
2036 
2037  LWLockAcquire(BtreeVacuumLock, LW_EXCLUSIVE);
2038 
2039  /* Find the array entry */
2040  for (i = 0; i < btvacinfo->num_vacuums; i++)
2041  {
2042  BTOneVacInfo *vac = &btvacinfo->vacuums[i];
2043 
2044  if (vac->relid.relId == rel->rd_lockInfo.lockRelId.relId &&
2045  vac->relid.dbId == rel->rd_lockInfo.lockRelId.dbId)
2046  {
2047  /* Remove it by shifting down the last entry */
2048  *vac = btvacinfo->vacuums[btvacinfo->num_vacuums - 1];
2050  break;
2051  }
2052  }
2053 
2054  LWLockRelease(BtreeVacuumLock);
2055 }
2056 
2057 /*
2058  * _bt_end_vacuum wrapped as an on_shmem_exit callback function
2059  */
2060 void
2062 {
2064 }
2065 
2066 /*
2067  * BTreeShmemSize --- report amount of shared memory space needed
2068  */
2069 Size
2071 {
2072  Size size;
2073 
2074  size = offsetof(BTVacInfo, vacuums);
2075  size = add_size(size, mul_size(MaxBackends, sizeof(BTOneVacInfo)));
2076  return size;
2077 }
2078 
2079 /*
2080  * BTreeShmemInit --- initialize this module's shared memory
2081  */
2082 void
2084 {
2085  bool found;
2086 
2087  btvacinfo = (BTVacInfo *) ShmemInitStruct("BTree Vacuum State",
2088  BTreeShmemSize(),
2089  &found);
2090 
2091  if (!IsUnderPostmaster)
2092  {
2093  /* Initialize shared memory area */
2094  Assert(!found);
2095 
2096  /*
2097  * It doesn't really matter what the cycle counter starts at, but
2098  * having it always start the same doesn't seem good. Seed with
2099  * low-order bits of time() instead.
2100  */
2101  btvacinfo->cycle_ctr = (BTCycleId) time(NULL);
2102 
2103  btvacinfo->num_vacuums = 0;
2105  }
2106  else
2107  Assert(found);
2108 }
2109 
2110 bytea *
2111 btoptions(Datum reloptions, bool validate)
2112 {
2113  static const relopt_parse_elt tab[] = {
2114  {"fillfactor", RELOPT_TYPE_INT, offsetof(BTOptions, fillfactor)},
2115  {"vacuum_cleanup_index_scale_factor", RELOPT_TYPE_REAL,
2116  offsetof(BTOptions, vacuum_cleanup_index_scale_factor)},
2117  {"deduplicate_items", RELOPT_TYPE_BOOL,
2118  offsetof(BTOptions, deduplicate_items)}
2119  };
2120 
2121  return (bytea *) build_reloptions(reloptions, validate,
2123  sizeof(BTOptions),
2124  tab, lengthof(tab));
2125 }
2126 
2127 /*
2128  * btproperty() -- Check boolean properties of indexes.
2129  *
2130  * This is optional, but handling AMPROP_RETURNABLE here saves opening the rel
2131  * to call btcanreturn.
2132  */
2133 bool
2134 btproperty(Oid index_oid, int attno,
2135  IndexAMProperty prop, const char *propname,
2136  bool *res, bool *isnull)
2137 {
2138  switch (prop)
2139  {
2140  case AMPROP_RETURNABLE:
2141  /* answer only for columns, not AM or whole index */
2142  if (attno == 0)
2143  return false;
2144  /* otherwise, btree can always return data */
2145  *res = true;
2146  return true;
2147 
2148  default:
2149  return false; /* punt to generic code */
2150  }
2151 }
2152 
2153 /*
2154  * btbuildphasename() -- Return name of index build phase.
2155  */
2156 char *
2157 btbuildphasename(int64 phasenum)
2158 {
2159  switch (phasenum)
2160  {
2162  return "initializing";
2164  return "scanning table";
2166  return "sorting live tuples";
2168  return "sorting dead tuples";
2170  return "loading tuples in tree";
2171  default:
2172  return NULL;
2173  }
2174 }
2175 
2176 /*
2177  * _bt_truncate() -- create tuple without unneeded suffix attributes.
2178  *
2179  * Returns truncated pivot index tuple allocated in caller's memory context,
2180  * with key attributes copied from caller's firstright argument. If rel is
2181  * an INCLUDE index, non-key attributes will definitely be truncated away,
2182  * since they're not part of the key space. More aggressive suffix
2183  * truncation can take place when it's clear that the returned tuple does not
2184  * need one or more suffix key attributes. We only need to keep firstright
2185  * attributes up to and including the first non-lastleft-equal attribute.
2186  * Caller's insertion scankey is used to compare the tuples; the scankey's
2187  * argument values are not considered here.
2188  *
2189  * Note that returned tuple's t_tid offset will hold the number of attributes
2190  * present, so the original item pointer offset is not represented. Caller
2191  * should only change truncated tuple's downlink. Note also that truncated
2192  * key attributes are treated as containing "minus infinity" values by
2193  * _bt_compare().
2194  *
2195  * In the worst case (when a heap TID must be appended to distinguish lastleft
2196  * from firstright), the size of the returned tuple is the size of firstright
2197  * plus the size of an additional MAXALIGN()'d item pointer. This guarantee
2198  * is important, since callers need to stay under the 1/3 of a page
2199  * restriction on tuple size. If this routine is ever taught to truncate
2200  * within an attribute/datum, it will need to avoid returning an enlarged
2201  * tuple to caller when truncation + TOAST compression ends up enlarging the
2202  * final datum.
2203  */
2204 IndexTuple
2205 _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
2206  BTScanInsert itup_key)
2207 {
2208  TupleDesc itupdesc = RelationGetDescr(rel);
2210  int keepnatts;
2211  IndexTuple pivot;
2212  IndexTuple tidpivot;
2213  ItemPointer pivotheaptid;
2214  Size newsize;
2215 
2216  /*
2217  * We should only ever truncate non-pivot tuples from leaf pages. It's
2218  * never okay to truncate when splitting an internal page.
2219  */
2220  Assert(!BTreeTupleIsPivot(lastleft) && !BTreeTupleIsPivot(firstright));
2221 
2222  /* Determine how many attributes must be kept in truncated tuple */
2223  keepnatts = _bt_keep_natts(rel, lastleft, firstright, itup_key);
2224 
2225 #ifdef DEBUG_NO_TRUNCATE
2226  /* Force truncation to be ineffective for testing purposes */
2227  keepnatts = nkeyatts + 1;
2228 #endif
2229 
2230  pivot = index_truncate_tuple(itupdesc, firstright,
2231  Min(keepnatts, nkeyatts));
2232 
2233  if (BTreeTupleIsPosting(pivot))
2234  {
2235  /*
2236  * index_truncate_tuple() just returns a straight copy of firstright
2237  * when it has no attributes to truncate. When that happens, we may
2238  * need to truncate away a posting list here instead.
2239  */
2240  Assert(keepnatts == nkeyatts || keepnatts == nkeyatts + 1);
2241  Assert(IndexRelationGetNumberOfAttributes(rel) == nkeyatts);
2242  pivot->t_info &= ~INDEX_SIZE_MASK;
2243  pivot->t_info |= MAXALIGN(BTreeTupleGetPostingOffset(firstright));
2244  }
2245 
2246  /*
2247  * If there is a distinguishing key attribute within pivot tuple, we're
2248  * done
2249  */
2250  if (keepnatts <= nkeyatts)
2251  {
2252  BTreeTupleSetNAtts(pivot, keepnatts, false);
2253  return pivot;
2254  }
2255 
2256  /*
2257  * We have to store a heap TID in the new pivot tuple, since no non-TID
2258  * key attribute value in firstright distinguishes the right side of the
2259  * split from the left side. nbtree conceptualizes this case as an
2260  * inability to truncate away any key attributes, since heap TID is
2261  * treated as just another key attribute (despite lacking a pg_attribute
2262  * entry).
2263  *
2264  * Use enlarged space that holds a copy of pivot. We need the extra space
2265  * to store a heap TID at the end (using the special pivot tuple
2266  * representation). Note that the original pivot already has firstright's
2267  * possible posting list/non-key attribute values removed at this point.
2268  */
2269  newsize = MAXALIGN(IndexTupleSize(pivot)) + MAXALIGN(sizeof(ItemPointerData));
2270  tidpivot = palloc0(newsize);
2271  memcpy(tidpivot, pivot, MAXALIGN(IndexTupleSize(pivot)));
2272  /* Cannot leak memory here */
2273  pfree(pivot);
2274 
2275  /*
2276  * Store all of firstright's key attribute values plus a tiebreaker heap
2277  * TID value in enlarged pivot tuple
2278  */
2279  tidpivot->t_info &= ~INDEX_SIZE_MASK;
2280  tidpivot->t_info |= newsize;
2281  BTreeTupleSetNAtts(tidpivot, nkeyatts, true);
2282  pivotheaptid = BTreeTupleGetHeapTID(tidpivot);
2283 
2284  /*
2285  * Lehman & Yao use lastleft as the leaf high key in all cases, but don't
2286  * consider suffix truncation. It seems like a good idea to follow that
2287  * example in cases where no truncation takes place -- use lastleft's heap
2288  * TID. (This is also the closest value to negative infinity that's
2289  * legally usable.)
2290  */
2291  ItemPointerCopy(BTreeTupleGetMaxHeapTID(lastleft), pivotheaptid);
2292 
2293  /*
2294  * We're done. Assert() that heap TID invariants hold before returning.
2295  *
2296  * Lehman and Yao require that the downlink to the right page, which is to
2297  * be inserted into the parent page in the second phase of a page split be
2298  * a strict lower bound on items on the right page, and a non-strict upper
2299  * bound for items on the left page. Assert that heap TIDs follow these
2300  * invariants, since a heap TID value is apparently needed as a
2301  * tiebreaker.
2302  */
2303 #ifndef DEBUG_NO_TRUNCATE
2305  BTreeTupleGetHeapTID(firstright)) < 0);
2306  Assert(ItemPointerCompare(pivotheaptid,
2307  BTreeTupleGetHeapTID(lastleft)) >= 0);
2308  Assert(ItemPointerCompare(pivotheaptid,
2309  BTreeTupleGetHeapTID(firstright)) < 0);
2310 #else
2311 
2312  /*
2313  * Those invariants aren't guaranteed to hold for lastleft + firstright
2314  * heap TID attribute values when they're considered here only because
2315  * DEBUG_NO_TRUNCATE is defined (a heap TID is probably not actually
2316  * needed as a tiebreaker). DEBUG_NO_TRUNCATE must therefore use a heap
2317  * TID value that always works as a strict lower bound for items to the
2318  * right. In particular, it must avoid using firstright's leading key
2319  * attribute values along with lastleft's heap TID value when lastleft's
2320  * TID happens to be greater than firstright's TID.
2321  */
2322  ItemPointerCopy(BTreeTupleGetHeapTID(firstright), pivotheaptid);
2323 
2324  /*
2325  * Pivot heap TID should never be fully equal to firstright. Note that
2326  * the pivot heap TID will still end up equal to lastleft's heap TID when
2327  * that's the only usable value.
2328  */
2329  ItemPointerSetOffsetNumber(pivotheaptid,
2331  Assert(ItemPointerCompare(pivotheaptid,
2332  BTreeTupleGetHeapTID(firstright)) < 0);
2333 #endif
2334 
2335  return tidpivot;
2336 }
2337 
2338 /*
2339  * _bt_keep_natts - how many key attributes to keep when truncating.
2340  *
2341  * Caller provides two tuples that enclose a split point. Caller's insertion
2342  * scankey is used to compare the tuples; the scankey's argument values are
2343  * not considered here.
2344  *
2345  * This can return a number of attributes that is one greater than the
2346  * number of key attributes for the index relation. This indicates that the
2347  * caller must use a heap TID as a unique-ifier in new pivot tuple.
2348  */
2349 static int
2350 _bt_keep_natts(Relation rel, IndexTuple lastleft, IndexTuple firstright,
2351  BTScanInsert itup_key)
2352 {
2353  int nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
2354  TupleDesc itupdesc = RelationGetDescr(rel);
2355  int keepnatts;
2356  ScanKey scankey;
2357 
2358  /*
2359  * _bt_compare() treats truncated key attributes as having the value minus
2360  * infinity, which would break searches within !heapkeyspace indexes. We
2361  * must still truncate away non-key attribute values, though.
2362  */
2363  if (!itup_key->heapkeyspace)
2364  return nkeyatts;
2365 
2366  scankey = itup_key->scankeys;
2367  keepnatts = 1;
2368  for (int attnum = 1; attnum <= nkeyatts; attnum++, scankey++)
2369  {
2370  Datum datum1,
2371  datum2;
2372  bool isNull1,
2373  isNull2;
2374 
2375  datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
2376  datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
2377 
2378  if (isNull1 != isNull2)
2379  break;
2380 
2381  if (!isNull1 &&
2383  scankey->sk_collation,
2384  datum1,
2385  datum2)) != 0)
2386  break;
2387 
2388  keepnatts++;
2389  }
2390 
2391  /*
2392  * Assert that _bt_keep_natts_fast() agrees with us in passing. This is
2393  * expected in an allequalimage index.
2394  */
2395  Assert(!itup_key->allequalimage ||
2396  keepnatts == _bt_keep_natts_fast(rel, lastleft, firstright));
2397 
2398  return keepnatts;
2399 }
2400 
2401 /*
2402  * _bt_keep_natts_fast - fast bitwise variant of _bt_keep_natts.
2403  *
2404  * This is exported so that a candidate split point can have its effect on
2405  * suffix truncation inexpensively evaluated ahead of time when finding a
2406  * split location. A naive bitwise approach to datum comparisons is used to
2407  * save cycles.
2408  *
2409  * The approach taken here usually provides the same answer as _bt_keep_natts
2410  * will (for the same pair of tuples from a heapkeyspace index), since the
2411  * majority of btree opclasses can never indicate that two datums are equal
2412  * unless they're bitwise equal after detoasting. When an index only has
2413  * "equal image" columns, routine is guaranteed to give the same result as
2414  * _bt_keep_natts would.
2415  *
2416  * Callers can rely on the fact that attributes considered equal here are
2417  * definitely also equal according to _bt_keep_natts, even when the index uses
2418  * an opclass or collation that is not "allequalimage"/deduplication-safe.
2419  * This weaker guarantee is good enough for nbtsplitloc.c caller, since false
2420  * negatives generally only have the effect of making leaf page splits use a
2421  * more balanced split point.
2422  */
2423 int
2425 {
2426  TupleDesc itupdesc = RelationGetDescr(rel);
2427  int keysz = IndexRelationGetNumberOfKeyAttributes(rel);
2428  int keepnatts;
2429 
2430  keepnatts = 1;
2431  for (int attnum = 1; attnum <= keysz; attnum++)
2432  {
2433  Datum datum1,
2434  datum2;
2435  bool isNull1,
2436  isNull2;
2437  Form_pg_attribute att;
2438 
2439  datum1 = index_getattr(lastleft, attnum, itupdesc, &isNull1);
2440  datum2 = index_getattr(firstright, attnum, itupdesc, &isNull2);
2441  att = TupleDescAttr(itupdesc, attnum - 1);
2442 
2443  if (isNull1 != isNull2)
2444  break;
2445 
2446  if (!isNull1 &&
2447  !datum_image_eq(datum1, datum2, att->attbyval, att->attlen))
2448  break;
2449 
2450  keepnatts++;
2451  }
2452 
2453  return keepnatts;
2454 }
2455 
2456 /*
2457  * _bt_check_natts() -- Verify tuple has expected number of attributes.
2458  *
2459  * Returns value indicating if the expected number of attributes were found
2460  * for a particular offset on page. This can be used as a general purpose
2461  * sanity check.
2462  *
2463  * Testing a tuple directly with BTreeTupleGetNAtts() should generally be
2464  * preferred to calling here. That's usually more convenient, and is always
2465  * more explicit. Call here instead when offnum's tuple may be a negative
2466  * infinity tuple that uses the pre-v11 on-disk representation, or when a low
2467  * context check is appropriate. This routine is as strict as possible about
2468  * what is expected on each version of btree.
2469  */
2470 bool
2471 _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
2472 {
2475  BTPageOpaque opaque = BTPageGetOpaque(page);
2476  IndexTuple itup;
2477  int tupnatts;
2478 
2479  /*
2480  * We cannot reliably test a deleted or half-dead page, since they have
2481  * dummy high keys
2482  */
2483  if (P_IGNORE(opaque))
2484  return true;
2485 
2486  Assert(offnum >= FirstOffsetNumber &&
2487  offnum <= PageGetMaxOffsetNumber(page));
2488 
2489  /*
2490  * Mask allocated for number of keys in index tuple must be able to fit
2491  * maximum possible number of index attributes
2492  */
2494  "BT_OFFSET_MASK can't fit INDEX_MAX_KEYS");
2495 
2496  itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
2497  tupnatts = BTreeTupleGetNAtts(itup, rel);
2498 
2499  /* !heapkeyspace indexes do not support deduplication */
2500  if (!heapkeyspace && BTreeTupleIsPosting(itup))
2501  return false;
2502 
2503  /* Posting list tuples should never have "pivot heap TID" bit set */
2504  if (BTreeTupleIsPosting(itup) &&
2506  BT_PIVOT_HEAP_TID_ATTR) != 0)
2507  return false;
2508 
2509  /* INCLUDE indexes do not support deduplication */
2510  if (natts != nkeyatts && BTreeTupleIsPosting(itup))
2511  return false;
2512 
2513  if (P_ISLEAF(opaque))
2514  {
2515  if (offnum >= P_FIRSTDATAKEY(opaque))
2516  {
2517  /*
2518  * Non-pivot tuple should never be explicitly marked as a pivot
2519  * tuple
2520  */
2521  if (BTreeTupleIsPivot(itup))
2522  return false;
2523 
2524  /*
2525  * Leaf tuples that are not the page high key (non-pivot tuples)
2526  * should never be truncated. (Note that tupnatts must have been
2527  * inferred, even with a posting list tuple, because only pivot
2528  * tuples store tupnatts directly.)
2529  */
2530  return tupnatts == natts;
2531  }
2532  else
2533  {
2534  /*
2535  * Rightmost page doesn't contain a page high key, so tuple was
2536  * checked above as ordinary leaf tuple
2537  */
2538  Assert(!P_RIGHTMOST(opaque));
2539 
2540  /*
2541  * !heapkeyspace high key tuple contains only key attributes. Note
2542  * that tupnatts will only have been explicitly represented in
2543  * !heapkeyspace indexes that happen to have non-key attributes.
2544  */
2545  if (!heapkeyspace)
2546  return tupnatts == nkeyatts;
2547 
2548  /* Use generic heapkeyspace pivot tuple handling */
2549  }
2550  }
2551  else /* !P_ISLEAF(opaque) */
2552  {
2553  if (offnum == P_FIRSTDATAKEY(opaque))
2554  {
2555  /*
2556  * The first tuple on any internal page (possibly the first after
2557  * its high key) is its negative infinity tuple. Negative
2558  * infinity tuples are always truncated to zero attributes. They
2559  * are a particular kind of pivot tuple.
2560  */
2561  if (heapkeyspace)
2562  return tupnatts == 0;
2563 
2564  /*
2565  * The number of attributes won't be explicitly represented if the
2566  * negative infinity tuple was generated during a page split that
2567  * occurred with a version of Postgres before v11. There must be
2568  * a problem when there is an explicit representation that is
2569  * non-zero, or when there is no explicit representation and the
2570  * tuple is evidently not a pre-pg_upgrade tuple.
2571  *
2572  * Prior to v11, downlinks always had P_HIKEY as their offset.
2573  * Accept that as an alternative indication of a valid
2574  * !heapkeyspace negative infinity tuple.
2575  */
2576  return tupnatts == 0 ||
2578  }
2579  else
2580  {
2581  /*
2582  * !heapkeyspace downlink tuple with separator key contains only
2583  * key attributes. Note that tupnatts will only have been
2584  * explicitly represented in !heapkeyspace indexes that happen to
2585  * have non-key attributes.
2586  */
2587  if (!heapkeyspace)
2588  return tupnatts == nkeyatts;
2589 
2590  /* Use generic heapkeyspace pivot tuple handling */
2591  }
2592  }
2593 
2594  /* Handle heapkeyspace pivot tuples (excluding minus infinity items) */
2595  Assert(heapkeyspace);
2596 
2597  /*
2598  * Explicit representation of the number of attributes is mandatory with
2599  * heapkeyspace index pivot tuples, regardless of whether or not there are
2600  * non-key attributes.
2601  */
2602  if (!BTreeTupleIsPivot(itup))
2603  return false;
2604 
2605  /* Pivot tuple should not use posting list representation (redundant) */
2606  if (BTreeTupleIsPosting(itup))
2607  return false;
2608 
2609  /*
2610  * Heap TID is a tiebreaker key attribute, so it cannot be untruncated
2611  * when any other key attribute is truncated
2612  */
2613  if (BTreeTupleGetHeapTID(itup) != NULL && tupnatts != nkeyatts)
2614  return false;
2615 
2616  /*
2617  * Pivot tuple must have at least one untruncated key attribute (minus
2618  * infinity pivot tuples are the only exception). Pivot tuples can never
2619  * represent that there is a value present for a key attribute that
2620  * exceeds pg_index.indnkeyatts for the index.
2621  */
2622  return tupnatts > 0 && tupnatts <= nkeyatts;
2623 }
2624 
2625 /*
2626  *
2627  * _bt_check_third_page() -- check whether tuple fits on a btree page at all.
2628  *
2629  * We actually need to be able to fit three items on every page, so restrict
2630  * any one item to 1/3 the per-page available space. Note that itemsz should
2631  * not include the ItemId overhead.
2632  *
2633  * It might be useful to apply TOAST methods rather than throw an error here.
2634  * Using out of line storage would break assumptions made by suffix truncation
2635  * and by contrib/amcheck, though.
2636  */
2637 void
2638 _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace,
2639  Page page, IndexTuple newtup)
2640 {
2641  Size itemsz;
2642  BTPageOpaque opaque;
2643 
2644  itemsz = MAXALIGN(IndexTupleSize(newtup));
2645 
2646  /* Double check item size against limit */
2647  if (itemsz <= BTMaxItemSize(page))
2648  return;
2649 
2650  /*
2651  * Tuple is probably too large to fit on page, but it's possible that the
2652  * index uses version 2 or version 3, or that page is an internal page, in
2653  * which case a slightly higher limit applies.
2654  */
2655  if (!needheaptidspace && itemsz <= BTMaxItemSizeNoHeapTid(page))
2656  return;
2657 
2658  /*
2659  * Internal page insertions cannot fail here, because that would mean that
2660  * an earlier leaf level insertion that should have failed didn't
2661  */
2662  opaque = BTPageGetOpaque(page);
2663  if (!P_ISLEAF(opaque))
2664  elog(ERROR, "cannot insert oversized tuple of size %zu on internal page of index \"%s\"",
2665  itemsz, RelationGetRelationName(rel));
2666 
2667  ereport(ERROR,
2668  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
2669  errmsg("index row size %zu exceeds btree version %u maximum %zu for index \"%s\"",
2670  itemsz,
2671  needheaptidspace ? BTREE_VERSION : BTREE_NOVAC_VERSION,
2672  needheaptidspace ? BTMaxItemSize(page) :
2673  BTMaxItemSizeNoHeapTid(page),
2675  errdetail("Index row references tuple (%u,%u) in relation \"%s\".",
2678  RelationGetRelationName(heap)),
2679  errhint("Values larger than 1/3 of a buffer page cannot be indexed.\n"
2680  "Consider a function index of an MD5 hash of the value, "
2681  "or use full text indexing."),
2683 }
2684 
2685 /*
2686  * Are all attributes in rel "equality is image equality" attributes?
2687  *
2688  * We use each attribute's BTEQUALIMAGE_PROC opclass procedure. If any
2689  * opclass either lacks a BTEQUALIMAGE_PROC procedure or returns false, we
2690  * return false; otherwise we return true.
2691  *
2692  * Returned boolean value is stored in index metapage during index builds.
2693  * Deduplication can only be used when we return true.
2694  */
2695 bool
2696 _bt_allequalimage(Relation rel, bool debugmessage)
2697 {
2698  bool allequalimage = true;
2699 
2700  /* INCLUDE indexes can never support deduplication */
2703  return false;
2704 
2705  for (int i = 0; i < IndexRelationGetNumberOfKeyAttributes(rel); i++)
2706  {
2707  Oid opfamily = rel->rd_opfamily[i];
2708  Oid opcintype = rel->rd_opcintype[i];
2709  Oid collation = rel->rd_indcollation[i];
2710  Oid equalimageproc;
2711 
2712  equalimageproc = get_opfamily_proc(opfamily, opcintype, opcintype,
2714 
2715  /*
2716  * If there is no BTEQUALIMAGE_PROC then deduplication is assumed to
2717  * be unsafe. Otherwise, actually call proc and see what it says.
2718  */
2719  if (!OidIsValid(equalimageproc) ||
2720  !DatumGetBool(OidFunctionCall1Coll(equalimageproc, collation,
2721  ObjectIdGetDatum(opcintype))))
2722  {
2723  allequalimage = false;
2724  break;
2725  }
2726  }
2727 
2728  if (debugmessage)
2729  {
2730  if (allequalimage)
2731  elog(DEBUG1, "index \"%s\" can safely use deduplication",
2733  else
2734  elog(DEBUG1, "index \"%s\" cannot use deduplication",
2736  }
2737 
2738  return allequalimage;
2739 }
IndexAMProperty
Definition: amapi.h:35
@ AMPROP_RETURNABLE
Definition: amapi.h:43
#define DatumGetArrayTypeP(X)
Definition: array.h:254
#define ARR_ELEMTYPE(a)
Definition: array.h:285
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3577
int16 AttrNumber
Definition: attnum.h:21
int Buffer
Definition: buf.h:23
XLogRecPtr BufferGetLSNAtomic(Buffer buffer)
Definition: bufmgr.c:3004
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:3985
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
Pointer Page
Definition: bufpage.h:78
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:356
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:234
#define PageGetItem(page, itemId)
Definition: bufpage.h:339
#define RegProcedureIsValid(p)
Definition: c.h:723
#define Min(x, y)
Definition: c.h:997
#define INVERT_COMPARE_RESULT(var)
Definition: c.h:1133
signed short int16
Definition: c.h:439
#define MAXALIGN(LEN)
Definition: c.h:768
#define offsetof(type, field)
Definition: c.h:738
signed int int32
Definition: c.h:440
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:361
regproc RegProcedure
Definition: c.h:596
#define lengthof(array)
Definition: c.h:745
#define StaticAssertStmt(condition, errmessage)
Definition: c.h:929
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:166
#define OidIsValid(objectId)
Definition: c.h:721
size_t Size
Definition: c.h:551
bool datum_image_eq(Datum value1, Datum value2, bool typByVal, int typLen)
Definition: datum.c:266
struct cursor * cur
Definition: ecpg.c:28
int errdetail(const char *fmt,...)
Definition: elog.c:1037
int errhint(const char *fmt,...)
Definition: elog.c:1151
int errcode(int sqlerrcode)
Definition: elog.c:693
int errmsg(const char *fmt,...)
Definition: elog.c:904
#define DEBUG1
Definition: elog.h:24
#define ERROR
Definition: elog.h:33
#define ereport(elevel,...)
Definition: elog.h:143
Datum OidFunctionCall2Coll(Oid functionId, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1406
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1134
void fmgr_info(Oid functionId, FmgrInfo *finfo)
Definition: fmgr.c:126
Datum OidFunctionCall1Coll(Oid functionId, Oid collation, Datum arg1)
Definition: fmgr.c:1396
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
bool IsUnderPostmaster
Definition: globals.c:113
int MaxBackends
Definition: globals.c:140
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:803
IndexTuple index_truncate_tuple(TupleDesc sourceDescriptor, IndexTuple source, int leavenatts)
Definition: indextuple.c:557
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:52
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:29
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
#define ItemPointerCopy(fromPointer, toPointer)
Definition: itemptr.h:161
#define ItemPointerSetOffsetNumber(pointer, offsetNumber)
Definition: itemptr.h:148
#define ItemPointerGetOffsetNumberNoCheck(pointer)
Definition: itemptr.h:108
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
#define index_getattr(tup, attnum, tupleDesc, isnull)
Definition: itup.h:99
IndexTupleData * IndexTuple
Definition: itup.h:53
#define IndexTupleSize(itup)
Definition: itup.h:70
#define INDEX_SIZE_MASK
Definition: itup.h:65
Assert(fmt[strlen(fmt) - 1] !='\n')
void get_typlenbyvalalign(Oid typid, int16 *typlen, bool *typbyval, char *typalign)
Definition: lsyscache.c:2228
Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, int16 procnum)
Definition: lsyscache.c:794
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1266
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:164
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1196
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1800
@ LW_SHARED
Definition: lwlock.h:105
@ LW_EXCLUSIVE
Definition: lwlock.h:104
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:143
void pfree(void *pointer)
Definition: mcxt.c:1175
void * palloc0(Size size)
Definition: mcxt.c:1099
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
void * palloc(Size size)
Definition: mcxt.c:1068
#define AllocSetContextCreate
Definition: memutils.h:173
#define ALLOCSET_SMALL_SIZES
Definition: memutils.h:207
void _bt_relbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1035
void _bt_metaversion(Relation rel, bool *heapkeyspace, bool *allequalimage)
Definition: nbtpage.c:736
Buffer _bt_getbuf(Relation rel, BlockNumber blkno, int access)
Definition: nbtpage.c:871
void _bt_unlockbuf(Relation rel, Buffer buf)
Definition: nbtpage.c:1082
void _bt_lockbuf(Relation rel, Buffer buf, int access)
Definition: nbtpage.c:1051
void _bt_parallel_advance_array_keys(IndexScanDesc scan)
Definition: nbtree.c:757
#define BTScanPosIsPinned(scanpos)
Definition: nbtree.h:990
#define BT_PIVOT_HEAP_TID_ATTR
Definition: nbtree.h:467
static uint16 BTreeTupleGetNPosting(IndexTuple posting)
Definition: nbtree.h:513
static bool BTreeTupleIsPivot(IndexTuple itup)
Definition: nbtree.h:475
#define P_ISLEAF(opaque)
Definition: nbtree.h:221
#define P_HIKEY
Definition: nbtree.h:369
#define PROGRESS_BTREE_PHASE_PERFORMSORT_2
Definition: nbtree.h:1116
#define BTMaxItemSizeNoHeapTid(page)
Definition: nbtree.h:170
#define PROGRESS_BTREE_PHASE_LEAF_LOAD
Definition: nbtree.h:1117
#define BTP_HAS_GARBAGE
Definition: nbtree.h:82
#define BTEQUALIMAGE_PROC
Definition: nbtree.h:705
#define BTORDER_PROC
Definition: nbtree.h:702
#define BTPageGetOpaque(page)
Definition: nbtree.h:73
#define BTREE_VERSION
Definition: nbtree.h:150
#define BT_OFFSET_MASK
Definition: nbtree.h:464
#define BTScanPosIsValid(scanpos)
Definition: nbtree.h:1007
#define PROGRESS_BTREE_PHASE_INDEXBUILD_TABLESCAN
Definition: nbtree.h:1114
#define SK_BT_INDOPTION_SHIFT
Definition: nbtree.h:1083
#define P_FIRSTDATAKEY(opaque)
Definition: nbtree.h:371
#define MAX_BT_CYCLE_ID
Definition: nbtree.h:93
#define PROGRESS_BTREE_PHASE_PERFORMSORT_1
Definition: nbtree.h:1115
uint16 BTCycleId
Definition: nbtree.h:29
static uint32 BTreeTupleGetPostingOffset(IndexTuple posting)
Definition: nbtree.h:524
#define SK_BT_REQBKWD
Definition: nbtree.h:1082
#define P_RIGHTMOST(opaque)
Definition: nbtree.h:220
#define BTMaxItemSize(page)
Definition: nbtree.h:164
#define SK_BT_NULLS_FIRST
Definition: nbtree.h:1085
static ItemPointer BTreeTupleGetPostingN(IndexTuple posting, int n)
Definition: nbtree.h:539
#define BT_READ
Definition: nbtree.h:714
#define SK_BT_REQFWD
Definition: nbtree.h:1081
#define SK_BT_DESC
Definition: nbtree.h:1084
#define P_IGNORE(opaque)
Definition: nbtree.h:226
#define BTCommuteStrategyNumber(strat)
Definition: nbtree.h:680
static ItemPointer BTreeTupleGetMaxHeapTID(IndexTuple itup)
Definition: nbtree.h:659
static bool BTreeTupleIsPosting(IndexTuple itup)
Definition: nbtree.h:487
#define BTREE_NOVAC_VERSION
Definition: nbtree.h:152
static ItemPointer BTreeTupleGetHeapTID(IndexTuple itup)
Definition: nbtree.h:633
static void BTreeTupleSetNAtts(IndexTuple itup, uint16 nkeyatts, bool heaptid)
Definition: nbtree.h:590
#define BTreeTupleGetNAtts(itup, rel)
Definition: nbtree.h:572
BTScanOpaqueData * BTScanOpaque
Definition: nbtree.h:1074
void _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace, Page page, IndexTuple newtup)
Definition: nbtutils.c:2638
void _bt_end_vacuum(Relation rel)
Definition: nbtutils.c:2033
static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey, StrategyNumber strat, Datum *elems, int nelems)
Definition: nbtutils.c:382
char * btbuildphasename(int64 phasenum)
Definition: nbtutils.c:2157
void _bt_end_vacuum_callback(int code, Datum arg)
Definition: nbtutils.c:2061
void _bt_freestack(BTStack stack)
Definition: nbtutils.c:182
void BTreeShmemInit(void)
Definition: nbtutils.c:2083
static int _bt_sort_array_elements(IndexScanDesc scan, ScanKey skey, bool reverse, Datum *elems, int nelems)
Definition: nbtutils.c:449
struct BTSortArrayContext BTSortArrayContext
bytea * btoptions(Datum reloptions, bool validate)
Definition: nbtutils.c:2111
bool _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
Definition: nbtutils.c:551
struct BTVacInfo BTVacInfo
BTCycleId _bt_vacuum_cycleid(Relation rel)
Definition: nbtutils.c:1942
BTScanInsert _bt_mkscankey(Relation rel, IndexTuple itup)
Definition: nbtutils.c:90
void _bt_killitems(IndexScanDesc scan)
Definition: nbtutils.c:1725
bool _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, int tupnatts, ScanDirection dir, bool *continuescan)
Definition: nbtutils.c:1362
static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption)
Definition: nbtutils.c:1203
void _bt_preprocess_array_keys(IndexScanDesc scan)
Definition: nbtutils.c:210
bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
Definition: nbtutils.c:2471
IndexTuple _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
Definition: nbtutils.c:2205
int _bt_keep_natts_fast(Relation rel, IndexTuple lastleft, IndexTuple firstright)
Definition: nbtutils.c:2424
static BTVacInfo * btvacinfo
Definition: nbtutils.c:1929
static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op, ScanKey leftarg, ScanKey rightarg, bool *result)
Definition: nbtutils.c:1039
void _bt_restore_array_keys(IndexScanDesc scan)
Definition: nbtutils.c:629
static void _bt_mark_scankey_required(ScanKey skey)
Definition: nbtutils.c:1305
static int _bt_compare_array_elements(const void *a, const void *b, void *arg)
Definition: nbtutils.c:503
Size BTreeShmemSize(void)
Definition: nbtutils.c:2070
void _bt_mark_array_keys(IndexScanDesc scan)
Definition: nbtutils.c:610
static int _bt_keep_natts(Relation rel, IndexTuple lastleft, IndexTuple firstright, BTScanInsert itup_key)
Definition: nbtutils.c:2350
bool btproperty(Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
Definition: nbtutils.c:2134
bool _bt_allequalimage(Relation rel, bool debugmessage)
Definition: nbtutils.c:2696
struct BTOneVacInfo BTOneVacInfo
void _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir)
Definition: nbtutils.c:525
void _bt_preprocess_keys(IndexScanDesc scan)
Definition: nbtutils.c:749
static bool _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts, TupleDesc tupdesc, ScanDirection dir, bool *continuescan)
Definition: nbtutils.c:1529
BTCycleId _bt_start_vacuum(Relation rel)
Definition: nbtutils.c:1976
#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
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int16 attnum
Definition: pg_attribute.h:83
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:207
void * arg
#define INDEX_MAX_KEYS
static char * buf
Definition: pg_test_fsync.c:67
int fillfactor
Definition: pgbench.c:200
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
uintptr_t Datum
Definition: postgres.h:411
#define DatumGetBool(X)
Definition: postgres.h:437
#define DatumGetPointer(X)
Definition: postgres.h:593
#define ObjectIdGetDatum(X)
Definition: postgres.h:551
#define DatumGetInt32(X)
Definition: postgres.h:516
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
static void test(void)
#define PROGRESS_CREATEIDX_SUBPHASE_INITIALIZE
Definition: progress.h:104
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
#define RelationGetDescr(relation)
Definition: rel.h:514
#define RelationGetRelationName(relation)
Definition: rel.h:522
#define IndexRelationGetNumberOfAttributes(relation)
Definition: rel.h:500
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:507
int errtableconstraint(Relation rel, const char *conname)
Definition: relcache.c:5867
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:1910
@ 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:55
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
ScanDirection
Definition: sdir.h:23
Size add_size(Size s1, Size s2)
Definition: shmem.c:502
void * ShmemInitStruct(const char *name, Size size, bool *foundPtr)
Definition: shmem.c:396
Size mul_size(Size s1, Size s2)
Definition: shmem.c:519
#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
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:1029
BTCycleId cycleid
Definition: nbtutils.c:1918
LockRelId relid
Definition: nbtutils.c:1917
bool allequalimage
Definition: nbtree.h:787
bool heapkeyspace
Definition: nbtree.h:786
ScanKeyData scankeys[INDEX_MAX_KEYS]
Definition: nbtree.h:793
BTArrayKeyInfo * arrayKeys
Definition: nbtree.h:1045
BTScanPosData currPos
Definition: nbtree.h:1070
int * killedItems
Definition: nbtree.h:1049
ScanKey arrayKeyData
Definition: nbtree.h:1040
ScanKey keyData
Definition: nbtree.h:1037
MemoryContext arrayContext
Definition: nbtree.h:1046
Buffer buf
Definition: nbtree.h:953
BlockNumber currPage
Definition: nbtree.h:956
int firstItem
Definition: nbtree.h:981
BTScanPosItem items[MaxTIDsPerBTreePage]
Definition: nbtree.h:985
XLogRecPtr lsn
Definition: nbtree.h:955
ItemPointerData heapTid
Definition: nbtree.h:946
OffsetNumber indexOffset
Definition: nbtree.h:947
FmgrInfo flinfo
Definition: nbtutils.c:36
struct BTStackData * bts_parent
Definition: nbtree.h:731
BTCycleId cycle_ctr
Definition: nbtutils.c:1923
int num_vacuums
Definition: nbtutils.c:1924
BTOneVacInfo vacuums[FLEXIBLE_ARRAY_MEMBER]
Definition: nbtutils.c:1926
int max_vacuums
Definition: nbtutils.c:1925
Definition: fmgr.h:57
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:45
Definition: rel.h:38
Oid relId
Definition: rel.h:39
Oid dbId
Definition: rel.h:40
LockInfoData rd_lockInfo
Definition: rel.h:112
Oid * rd_opcintype
Definition: rel.h:203
int16 * rd_indoption
Definition: rel.h:206
Form_pg_index rd_index
Definition: rel.h:187
Oid * rd_opfamily
Definition: rel.h:202
Oid * rd_indcollation
Definition: rel.h:212
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: skey.h:67
Definition: c.h:633
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:92