PostgreSQL Source Code  git master
gist.c File Reference
#include "postgres.h"
#include "access/gist_private.h"
#include "access/gistscan.h"
#include "access/xloginsert.h"
#include "catalog/pg_collation.h"
#include "commands/vacuum.h"
#include "miscadmin.h"
#include "nodes/execnodes.h"
#include "storage/predicate.h"
#include "utils/fmgrprotos.h"
#include "utils/index_selfuncs.h"
#include "utils/memutils.h"
#include "utils/rel.h"
Include dependency graph for gist.c:

Go to the source code of this file.

Macros

#define ROTATEDIST(d)
 

Functions

static void gistfixsplit (GISTInsertState *state, GISTSTATE *giststate)
 
static bool gistinserttuple (GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum)
 
static bool gistinserttuples (GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, IndexTuple *tuples, int ntup, OffsetNumber oldoffnum, Buffer leftchild, Buffer rightchild, bool unlockbuf, bool unlockleftchild)
 
static void gistfinishsplit (GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, List *splitinfo, bool unlockbuf)
 
static void gistprunepage (Relation rel, Page page, Buffer buffer, Relation heapRel)
 
Datum gisthandler (PG_FUNCTION_ARGS)
 
MemoryContext createTempGistContext (void)
 
void gistbuildempty (Relation index)
 
bool gistinsert (Relation r, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, IndexInfo *indexInfo)
 
bool gistplacetopage (Relation rel, Size freespace, GISTSTATE *giststate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber *newblkno, Buffer leftchildbuf, List **splitinfo, bool markfollowright, Relation heapRel, bool is_build)
 
void gistdoinsert (Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate, Relation heapRel, bool is_build)
 
