1/*-------------------------------------------------------------------------
4 * build algorithm for GiST indexes implementation.
6 * There are two different strategies:
8 * 1. Sort all input tuples, pack them into GiST leaf pages in the sorted
9 * order, and create downlinks and internal pages as we go. This builds
10 * the index from the bottom up, similar to how B-tree index build
13 * 2. Start with an empty index, and insert all tuples one by one.
15 * The sorted method is used if the operator classes for all columns have
16 * a 'sortsupport' defined. Otherwise, we resort to the second strategy.
18 * The second strategy can optionally use buffers at different levels of
19 * the tree to reduce I/O, see "Buffering build algorithm" in the README
20 * for a more detailed explanation. It initially calls insert over and
21 * over, but switches to the buffered algorithm after a certain number of
22 * tuples (unless buffering mode is disabled).
25 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
26 * Portions Copyright (c) 1994, Regents of the University of California
29 * src/backend/access/gist/gistbuild.c
31 *-------------------------------------------------------------------------
51/* Step of index tuples for check whether to switch to buffering build mode */
52 #define BUFFERING_MODE_SWITCH_CHECK_STEP 256
55 * Number of tuples to process in the slow way before switching to buffering
56 * mode, when buffering is explicitly turned on. Also, the number of tuples
57 * to process between readjusting the buffer size parameter, while in
60 #define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET 4096
63 * Strategy used to build the index. It can change between the
64 * GIST_BUFFERING_* modes on the fly, but if the Sorted method is used,
65 * that needs to be decided up-front and cannot be changed afterwards.
73 * buffering build mode if the index grows too
76 * before switching to the buffering build
81/* Working state for gistbuild and its callback */
95 * Extra data structures used during a buffering build. 'gfbb' contains
96 * information related to managing the build buffers. 'parentMap' is a
97 * lookup table of the parent of each internal page.
104 * Extra data structures used during a sorting build.
113 #define GIST_SORTED_BUILD_PAGE_NUM 4
116 * In sorted build, we use a stack of these structs, one for each level,
117 * to hold an in-memory buffer of last pages at the level.
119 * Sorting GiST build requires good linearization of the sort opclass. This is
120 * not always the case in multidimensional data. To tackle the anomalies, we
121 * buffer index tuples and apply picksplit that can be multidimension-aware.
131/* prototypes for private functions */
135 bool tupleIsAlive,
void *
state);
176 * Main entry point to GiST index build.
190 * We expect to be called exactly once for any index relation. If that's
191 * not the case, big trouble's what we have.
194 elog(
ERROR,
"index \"%s\" already contains data",
203 * Create a temporary memory context that is reset once for each tuple
204 * processed. (Note: we don't bother to make this a child of the
205 * giststate's scanCxt, so we have to delete it separately at the end.)
210 * Choose build strategy. First check whether the user specified to use
211 * buffering mode. (The use-case for that in the field is somewhat
212 * questionable perhaps, but it's important for testing purposes.)
220 else /* must be "auto" */
229 * Unless buffering mode was forced, see if we can use sorting instead.
233 bool hasallsortsupports =
true;
236 for (
int i = 0;
i < keyscount;
i++)
242 hasallsortsupports =
false;
246 if (hasallsortsupports)
251 * Calculate target amount of free space to leave on pages.
257 * Build the index using the chosen strategy.
265 * Sort all data, build the index from bottom up.
273 /* Scan the table, adding all tuples to the tuplesort */
279 * Perform the sort and build index pages.
290 * Initialize an empty index and insert all tuples, possibly using
291 * buffers on intermediate levels.
296 /* initialize the root page */
312 /* Scan the table, inserting all the tuples to the index. */
318 * If buffering was used, flush out all the tuples that are still in
323 elog(
DEBUG1,
"all tuples processed, emptying buffers");
329 * We didn't write WAL records as we built the index, so if
330 * WAL-logging is required, write all pages to the WAL now.
340 /* okay, all heap tuples are indexed */
357/*-------------------------------------------------------------------------
358 * Routines for sorted build
359 *-------------------------------------------------------------------------
363 * Per-tuple callback for table_index_build_scan.
379 /* Form an index tuple and point it at the heap tuple */
382 true, compressed_values);
387 compressed_values, isnull);
392 /* Update tuple count. */
397 * Build GiST index from bottom up from pre-sorted tuples.
406 /* Reserve block 0 for the root page */
407 state->pages_allocated = 1;
411 /* Allocate a temporary buffer for the first leaf page batch. */
414 levelstate->
parent = NULL;
418 * Fill index pages with tuples in the sorted order.
427 * Write out the partially full non-root pages.
429 * Keep in mind that flush can build a new root. If number of pages is > 1
430 * then new root is required.
445 /* Write out the root */
448 memcpy(rootbuf, levelstate->
pages[0], BLCKSZ);
457 * Add tuple to a page. If the pages are full, write them out and re-initialize
467 /* Check if tuple can be added to the current page */
509 /* Get index tuples from first page */
513 /* Append tuples from each page */
523 /* Apply picksplit to list of all collected tuples */
528 /* Create split layout from single page */
532 dist->
itup = union_tuple;
539 /* Reset page counter */
542 /* Create pages for all partitions in split result */
543 for (; dist != NULL; dist = dist->
next)
549 /* check once per page */
552 /* Create page and copy data */
566 union_tuple = dist->
itup;
569 * Set the right link to point to the previous page. This is just for
570 * debugging purposes: GiST only follows the right link if a page is
571 * split concurrently to a scan, and that cannot happen during index
574 * It's a bit counterintuitive that we set the right link on the new
575 * page to point to the previous page, not the other way around. But
576 * GiST pages are not ordered like B-tree pages are, so as long as the
577 * right-links form a chain through all the pages at the same level,
578 * the order doesn't matter.
584 * The page is now complete. Assign a block number to it, and pass it
585 * to the bulk writer.
587 blkno =
state->pages_allocated++;
594 * Insert the downlink to the parent page. If this was the root,
595 * create a new page as the parent, which becomes the new root.
612/*-------------------------------------------------------------------------
613 * Routines for non-sorted build
614 *-------------------------------------------------------------------------
618 * Attempt to switch to buffering mode.
620 * If there is not enough memory for buffering build, sets bufferingMode
621 * to GIST_BUFFERING_DISABLED, so that we don't bother to try the switch
622 * anymore. Otherwise initializes the build buffers, and sets bufferingMode to
623 * GIST_BUFFERING_ACTIVE.
633 double avgIndexTuplesPerPage,
634 maxIndexTuplesPerPage;
638 /* Calc space of index page which is available for index tuples */
644 * Calculate average size of already inserted index tuples using gathered
651 * Calculate minimal possible size of index tuple by index metadata.
652 * Minimal possible size of varlena is VARHDRSZ.
654 * XXX: that's not actually true, as a short varlen can be just 2 bytes.
655 * And we should take padding into account here.
658 for (
i = 0;
i <
index->rd_att->natts;
i++)
665 itupMinSize += attr->
attlen;
668 /* Calculate average and maximal number of index tuples which fit to page */
669 avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
670 maxIndexTuplesPerPage = pageFreeSpace / itupMinSize;
673 * We need to calculate two parameters for the buffering algorithm:
674 * levelStep and pagesPerBuffer.
676 * levelStep determines the size of subtree that we operate on, while
677 * emptying a buffer. A higher value is better, as you need fewer buffer
678 * emptying steps to build the index. However, if you set it too high, the
679 * subtree doesn't fit in cache anymore, and you quickly lose the benefit
682 * In Arge et al's paper, levelStep is chosen as logB(M/4B), where B is
683 * the number of tuples on page (ie. fanout), and M is the amount of
684 * internal memory available. Curiously, they doesn't explain *why* that
685 * setting is optimal. We calculate it by taking the highest levelStep so
686 * that a subtree still fits in cache. For a small B, our way of
687 * calculating levelStep is very close to Arge et al's formula. For a
688 * large B, our formula gives a value that is 2x higher.
690 * The average size (in pages) of a subtree of depth n can be calculated
691 * as a geometric series:
693 * B^0 + B^1 + B^2 + ... + B^n = (1 - B^(n + 1)) / (1 - B)
695 * where B is the average number of index tuples on page. The subtree is
696 * cached in the shared buffer cache and the OS cache, so we choose
697 * levelStep so that the subtree size is comfortably smaller than
698 * effective_cache_size, with a safety factor of 4.
700 * The estimate on the average number of index tuples on page is based on
701 * average tuple sizes observed before switching to buffered build, so the
702 * real subtree size can be somewhat larger. Also, it would selfish to
703 * gobble the whole cache for our index build. The safety factor of 4
704 * should account for those effects.
706 * The other limiting factor for setting levelStep is that while
707 * processing a subtree, we need to hold one page for each buffer at the
708 * next lower buffered level. The max. number of buffers needed for that
709 * is maxIndexTuplesPerPage^levelStep. This is very conservative, but
710 * hopefully maintenance_work_mem is set high enough that you're
711 * constrained by effective_cache_size rather than maintenance_work_mem.
713 * XXX: the buffer hash table consumes a fair amount of memory too per
714 * buffer, but that is not currently taken into account. That scales on
715 * the total number of buffers used, ie. the index size and on levelStep.
716 * Note that a higher levelStep *reduces* the amount of memory needed for
723 double maxlowestlevelpages;
725 /* size of an average subtree at this levelStep (in pages). */
727 (1 - pow(avgIndexTuplesPerPage, (
double) (levelStep + 1))) /
728 (1 - avgIndexTuplesPerPage);
730 /* max number of pages at the lowest level of a subtree */
731 maxlowestlevelpages = pow(maxIndexTuplesPerPage, (
double) levelStep);
733 /* subtree must fit in cache (with safety factor of 4) */
737 /* each node in the lowest level of a subtree has one page in memory */
741 /* Good, we can handle this levelStep. See if we can go one higher. */
746 * We just reached an unacceptable value of levelStep in previous loop.
747 * So, decrease levelStep to get last acceptable value.
752 * If there's not enough cache or maintenance_work_mem, fall back to plain
757 elog(
DEBUG1,
"failed to switch to buffered GiST build");
763 * The second parameter to set is pagesPerBuffer, which determines the
764 * size of each buffer. We adjust pagesPerBuffer also during the build,
765 * which is why this calculation is in a separate function.
769 /* Initialize GISTBuildBuffers with these parameters */
777 elog(
DEBUG1,
"switched to buffered GiST build; level step = %d, pagesPerBuffer = %d",
778 levelStep, pagesPerBuffer);
782 * Calculate pagesPerBuffer parameter for the buffering algorithm.
784 * Buffer size is chosen so that assuming that tuples are distributed
785 * randomly, emptying half a buffer fills on average one page in every buffer
786 * at the next lower level.
791 double pagesPerBuffer;
792 double avgIndexTuplesPerPage;
796 /* Calc space of index page which is available for index tuples */
802 * Calculate average size of already inserted index tuples using gathered
808 avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;
811 * Recalculate required size of buffers.
813 pagesPerBuffer = 2 * pow(avgIndexTuplesPerPage, levelStep);
815 return (
int) rint(pagesPerBuffer);
819 * Per-tuple callback for table_index_build_scan.
835 /* form an index tuple and point it at the heap tuple */
841 /* Update tuple count and total size. */
846 * XXX In buffering builds, the tempCxt is also reset down inside
847 * gistProcessEmptyingQueue(). This is not great because it risks
848 * confusion and possible use of dangling pointers (for example, itup
849 * might be already freed when control returns here). It's generally
850 * better that a memory context be "owned" by only one function. However,
851 * currently this isn't causing issues so it doesn't seem worth the amount
852 * of refactoring that would be needed to avoid it.
856 /* We have buffers, so use them. */
862 * There's no buffers (yet). Since we already have the index relation
863 * locked, we call gistdoinsert directly.
875 /* Adjust the target buffer size now */
881 * In 'auto' mode, check if the index has grown too large to fit in cache,
882 * and switch to buffering mode if it has.
884 * To avoid excessive calls to smgrnblocks(), only check this every
885 * BUFFERING_MODE_SWITCH_CHECK_STEP index tuples.
887 * In 'stats' state, switch as soon as we have seen enough tuples to have
888 * some idea of the average tuple size.
898 * Index doesn't fit in effective cache anymore. Try to switch to
899 * buffering build mode.
906 * Insert function for buffering index build.
911 /* Insert the tuple to buffers. */
914 /* If we filled up (half of a) buffer, process buffer emptying. */
919 * Process an index tuple. Runs the tuple down the tree until we reach a leaf
920 * page or node buffer, and inserts the tuple there. Returns true if we have
921 * to stop buffer emptying process (because one of child buffers can't take
922 * index tuples anymore).
942 * Loop until we reach a leaf page (level == 0) or a level with buffers
943 * (not including the level we start at, because we would otherwise make
956 /* Have we reached a level with buffers? */
960 /* Have we reached a leaf page? */
965 * Nope. Descend down to the next level then. Choose a child to
973 childoffnum =
gistchoose(indexrel, page, itup, giststate);
982 * Check that the key representing the target child node is consistent
983 * with the key we're inserting. Update it if it's not.
996 /* gistbufferinginserttuples() released the buffer */
1001 /* Descend to the child */
1002 parentblkno = blkno;
1004 downlinkoffnum = childoffnum;
1012 * We've reached level with buffers. Place the index tuple to the
1013 * buffer, and add the buffer to the emptying queue if it overflows.
1017 /* Find the buffer or create a new one */
1020 /* Add index tuple to it */
1029 * We've reached a leaf page. Place the tuple here.
1036 parentblkno, downlinkoffnum);
1037 /* gistbufferinginserttuples() released the buffer */
1044 * Insert tuples to a given page.
1046 * This is analogous with gistinserttuples() in the regular insertion code.
1048 * Returns the block number of the page where the (first) new or updated tuple
1049 * was inserted. Usually that's the original page, but might be a sibling page
1050 * if the original page was split.
1052 * Caller should hold a lock on 'buffer' on entry. This function will unlock
1069 itup, ntup, oldoffnum, &placed_to_blk,
1076 * If this is a root split, update the root path item kept in memory. This
1077 * ensures that all path stacks are always complete, including all parent
1078 * nodes up to the root. That simplifies the algorithm to re-find correct
1093 * All the downlinks on the old root page are now on one of the child
1094 * pages. Visit all the new child pages to memorize the parents of the
1112 * Also remember that the parent of the new child page is the
1123 * Insert the downlinks to the parent. This is analogous with
1124 * gistfinishsplit() in the regular insertion code, but the locking is
1125 * simpler, and we have to maintain the buffers on internal nodes and
1134 /* Parent may have changed since we memorized this path. */
1143 * If there's a buffer associated with this page, that needs to be
1144 * split too. gistRelocateBuildBuffersOnSplit() will also adjust the
1145 * downlinks in 'splitinfo', to make sure they're consistent not only
1146 * with the tuples already on the pages, but also the tuples in the
1147 * buffers that will eventually be inserted to them.
1155 /* Create an array of all the downlink tuples */
1159 foreach(lc, splitinfo)
1164 * Remember the parent of each new child page in our parent map.
1165 * This assumes that the downlinks fit on the parent page. If the
1166 * parent page is split, too, when we recurse up to insert the
1167 * downlinks, the recursive gistbufferinginserttuples() call will
1168 * update the map again.
1176 * Also update the parent map for all the downlinks that got moved
1177 * to a different page. (actually this also loops through the
1178 * downlinks that stayed on the original page, but it does no
1185 * Since there's no concurrent access, we can release the lower
1186 * level buffers immediately. This includes the original page.
1192 /* Insert them into parent. */
1194 downlinks, ndownlinks, downlinkoffnum,
1202 return placed_to_blk;
1206 * Find the downlink pointing to a child page.
1208 * 'childblkno' indicates the child page to find the parent for. 'level' is
1209 * the level of the child. On entry, *parentblkno and *downlinkoffnum can
1210 * point to a location where the downlink used to be - we will check that
1211 * location first, and save some cycles if it hasn't moved. The function
1212 * returns a buffer containing the downlink, exclusively-locked, and
1213 * *parentblkno and *downlinkoffnum are set to the real location of the
1216 * If the child page is a leaf (level == 0), the caller must supply a correct
1217 * parentblkno. Otherwise we use the parent map hash table to find the parent
1220 * This function serves the same purpose as gistFindCorrectParent() during
1221 * normal index inserts, but this is simpler because we don't need to deal
1222 * with concurrent inserts.
1241 * For a leaf page, the caller must supply a correct parent block
1245 elog(
ERROR,
"no parent buffer provided of child %u", childblkno);
1255 /* Check if it was not moved */
1270 * Downlink was not at the offset where it used to be. Scan the page to
1271 * find it. During normal gist insertions, it might've moved to another
1272 * page, to the right, but during a buffering build, we keep track of the
1273 * parent of each page in the lookup table so we should always know what
1283 /* yes!!, found it */
1284 *downlinkoffnum = off;
1289 elog(
ERROR,
"failed to re-find parent for block %u", childblkno);
1294 * Process buffers emptying stack. Emptying of one buffer can cause emptying
1295 * of other buffers. This function iterates until this cascading emptying
1296 * process finished, e.g. until buffers emptying stack is empty.
1303 /* Iterate while we have elements in buffers emptying stack. */
1308 /* Get node buffer from emptying stack. */
1314 * We are going to load last pages of buffers where emptying will be
1315 * to. So let's unload any previously loaded buffers.
1320 * Pop tuples from the buffer and run them down to the buffers at
1321 * lower level, or leaf pages. We continue until one of the lower
1322 * level buffers fills up, or this buffer runs empty.
1324 * In Arge et al's paper, the buffer emptying is stopped after
1325 * processing 1/2 node buffer worth of tuples, to avoid overfilling
1326 * any of the lower level buffers. However, it's more efficient to
1327 * keep going until one of the lower level buffers actually fills up,
1328 * so that's what we do. This doesn't need to be exact, if a buffer
1329 * overfills by a few tuples, there's no harm done.
1335 /* Get next index tuple from the buffer */
1340 * Run it down to the underlying node buffer or leaf page.
1342 * Note: it's possible that the buffer we're emptying splits as a
1343 * result of this call. If that happens, our emptyingNodeBuffer
1344 * points to the left half of the split. After split, it's very
1345 * likely that the new left buffer is no longer over the half-full
1346 * threshold, but we might as well keep flushing tuples from it
1347 * until we fill a lower-level buffer.
1352 * A lower level buffer filled up. Stop emptying this buffer,
1353 * to avoid overflowing the lower level buffer.
1358 /* Free all the memory allocated during index tuple processing */
1365 * Empty all node buffers, from top to bottom. This is done at the end of
1366 * index build to flush all remaining tuples to the index.
1368 * Note: This destroys the buffersOnLevels lists, so the buffers should not
1369 * be inserted to after this call.
1381 * Iterate through the levels from top to bottom.
1386 * Empty all buffers on this level. Note that new buffers can pop up
1387 * in the list during the processing, as a result of page splits, so a
1388 * simple walk through the list won't work. We remove buffers from the
1389 * list when we see them empty; a buffer can't become non-empty once
1390 * it's been fully emptied.
1401 * Add this buffer to the emptying queue, and proceed to empty
1418 elog(
DEBUG2,
"emptied all buffers at level %d",
i);
1424 * Get the depth of the GiST index.
1433 * Traverse down the tree, starting from the root, until we hit the leaf
1447 * There's no concurrent access during index build, so locking is just
1455 /* We hit the bottom, so we're done. */
1461 * Pick the first downlink on the page, and follow it. It doesn't
1462 * matter which downlink we choose, the tree has the same depth
1463 * everywhere, so we just pick the first one.
1471 * We're going down on the tree. It means that there is yet one more
1472 * level in the tree.
1481 * Routines for managing the parent map.
1483 * Whenever a page is split, we need to insert the downlinks into the parent.
1484 * We need to somehow find the parent page to do that. In normal insertions,
1485 * we keep a stack of nodes visited when we descend the tree. However, in
1486 * buffering build, we can start descending the tree from any internal node,
1487 * when we empty a buffer by cascading tuples to its children. So we don't
1488 * have a full stack up to the root available at that time.
1490 * So instead, we maintain a hash table to track the parent of every internal
1491 * page. We don't need to track the parents of leaf nodes, however. Whenever
1492 * we insert to a leaf, we've just descended down from its parent, so we know
1493 * its immediate parent already. This helps a lot to limit the memory used
1494 * by this hash table.
1496 * Whenever an internal node is split, the parent map needs to be updated.
1497 * the parent of the new child page needs to be recorded, and also the
1498 * entries for all page whose downlinks are moved to a new page at the split
1499 * needs to be updated.
1501 * We also update the parent map whenever we descend the tree. That might seem
1502 * unnecessary, because we maintain the map whenever a downlink is moved or
1503 * created, but it is needed because we switch to buffering mode after
1504 * creating a tree with regular index inserts. Any pages created before
1505 * switching to buffering mode will not be present in the parent map initially,
1506 * but will be added there the first time we visit them.
1543 * Scan all downlinks on a page, and memorize their parent.
1572 /* Find node buffer in hash table */
1578 elog(
ERROR,
"could not find parent of block %u in lookup table", child);
#define InvalidBlockNumber
static Datum values[MAXATTR]
BlockNumber BufferGetBlockNumber(Buffer buffer)
void UnlockReleaseBuffer(Buffer buffer)
void MarkBufferDirty(Buffer buffer)
void LockBuffer(Buffer buffer, int mode)
Buffer ReadBuffer(Relation reln, BlockNumber blockNum)
#define RelationGetNumberOfBlocks(reln)
static Page BufferGetPage(Buffer buffer)
Size PageGetFreeSpace(const PageData *page)
static Item PageGetItem(const PageData *page, const ItemIdData *itemId)
#define SizeOfPageHeaderData
static ItemId PageGetItemId(Page page, OffsetNumber offsetNumber)
static void PageSetLSN(Page page, XLogRecPtr lsn)
#define PageAddItem(page, item, size, offsetNumber, overwrite, is_heap)
static OffsetNumber PageGetMaxOffsetNumber(const PageData *page)
BulkWriteState * smgr_bulk_start_rel(Relation rel, ForkNumber forknum)
void smgr_bulk_write(BulkWriteState *bulkstate, BlockNumber blocknum, BulkWriteBuffer buf, bool page_std)
BulkWriteBuffer smgr_bulk_get_buf(BulkWriteState *bulkstate)
void smgr_bulk_finish(BulkWriteState *bulkstate)
#define OidIsValid(objectId)
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
HTAB * hash_create(const char *tabname, int64 nelem, const HASHCTL *info, int flags)
SplitPageLayout * gistSplit(Relation r, Page page, IndexTuple *itup, int len, GISTSTATE *giststate)
GISTSTATE * initGISTstate(Relation index)
void gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate, Relation heapRel, bool is_build)
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)
MemoryContext createTempGistContext(void)
void freeGISTstate(GISTSTATE *giststate)
#define GIST_SORTSUPPORT_PROC
struct GISTPageOpaqueData GISTPageOpaqueData
#define GistPageIsLeaf(page)
#define GistPageGetOpaque(page)
#define LEVEL_HAS_BUFFERS(nlevel, gfbb)
@ GIST_OPTION_BUFFERING_OFF
@ GIST_OPTION_BUFFERING_ON
#define GIST_DEFAULT_FILLFACTOR
#define BUFFER_OVERFLOWED(nodeBuffer, gfbb)
@ GIST_BUFFERING_DISABLED
static BlockNumber gistbufferinginserttuples(GISTBuildState *buildstate, Buffer buffer, int level, IndexTuple *itup, int ntup, OffsetNumber oldoffnum, BlockNumber parentblk, OffsetNumber downlinkoffnum)
static void gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parentbuf)
static bool gistProcessItup(GISTBuildState *buildstate, IndexTuple itup, BlockNumber startblkno, int startlevel)
static void gist_indexsortbuild_levelstate_flush(GISTBuildState *state, GistSortedBuildLevelState *levelstate)
#define BUFFERING_MODE_SWITCH_CHECK_STEP
static Buffer gistBufferingFindCorrectParent(GISTBuildState *buildstate, BlockNumber childblkno, int level, BlockNumber *parentblkno, OffsetNumber *downlinkoffnum)
static int calculatePagesPerBuffer(GISTBuildState *buildstate, int levelStep)
static void gist_indexsortbuild_levelstate_add(GISTBuildState *state, GistSortedBuildLevelState *levelstate, IndexTuple itup)
static void gist_indexsortbuild(GISTBuildState *state)
static void gistInitParentMap(GISTBuildState *buildstate)
static void gistBuildCallback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
IndexBuildResult * gistbuild(Relation heap, Relation index, IndexInfo *indexInfo)
static void gistSortedBuildCallback(Relation index, ItemPointer tid, Datum *values, bool *isnull, bool tupleIsAlive, void *state)
static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, BlockNumber parent)
#define GIST_SORTED_BUILD_PAGE_NUM
static void gistEmptyAllBuffers(GISTBuildState *buildstate)
#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET
static void gistInitBuffering(GISTBuildState *buildstate)
static void gistBufferingBuildInsert(GISTBuildState *buildstate, IndexTuple itup)
static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child)
static int gistGetMaxLevel(Relation index)
struct GistSortedBuildLevelState GistSortedBuildLevelState
static void gistProcessEmptyingQueue(GISTBuildState *buildstate)
void gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple itup)
void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb, GISTSTATE *giststate, Relation r, int level, Buffer buffer, List *splitinfo)
GISTBuildBuffers * gistInitBuildBuffers(int pagesPerBuffer, int levelStep, int maxLevel)
void gistFreeBuildBuffers(GISTBuildBuffers *gfbb)
bool gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer, IndexTuple *itup)
GISTNodeBuffer * gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate, BlockNumber nodeBlocknum, int level)
void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb)
Buffer gistNewBuffer(Relation r, Relation heaprel)
void gistfillbuffer(Page page, IndexTuple *itup, int len, OffsetNumber off)
IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, const Datum *attdata, const bool *isnull, bool isleaf)
IndexTuple * gistextractpage(Page page, int *len)
IndexTuple gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate)
void gistCompressValues(GISTSTATE *giststate, Relation r, const Datum *attdata, const bool *isnull, bool isleaf, Datum *compatt)
IndexTuple * gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
void gistinitpage(Page page, uint32 f)
IndexTuple gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
void GISTInitBuffer(Buffer b, uint32 f)
void gistcheckpage(Relation rel, Buffer buf)
IndexTupleData * gistfillitupvec(IndexTuple *vec, int veclen, int *memlen)
Assert(PointerIsAligned(start, uint64))
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
if(TABLE==NULL||TABLE_index==NULL)
struct ItemIdData ItemIdData
static void ItemPointerSetBlockNumber(ItemPointerData *pointer, BlockNumber blockNumber)
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
IndexTupleData * IndexTuple
static Size IndexTupleSize(const IndexTupleData *itup)
List * list_delete_first(List *list)
List * lcons(void *datum, List *list)
void list_free_deep(List *list)
void MemoryContextReset(MemoryContext context)
void pfree(void *pointer)
void * palloc0(Size size)
MemoryContext CurrentMemoryContext
void MemoryContextDelete(MemoryContext context)
#define START_CRIT_SECTION()
#define CHECK_FOR_INTERRUPTS()
#define END_CRIT_SECTION()
#define InvalidOffsetNumber
#define OffsetNumberNext(offsetNumber)
#define FirstOffsetNumber
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
static int list_length(const List *l)
static SMgrRelation RelationGetSmgr(Relation rel)
#define RelationGetRelationName(relation)
#define RelationNeedsWAL(relation)
#define IndexRelationGetNumberOfKeyAttributes(relation)
BlockNumber smgrnblocks(SMgrRelation reln, ForkNumber forknum)
List * bufferEmptyingQueue
BlockNumber pages_allocated
BulkWriteState * bulkstate
Tuplesortstate * sortstate
Page pages[GIST_SORTED_BUILD_PAGE_NUM]
struct GistSortedBuildLevelState * parent
struct SplitPageLayout * next
static double table_index_build_scan(Relation table_rel, Relation index_rel, IndexInfo *index_info, bool allow_sync, bool progress, IndexBuildCallback callback, void *callback_state, TableScanDesc scan)
static CompactAttribute * TupleDescCompactAttr(TupleDesc tupdesc, int i)
void tuplesort_performsort(Tuplesortstate *state)
void tuplesort_end(Tuplesortstate *state)
IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward)
void tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel, ItemPointer self, const Datum *values, const bool *isnull)
Tuplesortstate * tuplesort_begin_index_gist(Relation heapRel, Relation indexRel, int workMem, SortCoordinate coordinate, int sortopt)
void log_newpage_range(Relation rel, ForkNumber forknum, BlockNumber startblk, BlockNumber endblk, bool page_std)