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