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