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 "utils/tuplesort.h"
Include dependency graph for gistbuild.c:

Go to the source code of this file.

Data Structures

struct  GISTBuildState
 
struct  GistSortedBuildPageState
 
struct  ParentMapEntry
 

Macros

#define BUFFERING_MODE_SWITCH_CHECK_STEP   256
 
#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET   4096
 

Typedefs

typedef struct GistSortedBuildPageState GistSortedBuildPageState
 

Enumerations

enum  GistBuildMode {
  GIST_SORTED_BUILD, GIST_BUFFERING_DISABLED, GIST_BUFFERING_AUTO, GIST_BUFFERING_STATS,
  GIST_BUFFERING_ACTIVE
}
 

Functions

static void gistSortedBuildCallback (Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
 
static void gist_indexsortbuild (GISTBuildState *state)
 
static void gist_indexsortbuild_pagestate_add (GISTBuildState *state, GistSortedBuildPageState *pagestate, IndexTuple itup)
 
static void gist_indexsortbuild_pagestate_flush (GISTBuildState *state, GistSortedBuildPageState *pagestate)
 
static void gist_indexsortbuild_flush_ready_pages (GISTBuildState *state)
 
static void gistInitBuffering (GISTBuildState *buildstate)
 
static int calculatePagesPerBuffer (GISTBuildState *buildstate, int levelStep)
 
static void gistBuildCallback (Relation index, ItemPointer tid, 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)
 

Macro Definition Documentation

◆ BUFFERING_MODE_SWITCH_CHECK_STEP

#define BUFFERING_MODE_SWITCH_CHECK_STEP   256

Definition at line 52 of file gistbuild.c.

Referenced by gistBuildCallback().

◆ BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET

#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET   4096

Definition at line 60 of file gistbuild.c.

Referenced by gistBuildCallback().

Typedef Documentation

◆ GistSortedBuildPageState

Enumeration Type Documentation

◆ GistBuildMode

Enumerator
GIST_SORTED_BUILD 
GIST_BUFFERING_DISABLED 
GIST_BUFFERING_AUTO 
GIST_BUFFERING_STATS 
GIST_BUFFERING_ACTIVE 

Definition at line 67 of file gistbuild.c.

68 {
69  GIST_SORTED_BUILD, /* bottom-up build by sorting */
70  GIST_BUFFERING_DISABLED, /* in regular build mode and aren't going to
71  * switch */
72  GIST_BUFFERING_AUTO, /* in regular build mode, but will switch to
73  * buffering build mode if the index grows too
74  * big */
75  GIST_BUFFERING_STATS, /* gathering statistics of index tuple size
76  * before switching to the buffering build
77  * mode */
78  GIST_BUFFERING_ACTIVE /* in buffering build mode */
GistBuildMode
Definition: gistbuild.c:67

Function Documentation

◆ calculatePagesPerBuffer()

static int calculatePagesPerBuffer ( GISTBuildState buildstate,
int  levelStep 
)
static

Definition at line 766 of file gistbuild.c.

References GISTBuildState::freespace, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, and SizeOfPageHeaderData.

Referenced by gistBuildCallback(), and gistInitBuffering().

767 {
768  double pagesPerBuffer;
769  double avgIndexTuplesPerPage;
770  double itupAvgSize;
771  Size pageFreeSpace;
772 
773  /* Calc space of index page which is available for index tuples */
774  pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
775  - sizeof(ItemIdData)
776  - buildstate->freespace;
777 
778  /*
779  * Calculate average size of already inserted index tuples using gathered
780  * statistics.
781  */
782  itupAvgSize = (double) buildstate->indtuplesSize /
783  (double) buildstate->indtuples;
784 
785  avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
786 
787  /*
788  * Recalculate required size of buffers.
789  */
790  pagesPerBuffer = 2 * pow(avgIndexTuplesPerPage, levelStep);
791 
792  return (int) rint(pagesPerBuffer);
793 }
#define SizeOfPageHeaderData
Definition: bufpage.h:216
int64 indtuplesSize
Definition: gistbuild.c:99
int64 indtuples
Definition: gistbuild.c:92
Size freespace
Definition: gistbuild.c:88
struct GISTPageOpaqueData GISTPageOpaqueData
size_t Size
Definition: c.h:540

◆ gist_indexsortbuild()

static void gist_indexsortbuild ( GISTBuildState state)
static

Definition at line 396 of file gistbuild.c.

References F_LEAF, gist_indexsortbuild_flush_ready_pages(), gist_indexsortbuild_pagestate_add(), gist_indexsortbuild_pagestate_flush(), GIST_ROOT_BLKNO, GistBuildLSN, gistinitpage(), GISTBuildState::giststate, GISTBuildState::indexrel, log_newpage(), MAIN_FORKNUM, MemoryContextReset(), GistSortedBuildPageState::page, GISTBuildState::pages_allocated, GISTBuildState::pages_written, PageSetChecksumInplace(), PageSetLSN, palloc(), palloc0(), GistSortedBuildPageState::parent, pfree(), RelationData::rd_node, GISTBuildState::ready_num_pages, RelationGetSmgr(), RelationNeedsWAL, smgrextend(), smgrwrite(), GISTBuildState::sortstate, GISTSTATE::tempCxt, and tuplesort_getindextuple().

Referenced by gistbuild().

397 {
398  IndexTuple itup;
399  GistSortedBuildPageState *leafstate;
400  GistSortedBuildPageState *pagestate;
401  Page page;
402 
403  state->pages_allocated = 0;
404  state->pages_written = 0;
405  state->ready_num_pages = 0;
406 
407  /*
408  * Write an empty page as a placeholder for the root page. It will be
409  * replaced with the real root page at the end.
410  */
411  page = palloc0(BLCKSZ);
413  page, true);
414  state->pages_allocated++;
415  state->pages_written++;
416 
417  /* Allocate a temporary buffer for the first leaf page. */
418  leafstate = palloc(sizeof(GistSortedBuildPageState));
419  leafstate->page = page;
420  leafstate->parent = NULL;
421  gistinitpage(page, F_LEAF);
422 
423  /*
424  * Fill index pages with tuples in the sorted order.
425  */
426  while ((itup = tuplesort_getindextuple(state->sortstate, true)) != NULL)
427  {
428  gist_indexsortbuild_pagestate_add(state, leafstate, itup);
430  }
431 
432  /*
433  * Write out the partially full non-root pages.
434  *
435  * Keep in mind that flush can build a new root.
436  */
437  pagestate = leafstate;
438  while (pagestate->parent != NULL)
439  {
440  GistSortedBuildPageState *parent;
441 
442  gist_indexsortbuild_pagestate_flush(state, pagestate);
443  parent = pagestate->parent;
444  pfree(pagestate->page);
445  pfree(pagestate);
446  pagestate = parent;
447  }
448 
450 
451  /* Write out the root */
452  PageSetLSN(pagestate->page, GistBuildLSN);
455  pagestate->page, true);
456  if (RelationNeedsWAL(state->indexrel))
458  pagestate->page, true);
459 
460  pfree(pagestate->page);
461  pfree(pagestate);
462 }
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2465
#define GistBuildLSN
Definition: gist.h:69
BlockNumber pages_written
Definition: gistbuild.c:109
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:143
void gistinitpage(Page page, uint32 f)
Definition: gistutil.c:756
void pfree(void *pointer)
Definition: mcxt.c:1169
BlockNumber pages_allocated
Definition: gistbuild.c:108
MemoryContext tempCxt
Definition: gist_private.h:78
void smgrwrite(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer, bool skipFsync)
Definition: smgr.c:523
int ready_num_pages
Definition: gistbuild.c:111
static void gist_indexsortbuild_pagestate_add(GISTBuildState *state, GistSortedBuildPageState *pagestate, IndexTuple itup)
Definition: gistbuild.c:469
static void gist_indexsortbuild_flush_ready_pages(GISTBuildState *state)
Definition: gistbuild.c:558
struct GistSortedBuildPageState * parent
Definition: gistbuild.c:124
void * palloc0(Size size)
Definition: mcxt.c:1093
static void gist_indexsortbuild_pagestate_flush(GISTBuildState *state, GistSortedBuildPageState *pagestate)
Definition: gistbuild.c:484
GISTSTATE * giststate
Definition: gistbuild.c:86
RelFileNode rd_node
Definition: rel.h:56
static SMgrRelation RelationGetSmgr(Relation rel)
Definition: rel.h:544
Relation indexrel
Definition: gistbuild.c:84
void PageSetChecksumInplace(Page page, BlockNumber blkno)
Definition: bufpage.c:1532
#define RelationNeedsWAL(relation)
Definition: rel.h:601
void smgrextend(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer, bool skipFsync)
Definition: smgr.c:462
void * palloc(Size size)
Definition: mcxt.c:1062
#define F_LEAF
Definition: gist.h:46
XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum, BlockNumber blkno, Page page, bool page_std)
Definition: xloginsert.c:1048
#define GIST_ROOT_BLKNO
Definition: gist_private.h:262
#define PageSetLSN(page, lsn)
Definition: bufpage.h:368
Pointer Page
Definition: bufpage.h:78
Tuplesortstate * sortstate
Definition: gistbuild.c:106

