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->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;
654  sizeof(SpGistNodeTuple) * nNodes);
655 
656  SGITITERATE(innerTuple, i, node)
657  {
658  nodes[i] = node;
659  }
660 
662 
663  for (i = 0; i < out.nNodes; i++)
664  {
665  int nodeN = out.nodeNumbers[i];
666  SpGistSearchItem *innerItem;
667  double *distances;
668 
669  Assert(nodeN >= 0 && nodeN < nNodes);
670 
671  node = nodes[nodeN];
672 
673  if (!ItemPointerIsValid(&node->t_tid))
674  continue;
675 
676  /*
677  * Use infinity distances if innerConsistentFn() failed to return
678  * them or if is a NULL item (their distances are really unused).
679  */
680  distances = out.distances ? out.distances[i] : so->infDistances;
681 
682  innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull,
683  distances);
684 
685  spgAddSearchItemToQueue(so, innerItem);
686  }
687  }
688 
689  MemoryContextSwitchTo(oldCxt);
690 }
691 
692 /* Returns a next item in an (ordered) scan or null if the index is exhausted */
693 static SpGistSearchItem *
695 {
697  return NULL; /* Done when both heaps are empty */
698 
699  /* Return item; caller is responsible to pfree it */
701 }
702 
704 {
708 };
709 
710 static OffsetNumber
712  SpGistSearchItem *item,
713  Page page, OffsetNumber offset,
714  bool isnull, bool isroot,
715  bool *reportedSome,
716  storeRes_func storeRes)
717 {
718  SpGistLeafTuple leafTuple = (SpGistLeafTuple)
719  PageGetItem(page, PageGetItemId(page, offset));
720 
721  if (leafTuple->tupstate != SPGIST_LIVE)
722  {
723  if (!isroot) /* all tuples on root should be live */
724  {
725  if (leafTuple->tupstate == SPGIST_REDIRECT)
726  {
727  /* redirection tuple should be first in chain */
728  Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
729  /* transfer attention to redirect point */
730  item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer;
733  }
734 
735  if (leafTuple->tupstate == SPGIST_DEAD)
736  {
737  /* dead tuple should be first in chain */
738  Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr));
739  /* No live entries on this page */
740  Assert(leafTuple->nextOffset == InvalidOffsetNumber);
742  }
743  }
744 
745  /* We should not arrive at a placeholder */
746  elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate);
748  }
749 
750  Assert(ItemPointerIsValid(&leafTuple->heapPtr));
751 
752  spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes);
753 
754  return leafTuple->nextOffset;
755 }
756 
757 /*
758  * Walk the tree and report all tuples passing the scan quals to the storeRes
759  * subroutine.
760  *
761  * If scanWholeIndex is true, we'll do just that. If not, we'll stop at the
762  * next page boundary once we have reported at least one tuple.
763  */
764 static void
765 spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex,
766  storeRes_func storeRes, Snapshot snapshot)
767 {
768  Buffer buffer = InvalidBuffer;
769  bool reportedSome = false;
770 
771  while (scanWholeIndex || !reportedSome)
772  {
774 
775  if (item == NULL)
776  break; /* No more items in queue -> done */
777 
778 redirect:
779  /* Check for interrupts, just in case of infinite loop */
781 
782  if (item->isLeaf)
783  {
784  /* We store heap items in the queue only in case of ordered search */
786  storeRes(so, &item->heapPtr, item->value, item->isNull,
787  item->recheck, item->recheckDistances, item->distances);
788  reportedSome = true;
789  }
790  else
791  {
794  Page page;
795  bool isnull;
796 
797  if (buffer == InvalidBuffer)
798  {
799  buffer = ReadBuffer(index, blkno);
800  LockBuffer(buffer, BUFFER_LOCK_SHARE);
801  }
802  else if (blkno != BufferGetBlockNumber(buffer))
803  {
804  UnlockReleaseBuffer(buffer);
805  buffer = ReadBuffer(index, blkno);
806  LockBuffer(buffer, BUFFER_LOCK_SHARE);
807  }
808 
809  /* else new pointer points to the same page, no work needed */
810 
811  page = BufferGetPage(buffer);
812  TestForOldSnapshot(snapshot, index, page);
813 
814  isnull = SpGistPageStoresNulls(page) ? true : false;
815 
816  if (SpGistPageIsLeaf(page))
817  {
818  /* Page is a leaf - that is, all it's tuples are heap items */
820 
821  if (SpGistBlockIsRoot(blkno))
822  {
823  /* When root is a leaf, examine all its tuples */
824  for (offset = FirstOffsetNumber; offset <= max; offset++)
825  (void) spgTestLeafTuple(so, item, page, offset,
826  isnull, true,
827  &reportedSome, storeRes);
828  }
829  else
830  {
831  /* Normal case: just examine the chain we arrived at */
832  while (offset != InvalidOffsetNumber)
833  {
834  Assert(offset >= FirstOffsetNumber && offset <= max);
835  offset = spgTestLeafTuple(so, item, page, offset,
836  isnull, false,
837  &reportedSome, storeRes);
838  if (offset == SpGistRedirectOffsetNumber)
839  goto redirect;
840  }
841  }
842  }
843  else /* page is inner */
844  {
845  SpGistInnerTuple innerTuple = (SpGistInnerTuple)
846  PageGetItem(page, PageGetItemId(page, offset));
847 
848  if (innerTuple->tupstate != SPGIST_LIVE)
849  {
850  if (innerTuple->tupstate == SPGIST_REDIRECT)
851  {
852  /* transfer attention to redirect point */
853  item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
856  goto redirect;
857  }
858  elog(ERROR, "unexpected SPGiST tuple state: %d",
859  innerTuple->tupstate);
860  }
861 
862  spgInnerTest(so, item, innerTuple, isnull);
863  }
864  }
865 
866  /* done with this scan item */
867  spgFreeSearchItem(so, item);
868  /* clear temp context before proceeding to the next one */
870  }
871 
872  if (buffer != InvalidBuffer)
873  UnlockReleaseBuffer(buffer);
874 }
875 
876 
877 /* storeRes subroutine for getbitmap case */
878 static void
880  Datum leafValue, bool isnull, bool recheck, bool recheckDistances,
881  double *distances)
882 {
883  Assert(!recheckDistances && !distances);
884  tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
885  so->ntids++;
886 }
887 
888 int64
890 {
892 
893  /* Copy want_itup to *so so we don't need to pass it around separately */
894  so->want_itup = false;
895 
896  so->tbm = tbm;
897  so->ntids = 0;
898 
899  spgWalk(scan->indexRelation, so, true, storeBitmap, scan->xs_snapshot);
900 
901  return so->ntids;
902 }
903 
904 /* storeRes subroutine for gettuple case */
905 static void
907  Datum leafValue, bool isnull, bool recheck, bool recheckDistances,
908  double *nonNullDistances)
909 {
911  so->heapPtrs[so->nPtrs] = *heapPtr;
912  so->recheck[so->nPtrs] = recheck;
913  so->recheckDistances[so->nPtrs] = recheckDistances;
914 
915  if (so->numberOfOrderBys > 0)
916  {
917  if (isnull || so->numberOfNonNullOrderBys <= 0)
918  so->distances[so->nPtrs] = NULL;
919  else
920  {
921  IndexOrderByDistance *distances =
922  palloc(sizeof(distances[0]) * so->numberOfOrderBys);
923  int i;
924 
925  for (i = 0; i < so->numberOfOrderBys; i++)
926  {
927  int offset = so->nonNullOrderByOffsets[i];
928 
929  if (offset >= 0)
930  {
931  /* Copy non-NULL distance value */
932  distances[i].value = nonNullDistances[offset];
933  distances[i].isnull = false;
934  }
935  else
936  {
937  /* Set distance's NULL flag. */
938  distances[i].value = 0.0;
939  distances[i].isnull = true;
940  }
941  }
942 
943  so->distances[so->nPtrs] = distances;
944  }
945  }
946 
947  if (so->want_itup)
948  {
949  /*
950  * Reconstruct index data. We have to copy the datum out of the temp
951  * context anyway, so we may as well create the tuple here.
952  */
954  &leafValue,
955  &isnull);
956  }
957  so->nPtrs++;
958 }
959 
960 bool
962 {
964 
965  if (dir != ForwardScanDirection)
966  elog(ERROR, "SP-GiST only supports forward scan direction");
967 
968  /* Copy want_itup to *so so we don't need to pass it around separately */
969  so->want_itup = scan->xs_want_itup;
970 
971  for (;;)
972  {
973  if (so->iPtr < so->nPtrs)
974  {
975  /* continuing to return reported tuples */
976  scan->xs_heaptid = so->heapPtrs[so->iPtr];
977  scan->xs_recheck = so->recheck[so->iPtr];
978  scan->xs_hitup = so->reconTups[so->iPtr];
979 
980  if (so->numberOfOrderBys > 0)
982  so->distances[so->iPtr],
983  so->recheckDistances[so->iPtr]);
984  so->iPtr++;
985  return true;
986  }
987 
988  if (so->numberOfOrderBys > 0)
989  {
990  /* Must pfree distances to avoid memory leak */
991  int i;
992 
993  for (i = 0; i < so->nPtrs; i++)
994  if (so->distances[i])
995  pfree(so->distances[i]);
996  }
997 
998  if (so->want_itup)
999  {
1000  /* Must pfree reconstructed tuples to avoid memory leak */
1001  int i;
1002 
1003  for (i = 0; i < so->nPtrs; i++)
1004  pfree(so->reconTups[i]);
1005  }
1006  so->iPtr = so->nPtrs = 0;
1007 
1008  spgWalk(scan->indexRelation, so, false, storeGettuple,
1009  scan->xs_snapshot);
1010 
1011  if (so->nPtrs == 0)
1012  break; /* must have completed scan */
1013  }
1014 
1015  return false;
1016 }
1017 
1018 bool
1020 {
1021  SpGistCache *cache;
1022 
1023  /* We can do it if the opclass config function says so */
1024  cache = spgGetCache(index);
1025 
1026  return cache->config.canReturnData;
1027 }
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:170
static void TestForOldSnapshot(Snapshot snapshot, Relation relation, Page page)
Definition: bufmgr.h:264
SpGistInnerTupleData * SpGistInnerTuple
#define SpGistPageIsLeaf(page)
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
IndexOrderByDistance * distances[MaxIndexTuplesPerPage]
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:449
#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:694
MemoryContext tempCxt
Datum * xs_orderbyvals
Definition: relscan.h:146
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: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:411
#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:1019
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:313
bool * xs_orderbynulls
Definition: relscan.h:147
void pfree(void *pointer)
Definition: mcxt.c:1056
unsigned int allTheSame
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3388
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:192
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:711
ItemPointerData xs_heaptid
Definition: relscan.h:132
#define SPGIST_NULL_BLKNO
#define memmove(d, s, c)
Definition: c.h:1261
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: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:889
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: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:980
void index_store_float8_orderby_distances(IndexScanDesc scan, Oid *orderByTypes, IndexOrderByDistance *distances, bool recheckOrderBy)
Definition: indexam.c:849
uintptr_t Datum
Definition: postgres.h:367
double ** distances
Definition: spgist.h:164
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3602
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:906
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:765
ItemPointerData heapPtr
int sk_flags
Definition: skey.h:66
#define Assert(condition)
Definition: c.h:733
static void spgInitInnerConsistentIn(spgInnerConsistentIn *in, SpGistScanOpaque so, SpGistSearchItem *item, SpGistInnerTuple innerTuple)
Definition: spgscan.c:557
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:596
#define SpGistBlockIsRoot(blkno)
#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:949
HeapTuple xs_hitup
Definition: relscan.h:129
bool spggettuple(IndexScanDesc scan, ScanDirection dir)
Definition: spgscan.c:961
#define elog(elevel,...)
Definition: elog.h:228
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:468
IndexScanDesc RelationGetIndexScan(Relation indexRelation, int nkeys, int norderbys)
Definition: genam.c:80
SpGistSpecialOffsetNumbers
Definition: spgscan.c:703
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:879
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:441