static GISTInsertStackgistFindPath (Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
 
static void gistFindCorrectParent (Relation r, GISTInsertStack *child, bool is_build)
 
static IndexTuple gistformdownlink (Relation rel, Buffer buf, GISTSTATE *giststate, GISTInsertStack *stack, bool is_build)
 
SplitPageLayoutgistSplit (Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate)
 
GISTSTATEinitGISTstate (Relation index)
 
void freeGISTstate (GISTSTATE *giststate)
 

Macro Definition Documentation

◆ ROTATEDIST

#define ROTATEDIST (   d)
Value:
do { \
SplitPageLayout *tmp=(SplitPageLayout*)palloc0(sizeof(SplitPageLayout)); \
tmp->block.blkno = InvalidBlockNumber; \
tmp->buffer = InvalidBuffer; \
tmp->next = (d); \
(d)=tmp; \
} while(0)
#define InvalidBlockNumber
Definition: block.h:33
#define InvalidBuffer
Definition: buf.h:25
void * palloc0(Size size)
Definition: mcxt.c:1334

Definition at line 45 of file gist.c.

Function Documentation

◆ createTempGistContext()

MemoryContext createTempGistContext ( void  )

Definition at line 122 of file gist.c.

123 {
125  "GiST temporary context",
127 }
MemoryContext CurrentMemoryContext
Definition: mcxt.c:131
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:153

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, and CurrentMemoryContext.

Referenced by gist_xlog_startup(), gistbeginscan(), gistbuild(), and gistinsert().

◆ freeGISTstate()

void freeGISTstate ( GISTSTATE giststate)

Definition at line 1653 of file gist.c.

1654 {
1655  /* It's sufficient to delete the scanCxt */
1656  MemoryContextDelete(giststate->scanCxt);
1657 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:442
MemoryContext scanCxt
Definition: gist_private.h:77

References MemoryContextDelete(), and GISTSTATE::scanCxt.

Referenced by gistbuild(), and gistendscan().

◆ gistbuildempty()

void gistbuildempty ( Relation  index)

Definition at line 133 of file gist.c.

134 {
135  Buffer buffer;
136 
137  /* Initialize the root page */
138  buffer = ExtendBufferedRel(BMR_REL(index), INIT_FORKNUM, NULL,
140 
141  /* Initialize and xlog buffer */
143  GISTInitBuffer(buffer, F_LEAF);
144  MarkBufferDirty(buffer);
145  log_newpage_buffer(buffer, true);
147 
148  /* Unlock and release the buffer */
149  UnlockReleaseBuffer(buffer);
150 }
int Buffer
Definition: buf.h:23
Buffer ExtendBufferedRel(BufferManagerRelation bmr, ForkNumber forkNum, BufferAccessStrategy strategy, uint32 flags)
Definition: bufmgr.c:838
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4577
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:2189
@ EB_SKIP_EXTENSION_LOCK
Definition: bufmgr.h:73
@ EB_LOCK_FIRST
Definition: bufmgr.h:85
#define BMR_REL(p_rel)
Definition: bufmgr.h:106
#define F_LEAF
Definition: gist.h:48
void GISTInitBuffer(Buffer b, uint32 f)
Definition: gistutil.c:773
#define START_CRIT_SECTION()
Definition: miscadmin.h:149
#define END_CRIT_SECTION()
Definition: miscadmin.h:151
@ INIT_FORKNUM
Definition: relpath.h:53
Definition: type.h:95
XLogRecPtr log_newpage_buffer(Buffer buffer, bool page_std)
Definition: xloginsert.c:1237

References BMR_REL, EB_LOCK_FIRST, EB_SKIP_EXTENSION_LOCK, END_CRIT_SECTION, ExtendBufferedRel(), F_LEAF, GISTInitBuffer(), INIT_FORKNUM, log_newpage_buffer(), MarkBufferDirty(), START_CRIT_SECTION, and UnlockReleaseBuffer().

Referenced by gisthandler().

◆ gistdoinsert()

void gistdoinsert ( Relation  r,
IndexTuple  itup,
Size  freespace,
GISTSTATE giststate,
Relation  heapRel,
bool  is_build 
)

Definition at line 634 of file gist.c.

636 {
637  ItemId iid;
638  IndexTuple idxtuple;
639  GISTInsertStack firststack;
640  GISTInsertStack *stack;
642  bool xlocked = false;
643 
644  memset(&state, 0, sizeof(GISTInsertState));
645  state.freespace = freespace;
646  state.r = r;
647  state.heapRel = heapRel;
648  state.is_build = is_build;
649 
650  /* Start from the root */
651  firststack.blkno = GIST_ROOT_BLKNO;
652  firststack.lsn = 0;
653  firststack.retry_from_parent = false;
654  firststack.parent = NULL;
655  firststack.downlinkoffnum = InvalidOffsetNumber;
656  state.stack = stack = &firststack;
657 
658  /*
659  * Walk down along the path of smallest penalty, updating the parent
660  * pointers with the key we're inserting as we go. If we crash in the
661  * middle, the tree is consistent, although the possible parent updates
662  * were a waste.
663  */
664  for (;;)
665  {
666  /*
667  * If we split an internal page while descending the tree, we have to
668  * retry at the parent. (Normally, the LSN-NSN interlock below would
669  * also catch this and cause us to retry. But LSNs are not updated
670  * during index build.)
671  */
672  while (stack->retry_from_parent)
673  {
674  if (xlocked)
675  LockBuffer(stack->buffer, GIST_UNLOCK);
676  xlocked = false;
677  ReleaseBuffer(stack->buffer);
678  state.stack = stack = stack->parent;
679  }
680 
681  if (XLogRecPtrIsInvalid(stack->lsn))
682  stack->buffer = ReadBuffer(state.r, stack->blkno);
683 
684  /*
685  * Be optimistic and grab shared lock first. Swap it for an exclusive
686  * lock later if we need to update the page.
687  */
688  if (!xlocked)
689  {
690  LockBuffer(stack->buffer, GIST_SHARE);
691  gistcheckpage(state.r, stack->buffer);
692  }
693 
694  stack->page = (Page) BufferGetPage(stack->buffer);
695  stack->lsn = xlocked ?
696  PageGetLSN(stack->page) : BufferGetLSNAtomic(stack->buffer);
698 
699  /*
700  * If this page was split but the downlink was never inserted to the
701  * parent because the inserting backend crashed before doing that, fix
702  * that now.
703  */
704  if (GistFollowRight(stack->page))
705  {
706  if (!xlocked)
707  {
708  LockBuffer(stack->buffer, GIST_UNLOCK);
710  xlocked = true;
711  /* someone might've completed the split when we unlocked */
712  if (!GistFollowRight(stack->page))
713  continue;
714  }
715  gistfixsplit(&state, giststate);
716 
717  UnlockReleaseBuffer(stack->buffer);
718  xlocked = false;
719  state.stack = stack = stack->parent;
720  continue;
721  }
722 
723  if ((stack->blkno != GIST_ROOT_BLKNO &&
724  stack->parent->lsn < GistPageGetNSN(stack->page)) ||
725  GistPageIsDeleted(stack->page))
726  {
727  /*
728  * Concurrent split or page deletion detected. There's no
729  * guarantee that the downlink for this page is consistent with
730  * the tuple we're inserting anymore, so go back to parent and
731  * rechoose the best child.
732  */
733  UnlockReleaseBuffer(stack->buffer);
734  xlocked = false;
735  state.stack = stack = stack->parent;
736  continue;
737  }
738 
739  if (!GistPageIsLeaf(stack->page))
740  {
741  /*
742  * This is an internal page so continue to walk down the tree.
743  * Find the child node that has the minimum insertion penalty.
744  */
745  BlockNumber childblkno;
746  IndexTuple newtup;
747  GISTInsertStack *item;
748  OffsetNumber downlinkoffnum;
749 
750  downlinkoffnum = gistchoose(state.r, stack->page, itup, giststate);
751  iid = PageGetItemId(stack->page, downlinkoffnum);
752  idxtuple = (IndexTuple) PageGetItem(stack->page, iid);
753  childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
754 
755  /*
756  * Check that it's not a leftover invalid tuple from pre-9.1
757  */
758  if (GistTupleIsInvalid(idxtuple))
759  ereport(ERROR,
760  (errmsg("index \"%s\" contains an inner tuple marked as invalid",
762  errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
763  errhint("Please REINDEX it.")));
764 
765  /*
766  * Check that the key representing the target child node is
767  * consistent with the key we're inserting. Update it if it's not.
768  */
769  newtup = gistgetadjusted(state.r, idxtuple, itup, giststate);
770  if (newtup)
771  {
772  /*
773  * Swap shared lock for an exclusive one. Beware, the page may
774  * change while we unlock/lock the page...
775  */
776  if (!xlocked)
777  {
778  LockBuffer(stack->buffer, GIST_UNLOCK);
780  xlocked = true;
781  stack->page = (Page) BufferGetPage(stack->buffer);
782 
783  if (PageGetLSN(stack->page) != stack->lsn)
784  {
785  /* the page was changed while we unlocked it, retry */
786  continue;
787  }
788  }
789 
790  /*
791  * Update the tuple.
792  *
793  * We still hold the lock after gistinserttuple(), but it
794  * might have to split the page to make the updated tuple fit.
795  * In that case the updated tuple might migrate to the other
796  * half of the split, so we have to go back to the parent and
797  * descend back to the half that's a better fit for the new
798  * tuple.
799  */
800  if (gistinserttuple(&state, stack, giststate, newtup,
801  downlinkoffnum))
802  {
803  /*
804  * If this was a root split, the root page continues to be
805  * the parent and the updated tuple went to one of the
806  * child pages, so we just need to retry from the root
807  * page.
808  */
809  if (stack->blkno != GIST_ROOT_BLKNO)
810  {
811  UnlockReleaseBuffer(stack->buffer);
812  xlocked = false;
813  state.stack = stack = stack->parent;
814  }
815  continue;
816  }
817  }
818  LockBuffer(stack->buffer, GIST_UNLOCK);
819  xlocked = false;
820 
821  /* descend to the chosen child */
822  item = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
823  item->blkno = childblkno;
824  item->parent = stack;
825  item->downlinkoffnum = downlinkoffnum;
826  state.stack = stack = item;
827  }
828  else
829  {
830  /*
831  * Leaf page. Insert the new key. We've already updated all the
832  * parents on the way down, but we might have to split the page if
833  * it doesn't fit. gistinserttuple() will take care of that.
834  */
835 
836  /*
837  * Swap shared lock for an exclusive one. Be careful, the page may
838  * change while we unlock/lock the page...
839  */
840  if (!xlocked)
841  {
842  LockBuffer(stack->buffer, GIST_UNLOCK);
844  xlocked = true;
845  stack->page = (Page) BufferGetPage(stack->buffer);
846  stack->lsn = PageGetLSN(stack->page);
847 
848  if (stack->blkno == GIST_ROOT_BLKNO)
849  {
850  /*
851  * the only page that can become inner instead of leaf is
852  * the root page, so for root we should recheck it
853  */
854  if (!GistPageIsLeaf(stack->page))
855  {
856  /*
857  * very rare situation: during unlock/lock index with
858  * number of pages = 1 was increased
859  */
860  LockBuffer(stack->buffer, GIST_UNLOCK);
861  xlocked = false;
862  continue;
863  }
864 
865  /*
866  * we don't need to check root split, because checking
867  * leaf/inner is enough to recognize split for root
868  */
869  }
870  else if ((GistFollowRight(stack->page) ||
871  stack->parent->lsn < GistPageGetNSN(stack->page)) ||
872  GistPageIsDeleted(stack->page))
873  {
874  /*
875  * The page was split or deleted while we momentarily
876  * unlocked the page. Go back to parent.
877  */
878  UnlockReleaseBuffer(stack->buffer);
879  xlocked = false;
880  state.stack = stack = stack->parent;
881  continue;
882  }
883  }
884 
885  /* now state.stack->(page, buffer and blkno) points to leaf page */
886 
887  gistinserttuple(&state, stack, giststate, itup,
889  LockBuffer(stack->buffer, GIST_UNLOCK);
890 
891  /* Release any pins we might still hold before exiting */
892  for (; stack; stack = stack->parent)
893  ReleaseBuffer(stack->buffer);
894  break;
895  }
896  }
897 }
uint32 BlockNumber
Definition: block.h:31
void ReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:4560
XLogRecPtr BufferGetLSNAtomic(Buffer buffer)
Definition: bufmgr.c:3638
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4795
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:734
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:350
Pointer Page
Definition: bufpage.h:78
static Item PageGetItem(Page page, ItemId itemId)
Definition: bufpage.h:351
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
Definition: bufpage.h:240
static XLogRecPtr PageGetLSN(Page page)
Definition: bufpage.h:383
int errdetail(const char *fmt,...)
Definition: elog.c:1205
int errhint(const char *fmt,...)
Definition: elog.c:1319
int errmsg(const char *fmt,...)
Definition: elog.c:1072
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
static void gistfixsplit(GISTInsertState *state, GISTSTATE *giststate)
Definition: gist.c:1188
static bool gistinserttuple(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, IndexTuple tuple, OffsetNumber oldoffnum)
Definition: gist.c:1248
#define GistPageIsLeaf(page)
Definition: gist.h:169
#define GistFollowRight(page)
Definition: gist.h:182
#define GistPageIsDeleted(page)
Definition: gist.h:172
#define GistPageGetNSN(page)
Definition: gist.h:186
#define GIST_UNLOCK
Definition: gist_private.h:44
#define GIST_ROOT_BLKNO
Definition: gist_private.h:262
#define GIST_EXCLUSIVE
Definition: gist_private.h:43
#define GistTupleIsInvalid(itup)
Definition: gist_private.h:288
#define GIST_SHARE
Definition: gist_private.h:42
IndexTuple gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
Definition: gistutil.c:316
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
Definition: gistutil.c:374
void gistcheckpage(Relation rel, Buffer buf)
Definition: gistutil.c:785
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
IndexTupleData * IndexTuple
Definition: itup.h:53
Assert(fmt[strlen(fmt) - 1] !='\n')
#define InvalidOffsetNumber
Definition: off.h:26
uint16 OffsetNumber
Definition: off.h:24
#define RelationGetRelationName(relation)
Definition: rel.h:541
#define RelationNeedsWAL(relation)
Definition: rel.h:630
BlockNumber blkno
Definition: gist_private.h:210
OffsetNumber downlinkoffnum
Definition: gist_private.h:228
struct GISTInsertStack * parent
Definition: gist_private.h:231
ItemPointerData t_tid
Definition: itup.h:37
Definition: regguts.h:323
#define XLogRecPtrIsInvalid(r)
Definition: xlogdefs.h:29

References Assert(), GISTInsertStack::blkno, GISTInsertStack::buffer, BufferGetLSNAtomic(), BufferGetPage(), GISTInsertStack::downlinkoffnum, ereport, errdetail(), errhint(), errmsg(), ERROR, GIST_EXCLUSIVE, GIST_ROOT_BLKNO, GIST_SHARE, GIST_UNLOCK, gistcheckpage(), gistchoose(), gistfixsplit(), GistFollowRight, gistgetadjusted(), gistinserttuple(), GistPageGetNSN, GistPageIsDeleted, GistPageIsLeaf, GistTupleIsInvalid, InvalidOffsetNumber, ItemPointerGetBlockNumber(), LockBuffer(), GISTInsertStack::lsn, GISTInsertStack::page, PageGetItem(), PageGetItemId(), PageGetLSN(), palloc0(), GISTInsertStack::parent, ReadBuffer(), RelationGetRelationName, RelationNeedsWAL, ReleaseBuffer(), GISTInsertStack::retry_from_parent, IndexTupleData::t_tid, UnlockReleaseBuffer(), and XLogRecPtrIsInvalid.

Referenced by gistBuildCallback(), and gistinsert().

◆ gistFindCorrectParent()

static void gistFindCorrectParent ( Relation  r,
GISTInsertStack child,
bool  is_build 
)
static

Definition at line 1022 of file gist.c.

1023 {
1024  GISTInsertStack *parent = child->parent;
1025  ItemId iid;
1026  IndexTuple idxtuple;
1027  OffsetNumber maxoff;
1028  GISTInsertStack *ptr;
1029 
1030  gistcheckpage(r, parent->buffer);
1031  parent->page = (Page) BufferGetPage(parent->buffer);
1032  maxoff = PageGetMaxOffsetNumber(parent->page);
1033 
1034  /* Check if the downlink is still where it was before */
1035  if (child->downlinkoffnum != InvalidOffsetNumber && child->downlinkoffnum <= maxoff)
1036  {
1037  iid = PageGetItemId(parent->page, child->downlinkoffnum);
1038  idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
1039  if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
1040  return; /* still there */
1041  }
1042 
1043  /*
1044  * The page has changed since we looked. During normal operation, every
1045  * update of a page changes its LSN, so the LSN we memorized should have
1046  * changed too. During index build, however, we don't WAL-log the changes
1047  * until we have built the index, so the LSN doesn't change. There is no
1048  * concurrent activity during index build, but we might have changed the
1049  * parent ourselves.
1050  */
1051  Assert(parent->lsn != PageGetLSN(parent->page) || is_build);
1052 
1053  /*
1054  * Scan the page to re-find the downlink. If the page was split, it might
1055  * have moved to a different page, so follow the right links until we find
1056  * it.
1057  */
1058  while (true)
1059  {
1060  OffsetNumber i;
1061 
1062  maxoff = PageGetMaxOffsetNumber(parent->page);
1063  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1064  {
1065  iid = PageGetItemId(parent->page, i);
1066  idxtuple = (IndexTuple) PageGetItem(parent->page, iid);
1067  if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)
1068  {
1069  /* yes!!, found */
1070  child->downlinkoffnum = i;
1071  return;
1072  }
1073  }
1074 
1075  parent->blkno = GistPageGetOpaque(parent->page)->rightlink;
1077  UnlockReleaseBuffer(parent->buffer);
1078  if (parent->blkno == InvalidBlockNumber)
1079  {
1080  /*
1081  * End of chain and still didn't find parent. It's a very-very
1082  * rare situation when the root was split.
1083  */
1084  break;
1085  }
1086  parent->buffer = ReadBuffer(r, parent->blkno);
1087  LockBuffer(parent->buffer, GIST_EXCLUSIVE);
1088  gistcheckpage(r, parent->buffer);
1089  parent->page = (Page) BufferGetPage(parent->buffer);
1090  }
1091 
1092  /*
1093  * awful!!, we need search tree to find parent ... , but before we should
1094  * release all old parent
1095  */
1096 
1097  ptr = child->parent->parent; /* child->parent already released above */
1098  while (ptr)
1099  {
1100  ReleaseBuffer(ptr->buffer);
1101  ptr = ptr->parent;
1102  }
1103 
1104  /* ok, find new path */
1105  ptr = parent = gistFindPath(r, child->blkno, &child->downlinkoffnum);
1106 
1107  /* read all buffers as expected by caller */
1108  /* note we don't lock them or gistcheckpage them here! */
1109  while (ptr)
1110  {
1111  ptr->buffer = ReadBuffer(r, ptr->blkno);
1112  ptr->page = (Page) BufferGetPage(ptr->buffer);
1113  ptr = ptr->parent;
1114  }
1115 
1116  /* install new chain of parents to stack */
1117  child->parent = parent;
1118 
1119  /* make recursive call to normal processing */
1121  gistFindCorrectParent(r, child, is_build);
1122 }
static OffsetNumber PageGetMaxOffsetNumber(Page page)
Definition: bufpage.h:369
static GISTInsertStack * gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
Definition: gist.c:909
static void gistFindCorrectParent(Relation r, GISTInsertStack *child, bool is_build)
Definition: gist.c:1022
#define GistPageGetOpaque(page)
Definition: gist.h:167
int i
Definition: isn.c:73
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
#define FirstOffsetNumber
Definition: off.h:27

References Assert(), GISTInsertStack::blkno, GISTInsertStack::buffer, BufferGetPage(), GISTInsertStack::downlinkoffnum, FirstOffsetNumber, GIST_EXCLUSIVE, gistcheckpage(), gistFindPath(), GistPageGetOpaque, i, InvalidBlockNumber, InvalidOffsetNumber, ItemPointerGetBlockNumber(), LockBuffer(), GISTInsertStack::lsn, OffsetNumberNext, GISTInsertStack::page, PageGetItem(), PageGetItemId(), PageGetLSN(), PageGetMaxOffsetNumber(), GISTInsertStack::parent, ReadBuffer(), ReleaseBuffer(), IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistfinishsplit(), and gistformdownlink().

◆ gistFindPath()

static GISTInsertStack* gistFindPath ( Relation  r,
BlockNumber  child,
OffsetNumber downlinkoffnum 
)
static

Definition at line 909 of file gist.c.

910 {
911  Page page;
912  Buffer buffer;
913  OffsetNumber i,
914  maxoff;
915  ItemId iid;
916  IndexTuple idxtuple;
917  List *fifo;
918  GISTInsertStack *top,
919  *ptr;
920  BlockNumber blkno;
921 
922  top = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
923  top->blkno = GIST_ROOT_BLKNO;
925 
926  fifo = list_make1(top);
927  while (fifo != NIL)
928  {
929  /* Get next page to visit */
930  top = linitial(fifo);
931  fifo = list_delete_first(fifo);
932 
933  buffer = ReadBuffer(r, top->blkno);
934  LockBuffer(buffer, GIST_SHARE);
935  gistcheckpage(r, buffer);
936  page = (Page) BufferGetPage(buffer);
937 
938  if (GistPageIsLeaf(page))
939  {
940  /*
941  * Because we scan the index top-down, all the rest of the pages
942  * in the queue must be leaf pages as well.
943  */
944  UnlockReleaseBuffer(buffer);
945  break;
946  }
947 
948  /* currently, internal pages are never deleted */
949  Assert(!GistPageIsDeleted(page));
950 
951  top->lsn = BufferGetLSNAtomic(buffer);
952 
953  /*
954  * If F_FOLLOW_RIGHT is set, the page to the right doesn't have a
955  * downlink. This should not normally happen..
956  */
957  if (GistFollowRight(page))
958  elog(ERROR, "concurrent GiST page split was incomplete");
959 
960  if (top->parent && top->parent->lsn < GistPageGetNSN(page) &&
961  GistPageGetOpaque(page)->rightlink != InvalidBlockNumber /* sanity check */ )
962  {
963  /*
964  * Page was split while we looked elsewhere. We didn't see the
965  * downlink to the right page when we scanned the parent, so add
966  * it to the queue now.
967  *
968  * Put the right page ahead of the queue, so that we visit it
969  * next. That's important, because if this is the lowest internal
970  * level, just above leaves, we might already have queued up some
971  * leaf pages, and we assume that there can't be any non-leaf
972  * pages behind leaf pages.
973  */
974  ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
975  ptr->blkno = GistPageGetOpaque(page)->rightlink;
977  ptr->parent = top->parent;
978 
979  fifo = lcons(ptr, fifo);
980  }
981 
982  maxoff = PageGetMaxOffsetNumber(page);
983 
984  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
985  {
986  iid = PageGetItemId(page, i);
987  idxtuple = (IndexTuple) PageGetItem(page, iid);
988  blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
989  if (blkno == child)
990  {
991  /* Found it! */
992  UnlockReleaseBuffer(buffer);
993  *downlinkoffnum = i;
994  return top;
995  }
996  else
997  {
998  /* Append this child to the list of pages to visit later */
999  ptr = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack));
1000  ptr->blkno = blkno;
1001  ptr->downlinkoffnum = i;
1002  ptr->parent = top;
1003 
1004  fifo = lappend(fifo, ptr);
1005  }
1006  }
1007 
1008  UnlockReleaseBuffer(buffer);
1009  }
1010 
1011  elog(ERROR, "failed to re-find parent of a page in index \"%s\", block %u",
1012  RelationGetRelationName(r), child);
1013  return NULL; /* keep compiler quiet */
1014 }
#define elog(elevel,...)
Definition: elog.h:224
List * lappend(List *list, void *datum)
Definition: list.c:339
List * list_delete_first(List *list)
Definition: list.c:943
List * lcons(void *datum, List *list)
Definition: list.c:495
#define NIL
Definition: pg_list.h:68
#define list_make1(x1)
Definition: pg_list.h:212
#define linitial(l)
Definition: pg_list.h:178
Definition: pg_list.h:54

References Assert(), GISTInsertStack::blkno, BufferGetLSNAtomic(), BufferGetPage(), GISTInsertStack::downlinkoffnum, elog, ERROR, FirstOffsetNumber, GIST_ROOT_BLKNO, GIST_SHARE, gistcheckpage(), GistFollowRight, GistPageGetNSN, GistPageGetOpaque, GistPageIsDeleted, GistPageIsLeaf, i, InvalidBlockNumber, InvalidOffsetNumber, ItemPointerGetBlockNumber(), lappend(), lcons(), linitial, list_delete_first(), list_make1, LockBuffer(), GISTInsertStack::lsn, NIL, OffsetNumberNext, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), palloc0(), GISTInsertStack::parent, ReadBuffer(), RelationGetRelationName, IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistFindCorrectParent().

◆ gistfinishsplit()

static void gistfinishsplit ( GISTInsertState state,
GISTInsertStack stack,
GISTSTATE giststate,
List splitinfo,
bool  unlockbuf 
)
static

Definition at line 1342 of file gist.c.

1344 {
1345  GISTPageSplitInfo *right;
1346  GISTPageSplitInfo *left;
1347  IndexTuple tuples[2];
1348 
1349  /* A split always contains at least two halves */
1350  Assert(list_length(splitinfo) >= 2);
1351 
1352  /*
1353  * We need to insert downlinks for each new page, and update the downlink
1354  * for the original (leftmost) page in the split. Begin at the rightmost
1355  * page, inserting one downlink at a time until there's only two pages
1356  * left. Finally insert the downlink for the last new page and update the
1357  * downlink for the original page as one operation.
1358  */
1360 
1361  /*
1362  * Insert downlinks for the siblings from right to left, until there are
1363  * only two siblings left.
1364  */
1365  for (int pos = list_length(splitinfo) - 1; pos > 1; pos--)
1366  {
1367  right = (GISTPageSplitInfo *) list_nth(splitinfo, pos);
1368  left = (GISTPageSplitInfo *) list_nth(splitinfo, pos - 1);
1369 
1370  gistFindCorrectParent(state->r, stack, state->is_build);
1371  if (gistinserttuples(state, stack->parent, giststate,
1372  &right->downlink, 1,
1374  left->buf, right->buf, false, false))
1375  {
1376  /*
1377  * If the parent page was split, the existing downlink might have
1378  * moved.
1379  */
1381  }
1382  /* gistinserttuples() released the lock on right->buf. */
1383  }
1384 
1385  right = (GISTPageSplitInfo *) lsecond(splitinfo);
1386  left = (GISTPageSplitInfo *) linitial(splitinfo);
1387 
1388  /*
1389  * Finally insert downlink for the remaining right page and update the
1390  * downlink for the original page to not contain the tuples that were
1391  * moved to the new pages.
1392  */
1393  tuples[0] = left->downlink;
1394  tuples[1] = right->downlink;
1395  gistFindCorrectParent(state->r, stack, state->is_build);
1396  (void) gistinserttuples(state, stack->parent, giststate,
1397  tuples, 2,
1398  stack->downlinkoffnum,
1399  left->buf, right->buf,
1400  true, /* Unlock parent */
1401  unlockbuf /* Unlock stack->buffer if caller
1402  * wants that */
1403  );
1404 
1405  /*
1406  * The downlink might have moved when we updated it. Even if the page
1407  * wasn't split, because gistinserttuples() implements updating the old
1408  * tuple by removing and re-inserting it!
1409  */
1411 
1412  Assert(left->buf == stack->buffer);
1413 
1414  /*
1415  * If we split the page because we had to adjust the downlink on an
1416  * internal page, while descending the tree for inserting a new tuple,
1417  * then this might no longer be the correct page for the new tuple. The
1418  * downlink to this page might not cover the new tuple anymore, it might
1419  * need to go to the newly-created right sibling instead. Tell the caller
1420  * to walk back up the stack, to re-check at the parent which page to
1421  * insert to.
1422  *
1423  * Normally, the LSN-NSN interlock during the tree descend would also
1424  * detect that a concurrent split happened (by ourselves), and cause us to
1425  * retry at the parent. But that mechanism doesn't work during index
1426  * build, because we don't do WAL-logging, and don't update LSNs, during
1427  * index build.
1428  */
1429  stack->retry_from_parent = true;
1430 }
static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, IndexTuple *tuples, int ntup, OffsetNumber oldoffnum, Buffer leftchild, Buffer rightchild, bool unlockbuf, bool unlockleftchild)
Definition: gist.c:1282
static int list_length(const List *l)
Definition: pg_list.h:152
#define lsecond(l)
Definition: pg_list.h:183
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
IndexTuple downlink
Definition: gist_private.h:422