◆ gist_indexsortbuild_flush_ready_pages()

static void gist_indexsortbuild_flush_ready_pages ( GISTBuildState state)
static

Definition at line 558 of file gistbuild.c.

References elog, ERROR, GistBuildLSN, i, GISTBuildState::indexrel, log_newpages(), MAIN_FORKNUM, GistSortedBuildPageState::page, GISTBuildState::pages_written, PageSetChecksumInplace(), PageSetLSN, pfree(), RelationData::rd_node, GISTBuildState::ready_blknos, GISTBuildState::ready_num_pages, GISTBuildState::ready_pages, RelationGetSmgr(), RelationNeedsWAL, and smgrextend().

Referenced by gist_indexsortbuild(), and gist_indexsortbuild_pagestate_flush().

559 {
560  if (state->ready_num_pages == 0)
561  return;
562 
563  for (int i = 0; i < state->ready_num_pages; i++)
564  {
565  Page page = state->ready_pages[i];
566  BlockNumber blkno = state->ready_blknos[i];
567 
568  /* Currently, the blocks must be buffered in order. */
569  if (blkno != state->pages_written)
570  elog(ERROR, "unexpected block number to flush GiST sorting build");
571 
572  PageSetLSN(page, GistBuildLSN);
573  PageSetChecksumInplace(page, blkno);
574  smgrextend(RelationGetSmgr(state->indexrel), MAIN_FORKNUM, blkno, page,
575  true);
576 
577  state->pages_written++;
578  }
579 
580  if (RelationNeedsWAL(state->indexrel))
582  state->ready_blknos, state->ready_pages, true);
583 
584  for (int i = 0; i < state->ready_num_pages; i++)
585  pfree(state->ready_pages[i]);
586 
587  state->ready_num_pages = 0;
588 }
#define GistBuildLSN
Definition: gist.h:69
BlockNumber pages_written
Definition: gistbuild.c:109
uint32 BlockNumber
Definition: block.h:31
Page ready_pages[XLR_MAX_BLOCK_ID]
Definition: gistbuild.c:113
void pfree(void *pointer)
Definition: mcxt.c:1169
#define ERROR
Definition: elog.h:46
BlockNumber ready_blknos[XLR_MAX_BLOCK_ID]
Definition: gistbuild.c:112
int ready_num_pages
Definition: gistbuild.c:111
RelFileNode rd_node
Definition: rel.h:56
static SMgrRelation RelationGetSmgr(Relation rel)
Definition: rel.h:544
Relation indexrel
Definition: gistbuild.c:84
void PageSetChecksumInplace(Page page, BlockNumber blkno)
Definition: bufpage.c:1532
#define RelationNeedsWAL(relation)
Definition: rel.h:601
void smgrextend(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer, bool skipFsync)
Definition: smgr.c:462
void log_newpages(RelFileNode *rnode, ForkNumber forkNum, int num_pages, BlockNumber *blknos, Page *pages, bool page_std)
Definition: xloginsert.c:1080
#define elog(elevel,...)
Definition: elog.h:232
int i
#define PageSetLSN(page, lsn)
Definition: bufpage.h:368
Pointer Page
Definition: bufpage.h:78

◆ gist_indexsortbuild_pagestate_add()

static void gist_indexsortbuild_pagestate_add ( GISTBuildState state,
GistSortedBuildPageState pagestate,
IndexTuple  itup 
)
static

Definition at line 469 of file gistbuild.c.

References GISTBuildState::freespace, gist_indexsortbuild_pagestate_flush(), gistfillbuffer(), IndexTupleSize, InvalidOffsetNumber, GistSortedBuildPageState::page, and PageGetFreeSpace().

Referenced by gist_indexsortbuild(), and gist_indexsortbuild_pagestate_flush().

472 {
473  Size sizeNeeded;
474 
475  /* Does the tuple fit? If not, flush */
476  sizeNeeded = IndexTupleSize(itup) + sizeof(ItemIdData) + state->freespace;
477  if (PageGetFreeSpace(pagestate->page) < sizeNeeded)
478  gist_indexsortbuild_pagestate_flush(state, pagestate);
479 
480  gistfillbuffer(pagestate->page, &itup, 1, InvalidOffsetNumber);
481 }
void gistfillbuffer(Page page, IndexTuple *itup, int len, OffsetNumber off)
Definition: gistutil.c:33
Size PageGetFreeSpace(Page page)
Definition: bufpage.c:900
Size freespace
Definition: gistbuild.c:88
struct ItemIdData ItemIdData
static void gist_indexsortbuild_pagestate_flush(GISTBuildState *state, GistSortedBuildPageState *pagestate)
Definition: gistbuild.c:484
#define InvalidOffsetNumber
Definition: off.h:26
size_t Size
Definition: c.h:540
#define IndexTupleSize(itup)
Definition: itup.h:71

◆ gist_indexsortbuild_pagestate_flush()

static void gist_indexsortbuild_pagestate_flush ( GISTBuildState state,
GistSortedBuildPageState pagestate 
)
static

Definition at line 484 of file gistbuild.c.

References CHECK_FOR_INTERRUPTS, F_LEAF, gist_indexsortbuild_flush_ready_pages(), gist_indexsortbuild_pagestate_add(), gistextractpage(), gistinitpage(), GistPageGetOpaque, GistPageIsLeaf, GISTBuildState::giststate, gistunion(), GISTBuildState::indexrel, ItemPointerSetBlockNumber, MemoryContextSwitchTo(), GistSortedBuildPageState::page, GISTBuildState::pages_allocated, palloc(), GistSortedBuildPageState::parent, GISTBuildState::ready_blknos, GISTBuildState::ready_num_pages, GISTBuildState::ready_pages, IndexTupleData::t_tid, GISTSTATE::tempCxt, and XLR_MAX_BLOCK_ID.

Referenced by gist_indexsortbuild(), and gist_indexsortbuild_pagestate_add().

486 {
487  GistSortedBuildPageState *parent;
488  IndexTuple *itvec;
489  IndexTuple union_tuple;
490  int vect_len;
491  bool isleaf;
492  BlockNumber blkno;
493  MemoryContext oldCtx;
494 
495  /* check once per page */
497 
498  if (state->ready_num_pages == XLR_MAX_BLOCK_ID)
500 
501  /*
502  * The page is now complete. Assign a block number to it, and add it to
503  * the list of finished pages. (We don't write it out immediately, because
504  * we want to WAL-log the pages in batches.)
505  */
506  blkno = state->pages_allocated++;
507  state->ready_blknos[state->ready_num_pages] = blkno;
508  state->ready_pages[state->ready_num_pages] = pagestate->page;
509  state->ready_num_pages++;
510 
511  isleaf = GistPageIsLeaf(pagestate->page);
512 
513  /*
514  * Form a downlink tuple to represent all the tuples on the page.
515  */
516  oldCtx = MemoryContextSwitchTo(state->giststate->tempCxt);
517  itvec = gistextractpage(pagestate->page, &vect_len);
518  union_tuple = gistunion(state->indexrel, itvec, vect_len,
519  state->giststate);
520  ItemPointerSetBlockNumber(&(union_tuple->t_tid), blkno);
521  MemoryContextSwitchTo(oldCtx);
522 
523  /*
524  * Insert the downlink to the parent page. If this was the root, create a
525  * new page as the parent, which becomes the new root.
526  */
527  parent = pagestate->parent;
528  if (parent == NULL)
529  {
530  parent = palloc(sizeof(GistSortedBuildPageState));
531  parent->page = (Page) palloc(BLCKSZ);
532  parent->parent = NULL;
533  gistinitpage(parent->page, 0);
534 
535  pagestate->parent = parent;
536  }
537  gist_indexsortbuild_pagestate_add(state, parent, union_tuple);
538 
539  /* Re-initialize the page buffer for next page on this level. */
540  pagestate->page = palloc(BLCKSZ);
541  gistinitpage(pagestate->page, isleaf ? F_LEAF : 0);
542 
543  /*
544  * Set the right link to point to the previous page. This is just for
545  * debugging purposes: GiST only follows the right link if a page is split
546  * concurrently to a scan, and that cannot happen during index build.
547  *
548  * It's a bit counterintuitive that we set the right link on the new page
549  * to point to the previous page, and not the other way round. But GiST
550  * pages are not ordered like B-tree pages are, so as long as the
551  * right-links form a chain through all the pages in the same level, the
552  * order doesn't matter.
553  */
554  GistPageGetOpaque(pagestate->page)->rightlink = blkno;
555 }
ItemPointerData t_tid
Definition: itup.h:37
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
uint32 BlockNumber
Definition: block.h:31
void gistinitpage(Page page, uint32 f)
Definition: gistutil.c:756
Page ready_pages[XLR_MAX_BLOCK_ID]
Definition: gistbuild.c:113
IndexTuple * gistextractpage(Page page, int *len)
Definition: gistutil.c:94
BlockNumber pages_allocated
Definition: gistbuild.c:108
MemoryContext tempCxt
Definition: gist_private.h:78
BlockNumber ready_blknos[XLR_MAX_BLOCK_ID]
Definition: gistbuild.c:112
#define XLR_MAX_BLOCK_ID
Definition: xlogrecord.h:225
int ready_num_pages
Definition: gistbuild.c:111
#define GistPageIsLeaf(page)
Definition: gist.h:169
static void gist_indexsortbuild_pagestate_add(GISTBuildState *state, GistSortedBuildPageState *pagestate, IndexTuple itup)
Definition: gistbuild.c:469
static void gist_indexsortbuild_flush_ready_pages(GISTBuildState *state)
Definition: gistbuild.c:558
struct GistSortedBuildPageState * parent
Definition: gistbuild.c:124
GISTSTATE * giststate
Definition: gistbuild.c:86
#define GistPageGetOpaque(page)
Definition: gist.h:167
Relation indexrel
Definition: gistbuild.c:84
#define ItemPointerSetBlockNumber(pointer, blockNumber)
Definition: itemptr.h:138
IndexTuple gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
Definition: gistutil.c:218
void * palloc(Size size)
Definition: mcxt.c:1062
#define F_LEAF
Definition: gist.h:46
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:120
Pointer Page
Definition: bufpage.h:78

