/Users/deen/code/yugabyte-db/src/postgres/src/backend/access/gin/ginbulk.c
Line | Count | Source (jump to first uncovered line) |
1 | | /*------------------------------------------------------------------------- |
2 | | * |
3 | | * ginbulk.c |
4 | | * routines for fast build of inverted index |
5 | | * |
6 | | * |
7 | | * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group |
8 | | * Portions Copyright (c) 1994, Regents of the University of California |
9 | | * |
10 | | * IDENTIFICATION |
11 | | * src/backend/access/gin/ginbulk.c |
12 | | *------------------------------------------------------------------------- |
13 | | */ |
14 | | |
15 | | #include "postgres.h" |
16 | | |
17 | | #include <limits.h> |
18 | | |
19 | | #include "access/gin_private.h" |
20 | | #include "utils/datum.h" |
21 | | #include "utils/memutils.h" |
22 | | |
23 | | |
24 | 73 | #define DEF_NENTRY 2048 /* GinEntryAccumulator allocation quantum */ |
25 | 146 | #define DEF_NPTR 5 /* ItemPointer initial allocation quantum */ |
26 | | |
27 | | |
28 | | /* Combiner function for rbtree.c */ |
29 | | static void |
30 | | ginCombineData(RBTNode *existing, const RBTNode *newdata, void *arg) |
31 | 10 | { |
32 | 10 | GinEntryAccumulator *eo = (GinEntryAccumulator *) existing; |
33 | 10 | const GinEntryAccumulator *en = (const GinEntryAccumulator *) newdata; |
34 | 10 | BuildAccumulator *accum = (BuildAccumulator *) arg; |
35 | | |
36 | | /* |
37 | | * Note this code assumes that newdata contains only one itempointer. |
38 | | */ |
39 | 10 | if (eo->count >= eo->maxcount) |
40 | 0 | { |
41 | 0 | if (eo->maxcount > INT_MAX) |
42 | 0 | ereport(ERROR, |
43 | 0 | (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), |
44 | 0 | errmsg("posting list is too long"), |
45 | 0 | errhint("Reduce maintenance_work_mem."))); |
46 | | |
47 | 0 | accum->allocatedMemory -= GetMemoryChunkSpace(eo->list); |
48 | 0 | eo->maxcount *= 2; |
49 | 0 | eo->list = (ItemPointerData *) |
50 | 0 | repalloc_huge(eo->list, sizeof(ItemPointerData) * eo->maxcount); |
51 | 0 | accum->allocatedMemory += GetMemoryChunkSpace(eo->list); |
52 | 0 | } |
53 | | |
54 | | /* If item pointers are not ordered, they will need to be sorted later */ |
55 | 10 | if (eo->shouldSort == false) |
56 | 10 | { |
57 | 10 | int res; |
58 | | |
59 | 10 | res = ginCompareItemPointers(eo->list + eo->count - 1, en->list); |
60 | 10 | Assert(res != 0); |
61 | | |
62 | 10 | if (res > 0) |
63 | 0 | eo->shouldSort = true; |
64 | 10 | } |
65 | | |
66 | 10 | eo->list[eo->count] = en->list[0]; |
67 | 10 | eo->count++; |
68 | 10 | } |
69 | | |
70 | | /* Comparator function for rbtree.c */ |
71 | | static int |
72 | | cmpEntryAccumulator(const RBTNode *a, const RBTNode *b, void *arg) |
73 | 140 | { |
74 | 140 | const GinEntryAccumulator *ea = (const GinEntryAccumulator *) a; |
75 | 140 | const GinEntryAccumulator *eb = (const GinEntryAccumulator *) b; |
76 | 140 | BuildAccumulator *accum = (BuildAccumulator *) arg; |
77 | | |
78 | 140 | return ginCompareAttEntries(accum->ginstate, |
79 | 140 | ea->attnum, ea->key, ea->category, |
80 | 140 | eb->attnum, eb->key, eb->category); |
81 | 140 | } |
82 | | |
83 | | /* Allocator function for rbtree.c */ |
84 | | static RBTNode * |
85 | | ginAllocEntryAccumulator(void *arg) |
86 | 73 | { |
87 | 73 | BuildAccumulator *accum = (BuildAccumulator *) arg; |
88 | 73 | GinEntryAccumulator *ea; |
89 | | |
90 | | /* |
91 | | * Allocate memory by rather big chunks to decrease overhead. We have no |
92 | | * need to reclaim RBTNodes individually, so this costs nothing. |
93 | | */ |
94 | 73 | if (accum->entryallocator == NULL || accum->eas_used >= 60 DEF_NENTRY60 ) |
95 | 13 | { |
96 | 13 | accum->entryallocator = palloc(sizeof(GinEntryAccumulator) * DEF_NENTRY); |
97 | 13 | accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator); |
98 | 13 | accum->eas_used = 0; |
99 | 13 | } |
100 | | |
101 | | /* Allocate new RBTNode from current chunk */ |
102 | 73 | ea = accum->entryallocator + accum->eas_used; |
103 | 73 | accum->eas_used++; |
104 | | |
105 | 73 | return (RBTNode *) ea; |
106 | 73 | } |
107 | | |
108 | | void |
109 | | ginInitBA(BuildAccumulator *accum) |
110 | 15 | { |
111 | | /* accum->ginstate is intentionally not set here */ |
112 | 15 | accum->allocatedMemory = 0; |
113 | 15 | accum->entryallocator = NULL; |
114 | 15 | accum->eas_used = 0; |
115 | 15 | accum->tree = rbt_create(sizeof(GinEntryAccumulator), |
116 | 15 | cmpEntryAccumulator, |
117 | 15 | ginCombineData, |
118 | 15 | ginAllocEntryAccumulator, |
119 | 15 | NULL, /* no freefunc needed */ |
120 | 15 | (void *) accum); |
121 | 15 | } |
122 | | |
123 | | /* |
124 | | * This is basically the same as datumCopy(), but extended to count |
125 | | * palloc'd space in accum->allocatedMemory. |
126 | | */ |
127 | | static Datum |
128 | | getDatumCopy(BuildAccumulator *accum, OffsetNumber attnum, Datum value) |
129 | 73 | { |
130 | 73 | Form_pg_attribute att; |
131 | 73 | Datum res; |
132 | | |
133 | 73 | att = TupleDescAttr(accum->ginstate->origTupdesc, attnum - 1); |
134 | 73 | if (att->attbyval) |
135 | 35 | res = value; |
136 | 38 | else |
137 | 38 | { |
138 | 38 | res = datumCopy(value, false, att->attlen); |
139 | 38 | accum->allocatedMemory += GetMemoryChunkSpace(DatumGetPointer(res)); |
140 | 38 | } |
141 | 73 | return res; |
142 | 73 | } |
143 | | |
144 | | /* |
145 | | * Find/store one entry from indexed value. |
146 | | */ |
147 | | static void |
148 | | ginInsertBAEntry(BuildAccumulator *accum, |
149 | | ItemPointer heapptr, OffsetNumber attnum, |
150 | | Datum key, GinNullCategory category) |
151 | 83 | { |
152 | 83 | GinEntryAccumulator eatmp; |
153 | 83 | GinEntryAccumulator *ea; |
154 | 83 | bool isNew; |
155 | | |
156 | | /* |
157 | | * For the moment, fill only the fields of eatmp that will be looked at by |
158 | | * cmpEntryAccumulator or ginCombineData. |
159 | | */ |
160 | 83 | eatmp.attnum = attnum; |
161 | 83 | eatmp.key = key; |
162 | 83 | eatmp.category = category; |
163 | | /* temporarily set up single-entry itempointer list */ |
164 | 83 | eatmp.list = heapptr; |
165 | | |
166 | 83 | ea = (GinEntryAccumulator *) rbt_insert(accum->tree, (RBTNode *) &eatmp, |
167 | 83 | &isNew); |
168 | | |
169 | 83 | if (isNew) |
170 | 73 | { |
171 | | /* |
172 | | * Finish initializing new tree entry, including making permanent |
173 | | * copies of the datum (if it's not null) and itempointer. |
174 | | */ |
175 | 73 | if (category == GIN_CAT_NORM_KEY) |
176 | 73 | ea->key = getDatumCopy(accum, attnum, key); |
177 | 73 | ea->maxcount = DEF_NPTR; |
178 | 73 | ea->count = 1; |
179 | 73 | ea->shouldSort = false; |
180 | 73 | ea->list = |
181 | 73 | (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR); |
182 | 73 | ea->list[0] = *heapptr; |
183 | 73 | accum->allocatedMemory += GetMemoryChunkSpace(ea->list); |
184 | 73 | } |
185 | 10 | else |
186 | 10 | { |
187 | | /* |
188 | | * ginCombineData did everything needed. |
189 | | */ |
190 | 10 | } |
191 | 83 | } |
192 | | |
193 | | /* |
194 | | * Insert the entries for one heap pointer. |
195 | | * |
196 | | * Since the entries are being inserted into a balanced binary tree, you |
197 | | * might think that the order of insertion wouldn't be critical, but it turns |
198 | | * out that inserting the entries in sorted order results in a lot of |
199 | | * rebalancing operations and is slow. To prevent this, we attempt to insert |
200 | | * the nodes in an order that will produce a nearly-balanced tree if the input |
201 | | * is in fact sorted. |
202 | | * |
203 | | * We do this as follows. First, we imagine that we have an array whose size |
204 | | * is the smallest power of two greater than or equal to the actual array |
205 | | * size. Second, we insert the middle entry of our virtual array into the |
206 | | * tree; then, we insert the middles of each half of our virtual array, then |
207 | | * middles of quarters, etc. |
208 | | */ |
209 | | void |
210 | | ginInsertBAEntries(BuildAccumulator *accum, |
211 | | ItemPointer heapptr, OffsetNumber attnum, |
212 | | Datum *entries, GinNullCategory *categories, |
213 | | int32 nentries) |
214 | 35 | { |
215 | 35 | uint32 step = nentries; |
216 | | |
217 | 35 | if (nentries <= 0) |
218 | 0 | return; |
219 | | |
220 | 35 | Assert(ItemPointerIsValid(heapptr) && attnum >= FirstOffsetNumber); |
221 | | |
222 | | /* |
223 | | * step will contain largest power of 2 and <= nentries |
224 | | */ |
225 | 35 | step |= (step >> 1); |
226 | 35 | step |= (step >> 2); |
227 | 35 | step |= (step >> 4); |
228 | 35 | step |= (step >> 8); |
229 | 35 | step |= (step >> 16); |
230 | 35 | step >>= 1; |
231 | 35 | step++; |
232 | | |
233 | 101 | while (step > 0) |
234 | 66 | { |
235 | 66 | int i; |
236 | | |
237 | 149 | for (i = step - 1; i < nentries && i >= 083 ; i += step << 183 /* *2 */ ) |
238 | 83 | ginInsertBAEntry(accum, heapptr, attnum, |
239 | 83 | entries[i], categories[i]); |
240 | | |
241 | 66 | step >>= 1; /* /2 */ |
242 | 66 | } |
243 | 35 | } |
244 | | |
245 | | static int |
246 | | qsortCompareItemPointers(const void *a, const void *b) |
247 | 0 | { |
248 | 0 | int res = ginCompareItemPointers((ItemPointer) a, (ItemPointer) b); |
249 | | |
250 | | /* Assert that there are no equal item pointers being sorted */ |
251 | 0 | Assert(res != 0); |
252 | 0 | return res; |
253 | 0 | } |
254 | | |
255 | | /* Prepare to read out the rbtree contents using ginGetBAEntry */ |
256 | | void |
257 | | ginBeginBAScan(BuildAccumulator *accum) |
258 | 15 | { |
259 | 15 | rbt_begin_iterate(accum->tree, LeftRightWalk, &accum->tree_walk); |
260 | 15 | } |
261 | | |
262 | | /* |
263 | | * Get the next entry in sequence from the BuildAccumulator's rbtree. |
264 | | * This consists of a single key datum and a list (array) of one or more |
265 | | * heap TIDs in which that key is found. The list is guaranteed sorted. |
266 | | */ |
267 | | ItemPointerData * |
268 | | ginGetBAEntry(BuildAccumulator *accum, |
269 | | OffsetNumber *attnum, Datum *key, GinNullCategory *category, |
270 | | uint32 *n) |
271 | 88 | { |
272 | 88 | GinEntryAccumulator *entry; |
273 | 88 | ItemPointerData *list; |
274 | | |
275 | 88 | entry = (GinEntryAccumulator *) rbt_iterate(&accum->tree_walk); |
276 | | |
277 | 88 | if (entry == NULL) |
278 | 15 | return NULL; /* no more entries */ |
279 | | |
280 | 73 | *attnum = entry->attnum; |
281 | 73 | *key = entry->key; |
282 | 73 | *category = entry->category; |
283 | 73 | list = entry->list; |
284 | 73 | *n = entry->count; |
285 | | |
286 | 73 | Assert(list != NULL && entry->count > 0); |
287 | | |
288 | 73 | if (entry->shouldSort && entry->count > 10 ) |
289 | 0 | qsort(list, entry->count, sizeof(ItemPointerData), |
290 | 73 | qsortCompareItemPointers); |
291 | | |
292 | 73 | return list; |
293 | 73 | } |