PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
gistbuild.c File Reference
#include "postgres.h"
#include <math.h>
#include "access/genam.h"
#include "access/gist_private.h"
#include "access/gistxlog.h"
#include "access/xloginsert.h"
#include "catalog/index.h"
#include "miscadmin.h"
#include "optimizer/cost.h"
#include "storage/bufmgr.h"
#include "storage/smgr.h"
#include "utils/memutils.h"
#include "utils/rel.h"
Include dependency graph for gistbuild.c:

Go to the source code of this file.

Data Structures

struct  GISTBuildState
 
struct  ParentMapEntry
 

Macros

#define BUFFERING_MODE_SWITCH_CHECK_STEP   256
 
#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET   4096
 

Enumerations

enum  GistBufferingMode { GIST_BUFFERING_DISABLED, GIST_BUFFERING_AUTO, GIST_BUFFERING_STATS, GIST_BUFFERING_ACTIVE }
 

Functions

static void gistInitBuffering (GISTBuildState *buildstate)
 
static int calculatePagesPerBuffer (GISTBuildState *buildstate, int levelStep)
 
static void gistBuildCallback (Relation index, HeapTuple htup, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
 
static void gistBufferingBuildInsert (GISTBuildState *buildstate, IndexTuple itup)
 
static bool gistProcessItup (GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
 
static BlockNumber gistbufferinginserttuples (GISTBuildState *buildstate, Buffer buffer, int level, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber parentblk, OffsetNumber downlinkoffnum)
 
static Buffer gistBufferingFindCorrectParent (GISTBuildState *buildstate, BlockNumber childblkno, int level, BlockNumber *parentblk, OffsetNumber *downlinkoffnum)
 
static void gistProcessEmptyingQueue (GISTBuildState *buildstate)
 
static void gistEmptyAllBuffers (GISTBuildState *buildstate)
 
static int gistGetMaxLevel (Relation index)
 
static void gistInitParentMap (GISTBuildState *buildstate)
 
static void gistMemorizeParent (GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
 
static void gistMemorizeAllDownlinks (GISTBuildState *buildstate, Buffer parent)
 
static BlockNumber gistGetParent (GISTBuildState *buildstate, BlockNumber child)
 
IndexBuildResultgistbuild (Relation heap, Relation index, IndexInfo *indexInfo)
 
void gistValidateBufferingOption (char *value)
 

Macro Definition Documentation

#define BUFFERING_MODE_SWITCH_CHECK_STEP   256

Definition at line 32 of file gistbuild.c.

Referenced by gistBuildCallback().

#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET   4096

Definition at line 40 of file gistbuild.c.

Referenced by gistBuildCallback().

Enumeration Type Documentation

Enumerator
GIST_BUFFERING_DISABLED 
GIST_BUFFERING_AUTO 
GIST_BUFFERING_STATS 
GIST_BUFFERING_ACTIVE 

Definition at line 42 of file gistbuild.c.

43 {
44  GIST_BUFFERING_DISABLED, /* in regular build mode and aren't going to
45  * switch */
46  GIST_BUFFERING_AUTO, /* in regular build mode, but will switch to
47  * buffering build mode if the index grows too
48  * big */
49  GIST_BUFFERING_STATS, /* gathering statistics of index tuple size
50  * before switching to the buffering build
51  * mode */
52  GIST_BUFFERING_ACTIVE /* in buffering build mode */
GistBufferingMode
Definition: gistbuild.c:42

Function Documentation

static int calculatePagesPerBuffer ( GISTBuildState buildstate,
int  levelStep 
)
static

Definition at line 425 of file gistbuild.c.

References GISTBuildState::freespace, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, rint(), and SizeOfPageHeaderData.

Referenced by gistBuildCallback(), and gistInitBuffering().

426 {
427  double pagesPerBuffer;
428  double avgIndexTuplesPerPage;
429  double itupAvgSize;
430  Size pageFreeSpace;
431 
432  /* Calc space of index page which is available for index tuples */
433  pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
434  - sizeof(ItemIdData)
435  - buildstate->freespace;
436 
437  /*
438  * Calculate average size of already inserted index tuples using gathered
439  * statistics.
440  */
441  itupAvgSize = (double) buildstate->indtuplesSize /
442  (double) buildstate->indtuples;
443 
444  avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
445 
446  /*
447  * Recalculate required size of buffers.
448  */
449  pagesPerBuffer = 2 * pow(avgIndexTuplesPerPage, levelStep);
450 
451  return (int) rint(pagesPerBuffer);
452 }
#define SizeOfPageHeaderData
Definition: bufpage.h:212
int64 indtuplesSize
Definition: gistbuild.c:62
int64 indtuples
Definition: gistbuild.c:61
Size freespace
Definition: gistbuild.c:64
struct GISTPageOpaqueData GISTPageOpaqueData
double rint(double x)
Definition: rint.c:22
size_t Size
Definition: c.h:356
static void gistBufferingBuildInsert ( GISTBuildState buildstate,
IndexTuple  itup 
)
static

Definition at line 530 of file gistbuild.c.

References GISTBuildState::gfbb, gistProcessEmptyingQueue(), gistProcessItup(), and GISTBuildBuffers::rootlevel.

Referenced by gistBuildCallback().

531 {
532  /* Insert the tuple to buffers. */
533  gistProcessItup(buildstate, itup, 0, buildstate->gfbb->rootlevel);
534 
535  /* If we filled up (half of a) buffer, process buffer emptying. */
536  gistProcessEmptyingQueue(buildstate);
537 }
static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
Definition: gistbuild.c:546
static void gistProcessEmptyingQueue(GISTBuildState *buildstate)
Definition: gistbuild.c:919
GISTBuildBuffers * gfbb
Definition: gistbuild.c:71
static Buffer gistBufferingFindCorrectParent ( GISTBuildState buildstate,
BlockNumber  childblkno,
int  level,
BlockNumber parentblk,
OffsetNumber downlinkoffnum 
)
static

Definition at line 845 of file gistbuild.c.

References buffer, BufferGetPage, elog, ERROR, FirstOffsetNumber, GIST_EXCLUSIVE, gistcheckpage(), gistGetParent(), GISTBuildState::indexrel, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, ItemPointerGetBlockNumber, LockBuffer(), OffsetNumberNext, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, DataPageDeleteStack::parent, ReadBuffer(), and IndexTupleData::t_tid.

Referenced by gistbufferinginserttuples().

849 {
850  BlockNumber parent;
851  Buffer buffer;
852  Page page;
853  OffsetNumber maxoff;
854  OffsetNumber off;
855 
856  if (level > 0)
857  parent = gistGetParent(buildstate, childblkno);
858  else
859  {
860  /*
861  * For a leaf page, the caller must supply a correct parent block
862  * number.
863  */
864  if (*parentblkno == InvalidBlockNumber)
865  elog(ERROR, "no parent buffer provided of child %d", childblkno);
866  parent = *parentblkno;
867  }
868 
869  buffer = ReadBuffer(buildstate->indexrel, parent);
870  page = BufferGetPage(buffer);
871  LockBuffer(buffer, GIST_EXCLUSIVE);
872  gistcheckpage(buildstate->indexrel, buffer);
873  maxoff = PageGetMaxOffsetNumber(page);
874 
875  /* Check if it was not moved */
876  if (parent == *parentblkno && *parentblkno != InvalidBlockNumber &&
877  *downlinkoffnum != InvalidOffsetNumber && *downlinkoffnum <= maxoff)
878  {
879  ItemId iid = PageGetItemId(page, *downlinkoffnum);
880  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
881 
882  if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
883  {
884  /* Still there */
885  return buffer;
886  }
887  }
888 
889  /*
890  * Downlink was not at the offset where it used to be. Scan the page to
891  * find it. During normal gist insertions, it might've moved to another
892  * page, to the right, but during a buffering build, we keep track of the
893  * parent of each page in the lookup table so we should always know what
894  * page it's on.
895  */
896  for (off = FirstOffsetNumber; off <= maxoff; off = OffsetNumberNext(off))
897  {
898  ItemId iid = PageGetItemId(page, off);
899  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
900 
901  if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
902  {
903  /* yes!!, found it */
904  *downlinkoffnum = off;
905  return buffer;
906  }
907  }
908 
909  elog(ERROR, "failed to re-find parent for block %u", childblkno);
910  return InvalidBuffer; /* keep compiler quiet */
911 }
ItemPointerData t_tid
Definition: itup.h:37
#define InvalidBuffer
Definition: buf.h:25
uint32 BlockNumber
Definition: block.h:31
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:353
uint16 OffsetNumber
Definition: off.h:24
#define ERROR
Definition: elog.h:43
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child)
Definition: gistbuild.c:1187
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define InvalidOffsetNumber
Definition: off.h:26
Relation indexrel
Definition: gistbuild.c:58
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:214
void gistcheckpage(Relation rel, Buffer buf)
Definition: gistutil.c:723
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
#define OffsetNumberNext(offsetNumber)
Definition: off.h:53
#define InvalidBlockNumber
Definition: block.h:33
#define elog
Definition: elog.h:219
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:76
#define GIST_EXCLUSIVE
Definition: gist_private.h:44
int Buffer
Definition: buf.h:23
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
static BlockNumber gistbufferinginserttuples ( GISTBuildState buildstate,
Buffer  buffer,
int  level,
IndexTuple itup,
int  ntup,
OffsetNumber  oldoffnum,
BlockNumber  parentblk,
OffsetNumber  downlinkoffnum 
)
static

Definition at line 677 of file gistbuild.c.

References Assert, GISTPageSplitInfo::buf, BufferGetBlockNumber(), BufferGetPage, DEBUG2, GISTPageSplitInfo::downlink, elog, FirstOffsetNumber, GISTBuildState::freespace, GISTBuildState::gfbb, GIST_ROOT_BLKNO, GIST_SHARE, gistBufferingFindCorrectParent(), gistMemorizeAllDownlinks(), gistMemorizeParent(), gistplacetopage(), gistRelocateBuildBuffersOnSplit(), GISTBuildState::giststate, i, GISTBuildState::indexrel, InvalidBlockNumber, InvalidBuffer, InvalidOffsetNumber, ItemPointerGetBlockNumber, lfirst, list_free_deep(), list_length(), LockBuffer(), PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, palloc(), ReadBuffer(), GISTBuildBuffers::rootlevel, IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistProcessItup().

680 {
681  GISTBuildBuffers *gfbb = buildstate->gfbb;
682  List *splitinfo;
683  bool is_split;
684  BlockNumber placed_to_blk = InvalidBlockNumber;
685 
686  is_split = gistplacetopage(buildstate->indexrel,
687  buildstate->freespace,
688  buildstate->giststate,
689  buffer,
690  itup, ntup, oldoffnum, &placed_to_blk,
692  &splitinfo,
693  false);
694 
695  /*
696  * If this is a root split, update the root path item kept in memory. This
697  * ensures that all path stacks are always complete, including all parent
698  * nodes up to the root. That simplifies the algorithm to re-find correct
699  * parent.
700  */
701  if (is_split && BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO)
702  {
703  Page page = BufferGetPage(buffer);
704  OffsetNumber off;
705  OffsetNumber maxoff;
706 
707  Assert(level == gfbb->rootlevel);
708  gfbb->rootlevel++;
709 
710  elog(DEBUG2, "splitting GiST root page, now %d levels deep", gfbb->rootlevel);
711 
712  /*
713  * All the downlinks on the old root page are now on one of the child
714  * pages. Visit all the new child pages to memorize the parents of the
715  * grandchildren.
716  */
717  if (gfbb->rootlevel > 1)
718  {
719  maxoff = PageGetMaxOffsetNumber(page);
720  for (off = FirstOffsetNumber; off <= maxoff; off++)
721  {
722  ItemId iid = PageGetItemId(page, off);
723  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
724  BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
725  Buffer childbuf = ReadBuffer(buildstate->indexrel, childblkno);
726 
727  LockBuffer(childbuf, GIST_SHARE);
728  gistMemorizeAllDownlinks(buildstate, childbuf);
729  UnlockReleaseBuffer(childbuf);
730 
731  /*
732  * Also remember that the parent of the new child page is the
733  * root block.
734  */
735  gistMemorizeParent(buildstate, childblkno, GIST_ROOT_BLKNO);
736  }
737  }
738  }
739 
740  if (splitinfo)
741  {
742  /*
743  * Insert the downlinks to the parent. This is analogous with
744  * gistfinishsplit() in the regular insertion code, but the locking is
745  * simpler, and we have to maintain the buffers on internal nodes and
746  * the parent map.
747  */
748  IndexTuple *downlinks;
749  int ndownlinks,
750  i;
751  Buffer parentBuffer;
752  ListCell *lc;
753 
754  /* Parent may have changed since we memorized this path. */
755  parentBuffer =
758  level,
759  &parentblk,
760  &downlinkoffnum);
761 
762  /*
763  * If there's a buffer associated with this page, that needs to be
764  * split too. gistRelocateBuildBuffersOnSplit() will also adjust the
765  * downlinks in 'splitinfo', to make sure they're consistent not only
766  * with the tuples already on the pages, but also the tuples in the
767  * buffers that will eventually be inserted to them.
768  */
770  buildstate->giststate,
771  buildstate->indexrel,
772  level,
773  buffer, splitinfo);
774 
775  /* Create an array of all the downlink tuples */
776  ndownlinks = list_length(splitinfo);
777  downlinks = (IndexTuple *) palloc(sizeof(IndexTuple) * ndownlinks);
778  i = 0;
779  foreach(lc, splitinfo)
780  {
781  GISTPageSplitInfo *splitinfo = lfirst(lc);
782 
783  /*
784  * Remember the parent of each new child page in our parent map.
785  * This assumes that the downlinks fit on the parent page. If the
786  * parent page is split, too, when we recurse up to insert the
787  * downlinks, the recursive gistbufferinginserttuples() call will
788  * update the map again.
789  */
790  if (level > 0)
791  gistMemorizeParent(buildstate,
792  BufferGetBlockNumber(splitinfo->buf),
793  BufferGetBlockNumber(parentBuffer));
794 
795  /*
796  * Also update the parent map for all the downlinks that got moved
797  * to a different page. (actually this also loops through the
798  * downlinks that stayed on the original page, but it does no
799  * harm).
800  */
801  if (level > 1)
802  gistMemorizeAllDownlinks(buildstate, splitinfo->buf);
803 
804  /*
805  * Since there's no concurrent access, we can release the lower
806  * level buffers immediately. This includes the original page.
807  */
808  UnlockReleaseBuffer(splitinfo->buf);
809  downlinks[i++] = splitinfo->downlink;
810  }
811 
812  /* Insert them into parent. */
813  gistbufferinginserttuples(buildstate, parentBuffer, level + 1,
814  downlinks, ndownlinks, downlinkoffnum,
816 
817  list_free_deep(splitinfo); /* we don't need this anymore */
818  }
819  else
821 
822  return placed_to_blk;
823 }
void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate, Relation r, int level, Buffer buffer, List *splitinfo)
ItemPointerData t_tid
Definition: itup.h:37
#define InvalidBuffer
Definition: buf.h:25
uint32 BlockNumber
Definition: block.h:31
static Buffer gistBufferingFindCorrectParent(GISTBuildState *buildstate, BlockNumber childblkno, int level, BlockNumber *parentblk, OffsetNumber *downlinkoffnum)
Definition: gistbuild.c:845
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:353
void list_free_deep(List *list)
Definition: list.c:1147
uint16 OffsetNumber
Definition: off.h:24
static BlockNumber gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, int level, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber parentblk, OffsetNumber downlinkoffnum)
Definition: gistbuild.c:677
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
#define DEBUG2
Definition: elog.h:24
IndexTuple downlink
Definition: gist_private.h:398
bool gistplacetopage(Relation rel, Size freespace, GISTSTATE *giststate, Buffer buffer, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber *newblkno, Buffer leftchildbuf, List **splitinfo, bool markfollowright)
Definition: gist.c:212
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
Size freespace
Definition: gistbuild.c:64
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
GISTSTATE * giststate
Definition: gistbuild.c:59
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define InvalidOffsetNumber
Definition: off.h:26
#define Assert(condition)
Definition: c.h:675
#define lfirst(lc)
Definition: pg_list.h:106
Relation indexrel
Definition: gistbuild.c:58
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:214
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
Definition: gistbuild.c:1150
static void gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parent)
Definition: gistbuild.c:1166
#define InvalidBlockNumber
Definition: block.h:33
static int list_length(const List *l)
Definition: pg_list.h:89
#define GIST_SHARE
Definition: gist_private.h:43
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2605
void * palloc(Size size)
Definition: mcxt.c:849
GISTBuildBuffers * gfbb
Definition: gistbuild.c:71
int i
#define GIST_ROOT_BLKNO
Definition: gist_private.h:249
#define elog
Definition: elog.h:219
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:76
Definition: pg_list.h:45
int Buffer
Definition: buf.h:23
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
IndexBuildResult* gistbuild ( Relation  heap,
Relation  index,
IndexInfo indexInfo 
)

