PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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 */
40  uint32 hash_mask; /* bitmask for hash codes */
41 };
42 
43 
44 /*
45  * create and initialize a spool structure
46  */
47 HSpool *
49 {
50  HSpool *hspool = (HSpool *) palloc0(sizeof(HSpool));
51 
52  hspool->index = index;
53 
54  /*
55  * Determine the bitmask for hash code values. Since there are currently
56  * num_buckets buckets in the index, the appropriate mask can be computed
57  * as follows.
58  *
59  * Note: at present, the passed-in num_buckets is always a power of 2, so
60  * we could just compute num_buckets - 1. We prefer not to assume that
61  * here, though.
62  */
63  hspool->hash_mask = (((uint32) 1) << _hash_log2(num_buckets)) - 1;
64 
65  /*
66  * We size the sort area as maintenance_work_mem rather than work_mem to
67  * speed index creation. This should be OK since a single backend can't
68  * run multiple index creations in parallel.
69  */
71  index,
72  hspool->hash_mask,
74  false);
75 
76  return hspool;
77 }
78 
79 /*
80  * clean up a spool structure and its substructures.
81  */
82 void
84 {
85  tuplesort_end(hspool->sortstate);
86  pfree(hspool);
87 }
88 
89 /*
90  * spool an index entry into the sort file.
91  */
92 void
93 _h_spool(HSpool *hspool, ItemPointer self, Datum *values, bool *isnull)
94 {
96  self, values, isnull);
97 }
98 
99 /*
100  * given a spool loaded by successive calls to _h_spool,
101  * create an entire index.
102  */
103 void
105 {
106  IndexTuple itup;
107 #ifdef USE_ASSERT_CHECKING
108  uint32 hashkey = 0;
109 #endif
110 
112 
113  while ((itup = tuplesort_getindextuple(hspool->sortstate, true)) != NULL)
114  {
115  /*
116  * Technically, it isn't critical that hash keys be found in sorted
117  * order, since this sorting is only used to increase locality of
118  * access as a performance optimization. It still seems like a good
119  * idea to test tuplesort.c's handling of hash index tuple sorts
120  * through an assertion, though.
121  */
122 #ifdef USE_ASSERT_CHECKING
123  uint32 lasthashkey = hashkey;
124 
125  hashkey = _hash_get_indextuple_hashkey(itup) & hspool->hash_mask;
126  Assert(hashkey >= lasthashkey);
127 #endif
128 
129  _hash_doinsert(hspool->index, itup);
130  }
131 }
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2154
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1763
Tuplesortstate * sortstate
Definition: hashsort.c:38
Definition: type.h:90
void pfree(void *pointer)
Definition: mcxt.c:992
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:232
Tuplesortstate * tuplesort_begin_index_hash(Relation heapRel, Relation indexRel, uint32 hash_mask, int workMem, bool randomAccess)
Definition: tuplesort.c:992
void _h_spool(HSpool *hspool, ItemPointer self, Datum *values, bool *isnull)
Definition: hashsort.c:93
unsigned int uint32
Definition: c.h:265
void _hash_doinsert(Relation rel, IndexTuple itup)
Definition: hashinsert.c:29
void * palloc0(Size size)
Definition: mcxt.c:920
uintptr_t Datum
Definition: postgres.h:374
Relation index
Definition: hashsort.c:39
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
Definition: tuplesort.c:1397
int maintenance_work_mem
Definition: globals.c:113
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:670
void _h_indexbuild(HSpool *hspool)
Definition: hashsort.c:104
static Datum values[MAXATTR]
Definition: bootstrap.c:162
void _h_spooldestroy(HSpool *hspool)
Definition: hashsort.c:83
uint32 _hash_log2(uint32 num)
Definition: hashutil.c:140
uint32 hash_mask
Definition: hashsort.c:40
HSpool * _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
Definition: hashsort.c:48
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1157