| 1 |
/*------------------------------------------------------------------------- |
| 2 |
* |
| 3 |
* nbtsearch.c |
| 4 |
* Search code for postgres btrees. |
| 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/nbtree/nbtsearch.c |
| 12 |
* |
| 13 |
*------------------------------------------------------------------------- |
| 14 |
*/ |
| 15 |
|
| 16 |
#include "postgres.h" |
| 17 |
|
| 18 |
#include "access/nbtree.h" |
| 19 |
#include "access/relscan.h" |
| 20 |
#include "access/xact.h" |
| 21 |
#include "miscadmin.h" |
| 22 |
#include "pgstat.h" |
| 23 |
#include "storage/predicate.h" |
| 24 |
#include "utils/lsyscache.h" |
| 25 |
#include "utils/rel.h" |
| 26 |
|
| 27 |
|
| 28 |
static inline void _bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so); |
| 29 |
static Buffer _bt_moveright(Relation rel, Relation heaprel, BTScanInsert key, |
| 30 |
Buffer buf, bool forupdate, BTStack stack, |
| 31 |
int access); |
| 32 |
static OffsetNumber _bt_binsrch(Relation rel, BTScanInsert key, Buffer buf); |
| 33 |
static int _bt_binsrch_posting(BTScanInsert key, Page page, |
| 34 |
OffsetNumber offnum); |
| 35 |
static bool _bt_readpage(IndexScanDesc scan, ScanDirection dir, |
| 36 |
OffsetNumber offnum, bool firstpage); |
| 37 |
static void _bt_saveitem(BTScanOpaque so, int itemIndex, |
| 38 |
OffsetNumber offnum, IndexTuple itup); |
| 39 |
static int _bt_setuppostingitems(BTScanOpaque so, int itemIndex, |
| 40 |
OffsetNumber offnum, ItemPointer heapTid, |
| 41 |
IndexTuple itup); |
| 42 |
static inline void _bt_savepostingitem(BTScanOpaque so, int itemIndex, |
| 43 |
OffsetNumber offnum, |
| 44 |
ItemPointer heapTid, int tupleOffset); |
| 45 |
static inline void _bt_returnitem(IndexScanDesc scan, BTScanOpaque so); |
| 46 |
static bool _bt_steppage(IndexScanDesc scan, ScanDirection dir); |
| 47 |
static bool _bt_readfirstpage(IndexScanDesc scan, OffsetNumber offnum, |
| 48 |
ScanDirection dir); |
| 49 |
static bool _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, |
| 50 |
BlockNumber lastcurrblkno, ScanDirection dir, |
| 51 |
bool seized); |
| 52 |
static Buffer _bt_lock_and_validate_left(Relation rel, BlockNumber *blkno, |
| 53 |
BlockNumber lastcurrblkno); |
| 54 |
static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir); |
| 55 |
|
| 56 |
|
| 57 |
/* |
| 58 |
* _bt_drop_lock_and_maybe_pin() |
| 59 |
* |
| 60 |
* Unlock so->currPos.buf. If scan is so->dropPin, drop the pin, too. |
| 61 |
* Dropping the pin prevents VACUUM from blocking on acquiring a cleanup lock. |
| 62 |
*/ |
| 63 |
static inline void |
| 64 |
_bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so) |
| 65 |
{ |
| 66 |
if (!so->dropPin) |
| 67 |
{ |
| 68 |
/* Just drop the lock (not the pin) */ |
| 69 |
_bt_unlockbuf(rel, so->currPos.buf); |
| 70 |
return; |
| 71 |
} |
| 72 |
|
| 73 |
/* |
| 74 |
* Drop both the lock and the pin. |
| 75 |
* |
| 76 |
* Have to set so->currPos.lsn so that _bt_killitems has a way to detect |
| 77 |
* when concurrent heap TID recycling by VACUUM might have taken place. |
| 78 |
*/ |
| 79 |
Assert(RelationNeedsWAL(rel)); |
| 80 |
so->currPos.lsn = BufferGetLSNAtomic(so->currPos.buf); |
| 81 |
_bt_relbuf(rel, so->currPos.buf); |
| 82 |
so->currPos.buf = InvalidBuffer; |
| 83 |
} |
| 84 |
|
| 85 |
/* |
| 86 |
* _bt_search() -- Search the tree for a particular scankey, |
| 87 |
* or more precisely for the first leaf page it could be on. |
| 88 |
* |
| 89 |
* The passed scankey is an insertion-type scankey (see nbtree/README), |
| 90 |
* but it can omit the rightmost column(s) of the index. |
| 91 |
* |
| 92 |
* Return value is a stack of parent-page pointers (i.e. there is no entry for |
| 93 |
* the leaf level/page). *bufP is set to the address of the leaf-page buffer, |
| 94 |
* which is locked and pinned. No locks are held on the parent pages, |
| 95 |
* however! |
| 96 |
* |
| 97 |
* The returned buffer is locked according to access parameter. Additionally, |
| 98 |
* access = BT_WRITE will allow an empty root page to be created and returned. |
| 99 |
* When access = BT_READ, an empty index will result in *bufP being set to |
| 100 |
* InvalidBuffer. Also, in BT_WRITE mode, any incomplete splits encountered |
| 101 |
* during the search will be finished. |
| 102 |
* |
| 103 |
* heaprel must be provided by callers that pass access = BT_WRITE, since we |
| 104 |
* might need to allocate a new root page for caller -- see _bt_allocbuf. |
| 105 |
*/ |
| 106 |
BTStack |
| 107 |
_bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, |
| 108 |
int access) |
| 109 |
{ |
| 110 |
BTStack stack_in = NULL; |
| 111 |
int page_access = BT_READ; |
| 112 |
|
| 113 |
/* heaprel must be set whenever _bt_allocbuf is reachable */ |
| 114 |
Assert(access == BT_READ || access == BT_WRITE); |
| 115 |
Assert(access == BT_READ || heaprel != NULL); |
| 116 |
|
| 117 |
/* Get the root page to start with */ |
| 118 |
*bufP = _bt_getroot(rel, heaprel, access); |
| 119 |
|
| 120 |
/* If index is empty and access = BT_READ, no root page is created. */ |
| 121 |
if (!BufferIsValid(*bufP)) |
| 122 |
return (BTStack) NULL; |
| 123 |
|
| 124 |
/* Loop iterates once per level descended in the tree */ |
| 125 |
for (;;) |
| 126 |
{ |
| 127 |
Page page; |
| 128 |
BTPageOpaque opaque; |
| 129 |
OffsetNumber offnum; |
| 130 |
ItemId itemid; |
| 131 |
IndexTuple itup; |
| 132 |
BlockNumber child; |
| 133 |
BTStack new_stack; |
| 134 |
|
| 135 |
/* |
| 136 |
* Race -- the page we just grabbed may have split since we read its |
| 137 |
* downlink in its parent page (or the metapage). If it has, we may |
| 138 |
* need to move right to its new sibling. Do that. |
| 139 |
* |
| 140 |
* In write-mode, allow _bt_moveright to finish any incomplete splits |
| 141 |
* along the way. Strictly speaking, we'd only need to finish an |
| 142 |
* incomplete split on the leaf page we're about to insert to, not on |
| 143 |
* any of the upper levels (internal pages with incomplete splits are |
| 144 |
* also taken care of in _bt_getstackbuf). But this is a good |
| 145 |
* opportunity to finish splits of internal pages too. |
| 146 |
*/ |
| 147 |
*bufP = _bt_moveright(rel, heaprel, key, *bufP, (access == BT_WRITE), |
| 148 |
stack_in, page_access); |
| 149 |
|
| 150 |
/* if this is a leaf page, we're done */ |
| 151 |
page = BufferGetPage(*bufP); |
| 152 |
opaque = BTPageGetOpaque(page); |
| 153 |
if (P_ISLEAF(opaque)) |
| 154 |
break; |
| 155 |
|
| 156 |
/* |
| 157 |
* Find the appropriate pivot tuple on this page. Its downlink points |
| 158 |
* to the child page that we're about to descend to. |
| 159 |
*/ |
| 160 |
offnum = _bt_binsrch(rel, key, *bufP); |
| 161 |
itemid = PageGetItemId(page, offnum); |
| 162 |
itup = (IndexTuple) PageGetItem(page, itemid); |
| 163 |
Assert(BTreeTupleIsPivot(itup) || !key->heapkeyspace); |
| 164 |
child = BTreeTupleGetDownLink(itup); |
| 165 |
|
| 166 |
/* |
| 167 |
* We need to save the location of the pivot tuple we chose in a new |
| 168 |
* stack entry for this page/level. If caller ends up splitting a |
| 169 |
* page one level down, it usually ends up inserting a new pivot |
| 170 |
* tuple/downlink immediately after the location recorded here. |
| 171 |
*/ |
| 172 |
new_stack = (BTStack) palloc(sizeof(BTStackData)); |
| 173 |
new_stack->bts_blkno = BufferGetBlockNumber(*bufP); |
| 174 |
new_stack->bts_offset = offnum; |
| 175 |
new_stack->bts_parent = stack_in; |
| 176 |
|
| 177 |
/* |
| 178 |
* Page level 1 is lowest non-leaf page level prior to leaves. So, if |
| 179 |
* we're on the level 1 and asked to lock leaf page in write mode, |
| 180 |
* then lock next page in write mode, because it must be a leaf. |
| 181 |
*/ |
| 182 |
if (opaque->btpo_level == 1 && access == BT_WRITE) |
| 183 |
page_access = BT_WRITE; |
| 184 |
|
| 185 |
/* drop the read lock on the page, then acquire one on its child */ |
| 186 |
*bufP = _bt_relandgetbuf(rel, *bufP, child, page_access); |
| 187 |
|
| 188 |
/* okay, all set to move down a level */ |
| 189 |
stack_in = new_stack; |
| 190 |
} |
| 191 |
|
| 192 |
/* |
| 193 |
* If we're asked to lock leaf in write mode, but didn't manage to, then |
| 194 |
* relock. This should only happen when the root page is a leaf page (and |
| 195 |
* the only page in the index other than the metapage). |
| 196 |
*/ |
| 197 |
if (access == BT_WRITE && page_access == BT_READ) |
| 198 |
{ |
| 199 |
/* trade in our read lock for a write lock */ |
| 200 |
_bt_unlockbuf(rel, *bufP); |
| 201 |
_bt_lockbuf(rel, *bufP, BT_WRITE); |
| 202 |
|
| 203 |
/* |
| 204 |
* Race -- the leaf page may have split after we dropped the read lock |
| 205 |
* but before we acquired a write lock. If it has, we may need to |
| 206 |
* move right to its new sibling. Do that. |
| 207 |
*/ |
| 208 |
*bufP = _bt_moveright(rel, heaprel, key, *bufP, true, stack_in, BT_WRITE); |
| 209 |
} |
| 210 |
|
| 211 |
return stack_in; |
| 212 |
} |
| 213 |
|
| 214 |
/* |
| 215 |
* _bt_moveright() -- move right in the btree if necessary. |
| 216 |
* |
| 217 |
* When we follow a pointer to reach a page, it is possible that |
| 218 |
* the page has changed in the meanwhile. If this happens, we're |
| 219 |
* guaranteed that the page has "split right" -- that is, that any |
| 220 |
* data that appeared on the page originally is either on the page |
| 221 |
* or strictly to the right of it. |
| 222 |
* |
| 223 |
* This routine decides whether or not we need to move right in the |
| 224 |
* tree by examining the high key entry on the page. If that entry is |
| 225 |
* strictly less than the scankey, or <= the scankey in the |
| 226 |
* key.nextkey=true case, then we followed the wrong link and we need |
| 227 |
* to move right. |
| 228 |
* |
| 229 |
* The passed insertion-type scankey can omit the rightmost column(s) of the |
| 230 |
* index. (see nbtree/README) |
| 231 |
* |
| 232 |
* When key.nextkey is false (the usual case), we are looking for the first |
| 233 |
* item >= key. When key.nextkey is true, we are looking for the first item |
| 234 |
* strictly greater than key. |
| 235 |
* |
| 236 |
* If forupdate is true, we will attempt to finish any incomplete splits |
| 237 |
* that we encounter. This is required when locking a target page for an |
| 238 |
* insertion, because we don't allow inserting on a page before the split is |
| 239 |
* completed. 'heaprel' and 'stack' are only used if forupdate is true. |
| 240 |
* |
| 241 |
* On entry, we have the buffer pinned and a lock of the type specified by |
| 242 |
* 'access'. If we move right, we release the buffer and lock and acquire |
| 243 |
* the same on the right sibling. Return value is the buffer we stop at. |
| 244 |
*/ |
| 245 |
static Buffer |
| 246 |
_bt_moveright(Relation rel, |
| 247 |
Relation heaprel, |
| 248 |
BTScanInsert key, |
| 249 |
Buffer buf, |
| 250 |
bool forupdate, |
| 251 |
BTStack stack, |
| 252 |
int access) |
| 253 |
{ |
| 254 |
Page page; |
| 255 |
BTPageOpaque opaque; |
| 256 |
int32 cmpval; |
| 257 |
|
| 258 |
Assert(!forupdate || heaprel != NULL); |
| 259 |
|
| 260 |
/* |
| 261 |
* When nextkey = false (normal case): if the scan key that brought us to |
| 262 |
* this page is > the high key stored on the page, then the page has split |
| 263 |
* and we need to move right. (pg_upgrade'd !heapkeyspace indexes could |
| 264 |
* have some duplicates to the right as well as the left, but that's |
| 265 |
* something that's only ever dealt with on the leaf level, after |
| 266 |
* _bt_search has found an initial leaf page.) |
| 267 |
* |
| 268 |
* When nextkey = true: move right if the scan key is >= page's high key. |
| 269 |
* (Note that key.scantid cannot be set in this case.) |
| 270 |
* |
| 271 |
* The page could even have split more than once, so scan as far as |
| 272 |
* needed. |
| 273 |
* |
| 274 |
* We also have to move right if we followed a link that brought us to a |
| 275 |
* dead page. |
| 276 |
*/ |
| 277 |
cmpval = key->nextkey ? 0 : 1; |
| 278 |
|
| 279 |
for (;;) |
| 280 |
{ |
| 281 |
page = BufferGetPage(buf); |
| 282 |
opaque = BTPageGetOpaque(page); |
| 283 |
|
| 284 |
if (P_RIGHTMOST(opaque)) |
| 285 |
break; |
| 286 |
|
| 287 |
/* |
| 288 |
* Finish any incomplete splits we encounter along the way. |
| 289 |
*/ |
| 290 |
if (forupdate && P_INCOMPLETE_SPLIT(opaque)) |
| 291 |
{ |
| 292 |
BlockNumber blkno = BufferGetBlockNumber(buf); |
| 293 |
|
| 294 |
/* upgrade our lock if necessary */ |
| 295 |
if (access == BT_READ) |
| 296 |
{ |
| 297 |
_bt_unlockbuf(rel, buf); |
| 298 |
_bt_lockbuf(rel, buf, BT_WRITE); |
| 299 |
} |
| 300 |
|
| 301 |
if (P_INCOMPLETE_SPLIT(opaque)) |
| 302 |
_bt_finish_split(rel, heaprel, buf, stack); |
| 303 |
else |
| 304 |
_bt_relbuf(rel, buf); |
| 305 |
|
| 306 |
/* re-acquire the lock in the right mode, and re-check */ |
| 307 |
buf = _bt_getbuf(rel, blkno, access); |
| 308 |
continue; |
| 309 |
} |
| 310 |
|
| 311 |
if (P_IGNORE(opaque) || _bt_compare(rel, key, page, P_HIKEY) >= cmpval) |
| 312 |
{ |
| 313 |
/* step right one page */ |
| 314 |
buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access); |
| 315 |
continue; |
| 316 |
} |
| 317 |
else |
| 318 |
break; |
| 319 |
} |
| 320 |
|
| 321 |
if (P_IGNORE(opaque)) |
| 322 |
elog(ERROR, "fell off the end of index \"%s\"", |
| 323 |
RelationGetRelationName(rel)); |
| 324 |
|
| 325 |
return buf; |
| 326 |
} |
| 327 |
|
| 328 |
/* |
| 329 |
* _bt_binsrch() -- Do a binary search for a key on a particular page. |
| 330 |
* |
| 331 |
* On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber |
| 332 |
* of the last key < given scankey, or last key <= given scankey if nextkey |
| 333 |
* is true. (Since _bt_compare treats the first data key of such a page as |
| 334 |
* minus infinity, there will be at least one key < scankey, so the result |
| 335 |
* always points at one of the keys on the page.) |
| 336 |
* |
| 337 |
* On a leaf page, _bt_binsrch() returns the final result of the initial |
| 338 |
* positioning process that started with _bt_first's call to _bt_search. |
| 339 |
* We're returning a non-pivot tuple offset, so things are a little different. |
| 340 |
* It is possible that we'll return an offset that's either past the last |
| 341 |
* non-pivot slot, or (in the case of a backward scan) before the first slot. |
| 342 |
* |
| 343 |
* This procedure is not responsible for walking right, it just examines |
| 344 |
* the given page. _bt_binsrch() has no lock or refcount side effects |
| 345 |
* on the buffer. |
| 346 |
*/ |
| 347 |
static OffsetNumber |
| 348 |
_bt_binsrch(Relation rel, |
| 349 |
BTScanInsert key, |
| 350 |
Buffer buf) |
| 351 |
{ |
| 352 |
Page page; |
| 353 |
BTPageOpaque opaque; |
| 354 |
OffsetNumber low, |
| 355 |
high; |
| 356 |
int32 result, |
| 357 |
cmpval; |
| 358 |
|
| 359 |
page = BufferGetPage(buf); |
| 360 |
opaque = BTPageGetOpaque(page); |
| 361 |
|
| 362 |
/* Requesting nextkey semantics while using scantid seems nonsensical */ |
| 363 |
Assert(!key->nextkey || key->scantid == NULL); |
| 364 |
/* scantid-set callers must use _bt_binsrch_insert() on leaf pages */ |
| 365 |
Assert(!P_ISLEAF(opaque) || key->scantid == NULL); |
| 366 |
|
| 367 |
low = P_FIRSTDATAKEY(opaque); |
| 368 |
high = PageGetMaxOffsetNumber(page); |
| 369 |
|
| 370 |
/* |
| 371 |
* If there are no keys on the page, return the first available slot. Note |
| 372 |
* this covers two cases: the page is really empty (no keys), or it |
| 373 |
* contains only a high key. The latter case is possible after vacuuming. |
| 374 |
* This can never happen on an internal page, however, since they are |
| 375 |
* never empty (an internal page must have at least one child). |
| 376 |
*/ |
| 377 |
if (unlikely(high < low)) |
| 378 |
return low; |
| 379 |
|
| 380 |
/* |
| 381 |
* Binary search to find the first key on the page >= scan key, or first |
| 382 |
* key > scankey when nextkey is true. |
| 383 |
* |
| 384 |
* For nextkey=false (cmpval=1), the loop invariant is: all slots before |
| 385 |
* 'low' are < scan key, all slots at or after 'high' are >= scan key. |
| 386 |
* |
| 387 |
* For nextkey=true (cmpval=0), the loop invariant is: all slots before |
| 388 |
* 'low' are <= scan key, all slots at or after 'high' are > scan key. |
| 389 |
* |
| 390 |
* We can fall out when high == low. |
| 391 |
*/ |
| 392 |
high++; /* establish the loop invariant for high */ |
| 393 |
|
| 394 |
cmpval = key->nextkey ? 0 : 1; /* select comparison value */ |
| 395 |
|
| 396 |
while (high > low) |
| 397 |
{ |
| 398 |
OffsetNumber mid = low + ((high - low) / 2); |
| 399 |
|
| 400 |
/* We have low <= mid < high, so mid points at a real slot */ |
| 401 |
|
| 402 |
result = _bt_compare(rel, key, page, mid); |
| 403 |
|
| 404 |
if (result >= cmpval) |
| 405 |
low = mid + 1; |
| 406 |
else |
| 407 |
high = mid; |
| 408 |
} |
| 409 |
|
| 410 |
/* |
| 411 |
* At this point we have high == low. |
| 412 |
* |
| 413 |
* On a leaf page we always return the first non-pivot tuple >= scan key |
| 414 |
* (resp. > scan key) for forward scan callers. For backward scans, it's |
| 415 |
* always the _last_ non-pivot tuple < scan key (resp. <= scan key). |
| 416 |
*/ |
| 417 |
if (P_ISLEAF(opaque)) |
| 418 |
{ |
| 419 |
/* |
| 420 |
* In the backward scan case we're supposed to locate the last |
| 421 |
* matching tuple on the leaf level -- not the first matching tuple |
| 422 |
* (the last tuple will be the first one returned by the scan). |
| 423 |
* |
| 424 |
* At this point we've located the first non-pivot tuple immediately |
| 425 |
* after the last matching tuple (which might just be maxoff + 1). |
| 426 |
* Compensate by stepping back. |
| 427 |
*/ |
| 428 |
if (key->backward) |
| 429 |
return OffsetNumberPrev(low); |
| 430 |
|
| 431 |
return low; |
| 432 |
} |
| 433 |
|
| 434 |
/* |
| 435 |
* On a non-leaf page, return the last key < scan key (resp. <= scan key). |
| 436 |
* There must be one if _bt_compare() is playing by the rules. |
| 437 |
* |
| 438 |
* _bt_compare() will seldom see any exactly-matching pivot tuples, since |
| 439 |
* a truncated -inf heap TID is usually enough to prevent it altogether. |
| 440 |
* Even omitted scan key entries are treated as > truncated attributes. |
| 441 |
* |
| 442 |
* However, during backward scans _bt_compare() interprets omitted scan |
| 443 |
* key attributes as == corresponding truncated -inf attributes instead. |
| 444 |
* This works just like < would work here. Under this scheme, < strategy |
| 445 |
* backward scans will always directly descend to the correct leaf page. |
| 446 |
* In particular, they will never incur an "extra" leaf page access with a |
| 447 |
* scan key that happens to contain the same prefix of values as some |
| 448 |
* pivot tuple's untruncated prefix. VACUUM relies on this guarantee when |
| 449 |
* it uses a leaf page high key to "re-find" a page undergoing deletion. |
| 450 |
*/ |
| 451 |
Assert(low > P_FIRSTDATAKEY(opaque)); |
| 452 |
|
| 453 |
return OffsetNumberPrev(low); |
| 454 |
} |
| 455 |
|
| 456 |
/* |
| 457 |
* |
| 458 |
* _bt_binsrch_insert() -- Cacheable, incremental leaf page binary search. |
| 459 |
* |
| 460 |
* Like _bt_binsrch(), but with support for caching the binary search |
| 461 |
* bounds. Only used during insertion, and only on the leaf page that it |
| 462 |
* looks like caller will insert tuple on. Exclusive-locked and pinned |
| 463 |
* leaf page is contained within insertstate. |
| 464 |
* |
| 465 |
* Caches the bounds fields in insertstate so that a subsequent call can |
| 466 |
* reuse the low and strict high bounds of original binary search. Callers |
| 467 |
* that use these fields directly must be prepared for the case where low |
| 468 |
* and/or stricthigh are not on the same page (one or both exceed maxoff |
| 469 |
* for the page). The case where there are no items on the page (high < |
| 470 |
* low) makes bounds invalid. |
| 471 |
* |
| 472 |
* Caller is responsible for invalidating bounds when it modifies the page |
| 473 |
* before calling here a second time, and for dealing with posting list |
| 474 |
* tuple matches (callers can use insertstate's postingoff field to |
| 475 |
* determine which existing heap TID will need to be replaced by a posting |
| 476 |
* list split). |
| 477 |
*/ |
| 478 |
OffsetNumber |
| 479 |
_bt_binsrch_insert(Relation rel, BTInsertState insertstate) |
| 480 |
{ |
| 481 |
BTScanInsert key = insertstate->itup_key; |
| 482 |
Page page; |
| 483 |
BTPageOpaque opaque; |
| 484 |
OffsetNumber low, |
| 485 |
high, |
| 486 |
stricthigh; |
| 487 |
int32 result, |
| 488 |
cmpval; |
| 489 |
|
| 490 |
page = BufferGetPage(insertstate->buf); |
| 491 |
opaque = BTPageGetOpaque(page); |
| 492 |
|
| 493 |
Assert(P_ISLEAF(opaque)); |
| 494 |
Assert(!key->nextkey); |
| 495 |
Assert(insertstate->postingoff == 0); |
| 496 |
|
| 497 |
if (!insertstate->bounds_valid) |
| 498 |
{ |
| 499 |
/* Start new binary search */ |
| 500 |
low = P_FIRSTDATAKEY(opaque); |
| 501 |
high = PageGetMaxOffsetNumber(page); |
| 502 |
} |
| 503 |
else |
| 504 |
{ |
| 505 |
/* Restore result of previous binary search against same page */ |
| 506 |
low = insertstate->low; |
| 507 |
high = insertstate->stricthigh; |
| 508 |
} |
| 509 |
|
| 510 |
/* If there are no keys on the page, return the first available slot */ |
| 511 |
if (unlikely(high < low)) |
| 512 |
{ |
| 513 |
/* Caller can't reuse bounds */ |
| 514 |
insertstate->low = InvalidOffsetNumber; |
| 515 |
insertstate->stricthigh = InvalidOffsetNumber; |
| 516 |
insertstate->bounds_valid = false; |
| 517 |
return low; |
| 518 |
} |
| 519 |
|
| 520 |
/* |
| 521 |
* Binary search to find the first key on the page >= scan key. (nextkey |
| 522 |
* is always false when inserting). |
| 523 |
* |
| 524 |
* The loop invariant is: all slots before 'low' are < scan key, all slots |
| 525 |
* at or after 'high' are >= scan key. 'stricthigh' is > scan key, and is |
| 526 |
* maintained to save additional search effort for caller. |
| 527 |
* |
| 528 |
* We can fall out when high == low. |
| 529 |
*/ |
| 530 |
if (!insertstate->bounds_valid) |
| 531 |
high++; /* establish the loop invariant for high */ |
| 532 |
stricthigh = high; /* high initially strictly higher */ |
| 533 |
|
| 534 |
cmpval = 1; /* !nextkey comparison value */ |
| 535 |
|
| 536 |
while (high > low) |
| 537 |
{ |
| 538 |
OffsetNumber mid = low + ((high - low) / 2); |
| 539 |
|
| 540 |
/* We have low <= mid < high, so mid points at a real slot */ |
| 541 |
|
| 542 |
result = _bt_compare(rel, key, page, mid); |
| 543 |
|
| 544 |
if (result >= cmpval) |
| 545 |
low = mid + 1; |
| 546 |
else |
| 547 |
{ |
| 548 |
high = mid; |
| 549 |
if (result != 0) |
| 550 |
stricthigh = high; |
| 551 |
} |
| 552 |
|
| 553 |
/* |
| 554 |
* If tuple at offset located by binary search is a posting list whose |
| 555 |
* TID range overlaps with caller's scantid, perform posting list |
| 556 |
* binary search to set postingoff for caller. Caller must split the |
| 557 |
* posting list when postingoff is set. This should happen |
| 558 |
* infrequently. |
| 559 |
*/ |
| 560 |
if (unlikely(result == 0 && key->scantid != NULL)) |
| 561 |
{ |
| 562 |
/* |
| 563 |
* postingoff should never be set more than once per leaf page |
| 564 |
* binary search. That would mean that there are duplicate table |
| 565 |
* TIDs in the index, which is never okay. Check for that here. |
| 566 |
*/ |
| 567 |
if (insertstate->postingoff != 0) |
| 568 |
ereport(ERROR, |
| 569 |
(errcode(ERRCODE_INDEX_CORRUPTED), |
| 570 |
errmsg_internal("table tid from new index tuple (%u,%u) cannot find insert offset between offsets %u and %u of block %u in index \"%s\"", |
| 571 |
ItemPointerGetBlockNumber(key->scantid), |
| 572 |
ItemPointerGetOffsetNumber(key->scantid), |
| 573 |
low, stricthigh, |
| 574 |
BufferGetBlockNumber(insertstate->buf), |
| 575 |
RelationGetRelationName(rel)))); |
| 576 |
|
| 577 |
insertstate->postingoff = _bt_binsrch_posting(key, page, mid); |
| 578 |
} |
| 579 |
} |
| 580 |
|
| 581 |
/* |
| 582 |
* On a leaf page, a binary search always returns the first key >= scan |
| 583 |
* key (at least in !nextkey case), which could be the last slot + 1. This |
| 584 |
* is also the lower bound of cached search. |
| 585 |
* |
| 586 |
* stricthigh may also be the last slot + 1, which prevents caller from |
| 587 |
* using bounds directly, but is still useful to us if we're called a |
| 588 |
* second time with cached bounds (cached low will be < stricthigh when |
| 589 |
* that happens). |
| 590 |
*/ |
| 591 |
insertstate->low = low; |
| 592 |
insertstate->stricthigh = stricthigh; |
| 593 |
insertstate->bounds_valid = true; |
| 594 |
|
| 595 |
return low; |
| 596 |
} |
| 597 |
|
| 598 |
/*---------- |
| 599 |
* _bt_binsrch_posting() -- posting list binary search. |
| 600 |
* |
| 601 |
* Helper routine for _bt_binsrch_insert(). |
| 602 |
* |
| 603 |
* Returns offset into posting list where caller's scantid belongs. |
| 604 |
*---------- |
| 605 |
*/ |
| 606 |
static int |
| 607 |
_bt_binsrch_posting(BTScanInsert key, Page page, OffsetNumber offnum) |
| 608 |
{ |
| 609 |
IndexTuple itup; |
| 610 |
ItemId itemid; |
| 611 |
int low, |
| 612 |
high, |
| 613 |
mid, |
| 614 |
res; |
| 615 |
|
| 616 |
/* |
| 617 |
* If this isn't a posting tuple, then the index must be corrupt (if it is |
| 618 |
* an ordinary non-pivot tuple then there must be an existing tuple with a |
| 619 |
* heap TID that equals inserter's new heap TID/scantid). Defensively |
| 620 |
* check that tuple is a posting list tuple whose posting list range |
| 621 |
* includes caller's scantid. |
| 622 |
* |
| 623 |
* (This is also needed because contrib/amcheck's rootdescend option needs |
| 624 |
* to be able to relocate a non-pivot tuple using _bt_binsrch_insert().) |
| 625 |
*/ |
| 626 |
itemid = PageGetItemId(page, offnum); |
| 627 |
itup = (IndexTuple) PageGetItem(page, itemid); |
| 628 |
if (!BTreeTupleIsPosting(itup)) |
| 629 |
return 0; |
| 630 |
|
| 631 |
Assert(key->heapkeyspace && key->allequalimage); |
| 632 |
|
| 633 |
/* |
| 634 |
* In the event that posting list tuple has LP_DEAD bit set, indicate this |
| 635 |
* to _bt_binsrch_insert() caller by returning -1, a sentinel value. A |
| 636 |
* second call to _bt_binsrch_insert() can take place when its caller has |
| 637 |
* removed the dead item. |
| 638 |
*/ |
| 639 |
if (ItemIdIsDead(itemid)) |
| 640 |
return -1; |
| 641 |
|
| 642 |
/* "high" is past end of posting list for loop invariant */ |
| 643 |
low = 0; |
| 644 |
high = BTreeTupleGetNPosting(itup); |
| 645 |
Assert(high >= 2); |
| 646 |
|
| 647 |
while (high > low) |
| 648 |
{ |
| 649 |
mid = low + ((high - low) / 2); |
| 650 |
res = ItemPointerCompare(key->scantid, |
| 651 |
BTreeTupleGetPostingN(itup, mid)); |
| 652 |
|
| 653 |
if (res > 0) |
| 654 |
low = mid + 1; |
| 655 |
else if (res < 0) |
| 656 |
high = mid; |
| 657 |
else |
| 658 |
return mid; |
| 659 |
} |
| 660 |
|
| 661 |
/* Exact match not found */ |
| 662 |
return low; |
| 663 |
} |
| 664 |
|
| 665 |
/*---------- |
| 666 |
* _bt_compare() -- Compare insertion-type scankey to tuple on a page. |
| 667 |
* |
| 668 |
* page/offnum: location of btree item to be compared to. |
| 669 |
* |
| 670 |
* This routine returns: |
| 671 |
* <0 if scankey < tuple at offnum; |
| 672 |
* 0 if scankey == tuple at offnum; |
| 673 |
* >0 if scankey > tuple at offnum. |
| 674 |
* |
| 675 |
* NULLs in the keys are treated as sortable values. Therefore |
| 676 |
* "equality" does not necessarily mean that the item should be returned |
| 677 |
* to the caller as a matching key. Similarly, an insertion scankey |
| 678 |
* with its scantid set is treated as equal to a posting tuple whose TID |
| 679 |
* range overlaps with their scantid. There generally won't be a |
| 680 |
* matching TID in the posting tuple, which caller must handle |
| 681 |
* themselves (e.g., by splitting the posting list tuple). |
| 682 |
* |
| 683 |
* CRUCIAL NOTE: on a non-leaf page, the first data key is assumed to be |
| 684 |
* "minus infinity": this routine will always claim it is less than the |
| 685 |
* scankey. The actual key value stored is explicitly truncated to 0 |
| 686 |
* attributes (explicitly minus infinity) with version 3+ indexes, but |
| 687 |
* that isn't relied upon. This allows us to implement the Lehman and |
| 688 |
* Yao convention that the first down-link pointer is before the first |
| 689 |
* key. See backend/access/nbtree/README for details. |
| 690 |
*---------- |
| 691 |
*/ |
| 692 |
int32 |
| 693 |
_bt_compare(Relation rel, |
| 694 |
BTScanInsert key, |
| 695 |
Page page, |
| 696 |
OffsetNumber offnum) |
| 697 |
{ |
| 698 |
TupleDesc itupdesc = RelationGetDescr(rel); |
| 699 |
BTPageOpaque opaque = BTPageGetOpaque(page); |
| 700 |
IndexTuple itup; |
| 701 |
ItemPointer heapTid; |
| 702 |
ScanKey scankey; |
| 703 |
int ncmpkey; |
| 704 |
int ntupatts; |
| 705 |
int32 result; |
| 706 |
|
| 707 |
Assert(_bt_check_natts(rel, key->heapkeyspace, page, offnum)); |
| 708 |
Assert(key->keysz <= IndexRelationGetNumberOfKeyAttributes(rel)); |
| 709 |
Assert(key->heapkeyspace || key->scantid == NULL); |
| 710 |
|
| 711 |
/* |
| 712 |
* Force result ">" if target item is first data item on an internal page |
| 713 |
* --- see NOTE above. |
| 714 |
*/ |
| 715 |
if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque)) |
| 716 |
return 1; |
| 717 |
|
| 718 |
itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); |
| 719 |
ntupatts = BTreeTupleGetNAtts(itup, rel); |
| 720 |
|
| 721 |
/* |
| 722 |
* The scan key is set up with the attribute number associated with each |
| 723 |
* term in the key. It is important that, if the index is multi-key, the |
| 724 |
* scan contain the first k key attributes, and that they be in order. If |
| 725 |
* you think about how multi-key ordering works, you'll understand why |
| 726 |
* this is. |
| 727 |
* |
| 728 |
* We don't test for violation of this condition here, however. The |
| 729 |
* initial setup for the index scan had better have gotten it right (see |
| 730 |
* _bt_first). |
| 731 |
*/ |
| 732 |
|
| 733 |
ncmpkey = Min(ntupatts, key->keysz); |
| 734 |
Assert(key->heapkeyspace || ncmpkey == key->keysz); |
| 735 |
Assert(!BTreeTupleIsPosting(itup) || key->allequalimage); |
| 736 |
scankey = key->scankeys; |
| 737 |
for (int i = 1; i <= ncmpkey; i++) |
| 738 |
{ |
| 739 |
Datum datum; |
| 740 |
bool isNull; |
| 741 |
|
| 742 |
datum = index_getattr(itup, scankey->sk_attno, itupdesc, &isNull); |
| 743 |
|
| 744 |
if (scankey->sk_flags & SK_ISNULL) /* key is NULL */ |
| 745 |
{ |
| 746 |
if (isNull) |
| 747 |
result = 0; /* NULL "=" NULL */ |
| 748 |
else if (scankey->sk_flags & SK_BT_NULLS_FIRST) |
| 749 |
result = -1; /* NULL "<" NOT_NULL */ |
| 750 |
else |
| 751 |
result = 1; /* NULL ">" NOT_NULL */ |
| 752 |
} |
| 753 |
else if (isNull) /* key is NOT_NULL and item is NULL */ |
| 754 |
{ |
| 755 |
if (scankey->sk_flags & SK_BT_NULLS_FIRST) |
| 756 |
result = 1; /* NOT_NULL ">" NULL */ |
| 757 |
else |
| 758 |
result = -1; /* NOT_NULL "<" NULL */ |
| 759 |
} |
| 760 |
else |
| 761 |
{ |
| 762 |
/* |
| 763 |
* The sk_func needs to be passed the index value as left arg and |
| 764 |
* the sk_argument as right arg (they might be of different |
| 765 |
* types). Since it is convenient for callers to think of |
| 766 |
* _bt_compare as comparing the scankey to the index item, we have |
| 767 |
* to flip the sign of the comparison result. (Unless it's a DESC |
| 768 |
* column, in which case we *don't* flip the sign.) |
| 769 |
*/ |
| 770 |
result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func, |
| 771 |
scankey->sk_collation, |
| 772 |
datum, |
| 773 |
scankey->sk_argument)); |
| 774 |
|
| 775 |
if (!(scankey->sk_flags & SK_BT_DESC)) |
| 776 |
INVERT_COMPARE_RESULT(result); |
| 777 |
} |
| 778 |
|
| 779 |
/* if the keys are unequal, return the difference */ |
| 780 |
if (result != 0) |
| 781 |
return result; |
| 782 |
|
| 783 |
scankey++; |
| 784 |
} |
| 785 |
|
| 786 |
/* |
| 787 |
* All non-truncated attributes (other than heap TID) were found to be |
| 788 |
* equal. Treat truncated attributes as minus infinity when scankey has a |
| 789 |
* key attribute value that would otherwise be compared directly. |
| 790 |
* |
| 791 |
* Note: it doesn't matter if ntupatts includes non-key attributes; |
| 792 |
* scankey won't, so explicitly excluding non-key attributes isn't |
| 793 |
* necessary. |
| 794 |
*/ |
| 795 |
if (key->keysz > ntupatts) |
| 796 |
return 1; |
| 797 |
|
| 798 |
/* |
| 799 |
* Use the heap TID attribute and scantid to try to break the tie. The |
| 800 |
* rules are the same as any other key attribute -- only the |
| 801 |
* representation differs. |
| 802 |
*/ |
| 803 |
heapTid = BTreeTupleGetHeapTID(itup); |
| 804 |
if (key->scantid == NULL) |
| 805 |
{ |
| 806 |
/* |
| 807 |
* Forward scans have a scankey that is considered greater than a |
| 808 |
* truncated pivot tuple if and when the scankey has equal values for |
| 809 |
* attributes up to and including the least significant untruncated |
| 810 |
* attribute in tuple. Even attributes that were omitted from the |
| 811 |
* scan key are considered greater than -inf truncated attributes. |
| 812 |
* (See _bt_binsrch for an explanation of our backward scan behavior.) |
| 813 |
* |
| 814 |
* For example, if an index has the minimum two attributes (single |
| 815 |
* user key attribute, plus heap TID attribute), and a page's high key |
| 816 |
* is ('foo', -inf), and scankey is ('foo', <omitted>), the search |
| 817 |
* will not descend to the page to the left. The search will descend |
| 818 |
* right instead. The truncated attribute in pivot tuple means that |
| 819 |
* all non-pivot tuples on the page to the left are strictly < 'foo', |
| 820 |
* so it isn't necessary to descend left. In other words, search |
| 821 |
* doesn't have to descend left because it isn't interested in a match |
| 822 |
* that has a heap TID value of -inf. |
| 823 |
* |
| 824 |
* Note: the heap TID part of the test ensures that scankey is being |
| 825 |
* compared to a pivot tuple with one or more truncated -inf key |
| 826 |
* attributes. The heap TID attribute is the last key attribute in |
| 827 |
* every index, of course, but other than that it isn't special. |
| 828 |
*/ |
| 829 |
if (!key->backward && key->keysz == ntupatts && heapTid == NULL && |
| 830 |
key->heapkeyspace) |
| 831 |
return 1; |
| 832 |
|
| 833 |
/* All provided scankey arguments found to be equal */ |
| 834 |
return 0; |
| 835 |
} |
| 836 |
|
| 837 |
/* |
| 838 |
* Treat truncated heap TID as minus infinity, since scankey has a key |
| 839 |
* attribute value (scantid) that would otherwise be compared directly |
| 840 |
*/ |
| 841 |
Assert(key->keysz == IndexRelationGetNumberOfKeyAttributes(rel)); |
| 842 |
if (heapTid == NULL) |
| 843 |
return 1; |
| 844 |
|
| 845 |
/* |
| 846 |
* Scankey must be treated as equal to a posting list tuple if its scantid |
| 847 |
* value falls within the range of the posting list. In all other cases |
| 848 |
* there can only be a single heap TID value, which is compared directly |
| 849 |
* with scantid. |
| 850 |
*/ |
| 851 |
Assert(ntupatts >= IndexRelationGetNumberOfKeyAttributes(rel)); |
| 852 |
result = ItemPointerCompare(key->scantid, heapTid); |
| 853 |
if (result <= 0 || !BTreeTupleIsPosting(itup)) |
| 854 |
return result; |
| 855 |
else |
| 856 |
{ |
| 857 |
result = ItemPointerCompare(key->scantid, |
| 858 |
BTreeTupleGetMaxHeapTID(itup)); |
| 859 |
if (result > 0) |
| 860 |
return 1; |
| 861 |
} |
| 862 |
|
| 863 |
return 0; |
| 864 |
} |
| 865 |
|
| 866 |
/* |
| 867 |
* _bt_first() -- Find the first item in a scan. |
| 868 |
* |
| 869 |
* We need to be clever about the direction of scan, the search |
| 870 |
* conditions, and the tree ordering. We find the first item (or, |
| 871 |
* if backwards scan, the last item) in the tree that satisfies the |
| 872 |
* qualifications in the scan key. On success exit, data about the |
| 873 |
* matching tuple(s) on the page has been loaded into so->currPos. We'll |
| 874 |
* drop all locks and hold onto a pin on page's buffer, except during |
| 875 |
* so->dropPin scans, when we drop both the lock and the pin. |
| 876 |
* _bt_returnitem sets the next item to return to scan on success exit. |
| 877 |
* |
| 878 |
* If there are no matching items in the index, we return false, with no |
| 879 |
* pins or locks held. so->currPos will remain invalid. |
| 880 |
* |
| 881 |
* Note that scan->keyData[], and the so->keyData[] scankey built from it, |
| 882 |
* are both search-type scankeys (see nbtree/README for more about this). |
| 883 |
* Within this routine, we build a temporary insertion-type scankey to use |
| 884 |
* in locating the scan start position. |
| 885 |
*/ |
| 886 |
bool |
| 887 |
_bt_first(IndexScanDesc scan, ScanDirection dir) |
| 888 |
{ |
| 889 |
Relation rel = scan->indexRelation; |
| 890 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 891 |
BTStack stack; |
| 892 |
OffsetNumber offnum; |
| 893 |
BTScanInsertData inskey; |
| 894 |
ScanKey startKeys[INDEX_MAX_KEYS]; |
| 895 |
ScanKeyData notnullkeys[INDEX_MAX_KEYS]; |
| 896 |
int keysz = 0; |
| 897 |
StrategyNumber strat_total; |
| 898 |
BlockNumber blkno = InvalidBlockNumber, |
| 899 |
lastcurrblkno; |
| 900 |
|
| 901 |
Assert(!BTScanPosIsValid(so->currPos)); |
| 902 |
|
| 903 |
/* |
| 904 |
* Examine the scan keys and eliminate any redundant keys; also mark the |
| 905 |
* keys that must be matched to continue the scan. |
| 906 |
*/ |
| 907 |
_bt_preprocess_keys(scan); |
| 908 |
|
| 909 |
/* |
| 910 |
* Quit now if _bt_preprocess_keys() discovered that the scan keys can |
| 911 |
* never be satisfied (eg, x == 1 AND x > 2). |
| 912 |
*/ |
| 913 |
if (!so->qual_ok) |
| 914 |
{ |
| 915 |
Assert(!so->needPrimScan); |
| 916 |
_bt_parallel_done(scan); |
| 917 |
return false; |
| 918 |
} |
| 919 |
|
| 920 |
/* |
| 921 |
* If this is a parallel scan, we must seize the scan. _bt_readfirstpage |
| 922 |
* will likely release the parallel scan later on. |
| 923 |
*/ |
| 924 |
if (scan->parallel_scan != NULL && |
| 925 |
!_bt_parallel_seize(scan, &blkno, &lastcurrblkno, true)) |
| 926 |
return false; |
| 927 |
|
| 928 |
/* |
| 929 |
* Initialize the scan's arrays (if any) for the current scan direction |
| 930 |
* (except when they were already set to later values as part of |
| 931 |
* scheduling the primitive index scan that is now underway) |
| 932 |
*/ |
| 933 |
if (so->numArrayKeys && !so->needPrimScan) |
| 934 |
_bt_start_array_keys(scan, dir); |
| 935 |
|
| 936 |
if (blkno != InvalidBlockNumber) |
| 937 |
{ |
| 938 |
/* |
| 939 |
* We anticipated calling _bt_search, but another worker bet us to it. |
| 940 |
* _bt_readnextpage releases the scan for us (not _bt_readfirstpage). |
| 941 |
*/ |
| 942 |
Assert(scan->parallel_scan != NULL); |
| 943 |
Assert(!so->needPrimScan); |
| 944 |
Assert(blkno != P_NONE); |
| 945 |
|
| 946 |
if (!_bt_readnextpage(scan, blkno, lastcurrblkno, dir, true)) |
| 947 |
return false; |
| 948 |
|
| 949 |
_bt_returnitem(scan, so); |
| 950 |
return true; |
| 951 |
} |
| 952 |
|
| 953 |
/* |
| 954 |
* Count an indexscan for stats, now that we know that we'll call |
| 955 |
* _bt_search/_bt_endpoint below |
| 956 |
*/ |
| 957 |
pgstat_count_index_scan(rel); |
| 958 |
if (scan->instrument) |
| 959 |
scan->instrument->nsearches++; |
| 960 |
|
| 961 |
/*---------- |
| 962 |
* Examine the scan keys to discover where we need to start the scan. |
| 963 |
* The selected scan keys (at most one per index column) are remembered by |
| 964 |
* storing their addresses into the local startKeys[] array. The final |
| 965 |
* startKeys[] entry's strategy is set in strat_total. (Actually, there |
| 966 |
* are a couple of cases where we force a less/more restrictive strategy.) |
| 967 |
* |
| 968 |
* We must use the key that was marked required (in the direction opposite |
| 969 |
* our own scan's) during preprocessing. Each index attribute can only |
| 970 |
* have one such required key. In general, the keys that we use to find |
| 971 |
* an initial position when scanning forwards are the same keys that end |
| 972 |
* the scan on the leaf level when scanning backwards (and vice-versa). |
| 973 |
* |
| 974 |
* When the scan keys include cross-type operators, _bt_preprocess_keys |
| 975 |
* may not be able to eliminate redundant keys; in such cases it will |
| 976 |
* arbitrarily pick a usable key for each attribute (and scan direction), |
| 977 |
* ensuring that there is no more than one key required in each direction. |
| 978 |
* We stop considering further keys once we reach the first nonrequired |
| 979 |
* key (which must come after all required keys), so this can't affect us. |
| 980 |
* |
| 981 |
* The required keys that we use as starting boundaries have to be =, >, |
| 982 |
* or >= keys for a forward scan or =, <, <= keys for a backwards scan. |
| 983 |
* We can use keys for multiple attributes so long as the prior attributes |
| 984 |
* had only =, >= (resp. =, <=) keys. These rules are very similar to the |
| 985 |
* rules that preprocessing used to determine which keys to mark required. |
| 986 |
* We cannot always use every required key as a positioning key, though. |
| 987 |
* Skip arrays necessitate independently applying our own rules here. |
| 988 |
* Skip arrays are always generally considered = array keys, but we'll |
| 989 |
* nevertheless treat them as inequalities at certain points of the scan. |
| 990 |
* When that happens, it _might_ have implications for the number of |
| 991 |
* required keys that we can safely use for initial positioning purposes. |
| 992 |
* |
| 993 |
* For example, a forward scan with a skip array on its leading attribute |
| 994 |
* (with no low_compare/high_compare) will have at least two required scan |
| 995 |
* keys, but we won't use any of them as boundary keys during the scan's |
| 996 |
* initial call here. Our positioning key during the first call here can |
| 997 |
* be thought of as representing "> -infinity". Similarly, if such a skip |
| 998 |
* array's low_compare is "a > 'foo'", then we position using "a > 'foo'" |
| 999 |
* during the scan's initial call here; a lower-order key such as "b = 42" |
| 1000 |
* can't be used until the "a" array advances beyond MINVAL/low_compare. |
| 1001 |
* |
| 1002 |
* On the other hand, if such a skip array's low_compare was "a >= 'foo'", |
| 1003 |
* then we _can_ use "a >= 'foo' AND b = 42" during the initial call here. |
| 1004 |
* A subsequent call here might have us use "a = 'fop' AND b = 42". Note |
| 1005 |
* that we treat = and >= as equivalent when scanning forwards (just as we |
| 1006 |
* treat = and <= as equivalent when scanning backwards). We effectively |
| 1007 |
* do the same thing (though with a distinct "a" element/value) each time. |
| 1008 |
* |
| 1009 |
* All keys (with the exception of SK_SEARCHNULL keys and SK_BT_SKIP |
| 1010 |
* array keys whose array is "null_elem=true") imply a NOT NULL qualifier. |
| 1011 |
* If the index stores nulls at the end of the index we'll be starting |
| 1012 |
* from, and we have no boundary key for the column (which means the key |
| 1013 |
* we deduced NOT NULL from is an inequality key that constrains the other |
| 1014 |
* end of the index), then we cons up an explicit SK_SEARCHNOTNULL key to |
| 1015 |
* use as a boundary key. If we didn't do this, we might find ourselves |
| 1016 |
* traversing a lot of null entries at the start of the scan. |
| 1017 |
* |
| 1018 |
* In this loop, row-comparison keys are treated the same as keys on their |
| 1019 |
* first (leftmost) columns. We'll add all lower-order columns of the row |
| 1020 |
* comparison that were marked required during preprocessing below. |
| 1021 |
* |
| 1022 |
* _bt_advance_array_keys needs to know exactly how we'll reposition the |
| 1023 |
* scan (should it opt to schedule another primitive index scan). It is |
| 1024 |
* critical that primscans only be scheduled when they'll definitely make |
| 1025 |
* some useful progress. _bt_advance_array_keys does this by calling |
| 1026 |
* _bt_checkkeys routines that report whether a tuple is past the end of |
| 1027 |
* matches for the scan's keys (given the scan's current array elements). |
| 1028 |
* If the page's final tuple is "after the end of matches" for a scan that |
| 1029 |
* uses the *opposite* scan direction, then it must follow that it's also |
| 1030 |
* "before the start of matches" for the actual current scan direction. |
| 1031 |
* It is therefore essential that all of our initial positioning rules are |
| 1032 |
* symmetric with _bt_checkkeys's corresponding continuescan=false rule. |
| 1033 |
* If you update anything here, _bt_checkkeys/_bt_advance_array_keys might |
| 1034 |
* need to be kept in sync. |
| 1035 |
*---------- |
| 1036 |
*/ |
| 1037 |
strat_total = BTEqualStrategyNumber; |
| 1038 |
if (so->numberOfKeys > 0) |
| 1039 |
{ |
| 1040 |
AttrNumber curattr; |
| 1041 |
ScanKey bkey; |
| 1042 |
ScanKey impliesNN; |
| 1043 |
ScanKey cur; |
| 1044 |
|
| 1045 |
/* |
| 1046 |
* bkey will be set to the key that preprocessing left behind as the |
| 1047 |
* boundary key for this attribute, in this scan direction (if any) |
| 1048 |
*/ |
| 1049 |
cur = so->keyData; |
| 1050 |
curattr = 1; |
| 1051 |
bkey = NULL; |
| 1052 |
/* Also remember any scankey that implies a NOT NULL constraint */ |
| 1053 |
impliesNN = NULL; |
| 1054 |
|
| 1055 |
/* |
| 1056 |
* Loop iterates from 0 to numberOfKeys inclusive; we use the last |
| 1057 |
* pass to handle after-last-key processing. Actual exit from the |
| 1058 |
* loop is at one of the "break" statements below. |
| 1059 |
*/ |
| 1060 |
for (int i = 0;; cur++, i++) |
| 1061 |
{ |
| 1062 |
if (i >= so->numberOfKeys || cur->sk_attno != curattr) |
| 1063 |
{ |
| 1064 |
/* Done looking for the curattr boundary key */ |
| 1065 |
Assert(bkey == NULL || |
| 1066 |
(bkey->sk_attno == curattr && |
| 1067 |
(bkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)))); |
| 1068 |
Assert(impliesNN == NULL || |
| 1069 |
(impliesNN->sk_attno == curattr && |
| 1070 |
(impliesNN->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)))); |
| 1071 |
|
| 1072 |
/* |
| 1073 |
* If this is a scan key for a skip array whose current |
| 1074 |
* element is MINVAL, choose low_compare (when scanning |
| 1075 |
* backwards it'll be MAXVAL, and we'll choose high_compare). |
| 1076 |
* |
| 1077 |
* Note: if the array's low_compare key makes 'bkey' NULL, |
| 1078 |
* then we behave as if the array's first element is -inf, |
| 1079 |
* except when !array->null_elem implies a usable NOT NULL |
| 1080 |
* constraint. |
| 1081 |
*/ |
| 1082 |
if (bkey != NULL && |
| 1083 |
(bkey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))) |
| 1084 |
{ |
| 1085 |
int ikey = bkey - so->keyData; |
| 1086 |
ScanKey skipequalitykey = bkey; |
| 1087 |
BTArrayKeyInfo *array = NULL; |
| 1088 |
|
| 1089 |
for (int arridx = 0; arridx < so->numArrayKeys; arridx++) |
| 1090 |
{ |
| 1091 |
array = &so->arrayKeys[arridx]; |
| 1092 |
if (array->scan_key == ikey) |
| 1093 |
break; |
| 1094 |
} |
| 1095 |
|
| 1096 |
if (ScanDirectionIsForward(dir)) |
| 1097 |
{ |
| 1098 |
Assert(!(skipequalitykey->sk_flags & SK_BT_MAXVAL)); |
| 1099 |
bkey = array->low_compare; |
| 1100 |
} |
| 1101 |
else |
| 1102 |
{ |
| 1103 |
Assert(!(skipequalitykey->sk_flags & SK_BT_MINVAL)); |
| 1104 |
bkey = array->high_compare; |
| 1105 |
} |
| 1106 |
|
| 1107 |
Assert(bkey == NULL || |
| 1108 |
bkey->sk_attno == skipequalitykey->sk_attno); |
| 1109 |
|
| 1110 |
if (!array->null_elem) |
| 1111 |
impliesNN = skipequalitykey; |
| 1112 |
else |
| 1113 |
Assert(bkey == NULL && impliesNN == NULL); |
| 1114 |
} |
| 1115 |
|
| 1116 |
/* |
| 1117 |
* If we didn't find a usable boundary key, see if we can |
| 1118 |
* deduce a NOT NULL key |
| 1119 |
*/ |
| 1120 |
if (bkey == NULL && impliesNN != NULL && |
| 1121 |
((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ? |
| 1122 |
ScanDirectionIsForward(dir) : |
| 1123 |
ScanDirectionIsBackward(dir))) |
| 1124 |
{ |
| 1125 |
/* Yes, so build the key in notnullkeys[keysz] */ |
| 1126 |
bkey = ¬nullkeys[keysz]; |
| 1127 |
ScanKeyEntryInitialize(bkey, |
| 1128 |
(SK_SEARCHNOTNULL | SK_ISNULL | |
| 1129 |
(impliesNN->sk_flags & |
| 1130 |
(SK_BT_DESC | SK_BT_NULLS_FIRST))), |
| 1131 |
curattr, |
| 1132 |
((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ? |
| 1133 |
BTGreaterStrategyNumber : |
| 1134 |
BTLessStrategyNumber), |
| 1135 |
InvalidOid, |
| 1136 |
InvalidOid, |
| 1137 |
InvalidOid, |
| 1138 |
(Datum) 0); |
| 1139 |
} |
| 1140 |
|
| 1141 |
/* |
| 1142 |
* If preprocessing didn't leave a usable boundary key, quit; |
| 1143 |
* else save the boundary key pointer in startKeys[] |
| 1144 |
*/ |
| 1145 |
if (bkey == NULL) |
| 1146 |
break; |
| 1147 |
startKeys[keysz++] = bkey; |
| 1148 |
|
| 1149 |
/* |
| 1150 |
* We can only consider adding more boundary keys when the one |
| 1151 |
* that we just chose to add uses either the = or >= strategy |
| 1152 |
* (during backwards scans we can only do so when the key that |
| 1153 |
* we just added to startKeys[] uses the = or <= strategy) |
| 1154 |
*/ |
| 1155 |
strat_total = bkey->sk_strategy; |
| 1156 |
if (strat_total == BTGreaterStrategyNumber || |
| 1157 |
strat_total == BTLessStrategyNumber) |
| 1158 |
break; |
| 1159 |
|
| 1160 |
/* |
| 1161 |
* If the key that we just added to startKeys[] is a skip |
| 1162 |
* array = key whose current element is marked NEXT or PRIOR, |
| 1163 |
* make strat_total > or < (and stop adding boundary keys). |
| 1164 |
* This can only happen with opclasses that lack skip support. |
| 1165 |
*/ |
| 1166 |
if (bkey->sk_flags & (SK_BT_NEXT | SK_BT_PRIOR)) |
| 1167 |
{ |
| 1168 |
Assert(bkey->sk_flags & SK_BT_SKIP); |
| 1169 |
Assert(strat_total == BTEqualStrategyNumber); |
| 1170 |
|
| 1171 |
if (ScanDirectionIsForward(dir)) |
| 1172 |
{ |
| 1173 |
Assert(!(bkey->sk_flags & SK_BT_PRIOR)); |
| 1174 |
strat_total = BTGreaterStrategyNumber; |
| 1175 |
} |
| 1176 |
else |
| 1177 |
{ |
| 1178 |
Assert(!(bkey->sk_flags & SK_BT_NEXT)); |
| 1179 |
strat_total = BTLessStrategyNumber; |
| 1180 |
} |
| 1181 |
|
| 1182 |
/* |
| 1183 |
* We're done. We'll never find an exact = match for a |
| 1184 |
* NEXT or PRIOR sentinel sk_argument value. There's no |
| 1185 |
* sense in trying to add more keys to startKeys[]. |
| 1186 |
*/ |
| 1187 |
break; |
| 1188 |
} |
| 1189 |
|
| 1190 |
/* |
| 1191 |
* Done if that was the last scan key output by preprocessing. |
| 1192 |
* Also done if we've now examined all keys marked required. |
| 1193 |
*/ |
| 1194 |
if (i >= so->numberOfKeys || |
| 1195 |
!(cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))) |
| 1196 |
break; |
| 1197 |
|
| 1198 |
/* |
| 1199 |
* Reset for next attr. |
| 1200 |
*/ |
| 1201 |
Assert(cur->sk_attno == curattr + 1); |
| 1202 |
curattr = cur->sk_attno; |
| 1203 |
bkey = NULL; |
| 1204 |
impliesNN = NULL; |
| 1205 |
} |
| 1206 |
|
| 1207 |
/* |
| 1208 |
* If we've located the starting boundary key for curattr, we have |
| 1209 |
* no interest in curattr's other required key |
| 1210 |
*/ |
| 1211 |
if (bkey != NULL) |
| 1212 |
continue; |
| 1213 |
|
| 1214 |
/* |
| 1215 |
* Is this key the starting boundary key for curattr? |
| 1216 |
* |
| 1217 |
* If not, does it imply a NOT NULL constraint? (Because |
| 1218 |
* SK_SEARCHNULL keys are always assigned BTEqualStrategyNumber, |
| 1219 |
* *any* inequality key works for that; we need not test.) |
| 1220 |
*/ |
| 1221 |
switch (cur->sk_strategy) |
| 1222 |
{ |
| 1223 |
case BTLessStrategyNumber: |
| 1224 |
case BTLessEqualStrategyNumber: |
| 1225 |
if (ScanDirectionIsBackward(dir)) |
| 1226 |
bkey = cur; |
| 1227 |
else if (impliesNN == NULL) |
| 1228 |
impliesNN = cur; |
| 1229 |
break; |
| 1230 |
case BTEqualStrategyNumber: |
| 1231 |
bkey = cur; |
| 1232 |
break; |
| 1233 |
case BTGreaterEqualStrategyNumber: |
| 1234 |
case BTGreaterStrategyNumber: |
| 1235 |
if (ScanDirectionIsForward(dir)) |
| 1236 |
bkey = cur; |
| 1237 |
else if (impliesNN == NULL) |
| 1238 |
impliesNN = cur; |
| 1239 |
break; |
| 1240 |
} |
| 1241 |
} |
| 1242 |
} |
| 1243 |
|
| 1244 |
/* |
| 1245 |
* If we found no usable boundary keys, we have to start from one end of |
| 1246 |
* the tree. Walk down that edge to the first or last key, and scan from |
| 1247 |
* there. |
| 1248 |
* |
| 1249 |
* Note: calls _bt_readfirstpage for us, which releases the parallel scan. |
| 1250 |
*/ |
| 1251 |
if (keysz == 0) |
| 1252 |
return _bt_endpoint(scan, dir); |
| 1253 |
|
| 1254 |
/* |
| 1255 |
* We want to start the scan somewhere within the index. Set up an |
| 1256 |
* insertion scankey we can use to search for the boundary point we |
| 1257 |
* identified above. The insertion scankey is built using the keys |
| 1258 |
* identified by startKeys[]. (Remaining insertion scankey fields are |
| 1259 |
* initialized after initial-positioning scan keys are finalized.) |
| 1260 |
*/ |
| 1261 |
Assert(keysz <= INDEX_MAX_KEYS); |
| 1262 |
for (int i = 0; i < keysz; i++) |
| 1263 |
{ |
| 1264 |
ScanKey bkey = startKeys[i]; |
| 1265 |
|
| 1266 |
Assert(bkey->sk_attno == i + 1); |
| 1267 |
|
| 1268 |
if (bkey->sk_flags & SK_ROW_HEADER) |
| 1269 |
{ |
| 1270 |
/* |
| 1271 |
* Row comparison header: look to the first row member instead |
| 1272 |
*/ |
| 1273 |
ScanKey subkey = (ScanKey) DatumGetPointer(bkey->sk_argument); |
| 1274 |
bool loosen_strat = false, |
| 1275 |
tighten_strat = false; |
| 1276 |
|
| 1277 |
/* |
| 1278 |
* Cannot be a NULL in the first row member: _bt_preprocess_keys |
| 1279 |
* would've marked the qual as unsatisfiable, preventing us from |
| 1280 |
* ever getting this far |
| 1281 |
*/ |
| 1282 |
Assert(subkey->sk_flags & SK_ROW_MEMBER); |
| 1283 |
Assert(subkey->sk_attno == bkey->sk_attno); |
| 1284 |
Assert(!(subkey->sk_flags & SK_ISNULL)); |
| 1285 |
|
| 1286 |
/* |
| 1287 |
* This is either a > or >= key (during backwards scans it is |
| 1288 |
* either < or <=) that was marked required during preprocessing. |
| 1289 |
* Later so->keyData[] keys can't have been marked required, so |
| 1290 |
* our row compare header key must be the final startKeys[] entry. |
| 1291 |
*/ |
| 1292 |
Assert(subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)); |
| 1293 |
Assert(subkey->sk_strategy == bkey->sk_strategy); |
| 1294 |
Assert(subkey->sk_strategy == strat_total); |
| 1295 |
Assert(i == keysz - 1); |
| 1296 |
|
| 1297 |
/* |
| 1298 |
* The member scankeys are already in insertion format (ie, they |
| 1299 |
* have sk_func = 3-way-comparison function) |
| 1300 |
*/ |
| 1301 |
memcpy(inskey.scankeys + i, subkey, sizeof(ScanKeyData)); |
| 1302 |
|
| 1303 |
/* |
| 1304 |
* Now look to later row compare members. |
| 1305 |
* |
| 1306 |
* If there's an "index attribute gap" between two row compare |
| 1307 |
* members, the second member won't have been marked required, and |
| 1308 |
* so can't be used as a starting boundary key here. The part of |
| 1309 |
* the row comparison that we do still use has to be treated as a |
| 1310 |
* ">=" or "<=" condition. For example, a qual "(a, c) > (1, 42)" |
| 1311 |
* with an omitted intervening index attribute "b" will use an |
| 1312 |
* insertion scan key "a >= 1". Even the first "a = 1" tuple on |
| 1313 |
* the leaf level might satisfy the row compare qual. |
| 1314 |
* |
| 1315 |
* We're able to use a _more_ restrictive strategy when we reach a |
| 1316 |
* NULL row compare member, since they're always unsatisfiable. |
| 1317 |
* For example, a qual "(a, b, c) >= (1, NULL, 77)" will use an |
| 1318 |
* insertion scan key "a > 1". All tuples where "a = 1" cannot |
| 1319 |
* possibly satisfy the row compare qual, so this is safe. |
| 1320 |
*/ |
| 1321 |
Assert(!(subkey->sk_flags & SK_ROW_END)); |
| 1322 |
for (;;) |
| 1323 |
{ |
| 1324 |
subkey++; |
| 1325 |
Assert(subkey->sk_flags & SK_ROW_MEMBER); |
| 1326 |
|
| 1327 |
if (subkey->sk_flags & SK_ISNULL) |
| 1328 |
{ |
| 1329 |
/* |
| 1330 |
* NULL member key, can only use earlier keys. |
| 1331 |
* |
| 1332 |
* We deliberately avoid checking if this key is marked |
| 1333 |
* required. All earlier keys are required, and this key |
| 1334 |
* is unsatisfiable either way, so we can't miss anything. |
| 1335 |
*/ |
| 1336 |
tighten_strat = true; |
| 1337 |
break; |
| 1338 |
} |
| 1339 |
|
| 1340 |
if (!(subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))) |
| 1341 |
{ |
| 1342 |
/* nonrequired member key, can only use earlier keys */ |
| 1343 |
loosen_strat = true; |
| 1344 |
break; |
| 1345 |
} |
| 1346 |
|
| 1347 |
Assert(subkey->sk_attno == keysz + 1); |
| 1348 |
Assert(subkey->sk_strategy == bkey->sk_strategy); |
| 1349 |
Assert(keysz < INDEX_MAX_KEYS); |
| 1350 |
|
| 1351 |
memcpy(inskey.scankeys + keysz, subkey, sizeof(ScanKeyData)); |
| 1352 |
keysz++; |
| 1353 |
|
| 1354 |
if (subkey->sk_flags & SK_ROW_END) |
| 1355 |
break; |
| 1356 |
} |
| 1357 |
Assert(!(loosen_strat && tighten_strat)); |
| 1358 |
if (loosen_strat) |
| 1359 |
{ |
| 1360 |
/* Use less restrictive strategy (and fewer member keys) */ |
| 1361 |
switch (strat_total) |
| 1362 |
{ |
| 1363 |
case BTLessStrategyNumber: |
| 1364 |
strat_total = BTLessEqualStrategyNumber; |
| 1365 |
break; |
| 1366 |
case BTGreaterStrategyNumber: |
| 1367 |
strat_total = BTGreaterEqualStrategyNumber; |
| 1368 |
break; |
| 1369 |
} |
| 1370 |
} |
| 1371 |
if (tighten_strat) |
| 1372 |
{ |
| 1373 |
/* Use more restrictive strategy (and fewer member keys) */ |
| 1374 |
switch (strat_total) |
| 1375 |
{ |
| 1376 |
case BTLessEqualStrategyNumber: |
| 1377 |
strat_total = BTLessStrategyNumber; |
| 1378 |
break; |
| 1379 |
case BTGreaterEqualStrategyNumber: |
| 1380 |
strat_total = BTGreaterStrategyNumber; |
| 1381 |
break; |
| 1382 |
} |
| 1383 |
} |
| 1384 |
|
| 1385 |
/* Done (row compare header key is always last startKeys[] key) */ |
| 1386 |
break; |
| 1387 |
} |
| 1388 |
|
| 1389 |
/* |
| 1390 |
* Ordinary comparison key/search-style key. |
| 1391 |
* |
| 1392 |
* Transform the search-style scan key to an insertion scan key by |
| 1393 |
* replacing the sk_func with the appropriate btree 3-way-comparison |
| 1394 |
* function. |
| 1395 |
* |
| 1396 |
* If scankey operator is not a cross-type comparison, we can use the |
| 1397 |
* cached comparison function; otherwise gotta look it up in the |
| 1398 |
* catalogs. (That can't lead to infinite recursion, since no |
| 1399 |
* indexscan initiated by syscache lookup will use cross-data-type |
| 1400 |
* operators.) |
| 1401 |
* |
| 1402 |
* We support the convention that sk_subtype == InvalidOid means the |
| 1403 |
* opclass input type; this hack simplifies life for ScanKeyInit(). |
| 1404 |
*/ |
| 1405 |
if (bkey->sk_subtype == rel->rd_opcintype[i] || |
| 1406 |
bkey->sk_subtype == InvalidOid) |
| 1407 |
{ |
| 1408 |
FmgrInfo *procinfo; |
| 1409 |
|
| 1410 |
procinfo = index_getprocinfo(rel, bkey->sk_attno, BTORDER_PROC); |
| 1411 |
ScanKeyEntryInitializeWithInfo(inskey.scankeys + i, |
| 1412 |
bkey->sk_flags, |
| 1413 |
bkey->sk_attno, |
| 1414 |
InvalidStrategy, |
| 1415 |
bkey->sk_subtype, |
| 1416 |
bkey->sk_collation, |
| 1417 |
procinfo, |
| 1418 |
bkey->sk_argument); |
| 1419 |
} |
| 1420 |
else |
| 1421 |
{ |
| 1422 |
RegProcedure cmp_proc; |
| 1423 |
|
| 1424 |
cmp_proc = get_opfamily_proc(rel->rd_opfamily[i], |
| 1425 |
rel->rd_opcintype[i], |
| 1426 |
bkey->sk_subtype, BTORDER_PROC); |
| 1427 |
if (!RegProcedureIsValid(cmp_proc)) |
| 1428 |
elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"", |
| 1429 |
BTORDER_PROC, rel->rd_opcintype[i], bkey->sk_subtype, |
| 1430 |
bkey->sk_attno, RelationGetRelationName(rel)); |
| 1431 |
ScanKeyEntryInitialize(inskey.scankeys + i, |
| 1432 |
bkey->sk_flags, |
| 1433 |
bkey->sk_attno, |
| 1434 |
InvalidStrategy, |
| 1435 |
bkey->sk_subtype, |
| 1436 |
bkey->sk_collation, |
| 1437 |
cmp_proc, |
| 1438 |
bkey->sk_argument); |
| 1439 |
} |
| 1440 |
} |
| 1441 |
|
| 1442 |
/*---------- |
| 1443 |
* Examine the selected initial-positioning strategy to determine exactly |
| 1444 |
* where we need to start the scan, and set flag variables to control the |
| 1445 |
* initial descent by _bt_search (and our _bt_binsrch call for the leaf |
| 1446 |
* page _bt_search returns). |
| 1447 |
*---------- |
| 1448 |
*/ |
| 1449 |
_bt_metaversion(rel, &inskey.heapkeyspace, &inskey.allequalimage); |
| 1450 |
inskey.anynullkeys = false; /* unused */ |
| 1451 |
inskey.scantid = NULL; |
| 1452 |
inskey.keysz = keysz; |
| 1453 |
switch (strat_total) |
| 1454 |
{ |
| 1455 |
case BTLessStrategyNumber: |
| 1456 |
|
| 1457 |
inskey.nextkey = false; |
| 1458 |
inskey.backward = true; |
| 1459 |
break; |
| 1460 |
|
| 1461 |
case BTLessEqualStrategyNumber: |
| 1462 |
|
| 1463 |
inskey.nextkey = true; |
| 1464 |
inskey.backward = true; |
| 1465 |
break; |
| 1466 |
|
| 1467 |
case BTEqualStrategyNumber: |
| 1468 |
|
| 1469 |
/* |
| 1470 |
* If a backward scan was specified, need to start with last equal |
| 1471 |
* item not first one. |
| 1472 |
*/ |
| 1473 |
if (ScanDirectionIsBackward(dir)) |
| 1474 |
{ |
| 1475 |
/* |
| 1476 |
* This is the same as the <= strategy |
| 1477 |
*/ |
| 1478 |
inskey.nextkey = true; |
| 1479 |
inskey.backward = true; |
| 1480 |
} |
| 1481 |
else |
| 1482 |
{ |
| 1483 |
/* |
| 1484 |
* This is the same as the >= strategy |
| 1485 |
*/ |
| 1486 |
inskey.nextkey = false; |
| 1487 |
inskey.backward = false; |
| 1488 |
} |
| 1489 |
break; |
| 1490 |
|
| 1491 |
case BTGreaterEqualStrategyNumber: |
| 1492 |
|
| 1493 |
/* |
| 1494 |
* Find first item >= scankey |
| 1495 |
*/ |
| 1496 |
inskey.nextkey = false; |
| 1497 |
inskey.backward = false; |
| 1498 |
break; |
| 1499 |
|
| 1500 |
case BTGreaterStrategyNumber: |
| 1501 |
|
| 1502 |
/* |
| 1503 |
* Find first item > scankey |
| 1504 |
*/ |
| 1505 |
inskey.nextkey = true; |
| 1506 |
inskey.backward = false; |
| 1507 |
break; |
| 1508 |
|
| 1509 |
default: |
| 1510 |
/* can't get here, but keep compiler quiet */ |
| 1511 |
elog(ERROR, "unrecognized strat_total: %d", (int) strat_total); |
| 1512 |
return false; |
| 1513 |
} |
| 1514 |
|
| 1515 |
/* |
| 1516 |
* Use the manufactured insertion scan key to descend the tree and |
| 1517 |
* position ourselves on the target leaf page. |
| 1518 |
*/ |
| 1519 |
Assert(ScanDirectionIsBackward(dir) == inskey.backward); |
| 1520 |
stack = _bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ); |
| 1521 |
|
| 1522 |
/* don't need to keep the stack around... */ |
| 1523 |
_bt_freestack(stack); |
| 1524 |
|
| 1525 |
if (!BufferIsValid(so->currPos.buf)) |
| 1526 |
{ |
| 1527 |
Assert(!so->needPrimScan); |
| 1528 |
|
| 1529 |
/* |
| 1530 |
* We only get here if the index is completely empty. Lock relation |
| 1531 |
* because nothing finer to lock exists. Without a buffer lock, it's |
| 1532 |
* possible for another transaction to insert data between |
| 1533 |
* _bt_search() and PredicateLockRelation(). We have to try again |
| 1534 |
* after taking the relation-level predicate lock, to close a narrow |
| 1535 |
* window where we wouldn't scan concurrently inserted tuples, but the |
| 1536 |
* writer wouldn't see our predicate lock. |
| 1537 |
*/ |
| 1538 |
if (IsolationIsSerializable()) |
| 1539 |
{ |
| 1540 |
PredicateLockRelation(rel, scan->xs_snapshot); |
| 1541 |
stack = _bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ); |
| 1542 |
_bt_freestack(stack); |
| 1543 |
} |
| 1544 |
|
| 1545 |
if (!BufferIsValid(so->currPos.buf)) |
| 1546 |
{ |
| 1547 |
_bt_parallel_done(scan); |
| 1548 |
return false; |
| 1549 |
} |
| 1550 |
} |
| 1551 |
|
| 1552 |
/* position to the precise item on the page */ |
| 1553 |
offnum = _bt_binsrch(rel, &inskey, so->currPos.buf); |
| 1554 |
|
| 1555 |
/* |
| 1556 |
* Now load data from the first page of the scan (usually the page |
| 1557 |
* currently in so->currPos.buf). |
| 1558 |
* |
| 1559 |
* If inskey.nextkey = false and inskey.backward = false, offnum is |
| 1560 |
* positioned at the first non-pivot tuple >= inskey.scankeys. |
| 1561 |
* |
| 1562 |
* If inskey.nextkey = false and inskey.backward = true, offnum is |
| 1563 |
* positioned at the last non-pivot tuple < inskey.scankeys. |
| 1564 |
* |
| 1565 |
* If inskey.nextkey = true and inskey.backward = false, offnum is |
| 1566 |
* positioned at the first non-pivot tuple > inskey.scankeys. |
| 1567 |
* |
| 1568 |
* If inskey.nextkey = true and inskey.backward = true, offnum is |
| 1569 |
* positioned at the last non-pivot tuple <= inskey.scankeys. |
| 1570 |
* |
| 1571 |
* It's possible that _bt_binsrch returned an offnum that is out of bounds |
| 1572 |
* for the page. For example, when inskey is both < the leaf page's high |
| 1573 |
* key and > all of its non-pivot tuples, offnum will be "maxoff + 1". |
| 1574 |
*/ |
| 1575 |
if (!_bt_readfirstpage(scan, offnum, dir)) |
| 1576 |
return false; |
| 1577 |
|
| 1578 |
_bt_returnitem(scan, so); |
| 1579 |
return true; |
| 1580 |
} |
| 1581 |
|
| 1582 |
/* |
| 1583 |
* _bt_next() -- Get the next item in a scan. |
| 1584 |
* |
| 1585 |
* On entry, so->currPos describes the current page, which may be pinned |
| 1586 |
* but is not locked, and so->currPos.itemIndex identifies which item was |
| 1587 |
* previously returned. |
| 1588 |
* |
| 1589 |
* On success exit, so->currPos is updated as needed, and _bt_returnitem |
| 1590 |
* sets the next item to return to the scan. so->currPos remains valid. |
| 1591 |
* |
| 1592 |
* On failure exit (no more tuples), we invalidate so->currPos. It'll |
| 1593 |
* still be possible for the scan to return tuples by changing direction, |
| 1594 |
* though we'll need to call _bt_first anew in that other direction. |
| 1595 |
*/ |
| 1596 |
bool |
| 1597 |
_bt_next(IndexScanDesc scan, ScanDirection dir) |
| 1598 |
{ |
| 1599 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 1600 |
|
| 1601 |
Assert(BTScanPosIsValid(so->currPos)); |
| 1602 |
|
| 1603 |
/* |
| 1604 |
* Advance to next tuple on current page; or if there's no more, try to |
| 1605 |
* step to the next page with data. |
| 1606 |
*/ |
| 1607 |
if (ScanDirectionIsForward(dir)) |
| 1608 |
{ |
| 1609 |
if (++so->currPos.itemIndex > so->currPos.lastItem) |
| 1610 |
{ |
| 1611 |
if (!_bt_steppage(scan, dir)) |
| 1612 |
return false; |
| 1613 |
} |
| 1614 |
} |
| 1615 |
else |
| 1616 |
{ |
| 1617 |
if (--so->currPos.itemIndex < so->currPos.firstItem) |
| 1618 |
{ |
| 1619 |
if (!_bt_steppage(scan, dir)) |
| 1620 |
return false; |
| 1621 |
} |
| 1622 |
} |
| 1623 |
|
| 1624 |
_bt_returnitem(scan, so); |
| 1625 |
return true; |
| 1626 |
} |
| 1627 |
|
| 1628 |
/* |
| 1629 |
* _bt_readpage() -- Load data from current index page into so->currPos |
| 1630 |
* |
| 1631 |
* Caller must have pinned and read-locked so->currPos.buf; the buffer's state |
| 1632 |
* is not changed here. Also, currPos.moreLeft and moreRight must be valid; |
| 1633 |
* they are updated as appropriate. All other fields of so->currPos are |
| 1634 |
* initialized from scratch here. |
| 1635 |
* |
| 1636 |
* We scan the current page starting at offnum and moving in the indicated |
| 1637 |
* direction. All items matching the scan keys are loaded into currPos.items. |
| 1638 |
* moreLeft or moreRight (as appropriate) is cleared if _bt_checkkeys reports |
| 1639 |
* that there can be no more matching tuples in the current scan direction |
| 1640 |
* (could just be for the current primitive index scan when scan has arrays). |
| 1641 |
* |
| 1642 |
* In the case of a parallel scan, caller must have called _bt_parallel_seize |
| 1643 |
* prior to calling this function; this function will invoke |
| 1644 |
* _bt_parallel_release before returning. |
| 1645 |
* |
| 1646 |
* Returns true if any matching items found on the page, false if none. |
| 1647 |
*/ |
| 1648 |
static bool |
| 1649 |
_bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum, |
| 1650 |
bool firstpage) |
| 1651 |
{ |
| 1652 |
Relation rel = scan->indexRelation; |
| 1653 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 1654 |
Page page; |
| 1655 |
BTPageOpaque opaque; |
| 1656 |
OffsetNumber minoff; |
| 1657 |
OffsetNumber maxoff; |
| 1658 |
BTReadPageState pstate; |
| 1659 |
bool arrayKeys; |
| 1660 |
int itemIndex, |
| 1661 |
indnatts; |
| 1662 |
|
| 1663 |
/* save the page/buffer block number, along with its sibling links */ |
| 1664 |
page = BufferGetPage(so->currPos.buf); |
| 1665 |
opaque = BTPageGetOpaque(page); |
| 1666 |
so->currPos.currPage = BufferGetBlockNumber(so->currPos.buf); |
| 1667 |
so->currPos.prevPage = opaque->btpo_prev; |
| 1668 |
so->currPos.nextPage = opaque->btpo_next; |
| 1669 |
/* delay setting so->currPos.lsn until _bt_drop_lock_and_maybe_pin */ |
| 1670 |
so->currPos.dir = dir; |
| 1671 |
so->currPos.nextTupleOffset = 0; |
| 1672 |
|
| 1673 |
/* either moreRight or moreLeft should be set now (may be unset later) */ |
| 1674 |
Assert(ScanDirectionIsForward(dir) ? so->currPos.moreRight : |
| 1675 |
so->currPos.moreLeft); |
| 1676 |
Assert(!P_IGNORE(opaque)); |
| 1677 |
Assert(BTScanPosIsPinned(so->currPos)); |
| 1678 |
Assert(!so->needPrimScan); |
| 1679 |
|
| 1680 |
if (scan->parallel_scan) |
| 1681 |
{ |
| 1682 |
/* allow next/prev page to be read by other worker without delay */ |
| 1683 |
if (ScanDirectionIsForward(dir)) |
| 1684 |
_bt_parallel_release(scan, so->currPos.nextPage, |
| 1685 |
so->currPos.currPage); |
| 1686 |
else |
| 1687 |
_bt_parallel_release(scan, so->currPos.prevPage, |
| 1688 |
so->currPos.currPage); |
| 1689 |
} |
| 1690 |
|
| 1691 |
PredicateLockPage(rel, so->currPos.currPage, scan->xs_snapshot); |
| 1692 |
|
| 1693 |
/* initialize local variables */ |
| 1694 |
indnatts = IndexRelationGetNumberOfAttributes(rel); |
| 1695 |
arrayKeys = so->numArrayKeys != 0; |
| 1696 |
minoff = P_FIRSTDATAKEY(opaque); |
| 1697 |
maxoff = PageGetMaxOffsetNumber(page); |
| 1698 |
|
| 1699 |
/* initialize page-level state that we'll pass to _bt_checkkeys */ |
| 1700 |
pstate.minoff = minoff; |
| 1701 |
pstate.maxoff = maxoff; |
| 1702 |
pstate.finaltup = NULL; |
| 1703 |
pstate.page = page; |
| 1704 |
pstate.firstpage = firstpage; |
| 1705 |
pstate.forcenonrequired = false; |
| 1706 |
pstate.startikey = 0; |
| 1707 |
pstate.offnum = InvalidOffsetNumber; |
| 1708 |
pstate.skip = InvalidOffsetNumber; |
| 1709 |
pstate.continuescan = true; /* default assumption */ |
| 1710 |
pstate.rechecks = 0; |
| 1711 |
pstate.targetdistance = 0; |
| 1712 |
pstate.nskipadvances = 0; |
| 1713 |
|
| 1714 |
if (ScanDirectionIsForward(dir)) |
| 1715 |
{ |
| 1716 |
/* SK_SEARCHARRAY forward scans must provide high key up front */ |
| 1717 |
if (arrayKeys) |
| 1718 |
{ |
| 1719 |
if (!P_RIGHTMOST(opaque)) |
| 1720 |
{ |
| 1721 |
ItemId iid = PageGetItemId(page, P_HIKEY); |
| 1722 |
|
| 1723 |
pstate.finaltup = (IndexTuple) PageGetItem(page, iid); |
| 1724 |
|
| 1725 |
if (so->scanBehind && |
| 1726 |
!_bt_scanbehind_checkkeys(scan, dir, pstate.finaltup)) |
| 1727 |
{ |
| 1728 |
/* Schedule another primitive index scan after all */ |
| 1729 |
so->currPos.moreRight = false; |
| 1730 |
so->needPrimScan = true; |
| 1731 |
if (scan->parallel_scan) |
| 1732 |
_bt_parallel_primscan_schedule(scan, |
| 1733 |
so->currPos.currPage); |
| 1734 |
return false; |
| 1735 |
} |
| 1736 |
} |
| 1737 |
|
| 1738 |
so->scanBehind = so->oppositeDirCheck = false; /* reset */ |
| 1739 |
} |
| 1740 |
|
| 1741 |
/* |
| 1742 |
* Consider pstate.startikey optimization once the ongoing primitive |
| 1743 |
* index scan has already read at least one page |
| 1744 |
*/ |
| 1745 |
if (!pstate.firstpage && minoff < maxoff) |
| 1746 |
_bt_set_startikey(scan, &pstate); |
| 1747 |
|
| 1748 |
/* load items[] in ascending order */ |
| 1749 |
itemIndex = 0; |
| 1750 |
|
| 1751 |
offnum = Max(offnum, minoff); |
| 1752 |
|
| 1753 |
while (offnum <= maxoff) |
| 1754 |
{ |
| 1755 |
ItemId iid = PageGetItemId(page, offnum); |
| 1756 |
IndexTuple itup; |
| 1757 |
bool passes_quals; |
| 1758 |
|
| 1759 |
/* |
| 1760 |
* If the scan specifies not to return killed tuples, then we |
| 1761 |
* treat a killed tuple as not passing the qual |
| 1762 |
*/ |
| 1763 |
if (scan->ignore_killed_tuples && ItemIdIsDead(iid)) |
| 1764 |
{ |
| 1765 |
offnum = OffsetNumberNext(offnum); |
| 1766 |
continue; |
| 1767 |
} |
| 1768 |
|
| 1769 |
itup = (IndexTuple) PageGetItem(page, iid); |
| 1770 |
Assert(!BTreeTupleIsPivot(itup)); |
| 1771 |
|
| 1772 |
pstate.offnum = offnum; |
| 1773 |
passes_quals = _bt_checkkeys(scan, &pstate, arrayKeys, |
| 1774 |
itup, indnatts); |
| 1775 |
|
| 1776 |
/* |
| 1777 |
* Check if we need to skip ahead to a later tuple (only possible |
| 1778 |
* when the scan uses array keys) |
| 1779 |
*/ |
| 1780 |
if (arrayKeys && OffsetNumberIsValid(pstate.skip)) |
| 1781 |
{ |
| 1782 |
Assert(!passes_quals && pstate.continuescan); |
| 1783 |
Assert(offnum < pstate.skip); |
| 1784 |
Assert(!pstate.forcenonrequired); |
| 1785 |
|
| 1786 |
offnum = pstate.skip; |
| 1787 |
pstate.skip = InvalidOffsetNumber; |
| 1788 |
continue; |
| 1789 |
} |
| 1790 |
|
| 1791 |
if (passes_quals) |
| 1792 |
{ |
| 1793 |
/* tuple passes all scan key conditions */ |
| 1794 |
if (!BTreeTupleIsPosting(itup)) |
| 1795 |
{ |
| 1796 |
/* Remember it */ |
| 1797 |
_bt_saveitem(so, itemIndex, offnum, itup); |
| 1798 |
itemIndex++; |
| 1799 |
} |
| 1800 |
else |
| 1801 |
{ |
| 1802 |
int tupleOffset; |
| 1803 |
|
| 1804 |
/* |
| 1805 |
* Set up state to return posting list, and remember first |
| 1806 |
* TID |
| 1807 |
*/ |
| 1808 |
tupleOffset = |
| 1809 |
_bt_setuppostingitems(so, itemIndex, offnum, |
| 1810 |
BTreeTupleGetPostingN(itup, 0), |
| 1811 |
itup); |
| 1812 |
itemIndex++; |
| 1813 |
/* Remember additional TIDs */ |
| 1814 |
for (int i = 1; i < BTreeTupleGetNPosting(itup); i++) |
| 1815 |
{ |
| 1816 |
_bt_savepostingitem(so, itemIndex, offnum, |
| 1817 |
BTreeTupleGetPostingN(itup, i), |
| 1818 |
tupleOffset); |
| 1819 |
itemIndex++; |
| 1820 |
} |
| 1821 |
} |
| 1822 |
} |
| 1823 |
/* When !continuescan, there can't be any more matches, so stop */ |
| 1824 |
if (!pstate.continuescan) |
| 1825 |
break; |
| 1826 |
|
| 1827 |
offnum = OffsetNumberNext(offnum); |
| 1828 |
} |
| 1829 |
|
| 1830 |
/* |
| 1831 |
* We don't need to visit page to the right when the high key |
| 1832 |
* indicates that no more matches will be found there. |
| 1833 |
* |
| 1834 |
* Checking the high key like this works out more often than you might |
| 1835 |
* think. Leaf page splits pick a split point between the two most |
| 1836 |
* dissimilar tuples (this is weighed against the need to evenly share |
| 1837 |
* free space). Leaf pages with high key attribute values that can |
| 1838 |
* only appear on non-pivot tuples on the right sibling page are |
| 1839 |
* common. |
| 1840 |
*/ |
| 1841 |
if (pstate.continuescan && !so->scanBehind && !P_RIGHTMOST(opaque)) |
| 1842 |
{ |
| 1843 |
ItemId iid = PageGetItemId(page, P_HIKEY); |
| 1844 |
IndexTuple itup = (IndexTuple) PageGetItem(page, iid); |
| 1845 |
int truncatt; |
| 1846 |
|
| 1847 |
/* Reset arrays, per _bt_set_startikey contract */ |
| 1848 |
if (pstate.forcenonrequired) |
| 1849 |
_bt_start_array_keys(scan, dir); |
| 1850 |
pstate.forcenonrequired = false; |
| 1851 |
pstate.startikey = 0; /* _bt_set_startikey ignores P_HIKEY */ |
| 1852 |
|
| 1853 |
truncatt = BTreeTupleGetNAtts(itup, rel); |
| 1854 |
_bt_checkkeys(scan, &pstate, arrayKeys, itup, truncatt); |
| 1855 |
} |
| 1856 |
|
| 1857 |
if (!pstate.continuescan) |
| 1858 |
so->currPos.moreRight = false; |
| 1859 |
|
| 1860 |
Assert(itemIndex <= MaxTIDsPerBTreePage); |
| 1861 |
so->currPos.firstItem = 0; |
| 1862 |
so->currPos.lastItem = itemIndex - 1; |
| 1863 |
so->currPos.itemIndex = 0; |
| 1864 |
} |
| 1865 |
else |
| 1866 |
{ |
| 1867 |
/* SK_SEARCHARRAY backward scans must provide final tuple up front */ |
| 1868 |
if (arrayKeys) |
| 1869 |
{ |
| 1870 |
if (minoff <= maxoff && !P_LEFTMOST(opaque)) |
| 1871 |
{ |
| 1872 |
ItemId iid = PageGetItemId(page, minoff); |
| 1873 |
|
| 1874 |
pstate.finaltup = (IndexTuple) PageGetItem(page, iid); |
| 1875 |
|
| 1876 |
if (so->scanBehind && |
| 1877 |
!_bt_scanbehind_checkkeys(scan, dir, pstate.finaltup)) |
| 1878 |
{ |
| 1879 |
/* Schedule another primitive index scan after all */ |
| 1880 |
so->currPos.moreLeft = false; |
| 1881 |
so->needPrimScan = true; |
| 1882 |
if (scan->parallel_scan) |
| 1883 |
_bt_parallel_primscan_schedule(scan, |
| 1884 |
so->currPos.currPage); |
| 1885 |
return false; |
| 1886 |
} |
| 1887 |
} |
| 1888 |
|
| 1889 |
so->scanBehind = so->oppositeDirCheck = false; /* reset */ |
| 1890 |
} |
| 1891 |
|
| 1892 |
/* |
| 1893 |
* Consider pstate.startikey optimization once the ongoing primitive |
| 1894 |
* index scan has already read at least one page |
| 1895 |
*/ |
| 1896 |
if (!pstate.firstpage && minoff < maxoff) |
| 1897 |
_bt_set_startikey(scan, &pstate); |
| 1898 |
|
| 1899 |
/* load items[] in descending order */ |
| 1900 |
itemIndex = MaxTIDsPerBTreePage; |
| 1901 |
|
| 1902 |
offnum = Min(offnum, maxoff); |
| 1903 |
|
| 1904 |
while (offnum >= minoff) |
| 1905 |
{ |
| 1906 |
ItemId iid = PageGetItemId(page, offnum); |
| 1907 |
IndexTuple itup; |
| 1908 |
bool tuple_alive; |
| 1909 |
bool passes_quals; |
| 1910 |
|
| 1911 |
/* |
| 1912 |
* If the scan specifies not to return killed tuples, then we |
| 1913 |
* treat a killed tuple as not passing the qual. Most of the |
| 1914 |
* time, it's a win to not bother examining the tuple's index |
| 1915 |
* keys, but just skip to the next tuple (previous, actually, |
| 1916 |
* since we're scanning backwards). However, if this is the first |
| 1917 |
* tuple on the page, we do check the index keys, to prevent |
| 1918 |
* uselessly advancing to the page to the left. This is similar |
| 1919 |
* to the high key optimization used by forward scans. |
| 1920 |
*/ |
| 1921 |
if (scan->ignore_killed_tuples && ItemIdIsDead(iid)) |
| 1922 |
{ |
| 1923 |
if (offnum > minoff) |
| 1924 |
{ |
| 1925 |
offnum = OffsetNumberPrev(offnum); |
| 1926 |
continue; |
| 1927 |
} |
| 1928 |
|
| 1929 |
tuple_alive = false; |
| 1930 |
} |
| 1931 |
else |
| 1932 |
tuple_alive = true; |
| 1933 |
|
| 1934 |
itup = (IndexTuple) PageGetItem(page, iid); |
| 1935 |
Assert(!BTreeTupleIsPivot(itup)); |
| 1936 |
|
| 1937 |
pstate.offnum = offnum; |
| 1938 |
if (arrayKeys && offnum == minoff && pstate.forcenonrequired) |
| 1939 |
{ |
| 1940 |
/* Reset arrays, per _bt_set_startikey contract */ |
| 1941 |
pstate.forcenonrequired = false; |
| 1942 |
pstate.startikey = 0; |
| 1943 |
_bt_start_array_keys(scan, dir); |
| 1944 |
} |
| 1945 |
passes_quals = _bt_checkkeys(scan, &pstate, arrayKeys, |
| 1946 |
itup, indnatts); |
| 1947 |
|
| 1948 |
if (arrayKeys && so->scanBehind) |
| 1949 |
{ |
| 1950 |
/* |
| 1951 |
* Done scanning this page, but not done with the current |
| 1952 |
* primscan. |
| 1953 |
* |
| 1954 |
* Note: Forward scans don't check this explicitly, since they |
| 1955 |
* prefer to reuse pstate.skip for this instead. |
| 1956 |
*/ |
| 1957 |
Assert(!passes_quals && pstate.continuescan); |
| 1958 |
Assert(!pstate.forcenonrequired); |
| 1959 |
|
| 1960 |
break; |
| 1961 |
} |
| 1962 |
|
| 1963 |
/* |
| 1964 |
* Check if we need to skip ahead to a later tuple (only possible |
| 1965 |
* when the scan uses array keys) |
| 1966 |
*/ |
| 1967 |
if (arrayKeys && OffsetNumberIsValid(pstate.skip)) |
| 1968 |
{ |
| 1969 |
Assert(!passes_quals && pstate.continuescan); |
| 1970 |
Assert(offnum > pstate.skip); |
| 1971 |
Assert(!pstate.forcenonrequired); |
| 1972 |
|
| 1973 |
offnum = pstate.skip; |
| 1974 |
pstate.skip = InvalidOffsetNumber; |
| 1975 |
continue; |
| 1976 |
} |
| 1977 |
|
| 1978 |
if (passes_quals && tuple_alive) |
| 1979 |
{ |
| 1980 |
/* tuple passes all scan key conditions */ |
| 1981 |
if (!BTreeTupleIsPosting(itup)) |
| 1982 |
{ |
| 1983 |
/* Remember it */ |
| 1984 |
itemIndex--; |
| 1985 |
_bt_saveitem(so, itemIndex, offnum, itup); |
| 1986 |
} |
| 1987 |
else |
| 1988 |
{ |
| 1989 |
int tupleOffset; |
| 1990 |
|
| 1991 |
/* |
| 1992 |
* Set up state to return posting list, and remember first |
| 1993 |
* TID. |
| 1994 |
* |
| 1995 |
* Note that we deliberately save/return items from |
| 1996 |
* posting lists in ascending heap TID order for backwards |
| 1997 |
* scans. This allows _bt_killitems() to make a |
| 1998 |
* consistent assumption about the order of items |
| 1999 |
* associated with the same posting list tuple. |
| 2000 |
*/ |
| 2001 |
itemIndex--; |
| 2002 |
tupleOffset = |
| 2003 |
_bt_setuppostingitems(so, itemIndex, offnum, |
| 2004 |
BTreeTupleGetPostingN(itup, 0), |
| 2005 |
itup); |
| 2006 |
/* Remember additional TIDs */ |
| 2007 |
for (int i = 1; i < BTreeTupleGetNPosting(itup); i++) |
| 2008 |
{ |
| 2009 |
itemIndex--; |
| 2010 |
_bt_savepostingitem(so, itemIndex, offnum, |
| 2011 |
BTreeTupleGetPostingN(itup, i), |
| 2012 |
tupleOffset); |
| 2013 |
} |
| 2014 |
} |
| 2015 |
} |
| 2016 |
/* When !continuescan, there can't be any more matches, so stop */ |
| 2017 |
if (!pstate.continuescan) |
| 2018 |
break; |
| 2019 |
|
| 2020 |
offnum = OffsetNumberPrev(offnum); |
| 2021 |
} |
| 2022 |
|
| 2023 |
/* |
| 2024 |
* We don't need to visit page to the left when no more matches will |
| 2025 |
* be found there |
| 2026 |
*/ |
| 2027 |
if (!pstate.continuescan) |
| 2028 |
so->currPos.moreLeft = false; |
| 2029 |
|
| 2030 |
Assert(itemIndex >= 0); |
| 2031 |
so->currPos.firstItem = itemIndex; |
| 2032 |
so->currPos.lastItem = MaxTIDsPerBTreePage - 1; |
| 2033 |
so->currPos.itemIndex = MaxTIDsPerBTreePage - 1; |
| 2034 |
} |
| 2035 |
|
| 2036 |
/* |
| 2037 |
* If _bt_set_startikey told us to temporarily treat the scan's keys as |
| 2038 |
* nonrequired (possible only during scans with array keys), there must be |
| 2039 |
* no lasting consequences for the scan's array keys. The scan's arrays |
| 2040 |
* should now have exactly the same elements as they would have had if the |
| 2041 |
* nonrequired behavior had never been used. (In general, a scan's arrays |
| 2042 |
* are expected to track its progress through the index's key space.) |
| 2043 |
* |
| 2044 |
* We are required (by _bt_set_startikey) to call _bt_checkkeys against |
| 2045 |
* pstate.finaltup with pstate.forcenonrequired=false to allow the scan's |
| 2046 |
* arrays to recover. Assert that that step hasn't been missed. |
| 2047 |
*/ |
| 2048 |
Assert(!pstate.forcenonrequired); |
| 2049 |
|
| 2050 |
return (so->currPos.firstItem <= so->currPos.lastItem); |
| 2051 |
} |
| 2052 |
|
| 2053 |
/* Save an index item into so->currPos.items[itemIndex] */ |
| 2054 |
static void |
| 2055 |
_bt_saveitem(BTScanOpaque so, int itemIndex, |
| 2056 |
OffsetNumber offnum, IndexTuple itup) |
| 2057 |
{ |
| 2058 |
BTScanPosItem *currItem = &so->currPos.items[itemIndex]; |
| 2059 |
|
| 2060 |
Assert(!BTreeTupleIsPivot(itup) && !BTreeTupleIsPosting(itup)); |
| 2061 |
|
| 2062 |
currItem->heapTid = itup->t_tid; |
| 2063 |
currItem->indexOffset = offnum; |
| 2064 |
if (so->currTuples) |
| 2065 |
{ |
| 2066 |
Size itupsz = IndexTupleSize(itup); |
| 2067 |
|
| 2068 |
currItem->tupleOffset = so->currPos.nextTupleOffset; |
| 2069 |
memcpy(so->currTuples + so->currPos.nextTupleOffset, itup, itupsz); |
| 2070 |
so->currPos.nextTupleOffset += MAXALIGN(itupsz); |
| 2071 |
} |
| 2072 |
} |
| 2073 |
|
| 2074 |
/* |
| 2075 |
* Setup state to save TIDs/items from a single posting list tuple. |
| 2076 |
* |
| 2077 |
* Saves an index item into so->currPos.items[itemIndex] for TID that is |
| 2078 |
* returned to scan first. Second or subsequent TIDs for posting list should |
| 2079 |
* be saved by calling _bt_savepostingitem(). |
| 2080 |
* |
| 2081 |
* Returns an offset into tuple storage space that main tuple is stored at if |
| 2082 |
* needed. |
| 2083 |
*/ |
| 2084 |
static int |
| 2085 |
_bt_setuppostingitems(BTScanOpaque so, int itemIndex, OffsetNumber offnum, |
| 2086 |
ItemPointer heapTid, IndexTuple itup) |
| 2087 |
{ |
| 2088 |
BTScanPosItem *currItem = &so->currPos.items[itemIndex]; |
| 2089 |
|
| 2090 |
Assert(BTreeTupleIsPosting(itup)); |
| 2091 |
|
| 2092 |
currItem->heapTid = *heapTid; |
| 2093 |
currItem->indexOffset = offnum; |
| 2094 |
if (so->currTuples) |
| 2095 |
{ |
| 2096 |
/* Save base IndexTuple (truncate posting list) */ |
| 2097 |
IndexTuple base; |
| 2098 |
Size itupsz = BTreeTupleGetPostingOffset(itup); |
| 2099 |
|
| 2100 |
itupsz = MAXALIGN(itupsz); |
| 2101 |
currItem->tupleOffset = so->currPos.nextTupleOffset; |
| 2102 |
base = (IndexTuple) (so->currTuples + so->currPos.nextTupleOffset); |
| 2103 |
memcpy(base, itup, itupsz); |
| 2104 |
/* Defensively reduce work area index tuple header size */ |
| 2105 |
base->t_info &= ~INDEX_SIZE_MASK; |
| 2106 |
base->t_info |= itupsz; |
| 2107 |
so->currPos.nextTupleOffset += itupsz; |
| 2108 |
|
| 2109 |
return currItem->tupleOffset; |
| 2110 |
} |
| 2111 |
|
| 2112 |
return 0; |
| 2113 |
} |
| 2114 |
|
| 2115 |
/* |
| 2116 |
* Save an index item into so->currPos.items[itemIndex] for current posting |
| 2117 |
* tuple. |
| 2118 |
* |
| 2119 |
* Assumes that _bt_setuppostingitems() has already been called for current |
| 2120 |
* posting list tuple. Caller passes its return value as tupleOffset. |
| 2121 |
*/ |
| 2122 |
static inline void |
| 2123 |
_bt_savepostingitem(BTScanOpaque so, int itemIndex, OffsetNumber offnum, |
| 2124 |
ItemPointer heapTid, int tupleOffset) |
| 2125 |
{ |
| 2126 |
BTScanPosItem *currItem = &so->currPos.items[itemIndex]; |
| 2127 |
|
| 2128 |
currItem->heapTid = *heapTid; |
| 2129 |
currItem->indexOffset = offnum; |
| 2130 |
|
| 2131 |
/* |
| 2132 |
* Have index-only scans return the same base IndexTuple for every TID |
| 2133 |
* that originates from the same posting list |
| 2134 |
*/ |
| 2135 |
if (so->currTuples) |
| 2136 |
currItem->tupleOffset = tupleOffset; |
| 2137 |
} |
| 2138 |
|
| 2139 |
/* |
| 2140 |
* Return the index item from so->currPos.items[so->currPos.itemIndex] to the |
| 2141 |
* index scan by setting the relevant fields in caller's index scan descriptor |
| 2142 |
*/ |
| 2143 |
static inline void |
| 2144 |
_bt_returnitem(IndexScanDesc scan, BTScanOpaque so) |
| 2145 |
{ |
| 2146 |
BTScanPosItem *currItem = &so->currPos.items[so->currPos.itemIndex]; |
| 2147 |
|
| 2148 |
/* Most recent _bt_readpage must have succeeded */ |
| 2149 |
Assert(BTScanPosIsValid(so->currPos)); |
| 2150 |
Assert(so->currPos.itemIndex >= so->currPos.firstItem); |
| 2151 |
Assert(so->currPos.itemIndex <= so->currPos.lastItem); |
| 2152 |
|
| 2153 |
/* Return next item, per amgettuple contract */ |
| 2154 |
scan->xs_heaptid = currItem->heapTid; |
| 2155 |
if (so->currTuples) |
| 2156 |
scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset); |
| 2157 |
} |
| 2158 |
|
| 2159 |
/* |
| 2160 |
* _bt_steppage() -- Step to next page containing valid data for scan |
| 2161 |
* |
| 2162 |
* Wrapper on _bt_readnextpage that performs final steps for the current page. |
| 2163 |
* |
| 2164 |
* On entry, so->currPos must be valid. Its buffer will be pinned, though |
| 2165 |
* never locked. (Actually, when so->dropPin there won't even be a pin held, |
| 2166 |
* though so->currPos.currPage must still be set to a valid block number.) |
| 2167 |
*/ |
| 2168 |
static bool |
| 2169 |
_bt_steppage(IndexScanDesc scan, ScanDirection dir) |
| 2170 |
{ |
| 2171 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2172 |
BlockNumber blkno, |
| 2173 |
lastcurrblkno; |
| 2174 |
|
| 2175 |
Assert(BTScanPosIsValid(so->currPos)); |
| 2176 |
|
| 2177 |
/* Before leaving current page, deal with any killed items */ |
| 2178 |
if (so->numKilled > 0) |
| 2179 |
_bt_killitems(scan); |
| 2180 |
|
| 2181 |
/* |
| 2182 |
* Before we modify currPos, make a copy of the page data if there was a |
| 2183 |
* mark position that needs it. |
| 2184 |
*/ |
| 2185 |
if (so->markItemIndex >= 0) |
| 2186 |
{ |
| 2187 |
/* bump pin on current buffer for assignment to mark buffer */ |
| 2188 |
if (BTScanPosIsPinned(so->currPos)) |
| 2189 |
IncrBufferRefCount(so->currPos.buf); |
| 2190 |
memcpy(&so->markPos, &so->currPos, |
| 2191 |
offsetof(BTScanPosData, items[1]) + |
| 2192 |
so->currPos.lastItem * sizeof(BTScanPosItem)); |
| 2193 |
if (so->markTuples) |
| 2194 |
memcpy(so->markTuples, so->currTuples, |
| 2195 |
so->currPos.nextTupleOffset); |
| 2196 |
so->markPos.itemIndex = so->markItemIndex; |
| 2197 |
so->markItemIndex = -1; |
| 2198 |
|
| 2199 |
/* |
| 2200 |
* If we're just about to start the next primitive index scan |
| 2201 |
* (possible with a scan that has arrays keys, and needs to skip to |
| 2202 |
* continue in the current scan direction), moreLeft/moreRight only |
| 2203 |
* indicate the end of the current primitive index scan. They must |
| 2204 |
* never be taken to indicate that the top-level index scan has ended |
| 2205 |
* (that would be wrong). |
| 2206 |
* |
| 2207 |
* We could handle this case by treating the current array keys as |
| 2208 |
* markPos state. But depending on the current array state like this |
| 2209 |
* would add complexity. Instead, we just unset markPos's copy of |
| 2210 |
* moreRight or moreLeft (whichever might be affected), while making |
| 2211 |
* btrestrpos reset the scan's arrays to their initial scan positions. |
| 2212 |
* In effect, btrestrpos leaves advancing the arrays up to the first |
| 2213 |
* _bt_readpage call (that takes place after it has restored markPos). |
| 2214 |
*/ |
| 2215 |
if (so->needPrimScan) |
| 2216 |
{ |
| 2217 |
if (ScanDirectionIsForward(so->currPos.dir)) |
| 2218 |
so->markPos.moreRight = true; |
| 2219 |
else |
| 2220 |
so->markPos.moreLeft = true; |
| 2221 |
} |
| 2222 |
|
| 2223 |
/* mark/restore not supported by parallel scans */ |
| 2224 |
Assert(!scan->parallel_scan); |
| 2225 |
} |
| 2226 |
|
| 2227 |
BTScanPosUnpinIfPinned(so->currPos); |
| 2228 |
|
| 2229 |
/* Walk to the next page with data */ |
| 2230 |
if (ScanDirectionIsForward(dir)) |
| 2231 |
blkno = so->currPos.nextPage; |
| 2232 |
else |
| 2233 |
blkno = so->currPos.prevPage; |
| 2234 |
lastcurrblkno = so->currPos.currPage; |
| 2235 |
|
| 2236 |
/* |
| 2237 |
* Cancel primitive index scans that were scheduled when the call to |
| 2238 |
* _bt_readpage for currPos happened to use the opposite direction to the |
| 2239 |
* one that we're stepping in now. (It's okay to leave the scan's array |
| 2240 |
* keys as-is, since the next _bt_readpage will advance them.) |
| 2241 |
*/ |
| 2242 |
if (so->currPos.dir != dir) |
| 2243 |
so->needPrimScan = false; |
| 2244 |
|
| 2245 |
return _bt_readnextpage(scan, blkno, lastcurrblkno, dir, false); |
| 2246 |
} |
| 2247 |
|
| 2248 |
/* |
| 2249 |
* _bt_readfirstpage() -- Read first page containing valid data for _bt_first |
| 2250 |
* |
| 2251 |
* _bt_first caller passes us an offnum returned by _bt_binsrch, which might |
| 2252 |
* be an out of bounds offnum such as "maxoff + 1" in certain corner cases. |
| 2253 |
* When we're passed an offnum past the end of the page, we might still manage |
| 2254 |
* to stop the scan on this page by calling _bt_checkkeys against the high |
| 2255 |
* key. See _bt_readpage for full details. |
| 2256 |
* |
| 2257 |
* On entry, so->currPos must be pinned and locked (so offnum stays valid). |
| 2258 |
* Parallel scan callers must have seized the scan before calling here. |
| 2259 |
* |
| 2260 |
* On exit, we'll have updated so->currPos and retained locks and pins |
| 2261 |
* according to the same rules as those laid out for _bt_readnextpage exit. |
| 2262 |
* Like _bt_readnextpage, our return value indicates if there are any matching |
| 2263 |
* records in the given direction. |
| 2264 |
* |
| 2265 |
* We always release the scan for a parallel scan caller, regardless of |
| 2266 |
* success or failure; we'll call _bt_parallel_release as soon as possible. |
| 2267 |
*/ |
| 2268 |
static bool |
| 2269 |
_bt_readfirstpage(IndexScanDesc scan, OffsetNumber offnum, ScanDirection dir) |
| 2270 |
{ |
| 2271 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2272 |
|
| 2273 |
so->numKilled = 0; /* just paranoia */ |
| 2274 |
so->markItemIndex = -1; /* ditto */ |
| 2275 |
|
| 2276 |
/* Initialize so->currPos for the first page (page in so->currPos.buf) */ |
| 2277 |
if (so->needPrimScan) |
| 2278 |
{ |
| 2279 |
Assert(so->numArrayKeys); |
| 2280 |
|
| 2281 |
so->currPos.moreLeft = true; |
| 2282 |
so->currPos.moreRight = true; |
| 2283 |
so->needPrimScan = false; |
| 2284 |
} |
| 2285 |
else if (ScanDirectionIsForward(dir)) |
| 2286 |
{ |
| 2287 |
so->currPos.moreLeft = false; |
| 2288 |
so->currPos.moreRight = true; |
| 2289 |
} |
| 2290 |
else |
| 2291 |
{ |
| 2292 |
so->currPos.moreLeft = true; |
| 2293 |
so->currPos.moreRight = false; |
| 2294 |
} |
| 2295 |
|
| 2296 |
/* |
| 2297 |
* Attempt to load matching tuples from the first page. |
| 2298 |
* |
| 2299 |
* Note that _bt_readpage will finish initializing the so->currPos fields. |
| 2300 |
* _bt_readpage also releases parallel scan (even when it returns false). |
| 2301 |
*/ |
| 2302 |
if (_bt_readpage(scan, dir, offnum, true)) |
| 2303 |
{ |
| 2304 |
Relation rel = scan->indexRelation; |
| 2305 |
|
| 2306 |
/* |
| 2307 |
* _bt_readpage succeeded. Drop the lock (and maybe the pin) on |
| 2308 |
* so->currPos.buf in preparation for btgettuple returning tuples. |
| 2309 |
*/ |
| 2310 |
Assert(BTScanPosIsPinned(so->currPos)); |
| 2311 |
_bt_drop_lock_and_maybe_pin(rel, so); |
| 2312 |
return true; |
| 2313 |
} |
| 2314 |
|
| 2315 |
/* There's no actually-matching data on the page in so->currPos.buf */ |
| 2316 |
_bt_unlockbuf(scan->indexRelation, so->currPos.buf); |
| 2317 |
|
| 2318 |
/* Call _bt_readnextpage using its _bt_steppage wrapper function */ |
| 2319 |
if (!_bt_steppage(scan, dir)) |
| 2320 |
return false; |
| 2321 |
|
| 2322 |
/* _bt_readpage for a later page (now in so->currPos) succeeded */ |
| 2323 |
return true; |
| 2324 |
} |
| 2325 |
|
| 2326 |
/* |
| 2327 |
* _bt_readnextpage() -- Read next page containing valid data for _bt_next |
| 2328 |
* |
| 2329 |
* Caller's blkno is the next interesting page's link, taken from either the |
| 2330 |
* previously-saved right link or left link. lastcurrblkno is the page that |
| 2331 |
* was current at the point where the blkno link was saved, which we use to |
| 2332 |
* reason about concurrent page splits/page deletions during backwards scans. |
| 2333 |
* In the common case where seized=false, blkno is either so->currPos.nextPage |
| 2334 |
* or so->currPos.prevPage, and lastcurrblkno is so->currPos.currPage. |
| 2335 |
* |
| 2336 |
* On entry, so->currPos shouldn't be locked by caller. so->currPos.buf must |
| 2337 |
* be InvalidBuffer/unpinned as needed by caller (note that lastcurrblkno |
| 2338 |
* won't need to be read again in almost all cases). Parallel scan callers |
| 2339 |
* that seized the scan before calling here should pass seized=true; such a |
| 2340 |
* caller's blkno and lastcurrblkno arguments come from the seized scan. |
| 2341 |
* seized=false callers just pass us the blkno/lastcurrblkno taken from their |
| 2342 |
* so->currPos, which (along with so->currPos itself) can be used to end the |
| 2343 |
* scan. A seized=false caller's blkno can never be assumed to be the page |
| 2344 |
* that must be read next during a parallel scan, though. We must figure that |
| 2345 |
* part out for ourselves by seizing the scan (the correct page to read might |
| 2346 |
* already be beyond the seized=false caller's blkno during a parallel scan, |
| 2347 |
* unless blkno/so->currPos.nextPage/so->currPos.prevPage is already P_NONE, |
| 2348 |
* or unless so->currPos.moreRight/so->currPos.moreLeft is already unset). |
| 2349 |
* |
| 2350 |
* On success exit, so->currPos is updated to contain data from the next |
| 2351 |
* interesting page, and we return true. We hold a pin on the buffer on |
| 2352 |
* success exit (except during so->dropPin index scans, when we drop the pin |
| 2353 |
* eagerly to avoid blocking VACUUM). |
| 2354 |
* |
| 2355 |
* If there are no more matching records in the given direction, we invalidate |
| 2356 |
* so->currPos (while ensuring it retains no locks or pins), and return false. |
| 2357 |
* |
| 2358 |
* We always release the scan for a parallel scan caller, regardless of |
| 2359 |
* success or failure; we'll call _bt_parallel_release as soon as possible. |
| 2360 |
*/ |
| 2361 |
static bool |
| 2362 |
_bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, |
| 2363 |
BlockNumber lastcurrblkno, ScanDirection dir, bool seized) |
| 2364 |
{ |
| 2365 |
Relation rel = scan->indexRelation; |
| 2366 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2367 |
|
| 2368 |
Assert(so->currPos.currPage == lastcurrblkno || seized); |
| 2369 |
Assert(!(blkno == P_NONE && seized)); |
| 2370 |
Assert(!BTScanPosIsPinned(so->currPos)); |
| 2371 |
|
| 2372 |
/* |
| 2373 |
* Remember that the scan already read lastcurrblkno, a page to the left |
| 2374 |
* of blkno (or remember reading a page to the right, for backwards scans) |
| 2375 |
*/ |
| 2376 |
if (ScanDirectionIsForward(dir)) |
| 2377 |
so->currPos.moreLeft = true; |
| 2378 |
else |
| 2379 |
so->currPos.moreRight = true; |
| 2380 |
|
| 2381 |
for (;;) |
| 2382 |
{ |
| 2383 |
Page page; |
| 2384 |
BTPageOpaque opaque; |
| 2385 |
|
| 2386 |
if (blkno == P_NONE || |
| 2387 |
(ScanDirectionIsForward(dir) ? |
| 2388 |
!so->currPos.moreRight : !so->currPos.moreLeft)) |
| 2389 |
{ |
| 2390 |
/* most recent _bt_readpage call (for lastcurrblkno) ended scan */ |
| 2391 |
Assert(so->currPos.currPage == lastcurrblkno && !seized); |
| 2392 |
BTScanPosInvalidate(so->currPos); |
| 2393 |
_bt_parallel_done(scan); /* iff !so->needPrimScan */ |
| 2394 |
return false; |
| 2395 |
} |
| 2396 |
|
| 2397 |
Assert(!so->needPrimScan); |
| 2398 |
|
| 2399 |
/* parallel scan must never actually visit so->currPos blkno */ |
| 2400 |
if (!seized && scan->parallel_scan != NULL && |
| 2401 |
!_bt_parallel_seize(scan, &blkno, &lastcurrblkno, false)) |
| 2402 |
{ |
| 2403 |
/* whole scan is now done (or another primitive scan required) */ |
| 2404 |
BTScanPosInvalidate(so->currPos); |
| 2405 |
return false; |
| 2406 |
} |
| 2407 |
|
| 2408 |
if (ScanDirectionIsForward(dir)) |
| 2409 |
{ |
| 2410 |
/* read blkno, but check for interrupts first */ |
| 2411 |
CHECK_FOR_INTERRUPTS(); |
| 2412 |
so->currPos.buf = _bt_getbuf(rel, blkno, BT_READ); |
| 2413 |
} |
| 2414 |
else |
| 2415 |
{ |
| 2416 |
/* read blkno, avoiding race (also checks for interrupts) */ |
| 2417 |
so->currPos.buf = _bt_lock_and_validate_left(rel, &blkno, |
| 2418 |
lastcurrblkno); |
| 2419 |
if (so->currPos.buf == InvalidBuffer) |
| 2420 |
{ |
| 2421 |
/* must have been a concurrent deletion of leftmost page */ |
| 2422 |
BTScanPosInvalidate(so->currPos); |
| 2423 |
_bt_parallel_done(scan); |
| 2424 |
return false; |
| 2425 |
} |
| 2426 |
} |
| 2427 |
|
| 2428 |
page = BufferGetPage(so->currPos.buf); |
| 2429 |
opaque = BTPageGetOpaque(page); |
| 2430 |
lastcurrblkno = blkno; |
| 2431 |
if (likely(!P_IGNORE(opaque))) |
| 2432 |
{ |
| 2433 |
/* see if there are any matches on this page */ |
| 2434 |
if (ScanDirectionIsForward(dir)) |
| 2435 |
{ |
| 2436 |
/* note that this will clear moreRight if we can stop */ |
| 2437 |
if (_bt_readpage(scan, dir, P_FIRSTDATAKEY(opaque), seized)) |
| 2438 |
break; |
| 2439 |
blkno = so->currPos.nextPage; |
| 2440 |
} |
| 2441 |
else |
| 2442 |
{ |
| 2443 |
/* note that this will clear moreLeft if we can stop */ |
| 2444 |
if (_bt_readpage(scan, dir, PageGetMaxOffsetNumber(page), seized)) |
| 2445 |
break; |
| 2446 |
blkno = so->currPos.prevPage; |
| 2447 |
} |
| 2448 |
} |
| 2449 |
else |
| 2450 |
{ |
| 2451 |
/* _bt_readpage not called, so do all this for ourselves */ |
| 2452 |
if (ScanDirectionIsForward(dir)) |
| 2453 |
blkno = opaque->btpo_next; |
| 2454 |
else |
| 2455 |
blkno = opaque->btpo_prev; |
| 2456 |
if (scan->parallel_scan != NULL) |
| 2457 |
_bt_parallel_release(scan, blkno, lastcurrblkno); |
| 2458 |
} |
| 2459 |
|
| 2460 |
/* no matching tuples on this page */ |
| 2461 |
_bt_relbuf(rel, so->currPos.buf); |
| 2462 |
seized = false; /* released by _bt_readpage (or by us) */ |
| 2463 |
} |
| 2464 |
|
| 2465 |
/* |
| 2466 |
* _bt_readpage succeeded. Drop the lock (and maybe the pin) on |
| 2467 |
* so->currPos.buf in preparation for btgettuple returning tuples. |
| 2468 |
*/ |
| 2469 |
Assert(so->currPos.currPage == blkno); |
| 2470 |
Assert(BTScanPosIsPinned(so->currPos)); |
| 2471 |
_bt_drop_lock_and_maybe_pin(rel, so); |
| 2472 |
|
| 2473 |
return true; |
| 2474 |
} |
| 2475 |
|
| 2476 |
/* |
| 2477 |
* _bt_lock_and_validate_left() -- lock caller's left sibling blkno, |
| 2478 |
* recovering from concurrent page splits/page deletions when necessary |
| 2479 |
* |
| 2480 |
* Called during backwards scans, to deal with their unique concurrency rules. |
| 2481 |
* |
| 2482 |
* blkno points to the block number of the page that we expect to move the |
| 2483 |
* scan to. We'll successfully move the scan there when we find that its |
| 2484 |
* right sibling link still points to lastcurrblkno (the page we just read). |
| 2485 |
* Otherwise, we have to figure out which page is the correct one for the scan |
| 2486 |
* to now read the hard way, reasoning about concurrent splits and deletions. |
| 2487 |
* See nbtree/README. |
| 2488 |
* |
| 2489 |
* On return, we have both a pin and a read lock on the returned page, whose |
| 2490 |
* block number will be set in *blkno. Returns InvalidBuffer if there is no |
| 2491 |
* page to the left (no lock or pin is held in that case). |
| 2492 |
* |
| 2493 |
* It is possible for the returned leaf page to be half-dead; caller must |
| 2494 |
* check that condition and step left again when required. |
| 2495 |
*/ |
| 2496 |
static Buffer |
| 2497 |
_bt_lock_and_validate_left(Relation rel, BlockNumber *blkno, |
| 2498 |
BlockNumber lastcurrblkno) |
| 2499 |
{ |
| 2500 |
BlockNumber origblkno = *blkno; /* detects circular links */ |
| 2501 |
|
| 2502 |
for (;;) |
| 2503 |
{ |
| 2504 |
Buffer buf; |
| 2505 |
Page page; |
| 2506 |
BTPageOpaque opaque; |
| 2507 |
int tries; |
| 2508 |
|
| 2509 |
/* check for interrupts while we're not holding any buffer lock */ |
| 2510 |
CHECK_FOR_INTERRUPTS(); |
| 2511 |
buf = _bt_getbuf(rel, *blkno, BT_READ); |
| 2512 |
page = BufferGetPage(buf); |
| 2513 |
opaque = BTPageGetOpaque(page); |
| 2514 |
|
| 2515 |
/* |
| 2516 |
* If this isn't the page we want, walk right till we find what we |
| 2517 |
* want --- but go no more than four hops (an arbitrary limit). If we |
| 2518 |
* don't find the correct page by then, the most likely bet is that |
| 2519 |
* lastcurrblkno got deleted and isn't in the sibling chain at all |
| 2520 |
* anymore, not that its left sibling got split more than four times. |
| 2521 |
* |
| 2522 |
* Note that it is correct to test P_ISDELETED not P_IGNORE here, |
| 2523 |
* because half-dead pages are still in the sibling chain. |
| 2524 |
*/ |
| 2525 |
tries = 0; |
| 2526 |
for (;;) |
| 2527 |
{ |
| 2528 |
if (likely(!P_ISDELETED(opaque) && |
| 2529 |
opaque->btpo_next == lastcurrblkno)) |
| 2530 |
{ |
| 2531 |
/* Found desired page, return it */ |
| 2532 |
return buf; |
| 2533 |
} |
| 2534 |
if (P_RIGHTMOST(opaque) || ++tries > 4) |
| 2535 |
break; |
| 2536 |
/* step right */ |
| 2537 |
*blkno = opaque->btpo_next; |
| 2538 |
buf = _bt_relandgetbuf(rel, buf, *blkno, BT_READ); |
| 2539 |
page = BufferGetPage(buf); |
| 2540 |
opaque = BTPageGetOpaque(page); |
| 2541 |
} |
| 2542 |
|
| 2543 |
/* |
| 2544 |
* Return to the original page (usually the page most recently read by |
| 2545 |
* _bt_readpage, which is passed by caller as lastcurrblkno) to see |
| 2546 |
* what's up with its prev sibling link |
| 2547 |
*/ |
| 2548 |
buf = _bt_relandgetbuf(rel, buf, lastcurrblkno, BT_READ); |
| 2549 |
page = BufferGetPage(buf); |
| 2550 |
opaque = BTPageGetOpaque(page); |
| 2551 |
if (P_ISDELETED(opaque)) |
| 2552 |
{ |
| 2553 |
/* |
| 2554 |
* It was deleted. Move right to first nondeleted page (there |
| 2555 |
* must be one); that is the page that has acquired the deleted |
| 2556 |
* one's keyspace, so stepping left from it will take us where we |
| 2557 |
* want to be. |
| 2558 |
*/ |
| 2559 |
for (;;) |
| 2560 |
{ |
| 2561 |
if (P_RIGHTMOST(opaque)) |
| 2562 |
elog(ERROR, "fell off the end of index \"%s\"", |
| 2563 |
RelationGetRelationName(rel)); |
| 2564 |
lastcurrblkno = opaque->btpo_next; |
| 2565 |
buf = _bt_relandgetbuf(rel, buf, lastcurrblkno, BT_READ); |
| 2566 |
page = BufferGetPage(buf); |
| 2567 |
opaque = BTPageGetOpaque(page); |
| 2568 |
if (!P_ISDELETED(opaque)) |
| 2569 |
break; |
| 2570 |
} |
| 2571 |
} |
| 2572 |
else |
| 2573 |
{ |
| 2574 |
/* |
| 2575 |
* Original lastcurrblkno wasn't deleted; the explanation had |
| 2576 |
* better be that the page to the left got split or deleted. |
| 2577 |
* Without this check, we risk going into an infinite loop. |
| 2578 |
*/ |
| 2579 |
if (opaque->btpo_prev == origblkno) |
| 2580 |
elog(ERROR, "could not find left sibling of block %u in index \"%s\"", |
| 2581 |
lastcurrblkno, RelationGetRelationName(rel)); |
| 2582 |
/* Okay to try again, since left sibling link changed */ |
| 2583 |
} |
| 2584 |
|
| 2585 |
/* |
| 2586 |
* Original lastcurrblkno from caller was concurrently deleted (could |
| 2587 |
* also have been a great many concurrent left sibling page splits). |
| 2588 |
* Found a non-deleted page that should now act as our lastcurrblkno. |
| 2589 |
*/ |
| 2590 |
if (P_LEFTMOST(opaque)) |
| 2591 |
{ |
| 2592 |
/* New lastcurrblkno has no left sibling (concurrently deleted) */ |
| 2593 |
_bt_relbuf(rel, buf); |
| 2594 |
break; |
| 2595 |
} |
| 2596 |
|
| 2597 |
/* Start from scratch with new lastcurrblkno's blkno/prev link */ |
| 2598 |
*blkno = origblkno = opaque->btpo_prev; |
| 2599 |
_bt_relbuf(rel, buf); |
| 2600 |
} |
| 2601 |
|
| 2602 |
return InvalidBuffer; |
| 2603 |
} |
| 2604 |
|
| 2605 |
/* |
| 2606 |
* _bt_get_endpoint() -- Find the first or last page on a given tree level |
| 2607 |
* |
| 2608 |
* If the index is empty, we will return InvalidBuffer; any other failure |
| 2609 |
* condition causes ereport(). We will not return a dead page. |
| 2610 |
* |
| 2611 |
* The returned buffer is pinned and read-locked. |
| 2612 |
*/ |
| 2613 |
Buffer |
| 2614 |
_bt_get_endpoint(Relation rel, uint32 level, bool rightmost) |
| 2615 |
{ |
| 2616 |
Buffer buf; |
| 2617 |
Page page; |
| 2618 |
BTPageOpaque opaque; |
| 2619 |
OffsetNumber offnum; |
| 2620 |
BlockNumber blkno; |
| 2621 |
IndexTuple itup; |
| 2622 |
|
| 2623 |
/* |
| 2624 |
* If we are looking for a leaf page, okay to descend from fast root; |
| 2625 |
* otherwise better descend from true root. (There is no point in being |
| 2626 |
* smarter about intermediate levels.) |
| 2627 |
*/ |
| 2628 |
if (level == 0) |
| 2629 |
buf = _bt_getroot(rel, NULL, BT_READ); |
| 2630 |
else |
| 2631 |
buf = _bt_gettrueroot(rel); |
| 2632 |
|
| 2633 |
if (!BufferIsValid(buf)) |
| 2634 |
return InvalidBuffer; |
| 2635 |
|
| 2636 |
page = BufferGetPage(buf); |
| 2637 |
opaque = BTPageGetOpaque(page); |
| 2638 |
|
| 2639 |
for (;;) |
| 2640 |
{ |
| 2641 |
/* |
| 2642 |
* If we landed on a deleted page, step right to find a live page |
| 2643 |
* (there must be one). Also, if we want the rightmost page, step |
| 2644 |
* right if needed to get to it (this could happen if the page split |
| 2645 |
* since we obtained a pointer to it). |
| 2646 |
*/ |
| 2647 |
while (P_IGNORE(opaque) || |
| 2648 |
(rightmost && !P_RIGHTMOST(opaque))) |
| 2649 |
{ |
| 2650 |
blkno = opaque->btpo_next; |
| 2651 |
if (blkno == P_NONE) |
| 2652 |
elog(ERROR, "fell off the end of index \"%s\"", |
| 2653 |
RelationGetRelationName(rel)); |
| 2654 |
buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ); |
| 2655 |
page = BufferGetPage(buf); |
| 2656 |
opaque = BTPageGetOpaque(page); |
| 2657 |
} |
| 2658 |
|
| 2659 |
/* Done? */ |
| 2660 |
if (opaque->btpo_level == level) |
| 2661 |
break; |
| 2662 |
if (opaque->btpo_level < level) |
| 2663 |
ereport(ERROR, |
| 2664 |
(errcode(ERRCODE_INDEX_CORRUPTED), |
| 2665 |
errmsg_internal("btree level %u not found in index \"%s\"", |
| 2666 |
level, RelationGetRelationName(rel)))); |
| 2667 |
|
| 2668 |
/* Descend to leftmost or rightmost child page */ |
| 2669 |
if (rightmost) |
| 2670 |
offnum = PageGetMaxOffsetNumber(page); |
| 2671 |
else |
| 2672 |
offnum = P_FIRSTDATAKEY(opaque); |
| 2673 |
|
| 2674 |
itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); |
| 2675 |
blkno = BTreeTupleGetDownLink(itup); |
| 2676 |
|
| 2677 |
buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ); |
| 2678 |
page = BufferGetPage(buf); |
| 2679 |
opaque = BTPageGetOpaque(page); |
| 2680 |
} |
| 2681 |
|
| 2682 |
return buf; |
| 2683 |
} |
| 2684 |
|
| 2685 |
/* |
| 2686 |
* _bt_endpoint() -- Find the first or last page in the index, and scan |
| 2687 |
* from there to the first key satisfying all the quals. |
| 2688 |
* |
| 2689 |
* This is used by _bt_first() to set up a scan when we've determined |
| 2690 |
* that the scan must start at the beginning or end of the index (for |
| 2691 |
* a forward or backward scan respectively). |
| 2692 |
* |
| 2693 |
* Parallel scan callers must have seized the scan before calling here. |
| 2694 |
* Exit conditions are the same as for _bt_first(). |
| 2695 |
*/ |
| 2696 |
static bool |
| 2697 |
_bt_endpoint(IndexScanDesc scan, ScanDirection dir) |
| 2698 |
{ |
| 2699 |
Relation rel = scan->indexRelation; |
| 2700 |
BTScanOpaque so = (BTScanOpaque) scan->opaque; |
| 2701 |
Page page; |
| 2702 |
BTPageOpaque opaque; |
| 2703 |
OffsetNumber start; |
| 2704 |
|
| 2705 |
Assert(!BTScanPosIsValid(so->currPos)); |
| 2706 |
Assert(!so->needPrimScan); |
| 2707 |
|
| 2708 |
/* |
| 2709 |
* Scan down to the leftmost or rightmost leaf page. This is a simplified |
| 2710 |
* version of _bt_search(). |
| 2711 |
*/ |
| 2712 |
so->currPos.buf = _bt_get_endpoint(rel, 0, ScanDirectionIsBackward(dir)); |
| 2713 |
|
| 2714 |
if (!BufferIsValid(so->currPos.buf)) |
| 2715 |
{ |
| 2716 |
/* |
| 2717 |
* Empty index. Lock the whole relation using the approach explained |
| 2718 |
* at the same point in the _bt_first path. |
| 2719 |
*/ |
| 2720 |
if (IsolationIsSerializable()) |
| 2721 |
{ |
| 2722 |
PredicateLockRelation(rel, scan->xs_snapshot); |
| 2723 |
so->currPos.buf = _bt_get_endpoint(rel, 0, |
| 2724 |
ScanDirectionIsBackward(dir)); |
| 2725 |
} |
| 2726 |
|
| 2727 |
if (!BufferIsValid(so->currPos.buf)) |
| 2728 |
{ |
| 2729 |
_bt_parallel_done(scan); |
| 2730 |
return false; |
| 2731 |
} |
| 2732 |
} |
| 2733 |
|
| 2734 |
page = BufferGetPage(so->currPos.buf); |
| 2735 |
opaque = BTPageGetOpaque(page); |
| 2736 |
Assert(P_ISLEAF(opaque)); |
| 2737 |
|
| 2738 |
if (ScanDirectionIsForward(dir)) |
| 2739 |
{ |
| 2740 |
/* There could be dead pages to the left, so not this: */ |
| 2741 |
/* Assert(P_LEFTMOST(opaque)); */ |
| 2742 |
|
| 2743 |
start = P_FIRSTDATAKEY(opaque); |
| 2744 |
} |
| 2745 |
else if (ScanDirectionIsBackward(dir)) |
| 2746 |
{ |
| 2747 |
Assert(P_RIGHTMOST(opaque)); |
| 2748 |
|
| 2749 |
start = PageGetMaxOffsetNumber(page); |
| 2750 |
} |
| 2751 |
else |
| 2752 |
{ |
| 2753 |
elog(ERROR, "invalid scan direction: %d", (int) dir); |
| 2754 |
start = 0; /* keep compiler quiet */ |
| 2755 |
} |
| 2756 |
|
| 2757 |
/* |
| 2758 |
* Now load data from the first page of the scan. |
| 2759 |
*/ |
| 2760 |
if (!_bt_readfirstpage(scan, start, dir)) |
| 2761 |
return false; |
| 2762 |
|
| 2763 |
_bt_returnitem(scan, so); |
| 2764 |
return true; |
| 2765 |
} |