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