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