References Assert(), GISTPageSplitInfo::buf, GISTInsertStack::buffer, GISTPageSplitInfo::downlink, GISTInsertStack::downlinkoffnum, GIST_EXCLUSIVE, gistFindCorrectParent(), gistinserttuples(), InvalidOffsetNumber, linitial, list_length(), list_nth(), LockBuffer(), lsecond, GISTInsertStack::parent, and GISTInsertStack::retry_from_parent.

Referenced by gistfixsplit(), and gistinserttuples().

◆ gistfixsplit()

static void gistfixsplit ( GISTInsertState state,
GISTSTATE giststate 
)
static

Definition at line 1188 of file gist.c.

1189 {
1190  GISTInsertStack *stack = state->stack;
1191  Buffer buf;
1192  Page page;
1193  List *splitinfo = NIL;
1194 
1195  ereport(LOG,
1196  (errmsg("fixing incomplete split in index \"%s\", block %u",
1197  RelationGetRelationName(state->r), stack->blkno)));
1198 
1199  Assert(GistFollowRight(stack->page));
1201 
1202  buf = stack->buffer;
1203 
1204  /*
1205  * Read the chain of split pages, following the rightlinks. Construct a
1206  * downlink tuple for each page.
1207  */
1208  for (;;)
1209  {
1211  IndexTuple downlink;
1212 
1213  page = BufferGetPage(buf);
1214 
1215  /* Form the new downlink tuples to insert to parent */
1216  downlink = gistformdownlink(state->r, buf, giststate, stack, state->is_build);
1217 
1218  si->buf = buf;
1219  si->downlink = downlink;
1220 
1221  splitinfo = lappend(splitinfo, si);
1222 
1223  if (GistFollowRight(page))
1224  {
1225  /* lock next page */
1226  buf = ReadBuffer(state->r, GistPageGetOpaque(page)->rightlink);
1228  }
1229  else
1230  break;
1231  }
1232 
1233  /* Insert the downlinks */
1234  gistfinishsplit(state, stack, giststate, splitinfo, false);
1235 }
#define LOG
Definition: elog.h:31
static void gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack, GISTSTATE *giststate, List *splitinfo, bool unlockbuf)
Definition: gist.c:1342
static IndexTuple gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate, GISTInsertStack *stack, bool is_build)
Definition: gist.c:1128
void * palloc(Size size)
Definition: mcxt.c:1304
#define OffsetNumberIsValid(offsetNumber)
Definition: off.h:39
static char * buf
Definition: pg_test_fsync.c:73

