| 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 |
| 38 |
gistkillitems(IndexScanDesc scan) |
| 39 |
{ |
| 40 |
GISTScanOpaque so = (GISTScanOpaque) scan->opaque; |
| 41 |
Buffer buffer; |
| 42 |
Page page; |
| 43 |
OffsetNumber offnum; |
| 44 |
ItemId iid; |
| 45 |
int i; |
| 46 |
bool killedsomething = false; |
| 47 |
|
| 48 |
Assert(so->curBlkno != InvalidBlockNumber); |
| 49 |
Assert(!XLogRecPtrIsInvalid(so->curPageLSN)); |
| 50 |
Assert(so->killedItems != NULL); |
| 51 |
|
| 52 |
buffer = ReadBuffer(scan->indexRelation, so->curBlkno); |
| 53 |
if (!BufferIsValid(buffer)) |
| 54 |
return; |
| 55 |
|
| 56 |
LockBuffer(buffer, GIST_SHARE); |
| 57 |
gistcheckpage(scan->indexRelation, buffer); |
| 58 |
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 |
*/ |
| 65 |
if (BufferGetLSNAtomic(buffer) != so->curPageLSN) |
| 66 |
{ |
| 67 |
UnlockReleaseBuffer(buffer); |
| 68 |
so->numKilled = 0; /* reset counter */ |
| 69 |
return; |
| 70 |
} |
| 71 |
|
| 72 |
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 |
for (i = 0; i < so->numKilled; i++) |
| 79 |
{ |
| 80 |
offnum = so->killedItems[i]; |
| 81 |
iid = PageGetItemId(page, offnum); |
| 82 |
ItemIdMarkDead(iid); |
| 83 |
killedsomething = true; |
| 84 |
} |
| 85 |
|
| 86 |
if (killedsomething) |
| 87 |
{ |
| 88 |
GistMarkPageHasGarbage(page); |
| 89 |
MarkBufferDirtyHint(buffer, true); |
| 90 |
} |
| 91 |
|
| 92 |
UnlockReleaseBuffer(buffer); |
| 93 |
|
| 94 |
/* |
| 95 |
* Always reset the scan state, so we don't look for same items on other |
| 96 |
* pages. |
| 97 |
*/ |
| 98 |
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 |
| 125 |
gistindex_keytest(IndexScanDesc scan, |
| 126 |
IndexTuple tuple, |
| 127 |
Page page, |
| 128 |
OffsetNumber offset, |
| 129 |
bool *recheck_p, |
| 130 |
bool *recheck_distances_p) |
| 131 |
{ |
| 132 |
GISTScanOpaque so = (GISTScanOpaque) scan->opaque; |
| 133 |
GISTSTATE *giststate = so->giststate; |
| 134 |
ScanKey key = scan->keyData; |
| 135 |
int keySize = scan->numberOfKeys; |
| 136 |
IndexOrderByDistance *distance_p; |
| 137 |
Relation r = scan->indexRelation; |
| 138 |
|
| 139 |
*recheck_p = false; |
| 140 |
*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 |
*/ |
| 147 |
if (GistTupleIsInvalid(tuple)) |
| 148 |
{ |
| 149 |
int i; |
| 150 |
|
| 151 |
if (GistPageIsLeaf(page)) /* shouldn't happen */ |
| 152 |
elog(ERROR, "invalid GiST tuple found on leaf page"); |
| 153 |
for (i = 0; i < scan->numberOfOrderBys; i++) |
| 154 |
{ |
| 155 |
so->distances[i].value = -get_float8_infinity(); |
| 156 |
so->distances[i].isnull = false; |
| 157 |
} |
| 158 |
return true; |
| 159 |
} |
| 160 |
|
| 161 |
/* Check whether it matches according to the Consistent functions */ |
| 162 |
while (keySize > 0) |
| 163 |
{ |
| 164 |
Datum datum; |
| 165 |
bool isNull; |
| 166 |
|
| 167 |
datum = index_getattr(tuple, |
| 168 |
key->sk_attno, |
| 169 |
giststate->leafTupdesc, |
| 170 |
&isNull); |
| 171 |
|
| 172 |
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 |
if (key->sk_flags & SK_SEARCHNULL) |
| 181 |
{ |
| 182 |
if (GistPageIsLeaf(page) && !isNull) |
| 183 |
return false; |
| 184 |
} |
| 185 |
else |
| 186 |
{ |
| 187 |
Assert(key->sk_flags & SK_SEARCHNOTNULL); |
| 188 |
if (isNull) |
| 189 |
return false; |
| 190 |
} |
| 191 |
} |
| 192 |
else if (isNull) |
| 193 |
{ |
| 194 |
return false; |
| 195 |
} |
| 196 |
else |
| 197 |
{ |
| 198 |
Datum test; |
| 199 |
bool recheck; |
| 200 |
GISTENTRY de; |
| 201 |
|
| 202 |
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 |
recheck = true; |
| 220 |
|
| 221 |
test = FunctionCall5Coll(&key->sk_func, |
| 222 |
key->sk_collation, |
| 223 |
PointerGetDatum(&de), |
| 224 |
key->sk_argument, |
| 225 |
Int16GetDatum(key->sk_strategy), |
| 226 |
ObjectIdGetDatum(key->sk_subtype), |
| 227 |
PointerGetDatum(&recheck)); |
| 228 |
|
| 229 |
if (!DatumGetBool(test)) |
| 230 |
return false; |
| 231 |
*recheck_p |= recheck; |
| 232 |
} |
| 233 |
|
| 234 |
key++; |
| 235 |
keySize--; |
| 236 |
} |
| 237 |
|
| 238 |
/* OK, it passes --- now let's compute the distances */ |
| 239 |
key = scan->orderByData; |
| 240 |
distance_p = so->distances; |
| 241 |
keySize = scan->numberOfOrderBys; |
| 242 |
while (keySize > 0) |
| 243 |
{ |
| 244 |
Datum datum; |
| 245 |
bool isNull; |
| 246 |
|
| 247 |
datum = index_getattr(tuple, |
| 248 |
key->sk_attno, |
| 249 |
giststate->leafTupdesc, |
| 250 |
&isNull); |
| 251 |
|
| 252 |
if ((key->sk_flags & SK_ISNULL) || isNull) |
| 253 |
{ |
| 254 |
/* Assume distance computes as null */ |
| 255 |
distance_p->value = 0.0; |
| 256 |
distance_p->isnull = true; |
| 257 |
} |
| 258 |
else |
| 259 |
{ |
| 260 |
Datum dist; |
| 261 |
bool recheck; |
| 262 |
GISTENTRY de; |
| 263 |
|
| 264 |
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 |
*/ |
| 284 |
recheck = false; |
| 285 |
dist = FunctionCall5Coll(&key->sk_func, |
| 286 |
key->sk_collation, |
| 287 |
PointerGetDatum(&de), |
| 288 |
key->sk_argument, |
| 289 |
Int16GetDatum(key->sk_strategy), |
| 290 |
ObjectIdGetDatum(key->sk_subtype), |
| 291 |
PointerGetDatum(&recheck)); |
| 292 |
*recheck_distances_p |= recheck; |
| 293 |
distance_p->value = DatumGetFloat8(dist); |
| 294 |
distance_p->isnull = false; |
| 295 |
} |
| 296 |
|
| 297 |
key++; |
| 298 |
distance_p++; |
| 299 |
keySize--; |
| 300 |
} |
| 301 |
|
| 302 |
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 |
| 328 |
gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, |
| 329 |
IndexOrderByDistance *myDistances, TIDBitmap *tbm, int64 *ntids) |
| 330 |
{ |
| 331 |
GISTScanOpaque so = (GISTScanOpaque) scan->opaque; |
| 332 |
GISTSTATE *giststate = so->giststate; |
| 333 |
Relation r = scan->indexRelation; |
| 334 |
Buffer buffer; |
| 335 |
Page page; |
| 336 |
GISTPageOpaque opaque; |
| 337 |
OffsetNumber maxoff; |
| 338 |
OffsetNumber i; |
| 339 |
MemoryContext oldcxt; |
| 340 |
|
| 341 |
Assert(!GISTSearchItemIsHeap(*pageItem)); |
| 342 |
|
| 343 |
buffer = ReadBuffer(scan->indexRelation, pageItem->blkno); |
| 344 |
LockBuffer(buffer, GIST_SHARE); |
| 345 |
PredicateLockPage(r, BufferGetBlockNumber(buffer), scan->xs_snapshot); |
| 346 |
gistcheckpage(scan->indexRelation, buffer); |
| 347 |
page = BufferGetPage(buffer); |
| 348 |
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 |
if (!XLogRecPtrIsInvalid(pageItem->data.parentlsn) && |
| 357 |
(GistFollowRight(page) || |
| 358 |
pageItem->data.parentlsn < GistPageGetNSN(page)) && |
| 359 |
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 */ |
| 365 |
Assert(myDistances != NULL); |
| 366 |
|
| 367 |
oldcxt = MemoryContextSwitchTo(so->queueCxt); |
| 368 |
|
| 369 |
/* Create new GISTSearchItem for the right sibling index page */ |
| 370 |
item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys)); |
| 371 |
item->blkno = opaque->rightlink; |
| 372 |
item->data.parentlsn = pageItem->data.parentlsn; |
| 373 |
|
| 374 |
/* Insert it into the queue using same distances as for this page */ |
| 375 |
memcpy(item->distances, myDistances, |
| 376 |
sizeof(item->distances[0]) * scan->numberOfOrderBys); |
| 377 |
|
| 378 |
pairingheap_add(so->queue, &item->phNode); |
| 379 |
|
| 380 |
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 |
*/ |
| 391 |
if (GistPageIsDeleted(page)) |
| 392 |
{ |
| 393 |
UnlockReleaseBuffer(buffer); |
| 394 |
return; |
| 395 |
} |
| 396 |
|
| 397 |
so->nPageData = so->curPageData = 0; |
| 398 |
scan->xs_hitup = NULL; /* might point into pageDataCxt */ |
| 399 |
if (so->pageDataCxt) |
| 400 |
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 |
*/ |
| 407 |
so->curPageLSN = BufferGetLSNAtomic(buffer); |
| 408 |
|
| 409 |
/* |
| 410 |
* check all tuples on page |
| 411 |
*/ |
| 412 |
maxoff = PageGetMaxOffsetNumber(page); |
| 413 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 414 |
{ |
| 415 |
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 |
if (scan->ignore_killed_tuples && ItemIdIsDead(iid)) |
| 426 |
continue; |
| 427 |
|
| 428 |
it = (IndexTuple) PageGetItem(page, iid); |
| 429 |
|
| 430 |
/* |
| 431 |
* Must call gistindex_keytest in tempCxt, and clean up any leftover |
| 432 |
* junk afterward. |
| 433 |
*/ |
| 434 |
oldcxt = MemoryContextSwitchTo(so->giststate->tempCxt); |
| 435 |
|
| 436 |
match = gistindex_keytest(scan, it, page, i, |
| 437 |
&recheck, &recheck_distances); |
| 438 |
|
| 439 |
MemoryContextSwitchTo(oldcxt); |
| 440 |
MemoryContextReset(so->giststate->tempCxt); |
| 441 |
|
| 442 |
/* Ignore tuple if it doesn't match */ |
| 443 |
if (!match) |
| 444 |
continue; |
| 445 |
|
| 446 |
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 |
tbm_add_tuples(tbm, &it->t_tid, 1, recheck); |
| 453 |
(*ntids)++; |
| 454 |
} |
| 455 |
else if (scan->numberOfOrderBys == 0 && GistPageIsLeaf(page)) |
| 456 |
{ |
| 457 |
/* |
| 458 |
* Non-ordered scan, so report tuples in so->pageData[] |
| 459 |
*/ |
| 460 |
so->pageData[so->nPageData].heapPtr = it->t_tid; |
| 461 |
so->pageData[so->nPageData].recheck = recheck; |
| 462 |
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 |
*/ |
| 468 |
if (scan->xs_want_itup) |
| 469 |
{ |
| 470 |
oldcxt = MemoryContextSwitchTo(so->pageDataCxt); |
| 471 |
so->pageData[so->nPageData].recontup = |
| 472 |
gistFetchTuple(giststate, r, it); |
| 473 |
MemoryContextSwitchTo(oldcxt); |
| 474 |
} |
| 475 |
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; |
| 485 |
int nOrderBys = scan->numberOfOrderBys; |
| 486 |
|
| 487 |
oldcxt = MemoryContextSwitchTo(so->queueCxt); |
| 488 |
|
| 489 |
/* Create new GISTSearchItem for this item */ |
| 490 |
item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys)); |
| 491 |
|
| 492 |
if (GistPageIsLeaf(page)) |
| 493 |
{ |
| 494 |
/* Creating heap-tuple GISTSearchItem */ |
| 495 |
item->blkno = InvalidBlockNumber; |
| 496 |
item->data.heap.heapPtr = it->t_tid; |
| 497 |
item->data.heap.recheck = recheck; |
| 498 |
item->data.heap.recheckDistances = recheck_distances; |
| 499 |
|
| 500 |
/* |
| 501 |
* In an index-only scan, also fetch the data from the tuple. |
| 502 |
*/ |
| 503 |
if (scan->xs_want_itup) |
| 504 |
item->data.heap.recontup = gistFetchTuple(giststate, r, it); |
| 505 |
} |
| 506 |
else |
| 507 |
{ |
| 508 |
/* Creating index-page GISTSearchItem */ |
| 509 |
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 |
*/ |
| 516 |
item->data.parentlsn = BufferGetLSNAtomic(buffer); |
| 517 |
} |
| 518 |
|
| 519 |
/* Insert it into the queue using new distance data */ |
| 520 |
memcpy(item->distances, so->distances, |
| 521 |
sizeof(item->distances[0]) * nOrderBys); |
| 522 |
|
| 523 |
pairingheap_add(so->queue, &item->phNode); |
| 524 |
|
| 525 |
MemoryContextSwitchTo(oldcxt); |
| 526 |
} |
| 527 |
} |
| 528 |
|
| 529 |
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 |
getNextGISTSearchItem(GISTScanOpaque so) |
| 539 |
{ |
| 540 |
GISTSearchItem *item; |
| 541 |
|
| 542 |
if (!pairingheap_is_empty(so->queue)) |
| 543 |
{ |
| 544 |
item = (GISTSearchItem *) pairingheap_remove_first(so->queue); |
| 545 |
} |
| 546 |
else |
| 547 |
{ |
| 548 |
/* Done when both heaps are empty */ |
| 549 |
item = NULL; |
| 550 |
} |
| 551 |
|
| 552 |
/* Return item; caller is responsible to pfree it */ |
| 553 |
return item; |
| 554 |
} |
| 555 |
|
| 556 |
/* |
| 557 |
* Fetch next heap tuple in an ordered search |
| 558 |
*/ |
| 559 |
static bool |
| 560 |
getNextNearest(IndexScanDesc scan) |
| 561 |
{ |
| 562 |
GISTScanOpaque so = (GISTScanOpaque) scan->opaque; |
| 563 |
bool res = false; |
| 564 |
|
| 565 |
if (scan->xs_hitup) |
| 566 |
{ |
| 567 |
/* free previously returned tuple */ |
| 568 |
pfree(scan->xs_hitup); |
| 569 |
scan->xs_hitup = NULL; |
| 570 |
} |
| 571 |
|
| 572 |
do |
| 573 |
{ |
| 574 |
GISTSearchItem *item = getNextGISTSearchItem(so); |
| 575 |
|
| 576 |
if (!item) |
| 577 |
break; |
| 578 |
|
| 579 |
if (GISTSearchItemIsHeap(*item)) |
| 580 |
{ |
| 581 |
/* found a heap item at currently minimal distance */ |
| 582 |
scan->xs_heaptid = item->data.heap.heapPtr; |
| 583 |
scan->xs_recheck = item->data.heap.recheck; |
| 584 |
|
| 585 |
index_store_float8_orderby_distances(scan, so->orderByTypes, |
| 586 |
item->distances, |
| 587 |
item->data.heap.recheckDistances); |
| 588 |
|
| 589 |
/* in an index-only scan, also return the reconstructed tuple. */ |
| 590 |
if (scan->xs_want_itup) |
| 591 |
scan->xs_hitup = item->data.heap.recontup; |
| 592 |
res = true; |
| 593 |
} |
| 594 |
else |
| 595 |
{ |
| 596 |
/* visit an index page, extract its items into queue */ |
| 597 |
CHECK_FOR_INTERRUPTS(); |
| 598 |
|
| 599 |
gistScanPage(scan, item, item->distances, NULL, NULL); |
| 600 |
} |
| 601 |
|
| 602 |
pfree(item); |
| 603 |
} while (!res); |
| 604 |
|
| 605 |
return res; |
| 606 |
} |
| 607 |
|
| 608 |
/* |
| 609 |
* gistgettuple() -- Get the next tuple in the scan |
| 610 |
*/ |
| 611 |
bool |
| 612 |
gistgettuple(IndexScanDesc scan, ScanDirection dir) |
| 613 |
{ |
| 614 |
GISTScanOpaque so = (GISTScanOpaque) scan->opaque; |
| 615 |
|
| 616 |
if (dir != ForwardScanDirection) |
| 617 |
elog(ERROR, "GiST only supports forward scan direction"); |
| 618 |
|
| 619 |
if (!so->qual_ok) |
| 620 |
return false; |
| 621 |
|
| 622 |
if (so->firstCall) |
| 623 |
{ |
| 624 |
/* Begin the scan by processing the root page */ |
| 625 |
GISTSearchItem fakeItem; |
| 626 |
|
| 627 |
pgstat_count_index_scan(scan->indexRelation); |
| 628 |
if (scan->instrument) |
| 629 |
scan->instrument->nsearches++; |
| 630 |
|
| 631 |
so->firstCall = false; |
| 632 |
so->curPageData = so->nPageData = 0; |
| 633 |
scan->xs_hitup = NULL; |
| 634 |
if (so->pageDataCxt) |
| 635 |
MemoryContextReset(so->pageDataCxt); |
| 636 |
|
| 637 |
fakeItem.blkno = GIST_ROOT_BLKNO; |
| 638 |
memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN)); |
| 639 |
gistScanPage(scan, &fakeItem, NULL, NULL, NULL); |
| 640 |
} |
| 641 |
|
| 642 |
if (scan->numberOfOrderBys > 0) |
| 643 |
{ |
| 644 |
/* Must fetch tuples in strict distance order */ |
| 645 |
return getNextNearest(scan); |
| 646 |
} |
| 647 |
else |
| 648 |
{ |
| 649 |
/* Fetch tuples index-page-at-a-time */ |
| 650 |
for (;;) |
| 651 |
{ |
| 652 |
if (so->curPageData < so->nPageData) |
| 653 |
{ |
| 654 |
if (scan->kill_prior_tuple && so->curPageData > 0) |
| 655 |
{ |
| 656 |
|
| 657 |
if (so->killedItems == NULL) |
| 658 |
{ |
| 659 |
MemoryContext oldCxt = |
| 660 |
MemoryContextSwitchTo(so->giststate->scanCxt); |
| 661 |
|
| 662 |
so->killedItems = |
| 663 |
(OffsetNumber *) palloc(MaxIndexTuplesPerPage |
| 664 |
* sizeof(OffsetNumber)); |
| 665 |
|
| 666 |
MemoryContextSwitchTo(oldCxt); |
| 667 |
} |
| 668 |
if (so->numKilled < MaxIndexTuplesPerPage) |
| 669 |
so->killedItems[so->numKilled++] = |
| 670 |
so->pageData[so->curPageData - 1].offnum; |
| 671 |
} |
| 672 |
/* continuing to return tuples from a leaf page */ |
| 673 |
scan->xs_heaptid = so->pageData[so->curPageData].heapPtr; |
| 674 |
scan->xs_recheck = so->pageData[so->curPageData].recheck; |
| 675 |
|
| 676 |
/* in an index-only scan, also return the reconstructed tuple */ |
| 677 |
if (scan->xs_want_itup) |
| 678 |
scan->xs_hitup = so->pageData[so->curPageData].recontup; |
| 679 |
|
| 680 |
so->curPageData++; |
| 681 |
|
| 682 |
return true; |
| 683 |
} |
| 684 |
|
| 685 |
/* |
| 686 |
* Check the last returned tuple and add it to killedItems if |
| 687 |
* necessary |
| 688 |
*/ |
| 689 |
if (scan->kill_prior_tuple |
| 690 |
&& so->curPageData > 0 |
| 691 |
&& so->curPageData == so->nPageData) |
| 692 |
{ |
| 693 |
|
| 694 |
if (so->killedItems == NULL) |
| 695 |
{ |
| 696 |
MemoryContext oldCxt = |
| 697 |
MemoryContextSwitchTo(so->giststate->scanCxt); |
| 698 |
|
| 699 |
so->killedItems = |
| 700 |
(OffsetNumber *) palloc(MaxIndexTuplesPerPage |
| 701 |
* sizeof(OffsetNumber)); |
| 702 |
|
| 703 |
MemoryContextSwitchTo(oldCxt); |
| 704 |
} |
| 705 |
if (so->numKilled < MaxIndexTuplesPerPage) |
| 706 |
so->killedItems[so->numKilled++] = |
| 707 |
so->pageData[so->curPageData - 1].offnum; |
| 708 |
} |
| 709 |
/* find and process the next index page */ |
| 710 |
do |
| 711 |
{ |
| 712 |
GISTSearchItem *item; |
| 713 |
|
| 714 |
if ((so->curBlkno != InvalidBlockNumber) && (so->numKilled > 0)) |
| 715 |
gistkillitems(scan); |
| 716 |
|
| 717 |
item = getNextGISTSearchItem(so); |
| 718 |
|
| 719 |
if (!item) |
| 720 |
return false; |
| 721 |
|
| 722 |
CHECK_FOR_INTERRUPTS(); |
| 723 |
|
| 724 |
/* save current item BlockNumber for next gistkillitems() call */ |
| 725 |
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 |
*/ |
| 733 |
gistScanPage(scan, item, item->distances, NULL, NULL); |
| 734 |
|
| 735 |
pfree(item); |
| 736 |
} while (so->nPageData == 0); |
| 737 |
} |
| 738 |
} |
| 739 |
} |
| 740 |
|
| 741 |
/* |
| 742 |
* gistgetbitmap() -- Get a bitmap of all heap tuple locations |
| 743 |
*/ |
| 744 |
int64 |
| 745 |
gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm) |
| 746 |
{ |
| 747 |
GISTScanOpaque so = (GISTScanOpaque) scan->opaque; |
| 748 |
int64 ntids = 0; |
| 749 |
GISTSearchItem fakeItem; |
| 750 |
|
| 751 |
if (!so->qual_ok) |
| 752 |
return 0; |
| 753 |
|
| 754 |
pgstat_count_index_scan(scan->indexRelation); |
| 755 |
if (scan->instrument) |
| 756 |
scan->instrument->nsearches++; |
| 757 |
|
| 758 |
/* Begin the scan by processing the root page */ |
| 759 |
so->curPageData = so->nPageData = 0; |
| 760 |
scan->xs_hitup = NULL; |
| 761 |
if (so->pageDataCxt) |
| 762 |
MemoryContextReset(so->pageDataCxt); |
| 763 |
|
| 764 |
fakeItem.blkno = GIST_ROOT_BLKNO; |
| 765 |
memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN)); |
| 766 |
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 (;;) |
| 773 |
{ |
| 774 |
GISTSearchItem *item = getNextGISTSearchItem(so); |
| 775 |
|
| 776 |
if (!item) |
| 777 |
break; |
| 778 |
|
| 779 |
CHECK_FOR_INTERRUPTS(); |
| 780 |
|
| 781 |
gistScanPage(scan, item, item->distances, tbm, &ntids); |
| 782 |
|
| 783 |
pfree(item); |
| 784 |
} |
| 785 |
|
| 786 |
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 |
gistcanreturn(Relation index, int attno) |
| 798 |
{ |
| 799 |
if (attno > IndexRelationGetNumberOfKeyAttributes(index) || |
| 800 |
OidIsValid(index_getprocid(index, attno, GIST_FETCH_PROC)) || |
| 801 |
!OidIsValid(index_getprocid(index, attno, GIST_COMPRESS_PROC))) |
| 802 |
return true; |
| 803 |
else |
| 804 |
return false; |
| 805 |
} |