| blob | a662665b55fc87f8acdabb321384a730871041be |
1 /*-------------------------------------------------------------------------
2 *
3 * nbtsearch.c
4 * Search code for postgres btrees.
5 *
6 *
7 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
9 *
10 * IDENTIFICATION
11 * src/backend/access/nbtree/nbtsearch.c
12 *
13 *-------------------------------------------------------------------------
14 */
34 OffsetNumber offnum);
41 IndexTuple itup);
43 OffsetNumber offnum,
48 ScanDirection dir);
54 /*
55 * _bt_drop_lock_and_maybe_pin()
56 *
57 * Unlock the buffer; and if it is safe to release the pin, do that, too.
58 * This will prevent vacuum from stalling in a blocked state trying to read a
59 * page when a cursor is sitting on it.
60 *
61 * See nbtree/README section on making concurrent TID recycling safe.
62 */
63 static void
65 {
71 {
74 }
75 }
77 /*
78 * _bt_search() -- Search the tree for a particular scankey,
79 * or more precisely for the first leaf page it could be on.
80 *
81 * The passed scankey is an insertion-type scankey (see nbtree/README),
82 * but it can omit the rightmost column(s) of the index.
83 *
84 * Return value is a stack of parent-page pointers (i.e. there is no entry for
85 * the leaf level/page). *bufP is set to the address of the leaf-page buffer,
86 * which is locked and pinned. No locks are held on the parent pages,
87 * however!
88 *
89 * The returned buffer is locked according to access parameter. Additionally,
90 * access = BT_WRITE will allow an empty root page to be created and returned.
91 * When access = BT_READ, an empty index will result in *bufP being set to
92 * InvalidBuffer. Also, in BT_WRITE mode, any incomplete splits encountered
93 * during the search will be finished.
94 *
95 * heaprel must be provided by callers that pass access = BT_WRITE, since we
96 * might need to allocate a new root page for caller -- see _bt_allocbuf.
97 */
98 BTStack
101 {
105 /* heaprel must be set whenever _bt_allocbuf is reachable */
109 /* Get the root page to start with */
112 /* If index is empty and access = BT_READ, no root page is created. */
116 /* Loop iterates once per level descended in the tree */
118 {
119 Page page;
120 BTPageOpaque opaque;
121 OffsetNumber offnum;
122 ItemId itemid;
123 IndexTuple itup;
124 BlockNumber child;
125 BTStack new_stack;
127 /*
128 * Race -- the page we just grabbed may have split since we read its
129 * downlink in its parent page (or the metapage). If it has, we may
130 * need to move right to its new sibling. Do that.
131 *
132 * In write-mode, allow _bt_moveright to finish any incomplete splits
133 * along the way. Strictly speaking, we'd only need to finish an
134 * incomplete split on the leaf page we're about to insert to, not on
135 * any of the upper levels (internal pages with incomplete splits are
136 * also taken care of in _bt_getstackbuf). But this is a good
137 * opportunity to finish splits of internal pages too.
138 */
142 /* if this is a leaf page, we're done */
148 /*
149 * Find the appropriate pivot tuple on this page. Its downlink points
150 * to the child page that we're about to descend to.
151 */
158 /*
159 * We need to save the location of the pivot tuple we chose in a new
160 * stack entry for this page/level. If caller ends up splitting a
161 * page one level down, it usually ends up inserting a new pivot
162 * tuple/downlink immediately after the location recorded here.
163 */
169 /*
170 * Page level 1 is lowest non-leaf page level prior to leaves. So, if
171 * we're on the level 1 and asked to lock leaf page in write mode,
172 * then lock next page in write mode, because it must be a leaf.
173 */
177 /* drop the read lock on the page, then acquire one on its child */
180 /* okay, all set to move down a level */
182 }
184 /*
185 * If we're asked to lock leaf in write mode, but didn't manage to, then
186 * relock. This should only happen when the root page is a leaf page (and
187 * the only page in the index other than the metapage).
188 */
190 {
191 /* trade in our read lock for a write lock */
195 /*
196 * Race -- the leaf page may have split after we dropped the read lock
197 * but before we acquired a write lock. If it has, we may need to
198 * move right to its new sibling. Do that.
199 */
201 }
204 }
206 /*
207 * _bt_moveright() -- move right in the btree if necessary.
208 *
209 * When we follow a pointer to reach a page, it is possible that
210 * the page has changed in the meanwhile. If this happens, we're
211 * guaranteed that the page has "split right" -- that is, that any
212 * data that appeared on the page originally is either on the page
213 * or strictly to the right of it.
214 *
215 * This routine decides whether or not we need to move right in the
216 * tree by examining the high key entry on the page. If that entry is
217 * strictly less than the scankey, or <= the scankey in the
218 * key.nextkey=true case, then we followed the wrong link and we need
219 * to move right.
220 *
221 * The passed insertion-type scankey can omit the rightmost column(s) of the
222 * index. (see nbtree/README)
223 *
224 * When key.nextkey is false (the usual case), we are looking for the first
225 * item >= key. When key.nextkey is true, we are looking for the first item
226 * strictly greater than key.
227 *
228 * If forupdate is true, we will attempt to finish any incomplete splits
229 * that we encounter. This is required when locking a target page for an
230 * insertion, because we don't allow inserting on a page before the split is
231 * completed. 'heaprel' and 'stack' are only used if forupdate is true.
232 *
233 * On entry, we have the buffer pinned and a lock of the type specified by
234 * 'access'. If we move right, we release the buffer and lock and acquire
235 * the same on the right sibling. Return value is the buffer we stop at.
236 */
237 static Buffer
239 Relation heaprel,
240 BTScanInsert key,
241 Buffer buf,
243 BTStack stack,
245 {
246 Page page;
247 BTPageOpaque opaque;
248 int32 cmpval;
252 /*
253 * When nextkey = false (normal case): if the scan key that brought us to
254 * this page is > the high key stored on the page, then the page has split
255 * and we need to move right. (pg_upgrade'd !heapkeyspace indexes could
256 * have some duplicates to the right as well as the left, but that's
257 * something that's only ever dealt with on the leaf level, after
258 * _bt_search has found an initial leaf page.)
259 *
260 * When nextkey = true: move right if the scan key is >= page's high key.
261 * (Note that key.scantid cannot be set in this case.)
262 *
263 * The page could even have split more than once, so scan as far as
264 * needed.
265 *
266 * We also have to move right if we followed a link that brought us to a
267 * dead page.
268 */
272 {
279 /*
280 * Finish any incomplete splits we encounter along the way.
281 */
283 {
286 /* upgrade our lock if necessary */
288 {
291 }
295 else
298 /* re-acquire the lock in the right mode, and re-check */
301 }
304 {
305 /* step right one page */
308 }
309 else
311 }
318 }
320 /*
321 * _bt_binsrch() -- Do a binary search for a key on a particular page.
322 *
323 * On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber
324 * of the last key < given scankey, or last key <= given scankey if nextkey
325 * is true. (Since _bt_compare treats the first data key of such a page as
326 * minus infinity, there will be at least one key < scankey, so the result
327 * always points at one of the keys on the page.)
328 *
329 * On a leaf page, _bt_binsrch() returns the final result of the initial
330 * positioning process that started with _bt_first's call to _bt_search.
331 * We're returning a non-pivot tuple offset, so things are a little different.
332 * It is possible that we'll return an offset that's either past the last
333 * non-pivot slot, or (in the case of a backward scan) before the first slot.
334 *
335 * This procedure is not responsible for walking right, it just examines
336 * the given page. _bt_binsrch() has no lock or refcount side effects
337 * on the buffer.
338 */
339 static OffsetNumber
341 BTScanInsert key,
342 Buffer buf)
343 {
344 Page page;
345 BTPageOpaque opaque;
346 OffsetNumber low,
347 high;
348 int32 result,
349 cmpval;
354 /* Requesting nextkey semantics while using scantid seems nonsensical */
356 /* scantid-set callers must use _bt_binsrch_insert() on leaf pages */
362 /*
363 * If there are no keys on the page, return the first available slot. Note
364 * this covers two cases: the page is really empty (no keys), or it
365 * contains only a high key. The latter case is possible after vacuuming.
366 * This can never happen on an internal page, however, since they are
367 * never empty (an internal page must have at least one child).
368 */
372 /*
373 * Binary search to find the first key on the page >= scan key, or first
374 * key > scankey when nextkey is true.
375 *
376 * For nextkey=false (cmpval=1), the loop invariant is: all slots before
377 * 'low' are < scan key, all slots at or after 'high' are >= scan key.
378 *
379 * For nextkey=true (cmpval=0), the loop invariant is: all slots before
380 * 'low' are <= scan key, all slots at or after 'high' are > scan key.
381 *
382 * We can fall out when high == low.
383 */
389 {
392 /* We have low <= mid < high, so mid points at a real slot */
398 else
400 }
402 /*
403 * At this point we have high == low.
404 *
405 * On a leaf page we always return the first non-pivot tuple >= scan key
406 * (resp. > scan key) for forward scan callers. For backward scans, it's
407 * always the _last_ non-pivot tuple < scan key (resp. <= scan key).
408 */
410 {
411 /*
412 * In the backward scan case we're supposed to locate the last
413 * matching tuple on the leaf level -- not the first matching tuple
414 * (the last tuple will be the first one returned by the scan).
415 *
416 * At this point we've located the first non-pivot tuple immediately
417 * after the last matching tuple (which might just be maxoff + 1).
418 * Compensate by stepping back.
419 */
424 }
426 /*
427 * On a non-leaf page, return the last key < scan key (resp. <= scan key).
428 * There must be one if _bt_compare() is playing by the rules.
429 *
430 * _bt_compare() will seldom see any exactly-matching pivot tuples, since
431 * a truncated -inf heap TID is usually enough to prevent it altogether.
432 * Even omitted scan key entries are treated as > truncated attributes.
433 *
434 * However, during backward scans _bt_compare() interprets omitted scan
435 * key attributes as == corresponding truncated -inf attributes instead.
436 * This works just like < would work here. Under this scheme, < strategy
437 * backward scans will always directly descend to the correct leaf page.
438 * In particular, they will never incur an "extra" leaf page access with a
439 * scan key that happens to contain the same prefix of values as some
440 * pivot tuple's untruncated prefix. VACUUM relies on this guarantee when
441 * it uses a leaf page high key to "re-find" a page undergoing deletion.
442 */
446 }
448 /*
449 *
450 * _bt_binsrch_insert() -- Cacheable, incremental leaf page binary search.
451 *
452 * Like _bt_binsrch(), but with support for caching the binary search
453 * bounds. Only used during insertion, and only on the leaf page that it
454 * looks like caller will insert tuple on. Exclusive-locked and pinned
455 * leaf page is contained within insertstate.
456 *
457 * Caches the bounds fields in insertstate so that a subsequent call can
458 * reuse the low and strict high bounds of original binary search. Callers
459 * that use these fields directly must be prepared for the case where low
460 * and/or stricthigh are not on the same page (one or both exceed maxoff
461 * for the page). The case where there are no items on the page (high <
462 * low) makes bounds invalid.
463 *
464 * Caller is responsible for invalidating bounds when it modifies the page
465 * before calling here a second time, and for dealing with posting list
466 * tuple matches (callers can use insertstate's postingoff field to
467 * determine which existing heap TID will need to be replaced by a posting
468 * list split).
469 */
470 OffsetNumber
472 {
474 Page page;
475 BTPageOpaque opaque;
476 OffsetNumber low,
477 high,
478 stricthigh;
479 int32 result,
480 cmpval;
490 {
491 /* Start new binary search */
494 }
495 else
496 {
497 /* Restore result of previous binary search against same page */
500 }
502 /* If there are no keys on the page, return the first available slot */
504 {
505 /* Caller can't reuse bounds */
510 }
512 /*
513 * Binary search to find the first key on the page >= scan key. (nextkey
514 * is always false when inserting).
515 *
516 * The loop invariant is: all slots before 'low' are < scan key, all slots
517 * at or after 'high' are >= scan key. 'stricthigh' is > scan key, and is
518 * maintained to save additional search effort for caller.
519 *
520 * We can fall out when high == low.
521 */
529 {
532 /* We have low <= mid < high, so mid points at a real slot */
538 else
539 {
543 }
545 /*
546 * If tuple at offset located by binary search is a posting list whose
547 * TID range overlaps with caller's scantid, perform posting list
548 * binary search to set postingoff for caller. Caller must split the
549 * posting list when postingoff is set. This should happen
550 * infrequently.
551 */
553 {
554 /*
555 * postingoff should never be set more than once per leaf page
556 * binary search. That would mean that there are duplicate table
557 * TIDs in the index, which is never okay. Check for that here.
558 */
562 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\"",
570 }
571 }
573 /*
574 * On a leaf page, a binary search always returns the first key >= scan
575 * key (at least in !nextkey case), which could be the last slot + 1. This
576 * is also the lower bound of cached search.
577 *
578 * stricthigh may also be the last slot + 1, which prevents caller from
579 * using bounds directly, but is still useful to us if we're called a
580 * second time with cached bounds (cached low will be < stricthigh when
581 * that happens).
582 */
588 }
590 /*----------
591 * _bt_binsrch_posting() -- posting list binary search.
592 *
593 * Helper routine for _bt_binsrch_insert().
594 *
595 * Returns offset into posting list where caller's scantid belongs.
596 *----------
597 */
598 static int
600 {
601 IndexTuple itup;
602 ItemId itemid;
604 high,
605 mid,
606 res;
608 /*
609 * If this isn't a posting tuple, then the index must be corrupt (if it is
610 * an ordinary non-pivot tuple then there must be an existing tuple with a
611 * heap TID that equals inserter's new heap TID/scantid). Defensively
612 * check that tuple is a posting list tuple whose posting list range
613 * includes caller's scantid.
614 *
615 * (This is also needed because contrib/amcheck's rootdescend option needs
616 * to be able to relocate a non-pivot tuple using _bt_binsrch_insert().)
617 */
625 /*
626 * In the event that posting list tuple has LP_DEAD bit set, indicate this
627 * to _bt_binsrch_insert() caller by returning -1, a sentinel value. A
628 * second call to _bt_binsrch_insert() can take place when its caller has
629 * removed the dead item.
630 */
634 /* "high" is past end of posting list for loop invariant */
640 {
649 else
651 }
653 /* Exact match not found */
655 }
657 /*----------
658 * _bt_compare() -- Compare insertion-type scankey to tuple on a page.
659 *
660 * page/offnum: location of btree item to be compared to.
661 *
662 * This routine returns:
663 * <0 if scankey < tuple at offnum;
664 * 0 if scankey == tuple at offnum;
665 * >0 if scankey > tuple at offnum.
666 *
667 * NULLs in the keys are treated as sortable values. Therefore
668 * "equality" does not necessarily mean that the item should be returned
669 * to the caller as a matching key. Similarly, an insertion scankey
670 * with its scantid set is treated as equal to a posting tuple whose TID
671 * range overlaps with their scantid. There generally won't be a
672 * matching TID in the posting tuple, which caller must handle
673 * themselves (e.g., by splitting the posting list tuple).
674 *
675 * CRUCIAL NOTE: on a non-leaf page, the first data key is assumed to be
676 * "minus infinity": this routine will always claim it is less than the
677 * scankey. The actual key value stored is explicitly truncated to 0
678 * attributes (explicitly minus infinity) with version 3+ indexes, but
679 * that isn't relied upon. This allows us to implement the Lehman and
680 * Yao convention that the first down-link pointer is before the first
681 * key. See backend/access/nbtree/README for details.
682 *----------
683 */
684 int32
686 BTScanInsert key,
687 Page page,
688 OffsetNumber offnum)
689 {
692 IndexTuple itup;
693 ItemPointer heapTid;
694 ScanKey scankey;
697 int32 result;
703 /*
704 * Force result ">" if target item is first data item on an internal page
705 * --- see NOTE above.
706 */
713 /*
714 * The scan key is set up with the attribute number associated with each
715 * term in the key. It is important that, if the index is multi-key, the
716 * scan contain the first k key attributes, and that they be in order. If
717 * you think about how multi-key ordering works, you'll understand why
718 * this is.
719 *
720 * We don't test for violation of this condition here, however. The
721 * initial setup for the index scan had better have gotten it right (see
722 * _bt_first).
723 */
730 {
731 Datum datum;
737 {
742 else
744 }
746 {
749 else
751 }
752 else
753 {
754 /*
755 * The sk_func needs to be passed the index value as left arg and
756 * the sk_argument as right arg (they might be of different
757 * types). Since it is convenient for callers to think of
758 * _bt_compare as comparing the scankey to the index item, we have
759 * to flip the sign of the comparison result. (Unless it's a DESC
760 * column, in which case we *don't* flip the sign.)
761 */
764 datum,
769 }
771 /* if the keys are unequal, return the difference */
775 scankey++;
776 }
778 /*
779 * All non-truncated attributes (other than heap TID) were found to be
780 * equal. Treat truncated attributes as minus infinity when scankey has a
781 * key attribute value that would otherwise be compared directly.
782 *
783 * Note: it doesn't matter if ntupatts includes non-key attributes;
784 * scankey won't, so explicitly excluding non-key attributes isn't
785 * necessary.
786 */
790 /*
791 * Use the heap TID attribute and scantid to try to break the tie. The
792 * rules are the same as any other key attribute -- only the
793 * representation differs.
794 */
797 {
798 /*
799 * Forward scans have a scankey that is considered greater than a
800 * truncated pivot tuple if and when the scankey has equal values for
801 * attributes up to and including the least significant untruncated
802 * attribute in tuple. Even attributes that were omitted from the
803 * scan key are considered greater than -inf truncated attributes.
804 * (See _bt_binsrch for an explanation of our backward scan behavior.)
805 *
806 * For example, if an index has the minimum two attributes (single
807 * user key attribute, plus heap TID attribute), and a page's high key
808 * is ('foo', -inf), and scankey is ('foo', <omitted>), the search
809 * will not descend to the page to the left. The search will descend
810 * right instead. The truncated attribute in pivot tuple means that
811 * all non-pivot tuples on the page to the left are strictly < 'foo',
812 * so it isn't necessary to descend left. In other words, search
813 * doesn't have to descend left because it isn't interested in a match
814 * that has a heap TID value of -inf.
815 *
816 * Note: the heap TID part of the test ensures that scankey is being
817 * compared to a pivot tuple with one or more truncated -inf key
818 * attributes. The heap TID attribute is the last key attribute in
819 * every index, of course, but other than that it isn't special.
820 */
825 /* All provided scankey arguments found to be equal */
827 }
829 /*
830 * Treat truncated heap TID as minus infinity, since scankey has a key
831 * attribute value (scantid) that would otherwise be compared directly
832 */
837 /*
838 * Scankey must be treated as equal to a posting list tuple if its scantid
839 * value falls within the range of the posting list. In all other cases
840 * there can only be a single heap TID value, which is compared directly
841 * with scantid.
842 */
847 else
848 {
853 }
856 }
858 /*
859 * _bt_first() -- Find the first item in a scan.
860 *
861 * We need to be clever about the direction of scan, the search
862 * conditions, and the tree ordering. We find the first item (or,
863 * if backwards scan, the last item) in the tree that satisfies the
864 * qualifications in the scan key. On success exit, the page containing
865 * the current index tuple is pinned but not locked, and data about
866 * the matching tuple(s) on the page has been loaded into so->currPos.
867 * scan->xs_heaptid is set to the heap TID of the current tuple, and if
868 * requested, scan->xs_itup points to a copy of the index tuple.
869 *
870 * If there are no matching items in the index, we return false, with no
871 * pins or locks held.
872 *
873 * Note that scan->keyData[], and the so->keyData[] scankey built from it,
874 * are both search-type scankeys (see nbtree/README for more about this).
875 * Within this routine, we build a temporary insertion-type scankey to use
876 * in locating the scan start position.
877 */
878 bool
880 {
883 Buffer buf;
884 BTStack stack;
885 OffsetNumber offnum;
886 StrategyNumber strat;
887 BTScanInsertData inskey;
893 StrategyNumber strat_total;
895 BlockNumber blkno;
899 /*
900 * Examine the scan keys and eliminate any redundant keys; also mark the
901 * keys that must be matched to continue the scan.
902 */
905 /*
906 * Quit now if _bt_preprocess_keys() discovered that the scan keys can
907 * never be satisfied (eg, x == 1 AND x > 2).
908 */
910 {
913 }
915 /*
916 * For parallel scans, get the starting page from shared state. If the
917 * scan has not started, proceed to find out first leaf page in the usual
918 * way while keeping other participating processes waiting. If the scan
919 * has already begun, use the page number from the shared structure.
920 *
921 * When a parallel scan has another primitive index scan scheduled, a
922 * parallel worker will seize the scan for that purpose now. This is
923 * similar to the case where the top-level scan hasn't started.
924 */
926 {
929 /*
930 * Initialize arrays (when _bt_parallel_seize didn't already set up
931 * the next primitive index scan)
932 */
939 {
942 }
944 {
948 }
949 }
951 {
952 /*
953 * First _bt_first call (for current btrescan) without parallelism.
954 *
955 * Initialize arrays, and the corresponding scan keys that were just
956 * output by _bt_preprocess_keys.
957 */
959 }
961 /*
962 * Count an indexscan for stats, now that we know that we'll call
963 * _bt_search/_bt_endpoint below
964 */
967 /*----------
968 * Examine the scan keys to discover where we need to start the scan.
969 *
970 * We want to identify the keys that can be used as starting boundaries;
971 * these are =, >, or >= keys for a forward scan or =, <, <= keys for
972 * a backwards scan. We can use keys for multiple attributes so long as
973 * the prior attributes had only =, >= (resp. =, <=) keys. Once we accept
974 * a > or < boundary or find an attribute with no boundary (which can be
975 * thought of as the same as "> -infinity"), we can't use keys for any
976 * attributes to its right, because it would break our simplistic notion
977 * of what initial positioning strategy to use.
978 *
979 * When the scan keys include cross-type operators, _bt_preprocess_keys
980 * may not be able to eliminate redundant keys; in such cases we will
981 * arbitrarily pick a usable one for each attribute. This is correct
982 * but possibly not optimal behavior. (For example, with keys like
983 * "x >= 4 AND x >= 5" we would elect to scan starting at x=4 when
984 * x=5 would be more efficient.) Since the situation only arises given
985 * a poorly-worded query plus an incomplete opfamily, live with it.
986 *
987 * When both equality and inequality keys appear for a single attribute
988 * (again, only possible when cross-type operators appear), we *must*
989 * select one of the equality keys for the starting point, because
990 * _bt_checkkeys() will stop the scan as soon as an equality qual fails.
991 * For example, if we have keys like "x >= 4 AND x = 10" and we elect to
992 * start at x=4, we will fail and stop before reaching x=10. If multiple
993 * equality quals survive preprocessing, however, it doesn't matter which
994 * one we use --- by definition, they are either redundant or
995 * contradictory.
996 *
997 * Any regular (not SK_SEARCHNULL) key implies a NOT NULL qualifier.
998 * If the index stores nulls at the end of the index we'll be starting
999 * from, and we have no boundary key for the column (which means the key
1000 * we deduced NOT NULL from is an inequality key that constrains the other
1001 * end of the index), then we cons up an explicit SK_SEARCHNOTNULL key to
1002 * use as a boundary key. If we didn't do this, we might find ourselves
1003 * traversing a lot of null entries at the start of the scan.
1004 *
1005 * In this loop, row-comparison keys are treated the same as keys on their
1006 * first (leftmost) columns. We'll add on lower-order columns of the row
1007 * comparison below, if possible.
1008 *
1009 * The selected scan keys (at most one per index column) are remembered by
1010 * storing their addresses into the local startKeys[] array.
1011 *
1012 * _bt_checkkeys/_bt_advance_array_keys decide whether and when to start
1013 * the next primitive index scan (for scans with array keys) based in part
1014 * on an understanding of how it'll enable us to reposition the scan.
1015 * They're directly aware of how we'll sometimes cons up an explicit
1016 * SK_SEARCHNOTNULL key. They'll even end primitive scans by applying a
1017 * symmetric "deduce NOT NULL" rule of their own. This allows top-level
1018 * scans to skip large groups of NULLs through repeated deductions about
1019 * key strictness (for a required inequality key) and whether NULLs in the
1020 * key's index column are stored last or first (relative to non-NULLs).
1021 * If you update anything here, _bt_checkkeys/_bt_advance_array_keys might
1022 * need to be kept in sync.
1023 *----------
1024 */
1027 {
1028 AttrNumber curattr;
1029 ScanKey chosen;
1030 ScanKey impliesNN;
1031 ScanKey cur;
1033 /*
1034 * chosen is the so-far-chosen key for the current attribute, if any.
1035 * We don't cast the decision in stone until we reach keys for the
1036 * next attribute.
1037 */
1040 /* Also remember any scankey that implies a NOT NULL constraint */
1043 /*
1044 * Loop iterates from 0 to numberOfKeys inclusive; we use the last
1045 * pass to handle after-last-key processing. Actual exit from the
1046 * loop is at one of the "break" statements below.
1047 */
1049 {
1051 {
1052 /*
1053 * Done looking at keys for curattr. If we didn't find a
1054 * usable boundary key, see if we can deduce a NOT NULL key.
1055 */
1060 {
1061 /* Yes, so build the key in notnullkeys[keysz] */
1067 curattr,
1069 BTGreaterStrategyNumber :
1070 BTLessStrategyNumber),
1071 InvalidOid,
1072 InvalidOid,
1073 InvalidOid,
1075 }
1077 /*
1078 * If we still didn't find a usable boundary key, quit; else
1079 * save the boundary key pointer in startKeys.
1080 */
1085 /*
1086 * Adjust strat_total, and quit if we have stored a > or <
1087 * key.
1088 */
1091 {
1096 }
1098 /*
1099 * Done if that was the last attribute, or if next key is not
1100 * in sequence (implying no boundary key is available for the
1101 * next attribute).
1102 */
1107 /*
1108 * Reset for next attr.
1109 */
1113 }
1115 /*
1116 * Can we use this key as a starting boundary for this attr?
1117 *
1118 * If not, does it imply a NOT NULL constraint? (Because
1119 * SK_SEARCHNULL keys are always assigned BTEqualStrategyNumber,
1120 * *any* inequality key works for that; we need not test.)
1121 */
1123 {
1127 {
1130 else
1132 }
1135 /* override any non-equality choice */
1141 {
1144 else
1146 }
1148 }
1149 }
1150 }
1152 /*
1153 * If we found no usable boundary keys, we have to start from one end of
1154 * the tree. Walk down that edge to the first or last key, and scan from
1155 * there.
1156 */
1158 {
1164 {
1165 /* No match, so mark (parallel) scan finished */
1167 }
1170 }
1172 /*
1173 * We want to start the scan somewhere within the index. Set up an
1174 * insertion scankey we can use to search for the boundary point we
1175 * identified above. The insertion scankey is built using the keys
1176 * identified by startKeys[]. (Remaining insertion scankey fields are
1177 * initialized after initial-positioning strategy is finalized.)
1178 */
1181 {
1187 {
1188 /*
1189 * Row comparison header: look to the first row member instead.
1190 *
1191 * The member scankeys are already in insertion format (ie, they
1192 * have sk_func = 3-way-comparison function), but we have to watch
1193 * out for nulls, which _bt_preprocess_keys didn't check. A null
1194 * in the first row member makes the condition unmatchable, just
1195 * like qual_ok = false.
1196 */
1201 {
1204 }
1207 /*
1208 * If the row comparison is the last positioning key we accepted,
1209 * try to add additional keys from the lower-order row members.
1210 * (If we accepted independent conditions on additional index
1211 * columns, we use those instead --- doesn't seem worth trying to
1212 * determine which is more restrictive.) Note that this is OK
1213 * even if the row comparison is of ">" or "<" type, because the
1214 * condition applied to all but the last row member is effectively
1215 * ">=" or "<=", and so the extra keys don't break the positioning
1216 * scheme. But, by the same token, if we aren't able to use all
1217 * the row members, then the part of the row comparison that we
1218 * did use has to be treated as just a ">=" or "<=" condition, and
1219 * so we'd better adjust strat_total accordingly.
1220 */
1222 {
1227 {
1228 subkey++;
1239 keysz++;
1241 {
1244 }
1245 }
1247 {
1249 {
1256 }
1257 }
1259 }
1260 }
1261 else
1262 {
1263 /*
1264 * Ordinary comparison key. Transform the search-style scan key
1265 * to an insertion scan key by replacing the sk_func with the
1266 * appropriate btree comparison function.
1267 *
1268 * If scankey operator is not a cross-type comparison, we can use
1269 * the cached comparison function; otherwise gotta look it up in
1270 * the catalogs. (That can't lead to infinite recursion, since no
1271 * indexscan initiated by syscache lookup will use cross-data-type
1272 * operators.)
1273 *
1274 * We support the convention that sk_subtype == InvalidOid means
1275 * the opclass input type; this is a hack to simplify life for
1276 * ScanKeyInit().
1277 */
1280 {
1287 InvalidStrategy,
1290 procinfo,
1292 }
1293 else
1294 {
1295 RegProcedure cmp_proc;
1300 BTORDER_PROC);
1308 InvalidStrategy,
1311 cmp_proc,
1313 }
1314 }
1315 }
1317 /*----------
1318 * Examine the selected initial-positioning strategy to determine exactly
1319 * where we need to start the scan, and set flag variables to control the
1320 * initial descent by _bt_search (and our _bt_binsrch call for the leaf
1321 * page _bt_search returns).
1322 *----------
1323 */
1329 {
1344 /*
1345 * If a backward scan was specified, need to start with last equal
1346 * item not first one.
1347 */
1349 {
1350 /*
1351 * This is the same as the <= strategy
1352 */
1355 }
1356 else
1357 {
1358 /*
1359 * This is the same as the >= strategy
1360 */
1363 }
1368 /*
1369 * Find first item >= scankey
1370 */
1377 /*
1378 * Find first item > scankey
1379 */
1385 /* can't get here, but keep compiler quiet */
1388 }
1390 /*
1391 * Use the manufactured insertion scan key to descend the tree and
1392 * position ourselves on the target leaf page.
1393 */
1397 /* don't need to keep the stack around... */
1401 {
1402 /*
1403 * We only get here if the index is completely empty. Lock relation
1404 * because nothing finer to lock exists. Without a buffer lock, it's
1405 * possible for another transaction to insert data between
1406 * _bt_search() and PredicateLockRelation(). We have to try again
1407 * after taking the relation-level predicate lock, to close a narrow
1408 * window where we wouldn't scan concurrently inserted tuples, but the
1409 * writer wouldn't see our predicate lock.
1410 */
1412 {
1416 }
1419 {
1420 /*
1421 * Mark parallel scan as done, so that all the workers can finish
1422 * their scan.
1423 */
1427 }
1428 }
1434 /* position to the precise item on the page */
1439 /*
1440 * Now load data from the first page of the scan.
1441 *
1442 * If inskey.nextkey = false and inskey.backward = false, offnum is
1443 * positioned at the first non-pivot tuple >= inskey.scankeys.
1444 *
1445 * If inskey.nextkey = false and inskey.backward = true, offnum is
1446 * positioned at the last non-pivot tuple < inskey.scankeys.
1447 *
1448 * If inskey.nextkey = true and inskey.backward = false, offnum is
1449 * positioned at the first non-pivot tuple > inskey.scankeys.
1450 *
1451 * If inskey.nextkey = true and inskey.backward = true, offnum is
1452 * positioned at the last non-pivot tuple <= inskey.scankeys.
1453 *
1454 * It's possible that _bt_binsrch returned an offnum that is out of bounds
1455 * for the page. For example, when inskey is both < the leaf page's high
1456 * key and > all of its non-pivot tuples, offnum will be "maxoff + 1".
1457 */
1459 {
1460 /*
1461 * There's no actually-matching data on this page. Try to advance to
1462 * the next page. Return false if there's no matching data at all.
1463 */
1467 }
1468 else
1469 {
1470 /* We have at least one item to return as scan's first item */
1472 }
1474 readcomplete:
1475 /* OK, itemIndex says what to return */
1482 }
1484 /*
1485 * _bt_next() -- Get the next item in a scan.
1486 *
1487 * On entry, so->currPos describes the current page, which may be pinned
1488 * but is not locked, and so->currPos.itemIndex identifies which item was
1489 * previously returned.
1490 *
1491 * On successful exit, scan->xs_heaptid is set to the TID of the next
1492 * heap tuple, and if requested, scan->xs_itup points to a copy of the
1493 * index tuple. so->currPos is updated as needed.
1494 *
1495 * On failure exit (no more tuples), we release pin and set
1496 * so->currPos.buf to InvalidBuffer.
1497 */
1498 bool
1500 {
1504 /*
1505 * Advance to next tuple on current page; or if there's no more, try to
1506 * step to the next page with data.
1507 */
1509 {
1511 {
1514 }
1515 }
1516 else
1517 {
1519 {
1522 }
1523 }
1525 /* OK, itemIndex says what to return */
1532 }
1534 /*
1535 * _bt_readpage() -- Load data from current index page into so->currPos
1536 *
1537 * Caller must have pinned and read-locked so->currPos.buf; the buffer's state
1538 * is not changed here. Also, currPos.moreLeft and moreRight must be valid;
1539 * they are updated as appropriate. All other fields of so->currPos are
1540 * initialized from scratch here.
1541 *
1542 * We scan the current page starting at offnum and moving in the indicated
1543 * direction. All items matching the scan keys are loaded into currPos.items.
1544 * moreLeft or moreRight (as appropriate) is cleared if _bt_checkkeys reports
1545 * that there can be no more matching tuples in the current scan direction
1546 * (could just be for the current primitive index scan when scan has arrays).
1547 *
1548 * _bt_first caller passes us an offnum returned by _bt_binsrch, which might
1549 * be an out of bounds offnum such as "maxoff + 1" in certain corner cases.
1550 * _bt_checkkeys will stop the scan as soon as an equality qual fails (when
1551 * its scan key was marked required), so _bt_first _must_ pass us an offnum
1552 * exactly at the beginning of where equal tuples are to be found. When we're
1553 * passed an offnum past the end of the page, we might still manage to stop
1554 * the scan on this page by calling _bt_checkkeys against the high key.
1555 *
1556 * In the case of a parallel scan, caller must have called _bt_parallel_seize
1557 * prior to calling this function; this function will invoke
1558 * _bt_parallel_release before returning.
1559 *
1560 * Returns true if any matching items found on the page, false if none.
1561 */
1562 static bool
1565 {
1567 Page page;
1568 BTPageOpaque opaque;
1569 OffsetNumber minoff;
1570 OffsetNumber maxoff;
1571 BTReadPageState pstate;
1574 indnatts;
1576 /*
1577 * We must have the buffer pinned and locked, but the usual macro can't be
1578 * used here; this function is what makes it good for currPos.
1579 */
1585 /* allow next page be processed by parallel worker */
1587 {
1590 else
1594 }
1601 /* initialize page-level state that we'll pass to _bt_checkkeys */
1615 /*
1616 * We note the buffer's block number so that we can release the pin later.
1617 * This allows us to re-read the buffer if it is needed again for hinting.
1618 */
1621 /*
1622 * We save the LSN of the page as we read it, so that we know whether it
1623 * safe to apply LP_DEAD hints to the page later. This allows us to drop
1624 * the pin for MVCC scans, which allows vacuum to avoid blocking.
1625 */
1628 /*
1629 * we must save the page's right-link while scanning it; this tells us
1630 * where to step right to after we're done with these items. There is no
1631 * corresponding need for the left-link, since splits always go right.
1632 */
1635 /* initialize tuple workspace to empty */
1638 /*
1639 * Now that the current page has been made consistent, the macro should be
1640 * good.
1641 */
1644 /*
1645 * Prechecking the value of the continuescan flag for the last item on the
1646 * page (for backwards scan it will be the first item on a page). If we
1647 * observe it to be true, then it should be true for all other items. This
1648 * allows us to do significant optimizations in the _bt_checkkeys()
1649 * function for all the items on the page.
1650 *
1651 * With the forward scan, we do this check for the last item on the page
1652 * instead of the high key. It's relatively likely that the most
1653 * significant column in the high key will be different from the
1654 * corresponding value from the last item on the page. So checking with
1655 * the last item on the page would give a more precise answer.
1656 *
1657 * We skip this for the first page read by each (primitive) scan, to avoid
1658 * slowing down point queries. They typically don't stand to gain much
1659 * when the optimization can be applied, and are more likely to notice the
1660 * overhead of the precheck.
1661 *
1662 * The optimization is unsafe and must be avoided whenever _bt_checkkeys
1663 * just set a low-order required array's key to the best available match
1664 * for a truncated -inf attribute value from the prior page's high key
1665 * (array element 0 is always the best available match in this scenario).
1666 * It's quite likely that matches for array element 0 begin on this page,
1667 * but the start of matches won't necessarily align with page boundaries.
1668 * When the start of matches is somewhere in the middle of this page, it
1669 * would be wrong to treat page's final non-pivot tuple as representative.
1670 * Doing so might lead us to treat some of the page's earlier tuples as
1671 * being part of a group of tuples thought to satisfy the required keys.
1672 *
1673 * Note: Conversely, in the case where the scan's arrays just advanced
1674 * using the prior page's HIKEY _without_ advancement setting scanBehind,
1675 * the start of matches must be aligned with page boundaries, which makes
1676 * it safe to attempt the optimization here now. It's also safe when the
1677 * prior page's HIKEY simply didn't need to advance any required array. In
1678 * both cases we can safely assume that the _first_ tuple from this page
1679 * must be >= the current set of array keys/equality constraints. And so
1680 * if the final tuple is == those same keys (and also satisfies any
1681 * required < or <= strategy scan keys) during the precheck, we can safely
1682 * assume that this must also be true of all earlier tuples from the page.
1683 */
1685 {
1686 ItemId iid;
1687 IndexTuple itup;
1692 /* Call with arrayKeys=false to avoid undesirable side-effects */
1696 }
1699 {
1700 /* SK_SEARCHARRAY forward scans must provide high key up front */
1702 {
1708 {
1711 /*
1712 * Last _bt_readpage call scheduled a recheck of finaltup for
1713 * required scan keys up to and including a > or >= scan key.
1714 *
1715 * _bt_checkkeys won't consider the scanBehind flag unless the
1716 * scan is stopped by a scan key required in the current scan
1717 * direction. We need this recheck so that we'll notice when
1718 * all tuples on this page are still before the _bt_first-wise
1719 * start of matches for the current set of array keys.
1720 */
1722 {
1723 /* Schedule another primitive index scan after all */
1727 }
1729 /* Deliberately don't unset scanBehind flag just yet */
1730 }
1731 }
1733 /* load items[] in ascending order */
1739 {
1741 IndexTuple itup;
1744 /*
1745 * If the scan specifies not to return killed tuples, then we
1746 * treat a killed tuple as not passing the qual
1747 */
1749 {
1752 }
1761 /*
1762 * Check if we need to skip ahead to a later tuple (only possible
1763 * when the scan uses array keys)
1764 */
1766 {
1773 }
1776 {
1777 /* tuple passes all scan key conditions */
1780 {
1781 /* Remember it */
1783 itemIndex++;
1784 }
1785 else
1786 {
1789 /*
1790 * Set up state to return posting list, and remember first
1791 * TID
1792 */
1793 tupleOffset =
1796 itup);
1797 itemIndex++;
1798 /* Remember additional TIDs */
1800 {
1803 tupleOffset);
1804 itemIndex++;
1805 }
1806 }
1807 }
1808 /* When !continuescan, there can't be any more matches, so stop */
1813 }
1815 /*
1816 * We don't need to visit page to the right when the high key
1817 * indicates that no more matches will be found there.
1818 *
1819 * Checking the high key like this works out more often than you might
1820 * think. Leaf page splits pick a split point between the two most
1821 * dissimilar tuples (this is weighed against the need to evenly share
1822 * free space). Leaf pages with high key attribute values that can
1823 * only appear on non-pivot tuples on the right sibling page are
1824 * common.
1825 */
1827 {
1835 }
1844 }
1845 else
1846 {
1847 /* SK_SEARCHARRAY backward scans must provide final tuple up front */
1849 {
1853 }
1855 /* load items[] in descending order */
1861 {
1863 IndexTuple itup;
1867 /*
1868 * If the scan specifies not to return killed tuples, then we
1869 * treat a killed tuple as not passing the qual. Most of the
1870 * time, it's a win to not bother examining the tuple's index
1871 * keys, but just skip to the next tuple (previous, actually,
1872 * since we're scanning backwards). However, if this is the first
1873 * tuple on the page, we do check the index keys, to prevent
1874 * uselessly advancing to the page to the left. This is similar
1875 * to the high key optimization used by forward scans.
1876 */
1878 {
1881 {
1884 }
1887 }
1888 else
1898 /*
1899 * Check if we need to skip ahead to a later tuple (only possible
1900 * when the scan uses array keys)
1901 */
1903 {
1910 }
1913 {
1914 /* tuple passes all scan key conditions */
1917 {
1918 /* Remember it */
1919 itemIndex--;
1921 }
1922 else
1923 {
1926 /*
1927 * Set up state to return posting list, and remember first
1928 * TID.
1929 *
1930 * Note that we deliberately save/return items from
1931 * posting lists in ascending heap TID order for backwards
1932 * scans. This allows _bt_killitems() to make a
1933 * consistent assumption about the order of items
1934 * associated with the same posting list tuple.
1935 */
1936 itemIndex--;
1937 tupleOffset =
1940 itup);
1941 /* Remember additional TIDs */
1943 {
1944 itemIndex--;
1947 tupleOffset);
1948 }
1949 }
1950 }
1951 /* When !continuescan, there can't be any more matches, so stop */
1956 }
1958 /*
1959 * We don't need to visit page to the left when no more matches will
1960 * be found there
1961 */
1969 }
1972 }
1974 /* Save an index item into so->currPos.items[itemIndex] */
1975 static void
1978 {
1986 {
1992 }
1993 }
1995 /*
1996 * Setup state to save TIDs/items from a single posting list tuple.
1997 *
1998 * Saves an index item into so->currPos.items[itemIndex] for TID that is
1999 * returned to scan first. Second or subsequent TIDs for posting list should
2000 * be saved by calling _bt_savepostingitem().
2001 *
2002 * Returns an offset into tuple storage space that main tuple is stored at if
2003 * needed.
2004 */
2005 static int
2008 {
2016 {
2017 /* Save base IndexTuple (truncate posting list) */
2018 IndexTuple base;
2025 /* Defensively reduce work area index tuple header size */
2031 }
2034 }
2036 /*
2037 * Save an index item into so->currPos.items[itemIndex] for current posting
2038 * tuple.
2039 *
2040 * Assumes that _bt_setuppostingitems() has already been called for current
2041 * posting list tuple. Caller passes its return value as tupleOffset.
2042 */
2046 {
2052 /*
2053 * Have index-only scans return the same base IndexTuple for every TID
2054 * that originates from the same posting list
2055 */
2058 }
2060 /*
2061 * _bt_steppage() -- Step to next page containing valid data for scan
2062 *
2063 * On entry, if so->currPos.buf is valid the buffer is pinned but not locked;
2064 * if pinned, we'll drop the pin before moving to next page. The buffer is
2065 * not locked on entry.
2066 *
2067 * For success on a scan using a non-MVCC snapshot we hold a pin, but not a
2068 * read lock, on that page. If we do not hold the pin, we set so->currPos.buf
2069 * to InvalidBuffer. We return true to indicate success.
2070 */
2071 static bool
2073 {
2080 /* Before leaving current page, deal with any killed items */
2084 /*
2085 * Before we modify currPos, make a copy of the page data if there was a
2086 * mark position that needs it.
2087 */
2089 {
2090 /* bump pin on current buffer for assignment to mark buffer */
2102 /*
2103 * If we're just about to start the next primitive index scan
2104 * (possible with a scan that has arrays keys, and needs to skip to
2105 * continue in the current scan direction), moreLeft/moreRight only
2106 * indicate the end of the current primitive index scan. They must
2107 * never be taken to indicate that the top-level index scan has ended
2108 * (that would be wrong).
2109 *
2110 * We could handle this case by treating the current array keys as
2111 * markPos state. But depending on the current array state like this
2112 * would add complexity. Instead, we just unset markPos's copy of
2113 * moreRight or moreLeft (whichever might be affected), while making
2114 * btrestpos reset the scan's arrays to their initial scan positions.
2115 * In effect, btrestpos leaves advancing the arrays up to the first
2116 * _bt_readpage call (that takes place after it has restored markPos).
2117 */
2120 {
2123 else
2125 }
2126 }
2129 {
2130 /* Walk right to the next page with data */
2132 {
2133 /*
2134 * Seize the scan to get the next block number; if the scan has
2135 * ended already, bail out.
2136 */
2139 {
2140 /* release the previous buffer, if pinned */
2144 }
2145 }
2146 else
2147 {
2148 /* Not parallel, so use the previously-saved nextPage link. */
2150 }
2152 /* Remember we left a page with data */
2155 /* release the previous buffer, if pinned */
2157 }
2158 else
2159 {
2160 /* Remember we left a page with data */
2164 {
2165 /*
2166 * Seize the scan to get the current block number; if the scan has
2167 * ended already, bail out.
2168 */
2172 {
2175 }
2176 }
2177 else
2178 {
2179 /* Not parallel, so just use our own notion of the current page */
2181 }
2182 }
2187 /* We have at least one item to return as scan's next item */
2191 }
2193 /*
2194 * _bt_readnextpage() -- Read next page containing valid data for scan
2195 *
2196 * On success exit, so->currPos is updated to contain data from the next
2197 * interesting page, and we return true. Caller must release the lock (and
2198 * maybe the pin) on the buffer on success exit.
2199 *
2200 * If there are no more matching records in the given direction, we drop all
2201 * locks and pins, set so->currPos.buf to InvalidBuffer, and return false.
2202 */
2203 static bool
2205 {
2207 Relation rel;
2208 Page page;
2209 BTPageOpaque opaque;
2215 {
2217 {
2218 /*
2219 * if we're at end of scan, give up and mark parallel scan as
2220 * done, so that all the workers can finish their scan
2221 */
2223 {
2227 }
2228 /* check for interrupts while we're not holding any buffer lock */
2230 /* step right one page */
2234 /* check for deleted page */
2236 {
2238 /* see if there are any matches on this page */
2239 /* note that this will clear moreRight if we can stop */
2242 }
2244 {
2245 /* allow next page be processed by parallel worker */
2247 }
2249 /* nope, keep going */
2251 {
2255 {
2258 }
2259 }
2260 else
2261 {
2264 }
2265 }
2266 }
2267 else
2268 {
2269 /*
2270 * Should only happen in parallel cases, when some other backend
2271 * advanced the scan.
2272 */
2274 {
2277 }
2279 /* Done if we know that the left sibling link isn't of interest */
2281 {
2286 }
2288 /*
2289 * Walk left to the next page with data. This is much more complex
2290 * than the walk-right case because of the possibility that the page
2291 * to our left splits while we are in flight to it, plus the
2292 * possibility that the page we were on gets deleted after we leave
2293 * it. See nbtree/README for details.
2294 *
2295 * It might be possible to rearrange this code to have less overhead
2296 * in pinning and locking, but that would require capturing the left
2297 * sibling block number when the page is initially read, and then
2298 * optimistically starting there (rather than pinning the page twice).
2299 * It is not clear that this would be worth the complexity.
2300 */
2303 else
2307 {
2308 /* Done if we know that the left sibling link isn't of interest */
2310 {
2315 }
2317 /* Step to next physical page */
2320 /* if we're physically at end of index, return failure */
2322 {
2326 }
2328 /*
2329 * Okay, we managed to move left to a non-deleted page. Done if
2330 * it's not half-dead and contains matching tuples. Else loop back
2331 * and do it all again.
2332 */
2336 {
2338 /* see if there are any matches on this page */
2339 /* note that this will clear moreLeft if we can stop */
2342 }
2344 {
2345 /* allow next page be processed by parallel worker */
2347 }
2349 /*
2350 * For parallel scans, get the last page scanned as it is quite
2351 * possible that by the time we try to seize the scan, some other
2352 * worker has already advanced the scan to a different page. We
2353 * must continue based on the latest page scanned by any worker.
2354 */
2356 {
2360 {
2363 }
2365 }
2366 }
2367 }
2370 }
2372 /*
2373 * _bt_parallel_readpage() -- Read current page containing valid data for scan
2374 *
2375 * On success, release lock and maybe pin on buffer. We return true to
2376 * indicate success.
2377 */
2378 static bool
2380 {
2390 /* We have at least one item to return as scan's next item */
2394 }
2396 /*
2397 * _bt_walk_left() -- step left one page, if possible
2398 *
2399 * The given buffer must be pinned and read-locked. This will be dropped
2400 * before stepping left. On return, we have pin and read lock on the
2401 * returned page, instead.
2402 *
2403 * Returns InvalidBuffer if there is no page to the left (no lock is held
2404 * in that case).
2405 *
2406 * It is possible for the returned leaf page to be half-dead; caller must
2407 * check that condition and step left again when required.
2408 */
2409 static Buffer
2411 {
2412 Page page;
2413 BTPageOpaque opaque;
2419 {
2420 BlockNumber obknum;
2421 BlockNumber lblkno;
2422 BlockNumber blkno;
2425 /* if we're at end of tree, release buf and return failure */
2427 {
2430 }
2431 /* remember original page we are stepping left from */
2433 /* step left */
2436 /* check for interrupts while we're not holding any buffer lock */
2442 /*
2443 * If this isn't the page we want, walk right till we find what we
2444 * want --- but go no more than four hops (an arbitrary limit). If we
2445 * don't find the correct page by then, the most likely bet is that
2446 * the original page got deleted and isn't in the sibling chain at all
2447 * anymore, not that its left sibling got split more than four times.
2448 *
2449 * Note that it is correct to test P_ISDELETED not P_IGNORE here,
2450 * because half-dead pages are still in the sibling chain.
2451 */
2454 {
2456 {
2457 /* Found desired page, return it */
2459 }
2466 }
2468 /* Return to the original page to see what's up */
2473 {
2474 /*
2475 * It was deleted. Move right to first nondeleted page (there
2476 * must be one); that is the page that has acquired the deleted
2477 * one's keyspace, so stepping left from it will take us where we
2478 * want to be.
2479 */
2481 {
2491 }
2493 /*
2494 * Now return to top of loop, resetting obknum to point to this
2495 * nondeleted page, and try again.
2496 */
2497 }
2498 else
2499 {
2500 /*
2501 * It wasn't deleted; the explanation had better be that the page
2502 * to the left got split or deleted. Without this check, we'd go
2503 * into an infinite loop if there's anything wrong.
2504 */
2508 /* Okay to try again with new lblkno value */
2509 }
2510 }
2513 }
2515 /*
2516 * _bt_get_endpoint() -- Find the first or last page on a given tree level
2517 *
2518 * If the index is empty, we will return InvalidBuffer; any other failure
2519 * condition causes ereport(). We will not return a dead page.
2520 *
2521 * The returned buffer is pinned and read-locked.
2522 */
2523 Buffer
2525 {
2526 Buffer buf;
2527 Page page;
2528 BTPageOpaque opaque;
2529 OffsetNumber offnum;
2530 BlockNumber blkno;
2531 IndexTuple itup;
2533 /*
2534 * If we are looking for a leaf page, okay to descend from fast root;
2535 * otherwise better descend from true root. (There is no point in being
2536 * smarter about intermediate levels.)
2537 */
2540 else
2550 {
2551 /*
2552 * If we landed on a deleted page, step right to find a live page
2553 * (there must be one). Also, if we want the rightmost page, step
2554 * right if needed to get to it (this could happen if the page split
2555 * since we obtained a pointer to it).
2556 */
2559 {
2567 }
2569 /* Done? */
2578 /* Descend to leftmost or rightmost child page */
2581 else
2590 }
2593 }
2595 /*
2596 * _bt_endpoint() -- Find the first or last page in the index, and scan
2597 * from there to the first key satisfying all the quals.
2598 *
2599 * This is used by _bt_first() to set up a scan when we've determined
2600 * that the scan must start at the beginning or end of the index (for
2601 * a forward or backward scan respectively). Exit conditions are the
2602 * same as for _bt_first().
2603 */
2604 static bool
2606 {
2609 Buffer buf;
2610 Page page;
2611 BTPageOpaque opaque;
2612 OffsetNumber start;
2615 /*
2616 * Scan down to the leftmost or rightmost leaf page. This is a simplified
2617 * version of _bt_search(). We don't maintain a stack since we know we
2618 * won't need it.
2619 */
2623 {
2624 /*
2625 * Empty index. Lock the whole relation, as nothing finer to lock
2626 * exists.
2627 */
2631 }
2639 {
2640 /* There could be dead pages to the left, so not this: */
2641 /* Assert(P_LEFTMOST(opaque)); */
2644 }
2646 {
2650 }
2651 else
2652 {
2655 }
2657 /* remember which buffer we have pinned */
2662 /*
2663 * Now load data from the first page of the scan.
2664 */
2666 {
2667 /*
2668 * There's no actually-matching data on this page. Try to advance to
2669 * the next page. Return false if there's no matching data at all.
2670 */
2674 }
2675 else
2676 {
2677 /* We have at least one item to return as scan's first item */
2679 }
2681 /* OK, itemIndex says what to return */
2688 }
2690 /*
2691 * _bt_initialize_more_data() -- initialize moreLeft, moreRight and scan dir
2692 * from currPos
2693 */
2696 {
2699 {
2705 }
2707 {
2710 }
2711 else
2712 {
2715 }
2718 }