diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
new file mode 100644
index d800701..97dc648
*** a/doc/src/sgml/ref/create_index.sgml
--- b/doc/src/sgml/ref/create_index.sgml
*************** CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ]
*** 309,315 ****
! GiST indexes additionally accept this parameter:
--- 309,315 ----
! GiST indexes additionally accept these parameters:
*************** CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ]
*** 325,330 ****
--- 325,345 ----
+
+ RANDOMIZATION
+
+
+ This parameter controls GiST behaviour when it has two or more paths
+ with equal penalty values during insertion. When parameter is ON
+ it selects random path, otherwise it selects the first path. Selecting
+ random path makes GiST use tree more uniformly in insertions. It
+ increases chance for freed space to be reused, thus reducing bloat.
+ Hovewer selecting first path makes smaller part of tree to be used
+ for actual inserting. That could leads to better caching, thus
+ less of IO operations. The default is ON.
+
+
+
diff --git a/src/backend/access/common/reloptions.c b/src/backend/access/common/reloptions.c
new file mode 100644
index bc6911e..ee76558
*** a/src/backend/access/common/reloptions.c
--- b/src/backend/access/common/reloptions.c
*************** static relopt_bool boolRelOpts[] =
*** 62,67 ****
--- 62,75 ----
},
{
{
+ "randomization",
+ "Radomize GiST insertions for bloat reducing",
+ RELOPT_KIND_GIST
+ },
+ true
+ },
+ {
+ {
"fastupdate",
"Enables \"fast update\" feature for this GIN index",
RELOPT_KIND_GIN
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
new file mode 100644
index 9c6625b..72372e2
*** a/src/backend/access/gist/gist.c
--- b/src/backend/access/gist/gist.c
*************** initGISTstate(Relation index)
*** 1309,1314 ****
--- 1309,1315 ----
MemoryContext scanCxt;
MemoryContext oldCxt;
int i;
+ GiSTOptions *options = (GiSTOptions *) index->rd_options;
/* safety check to protect fixed-size arrays in GISTSTATE */
if (index->rd_att->natts > INDEX_MAX_KEYS)
*************** initGISTstate(Relation index)
*** 1326,1331 ****
--- 1327,1337 ----
/* Create and fill in the GISTSTATE */
giststate = (GISTSTATE *) palloc(sizeof(GISTSTATE));
+ /* Randomization option is true by default */
+ if (options)
+ giststate->randomization = options->randomization;
+ else
+ giststate->randomization = true;
giststate->scanCxt = scanCxt;
giststate->tempCxt = scanCxt; /* caller must change this if needed */
giststate->tupdesc = index->rd_att;
diff --git a/src/backend/access/gist/gistbuildbuffers.c b/src/backend/access/gist/gistbuildbuffers.c
new file mode 100644
index fc99976..fa42aa6
*** a/src/backend/access/gist/gistbuildbuffers.c
--- b/src/backend/access/gist/gistbuildbuffers.c
*************** gistRelocateBuildBuffersOnSplit(GISTBuil
*** 547,552 ****
--- 547,553 ----
IndexTuple itup;
int splitPagesCount = 0,
i;
+ int *relocationBuffersIndexes;
GISTENTRY entry[INDEX_MAX_KEYS];
bool isnull[INDEX_MAX_KEYS];
GISTNodeBuffer oldBuf;
*************** gistRelocateBuildBuffersOnSplit(GISTBuil
*** 594,599 ****
--- 595,606 ----
splitPagesCount);
/*
+ * Allocate memory for buffers indexes if randomization is required.
+ */
+ if (giststate->randomization)
+ relocationBuffersIndexes = (int *)palloc(sizeof(int) * splitPagesCount);
+
+ /*
* Fill relocation buffers information for node buffers of pages produced
* by split.
*/
*************** gistRelocateBuildBuffersOnSplit(GISTBuil
*** 631,637 ****
* or, in the case of a tie, the lowest penalty for the earliest column
* that is not tied.
*
! * The page searching logic is very similar to gistchoose().
*/
while (gistPopItupFromNodeBuffer(gfbb, &oldBuf, &itup))
{
--- 638,646 ----
* or, in the case of a tie, the lowest penalty for the earliest column
* that is not tied.
*
! * The page searching logic is very similar to gistchoose(). If
! * randomization is required then node buffers are visited in random order
! * for each relocated index tuple.
*/
while (gistPopItupFromNodeBuffer(gfbb, &oldBuf, &itup))
{
*************** gistRelocateBuildBuffersOnSplit(GISTBuil
*** 654,671 ****
*/
best_penalty[0] = -1;
/*
* Loop over possible target pages, looking for one to move this tuple
* to.
*/
for (i = 0; i < splitPagesCount; i++)
{
! RelocationBufferInfo *splitPageInfo = &relocationBuffersInfos[i];
bool zero_penalty;
int j;
zero_penalty = true;
/* Loop over index attributes. */
for (j = 0; j < r->rd_att->natts; j++)
{
--- 663,712 ----
*/
best_penalty[0] = -1;
+ if (giststate->randomization)
+ {
+ /*
+ * If randomization is required then prepare array of buffer indexes
+ * in order to remember which buffers were already examined.
+ */
+ for (i = 0; i < splitPagesCount; i++)
+ relocationBuffersIndexes[i] = i;
+ }
+
/*
* Loop over possible target pages, looking for one to move this tuple
* to.
*/
for (i = 0; i < splitPagesCount; i++)
{
! RelocationBufferInfo *splitPageInfo;
bool zero_penalty;
int j;
+ int bufferIndex;
zero_penalty = true;
+ if (giststate->randomization)
+ {
+ /*
+ * Randomization: select random buffer index from those which
+ * aren't previously selected.
+ */
+ int rnd_i, tmp;
+ rnd_i = random() % (splitPagesCount - i) + i;
+ tmp = relocationBuffersIndexes[rnd_i];
+ relocationBuffersIndexes[rnd_i] = relocationBuffersIndexes[i];
+ relocationBuffersIndexes[i] = tmp;
+ bufferIndex = relocationBuffersIndexes[i];
+ }
+ else
+ {
+ /* No randomization: select next buffer index. */
+ bufferIndex = i;
+ }
+
+ splitPageInfo = &relocationBuffersInfos[bufferIndex];
+
/* Loop over index attributes. */
for (j = 0; j < r->rd_att->natts; j++)
{
*************** gistRelocateBuildBuffersOnSplit(GISTBuil
*** 690,696 ****
* as the best for all the remaining columns during
* subsequent loop iterations.
*/
! which = i;
best_penalty[j] = usize;
if (j < r->rd_att->natts - 1)
--- 731,737 ----
* as the best for all the remaining columns during
* subsequent loop iterations.
*/
! which = bufferIndex;
best_penalty[j] = usize;
if (j < r->rd_att->natts - 1)
diff --git a/src/backend/access/gist/gistutil.c b/src/backend/access/gist/gistutil.c
new file mode 100644
index efb650e..37e8c08
*** a/src/backend/access/gist/gistutil.c
--- b/src/backend/access/gist/gistutil.c
*************** gistchoose(Relation r, Page p, IndexTupl
*** 375,380 ****
--- 375,381 ----
OffsetNumber result;
OffsetNumber maxoff;
OffsetNumber i;
+ OffsetNumber offsets[MaxOffsetNumber];
float best_penalty[INDEX_MAX_KEYS];
GISTENTRY entry,
identry[INDEX_MAX_KEYS];
*************** gistchoose(Relation r, Page p, IndexTupl
*** 407,417 ****
maxoff = PageGetMaxOffsetNumber(p);
Assert(maxoff >= FirstOffsetNumber);
! for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
! IndexTuple itup = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
! bool zero_penalty;
! int j;
zero_penalty = true;
--- 408,450 ----
maxoff = PageGetMaxOffsetNumber(p);
Assert(maxoff >= FirstOffsetNumber);
! if (giststate->randomization)
{
! /*
! * If randomization is required then prepare array of offset numbers
! * in order to remember which offset numbers were already exanimed.
! */
! for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
! offsets[i - FirstOffsetNumber] = i;
! }
!
! for (i = 0; i < maxoff; i++)
! {
! IndexTuple itup;
! bool zero_penalty;
! int j;
! OffsetNumber offset;
!
! if (giststate->randomization)
! {
! /*
! * Randomization: select random offset number from those which
! * aren't previously selected.
! */
! OffsetNumber rnd_i, tmp;
! rnd_i = random() % (maxoff - i) + i;
! tmp = offsets[rnd_i];
! offsets[rnd_i] = offsets[i];
! offsets[i] = tmp;
! offset = offsets[i];
! }
! else
! {
! /* No randomization: select next offset number */
! offset = i + FirstOffsetNumber;
! }
!
! itup = (IndexTuple) PageGetItem(p, PageGetItemId(p, offset));
zero_penalty = true;
*************** gistchoose(Relation r, Page p, IndexTupl
*** 424,430 ****
/* Compute penalty for this column. */
datum = index_getattr(itup, j + 1, giststate->tupdesc, &IsNull);
! gistdentryinit(giststate, j, &entry, datum, r, p, i,
FALSE, IsNull);
usize = gistpenalty(giststate, j, &entry, IsNull,
&identry[j], isnull[j]);
--- 457,463 ----
/* Compute penalty for this column. */
datum = index_getattr(itup, j + 1, giststate->tupdesc, &IsNull);
! gistdentryinit(giststate, j, &entry, datum, r, p, offset,
FALSE, IsNull);
usize = gistpenalty(giststate, j, &entry, IsNull,
&identry[j], isnull[j]);
*************** gistchoose(Relation r, Page p, IndexTupl
*** 441,447 ****
* adopt this tuple's penalty values as the best for all the
* remaining columns during subsequent loop iterations.
*/
! result = i;
best_penalty[j] = usize;
if (j < r->rd_att->natts - 1)
--- 474,480 ----
* adopt this tuple's penalty values as the best for all the
* remaining columns during subsequent loop iterations.
*/
! result = offset;
best_penalty[j] = usize;
if (j < r->rd_att->natts - 1)
*************** gistoptions(PG_FUNCTION_ARGS)
*** 723,729 ****
int numoptions;
static const relopt_parse_elt tab[] = {
{"fillfactor", RELOPT_TYPE_INT, offsetof(GiSTOptions, fillfactor)},
! {"buffering", RELOPT_TYPE_STRING, offsetof(GiSTOptions, bufferingModeOffset)}
};
options = parseRelOptions(reloptions, validate, RELOPT_KIND_GIST,
--- 756,763 ----
int numoptions;
static const relopt_parse_elt tab[] = {
{"fillfactor", RELOPT_TYPE_INT, offsetof(GiSTOptions, fillfactor)},
! {"buffering", RELOPT_TYPE_STRING, offsetof(GiSTOptions, bufferingModeOffset)},
! {"randomization", RELOPT_TYPE_BOOL, offsetof(GiSTOptions, randomization)}
};
options = parseRelOptions(reloptions, validate, RELOPT_KIND_GIST,
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h
new file mode 100644
index 1e8eabd..abc7ff1
*** a/src/include/access/gist_private.h
--- b/src/include/access/gist_private.h
*************** typedef struct GISTSTATE
*** 72,77 ****
--- 72,79 ----
FmgrInfo equalFn[INDEX_MAX_KEYS];
FmgrInfo distanceFn[INDEX_MAX_KEYS];
+ bool randomization;
+
/* Collations to pass to the support functions */
Oid supportCollation[INDEX_MAX_KEYS];
} GISTSTATE;
*************** typedef struct GiSTOptions
*** 402,407 ****
--- 404,410 ----
int32 vl_len_; /* varlena header (do not touch directly!) */
int fillfactor; /* page fill factor in percent (0..100) */
int bufferingModeOffset; /* use buffering build? */
+ bool randomization;
} GiSTOptions;
/* gist.c */