References Assert(), GISTInsertStack::blkno, buf, GISTPageSplitInfo::buf, GISTInsertStack::buffer, BufferGetPage(), GISTPageSplitInfo::downlink, GISTInsertStack::downlinkoffnum, ereport, errmsg(), GIST_EXCLUSIVE, gistfinishsplit(), GistFollowRight, gistformdownlink(), GistPageGetOpaque, lappend(), LockBuffer(), LOG, NIL, OffsetNumberIsValid, GISTInsertStack::page, palloc(), ReadBuffer(), and RelationGetRelationName.

Referenced by gistdoinsert().

◆ gistformdownlink()

static IndexTuple gistformdownlink ( Relation  rel,
Buffer  buf,
GISTSTATE giststate,
GISTInsertStack stack,
bool  is_build 
)
static

Definition at line 1128 of file gist.c.

1130 {
1131  Page page = BufferGetPage(buf);
1132  OffsetNumber maxoff;
1133  OffsetNumber offset;
1134  IndexTuple downlink = NULL;
1135 
1136  maxoff = PageGetMaxOffsetNumber(page);
1137  for (offset = FirstOffsetNumber; offset <= maxoff; offset = OffsetNumberNext(offset))
1138  {
1139  IndexTuple ituple = (IndexTuple)
1140  PageGetItem(page, PageGetItemId(page, offset));
1141 
1142  if (downlink == NULL)
1143  downlink = CopyIndexTuple(ituple);
1144  else
1145  {
1146  IndexTuple newdownlink;
1147 
1148  newdownlink = gistgetadjusted(rel, downlink, ituple,
1149  giststate);
1150  if (newdownlink)
1151  downlink = newdownlink;
1152  }
1153  }
1154 
1155  /*
1156  * If the page is completely empty, we can't form a meaningful downlink
1157  * for it. But we have to insert a downlink for the page. Any key will do,
1158  * as long as its consistent with the downlink of parent page, so that we
1159  * can legally insert it to the parent. A minimal one that matches as few
1160  * scans as possible would be best, to keep scans from doing useless work,
1161  * but we don't know how to construct that. So we just use the downlink of
1162  * the original page that was split - that's as far from optimal as it can
1163  * get but will do..
1164  */
1165  if (!downlink)
1166  {
1167  ItemId iid;
1168 
1170  gistFindCorrectParent(rel, stack, is_build);
1171  iid = PageGetItemId(stack->parent->page, stack->downlinkoffnum);
1172  downlink = (IndexTuple) PageGetItem(stack->parent->page, iid);
1173  downlink = CopyIndexTuple(downlink);
1174  LockBuffer(stack->parent->buffer, GIST_UNLOCK);
1175  }
1176 
1178  GistTupleSetValid(downlink);
1179 
1180  return downlink;
1181 }
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:3377
#define GistTupleSetValid(itup)
Definition: gist_private.h:289
IndexTuple CopyIndexTuple(IndexTuple source)
Definition: indextuple.c:547
static void ItemPointerSetBlockNumber(ItemPointerData *pointer, BlockNumber blockNumber)
Definition: itemptr.h:147

References buf, GISTInsertStack::buffer, BufferGetBlockNumber(), BufferGetPage(), CopyIndexTuple(), GISTInsertStack::downlinkoffnum, FirstOffsetNumber, GIST_EXCLUSIVE, GIST_UNLOCK, gistFindCorrectParent(), gistgetadjusted(), GistTupleSetValid, ItemPointerSetBlockNumber(), LockBuffer(), OffsetNumberNext, GISTInsertStack::page, PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), GISTInsertStack::parent, and IndexTupleData::t_tid.

Referenced by gistfixsplit().

◆ gisthandler()

Datum gisthandler ( PG_FUNCTION_ARGS  )

Definition at line 59 of file gist.c.

60 {
62 
63  amroutine->amstrategies = 0;
64  amroutine->amsupport = GISTNProcs;
65  amroutine->amoptsprocnum = GIST_OPTIONS_PROC;
66  amroutine->amcanorder = false;
67  amroutine->amcanorderbyop = true;
68  amroutine->amcanbackward = false;
69  amroutine->amcanunique = false;
70  amroutine->amcanmulticol = true;
71  amroutine->amoptionalkey = true;
72  amroutine->amsearcharray = false;
73  amroutine->amsearchnulls = true;
74  amroutine->amstorage = true;
75  amroutine->amclusterable = true;
76  amroutine->ampredlocks = true;
77  amroutine->amcanparallel = false;
78  amroutine->amcanbuildparallel = false;
79  amroutine->amcaninclude = true;
80  amroutine->amusemaintenanceworkmem = false;
81  amroutine->amsummarizing = false;
82  amroutine->amparallelvacuumoptions =
84  amroutine->amkeytype = InvalidOid;
85 
86  amroutine->ambuild = gistbuild;
87  amroutine->ambuildempty = gistbuildempty;
88  amroutine->aminsert = gistinsert;
89  amroutine->aminsertcleanup = NULL;
90  amroutine->ambulkdelete = gistbulkdelete;
92  amroutine->amcanreturn = gistcanreturn;
93  amroutine->amcostestimate = gistcostestimate;
94  amroutine->amoptions = gistoptions;
95  amroutine->amproperty = gistproperty;
96  amroutine->ambuildphasename = NULL;
97  amroutine->amvalidate = gistvalidate;
99  amroutine->ambeginscan = gistbeginscan;
100  amroutine->amrescan = gistrescan;
101  amroutine->amgettuple = gistgettuple;
102  amroutine->amgetbitmap = gistgetbitmap;
103  amroutine->amendscan = gistendscan;
104  amroutine->ammarkpos = NULL;
105  amroutine->amrestrpos = NULL;
106  amroutine->amestimateparallelscan = NULL;
107  amroutine->aminitparallelscan = NULL;
108  amroutine->amparallelrescan = NULL;
109 
110  PG_RETURN_POINTER(amroutine);
111 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
bool gistinsert(Relation r, Datum *values, bool *isnull, ItemPointer ht_ctid, Relation heapRel, IndexUniqueCheck checkUnique, bool indexUnchanged, IndexInfo *indexInfo)
Definition: gist.c:159
void gistbuildempty(Relation index)
Definition: gist.c:133
#define GISTNProcs
Definition: gist.h:43
#define GIST_OPTIONS_PROC
Definition: gist.h:40
IndexBuildResult * gistbuild(Relation heap, Relation index, IndexInfo *indexInfo)
Definition: gistbuild.c:179
bool gistgettuple(IndexScanDesc scan, ScanDirection dir)
Definition: gistget.c:612
int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
Definition: gistget.c:743
bool gistcanreturn(Relation index, int attno)
Definition: gistget.c:793
IndexScanDesc gistbeginscan(Relation r, int nkeys, int norderbys)
Definition: gistscan.c:74
void gistendscan(IndexScanDesc scan)
Definition: gistscan.c:349
void gistrescan(IndexScanDesc scan, ScanKey key, int nkeys, ScanKey orderbys, int norderbys)
Definition: gistscan.c:127
bool gistproperty(Oid index_oid, int attno, IndexAMProperty prop, const char *propname, bool *res, bool *isnull)
Definition: gistutil.c:933
bytea * gistoptions(Datum reloptions, bool validate)
Definition: gistutil.c:912
IndexBulkDeleteResult * gistbulkdelete(IndexVacuumInfo *info, IndexBulkDeleteResult *stats, IndexBulkDeleteCallback callback, void *callback_state)
Definition: gistvacuum.c:59
IndexBulkDeleteResult * gistvacuumcleanup(IndexVacuumInfo *info, IndexBulkDeleteResult *stats)
Definition: gistvacuum.c:75
void gistadjustmembers(Oid opfamilyoid, Oid opclassoid, List *operators, List *functions)
Definition: gistvalidate.c:295
bool gistvalidate(Oid opclassoid)
Definition: gistvalidate.c:33
#define makeNode(_type_)
Definition: nodes.h:155
#define InvalidOid
Definition: postgres_ext.h:36
void gistcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
Definition: selfuncs.c:7128
ambuildphasename_function ambuildphasename
Definition: amapi.h:276
ambuildempty_function ambuildempty
Definition: amapi.h:267
amvacuumcleanup_function amvacuumcleanup
Definition: amapi.h:271
bool amclusterable
Definition: amapi.h:241
amoptions_function amoptions
Definition: amapi.h:274
amestimateparallelscan_function amestimateparallelscan
Definition: amapi.h:288
amrestrpos_function amrestrpos
Definition: amapi.h:285
aminsert_function aminsert
Definition: amapi.h:268
amendscan_function amendscan
Definition: amapi.h:283
uint16 amoptsprocnum
Definition: amapi.h:221
amparallelrescan_function amparallelrescan
Definition: amapi.h:290
Oid amkeytype
Definition: amapi.h:257
bool ampredlocks
Definition: amapi.h:243
uint16 amsupport
Definition: amapi.h:219
amcostestimate_function amcostestimate
Definition: amapi.h:273
bool amcanorderbyop
Definition: amapi.h:225
amadjustmembers_function amadjustmembers
Definition: amapi.h:278
ambuild_function ambuild
Definition: amapi.h:266
bool amstorage
Definition: amapi.h:239
uint16 amstrategies
Definition: amapi.h:217
bool amoptionalkey
Definition: amapi.h:233
amgettuple_function amgettuple
Definition: amapi.h:281
amcanreturn_function amcanreturn
Definition: amapi.h:272
bool amcanunique
Definition: amapi.h:229
amgetbitmap_function amgetbitmap
Definition: amapi.h:282
amproperty_function amproperty
Definition: amapi.h:275
ambulkdelete_function ambulkdelete
Definition: amapi.h:270
bool amsearcharray
Definition: amapi.h:235
bool amsummarizing
Definition: amapi.h:253
amvalidate_function amvalidate
Definition: amapi.h:277
ammarkpos_function ammarkpos
Definition: amapi.h:284
bool amcanmulticol
Definition: amapi.h:231
bool amusemaintenanceworkmem
Definition: amapi.h:251
ambeginscan_function ambeginscan
Definition: amapi.h:279
bool amcanparallel
Definition: amapi.h:245
amrescan_function amrescan
Definition: amapi.h:280
bool amcanorder
Definition: amapi.h:223
bool amcanbuildparallel
Definition: amapi.h:247
aminitparallelscan_function aminitparallelscan
Definition: amapi.h:289
uint8 amparallelvacuumoptions
Definition: amapi.h:255
aminsertcleanup_function aminsertcleanup
Definition: amapi.h:269
bool amcanbackward
Definition: amapi.h:227
bool amcaninclude
Definition: amapi.h:249
bool amsearchnulls
Definition: amapi.h:237
#define VACUUM_OPTION_PARALLEL_BULKDEL
Definition: vacuum.h:47
#define VACUUM_OPTION_PARALLEL_COND_CLEANUP
Definition: vacuum.h:54

References IndexAmRoutine::amadjustmembers, IndexAmRoutine::ambeginscan, IndexAmRoutine::ambuild, IndexAmRoutine::ambuildempty, IndexAmRoutine::ambuildphasename, IndexAmRoutine::ambulkdelete, IndexAmRoutine::amcanbackward, IndexAmRoutine::amcanbuildparallel, IndexAmRoutine::amcaninclude, IndexAmRoutine::amcanmulticol, IndexAmRoutine::amcanorder, IndexAmRoutine::amcanorderbyop, IndexAmRoutine::amcanparallel, IndexAmRoutine::amcanreturn, IndexAmRoutine::amcanunique, IndexAmRoutine::amclusterable, IndexAmRoutine::amcostestimate, IndexAmRoutine::amendscan, IndexAmRoutine::amestimateparallelscan, IndexAmRoutine::amgetbitmap, IndexAmRoutine::amgettuple, IndexAmRoutine::aminitparallelscan, IndexAmRoutine::aminsert, IndexAmRoutine::aminsertcleanup, IndexAmRoutine::amkeytype, IndexAmRoutine::ammarkpos, IndexAmRoutine::amoptionalkey, IndexAmRoutine::amoptions, IndexAmRoutine::amoptsprocnum, IndexAmRoutine::amparallelrescan, IndexAmRoutine::amparallelvacuumoptions, IndexAmRoutine::ampredlocks, IndexAmRoutine::amproperty, IndexAmRoutine::amrescan, IndexAmRoutine::amrestrpos, IndexAmRoutine::amsearcharray, IndexAmRoutine::amsearchnulls, IndexAmRoutine::amstorage, IndexAmRoutine::amstrategies, IndexAmRoutine::amsummarizing, IndexAmRoutine::amsupport, IndexAmRoutine::amusemaintenanceworkmem, IndexAmRoutine::amvacuumcleanup, IndexAmRoutine::amvalidate, GIST_OPTIONS_PROC, gistadjustmembers(), gistbeginscan(), gistbuild(), gistbuildempty(), gistbulkdelete(), gistcanreturn(), gistcostestimate(), gistendscan(), gistgetbitmap(), gistgettuple(), gistinsert(), GISTNProcs, gistoptions(), gistproperty(), gistrescan(), gistvacuumcleanup(), gistvalidate(), InvalidOid, makeNode, PG_RETURN_POINTER, VACUUM_OPTION_PARALLEL_BULKDEL, and VACUUM_OPTION_PARALLEL_COND_CLEANUP.

◆ gistinsert()

bool gistinsert ( Relation  r,
Datum values,
bool isnull,
ItemPointer  ht_ctid,
Relation  heapRel,
IndexUniqueCheck  checkUnique,
bool  indexUnchanged,
IndexInfo indexInfo 
)

Definition at line 159 of file gist.c.

164 {
165  GISTSTATE *giststate = (GISTSTATE *) indexInfo->ii_AmCache;
166  IndexTuple itup;
167  MemoryContext oldCxt;
168 
169  /* Initialize GISTSTATE cache if first call in this statement */
170  if (giststate == NULL)
171  {
172  oldCxt = MemoryContextSwitchTo(indexInfo->ii_Context);
173  giststate = initGISTstate(r);
174  giststate->tempCxt = createTempGistContext();
175  indexInfo->ii_AmCache = (void *) giststate;
176  MemoryContextSwitchTo(oldCxt);
177  }
178 
179  oldCxt = MemoryContextSwitchTo(giststate->tempCxt);
180 
181  itup = gistFormTuple(giststate, r,
182  values, isnull, true /* size is currently bogus */ );
183  itup->t_tid = *ht_ctid;
184 
185  gistdoinsert(r, itup, 0, giststate, heapRel, false);
186 
187  /* cleanup */
188  MemoryContextSwitchTo(oldCxt);
189  MemoryContextReset(giststate->tempCxt);
190 
191  return false;
192 }
static Datum values[MAXATTR]
Definition: bootstrap.c:152
void gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate, Relation heapRel, bool is_build)
Definition: gist.c:634
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1525
MemoryContext createTempGistContext(void)
Definition: gist.c:122
IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, const Datum *attdata, const bool *isnull, bool isleaf)
Definition: gistutil.c:575
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:371
MemoryContextSwitchTo(old_ctx)
MemoryContext tempCxt
Definition: gist_private.h:78
void * ii_AmCache
Definition: execnodes.h:207
MemoryContext ii_Context
Definition: execnodes.h:208

