PostgreSQL Source Code  git master
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/tableam.h"
#include "access/xloginsert.h"
#include "catalog/index.h"
#include "miscadmin.h"
#include "optimizer/optimizer.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 (const char *value)
 

Macro Definition Documentation

◆ BUFFERING_MODE_SWITCH_CHECK_STEP

#define BUFFERING_MODE_SWITCH_CHECK_STEP   256

Definition at line 33 of file gistbuild.c.

Referenced by gistBuildCallback().

◆ BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET

#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET   4096

Definition at line 41 of file gistbuild.c.

Referenced by gistBuildCallback().

Enumeration Type Documentation

◆ GistBufferingMode

Enumerator
GIST_BUFFERING_DISABLED 
GIST_BUFFERING_AUTO 
GIST_BUFFERING_STATS 
GIST_BUFFERING_ACTIVE 

Definition at line 43 of file gistbuild.c.

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

Function Documentation

◆ calculatePagesPerBuffer()

static int calculatePagesPerBuffer ( GISTBuildState buildstate,
int  levelStep 
)
static

Definition at line 428 of file gistbuild.c.

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

Referenced by gistBuildCallback(), and gistInitBuffering().

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

◆ gistBufferingBuildInsert()

static void gistBufferingBuildInsert ( GISTBuildState buildstate,
IndexTuple  itup 
)
static

Definition at line 533 of file gistbuild.c.

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

Referenced by gistBuildCallback().

534 {
535  /* Insert the tuple to buffers. */
536  gistProcessItup(buildstate, itup, 0, buildstate->gfbb->rootlevel);
537 
538  /* If we filled up (half of a) buffer, process buffer emptying. */
539  gistProcessEmptyingQueue(buildstate);
540 }
static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
Definition: gistbuild.c:549
static void gistProcessEmptyingQueue(GISTBuildState *buildstate)
Definition: gistbuild.c:923
GISTBuildBuffers * gfbb
Definition: gistbuild.c:73

◆ gistBufferingFindCorrectParent()

static Buffer gistBufferingFindCorrectParent ( GISTBuildState buildstate,
BlockNumber  childblkno,
int  level,
BlockNumber parentblk,
OffsetNumber downlinkoffnum 
)
static

Definition at line 849 of file gistbuild.c.

References 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().

853 {
854  BlockNumber parent;
855  Buffer buffer;
856  Page page;
857  OffsetNumber maxoff;
858  OffsetNumber off;
859 
860  if (level > 0)
861  parent = gistGetParent(buildstate, childblkno);
862  else
863  {
864  /*
865  * For a leaf page, the caller must supply a correct parent block
866  * number.
867  */
868  if (*parentblkno == InvalidBlockNumber)
869  elog(ERROR, "no parent buffer provided of child %d", childblkno);
870  parent = *parentblkno;
871  }
872 
873  buffer = ReadBuffer(buildstate->indexrel, parent);
874  page = BufferGetPage(buffer);
875  LockBuffer(buffer, GIST_EXCLUSIVE);
876  gistcheckpage(buildstate->indexrel, buffer);
877  maxoff = PageGetMaxOffsetNumber(page);
878 
879  /* Check if it was not moved */
880  if (parent == *parentblkno && *parentblkno != InvalidBlockNumber &&
881  *downlinkoffnum != InvalidOffsetNumber && *downlinkoffnum <= maxoff)
882  {
883  ItemId iid = PageGetItemId(page, *downlinkoffnum);
884  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
885 
886  if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
887  {
888  /* Still there */
889  return buffer;
890  }
891  }
892 
893  /*
894  * Downlink was not at the offset where it used to be. Scan the page to
895  * find it. During normal gist insertions, it might've moved to another
896  * page, to the right, but during a buffering build, we keep track of the
897  * parent of each page in the lookup table so we should always know what
898  * page it's on.
899  */
900  for (off = FirstOffsetNumber; off <= maxoff; off = OffsetNumberNext(off))
901  {
902  ItemId iid = PageGetItemId(page, off);
903  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
904 
905  if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
906  {
907  /* yes!!, found it */
908  *downlinkoffnum = off;
909  return buffer;
910  }
911  }
912 
913  elog(ERROR, "failed to re-find parent for block %u", childblkno);
914  return InvalidBuffer; /* keep compiler quiet */
915 }
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:357
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:159
static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child)
Definition: gistbuild.c:1191
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:3590
#define InvalidOffsetNumber
Definition: off.h:26
Relation indexrel
Definition: gistbuild.c:59
void gistcheckpage(Relation rel, Buffer buf)
Definition: gistutil.c:771
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:596
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
#define InvalidBlockNumber
Definition: block.h:33
#define elog(elevel,...)
Definition: elog.h:226
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
#define GIST_EXCLUSIVE
Definition: gist_private.h:43
int Buffer
Definition: buf.h:23
#define PageGetItem(page, itemId)
Definition: bufpage.h:340
Pointer Page
Definition: bufpage.h:78

