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-2003, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.79 2003/08/04 02:39:57 momjian Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "access/genam.h"
  19 #include "access/nbtree.h"
  20
  21
  22 static Buffer _bt_walk_left(Relation rel, Buffer buf);
  23 static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir);
  24
  25
  26 /*
  27  *      _bt_search() -- Search the tree for a particular scankey,
  28  *              or more precisely for the first leaf page it could be on.
  29  *
  30  * Return value is a stack of parent-page pointers.  *bufP is set to the
  31  * address of the leaf-page buffer, which is read-locked and pinned.
  32  * No locks are held on the parent pages, however!
  33  *
  34  * NOTE that the returned buffer is read-locked regardless of the access
  35  * parameter.  However, access = BT_WRITE will allow an empty root page
  36  * to be created and returned.  When access = BT_READ, an empty index
  37  * will result in *bufP being set to InvalidBuffer.
  38  */
  39 BTStack
  40 _bt_search(Relation rel, int keysz, ScanKey scankey,
  41                    Buffer *bufP, int access)
  42 {
  43         BTStack         stack_in = NULL;
  44
  45         /* Get the root page to start with */
  46         *bufP = _bt_getroot(rel, access);
  47
  48         /* If index is empty and access = BT_READ, no root page is created. */
  49         if (!BufferIsValid(*bufP))
  50                 return (BTStack) NULL;
  51
  52         /* Loop iterates once per level descended in the tree */
  53         for (;;)
  54         {
  55                 Page            page;
  56                 BTPageOpaque opaque;
  57                 OffsetNumber offnum;
  58                 ItemId          itemid;
  59                 BTItem          btitem;
  60                 IndexTuple      itup;
  61                 BlockNumber blkno;
  62                 BlockNumber par_blkno;
  63                 BTStack         new_stack;
  64
  65                 /*
  66                  * Race -- the page we just grabbed may have split since we read
  67                  * its pointer in the parent (or metapage).  If it has, we may
  68                  * need to move right to its new sibling.  Do that.
  69                  */
  70                 *bufP = _bt_moveright(rel, *bufP, keysz, scankey, BT_READ);
  71
  72                 /* if this is a leaf page, we're done */
  73                 page = BufferGetPage(*bufP);
  74                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  75                 if (P_ISLEAF(opaque))
  76                         break;
  77
  78                 /*
  79                  * Find the appropriate item on the internal page, and get the
  80                  * child page that it points to.
  81                  */
  82                 offnum = _bt_binsrch(rel, *bufP, keysz, scankey);
  83                 itemid = PageGetItemId(page, offnum);
  84                 btitem = (BTItem) PageGetItem(page, itemid);
  85                 itup = &(btitem->bti_itup);
  86                 blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
  87                 par_blkno = BufferGetBlockNumber(*bufP);
  88
  89                 /*
  90                  * We need to save the location of the index entry we chose in the
  91                  * parent page on a stack. In case we split the tree, we'll use
  92                  * the stack to work back up to the parent page.  We also save the
  93                  * actual downlink (TID) to uniquely identify the index entry, in
  94                  * case it moves right while we're working lower in the tree.  See
  95                  * the paper by Lehman and Yao for how this is detected and
  96                  * handled. (We use the child link to disambiguate duplicate keys
  97                  * in the index -- Lehman and Yao disallow duplicate keys.)
  98                  */
  99                 new_stack = (BTStack) palloc(sizeof(BTStackData));
 100                 new_stack->bts_blkno = par_blkno;
 101                 new_stack->bts_offset = offnum;
 102                 memcpy(&new_stack->bts_btitem, btitem, sizeof(BTItemData));
 103                 new_stack->bts_parent = stack_in;
 104
 105                 /* drop the read lock on the parent page, acquire one on the child */
 106                 _bt_relbuf(rel, *bufP);
 107                 *bufP = _bt_getbuf(rel, blkno, BT_READ);
 108
 109                 /* okay, all set to move down a level */
 110                 stack_in = new_stack;
 111         }
 112
 113         return stack_in;
 114 }
 115
 116 /*
 117  *      _bt_moveright() -- move right in the btree if necessary.
 118  *
 119  *              When we follow a pointer to reach a page, it is possible that
 120  *              the page has changed in the meanwhile.  If this happens, we're
 121  *              guaranteed that the page has "split right" -- that is, that any
 122  *              data that appeared on the page originally is either on the page
 123  *              or strictly to the right of it.
 124  *
 125  *              This routine decides whether or not we need to move right in the
 126  *              tree by examining the high key entry on the page.  If that entry
 127  *              is strictly less than one we expect to be on the page, then our
 128  *              picture of the page is incorrect and we need to move right.
 129  *
 130  *              On entry, we have the buffer pinned and a lock of the proper type.
 131  *              If we move right, we release the buffer and lock and acquire the
 132  *              same on the right sibling.      Return value is the buffer we stop at.
 133  */
 134 Buffer
 135 _bt_moveright(Relation rel,
 136                           Buffer buf,
 137                           int keysz,
 138                           ScanKey scankey,
 139                           int access)
 140 {
 141         Page            page;
 142         BTPageOpaque opaque;
 143
 144         page = BufferGetPage(buf);
 145         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 146
 147         /*
 148          * If the scan key that brought us to this page is > the high key
 149          * stored on the page, then the page has split and we need to move
 150          * right.  (If the scan key is equal to the high key, we might or
 151          * might not need to move right; have to scan the page first anyway.)
 152          * It could even have split more than once, so scan as far as needed.
 153          *
 154          * We also have to move right if we followed a link that brought us to a
 155          * dead page.
 156          */
 157         while (!P_RIGHTMOST(opaque) &&
 158                    (P_IGNORE(opaque) ||
 159                         _bt_compare(rel, keysz, scankey, page, P_HIKEY) > 0))
 160         {
 161                 /* step right one page */
 162                 BlockNumber rblkno = opaque->btpo_next;
 163
 164                 _bt_relbuf(rel, buf);
 165                 buf = _bt_getbuf(rel, rblkno, access);
 166                 page = BufferGetPage(buf);
 167                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 168         }
 169
 170         if (P_IGNORE(opaque))
 171                 elog(ERROR, "fell off the end of \"%s\"",
 172                          RelationGetRelationName(rel));
 173
 174         return buf;
 175 }
 176
 177 /*
 178  *      _bt_binsrch() -- Do a binary search for a key on a particular page.
 179  *
 180  * The scankey we get has the compare function stored in the procedure
 181  * entry of each data struct.  We invoke this regproc to do the
 182  * comparison for every key in the scankey.
 183  *
 184  * On a leaf page, _bt_binsrch() returns the OffsetNumber of the first
 185  * key >= given scankey.  (NOTE: in particular, this means it is possible
 186  * to return a value 1 greater than the number of keys on the page,
 187  * if the scankey is > all keys on the page.)
 188  *
 189  * On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber
 190  * of the last key < given scankey.  (Since _bt_compare treats the first
 191  * data key of such a page as minus infinity, there will be at least one
 192  * key < scankey, so the result always points at one of the keys on the
 193  * page.)  This key indicates the right place to descend to be sure we
 194  * find all leaf keys >= given scankey.
 195  *
 196  * This procedure is not responsible for walking right, it just examines
 197  * the given page.      _bt_binsrch() has no lock or refcount side effects
 198  * on the buffer.
 199  */
 200 OffsetNumber
 201 _bt_binsrch(Relation rel,
 202                         Buffer buf,
 203                         int keysz,
 204                         ScanKey scankey)
 205 {
 206         TupleDesc       itupdesc;
 207         Page            page;
 208         BTPageOpaque opaque;
 209         OffsetNumber low,
 210                                 high;
 211         int32           result;
 212
 213         itupdesc = RelationGetDescr(rel);
 214         page = BufferGetPage(buf);
 215         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 216
 217         low = P_FIRSTDATAKEY(opaque);
 218         high = PageGetMaxOffsetNumber(page);
 219
 220         /*
 221          * If there are no keys on the page, return the first available slot.
 222          * Note this covers two cases: the page is really empty (no keys), or
 223          * it contains only a high key.  The latter case is possible after
 224          * vacuuming.  This can never happen on an internal page, however,
 225          * since they are never empty (an internal page must have children).
 226          */
 227         if (high < low)
 228                 return low;
 229
 230         /*
 231          * Binary search to find the first key on the page >= scan key. Loop
 232          * invariant: all slots before 'low' are < scan key, all slots at or
 233          * after 'high' are >= scan key.  We can fall out when high == low.
 234          */
 235         high++;                                         /* establish the loop invariant for high */
 236
 237         while (high > low)
 238         {
 239                 OffsetNumber mid = low + ((high - low) / 2);
 240
 241                 /* We have low <= mid < high, so mid points at a real slot */
 242
 243                 result = _bt_compare(rel, keysz, scankey, page, mid);
 244
 245                 if (result > 0)
 246                         low = mid + 1;
 247                 else
 248                         high = mid;
 249         }
 250
 251         /*
 252          * At this point we have high == low, but be careful: they could point
 253          * past the last slot on the page.
 254          *
 255          * On a leaf page, we always return the first key >= scan key (which
 256          * could be the last slot + 1).
 257          */
 258         if (P_ISLEAF(opaque))
 259                 return low;
 260
 261         /*
 262          * On a non-leaf page, return the last key < scan key. There must be
 263          * one if _bt_compare() is playing by the rules.
 264          */
 265         Assert(low > P_FIRSTDATAKEY(opaque));
 266
 267         return OffsetNumberPrev(low);
 268 }
 269
 270 /*----------
 271  *      _bt_compare() -- Compare scankey to a particular tuple on the page.
 272  *
 273  *      keysz: number of key conditions to be checked (might be less than the
 274  *      total length of the scan key!)
 275  *      page/offnum: location of btree item to be compared to.
 276  *
 277  *              This routine returns:
 278  *                      <0 if scankey < tuple at offnum;
 279  *                       0 if scankey == tuple at offnum;
 280  *                      >0 if scankey > tuple at offnum.
 281  *              NULLs in the keys are treated as sortable values.  Therefore
 282  *              "equality" does not necessarily mean that the item should be
 283  *              returned to the caller as a matching key!
 284  *
 285  * CRUCIAL NOTE: on a non-leaf page, the first data key is assumed to be
 286  * "minus infinity": this routine will always claim it is less than the
 287  * scankey.  The actual key value stored (if any, which there probably isn't)
 288  * does not matter.  This convention allows us to implement the Lehman and
 289  * Yao convention that the first down-link pointer is before the first key.
 290  * See backend/access/nbtree/README for details.
 291  *----------
 292  */
 293 int32
 294 _bt_compare(Relation rel,
 295                         int keysz,
 296                         ScanKey scankey,
 297                         Page page,
 298                         OffsetNumber offnum)
 299 {
 300         TupleDesc       itupdesc = RelationGetDescr(rel);
 301         BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 302         BTItem          btitem;
 303         IndexTuple      itup;
 304         int                     i;
 305
 306         /*
 307          * Force result ">" if target item is first data item on an internal
 308          * page --- see NOTE above.
 309          */
 310         if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque))
 311                 return 1;
 312
 313         btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
 314         itup = &(btitem->bti_itup);
 315
 316         /*
 317          * The scan key is set up with the attribute number associated with
 318          * each term in the key.  It is important that, if the index is
 319          * multi-key, the scan contain the first k key attributes, and that
 320          * they be in order.  If you think about how multi-key ordering works,
 321          * you'll understand why this is.
 322          *
 323          * We don't test for violation of this condition here, however.  The
 324          * initial setup for the index scan had better have gotten it right
 325          * (see _bt_first).
 326          */
 327
 328         for (i = 0; i < keysz; i++)
 329         {
 330                 ScanKey         entry = &scankey[i];
 331                 Datum           datum;
 332                 bool            isNull;
 333                 int32           result;
 334
 335                 datum = index_getattr(itup, entry->sk_attno, itupdesc, &isNull);
 336
 337                 /* see comments about NULLs handling in btbuild */
 338                 if (entry->sk_flags & SK_ISNULL)                /* key is NULL */
 339                 {
 340                         if (isNull)
 341                                 result = 0;             /* NULL "=" NULL */
 342                         else
 343                                 result = 1;             /* NULL ">" NOT_NULL */
 344                 }
 345                 else if (isNull)                /* key is NOT_NULL and item is NULL */
 346                 {
 347                         result = -1;            /* NOT_NULL "<" NULL */
 348                 }
 349                 else
 350                 {
 351                         result = DatumGetInt32(FunctionCall2(&entry->sk_func,
 352                                                                                                  entry->sk_argument,
 353                                                                                                  datum));
 354                 }
 355
 356                 /* if the keys are unequal, return the difference */
 357                 if (result != 0)
 358                         return result;
 359         }
 360
 361         /* if we get here, the keys are equal */
 362         return 0;
 363 }
 364
 365 /*
 366  *      _bt_next() -- Get the next item in a scan.
 367  *
 368  *              On entry, we have a valid currentItemData in the scan, and a
 369  *              read lock and pin count on the page that contains that item.
 370  *              We return the next item in the scan, or false if no more.
 371  *              On successful exit, the page containing the new item is locked
 372  *              and pinned; on failure exit, no lock or pin is held.
 373  */
 374 bool
 375 _bt_next(IndexScanDesc scan, ScanDirection dir)
 376 {
 377         Relation        rel;
 378         Buffer          buf;
 379         Page            page;
 380         OffsetNumber offnum;
 381         ItemPointer current;
 382         BTItem          btitem;
 383         IndexTuple      itup;
 384         BTScanOpaque so;
 385         bool            continuescan;
 386
 387         rel = scan->indexRelation;
 388         so = (BTScanOpaque) scan->opaque;
 389         current = &(scan->currentItemData);
 390
 391         /* we still have the buffer pinned and locked */
 392         buf = so->btso_curbuf;
 393         Assert(BufferIsValid(buf));
 394
 395         do
 396         {
 397                 /* step one tuple in the appropriate direction */
 398                 if (!_bt_step(scan, &buf, dir))
 399                         return false;
 400
 401                 /* current is the next candidate tuple to return */
 402                 offnum = ItemPointerGetOffsetNumber(current);
 403                 page = BufferGetPage(buf);
 404                 btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
 405                 itup = &btitem->bti_itup;
 406
 407                 if (_bt_checkkeys(scan, itup, dir, &continuescan))
 408                 {
 409                         /* tuple passes all scan key conditions, so return it */
 410                         scan->xs_ctup.t_self = itup->t_tid;
 411                         return true;
 412                 }
 413
 414                 /* This tuple doesn't pass, but there might be more that do */
 415         } while (continuescan);
 416
 417         /* No more items, so close down the current-item info */
 418         ItemPointerSetInvalid(current);
 419         so->btso_curbuf = InvalidBuffer;
 420         _bt_relbuf(rel, buf);
 421
 422         return false;
 423 }
 424
 425 /*
 426  *      _bt_first() -- Find the first item in a scan.
 427  *
 428  *              We need to be clever about the type of scan, the operation it's
 429  *              performing, and the tree ordering.      We find the
 430  *              first item in the tree that satisfies the qualification
 431  *              associated with the scan descriptor.  On exit, the page containing
 432  *              the current index tuple is read locked and pinned, and the scan's
 433  *              opaque data entry is updated to include the buffer.
 434  */
 435 bool
 436 _bt_first(IndexScanDesc scan, ScanDirection dir)
 437 {
 438         Relation        rel = scan->indexRelation;
 439         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 440         Buffer          buf;
 441         Page            page;
 442         BTStack         stack;
 443         OffsetNumber offnum;
 444         BTItem          btitem;
 445         IndexTuple      itup;
 446         ItemPointer current;
 447         BlockNumber blkno;
 448         StrategyNumber strat;
 449         bool            res;
 450         int32           result;
 451         bool            scanFromEnd;
 452         bool            continuescan;
 453         ScanKey         scankeys = NULL;
 454         int                     keysCount = 0;
 455         int                *nKeyIs = NULL;
 456         int                     i,
 457                                 j;
 458         StrategyNumber strat_total;
 459
 460         /*
 461          * Order the scan keys in our canonical fashion and eliminate any
 462          * redundant keys.
 463          */
 464         _bt_orderkeys(scan);
 465
 466         /*
 467          * Quit now if _bt_orderkeys() discovered that the scan keys can never
 468          * be satisfied (eg, x == 1 AND x > 2).
 469          */
 470         if (!so->qual_ok)
 471                 return false;
 472
 473         /*
 474          * Examine the scan keys to discover where we need to start the scan.
 475          */
 476         scanFromEnd = false;
 477         strat_total = BTEqualStrategyNumber;
 478         if (so->numberOfKeys > 0)
 479         {
 480                 nKeyIs = (int *) palloc(so->numberOfKeys * sizeof(int));
 481                 for (i = 0; i < so->numberOfKeys; i++)
 482                 {
 483                         AttrNumber      attno = so->keyData[i].sk_attno;
 484
 485                         /* ignore keys for already-determined attrs */
 486                         if (attno <= keysCount)
 487                                 continue;
 488                         /* if we didn't find a boundary for the preceding attr, quit */
 489                         if (attno > keysCount + 1)
 490                                 break;
 491                         strat = _bt_getstrat(rel, attno,
 492                                                                  so->keyData[i].sk_procedure);
 493
 494                         /*
 495                          * Can we use this key as a starting boundary for this attr?
 496                          *
 497                          * We can use multiple keys if they look like, say, = >= = but we
 498                          * have to stop after accepting a > or < boundary.
 499                          */
 500                         if (strat == strat_total ||
 501                                 strat == BTEqualStrategyNumber)
 502                                 nKeyIs[keysCount++] = i;
 503                         else if (ScanDirectionIsBackward(dir) &&
 504                                          (strat == BTLessStrategyNumber ||
 505                                           strat == BTLessEqualStrategyNumber))
 506                         {
 507                                 nKeyIs[keysCount++] = i;
 508                                 strat_total = strat;
 509                                 if (strat == BTLessStrategyNumber)
 510                                         break;
 511                         }
 512                         else if (ScanDirectionIsForward(dir) &&
 513                                          (strat == BTGreaterStrategyNumber ||
 514                                           strat == BTGreaterEqualStrategyNumber))
 515                         {
 516                                 nKeyIs[keysCount++] = i;
 517                                 strat_total = strat;
 518                                 if (strat == BTGreaterStrategyNumber)
 519                                         break;
 520                         }
 521                 }
 522                 if (keysCount == 0)
 523                         scanFromEnd = true;
 524         }
 525         else
 526                 scanFromEnd = true;
 527
 528         /* if we just need to walk down one edge of the tree, do that */
 529         if (scanFromEnd)
 530         {
 531                 if (nKeyIs)
 532                         pfree(nKeyIs);
 533                 return _bt_endpoint(scan, dir);
 534         }
 535
 536         /*
 537          * We want to start the scan somewhere within the index.  Set up a
 538          * scankey we can use to search for the correct starting point.
 539          */
 540         scankeys = (ScanKey) palloc(keysCount * sizeof(ScanKeyData));
 541         for (i = 0; i < keysCount; i++)
 542         {
 543                 FmgrInfo   *procinfo;
 544
 545                 j = nKeyIs[i];
 546
 547                 /*
 548                  * _bt_orderkeys disallows it, but it's place to add some code
 549                  * later
 550                  */
 551                 if (so->keyData[j].sk_flags & SK_ISNULL)
 552                 {
 553                         pfree(nKeyIs);
 554                         pfree(scankeys);
 555                         elog(ERROR, "btree doesn't support is(not)null, yet");
 556                         return false;
 557                 }
 558                 procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
 559                 ScanKeyEntryInitializeWithInfo(scankeys + i,
 560                                                                            so->keyData[j].sk_flags,
 561                                                                            i + 1,
 562                                                                            procinfo,
 563                                                                            CurrentMemoryContext,
 564                                                                            so->keyData[j].sk_argument);
 565         }
 566         if (nKeyIs)
 567                 pfree(nKeyIs);
 568
 569         current = &(scan->currentItemData);
 570
 571         /*
 572          * Use the manufactured scan key to descend the tree and position
 573          * ourselves on the target leaf page.
 574          */
 575         stack = _bt_search(rel, keysCount, scankeys, &buf, BT_READ);
 576
 577         /* don't need to keep the stack around... */
 578         _bt_freestack(stack);
 579
 580         if (!BufferIsValid(buf))
 581         {
 582                 /* Only get here if index is completely empty */
 583                 ItemPointerSetInvalid(current);
 584                 so->btso_curbuf = InvalidBuffer;
 585                 pfree(scankeys);
 586                 return false;
 587         }
 588
 589         /* remember which buffer we have pinned */
 590         so->btso_curbuf = buf;
 591         blkno = BufferGetBlockNumber(buf);
 592         page = BufferGetPage(buf);
 593
 594         /* position to the precise item on the page */
 595         offnum = _bt_binsrch(rel, buf, keysCount, scankeys);
 596
 597         ItemPointerSet(current, blkno, offnum);
 598
 599         /*
 600          * At this point we are positioned at the first item >= scan key, or
 601          * possibly at the end of a page on which all the existing items are
 602          * less than the scan key and we know that everything on later pages
 603          * is greater than or equal to scan key.
 604          *
 605          * We could step forward in the latter case, but that'd be a waste of
 606          * time if we want to scan backwards.  So, it's now time to examine
 607          * the scan strategy to find the exact place to start the scan.
 608          *
 609          * Note: if _bt_step fails (meaning we fell off the end of the index in
 610          * one direction or the other), we either return false (no matches) or
 611          * call _bt_endpoint() to set up a scan starting at that index
 612          * endpoint, as appropriate for the desired scan type.
 613          *
 614          * it's yet other place to add some code later for is(not)null ...
 615          */
 616
 617         switch (strat_total)
 618         {
 619                 case BTLessStrategyNumber:
 620
 621                         /*
 622                          * Back up one to arrive at last item < scankey
 623                          */
 624                         if (!_bt_step(scan, &buf, BackwardScanDirection))
 625                         {
 626                                 pfree(scankeys);
 627                                 return false;
 628                         }
 629                         break;
 630
 631                 case BTLessEqualStrategyNumber:
 632
 633                         /*
 634                          * We need to find the last item <= scankey, so step forward
 635                          * till we find one > scankey, then step back one.
 636                          */
 637                         if (offnum > PageGetMaxOffsetNumber(page))
 638                         {
 639                                 if (!_bt_step(scan, &buf, ForwardScanDirection))
 640                                 {
 641                                         pfree(scankeys);
 642                                         return _bt_endpoint(scan, dir);
 643                                 }
 644                         }
 645                         for (;;)
 646                         {
 647                                 offnum = ItemPointerGetOffsetNumber(current);
 648                                 page = BufferGetPage(buf);
 649                                 result = _bt_compare(rel, keysCount, scankeys, page, offnum);
 650                                 if (result < 0)
 651                                         break;
 652                                 if (!_bt_step(scan, &buf, ForwardScanDirection))
 653                                 {
 654                                         pfree(scankeys);
 655                                         return _bt_endpoint(scan, dir);
 656                                 }
 657                         }
 658                         if (!_bt_step(scan, &buf, BackwardScanDirection))
 659                         {
 660                                 pfree(scankeys);
 661                                 return false;
 662                         }
 663                         break;
 664
 665                 case BTEqualStrategyNumber:
 666
 667                         /*
 668                          * Make sure we are on the first equal item; might have to
 669                          * step forward if currently at end of page.
 670                          */
 671                         if (offnum > PageGetMaxOffsetNumber(page))
 672                         {
 673                                 if (!_bt_step(scan, &buf, ForwardScanDirection))
 674                                 {
 675                                         pfree(scankeys);
 676                                         return false;
 677                                 }
 678                                 offnum = ItemPointerGetOffsetNumber(current);
 679                                 page = BufferGetPage(buf);
 680                         }
 681                         result = _bt_compare(rel, keysCount, scankeys, page, offnum);
 682                         if (result != 0)
 683                                 goto nomatches; /* no equal items! */
 684
 685                         /*
 686                          * If a backward scan was specified, need to start with last
 687                          * equal item not first one.
 688                          */
 689                         if (ScanDirectionIsBackward(dir))
 690                         {
 691                                 do
 692                                 {
 693                                         if (!_bt_step(scan, &buf, ForwardScanDirection))
 694                                         {
 695                                                 pfree(scankeys);
 696                                                 return _bt_endpoint(scan, dir);
 697                                         }
 698                                         offnum = ItemPointerGetOffsetNumber(current);
 699                                         page = BufferGetPage(buf);
 700                                         result = _bt_compare(rel, keysCount, scankeys, page, offnum);
 701                                 } while (result == 0);
 702                                 if (!_bt_step(scan, &buf, BackwardScanDirection))
 703                                         elog(ERROR, "equal items disappeared?");
 704                         }
 705                         break;
 706
 707                 case BTGreaterEqualStrategyNumber:
 708
 709                         /*
 710                          * We want the first item >= scankey, which is where we are...
 711                          * unless we're not anywhere at all...
 712                          */
 713                         if (offnum > PageGetMaxOffsetNumber(page))
 714                         {
 715                                 if (!_bt_step(scan, &buf, ForwardScanDirection))
 716                                 {
 717                                         pfree(scankeys);
 718                                         return false;
 719                                 }
 720                         }
 721                         break;
 722
 723                 case BTGreaterStrategyNumber:
 724
 725                         /*
 726                          * We want the first item > scankey, so make sure we are on an
 727                          * item and then step over any equal items.
 728                          */
 729                         if (offnum > PageGetMaxOffsetNumber(page))
 730                         {
 731                                 if (!_bt_step(scan, &buf, ForwardScanDirection))
 732                                 {
 733                                         pfree(scankeys);
 734                                         return false;
 735                                 }
 736                                 offnum = ItemPointerGetOffsetNumber(current);
 737                                 page = BufferGetPage(buf);
 738                         }
 739                         result = _bt_compare(rel, keysCount, scankeys, page, offnum);
 740                         while (result == 0)
 741                         {
 742                                 if (!_bt_step(scan, &buf, ForwardScanDirection))
 743                                 {
 744                                         pfree(scankeys);
 745                                         return false;
 746                                 }
 747                                 offnum = ItemPointerGetOffsetNumber(current);
 748                                 page = BufferGetPage(buf);
 749                                 result = _bt_compare(rel, keysCount, scankeys, page, offnum);
 750                         }
 751                         break;
 752         }
 753
 754         /* okay, current item pointer for the scan is right */
 755         offnum = ItemPointerGetOffsetNumber(current);
 756         page = BufferGetPage(buf);
 757         btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
 758         itup = &btitem->bti_itup;
 759
 760         /* is the first item actually acceptable? */
 761         if (_bt_checkkeys(scan, itup, dir, &continuescan))
 762         {
 763                 /* yes, return it */
 764                 scan->xs_ctup.t_self = itup->t_tid;
 765                 res = true;
 766         }
 767         else if (continuescan)
 768         {
 769                 /* no, but there might be another one that is */
 770                 res = _bt_next(scan, dir);
 771         }
 772         else
 773         {
 774                 /* no tuples in the index match this scan key */
 775 nomatches:
 776                 ItemPointerSetInvalid(current);
 777                 so->btso_curbuf = InvalidBuffer;
 778                 _bt_relbuf(rel, buf);
 779                 res = false;
 780         }
 781
 782         pfree(scankeys);
 783
 784         return res;
 785 }
 786
 787 /*
 788  *      _bt_step() -- Step one item in the requested direction in a scan on
 789  *                                the tree.
 790  *
 791  *              *bufP is the current buffer (read-locked and pinned).  If we change
 792  *              pages, it's updated appropriately.
 793  *
 794  *              If successful, update scan's currentItemData and return true.
 795  *              If no adjacent record exists in the requested direction,
 796  *              release buffer pin/locks and return false.
 797  */
 798 bool
 799 _bt_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
 800 {
 801         Relation        rel = scan->indexRelation;
 802         ItemPointer current = &(scan->currentItemData);
 803         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 804         Page            page;
 805         BTPageOpaque opaque;
 806         OffsetNumber offnum,
 807                                 maxoff;
 808         BlockNumber blkno;
 809
 810         /*
 811          * Don't use ItemPointerGetOffsetNumber or you risk to get assertion
 812          * due to ability of ip_posid to be equal 0.
 813          */
 814         offnum = current->ip_posid;
 815
 816         page = BufferGetPage(*bufP);
 817         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 818         maxoff = PageGetMaxOffsetNumber(page);
 819
 820         if (ScanDirectionIsForward(dir))
 821         {
 822                 if (!PageIsEmpty(page) && offnum < maxoff)
 823                         offnum = OffsetNumberNext(offnum);
 824                 else
 825                 {
 826                         /* Walk right to the next page with data */
 827                         for (;;)
 828                         {
 829                                 /* if we're at end of scan, release the buffer and return */
 830                                 if (P_RIGHTMOST(opaque))
 831                                 {
 832                                         _bt_relbuf(rel, *bufP);
 833                                         ItemPointerSetInvalid(current);
 834                                         *bufP = so->btso_curbuf = InvalidBuffer;
 835                                         return false;
 836                                 }
 837                                 /* step right one page */
 838                                 blkno = opaque->btpo_next;
 839                                 _bt_relbuf(rel, *bufP);
 840                                 *bufP = _bt_getbuf(rel, blkno, BT_READ);
 841                                 page = BufferGetPage(*bufP);
 842                                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 843                                 if (!P_IGNORE(opaque))
 844                                 {
 845                                         maxoff = PageGetMaxOffsetNumber(page);
 846                                         /* done if it's not empty */
 847                                         offnum = P_FIRSTDATAKEY(opaque);
 848                                         if (!PageIsEmpty(page) && offnum <= maxoff)
 849                                                 break;
 850                                 }
 851                         }
 852                 }
 853         }
 854         else
 855 /* backwards scan */
 856         {
 857                 if (offnum > P_FIRSTDATAKEY(opaque))
 858                         offnum = OffsetNumberPrev(offnum);
 859                 else
 860                 {
 861                         /*
 862                          * Walk left to the next page with data.  This is much more
 863                          * complex than the walk-right case because of the possibility
 864                          * that the page to our left splits while we are in flight to
 865                          * it, plus the possibility that the page we were on gets
 866                          * deleted after we leave it.  See nbtree/README for details.
 867                          */
 868                         for (;;)
 869                         {
 870                                 *bufP = _bt_walk_left(rel, *bufP);
 871
 872                                 /* if we're at end of scan, return failure */
 873                                 if (*bufP == InvalidBuffer)
 874                                 {
 875                                         ItemPointerSetInvalid(current);
 876                                         so->btso_curbuf = InvalidBuffer;
 877                                         return false;
 878                                 }
 879                                 page = BufferGetPage(*bufP);
 880                                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 881
 882                                 /*
 883                                  * Okay, we managed to move left to a non-deleted page.
 884                                  * Done if it's not half-dead and not empty.  Else loop
 885                                  * back and do it all again.
 886                                  */
 887                                 if (!P_IGNORE(opaque))
 888                                 {
 889                                         maxoff = PageGetMaxOffsetNumber(page);
 890                                         offnum = maxoff;
 891                                         if (!PageIsEmpty(page) &&
 892                                                 maxoff >= P_FIRSTDATAKEY(opaque))
 893                                                 break;
 894                                 }
 895                         }
 896                 }
 897         }
 898
 899         /* Update scan state */
 900         so->btso_curbuf = *bufP;
 901         blkno = BufferGetBlockNumber(*bufP);
 902         ItemPointerSet(current, blkno, offnum);
 903
 904         return true;
 905 }
 906
 907 /*
 908  * _bt_walk_left() -- step left one page, if possible
 909  *
 910  * The given buffer must be pinned and read-locked.  This will be dropped
 911  * before stepping left.  On return, we have pin and read lock on the
 912  * returned page, instead.
 913  *
 914  * Returns InvalidBuffer if there is no page to the left (no lock is held
 915  * in that case).
 916  *
 917  * When working on a non-leaf level, it is possible for the returned page
 918  * to be half-dead; the caller should check that condition and step left
 919  * again if it's important.
 920  */
 921 static Buffer
 922 _bt_walk_left(Relation rel, Buffer buf)
 923 {
 924         Page            page;
 925         BTPageOpaque opaque;
 926
 927         page = BufferGetPage(buf);
 928         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 929
 930         for (;;)
 931         {
 932                 BlockNumber obknum;
 933                 BlockNumber lblkno;
 934                 BlockNumber blkno;
 935                 int                     tries;
 936
 937                 /* if we're at end of tree, release buf and return failure */
 938                 if (P_LEFTMOST(opaque))
 939                 {
 940                         _bt_relbuf(rel, buf);
 941                         break;
 942                 }
 943                 /* remember original page we are stepping left from */
 944                 obknum = BufferGetBlockNumber(buf);
 945                 /* step left */
 946                 blkno = lblkno = opaque->btpo_prev;
 947                 _bt_relbuf(rel, buf);
 948                 buf = _bt_getbuf(rel, blkno, BT_READ);
 949                 page = BufferGetPage(buf);
 950                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 951
 952                 /*
 953                  * If this isn't the page we want, walk right till we find what we
 954                  * want --- but go no more than four hops (an arbitrary limit).
 955                  * If we don't find the correct page by then, the most likely bet
 956                  * is that the original page got deleted and isn't in the sibling
 957                  * chain at all anymore, not that its left sibling got split more
 958                  * than four times.
 959                  *
 960                  * Note that it is correct to test P_ISDELETED not P_IGNORE here,
 961                  * because half-dead pages are still in the sibling chain.      Caller
 962                  * must reject half-dead pages if wanted.
 963                  */
 964                 tries = 0;
 965                 for (;;)
 966                 {
 967                         if (!P_ISDELETED(opaque) && opaque->btpo_next == obknum)
 968                         {
 969                                 /* Found desired page, return it */
 970                                 return buf;
 971                         }
 972                         if (P_RIGHTMOST(opaque) || ++tries > 4)
 973                                 break;
 974                         blkno = opaque->btpo_next;
 975                         _bt_relbuf(rel, buf);
 976                         buf = _bt_getbuf(rel, blkno, BT_READ);
 977                         page = BufferGetPage(buf);
 978                         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 979                 }
 980
 981                 /* Return to the original page to see what's up */
 982                 _bt_relbuf(rel, buf);
 983                 buf = _bt_getbuf(rel, obknum, BT_READ);
 984                 page = BufferGetPage(buf);
 985                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 986                 if (P_ISDELETED(opaque))
 987                 {
 988                         /*
 989                          * It was deleted.      Move right to first nondeleted page (there
 990                          * must be one); that is the page that has acquired the
 991                          * deleted one's keyspace, so stepping left from it will take
 992                          * us where we want to be.
 993                          */
 994                         for (;;)
 995                         {
 996                                 if (P_RIGHTMOST(opaque))
 997                                         elog(ERROR, "fell off the end of \"%s\"",
 998                                                  RelationGetRelationName(rel));
 999                                 blkno = opaque->btpo_next;
1000                                 _bt_relbuf(rel, buf);
1001                                 buf = _bt_getbuf(rel, blkno, BT_READ);
1002                                 page = BufferGetPage(buf);
1003                                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1004                                 if (!P_ISDELETED(opaque))
1005                                         break;
1006                         }
1007
1008                         /*
1009                          * Now return to top of loop, resetting obknum to point to
1010                          * this nondeleted page, and try again.
1011                          */
1012                 }
1013                 else
1014                 {
1015                         /*
1016                          * It wasn't deleted; the explanation had better be that the
1017                          * page to the left got split or deleted. Without this check,
1018                          * we'd go into an infinite loop if there's anything wrong.
1019                          */
1020                         if (opaque->btpo_prev == lblkno)
1021                                 elog(ERROR, "could not find left sibling in \"%s\"",
1022                                          RelationGetRelationName(rel));
1023                         /* Okay to try again with new lblkno value */
1024                 }
1025         }
1026
1027         return InvalidBuffer;
1028 }
1029
1030 /*
1031  * _bt_get_endpoint() -- Find the first or last page on a given tree level
1032  *
1033  * If the index is empty, we will return InvalidBuffer; any other failure
1034  * condition causes ereport().  We will not return a dead page.
1035  *
1036  * The returned buffer is pinned and read-locked.
1037  */
1038 Buffer
1039 _bt_get_endpoint(Relation rel, uint32 level, bool rightmost)
1040 {
1041         Buffer          buf;
1042         Page            page;
1043         BTPageOpaque opaque;
1044         OffsetNumber offnum;
1045         BlockNumber blkno;
1046         BTItem          btitem;
1047         IndexTuple      itup;
1048
1049         /*
1050          * If we are looking for a leaf page, okay to descend from fast root;
1051          * otherwise better descend from true root.  (There is no point in
1052          * being smarter about intermediate levels.)
1053          */
1054         if (level == 0)
1055                 buf = _bt_getroot(rel, BT_READ);
1056         else
1057                 buf = _bt_gettrueroot(rel);
1058
1059         if (!BufferIsValid(buf))
1060         {
1061                 /* empty index... */
1062                 return InvalidBuffer;
1063         }
1064
1065         page = BufferGetPage(buf);
1066         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1067
1068         for (;;)
1069         {
1070                 /*
1071                  * If we landed on a deleted page, step right to find a live page
1072                  * (there must be one).  Also, if we want the rightmost page, step
1073                  * right if needed to get to it (this could happen if the page
1074                  * split since we obtained a pointer to it).
1075                  */
1076                 while (P_IGNORE(opaque) ||
1077                            (rightmost && !P_RIGHTMOST(opaque)))
1078                 {
1079                         blkno = opaque->btpo_next;
1080                         if (blkno == P_NONE)
1081                                 elog(ERROR, "fell off the end of \"%s\"",
1082                                          RelationGetRelationName(rel));
1083                         _bt_relbuf(rel, buf);
1084                         buf = _bt_getbuf(rel, blkno, BT_READ);
1085                         page = BufferGetPage(buf);
1086                         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1087                 }
1088
1089                 /* Done? */
1090                 if (opaque->btpo.level == level)
1091                         break;
1092                 if (opaque->btpo.level < level)
1093                         elog(ERROR, "btree level %u not found", level);
1094
1095                 /* Descend to leftmost or rightmost child page */
1096                 if (rightmost)
1097                         offnum = PageGetMaxOffsetNumber(page);
1098                 else
1099                         offnum = P_FIRSTDATAKEY(opaque);
1100
1101                 btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
1102                 itup = &(btitem->bti_itup);
1103                 blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1104
1105                 _bt_relbuf(rel, buf);
1106                 buf = _bt_getbuf(rel, blkno, BT_READ);
1107                 page = BufferGetPage(buf);
1108                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1109         }
1110
1111         return buf;
1112 }
1113
1114 /*
1115  *      _bt_endpoint() -- Find the first or last key in the index.
1116  *
1117  * This is used by _bt_first() to set up a scan when we've determined
1118  * that the scan must start at the beginning or end of the index (for
1119  * a forward or backward scan respectively).
1120  */
1121 static bool
1122 _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
1123 {
1124         Relation        rel;
1125         Buffer          buf;
1126         Page            page;
1127         BTPageOpaque opaque;
1128         ItemPointer current;
1129         OffsetNumber maxoff;
1130         OffsetNumber start;
1131         BlockNumber blkno;
1132         BTItem          btitem;
1133         IndexTuple      itup;
1134         BTScanOpaque so;
1135         bool            res;
1136         bool            continuescan;
1137
1138         rel = scan->indexRelation;
1139         current = &(scan->currentItemData);
1140         so = (BTScanOpaque) scan->opaque;
1141
1142         /*
1143          * Scan down to the leftmost or rightmost leaf page.  This is a
1144          * simplified version of _bt_search().  We don't maintain a stack
1145          * since we know we won't need it.
1146          */
1147         buf = _bt_get_endpoint(rel, 0, ScanDirectionIsBackward(dir));
1148
1149         if (!BufferIsValid(buf))
1150         {
1151                 /* empty index... */
1152                 ItemPointerSetInvalid(current);
1153                 so->btso_curbuf = InvalidBuffer;
1154                 return false;
1155         }
1156
1157         blkno = BufferGetBlockNumber(buf);
1158         page = BufferGetPage(buf);
1159         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1160         Assert(P_ISLEAF(opaque));
1161
1162         maxoff = PageGetMaxOffsetNumber(page);
1163
1164         if (ScanDirectionIsForward(dir))
1165         {
1166                 /* There could be dead pages to the left, so not this: */
1167                 /* Assert(P_LEFTMOST(opaque)); */
1168
1169                 start = P_FIRSTDATAKEY(opaque);
1170         }
1171         else if (ScanDirectionIsBackward(dir))
1172         {
1173                 Assert(P_RIGHTMOST(opaque));
1174
1175                 start = PageGetMaxOffsetNumber(page);
1176                 if (start < P_FIRSTDATAKEY(opaque))             /* watch out for empty
1177                                                                                                  * page */
1178                         start = P_FIRSTDATAKEY(opaque);
1179         }
1180         else
1181         {
1182                 elog(ERROR, "invalid scan direction: %d", (int) dir);
1183                 start = 0;                              /* keep compiler quiet */
1184         }
1185
1186         ItemPointerSet(current, blkno, start);
1187         /* remember which buffer we have pinned */
1188         so->btso_curbuf = buf;
1189
1190         /*
1191          * Left/rightmost page could be empty due to deletions, if so step
1192          * till we find a nonempty page.
1193          */
1194         if (start > maxoff)
1195         {
1196                 if (!_bt_step(scan, &buf, dir))
1197                         return false;
1198                 start = ItemPointerGetOffsetNumber(current);
1199                 page = BufferGetPage(buf);
1200         }
1201
1202         btitem = (BTItem) PageGetItem(page, PageGetItemId(page, start));
1203         itup = &(btitem->bti_itup);
1204
1205         /* see if we picked a winner */
1206         if (_bt_checkkeys(scan, itup, dir, &continuescan))
1207         {
1208                 /* yes, return it */
1209                 scan->xs_ctup.t_self = itup->t_tid;
1210                 res = true;
1211         }
1212         else if (continuescan)
1213         {
1214                 /* no, but there might be another one that is */
1215                 res = _bt_next(scan, dir);
1216         }
1217         else
1218         {
1219                 /* no tuples in the index match this scan key */
1220                 ItemPointerSetInvalid(current);
1221                 so->btso_curbuf = InvalidBuffer;
1222                 _bt_relbuf(rel, buf);
1223                 res = false;
1224         }
1225
1226         return res;
1227 }