PostgreSQL Source Code: src/backend/access/hash/hashsort.c Source File

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-2025, 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 */
59HSpool *
60 _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
61{
62 HSpool *hspool = (HSpool *) palloc0(sizeof(HSpool));
63
64 hspool->index = index;
65
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 */
74 hspool->high_mask = pg_nextpower2_32(num_buckets + 1) - 1;
75 hspool->low_mask = (hspool->high_mask >> 1);
76 hspool->max_buckets = num_buckets - 1;
77
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 */
83 hspool->sortstate = tuplesort_begin_index_hash(heap,
84 index,
85 hspool->high_mask,
86 hspool->low_mask,
87 hspool->max_buckets,
88 maintenance_work_mem,
89 NULL,
90 TUPLESORT_NONE);
91
92 return hspool;
93}
94
95/*
96 * clean up a spool structure and its substructures.
97 */
98void
99 _h_spooldestroy(HSpool *hspool)
100{
101 tuplesort_end(hspool->sortstate);
102 pfree(hspool);
103}
104
105/*
106 * spool an index entry into the sort file.
107 */
108void
109 _h_spool(HSpool *hspool, ItemPointer self, const Datum *values, const bool *isnull)
110{
111 tuplesort_putindextuplevalues(hspool->sortstate, hspool->index,
112 self, values, isnull);
113}
114
115/*
116 * given a spool loaded by successive calls to _h_spool,
117 * create an entire index.
118 */
119void
120 _h_indexbuild(HSpool *hspool, Relation heapRel)
121{
122 IndexTuple itup;
123 int64 tups_done = 0;
124#ifdef USE_ASSERT_CHECKING
125 uint32 hashkey = 0;
126#endif
127
128 tuplesort_performsort(hspool->sortstate);
129
130 while ((itup = tuplesort_getindextuple(hspool->sortstate, true)) != NULL)
131 {
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
140 uint32 lasthashkey = hashkey;
141
142 hashkey = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
143 hspool->max_buckets, hspool->high_mask,
144 hspool->low_mask);
145 Assert(hashkey >= lasthashkey);
146#endif
147
148 /* the tuples are sorted by hashkey, so pass 'sorted' as true */
149 _hash_doinsert(hspool->index, itup, heapRel, true);
150
151 /* allow insertion phase to be interrupted, and track progress */
152 CHECK_FOR_INTERRUPTS();
153
154 pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
155 ++tups_done);
156 }
157}
void pgstat_progress_update_param(int index, int64 val)
static Datum values[MAXATTR]
Definition: bootstrap.c:153
int64_t int64
Definition: c.h:535
uint32_t uint32
Definition: c.h:538
int maintenance_work_mem
Definition: globals.c:133
Assert(PointerIsAligned(start, uint64))
void _hash_doinsert(Relation rel, IndexTuple itup, Relation heapRel, bool sorted)
Definition: hashinsert.c:38
void _h_spool(HSpool *hspool, ItemPointer self, const Datum *values, const bool *isnull)
Definition: hashsort.c:109
void _h_indexbuild(HSpool *hspool, Relation heapRel)
Definition: hashsort.c:120
HSpool * _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
Definition: hashsort.c:60
void _h_spooldestroy(HSpool *hspool)
Definition: hashsort.c:99
uint32 _hash_get_indextuple_hashkey(IndexTuple itup)
Definition: hashutil.c:291
Bucket _hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket, uint32 highmask, uint32 lowmask)
Definition: hashutil.c:125
void pfree(void *pointer)
Definition: mcxt.c:1594
void * palloc0(Size size)
Definition: mcxt.c:1395
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
static uint32 pg_nextpower2_32(uint32 num)
Definition: pg_bitutils.h:189
uint64_t Datum
Definition: postgres.h:70
#define PROGRESS_CREATEIDX_TUPLES_DONE
Definition: progress.h:90
Definition: hashsort.c:40
uint32 low_mask
Definition: hashsort.c:51
Tuplesortstate * sortstate
Definition: hashsort.c:41
uint32 high_mask
Definition: hashsort.c:50
uint32 max_buckets
Definition: hashsort.c:52
Relation index
Definition: hashsort.c:42
Definition: rel.h:56
Definition: type.h:96
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:1359
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:947
#define TUPLESORT_NONE
Definition: tuplesort.h:94
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, const Datum *values, const bool *isnull)
Tuplesortstate * tuplesort_begin_index_hash(Relation heapRel, Relation indexRel, uint32 high_mask, uint32 low_mask, uint32 max_buckets, int workMem, SortCoordinate coordinate, int sortopt)

AltStyle によって変換されたページ (->オリジナル) /