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