Line data Source code
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"
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 4393754 : pairingheap_SpGistSearchItem_cmp(const pairingheap_node *a,
42 : const pairingheap_node *b, void *arg)
43 : {
44 4393754 : const SpGistSearchItem *sa = (const SpGistSearchItem *) a;
45 4393754 : const SpGistSearchItem *sb = (const SpGistSearchItem *) b;
46 4393754 : SpGistScanOpaque so = (SpGistScanOpaque) arg;
47 : int i;
48 :
49 4393754 : if (sa->isNull)
50 : {
51 638 : if (!sb->isNull)
52 596 : return -1;
53 : }
54 4393116 : else if (sb->isNull)
55 : {
56 592 : return 1;
57 : }
58 : else
59 : {
60 : /* Order according to distance comparison */
61 4632492 : for (i = 0; i < so->numberOfNonNullOrderBys; i++)
62 : {
63 4033198 : if (isnan(sa->distances[i]) && isnan(sb->distances[i]))
64 0 : continue; /* NaN == NaN */
65 4033198 : if (isnan(sa->distances[i]))
66 0 : return -1; /* NaN > number */
67 4033198 : if (isnan(sb->distances[i]))
68 0 : return 1; /* number < NaN */
69 4033198 : if (sa->distances[i] != sb->distances[i])
70 3793230 : 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 599336 : if (sa->isLeaf && !sb->isLeaf)
76 4298 : return 1;
77 595038 : if (!sa->isLeaf && sb->isLeaf)
78 4712 : return -1;
79 :
80 590326 : return 0;
81 : }
82 :
83 : static void
84 458480 : 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 458480 : if (!(item->isLeaf ? so->state.attType.attbyval :
89 916960 : so->state.attLeafType.attbyval) &&
90 458480 : DatumGetPointer(item->value) != NULL)
91 289290 : pfree(DatumGetPointer(item->value));
92 :
93 458480 : if (item->leafTuple)
94 60 : pfree(item->leafTuple);
95 :
96 458480 : if (item->traversalValue)
97 44376 : pfree(item->traversalValue);
98 :
99 458480 : pfree(item);
100 458480 : }
101 :
102 : /*
103 : * Add SpGistSearchItem to queue
104 : *
105 : * Called in queue context
106 : */
107 : static void
108 461238 : spgAddSearchItemToQueue(SpGistScanOpaque so, SpGistSearchItem *item)
109 : {
110 461238 : pairingheap_add(so->scanQueue, &item->phNode);
111 461238 : }
112 :
113 : static SpGistSearchItem *
114 461238 : spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances)
115 : {
116 : /* allocate distance array only for non-NULL items */
117 : SpGistSearchItem *item =
118 461238 : palloc(SizeOfSpGistSearchItem(isnull ? 0 : so->numberOfNonNullOrderBys));
119 :
120 461238 : item->isNull = isnull;
121 :
122 461238 : if (!isnull && so->numberOfNonNullOrderBys > 0)
123 377900 : memcpy(item->distances, distances,
124 377900 : sizeof(item->distances[0]) * so->numberOfNonNullOrderBys);
125 :
126 461238 : return item;
127 : }
128 :
129 : static void
130 982 : spgAddStartItem(SpGistScanOpaque so, bool isnull)
131 : {
132 : SpGistSearchItem *startEntry =
133 982 : spgAllocSearchItem(so, isnull, so->zeroDistances);
134 :
135 982 : ItemPointerSet(&startEntry->heapPtr,
136 : isnull ? SPGIST_NULL_BLKNO : SPGIST_ROOT_BLKNO,
137 : FirstOffsetNumber);
138 982 : startEntry->isLeaf = false;
139 982 : startEntry->level = 0;
140 982 : startEntry->value = (Datum) 0;
141 982 : startEntry->leafTuple = NULL;
142 982 : startEntry->traversalValue = NULL;
143 982 : startEntry->recheck = false;
144 982 : startEntry->recheckDistances = false;
145 :
146 982 : spgAddSearchItemToQueue(so, startEntry);
147 982 : }
148 :
149 : /*
150 : * Initialize queue to search the root page, resetting
151 : * any previously active scan
152 : */
153 : static void
154 928 : resetSpGistScanOpaque(SpGistScanOpaque so)
155 : {
156 : MemoryContext oldCtx;
157 :
158 928 : MemoryContextReset(so->traversalCxt);
159 :
160 928 : oldCtx = MemoryContextSwitchTo(so->traversalCxt);
161 :
162 : /* initialize queue only for distance-ordered scans */
163 928 : so->scanQueue = pairingheap_allocate(pairingheap_SpGistSearchItem_cmp, so);
164 :
165 928 : if (so->searchNulls)
166 : /* Add a work item to scan the null index entries */
167 66 : spgAddStartItem(so, true);
168 :
169 928 : if (so->searchNonNulls)
170 : /* Add a work item to scan the non-null index entries */
171 916 : spgAddStartItem(so, false);
172 :
173 928 : MemoryContextSwitchTo(oldCtx);
174 :
175 928 : if (so->numberOfOrderBys > 0)
176 : {
177 : /* Must pfree distances to avoid memory leak */
178 : int i;
179 :
180 90 : for (i = 0; i < so->nPtrs; i++)
181 12 : if (so->distances[i])
182 12 : pfree(so->distances[i]);
183 : }
184 :
185 928 : if (so->want_itup)
186 : {
187 : /* Must pfree reconstructed tuples to avoid memory leak */
188 : int i;
189 :
190 90 : for (i = 0; i < so->nPtrs; i++)
191 66 : pfree(so->reconTups[i]);
192 : }
193 928 : so->iPtr = so->nPtrs = 0;
194 928 : }
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 928 : spgPrepareScanKeys(IndexScanDesc scan)
209 : {
210 928 : SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
211 : bool qual_ok;
212 : bool haveIsNull;
213 : bool haveNotNull;
214 : int nkeys;
215 : int i;
216 :
217 928 : so->numberOfOrderBys = scan->numberOfOrderBys;
218 928 : so->orderByData = scan->orderByData;
219 :
220 928 : if (so->numberOfOrderBys <= 0)
221 850 : so->numberOfNonNullOrderBys = 0;
222 : else
223 : {
224 78 : int j = 0;
225 :
226 : /*
227 : * Remove all NULL keys, but remember their offsets in the original
228 : * array.
229 : */
230 174 : for (i = 0; i < scan->numberOfOrderBys; i++)
231 : {
232 96 : ScanKey skey = &so->orderByData[i];
233 :
234 96 : if (skey->sk_flags & SK_ISNULL)
235 6 : so->nonNullOrderByOffsets[i] = -1;
236 : else
237 : {
238 90 : if (i != j)
239 6 : so->orderByData[j] = *skey;
240 :
241 90 : so->nonNullOrderByOffsets[i] = j++;
242 : }
243 : }
244 :
245 78 : so->numberOfNonNullOrderBys = j;
246 : }
247 :
248 928 : if (scan->numberOfKeys <= 0)
249 : {
250 : /* If no quals, whole-index scan is required */
251 54 : so->searchNulls = true;
252 54 : so->searchNonNulls = true;
253 54 : so->numberOfKeys = 0;
254 54 : return;
255 : }
256 :
257 : /* Examine the given quals */
258 874 : qual_ok = true;
259 874 : haveIsNull = haveNotNull = false;
260 874 : nkeys = 0;
261 1752 : for (i = 0; i < scan->numberOfKeys; i++)
262 : {
263 878 : ScanKey skey = &scan->keyData[i];
264 :
265 878 : if (skey->sk_flags & SK_SEARCHNULL)
266 12 : haveIsNull = true;
267 866 : else if (skey->sk_flags & SK_SEARCHNOTNULL)
268 24 : haveNotNull = true;
269 842 : else if (skey->sk_flags & SK_ISNULL)
270 : {
271 : /* ordinary qual with null argument - unsatisfiable */
272 0 : qual_ok = false;
273 0 : break;
274 : }
275 : else
276 : {
277 : /* ordinary qual, propagate into so->keyData */
278 842 : so->keyData[nkeys++] = *skey;
279 : /* this effectively creates a not-null requirement */
280 842 : haveNotNull = true;
281 : }
282 : }
283 :
284 : /* IS NULL in combination with something else is unsatisfiable */
285 874 : if (haveIsNull && haveNotNull)
286 0 : qual_ok = false;
287 :
288 : /* Emit results */
289 874 : if (qual_ok)
290 : {
291 874 : so->searchNulls = haveIsNull;
292 874 : so->searchNonNulls = haveNotNull;
293 874 : so->numberOfKeys = nkeys;
294 : }
295 : else
296 : {
297 0 : so->searchNulls = false;
298 0 : so->searchNonNulls = false;
299 0 : so->numberOfKeys = 0;
300 : }
301 : }
302 :
303 : IndexScanDesc
304 904 : spgbeginscan(Relation rel, int keysz, int orderbysz)
305 : {
306 : IndexScanDesc scan;
307 : SpGistScanOpaque so;
308 : int i;
309 :
310 904 : scan = RelationGetIndexScan(rel, keysz, orderbysz);
311 :
312 904 : so = (SpGistScanOpaque) palloc0(sizeof(SpGistScanOpaqueData));
313 904 : if (keysz > 0)
314 862 : so->keyData = (ScanKey) palloc(sizeof(ScanKeyData) * keysz);
315 : else
316 42 : so->keyData = NULL;
317 904 : initSpGistState(&so->state, scan->indexRelation);
318 :
319 904 : so->tempCxt = AllocSetContextCreate(CurrentMemoryContext,
320 : "SP-GiST search temporary context",
321 : ALLOCSET_DEFAULT_SIZES);
322 904 : 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 904 : so->reconTupDesc = scan->xs_hitupdesc =
333 904 : getSpGistTupleDesc(rel, &so->state.attType);
334 :
335 : /* Allocate various arrays needed for order-by scans */
336 904 : if (scan->numberOfOrderBys > 0)
337 : {
338 : /* This will be filled in spgrescan, but allocate the space here */
339 66 : so->orderByTypes = (Oid *)
340 66 : palloc(sizeof(Oid) * scan->numberOfOrderBys);
341 66 : so->nonNullOrderByOffsets = (int *)
342 66 : palloc(sizeof(int) * scan->numberOfOrderBys);
343 :
344 : /* These arrays have constant contents, so we can fill them now */
345 66 : so->zeroDistances = (double *)
346 66 : palloc(sizeof(double) * scan->numberOfOrderBys);
347 66 : so->infDistances = (double *)
348 66 : palloc(sizeof(double) * scan->numberOfOrderBys);
349 :
350 138 : for (i = 0; i < scan->numberOfOrderBys; i++)
351 : {
352 72 : so->zeroDistances[i] = 0.0;
353 72 : so->infDistances[i] = get_float8_infinity();
354 : }
355 :
356 66 : scan->xs_orderbyvals = (Datum *)
357 66 : palloc0(sizeof(Datum) * scan->numberOfOrderBys);
358 66 : scan->xs_orderbynulls = (bool *)
359 66 : palloc(sizeof(bool) * scan->numberOfOrderBys);
360 66 : memset(scan->xs_orderbynulls, true,
361 66 : sizeof(bool) * scan->numberOfOrderBys);
362 : }
363 :
364 904 : fmgr_info_copy(&so->innerConsistentFn,
365 : index_getprocinfo(rel, 1, SPGIST_INNER_CONSISTENT_PROC),
366 : CurrentMemoryContext);
367 :
368 904 : fmgr_info_copy(&so->leafConsistentFn,
369 : index_getprocinfo(rel, 1, SPGIST_LEAF_CONSISTENT_PROC),
370 : CurrentMemoryContext);
371 :
372 904 : so->indexCollation = rel->rd_indcollation[0];
373 :
374 904 : scan->opaque = so;
375 :
376 904 : return scan;
377 : }
378 :
379 : void
380 928 : spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
381 : ScanKey orderbys, int norderbys)
382 : {
383 928 : SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
384 :
385 : /* copy scankeys into local storage */
386 928 : if (scankey && scan->numberOfKeys > 0)
387 874 : memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
388 :
389 : /* initialize order-by data if needed */
390 928 : if (orderbys && scan->numberOfOrderBys > 0)
391 : {
392 : int i;
393 :
394 78 : memcpy(scan->orderByData, orderbys, scan->numberOfOrderBys * sizeof(ScanKeyData));
395 :
396 174 : for (i = 0; i < scan->numberOfOrderBys; i++)
397 : {
398 96 : 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 96 : so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid);
413 : }
414 : }
415 :
416 : /* preprocess scankeys, set up the representation in *so */
417 928 : spgPrepareScanKeys(scan);
418 :
419 : /* set up starting queue entries */
420 928 : resetSpGistScanOpaque(so);
421 :
422 : /* count an indexscan for stats */
423 928 : pgstat_count_index_scan(scan->indexRelation);
424 928 : }
425 :
426 : void
427 904 : spgendscan(IndexScanDesc scan)
428 : {
429 904 : SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
430 :
431 904 : MemoryContextDelete(so->tempCxt);
432 904 : MemoryContextDelete(so->traversalCxt);
433 :
434 904 : if (so->keyData)
435 862 : pfree(so->keyData);
436 :
437 904 : if (so->state.leafTupDesc &&
438 904 : so->state.leafTupDesc != RelationGetDescr(so->state.index))
439 8 : FreeTupleDesc(so->state.leafTupDesc);
440 :
441 904 : if (so->state.deadTupleStorage)
442 904 : pfree(so->state.deadTupleStorage);
443 :
444 904 : if (scan->numberOfOrderBys > 0)
445 : {
446 66 : pfree(so->orderByTypes);
447 66 : pfree(so->nonNullOrderByOffsets);
448 66 : pfree(so->zeroDistances);
449 66 : pfree(so->infDistances);
450 66 : pfree(scan->xs_orderbyvals);
451 66 : pfree(scan->xs_orderbynulls);
452 : }
453 :
454 904 : pfree(so);
455 904 : }
456 :
457 : /*
458 : * Leaf SpGistSearchItem constructor, called in queue context
459 : */
460 : static SpGistSearchItem *
461 365902 : spgNewHeapItem(SpGistScanOpaque so, int level, SpGistLeafTuple leafTuple,
462 : Datum leafValue, bool recheck, bool recheckDistances,
463 : bool isnull, double *distances)
464 : {
465 365902 : SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
466 :
467 365902 : item->level = level;
468 365902 : 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 365902 : if (so->want_itup)
477 : {
478 279346 : item->value = isnull ? (Datum) 0 :
479 279310 : datumCopy(leafValue, so->state.attType.attbyval,
480 279310 : 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 279346 : if (so->state.leafTupDesc->natts > 1)
487 : {
488 196 : item->leafTuple = palloc(leafTuple->size);
489 196 : memcpy(item->leafTuple, leafTuple, leafTuple->size);
490 : }
491 : else
492 279150 : item->leafTuple = NULL;
493 : }
494 : else
495 : {
496 86556 : item->value = (Datum) 0;
497 86556 : item->leafTuple = NULL;
498 : }
499 365902 : item->traversalValue = NULL;
500 365902 : item->isLeaf = true;
501 365902 : item->recheck = recheck;
502 365902 : item->recheckDistances = recheckDistances;
503 :
504 365902 : 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 : */
513 : static bool
514 2544984 : spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item,
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 2544984 : if (isnull)
525 : {
526 : /* Should not have arrived on a nulls page unless nulls are wanted */
527 : Assert(so->searchNulls);
528 120 : leafValue = (Datum) 0;
529 120 : distances = NULL;
530 120 : recheck = false;
531 120 : recheckDistances = false;
532 120 : result = true;
533 : }
534 : else
535 : {
536 : spgLeafConsistentIn in;
537 : spgLeafConsistentOut out;
538 :
539 : /* use temp context for calling leaf_consistent */
540 2544864 : MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
541 :
542 2544864 : in.scankeys = so->keyData;
543 2544864 : in.nkeys = so->numberOfKeys;
544 2544864 : in.orderbys = so->orderByData;
545 2544864 : in.norderbys = so->numberOfNonNullOrderBys;
546 : Assert(!item->isLeaf); /* else reconstructedValue would be wrong type */
547 2544864 : in.reconstructedValue = item->value;
548 2544864 : in.traversalValue = item->traversalValue;
549 2544864 : in.level = item->level;
550 2544864 : in.returnData = so->want_itup;
551 2544864 : in.leafDatum = SGLTDATUM(leafTuple, &so->state);
552 :
553 2544864 : out.leafValue = (Datum) 0;
554 2544864 : out.recheck = false;
555 2544864 : out.distances = NULL;
556 2544864 : out.recheckDistances = false;
557 :
558 2544864 : result = DatumGetBool(FunctionCall2Coll(&so->leafConsistentFn,
559 : so->indexCollation,
560 : PointerGetDatum(&in),
561 : PointerGetDatum(&out)));
562 2544864 : recheck = out.recheck;
563 2544864 : recheckDistances = out.recheckDistances;
564 2544864 : leafValue = out.leafValue;
565 2544864 : distances = out.distances;
566 :
567 2544864 : MemoryContextSwitchTo(oldCxt);
568 : }
569 :
570 2544984 : if (result)
571 : {
572 : /* item passes the scankeys */
573 2061236 : if (so->numberOfNonNullOrderBys > 0)
574 : {
575 : /* the scan is ordered -> add the item to the queue */
576 365902 : MemoryContext oldCxt = MemoryContextSwitchTo(so->traversalCxt);
577 365902 : SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level,
578 : leafTuple,
579 : leafValue,
580 : recheck,
581 : recheckDistances,
582 : isnull,
583 : distances);
584 :
585 365902 : spgAddSearchItemToQueue(so, heapItem);
586 :
587 365902 : MemoryContextSwitchTo(oldCxt);
588 : }
589 : else
590 : {
591 : /* non-ordered scan, so report the item right away */
592 : Assert(!recheckDistances);
593 1695334 : storeRes(so, &leafTuple->heapPtr, leafValue, isnull,
594 : leafTuple, recheck, false, NULL);
595 1695334 : *reportedSome = true;
596 : }
597 : }
598 :
599 2544984 : return result;
600 : }
601 :
602 : /* A bundle initializer for inner_consistent methods */
603 : static void
604 24502 : spgInitInnerConsistentIn(spgInnerConsistentIn *in,
605 : SpGistScanOpaque so,
606 : SpGistSearchItem *item,
607 : SpGistInnerTuple innerTuple)
608 : {
609 24502 : in->scankeys = so->keyData;
610 24502 : in->orderbys = so->orderByData;
611 24502 : in->nkeys = so->numberOfKeys;
612 24502 : in->norderbys = so->numberOfNonNullOrderBys;
613 : Assert(!item->isLeaf); /* else reconstructedValue would be wrong type */
614 24502 : in->reconstructedValue = item->value;
615 24502 : in->traversalMemoryContext = so->traversalCxt;
616 24502 : in->traversalValue = item->traversalValue;
617 24502 : in->level = item->level;
618 24502 : in->returnData = so->want_itup;
619 24502 : in->allTheSame = innerTuple->allTheSame;
620 24502 : in->hasPrefix = (innerTuple->prefixSize > 0);
621 24502 : in->prefixDatum = SGITDATUM(innerTuple, &so->state);
622 24502 : in->nNodes = innerTuple->nNodes;
623 24502 : in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple);
624 24502 : }
625 :
626 : static SpGistSearchItem *
627 94354 : spgMakeInnerItem(SpGistScanOpaque so,
628 : SpGistSearchItem *parentItem,
629 : SpGistNodeTuple tuple,
630 : spgInnerConsistentOut *out, int i, bool isnull,
631 : double *distances)
632 : {
633 94354 : SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances);
634 :
635 94354 : item->heapPtr = tuple->t_tid;
636 230864 : item->level = out->levelAdds ? parentItem->level + out->levelAdds[i]
637 94354 : : parentItem->level;
638 :
639 : /* Must copy value out of temp context */
640 : /* (recall that reconstructed values are of type leafType) */
641 188708 : item->value = out->reconstructedValues
642 12528 : ? datumCopy(out->reconstructedValues[i],
643 12528 : so->state.attLeafType.attbyval,
644 12528 : so->state.attLeafType.attlen)
645 94354 : : (Datum) 0;
646 :
647 94354 : 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 94354 : item->traversalValue =
655 94354 : out->traversalValues ? out->traversalValues[i] : NULL;
656 :
657 94354 : item->isLeaf = false;
658 94354 : item->recheck = false;
659 94354 : item->recheckDistances = false;
660 :
661 94354 : return item;
662 : }
663 :
664 : static void
665 24502 : spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item,
666 : SpGistInnerTuple innerTuple, bool isnull)
667 : {
668 24502 : MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt);
669 : spgInnerConsistentOut out;
670 24502 : int nNodes = innerTuple->nNodes;
671 : int i;
672 :
673 24502 : memset(&out, 0, sizeof(out));
674 :
675 24502 : if (!isnull)
676 : {
677 : spgInnerConsistentIn in;
678 :
679 24502 : spgInitInnerConsistentIn(&in, so, item, innerTuple);
680 :
681 : /* use user-defined inner consistent method */
682 24502 : FunctionCall2Coll(&so->innerConsistentFn,
683 : so->indexCollation,
684 : PointerGetDatum(&in),
685 : PointerGetDatum(&out));
686 : }
687 : else
688 : {
689 : /* force all children to be visited */
690 0 : out.nNodes = nNodes;
691 0 : out.nodeNumbers = (int *) palloc(sizeof(int) * nNodes);
692 0 : for (i = 0; i < nNodes; i++)
693 0 : out.nodeNumbers[i] = i;
694 : }
695 :
696 : /* If allTheSame, they should all or none of them match */
697 24502 : if (innerTuple->allTheSame && out.nNodes != 0 && out.nNodes != nNodes)
698 0 : elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple");
699 :
700 24502 : if (out.nNodes)
701 : {
702 : /* collect node pointers */
703 : SpGistNodeTuple node;
704 24502 : SpGistNodeTuple *nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * nNodes);
705 :
706 226656 : SGITITERATE(innerTuple, i, node)
707 : {
708 202154 : nodes[i] = node;
709 : }
710 :
711 24502 : MemoryContextSwitchTo(so->traversalCxt);
712 :
713 185930 : for (i = 0; i < out.nNodes; i++)
714 : {
715 161428 : int nodeN = out.nodeNumbers[i];
716 : SpGistSearchItem *innerItem;
717 : double *distances;
718 :
719 : Assert(nodeN >= 0 && nodeN < nNodes);
720 :
721 161428 : node = nodes[nodeN];
722 :
723 161428 : if (!ItemPointerIsValid(&node->t_tid))
724 67074 : 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 94354 : distances = out.distances ? out.distances[i] : so->infDistances;
731 :
732 94354 : innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull,
733 : distances);
734 :
735 94354 : spgAddSearchItemToQueue(so, innerItem);
736 : }
737 : }
738 :
739 24502 : MemoryContextSwitchTo(oldCxt);
740 24502 : }
741 :
742 : /* Returns a next item in an (ordered) scan or null if the index is exhausted */
743 : static SpGistSearchItem *
744 459366 : spgGetNextQueueItem(SpGistScanOpaque so)
745 : {
746 459366 : if (pairingheap_is_empty(so->scanQueue))
747 886 : return NULL; /* Done when both heaps are empty */
748 :
749 : /* Return item; caller is responsible to pfree it */
750 458480 : return (SpGistSearchItem *) pairingheap_remove_first(so->scanQueue);
751 : }
752 :
753 : enum SpGistSpecialOffsetNumbers
754 : {
755 : SpGistBreakOffsetNumber = InvalidOffsetNumber,
756 : SpGistRedirectOffsetNumber = MaxOffsetNumber + 1,
757 : SpGistErrorOffsetNumber = MaxOffsetNumber + 2,
758 : };
759 :
760 : static OffsetNumber
761 2544984 : spgTestLeafTuple(SpGistScanOpaque so,
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 2544984 : PageGetItem(page, PageGetItemId(page, offset));
770 :
771 2544984 : if (leafTuple->tupstate != SPGIST_LIVE)
772 : {
773 0 : if (!isroot) /* all tuples on root should be live */
774 : {
775 0 : 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 0 : item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer;
781 : Assert(ItemPointerGetBlockNumber(&item->heapPtr) != SPGIST_METAPAGE_BLKNO);
782 0 : return SpGistRedirectOffsetNumber;
783 : }
784 :
785 0 : 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 */
790 : Assert(SGLT_GET_NEXTOFFSET(leafTuple) == InvalidOffsetNumber);
791 0 : return SpGistBreakOffsetNumber;
792 : }
793 : }
794 :
795 : /* We should not arrive at a placeholder */
796 0 : elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate);
797 : return SpGistErrorOffsetNumber;
798 : }
799 :
800 : Assert(ItemPointerIsValid(&leafTuple->heapPtr));
801 :
802 2544984 : spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes);
803 :
804 2544984 : 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 : */
814 : static void
815 377330 : spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex,
816 : storeRes_func storeRes)
817 : {
818 377330 : Buffer buffer = InvalidBuffer;
819 377330 : bool reportedSome = false;
820 :
821 835810 : while (scanWholeIndex || !reportedSome)
822 : {
823 459366 : SpGistSearchItem *item = spgGetNextQueueItem(so);
824 :
825 459366 : if (item == NULL)
826 886 : break; /* No more items in queue -> done */
827 :
828 458480 : redirect:
829 : /* Check for interrupts, just in case of infinite loop */
830 458480 : CHECK_FOR_INTERRUPTS();
831 :
832 458480 : if (item->isLeaf)
833 : {
834 : /* We store heap items in the queue only in case of ordered search */
835 : Assert(so->numberOfNonNullOrderBys > 0);
836 363354 : storeRes(so, &item->heapPtr, item->value, item->isNull,
837 363354 : item->leafTuple, item->recheck,
838 363354 : item->recheckDistances, item->distances);
839 363354 : reportedSome = true;
840 : }
841 : else
842 : {
843 95126 : BlockNumber blkno = ItemPointerGetBlockNumber(&item->heapPtr);
844 95126 : OffsetNumber offset = ItemPointerGetOffsetNumber(&item->heapPtr);
845 : Page page;
846 : bool isnull;
847 :
848 95126 : if (buffer == InvalidBuffer)
849 : {
850 19872 : buffer = ReadBuffer(index, blkno);
851 19872 : LockBuffer(buffer, BUFFER_LOCK_SHARE);
852 : }
853 75254 : else if (blkno != BufferGetBlockNumber(buffer))
854 : {
855 51946 : UnlockReleaseBuffer(buffer);
856 51946 : buffer = ReadBuffer(index, blkno);
857 51946 : LockBuffer(buffer, BUFFER_LOCK_SHARE);
858 : }
859 :
860 : /* else new pointer points to the same page, no work needed */
861 :
862 95126 : page = BufferGetPage(buffer);
863 :
864 95126 : isnull = SpGistPageStoresNulls(page) ? true : false;
865 :
866 95126 : if (SpGistPageIsLeaf(page))
867 : {
868 : /* Page is a leaf - that is, all it's tuples are heap items */
869 70624 : OffsetNumber max = PageGetMaxOffsetNumber(page);
870 :
871 70624 : if (SpGistBlockIsRoot(blkno))
872 : {
873 : /* When root is a leaf, examine all its tuples */
874 6126 : for (offset = FirstOffsetNumber; offset <= max; offset++)
875 5928 : (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 2609482 : while (offset != InvalidOffsetNumber)
883 : {
884 : Assert(offset >= FirstOffsetNumber && offset <= max);
885 2539056 : offset = spgTestLeafTuple(so, item, page, offset,
886 : isnull, false,
887 : &reportedSome, storeRes);
888 2539056 : if (offset == SpGistRedirectOffsetNumber)
889 0 : goto redirect;
890 : }
891 : }
892 : }
893 : else /* page is inner */
894 : {
895 : SpGistInnerTuple innerTuple = (SpGistInnerTuple)
896 24502 : PageGetItem(page, PageGetItemId(page, offset));
897 :
898 24502 : if (innerTuple->tupstate != SPGIST_LIVE)
899 : {
900 0 : if (innerTuple->tupstate == SPGIST_REDIRECT)
901 : {
902 : /* transfer attention to redirect point */
903 0 : item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer;
904 : Assert(ItemPointerGetBlockNumber(&item->heapPtr) !=
905 : SPGIST_METAPAGE_BLKNO);
906 0 : goto redirect;
907 : }
908 0 : elog(ERROR, "unexpected SPGiST tuple state: %d",
909 : innerTuple->tupstate);
910 : }
911 :
912 24502 : spgInnerTest(so, item, innerTuple, isnull);
913 : }
914 : }
915 :
916 : /* done with this scan item */
917 458480 : spgFreeSearchItem(so, item);
918 : /* clear temp context before proceeding to the next one */
919 458480 : MemoryContextReset(so->tempCxt);
920 : }
921 :
922 377330 : if (buffer != InvalidBuffer)
923 19872 : UnlockReleaseBuffer(buffer);
924 377330 : }
925 :
926 :
927 : /* storeRes subroutine for getbitmap case */
928 : static void
929 1052214 : storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr,
930 : Datum leafValue, bool isnull,
931 : SpGistLeafTuple leafTuple, bool recheck,
932 : bool recheckDistances, double *distances)
933 : {
934 : Assert(!recheckDistances && !distances);
935 1052214 : tbm_add_tuples(so->tbm, heapPtr, 1, recheck);
936 1052214 : so->ntids++;
937 1052214 : }
938 :
939 : int64
940 348 : spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
941 : {
942 348 : SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
943 :
944 : /* Copy want_itup to *so so we don't need to pass it around separately */
945 348 : so->want_itup = false;
946 :
947 348 : so->tbm = tbm;
948 348 : so->ntids = 0;
949 :
950 348 : spgWalk(scan->indexRelation, so, true, storeBitmap);
951 :
952 348 : return so->ntids;
953 : }
954 :
955 : /* storeRes subroutine for gettuple case */
956 : static void
957 1006474 : storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr,
958 : Datum leafValue, bool isnull,
959 : SpGistLeafTuple leafTuple, bool recheck,
960 : bool recheckDistances, double *nonNullDistances)
961 : {
962 : Assert(so->nPtrs < MaxIndexTuplesPerPage);
963 1006474 : so->heapPtrs[so->nPtrs] = *heapPtr;
964 1006474 : so->recheck[so->nPtrs] = recheck;
965 1006474 : so->recheckDistances[so->nPtrs] = recheckDistances;
966 :
967 1006474 : if (so->numberOfOrderBys > 0)
968 : {
969 363354 : if (isnull || so->numberOfNonNullOrderBys <= 0)
970 48 : so->distances[so->nPtrs] = NULL;
971 : else
972 : {
973 : IndexOrderByDistance *distances =
974 363306 : palloc(sizeof(distances[0]) * so->numberOfOrderBys);
975 : int i;
976 :
977 726630 : for (i = 0; i < so->numberOfOrderBys; i++)
978 : {
979 363324 : int offset = so->nonNullOrderByOffsets[i];
980 :
981 363324 : if (offset >= 0)
982 : {
983 : /* Copy non-NULL distance value */
984 363318 : distances[i].value = nonNullDistances[offset];
985 363318 : distances[i].isnull = false;
986 : }
987 : else
988 : {
989 : /* Set distance's NULL flag. */
990 6 : distances[i].value = 0.0;
991 6 : distances[i].isnull = true;
992 : }
993 : }
994 :
995 363306 : so->distances[so->nPtrs] = distances;
996 : }
997 : }
998 :
999 1006474 : 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 919438 : if (so->state.leafTupDesc->natts > 1)
1010 112 : spgDeformLeafTuple(leafTuple, so->state.leafTupDesc,
1011 : leafDatums, leafIsnulls, isnull);
1012 :
1013 919438 : leafDatums[spgKeyColumn] = leafValue;
1014 919438 : leafIsnulls[spgKeyColumn] = isnull;
1015 :
1016 919438 : so->reconTups[so->nPtrs] = heap_form_tuple(so->reconTupDesc,
1017 : leafDatums,
1018 : leafIsnulls);
1019 : }
1020 1006474 : so->nPtrs++;
1021 1006474 : }
1022 :
1023 : bool
1024 1006916 : spggettuple(IndexScanDesc scan, ScanDirection dir)
1025 : {
1026 1006916 : SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque;
1027 :
1028 1006916 : if (dir != ForwardScanDirection)
1029 0 : 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 1006916 : so->want_itup = scan->xs_want_itup;
1033 :
1034 : for (;;)
1035 : {
1036 1383360 : if (so->iPtr < so->nPtrs)
1037 : {
1038 : /* continuing to return reported tuples */
1039 1006378 : scan->xs_heaptid = so->heapPtrs[so->iPtr];
1040 1006378 : scan->xs_recheck = so->recheck[so->iPtr];
1041 1006378 : scan->xs_hitup = so->reconTups[so->iPtr];
1042 :
1043 1006378 : if (so->numberOfOrderBys > 0)
1044 363354 : index_store_float8_orderby_distances(scan, so->orderByTypes,
1045 363354 : so->distances[so->iPtr],
1046 363354 : so->recheckDistances[so->iPtr]);
1047 1006378 : so->iPtr++;
1048 1006378 : return true;
1049 : }
1050 :
1051 376982 : if (so->numberOfOrderBys > 0)
1052 : {
1053 : /* Must pfree distances to avoid memory leak */
1054 : int i;
1055 :
1056 726738 : for (i = 0; i < so->nPtrs; i++)
1057 363330 : if (so->distances[i])
1058 363282 : pfree(so->distances[i]);
1059 : }
1060 :
1061 376982 : if (so->want_itup)
1062 : {
1063 : /* Must pfree reconstructed tuples to avoid memory leak */
1064 : int i;
1065 :
1066 1209570 : for (i = 0; i < so->nPtrs; i++)
1067 919300 : pfree(so->reconTups[i]);
1068 : }
1069 376982 : so->iPtr = so->nPtrs = 0;
1070 :
1071 376982 : spgWalk(scan->indexRelation, so, false, storeGettuple);
1072 :
1073 376982 : if (so->nPtrs == 0)
1074 538 : break; /* must have completed scan */
1075 : }
1076 :
1077 538 : return false;
1078 : }
1079 :
1080 : bool
1081 1854 : spgcanreturn(Relation index, int attno)
1082 : {
1083 : SpGistCache *cache;
1084 :
1085 : /* INCLUDE attributes can always be fetched for index-only scans */
1086 1854 : if (attno > 1)
1087 28 : return true;
1088 :
1089 : /* We can do it if the opclass config function says so */
1090 1826 : cache = spgGetCache(index);
1091 :
1092 1826 : return cache->config.canReturnData;
1093 : }
|
