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 769 of file gistbuild.c.

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

Referenced by gistBuildCallback(), and gistInitBuffering().

770 {
771  double pagesPerBuffer;
772  double avgIndexTuplesPerPage;
773  double itupAvgSize;
774  Size pageFreeSpace;
775 
776  /* Calc space of index page which is available for index tuples */
777  pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
778  - sizeof(ItemIdData)
779  - buildstate->freespace;
780 
781  /*
782  * Calculate average size of already inserted index tuples using gathered
783  * statistics.
784  */
785  itupAvgSize = (double) buildstate->indtuplesSize /
786  (double) buildstate->indtuples;
787 
788  avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
789 
790  /*
791  * Recalculate required size of buffers.
792  */
793  pagesPerBuffer = 2 * pow(avgIndexTuplesPerPage, levelStep);
794 
795  return (int) rint(pagesPerBuffer);
796 }
#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:474

◆ 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, RelationData::rd_smgr, GISTBuildState::ready_num_pages, RelationNeedsWAL, RelationOpenSmgr, 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);
412  RelationOpenSmgr(state->indexrel);
414  page, true);
415  state->pages_allocated++;
416  state->pages_written++;
417 
418  /* Allocate a temporary buffer for the first leaf page. */
419  leafstate = palloc(sizeof(GistSortedBuildPageState));
420  leafstate->page = page;
421  leafstate->parent = NULL;
422  gistinitpage(page, F_LEAF);
423 
424  /*
425  * Fill index pages with tuples in the sorted order.
426  */
427  while ((itup = tuplesort_getindextuple(state->sortstate, true)) != NULL)
428  {
429  gist_indexsortbuild_pagestate_add(state, leafstate, itup);
431  }
432 
433  /*
434  * Write out the partially full non-root pages.
435  *
436  * Keep in mind that flush can build a new root.
437  */
438  pagestate = leafstate;
439  while (pagestate->parent != NULL)
440  {
441  GistSortedBuildPageState *parent;
442 
443  gist_indexsortbuild_pagestate_flush(state, pagestate);
444  parent = pagestate->parent;
445  pfree(pagestate->page);
446  pfree(pagestate);
447  pagestate = parent;
448  }
449 
451 
452  /* Write out the root */
453  RelationOpenSmgr(state->indexrel);
454  PageSetLSN(pagestate->page, GistBuildLSN);
457  pagestate->page, true);
458  if (RelationNeedsWAL(state->indexrel))
460  pagestate->page, true);
461 
462  pfree(pagestate->page);
463  pfree(pagestate);
464 }
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
Definition: tuplesort.c:2446
#define GistBuildLSN
Definition: gist.h:61
BlockNumber pages_written
Definition: gistbuild.c:109
struct SMgrRelationData * rd_smgr
Definition: rel.h:57
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:137
void gistinitpage(Page page, uint32 f)
Definition: gistutil.c:756
#define RelationOpenSmgr(relation)
Definition: rel.h:513
void pfree(void *pointer)
Definition: mcxt.c:1057
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:524
int ready_num_pages
Definition: gistbuild.c:111
static void gist_indexsortbuild_pagestate_add(GISTBuildState *state, GistSortedBuildPageState *pagestate, IndexTuple itup)
Definition: gistbuild.c:471
static void gist_indexsortbuild_flush_ready_pages(GISTBuildState *state)
Definition: gistbuild.c:560
struct GistSortedBuildPageState * parent
Definition: gistbuild.c:124
void * palloc0(Size size)
Definition: mcxt.c:981
static void gist_indexsortbuild_pagestate_flush(GISTBuildState *state, GistSortedBuildPageState *pagestate)
Definition: gistbuild.c:486
GISTSTATE * giststate
Definition: gistbuild.c:86
RelFileNode rd_node
Definition: rel.h:55
Relation indexrel
Definition: gistbuild.c:84
void PageSetChecksumInplace(Page page, BlockNumber blkno)
Definition: bufpage.c:1414
#define RelationNeedsWAL(relation)
Definition: rel.h:562
void smgrextend(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer, bool skipFsync)
Definition: smgr.c:463
void * palloc(Size size)
Definition: mcxt.c:950
#define F_LEAF
Definition: gist.h:46
XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum, BlockNumber blkno, Page page, bool page_std)
Definition: xloginsert.c:996
#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 560 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, RelationData::rd_smgr, GISTBuildState::ready_blknos, GISTBuildState::ready_num_pages, GISTBuildState::ready_pages, RelationNeedsWAL, RelationOpenSmgr, and smgrextend().

