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