diff --git a/contrib/pageinspect/expected/gist.out b/contrib/pageinspect/expected/gist.out index 86c9e9caa9..8cb390feed 100644 --- a/contrib/pageinspect/expected/gist.out +++ b/contrib/pageinspect/expected/gist.out @@ -33,14 +33,15 @@ COMMIT; SELECT * FROM gist_page_items(get_raw_page('test_gist_idx', 0), 'test_gist_idx'); itemoffset | ctid | itemlen | dead | keys ------------+-----------+---------+------+------------------- - 1 | (1,65535) | 40 | f | (p)=((166,166)) - 2 | (2,65535) | 40 | f | (p)=((332,332)) - 3 | (3,65535) | 40 | f | (p)=((498,498)) - 4 | (4,65535) | 40 | f | (p)=((664,664)) - 5 | (5,65535) | 40 | f | (p)=((830,830)) - 6 | (6,65535) | 40 | f | (p)=((996,996)) - 7 | (7,65535) | 40 | f | (p)=((1000,1000)) -(7 rows) + 1 | (1,65535) | 40 | f | (p)=((125,125)) + 2 | (2,65535) | 40 | f | (p)=((250,250)) + 3 | (3,65535) | 40 | f | (p)=((375,375)) + 4 | (4,65535) | 40 | f | (p)=((500,500)) + 5 | (5,65535) | 40 | f | (p)=((625,625)) + 6 | (6,65535) | 40 | f | (p)=((750,750)) + 7 | (7,65535) | 40 | f | (p)=((875,875)) + 8 | (8,65535) | 40 | f | (p)=((1000,1000)) +(8 rows) SELECT * FROM gist_page_items(get_raw_page('test_gist_idx', 1), 'test_gist_idx') LIMIT 5; itemoffset | ctid | itemlen | dead | keys @@ -64,6 +65,7 @@ SELECT itemoffset, ctid, itemlen FROM gist_page_items_bytea(get_raw_page('test_g 5 | (5,65535) | 40 6 | (6,65535) | 40 7 | (7,65535) | 40 -(7 rows) + 8 | (8,65535) | 40 +(8 rows) DROP TABLE test_gist; diff --git a/src/backend/access/gist/gistbuild.c b/src/backend/access/gist/gistbuild.c index 9854116fca..239fd08495 100644 --- a/src/backend/access/gist/gistbuild.c +++ b/src/backend/access/gist/gistbuild.c @@ -59,6 +59,11 @@ */ #define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET 4096 +/** + * Number of pages to collect during sorted build before applying split operation + */ +int GistSortedBuildPageBufferSize = 8; + /* * Strategy used to build the index. It can change between the * GIST_BUFFERING_* modes on the fly, but if the Sorted method is used, @@ -115,14 +120,34 @@ typedef struct /* * In sorted build, we use a stack of these structs, one for each level, - * to hold an in-memory buffer of the rightmost page at the level. When the - * page fills up, it is written out and a new page is allocated. + * to hold an in-memory buffer of last pages at the level. + * + * Sorting GiST build requires good linearization of the sort opclass. This is + * not always the case in multidimensional data. To fight the anomalies, we + * buffer index tuples and apply picksplit that can be multidimension-aware. */ -typedef struct GistSortedBuildPageState +typedef struct GistSortedBuildLevelState { - Page page; - struct GistSortedBuildPageState *parent; /* Upper level, if any */ -} GistSortedBuildPageState; + int current_page; + BlockNumber last_blkno; + struct GistSortedBuildLevelState *parent; /* Upper level, if any */ + uint16 item_num_total; + Size page_max_num; + Page pages[FLEXIBLE_ARRAY_MEMBER]; +} GistSortedBuildLevelState; + +/* + * Max. number of items to apply gistSplit to is limited by OffsetNumber type + * used in GIST_SPLITVEC. + */ +#define GistSortedBuildLevelStateIsMaxItemNum(levelstate) \ + (levelstate->item_num_total + 1 == PG_UINT16_MAX) + +#define GistSortedBuildLevelStateRequiredSize(page_max_num) \ +( \ + AssertMacro(page_max_num > 0), \ + (offsetof(GistSortedBuildLevelState, pages) + page_max_num * sizeof(Page)) \ +) /* prototypes for private functions */ @@ -130,11 +155,11 @@ 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, +static void gist_indexsortbuild_levelstate_add(GISTBuildState *state, + GistSortedBuildLevelState *levelstate, IndexTuple itup); -static void gist_indexsortbuild_pagestate_flush(GISTBuildState *state, - GistSortedBuildPageState *pagestate); +static void gist_indexsortbuild_levelstate_flush(GISTBuildState *state, + GistSortedBuildLevelState *levelstate); static void gist_indexsortbuild_flush_ready_pages(GISTBuildState *state); static void gistInitBuffering(GISTBuildState *buildstate); @@ -396,9 +421,14 @@ static void gist_indexsortbuild(GISTBuildState *state) { IndexTuple itup; - GistSortedBuildPageState *leafstate; - GistSortedBuildPageState *pagestate; + GistSortedBuildLevelState *levelstate; Page page; + Size page_max_num; + + /* Number of pages to collect before splitting */ + page_max_num = GistSortedBuildPageBufferSize; + if (page_max_num > 1) + state->freespace = 0; /* collected tuples will all be split between new pages */ state->pages_allocated = 0; state->pages_written = 0; @@ -414,10 +444,12 @@ gist_indexsortbuild(GISTBuildState *state) state->pages_allocated++; state->pages_written++; - /* Allocate a temporary buffer for the first leaf page. */ - leafstate = palloc(sizeof(GistSortedBuildPageState)); - leafstate->page = page; - leafstate->parent = NULL; + /* Allocate a temporary buffer for the first leaf page batch. */ + levelstate = palloc0(GistSortedBuildLevelStateRequiredSize(page_max_num)); + levelstate->item_num_total = 0; + levelstate->page_max_num = page_max_num; + levelstate->pages[0] = page; + levelstate->parent = NULL; gistinitpage(page, F_LEAF); /* @@ -425,7 +457,7 @@ gist_indexsortbuild(GISTBuildState *state) */ while ((itup = tuplesort_getindextuple(state->sortstate, true)) != NULL) { - gist_indexsortbuild_pagestate_add(state, leafstate, itup); + gist_indexsortbuild_levelstate_add(state, levelstate, itup); MemoryContextReset(state->giststate->tempCxt); } @@ -433,32 +465,34 @@ gist_indexsortbuild(GISTBuildState *state) * Write out the partially full non-root pages. * * Keep in mind that flush can build a new root. + * If number of pages is > 1 then new root is required. */ - pagestate = leafstate; - while (pagestate->parent != NULL) + while (levelstate->parent != NULL || levelstate->current_page != 0) { - GistSortedBuildPageState *parent; - - gist_indexsortbuild_pagestate_flush(state, pagestate); - parent = pagestate->parent; - pfree(pagestate->page); - pfree(pagestate); - pagestate = parent; + GistSortedBuildLevelState *parent; + + gist_indexsortbuild_levelstate_flush(state, levelstate); + parent = levelstate->parent; + for (Size i = 0; i < levelstate->page_max_num; i++) + if (levelstate->pages[i]) + pfree(levelstate->pages[i]); + pfree(levelstate); + levelstate = parent; } gist_indexsortbuild_flush_ready_pages(state); /* Write out the root */ - PageSetLSN(pagestate->page, GistBuildLSN); - PageSetChecksumInplace(pagestate->page, GIST_ROOT_BLKNO); + PageSetLSN(levelstate->pages[0], GistBuildLSN); + PageSetChecksumInplace(levelstate->pages[0], GIST_ROOT_BLKNO); smgrwrite(RelationGetSmgr(state->indexrel), MAIN_FORKNUM, GIST_ROOT_BLKNO, - pagestate->page, true); + levelstate->pages[0], true); if (RelationNeedsWAL(state->indexrel)) log_newpage(&state->indexrel->rd_node, MAIN_FORKNUM, GIST_ROOT_BLKNO, - pagestate->page, true); + levelstate->pages[0], true); - pfree(pagestate->page); - pfree(pagestate); + pfree(levelstate->pages[0]); + pfree(levelstate); } /* @@ -466,92 +500,159 @@ gist_indexsortbuild(GISTBuildState *state) * a new page first. */ static void -gist_indexsortbuild_pagestate_add(GISTBuildState *state, - GistSortedBuildPageState *pagestate, +gist_indexsortbuild_levelstate_add(GISTBuildState *state, + GistSortedBuildLevelState *levelstate, IndexTuple itup) { Size sizeNeeded; - /* Does the tuple fit? If not, flush */ + /* Does the tuple fit? + * Tuple fits if total number of tuples is less than GistSortedBuildLevelStateMaxItemNum + * and tuple fits into current page or new page can be added. + * If not, flush */ sizeNeeded = IndexTupleSize(itup) + sizeof(ItemIdData) + state->freespace; - if (PageGetFreeSpace(pagestate->page) < sizeNeeded) - gist_indexsortbuild_pagestate_flush(state, pagestate); + if (GistSortedBuildLevelStateIsMaxItemNum(levelstate) + || PageGetFreeSpace(levelstate->pages[levelstate->current_page]) < sizeNeeded) + { + Page newPage; + Page old_page = levelstate->pages[levelstate->current_page]; + uint16 old_page_flags = GistPageGetOpaque(old_page)->flags; + if (GistSortedBuildLevelStateIsMaxItemNum(levelstate) + || levelstate->current_page + 1 == levelstate->page_max_num) + { + gist_indexsortbuild_levelstate_flush(state, levelstate); + } + else + levelstate->current_page++; - gistfillbuffer(pagestate->page, &itup, 1, InvalidOffsetNumber); + if (levelstate->pages[levelstate->current_page] == NULL) + levelstate->pages[levelstate->current_page] = palloc(BLCKSZ); + + newPage = levelstate->pages[levelstate->current_page]; + gistinitpage(newPage, old_page_flags); + } + + Assert(!GistSortedBuildLevelStateIsMaxItemNum(levelstate)); + levelstate->item_num_total++; + gistfillbuffer(levelstate->pages[levelstate->current_page], &itup, 1, InvalidOffsetNumber); } static void -gist_indexsortbuild_pagestate_flush(GISTBuildState *state, - GistSortedBuildPageState *pagestate) +gist_indexsortbuild_levelstate_flush(GISTBuildState *state, + GistSortedBuildLevelState *levelstate) { - GistSortedBuildPageState *parent; - IndexTuple *itvec; - IndexTuple union_tuple; - int vect_len; - bool isleaf; - BlockNumber blkno; + GistSortedBuildLevelState *parent; + BlockNumber blkno; MemoryContext oldCtx; + IndexTuple union_tuple; + SplitedPageLayout *dist; + IndexTuple *itvec; + int vect_len; + bool isleaf = GistPageIsLeaf(levelstate->pages[0]); - /* check once per page */ + /* check once per whatever */ CHECK_FOR_INTERRUPTS(); - if (state->ready_num_pages == XLR_MAX_BLOCK_ID) - gist_indexsortbuild_flush_ready_pages(state); - - /* - * The page is now complete. Assign a block number to it, and add it to - * the list of finished pages. (We don't write it out immediately, because - * we want to WAL-log the pages in batches.) - */ - blkno = state->pages_allocated++; - state->ready_blknos[state->ready_num_pages] = blkno; - state->ready_pages[state->ready_num_pages] = pagestate->page; - state->ready_num_pages++; + oldCtx = MemoryContextSwitchTo(state->giststate->tempCxt); - isleaf = GistPageIsLeaf(pagestate->page); + /* Get index tuples from first page */ + itvec = gistextractpage(levelstate->pages[0], &vect_len); + if (levelstate->current_page > 0) + { + /* Append tuples from each page */ + for (int i = 1; i < levelstate->current_page + 1; i++) + { + int len_local; + IndexTuple *itvec_local = gistextractpage(levelstate->pages[i], &len_local); + itvec = gistjoinvector(itvec, &vect_len, itvec_local, len_local); + pfree(itvec_local); + } - /* - * Form a downlink tuple to represent all the tuples on the page. - */ - oldCtx = MemoryContextSwitchTo(state->giststate->tempCxt); - itvec = gistextractpage(pagestate->page, &vect_len); - union_tuple = gistunion(state->indexrel, itvec, vect_len, + /* Apply picksplit to list of all collected tuples */ + dist = gistSplit(state->indexrel, levelstate->pages[0], itvec, vect_len, state->giststate); + } + else + { + /* Create splitted layout from single page */ + dist = (SplitedPageLayout*) palloc0(sizeof(SplitedPageLayout)); + union_tuple = gistunion(state->indexrel, itvec, vect_len, state->giststate); - ItemPointerSetBlockNumber(&(union_tuple->t_tid), blkno); + dist->itup = union_tuple; + dist->list = gistfillitupvec(itvec, vect_len, &(dist->lenlist)); + dist->block.num = vect_len; + } + MemoryContextSwitchTo(oldCtx); - /* - * Insert the downlink to the parent page. If this was the root, create a - * new page as the parent, which becomes the new root. - */ - parent = pagestate->parent; - if (parent == NULL) + /* Reset page and item counters */ + levelstate->current_page = 0; + levelstate->item_num_total = 0; + + /* Create pages for all partitions in split result */ + for (;dist != NULL; dist = dist->next) { - parent = palloc(sizeof(GistSortedBuildPageState)); - parent->page = (Page) palloc(BLCKSZ); - parent->parent = NULL; - gistinitpage(parent->page, 0); + /* Create page and copy data */ + char *data = (char *) (dist->list); + Page target = palloc0(BLCKSZ); + gistinitpage(target, isleaf? F_LEAF:0); + for (int i = 0; i < dist->block.num; i++) + { + IndexTuple thistup = (IndexTuple) data; - pagestate->parent = parent; - } - gist_indexsortbuild_pagestate_add(state, parent, union_tuple); + if (PageAddItem(target, (Item) data, IndexTupleSize(thistup), i + FirstOffsetNumber, false, false) == InvalidOffsetNumber) + elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(state->indexrel)); - /* Re-initialize the page buffer for next page on this level. */ - pagestate->page = palloc(BLCKSZ); - gistinitpage(pagestate->page, isleaf ? F_LEAF : 0); + data += IndexTupleSize(thistup); + } + union_tuple = dist->itup; - /* - * Set the right link to point to the previous page. This is just for - * debugging purposes: GiST only follows the right link if a page is split - * concurrently to a scan, and that cannot happen during index build. - * - * It's a bit counterintuitive that we set the right link on the new page - * to point to the previous page, and not the other way round. But GiST - * pages are not ordered like B-tree pages are, so as long as the - * right-links form a chain through all the pages in the same level, the - * order doesn't matter. - */ - GistPageGetOpaque(pagestate->page)->rightlink = blkno; + if (state->ready_num_pages == XLR_MAX_BLOCK_ID) + gist_indexsortbuild_flush_ready_pages(state); + + /* + * The page is now complete. Assign a block number to it, and add it to + * the list of finished pages. (We don't write it out immediately, because + * we want to WAL-log the pages in batches.) + */ + blkno = state->pages_allocated++; + state->ready_blknos[state->ready_num_pages] = blkno; + state->ready_pages[state->ready_num_pages] = target; + state->ready_num_pages++; + ItemPointerSetBlockNumber(&(union_tuple->t_tid), blkno); + + /* + * Set the right link to point to the previous page. This is just for + * debugging purposes: GiST only follows the right link if a page is split + * concurrently to a scan, and that cannot happen during index build. + * + * It's a bit counterintuitive that we set the right link on the new page + * to point to the previous page, and not the other way round. But GiST + * pages are not ordered like B-tree pages are, so as long as the + * right-links form a chain through all the pages in the same level, the + * order doesn't matter. + */ + if (levelstate->last_blkno) + GistPageGetOpaque(target)->rightlink = levelstate->last_blkno; + levelstate->last_blkno = blkno; + + /* + * Insert the downlink to the parent page. If this was the root, create a + * new page as the parent, which becomes the new root. + */ + parent = levelstate->parent; + if (parent == NULL) + { + parent = palloc0(GistSortedBuildLevelStateRequiredSize(levelstate->page_max_num)); + parent->item_num_total = 0; + parent->page_max_num = levelstate->page_max_num; + parent->pages[0] = (Page) palloc(BLCKSZ); + parent->parent = NULL; + gistinitpage(parent->pages[0], 0); + + levelstate->parent = parent; + } + gist_indexsortbuild_levelstate_add(state, parent, union_tuple); + } } static void diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c index 4c94f09c64..4755113737 100644 --- a/src/backend/utils/misc/guc.c +++ b/src/backend/utils/misc/guc.c @@ -34,6 +34,7 @@ #include "access/commit_ts.h" #include "access/gin.h" +#include "access/gist.h" #include "access/rmgr.h" #include "access/tableam.h" #include "access/toast_compression.h" @@ -3600,6 +3601,17 @@ static struct config_int ConfigureNamesInt[] = NULL, NULL, NULL }, + { + {"gist_sorted_build_page_buffer_size", PGC_USERSET, UNGROUPED, + gettext_noop("GiST sorted build: # of pages to collect before applying split"), + NULL, + 0 + }, + &GistSortedBuildPageBufferSize, + 8, 1, INT_MAX, + NULL, NULL, NULL + }, + /* End-of-list marker */ { {NULL, 0, 0, NULL, NULL}, NULL, 0, 0, 0, NULL, NULL, NULL diff --git a/src/include/access/gist.h b/src/include/access/gist.h index a3337627b8..eb66b9e548 100644 --- a/src/include/access/gist.h +++ b/src/include/access/gist.h @@ -186,6 +186,7 @@ typedef struct GISTENTRY #define GistPageGetNSN(page) ( PageXLogRecPtrGet(GistPageGetOpaque(page)->nsn)) #define GistPageSetNSN(page, val) ( PageXLogRecPtrSet(GistPageGetOpaque(page)->nsn, val)) +extern int GistSortedBuildPageBufferSize; /* * On a deleted page, we store this struct. A deleted page doesn't contain any diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index 89249ecc97..bfb7802f2d 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -969,7 +969,7 @@ GistHstoreOptions GistInetKey GistNSN GistOptBufferingMode -GistSortedBuildPageState +GistSortedBuildLevelState GistSplitUnion GistSplitVector GistTsVectorOptions