granicus.if.org Git - postgresql/blob - src/backend/access/nbtree/nbtsearch.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nbtsearch.c
   4  *        Search code for postgres btrees.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2016, 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 "miscadmin.h"
  21 #include "pgstat.h"
  22 #include "storage/predicate.h"
  23 #include "utils/lsyscache.h"
  24 #include "utils/rel.h"
  25 #include "utils/tqual.h"
  26
  27
  28 static bool _bt_readpage(IndexScanDesc scan, ScanDirection dir,
  29                          OffsetNumber offnum);
  30 static void _bt_saveitem(BTScanOpaque so, int itemIndex,
  31                          OffsetNumber offnum, IndexTuple itup);
  32 static bool _bt_steppage(IndexScanDesc scan, ScanDirection dir);
  33 static Buffer _bt_walk_left(Relation rel, Buffer buf, Snapshot snapshot);
  34 static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir);
  35 static void _bt_drop_lock_and_maybe_pin(IndexScanDesc scan, BTScanPos sp);
  36
  37
  38 /*
  39  *      _bt_drop_lock_and_maybe_pin()
  40  *
  41  * Unlock the buffer; and if it is safe to release the pin, do that, too.  It
  42  * is safe if the scan is using an MVCC snapshot and the index is WAL-logged.
  43  * This will prevent vacuum from stalling in a blocked state trying to read a
  44  * page when a cursor is sitting on it -- at least in many important cases.
  45  *
  46  * Set the buffer to invalid if the pin is released, since the buffer may be
  47  * re-used.  If we need to go back to this block (for example, to apply
  48  * LP_DEAD hints) we must get a fresh reference to the buffer.  Hopefully it
  49  * will remain in shared memory for as long as it takes to scan the index
  50  * buffer page.
  51  */
  52 static void
  53 _bt_drop_lock_and_maybe_pin(IndexScanDesc scan, BTScanPos sp)
  54 {
  55         LockBuffer(sp->buf, BUFFER_LOCK_UNLOCK);
  56
  57         if (IsMVCCSnapshot(scan->xs_snapshot) &&
  58                 RelationNeedsWAL(scan->indexRelation) &&
  59                 !scan->xs_want_itup)
  60         {
  61                 ReleaseBuffer(sp->buf);
  62                 sp->buf = InvalidBuffer;
  63         }
  64 }
  65
  66
  67 /*
  68  *      _bt_search() -- Search the tree for a particular scankey,
  69  *              or more precisely for the first leaf page it could be on.
  70  *
  71  * The passed scankey must be an insertion-type scankey (see nbtree/README),
  72  * but it can omit the rightmost column(s) of the index.
  73  *
  74  * When nextkey is false (the usual case), we are looking for the first
  75  * item >= scankey.  When nextkey is true, we are looking for the first
  76  * item strictly greater than scankey.
  77  *
  78  * Return value is a stack of parent-page pointers.  *bufP is set to the
  79  * address of the leaf-page buffer, which is read-locked and pinned.
  80  * No locks are held on the parent pages, however!
  81  *
  82  * NOTE that the returned buffer is read-locked regardless of the access
  83  * parameter.  However, access = BT_WRITE will allow an empty root page
  84  * to be created and returned.  When access = BT_READ, an empty index
  85  * will result in *bufP being set to InvalidBuffer.  Also, in BT_WRITE mode,
  86  * any incomplete splits encountered during the search will be finished.
  87  */
  88 BTStack
  89 _bt_search(Relation rel, int keysz, ScanKey scankey, bool nextkey,
  90                    Buffer *bufP, int access)
  91 {
  92         BTStack         stack_in = NULL;
  93
  94         /* Get the root page to start with */
  95         *bufP = _bt_getroot(rel, access);
  96
  97         /* If index is empty and access = BT_READ, no root page is created. */
  98         if (!BufferIsValid(*bufP))
  99         {
 100                 return (BTStack) NULL;
 101         }
 102
 103         /* Loop iterates once per level descended in the tree */
 104         for (;;)
 105         {
 106                 Page            page;
 107                 BTPageOpaque opaque;
 108                 OffsetNumber offnum;
 109                 ItemId          itemid;
 110                 IndexTuple      itup;
 111                 BlockNumber blkno;
 112                 BlockNumber par_blkno;
 113                 BTStack         new_stack;
 114
 115                 /*
 116                  * Race -- the page we just grabbed may have split since we read its
 117                  * pointer in the parent (or metapage).  If it has, we may need to
 118                  * move right to its new sibling.  Do that.
 119                  *
 120                  * In write-mode, allow _bt_moveright to finish any incomplete splits
 121                  * along the way.  Strictly speaking, we'd only need to finish an
 122                  * incomplete split on the leaf page we're about to insert to, not on
 123                  * any of the upper levels (they are taken care of in _bt_getstackbuf,
 124                  * if the leaf page is split and we insert to the parent page).  But
 125                  * this is a good opportunity to finish splits of internal pages too.
 126                  */
 127                 *bufP = _bt_moveright(rel, *bufP, keysz, scankey, nextkey,
 128                                                           (access == BT_WRITE), stack_in,
 129                                                           BT_READ);
 130
 131                 /* if this is a leaf page, we're done */
 132                 page = BufferGetPage(*bufP, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
 133                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 134                 if (P_ISLEAF(opaque))
 135                         break;
 136
 137                 /*
 138                  * Find the appropriate item on the internal page, and get the child
 139                  * page that it points to.
 140                  */
 141                 offnum = _bt_binsrch(rel, *bufP, keysz, scankey, nextkey);
 142                 itemid = PageGetItemId(page, offnum);
 143                 itup = (IndexTuple) PageGetItem(page, itemid);
 144                 blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
 145                 par_blkno = BufferGetBlockNumber(*bufP);
 146
 147                 /*
 148                  * We need to save the location of the index entry we chose in the
 149                  * parent page on a stack. In case we split the tree, we'll use the
 150                  * stack to work back up to the parent page.  We also save the actual
 151                  * downlink (TID) to uniquely identify the index entry, in case it
 152                  * moves right while we're working lower in the tree.  See the paper
 153                  * by Lehman and Yao for how this is detected and handled. (We use the
 154                  * child link to disambiguate duplicate keys in the index -- Lehman
 155                  * and Yao disallow duplicate keys.)
 156                  */
 157                 new_stack = (BTStack) palloc(sizeof(BTStackData));
 158                 new_stack->bts_blkno = par_blkno;
 159                 new_stack->bts_offset = offnum;
 160                 memcpy(&new_stack->bts_btentry, itup, sizeof(IndexTupleData));
 161                 new_stack->bts_parent = stack_in;
 162
 163                 /* drop the read lock on the parent page, acquire one on the child */
 164                 *bufP = _bt_relandgetbuf(rel, *bufP, blkno, BT_READ);
 165
 166                 /* okay, all set to move down a level */
 167                 stack_in = new_stack;
 168         }
 169
 170         return stack_in;
 171 }
 172
 173 /*
 174  *      _bt_moveright() -- move right in the btree if necessary.
 175  *
 176  * When we follow a pointer to reach a page, it is possible that
 177  * the page has changed in the meanwhile.  If this happens, we're
 178  * guaranteed that the page has "split right" -- that is, that any
 179  * data that appeared on the page originally is either on the page
 180  * or strictly to the right of it.
 181  *
 182  * This routine decides whether or not we need to move right in the
 183  * tree by examining the high key entry on the page.  If that entry
 184  * is strictly less than the scankey, or <= the scankey in the nextkey=true
 185  * case, then we followed the wrong link and we need to move right.
 186  *
 187  * The passed scankey must be an insertion-type scankey (see nbtree/README),
 188  * but it can omit the rightmost column(s) of the index.
 189  *
 190  * When nextkey is false (the usual case), we are looking for the first
 191  * item >= scankey.  When nextkey is true, we are looking for the first
 192  * item strictly greater than scankey.
 193  *
 194  * If forupdate is true, we will attempt to finish any incomplete splits
 195  * that we encounter.  This is required when locking a target page for an
 196  * insertion, because we don't allow inserting on a page before the split
 197  * is completed.  'stack' is only used if forupdate is true.
 198  *
 199  * On entry, we have the buffer pinned and a lock of the type specified by
 200  * 'access'.  If we move right, we release the buffer and lock and acquire
 201  * the same on the right sibling.  Return value is the buffer we stop at.
 202  */
 203 Buffer
 204 _bt_moveright(Relation rel,
 205                           Buffer buf,
 206                           int keysz,
 207                           ScanKey scankey,
 208                           bool nextkey,
 209                           bool forupdate,
 210                           BTStack stack,
 211                           int access)
 212 {
 213         Page            page;
 214         BTPageOpaque opaque;
 215         int32           cmpval;
 216
 217         /*
 218          * When nextkey = false (normal case): if the scan key that brought us to
 219          * this page is > the high key stored on the page, then the page has split
 220          * and we need to move right.  (If the scan key is equal to the high key,
 221          * we might or might not need to move right; have to scan the page first
 222          * anyway.)
 223          *
 224          * When nextkey = true: move right if the scan key is >= page's high key.
 225          *
 226          * The page could even have split more than once, so scan as far as
 227          * needed.
 228          *
 229          * We also have to move right if we followed a link that brought us to a
 230          * dead page.
 231          */
 232         cmpval = nextkey ? 0 : 1;
 233
 234         for (;;)
 235         {
 236                 page = BufferGetPage(buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
 237                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 238
 239                 if (P_RIGHTMOST(opaque))
 240                         break;
 241
 242                 /*
 243                  * Finish any incomplete splits we encounter along the way.
 244                  */
 245                 if (forupdate && P_INCOMPLETE_SPLIT(opaque))
 246                 {
 247                         BlockNumber blkno = BufferGetBlockNumber(buf);
 248
 249                         /* upgrade our lock if necessary */
 250                         if (access == BT_READ)
 251                         {
 252                                 LockBuffer(buf, BUFFER_LOCK_UNLOCK);
 253                                 LockBuffer(buf, BT_WRITE);
 254                         }
 255
 256                         if (P_INCOMPLETE_SPLIT(opaque))
 257                                 _bt_finish_split(rel, buf, stack);
 258                         else
 259                                 _bt_relbuf(rel, buf);
 260
 261                         /* re-acquire the lock in the right mode, and re-check */
 262                         buf = _bt_getbuf(rel, blkno, access);
 263                         continue;
 264                 }
 265
 266                 if (P_IGNORE(opaque) || _bt_compare(rel, keysz, scankey, page, P_HIKEY) >= cmpval)
 267                 {
 268                         /* step right one page */
 269                         buf = _bt_relandgetbuf(rel, buf, opaque->btpo_next, access);
 270                         continue;
 271                 }
 272                 else
 273                         break;
 274         }
 275
 276         if (P_IGNORE(opaque))
 277                 elog(ERROR, "fell off the end of index \"%s\"",
 278                          RelationGetRelationName(rel));
 279
 280         return buf;
 281 }
 282
 283 /*
 284  *      _bt_binsrch() -- Do a binary search for a key on a particular page.
 285  *
 286  * The passed scankey must be an insertion-type scankey (see nbtree/README),
 287  * but it can omit the rightmost column(s) of the index.
 288  *
 289  * When nextkey is false (the usual case), we are looking for the first
 290  * item >= scankey.  When nextkey is true, we are looking for the first
 291  * item strictly greater than scankey.
 292  *
 293  * On a leaf page, _bt_binsrch() returns the OffsetNumber of the first
 294  * key >= given scankey, or > scankey if nextkey is true.  (NOTE: in
 295  * particular, this means it is possible to return a value 1 greater than the
 296  * number of keys on the page, if the scankey is > all keys on the page.)
 297  *
 298  * On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber
 299  * of the last key < given scankey, or last key <= given scankey if nextkey
 300  * is true.  (Since _bt_compare treats the first data key of such a page as
 301  * minus infinity, there will be at least one key < scankey, so the result
 302  * always points at one of the keys on the page.)  This key indicates the
 303  * right place to descend to be sure we find all leaf keys >= given scankey
 304  * (or leaf keys > given scankey when nextkey is true).
 305  *
 306  * This procedure is not responsible for walking right, it just examines
 307  * the given page.  _bt_binsrch() has no lock or refcount side effects
 308  * on the buffer.
 309  */
 310 OffsetNumber
 311 _bt_binsrch(Relation rel,
 312                         Buffer buf,
 313                         int keysz,
 314                         ScanKey scankey,
 315                         bool nextkey)
 316 {
 317         Page            page;
 318         BTPageOpaque opaque;
 319         OffsetNumber low,
 320                                 high;
 321         int32           result,
 322                                 cmpval;
 323
 324         page = BufferGetPage(buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
 325         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 326
 327         low = P_FIRSTDATAKEY(opaque);
 328         high = PageGetMaxOffsetNumber(page);
 329
 330         /*
 331          * If there are no keys on the page, return the first available slot. Note
 332          * this covers two cases: the page is really empty (no keys), or it
 333          * contains only a high key.  The latter case is possible after vacuuming.
 334          * This can never happen on an internal page, however, since they are
 335          * never empty (an internal page must have children).
 336          */
 337         if (high < low)
 338                 return low;
 339
 340         /*
 341          * Binary search to find the first key on the page >= scan key, or first
 342          * key > scankey when nextkey is true.
 343          *
 344          * For nextkey=false (cmpval=1), the loop invariant is: all slots before
 345          * 'low' are < scan key, all slots at or after 'high' are >= scan key.
 346          *
 347          * For nextkey=true (cmpval=0), the loop invariant is: all slots before
 348          * 'low' are <= scan key, all slots at or after 'high' are > scan key.
 349          *
 350          * We can fall out when high == low.
 351          */
 352         high++;                                         /* establish the loop invariant for high */
 353
 354         cmpval = nextkey ? 0 : 1;       /* select comparison value */
 355
 356         while (high > low)
 357         {
 358                 OffsetNumber mid = low + ((high - low) / 2);
 359
 360                 /* We have low <= mid < high, so mid points at a real slot */
 361
 362                 result = _bt_compare(rel, keysz, scankey, page, mid);
 363
 364                 if (result >= cmpval)
 365                         low = mid + 1;
 366                 else
 367                         high = mid;
 368         }
 369
 370         /*
 371          * At this point we have high == low, but be careful: they could point
 372          * past the last slot on the page.
 373          *
 374          * On a leaf page, we always return the first key >= scan key (resp. >
 375          * scan key), which could be the last slot + 1.
 376          */
 377         if (P_ISLEAF(opaque))
 378                 return low;
 379
 380         /*
 381          * On a non-leaf page, return the last key < scan key (resp. <= scan key).
 382          * There must be one if _bt_compare() is playing by the rules.
 383          */
 384         Assert(low > P_FIRSTDATAKEY(opaque));
 385
 386         return OffsetNumberPrev(low);
 387 }
 388
 389 /*----------
 390  *      _bt_compare() -- Compare scankey to a particular tuple on the page.
 391  *
 392  * The passed scankey must be an insertion-type scankey (see nbtree/README),
 393  * but it can omit the rightmost column(s) of the index.
 394  *
 395  *      keysz: number of key conditions to be checked (might be less than the
 396  *              number of index columns!)
 397  *      page/offnum: location of btree item to be compared to.
 398  *
 399  *              This routine returns:
 400  *                      <0 if scankey < tuple at offnum;
 401  *                       0 if scankey == tuple at offnum;
 402  *                      >0 if scankey > tuple at offnum.
 403  *              NULLs in the keys are treated as sortable values.  Therefore
 404  *              "equality" does not necessarily mean that the item should be
 405  *              returned to the caller as a matching key!
 406  *
 407  * CRUCIAL NOTE: on a non-leaf page, the first data key is assumed to be
 408  * "minus infinity": this routine will always claim it is less than the
 409  * scankey.  The actual key value stored (if any, which there probably isn't)
 410  * does not matter.  This convention allows us to implement the Lehman and
 411  * Yao convention that the first down-link pointer is before the first key.
 412  * See backend/access/nbtree/README for details.
 413  *----------
 414  */
 415 int32
 416 _bt_compare(Relation rel,
 417                         int keysz,
 418                         ScanKey scankey,
 419                         Page page,
 420                         OffsetNumber offnum)
 421 {
 422         TupleDesc       itupdesc = RelationGetDescr(rel);
 423         BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 424         IndexTuple      itup;
 425         int                     i;
 426
 427         /*
 428          * Force result ">" if target item is first data item on an internal page
 429          * --- see NOTE above.
 430          */
 431         if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque))
 432                 return 1;
 433
 434         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
 435
 436         /*
 437          * The scan key is set up with the attribute number associated with each
 438          * term in the key.  It is important that, if the index is multi-key, the
 439          * scan contain the first k key attributes, and that they be in order.  If
 440          * you think about how multi-key ordering works, you'll understand why
 441          * this is.
 442          *
 443          * We don't test for violation of this condition here, however.  The
 444          * initial setup for the index scan had better have gotten it right (see
 445          * _bt_first).
 446          */
 447
 448         for (i = 1; i <= keysz; i++)
 449         {
 450                 Datum           datum;
 451                 bool            isNull;
 452                 int32           result;
 453
 454                 datum = index_getattr(itup, scankey->sk_attno, itupdesc, &isNull);
 455
 456                 /* see comments about NULLs handling in btbuild */
 457                 if (scankey->sk_flags & SK_ISNULL)              /* key is NULL */
 458                 {
 459                         if (isNull)
 460                                 result = 0;             /* NULL "=" NULL */
 461                         else if (scankey->sk_flags & SK_BT_NULLS_FIRST)
 462                                 result = -1;    /* NULL "<" NOT_NULL */
 463                         else
 464                                 result = 1;             /* NULL ">" NOT_NULL */
 465                 }
 466                 else if (isNull)                /* key is NOT_NULL and item is NULL */
 467                 {
 468                         if (scankey->sk_flags & SK_BT_NULLS_FIRST)
 469                                 result = 1;             /* NOT_NULL ">" NULL */
 470                         else
 471                                 result = -1;    /* NOT_NULL "<" NULL */
 472                 }
 473                 else
 474                 {
 475                         /*
 476                          * The sk_func needs to be passed the index value as left arg and
 477                          * the sk_argument as right arg (they might be of different
 478                          * types).  Since it is convenient for callers to think of
 479                          * _bt_compare as comparing the scankey to the index item, we have
 480                          * to flip the sign of the comparison result.  (Unless it's a DESC
 481                          * column, in which case we *don't* flip the sign.)
 482                          */
 483                         result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func,
 484                                                                                                          scankey->sk_collation,
 485                                                                                                          datum,
 486                                                                                                          scankey->sk_argument));
 487
 488                         if (!(scankey->sk_flags & SK_BT_DESC))
 489                                 result = -result;
 490                 }
 491
 492                 /* if the keys are unequal, return the difference */
 493                 if (result != 0)
 494                         return result;
 495
 496                 scankey++;
 497         }
 498
 499         /* if we get here, the keys are equal */
 500         return 0;
 501 }
 502
 503 /*
 504  *      _bt_first() -- Find the first item in a scan.
 505  *
 506  *              We need to be clever about the direction of scan, the search
 507  *              conditions, and the tree ordering.  We find the first item (or,
 508  *              if backwards scan, the last item) in the tree that satisfies the
 509  *              qualifications in the scan key.  On success exit, the page containing
 510  *              the current index tuple is pinned but not locked, and data about
 511  *              the matching tuple(s) on the page has been loaded into so->currPos.
 512  *              scan->xs_ctup.t_self is set to the heap TID of the current tuple,
 513  *              and if requested, scan->xs_itup points to a copy of the index tuple.
 514  *
 515  * If there are no matching items in the index, we return FALSE, with no
 516  * pins or locks held.
 517  *
 518  * Note that scan->keyData[], and the so->keyData[] scankey built from it,
 519  * are both search-type scankeys (see nbtree/README for more about this).
 520  * Within this routine, we build a temporary insertion-type scankey to use
 521  * in locating the scan start position.
 522  */
 523 bool
 524 _bt_first(IndexScanDesc scan, ScanDirection dir)
 525 {
 526         Relation        rel = scan->indexRelation;
 527         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 528         Buffer          buf;
 529         BTStack         stack;
 530         OffsetNumber offnum;
 531         StrategyNumber strat;
 532         bool            nextkey;
 533         bool            goback;
 534         ScanKey         startKeys[INDEX_MAX_KEYS];
 535         ScanKeyData scankeys[INDEX_MAX_KEYS];
 536         ScanKeyData notnullkeys[INDEX_MAX_KEYS];
 537         int                     keysCount = 0;
 538         int                     i;
 539         StrategyNumber strat_total;
 540         BTScanPosItem *currItem;
 541
 542         Assert(!BTScanPosIsValid(so->currPos));
 543
 544         pgstat_count_index_scan(rel);
 545
 546         /*
 547          * Examine the scan keys and eliminate any redundant keys; also mark the
 548          * keys that must be matched to continue the scan.
 549          */
 550         _bt_preprocess_keys(scan);
 551
 552         /*
 553          * Quit now if _bt_preprocess_keys() discovered that the scan keys can
 554          * never be satisfied (eg, x == 1 AND x > 2).
 555          */
 556         if (!so->qual_ok)
 557                 return false;
 558
 559         /*----------
 560          * Examine the scan keys to discover where we need to start the scan.
 561          *
 562          * We want to identify the keys that can be used as starting boundaries;
 563          * these are =, >, or >= keys for a forward scan or =, <, <= keys for
 564          * a backwards scan.  We can use keys for multiple attributes so long as
 565          * the prior attributes had only =, >= (resp. =, <=) keys.  Once we accept
 566          * a > or < boundary or find an attribute with no boundary (which can be
 567          * thought of as the same as "> -infinity"), we can't use keys for any
 568          * attributes to its right, because it would break our simplistic notion
 569          * of what initial positioning strategy to use.
 570          *
 571          * When the scan keys include cross-type operators, _bt_preprocess_keys
 572          * may not be able to eliminate redundant keys; in such cases we will
 573          * arbitrarily pick a usable one for each attribute.  This is correct
 574          * but possibly not optimal behavior.  (For example, with keys like
 575          * "x >= 4 AND x >= 5" we would elect to scan starting at x=4 when
 576          * x=5 would be more efficient.)  Since the situation only arises given
 577          * a poorly-worded query plus an incomplete opfamily, live with it.
 578          *
 579          * When both equality and inequality keys appear for a single attribute
 580          * (again, only possible when cross-type operators appear), we *must*
 581          * select one of the equality keys for the starting point, because
 582          * _bt_checkkeys() will stop the scan as soon as an equality qual fails.
 583          * For example, if we have keys like "x >= 4 AND x = 10" and we elect to
 584          * start at x=4, we will fail and stop before reaching x=10.  If multiple
 585          * equality quals survive preprocessing, however, it doesn't matter which
 586          * one we use --- by definition, they are either redundant or
 587          * contradictory.
 588          *
 589          * Any regular (not SK_SEARCHNULL) key implies a NOT NULL qualifier.
 590          * If the index stores nulls at the end of the index we'll be starting
 591          * from, and we have no boundary key for the column (which means the key
 592          * we deduced NOT NULL from is an inequality key that constrains the other
 593          * end of the index), then we cons up an explicit SK_SEARCHNOTNULL key to
 594          * use as a boundary key.  If we didn't do this, we might find ourselves
 595          * traversing a lot of null entries at the start of the scan.
 596          *
 597          * In this loop, row-comparison keys are treated the same as keys on their
 598          * first (leftmost) columns.  We'll add on lower-order columns of the row
 599          * comparison below, if possible.
 600          *
 601          * The selected scan keys (at most one per index column) are remembered by
 602          * storing their addresses into the local startKeys[] array.
 603          *----------
 604          */
 605         strat_total = BTEqualStrategyNumber;
 606         if (so->numberOfKeys > 0)
 607         {
 608                 AttrNumber      curattr;
 609                 ScanKey         chosen;
 610                 ScanKey         impliesNN;
 611                 ScanKey         cur;
 612
 613                 /*
 614                  * chosen is the so-far-chosen key for the current attribute, if any.
 615                  * We don't cast the decision in stone until we reach keys for the
 616                  * next attribute.
 617                  */
 618                 curattr = 1;
 619                 chosen = NULL;
 620                 /* Also remember any scankey that implies a NOT NULL constraint */
 621                 impliesNN = NULL;
 622
 623                 /*
 624                  * Loop iterates from 0 to numberOfKeys inclusive; we use the last
 625                  * pass to handle after-last-key processing.  Actual exit from the
 626                  * loop is at one of the "break" statements below.
 627                  */
 628                 for (cur = so->keyData, i = 0;; cur++, i++)
 629                 {
 630                         if (i >= so->numberOfKeys || cur->sk_attno != curattr)
 631                         {
 632                                 /*
 633                                  * Done looking at keys for curattr.  If we didn't find a
 634                                  * usable boundary key, see if we can deduce a NOT NULL key.
 635                                  */
 636                                 if (chosen == NULL && impliesNN != NULL &&
 637                                         ((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ?
 638                                          ScanDirectionIsForward(dir) :
 639                                          ScanDirectionIsBackward(dir)))
 640                                 {
 641                                         /* Yes, so build the key in notnullkeys[keysCount] */
 642                                         chosen = &notnullkeys[keysCount];
 643                                         ScanKeyEntryInitialize(chosen,
 644                                                                                    (SK_SEARCHNOTNULL | SK_ISNULL |
 645                                                                                         (impliesNN->sk_flags &
 646                                                                                   (SK_BT_DESC | SK_BT_NULLS_FIRST))),
 647                                                                                    curattr,
 648                                                                  ((impliesNN->sk_flags & SK_BT_NULLS_FIRST) ?
 649                                                                   BTGreaterStrategyNumber :
 650                                                                   BTLessStrategyNumber),
 651                                                                                    InvalidOid,
 652                                                                                    InvalidOid,
 653                                                                                    InvalidOid,
 654                                                                                    (Datum) 0);
 655                                 }
 656
 657                                 /*
 658                                  * If we still didn't find a usable boundary key, quit; else
 659                                  * save the boundary key pointer in startKeys.
 660                                  */
 661                                 if (chosen == NULL)
 662                                         break;
 663                                 startKeys[keysCount++] = chosen;
 664
 665                                 /*
 666                                  * Adjust strat_total, and quit if we have stored a > or <
 667                                  * key.
 668                                  */
 669                                 strat = chosen->sk_strategy;
 670                                 if (strat != BTEqualStrategyNumber)
 671                                 {
 672                                         strat_total = strat;
 673                                         if (strat == BTGreaterStrategyNumber ||
 674                                                 strat == BTLessStrategyNumber)
 675                                                 break;
 676                                 }
 677
 678                                 /*
 679                                  * Done if that was the last attribute, or if next key is not
 680                                  * in sequence (implying no boundary key is available for the
 681                                  * next attribute).
 682                                  */
 683                                 if (i >= so->numberOfKeys ||
 684                                         cur->sk_attno != curattr + 1)
 685                                         break;
 686
 687                                 /*
 688                                  * Reset for next attr.
 689                                  */
 690                                 curattr = cur->sk_attno;
 691                                 chosen = NULL;
 692                                 impliesNN = NULL;
 693                         }
 694
 695                         /*
 696                          * Can we use this key as a starting boundary for this attr?
 697                          *
 698                          * If not, does it imply a NOT NULL constraint?  (Because
 699                          * SK_SEARCHNULL keys are always assigned BTEqualStrategyNumber,
 700                          * *any* inequality key works for that; we need not test.)
 701                          */
 702                         switch (cur->sk_strategy)
 703                         {
 704                                 case BTLessStrategyNumber:
 705                                 case BTLessEqualStrategyNumber:
 706                                         if (chosen == NULL)
 707                                         {
 708                                                 if (ScanDirectionIsBackward(dir))
 709                                                         chosen = cur;
 710                                                 else
 711                                                         impliesNN = cur;
 712                                         }
 713                                         break;
 714                                 case BTEqualStrategyNumber:
 715                                         /* override any non-equality choice */
 716                                         chosen = cur;
 717                                         break;
 718                                 case BTGreaterEqualStrategyNumber:
 719                                 case BTGreaterStrategyNumber:
 720                                         if (chosen == NULL)
 721                                         {
 722                                                 if (ScanDirectionIsForward(dir))
 723                                                         chosen = cur;
 724                                                 else
 725                                                         impliesNN = cur;
 726                                         }
 727                                         break;
 728                         }
 729                 }
 730         }
 731
 732         /*
 733          * If we found no usable boundary keys, we have to start from one end of
 734          * the tree.  Walk down that edge to the first or last key, and scan from
 735          * there.
 736          */
 737         if (keysCount == 0)
 738                 return _bt_endpoint(scan, dir);
 739
 740         /*
 741          * We want to start the scan somewhere within the index.  Set up an
 742          * insertion scankey we can use to search for the boundary point we
 743          * identified above.  The insertion scankey is built in the local
 744          * scankeys[] array, using the keys identified by startKeys[].
 745          */
 746         Assert(keysCount <= INDEX_MAX_KEYS);
 747         for (i = 0; i < keysCount; i++)
 748         {
 749                 ScanKey         cur = startKeys[i];
 750
 751                 Assert(cur->sk_attno == i + 1);
 752
 753                 if (cur->sk_flags & SK_ROW_HEADER)
 754                 {
 755                         /*
 756                          * Row comparison header: look to the first row member instead.
 757                          *
 758                          * The member scankeys are already in insertion format (ie, they
 759                          * have sk_func = 3-way-comparison function), but we have to watch
 760                          * out for nulls, which _bt_preprocess_keys didn't check. A null
 761                          * in the first row member makes the condition unmatchable, just
 762                          * like qual_ok = false.
 763                          */
 764                         ScanKey         subkey = (ScanKey) DatumGetPointer(cur->sk_argument);
 765
 766                         Assert(subkey->sk_flags & SK_ROW_MEMBER);
 767                         if (subkey->sk_flags & SK_ISNULL)
 768                                 return false;
 769                         memcpy(scankeys + i, subkey, sizeof(ScanKeyData));
 770
 771                         /*
 772                          * If the row comparison is the last positioning key we accepted,
 773                          * try to add additional keys from the lower-order row members.
 774                          * (If we accepted independent conditions on additional index
 775                          * columns, we use those instead --- doesn't seem worth trying to
 776                          * determine which is more restrictive.)  Note that this is OK
 777                          * even if the row comparison is of ">" or "<" type, because the
 778                          * condition applied to all but the last row member is effectively
 779                          * ">=" or "<=", and so the extra keys don't break the positioning
 780                          * scheme.  But, by the same token, if we aren't able to use all
 781                          * the row members, then the part of the row comparison that we
 782                          * did use has to be treated as just a ">=" or "<=" condition, and
 783                          * so we'd better adjust strat_total accordingly.
 784                          */
 785                         if (i == keysCount - 1)
 786                         {
 787                                 bool            used_all_subkeys = false;
 788
 789                                 Assert(!(subkey->sk_flags & SK_ROW_END));
 790                                 for (;;)
 791                                 {
 792                                         subkey++;
 793                                         Assert(subkey->sk_flags & SK_ROW_MEMBER);
 794                                         if (subkey->sk_attno != keysCount + 1)
 795                                                 break;  /* out-of-sequence, can't use it */
 796                                         if (subkey->sk_strategy != cur->sk_strategy)
 797                                                 break;  /* wrong direction, can't use it */
 798                                         if (subkey->sk_flags & SK_ISNULL)
 799                                                 break;  /* can't use null keys */
 800                                         Assert(keysCount < INDEX_MAX_KEYS);
 801                                         memcpy(scankeys + keysCount, subkey, sizeof(ScanKeyData));
 802                                         keysCount++;
 803                                         if (subkey->sk_flags & SK_ROW_END)
 804                                         {
 805                                                 used_all_subkeys = true;
 806                                                 break;
 807                                         }
 808                                 }
 809                                 if (!used_all_subkeys)
 810                                 {
 811                                         switch (strat_total)
 812                                         {
 813                                                 case BTLessStrategyNumber:
 814                                                         strat_total = BTLessEqualStrategyNumber;
 815                                                         break;
 816                                                 case BTGreaterStrategyNumber:
 817                                                         strat_total = BTGreaterEqualStrategyNumber;
 818                                                         break;
 819                                         }
 820                                 }
 821                                 break;                  /* done with outer loop */
 822                         }
 823                 }
 824                 else
 825                 {
 826                         /*
 827                          * Ordinary comparison key.  Transform the search-style scan key
 828                          * to an insertion scan key by replacing the sk_func with the
 829                          * appropriate btree comparison function.
 830                          *
 831                          * If scankey operator is not a cross-type comparison, we can use
 832                          * the cached comparison function; otherwise gotta look it up in
 833                          * the catalogs.  (That can't lead to infinite recursion, since no
 834                          * indexscan initiated by syscache lookup will use cross-data-type
 835                          * operators.)
 836                          *
 837                          * We support the convention that sk_subtype == InvalidOid means
 838                          * the opclass input type; this is a hack to simplify life for
 839                          * ScanKeyInit().
 840                          */
 841                         if (cur->sk_subtype == rel->rd_opcintype[i] ||
 842                                 cur->sk_subtype == InvalidOid)
 843                         {
 844                                 FmgrInfo   *procinfo;
 845
 846                                 procinfo = index_getprocinfo(rel, cur->sk_attno, BTORDER_PROC);
 847                                 ScanKeyEntryInitializeWithInfo(scankeys + i,
 848                                                                                            cur->sk_flags,
 849                                                                                            cur->sk_attno,
 850                                                                                            InvalidStrategy,
 851                                                                                            cur->sk_subtype,
 852                                                                                            cur->sk_collation,
 853                                                                                            procinfo,
 854                                                                                            cur->sk_argument);
 855                         }
 856                         else
 857                         {
 858                                 RegProcedure cmp_proc;
 859
 860                                 cmp_proc = get_opfamily_proc(rel->rd_opfamily[i],
 861                                                                                          rel->rd_opcintype[i],
 862                                                                                          cur->sk_subtype,
 863                                                                                          BTORDER_PROC);
 864                                 if (!RegProcedureIsValid(cmp_proc))
 865                                         elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
 866                                                  BTORDER_PROC, rel->rd_opcintype[i], cur->sk_subtype,
 867                                                  cur->sk_attno, RelationGetRelationName(rel));
 868                                 ScanKeyEntryInitialize(scankeys + i,
 869                                                                            cur->sk_flags,
 870                                                                            cur->sk_attno,
 871                                                                            InvalidStrategy,
 872                                                                            cur->sk_subtype,
 873                                                                            cur->sk_collation,
 874                                                                            cmp_proc,
 875                                                                            cur->sk_argument);
 876                         }
 877                 }
 878         }
 879
 880         /*----------
 881          * Examine the selected initial-positioning strategy to determine exactly
 882          * where we need to start the scan, and set flag variables to control the
 883          * code below.
 884          *
 885          * If nextkey = false, _bt_search and _bt_binsrch will locate the first
 886          * item >= scan key.  If nextkey = true, they will locate the first
 887          * item > scan key.
 888          *
 889          * If goback = true, we will then step back one item, while if
 890          * goback = false, we will start the scan on the located item.
 891          *----------
 892          */
 893         switch (strat_total)
 894         {
 895                 case BTLessStrategyNumber:
 896
 897                         /*
 898                          * Find first item >= scankey, then back up one to arrive at last
 899                          * item < scankey.  (Note: this positioning strategy is only used
 900                          * for a backward scan, so that is always the correct starting
 901                          * position.)
 902                          */
 903                         nextkey = false;
 904                         goback = true;
 905                         break;
 906
 907                 case BTLessEqualStrategyNumber:
 908
 909                         /*
 910                          * Find first item > scankey, then back up one to arrive at last
 911                          * item <= scankey.  (Note: this positioning strategy is only used
 912                          * for a backward scan, so that is always the correct starting
 913                          * position.)
 914                          */
 915                         nextkey = true;
 916                         goback = true;
 917                         break;
 918
 919                 case BTEqualStrategyNumber:
 920
 921                         /*
 922                          * If a backward scan was specified, need to start with last equal
 923                          * item not first one.
 924                          */
 925                         if (ScanDirectionIsBackward(dir))
 926                         {
 927                                 /*
 928                                  * This is the same as the <= strategy.  We will check at the
 929                                  * end whether the found item is actually =.
 930                                  */
 931                                 nextkey = true;
 932                                 goback = true;
 933                         }
 934                         else
 935                         {
 936                                 /*
 937                                  * This is the same as the >= strategy.  We will check at the
 938                                  * end whether the found item is actually =.
 939                                  */
 940                                 nextkey = false;
 941                                 goback = false;
 942                         }
 943                         break;
 944
 945                 case BTGreaterEqualStrategyNumber:
 946
 947                         /*
 948                          * Find first item >= scankey.  (This is only used for forward
 949                          * scans.)
 950                          */
 951                         nextkey = false;
 952                         goback = false;
 953                         break;
 954
 955                 case BTGreaterStrategyNumber:
 956
 957                         /*
 958                          * Find first item > scankey.  (This is only used for forward
 959                          * scans.)
 960                          */
 961                         nextkey = true;
 962                         goback = false;
 963                         break;
 964
 965                 default:
 966                         /* can't get here, but keep compiler quiet */
 967                         elog(ERROR, "unrecognized strat_total: %d", (int) strat_total);
 968                         return false;
 969         }
 970
 971         /*
 972          * Use the manufactured insertion scan key to descend the tree and
 973          * position ourselves on the target leaf page.
 974          */
 975         stack = _bt_search(rel, keysCount, scankeys, nextkey, &buf, BT_READ);
 976
 977         /* don't need to keep the stack around... */
 978         _bt_freestack(stack);
 979
 980         if (!BufferIsValid(buf))
 981         {
 982                 /*
 983                  * We only get here if the index is completely empty. Lock relation
 984                  * because nothing finer to lock exists.
 985                  */
 986                 PredicateLockRelation(rel, scan->xs_snapshot);
 987                 return false;
 988         }
 989         else
 990                 PredicateLockPage(rel, BufferGetBlockNumber(buf),
 991                                                   scan->xs_snapshot);
 992
 993         /* initialize moreLeft/moreRight appropriately for scan direction */
 994         if (ScanDirectionIsForward(dir))
 995         {
 996                 so->currPos.moreLeft = false;
 997                 so->currPos.moreRight = true;
 998         }
 999         else
1000         {
1001                 so->currPos.moreLeft = true;
1002                 so->currPos.moreRight = false;
1003         }
1004         so->numKilled = 0;                      /* just paranoia */
1005         so->markItemIndex = -1;         /* ditto */
1006
1007         /* position to the precise item on the page */
1008         offnum = _bt_binsrch(rel, buf, keysCount, scankeys, nextkey);
1009
1010         /*
1011          * If nextkey = false, we are positioned at the first item >= scan key, or
1012          * possibly at the end of a page on which all the existing items are less
1013          * than the scan key and we know that everything on later pages is greater
1014          * than or equal to scan key.
1015          *
1016          * If nextkey = true, we are positioned at the first item > scan key, or
1017          * possibly at the end of a page on which all the existing items are less
1018          * than or equal to the scan key and we know that everything on later
1019          * pages is greater than scan key.
1020          *
1021          * The actually desired starting point is either this item or the prior
1022          * one, or in the end-of-page case it's the first item on the next page or
1023          * the last item on this page.  Adjust the starting offset if needed. (If
1024          * this results in an offset before the first item or after the last one,
1025          * _bt_readpage will report no items found, and then we'll step to the
1026          * next page as needed.)
1027          */
1028         if (goback)
1029                 offnum = OffsetNumberPrev(offnum);
1030
1031         /* remember which buffer we have pinned, if any */
1032         Assert(!BTScanPosIsValid(so->currPos));
1033         so->currPos.buf = buf;
1034
1035         /*
1036          * Now load data from the first page of the scan.
1037          */
1038         if (!_bt_readpage(scan, dir, offnum))
1039         {
1040                 /*
1041                  * There's no actually-matching data on this page.  Try to advance to
1042                  * the next page.  Return false if there's no matching data at all.
1043                  */
1044                 LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
1045                 if (!_bt_steppage(scan, dir))
1046                         return false;
1047         }
1048         else
1049         {
1050                 /* Drop the lock, and maybe the pin, on the current page */
1051                 _bt_drop_lock_and_maybe_pin(scan, &so->currPos);
1052         }
1053
1054         /* OK, itemIndex says what to return */
1055         currItem = &so->currPos.items[so->currPos.itemIndex];
1056         scan->xs_ctup.t_self = currItem->heapTid;
1057         if (scan->xs_want_itup)
1058                 scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);
1059
1060         return true;
1061 }
1062
1063 /*
1064  *      _bt_next() -- Get the next item in a scan.
1065  *
1066  *              On entry, so->currPos describes the current page, which may be pinned
1067  *              but is not locked, and so->currPos.itemIndex identifies which item was
1068  *              previously returned.
1069  *
1070  *              On successful exit, scan->xs_ctup.t_self is set to the TID of the
1071  *              next heap tuple, and if requested, scan->xs_itup points to a copy of
1072  *              the index tuple.  so->currPos is updated as needed.
1073  *
1074  *              On failure exit (no more tuples), we release pin and set
1075  *              so->currPos.buf to InvalidBuffer.
1076  */
1077 bool
1078 _bt_next(IndexScanDesc scan, ScanDirection dir)
1079 {
1080         BTScanOpaque so = (BTScanOpaque) scan->opaque;
1081         BTScanPosItem *currItem;
1082
1083         /*
1084          * Advance to next tuple on current page; or if there's no more, try to
1085          * step to the next page with data.
1086          */
1087         if (ScanDirectionIsForward(dir))
1088         {
1089                 if (++so->currPos.itemIndex > so->currPos.lastItem)
1090                 {
1091                         if (!_bt_steppage(scan, dir))
1092                                 return false;
1093                 }
1094         }
1095         else
1096         {
1097                 if (--so->currPos.itemIndex < so->currPos.firstItem)
1098                 {
1099                         if (!_bt_steppage(scan, dir))
1100                                 return false;
1101                 }
1102         }
1103
1104         /* OK, itemIndex says what to return */
1105         currItem = &so->currPos.items[so->currPos.itemIndex];
1106         scan->xs_ctup.t_self = currItem->heapTid;
1107         if (scan->xs_want_itup)
1108                 scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);
1109
1110         return true;
1111 }
1112
1113 /*
1114  *      _bt_readpage() -- Load data from current index page into so->currPos
1115  *
1116  * Caller must have pinned and read-locked so->currPos.buf; the buffer's state
1117  * is not changed here.  Also, currPos.moreLeft and moreRight must be valid;
1118  * they are updated as appropriate.  All other fields of so->currPos are
1119  * initialized from scratch here.
1120  *
1121  * We scan the current page starting at offnum and moving in the indicated
1122  * direction.  All items matching the scan keys are loaded into currPos.items.
1123  * moreLeft or moreRight (as appropriate) is cleared if _bt_checkkeys reports
1124  * that there can be no more matching tuples in the current scan direction.
1125  *
1126  * Returns true if any matching items found on the page, false if none.
1127  */
1128 static bool
1129 _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
1130 {
1131         BTScanOpaque so = (BTScanOpaque) scan->opaque;
1132         Page            page;
1133         BTPageOpaque opaque;
1134         OffsetNumber minoff;
1135         OffsetNumber maxoff;
1136         int                     itemIndex;
1137         IndexTuple      itup;
1138         bool            continuescan;
1139
1140         /*
1141          * We must have the buffer pinned and locked, but the usual macro can't be
1142          * used here; this function is what makes it good for currPos.
1143          */
1144         Assert(BufferIsValid(so->currPos.buf));
1145
1146         page = BufferGetPage(so->currPos.buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
1147         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1148         minoff = P_FIRSTDATAKEY(opaque);
1149         maxoff = PageGetMaxOffsetNumber(page);
1150
1151         /*
1152          * We note the buffer's block number so that we can release the pin later.
1153          * This allows us to re-read the buffer if it is needed again for hinting.
1154          */
1155         so->currPos.currPage = BufferGetBlockNumber(so->currPos.buf);
1156
1157         /*
1158          * We save the LSN of the page as we read it, so that we know whether it
1159          * safe to apply LP_DEAD hints to the page later.  This allows us to drop
1160          * the pin for MVCC scans, which allows vacuum to avoid blocking.
1161          */
1162         so->currPos.lsn = PageGetLSN(page);
1163
1164         /*
1165          * we must save the page's right-link while scanning it; this tells us
1166          * where to step right to after we're done with these items.  There is no
1167          * corresponding need for the left-link, since splits always go right.
1168          */
1169         so->currPos.nextPage = opaque->btpo_next;
1170
1171         /* initialize tuple workspace to empty */
1172         so->currPos.nextTupleOffset = 0;
1173
1174         /*
1175          * Now that the current page has been made consistent, the macro should be
1176          * good.
1177          */
1178         Assert(BTScanPosIsPinned(so->currPos));
1179
1180         if (ScanDirectionIsForward(dir))
1181         {
1182                 /* load items[] in ascending order */
1183                 itemIndex = 0;
1184
1185                 offnum = Max(offnum, minoff);
1186
1187                 while (offnum <= maxoff)
1188                 {
1189                         itup = _bt_checkkeys(scan, page, offnum, dir, &continuescan);
1190                         if (itup != NULL)
1191                         {
1192                                 /* tuple passes all scan key conditions, so remember it */
1193                                 _bt_saveitem(so, itemIndex, offnum, itup);
1194                                 itemIndex++;
1195                         }
1196                         if (!continuescan)
1197                         {
1198                                 /* there can't be any more matches, so stop */
1199                                 so->currPos.moreRight = false;
1200                                 break;
1201                         }
1202
1203                         offnum = OffsetNumberNext(offnum);
1204                 }
1205
1206                 Assert(itemIndex <= MaxIndexTuplesPerPage);
1207                 so->currPos.firstItem = 0;
1208                 so->currPos.lastItem = itemIndex - 1;
1209                 so->currPos.itemIndex = 0;
1210         }
1211         else
1212         {
1213                 /* load items[] in descending order */
1214                 itemIndex = MaxIndexTuplesPerPage;
1215
1216                 offnum = Min(offnum, maxoff);
1217
1218                 while (offnum >= minoff)
1219                 {
1220                         itup = _bt_checkkeys(scan, page, offnum, dir, &continuescan);
1221                         if (itup != NULL)
1222                         {
1223                                 /* tuple passes all scan key conditions, so remember it */
1224                                 itemIndex--;
1225                                 _bt_saveitem(so, itemIndex, offnum, itup);
1226                         }
1227                         if (!continuescan)
1228                         {
1229                                 /* there can't be any more matches, so stop */
1230                                 so->currPos.moreLeft = false;
1231                                 break;
1232                         }
1233
1234                         offnum = OffsetNumberPrev(offnum);
1235                 }
1236
1237                 Assert(itemIndex >= 0);
1238                 so->currPos.firstItem = itemIndex;
1239                 so->currPos.lastItem = MaxIndexTuplesPerPage - 1;
1240                 so->currPos.itemIndex = MaxIndexTuplesPerPage - 1;
1241         }
1242
1243         return (so->currPos.firstItem <= so->currPos.lastItem);
1244 }
1245
1246 /* Save an index item into so->currPos.items[itemIndex] */
1247 static void
1248 _bt_saveitem(BTScanOpaque so, int itemIndex,
1249                          OffsetNumber offnum, IndexTuple itup)
1250 {
1251         BTScanPosItem *currItem = &so->currPos.items[itemIndex];
1252
1253         currItem->heapTid = itup->t_tid;
1254         currItem->indexOffset = offnum;
1255         if (so->currTuples)
1256         {
1257                 Size            itupsz = IndexTupleSize(itup);
1258
1259                 currItem->tupleOffset = so->currPos.nextTupleOffset;
1260                 memcpy(so->currTuples + so->currPos.nextTupleOffset, itup, itupsz);
1261                 so->currPos.nextTupleOffset += MAXALIGN(itupsz);
1262         }
1263 }
1264
1265 /*
1266  *      _bt_steppage() -- Step to next page containing valid data for scan
1267  *
1268  * On entry, if so->currPos.buf is valid the buffer is pinned but not locked;
1269  * if pinned, we'll drop the pin before moving to next page.  The buffer is
1270  * not locked on entry.
1271  *
1272  * On success exit, so->currPos is updated to contain data from the next
1273  * interesting page.  For success on a scan using a non-MVCC snapshot we hold
1274  * a pin, but not a read lock, on that page.  If we do not hold the pin, we
1275  * set so->currPos.buf to InvalidBuffer.  We return TRUE to indicate success.
1276  *
1277  * If there are no more matching records in the given direction, we drop all
1278  * locks and pins, set so->currPos.buf to InvalidBuffer, and return FALSE.
1279  */
1280 static bool
1281 _bt_steppage(IndexScanDesc scan, ScanDirection dir)
1282 {
1283         BTScanOpaque so = (BTScanOpaque) scan->opaque;
1284         Relation        rel;
1285         Page            page;
1286         BTPageOpaque opaque;
1287
1288         Assert(BTScanPosIsValid(so->currPos));
1289
1290         /* Before leaving current page, deal with any killed items */
1291         if (so->numKilled > 0)
1292                 _bt_killitems(scan);
1293
1294         /*
1295          * Before we modify currPos, make a copy of the page data if there was a
1296          * mark position that needs it.
1297          */
1298         if (so->markItemIndex >= 0)
1299         {
1300                 /* bump pin on current buffer for assignment to mark buffer */
1301                 if (BTScanPosIsPinned(so->currPos))
1302                         IncrBufferRefCount(so->currPos.buf);
1303                 memcpy(&so->markPos, &so->currPos,
1304                            offsetof(BTScanPosData, items[1]) +
1305                            so->currPos.lastItem * sizeof(BTScanPosItem));
1306                 if (so->markTuples)
1307                         memcpy(so->markTuples, so->currTuples,
1308                                    so->currPos.nextTupleOffset);
1309                 so->markPos.itemIndex = so->markItemIndex;
1310                 so->markItemIndex = -1;
1311         }
1312
1313         rel = scan->indexRelation;
1314
1315         if (ScanDirectionIsForward(dir))
1316         {
1317                 /* Walk right to the next page with data */
1318                 /* We must rely on the previously saved nextPage link! */
1319                 BlockNumber blkno = so->currPos.nextPage;
1320
1321                 /* Remember we left a page with data */
1322                 so->currPos.moreLeft = true;
1323
1324                 /* release the previous buffer, if pinned */
1325                 BTScanPosUnpinIfPinned(so->currPos);
1326
1327                 for (;;)
1328                 {
1329                         /* if we're at end of scan, give up */
1330                         if (blkno == P_NONE || !so->currPos.moreRight)
1331                         {
1332                                 BTScanPosInvalidate(so->currPos);
1333                                 return false;
1334                         }
1335                         /* check for interrupts while we're not holding any buffer lock */
1336                         CHECK_FOR_INTERRUPTS();
1337                         /* step right one page */
1338                         so->currPos.buf = _bt_getbuf(rel, blkno, BT_READ);
1339                         /* check for deleted page */
1340                         page = BufferGetPage(so->currPos.buf, NULL, NULL,
1341                                                                  BGP_NO_SNAPSHOT_TEST);
1342                         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1343                         if (!P_IGNORE(opaque))
1344                         {
1345                                 PredicateLockPage(rel, blkno, scan->xs_snapshot);
1346                                 /* see if there are any matches on this page */
1347                                 /* note that this will clear moreRight if we can stop */
1348                                 if (_bt_readpage(scan, dir, P_FIRSTDATAKEY(opaque)))
1349                                         break;
1350                         }
1351
1352                         /* nope, keep going */
1353                         blkno = opaque->btpo_next;
1354                         _bt_relbuf(rel, so->currPos.buf);
1355                 }
1356         }
1357         else
1358         {
1359                 /* Remember we left a page with data */
1360                 so->currPos.moreRight = true;
1361
1362                 /*
1363                  * Walk left to the next page with data.  This is much more complex
1364                  * than the walk-right case because of the possibility that the page
1365                  * to our left splits while we are in flight to it, plus the
1366                  * possibility that the page we were on gets deleted after we leave
1367                  * it.  See nbtree/README for details.
1368                  *
1369                  * It might be possible to rearrange this code to have less overhead
1370                  * in pinning and locking, but that would require capturing the left
1371                  * pointer when the page is initially read, and using it here, along
1372                  * with big changes to _bt_walk_left() and the code below.  It is not
1373                  * clear whether this would be a win, since if the page immediately to
1374                  * the left splits after we read this page and before we step left, we
1375                  * would need to visit more pages than with the current code.
1376                  *
1377                  * Note that if we change the code so that we drop the pin for a scan
1378                  * which uses a non-MVCC snapshot, we will need to modify the code for
1379                  * walking left, to allow for the possibility that a referenced page
1380                  * has been deleted.  As long as the buffer is pinned or the snapshot
1381                  * is MVCC the page cannot move past the half-dead state to fully
1382                  * deleted.
1383                  */
1384                 if (BTScanPosIsPinned(so->currPos))
1385                         LockBuffer(so->currPos.buf, BT_READ);
1386                 else
1387                         so->currPos.buf = _bt_getbuf(rel, so->currPos.currPage, BT_READ);
1388
1389                 for (;;)
1390                 {
1391                         /* Done if we know there are no matching keys to the left */
1392                         if (!so->currPos.moreLeft)
1393                         {
1394                                 _bt_relbuf(rel, so->currPos.buf);
1395                                 BTScanPosInvalidate(so->currPos);
1396                                 return false;
1397                         }
1398
1399                         /* Step to next physical page */
1400                         so->currPos.buf = _bt_walk_left(rel, so->currPos.buf,
1401                                                                                         scan->xs_snapshot);
1402
1403                         /* if we're physically at end of index, return failure */
1404                         if (so->currPos.buf == InvalidBuffer)
1405                         {
1406                                 BTScanPosInvalidate(so->currPos);
1407                                 return false;
1408                         }
1409
1410                         /*
1411                          * Okay, we managed to move left to a non-deleted page. Done if
1412                          * it's not half-dead and contains matching tuples. Else loop back
1413                          * and do it all again.
1414                          */
1415                         page = BufferGetPage(so->currPos.buf, NULL, NULL,
1416                                                                  BGP_NO_SNAPSHOT_TEST);
1417                         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1418                         if (!P_IGNORE(opaque))
1419                         {
1420                                 PredicateLockPage(rel, BufferGetBlockNumber(so->currPos.buf), scan->xs_snapshot);
1421                                 /* see if there are any matches on this page */
1422                                 /* note that this will clear moreLeft if we can stop */
1423                                 if (_bt_readpage(scan, dir, PageGetMaxOffsetNumber(page)))
1424                                         break;
1425                         }
1426                 }
1427         }
1428
1429         /* Drop the lock, and maybe the pin, on the current page */
1430         _bt_drop_lock_and_maybe_pin(scan, &so->currPos);
1431
1432         return true;
1433 }
1434
1435 /*
1436  * _bt_walk_left() -- step left one page, if possible
1437  *
1438  * The given buffer must be pinned and read-locked.  This will be dropped
1439  * before stepping left.  On return, we have pin and read lock on the
1440  * returned page, instead.
1441  *
1442  * Returns InvalidBuffer if there is no page to the left (no lock is held
1443  * in that case).
1444  *
1445  * When working on a non-leaf level, it is possible for the returned page
1446  * to be half-dead; the caller should check that condition and step left
1447  * again if it's important.
1448  */
1449 static Buffer
1450 _bt_walk_left(Relation rel, Buffer buf, Snapshot snapshot)
1451 {
1452         Page            page;
1453         BTPageOpaque opaque;
1454
1455         page = BufferGetPage(buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
1456         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1457
1458         for (;;)
1459         {
1460                 BlockNumber obknum;
1461                 BlockNumber lblkno;
1462                 BlockNumber blkno;
1463                 int                     tries;
1464
1465                 /* if we're at end of tree, release buf and return failure */
1466                 if (P_LEFTMOST(opaque))
1467                 {
1468                         _bt_relbuf(rel, buf);
1469                         break;
1470                 }
1471                 /* remember original page we are stepping left from */
1472                 obknum = BufferGetBlockNumber(buf);
1473                 /* step left */
1474                 blkno = lblkno = opaque->btpo_prev;
1475                 _bt_relbuf(rel, buf);
1476                 /* check for interrupts while we're not holding any buffer lock */
1477                 CHECK_FOR_INTERRUPTS();
1478                 buf = _bt_getbuf(rel, blkno, BT_READ);
1479                 page = BufferGetPage(buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
1480                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1481
1482                 /*
1483                  * If this isn't the page we want, walk right till we find what we
1484                  * want --- but go no more than four hops (an arbitrary limit). If we
1485                  * don't find the correct page by then, the most likely bet is that
1486                  * the original page got deleted and isn't in the sibling chain at all
1487                  * anymore, not that its left sibling got split more than four times.
1488                  *
1489                  * Note that it is correct to test P_ISDELETED not P_IGNORE here,
1490                  * because half-dead pages are still in the sibling chain.  Caller
1491                  * must reject half-dead pages if wanted.
1492                  */
1493                 tries = 0;
1494                 for (;;)
1495                 {
1496                         if (!P_ISDELETED(opaque) && opaque->btpo_next == obknum)
1497                         {
1498                                 /* Found desired page, return it */
1499                                 return buf;
1500                         }
1501                         if (P_RIGHTMOST(opaque) || ++tries > 4)
1502                                 break;
1503                         blkno = opaque->btpo_next;
1504                         buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
1505                         page = BufferGetPage(buf, NULL, NULL,
1506                                                                  BGP_NO_SNAPSHOT_TEST);
1507                         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1508                 }
1509
1510                 /* Return to the original page to see what's up */
1511                 buf = _bt_relandgetbuf(rel, buf, obknum, BT_READ);
1512                 page = BufferGetPage(buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
1513                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1514                 if (P_ISDELETED(opaque))
1515                 {
1516                         /*
1517                          * It was deleted.  Move right to first nondeleted page (there
1518                          * must be one); that is the page that has acquired the deleted
1519                          * one's keyspace, so stepping left from it will take us where we
1520                          * want to be.
1521                          */
1522                         for (;;)
1523                         {
1524                                 if (P_RIGHTMOST(opaque))
1525                                         elog(ERROR, "fell off the end of index \"%s\"",
1526                                                  RelationGetRelationName(rel));
1527                                 blkno = opaque->btpo_next;
1528                                 buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
1529                                 page = BufferGetPage(buf, NULL, NULL,
1530                                                                          BGP_NO_SNAPSHOT_TEST);
1531                                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1532                                 if (!P_ISDELETED(opaque))
1533                                         break;
1534                         }
1535
1536                         /*
1537                          * Now return to top of loop, resetting obknum to point to this
1538                          * nondeleted page, and try again.
1539                          */
1540                 }
1541                 else
1542                 {
1543                         /*
1544                          * It wasn't deleted; the explanation had better be that the page
1545                          * to the left got split or deleted. Without this check, we'd go
1546                          * into an infinite loop if there's anything wrong.
1547                          */
1548                         if (opaque->btpo_prev == lblkno)
1549                                 elog(ERROR, "could not find left sibling of block %u in index \"%s\"",
1550                                          obknum, RelationGetRelationName(rel));
1551                         /* Okay to try again with new lblkno value */
1552                 }
1553         }
1554
1555         return InvalidBuffer;
1556 }
1557
1558 /*
1559  * _bt_get_endpoint() -- Find the first or last page on a given tree level
1560  *
1561  * If the index is empty, we will return InvalidBuffer; any other failure
1562  * condition causes ereport().  We will not return a dead page.
1563  *
1564  * The returned buffer is pinned and read-locked.
1565  */
1566 Buffer
1567 _bt_get_endpoint(Relation rel, uint32 level, bool rightmost)
1568 {
1569         Buffer          buf;
1570         Page            page;
1571         BTPageOpaque opaque;
1572         OffsetNumber offnum;
1573         BlockNumber blkno;
1574         IndexTuple      itup;
1575
1576         /*
1577          * If we are looking for a leaf page, okay to descend from fast root;
1578          * otherwise better descend from true root.  (There is no point in being
1579          * smarter about intermediate levels.)
1580          */
1581         if (level == 0)
1582                 buf = _bt_getroot(rel, BT_READ);
1583         else
1584                 buf = _bt_gettrueroot(rel);
1585
1586         if (!BufferIsValid(buf))
1587                 return InvalidBuffer;
1588
1589         page = BufferGetPage(buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
1590         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1591
1592         for (;;)
1593         {
1594                 /*
1595                  * If we landed on a deleted page, step right to find a live page
1596                  * (there must be one).  Also, if we want the rightmost page, step
1597                  * right if needed to get to it (this could happen if the page split
1598                  * since we obtained a pointer to it).
1599                  */
1600                 while (P_IGNORE(opaque) ||
1601                            (rightmost && !P_RIGHTMOST(opaque)))
1602                 {
1603                         blkno = opaque->btpo_next;
1604                         if (blkno == P_NONE)
1605                                 elog(ERROR, "fell off the end of index \"%s\"",
1606                                          RelationGetRelationName(rel));
1607                         buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
1608                         page = BufferGetPage(buf, NULL, NULL,
1609                                                                  BGP_NO_SNAPSHOT_TEST);
1610                         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1611                 }
1612
1613                 /* Done? */
1614                 if (opaque->btpo.level == level)
1615                         break;
1616                 if (opaque->btpo.level < level)
1617                         elog(ERROR, "btree level %u not found in index \"%s\"",
1618                                  level, RelationGetRelationName(rel));
1619
1620                 /* Descend to leftmost or rightmost child page */
1621                 if (rightmost)
1622                         offnum = PageGetMaxOffsetNumber(page);
1623                 else
1624                         offnum = P_FIRSTDATAKEY(opaque);
1625
1626                 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
1627                 blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1628
1629                 buf = _bt_relandgetbuf(rel, buf, blkno, BT_READ);
1630                 page = BufferGetPage(buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
1631                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1632         }
1633
1634         return buf;
1635 }
1636
1637 /*
1638  *      _bt_endpoint() -- Find the first or last page in the index, and scan
1639  * from there to the first key satisfying all the quals.
1640  *
1641  * This is used by _bt_first() to set up a scan when we've determined
1642  * that the scan must start at the beginning or end of the index (for
1643  * a forward or backward scan respectively).  Exit conditions are the
1644  * same as for _bt_first().
1645  */
1646 static bool
1647 _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
1648 {
1649         Relation        rel = scan->indexRelation;
1650         BTScanOpaque so = (BTScanOpaque) scan->opaque;
1651         Buffer          buf;
1652         Page            page;
1653         BTPageOpaque opaque;
1654         OffsetNumber start;
1655         BTScanPosItem *currItem;
1656
1657         /*
1658          * Scan down to the leftmost or rightmost leaf page.  This is a simplified
1659          * version of _bt_search().  We don't maintain a stack since we know we
1660          * won't need it.
1661          */
1662         buf = _bt_get_endpoint(rel, 0, ScanDirectionIsBackward(dir));
1663
1664         if (!BufferIsValid(buf))
1665         {
1666                 /*
1667                  * Empty index. Lock the whole relation, as nothing finer to lock
1668                  * exists.
1669                  */
1670                 PredicateLockRelation(rel, scan->xs_snapshot);
1671                 BTScanPosInvalidate(so->currPos);
1672                 return false;
1673         }
1674
1675         PredicateLockPage(rel, BufferGetBlockNumber(buf), scan->xs_snapshot);
1676         page = BufferGetPage(buf, NULL, NULL, BGP_NO_SNAPSHOT_TEST);
1677         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1678         Assert(P_ISLEAF(opaque));
1679
1680         if (ScanDirectionIsForward(dir))
1681         {
1682                 /* There could be dead pages to the left, so not this: */
1683                 /* Assert(P_LEFTMOST(opaque)); */
1684
1685                 start = P_FIRSTDATAKEY(opaque);
1686         }
1687         else if (ScanDirectionIsBackward(dir))
1688         {
1689                 Assert(P_RIGHTMOST(opaque));
1690
1691                 start = PageGetMaxOffsetNumber(page);
1692         }
1693         else
1694         {
1695                 elog(ERROR, "invalid scan direction: %d", (int) dir);
1696                 start = 0;                              /* keep compiler quiet */
1697         }
1698
1699         /* remember which buffer we have pinned */
1700         so->currPos.buf = buf;
1701
1702         /* initialize moreLeft/moreRight appropriately for scan direction */
1703         if (ScanDirectionIsForward(dir))
1704         {
1705                 so->currPos.moreLeft = false;
1706                 so->currPos.moreRight = true;
1707         }
1708         else
1709         {
1710                 so->currPos.moreLeft = true;
1711                 so->currPos.moreRight = false;
1712         }
1713         so->numKilled = 0;                      /* just paranoia */
1714         so->markItemIndex = -1;         /* ditto */
1715
1716         /*
1717          * Now load data from the first page of the scan.
1718          */
1719         if (!_bt_readpage(scan, dir, start))
1720         {
1721                 /*
1722                  * There's no actually-matching data on this page.  Try to advance to
1723                  * the next page.  Return false if there's no matching data at all.
1724                  */
1725                 LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
1726                 if (!_bt_steppage(scan, dir))
1727                         return false;
1728         }
1729         else
1730         {
1731                 /* Drop the lock, and maybe the pin, on the current page */
1732                 _bt_drop_lock_and_maybe_pin(scan, &so->currPos);
1733         }
1734
1735         /* OK, itemIndex says what to return */
1736         currItem = &so->currPos.items[so->currPos.itemIndex];
1737         scan->xs_ctup.t_self = currItem->heapTid;
1738         if (scan->xs_want_itup)
1739                 scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);
1740
1741         return true;
1742 }