1 /*-------------------------------------------------------------------------
2 *
3 * gininsert.c
4 * insert routines for the postgres inverted index access method.
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/gininsert.c
12 *-------------------------------------------------------------------------
13 */
14
15 #include "postgres.h"
16
17 #include "access/gin_private.h"
18 #include "access/xloginsert.h"
19 #include "catalog/index.h"
20 #include "miscadmin.h"
21 #include "storage/bufmgr.h"
22 #include "storage/smgr.h"
23 #include "storage/indexfsm.h"
24 #include "utils/memutils.h"
25 #include "utils/rel.h"
26
27
28 typedef struct
29 {
30 GinState ginstate;
31 double indtuples;
32 GinStatsData buildStats;
33 MemoryContext tmpCtx;
34 MemoryContext funcCtx;
35 BuildAccumulator accum;
36 } GinBuildState;
37
38
39 /*
40 * Adds array of item pointers to tuple's posting list, or
41 * creates posting tree and tuple pointing to tree in case
42 * of not enough space. Max size of tuple is defined in
43 * GinFormTuple(). Returns a new, modified index tuple.
44 * items[] must be in sorted order with no duplicates.
45 */
46 static IndexTuple
addItemPointersToLeafTuple(GinState * ginstate,IndexTuple old,ItemPointerData * items,uint32 nitem,GinStatsData * buildStats)47 addItemPointersToLeafTuple(GinState *ginstate,
48 IndexTuple old,
49 ItemPointerData *items, uint32 nitem,
50 GinStatsData *buildStats)
51 {
52 OffsetNumber attnum;
53 Datum key;
54 GinNullCategory category;
55 IndexTuple res;
56 ItemPointerData *newItems,
57 *oldItems;
58 int oldNPosting,
59 newNPosting;
60 GinPostingList *compressedList;
61
62 Assert(!GinIsPostingTree(old));
63
64 attnum = gintuple_get_attrnum(ginstate, old);
65 key = gintuple_get_key(ginstate, old, &category);
66
67 /* merge the old and new posting lists */
68 oldItems = ginReadTuple(ginstate, attnum, old, &oldNPosting);
69
70 newItems = ginMergeItemPointers(items, nitem,
71 oldItems, oldNPosting,
72 &newNPosting);
73
74 /* Compress the posting list, and try to a build tuple with room for it */
75 res = NULL;
76 compressedList = ginCompressPostingList(newItems, newNPosting, GinMaxItemSize,
77 NULL);
78 pfree(newItems);
79 if (compressedList)
80 {
81 res = GinFormTuple(ginstate, attnum, key, category,
82 (char *) compressedList,
83 SizeOfGinPostingList(compressedList),
84 newNPosting,
85 false);
86 pfree(compressedList);
87 }
88 if (!res)
89 {
90 /* posting list would be too big, convert to posting tree */
91 BlockNumber postingRoot;
92
93 /*
94 * Initialize posting tree with the old tuple's posting list. It's
95 * surely small enough to fit on one posting-tree page, and should
96 * already be in order with no duplicates.
97 */
98 postingRoot = createPostingTree(ginstate->index,
99 oldItems,
100 oldNPosting,
101 buildStats);
102
103 /* Now insert the TIDs-to-be-added into the posting tree */
104 ginInsertItemPointers(ginstate->index, postingRoot,
105 items, nitem,
106 buildStats);
107
108 /* And build a new posting-tree-only result tuple */
109 res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, 0, true);
110 GinSetPostingTree(res, postingRoot);
111 }
112 pfree(oldItems);
113
114 return res;
115 }
116
117 /*
118 * Build a fresh leaf tuple, either posting-list or posting-tree format
119 * depending on whether the given items list will fit.
120 * items[] must be in sorted order with no duplicates.
121 *
122 * This is basically the same logic as in addItemPointersToLeafTuple,
123 * but working from slightly different input.
124 */
125 static IndexTuple
buildFreshLeafTuple(GinState * ginstate,OffsetNumber attnum,Datum key,GinNullCategory category,ItemPointerData * items,uint32 nitem,GinStatsData * buildStats)126 buildFreshLeafTuple(GinState *ginstate,
127 OffsetNumber attnum, Datum key, GinNullCategory category,
128 ItemPointerData *items, uint32 nitem,
129 GinStatsData *buildStats)
130 {
131 IndexTuple res = NULL;
132 GinPostingList *compressedList;
133
134 /* try to build a posting list tuple with all the items */
135 compressedList = ginCompressPostingList(items, nitem, GinMaxItemSize, NULL);
136 if (compressedList)
137 {
138 res = GinFormTuple(ginstate, attnum, key, category,
139 (char *) compressedList,
140 SizeOfGinPostingList(compressedList),
141 nitem, false);
142 pfree(compressedList);
143 }
144 if (!res)
145 {
146 /* posting list would be too big, build posting tree */
147 BlockNumber postingRoot;
148
149 /*
150 * Build posting-tree-only result tuple. We do this first so as to
151 * fail quickly if the key is too big.
152 */
153 res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, 0, true);
154
155 /*
156 * Initialize a new posting tree with the TIDs.
157 */
158 postingRoot = createPostingTree(ginstate->index, items, nitem,
159 buildStats);
160
161 /* And save the root link in the result tuple */
162 GinSetPostingTree(res, postingRoot);
163 }
164
165 return res;
166 }
167
168 /*
169 * Insert one or more heap TIDs associated with the given key value.
170 * This will either add a single key entry, or enlarge a pre-existing entry.
171 *
172 * During an index build, buildStats is non-null and the counters
173 * it contains should be incremented as needed.
174 */
175 void
ginEntryInsert(GinState * ginstate,OffsetNumber attnum,Datum key,GinNullCategory category,ItemPointerData * items,uint32 nitem,GinStatsData * buildStats)176 ginEntryInsert(GinState *ginstate,
177 OffsetNumber attnum, Datum key, GinNullCategory category,
178 ItemPointerData *items, uint32 nitem,
179 GinStatsData *buildStats)
180 {
181 GinBtreeData btree;
182 GinBtreeEntryInsertData insertdata;
183 GinBtreeStack *stack;
184 IndexTuple itup;
185 Page page;
186
187 insertdata.isDelete = FALSE;
188
189 /* During index build, count the to-be-inserted entry */
190 if (buildStats)
191 buildStats->nEntries++;
192
193 ginPrepareEntryScan(&btree, attnum, key, category, ginstate);
194
195 stack = ginFindLeafPage(&btree, false, NULL);
196 page = BufferGetPage(stack->buffer);
197
198 if (btree.findItem(&btree, stack))
199 {
200 /* found pre-existing entry */
201 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
202
203 if (GinIsPostingTree(itup))
204 {
205 /* add entries to existing posting tree */
206 BlockNumber rootPostingTree = GinGetPostingTree(itup);
207
208 /* release all stack */
209 LockBuffer(stack->buffer, GIN_UNLOCK);
210 freeGinBtreeStack(stack);
211
212 /* insert into posting tree */
213 ginInsertItemPointers(ginstate->index, rootPostingTree,
214 items, nitem,
215 buildStats);
216 return;
217 }
218
219 /* modify an existing leaf entry */
220 itup = addItemPointersToLeafTuple(ginstate, itup,
221 items, nitem, buildStats);
222
223 insertdata.isDelete = TRUE;
224 }
225 else
226 {
227 /* no match, so construct a new leaf entry */
228 itup = buildFreshLeafTuple(ginstate, attnum, key, category,
229 items, nitem, buildStats);
230 }
231
232 /* Insert the new or modified leaf tuple */
233 insertdata.entry = itup;
234 ginInsertValue(&btree, stack, &insertdata, buildStats);
235 pfree(itup);
236 }
237
238 /*
239 * Extract index entries for a single indexable item, and add them to the
240 * BuildAccumulator's state.
241 *
242 * This function is used only during initial index creation.
243 */
244 static void
ginHeapTupleBulkInsert(GinBuildState * buildstate,OffsetNumber attnum,Datum value,bool isNull,ItemPointer heapptr)245 ginHeapTupleBulkInsert(GinBuildState *buildstate, OffsetNumber attnum,
246 Datum value, bool isNull,
247 ItemPointer heapptr)
248 {
249 Datum *entries;
250 GinNullCategory *categories;
251 int32 nentries;
252 MemoryContext oldCtx;
253
254 oldCtx = MemoryContextSwitchTo(buildstate->funcCtx);
255 entries = ginExtractEntries(buildstate->accum.ginstate, attnum,
256 value, isNull,
257 &nentries, &categories);
258 MemoryContextSwitchTo(oldCtx);
259
260 ginInsertBAEntries(&buildstate->accum, heapptr, attnum,
261 entries, categories, nentries);
262
263 buildstate->indtuples += nentries;
264
265 MemoryContextReset(buildstate->funcCtx);
266 }
267
268 static void
ginBuildCallback(Relation index,HeapTuple htup,Datum * values,bool * isnull,bool tupleIsAlive,void * state)269 ginBuildCallback(Relation index, HeapTuple htup, Datum *values,
270 bool *isnull, bool tupleIsAlive, void *state)
271 {
272 GinBuildState *buildstate = (GinBuildState *) state;
273 MemoryContext oldCtx;
274 int i;
275
276 oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);
277
278 for (i = 0; i < buildstate->ginstate.origTupdesc->natts; i++)
279 ginHeapTupleBulkInsert(buildstate, (OffsetNumber) (i + 1),
280 values[i], isnull[i],
281 &htup->t_self);
282
283 /* If we've maxed out our available memory, dump everything to the index */
284 if (buildstate->accum.allocatedMemory >= (Size) maintenance_work_mem * 1024L)
285 {
286 ItemPointerData *list;
287 Datum key;
288 GinNullCategory category;
289 uint32 nlist;
290 OffsetNumber attnum;
291
292 ginBeginBAScan(&buildstate->accum);
293 while ((list = ginGetBAEntry(&buildstate->accum,
294 &attnum, &key, &category, &nlist)) != NULL)
295 {
296 /* there could be many entries, so be willing to abort here */
297 CHECK_FOR_INTERRUPTS();
298 ginEntryInsert(&buildstate->ginstate, attnum, key, category,
299 list, nlist, &buildstate->buildStats);
300 }
301
302 MemoryContextReset(buildstate->tmpCtx);
303 ginInitBA(&buildstate->accum);
304 }
305
306 MemoryContextSwitchTo(oldCtx);
307 }
308
309 IndexBuildResult *
ginbuild(Relation heap,Relation index,IndexInfo * indexInfo)310 ginbuild(Relation heap, Relation index, IndexInfo *indexInfo)
311 {
312 IndexBuildResult *result;
313 double reltuples;
314 GinBuildState buildstate;
315 Buffer RootBuffer,
316 MetaBuffer;
317 ItemPointerData *list;
318 Datum key;
319 GinNullCategory category;
320 uint32 nlist;
321 MemoryContext oldCtx;
322 OffsetNumber attnum;
323
324 if (RelationGetNumberOfBlocks(index) != 0)
325 elog(ERROR, "index \"%s\" already contains data",
326 RelationGetRelationName(index));
327
328 initGinState(&buildstate.ginstate, index);
329 buildstate.indtuples = 0;
330 memset(&buildstate.buildStats, 0, sizeof(GinStatsData));
331
332 /* initialize the meta page */
333 MetaBuffer = GinNewBuffer(index);
334
335 /* initialize the root page */
336 RootBuffer = GinNewBuffer(index);
337
338 START_CRIT_SECTION();
339 GinInitMetabuffer(MetaBuffer);
340 MarkBufferDirty(MetaBuffer);
341 GinInitBuffer(RootBuffer, GIN_LEAF);
342 MarkBufferDirty(RootBuffer);
343
344 if (RelationNeedsWAL(index))
345 {
346 XLogRecPtr recptr;
347 Page page;
348
349 XLogBeginInsert();
350 XLogRegisterBuffer(0, MetaBuffer, REGBUF_WILL_INIT);
351 XLogRegisterBuffer(1, RootBuffer, REGBUF_WILL_INIT);
352
353 recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_CREATE_INDEX);
354
355 page = BufferGetPage(RootBuffer);
356 PageSetLSN(page, recptr);
357
358 page = BufferGetPage(MetaBuffer);
359 PageSetLSN(page, recptr);
360 }
361
362 UnlockReleaseBuffer(MetaBuffer);
363 UnlockReleaseBuffer(RootBuffer);
364 END_CRIT_SECTION();
365
366 /* count the root as first entry page */
367 buildstate.buildStats.nEntryPages++;
368
369 /*
370 * create a temporary memory context that is used to hold data not yet
371 * dumped out to the index
372 */
373 buildstate.tmpCtx = AllocSetContextCreate(CurrentMemoryContext,
374 "Gin build temporary context",
375 ALLOCSET_DEFAULT_SIZES);
376
377 /*
378 * create a temporary memory context that is used for calling
379 * ginExtractEntries(), and can be reset after each tuple
380 */
381 buildstate.funcCtx = AllocSetContextCreate(CurrentMemoryContext,
382 "Gin build temporary context for user-defined function",
383 ALLOCSET_DEFAULT_SIZES);
384
385 buildstate.accum.ginstate = &buildstate.ginstate;
386 ginInitBA(&buildstate.accum);
387
388 /*
389 * Do the heap scan. We disallow sync scan here because dataPlaceToPage
390 * prefers to receive tuples in TID order.
391 */
392 reltuples = IndexBuildHeapScan(heap, index, indexInfo, false,
393 ginBuildCallback, (void *) &buildstate);
394
395 /* dump remaining entries to the index */
396 oldCtx = MemoryContextSwitchTo(buildstate.tmpCtx);
397 ginBeginBAScan(&buildstate.accum);
398 while ((list = ginGetBAEntry(&buildstate.accum,
399 &attnum, &key, &category, &nlist)) != NULL)
400 {
401 /* there could be many entries, so be willing to abort here */
402 CHECK_FOR_INTERRUPTS();
403 ginEntryInsert(&buildstate.ginstate, attnum, key, category,
404 list, nlist, &buildstate.buildStats);
405 }
406 MemoryContextSwitchTo(oldCtx);
407
408 MemoryContextDelete(buildstate.funcCtx);
409 MemoryContextDelete(buildstate.tmpCtx);
410
411 /*
412 * Update metapage stats
413 */
414 buildstate.buildStats.nTotalPages = RelationGetNumberOfBlocks(index);
415 ginUpdateStats(index, &buildstate.buildStats);
416
417 /*
418 * Return statistics
419 */
420 result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
421
422 result->heap_tuples = reltuples;
423 result->index_tuples = buildstate.indtuples;
424
425 return result;
426 }
427
428 /*
429 * ginbuildempty() -- build an empty gin index in the initialization fork
430 */
431 void
ginbuildempty(Relation index)432 ginbuildempty(Relation index)
433 {
434 Buffer RootBuffer,
435 MetaBuffer;
436
437 /* An empty GIN index has two pages. */
438 MetaBuffer =
439 ReadBufferExtended(index, INIT_FORKNUM, P_NEW, RBM_NORMAL, NULL);
440 LockBuffer(MetaBuffer, BUFFER_LOCK_EXCLUSIVE);
441 RootBuffer =
442 ReadBufferExtended(index, INIT_FORKNUM, P_NEW, RBM_NORMAL, NULL);
443 LockBuffer(RootBuffer, BUFFER_LOCK_EXCLUSIVE);
444
445 /* Initialize and xlog metabuffer and root buffer. */
446 START_CRIT_SECTION();
447 GinInitMetabuffer(MetaBuffer);
448 MarkBufferDirty(MetaBuffer);
449 log_newpage_buffer(MetaBuffer, false);
450 GinInitBuffer(RootBuffer, GIN_LEAF);
451 MarkBufferDirty(RootBuffer);
452 log_newpage_buffer(RootBuffer, false);
453 END_CRIT_SECTION();
454
455 /* Unlock and release the buffers. */
456 UnlockReleaseBuffer(MetaBuffer);
457 UnlockReleaseBuffer(RootBuffer);
458 }
459
460 /*
461 * Insert index entries for a single indexable item during "normal"
462 * (non-fast-update) insertion
463 */
464 static void
ginHeapTupleInsert(GinState * ginstate,OffsetNumber attnum,Datum value,bool isNull,ItemPointer item)465 ginHeapTupleInsert(GinState *ginstate, OffsetNumber attnum,
466 Datum value, bool isNull,
467 ItemPointer item)
468 {
469 Datum *entries;
470 GinNullCategory *categories;
471 int32 i,
472 nentries;
473
474 entries = ginExtractEntries(ginstate, attnum, value, isNull,
475 &nentries, &categories);
476
477 for (i = 0; i < nentries; i++)
478 ginEntryInsert(ginstate, attnum, entries[i], categories[i],
479 item, 1, NULL);
480 }
481
482 bool
gininsert(Relation index,Datum * values,bool * isnull,ItemPointer ht_ctid,Relation heapRel,IndexUniqueCheck checkUnique)483 gininsert(Relation index, Datum *values, bool *isnull,
484 ItemPointer ht_ctid, Relation heapRel,
485 IndexUniqueCheck checkUnique)
486 {
487 GinState ginstate;
488 MemoryContext oldCtx;
489 MemoryContext insertCtx;
490 int i;
491
492 insertCtx = AllocSetContextCreate(CurrentMemoryContext,
493 "Gin insert temporary context",
494 ALLOCSET_DEFAULT_SIZES);
495
496 oldCtx = MemoryContextSwitchTo(insertCtx);
497
498 initGinState(&ginstate, index);
499
500 if (GinGetUseFastUpdate(index))
501 {
502 GinTupleCollector collector;
503
504 memset(&collector, 0, sizeof(GinTupleCollector));
505
506 for (i = 0; i < ginstate.origTupdesc->natts; i++)
507 ginHeapTupleFastCollect(&ginstate, &collector,
508 (OffsetNumber) (i + 1),
509 values[i], isnull[i],
510 ht_ctid);
511
512 ginHeapTupleFastInsert(&ginstate, &collector);
513 }
514 else
515 {
516 for (i = 0; i < ginstate.origTupdesc->natts; i++)
517 ginHeapTupleInsert(&ginstate, (OffsetNumber) (i + 1),
518 values[i], isnull[i],
519 ht_ctid);
520 }
521
522 MemoryContextSwitchTo(oldCtx);
523 MemoryContextDelete(insertCtx);
524
525 return false;
526 }
527