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