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 "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 : 273 : hashhandler(PG_FUNCTION_ARGS)
59 : : {
60 : : static const IndexAmRoutine amroutine = {
61 : : .type = T_IndexAmRoutine,
62 : : .amstrategies = HTMaxStrategyNumber,
63 : : .amsupport = HASHNProcs,
64 : : .amoptsprocnum = HASHOPTIONS_PROC,
65 : : .amcanorder = false,
66 : : .amcanorderbyop = false,
67 : : .amcanhash = true,
68 : : .amconsistentequality = true,
69 : : .amconsistentordering = false,
70 : : .amcanbackward = true,
71 : : .amcanunique = false,
72 : : .amcanmulticol = false,
73 : : .amoptionalkey = false,
74 : : .amsearcharray = false,
75 : : .amsearchnulls = false,
76 : : .amstorage = false,
77 : : .amclusterable = false,
78 : : .ampredlocks = true,
79 : : .amcanparallel = false,
80 : : .amcanbuildparallel = false,
81 : : .amcaninclude = false,
82 : : .amusemaintenanceworkmem = false,
83 : : .amsummarizing = false,
84 : : .amparallelvacuumoptions =
85 : : VACUUM_OPTION_PARALLEL_BULKDEL,
86 : : .amkeytype = INT4OID,
87 : :
88 : : .ambuild = hashbuild,
89 : : .ambuildempty = hashbuildempty,
90 : : .aminsert = hashinsert,
91 : : .aminsertcleanup = NULL,
92 : : .ambulkdelete = hashbulkdelete,
93 : : .amvacuumcleanup = hashvacuumcleanup,
94 : : .amcanreturn = NULL,
95 : : .amcostestimate = hashcostestimate,
96 : : .amgettreeheight = NULL,
97 : : .amoptions = hashoptions,
98 : : .amproperty = NULL,
99 : : .ambuildphasename = NULL,
100 : : .amvalidate = hashvalidate,
101 : : .amadjustmembers = hashadjustmembers,
102 : : .ambeginscan = hashbeginscan,
103 : : .amrescan = hashrescan,
104 : : .amgettuple = hashgettuple,
105 : : .amgetbitmap = hashgetbitmap,
106 : : .amendscan = hashendscan,
107 : : .ammarkpos = NULL,
108 : : .amrestrpos = NULL,
109 : : .amestimateparallelscan = NULL,
110 : : .aminitparallelscan = NULL,
111 : : .amparallelrescan = NULL,
112 : : .amtranslatestrategy = hashtranslatestrategy,
113 : : .amtranslatecmptype = hashtranslatecmptype,
114 : : };
115 : :
116 : 273 : PG_RETURN_POINTER(&amroutine);
117 : : }
118 : :
119 : : /*
120 : : * hashbuild() -- build a new hash index.
121 : : */
122 : : IndexBuildResult *
123 : 29 : hashbuild(Relation heap, Relation index, IndexInfo *indexInfo)
124 : : {
125 : 29 : IndexBuildResult *result;
126 : 29 : BlockNumber relpages;
127 : 29 : double reltuples;
128 : 29 : double allvisfrac;
129 : 29 : uint32 num_buckets;
130 : 29 : Size sort_threshold;
131 : 29 : HashBuildState buildstate;
132 : :
133 : : /*
134 : : * We expect to be called exactly once for any index relation. If that's
135 : : * not the case, big trouble's what we have.
136 : : */
137 [ + - ]: 29 : if (RelationGetNumberOfBlocks(index) != 0)
138 [ # # # # ]: 0 : elog(ERROR, "index \"%s\" already contains data",
139 : : RelationGetRelationName(index));
140 : :
141 : : /* Estimate the number of rows currently present in the table */
142 : 29 : estimate_rel_size(heap, NULL, &relpages, &reltuples, &allvisfrac);
143 : :
144 : : /* Initialize the hash index metadata page and initial buckets */
145 : 29 : num_buckets = _hash_init(index, reltuples, MAIN_FORKNUM);
146 : :
147 : : /*
148 : : * If we just insert the tuples into the index in scan order, then
149 : : * (assuming their hash codes are pretty random) there will be no locality
150 : : * of access to the index, and if the index is bigger than available RAM
151 : : * then we'll thrash horribly. To prevent that scenario, we can sort the
152 : : * tuples by (expected) bucket number. However, such a sort is useless
153 : : * overhead when the index does fit in RAM. We choose to sort if the
154 : : * initial index size exceeds maintenance_work_mem, or the number of
155 : : * buffers usable for the index, whichever is less. (Limiting by the
156 : : * number of buffers should reduce thrashing between PG buffers and kernel
157 : : * buffers, which seems useful even if no physical I/O results. Limiting
158 : : * by maintenance_work_mem is useful to allow easy testing of the sort
159 : : * code path, and may be useful to DBAs as an additional control knob.)
160 : : *
161 : : * NOTE: this test will need adjustment if a bucket is ever different from
162 : : * one page. Also, "initial index size" accounting does not include the
163 : : * metapage, nor the first bitmap page.
164 : : */
165 : 29 : sort_threshold = (maintenance_work_mem * (Size) 1024) / BLCKSZ;
166 [ + + ]: 29 : if (index->rd_rel->relpersistence != RELPERSISTENCE_TEMP)
167 [ + - ]: 28 : sort_threshold = Min(sort_threshold, NBuffers);
168 : : else
169 [ - + ]: 1 : sort_threshold = Min(sort_threshold, NLocBuffer);
170 : :
171 [ + + ]: 29 : if (num_buckets >= sort_threshold)
172 : 1 : buildstate.spool = _h_spoolinit(heap, index, num_buckets);
173 : : else
174 : 28 : buildstate.spool = NULL;
175 : :
176 : : /* prepare to build the index */
177 : 29 : buildstate.indtuples = 0;
178 : 29 : buildstate.heapRel = heap;
179 : :
180 : : /* do the heap scan */
181 : 29 : reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
182 : : hashbuildCallback,
183 : : &buildstate, NULL);
184 : 29 : pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_TOTAL,
185 : 29 : buildstate.indtuples);
186 : :
187 [ + + ]: 29 : if (buildstate.spool)
188 : : {
189 : : /* sort the tuples and insert them into the index */
190 : 1 : _h_indexbuild(buildstate.spool, buildstate.heapRel);
191 : 1 : _h_spooldestroy(buildstate.spool);
192 : 1 : }
193 : :
194 : : /*
195 : : * Return statistics
196 : : */
197 : 29 : result = palloc_object(IndexBuildResult);
198 : :
199 : 29 : result->heap_tuples = reltuples;
200 : 29 : result->index_tuples = buildstate.indtuples;
201 : :
202 : 58 : return result;
203 : 29 : }
204 : :
205 : : /*
206 : : * hashbuildempty() -- build an empty hash index in the initialization fork
207 : : */
208 : : void
209 : 1 : hashbuildempty(Relation index)
210 : : {
211 : 1 : _hash_init(index, 0, INIT_FORKNUM);
212 : 1 : }
213 : :
214 : : /*
215 : : * Per-tuple callback for table_index_build_scan
216 : : */
217 : : static void
218 : 82059 : hashbuildCallback(Relation index,
219 : : ItemPointer tid,
220 : : Datum *values,
221 : : bool *isnull,
222 : : bool tupleIsAlive,
223 : : void *state)
224 : : {
225 : 82059 : HashBuildState *buildstate = (HashBuildState *) state;
226 : 82059 : Datum index_values[1];
227 : 82059 : bool index_isnull[1];
228 : 82059 : IndexTuple itup;
229 : :
230 : : /* convert data to a hash key; on failure, do not insert anything */
231 [ + - + - ]: 164118 : if (!_hash_convert_tuple(index,
232 : 82059 : values, isnull,
233 : 82059 : index_values, index_isnull))
234 : 0 : return;
235 : :
236 : : /* Either spool the tuple for sorting, or just put it into the index */
237 [ + + ]: 82059 : if (buildstate->spool)
238 : 10000 : _h_spool(buildstate->spool, tid, index_values, index_isnull);
239 : : else
240 : : {
241 : : /* form an index tuple and point it at the heap tuple */
242 : 144118 : itup = index_form_tuple(RelationGetDescr(index),
243 : 72059 : index_values, index_isnull);
244 : 72059 : itup->t_tid = *tid;
245 : 72059 : _hash_doinsert(index, itup, buildstate->heapRel, false);
246 : 72059 : pfree(itup);
247 : : }
248 : :
249 : 82059 : buildstate->indtuples += 1;
250 [ - + ]: 82059 : }
251 : :
252 : : /*
253 : : * hashinsert() -- insert an index tuple into a hash table.
254 : : *
255 : : * Hash on the heap tuple's key, form an index tuple with hash code.
256 : : * Find the appropriate location for the new tuple, and put it there.
257 : : */
258 : : bool
259 : 37557 : hashinsert(Relation rel, Datum *values, bool *isnull,
260 : : ItemPointer ht_ctid, Relation heapRel,
261 : : IndexUniqueCheck checkUnique,
262 : : bool indexUnchanged,
263 : : IndexInfo *indexInfo)
264 : : {
265 : 37557 : Datum index_values[1];
266 : 37557 : bool index_isnull[1];
267 : 37557 : IndexTuple itup;
268 : :
269 : : /* convert data to a hash key; on failure, do not insert anything */
270 [ - + - + ]: 75114 : if (!_hash_convert_tuple(rel,
271 : 37557 : values, isnull,
272 : 37557 : index_values, index_isnull))
273 : 0 : return false;
274 : :
275 : : /* form an index tuple and point it at the heap tuple */
276 : 37557 : itup = index_form_tuple(RelationGetDescr(rel), index_values, index_isnull);
277 : 37557 : itup->t_tid = *ht_ctid;
278 : :
279 : 37557 : _hash_doinsert(rel, itup, heapRel, false);
280 : :
281 : 37557 : pfree(itup);
282 : :
283 : 37557 : return false;
284 : 37557 : }
285 : :
286 : :
287 : : /*
288 : : * hashgettuple() -- Get the next tuple in the scan.
289 : : */
290 : : bool
291 : 16588 : hashgettuple(IndexScanDesc scan, ScanDirection dir)
292 : : {
293 : 16588 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
294 : 16588 : bool res;
295 : :
296 : : /* Hash indexes are always lossy since we store only the hash code */
297 : 16588 : scan->xs_recheck = true;
298 : :
299 : : /*
300 : : * If we've already initialized this scan, we can just advance it in the
301 : : * appropriate direction. If we haven't done so yet, we call a routine to
302 : : * get the first item in the scan.
303 : : */
304 [ + + + - : 16588 : if (!HashScanPosIsValid(so->currPos))
+ + ]
305 : 50 : res = _hash_first(scan, dir);
306 : : else
307 : : {
308 : : /*
309 : : * Check to see if we should kill the previously-fetched tuple.
310 : : */
311 [ + - ]: 16538 : if (scan->kill_prior_tuple)
312 : : {
313 : : /*
314 : : * Yes, so remember it for later. (We'll deal with all such tuples
315 : : * at once right after leaving the index page or at end of scan.)
316 : : * In case if caller reverses the indexscan direction it is quite
317 : : * possible that the same item might get entered multiple times.
318 : : * But, we don't detect that; instead, we just forget any excess
319 : : * entries.
320 : : */
321 [ # # ]: 0 : if (so->killedItems == NULL)
322 : 0 : so->killedItems = palloc_array(int, MaxIndexTuplesPerPage);
323 : :
324 [ # # ]: 0 : if (so->numKilled < MaxIndexTuplesPerPage)
325 : 0 : so->killedItems[so->numKilled++] = so->currPos.itemIndex;
326 : 0 : }
327 : :
328 : : /*
329 : : * Now continue the scan.
330 : : */
331 : 16538 : res = _hash_next(scan, dir);
332 : : }
333 : :
334 : 33176 : return res;
335 : 16588 : }
336 : :
337 : :
338 : : /*
339 : : * hashgetbitmap() -- get all tuples at once
340 : : */
341 : : int64
342 : 10 : hashgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
343 : : {
344 : 10 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
345 : 10 : bool res;
346 : 10 : int64 ntids = 0;
347 : 10 : HashScanPosItem *currItem;
348 : :
349 : 10 : res = _hash_first(scan, ForwardScanDirection);
350 : :
351 [ + + ]: 31 : while (res)
352 : : {
353 : 21 : 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 : 21 : tbm_add_tuples(tbm, &(currItem->heapTid), 1, true);
361 : 21 : ntids++;
362 : :
363 : 21 : res = _hash_next(scan, ForwardScanDirection);
364 : : }
365 : :
366 : 20 : return ntids;
367 : 10 : }
368 : :
369 : :
370 : : /*
371 : : * hashbeginscan() -- start a scan on a hash index
372 : : */
373 : : IndexScanDesc
374 : 34 : hashbeginscan(Relation rel, int nkeys, int norderbys)
375 : : {
376 : 34 : IndexScanDesc scan;
377 : 34 : HashScanOpaque so;
378 : :
379 : : /* no order by operators allowed */
380 [ + - ]: 34 : Assert(norderbys == 0);
381 : :
382 : 34 : scan = RelationGetIndexScan(rel, nkeys, norderbys);
383 : :
384 : 34 : so = (HashScanOpaque) palloc_object(HashScanOpaqueData);
385 : 34 : HashScanPosInvalidate(so->currPos);
386 : 34 : so->hashso_bucket_buf = InvalidBuffer;
387 : 34 : so->hashso_split_bucket_buf = InvalidBuffer;
388 : :
389 : 34 : so->hashso_buc_populated = false;
390 : 34 : so->hashso_buc_split = false;
391 : :
392 : 34 : so->killedItems = NULL;
393 : 34 : so->numKilled = 0;
394 : :
395 : 34 : scan->opaque = so;
396 : :
397 : 68 : return scan;
398 : 34 : }
399 : :
400 : : /*
401 : : * hashrescan() -- rescan an index relation
402 : : */
403 : : void
404 : 59 : hashrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
405 : : ScanKey orderbys, int norderbys)
406 : : {
407 : 59 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
408 : 59 : Relation rel = scan->indexRelation;
409 : :
410 [ + + + - : 59 : if (HashScanPosIsValid(so->currPos))
+ + ]
411 : : {
412 : : /* Before leaving current page, deal with any killed items */
413 [ + - ]: 10 : if (so->numKilled > 0)
414 : 0 : _hash_kill_items(scan);
415 : 10 : }
416 : :
417 : 59 : _hash_dropscanbuf(rel, so);
418 : :
419 : : /* set position invalid (this will cause _hash_first call) */
420 : 59 : HashScanPosInvalidate(so->currPos);
421 : :
422 : : /* Update scan key, if a new one is given */
423 [ + - - + ]: 59 : if (scankey && scan->numberOfKeys > 0)
424 : 59 : memcpy(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData));
425 : :
426 : 59 : so->hashso_buc_populated = false;
427 : 59 : so->hashso_buc_split = false;
428 : 59 : }
429 : :
430 : : /*
431 : : * hashendscan() -- close down a scan
432 : : */
433 : : void
434 : 34 : hashendscan(IndexScanDesc scan)
435 : : {
436 : 34 : HashScanOpaque so = (HashScanOpaque) scan->opaque;
437 : 34 : Relation rel = scan->indexRelation;
438 : :
439 [ + + + - : 34 : if (HashScanPosIsValid(so->currPos))
+ + ]
440 : : {
441 : : /* Before leaving current page, deal with any killed items */
442 [ + - ]: 9 : if (so->numKilled > 0)
443 : 0 : _hash_kill_items(scan);
444 : 9 : }
445 : :
446 : 34 : _hash_dropscanbuf(rel, so);
447 : :
448 [ + - ]: 34 : if (so->killedItems != NULL)
449 : 0 : pfree(so->killedItems);
450 : 34 : pfree(so);
451 : 34 : scan->opaque = NULL;
452 : 34 : }
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 : 4 : hashbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
466 : : IndexBulkDeleteCallback callback, void *callback_state)
467 : : {
468 : 4 : Relation rel = info->index;
469 : 4 : double tuples_removed;
470 : 4 : double num_index_tuples;
471 : 4 : double orig_ntuples;
472 : 4 : Bucket orig_maxbucket;
473 : 4 : Bucket cur_maxbucket;
474 : 4 : Bucket cur_bucket;
475 : 4 : Buffer metabuf = InvalidBuffer;
476 : 4 : HashMetaPage metap;
477 : 4 : HashMetaPage cachedmetap;
478 : :
479 : 4 : tuples_removed = 0;
480 : 4 : 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 : 4 : cachedmetap = _hash_getcachedmetap(rel, &metabuf, false);
489 [ + - ]: 4 : Assert(cachedmetap != NULL);
490 : :
491 : 4 : orig_maxbucket = cachedmetap->hashm_maxbucket;
492 : 4 : orig_ntuples = cachedmetap->hashm_ntuples;
493 : :
494 : : /* Scan the buckets that we know exist */
495 : 4 : cur_bucket = 0;
496 : 4 : cur_maxbucket = orig_maxbucket;
497 : :
498 : : loop_top:
499 [ + + ]: 35 : while (cur_bucket <= cur_maxbucket)
500 : : {
501 : 31 : BlockNumber bucket_blkno;
502 : 31 : BlockNumber blkno;
503 : 31 : Buffer bucket_buf;
504 : 31 : Buffer buf;
505 : 31 : HashPageOpaque bucket_opaque;
506 : 31 : Page page;
507 : 31 : bool split_cleanup = false;
508 : :
509 : : /* Get address of bucket's start page */
510 [ + + ]: 31 : bucket_blkno = BUCKET_TO_BLKNO(cachedmetap, cur_bucket);
511 : :
512 : 31 : 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 : 31 : buf = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL, info->strategy);
519 : 31 : LockBufferForCleanup(buf);
520 : 31 : _hash_checkpage(rel, buf, LH_BUCKET_PAGE);
521 : :
522 : 31 : page = BufferGetPage(buf);
523 : 31 : 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 [ + - + - ]: 31 : if (!H_BUCKET_BEING_SPLIT(bucket_opaque) &&
531 : 31 : H_NEEDS_SPLIT_CLEANUP(bucket_opaque))
532 : : {
533 : 0 : 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 [ # # ]: 0 : Assert(bucket_opaque->hasho_prevblkno != InvalidBlockNumber);
545 [ # # ]: 0 : if (bucket_opaque->hasho_prevblkno > cachedmetap->hashm_maxbucket)
546 : : {
547 : 0 : cachedmetap = _hash_getcachedmetap(rel, &metabuf, true);
548 [ # # ]: 0 : Assert(cachedmetap != NULL);
549 : 0 : }
550 : 0 : }
551 : :
552 : 31 : bucket_buf = buf;
553 : :
554 : 62 : hashbucketcleanup(rel, cur_bucket, bucket_buf, blkno, info->strategy,
555 : 31 : cachedmetap->hashm_maxbucket,
556 : 31 : cachedmetap->hashm_highmask,
557 : 31 : cachedmetap->hashm_lowmask, &tuples_removed,
558 : 31 : &num_index_tuples, split_cleanup,
559 : 31 : callback, callback_state);
560 : :
561 : 31 : _hash_dropbuf(rel, bucket_buf);
562 : :
563 : : /* Advance to next bucket */
564 : 31 : cur_bucket++;
565 : 31 : }
566 : :
567 [ - + ]: 4 : if (BufferIsInvalid(metabuf))
568 : 4 : metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_NOLOCK, LH_META_PAGE);
569 : :
570 : : /* Write-lock metapage and check for split since we started */
571 : 4 : LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
572 : 4 : metap = HashPageGetMeta(BufferGetPage(metabuf));
573 : :
574 [ - + ]: 4 : if (cur_maxbucket != metap->hashm_maxbucket)
575 : : {
576 : : /* There's been a split, so process the additional bucket(s) */
577 : 0 : LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
578 : 0 : cachedmetap = _hash_getcachedmetap(rel, &metabuf, true);
579 [ # # ]: 0 : Assert(cachedmetap != NULL);
580 : 0 : cur_maxbucket = cachedmetap->hashm_maxbucket;
581 : 0 : goto loop_top;
582 : : }
583 : :
584 : : /* Okay, we're really done. Update tuple count in metapage. */
585 : 4 : START_CRIT_SECTION();
586 : :
587 [ + - - + ]: 4 : if (orig_maxbucket == metap->hashm_maxbucket &&
588 : 4 : 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 : 0 : metap->hashm_ntuples = num_index_tuples;
595 : 0 : }
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 [ + - ]: 4 : if (metap->hashm_ntuples > tuples_removed)
605 : 4 : metap->hashm_ntuples -= tuples_removed;
606 : : else
607 : 0 : metap->hashm_ntuples = 0;
608 : 4 : num_index_tuples = metap->hashm_ntuples;
609 : : }
610 : :
611 : 4 : MarkBufferDirty(metabuf);
612 : :
613 : : /* XLOG stuff */
614 [ + - + - : 4 : if (RelationNeedsWAL(rel))
+ - - + ]
615 : : {
616 : 4 : xl_hash_update_meta_page xlrec;
617 : 4 : XLogRecPtr recptr;
618 : :
619 : 4 : xlrec.ntuples = metap->hashm_ntuples;
620 : :
621 : 4 : XLogBeginInsert();
622 : 4 : XLogRegisterData(&xlrec, SizeOfHashUpdateMetaPage);
623 : :
624 : 4 : XLogRegisterBuffer(0, metabuf, REGBUF_STANDARD);
625 : :
626 : 4 : recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_UPDATE_META_PAGE);
627 : 4 : PageSetLSN(BufferGetPage(metabuf), recptr);
628 : 4 : }
629 : :
630 [ + - ]: 4 : END_CRIT_SECTION();
631 : :
632 : 4 : _hash_relbuf(rel, metabuf);
633 : :
634 : : /* return statistics */
635 [ - + ]: 4 : if (stats == NULL)
636 : 4 : stats = palloc0_object(IndexBulkDeleteResult);
637 : 4 : stats->estimated_count = false;
638 : 4 : stats->num_index_tuples = num_index_tuples;
639 : 4 : stats->tuples_removed += tuples_removed;
640 : : /* hashvacuumcleanup will fill in num_pages */
641 : :
642 : 8 : return stats;
643 : 4 : }
644 : :
645 : : /*
646 : : * Post-VACUUM cleanup.
647 : : *
648 : : * Result: a palloc'd struct containing statistical info for VACUUM displays.
649 : : */
650 : : IndexBulkDeleteResult *
651 : 7 : hashvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
652 : : {
653 : 7 : Relation rel = info->index;
654 : 7 : 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 [ + + ]: 7 : if (stats == NULL)
659 : 3 : return NULL;
660 : :
661 : : /* update statistics */
662 : 4 : num_pages = RelationGetNumberOfBlocks(rel);
663 : 4 : stats->num_pages = num_pages;
664 : :
665 : 4 : return stats;
666 : 7 : }
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 : 252 : 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 : 252 : BlockNumber blkno;
698 : 252 : Buffer buf;
699 : 252 : Bucket new_bucket PG_USED_FOR_ASSERTS_ONLY = InvalidBucket;
700 : 252 : bool bucket_dirty = false;
701 : :
702 : 252 : blkno = bucket_blkno;
703 : 252 : buf = bucket_buf;
704 : :
705 [ + + ]: 252 : if (split_cleanup)
706 : 442 : new_bucket = _hash_get_newbucket_from_oldbucket(rel, cur_bucket,
707 : 221 : lowmask, maxbucket);
708 : :
709 : : /* Scan each page in bucket */
710 : 322 : for (;;)
711 : : {
712 : 322 : HashPageOpaque opaque;
713 : 322 : OffsetNumber offno;
714 : 322 : OffsetNumber maxoffno;
715 : 322 : Buffer next_buf;
716 : 322 : Page page;
717 : 322 : OffsetNumber deletable[MaxOffsetNumber];
718 : 322 : int ndeletable = 0;
719 : 322 : bool retain_pin = false;
720 : 322 : bool clear_dead_marking = false;
721 : :
722 : 322 : vacuum_delay_point(false);
723 : :
724 : 322 : page = BufferGetPage(buf);
725 : 322 : opaque = HashPageGetOpaque(page);
726 : :
727 : : /* Scan each tuple in page */
728 : 322 : maxoffno = PageGetMaxOffsetNumber(page);
729 [ + + ]: 58184 : for (offno = FirstOffsetNumber;
730 : 58184 : offno <= maxoffno;
731 : 57862 : offno = OffsetNumberNext(offno))
732 : : {
733 : 57862 : ItemPointer htup;
734 : 57862 : IndexTuple itup;
735 : 57862 : Bucket bucket;
736 : 57862 : bool kill_tuple = false;
737 : :
738 : 115724 : itup = (IndexTuple) PageGetItem(page,
739 : 57862 : PageGetItemId(page, offno));
740 : 57862 : 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 [ + + + + ]: 57862 : if (callback && callback(htup, callback_state))
747 : : {
748 : 4999 : kill_tuple = true;
749 [ - + ]: 4999 : if (tuples_removed)
750 : 4999 : *tuples_removed += 1;
751 : 4999 : }
752 [ + + ]: 52863 : else if (split_cleanup)
753 : : {
754 : : /* delete the tuples that are moved by split. */
755 : 100526 : bucket = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
756 : 50263 : maxbucket,
757 : 50263 : highmask,
758 : 50263 : lowmask);
759 : : /* mark the item for deletion */
760 [ + + ]: 50263 : 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 [ - + ]: 20512 : Assert(bucket == new_bucket);
769 : 20512 : kill_tuple = true;
770 : 20512 : }
771 : 50263 : }
772 : :
773 [ + + ]: 57862 : if (kill_tuple)
774 : : {
775 : : /* mark the item for deletion */
776 : 25511 : deletable[ndeletable++] = offno;
777 : 25511 : }
778 : : else
779 : : {
780 : : /* we're keeping it, so count it */
781 [ + + ]: 32351 : if (num_index_tuples)
782 : 2600 : *num_index_tuples += 1;
783 : : }
784 : 57862 : }
785 : :
786 : : /* retain the pin on primary bucket page till end of bucket scan */
787 [ + + ]: 322 : if (blkno == bucket_blkno)
788 : 252 : retain_pin = true;
789 : : else
790 : 70 : retain_pin = false;
791 : :
792 : 322 : blkno = opaque->hasho_nextblkno;
793 : :
794 : : /*
795 : : * Apply deletions, advance to next page and write page if needed.
796 : : */
797 [ + + ]: 322 : if (ndeletable > 0)
798 : : {
799 : : /* No ereport(ERROR) until changes are logged */
800 : 248 : START_CRIT_SECTION();
801 : :
802 : 248 : PageIndexMultiDelete(page, deletable, ndeletable);
803 : 248 : 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 [ + + + - : 248 : if (tuples_removed && *tuples_removed > 0 &&
+ - ]
811 : 18 : H_HAS_DEAD_TUPLES(opaque))
812 : : {
813 : 0 : opaque->hasho_flag &= ~LH_PAGE_HAS_DEAD_TUPLES;
814 : 0 : clear_dead_marking = true;
815 : 0 : }
816 : :
817 : 248 : MarkBufferDirty(buf);
818 : :
819 : : /* XLOG stuff */
820 [ + - + - : 248 : if (RelationNeedsWAL(rel))
+ + + + ]
821 : : {
822 : 122 : xl_hash_delete xlrec;
823 : 122 : XLogRecPtr recptr;
824 : :
825 : 122 : xlrec.clear_dead_marking = clear_dead_marking;
826 : 122 : xlrec.is_primary_bucket_page = (buf == bucket_buf);
827 : :
828 : 122 : XLogBeginInsert();
829 : 122 : 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 [ + + ]: 122 : if (!xlrec.is_primary_bucket_page)
837 : : {
838 : 32 : uint8 flags = REGBUF_STANDARD | REGBUF_NO_IMAGE | REGBUF_NO_CHANGE;
839 : :
840 : 32 : XLogRegisterBuffer(0, bucket_buf, flags);
841 : 32 : }
842 : :
843 : 122 : XLogRegisterBuffer(1, buf, REGBUF_STANDARD);
844 : 244 : XLogRegisterBufData(1, deletable,
845 : 122 : ndeletable * sizeof(OffsetNumber));
846 : :
847 : 122 : recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_DELETE);
848 : 122 : PageSetLSN(BufferGetPage(buf), recptr);
849 : 122 : }
850 : :
851 [ - + ]: 248 : END_CRIT_SECTION();
852 : 248 : }
853 : :
854 : : /* bail out if there are no more pages to scan. */
855 [ + + ]: 322 : if (!BlockNumberIsValid(blkno))
856 : 252 : break;
857 : :
858 : 140 : next_buf = _hash_getbuf_with_strategy(rel, blkno, HASH_WRITE,
859 : : LH_OVERFLOW_PAGE,
860 : 70 : bstrategy);
861 : :
862 : : /*
863 : : * release the lock on previous page after acquiring the lock on next
864 : : * page
865 : : */
866 [ + + ]: 70 : if (retain_pin)
867 : 13 : LockBuffer(buf, BUFFER_LOCK_UNLOCK);
868 : : else
869 : 57 : _hash_relbuf(rel, buf);
870 : :
871 : 70 : buf = next_buf;
872 [ - + + ]: 322 : }
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 [ + + ]: 252 : if (buf != bucket_buf)
880 : : {
881 : 13 : _hash_relbuf(rel, buf);
882 : 13 : LockBuffer(bucket_buf, BUFFER_LOCK_EXCLUSIVE);
883 : 13 : }
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 [ + + ]: 252 : if (split_cleanup)
892 : : {
893 : 221 : HashPageOpaque bucket_opaque;
894 : 221 : Page page;
895 : :
896 : 221 : page = BufferGetPage(bucket_buf);
897 : 221 : bucket_opaque = HashPageGetOpaque(page);
898 : :
899 : : /* No ereport(ERROR) until changes are logged */
900 : 221 : START_CRIT_SECTION();
901 : :
902 : 221 : bucket_opaque->hasho_flag &= ~LH_BUCKET_NEEDS_SPLIT_CLEANUP;
903 : 221 : MarkBufferDirty(bucket_buf);
904 : :
905 : : /* XLOG stuff */
906 [ + - + - : 221 : if (RelationNeedsWAL(rel))
+ + + + ]
907 : : {
908 : 95 : XLogRecPtr recptr;
909 : :
910 : 95 : XLogBeginInsert();
911 : 95 : XLogRegisterBuffer(0, bucket_buf, REGBUF_STANDARD);
912 : :
913 : 95 : recptr = XLogInsert(RM_HASH_ID, XLOG_HASH_SPLIT_CLEANUP);
914 : 95 : PageSetLSN(page, recptr);
915 : 95 : }
916 : :
917 [ + - ]: 221 : END_CRIT_SECTION();
918 : 221 : }
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 [ + + - + ]: 252 : if (bucket_dirty && IsBufferCleanupOK(bucket_buf))
926 : 440 : _hash_squeezebucket(rel, cur_bucket, bucket_blkno, bucket_buf,
927 : 220 : bstrategy);
928 : : else
929 : 32 : LockBuffer(bucket_buf, BUFFER_LOCK_UNLOCK);
930 : 252 : }
931 : :
932 : : CompareType
933 : 0 : hashtranslatestrategy(StrategyNumber strategy, Oid opfamily)
934 : : {
935 [ # # ]: 0 : if (strategy == HTEqualStrategyNumber)
936 : 0 : return COMPARE_EQ;
937 : 0 : return COMPARE_INVALID;
938 : 0 : }
939 : :
940 : : StrategyNumber
941 : 0 : hashtranslatecmptype(CompareType cmptype, Oid opfamily)
942 : : {
943 [ # # ]: 0 : if (cmptype == COMPARE_EQ)
944 : 0 : return HTEqualStrategyNumber;
945 : 0 : return InvalidStrategy;
946 : 0 : }
|
