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
3840 teodor@sigaev.ru 39 :GBC 1 : gistkillitems(IndexScanDesc scan)
40 : : {
3566 rhaas@postgresql.org 41 : 1 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
42 : : Buffer buffer;
43 : : Page page;
44 : : OffsetNumber offnum;
45 : : ItemId iid;
46 : : int i;
47 : 1 : bool killedsomething = false;
48 : :
3840 teodor@sigaev.ru 49 [ - + ]: 1 : Assert(so->curBlkno != InvalidBlockNumber);
129 alvherre@kurilemu.de 50 [ - + ]:GNC 1 : Assert(XLogRecPtrIsValid(so->curPageLSN));
3840 teodor@sigaev.ru 51 [ - + ]:GBC 1 : Assert(so->killedItems != NULL);
52 : :
53 : 1 : buffer = ReadBuffer(scan->indexRelation, so->curBlkno);
54 [ - + ]: 1 : if (!BufferIsValid(buffer))
3840 teodor@sigaev.ru 55 :UBC 0 : return;
56 : :
3840 teodor@sigaev.ru 57 :GBC 1 : LockBuffer(buffer, GIST_SHARE);
58 : 1 : gistcheckpage(scan->indexRelation, buffer);
3616 kgrittn@postgresql.o 59 : 1 : 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 : : */
2987 alvherre@alvh.no-ip. 66 [ - + ]: 1 : if (BufferGetLSNAtomic(buffer) != so->curPageLSN)
5 andres@anarazel.de 67 :UNC 0 : goto unlock;
68 : :
3840 teodor@sigaev.ru 69 [ - + ]:GBC 1 : 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 [ + + ]: 2 : for (i = 0; i < so->numKilled; i++)
76 : : {
5 andres@anarazel.de 77 [ + - ]:GNC 1 : 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 [ - + ]: 1 : if (!BufferBeginSetHintBits(buffer))
5 andres@anarazel.de 85 :UNC 0 : goto unlock;
86 : : }
87 : :
3840 teodor@sigaev.ru 88 :GBC 1 : offnum = so->killedItems[i];
89 : 1 : iid = PageGetItemId(page, offnum);
90 : 1 : ItemIdMarkDead(iid);
91 : 1 : killedsomething = true;
92 : : }
93 : :
94 [ - + ]: 1 : if (killedsomething)
95 : : {
96 : 1 : GistMarkPageHasGarbage(page);
5 andres@anarazel.de 97 :GNC 1 : BufferFinishSetHintBits(buffer, true, true);
98 : : }
99 : :
5 andres@anarazel.de 100 :UNC 0 : unlock:
3840 teodor@sigaev.ru 101 :GBC 1 : UnlockReleaseBuffer(buffer);
102 : :
103 : : /*
104 : : * Always reset the scan state, so we don't look for same items on other
105 : : * pages.
106 : : */
107 : 1 : 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
5581 tgl@sss.pgh.pa.us 134 :CBC 1058733 : gistindex_keytest(IndexScanDesc scan,
135 : : IndexTuple tuple,
136 : : Page page,
137 : : OffsetNumber offset,
138 : : bool *recheck_p,
139 : : bool *recheck_distances_p)
140 : : {
141 : 1058733 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
142 : 1058733 : GISTSTATE *giststate = so->giststate;
143 : 1058733 : ScanKey key = scan->keyData;
144 : 1058733 : int keySize = scan->numberOfKeys;
145 : : IndexOrderByDistance *distance_p;
146 : 1058733 : Relation r = scan->indexRelation;
147 : :
148 : 1058733 : *recheck_p = false;
3957 heikki.linnakangas@i 149 : 1058733 : *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 : : */
5581 tgl@sss.pgh.pa.us 156 [ - + ]: 1058733 : if (GistTupleIsInvalid(tuple))
157 : : {
158 : : int i;
159 : :
3189 tgl@sss.pgh.pa.us 160 [ # # ]:UBC 0 : if (GistPageIsLeaf(page)) /* shouldn't happen */
5414 peter_e@gmx.net 161 [ # # ]: 0 : elog(ERROR, "invalid GiST tuple found on leaf page");
5581 tgl@sss.pgh.pa.us 162 [ # # ]: 0 : for (i = 0; i < scan->numberOfOrderBys; i++)
163 : : {
2369 akorotkov@postgresql 164 : 0 : so->distances[i].value = -get_float8_infinity();
165 : 0 : so->distances[i].isnull = false;
166 : : }
5581 tgl@sss.pgh.pa.us 167 : 0 : return true;
168 : : }
169 : :
170 : : /* Check whether it matches according to the Consistent functions */
5581 tgl@sss.pgh.pa.us 171 [ + + ]:CBC 1639369 : while (keySize > 0)
172 : : {
173 : : Datum datum;
174 : : bool isNull;
175 : :
176 : 1016006 : datum = index_getattr(tuple,
177 : 1016006 : key->sk_attno,
178 : : giststate->leafTupdesc,
179 : : &isNull);
180 : :
181 [ + + ]: 1016006 : 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 [ + + ]: 23098 : if (key->sk_flags & SK_SEARCHNULL)
190 : : {
191 [ + + + + ]: 23065 : if (GistPageIsLeaf(page) && !isNull)
192 : 435370 : return false;
193 : : }
194 : : else
195 : : {
196 [ - + ]: 33 : Assert(key->sk_flags & SK_SEARCHNOTNULL);
197 [ + + ]: 33 : if (isNull)
198 : 3 : return false;
199 : : }
200 : : }
201 [ + + ]: 992908 : else if (isNull)
202 : : {
203 : 1684 : return false;
204 : : }
205 : : else
206 : : {
207 : : Datum test;
208 : : bool recheck;
209 : : GISTENTRY de;
210 : :
211 : 991224 : 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 : 991224 : recheck = true;
229 : :
5451 230 : 1982448 : test = FunctionCall5Coll(&key->sk_func,
231 : : key->sk_collation,
232 : : PointerGetDatum(&de),
233 : : key->sk_argument,
60 michael@paquier.xyz 234 :GNC 991224 : UInt16GetDatum(key->sk_strategy),
235 : : ObjectIdGetDatum(key->sk_subtype),
236 : : PointerGetDatum(&recheck));
237 : :
5581 tgl@sss.pgh.pa.us 238 [ + + ]:CBC 991224 : if (!DatumGetBool(test))
239 : 412476 : return false;
240 : 578748 : *recheck_p |= recheck;
241 : : }
242 : :
243 : 580636 : key++;
244 : 580636 : keySize--;
245 : : }
246 : :
247 : : /* OK, it passes --- now let's compute the distances */
248 : 623363 : key = scan->orderByData;
2369 akorotkov@postgresql 249 : 623363 : distance_p = so->distances;
5581 tgl@sss.pgh.pa.us 250 : 623363 : keySize = scan->numberOfOrderBys;
251 [ + + ]: 639029 : while (keySize > 0)
252 : : {
253 : : Datum datum;
254 : : bool isNull;
255 : :
256 : 15666 : datum = index_getattr(tuple,
257 : 15666 : key->sk_attno,
258 : : giststate->leafTupdesc,
259 : : &isNull);
260 : :
261 [ + - + + ]: 15666 : if ((key->sk_flags & SK_ISNULL) || isNull)
262 : : {
263 : : /* Assume distance computes as null */
2369 akorotkov@postgresql 264 : 54 : distance_p->value = 0.0;
265 : 54 : distance_p->isnull = true;
266 : : }
267 : : else
268 : : {
269 : : Datum dist;
270 : : bool recheck;
271 : : GISTENTRY de;
272 : :
5581 tgl@sss.pgh.pa.us 273 : 15612 : 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 : : */
3957 heikki.linnakangas@i 293 : 15612 : recheck = false;
294 : 31224 : dist = FunctionCall5Coll(&key->sk_func,
295 : : key->sk_collation,
296 : : PointerGetDatum(&de),
297 : : key->sk_argument,
60 michael@paquier.xyz 298 :GNC 15612 : UInt16GetDatum(key->sk_strategy),
299 : : ObjectIdGetDatum(key->sk_subtype),
300 : : PointerGetDatum(&recheck));
3957 heikki.linnakangas@i 301 :CBC 15612 : *recheck_distances_p |= recheck;
2369 akorotkov@postgresql 302 : 15612 : distance_p->value = DatumGetFloat8(dist);
303 : 15612 : distance_p->isnull = false;
304 : : }
305 : :
5581 tgl@sss.pgh.pa.us 306 : 15666 : key++;
2369 akorotkov@postgresql 307 : 15666 : distance_p++;
5581 tgl@sss.pgh.pa.us 308 : 15666 : keySize--;
309 : : }
310 : :
311 : 623363 : 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
2380 akorotkov@postgresql 337 : 39161 : gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
338 : : IndexOrderByDistance *myDistances, TIDBitmap *tbm, int64 *ntids)
339 : : {
5581 tgl@sss.pgh.pa.us 340 : 39161 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
4007 heikki.linnakangas@i 341 : 39161 : GISTSTATE *giststate = so->giststate;
342 : 39161 : Relation r = scan->indexRelation;
343 : : Buffer buffer;
344 : : Page page;
345 : : GISTPageOpaque opaque;
346 : : OffsetNumber maxoff;
347 : : OffsetNumber i;
348 : : MemoryContext oldcxt;
349 : :
5581 tgl@sss.pgh.pa.us 350 [ - + ]: 39161 : Assert(!GISTSearchItemIsHeap(*pageItem));
351 : :
352 : 39161 : buffer = ReadBuffer(scan->indexRelation, pageItem->blkno);
353 : 39161 : LockBuffer(buffer, GIST_SHARE);
2910 teodor@sigaev.ru 354 : 39161 : PredicateLockPage(r, BufferGetBlockNumber(buffer), scan->xs_snapshot);
5581 tgl@sss.pgh.pa.us 355 : 39161 : gistcheckpage(scan->indexRelation, buffer);
3616 kgrittn@postgresql.o 356 : 39161 : page = BufferGetPage(buffer);
5581 tgl@sss.pgh.pa.us 357 : 39161 : 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 : : */
129 alvherre@kurilemu.de 365 [ + + ]:GNC 39161 : if (XLogRecPtrIsValid(pageItem->data.parentlsn) &&
5561 heikki.linnakangas@i 366 [ + - - + ]:CBC 72310 : (GistFollowRight(page) ||
4805 367 : 36155 : pageItem->data.parentlsn < GistPageGetNSN(page)) &&
5581 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 */
2369 akorotkov@postgresql 374 [ # # ]: 0 : Assert(myDistances != NULL);
375 : :
5581 tgl@sss.pgh.pa.us 376 : 0 : oldcxt = MemoryContextSwitchTo(so->queueCxt);
377 : :
378 : : /* Create new GISTSearchItem for the right sibling index page */
4101 heikki.linnakangas@i 379 : 0 : item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
5581 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 */
2369 akorotkov@postgresql 384 : 0 : memcpy(item->distances, myDistances,
385 : 0 : sizeof(item->distances[0]) * scan->numberOfOrderBys);
386 : :
4101 heikki.linnakangas@i 387 : 0 : pairingheap_add(so->queue, &item->phNode);
388 : :
5581 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 : : */
2426 heikki.linnakangas@i 400 [ - + ]:CBC 39161 : if (GistPageIsDeleted(page))
401 : : {
2426 heikki.linnakangas@i 402 :UBC 0 : UnlockReleaseBuffer(buffer);
403 : 0 : return;
404 : : }
405 : :
5581 tgl@sss.pgh.pa.us 406 :CBC 39161 : so->nPageData = so->curPageData = 0;
3237 407 : 39161 : scan->xs_hitup = NULL; /* might point into pageDataCxt */
4007 heikki.linnakangas@i 408 [ + + ]: 39161 : if (so->pageDataCxt)
409 : 3007 : MemoryContextReset(so->pageDataCxt);
410 : :
411 : : /*
412 : : * We save the LSN of the page as we read it, so that we know whether it
413 : : * is safe to apply LP_DEAD hints to the page later. This allows us to
414 : : * drop the pin for MVCC scans, which allows vacuum to avoid blocking.
415 : : */
2987 alvherre@alvh.no-ip. 416 : 39161 : so->curPageLSN = BufferGetLSNAtomic(buffer);
417 : :
418 : : /*
419 : : * check all tuples on page
420 : : */
5581 tgl@sss.pgh.pa.us 421 : 39161 : maxoff = PageGetMaxOffsetNumber(page);
422 [ + + ]: 1097895 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
423 : : {
3566 rhaas@postgresql.org 424 : 1058734 : ItemId iid = PageGetItemId(page, i);
425 : : IndexTuple it;
426 : : bool match;
427 : : bool recheck;
428 : : bool recheck_distances;
429 : :
430 : : /*
431 : : * If the scan specifies not to return killed tuples, then we treat a
432 : : * killed tuple as not passing the qual.
433 : : */
434 [ + - + + ]: 1058734 : if (scan->ignore_killed_tuples && ItemIdIsDead(iid))
3840 teodor@sigaev.ru 435 : 435371 : continue;
436 : :
437 : 1058733 : it = (IndexTuple) PageGetItem(page, iid);
438 : :
439 : : /*
440 : : * Must call gistindex_keytest in tempCxt, and clean up any leftover
441 : : * junk afterward.
442 : : */
5280 tgl@sss.pgh.pa.us 443 : 1058733 : oldcxt = MemoryContextSwitchTo(so->giststate->tempCxt);
444 : :
3957 heikki.linnakangas@i 445 : 1058733 : match = gistindex_keytest(scan, it, page, i,
446 : : &recheck, &recheck_distances);
447 : :
5581 tgl@sss.pgh.pa.us 448 : 1058733 : MemoryContextSwitchTo(oldcxt);
5280 449 : 1058733 : MemoryContextReset(so->giststate->tempCxt);
450 : :
451 : : /* Ignore tuple if it doesn't match */
5581 452 [ + + ]: 1058733 : if (!match)
453 : 435370 : continue;
454 : :
455 [ + + + + ]: 623363 : if (tbm && GistPageIsLeaf(page))
456 : : {
457 : : /*
458 : : * getbitmap scan, so just push heap tuple TIDs into the bitmap
459 : : * without worrying about ordering
460 : : */
461 : 198079 : tbm_add_tuples(tbm, &it->t_tid, 1, recheck);
462 : 198079 : (*ntids)++;
463 : : }
464 [ + + + + ]: 425284 : else if (scan->numberOfOrderBys == 0 && GistPageIsLeaf(page))
465 : : {
466 : : /*
467 : : * Non-ordered scan, so report tuples in so->pageData[]
468 : : */
469 : 373624 : so->pageData[so->nPageData].heapPtr = it->t_tid;
470 : 373624 : so->pageData[so->nPageData].recheck = recheck;
3840 teodor@sigaev.ru 471 : 373624 : so->pageData[so->nPageData].offnum = i;
472 : :
473 : : /*
474 : : * In an index-only scan, also fetch the data from the tuple. The
475 : : * reconstructed tuples are stored in pageDataCxt.
476 : : */
4007 heikki.linnakangas@i 477 [ + + ]: 373624 : if (scan->xs_want_itup)
478 : : {
479 : 258739 : oldcxt = MemoryContextSwitchTo(so->pageDataCxt);
3303 tgl@sss.pgh.pa.us 480 : 517478 : so->pageData[so->nPageData].recontup =
4007 heikki.linnakangas@i 481 : 258739 : gistFetchTuple(giststate, r, it);
482 : 258739 : MemoryContextSwitchTo(oldcxt);
483 : : }
5581 tgl@sss.pgh.pa.us 484 : 373624 : so->nPageData++;
485 : : }
486 : : else
487 : : {
488 : : /*
489 : : * Must push item into search queue. We get here for any lower
490 : : * index page, and also for heap tuples if doing an ordered
491 : : * search.
492 : : */
493 : : GISTSearchItem *item;
2380 akorotkov@postgresql 494 : 51660 : int nOrderBys = scan->numberOfOrderBys;
495 : :
5581 tgl@sss.pgh.pa.us 496 : 51660 : oldcxt = MemoryContextSwitchTo(so->queueCxt);
497 : :
498 : : /* Create new GISTSearchItem for this item */
4101 heikki.linnakangas@i 499 : 51660 : item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
500 : :
5581 tgl@sss.pgh.pa.us 501 [ + + ]: 51660 : if (GistPageIsLeaf(page))
502 : : {
503 : : /* Creating heap-tuple GISTSearchItem */
504 : 13923 : item->blkno = InvalidBlockNumber;
505 : 13923 : item->data.heap.heapPtr = it->t_tid;
506 : 13923 : item->data.heap.recheck = recheck;
3957 heikki.linnakangas@i 507 : 13923 : item->data.heap.recheckDistances = recheck_distances;
508 : :
509 : : /*
510 : : * In an index-only scan, also fetch the data from the tuple.
511 : : */
4007 512 [ + + ]: 13923 : if (scan->xs_want_itup)
3303 tgl@sss.pgh.pa.us 513 : 7074 : item->data.heap.recontup = gistFetchTuple(giststate, r, it);
514 : : }
515 : : else
516 : : {
517 : : /* Creating index-page GISTSearchItem */
5581 518 : 37737 : item->blkno = ItemPointerGetBlockNumber(&it->t_tid);
519 : :
520 : : /*
521 : : * LSN of current page is lsn of parent page for child. We
522 : : * only have a shared lock, so we need to get the LSN
523 : : * atomically.
524 : : */
4741 simon@2ndQuadrant.co 525 : 37737 : item->data.parentlsn = BufferGetLSNAtomic(buffer);
526 : : }
527 : :
528 : : /* Insert it into the queue using new distance data */
2369 akorotkov@postgresql 529 : 51660 : memcpy(item->distances, so->distances,
530 : : sizeof(item->distances[0]) * nOrderBys);
531 : :
4101 heikki.linnakangas@i 532 : 51660 : pairingheap_add(so->queue, &item->phNode);
533 : :
5581 tgl@sss.pgh.pa.us 534 : 51660 : MemoryContextSwitchTo(oldcxt);
535 : : }
536 : : }
537 : :
538 : 39161 : UnlockReleaseBuffer(buffer);
539 : : }
540 : :
541 : : /*
542 : : * Extract next item (in order) from search queue
543 : : *
544 : : * Returns a GISTSearchItem or NULL. Caller must pfree item when done with it.
545 : : */
546 : : static GISTSearchItem *
547 : 39591 : getNextGISTSearchItem(GISTScanOpaque so)
548 : : {
549 : : GISTSearchItem *item;
550 : :
4101 heikki.linnakangas@i 551 [ + + ]: 39591 : if (!pairingheap_is_empty(so->queue))
552 : : {
553 : 36778 : item = (GISTSearchItem *) pairingheap_remove_first(so->queue);
554 : : }
555 : : else
556 : : {
557 : : /* Done when both heaps are empty */
558 : 2813 : item = NULL;
559 : : }
560 : :
561 : : /* Return item; caller is responsible to pfree it */
562 : 39591 : return item;
563 : : }
564 : :
565 : : /*
566 : : * Fetch next heap tuple in an ordered search
567 : : */
568 : : static bool
5581 tgl@sss.pgh.pa.us 569 : 644 : getNextNearest(IndexScanDesc scan)
570 : : {
571 : 644 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
572 : 644 : bool res = false;
573 : :
3303 574 [ + + ]: 644 : if (scan->xs_hitup)
575 : : {
576 : : /* free previously returned tuple */
577 : 425 : pfree(scan->xs_hitup);
578 : 425 : scan->xs_hitup = NULL;
579 : : }
580 : :
581 : : do
582 : : {
5581 583 : 805 : GISTSearchItem *item = getNextGISTSearchItem(so);
584 : :
585 [ + + ]: 805 : if (!item)
586 : 21 : break;
587 : :
588 [ + + ]: 784 : if (GISTSearchItemIsHeap(*item))
589 : : {
590 : : /* found a heap item at currently minimal distance */
2561 andres@anarazel.de 591 : 623 : scan->xs_heaptid = item->data.heap.heapPtr;
5581 tgl@sss.pgh.pa.us 592 : 623 : scan->xs_recheck = item->data.heap.recheck;
593 : :
2734 akorotkov@postgresql 594 : 623 : index_store_float8_orderby_distances(scan, so->orderByTypes,
2369 595 : 623 : item->distances,
2734 596 : 623 : item->data.heap.recheckDistances);
597 : :
598 : : /* in an index-only scan, also return the reconstructed tuple. */
4007 heikki.linnakangas@i 599 [ + + ]: 623 : if (scan->xs_want_itup)
3303 tgl@sss.pgh.pa.us 600 : 459 : scan->xs_hitup = item->data.heap.recontup;
5581 601 : 623 : res = true;
602 : : }
603 : : else
604 : : {
605 : : /* visit an index page, extract its items into queue */
606 [ - + ]: 161 : CHECK_FOR_INTERRUPTS();
607 : :
2369 akorotkov@postgresql 608 : 161 : gistScanPage(scan, item, item->distances, NULL, NULL);
609 : : }
610 : :
5581 tgl@sss.pgh.pa.us 611 : 784 : pfree(item);
612 [ + + ]: 784 : } while (!res);
613 : :
614 : 644 : return res;
615 : : }
616 : :
617 : : /*
618 : : * gistgettuple() -- Get the next tuple in the scan
619 : : */
620 : : bool
3710 621 : 376160 : gistgettuple(IndexScanDesc scan, ScanDirection dir)
622 : : {
5581 623 : 376160 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
624 : :
625 [ - + ]: 376160 : if (dir != ForwardScanDirection)
5581 tgl@sss.pgh.pa.us 626 [ # # ]:UBC 0 : elog(ERROR, "GiST only supports forward scan direction");
627 : :
5581 tgl@sss.pgh.pa.us 628 [ - + ]:CBC 376160 : if (!so->qual_ok)
3710 tgl@sss.pgh.pa.us 629 :UBC 0 : return false;
630 : :
5581 tgl@sss.pgh.pa.us 631 [ + + ]:CBC 376160 : if (so->firstCall)
632 : : {
633 : : /* Begin the scan by processing the root page */
634 : : GISTSearchItem fakeItem;
635 : :
636 [ + + + - : 2185 : pgstat_count_index_scan(scan->indexRelation);
+ - ]
369 pg@bowt.ie 637 [ + + ]: 2185 : if (scan->instrument)
638 : 1045 : scan->instrument->nsearches++;
639 : :
5581 tgl@sss.pgh.pa.us 640 : 2185 : so->firstCall = false;
641 : 2185 : so->curPageData = so->nPageData = 0;
3237 642 : 2185 : scan->xs_hitup = NULL;
4007 heikki.linnakangas@i 643 [ + + ]: 2185 : if (so->pageDataCxt)
644 : 340 : MemoryContextReset(so->pageDataCxt);
645 : :
5581 tgl@sss.pgh.pa.us 646 : 2185 : fakeItem.blkno = GIST_ROOT_BLKNO;
647 : 2185 : memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
2369 akorotkov@postgresql 648 : 2185 : gistScanPage(scan, &fakeItem, NULL, NULL, NULL);
649 : : }
650 : :
5581 tgl@sss.pgh.pa.us 651 [ + + ]: 376160 : if (scan->numberOfOrderBys > 0)
652 : : {
653 : : /* Must fetch tuples in strict distance order */
3710 654 : 644 : return getNextNearest(scan);
655 : : }
656 : : else
657 : : {
658 : : /* Fetch tuples index-page-at-a-time */
659 : : for (;;)
660 : : {
5581 661 [ + + ]: 379606 : if (so->curPageData < so->nPageData)
662 : : {
3840 teodor@sigaev.ru 663 [ + + + - ]: 373545 : if (scan->kill_prior_tuple && so->curPageData > 0)
664 : : {
665 : :
666 [ + + ]: 293 : if (so->killedItems == NULL)
667 : : {
668 : : MemoryContext oldCxt =
1031 tgl@sss.pgh.pa.us 669 : 231 : MemoryContextSwitchTo(so->giststate->scanCxt);
670 : :
3840 teodor@sigaev.ru 671 : 231 : so->killedItems =
672 : 231 : (OffsetNumber *) palloc(MaxIndexTuplesPerPage
673 : : * sizeof(OffsetNumber));
674 : :
675 : 231 : MemoryContextSwitchTo(oldCxt);
676 : : }
677 [ + - ]: 293 : if (so->numKilled < MaxIndexTuplesPerPage)
678 : 293 : so->killedItems[so->numKilled++] =
679 : 293 : so->pageData[so->curPageData - 1].offnum;
680 : : }
681 : : /* continuing to return tuples from a leaf page */
2561 andres@anarazel.de 682 : 373545 : scan->xs_heaptid = so->pageData[so->curPageData].heapPtr;
5581 tgl@sss.pgh.pa.us 683 : 373545 : scan->xs_recheck = so->pageData[so->curPageData].recheck;
684 : :
685 : : /* in an index-only scan, also return the reconstructed tuple */
4007 heikki.linnakangas@i 686 [ + + ]: 373545 : if (scan->xs_want_itup)
3303 tgl@sss.pgh.pa.us 687 : 258739 : scan->xs_hitup = so->pageData[so->curPageData].recontup;
688 : :
5581 689 : 373545 : so->curPageData++;
690 : :
3710 691 : 373545 : return true;
692 : : }
693 : :
694 : : /*
695 : : * Check the last returned tuple and add it to killedItems if
696 : : * necessary
697 : : */
3840 teodor@sigaev.ru 698 [ + + ]: 6061 : if (scan->kill_prior_tuple
699 [ + - ]: 5 : && so->curPageData > 0
700 [ + - ]: 5 : && so->curPageData == so->nPageData)
701 : : {
702 : :
703 [ + - ]: 5 : if (so->killedItems == NULL)
704 : : {
705 : : MemoryContext oldCxt =
1031 tgl@sss.pgh.pa.us 706 : 5 : MemoryContextSwitchTo(so->giststate->scanCxt);
707 : :
3840 teodor@sigaev.ru 708 : 5 : so->killedItems =
709 : 5 : (OffsetNumber *) palloc(MaxIndexTuplesPerPage
710 : : * sizeof(OffsetNumber));
711 : :
712 : 5 : MemoryContextSwitchTo(oldCxt);
713 : : }
714 [ + - ]: 5 : if (so->numKilled < MaxIndexTuplesPerPage)
715 : 5 : so->killedItems[so->numKilled++] =
716 : 5 : so->pageData[so->curPageData - 1].offnum;
717 : : }
718 : : /* find and process the next index page */
719 : : do
720 : : {
721 : : GISTSearchItem *item;
722 : :
723 [ + + + + ]: 7734 : if ((so->curBlkno != InvalidBlockNumber) && (so->numKilled > 0))
3840 teodor@sigaev.ru 724 :GBC 1 : gistkillitems(scan);
725 : :
3840 teodor@sigaev.ru 726 :CBC 7734 : item = getNextGISTSearchItem(so);
727 : :
5581 tgl@sss.pgh.pa.us 728 [ + + ]: 7734 : if (!item)
3710 729 : 1971 : return false;
730 : :
5581 731 [ - + ]: 5763 : CHECK_FOR_INTERRUPTS();
732 : :
733 : : /* save current item BlockNumber for next gistkillitems() call */
3840 teodor@sigaev.ru 734 : 5763 : so->curBlkno = item->blkno;
735 : :
736 : : /*
737 : : * While scanning a leaf page, ItemPointers of matching heap
738 : : * tuples are stored in so->pageData. If there are any on
739 : : * this page, we fall out of the inner "do" and loop around to
740 : : * return them.
741 : : */
2369 akorotkov@postgresql 742 : 5763 : gistScanPage(scan, item, item->distances, NULL, NULL);
743 : :
5581 tgl@sss.pgh.pa.us 744 : 5763 : pfree(item);
745 [ + + ]: 5763 : } while (so->nPageData == 0);
746 : : }
747 : : }
748 : : }
749 : :
750 : : /*
751 : : * gistgetbitmap() -- Get a bitmap of all heap tuple locations
752 : : */
753 : : int64
3710 754 : 821 : gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
755 : : {
5581 756 : 821 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
757 : 821 : int64 ntids = 0;
758 : : GISTSearchItem fakeItem;
759 : :
760 [ - + ]: 821 : if (!so->qual_ok)
3710 tgl@sss.pgh.pa.us 761 :UBC 0 : return 0;
762 : :
5581 tgl@sss.pgh.pa.us 763 [ + + + - :CBC 821 : pgstat_count_index_scan(scan->indexRelation);
+ - ]
369 pg@bowt.ie 764 [ + - ]: 821 : if (scan->instrument)
765 : 821 : scan->instrument->nsearches++;
766 : :
767 : : /* Begin the scan by processing the root page */
5581 tgl@sss.pgh.pa.us 768 : 821 : so->curPageData = so->nPageData = 0;
3237 769 : 821 : scan->xs_hitup = NULL;
4007 heikki.linnakangas@i 770 [ - + ]: 821 : if (so->pageDataCxt)
4007 heikki.linnakangas@i 771 :UBC 0 : MemoryContextReset(so->pageDataCxt);
772 : :
5581 tgl@sss.pgh.pa.us 773 :CBC 821 : fakeItem.blkno = GIST_ROOT_BLKNO;
774 : 821 : memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
2369 akorotkov@postgresql 775 : 821 : gistScanPage(scan, &fakeItem, NULL, tbm, &ntids);
776 : :
777 : : /*
778 : : * While scanning a leaf page, ItemPointers of matching heap tuples will
779 : : * be stored directly into tbm, so we don't need to deal with them here.
780 : : */
781 : : for (;;)
10416 bruce@momjian.us 782 : 30231 : {
5581 tgl@sss.pgh.pa.us 783 : 31052 : GISTSearchItem *item = getNextGISTSearchItem(so);
784 : :
785 [ + + ]: 31052 : if (!item)
10416 bruce@momjian.us 786 : 821 : break;
787 : :
5581 tgl@sss.pgh.pa.us 788 [ - + ]: 30231 : CHECK_FOR_INTERRUPTS();
789 : :
2369 akorotkov@postgresql 790 : 30231 : gistScanPage(scan, item, item->distances, tbm, &ntids);
791 : :
5581 tgl@sss.pgh.pa.us 792 : 30231 : pfree(item);
793 : : }
794 : :
3710 795 : 821 : return ntids;
796 : : }
797 : :
798 : : /*
799 : : * Can we do index-only scans on the given index column?
800 : : *
801 : : * Opclasses that implement a fetch function support index-only scans.
802 : : * Opclasses without compression functions also support index-only scans.
803 : : * Included attributes always can be fetched for index-only scans.
804 : : */
805 : : bool
806 : 3901 : gistcanreturn(Relation index, int attno)
807 : : {
2562 akorotkov@postgresql 808 [ + + + + ]: 7739 : if (attno > IndexRelationGetNumberOfKeyAttributes(index) ||
809 [ + + ]: 7125 : OidIsValid(index_getprocid(index, attno, GIST_FETCH_PROC)) ||
3099 tgl@sss.pgh.pa.us 810 : 3287 : !OidIsValid(index_getprocid(index, attno, GIST_COMPRESS_PROC)))
3710 811 : 2604 : return true;
812 : : else
813 : 1297 : return false;
814 : : }
|
