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 : 2145 : 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 : 2145 : 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 : 330272 : hashbuildCallback(Relation index,
231 : : ItemPointer tid,
232 : : Datum *values,
233 : : bool *isnull,
234 : : bool tupleIsAlive,
235 : : void *state)
236 : : {
237 : 330272 : 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 [ - + ]: 330272 : 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 [ + + ]: 330272 : 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 : 259772 : itup = index_form_tuple(RelationGetDescr(index),
255 : : index_values, index_isnull);
256 : 259772 : itup->t_tid = *tid;
257 : 259772 : _hash_doinsert(index, itup, buildstate->heapRel, false);
258 : 259772 : pfree(itup);
259 : : }
260 : :
261 : 330272 : 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 : 160881 : 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 [ - + ]: 160881 : 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 : 160881 : itup = index_form_tuple(RelationGetDescr(rel), index_values, index_isnull);
289 : 160881 : itup->t_tid = *ht_ctid;
290 : :
291 : 160881 : _hash_doinsert(rel, itup, heapRel, false);
292 : :
293 : 160875 : pfree(itup);
294 : :
295 : 160875 : 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 [ + + ]: 2410 : if (so->killedItems == NULL)
334 : 7 : so->killedItems = palloc_array(int, MaxIndexTuplesPerPage);
335 : :
336 [ + - ]: 2410 : if (so->numKilled < MaxIndexTuplesPerPage)
337 : 2410 : 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 : 7 : 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 : 832 : hash_bulkdelete_read_stream_cb(ReadStream *stream,
474 : : void *callback_private_data,
475 : : void *per_buffer_data)
476 : : {
477 : 832 : HashBulkDeleteStreamPrivate *p = callback_private_data;
478 : : Bucket bucket;
479 : :
480 [ + + ]: 832 : if (p->next_bucket > p->max_bucket)
481 : 35 : return InvalidBlockNumber;
482 : :
483 : 797 : bucket = p->next_bucket++;
484 [ + + ]: 797 : 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 : 35 : hashbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
499 : : IndexBulkDeleteCallback callback, void *callback_state)
500 : : {
501 : 35 : 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 : 35 : Buffer metabuf = InvalidBuffer;
509 : : HashMetaPage metap;
510 : : HashMetaPage cachedmetap;
511 : : HashBulkDeleteStreamPrivate stream_private;
512 : 35 : ReadStream *stream = NULL;
513 : : XLogRecPtr recptr;
514 : :
515 : 35 : tuples_removed = 0;
516 : 35 : 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 : 35 : 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 : 35 : cachedmetap = _hash_getcachedmetap(rel, &metabuf, false);
540 : : Assert(cachedmetap != NULL);
541 : :
542 : 35 : orig_maxbucket = cachedmetap->hashm_maxbucket;
543 : 35 : orig_ntuples = cachedmetap->hashm_ntuples;
544 : :
545 : : /* Scan the buckets that we know exist */
546 : 35 : cur_bucket = 0;
547 : 35 : cur_maxbucket = orig_maxbucket;
548 : :
549 : : /* Set up streaming read for primary bucket pages */
550 : 35 : stream_private.metap = cachedmetap;
551 : 35 : stream_private.next_bucket = cur_bucket;
552 : 35 : stream_private.max_bucket = cur_maxbucket;
553 : :
554 : 35 : bucket_loop:
555 [ + + ]: 832 : 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 : 797 : bool split_cleanup = false;
564 : :
565 : : /* call vacuum_delay_point while not holding any buffer lock */
566 : 797 : vacuum_delay_point(false);
567 : :
568 : : /* Get address of bucket's start page */
569 [ + + ]: 797 : bucket_blkno = BUCKET_TO_BLKNO(cachedmetap, cur_bucket);
570 : :
571 : 797 : blkno = bucket_blkno;
572 : :
573 : : /*
574 : : * We need to acquire a cleanup lock on the primary bucket page to out
575 : : * wait concurrent scans before deleting the dead tuples.
576 : : */
577 : 797 : buf = read_stream_next_buffer(stream, NULL);
578 : : Assert(BufferIsValid(buf));
579 : 797 : LockBufferForCleanup(buf);
580 : 797 : _hash_checkpage(rel, buf, LH_BUCKET_PAGE);
581 : :
582 : 797 : page = BufferGetPage(buf);
583 : 797 : bucket_opaque = HashPageGetOpaque(page);
584 : :
585 : : /*
586 : : * If the bucket contains tuples that are moved by split, then we need
587 : : * to delete such tuples. We can't delete such tuples if the split
588 : : * operation on bucket is not finished as those are needed by scans.
589 : : */
590 [ + - ]: 797 : if (!H_BUCKET_BEING_SPLIT(bucket_opaque) &&
591 [ - + ]: 797 : H_NEEDS_SPLIT_CLEANUP(bucket_opaque))
592 : : {
593 : 0 : split_cleanup = true;
594 : :
595 : : /*
596 : : * This bucket might have been split since we last held a lock on
597 : : * the metapage. If so, hashm_maxbucket, hashm_highmask and
598 : : * hashm_lowmask might be old enough to cause us to fail to remove
599 : : * tuples left behind by the most recent split. To prevent that,
600 : : * now that the primary page of the target bucket has been locked
601 : : * (and thus can't be further split), check whether we need to
602 : : * update our cached metapage data.
603 : : */
604 : : Assert(bucket_opaque->hasho_prevblkno != InvalidBlockNumber);
605 [ # # ]: 0 : if (bucket_opaque->hasho_prevblkno > cachedmetap->hashm_maxbucket)
606 : : {
607 : 0 : cachedmetap = _hash_getcachedmetap(rel, &metabuf, true);
608 : : Assert(cachedmetap != NULL);
609 : :
610 : : /*
611 : : * Reset stream with updated metadata for remaining buckets.
612 : : * The BUCKET_TO_BLKNO mapping depends on hashm_spares[],
613 : : * which may have changed.
614 : : */
615 : 0 : stream_private.metap = cachedmetap;
616 : 0 : stream_private.next_bucket = cur_bucket + 1;
617 : 0 : stream_private.max_bucket = cur_maxbucket;
618 : 0 : read_stream_reset(stream);
619 : : }
620 : : }
621 : :
622 : 797 : bucket_buf = buf;
623 : :
624 : 797 : hashbucketcleanup(rel, cur_bucket, bucket_buf, blkno, info->strategy,
625 : : cachedmetap->hashm_maxbucket,
626 : : cachedmetap->hashm_highmask,
627 : : cachedmetap->hashm_lowmask, &tuples_removed,
628 : : &num_index_tuples, split_cleanup,
629 : : callback, callback_state);
630 : :
631 : 797 : _hash_dropbuf(rel, bucket_buf);
632 : :
633 : : /* Advance to next bucket */
634 : 797 : cur_bucket++;
635 : : }
636 : :
637 [ + + ]: 35 : if (BufferIsInvalid(metabuf))
638 : 19 : metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_NOLOCK, LH_META_PAGE);
639 : :
640 : : /* Write-lock metapage and check for split since we started */
641 : 35 : LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
642 : 35 : metap = HashPageGetMeta(BufferGetPage(metabuf));
643 : :
644 [ - + ]: 35 : if (cur_maxbucket != metap->hashm_maxbucket)
645 : : {
646 : : /* There's been a split, so process the additional bucket(s) */
647 : 0 : LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
648 : 0 : cachedmetap = _hash_getcachedmetap(rel, &metabuf, true);
649 : : Assert(cachedmetap != NULL);
650 : 0 : cur_maxbucket = cachedmetap->hashm_maxbucket;
651 : :
652 : : /* Reset stream to process additional buckets from split */
653 : 0 : stream_private.metap = cachedmetap;
654 : 0 : stream_private.next_bucket = cur_bucket;
655 : 0 : stream_private.max_bucket = cur_maxbucket;
656 : 0 : read_stream_reset(stream);
657 : 0 : goto bucket_loop;
658 : : }
659 : :
660 : : /* Stream should be exhausted since we processed all buckets */
661 : : Assert(read_stream_next_buffer(stream, NULL) == InvalidBuffer);
662 : 35 : read_stream_end(stream);
663 : :
664 : : /* Okay, we're really done. Update tuple count in metapage. */
665 : 35 : START_CRIT_SECTION();
666 : :
667 [ + - ]: 35 : if (orig_maxbucket == metap->hashm_maxbucket &&
668 [ + + ]: 35 : orig_ntuples == metap->hashm_ntuples)
669 : : {
670 : : /*
671 : : * No one has split or inserted anything since start of scan, so
672 : : * believe our count as gospel.
673 : : */
674 : 16 : metap->hashm_ntuples = num_index_tuples;
675 : : }
676 : : else
677 : : {
678 : : /*
679 : : * Otherwise, our count is untrustworthy since we may have
680 : : * double-scanned tuples in split buckets. Proceed by dead-reckoning.
681 : : * (Note: we still return estimated_count = false, because using this
682 : : * count is better than not updating reltuples at all.)
683 : : */
684 [ + + ]: 19 : if (metap->hashm_ntuples > tuples_removed)
685 : 17 : metap->hashm_ntuples -= tuples_removed;
686 : : else
687 : 2 : metap->hashm_ntuples = 0;
688 : 19 : num_index_tuples = metap->hashm_ntuples;
689 : : }
690 : :
691 : 35 : MarkBufferDirty(metabuf);
692 : :
693 : : /* XLOG stuff */
694 [ + - - + : 35 : if (RelationNeedsWAL(rel))
- - - - ]
695 : 35 : {
696 : : xl_hash_update_meta_page xlrec;
697 : :
698 : 35 : xlrec.ntuples = metap->hashm_ntuples;
699 : :
700 : 35 : XLogBeginInsert();
701 : 35 : XLogRegisterData(&xlrec, SizeOfHashUpdateMetaPage);
702 : :
703 : 35 : XLogRegisterBuffer(0, metabuf, REGBUF_STANDARD);
704 : :
705 : 35 : recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_UPDATE_META_PAGE);
706 : : }
707 : : else
708 : 0 : recptr = XLogGetFakeLSN(rel);
709 : :
710 : 35 : PageSetLSN(BufferGetPage(metabuf), recptr);
711 : :
712 : 35 : END_CRIT_SECTION();
713 : :
714 : 35 : _hash_relbuf(rel, metabuf);
715 : :
716 : : /* return statistics */
717 [ + - ]: 35 : if (stats == NULL)
718 : 35 : stats = palloc0_object(IndexBulkDeleteResult);
719 : 35 : stats->estimated_count = false;
720 : 35 : stats->num_index_tuples = num_index_tuples;
721 : 35 : stats->tuples_removed += tuples_removed;
722 : : /* hashvacuumcleanup will fill in num_pages */
723 : :
724 : 35 : return stats;
725 : : }
726 : :
727 : : /*
728 : : * Post-VACUUM cleanup.
729 : : *
730 : : * Result: a palloc'd struct containing statistical info for VACUUM displays.
731 : : */
732 : : IndexBulkDeleteResult *
733 : 51 : hashvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
734 : : {
735 : 51 : Relation rel = info->index;
736 : : BlockNumber num_pages;
737 : :
738 : : /* If hashbulkdelete wasn't called, return NULL signifying no change */
739 : : /* Note: this covers the analyze_only case too */
740 [ + + ]: 51 : if (stats == NULL)
741 : 16 : return NULL;
742 : :
743 : : /* update statistics */
744 : 35 : num_pages = RelationGetNumberOfBlocks(rel);
745 : 35 : stats->num_pages = num_pages;
746 : :
747 : 35 : return stats;
748 : : }
749 : :
750 : : /*
751 : : * Helper function to perform deletion of index entries from a bucket.
752 : : *
753 : : * This function expects that the caller has acquired a cleanup lock on the
754 : : * primary bucket page, and will return with a write lock again held on the
755 : : * primary bucket page. The lock won't necessarily be held continuously,
756 : : * though, because we'll release it when visiting overflow pages.
757 : : *
758 : : * There can't be any concurrent scans in progress when we first enter this
759 : : * function because of the cleanup lock we hold on the primary bucket page,
760 : : * but as soon as we release that lock, there might be. If those scans got
761 : : * ahead of our cleanup scan, they might see a tuple before we kill it and
762 : : * wake up only after VACUUM has completed and the TID has been recycled for
763 : : * an unrelated tuple. To avoid that calamity, we prevent scans from passing
764 : : * our cleanup scan by locking the next page in the bucket chain before
765 : : * releasing the lock on the previous page. (This type of lock chaining is not
766 : : * ideal, so we might want to look for a better solution at some point.)
767 : : *
768 : : * We need to retain a pin on the primary bucket to ensure that no concurrent
769 : : * split can start.
770 : : */
771 : : void
772 : 1688 : hashbucketcleanup(Relation rel, Bucket cur_bucket, Buffer bucket_buf,
773 : : BlockNumber bucket_blkno, BufferAccessStrategy bstrategy,
774 : : uint32 maxbucket, uint32 highmask, uint32 lowmask,
775 : : double *tuples_removed, double *num_index_tuples,
776 : : bool split_cleanup,
777 : : IndexBulkDeleteCallback callback, void *callback_state)
778 : : {
779 : : BlockNumber blkno;
780 : : Buffer buf;
781 : 1688 : Bucket new_bucket PG_USED_FOR_ASSERTS_ONLY = InvalidBucket;
782 : 1688 : bool bucket_dirty = false;
783 : : XLogRecPtr recptr;
784 : :
785 : 1688 : blkno = bucket_blkno;
786 : 1688 : buf = bucket_buf;
787 : :
788 [ + + ]: 1688 : if (split_cleanup)
789 : 891 : new_bucket = _hash_get_newbucket_from_oldbucket(rel, cur_bucket,
790 : : lowmask, maxbucket);
791 : :
792 : : /* Scan each page in bucket */
793 : : for (;;)
794 : 281 : {
795 : : HashPageOpaque opaque;
796 : : OffsetNumber offno;
797 : : OffsetNumber maxoffno;
798 : : Buffer next_buf;
799 : : Page page;
800 : : OffsetNumber deletable[MaxOffsetNumber];
801 : 1969 : int ndeletable = 0;
802 : 1969 : bool retain_pin = false;
803 : 1969 : bool clear_dead_marking = false;
804 : :
805 : 1969 : page = BufferGetPage(buf);
806 : 1969 : opaque = HashPageGetOpaque(page);
807 : :
808 : : /* Scan each tuple in page */
809 : 1969 : maxoffno = PageGetMaxOffsetNumber(page);
810 : 1969 : for (offno = FirstOffsetNumber;
811 [ + + ]: 360639 : offno <= maxoffno;
812 : 358670 : offno = OffsetNumberNext(offno))
813 : : {
814 : : ItemPointer htup;
815 : : IndexTuple itup;
816 : : Bucket bucket;
817 : 358670 : bool kill_tuple = false;
818 : :
819 : 358670 : itup = (IndexTuple) PageGetItem(page,
820 : 358670 : PageGetItemId(page, offno));
821 : 358670 : htup = &(itup->t_tid);
822 : :
823 : : /*
824 : : * To remove the dead tuples, we strictly want to rely on results
825 : : * of callback function. refer btvacuumpage for detailed reason.
826 : : */
827 [ + + + + ]: 358670 : if (callback && callback(htup, callback_state))
828 : : {
829 : 21926 : kill_tuple = true;
830 [ + - ]: 21926 : if (tuples_removed)
831 : 21926 : *tuples_removed += 1;
832 : : }
833 [ + + ]: 336744 : else if (split_cleanup)
834 : : {
835 : : /* delete the tuples that are moved by split. */
836 : 204368 : bucket = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
837 : : maxbucket,
838 : : highmask,
839 : : lowmask);
840 : : /* mark the item for deletion */
841 [ + + ]: 204368 : if (bucket != cur_bucket)
842 : : {
843 : : /*
844 : : * We expect tuples to either belong to current bucket or
845 : : * new_bucket. This is ensured because we don't allow
846 : : * further splits from bucket that contains garbage. See
847 : : * comments in _hash_expandtable.
848 : : */
849 : : Assert(bucket == new_bucket);
850 : 83714 : kill_tuple = true;
851 : : }
852 : : }
853 : :
854 [ + + ]: 358670 : if (kill_tuple)
855 : : {
856 : : /* mark the item for deletion */
857 : 105640 : deletable[ndeletable++] = offno;
858 : : }
859 : : else
860 : : {
861 : : /* we're keeping it, so count it */
862 [ + + ]: 253030 : if (num_index_tuples)
863 : 132376 : *num_index_tuples += 1;
864 : : }
865 : : }
866 : :
867 : : /* retain the pin on primary bucket page till end of bucket scan */
868 [ + + ]: 1969 : if (blkno == bucket_blkno)
869 : 1688 : retain_pin = true;
870 : : else
871 : 281 : retain_pin = false;
872 : :
873 : 1969 : blkno = opaque->hasho_nextblkno;
874 : :
875 : : /*
876 : : * Apply deletions, advance to next page and write page if needed.
877 : : */
878 [ + + ]: 1969 : if (ndeletable > 0)
879 : : {
880 : : /* No ereport(ERROR) until changes are logged */
881 : 1040 : START_CRIT_SECTION();
882 : :
883 : 1040 : PageIndexMultiDelete(page, deletable, ndeletable);
884 : 1040 : bucket_dirty = true;
885 : :
886 : : /*
887 : : * Let us mark the page as clean if vacuum removes the DEAD tuples
888 : : * from an index page. We do this by clearing
889 : : * LH_PAGE_HAS_DEAD_TUPLES flag.
890 : : */
891 [ + + + - ]: 1040 : if (tuples_removed && *tuples_removed > 0 &&
892 [ + + ]: 111 : H_HAS_DEAD_TUPLES(opaque))
893 : : {
894 : 1 : opaque->hasho_flag &= ~LH_PAGE_HAS_DEAD_TUPLES;
895 : 1 : clear_dead_marking = true;
896 : : }
897 : :
898 : 1040 : MarkBufferDirty(buf);
899 : :
900 : : /* XLOG stuff */
901 [ + - - + : 1040 : if (RelationNeedsWAL(rel))
- - - - ]
902 : 1040 : {
903 : : xl_hash_delete xlrec;
904 : :
905 : 1040 : xlrec.clear_dead_marking = clear_dead_marking;
906 : 1040 : xlrec.is_primary_bucket_page = (buf == bucket_buf);
907 : :
908 : 1040 : XLogBeginInsert();
909 : 1040 : XLogRegisterData(&xlrec, SizeOfHashDelete);
910 : :
911 : : /*
912 : : * bucket buffer was not changed, but still needs to be
913 : : * registered to ensure that we can acquire a cleanup lock on
914 : : * it during replay.
915 : : */
916 [ + + ]: 1040 : if (!xlrec.is_primary_bucket_page)
917 : : {
918 : 130 : uint8 flags = REGBUF_STANDARD | REGBUF_NO_IMAGE | REGBUF_NO_CHANGE;
919 : :
920 : 130 : XLogRegisterBuffer(0, bucket_buf, flags);
921 : : }
922 : :
923 : 1040 : XLogRegisterBuffer(1, buf, REGBUF_STANDARD);
924 : 1040 : XLogRegisterBufData(1, deletable,
925 : : ndeletable * sizeof(OffsetNumber));
926 : :
927 : 1040 : recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_DELETE);
928 : : }
929 : : else
930 : 0 : recptr = XLogGetFakeLSN(rel);
931 : :
932 : 1040 : PageSetLSN(BufferGetPage(buf), recptr);
933 : :
934 : 1040 : END_CRIT_SECTION();
935 : : }
936 : :
937 : : /* bail out if there are no more pages to scan. */
938 [ + + ]: 1969 : if (!BlockNumberIsValid(blkno))
939 : 1688 : break;
940 : :
941 : 281 : next_buf = _hash_getbuf_with_strategy(rel, blkno, HASH_WRITE,
942 : : LH_OVERFLOW_PAGE,
943 : : bstrategy);
944 : :
945 : : /*
946 : : * release the lock on previous page after acquiring the lock on next
947 : : * page
948 : : */
949 [ + + ]: 281 : if (retain_pin)
950 : 53 : LockBuffer(buf, BUFFER_LOCK_UNLOCK);
951 : : else
952 : 228 : _hash_relbuf(rel, buf);
953 : :
954 : 281 : buf = next_buf;
955 : : }
956 : :
957 : : /*
958 : : * lock the bucket page to clear the garbage flag and squeeze the bucket.
959 : : * if the current buffer is same as bucket buffer, then we already have
960 : : * lock on bucket page.
961 : : */
962 [ + + ]: 1688 : if (buf != bucket_buf)
963 : : {
964 : 53 : _hash_relbuf(rel, buf);
965 : 53 : LockBuffer(bucket_buf, BUFFER_LOCK_EXCLUSIVE);
966 : : }
967 : :
968 : : /*
969 : : * Clear the garbage flag from bucket after deleting the tuples that are
970 : : * moved by split. We purposefully clear the flag before squeeze bucket,
971 : : * so that after restart, vacuum shouldn't again try to delete the moved
972 : : * by split tuples.
973 : : */
974 [ + + ]: 1688 : if (split_cleanup)
975 : : {
976 : : HashPageOpaque bucket_opaque;
977 : : Page page;
978 : :
979 : 891 : page = BufferGetPage(bucket_buf);
980 : 891 : bucket_opaque = HashPageGetOpaque(page);
981 : :
982 : : /* No ereport(ERROR) until changes are logged */
983 : 891 : START_CRIT_SECTION();
984 : :
985 : 891 : bucket_opaque->hasho_flag &= ~LH_BUCKET_NEEDS_SPLIT_CLEANUP;
986 : 891 : MarkBufferDirty(bucket_buf);
987 : :
988 : : /* XLOG stuff */
989 [ + - - + : 891 : if (RelationNeedsWAL(rel))
- - - - ]
990 : : {
991 : 891 : XLogBeginInsert();
992 : 891 : XLogRegisterBuffer(0, bucket_buf, REGBUF_STANDARD);
993 : :
994 : 891 : recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_SPLIT_CLEANUP);
995 : : }
996 : : else
997 : 0 : recptr = XLogGetFakeLSN(rel);
998 : :
999 : 891 : PageSetLSN(page, recptr);
1000 : :
1001 : 891 : END_CRIT_SECTION();
1002 : : }
1003 : :
1004 : : /*
1005 : : * If we have deleted anything, try to compact free space. For squeezing
1006 : : * the bucket, we must have a cleanup lock, else it can impact the
1007 : : * ordering of tuples for a scan that has started before it.
1008 : : */
1009 [ + + + - ]: 1688 : if (bucket_dirty && IsBufferCleanupOK(bucket_buf))
1010 : 926 : _hash_squeezebucket(rel, cur_bucket, bucket_blkno, bucket_buf,
1011 : : bstrategy);
1012 : : else
1013 : 762 : LockBuffer(bucket_buf, BUFFER_LOCK_UNLOCK);
1014 : 1688 : }
1015 : :
1016 : : CompareType
1017 : 0 : hashtranslatestrategy(StrategyNumber strategy, Oid opfamily)
1018 : : {
1019 [ # # ]: 0 : if (strategy == HTEqualStrategyNumber)
1020 : 0 : return COMPARE_EQ;
1021 : 0 : return COMPARE_INVALID;
1022 : : }
1023 : :
1024 : : StrategyNumber
1025 : 6 : hashtranslatecmptype(CompareType cmptype, Oid opfamily)
1026 : : {
1027 [ + - ]: 6 : if (cmptype == COMPARE_EQ)
1028 : 6 : return HTEqualStrategyNumber;
1029 : 0 : return InvalidStrategy;
1030 : : }
|
