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-2019, 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->numberOfOrderBys; 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->numberOfOrderBys > 0)
115  memcpy(item->distances, distances,
116  so->numberOfOrderBys * sizeof(double));
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 (scan->numberOfKeys <= 0)
212  {
213  /* If no quals, whole-index scan is required */
214  so->searchNulls = true;
215  so->searchNonNulls = true;
216  so->numberOfKeys = 0;
217  return;
218  }
219 
220  /* Examine the given quals */
221  qual_ok = true;
222  haveIsNull = haveNotNull = false;
223  nkeys = 0;
224  for (i = 0; i < scan->numberOfKeys; i++)
225  {
226  ScanKey skey = &scan->keyData[i];
227 
228  if (skey->sk_flags & SK_SEARCHNULL)
229  haveIsNull = true;
230  else if (skey->sk_flags & SK_SEARCHNOTNULL)
231  haveNotNull = true;
232  else if (skey->sk_flags & SK_ISNULL)
233  {
234  /* ordinary qual with null argument - unsatisfiable */
235  qual_ok = false;
236  break;
237  }
238  else
239  {
240  /* ordinary qual, propagate into so->keyData */
241  so->keyData[nkeys++] = *skey;
242  /* this effectively creates a not-null requirement */
243  haveNotNull = true;
244  }
245  }
246 
247  /* IS NULL in combination with something else is unsatisfiable */
248  if (haveIsNull && haveNotNull)
249  qual_ok = false;
250 
251  /* Emit results */
252  if (qual_ok)
253  {
254  so->searchNulls = haveIsNull;
255  so->searchNonNulls = haveNotNull;
256  so->numberOfKeys = nkeys;
257  }
258  else
259  {
260  so->searchNulls = false;
261  so->searchNonNulls = false;
262  so->numberOfKeys = 0;
263  }
264 }
265 
267 spgbeginscan(Relation rel, int keysz, int orderbysz)
268 {
269  IndexScanDesc scan;
270  SpGistScanOpaque so;
271  int i;
272 
273  scan = RelationGetIndexScan(rel, keysz, orderbysz);
274 
276  if (keysz > 0)
277  so->keyData = (ScanKey) palloc(sizeof(ScanKeyData) * keysz);
278  else
279  so->keyData = NULL;
280  initSpGistState(&so->state, scan->indexRelation);
281 
283  "SP-GiST search temporary context",
286  "SP-GiST traversal-value context",
288 
289  /* Set up indexTupDesc and xs_hitupdesc in case it's an index-only scan */
290  so->indexTupDesc = scan->xs_hitupdesc = RelationGetDescr(rel);
291 
292  /* Allocate various arrays needed for order-by scans */
293  if (scan->numberOfOrderBys > 0)
294  {
295  /* This will be filled in spgrescan, but allocate the space here */
296  so->orderByTypes = (Oid *)
297  palloc(sizeof(Oid) * scan->numberOfOrderBys);
298 
299  /* These arrays have constant contents, so we can fill them now */
300  so->zeroDistances = (double *)
301  palloc(sizeof(double) * scan->numberOfOrderBys);
302  so->infDistances = (double *)
303  palloc(sizeof(double) * scan->numberOfOrderBys);
304 
305  for (i = 0; i < scan->numberOfOrderBys; i++)
306  {
307  so->zeroDistances[i] = 0.0;
309  }
310 
311  scan->xs_orderbyvals = (Datum *)
312  palloc0(sizeof(Datum) * scan->numberOfOrderBys);
313  scan->xs_orderbynulls = (bool *)
314  palloc(sizeof(bool) * scan->numberOfOrderBys);
315  memset(scan->xs_orderbynulls, true,
316  sizeof(bool) * scan->numberOfOrderBys);
317  }
318 
322 
326 
327  so->indexCollation = rel->rd_indcollation[0];
328 
329  scan->opaque = so;
330 
331  return scan;
332 }
333 
334 void
335 spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
336  ScanKey orderbys, int norderbys)
337 {
339 
340  /* copy scankeys into local storage */
341  if (scankey && scan->numberOfKeys > 0)
342  memmove(scan->keyData, scankey,
343  scan->numberOfKeys * sizeof(ScanKeyData));
344 
345  /* initialize order-by data if needed */
346  if (orderbys && scan->numberOfOrderBys > 0)
347  {
348  int i;
349 
350  memmove(scan->orderByData, orderbys,
351  scan->numberOfOrderBys * sizeof(ScanKeyData));
352 
353  for (i = 0; i < scan->numberOfOrderBys; i++)
354  {
355  ScanKey skey = &scan->orderByData[i];
356 
357  /*
358  * Look up the datatype returned by the original ordering
359  * operator. SP-GiST always uses a float8 for the distance
360  * function, but the ordering operator could be anything else.
361  *
362  * XXX: The distance function is only allowed to be lossy if the
363  * ordering operator's result type is float4 or float8. Otherwise
364  * we don't know how to return the distance to the executor. But
365  * we cannot check that here, as we won't know if the distance
366  * function is lossy until it returns *recheck = true for the
367  * first time.
368  */
370  }
371  }
372 
373  /* preprocess scankeys, set up the representation in *so */
374  spgPrepareScanKeys(scan);
375 
376  /* set up starting queue entries */
378 }
379 
380 void
382 {
384 
387 
388  if (so->keyData)
389  pfree(so->keyData);
390 
391  if (so->state.deadTupleStorage)
393 
394  if (scan->numberOfOrderBys > 0)
395  {
396  pfree(so->orderByTypes);
397  pfree(so->zeroDistances);
398  pfree(so->infDistances);
399  pfree(scan->xs_orderbyvals);
400  pfree(scan->xs_orderbynulls);
401  }
402 
403  pfree(so);
404 }
405 
406 /*
407  * Leaf SpGistSearchItem constructor, called in queue context
408  */
409 static SpGistSearchItem *
411  Datum leafValue, bool recheck, bool recheckDistances,
412  bool isnull, double *distances)
413 {
414  SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
415 
416  item->level = level;
417  item->heapPtr = *heapPtr;
418  /* copy value to queue cxt out of tmp cxt */
419  item->value = isnull ? (Datum) 0 :
420  datumCopy(leafValue, so->state.attLeafType.attbyval,
421  so->state.attLeafType.attlen);
422  item->traversalValue = NULL;
423  item->isLeaf = true;
424  item->recheck = recheck;
425  item->recheckDistances = recheckDistances;
426 
427  return item;
428 }
429 
430 /*
431  * Test whether a leaf tuple satisfies all the scan keys
432  *
433  * *reportedSome is set to true if:
434  * the scan is not ordered AND the item satisfies the scankeys
435  */
436 static bool
438  SpGistLeafTuple leafTuple, bool isnull,
439  bool *reportedSome, storeRes_func storeRes)
440 {
441  Datum leafValue;
442  double *distances;
443  bool result;
444  bool recheck;
445  bool recheckDistances;
446 
447  if (isnull)
448  {
449  /* Should not have arrived on a nulls page unless nulls are wanted */
450  Assert(so->searchNulls);
451  leafValue = (Datum) 0;
452  distances = NULL;
453  recheck = false;
454  recheckDistances = false;
455  result = true;
456  }
457  else
458  {
461 
462  /* use temp context for calling leaf_consistent */
464 
465  in.scankeys = so->keyData;
466  in.nkeys = so->numberOfKeys;
467  in.orderbys = so->orderByData;
468  in.norderbys = so->numberOfOrderBys;
469  in.reconstructedValue = item->value;
470  in.traversalValue = item->traversalValue;
471  in.level = item->level;
472  in.returnData = so->want_itup;
473  in.leafDatum = SGLTDATUM(leafTuple, &so->state);
474 
475  out.leafValue = (Datum) 0;
476  out.recheck = false;
477  out.distances = NULL;
478  out.recheckDistances = false;
479 
481  so->indexCollation,
482  PointerGetDatum(&in),
483  PointerGetDatum(&out)));
484  recheck = out.recheck;
485  recheckDistances = out.recheckDistances;
486  leafValue = out.leafValue;
487  distances = out.distances;
488 
489  MemoryContextSwitchTo(oldCxt);
490  }
491 
492  if (result)
493  {
494  /* item passes the scankeys */
495  if (so->numberOfOrderBys > 0)
496  {
497  /* the scan is ordered -> add the item to the queue */
499  SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
500  &leafTuple->heapPtr,
501  leafValue,
502  recheck,
503  recheckDistances,
504  isnull,
505  distances);
506 
507  spgAddSearchItemToQueue(so, heapItem);
508 
509  MemoryContextSwitchTo(oldCxt);
510  }
511  else
512  {
513  /* non-ordered scan, so report the item right away */
514  Assert(!recheckDistances);
515  storeRes(so, &leafTuple->heapPtr, leafValue, isnull,
516  recheck, false, NULL);
517  *reportedSome = true;
518  }
519  }
520 
521  return result;
522 }
523 
524 /* A bundle initializer for inner_consistent methods */
525 static void
527  SpGistScanOpaque so,
528  SpGistSearchItem *item,
529  SpGistInnerTuple innerTuple)
530 {
531  in->scankeys = so->keyData;
532  in->orderbys = so->orderByData;
533  in->nkeys = so->numberOfKeys;
534  in->norderbys = so->numberOfOrderBys;
535  in->reconstructedValue = item->value;
537  in->traversalValue = item->traversalValue;
538  in->level = item->level;
539  in->returnData = so->want_itup;
540  in->allTheSame = innerTuple->allTheSame;
541  in->hasPrefix = (innerTuple->prefixSize > 0);
542  in->prefixDatum = SGITDATUM(innerTuple, &so->state);
543  in->nNodes = innerTuple->nNodes;
544  in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
545 }
546 
547 static SpGistSearchItem *
549  SpGistSearchItem *parentItem,
550  SpGistNodeTuple tuple,
551  spgInnerConsistentOut *out, int i, bool isnull,
552  double *distances)
553 {
554  SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
555 
556  item->heapPtr = tuple->t_tid;
557  item->level = out->levelAdds ? parentItem->level + out->levelAdds[i]
558  : parentItem->level;
559 
560  /* Must copy value out of temp context */
561  item->value = out->reconstructedValues
562  ? datumCopy(out->reconstructedValues[i],
565  : (Datum) 0;
566 
567  /*
568  * Elements of out.traversalValues should be allocated in
569  * in.traversalMemoryContext, which is actually a long lived context of
570  * index scan.
571  */
572  item->traversalValue =
573  out->traversalValues ? out->traversalValues[i] : NULL;
574 
575  item->isLeaf = false;
576  item->recheck = false;
577  item->recheckDistances = false;
578 
579  return item;
580 }
581 
582 static void
584  SpGistInnerTuple innerTuple, bool isnull)
585 {
588  int nNodes = innerTuple->nNodes;
589  int i;
590 
591  memset(&out, 0, sizeof(out));
592 
593  if (!isnull)
594  {
596 
597  spgInitInnerConsistentIn(&in, so, item, innerTuple);
598 
599  /* use user-defined inner consistent method */
601  so->indexCollation,
602  PointerGetDatum(&in),
603  PointerGetDatum(&out));
604  }
605  else
606  {
607  /* force all children to be visited */
608  out.nNodes = nNodes;
609  out.nodeNumbers = (int *) palloc(sizeof(int) * nNodes);
610  for (i = 0; i < nNodes; i++)
611  out.nodeNumbers[i] = i;
612  }
613 
614  /* If allTheSame, they should all or none of them match */
615  if (innerTuple->allTheSame && out.nNodes != 0 && out.nNodes != nNodes)
616  elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
617 
618  if (out.nNodes)
619  {
620  /* collect node pointers */
621  SpGistNodeTuple node;
623  sizeof(SpGistNodeTuple) * nNodes);
624 
625  SGITITERATE(innerTuple, i, node)
626  {
627  nodes[i] = node;
628  }
629 
631 
632  for (i = 0; i < out.nNodes; i++)
633  {
634  int nodeN = out.nodeNumbers[i];
635  SpGistSearchItem *innerItem;
636  double *distances;
637 
638  Assert(nodeN >= 0 && nodeN < nNodes);
639 
640  node = nodes[nodeN];
641 
642  if (!ItemPointerIsValid(&node->t_tid))
643  continue;
644 
645  /*
646  * Use infinity distances if innerConsistentFn() failed to return
647  * them or if is a NULL item (their distances are really unused).
648  */
649  distances = out.distances ? out.distances[i] : so->infDistances;
650 
651  innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull,
652  distances);
653 
654  spgAddSearchItemToQueue(so, innerItem);
655  }
656  }
657 
658  MemoryContextSwitchTo(oldCxt);
659 }
660 
661 /* Returns a next item in an (ordered) scan or null if the index is exhausted */
662 static SpGistSearchItem *
664 {
666  return NULL; /* Done when both heaps are empty */
667 
668  /* Return item; caller is responsible to pfree it */
670 }
671 
673 {
677 };
678 
679 static OffsetNumber
681  SpGistSearchItem *item,
682  Page page, OffsetNumber offset,
683  bool isnull, bool isroot,
684  bool *reportedSome,
685  storeRes_func storeRes)
686 {
687  SpGistLeafTuple leafTuple = (SpGistLeafTuple)
688  PageGetItem(page, PageGetItemId(page, offset));
689 
690  if (leafTuple->tupstate != SPGIST_LIVE)
691  {
692  if (!isroot) /* all tuples on root should be live */
693  {
694  if (leafTuple->tupstate == SPGIST_REDIRECT)
695  {
696  /* redirection tuple should be first in chain */
697  Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
698  /* transfer attention to redirect point */
699  item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer;
702  }
703 
704  if (leafTuple->tupstate == SPGIST_DEAD)
705  {
706  /* dead tuple should be first in chain */
707  Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
708  /* No live entries on this page */
709  Assert(leafTuple->nextOffset == InvalidOffsetNumber);
711  }
712  }
713 
714  /* We should not arrive at a placeholder */
715  elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate);
717  }
718 
719  Assert(ItemPointerIsValid(&leafTuple->heapPtr));
720 
721  spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes);
722 
723  return leafTuple->nextOffset;
724 }
725 
726 /*
727  * Walk the tree and report all tuples passing the scan quals to the storeRes
728  * subroutine.
729  *
730  * If scanWholeIndex is true, we'll do just that. If not, we'll stop at the
731  * next page boundary once we have reported at least one tuple.
732  */
733 static void
734 spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex,
735  storeRes_func storeRes, Snapshot snapshot)
736 {
737  Buffer buffer = InvalidBuffer;
738  bool reportedSome = false;
739 
740  while (scanWholeIndex || !reportedSome)
741  {
743 
744  if (item == NULL)
745  break; /* No more items in queue -> done */
746 
747 redirect:
748  /* Check for interrupts, just in case of infinite loop */
750 
751  if (item->isLeaf)
752  {
753  /* We store heap items in the queue only in case of ordered search */
754  Assert(so->numberOfOrderBys > 0);
755  storeRes(so, &item->heapPtr, item->value, item->isNull,
756  item->recheck, item->recheckDistances, item->distances);
757  reportedSome = true;
758  }
759  else
760  {
763  Page page;
764  bool isnull;
765 
766  if (buffer == InvalidBuffer)
767  {
768  buffer = ReadBuffer(index, blkno);
769  LockBuffer(buffer, BUFFER_LOCK_SHARE);
770  }
771  else if (blkno != BufferGetBlockNumber(buffer))
772  {
773  UnlockReleaseBuffer(buffer);
774  buffer = ReadBuffer(index, blkno);
775  LockBuffer(buffer, BUFFER_LOCK_SHARE);
776  }
777 
778  /* else new pointer points to the same page, no work needed */
779 
780  page = BufferGetPage(buffer);
781  TestForOldSnapshot(snapshot, index, page);
782 
783  isnull = SpGistPageStoresNulls(page) ? true : false;
784 
785  if (SpGistPageIsLeaf(page))
786  {
787  /* Page is a leaf - that is, all it's tuples are heap items */
789 
790  if (SpGistBlockIsRoot(blkno))
791  {
792  /* When root is a leaf, examine all its tuples */
793  for (offset = FirstOffsetNumber; offset <= max; offset++)
794  (void) spgTestLeafTuple(so, item, page, offset,
795  isnull, true,
796  &reportedSome, storeRes);
797  }
798  else
799  {
800  /* Normal case: just examine the chain we arrived at */
801  while (offset != InvalidOffsetNumber)
802  {
803  Assert(offset >= FirstOffsetNumber && offset <= max);
804  offset = spgTestLeafTuple(so, item, page, offset,
805  isnull, false,
806  &reportedSome, storeRes);
807  if (offset == SpGistRedirectOffsetNumber)
808  goto redirect;
809  }
810  }
811  }
812  else /* page is inner */
813  {
814  SpGistInnerTuple innerTuple = (SpGistInnerTuple)
815  PageGetItem(page, PageGetItemId(page, offset));
816 
817  if (innerTuple->tupstate != SPGIST_LIVE)
818  {
819  if (innerTuple->tupstate == SPGIST_REDIRECT)
820  {
821  /* transfer attention to redirect point */
822  item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
825  goto redirect;
826  }
827  elog(ERROR, "unexpected SPGiST tuple state: %d",
828  innerTuple->tupstate);
829  }
830 
831  spgInnerTest(so, item, innerTuple, isnull);
832  }
833  }
834 
835  /* done with this scan item */
836  spgFreeSearchItem(so, item);
837  /* clear temp context before proceeding to the next one */
839  }
840 
841  if (buffer != InvalidBuffer)
842  UnlockReleaseBuffer(buffer);
843 }
844 
845 
846 /* storeRes subroutine for getbitmap case */
847 static void
849  Datum leafValue, bool isnull, bool recheck, bool recheckDistances,
850  double *distances)
851 {
852  Assert(!recheckDistances && !distances);
853  tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
854  so->ntids++;
855 }
856 
857 int64
859 {
861 
862  /* Copy want_itup to *so so we don't need to pass it around separately */
863  so->want_itup = false;
864 
865  so->tbm = tbm;
866  so->ntids = 0;
867 
868  spgWalk(scan->indexRelation, so, true, storeBitmap, scan->xs_snapshot);
869 
870  return so->ntids;
871 }
872 
873 /* storeRes subroutine for gettuple case */
874 static void
876  Datum leafValue, bool isnull, bool recheck, bool recheckDistances,
877  double *distances)
878 {
880  so->heapPtrs[so->nPtrs] = *heapPtr;
881  so->recheck[so->nPtrs] = recheck;
882  so->recheckDistances[so->nPtrs] = recheckDistances;
883 
884  if (so->numberOfOrderBys > 0)
885  {
886  if (isnull)
887  so->distances[so->nPtrs] = NULL;
888  else
889  {
890  Size size = sizeof(double) * so->numberOfOrderBys;
891 
892  so->distances[so->nPtrs] = memcpy(palloc(size), distances, size);
893  }
894  }
895 
896  if (so->want_itup)
897  {
898  /*
899  * Reconstruct index data. We have to copy the datum out of the temp
900  * context anyway, so we may as well create the tuple here.
901  */
903  &leafValue,
904  &isnull);
905  }
906  so->nPtrs++;
907 }
908 
909 bool
911 {
913 
914  if (dir != ForwardScanDirection)
915  elog(ERROR, "SP-GiST only supports forward scan direction");
916 
917  /* Copy want_itup to *so so we don't need to pass it around separately */
918  so->want_itup = scan->xs_want_itup;
919 
920  for (;;)
921  {
922  if (so->iPtr < so->nPtrs)
923  {
924  /* continuing to return reported tuples */
925  scan->xs_heaptid = so->heapPtrs[so->iPtr];
926  scan->xs_recheck = so->recheck[so->iPtr];
927  scan->xs_hitup = so->reconTups[so->iPtr];
928 
929  if (so->numberOfOrderBys > 0)
931  so->distances[so->iPtr],
932  NULL,
933  so->recheckDistances[so->iPtr]);
934  so->iPtr++;
935  return true;
936  }
937 
938  if (so->numberOfOrderBys > 0)
939  {
940  /* Must pfree distances to avoid memory leak */
941  int i;
942 
943  for (i = 0; i < so->nPtrs; i++)
944  if (so->distances[i])
945  pfree(so->distances[i]);
946  }
947 
948  if (so->want_itup)
949  {
950  /* Must pfree reconstructed tuples to avoid memory leak */
951  int i;
952 
953  for (i = 0; i < so->nPtrs; i++)
954  pfree(so->reconTups[i]);
955  }
956  so->iPtr = so->nPtrs = 0;
957 
958  spgWalk(scan->indexRelation, so, false, storeGettuple,
959  scan->xs_snapshot);
960 
961  if (so->nPtrs == 0)
962  break; /* must have completed scan */
963  }
964 
965  return false;
966 }
967 
968 bool
970 {
971  SpGistCache *cache;
972 
973  /* We can do it if the opclass config function says so */
974  cache = spgGetCache(index);
975 
976  return cache->config.canReturnData;
977 }
Datum reconstructedValue
Definition: spgist.h:178
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:82
#define SPGIST_DEAD
Datum * spgExtractNodeLabels(SpGistState *state, SpGistInnerTuple innerTuple)
Definition: spgutils.c:828
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
#define AllocSetContextCreate
Definition: memutils.h:169
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:264
SpGistInnerTupleData * SpGistInnerTuple
#define SpGistPageIsLeaf(page)
static void storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, Datum leafValue, bool isnull, bool recheck, bool recheckDistances, double *distances)
Definition: spgscan.c:875
static float8 get_float8_infinity(void)
Definition: float.h:90
SpGistCache * spgGetCache(Relation index)
Definition: spgutils.c:99
#define SPGIST_LEAF_CONSISTENT_PROC
Definition: spgist.h:31
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:794
struct ScanKeyData * orderByData
Definition: relscan.h:108
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:49
#define RelationGetDescr(relation)
Definition: rel.h:442
#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:130
SpGistTypeDesc attLeafType
ItemPointerData t_tid
Definition: itup.h:37
ScanKey orderbys
Definition: spgist.h:138
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void * traversalValue
Definition: spgist.h:144
#define pairingheap_is_empty(h)
Definition: pairingheap.h:96
#define InvalidBuffer
Definition: buf.h:25
static SpGistSearchItem * spgGetNextQueueItem(SpGistScanOpaque so)
Definition: spgscan.c:663
MemoryContext tempCxt
Datum * xs_orderbyvals
Definition: relscan.h:146
void spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys)
Definition: spgscan.c:335
pairingheap * pairingheap_allocate(pairingheap_comparator compare, void *arg)
Definition: pairingheap.c:42
struct SnapshotData * xs_snapshot
Definition: relscan.h:104
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:1150
unsigned int Oid
Definition: postgres_ext.h:31
#define SPGIST_ROOT_BLKNO
void spgendscan(IndexScanDesc scan)
Definition: spgscan.c:381
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
Datum reconstructedValue
Definition: spgist.h:143
HeapTuple reconTups[MaxIndexTuplesPerPage]
bool spgcanreturn(Relation index, int attno)
Definition: spgscan.c:969
Oid get_func_rettype(Oid funcid)
Definition: lsyscache.c:1457
Relation indexRelation
Definition: relscan.h:103
uint16 OffsetNumber
Definition: off.h:24
#define SGITDATUM(x, s)
Definition: type.h:89
#define true
Definition: c.h:312
bool * xs_orderbynulls
Definition: relscan.h:147
void pfree(void *pointer)
Definition: mcxt.c:1031
unsigned int allTheSame
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3376
Oid * rd_indcollation
Definition: rel.h:168
MemoryContext traversalMemoryContext
Definition: spgist.h:145
#define ERROR
Definition: elog.h:43
ScanKey orderbys
Definition: spgist.h:173
pairingheap_node phNode
ScanKey scankeys
Definition: spgist.h:172
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:191
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:610
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:680
ItemPointerData xs_heaptid
Definition: relscan.h:132
#define SPGIST_NULL_BLKNO
#define memmove(d, s, c)
Definition: c.h:1238
double * distances[MaxIndexTuplesPerPage]
ScanKeyData * ScanKey
Definition: skey.h:75
void index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, double *distanceValues, bool *distanceNulls, bool recheckOrderBy)
Definition: indexam.c:849
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:191
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:181
SpGistDeadTupleData * SpGistDeadTuple
int64 spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: spgscan.c:858
static SpGistSearchItem * spgMakeInnerItem(SpGistScanOpaque so, SpGistSearchItem *parentItem, SpGistNodeTuple tuple, spgInnerConsistentOut *out, int i, bool isnull, double *distances)
Definition: spgscan.c:548
#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:159
void ** traversalValues
Definition: spgist.h:163
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:130
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:955
uintptr_t Datum
Definition: postgres.h:367
double ** distances
Definition: spgist.h:164
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3590
char * deadTupleStorage
SpGistScanOpaqueData * SpGistScanOpaque
static void spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple, bool isnull)
Definition: spgscan.c:583
Datum * nodeLabels
Definition: spgist.h:154
#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:734
ItemPointerData heapPtr
int sk_flags
Definition: skey.h:66
#define Assert(condition)
Definition: c.h:732
static void spgInitInnerConsistentIn(spgInnerConsistentIn *in, SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple)
Definition: spgscan.c:526
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:596
#define SpGistBlockIsRoot(blkno)
size_t Size
Definition: c.h:466
#define SPGIST_LIVE
#define SGLTDATUM(x, s)
Datum * reconstructedValues
Definition: spgist.h:162
OffsetNumber nextOffset
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:117
ScanKey scankeys
Definition: spgist.h:137
static void resetSpGistScanOpaque(SpGistScanOpaque so)
Definition: spgscan.c:145
#define DatumGetPointer(X)
Definition: postgres.h:549
struct ScanKeyData * keyData
Definition: relscan.h:107
MemoryContext traversalCxt
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2613
#define MaxIndexTuplesPerPage
Definition: itup.h:145
void * palloc(Size size)
Definition: mcxt.c:924
HeapTuple xs_hitup
Definition: relscan.h:129
bool spggettuple(IndexScanDesc scan, ScanDirection dir)
Definition: spgscan.c:910
#define elog(elevel,...)
Definition: elog.h:226
int i
#define BUFFER_LOCK_SHARE
Definition: bufmgr.h:87
pairingheap_node * pairingheap_remove_first(pairingheap *heap)
Definition: pairingheap.c:145
#define SPGIST_INNER_CONSISTENT_PROC
Definition: spgist.h:30
void * arg
void * traversalValue
Definition: spgist.h:179
static bool spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item, SpGistLeafTuple leafTuple, bool isnull, bool *reportedSome, storeRes_func storeRes)
Definition: spgscan.c:437
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:80
SpGistSpecialOffsetNumbers
Definition: spgscan.c:672
IndexScanDesc spgbeginscan(Relation rel, int keysz, int orderbysz)
Definition: spgscan.c:267
#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:848
int numberOfOrderBys
Definition: relscan.h:106
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:410