◆ gistBufferingBuildInsert()

static void gistBufferingBuildInsert ( GISTBuildState buildstate,
IndexTuple  itup 
)
static

Definition at line 877 of file gistbuild.c.

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

Referenced by gistBuildCallback().

878 {
879  /* Insert the tuple to buffers. */
880  gistProcessItup(buildstate, itup, 0, buildstate->gfbb->rootlevel);
881 
882  /* If we filled up (half of a) buffer, process buffer emptying. */
883  gistProcessEmptyingQueue(buildstate);
884 }
static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
Definition: gistbuild.c:893
static void gistProcessEmptyingQueue(GISTBuildState *buildstate)
Definition: gistbuild.c:1267
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100

◆ gistBufferingFindCorrectParent()

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

Definition at line 1193 of file gistbuild.c.

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

Referenced by gistbufferinginserttuples().

1197 {
1198  BlockNumber parent;
1199  Buffer buffer;
1200  Page page;
1201  OffsetNumber maxoff;
1202  OffsetNumber off;
1203 
1204  if (level > 0)
1205  parent = gistGetParent(buildstate, childblkno);
1206  else
1207  {
1208  /*
1209  * For a leaf page, the caller must supply a correct parent block
1210  * number.
1211  */
1212  if (*parentblkno == InvalidBlockNumber)
1213  elog(ERROR, "no parent buffer provided of child %u", childblkno);
1214  parent = *parentblkno;
1215  }
1216 
1217  buffer = ReadBuffer(buildstate->indexrel, parent);
1218  page = BufferGetPage(buffer);
1219  LockBuffer(buffer, GIST_EXCLUSIVE);
1220  gistcheckpage(buildstate->indexrel, buffer);
1221  maxoff = PageGetMaxOffsetNumber(page);
1222 
1223  /* Check if it was not moved */
1224  if (parent == *parentblkno && *parentblkno != InvalidBlockNumber &&
1225  *downlinkoffnum != InvalidOffsetNumber && *downlinkoffnum <= maxoff)
1226  {
1227  ItemId iid = PageGetItemId(page, *downlinkoffnum);
1228  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1229 
1230  if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
1231  {
1232  /* Still there */
1233  return buffer;
1234  }
1235  }
1236 
1237  /*
1238  * Downlink was not at the offset where it used to be. Scan the page to
1239  * find it. During normal gist insertions, it might've moved to another
1240  * page, to the right, but during a buffering build, we keep track of the
1241  * parent of each page in the lookup table so we should always know what
1242  * page it's on.
1243  */
1244  for (off = FirstOffsetNumber; off <= maxoff; off = OffsetNumberNext(off))
1245  {
1246  ItemId iid = PageGetItemId(page, off);
1247  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1248 
1249  if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == childblkno)
1250  {
1251  /* yes!!, found it */
1252  *downlinkoffnum = off;
1253  return buffer;
1254  }
1255  }
1256 
1257  elog(ERROR, "failed to re-find parent for block %u", childblkno);
1258  return InvalidBuffer; /* keep compiler quiet */
1259 }
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:46
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child)
Definition: gistbuild.c:1535
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4011
#define InvalidOffsetNumber
Definition: off.h:26
Relation indexrel
Definition: gistbuild.c:84
void gistcheckpage(Relation rel, Buffer buf)
Definition: gistutil.c:784
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:694
#define OffsetNumberNext(offsetNumber)
Definition: off.h:52
#define InvalidBlockNumber
Definition: block.h:33
#define elog(elevel,...)
Definition: elog.h:232
#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 1024 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(), GistSortedBuildPageState::page, PageGetItem, PageGetItemId, PageGetMaxOffsetNumber, palloc(), ReadBuffer(), GISTBuildBuffers::rootlevel, IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistProcessItup().

