PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
ginbulk.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * ginbulk.c
4  * routines for fast build of inverted index
5  *
6  *
7  * Portions Copyright (c) 1996-2017, 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
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 
48  eo->maxcount *= 2;
49  eo->list = (ItemPointerData *)
50  repalloc_huge(eo->list, sizeof(ItemPointerData) * eo->maxcount);
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
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 *
86 {
87  BuildAccumulator *accum = (BuildAccumulator *) arg;
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  {
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
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),
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
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);
139  }
140  return res;
141 }
142 
143 /*
144  * Find/store one entry from indexed value.
145  */
146 static void
148  ItemPointer heapptr, OffsetNumber attnum,
149  Datum key, GinNullCategory category)
150 {
151  GinEntryAccumulator eatmp;
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 =
181  ea->list[0] = *heapptr;
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
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
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
257 {
258  rb_begin_iterate(accum->tree, LeftRightWalk, &accum->tree_walk);
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  */
268  OffsetNumber *attnum, Datum *key, GinNullCategory *category,
269  uint32 *n)
270 {
271  GinEntryAccumulator *entry;
273 
274  entry = (GinEntryAccumulator *) rb_iterate(&accum->tree_walk);
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),
290 
291  return list;
292 }
#define ItemPointerIsValid(pointer)
Definition: itemptr.h:59
GinEntryAccumulator * entryallocator
Definition: gin_private.h:409
RBNode * rb_insert(RBTree *rb, const RBNode *data, bool *isNew)
Definition: rbtree.c:399
int errhint(const char *fmt,...)
Definition: elog.c:987
static void ginCombineData(RBNode *existing, const RBNode *newdata, void *arg)
Definition: ginbulk.c:30
static void ginInsertBAEntry(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum, Datum key, GinNullCategory category)
Definition: ginbulk.c:147
RBTree * rb_create(Size node_size, rb_comparator comparator, rb_combiner combiner, rb_allocfunc allocfunc, rb_freefunc freefunc, void *arg)
Definition: rbtree.c:110
Form_pg_attribute * attrs
Definition: tupdesc.h:74
#define DEF_NENTRY
Definition: ginbulk.c:24
OffsetNumber attnum
Definition: gin_private.h:398
int ginCompareAttEntries(GinState *ginstate, OffsetNumber attnuma, Datum a, GinNullCategory categorya, OffsetNumber attnumb, Datum b, GinNullCategory categoryb)
Definition: ginutil.c:403
int errcode(int sqlerrcode)
Definition: elog.c:575
Size GetMemoryChunkSpace(void *pointer)
Definition: mcxt.c:390
RBNode * rb_iterate(RBTreeIterator *iter)
Definition: rbtree.c:886
GinNullCategory category
Definition: gin_private.h:397
signed int int32
Definition: c.h:256
uint16 OffsetNumber
Definition: off.h:24
static int cmpEntryAccumulator(const RBNode *a, const RBNode *b, void *arg)
Definition: ginbulk.c:72
#define ERROR
Definition: elog.h:43
signed char GinNullCategory
Definition: ginblock.h:197
#define FALSE
Definition: c.h:221
Definition: rbtree.h:23
static RBNode * ginAllocEntryAccumulator(void *arg)
Definition: ginbulk.c:85
#define GIN_CAT_NORM_KEY
Definition: ginblock.h:199
#define FirstOffsetNumber
Definition: off.h:27
FormData_pg_attribute * Form_pg_attribute
Definition: pg_attribute.h:187
unsigned int uint32
Definition: c.h:268
GinState * ginstate
Definition: gin_private.h:407
static Datum getDatumCopy(BuildAccumulator *accum, OffsetNumber attnum, Datum value)
Definition: ginbulk.c:128
#define ereport(elevel, rest)
Definition: elog.h:122
#define DEF_NPTR
Definition: ginbulk.c:25
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:128
uintptr_t Datum
Definition: postgres.h:372
void ginInsertBAEntries(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum, Datum *entries, GinNullCategory *categories, int32 nentries)
Definition: ginbulk.c:209
void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:855
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
ItemPointerData * ginGetBAEntry(BuildAccumulator *accum, OffsetNumber *attnum, Datum *key, GinNullCategory *category, uint32 *n)
Definition: ginbulk.c:267
static int qsortCompareItemPointers(const void *a, const void *b)
Definition: ginbulk.c:245
#define DatumGetPointer(X)
Definition: postgres.h:555
static int ginCompareItemPointers(ItemPointer a, ItemPointer b)
Definition: gin_private.h:461
void ginBeginBAScan(BuildAccumulator *accum)
Definition: ginbulk.c:256
tuple list
Definition: sort-test.py:11
void * repalloc_huge(void *pointer, Size size)
Definition: mcxt.c:1031
void * palloc(Size size)
Definition: mcxt.c:849
int errmsg(const char *fmt,...)
Definition: elog.c:797
int i
void * arg
TupleDesc origTupdesc
Definition: gin_private.h:67
#define TRUE
Definition: c.h:217
RBTreeIterator tree_walk
Definition: gin_private.h:412
static struct @121 value
#define qsort(a, b, c, d)
Definition: port.h:440
ItemPointerData * list
Definition: gin_private.h:400
void ginInitBA(BuildAccumulator *accum)
Definition: ginbulk.c:109