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-2024, 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
3140 teodor@sigaev.ru 38 :UBC 0 : gistkillitems(IndexScanDesc scan)
39 : : {
2866 rhaas@postgresql.org 40 : 0 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
41 : : Buffer buffer;
42 : : Page page;
43 : : OffsetNumber offnum;
44 : : ItemId iid;
45 : : int i;
46 : 0 : bool killedsomething = false;
47 : :
3140 teodor@sigaev.ru 48 [ # # ]: 0 : Assert(so->curBlkno != InvalidBlockNumber);
49 [ # # ]: 0 : Assert(!XLogRecPtrIsInvalid(so->curPageLSN));
50 [ # # ]: 0 : Assert(so->killedItems != NULL);
51 : :
52 : 0 : buffer = ReadBuffer(scan->indexRelation, so->curBlkno);
53 [ # # ]: 0 : if (!BufferIsValid(buffer))
54 : 0 : return;
55 : :
56 : 0 : LockBuffer(buffer, GIST_SHARE);
57 : 0 : gistcheckpage(scan->indexRelation, buffer);
2916 kgrittn@postgresql.o 58 : 0 : 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 : : */
2287 alvherre@alvh.no-ip. 65 [ # # ]: 0 : if (BufferGetLSNAtomic(buffer) != so->curPageLSN)
66 : : {
3140 teodor@sigaev.ru 67 : 0 : UnlockReleaseBuffer(buffer);
2866 rhaas@postgresql.org 68 : 0 : so->numKilled = 0; /* reset counter */
3140 teodor@sigaev.ru 69 : 0 : return;
70 : : }
71 : :
72 [ # # ]: 0 : 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 [ # # ]: 0 : for (i = 0; i < so->numKilled; i++)
79 : : {
80 : 0 : offnum = so->killedItems[i];
81 : 0 : iid = PageGetItemId(page, offnum);
82 : 0 : ItemIdMarkDead(iid);
83 : 0 : killedsomething = true;
84 : : }
85 : :
86 [ # # ]: 0 : if (killedsomething)
87 : : {
88 : 0 : GistMarkPageHasGarbage(page);
89 : 0 : MarkBufferDirtyHint(buffer, true);
90 : : }
91 : :
92 : 0 : UnlockReleaseBuffer(buffer);
93 : :
94 : : /*
95 : : * Always reset the scan state, so we don't look for same items on other
96 : : * pages.
97 : : */
98 : 0 : 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
4881 tgl@sss.pgh.pa.us 125 :CBC 1062477 : gistindex_keytest(IndexScanDesc scan,
126 : : IndexTuple tuple,
127 : : Page page,
128 : : OffsetNumber offset,
129 : : bool *recheck_p,
130 : : bool *recheck_distances_p)
131 : : {
132 : 1062477 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
133 : 1062477 : GISTSTATE *giststate = so->giststate;
134 : 1062477 : ScanKey key = scan->keyData;
135 : 1062477 : int keySize = scan->numberOfKeys;
136 : : IndexOrderByDistance *distance_p;
137 : 1062477 : Relation r = scan->indexRelation;
138 : :
139 : 1062477 : *recheck_p = false;
3257 heikki.linnakangas@i 140 : 1062477 : *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 : : */
4881 tgl@sss.pgh.pa.us 147 [ - + ]: 1062477 : if (GistTupleIsInvalid(tuple))
148 : : {
149 : : int i;
150 : :
2489 tgl@sss.pgh.pa.us 151 [ # # ]:UBC 0 : if (GistPageIsLeaf(page)) /* shouldn't happen */
4714 peter_e@gmx.net 152 [ # # ]: 0 : elog(ERROR, "invalid GiST tuple found on leaf page");
4881 tgl@sss.pgh.pa.us 153 [ # # ]: 0 : for (i = 0; i < scan->numberOfOrderBys; i++)
154 : : {
1669 akorotkov@postgresql 155 : 0 : so->distances[i].value = -get_float8_infinity();
156 : 0 : so->distances[i].isnull = false;
157 : : }
4881 tgl@sss.pgh.pa.us 158 : 0 : return true;
159 : : }
160 : :
161 : : /* Check whether it matches according to the Consistent functions */
4881 tgl@sss.pgh.pa.us 162 [ + + ]:CBC 1641178 : while (keySize > 0)
163 : : {
164 : : Datum datum;
165 : : bool isNull;
166 : :
167 : 1019533 : datum = index_getattr(tuple,
168 : 1019533 : key->sk_attno,
169 : : giststate->leafTupdesc,
170 : : &isNull);
171 : :
172 [ + + ]: 1019533 : 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 : 440832 : 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 [ + + ]: 996435 : else if (isNull)
193 : : {
194 : 983 : return false;
195 : : }
196 : : else
197 : : {
198 : : Datum test;
199 : : bool recheck;
200 : : GISTENTRY de;
201 : :
202 : 995452 : 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 : 995452 : recheck = true;
220 : :
4751 221 : 1990904 : test = FunctionCall5Coll(&key->sk_func,
222 : : key->sk_collation,
223 : : PointerGetDatum(&de),
224 : : key->sk_argument,
3008 225 : 995452 : Int16GetDatum(key->sk_strategy),
226 : : ObjectIdGetDatum(key->sk_subtype),
227 : : PointerGetDatum(&recheck));
228 : :
4881 229 [ + + ]: 995452 : if (!DatumGetBool(test))
230 : 418639 : return false;
231 : 576813 : *recheck_p |= recheck;
232 : : }
233 : :
234 : 578701 : key++;
235 : 578701 : keySize--;
236 : : }
237 : :
238 : : /* OK, it passes --- now let's compute the distances */
239 : 621645 : key = scan->orderByData;
1669 akorotkov@postgresql 240 : 621645 : distance_p = so->distances;
4881 tgl@sss.pgh.pa.us 241 : 621645 : keySize = scan->numberOfOrderBys;
242 [ + + ]: 636816 : while (keySize > 0)
243 : : {
244 : : Datum datum;
245 : : bool isNull;
246 : :
247 : 15171 : datum = index_getattr(tuple,
248 : 15171 : key->sk_attno,
249 : : giststate->leafTupdesc,
250 : : &isNull);
251 : :
252 [ + - + + ]: 15171 : if ((key->sk_flags & SK_ISNULL) || isNull)
253 : : {
254 : : /* Assume distance computes as null */
1669 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 : :
4881 tgl@sss.pgh.pa.us 264 : 15117 : 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 : : */
3257 heikki.linnakangas@i 284 : 15117 : recheck = false;
285 : 30234 : dist = FunctionCall5Coll(&key->sk_func,
286 : : key->sk_collation,
287 : : PointerGetDatum(&de),
288 : : key->sk_argument,
3008 tgl@sss.pgh.pa.us 289 : 15117 : Int16GetDatum(key->sk_strategy),
290 : : ObjectIdGetDatum(key->sk_subtype),
291 : : PointerGetDatum(&recheck));
3257 heikki.linnakangas@i 292 : 15117 : *recheck_distances_p |= recheck;
1669 akorotkov@postgresql 293 : 15117 : distance_p->value = DatumGetFloat8(dist);
294 : 15117 : distance_p->isnull = false;
295 : : }
296 : :
4881 tgl@sss.pgh.pa.us 297 : 15171 : key++;
1669 akorotkov@postgresql 298 : 15171 : distance_p++;
4881 tgl@sss.pgh.pa.us 299 : 15171 : keySize--;
300 : : }
301 : :
302 : 621645 : 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
1680 akorotkov@postgresql 328 : 38437 : gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem,
329 : : IndexOrderByDistance *myDistances, TIDBitmap *tbm, int64 *ntids)
330 : : {
4881 tgl@sss.pgh.pa.us 331 : 38437 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
3307 heikki.linnakangas@i 332 : 38437 : GISTSTATE *giststate = so->giststate;
333 : 38437 : Relation r = scan->indexRelation;
334 : : Buffer buffer;
335 : : Page page;
336 : : GISTPageOpaque opaque;
337 : : OffsetNumber maxoff;
338 : : OffsetNumber i;
339 : : MemoryContext oldcxt;
340 : :
4881 tgl@sss.pgh.pa.us 341 [ - + ]: 38437 : Assert(!GISTSearchItemIsHeap(*pageItem));
342 : :
343 : 38437 : buffer = ReadBuffer(scan->indexRelation, pageItem->blkno);
344 : 38437 : LockBuffer(buffer, GIST_SHARE);
2210 teodor@sigaev.ru 345 : 38437 : PredicateLockPage(r, BufferGetBlockNumber(buffer), scan->xs_snapshot);
4881 tgl@sss.pgh.pa.us 346 : 38437 : gistcheckpage(scan->indexRelation, buffer);
2916 kgrittn@postgresql.o 347 : 38437 : page = BufferGetPage(buffer);
4881 tgl@sss.pgh.pa.us 348 : 38437 : 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 [ + + ]: 38437 : if (!XLogRecPtrIsInvalid(pageItem->data.parentlsn) &&
4861 heikki.linnakangas@i 357 [ + - - + ]: 72188 : (GistFollowRight(page) ||
4105 heikki.linnakangas@i 358 :UBC 0 : pageItem->data.parentlsn < GistPageGetNSN(page)) &&
4881 tgl@sss.pgh.pa.us 359 [ # # ]: 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 */
1669 akorotkov@postgresql 365 [ # # ]: 0 : Assert(myDistances != NULL);
366 : :
4881 tgl@sss.pgh.pa.us 367 : 0 : oldcxt = MemoryContextSwitchTo(so->queueCxt);
368 : :
369 : : /* Create new GISTSearchItem for the right sibling index page */
3401 heikki.linnakangas@i 370 : 0 : item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
4881 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 */
1669 akorotkov@postgresql 375 : 0 : memcpy(item->distances, myDistances,
376 : 0 : sizeof(item->distances[0]) * scan->numberOfOrderBys);
377 : :
3401 heikki.linnakangas@i 378 : 0 : pairingheap_add(so->queue, &item->phNode);
379 : :
4881 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 : : */
1726 heikki.linnakangas@i 391 [ - + ]:CBC 38437 : if (GistPageIsDeleted(page))
392 : : {
1726 heikki.linnakangas@i 393 :UBC 0 : UnlockReleaseBuffer(buffer);
394 : 0 : return;
395 : : }
396 : :
4881 tgl@sss.pgh.pa.us 397 :CBC 38437 : so->nPageData = so->curPageData = 0;
2537 398 : 38437 : scan->xs_hitup = NULL; /* might point into pageDataCxt */
3307 heikki.linnakangas@i 399 [ + + ]: 38437 : if (so->pageDataCxt)
400 : 3197 : 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 : : */
2287 alvherre@alvh.no-ip. 407 : 38437 : so->curPageLSN = BufferGetLSNAtomic(buffer);
408 : :
409 : : /*
410 : : * check all tuples on page
411 : : */
4881 tgl@sss.pgh.pa.us 412 : 38437 : maxoff = PageGetMaxOffsetNumber(page);
413 [ + + ]: 1100914 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
414 : : {
2866 rhaas@postgresql.org 415 : 1062477 : 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 [ + - - + ]: 1062477 : if (scan->ignore_killed_tuples && ItemIdIsDead(iid))
3140 teodor@sigaev.ru 426 :UBC 0 : continue;
427 : :
3140 teodor@sigaev.ru 428 :CBC 1062477 : it = (IndexTuple) PageGetItem(page, iid);
429 : :
430 : : /*
431 : : * Must call gistindex_keytest in tempCxt, and clean up any leftover
432 : : * junk afterward.
433 : : */
4580 tgl@sss.pgh.pa.us 434 : 1062477 : oldcxt = MemoryContextSwitchTo(so->giststate->tempCxt);
435 : :
3257 heikki.linnakangas@i 436 : 1062477 : match = gistindex_keytest(scan, it, page, i,
437 : : &recheck, &recheck_distances);
438 : :
4881 tgl@sss.pgh.pa.us 439 : 1062477 : MemoryContextSwitchTo(oldcxt);
4580 440 : 1062477 : MemoryContextReset(so->giststate->tempCxt);
441 : :
442 : : /* Ignore tuple if it doesn't match */
4881 443 [ + + ]: 1062477 : if (!match)
444 : 440832 : continue;
445 : :
446 [ + + + + ]: 621645 : 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 : 197778 : tbm_add_tuples(tbm, &it->t_tid, 1, recheck);
453 : 197778 : (*ntids)++;
454 : : }
455 [ + + + + ]: 423867 : else if (scan->numberOfOrderBys == 0 && GistPageIsLeaf(page))
456 : : {
457 : : /*
458 : : * Non-ordered scan, so report tuples in so->pageData[]
459 : : */
460 : 372766 : so->pageData[so->nPageData].heapPtr = it->t_tid;
461 : 372766 : so->pageData[so->nPageData].recheck = recheck;
3140 teodor@sigaev.ru 462 : 372766 : 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 : : */
3307 heikki.linnakangas@i 468 [ + + ]: 372766 : if (scan->xs_want_itup)
469 : : {
470 : 258739 : oldcxt = MemoryContextSwitchTo(so->pageDataCxt);
2603 tgl@sss.pgh.pa.us 471 : 517478 : so->pageData[so->nPageData].recontup =
3307 heikki.linnakangas@i 472 : 258739 : gistFetchTuple(giststate, r, it);
473 : 258739 : MemoryContextSwitchTo(oldcxt);
474 : : }
4881 tgl@sss.pgh.pa.us 475 : 372766 : 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;
1680 akorotkov@postgresql 485 : 51101 : int nOrderBys = scan->numberOfOrderBys;
486 : :
4881 tgl@sss.pgh.pa.us 487 : 51101 : oldcxt = MemoryContextSwitchTo(so->queueCxt);
488 : :
489 : : /* Create new GISTSearchItem for this item */
3401 heikki.linnakangas@i 490 : 51101 : item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
491 : :
4881 tgl@sss.pgh.pa.us 492 [ + + ]: 51101 : if (GistPageIsLeaf(page))
493 : : {
494 : : /* Creating heap-tuple GISTSearchItem */
495 : 13430 : item->blkno = InvalidBlockNumber;
496 : 13430 : item->data.heap.heapPtr = it->t_tid;
497 : 13430 : item->data.heap.recheck = recheck;
3257 heikki.linnakangas@i 498 : 13430 : item->data.heap.recheckDistances = recheck_distances;
499 : :
500 : : /*
501 : : * In an index-only scan, also fetch the data from the tuple.
502 : : */
3307 503 [ + + ]: 13430 : if (scan->xs_want_itup)
2603 tgl@sss.pgh.pa.us 504 : 6569 : item->data.heap.recontup = gistFetchTuple(giststate, r, it);
505 : : }
506 : : else
507 : : {
508 : : /* Creating index-page GISTSearchItem */
4881 509 : 37671 : 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 : : */
4041 simon@2ndQuadrant.co 516 : 37671 : item->data.parentlsn = BufferGetLSNAtomic(buffer);
517 : : }
518 : :
519 : : /* Insert it into the queue using new distance data */
1669 akorotkov@postgresql 520 : 51101 : memcpy(item->distances, so->distances,
521 : : sizeof(item->distances[0]) * nOrderBys);
522 : :
3401 heikki.linnakangas@i 523 : 51101 : pairingheap_add(so->queue, &item->phNode);
524 : :
4881 tgl@sss.pgh.pa.us 525 : 51101 : MemoryContextSwitchTo(oldcxt);
526 : : }
527 : : }
528 : :
529 : 38437 : 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 : 38940 : getNextGISTSearchItem(GISTScanOpaque so)
539 : : {
540 : : GISTSearchItem *item;
541 : :
3401 heikki.linnakangas@i 542 [ + + ]: 38940 : if (!pairingheap_is_empty(so->queue))
543 : : {
544 : 36717 : item = (GISTSearchItem *) pairingheap_remove_first(so->queue);
545 : : }
546 : : else
547 : : {
548 : : /* Done when both heaps are empty */
549 : 2223 : item = NULL;
550 : : }
551 : :
552 : : /* Return item; caller is responsible to pfree it */
553 : 38940 : return item;
554 : : }
555 : :
556 : : /*
557 : : * Fetch next heap tuple in an ordered search
558 : : */
559 : : static bool
4881 tgl@sss.pgh.pa.us 560 : 644 : getNextNearest(IndexScanDesc scan)
561 : : {
562 : 644 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
563 : 644 : bool res = false;
564 : :
2603 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 : : {
4881 574 : 808 : GISTSearchItem *item = getNextGISTSearchItem(so);
575 : :
576 [ + + ]: 808 : if (!item)
577 : 21 : break;
578 : :
579 [ + + ]: 787 : if (GISTSearchItemIsHeap(*item))
580 : : {
581 : : /* found a heap item at currently minimal distance */
1861 andres@anarazel.de 582 : 623 : scan->xs_heaptid = item->data.heap.heapPtr;
4881 tgl@sss.pgh.pa.us 583 : 623 : scan->xs_recheck = item->data.heap.recheck;
584 : :
2034 akorotkov@postgresql 585 : 623 : index_store_float8_orderby_distances(scan, so->orderByTypes,
1669 586 : 623 : item->distances,
2034 587 : 623 : item->data.heap.recheckDistances);
588 : :
589 : : /* in an index-only scan, also return the reconstructed tuple. */
3307 heikki.linnakangas@i 590 [ + + ]: 623 : if (scan->xs_want_itup)
2603 tgl@sss.pgh.pa.us 591 : 459 : scan->xs_hitup = item->data.heap.recontup;
4881 592 : 623 : res = true;
593 : : }
594 : : else
595 : : {
596 : : /* visit an index page, extract its items into queue */
597 [ - + ]: 164 : CHECK_FOR_INTERRUPTS();
598 : :
1669 akorotkov@postgresql 599 : 164 : gistScanPage(scan, item, item->distances, NULL, NULL);
600 : : }
601 : :
4881 tgl@sss.pgh.pa.us 602 : 787 : pfree(item);
603 [ + + ]: 787 : } while (!res);
604 : :
605 : 644 : return res;
606 : : }
607 : :
608 : : /*
609 : : * gistgettuple() -- Get the next tuple in the scan
610 : : */
611 : : bool
3010 612 : 374769 : gistgettuple(IndexScanDesc scan, ScanDirection dir)
613 : : {
4881 614 : 374769 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
615 : :
616 [ - + ]: 374769 : if (dir != ForwardScanDirection)
4881 tgl@sss.pgh.pa.us 617 [ # # ]:UBC 0 : elog(ERROR, "GiST only supports forward scan direction");
618 : :
4881 tgl@sss.pgh.pa.us 619 [ - + ]:CBC 374769 : if (!so->qual_ok)
3010 tgl@sss.pgh.pa.us 620 :UBC 0 : return false;
621 : :
4881 tgl@sss.pgh.pa.us 622 [ + + ]:CBC 374769 : if (so->firstCall)
623 : : {
624 : : /* Begin the scan by processing the root page */
625 : : GISTSearchItem fakeItem;
626 : :
627 [ + + + + : 1548 : pgstat_count_index_scan(scan->indexRelation);
+ + ]
628 : :
629 : 1548 : so->firstCall = false;
630 : 1548 : so->curPageData = so->nPageData = 0;
2537 631 : 1548 : scan->xs_hitup = NULL;
3307 heikki.linnakangas@i 632 [ + + ]: 1548 : if (so->pageDataCxt)
633 : 340 : MemoryContextReset(so->pageDataCxt);
634 : :
4881 tgl@sss.pgh.pa.us 635 : 1548 : fakeItem.blkno = GIST_ROOT_BLKNO;
636 : 1548 : memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
1669 akorotkov@postgresql 637 : 1548 : gistScanPage(scan, &fakeItem, NULL, NULL, NULL);
638 : : }
639 : :
4881 tgl@sss.pgh.pa.us 640 [ + + ]: 374769 : if (scan->numberOfOrderBys > 0)
641 : : {
642 : : /* Must fetch tuples in strict distance order */
3010 643 : 644 : return getNextNearest(scan);
644 : : }
645 : : else
646 : : {
647 : : /* Fetch tuples index-page-at-a-time */
648 : : for (;;)
649 : : {
4881 650 [ + + ]: 378412 : if (so->curPageData < so->nPageData)
651 : : {
3140 teodor@sigaev.ru 652 [ + + + - ]: 372718 : if (scan->kill_prior_tuple && so->curPageData > 0)
653 : : {
654 : :
655 [ + + ]: 247 : if (so->killedItems == NULL)
656 : : {
657 : : MemoryContext oldCxt =
331 tgl@sss.pgh.pa.us 658 : 222 : MemoryContextSwitchTo(so->giststate->scanCxt);
659 : :
3140 teodor@sigaev.ru 660 : 222 : so->killedItems =
661 : 222 : (OffsetNumber *) palloc(MaxIndexTuplesPerPage
662 : : * sizeof(OffsetNumber));
663 : :
664 : 222 : MemoryContextSwitchTo(oldCxt);
665 : : }
666 [ + - ]: 247 : if (so->numKilled < MaxIndexTuplesPerPage)
667 : 247 : so->killedItems[so->numKilled++] =
668 : 247 : so->pageData[so->curPageData - 1].offnum;
669 : : }
670 : : /* continuing to return tuples from a leaf page */
1861 andres@anarazel.de 671 : 372718 : scan->xs_heaptid = so->pageData[so->curPageData].heapPtr;
4881 tgl@sss.pgh.pa.us 672 : 372718 : scan->xs_recheck = so->pageData[so->curPageData].recheck;
673 : :
674 : : /* in an index-only scan, also return the reconstructed tuple */
3307 heikki.linnakangas@i 675 [ + + ]: 372718 : if (scan->xs_want_itup)
2603 tgl@sss.pgh.pa.us 676 : 258739 : scan->xs_hitup = so->pageData[so->curPageData].recontup;
677 : :
4881 678 : 372718 : so->curPageData++;
679 : :
3010 680 : 372718 : return true;
681 : : }
682 : :
683 : : /*
684 : : * Check the last returned tuple and add it to killedItems if
685 : : * necessary
686 : : */
3140 teodor@sigaev.ru 687 [ + + ]: 5694 : if (scan->kill_prior_tuple
3140 teodor@sigaev.ru 688 [ + - ]:GBC 17 : && so->curPageData > 0
689 [ + - ]: 17 : && so->curPageData == so->nPageData)
690 : : {
691 : :
692 [ + - ]: 17 : if (so->killedItems == NULL)
693 : : {
694 : : MemoryContext oldCxt =
331 tgl@sss.pgh.pa.us 695 : 17 : MemoryContextSwitchTo(so->giststate->scanCxt);
696 : :
3140 teodor@sigaev.ru 697 : 17 : so->killedItems =
698 : 17 : (OffsetNumber *) palloc(MaxIndexTuplesPerPage
699 : : * sizeof(OffsetNumber));
700 : :
701 : 17 : MemoryContextSwitchTo(oldCxt);
702 : : }
703 [ + - ]: 17 : if (so->numKilled < MaxIndexTuplesPerPage)
704 : 17 : so->killedItems[so->numKilled++] =
705 : 17 : so->pageData[so->curPageData - 1].offnum;
706 : : }
707 : : /* find and process the next index page */
708 : : do
709 : : {
710 : : GISTSearchItem *item;
711 : :
3140 teodor@sigaev.ru 712 [ + + - + ]:CBC 7329 : if ((so->curBlkno != InvalidBlockNumber) && (so->numKilled > 0))
3140 teodor@sigaev.ru 713 :UBC 0 : gistkillitems(scan);
714 : :
3140 teodor@sigaev.ru 715 :CBC 7329 : item = getNextGISTSearchItem(so);
716 : :
4881 tgl@sss.pgh.pa.us 717 [ + + ]: 7329 : if (!item)
3010 718 : 1407 : return false;
719 : :
4881 720 [ - + ]: 5922 : CHECK_FOR_INTERRUPTS();
721 : :
722 : : /* save current item BlockNumber for next gistkillitems() call */
3140 teodor@sigaev.ru 723 : 5922 : so->curBlkno = item->blkno;
724 : :
725 : : /*
726 : : * While scanning a leaf page, ItemPointers of matching heap
727 : : * tuples are stored in so->pageData. If there are any on
728 : : * this page, we fall out of the inner "do" and loop around to
729 : : * return them.
730 : : */
1669 akorotkov@postgresql 731 : 5922 : gistScanPage(scan, item, item->distances, NULL, NULL);
732 : :
4881 tgl@sss.pgh.pa.us 733 : 5922 : pfree(item);
734 [ + + ]: 5922 : } while (so->nPageData == 0);
735 : : }
736 : : }
737 : : }
738 : :
739 : : /*
740 : : * gistgetbitmap() -- Get a bitmap of all heap tuple locations
741 : : */
742 : : int64
3010 743 : 795 : gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
744 : : {
4881 745 : 795 : GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
746 : 795 : int64 ntids = 0;
747 : : GISTSearchItem fakeItem;
748 : :
749 [ - + ]: 795 : if (!so->qual_ok)
3010 tgl@sss.pgh.pa.us 750 :UBC 0 : return 0;
751 : :
4881 tgl@sss.pgh.pa.us 752 [ + + + - :CBC 795 : pgstat_count_index_scan(scan->indexRelation);
+ - ]
753 : :
754 : : /* Begin the scan by processing the root page */
755 : 795 : so->curPageData = so->nPageData = 0;
2537 756 : 795 : scan->xs_hitup = NULL;
3307 heikki.linnakangas@i 757 [ - + ]: 795 : if (so->pageDataCxt)
3307 heikki.linnakangas@i 758 :UBC 0 : MemoryContextReset(so->pageDataCxt);
759 : :
4881 tgl@sss.pgh.pa.us 760 :CBC 795 : fakeItem.blkno = GIST_ROOT_BLKNO;
761 : 795 : memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
1669 akorotkov@postgresql 762 : 795 : gistScanPage(scan, &fakeItem, NULL, tbm, &ntids);
763 : :
764 : : /*
765 : : * While scanning a leaf page, ItemPointers of matching heap tuples will
766 : : * be stored directly into tbm, so we don't need to deal with them here.
767 : : */
768 : : for (;;)
9716 bruce@momjian.us 769 : 30008 : {
4881 tgl@sss.pgh.pa.us 770 : 30803 : GISTSearchItem *item = getNextGISTSearchItem(so);
771 : :
772 [ + + ]: 30803 : if (!item)
9716 bruce@momjian.us 773 : 795 : break;
774 : :
4881 tgl@sss.pgh.pa.us 775 [ - + ]: 30008 : CHECK_FOR_INTERRUPTS();
776 : :
1669 akorotkov@postgresql 777 : 30008 : gistScanPage(scan, item, item->distances, tbm, &ntids);
778 : :
4881 tgl@sss.pgh.pa.us 779 : 30008 : pfree(item);
780 : : }
781 : :
3010 782 : 795 : return ntids;
783 : : }
784 : :
785 : : /*
786 : : * Can we do index-only scans on the given index column?
787 : : *
788 : : * Opclasses that implement a fetch function support index-only scans.
789 : : * Opclasses without compression functions also support index-only scans.
790 : : * Included attributes always can be fetched for index-only scans.
791 : : */
792 : : bool
793 : 3289 : gistcanreturn(Relation index, int attno)
794 : : {
1862 akorotkov@postgresql 795 [ + + + + ]: 6515 : if (attno > IndexRelationGetNumberOfKeyAttributes(index) ||
796 [ + + ]: 5911 : OidIsValid(index_getprocid(index, attno, GIST_FETCH_PROC)) ||
2399 tgl@sss.pgh.pa.us 797 : 2685 : !OidIsValid(index_getprocid(index, attno, GIST_COMPRESS_PROC)))
3010 798 : 2248 : return true;
799 : : else
800 : 1041 : return false;
801 : : }
|
