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