Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * hashsearch.c
4 : : * search code for postgres hash tables
5 : : *
6 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/hash/hashsearch.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : : #include "postgres.h"
16 : :
17 : : #include "access/hash.h"
18 : : #include "access/relscan.h"
19 : : #include "miscadmin.h"
20 : : #include "executor/instrument_node.h"
21 : : #include "pgstat.h"
22 : : #include "storage/predicate.h"
23 : : #include "utils/rel.h"
24 : :
25 : : static void _hash_readnext(IndexScanDesc scan, Buffer *bufp,
26 : : Page *pagep, HashPageOpaque *opaquep);
27 : : static void _hash_readprev(IndexScanDesc scan, Buffer *bufp,
28 : : Page *pagep, HashPageOpaque *opaquep);
29 : : static Buffer _hash_step_to_split_bucket(IndexScanDesc scan);
30 : : static Buffer _hash_step_to_populated_bucket(IndexScanDesc scan);
31 : : static bool _hash_readpage(IndexScanDesc scan, Buffer *bufP,
32 : : ScanDirection dir);
33 : : static int _hash_load_qualified_items(IndexScanDesc scan, Page page,
34 : : OffsetNumber offnum, ScanDirection dir);
35 : : static inline void _hash_saveitem(HashScanOpaque so, int itemIndex,
36 : : OffsetNumber offnum, IndexTuple itup);
37 : :
38 : : /*
39 : : * _hash_next() -- Get the next item in a scan.
40 : : *
41 : : * On entry, so->currPos describes the current page, which may
42 : : * be pinned but not locked, and so->currPos.itemIndex identifies
43 : : * which item was previously returned.
44 : : *
45 : : * On successful exit, scan->xs_heaptid is set to the TID of the next
46 : : * heap tuple. so->currPos is updated as needed.
47 : : *
48 : : * On failure exit (no more tuples), we return false with pin
49 : : * held on bucket page but no pins or locks held on overflow
50 : : * page.
51 : : */
52 : : bool
11052 scrappy@hub.org 53 :CBC 74393 : _hash_next(IndexScanDesc scan, ScanDirection dir)
54 : : {
8439 tgl@sss.pgh.pa.us 55 : 74393 : Relation rel = scan->indexRelation;
56 : 74393 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
57 : : HashScanPosItem *currItem;
58 : : BlockNumber blkno;
59 : : Buffer buf;
3307 rhaas@postgresql.org 60 : 74393 : bool end_of_scan = false;
61 : :
62 : : /*
63 : : * Advance to the next tuple on the current page; or if done, try to read
64 : : * data from the next or previous page based on the scan direction. Before
65 : : * moving to the next or previous page make sure that we deal with all the
66 : : * killed items.
67 : : */
68 [ + + ]: 74393 : if (ScanDirectionIsForward(dir))
69 : : {
70 [ + + ]: 52382 : if (++so->currPos.itemIndex > so->currPos.lastItem)
71 : : {
72 [ + + ]: 379 : if (so->numKilled > 0)
73 : 11 : _hash_kill_items(scan);
74 : :
75 : 379 : blkno = so->currPos.nextPage;
76 [ + + ]: 379 : if (BlockNumberIsValid(blkno))
77 : : {
78 : 119 : buf = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);
79 [ - + ]: 119 : if (!_hash_readpage(scan, &buf, dir))
3307 rhaas@postgresql.org 80 :UBC 0 : end_of_scan = true;
81 : : }
2 pg@bowt.ie 82 [ + + + + ]:CBC 260 : else if (so->hashso_buc_populated && !so->hashso_buc_split)
83 : : {
84 : 2 : buf = _hash_step_to_split_bucket(scan);
85 : :
86 [ - + ]: 2 : if (!_hash_readpage(scan, &buf, dir))
2 pg@bowt.ie 87 :UBC 0 : end_of_scan = true;
88 : : }
89 : : else
3307 rhaas@postgresql.org 90 :CBC 258 : end_of_scan = true;
91 : : }
92 : : }
93 : : else
94 : : {
95 [ + + ]: 22011 : if (--so->currPos.itemIndex < so->currPos.firstItem)
96 : : {
97 [ - + ]: 58 : if (so->numKilled > 0)
3307 rhaas@postgresql.org 98 :UBC 0 : _hash_kill_items(scan);
99 : :
3307 rhaas@postgresql.org 100 :CBC 58 : blkno = so->currPos.prevPage;
101 [ + + ]: 58 : if (BlockNumberIsValid(blkno))
102 : : {
103 : 52 : buf = _hash_getbuf(rel, blkno, HASH_READ,
104 : : LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
105 : :
106 : : /*
107 : : * We always maintain the pin on bucket page for whole scan
108 : : * operation, so releasing the additional pin we have acquired
109 : : * here.
110 : : */
111 [ + + ]: 52 : if (buf == so->hashso_bucket_buf ||
112 [ - + ]: 48 : buf == so->hashso_split_bucket_buf)
113 : 4 : _hash_dropbuf(rel, buf);
114 : :
115 [ - + ]: 52 : if (!_hash_readpage(scan, &buf, dir))
3307 rhaas@postgresql.org 116 :UBC 0 : end_of_scan = true;
117 : : }
2 pg@bowt.ie 118 [ + + + + ]:CBC 6 : else if (so->hashso_buc_populated && so->hashso_buc_split)
119 : : {
120 : 1 : buf = _hash_step_to_populated_bucket(scan);
121 : :
122 [ - + ]: 1 : if (!_hash_readpage(scan, &buf, dir))
2 pg@bowt.ie 123 :UBC 0 : end_of_scan = true;
124 : : }
125 : : else
3307 rhaas@postgresql.org 126 :CBC 5 : end_of_scan = true;
127 : : }
128 : : }
129 : :
130 [ + + ]: 74393 : if (end_of_scan)
131 : : {
132 : : /*
133 : : * A scan that started during a bucket split ends in the bucket that
134 : : * its direction visits last: forward scans end in the bucket being
135 : : * split, backward scans in the bucket being populated.
136 : : */
2 pg@bowt.ie 137 [ + + - + ]: 263 : Assert(!so->hashso_buc_populated ||
138 : : so->hashso_buc_split == ScanDirectionIsForward(dir));
139 : :
3307 rhaas@postgresql.org 140 : 263 : _hash_dropscanbuf(rel, so);
141 : 263 : HashScanPosInvalidate(so->currPos);
8911 tgl@sss.pgh.pa.us 142 : 263 : return false;
143 : : }
144 : :
145 : : /* OK, itemIndex says what to return */
3307 rhaas@postgresql.org 146 : 74130 : currItem = &so->currPos.items[so->currPos.itemIndex];
2772 andres@anarazel.de 147 : 74130 : scan->xs_heaptid = currItem->heapTid;
148 : :
8911 tgl@sss.pgh.pa.us 149 : 74130 : return true;
150 : : }
151 : :
152 : : /*
153 : : * Advance to next page in a bucket, if any. If we are scanning the bucket
154 : : * being populated during split operation then this function advances to the
155 : : * bucket being split after the last bucket page of bucket being populated.
156 : : */
157 : : static void
3603 rhaas@postgresql.org 158 : 132 : _hash_readnext(IndexScanDesc scan,
159 : : Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
160 : : {
161 : : BlockNumber blkno;
162 : 132 : Relation rel = scan->indexRelation;
163 : 132 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
164 : 132 : bool block_found = false;
165 : :
10627 bruce@momjian.us 166 : 132 : blkno = (*opaquep)->hasho_nextblkno;
167 : :
168 : : /*
169 : : * Retain the pin on primary bucket page till the end of scan. Refer the
170 : : * comments in _hash_first to know the reason of retaining pin.
171 : : */
3603 rhaas@postgresql.org 172 [ + + - + ]: 132 : if (*bufp == so->hashso_bucket_buf || *bufp == so->hashso_split_bucket_buf)
3580 173 : 83 : LockBuffer(*bufp, BUFFER_LOCK_UNLOCK);
174 : : else
3603 175 : 49 : _hash_relbuf(rel, *bufp);
176 : :
10627 bruce@momjian.us 177 : 132 : *bufp = InvalidBuffer;
178 : : /* check for interrupts while we're not holding any buffer lock */
6369 tgl@sss.pgh.pa.us 179 [ - + ]: 132 : CHECK_FOR_INTERRUPTS();
10627 bruce@momjian.us 180 [ + + ]: 132 : if (BlockNumberIsValid(blkno))
181 : : {
7102 tgl@sss.pgh.pa.us 182 : 53 : *bufp = _hash_getbuf(rel, blkno, HASH_READ, LH_OVERFLOW_PAGE);
3603 rhaas@postgresql.org 183 : 53 : block_found = true;
184 : : }
185 [ + + + - ]: 79 : else if (so->hashso_buc_populated && !so->hashso_buc_split)
186 : : {
187 : : /*
188 : : * end of bucket, scan bucket being split if there was a split in
189 : : * progress at the start of scan.
190 : : */
2 pg@bowt.ie 191 : 1 : *bufp = _hash_step_to_split_bucket(scan);
3603 rhaas@postgresql.org 192 : 1 : block_found = true;
193 : : }
194 : :
195 [ + + ]: 132 : if (block_found)
196 : : {
3827 kgrittn@postgresql.o 197 : 54 : *pagep = BufferGetPage(*bufp);
1655 michael@paquier.xyz 198 : 54 : *opaquep = HashPageGetOpaque(*pagep);
199 : : }
11052 scrappy@hub.org 200 : 132 : }
201 : :
202 : : /*
203 : : * Advance to previous page in a bucket, if any. If the current scan has
204 : : * started during split operation then this function advances to bucket
205 : : * being populated after the first bucket page of bucket being split.
206 : : */
207 : : static void
3603 rhaas@postgresql.org 208 :UBC 0 : _hash_readprev(IndexScanDesc scan,
209 : : Buffer *bufp, Page *pagep, HashPageOpaque *opaquep)
210 : : {
211 : : BlockNumber blkno;
212 : 0 : Relation rel = scan->indexRelation;
213 : 0 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
214 : : bool haveprevblk;
215 : :
10627 bruce@momjian.us 216 : 0 : blkno = (*opaquep)->hasho_prevblkno;
217 : :
218 : : /*
219 : : * Retain the pin on primary bucket page till the end of scan. Refer the
220 : : * comments in _hash_first to know the reason of retaining pin.
221 : : */
3603 rhaas@postgresql.org 222 [ # # # # ]: 0 : if (*bufp == so->hashso_bucket_buf || *bufp == so->hashso_split_bucket_buf)
223 : : {
3580 224 : 0 : LockBuffer(*bufp, BUFFER_LOCK_UNLOCK);
3534 225 : 0 : haveprevblk = false;
226 : : }
227 : : else
228 : : {
3603 229 : 0 : _hash_relbuf(rel, *bufp);
3534 230 : 0 : haveprevblk = true;
231 : : }
232 : :
10627 bruce@momjian.us 233 : 0 : *bufp = InvalidBuffer;
234 : : /* check for interrupts while we're not holding any buffer lock */
6369 tgl@sss.pgh.pa.us 235 [ # # ]: 0 : CHECK_FOR_INTERRUPTS();
236 : :
3534 rhaas@postgresql.org 237 [ # # ]: 0 : if (haveprevblk)
238 : : {
239 [ # # ]: 0 : Assert(BlockNumberIsValid(blkno));
7102 tgl@sss.pgh.pa.us 240 : 0 : *bufp = _hash_getbuf(rel, blkno, HASH_READ,
241 : : LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
3827 kgrittn@postgresql.o 242 : 0 : *pagep = BufferGetPage(*bufp);
1655 michael@paquier.xyz 243 : 0 : *opaquep = HashPageGetOpaque(*pagep);
244 : :
245 : : /*
246 : : * We always maintain the pin on bucket page for whole scan operation,
247 : : * so releasing the additional pin we have acquired here.
248 : : */
3603 rhaas@postgresql.org 249 [ # # # # ]: 0 : if (*bufp == so->hashso_bucket_buf || *bufp == so->hashso_split_bucket_buf)
250 : 0 : _hash_dropbuf(rel, *bufp);
251 : : }
252 [ # # # # ]: 0 : else if (so->hashso_buc_populated && so->hashso_buc_split)
253 : : {
254 : : /*
255 : : * end of bucket, scan bucket being populated if there was a split in
256 : : * progress at the start of scan.
257 : : */
2 pg@bowt.ie 258 : 0 : *bufp = _hash_step_to_populated_bucket(scan);
3603 rhaas@postgresql.org 259 : 0 : *pagep = BufferGetPage(*bufp);
1655 michael@paquier.xyz 260 : 0 : *opaquep = HashPageGetOpaque(*pagep);
261 : : }
2 pg@bowt.ie 262 : 0 : }
263 : :
264 : : /*
265 : : * Cross over from the bucket being populated to the bucket being split, on
266 : : * whose primary page we have held a pin since _hash_first. Called on
267 : : * reaching the end of the populated bucket's chain while moving forward
268 : : * through it.
269 : : *
270 : : * Returns the split bucket's primary page, pinned and share-locked, and
271 : : * sets hashso_buc_split to indicate that we are now scanning that bucket.
272 : : */
273 : : static Buffer
2 pg@bowt.ie 274 :CBC 3 : _hash_step_to_split_bucket(IndexScanDesc scan)
275 : : {
276 : 3 : Relation rel = scan->indexRelation;
277 : 3 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
278 : 3 : Buffer buf = so->hashso_split_bucket_buf;
279 : :
280 : : /*
281 : : * buffer for bucket being split must be valid as we acquire the pin on it
282 : : * before the start of scan and retain it till end of scan.
283 : : */
284 [ - + ]: 3 : Assert(BufferIsValid(buf));
285 : :
286 : 3 : LockBuffer(buf, BUFFER_LOCK_SHARE);
287 : 3 : PredicateLockPage(rel, BufferGetBlockNumber(buf), scan->xs_snapshot);
288 : :
289 : 3 : so->hashso_buc_split = true;
290 : :
291 : 3 : return buf;
292 : : }
293 : :
294 : : /*
295 : : * Cross over from the bucket being split back to the bucket being
296 : : * populated, on whose primary page we have held a pin since _hash_first,
297 : : * and walk to the end of its chain (backward scans read chains tail to
298 : : * head). Called on reaching the start of the split bucket's chain while
299 : : * moving backward through it.
300 : : *
301 : : * Returns the last page in the populated bucket's chain, pinned and
302 : : * share-locked, and clears hashso_buc_split: from here on the scan skips
303 : : * the moved-by-split tuples, whose originals it reads in the split
304 : : * bucket, and stops at the populated bucket's primary page instead of
305 : : * crossing again.
306 : : */
307 : : static Buffer
308 : 1 : _hash_step_to_populated_bucket(IndexScanDesc scan)
309 : : {
310 : 1 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
311 : 1 : Buffer buf = so->hashso_bucket_buf;
312 : : Page page;
313 : : HashPageOpaque opaque;
314 : :
315 : : /*
316 : : * buffer for bucket being populated must be valid as we acquire the pin
317 : : * on it before the start of scan and retain it till end of scan.
318 : : */
319 [ - + ]: 1 : Assert(BufferIsValid(buf));
320 : :
321 : 1 : LockBuffer(buf, BUFFER_LOCK_SHARE);
322 : 1 : page = BufferGetPage(buf);
323 : 1 : opaque = HashPageGetOpaque(page);
324 : :
325 : : /* move to the end of bucket chain */
326 [ - + ]: 1 : while (BlockNumberIsValid(opaque->hasho_nextblkno))
2 pg@bowt.ie 327 :UBC 0 : _hash_readnext(scan, &buf, &page, &opaque);
328 : :
2 pg@bowt.ie 329 :CBC 1 : so->hashso_buc_split = false;
330 : :
331 : 1 : return buf;
332 : : }
333 : :
334 : : /*
335 : : * _hash_first() -- Find the first item in a scan.
336 : : *
337 : : * We find the first item (or, if backward scan, the last item) in the
338 : : * index that satisfies the qualification associated with the scan
339 : : * descriptor.
340 : : *
341 : : * On successful exit, if the page containing current index tuple is an
342 : : * overflow page, both pin and lock are released whereas if it is a bucket
343 : : * page then it is pinned but not locked and data about the matching
344 : : * tuple(s) on the page has been loaded into so->currPos,
345 : : * scan->xs_heaptid is set to the heap TID of the current tuple.
346 : : *
347 : : * On failure exit (no more tuples), we return false, with pin held on
348 : : * bucket page but no pins or locks held on overflow page.
349 : : */
350 : : bool
11052 scrappy@hub.org 351 : 345 : _hash_first(IndexScanDesc scan, ScanDirection dir)
352 : : {
8439 tgl@sss.pgh.pa.us 353 : 345 : Relation rel = scan->indexRelation;
354 : 345 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
355 : : ScanKey cur;
356 : : uint32 hashkey;
357 : : Bucket bucket;
358 : : Buffer buf;
359 : : Page page;
360 : : HashPageOpaque opaque;
361 : : HashScanPosItem *currItem;
362 : :
7078 363 [ + + + - : 345 : pgstat_count_index_scan(rel);
+ - - + ]
580 pg@bowt.ie 364 [ + + ]: 345 : if (scan->instrument)
365 : 8 : scan->instrument->nsearches++;
366 : :
367 : : /*
368 : : * We do not support hash scans with no index qualification, because we
369 : : * would have to read the whole index rather than just one bucket. That
370 : : * creates a whole raft of problems, since we haven't got a practical way
371 : : * to lock all the buckets against splits or compactions.
372 : : */
8439 tgl@sss.pgh.pa.us 373 [ - + ]: 345 : if (scan->numberOfKeys < 1)
8439 tgl@sss.pgh.pa.us 374 [ # # ]:UBC 0 : ereport(ERROR,
375 : : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
376 : : errmsg("hash indexes do not support whole-index scans")));
377 : :
378 : : /* There may be more than one index qual, but we hash only the first */
7195 tgl@sss.pgh.pa.us 379 :CBC 345 : cur = &scan->keyData[0];
380 : :
381 : : /* We support only single-column hash indexes */
382 [ - + ]: 345 : Assert(cur->sk_attno == 1);
383 : : /* And there's only one operator strategy, too */
384 [ - + ]: 345 : Assert(cur->sk_strategy == HTEqualStrategyNumber);
385 : :
386 : : /*
387 : : * If the constant in the index qual is NULL, assume it cannot match any
388 : : * items in the index.
389 : : */
390 [ - + ]: 345 : if (cur->sk_flags & SK_ISNULL)
8439 tgl@sss.pgh.pa.us 391 :UBC 0 : return false;
392 : :
393 : : /*
394 : : * Okay to compute the hash key. We want to do this before acquiring any
395 : : * locks, in case a user-defined hash function happens to be slow.
396 : : *
397 : : * If scankey operator is not a cross-type comparison, we can use the
398 : : * cached hash function; otherwise gotta look it up in the catalogs.
399 : : *
400 : : * We support the convention that sk_subtype == InvalidOid means the
401 : : * opclass input type; this is a hack to simplify life for ScanKeyInit().
402 : : */
7195 tgl@sss.pgh.pa.us 403 [ + + ]:CBC 345 : if (cur->sk_subtype == rel->rd_opcintype[0] ||
404 [ + - ]: 4 : cur->sk_subtype == InvalidOid)
405 : 345 : hashkey = _hash_datum2hashkey(rel, cur->sk_argument);
406 : : else
7195 tgl@sss.pgh.pa.us 407 :UBC 0 : hashkey = _hash_datum2hashkey_type(rel, cur->sk_argument,
408 : : cur->sk_subtype);
409 : :
6601 tgl@sss.pgh.pa.us 410 :CBC 345 : so->hashso_sk_hash = hashkey;
411 : :
3534 rhaas@postgresql.org 412 : 345 : buf = _hash_getbucketbuf_from_hashkey(rel, hashkey, HASH_READ, NULL);
3110 teodor@sigaev.ru 413 : 345 : PredicateLockPage(rel, BufferGetBlockNumber(buf), scan->xs_snapshot);
3827 kgrittn@postgresql.o 414 : 345 : page = BufferGetPage(buf);
1655 michael@paquier.xyz 415 : 345 : opaque = HashPageGetOpaque(page);
3534 rhaas@postgresql.org 416 : 345 : bucket = opaque->hasho_bucket;
417 : :
3603 418 : 345 : so->hashso_bucket_buf = buf;
419 : :
420 : : /*
421 : : * If a bucket split is in progress, then while scanning the bucket being
422 : : * populated, we need to skip tuples that were copied from bucket being
423 : : * split. We also need to maintain a pin on the bucket being split to
424 : : * ensure that split-cleanup work done by vacuum doesn't remove tuples
425 : : * from it till this scan is done. We need to maintain a pin on the
426 : : * bucket being populated to ensure that vacuum doesn't squeeze that
427 : : * bucket till this scan is complete; otherwise, the ordering of tuples
428 : : * can't be maintained during forward and backward scans. Here, we have
429 : : * to be cautious about locking order: first, acquire the lock on bucket
430 : : * being split; then, release the lock on it but not the pin; then,
431 : : * acquire a lock on bucket being populated and again re-verify whether
432 : : * the bucket split is still in progress. Acquiring the lock on bucket
433 : : * being split first ensures that the vacuum waits for this scan to
434 : : * finish.
435 : : */
436 [ + + ]: 345 : if (H_BUCKET_BEING_POPULATED(opaque))
437 : : {
438 : : BlockNumber old_blkno;
439 : : Buffer old_buf;
440 : :
441 : 3 : old_blkno = _hash_get_oldblock_from_newbucket(rel, bucket);
442 : :
443 : : /*
444 : : * release the lock on new bucket and re-acquire it after acquiring
445 : : * the lock on old bucket.
446 : : */
3580 447 : 3 : LockBuffer(buf, BUFFER_LOCK_UNLOCK);
448 : :
3603 449 : 3 : old_buf = _hash_getbuf(rel, old_blkno, HASH_READ, LH_BUCKET_PAGE);
450 : :
451 : : /*
452 : : * remember the split bucket buffer so as to use it later for
453 : : * scanning.
454 : : */
455 : 3 : so->hashso_split_bucket_buf = old_buf;
3580 456 : 3 : LockBuffer(old_buf, BUFFER_LOCK_UNLOCK);
457 : :
458 : 3 : LockBuffer(buf, BUFFER_LOCK_SHARE);
3603 459 : 3 : page = BufferGetPage(buf);
1655 michael@paquier.xyz 460 : 3 : opaque = HashPageGetOpaque(page);
3603 rhaas@postgresql.org 461 [ - + ]: 3 : Assert(opaque->hasho_bucket == bucket);
462 : :
463 [ + - ]: 3 : if (H_BUCKET_BEING_POPULATED(opaque))
464 : 3 : so->hashso_buc_populated = true;
465 : : else
466 : : {
3603 rhaas@postgresql.org 467 :UBC 0 : _hash_dropbuf(rel, so->hashso_split_bucket_buf);
468 : 0 : so->hashso_split_bucket_buf = InvalidBuffer;
469 : : }
470 : : }
471 : :
472 : : /* If a backwards scan is requested, move to the end of the chain */
10627 bruce@momjian.us 473 [ + + ]:CBC 345 : if (ScanDirectionIsBackward(dir))
474 : : {
475 : : /*
476 : : * Backward scans that start during split needs to start from end of
477 : : * bucket being split.
478 : : */
3603 rhaas@postgresql.org 479 [ + + ]: 58 : while (BlockNumberIsValid(opaque->hasho_nextblkno) ||
480 [ + + + + ]: 6 : (so->hashso_buc_populated && !so->hashso_buc_split))
481 : 53 : _hash_readnext(scan, &buf, &page, &opaque);
482 : : }
483 : :
484 : : /* remember which buffer we have pinned, if any */
3307 485 [ - + ]: 345 : Assert(BufferIsInvalid(so->currPos.buf));
486 : 345 : so->currPos.buf = buf;
487 : :
488 : : /* Now find all the tuples satisfying the qualification from a page */
489 [ + + ]: 345 : if (!_hash_readpage(scan, &buf, dir))
8911 tgl@sss.pgh.pa.us 490 : 78 : return false;
491 : :
492 : : /* OK, itemIndex says what to return */
3307 rhaas@postgresql.org 493 : 267 : currItem = &so->currPos.items[so->currPos.itemIndex];
2772 andres@anarazel.de 494 : 267 : scan->xs_heaptid = currItem->heapTid;
495 : :
496 : : /* if we're here, _hash_readpage found a valid tuples */
8911 tgl@sss.pgh.pa.us 497 : 267 : return true;
498 : : }
499 : :
500 : : /*
501 : : * _hash_readpage() -- Load data from current index page into so->currPos
502 : : *
503 : : * We scan all the items in the current index page and save them into
504 : : * so->currPos if it satisfies the qualification. If no matching items
505 : : * are found in the current page, we move to the next or previous page
506 : : * in a bucket chain as indicated by the direction.
507 : : *
508 : : * Return true if any matching items are found else return false.
509 : : */
510 : : static bool
3307 rhaas@postgresql.org 511 : 519 : _hash_readpage(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
512 : : {
8439 tgl@sss.pgh.pa.us 513 : 519 : Relation rel = scan->indexRelation;
514 : 519 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
515 : : Buffer buf;
516 : : Page page;
517 : : HashPageOpaque opaque;
518 : : OffsetNumber offnum;
519 : : uint16 itemIndex;
520 : :
10627 bruce@momjian.us 521 : 519 : buf = *bufP;
3307 rhaas@postgresql.org 522 [ - + ]: 519 : Assert(BufferIsValid(buf));
7645 tgl@sss.pgh.pa.us 523 : 519 : _hash_checkpage(rel, buf, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
3827 kgrittn@postgresql.o 524 : 519 : page = BufferGetPage(buf);
1655 michael@paquier.xyz 525 : 519 : opaque = HashPageGetOpaque(page);
526 : :
3307 rhaas@postgresql.org 527 : 519 : so->currPos.buf = buf;
528 : 519 : so->currPos.currPage = BufferGetBlockNumber(buf);
529 : :
530 [ + + ]: 519 : if (ScanDirectionIsForward(dir))
531 : : {
532 : 461 : BlockNumber prev_blkno = InvalidBlockNumber;
533 : :
534 : : for (;;)
535 : : {
536 : : /* new page, locate starting position by binary search */
537 : 462 : offnum = _hash_binsearch(page, so->hashso_sk_hash);
538 : :
539 : 462 : itemIndex = _hash_load_qualified_items(scan, page, offnum, dir);
540 : :
541 [ + + ]: 462 : if (itemIndex != 0)
10626 bruce@momjian.us 542 : 383 : break;
543 : :
544 : : /*
545 : : * Could not find any matching tuples in the current page, move to
546 : : * the next page. Before leaving the current page, deal with any
547 : : * killed items.
548 : : */
3307 rhaas@postgresql.org 549 [ - + ]: 79 : if (so->numKilled > 0)
3307 rhaas@postgresql.org 550 :UBC 0 : _hash_kill_items(scan);
551 : :
552 : : /*
553 : : * If this is a primary bucket page, hasho_prevblkno is not a real
554 : : * block number.
555 : : */
3307 rhaas@postgresql.org 556 [ + + ]:CBC 79 : if (so->currPos.buf == so->hashso_bucket_buf ||
557 [ - + ]: 1 : so->currPos.buf == so->hashso_split_bucket_buf)
558 : 78 : prev_blkno = InvalidBlockNumber;
559 : : else
560 : 1 : prev_blkno = opaque->hasho_prevblkno;
561 : :
562 : 79 : _hash_readnext(scan, &buf, &page, &opaque);
563 [ + + ]: 79 : if (BufferIsValid(buf))
564 : : {
565 : 1 : so->currPos.buf = buf;
566 : 1 : so->currPos.currPage = BufferGetBlockNumber(buf);
567 : : }
568 : : else
569 : : {
570 : : /*
571 : : * Remember next and previous block numbers for scrollable
572 : : * cursors to know the start position and return false
573 : : * indicating that no more matching tuples were found. Also,
574 : : * don't reset currPage or lsn, because we expect
575 : : * _hash_kill_items to be called for the old page after this
576 : : * function returns.
577 : : */
578 : 78 : so->currPos.prevPage = prev_blkno;
579 : 78 : so->currPos.nextPage = InvalidBlockNumber;
580 : 78 : so->currPos.buf = buf;
581 : 78 : return false;
582 : : }
583 : : }
584 : :
585 : 383 : so->currPos.firstItem = 0;
586 : 383 : so->currPos.lastItem = itemIndex - 1;
587 : 383 : so->currPos.itemIndex = 0;
588 : : }
589 : : else
590 : : {
591 : 58 : BlockNumber next_blkno = InvalidBlockNumber;
592 : :
593 : : for (;;)
594 : : {
595 : : /* new page, locate starting position by binary search */
596 : 58 : offnum = _hash_binsearch_last(page, so->hashso_sk_hash);
597 : :
598 : 58 : itemIndex = _hash_load_qualified_items(scan, page, offnum, dir);
599 : :
600 [ + - ]: 58 : if (itemIndex != MaxIndexTuplesPerPage)
10626 bruce@momjian.us 601 : 58 : break;
602 : :
603 : : /*
604 : : * Could not find any matching tuples in the current page, move to
605 : : * the previous page. Before leaving the current page, deal with
606 : : * any killed items.
607 : : */
3307 rhaas@postgresql.org 608 [ # # ]:UBC 0 : if (so->numKilled > 0)
609 : 0 : _hash_kill_items(scan);
610 : :
611 [ # # ]: 0 : if (so->currPos.buf == so->hashso_bucket_buf ||
612 [ # # ]: 0 : so->currPos.buf == so->hashso_split_bucket_buf)
613 : 0 : next_blkno = opaque->hasho_nextblkno;
614 : :
615 : 0 : _hash_readprev(scan, &buf, &page, &opaque);
616 [ # # ]: 0 : if (BufferIsValid(buf))
617 : : {
618 : 0 : so->currPos.buf = buf;
619 : 0 : so->currPos.currPage = BufferGetBlockNumber(buf);
620 : : }
621 : : else
622 : : {
623 : : /*
624 : : * Remember next and previous block numbers for scrollable
625 : : * cursors to know the start position and return false
626 : : * indicating that no more matching tuples were found. Also,
627 : : * don't reset currPage or lsn, because we expect
628 : : * _hash_kill_items to be called for the old page after this
629 : : * function returns.
630 : : */
631 : 0 : so->currPos.prevPage = InvalidBlockNumber;
632 : 0 : so->currPos.nextPage = next_blkno;
633 : 0 : so->currPos.buf = buf;
634 : 0 : return false;
635 : : }
636 : : }
637 : :
3307 rhaas@postgresql.org 638 :CBC 58 : so->currPos.firstItem = itemIndex;
639 : 58 : so->currPos.lastItem = MaxIndexTuplesPerPage - 1;
640 : 58 : so->currPos.itemIndex = MaxIndexTuplesPerPage - 1;
641 : : }
642 : :
643 [ + + ]: 441 : if (so->currPos.buf == so->hashso_bucket_buf ||
644 [ + + ]: 174 : so->currPos.buf == so->hashso_split_bucket_buf)
645 : : {
646 : 270 : so->currPos.prevPage = InvalidBlockNumber;
647 : 270 : so->currPos.nextPage = opaque->hasho_nextblkno;
648 : 270 : LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);
649 : : }
650 : : else
651 : : {
652 : 171 : so->currPos.prevPage = opaque->hasho_prevblkno;
653 : 171 : so->currPos.nextPage = opaque->hasho_nextblkno;
654 : 171 : _hash_relbuf(rel, so->currPos.buf);
655 : 171 : so->currPos.buf = InvalidBuffer;
656 : : }
657 : :
658 [ - + ]: 441 : Assert(so->currPos.firstItem <= so->currPos.lastItem);
659 : 441 : return true;
660 : : }
661 : :
662 : : /*
663 : : * Load all the qualified items from a current index page
664 : : * into so->currPos. Helper function for _hash_readpage.
665 : : */
666 : : static int
667 : 520 : _hash_load_qualified_items(IndexScanDesc scan, Page page,
668 : : OffsetNumber offnum, ScanDirection dir)
669 : : {
670 : 520 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
671 : : IndexTuple itup;
672 : : int itemIndex;
673 : : OffsetNumber maxoff;
674 : :
675 : 520 : maxoff = PageGetMaxOffsetNumber(page);
676 : :
677 [ + + ]: 520 : if (ScanDirectionIsForward(dir))
678 : : {
679 : : /* load items[] in ascending order */
680 : 462 : itemIndex = 0;
681 : :
682 [ + + ]: 53257 : while (offnum <= maxoff)
683 : : {
684 [ - + ]: 52985 : Assert(offnum >= FirstOffsetNumber);
685 : 52985 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
686 : :
687 : : /*
688 : : * skip the tuples that are moved by split operation for the scan
689 : : * that has started when split was in progress. Also, skip the
690 : : * tuples that are marked as dead.
691 : : */
692 [ + + + + ]: 52985 : if ((so->hashso_buc_populated && !so->hashso_buc_split &&
693 [ + - ]: 2 : (itup->t_info & INDEX_MOVED_BY_SPLIT_MASK)) ||
694 [ + - ]: 52985 : (scan->ignore_killed_tuples &&
695 [ + + ]: 52985 : (ItemIdIsDead(PageGetItemId(page, offnum)))))
696 : : {
697 : 409 : offnum = OffsetNumberNext(offnum); /* move forward */
698 : 409 : continue;
699 : : }
700 : :
701 [ + + + - ]: 104962 : if (so->hashso_sk_hash == _hash_get_indextuple_hashkey(itup) &&
702 : 52386 : _hash_checkqual(scan, itup))
703 : : {
704 : : /* tuple is qualified, so remember it */
705 : 52386 : _hash_saveitem(so, itemIndex, offnum, itup);
706 : 52386 : itemIndex++;
707 : : }
708 : : else
709 : : {
710 : : /*
711 : : * No more matching tuples exist in this page. so, exit while
712 : : * loop.
713 : : */
714 : : break;
715 : : }
716 : :
717 : 52386 : offnum = OffsetNumberNext(offnum);
718 : : }
719 : :
720 [ - + ]: 462 : Assert(itemIndex <= MaxIndexTuplesPerPage);
721 : 462 : return itemIndex;
722 : : }
723 : : else
724 : : {
725 : : /* load items[] in descending order */
726 : 58 : itemIndex = MaxIndexTuplesPerPage;
727 : :
728 [ + + ]: 22069 : while (offnum >= FirstOffsetNumber)
729 : : {
730 [ - + ]: 22012 : Assert(offnum <= maxoff);
731 : 22012 : itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
732 : :
733 : : /*
734 : : * skip the tuples that are moved by split operation for the scan
735 : : * that has started when split was in progress. Also, skip the
736 : : * tuples that are marked as dead.
737 : : */
738 [ + + + + ]: 22012 : if ((so->hashso_buc_populated && !so->hashso_buc_split &&
739 [ + - ]: 1 : (itup->t_info & INDEX_MOVED_BY_SPLIT_MASK)) ||
740 [ + - ]: 22012 : (scan->ignore_killed_tuples &&
741 [ - + ]: 22012 : (ItemIdIsDead(PageGetItemId(page, offnum)))))
742 : : {
3307 rhaas@postgresql.org 743 :UBC 0 : offnum = OffsetNumberPrev(offnum); /* move back */
744 : 0 : continue;
745 : : }
746 : :
3307 rhaas@postgresql.org 747 [ + + + - ]:CBC 44023 : if (so->hashso_sk_hash == _hash_get_indextuple_hashkey(itup) &&
748 : 22011 : _hash_checkqual(scan, itup))
749 : : {
750 : 22011 : itemIndex--;
751 : : /* tuple is qualified, so remember it */
752 : 22011 : _hash_saveitem(so, itemIndex, offnum, itup);
753 : : }
754 : : else
755 : : {
756 : : /*
757 : : * No more matching tuples exist in this page. so, exit while
758 : : * loop.
759 : : */
760 : : break;
761 : : }
762 : :
763 : 22011 : offnum = OffsetNumberPrev(offnum);
764 : : }
765 : :
766 [ - + ]: 58 : Assert(itemIndex >= 0);
767 : 58 : return itemIndex;
768 : : }
769 : : }
770 : :
771 : : /* Save an index item into so->currPos.items[itemIndex] */
772 : : static inline void
773 : 74397 : _hash_saveitem(HashScanOpaque so, int itemIndex,
774 : : OffsetNumber offnum, IndexTuple itup)
775 : : {
776 : 74397 : HashScanPosItem *currItem = &so->currPos.items[itemIndex];
777 : :
778 : 74397 : currItem->heapTid = itup->t_tid;
779 : 74397 : currItem->indexOffset = offnum;
11052 scrappy@hub.org 780 : 74397 : }
|
