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