Referenced by gist_indexsortbuild(), and gist_indexsortbuild_pagestate_flush().

561 {
562  if (state->ready_num_pages == 0)
563  return;
564 
565  RelationOpenSmgr(state->indexrel);
566 
567  for (int i = 0; i < state->ready_num_pages; i++)
568  {
569  Page page = state->ready_pages[i];
570  BlockNumber blkno = state->ready_blknos[i];
571 
572  /* Currently, the blocks must be buffered in order. */
573  if (blkno != state->pages_written)
574  elog(ERROR, "unexpected block number to flush GiST sorting build");
575 
576  PageSetLSN(page, GistBuildLSN);
577  PageSetChecksumInplace(page, blkno);
578  smgrextend(state->indexrel->rd_smgr, MAIN_FORKNUM, blkno, page, true);
579 
580  state->pages_written++;
581  }
582 
583  if (RelationNeedsWAL(state->indexrel))
585  state->ready_blknos, state->ready_pages, true);
586 
587  for (int i = 0; i < state->ready_num_pages; i++)
588  pfree(state->ready_pages[i]);
589 
590  state->ready_num_pages = 0;
591 }
#define GistBuildLSN
Definition: gist.h:61
BlockNumber pages_written
Definition: gistbuild.c:109
struct SMgrRelationData * rd_smgr
Definition: rel.h:57
uint32 BlockNumber
Definition: block.h:31
Page ready_pages[XLR_MAX_BLOCK_ID]
Definition: gistbuild.c:113
#define RelationOpenSmgr(relation)
Definition: rel.h:513
void pfree(void *pointer)
Definition: mcxt.c:1057
#define ERROR
Definition: elog.h:43
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:55
Relation indexrel
Definition: gistbuild.c:84
void PageSetChecksumInplace(Page page, BlockNumber blkno)
Definition: bufpage.c:1414
#define RelationNeedsWAL(relation)
Definition: rel.h:562
void smgrextend(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum, char *buffer, bool skipFsync)
Definition: smgr.c:463
void log_newpages(RelFileNode *rnode, ForkNumber forkNum, int num_pages, BlockNumber *blknos, Page *pages, bool page_std)
Definition: xloginsert.c:1028
#define elog(elevel,...)
Definition: elog.h:214
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 471 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().

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

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

◆ gistBufferingBuildInsert()

static void gistBufferingBuildInsert ( GISTBuildState buildstate,
IndexTuple  itup 
)
static

Definition at line 879 of file gistbuild.c.

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

Referenced by gistBuildCallback().

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

◆ gistBufferingFindCorrectParent()

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

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

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

