Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * hashsort.c
4 : * Sort tuples for insertion into a new hash index.
5 : *
6 : * When building a very large hash index, we pre-sort the tuples by bucket
7 : * number to improve locality of access to the index, and thereby avoid
8 : * thrashing. We use tuplesort.c to sort the given index tuples into order.
9 : *
10 : * Note: if the number of rows in the table has been underestimated,
11 : * bucket splits may occur during the index build. In that case we'd
12 : * be inserting into two or more buckets for each possible masked-off
13 : * hash code value. That's no big problem though, since we'll still have
14 : * plenty of locality of access.
15 : *
16 : *
17 : * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
18 : * Portions Copyright (c) 1994, Regents of the University of California
19 : *
20 : * IDENTIFICATION
21 : * src/backend/access/hash/hashsort.c
22 : *
23 : *-------------------------------------------------------------------------
24 : */
25 :
26 : #include "postgres.h"
27 :
28 : #include "access/hash.h"
29 : #include "commands/progress.h"
30 : #include "miscadmin.h"
31 : #include "pgstat.h"
32 : #include "port/pg_bitutils.h"
33 : #include "utils/tuplesort.h"
34 :
35 :
36 : /*
37 : * Status record for spooling/sorting phase.
38 : */
39 : struct HSpool
40 : {
41 : Tuplesortstate *sortstate; /* state data for tuplesort.c */
42 : Relation index;
43 :
44 : /*
45 : * We sort the hash keys based on the buckets they belong to, then by the
46 : * hash values themselves, to optimize insertions onto hash pages. The
47 : * masks below are used in _hash_hashkey2bucket to determine the bucket of
48 : * a given hash key.
49 : */
50 : uint32 high_mask;
51 : uint32 low_mask;
52 : uint32 max_buckets;
53 : };
54 :
55 :
56 : /*
57 : * create and initialize a spool structure
58 : */
59 : HSpool *
3722 tgl 60 GIC 4 : _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
5502 tgl 61 ECB : {
5502 tgl 62 GIC 4 : HSpool *hspool = (HSpool *) palloc0(sizeof(HSpool));
5502 tgl 63 ECB :
5502 tgl 64 GIC 4 : hspool->index = index;
5502 tgl 65 ECB :
66 : /*
67 : * Determine the bitmask for hash code values. Since there are currently
68 : * num_buckets buckets in the index, the appropriate mask can be computed
69 : * as follows.
70 : *
71 : * NOTE : This hash mask calculation should be in sync with similar
72 : * calculation in _hash_init_metabuffer.
73 : */
1096 drowley 74 GIC 4 : hspool->high_mask = pg_nextpower2_32(num_buckets + 1) - 1;
2197 rhaas 75 CBC 4 : hspool->low_mask = (hspool->high_mask >> 1);
76 4 : hspool->max_buckets = num_buckets - 1;
5502 tgl 77 ECB :
78 : /*
79 : * We size the sort area as maintenance_work_mem rather than work_mem to
80 : * speed index creation. This should be OK since a single backend can't
81 : * run multiple index creations in parallel.
82 : */
3722 tgl 83 GIC 4 : hspool->sortstate = tuplesort_begin_index_hash(heap,
3722 tgl 84 ECB : index,
85 : hspool->high_mask,
86 : hspool->low_mask,
87 : hspool->max_buckets,
88 : maintenance_work_mem,
89 : NULL,
90 : TUPLESORT_NONE);
91 :
5502 tgl 92 GIC 4 : return hspool;
5502 tgl 93 ECB : }
94 :
95 : /*
96 : * clean up a spool structure and its substructures.
97 : */
98 : void
5502 tgl 99 GIC 4 : _h_spooldestroy(HSpool *hspool)
5502 tgl 100 ECB : {
5502 tgl 101 GIC 4 : tuplesort_end(hspool->sortstate);
5502 tgl 102 CBC 4 : pfree(hspool);
103 4 : }
5502 tgl 104 ECB :
105 : /*
106 : * spool an index entry into the sort file.
107 : */
108 : void
3204 rhaas 109 GIC 60500 : _h_spool(HSpool *hspool, ItemPointer self, Datum *values, bool *isnull)
5502 tgl 110 ECB : {
3204 rhaas 111 GIC 60500 : tuplesort_putindextuplevalues(hspool->sortstate, hspool->index,
3204 rhaas 112 ECB : self, values, isnull);
5502 tgl 113 GIC 60500 : }
5502 tgl 114 ECB :
115 : /*
116 : * given a spool loaded by successive calls to _h_spool,
117 : * create an entire index.
118 : */
119 : void
2216 rhaas 120 GIC 4 : _h_indexbuild(HSpool *hspool, Relation heapRel)
5502 tgl 121 ECB : {
122 : IndexTuple itup;
1441 alvherre 123 GIC 4 : int64 tups_done = 0;
2458 tgl 124 ECB : #ifdef USE_ASSERT_CHECKING
2458 tgl 125 GIC 4 : uint32 hashkey = 0;
2458 tgl 126 ECB : #endif
127 :
5502 tgl 128 GIC 4 : tuplesort_performsort(hspool->sortstate);
5502 tgl 129 ECB :
2309 rhaas 130 GIC 60504 : while ((itup = tuplesort_getindextuple(hspool->sortstate, true)) != NULL)
5502 tgl 131 ECB : {
132 : /*
133 : * Technically, it isn't critical that hash keys be found in sorted
134 : * order, since this sorting is only used to increase locality of
135 : * access as a performance optimization. It still seems like a good
136 : * idea to test tuplesort.c's handling of hash index tuple sorts
137 : * through an assertion, though.
138 : */
139 : #ifdef USE_ASSERT_CHECKING
2458 tgl 140 GIC 60500 : uint32 lasthashkey = hashkey;
2458 tgl 141 ECB :
2197 rhaas 142 GIC 60500 : hashkey = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
2197 rhaas 143 ECB : hspool->max_buckets, hspool->high_mask,
144 : hspool->low_mask);
2458 tgl 145 GIC 60500 : Assert(hashkey >= lasthashkey);
2458 tgl 146 ECB : #endif
147 :
148 : /* the tuples are sorted by hashkey, so pass 'sorted' as true */
136 drowley 149 GNC 60500 : _hash_doinsert(hspool->index, itup, heapRel, true);
150 :
1468 alvherre 151 CBC 60500 : pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
152 : ++tups_done);
5502 tgl 153 ECB : }
5502 tgl 154 GIC 4 : }
|
