1 /*-------------------------------------------------------------------------
4 * search code for postgres hash tables
6 * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $PostgreSQL: pgsql/src/backend/access/hash/hashsearch.c,v 1.47 2007/01/20 18:43:35 neilc Exp $
13 *-------------------------------------------------------------------------
17 #include "access/hash.h"
22 * _hash_next() -- Get the next item in a scan.
24 * On entry, we have a valid hashso_curpos in the scan, and a
25 * pin and read lock on the page that contains that item.
26 * We find the next item in the scan, if any.
27 * On success exit, we have the page containing the next item
31 _hash_next(IndexScanDesc scan, ScanDirection dir)
33 Relation rel = scan->indexRelation;
34 HashScanOpaque so = (HashScanOpaque) scan->opaque;
41 /* we still have the buffer pinned and read-locked */
42 buf = so->hashso_curbuf;
43 Assert(BufferIsValid(buf));
46 * step to next valid tuple.
48 if (!_hash_step(scan, &buf, dir))
51 /* if we're here, _hash_step found a valid tuple */
52 current = &(so->hashso_curpos);
53 offnum = ItemPointerGetOffsetNumber(current);
54 _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
55 page = BufferGetPage(buf);
56 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
57 scan->xs_ctup.t_self = itup->t_tid;
63 * Advance to next page in a bucket, if any.
66 _hash_readnext(Relation rel,
67 Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
71 blkno = (*opaquep)->hasho_nextblkno;
72 _hash_relbuf(rel, *bufp);
73 *bufp = InvalidBuffer;
74 if (BlockNumberIsValid(blkno))
76 *bufp = _hash_getbuf(rel, blkno, HASH_READ);
77 _hash_checkpage(rel, *bufp, LH_OVERFLOW_PAGE);
78 *pagep = BufferGetPage(*bufp);
79 *opaquep = (HashPageOpaque) PageGetSpecialPointer(*pagep);
84 * Advance to previous page in a bucket, if any.
87 _hash_readprev(Relation rel,
88 Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
92 blkno = (*opaquep)->hasho_prevblkno;
93 _hash_relbuf(rel, *bufp);
94 *bufp = InvalidBuffer;
95 if (BlockNumberIsValid(blkno))
97 *bufp = _hash_getbuf(rel, blkno, HASH_READ);
98 _hash_checkpage(rel, *bufp, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
99 *pagep = BufferGetPage(*bufp);
100 *opaquep = (HashPageOpaque) PageGetSpecialPointer(*pagep);
105 * _hash_first() -- Find the first item in a scan.
107 * Find the first item in the index that
108 * satisfies the qualification associated with the scan descriptor. On
109 * success, the page containing the current index tuple is read locked
110 * and pinned, and the scan's opaque data entry is updated to
111 * include the buffer.
114 _hash_first(IndexScanDesc scan, ScanDirection dir)
116 Relation rel = scan->indexRelation;
117 HashScanOpaque so = (HashScanOpaque) scan->opaque;
124 HashPageOpaque opaque;
130 pgstat_count_index_scan(&scan->xs_pgstat_info);
132 current = &(so->hashso_curpos);
133 ItemPointerSetInvalid(current);
136 * We do not support hash scans with no index qualification, because we
137 * would have to read the whole index rather than just one bucket. That
138 * creates a whole raft of problems, since we haven't got a practical way
139 * to lock all the buckets against splits or compactions.
141 if (scan->numberOfKeys < 1)
143 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
144 errmsg("hash indexes do not support whole-index scans")));
147 * If the constant in the index qual is NULL, assume it cannot match any
148 * items in the index.
150 if (scan->keyData[0].sk_flags & SK_ISNULL)
154 * Okay to compute the hash key. We want to do this before acquiring any
155 * locks, in case a user-defined hash function happens to be slow.
157 hashkey = _hash_datum2hashkey(rel, scan->keyData[0].sk_argument);
160 * Acquire shared split lock so we can compute the target bucket safely
163 _hash_getlock(rel, 0, HASH_SHARE);
165 /* Read the metapage */
166 metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_READ);
167 _hash_checkpage(rel, metabuf, LH_META_PAGE);
168 metap = (HashMetaPage) BufferGetPage(metabuf);
171 * Compute the target bucket number, and convert to block number.
173 bucket = _hash_hashkey2bucket(hashkey,
174 metap->hashm_maxbucket,
175 metap->hashm_highmask,
176 metap->hashm_lowmask);
178 blkno = BUCKET_TO_BLKNO(metap, bucket);
180 /* done with the metapage */
181 _hash_relbuf(rel, metabuf);
184 * Acquire share lock on target bucket; then we can release split lock.
186 _hash_getlock(rel, blkno, HASH_SHARE);
188 _hash_droplock(rel, 0, HASH_SHARE);
190 /* Update scan opaque state to show we have lock on the bucket */
191 so->hashso_bucket = bucket;
192 so->hashso_bucket_valid = true;
193 so->hashso_bucket_blkno = blkno;
195 /* Fetch the primary bucket page for the bucket */
196 buf = _hash_getbuf(rel, blkno, HASH_READ);
197 _hash_checkpage(rel, buf, LH_BUCKET_PAGE);
198 page = BufferGetPage(buf);
199 opaque = (HashPageOpaque) PageGetSpecialPointer(page);
200 Assert(opaque->hasho_bucket == bucket);
202 /* If a backwards scan is requested, move to the end of the chain */
203 if (ScanDirectionIsBackward(dir))
205 while (BlockNumberIsValid(opaque->hasho_nextblkno))
206 _hash_readnext(rel, &buf, &page, &opaque);
209 /* Now find the first tuple satisfying the qualification */
210 if (!_hash_step(scan, &buf, dir))
213 /* if we're here, _hash_step found a valid tuple */
214 offnum = ItemPointerGetOffsetNumber(current);
215 _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
216 page = BufferGetPage(buf);
217 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
218 scan->xs_ctup.t_self = itup->t_tid;
224 * _hash_step() -- step to the next valid item in a scan in the bucket.
226 * If no valid record exists in the requested direction, return
227 * false. Else, return true and set the hashso_curpos for the
228 * scan to the right thing.
230 * 'bufP' points to the current buffer, which is pinned and read-locked.
231 * On success exit, we have pin and read-lock on whichever page
232 * contains the right item; on failure, we have released all buffers.
235 _hash_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
237 Relation rel = scan->indexRelation;
238 HashScanOpaque so = (HashScanOpaque) scan->opaque;
242 HashPageOpaque opaque;
248 current = &(so->hashso_curpos);
251 _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
252 page = BufferGetPage(buf);
253 opaque = (HashPageOpaque) PageGetSpecialPointer(page);
256 * If _hash_step is called from _hash_first, current will not be valid, so
257 * we can't dereference it. However, in that case, we presumably want to
258 * start at the beginning/end of the page...
260 maxoff = PageGetMaxOffsetNumber(page);
261 if (ItemPointerIsValid(current))
262 offnum = ItemPointerGetOffsetNumber(current);
264 offnum = InvalidOffsetNumber;
267 * 'offnum' now points to the last tuple we have seen (if any).
269 * continue to step through tuples until: 1) we get to the end of the
270 * bucket chain or 2) we find a valid tuple.
276 case ForwardScanDirection:
277 if (offnum != InvalidOffsetNumber)
278 offnum = OffsetNumberNext(offnum); /* move forward */
280 offnum = FirstOffsetNumber; /* new page */
282 while (offnum > maxoff)
285 * either this page is empty (maxoff ==
286 * InvalidOffsetNumber) or we ran off the end.
288 _hash_readnext(rel, &buf, &page, &opaque);
289 if (BufferIsValid(buf))
291 maxoff = PageGetMaxOffsetNumber(page);
292 offnum = FirstOffsetNumber;
297 maxoff = offnum = InvalidOffsetNumber;
298 break; /* exit while */
303 case BackwardScanDirection:
304 if (offnum != InvalidOffsetNumber)
305 offnum = OffsetNumberPrev(offnum); /* move back */
307 offnum = maxoff; /* new page */
309 while (offnum < FirstOffsetNumber)
312 * either this page is empty (offnum ==
313 * InvalidOffsetNumber) or we ran off the end.
315 _hash_readprev(rel, &buf, &page, &opaque);
316 if (BufferIsValid(buf))
317 maxoff = offnum = PageGetMaxOffsetNumber(page);
321 maxoff = offnum = InvalidOffsetNumber;
322 break; /* exit while */
328 /* NoMovementScanDirection */
329 /* this should not be reached */
333 /* we ran off the end of the world without finding a match */
334 if (offnum == InvalidOffsetNumber)
336 *bufP = so->hashso_curbuf = InvalidBuffer;
337 ItemPointerSetInvalid(current);
341 /* get ready to check this tuple */
342 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
343 } while (!_hash_checkqual(scan, itup));
345 /* if we made it to here, we've found a valid tuple */
346 blkno = BufferGetBlockNumber(buf);
347 *bufP = so->hashso_curbuf = buf;
348 ItemPointerSet(current, blkno, offnum);