1027 {
1028  GISTBuildBuffers *gfbb = buildstate->gfbb;
1029  List *splitinfo;
1030  bool is_split;
1031  BlockNumber placed_to_blk = InvalidBlockNumber;
1032 
1033  is_split = gistplacetopage(buildstate->indexrel,
1034  buildstate->freespace,
1035  buildstate->giststate,
1036  buffer,
1037  itup, ntup, oldoffnum, &placed_to_blk,
1038  InvalidBuffer,
1039  &splitinfo,
1040  false,
1041  buildstate->heaprel, true);
1042 
1043  /*
1044  * If this is a root split, update the root path item kept in memory. This
1045  * ensures that all path stacks are always complete, including all parent
1046  * nodes up to the root. That simplifies the algorithm to re-find correct
1047  * parent.
1048  */
1049  if (is_split && BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO)
1050  {
1051  Page page = BufferGetPage(buffer);
1052  OffsetNumber off;
1053  OffsetNumber maxoff;
1054 
1055  Assert(level == gfbb->rootlevel);
1056  gfbb->rootlevel++;
1057 
1058  elog(DEBUG2, "splitting GiST root page, now %d levels deep", gfbb->rootlevel);
1059 
1060  /*
1061  * All the downlinks on the old root page are now on one of the child
1062  * pages. Visit all the new child pages to memorize the parents of the
1063  * grandchildren.
1064  */
1065  if (gfbb->rootlevel > 1)
1066  {
1067  maxoff = PageGetMaxOffsetNumber(page);
1068  for (off = FirstOffsetNumber; off <= maxoff; off++)
1069  {
1070  ItemId iid = PageGetItemId(page, off);
1071  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1072  BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
1073  Buffer childbuf = ReadBuffer(buildstate->indexrel, childblkno);
1074 
1075  LockBuffer(childbuf, GIST_SHARE);
1076  gistMemorizeAllDownlinks(buildstate, childbuf);
1077  UnlockReleaseBuffer(childbuf);
1078 
1079  /*
1080  * Also remember that the parent of the new child page is the
1081  * root block.
1082  */
1083  gistMemorizeParent(buildstate, childblkno, GIST_ROOT_BLKNO);
1084  }
1085  }
1086  }
1087 
1088  if (splitinfo)
1089  {
1090  /*
1091  * Insert the downlinks to the parent. This is analogous with
1092  * gistfinishsplit() in the regular insertion code, but the locking is
1093  * simpler, and we have to maintain the buffers on internal nodes and
1094  * the parent map.
1095  */
1096  IndexTuple *downlinks;
1097  int ndownlinks,
1098  i;
1099  Buffer parentBuffer;
1100  ListCell *lc;
1101 
1102  /* Parent may have changed since we memorized this path. */
1103  parentBuffer =
1104  gistBufferingFindCorrectParent(buildstate,
1105  BufferGetBlockNumber(buffer),
1106  level,
1107  &parentblk,
1108  &downlinkoffnum);
1109 
1110  /*
1111  * If there's a buffer associated with this page, that needs to be
1112  * split too. gistRelocateBuildBuffersOnSplit() will also adjust the
1113  * downlinks in 'splitinfo', to make sure they're consistent not only
1114  * with the tuples already on the pages, but also the tuples in the
1115  * buffers that will eventually be inserted to them.
1116  */
1118  buildstate->giststate,
1119  buildstate->indexrel,
1120  level,
1121  buffer, splitinfo);
1122 
1123  /* Create an array of all the downlink tuples */
1124  ndownlinks = list_length(splitinfo);
1125  downlinks = (IndexTuple *) palloc(sizeof(IndexTuple) * ndownlinks);
1126  i = 0;
1127  foreach(lc, splitinfo)
1128  {
1129  GISTPageSplitInfo *splitinfo = lfirst(lc);
1130 
1131  /*
1132  * Remember the parent of each new child page in our parent map.
1133  * This assumes that the downlinks fit on the parent page. If the
1134  * parent page is split, too, when we recurse up to insert the
1135  * downlinks, the recursive gistbufferinginserttuples() call will
1136  * update the map again.
1137  */
1138  if (level > 0)
1139  gistMemorizeParent(buildstate,
1140  BufferGetBlockNumber(splitinfo->buf),
1141  BufferGetBlockNumber(parentBuffer));
1142 
1143  /*
1144  * Also update the parent map for all the downlinks that got moved
1145  * to a different page. (actually this also loops through the
1146  * downlinks that stayed on the original page, but it does no
1147  * harm).
1148  */
1149  if (level > 1)
1150  gistMemorizeAllDownlinks(buildstate, splitinfo->buf);
1151 
1152  /*
1153  * Since there's no concurrent access, we can release the lower
1154  * level buffers immediately. This includes the original page.
1155  */
1156  UnlockReleaseBuffer(splitinfo->buf);
1157  downlinks[i++] = splitinfo->downlink;
1158  }
1159 
1160  /* Insert them into parent. */
1161  gistbufferinginserttuples(buildstate, parentBuffer, level + 1,
1162  downlinks, ndownlinks, downlinkoffnum,
1164 
1165  list_free_deep(splitinfo); /* we don't need this anymore */
1166  }
1167  else
1168  UnlockReleaseBuffer(buffer);
1169 
1170  return placed_to_blk;
1171 }
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:222
uint32 BlockNumber
Definition: block.h:31
static Buffer gistBufferingFindCorrectParent(GISTBuildState *buildstate, BlockNumber childblkno, int level, BlockNumber *parentblk, OffsetNumber *downlinkoffnum)
Definition: gistbuild.c:1193
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
void list_free_deep(List *list)
Definition: list.c:1405
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:1024
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3795
#define DEBUG2
Definition: elog.h:24
IndexTuple downlink
Definition: gist_private.h:422
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
Size freespace
Definition: gistbuild.c:88
Relation heaprel
Definition: gistbuild.c:85
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
GISTSTATE * giststate
Definition: gistbuild.c:86
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4011
#define InvalidOffsetNumber
Definition: off.h:26
#define Assert(condition)
Definition: c.h:804
#define lfirst(lc)
Definition: pg_list.h:169
Relation indexrel
Definition: gistbuild.c:84
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:694
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
Definition: gistbuild.c:1498
static void gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parent)
Definition: gistbuild.c:1514
#define InvalidBlockNumber
Definition: block.h:33
static int list_length(const List *l)
Definition: pg_list.h:149
#define GIST_SHARE
Definition: gist_private.h:42
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2752
void * palloc(Size size)
Definition: mcxt.c:1062
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
#define elog(elevel,...)
Definition: elog.h:232
int i
#define GIST_ROOT_BLKNO
Definition: gist_private.h:262
#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 175 of file gistbuild.c.

References Assert, BufferGetBlockNumber(), BufferGetPage, GiSTOptions::buffering_mode, GISTBuildState::buildMode, 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_indexsortbuild(), GIST_OPTION_BUFFERING_OFF, GIST_OPTION_BUFFERING_ON, GIST_ROOT_BLKNO, GIST_SORTED_BUILD, GIST_SORTSUPPORT_PROC, gistBuildCallback(), GistBuildLSN, gistEmptyAllBuffers(), gistFreeBuildBuffers(), GISTInitBuffer(), gistNewBuffer(), gistSortedBuildCallback(), GISTBuildState::giststate, IndexBuildResult::heap_tuples, GISTBuildState::heaprel, i, index_getprocid(), INDEX_MAX_KEYS, IndexBuildResult::index_tuples, GISTBuildState::indexrel, IndexRelationGetNumberOfKeyAttributes, GISTBuildState::indtuples, GISTBuildState::indtuplesSize, initGISTstate(), log_newpage_range(), MAIN_FORKNUM, maintenance_work_mem, MarkBufferDirty(), MemoryContextDelete(), MemoryContextSwitchTo(), OidIsValid, GistSortedBuildPageState::page, PageSetLSN, palloc(), RelationData::rd_options, RelationGetNumberOfBlocks, RelationGetRelationName, RelationNeedsWAL, GISTBuildState::sortstate, START_CRIT_SECTION, table_index_build_scan(), GISTSTATE::tempCxt, tuplesort_begin_index_gist(), tuplesort_end(), tuplesort_performsort(), and UnlockReleaseBuffer().

Referenced by gisthandler().