References createTempGistContext(), gistdoinsert(), gistFormTuple(), if(), IndexInfo::ii_AmCache, IndexInfo::ii_Context, initGISTstate(), MemoryContextReset(), MemoryContextSwitchTo(), GISTSTATE::tempCxt, and values.

Referenced by gisthandler().

◆ gistinserttuple()

static bool gistinserttuple ( GISTInsertState state,
GISTInsertStack stack,
GISTSTATE giststate,
IndexTuple  tuple,
OffsetNumber  oldoffnum 
)
static

Definition at line 1248 of file gist.c.

1250 {
1251  return gistinserttuples(state, stack, giststate, &tuple, 1, oldoffnum,
1252  InvalidBuffer, InvalidBuffer, false, false);
1253 }

References gistinserttuples(), and InvalidBuffer.

Referenced by gistdoinsert().

◆ gistinserttuples()

static bool gistinserttuples ( GISTInsertState state,
GISTInsertStack stack,
GISTSTATE giststate,
IndexTuple tuples,
int  ntup,
OffsetNumber  oldoffnum,
Buffer  leftchild,
Buffer  rightchild,
bool  unlockbuf,
bool  unlockleftchild 
)
static

Definition at line 1282 of file gist.c.

1287 {
1288  List *splitinfo;
1289  bool is_split;
1290 
1291  /*
1292  * Check for any rw conflicts (in serializable isolation level) just
1293  * before we intend to modify the page
1294  */
1296 
1297  /* Insert the tuple(s) to the page, splitting the page if necessary */
1298  is_split = gistplacetopage(state->r, state->freespace, giststate,
1299  stack->buffer,
1300  tuples, ntup,
1301  oldoffnum, NULL,
1302  leftchild,
1303  &splitinfo,
1304  true,
1305  state->heapRel,
1306  state->is_build);
1307 
1308  /*
1309  * Before recursing up in case the page was split, release locks on the
1310  * child pages. We don't need to keep them locked when updating the
1311  * parent.
1312  */
1315  if (BufferIsValid(leftchild) && unlockleftchild)
1317 
1318  /*
1319  * If we had to split, insert/update the downlinks in the parent. If the
1320  * caller requested us to release the lock on stack->buffer, tell
1321  * gistfinishsplit() to do that as soon as it's safe to do so. If we
1322  * didn't have to split, release it ourselves.
1323  */
1324  if (splitinfo)
1325  gistfinishsplit(state, stack, giststate, splitinfo, unlockbuf);
1326  else if (unlockbuf)
1327  LockBuffer(stack->buffer, GIST_UNLOCK);
1328 
1329  return is_split;
1330 }
static bool BufferIsValid(Buffer bufnum)
Definition: bufmgr.h:301
#define rightchild(x)
Definition: fsmpage.c:30
#define leftchild(x)
Definition: fsmpage.c:29
bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber *newblkno, Buffer leftchildbuf, List **splitinfo, bool markfollowright, Relation heapRel, bool is_build)
Definition: gist.c:225
void CheckForSerializableConflictIn(Relation relation, ItemPointer tid, BlockNumber blkno)
Definition: predicate.c:4316

References GISTInsertStack::buffer, BufferGetBlockNumber(), BufferIsValid(), CheckForSerializableConflictIn(), GIST_UNLOCK, gistfinishsplit(), gistplacetopage(), leftchild, LockBuffer(), rightchild, and UnlockReleaseBuffer().

Referenced by gistfinishsplit(), and gistinserttuple().

◆ gistplacetopage()

bool gistplacetopage ( Relation  rel,
Size  freespace,
GISTSTATE giststate,
Buffer  buffer,
IndexTuple itup,
int  ntup,
OffsetNumber  oldoffnum,
BlockNumber newblkno,
Buffer  leftchildbuf,
List **  splitinfo,
bool  markfollowright,
Relation  heapRel,
bool  is_build 
)

Definition at line 225 of file gist.c.

