Debian Codegraph @

src/backend/access/nbtree/nbtsearch.c

raw
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 = &notnullkeys[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 }