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  memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
388 
389  /* initialize order-by data if needed */
390  if (orderbys && scan->numberOfOrderBys > 0)
391  {
392  int i;
393 
394  memcpy(scan->orderByData, orderbys, scan->numberOfOrderBys * sizeof(ScanKeyData));
395 
396  for (i = 0; i < scan->numberOfOrderBys; i++)
397  {
398  ScanKey skey = &scan->orderByData[i];
399 
400  /*
401  * Look up the datatype returned by the original ordering
402  * operator. SP-GiST always uses a float8 for the distance
403  * function, but the ordering operator could be anything else.
404  *
405  * XXX: The distance function is only allowed to be lossy if the
406  * ordering operator's result type is float4 or float8. Otherwise
407  * we don't know how to return the distance to the executor. But
408  * we cannot check that here, as we won't know if the distance
409  * function is lossy until it returns *recheck = true for the
410  * first time.
411  */
413  }
414  }
415 
416  /* preprocess scankeys, set up the representation in *so */
417  spgPrepareScanKeys(scan);
418 
419  /* set up starting queue entries */
421 
422  /* count an indexscan for stats */
424 }
425 
426 void
428 {
430 
433 
434  if (so->keyData)
435  pfree(so->keyData);
436 
437  if (so->state.leafTupDesc &&
440 
441  if (so->state.deadTupleStorage)
443 
444  if (scan->numberOfOrderBys > 0)
445  {
446  pfree(so->orderByTypes);
448  pfree(so->zeroDistances);
449  pfree(so->infDistances);
450  pfree(scan->xs_orderbyvals);
451  pfree(scan->xs_orderbynulls);
452  }
453 
454  pfree(so);
455 }
456 
457 /*
458  * Leaf SpGistSearchItem constructor, called in queue context
459  */
460 static SpGistSearchItem *
462  Datum leafValue, bool recheck, bool recheckDistances,
463  bool isnull, double *distances)
464 {
465  SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
466 
467  item->level = level;
468  item->heapPtr = leafTuple->heapPtr;
469 
470  /*
471  * If we need the reconstructed value, copy it to queue cxt out of tmp
472  * cxt. Caution: the leaf_consistent method may not have supplied a value
473  * if we didn't ask it to, and mildly-broken methods might supply one of
474  * the wrong type. The correct leafValue type is attType not leafType.
475  */
476  if (so->want_itup)
477  {
478  item->value = isnull ? (Datum) 0 :
479  datumCopy(leafValue, so->state.attType.attbyval,
480  so->state.attType.attlen);
481 
482  /*
483  * If we're going to need to reconstruct INCLUDE attributes, store the
484  * whole leaf tuple so we can get the INCLUDE attributes out of it.
485  */
486  if (so->state.leafTupDesc->natts > 1)
487  {
488  item->leafTuple = palloc(leafTuple->size);
489  memcpy(item->leafTuple, leafTuple, leafTuple->size);
490  }
491  else
492  item->leafTuple = NULL;
493  }
494  else
495  {
496  item->value = (Datum) 0;
497  item->leafTuple = NULL;
498  }
499  item->traversalValue = NULL;
500  item->isLeaf = true;
501  item->recheck = recheck;
502  item->recheckDistances = recheckDistances;
503 
504  return item;
505 }
506 
507 /*
508  * Test whether a leaf tuple satisfies all the scan keys
509  *
510  * *reportedSome is set to true if:
511  * the scan is not ordered AND the item satisfies the scankeys
512  */
513 static bool
515  SpGistLeafTuple leafTuple, bool isnull,
516  bool *reportedSome, storeRes_func storeRes)
517 {
518  Datum leafValue;
519  double *distances;
520  bool result;
521  bool recheck;
522  bool recheckDistances;
523 
524  if (isnull)
525  {
526  /* Should not have arrived on a nulls page unless nulls are wanted */
527  Assert(so->searchNulls);
528  leafValue = (Datum) 0;
529  distances = NULL;
530  recheck = false;
531  recheckDistances = false;
532  result = true;
533  }
534  else
535  {
538 
539  /* use temp context for calling leaf_consistent */
541 
542  in.scankeys = so->keyData;
543  in.nkeys = so->numberOfKeys;
544  in.orderbys = so->orderByData;
546  Assert(!item->isLeaf); /* else reconstructedValue would be wrong type */
547  in.reconstructedValue = item->value;
548  in.traversalValue = item->traversalValue;
549  in.level = item->level;
550  in.returnData = so->want_itup;
551  in.leafDatum = SGLTDATUM(leafTuple, &so->state);
552 
553  out.leafValue = (Datum) 0;
554  out.recheck = false;
555  out.distances = NULL;
556  out.recheckDistances = false;
557 
559  so->indexCollation,
560  PointerGetDatum(&in),
561  PointerGetDatum(&out)));
562  recheck = out.recheck;
563  recheckDistances = out.recheckDistances;
564  leafValue = out.leafValue;
565  distances = out.distances;
566 
567  MemoryContextSwitchTo(oldCxt);
568  }
569 
570  if (result)
571  {
572  /* item passes the scankeys */
573  if (so->numberOfNonNullOrderBys > 0)
574  {
575  /* the scan is ordered -> add the item to the queue */
577  SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
578  leafTuple,
579  leafValue,
580  recheck,
581  recheckDistances,
582  isnull,
583  distances);
584 
585  spgAddSearchItemToQueue(so, heapItem);
586 
587  MemoryContextSwitchTo(oldCxt);
588  }
589  else
590  {
591  /* non-ordered scan, so report the item right away */
592  Assert(!recheckDistances);
593  storeRes(so, &leafTuple->heapPtr, leafValue, isnull,
594  leafTuple, recheck, false, NULL);
595  *reportedSome = true;
596  }
597  }
598 
599  return result;
600 }
601 
602 /* A bundle initializer for inner_consistent methods */
603 static void
605  SpGistScanOpaque so,
606  SpGistSearchItem *item,
607  SpGistInnerTuple innerTuple)
608 {
609  in->scankeys = so->keyData;
610  in->orderbys = so->orderByData;
611  in->nkeys = so->numberOfKeys;
613  Assert(!item->isLeaf); /* else reconstructedValue would be wrong type */
614  in->reconstructedValue = item->value;
616  in->traversalValue = item->traversalValue;
617  in->level = item->level;
618  in->returnData = so->want_itup;
619  in->allTheSame = innerTuple->allTheSame;
620  in->hasPrefix = (innerTuple->prefixSize > 0);
621  in->prefixDatum = SGITDATUM(innerTuple, &so->state);
622  in->nNodes = innerTuple->nNodes;
623  in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
624 }
625 
626 static SpGistSearchItem *
628  SpGistSearchItem *parentItem,
629  SpGistNodeTuple tuple,
630  spgInnerConsistentOut *out, int i, bool isnull,
631  double *distances)
632 {
633  SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
634 
635  item->heapPtr = tuple->t_tid;
636  item->level = out->levelAdds ? parentItem->level + out->levelAdds[i]
637  : parentItem->level;
638 
639  /* Must copy value out of temp context */
640  /* (recall that reconstructed values are of type leafType) */
641  item->value = out->reconstructedValues
645  : (Datum) 0;
646 
647  item->leafTuple = NULL;
648 
649  /*
650  * Elements of out.traversalValues should be allocated in
651  * in.traversalMemoryContext, which is actually a long lived context of
652  * index scan.
653  */
654  item->traversalValue =
655  out->traversalValues ? out->traversalValues[i] : NULL;
656 
657  item->isLeaf = false;
658  item->recheck = false;
659  item->recheckDistances = false;
660 
661  return item;
662 }
663 
664 static void
666  SpGistInnerTuple innerTuple, bool isnull)
667 {
670  int nNodes = innerTuple->nNodes;
671  int i;
672 
673  memset(&out, 0, sizeof(out));
674 
675  if (!isnull)
676  {
678 
679  spgInitInnerConsistentIn(&in, so, item, innerTuple);
680 
681  /* use user-defined inner consistent method */
683  so->indexCollation,
684  PointerGetDatum(&in),
685  PointerGetDatum(&out));
686  }
687  else
688  {
689  /* force all children to be visited */
690  out.nNodes = nNodes;
691  out.nodeNumbers = (int *) palloc(sizeof(int) * nNodes);
692  for (i = 0; i < nNodes; i++)
693  out.nodeNumbers[i] = i;
694  }
695 
696  /* If allTheSame, they should all or none of them match */
697  if (innerTuple->allTheSame && out.nNodes != 0 && out.nNodes != nNodes)
698  elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
699 
700  if (out.nNodes)
701  {
702  /* collect node pointers */
703  SpGistNodeTuple node;
704  SpGistNodeTuple *nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * nNodes);
705 
706  SGITITERATE(innerTuple, i, node)
707  {
708  nodes[i] = node;
709  }
710 
712 
713  for (i = 0; i < out.nNodes; i++)
714  {
715  int nodeN = out.nodeNumbers[i];
716  SpGistSearchItem *innerItem;
717  double *distances;
718 
719  Assert(nodeN >= 0 && nodeN < nNodes);
720 
721  node = nodes[nodeN];
722 
723  if (!ItemPointerIsValid(&node->t_tid))
724  continue;
725 
726  /*
727  * Use infinity distances if innerConsistentFn() failed to return
728  * them or if is a NULL item (their distances are really unused).
729  */
730  distances = out.distances ? out.distances[i] : so->infDistances;
731 
732  innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull,
733  distances);
734 
735  spgAddSearchItemToQueue(so, innerItem);
736  }
737  }
738 
739  MemoryContextSwitchTo(oldCxt);
740 }
741 
742 /* Returns a next item in an (ordered) scan or null if the index is exhausted */
743 static SpGistSearchItem *
745 {
747  return NULL; /* Done when both heaps are empty */
748 
749  /* Return item; caller is responsible to pfree it */
751 }
752 
754 {
758 };
759 
760 static OffsetNumber
762  SpGistSearchItem *item,
763  Page page, OffsetNumber offset,
764  bool isnull, bool isroot,
765  bool *reportedSome,
766  storeRes_func storeRes)
767 {
768  SpGistLeafTuple leafTuple = (SpGistLeafTuple)
769  PageGetItem(page, PageGetItemId(page, offset));
770 
771  if (leafTuple->tupstate != SPGIST_LIVE)
772  {
773  if (!isroot) /* all tuples on root should be live */
774  {
775  if (leafTuple->tupstate == SPGIST_REDIRECT)
776  {
777  /* redirection tuple should be first in chain */
778  Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
779  /* transfer attention to redirect point */
780  item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer;
783  }
784 
785  if (leafTuple->tupstate == SPGIST_DEAD)
786  {
787  /* dead tuple should be first in chain */
788  Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
789  /* No live entries on this page */
792  }
793  }
794 
795  /* We should not arrive at a placeholder */
796  elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate);
798  }
799 
800  Assert(ItemPointerIsValid(&leafTuple->heapPtr));
801 
802  spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes);
803 
804  return SGLT_GET_NEXTOFFSET(leafTuple);
805 }
806 
807 /*
808  * Walk the tree and report all tuples passing the scan quals to the storeRes
809  * subroutine.
810  *
811  * If scanWholeIndex is true, we'll do just that. If not, we'll stop at the
812  * next page boundary once we have reported at least one tuple.
813  */
814 static void
815 spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex,
816  storeRes_func storeRes)
817 {
818  Buffer buffer = InvalidBuffer;
819  bool reportedSome = false;
820 
821  while (scanWholeIndex || !reportedSome)
822  {
824 
825  if (item == NULL)
826  break; /* No more items in queue -> done */
827 
828 redirect:
829  /* Check for interrupts, just in case of infinite loop */
831 
832  if (item->isLeaf)
833  {
834  /* We store heap items in the queue only in case of ordered search */
836  storeRes(so, &item->heapPtr, item->value, item->isNull,
837  item->leafTuple, item->recheck,
838  item->recheckDistances, item->distances);
839  reportedSome = true;
840  }
841  else
842  {
845  Page page;
846  bool isnull;
847 
848  if (buffer == InvalidBuffer)
849  {
850  buffer = ReadBuffer(index, blkno);
851  LockBuffer(buffer, BUFFER_LOCK_SHARE);
852  }
853  else if (blkno != BufferGetBlockNumber(buffer))
854  {
855  UnlockReleaseBuffer(buffer);
856  buffer = ReadBuffer(index, blkno);
857  LockBuffer(buffer, BUFFER_LOCK_SHARE);
858  }
859 
860  /* else new pointer points to the same page, no work needed */
861 
862  page = BufferGetPage(buffer);
863 
864  isnull = SpGistPageStoresNulls(page) ? true : false;
865 
866  if (SpGistPageIsLeaf(page))
867  {
868  /* Page is a leaf - that is, all it's tuples are heap items */
870 
871  if (SpGistBlockIsRoot(blkno))
872  {
873  /* When root is a leaf, examine all its tuples */
874  for (offset = FirstOffsetNumber; offset <= max; offset++)
875  (void) spgTestLeafTuple(so, item, page, offset,
876  isnull, true,
877  &reportedSome, storeRes);
878  }
879  else
880  {
881  /* Normal case: just examine the chain we arrived at */
882  while (offset != InvalidOffsetNumber)
883  {
884  Assert(offset >= FirstOffsetNumber && offset <= max);
885  offset = spgTestLeafTuple(so, item, page, offset,
886  isnull, false,
887  &reportedSome, storeRes);
888  if (offset == SpGistRedirectOffsetNumber)
889  goto redirect;
890  }
891  }
892  }
893  else /* page is inner */
894  {
895  SpGistInnerTuple innerTuple = (SpGistInnerTuple)
896  PageGetItem(page, PageGetItemId(page, offset));
897 
898  if (innerTuple->tupstate != SPGIST_LIVE)
899  {
900  if (innerTuple->tupstate == SPGIST_REDIRECT)
901  {
902  /* transfer attention to redirect point */
903  item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
906  goto redirect;
907  }
908  elog(ERROR, "unexpected SPGiST tuple state: %d",
909  innerTuple->tupstate);
910  }
911 
912  spgInnerTest(so, item, innerTuple, isnull);
913  }
914  }
915 
916  /* done with this scan item */
917  spgFreeSearchItem(so, item);
918  /* clear temp context before proceeding to the next one */
920  }
921 
922  if (buffer != InvalidBuffer)
923  UnlockReleaseBuffer(buffer);
924 }
925 
926 
927 /* storeRes subroutine for getbitmap case */
928 static void
930  Datum leafValue, bool isnull,
931  SpGistLeafTuple leafTuple, bool recheck,
932  bool recheckDistances, double *distances)
933 {
934  Assert(!recheckDistances && !distances);
935  tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
936  so->ntids++;
937 }
938 
939 int64
941 {
943 
944  /* Copy want_itup to *so so we don't need to pass it around separately */
945  so->want_itup = false;
946 
947  so->tbm = tbm;
948  so->ntids = 0;
949 
950  spgWalk(scan->indexRelation, so, true, storeBitmap);
951 
952  return so->ntids;
953 }
954 
955 /* storeRes subroutine for gettuple case */
956 static void
958  Datum leafValue, bool isnull,
959  SpGistLeafTuple leafTuple, bool recheck,
960  bool recheckDistances, double *nonNullDistances)
961 {
963  so->heapPtrs[so->nPtrs] = *heapPtr;
964  so->recheck[so->nPtrs] = recheck;
965  so->recheckDistances[so->nPtrs] = recheckDistances;
966 
967  if (so->numberOfOrderBys > 0)
968  {
969  if (isnull || so->numberOfNonNullOrderBys <= 0)
970  so->distances[so->nPtrs] = NULL;
971  else
972  {
973  IndexOrderByDistance *distances =
974  palloc(sizeof(distances[0]) * so->numberOfOrderBys);
975  int i;
976 
977  for (i = 0; i < so->numberOfOrderBys; i++)
978  {
979  int offset = so->nonNullOrderByOffsets[i];
980 
981  if (offset >= 0)
982  {
983  /* Copy non-NULL distance value */
984  distances[i].value = nonNullDistances[offset];
985  distances[i].isnull = false;
986  }
987  else
988  {
989  /* Set distance's NULL flag. */
990  distances[i].value = 0.0;
991  distances[i].isnull = true;
992  }
993  }
994 
995  so->distances[so->nPtrs] = distances;
996  }
997  }
998 
999  if (so->want_itup)
1000  {
1001  /*
1002  * Reconstruct index data. We have to copy the datum out of the temp
1003  * context anyway, so we may as well create the tuple here.
1004  */
1005  Datum leafDatums[INDEX_MAX_KEYS];
1006  bool leafIsnulls[INDEX_MAX_KEYS];
1007 
1008  /* We only need to deform the old tuple if it has INCLUDE attributes */
1009  if (so->state.leafTupDesc->natts > 1)
1010  spgDeformLeafTuple(leafTuple, so->state.leafTupDesc,
1011  leafDatums, leafIsnulls, isnull);
1012 
1013  leafDatums[spgKeyColumn] = leafValue;
1014  leafIsnulls[spgKeyColumn] = isnull;
1015 
1017  leafDatums,
1018  leafIsnulls);
1019  }
1020  so->nPtrs++;
1021 }
1022 
1023 bool
1025 {
1027 
1028  if (dir != ForwardScanDirection)
1029  elog(ERROR, "SP-GiST only supports forward scan direction");
1030 
1031  /* Copy want_itup to *so so we don't need to pass it around separately */
1032  so->want_itup = scan->xs_want_itup;
1033 
1034  for (;;)
1035  {
1036  if (so->iPtr < so->nPtrs)
1037  {
1038  /* continuing to return reported tuples */
1039  scan->xs_heaptid = so->heapPtrs[so->iPtr];
1040  scan->xs_recheck = so->recheck[so->iPtr];
1041  scan->xs_hitup = so->reconTups[so->iPtr];
1042 
1043  if (so->numberOfOrderBys > 0)
1045  so->distances[so->iPtr],
1046  so->recheckDistances[so->iPtr]);
1047  so->iPtr++;
1048  return true;
1049  }
1050 
1051  if (so->numberOfOrderBys > 0)
1052  {
1053  /* Must pfree distances to avoid memory leak */
1054  int i;
1055 
1056  for (i = 0; i < so->nPtrs; i++)
1057  if (so->distances[i])
1058  pfree(so->distances[i]);
1059  }
1060 
1061  if (so->want_itup)
1062  {
1063  /* Must pfree reconstructed tuples to avoid memory leak */
1064  int i;
1065 
1066  for (i = 0; i < so->nPtrs; i++)
1067  pfree(so->reconTups[i]);
1068  }
1069  so->iPtr = so->nPtrs = 0;
1070 
1071  spgWalk(scan->indexRelation, so, false, storeGettuple);
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 }
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:3706
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4923
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:5140
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:746
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:190
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:400
Pointer Page
Definition: bufpage.h:81
static Item PageGetItem(Page page, ItemId itemId)
Definition: bufpage.h:354
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:243
static OffsetNumber PageGetMaxOffsetNumber(Page page)
Definition: bufpage.h:372
#define Assert(condition)
Definition: c.h:858
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
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:860
void index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, IndexOrderByDistance *distances, bool recheckOrderBy)
Definition: indexam.c:928
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
Oid get_func_rettype(Oid funcid)
Definition: lsyscache.c:1655
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:383
void pfree(void *pointer)
Definition: mcxt.c:1521
void * palloc0(Size size)
Definition: mcxt.c:1347
MemoryContext CurrentMemoryContext
Definition: mcxt.c:143
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:454
void * palloc(Size size)
Definition: mcxt.c:1317
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:160
#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:126
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
Definition: pairingheap.c:159
#define pairingheap_is_empty(h)
Definition: pairingheap.h:99
void * arg
#define INDEX_MAX_KEYS
#define pgstat_count_index_scan(rel)
Definition: pgstat.h:658
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
MemoryContextSwitchTo(old_ctx)
#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:1081
bool spggettuple(IndexScanDesc scan, ScanDirection dir)
Definition: spgscan.c:1024
static void spgInitInnerConsistentIn(spgInnerConsistentIn *in, SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple)
Definition: spgscan.c:604
static void spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex, storeRes_func storeRes)
Definition: spgscan.c:815
void spgendscan(IndexScanDesc scan)
Definition: spgscan.c:427
static SpGistSearchItem * spgGetNextQueueItem(SpGistScanOpaque so)
Definition: spgscan.c:744
static OffsetNumber spgTestLeafTuple(SpGistScanOpaque so, SpGistSearchItem *item, Page page, OffsetNumber offset, bool isnull, bool isroot, bool *reportedSome, storeRes_func storeRes)
Definition: spgscan.c:761
static bool spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item, SpGistLeafTuple leafTuple, bool isnull, bool *reportedSome, storeRes_func storeRes)
Definition: spgscan.c:514
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:754
@ SpGistErrorOffsetNumber
Definition: spgscan.c:757
@ SpGistBreakOffsetNumber
Definition: spgscan.c:755
@ SpGistRedirectOffsetNumber
Definition: spgscan.c:756
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:461
static void storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *nonNullDistances)
Definition: spgscan.c:957
static SpGistSearchItem * spgMakeInnerItem(SpGistScanOpaque so, SpGistSearchItem *parentItem, SpGistNodeTuple tuple, spgInnerConsistentOut *out, int i, bool isnull, double *distances)
Definition: spgscan.c:627
static void storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, SpGistLeafTuple leafTuple, bool recheck, bool recheckDistances, double *distances)
Definition: spgscan.c:929
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:940
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:665
Datum * spgExtractNodeLabels(SpGistState *state, SpGistInnerTuple innerTuple)
Definition: spgutils.c:1153
void initSpGistState(SpGistState *state, Relation index)
Definition: spgutils.c:341
TupleDesc getSpGistTupleDesc(Relation index, SpGistTypeDesc *keyType)
Definition: spgutils.c:310
void spgDeformLeafTuple(SpGistLeafTuple tup, TupleDesc tupleDescriptor, Datum *datums, bool *isnulls, bool keyColumnIsNull)
Definition: spgutils.c:1108
SpGistCache * spgGetCache(Relation index)
Definition: spgutils.c:183
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