234 {
235  BlockNumber blkno = BufferGetBlockNumber(buffer);
236  Page page = BufferGetPage(buffer);
237  bool is_leaf = (GistPageIsLeaf(page)) ? true : false;
238  XLogRecPtr recptr;
239  bool is_split;
240 
241  /*
242  * Refuse to modify a page that's incompletely split. This should not
243  * happen because we finish any incomplete splits while we walk down the
244  * tree. However, it's remotely possible that another concurrent inserter
245  * splits a parent page, and errors out before completing the split. We
246  * will just throw an error in that case, and leave any split we had in
247  * progress unfinished too. The next insert that comes along will clean up
248  * the mess.
249  */
250  if (GistFollowRight(page))
251  elog(ERROR, "concurrent GiST page split was incomplete");
252 
253  /* should never try to insert to a deleted page */
254  Assert(!GistPageIsDeleted(page));
255 
256  *splitinfo = NIL;
257 
258  /*
259  * if isupdate, remove old key: This node's key has been modified, either
260  * because a child split occurred or because we needed to adjust our key
261  * for an insert in a child node. Therefore, remove the old version of
262  * this node's key.
263  *
264  * for WAL replay, in the non-split case we handle this by setting up a
265  * one-element todelete array; in the split case, it's handled implicitly
266  * because the tuple vector passed to gistSplit won't include this tuple.
267  */
268  is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
269 
270  /*
271  * If leaf page is full, try at first to delete dead tuples. And then
272  * check again.
273  */
274  if (is_split && GistPageIsLeaf(page) && GistPageHasGarbage(page))
275  {
276  gistprunepage(rel, page, buffer, heapRel);
277  is_split = gistnospace(page, itup, ntup, oldoffnum, freespace);
278  }
279 
280  if (is_split)
281  {
282  /* no space for insertion */
283  IndexTuple *itvec;
284  int tlen;
285  SplitPageLayout *dist = NULL,
286  *ptr;
287  BlockNumber oldrlink = InvalidBlockNumber;
288  GistNSN oldnsn = 0;
289  SplitPageLayout rootpg;
290  bool is_rootsplit;
291  int npage;
292 
293  is_rootsplit = (blkno == GIST_ROOT_BLKNO);
294 
295  /*
296  * Form index tuples vector to split. If we're replacing an old tuple,
297  * remove the old version from the vector.
298  */
299  itvec = gistextractpage(page, &tlen);
300  if (OffsetNumberIsValid(oldoffnum))
301  {
302  /* on inner page we should remove old tuple */
303  int pos = oldoffnum - FirstOffsetNumber;
304 
305  tlen--;
306  if (pos != tlen)
307  memmove(itvec + pos, itvec + pos + 1, sizeof(IndexTuple) * (tlen - pos));
308  }
309  itvec = gistjoinvector(itvec, &tlen, itup, ntup);
310  dist = gistSplit(rel, page, itvec, tlen, giststate);
311 
312  /*
313  * Check that split didn't produce too many pages.
314  */
315  npage = 0;
316  for (ptr = dist; ptr; ptr = ptr->next)
317  npage++;
318  /* in a root split, we'll add one more page to the list below */
319  if (is_rootsplit)
320  npage++;
321  if (npage > GIST_MAX_SPLIT_PAGES)
322  elog(ERROR, "GiST page split into too many halves (%d, maximum %d)",
323  npage, GIST_MAX_SPLIT_PAGES);
324 
325  /*
326  * Set up pages to work with. Allocate new buffers for all but the
327  * leftmost page. The original page becomes the new leftmost page, and
328  * is just replaced with the new contents.
329  *
330  * For a root-split, allocate new buffers for all child pages, the
331  * original page is overwritten with new root page containing
332  * downlinks to the new child pages.
333  */
334  ptr = dist;
335  if (!is_rootsplit)
336  {
337  /* save old rightlink and NSN */
338  oldrlink = GistPageGetOpaque(page)->rightlink;
339  oldnsn = GistPageGetNSN(page);
340 
341  dist->buffer = buffer;
342  dist->block.blkno = BufferGetBlockNumber(buffer);
344 
345  /* clean all flags except F_LEAF */
346  GistPageGetOpaque(dist->page)->flags = (is_leaf) ? F_LEAF : 0;
347 
348  ptr = ptr->next;
349  }
350  for (; ptr; ptr = ptr->next)
351  {
352  /* Allocate new page */
353  ptr->buffer = gistNewBuffer(rel, heapRel);
354  GISTInitBuffer(ptr->buffer, (is_leaf) ? F_LEAF : 0);
355  ptr->page = BufferGetPage(ptr->buffer);
356  ptr->block.blkno = BufferGetBlockNumber(ptr->buffer);
358  BufferGetBlockNumber(buffer),
359  BufferGetBlockNumber(ptr->buffer));
360  }
361 
362  /*
363  * Now that we know which blocks the new pages go to, set up downlink
364  * tuples to point to them.
365  */
366  for (ptr = dist; ptr; ptr = ptr->next)
367  {
368  ItemPointerSetBlockNumber(&(ptr->itup->t_tid), ptr->block.blkno);
369  GistTupleSetValid(ptr->itup);
370  }
371 
372  /*
373  * If this is a root split, we construct the new root page with the
374  * downlinks here directly, instead of requiring the caller to insert
375  * them. Add the new root page to the list along with the child pages.
376  */
377  if (is_rootsplit)
378  {
379  IndexTuple *downlinks;
380  int ndownlinks = 0;
381  int i;
382 
383  rootpg.buffer = buffer;
385  GistPageGetOpaque(rootpg.page)->flags = 0;
386 
387  /* Prepare a vector of all the downlinks */
388  for (ptr = dist; ptr; ptr = ptr->next)
389  ndownlinks++;
390  downlinks = palloc(sizeof(IndexTuple) * ndownlinks);
391  for (i = 0, ptr = dist; ptr; ptr = ptr->next)
392  downlinks[i++] = ptr->itup;
393 
394  rootpg.block.blkno = GIST_ROOT_BLKNO;
395  rootpg.block.num = ndownlinks;
396  rootpg.list = gistfillitupvec(downlinks, ndownlinks,
397  &(rootpg.lenlist));
398  rootpg.itup = NULL;
399 
400  rootpg.next = dist;
401  dist = &rootpg;
402  }
403  else
404  {
405  /* Prepare split-info to be returned to caller */
406  for (ptr = dist; ptr; ptr = ptr->next)
407  {
409 
410  si->buf = ptr->buffer;
411  si->downlink = ptr->itup;
412  *splitinfo = lappend(*splitinfo, si);
413  }
414  }
415 
416  /*
417  * Fill all pages. All the pages are new, ie. freshly allocated empty
418  * pages, or a temporary copy of the old page.
419  */
420  for (ptr = dist; ptr; ptr = ptr->next)
421  {
422  char *data = (char *) (ptr->list);
423 
424  for (int i = 0; i < ptr->block.num; i++)
425  {
426  IndexTuple thistup = (IndexTuple) data;
427 
428  if (PageAddItem(ptr->page, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
429  elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(rel));
430 
431  /*
432  * If this is the first inserted/updated tuple, let the caller
433  * know which page it landed on.
434  */
435  if (newblkno && ItemPointerEquals(&thistup->t_tid, &(*itup)->t_tid))
436  *newblkno = ptr->block.blkno;
437 
438  data += IndexTupleSize(thistup);
439  }
440 
441  /* Set up rightlinks */
442  if (ptr->next && ptr->block.blkno != GIST_ROOT_BLKNO)
443  GistPageGetOpaque(ptr->page)->rightlink =
444  ptr->next->block.blkno;
445  else
446  GistPageGetOpaque(ptr->page)->rightlink = oldrlink;
447 
448  /*
449  * Mark the all but the right-most page with the follow-right
450  * flag. It will be cleared as soon as the downlink is inserted
451  * into the parent, but this ensures that if we error out before
452  * that, the index is still consistent. (in buffering build mode,
453  * any error will abort the index build anyway, so this is not
454  * needed.)
455  */
456  if (ptr->next && !is_rootsplit && markfollowright)
457  GistMarkFollowRight(ptr->page);
458  else
459  GistClearFollowRight(ptr->page);
460 
461  /*
462  * Copy the NSN of the original page to all pages. The
463  * F_FOLLOW_RIGHT flags ensure that scans will follow the
464  * rightlinks until the downlinks are inserted.
465  */
466  GistPageSetNSN(ptr->page, oldnsn);
467  }
468 
469  /*
470  * gistXLogSplit() needs to WAL log a lot of pages, prepare WAL
471  * insertion for that. NB: The number of pages and data segments
472  * specified here must match the calculations in gistXLogSplit()!
473  */
474  if (!is_build && RelationNeedsWAL(rel))
475  XLogEnsureRecordSpace(npage, 1 + npage * 2);
476 
478 
479  /*
480  * Must mark buffers dirty before XLogInsert, even though we'll still
481  * be changing their opaque fields below.
482  */
483  for (ptr = dist; ptr; ptr = ptr->next)
484  MarkBufferDirty(ptr->buffer);
485  if (BufferIsValid(leftchildbuf))
486  MarkBufferDirty(leftchildbuf);
487 
488  /*
489  * The first page in the chain was a temporary working copy meant to
490  * replace the old page. Copy it over the old page.
491  */
493  dist->page = BufferGetPage(dist->buffer);
494 
495  /*
496  * Write the WAL record.
497  *
498  * If we're building a new index, however, we don't WAL-log changes
499  * yet. The LSN-NSN interlock between parent and child requires that
500  * LSNs never move backwards, so set the LSNs to a value that's
501  * smaller than any real or fake unlogged LSN that might be generated
502  * later. (There can't be any concurrent scans during index build, so
503  * we don't need to be able to detect concurrent splits yet.)
504  */
505  if (is_build)
506  recptr = GistBuildLSN;
507  else
508  {
509  if (RelationNeedsWAL(rel))
510  recptr = gistXLogSplit(is_leaf,
511  dist, oldrlink, oldnsn, leftchildbuf,
512  markfollowright);
513  else
514  recptr = gistGetFakeLSN(rel);
515  }
516 
517  for (ptr = dist; ptr; ptr = ptr->next)
518  PageSetLSN(ptr->page, recptr);
519 
520  /*
521  * Return the new child buffers to the caller.
522  *
523  * If this was a root split, we've already inserted the downlink
524  * pointers, in the form of a new root page. Therefore we can release
525  * all the new buffers, and keep just the root page locked.
526  */
527  if (is_rootsplit)
528  {
529  for (ptr = dist->next; ptr; ptr = ptr->next)
530  UnlockReleaseBuffer(ptr->buffer);
531  }
532  }
533  else
534  {
535  /*
536  * Enough space. We always get here if ntup==0.
537  */
539 
540  /*
541  * Delete old tuple if any, then insert new tuple(s) if any. If
542  * possible, use the fast path of PageIndexTupleOverwrite.
543  */
544  if (OffsetNumberIsValid(oldoffnum))
545  {
546  if (ntup == 1)
547  {
548  /* One-for-one replacement, so use PageIndexTupleOverwrite */
549  if (!PageIndexTupleOverwrite(page, oldoffnum, (Item) *itup,
550  IndexTupleSize(*itup)))
551  elog(ERROR, "failed to add item to index page in \"%s\"",
553  }
554  else
555  {
556  /* Delete old, then append new tuple(s) to page */
557  PageIndexTupleDelete(page, oldoffnum);
558  gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
559  }
560  }
561  else
562  {
563  /* Just append new tuples at the end of the page */
564  gistfillbuffer(page, itup, ntup, InvalidOffsetNumber);
565  }
566 
567  MarkBufferDirty(buffer);
568 
569  if (BufferIsValid(leftchildbuf))
570  MarkBufferDirty(leftchildbuf);
571 
572  if (is_build)
573  recptr = GistBuildLSN;
574  else
575  {
576  if (RelationNeedsWAL(rel))
577  {
578  OffsetNumber ndeloffs = 0,
579  deloffs[1];
580 
581  if (OffsetNumberIsValid(oldoffnum))
582  {
583  deloffs[0] = oldoffnum;
584  ndeloffs = 1;
585  }
586 
587  recptr = gistXLogUpdate(buffer,
588  deloffs, ndeloffs, itup, ntup,
589  leftchildbuf);
590  }
591  else
592  recptr = gistGetFakeLSN(rel);
593  }
594  PageSetLSN(page, recptr);
595 
596  if (newblkno)
597  *newblkno = blkno;
598  }
599 
600  /*
601  * If we inserted the downlink for a child page, set NSN and clear
602  * F_FOLLOW_RIGHT flag on the left child, so that concurrent scans know to
603  * follow the rightlink if and only if they looked at the parent page
604  * before we inserted the downlink.
605  *
606  * Note that we do this *after* writing the WAL record. That means that
607  * the possible full page image in the WAL record does not include these
608  * changes, and they must be replayed even if the page is restored from
609  * the full page image. There's a chicken-and-egg problem: if we updated
610  * the child pages first, we wouldn't know the recptr of the WAL record
611  * we're about to write.
612  */
613  if (BufferIsValid(leftchildbuf))
614  {
615  Page leftpg = BufferGetPage(leftchildbuf);
616 
617  GistPageSetNSN(leftpg, recptr);
618  GistClearFollowRight(leftpg);
619 
620  PageSetLSN(leftpg, recptr);
621  }
622 
624 
625  return is_split;
626 }
void PageRestoreTempPage(Page tempPage, Page oldPage)
Definition: bufpage.c:424
Page PageGetTempPageCopySpecial(Page page)
Definition: bufpage.c:402
bool PageIndexTupleOverwrite(Page page, OffsetNumber offnum, Item newtup, Size newsize)
Definition: bufpage.c:1405
void PageIndexTupleDelete(Page page, OffsetNumber offnum)
Definition: bufpage.c:1052
static void PageSetLSN(Page page, XLogRecPtr lsn)
Definition: bufpage.h:388
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
Definition: bufpage.h:468
static void gistprunepage(Relation rel, Page page, Buffer buffer, Relation heapRel)
Definition: gist.c:1664
SplitPageLayout * gistSplit(Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate)
Definition: gist.c:1438
#define GistMarkFollowRight(page)
Definition: gist.h:183
#define GistClearFollowRight(page)
Definition: gist.h:184
#define GistPageSetNSN(page, val)
Definition: gist.h:187
#define GistPageHasGarbage(page)
Definition: gist.h:178
XLogRecPtr GistNSN
Definition: gist.h:62
#define GistBuildLSN
Definition: gist.h:69
#define GIST_MAX_SPLIT_PAGES
Definition: gist_private.h:39
Buffer gistNewBuffer(Relation r, Relation heaprel)
Definition: gistutil.c:824
bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace)
Definition: gistutil.c:59
void gistfillbuffer(Page page, IndexTuple *itup, int len, OffsetNumber off)
Definition: gistutil.c:34
IndexTuple * gistextractpage(Page page, int *len)
Definition: gistutil.c:95
XLogRecPtr gistGetFakeLSN(Relation rel)
Definition: gistutil.c:1016
IndexTuple * gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
Definition: gistutil.c:114
IndexTupleData * gistfillitupvec(IndexTuple *vec, int veclen, int *memlen)
Definition: gistutil.c:127
XLogRecPtr gistXLogSplit(bool page_is_leaf, SplitPageLayout *dist, BlockNumber origrlink, GistNSN orignsn, Buffer leftchildbuf, bool markfollowright)
Definition: gistxlog.c:495
XLogRecPtr gistXLogUpdate(Buffer buffer, OffsetNumber *todelete, int ntodelete, IndexTuple *itup, int ituplen, Buffer leftchildbuf)
Definition: gistxlog.c:629
Pointer Item
Definition: item.h:17
bool ItemPointerEquals(ItemPointer pointer1, ItemPointer pointer2)
Definition: itemptr.c:35
#define IndexTupleSize(itup)
Definition: itup.h:70
const void * data
void PredicateLockPageSplit(Relation relation, BlockNumber oldblkno, BlockNumber newblkno)
Definition: predicate.c:3124
gistxlogPage block
Definition: gist_private.h:193
struct SplitPageLayout * next
Definition: gist_private.h:200
IndexTuple itup
Definition: gist_private.h:196
IndexTupleData * list
Definition: gist_private.h:194
BlockNumber blkno
Definition: gist_private.h:186
uint64 XLogRecPtr
Definition: xlogdefs.h:21
void XLogEnsureRecordSpace(int max_block_id, int ndatas)
Definition: xloginsert.c:175