1029 {
1030  GISTBuildBuffers *gfbb = buildstate->gfbb;
1031  List *splitinfo;
1032  bool is_split;
1033  BlockNumber placed_to_blk = InvalidBlockNumber;
1034 
1035  is_split = gistplacetopage(buildstate->indexrel,
1036  buildstate->freespace,
1037  buildstate->giststate,
1038  buffer,
1039  itup, ntup, oldoffnum, &placed_to_blk,
1040  InvalidBuffer,
1041  &splitinfo,
1042  false,
1043  buildstate->heaprel, true);
1044 
1045  /*
1046  * If this is a root split, update the root path item kept in memory. This
1047  * ensures that all path stacks are always complete, including all parent
1048  * nodes up to the root. That simplifies the algorithm to re-find correct
1049  * parent.
1050  */
1051  if (is_split && BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO)
1052  {
1053  Page page = BufferGetPage(buffer);
1054  OffsetNumber off;
1055  OffsetNumber maxoff;
1056 
1057  Assert(level == gfbb->rootlevel);
1058  gfbb->rootlevel++;
1059 
1060  elog(DEBUG2, "splitting GiST root page, now %d levels deep", gfbb->rootlevel);
1061 
1062  /*
1063  * All the downlinks on the old root page are now on one of the child
1064  * pages. Visit all the new child pages to memorize the parents of the
1065  * grandchildren.
1066  */
1067  if (gfbb->rootlevel > 1)
1068  {
1069  maxoff = PageGetMaxOffsetNumber(page);
1070  for (off = FirstOffsetNumber; off <= maxoff; off++)
1071  {
1072  ItemId iid = PageGetItemId(page, off);
1073  IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
1074  BlockNumber childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
1075  Buffer childbuf = ReadBuffer(buildstate->indexrel, childblkno);
1076 
1077  LockBuffer(childbuf, GIST_SHARE);
1078  gistMemorizeAllDownlinks(buildstate, childbuf);
1079  UnlockReleaseBuffer(childbuf);
1080 
1081  /*
1082  * Also remember that the parent of the new child page is the
1083  * root block.
1084  */
1085  gistMemorizeParent(buildstate, childblkno, GIST_ROOT_BLKNO);
1086  }
1087  }
1088  }
1089 
1090  if (splitinfo)
1091  {
1092  /*
1093  * Insert the downlinks to the parent. This is analogous with
1094  * gistfinishsplit() in the regular insertion code, but the locking is
1095  * simpler, and we have to maintain the buffers on internal nodes and
1096  * the parent map.
1097  */
1098  IndexTuple *downlinks;
1099  int ndownlinks,
1100  i;
1101  Buffer parentBuffer;
1102  ListCell *lc;
1103 
1104  /* Parent may have changed since we memorized this path. */
1105  parentBuffer =
1106  gistBufferingFindCorrectParent(buildstate,
1107  BufferGetBlockNumber(buffer),
1108  level,
1109  &parentblk,
1110  &downlinkoffnum);
1111 
1112  /*
1113  * If there's a buffer associated with this page, that needs to be
1114  * split too. gistRelocateBuildBuffersOnSplit() will also adjust the
1115  * downlinks in 'splitinfo', to make sure they're consistent not only
1116  * with the tuples already on the pages, but also the tuples in the
1117  * buffers that will eventually be inserted to them.
1118  */
1120  buildstate->giststate,
1121  buildstate->indexrel,
1122  level,
1123  buffer, splitinfo);
1124 
1125  /* Create an array of all the downlink tuples */
1126  ndownlinks = list_length(splitinfo);
1127  downlinks = (IndexTuple *) palloc(sizeof(IndexTuple) * ndownlinks);
1128  i = 0;
1129  foreach(lc, splitinfo)
1130  {
1131  GISTPageSplitInfo *splitinfo = lfirst(lc);
1132 
1133  /*
1134  * Remember the parent of each new child page in our parent map.
1135  * This assumes that the downlinks fit on the parent page. If the
1136  * parent page is split, too, when we recurse up to insert the
1137  * downlinks, the recursive gistbufferinginserttuples() call will
1138  * update the map again.
1139  */
1140  if (level > 0)
1141  gistMemorizeParent(buildstate,
1142  BufferGetBlockNumber(splitinfo->buf),
1143  BufferGetBlockNumber(parentBuffer));
1144 
1145  /*
1146  * Also update the parent map for all the downlinks that got moved
1147  * to a different page. (actually this also loops through the
1148  * downlinks that stayed on the original page, but it does no
1149  * harm).
1150  */
1151  if (level > 1)
1152  gistMemorizeAllDownlinks(buildstate, splitinfo->buf);
1153 
1154  /*
1155  * Since there's no concurrent access, we can release the lower
1156  * level buffers immediately. This includes the original page.
1157  */
1158  UnlockReleaseBuffer(splitinfo->buf);
1159  downlinks[i++] = splitinfo->downlink;
1160  }
1161 
1162  /* Insert them into parent. */
1163  gistbufferinginserttuples(buildstate, parentBuffer, level + 1,
1164  downlinks, ndownlinks, downlinkoffnum,
1166 
1167  list_free_deep(splitinfo); /* we don't need this anymore */
1168  }
1169  else
1170  UnlockReleaseBuffer(buffer);
1171 
1172  return placed_to_blk;
1173 }
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:221
uint32 BlockNumber
Definition: block.h:31
static Buffer gistBufferingFindCorrectParent(GISTBuildState *buildstate, BlockNumber childblkno, int level, BlockNumber *parentblk, OffsetNumber *downlinkoffnum)
Definition: gistbuild.c:1195
#define PageGetMaxOffsetNumber(page)
Definition: bufpage.h:357
void list_free_deep(List *list)
Definition: list.c:1390
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:1026
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3534
#define DEBUG2
Definition: elog.h:24
IndexTuple downlink
Definition: gist_private.h:421
#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:3750
#define InvalidOffsetNumber
Definition: off.h:26
#define Assert(condition)
Definition: c.h:746
#define lfirst(lc)
Definition: pg_list.h:169
Relation indexrel
Definition: gistbuild.c:84
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
Definition: bufmgr.c:607
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
Definition: gistbuild.c:1500
static void gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parent)
Definition: gistbuild.c:1516
#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:2661
void * palloc(Size size)
Definition: mcxt.c:950
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
#define elog(elevel,...)
Definition: elog.h:214
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:2021
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:212
#define GistBuildLSN
Definition: gist.h:61
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:802
void MarkBufferDirty(Buffer buffer)
Definition: bufmgr.c:1469
MemoryContext createTempGistContext(void)
Definition: gist.c:119
#define GIST_SORTSUPPORT_PROC
Definition: gist.h:40
#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
unsigned int Oid
Definition: postgres_ext.h:31
static void gist_indexsortbuild(GISTBuildState *state)
Definition: gistbuild.c:396
#define OidIsValid(objectId)
Definition: c.h:652
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:1171
void UnlockReleaseBuffer(Buffer buffer)
Definition: bufmgr.c:3534
#define ERROR
Definition: elog.h:43
int fillfactor
Definition: pgbench.c:160
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:1552
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:490
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define IndexRelationGetNumberOfKeyAttributes(relation)
Definition: rel.h:475
#define GIST_DEFAULT_FILLFACTOR
Definition: gist_private.h:478
Relation heaprel
Definition: gistbuild.c:85
#define BufferGetPage(buffer)
Definition: bufmgr.h:169
void freeGISTstate(GISTSTATE *giststate)
Definition: gist.c:1626
GistBuildMode buildMode
Definition: gistbuild.c:90
GISTSTATE * giststate
Definition: gistbuild.c:86
#define RelationGetNumberOfBlocks(reln)
Definition: bufmgr.h:211
GISTSTATE * initGISTstate(Relation index)
Definition: gist.c:1498
int maintenance_work_mem
Definition: globals.c:123
static void gistEmptyAllBuffers(GISTBuildState *buildstate)
Definition: gistbuild.c:1342
#define Assert(condition)
Definition: c.h:746
Relation indexrel
Definition: gistbuild.c:84
#define INDEX_MAX_KEYS
#define RelationNeedsWAL(relation)
Definition: rel.h:562
void log_newpage_range(Relation rel, ForkNumber forkNum, BlockNumber startblk, BlockNumber endblk, bool page_std)
Definition: xloginsert.c:1123
BlockNumber BufferGetBlockNumber(Buffer buffer)
Definition: bufmgr.c:2661
void gistFreeBuildBuffers(GISTBuildBuffers *gfbb)
void * palloc(Size size)
Definition: mcxt.c:950
#define F_LEAF
Definition: gist.h:46
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
#define elog(elevel,...)
Definition: elog.h:214
int i
#define GIST_ROOT_BLKNO
Definition: gist_private.h:262
void GISTInitBuffer(Buffer b, uint32 f)
Definition: gistutil.c:775
void tuplesort_end(Tuplesortstate *state)
Definition: tuplesort.c:1445
#define PageSetLSN(page, lsn)
Definition: bufpage.h:368
int Buffer
Definition: buf.h:23
Buffer gistNewBuffer(Relation r)
Definition: gistutil.c:826
bytea * rd_options
Definition: rel.h:157
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:767