176 {
177  IndexBuildResult *result;
178  double reltuples;
179  GISTBuildState buildstate;
181  int fillfactor;
182  Oid SortSupportFnOids[INDEX_MAX_KEYS];
184 
185  /*
186  * We expect to be called exactly once for any index relation. If that's
187  * not the case, big trouble's what we have.
188  */
189  if (RelationGetNumberOfBlocks(index) != 0)
190  elog(ERROR, "index \"%s\" already contains data",
191  RelationGetRelationName(index));
192 
193  buildstate.indexrel = index;
194  buildstate.heaprel = heap;
195  buildstate.sortstate = NULL;
196  buildstate.giststate = initGISTstate(index);
197 
198  /*
199  * Create a temporary memory context that is reset once for each tuple
200  * processed. (Note: we don't bother to make this a child of the
201  * giststate's scanCxt, so we have to delete it separately at the end.)
202  */
203  buildstate.giststate->tempCxt = createTempGistContext();
204 
205  /*
206  * Choose build strategy. First check whether the user specified to use
207  * buffering mode. (The use-case for that in the field is somewhat
208  * questionable perhaps, but it's important for testing purposes.)
209  */
210  if (options)
211  {
213  buildstate.buildMode = GIST_BUFFERING_STATS;
214  else if (options->buffering_mode == GIST_OPTION_BUFFERING_OFF)
215  buildstate.buildMode = GIST_BUFFERING_DISABLED;
216  else /* must be "auto" */
217  buildstate.buildMode = GIST_BUFFERING_AUTO;
218  }
219  else
220  {
221  buildstate.buildMode = GIST_BUFFERING_AUTO;
222  }
223 
224  /*
225  * Unless buffering mode was forced, see if we can use sorting instead.
226  */
227  if (buildstate.buildMode != GIST_BUFFERING_STATS)
228  {
229  bool hasallsortsupports = true;
230  int keyscount = IndexRelationGetNumberOfKeyAttributes(index);
231 
232  for (int i = 0; i < keyscount; i++)
233  {
234  SortSupportFnOids[i] = index_getprocid(index, i + 1,
236  if (!OidIsValid(SortSupportFnOids[i]))
237  {
238  hasallsortsupports = false;
239  break;
240  }
241  }
242  if (hasallsortsupports)
243  buildstate.buildMode = GIST_SORTED_BUILD;
244  }
245 
246  /*
247  * Calculate target amount of free space to leave on pages.
248  */
249  fillfactor = options ? options->fillfactor : GIST_DEFAULT_FILLFACTOR;
250  buildstate.freespace = BLCKSZ * (100 - fillfactor) / 100;
251 
252  /*
253  * Build the index using the chosen strategy.
254  */
255  buildstate.indtuples = 0;
256  buildstate.indtuplesSize = 0;
257 
258  if (buildstate.buildMode == GIST_SORTED_BUILD)
259  {
260  /*
261  * Sort all data, build the index from bottom up.
262  */
263  buildstate.sortstate = tuplesort_begin_index_gist(heap,
264  index,
266  NULL,
267  false);
268 
269  /* Scan the table, adding all tuples to the tuplesort */
270  reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
272  (void *) &buildstate, NULL);
273 
274  /*
275  * Perform the sort and build index pages.
276  */
277  tuplesort_performsort(buildstate.sortstate);
278 
279  gist_indexsortbuild(&buildstate);
280 
281  tuplesort_end(buildstate.sortstate);
282  }
283  else
284  {
285  /*
286  * Initialize an empty index and insert all tuples, possibly using
287  * buffers on intermediate levels.
288  */
289  Buffer buffer;
290  Page page;
291 
292  /* initialize the root page */
293  buffer = gistNewBuffer(index);
295  page = BufferGetPage(buffer);
296 
298 
299  GISTInitBuffer(buffer, F_LEAF);
300 
301  MarkBufferDirty(buffer);
302  PageSetLSN(page, GistBuildLSN);
303 
304  UnlockReleaseBuffer(buffer);
305 
307 
308  /* Scan the table, inserting all the tuples to the index. */
309  reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
311  (void *) &buildstate, NULL);
312 
313  /*
314  * If buffering was used, flush out all the tuples that are still in
315  * the buffers.
316  */
317  if (buildstate.buildMode == GIST_BUFFERING_ACTIVE)
318  {
319  elog(DEBUG1, "all tuples processed, emptying buffers");
320  gistEmptyAllBuffers(&buildstate);
321  gistFreeBuildBuffers(buildstate.gfbb);
322  }
323 
324  /*
325  * We didn't write WAL records as we built the index, so if
326  * WAL-logging is required, write all pages to the WAL now.
327  */
328  if (RelationNeedsWAL(index))
329  {
331  0, RelationGetNumberOfBlocks(index),
332  true);
333  }
334  }
335 
336  /* okay, all heap tuples are indexed */
337  MemoryContextSwitchTo(oldcxt);
339 
340  freeGISTstate(buildstate.giststate);
341 
342  /*
343  * Return statistics
344  */
345  result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
346 
347  result->heap_tuples = reltuples;
348  result->index_tuples = (double) buildstate.indtuples;
349 
350  return result;
351 }
void tuplesort_performsort(Tuplesortstate *state)
Definition: tuplesort.c:2040
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:218
#define GistBuildLSN
Definition: gist.h:69
GistOptBufferingMode buffering_mode
Definition: gist_private.h:398
#define DEBUG1
Definition: elog.h:25
static void gistBuildCallback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
Definition: gistbuild.c:799
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1556
MemoryContext createTempGistContext(void)
Definition: gist.c:119
#define GIST_SORTSUPPORT_PROC
Definition: gist.h:40
#define END_CRIT_SECTION()
Definition: miscadmin.h:149
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define START_CRIT_SECTION()
Definition: miscadmin.h:147
unsigned int Oid
Definition: postgres_ext.h:31
static void gist_indexsortbuild(GISTBuildState *state)
Definition: gistbuild.c:396
#define OidIsValid(objectId)
Definition: c.h:710
int64 indtuplesSize
Definition: gistbuild.c:99
static void gistSortedBuildCallback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
Definition: gistbuild.c:362
Tuplesortstate * tuplesort_begin_index_gist(Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, bool randomAccess)
Definition: tuplesort.c:1190
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3795
#define ERROR
Definition: elog.h:46
int fillfactor
Definition: pgbench.c:197
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:1745
int64 indtuples
Definition: gistbuild.c:92
MemoryContext tempCxt
Definition: gist_private.h:78
Size freespace
Definition: gistbuild.c:88
#define RelationGetRelationName(relation)
Definition: rel.h:511
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:496
#define GIST_DEFAULT_FILLFACTOR
Definition: gist_private.h:479
Relation heaprel
Definition: gistbuild.c:85
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
void freeGISTstate(GISTSTATE *giststate)
Definition: gist.c:1631
GistBuildMode buildMode
Definition: gistbuild.c:90
GISTSTATE * giststate
Definition: gistbuild.c:86
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:213
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1503
int maintenance_work_mem
Definition: globals.c:126
static void gistEmptyAllBuffers(GISTBuildState *buildstate)
Definition: gistbuild.c:1340
#define Assert(condition)
Definition: c.h:804
Relation indexrel
Definition: gistbuild.c:84
#define INDEX_MAX_KEYS
#define RelationNeedsWAL(relation)
Definition: rel.h:601
void log_newpage_range(Relation rel, ForkNumber forkNum, BlockNumber startblk, BlockNumber endblk, bool page_std)
Definition: xloginsert.c:1175
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2752
void gistFreeBuildBuffers(GISTBuildBuffers *gfbb)
void * palloc(Size size)
Definition: mcxt.c:1062
#define F_LEAF
Definition: gist.h:46
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
#define elog(elevel,...)
Definition: elog.h:232
int i
#define GIST_ROOT_BLKNO
Definition: gist_private.h:262
void GISTInitBuffer(Buffer b, uint32 f)
Definition: gistutil.c:772
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1464
#define PageSetLSN(page, lsn)
Definition: bufpage.h:368
int Buffer
Definition: buf.h:23
Buffer gistNewBuffer(Relation r)
Definition: gistutil.c:823
bytea * rd_options
Definition: rel.h:170
Pointer Page
Definition: bufpage.h:78
double index_tuples
Definition: genam.h:33
double heap_tuples
Definition: genam.h:32
Tuplesortstate * sortstate
Definition: gistbuild.c:106
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:769

◆ gistBuildCallback()

static void gistBuildCallback ( Relation  index,
ItemPointer  tid,
Datum values,
bool isnull,
bool  tupleIsAlive,
void *  state 
)
static

Definition at line 799 of file gistbuild.c.

References BUFFERING_MODE_SWITCH_CHECK_STEP, BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET, GISTBuildState::buildMode, 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, RelationGetSmgr(), smgrnblocks(), IndexTupleData::t_tid, and GISTSTATE::tempCxt.

Referenced by gistbuild().

805 {
806  GISTBuildState *buildstate = (GISTBuildState *) state;
807  IndexTuple itup;
808  MemoryContext oldCtx;
809 
810  oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
811 
812  /* form an index tuple and point it at the heap tuple */
813  itup = gistFormTuple(buildstate->giststate, index,
814  values, isnull,
815  true);
816  itup->t_tid = *tid;
817 
818  if (buildstate->buildMode == GIST_BUFFERING_ACTIVE)
819  {
820  /* We have buffers, so use them. */
821  gistBufferingBuildInsert(buildstate, itup);
822  }
823  else
824  {
825  /*
826  * There's no buffers (yet). Since we already have the index relation
827  * locked, we call gistdoinsert directly.
828  */
829  gistdoinsert(index, itup, buildstate->freespace,
830  buildstate->giststate, buildstate->heaprel, true);
831  }
832 
833  /* Update tuple count and total size. */
834  buildstate->indtuples += 1;
835  buildstate->indtuplesSize += IndexTupleSize(itup);
836 
837  MemoryContextSwitchTo(oldCtx);
838  MemoryContextReset(buildstate->giststate->tempCxt);
839 
840  if (buildstate->buildMode == GIST_BUFFERING_ACTIVE &&
842  {
843  /* Adjust the target buffer size now */
844  buildstate->gfbb->pagesPerBuffer =
845  calculatePagesPerBuffer(buildstate, buildstate->gfbb->levelStep);
846  }
847 
848  /*
849  * In 'auto' mode, check if the index has grown too large to fit in cache,
850  * and switch to buffering mode if it has.
851  *
852  * To avoid excessive calls to smgrnblocks(), only check this every
853  * BUFFERING_MODE_SWITCH_CHECK_STEP index tuples.
854  *
855  * In 'stats' state, switch as soon as we have seen enough tuples to have
856  * some idea of the average tuple size.
857  */
858  if ((buildstate->buildMode == GIST_BUFFERING_AUTO &&
859  buildstate->indtuples % BUFFERING_MODE_SWITCH_CHECK_STEP == 0 &&
861  MAIN_FORKNUM)) ||
862  (buildstate->buildMode == GIST_BUFFERING_STATS &&
864  {
865  /*
866  * Index doesn't fit in effective cache anymore. Try to switch to
867  * buffering build mode.
868  */
869  gistInitBuffering(buildstate);
870  }
871 }
ItemPointerData t_tid
Definition: itup.h:37
int effective_cache_size
Definition: costsize.c:127
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:143
#define BUFFERING_MODE_SWITCH_CHECK_STEP
Definition: gistbuild.c:52
int64 indtuplesSize
Definition: gistbuild.c:99
void gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate, Relation heapRel, bool is_build)
Definition: gist.c:632
int64 indtuples
Definition: gistbuild.c:92
MemoryContext tempCxt
Definition: gist_private.h:78
Size freespace
Definition: gistbuild.c:88
static int calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep)
Definition: gistbuild.c:766
Relation heaprel
Definition: gistbuild.c:85
GistBuildMode buildMode
Definition: gistbuild.c:90
static void gistBufferingBuildInsert(GISTBuildState *buildstate, IndexTuple itup)
Definition: gistbuild.c:877
GISTSTATE * giststate
Definition: gistbuild.c:86
BlockNumber smgrnblocks(SMgrRelation reln, ForkNumber forknum)
Definition: smgr.c:548
Definition: regguts.h:317
static SMgrRelation RelationGetSmgr(Relation rel)
Definition: rel.h:544
IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, Datum *attdata, bool *isnull, bool isleaf)
Definition: gistutil.c:574
static Datum values[MAXATTR]
Definition: bootstrap.c:166
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
static void gistInitBuffering(GISTBuildState *buildstate)
Definition: gistbuild.c:605
#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET
Definition: gistbuild.c:60
#define IndexTupleSize(itup)
Definition: itup.h:71

