granicus.if.org Git - postgresql/blob - src/backend/access/hash/hashsearch.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * hashsearch.c--
   4  *    search code for postgres hash tables
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *    $Header: /cvsroot/pgsql/src/backend/access/hash/hashsearch.c,v 1.1.1.1 1996/07/09 06:21:10 scrappy Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "storage/bufmgr.h"
  17 #include "storage/bufpage.h"
  18
  19 #include "utils/elog.h"
  20 #include "utils/palloc.h"
  21 #include "utils/rel.h"
  22 #include "utils/excid.h"
  23
  24 #include "fmgr.h"
  25
  26 #include "access/heapam.h"
  27 #include "access/genam.h"
  28 #include "access/skey.h"
  29 #include "access/sdir.h"
  30 #include "access/hash.h"
  31
  32 /*
  33  *  _hash_search() -- Finds the page/bucket that the contains the
  34  *  scankey and loads it into *bufP.  the buffer has a read lock.
  35  */
  36 void
  37 _hash_search(Relation rel,
  38              int keysz,
  39              ScanKey scankey,
  40              Buffer *bufP,
  41              HashMetaPage metap)
  42 {
  43     BlockNumber blkno;
  44     Datum keyDatum;
  45     Bucket bucket;
  46
  47     if (scankey == (ScanKey) NULL ||
  48         (keyDatum = scankey[0].sk_argument) == (Datum) NULL) {
  49         /*
  50          * If the scankey argument is NULL, all tuples will satisfy
  51          * the scan so we start the scan at the first bucket (bucket
  52          * 0).
  53          */
  54         bucket = 0;
  55     } else {
  56         bucket = _hash_call(rel, metap, keyDatum);
  57     }
  58
  59     blkno = BUCKET_TO_BLKNO(bucket);
  60
  61     *bufP = _hash_getbuf(rel, blkno, HASH_READ);
  62 }
  63
  64 /*
  65  *  _hash_next() -- Get the next item in a scan.
  66  *
  67  *      On entry, we have a valid currentItemData in the scan, and a
  68  *      read lock on the page that contains that item.  We do not have
  69  *      the page pinned.  We return the next item in the scan.  On
  70  *      exit, we have the page containing the next item locked but not
  71  *      pinned.
  72  */
  73 RetrieveIndexResult
  74 _hash_next(IndexScanDesc scan, ScanDirection dir)
  75 {
  76     Relation rel;
  77     Buffer buf;
  78     Buffer metabuf;
  79     Page page;
  80     OffsetNumber offnum;
  81     RetrieveIndexResult res;
  82     ItemPointer current;
  83     ItemPointer iptr;
  84     HashItem hitem;
  85     IndexTuple itup;
  86     HashScanOpaque so;
  87
  88     rel = scan->relation;
  89     so = (HashScanOpaque) scan->opaque;
  90     current = &(scan->currentItemData);
  91
  92     metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ);
  93
  94     /*
  95      *  XXX 10 may 91:  somewhere there's a bug in our management of the
  96      *  cached buffer for this scan.  wei discovered it.  the following
  97      *  is a workaround so he can work until i figure out what's going on.
  98      */
  99
 100     if (!BufferIsValid(so->hashso_curbuf)) {
 101         so->hashso_curbuf = _hash_getbuf(rel,
 102                                          ItemPointerGetBlockNumber(current),
 103                                          HASH_READ);
 104     }
 105
 106     /* we still have the buffer pinned and locked */
 107     buf = so->hashso_curbuf;
 108
 109     /*
 110      * step to next valid tuple.  note that _hash_step releases our
 111      * lock on 'metabuf'; if we switch to a new 'buf' while looking
 112      * for the next tuple, we come back with a lock on that buffer.
 113      */
 114     if (!_hash_step(scan, &buf, dir, metabuf)) {
 115         return ((RetrieveIndexResult) NULL);
 116     }
 117
 118     /* if we're here, _hash_step found a valid tuple */
 119     current = &(scan->currentItemData);
 120     offnum = ItemPointerGetOffsetNumber(current);
 121     page = BufferGetPage(buf);
 122     _hash_checkpage(page, LH_BUCKET_PAGE|LH_OVERFLOW_PAGE);
 123     hitem = (HashItem) PageGetItem(page, PageGetItemId(page, offnum));
 124     itup = &hitem->hash_itup;
 125     iptr = (ItemPointer) palloc(sizeof(ItemPointerData));
 126     memmove((char *) iptr, (char *) &(itup->t_tid),  sizeof(ItemPointerData));
 127     res = FormRetrieveIndexResult(current, iptr);
 128
 129     return (res);
 130 }
 131
 132 static void
 133 _hash_readnext(Relation rel,
 134                Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
 135 {
 136     BlockNumber blkno;
 137
 138     blkno = (*opaquep)->hasho_nextblkno;
 139     _hash_relbuf(rel, *bufp, HASH_READ);
 140     *bufp = InvalidBuffer;
 141     if (BlockNumberIsValid(blkno)) {
 142         *bufp = _hash_getbuf(rel, blkno, HASH_READ);
 143         *pagep = BufferGetPage(*bufp);
 144         _hash_checkpage(*pagep, LH_OVERFLOW_PAGE);
 145         *opaquep = (HashPageOpaque) PageGetSpecialPointer(*pagep);
 146         Assert(!PageIsEmpty(*pagep));
 147     }
 148 }
 149
 150 static void
 151 _hash_readprev(Relation rel,
 152                Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
 153 {
 154     BlockNumber blkno;
 155
 156     blkno = (*opaquep)->hasho_prevblkno;
 157     _hash_relbuf(rel, *bufp, HASH_READ);
 158     *bufp = InvalidBuffer;
 159     if (BlockNumberIsValid(blkno)) {
 160         *bufp = _hash_getbuf(rel, blkno, HASH_READ);
 161         *pagep = BufferGetPage(*bufp);
 162         _hash_checkpage(*pagep, LH_BUCKET_PAGE|LH_OVERFLOW_PAGE);
 163         *opaquep = (HashPageOpaque) PageGetSpecialPointer(*pagep);
 164         if (PageIsEmpty(*pagep)) {
 165             Assert((*opaquep)->hasho_flag & LH_BUCKET_PAGE);
 166             _hash_relbuf(rel, *bufp, HASH_READ);
 167             *bufp = InvalidBuffer;
 168         }
 169     }
 170 }
 171
 172 /*
 173  *  _hash_first() -- Find the first item in a scan.
 174  *
 175  *      Return the RetrieveIndexResult of the first item in the tree that
 176  *      satisfies the qualificatin associated with the scan descriptor. On
 177  *      exit, the page containing the current index tuple is read locked
 178  *      and pinned, and the scan's opaque data entry is updated to
 179  *      include the buffer.
 180  */
 181 RetrieveIndexResult
 182 _hash_first(IndexScanDesc scan, ScanDirection dir)
 183 {
 184     Relation rel;
 185     Buffer buf;
 186     Buffer metabuf;
 187     Page page;
 188     HashPageOpaque opaque;
 189     HashMetaPage metap;
 190     HashItem hitem;
 191     IndexTuple itup;
 192     ItemPointer current;
 193     ItemPointer iptr;
 194     OffsetNumber offnum;
 195     RetrieveIndexResult res;
 196     HashScanOpaque so;
 197
 198     rel = scan->relation;
 199     so = (HashScanOpaque) scan->opaque;
 200     current = &(scan->currentItemData);
 201
 202     metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ);
 203     metap = (HashMetaPage) BufferGetPage(metabuf);
 204     _hash_checkpage((Page) metap, LH_META_PAGE);
 205
 206     /*
 207      *  XXX -- The attribute number stored in the scan key is the attno
 208      *         in the heap relation.  We need to transmogrify this into
 209      *         the index relation attno here.  For the moment, we have
 210      *         hardwired attno == 1.
 211      */
 212
 213     /* find the correct bucket page and load it into buf */
 214     _hash_search(rel, 1, scan->keyData, &buf, metap);
 215     page = BufferGetPage(buf);
 216     _hash_checkpage(page, LH_BUCKET_PAGE);
 217     opaque = (HashPageOpaque) PageGetSpecialPointer(page);
 218
 219     /*
 220      * if we are scanning forward, we need to find the first non-empty
 221      * page (if any) in the bucket chain.  since overflow pages are
 222      * never empty, this had better be either the bucket page or the
 223      * first overflow page.
 224      *
 225      * if we are scanning backward, we always go all the way to the
 226      * end of the bucket chain.
 227      */
 228     if (PageIsEmpty(page)) {
 229         if (BlockNumberIsValid(opaque->hasho_nextblkno)) {
 230             _hash_readnext(rel, &buf, &page, &opaque);
 231         } else {
 232             ItemPointerSetInvalid(current);
 233             so->hashso_curbuf = InvalidBuffer;
 234             return ((RetrieveIndexResult) NULL);
 235         }
 236     }
 237     if (ScanDirectionIsBackward(dir)) {
 238         while (BlockNumberIsValid(opaque->hasho_nextblkno)) {
 239             _hash_readnext(rel, &buf, &page, &opaque);
 240         }
 241     }
 242
 243     if (!_hash_step(scan, &buf, dir, metabuf)) {
 244         return ((RetrieveIndexResult) NULL);
 245     }
 246
 247     /* if we're here, _hash_step found a valid tuple */
 248     current = &(scan->currentItemData);
 249     offnum = ItemPointerGetOffsetNumber(current);
 250     page = BufferGetPage(buf);
 251     _hash_checkpage(page, LH_BUCKET_PAGE|LH_OVERFLOW_PAGE);
 252     hitem = (HashItem) PageGetItem(page, PageGetItemId(page, offnum));
 253     itup = &hitem->hash_itup;
 254     iptr = (ItemPointer) palloc(sizeof(ItemPointerData));
 255     memmove((char *) iptr, (char *) &(itup->t_tid), sizeof(ItemPointerData));
 256     res = FormRetrieveIndexResult(current, iptr);
 257
 258     return (res);
 259 }
 260
 261 /*
 262  *  _hash_step() -- step to the next valid item in a scan in the bucket.
 263  *
 264  *      If no valid record exists in the requested direction, return
 265  *      false.  Else, return true and set the CurrentItemData for the
 266  *      scan to the right thing.
 267  *
 268  *      'bufP' points to the buffer which contains the current page
 269  *      that we'll step through.
 270  *
 271  *      'metabuf' is released when this returns.
 272  */
 273 bool
 274 _hash_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir, Buffer metabuf)
 275 {
 276     Relation rel;
 277     ItemPointer current;
 278     HashScanOpaque so;
 279     int allbuckets;
 280     HashMetaPage metap;
 281     Buffer buf;
 282     Page page;
 283     HashPageOpaque opaque;
 284     OffsetNumber maxoff;
 285     OffsetNumber offnum;
 286     Bucket bucket;
 287     BlockNumber blkno;
 288     HashItem hitem;
 289     IndexTuple itup;
 290
 291     rel = scan->relation;
 292     current = &(scan->currentItemData);
 293     so = (HashScanOpaque) scan->opaque;
 294     allbuckets = (scan->numberOfKeys < 1);
 295
 296     metap = (HashMetaPage) BufferGetPage(metabuf);
 297     _hash_checkpage((Page) metap, LH_META_PAGE);
 298
 299     buf = *bufP;
 300     page = BufferGetPage(buf);
 301     _hash_checkpage(page, LH_BUCKET_PAGE|LH_OVERFLOW_PAGE);
 302     opaque = (HashPageOpaque) PageGetSpecialPointer(page);
 303
 304     /*
 305      * If _hash_step is called from _hash_first, current will not be
 306      * valid, so we can't dereference it.  However, in that case, we
 307      * presumably want to start at the beginning/end of the page...
 308      */
 309     maxoff = PageGetMaxOffsetNumber(page);
 310     if (ItemPointerIsValid(current)) {
 311         offnum = ItemPointerGetOffsetNumber(current);
 312     } else {
 313         offnum = InvalidOffsetNumber;
 314     }
 315
 316     /*
 317      * 'offnum' now points to the last tuple we have seen (if any).
 318      *
 319      * continue to step through tuples until:
 320      *    1) we get to the end of the bucket chain or
 321      *    2) we find a valid tuple.
 322      */
 323     do {
 324         bucket = opaque->hasho_bucket;
 325
 326         switch (dir) {
 327         case ForwardScanDirection:
 328             if (offnum != InvalidOffsetNumber) {
 329                 offnum = OffsetNumberNext(offnum);      /* move forward */
 330             } else {
 331                 offnum = FirstOffsetNumber;             /* new page */
 332             }
 333             while (offnum > maxoff) {
 334                 /*
 335                  * either this page is empty (maxoff ==
 336                  * InvalidOffsetNumber) or we ran off the end.
 337                  */
 338                 _hash_readnext(rel, &buf, &page, &opaque);
 339                 if (BufferIsInvalid(buf)) {     /* end of chain */
 340                     if (allbuckets && bucket < metap->hashm_maxbucket) {
 341                         ++bucket;
 342                         blkno = BUCKET_TO_BLKNO(bucket);
 343                         buf = _hash_getbuf(rel, blkno, HASH_READ);
 344                         page = BufferGetPage(buf);
 345                         _hash_checkpage(page, LH_BUCKET_PAGE);
 346                         opaque = (HashPageOpaque) PageGetSpecialPointer(page);
 347                         Assert(opaque->hasho_bucket == bucket);
 348                         while (PageIsEmpty(page) &&
 349                                BlockNumberIsValid(opaque->hasho_nextblkno)) {
 350                             _hash_readnext(rel, &buf, &page, &opaque);
 351                         }
 352                         maxoff = PageGetMaxOffsetNumber(page);
 353                         offnum = FirstOffsetNumber;
 354                     } else {
 355                         maxoff = offnum = InvalidOffsetNumber;
 356                         break;  /* while */
 357                     }
 358                 } else {
 359                     /* _hash_readnext never returns an empty page */
 360                     maxoff = PageGetMaxOffsetNumber(page);
 361                     offnum = FirstOffsetNumber;
 362                 }
 363             }
 364             break;
 365         case BackwardScanDirection:
 366             if (offnum != InvalidOffsetNumber) {
 367                 offnum = OffsetNumberPrev(offnum);      /* move back */
 368             } else {
 369                 offnum = maxoff;                        /* new page */
 370             }
 371             while (offnum < FirstOffsetNumber) {
 372                 /*
 373                  * either this page is empty (offnum ==
 374                  * InvalidOffsetNumber) or we ran off the end.
 375                  */
 376                 _hash_readprev(rel, &buf, &page, &opaque);
 377                 if (BufferIsInvalid(buf)) {     /* end of chain */
 378                     if (allbuckets && bucket > 0) {
 379                         --bucket;
 380                         blkno = BUCKET_TO_BLKNO(bucket);
 381                         buf = _hash_getbuf(rel, blkno, HASH_READ);
 382                         page = BufferGetPage(buf);
 383                         _hash_checkpage(page, LH_BUCKET_PAGE);
 384                         opaque = (HashPageOpaque) PageGetSpecialPointer(page);
 385                         Assert(opaque->hasho_bucket == bucket);
 386                         while (BlockNumberIsValid(opaque->hasho_nextblkno)) {
 387                             _hash_readnext(rel, &buf, &page, &opaque);
 388                         }
 389                         maxoff = offnum = PageGetMaxOffsetNumber(page);
 390                     } else {
 391                         maxoff = offnum = InvalidOffsetNumber;
 392                         break;  /* while */
 393                     }
 394                 } else {
 395                     /* _hash_readprev never returns an empty page */
 396                     maxoff = offnum = PageGetMaxOffsetNumber(page);
 397                 }
 398             }
 399             break;
 400         default:
 401             /* NoMovementScanDirection */
 402             /* this should not be reached */
 403             break;
 404         }
 405
 406         /* we ran off the end of the world without finding a match */
 407         if (offnum == InvalidOffsetNumber) {
 408             _hash_relbuf(rel, metabuf, HASH_READ);
 409             *bufP = so->hashso_curbuf = InvalidBuffer;
 410             ItemPointerSetInvalid(current);
 411             return(false);
 412         }
 413
 414         /* get ready to check this tuple */
 415         hitem = (HashItem) PageGetItem(page, PageGetItemId(page, offnum));
 416         itup = &hitem->hash_itup;
 417     } while (!_hash_checkqual(scan, itup));
 418
 419     /* if we made it to here, we've found a valid tuple */
 420     _hash_relbuf(rel, metabuf, HASH_READ);
 421     blkno = BufferGetBlockNumber(buf);
 422     *bufP = so->hashso_curbuf = buf;
 423     ItemPointerSet(current, blkno, offnum);
 424     return(true);
 425 }