Definition at line 114 of file gistbuild.c.

References Assert, buffer, BufferGetBlockNumber(), BufferGetPage, GISTBuildState::bufferingMode, GiSTOptions::bufferingModeOffset, createTempGistContext(), CurrentMemoryContext, DEBUG1, elog, END_CRIT_SECTION, ERROR, F_LEAF, fillfactor, GiSTOptions::fillfactor, freeGISTstate(), GISTBuildState::freespace, GISTBuildState::gfbb, GIST_BUFFERING_ACTIVE, GIST_BUFFERING_AUTO, GIST_BUFFERING_DISABLED, GIST_BUFFERING_STATS, GIST_DEFAULT_FILLFACTOR, GIST_ROOT_BLKNO, gistBuildCallback(), gistEmptyAllBuffers(), gistFreeBuildBuffers(), gistGetFakeLSN(), GISTInitBuffer(), gistNewBuffer(), GISTBuildState::giststate, IndexBuildResult::heap_tuples, IndexBuildResult::index_tuples, IndexBuildHeapScan(), GISTBuildState::indexrel, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, initGISTstate(), MarkBufferDirty(), MemoryContextDelete(), MemoryContextSwitchTo(), PageSetLSN, palloc(), RelationData::rd_options, REGBUF_WILL_INIT, RelationGetNumberOfBlocks, RelationGetRelationName, RelationNeedsWAL, result, START_CRIT_SECTION, GISTSTATE::tempCxt, UnlockReleaseBuffer(), XLOG_GIST_CREATE_INDEX, XLogBeginInsert(), XLogInsert(), and XLogRegisterBuffer().

