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

Generated by: LCOV version 1.13