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