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