◆ gistbufferinginserttuples()

static BlockNumber gistbufferinginserttuples ( GISTBuildState buildstate,
Buffer  buffer,
int  level,
IndexTuple itup,
int  ntup,
OffsetNumber  oldoffnum,
BlockNumber  parentblk,
OffsetNumber  downlinkoffnum 
)
static

Definition at line 680 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, GISTBuildState::heaprel, 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().

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

◆ gistbuild()

IndexBuildResult* gistbuild ( Relation  heap,
Relation  index,
IndexInfo indexInfo 
)

Definition at line 116 of file gistbuild.c.

References Assert, BufferGetBlockNumber(), BufferGetPage, GISTBuildState::bufferingMode, GiSTOptions::bufferingModeOffset, createTempGistContext(), CurrentMemoryContext, DEBUG1, elog, END_CRIT_SECTION, ERROR, F_LEAF, fillfactor, GiSTOptions::fillfactor, freeGISTstate(), GISTBuildState::freespace, GIST_BUFFERING_ACTIVE, GIST_BUFFERING_AUTO, GIST_BUFFERING_DISABLED, GIST_BUFFERING_STATS, GIST_DEFAULT_FILLFACTOR, GIST_ROOT_BLKNO, gistBuildCallback(), GistBuildLSN, gistEmptyAllBuffers(), gistFreeBuildBuffers(), GISTInitBuffer(), gistNewBuffer(), GISTBuildState::giststate, IndexBuildResult::heap_tuples, GISTBuildState::heaprel, IndexBuildResult::index_tuples, GISTBuildState::indexrel, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, initGISTstate(), log_newpage_range(), MAIN_FORKNUM, MarkBufferDirty(), MemoryContextDelete(), MemoryContextSwitchTo(), PageSetLSN, palloc(), RelationData::rd_options, RelationGetNumberOfBlocks, RelationGetRelationName, RelationNeedsWAL, reltuples, START_CRIT_SECTION, table_index_build_scan(), GISTSTATE::tempCxt, and UnlockReleaseBuffer().

Referenced by gisthandler().