References Assert(), gistxlogPage::blkno, SplitPageLayout::block, GISTPageSplitInfo::buf, SplitPageLayout::buffer, BufferGetBlockNumber(), BufferGetPage(), BufferIsValid(), data, GISTPageSplitInfo::downlink, elog, END_CRIT_SECTION, ERROR, F_LEAF, FirstOffsetNumber, GIST_MAX_SPLIT_PAGES, GIST_ROOT_BLKNO, GistBuildLSN, GistClearFollowRight, gistextractpage(), gistfillbuffer(), gistfillitupvec(), GistFollowRight, gistGetFakeLSN(), GISTInitBuffer(), gistjoinvector(), GistMarkFollowRight, gistNewBuffer(), gistnospace(), GistPageGetNSN, GistPageGetOpaque, GistPageHasGarbage, GistPageIsDeleted, GistPageIsLeaf, GistPageSetNSN, gistprunepage(), gistSplit(), GistTupleSetValid, gistXLogSplit(), gistXLogUpdate(), i, IndexTupleSize, InvalidBlockNumber, InvalidOffsetNumber, ItemPointerEquals(), ItemPointerSetBlockNumber(), SplitPageLayout::itup, lappend(), SplitPageLayout::lenlist, SplitPageLayout::list, MarkBufferDirty(), SplitPageLayout::next, NIL, gistxlogPage::num, OffsetNumberIsValid, SplitPageLayout::page, PageAddItem, PageGetTempPageCopySpecial(), PageIndexTupleDelete(), PageIndexTupleOverwrite(), PageRestoreTempPage(), PageSetLSN(), palloc(), PredicateLockPageSplit(), RelationGetRelationName, RelationNeedsWAL, START_CRIT_SECTION, IndexTupleData::t_tid, UnlockReleaseBuffer(), and XLogEnsureRecordSpace().

Referenced by gistbufferinginserttuples(), and gistinserttuples().

◆ gistprunepage()

static void gistprunepage ( Relation  rel,
Page  page,
Buffer  buffer,
Relation  heapRel 
)
static

Definition at line 1664 of file gist.c.

1665 {
1667  int ndeletable = 0;
1668  OffsetNumber offnum,
1669  maxoff;
1670 
1671  Assert(GistPageIsLeaf(page));
1672 
1673  /*
1674  * Scan over all items to see which ones need to be deleted according to
1675  * LP_DEAD flags.
1676  */
1677  maxoff = PageGetMaxOffsetNumber(page);
1678  for (offnum = FirstOffsetNumber;
1679  offnum <= maxoff;
1680  offnum = OffsetNumberNext(offnum))
1681  {
1682  ItemId itemId = PageGetItemId(page, offnum);
1683 
1684  if (ItemIdIsDead(itemId))
1685  deletable[ndeletable++] = offnum;
1686  }
1687 
1688  if (ndeletable > 0)
1689  {
1690  TransactionId snapshotConflictHorizon = InvalidTransactionId;
1691 
1693  snapshotConflictHorizon =
1694  index_compute_xid_horizon_for_tuples(rel, heapRel, buffer,
1695  deletable, ndeletable);
1696 
1698 
1699  PageIndexMultiDelete(page, deletable, ndeletable);
1700 
1701  /*
1702  * Mark the page as not containing any LP_DEAD items. This is not
1703  * certainly true (there might be some that have recently been marked,
1704  * but weren't included in our target-item list), but it will almost
1705  * always be true and it doesn't seem worth an additional page scan to
1706  * check it. Remember that F_HAS_GARBAGE is only a hint anyway.
1707  */
1709 
1710  MarkBufferDirty(buffer);
1711 
1712  /* XLOG stuff */
1713  if (RelationNeedsWAL(rel))
1714  {
1715  XLogRecPtr recptr;
1716 
1717  recptr = gistXLogDelete(buffer,
1718  deletable, ndeletable,
1719  snapshotConflictHorizon,
1720  heapRel);
1721 
1722  PageSetLSN(page, recptr);
1723  }
1724  else
1725  PageSetLSN(page, gistGetFakeLSN(rel));
1726 
1727  END_CRIT_SECTION();
1728  }
1729 
1730  /*
1731  * Note: if we didn't find any LP_DEAD items, then the page's
1732  * F_HAS_GARBAGE hint bit is falsely set. We do not bother expending a
1733  * separate write to clear it, however. We will clear it when we split
1734  * the page.
1735  */
1736 }
void PageIndexMultiDelete(Page page, OffsetNumber *itemnos, int nitems)
Definition: bufpage.c:1161
uint32 TransactionId
Definition: c.h:639
TransactionId index_compute_xid_horizon_for_tuples(Relation irel, Relation hrel, Buffer ibuf, OffsetNumber *itemnos, int nitems)
Definition: genam.c:291
#define GistClearPageHasGarbage(page)
Definition: gist.h:180
XLogRecPtr gistXLogDelete(Buffer buffer, OffsetNumber *todelete, int ntodelete, TransactionId snapshotConflictHorizon, Relation heaprel)
Definition: gistxlog.c:670
#define ItemIdIsDead(itemId)
Definition: itemid.h:113
#define MaxIndexTuplesPerPage
Definition: itup.h:165
#define InvalidTransactionId
Definition: transam.h:31
#define XLogStandbyInfoActive()
Definition: xlog.h:121

References Assert(), END_CRIT_SECTION, FirstOffsetNumber, GistClearPageHasGarbage, gistGetFakeLSN(), GistPageIsLeaf, gistXLogDelete(), index_compute_xid_horizon_for_tuples(), InvalidTransactionId, ItemIdIsDead, MarkBufferDirty(), MaxIndexTuplesPerPage, OffsetNumberNext, PageGetItemId(), PageGetMaxOffsetNumber(), PageIndexMultiDelete(), PageSetLSN(), RelationNeedsWAL, START_CRIT_SECTION, and XLogStandbyInfoActive.

Referenced by gistplacetopage().

◆ gistSplit()

SplitPageLayout* gistSplit ( Relation  r,
Page  page,
IndexTuple itup,
int  len,
GISTSTATE giststate 
)

Definition at line 1438 of file gist.c.

