/*------------------------------------------------------------------------- * * nbtsearch.c * Search code for postgres btrees. * * * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION * src/backend/access/nbtree/nbtsearch.c * *------------------------------------------------------------------------- */ #include "postgres.h" #include "access/nbtree.h" #include "access/relscan.h" #include "access/xact.h" #include "executor/instrument_node.h" #include "miscadmin.h" #include "pgstat.h" #include "storage/predicate.h" #include "utils/lsyscache.h" #include "utils/rel.h" static inline void _bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so); static Buffer _bt_moveright(Relation rel, Relation heaprel, BTScanInsert key, Buffer buf, bool forupdate, BTStack stack, int access); static OffsetNumber _bt_binsrch(Relation rel, BTScanInsert key, Buffer buf); static int _bt_binsrch_posting(BTScanInsert key, Page page, OffsetNumber offnum); static inline void _bt_returnitem(IndexScanDesc scan, BTScanOpaque so); static bool _bt_steppage(IndexScanDesc scan, ScanDirection dir); static bool _bt_readfirstpage(IndexScanDesc scan, OffsetNumber offnum, ScanDirection dir); static bool _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, BlockNumber lastcurrblkno, ScanDirection dir, bool seized); static Buffer _bt_lock_and_validate_left(Relation rel, BlockNumber *blkno, BlockNumber lastcurrblkno); static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir); /* * _bt_drop_lock_and_maybe_pin() * * Unlock so->currPos.buf. If scan is so->dropPin, drop the pin, too. * Dropping the pin prevents VACUUM from blocking on acquiring a cleanup lock. */ static inline void _bt_drop_lock_and_maybe_pin(Relation rel, BTScanOpaque so) { if (!so->dropPin) { /* Just drop the lock (not the pin) */ _bt_unlockbuf(rel, so->currPos.buf); return; } /* * Drop both the lock and the pin. * * Have to set so->currPos.lsn so that _bt_killitems has a way to detect * when concurrent heap TID recycling by VACUUM might have taken place. */ Assert(RelationNeedsWAL(rel)); so->currPos.lsn = BufferGetLSNAtomic(so->currPos.buf); _bt_relbuf(rel, so->currPos.buf); so->currPos.buf = InvalidBuffer; } /* * _bt_search() -- Search the tree for a particular scankey, * or more precisely for the first leaf page it could be on. * * The passed scankey is an insertion-type scankey (see nbtree/README), * but it can omit the rightmost column(s) of the index. * * Return value is a stack of parent-page pointers (i.e. there is no entry for * the leaf level/page). *bufP is set to the address of the leaf-page buffer, * which is locked and pinned. No locks are held on the parent pages, * however! * * The returned buffer is locked according to access parameter. Additionally, * access = BT_WRITE will allow an empty root page to be created and returned. * When access = BT_READ, an empty index will result in *bufP being set to * InvalidBuffer. Also, in BT_WRITE mode, any incomplete splits encountered * during the search will be finished. * * heaprel must be provided by callers that pass access = BT_WRITE, since we * might need to allocate a new root page for caller -- see _bt_allocbuf. */ BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP, int access) { BTStack stack_in = NULL; int page_access = BT_READ; /* heaprel must be set whenever _bt_allocbuf is reachable */ Assert(access == BT_READ || access == BT_WRITE); Assert(access == BT_READ || heaprel != NULL); /* Get the root page to start with */ *bufP = _bt_getroot(rel, heaprel, access); /* If index is empty and access = BT_READ, no root page is created. */ if (!BufferIsValid(*bufP)) return (BTStack) NULL; /* Loop iterates once per level descended in the tree */ for (;;) { Page page; BTPageOpaque opaque; OffsetNumber offnum; ItemId itemid; IndexTuple itup; BlockNumber child; BTStack new_stack; /* * Race -- the page we just grabbed may have split since we read its * downlink in its parent page (or the metapage). If it has, we may * need to move right to its new sibling. Do that. * * In write-mode, allow _bt_moveright to finish any incomplete splits * along the way. Strictly speaking, we'd only need to finish an * incomplete split on the leaf page we're about to insert to, not on * any of the upper levels (internal pages with incomplete splits are * also taken care of in _bt_getstackbuf). But this is a good * opportunity to finish splits of internal pages too. */ *bufP = _bt_moveright(rel, heaprel, key, *bufP, (access == BT_WRITE), stack_in, page_access); /* if this is a leaf page, we're done */ page = BufferGetPage(*bufP); opaque = BTPageGetOpaque(page); if (P_ISLEAF(opaque)) break; /* * Find the appropriate pivot tuple on this page. Its downlink points * to the child page that we're about to descend to. */ offnum = _bt_binsrch(rel, key, *bufP); itemid = PageGetItemId(page, offnum); itup = (IndexTuple) PageGetItem(page, itemid); Assert(BTreeTupleIsPivot(itup) || !key->heapkeyspace); child = BTreeTupleGetDownLink(itup); /* * We need to save the location of the pivot tuple we chose in a new * stack entry for this page/level. If caller ends up splitting a * page one level down, it usually ends up inserting a new pivot * tuple/downlink immediately after the location recorded here. */ new_stack = (BTStack) palloc_object(BTStackData); new_stack->bts_blkno = BufferGetBlockNumber(*bufP); new_stack->bts_offset = offnum; new_stack->bts_parent = stack_in; /* * Page level 1 is lowest non-leaf page level prior to leaves. So, if * we're on the level 1 and asked to lock leaf page in write mode, * then lock next page in write mode, because it must be a leaf. */ if (opaque->btpo_level == 1 && access == BT_WRITE) page_access = BT_WRITE; /* drop the read lock on the page, then acquire one on its child */ *bufP = _bt_relandgetbuf(rel, *bufP, child, page_access); /* okay, all set to move down a level */ stack_in = new_stack; } /* * If we're asked to lock leaf in write mode, but didn't manage to, then * relock. This should only happen when the root page is a leaf page (and * the only page in the index other than the metapage). */ if (access == BT_WRITE && page_access == BT_READ) { /* trade in our read lock for a write lock */ _bt_unlockbuf(rel, *bufP); _bt_lockbuf(rel, *bufP, BT_WRITE); /* * Race -- the leaf page may have split after we dropped the read lock * but before we acquired a write lock. If it has, we may need to * move right to its new sibling. Do that. */ *bufP = _bt_moveright(rel, heaprel, key, *bufP, true, stack_in, BT_WRITE); } return stack_in; } /* * _bt_moveright() -- move right in the btree if necessary. * * When we follow a pointer to reach a page, it is possible that * the page has changed in the meanwhile. If this happens, we're * guaranteed that the page has "split right" -- that is, that any * data that appeared on the page originally is either on the page * or strictly to the right of it. * * This routine decides whether or not we need to move right in the * tree by examining the high key entry on the page. If that entry is * strictly less than the scankey, or <= the scankey in the * key.nextkey=true case, then we followed the wrong link and we need * to move right. * * The passed insertion-type scankey can omit the rightmost column(s) of the * index. (see nbtree/README) * * When key.nextkey is false (the usual case), we are looking for the first * item >= key. When key.nextkey is true, we are looking for the first item * strictly greater than key. * * If forupdate is true, we will attempt to finish any incomplete splits * that we encounter. This is required when locking a target page for an * insertion, because we don't allow inserting on a page before the split is * completed. 'heaprel' and 'stack' are only used if forupdate is true. * * On entry, we have the buffer pinned and a lock of the type specified by * 'access'. If we move right, we release the buffer and lock and acquire * the same on the right sibling. Return value is the buffer we stop at. */ static Buffer _bt_moveright(Relation rel, Relation heaprel, BTScanInsert key, Buffer buf, bool forupdate, BTStack stack, int access) { Page page; BTPageOpaque opaque; int32 cmpval; Assert(!forupdate || heaprel != NULL); /* * When nextkey = false (normal case): if the scan key that brought us to * this page is > the high key stored on the page, then the page has split * and we need to move right. (pg_upgrade'd !heapkeyspace indexes could * have some duplicates to the right as well as the left, but that's * something that's only ever dealt with on the leaf level, after * _bt_search has found an initial leaf page.) * * When nextkey = true: move right if the scan key is >= page's high key. * (Note that key.scantid cannot be set in this case.) * * The page could even have split more than once, so scan as far as * needed. * * We also have to move right if we followed a link that brought us to a * dead page. */ cmpval = key->nextkey ? 0 : 1; for (;;) { page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); if (P_RIGHTMOST(opaque)) break; /* * Finish any incomplete splits we encounter along the way. */ if (forupdate && P_INCOMPLETE_SPLIT(opaque)) { BlockNumber blkno = BufferGetBlockNumber(buf); /* upgrade our lock if necessary */ if (access == BT_READ) { _bt_unlockbuf(rel, buf); _bt_lockbuf(rel, buf, BT_WRITE); } if (P_INCOMPLETE_SPLIT(opaque)) _bt_finish_split(rel, heaprel, buf, stack); else _bt_relbuf(rel, buf); /* re-acquire the lock in the right mode, and re-check */ buf = _bt_getbuf(rel, blkno, access); continue; } if (P_IGNORE(opaque) || _bt_compare(rel, key, page, P_HIKEY) >= cmpval) { /* step right one page */ buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access); continue; } else break; } if (P_IGNORE(opaque)) elog(ERROR, "fell off the end of index \"%s\"", RelationGetRelationName(rel)); return buf; } /* * _bt_binsrch() -- Do a binary search for a key on a particular page. * * On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber * of the last key < given scankey, or last key <= given scankey if nextkey * is true. (Since _bt_compare treats the first data key of such a page as * minus infinity, there will be at least one key < scankey, so the result * always points at one of the keys on the page.) * * On a leaf page, _bt_binsrch() returns the final result of the initial * positioning process that started with _bt_first's call to _bt_search. * We're returning a non-pivot tuple offset, so things are a little different. * It is possible that we'll return an offset that's either past the last * non-pivot slot, or (in the case of a backward scan) before the first slot. * * This procedure is not responsible for walking right, it just examines * the given page. _bt_binsrch() has no lock or refcount side effects * on the buffer. */ static OffsetNumber _bt_binsrch(Relation rel, BTScanInsert key, Buffer buf) { Page page; BTPageOpaque opaque; OffsetNumber low, high; int32 result, cmpval; page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); /* Requesting nextkey semantics while using scantid seems nonsensical */ Assert(!key->nextkey || key->scantid == NULL); /* scantid-set callers must use _bt_binsrch_insert() on leaf pages */ Assert(!P_ISLEAF(opaque) || key->scantid == NULL); low = P_FIRSTDATAKEY(opaque); high = PageGetMaxOffsetNumber(page); /* * If there are no keys on the page, return the first available slot. Note * this covers two cases: the page is really empty (no keys), or it * contains only a high key. The latter case is possible after vacuuming. * This can never happen on an internal page, however, since they are * never empty (an internal page must have at least one child). */ if (unlikely(high < low)) return low; /* * Binary search to find the first key on the page >= scan key, or first * key > scankey when nextkey is true. * * For nextkey=false (cmpval=1), the loop invariant is: all slots before * 'low' are < scan key, all slots at or after 'high' are >= scan key. * * For nextkey=true (cmpval=0), the loop invariant is: all slots before * 'low' are <= scan key, all slots at or after 'high' are > scan key. * * We can fall out when high == low. */ high++; /* establish the loop invariant for high */ cmpval = key->nextkey ? 0 : 1; /* select comparison value */ while (high > low) { OffsetNumber mid = low + ((high - low) / 2); /* We have low <= mid < high, so mid points at a real slot */ result = _bt_compare(rel, key, page, mid); if (result >= cmpval) low = mid + 1; else high = mid; } /* * At this point we have high == low. * * On a leaf page we always return the first non-pivot tuple >= scan key * (resp. > scan key) for forward scan callers. For backward scans, it's * always the _last_ non-pivot tuple < scan key (resp. <= scan key). */ if (P_ISLEAF(opaque)) { /* * In the backward scan case we're supposed to locate the last * matching tuple on the leaf level -- not the first matching tuple * (the last tuple will be the first one returned by the scan). * * At this point we've located the first non-pivot tuple immediately * after the last matching tuple (which might just be maxoff + 1). * Compensate by stepping back. */ if (key->backward) return OffsetNumberPrev(low); return low; } /* * On a non-leaf page, return the last key < scan key (resp. <= scan key). * There must be one if _bt_compare() is playing by the rules. * * _bt_compare() will seldom see any exactly-matching pivot tuples, since * a truncated -inf heap TID is usually enough to prevent it altogether. * Even omitted scan key entries are treated as > truncated attributes. * * However, during backward scans _bt_compare() interprets omitted scan * key attributes as == corresponding truncated -inf attributes instead. * This works just like < would work here. Under this scheme, < strategy * backward scans will always directly descend to the correct leaf page. * In particular, they will never incur an "extra" leaf page access with a * scan key that happens to contain the same prefix of values as some * pivot tuple's untruncated prefix. VACUUM relies on this guarantee when * it uses a leaf page high key to "re-find" a page undergoing deletion. */ Assert(low > P_FIRSTDATAKEY(opaque)); return OffsetNumberPrev(low); } /* * * _bt_binsrch_insert() -- Cacheable, incremental leaf page binary search. * * Like _bt_binsrch(), but with support for caching the binary search * bounds. Only used during insertion, and only on the leaf page that it * looks like caller will insert tuple on. Exclusive-locked and pinned * leaf page is contained within insertstate. * * Caches the bounds fields in insertstate so that a subsequent call can * reuse the low and strict high bounds of original binary search. Callers * that use these fields directly must be prepared for the case where low * and/or stricthigh are not on the same page (one or both exceed maxoff * for the page). The case where there are no items on the page (high < * low) makes bounds invalid. * * Caller is responsible for invalidating bounds when it modifies the page * before calling here a second time, and for dealing with posting list * tuple matches (callers can use insertstate's postingoff field to * determine which existing heap TID will need to be replaced by a posting * list split). */ OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate) { BTScanInsert key = insertstate->itup_key; Page page; BTPageOpaque opaque; OffsetNumber low, high, stricthigh; int32 result, cmpval; page = BufferGetPage(insertstate->buf); opaque = BTPageGetOpaque(page); Assert(P_ISLEAF(opaque)); Assert(!key->nextkey); Assert(insertstate->postingoff == 0); if (!insertstate->bounds_valid) { /* Start new binary search */ low = P_FIRSTDATAKEY(opaque); high = PageGetMaxOffsetNumber(page); } else { /* Restore result of previous binary search against same page */ low = insertstate->low; high = insertstate->stricthigh; } /* If there are no keys on the page, return the first available slot */ if (unlikely(high < low)) { /* Caller can't reuse bounds */ insertstate->low = InvalidOffsetNumber; insertstate->stricthigh = InvalidOffsetNumber; insertstate->bounds_valid = false; return low; } /* * Binary search to find the first key on the page >= scan key. (nextkey * is always false when inserting). * * The loop invariant is: all slots before 'low' are < scan key, all slots * at or after 'high' are >= scan key. 'stricthigh' is > scan key, and is * maintained to save additional search effort for caller. * * We can fall out when high == low. */ if (!insertstate->bounds_valid) high++; /* establish the loop invariant for high */ stricthigh = high; /* high initially strictly higher */ cmpval = 1; /* !nextkey comparison value */ while (high > low) { OffsetNumber mid = low + ((high - low) / 2); /* We have low <= mid < high, so mid points at a real slot */ result = _bt_compare(rel, key, page, mid); if (result >= cmpval) low = mid + 1; else { high = mid; if (result != 0) stricthigh = high; } /* * If tuple at offset located by binary search is a posting list whose * TID range overlaps with caller's scantid, perform posting list * binary search to set postingoff for caller. Caller must split the * posting list when postingoff is set. This should happen * infrequently. */ if (unlikely(result == 0 && key->scantid != NULL)) { /* * postingoff should never be set more than once per leaf page * binary search. That would mean that there are duplicate table * TIDs in the index, which is never okay. Check for that here. */ if (insertstate->postingoff != 0) ereport(ERROR, (errcode(ERRCODE_INDEX_CORRUPTED), 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\"", ItemPointerGetBlockNumber(key->scantid), ItemPointerGetOffsetNumber(key->scantid), low, stricthigh, BufferGetBlockNumber(insertstate->buf), RelationGetRelationName(rel)))); insertstate->postingoff = _bt_binsrch_posting(key, page, mid); } } /* * On a leaf page, a binary search always returns the first key >= scan * key (at least in !nextkey case), which could be the last slot + 1. This * is also the lower bound of cached search. * * stricthigh may also be the last slot + 1, which prevents caller from * using bounds directly, but is still useful to us if we're called a * second time with cached bounds (cached low will be < stricthigh when * that happens). */ insertstate->low = low; insertstate->stricthigh = stricthigh; insertstate->bounds_valid = true; return low; } /*---------- * _bt_binsrch_posting() -- posting list binary search. * * Helper routine for _bt_binsrch_insert(). * * Returns offset into posting list where caller's scantid belongs. *---------- */ static int _bt_binsrch_posting(BTScanInsert key, Page page, OffsetNumber offnum) { IndexTuple itup; ItemId itemid; int low, high, mid, res; /* * If this isn't a posting tuple, then the index must be corrupt (if it is * an ordinary non-pivot tuple then there must be an existing tuple with a * heap TID that equals inserter's new heap TID/scantid). Defensively * check that tuple is a posting list tuple whose posting list range * includes caller's scantid. * * (This is also needed because contrib/amcheck's rootdescend option needs * to be able to relocate a non-pivot tuple using _bt_binsrch_insert().) */ itemid = PageGetItemId(page, offnum); itup = (IndexTuple) PageGetItem(page, itemid); if (!BTreeTupleIsPosting(itup)) return 0; Assert(key->heapkeyspace && key->allequalimage); /* * In the event that posting list tuple has LP_DEAD bit set, indicate this * to _bt_binsrch_insert() caller by returning -1, a sentinel value. A * second call to _bt_binsrch_insert() can take place when its caller has * removed the dead item. */ if (ItemIdIsDead(itemid)) return -1; /* "high" is past end of posting list for loop invariant */ low = 0; high = BTreeTupleGetNPosting(itup); Assert(high >= 2); while (high > low) { mid = low + ((high - low) / 2); res = ItemPointerCompare(key->scantid, BTreeTupleGetPostingN(itup, mid)); if (res > 0) low = mid + 1; else if (res < 0) high = mid; else return mid; } /* Exact match not found */ return low; } /*---------- * _bt_compare() -- Compare insertion-type scankey to tuple on a page. * * page/offnum: location of btree item to be compared to. * * This routine returns: * <0 if scankey < tuple at offnum; * 0 if scankey == tuple at offnum; * >0 if scankey > tuple at offnum. * * NULLs in the keys are treated as sortable values. Therefore * "equality" does not necessarily mean that the item should be returned * to the caller as a matching key. Similarly, an insertion scankey * with its scantid set is treated as equal to a posting tuple whose TID * range overlaps with their scantid. There generally won't be a * matching TID in the posting tuple, which caller must handle * themselves (e.g., by splitting the posting list tuple). * * CRUCIAL NOTE: on a non-leaf page, the first data key is assumed to be * "minus infinity": this routine will always claim it is less than the * scankey. The actual key value stored is explicitly truncated to 0 * attributes (explicitly minus infinity) with version 3+ indexes, but * that isn't relied upon. This allows us to implement the Lehman and * Yao convention that the first down-link pointer is before the first * key. See backend/access/nbtree/README for details. *---------- */ int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum) { TupleDesc itupdesc = RelationGetDescr(rel); BTPageOpaque opaque = BTPageGetOpaque(page); IndexTuple itup; ItemPointer heapTid; ScanKey scankey; int ncmpkey; int ntupatts; int32 result; Assert(_bt_check_natts(rel, key->heapkeyspace, page, offnum)); Assert(key->keysz <= IndexRelationGetNumberOfKeyAttributes(rel)); Assert(key->heapkeyspace || key->scantid == NULL); /* * Force result ">" if target item is first data item on an internal page * --- see NOTE above. */ if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque)) return 1; itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); ntupatts = BTreeTupleGetNAtts(itup, rel); /* * The scan key is set up with the attribute number associated with each * term in the key. It is important that, if the index is multi-key, the * scan contain the first k key attributes, and that they be in order. If * you think about how multi-key ordering works, you'll understand why * this is. * * We don't test for violation of this condition here, however. The * initial setup for the index scan had better have gotten it right (see * _bt_first). */ ncmpkey = Min(ntupatts, key->keysz); Assert(key->heapkeyspace || ncmpkey == key->keysz); Assert(!BTreeTupleIsPosting(itup) || key->allequalimage); scankey = key->scankeys; for (int i = 1; i <= ncmpkey; i++) { Datum datum; bool isNull; datum = index_getattr(itup, scankey->sk_attno, itupdesc, &isNull); if (scankey->sk_flags & SK_ISNULL) /* key is NULL */ { if (isNull) result = 0; /* NULL "=" NULL */ else if (scankey->sk_flags & SK_BT_NULLS_FIRST) result = -1; /* NULL "<" NOT_NULL */ else result = 1; /* NULL ">" NOT_NULL */ } else if (isNull) /* key is NOT_NULL and item is NULL */ { if (scankey->sk_flags & SK_BT_NULLS_FIRST) result = 1; /* NOT_NULL ">" NULL */ else result = -1; /* NOT_NULL "<" NULL */ } else { /* * The sk_func needs to be passed the index value as left arg and * the sk_argument as right arg (they might be of different * types). Since it is convenient for callers to think of * _bt_compare as comparing the scankey to the index item, we have * to flip the sign of the comparison result. (Unless it's a DESC * column, in which case we *don't* flip the sign.) */ result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func, scankey->sk_collation, datum, scankey->sk_argument)); if (!(scankey->sk_flags & SK_BT_DESC)) INVERT_COMPARE_RESULT(result); } /* if the keys are unequal, return the difference */ if (result != 0) return result; scankey++; } /* * All non-truncated attributes (other than heap TID) were found to be * equal. Treat truncated attributes as minus infinity when scankey has a * key attribute value that would otherwise be compared directly. * * Note: it doesn't matter if ntupatts includes non-key attributes; * scankey won't, so explicitly excluding non-key attributes isn't * necessary. */ if (key->keysz > ntupatts) return 1; /* * Use the heap TID attribute and scantid to try to break the tie. The * rules are the same as any other key attribute -- only the * representation differs. */ heapTid = BTreeTupleGetHeapTID(itup); if (key->scantid == NULL) { /* * Forward scans have a scankey that is considered greater than a * truncated pivot tuple if and when the scankey has equal values for * attributes up to and including the least significant untruncated * attribute in tuple. Even attributes that were omitted from the * scan key are considered greater than -inf truncated attributes. * (See _bt_binsrch for an explanation of our backward scan behavior.) * * For example, if an index has the minimum two attributes (single * user key attribute, plus heap TID attribute), and a page's high key * is ('foo', -inf), and scankey is ('foo', ), the search * will not descend to the page to the left. The search will descend * right instead. The truncated attribute in pivot tuple means that * all non-pivot tuples on the page to the left are strictly < 'foo', * so it isn't necessary to descend left. In other words, search * doesn't have to descend left because it isn't interested in a match * that has a heap TID value of -inf. * * Note: the heap TID part of the test ensures that scankey is being * compared to a pivot tuple with one or more truncated -inf key * attributes. The heap TID attribute is the last key attribute in * every index, of course, but other than that it isn't special. */ if (!key->backward && key->keysz == ntupatts && heapTid == NULL && key->heapkeyspace) return 1; /* All provided scankey arguments found to be equal */ return 0; } /* * Treat truncated heap TID as minus infinity, since scankey has a key * attribute value (scantid) that would otherwise be compared directly */ Assert(key->keysz == IndexRelationGetNumberOfKeyAttributes(rel)); if (heapTid == NULL) return 1; /* * Scankey must be treated as equal to a posting list tuple if its scantid * value falls within the range of the posting list. In all other cases * there can only be a single heap TID value, which is compared directly * with scantid. */ Assert(ntupatts >= IndexRelationGetNumberOfKeyAttributes(rel)); result = ItemPointerCompare(key->scantid, heapTid); if (result <= 0 || !BTreeTupleIsPosting(itup)) return result; else { result = ItemPointerCompare(key->scantid, BTreeTupleGetMaxHeapTID(itup)); if (result > 0) return 1; } return 0; } /* * _bt_first() -- Find the first item in a scan. * * We need to be clever about the direction of scan, the search * conditions, and the tree ordering. We find the first item (or, * if backwards scan, the last item) in the tree that satisfies the * qualifications in the scan key. On success exit, data about the * matching tuple(s) on the page has been loaded into so->currPos. We'll * drop all locks and hold onto a pin on page's buffer, except during * so->dropPin scans, when we drop both the lock and the pin. * _bt_returnitem sets the next item to return to scan on success exit. * * If there are no matching items in the index, we return false, with no * pins or locks held. so->currPos will remain invalid. * * Note that scan->keyData[], and the so->keyData[] scankey built from it, * are both search-type scankeys (see nbtree/README for more about this). * Within this routine, we build a temporary insertion-type scankey to use * in locating the scan start position. */ bool _bt_first(IndexScanDesc scan, ScanDirection dir) { Relation rel = scan->indexRelation; BTScanOpaque so = (BTScanOpaque) scan->opaque; BTStack stack; OffsetNumber offnum; BTScanInsertData inskey; ScanKey startKeys[INDEX_MAX_KEYS]; ScanKeyData notnullkey; int keysz = 0; StrategyNumber strat_total = InvalidStrategy; BlockNumber blkno = InvalidBlockNumber, lastcurrblkno; Assert(!BTScanPosIsValid(so->currPos)); /* * Examine the scan keys and eliminate any redundant keys; also mark the * keys that must be matched to continue the scan. */ _bt_preprocess_keys(scan); /* * Quit now if _bt_preprocess_keys() discovered that the scan keys can * never be satisfied (eg, x == 1 AND x > 2). */ if (!so->qual_ok) { Assert(!so->needPrimScan); _bt_parallel_done(scan); return false; } /* * If this is a parallel scan, we must seize the scan. _bt_readfirstpage * will likely release the parallel scan later on. */ if (scan->parallel_scan != NULL && !_bt_parallel_seize(scan, &blkno, &lastcurrblkno, true)) return false; /* * Initialize the scan's arrays (if any) for the current scan direction * (except when they were already set to later values as part of * scheduling the primitive index scan that is now underway) */ if (so->numArrayKeys && !so->needPrimScan) _bt_start_array_keys(scan, dir); if (blkno != InvalidBlockNumber) { /* * We anticipated calling _bt_search, but another worker bet us to it. * _bt_readnextpage releases the scan for us (not _bt_readfirstpage). */ Assert(scan->parallel_scan != NULL); Assert(!so->needPrimScan); Assert(blkno != P_NONE); if (!_bt_readnextpage(scan, blkno, lastcurrblkno, dir, true)) return false; _bt_returnitem(scan, so); return true; } /* * Count an indexscan for stats, now that we know that we'll call * _bt_search/_bt_endpoint below */ pgstat_count_index_scan(rel); if (scan->instrument) scan->instrument->nsearches++; /*---------- * Examine the scan keys to discover where we need to start the scan. * The selected scan keys (at most one per index column) are remembered by * storing their addresses into the local startKeys[] array. The final * startKeys[] entry's strategy is set in strat_total. (Actually, there * are a couple of cases where we force a less/more restrictive strategy.) * * We must use the key that was marked required (in the direction opposite * our own scan's) during preprocessing. Each index attribute can only * have one such required key. In general, the keys that we use to find * an initial position when scanning forwards are the same keys that end * the scan on the leaf level when scanning backwards (and vice-versa). * * When the scan keys include cross-type operators, _bt_preprocess_keys * may not be able to eliminate redundant keys; in such cases it will * arbitrarily pick a usable key for each attribute (and scan direction), * ensuring that there is no more than one key required in each direction. * We stop considering further keys once we reach the first nonrequired * key (which must come after all required keys), so this can't affect us. * * The required keys that we use as starting boundaries have to be =, >, * or >= keys for a forward scan or =, <, <= keys for a backwards scan. * We can use keys for multiple attributes so long as the prior attributes * had only =, >= (resp. =, <=) keys. These rules are very similar to the * rules that preprocessing used to determine which keys to mark required. * We cannot always use every required key as a positioning key, though. * Skip arrays necessitate independently applying our own rules here. * Skip arrays are always generally considered = array keys, but we'll * nevertheless treat them as inequalities at certain points of the scan. * When that happens, it _might_ have implications for the number of * required keys that we can safely use for initial positioning purposes. * * For example, a forward scan with a skip array on its leading attribute * (with no low_compare/high_compare) will have at least two required scan * keys, but we won't use any of them as boundary keys during the scan's * initial call here. Our positioning key during the first call here can * be thought of as representing "> -infinity". Similarly, if such a skip * array's low_compare is "a > 'foo'", then we position using "a > 'foo'" * during the scan's initial call here; a lower-order key such as "b = 42" * can't be used until the "a" array advances beyond MINVAL/low_compare. * * On the other hand, if such a skip array's low_compare was "a >= 'foo'", * then we _can_ use "a >= 'foo' AND b = 42" during the initial call here. * A subsequent call here might have us use "a = 'fop' AND b = 42". Note * that we treat = and >= as equivalent when scanning forwards (just as we * treat = and <= as equivalent when scanning backwards). We effectively * do the same thing (though with a distinct "a" element/value) each time. * * All keys (with the exception of SK_SEARCHNULL keys and SK_BT_SKIP * array keys whose array is "null_elem=true") imply a NOT NULL qualifier. * If the index stores nulls at the end of the index we'll be starting * from, and we have no boundary key for the column (which means the key * we deduced NOT NULL from is an inequality key that constrains the other * end of the index), then we cons up an explicit SK_SEARCHNOTNULL key to * use as a boundary key. If we didn't do this, we might find ourselves * traversing a lot of null entries at the start of the scan. * * In this loop, row-comparison keys are treated the same as keys on their * first (leftmost) columns. We'll add all lower-order columns of the row * comparison that were marked required during preprocessing below. * * _bt_advance_array_keys needs to know exactly how we'll reposition the * scan (should it opt to schedule another primitive index scan). It is * critical that primscans only be scheduled when they'll definitely make * some useful progress. _bt_advance_array_keys does this by calling * _bt_checkkeys routines that report whether a tuple is past the end of * matches for the scan's keys (given the scan's current array elements). * If the page's final tuple is "after the end of matches" for a scan that * uses the *opposite* scan direction, then it must follow that it's also * "before the start of matches" for the actual current scan direction. * It is therefore essential that all of our initial positioning rules are * symmetric with _bt_checkkeys's corresponding continuescan=false rule. * If you update anything here, _bt_checkkeys/_bt_advance_array_keys might * need to be kept in sync. *---------- */ if (so->numberOfKeys > 0) { AttrNumber curattr; ScanKey bkey; ScanKey impliesNN; ScanKey cur; /* * bkey will be set to the key that preprocessing left behind as the * boundary key for this attribute, in this scan direction (if any) */ cur = so->keyData; curattr = 1; bkey = NULL; /* Also remember any scankey that implies a NOT NULL constraint */ impliesNN = NULL; /* * Loop iterates from 0 to numberOfKeys inclusive; we use the last * pass to handle after-last-key processing. Actual exit from the * loop is at one of the "break" statements below. */ for (int i = 0;; cur++, i++) { if (i >= so->numberOfKeys || cur->sk_attno != curattr) { /* Done looking for the curattr boundary key */ Assert(bkey == NULL || (bkey->sk_attno == curattr && (bkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)))); Assert(impliesNN == NULL || (impliesNN->sk_attno == curattr && (impliesNN->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)))); /* * If this is a scan key for a skip array whose current * element is MINVAL, choose low_compare (when scanning * backwards it'll be MAXVAL, and we'll choose high_compare). * * Note: if the array's low_compare key makes 'bkey' NULL, * then we behave as if the array's first element is -inf, * except when !array->null_elem implies a usable NOT NULL * constraint. */ if (bkey != NULL && (bkey->sk_flags & (SK_BT_MINVAL | SK_BT_MAXVAL))) { int ikey = bkey - so->keyData; ScanKey skipequalitykey = bkey; BTArrayKeyInfo *array = NULL; for (int arridx = 0; arridx < so->numArrayKeys; arridx++) { array = &so->arrayKeys[arridx]; if (array->scan_key == ikey) break; } if (ScanDirectionIsForward(dir)) { Assert(!(skipequalitykey->sk_flags & SK_BT_MAXVAL)); bkey = array->low_compare; } else { Assert(!(skipequalitykey->sk_flags & SK_BT_MINVAL)); bkey = array->high_compare; } Assert(bkey == NULL || bkey->sk_attno == skipequalitykey->sk_attno); if (!array->null_elem) impliesNN = skipequalitykey; else Assert(bkey == NULL && impliesNN == NULL); } /* * If we didn't find a usable boundary key, see if we can * deduce a NOT NULL key */ if (bkey == NULL && impliesNN != NULL && ((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ? ScanDirectionIsForward(dir) : ScanDirectionIsBackward(dir))) { /* Final startKeys[] entry will be deduced NOT NULL key */ bkey = ¬nullkey; ScanKeyEntryInitialize(bkey, (SK_SEARCHNOTNULL | SK_ISNULL | (impliesNN->sk_flags & (SK_BT_DESC | SK_BT_NULLS_FIRST))), curattr, ScanDirectionIsForward(dir) ? BTGreaterStrategyNumber : BTLessStrategyNumber, InvalidOid, InvalidOid, InvalidOid, (Datum) 0); } /* * If preprocessing didn't leave a usable boundary key, quit; * else save the boundary key pointer in startKeys[] */ if (bkey == NULL) break; startKeys[keysz++] = bkey; /* * We can only consider adding more boundary keys when the one * that we just chose to add uses either the = or >= strategy * (during backwards scans we can only do so when the key that * we just added to startKeys[] uses the = or <= strategy) */ strat_total = bkey->sk_strategy; if (strat_total == BTGreaterStrategyNumber || strat_total == BTLessStrategyNumber) break; /* * If the key that we just added to startKeys[] is a skip * array = key whose current element is marked NEXT or PRIOR, * make strat_total > or < (and stop adding boundary keys). * This can only happen with opclasses that lack skip support. */ if (bkey->sk_flags & (SK_BT_NEXT | SK_BT_PRIOR)) { Assert(bkey->sk_flags & SK_BT_SKIP); Assert(strat_total == BTEqualStrategyNumber); if (ScanDirectionIsForward(dir)) { Assert(!(bkey->sk_flags & SK_BT_PRIOR)); strat_total = BTGreaterStrategyNumber; } else { Assert(!(bkey->sk_flags & SK_BT_NEXT)); strat_total = BTLessStrategyNumber; } /* * We're done. We'll never find an exact = match for a * NEXT or PRIOR sentinel sk_argument value. There's no * sense in trying to add more keys to startKeys[]. */ break; } /* * Done if that was the last scan key output by preprocessing. * Also done if we've now examined all keys marked required. */ if (i >= so->numberOfKeys || !(cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))) break; /* * Reset for next attr. */ Assert(cur->sk_attno == curattr + 1); curattr = cur->sk_attno; bkey = NULL; impliesNN = NULL; } /* * If we've located the starting boundary key for curattr, we have * no interest in curattr's other required key */ if (bkey != NULL) continue; /* * Is this key the starting boundary key for curattr? * * If not, does it imply a NOT NULL constraint? (Because * SK_SEARCHNULL keys are always assigned BTEqualStrategyNumber, * *any* inequality key works for that; we need not test.) */ switch (cur->sk_strategy) { case BTLessStrategyNumber: case BTLessEqualStrategyNumber: if (ScanDirectionIsBackward(dir)) bkey = cur; else if (impliesNN == NULL) impliesNN = cur; break; case BTEqualStrategyNumber: bkey = cur; break; case BTGreaterEqualStrategyNumber: case BTGreaterStrategyNumber: if (ScanDirectionIsForward(dir)) bkey = cur; else if (impliesNN == NULL) impliesNN = cur; break; } } } /* * If we found no usable boundary keys, we have to start from one end of * the tree. Walk down that edge to the first or last key, and scan from * there. * * Note: calls _bt_readfirstpage for us, which releases the parallel scan. */ if (keysz == 0) return _bt_endpoint(scan, dir); /* * We want to start the scan somewhere within the index. Set up an * insertion scankey we can use to search for the boundary point we * identified above. The insertion scankey is built using the keys * identified by startKeys[]. (Remaining insertion scankey fields are * initialized after initial-positioning scan keys are finalized.) */ Assert(keysz <= INDEX_MAX_KEYS); for (int i = 0; i < keysz; i++) { ScanKey bkey = startKeys[i]; Assert(bkey->sk_attno == i + 1); if (bkey->sk_flags & SK_ROW_HEADER) { /* * Row comparison header: look to the first row member instead */ ScanKey subkey = (ScanKey) DatumGetPointer(bkey->sk_argument); bool loosen_strat = false, tighten_strat = false; /* * Cannot be a NULL in the first row member: _bt_preprocess_keys * would've marked the qual as unsatisfiable, preventing us from * ever getting this far */ Assert(subkey->sk_flags & SK_ROW_MEMBER); Assert(subkey->sk_attno == bkey->sk_attno); Assert(!(subkey->sk_flags & SK_ISNULL)); /* * This is either a > or >= key (during backwards scans it is * either < or <=) that was marked required during preprocessing. * Later so->keyData[] keys can't have been marked required, so * our row compare header key must be the final startKeys[] entry. */ Assert(subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)); Assert(subkey->sk_strategy == bkey->sk_strategy); Assert(subkey->sk_strategy == strat_total); Assert(i == keysz - 1); /* * The member scankeys are already in insertion format (ie, they * have sk_func = 3-way-comparison function) */ memcpy(inskey.scankeys + i, subkey, sizeof(ScanKeyData)); /* * Now look to later row compare members. * * If there's an "index attribute gap" between two row compare * members, the second member won't have been marked required, and * so can't be used as a starting boundary key here. The part of * the row comparison that we do still use has to be treated as a * ">=" or "<=" condition. For example, a qual "(a, c) > (1, 42)" * with an omitted intervening index attribute "b" will use an * insertion scan key "a >= 1". Even the first "a = 1" tuple on * the leaf level might satisfy the row compare qual. * * We're able to use a _more_ restrictive strategy when we reach a * NULL row compare member, since they're always unsatisfiable. * For example, a qual "(a, b, c) >= (1, NULL, 77)" will use an * insertion scan key "a > 1". All tuples where "a = 1" cannot * possibly satisfy the row compare qual, so this is safe. */ Assert(!(subkey->sk_flags & SK_ROW_END)); for (;;) { subkey++; Assert(subkey->sk_flags & SK_ROW_MEMBER); if (subkey->sk_flags & SK_ISNULL) { /* * NULL member key, can only use earlier keys. * * We deliberately avoid checking if this key is marked * required. All earlier keys are required, and this key * is unsatisfiable either way, so we can't miss anything. */ tighten_strat = true; break; } if (!(subkey->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD))) { /* nonrequired member key, can only use earlier keys */ loosen_strat = true; break; } Assert(subkey->sk_attno == keysz + 1); Assert(subkey->sk_strategy == bkey->sk_strategy); Assert(keysz < INDEX_MAX_KEYS); memcpy(inskey.scankeys + keysz, subkey, sizeof(ScanKeyData)); keysz++; if (subkey->sk_flags & SK_ROW_END) break; } Assert(!(loosen_strat && tighten_strat)); if (loosen_strat) { /* Use less restrictive strategy (and fewer member keys) */ switch (strat_total) { case BTLessStrategyNumber: strat_total = BTLessEqualStrategyNumber; break; case BTGreaterStrategyNumber: strat_total = BTGreaterEqualStrategyNumber; break; } } if (tighten_strat) { /* Use more restrictive strategy (and fewer member keys) */ switch (strat_total) { case BTLessEqualStrategyNumber: strat_total = BTLessStrategyNumber; break; case BTGreaterEqualStrategyNumber: strat_total = BTGreaterStrategyNumber; break; } } /* Done (row compare header key is always last startKeys[] key) */ break; } /* * Ordinary comparison key/search-style key. * * Transform the search-style scan key to an insertion scan key by * replacing the sk_func with the appropriate btree 3-way-comparison * function. * * If scankey operator is not a cross-type comparison, we can use the * cached comparison function; otherwise gotta look it up in the * catalogs. (That can't lead to infinite recursion, since no * indexscan initiated by syscache lookup will use cross-data-type * operators.) * * We support the convention that sk_subtype == InvalidOid means the * opclass input type; this hack simplifies life for ScanKeyInit(). */ if (bkey->sk_subtype == rel->rd_opcintype[i] || bkey->sk_subtype == InvalidOid) { FmgrInfo *procinfo; procinfo = index_getprocinfo(rel, bkey->sk_attno, BTORDER_PROC); ScanKeyEntryInitializeWithInfo(inskey.scankeys + i, bkey->sk_flags, bkey->sk_attno, InvalidStrategy, bkey->sk_subtype, bkey->sk_collation, procinfo, bkey->sk_argument); } else { RegProcedure cmp_proc; cmp_proc = get_opfamily_proc(rel->rd_opfamily[i], rel->rd_opcintype[i], bkey->sk_subtype, BTORDER_PROC); if (!RegProcedureIsValid(cmp_proc)) elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"", BTORDER_PROC, rel->rd_opcintype[i], bkey->sk_subtype, bkey->sk_attno, RelationGetRelationName(rel)); ScanKeyEntryInitialize(inskey.scankeys + i, bkey->sk_flags, bkey->sk_attno, InvalidStrategy, bkey->sk_subtype, bkey->sk_collation, cmp_proc, bkey->sk_argument); } } /*---------- * Examine the selected initial-positioning strategy to determine exactly * where we need to start the scan, and set flag variables to control the * initial descent by _bt_search (and our _bt_binsrch call for the leaf * page _bt_search returns). *---------- */ _bt_metaversion(rel, &inskey.heapkeyspace, &inskey.allequalimage); inskey.anynullkeys = false; /* unused */ inskey.scantid = NULL; inskey.keysz = keysz; switch (strat_total) { case BTLessStrategyNumber: inskey.nextkey = false; inskey.backward = true; break; case BTLessEqualStrategyNumber: inskey.nextkey = true; inskey.backward = true; break; case BTEqualStrategyNumber: /* * If a backward scan was specified, need to start with last equal * item not first one. */ if (ScanDirectionIsBackward(dir)) { /* * This is the same as the <= strategy */ inskey.nextkey = true; inskey.backward = true; } else { /* * This is the same as the >= strategy */ inskey.nextkey = false; inskey.backward = false; } break; case BTGreaterEqualStrategyNumber: /* * Find first item >= scankey */ inskey.nextkey = false; inskey.backward = false; break; case BTGreaterStrategyNumber: /* * Find first item > scankey */ inskey.nextkey = true; inskey.backward = false; break; default: /* can't get here, but keep compiler quiet */ elog(ERROR, "unrecognized strat_total: %d", (int) strat_total); return false; } /* * Use the manufactured insertion scan key to descend the tree and * position ourselves on the target leaf page. */ Assert(ScanDirectionIsBackward(dir) == inskey.backward); stack = _bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ); /* don't need to keep the stack around... */ _bt_freestack(stack); if (!BufferIsValid(so->currPos.buf)) { Assert(!so->needPrimScan); /* * We only get here if the index is completely empty. Lock relation * because nothing finer to lock exists. Without a buffer lock, it's * possible for another transaction to insert data between * _bt_search() and PredicateLockRelation(). We have to try again * after taking the relation-level predicate lock, to close a narrow * window where we wouldn't scan concurrently inserted tuples, but the * writer wouldn't see our predicate lock. */ if (IsolationIsSerializable()) { PredicateLockRelation(rel, scan->xs_snapshot); stack = _bt_search(rel, NULL, &inskey, &so->currPos.buf, BT_READ); _bt_freestack(stack); } if (!BufferIsValid(so->currPos.buf)) { _bt_parallel_done(scan); return false; } } /* position to the precise item on the page */ offnum = _bt_binsrch(rel, &inskey, so->currPos.buf); /* * Now load data from the first page of the scan (usually the page * currently in so->currPos.buf). * * If inskey.nextkey = false and inskey.backward = false, offnum is * positioned at the first non-pivot tuple >= inskey.scankeys. * * If inskey.nextkey = false and inskey.backward = true, offnum is * positioned at the last non-pivot tuple < inskey.scankeys. * * If inskey.nextkey = true and inskey.backward = false, offnum is * positioned at the first non-pivot tuple > inskey.scankeys. * * If inskey.nextkey = true and inskey.backward = true, offnum is * positioned at the last non-pivot tuple <= inskey.scankeys. * * It's possible that _bt_binsrch returned an offnum that is out of bounds * for the page. For example, when inskey is both < the leaf page's high * key and > all of its non-pivot tuples, offnum will be "maxoff + 1". */ if (!_bt_readfirstpage(scan, offnum, dir)) return false; _bt_returnitem(scan, so); return true; } /* * _bt_next() -- Get the next item in a scan. * * On entry, so->currPos describes the current page, which may be pinned * but is not locked, and so->currPos.itemIndex identifies which item was * previously returned. * * On success exit, so->currPos is updated as needed, and _bt_returnitem * sets the next item to return to the scan. so->currPos remains valid. * * On failure exit (no more tuples), we invalidate so->currPos. It'll * still be possible for the scan to return tuples by changing direction, * though we'll need to call _bt_first anew in that other direction. */ bool _bt_next(IndexScanDesc scan, ScanDirection dir) { BTScanOpaque so = (BTScanOpaque) scan->opaque; Assert(BTScanPosIsValid(so->currPos)); /* * Advance to next tuple on current page; or if there's no more, try to * step to the next page with data. */ if (ScanDirectionIsForward(dir)) { if (++so->currPos.itemIndex > so->currPos.lastItem) { if (!_bt_steppage(scan, dir)) return false; } } else { if (--so->currPos.itemIndex < so->currPos.firstItem) { if (!_bt_steppage(scan, dir)) return false; } } _bt_returnitem(scan, so); return true; } /* * Return the index item from so->currPos.items[so->currPos.itemIndex] to the * index scan by setting the relevant fields in caller's index scan descriptor */ static inline void _bt_returnitem(IndexScanDesc scan, BTScanOpaque so) { BTScanPosItem *currItem = &so->currPos.items[so->currPos.itemIndex]; /* Most recent _bt_readpage must have succeeded */ Assert(BTScanPosIsValid(so->currPos)); Assert(so->currPos.itemIndex >= so->currPos.firstItem); Assert(so->currPos.itemIndex <= so->currPos.lastItem); /* Return next item, per amgettuple contract */ scan->xs_heaptid = currItem->heapTid; if (so->currTuples) scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset); } /* * _bt_steppage() -- Step to next page containing valid data for scan * * Wrapper on _bt_readnextpage that performs final steps for the current page. * * On entry, so->currPos must be valid. Its buffer will be pinned, though * never locked. (Actually, when so->dropPin there won't even be a pin held, * though so->currPos.currPage must still be set to a valid block number.) */ static bool _bt_steppage(IndexScanDesc scan, ScanDirection dir) { BTScanOpaque so = (BTScanOpaque) scan->opaque; BlockNumber blkno, lastcurrblkno; Assert(BTScanPosIsValid(so->currPos)); /* Before leaving current page, deal with any killed items */ if (so->numKilled > 0) _bt_killitems(scan); /* * Before we modify currPos, make a copy of the page data if there was a * mark position that needs it. */ if (so->markItemIndex >= 0) { /* bump pin on current buffer for assignment to mark buffer */ if (BTScanPosIsPinned(so->currPos)) IncrBufferRefCount(so->currPos.buf); memcpy(&so->markPos, &so->currPos, offsetof(BTScanPosData, items[1]) + so->currPos.lastItem * sizeof(BTScanPosItem)); if (so->markTuples) memcpy(so->markTuples, so->currTuples, so->currPos.nextTupleOffset); so->markPos.itemIndex = so->markItemIndex; so->markItemIndex = -1; /* * If we're just about to start the next primitive index scan * (possible with a scan that has arrays keys, and needs to skip to * continue in the current scan direction), moreLeft/moreRight only * indicate the end of the current primitive index scan. They must * never be taken to indicate that the top-level index scan has ended * (that would be wrong). * * We could handle this case by treating the current array keys as * markPos state. But depending on the current array state like this * would add complexity. Instead, we just unset markPos's copy of * moreRight or moreLeft (whichever might be affected), while making * btrestrpos reset the scan's arrays to their initial scan positions. * In effect, btrestrpos leaves advancing the arrays up to the first * _bt_readpage call (that takes place after it has restored markPos). */ if (so->needPrimScan) { if (ScanDirectionIsForward(so->currPos.dir)) so->markPos.moreRight = true; else so->markPos.moreLeft = true; } /* mark/restore not supported by parallel scans */ Assert(!scan->parallel_scan); } BTScanPosUnpinIfPinned(so->currPos); /* Walk to the next page with data */ if (ScanDirectionIsForward(dir)) blkno = so->currPos.nextPage; else blkno = so->currPos.prevPage; lastcurrblkno = so->currPos.currPage; /* * Cancel primitive index scans that were scheduled when the call to * _bt_readpage for currPos happened to use the opposite direction to the * one that we're stepping in now. (It's okay to leave the scan's array * keys as-is, since the next _bt_readpage will advance them.) */ if (so->currPos.dir != dir) so->needPrimScan = false; return _bt_readnextpage(scan, blkno, lastcurrblkno, dir, false); } /* * _bt_readfirstpage() -- Read first page containing valid data for _bt_first * * _bt_first caller passes us an offnum returned by _bt_binsrch, which might * be an out of bounds offnum such as "maxoff + 1" in certain corner cases. * When we're passed an offnum past the end of the page, we might still manage * to stop the scan on this page by calling _bt_checkkeys against the high * key. See _bt_readpage for full details. * * On entry, so->currPos must be pinned and locked (so offnum stays valid). * Parallel scan callers must have seized the scan before calling here. * * On exit, we'll have updated so->currPos and retained locks and pins * according to the same rules as those laid out for _bt_readnextpage exit. * Like _bt_readnextpage, our return value indicates if there are any matching * records in the given direction. * * We always release the scan for a parallel scan caller, regardless of * success or failure; we'll call _bt_parallel_release as soon as possible. */ static bool _bt_readfirstpage(IndexScanDesc scan, OffsetNumber offnum, ScanDirection dir) { BTScanOpaque so = (BTScanOpaque) scan->opaque; so->numKilled = 0; /* just paranoia */ so->markItemIndex = -1; /* ditto */ /* Initialize so->currPos for the first page (page in so->currPos.buf) */ if (so->needPrimScan) { Assert(so->numArrayKeys); so->currPos.moreLeft = true; so->currPos.moreRight = true; so->needPrimScan = false; } else if (ScanDirectionIsForward(dir)) { so->currPos.moreLeft = false; so->currPos.moreRight = true; } else { so->currPos.moreLeft = true; so->currPos.moreRight = false; } /* * Attempt to load matching tuples from the first page. * * Note that _bt_readpage will finish initializing the so->currPos fields. * _bt_readpage also releases parallel scan (even when it returns false). */ if (_bt_readpage(scan, dir, offnum, true)) { Relation rel = scan->indexRelation; /* * _bt_readpage succeeded. Drop the lock (and maybe the pin) on * so->currPos.buf in preparation for btgettuple returning tuples. */ Assert(BTScanPosIsPinned(so->currPos)); _bt_drop_lock_and_maybe_pin(rel, so); return true; } /* There's no actually-matching data on the page in so->currPos.buf */ _bt_unlockbuf(scan->indexRelation, so->currPos.buf); /* Call _bt_readnextpage using its _bt_steppage wrapper function */ if (!_bt_steppage(scan, dir)) return false; /* _bt_readpage for a later page (now in so->currPos) succeeded */ return true; } /* * _bt_readnextpage() -- Read next page containing valid data for _bt_next * * Caller's blkno is the next interesting page's link, taken from either the * previously-saved right link or left link. lastcurrblkno is the page that * was current at the point where the blkno link was saved, which we use to * reason about concurrent page splits/page deletions during backwards scans. * In the common case where seized=false, blkno is either so->currPos.nextPage * or so->currPos.prevPage, and lastcurrblkno is so->currPos.currPage. * * On entry, so->currPos shouldn't be locked by caller. so->currPos.buf must * be InvalidBuffer/unpinned as needed by caller (note that lastcurrblkno * won't need to be read again in almost all cases). Parallel scan callers * that seized the scan before calling here should pass seized=true; such a * caller's blkno and lastcurrblkno arguments come from the seized scan. * seized=false callers just pass us the blkno/lastcurrblkno taken from their * so->currPos, which (along with so->currPos itself) can be used to end the * scan. A seized=false caller's blkno can never be assumed to be the page * that must be read next during a parallel scan, though. We must figure that * part out for ourselves by seizing the scan (the correct page to read might * already be beyond the seized=false caller's blkno during a parallel scan, * unless blkno/so->currPos.nextPage/so->currPos.prevPage is already P_NONE, * or unless so->currPos.moreRight/so->currPos.moreLeft is already unset). * * On success exit, so->currPos is updated to contain data from the next * interesting page, and we return true. We hold a pin on the buffer on * success exit (except during so->dropPin index scans, when we drop the pin * eagerly to avoid blocking VACUUM). * * If there are no more matching records in the given direction, we invalidate * so->currPos (while ensuring it retains no locks or pins), and return false. * * We always release the scan for a parallel scan caller, regardless of * success or failure; we'll call _bt_parallel_release as soon as possible. */ static bool _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, BlockNumber lastcurrblkno, ScanDirection dir, bool seized) { Relation rel = scan->indexRelation; BTScanOpaque so = (BTScanOpaque) scan->opaque; Assert(so->currPos.currPage == lastcurrblkno || seized); Assert(!(blkno == P_NONE && seized)); Assert(!BTScanPosIsPinned(so->currPos)); /* * Remember that the scan already read lastcurrblkno, a page to the left * of blkno (or remember reading a page to the right, for backwards scans) */ if (ScanDirectionIsForward(dir)) so->currPos.moreLeft = true; else so->currPos.moreRight = true; for (;;) { Page page; BTPageOpaque opaque; if (blkno == P_NONE || (ScanDirectionIsForward(dir) ? !so->currPos.moreRight : !so->currPos.moreLeft)) { /* most recent _bt_readpage call (for lastcurrblkno) ended scan */ Assert(so->currPos.currPage == lastcurrblkno && !seized); BTScanPosInvalidate(so->currPos); _bt_parallel_done(scan); /* iff !so->needPrimScan */ return false; } Assert(!so->needPrimScan); /* parallel scan must never actually visit so->currPos blkno */ if (!seized && scan->parallel_scan != NULL && !_bt_parallel_seize(scan, &blkno, &lastcurrblkno, false)) { /* whole scan is now done (or another primitive scan required) */ BTScanPosInvalidate(so->currPos); return false; } if (ScanDirectionIsForward(dir)) { /* read blkno, but check for interrupts first */ CHECK_FOR_INTERRUPTS(); so->currPos.buf = _bt_getbuf(rel, blkno, BT_READ); } else { /* read blkno, avoiding race (also checks for interrupts) */ so->currPos.buf = _bt_lock_and_validate_left(rel, &blkno, lastcurrblkno); if (so->currPos.buf == InvalidBuffer) { /* must have been a concurrent deletion of leftmost page */ BTScanPosInvalidate(so->currPos); _bt_parallel_done(scan); return false; } } page = BufferGetPage(so->currPos.buf); opaque = BTPageGetOpaque(page); lastcurrblkno = blkno; if (likely(!P_IGNORE(opaque))) { /* see if there are any matches on this page */ if (ScanDirectionIsForward(dir)) { /* note that this will clear moreRight if we can stop */ if (_bt_readpage(scan, dir, P_FIRSTDATAKEY(opaque), seized)) break; blkno = so->currPos.nextPage; } else { /* note that this will clear moreLeft if we can stop */ if (_bt_readpage(scan, dir, PageGetMaxOffsetNumber(page), seized)) break; blkno = so->currPos.prevPage; } } else { /* _bt_readpage not called, so do all this for ourselves */ if (ScanDirectionIsForward(dir)) blkno = opaque->btpo_next; else blkno = opaque->btpo_prev; if (scan->parallel_scan != NULL) _bt_parallel_release(scan, blkno, lastcurrblkno); } /* no matching tuples on this page */ _bt_relbuf(rel, so->currPos.buf); seized = false; /* released by _bt_readpage (or by us) */ } /* * _bt_readpage succeeded. Drop the lock (and maybe the pin) on * so->currPos.buf in preparation for btgettuple returning tuples. */ Assert(so->currPos.currPage == blkno); Assert(BTScanPosIsPinned(so->currPos)); _bt_drop_lock_and_maybe_pin(rel, so); return true; } /* * _bt_lock_and_validate_left() -- lock caller's left sibling blkno, * recovering from concurrent page splits/page deletions when necessary * * Called during backwards scans, to deal with their unique concurrency rules. * * blkno points to the block number of the page that we expect to move the * scan to. We'll successfully move the scan there when we find that its * right sibling link still points to lastcurrblkno (the page we just read). * Otherwise, we have to figure out which page is the correct one for the scan * to now read the hard way, reasoning about concurrent splits and deletions. * See nbtree/README. * * On return, we have both a pin and a read lock on the returned page, whose * block number will be set in *blkno. Returns InvalidBuffer if there is no * page to the left (no lock or pin is held in that case). * * It is possible for the returned leaf page to be half-dead; caller must * check that condition and step left again when required. */ static Buffer _bt_lock_and_validate_left(Relation rel, BlockNumber *blkno, BlockNumber lastcurrblkno) { BlockNumber origblkno = *blkno; /* detects circular links */ for (;;) { Buffer buf; Page page; BTPageOpaque opaque; int tries; /* check for interrupts while we're not holding any buffer lock */ CHECK_FOR_INTERRUPTS(); buf = _bt_getbuf(rel, *blkno, BT_READ); page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); /* * If this isn't the page we want, walk right till we find what we * want --- but go no more than four hops (an arbitrary limit). If we * don't find the correct page by then, the most likely bet is that * lastcurrblkno got deleted and isn't in the sibling chain at all * anymore, not that its left sibling got split more than four times. * * Note that it is correct to test P_ISDELETED not P_IGNORE here, * because half-dead pages are still in the sibling chain. */ tries = 0; for (;;) { if (likely(!P_ISDELETED(opaque) && opaque->btpo_next == lastcurrblkno)) { /* Found desired page, return it */ return buf; } if (P_RIGHTMOST(opaque) || ++tries > 4) break; /* step right */ *blkno = opaque->btpo_next; buf = _bt_relandgetbuf(rel, buf, *blkno, BT_READ); page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); } /* * Return to the original page (usually the page most recently read by * _bt_readpage, which is passed by caller as lastcurrblkno) to see * what's up with its prev sibling link */ buf = _bt_relandgetbuf(rel, buf, lastcurrblkno, BT_READ); page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); if (P_ISDELETED(opaque)) { /* * It was deleted. Move right to first nondeleted page (there * must be one); that is the page that has acquired the deleted * one's keyspace, so stepping left from it will take us where we * want to be. */ for (;;) { if (P_RIGHTMOST(opaque)) elog(ERROR, "fell off the end of index \"%s\"", RelationGetRelationName(rel)); lastcurrblkno = opaque->btpo_next; buf = _bt_relandgetbuf(rel, buf, lastcurrblkno, BT_READ); page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); if (!P_ISDELETED(opaque)) break; } } else { /* * Original lastcurrblkno wasn't deleted; the explanation had * better be that the page to the left got split or deleted. * Without this check, we risk going into an infinite loop. */ if (opaque->btpo_prev == origblkno) elog(ERROR, "could not find left sibling of block %u in index \"%s\"", lastcurrblkno, RelationGetRelationName(rel)); /* Okay to try again, since left sibling link changed */ } /* * Original lastcurrblkno from caller was concurrently deleted (could * also have been a great many concurrent left sibling page splits). * Found a non-deleted page that should now act as our lastcurrblkno. */ if (P_LEFTMOST(opaque)) { /* New lastcurrblkno has no left sibling (concurrently deleted) */ _bt_relbuf(rel, buf); break; } /* Start from scratch with new lastcurrblkno's blkno/prev link */ *blkno = origblkno = opaque->btpo_prev; _bt_relbuf(rel, buf); } return InvalidBuffer; } /* * _bt_get_endpoint() -- Find the first or last page on a given tree level * * If the index is empty, we will return InvalidBuffer; any other failure * condition causes ereport(). We will not return a dead page. * * The returned buffer is pinned and read-locked. */ Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost) { Buffer buf; Page page; BTPageOpaque opaque; OffsetNumber offnum; BlockNumber blkno; IndexTuple itup; /* * If we are looking for a leaf page, okay to descend from fast root; * otherwise better descend from true root. (There is no point in being * smarter about intermediate levels.) */ if (level == 0) buf = _bt_getroot(rel, NULL, BT_READ); else buf = _bt_gettrueroot(rel); if (!BufferIsValid(buf)) return InvalidBuffer; page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); for (;;) { /* * If we landed on a deleted page, step right to find a live page * (there must be one). Also, if we want the rightmost page, step * right if needed to get to it (this could happen if the page split * since we obtained a pointer to it). */ while (P_IGNORE(opaque) || (rightmost && !P_RIGHTMOST(opaque))) { blkno = opaque->btpo_next; if (blkno == P_NONE) elog(ERROR, "fell off the end of index \"%s\"", RelationGetRelationName(rel)); buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ); page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); } /* Done? */ if (opaque->btpo_level == level) break; if (opaque->btpo_level < level) ereport(ERROR, (errcode(ERRCODE_INDEX_CORRUPTED), errmsg_internal("btree level %u not found in index \"%s\"", level, RelationGetRelationName(rel)))); /* Descend to leftmost or rightmost child page */ if (rightmost) offnum = PageGetMaxOffsetNumber(page); else offnum = P_FIRSTDATAKEY(opaque); if (offnum < 1 || offnum > PageGetMaxOffsetNumber(page)) elog(PANIC, "offnum out of range"); itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); blkno = BTreeTupleGetDownLink(itup); buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ); page = BufferGetPage(buf); opaque = BTPageGetOpaque(page); } return buf; } /* * _bt_endpoint() -- Find the first or last page in the index, and scan * from there to the first key satisfying all the quals. * * This is used by _bt_first() to set up a scan when we've determined * that the scan must start at the beginning or end of the index (for * a forward or backward scan respectively). * * Parallel scan callers must have seized the scan before calling here. * Exit conditions are the same as for _bt_first(). */ static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir) { Relation rel = scan->indexRelation; BTScanOpaque so = (BTScanOpaque) scan->opaque; Page page; BTPageOpaque opaque; OffsetNumber start; Assert(!BTScanPosIsValid(so->currPos)); Assert(!so->needPrimScan); /* * Scan down to the leftmost or rightmost leaf page. This is a simplified * version of _bt_search(). */ so->currPos.buf = _bt_get_endpoint(rel, 0, ScanDirectionIsBackward(dir)); if (!BufferIsValid(so->currPos.buf)) { /* * Empty index. Lock the whole relation, as nothing finer to lock * exists. */ PredicateLockRelation(rel, scan->xs_snapshot); _bt_parallel_done(scan); return false; } page = BufferGetPage(so->currPos.buf); opaque = BTPageGetOpaque(page); Assert(P_ISLEAF(opaque)); if (ScanDirectionIsForward(dir)) { /* There could be dead pages to the left, so not this: */ /* Assert(P_LEFTMOST(opaque)); */ start = P_FIRSTDATAKEY(opaque); } else if (ScanDirectionIsBackward(dir)) { Assert(P_RIGHTMOST(opaque)); start = PageGetMaxOffsetNumber(page); } else { elog(ERROR, "invalid scan direction: %d", (int) dir); start = 0; /* keep compiler quiet */ } /* * Now load data from the first page of the scan. */ if (!_bt_readfirstpage(scan, start, dir)) return false; _bt_returnitem(scan, so); return true; }