117 {
118  IndexBuildResult *result;
119  double reltuples;
120  GISTBuildState buildstate;
121  Buffer buffer;
122  Page page;
124  int fillfactor;
125 
126  buildstate.indexrel = index;
127  buildstate.heaprel = heap;
128  if (index->rd_options)
129  {
130  /* Get buffering mode from the options string */
132  char *bufferingMode = (char *) options + options->bufferingModeOffset;
133 
134  if (strcmp(bufferingMode, "on") == 0)
135  buildstate.bufferingMode = GIST_BUFFERING_STATS;
136  else if (strcmp(bufferingMode, "off") == 0)
138  else
139  buildstate.bufferingMode = GIST_BUFFERING_AUTO;
140 
141  fillfactor = options->fillfactor;
142  }
143  else
144  {
145  /*
146  * By default, switch to buffering mode when the index grows too large
147  * to fit in cache.
148  */
149  buildstate.bufferingMode = GIST_BUFFERING_AUTO;
150  fillfactor = GIST_DEFAULT_FILLFACTOR;
151  }
152  /* Calculate target amount of free space to leave on pages */
153  buildstate.freespace = BLCKSZ * (100 - fillfactor) / 100;
154 
155  /*
156  * We expect to be called exactly once for any index relation. If that's
157  * not the case, big trouble's what we have.
158  */
159  if (RelationGetNumberOfBlocks(index) != 0)
160  elog(ERROR, "index \"%s\" already contains data",
161  RelationGetRelationName(index));
162 
163  /* no locking is needed */
164  buildstate.giststate = initGISTstate(index);
165 
166  /*
167  * Create a temporary memory context that is reset once for each tuple
168  * processed. (Note: we don't bother to make this a child of the
169  * giststate's scanCxt, so we have to delete it separately at the end.)
170  */
171  buildstate.giststate->tempCxt = createTempGistContext();
172 
173  /* initialize the root page */
174  buffer = gistNewBuffer(index);
176  page = BufferGetPage(buffer);
177 
179 
180  GISTInitBuffer(buffer, F_LEAF);
181 
182  MarkBufferDirty(buffer);
183  PageSetLSN(page, GistBuildLSN);
184 
185  UnlockReleaseBuffer(buffer);
186 
188 
189  /* build the index */
190  buildstate.indtuples = 0;
191  buildstate.indtuplesSize = 0;
192 
193  /*
194  * Do the heap scan.
195  */
196  reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
198  (void *) &buildstate, NULL);
199 
200  /*
201  * If buffering was used, flush out all the tuples that are still in the
202  * buffers.
203  */
204  if (buildstate.bufferingMode == GIST_BUFFERING_ACTIVE)
205  {
206  elog(DEBUG1, "all tuples processed, emptying buffers");
207  gistEmptyAllBuffers(&buildstate);
208  gistFreeBuildBuffers(buildstate.gfbb);
209  }
210 
211  /* okay, all heap tuples are indexed */
212  MemoryContextSwitchTo(oldcxt);
214 
215  freeGISTstate(buildstate.giststate);
216 
217  /*
218  * We didn't write WAL records as we built the index, so if WAL-logging is
219  * required, write all pages to the WAL now.
220  */
221  if (RelationNeedsWAL(index))
222  {
224  0, RelationGetNumberOfBlocks(index),
225  true);
226  }
227 
228  /*
229  * Return statistics
230  */
231  result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
232 
233  result->heap_tuples = reltuples;
234  result->index_tuples = (double) buildstate.indtuples;
235 
236  return result;
237 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:211
#define GistBuildLSN
Definition: gist.h:58
#define DEBUG1
Definition: elog.h:25
int bufferingModeOffset
Definition: gist_private.h:387
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1458
MemoryContext createTempGistContext(void)
Definition: gist.c:114
#define END_CRIT_SECTION()
Definition: miscadmin.h:134
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define START_CRIT_SECTION()
Definition: miscadmin.h:132
GistBufferingMode bufferingMode
Definition: gistbuild.c:76
int64 indtuplesSize
Definition: gistbuild.c:64
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3376
#define ERROR
Definition: elog.h:43
int fillfactor
Definition: pgbench.c:157
static double table_index_build_scan(Relation table_rel, Relation index_rel, struct IndexInfo *index_info, bool allow_sync, bool progress, IndexBuildCallback callback, void *callback_state, TableScanDesc scan)
Definition: tableam.h:1499
int64 indtuples
Definition: gistbuild.c:63
MemoryContext tempCxt
Definition: gist_private.h:78
Size freespace
Definition: gistbuild.c:66
#define RelationGetRelationName(relation)
Definition: rel.h:450
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define GIST_DEFAULT_FILLFACTOR
Definition: gist_private.h:461
Relation heaprel
Definition: gistbuild.c:60
#define BufferGetPage(buffer)
Definition: bufmgr.h:159
void freeGISTstate(GISTSTATE *giststate)
Definition: gist.c:1614
GISTSTATE * giststate
Definition: gistbuild.c:61
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:198
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1486
static void gistEmptyAllBuffers(GISTBuildState *buildstate)
Definition: gistbuild.c:996
#define Assert(condition)
Definition: c.h:732
Relation indexrel
Definition: gistbuild.c:59
#define RelationNeedsWAL(relation)
Definition: rel.h:518
void log_newpage_range(Relation rel, ForkNumber forkNum, BlockNumber startblk, BlockNumber endblk, bool page_std)
Definition: xloginsert.c:1042
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2613
void gistFreeBuildBuffers(GISTBuildBuffers *gfbb)
void * palloc(Size size)
Definition: mcxt.c:924
static void gistBuildCallback(Relation index, HeapTuple htup, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
Definition: gistbuild.c:461
#define F_LEAF
Definition: gist.h:43
GISTBuildBuffers * gfbb
Definition: gistbuild.c:73
#define elog(elevel,...)
Definition: elog.h:226
#define GIST_ROOT_BLKNO
Definition: gist_private.h:259
void GISTInitBuffer(Buffer b, uint32 f)
Definition: gistutil.c:749
#define PageSetLSN(page, lsn)
Definition: bufpage.h:368
int Buffer
Definition: buf.h:23
Buffer gistNewBuffer(Relation r)
Definition: gistutil.c:810
float4 reltuples
Definition: pg_class.h:63
bytea * rd_options
Definition: rel.h:126
Pointer Page
Definition: bufpage.h:78
double index_tuples
Definition: genam.h:33
double heap_tuples
Definition: genam.h:32

◆ gistBuildCallback()

static void gistBuildCallback ( Relation  index,
HeapTuple  htup,
Datum values,
bool isnull,
bool  tupleIsAlive,
void *  state 
)
static

Definition at line 461 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, GISTBuildState::heaprel, 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().

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

◆ gistEmptyAllBuffers()

static void gistEmptyAllBuffers ( GISTBuildState buildstate)
static

Definition at line 996 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().

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

◆ gistGetMaxLevel()

static int gistGetMaxLevel ( Relation  index)
static

Definition at line 1051 of file gistbuild.c.

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

Referenced by gistInitBuffering().

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

◆ gistGetParent()

static BlockNumber gistGetParent ( GISTBuildState buildstate,
BlockNumber  child 
)
static

Definition at line 1191 of file gistbuild.c.

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

Referenced by gistBufferingFindCorrectParent().

1192 {
1193  ParentMapEntry *entry;
1194  bool found;
1195 
1196  /* Find node buffer in hash table */
1197  entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
1198  (const void *) &child,
1199  HASH_FIND,
1200  &found);
1201  if (!found)
1202  elog(ERROR, "could not find parent of block %d in lookup table", child);
1203 
1204  return entry->parentblkno;
1205 }
BlockNumber parentblkno
Definition: gistbuild.c:1136
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:906
HTAB * parentMap
Definition: gistbuild.c:74
#define ERROR
Definition: elog.h:43
#define elog(elevel,...)
Definition: elog.h:226

