From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
To: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
Cc: Alexander Korotkov <aekorotkov@gmail.com>
Cc: Robert Haas <robertmhaas@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: WIP: Fast GiST index build
Date: Tue, 16 Aug 2011 22:15:15 +0300
Message-ID: <4E4AC1C3.4070003@enterprisedb.com> (raw)
In-Reply-To: <4E4AC0B9.8070203@enterprisedb.com>
References: <BANLkTikgOQ1+r=A9b08szNTeEWsk-cNMMg@mail.gmail.com>
<CAPpHfduAhSNo8LHMPj_pqQ_2W6ZDPzdQBPzHbnpqaKz6kf4nrw@mail.gmail.com>
<4E3977D8.1020506@enterprisedb.com>
<CAPpHfducs8Ussw+t8iP3WS3ZTuX2J-77FOY=jAZUg-K6AuOC0g@mail.gmail.com>
<CAPpHfdusd_b_dtvNY2uuJict6=VEUTGAS8ELXGck=o=kOdMnOw@mail.gmail.com>
<4E3FAB1D.1060105@enterprisedb.com>
<CAPpHfdsovwbgs30TojJc_zDsc+0ghapm+-AALfP58UaHiYjr2A@mail.gmail.com>
<CAPpHfdvi5WZKdRD+s60R+pdm8dLczRQ5_RYt4L8OA_bhorPjpg@mail.gmail.com>
<4E42DFCE.3050904@enterprisedb.com>
<CAPpHfdvhoYKUUCVaC-yFbDaE5j2QTa94cVgYuKnzX4xwWUjSTg@mail.gmail.com>
<CA+TgmoZoON6aAE3NB9=GF9oAdF=Kkz21+MmoE5P_kA9aKN-OQA@mail.gmail.com>
<CAPpHfdu4DusbHtMLE+csQJj61rMg_JtFOGSwrQVoOF5wPBkixQ@mail.gmail.com>
<CAPpHfdtMe6yizpbT+Lsx0mWSW9thPV9KosSrUsSEMNRBHUWUPw@mail.gmail.com>
<4E4AAC49.7070401@enterprisedb.com>
<CAPpHfduTY5FqYdA_AB2zQ5MYyaeEqc5fRLLPgGBOymDXu16gFQ@mail.gmail.com>
<4E4AC0B9.8070203@enterprisedb.com>
On 16.08.2011 22:10, Heikki Linnakangas wrote:
> Here's an version of the patch with a bunch of minor changes:
And here it really is, this time with an attachment...
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.comAttachments:gist_fast_build-heikki-0.14.1.1.patch (text/x-diff, 84.7K) downloaddiff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgmlindex 78171cf..244a2e2 100644--- a/doc/src/sgml/gist.sgml+++ b/doc/src/sgml/gist.sgml@@ -642,6 +642,35 @@ my_distance(PG_FUNCTION_ARGS)
</variablelist>
+ <sect2 id="gist-buffering-build">+ <title>GiST buffering build</title>+ <para>+ Building large GiST indexes that don't fit in cache by simply inserting+ all the tuples tends to be slow, because if the index tuples are scattered+ across the index, a large fraction of the insertions need to perform+ I/O. The exception is well-ordered datasets, where the part of the index+ where new insertions go to stays well cached.+ PostgreSQL from version 9.2 supports a more efficient method to build+ GiST indexes based on buffering, which can dramatically reduce number of+ random I/O needed.+ </para>++ <para>+ However, buffering index build needs to call the <function>penalty</>+ function more often, which consumes some extra CPU resources. Also, it can+ infuence the quality of the produced index, in both positive and negative+ directions. That influence depends on various factors, like the+ distribution of the input data and operator class implementation.+ </para>++ <para>+ By default, the index build switches to the buffering method when the+ index size reaches <xref linkend="guc-effective-cache-size">. It can+ be manually turned on or off by the <literal>BUFFERING</literal> parameter+ to the CREATE INDEX clause.+ </para>++ </sect2>
</sect1>
<sect1 id="gist-examples">
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgmlindex 1a1e8d6..1032c94 100644--- a/doc/src/sgml/ref/create_index.sgml+++ b/doc/src/sgml/ref/create_index.sgml@@ -341,6 +341,26 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
</varlistentry>
</variablelist>
+ <para>+ GiST indexes additionaly accepts parameters:+ </para>++ <variablelist>++ <varlistentry>+ <term><literal>BUFFERING</></term>+ <listitem>+ <para>+ Determines whether the buffering build technique described in+ <xref linkend="gist-buffering-build"> is used to build the index. With+ <literal>OFF</> it is disabled, with <literal>ON</> it is enabled, and+ with <literal>AUTO</> (default) it is initially disabled, but turned on+ on-the-fly once the index size reaches <xref linkend="guc-effective-cache-size">.+ </para>+ </listitem>+ </varlistentry>++ </variablelist>
</refsect2>
<refsect2 id="SQL-CREATEINDEX-CONCURRENTLY">
diff --git a/src/backend/access/common/reloptions.c b/src/backend/access/common/reloptions.cindex 900b222..4514818 100644--- a/src/backend/access/common/reloptions.c+++ b/src/backend/access/common/reloptions.c@@ -30,6 +30,9 @@
#include "utils/memutils.h"
#include "utils/rel.h"
++static void validateBufferingOption(char *value);+
/*
* Contents of pg_class.reloptions
*
@@ -219,6 +222,17 @@ static relopt_real realRelOpts[] =
static relopt_string stringRelOpts[] =
{
+ {+ {+ "buffering",+ "Enables buffering build for this GiST index",+ RELOPT_KIND_GIST+ },+ 4,+ false,+ validateBufferingOption,+ "auto"+ },
/* list terminator */
{{NULL}}
};
@@ -1267,3 +1281,24 @@ tablespace_reloptions(Datum reloptions, bool validate)
return (bytea *) tsopts;
}
++/*+ * Validator for "buffering" option of GiST indexed. Allows only "on", "off" and+ * "auto" values.+ */+static void+validateBufferingOption(char *value)+{+ if (!value ||+ (+ strcmp(value, "on") &&+ strcmp(value, "off") &&+ strcmp(value, "auto")+ )+ )+ {+ ereport(ERROR,+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),+ errmsg("Only \"on\", \"off\" and \"auto\" values are available for \"buffering\" option.")));+ }+}diff --git a/src/backend/access/gist/Makefile b/src/backend/access/gist/Makefileindex f8051a2..cc9468f 100644--- a/src/backend/access/gist/Makefile+++ b/src/backend/access/gist/Makefile@@ -13,6 +13,6 @@ top_builddir = ../../../..
include $(top_builddir)/src/Makefile.global
OBJS = gist.o gistutil.o gistxlog.o gistvacuum.o gistget.o gistscan.o \
- gistproc.o gistsplit.o+ gistproc.o gistsplit.o gistbuild.o gistbuildbuffers.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/access/gist/README b/src/backend/access/gist/READMEindex 2d78dcb..7cbd1e3 100644--- a/src/backend/access/gist/README+++ b/src/backend/access/gist/README@@ -24,6 +24,7 @@ The current implementation of GiST supports:
* provides NULL-safe interface to GiST core
* Concurrency
* Recovery support via WAL logging
+ * Buffering build algorithm
The support for concurrency implemented in PostgreSQL was developed based on
the paper "Access Methods for Next-Generation Database Systems" by
@@ -31,6 +32,12 @@ Marcel Kornaker:
http://www.sai.msu.su/~megera/postgres/gist/papers/concurrency/access-methods-for-next-generation.pdf.gz
+Buffering build algorithm for GiST was developed based on the paper "Efficient+Bulk Operations on Dynamic R-trees" by Lars Arge, Klaus Hinrichs, Jan Vahrenhold+and Jeffrey Scott Vitter.++ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.9894&rep=rep1&type=pdf+
The original algorithms were modified in several ways:
* They had to be adapted to PostgreSQL conventions. For example, the SEARCH
@@ -278,6 +285,134 @@ would complicate the insertion algorithm. So when an insertion sees a page
with F_FOLLOW_RIGHT set, it immediately tries to bring the split that
crashed in the middle to completion by adding the downlink in the parent.
+Buffering build algorithm+-------------------------++In the buffering index build algorithm, some or all internal nodes have a+buffer attached to them. When a tuple is inserted at the top, the descend down+the tree is stopped as soon as a buffer is reached, and the tuple is pushed to+the buffer. When a buffer gets too full, all the tuples in it are flushed to+the lower level, where they again hit lower level buffers or leaf pages. This+makes the insertions happen in more of a breadth-first than depth-first order,+which greatly reduces the amount of random I/O required.++In the algorithm, levels are numbered so that leaf pages have level zero,+and internal node levels count up from 1. This numbering ensures that a page's+level number never changes, even when the root page is split.++Level Tree++3 *+ / \+2 * *+ / | \ / | \+1 * * * * * *+ / \ / \ / \ / \ / \ / \+0 o o o o o o o o o o o o++* - internal page+o - leaf page++Internal pages that belong to certain levels have buffers associated with+them. Leaf pages never have buffers. Which levels have buffers is controlled+by "level step" parameter: level numbers that are multiples of level_step+have buffers, while others do not. For example, if level_step = 2, then+pages on levels 2, 4, 6, ... have buffers. If level_step = 1 then every+internal page has a buffer.++Level Tree (level_step = 1) Tree (level_step = 2) + +3 *(b) *+ / \ / \+2 *(b) *(b) *(b) *(b)+ / | \ / | \ / | \ / | \+1 *(b) *(b) *(b) *(b) *(b) *(b) * * * * * *+ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \+0 o o o o o o o o o o o o o o o o o o o o o o o o++(b) - buffer++Logically, a buffer is just bunch of tuples. Physically, it is divided in+pages, backed by a temporary file. Each buffer can be in one of two states:+a) Last page of the buffer is kept in main memory. A node buffer is+automatically switched to this state when a new index tuple is added to it,+or a tuple is removed from it.+b) All pages of the buffer are swapped out to disk. When a buffer becomes too+full, and we start to flush it, all other buffers are switched to this state.++When an index tuple is inserted, its initial processing can end in one of the+following points:+1) Leaf page, if the depth of the index <= level_step, meaning that+ none of the internal pages have buffers associated with them.+2) Buffer of topmost level page that has buffers.++New index tuples are processed until one of the buffers in the topmost+buffered level becomes half-full. When a buffer becomes half-full, it's added+to the emptying queue, and will be emptied before a new tuple is processed.++Buffer emptying process means that index tuples from the buffer are moved+into buffers at a lower level, or leaf pages. First, all the other buffers are+swapped to disk to free up the memory. Then tuples are popped from the buffer+one by one, and cascaded down the tree to the next buffer or leaf page below+the buffered node.++Emptying a buffer has the interesting dynamic property that any intermediate+pages between the buffer being emptied, and the next buffered or leaf level+below it, become cached. If there are no more buffers below the node, the leaf+pages where the tuples finally land on get cached too. If there are, the last+buffer page of each buffer below is kept in memory. This is illustrated in+the figures below:++ Buffer being emptied to+ lower-level buffers Buffer being emptied to leaf pages++ +(fb) +(fb)+ / \ / \+ + + + ++ / \ / \ / \ / \+ *(ab) *(ab) *(ab) *(ab) x x x x+++ - cached internal page+x - cached leaf page+* - non-cached internal page+(fb) - buffer being emptied+(ab) - buffers being appended to, with last page in memory++In the beginning of the index build, the level-step is chosen so that all those+pages involved in emptying one buffer fit in cache, so after each of those+pages have been accessed once and cached, emptying a buffer doesn't involve+any more I/O. This locality is where the speedup of the buffering algorithm+comes from.++Emptying one buffer can fill up one or more of the lower-level buffers,+triggering emptying of them as well. Whenever a buffer becomes too full, it's+added to the emptying queue, and will be emptied after the current buffer has+been processed.++To keep the size of each buffer limited even in the worst case, buffer emptying+is scheduled as soon as a buffer becomes half-full, and emptying it continues+until 1/2 of the nominal buffer size worth of tuples has been emptied. This+guarantees that when buffer emptying begins, all the lower-level buffers+are at most half-full. In the worst case that all the tuples are cascaded down+to the same lower-level buffer, that buffer therefore has enough space to+accommodate all the tuples emptied from the upper-level buffer. There is no+hard size limit in any of the data structures used, though, so this only needs+to be approximate; small overfilling of some buffers doesn't matter.++If an internal page that has a buffer associated with it is split, the buffer+needs to be split too. All tuples in the buffer are scanned through and+relocated to the correct sibling buffers, using the penalty function to decide+which buffer each tuple should go to.++After all tuples from the heap have been processed, there are still some index+tuples in the buffers. At this point, final buffer emptying starts. All buffers+are emptied in top-down order. This is slightly complicated by the fact that+new buffers can be allocated during the emptying, due to page splits. However,+the new buffers will always be siblings of buffers that haven't been fully+emptied yet; tuples never move upwards in the tree. The final emptying loops+through buffers at a given level until all buffers at that level have been+emptied, and then moves down to the next level.+
Authors:
Teodor Sigaev <teodor@sigaev.ru>
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.cindex 4fc7a21..b140e0c 100644--- a/src/backend/access/gist/gist.c+++ b/src/backend/access/gist/gist.c@@ -24,15 +24,6 @@
#include "utils/memutils.h"
#include "utils/rel.h"
-/* Working state for gistbuild and its callback */-typedef struct-{- GISTSTATE giststate;- int numindexattrs;- double indtuples;- MemoryContext tmpCtx;-} GISTBuildState;-
/* A List of these is used represent a split-in-progress. */
typedef struct
{
@@ -41,16 +32,6 @@ typedef struct
} GISTPageSplitInfo;
/* non-export function prototypes */
-static void gistbuildCallback(Relation index,- HeapTuple htup,- Datum *values,- bool *isnull,- bool tupleIsAlive,- void *state);-static void gistdoinsert(Relation r,- IndexTuple itup,- Size freespace,- GISTSTATE *GISTstate);
static void gistfixsplit(GISTInsertState *state, GISTSTATE *giststate);
static bool gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
GISTSTATE *giststate,
@@ -89,138 +70,6 @@ createTempGistContext(void)
}
/*
- * Routine to build an index. Basically calls insert over and over.- *- * XXX: it would be nice to implement some sort of bulk-loading- * algorithm, but it is not clear how to do that.- */-Datum-gistbuild(PG_FUNCTION_ARGS)-{- Relation heap = (Relation) PG_GETARG_POINTER(0);- Relation index = (Relation) PG_GETARG_POINTER(1);- IndexInfo *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);- IndexBuildResult *result;- double reltuples;- GISTBuildState buildstate;- Buffer buffer;- Page page;-- /*- * 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));-- /* no locking is needed */- initGISTstate(&buildstate.giststate, index);-- /* 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);-- if (RelationNeedsWAL(index))- {- XLogRecPtr recptr;- XLogRecData rdata;-- rdata.data = (char *) &(index->rd_node);- rdata.len = sizeof(RelFileNode);- rdata.buffer = InvalidBuffer;- rdata.next = NULL;-- recptr = XLogInsert(RM_GIST_ID, XLOG_GIST_CREATE_INDEX, &rdata);- PageSetLSN(page, recptr);- PageSetTLI(page, ThisTimeLineID);- }- else- PageSetLSN(page, GetXLogRecPtrForTemp());-- UnlockReleaseBuffer(buffer);-- END_CRIT_SECTION();-- /* build the index */- buildstate.numindexattrs = indexInfo->ii_NumIndexAttrs;- buildstate.indtuples = 0;-- /*- * create a temporary memory context that is reset once for each tuple- * inserted into the index- */- buildstate.tmpCtx = createTempGistContext();-- /* do the heap scan */- reltuples = IndexBuildHeapScan(heap, index, indexInfo, true,- gistbuildCallback, (void *) &buildstate);-- /* okay, all heap tuples are indexed */- MemoryContextDelete(buildstate.tmpCtx);-- freeGISTstate(&buildstate.giststate);-- /*- * Return statistics- */- result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));-- result->heap_tuples = reltuples;- result->index_tuples = buildstate.indtuples;-- PG_RETURN_POINTER(result);-}--/*- * Per-tuple callback from IndexBuildHeapScan- */-static void-gistbuildCallback(Relation index,- HeapTuple htup,- Datum *values,- bool *isnull,- bool tupleIsAlive,- void *state)-{- GISTBuildState *buildstate = (GISTBuildState *) state;- IndexTuple itup;- MemoryContext oldCtx;-- oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);-- /* form an index tuple and point it at the heap tuple */- itup = gistFormTuple(&buildstate->giststate, index,- values, isnull, true /* size is currently bogus */ );- itup->t_tid = htup->t_self;-- /*- * Since we already have the index relation locked, we call gistdoinsert- * directly. Normal access method calls dispatch through gistinsert,- * which locks the relation for write. This is the right thing to do if- * you're inserting single tups, but not when you're initializing the- * whole index at once.- *- * In this path we respect the fillfactor setting, whereas insertions- * after initial build do not.- */- gistdoinsert(index, itup,- RelationGetTargetPageFreeSpace(index, GIST_DEFAULT_FILLFACTOR),- &buildstate->giststate);-- buildstate->indtuples += 1;- MemoryContextSwitchTo(oldCtx);- MemoryContextReset(buildstate->tmpCtx);-}--/*
* gistbuildempty() -- build an empty gist index in the initialization fork
*/
Datum
@@ -275,7 +124,6 @@ gistinsert(PG_FUNCTION_ARGS)
PG_RETURN_BOOL(false);
}
-
/*
* Place tuples from 'itup' to 'buffer'. If 'oldoffnum' is valid, the tuple
* at that offset is atomically removed along with inserting the new tuples.
@@ -293,19 +141,27 @@ gistinsert(PG_FUNCTION_ARGS)
* In that case, we continue to hold the root page locked, and the child
* pages are released; note that new tuple(s) are *not* on the root page
* but in one of the new child pages.
+ *+ * Also this function have some special behaviour in buffering build. It takes+ * care about maintaining data structured of buffering build: creates new+ * root path item if needed and relocates buffer of splitted node. Also it+ * doesn't returns splitinfo to the caller but uses simplified downlinks+ * insertion by recursive call.
*/
-static bool+bool
gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
Buffer buffer,
IndexTuple *itup, int ntup, OffsetNumber oldoffnum,
Buffer leftchildbuf,
- List **splitinfo)+ List **splitinfo,+ GISTBufferingInsertStack * path)
{
Page page = BufferGetPage(buffer);
bool is_leaf = (GistPageIsLeaf(page)) ? true : false;
XLogRecPtr recptr;
int i;
bool is_split;
+ GISTBuildBuffers *gfbb = giststate->gfbb;
/*
* Refuse to modify a page that's incompletely split. This should not
@@ -319,7 +175,14 @@ gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
if (GistFollowRight(page))
elog(ERROR, "concurrent GiST page split was incomplete");
- *splitinfo = NIL;+ if (!gfbb)+ {+ /*+ * We haven't to return splitinfo in buffering build. Otherwise+ * initialize splitinfo as empty list.+ */+ *splitinfo = NIL;+ }
/*
* if isupdate, remove old key: This node's key has been modified, either
@@ -408,6 +271,24 @@ gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
GistTupleSetValid(ptr->itup);
}
+ /* Are we inside a buffering build? */+ if (gfbb)+ {+ /*+ * Parent may be changed from the moment we set it. So, let us+ * adjust the parent.+ */+ if (!is_rootsplit)+ gistBufferingFindCorrectParent(giststate, state->r, path);++ /*+ * Relocate index tuples from buffer of splitted page between+ * buffers of the pages produced by split.+ */+ gistRelocateBuildBuffersOnSplit(giststate->gfbb, giststate, state->r,+ path, buffer, dist);+ }+
/*
* If this is a root split, we construct the new root page with the
* downlinks here directly, instead of requiring the caller to insert
@@ -439,9 +320,12 @@ gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
rootpg.next = dist;
dist = &rootpg;
}
- else+ else if (!gfbb)
{
- /* Prepare split-info to be returned to caller */+ /*+ * If we're not in buffering build then prepare split-info to be+ * returned to caller.+ */
for (ptr = dist; ptr; ptr = ptr->next)
{
GISTPageSplitInfo *si = palloc(sizeof(GISTPageSplitInfo));
@@ -474,7 +358,7 @@ gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
else
GistPageGetOpaque(ptr->page)->rightlink = oldrlink;
- if (ptr->next && !is_rootsplit)+ if (ptr->next && !is_rootsplit && !gfbb)
GistMarkFollowRight(ptr->page);
else
GistClearFollowRight(ptr->page);
@@ -508,7 +392,8 @@ gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
/* Write the WAL record */
if (RelationNeedsWAL(state->r))
recptr = gistXLogSplit(state->r->rd_node, blkno, is_leaf,
- dist, oldrlink, oldnsn, leftchildbuf);+ dist, oldrlink, oldnsn, leftchildbuf,+ gfbb ? true : false);
else
recptr = GetXLogRecPtrForTemp();
@@ -524,12 +409,51 @@ gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
* If this was a root split, we've already inserted the downlink
* pointers, in the form of a new root page. Therefore we can release
* all the new buffers, and keep just the root page locked.
+ *+ * In buffering build due to no concurrent activity, we can use+ * simplified downlinks insertion. So in that case we also can release+ * all the new buffers.
*/
- if (is_rootsplit)+ if (is_rootsplit || gfbb)
{
for (ptr = dist->next; ptr; ptr = ptr->next)
UnlockReleaseBuffer(ptr->buffer);
}
++ if (gfbb && !is_rootsplit)+ {+ /*+ * Simplified insertion of downlinks during buffering build.+ */+ IndexTuple *itups;+ int cnt = 0,+ i;+ Buffer parentBuffer;++ /* Count number of downlinks for insert. */+ for (ptr = dist; ptr; ptr = ptr->next)+ {+ cnt++;+ }++ /* Allocate array of downlinks index tuples */+ itups = (IndexTuple *) palloc(sizeof(IndexTuple) * cnt);++ /* Fill that array */+ i = 0;+ for (ptr = dist; ptr; ptr = ptr->next)+ {+ itups[i] = ptr->itup;+ i++;+ }++ /* Insert downlinks into parent. */+ parentBuffer = ReadBuffer(state->r, path->parent->blkno);+ LockBuffer(parentBuffer, GIST_EXCLUSIVE);+ gistplacetopage(state, giststate, parentBuffer,+ itups, cnt, path->downlinkoffnum, InvalidBuffer, NULL, path->parent);+ UnlockReleaseBuffer(parentBuffer);+ }
}
else
{
@@ -570,8 +494,6 @@ gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
recptr = GetXLogRecPtrForTemp();
PageSetLSN(page, recptr);
}
-- *splitinfo = NIL;
}
/*
@@ -608,7 +530,7 @@ gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,
* this routine assumes it is invoked in a short-lived memory context,
* so it does not bother releasing palloc'd allocations.
*/
-static void+void
gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate)
{
ItemId iid;
@@ -917,8 +839,8 @@ gistFindPath(Relation r, BlockNumber child, OffsetNumber *downlinkoffnum)
{
/*
* Page was split while we looked elsewhere. We didn't see the
- * downlink to the right page when we scanned the parent, so- * add it to the queue now.+ * downlink to the right page when we scanned the parent, so add+ * it to the queue now.
*
* Put the right page ahead of the queue, so that we visit it
* next. That's important, because if this is the lowest internal
@@ -1195,7 +1117,7 @@ gistinserttuples(GISTInsertState *state, GISTInsertStack *stack,
is_split = gistplacetopage(state, giststate, stack->buffer,
tuples, ntup, oldoffnum,
leftchild,
- &splitinfo);+ &splitinfo, NULL);
if (splitinfo)
gistfinishsplit(state, stack, giststate, splitinfo);
@@ -1414,6 +1336,7 @@ initGISTstate(GISTSTATE *giststate, Relation index)
else
giststate->supportCollation[i] = DEFAULT_COLLATION_OID;
}
+ giststate->gfbb = NULL;
}
void
diff --git a/src/backend/access/gist/gistbuild.c b/src/backend/access/gist/gistbuild.cnew file mode 100644index 0000000..e0a0763--- /dev/null+++ b/src/backend/access/gist/gistbuild.c@@ -0,0 +1,929 @@+/*-------------------------------------------------------------------------+ *+ * gistbuild.c+ * build algorithm for GiST indexes implementation.+ *+ *+ * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group+ * Portions Copyright (c) 1994, Regents of the University of California+ *+ * IDENTIFICATION+ * src/backend/access/gist/gistbuild.c+ *+ *-------------------------------------------------------------------------+ */+#include "postgres.h"++#include "access/genam.h"+#include "access/gist_private.h"+#include "catalog/index.h"+#include "catalog/pg_collation.h"+#include "miscadmin.h"+#include "optimizer/cost.h"+#include "storage/bufmgr.h"+#include "storage/indexfsm.h"+#include "storage/smgr.h"+#include "utils/memutils.h"+#include "utils/rel.h"++/* Step of index tuples for check whether to switch to buffering build mode */+#define BUFFERING_MODE_SWITCH_CHECK_STEP 256+#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET 4096++typedef enum+{+ GIST_BUFFERING_DISABLED, /* in regular build mode and aren't going to+ * switch */+ GIST_BUFFERING_AUTO, /* in regular build mode, but will switch to+ * buffering build mode if the index grows+ * too big */+ GIST_BUFFERING_STATS, /* gathering statistics of index tuple size+ * before switching to the buffering build+ * mode */+ GIST_BUFFERING_ACTIVE /* in buffering build mode */+} GistBufferingMode;++/* Working state for gistbuild and its callback */+typedef struct+{+ GISTSTATE giststate;+ int64 indtuples;+ int64 indtuplesSize;++ Size freespace; /* Amount of free space to leave on pages */++ GistBufferingMode bufferingMode;+ MemoryContext tmpCtx;+} GISTBuildState;++static void gistFreeUnreferencedPath(GISTBufferingInsertStack *path);+static bool gistProcessItup(GISTSTATE *giststate, GISTInsertState *state,+ GISTBuildBuffers *gfbb, IndexTuple itup,+ GISTBufferingInsertStack *startparent);+static void gistProcessEmptyingStack(GISTSTATE *giststate, GISTInsertState *state);+static void gistBufferingBuildInsert(Relation index, IndexTuple itup,+ GISTBuildState *buildstate);+static void gistBuildCallback(Relation index,+ HeapTuple htup,+ Datum *values,+ bool *isnull,+ bool tupleIsAlive,+ void *state);+static int gistGetMaxLevel(Relation index);+static bool gistInitBuffering(GISTBuildState *buildstate, Relation index);+static int calculatePagesPerBuffer(GISTBuildState *buildstate, Relation index,+ int levelStep);++/*+ * Free unreferenced parts of path;+ */+static void+gistFreeUnreferencedPath(GISTBufferingInsertStack *path)+{+ while (path->refCount == 0)+ {+ /*+ * Path part is unreferenced. We can free it and decrease reference+ * count of parent. If parent becomes unreferenced too procedure+ * should be repeated for it.+ */+ GISTBufferingInsertStack *tmp = path->parent;++ pfree(path);+ path = tmp;+ if (path)+ path->refCount--;+ else+ break;+ }+}++/*+ * Decrease reference count of path part and remove unreferenced path parts if+ * any.+ */+void+gistDecreasePathRefcount(GISTBufferingInsertStack *path)+{+ path->refCount--;+ gistFreeUnreferencedPath(path);+}++/*+ * Process index tuple. Run index tuple down until it meet leaf page or+ * node buffer. If it meets a node buffer then it is just placed to it. If it+ * meet leaf page then actual insert takes place. Returns true if we have to+ * stop buffer emptying process (one of child buffers can't take index+ * tuples anymore).+ */+static bool+gistProcessItup(GISTSTATE *giststate, GISTInsertState *state,+ GISTBuildBuffers *gfbb, IndexTuple itup,+ GISTBufferingInsertStack *startparent)+{+ GISTBufferingInsertStack *path;+ BlockNumber childblkno;+ Buffer buffer;+ bool result = false;++ /*+ * NULL passed in startparent means that we start index tuple processing+ * from the root.+ */+ if (!startparent)+ path = gfbb->rootitem;+ else+ path = startparent;++ /*+ * Loop until we are on leaf page (level == 0) or we reach level with+ * buffers (if it wasn't level that we've start at, because we should move+ * forward at least in one level down).+ */+ for (;;)+ {+ ItemId iid;+ IndexTuple idxtuple,+ newtup;+ Page page;+ OffsetNumber childoffnum;+ GISTBufferingInsertStack *parent;++ /*+ * Do we meet a level with buffers? Surely buffer of page we start+ * from doesn't matter.+ */+ if (path != startparent && LEVEL_HAS_BUFFERS(path->level, gfbb))+ break;++ /* Do we meet leaf page? */+ if (path->level == 0)+ break;++ /* Choose child for insertion */+ buffer = ReadBuffer(state->r, path->blkno);+ LockBuffer(buffer, GIST_EXCLUSIVE);++ page = (Page) BufferGetPage(buffer);+ childoffnum = gistchoose(state->r, page, itup, giststate);+ iid = PageGetItemId(page, childoffnum);+ idxtuple = (IndexTuple) PageGetItem(page, iid);+ childblkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));++ /* Adjust key representing child if needed */+ newtup = gistgetadjusted(state->r, idxtuple, itup, giststate);++ if (newtup)+ {+ /*+ * Key adjustment was actually produced a new key. So, we need to+ * update it in the page.+ */+ gistplacetopage(state, giststate, buffer, &newtup, 1, childoffnum,+ InvalidBuffer, NULL, path);+ }+ UnlockReleaseBuffer(buffer);++ /* Create new path item representing current page */+ parent = path;+ path = (GISTBufferingInsertStack *) MemoryContextAlloc(gfbb->context,+ sizeof(GISTBufferingInsertStack));+ path->parent = parent;+ path->level = parent->level - 1;+ path->blkno = childblkno;+ path->downlinkoffnum = childoffnum;++ /* It's unreferenced just now */+ path->refCount = 0;++ /* Adjust reference count of parent */+ if (parent)+ parent->refCount++;+ }++ if (LEVEL_HAS_BUFFERS(path->level, gfbb))+ {+ /*+ * We've reached level with buffers. Now place index tuple to the+ * buffer and add buffer emptying stack element if buffer overflows.+ */+ GISTNodeBuffer *childNodeBuffer;++ /* Find node buffer or create a new one */+ childNodeBuffer = gistGetNodeBuffer(gfbb, giststate, path->blkno,+ path->downlinkoffnum, path->parent,+ true);++ /* Add index tuple to it */+ gistPushItupToNodeBuffer(gfbb, childNodeBuffer, itup);++ if (BUFFER_HALF_FILLED(childNodeBuffer, gfbb) && !childNodeBuffer->queuedForEmptying)+ {+ /*+ * Node buffer was overflowed just now. Let's add it to the+ * emptying stack.+ */+ MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context);+ childNodeBuffer->queuedForEmptying = true;+ gfbb->bufferEmptyingQueue = lcons(childNodeBuffer,+ gfbb->bufferEmptyingQueue);+ MemoryContextSwitchTo(oldcxt);+ }++ if (BUFFER_OVERFLOWED(childNodeBuffer, gfbb))+ result = true;+ }+ else+ {+ /*+ * We've reached leaf level. So, place index tuple here.+ */+ buffer = ReadBuffer(state->r, path->blkno);+ LockBuffer(buffer, GIST_EXCLUSIVE);+ gistplacetopage(state, giststate, buffer, &itup, 1,+ InvalidOffsetNumber, InvalidBuffer, NULL, path);+ UnlockReleaseBuffer(buffer);+ }++ /*+ * Free unreferenced path items if any. Path item may be referenced by+ * node buffer.+ */+ gistFreeUnreferencedPath(path);++ return result;+}+++/*+ * Find correct parent by following rightlinks in buffering index build. This+ * method of parent searching is possible because no concurrent activity is+ * possible while index builds.+ */+void+gistBufferingFindCorrectParent(GISTSTATE *giststate, Relation r,+ GISTBufferingInsertStack *child)+{+ GISTBuildBuffers *gfbb = giststate->gfbb;+ GISTBufferingInsertStack *parent = child->parent;+ OffsetNumber i,+ maxoff;+ ItemId iid;+ IndexTuple idxtuple;+ Buffer buffer;+ Page page;+ bool copied = false;++ buffer = ReadBuffer(r, parent->blkno);+ page = BufferGetPage(buffer);+ LockBuffer(buffer, GIST_EXCLUSIVE);+ gistcheckpage(r, buffer);++ /* Check if it was not moved */+ if (child->downlinkoffnum != InvalidOffsetNumber)+ {+ iid = PageGetItemId(page, child->downlinkoffnum);+ idxtuple = (IndexTuple) PageGetItem(page, iid);+ if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)+ {+ /* Still there */+ UnlockReleaseBuffer(buffer);+ return;+ }+ }++ /* parent is changed, look child in right links until found */+ while (true)+ {+ /* Search for relevant downlink in the current page */+ maxoff = PageGetMaxOffsetNumber(page);+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))+ {+ iid = PageGetItemId(page, i);+ idxtuple = (IndexTuple) PageGetItem(page, iid);+ if (ItemPointerGetBlockNumber(&(idxtuple->t_tid)) == child->blkno)+ {+ /* yes!!, found */+ child->downlinkoffnum = i;+ UnlockReleaseBuffer(buffer);+ return;+ }+ }++ /*+ * We should copy parent path item because some other path items can+ * refer to it.+ */+ if (!copied)+ {+ parent = (GISTBufferingInsertStack *) MemoryContextAlloc(gfbb->context,+ sizeof(GISTBufferingInsertStack));+ memcpy(parent, child->parent, sizeof(GISTBufferingInsertStack));+ if (parent->parent)+ parent->parent->refCount++;+ gistDecreasePathRefcount(child->parent);+ child->parent = parent;+ parent->refCount = 1;+ copied = true;+ }++ /*+ * Not found in current page. Move towards rightlink.+ */+ parent->blkno = GistPageGetOpaque(page)->rightlink;+ UnlockReleaseBuffer(buffer);++ if (parent->blkno == InvalidBlockNumber)+ {+ /*+ * End of chain and still didn't find parent. Should not happen+ * during index build.+ */+ break;+ }++ /* Get the next page */+ buffer = ReadBuffer(r, parent->blkno);+ page = BufferGetPage(buffer);+ LockBuffer(buffer, GIST_EXCLUSIVE);+ gistcheckpage(r, buffer);+ }++ elog(ERROR, "failed to re-find parent for block %u", child->blkno);+}++/*+ * Process buffers emptying stack. Emptying of one buffer can cause emptying+ * of other buffers. This function iterates until this cascading emptying+ * process finished, e.g. until buffers emptying stack is empty.+ */+static void+gistProcessEmptyingStack(GISTSTATE *giststate, GISTInsertState *state)+{+ GISTBuildBuffers *gfbb = giststate->gfbb;++ /* Iterate while we have elements in buffers emptying stack. */+ while (gfbb->bufferEmptyingQueue != NIL)+ {+ GISTNodeBuffer *emptyingNodeBuffer;++ /* Get node buffer from emptying stack. */+ emptyingNodeBuffer = (GISTNodeBuffer *) linitial(gfbb->bufferEmptyingQueue);+ gfbb->bufferEmptyingQueue = list_delete_first(gfbb->bufferEmptyingQueue);+ emptyingNodeBuffer->queuedForEmptying = false;++ /*+ * We are going to load last pages of buffers where emptying will be+ * to. So let's unload any previously loaded buffers.+ */+ gistUnloadNodeBuffers(gfbb);++ /* Variables for split of current emptying buffer detection. */+ gfbb->currentEmptyingBufferSplit = false;+ gfbb->currentEmptyingBufferBlockNumber = emptyingNodeBuffer->nodeBlocknum;++ while (true)+ {+ IndexTuple itup;++ /* Get the next one index tuple from node buffer */+ if (!gistPopItupFromNodeBuffer(gfbb, emptyingNodeBuffer, &itup))+ break;++ /* Run it down to the underlying node buffer or leaf page */+ if (gistProcessItup(giststate, state, gfbb, itup, emptyingNodeBuffer->path))+ break;++ /* Free all the memory allocated during index tuple processing */+ MemoryContextReset(CurrentMemoryContext);++ /*+ * If current emptying node buffer split we should stop emptying+ * just because there is no such node buffer anymore.+ */+ if (gfbb->currentEmptyingBufferSplit)+ break;+ }+ }+}++/*+ * Insert function for buffering index build.+ */+static void+gistBufferingBuildInsert(Relation index, IndexTuple itup,+ GISTBuildState *buildstate)+{+ GISTBuildBuffers *gfbb = buildstate->giststate.gfbb;+ GISTInsertState insertstate;++ memset(&insertstate, 0, sizeof(GISTInsertState));+ insertstate.freespace = buildstate->freespace;+ insertstate.r = index;++ /* We are ready for index tuple processing */+ gistProcessItup(&buildstate->giststate, &insertstate, gfbb, itup, NULL);++ /* Process buffer emptying stack if any */+ gistProcessEmptyingStack(&buildstate->giststate, &insertstate);+}++/*+ * Per-tuple callback from IndexBuildHeapScan.+ */+static void+gistBuildCallback(Relation index,+ HeapTuple htup,+ Datum *values,+ bool *isnull,+ bool tupleIsAlive,+ void *state)+{+ GISTBuildState *buildstate = (GISTBuildState *) state;+ IndexTuple itup;+ MemoryContext oldCtx;++ oldCtx = MemoryContextSwitchTo(buildstate->tmpCtx);++ /* form an index tuple and point it at the heap tuple */+ itup = gistFormTuple(&buildstate->giststate, index, values, isnull, true);+ itup->t_tid = htup->t_self;++ if (buildstate->bufferingMode == GIST_BUFFERING_ACTIVE)+ {+ /* We have buffers, so use them. */+ gistBufferingBuildInsert(index, itup, buildstate);+ }+ else+ {+ /*+ * There's no buffers (yet). Since we already have the index relation+ * locked, we call gistdoinsert directly.+ *+ * In this path we respect the fillfactor setting, whereas insertions+ * after initial build do not.+ */+ gistdoinsert(index, itup, buildstate->freespace,+ &buildstate->giststate);+ }++ /* Increase statistics of index tuples count and their summary size. */+ buildstate->indtuples += 1;+ buildstate->indtuplesSize += IndexTupleSize(itup);++ MemoryContextSwitchTo(oldCtx);+ MemoryContextReset(buildstate->tmpCtx);++ if (buildstate->bufferingMode == GIST_BUFFERING_ACTIVE &&+ buildstate->indtuples % BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET == 0)+ {+ /* We've to adjust buffers size now */+ buildstate->giststate.gfbb->pagesPerBuffer =+ calculatePagesPerBuffer(buildstate, index,+ buildstate->giststate.gfbb->levelStep);+ }++ /*+ * For automatic switching to buffering mode, check whether index fits to+ * effective cache. We call smgrnblocks only each+ * BUFFERING_MODE_SWITCH_CHECK_STEP index tuples because frequent+ * smgrnblocks calls can be expensive.+ */+ if ((buildstate->bufferingMode == 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->indtuples >= BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET))+ {+ /*+ * Index doesn't fit to effective cache anymore. Trying to switch to+ * buffering build mode.+ */+ if (gistInitBuffering(buildstate, index))+ {+ /*+ * Buffering build is successfully initialized. Now we can set+ * appropriate flag.+ */+ buildstate->bufferingMode = GIST_BUFFERING_ACTIVE;+ }+ else+ {+ /*+ * Failed to switch to buffering build due to not enough memory+ * settings. Mark that we aren't going to switch anymore.+ */+ buildstate->bufferingMode = GIST_BUFFERING_DISABLED;+ }+ }+}++/*+ * Calculate pagesPerBuffer parameter for the buffering algorithm.+ *+ * Buffer size is chosen so that assuming that tuples are distributed+ * randomly, emptying half a buffer fills on average one page in every buffer+ * at the next lower level.+ */+static int+calculatePagesPerBuffer(GISTBuildState *buildstate, Relation index,+ int levelStep)+{+ double pagesPerBuffer;+ double avgIndexTuplesPerPage;+ double itupAvgSize;+ Size pageFreeSpace;++ /* Calc space of index page which is available for index tuples */+ pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)+ - sizeof(ItemIdData)+ - buildstate->freespace;++ /*+ * Calculate average size of already inserted index tuples using+ * gathered statistics.+ */+ itupAvgSize = (double) buildstate->indtuplesSize /+ (double) buildstate->indtuples;++ avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;++ /*+ * Recalculate required size of buffers.+ */+ pagesPerBuffer = 2 * pow(avgIndexTuplesPerPage, levelStep);++ return round(pagesPerBuffer);+}+++/*+ * Get maximum level number of GiST index. Scans tree from root until meets+ * leaf page choosing first link in each page.+ */+static int+gistGetMaxLevel(Relation index)+{+ int maxLevel = 0;+ BlockNumber blkno = GIST_ROOT_BLKNO;++ while (true)+ {+ Buffer buffer;+ Page page;+ IndexTuple itup;++ /* Read page */+ buffer = ReadBuffer(index, blkno);+ page = (Page) BufferGetPage(buffer);++ /* Is it a leaf page? */+ if (GistPageIsLeaf(page))+ {+ /* Page is leaf. We've counted height of tree. */+ ReleaseBuffer(buffer);+ break;+ }++ /*+ * Page is not leaf. Iterate to underlying page using first link of+ * it.+ */+ itup = (IndexTuple) PageGetItem(page,+ PageGetItemId(page, FirstOffsetNumber));+ blkno = ItemPointerGetBlockNumber(&(itup->t_tid));+ ReleaseBuffer(buffer);++ /*+ * We're going down on the tree. It means that there is yet one more+ * level is the tree.+ */+ maxLevel++;+ }+ return maxLevel;+}++/*+ * Initial calculations for GiST buffering build.+ */+static bool+gistInitBuffering(GISTBuildState *buildstate, Relation index)+{+ int pagesPerBuffer;+ Size pageFreeSpace;+ Size itupAvgSize,+ itupMinSize;+ double avgIndexTuplesPerPage,+ maxIndexTuplesPerPage;+ int i;+ int levelStep;+ GISTBuildBuffers *gfbb;++ /* Calc space of index page which is available for index tuples */+ pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)+ - sizeof(ItemIdData)+ - buildstate->freespace;++ /*+ * Calculate average size of already inserted index tuples using gathered+ * statistics.+ */+ itupAvgSize = (double) buildstate->indtuplesSize /+ (double) buildstate->indtuples;++ /*+ * Calculate minimal possible size of index tuple by index metadata.+ * Minimal possible size of varlena is VARHDRSZ.+ *+ * XXX: that's not actually true, as a short varlen can be just 2 bytes.+ * And we should take padding into account here.+ */+ itupMinSize = (Size) MAXALIGN(sizeof(IndexTupleData));+ for (i = 0; i < index->rd_att->natts; i++)+ {+ if (index->rd_att->attrs[i]->attlen < 0)+ itupMinSize += VARHDRSZ;+ else+ itupMinSize += index->rd_att->attrs[i]->attlen;+ }++ /* Calculate average and maximal number of index tuples which fit to page */+ avgIndexTuplesPerPage = pageFreeSpace / itupAvgSize;+ maxIndexTuplesPerPage = pageFreeSpace / itupMinSize;++ /*+ * We need to calculate two parameters for the buffering algorithm:+ * levelStep and pagesPerBuffer.+ *+ * levelStep determines the size of subtree that we operate on, while+ * emptying a buffer. A higher value is better, as you need fewer buffer+ * emptying steps to perform the index build. However, if you set it too+ * high, the subtree doesn't fit in cache anymore, and you quickly lose+ * the benefit of the buffers.+ *+ * In Arge et al's paper, levelStep is chosen as logB(M/4B), where B is+ * the number of tuples on page (ie. fanout), and M is the amount of+ * internal memory available. Curiously, they doesn't explain *why* that+ * setting is optimal. We calculate it by taking the highest levelStep+ * so that a subtree still fits in cache. For a small B, our way of+ * calculating levelStep is very close to Arge et al's formula. For a+ * large B, our formula gives a value that is 2x higher.+ *+ * The average size of a subtree of depth n can be calculated as a+ * geometric series:+ *+ * B^0 + B^1 + B^2 + ... + B^n = (1 - B^(n + 1)) / (1 - B)+ *+ * where B is the average number of index tuples on page. The subtree is+ * cached in the shared buffer cache and the OS cache, so we choose+ * levelStep so that the subtree size is comfortably smaller than+ * effective_cache_size, with a safety factor of 4.+ *+ * The estimate on the average number of index tuples on page is based on+ * average tuple sizes observed before switching to buffered build, so the+ * real subtree size can be somewhat larger. Also, it would selfish to+ * gobble the whole cache for our index build. The safety factor of 4+ * should account for those effects.+ *+ * The other limiting factor for setting levelStep is that while+ * processing a subtree, we need to hold one page for each buffer at the+ * next lower buffered level. The max. number of buffers needed for that+ * is maxIndexTuplesPerPage^levelStep. This is very conservative, but+ * hopefully maintenance_work_mem is set high enough that you're+ * constrained by effective_cache_size rather than maintenance_work_mem.+ *+ * XXX: the buffer hash table consumes a fair amount of memory too per+ * buffer, but that is not currently taken into account. That scales on+ * the total number of buffers used, ie. the index size and on levelStep.+ * Note that a higher levelStep *reduces* the amount of memory needed for+ * the hash table.+ */+ levelStep = 0;+ while (+ /* subtree must fit in cache (with safety factor of 4) */+ (1 - pow(avgIndexTuplesPerPage, (double) (levelStep + 1))) / (1 - avgIndexTuplesPerPage) < effective_cache_size / 4+ &&+ /* each node in the lowest level of a subtree has one page in memory */+ (pow(maxIndexTuplesPerPage, (double) levelStep) < (maintenance_work_mem * 1024) / BLCKSZ)+ )+ {+ levelStep++;+ }++ /*+ * If there's not enough cache or maintenance_work_mem, fall back to plain+ * inserts.+ */+ if (levelStep <= 0)+ {+ elog(DEBUG1, "failed to switch to buffered GiST build");+ return false;+ }++ /*+ * The second parameter to set is pagesPerBuffer, which determines the+ * size of each buffer. We adjust pagesPerBuffer also during the build,+ * which is why this calculation is in a separate function.+ */+ pagesPerBuffer = calculatePagesPerBuffer(buildstate, index, levelStep);++ elog(DEBUG1, "switching to buffered GiST build; level step = %d, pagesPerBuffer = %d",+ levelStep, pagesPerBuffer);++ /* Initialize GISTBuildBuffers with these parameters */+ gfbb = palloc(sizeof(GISTBuildBuffers));+ gfbb->pagesPerBuffer = pagesPerBuffer;+ gfbb->levelStep = levelStep;+ gistInitBuildBuffers(gfbb, gistGetMaxLevel(index));++ buildstate->giststate.gfbb = gfbb;++ return true;+}++/*+ * Routine to build an index. Basically calls insert over and over.+ *+ * XXX: it would be nice to implement some sort of bulk-loading+ * algorithm, but it is not clear how to do that.+ */+Datum+gistbuild(PG_FUNCTION_ARGS)+{+ Relation heap = (Relation) PG_GETARG_POINTER(0);+ Relation index = (Relation) PG_GETARG_POINTER(1);+ IndexInfo *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);+ IndexBuildResult *result;+ double reltuples;+ GISTBuildState buildstate;+ Buffer buffer;+ Page page;+ MemoryContext oldcxt = CurrentMemoryContext;++ buildstate.freespace = RelationGetTargetPageFreeSpace(index,+ GIST_DEFAULT_FILLFACTOR);++ if (index->rd_options)+ {+ /* Get buffering mode from the options string */+ GiSTOptions *options = (GiSTOptions *) index->rd_options;+ char *bufferingMode = (char *) options + options->bufferingModeOffset;++ if (strcmp(bufferingMode, "on") != 0)+ buildstate.bufferingMode = GIST_BUFFERING_STATS;+ else if (strcmp(bufferingMode, "off") != 0)+ buildstate.bufferingMode = GIST_BUFFERING_DISABLED;+ else+ buildstate.bufferingMode = GIST_BUFFERING_AUTO;+ }+ else+ {+ /* Automatic buffering mode switching by default */+ buildstate.bufferingMode = GIST_BUFFERING_AUTO;+ }++ /*+ * 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));++ /* no locking is needed */+ initGISTstate(&buildstate.giststate, index);++ /* 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);++ if (RelationNeedsWAL(index))+ {+ XLogRecPtr recptr;+ XLogRecData rdata;++ rdata.data = (char *) &(index->rd_node);+ rdata.len = sizeof(RelFileNode);+ rdata.buffer = InvalidBuffer;+ rdata.next = NULL;++ recptr = XLogInsert(RM_GIST_ID, XLOG_GIST_CREATE_INDEX, &rdata);+ PageSetLSN(page, recptr);+ PageSetTLI(page, ThisTimeLineID);+ }+ else+ PageSetLSN(page, GetXLogRecPtrForTemp());++ UnlockReleaseBuffer(buffer);++ END_CRIT_SECTION();++ /* build the index */+ buildstate.indtuples = 0;+ buildstate.indtuplesSize = 0;++ /*+ * create a temporary memory context that is reset once for each tuple+ * inserted into the index+ */+ buildstate.tmpCtx = createTempGistContext();++ /*+ * Do the heap scan.+ */+ reltuples = IndexBuildHeapScan(heap, index, indexInfo, true,+ gistBuildCallback, (void *) &buildstate);++ /*+ * If buffering build do final node buffers emptying.+ */+ if (buildstate.bufferingMode == GIST_BUFFERING_ACTIVE)+ {+ int i;+ GISTInsertState insertstate;+ GISTNodeBuffer *nodeBuffer;+ MemoryContext oldCtx;+ GISTBuildBuffers *gfbb = buildstate.giststate.gfbb;++ elog(DEBUG1, "all tuples processed, emptying buffers");++ oldCtx = MemoryContextSwitchTo(buildstate.tmpCtx);++ memset(&insertstate, 0, sizeof(GISTInsertState));+ insertstate.freespace = buildstate.freespace;+ insertstate.r = index;++ /*+ * Iterate through the levels from the most higher.+ */+ for (i = gfbb->buffersOnLevelsCount - 1; i >= 0; i--)+ {+ bool nonEmpty = true;++ /*+ * Until we have non-empty node buffers on the level, iterate over+ * them and initial emptying of non-empty ones.+ */+ while (nonEmpty)+ {+ ListCell *p;++ nonEmpty = false;++ for (p = list_head(gfbb->buffersOnLevels[i]); p; p = p->next)+ {+ bool isRoot;++ /* Get next node buffer */+ nodeBuffer = (GISTNodeBuffer *) p->data.ptr_value;+ isRoot = (nodeBuffer->nodeBlocknum == GIST_ROOT_BLKNO);++ /* Skip empty node buffer */+ if (nodeBuffer->blocksCount == 0)+ continue;++ /* Memorize that we saw a non-empty buffer. */+ nonEmpty = true;++ /* Process emptying of node buffer */+ MemoryContextSwitchTo(gfbb->context);+ gfbb->bufferEmptyingQueue = lcons(nodeBuffer, gfbb->bufferEmptyingQueue);+ MemoryContextSwitchTo(buildstate.tmpCtx);+ gistProcessEmptyingStack(&buildstate.giststate, &insertstate);++ /*+ * Root page node buffer is the only node buffer that can+ * be deleted from the list. So, let's be careful and+ * restart the scan.+ */+ if (isRoot)+ break;+ }+ }+ }+ MemoryContextSwitchTo(oldCtx);+ }++ /* okay, all heap tuples are indexed */+ MemoryContextSwitchTo(oldcxt);+ MemoryContextDelete(buildstate.tmpCtx);++ freeGISTstate(&buildstate.giststate);++ /*+ * Return statistics+ */+ result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));++ result->heap_tuples = reltuples;+ result->index_tuples = (double) buildstate.indtuples;++ PG_RETURN_POINTER(result);+}diff --git a/src/backend/access/gist/gistbuildbuffers.c b/src/backend/access/gist/gistbuildbuffers.cnew file mode 100644index 0000000..d0c124d--- /dev/null+++ b/src/backend/access/gist/gistbuildbuffers.c@@ -0,0 +1,910 @@+/*-------------------------------------------------------------------------+ *+ * gistbuildbuffers.c+ * buffers management functions for GiST buffering build algorithm.+ *+ *+ * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group+ * Portions Copyright (c) 1994, Regents of the University of California+ *+ * IDENTIFICATION+ * src/backend/access/gist/gistbuildbuffers.c+ *+ *-------------------------------------------------------------------------+ */+#include "postgres.h"++#include "access/genam.h"+#include "access/gist_private.h"+#include "catalog/index.h"+#include "catalog/pg_collation.h"+#include "miscadmin.h"+#include "storage/buffile.h"+#include "storage/bufmgr.h"+#include "storage/indexfsm.h"+#include "utils/memutils.h"+#include "utils/rel.h"++static GISTNodeBufferPage *gistAllocateNewPageBuffer(GISTBuildBuffers *gfbb);+static void gistAddLoadedBuffer(GISTBuildBuffers *gfbb, BlockNumber blocknum);+static void gistLoadNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer);+static void gistUnloadNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer);+static void gistPlaceItupToPage(GISTNodeBufferPage *pageBuffer, IndexTuple item);+static void gistGetItupFromPage(GISTNodeBufferPage *pageBuffer, IndexTuple *item);+static int gistBuffersFreeBlocksCmp(const void *a, const void *b);+static long gistBuffersGetFreeBlock(GISTBuildBuffers *gfbb);+static void gistBuffersReleaseBlock(GISTBuildBuffers *gfbb, long blocknum);++/*+ * Initialize GiST buffering build data structure.+ */+void+gistInitBuildBuffers(GISTBuildBuffers *gfbb, int maxLevel)+{+ HASHCTL hashCtl;++ /*+ * Create temporary file initialize data structures for free pages+ * management.+ */+ gfbb->pfile = BufFileCreateTemp(true);+ gfbb->nFileBlocks = 0;+ gfbb->nFreeBlocks = 0;+ gfbb->blocksSorted = false;+ gfbb->freeBlocksLen = 32;+ gfbb->freeBlocks = (long *) palloc(gfbb->freeBlocksLen * sizeof(long));++ /*+ * Current memory context will be used for all in-memory data structures+ * of buffers which are persistent during buffering build.+ */+ gfbb->context = CurrentMemoryContext;++ /*+ * nodeBuffersTab hash is association between index blocks and it's+ * buffers.+ */+ hashCtl.keysize = sizeof(BlockNumber);+ hashCtl.entrysize = sizeof(GISTNodeBuffer);+ hashCtl.hcxt = CurrentMemoryContext;+ hashCtl.hash = tag_hash;+ hashCtl.match = memcmp;+ gfbb->nodeBuffersTab = hash_create("gistbuildbuffers",+ 1024,+ &hashCtl,+ HASH_ELEM | HASH_CONTEXT | HASH_FUNCTION+ | HASH_COMPARE);++ /*+ * Stack of node buffers which was planned for emptying.+ */+ gfbb->bufferEmptyingQueue = NIL;++ gfbb->currentEmptyingBufferBlockNumber = InvalidBlockNumber;+ gfbb->currentEmptyingBufferSplit = false;++ /*+ * Per-level node buffers lists for final buffers emptying process. Node+ * buffer are inserted here when it is created. Root node buffer is the+ * only buffer which can be deleted from appropriate list, because after+ * split root node appears at higher level but saves block number.+ */+ gfbb->buffersOnLevelsLen = 16;+ gfbb->buffersOnLevels = (List **) palloc(sizeof(List *) *+ gfbb->buffersOnLevelsLen);+ gfbb->buffersOnLevelsCount = 0;++ /*+ * Block numbers of node buffers which last pages are currently loaded+ * into main memory.+ */+ gfbb->loadedBuffersLen = 32;+ gfbb->loadedBuffers = (BlockNumber *) palloc(gfbb->loadedBuffersLen *+ sizeof(BlockNumber));+ gfbb->loadedBuffersCount = 0;++ /*+ * Root path item of the tree. Being updated on each root node split.+ */+ gfbb->rootitem = (GISTBufferingInsertStack *) MemoryContextAlloc(+ gfbb->context, sizeof(GISTBufferingInsertStack));+ gfbb->rootitem->parent = NULL;+ gfbb->rootitem->blkno = GIST_ROOT_BLKNO;+ gfbb->rootitem->downlinkoffnum = InvalidOffsetNumber;+ gfbb->rootitem->level = maxLevel;+ gfbb->rootitem->refCount = 1;+}++/*+ * Returns a node buffer by its block number. If createNew flag is specified+ * then new NodeBuffer structure will be created on it's absence.+ */+GISTNodeBuffer *+gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate,+ BlockNumber nodeBlocknum,+ OffsetNumber downlinkoffnum,+ GISTBufferingInsertStack *parent, bool createNew)+{+ GISTNodeBuffer *nodeBuffer;+ bool found;++ /*+ * Find nodeBuffer in hash table+ */+ nodeBuffer = (GISTNodeBuffer *) hash_search(gfbb->nodeBuffersTab,+ (const void *) &nodeBlocknum,+ createNew ? HASH_ENTER : HASH_FIND,+ &found);+ if (!found)+ {+ GISTBufferingInsertStack *path;+ int levelIndex;+ int i;+ MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context);++ /*+ * Node buffer wasn't found. Create new if required.+ */+ if (!createNew)+ return NULL;++ if (nodeBlocknum != GIST_ROOT_BLKNO)+ {+ /*+ * For non-root page we have to create new path item which+ * references to the given parent.+ */+ path = (GISTBufferingInsertStack *) palloc(+ sizeof(GISTBufferingInsertStack));+ path->parent = parent;+ path->blkno = nodeBlocknum;+ path->downlinkoffnum = downlinkoffnum;+ path->level = parent->level - 1;+ path->refCount = 0;+ parent->refCount++;+ Assert(path->level > 0);+ }+ else+ {+ path = gfbb->rootitem;+ }++ /* Node buffer references it's path item. */+ path->refCount++;++ /*+ * New node buffer. Fill data structure with default values.+ */+ nodeBuffer->pageBuffer = NULL;+ nodeBuffer->blocksCount = 0;+ nodeBuffer->path = path;+ nodeBuffer->queuedForEmptying = false;++ /*+ * Put node buffer to the appropriate list. Calc index of node buffer+ * list by it's level.+ */+ levelIndex = (path->level - gfbb->levelStep) / gfbb->levelStep;++ /*+ * Probably, we should increase number of allocated buffers lists.+ */+ while (levelIndex >= gfbb->buffersOnLevelsLen)+ {+ gfbb->buffersOnLevelsLen *= 2;+ gfbb->buffersOnLevels =+ (List **) repalloc(gfbb->buffersOnLevels,+ gfbb->buffersOnLevelsLen *+ sizeof(List *));+ }++ /* Initialize new buffers lists as empty. */+ if (levelIndex >= gfbb->buffersOnLevelsCount)+ {+ for (i = gfbb->buffersOnLevelsCount; i <= levelIndex; i++)+ gfbb->buffersOnLevels[i] = NIL;+ gfbb->buffersOnLevelsCount = levelIndex + 1;+ }++ /* Add node buffer to the corresponding list */+ gfbb->buffersOnLevels[levelIndex] = lcons(+ nodeBuffer, gfbb->buffersOnLevels[levelIndex]);++ MemoryContextSwitchTo(oldcxt);+ }+ else+ {+ if (parent != nodeBuffer->path->parent)+ {+ /*+ * Other parent path item was provided than we've remembered. We+ * trust caller to provide more correct parent than we have.+ * Previous parent may be outdated by page split.+ */+ gistDecreasePathRefcount(nodeBuffer->path->parent);+ nodeBuffer->path->parent = parent;+ parent->refCount++;+ }+ }++ return nodeBuffer;+}++/*+ * Allocate memory for buffer page.+ */+static GISTNodeBufferPage *+gistAllocateNewPageBuffer(GISTBuildBuffers * gfbb)+{+ GISTNodeBufferPage *pageBuffer;++ /*+ * Allocate memory for page in appropriate context.+ */+ pageBuffer = (GISTNodeBufferPage *) MemoryContextAlloc(gfbb->context, BLCKSZ);++ /*+ * Set page free space+ */+ PAGE_FREE_SPACE(pageBuffer) = BLCKSZ - BUFFER_PAGE_DATA_OFFSET;+ return pageBuffer;+}++/*+ * Add specified block number into preparedBlocks array.+ */+static void+gistAddLoadedBuffer(GISTBuildBuffers * gfbb, BlockNumber blocknum)+{+ if (gfbb->loadedBuffersCount >= gfbb->loadedBuffersLen)+ {+ /*+ * Not enough of memory is currently allocated.+ */+ gfbb->loadedBuffersLen *= 2;+ gfbb->loadedBuffers = (BlockNumber *) repalloc(gfbb->loadedBuffers,+ gfbb->loadedBuffersLen *+ sizeof(BlockNumber));+ }+ /* Actual add to array */+ gfbb->loadedBuffers[gfbb->loadedBuffersCount] = blocknum;+ gfbb->loadedBuffersCount++;+}+++/*+ * Load last page of node buffer into main memory.+ */+static void+gistLoadNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer)+{+ /* Check if we really should load something */+ if (!nodeBuffer->pageBuffer && nodeBuffer->blocksCount > 0)+ {+ /* Allocate memory for page */+ nodeBuffer->pageBuffer = gistAllocateNewPageBuffer(gfbb);++ /* Read block from temporary file */+ BufFileSeekBlock(gfbb->pfile, nodeBuffer->pageBlocknum);+ BufFileRead(gfbb->pfile, nodeBuffer->pageBuffer, BLCKSZ);++ /* Mark file block as free */+ gistBuffersReleaseBlock(gfbb, nodeBuffer->pageBlocknum);++ /* Mark node buffer as loaded */+ gistAddLoadedBuffer(gfbb, nodeBuffer->nodeBlocknum);+ nodeBuffer->pageBlocknum = InvalidBlockNumber;+ }+}++/*+ * Write last page of node buffer to the disk.+ */+static void+gistUnloadNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer)+{+ /* Check if we have something to write */+ if (nodeBuffer->pageBuffer)+ {+ BlockNumber blkno;++ /* Get free file block */+ blkno = gistBuffersGetFreeBlock(gfbb);++ /* Write block to the temporary file */+ BufFileSeekBlock(gfbb->pfile, blkno);+ BufFileWrite(gfbb->pfile, nodeBuffer->pageBuffer, BLCKSZ);++ /* Free memory of that page */+ pfree(nodeBuffer->pageBuffer);+ nodeBuffer->pageBuffer = NULL;++ /* Save block number */+ nodeBuffer->pageBlocknum = blkno;+ }+}++/*+ * Write last pages of all node buffers to the disk.+ */+void+gistUnloadNodeBuffers(GISTBuildBuffers *gfbb)+{+ int i;++ /* Iterate over node buffers which last page is loaded into main memory */+ for (i = 0; i < gfbb->loadedBuffersCount; i++)+ {+ GISTNodeBuffer *nodeBuffer;+ bool found;++ /* Find node buffer by it's block number */+ nodeBuffer = hash_search(gfbb->nodeBuffersTab, &gfbb->loadedBuffers[i],+ HASH_FIND, &found);++ /*+ * Node buffer can be not found. It can disappear during page split.+ * So, it's ok, just skip it.+ */+ if (!found)+ continue;++ /* Unload last page to the disk */+ gistUnloadNodeBuffer(gfbb, nodeBuffer);+ }+ /* Now there are no node buffers with loaded last page */+ gfbb->loadedBuffersCount = 0;+}++/*+ * Add index tuple to buffer page.+ */+static void+gistPlaceItupToPage(GISTNodeBufferPage *pageBuffer, IndexTuple itup)+{+ /*+ * Get pointer to the start of page free space+ */+ char *ptr = (char *) pageBuffer + BUFFER_PAGE_DATA_OFFSET+ + PAGE_FREE_SPACE(pageBuffer) - MAXALIGN(IndexTupleSize(itup));++ /*+ * There should be enough of space+ */+ Assert(PAGE_FREE_SPACE(pageBuffer) >= MAXALIGN(IndexTupleSize(itup)));++ /*+ * Reduce free space value of page+ */+ PAGE_FREE_SPACE(pageBuffer) -= MAXALIGN(IndexTupleSize(itup));++ /*+ * Copy index tuple to free space+ */+ memcpy(ptr, itup, IndexTupleSize(itup));+}++/*+ * Get last item from buffer page and remove it from page.+ */+static void+gistGetItupFromPage(GISTNodeBufferPage *pageBuffer, IndexTuple *itup)+{+ /*+ * Get pointer to last index tuple+ */+ IndexTuple ptr = (IndexTuple) ((char *) pageBuffer+ + BUFFER_PAGE_DATA_OFFSET+ + PAGE_FREE_SPACE(pageBuffer));++ /*+ * Page shouldn't be empty+ */+ Assert(!PAGE_IS_EMPTY(pageBuffer));++ /*+ * Allocate memory for returned index tuple copy+ */+ *itup = (IndexTuple) palloc(IndexTupleSize(ptr));++ /*+ * Copy data+ */+ memcpy(*itup, ptr, IndexTupleSize(ptr));++ /*+ * Increase free space value of page+ */+ PAGE_FREE_SPACE(pageBuffer) += MAXALIGN(IndexTupleSize(*itup));+}++/*+ * Push new index tuple to node buffer.+ */+void+gistPushItupToNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer,+ IndexTuple itup)+{+ /*+ * Most part of memory operations will be in buffering build persistent+ * context. So, let's switch to it.+ */+ MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context);++ /* Is the buffer currently empty? */+ if (nodeBuffer->blocksCount == 0)+ {+ /* It's empty, let's create the first page */+ nodeBuffer->pageBuffer = gistAllocateNewPageBuffer(gfbb);+ nodeBuffer->pageBuffer->prev = InvalidBlockNumber;+ nodeBuffer->blocksCount = 1;+ gistAddLoadedBuffer(gfbb, nodeBuffer->nodeBlocknum);+ }++ /* Load last page of node buffer if it wasn't already */+ if (!nodeBuffer->pageBuffer)+ {+ gistLoadNodeBuffer(gfbb, nodeBuffer);+ }++ /*+ * Check if there is enough space on the last page for the tuple+ */+ if (PAGE_NO_SPACE(nodeBuffer->pageBuffer, itup))+ {+ /*+ * Swap previous block to disk and allocate new one+ */+ BlockNumber blkno;++ /* Write filled page to the disk */+ blkno = gistBuffersGetFreeBlock(gfbb);+ BufFileSeekBlock(gfbb->pfile, blkno);+ BufFileWrite(gfbb->pfile, nodeBuffer->pageBuffer, BLCKSZ);++ /* Mark space of in-memory page as empty */+ PAGE_FREE_SPACE(nodeBuffer->pageBuffer) =+ BLCKSZ - MAXALIGN(offsetof(GISTNodeBufferPage, tupledata));++ /* Save block number of the previous page */+ nodeBuffer->pageBuffer->prev = blkno;++ /* We've just added one more page */+ nodeBuffer->blocksCount++;+ }++ gistPlaceItupToPage(nodeBuffer->pageBuffer, itup);++ /*+ * Restore memory context+ */+ MemoryContextSwitchTo(oldcxt);+}++/*+ * Removes one index tuple from node buffer. Returns true if success and false+ * if node buffer is empty.+ */+bool+gistPopItupFromNodeBuffer(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer,+ IndexTuple *itup)+{+ /*+ * If node buffer is empty then return false.+ */+ if (nodeBuffer->blocksCount <= 0)+ return false;++ /* Load last page of node buffer if needed */+ if (!nodeBuffer->pageBuffer)+ gistLoadNodeBuffer(gfbb, nodeBuffer);++ /*+ * Get index tuple from last non-empty page.+ */+ gistGetItupFromPage(nodeBuffer->pageBuffer, itup);++ /*+ * Check if the page which the index tuple was got from is now empty+ */+ if (PAGE_IS_EMPTY(nodeBuffer->pageBuffer))+ {+ BlockNumber prevblkno;++ /*+ * If it's empty then we need to release buffer file block and free+ * page buffer.+ */+ nodeBuffer->blocksCount--;++ /*+ * If there's more pages, fetch previous one+ */+ prevblkno = nodeBuffer->pageBuffer->prev;+ if (prevblkno != InvalidBlockNumber)+ {+ /* There actually is previous page, so read it. */+ Assert(nodeBuffer->blocksCount > 0);+ BufFileSeekBlock(gfbb->pfile, prevblkno);+ BufFileRead(gfbb->pfile, nodeBuffer->pageBuffer, BLCKSZ);++ /* Mark block as free */+ gistBuffersReleaseBlock(gfbb, prevblkno);+ }+ else+ {+ /* Actually there are no more pages. Free memory. */+ Assert(nodeBuffer->blocksCount == 0);+ pfree(nodeBuffer->pageBuffer);+ nodeBuffer->pageBuffer = NULL;+ }+ }+ return true;+}++/*+ * qsort comparator for sorting freeBlocks[] into decreasing order.+ */+static int+gistBuffersFreeBlocksCmp(const void *a, const void *b)+{+ long ablk = *((const long *) a);+ long bblk = *((const long *) b);++ /*+ * can't just subtract because long might be wider than int+ */+ if (ablk < bblk)+ return 1;+ if (ablk > bblk)+ return -1;+ return 0;+}++/*+ * Select a currently unused block for writing to.+ *+ * NB: should only be called when writer is ready to write immediately,+ * to ensure that first write pass is sequential.+ */+static long+gistBuffersGetFreeBlock(GISTBuildBuffers * gfbb)+{+ /*+ * If there are multiple free blocks, we select the one appearing last in+ * freeBlocks[] (after sorting the array if needed). If there are none,+ * assign the next block at the end of the file.+ */+ if (gfbb->nFreeBlocks > 0)+ {+ if (!gfbb->blocksSorted)+ {+ qsort((void *) gfbb->freeBlocks, gfbb->nFreeBlocks,+ sizeof(long), gistBuffersFreeBlocksCmp);+ gfbb->blocksSorted = true;+ }+ return gfbb->freeBlocks[--gfbb->nFreeBlocks];+ }+ else+ return gfbb->nFileBlocks++;+}++/*+ * Return a block# to the freelist.+ */+static void+gistBuffersReleaseBlock(GISTBuildBuffers * gfbb, long blocknum)+{+ int ndx;++ /*+ * Enlarge freeBlocks array if full.+ */+ if (gfbb->nFreeBlocks >= gfbb->freeBlocksLen)+ {+ gfbb->freeBlocksLen *= 2;+ gfbb->freeBlocks = (long *) repalloc(gfbb->freeBlocks,+ gfbb->freeBlocksLen *+ sizeof(long));+ }++ /*+ * Add blocknum to array, and mark the array unsorted if it's no longer in+ * decreasing order.+ */+ ndx = gfbb->nFreeBlocks++;+ gfbb->freeBlocks[ndx] = blocknum;+ if (ndx > 0 && gfbb->freeBlocks[ndx - 1] < blocknum)+ gfbb->blocksSorted = false;+}++/*+ * Free buffering build data structure.+ */+void+gistFreeBuildBuffers(GISTBuildBuffers * gfbb)+{+ /* Close buffers file. */+ BufFileClose(gfbb->pfile);++ /* All other things will be free on memory context release */+}++/*+ * Data structure representing information about node buffer for index tuples+ * relocation from splitted node buffer.+ */+typedef struct+{+ GISTENTRY entry[INDEX_MAX_KEYS];+ bool isnull[INDEX_MAX_KEYS];+ SplitedPageLayout *dist;+ GISTNodeBuffer *nodeBuffer;+} RelocationBufferInfo;++/*+ * Maintain data structures on page split.+ */+void+gistRelocateBuildBuffersOnSplit(GISTBuildBuffers * gfbb, GISTSTATE *giststate,+ Relation r, GISTBufferingInsertStack *path,+ Buffer buffer, SplitedPageLayout *dist)+{+ RelocationBufferInfo *relocationBuffersInfos;+ bool found;+ GISTNodeBuffer *nodeBuffer;+ BlockNumber blocknum;+ IndexTuple itup;+ int splitPagesCount = 0,+ i;+ GISTENTRY entry[INDEX_MAX_KEYS];+ bool isnull[INDEX_MAX_KEYS];+ SplitedPageLayout *ptr;+ int level = path->level;+ GISTNodeBuffer nodebuf;++ blocknum = BufferGetBlockNumber(buffer);++ /*+ * If this is a root split, update the root path item kept in memory. This+ * ensures that all path stacks are always complete, including all parent+ * nodes up to the root, which simplifies the algorithm to re-find correct+ * parent.+ */+ if (blocknum == GIST_ROOT_BLKNO)+ {+ GISTBufferingInsertStack *oldroot = gfbb->rootitem;++ gfbb->rootitem = (GISTBufferingInsertStack *) MemoryContextAlloc(+ gfbb->context, sizeof(GISTBufferingInsertStack));+ gfbb->rootitem->parent = NULL;+ gfbb->rootitem->blkno = GIST_ROOT_BLKNO;+ gfbb->rootitem->downlinkoffnum = InvalidOffsetNumber;+ gfbb->rootitem->level = oldroot->level + 1;+ gfbb->rootitem->refCount = 1;++ oldroot->parent = gfbb->rootitem;+ oldroot->blkno = dist->block.blkno;+ oldroot->downlinkoffnum = InvalidOffsetNumber;+ }++ /*+ * If splitted page level doesn't have buffers, then we've nothing to do+ * with it.+ */+ if (!LEVEL_HAS_BUFFERS(level, gfbb))+ return;++ /*+ * Get pointer of node buffer of splitted page.+ */+ nodeBuffer = hash_search(gfbb->nodeBuffersTab, &blocknum,+ HASH_FIND, &found);+ if (!found)+ {+ /*+ * Node buffer should anyway be created at this moment. Either by+ * index tuples insertion or page split.+ */+ elog(ERROR,+ "node buffer of splitting page (%u) doesn't exists while it should.",+ blocknum);+ }++ /*+ * Make a copy of the old buffer, as we're going reuse the old one for+ * the buffer for the new left page, which is on the same block as the+ * old page. That's not true for the root page, but that's fine because+ * we never have a buffer on the root page anyway. The original algorithm+ * as described by Arge et al did, but it doesn't help as you might as+ * well read the tuples straight from the heap instead of the root buffer.+ */+ Assert(blocknum != GIST_ROOT_BLKNO);+ memcpy(&nodebuf, nodeBuffer, sizeof(GISTNodeBuffer));++ /* Reassign pointer to the saved copy. */+ nodeBuffer = &nodebuf;++ /*+ * Count pages produced by split and save pointer data structure of the+ * last one.+ */+ for (ptr = dist; ptr; ptr = ptr->next)+ splitPagesCount++;++ /*+ * Allocate memory for information about relocation buffers.+ */+ relocationBuffersInfos =+ (RelocationBufferInfo *) palloc(sizeof(RelocationBufferInfo) *+ splitPagesCount);++ /*+ * Fill relocation buffers information for node buffers of pages produced+ * by split.+ */+ i = 0;+ for (ptr = dist; ptr; ptr = ptr->next)+ {+ GISTNodeBuffer *newNodeBuffer;++ /*+ * Decompress parent index tuple of node buffer page.+ */+ gistDeCompressAtt(giststate, r,+ ptr->itup, NULL, (OffsetNumber) 0,+ relocationBuffersInfos[i].entry,+ relocationBuffersInfos[i].isnull);++ newNodeBuffer = gistGetNodeBuffer(gfbb, giststate, ptr->block.blkno,+ path->downlinkoffnum, path->parent, true);++ /*+ * Fill relocation information+ */+ relocationBuffersInfos[i].nodeBuffer = newNodeBuffer;+ if (newNodeBuffer->nodeBlocknum == blocknum)+ {+ /*+ * Reuse of GISTNodeBuffer data structure of splitted node. Old+ * version was copied.+ */+ newNodeBuffer->blocksCount = 0;+ newNodeBuffer->pageBuffer = NULL;+ newNodeBuffer->pageBlocknum = InvalidBlockNumber;+ }++ /*+ * Fill node buffer structure+ */+ relocationBuffersInfos[i].dist = ptr;++ i++;+ }++ /*+ * Loop of index tuples relocation.+ */+ while (gistPopItupFromNodeBuffer(gfbb, nodeBuffer, &itup))+ {+ float sum_grow,+ which_grow[INDEX_MAX_KEYS];+ int i,+ which;+ IndexTuple newtup;++ /*+ * Choose node buffer for index tuple insert.+ */+ gistDeCompressAtt(giststate, r,+ itup, NULL, (OffsetNumber) 0, entry, isnull);++ which = -1;+ *which_grow = -1.0f;+ sum_grow = 1.0f;++ for (i = 0; i < splitPagesCount && sum_grow; i++)+ {+ int j;+ RelocationBufferInfo *splitPageInfo = &relocationBuffersInfos[i];++ sum_grow = 0.0f;+ for (j = 0; j < r->rd_att->natts; j++)+ {+ float usize;++ usize = gistpenalty(giststate, j,+ &splitPageInfo->entry[j],+ splitPageInfo->isnull[j],+ &entry[j], isnull[j]);++ if (which_grow[j] < 0 || usize < which_grow[j])+ {+ which = i;+ which_grow[j] = usize;+ if (j < r->rd_att->natts - 1 && i == 0)+ which_grow[j + 1] = -1;+ sum_grow += which_grow[j];+ }+ else if (which_grow[j] == usize)+ sum_grow += usize;+ else+ {+ sum_grow = 1;+ break;+ }+ }+ }++ /*+ * push item to selected node buffer+ */+ gistPushItupToNodeBuffer(gfbb, relocationBuffersInfos[which].nodeBuffer,+ itup);++ /*+ * If node buffer was just overflowed then we should add it to the+ * emptying stack.+ */+ if (BUFFER_HALF_FILLED(relocationBuffersInfos[which].nodeBuffer, gfbb)+ && !relocationBuffersInfos[which].nodeBuffer->queuedForEmptying)+ {+ MemoryContext oldcxt = MemoryContextSwitchTo(gfbb->context);++ relocationBuffersInfos[which].nodeBuffer->queuedForEmptying = true;+ gfbb->bufferEmptyingQueue =+ lcons(relocationBuffersInfos[which].nodeBuffer,+ gfbb->bufferEmptyingQueue);+ MemoryContextSwitchTo(oldcxt);+ }++ /*+ * adjust tuple of parent page+ */+ newtup = gistgetadjusted(r, relocationBuffersInfos[which].dist->itup,+ itup, giststate);+ if (newtup)+ {+ /*+ * Parent page index tuple expands. We need to update old index+ * tuple with the new one.+ */+ gistDeCompressAtt(giststate, r,+ newtup, NULL, (OffsetNumber) 0,+ relocationBuffersInfos[which].entry,+ relocationBuffersInfos[which].isnull);++ relocationBuffersInfos[which].dist->itup = newtup;+ }+ }++ /* Report about splitting for current emptying buffer */+ if (blocknum == gfbb->currentEmptyingBufferBlockNumber)+ gfbb->currentEmptyingBufferSplit = true;++ pfree(relocationBuffersInfos);+}++/*+ * Return size of node buffer occupied by stored index tuples.+ */+int+gistGetNodeBufferBusySize(GISTBuildBuffers *gfbb, GISTNodeBuffer *nodeBuffer)+{+ int size;++ /*+ * No occupied buffer file blocks means that node buffer is empty.+ */+ if (nodeBuffer->blocksCount == 0)+ return 0;+ if (!nodeBuffer->pageBuffer)+ gistLoadNodeBuffer(gfbb, nodeBuffer);++ /*+ * We assume only the last page to be not fully filled.+ */+ size = (BLCKSZ - MAXALIGN(sizeof(uint32))) * nodeBuffer->blocksCount;+ size -= PAGE_FREE_SPACE(nodeBuffer->pageBuffer);+ return size;+}diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.cindex 1754a10..bae990b 100644--- a/src/backend/access/gist/gistutil.c+++ b/src/backend/access/gist/gistutil.c@@ -670,13 +670,30 @@ gistoptions(PG_FUNCTION_ARGS)
{
Datum reloptions = PG_GETARG_DATUM(0);
bool validate = PG_GETARG_BOOL(1);
- bytea *result;+ relopt_value *options;+ GiSTOptions *rdopts;+ int numoptions;+ static const relopt_parse_elt tab[] = {+ {"fillfactor", RELOPT_TYPE_INT, offsetof(GiSTOptions, fillfactor)},+ {"buffering", RELOPT_TYPE_STRING, offsetof(GiSTOptions, bufferingModeOffset)}+ };- result = default_reloptions(reloptions, validate, RELOPT_KIND_GIST);+ options = parseRelOptions(reloptions, validate, RELOPT_KIND_GIST,+ &numoptions);++ /* if none set, we're done */+ if (numoptions == 0)+ PG_RETURN_NULL();++ rdopts = allocateReloptStruct(sizeof(GiSTOptions), options, numoptions);++ fillRelOptions((void *) rdopts, sizeof(GiSTOptions), options, numoptions,+ validate, tab, lengthof(tab));++ pfree(options);++ PG_RETURN_BYTEA_P(rdopts);- if (result)- PG_RETURN_BYTEA_P(result);- PG_RETURN_NULL();
}
/*
diff --git a/src/backend/access/gist/gistxlog.c b/src/backend/access/gist/gistxlog.cindex 02c4ec3..9cf4875 100644--- a/src/backend/access/gist/gistxlog.c+++ b/src/backend/access/gist/gistxlog.c@@ -266,7 +266,8 @@ gistRedoPageSplitRecord(XLogRecPtr lsn, XLogRecord *record)
else
GistPageGetOpaque(page)->rightlink = xldata->origrlink;
GistPageGetOpaque(page)->nsn = xldata->orignsn;
- if (i < xlrec.data->npage - 1 && !isrootsplit)+ if (i < xlrec.data->npage - 1 && !isrootsplit &&+ !xldata->noFollowRight)
GistMarkFollowRight(page);
else
GistClearFollowRight(page);
@@ -414,7 +415,7 @@ XLogRecPtr
gistXLogSplit(RelFileNode node, BlockNumber blkno, bool page_is_leaf,
SplitedPageLayout *dist,
BlockNumber origrlink, GistNSN orignsn,
- Buffer leftchildbuf)+ Buffer leftchildbuf, bool noFollowFight)
{
XLogRecData *rdata;
gistxlogPageSplit xlrec;
@@ -436,6 +437,7 @@ gistXLogSplit(RelFileNode node, BlockNumber blkno, bool page_is_leaf,
xlrec.npage = (uint16) npage;
xlrec.leftchild =
BufferIsValid(leftchildbuf) ? BufferGetBlockNumber(leftchildbuf) : InvalidBlockNumber;
+ xlrec.noFollowRight = noFollowFight;
rdata[0].data = (char *) &xlrec;
rdata[0].len = sizeof(gistxlogPageSplit);
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.hindex 9fb20a6..a0e41b4 100644--- a/src/include/access/gist_private.h+++ b/src/include/access/gist_private.h@@ -17,13 +17,56 @@
#include "access/gist.h"
#include "access/itup.h"
#include "storage/bufmgr.h"
+#include "storage/buffile.h"
#include "utils/rbtree.h"
+#include "utils/hsearch.h"++/* Has specified level buffers? */+#define LEVEL_HAS_BUFFERS(nlevel, gfbb) ((nlevel) != 0 && (nlevel) % (gfbb)->levelStep == 0 && nlevel != (gfbb)->rootitem->level)+/* Is specified buffer at least half-filled (should be planned for emptying)?*/+#define BUFFER_HALF_FILLED(nodeBuffer, gfbb) ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer / 2)+/* Is specified buffer overflowed (can't take index tuples anymore)?*/+#define BUFFER_OVERFLOWED(nodeBuffer, gfbb) ((nodeBuffer)->blocksCount > (gfbb)->pagesPerBuffer)
/* Buffer lock modes */
#define GIST_SHARE BUFFER_LOCK_SHARE
#define GIST_EXCLUSIVE BUFFER_LOCK_EXCLUSIVE
#define GIST_UNLOCK BUFFER_LOCK_UNLOCK
+typedef struct+{+ BlockNumber prev;+ uint32 freespace;+ char tupledata[1];+} GISTNodeBufferPage;++#define BUFFER_PAGE_DATA_OFFSET MAXALIGN(offsetof(GISTNodeBufferPage, tupledata))+/* Returns free space in node buffer page */+#define PAGE_FREE_SPACE(nbp) (nbp->freespace)+/* Checks if node buffer page is empty */+#define PAGE_IS_EMPTY(nbp) (nbp->freespace == BLCKSZ - BUFFER_PAGE_DATA_OFFSET)+/* Checks if node buffers page don't contain sufficient space for index tuple */+#define PAGE_NO_SPACE(nbp, itup) (PAGE_FREE_SPACE(nbp) < \+ MAXALIGN(IndexTupleSize(itup)))++/* Buffer of tree node data structure */+typedef struct+{+ /* number of page containing node */+ BlockNumber nodeBlocknum;++ /* count of blocks occupied by buffer */+ int32 blocksCount;++ BlockNumber pageBlocknum;+ GISTNodeBufferPage *pageBuffer;++ /* is this buffer queued for emptying? */+ bool queuedForEmptying;++ struct GISTBufferingInsertStack *path;+} GISTNodeBuffer;+
/*
* GISTSTATE: information needed for any GiST index operation
*
@@ -44,6 +87,8 @@ typedef struct GISTSTATE
/* Collations to pass to the support functions */
Oid supportCollation[INDEX_MAX_KEYS];
+ struct GISTBuildBuffers *gfbb;+
TupleDesc tupdesc;
} GISTSTATE;
@@ -170,6 +215,7 @@ typedef struct gistxlogPageSplit
BlockNumber leftchild; /* like in gistxlogPageUpdate */
uint16 npage; /* # of pages in the split */
+ bool noFollowRight; /* skip followRight flag setting */
/*
* follow: 1. gistxlogPage and array of IndexTupleData per page
@@ -225,6 +271,76 @@ typedef struct GISTInsertStack
struct GISTInsertStack *parent;
} GISTInsertStack;
+/*+ * Extended GISTInsertStack for buffering GiST index build. It additionally hold+ * level number of page.+ */+typedef struct GISTBufferingInsertStack+{+ /* current page */+ BlockNumber blkno;++ /* offset of the downlink in the parent page, that points to this page */+ OffsetNumber downlinkoffnum;++ /* pointer to parent */+ struct GISTBufferingInsertStack *parent;++ int refCount;++ /* level number */+ int level;+} GISTBufferingInsertStack;++/*+ * Data structure with general information about build buffers.+ */+typedef struct GISTBuildBuffers+{+ /* memory context which is persistent during buffering build */+ MemoryContext context;+ /* underlying files */+ BufFile *pfile;+ /* # of blocks used in underlying files */+ long nFileBlocks;+ /* is freeBlocks[] currently in order? */+ bool blocksSorted;+ /* resizable array of free blocks */+ long *freeBlocks;+ /* # of currently free blocks */+ int nFreeBlocks;+ /* current allocated length of freeBlocks[] */+ int freeBlocksLen;++ /* hash for buffers by block number */+ HTAB *nodeBuffersTab;++ /* stack of buffers for emptying */+ List *bufferEmptyingQueue;+ /* number of currently emptying buffer */+ BlockNumber currentEmptyingBufferBlockNumber;+ /* whether currently emptying buffer was split - a signal to stop emptying */+ bool currentEmptyingBufferSplit;++ /* step of levels for buffers location */+ int levelStep;+ /* maximal number of pages occupied by buffer */+ int pagesPerBuffer;++ /* array of lists of non-empty buffers on levels for final emptying */+ List **buffersOnLevels;+ int buffersOnLevelsLen;+ int buffersOnLevelsCount;++ /* dynamic array of block numbers of buffer loaded into main memory */+ BlockNumber *loadedBuffers;+ /* number of block numbers */+ int loadedBuffersCount;+ /* length of array */+ int loadedBuffersLen;+ GISTBufferingInsertStack *rootitem;+} GISTBuildBuffers;+
typedef struct GistSplitVector
{
GIST_SPLITVEC splitVector; /* to/from PickSplit method */
@@ -286,6 +402,17 @@ extern Datum gistinsert(PG_FUNCTION_ARGS);
extern MemoryContext createTempGistContext(void);
extern void initGISTstate(GISTSTATE *giststate, Relation index);
extern void freeGISTstate(GISTSTATE *giststate);
+void gistdoinsert(Relation r,+ IndexTuple itup,+ Size freespace,+ GISTSTATE *GISTstate);+bool gistplacetopage(GISTInsertState *state, GISTSTATE *giststate,+ Buffer buffer,+ IndexTuple *itup, int ntup, OffsetNumber oldoffnum,+ Buffer leftchildbuf,+ List **splitinfo,+ GISTBufferingInsertStack * path);+void gistBufferingFindCorrectParent(GISTSTATE *giststate, Relation r, GISTBufferingInsertStack * child);
extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
int len, GISTSTATE *giststate);
@@ -305,7 +432,7 @@ extern XLogRecPtr gistXLogSplit(RelFileNode node,
BlockNumber blkno, bool page_is_leaf,
SplitedPageLayout *dist,
BlockNumber origrlink, GistNSN oldnsn,
- Buffer leftchild);+ Buffer leftchild, bool noFollowFight);
/* gistget.c */
extern Datum gistgettuple(PG_FUNCTION_ARGS);
@@ -313,6 +440,16 @@ extern Datum gistgetbitmap(PG_FUNCTION_ARGS);
/* gistutil.c */
+/*+ * Storage type for GiST's reloptions+ */+typedef struct GiSTOptions+{+ int32 vl_len_; /* varlena header (do not touch directly!) */+ int fillfactor; /* page fill factor in percent (0..100) */+ int bufferingModeOffset; /* use buffering build? */+} GiSTOptions;+
#define GiSTPageSize \
( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
@@ -380,4 +517,25 @@ extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
GistSplitVector *v, GistEntryVector *entryvec,
int attno);
+/* gistbuild.c */+extern void gistDecreasePathRefcount(GISTBufferingInsertStack * path);++/* gistbuildbuffers.c */+extern void gistInitBuildBuffers(GISTBuildBuffers *gfbb, int maxLevel);+GISTNodeBuffer *gistGetNodeBuffer(GISTBuildBuffers *gfbb, GISTSTATE *giststate,+ BlockNumber blkno, OffsetNumber downlinkoffnu,+ GISTBufferingInsertStack * parent, bool createNew);+extern void gistPushItupToNodeBuffer(GISTBuildBuffers * gfbb,+ GISTNodeBuffer *nodeBuffer, IndexTuple item);+extern bool gistPopItupFromNodeBuffer(GISTBuildBuffers * gfbb,+ GISTNodeBuffer *nodeBuffer, IndexTuple *item);+extern void gistFreeBuildBuffers(GISTBuildBuffers * gfbb);+extern void gistRelocateBuildBuffersOnSplit(GISTBuildBuffers *gfbb,+ GISTSTATE *giststate, Relation r,+ GISTBufferingInsertStack *path, Buffer buffer,+ SplitedPageLayout *dist);+extern int gistGetNodeBufferBusySize(GISTBuildBuffers *gfbb,+ GISTNodeBuffer *nodeBuffer);+extern void gistUnloadNodeBuffers(GISTBuildBuffers *gfbb);+
#endif /* GIST_PRIVATE_H */
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: heikki.linnakangas@enterprisedb.com, aekorotkov@gmail.com, robertmhaas@gmail.com
Subject: Re: WIP: Fast GiST index build
In-Reply-To: <4E4AC1C3.4070003@enterprisedb.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox