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