◆ gistEmptyAllBuffers()

static void gistEmptyAllBuffers ( GISTBuildState buildstate)
static

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

1341 {
1342  GISTBuildBuffers *gfbb = buildstate->gfbb;
1343  MemoryContext oldCtx;
1344  int i;
1345 
1346  oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
1347 
1348  /*
1349  * Iterate through the levels from top to bottom.
1350  */
1351  for (i = gfbb->buffersOnLevelsLen - 1; i >= 0; i--)
1352  {
1353  /*
1354  * Empty all buffers on this level. Note that new buffers can pop up
1355  * in the list during the processing, as a result of page splits, so a
1356  * simple walk through the list won't work. We remove buffers from the
1357  * list when we see them empty; a buffer can't become non-empty once
1358  * it's been fully emptied.
1359  */
1360  while (gfbb->buffersOnLevels[i] != NIL)
1361  {
1362  GISTNodeBuffer *nodeBuffer;
1363 
1364  nodeBuffer = (GISTNodeBuffer *) linitial(gfbb->buffersOnLevels[i]);
1365 
1366  if (nodeBuffer->blocksCount != 0)
1367  {
1368  /*
1369  * Add this buffer to the emptying queue, and proceed to empty
1370  * the queue.
1371  */
1372  if (!nodeBuffer->queuedForEmptying)
1373  {
1375  nodeBuffer->queuedForEmptying = true;
1376  gfbb->bufferEmptyingQueue =
1377  lcons(nodeBuffer, gfbb->bufferEmptyingQueue);
1378  MemoryContextSwitchTo(buildstate->giststate->tempCxt);
1379  }
1380  gistProcessEmptyingQueue(buildstate);
1381  }
1382  else
1383  gfbb->buffersOnLevels[i] =
1385  }
1386  elog(DEBUG2, "emptied all buffers at level %d", i);
1387  }
1388  MemoryContextSwitchTo(oldCtx);
1389 }
#define NIL
Definition: pg_list.h:65
MemoryContext context
Definition: gist_private.h:341
List ** buffersOnLevels
Definition: gist_private.h:368
static void gistProcessEmptyingQueue(GISTBuildState *buildstate)
Definition: gistbuild.c:1267
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define linitial(l)
Definition: pg_list.h:174
List * bufferEmptyingQueue
Definition: gist_private.h:357
MemoryContext tempCxt
Definition: gist_private.h:78
#define DEBUG2
Definition: elog.h:24
bool queuedForEmptying
Definition: gist_private.h:307
GISTSTATE * giststate
Definition: gistbuild.c:86
List * lcons(void *datum, List *list)
Definition: list.c:468
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
#define elog(elevel,...)
Definition: elog.h:232
int i
List * list_delete_first(List *list)
Definition: list.c:875

◆ gistGetMaxLevel()

static int gistGetMaxLevel ( Relation  index)
static

Definition at line 1395 of file gistbuild.c.

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

Referenced by gistInitBuffering().

1396 {
1397  int maxLevel;
1398  BlockNumber blkno;
1399 
1400  /*
1401  * Traverse down the tree, starting from the root, until we hit the leaf
1402  * level.
1403  */
1404  maxLevel = 0;
1405  blkno = GIST_ROOT_BLKNO;
1406  while (true)
1407  {
1408  Buffer buffer;
1409  Page page;
1410  IndexTuple itup;
1411 
1412  buffer = ReadBuffer(index, blkno);
1413 
1414  /*
1415  * There's no concurrent access during index build, so locking is just
1416  * pro forma.
1417  */
1418  LockBuffer(buffer, GIST_SHARE);
1419  page = (Page) BufferGetPage(buffer);
1420 
1421  if (GistPageIsLeaf(page))
1422  {
1423  /* We hit the bottom, so we're done. */
1424  UnlockReleaseBuffer(buffer);
1425  break;
1426  }
1427 
1428  /*
1429  * Pick the first downlink on the page, and follow it. It doesn't
1430  * matter which downlink we choose, the tree has the same depth
1431  * everywhere, so we just pick the first one.
1432  */
1433  itup = (IndexTuple) PageGetItem(page,
1435  blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1436  UnlockReleaseBuffer(buffer);
1437 
1438  /*
1439  * We're going down on the tree. It means that there is yet one more
1440  * level in the tree.
1441  */
1442  maxLevel++;
1443  }
1444  return maxLevel;
1445 }
ItemPointerData t_tid
Definition: itup.h:37
uint32 BlockNumber
Definition: block.h:31
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3795
#define FirstOffsetNumber
Definition: off.h:27
IndexTupleData * IndexTuple
Definition: itup.h:53
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
#define GistPageIsLeaf(page)
Definition: gist.h:169
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4011
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:694
#define GIST_SHARE
Definition: gist_private.h:42
#define GIST_ROOT_BLKNO
Definition: gist_private.h:262
#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 1535 of file gistbuild.c.

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

Referenced by gistBufferingFindCorrectParent().

1536 {
1537  ParentMapEntry *entry;
1538  bool found;
1539 
1540  /* Find node buffer in hash table */
1541  entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
1542  (const void *) &child,
1543  HASH_FIND,
1544  &found);
1545  if (!found)
1546  elog(ERROR, "could not find parent of block %u in lookup table", child);
1547 
1548  return entry->parentblkno;
1549 }
BlockNumber parentblkno
Definition: gistbuild.c:1480
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:954
HTAB * parentMap
Definition: gistbuild.c:101
#define ERROR
Definition: elog.h:46
#define elog(elevel,...)
Definition: elog.h:232

◆ gistInitBuffering()

static void gistInitBuffering ( GISTBuildState buildstate)
static

Definition at line 605 of file gistbuild.c.

References GISTBuildState::buildMode, 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().

