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