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