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