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-2024, 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 
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
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)
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 
866  isnull = SpGistPageStoresNulls(page) ? true : false;
867 
868  if (SpGistPageIsLeaf(page))
869  {
870  /* Page is a leaf - that is, all it's tuples are heap items */
872 
873  if (SpGistBlockIsRoot(blkno))
874  {
875  /* When root is a leaf, examine all its tuples */
876  for (offset = FirstOffsetNumber; offset <= max; offset++)
877  (void) spgTestLeafTuple(so, item, page, offset,
878  isnull, true,
879  &reportedSome, storeRes);
880  }
881  else
882  {
883  /* Normal case: just examine the chain we arrived at */
884  while (offset != InvalidOffsetNumber)
885  {
886  Assert(offset >= FirstOffsetNumber && offset <= max);
887  offset = spgTestLeafTuple(so, item, page, offset,
888  isnull, false,
889  &reportedSome, storeRes);
890  if (offset == SpGistRedirectOffsetNumber)
891  goto redirect;
892  }
893  }
894  }
895  else /* page is inner */
896  {
897  SpGistInnerTuple innerTuple = (SpGistInnerTuple)
898  PageGetItem(page, PageGetItemId(page, offset));
899 
900  if (innerTuple->tupstate != SPGIST_LIVE)
901  {
902  if (innerTuple->tupstate == SPGIST_REDIRECT)
903  {
904  /* transfer attention to redirect point */
905  item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
908  goto redirect;
909  }
910  elog(ERROR, "unexpected SPGiST tuple state: %d",
911  innerTuple->tupstate);
912  }
913 
914  spgInnerTest(so, item, innerTuple, isnull);
915  }
916  }
917 
918  /* done with this scan item */
919  spgFreeSearchItem(so, item);
920  /* clear temp context before proceeding to the next one */
922  }
923 
924  if (buffer != InvalidBuffer)
925  UnlockReleaseBuffer(buffer);
926 }
927 
928 
929 /* storeRes subroutine for getbitmap case */
930 static void
932  Datum leafValue, bool isnull,
933  SpGistLeafTuple leafTuple, bool recheck,
934  bool recheckDistances, double *distances)
935 {
936  Assert(!recheckDistances && !distances);
937  tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
938  so->ntids++;
939 }
940 
941 int64
943 {
945 
946  /* Copy want_itup to *so so we don't need to pass it around separately */
947  so->want_itup = false;
948 
949  so->tbm = tbm;
950  so->ntids = 0;
951 
952  spgWalk(scan->indexRelation, so, true, storeBitmap);
953 
954  return so->ntids;
955 }
956 
957 /* storeRes subroutine for gettuple case */
958 static void
960  Datum leafValue, bool isnull,
961  SpGistLeafTuple leafTuple, bool recheck,
962  bool recheckDistances, double *nonNullDistances)
963 {
965  so->heapPtrs[so->nPtrs] = *heapPtr;
966  so->recheck[so->nPtrs] = recheck;
967  so->recheckDistances[so->nPtrs] = recheckDistances;
968 
969  if (so->numberOfOrderBys > 0)
970  {
971  if (isnull || so->numberOfNonNullOrderBys <= 0)
972  so->distances[so->nPtrs] = NULL;
973  else
974  {
975  IndexOrderByDistance *distances =
976  palloc(sizeof(distances[0]) * so->numberOfOrderBys);
977  int i;
978 
979  for (i = 0; i < so->numberOfOrderBys; i++)
980  {
981  int offset = so->nonNullOrderByOffsets[i];
982 
983  if (offset >= 0)
984  {
985  /* Copy non-NULL distance value */
986  distances[i].value = nonNullDistances[offset];
987  distances[i].isnull = false;
988  }
989  else
990  {
991  /* Set distance's NULL flag. */
992  distances[i].value = 0.0;
993  distances[i].isnull = true;
994  }
995  }
996 
997  so->distances[so->nPtrs] = distances;
998  }
999  }
1000 
1001  if (so->want_itup)
1002  {
1003  /*
1004  * Reconstruct index data. We have to copy the datum out of the temp
1005  * context anyway, so we may as well create the tuple here.
1006  */
1007  Datum leafDatums[INDEX_MAX_KEYS];
1008  bool leafIsnulls[INDEX_MAX_KEYS];
1009 
1010  /* We only need to deform the old tuple if it has INCLUDE attributes */
1011  if (so->state.leafTupDesc->natts > 1)
1012  spgDeformLeafTuple(leafTuple, so->state.leafTupDesc,
1013  leafDatums, leafIsnulls, isnull);
1014 
1015  leafDatums[spgKeyColumn] = leafValue;
1016  leafIsnulls[spgKeyColumn] = isnull;
1017 
1019  leafDatums,
1020  leafIsnulls);
1021  }
1022  so->nPtrs++;
1023 }
1024 
1025 bool
1027 {
1029 
1030  if (dir != ForwardScanDirection)
1031  elog(ERROR, "SP-GiST only supports forward scan direction");
1032 
1033  /* Copy want_itup to *so so we don't need to pass it around separately */
1034  so->want_itup = scan->xs_want_itup;
1035 
1036  for (;;)
1037  {
1038  if (so->iPtr < so->nPtrs)
1039  {
1040  /* continuing to return reported tuples */
1041  scan->xs_heaptid = so->heapPtrs[so->iPtr];
1042  scan->xs_recheck = so->recheck[so->iPtr];
1043  scan->xs_hitup = so->reconTups[so->iPtr];
1044 
1045  if (so->numberOfOrderBys > 0)
1047  so->distances[so->iPtr],
1048  so->recheckDistances[so->iPtr]);
1049  so->iPtr++;
1050  return true;
1051  }
1052 
1053  if (so->numberOfOrderBys > 0)
1054  {
1055  /* Must pfree distances to avoid memory leak */
1056  int i;
1057 
1058  for (i = 0; i < so->nPtrs; i++)
1059  if (so->distances[i])
1060  pfree(so->distances[i]);
1061  }
1062 
1063  if (so->want_itup)
1064  {
1065  /* Must pfree reconstructed tuples to avoid memory leak */
1066  int i;
1067 
1068  for (i = 0; i < so->nPtrs; i++)
1069  pfree(so->reconTups[i]);
1070  }
1071  so->iPtr = so->nPtrs = 0;
1072 
1073  spgWalk(scan->indexRelation, so, false, storeGettuple);
1074 
1075  if (so->nPtrs == 0)
1076  break; /* must have completed scan */
1077  }
1078 
1079  return false;
1080 }
1081 
1082 bool
1084 {
1085  SpGistCache *cache;
1086 
1087  /* INCLUDE attributes can always be fetched for index-only scans */
1088  if (attno > 1)
1089  return true;
1090 
1091  /* We can do it if the opclass config function says so */
1092  cache = spgGetCache(index);
1093 
1094  return cache->config.canReturnData;
1095 }
uint32 BlockNumber
Definition: block.h:31
int Buffer
Definition: buf.h:23
#define InvalidBuffer
Definition: buf.h:25
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:3377
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4577
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4795
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:734
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:158
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:350
Pointer Page
Definition: bufpage.h:78
static Item PageGetItem(Page page, ItemId itemId)
Definition: bufpage.h:351
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:240
static OffsetNumber PageGetMaxOffsetNumber(Page page)
Definition: bufpage.h:369
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
static float8 get_float8_infinity(void)
Definition: float.h:94
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1149
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:580
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:78
HeapTuple heap_form_tuple(TupleDesc tupleDescriptor, const Datum *values, const bool *isnull)
Definition: heaptuple.c:1116
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:863
void index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, IndexOrderByDistance *distances, bool recheckOrderBy)
Definition: indexam.c:931
int b
Definition: isn.c:70
return true
Definition: isn.c:126
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
static void ItemPointerSet(ItemPointerData *pointer, BlockNumber blockNumber, OffsetNumber offNum)
Definition: itemptr.h:135
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
static bool ItemPointerIsValid(const ItemPointerData *pointer)
Definition: itemptr.h:83
#define MaxIndexTuplesPerPage
Definition: itup.h:165
Assert(fmt[strlen(fmt) - 1] !='\n')
Oid get_func_rettype(Oid funcid)
Definition: lsyscache.c:1633
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:371
void pfree(void *pointer)
Definition: mcxt.c:1508
void * palloc0(Size size)
Definition: mcxt.c:1334
MemoryContext CurrentMemoryContext
Definition: mcxt.c:131
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:442
void * palloc(Size size)
Definition: mcxt.c:1304
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:153
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
#define InvalidOffsetNumber
Definition: off.h:26
uint16 OffsetNumber
Definition: off.h:24
#define FirstOffsetNumber
Definition: off.h:27
#define MaxOffsetNumber
Definition: off.h:28
void pairingheap_add(pairingheap *heap, pairingheap_node *node)
Definition: pairingheap.c:112
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
Definition: pairingheap.c:145
#define pairingheap_is_empty(h)
Definition: pairingheap.h:96
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
void * arg
#define INDEX_MAX_KEYS
#define pgstat_count_index_scan(rel)
Definition: pgstat.h:625
static bool DatumGetBool(Datum X)
Definition: postgres.h:90
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
uintptr_t Datum
Definition: postgres.h:64
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
unsigned int Oid
Definition: postgres_ext.h:31
#define RelationGetDescr(relation)
Definition: rel.h:531
ScanDirection
Definition: sdir.h:25
@ ForwardScanDirection
Definition: sdir.h:28
#define SK_SEARCHNOTNULL
Definition: skey.h:122
#define SK_SEARCHNULL
Definition: skey.h:121
ScanKeyData * ScanKey
Definition: skey.h:75
#define SK_ISNULL
Definition: skey.h:115
#define SPGIST_LEAF_CONSISTENT_PROC
Definition: spgist.h:27
#define SPGIST_INNER_CONSISTENT_PROC
Definition: spgist.h:26
#define SGLTDATUM(x, s)
#define SPGIST_NULL_BLKNO
SpGistDeadTupleData * SpGistDeadTuple
#define SPGIST_REDIRECT
SpGistInnerTupleData * SpGistInnerTuple
#define SPGIST_LIVE
#define SpGistPageStoresNulls(page)
#define SGITDATUM(x, s)
#define SGLT_GET_NEXTOFFSET(spgLeafTuple)
#define SizeOfSpGistSearchItem(n_distances)
#define SGITITERATE(x, i, nt)
SpGistScanOpaqueData * SpGistScanOpaque
#define SPGIST_DEAD
#define SpGistPageIsLeaf(page)
#define SPGIST_METAPAGE_BLKNO
#define SpGistBlockIsRoot(blkno)
struct SpGistLeafTupleData * SpGistLeafTuple
#define spgKeyColumn
#define SPGIST_ROOT_BLKNO
IndexScanDesc spgbeginscan(Relation rel, int keysz, int orderbysz)
Definition: spgscan.c:304
static int pairingheap_SpGistSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
Definition: spgscan.c:41
bool spgcanreturn(Relation index, int attno)
Definition: spgscan.c:1083
bool spggettuple(IndexScanDesc scan, ScanDirection dir)
Definition: spgscan.c:1026
static void spgInitInnerConsistentIn(spgInnerConsistentIn *in, SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple)
Definition: spgscan.c:606
static void spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex, storeRes_func storeRes)
Definition: spgscan.c:817
void spgendscan(IndexScanDesc scan)
Definition: spgscan.c:429
static SpGistSearchItem * spgGetNextQueueItem(SpGistScanOpaque so)
Definition: spgscan.c:746
static OffsetNumber spgTestLeafTuple(SpGistScanOpaque so, SpGistSearchItem *item, Page page, OffsetNumber offset, bool isnull, bool isroot, bool *reportedSome, storeRes_func storeRes)
Definition: spgscan.c:763
static bool spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item, SpGistLeafTuple leafTuple, bool isnull, bool *reportedSome, storeRes_func storeRes)
Definition: spgscan.c:516
static void spgAddStartItem(SpGistScanOpaque so, bool isnull)
Definition: spgscan.c:130
static void spgFreeSearchItem(SpGistScanOpaque so, SpGistSearchItem *item)
Definition: spgscan.c:84
SpGistSpecialOffsetNumbers
Definition: spgscan.c:756
@ SpGistErrorOffsetNumber
Definition: spgscan.c:759
@ SpGistBreakOffsetNumber
Definition: spgscan.c:757
@ SpGistRedirectOffsetNumber
Definition: spgscan.c:758
static void resetSpGistScanOpaque(SpGistScanOpaque so)
Definition: spgscan.c:154
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 storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *nonNullDistances)
Definition: spgscan.c:959
static SpGistSearchItem * spgMakeInnerItem(SpGistScanOpaque so, SpGistSearchItem *parentItem, SpGistNodeTuple tuple, spgInnerConsistentOut *out, int i, bool isnull, double *distances)
Definition: spgscan.c:629
static void storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *distances)
Definition: spgscan.c:931
void spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: spgscan.c:380
int64 spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: spgscan.c:942
static void spgPrepareScanKeys(IndexScanDesc scan)
Definition: spgscan.c:208
static void spgAddSearchItemToQueue(SpGistScanOpaque so, SpGistSearchItem *item)
Definition: spgscan.c:108
static SpGistSearchItem * spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances)
Definition: spgscan.c:114
void(* storeRes_func)(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isNull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *distances)
Definition: spgscan.c:30
static void spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple, bool isnull)
Definition: spgscan.c:667
Datum * spgExtractNodeLabels(SpGistState *state, SpGistInnerTuple innerTuple)
Definition: spgutils.c:1142
void initSpGistState(SpGistState *state, Relation index)
Definition: spgutils.c:340
TupleDesc getSpGistTupleDesc(Relation index, SpGistTypeDesc *keyType)
Definition: spgutils.c:309
void spgDeformLeafTuple(SpGistLeafTuple tup, TupleDesc tupleDescriptor, Datum *datums, bool *isnulls, bool keyColumnIsNull)
Definition: spgutils.c:1097
SpGistCache * spgGetCache(Relation index)
Definition: spgutils.c:182
Oid fn_oid
Definition: fmgr.h:59
struct ScanKeyData * keyData
Definition: relscan.h:122
struct ScanKeyData * orderByData
Definition: relscan.h:123
HeapTuple xs_hitup
Definition: relscan.h:144
bool * xs_orderbynulls
Definition: relscan.h:162
int numberOfOrderBys
Definition: relscan.h:121
struct TupleDescData * xs_hitupdesc
Definition: relscan.h:145
Relation indexRelation
Definition: relscan.h:118
ItemPointerData xs_heaptid
Definition: relscan.h:147
Datum * xs_orderbyvals
Definition: relscan.h:161
ItemPointerData t_tid
Definition: itup.h:37
Oid * rd_indcollation
Definition: rel.h:217
int sk_flags
Definition: skey.h:66
FmgrInfo sk_func
Definition: skey.h:71
spgConfigOut config
unsigned int prefixSize
unsigned int allTheSame
unsigned int tupstate
ItemPointerData heapPtr
HeapTuple reconTups[MaxIndexTuplesPerPage]
ItemPointerData heapPtrs[MaxIndexTuplesPerPage]
MemoryContext traversalCxt
pairingheap * scanQueue
bool recheckDistances[MaxIndexTuplesPerPage]
MemoryContext tempCxt
IndexOrderByDistance * distances[MaxIndexTuplesPerPage]
bool recheck[MaxIndexTuplesPerPage]
pairingheap_node phNode
SpGistLeafTuple leafTuple
ItemPointerData heapPtr
double distances[FLEXIBLE_ARRAY_MEMBER]
Relation index
SpGistTypeDesc attType
TupleDesc leafTupDesc
char * deadTupleStorage
SpGistTypeDesc attLeafType
Definition: type.h:95
bool canReturnData
Definition: spgist.h:46
Datum reconstructedValue
Definition: spgist.h:140
void * traversalValue
Definition: spgist.h:141
ScanKey scankeys
Definition: spgist.h:134
ScanKey orderbys
Definition: spgist.h:135
MemoryContext traversalMemoryContext
Definition: spgist.h:142
Datum * nodeLabels
Definition: spgist.h:151
void ** traversalValues
Definition: spgist.h:160
double ** distances
Definition: spgist.h:161
Datum * reconstructedValues
Definition: spgist.h:159
ScanKey scankeys
Definition: spgist.h:169
Datum reconstructedValue
Definition: spgist.h:175
ScanKey orderbys
Definition: spgist.h:170
void * traversalValue
Definition: spgist.h:176
double * distances
Definition: spgist.h:188
void tbm_add_tuples(TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
Definition: tidbitmap.c:377
void FreeTupleDesc(TupleDesc tupdesc)
Definition: tupdesc.c:331