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-2018, 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 "miscadmin.h"
30 #include "utils/tuplesort.h"
31
32
33 /*
34 * Status record for spooling/sorting phase.
35 */
36 struct HSpool
37 {
38 Tuplesortstate *sortstate; /* state data for tuplesort.c */
39 Relation index;
40
41 /*
42 * We sort the hash keys based on the buckets they belong to. Below masks
43 * are used in _hash_hashkey2bucket to determine the bucket of given hash
44 * key.
45 */
46 uint32 high_mask;
47 uint32 low_mask;
48 uint32 max_buckets;
49 };
50
51
52 /*
53 * create and initialize a spool structure
54 */
55 HSpool *
_h_spoolinit(Relation heap,Relation index,uint32 num_buckets)56 _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
57 {
58 HSpool *hspool = (HSpool *) palloc0(sizeof(HSpool));
59
60 hspool->index = index;
61
62 /*
63 * Determine the bitmask for hash code values. Since there are currently
64 * num_buckets buckets in the index, the appropriate mask can be computed
65 * as follows.
66 *
67 * NOTE : This hash mask calculation should be in sync with similar
68 * calculation in _hash_init_metabuffer.
69 */
70 hspool->high_mask = (((uint32) 1) << _hash_log2(num_buckets + 1)) - 1;
71 hspool->low_mask = (hspool->high_mask >> 1);
72 hspool->max_buckets = num_buckets - 1;
73
74 /*
75 * We size the sort area as maintenance_work_mem rather than work_mem to
76 * speed index creation. This should be OK since a single backend can't
77 * run multiple index creations in parallel.
78 */
79 hspool->sortstate = tuplesort_begin_index_hash(heap,
80 index,
81 hspool->high_mask,
82 hspool->low_mask,
83 hspool->max_buckets,
84 maintenance_work_mem,
85 NULL,
86 false);
87
88 return hspool;
89 }
90
91 /*
92 * clean up a spool structure and its substructures.
93 */
94 void
_h_spooldestroy(HSpool * hspool)95 _h_spooldestroy(HSpool *hspool)
96 {
97 tuplesort_end(hspool->sortstate);
98 pfree(hspool);
99 }
100
101 /*
102 * spool an index entry into the sort file.
103 */
104 void
_h_spool(HSpool * hspool,ItemPointer self,Datum * values,bool * isnull)105 _h_spool(HSpool *hspool, ItemPointer self, Datum *values, bool *isnull)
106 {
107 tuplesort_putindextuplevalues(hspool->sortstate, hspool->index,
108 self, values, isnull);
109 }
110
111 /*
112 * given a spool loaded by successive calls to _h_spool,
113 * create an entire index.
114 */
115 void
_h_indexbuild(HSpool * hspool,Relation heapRel)116 _h_indexbuild(HSpool *hspool, Relation heapRel)
117 {
118 IndexTuple itup;
119 #ifdef USE_ASSERT_CHECKING
120 uint32 hashkey = 0;
121 #endif
122
123 tuplesort_performsort(hspool->sortstate);
124
125 while ((itup = tuplesort_getindextuple(hspool->sortstate, true)) != NULL)
126 {
127 /*
128 * Technically, it isn't critical that hash keys be found in sorted
129 * order, since this sorting is only used to increase locality of
130 * access as a performance optimization. It still seems like a good
131 * idea to test tuplesort.c's handling of hash index tuple sorts
132 * through an assertion, though.
133 */
134 #ifdef USE_ASSERT_CHECKING
135 uint32 lasthashkey = hashkey;
136
137 hashkey = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
138 hspool->max_buckets, hspool->high_mask,
139 hspool->low_mask);
140 Assert(hashkey >= lasthashkey);
141 #endif
142
143 _hash_doinsert(hspool->index, itup, heapRel);
144 }
145 }
146