606 {
607  Relation index = buildstate->indexrel;
608  int pagesPerBuffer;
609  Size pageFreeSpace;
610  Size itupAvgSize,
611  itupMinSize;
612  double avgIndexTuplesPerPage,
613  maxIndexTuplesPerPage;
614  int i;
615  int levelStep;
616 
617  /* Calc space of index page which is available for index tuples */
618  pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
619  - sizeof(ItemIdData)
620  - buildstate->freespace;
621 
622  /*
623  * Calculate average size of already inserted index tuples using gathered
624  * statistics.
625  */
626  itupAvgSize = (double) buildstate->indtuplesSize /
627  (double) buildstate->indtuples;
628 
629  /*
630  * Calculate minimal possible size of index tuple by index metadata.
631  * Minimal possible size of varlena is VARHDRSZ.
632  *
633  * XXX: that's not actually true, as a short varlen can be just 2 bytes.
634  * And we should take padding into account here.
635  */
636  itupMinSize = (Size) MAXALIGN(sizeof(IndexTupleData));
637  for (i = 0; i < index->rd_att->natts; i++)
638  {
639  if (TupleDescAttr(index->rd_att, i)->attlen < 0)
640  itupMinSize += VARHDRSZ;
641  else
642  itupMinSize += TupleDescAttr(index->rd_att, i)->attlen;
643  }
644 
645  /* Calculate average and maximal number of index tuples which fit to page */
646  avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
647  maxIndexTuplesPerPage = pageFreeSpace / itupMinSize;
648 
649  /*
650  * We need to calculate two parameters for the buffering algorithm:
651  * levelStep and pagesPerBuffer.
652  *
653  * levelStep determines the size of subtree that we operate on, while
654  * emptying a buffer. A higher value is better, as you need fewer buffer
655  * emptying steps to build the index. However, if you set it too high, the
656  * subtree doesn't fit in cache anymore, and you quickly lose the benefit
657  * of the buffers.
658  *
659  * In Arge et al's paper, levelStep is chosen as logB(M/4B), where B is
660  * the number of tuples on page (ie. fanout), and M is the amount of
661  * internal memory available. Curiously, they doesn't explain *why* that
662  * setting is optimal. We calculate it by taking the highest levelStep so
663  * that a subtree still fits in cache. For a small B, our way of
664  * calculating levelStep is very close to Arge et al's formula. For a
665  * large B, our formula gives a value that is 2x higher.
666  *
667  * The average size (in pages) of a subtree of depth n can be calculated
668  * as a geometric series:
669  *
670  * B^0 + B^1 + B^2 + ... + B^n = (1 - B^(n + 1)) / (1 - B)
671  *
672  * where B is the average number of index tuples on page. The subtree is
673  * cached in the shared buffer cache and the OS cache, so we choose
674  * levelStep so that the subtree size is comfortably smaller than
675  * effective_cache_size, with a safety factor of 4.
676  *
677  * The estimate on the average number of index tuples on page is based on
678  * average tuple sizes observed before switching to buffered build, so the
679  * real subtree size can be somewhat larger. Also, it would selfish to
680  * gobble the whole cache for our index build. The safety factor of 4
681  * should account for those effects.
682  *
683  * The other limiting factor for setting levelStep is that while
684  * processing a subtree, we need to hold one page for each buffer at the
685  * next lower buffered level. The max. number of buffers needed for that
686  * is maxIndexTuplesPerPage^levelStep. This is very conservative, but
687  * hopefully maintenance_work_mem is set high enough that you're
688  * constrained by effective_cache_size rather than maintenance_work_mem.
689  *
690  * XXX: the buffer hash table consumes a fair amount of memory too per
691  * buffer, but that is not currently taken into account. That scales on
692  * the total number of buffers used, ie. the index size and on levelStep.
693  * Note that a higher levelStep *reduces* the amount of memory needed for
694  * the hash table.
695  */
696  levelStep = 1;
697  for (;;)
698  {
699  double subtreesize;
700  double maxlowestlevelpages;
701 
702  /* size of an average subtree at this levelStep (in pages). */
703  subtreesize =
704  (1 - pow(avgIndexTuplesPerPage, (double) (levelStep + 1))) /
705  (1 - avgIndexTuplesPerPage);
706 
707  /* max number of pages at the lowest level of a subtree */
708  maxlowestlevelpages = pow(maxIndexTuplesPerPage, (double) levelStep);
709 
710  /* subtree must fit in cache (with safety factor of 4) */
711  if (subtreesize > effective_cache_size / 4)
712  break;
713 
714  /* each node in the lowest level of a subtree has one page in memory */
715  if (maxlowestlevelpages > ((double) maintenance_work_mem * 1024) / BLCKSZ)
716  break;
717 
718  /* Good, we can handle this levelStep. See if we can go one higher. */
719  levelStep++;
720  }
721 
722  /*
723  * We just reached an unacceptable value of levelStep in previous loop.
724  * So, decrease levelStep to get last acceptable value.
725  */
726  levelStep--;
727 
728  /*
729  * If there's not enough cache or maintenance_work_mem, fall back to plain
730  * inserts.
731  */
732  if (levelStep <= 0)
733  {
734  elog(DEBUG1, "failed to switch to buffered GiST build");
735  buildstate->buildMode = GIST_BUFFERING_DISABLED;
736  return;
737  }
738 
739  /*
740  * The second parameter to set is pagesPerBuffer, which determines the
741  * size of each buffer. We adjust pagesPerBuffer also during the build,
742  * which is why this calculation is in a separate function.
743  */
744  pagesPerBuffer = calculatePagesPerBuffer(buildstate, levelStep);
745 
746  /* Initialize GISTBuildBuffers with these parameters */
747  buildstate->gfbb = gistInitBuildBuffers(pagesPerBuffer, levelStep,
748  gistGetMaxLevel(index));
749 
750  gistInitParentMap(buildstate);
751 
752  buildstate->buildMode = GIST_BUFFERING_ACTIVE;
753 
754  elog(DEBUG1, "switched to buffered GiST build; level step = %d, pagesPerBuffer = %d",
755  levelStep, pagesPerBuffer);
756 }
#define DEBUG1
Definition: elog.h:25
#define TupleDescAttr(tupdesc, i)
Definition: tupdesc.h:92
#define VARHDRSZ
Definition: c.h:627
int effective_cache_size
Definition: costsize.c:127
#define SizeOfPageHeaderData
Definition: bufpage.h:216
static int gistGetMaxLevel(Relation index)
Definition: gistbuild.c:1395
Definition: type.h:89
int64 indtuplesSize
Definition: gistbuild.c:99
int64 indtuples
Definition: gistbuild.c:92
GISTBuildBuffers * gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel)
Size freespace
Definition: gistbuild.c:88
struct GISTPageOpaqueData GISTPageOpaqueData
static int calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep)
Definition: gistbuild.c:766
GistBuildMode buildMode
Definition: gistbuild.c:90
TupleDesc rd_att
Definition: rel.h:110
int maintenance_work_mem
Definition: globals.c:126
Relation indexrel
Definition: gistbuild.c:84
size_t Size
Definition: c.h:540
#define MAXALIGN(LEN)
Definition: c.h:757
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
#define elog(elevel,...)
Definition: elog.h:232
int i
static void gistInitParentMap(GISTBuildState *buildstate)
Definition: gistbuild.c:1484

◆ gistInitParentMap()

static void gistInitParentMap ( GISTBuildState buildstate)
static

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

1485 {
1486  HASHCTL hashCtl;
1487 
1488  hashCtl.keysize = sizeof(BlockNumber);
1489  hashCtl.entrysize = sizeof(ParentMapEntry);
1490  hashCtl.hcxt = CurrentMemoryContext;
1491  buildstate->parentMap = hash_create("gistbuild parent map",
1492  1024,
1493  &hashCtl,
1495 }
#define HASH_CONTEXT
Definition: hsearch.h:102
#define HASH_ELEM
Definition: hsearch.h:95
MemoryContext hcxt
Definition: hsearch.h:86
Size entrysize
Definition: hsearch.h:76
uint32 BlockNumber
Definition: block.h:31
HTAB * parentMap
Definition: gistbuild.c:101
HTAB * hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
Definition: dynahash.c:349
MemoryContext CurrentMemoryContext
Definition: mcxt.c:42
#define HASH_BLOBS
Definition: hsearch.h:97
Size keysize
Definition: hsearch.h:75

◆ gistMemorizeAllDownlinks()

static void gistMemorizeAllDownlinks ( GISTBuildState buildstate,
Buffer  parent 
)
static

Definition at line 1514 of file gistbuild.c.

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

Referenced by gistbufferinginserttuples().

1515 {
1516  OffsetNumber maxoff;
1517  OffsetNumber off;
1518  BlockNumber parentblkno = BufferGetBlockNumber(parentbuf);
1519  Page page = BufferGetPage(parentbuf);
1520 
1521  Assert(!GistPageIsLeaf(page));
1522 
1523  maxoff = PageGetMaxOffsetNumber(page);
1524  for (off = FirstOffsetNumber; off <= maxoff; off++)
1525  {
1526  ItemId iid = PageGetItemId(page, off);
1527  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1528  BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
1529 
1530  gistMemorizeParent(buildstate, childblkno, parentblkno);
1531  }
1532 }
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:169
#define GistPageIsLeaf(page)
Definition: gist.h:169
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
#define Assert(condition)
Definition: c.h:804
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
Definition: gistbuild.c:1498
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2752
#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 1498 of file gistbuild.c.

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

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

1499 {
1500  ParentMapEntry *entry;
1501  bool found;
1502 
1503  entry = (ParentMapEntry *) hash_search(buildstate->parentMap,
1504  (const void *) &child,
1505  HASH_ENTER,
1506  &found);
1507  entry->parentblkno = parent;
1508 }
BlockNumber parentblkno
Definition: gistbuild.c:1480
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:954
HTAB * parentMap
Definition: gistbuild.c:101

◆ gistProcessEmptyingQueue()

static void gistProcessEmptyingQueue ( GISTBuildState buildstate)
static

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

1268 {
1269  GISTBuildBuffers *gfbb = buildstate->gfbb;
1270 
1271  /* Iterate while we have elements in buffers emptying stack. */
1272  while (gfbb->bufferEmptyingQueue != NIL)
1273  {
1274  GISTNodeBuffer *emptyingNodeBuffer;
1275 
1276  /* Get node buffer from emptying stack. */
1277  emptyingNodeBuffer = (GISTNodeBuffer *) linitial(gfbb->bufferEmptyingQueue);
1279  emptyingNodeBuffer->queuedForEmptying = false;
1280 
1281  /*
1282  * We are going to load last pages of buffers where emptying will be
1283  * to. So let's unload any previously loaded buffers.
1284  */
1285  gistUnloadNodeBuffers(gfbb);
1286 
1287  /*
1288  * Pop tuples from the buffer and run them down to the buffers at
1289  * lower level, or leaf pages. We continue until one of the lower
1290  * level buffers fills up, or this buffer runs empty.
1291  *
1292  * In Arge et al's paper, the buffer emptying is stopped after
1293  * processing 1/2 node buffer worth of tuples, to avoid overfilling
1294  * any of the lower level buffers. However, it's more efficient to
1295  * keep going until one of the lower level buffers actually fills up,
1296  * so that's what we do. This doesn't need to be exact, if a buffer
1297  * overfills by a few tuples, there's no harm done.
1298  */
1299  while (true)
1300  {
1301  IndexTuple itup;
1302 
1303  /* Get next index tuple from the buffer */
1304  if (!gistPopItupFromNodeBuffer(gfbb, emptyingNodeBuffer, &itup))
1305  break;
1306 
1307  /*
1308  * Run it down to the underlying node buffer or leaf page.
1309  *
1310  * Note: it's possible that the buffer we're emptying splits as a
1311  * result of this call. If that happens, our emptyingNodeBuffer
1312  * points to the left half of the split. After split, it's very
1313  * likely that the new left buffer is no longer over the half-full
1314  * threshold, but we might as well keep flushing tuples from it
1315  * until we fill a lower-level buffer.
1316  */
1317  if (gistProcessItup(buildstate, itup, emptyingNodeBuffer->nodeBlocknum, emptyingNodeBuffer->level))
1318  {
1319  /*
1320  * A lower level buffer filled up. Stop emptying this buffer,
1321  * to avoid overflowing the lower level buffer.
1322  */
1323  break;
1324  }
1325 
1326  /* Free all the memory allocated during index tuple processing */
1327  MemoryContextReset(buildstate->giststate->tempCxt);
1328  }
1329  }
1330 }
#define NIL
Definition: pg_list.h:65
static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
Definition: gistbuild.c:893
BlockNumber nodeBlocknum
Definition: gist_private.h:300
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:143
#define linitial(l)
Definition: pg_list.h:174
List * bufferEmptyingQueue
Definition: gist_private.h:357
MemoryContext tempCxt
Definition: gist_private.h:78
bool queuedForEmptying
Definition: gist_private.h:307
GISTSTATE * giststate
Definition: gistbuild.c:86
void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb)
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple *itup)
List * list_delete_first(List *list)
Definition: list.c:875

