Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * ginbulk.c
4 : : * routines for fast build of inverted index
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2025, 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
2598 tgl@sss.pgh.pa.us 30 :CBC 1248590 : ginCombineData(RBTNode *existing, const RBTNode *newdata, void *arg)
31 : : {
5458 32 : 1248590 : GinEntryAccumulator *eo = (GinEntryAccumulator *) existing;
33 : 1248590 : const GinEntryAccumulator *en = (const GinEntryAccumulator *) newdata;
5773 bruce@momjian.us 34 : 1248590 : BuildAccumulator *accum = (BuildAccumulator *) arg;
35 : :
36 : : /*
37 : : * Note this code assumes that newdata contains only one itempointer.
38 : : */
5458 tgl@sss.pgh.pa.us 39 [ + + ]: 1248590 : if (eo->count >= eo->maxcount)
40 : : {
3759 teodor@sigaev.ru 41 [ - + ]: 44256 : if (eo->maxcount > INT_MAX)
3759 teodor@sigaev.ru 42 [ # # ]:UBC 0 : ereport(ERROR,
43 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
44 : : errmsg("posting list is too long"),
45 : : errhint("Reduce \"maintenance_work_mem\".")));
46 : :
5788 teodor@sigaev.ru 47 :CBC 44256 : accum->allocatedMemory -= GetMemoryChunkSpace(eo->list);
5458 tgl@sss.pgh.pa.us 48 : 44256 : eo->maxcount *= 2;
49 : 44256 : eo->list = (ItemPointerData *)
3759 teodor@sigaev.ru 50 : 44256 : repalloc_huge(eo->list, sizeof(ItemPointerData) * eo->maxcount);
5788 51 : 44256 : accum->allocatedMemory += GetMemoryChunkSpace(eo->list);
52 : : }
53 : :
54 : : /* If item pointers are not ordered, they will need to be sorted later */
3045 peter_e@gmx.net 55 [ + - ]: 1248590 : if (eo->shouldSort == false)
56 : : {
57 : : int res;
58 : :
5458 tgl@sss.pgh.pa.us 59 : 1248590 : res = ginCompareItemPointers(eo->list + eo->count - 1, en->list);
7014 bruce@momjian.us 60 [ - + ]: 1248590 : Assert(res != 0);
61 : :
62 [ - + ]: 1248590 : if (res > 0)
3045 peter_e@gmx.net 63 :UBC 0 : eo->shouldSort = true;
64 : : }
65 : :
5458 tgl@sss.pgh.pa.us 66 :CBC 1248590 : eo->list[eo->count] = en->list[0];
67 : 1248590 : eo->count++;
5788 teodor@sigaev.ru 68 : 1248590 : }
69 : :
70 : : /* Comparator function for rbtree.c */
71 : : static int
2598 tgl@sss.pgh.pa.us 72 : 14468116 : cmpEntryAccumulator(const RBTNode *a, const RBTNode *b, void *arg)
73 : : {
5458 74 : 14468116 : const GinEntryAccumulator *ea = (const GinEntryAccumulator *) a;
75 : 14468116 : const GinEntryAccumulator *eb = (const GinEntryAccumulator *) b;
5773 bruce@momjian.us 76 : 14468116 : BuildAccumulator *accum = (BuildAccumulator *) arg;
77 : :
5458 tgl@sss.pgh.pa.us 78 : 28936232 : return ginCompareAttEntries(accum->ginstate,
79 : 14468116 : ea->attnum, ea->key, ea->category,
80 : 14468116 : eb->attnum, eb->key, eb->category);
81 : : }
82 : :
83 : : /* Allocator function for rbtree.c */
84 : : static RBTNode *
5617 85 : 259322 : ginAllocEntryAccumulator(void *arg)
86 : : {
87 : 259322 : 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 RBTNodes individually, so this costs nothing.
93 : : */
5458 94 [ + + + + ]: 259322 : if (accum->entryallocator == NULL || accum->eas_used >= DEF_NENTRY)
95 : : {
7 michael@paquier.xyz 96 :GNC 289 : accum->entryallocator = palloc_array(GinEntryAccumulator, DEF_NENTRY);
5617 tgl@sss.pgh.pa.us 97 :CBC 289 : accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator);
5458 98 : 289 : accum->eas_used = 0;
99 : : }
100 : :
101 : : /* Allocate new RBTNode from current chunk */
102 : 259322 : ea = accum->entryallocator + accum->eas_used;
103 : 259322 : accum->eas_used++;
104 : :
2598 105 : 259322 : return (RBTNode *) ea;
106 : : }
107 : :
108 : : void
5788 teodor@sigaev.ru 109 : 217 : ginInitBA(BuildAccumulator *accum)
110 : : {
111 : : /* accum->ginstate is intentionally not set here */
112 : 217 : accum->allocatedMemory = 0;
113 : 217 : accum->entryallocator = NULL;
5458 tgl@sss.pgh.pa.us 114 : 217 : accum->eas_used = 0;
2598 115 : 217 : accum->tree = rbt_create(sizeof(GinEntryAccumulator),
116 : : cmpEntryAccumulator,
117 : : ginCombineData,
118 : : ginAllocEntryAccumulator,
119 : : NULL, /* no freefunc needed */
120 : : accum);
7169 teodor@sigaev.ru 121 : 217 : }
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
6368 tgl@sss.pgh.pa.us 128 : 259249 : getDatumCopy(BuildAccumulator *accum, OffsetNumber attnum, Datum value)
129 : : {
130 : : CompactAttribute *att;
131 : : Datum res;
132 : :
362 drowley@postgresql.o 133 : 259249 : att = TupleDescCompactAttr(accum->ginstate->origTupdesc, attnum - 1);
6368 tgl@sss.pgh.pa.us 134 [ + + ]: 259249 : if (att->attbyval)
7094 135 : 249838 : res = value;
136 : : else
137 : : {
6368 138 : 9411 : res = datumCopy(value, false, att->attlen);
6380 139 : 9411 : accum->allocatedMemory += GetMemoryChunkSpace(DatumGetPointer(res));
140 : : }
7094 141 : 259249 : return res;
142 : : }
143 : :
144 : : /*
145 : : * Find/store one entry from indexed value.
146 : : */
147 : : static void
5458 148 : 1507912 : ginInsertBAEntry(BuildAccumulator *accum,
149 : : ItemPointer heapptr, OffsetNumber attnum,
150 : : Datum key, GinNullCategory category)
151 : : {
152 : : GinEntryAccumulator eatmp;
153 : : GinEntryAccumulator *ea;
154 : : 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 : 1507912 : eatmp.attnum = attnum;
161 : 1507912 : eatmp.key = key;
162 : 1507912 : eatmp.category = category;
163 : : /* temporarily set up single-entry itempointer list */
164 : 1507912 : eatmp.list = heapptr;
165 : :
2598 166 : 1507912 : ea = (GinEntryAccumulator *) rbt_insert(accum->tree, (RBTNode *) &eatmp,
167 : : &isNew);
168 : :
5617 169 [ + + ]: 1507912 : if (isNew)
170 : : {
171 : : /*
172 : : * Finish initializing new tree entry, including making permanent
173 : : * copies of the datum (if it's not null) and itempointer.
174 : : */
5458 175 [ + + ]: 259322 : if (category == GIN_CAT_NORM_KEY)
176 : 259249 : ea->key = getDatumCopy(accum, attnum, key);
177 : 259322 : ea->maxcount = DEF_NPTR;
178 : 259322 : ea->count = 1;
3045 peter_e@gmx.net 179 : 259322 : ea->shouldSort = false;
7 michael@paquier.xyz 180 :GNC 259322 : ea->list = palloc_array(ItemPointerData, DEF_NPTR);
5617 tgl@sss.pgh.pa.us 181 :CBC 259322 : ea->list[0] = *heapptr;
182 : 259322 : accum->allocatedMemory += GetMemoryChunkSpace(ea->list);
183 : : }
184 : : else
185 : : {
186 : : /*
187 : : * ginCombineData did everything needed.
188 : : */
189 : : }
7099 teodor@sigaev.ru 190 : 1507912 : }
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
5458 tgl@sss.pgh.pa.us 209 : 664005 : ginInsertBAEntries(BuildAccumulator *accum,
210 : : ItemPointer heapptr, OffsetNumber attnum,
211 : : Datum *entries, GinNullCategory *categories,
212 : : int32 nentries)
213 : : {
214 : 664005 : uint32 step = nentries;
215 : :
216 [ - + ]: 664005 : if (nentries <= 0)
7099 teodor@sigaev.ru 217 :UBC 0 : return;
218 : :
6112 tgl@sss.pgh.pa.us 219 [ + - - + ]:CBC 664005 : Assert(ItemPointerIsValid(heapptr) && attnum >= FirstOffsetNumber);
220 : :
221 : : /*
222 : : * step will contain largest power of 2 and <= nentries
223 : : */
5773 bruce@momjian.us 224 : 664005 : step |= (step >> 1);
225 : 664005 : step |= (step >> 2);
226 : 664005 : step |= (step >> 4);
227 : 664005 : step |= (step >> 8);
5788 teodor@sigaev.ru 228 : 664005 : step |= (step >> 16);
229 : 664005 : step >>= 1;
5773 bruce@momjian.us 230 : 664005 : step++;
231 : :
232 [ + + ]: 1668371 : while (step > 0)
233 : : {
234 : : int i;
235 : :
5458 tgl@sss.pgh.pa.us 236 [ + + + - ]: 2512278 : for (i = step - 1; i < nentries && i >= 0; i += step << 1 /* *2 */ )
237 : 1507912 : ginInsertBAEntry(accum, heapptr, attnum,
238 : 1507912 : entries[i], categories[i]);
239 : :
5773 bruce@momjian.us 240 : 1004366 : step >>= 1; /* /2 */
241 : : }
242 : : }
243 : :
244 : : static int
7014 bruce@momjian.us 245 :UBC 0 : qsortCompareItemPointers(const void *a, const void *b)
246 : : {
5540 tgl@sss.pgh.pa.us 247 : 0 : int res = ginCompareItemPointers((ItemPointer) a, (ItemPointer) b);
248 : :
249 : : /* Assert that there are no equal item pointers being sorted */
7014 bruce@momjian.us 250 [ # # ]: 0 : Assert(res != 0);
7169 teodor@sigaev.ru 251 : 0 : return res;
252 : : }
253 : :
254 : : /* Prepare to read out the rbtree contents using ginGetBAEntry */
255 : : void
5617 tgl@sss.pgh.pa.us 256 :CBC 217 : ginBeginBAScan(BuildAccumulator *accum)
257 : : {
2598 258 : 217 : rbt_begin_iterate(accum->tree, LeftRightWalk, &accum->tree_walk);
5617 259 : 217 : }
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 *
5458 267 : 259539 : ginGetBAEntry(BuildAccumulator *accum,
268 : : OffsetNumber *attnum, Datum *key, GinNullCategory *category,
269 : : uint32 *n)
270 : : {
271 : : GinEntryAccumulator *entry;
272 : : ItemPointerData *list;
273 : :
2598 274 : 259539 : entry = (GinEntryAccumulator *) rbt_iterate(&accum->tree_walk);
275 : :
7014 bruce@momjian.us 276 [ + + ]: 259539 : if (entry == NULL)
5458 tgl@sss.pgh.pa.us 277 : 217 : return NULL; /* no more entries */
278 : :
6368 279 : 259322 : *attnum = entry->attnum;
5458 280 : 259322 : *key = entry->key;
281 : 259322 : *category = entry->category;
7014 bruce@momjian.us 282 : 259322 : list = entry->list;
5458 tgl@sss.pgh.pa.us 283 : 259322 : *n = entry->count;
284 : :
285 [ + - - + ]: 259322 : Assert(list != NULL && entry->count > 0);
286 : :
287 [ - + - - ]: 259322 : if (entry->shouldSort && entry->count > 1)
5458 tgl@sss.pgh.pa.us 288 :UBC 0 : qsort(list, entry->count, sizeof(ItemPointerData),
289 : : qsortCompareItemPointers);
290 : :
7169 teodor@sigaev.ru 291 :CBC 259322 : return list;
292 : : }
|
