LCOV - code coverage report
Current view: top level - src/backend/access/gist - gist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 414 580 71.4 %
Date: 2025-04-02 03:15:43 Functions: 13 17 76.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * gist.c
       4             :  *    interface routines for the postgres GiST 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/gist/gist.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : #include "postgres.h"
      16             : 
      17             : #include "access/gist_private.h"
      18             : #include "access/gistscan.h"
      19             : #include "access/xloginsert.h"
      20             : #include "catalog/pg_collation.h"
      21             : #include "commands/vacuum.h"
      22             : #include "miscadmin.h"
      23             : #include "nodes/execnodes.h"
      24             : #include "storage/predicate.h"
      25             : #include "utils/fmgrprotos.h"
      26             : #include "utils/index_selfuncs.h"
      27             : #include "utils/memutils.h"
      28             : #include "utils/rel.h"
      29             : 
      30             : /* non-export function prototypes */
      31             : static void gistfixsplit(GISTInsertState *state, GISTSTATE *giststate);
      32             : static bool gistinserttuple(GISTInsertState *state, GISTInsertStack *stack,
      33             :                             GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum);
      34             : static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
      35             :                              GISTSTATE *giststate,
      36             :                              IndexTuple *tuples, int ntup, OffsetNumber oldoffnum,
      37             :                              Buffer leftchild, Buffer rightchild,
      38             :                              bool unlockbuf, bool unlockleftchild);
      39             : static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
      40             :                             GISTSTATE *giststate, List *splitinfo, bool unlockbuf);
      41             : static void gistprunepage(Relation rel, Page page, Buffer buffer,
      42             :                           Relation heapRel);
      43             : 
      44             : 
      45             : #define ROTATEDIST(d) do { \
      46             :     SplitPageLayout *tmp = (SplitPageLayout *) palloc0(sizeof(SplitPageLayout)); \
      47             :     tmp->block.blkno = InvalidBlockNumber;   \
      48             :     tmp->buffer = InvalidBuffer; \
      49             :     tmp->next = (d); \
      50             :     (d)=tmp; \
      51             : } while(0)
      52             : 
      53             : 
      54             : /*
      55             :  * GiST handler function: return IndexAmRoutine with access method parameters
      56             :  * and callbacks.
      57             :  */
      58             : Datum
      59       11970 : gisthandler(PG_FUNCTION_ARGS)
      60             : {
      61       11970 :     IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
      62             : 
      63       11970 :     amroutine->amstrategies = 0;
      64       11970 :     amroutine->amsupport = GISTNProcs;
      65       11970 :     amroutine->amoptsprocnum = GIST_OPTIONS_PROC;
      66       11970 :     amroutine->amcanorder = false;
      67       11970 :     amroutine->amcanorderbyop = true;
      68       11970 :     amroutine->amcanhash = false;
      69       11970 :     amroutine->amconsistentequality = false;
      70       11970 :     amroutine->amconsistentordering = false;
      71       11970 :     amroutine->amcanbackward = false;
      72       11970 :     amroutine->amcanunique = false;
      73       11970 :     amroutine->amcanmulticol = true;
      74       11970 :     amroutine->amoptionalkey = true;
      75       11970 :     amroutine->amsearcharray = false;
      76       11970 :     amroutine->amsearchnulls = true;
      77       11970 :     amroutine->amstorage = true;
      78       11970 :     amroutine->amclusterable = true;
      79       11970 :     amroutine->ampredlocks = true;
      80       11970 :     amroutine->amcanparallel = false;
      81       11970 :     amroutine->amcanbuildparallel = false;
      82       11970 :     amroutine->amcaninclude = true;
      83       11970 :     amroutine->amusemaintenanceworkmem = false;
      84       11970 :     amroutine->amsummarizing = false;
      85       11970 :     amroutine->amparallelvacuumoptions =
      86             :         VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP;
      87       11970 :     amroutine->amkeytype = InvalidOid;
      88             : 
      89       11970 :     amroutine->ambuild = gistbuild;
      90       11970 :     amroutine->ambuildempty = gistbuildempty;
      91       11970 :     amroutine->aminsert = gistinsert;
      92       11970 :     amroutine->aminsertcleanup = NULL;
      93       11970 :     amroutine->ambulkdelete = gistbulkdelete;
      94       11970 :     amroutine->amvacuumcleanup = gistvacuumcleanup;
      95       11970 :     amroutine->amcanreturn = gistcanreturn;
      96       11970 :     amroutine->amcostestimate = gistcostestimate;
      97       11970 :     amroutine->amgettreeheight = NULL;
      98       11970 :     amroutine->amoptions = gistoptions;
      99       11970 :     amroutine->amproperty = gistproperty;
     100       11970 :     amroutine->ambuildphasename = NULL;
     101       11970 :     amroutine->amvalidate = gistvalidate;
     102       11970 :     amroutine->amadjustmembers = gistadjustmembers;
     103       11970 :     amroutine->ambeginscan = gistbeginscan;
     104       11970 :     amroutine->amrescan = gistrescan;
     105       11970 :     amroutine->amgettuple = gistgettuple;
     106       11970 :     amroutine->amgetbitmap = gistgetbitmap;
     107       11970 :     amroutine->amendscan = gistendscan;
     108       11970 :     amroutine->ammarkpos = NULL;
     109       11970 :     amroutine->amrestrpos = NULL;
     110       11970 :     amroutine->amestimateparallelscan = NULL;
     111       11970 :     amroutine->aminitparallelscan = NULL;
     112       11970 :     amroutine->amparallelrescan = NULL;
     113       11970 :     amroutine->amtranslatestrategy = NULL;
     114       11970 :     amroutine->amtranslatecmptype = gisttranslatecmptype;
     115             : 
     116       11970 :     PG_RETURN_POINTER(amroutine);
     117             : }
     118             : 
     119             : /*
     120             :  * Create and return a temporary memory context for use by GiST. We
     121             :  * _always_ invoke user-provided methods in a temporary memory
     122             :  * context, so that memory leaks in those functions cannot cause
     123             :  * problems. Also, we use some additional temporary contexts in the
     124             :  * GiST code itself, to avoid the need to do some awkward manual
     125             :  * memory management.
     126             :  */
     127             : MemoryContext
     128        9564 : createTempGistContext(void)
     129             : {
     130        9564 :     return AllocSetContextCreate(CurrentMemoryContext,
     131             :                                  "GiST temporary context",
     132             :                                  ALLOCSET_DEFAULT_SIZES);
     133             : }
     134             : 
     135             : /*
     136             :  *  gistbuildempty() -- build an empty gist index in the initialization fork
     137             :  */
     138             : void
     139          10 : gistbuildempty(Relation index)
     140             : {
     141             :     Buffer      buffer;
     142             : 
     143             :     /* Initialize the root page */
     144          10 :     buffer = ExtendBufferedRel(BMR_REL(index), INIT_FORKNUM, NULL,
     145             :                                EB_SKIP_EXTENSION_LOCK | EB_LOCK_FIRST);
     146             : 
     147             :     /* Initialize and xlog buffer */
     148          10 :     START_CRIT_SECTION();
     149          10 :     GISTInitBuffer(buffer, F_LEAF);
     150          10 :     MarkBufferDirty(buffer);
     151          10 :     log_newpage_buffer(buffer, true);
     152          10 :     END_CRIT_SECTION();
     153             : 
     154             :     /* Unlock and release the buffer */
     155          10 :     UnlockReleaseBuffer(buffer);
     156          10 : }
     157             : 
     158             : /*
     159             :  *  gistinsert -- wrapper for GiST tuple insertion.
     160             :  *
     161             :  *    This is the public interface routine for tuple insertion in GiSTs.
     162             :  *    It doesn't do any work; just locks the relation and passes the buck.
     163             :  */
     164             : bool
     165      304330 : gistinsert(Relation r, Datum *values, bool *isnull,
     166             :            ItemPointer ht_ctid, Relation heapRel,
     167             :            IndexUniqueCheck checkUnique,
     168             :            bool indexUnchanged,
     169             :            IndexInfo *indexInfo)
     170             : {
     171      304330 :     GISTSTATE  *giststate = (GISTSTATE *) indexInfo->ii_AmCache;
     172             :     IndexTuple  itup;
     173             :     MemoryContext oldCxt;
     174             : 
     175             :     /* Initialize GISTSTATE cache if first call in this statement */
     176      304330 :     if (giststate == NULL)
     177             :     {
     178        1860 :         oldCxt = MemoryContextSwitchTo(indexInfo->ii_Context);
     179        1860 :         giststate = initGISTstate(r);
     180        1860 :         giststate->tempCxt = createTempGistContext();
     181        1860 :         indexInfo->ii_AmCache = giststate;
     182        1860 :         MemoryContextSwitchTo(oldCxt);
     183             :     }
     184             : 
     185      304330 :     oldCxt = MemoryContextSwitchTo(giststate->tempCxt);
     186             : 
     187      304330 :     itup = gistFormTuple(giststate, r, values, isnull, true);
     188      304328 :     itup->t_tid = *ht_ctid;
     189             : 
     190      304328 :     gistdoinsert(r, itup, 0, giststate, heapRel, false);
     191             : 
     192             :     /* cleanup */
     193      304316 :     MemoryContextSwitchTo(oldCxt);
     194      304316 :     MemoryContextReset(giststate->tempCxt);
     195             : 
     196      304316 :     return false;
     197             : }
     198             : 
     199             : 
     200             : /*
     201             :  * Place tuples from 'itup' to 'buffer'. If 'oldoffnum' is valid, the tuple
     202             :  * at that offset is atomically removed along with inserting the new tuples.
     203             :  * This is used to replace a tuple with a new one.
     204             :  *
     205             :  * If 'leftchildbuf' is valid, we're inserting the downlink for the page
     206             :  * to the right of 'leftchildbuf', or updating the downlink for 'leftchildbuf'.
     207             :  * F_FOLLOW_RIGHT flag on 'leftchildbuf' is cleared and NSN is set.
     208             :  *
     209             :  * If 'markfollowright' is true and the page is split, the left child is
     210             :  * marked with F_FOLLOW_RIGHT flag. That is the normal case. During buffered
     211             :  * index build, however, there is no concurrent access and the page splitting
     212             :  * is done in a slightly simpler fashion, and false is passed.
     213             :  *
     214             :  * If there is not enough room on the page, it is split. All the split
     215             :  * pages are kept pinned and locked and returned in *splitinfo, the caller
     216             :  * is responsible for inserting the downlinks for them. However, if
     217             :  * 'buffer' is the root page and it needs to be split, gistplacetopage()
     218             :  * performs the split as one atomic operation, and *splitinfo is set to NIL.
     219             :  * In that case, we continue to hold the root page locked, and the child
     220             :  * pages are released; note that new tuple(s) are *not* on the root page
     221             :  * but in one of the new child pages.
     222             :  *
     223             :  * If 'newblkno' is not NULL, returns the block number of page the first
     224             :  * new/updated tuple was inserted to. Usually it's the given page, but could
     225             :  * be its right sibling if the page was split.
     226             :  *
     227             :  * Returns 'true' if the page was split, 'false' otherwise.
     228             :  */
     229             : bool
     230     1749084 : gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate,
     231             :                 Buffer buffer,
     232             :                 IndexTuple *itup, int ntup, OffsetNumber oldoffnum,
     233             :                 BlockNumber *newblkno,
     234             :                 Buffer leftchildbuf,
     235             :                 List **splitinfo,
     236             :                 bool markfollowright,
     237             :                 Relation heapRel,
     238             :                 bool is_build)
     239             : {
     240     1749084 :     BlockNumber blkno = BufferGetBlockNumber(buffer);
     241     1749084 :     Page        page = BufferGetPage(buffer);
     242     1749084 :     bool        is_leaf = (GistPageIsLeaf(page)) ? true : false;
     243             :     XLogRecPtr  recptr;
     244             :     bool        is_split;
     245             : 
     246             :     /*
     247             :      * Refuse to modify a page that's incompletely split. This should not
     248             :      * happen because we finish any incomplete splits while we walk down the
     249             :      * tree. However, it's remotely possible that another concurrent inserter
     250             :      * splits a parent page, and errors out before completing the split. We
     251             :      * will just throw an error in that case, and leave any split we had in
     252             :      * progress unfinished too. The next insert that comes along will clean up
     253             :      * the mess.
     254             :      */
     255     1749084 :     if (GistFollowRight(page))
     256           0 :         elog(ERROR, "concurrent GiST page split was incomplete");
     257             : 
     258             :     /* should never try to insert to a deleted page */
     259             :     Assert(!GistPageIsDeleted(page));
     260             : 
     261     1749084 :     *splitinfo = NIL;
     262             : 
     263             :     /*
     264             :      * if isupdate, remove old key: This node's key has been modified, either
     265             :      * because a child split occurred or because we needed to adjust our key
     266             :      * for an insert in a child node. Therefore, remove the old version of
     267             :      * this node's key.
     268             :      *
     269             :      * for WAL replay, in the non-split case we handle this by setting up a
     270             :      * one-element todelete array; in the split case, it's handled implicitly
     271             :      * because the tuple vector passed to gistSplit won't include this tuple.
     272             :      */
     273     1749084 :     is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
     274             : 
     275             :     /*
     276             :      * If leaf page is full, try at first to delete dead tuples. And then
     277             :      * check again.
     278             :      */
     279     1749084 :     if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
     280             :     {
     281           0 :         gistprunepage(rel, page, buffer, heapRel);
     282           0 :         is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
     283             :     }
     284             : 
     285     1749084 :     if (is_split)
     286             :     {
     287             :         /* no space for insertion */
     288             :         IndexTuple *itvec;
     289             :         int         tlen;
     290       25272 :         SplitPageLayout *dist = NULL,
     291             :                    *ptr;
     292       25272 :         BlockNumber oldrlink = InvalidBlockNumber;
     293       25272 :         GistNSN     oldnsn = 0;
     294             :         SplitPageLayout rootpg;
     295             :         bool        is_rootsplit;
     296             :         int         npage;
     297             : 
     298       25272 :         is_rootsplit = (blkno == GIST_ROOT_BLKNO);
     299             : 
     300             :         /*
     301             :          * Form index tuples vector to split. If we're replacing an old tuple,
     302             :          * remove the old version from the vector.
     303             :          */
     304       25272 :         itvec = gistextractpage(page, &tlen);
     305       25272 :         if (OffsetNumberIsValid(oldoffnum))
     306             :         {
     307             :             /* on inner page we should remove old tuple */
     308        5078 :             int         pos = oldoffnum - FirstOffsetNumber;
     309             : 
     310        5078 :             tlen--;
     311        5078 :             if (pos != tlen)
     312        3258 :                 memmove(itvec + pos, itvec + pos + 1, sizeof(IndexTuple) * (tlen - pos));
     313             :         }
     314       25272 :         itvec = gistjoinvector(itvec, &tlen, itup, ntup);
     315       25272 :         dist = gistSplit(rel, page, itvec, tlen, giststate);
     316             : 
     317             :         /*
     318             :          * Check that split didn't produce too many pages.
     319             :          */
     320       25272 :         npage = 0;
     321       75878 :         for (ptr = dist; ptr; ptr = ptr->next)
     322       50606 :             npage++;
     323             :         /* in a root split, we'll add one more page to the list below */
     324       25272 :         if (is_rootsplit)
     325         408 :             npage++;
     326       25272 :         if (npage > GIST_MAX_SPLIT_PAGES)
     327           0 :             elog(ERROR, "GiST page split into too many halves (%d, maximum %d)",
     328             :                  npage, GIST_MAX_SPLIT_PAGES);
     329             : 
     330             :         /*
     331             :          * Set up pages to work with. Allocate new buffers for all but the
     332             :          * leftmost page. The original page becomes the new leftmost page, and
     333             :          * is just replaced with the new contents.
     334             :          *
     335             :          * For a root-split, allocate new buffers for all child pages, the
     336             :          * original page is overwritten with new root page containing
     337             :          * downlinks to the new child pages.
     338             :          */
     339       25272 :         ptr = dist;
     340       25272 :         if (!is_rootsplit)
     341             :         {
     342             :             /* save old rightlink and NSN */
     343       24864 :             oldrlink = GistPageGetOpaque(page)->rightlink;
     344       24864 :             oldnsn = GistPageGetNSN(page);
     345             : 
     346       24864 :             dist->buffer = buffer;
     347       24864 :             dist->block.blkno = BufferGetBlockNumber(buffer);
     348       24864 :             dist->page = PageGetTempPageCopySpecial(BufferGetPage(buffer));
     349             : 
     350             :             /* clean all flags except F_LEAF */
     351       24864 :             GistPageGetOpaque(dist->page)->flags = (is_leaf) ? F_LEAF : 0;
     352             : 
     353       24864 :             ptr = ptr->next;
     354             :         }
     355       51014 :         for (; ptr; ptr = ptr->next)
     356             :         {
     357             :             /* Allocate new page */
     358       25742 :             ptr->buffer = gistNewBuffer(rel, heapRel);
     359       25742 :             GISTInitBuffer(ptr->buffer, (is_leaf) ? F_LEAF : 0);
     360       25742 :             ptr->page = BufferGetPage(ptr->buffer);
     361       25742 :             ptr->block.blkno = BufferGetBlockNumber(ptr->buffer);
     362       25742 :             PredicateLockPageSplit(rel,
     363             :                                    BufferGetBlockNumber(buffer),
     364             :                                    BufferGetBlockNumber(ptr->buffer));
     365             :         }
     366             : 
     367             :         /*
     368             :          * Now that we know which blocks the new pages go to, set up downlink
     369             :          * tuples to point to them.
     370             :          */
     371       75878 :         for (ptr = dist; ptr; ptr = ptr->next)
     372             :         {
     373       50606 :             ItemPointerSetBlockNumber(&(ptr->itup->t_tid), ptr->block.blkno);
     374       50606 :             GistTupleSetValid(ptr->itup);
     375             :         }
     376             : 
     377             :         /*
     378             :          * If this is a root split, we construct the new root page with the
     379             :          * downlinks here directly, instead of requiring the caller to insert
     380             :          * them. Add the new root page to the list along with the child pages.
     381             :          */
     382       25272 :         if (is_rootsplit)
     383             :         {
     384             :             IndexTuple *downlinks;
     385         408 :             int         ndownlinks = 0;
     386             :             int         i;
     387             : 
     388         408 :             rootpg.buffer = buffer;
     389         408 :             rootpg.page = PageGetTempPageCopySpecial(BufferGetPage(rootpg.buffer));
     390         408 :             GistPageGetOpaque(rootpg.page)->flags = 0;
     391             : 
     392             :             /* Prepare a vector of all the downlinks */
     393        1230 :             for (ptr = dist; ptr; ptr = ptr->next)
     394         822 :                 ndownlinks++;
     395         408 :             downlinks = palloc(sizeof(IndexTuple) * ndownlinks);
     396        1230 :             for (i = 0, ptr = dist; ptr; ptr = ptr->next)
     397         822 :                 downlinks[i++] = ptr->itup;
     398             : 
     399         408 :             rootpg.block.blkno = GIST_ROOT_BLKNO;
     400         408 :             rootpg.block.num = ndownlinks;
     401         408 :             rootpg.list = gistfillitupvec(downlinks, ndownlinks,
     402             :                                           &(rootpg.lenlist));
     403         408 :             rootpg.itup = NULL;
     404             : 
     405         408 :             rootpg.next = dist;
     406         408 :             dist = &rootpg;
     407             :         }
     408             :         else
     409             :         {
     410             :             /* Prepare split-info to be returned to caller */
     411       74648 :             for (ptr = dist; ptr; ptr = ptr->next)
     412             :             {
     413       49784 :                 GISTPageSplitInfo *si = palloc(sizeof(GISTPageSplitInfo));
     414             : 
     415       49784 :                 si->buf = ptr->buffer;
     416       49784 :                 si->downlink = ptr->itup;
     417       49784 :                 *splitinfo = lappend(*splitinfo, si);
     418             :             }
     419             :         }
     420             : 
     421             :         /*
     422             :          * Fill all pages. All the pages are new, ie. freshly allocated empty
     423             :          * pages, or a temporary copy of the old page.
     424             :          */
     425       76286 :         for (ptr = dist; ptr; ptr = ptr->next)
     426             :         {
     427       51014 :             char       *data = (char *) (ptr->list);
     428             : 
     429     1905562 :             for (int i = 0; i < ptr->block.num; i++)
     430             :             {
     431     1854548 :                 IndexTuple  thistup = (IndexTuple) data;
     432             : 
     433     1854548 :                 if (PageAddItem(ptr->page, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
     434           0 :                     elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(rel));
     435             : 
     436             :                 /*
     437             :                  * If this is the first inserted/updated tuple, let the caller
     438             :                  * know which page it landed on.
     439             :                  */
     440     1854548 :                 if (newblkno && ItemPointerEquals(&thistup->t_tid, &(*itup)->t_tid))
     441         774 :                     *newblkno = ptr->block.blkno;
     442             : 
     443     1854548 :                 data += IndexTupleSize(thistup);
     444             :             }
     445             : 
     446             :             /* Set up rightlinks */
     447       51014 :             if (ptr->next && ptr->block.blkno != GIST_ROOT_BLKNO)
     448       50668 :                 GistPageGetOpaque(ptr->page)->rightlink =
     449       25334 :                     ptr->next->block.blkno;
     450             :             else
     451       25680 :                 GistPageGetOpaque(ptr->page)->rightlink = oldrlink;
     452             : 
     453             :             /*
     454             :              * Mark the all but the right-most page with the follow-right
     455             :              * flag. It will be cleared as soon as the downlink is inserted
     456             :              * into the parent, but this ensures that if we error out before
     457             :              * that, the index is still consistent. (in buffering build mode,
     458             :              * any error will abort the index build anyway, so this is not
     459             :              * needed.)
     460             :              */
     461       51014 :             if (ptr->next && !is_rootsplit && markfollowright)
     462       24152 :                 GistMarkFollowRight(ptr->page);
     463             :             else
     464       26862 :                 GistClearFollowRight(ptr->page);
     465             : 
     466             :             /*
     467             :              * Copy the NSN of the original page to all pages. The
     468             :              * F_FOLLOW_RIGHT flags ensure that scans will follow the
     469             :              * rightlinks until the downlinks are inserted.
     470             :              */
     471       51014 :             GistPageSetNSN(ptr->page, oldnsn);
     472             :         }
     473             : 
     474             :         /*
     475             :          * gistXLogSplit() needs to WAL log a lot of pages, prepare WAL
     476             :          * insertion for that. NB: The number of pages and data segments
     477             :          * specified here must match the calculations in gistXLogSplit()!
     478             :          */
     479       25272 :         if (!is_build && RelationNeedsWAL(rel))
     480        3472 :             XLogEnsureRecordSpace(npage, 1 + npage * 2);
     481             : 
     482       25272 :         START_CRIT_SECTION();
     483             : 
     484             :         /*
     485             :          * Must mark buffers dirty before XLogInsert, even though we'll still
     486             :          * be changing their opaque fields below.
     487             :          */
     488       76286 :         for (ptr = dist; ptr; ptr = ptr->next)
     489       51014 :             MarkBufferDirty(ptr->buffer);
     490       25272 :         if (BufferIsValid(leftchildbuf))
     491        4954 :             MarkBufferDirty(leftchildbuf);
     492             : 
     493             :         /*
     494             :          * The first page in the chain was a temporary working copy meant to
     495             :          * replace the old page. Copy it over the old page.
     496             :          */
     497       25272 :         PageRestoreTempPage(dist->page, BufferGetPage(dist->buffer));
     498       25272 :         dist->page = BufferGetPage(dist->buffer);
     499             : 
     500             :         /*
     501             :          * Write the WAL record.
     502             :          *
     503             :          * If we're building a new index, however, we don't WAL-log changes
     504             :          * yet. The LSN-NSN interlock between parent and child requires that
     505             :          * LSNs never move backwards, so set the LSNs to a value that's
     506             :          * smaller than any real or fake unlogged LSN that might be generated
     507             :          * later. (There can't be any concurrent scans during index build, so
     508             :          * we don't need to be able to detect concurrent splits yet.)
     509             :          */
     510       25272 :         if (is_build)
     511       21794 :             recptr = GistBuildLSN;
     512             :         else
     513             :         {
     514        3478 :             if (RelationNeedsWAL(rel))
     515        3472 :                 recptr = gistXLogSplit(is_leaf,
     516             :                                        dist, oldrlink, oldnsn, leftchildbuf,
     517             :                                        markfollowright);
     518             :             else
     519           6 :                 recptr = gistGetFakeLSN(rel);
     520             :         }
     521             : 
     522       76286 :         for (ptr = dist; ptr; ptr = ptr->next)
     523       51014 :             PageSetLSN(ptr->page, recptr);
     524             : 
     525             :         /*
     526             :          * Return the new child buffers to the caller.
     527             :          *
     528             :          * If this was a root split, we've already inserted the downlink
     529             :          * pointers, in the form of a new root page. Therefore we can release
     530             :          * all the new buffers, and keep just the root page locked.
     531             :          */
     532       25272 :         if (is_rootsplit)
     533             :         {
     534        1230 :             for (ptr = dist->next; ptr; ptr = ptr->next)
     535         822 :                 UnlockReleaseBuffer(ptr->buffer);
     536             :         }
     537             :     }
     538             :     else
     539             :     {
     540             :         /*
     541             :          * Enough space.  We always get here if ntup==0.
     542             :          */
     543     1723812 :         START_CRIT_SECTION();
     544             : 
     545             :         /*
     546             :          * Delete old tuple if any, then insert new tuple(s) if any.  If
     547             :          * possible, use the fast path of PageIndexTupleOverwrite.
     548             :          */
     549     1723812 :         if (OffsetNumberIsValid(oldoffnum))
     550             :         {
     551      759920 :             if (ntup == 1)
     552             :             {
     553             :                 /* One-for-one replacement, so use PageIndexTupleOverwrite */
     554      740028 :                 if (!PageIndexTupleOverwrite(page, oldoffnum, (Item) *itup,
     555             :                                              IndexTupleSize(*itup)))
     556           0 :                     elog(ERROR, "failed to add item to index page in \"%s\"",
     557             :                          RelationGetRelationName(rel));
     558             :             }
     559             :             else
     560             :             {
     561             :                 /* Delete old, then append new tuple(s) to page */
     562       19892 :                 PageIndexTupleDelete(page, oldoffnum);
     563       19892 :                 gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
     564             :             }
     565             :         }
     566             :         else
     567             :         {
     568             :             /* Just append new tuples at the end of the page */
     569      963892 :             gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
     570             :         }
     571             : 
     572     1723812 :         MarkBufferDirty(buffer);
     573             : 
     574     1723812 :         if (BufferIsValid(leftchildbuf))
     575       19198 :             MarkBufferDirty(leftchildbuf);
     576             : 
     577     1723812 :         if (is_build)
     578     1229172 :             recptr = GistBuildLSN;
     579             :         else
     580             :         {
     581      494640 :             if (RelationNeedsWAL(rel))
     582      494562 :             {
     583      494562 :                 OffsetNumber ndeloffs = 0,
     584             :                             deloffs[1];
     585             : 
     586      494562 :                 if (OffsetNumberIsValid(oldoffnum))
     587             :                 {
     588      193778 :                     deloffs[0] = oldoffnum;
     589      193778 :                     ndeloffs = 1;
     590             :                 }
     591             : 
     592      494562 :                 recptr = gistXLogUpdate(buffer,
     593             :                                         deloffs, ndeloffs, itup, ntup,
     594             :                                         leftchildbuf);
     595             :             }
     596             :             else
     597          78 :                 recptr = gistGetFakeLSN(rel);
     598             :         }
     599     1723812 :         PageSetLSN(page, recptr);
     600             : 
     601     1723812 :         if (newblkno)
     602      104370 :             *newblkno = blkno;
     603             :     }
     604             : 
     605             :     /*
     606             :      * If we inserted the downlink for a child page, set NSN and clear
     607             :      * F_FOLLOW_RIGHT flag on the left child, so that concurrent scans know to
     608             :      * follow the rightlink if and only if they looked at the parent page
     609             :      * before we inserted the downlink.
     610             :      *
     611             :      * Note that we do this *after* writing the WAL record. That means that
     612             :      * the possible full page image in the WAL record does not include these
     613             :      * changes, and they must be replayed even if the page is restored from
     614             :      * the full page image. There's a chicken-and-egg problem: if we updated
     615             :      * the child pages first, we wouldn't know the recptr of the WAL record
     616             :      * we're about to write.
     617             :      */
     618     1749084 :     if (BufferIsValid(leftchildbuf))
     619             :     {
     620       24152 :         Page        leftpg = BufferGetPage(leftchildbuf);
     621             : 
     622       24152 :         GistPageSetNSN(leftpg, recptr);
     623       24152 :         GistClearFollowRight(leftpg);
     624             : 
     625       24152 :         PageSetLSN(leftpg, recptr);
     626             :     }
     627             : 
     628     1749084 :     END_CRIT_SECTION();
     629             : 
     630     1749084 :     return is_split;
     631             : }
     632             : 
     633             : /*
     634             :  * Workhorse routine for doing insertion into a GiST index. Note that
     635             :  * this routine assumes it is invoked in a short-lived memory context,
     636             :  * so it does not bother releasing palloc'd allocations.
     637             :  */
     638             : void
     639      948612 : gistdoinsert(Relation r, IndexTuple itup, Size freespace,
     640             :              GISTSTATE *giststate, Relation heapRel, bool is_build)
     641             : {
     642             :     ItemId      iid;
     643             :     IndexTuple  idxtuple;
     644             :     GISTInsertStack firststack;
     645             :     GISTInsertStack *stack;
     646             :     GISTInsertState state;
     647      948612 :     bool        xlocked = false;
     648             : 
     649      948612 :     memset(&state, 0, sizeof(GISTInsertState));
     650      948612 :     state.freespace = freespace;
     651      948612 :     state.r = r;
     652      948612 :     state.heapRel = heapRel;
     653      948612 :     state.is_build = is_build;
     654             : 
     655             :     /* Start from the root */
     656      948612 :     firststack.blkno = GIST_ROOT_BLKNO;
     657      948612 :     firststack.lsn = 0;
     658      948612 :     firststack.retry_from_parent = false;
     659      948612 :     firststack.parent = NULL;
     660      948612 :     firststack.downlinkoffnum = InvalidOffsetNumber;
     661      948612 :     state.stack = stack = &firststack;
     662             : 
     663             :     /*
     664             :      * Walk down along the path of smallest penalty, updating the parent
     665             :      * pointers with the key we're inserting as we go. If we crash in the
     666             :      * middle, the tree is consistent, although the possible parent updates
     667             :      * were a waste.
     668             :      */
     669             :     for (;;)
     670             :     {
     671             :         /*
     672             :          * If we split an internal page while descending the tree, we have to
     673             :          * retry at the parent. (Normally, the LSN-NSN interlock below would
     674             :          * also catch this and cause us to retry. But LSNs are not updated
     675             :          * during index build.)
     676             :          */
     677     2133826 :         while (stack->retry_from_parent)
     678             :         {
     679         140 :             if (xlocked)
     680           0 :                 LockBuffer(stack->buffer, GIST_UNLOCK);
     681         140 :             xlocked = false;
     682         140 :             ReleaseBuffer(stack->buffer);
     683         140 :             state.stack = stack = stack->parent;
     684             :         }
     685             : 
     686     2133686 :         if (XLogRecPtrIsInvalid(stack->lsn))
     687     2133580 :             stack->buffer = ReadBuffer(state.r, stack->blkno);
     688             : 
     689             :         /*
     690             :          * Be optimistic and grab shared lock first. Swap it for an exclusive
     691             :          * lock later if we need to update the page.
     692             :          */
     693     2133686 :         if (!xlocked)
     694             :         {
     695     2133684 :             LockBuffer(stack->buffer, GIST_SHARE);
     696     2133684 :             gistcheckpage(state.r, stack->buffer);
     697             :         }
     698             : 
     699     2133686 :         stack->page = (Page) BufferGetPage(stack->buffer);
     700     2133686 :         stack->lsn = xlocked ?
     701     2133686 :             PageGetLSN(stack->page) : BufferGetLSNAtomic(stack->buffer);
     702             :         Assert(!RelationNeedsWAL(state.r) || !XLogRecPtrIsInvalid(stack->lsn));
     703             : 
     704             :         /*
     705             :          * If this page was split but the downlink was never inserted to the
     706             :          * parent because the inserting backend crashed before doing that, fix
     707             :          * that now.
     708             :          */
     709     2133686 :         if (GistFollowRight(stack->page))
     710             :         {
     711           0 :             if (!xlocked)
     712             :             {
     713           0 :                 LockBuffer(stack->buffer, GIST_UNLOCK);
     714           0 :                 LockBuffer(stack->buffer, GIST_EXCLUSIVE);
     715           0 :                 xlocked = true;
     716             :                 /* someone might've completed the split when we unlocked */
     717           0 :                 if (!GistFollowRight(stack->page))
     718           0 :                     continue;
     719             :             }
     720           0 :             gistfixsplit(&state, giststate);
     721             : 
     722           0 :             UnlockReleaseBuffer(stack->buffer);
     723           0 :             xlocked = false;
     724           0 :             state.stack = stack = stack->parent;
     725           0 :             continue;
     726             :         }
     727             : 
     728     3318684 :         if ((stack->blkno != GIST_ROOT_BLKNO &&
     729     1184998 :              stack->parent->lsn < GistPageGetNSN(stack->page)) ||
     730     2133686 :             GistPageIsDeleted(stack->page))
     731             :         {
     732             :             /*
     733             :              * Concurrent split or page deletion detected. There's no
     734             :              * guarantee that the downlink for this page is consistent with
     735             :              * the tuple we're inserting anymore, so go back to parent and
     736             :              * rechoose the best child.
     737             :              */
     738           0 :             UnlockReleaseBuffer(stack->buffer);
     739           0 :             xlocked = false;
     740           0 :             state.stack = stack = stack->parent;
     741           0 :             continue;
     742             :         }
     743             : 
     744     2133686 :         if (!GistPageIsLeaf(stack->page))
     745             :         {
     746             :             /*
     747             :              * This is an internal page so continue to walk down the tree.
     748             :              * Find the child node that has the minimum insertion penalty.
     749             :              */
     750             :             BlockNumber childblkno;
     751             :             IndexTuple  newtup;
     752             :             GISTInsertStack *item;
     753             :             OffsetNumber downlinkoffnum;
     754             : 
     755     1185074 :             downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
     756     1185074 :             iid = PageGetItemId(stack->page, downlinkoffnum);
     757     1185074 :             idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
     758     1185074 :             childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
     759             : 
     760             :             /*
     761             :              * Check that it's not a leftover invalid tuple from pre-9.1
     762             :              */
     763     1185074 :             if (GistTupleIsInvalid(idxtuple))
     764           0 :                 ereport(ERROR,
     765             :                         (errmsg("index \"%s\" contains an inner tuple marked as invalid",
     766             :                                 RelationGetRelationName(r)),
     767             :                          errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
     768             :                          errhint("Please REINDEX it.")));
     769             : 
     770             :             /*
     771             :              * Check that the key representing the target child node is
     772             :              * consistent with the key we're inserting. Update it if it's not.
     773             :              */
     774     1185074 :             newtup = gistgetadjusted(state.r, idxtuple, itup, giststate);
     775     1185074 :             if (newtup)
     776             :             {
     777             :                 /*
     778             :                  * Swap shared lock for an exclusive one. Beware, the page may
     779             :                  * change while we unlock/lock the page...
     780             :                  */
     781      671188 :                 if (!xlocked)
     782             :                 {
     783      671188 :                     LockBuffer(stack->buffer, GIST_UNLOCK);
     784      671188 :                     LockBuffer(stack->buffer, GIST_EXCLUSIVE);
     785      671188 :                     xlocked = true;
     786      671188 :                     stack->page = (Page) BufferGetPage(stack->buffer);
     787             : 
     788      671188 :                     if (PageGetLSN(stack->page) != stack->lsn)
     789             :                     {
     790             :                         /* the page was changed while we unlocked it, retry */
     791           0 :                         continue;
     792             :                     }
     793             :                 }
     794             : 
     795             :                 /*
     796             :                  * Update the tuple.
     797             :                  *
     798             :                  * We still hold the lock after gistinserttuple(), but it
     799             :                  * might have to split the page to make the updated tuple fit.
     800             :                  * In that case the updated tuple might migrate to the other
     801             :                  * half of the split, so we have to go back to the parent and
     802             :                  * descend back to the half that's a better fit for the new
     803             :                  * tuple.
     804             :                  */
     805      671188 :                 if (gistinserttuple(&state, stack, giststate, newtup,
     806             :                                     downlinkoffnum))
     807             :                 {
     808             :                     /*
     809             :                      * If this was a root split, the root page continues to be
     810             :                      * the parent and the updated tuple went to one of the
     811             :                      * child pages, so we just need to retry from the root
     812             :                      * page.
     813             :                      */
     814         106 :                     if (stack->blkno != GIST_ROOT_BLKNO)
     815             :                     {
     816         104 :                         UnlockReleaseBuffer(stack->buffer);
     817         104 :                         xlocked = false;
     818         104 :                         state.stack = stack = stack->parent;
     819             :                     }
     820         106 :                     continue;
     821             :                 }
     822             :             }
     823     1184968 :             LockBuffer(stack->buffer, GIST_UNLOCK);
     824     1184968 :             xlocked = false;
     825             : 
     826             :             /* descend to the chosen child */
     827     1184968 :             item = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
     828     1184968 :             item->blkno = childblkno;
     829     1184968 :             item->parent = stack;
     830     1184968 :             item->downlinkoffnum = downlinkoffnum;
     831     1184968 :             state.stack = stack = item;
     832             :         }
     833             :         else
     834             :         {
     835             :             /*
     836             :              * Leaf page. Insert the new key. We've already updated all the
     837             :              * parents on the way down, but we might have to split the page if
     838             :              * it doesn't fit. gistinserttuple() will take care of that.
     839             :              */
     840             : 
     841             :             /*
     842             :              * Swap shared lock for an exclusive one. Be careful, the page may
     843             :              * change while we unlock/lock the page...
     844             :              */
     845      948612 :             if (!xlocked)
     846             :             {
     847      948612 :                 LockBuffer(stack->buffer, GIST_UNLOCK);
     848      948612 :                 LockBuffer(stack->buffer, GIST_EXCLUSIVE);
     849      948612 :                 xlocked = true;
     850      948612 :                 stack->page = (Page) BufferGetPage(stack->buffer);
     851      948612 :                 stack->lsn = PageGetLSN(stack->page);
     852             : 
     853      948612 :                 if (stack->blkno == GIST_ROOT_BLKNO)
     854             :                 {
     855             :                     /*
     856             :                      * the only page that can become inner instead of leaf is
     857             :                      * the root page, so for root we should recheck it
     858             :                      */
     859       55284 :                     if (!GistPageIsLeaf(stack->page))
     860             :                     {
     861             :                         /*
     862             :                          * very rare situation: during unlock/lock index with
     863             :                          * number of pages = 1 was increased
     864             :                          */
     865           0 :                         LockBuffer(stack->buffer, GIST_UNLOCK);
     866           0 :                         xlocked = false;
     867           0 :                         continue;
     868             :                     }
     869             : 
     870             :                     /*
     871             :                      * we don't need to check root split, because checking
     872             :                      * leaf/inner is enough to recognize split for root
     873             :                      */
     874             :                 }
     875     1786656 :                 else if ((GistFollowRight(stack->page) ||
     876      893328 :                           stack->parent->lsn < GistPageGetNSN(stack->page)) ||
     877      893328 :                          GistPageIsDeleted(stack->page))
     878             :                 {
     879             :                     /*
     880             :                      * The page was split or deleted while we momentarily
     881             :                      * unlocked the page. Go back to parent.
     882             :                      */
     883           0 :                     UnlockReleaseBuffer(stack->buffer);
     884           0 :                     xlocked = false;
     885           0 :                     state.stack = stack = stack->parent;
     886           0 :                     continue;
     887             :                 }
     888             :             }
     889             : 
     890             :             /* now state.stack->(page, buffer and blkno) points to leaf page */
     891             : 
     892      948612 :             gistinserttuple(&state, stack, giststate, itup,
     893             :                             InvalidOffsetNumber);
     894      948600 :             LockBuffer(stack->buffer, GIST_UNLOCK);
     895             : 
     896             :             /* Release any pins we might still hold before exiting */
     897     3081912 :             for (; stack; stack = stack->parent)
     898     2133312 :                 ReleaseBuffer(stack->buffer);
     899      948600 :             break;
     900             :         }
     901             :     }
     902      948600 : }
     903             : 
     904             : /*
     905             :  * Traverse the tree to find path from root page to specified "child" block.
     906             :  *
     907             :  * returns a new insertion stack, starting from the parent of "child", up
     908             :  * to the root. *downlinkoffnum is set to the offset of the downlink in the
     909             :  * direct parent of child.
     910             :  *
     911             :  * To prevent deadlocks, this should lock only one page at a time.
     912             :  */
     913             : static GISTInsertStack *
     914           0 : gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
     915             : {
     916             :     Page        page;
     917             :     Buffer      buffer;
     918             :     OffsetNumber i,
     919             :                 maxoff;
     920             :     ItemId      iid;
     921             :     IndexTuple  idxtuple;
     922             :     List       *fifo;
     923             :     GISTInsertStack *top,
     924             :                *ptr;
     925             :     BlockNumber blkno;
     926             : 
     927           0 :     top = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
     928           0 :     top->blkno = GIST_ROOT_BLKNO;
     929           0 :     top->downlinkoffnum = InvalidOffsetNumber;
     930             : 
     931           0 :     fifo = list_make1(top);
     932           0 :     while (fifo != NIL)
     933             :     {
     934             :         /* Get next page to visit */
     935           0 :         top = linitial(fifo);
     936           0 :         fifo = list_delete_first(fifo);
     937             : 
     938           0 :         buffer = ReadBuffer(r, top->blkno);
     939           0 :         LockBuffer(buffer, GIST_SHARE);
     940           0 :         gistcheckpage(r, buffer);
     941           0 :         page = (Page) BufferGetPage(buffer);
     942             : 
     943           0 :         if (GistPageIsLeaf(page))
     944             :         {
     945             :             /*
     946             :              * Because we scan the index top-down, all the rest of the pages
     947             :              * in the queue must be leaf pages as well.
     948             :              */
     949           0 :             UnlockReleaseBuffer(buffer);
     950           0 :             break;
     951             :         }
     952             : 
     953             :         /* currently, internal pages are never deleted */
     954             :         Assert(!GistPageIsDeleted(page));
     955             : 
     956           0 :         top->lsn = BufferGetLSNAtomic(buffer);
     957             : 
     958             :         /*
     959             :          * If F_FOLLOW_RIGHT is set, the page to the right doesn't have a
     960             :          * downlink. This should not normally happen..
     961             :          */
     962           0 :         if (GistFollowRight(page))
     963           0 :             elog(ERROR, "concurrent GiST page split was incomplete");
     964             : 
     965           0 :         if (top->parent && top->parent->lsn < GistPageGetNSN(page) &&
     966           0 :             GistPageGetOpaque(page)->rightlink != InvalidBlockNumber /* sanity check */ )
     967             :         {
     968             :             /*
     969             :              * Page was split while we looked elsewhere. We didn't see the
     970             :              * downlink to the right page when we scanned the parent, so add
     971             :              * it to the queue now.
     972             :              *
     973             :              * Put the right page ahead of the queue, so that we visit it
     974             :              * next. That's important, because if this is the lowest internal
     975             :              * level, just above leaves, we might already have queued up some
     976             :              * leaf pages, and we assume that there can't be any non-leaf
     977             :              * pages behind leaf pages.
     978             :              */
     979           0 :             ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
     980           0 :             ptr->blkno = GistPageGetOpaque(page)->rightlink;
     981           0 :             ptr->downlinkoffnum = InvalidOffsetNumber;
     982           0 :             ptr->parent = top->parent;
     983             : 
     984           0 :             fifo = lcons(ptr, fifo);
     985             :         }
     986             : 
     987           0 :         maxoff = PageGetMaxOffsetNumber(page);
     988             : 
     989           0 :         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
     990             :         {
     991           0 :             iid = PageGetItemId(page, i);
     992           0 :             idxtuple = (IndexTuple) PageGetItem(page, iid);
     993           0 :             blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
     994           0 :             if (blkno == child)
     995             :             {
     996             :                 /* Found it! */
     997           0 :                 UnlockReleaseBuffer(buffer);
     998           0 :                 *downlinkoffnum = i;
     999           0 :                 return top;
    1000             :             }
    1001             :             else
    1002             :             {
    1003             :                 /* Append this child to the list of pages to visit later */
    1004           0 :                 ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
    1005           0 :                 ptr->blkno = blkno;
    1006           0 :                 ptr->downlinkoffnum = i;
    1007           0 :                 ptr->parent = top;
    1008             : 
    1009           0 :                 fifo = lappend(fifo, ptr);
    1010             :             }
    1011             :         }
    1012             : 
    1013           0 :         UnlockReleaseBuffer(buffer);
    1014             :     }
    1015             : 
    1016           0 :     elog(ERROR, "failed to re-find parent of a page in index \"%s\", block %u",
    1017             :          RelationGetRelationName(r), child);
    1018             :     return NULL;                /* keep compiler quiet */
    1019             : }
    1020             : 
    1021             : /*
    1022             :  * Updates the stack so that child->parent is the correct parent of the
    1023             :  * child. child->parent must be exclusively locked on entry, and will
    1024             :  * remain so at exit, but it might not be the same page anymore.
    1025             :  */
    1026             : static void
    1027       24152 : gistFindCorrectParent(Relation r, GISTInsertStack *child, bool is_build)
    1028             : {
    1029       24152 :     GISTInsertStack *parent = child->parent;
    1030             :     ItemId      iid;
    1031             :     IndexTuple  idxtuple;
    1032             :     OffsetNumber maxoff;
    1033             :     GISTInsertStack *ptr;
    1034             : 
    1035       24152 :     gistcheckpage(r, parent->buffer);
    1036       24152 :     parent->page = (Page) BufferGetPage(parent->buffer);
    1037       24152 :     maxoff = PageGetMaxOffsetNumber(parent->page);
    1038             : 
    1039             :     /* Check if the downlink is still where it was before */
    1040       24152 :     if (child->downlinkoffnum != InvalidOffsetNumber && child->downlinkoffnum <= maxoff)
    1041             :     {
    1042       24152 :         iid = PageGetItemId(parent->page, child->downlinkoffnum);
    1043       24152 :         idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
    1044       24152 :         if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
    1045       24152 :             return;             /* still there */
    1046             :     }
    1047             : 
    1048             :     /*
    1049             :      * The page has changed since we looked. During normal operation, every
    1050             :      * update of a page changes its LSN, so the LSN we memorized should have
    1051             :      * changed too. During index build, however, we don't WAL-log the changes
    1052             :      * until we have built the index, so the LSN doesn't change. There is no
    1053             :      * concurrent activity during index build, but we might have changed the
    1054             :      * parent ourselves.
    1055             :      */
    1056             :     Assert(parent->lsn != PageGetLSN(parent->page) || is_build);
    1057             : 
    1058             :     /*
    1059             :      * Scan the page to re-find the downlink. If the page was split, it might
    1060             :      * have moved to a different page, so follow the right links until we find
    1061             :      * it.
    1062             :      */
    1063             :     while (true)
    1064           0 :     {
    1065             :         OffsetNumber i;
    1066             : 
    1067           0 :         maxoff = PageGetMaxOffsetNumber(parent->page);
    1068           0 :         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
    1069             :         {
    1070           0 :             iid = PageGetItemId(parent->page, i);
    1071           0 :             idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
    1072           0 :             if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
    1073             :             {
    1074             :                 /* yes!!, found */
    1075           0 :                 child->downlinkoffnum = i;
    1076           0 :                 return;
    1077             :             }
    1078             :         }
    1079             : 
    1080           0 :         parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
    1081           0 :         parent->downlinkoffnum = InvalidOffsetNumber;
    1082           0 :         UnlockReleaseBuffer(parent->buffer);
    1083           0 :         if (parent->blkno == InvalidBlockNumber)
    1084             :         {
    1085             :             /*
    1086             :              * End of chain and still didn't find parent. It's a very-very
    1087             :              * rare situation when the root was split.
    1088             :              */
    1089           0 :             break;
    1090             :         }
    1091           0 :         parent->buffer = ReadBuffer(r, parent->blkno);
    1092           0 :         LockBuffer(parent->buffer, GIST_EXCLUSIVE);
    1093           0 :         gistcheckpage(r, parent->buffer);
    1094           0 :         parent->page = (Page) BufferGetPage(parent->buffer);
    1095             :     }
    1096             : 
    1097             :     /*
    1098             :      * awful!!, we need search tree to find parent ... , but before we should
    1099             :      * release all old parent
    1100             :      */
    1101             : 
    1102           0 :     ptr = child->parent->parent;  /* child->parent already released above */
    1103           0 :     while (ptr)
    1104             :     {
    1105           0 :         ReleaseBuffer(ptr->buffer);
    1106           0 :         ptr = ptr->parent;
    1107             :     }
    1108             : 
    1109             :     /* ok, find new path */
    1110           0 :     ptr = parent = gistFindPath(r, child->blkno, &child->downlinkoffnum);
    1111             : 
    1112             :     /* read all buffers as expected by caller */
    1113             :     /* note we don't lock them or gistcheckpage them here! */
    1114           0 :     while (ptr)
    1115             :     {
    1116           0 :         ptr->buffer = ReadBuffer(r, ptr->blkno);
    1117           0 :         ptr->page = (Page) BufferGetPage(ptr->buffer);
    1118           0 :         ptr = ptr->parent;
    1119             :     }
    1120             : 
    1121             :     /* install new chain of parents to stack */
    1122           0 :     child->parent = parent;
    1123             : 
    1124             :     /* make recursive call to normal processing */
    1125           0 :     LockBuffer(child->parent->buffer, GIST_EXCLUSIVE);
    1126           0 :     gistFindCorrectParent(r, child, is_build);
    1127             : }
    1128             : 
    1129             : /*
    1130             :  * Form a downlink pointer for the page in 'buf'.
    1131             :  */
    1132             : static IndexTuple
    1133           0 : gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate,
    1134             :                  GISTInsertStack *stack, bool is_build)
    1135             : {
    1136           0 :     Page        page = BufferGetPage(buf);
    1137             :     OffsetNumber maxoff;
    1138             :     OffsetNumber offset;
    1139           0 :     IndexTuple  downlink = NULL;
    1140             : 
    1141           0 :     maxoff = PageGetMaxOffsetNumber(page);
    1142           0 :     for (offset = FirstOffsetNumber; offset <= maxoff; offset = OffsetNumberNext(offset))
    1143             :     {
    1144             :         IndexTuple  ituple = (IndexTuple)
    1145           0 :             PageGetItem(page, PageGetItemId(page, offset));
    1146             : 
    1147           0 :         if (downlink == NULL)
    1148           0 :             downlink = CopyIndexTuple(ituple);
    1149             :         else
    1150             :         {
    1151             :             IndexTuple  newdownlink;
    1152             : 
    1153           0 :             newdownlink = gistgetadjusted(rel, downlink, ituple,
    1154             :                                           giststate);
    1155           0 :             if (newdownlink)
    1156           0 :                 downlink = newdownlink;
    1157             :         }
    1158             :     }
    1159             : 
    1160             :     /*
    1161             :      * If the page is completely empty, we can't form a meaningful downlink
    1162             :      * for it. But we have to insert a downlink for the page. Any key will do,
    1163             :      * as long as its consistent with the downlink of parent page, so that we
    1164             :      * can legally insert it to the parent. A minimal one that matches as few
    1165             :      * scans as possible would be best, to keep scans from doing useless work,
    1166             :      * but we don't know how to construct that. So we just use the downlink of
    1167             :      * the original page that was split - that's as far from optimal as it can
    1168             :      * get but will do..
    1169             :      */
    1170           0 :     if (!downlink)
    1171             :     {
    1172             :         ItemId      iid;
    1173             : 
    1174           0 :         LockBuffer(stack->parent->buffer, GIST_EXCLUSIVE);
    1175           0 :         gistFindCorrectParent(rel, stack, is_build);
    1176           0 :         iid = PageGetItemId(stack->parent->page, stack->downlinkoffnum);
    1177           0 :         downlink = (IndexTuple) PageGetItem(stack->parent->page, iid);
    1178           0 :         downlink = CopyIndexTuple(downlink);
    1179           0 :         LockBuffer(stack->parent->buffer, GIST_UNLOCK);
    1180             :     }
    1181             : 
    1182           0 :     ItemPointerSetBlockNumber(&(downlink->t_tid), BufferGetBlockNumber(buf));
    1183           0 :     GistTupleSetValid(downlink);
    1184             : 
    1185           0 :     return downlink;
    1186             : }
    1187             : 
    1188             : 
    1189             : /*
    1190             :  * Complete the incomplete split of state->stack->page.
    1191             :  */
    1192             : static void
    1193           0 : gistfixsplit(GISTInsertState *state, GISTSTATE *giststate)
    1194             : {
    1195           0 :     GISTInsertStack *stack = state->stack;
    1196             :     Buffer      buf;
    1197             :     Page        page;
    1198           0 :     List       *splitinfo = NIL;
    1199             : 
    1200           0 :     ereport(LOG,
    1201             :             (errmsg("fixing incomplete split in index \"%s\", block %u",
    1202             :                     RelationGetRelationName(state->r), stack->blkno)));
    1203             : 
    1204             :     Assert(GistFollowRight(stack->page));
    1205             :     Assert(OffsetNumberIsValid(stack->downlinkoffnum));
    1206             : 
    1207           0 :     buf = stack->buffer;
    1208             : 
    1209             :     /*
    1210             :      * Read the chain of split pages, following the rightlinks. Construct a
    1211             :      * downlink tuple for each page.
    1212             :      */
    1213             :     for (;;)
    1214           0 :     {
    1215           0 :         GISTPageSplitInfo *si = palloc(sizeof(GISTPageSplitInfo));
    1216             :         IndexTuple  downlink;
    1217             : 
    1218           0 :         page = BufferGetPage(buf);
    1219             : 
    1220             :         /* Form the new downlink tuples to insert to parent */
    1221           0 :         downlink = gistformdownlink(state->r, buf, giststate, stack, state->is_build);
    1222             : 
    1223           0 :         si->buf = buf;
    1224           0 :         si->downlink = downlink;
    1225             : 
    1226           0 :         splitinfo = lappend(splitinfo, si);
    1227             : 
    1228           0 :         if (GistFollowRight(page))
    1229             :         {
    1230             :             /* lock next page */
    1231           0 :             buf = ReadBuffer(state->r, GistPageGetOpaque(page)->rightlink);
    1232           0 :             LockBuffer(buf, GIST_EXCLUSIVE);
    1233             :         }
    1234             :         else
    1235           0 :             break;
    1236             :     }
    1237             : 
    1238             :     /* Insert the downlinks */
    1239           0 :     gistfinishsplit(state, stack, giststate, splitinfo, false);
    1240           0 : }
    1241             : 
    1242             : /*
    1243             :  * Insert or replace a tuple in stack->buffer. If 'oldoffnum' is valid, the
    1244             :  * tuple at 'oldoffnum' is replaced, otherwise the tuple is inserted as new.
    1245             :  * 'stack' represents the path from the root to the page being updated.
    1246             :  *
    1247             :  * The caller must hold an exclusive lock on stack->buffer.  The lock is still
    1248             :  * held on return, but the page might not contain the inserted tuple if the
    1249             :  * page was split. The function returns true if the page was split, false
    1250             :  * otherwise.
    1251             :  */
    1252             : static bool
    1253     1619800 : gistinserttuple(GISTInsertState *state, GISTInsertStack *stack,
    1254             :                 GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum)
    1255             : {
    1256     1619800 :     return gistinserttuples(state, stack, giststate, &tuple, 1, oldoffnum,
    1257             :                             InvalidBuffer, InvalidBuffer, false, false);
    1258             : }
    1259             : 
    1260             : /* ----------------
    1261             :  * An extended workhorse version of gistinserttuple(). This version allows
    1262             :  * inserting multiple tuples, or replacing a single tuple with multiple tuples.
    1263             :  * This is used to recursively update the downlinks in the parent when a page
    1264             :  * is split.
    1265             :  *
    1266             :  * If leftchild and rightchild are valid, we're inserting/replacing the
    1267             :  * downlink for rightchild, and leftchild is its left sibling. We clear the
    1268             :  * F_FOLLOW_RIGHT flag and update NSN on leftchild, atomically with the
    1269             :  * insertion of the downlink.
    1270             :  *
    1271             :  * To avoid holding locks for longer than necessary, when recursing up the
    1272             :  * tree to update the parents, the locking is a bit peculiar here. On entry,
    1273             :  * the caller must hold an exclusive lock on stack->buffer, as well as
    1274             :  * leftchild and rightchild if given. On return:
    1275             :  *
    1276             :  *  - Lock on stack->buffer is released, if 'unlockbuf' is true. The page is
    1277             :  *    always kept pinned, however.
    1278             :  *  - Lock on 'leftchild' is released, if 'unlockleftchild' is true. The page
    1279             :  *    is kept pinned.
    1280             :  *  - Lock and pin on 'rightchild' are always released.
    1281             :  *
    1282             :  * Returns 'true' if the page had to be split. Note that if the page was
    1283             :  * split, the inserted/updated tuples might've been inserted to a right
    1284             :  * sibling of stack->buffer instead of stack->buffer itself.
    1285             :  */
    1286             : static bool
    1287     1643952 : gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
    1288             :                  GISTSTATE *giststate,
    1289             :                  IndexTuple *tuples, int ntup, OffsetNumber oldoffnum,
    1290             :                  Buffer leftchild, Buffer rightchild,
    1291             :                  bool unlockbuf, bool unlockleftchild)
    1292             : {
    1293             :     List       *splitinfo;
    1294             :     bool        is_split;
    1295             : 
    1296             :     /*
    1297             :      * Check for any rw conflicts (in serializable isolation level) just
    1298             :      * before we intend to modify the page
    1299             :      */
    1300     1643952 :     CheckForSerializableConflictIn(state->r, NULL, BufferGetBlockNumber(stack->buffer));
    1301             : 
    1302             :     /* Insert the tuple(s) to the page, splitting the page if necessary */
    1303     1643940 :     is_split = gistplacetopage(state->r, state->freespace, giststate,
    1304             :                                stack->buffer,
    1305             :                                tuples, ntup,
    1306             :                                oldoffnum, NULL,
    1307             :                                leftchild,
    1308             :                                &splitinfo,
    1309             :                                true,
    1310             :                                state->heapRel,
    1311     1643940 :                                state->is_build);
    1312             : 
    1313             :     /*
    1314             :      * Before recursing up in case the page was split, release locks on the
    1315             :      * child pages. We don't need to keep them locked when updating the
    1316             :      * parent.
    1317             :      */
    1318     1643940 :     if (BufferIsValid(rightchild))
    1319       24152 :         UnlockReleaseBuffer(rightchild);
    1320     1643940 :     if (BufferIsValid(leftchild) && unlockleftchild)
    1321        4846 :         LockBuffer(leftchild, GIST_UNLOCK);
    1322             : 
    1323             :     /*
    1324             :      * If we had to split, insert/update the downlinks in the parent. If the
    1325             :      * caller requested us to release the lock on stack->buffer, tell
    1326             :      * gistfinishsplit() to do that as soon as it's safe to do so. If we
    1327             :      * didn't have to split, release it ourselves.
    1328             :      */
    1329     1643940 :     if (splitinfo)
    1330       24096 :         gistfinishsplit(state, stack, giststate, splitinfo, unlockbuf);
    1331     1619844 :     else if (unlockbuf)
    1332       19250 :         LockBuffer(stack->buffer, GIST_UNLOCK);
    1333             : 
    1334     1643940 :     return is_split;
    1335             : }
    1336             : 
    1337             : /*
    1338             :  * Finish an incomplete split by inserting/updating the downlinks in parent
    1339             :  * page. 'splitinfo' contains all the child pages involved in the split,
    1340             :  * from left-to-right.
    1341             :  *
    1342             :  * On entry, the caller must hold a lock on stack->buffer and all the child
    1343             :  * pages in 'splitinfo'. If 'unlockbuf' is true, the lock on stack->buffer is
    1344             :  * released on return. The child pages are always unlocked and unpinned.
    1345             :  */
    1346             : static void
    1347       24096 : gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
    1348             :                 GISTSTATE *giststate, List *splitinfo, bool unlockbuf)
    1349             : {
    1350             :     GISTPageSplitInfo *right;
    1351             :     GISTPageSplitInfo *left;
    1352             :     IndexTuple  tuples[2];
    1353             : 
    1354             :     /* A split always contains at least two halves */
    1355             :     Assert(list_length(splitinfo) >= 2);
    1356             : 
    1357             :     /*
    1358             :      * We need to insert downlinks for each new page, and update the downlink
    1359             :      * for the original (leftmost) page in the split. Begin at the rightmost
    1360             :      * page, inserting one downlink at a time until there's only two pages
    1361             :      * left. Finally insert the downlink for the last new page and update the
    1362             :      * downlink for the original page as one operation.
    1363             :      */
    1364       24096 :     LockBuffer(stack->parent->buffer, GIST_EXCLUSIVE);
    1365             : 
    1366             :     /*
    1367             :      * Insert downlinks for the siblings from right to left, until there are
    1368             :      * only two siblings left.
    1369             :      */
    1370       24152 :     for (int pos = list_length(splitinfo) - 1; pos > 1; pos--)
    1371             :     {
    1372          56 :         right = (GISTPageSplitInfo *) list_nth(splitinfo, pos);
    1373          56 :         left = (GISTPageSplitInfo *) list_nth(splitinfo, pos - 1);
    1374             : 
    1375          56 :         gistFindCorrectParent(state->r, stack, state->is_build);
    1376          56 :         if (gistinserttuples(state, stack->parent, giststate,
    1377             :                              &right->downlink, 1,
    1378             :                              InvalidOffsetNumber,
    1379             :                              left->buf, right->buf, false, false))
    1380             :         {
    1381             :             /*
    1382             :              * If the parent page was split, the existing downlink might have
    1383             :              * moved.
    1384             :              */
    1385           0 :             stack->downlinkoffnum = InvalidOffsetNumber;
    1386             :         }
    1387             :         /* gistinserttuples() released the lock on right->buf. */
    1388             :     }
    1389             : 
    1390       24096 :     right = (GISTPageSplitInfo *) lsecond(splitinfo);
    1391       24096 :     left = (GISTPageSplitInfo *) linitial(splitinfo);
    1392             : 
    1393             :     /*
    1394             :      * Finally insert downlink for the remaining right page and update the
    1395             :      * downlink for the original page to not contain the tuples that were
    1396             :      * moved to the new pages.
    1397             :      */
    1398       24096 :     tuples[0] = left->downlink;
    1399       24096 :     tuples[1] = right->downlink;
    1400       24096 :     gistFindCorrectParent(state->r, stack, state->is_build);
    1401       24096 :     (void) gistinserttuples(state, stack->parent, giststate,
    1402             :                             tuples, 2,
    1403       24096 :                             stack->downlinkoffnum,
    1404             :                             left->buf, right->buf,
    1405             :                             true,   /* Unlock parent */
    1406             :                             unlockbuf   /* Unlock stack->buffer if caller
    1407             :                                          * wants that */
    1408             :         );
    1409             : 
    1410             :     /*
    1411             :      * The downlink might have moved when we updated it. Even if the page
    1412             :      * wasn't split, because gistinserttuples() implements updating the old
    1413             :      * tuple by removing and re-inserting it!
    1414             :      */
    1415       24096 :     stack->downlinkoffnum = InvalidOffsetNumber;
    1416             : 
    1417             :     Assert(left->buf == stack->buffer);
    1418             : 
    1419             :     /*
    1420             :      * If we split the page because we had to adjust the downlink on an
    1421             :      * internal page, while descending the tree for inserting a new tuple,
    1422             :      * then this might no longer be the correct page for the new tuple. The
    1423             :      * downlink to this page might not cover the new tuple anymore, it might
    1424             :      * need to go to the newly-created right sibling instead. Tell the caller
    1425             :      * to walk back up the stack, to re-check at the parent which page to
    1426             :      * insert to.
    1427             :      *
    1428             :      * Normally, the LSN-NSN interlock during the tree descend would also
    1429             :      * detect that a concurrent split happened (by ourselves), and cause us to
    1430             :      * retry at the parent. But that mechanism doesn't work during index
    1431             :      * build, because we don't do WAL-logging, and don't update LSNs, during
    1432             :      * index build.
    1433             :      */
    1434       24096 :     stack->retry_from_parent = true;
    1435       24096 : }
    1436             : 
    1437             : /*
    1438             :  * gistSplit -- split a page in the tree and fill struct
    1439             :  * used for XLOG and real writes buffers. Function is recursive, ie
    1440             :  * it will split page until keys will fit in every page.
    1441             :  */
    1442             : SplitPageLayout *
    1443       26484 : gistSplit(Relation r,
    1444             :           Page page,
    1445             :           IndexTuple *itup,     /* contains compressed entry */
    1446             :           int len,
    1447             :           GISTSTATE *giststate)
    1448             : {
    1449             :     IndexTuple *lvectup,
    1450             :                *rvectup;
    1451             :     GistSplitVector v;
    1452             :     int         i;
    1453       26484 :     SplitPageLayout *res = NULL;
    1454             : 
    1455             :     /* this should never recurse very deeply, but better safe than sorry */
    1456       26484 :     check_stack_depth();
    1457             : 
    1458             :     /* there's no point in splitting an empty page */
    1459             :     Assert(len > 0);
    1460             : 
    1461             :     /*
    1462             :      * If a single tuple doesn't fit on a page, no amount of splitting will
    1463             :      * help.
    1464             :      */
    1465       26484 :     if (len == 1)
    1466           0 :         ereport(ERROR,
    1467             :                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
    1468             :                  errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
    1469             :                         IndexTupleSize(itup[0]), GiSTPageSize,
    1470             :                         RelationGetRelationName(r))));
    1471             : 
    1472       26484 :     memset(v.spl_lisnull, true,
    1473       26484 :            sizeof(bool) * giststate->nonLeafTupdesc->natts);
    1474       26484 :     memset(v.spl_risnull, true,
    1475       26484 :            sizeof(bool) * giststate->nonLeafTupdesc->natts);
    1476       26484 :     gistSplitByKey(r, page, itup, len, giststate, &v, 0);
    1477             : 
    1478             :     /* form left and right vector */
    1479       26484 :     lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
    1480       26484 :     rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
    1481             : 
    1482     1117080 :     for (i = 0; i < v.splitVector.spl_nleft; i++)
    1483     1090596 :         lvectup[i] = itup[v.splitVector.spl_left[i] - 1];
    1484             : 
    1485     1247726 :     for (i = 0; i < v.splitVector.spl_nright; i++)
    1486     1221242 :         rvectup[i] = itup[v.splitVector.spl_right[i] - 1];
    1487             : 
    1488             :     /* finalize splitting (may need another split) */
    1489       26484 :     if (!gistfitpage(rvectup, v.splitVector.spl_nright))
    1490             :     {
    1491         596 :         res = gistSplit(r, page, rvectup, v.splitVector.spl_nright, giststate);
    1492             :     }
    1493             :     else
    1494             :     {
    1495       25888 :         ROTATEDIST(res);
    1496       25888 :         res->block.num = v.splitVector.spl_nright;
    1497       25888 :         res->list = gistfillitupvec(rvectup, v.splitVector.spl_nright, &(res->lenlist));
    1498       25888 :         res->itup = gistFormTuple(giststate, r, v.spl_rattr, v.spl_risnull, false);
    1499             :     }
    1500             : 
    1501       26484 :     if (!gistfitpage(lvectup, v.splitVector.spl_nleft))
    1502             :     {
    1503             :         SplitPageLayout *resptr,
    1504             :                    *subres;
    1505             : 
    1506         330 :         resptr = subres = gistSplit(r, page, lvectup, v.splitVector.spl_nleft, giststate);
    1507             : 
    1508             :         /* install on list's tail */
    1509         822 :         while (resptr->next)
    1510         492 :             resptr = resptr->next;
    1511             : 
    1512         330 :         resptr->next = res;
    1513         330 :         res = subres;
    1514             :     }
    1515             :     else
    1516             :     {
    1517       26154 :         ROTATEDIST(res);
    1518       26154 :         res->block.num = v.splitVector.spl_nleft;
    1519       26154 :         res->list = gistfillitupvec(lvectup, v.splitVector.spl_nleft, &(res->lenlist));
    1520       26154 :         res->itup = gistFormTuple(giststate, r, v.spl_lattr, v.spl_lisnull, false);
    1521             :     }
    1522             : 
    1523       26484 :     return res;
    1524             : }
    1525             : 
    1526             : /*
    1527             :  * Create a GISTSTATE and fill it with information about the index
    1528             :  */
    1529             : GISTSTATE *
    1530        9164 : initGISTstate(Relation index)
    1531             : {
    1532             :     GISTSTATE  *giststate;
    1533             :     MemoryContext scanCxt;
    1534             :     MemoryContext oldCxt;
    1535             :     int         i;
    1536             : 
    1537             :     /* safety check to protect fixed-size arrays in GISTSTATE */
    1538        9164 :     if (index->rd_att->natts > INDEX_MAX_KEYS)
    1539           0 :         elog(ERROR, "numberOfAttributes %d > %d",
    1540             :              index->rd_att->natts, INDEX_MAX_KEYS);
    1541             : 
    1542             :     /* Create the memory context that will hold the GISTSTATE */
    1543        9164 :     scanCxt = AllocSetContextCreate(CurrentMemoryContext,
    1544             :                                     "GiST scan context",
    1545             :                                     ALLOCSET_DEFAULT_SIZES);
    1546        9164 :     oldCxt = MemoryContextSwitchTo(scanCxt);
    1547             : 
    1548             :     /* Create and fill in the GISTSTATE */
    1549        9164 :     giststate = (GISTSTATE *) palloc(sizeof(GISTSTATE));
    1550             : 
    1551        9164 :     giststate->scanCxt = scanCxt;
    1552        9164 :     giststate->tempCxt = scanCxt;    /* caller must change this if needed */
    1553        9164 :     giststate->leafTupdesc = index->rd_att;
    1554             : 
    1555             :     /*
    1556             :      * The truncated tupdesc for non-leaf index tuples, which doesn't contain
    1557             :      * the INCLUDE attributes.
    1558             :      *
    1559             :      * It is used to form tuples during tuple adjustment and page split.
    1560             :      * B-tree creates shortened tuple descriptor for every truncated tuple,
    1561             :      * because it is doing this less often: it does not have to form truncated
    1562             :      * tuples during page split.  Also, B-tree is not adjusting tuples on
    1563             :      * internal pages the way GiST does.
    1564             :      */
    1565       18328 :     giststate->nonLeafTupdesc = CreateTupleDescTruncatedCopy(index->rd_att,
    1566        9164 :                                                              IndexRelationGetNumberOfKeyAttributes(index));
    1567             : 
    1568       24248 :     for (i = 0; i < IndexRelationGetNumberOfKeyAttributes(index); i++)
    1569             :     {
    1570       15084 :         fmgr_info_copy(&(giststate->consistentFn[i]),
    1571       15084 :                        index_getprocinfo(index, i + 1, GIST_CONSISTENT_PROC),
    1572             :                        scanCxt);
    1573       15084 :         fmgr_info_copy(&(giststate->unionFn[i]),
    1574       15084 :                        index_getprocinfo(index, i + 1, GIST_UNION_PROC),
    1575             :                        scanCxt);
    1576             : 
    1577             :         /* opclasses are not required to provide a Compress method */
    1578       15084 :         if (OidIsValid(index_getprocid(index, i + 1, GIST_COMPRESS_PROC)))
    1579        5386 :             fmgr_info_copy(&(giststate->compressFn[i]),
    1580        5386 :                            index_getprocinfo(index, i + 1, GIST_COMPRESS_PROC),
    1581             :                            scanCxt);
    1582             :         else
    1583        9698 :             giststate->compressFn[i].fn_oid = InvalidOid;
    1584             : 
    1585             :         /* opclasses are not required to provide a Decompress method */
    1586       15084 :         if (OidIsValid(index_getprocid(index, i + 1, GIST_DECOMPRESS_PROC)))
    1587        1594 :             fmgr_info_copy(&(giststate->decompressFn[i]),
    1588        1594 :                            index_getprocinfo(index, i + 1, GIST_DECOMPRESS_PROC),
    1589             :                            scanCxt);
    1590             :         else
    1591       13490 :             giststate->decompressFn[i].fn_oid = InvalidOid;
    1592             : 
    1593       15084 :         fmgr_info_copy(&(giststate->penaltyFn[i]),
    1594       15084 :                        index_getprocinfo(index, i + 1, GIST_PENALTY_PROC),
    1595             :                        scanCxt);
    1596       15084 :         fmgr_info_copy(&(giststate->picksplitFn[i]),
    1597       15084 :                        index_getprocinfo(index, i + 1, GIST_PICKSPLIT_PROC),
    1598             :                        scanCxt);
    1599       15084 :         fmgr_info_copy(&(giststate->equalFn[i]),
    1600       15084 :                        index_getprocinfo(index, i + 1, GIST_EQUAL_PROC),
    1601             :                        scanCxt);
    1602             : 
    1603             :         /* opclasses are not required to provide a Distance method */
    1604       15084 :         if (OidIsValid(index_getprocid(index, i + 1, GIST_DISTANCE_PROC)))
    1605        1904 :             fmgr_info_copy(&(giststate->distanceFn[i]),
    1606        1904 :                            index_getprocinfo(index, i + 1, GIST_DISTANCE_PROC),
    1607             :                            scanCxt);
    1608             :         else
    1609       13180 :             giststate->distanceFn[i].fn_oid = InvalidOid;
    1610             : 
    1611             :         /* opclasses are not required to provide a Fetch method */
    1612       15084 :         if (OidIsValid(index_getprocid(index, i + 1, GIST_FETCH_PROC)))
    1613        1362 :             fmgr_info_copy(&(giststate->fetchFn[i]),
    1614        1362 :                            index_getprocinfo(index, i + 1, GIST_FETCH_PROC),
    1615             :                            scanCxt);
    1616             :         else
    1617       13722 :             giststate->fetchFn[i].fn_oid = InvalidOid;
    1618             : 
    1619             :         /*
    1620             :          * If the index column has a specified collation, we should honor that
    1621             :          * while doing comparisons.  However, we may have a collatable storage
    1622             :          * type for a noncollatable indexed data type.  If there's no index
    1623             :          * collation then specify default collation in case the support
    1624             :          * functions need collation.  This is harmless if the support
    1625             :          * functions don't care about collation, so we just do it
    1626             :          * unconditionally.  (We could alternatively call get_typcollation,
    1627             :          * but that seems like expensive overkill --- there aren't going to be
    1628             :          * any cases where a GiST storage type has a nondefault collation.)
    1629             :          */
    1630       15084 :         if (OidIsValid(index->rd_indcollation[i]))
    1631         194 :             giststate->supportCollation[i] = index->rd_indcollation[i];
    1632             :         else
    1633       14890 :             giststate->supportCollation[i] = DEFAULT_COLLATION_OID;
    1634             :     }
    1635             : 
    1636             :     /* No opclass information for INCLUDE attributes */
    1637        9666 :     for (; i < index->rd_att->natts; i++)
    1638             :     {
    1639         502 :         giststate->consistentFn[i].fn_oid = InvalidOid;
    1640         502 :         giststate->unionFn[i].fn_oid = InvalidOid;
    1641         502 :         giststate->compressFn[i].fn_oid = InvalidOid;
    1642         502 :         giststate->decompressFn[i].fn_oid = InvalidOid;
    1643         502 :         giststate->penaltyFn[i].fn_oid = InvalidOid;
    1644         502 :         giststate->picksplitFn[i].fn_oid = InvalidOid;
    1645         502 :         giststate->equalFn[i].fn_oid = InvalidOid;
    1646         502 :         giststate->distanceFn[i].fn_oid = InvalidOid;
    1647         502 :         giststate->fetchFn[i].fn_oid = InvalidOid;
    1648         502 :         giststate->supportCollation[i] = InvalidOid;
    1649             :     }
    1650             : 
    1651        9164 :     MemoryContextSwitchTo(oldCxt);
    1652             : 
    1653        9164 :     return giststate;
    1654             : }
    1655             : 
    1656             : void
    1657        7040 : freeGISTstate(GISTSTATE *giststate)
    1658             : {
    1659             :     /* It's sufficient to delete the scanCxt */
    1660        7040 :     MemoryContextDelete(giststate->scanCxt);
    1661        7040 : }
    1662             : 
    1663             : /*
    1664             :  * gistprunepage() -- try to remove LP_DEAD items from the given page.
    1665             :  * Function assumes that buffer is exclusively locked.
    1666             :  */
    1667             : static void
    1668           0 : gistprunepage(Relation rel, Page page, Buffer buffer, Relation heapRel)
    1669             : {
    1670             :     OffsetNumber deletable[MaxIndexTuplesPerPage];
    1671           0 :     int         ndeletable = 0;
    1672             :     OffsetNumber offnum,
    1673             :                 maxoff;
    1674             : 
    1675             :     Assert(GistPageIsLeaf(page));
    1676             : 
    1677             :     /*
    1678             :      * Scan over all items to see which ones need to be deleted according to
    1679             :      * LP_DEAD flags.
    1680             :      */
    1681           0 :     maxoff = PageGetMaxOffsetNumber(page);
    1682           0 :     for (offnum = FirstOffsetNumber;
    1683             :          offnum <= maxoff;
    1684           0 :          offnum = OffsetNumberNext(offnum))
    1685             :     {
    1686           0 :         ItemId      itemId = PageGetItemId(page, offnum);
    1687             : 
    1688           0 :         if (ItemIdIsDead(itemId))
    1689           0 :             deletable[ndeletable++] = offnum;
    1690             :     }
    1691             : 
    1692           0 :     if (ndeletable > 0)
    1693             :     {
    1694           0 :         TransactionId snapshotConflictHorizon = InvalidTransactionId;
    1695             : 
    1696           0 :         if (XLogStandbyInfoActive() && RelationNeedsWAL(rel))
    1697             :             snapshotConflictHorizon =
    1698           0 :                 index_compute_xid_horizon_for_tuples(rel, heapRel, buffer,
    1699             :                                                      deletable, ndeletable);
    1700             : 
    1701           0 :         START_CRIT_SECTION();
    1702             : 
    1703           0 :         PageIndexMultiDelete(page, deletable, ndeletable);
    1704             : 
    1705             :         /*
    1706             :          * Mark the page as not containing any LP_DEAD items.  This is not
    1707             :          * certainly true (there might be some that have recently been marked,
    1708             :          * but weren't included in our target-item list), but it will almost
    1709             :          * always be true and it doesn't seem worth an additional page scan to
    1710             :          * check it. Remember that F_HAS_GARBAGE is only a hint anyway.
    1711             :          */
    1712           0 :         GistClearPageHasGarbage(page);
    1713             : 
    1714           0 :         MarkBufferDirty(buffer);
    1715             : 
    1716             :         /* XLOG stuff */
    1717           0 :         if (RelationNeedsWAL(rel))
    1718           0 :         {
    1719             :             XLogRecPtr  recptr;
    1720             : 
    1721           0 :             recptr = gistXLogDelete(buffer,
    1722             :                                     deletable, ndeletable,
    1723             :                                     snapshotConflictHorizon,
    1724             :                                     heapRel);
    1725             : 
    1726           0 :             PageSetLSN(page, recptr);
    1727             :         }
    1728             :         else
    1729           0 :             PageSetLSN(page, gistGetFakeLSN(rel));
    1730             : 
    1731           0 :         END_CRIT_SECTION();
    1732             :     }
    1733             : 
    1734             :     /*
    1735             :      * Note: if we didn't find any LP_DEAD items, then the page's
    1736             :      * F_HAS_GARBAGE hint bit is falsely set.  We do not bother expending a
    1737             :      * separate write to clear it, however.  We will clear it when we split
    1738             :      * the page.
    1739             :      */
    1740           0 : }

Generated by: LCOV version 1.14