Debian Codegraph @

src/backend/access/gin/gininsert.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * gininsert.c
4 * insert routines for the postgres inverted index access method.
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/gininsert.c
12 *-------------------------------------------------------------------------
13 */
14
15 #include "postgres.h"
16
17 #include "access/gin_private.h"
18 #include "access/gin_tuple.h"
19 #include "access/parallel.h"
20 #include "access/table.h"
21 #include "access/tableam.h"
22 #include "access/xloginsert.h"
23 #include "catalog/index.h"
24 #include "catalog/pg_collation.h"
25 #include "commands/progress.h"
26 #include "miscadmin.h"
27 #include "nodes/execnodes.h"
28 #include "pgstat.h"
29 #include "storage/bufmgr.h"
30 #include "storage/predicate.h"
31 #include "tcop/tcopprot.h"
32 #include "utils/datum.h"
33 #include "utils/memutils.h"
34 #include "utils/rel.h"
35 #include "utils/builtins.h"
36
37
38 /* Magic numbers for parallel state sharing */
39 #define PARALLEL_KEY_GIN_SHARED UINT64CONST(0xB000000000000001)
40 #define PARALLEL_KEY_TUPLESORT UINT64CONST(0xB000000000000002)
41 #define PARALLEL_KEY_QUERY_TEXT UINT64CONST(0xB000000000000003)
42 #define PARALLEL_KEY_WAL_USAGE UINT64CONST(0xB000000000000004)
43 #define PARALLEL_KEY_BUFFER_USAGE UINT64CONST(0xB000000000000005)
44
45 /*
46 * Status for index builds performed in parallel. This is allocated in a
47 * dynamic shared memory segment.
48 */
49 typedef struct GinBuildShared
50 {
51 /*
52 * These fields are not modified during the build. They primarily exist
53 * for the benefit of worker processes that need to create state
54 * corresponding to that used by the leader.
55 */
56 Oid heaprelid;
57 Oid indexrelid;
58 bool isconcurrent;
59 int scantuplesortstates;
60
61 /*
62 * workersdonecv is used to monitor the progress of workers. All parallel
63 * participants must indicate that they are done before leader can use
64 * results built by the workers (and before leader can write the data into
65 * the index).
66 */
67 ConditionVariable workersdonecv;
68
69 /*
70 * mutex protects all following fields
71 *
72 * These fields contain status information of interest to GIN index builds
73 * that must work just the same when an index is built in parallel.
74 */
75 slock_t mutex;
76
77 /*
78 * Mutable state that is maintained by workers, and reported back to
79 * leader at end of the scans.
80 *
81 * nparticipantsdone is number of worker processes finished.
82 *
83 * reltuples is the total number of input heap tuples.
84 *
85 * indtuples is the total number of tuples that made it into the index.
86 */
87 int nparticipantsdone;
88 double reltuples;
89 double indtuples;
90
91 /*
92 * ParallelTableScanDescData data follows. Can't directly embed here, as
93 * implementations of the parallel table scan desc interface might need
94 * stronger alignment.
95 */
96 } GinBuildShared;
97
98 /*
99 * Return pointer to a GinBuildShared's parallel table scan.
100 *
101 * c.f. shm_toc_allocate as to why BUFFERALIGN is used, rather than just
102 * MAXALIGN.
103 */
104 #define ParallelTableScanFromGinBuildShared(shared) \
105 (ParallelTableScanDesc) ((char *) (shared) + BUFFERALIGN(sizeof(GinBuildShared)))
106
107 /*
108 * Status for leader in parallel index build.
109 */
110 typedef struct GinLeader
111 {
112 /* parallel context itself */
113 ParallelContext *pcxt;
114
115 /*
116 * nparticipanttuplesorts is the exact number of worker processes
117 * successfully launched, plus one leader process if it participates as a
118 * worker (only DISABLE_LEADER_PARTICIPATION builds avoid leader
119 * participating as a worker).
120 */
121 int nparticipanttuplesorts;
122
123 /*
124 * Leader process convenience pointers to shared state (leader avoids TOC
125 * lookups).
126 *
127 * GinBuildShared is the shared state for entire build. sharedsort is the
128 * shared, tuplesort-managed state passed to each process tuplesort.
129 * snapshot is the snapshot used by the scan iff an MVCC snapshot is
130 * required.
131 */
132 GinBuildShared *ginshared;
133 Sharedsort *sharedsort;
134 Snapshot snapshot;
135 WalUsage *walusage;
136 BufferUsage *bufferusage;
137 } GinLeader;
138
139 typedef struct
140 {
141 GinState ginstate;
142 double indtuples;
143 GinStatsData buildStats;
144 MemoryContext tmpCtx;
145 MemoryContext funcCtx;
146 BuildAccumulator accum;
147 ItemPointerData tid;
148 int work_mem;
149
150 /*
151 * bs_leader is only present when a parallel index build is performed, and
152 * only in the leader process.
153 */
154 GinLeader *bs_leader;
155
156 /* number of participating workers (including leader) */
157 int bs_num_workers;
158
159 /* used to pass information from workers to leader */
160 double bs_numtuples;
161 double bs_reltuples;
162
163 /*
164 * The sortstate is used by workers (including the leader). It has to be
165 * part of the build state, because that's the only thing passed to the
166 * build callback etc.
167 */
168 Tuplesortstate *bs_sortstate;
169
170 /*
171 * The sortstate used only within a single worker for the first merge pass
172 * happening there. In principle it doesn't need to be part of the build
173 * state and we could pass it around directly, but it's more convenient
174 * this way. And it's part of the build state, after all.
175 */
176 Tuplesortstate *bs_worker_sort;
177 } GinBuildState;
178
179
180 /* parallel index builds */
181 static void _gin_begin_parallel(GinBuildState *buildstate, Relation heap, Relation index,
182 bool isconcurrent, int request);
183 static void _gin_end_parallel(GinLeader *ginleader, GinBuildState *state);
184 static Size _gin_parallel_estimate_shared(Relation heap, Snapshot snapshot);
185 static double _gin_parallel_heapscan(GinBuildState *state);
186 static double _gin_parallel_merge(GinBuildState *state);
187 static void _gin_leader_participate_as_worker(GinBuildState *buildstate,
188 Relation heap, Relation index);
189 static void _gin_parallel_scan_and_build(GinBuildState *state,
190 GinBuildShared *ginshared,
191 Sharedsort *sharedsort,
192 Relation heap, Relation index,
193 int sortmem, bool progress);
194
195 static ItemPointer _gin_parse_tuple_items(GinTuple *a);
196 static Datum _gin_parse_tuple_key(GinTuple *a);
197
198 static GinTuple *_gin_build_tuple(OffsetNumber attrnum, unsigned char category,
199 Datum key, int16 typlen, bool typbyval,
200 ItemPointerData *items, uint32 nitems,
201 Size *len);
202
203 /*
204 * Adds array of item pointers to tuple's posting list, or
205 * creates posting tree and tuple pointing to tree in case
206 * of not enough space. Max size of tuple is defined in
207 * GinFormTuple(). Returns a new, modified index tuple.
208 * items[] must be in sorted order with no duplicates.
209 */
210 static IndexTuple
211 addItemPointersToLeafTuple(GinState *ginstate,
212 IndexTuple old,
213 ItemPointerData *items, uint32 nitem,
214 GinStatsData *buildStats, Buffer buffer)
215 {
216 OffsetNumber attnum;
217 Datum key;
218 GinNullCategory category;
219 IndexTuple res;
220 ItemPointerData *newItems,
221 *oldItems;
222 int oldNPosting,
223 newNPosting;
224 GinPostingList *compressedList;
225
226 Assert(!GinIsPostingTree(old));
227
228 attnum = gintuple_get_attrnum(ginstate, old);
229 key = gintuple_get_key(ginstate, old, &category);
230
231 /* merge the old and new posting lists */
232 oldItems = ginReadTuple(ginstate, attnum, old, &oldNPosting);
233
234 newItems = ginMergeItemPointers(items, nitem,
235 oldItems, oldNPosting,
236 &newNPosting);
237
238 /* Compress the posting list, and try to a build tuple with room for it */
239 res = NULL;
240 compressedList = ginCompressPostingList(newItems, newNPosting, GinMaxItemSize,
241 NULL);
242 pfree(newItems);
243 if (compressedList)
244 {
245 res = GinFormTuple(ginstate, attnum, key, category,
246 (char *) compressedList,
247 SizeOfGinPostingList(compressedList),
248 newNPosting,
249 false);
250 pfree(compressedList);
251 }
252 if (!res)
253 {
254 /* posting list would be too big, convert to posting tree */
255 BlockNumber postingRoot;
256
257 /*
258 * Initialize posting tree with the old tuple's posting list. It's
259 * surely small enough to fit on one posting-tree page, and should
260 * already be in order with no duplicates.
261 */
262 postingRoot = createPostingTree(ginstate->index,
263 oldItems,
264 oldNPosting,
265 buildStats,
266 buffer);
267
268 /* Now insert the TIDs-to-be-added into the posting tree */
269 ginInsertItemPointers(ginstate->index, postingRoot,
270 items, nitem,
271 buildStats);
272
273 /* And build a new posting-tree-only result tuple */
274 res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, 0, true);
275 GinSetPostingTree(res, postingRoot);
276 }
277 pfree(oldItems);
278
279 return res;
280 }
281
282 /*
283 * Build a fresh leaf tuple, either posting-list or posting-tree format
284 * depending on whether the given items list will fit.
285 * items[] must be in sorted order with no duplicates.
286 *
287 * This is basically the same logic as in addItemPointersToLeafTuple,
288 * but working from slightly different input.
289 */
290 static IndexTuple
291 buildFreshLeafTuple(GinState *ginstate,
292 OffsetNumber attnum, Datum key, GinNullCategory category,
293 ItemPointerData *items, uint32 nitem,
294 GinStatsData *buildStats, Buffer buffer)
295 {
296 IndexTuple res = NULL;
297 GinPostingList *compressedList;
298
299 /* try to build a posting list tuple with all the items */
300 compressedList = ginCompressPostingList(items, nitem, GinMaxItemSize, NULL);
301 if (compressedList)
302 {
303 res = GinFormTuple(ginstate, attnum, key, category,
304 (char *) compressedList,
305 SizeOfGinPostingList(compressedList),
306 nitem, false);
307 pfree(compressedList);
308 }
309 if (!res)
310 {
311 /* posting list would be too big, build posting tree */
312 BlockNumber postingRoot;
313
314 /*
315 * Build posting-tree-only result tuple. We do this first so as to
316 * fail quickly if the key is too big.
317 */
318 res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, 0, true);
319
320 /*
321 * Initialize a new posting tree with the TIDs.
322 */
323 postingRoot = createPostingTree(ginstate->index, items, nitem,
324 buildStats, buffer);
325
326 /* And save the root link in the result tuple */
327 GinSetPostingTree(res, postingRoot);
328 }
329
330 return res;
331 }
332
333 /*
334 * Insert one or more heap TIDs associated with the given key value.
335 * This will either add a single key entry, or enlarge a pre-existing entry.
336 *
337 * During an index build, buildStats is non-null and the counters
338 * it contains should be incremented as needed.
339 */
340 void
341 ginEntryInsert(GinState *ginstate,
342 OffsetNumber attnum, Datum key, GinNullCategory category,
343 ItemPointerData *items, uint32 nitem,
344 GinStatsData *buildStats)
345 {
346 GinBtreeData btree;
347 GinBtreeEntryInsertData insertdata;
348 GinBtreeStack *stack;
349 IndexTuple itup;
350 Page page;
351
352 insertdata.isDelete = false;
353
354 ginPrepareEntryScan(&btree, attnum, key, category, ginstate);
355 btree.isBuild = (buildStats != NULL);
356
357 stack = ginFindLeafPage(&btree, false, false);
358 page = BufferGetPage(stack->buffer);
359
360 if (btree.findItem(&btree, stack))
361 {
362 /* found pre-existing entry */
363 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
364
365 if (GinIsPostingTree(itup))
366 {
367 /* add entries to existing posting tree */
368 BlockNumber rootPostingTree = GinGetPostingTree(itup);
369
370 /* release all stack */
371 LockBuffer(stack->buffer, GIN_UNLOCK);
372 freeGinBtreeStack(stack);
373
374 /* insert into posting tree */
375 ginInsertItemPointers(ginstate->index, rootPostingTree,
376 items, nitem,
377 buildStats);
378 return;
379 }
380
381 CheckForSerializableConflictIn(ginstate->index, NULL,
382 BufferGetBlockNumber(stack->buffer));
383 /* modify an existing leaf entry */
384 itup = addItemPointersToLeafTuple(ginstate, itup,
385 items, nitem, buildStats, stack->buffer);
386
387 insertdata.isDelete = true;
388 }
389 else
390 {
391 CheckForSerializableConflictIn(ginstate->index, NULL,
392 BufferGetBlockNumber(stack->buffer));
393 /* no match, so construct a new leaf entry */
394 itup = buildFreshLeafTuple(ginstate, attnum, key, category,
395 items, nitem, buildStats, stack->buffer);
396
397 /*
398 * nEntries counts leaf tuples, so increment it only when we make a
399 * new one.
400 */
401 if (buildStats)
402 buildStats->nEntries++;
403 }
404
405 /* Insert the new or modified leaf tuple */
406 insertdata.entry = itup;
407 ginInsertValue(&btree, stack, &insertdata, buildStats);
408 pfree(itup);
409 }
410
411 /*
412 * Extract index entries for a single indexable item, and add them to the
413 * BuildAccumulator's state.
414 *
415 * This function is used only during initial index creation.
416 */
417 static void
418 ginHeapTupleBulkInsert(GinBuildState *buildstate, OffsetNumber attnum,
419 Datum value, bool isNull,
420 ItemPointer heapptr)
421 {
422 Datum *entries;
423 GinNullCategory *categories;
424 int32 nentries;
425 MemoryContext oldCtx;
426
427 oldCtx = MemoryContextSwitchTo(buildstate->funcCtx);
428 entries = ginExtractEntries(buildstate->accum.ginstate, attnum,
429 value, isNull,
430 &nentries, &categories);
431 MemoryContextSwitchTo(oldCtx);
432
433 ginInsertBAEntries(&buildstate->accum, heapptr, attnum,
434 entries, categories, nentries);
435
436 buildstate->indtuples += nentries;
437
438 MemoryContextReset(buildstate->funcCtx);
439 }
440
441 static void
442 ginBuildCallback(Relation index, ItemPointer tid, Datum *values,
443 bool *isnull, bool tupleIsAlive, void *state)
444 {
445 GinBuildState *buildstate = (GinBuildState *) state;
446 MemoryContext oldCtx;
447 int i;
448
449 oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);
450
451 for (i = 0; i < buildstate->ginstate.origTupdesc->natts; i++)
452 ginHeapTupleBulkInsert(buildstate, (OffsetNumber) (i + 1),
453 values[i], isnull[i], tid);
454
455 /* If we've maxed out our available memory, dump everything to the index */
456 if (buildstate->accum.allocatedMemory >= maintenance_work_mem * (Size) 1024)
457 {
458 ItemPointerData *list;
459 Datum key;
460 GinNullCategory category;
461 uint32 nlist;
462 OffsetNumber attnum;
463
464 ginBeginBAScan(&buildstate->accum);
465 while ((list = ginGetBAEntry(&buildstate->accum,
466 &attnum, &key, &category, &nlist)) != NULL)
467 {
468 /* there could be many entries, so be willing to abort here */
469 CHECK_FOR_INTERRUPTS();
470 ginEntryInsert(&buildstate->ginstate, attnum, key, category,
471 list, nlist, &buildstate->buildStats);
472 }
473
474 MemoryContextReset(buildstate->tmpCtx);
475 ginInitBA(&buildstate->accum);
476 }
477
478 MemoryContextSwitchTo(oldCtx);
479 }
480
481 /*
482 * ginFlushBuildState
483 * Write all data from BuildAccumulator into the tuplesort.
484 *
485 * The number of TIDs written to the tuplesort at once is limited, to reduce
486 * the amount of memory needed when merging the intermediate results later.
487 * The leader will see up to two chunks per worker, so calculate the limit to
488 * not need more than MaxAllocSize overall.
489 *
490 * We don't need to worry about overflowing maintenance_work_mem. We can't
491 * build chunks larger than work_mem, and that limit was set so that workers
492 * produce sufficiently small chunks.
493 */
494 static void
495 ginFlushBuildState(GinBuildState *buildstate, Relation index)
496 {
497 ItemPointerData *list;
498 Datum key;
499 GinNullCategory category;
500 uint32 nlist;
501 OffsetNumber attnum;
502 TupleDesc tdesc = RelationGetDescr(index);
503 uint32 maxlen;
504
505 /* maximum number of TIDs per chunk (two chunks per worker) */
506 maxlen = MaxAllocSize / sizeof(ItemPointerData);
507 maxlen /= (2 * buildstate->bs_num_workers);
508
509 ginBeginBAScan(&buildstate->accum);
510 while ((list = ginGetBAEntry(&buildstate->accum,
511 &attnum, &key, &category, &nlist)) != NULL)
512 {
513 /* information about the key */
514 Form_pg_attribute attr = TupleDescAttr(tdesc, (attnum - 1));
515
516 /* start of the chunk */
517 uint32 offset = 0;
518
519 /* split the entry into smaller chunk with up to maxlen items */
520 while (offset < nlist)
521 {
522 /* GIN tuple and tuple length */
523 GinTuple *tup;
524 Size tuplen;
525 uint32 len = Min(maxlen, nlist - offset);
526
527 /* there could be many entries, so be willing to abort here */
528 CHECK_FOR_INTERRUPTS();
529
530 tup = _gin_build_tuple(attnum, category,
531 key, attr->attlen, attr->attbyval,
532 &list[offset], len,
533 &tuplen);
534
535 offset += len;
536
537 tuplesort_putgintuple(buildstate->bs_worker_sort, tup, tuplen);
538
539 pfree(tup);
540 }
541 }
542
543 MemoryContextReset(buildstate->tmpCtx);
544 ginInitBA(&buildstate->accum);
545 }
546
547 /*
548 * ginBuildCallbackParallel
549 * Callback for the parallel index build.
550 *
551 * This is similar to the serial build callback ginBuildCallback, but
552 * instead of writing the accumulated entries into the index, each worker
553 * writes them into a (local) tuplesort.
554 *
555 * The worker then sorts and combines these entries, before writing them
556 * into a shared tuplesort for the leader (see _gin_parallel_scan_and_build
557 * for the whole process).
558 */
559 static void
560 ginBuildCallbackParallel(Relation index, ItemPointer tid, Datum *values,
561 bool *isnull, bool tupleIsAlive, void *state)
562 {
563 GinBuildState *buildstate = (GinBuildState *) state;
564 MemoryContext oldCtx;
565 int i;
566
567 oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);
568
569 /*
570 * if scan wrapped around - flush accumulated entries and start anew
571 *
572 * With parallel scans, we don't have a guarantee the scan does not start
573 * half-way through the relation (serial builds disable sync scans and
574 * always start from block 0, parallel scans require allow_sync=true).
575 *
576 * Building the posting lists assumes the TIDs are monotonic and never go
577 * back, and the wrap around would break that. We handle that by detecting
578 * the wraparound, and flushing all entries. This means we'll later see
579 * two separate entries with non-overlapping TID lists (which can be
580 * combined by merge sort).
581 *
582 * To detect a wraparound, we remember the last TID seen by each worker
583 * (for any key). If the next TID seen by the worker is lower, the scan
584 * must have wrapped around.
585 */
586 if (ItemPointerCompare(tid, &buildstate->tid) < 0)
587 ginFlushBuildState(buildstate, index);
588
589 /* remember the TID we're about to process */
590 buildstate->tid = *tid;
591
592 for (i = 0; i < buildstate->ginstate.origTupdesc->natts; i++)
593 ginHeapTupleBulkInsert(buildstate, (OffsetNumber) (i + 1),
594 values[i], isnull[i], tid);
595
596 /*
597 * If we've maxed out our available memory, dump everything to the
598 * tuplesort. We use half the per-worker fraction of maintenance_work_mem,
599 * the other half is used for the tuplesort.
600 */
601 if (buildstate->accum.allocatedMemory >= buildstate->work_mem * (Size) 1024)
602 ginFlushBuildState(buildstate, index);
603
604 MemoryContextSwitchTo(oldCtx);
605 }
606
607 IndexBuildResult *
608 ginbuild(Relation heap, Relation index, IndexInfo *indexInfo)
609 {
610 IndexBuildResult *result;
611 double reltuples;
612 GinBuildState buildstate;
613 GinBuildState *state = &buildstate;
614 Buffer RootBuffer,
615 MetaBuffer;
616 ItemPointerData *list;
617 Datum key;
618 GinNullCategory category;
619 uint32 nlist;
620 MemoryContext oldCtx;
621 OffsetNumber attnum;
622
623 if (RelationGetNumberOfBlocks(index) != 0)
624 elog(ERROR, "index \"%s\" already contains data",
625 RelationGetRelationName(index));
626
627 initGinState(&buildstate.ginstate, index);
628 buildstate.indtuples = 0;
629 memset(&buildstate.buildStats, 0, sizeof(GinStatsData));
630
631 /* Initialize fields for parallel build too. */
632 buildstate.bs_numtuples = 0;
633 buildstate.bs_reltuples = 0;
634 buildstate.bs_leader = NULL;
635 memset(&buildstate.tid, 0, sizeof(ItemPointerData));
636
637 /* initialize the meta page */
638 MetaBuffer = GinNewBuffer(index);
639
640 /* initialize the root page */
641 RootBuffer = GinNewBuffer(index);
642
643 START_CRIT_SECTION();
644 GinInitMetabuffer(MetaBuffer);
645 MarkBufferDirty(MetaBuffer);
646 GinInitBuffer(RootBuffer, GIN_LEAF);
647 MarkBufferDirty(RootBuffer);
648
649
650 UnlockReleaseBuffer(MetaBuffer);
651 UnlockReleaseBuffer(RootBuffer);
652 END_CRIT_SECTION();
653
654 /* count the root as first entry page */
655 buildstate.buildStats.nEntryPages++;
656
657 /*
658 * create a temporary memory context that is used to hold data not yet
659 * dumped out to the index
660 */
661 buildstate.tmpCtx = AllocSetContextCreate(CurrentMemoryContext,
662 "Gin build temporary context",
663 ALLOCSET_DEFAULT_SIZES);
664
665 /*
666 * create a temporary memory context that is used for calling
667 * ginExtractEntries(), and can be reset after each tuple
668 */
669 buildstate.funcCtx = AllocSetContextCreate(CurrentMemoryContext,
670 "Gin build temporary context for user-defined function",
671 ALLOCSET_DEFAULT_SIZES);
672
673 buildstate.accum.ginstate = &buildstate.ginstate;
674 ginInitBA(&buildstate.accum);
675
676 /* Report table scan phase started */
677 pgstat_progress_update_param(PROGRESS_CREATEIDX_SUBPHASE,
678 PROGRESS_GIN_PHASE_INDEXBUILD_TABLESCAN);
679
680 /*
681 * Attempt to launch parallel worker scan when required
682 *
683 * XXX plan_create_index_workers makes the number of workers dependent on
684 * maintenance_work_mem, requiring 32MB for each worker. For GIN that's
685 * reasonable too, because we sort the data just like btree. It does
686 * ignore the memory used to accumulate data in memory (set by work_mem),
687 * but there is no way to communicate that to plan_create_index_workers.
688 */
689 if (indexInfo->ii_ParallelWorkers > 0)
690 _gin_begin_parallel(state, heap, index, indexInfo->ii_Concurrent,
691 indexInfo->ii_ParallelWorkers);
692
693 /*
694 * If parallel build requested and at least one worker process was
695 * successfully launched, set up coordination state, wait for workers to
696 * complete. Then read all tuples from the shared tuplesort and insert
697 * them into the index.
698 *
699 * In serial mode, simply scan the table and build the index one index
700 * tuple at a time.
701 */
702 if (state->bs_leader)
703 {
704 SortCoordinate coordinate;
705
706 coordinate = (SortCoordinate) palloc0(sizeof(SortCoordinateData));
707 coordinate->isWorker = false;
708 coordinate->nParticipants =
709 state->bs_leader->nparticipanttuplesorts;
710 coordinate->sharedsort = state->bs_leader->sharedsort;
711
712 /*
713 * Begin leader tuplesort.
714 *
715 * In cases where parallelism is involved, the leader receives the
716 * same share of maintenance_work_mem as a serial sort (it is
717 * generally treated in the same way as a serial sort once we return).
718 * Parallel worker Tuplesortstates will have received only a fraction
719 * of maintenance_work_mem, though.
720 *
721 * We rely on the lifetime of the Leader Tuplesortstate almost not
722 * overlapping with any worker Tuplesortstate's lifetime. There may
723 * be some small overlap, but that's okay because we rely on leader
724 * Tuplesortstate only allocating a small, fixed amount of memory
725 * here. When its tuplesort_performsort() is called (by our caller),
726 * and significant amounts of memory are likely to be used, all
727 * workers must have already freed almost all memory held by their
728 * Tuplesortstates (they are about to go away completely, too). The
729 * overall effect is that maintenance_work_mem always represents an
730 * absolute high watermark on the amount of memory used by a CREATE
731 * INDEX operation, regardless of the use of parallelism or any other
732 * factor.
733 */
734 state->bs_sortstate =
735 tuplesort_begin_index_gin(heap, index,
736 maintenance_work_mem, coordinate,
737 TUPLESORT_NONE);
738
739 /* scan the relation in parallel and merge per-worker results */
740 reltuples = _gin_parallel_merge(state);
741
742 _gin_end_parallel(state->bs_leader, state);
743 }
744 else /* no parallel index build */
745 {
746 /*
747 * Do the heap scan. We disallow sync scan here because
748 * dataPlaceToPage prefers to receive tuples in TID order.
749 */
750 reltuples = table_index_build_scan(heap, index, indexInfo, false, true,
751 ginBuildCallback, &buildstate, NULL);
752
753 /* dump remaining entries to the index */
754 oldCtx = MemoryContextSwitchTo(buildstate.tmpCtx);
755 ginBeginBAScan(&buildstate.accum);
756 while ((list = ginGetBAEntry(&buildstate.accum,
757 &attnum, &key, &category, &nlist)) != NULL)
758 {
759 /* there could be many entries, so be willing to abort here */
760 CHECK_FOR_INTERRUPTS();
761 ginEntryInsert(&buildstate.ginstate, attnum, key, category,
762 list, nlist, &buildstate.buildStats);
763 }
764 MemoryContextSwitchTo(oldCtx);
765 }
766
767 MemoryContextDelete(buildstate.funcCtx);
768 MemoryContextDelete(buildstate.tmpCtx);
769
770 /*
771 * Update metapage stats
772 */
773 buildstate.buildStats.nTotalPages = RelationGetNumberOfBlocks(index);
774 ginUpdateStats(index, &buildstate.buildStats, true);
775
776 /*
777 * We didn't write WAL records as we built the index, so if WAL-logging is
778 * required, write all pages to the WAL now.
779 */
780 if (RelationNeedsWAL(index))
781 {
782 log_newpage_range(index, MAIN_FORKNUM,
783 0, RelationGetNumberOfBlocks(index),
784 true);
785 }
786
787 /*
788 * Return statistics
789 */
790 result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
791
792 result->heap_tuples = reltuples;
793 result->index_tuples = buildstate.indtuples;
794
795 return result;
796 }
797
798 /*
799 * ginbuildempty() -- build an empty gin index in the initialization fork
800 */
801 void
802 ginbuildempty(Relation index)
803 {
804 Buffer RootBuffer,
805 MetaBuffer;
806
807 /* An empty GIN index has two pages. */
808 MetaBuffer = ExtendBufferedRel(BMR_REL(index), INIT_FORKNUM, NULL,
809 EB_LOCK_FIRST | EB_SKIP_EXTENSION_LOCK);
810 RootBuffer = ExtendBufferedRel(BMR_REL(index), INIT_FORKNUM, NULL,
811 EB_LOCK_FIRST | EB_SKIP_EXTENSION_LOCK);
812
813 /* Initialize and xlog metabuffer and root buffer. */
814 START_CRIT_SECTION();
815 GinInitMetabuffer(MetaBuffer);
816 MarkBufferDirty(MetaBuffer);
817 log_newpage_buffer(MetaBuffer, true);
818 GinInitBuffer(RootBuffer, GIN_LEAF);
819 MarkBufferDirty(RootBuffer);
820 log_newpage_buffer(RootBuffer, false);
821 END_CRIT_SECTION();
822
823 /* Unlock and release the buffers. */
824 UnlockReleaseBuffer(MetaBuffer);
825 UnlockReleaseBuffer(RootBuffer);
826 }
827
828 /*
829 * Insert index entries for a single indexable item during "normal"
830 * (non-fast-update) insertion
831 */
832 static void
833 ginHeapTupleInsert(GinState *ginstate, OffsetNumber attnum,
834 Datum value, bool isNull,
835 ItemPointer item)
836 {
837 Datum *entries;
838 GinNullCategory *categories;
839 int32 i,
840 nentries;
841
842 entries = ginExtractEntries(ginstate, attnum, value, isNull,
843 &nentries, &categories);
844
845 for (i = 0; i < nentries; i++)
846 ginEntryInsert(ginstate, attnum, entries[i], categories[i],
847 item, 1, NULL);
848 }
849
850 bool
851 gininsert(Relation index, Datum *values, bool *isnull,
852 ItemPointer ht_ctid, Relation heapRel,
853 IndexUniqueCheck checkUnique,
854 bool indexUnchanged,
855 IndexInfo *indexInfo)
856 {
857 GinState *ginstate = (GinState *) indexInfo->ii_AmCache;
858 MemoryContext oldCtx;
859 MemoryContext insertCtx;
860 int i;
861
862 /* Initialize GinState cache if first call in this statement */
863 if (ginstate == NULL)
864 {
865 oldCtx = MemoryContextSwitchTo(indexInfo->ii_Context);
866 ginstate = (GinState *) palloc(sizeof(GinState));
867 initGinState(ginstate, index);
868 indexInfo->ii_AmCache = ginstate;
869 MemoryContextSwitchTo(oldCtx);
870 }
871
872 insertCtx = AllocSetContextCreate(CurrentMemoryContext,
873 "Gin insert temporary context",
874 ALLOCSET_DEFAULT_SIZES);
875
876 oldCtx = MemoryContextSwitchTo(insertCtx);
877
878 if (GinGetUseFastUpdate(index))
879 {
880 GinTupleCollector collector;
881
882 memset(&collector, 0, sizeof(GinTupleCollector));
883
884 for (i = 0; i < ginstate->origTupdesc->natts; i++)
885 ginHeapTupleFastCollect(ginstate, &collector,
886 (OffsetNumber) (i + 1),
887 values[i], isnull[i],
888 ht_ctid);
889
890 ginHeapTupleFastInsert(ginstate, &collector);
891 }
892 else
893 {
894 for (i = 0; i < ginstate->origTupdesc->natts; i++)
895 ginHeapTupleInsert(ginstate, (OffsetNumber) (i + 1),
896 values[i], isnull[i],
897 ht_ctid);
898 }
899
900 MemoryContextSwitchTo(oldCtx);
901 MemoryContextDelete(insertCtx);
902
903 return false;
904 }
905
906 /*
907 * Create parallel context, and launch workers for leader.
908 *
909 * buildstate argument should be initialized (with the exception of the
910 * tuplesort states, which may later be created based on shared
911 * state initially set up here).
912 *
913 * isconcurrent indicates if operation is CREATE INDEX CONCURRENTLY.
914 *
915 * request is the target number of parallel worker processes to launch.
916 *
917 * Sets buildstate's GinLeader, which caller must use to shut down parallel
918 * mode by passing it to _gin_end_parallel() at the very end of its index
919 * build. If not even a single worker process can be launched, this is
920 * never set, and caller should proceed with a serial index build.
921 */
922 static void
923 _gin_begin_parallel(GinBuildState *buildstate, Relation heap, Relation index,
924 bool isconcurrent, int request)
925 {
926 ParallelContext *pcxt;
927 int scantuplesortstates;
928 Snapshot snapshot;
929 Size estginshared;
930 Size estsort;
931 GinBuildShared *ginshared;
932 Sharedsort *sharedsort;
933 GinLeader *ginleader = (GinLeader *) palloc0(sizeof(GinLeader));
934 WalUsage *walusage;
935 BufferUsage *bufferusage;
936 bool leaderparticipates = true;
937 int querylen;
938
939 #ifdef DISABLE_LEADER_PARTICIPATION
940 leaderparticipates = false;
941 #endif
942
943 /*
944 * Enter parallel mode, and create context for parallel build of gin index
945 */
946 EnterParallelMode();
947 Assert(request > 0);
948 pcxt = CreateParallelContext("postgres", "_gin_parallel_build_main",
949 request);
950
951 scantuplesortstates = leaderparticipates ? request + 1 : request;
952
953 /*
954 * Prepare for scan of the base relation. In a normal index build, we use
955 * SnapshotAny because we must retrieve all tuples and do our own time
956 * qual checks (because we have to index RECENTLY_DEAD tuples). In a
957 * concurrent build, we take a regular MVCC snapshot and index whatever's
958 * live according to that.
959 */
960 if (!isconcurrent)
961 snapshot = SnapshotAny;
962 else
963 snapshot = RegisterSnapshot(GetTransactionSnapshot());
964
965 /*
966 * Estimate size for our own PARALLEL_KEY_GIN_SHARED workspace.
967 */
968 estginshared = _gin_parallel_estimate_shared(heap, snapshot);
969 shm_toc_estimate_chunk(&pcxt->estimator, estginshared);
970 estsort = tuplesort_estimate_shared(scantuplesortstates);
971 shm_toc_estimate_chunk(&pcxt->estimator, estsort);
972
973 shm_toc_estimate_keys(&pcxt->estimator, 2);
974
975 /*
976 * Estimate space for WalUsage and BufferUsage -- PARALLEL_KEY_WAL_USAGE
977 * and PARALLEL_KEY_BUFFER_USAGE.
978 *
979 * If there are no extensions loaded that care, we could skip this. We
980 * have no way of knowing whether anyone's looking at pgWalUsage or
981 * pgBufferUsage, so do it unconditionally.
982 */
983 shm_toc_estimate_chunk(&pcxt->estimator,
984 mul_size(sizeof(WalUsage), pcxt->nworkers));
985 shm_toc_estimate_keys(&pcxt->estimator, 1);
986 shm_toc_estimate_chunk(&pcxt->estimator,
987 mul_size(sizeof(BufferUsage), pcxt->nworkers));
988 shm_toc_estimate_keys(&pcxt->estimator, 1);
989
990 /* Finally, estimate PARALLEL_KEY_QUERY_TEXT space */
991 if (debug_query_string)
992 {
993 querylen = strlen(debug_query_string);
994 shm_toc_estimate_chunk(&pcxt->estimator, querylen + 1);
995 shm_toc_estimate_keys(&pcxt->estimator, 1);
996 }
997 else
998 querylen = 0; /* keep compiler quiet */
999
1000 /* Everyone's had a chance to ask for space, so now create the DSM */
1001 InitializeParallelDSM(pcxt);
1002
1003 /* If no DSM segment was available, back out (do serial build) */
1004 if (pcxt->seg == NULL)
1005 {
1006 if (IsMVCCSnapshot(snapshot))
1007 UnregisterSnapshot(snapshot);
1008 DestroyParallelContext(pcxt);
1009 ExitParallelMode();
1010 return;
1011 }
1012
1013 /* Store shared build state, for which we reserved space */
1014 ginshared = (GinBuildShared *) shm_toc_allocate(pcxt->toc, estginshared);
1015 /* Initialize immutable state */
1016 ginshared->heaprelid = RelationGetRelid(heap);
1017 ginshared->indexrelid = RelationGetRelid(index);
1018 ginshared->isconcurrent = isconcurrent;
1019 ginshared->scantuplesortstates = scantuplesortstates;
1020
1021 ConditionVariableInit(&ginshared->workersdonecv);
1022 SpinLockInit(&ginshared->mutex);
1023
1024 /* Initialize mutable state */
1025 ginshared->nparticipantsdone = 0;
1026 ginshared->reltuples = 0.0;
1027 ginshared->indtuples = 0.0;
1028
1029 table_parallelscan_initialize(heap,
1030 ParallelTableScanFromGinBuildShared(ginshared),
1031 snapshot);
1032
1033 /*
1034 * Store shared tuplesort-private state, for which we reserved space.
1035 * Then, initialize opaque state using tuplesort routine.
1036 */
1037 sharedsort = (Sharedsort *) shm_toc_allocate(pcxt->toc, estsort);
1038 tuplesort_initialize_shared(sharedsort, scantuplesortstates,
1039 pcxt->seg);
1040
1041 shm_toc_insert(pcxt->toc, PARALLEL_KEY_GIN_SHARED, ginshared);
1042 shm_toc_insert(pcxt->toc, PARALLEL_KEY_TUPLESORT, sharedsort);
1043
1044 /* Store query string for workers */
1045 if (debug_query_string)
1046 {
1047 char *sharedquery;
1048
1049 sharedquery = (char *) shm_toc_allocate(pcxt->toc, querylen + 1);
1050 memcpy(sharedquery, debug_query_string, querylen + 1);
1051 shm_toc_insert(pcxt->toc, PARALLEL_KEY_QUERY_TEXT, sharedquery);
1052 }
1053
1054 /*
1055 * Allocate space for each worker's WalUsage and BufferUsage; no need to
1056 * initialize.
1057 */
1058 walusage = shm_toc_allocate(pcxt->toc,
1059 mul_size(sizeof(WalUsage), pcxt->nworkers));
1060 shm_toc_insert(pcxt->toc, PARALLEL_KEY_WAL_USAGE, walusage);
1061 bufferusage = shm_toc_allocate(pcxt->toc,
1062 mul_size(sizeof(BufferUsage), pcxt->nworkers));
1063 shm_toc_insert(pcxt->toc, PARALLEL_KEY_BUFFER_USAGE, bufferusage);
1064
1065 /* Launch workers, saving status for leader/caller */
1066 LaunchParallelWorkers(pcxt);
1067 ginleader->pcxt = pcxt;
1068 ginleader->nparticipanttuplesorts = pcxt->nworkers_launched;
1069 if (leaderparticipates)
1070 ginleader->nparticipanttuplesorts++;
1071 ginleader->ginshared = ginshared;
1072 ginleader->sharedsort = sharedsort;
1073 ginleader->snapshot = snapshot;
1074 ginleader->walusage = walusage;
1075 ginleader->bufferusage = bufferusage;
1076
1077 /* If no workers were successfully launched, back out (do serial build) */
1078 if (pcxt->nworkers_launched == 0)
1079 {
1080 _gin_end_parallel(ginleader, NULL);
1081 return;
1082 }
1083
1084 /* Save leader state now that it's clear build will be parallel */
1085 buildstate->bs_leader = ginleader;
1086
1087 /* Join heap scan ourselves */
1088 if (leaderparticipates)
1089 _gin_leader_participate_as_worker(buildstate, heap, index);
1090
1091 /*
1092 * Caller needs to wait for all launched workers when we return. Make
1093 * sure that the failure-to-start case will not hang forever.
1094 */
1095 WaitForParallelWorkersToAttach(pcxt);
1096 }
1097
1098 /*
1099 * Shut down workers, destroy parallel context, and end parallel mode.
1100 */
1101 static void
1102 _gin_end_parallel(GinLeader *ginleader, GinBuildState *state)
1103 {
1104 int i;
1105
1106 /* Shutdown worker processes */
1107 WaitForParallelWorkersToFinish(ginleader->pcxt);
1108
1109 /*
1110 * Next, accumulate WAL usage. (This must wait for the workers to finish,
1111 * or we might get incomplete data.)
1112 */
1113 for (i = 0; i < ginleader->pcxt->nworkers_launched; i++)
1114 InstrAccumParallelQuery(&ginleader->bufferusage[i], &ginleader->walusage[i]);
1115
1116 /* Free last reference to MVCC snapshot, if one was used */
1117 if (IsMVCCSnapshot(ginleader->snapshot))
1118 UnregisterSnapshot(ginleader->snapshot);
1119 DestroyParallelContext(ginleader->pcxt);
1120 ExitParallelMode();
1121 }
1122
1123 /*
1124 * Within leader, wait for end of heap scan.
1125 *
1126 * When called, parallel heap scan started by _gin_begin_parallel() will
1127 * already be underway within worker processes (when leader participates
1128 * as a worker, we should end up here just as workers are finishing).
1129 *
1130 * Returns the total number of heap tuples scanned.
1131 */
1132 static double
1133 _gin_parallel_heapscan(GinBuildState *state)
1134 {
1135 GinBuildShared *ginshared = state->bs_leader->ginshared;
1136 int nparticipanttuplesorts;
1137
1138 nparticipanttuplesorts = state->bs_leader->nparticipanttuplesorts;
1139 for (;;)
1140 {
1141 SpinLockAcquire(&ginshared->mutex);
1142 if (ginshared->nparticipantsdone == nparticipanttuplesorts)
1143 {
1144 /* copy the data into leader state */
1145 state->bs_reltuples = ginshared->reltuples;
1146 state->bs_numtuples = ginshared->indtuples;
1147
1148 SpinLockRelease(&ginshared->mutex);
1149 break;
1150 }
1151 SpinLockRelease(&ginshared->mutex);
1152
1153 ConditionVariableSleep(&ginshared->workersdonecv,
1154 WAIT_EVENT_PARALLEL_CREATE_INDEX_SCAN);
1155 }
1156
1157 ConditionVariableCancelSleep();
1158
1159 return state->bs_reltuples;
1160 }
1161
1162 /*
1163 * Buffer used to accumulate TIDs from multiple GinTuples for the same key
1164 * (we read these from the tuplesort, sorted by the key).
1165 *
1166 * This is similar to BuildAccumulator in that it's used to collect TIDs
1167 * in memory before inserting them into the index, but it's much simpler
1168 * as it only deals with a single index key at a time.
1169 *
1170 * When adding TIDs to the buffer, we make sure to keep them sorted, both
1171 * during the initial table scan (and detecting when the scan wraps around),
1172 * and during merging (where we do mergesort).
1173 */
1174 typedef struct GinBuffer
1175 {
1176 OffsetNumber attnum;
1177 GinNullCategory category;
1178 Datum key; /* 0 if no key (and keylen == 0) */
1179 Size keylen; /* number of bytes (not typlen) */
1180
1181 /* type info */
1182 int16 typlen;
1183 bool typbyval;
1184
1185 /* Number of TIDs to collect before attempt to write some out. */
1186 int maxitems;
1187
1188 /* array of TID values */
1189 int nitems;
1190 int nfrozen;
1191 SortSupport ssup; /* for sorting/comparing keys */
1192 ItemPointerData *items;
1193 } GinBuffer;
1194
1195 /*
1196 * Check that TID array contains valid values, and that it's sorted (if we
1197 * expect it to be).
1198 */
1199 static void
1200 AssertCheckItemPointers(GinBuffer *buffer)
1201 {
1202 #ifdef USE_ASSERT_CHECKING
1203 /* we should not have a buffer with no TIDs to sort */
1204 Assert(buffer->items != NULL);
1205 Assert(buffer->nitems > 0);
1206
1207 for (int i = 0; i < buffer->nitems; i++)
1208 {
1209 Assert(ItemPointerIsValid(&buffer->items[i]));
1210
1211 /* don't check ordering for the first TID item */
1212 if (i == 0)
1213 continue;
1214
1215 Assert(ItemPointerCompare(&buffer->items[i - 1], &buffer->items[i]) < 0);
1216 }
1217 #endif
1218 }
1219
1220 /*
1221 * GinBuffer checks
1222 *
1223 * Make sure the nitems/items fields are consistent (either the array is empty
1224 * or not empty, the fields need to agree). If there are items, check ordering.
1225 */
1226 static void
1227 AssertCheckGinBuffer(GinBuffer *buffer)
1228 {
1229 #ifdef USE_ASSERT_CHECKING
1230 /* if we have any items, the array must exist */
1231 Assert(!((buffer->nitems > 0) && (buffer->items == NULL)));
1232
1233 /*
1234 * The buffer may be empty, in which case we must not call the check of
1235 * item pointers, because that assumes non-emptiness.
1236 */
1237 if (buffer->nitems == 0)
1238 return;
1239
1240 /* Make sure the item pointers are valid and sorted. */
1241 AssertCheckItemPointers(buffer);
1242 #endif
1243 }
1244
1245 /*
1246 * GinBufferInit
1247 * Initialize buffer to store tuples for a GIN index.
1248 *
1249 * Initialize the buffer used to accumulate TID for a single key at a time
1250 * (we process the data sorted), so we know when we received all data for
1251 * a given key.
1252 *
1253 * Initializes sort support procedures for all index attributes.
1254 */
1255 static GinBuffer *
1256 GinBufferInit(Relation index)
1257 {
1258 GinBuffer *buffer = palloc0(sizeof(GinBuffer));
1259 int i,
1260 nKeys;
1261 TupleDesc desc = RelationGetDescr(index);
1262
1263 /*
1264 * How many items can we fit into the memory limit? We don't want to end
1265 * with too many TIDs. and 64kB seems more than enough. But maybe this
1266 * should be tied to maintenance_work_mem or something like that?
1267 */
1268 buffer->maxitems = (64 * 1024L) / sizeof(ItemPointerData);
1269
1270 nKeys = IndexRelationGetNumberOfKeyAttributes(index);
1271
1272 buffer->ssup = palloc0(sizeof(SortSupportData) * nKeys);
1273
1274 /*
1275 * Lookup ordering operator for the index key data type, and initialize
1276 * the sort support function.
1277 */
1278 for (i = 0; i < nKeys; i++)
1279 {
1280 Oid cmpFunc;
1281 SortSupport sortKey = &buffer->ssup[i];
1282 Form_pg_attribute att = TupleDescAttr(desc, i);
1283
1284 sortKey->ssup_cxt = CurrentMemoryContext;
1285 sortKey->ssup_collation = index->rd_indcollation[i];
1286
1287 if (!OidIsValid(sortKey->ssup_collation))
1288 sortKey->ssup_collation = DEFAULT_COLLATION_OID;
1289
1290 sortKey->ssup_nulls_first = false;
1291 sortKey->ssup_attno = i + 1;
1292 sortKey->abbreviate = false;
1293
1294 Assert(sortKey->ssup_attno != 0);
1295
1296 /*
1297 * If the compare proc isn't specified in the opclass definition, look
1298 * up the index key type's default btree comparator.
1299 */
1300 cmpFunc = index_getprocid(index, i + 1, GIN_COMPARE_PROC);
1301 if (cmpFunc == InvalidOid)
1302 {
1303 TypeCacheEntry *typentry;
1304
1305 typentry = lookup_type_cache(att->atttypid,
1306 TYPECACHE_CMP_PROC_FINFO);
1307 if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
1308 ereport(ERROR,
1309 (errcode(ERRCODE_UNDEFINED_FUNCTION),
1310 errmsg("could not identify a comparison function for type %s",
1311 format_type_be(att->atttypid))));
1312
1313 cmpFunc = typentry->cmp_proc_finfo.fn_oid;
1314 }
1315
1316 PrepareSortSupportComparisonShim(cmpFunc, sortKey);
1317 }
1318
1319 return buffer;
1320 }
1321
1322 /* Is the buffer empty, i.e. has no TID values in the array? */
1323 static bool
1324 GinBufferIsEmpty(GinBuffer *buffer)
1325 {
1326 return (buffer->nitems == 0);
1327 }
1328
1329 /*
1330 * GinBufferKeyEquals
1331 * Can the buffer store TIDs for the provided GIN tuple (same key)?
1332 *
1333 * Compare if the tuple matches the already accumulated data in the GIN
1334 * buffer. Compare scalar fields first, before the actual key.
1335 *
1336 * Returns true if the key matches, and the TID belongs to the buffer, or
1337 * false if the key does not match.
1338 */
1339 static bool
1340 GinBufferKeyEquals(GinBuffer *buffer, GinTuple *tup)
1341 {
1342 int r;
1343 Datum tupkey;
1344
1345 AssertCheckGinBuffer(buffer);
1346
1347 if (tup->attrnum != buffer->attnum)
1348 return false;
1349
1350 /* same attribute should have the same type info */
1351 Assert(tup->typbyval == buffer->typbyval);
1352 Assert(tup->typlen == buffer->typlen);
1353
1354 if (tup->category != buffer->category)
1355 return false;
1356
1357 /*
1358 * For NULL/empty keys, this means equality, for normal keys we need to
1359 * compare the actual key value.
1360 */
1361 if (buffer->category != GIN_CAT_NORM_KEY)
1362 return true;
1363
1364 /*
1365 * For the tuple, get either the first sizeof(Datum) bytes for byval
1366 * types, or a pointer to the beginning of the data array.
1367 */
1368 tupkey = (buffer->typbyval) ? *(Datum *) tup->data : PointerGetDatum(tup->data);
1369
1370 r = ApplySortComparator(buffer->key, false,
1371 tupkey, false,
1372 &buffer->ssup[buffer->attnum - 1]);
1373
1374 return (r == 0);
1375 }
1376
1377 /*
1378 * GinBufferShouldTrim
1379 * Should we trim the list of item pointers?
1380 *
1381 * By trimming we understand writing out and removing the tuple IDs that
1382 * we know can't change by future merges. We can deduce the TID up to which
1383 * this is guaranteed from the "first" TID in each GIN tuple, which provides
1384 * a "horizon" (for a given key) thanks to the sort.
1385 *
1386 * We don't want to do this too often - compressing longer TID lists is more
1387 * efficient. But we also don't want to accumulate too many TIDs, for two
1388 * reasons. First, it consumes memory and we might exceed maintenance_work_mem
1389 * (or whatever limit applies), even if that's unlikely because TIDs are very
1390 * small so we can fit a lot of them. Second, and more importantly, long TID
1391 * lists are an issue if the scan wraps around, because a key may get a very
1392 * wide list (with min/max TID for that key), forcing "full" mergesorts for
1393 * every list merged into it (instead of the efficient append).
1394 *
1395 * So we look at two things when deciding if to trim - if the resulting list
1396 * (after adding TIDs from the new tuple) would be too long, and if there is
1397 * enough TIDs to trim (with values less than "first" TID from the new tuple),
1398 * we do the trim. By enough we mean at least 128 TIDs (mostly an arbitrary
1399 * number).
1400 */
1401 static bool
1402 GinBufferShouldTrim(GinBuffer *buffer, GinTuple *tup)
1403 {
1404 /* not enough TIDs to trim (1024 is somewhat arbitrary number) */
1405 if (buffer->nfrozen < 1024)
1406 return false;
1407
1408 /* no need to trim if we have not hit the memory limit yet */
1409 if ((buffer->nitems + tup->nitems) < buffer->maxitems)
1410 return false;
1411
1412 /*
1413 * OK, we have enough frozen TIDs to flush, and we have hit the memory
1414 * limit, so it's time to write it out.
1415 */
1416 return true;
1417 }
1418
1419 /*
1420 * GinBufferStoreTuple
1421 * Add data (especially TID list) from a GIN tuple to the buffer.
1422 *
1423 * The buffer is expected to be empty (in which case it's initialized), or
1424 * having the same key. The TID values from the tuple are combined with the
1425 * stored values using a merge sort.
1426 *
1427 * The tuples (for the same key) are expected to be sorted by first TID. But
1428 * this does not guarantee the lists do not overlap, especially in the leader,
1429 * because the workers process interleaving data. There should be no overlaps
1430 * in a single worker - it could happen when the parallel scan wraps around,
1431 * but we detect that and flush the data (see ginBuildCallbackParallel).
1432 *
1433 * By sorting the GinTuple not only by key, but also by the first TID, we make
1434 * it more less likely the lists will overlap during merge. We merge them using
1435 * mergesort, but it's cheaper to just append one list to the other.
1436 *
1437 * How often can the lists overlap? There should be no overlaps in workers,
1438 * and in the leader we can see overlaps between lists built by different
1439 * workers. But the workers merge the items as much as possible, so there
1440 * should not be too many.
1441 */
1442 static void
1443 GinBufferStoreTuple(GinBuffer *buffer, GinTuple *tup)
1444 {
1445 ItemPointerData *items;
1446 Datum key;
1447
1448 AssertCheckGinBuffer(buffer);
1449
1450 key = _gin_parse_tuple_key(tup);
1451 items = _gin_parse_tuple_items(tup);
1452
1453 /* if the buffer is empty, set the fields (and copy the key) */
1454 if (GinBufferIsEmpty(buffer))
1455 {
1456 buffer->category = tup->category;
1457 buffer->keylen = tup->keylen;
1458 buffer->attnum = tup->attrnum;
1459
1460 buffer->typlen = tup->typlen;
1461 buffer->typbyval = tup->typbyval;
1462
1463 if (tup->category == GIN_CAT_NORM_KEY)
1464 buffer->key = datumCopy(key, buffer->typbyval, buffer->typlen);
1465 else
1466 buffer->key = (Datum) 0;
1467 }
1468
1469 /*
1470 * Try freeze TIDs at the beginning of the list, i.e. exclude them from
1471 * the mergesort. We can do that with TIDs before the first TID in the new
1472 * tuple we're about to add into the buffer.
1473 *
1474 * We do this incrementally when adding data into the in-memory buffer,
1475 * and not later (e.g. when hitting a memory limit), because it allows us
1476 * to skip the frozen data during the mergesort, making it cheaper.
1477 */
1478
1479 /*
1480 * Check if the last TID in the current list is frozen. This is the case
1481 * when merging non-overlapping lists, e.g. in each parallel worker.
1482 */
1483 if ((buffer->nitems > 0) &&
1484 (ItemPointerCompare(&buffer->items[buffer->nitems - 1],
1485 GinTupleGetFirst(tup)) == 0))
1486 buffer->nfrozen = buffer->nitems;
1487
1488 /*
1489 * Now find the last TID we know to be frozen, i.e. the last TID right
1490 * before the new GIN tuple.
1491 *
1492 * Start with the first not-yet-frozen tuple, and walk until we find the
1493 * first TID that's higher. If we already know the whole list is frozen
1494 * (i.e. nfrozen == nitems), this does nothing.
1495 *
1496 * XXX This might do a binary search for sufficiently long lists, but it
1497 * does not seem worth the complexity. Overlapping lists should be rare
1498 * common, TID comparisons are cheap, and we should quickly freeze most of
1499 * the list.
1500 */
1501 for (int i = buffer->nfrozen; i < buffer->nitems; i++)
1502 {
1503 /* Is the TID after the first TID of the new tuple? Can't freeze. */
1504 if (ItemPointerCompare(&buffer->items[i],
1505 GinTupleGetFirst(tup)) > 0)
1506 break;
1507
1508 buffer->nfrozen++;
1509 }
1510
1511 /* add the new TIDs into the buffer, combine using merge-sort */
1512 {
1513 int nnew;
1514 ItemPointer new;
1515
1516 /*
1517 * Resize the array - we do this first, because we'll dereference the
1518 * first unfrozen TID, which would fail if the array is NULL. We'll
1519 * still pass 0 as number of elements in that array though.
1520 */
1521 if (buffer->items == NULL)
1522 buffer->items = palloc((buffer->nitems + tup->nitems) * sizeof(ItemPointerData));
1523 else
1524 buffer->items = repalloc(buffer->items,
1525 (buffer->nitems + tup->nitems) * sizeof(ItemPointerData));
1526
1527 new = ginMergeItemPointers(&buffer->items[buffer->nfrozen], /* first unfrozen */
1528 (buffer->nitems - buffer->nfrozen), /* num of unfrozen */
1529 items, tup->nitems, &nnew);
1530
1531 Assert(nnew == (tup->nitems + (buffer->nitems - buffer->nfrozen)));
1532
1533 memcpy(&buffer->items[buffer->nfrozen], new,
1534 nnew * sizeof(ItemPointerData));
1535
1536 pfree(new);
1537
1538 buffer->nitems += tup->nitems;
1539
1540 AssertCheckItemPointers(buffer);
1541 }
1542
1543 /* free the decompressed TID list */
1544 pfree(items);
1545 }
1546
1547 /*
1548 * GinBufferReset
1549 * Reset the buffer into a state as if it contains no data.
1550 */
1551 static void
1552 GinBufferReset(GinBuffer *buffer)
1553 {
1554 Assert(!GinBufferIsEmpty(buffer));
1555
1556 /* release byref values, do nothing for by-val ones */
1557 if ((buffer->category == GIN_CAT_NORM_KEY) && !buffer->typbyval)
1558 pfree(DatumGetPointer(buffer->key));
1559
1560 /*
1561 * Not required, but makes it more likely to trigger NULL dereference if
1562 * using the value incorrectly, etc.
1563 */
1564 buffer->key = (Datum) 0;
1565
1566 buffer->attnum = 0;
1567 buffer->category = 0;
1568 buffer->keylen = 0;
1569 buffer->nitems = 0;
1570 buffer->nfrozen = 0;
1571
1572 buffer->typlen = 0;
1573 buffer->typbyval = 0;
1574 }
1575
1576 /*
1577 * GinBufferTrim
1578 * Discard the "frozen" part of the TID list (which should have been
1579 * written to disk/index before this call).
1580 */
1581 static void
1582 GinBufferTrim(GinBuffer *buffer)
1583 {
1584 Assert((buffer->nfrozen > 0) && (buffer->nfrozen <= buffer->nitems));
1585
1586 memmove(&buffer->items[0], &buffer->items[buffer->nfrozen],
1587 sizeof(ItemPointerData) * (buffer->nitems - buffer->nfrozen));
1588
1589 buffer->nitems -= buffer->nfrozen;
1590 buffer->nfrozen = 0;
1591 }
1592
1593 /*
1594 * GinBufferFree
1595 * Release memory associated with the GinBuffer (including TID array).
1596 */
1597 static void
1598 GinBufferFree(GinBuffer *buffer)
1599 {
1600 if (buffer->items)
1601 pfree(buffer->items);
1602
1603 /* release byref values, do nothing for by-val ones */
1604 if (!GinBufferIsEmpty(buffer) &&
1605 (buffer->category == GIN_CAT_NORM_KEY) && !buffer->typbyval)
1606 pfree(DatumGetPointer(buffer->key));
1607
1608 pfree(buffer);
1609 }
1610
1611 /*
1612 * GinBufferCanAddKey
1613 * Check if a given GIN tuple can be added to the current buffer.
1614 *
1615 * Returns true if the buffer is either empty or for the same index key.
1616 */
1617 static bool
1618 GinBufferCanAddKey(GinBuffer *buffer, GinTuple *tup)
1619 {
1620 /* empty buffer can accept data for any key */
1621 if (GinBufferIsEmpty(buffer))
1622 return true;
1623
1624 /* otherwise just data for the same key */
1625 return GinBufferKeyEquals(buffer, tup);
1626 }
1627
1628 /*
1629 * Within leader, wait for end of heap scan and merge per-worker results.
1630 *
1631 * After waiting for all workers to finish, merge the per-worker results into
1632 * the complete index. The results from each worker are sorted by block number
1633 * (start of the page range). While combining the per-worker results we merge
1634 * summaries for the same page range, and also fill-in empty summaries for
1635 * ranges without any tuples.
1636 *
1637 * Returns the total number of heap tuples scanned.
1638 */
1639 static double
1640 _gin_parallel_merge(GinBuildState *state)
1641 {
1642 GinTuple *tup;
1643 Size tuplen;
1644 double reltuples = 0;
1645 GinBuffer *buffer;
1646
1647 /* GIN tuples from workers, merged by leader */
1648 double numtuples = 0;
1649
1650 /* wait for workers to scan table and produce partial results */
1651 reltuples = _gin_parallel_heapscan(state);
1652
1653 /* Execute the sort */
1654 pgstat_progress_update_param(PROGRESS_CREATEIDX_SUBPHASE,
1655 PROGRESS_GIN_PHASE_PERFORMSORT_2);
1656
1657 /* do the actual sort in the leader */
1658 tuplesort_performsort(state->bs_sortstate);
1659
1660 /*
1661 * Initialize buffer to combine entries for the same key.
1662 *
1663 * The leader is allowed to use the whole maintenance_work_mem buffer to
1664 * combine data. The parallel workers already completed.
1665 */
1666 buffer = GinBufferInit(state->ginstate.index);
1667
1668 /*
1669 * Set the progress target for the next phase. Reset the block number
1670 * values set by table_index_build_scan
1671 */
1672 {
1673 const int progress_index[] = {
1674 PROGRESS_CREATEIDX_SUBPHASE,
1675 PROGRESS_CREATEIDX_TUPLES_TOTAL,
1676 PROGRESS_SCAN_BLOCKS_TOTAL,
1677 PROGRESS_SCAN_BLOCKS_DONE
1678 };
1679 const int64 progress_vals[] = {
1680 PROGRESS_GIN_PHASE_MERGE_2,
1681 state->bs_numtuples,
1682 0, 0
1683 };
1684
1685 pgstat_progress_update_multi_param(4, progress_index, progress_vals);
1686 }
1687
1688 /*
1689 * Read the GIN tuples from the shared tuplesort, sorted by category and
1690 * key. That probably gives us order matching how data is organized in the
1691 * index.
1692 *
1693 * We don't insert the GIN tuples right away, but instead accumulate as
1694 * many TIDs for the same key as possible, and then insert that at once.
1695 * This way we don't need to decompress/recompress the posting lists, etc.
1696 */
1697 while ((tup = tuplesort_getgintuple(state->bs_sortstate, &tuplen, true)) != NULL)
1698 {
1699 MemoryContext oldCtx;
1700
1701 CHECK_FOR_INTERRUPTS();
1702
1703 /*
1704 * If the buffer can accept the new GIN tuple, just store it there and
1705 * we're done. If it's a different key (or maybe too much data) flush
1706 * the current contents into the index first.
1707 */
1708 if (!GinBufferCanAddKey(buffer, tup))
1709 {
1710 /*
1711 * Buffer is not empty and it's storing a different key - flush
1712 * the data into the insert, and start a new entry for current
1713 * GinTuple.
1714 */
1715 AssertCheckItemPointers(buffer);
1716
1717 oldCtx = MemoryContextSwitchTo(state->tmpCtx);
1718
1719 ginEntryInsert(&state->ginstate,
1720 buffer->attnum, buffer->key, buffer->category,
1721 buffer->items, buffer->nitems, &state->buildStats);
1722
1723 MemoryContextSwitchTo(oldCtx);
1724 MemoryContextReset(state->tmpCtx);
1725
1726 /* discard the existing data */
1727 GinBufferReset(buffer);
1728 }
1729
1730 /*
1731 * We're about to add a GIN tuple to the buffer - check the memory
1732 * limit first, and maybe write out some of the data into the index
1733 * first, if needed (and possible). We only flush the part of the TID
1734 * list that we know won't change, and only if there's enough data for
1735 * compression to work well.
1736 */
1737 if (GinBufferShouldTrim(buffer, tup))
1738 {
1739 Assert(buffer->nfrozen > 0);
1740
1741 /*
1742 * Buffer is not empty and it's storing a different key - flush
1743 * the data into the insert, and start a new entry for current
1744 * GinTuple.
1745 */
1746 AssertCheckItemPointers(buffer);
1747
1748 oldCtx = MemoryContextSwitchTo(state->tmpCtx);
1749
1750 ginEntryInsert(&state->ginstate,
1751 buffer->attnum, buffer->key, buffer->category,
1752 buffer->items, buffer->nfrozen, &state->buildStats);
1753
1754 MemoryContextSwitchTo(oldCtx);
1755 MemoryContextReset(state->tmpCtx);
1756
1757 /* truncate the data we've just discarded */
1758 GinBufferTrim(buffer);
1759 }
1760
1761 /*
1762 * Remember data for the current tuple (either remember the new key,
1763 * or append if to the existing data).
1764 */
1765 GinBufferStoreTuple(buffer, tup);
1766
1767 /* Report progress */
1768 pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
1769 ++numtuples);
1770 }
1771
1772 /* flush data remaining in the buffer (for the last key) */
1773 if (!GinBufferIsEmpty(buffer))
1774 {
1775 AssertCheckItemPointers(buffer);
1776
1777 ginEntryInsert(&state->ginstate,
1778 buffer->attnum, buffer->key, buffer->category,
1779 buffer->items, buffer->nitems, &state->buildStats);
1780
1781 /* discard the existing data */
1782 GinBufferReset(buffer);
1783
1784 /* Report progress */
1785 pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
1786 ++numtuples);
1787 }
1788
1789 /* relase all the memory */
1790 GinBufferFree(buffer);
1791
1792 tuplesort_end(state->bs_sortstate);
1793
1794 return reltuples;
1795 }
1796
1797 /*
1798 * Returns size of shared memory required to store state for a parallel
1799 * gin index build based on the snapshot its parallel scan will use.
1800 */
1801 static Size
1802 _gin_parallel_estimate_shared(Relation heap, Snapshot snapshot)
1803 {
1804 /* c.f. shm_toc_allocate as to why BUFFERALIGN is used */
1805 return add_size(BUFFERALIGN(sizeof(GinBuildShared)),
1806 table_parallelscan_estimate(heap, snapshot));
1807 }
1808
1809 /*
1810 * Within leader, participate as a parallel worker.
1811 */
1812 static void
1813 _gin_leader_participate_as_worker(GinBuildState *buildstate, Relation heap, Relation index)
1814 {
1815 GinLeader *ginleader = buildstate->bs_leader;
1816 int sortmem;
1817
1818 /*
1819 * Might as well use reliable figure when doling out maintenance_work_mem
1820 * (when requested number of workers were not launched, this will be
1821 * somewhat higher than it is for other workers).
1822 */
1823 sortmem = maintenance_work_mem / ginleader->nparticipanttuplesorts;
1824
1825 /* Perform work common to all participants */
1826 _gin_parallel_scan_and_build(buildstate, ginleader->ginshared,
1827 ginleader->sharedsort, heap, index,
1828 sortmem, true);
1829 }
1830
1831 /*
1832 * _gin_process_worker_data
1833 * First phase of the key merging, happening in the worker.
1834 *
1835 * Depending on the number of distinct keys, the TID lists produced by the
1836 * callback may be very short (due to frequent evictions in the callback).
1837 * But combining many tiny lists is expensive, so we try to do as much as
1838 * possible in the workers and only then pass the results to the leader.
1839 *
1840 * We read the tuples sorted by the key, and merge them into larger lists.
1841 * At the moment there's no memory limit, so this will just produce one
1842 * huge (sorted) list per key in each worker. Which means the leader will
1843 * do a very limited number of mergesorts, which is good.
1844 */
1845 static void
1846 _gin_process_worker_data(GinBuildState *state, Tuplesortstate *worker_sort,
1847 bool progress)
1848 {
1849 GinTuple *tup;
1850 Size tuplen;
1851
1852 GinBuffer *buffer;
1853
1854 /*
1855 * Initialize buffer to combine entries for the same key.
1856 *
1857 * The workers are limited to the same amount of memory as during the sort
1858 * in ginBuildCallbackParallel. But this probably should be the 32MB used
1859 * during planning, just like there.
1860 */
1861 buffer = GinBufferInit(state->ginstate.index);
1862
1863 /* sort the raw per-worker data */
1864 if (progress)
1865 pgstat_progress_update_param(PROGRESS_CREATEIDX_SUBPHASE,
1866 PROGRESS_GIN_PHASE_PERFORMSORT_1);
1867
1868 tuplesort_performsort(state->bs_worker_sort);
1869
1870 if (progress)
1871 pgstat_progress_update_param(PROGRESS_CREATEIDX_SUBPHASE,
1872 PROGRESS_GIN_PHASE_MERGE_1);
1873
1874 /*
1875 * Read the GIN tuples from the shared tuplesort, sorted by the key, and
1876 * merge them into larger chunks for the leader to combine.
1877 */
1878 while ((tup = tuplesort_getgintuple(worker_sort, &tuplen, true)) != NULL)
1879 {
1880
1881 CHECK_FOR_INTERRUPTS();
1882
1883 /*
1884 * If the buffer can accept the new GIN tuple, just store it there and
1885 * we're done. If it's a different key (or maybe too much data) flush
1886 * the current contents into the index first.
1887 */
1888 if (!GinBufferCanAddKey(buffer, tup))
1889 {
1890 GinTuple *ntup;
1891 Size ntuplen;
1892
1893 /*
1894 * Buffer is not empty and it's storing a different key - flush
1895 * the data into the insert, and start a new entry for current
1896 * GinTuple.
1897 */
1898 AssertCheckItemPointers(buffer);
1899
1900 ntup = _gin_build_tuple(buffer->attnum, buffer->category,
1901 buffer->key, buffer->typlen, buffer->typbyval,
1902 buffer->items, buffer->nitems, &ntuplen);
1903
1904 tuplesort_putgintuple(state->bs_sortstate, ntup, ntuplen);
1905 state->bs_numtuples++;
1906
1907 pfree(ntup);
1908
1909 /* discard the existing data */
1910 GinBufferReset(buffer);
1911 }
1912
1913 /*
1914 * We're about to add a GIN tuple to the buffer - check the memory
1915 * limit first, and maybe write out some of the data into the index
1916 * first, if needed (and possible). We only flush the part of the TID
1917 * list that we know won't change, and only if there's enough data for
1918 * compression to work well.
1919 */
1920 if (GinBufferShouldTrim(buffer, tup))
1921 {
1922 GinTuple *ntup;
1923 Size ntuplen;
1924
1925 Assert(buffer->nfrozen > 0);
1926
1927 /*
1928 * Buffer is not empty and it's storing a different key - flush
1929 * the data into the insert, and start a new entry for current
1930 * GinTuple.
1931 */
1932 AssertCheckItemPointers(buffer);
1933
1934 ntup = _gin_build_tuple(buffer->attnum, buffer->category,
1935 buffer->key, buffer->typlen, buffer->typbyval,
1936 buffer->items, buffer->nfrozen, &ntuplen);
1937
1938 tuplesort_putgintuple(state->bs_sortstate, ntup, ntuplen);
1939
1940 pfree(ntup);
1941
1942 /* truncate the data we've just discarded */
1943 GinBufferTrim(buffer);
1944 }
1945
1946 /*
1947 * Remember data for the current tuple (either remember the new key,
1948 * or append if to the existing data).
1949 */
1950 GinBufferStoreTuple(buffer, tup);
1951 }
1952
1953 /* flush data remaining in the buffer (for the last key) */
1954 if (!GinBufferIsEmpty(buffer))
1955 {
1956 GinTuple *ntup;
1957 Size ntuplen;
1958
1959 AssertCheckItemPointers(buffer);
1960
1961 ntup = _gin_build_tuple(buffer->attnum, buffer->category,
1962 buffer->key, buffer->typlen, buffer->typbyval,
1963 buffer->items, buffer->nitems, &ntuplen);
1964
1965 tuplesort_putgintuple(state->bs_sortstate, ntup, ntuplen);
1966 state->bs_numtuples++;
1967
1968 pfree(ntup);
1969
1970 /* discard the existing data */
1971 GinBufferReset(buffer);
1972 }
1973
1974 /* relase all the memory */
1975 GinBufferFree(buffer);
1976
1977 tuplesort_end(worker_sort);
1978 }
1979
1980 /*
1981 * Perform a worker's portion of a parallel GIN index build sort.
1982 *
1983 * This generates a tuplesort for the worker portion of the table.
1984 *
1985 * sortmem is the amount of working memory to use within each worker,
1986 * expressed in KBs.
1987 *
1988 * When this returns, workers are done, and need only release resources.
1989 *
1990 * Before feeding data into a shared tuplesort (for the leader process),
1991 * the workers process data in two phases.
1992 *
1993 * 1) A worker reads a portion of rows from the table, accumulates entries
1994 * in memory, and flushes them into a private tuplesort (e.g. because of
1995 * using too much memory).
1996 *
1997 * 2) The private tuplesort gets sorted (by key and TID), the worker reads
1998 * the data again, and combines the entries as much as possible. This has
1999 * to happen eventually, and this way it's done in workers in parallel.
2000 *
2001 * Finally, the combined entries are written into the shared tuplesort, so
2002 * that the leader can process them.
2003 *
2004 * How well this works (compared to just writing entries into the shared
2005 * tuplesort) depends on the data set. For large tables with many distinct
2006 * keys this helps a lot. With many distinct keys it's likely the buffers has
2007 * to be flushed often, generating many entries with the same key and short
2008 * TID lists. These entries need to be sorted and merged at some point,
2009 * before writing them to the index. The merging is quite expensive, it can
2010 * easily be ~50% of a serial build, and doing as much of it in the workers
2011 * means it's parallelized. The leader still has to merge results from the
2012 * workers, but it's much more efficient to merge few large entries than
2013 * many tiny ones.
2014 *
2015 * This also reduces the amount of data the workers pass to the leader through
2016 * the shared tuplesort. OTOH the workers need more space for the private sort,
2017 * possibly up to 2x of the data, if no entries be merged in a worker. But this
2018 * is very unlikely, and the only consequence is inefficiency, so we ignore it.
2019 */
2020 static void
2021 _gin_parallel_scan_and_build(GinBuildState *state,
2022 GinBuildShared *ginshared, Sharedsort *sharedsort,
2023 Relation heap, Relation index,
2024 int sortmem, bool progress)
2025 {
2026 SortCoordinate coordinate;
2027 TableScanDesc scan;
2028 double reltuples;
2029 IndexInfo *indexInfo;
2030
2031 /* Initialize local tuplesort coordination state */
2032 coordinate = palloc0(sizeof(SortCoordinateData));
2033 coordinate->isWorker = true;
2034 coordinate->nParticipants = -1;
2035 coordinate->sharedsort = sharedsort;
2036
2037 /* remember how much space is allowed for the accumulated entries */
2038 state->work_mem = (sortmem / 2);
2039
2040 /* remember how many workers participate in the build */
2041 state->bs_num_workers = ginshared->scantuplesortstates;
2042
2043 /* Begin "partial" tuplesort */
2044 state->bs_sortstate = tuplesort_begin_index_gin(heap, index,
2045 state->work_mem,
2046 coordinate,
2047 TUPLESORT_NONE);
2048
2049 /* Local per-worker sort of raw-data */
2050 state->bs_worker_sort = tuplesort_begin_index_gin(heap, index,
2051 state->work_mem,
2052 NULL,
2053 TUPLESORT_NONE);
2054
2055 /* Join parallel scan */
2056 indexInfo = BuildIndexInfo(index);
2057 indexInfo->ii_Concurrent = ginshared->isconcurrent;
2058
2059 scan = table_beginscan_parallel(heap,
2060 ParallelTableScanFromGinBuildShared(ginshared));
2061
2062 reltuples = table_index_build_scan(heap, index, indexInfo, true, progress,
2063 ginBuildCallbackParallel, state, scan);
2064
2065 /* write remaining accumulated entries */
2066 ginFlushBuildState(state, index);
2067
2068 /*
2069 * Do the first phase of in-worker processing - sort the data produced by
2070 * the callback, and combine them into much larger chunks and place that
2071 * into the shared tuplestore for leader to process.
2072 */
2073 _gin_process_worker_data(state, state->bs_worker_sort, progress);
2074
2075 /* sort the GIN tuples built by this worker */
2076 tuplesort_performsort(state->bs_sortstate);
2077
2078 state->bs_reltuples += reltuples;
2079
2080 /*
2081 * Done. Record ambuild statistics.
2082 */
2083 SpinLockAcquire(&ginshared->mutex);
2084 ginshared->nparticipantsdone++;
2085 ginshared->reltuples += state->bs_reltuples;
2086 ginshared->indtuples += state->bs_numtuples;
2087 SpinLockRelease(&ginshared->mutex);
2088
2089 /* Notify leader */
2090 ConditionVariableSignal(&ginshared->workersdonecv);
2091
2092 tuplesort_end(state->bs_sortstate);
2093 }
2094
2095 /*
2096 * Perform work within a launched parallel process.
2097 */
2098 void
2099 _gin_parallel_build_main(dsm_segment *seg, shm_toc *toc)
2100 {
2101 char *sharedquery;
2102 GinBuildShared *ginshared;
2103 Sharedsort *sharedsort;
2104 GinBuildState buildstate;
2105 Relation heapRel;
2106 Relation indexRel;
2107 LOCKMODE heapLockmode;
2108 LOCKMODE indexLockmode;
2109 WalUsage *walusage;
2110 BufferUsage *bufferusage;
2111 int sortmem;
2112
2113 /*
2114 * The only possible status flag that can be set to the parallel worker is
2115 * PROC_IN_SAFE_IC.
2116 */
2117 Assert((MyProc->statusFlags == 0) ||
2118 (MyProc->statusFlags == PROC_IN_SAFE_IC));
2119
2120 /* Set debug_query_string for individual workers first */
2121 sharedquery = shm_toc_lookup(toc, PARALLEL_KEY_QUERY_TEXT, true);
2122 debug_query_string = sharedquery;
2123
2124 /* Report the query string from leader */
2125 pgstat_report_activity(STATE_RUNNING, debug_query_string);
2126
2127 /* Look up gin shared state */
2128 ginshared = shm_toc_lookup(toc, PARALLEL_KEY_GIN_SHARED, false);
2129
2130 /* Open relations using lock modes known to be obtained by index.c */
2131 if (!ginshared->isconcurrent)
2132 {
2133 heapLockmode = ShareLock;
2134 indexLockmode = AccessExclusiveLock;
2135 }
2136 else
2137 {
2138 heapLockmode = ShareUpdateExclusiveLock;
2139 indexLockmode = RowExclusiveLock;
2140 }
2141
2142 /* Open relations within worker */
2143 heapRel = table_open(ginshared->heaprelid, heapLockmode);
2144 indexRel = index_open(ginshared->indexrelid, indexLockmode);
2145
2146 /* initialize the GIN build state */
2147 initGinState(&buildstate.ginstate, indexRel);
2148 buildstate.indtuples = 0;
2149
2150 /* Initialize counters used to report tuple counts to the leader */
2151 buildstate.bs_numtuples = 0;
2152 buildstate.bs_reltuples = 0;
2153
2154 memset(&buildstate.buildStats, 0, sizeof(GinStatsData));
2155 memset(&buildstate.tid, 0, sizeof(ItemPointerData));
2156
2157 /*
2158 * create a temporary memory context that is used to hold data not yet
2159 * dumped out to the index
2160 */
2161 buildstate.tmpCtx = AllocSetContextCreate(CurrentMemoryContext,
2162 "Gin build temporary context",
2163 ALLOCSET_DEFAULT_SIZES);
2164
2165 /*
2166 * create a temporary memory context that is used for calling
2167 * ginExtractEntries(), and can be reset after each tuple
2168 */
2169 buildstate.funcCtx = AllocSetContextCreate(CurrentMemoryContext,
2170 "Gin build temporary context for user-defined function",
2171 ALLOCSET_DEFAULT_SIZES);
2172
2173 buildstate.accum.ginstate = &buildstate.ginstate;
2174 ginInitBA(&buildstate.accum);
2175
2176
2177 /* Look up shared state private to tuplesort.c */
2178 sharedsort = shm_toc_lookup(toc, PARALLEL_KEY_TUPLESORT, false);
2179 tuplesort_attach_shared(sharedsort, seg);
2180
2181 /* Prepare to track buffer usage during parallel execution */
2182 InstrStartParallelQuery();
2183
2184 /*
2185 * Might as well use reliable figure when doling out maintenance_work_mem
2186 * (when requested number of workers were not launched, this will be
2187 * somewhat higher than it is for other workers).
2188 */
2189 sortmem = maintenance_work_mem / ginshared->scantuplesortstates;
2190
2191 _gin_parallel_scan_and_build(&buildstate, ginshared, sharedsort,
2192 heapRel, indexRel, sortmem, false);
2193
2194 /* Report WAL/buffer usage during parallel execution */
2195 bufferusage = shm_toc_lookup(toc, PARALLEL_KEY_BUFFER_USAGE, false);
2196 walusage = shm_toc_lookup(toc, PARALLEL_KEY_WAL_USAGE, false);
2197 InstrEndParallelQuery(&bufferusage[ParallelWorkerNumber],
2198 &walusage[ParallelWorkerNumber]);
2199
2200 index_close(indexRel, indexLockmode);
2201 table_close(heapRel, heapLockmode);
2202 }
2203
2204 /*
2205 * Used to keep track of compressed TID lists when building a GIN tuple.
2206 */
2207 typedef struct
2208 {
2209 dlist_node node; /* linked list pointers */
2210 GinPostingList *seg;
2211 } GinSegmentInfo;
2212
2213 /*
2214 * _gin_build_tuple
2215 * Serialize the state for an index key into a tuple for tuplesort.
2216 *
2217 * The tuple has a number of scalar fields (mostly matching the build state),
2218 * and then a data array that stores the key first, and then the TID list.
2219 *
2220 * For by-reference data types, we store the actual data. For by-val types
2221 * we simply copy the whole Datum, so that we don't have to care about stuff
2222 * like endianess etc. We could make it a little bit smaller, but it's not
2223 * worth it - it's a tiny fraction of the data, and we need to MAXALIGN the
2224 * start of the TID list anyway. So we wouldn't save anything.
2225 *
2226 * The TID list is serialized as compressed - it's highly compressible, and
2227 * we already have ginCompressPostingList for this purpose. The list may be
2228 * pretty long, so we compress it into multiple segments and then copy all
2229 * of that into the GIN tuple.
2230 */
2231 static GinTuple *
2232 _gin_build_tuple(OffsetNumber attrnum, unsigned char category,
2233 Datum key, int16 typlen, bool typbyval,
2234 ItemPointerData *items, uint32 nitems,
2235 Size *len)
2236 {
2237 GinTuple *tuple;
2238 char *ptr;
2239
2240 Size tuplen;
2241 int keylen;
2242
2243 dlist_mutable_iter iter;
2244 dlist_head segments;
2245 int ncompressed;
2246 Size compresslen;
2247
2248 /*
2249 * Calculate how long is the key value. Only keys with GIN_CAT_NORM_KEY
2250 * have actual non-empty key. We include varlena headers and \0 bytes for
2251 * strings, to make it easier to access the data in-line.
2252 *
2253 * For byval types we simply copy the whole Datum. We could store just the
2254 * necessary bytes, but this is simpler to work with and not worth the
2255 * extra complexity. Moreover we still need to do the MAXALIGN to allow
2256 * direct access to items pointers.
2257 *
2258 * XXX Note that for byval types we store the whole datum, no matter what
2259 * the typlen value is.
2260 */
2261 if (category != GIN_CAT_NORM_KEY)
2262 keylen = 0;
2263 else if (typbyval)
2264 keylen = sizeof(Datum);
2265 else if (typlen > 0)
2266 keylen = typlen;
2267 else if (typlen == -1)
2268 keylen = VARSIZE_ANY(key);
2269 else if (typlen == -2)
2270 keylen = strlen(DatumGetPointer(key)) + 1;
2271 else
2272 elog(ERROR, "unexpected typlen value (%d)", typlen);
2273
2274 /* compress the item pointers */
2275 ncompressed = 0;
2276 compresslen = 0;
2277 dlist_init(&segments);
2278
2279 /* generate compressed segments of TID list chunks */
2280 while (ncompressed < nitems)
2281 {
2282 int cnt;
2283 GinSegmentInfo *seginfo = palloc(sizeof(GinSegmentInfo));
2284
2285 seginfo->seg = ginCompressPostingList(&items[ncompressed],
2286 (nitems - ncompressed),
2287 UINT16_MAX,
2288 &cnt);
2289
2290 ncompressed += cnt;
2291 compresslen += SizeOfGinPostingList(seginfo->seg);
2292
2293 dlist_push_tail(&segments, &seginfo->node);
2294 }
2295
2296 /*
2297 * Determine GIN tuple length with all the data included. Be careful about
2298 * alignment, to allow direct access to compressed segments (those require
2299 * only SHORTALIGN).
2300 */
2301 tuplen = SHORTALIGN(offsetof(GinTuple, data) + keylen) + compresslen;
2302
2303 *len = tuplen;
2304
2305 /*
2306 * Allocate space for the whole GIN tuple.
2307 *
2308 * The palloc0 is needed - writetup_index_gin will write the whole tuple
2309 * to disk, so we need to make sure the padding bytes are defined
2310 * (otherwise valgrind would report this).
2311 */
2312 tuple = palloc0(tuplen);
2313
2314 tuple->tuplen = tuplen;
2315 tuple->attrnum = attrnum;
2316 tuple->category = category;
2317 tuple->keylen = keylen;
2318 tuple->nitems = nitems;
2319
2320 /* key type info */
2321 tuple->typlen = typlen;
2322 tuple->typbyval = typbyval;
2323
2324 /*
2325 * Copy the key and items into the tuple. First the key value, which we
2326 * can simply copy right at the beginning of the data array.
2327 */
2328 if (category == GIN_CAT_NORM_KEY)
2329 {
2330 if (typbyval)
2331 {
2332 memcpy(tuple->data, &key, sizeof(Datum));
2333 }
2334 else if (typlen > 0) /* byref, fixed length */
2335 {
2336 memcpy(tuple->data, DatumGetPointer(key), typlen);
2337 }
2338 else if (typlen == -1)
2339 {
2340 memcpy(tuple->data, DatumGetPointer(key), keylen);
2341 }
2342 else if (typlen == -2)
2343 {
2344 memcpy(tuple->data, DatumGetPointer(key), keylen);
2345 }
2346 }
2347
2348 /* finally, copy the TIDs into the array */
2349 ptr = (char *) tuple + SHORTALIGN(offsetof(GinTuple, data) + keylen);
2350
2351 /* copy in the compressed data, and free the segments */
2352 dlist_foreach_modify(iter, &segments)
2353 {
2354 GinSegmentInfo *seginfo = dlist_container(GinSegmentInfo, node, iter.cur);
2355
2356 memcpy(ptr, seginfo->seg, SizeOfGinPostingList(seginfo->seg));
2357
2358 ptr += SizeOfGinPostingList(seginfo->seg);
2359
2360 dlist_delete(&seginfo->node);
2361
2362 pfree(seginfo->seg);
2363 pfree(seginfo);
2364 }
2365
2366 return tuple;
2367 }
2368
2369 /*
2370 * _gin_parse_tuple_key
2371 * Return a Datum representing the key stored in the tuple.
2372 *
2373 * Most of the tuple fields are directly accessible, the only thing that
2374 * needs more care is the key and the TID list.
2375 *
2376 * For the key, this returns a regular Datum representing it. It's either the
2377 * actual key value, or a pointer to the beginning of the data array (which is
2378 * where the data was copied by _gin_build_tuple).
2379 */
2380 static Datum
2381 _gin_parse_tuple_key(GinTuple *a)
2382 {
2383 Datum key;
2384
2385 if (a->category != GIN_CAT_NORM_KEY)
2386 return (Datum) 0;
2387
2388 if (a->typbyval)
2389 {
2390 memcpy(&key, a->data, a->keylen);
2391 return key;
2392 }
2393
2394 return PointerGetDatum(a->data);
2395 }
2396
2397 /*
2398 * _gin_parse_tuple_items
2399 * Return a pointer to a palloc'd array of decompressed TID array.
2400 */
2401 static ItemPointer
2402 _gin_parse_tuple_items(GinTuple *a)
2403 {
2404 int len;
2405 char *ptr;
2406 int ndecoded;
2407 ItemPointer items;
2408
2409 len = a->tuplen - SHORTALIGN(offsetof(GinTuple, data) + a->keylen);
2410 ptr = (char *) a + SHORTALIGN(offsetof(GinTuple, data) + a->keylen);
2411
2412 items = ginPostingListDecodeAllSegments((GinPostingList *) ptr, len, &ndecoded);
2413
2414 Assert(ndecoded == a->nitems);
2415
2416 return (ItemPointer) items;
2417 }
2418
2419 /*
2420 * _gin_compare_tuples
2421 * Compare GIN tuples, used by tuplesort during parallel index build.
2422 *
2423 * The scalar fields (attrnum, category) are compared first, the key value is
2424 * compared last. The comparisons are done using type-specific sort support
2425 * functions.
2426 *
2427 * If the key value matches, we compare the first TID value in the TID list,
2428 * which means the tuples are merged in an order in which they are most
2429 * likely to be simply concatenated. (This "first" TID will also allow us
2430 * to determine a point up to which the list is fully determined and can be
2431 * written into the index to enforce a memory limit etc.)
2432 */
2433 int
2434 _gin_compare_tuples(GinTuple *a, GinTuple *b, SortSupport ssup)
2435 {
2436 int r;
2437 Datum keya,
2438 keyb;
2439
2440 if (a->attrnum < b->attrnum)
2441 return -1;
2442
2443 if (a->attrnum > b->attrnum)
2444 return 1;
2445
2446 if (a->category < b->category)
2447 return -1;
2448
2449 if (a->category > b->category)
2450 return 1;
2451
2452 if (a->category == GIN_CAT_NORM_KEY)
2453 {
2454 keya = _gin_parse_tuple_key(a);
2455 keyb = _gin_parse_tuple_key(b);
2456
2457 r = ApplySortComparator(keya, false,
2458 keyb, false,
2459 &ssup[a->attrnum - 1]);
2460
2461 /* if the key is the same, consider the first TID in the array */
2462 return (r != 0) ? r : ItemPointerCompare(GinTupleGetFirst(a),
2463 GinTupleGetFirst(b));
2464 }
2465
2466 return ItemPointerCompare(GinTupleGetFirst(a),
2467 GinTupleGetFirst(b));
2468 }