From 66dd8793031a6b960137fb004803ecb3efd82a5e Mon Sep 17 00:00:00 2001 From: Andrey Borodin Date: Tue, 4 Aug 2020 22:17:28 +0500 Subject: [PATCH v14 2/3] Implement GiST build using sort support We use special sorting function provided by opcalss to approximate GiST tree with B-tree-like structure. This approach allows to radically reduce build time in some cases. --- doc/src/sgml/gist.sgml | 52 ++++++ src/backend/access/gist/gistbuild.c | 231 ++++++++++++++++++++++++- src/backend/access/gist/gistutil.c | 32 +++- src/backend/access/gist/gistvalidate.c | 6 +- src/backend/utils/sort/tuplesort.c | 37 ++++ src/include/access/gist.h | 3 +- src/include/access/gist_private.h | 3 + src/include/catalog/pg_amproc.dat | 2 + src/include/utils/tuplesort.h | 6 + 9 files changed, 358 insertions(+), 14 deletions(-) diff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgml index 5d970ee9f2..dde9f6030f 100644 --- a/doc/src/sgml/gist.sgml +++ b/doc/src/sgml/gist.sgml @@ -290,6 +290,8 @@ CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops); compress method is omitted. The optional tenth method options is needed if the operator class provides the user-specified parameters. + The sortsupport method is also optional and is used during + fast GiST build. @@ -1096,6 +1098,56 @@ my_compress(PG_FUNCTION_ARGS) + + + sortsupport + + + Returns a comparator, suitable for fast GiST build. + + + + The SQL declaration of the function must look like this: + + +CREATE OR REPLACE FUNCTION my_sortsupport(internal) +RETURNS void +AS 'MODULE_PATHNAME' +LANGUAGE C STRICT; + + + The argument is a pointer to a SortSupport struct. + + + + The matching code in the C module could then follow this skeleton: + + +PG_FUNCTION_INFO_V1(my_sortsupport); + +static int +my_fastcmp(Datum x, Datum y, SortSupport ssup) +{ + /* establish order between x and y by computing some sorting value z */ + + int z1 = ComputeSpatialCode(x); + int z2 = ComputeSpatialCode(y); + + return z1 == z2 ? 0 : z1 > z2 ? 1 : -1; +} + +Datum +my_sortsupport(PG_FUNCTION_ARGS) +{ + SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0); + + ssup->comparator = my_fastcmp; + PG_RETURN_VOID(); +} + + + + diff --git a/src/backend/access/gist/gistbuild.c b/src/backend/access/gist/gistbuild.c index 671b5e9186..3c9a50a720 100644 --- a/src/backend/access/gist/gistbuild.c +++ b/src/backend/access/gist/gistbuild.c @@ -28,6 +28,8 @@ #include "storage/smgr.h" #include "utils/memutils.h" #include "utils/rel.h" +#include "utils/regproc.h" +#include "utils/tuplesort.h" /* Step of index tuples for check whether to switch to buffering build mode */ #define BUFFERING_MODE_SWITCH_CHECK_STEP 256 @@ -53,6 +55,15 @@ typedef enum GIST_BUFFERING_ACTIVE /* in buffering build mode */ } GistBufferingMode; +/* + * Status record for spooling/sorting phase. + */ +typedef struct +{ + Tuplesortstate *sortstate; /* state data for tuplesort.c */ + Relation index; +} GSpool; + /* Working state for gistbuild and its callback */ typedef struct { @@ -74,6 +85,8 @@ typedef struct HTAB *parentMap; GistBufferingMode bufferingMode; + GSpool *spool; + BlockNumber next_block; } GISTBuildState; /* prototypes for private functions */ @@ -107,6 +120,182 @@ static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child, static void gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parent); static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child); +static GSpool *gist_spoolinit(Relation heap, Relation index, SortSupport ssup); +static void gist_spool(GSpool *gspool, ItemPointer self, Datum *values, bool *isnull); +static void gist_indexsortbuild(GISTBuildState *state); +static void gist_indexsortbuild_flush(Relation rel, Page page, BlockNumber blockno, bool isNew); + +/* + * create and initialize a spool structure to sort tuples + */ +static GSpool * +gist_spoolinit(Relation heap, Relation index, SortSupport ssup) +{ + GSpool *gspool = (GSpool *) palloc0(sizeof(GSpool)); + + gspool->index = index; + + /* + * We size the sort area as maintenance_work_mem rather than work_mem to + * speed index creation. This should be OK since a single backend can't + * run multiple index creations in parallel. + */ + gspool->sortstate = tuplesort_begin_index_gist(heap, + index, + ssup, + maintenance_work_mem, + NULL, + false); + + return gspool; +} + +/* + * Flush page contents to actual page at blockno + * We have expected block number, because GiST build relies on that pages + * will be allocated in continous segments. This simplifies allocation + * logic. + */ +static void +gist_indexsortbuild_flush(Relation rel, Page page, BlockNumber blockno, bool isNew) +{ + Page newpage; + + Buffer buffer = ReadBuffer(rel, isNew ? P_NEW : blockno); + GISTInitBuffer(buffer, GistPageIsLeaf(page) ? F_LEAF : 0); + /* If the page is new - check that it was allocated correctly */ + Assert(BufferGetBlockNumber(buffer) == blockno); + + LockBuffer(buffer, GIST_EXCLUSIVE); + newpage = BufferGetPage(buffer); + + START_CRIT_SECTION(); + memcpy(newpage, page, BLCKSZ); + + MarkBufferDirty(buffer); + log_newpage_buffer(buffer, true); + END_CRIT_SECTION(); + UnlockReleaseBuffer(buffer); +} + +/* This is basically a page and a reference to yet another iterator */ +typedef struct PageIterator +{ + Page page; + struct PageIterator* next; +} PageIterator; + +/* Flushes page iterator to disk if neccessary. Adds tuple to the block, if itup given. */ +static void +gist_indexsortbuild_pageiterator_add(GISTBuildState *state, PageIterator *pi, IndexTuple itup) +{ + Page page = pi->page; + IndexTuple *itvec; + IndexTuple union_tuple; + int vect_len; + int page_flags; + + /* If we are given a tuple - we can try to accomodate it in a temp block */ + if ((itup != NULL) + && (PageGetFreeSpace(page) >= IndexTupleSize(itup) + sizeof(ItemIdData) + state->freespace)) + { + gistfillbuffer(page, &itup, 1, InvalidOffsetNumber); + return; + } + + /* We have to flush block on disk and form a downlink */ + gist_indexsortbuild_flush(state->indexrel, page, state->next_block, true); + + /* Check if a tree needs to grow */ + if (pi->next == NULL) + { + Assert(TopMemoryContext != state->giststate->tempCxt); + pi->next = palloc(sizeof(PageIterator) + BLCKSZ); + pi->next->page = (Page)(&pi->next[1]); + pi->next->next = NULL; + gistinitpage(pi->next->page, 0); + } + + /* Downlink is union of all tuples on page */ + itvec = gistextractpage(page, &vect_len); + union_tuple = gistunion(state->indexrel, itvec, vect_len, + state->giststate); + ItemPointerSetBlockNumber(&(union_tuple->t_tid), state->next_block); + state->next_block++; + + gist_indexsortbuild_pageiterator_add(state, pi->next, union_tuple); + pfree(itvec); + // TODO: Better to switch to tempCtx here - there's + // a problem with unreturned allocations in gistunion + // But the problem is it's har to pass recursively things that are + // allocated in temp context + pfree(union_tuple); + + page_flags = GistPageIsLeaf(page) ? F_LEAF : 0; + memset(page, 1, BLCKSZ); + gistinitpage(page, page_flags); + + /* if itup given - add it to new page */ + if (itup != NULL) + gistfillbuffer(page, &itup, 1, InvalidOffsetNumber); +} + +/* + * given a spool loaded by successive calls to _h_spool, + * create an entire index. + */ +static void +gist_indexsortbuild(GISTBuildState *state) +{ + GSpool *gspool = state->spool; + /* + * Build constructs GiST by levels. Level is always allocated + * sequentially from level_start until level_end. + */ + state->next_block = GIST_ROOT_BLKNO + 1; + IndexTuple itup; + + /* Allocate a temp block withing page iterator to gather tuples */ + PageIterator *pi = palloc(sizeof(PageIterator) + BLCKSZ); + Page page = (Page)(&pi[1]); + pi->page = page; + pi->next = NULL; + gistinitpage(page, F_LEAF); + + tuplesort_performsort(gspool->sortstate); + + /* Write tuples into the index */ + while ((itup = tuplesort_getindextuple(gspool->sortstate, true)) != NULL) + { + gist_indexsortbuild_pageiterator_add(state, pi, itup); + } + + /* Some tuples are left in page iterators - let's flush them */ + while (pi->next != NULL) + { + PageIterator *pi_next; /* Keep in mind that flush can build new root */ + gist_indexsortbuild_pageiterator_add(state, pi, NULL); + pi_next = pi->next; + pfree (pi); + pi = pi_next; + } + + /* Last block is root */ + gist_indexsortbuild_flush(state->indexrel, pi->page, GIST_ROOT_BLKNO, + false); + pfree(pi); +} + +/* + * spool an index entry into the sort file. + */ +static void +gist_spool(GSpool *gspool, ItemPointer self, Datum *values, bool *isnull) +{ + tuplesort_putindextuplevalues(gspool->sortstate, gspool->index, + self, values, isnull); +} + /* * Main entry point to GiST index build. Initially calls insert over and over, * but switches to more efficient buffering build algorithm after a certain @@ -121,11 +310,15 @@ gistbuild(Relation heap, Relation index, IndexInfo *indexInfo) Buffer buffer; Page page; MemoryContext oldcxt = CurrentMemoryContext; - int fillfactor; + int fillfactor, i; + Oid SortSupportFnOids[INDEX_MAX_KEYS]; + bool hasallsortsupports = true; + int keyscount = IndexRelationGetNumberOfKeyAttributes(index); buildstate.indexrel = index; buildstate.heaprel = heap; + buildstate.spool = NULL; if (index->rd_options) { /* Get buffering mode from the options string */ @@ -152,6 +345,24 @@ gistbuild(Relation heap, Relation index, IndexInfo *indexInfo) /* Calculate target amount of free space to leave on pages */ buildstate.freespace = BLCKSZ * (100 - fillfactor) / 100; + for (i = 0; i < keyscount; i++) + { + SortSupportFnOids[i] = index_getprocid(index, i + 1, GIST_SORTSUPPORT_PROC); + if (!OidIsValid(SortSupportFnOids[i])) + { + hasallsortsupports = false; + break; + } + } + if (hasallsortsupports) + { + SortSupport sort = palloc0(sizeof(SortSupportData) * keyscount); + for (i = 0; i < keyscount; i++) + OidFunctionCall1(SortSupportFnOids[i], PointerGetDatum(sort + i)); + buildstate.bufferingMode = GIST_BUFFERING_DISABLED; + buildstate.spool = gist_spoolinit(heap, index, sort); + } + /* * We expect to be called exactly once for any index relation. If that's * not the case, big trouble's what we have. @@ -208,6 +419,12 @@ gistbuild(Relation heap, Relation index, IndexInfo *indexInfo) gistFreeBuildBuffers(buildstate.gfbb); } + if (buildstate.spool) + { + gist_indexsortbuild(&buildstate); + tuplesort_end(buildstate.spool->sortstate); + } + /* okay, all heap tuples are indexed */ MemoryContextSwitchTo(oldcxt); MemoryContextDelete(buildstate.giststate->tempCxt); @@ -218,7 +435,7 @@ gistbuild(Relation heap, Relation index, IndexInfo *indexInfo) * We didn't write WAL records as we built the index, so if WAL-logging is * required, write all pages to the WAL now. */ - if (RelationNeedsWAL(index)) + if (RelationNeedsWAL(index) && (buildstate.spool == NULL)) { log_newpage_range(index, MAIN_FORKNUM, 0, RelationGetNumberOfBlocks(index), @@ -449,14 +666,20 @@ gistBuildCallback(Relation index, GISTBuildState *buildstate = (GISTBuildState *) state; IndexTuple itup; MemoryContext oldCtx; + Datum compressed_values[INDEX_MAX_KEYS]; oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt); /* form an index tuple and point it at the heap tuple */ - itup = gistFormTuple(buildstate->giststate, index, values, isnull, true); + itup = gistCompressValuesAndFormTuple(buildstate->giststate, index, values, isnull, true, compressed_values); itup->t_tid = *tid; - if (buildstate->bufferingMode == GIST_BUFFERING_ACTIVE) + if (buildstate->spool) + { + if (tupleIsAlive) + gist_spool(buildstate->spool, (ItemPointer)itup, compressed_values, isnull); + } + else if (buildstate->bufferingMode == GIST_BUFFERING_ACTIVE) { /* We have buffers, so use them. */ gistBufferingBuildInsert(buildstate, itup); diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.c index bfda7fbe3d..86f18ba7a6 100644 --- a/src/backend/access/gist/gistutil.c +++ b/src/backend/access/gist/gistutil.c @@ -173,6 +173,7 @@ gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len, datum = index_getattr(itvec[j], i + 1, giststate->leafTupdesc, &IsNull); + if (IsNull) continue; @@ -572,9 +573,16 @@ gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e, IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, - Datum attdata[], bool isnull[], bool isleaf) + Datum* attdata, bool* isnull, bool isleaf) { Datum compatt[INDEX_MAX_KEYS]; + return gistCompressValuesAndFormTuple(giststate, r, attdata, isnull, isleaf, compatt); +} + +IndexTuple +gistCompressValuesAndFormTuple(GISTSTATE *giststate, Relation r, + Datum* attdata, bool* isnull, bool isleaf, Datum* compatt) +{ int i; IndexTuple res; @@ -745,14 +753,10 @@ gistpenalty(GISTSTATE *giststate, int attno, * Initialize a new index page */ void -GISTInitBuffer(Buffer b, uint32 f) +gistinitpage(Page page, uint32 f) { - GISTPageOpaque opaque; - Page page; - Size pageSize; - - pageSize = BufferGetPageSize(b); - page = BufferGetPage(b); + GISTPageOpaque opaque; + Size pageSize = BLCKSZ; PageInit(page, pageSize, sizeof(GISTPageOpaqueData)); opaque = GistPageGetOpaque(page); @@ -763,6 +767,18 @@ GISTInitBuffer(Buffer b, uint32 f) opaque->gist_page_id = GIST_PAGE_ID; } +/* + * Initialize a new index buffer + */ +void +GISTInitBuffer(Buffer b, uint32 f) +{ + Page page; + + page = BufferGetPage(b); + gistinitpage(page, f); +} + /* * Verify that a freshly-read page looks sane. */ diff --git a/src/backend/access/gist/gistvalidate.c b/src/backend/access/gist/gistvalidate.c index 2b9ab693be..8a14620fab 100644 --- a/src/backend/access/gist/gistvalidate.c +++ b/src/backend/access/gist/gistvalidate.c @@ -143,6 +143,10 @@ gistvalidate(Oid opclassoid) case GIST_OPTIONS_PROC: ok = check_amoptsproc_signature(procform->amproc); break; + case GIST_SORTSUPPORT_PROC: + ok = check_amproc_signature(procform->amproc, VOIDOID, true, + 1, 1, INTERNALOID); + break; default: ereport(INFO, (errcode(ERRCODE_INVALID_OBJECT_DEFINITION), @@ -263,7 +267,7 @@ gistvalidate(Oid opclassoid) continue; /* got it */ if (i == GIST_DISTANCE_PROC || i == GIST_FETCH_PROC || i == GIST_COMPRESS_PROC || i == GIST_DECOMPRESS_PROC || - i == GIST_OPTIONS_PROC) + i == GIST_OPTIONS_PROC || i == GIST_SORTSUPPORT_PROC) continue; /* optional methods */ ereport(INFO, (errcode(ERRCODE_INVALID_OBJECT_DEFINITION), diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 3c49476483..c5c7e5af05 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -1167,6 +1167,43 @@ tuplesort_begin_index_hash(Relation heapRel, return state; } +Tuplesortstate * +tuplesort_begin_index_gist(Relation heapRel, + Relation indexRel, + SortSupport ssup, + int workMem, + SortCoordinate coordinate, + bool randomAccess) +{ + Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate, + randomAccess); + MemoryContext oldcontext; + + oldcontext = MemoryContextSwitchTo(state->sortcontext); + +#ifdef TRACE_SORT + if (trace_sort) + elog(LOG, + "begin index sort: workMem = %d, randomAccess = %c", + workMem, randomAccess ? 't' : 'f'); +#endif + + state->nKeys = IndexRelationGetNumberOfKeyAttributes(indexRel); + + state->comparetup = comparetup_index_btree; + state->copytup = copytup_index; + state->writetup = writetup_index; + state->readtup = readtup_index; + state->sortKeys = ssup; + + state->heapRel = heapRel; + state->indexRel = indexRel; + + MemoryContextSwitchTo(oldcontext); + + return state; +} + Tuplesortstate * tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, int workMem, diff --git a/src/include/access/gist.h b/src/include/access/gist.h index 4994351697..4f6dae9a76 100644 --- a/src/include/access/gist.h +++ b/src/include/access/gist.h @@ -37,7 +37,8 @@ #define GIST_DISTANCE_PROC 8 #define GIST_FETCH_PROC 9 #define GIST_OPTIONS_PROC 10 -#define GISTNProcs 10 +#define GIST_SORTSUPPORT_PROC 11 +#define GISTNProcs 11 /* * Page opaque data in a GiST index page. diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h index 02e985549f..6af8a4b69b 100644 --- a/src/include/access/gist_private.h +++ b/src/include/access/gist_private.h @@ -501,12 +501,15 @@ extern IndexTuple gistgetadjusted(Relation r, GISTSTATE *giststate); extern IndexTuple gistFormTuple(GISTSTATE *giststate, Relation r, Datum *attdata, bool *isnull, bool isleaf); +extern IndexTuple gistCompressValuesAndFormTuple(GISTSTATE *giststate, Relation r, + Datum* attdata, bool* isnull, bool isleaf, Datum* compatt); extern OffsetNumber gistchoose(Relation r, Page p, IndexTuple it, GISTSTATE *giststate); extern void GISTInitBuffer(Buffer b, uint32 f); +extern void gistinitpage(Page page, uint32 f); extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e, Datum k, Relation r, Page pg, OffsetNumber o, bool l, bool isNull); diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat index 37b580883f..a8e0c4ff8a 100644 --- a/src/include/catalog/pg_amproc.dat +++ b/src/include/catalog/pg_amproc.dat @@ -480,6 +480,8 @@ amproc => 'gist_point_distance' }, { amprocfamily => 'gist/point_ops', amproclefttype => 'point', amprocrighttype => 'point', amprocnum => '9', amproc => 'gist_point_fetch' }, +{ amprocfamily => 'gist/point_ops', amproclefttype => 'point', + amprocrighttype => 'point', amprocnum => '11', amproc => 'gist_point_sortsupport' }, { amprocfamily => 'gist/box_ops', amproclefttype => 'box', amprocrighttype => 'box', amprocnum => '1', amproc => 'gist_box_consistent' }, { amprocfamily => 'gist/box_ops', amproclefttype => 'box', diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h index 9e76666fe9..f39f232aae 100644 --- a/src/include/utils/tuplesort.h +++ b/src/include/utils/tuplesort.h @@ -25,6 +25,7 @@ #include "executor/tuptable.h" #include "storage/dsm.h" #include "utils/relcache.h" +#include "utils/sortsupport.h" /* @@ -217,6 +218,11 @@ extern Tuplesortstate *tuplesort_begin_index_hash(Relation heapRel, uint32 max_buckets, int workMem, SortCoordinate coordinate, bool randomAccess); +extern Tuplesortstate *tuplesort_begin_index_gist(Relation heapRel, + Relation indexRel, + SortSupport ssup, + int workMem, SortCoordinate coordinate, + bool randomAccess); extern Tuplesortstate *tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation, bool nullsFirstFlag, -- 2.24.3 (Apple Git-128)