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 *
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
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
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
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