1443 {
1444  IndexTuple *lvectup,
1445  *rvectup;
1446  GistSplitVector v;
1447  int i;
1448  SplitPageLayout *res = NULL;
1449 
1450  /* this should never recurse very deeply, but better safe than sorry */
1452 
1453  /* there's no point in splitting an empty page */
1454  Assert(len > 0);
1455 
1456  /*
1457  * If a single tuple doesn't fit on a page, no amount of splitting will
1458  * help.
1459  */
1460  if (len == 1)
1461  ereport(ERROR,
1462  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1463  errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
1464  IndexTupleSize(itup[0]), GiSTPageSize,
1466 
1467  memset(v.spl_lisnull, true,
1468  sizeof(bool) * giststate->nonLeafTupdesc->natts);
1469  memset(v.spl_risnull, true,
1470  sizeof(bool) * giststate->nonLeafTupdesc->natts);
1471  gistSplitByKey(r, page, itup, len, giststate, &v, 0);
1472 
1473  /* form left and right vector */
1474  lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
1475  rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * (len + 1));
1476 
1477  for (i = 0; i < v.splitVector.spl_nleft; i++)
1478  lvectup[i] = itup[v.splitVector.spl_left[i] - 1];
1479 
1480  for (i = 0; i < v.splitVector.spl_nright; i++)
1481  rvectup[i] = itup[v.splitVector.spl_right[i] - 1];
1482 
1483  /* finalize splitting (may need another split) */
1484  if (!gistfitpage(rvectup, v.splitVector.spl_nright))
1485  {
1486  res = gistSplit(r, page, rvectup, v.splitVector.spl_nright, giststate);
1487  }
1488  else
1489  {
1490  ROTATEDIST(res);
1491  res->block.num = v.splitVector.spl_nright;
1492  res->list = gistfillitupvec(rvectup, v.splitVector.spl_nright, &(res->lenlist));
1493  res->itup = gistFormTuple(giststate, r, v.spl_rattr, v.spl_risnull, false);
1494  }
1495 
1496  if (!gistfitpage(lvectup, v.splitVector.spl_nleft))
1497  {
1498  SplitPageLayout *resptr,
1499  *subres;
1500 
1501  resptr = subres = gistSplit(r, page, lvectup, v.splitVector.spl_nleft, giststate);
1502 
1503  /* install on list's tail */
1504  while (resptr->next)
1505  resptr = resptr->next;
1506 
1507  resptr->next = res;
1508  res = subres;
1509  }
1510  else
1511  {
1512  ROTATEDIST(res);
1513  res->block.num = v.splitVector.spl_nleft;
1514  res->list = gistfillitupvec(lvectup, v.splitVector.spl_nleft, &(res->lenlist));
1515  res->itup = gistFormTuple(giststate, r, v.spl_lattr, v.spl_lisnull, false);
1516  }
1517 
1518  return res;
1519 }
int errcode(int sqlerrcode)
Definition: elog.c:859
#define ROTATEDIST(d)
Definition: gist.c:45
#define GiSTPageSize
Definition: gist_private.h:476
void gistSplitByKey(Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate, GistSplitVector *v, int attno)
Definition: gistsplit.c:623
bool gistfitpage(IndexTuple *itvec, int len)
Definition: gistutil.c:79
const void size_t len
void check_stack_depth(void)
Definition: postgres.c:3531
for(int i=0;i< RT_NUM_SIZE_CLASSES;i++)
Definition: radixtree.h:1810
TupleDesc nonLeafTupdesc
Definition: gist_private.h:81
int spl_nleft
Definition: gist.h:143
OffsetNumber * spl_right
Definition: gist.h:147
int spl_nright
Definition: gist.h:148
OffsetNumber * spl_left
Definition: gist.h:142
GIST_SPLITVEC splitVector
Definition: gist_private.h:237
Datum spl_lattr[INDEX_MAX_KEYS]
Definition: gist_private.h:239
bool spl_lisnull[INDEX_MAX_KEYS]
Definition: gist_private.h:241
Datum spl_rattr[INDEX_MAX_KEYS]
Definition: gist_private.h:243
bool spl_risnull[INDEX_MAX_KEYS]
Definition: gist_private.h:245

References Assert(), check_stack_depth(), ereport, errcode(), errmsg(), ERROR, for(), gistfillitupvec(), gistfitpage(), gistFormTuple(), GiSTPageSize, gistSplitByKey(), i, if(), IndexTupleSize, len, TupleDescData::natts, SplitPageLayout::next, GISTSTATE::nonLeafTupdesc, palloc(), RelationGetRelationName, res, ROTATEDIST, GistSplitVector::spl_lattr, GIST_SPLITVEC::spl_left, GistSplitVector::spl_lisnull, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GistSplitVector::spl_rattr, GIST_SPLITVEC::spl_right, GistSplitVector::spl_risnull, and GistSplitVector::splitVector.

Referenced by gist_indexsortbuild_levelstate_flush(), and gistplacetopage().

◆ initGISTstate()

GISTSTATE* initGISTstate ( Relation  index)

Definition at line 1525 of file gist.c.

1526 {
1527  GISTSTATE *giststate;
1528  MemoryContext scanCxt;
1529  MemoryContext oldCxt;
1530  int i;
1531 
1532  /* safety check to protect fixed-size arrays in GISTSTATE */
1533  if (index->rd_att->natts > INDEX_MAX_KEYS)
1534  elog(ERROR, "numberOfAttributes %d > %d",
1535  index->rd_att->natts, INDEX_MAX_KEYS);
1536 
1537  /* Create the memory context that will hold the GISTSTATE */
1539  "GiST scan context",
1541  oldCxt = MemoryContextSwitchTo(scanCxt);
1542 
1543  /* Create and fill in the GISTSTATE */
1544  giststate = (GISTSTATE *) palloc(sizeof(GISTSTATE));
1545 
1546  giststate->scanCxt = scanCxt;
1547  giststate->tempCxt = scanCxt; /* caller must change this if needed */
1548  giststate->leafTupdesc = index->rd_att;
1549 
1550  /*
1551  * The truncated tupdesc for non-leaf index tuples, which doesn't contain
1552  * the INCLUDE attributes.
1553  *
1554  * It is used to form tuples during tuple adjustment and page split.
1555  * B-tree creates shortened tuple descriptor for every truncated tuple,
1556  * because it is doing this less often: it does not have to form truncated
1557  * tuples during page split. Also, B-tree is not adjusting tuples on
1558  * internal pages the way GiST does.
1559  */
1560  giststate->nonLeafTupdesc = CreateTupleDescCopyConstr(index->rd_att);
1561  giststate->nonLeafTupdesc->natts =
1563 
1565  {
1566  fmgr_info_copy(&(giststate->consistentFn[i]),
1568  scanCxt);
1569  fmgr_info_copy(&(giststate->unionFn[i]),
1571  scanCxt);
1572 
1573  /* opclasses are not required to provide a Compress method */
1575  fmgr_info_copy(&(giststate->compressFn[i]),
1577  scanCxt);
1578  else
1579  giststate->compressFn[i].fn_oid = InvalidOid;
1580 
1581  /* opclasses are not required to provide a Decompress method */
1583  fmgr_info_copy(&(giststate->decompressFn[i]),
1585  scanCxt);
1586  else
1587  giststate->decompressFn[i].fn_oid = InvalidOid;
1588 
1589  fmgr_info_copy(&(giststate->penaltyFn[i]),
1591  scanCxt);
1592  fmgr_info_copy(&(giststate->picksplitFn[i]),
1594  scanCxt);
1595  fmgr_info_copy(&(giststate->equalFn[i]),
1597  scanCxt);
1598 
1599  /* opclasses are not required to provide a Distance method */
1601  fmgr_info_copy(&(giststate->distanceFn[i]),
1603  scanCxt);
1604  else
1605  giststate->distanceFn[i].fn_oid = InvalidOid;
1606 
1607  /* opclasses are not required to provide a Fetch method */
1609  fmgr_info_copy(&(giststate->fetchFn[i]),
1611  scanCxt);
1612  else
1613  giststate->fetchFn[i].fn_oid = InvalidOid;
1614 
1615  /*
1616  * If the index column has a specified collation, we should honor that
1617  * while doing comparisons. However, we may have a collatable storage
1618  * type for a noncollatable indexed data type. If there's no index
1619  * collation then specify default collation in case the support
1620  * functions need collation. This is harmless if the support
1621  * functions don't care about collation, so we just do it
1622  * unconditionally. (We could alternatively call get_typcollation,
1623  * but that seems like expensive overkill --- there aren't going to be
1624  * any cases where a GiST storage type has a nondefault collation.)
1625  */
1626  if (OidIsValid(index->rd_indcollation[i]))
1627  giststate->supportCollation[i] = index->rd_indcollation[i];
1628  else
1629  giststate->supportCollation[i] = DEFAULT_COLLATION_OID;
1630  }
1631 
1632  /* No opclass information for INCLUDE attributes */
1633  for (; i < index->rd_att->natts; i++)
1634  {
1635  giststate->consistentFn[i].fn_oid = InvalidOid;
1636  giststate->unionFn[i].fn_oid = InvalidOid;
1637  giststate->compressFn[i].fn_oid = InvalidOid;
1638  giststate->decompressFn[i].fn_oid = InvalidOid;
1639  giststate->penaltyFn[i].fn_oid = InvalidOid;
1640  giststate->picksplitFn[i].fn_oid = InvalidOid;
1641  giststate->equalFn[i].fn_oid = InvalidOid;
1642  giststate->distanceFn[i].fn_oid = InvalidOid;
1643  giststate->fetchFn[i].fn_oid = InvalidOid;
1644  giststate->supportCollation[i] = InvalidOid;
1645  }
1646 
1647  MemoryContextSwitchTo(oldCxt);
1648 
1649  return giststate;
1650 }
#define OidIsValid(objectId)
Definition: c.h:762
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:580
#define GIST_DECOMPRESS_PROC
Definition: gist.h:34
#define GIST_PICKSPLIT_PROC
Definition: gist.h:36
#define GIST_CONSISTENT_PROC
Definition: gist.h:31
#define GIST_UNION_PROC
Definition: gist.h:32
#define GIST_FETCH_PROC
Definition: gist.h:39
#define GIST_COMPRESS_PROC
Definition: gist.h:33
#define GIST_PENALTY_PROC
Definition: gist.h:35
#define GIST_DISTANCE_PROC
Definition: gist.h:38
#define GIST_EQUAL_PROC
Definition: gist.h:37
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:863
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:829
#define INDEX_MAX_KEYS
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:526
Oid fn_oid
Definition: fmgr.h:59
FmgrInfo fetchFn[INDEX_MAX_KEYS]
Definition: gist_private.h:94
TupleDesc leafTupdesc
Definition: gist_private.h:80
FmgrInfo penaltyFn[INDEX_MAX_KEYS]
Definition: gist_private.h:90
Oid supportCollation[INDEX_MAX_KEYS]
Definition: gist_private.h:97
FmgrInfo distanceFn[INDEX_MAX_KEYS]
Definition: gist_private.h:93
FmgrInfo consistentFn[INDEX_MAX_KEYS]
Definition: gist_private.h:86
FmgrInfo decompressFn[INDEX_MAX_KEYS]
Definition: gist_private.h:89
FmgrInfo compressFn[INDEX_MAX_KEYS]
Definition: gist_private.h:88
FmgrInfo equalFn[INDEX_MAX_KEYS]
Definition: gist_private.h:92
FmgrInfo unionFn[INDEX_MAX_KEYS]
Definition: gist_private.h:87
FmgrInfo picksplitFn[INDEX_MAX_KEYS]
Definition: gist_private.h:91
TupleDesc CreateTupleDescCopyConstr(TupleDesc tupdesc)
Definition: tupdesc.c:173

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, GISTSTATE::compressFn, GISTSTATE::consistentFn, CreateTupleDescCopyConstr(), CurrentMemoryContext, GISTSTATE::decompressFn, GISTSTATE::distanceFn, elog, GISTSTATE::equalFn, ERROR, GISTSTATE::fetchFn, fmgr_info_copy(), FmgrInfo::fn_oid, GIST_COMPRESS_PROC, GIST_CONSISTENT_PROC, GIST_DECOMPRESS_PROC, GIST_DISTANCE_PROC, GIST_EQUAL_PROC, GIST_FETCH_PROC, GIST_PENALTY_PROC, GIST_PICKSPLIT_PROC, GIST_UNION_PROC, i, index_getprocid(), index_getprocinfo(), INDEX_MAX_KEYS, IndexRelationGetNumberOfKeyAttributes, InvalidOid, GISTSTATE::leafTupdesc, MemoryContextSwitchTo(), TupleDescData::natts, GISTSTATE::nonLeafTupdesc, OidIsValid, palloc(), GISTSTATE::penaltyFn, GISTSTATE::picksplitFn, GISTSTATE::scanCxt, GISTSTATE::supportCollation, GISTSTATE::tempCxt, and GISTSTATE::unionFn.

Referenced by gistbeginscan(), gistbuild(), and gistinsert().