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