Debian Codegraph @

src/backend/access/hash/hash.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * hash.c
4 * Implementation of Margo Seltzer's Hashing package for postgres.
5 *
6 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/access/hash/hash.c
12 *
13 * NOTES
14 * This file contains only the public interface routines.
15 *
16 *-------------------------------------------------------------------------
17 */
18
19 #include "postgres.h"
20
21 #include "access/hash.h"
22 #include "access/hash_xlog.h"
23 #include "access/relscan.h"
24 #include "access/stratnum.h"
25 #include "access/tableam.h"
26 #include "access/xloginsert.h"
27 #include "commands/progress.h"
28 #include "commands/vacuum.h"
29 #include "miscadmin.h"
30 #include "nodes/execnodes.h"
31 #include "optimizer/plancat.h"
32 #include "pgstat.h"
33 #include "utils/fmgrprotos.h"
34 #include "utils/index_selfuncs.h"
35 #include "utils/rel.h"
36
37 /* Working state for hashbuild and its callback */
38 typedef struct
39 {
40 HSpool *spool; /* NULL if not using spooling */
41 double indtuples; /* # tuples accepted into index */
42 Relation heapRel; /* heap relation descriptor */
43 } HashBuildState;
44
45 static void hashbuildCallback(Relation index,
46 ItemPointer tid,
47 Datum *values,
48 bool *isnull,
49 bool tupleIsAlive,
50 void *state);
51
52
53 /*
54 * Hash handler function: return IndexAmRoutine with access method parameters
55 * and callbacks.
56 */
57 Datum
58 hashhandler(PG_FUNCTION_ARGS)
59 {
60 IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
61
62 amroutine->amstrategies = HTMaxStrategyNumber;
63 amroutine->amsupport = HASHNProcs;
64 amroutine->amoptsprocnum = HASHOPTIONS_PROC;
65 amroutine->amcanorder = false;
66 amroutine->amcanorderbyop = false;
67 amroutine->amcanhash = true;
68 amroutine->amconsistentequality = true;
69 amroutine->amconsistentordering = false;
70 amroutine->amcanbackward = true;
71 amroutine->amcanunique = false;
72 amroutine->amcanmulticol = false;
73 amroutine->amoptionalkey = false;
74 amroutine->amsearcharray = false;
75 amroutine->amsearchnulls = false;
76 amroutine->amstorage = false;
77 amroutine->amclusterable = false;
78 amroutine->ampredlocks = true;
79 amroutine->amcanparallel = false;
80 amroutine->amcanbuildparallel = false;
81 amroutine->amcaninclude = false;
82 amroutine->amusemaintenanceworkmem = false;
83 amroutine->amsummarizing = false;
84 amroutine->amparallelvacuumoptions =
85 VACUUM_OPTION_PARALLEL_BULKDEL;
86 amroutine->amkeytype = INT4OID;
87
88 amroutine->ambuild = hashbuild;
89 amroutine->ambuildempty = hashbuildempty;
90 amroutine->aminsert = hashinsert;
91 amroutine->aminsertcleanup = NULL;
92 amroutine->ambulkdelete = hashbulkdelete;
93 amroutine->amvacuumcleanup = hashvacuumcleanup;
94 amroutine->amcanreturn = NULL;
95 amroutine->amcostestimate = hashcostestimate;
96 amroutine->amgettreeheight = NULL;
97 amroutine->amoptions = hashoptions;
98 amroutine->amproperty = NULL;
99 amroutine->ambuildphasename = NULL;
100 amroutine->amvalidate = hashvalidate;
101 amroutine->amadjustmembers = hashadjustmembers;
102 amroutine->ambeginscan = hashbeginscan;
103 amroutine->amrescan = hashrescan;
104 amroutine->amgettuple = hashgettuple;
105 amroutine->amgetbitmap = hashgetbitmap;
106 amroutine->amendscan = hashendscan;
107 amroutine->ammarkpos = NULL;
108 amroutine->amrestrpos = NULL;
109 amroutine->amestimateparallelscan = NULL;
110 amroutine->aminitparallelscan = NULL;
111 amroutine->amparallelrescan = NULL;
112 amroutine->amtranslatestrategy = hashtranslatestrategy;
113 amroutine->amtranslatecmptype = hashtranslatecmptype;
114
115 PG_RETURN_POINTER(amroutine);
116 }
117
118 /*
119 * hashbuild() -- build a new hash index.
120 */
121 IndexBuildResult *
122 hashbuild(Relation heap, Relation index, IndexInfo *indexInfo)
123 {
124 IndexBuildResult *result;
125 BlockNumber relpages;
126 double reltuples;
127 double allvisfrac;
128 uint32 num_buckets;
129 Size sort_threshold;
130 HashBuildState buildstate;
131
132 /*
133 * We expect to be called exactly once for any index relation. If that's
134 * not the case, big trouble's what we have.
135 */
136 if (RelationGetNumberOfBlocks(index) != 0)
137 elog(ERROR, "index \"%s\" already contains data",
138 RelationGetRelationName(index));
139
140 /* Estimate the number of rows currently present in the table */
141 estimate_rel_size(heap, NULL, &relpages, &reltuples, &allvisfrac);
142
143 /* Initialize the hash index metadata page and initial buckets */
144 num_buckets = _hash_init(index, reltuples, MAIN_FORKNUM);
145
146 /*
147 * If we just insert the tuples into the index in scan order, then
148 * (assuming their hash codes are pretty random) there will be no locality
149 * of access to the index, and if the index is bigger than available RAM
150 * then we'll thrash horribly. To prevent that scenario, we can sort the
151 * tuples by (expected) bucket number. However, such a sort is useless
152 * overhead when the index does fit in RAM. We choose to sort if the
153 * initial index size exceeds maintenance_work_mem, or the number of
154 * buffers usable for the index, whichever is less. (Limiting by the
155 * number of buffers should reduce thrashing between PG buffers and kernel
156 * buffers, which seems useful even if no physical I/O results. Limiting
157 * by maintenance_work_mem is useful to allow easy testing of the sort
158 * code path, and may be useful to DBAs as an additional control knob.)
159 *
160 * NOTE: this test will need adjustment if a bucket is ever different from
161 * one page. Also, "initial index size" accounting does not include the
162 * metapage, nor the first bitmap page.
163 */
164 sort_threshold = (maintenance_work_mem * (Size) 1024) / BLCKSZ;
165 if (index->rd_rel->relpersistence != RELPERSISTENCE_TEMP)
166 sort_threshold = Min(sort_threshold, NBuffers);
167 else
168 sort_threshold = Min(sort_threshold, NLocBuffer);
169
170 if (num_buckets >= sort_threshold)
171 buildstate.spool = _h_spoolinit(heap, index, num_buckets);
172 else
173 buildstate.spool = NULL;
174
175 /* prepare to build the index */
176 buildstate.indtuples = 0;
177 buildstate.heapRel = heap;
178
179 /* do the heap scan */
180 reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
181 hashbuildCallback,
182 &buildstate, NULL);
183 pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_TOTAL,
184 buildstate.indtuples);
185
186 if (buildstate.spool)
187 {
188 /* sort the tuples and insert them into the index */
189 _h_indexbuild(buildstate.spool, buildstate.heapRel);
190 _h_spooldestroy(buildstate.spool);
191 }
192
193 /*
194 * Return statistics
195 */
196 result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
197
198 result->heap_tuples = reltuples;
199 result->index_tuples = buildstate.indtuples;
200
201 return result;
202 }
203
204 /*
205 * hashbuildempty() -- build an empty hash index in the initialization fork
206 */
207 void
208 hashbuildempty(Relation index)
209 {
210 _hash_init(index, 0, INIT_FORKNUM);
211 }
212
213 /*
214 * Per-tuple callback for table_index_build_scan
215 */
216 static void
217 hashbuildCallback(Relation index,
218 ItemPointer tid,
219 Datum *values,
220 bool *isnull,
221 bool tupleIsAlive,
222 void *state)
223 {
224 HashBuildState *buildstate = (HashBuildState *) state;
225 Datum index_values[1];
226 bool index_isnull[1];
227 IndexTuple itup;
228
229 /* convert data to a hash key; on failure, do not insert anything */
230 if (!_hash_convert_tuple(index,
231 values, isnull,
232 index_values, index_isnull))
233 return;
234
235 /* Either spool the tuple for sorting, or just put it into the index */
236 if (buildstate->spool)
237 _h_spool(buildstate->spool, tid, index_values, index_isnull);
238 else
239 {
240 /* form an index tuple and point it at the heap tuple */
241 itup = index_form_tuple(RelationGetDescr(index),
242 index_values, index_isnull);
243 itup->t_tid = *tid;
244 _hash_doinsert(index, itup, buildstate->heapRel, false);
245 pfree(itup);
246 }
247
248 buildstate->indtuples += 1;
249 }
250
251 /*
252 * hashinsert() -- insert an index tuple into a hash table.
253 *
254 * Hash on the heap tuple's key, form an index tuple with hash code.
255 * Find the appropriate location for the new tuple, and put it there.
256 */
257 bool
258 hashinsert(Relation rel, Datum *values, bool *isnull,
259 ItemPointer ht_ctid, Relation heapRel,
260 IndexUniqueCheck checkUnique,
261 bool indexUnchanged,
262 IndexInfo *indexInfo)
263 {
264 Datum index_values[1];
265 bool index_isnull[1];
266 IndexTuple itup;
267
268 /* convert data to a hash key; on failure, do not insert anything */
269 if (!_hash_convert_tuple(rel,
270 values, isnull,
271 index_values, index_isnull))
272 return false;
273
274 /* form an index tuple and point it at the heap tuple */
275 itup = index_form_tuple(RelationGetDescr(rel), index_values, index_isnull);
276 itup->t_tid = *ht_ctid;
277
278 _hash_doinsert(rel, itup, heapRel, false);
279
280 pfree(itup);
281
282 return false;
283 }
284
285
286 /*
287 * hashgettuple() -- Get the next tuple in the scan.
288 */
289 bool
290 hashgettuple(IndexScanDesc scan, ScanDirection dir)
291 {
292 HashScanOpaque so = (HashScanOpaque) scan->opaque;
293 bool res;
294
295 /* Hash indexes are always lossy since we store only the hash code */
296 scan->xs_recheck = true;
297
298 /*
299 * If we've already initialized this scan, we can just advance it in the
300 * appropriate direction. If we haven't done so yet, we call a routine to
301 * get the first item in the scan.
302 */
303 if (!HashScanPosIsValid(so->currPos))
304 res = _hash_first(scan, dir);
305 else
306 {
307 /*
308 * Check to see if we should kill the previously-fetched tuple.
309 */
310 if (scan->kill_prior_tuple)
311 {
312 /*
313 * Yes, so remember it for later. (We'll deal with all such tuples
314 * at once right after leaving the index page or at end of scan.)
315 * In case if caller reverses the indexscan direction it is quite
316 * possible that the same item might get entered multiple times.
317 * But, we don't detect that; instead, we just forget any excess
318 * entries.
319 */
320 if (so->killedItems == NULL)
321 so->killedItems = (int *)
322 palloc(MaxIndexTuplesPerPage * sizeof(int));
323
324 if (so->numKilled < MaxIndexTuplesPerPage)
325 so->killedItems[so->numKilled++] = so->currPos.itemIndex;
326 }
327
328 /*
329 * Now continue the scan.
330 */
331 res = _hash_next(scan, dir);
332 }
333
334 return res;
335 }
336
337
338 /*
339 * hashgetbitmap() -- get all tuples at once
340 */
341 int64
342 hashgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
343 {
344 HashScanOpaque so = (HashScanOpaque) scan->opaque;
345 bool res;
346 int64 ntids = 0;
347 HashScanPosItem *currItem;
348
349 res = _hash_first(scan, ForwardScanDirection);
350
351 while (res)
352 {
353 currItem = &so->currPos.items[so->currPos.itemIndex];
354
355 /*
356 * _hash_first and _hash_next handle eliminate dead index entries
357 * whenever scan->ignore_killed_tuples is true. Therefore, there's
358 * nothing to do here except add the results to the TIDBitmap.
359 */
360 tbm_add_tuples(tbm, &(currItem->heapTid), 1, true);
361 ntids++;
362
363 res = _hash_next(scan, ForwardScanDirection);
364 }
365
366 return ntids;
367 }
368
369
370 /*
371 * hashbeginscan() -- start a scan on a hash index
372 */
373 IndexScanDesc
374 hashbeginscan(Relation rel, int nkeys, int norderbys)
375 {
376 IndexScanDesc scan;
377 HashScanOpaque so;
378
379 /* no order by operators allowed */
380 Assert(norderbys == 0);
381
382 scan = RelationGetIndexScan(rel, nkeys, norderbys);
383
384 so = (HashScanOpaque) palloc(sizeof(HashScanOpaqueData));
385 HashScanPosInvalidate(so->currPos);
386 so->hashso_bucket_buf = InvalidBuffer;
387 so->hashso_split_bucket_buf = InvalidBuffer;
388
389 so->hashso_buc_populated = false;
390 so->hashso_buc_split = false;
391
392 so->killedItems = NULL;
393 so->numKilled = 0;
394
395 scan->opaque = so;
396
397 return scan;
398 }
399
400 /*
401 * hashrescan() -- rescan an index relation
402 */
403 void
404 hashrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
405 ScanKey orderbys, int norderbys)
406 {
407 HashScanOpaque so = (HashScanOpaque) scan->opaque;
408 Relation rel = scan->indexRelation;
409
410 if (HashScanPosIsValid(so->currPos))
411 {
412 /* Before leaving current page, deal with any killed items */
413 if (so->numKilled > 0)
414 _hash_kill_items(scan);
415 }
416
417 _hash_dropscanbuf(rel, so);
418
419 /* set position invalid (this will cause _hash_first call) */
420 HashScanPosInvalidate(so->currPos);
421
422 /* Update scan key, if a new one is given */
423 if (scankey && scan->numberOfKeys > 0)
424 memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
425
426 so->hashso_buc_populated = false;
427 so->hashso_buc_split = false;
428 }
429
430 /*
431 * hashendscan() -- close down a scan
432 */
433 void
434 hashendscan(IndexScanDesc scan)
435 {
436 HashScanOpaque so = (HashScanOpaque) scan->opaque;
437 Relation rel = scan->indexRelation;
438
439 if (HashScanPosIsValid(so->currPos))
440 {
441 /* Before leaving current page, deal with any killed items */
442 if (so->numKilled > 0)
443 _hash_kill_items(scan);
444 }
445
446 _hash_dropscanbuf(rel, so);
447
448 if (so->killedItems != NULL)
449 pfree(so->killedItems);
450 pfree(so);
451 scan->opaque = NULL;
452 }
453
454 /*
455 * Bulk deletion of all index entries pointing to a set of heap tuples.
456 * The set of target tuples is specified via a callback routine that tells
457 * whether any given heap tuple (identified by ItemPointer) is being deleted.
458 *
459 * This function also deletes the tuples that are moved by split to other
460 * bucket.
461 *
462 * Result: a palloc'd struct containing statistical info for VACUUM displays.
463 */
464 IndexBulkDeleteResult *
465 hashbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
466 IndexBulkDeleteCallback callback, void *callback_state)
467 {
468 Relation rel = info->index;
469 double tuples_removed;
470 double num_index_tuples;
471 double orig_ntuples;
472 Bucket orig_maxbucket;
473 Bucket cur_maxbucket;
474 Bucket cur_bucket;
475 Buffer metabuf = InvalidBuffer;
476 HashMetaPage metap;
477 HashMetaPage cachedmetap;
478
479 tuples_removed = 0;
480 num_index_tuples = 0;
481
482 /*
483 * We need a copy of the metapage so that we can use its hashm_spares[]
484 * values to compute bucket page addresses, but a cached copy should be
485 * good enough. (If not, we'll detect that further down and refresh the
486 * cache as necessary.)
487 */
488 cachedmetap = _hash_getcachedmetap(rel, &metabuf, false);
489 Assert(cachedmetap != NULL);
490
491 orig_maxbucket = cachedmetap->hashm_maxbucket;
492 orig_ntuples = cachedmetap->hashm_ntuples;
493
494 /* Scan the buckets that we know exist */
495 cur_bucket = 0;
496 cur_maxbucket = orig_maxbucket;
497
498 loop_top:
499 while (cur_bucket <= cur_maxbucket)
500 {
501 BlockNumber bucket_blkno;
502 BlockNumber blkno;
503 Buffer bucket_buf;
504 Buffer buf;
505 HashPageOpaque bucket_opaque;
506 Page page;
507 bool split_cleanup = false;
508
509 /* Get address of bucket's start page */
510 bucket_blkno = BUCKET_TO_BLKNO(cachedmetap, cur_bucket);
511
512 blkno = bucket_blkno;
513
514 /*
515 * We need to acquire a cleanup lock on the primary bucket page to out
516 * wait concurrent scans before deleting the dead tuples.
517 */
518 buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL, info->strategy);
519 LockBufferForCleanup(buf);
520 _hash_checkpage(rel, buf, LH_BUCKET_PAGE);
521
522 page = BufferGetPage(buf);
523 bucket_opaque = HashPageGetOpaque(page);
524
525 /*
526 * If the bucket contains tuples that are moved by split, then we need
527 * to delete such tuples. We can't delete such tuples if the split
528 * operation on bucket is not finished as those are needed by scans.
529 */
530 if (!H_BUCKET_BEING_SPLIT(bucket_opaque) &&
531 H_NEEDS_SPLIT_CLEANUP(bucket_opaque))
532 {
533 split_cleanup = true;
534
535 /*
536 * This bucket might have been split since we last held a lock on
537 * the metapage. If so, hashm_maxbucket, hashm_highmask and
538 * hashm_lowmask might be old enough to cause us to fail to remove
539 * tuples left behind by the most recent split. To prevent that,
540 * now that the primary page of the target bucket has been locked
541 * (and thus can't be further split), check whether we need to
542 * update our cached metapage data.
543 */
544 Assert(bucket_opaque->hasho_prevblkno != InvalidBlockNumber);
545 if (bucket_opaque->hasho_prevblkno > cachedmetap->hashm_maxbucket)
546 {
547 cachedmetap = _hash_getcachedmetap(rel, &metabuf, true);
548 Assert(cachedmetap != NULL);
549 }
550 }
551
552 bucket_buf = buf;
553
554 hashbucketcleanup(rel, cur_bucket, bucket_buf, blkno, info->strategy,
555 cachedmetap->hashm_maxbucket,
556 cachedmetap->hashm_highmask,
557 cachedmetap->hashm_lowmask, &tuples_removed,
558 &num_index_tuples, split_cleanup,
559 callback, callback_state);
560
561 _hash_dropbuf(rel, bucket_buf);
562
563 /* Advance to next bucket */
564 cur_bucket++;
565 }
566
567 if (BufferIsInvalid(metabuf))
568 metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_NOLOCK, LH_META_PAGE);
569
570 /* Write-lock metapage and check for split since we started */
571 LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
572 metap = HashPageGetMeta(BufferGetPage(metabuf));
573
574 if (cur_maxbucket != metap->hashm_maxbucket)
575 {
576 /* There's been a split, so process the additional bucket(s) */
577 LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
578 cachedmetap = _hash_getcachedmetap(rel, &metabuf, true);
579 Assert(cachedmetap != NULL);
580 cur_maxbucket = cachedmetap->hashm_maxbucket;
581 goto loop_top;
582 }
583
584 /* Okay, we're really done. Update tuple count in metapage. */
585 START_CRIT_SECTION();
586
587 if (orig_maxbucket == metap->hashm_maxbucket &&
588 orig_ntuples == metap->hashm_ntuples)
589 {
590 /*
591 * No one has split or inserted anything since start of scan, so
592 * believe our count as gospel.
593 */
594 metap->hashm_ntuples = num_index_tuples;
595 }
596 else
597 {
598 /*
599 * Otherwise, our count is untrustworthy since we may have
600 * double-scanned tuples in split buckets. Proceed by dead-reckoning.
601 * (Note: we still return estimated_count = false, because using this
602 * count is better than not updating reltuples at all.)
603 */
604 if (metap->hashm_ntuples > tuples_removed)
605 metap->hashm_ntuples -= tuples_removed;
606 else
607 metap->hashm_ntuples = 0;
608 num_index_tuples = metap->hashm_ntuples;
609 }
610
611 MarkBufferDirty(metabuf);
612
613 /* XLOG stuff */
614 if (RelationNeedsWAL(rel))
615 {
616 xl_hash_update_meta_page xlrec;
617 XLogRecPtr recptr;
618
619 xlrec.ntuples = metap->hashm_ntuples;
620
621 XLogBeginInsert();
622 XLogRegisterData(&xlrec, SizeOfHashUpdateMetaPage);
623
624 XLogRegisterBuffer(0, metabuf, REGBUF_STANDARD);
625
626 recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_UPDATE_META_PAGE);
627 PageSetLSN(BufferGetPage(metabuf), recptr);
628 }
629
630 END_CRIT_SECTION();
631
632 _hash_relbuf(rel, metabuf);
633
634 /* return statistics */
635 if (stats == NULL)
636 stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
637 stats->estimated_count = false;
638 stats->num_index_tuples = num_index_tuples;
639 stats->tuples_removed += tuples_removed;
640 /* hashvacuumcleanup will fill in num_pages */
641
642 return stats;
643 }
644
645 /*
646 * Post-VACUUM cleanup.
647 *
648 * Result: a palloc'd struct containing statistical info for VACUUM displays.
649 */
650 IndexBulkDeleteResult *
651 hashvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
652 {
653 Relation rel = info->index;
654 BlockNumber num_pages;
655
656 /* If hashbulkdelete wasn't called, return NULL signifying no change */
657 /* Note: this covers the analyze_only case too */
658 if (stats == NULL)
659 return NULL;
660
661 /* update statistics */
662 num_pages = RelationGetNumberOfBlocks(rel);
663 stats->num_pages = num_pages;
664
665 return stats;
666 }
667
668 /*
669 * Helper function to perform deletion of index entries from a bucket.
670 *
671 * This function expects that the caller has acquired a cleanup lock on the
672 * primary bucket page, and will return with a write lock again held on the
673 * primary bucket page. The lock won't necessarily be held continuously,
674 * though, because we'll release it when visiting overflow pages.
675 *
676 * There can't be any concurrent scans in progress when we first enter this
677 * function because of the cleanup lock we hold on the primary bucket page,
678 * but as soon as we release that lock, there might be. If those scans got
679 * ahead of our cleanup scan, they might see a tuple before we kill it and
680 * wake up only after VACUUM has completed and the TID has been recycled for
681 * an unrelated tuple. To avoid that calamity, we prevent scans from passing
682 * our cleanup scan by locking the next page in the bucket chain before
683 * releasing the lock on the previous page. (This type of lock chaining is not
684 * ideal, so we might want to look for a better solution at some point.)
685 *
686 * We need to retain a pin on the primary bucket to ensure that no concurrent
687 * split can start.
688 */
689 void
690 hashbucketcleanup(Relation rel, Bucket cur_bucket, Buffer bucket_buf,
691 BlockNumber bucket_blkno, BufferAccessStrategy bstrategy,
692 uint32 maxbucket, uint32 highmask, uint32 lowmask,
693 double *tuples_removed, double *num_index_tuples,
694 bool split_cleanup,
695 IndexBulkDeleteCallback callback, void *callback_state)
696 {
697 BlockNumber blkno;
698 Buffer buf;
699 Bucket new_bucket PG_USED_FOR_ASSERTS_ONLY = InvalidBucket;
700 bool bucket_dirty = false;
701
702 blkno = bucket_blkno;
703 buf = bucket_buf;
704
705 if (split_cleanup)
706 new_bucket = _hash_get_newbucket_from_oldbucket(rel, cur_bucket,
707 lowmask, maxbucket);
708
709 /* Scan each page in bucket */
710 for (;;)
711 {
712 HashPageOpaque opaque;
713 OffsetNumber offno;
714 OffsetNumber maxoffno;
715 Buffer next_buf;
716 Page page;
717 OffsetNumber deletable[MaxOffsetNumber];
718 int ndeletable = 0;
719 bool retain_pin = false;
720 bool clear_dead_marking = false;
721
722 vacuum_delay_point(false);
723
724 page = BufferGetPage(buf);
725 opaque = HashPageGetOpaque(page);
726
727 /* Scan each tuple in page */
728 maxoffno = PageGetMaxOffsetNumber(page);
729 for (offno = FirstOffsetNumber;
730 offno <= maxoffno;
731 offno = OffsetNumberNext(offno))
732 {
733 ItemPointer htup;
734 IndexTuple itup;
735 Bucket bucket;
736 bool kill_tuple = false;
737
738 itup = (IndexTuple) PageGetItem(page,
739 PageGetItemId(page, offno));
740 htup = &(itup->t_tid);
741
742 /*
743 * To remove the dead tuples, we strictly want to rely on results
744 * of callback function. refer btvacuumpage for detailed reason.
745 */
746 if (callback && callback(htup, callback_state))
747 {
748 kill_tuple = true;
749 if (tuples_removed)
750 *tuples_removed += 1;
751 }
752 else if (split_cleanup)
753 {
754 /* delete the tuples that are moved by split. */
755 bucket = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
756 maxbucket,
757 highmask,
758 lowmask);
759 /* mark the item for deletion */
760 if (bucket != cur_bucket)
761 {
762 /*
763 * We expect tuples to either belong to current bucket or
764 * new_bucket. This is ensured because we don't allow
765 * further splits from bucket that contains garbage. See
766 * comments in _hash_expandtable.
767 */
768 Assert(bucket == new_bucket);
769 kill_tuple = true;
770 }
771 }
772
773 if (kill_tuple)
774 {
775 /* mark the item for deletion */
776 deletable[ndeletable++] = offno;
777 }
778 else
779 {
780 /* we're keeping it, so count it */
781 if (num_index_tuples)
782 *num_index_tuples += 1;
783 }
784 }
785
786 /* retain the pin on primary bucket page till end of bucket scan */
787 if (blkno == bucket_blkno)
788 retain_pin = true;
789 else
790 retain_pin = false;
791
792 blkno = opaque->hasho_nextblkno;
793
794 /*
795 * Apply deletions, advance to next page and write page if needed.
796 */
797 if (ndeletable > 0)
798 {
799 /* No ereport(ERROR) until changes are logged */
800 START_CRIT_SECTION();
801
802 PageIndexMultiDelete(page, deletable, ndeletable);
803 bucket_dirty = true;
804
805 /*
806 * Let us mark the page as clean if vacuum removes the DEAD tuples
807 * from an index page. We do this by clearing
808 * LH_PAGE_HAS_DEAD_TUPLES flag.
809 */
810 if (tuples_removed && *tuples_removed > 0 &&
811 H_HAS_DEAD_TUPLES(opaque))
812 {
813 opaque->hasho_flag &= ~LH_PAGE_HAS_DEAD_TUPLES;
814 clear_dead_marking = true;
815 }
816
817 MarkBufferDirty(buf);
818
819 /* XLOG stuff */
820 if (RelationNeedsWAL(rel))
821 {
822 xl_hash_delete xlrec;
823 XLogRecPtr recptr;
824
825 xlrec.clear_dead_marking = clear_dead_marking;
826 xlrec.is_primary_bucket_page = (buf == bucket_buf);
827
828 XLogBeginInsert();
829 XLogRegisterData(&xlrec, SizeOfHashDelete);
830
831 /*
832 * bucket buffer was not changed, but still needs to be
833 * registered to ensure that we can acquire a cleanup lock on
834 * it during replay.
835 */
836 if (!xlrec.is_primary_bucket_page)
837 {
838 uint8 flags = REGBUF_STANDARD | REGBUF_NO_IMAGE | REGBUF_NO_CHANGE;
839
840 XLogRegisterBuffer(0, bucket_buf, flags);
841 }
842
843 XLogRegisterBuffer(1, buf, REGBUF_STANDARD);
844 XLogRegisterBufData(1, deletable,
845 ndeletable * sizeof(OffsetNumber));
846
847 recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_DELETE);
848 PageSetLSN(BufferGetPage(buf), recptr);
849 }
850
851 END_CRIT_SECTION();
852 }
853
854 /* bail out if there are no more pages to scan. */
855 if (!BlockNumberIsValid(blkno))
856 break;
857
858 next_buf = _hash_getbuf_with_strategy(rel, blkno, HASH_WRITE,
859 LH_OVERFLOW_PAGE,
860 bstrategy);
861
862 /*
863 * release the lock on previous page after acquiring the lock on next
864 * page
865 */
866 if (retain_pin)
867 LockBuffer(buf, BUFFER_LOCK_UNLOCK);
868 else
869 _hash_relbuf(rel, buf);
870
871 buf = next_buf;
872 }
873
874 /*
875 * lock the bucket page to clear the garbage flag and squeeze the bucket.
876 * if the current buffer is same as bucket buffer, then we already have
877 * lock on bucket page.
878 */
879 if (buf != bucket_buf)
880 {
881 _hash_relbuf(rel, buf);
882 LockBuffer(bucket_buf, BUFFER_LOCK_EXCLUSIVE);
883 }
884
885 /*
886 * Clear the garbage flag from bucket after deleting the tuples that are
887 * moved by split. We purposefully clear the flag before squeeze bucket,
888 * so that after restart, vacuum shouldn't again try to delete the moved
889 * by split tuples.
890 */
891 if (split_cleanup)
892 {
893 HashPageOpaque bucket_opaque;
894 Page page;
895
896 page = BufferGetPage(bucket_buf);
897 bucket_opaque = HashPageGetOpaque(page);
898
899 /* No ereport(ERROR) until changes are logged */
900 START_CRIT_SECTION();
901
902 bucket_opaque->hasho_flag &= ~LH_BUCKET_NEEDS_SPLIT_CLEANUP;
903 MarkBufferDirty(bucket_buf);
904
905 /* XLOG stuff */
906 if (RelationNeedsWAL(rel))
907 {
908 XLogRecPtr recptr;
909
910 XLogBeginInsert();
911 XLogRegisterBuffer(0, bucket_buf, REGBUF_STANDARD);
912
913 recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_SPLIT_CLEANUP);
914 PageSetLSN(page, recptr);
915 }
916
917 END_CRIT_SECTION();
918 }
919
920 /*
921 * If we have deleted anything, try to compact free space. For squeezing
922 * the bucket, we must have a cleanup lock, else it can impact the
923 * ordering of tuples for a scan that has started before it.
924 */
925 if (bucket_dirty && IsBufferCleanupOK(bucket_buf))
926 _hash_squeezebucket(rel, cur_bucket, bucket_blkno, bucket_buf,
927 bstrategy);
928 else
929 LockBuffer(bucket_buf, BUFFER_LOCK_UNLOCK);
930 }
931
932 CompareType
933 hashtranslatestrategy(StrategyNumber strategy, Oid opfamily)
934 {
935 if (strategy == HTEqualStrategyNumber)
936 return COMPARE_EQ;
937 return COMPARE_INVALID;
938 }
939
940 StrategyNumber
941 hashtranslatecmptype(CompareType cmptype, Oid opfamily)
942 {
943 if (cmptype == COMPARE_EQ)
944 return HTEqualStrategyNumber;
945 return InvalidStrategy;
946 }