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