◆ gistInitBuffering()

static void gistInitBuffering ( GISTBuildState buildstate)
static

Definition at line 267 of file gistbuild.c.

References 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, TupleDescData::natts, RelationData::rd_att, SizeOfPageHeaderData, TupleDescAttr, and VARHDRSZ.

Referenced by gistBuildCallback().

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

◆ gistInitParentMap()

static void gistInitParentMap ( GISTBuildState buildstate)
static

Definition at line 1140 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().

1141 {
1142  HASHCTL hashCtl;
1143 
1144  hashCtl.keysize = sizeof(BlockNumber);
1145  hashCtl.entrysize = sizeof(ParentMapEntry);
1146  hashCtl.hcxt = CurrentMemoryContext;
1147  buildstate->parentMap = hash_create("gistbuild parent map",
1148  1024,
1149  &hashCtl,
1151 }
#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:74
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define HASH_BLOBS
Definition: hsearch.h:88
HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
Definition: dynahash.c:316
Size keysize
Definition: hsearch.h:72

◆ gistMemorizeAllDownlinks()

static void gistMemorizeAllDownlinks ( GISTBuildState buildstate,
Buffer  parent 
)
static

Definition at line 1170 of file gistbuild.c.

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

Referenced by gistbufferinginserttuples().

1171 {
1172  OffsetNumber maxoff;
1173  OffsetNumber off;
1174  BlockNumber parentblkno = BufferGetBlockNumber(parentbuf);
1175  Page page = BufferGetPage(parentbuf);
1176 
1177  Assert(!GistPageIsLeaf(page));
1178 
1179  maxoff = PageGetMaxOffsetNumber(page);
1180  for (off = FirstOffsetNumber; off <= maxoff; off++)
1181  {
1182  ItemId iid = PageGetItemId(page, off);
1183  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1184  BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
1185 
1186  gistMemorizeParent(buildstate, childblkno, parentblkno);
1187  }
1188 }
ItemPointerData t_tid
Definition: itup.h:37
uint32 BlockNumber
Definition: block.h:31
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
uint16 OffsetNumber
Definition: off.h:24
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:159
#define GistPageIsLeaf(page)
Definition: gist.h:140
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
#define Assert(condition)
Definition: c.h:732
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
Definition: gistbuild.c:1154
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2613
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:98
#define PageGetItem(page, itemId)
Definition: bufpage.h:340
Pointer Page
Definition: bufpage.h:78

◆ gistMemorizeParent()

static void gistMemorizeParent ( GISTBuildState buildstate,
BlockNumber  child,
BlockNumber  parent 
)
static

Definition at line 1154 of file gistbuild.c.

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

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

1155 {
1156  ParentMapEntry *entry;
1157  bool found;
1158 
1159  entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
1160  (const void *) &child,
1161  HASH_ENTER,
1162  &found);
1163  entry->parentblkno = parent;
1164 }
BlockNumber parentblkno
Definition: gistbuild.c:1136
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:906
HTAB * parentMap
Definition: gistbuild.c:74