◆ gistBuildCallback()

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

Definition at line 802 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, RelationData::rd_smgr, smgrnblocks(), IndexTupleData::t_tid, and GISTSTATE::tempCxt.

Referenced by gistbuild().

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

1343 {
1344  GISTBuildBuffers *gfbb = buildstate->gfbb;
1345  MemoryContext oldCtx;
1346  int i;
1347 
1348  oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
1349 
1350  /*
1351  * Iterate through the levels from top to bottom.
1352  */
1353  for (i = gfbb->buffersOnLevelsLen - 1; i >= 0; i--)
1354  {
1355  /*
1356  * Empty all buffers on this level. Note that new buffers can pop up
1357  * in the list during the processing, as a result of page splits, so a
1358  * simple walk through the list won't work. We remove buffers from the
1359  * list when we see them empty; a buffer can't become non-empty once
1360  * it's been fully emptied.
1361  */
1362  while (gfbb->buffersOnLevels[i] != NIL)
1363  {
1364  GISTNodeBuffer *nodeBuffer;
1365 
1366  nodeBuffer = (GISTNodeBuffer *) linitial(gfbb->buffersOnLevels[i]);
1367 
1368  if (nodeBuffer->blocksCount != 0)
1369  {
1370  /*
1371  * Add this buffer to the emptying queue, and proceed to empty
1372  * the queue.
1373  */
1374  if (!nodeBuffer->queuedForEmptying)
1375  {
1377  nodeBuffer->queuedForEmptying = true;
1378  gfbb->bufferEmptyingQueue =
1379  lcons(nodeBuffer, gfbb->bufferEmptyingQueue);
1380  MemoryContextSwitchTo(buildstate->giststate->tempCxt);
1381  }
1382  gistProcessEmptyingQueue(buildstate);
1383  }
1384  else
1385  gfbb->buffersOnLevels[i] =
1387  }
1388  elog(DEBUG2, "emptied all buffers at level %d", i);
1389  }
1390  MemoryContextSwitchTo(oldCtx);
1391 }
#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:1269
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:453
GISTBuildBuffers * gfbb
Definition: gistbuild.c:100
#define elog(elevel,...)
Definition: elog.h:214
int i
List * list_delete_first(List *list)
Definition: list.c:860