◆ gistProcessItup()

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

Definition at line 893 of file gistbuild.c.

References Assert, 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(), GistSortedBuildPageState::page, PageGetItem, PageGetItemId, ReadBuffer(), IndexTupleData::t_tid, and UnlockReleaseBuffer().

Referenced by gistBufferingBuildInsert(), and gistProcessEmptyingQueue().

895 {
896  GISTSTATE *giststate = buildstate->giststate;
897  GISTBuildBuffers *gfbb = buildstate->gfbb;
898  Relation indexrel = buildstate->indexrel;
899  BlockNumber childblkno;
900  Buffer buffer;
901  bool result = false;
902  BlockNumber blkno;
903  int level;
904  OffsetNumber downlinkoffnum = InvalidOffsetNumber;
905  BlockNumber parentblkno = InvalidBlockNumber;
906 
908 
909  /*
910  * Loop until we reach a leaf page (level == 0) or a level with buffers
911  * (not including the level we start at, because we would otherwise make
912  * no progress).
913  */
914  blkno = startblkno;
915  level = startlevel;
916  for (;;)
917  {
918  ItemId iid;
919  IndexTuple idxtuple,
920  newtup;
921  Page page;
922  OffsetNumber childoffnum;
923 
924  /* Have we reached a level with buffers? */
925  if (LEVEL_HAS_BUFFERS(level, gfbb) && level != startlevel)
926  break;
927 
928  /* Have we reached a leaf page? */
929  if (level == 0)
930  break;
931 
932  /*
933  * Nope. Descend down to the next level then. Choose a child to
934  * descend down to.
935  */
936 
937  buffer = ReadBuffer(indexrel, blkno);
938  LockBuffer(buffer, GIST_EXCLUSIVE);
939 
940  page = (Page) BufferGetPage(buffer);
941  childoffnum = gistchoose(indexrel, page, itup, giststate);
942  iid = PageGetItemId(page, childoffnum);
943  idxtuple = (IndexTuple) PageGetItem(page, iid);
944  childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
945 
946  if (level > 1)
947  gistMemorizeParent(buildstate, childblkno, blkno);
948 
949  /*
950  * Check that the key representing the target child node is consistent
951  * with the key we're inserting. Update it if it's not.
952  */
953  newtup = gistgetadjusted(indexrel, idxtuple, itup, giststate);
954  if (newtup)
955  {
956  blkno = gistbufferinginserttuples(buildstate,
957  buffer,
958  level,
959  &newtup,
960  1,
961  childoffnum,
964  /* gistbufferinginserttuples() released the buffer */
965  }
966  else
967  UnlockReleaseBuffer(buffer);
968 
969  /* Descend to the child */
970  parentblkno = blkno;
971  blkno = childblkno;
972  downlinkoffnum = childoffnum;
973  Assert(level > 0);
974  level--;
975  }
976 
977  if (LEVEL_HAS_BUFFERS(level, gfbb))
978  {
979  /*
980  * We've reached level with buffers. Place the index tuple to the
981  * buffer, and add the buffer to the emptying queue if it overflows.
982  */
983  GISTNodeBuffer *childNodeBuffer;
984 
985  /* Find the buffer or create a new one */
986  childNodeBuffer = gistGetNodeBuffer(gfbb, giststate, blkno, level);
987 
988  /* Add index tuple to it */
989  gistPushItupToNodeBuffer(gfbb, childNodeBuffer, itup);
990 
991  if (BUFFER_OVERFLOWED(childNodeBuffer, gfbb))
992  result = true;
993  }
994  else
995  {
996  /*
997  * We've reached a leaf page. Place the tuple here.
998  */
999  Assert(level == 0);
1000  buffer = ReadBuffer(indexrel, blkno);
1001  LockBuffer(buffer, GIST_EXCLUSIVE);
1002  gistbufferinginserttuples(buildstate, buffer, level,
1003  &itup, 1, InvalidOffsetNumber,
1004  parentblkno, downlinkoffnum);
1005  /* gistbufferinginserttuples() released the buffer */
1006  }
1007 
1008  return result;
1009 }
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:315
#define LEVEL_HAS_BUFFERS(nlevel, gfbb)
Definition: gist_private.h:319
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:1024
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3795
IndexTupleData * IndexTuple
Definition: itup.h:53
GISTNodeBuffer * gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, BlockNumber nodeBlocknum, int level)
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
Definition: gistutil.c:373
#define PageGetItemId(page, offsetNumber)
Definition: bufpage.h:235
GISTSTATE * giststate
Definition: gistbuild.c:86
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:4011
#define InvalidOffsetNumber
Definition: off.h:26
#define Assert(condition)
Definition: c.h:804
Relation indexrel
Definition: gistbuild.c:84
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:694
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
Definition: gistbuild.c:1498
#define InvalidBlockNumber
Definition: block.h:33
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
#define BUFFER_OVERFLOWED(nodeBuffer, gfbb)
Definition: gist_private.h:332
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:120
#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

◆ gistSortedBuildCallback()

static void gistSortedBuildCallback ( Relation  index,
ItemPointer  tid,
Datum values,
bool isnull,
bool  tupleIsAlive,
void *  state 
)
static

Definition at line 362 of file gistbuild.c.

References gistCompressValues(), GISTBuildState::giststate, INDEX_MAX_KEYS, GISTBuildState::indexrel, GISTBuildState::indtuples, MemoryContextReset(), MemoryContextSwitchTo(), GISTBuildState::sortstate, GISTSTATE::tempCxt, and tuplesort_putindextuplevalues().

Referenced by gistbuild().

368 {
369  GISTBuildState *buildstate = (GISTBuildState *) state;
370  MemoryContext oldCtx;
371  Datum compressed_values[INDEX_MAX_KEYS];
372 
373  oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
374 
375  /* Form an index tuple and point it at the heap tuple */
376  gistCompressValues(buildstate->giststate, index,
377  values, isnull,
378  true, compressed_values);
379 
381  buildstate->indexrel,
382  tid,
383  compressed_values, isnull);
384 
385  MemoryContextSwitchTo(oldCtx);
386  MemoryContextReset(buildstate->giststate->tempCxt);
387 
388  /* Update tuple count. */
389  buildstate->indtuples += 1;
390 }
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:143
int64 indtuples
Definition: gistbuild.c:92
MemoryContext tempCxt
Definition: gist_private.h:78
void gistCompressValues(GISTSTATE *giststate, Relation r, Datum *attdata, bool *isnull, bool isleaf, Datum *compatt)
Definition: gistutil.c:595
uintptr_t Datum
Definition: postgres.h:411
GISTSTATE * giststate
Definition: gistbuild.c:86
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
Definition: tuplesort.c:1727
Definition: regguts.h:317
Relation indexrel
Definition: gistbuild.c:84
#define INDEX_MAX_KEYS
static Datum values[MAXATTR]
Definition: bootstrap.c:166
Tuplesortstate * sortstate
Definition: gistbuild.c:106