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