◆ gistGetMaxLevel()

static int gistGetMaxLevel ( Relation  index)
static

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

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

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

Referenced by gistBufferingFindCorrectParent().

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

◆ gistInitBuffering()

static void gistInitBuffering ( GISTBuildState buildstate)
static

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

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

◆ gistInitParentMap()

static void gistInitParentMap ( GISTBuildState buildstate)
static

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

1487 {
1488  HASHCTL hashCtl;
1489 
1490  hashCtl.keysize = sizeof(BlockNumber);
1491  hashCtl.entrysize = sizeof(ParentMapEntry);
1492  hashCtl.hcxt = CurrentMemoryContext;
1493  buildstate->parentMap = hash_create("gistbuild parent map",
1494  1024,
1495  &hashCtl,
1497 }
#define HASH_CONTEXT
Definition: hsearch.h:91
#define HASH_ELEM
Definition: hsearch.h:85
MemoryContext hcxt
Definition: hsearch.h:77
Size entrysize
Definition: hsearch.h:72
uint32 BlockNumber
Definition: block.h:31
HTAB * parentMap
Definition: gistbuild.c:101
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define HASH_BLOBS
Definition: hsearch.h:86
HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
Definition: dynahash.c:326
Size keysize
Definition: hsearch.h:71

◆ gistMemorizeAllDownlinks()

static void gistMemorizeAllDownlinks ( GISTBuildState buildstate,
Buffer  parent 
)
static

Definition at line 1516 of file gistbuild.c.

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

Referenced by gistbufferinginserttuples().

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

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

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

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

◆ gistProcessEmptyingQueue()

static void gistProcessEmptyingQueue ( GISTBuildState buildstate)
static

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

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

◆ gistProcessItup()

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

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

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

◆ 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:137
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:367
GISTSTATE * giststate
Definition: gistbuild.c:86
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, Datum *values, bool *isnull)
Definition: tuplesort.c:1708
Definition: regguts.h:298
Relation indexrel
Definition: gistbuild.c:84
#define INDEX_MAX_KEYS
static Datum values[MAXATTR]
Definition: bootstrap.c:165
Tuplesortstate * sortstate
Definition: gistbuild.c:106