src/backend/access/gin/gininsert.c

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