On 08/09/2020 21:33, Pavel Borisov wrote:
> Thanks! Did you measure the quality of the built index somehow? The
> ordering shouldn't make any difference to the build speed, but it
> affects the shape of the resulting index and the speed of queries
> against it.
Again I've tried random select tests near axes and haven't noticed any
performance difference between ordinary gist build and z-ordered one.
The same is for selects far from axes. Theoretically, there may be a
possible slowdown for particular points inside the MBR which crosses the
axis but I haven't tried to dig so deep and haven't tested performance
as a function of coordinate.
So I feel this patch is not about select speed optimization.
Ok, thank for confirming.
I've been reviewing the patch today. The biggest changes I've made have
been in restructuring the code in gistbuild.c for readability, but there
are a bunch of smaller changes throughout. Attached is what I've got so
far, squashed into one patch. I'm continuing to review it, but a couple
of questions so far:
In the gistBuildCallback(), you're skipping the tuple if 'tupleIsAlive
== false'. That seems fishy, surely we need to index recently-dead
tuples, too. The normal index build path isn't skipping them either.
How does the 'sortsupport' routine interact with
'compress'/'decompress'? Which representation is passed to the
comparator routine: the original value from the table, the compressed
representation, or the decompressed representation? Do the
comparetup_index_btree() and readtup_index() routines agree with that?
- Heikki
>From 7a9331bbd43799150d6a0b9dad2e98604c6b7dfc Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakan...@iki.fi>
Date: Tue, 8 Sep 2020 21:56:41 +0300
Subject: [PATCH v16 1/1] Add sort support for point gist_point_sortsupport
Implement GiST build using sort support
We use special sorting function provided by opclass to approximate
GiST tree with B-tree-like structure. This approach allows to
radically reduce build time in some cases.
Discussion: https://www.postgresql.org/message-id/1A36620E-CAD8-4267-9067-FB31385E7C0D%40yandex-team.ru
Reviewed-by: Pavel Borisov, Thomas Munro
---
doc/src/sgml/gist.sgml | 64 +++
src/backend/access/gist/gistbuild.c | 511 ++++++++++++++++++++----
src/backend/access/gist/gistproc.c | 154 +++++++
src/backend/access/gist/gistutil.c | 59 ++-
src/backend/access/gist/gistvalidate.c | 6 +-
src/backend/access/transam/xloginsert.c | 57 +++
src/backend/utils/sort/tuplesort.c | 37 ++
src/include/access/gist.h | 3 +-
src/include/access/gist_private.h | 3 +
src/include/access/xloginsert.h | 2 +
src/include/catalog/pg_amproc.dat | 2 +
src/include/catalog/pg_proc.dat | 3 +
src/include/utils/tuplesort.h | 6 +
13 files changed, 801 insertions(+), 106 deletions(-)
diff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgml
index f9226e7a35c..bc45b3260f2 100644
--- a/doc/src/sgml/gist.sgml
+++ b/doc/src/sgml/gist.sgml
@@ -259,6 +259,8 @@ CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops);
<function>compress</function> method is omitted. The optional tenth method
<function>options</function> is needed if the operator class provides
the user-specified parameters.
+ The <function>sortsupport</function> method is also optional and is used to speed up
+ building a <acronym>GiST</acronym> index.
</para>
<variablelist>
@@ -1065,6 +1067,68 @@ my_compress(PG_FUNCTION_ARGS)
</para>
</listitem>
</varlistentry>
+
+ <varlistentry>
+ <term><function>sortsupport</function></term>
+ <listitem>
+ <para>
+ Returns a comparator function to sort data in a way that preserves
+ locality. It is used by <command>CREATE INDEX</command> and
+ <command>REINDEX</command>. The quality of the created index depends on
+ how well the sort order determined by the comparator routine preserves
+ locality of the inputs.
+ </para>
+ <para>
+ The <function>sortsupport</function> method is optional. If it is not
+ provided, <command>CREATE INDEX</command> builds the index by inserting
+ each tuple to the tree using the <function>penalty</function> and
+ <function>picksplit</function> functions, which is much slower.
+ </para>
+
+ <para>
+ The <acronym>SQL</acronym> declaration of the function must look like this:
+
+<programlisting>
+CREATE OR REPLACE FUNCTION my_sortsupport(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
+</programlisting>
+
+ The argument is a pointer to a <structname>SortSupport</structname> struct.
+ At a minimum, the function must fill in its comparator field, the full API
+ is defined in <filename>src/include/utils/sortsupport.h</filename>.
+ </para>
+
+ <para>
+ The matching code in the C module could then follow this skeleton:
+
+<programlisting>
+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();
+}
+</programlisting>
+ </para>
+ </listitem>
+ </varlistentry>
</variablelist>
<para>
diff --git a/src/backend/access/gist/gistbuild.c b/src/backend/access/gist/gistbuild.c
index 671b5e9186f..8693be60b6f 100644
--- a/src/backend/access/gist/gistbuild.c
+++ b/src/backend/access/gist/gistbuild.c
@@ -4,6 +4,25 @@
* build algorithm for GiST indexes implementation.
*
*
+ * There are two different strategies:
+ *
+ * 1. Sort all input tuples, pack the tuple into GiST pages in the sorted
+ * order. This builds the index from the bottom up, similar to how the
+ * B-tree build works.
+ *
+ * 2. Start with an empty index, and insert all tuples one by one.
+ *
+ * The sorted method is used if the operator class for all the columns
+ * have a 'sortsupport' defined. Otherwise, we resort to the second
+ * strategy.
+ *
+ * The second strategy can optionally use buffers at different levels of
+ * the tree to reduce I/O, see "Buffering build algorithm" in the README
+ * for a more detailed explanation. It initially calls insert over and over,
+ * but switches to the buffered algorithm after a certain number of tuples
+ * (unless buffering mode is disabled).
+ *
+
* Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
@@ -28,6 +47,7 @@
#include "storage/smgr.h"
#include "utils/memutils.h"
#include "utils/rel.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
@@ -40,8 +60,14 @@
*/
#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET 4096
+/*
+ * Strategy used to build the index. The mode can be changed between
+ * GIST_BUFFERING_* modes on the fly, but if the Sorted method is used,
+ * that needs to be decided up-front and cannot be changed afterwards.
+ */
typedef enum
{
+ GIST_SORTED_BUILD, /* bottom-up build by sorting */
GIST_BUFFERING_DISABLED, /* in regular build mode and aren't going to
* switch */
GIST_BUFFERING_AUTO, /* in regular build mode, but will switch to
@@ -51,7 +77,7 @@ typedef enum
* before switching to the buffering build
* mode */
GIST_BUFFERING_ACTIVE /* in buffering build mode */
-} GistBufferingMode;
+} GistBuildMode;
/* Working state for gistbuild and its callback */
typedef struct
@@ -60,23 +86,57 @@ typedef struct
Relation heaprel;
GISTSTATE *giststate;
- int64 indtuples; /* number of tuples indexed */
- int64 indtuplesSize; /* total size of all indexed tuples */
-
Size freespace; /* amount of free space to leave on pages */
+ GistBuildMode buildMode;
+
+ int64 indtuples; /* number of tuples indexed */
+
/*
* Extra data structures used during a buffering build. 'gfbb' contains
* information related to managing the build buffers. 'parentMap' is a
* lookup table of the parent of each internal page.
*/
+ int64 indtuplesSize; /* total size of all indexed tuples */
GISTBuildBuffers *gfbb;
HTAB *parentMap;
- GistBufferingMode bufferingMode;
+ /*
+ * Extra data structures used during a sorting build.
+ */
+ Tuplesortstate *sortstate; /* state data for tuplesort.c */
+
+ BlockNumber pages_allocated;
+ BlockNumber pages_written;
+
+ int ready_num_pages;
+ BlockNumber ready_blknos[XLR_MAX_BLOCK_ID];
+ Page ready_pages[XLR_MAX_BLOCK_ID];
} GISTBuildState;
+/*
+ * Sorted tuples are packed into pages using a stack of these structs.
+ * one for each level.
+ */
+typedef struct GistSortedBuildPageState
+{
+ Page page;
+ struct GistSortedBuildPageState *parent; /* Upper level, if any */
+} GistSortedBuildPageState;
+
/* prototypes for private 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 *pi, IndexTuple itup);
+static void gist_indexsortbuild_pagestate_flush(GISTBuildState *state, GistSortedBuildPageState *pi);
+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,
@@ -107,10 +167,9 @@ static void gistMemorizeParent(GISTBuildState *buildstate, BlockNumber child,
static void gistMemorizeAllDownlinks(GISTBuildState *buildstate, Buffer parent);
static BlockNumber gistGetParent(GISTBuildState *buildstate, BlockNumber child);
+
/*
- * Main entry point to GiST index build. Initially calls insert over and over,
- * but switches to more efficient buffering build algorithm after a certain
- * number of tuples (unless buffering mode is disabled).
+ * Main entry point to GiST index build.
*/
IndexBuildResult *
gistbuild(Relation heap, Relation index, IndexInfo *indexInfo)
@@ -118,124 +177,408 @@ gistbuild(Relation heap, Relation index, IndexInfo *indexInfo)
IndexBuildResult *result;
double reltuples;
GISTBuildState buildstate;
- Buffer buffer;
- Page page;
MemoryContext oldcxt = CurrentMemoryContext;
int fillfactor;
+ Oid SortSupportFnOids[INDEX_MAX_KEYS];
+ bool hasallsortsupports;
+ int keyscount = IndexRelationGetNumberOfKeyAttributes(index);
+ GiSTOptions *options = NULL;
+
+ /*
+ * We expect to be called exactly once for any index relation. If that's
+ * not the case, big trouble's what we have.
+ */
+ if (RelationGetNumberOfBlocks(index) != 0)
+ elog(ERROR, "index \"%s\" already contains data",
+ RelationGetRelationName(index));
+
+ if (index->rd_options)
+ options = (GiSTOptions *) index->rd_options;
buildstate.indexrel = index;
buildstate.heaprel = heap;
+ buildstate.sortstate = NULL;
+ buildstate.giststate = initGISTstate(index);
- if (index->rd_options)
+ /*
+ * Create a temporary memory context that is reset once for each tuple
+ * processed. (Note: we don't bother to make this a child of the
+ * giststate's scanCxt, so we have to delete it separately at the end.)
+ */
+ buildstate.giststate->tempCxt = createTempGistContext();
+
+ /*
+ * Choose build strategy. If all keys support sorting, do that.
+ * Otherwise the default strategy is switch to buffering mode when
+ * the index grows too large to fit in cache.
+ */
+ hasallsortsupports = true;
+ for (int i = 0; i < keyscount; i++)
{
- /* Get buffering mode from the options string */
- GiSTOptions *options = (GiSTOptions *) index->rd_options;
+ SortSupportFnOids[i] = index_getprocid(index, i + 1, GIST_SORTSUPPORT_PROC);
+ if (!OidIsValid(SortSupportFnOids[i]))
+ {
+ hasallsortsupports = false;
+ break;
+ }
+ }
+ if (hasallsortsupports)
+ {
+ buildstate.buildMode = GIST_SORTED_BUILD;
+ }
+ else if (options)
+ {
if (options->buffering_mode == GIST_OPTION_BUFFERING_ON)
- buildstate.bufferingMode = GIST_BUFFERING_STATS;
+ buildstate.buildMode = GIST_BUFFERING_STATS;
else if (options->buffering_mode == GIST_OPTION_BUFFERING_OFF)
- buildstate.bufferingMode = GIST_BUFFERING_DISABLED;
+ buildstate.buildMode = GIST_BUFFERING_DISABLED;
else
- buildstate.bufferingMode = GIST_BUFFERING_AUTO;
-
- fillfactor = options->fillfactor;
+ buildstate.buildMode = GIST_BUFFERING_AUTO;
}
else
{
- /*
- * By default, switch to buffering mode when the index grows too large
- * to fit in cache.
- */
- buildstate.bufferingMode = GIST_BUFFERING_AUTO;
- fillfactor = GIST_DEFAULT_FILLFACTOR;
+ buildstate.buildMode = GIST_BUFFERING_AUTO;
}
- /* Calculate target amount of free space to leave on pages */
+
+ /*
+ * Calculate target amount of free space to leave on pages.
+ */
+ fillfactor = options ? options->fillfactor : GIST_DEFAULT_FILLFACTOR;
buildstate.freespace = BLCKSZ * (100 - fillfactor) / 100;
/*
- * We expect to be called exactly once for any index relation. If that's
- * not the case, big trouble's what we have.
+ * Build the index using the chosen strategy.
*/
- if (RelationGetNumberOfBlocks(index) != 0)
- elog(ERROR, "index \"%s\" already contains data",
- RelationGetRelationName(index));
+ buildstate.indtuples = 0;
+ buildstate.indtuplesSize = 0;
- /* no locking is needed */
- buildstate.giststate = initGISTstate(index);
+ if (buildstate.buildMode == GIST_SORTED_BUILD)
+ {
+ /*
+ * Sort all data, build the index from bottom up.
+ */
+ SortSupport ssup;
+
+ /*
+ * 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.
+ */
+ ssup = palloc0(sizeof(SortSupportData) * keyscount);
+ for (int i = 0; i < keyscount; i++)
+ OidFunctionCall1(SortSupportFnOids[i], PointerGetDatum(&ssup[i]));
+ buildstate.sortstate = tuplesort_begin_index_gist(heap,
+ index,
+ ssup,
+ maintenance_work_mem,
+ NULL,
+ false);
+
+ /* Scan the table, adding all tuples to the tuplesort */
+ reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
+ gistSortedBuildCallback,
+ (void *) &buildstate, NULL);
+
+ /*
+ * Perform the sort and build index pages.
+ */
+ tuplesort_performsort(buildstate.sortstate);
+
+ gist_indexsortbuild(&buildstate);
+
+ tuplesort_end(buildstate.sortstate);
+ }
+ else
+ {
+ /*
+ * Initialize an empty index and insert all tuples, possibly using
+ * buffers on intermediate levels.
+ */
+ Buffer buffer;
+ Page page;
+
+ /* initialize the root page */
+ buffer = gistNewBuffer(index);
+ Assert(BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO);
+ page = BufferGetPage(buffer);
+
+ START_CRIT_SECTION();
+
+ GISTInitBuffer(buffer, F_LEAF);
+
+ MarkBufferDirty(buffer);
+ PageSetLSN(page, GistBuildLSN);
+
+ UnlockReleaseBuffer(buffer);
+
+ END_CRIT_SECTION();
+
+ /* Scan the table, inserting all the tuples to the index. */
+ reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
+ gistBuildCallback,
+ (void *) &buildstate, NULL);
+
+ /*
+ * If buffering was used, flush out all the tuples that are still in the
+ * buffers.
+ */
+ if (buildstate.buildMode == GIST_BUFFERING_ACTIVE)
+ {
+ elog(DEBUG1, "all tuples processed, emptying buffers");
+ gistEmptyAllBuffers(&buildstate);
+ gistFreeBuildBuffers(buildstate.gfbb);
+ }
+
+ /*
+ * 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))
+ {
+ log_newpage_range(index, MAIN_FORKNUM,
+ 0, RelationGetNumberOfBlocks(index),
+ true);
+ }
+ }
+
+ /* okay, all heap tuples are indexed */
+ MemoryContextSwitchTo(oldcxt);
+ MemoryContextDelete(buildstate.giststate->tempCxt);
+
+ freeGISTstate(buildstate.giststate);
/*
- * Create a temporary memory context that is reset once for each tuple
- * processed. (Note: we don't bother to make this a child of the
- * giststate's scanCxt, so we have to delete it separately at the end.)
+ * Return statistics
*/
- buildstate.giststate->tempCxt = createTempGistContext();
+ result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
- /* initialize the root page */
- buffer = gistNewBuffer(index);
- Assert(BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO);
- page = BufferGetPage(buffer);
+ result->heap_tuples = reltuples;
+ result->index_tuples = (double) buildstate.indtuples;
- START_CRIT_SECTION();
+ return result;
+}
- GISTInitBuffer(buffer, F_LEAF);
+/*-------------------------------------------------------------------------
+ * Routines for sorted build
+ *-------------------------------------------------------------------------
+ */
- MarkBufferDirty(buffer);
- PageSetLSN(page, GistBuildLSN);
+/*
+ * Per-tuple callback for table_index_build_scan, for sorted builds.
+ */
+static void
+gistSortedBuildCallback(Relation index,
+ ItemPointer tid,
+ Datum *values,
+ bool *isnull,
+ bool tupleIsAlive,
+ void *state)
+{
+ GISTBuildState *buildstate = (GISTBuildState *) state;
+ MemoryContext oldCtx;
+ Datum compressed_values[INDEX_MAX_KEYS];
- UnlockReleaseBuffer(buffer);
+ if (!tupleIsAlive)
+ {
+ // FIXME: Is this okay?
+ return;
+ }
- END_CRIT_SECTION();
+ oldCtx = MemoryContextSwitchTo(buildstate->giststate->tempCxt);
- /* build the index */
- buildstate.indtuples = 0;
- buildstate.indtuplesSize = 0;
+ /* Form an index tuple and point it at the heap tuple */
+ gistCompressValues(buildstate->giststate, index,
+ values, isnull,
+ true, compressed_values);
+
+ tuplesort_putindextuplevalues(buildstate->sortstate,
+ buildstate->indexrel,
+ tid,
+ compressed_values, isnull);
+
+ MemoryContextSwitchTo(oldCtx);
+ MemoryContextReset(buildstate->giststate->tempCxt);
+
+ /* Update tuple count. */
+ buildstate->indtuples += 1;
+}
+
+/*
+ * Sort all tuples, and build the GiST index from bottom up.
+ */
+static void
+gist_indexsortbuild(GISTBuildState *state)
+{
+ IndexTuple itup;
+ GistSortedBuildPageState *leafstate;
+ GistSortedBuildPageState *pagestate;
+ Page page;
+
+ state->pages_allocated = 0;
+ state->pages_written = 0;
+ state->ready_num_pages = 0;
/*
- * Do the heap scan.
+ * Write an empty page as a placeholder for the root page. It will be
+ * replaced with the real root page at the end.
*/
- reltuples = table_index_build_scan(heap, index, indexInfo, true, true,
- gistBuildCallback,
- (void *) &buildstate, NULL);
+ page = palloc0(BLCKSZ);
+ smgrextend(state->indexrel->rd_smgr, MAIN_FORKNUM, GIST_ROOT_BLKNO,
+ page, true);
+ state->pages_allocated++;
+ state->pages_written++;
+
+ /* Allocate a scratch page in memory to collect the tuples */
+ leafstate = palloc(sizeof(GistSortedBuildPageState));
+ leafstate->page = page;
+ leafstate->parent = NULL;
+ gistinitpage(page, F_LEAF);
/*
- * If buffering was used, flush out all the tuples that are still in the
- * buffers.
+ * Fill index pages with tuples in the sorted order.
*/
- if (buildstate.bufferingMode == GIST_BUFFERING_ACTIVE)
+ while ((itup = tuplesort_getindextuple(state->sortstate, true)) != NULL)
{
- elog(DEBUG1, "all tuples processed, emptying buffers");
- gistEmptyAllBuffers(&buildstate);
- gistFreeBuildBuffers(buildstate.gfbb);
+ gist_indexsortbuild_pagestate_add(state, leafstate, itup);
}
- /* okay, all heap tuples are indexed */
- MemoryContextSwitchTo(oldcxt);
- MemoryContextDelete(buildstate.giststate->tempCxt);
-
- freeGISTstate(buildstate.giststate);
-
/*
- * We didn't write WAL records as we built the index, so if WAL-logging is
- * required, write all pages to the WAL now.
+ * Write out the partially full non-root pages.
*/
- if (RelationNeedsWAL(index))
+ pagestate = leafstate;
+ while (pagestate->parent != NULL)
{
- log_newpage_range(index, MAIN_FORKNUM,
- 0, RelationGetNumberOfBlocks(index),
- true);
+ GistSortedBuildPageState *parent; /* Keep in mind that flush can build new root */
+
+ gist_indexsortbuild_pagestate_flush(state, pagestate);
+ parent = pagestate->parent;
+ pfree(pagestate->page);
+ pfree(pagestate);
+ pagestate = parent;
}
+ gist_indexsortbuild_flush_ready_pages(state);
+
+ /* Write out the root */
+ smgrwrite(state->indexrel->rd_smgr, MAIN_FORKNUM, GIST_ROOT_BLKNO, pagestate->page, true);
+ if (RelationNeedsWAL(state->indexrel))
+ log_newpage(&state->indexrel->rd_node, MAIN_FORKNUM, GIST_ROOT_BLKNO, pagestate->page, true);
+
+ pfree(pagestate->page);
+ pfree(pagestate);
+}
+
+
+/* Flushes page iterator to disk if neccessary. Adds tuple to the block. */
+static void
+gist_indexsortbuild_pagestate_add(GISTBuildState *state,
+ GistSortedBuildPageState *pagestate,
+ IndexTuple itup)
+{
+ Page page = pagestate->page;
+
+ /* Does the tuple fit? If not, flush */
+ if (PageGetFreeSpace(page) < IndexTupleSize(itup) + sizeof(ItemIdData) + state->freespace)
+ gist_indexsortbuild_pagestate_flush(state, pagestate);
+
+ gistfillbuffer(page, &itup, 1, InvalidOffsetNumber);
+}
+
+static void
+gist_indexsortbuild_pagestate_flush(GISTBuildState *state,
+ GistSortedBuildPageState *pagestate)
+{
+ GistSortedBuildPageState *parent;
+ IndexTuple *itvec;
+ IndexTuple union_tuple;
+ int vect_len;
+ bool isleaf;
+ BlockNumber blkno;
+
+ if (state->ready_num_pages == XLR_MAX_BLOCK_ID)
+ gist_indexsortbuild_flush_ready_pages(state);
+
/*
- * Return statistics
+ * 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.)
*/
- result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));
+ 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++;
- result->heap_tuples = reltuples;
- result->index_tuples = (double) buildstate.indtuples;
+ /* check once per page */
+ CHECK_FOR_INTERRUPTS();
- return result;
+ isleaf = GistPageIsLeaf(pagestate->page);
+
+ /*
+ * Form a downlink tuple to represent all the tuples on the page.
+ */
+ itvec = gistextractpage(pagestate->page, &vect_len);
+ union_tuple = gistunion(state->indexrel, itvec, vect_len,
+ state->giststate);
+ ItemPointerSetBlockNumber(&(union_tuple->t_tid), blkno);
+ pfree(itvec);
+
+ /*
+ * 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)
+ {
+ parent = palloc(sizeof(GistSortedBuildPageState));
+ parent->page = (Page) palloc(BLCKSZ);
+ parent->parent = NULL;
+ gistinitpage(parent->page, 0);
+
+ pagestate->parent = parent;
+ }
+ gist_indexsortbuild_pagestate_add(state, parent, union_tuple);
+ pfree(union_tuple);
+
+ /* Re-initialize the page buffer for next page on this level. */
+ pagestate->page = palloc(BLCKSZ);
+ gistinitpage(pagestate->page, isleaf ? F_LEAF : 0);
+}
+
+static void
+gist_indexsortbuild_flush_ready_pages(GISTBuildState *state)
+{
+ if (state->ready_num_pages == 0)
+ return;
+
+ for (int i = 0; i < state->ready_num_pages; i++)
+ {
+ /*
+ * currently, the blocks must be buffered in order. Otherwise we should
+ * do a similar smgrextend/ smgrwrite dance as in nbtsort.c
+ */
+ if (state->ready_blknos[i] != state->pages_written)
+ elog(ERROR, "unexpected block number to flush GiST sorting build");
+
+ smgrextend(state->indexrel->rd_smgr,
+ MAIN_FORKNUM,
+ state->pages_written++,
+ state->ready_pages[i],
+ true);
+ }
+
+ if (RelationNeedsWAL(state->indexrel))
+ log_newpages(&state->indexrel->rd_node, MAIN_FORKNUM, state->ready_num_pages,
+ state->ready_blknos, state->ready_pages, true);
+ state->ready_num_pages = 0;
}
+
+/*-------------------------------------------------------------------------
+ * Routines for non-sorted build
+ *-------------------------------------------------------------------------
+ */
+
/*
* Attempt to switch to buffering mode.
*
@@ -375,7 +718,7 @@ gistInitBuffering(GISTBuildState *buildstate)
if (levelStep <= 0)
{
elog(DEBUG1, "failed to switch to buffered GiST build");
- buildstate->bufferingMode = GIST_BUFFERING_DISABLED;
+ buildstate->buildMode = GIST_BUFFERING_DISABLED;
return;
}
@@ -392,7 +735,7 @@ gistInitBuffering(GISTBuildState *buildstate)
gistInitParentMap(buildstate);
- buildstate->bufferingMode = GIST_BUFFERING_ACTIVE;
+ buildstate->buildMode = GIST_BUFFERING_ACTIVE;
elog(DEBUG1, "switched to buffered GiST build; level step = %d, pagesPerBuffer = %d",
levelStep, pagesPerBuffer);
@@ -453,10 +796,12 @@ gistBuildCallback(Relation index,
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 = gistFormTuple(buildstate->giststate, index,
+ values, isnull,
+ true);
itup->t_tid = *tid;
- if (buildstate->bufferingMode == GIST_BUFFERING_ACTIVE)
+ if (buildstate->buildMode == GIST_BUFFERING_ACTIVE)
{
/* We have buffers, so use them. */
gistBufferingBuildInsert(buildstate, itup);
@@ -478,7 +823,7 @@ gistBuildCallback(Relation index,
MemoryContextSwitchTo(oldCtx);
MemoryContextReset(buildstate->giststate->tempCxt);
- if (buildstate->bufferingMode == GIST_BUFFERING_ACTIVE &&
+ if (buildstate->buildMode == GIST_BUFFERING_ACTIVE &&
buildstate->indtuples % BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET == 0)
{
/* Adjust the target buffer size now */
@@ -493,10 +838,10 @@ gistBuildCallback(Relation index,
* To avoid excessive calls to smgrnblocks(), only check this every
* BUFFERING_MODE_SWITCH_CHECK_STEP index tuples
*/
- if ((buildstate->bufferingMode == GIST_BUFFERING_AUTO &&
+ if ((buildstate->buildMode == GIST_BUFFERING_AUTO &&
buildstate->indtuples % BUFFERING_MODE_SWITCH_CHECK_STEP == 0 &&
effective_cache_size < smgrnblocks(index->rd_smgr, MAIN_FORKNUM)) ||
- (buildstate->bufferingMode == GIST_BUFFERING_STATS &&
+ (buildstate->buildMode == GIST_BUFFERING_STATS &&
buildstate->indtuples >= BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET))
{
/*
diff --git a/src/backend/access/gist/gistproc.c b/src/backend/access/gist/gistproc.c
index 9ace64c3c4a..46a5e315193 100644
--- a/src/backend/access/gist/gistproc.c
+++ b/src/backend/access/gist/gistproc.c
@@ -24,12 +24,18 @@
#include "utils/builtins.h"
#include "utils/float.h"
#include "utils/geo_decls.h"
+#include "utils/sortsupport.h"
static bool gist_box_leaf_consistent(BOX *key, BOX *query,
StrategyNumber strategy);
static bool rtree_internal_consistent(BOX *key, BOX *query,
StrategyNumber strategy);
+static uint64 part_bits32_by2(uint32 x);
+static uint32 ieee_float32_to_uint32(float f);
+static uint64 point_zorder_internal(Point *p);
+static int gist_bbox_fastcmp(Datum x, Datum y, SortSupport ssup);
+
/* Minimum accepted ratio of split */
#define LIMIT_RATIO 0.3
@@ -1540,3 +1546,151 @@ gist_poly_distance(PG_FUNCTION_ARGS)
PG_RETURN_FLOAT8(distance);
}
+
+/* Z-order routines */
+
+/*
+ * Compute Z-order for a point
+ *
+ * Map a two-dimensional point to a single integer, in a way that preserves
+ * locality. Points that are close in the two-dimensional space are mapped to
+ * integer that are not far from each other. We do that by interleaving the
+ * bits in the X and Y components, this is called a Z-order or Morton Code.
+ *
+ * A Morton Code is normally defined only for integers, but the X and Y values
+ * of a point are floating point. We expect floats to be in IEEE format, and
+ * the sort order of IEEE floats is mostly correlated to the binary sort order
+ * of the bits reinterpreted as an int. It isn't in some special cases, but
+ * for this use case we don't really care about that, we're just trying to
+ * encourage locality.
+ */
+static uint64
+point_zorder_internal(Point *p)
+{
+ uint32 x = ieee_float32_to_uint32(p->x);
+ uint32 y = ieee_float32_to_uint32(p->y);
+
+ /* Interleave the bits */
+ return part_bits32_by2(x) | (part_bits32_by2(y) << 1);
+}
+
+/* Interleave 32 bits with zeroes */
+static uint64
+part_bits32_by2(uint32 x)
+{
+ uint64 n = x;
+
+ n = (n | (n << 16)) & UINT64CONST(0x0000FFFF0000FFFF);
+ n = (n | (n << 8)) & UINT64CONST(0x00FF00FF00FF00FF);
+ n = (n | (n << 4)) & UINT64CONST(0x0F0F0F0F0F0F0F0F);
+ n = (n | (n << 2)) & UINT64CONST(0x3333333333333333);
+ n = (n | (n << 1)) & UINT64CONST(0x5555555555555555);
+
+ return n;
+}
+
+/*
+ * Convert a 32-bit IEEE float to uint32 in a way that preserves the ordering.
+ */
+static uint32
+ieee_float32_to_uint32(float f)
+{
+ /*----
+ *
+ * IEEE 754 floating point format
+ * ------------------------------
+ *
+ * IEEE 754 floating point numbers have this format:
+ *
+ * exponent (8 bits)
+ * |
+ * s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm
+ * | |
+ * sign mantissa (23 bits)
+ *
+ * Infinity has all bits in the exponent set and the mantissa is
+ * all-zeros. Negative infinity is the same but with the sign bit set.
+ *
+ * NaNs are represented with all bits in the exponent set, and the least
+ * significant bit in the mantissa also set. The rest of the mantissa bits
+ * can be used to distinguish different kinds of NaNs.
+ *
+ * The IEEE format has the nice property that when you take the bit
+ * representation and interpret it as an integer, the order is preserved,
+ * except for the sign. That holds for the +-Infinity values too.
+ *
+ * Mapping to uint32
+ * -----------------
+ *
+ * In order to have a smooth transition from negative to positive numbers,
+ * we map floats to unsigned integers like this:
+ *
+ * x < 0 to range 0-7FFFFFFF
+ * x = 0 to value 8000000 (both positive and negative zero)
+ * x > 0 to range 8000001-FFFFFFFF
+ *
+ * We don't care to distinguish different kind of NaNs, so they are all
+ * mapped to the same arbitrary value, FFFFFFFF. Because of the IEEE bit
+ * representation of NaNs, there aren't any non-NaN values that would be
+ * mapped to FFFFFFFF. In fact, there is a range of unused values on both
+ * ends of the uint32 space.
+ */
+ if (isnan(f))
+ return 0xFFFFFFFF;
+ else
+ {
+ union
+ {
+ float f;
+ uint32 i;
+ } u;
+
+ u.f = f;
+
+ /* Check the sign bit */
+ if ((u.i & 0x80000000) != 0)
+ {
+ /*
+ * Map the negative value to range 0-7FFFFFFF. This flips the sign
+ * bit to 0 in the same instruction.
+ */
+ Assert(f < 0);
+ u.i ^= 0xFFFFFFFF;
+ }
+ else
+ {
+ /* Map the positive value (or 0) to range 80000000-FFFFFFFF */
+ u.i |= 0x80000000;
+ }
+
+ return u.i;
+ }
+}
+
+static int
+gist_bbox_fastcmp(Datum x, Datum y, SortSupport ssup)
+{
+ Point *p1 = &(DatumGetBoxP(x)->low);
+ Point *p2 = &(DatumGetBoxP(y)->low);
+ uint64 z1 = point_zorder_internal(p1);
+ uint64 z2 = point_zorder_internal(p2);
+
+ if (z1 > z2)
+ return 1;
+ else if (z1 < z2)
+ return -1;
+ else
+ return 0;
+}
+
+/*
+ * Sort support routine for fast GiST index build by sorting.
+ */
+Datum
+gist_point_sortsupport(PG_FUNCTION_ARGS)
+{
+ SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
+
+ ssup->comparator = gist_bbox_fastcmp;
+ PG_RETURN_VOID();
+}
diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.c
index 0516059e3dd..9b589d22e0a 100644
--- a/src/backend/access/gist/gistutil.c
+++ b/src/backend/access/gist/gistutil.c
@@ -71,7 +71,7 @@ gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size f
deleted = IndexTupleSize(itup) + sizeof(ItemIdData);
}
- return (PageGetFreeSpace(page) + deleted < size);
+ return (PageGetFreeSpace(page) + deleted < size); // FIXME: shouldn't we use PageGetExactFreeSpace here?
}
bool
@@ -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,12 +573,31 @@ 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];
- int i;
IndexTuple res;
+ gistCompressValues(giststate, r, attdata, isnull, isleaf, compatt);
+
+ res = index_form_tuple(isleaf ? giststate->leafTupdesc :
+ giststate->nonLeafTupdesc,
+ compatt, isnull);
+
+ /*
+ * The offset number on tuples on internal pages is unused. For historical
+ * reasons, it is set to 0xffff.
+ */
+ ItemPointerSetOffsetNumber(&(res->t_tid), 0xffff);
+ return res;
+}
+
+void
+gistCompressValues(GISTSTATE *giststate, Relation r,
+ Datum *attdata, bool *isnull, bool isleaf, Datum *compatt)
+{
+ int i;
+
/*
* Call the compress method on each attribute.
*/
@@ -617,17 +637,6 @@ gistFormTuple(GISTSTATE *giststate, Relation r,
compatt[i] = attdata[i];
}
}
-
- res = index_form_tuple(isleaf ? giststate->leafTupdesc :
- giststate->nonLeafTupdesc,
- compatt, isnull);
-
- /*
- * The offset number on tuples on internal pages is unused. For historical
- * reasons, it is set to 0xffff.
- */
- ItemPointerSetOffsetNumber(&(res->t_tid), 0xffff);
- return res;
}
/*
@@ -745,14 +754,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 +768,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 2b9ab693be1..8a14620fab2 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/access/transam/xloginsert.c b/src/backend/access/transam/xloginsert.c
index c526bb19281..2300a6f5873 100644
--- a/src/backend/access/transam/xloginsert.c
+++ b/src/backend/access/transam/xloginsert.c
@@ -1019,6 +1019,63 @@ log_newpage(RelFileNode *rnode, ForkNumber forkNum, BlockNumber blkno,
return recptr;
}
+/*
+ * Like log_newpage(), but allow logging multiple pages in one operation.
+ * It is more efficient, because we cna write multiple pages in a single
+ * WAL record.
+ */
+void
+log_newpages(RelFileNode *rnode, ForkNumber forkNum, int num_pages,
+ BlockNumber *blknos, Page *pages, bool page_std)
+{
+ int flags;
+ XLogRecPtr recptr;
+ int i;
+ int j;
+
+ flags = REGBUF_FORCE_IMAGE;
+ if (page_std)
+ flags |= REGBUF_STANDARD;
+
+ /*
+ * Iterate over all the pages. They are collected into batches of
+ * XLR_MAX_BLOCK_ID pages, and a single WAL-record is written for each
+ * batch.
+ */
+ XLogEnsureRecordSpace(XLR_MAX_BLOCK_ID - 1, 0);
+
+ i = 0;
+ while (i < num_pages)
+ {
+ int batch_start = i;
+ int nbatch;
+
+ XLogBeginInsert();
+
+ nbatch = 0;
+ while (nbatch < XLR_MAX_BLOCK_ID && i < num_pages)
+ {
+ XLogRegisterBlock(nbatch, rnode, forkNum, blknos[i], pages[i], flags);
+ i++;
+ nbatch++;
+ }
+
+ recptr = XLogInsert(RM_XLOG_ID, XLOG_FPI);
+
+ for (j = batch_start; j < i; j++)
+ {
+ /*
+ * The page may be uninitialized. If so, we can't set the LSN because that
+ * would corrupt the page.
+ */
+ if (!PageIsNew(pages[j]))
+ {
+ PageSetLSN(pages[j], recptr);
+ }
+ }
+ }
+}
+
/*
* Write a WAL record containing a full image of a page.
*
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 3c49476483b..c5c7e5af056 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 4994351697c..4f6dae9a76b 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 02e985549f6..b68c01a5f24 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 void gistCompressValues(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/access/xloginsert.h b/src/include/access/xloginsert.h
index 63df25ae90f..674c376053e 100644
--- a/src/include/access/xloginsert.h
+++ b/src/include/access/xloginsert.h
@@ -54,6 +54,8 @@ extern bool XLogCheckBufferNeedsBackup(Buffer buffer);
extern XLogRecPtr log_newpage(RelFileNode *rnode, ForkNumber forkNum,
BlockNumber blk, char *page, bool page_std);
+extern void log_newpages(RelFileNode *rnode, ForkNumber forkNum, int num_pages,
+ BlockNumber *blknos, char **pages, bool page_std);
extern XLogRecPtr log_newpage_buffer(Buffer buffer, bool page_std);
extern void log_newpage_range(Relation rel, ForkNumber forkNum,
BlockNumber startblk, BlockNumber endblk, bool page_std);
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index 37b580883fc..a8e0c4ff8a5 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/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 687509ba926..96d7efd4270 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -8062,6 +8062,9 @@
proname => 'gist_poly_distance', prorettype => 'float8',
proargtypes => 'internal polygon int2 oid internal',
prosrc => 'gist_poly_distance' },
+{ oid => '3435', descr => 'sort support',
+ proname => 'gist_point_sortsupport', prorettype => 'void',
+ proargtypes => 'internal', prosrc => 'gist_point_sortsupport' },
# GIN array support
{ oid => '2743', descr => 'GIN array support',
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
index 9e76666fe94..f39f232aae9 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.20.1
