| 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 |
} |