Debian Codegraph @

src/backend/access/spgist/spgscan.c

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