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