Referenced by gisthandler().

115 {
117  double reltuples;
118  GISTBuildState buildstate;
119  Buffer buffer;
120  Page page;
122  int fillfactor;
123 
124  buildstate.indexrel = index;
125  if (index->rd_options)
126  {
127  /* Get buffering mode from the options string */
129  char *bufferingMode = (char *) options + options->bufferingModeOffset;
130 
131  if (strcmp(bufferingMode, "on") == 0)
132  buildstate.bufferingMode = GIST_BUFFERING_STATS;
133  else if (strcmp(bufferingMode, "off") == 0)
135  else
136  buildstate.bufferingMode = GIST_BUFFERING_AUTO;
137 
138  fillfactor = options->fillfactor;
139  }
140  else
141  {
142  /*
143  * By default, switch to buffering mode when the index grows too large
144  * to fit in cache.
145  */
146  buildstate.bufferingMode = GIST_BUFFERING_AUTO;
147  fillfactor = GIST_DEFAULT_FILLFACTOR;
148  }
149  /* Calculate target amount of free space to leave on pages */
150  buildstate.freespace = BLCKSZ * (100 - fillfactor) / 100;
151 
152  /*
153  * We expect to be called exactly once for any index relation. If that's
154  * not the case, big trouble's what we have.
155  */
156  if (RelationGetNumberOfBlocks(index) != 0)
157  elog(ERROR, "index \"%s\" already contains data",
158  RelationGetRelationName(index));
159 
160  /* no locking is needed */
161  buildstate.giststate = initGISTstate(index);
162 
163  /*
164  * Create a temporary memory context that is reset once for each tuple
165  * processed. (Note: we don't bother to make this a child of the
166  * giststate's scanCxt, so we have to delete it separately at the end.)
167  */
168  buildstate.giststate->tempCxt = createTempGistContext();
169 
170  /* initialize the root page */
171  buffer = gistNewBuffer(index);
173  page = BufferGetPage(buffer);
174 
176 
177  GISTInitBuffer(buffer, F_LEAF);
178 
179  MarkBufferDirty(buffer);
180 
181  if (RelationNeedsWAL(index))
182  {
183  XLogRecPtr recptr;
184 
185  XLogBeginInsert();
187 
188  recptr = XLogInsert(RM_GIST_ID, XLOG_GIST_CREATE_INDEX);
189  PageSetLSN(page, recptr);
190  }
191  else
192  PageSetLSN(page, gistGetFakeLSN(heap));
193 
194  UnlockReleaseBuffer(buffer);
195 
197 
198  /* build the index */
199  buildstate.indtuples = 0;
200  buildstate.indtuplesSize = 0;
201 
202  /*
203  * Do the heap scan.
204  */
205  reltuples = IndexBuildHeapScan(heap, index, indexInfo, true,
206  gistBuildCallback, (void *) &buildstate);
207 
208  /*
209  * If buffering was used, flush out all the tuples that are still in the
210  * buffers.
211  */
212  if (buildstate.bufferingMode == GIST_BUFFERING_ACTIVE)
213  {
214  elog(DEBUG1, "all tuples processed, emptying buffers");
215  gistEmptyAllBuffers(&buildstate);
216  gistFreeBuildBuffers(buildstate.gfbb);
217  }
218 
219  /* okay, all heap tuples are indexed */
220  MemoryContextSwitchTo(oldcxt);
222 
223  freeGISTstate(buildstate.giststate);
224 
225  /*
226  * Return statistics
227  */
228  result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
229 
230  result->heap_tuples = reltuples;
231  result->index_tuples = (double) buildstate.indtuples;
232 
233  return result;
234 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:200
#define DEBUG1
Definition: elog.h:25
int bufferingModeOffset
Definition: gist_private.h:377
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1450
MemoryContext createTempGistContext(void)
Definition: gist.c:110
void XLogRegisterBuffer(uint8 block_id, Buffer buffer, uint8 flags)
Definition: xloginsert.c:213
#define END_CRIT_SECTION()
Definition: miscadmin.h:133
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define REGBUF_WILL_INIT
Definition: xloginsert.h:32
#define START_CRIT_SECTION()
Definition: miscadmin.h:131
#define XLOG_GIST_CREATE_INDEX
Definition: gistxlog.h:24
return result
Definition: formatting.c:1633
GistBufferingMode bufferingMode
Definition: gistbuild.c:74
XLogRecPtr gistGetFakeLSN(Relation rel)
Definition: gistutil.c:946
int64 indtuplesSize
Definition: gistbuild.c:62
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
#define ERROR
Definition: elog.h:43
int fillfactor
Definition: pgbench.c:112
int64 indtuples
Definition: gistbuild.c:61
MemoryContext tempCxt
Definition: gist_private.h:79
Size freespace
Definition: gistbuild.c:64
#define RelationGetRelationName(relation)
Definition: rel.h:436
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define GIST_DEFAULT_FILLFACTOR
Definition: gist_private.h:436
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
void freeGISTstate(GISTSTATE *giststate)
Definition: gist.c:1510
XLogRecPtr XLogInsert(RmgrId rmid, uint8 info)
Definition: xloginsert.c:415
GISTSTATE * giststate
Definition: gistbuild.c:59
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:199
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1423
static void gistEmptyAllBuffers(GISTBuildState *buildstate)
Definition: gistbuild.c:992
uint64 XLogRecPtr
Definition: xlogdefs.h:21
#define Assert(condition)
Definition: c.h:675
Relation indexrel
Definition: gistbuild.c:58
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:214
#define RelationNeedsWAL(relation)
Definition: rel.h:505
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2605
void gistFreeBuildBuffers(GISTBuildBuffers *gfbb)
double IndexBuildHeapScan(Relation heapRelation, Relation indexRelation, IndexInfo *indexInfo, bool allow_sync, IndexBuildCallback callback, void *callback_state)
Definition: index.c:2169
void * palloc(Size size)
Definition: mcxt.c:849
static void gistBuildCallback(Relation index, HeapTuple htup, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
Definition: gistbuild.c:458
#define F_LEAF
Definition: gist.h:42
GISTBuildBuffers * gfbb
Definition: gistbuild.c:71
#define GIST_ROOT_BLKNO
Definition: gist_private.h:249
void GISTInitBuffer(Buffer b, uint32 f)
Definition: gistutil.c:701
#define elog
Definition: elog.h:219
void XLogBeginInsert(void)
Definition: xloginsert.c:120
#define PageSetLSN(page, lsn)
Definition: bufpage.h:364
int Buffer
Definition: buf.h:23
Buffer gistNewBuffer(Relation r)
Definition: gistutil.c:762
bytea * rd_options
Definition: rel.h:156
Pointer Page
Definition: bufpage.h:74
double index_tuples
Definition: genam.h:33
double heap_tuples
Definition: genam.h:32
static void gistBuildCallback ( Relation  index,
HeapTuple  htup,
Datum values,
bool isnull,
bool  tupleIsAlive,
void *  state 
)
static

Definition at line 458 of file gistbuild.c.

References BUFFERING_MODE_SWITCH_CHECK_STEP, BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET, GISTBuildState::bufferingMode, calculatePagesPerBuffer(), effective_cache_size, GISTBuildState::freespace, GISTBuildState::gfbb, GIST_BUFFERING_ACTIVE, GIST_BUFFERING_AUTO, GIST_BUFFERING_STATS, gistBufferingBuildInsert(), gistdoinsert(), gistFormTuple(), gistInitBuffering(), GISTBuildState::giststate, IndexTupleSize, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, GISTBuildBuffers::levelStep, MAIN_FORKNUM, MemoryContextReset(), MemoryContextSwitchTo(), GISTBuildBuffers::pagesPerBuffer, RelationData::rd_smgr, smgrnblocks(), HeapTupleData::t_self, IndexTupleData::t_tid, and GISTSTATE::tempCxt.

Referenced by gistbuild().

464 {
465  GISTBuildState *buildstate = (GISTBuildState *) state;
466  IndexTuple itup;
467  MemoryContext oldCtx;
468 
469  oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
470 
471  /* form an index tuple and point it at the heap tuple */
472  itup = gistFormTuple(buildstate->giststate, index, values, isnull, true);
473  itup->t_tid = htup->t_self;
474 
475  if (buildstate->bufferingMode == GIST_BUFFERING_ACTIVE)
476  {
477  /* We have buffers, so use them. */
478  gistBufferingBuildInsert(buildstate, itup);
479  }
480  else
481  {
482  /*
483  * There's no buffers (yet). Since we already have the index relation
484  * locked, we call gistdoinsert directly.
485  */
486  gistdoinsert(index, itup, buildstate->freespace,
487  buildstate->giststate);
488  }
489 
490  /* Update tuple count and total size. */
491  buildstate->indtuples += 1;
492  buildstate->indtuplesSize += IndexTupleSize(itup);
493 
494  MemoryContextSwitchTo(oldCtx);
495  MemoryContextReset(buildstate->giststate->tempCxt);
496 
497  if (buildstate->bufferingMode == GIST_BUFFERING_ACTIVE &&
499  {
500  /* Adjust the target buffer size now */
501  buildstate->gfbb->pagesPerBuffer =
502  calculatePagesPerBuffer(buildstate, buildstate->gfbb->levelStep);
503  }
504 
505  /*
506  * In 'auto' mode, check if the index has grown too large to fit in cache,
507  * and switch to buffering mode if it has.
508  *
509  * To avoid excessive calls to smgrnblocks(), only check this every
510  * BUFFERING_MODE_SWITCH_CHECK_STEP index tuples
511  */
512  if ((buildstate->bufferingMode == GIST_BUFFERING_AUTO &&
513  buildstate->indtuples % BUFFERING_MODE_SWITCH_CHECK_STEP == 0 &&
515  (buildstate->bufferingMode == GIST_BUFFERING_STATS &&
517  {
518  /*
519  * Index doesn't fit in effective cache anymore. Try to switch to
520  * buffering build mode.
521  */
522  gistInitBuffering(buildstate);
523  }
524 }
struct SMgrRelationData * rd_smgr
Definition: rel.h:87
ItemPointerData t_tid
Definition: itup.h:37
int effective_cache_size
Definition: costsize.c:112
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:135
void gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate)
Definition: gist.c:601
GistBufferingMode bufferingMode
Definition: gistbuild.c:74
#define BUFFERING_MODE_SWITCH_CHECK_STEP
Definition: gistbuild.c:32
int64 indtuplesSize
Definition: gistbuild.c:62
ItemPointerData t_self
Definition: htup.h:65
int64 indtuples
Definition: gistbuild.c:61
MemoryContext tempCxt
Definition: gist_private.h:79
Size freespace
Definition: gistbuild.c:64
static int calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep)
Definition: gistbuild.c:425
static void gistBufferingBuildInsert(GISTBuildState *buildstate, IndexTuple itup)
Definition: gistbuild.c:530
GISTSTATE * giststate
Definition: gistbuild.c:59
BlockNumber smgrnblocks(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:672
Definition: regguts.h:298
static Datum values[MAXATTR]
Definition: bootstrap.c:163
GISTBuildBuffers * gfbb
Definition: gistbuild.c:71
static void gistInitBuffering(GISTBuildState *buildstate)
Definition: gistbuild.c:264
#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET
Definition: gistbuild.c:40
IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, Datum attdata[], bool isnull[], bool isleaf)
Definition: gistutil.c:567
#define IndexTupleSize(itup)
Definition: itup.h:70
static void gistEmptyAllBuffers ( GISTBuildState buildstate)
static

Definition at line 992 of file gistbuild.c.

References GISTNodeBuffer::blocksCount, GISTBuildBuffers::bufferEmptyingQueue, GISTBuildBuffers::buffersOnLevels, GISTBuildBuffers::buffersOnLevelsLen, GISTBuildBuffers::context, DEBUG2, elog, GISTBuildState::gfbb, gistProcessEmptyingQueue(), GISTBuildState::giststate, i, lcons(), linitial, list_delete_first(), MemoryContextSwitchTo(), NIL, GISTNodeBuffer::queuedForEmptying, and GISTSTATE::tempCxt.

Referenced by gistbuild().

993 {
994  GISTBuildBuffers *gfbb = buildstate->gfbb;
995  MemoryContext oldCtx;
996  int i;
997 
998  oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
999 
1000  /*
1001  * Iterate through the levels from top to bottom.
1002  */
1003  for (i = gfbb->buffersOnLevelsLen - 1; i >= 0; i--)
1004  {
1005  /*
1006  * Empty all buffers on this level. Note that new buffers can pop up
1007  * in the list during the processing, as a result of page splits, so a
1008  * simple walk through the list won't work. We remove buffers from the
1009  * list when we see them empty; a buffer can't become non-empty once
1010  * it's been fully emptied.
1011  */
1012  while (gfbb->buffersOnLevels[i] != NIL)
1013  {
1014  GISTNodeBuffer *nodeBuffer;
1015 
1016  nodeBuffer = (GISTNodeBuffer *) linitial(gfbb->buffersOnLevels[i]);
1017 
1018  if (nodeBuffer->blocksCount != 0)
1019  {
1020  /*
1021  * Add this buffer to the emptying queue, and proceed to empty
1022  * the queue.
1023  */
1024  if (!nodeBuffer->queuedForEmptying)
1025  {
1027  nodeBuffer->queuedForEmptying = true;
1028  gfbb->bufferEmptyingQueue =
1029  lcons(nodeBuffer, gfbb->bufferEmptyingQueue);
1030  MemoryContextSwitchTo(buildstate->giststate->tempCxt);
1031  }
1032  gistProcessEmptyingQueue(buildstate);
1033  }
1034  else
1035  gfbb->buffersOnLevels[i] =
1037  }
1038  elog(DEBUG2, "emptied all buffers at level %d", i);
1039  }
1040  MemoryContextSwitchTo(oldCtx);
1041 }
#define NIL
Definition: pg_list.h:69
MemoryContext context
Definition: gist_private.h:328
List ** buffersOnLevels
Definition: gist_private.h:355
static void gistProcessEmptyingQueue(GISTBuildState *buildstate)
Definition: gistbuild.c:919
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define linitial(l)
Definition: pg_list.h:111
List * bufferEmptyingQueue
Definition: gist_private.h:344
MemoryContext tempCxt
Definition: gist_private.h:79
#define DEBUG2
Definition: elog.h:24
bool queuedForEmptying
Definition: gist_private.h:294
GISTSTATE * giststate
Definition: gistbuild.c:59
List * lcons(void *datum, List *list)
Definition: list.c:259
GISTBuildBuffers * gfbb
Definition: gistbuild.c:71
int i
#define elog
Definition: elog.h:219
List * list_delete_first(List *list)
Definition: list.c:666
static int gistGetMaxLevel ( Relation  index)
static

Definition at line 1047 of file gistbuild.c.

References DataPageDeleteStack::blkno, buffer, BufferGetPage, FirstOffsetNumber, GIST_ROOT_BLKNO, GIST_SHARE, GistPageIsLeaf, ItemPointerGetBlockNumber, LockBuffer(), PageGetItem, PageGetItemId, ReadBuffer(), IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistInitBuffering().

1048 {
1049  int maxLevel;
1050  BlockNumber blkno;
1051 
1052  /*
1053  * Traverse down the tree, starting from the root, until we hit the leaf
1054  * level.
1055  */
1056  maxLevel = 0;
1057  blkno = GIST_ROOT_BLKNO;
1058  while (true)
1059  {
1060  Buffer buffer;
1061  Page page;
1062  IndexTuple itup;
1063 
1064  buffer = ReadBuffer(index, blkno);
1065 
1066  /*
1067  * There's no concurrent access during index build, so locking is just
1068  * pro forma.
1069  */
1070  LockBuffer(buffer, GIST_SHARE);
1071  page = (Page) BufferGetPage(buffer);
1072 
1073  if (GistPageIsLeaf(page))
1074  {
1075  /* We hit the bottom, so we're done. */
1076  UnlockReleaseBuffer(buffer);
1077  break;
1078  }
1079 
1080  /*
1081  * Pick the first downlink on the page, and follow it. It doesn't
1082  * matter which downlink we choose, the tree has the same depth
1083  * everywhere, so we just pick the first one.
1084  */
1085  itup = (IndexTuple) PageGetItem(page,
1087  blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1088  UnlockReleaseBuffer(buffer);
1089 
1090  /*
1091  * We're going down on the tree. It means that there is yet one more
1092  * level in the tree.
1093  */
1094  maxLevel++;
1095  }
1096  return maxLevel;
1097 }
ItemPointerData t_tid
Definition: itup.h:37
uint32 BlockNumber
Definition: block.h:31
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define GistPageIsLeaf(page)
Definition: gist.h:132
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:214
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
#define GIST_SHARE
Definition: gist_private.h:43
#define GIST_ROOT_BLKNO
Definition: gist_private.h:249
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:76
int Buffer
Definition: buf.h:23
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
static BlockNumber gistGetParent ( GISTBuildState buildstate,
BlockNumber  child 
)
static

Definition at line 1187 of file gistbuild.c.

References DataPageDeleteStack::child, elog, ERROR, HASH_FIND, hash_search(), ParentMapEntry::parentblkno, and GISTBuildState::parentMap.

Referenced by gistBufferingFindCorrectParent().

1188 {
1189  ParentMapEntry *entry;
1190  bool found;
1191 
1192  /* Find node buffer in hash table */
1193  entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
1194  (const void *) &child,
1195  HASH_FIND,
1196  &found);
1197  if (!found)
1198  elog(ERROR, "could not find parent of block %d in lookup table", child);
1199 
1200  return entry->parentblkno;
1201 }
BlockNumber parentblkno
Definition: gistbuild.c:1132
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:885
HTAB * parentMap
Definition: gistbuild.c:72
#define ERROR
Definition: elog.h:43
#define elog
Definition: elog.h:219
static void gistInitBuffering ( GISTBuildState buildstate)
static

Definition at line 264 of file gistbuild.c.

References tupleDesc::attrs, GISTBuildState::bufferingMode, calculatePagesPerBuffer(), DEBUG1, effective_cache_size, elog, GISTBuildState::freespace, GISTBuildState::gfbb, GIST_BUFFERING_ACTIVE, GIST_BUFFERING_DISABLED, gistGetMaxLevel(), gistInitBuildBuffers(), gistInitParentMap(), i, GISTBuildState::indexrel, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, maintenance_work_mem, MAXALIGN, tupleDesc::natts, RelationData::rd_att, SizeOfPageHeaderData, and VARHDRSZ.

Referenced by gistBuildCallback().

265 {
266  Relation index = buildstate->indexrel;
267  int pagesPerBuffer;
268  Size pageFreeSpace;
269  Size itupAvgSize,
270  itupMinSize;
271  double avgIndexTuplesPerPage,
272  maxIndexTuplesPerPage;
273  int i;
274  int levelStep;
275 
276  /* Calc space of index page which is available for index tuples */
277  pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
278  - sizeof(ItemIdData)
279  - buildstate->freespace;
280 
281  /*
282  * Calculate average size of already inserted index tuples using gathered
283  * statistics.
284  */
285  itupAvgSize = (double) buildstate->indtuplesSize /
286  (double) buildstate->indtuples;
287 
288  /*
289  * Calculate minimal possible size of index tuple by index metadata.
290  * Minimal possible size of varlena is VARHDRSZ.
291  *
292  * XXX: that's not actually true, as a short varlen can be just 2 bytes.
293  * And we should take padding into account here.
294  */
295  itupMinSize = (Size) MAXALIGN(sizeof(IndexTupleData));
296  for (i = 0; i < index->rd_att->natts; i++)
297  {
298  if (index->rd_att->attrs[i]->attlen < 0)
299  itupMinSize += VARHDRSZ;
300  else
301  itupMinSize += index->rd_att->attrs[i]->attlen;
302  }
303 
304  /* Calculate average and maximal number of index tuples which fit to page */
305  avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
306  maxIndexTuplesPerPage = pageFreeSpace / itupMinSize;
307 
308  /*
309  * We need to calculate two parameters for the buffering algorithm:
310  * levelStep and pagesPerBuffer.
311  *
312  * levelStep determines the size of subtree that we operate on, while
313  * emptying a buffer. A higher value is better, as you need fewer buffer
314  * emptying steps to build the index. However, if you set it too high, the
315  * subtree doesn't fit in cache anymore, and you quickly lose the benefit
316  * of the buffers.
317  *
318  * In Arge et al's paper, levelStep is chosen as logB(M/4B), where B is
319  * the number of tuples on page (ie. fanout), and M is the amount of
320  * internal memory available. Curiously, they doesn't explain *why* that
321  * setting is optimal. We calculate it by taking the highest levelStep so
322  * that a subtree still fits in cache. For a small B, our way of
323  * calculating levelStep is very close to Arge et al's formula. For a
324  * large B, our formula gives a value that is 2x higher.
325  *
326  * The average size (in pages) of a subtree of depth n can be calculated
327  * as a geometric series:
328  *
329  * B^0 + B^1 + B^2 + ... + B^n = (1 - B^(n + 1)) / (1 - B)
330  *
331  * where B is the average number of index tuples on page. The subtree is
332  * cached in the shared buffer cache and the OS cache, so we choose
333  * levelStep so that the subtree size is comfortably smaller than
334  * effective_cache_size, with a safety factor of 4.
335  *
336  * The estimate on the average number of index tuples on page is based on
337  * average tuple sizes observed before switching to buffered build, so the
338  * real subtree size can be somewhat larger. Also, it would selfish to
339  * gobble the whole cache for our index build. The safety factor of 4
340  * should account for those effects.
341  *
342  * The other limiting factor for setting levelStep is that while
343  * processing a subtree, we need to hold one page for each buffer at the
344  * next lower buffered level. The max. number of buffers needed for that
345  * is maxIndexTuplesPerPage^levelStep. This is very conservative, but
346  * hopefully maintenance_work_mem is set high enough that you're
347  * constrained by effective_cache_size rather than maintenance_work_mem.
348  *
349  * XXX: the buffer hash table consumes a fair amount of memory too per
350  * buffer, but that is not currently taken into account. That scales on
351  * the total number of buffers used, ie. the index size and on levelStep.
352  * Note that a higher levelStep *reduces* the amount of memory needed for
353  * the hash table.
354  */
355  levelStep = 1;
356  for (;;)
357  {
358  double subtreesize;
359  double maxlowestlevelpages;
360 
361  /* size of an average subtree at this levelStep (in pages). */
362  subtreesize =
363  (1 - pow(avgIndexTuplesPerPage, (double) (levelStep + 1))) /
364  (1 - avgIndexTuplesPerPage);
365 
366  /* max number of pages at the lowest level of a subtree */
367  maxlowestlevelpages = pow(maxIndexTuplesPerPage, (double) levelStep);
368 
369  /* subtree must fit in cache (with safety factor of 4) */
370  if (subtreesize > effective_cache_size / 4)
371  break;
372 
373  /* each node in the lowest level of a subtree has one page in memory */
374  if (maxlowestlevelpages > ((double) maintenance_work_mem * 1024) / BLCKSZ)
375  break;
376 
377  /* Good, we can handle this levelStep. See if we can go one higher. */
378  levelStep++;
379  }
380 
381  /*
382  * We just reached an unacceptable value of levelStep in previous loop.
383  * So, decrease levelStep to get last acceptable value.
384  */
385  levelStep--;
386 
387  /*
388  * If there's not enough cache or maintenance_work_mem, fall back to plain
389  * inserts.
390  */
391  if (levelStep <= 0)
392  {
393  elog(DEBUG1, "failed to switch to buffered GiST build");
395  return;
396  }
397 
398  /*
399  * The second parameter to set is pagesPerBuffer, which determines the
400  * size of each buffer. We adjust pagesPerBuffer also during the build,
401  * which is why this calculation is in a separate function.
402  */
403  pagesPerBuffer = calculatePagesPerBuffer(buildstate, levelStep);
404 
405  /* Initialize GISTBuildBuffers with these parameters */
406  buildstate->gfbb = gistInitBuildBuffers(pagesPerBuffer, levelStep,
407  gistGetMaxLevel(index));
408 
409  gistInitParentMap(buildstate);
410 
411  buildstate->bufferingMode = GIST_BUFFERING_ACTIVE;
412 
413  elog(DEBUG1, "switched to buffered GiST build; level step = %d, pagesPerBuffer = %d",
414  levelStep, pagesPerBuffer);
415 }
#define DEBUG1
Definition: elog.h:25
#define VARHDRSZ
Definition: c.h:445
Form_pg_attribute * attrs
Definition: tupdesc.h:74
int effective_cache_size
Definition: costsize.c:112
#define SizeOfPageHeaderData
Definition: bufpage.h:212
GistBufferingMode bufferingMode
Definition: gistbuild.c:74
int natts
Definition: tupdesc.h:73
static int gistGetMaxLevel(Relation index)
Definition: gistbuild.c:1047
Definition: type.h:89
int64 indtuplesSize
Definition: gistbuild.c:62
int64 indtuples
Definition: gistbuild.c:61
GISTBuildBuffers * gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel)
Size freespace
Definition: gistbuild.c:64
struct GISTPageOpaqueData GISTPageOpaqueData
static int calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep)
Definition: gistbuild.c:425
TupleDesc rd_att
Definition: rel.h:115
int maintenance_work_mem
Definition: globals.c:114
Relation indexrel
Definition: gistbuild.c:58
size_t Size
Definition: c.h:356
#define MAXALIGN(LEN)
Definition: c.h:588
GISTBuildBuffers * gfbb
Definition: gistbuild.c:71
int i
static void gistInitParentMap(GISTBuildState *buildstate)
Definition: gistbuild.c:1136
#define elog
Definition: elog.h:219
static void gistInitParentMap ( GISTBuildState buildstate)
static

Definition at line 1136 of file gistbuild.c.

References CurrentMemoryContext, HASHCTL::entrysize, HASH_BLOBS, HASH_CONTEXT, hash_create(), HASH_ELEM, HASHCTL::hcxt, HASHCTL::keysize, and GISTBuildState::parentMap.

Referenced by gistInitBuffering().

1137 {
1138  HASHCTL hashCtl;
1139 
1140  hashCtl.keysize = sizeof(BlockNumber);
1141  hashCtl.entrysize = sizeof(ParentMapEntry);
1142  hashCtl.hcxt = CurrentMemoryContext;
1143  buildstate->parentMap = hash_create("gistbuild parent map",
1144  1024,
1145  &hashCtl,
1147 }
#define HASH_CONTEXT
Definition: hsearch.h:93
#define HASH_ELEM
Definition: hsearch.h:87
MemoryContext hcxt
Definition: hsearch.h:78
Size entrysize
Definition: hsearch.h:73
uint32 BlockNumber
Definition: block.h:31
HTAB * parentMap
Definition: gistbuild.c:72
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define HASH_BLOBS
Definition: hsearch.h:88
HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
Definition: dynahash.c:301
Size keysize
Definition: hsearch.h:72
static void gistMemorizeAllDownlinks ( GISTBuildState buildstate,
Buffer  parent 
)
static

Definition at line 1166 of file gistbuild.c.

References Assert, BufferGetBlockNumber(), BufferGetPage, FirstOffsetNumber, gistMemorizeParent(), GistPageIsLeaf, ItemPointerGetBlockNumber, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, and IndexTupleData::t_tid.

Referenced by gistbufferinginserttuples().

1167 {
1168  OffsetNumber maxoff;
1169  OffsetNumber off;
1170  BlockNumber parentblkno = BufferGetBlockNumber(parentbuf);
1171  Page page = BufferGetPage(parentbuf);
1172 
1173  Assert(!GistPageIsLeaf(page));
1174 
1175  maxoff = PageGetMaxOffsetNumber(page);
1176  for (off = FirstOffsetNumber; off <= maxoff; off++)
1177  {
1178  ItemId iid = PageGetItemId(page, off);
1179  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1180  BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
1181 
1182  gistMemorizeParent(buildstate, childblkno, parentblkno);
1183  }
1184 }
ItemPointerData t_tid
Definition: itup.h:37
uint32 BlockNumber
Definition: block.h:31
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:353
uint16 OffsetNumber
Definition: off.h:24
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
#define GistPageIsLeaf(page)
Definition: gist.h:132
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
#define Assert(condition)
Definition: c.h:675
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
Definition: gistbuild.c:1150
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2605
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:76
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
static void gistMemorizeParent ( GISTBuildState buildstate,
BlockNumber  child,
BlockNumber  parent 
)
static

Definition at line 1150 of file gistbuild.c.

References DataPageDeleteStack::child, HASH_ENTER, hash_search(), DataPageDeleteStack::parent, ParentMapEntry::parentblkno, and GISTBuildState::parentMap.

Referenced by gistbufferinginserttuples(), gistMemorizeAllDownlinks(), and gistProcessItup().

1151 {
1152  ParentMapEntry *entry;
1153  bool found;
1154 
1155  entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
1156  (const void *) &child,
1157  HASH_ENTER,
1158  &found);
1159  entry->parentblkno = parent;
1160 }
BlockNumber parentblkno
Definition: gistbuild.c:1132
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:885
HTAB * parentMap
Definition: gistbuild.c:72
static void gistProcessEmptyingQueue ( GISTBuildState buildstate)
static

Definition at line 919 of file gistbuild.c.

References GISTBuildBuffers::bufferEmptyingQueue, GISTBuildState::gfbb, gistPopItupFromNodeBuffer(), gistProcessItup(), GISTBuildState::giststate, gistUnloadNodeBuffers(), GISTNodeBuffer::level, linitial, list_delete_first(), MemoryContextReset(), NIL, GISTNodeBuffer::nodeBlocknum, GISTNodeBuffer::queuedForEmptying, and GISTSTATE::tempCxt.

Referenced by gistBufferingBuildInsert(), and gistEmptyAllBuffers().

920 {
921  GISTBuildBuffers *gfbb = buildstate->gfbb;
922 
923  /* Iterate while we have elements in buffers emptying stack. */
924  while (gfbb->bufferEmptyingQueue != NIL)
925  {
926  GISTNodeBuffer *emptyingNodeBuffer;
927 
928  /* Get node buffer from emptying stack. */
929  emptyingNodeBuffer = (GISTNodeBuffer *) linitial(gfbb->bufferEmptyingQueue);
931  emptyingNodeBuffer->queuedForEmptying = false;
932 
933  /*
934  * We are going to load last pages of buffers where emptying will be
935  * to. So let's unload any previously loaded buffers.
936  */
937  gistUnloadNodeBuffers(gfbb);
938 
939  /*
940  * Pop tuples from the buffer and run them down to the buffers at
941  * lower level, or leaf pages. We continue until one of the lower
942  * level buffers fills up, or this buffer runs empty.
943  *
944  * In Arge et al's paper, the buffer emptying is stopped after
945  * processing 1/2 node buffer worth of tuples, to avoid overfilling
946  * any of the lower level buffers. However, it's more efficient to
947  * keep going until one of the lower level buffers actually fills up,
948  * so that's what we do. This doesn't need to be exact, if a buffer
949  * overfills by a few tuples, there's no harm done.
950  */
951  while (true)
952  {
953  IndexTuple itup;
954 
955  /* Get next index tuple from the buffer */
956  if (!gistPopItupFromNodeBuffer(gfbb, emptyingNodeBuffer, &itup))
957  break;
958 
959  /*
960  * Run it down to the underlying node buffer or leaf page.
961  *
962  * Note: it's possible that the buffer we're emptying splits as a
963  * result of this call. If that happens, our emptyingNodeBuffer
964  * points to the left half of the split. After split, it's very
965  * likely that the new left buffer is no longer over the half-full
966  * threshold, but we might as well keep flushing tuples from it
967  * until we fill a lower-level buffer.
968  */
969  if (gistProcessItup(buildstate, itup, emptyingNodeBuffer->nodeBlocknum, emptyingNodeBuffer->level))
970  {
971  /*
972  * A lower level buffer filled up. Stop emptying this buffer,
973  * to avoid overflowing the lower level buffer.
974  */
975  break;
976  }
977 
978  /* Free all the memory allocated during index tuple processing */
979  MemoryContextReset(buildstate->giststate->tempCxt);
980  }
981  }
982 }
#define NIL
Definition: pg_list.h:69
static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
Definition: gistbuild.c:546
BlockNumber nodeBlocknum
Definition: gist_private.h:287
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:135
#define linitial(l)
Definition: pg_list.h:111
List * bufferEmptyingQueue
Definition: gist_private.h:344
MemoryContext tempCxt
Definition: gist_private.h:79
bool queuedForEmptying
Definition: gist_private.h:294
GISTSTATE * giststate
Definition: gistbuild.c:59
void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb)
GISTBuildBuffers * gfbb
Definition: gistbuild.c:71
bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple *itup)
List * list_delete_first(List *list)
Definition: list.c:666
static bool gistProcessItup ( GISTBuildState buildstate,
IndexTuple  itup,
BlockNumber  startblkno,
int  startlevel 
)
static

