PostgreSQL Source Code  git master
spgscan.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * spgscan.c
4  * routines for scanning SP-GiST indexes
5  *
6  *
7  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
8  * Portions Copyright (c) 1994, Regents of the University of California
9  *
10  * IDENTIFICATION
11  * src/backend/access/spgist/spgscan.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 
16 #include "postgres.h"
17 
18 #include "access/genam.h"
19 #include "access/relscan.h"
20 #include "access/spgist_private.h"
21 #include "miscadmin.h"
22 #include "storage/bufmgr.h"
23 #include "utils/datum.h"
24 #include "utils/float.h"
25 #include "utils/lsyscache.h"
26 #include "utils/memutils.h"
27 #include "utils/rel.h"
28 
29 typedef void (*storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr,
30  Datum leafValue, bool isNull,
31  SpGistLeafTuple leafTuple, bool recheck,
32  bool recheckDistances, double *distances);
33 
34 /*
35  * Pairing heap comparison function for the SpGistSearchItem queue.
36  * KNN-searches currently only support NULLS LAST. So, preserve this logic
37  * here.
38  */
39 static int
41  const pairingheap_node *b, void *arg)
42 {
43  const SpGistSearchItem *sa = (const SpGistSearchItem *) a;
44  const SpGistSearchItem *sb = (const SpGistSearchItem *) b;
46  int i;
47 
48  if (sa->isNull)
49  {
50  if (!sb->isNull)
51  return -1;
52  }
53  else if (sb->isNull)
54  {
55  return 1;
56  }
57  else
58  {
59  /* Order according to distance comparison */
60  for (i = 0; i < so->numberOfNonNullOrderBys; i++)
61  {
62  if (isnan(sa->distances[i]) && isnan(sb->distances[i]))
63  continue; /* NaN == NaN */
64  if (isnan(sa->distances[i]))
65  return -1; /* NaN > number */
66  if (isnan(sb->distances[i]))
67  return 1; /* number < NaN */
68  if (sa->distances[i] != sb->distances[i])
69  return (sa->distances[i] < sb->distances[i]) ? 1 : -1;
70  }
71  }
72 
73  /* Leaf items go before inner pages, to ensure a depth-first search */
74  if (sa->isLeaf && !sb->isLeaf)
75  return 1;
76  if (!sa->isLeaf && sb->isLeaf)
77  return -1;
78 
79  return 0;
80 }
81 
82 static void
84 {
85  /* value is of type attType if isLeaf, else of type attLeafType */
86  /* (no, that is not backwards; yes, it's confusing) */
87  if (!(item->isLeaf ? so->state.attType.attbyval :
88  so->state.attLeafType.attbyval) &&
89  DatumGetPointer(item->value) != NULL)
90  pfree(DatumGetPointer(item->value));
91 
92  if (item->leafTuple)
93  pfree(item->leafTuple);
94 
95  if (item->traversalValue)
96  pfree(item->traversalValue);
97 
98  pfree(item);
99 }
100 
101 /*
102  * Add SpGistSearchItem to queue
103  *
104  * Called in queue context
105  */
106 static void
108 {
109  pairingheap_add(so->scanQueue, &item->phNode);
110 }
111 
112 static SpGistSearchItem *
113 spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances)
114 {
115  /* allocate distance array only for non-NULL items */
116  SpGistSearchItem *item =
118 
119  item->isNull = isnull;
120 
121  if (!isnull && so->numberOfNonNullOrderBys > 0)
122  memcpy(item->distances, distances,
123  sizeof(item->distances[0]) * so->numberOfNonNullOrderBys);
124 
125  return item;
126 }
127 
128 static void
130 {
131  SpGistSearchItem *startEntry =
132  spgAllocSearchItem(so, isnull, so->zeroDistances);
133 
134  ItemPointerSet(&startEntry->heapPtr,
137  startEntry->isLeaf = false;
138  startEntry->level = 0;
139  startEntry->value = (Datum) 0;
140  startEntry->leafTuple = NULL;
141  startEntry->traversalValue = NULL;
142  startEntry->recheck = false;
143  startEntry->recheckDistances = false;
144 
145  spgAddSearchItemToQueue(so, startEntry);
146 }
147 
148 /*
149  * Initialize queue to search the root page, resetting
150  * any previously active scan
151  */
152 static void
154 {
155  MemoryContext oldCtx;
156 
158 
159  oldCtx = MemoryContextSwitchTo(so->traversalCxt);
160 
161  /* initialize queue only for distance-ordered scans */
163 
164  if (so->searchNulls)
165  /* Add a work item to scan the null index entries */
166  spgAddStartItem(so, true);
167 
168  if (so->searchNonNulls)
169  /* Add a work item to scan the non-null index entries */
170  spgAddStartItem(so, false);
171 
172  MemoryContextSwitchTo(oldCtx);
173 
174  if (so->numberOfOrderBys > 0)
175  {
176  /* Must pfree distances to avoid memory leak */
177  int i;
178 
179  for (i = 0; i < so->nPtrs; i++)
180  if (so->distances[i])
181  pfree(so->distances[i]);
182  }
183 
184  if (so->want_itup)
185  {
186  /* Must pfree reconstructed tuples to avoid memory leak */
187  int i;
188 
189  for (i = 0; i < so->nPtrs; i++)
190  pfree(so->reconTups[i]);
191  }
192  so->iPtr = so->nPtrs = 0;
193 }
194 
195 /*
196  * Prepare scan keys in SpGistScanOpaque from caller-given scan keys
197  *
198  * Sets searchNulls, searchNonNulls, numberOfKeys, keyData fields of *so.
199  *
200  * The point here is to eliminate null-related considerations from what the
201  * opclass consistent functions need to deal with. We assume all SPGiST-
202  * indexable operators are strict, so any null RHS value makes the scan
203  * condition unsatisfiable. We also pull out any IS NULL/IS NOT NULL
204  * conditions; their effect is reflected into searchNulls/searchNonNulls.
205  */
206 static void
208 {
210  bool qual_ok;
211  bool haveIsNull;
212  bool haveNotNull;
213  int nkeys;
214  int i;
215 
217  so->orderByData = scan->orderByData;
218 
219  if (so->numberOfOrderBys <= 0)
220  so->numberOfNonNullOrderBys = 0;
221  else
222  {
223  int j = 0;
224 
225  /*
226  * Remove all NULL keys, but remember their offsets in the original
227  * array.
228  */
229  for (i = 0; i < scan->numberOfOrderBys; i++)
230  {
231  ScanKey skey = &so->orderByData[i];
232 
233  if (skey->sk_flags & SK_ISNULL)
234  so->nonNullOrderByOffsets[i] = -1;
235  else
236  {
237  if (i != j)
238  so->orderByData[j] = *skey;
239 
240  so->nonNullOrderByOffsets[i] = j++;
241  }
242  }
243 
244  so->numberOfNonNullOrderBys = j;
245  }
246 
247  if (scan->numberOfKeys <= 0)
248  {
249  /* If no quals, whole-index scan is required */
250  so->searchNulls = true;
251  so->searchNonNulls = true;
252  so->numberOfKeys = 0;
253  return;
254  }
255 
256  /* Examine the given quals */
257  qual_ok = true;
258  haveIsNull = haveNotNull = false;
259  nkeys = 0;
260  for (i = 0; i < scan->numberOfKeys; i++)
261  {
262  ScanKey skey = &scan->keyData[i];
263 
264  if (skey->sk_flags & SK_SEARCHNULL)
265  haveIsNull = true;
266  else if (skey->sk_flags & SK_SEARCHNOTNULL)
267  haveNotNull = true;
268  else if (skey->sk_flags & SK_ISNULL)
269  {
270  /* ordinary qual with null argument - unsatisfiable */
271  qual_ok = false;
272  break;
273  }
274  else
275  {
276  /* ordinary qual, propagate into so->keyData */
277  so->keyData[nkeys++] = *skey;
278  /* this effectively creates a not-null requirement */
279  haveNotNull = true;
280  }
281  }
282 
283  /* IS NULL in combination with something else is unsatisfiable */
284  if (haveIsNull && haveNotNull)
285  qual_ok = false;
286 
287  /* Emit results */
288  if (qual_ok)
289  {
290  so->searchNulls = haveIsNull;
291  so->searchNonNulls = haveNotNull;
292  so->numberOfKeys = nkeys;
293  }
294  else
295  {
296  so->searchNulls = false;
297  so->searchNonNulls = false;
298  so->numberOfKeys = 0;
299  }
300 }
301 
303 spgbeginscan(Relation rel, int keysz, int orderbysz)
304 {
305  IndexScanDesc scan;
306  SpGistScanOpaque so;
307  int i;
308 
309  scan = RelationGetIndexScan(rel, keysz, orderbysz);
310 
312  if (keysz > 0)
313  so->keyData = (ScanKey) palloc(sizeof(ScanKeyData) * keysz);
314  else
315  so->keyData = NULL;
316  initSpGistState(&so->state, scan->indexRelation);
317 
319  "SP-GiST search temporary context",
322  "SP-GiST traversal-value context",
324 
325  /*
326  * Set up reconTupDesc and xs_hitupdesc in case it's an index-only scan,
327  * making sure that the key column is shown as being of type attType.
328  * (It's rather annoying to do this work when it might be wasted, but for
329  * most opclasses we can re-use the index reldesc instead of making one.)
330  */
331  so->reconTupDesc = scan->xs_hitupdesc =
332  getSpGistTupleDesc(rel, &so->state.attType);
333 
334  /* Allocate various arrays needed for order-by scans */
335  if (scan->numberOfOrderBys > 0)
336  {
337  /* This will be filled in spgrescan, but allocate the space here */
338  so->orderByTypes = (Oid *)
339  palloc(sizeof(Oid) * scan->numberOfOrderBys);
340  so->nonNullOrderByOffsets = (int *)
341  palloc(sizeof(int) * scan->numberOfOrderBys);
342 
343  /* These arrays have constant contents, so we can fill them now */
344  so->zeroDistances = (double *)
345  palloc(sizeof(double) * scan->numberOfOrderBys);
346  so->infDistances = (double *)
347  palloc(sizeof(double) * scan->numberOfOrderBys);
348 
349  for (i = 0; i < scan->numberOfOrderBys; i++)
350  {
351  so->zeroDistances[i] = 0.0;
353  }
354 
355  scan->xs_orderbyvals = (Datum *)
356  palloc0(sizeof(Datum) * scan->numberOfOrderBys);
357  scan->xs_orderbynulls = (bool *)
358  palloc(sizeof(bool) * scan->numberOfOrderBys);
359  memset(scan->xs_orderbynulls, true,
360  sizeof(bool) * scan->numberOfOrderBys);
361  }
362 
366 
370 
371  so->indexCollation = rel->rd_indcollation[0];
372 
373  scan->opaque = so;
374 
375  return scan;
376 }
377 
378 void
379 spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
380  ScanKey orderbys, int norderbys)
381 {
383 
384  /* copy scankeys into local storage */
385  if (scankey && scan->numberOfKeys > 0)
386  memmove(scan->keyData, scankey,
387  scan->numberOfKeys * sizeof(ScanKeyData));
388 
389  /* initialize order-by data if needed */
390  if (orderbys && scan->numberOfOrderBys > 0)
391  {
392  int i;
393 
394  memmove(scan->orderByData, orderbys,
395  scan->numberOfOrderBys * sizeof(ScanKeyData));
396 
397  for (i = 0; i < scan->numberOfOrderBys; i++)
398  {
399  ScanKey skey = &scan->orderByData[i];
400 
401  /*
402  * Look up the datatype returned by the original ordering
403  * operator. SP-GiST always uses a float8 for the distance
404  * function, but the ordering operator could be anything else.
405  *
406  * XXX: The distance function is only allowed to be lossy if the
407  * ordering operator's result type is float4 or float8. Otherwise
408  * we don't know how to return the distance to the executor. But
409  * we cannot check that here, as we won't know if the distance
410  * function is lossy until it returns *recheck = true for the
411  * first time.
412  */
414  }
415  }
416 
417  /* preprocess scankeys, set up the representation in *so */
418  spgPrepareScanKeys(scan);
419 
420  /* set up starting queue entries */
422 }
423 
424 void
426 {
428 
431 
432  if (so->keyData)
433  pfree(so->keyData);
434 
435  if (so->state.leafTupDesc &&
438 
439  if (so->state.deadTupleStorage)
441 
442  if (scan->numberOfOrderBys > 0)
443  {
444  pfree(so->orderByTypes);
446  pfree(so->zeroDistances);
447  pfree(so->infDistances);
448  pfree(scan->xs_orderbyvals);
449  pfree(scan->xs_orderbynulls);
450  }
451 
452  pfree(so);
453 }
454 
455 /*
456  * Leaf SpGistSearchItem constructor, called in queue context
457  */
458 static SpGistSearchItem *
460  Datum leafValue, bool recheck, bool recheckDistances,
461  bool isnull, double *distances)
462 {
463  SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
464 
465  item->level = level;
466  item->heapPtr = leafTuple->heapPtr;
467 
468  /*
469  * If we need the reconstructed value, copy it to queue cxt out of tmp
470  * cxt. Caution: the leaf_consistent method may not have supplied a value
471  * if we didn't ask it to, and mildly-broken methods might supply one of
472  * the wrong type. The correct leafValue type is attType not leafType.
473  */
474  if (so->want_itup)
475  {
476  item->value = isnull ? (Datum) 0 :
477  datumCopy(leafValue, so->state.attType.attbyval,
478  so->state.attType.attlen);
479 
480  /*
481  * If we're going to need to reconstruct INCLUDE attributes, store the
482  * whole leaf tuple so we can get the INCLUDE attributes out of it.
483  */
484  if (so->state.leafTupDesc->natts > 1)
485  {
486  item->leafTuple = palloc(leafTuple->size);
487  memcpy(item->leafTuple, leafTuple, leafTuple->size);
488  }
489  else
490  item->leafTuple = NULL;
491  }
492  else
493  {
494  item->value = (Datum) 0;
495  item->leafTuple = NULL;
496  }
497  item->traversalValue = NULL;
498  item->isLeaf = true;
499  item->recheck = recheck;
500  item->recheckDistances = recheckDistances;
501 
502  return item;
503 }
504 
505 /*
506  * Test whether a leaf tuple satisfies all the scan keys
507  *
508  * *reportedSome is set to true if:
509  * the scan is not ordered AND the item satisfies the scankeys
510  */
511 static bool
513  SpGistLeafTuple leafTuple, bool isnull,
514  bool *reportedSome, storeRes_func storeRes)
515 {
516  Datum leafValue;
517  double *distances;
518  bool result;
519  bool recheck;
520  bool recheckDistances;
521 
522  if (isnull)
523  {
524  /* Should not have arrived on a nulls page unless nulls are wanted */
525  Assert(so->searchNulls);
526  leafValue = (Datum) 0;
527  distances = NULL;
528  recheck = false;
529  recheckDistances = false;
530  result = true;
531  }
532  else
533  {
536 
537  /* use temp context for calling leaf_consistent */
539 
540  in.scankeys = so->keyData;
541  in.nkeys = so->numberOfKeys;
542  in.orderbys = so->orderByData;
544  Assert(!item->isLeaf); /* else reconstructedValue would be wrong type */
545  in.reconstructedValue = item->value;
546  in.traversalValue = item->traversalValue;
547  in.level = item->level;
548  in.returnData = so->want_itup;
549  in.leafDatum = SGLTDATUM(leafTuple, &so->state);
550 
551  out.leafValue = (Datum) 0;
552  out.recheck = false;
553  out.distances = NULL;
554  out.recheckDistances = false;
555 
557  so->indexCollation,
558  PointerGetDatum(&in),
559  PointerGetDatum(&out)));
560  recheck = out.recheck;
561  recheckDistances = out.recheckDistances;
562  leafValue = out.leafValue;
563  distances = out.distances;
564 
565  MemoryContextSwitchTo(oldCxt);
566  }
567 
568  if (result)
569  {
570  /* item passes the scankeys */
571  if (so->numberOfNonNullOrderBys > 0)
572  {
573  /* the scan is ordered -> add the item to the queue */
575  SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
576  leafTuple,
577  leafValue,
578  recheck,
579  recheckDistances,
580  isnull,
581  distances);
582 
583  spgAddSearchItemToQueue(so, heapItem);
584 
585  MemoryContextSwitchTo(oldCxt);
586  }
587  else
588  {
589  /* non-ordered scan, so report the item right away */
590  Assert(!recheckDistances);
591  storeRes(so, &leafTuple->heapPtr, leafValue, isnull,
592  leafTuple, recheck, false, NULL);
593  *reportedSome = true;
594  }
595  }
596 
597  return result;
598 }
599 
600 /* A bundle initializer for inner_consistent methods */
601 static void
603  SpGistScanOpaque so,
604  SpGistSearchItem *item,
605  SpGistInnerTuple innerTuple)
606 {
607  in->scankeys = so->keyData;
608  in->orderbys = so->orderByData;
609  in->nkeys = so->numberOfKeys;
611  Assert(!item->isLeaf); /* else reconstructedValue would be wrong type */
612  in->reconstructedValue = item->value;
614  in->traversalValue = item->traversalValue;
615  in->level = item->level;
616  in->returnData = so->want_itup;
617  in->allTheSame = innerTuple->allTheSame;
618  in->hasPrefix = (innerTuple->prefixSize > 0);
619  in->prefixDatum = SGITDATUM(innerTuple, &so->state);
620  in->nNodes = innerTuple->nNodes;
621  in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
622 }
623 
624 static SpGistSearchItem *
626  SpGistSearchItem *parentItem,
627  SpGistNodeTuple tuple,
628  spgInnerConsistentOut *out, int i, bool isnull,
629  double *distances)
630 {
631  SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
632 
633  item->heapPtr = tuple->t_tid;
634  item->level = out->levelAdds ? parentItem->level + out->levelAdds[i]
635  : parentItem->level;
636 
637  /* Must copy value out of temp context */
638  /* (recall that reconstructed values are of type leafType) */
639  item->value = out->reconstructedValues
640  ? datumCopy(out->reconstructedValues[i],
643  : (Datum) 0;
644 
645  item->leafTuple = NULL;
646 
647  /*
648  * Elements of out.traversalValues should be allocated in
649  * in.traversalMemoryContext, which is actually a long lived context of
650  * index scan.
651  */
652  item->traversalValue =
653  out->traversalValues ? out->traversalValues[i] : NULL;
654 
655  item->isLeaf = false;
656  item->recheck = false;
657  item->recheckDistances = false;
658 
659  return item;
660 }
661 
662 static void
664  SpGistInnerTuple innerTuple, bool isnull)
665 {
668  int nNodes = innerTuple->nNodes;
669  int i;
670 
671  memset(&out, 0, sizeof(out));
672 
673  if (!isnull)
674  {
676 
677  spgInitInnerConsistentIn(&in, so, item, innerTuple);
678 
679  /* use user-defined inner consistent method */
681  so->indexCollation,
682  PointerGetDatum(&in),
683  PointerGetDatum(&out));
684  }
685  else
686  {
687  /* force all children to be visited */
688  out.nNodes = nNodes;
689  out.nodeNumbers = (int *) palloc(sizeof(int) * nNodes);
690  for (i = 0; i < nNodes; i++)
691  out.nodeNumbers[i] = i;
692  }
693 
694  /* If allTheSame, they should all or none of them match */
695  if (innerTuple->allTheSame && out.nNodes != 0 && out.nNodes != nNodes)
696  elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
697 
698  if (out.nNodes)
699  {
700  /* collect node pointers */
701  SpGistNodeTuple node;
702  SpGistNodeTuple *nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * nNodes);
703 
704  SGITITERATE(innerTuple, i, node)
705  {
706  nodes[i] = node;
707  }
708 
710 
711  for (i = 0; i < out.nNodes; i++)
712  {
713  int nodeN = out.nodeNumbers[i];
714  SpGistSearchItem *innerItem;
715  double *distances;
716 
717  Assert(nodeN >= 0 && nodeN < nNodes);
718 
719  node = nodes[nodeN];
720 
721  if (!ItemPointerIsValid(&node->t_tid))
722  continue;
723 
724  /*
725  * Use infinity distances if innerConsistentFn() failed to return
726  * them or if is a NULL item (their distances are really unused).
727  */
728  distances = out.distances ? out.distances[i] : so->infDistances;
729 
730  innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull,
731  distances);
732 
733  spgAddSearchItemToQueue(so, innerItem);
734  }
735  }
736 
737  MemoryContextSwitchTo(oldCxt);
738 }
739 
740 /* Returns a next item in an (ordered) scan or null if the index is exhausted */
741 static SpGistSearchItem *
743 {
745  return NULL; /* Done when both heaps are empty */
746 
747  /* Return item; caller is responsible to pfree it */
749 }
750 
752 {
756 };
757 
758 static OffsetNumber
760  SpGistSearchItem *item,
761  Page page, OffsetNumber offset,
762  bool isnull, bool isroot,
763  bool *reportedSome,
764  storeRes_func storeRes)
765 {
766  SpGistLeafTuple leafTuple = (SpGistLeafTuple)
767  PageGetItem(page, PageGetItemId(page, offset));
768 
769  if (leafTuple->tupstate != SPGIST_LIVE)
770  {
771  if (!isroot) /* all tuples on root should be live */
772  {
773  if (leafTuple->tupstate == SPGIST_REDIRECT)
774  {
775  /* redirection tuple should be first in chain */
776  Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
777  /* transfer attention to redirect point */
778  item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer;
781  }
782 
783  if (leafTuple->tupstate == SPGIST_DEAD)
784  {
785  /* dead tuple should be first in chain */
786  Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
787  /* No live entries on this page */
790  }
791  }
792 
793  /* We should not arrive at a placeholder */
794  elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate);
796  }
797 
798  Assert(ItemPointerIsValid(&leafTuple->heapPtr));
799 
800  spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes);
801 
802  return SGLT_GET_NEXTOFFSET(leafTuple);
803 }
804 
805 /*
806  * Walk the tree and report all tuples passing the scan quals to the storeRes
807  * subroutine.
808  *
809  * If scanWholeIndex is true, we'll do just that. If not, we'll stop at the
810  * next page boundary once we have reported at least one tuple.
811  */
812 static void
813 spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex,
814  storeRes_func storeRes, Snapshot snapshot)
815 {
816  Buffer buffer = InvalidBuffer;
817  bool reportedSome = false;
818 
819  while (scanWholeIndex || !reportedSome)
820  {
822 
823  if (item == NULL)
824  break; /* No more items in queue -> done */
825 
826 redirect:
827  /* Check for interrupts, just in case of infinite loop */
829 
830  if (item->isLeaf)
831  {
832  /* We store heap items in the queue only in case of ordered search */
834  storeRes(so, &item->heapPtr, item->value, item->isNull,
835  item->leafTuple, item->recheck,
836  item->recheckDistances, item->distances);
837  reportedSome = true;
838  }
839  else
840  {
843  Page page;
844  bool isnull;
845 
846  if (buffer == InvalidBuffer)
847  {
848  buffer = ReadBuffer(index, blkno);
849  LockBuffer(buffer, BUFFER_LOCK_SHARE);
850  }
851  else if (blkno != BufferGetBlockNumber(buffer))
852  {
853  UnlockReleaseBuffer(buffer);
854  buffer = ReadBuffer(index, blkno);
855  LockBuffer(buffer, BUFFER_LOCK_SHARE);
856  }
857 
858  /* else new pointer points to the same page, no work needed */
859 
860  page = BufferGetPage(buffer);
861  TestForOldSnapshot(snapshot, index, page);
862 
863  isnull = SpGistPageStoresNulls(page) ? true : false;
864 
865  if (SpGistPageIsLeaf(page))
866  {
867  /* Page is a leaf - that is, all it's tuples are heap items */
869 
870  if (SpGistBlockIsRoot(blkno))
871  {
872  /* When root is a leaf, examine all its tuples */
873  for (offset = FirstOffsetNumber; offset <= max; offset++)
874  (void) spgTestLeafTuple(so, item, page, offset,
875  isnull, true,
876  &reportedSome, storeRes);
877  }
878  else
879  {
880  /* Normal case: just examine the chain we arrived at */
881  while (offset != InvalidOffsetNumber)
882  {
883  Assert(offset >= FirstOffsetNumber && offset <= max);
884  offset = spgTestLeafTuple(so, item, page, offset,
885  isnull, false,
886  &reportedSome, storeRes);
887  if (offset == SpGistRedirectOffsetNumber)
888  goto redirect;
889  }
890  }
891  }
892  else /* page is inner */
893  {
894  SpGistInnerTuple innerTuple = (SpGistInnerTuple)
895  PageGetItem(page, PageGetItemId(page, offset));
896 
897  if (innerTuple->tupstate != SPGIST_LIVE)
898  {
899  if (innerTuple->tupstate == SPGIST_REDIRECT)
900  {
901  /* transfer attention to redirect point */
902  item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
905  goto redirect;
906  }
907  elog(ERROR, "unexpected SPGiST tuple state: %d",
908  innerTuple->tupstate);
909  }
910 
911  spgInnerTest(so, item, innerTuple, isnull);
912  }
913  }
914 
915  /* done with this scan item */
916  spgFreeSearchItem(so, item);
917  /* clear temp context before proceeding to the next one */
919  }
920 
921  if (buffer != InvalidBuffer)
922  UnlockReleaseBuffer(buffer);
923 }
924 
925 
926 /* storeRes subroutine for getbitmap case */
927 static void
929  Datum leafValue, bool isnull,
930  SpGistLeafTuple leafTuple, bool recheck,
931  bool recheckDistances, double *distances)
932 {
933  Assert(!recheckDistances && !distances);
934  tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
935  so->ntids++;
936 }
937 
938 int64
940 {
942 
943  /* Copy want_itup to *so so we don't need to pass it around separately */
944  so->want_itup = false;
945 
946  so->tbm = tbm;
947  so->ntids = 0;
948 
949  spgWalk(scan->indexRelation, so, true, storeBitmap, scan->xs_snapshot);
950 
951  return so->ntids;
952 }
953 
954 /* storeRes subroutine for gettuple case */
955 static void
957  Datum leafValue, bool isnull,
958  SpGistLeafTuple leafTuple, bool recheck,
959  bool recheckDistances, double *nonNullDistances)
960 {
962  so->heapPtrs[so->nPtrs] = *heapPtr;
963  so->recheck[so->nPtrs] = recheck;
964  so->recheckDistances[so->nPtrs] = recheckDistances;
965 
966  if (so->numberOfOrderBys > 0)
967  {
968  if (isnull || so->numberOfNonNullOrderBys <= 0)
969  so->distances[so->nPtrs] = NULL;
970  else
971  {
972  IndexOrderByDistance *distances =
973  palloc(sizeof(distances[0]) * so->numberOfOrderBys);
974  int i;
975 
976  for (i = 0; i < so->numberOfOrderBys; i++)
977  {
978  int offset = so->nonNullOrderByOffsets[i];
979 
980  if (offset >= 0)
981  {
982  /* Copy non-NULL distance value */
983  distances[i].value = nonNullDistances[offset];
984  distances[i].isnull = false;
985  }
986  else
987  {
988  /* Set distance's NULL flag. */
989  distances[i].value = 0.0;
990  distances[i].isnull = true;
991  }
992  }
993 
994  so->distances[so->nPtrs] = distances;
995  }
996  }
997 
998  if (so->want_itup)
999  {
1000  /*
1001  * Reconstruct index data. We have to copy the datum out of the temp
1002  * context anyway, so we may as well create the tuple here.
1003  */
1004  Datum leafDatums[INDEX_MAX_KEYS];
1005  bool leafIsnulls[INDEX_MAX_KEYS];
1006 
1007  /* We only need to deform the old tuple if it has INCLUDE attributes */
1008  if (so->state.leafTupDesc->natts > 1)
1009  spgDeformLeafTuple(leafTuple, so->state.leafTupDesc,
1010  leafDatums, leafIsnulls, isnull);
1011 
1012  leafDatums[spgKeyColumn] = leafValue;
1013  leafIsnulls[spgKeyColumn] = isnull;
1014 
1016  leafDatums,
1017  leafIsnulls);
1018  }
1019  so->nPtrs++;
1020 }
1021 
1022 bool
1024 {
1026 
1027  if (dir != ForwardScanDirection)
1028  elog(ERROR, "SP-GiST only supports forward scan direction");
1029 
1030  /* Copy want_itup to *so so we don't need to pass it around separately */
1031  so->want_itup = scan->xs_want_itup;
1032 
1033  for (;;)
1034  {
1035  if (so->iPtr < so->nPtrs)
1036  {
1037  /* continuing to return reported tuples */
1038  scan->xs_heaptid = so->heapPtrs[so->iPtr];
1039  scan->xs_recheck = so->recheck[so->iPtr];
1040  scan->xs_hitup = so->reconTups[so->iPtr];
1041 
1042  if (so->numberOfOrderBys > 0)
1044  so->distances[so->iPtr],
1045  so->recheckDistances[so->iPtr]);
1046  so->iPtr++;
1047  return true;
1048  }
1049 
1050  if (so->numberOfOrderBys > 0)
1051  {
1052  /* Must pfree distances to avoid memory leak */
1053  int i;
1054 
1055  for (i = 0; i < so->nPtrs; i++)
1056  if (so->distances[i])
1057  pfree(so->distances[i]);
1058  }
1059 
1060  if (so->want_itup)
1061  {
1062  /* Must pfree reconstructed tuples to avoid memory leak */
1063  int i;
1064 
1065  for (i = 0; i < so->nPtrs; i++)
1066  pfree(so->reconTups[i]);
1067  }
1068  so->iPtr = so->nPtrs = 0;
1069 
1070  spgWalk(scan->indexRelation, so, false, storeGettuple,
1071  scan->xs_snapshot);
1072 
1073  if (so->nPtrs == 0)
1074  break; /* must have completed scan */
1075  }
1076 
1077  return false;
1078 }
1079 
1080 bool
1082 {
1083  SpGistCache *cache;
1084 
1085  /* INCLUDE attributes can always be fetched for index-only scans */
1086  if (attno > 1)
1087  return true;
1088 
1089  /* We can do it if the opclass config function says so */
1090  cache = spgGetCache(index);
1091 
1092  return cache->config.canReturnData;
1093 }
Datum reconstructedValue
Definition: spgist.h:175
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:82
#define SPGIST_DEAD
Datum * spgExtractNodeLabels(SpGistState *state, SpGistInnerTuple innerTuple)
Definition: spgutils.c:1130
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:218
#define AllocSetContextCreate
Definition: memutils.h:173
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:279
SpGistInnerTupleData * SpGistInnerTuple
#define SpGistPageIsLeaf(page)
static float8 get_float8_infinity(void)
Definition: float.h:93
static void storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *distances)
Definition: spgscan.c:928
SpGistCache * spgGetCache(Relation index)
Definition: spgutils.c:178
#define SPGIST_LEAF_CONSISTENT_PROC
Definition: spgist.h:27
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:803
IndexOrderByDistance * distances[MaxIndexTuplesPerPage]
struct ScanKeyData * orderByData
Definition: relscan.h:123
static int pairingheap_SpGistSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
Definition: spgscan.c:40
bool recheckDistances[MaxIndexTuplesPerPage]
bool canReturnData
Definition: spgist.h:46
#define RelationGetDescr(relation)
Definition: rel.h:503
#define SPGIST_REDIRECT
ItemPointerData heapPtrs[MaxIndexTuplesPerPage]
#define PointerGetDatum(X)
Definition: postgres.h:600
pairingheap * scanQueue
#define MaxOffsetNumber
Definition: off.h:28
#define SGITITERATE(x, i, nt)
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:376
struct TupleDescData * xs_hitupdesc
Definition: relscan.h:145
SpGistTypeDesc attLeafType
ItemPointerData t_tid
Definition: itup.h:37
SpGistTypeDesc attType
ScanKey orderbys
Definition: spgist.h:135
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * traversalValue
Definition: spgist.h:141
#define pairingheap_is_empty(h)
Definition: pairingheap.h:96
#define InvalidBuffer
Definition: buf.h:25
static SpGistSearchItem * spgGetNextQueueItem(SpGistScanOpaque so)
Definition: spgscan.c:742
MemoryContext tempCxt
Datum * xs_orderbyvals
Definition: relscan.h:161
void spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: spgscan.c:379
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
struct SnapshotData * xs_snapshot
Definition: relscan.h:119
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:143
uint32 BlockNumber
Definition: block.h:31
HeapTuple heap_form_tuple(TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: heaptuple.c:1020
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1148
unsigned int Oid
Definition: postgres_ext.h:31
#define SPGIST_ROOT_BLKNO
void spgendscan(IndexScanDesc scan)
Definition: spgscan.c:425
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
Datum reconstructedValue
Definition: spgist.h:140
HeapTuple reconTups[MaxIndexTuplesPerPage]
bool spgcanreturn(Relation index, int attno)
Definition: spgscan.c:1081
Oid get_func_rettype(Oid funcid)
Definition: lsyscache.c:1626
Relation indexRelation
Definition: relscan.h:118
uint16 OffsetNumber
Definition: off.h:24
#define SGITDATUM(x, s)
Definition: type.h:89
#define true
Definition: c.h:395
bool * xs_orderbynulls
Definition: relscan.h:162
void pfree(void *pointer)
Definition: mcxt.c:1169
unsigned int allTheSame
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3795
Oid * rd_indcollation
Definition: rel.h:212
MemoryContext traversalMemoryContext
Definition: spgist.h:142
#define ERROR
Definition: elog.h:46
ScanKey orderbys
Definition: spgist.h:170
pairingheap_node phNode
ScanKey scankeys
Definition: spgist.h:169
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:195
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:608
unsigned int prefixSize
#define SizeOfSpGistSearchItem(n_distances)
static OffsetNumber spgTestLeafTuple(SpGistScanOpaque so, SpGistSearchItem *item, Page page, OffsetNumber offset, bool isnull, bool isroot, bool *reportedSome, storeRes_func storeRes)
Definition: spgscan.c:759
struct SpGistLeafTupleData * SpGistLeafTuple
ItemPointerData xs_heaptid
Definition: relscan.h:147
#define SPGIST_NULL_BLKNO
ScanKeyData * ScanKey
Definition: skey.h:75
static SpGistSearchItem * spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances)
Definition: spgscan.c:113
bool recheck[MaxIndexTuplesPerPage]
SpGistLeafTuple leafTuple
#define FirstOffsetNumber
Definition: off.h:27
void(* storeRes_func)(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isNull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *distances)
Definition: spgscan.c:29
double * distances
Definition: spgist.h:188
static void spgPrepareScanKeys(IndexScanDesc scan)
Definition: spgscan.c:207
FmgrInfo sk_func
Definition: skey.h:71
#define SPGIST_METAPAGE_BLKNO
ScanDirection
Definition: sdir.h:22
#define DatumGetBool(X)
Definition: postgres.h:437
void initSpGistState(SpGistState *state, Relation index)
Definition: spgutils.c:318
SpGistDeadTupleData * SpGistDeadTuple
int64 spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: spgscan.c:939
static SpGistSearchItem * spgMakeInnerItem(SpGistScanOpaque so, SpGistSearchItem *parentItem, SpGistNodeTuple tuple, spgInnerConsistentOut *out, int i, bool isnull, double *distances)
Definition: spgscan.c:625
#define SK_SEARCHNOTNULL
Definition: skey.h:122
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
static void spgAddStartItem(SpGistScanOpaque so, bool isnull)
Definition: spgscan.c:129
#define SK_ISNULL
Definition: skey.h:115
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
void ** traversalValues
Definition: spgist.h:160
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:131
static SpGistSearchItem * spgNewHeapItem(SpGistScanOpaque so, int level, SpGistLeafTuple leafTuple, Datum leafValue, bool recheck, bool recheckDistances, bool isnull, double *distances)
Definition: spgscan.c:459
static void spgAddSearchItemToQueue(SpGistScanOpaque so, SpGistSearchItem *item)
Definition: spgscan.c:107
spgConfigOut config
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
#define spgKeyColumn
unsigned int tupstate
void * palloc0(Size size)
Definition: mcxt.c:1093
void index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, IndexOrderByDistance *distances, bool recheckOrderBy)
Definition: indexam.c:871
uintptr_t Datum
Definition: postgres.h:411
double ** distances
Definition: spgist.h:161
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4011
char * deadTupleStorage
SpGistScanOpaqueData * SpGistScanOpaque
static void spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple, bool isnull)
Definition: spgscan.c:663
Datum * nodeLabels
Definition: spgist.h:151
#define InvalidOffsetNumber
Definition: off.h:26
Oid fn_oid
Definition: fmgr.h:59
double distances[FLEXIBLE_ARRAY_MEMBER]
#define SpGistPageStoresNulls(page)
static void spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex, storeRes_func storeRes, Snapshot snapshot)
Definition: spgscan.c:813
ItemPointerData heapPtr
int sk_flags
Definition: skey.h:66
TupleDesc leafTupDesc
#define Assert(condition)
Definition: c.h:804
static void spgInitInnerConsistentIn(spgInnerConsistentIn *in, SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple)
Definition: spgscan.c:602
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:694
#define SpGistBlockIsRoot(blkno)
#define INDEX_MAX_KEYS
#define SPGIST_LIVE
#define SGLTDATUM(x, s)
Datum * reconstructedValues
Definition: spgist.h:159
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
ScanKey scankeys
Definition: spgist.h:134
static void resetSpGistScanOpaque(SpGistScanOpaque so)
Definition: spgscan.c:153
void FreeTupleDesc(TupleDesc tupdesc)
Definition: tupdesc.c:309
#define DatumGetPointer(X)
Definition: postgres.h:593
struct ScanKeyData * keyData
Definition: relscan.h:122
MemoryContext traversalCxt
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2752
#define MaxIndexTuplesPerPage
Definition: itup.h:145
void * palloc(Size size)
Definition: mcxt.c:1062
HeapTuple xs_hitup
Definition: relscan.h:144
TupleDesc getSpGistTupleDesc(Relation index, SpGistTypeDesc *keyType)
Definition: spgutils.c:287
static void storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *nonNullDistances)
Definition: spgscan.c:956
bool spggettuple(IndexScanDesc scan, ScanDirection dir)
Definition: spgscan.c:1023
#define SGLT_GET_NEXTOFFSET(spgLeafTuple)
#define elog(elevel,...)
Definition: elog.h:232
int i
void spgDeformLeafTuple(SpGistLeafTuple tup, TupleDesc tupleDescriptor, Datum *datums, bool *isnulls, bool keyColumnIsNull)
Definition: spgutils.c:1085
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:97
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
Definition: pairingheap.c:145
#define SPGIST_INNER_CONSISTENT_PROC
Definition: spgist.h:26
void * arg
void * traversalValue
Definition: spgist.h:176
static bool spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item, SpGistLeafTuple leafTuple, bool isnull, bool *reportedSome, storeRes_func storeRes)
Definition: spgscan.c:512
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:81
SpGistSpecialOffsetNumbers
Definition: spgscan.c:751
Relation index
IndexScanDesc spgbeginscan(Relation rel, int keysz, int orderbysz)
Definition: spgscan.c:303
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:120
void pairingheap_add(pairingheap *heap, pairingheap_node *node)
Definition: pairingheap.c:112
int numberOfOrderBys
Definition: relscan.h:121
ItemPointerData heapPtr
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
int Buffer
Definition: buf.h:23
#define SK_SEARCHNULL
Definition: skey.h:121
#define PageGetItem(page, itemId)
Definition: bufpage.h:340
Pointer Page
Definition: bufpage.h:78
#define ItemPointerSet(pointer, blockNumber, offNum)
Definition: itemptr.h:127
static void spgFreeSearchItem(SpGistScanOpaque so, SpGistSearchItem *item)
Definition: spgscan.c:83