Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * gistget.c
4 : * fetch tuples from a GiST scan.
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/gist/gistget.c
12 : *
13 : *-------------------------------------------------------------------------
14 : */
15 : #include "postgres.h"
16 :
17 : #include "access/genam.h"
18 : #include "access/gist_private.h"
19 : #include "access/relscan.h"
20 : #include "lib/pairingheap.h"
21 : #include "miscadmin.h"
22 : #include "pgstat.h"
23 : #include "storage/lmgr.h"
24 : #include "storage/predicate.h"
25 : #include "utils/float.h"
26 : #include "utils/memutils.h"
27 : #include "utils/rel.h"
28 :
29 : /*
30 : * gistkillitems() -- set LP_DEAD state for items an indexscan caller has
31 : * told us were killed.
32 : *
33 : * We re-read page here, so it's important to check page LSN. If the page
34 : * has been modified since the last read (as determined by LSN), we cannot
35 : * flag any entries because it is possible that the old entry was vacuumed
36 : * away and the TID was re-used by a completely different heap tuple.
37 : */
38 : static void
2769 teodor 39 UBC 0 : gistkillitems(IndexScanDesc scan)
40 : {
2495 rhaas 41 0 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
42 : Buffer buffer;
43 : Page page;
44 : OffsetNumber offnum;
45 : ItemId iid;
46 : int i;
47 0 : bool killedsomething = false;
48 :
2769 teodor 49 0 : Assert(so->curBlkno != InvalidBlockNumber);
50 0 : Assert(!XLogRecPtrIsInvalid(so->curPageLSN));
51 0 : Assert(so->killedItems != NULL);
52 :
53 0 : buffer = ReadBuffer(scan->indexRelation, so->curBlkno);
54 0 : if (!BufferIsValid(buffer))
55 0 : return;
56 :
57 0 : LockBuffer(buffer, GIST_SHARE);
58 0 : gistcheckpage(scan->indexRelation, buffer);
2545 kgrittn 59 0 : page = BufferGetPage(buffer);
60 :
61 : /*
62 : * If page LSN differs it means that the page was modified since the last
63 : * read. killedItems could be not valid so LP_DEAD hints applying is not
64 : * safe.
65 : */
1916 alvherre 66 0 : if (BufferGetLSNAtomic(buffer) != so->curPageLSN)
67 : {
2769 teodor 68 0 : UnlockReleaseBuffer(buffer);
2495 rhaas 69 0 : so->numKilled = 0; /* reset counter */
2769 teodor 70 0 : return;
71 : }
72 :
73 0 : Assert(GistPageIsLeaf(page));
74 :
75 : /*
76 : * Mark all killedItems as dead. We need no additional recheck, because,
77 : * if page was modified, curPageLSN must have changed.
78 : */
79 0 : for (i = 0; i < so->numKilled; i++)
80 : {
81 0 : offnum = so->killedItems[i];
82 0 : iid = PageGetItemId(page, offnum);
83 0 : ItemIdMarkDead(iid);
84 0 : killedsomething = true;
85 : }
86 :
87 0 : if (killedsomething)
88 : {
89 0 : GistMarkPageHasGarbage(page);
90 0 : MarkBufferDirtyHint(buffer, true);
91 : }
92 :
93 0 : UnlockReleaseBuffer(buffer);
94 :
95 : /*
96 : * Always reset the scan state, so we don't look for same items on other
97 : * pages.
98 : */
99 0 : so->numKilled = 0;
100 : }
101 :
102 : /*
103 : * gistindex_keytest() -- does this index tuple satisfy the scan key(s)?
104 : *
105 : * The index tuple might represent either a heap tuple or a lower index page,
106 : * depending on whether the containing page is a leaf page or not.
107 : *
108 : * On success return for a heap tuple, *recheck_p is set to indicate whether
109 : * the quals need to be rechecked. We recheck if any of the consistent()
110 : * functions request it. recheck is not interesting when examining a non-leaf
111 : * entry, since we must visit the lower index page if there's any doubt.
112 : * Similarly, *recheck_distances_p is set to indicate whether the distances
113 : * need to be rechecked, and it is also ignored for non-leaf entries.
114 : *
115 : * If we are doing an ordered scan, so->distances[] is filled with distance
116 : * data from the distance() functions before returning success.
117 : *
118 : * We must decompress the key in the IndexTuple before passing it to the
119 : * sk_funcs (which actually are the opclass Consistent or Distance methods).
120 : *
121 : * Note that this function is always invoked in a short-lived memory context,
122 : * so we don't need to worry about cleaning up allocated memory, either here
123 : * or in the implementation of any Consistent or Distance methods.
124 : */
125 : static bool
4510 tgl 126 CBC 1024934 : gistindex_keytest(IndexScanDesc scan,
127 : IndexTuple tuple,
128 : Page page,
129 : OffsetNumber offset,
130 : bool *recheck_p,
131 : bool *recheck_distances_p)
132 : {
133 1024934 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
134 1024934 : GISTSTATE *giststate = so->giststate;
135 1024934 : ScanKey key = scan->keyData;
136 1024934 : int keySize = scan->numberOfKeys;
137 : IndexOrderByDistance *distance_p;
138 1024934 : Relation r = scan->indexRelation;
139 :
140 1024934 : *recheck_p = false;
2886 heikki.linnakangas 141 1024934 : *recheck_distances_p = false;
142 :
143 : /*
144 : * If it's a leftover invalid tuple from pre-9.1, treat it as a match with
145 : * minimum possible distances. This means we'll always follow it to the
146 : * referenced page.
147 : */
4510 tgl 148 1024934 : if (GistTupleIsInvalid(tuple))
149 : {
150 : int i;
151 :
2118 tgl 152 UBC 0 : if (GistPageIsLeaf(page)) /* shouldn't happen */
4343 peter_e 153 0 : elog(ERROR, "invalid GiST tuple found on leaf page");
4510 tgl 154 0 : for (i = 0; i < scan->numberOfOrderBys; i++)
155 : {
1298 akorotkov 156 0 : so->distances[i].value = -get_float8_infinity();
157 0 : so->distances[i].isnull = false;
158 : }
4510 tgl 159 0 : return true;
160 : }
161 :
162 : /* Check whether it matches according to the Consistent functions */
4510 tgl 163 CBC 1585980 : while (keySize > 0)
164 : {
165 : Datum datum;
166 : bool isNull;
167 :
168 979884 : datum = index_getattr(tuple,
169 979884 : key->sk_attno,
170 : giststate->leafTupdesc,
171 : &isNull);
172 :
173 979884 : if (key->sk_flags & SK_ISNULL)
174 : {
175 : /*
176 : * On non-leaf page we can't conclude that child hasn't NULL
177 : * values because of assumption in GiST: union (VAL, NULL) is VAL.
178 : * But if on non-leaf page key IS NULL, then all children are
179 : * NULL.
180 : */
181 23098 : if (key->sk_flags & SK_SEARCHNULL)
182 : {
183 23065 : if (GistPageIsLeaf(page) && !isNull)
184 418838 : return false;
185 : }
186 : else
187 : {
188 33 : Assert(key->sk_flags & SK_SEARCHNOTNULL);
189 33 : if (isNull)
190 3 : return false;
191 : }
192 : }
193 956786 : else if (isNull)
194 : {
195 507 : return false;
196 : }
197 : else
198 : {
199 : Datum test;
200 : bool recheck;
201 : GISTENTRY de;
202 :
203 956279 : gistdentryinit(giststate, key->sk_attno - 1, &de,
204 : datum, r, page, offset,
205 : false, isNull);
206 :
207 : /*
208 : * Call the Consistent function to evaluate the test. The
209 : * arguments are the index datum (as a GISTENTRY*), the comparison
210 : * datum, the comparison operator's strategy number and subtype
211 : * from pg_amop, and the recheck flag.
212 : *
213 : * (Presently there's no need to pass the subtype since it'll
214 : * always be zero, but might as well pass it for possible future
215 : * use.)
216 : *
217 : * We initialize the recheck flag to true (the safest assumption)
218 : * in case the Consistent function forgets to set it.
219 : */
220 956279 : recheck = true;
221 :
4380 222 1912558 : test = FunctionCall5Coll(&key->sk_func,
223 : key->sk_collation,
224 : PointerGetDatum(&de),
225 : key->sk_argument,
2637 226 956279 : Int16GetDatum(key->sk_strategy),
227 : ObjectIdGetDatum(key->sk_subtype),
228 : PointerGetDatum(&recheck));
229 :
4510 230 956279 : if (!DatumGetBool(test))
231 397121 : return false;
232 559158 : *recheck_p |= recheck;
233 : }
234 :
235 561046 : key++;
236 561046 : keySize--;
237 : }
238 :
239 : /* OK, it passes --- now let's compute the distances */
240 606096 : key = scan->orderByData;
1298 akorotkov 241 606096 : distance_p = so->distances;
4510 tgl 242 606096 : keySize = scan->numberOfOrderBys;
243 621285 : while (keySize > 0)
244 : {
245 : Datum datum;
246 : bool isNull;
247 :
248 15189 : datum = index_getattr(tuple,
249 15189 : key->sk_attno,
250 : giststate->leafTupdesc,
251 : &isNull);
252 :
253 15189 : if ((key->sk_flags & SK_ISNULL) || isNull)
254 : {
255 : /* Assume distance computes as null */
1298 akorotkov 256 54 : distance_p->value = 0.0;
257 54 : distance_p->isnull = true;
258 : }
259 : else
260 : {
261 : Datum dist;
262 : bool recheck;
263 : GISTENTRY de;
264 :
4510 tgl 265 15135 : gistdentryinit(giststate, key->sk_attno - 1, &de,
266 : datum, r, page, offset,
267 : false, isNull);
268 :
269 : /*
270 : * Call the Distance function to evaluate the distance. The
271 : * arguments are the index datum (as a GISTENTRY*), the comparison
272 : * datum, the ordering operator's strategy number and subtype from
273 : * pg_amop, and the recheck flag.
274 : *
275 : * (Presently there's no need to pass the subtype since it'll
276 : * always be zero, but might as well pass it for possible future
277 : * use.)
278 : *
279 : * If the function sets the recheck flag, the returned distance is
280 : * a lower bound on the true distance and needs to be rechecked.
281 : * We initialize the flag to 'false'. This flag was added in
282 : * version 9.5; distance functions written before that won't know
283 : * about the flag, but are expected to never be lossy.
284 : */
2886 heikki.linnakangas 285 15135 : recheck = false;
286 30270 : dist = FunctionCall5Coll(&key->sk_func,
287 : key->sk_collation,
288 : PointerGetDatum(&de),
289 : key->sk_argument,
2637 tgl 290 15135 : Int16GetDatum(key->sk_strategy),
291 : ObjectIdGetDatum(key->sk_subtype),
292 : PointerGetDatum(&recheck));
2886 heikki.linnakangas 293 15135 : *recheck_distances_p |= recheck;
1298 akorotkov 294 15135 : distance_p->value = DatumGetFloat8(dist);
295 15135 : distance_p->isnull = false;
296 : }
297 :
4510 tgl 298 15189 : key++;
1298 akorotkov 299 15189 : distance_p++;
4510 tgl 300 15189 : keySize--;
301 : }
302 :
303 606096 : return true;
304 : }
305 :
306 : /*
307 : * Scan all items on the GiST index page identified by *pageItem, and insert
308 : * them into the queue (or directly to output areas)
309 : *
310 : * scan: index scan we are executing
311 : * pageItem: search queue item identifying an index page to scan
312 : * myDistances: distances array associated with pageItem, or NULL at the root
313 : * tbm: if not NULL, gistgetbitmap's output bitmap
314 : * ntids: if not NULL, gistgetbitmap's output tuple counter
315 : *
316 : * If tbm/ntids aren't NULL, we are doing an amgetbitmap scan, and heap
317 : * tuples should be reported directly into the bitmap. If they are NULL,
318 : * we're doing a plain or ordered indexscan. For a plain indexscan, heap
319 : * tuple TIDs are returned into so->pageData[]. For an ordered indexscan,
320 : * heap tuple TIDs are pushed into individual search queue items. In an
321 : * index-only scan, reconstructed index tuples are returned along with the
322 : * TIDs.
323 : *
324 : * If we detect that the index page has split since we saw its downlink
325 : * in the parent, we push its new right sibling onto the queue so the
326 : * sibling will be processed next.
327 : */
328 : static void
1309 akorotkov 329 35025 : gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
330 : IndexOrderByDistance *myDistances, TIDBitmap *tbm, int64 *ntids)
331 : {
4510 tgl 332 35025 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
2936 heikki.linnakangas 333 35025 : GISTSTATE *giststate = so->giststate;
334 35025 : Relation r = scan->indexRelation;
335 : Buffer buffer;
336 : Page page;
337 : GISTPageOpaque opaque;
338 : OffsetNumber maxoff;
339 : OffsetNumber i;
340 : MemoryContext oldcxt;
341 :
4510 tgl 342 35025 : Assert(!GISTSearchItemIsHeap(*pageItem));
343 :
344 35025 : buffer = ReadBuffer(scan->indexRelation, pageItem->blkno);
345 35025 : LockBuffer(buffer, GIST_SHARE);
1839 teodor 346 35025 : PredicateLockPage(r, BufferGetBlockNumber(buffer), scan->xs_snapshot);
4510 tgl 347 35025 : gistcheckpage(scan->indexRelation, buffer);
2545 kgrittn 348 35025 : page = BufferGetPage(buffer);
349 35025 : TestForOldSnapshot(scan->xs_snapshot, r, page);
4510 tgl 350 35025 : opaque = GistPageGetOpaque(page);
351 :
352 : /*
353 : * Check if we need to follow the rightlink. We need to follow it if the
354 : * page was concurrently split since we visited the parent (in which case
355 : * parentlsn < nsn), or if the system crashed after a page split but
356 : * before the downlink was inserted into the parent.
357 : */
358 35025 : if (!XLogRecPtrIsInvalid(pageItem->data.parentlsn) &&
4490 heikki.linnakangas 359 67444 : (GistFollowRight(page) ||
3734 360 33722 : pageItem->data.parentlsn < GistPageGetNSN(page)) &&
4510 tgl 361 UBC 0 : opaque->rightlink != InvalidBlockNumber /* sanity check */ )
362 : {
363 : /* There was a page split, follow right link to add pages */
364 : GISTSearchItem *item;
365 :
366 : /* This can't happen when starting at the root */
1298 akorotkov 367 0 : Assert(myDistances != NULL);
368 :
4510 tgl 369 0 : oldcxt = MemoryContextSwitchTo(so->queueCxt);
370 :
371 : /* Create new GISTSearchItem for the right sibling index page */
3030 heikki.linnakangas 372 0 : item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
4510 tgl 373 0 : item->blkno = opaque->rightlink;
374 0 : item->data.parentlsn = pageItem->data.parentlsn;
375 :
376 : /* Insert it into the queue using same distances as for this page */
1298 akorotkov 377 0 : memcpy(item->distances, myDistances,
378 0 : sizeof(item->distances[0]) * scan->numberOfOrderBys);
379 :
3030 heikki.linnakangas 380 0 : pairingheap_add(so->queue, &item->phNode);
381 :
4510 tgl 382 0 : MemoryContextSwitchTo(oldcxt);
383 : }
384 :
385 : /*
386 : * Check if the page was deleted after we saw the downlink. There's
387 : * nothing of interest on a deleted page. Note that we must do this after
388 : * checking the NSN for concurrent splits! It's possible that the page
389 : * originally contained some tuples that are visible to us, but was split
390 : * so that all the visible tuples were moved to another page, and then
391 : * this page was deleted.
392 : */
1355 heikki.linnakangas 393 CBC 35025 : if (GistPageIsDeleted(page))
394 : {
1355 heikki.linnakangas 395 UBC 0 : UnlockReleaseBuffer(buffer);
396 0 : return;
397 : }
398 :
4510 tgl 399 CBC 35025 : so->nPageData = so->curPageData = 0;
2166 400 35025 : scan->xs_hitup = NULL; /* might point into pageDataCxt */
2936 heikki.linnakangas 401 35025 : if (so->pageDataCxt)
402 3201 : MemoryContextReset(so->pageDataCxt);
403 :
404 : /*
405 : * We save the LSN of the page as we read it, so that we know whether it
406 : * safe to apply LP_DEAD hints to the page later. This allows us to drop
407 : * the pin for MVCC scans, which allows vacuum to avoid blocking.
408 : */
1916 alvherre 409 35025 : so->curPageLSN = BufferGetLSNAtomic(buffer);
410 :
411 : /*
412 : * check all tuples on page
413 : */
4510 tgl 414 35025 : maxoff = PageGetMaxOffsetNumber(page);
415 1059959 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
416 : {
2495 rhaas 417 1024934 : ItemId iid = PageGetItemId(page, i);
418 : IndexTuple it;
419 : bool match;
420 : bool recheck;
421 : bool recheck_distances;
422 :
423 : /*
424 : * If the scan specifies not to return killed tuples, then we treat a
425 : * killed tuple as not passing the qual.
426 : */
427 1024934 : if (scan->ignore_killed_tuples && ItemIdIsDead(iid))
2769 teodor 428 418838 : continue;
429 :
430 1024934 : it = (IndexTuple) PageGetItem(page, iid);
431 :
432 : /*
433 : * Must call gistindex_keytest in tempCxt, and clean up any leftover
434 : * junk afterward.
435 : */
4209 tgl 436 1024934 : oldcxt = MemoryContextSwitchTo(so->giststate->tempCxt);
437 :
2886 heikki.linnakangas 438 1024934 : match = gistindex_keytest(scan, it, page, i,
439 : &recheck, &recheck_distances);
440 :
4510 tgl 441 1024934 : MemoryContextSwitchTo(oldcxt);
4209 442 1024934 : MemoryContextReset(so->giststate->tempCxt);
443 :
444 : /* Ignore tuple if it doesn't match */
4510 445 1024934 : if (!match)
446 418838 : continue;
447 :
448 606096 : if (tbm && GistPageIsLeaf(page))
449 : {
450 : /*
451 : * getbitmap scan, so just push heap tuple TIDs into the bitmap
452 : * without worrying about ordering
453 : */
454 179006 : tbm_add_tuples(tbm, &it->t_tid, 1, recheck);
455 179006 : (*ntids)++;
456 : }
457 427090 : else if (scan->numberOfOrderBys == 0 && GistPageIsLeaf(page))
458 : {
459 : /*
460 : * Non-ordered scan, so report tuples in so->pageData[]
461 : */
462 378342 : so->pageData[so->nPageData].heapPtr = it->t_tid;
463 378342 : so->pageData[so->nPageData].recheck = recheck;
2769 teodor 464 378342 : so->pageData[so->nPageData].offnum = i;
465 :
466 : /*
467 : * In an index-only scan, also fetch the data from the tuple. The
468 : * reconstructed tuples are stored in pageDataCxt.
469 : */
2936 heikki.linnakangas 470 378342 : if (scan->xs_want_itup)
471 : {
472 258739 : oldcxt = MemoryContextSwitchTo(so->pageDataCxt);
2232 tgl 473 517478 : so->pageData[so->nPageData].recontup =
2936 heikki.linnakangas 474 258739 : gistFetchTuple(giststate, r, it);
475 258739 : MemoryContextSwitchTo(oldcxt);
476 : }
4510 tgl 477 378342 : so->nPageData++;
478 : }
479 : else
480 : {
481 : /*
482 : * Must push item into search queue. We get here for any lower
483 : * index page, and also for heap tuples if doing an ordered
484 : * search.
485 : */
486 : GISTSearchItem *item;
1309 akorotkov 487 48748 : int nOrderBys = scan->numberOfOrderBys;
488 :
4510 tgl 489 48748 : oldcxt = MemoryContextSwitchTo(so->queueCxt);
490 :
491 : /* Create new GISTSearchItem for this item */
3030 heikki.linnakangas 492 48748 : item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
493 :
4510 tgl 494 48748 : if (GistPageIsLeaf(page))
495 : {
496 : /* Creating heap-tuple GISTSearchItem */
497 13437 : item->blkno = InvalidBlockNumber;
498 13437 : item->data.heap.heapPtr = it->t_tid;
499 13437 : item->data.heap.recheck = recheck;
2886 heikki.linnakangas 500 13437 : item->data.heap.recheckDistances = recheck_distances;
501 :
502 : /*
503 : * In an index-only scan, also fetch the data from the tuple.
504 : */
2936 505 13437 : if (scan->xs_want_itup)
2232 tgl 506 6363 : item->data.heap.recontup = gistFetchTuple(giststate, r, it);
507 : }
508 : else
509 : {
510 : /* Creating index-page GISTSearchItem */
4510 511 35311 : item->blkno = ItemPointerGetBlockNumber(&it->t_tid);
512 :
513 : /*
514 : * LSN of current page is lsn of parent page for child. We
515 : * only have a shared lock, so we need to get the LSN
516 : * atomically.
517 : */
3670 simon 518 35311 : item->data.parentlsn = BufferGetLSNAtomic(buffer);
519 : }
520 :
521 : /* Insert it into the queue using new distance data */
1298 akorotkov 522 48748 : memcpy(item->distances, so->distances,
523 : sizeof(item->distances[0]) * nOrderBys);
524 :
3030 heikki.linnakangas 525 48748 : pairingheap_add(so->queue, &item->phNode);
526 :
4510 tgl 527 48748 : MemoryContextSwitchTo(oldcxt);
528 : }
529 : }
530 :
531 35025 : UnlockReleaseBuffer(buffer);
532 : }
533 :
534 : /*
535 : * Extract next item (in order) from search queue
536 : *
537 : * Returns a GISTSearchItem or NULL. Caller must pfree item when done with it.
538 : */
539 : static GISTSearchItem *
540 35539 : getNextGISTSearchItem(GISTScanOpaque so)
541 : {
542 : GISTSearchItem *item;
543 :
3030 heikki.linnakangas 544 35539 : if (!pairingheap_is_empty(so->queue))
545 : {
546 34345 : item = (GISTSearchItem *) pairingheap_remove_first(so->queue);
547 : }
548 : else
549 : {
550 : /* Done when both heaps are empty */
551 1194 : item = NULL;
552 : }
553 :
554 : /* Return item; caller is responsible to pfree it */
555 35539 : return item;
556 : }
557 :
558 : /*
559 : * Fetch next heap tuple in an ordered search
560 : */
561 : static bool
4510 tgl 562 644 : getNextNearest(IndexScanDesc scan)
563 : {
564 644 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
565 644 : bool res = false;
566 :
2232 567 644 : if (scan->xs_hitup)
568 : {
569 : /* free previously returned tuple */
570 425 : pfree(scan->xs_hitup);
571 425 : scan->xs_hitup = NULL;
572 : }
573 :
574 : do
575 : {
4510 576 807 : GISTSearchItem *item = getNextGISTSearchItem(so);
577 :
578 807 : if (!item)
579 21 : break;
580 :
581 786 : if (GISTSearchItemIsHeap(*item))
582 : {
583 : /* found a heap item at currently minimal distance */
1490 andres 584 623 : scan->xs_heaptid = item->data.heap.heapPtr;
4510 tgl 585 623 : scan->xs_recheck = item->data.heap.recheck;
586 :
1663 akorotkov 587 623 : index_store_float8_orderby_distances(scan, so->orderByTypes,
1298 588 623 : item->distances,
1663 589 623 : item->data.heap.recheckDistances);
590 :
591 : /* in an index-only scan, also return the reconstructed tuple. */
2936 heikki.linnakangas 592 623 : if (scan->xs_want_itup)
2232 tgl 593 459 : scan->xs_hitup = item->data.heap.recontup;
4510 594 623 : res = true;
595 : }
596 : else
597 : {
598 : /* visit an index page, extract its items into queue */
599 163 : CHECK_FOR_INTERRUPTS();
600 :
1298 akorotkov 601 163 : gistScanPage(scan, item, item->distances, NULL, NULL);
602 : }
603 :
4510 tgl 604 786 : pfree(item);
605 786 : } while (!res);
606 :
607 644 : return res;
608 : }
609 :
610 : /*
611 : * gistgettuple() -- Get the next tuple in the scan
612 : */
613 : bool
2639 614 379596 : gistgettuple(IndexScanDesc scan, ScanDirection dir)
615 : {
4510 616 379596 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
617 :
618 379596 : if (dir != ForwardScanDirection)
4510 tgl 619 UBC 0 : elog(ERROR, "GiST only supports forward scan direction");
620 :
4510 tgl 621 CBC 379596 : if (!so->qual_ok)
2639 tgl 622 UBC 0 : return false;
623 :
4510 tgl 624 CBC 379596 : if (so->firstCall)
625 : {
626 : /* Begin the scan by processing the root page */
627 : GISTSearchItem fakeItem;
628 :
629 777 : pgstat_count_index_scan(scan->indexRelation);
630 :
631 777 : so->firstCall = false;
632 777 : so->curPageData = so->nPageData = 0;
2166 633 777 : scan->xs_hitup = NULL;
2936 heikki.linnakangas 634 777 : if (so->pageDataCxt)
635 340 : MemoryContextReset(so->pageDataCxt);
636 :
4510 tgl 637 777 : fakeItem.blkno = GIST_ROOT_BLKNO;
638 777 : memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
1298 akorotkov 639 777 : gistScanPage(scan, &fakeItem, NULL, NULL, NULL);
640 : }
641 :
4510 tgl 642 379596 : if (scan->numberOfOrderBys > 0)
643 : {
644 : /* Must fetch tuples in strict distance order */
2639 645 644 : return getNextNearest(scan);
646 : }
647 : else
648 : {
649 : /* Fetch tuples index-page-at-a-time */
650 : for (;;)
651 : {
4510 652 385838 : if (so->curPageData < so->nPageData)
653 : {
2769 teodor 654 378305 : if (scan->kill_prior_tuple && so->curPageData > 0)
655 : {
656 :
657 6 : if (so->killedItems == NULL)
658 : {
659 : MemoryContext oldCxt =
2495 rhaas 660 6 : MemoryContextSwitchTo(so->giststate->scanCxt);
661 :
2769 teodor 662 6 : so->killedItems =
663 6 : (OffsetNumber *) palloc(MaxIndexTuplesPerPage
664 : * sizeof(OffsetNumber));
665 :
666 6 : MemoryContextSwitchTo(oldCxt);
667 : }
668 6 : if (so->numKilled < MaxIndexTuplesPerPage)
669 6 : so->killedItems[so->numKilled++] =
670 6 : so->pageData[so->curPageData - 1].offnum;
671 : }
672 : /* continuing to return tuples from a leaf page */
1490 andres 673 378305 : scan->xs_heaptid = so->pageData[so->curPageData].heapPtr;
4510 tgl 674 378305 : scan->xs_recheck = so->pageData[so->curPageData].recheck;
675 :
676 : /* in an index-only scan, also return the reconstructed tuple */
2936 heikki.linnakangas 677 378305 : if (scan->xs_want_itup)
2232 tgl 678 258739 : scan->xs_hitup = so->pageData[so->curPageData].recontup;
679 :
4510 680 378305 : so->curPageData++;
681 :
2639 682 378305 : return true;
683 : }
684 :
685 : /*
686 : * Check the last returned tuple and add it to killedItems if
687 : * necessary
688 : */
2769 teodor 689 7533 : if (scan->kill_prior_tuple
2769 teodor 690 UBC 0 : && so->curPageData > 0
691 0 : && so->curPageData == so->nPageData)
692 : {
693 :
694 0 : if (so->killedItems == NULL)
695 : {
696 : MemoryContext oldCxt =
2495 rhaas 697 0 : MemoryContextSwitchTo(so->giststate->scanCxt);
698 :
2769 teodor 699 0 : so->killedItems =
700 0 : (OffsetNumber *) palloc(MaxIndexTuplesPerPage
701 : * sizeof(OffsetNumber));
702 :
703 0 : MemoryContextSwitchTo(oldCxt);
704 : }
705 0 : if (so->numKilled < MaxIndexTuplesPerPage)
706 0 : so->killedItems[so->numKilled++] =
707 0 : so->pageData[so->curPageData - 1].offnum;
708 : }
709 : /* find and process the next index page */
710 : do
711 : {
712 : GISTSearchItem *item;
713 :
2769 teodor 714 CBC 10083 : if ((so->curBlkno != InvalidBlockNumber) && (so->numKilled > 0))
2769 teodor 715 UBC 0 : gistkillitems(scan);
716 :
2769 teodor 717 CBC 10083 : item = getNextGISTSearchItem(so);
718 :
4510 tgl 719 10083 : if (!item)
2639 720 647 : return false;
721 :
4510 722 9436 : CHECK_FOR_INTERRUPTS();
723 :
724 : /* save current item BlockNumber for next gistkillitems() call */
2769 teodor 725 9436 : so->curBlkno = item->blkno;
726 :
727 : /*
728 : * While scanning a leaf page, ItemPointers of matching heap
729 : * tuples are stored in so->pageData. If there are any on
730 : * this page, we fall out of the inner "do" and loop around to
731 : * return them.
732 : */
1298 akorotkov 733 9436 : gistScanPage(scan, item, item->distances, NULL, NULL);
734 :
4510 tgl 735 9436 : pfree(item);
736 9436 : } while (so->nPageData == 0);
737 : }
738 : }
739 : }
740 :
741 : /*
742 : * gistgetbitmap() -- Get a bitmap of all heap tuple locations
743 : */
744 : int64
2639 745 526 : gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
746 : {
4510 747 526 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
748 526 : int64 ntids = 0;
749 : GISTSearchItem fakeItem;
750 :
751 526 : if (!so->qual_ok)
2639 tgl 752 UBC 0 : return 0;
753 :
4510 tgl 754 CBC 526 : pgstat_count_index_scan(scan->indexRelation);
755 :
756 : /* Begin the scan by processing the root page */
757 526 : so->curPageData = so->nPageData = 0;
2166 758 526 : scan->xs_hitup = NULL;
2936 heikki.linnakangas 759 526 : if (so->pageDataCxt)
2936 heikki.linnakangas 760 UBC 0 : MemoryContextReset(so->pageDataCxt);
761 :
4510 tgl 762 CBC 526 : fakeItem.blkno = GIST_ROOT_BLKNO;
763 526 : memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
1298 akorotkov 764 526 : gistScanPage(scan, &fakeItem, NULL, tbm, &ntids);
765 :
766 : /*
767 : * While scanning a leaf page, ItemPointers of matching heap tuples will
768 : * be stored directly into tbm, so we don't need to deal with them here.
769 : */
770 : for (;;)
9345 bruce 771 24123 : {
4510 tgl 772 24649 : GISTSearchItem *item = getNextGISTSearchItem(so);
773 :
774 24649 : if (!item)
9345 bruce 775 526 : break;
776 :
4510 tgl 777 24123 : CHECK_FOR_INTERRUPTS();
778 :
1298 akorotkov 779 24123 : gistScanPage(scan, item, item->distances, tbm, &ntids);
780 :
4510 tgl 781 24123 : pfree(item);
782 : }
783 :
2639 784 526 : return ntids;
785 : }
786 :
787 : /*
788 : * Can we do index-only scans on the given index column?
789 : *
790 : * Opclasses that implement a fetch function support index-only scans.
791 : * Opclasses without compression functions also support index-only scans.
792 : * Included attributes always can be fetched for index-only scans.
793 : */
794 : bool
795 1741 : gistcanreturn(Relation index, int attno)
796 : {
1491 akorotkov 797 3419 : if (attno > IndexRelationGetNumberOfKeyAttributes(index) ||
798 2838 : OidIsValid(index_getprocid(index, attno, GIST_FETCH_PROC)) ||
2028 tgl 799 1160 : !OidIsValid(index_getprocid(index, attno, GIST_COMPRESS_PROC)))
2639 800 883 : return true;
801 : else
802 858 : return false;
803 : }
|