Definition at line 546 of file gistbuild.c.

References Assert, DataPageDeleteStack::blkno, buffer, BUFFER_OVERFLOWED, BufferGetPage, CHECK_FOR_INTERRUPTS, GISTBuildState::gfbb, GIST_EXCLUSIVE, gistbufferinginserttuples(), gistchoose(), gistgetadjusted(), gistGetNodeBuffer(), gistMemorizeParent(), gistPushItupToNodeBuffer(), GISTBuildState::giststate, GISTBuildState::indexrel, InvalidBlockNumber, InvalidOffsetNumber, ItemPointerGetBlockNumber, LEVEL_HAS_BUFFERS, LockBuffer(), PageGetItem, PageGetItemId, ReadBuffer(), result, IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistBufferingBuildInsert(), and gistProcessEmptyingQueue().

548 {
549  GISTSTATE *giststate = buildstate->giststate;
550  GISTBuildBuffers *gfbb = buildstate->gfbb;
551  Relation indexrel = buildstate->indexrel;
552  BlockNumber childblkno;
553  Buffer buffer;
554  bool result = false;
555  BlockNumber blkno;
556  int level;
557  OffsetNumber downlinkoffnum = InvalidOffsetNumber;
558  BlockNumber parentblkno = InvalidBlockNumber;
559 
561 
562  /*
563  * Loop until we reach a leaf page (level == 0) or a level with buffers
564  * (not including the level we start at, because we would otherwise make
565  * no progress).
566  */
567  blkno = startblkno;
568  level = startlevel;
569  for (;;)
570  {
571  ItemId iid;
572  IndexTuple idxtuple,
573  newtup;
574  Page page;
575  OffsetNumber childoffnum;
576 
577  /* Have we reached a level with buffers? */
578  if (LEVEL_HAS_BUFFERS(level, gfbb) && level != startlevel)
579  break;
580 
581  /* Have we reached a leaf page? */
582  if (level == 0)
583  break;
584 
585  /*
586  * Nope. Descend down to the next level then. Choose a child to
587  * descend down to.
588  */
589 
590  buffer = ReadBuffer(indexrel, blkno);
591  LockBuffer(buffer, GIST_EXCLUSIVE);
592 
593  page = (Page) BufferGetPage(buffer);
594  childoffnum = gistchoose(indexrel, page, itup, giststate);
595  iid = PageGetItemId(page, childoffnum);
596  idxtuple = (IndexTuple) PageGetItem(page, iid);
597  childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
598 
599  if (level > 1)
600  gistMemorizeParent(buildstate, childblkno, blkno);
601 
602  /*
603  * Check that the key representing the target child node is consistent
604  * with the key we're inserting. Update it if it's not.
605  */
606  newtup = gistgetadjusted(indexrel, idxtuple, itup, giststate);
607  if (newtup)
608  {
609  blkno = gistbufferinginserttuples(buildstate,
610  buffer,
611  level,
612  &newtup,
613  1,
614  childoffnum,
617  /* gistbufferinginserttuples() released the buffer */
618  }
619  else
620  UnlockReleaseBuffer(buffer);
621 
622  /* Descend to the child */
623  parentblkno = blkno;
624  blkno = childblkno;
625  downlinkoffnum = childoffnum;
626  Assert(level > 0);
627  level--;
628  }
629 
630  if (LEVEL_HAS_BUFFERS(level, gfbb))
631  {
632  /*
633  * We've reached level with buffers. Place the index tuple to the
634  * buffer, and add the buffer to the emptying queue if it overflows.
635  */
636  GISTNodeBuffer *childNodeBuffer;
637 
638  /* Find the buffer or create a new one */
639  childNodeBuffer = gistGetNodeBuffer(gfbb, giststate, blkno, level);
640 
641  /* Add index tuple to it */
642  gistPushItupToNodeBuffer(gfbb, childNodeBuffer, itup);
643 
644  if (BUFFER_OVERFLOWED(childNodeBuffer, gfbb))
645  result = true;
646  }
647  else
648  {
649  /*
650  * We've reached a leaf page. Place the tuple here.
651  */
652  Assert(level == 0);
653  buffer = ReadBuffer(indexrel, blkno);
654  LockBuffer(buffer, GIST_EXCLUSIVE);
655  gistbufferinginserttuples(buildstate, buffer, level,
656  &itup, 1, InvalidOffsetNumber,
657  parentblkno, downlinkoffnum);
658  /* gistbufferinginserttuples() released the buffer */
659  }
660 
661  return result;
662 }
void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple itup)
ItemPointerData t_tid
Definition: itup.h:37
return result
Definition: formatting.c:1633
uint32 BlockNumber
Definition: block.h:31
IndexTuple gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
Definition: gistutil.c:314
#define LEVEL_HAS_BUFFERS(nlevel, gfbb)
Definition: gist_private.h:306
uint16 OffsetNumber
Definition: off.h:24
static BlockNumber gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, int level, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber parentblk, OffsetNumber downlinkoffnum)
Definition: gistbuild.c:677
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3332
IndexTupleData * IndexTuple
Definition: itup.h:53
GISTNodeBuffer * gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, BlockNumber nodeBlocknum, int level)
#define BufferGetPage(buffer)
Definition: bufmgr.h:160
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
Definition: gistutil.c:372
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:231
GISTSTATE * giststate
Definition: gistbuild.c:59
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3546
#define InvalidOffsetNumber
Definition: off.h:26
#define Assert(condition)
Definition: c.h:675
Relation indexrel
Definition: gistbuild.c:58
WalTimeSample buffer[LAG_TRACKER_BUFFER_SIZE]
Definition: walsender.c:214
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:594
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
Definition: gistbuild.c:1150
#define InvalidBlockNumber
Definition: block.h:33
GISTBuildBuffers * gfbb
Definition: gistbuild.c:71
#define BUFFER_OVERFLOWED(nodeBuffer, gfbb)
Definition: gist_private.h:319
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:98
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:76
#define GIST_EXCLUSIVE
Definition: gist_private.h:44
int Buffer
Definition: buf.h:23
#define PageGetItem(page, itemId)
Definition: bufpage.h:336
Pointer Page
Definition: bufpage.h:74
void gistValidateBufferingOption ( char *  value)

Definition at line 241 of file gistbuild.c.

References ereport, errcode(), errdetail(), errmsg(), ERROR, and NULL.

242 {
243  if (value == NULL ||
244  (strcmp(value, "on") != 0 &&
245  strcmp(value, "off") != 0 &&
246  strcmp(value, "auto") != 0))
247  {
248  ereport(ERROR,
249  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
250  errmsg("invalid value for \"buffering\" option"),
251  errdetail("Valid values are \"on\", \"off\", and \"auto\".")));
252  }
253 }
int errcode(int sqlerrcode)
Definition: elog.c:575
#define ERROR
Definition: elog.h:43
static struct @121 value
int errdetail(const char *fmt,...)
Definition: elog.c:873
#define ereport(elevel, rest)
Definition: elog.h:122
#define NULL
Definition: c.h:229
int errmsg(const char *fmt,...)
Definition: elog.c:797