1 /*-------------------------------------------------------------------------
2 *
3 * gininsert.c
4 * insert routines for the postgres inverted index access method.
5 *
6 *
7 * Portions Copyright (c) 1996-2020, 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/tableam.h"
20 #include "access/xloginsert.h"
21 #include "catalog/index.h"
22 #include "miscadmin.h"
23 #include "storage/bufmgr.h"
24 #include "storage/indexfsm.h"
25 #include "storage/predicate.h"
26 #include "storage/smgr.h"
27 #include "utils/memutils.h"
28 #include "utils/rel.h"
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 ginPrepareEntryScan(&btree, attnum, key, category, ginstate);
193 btree.isBuild = (buildStats != NULL);
194
195 stack = ginFindLeafPage(&btree, false, 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 CheckForSerializableConflictIn(ginstate->index, NULL,
220 BufferGetBlockNumber(stack->buffer));
221 /* modify an existing leaf entry */
222 itup = addItemPointersToLeafTuple(ginstate, itup,
223 items, nitem, buildStats, stack->buffer);
224
225 insertdata.isDelete = true;
226 }
227 else
228 {
229 CheckForSerializableConflictIn(ginstate->index, NULL,
230 BufferGetBlockNumber(stack->buffer));
231 /* no match, so construct a new leaf entry */
232 itup = buildFreshLeafTuple(ginstate, attnum, key, category,
233 items, nitem, buildStats, stack->buffer);
234
235 /*
236 * nEntries counts leaf tuples, so increment it only when we make a
237 * new one.
238 */
239 if (buildStats)
240 buildStats->nEntries++;
241 }
242
243 /* Insert the new or modified leaf tuple */
244 insertdata.entry = itup;
245 ginInsertValue(&btree, stack, &insertdata, buildStats);
246 pfree(itup);
247 }
248
249 /*
250 * Extract index entries for a single indexable item, and add them to the
251 * BuildAccumulator's state.
252 *
253 * This function is used only during initial index creation.
254 */
255 static void
ginHeapTupleBulkInsert(GinBuildState * buildstate,OffsetNumber attnum,Datum value,bool isNull,ItemPointer heapptr)256 ginHeapTupleBulkInsert(GinBuildState *buildstate, OffsetNumber attnum,
257 Datum value, bool isNull,
258 ItemPointer heapptr)
259 {
260 Datum *entries;
261 GinNullCategory *categories;
262 int32 nentries;
263 MemoryContext oldCtx;
264
265 oldCtx = MemoryContextSwitchTo(buildstate->funcCtx);
266 entries = ginExtractEntries(buildstate->accum.ginstate, attnum,
267 value, isNull,
268 &nentries, &categories);
269 MemoryContextSwitchTo(oldCtx);
270
271 ginInsertBAEntries(&buildstate->accum, heapptr, attnum,
272 entries, categories, nentries);
273
274 buildstate->indtuples += nentries;
275
276 MemoryContextReset(buildstate->funcCtx);
277 }
278
279 static void
ginBuildCallback(Relation index,ItemPointer tid,Datum * values,bool * isnull,bool tupleIsAlive,void * state)280 ginBuildCallback(Relation index, ItemPointer tid, Datum *values,
281 bool *isnull, bool tupleIsAlive, void *state)
282 {
283 GinBuildState *buildstate = (GinBuildState *) state;
284 MemoryContext oldCtx;
285 int i;
286
287 oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);
288
289 for (i = 0; i < buildstate->ginstate.origTupdesc->natts; i++)
290 ginHeapTupleBulkInsert(buildstate, (OffsetNumber) (i + 1),
291 values[i], isnull[i], tid);
292
293 /* If we've maxed out our available memory, dump everything to the index */
294 if (buildstate->accum.allocatedMemory >= (Size) maintenance_work_mem * 1024L)
295 {
296 ItemPointerData *list;
297 Datum key;
298 GinNullCategory category;
299 uint32 nlist;
300 OffsetNumber attnum;
301
302 ginBeginBAScan(&buildstate->accum);
303 while ((list = ginGetBAEntry(&buildstate->accum,
304 &attnum, &key, &category, &nlist)) != NULL)
305 {
306 /* there could be many entries, so be willing to abort here */
307 CHECK_FOR_INTERRUPTS();
308 ginEntryInsert(&buildstate->ginstate, attnum, key, category,
309 list, nlist, &buildstate->buildStats);
310 }
311
312 MemoryContextReset(buildstate->tmpCtx);
313 ginInitBA(&buildstate->accum);
314 }
315
316 MemoryContextSwitchTo(oldCtx);
317 }
318
319 IndexBuildResult *
ginbuild(Relation heap,Relation index,IndexInfo * indexInfo)320 ginbuild(Relation heap, Relation index, IndexInfo *indexInfo)
321 {
322 IndexBuildResult *result;
323 double reltuples;
324 GinBuildState buildstate;
325 Buffer RootBuffer,
326 MetaBuffer;
327 ItemPointerData *list;
328 Datum key;
329 GinNullCategory category;
330 uint32 nlist;
331 MemoryContext oldCtx;
332 OffsetNumber attnum;
333
334 if (RelationGetNumberOfBlocks(index) != 0)
335 elog(ERROR, "index \"%s\" already contains data",
336 RelationGetRelationName(index));
337
338 initGinState(&buildstate.ginstate, index);
339 buildstate.indtuples = 0;
340 memset(&buildstate.buildStats, 0, sizeof(GinStatsData));
341
342 /* initialize the meta page */
343 MetaBuffer = GinNewBuffer(index);
344
345 /* initialize the root page */
346 RootBuffer = GinNewBuffer(index);
347
348 START_CRIT_SECTION();
349 GinInitMetabuffer(MetaBuffer);
350 MarkBufferDirty(MetaBuffer);
351 GinInitBuffer(RootBuffer, GIN_LEAF);
352 MarkBufferDirty(RootBuffer);
353
354
355 UnlockReleaseBuffer(MetaBuffer);
356 UnlockReleaseBuffer(RootBuffer);
357 END_CRIT_SECTION();
358
359 /* count the root as first entry page */
360 buildstate.buildStats.nEntryPages++;
361
362 /*
363 * create a temporary memory context that is used to hold data not yet
364 * dumped out to the index
365 */
366 buildstate.tmpCtx = AllocSetContextCreate(CurrentMemoryContext,
367 "Gin build temporary context",
368 ALLOCSET_DEFAULT_SIZES);
369
370 /*
371 * create a temporary memory context that is used for calling
372 * ginExtractEntries(), and can be reset after each tuple
373 */
374 buildstate.funcCtx = AllocSetContextCreate(CurrentMemoryContext,
375 "Gin build temporary context for user-defined function",
376 ALLOCSET_DEFAULT_SIZES);
377
378 buildstate.accum.ginstate = &buildstate.ginstate;
379 ginInitBA(&buildstate.accum);
380
381 /*
382 * Do the heap scan. We disallow sync scan here because dataPlaceToPage
383 * prefers to receive tuples in TID order.
384 */
385 reltuples = table_index_build_scan(heap, index, indexInfo, false, true,
386 ginBuildCallback, (void *) &buildstate,
387 NULL);
388
389 /* dump remaining entries to the index */
390 oldCtx = MemoryContextSwitchTo(buildstate.tmpCtx);
391 ginBeginBAScan(&buildstate.accum);
392 while ((list = ginGetBAEntry(&buildstate.accum,
393 &attnum, &key, &category, &nlist)) != NULL)
394 {
395 /* there could be many entries, so be willing to abort here */
396 CHECK_FOR_INTERRUPTS();
397 ginEntryInsert(&buildstate.ginstate, attnum, key, category,
398 list, nlist, &buildstate.buildStats);
399 }
400 MemoryContextSwitchTo(oldCtx);
401
402 MemoryContextDelete(buildstate.funcCtx);
403 MemoryContextDelete(buildstate.tmpCtx);
404
405 /*
406 * Update metapage stats
407 */
408 buildstate.buildStats.nTotalPages = RelationGetNumberOfBlocks(index);
409 ginUpdateStats(index, &buildstate.buildStats, true);
410
411 /*
412 * We didn't write WAL records as we built the index, so if WAL-logging is
413 * required, write all pages to the WAL now.
414 */
415 if (RelationNeedsWAL(index))
416 {
417 log_newpage_range(index, MAIN_FORKNUM,
418 0, RelationGetNumberOfBlocks(index),
419 true);
420 }
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