◆ gistProcessEmptyingQueue()

static void gistProcessEmptyingQueue ( GISTBuildState buildstate)
static

Definition at line 923 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().

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

◆ gistProcessItup()

static bool gistProcessItup ( GISTBuildState buildstate,
IndexTuple  itup,
BlockNumber  startblkno,
int  startlevel 
)
static

Definition at line 549 of file gistbuild.c.

References Assert, DataPageDeleteStack::blkno, 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(), IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistBufferingBuildInsert(), and gistProcessEmptyingQueue().

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

◆ gistValidateBufferingOption()

void gistValidateBufferingOption ( const char *  value)

Definition at line 244 of file gistbuild.c.

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

245 {
246  if (value == NULL ||
247  (strcmp(value, "on") != 0 &&
248  strcmp(value, "off") != 0 &&
249  strcmp(value, "auto") != 0))
250  {
251  ereport(ERROR,
252  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
253  errmsg("invalid value for \"buffering\" option"),
254  errdetail("Valid values are \"on\", \"off\", and \"auto\".")));
255  }
256 }
static struct @144 value
int errcode(int sqlerrcode)
Definition: elog.c:570
#define ERROR
Definition: elog.h:43
int errdetail(const char *fmt,...)
Definition: elog.c:860
#define ereport(elevel, rest)
Definition: elog.h:141
int errmsg(const char *fmt,...)
Definition: elog.c:784