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