v20250307-0003-Merge-GinTuples-during-tuplesort-before-fl.patch

From 2c41e560658e85fb507fdb20e492b392b8515ea5 Mon Sep 17 00:00:00 2001
From: Matthias van de Meent <boekewurm+postgres@gmail.com>
Date: Thu, 6 Mar 2025 02:25:18 +0100
Subject: [PATCH v20250307 3/4] Merge GinTuples during tuplesort before
 flushing to disk

This reduces on-disk size of the data, and increases the behaviour
of our tuplesort when we have to flush to disk relatively frequently.

In passing we also improve GinBuffer's merging of GinTuples to
use direct-to-buffer decoding of posting lists. Previously this
decoding would always allocate a new temporary array, but with
these changes we don't have to re-allocate this data and move
it around.

When we have overlapping TID ranges we still allocate the arrays,
but that's much rarer than non-overlapping TID ranges, thus in
general improving performance.
---
 src/include/access/gin_private.h           |   2 +
 src/include/access/gin_tuple.h             |  10 +
 src/backend/access/gin/gininsert.c         | 411 +++++++++++++++++----
 src/backend/access/gin/ginpostinglist.c    |  67 ++++
 src/backend/utils/sort/tuplesortvariants.c |  93 ++++-
 src/tools/pgindent/typedefs.list           |   1 +
 6 files changed, 507 insertions(+), 77 deletions(-)

diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index 95d8805b66f..681cc30fe71 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -476,6 +476,8 @@ extern GinPostingList *ginCompressPostingList(const ItemPointer ipd, int nipd,
 											  int maxsize, int *nwritten);
 extern int	ginPostingListDecodeAllSegmentsToTbm(GinPostingList *ptr, int len, TIDBitmap *tbm);
 
+extern void ginPostingListDecodeAllSegmentsInto(GinPostingList *segment, int len,
+												ItemPointer out, int nptrs);
 extern ItemPointer ginPostingListDecodeAllSegments(GinPostingList *segment, int len,
 												   int *ndecoded_out);
 extern ItemPointer ginPostingListDecode(GinPostingList *plist, int *ndecoded_out);
diff --git a/src/include/access/gin_tuple.h b/src/include/access/gin_tuple.h
index ce555031335..309427646f2 100644
--- a/src/include/access/gin_tuple.h
+++ b/src/include/access/gin_tuple.h
@@ -39,6 +39,16 @@ GinTupleGetFirst(GinTuple *tup)
 	return &list->first;
 }
 
+typedef struct GinBuffer GinBuffer;
+
 extern int	_gin_compare_tuples(GinTuple *a, GinTuple *b, SortSupport ssup);
 
+extern GinBuffer *GinBufferInit(Relation index);
+extern bool GinBufferIsEmpty(GinBuffer *buffer);
+extern bool GinBufferCanAddKey(GinBuffer *buffer, GinTuple *tup);
+extern void GinBufferReset(GinBuffer *buffer);
+extern void GinBufferFree(GinBuffer *buffer);
+extern void GinBufferStoreOrMergeTuple(GinBuffer *buffer, GinTuple *tup);
+extern GinTuple *GinBufferBuildTuple(GinBuffer *buffer);
+
 #endif							/* GIN_TUPLE_H */
diff --git a/src/backend/access/gin/gininsert.c b/src/backend/access/gin/gininsert.c
index f5782ea95df..80cabae99b1 100644
--- a/src/backend/access/gin/gininsert.c
+++ b/src/backend/access/gin/gininsert.c
@@ -191,6 +191,8 @@ static void _gin_parallel_scan_and_build(GinBuildState *buildstate,
 										 int sortmem, bool progress);
 
 static ItemPointer _gin_parse_tuple_items(GinTuple *a);
+static void _gin_parse_tuple_items_into(GinTuple *a, ItemPointer items,
+										int nspace);
 static Datum _gin_parse_tuple_key(GinTuple *a);
 
 static GinTuple *_gin_build_tuple(OffsetNumber attrnum, unsigned char category,
@@ -1141,9 +1143,23 @@ _gin_parallel_heapscan(GinBuildState *state)
  * When adding TIDs to the buffer, we make sure to keep them sorted, both
  * during the initial table scan (and detecting when the scan wraps around),
  * and during merging (where we do mergesort).
+ *
+ * Note: When nitems == 0, we may still have a cached GinTuple that holds
+ * many items.
+ * We don't always deserialize the cached GinTuple, as deserializing and
+ * then serializing this data while we're in tuplesort code can be quite
+ * expensive, especially while we don't know if the next tuple actually needs
+ * to be merged into this tuple: The cached tuple could just as well be written
+ * as-is to the tape without any further modifications.
  */
-typedef struct GinBuffer
+struct GinBuffer
 {
+	/*
+	 * The memory context holds the dynamic allocation of items, key, cached,
+	 * and any GinTuple returned from GinBufferBuildTuple.
+	 */
+	MemoryContext context;
+	GinTuple   *cached;			/* copy of previous GIN tuple, if any */
 	OffsetNumber attnum;
 	GinNullCategory category;
 	Datum		key;			/* 0 if no key (and keylen == 0) */
@@ -1161,7 +1177,7 @@ typedef struct GinBuffer
 	int			nfrozen;
 	SortSupport ssup;			/* for sorting/comparing keys */
 	ItemPointerData *items;
-} GinBuffer;
+};
 
 /*
  * Check that TID array contains valid values, and that it's sorted (if we
@@ -1172,8 +1188,7 @@ AssertCheckItemPointers(GinBuffer *buffer)
 {
 #ifdef USE_ASSERT_CHECKING
 	/* we should not have a buffer with no TIDs to sort */
-	Assert(buffer->items != NULL);
-	Assert(buffer->nitems > 0);
+	Assert(buffer->nitems == 0 || buffer->items != NULL);
 
 	for (int i = 0; i < buffer->nitems; i++)
 	{
@@ -1199,14 +1214,17 @@ AssertCheckGinBuffer(GinBuffer *buffer)
 {
 #ifdef USE_ASSERT_CHECKING
 	/* if we have any items, the array must exist */
-	Assert(!((buffer->nitems > 0) && (buffer->items == NULL)));
+	Assert((buffer->nitems == 0) || (buffer->items != NULL));
 
 	/*
 	 * The buffer may be empty, in which case we must not call the check of
 	 * item pointers, because that assumes non-emptiness.
 	 */
 	if (buffer->nitems == 0)
+	{
+		Assert(buffer->nfrozen == 0);
 		return;
+	}
 
 	/* Make sure the item pointers are valid and sorted. */
 	AssertCheckItemPointers(buffer);
@@ -1223,7 +1241,7 @@ AssertCheckGinBuffer(GinBuffer *buffer)
  *
  * Initializes sort support procedures for all index attributes.
  */
-static GinBuffer *
+GinBuffer *
 GinBufferInit(Relation index)
 {
 	GinBuffer  *buffer = palloc0(sizeof(GinBuffer));
@@ -1286,15 +1304,18 @@ GinBufferInit(Relation index)
 
 		PrepareSortSupportComparisonShim(cmpFunc, sortKey);
 	}
+	buffer->context = GenerationContextCreate(CurrentMemoryContext,
+											  "Gin Buffer",
+											  ALLOCSET_DEFAULT_SIZES);
 
 	return buffer;
 }
 
 /* Is the buffer empty, i.e. has no TID values in the array? */
-static bool
+bool
 GinBufferIsEmpty(GinBuffer *buffer)
 {
-	return (buffer->nitems == 0);
+	return (buffer->nitems == 0 && buffer->cached == NULL);
 }
 
 /*
@@ -1310,37 +1331,81 @@ GinBufferIsEmpty(GinBuffer *buffer)
 static bool
 GinBufferKeyEquals(GinBuffer *buffer, GinTuple *tup)
 {
+	MemoryContext prev;
 	int			r;
+	AttrNumber	attnum;
 	Datum		tupkey;
+	Datum		bufkey;
 
 	AssertCheckGinBuffer(buffer);
 
-	if (tup->attrnum != buffer->attnum)
-		return false;
+	/*
+	 * If we have a cached GinTuple, compare against its stored info, as
+	 * we haven't yet populated the GinBuffer with its data.
+	 */
+	if (buffer->cached)
+	{
+		GinTuple   *cached = buffer->cached;
 
-	/* same attribute should have the same type info */
-	Assert(tup->typbyval == buffer->typbyval);
-	Assert(tup->typlen == buffer->typlen);
+		if (tup->attrnum != cached->attrnum)
+			return false;
 
-	if (tup->category != buffer->category)
-		return false;
+		Assert(tup->typbyval == cached->typbyval);
+		Assert(tup->typlen == cached->typlen);
 
-	/*
-	 * For NULL/empty keys, this means equality, for normal keys we need to
-	 * compare the actual key value.
-	 */
-	if (buffer->category != GIN_CAT_NORM_KEY)
-		return true;
+		if (tup->category != cached->category)
+			return false;
+
+		/*
+		 * For NULL/empty keys, this means equality, for normal keys we need
+		 * to compare the actual key value.
+		 */
+		if (cached->category != GIN_CAT_NORM_KEY)
+			return true;
+
+		attnum = cached->attrnum;
+		bufkey = _gin_parse_tuple_key(cached);
+	}
+	else
+	{
+		if (tup->attrnum != buffer->attnum)
+			return false;
+
+		/* same attribute should have the same type info */
+		Assert(tup->typbyval == buffer->typbyval);
+		Assert(tup->typlen == buffer->typlen);
+
+		if (tup->category != buffer->category)
+			return false;
+
+		/*
+		 * For NULL/empty keys, this means equality, for normal keys we need to
+		 * compare the actual key value.
+		 */
+		if (buffer->category != GIN_CAT_NORM_KEY)
+			return true;
+		attnum = buffer->attnum;
+		bufkey = buffer->key;
+	}
 
 	/*
 	 * For the tuple, get either the first sizeof(Datum) bytes for byval
 	 * types, or a pointer to the beginning of the data array.
 	 */
-	tupkey = (buffer->typbyval) ? *(Datum *) tup->data : PointerGetDatum(tup->data);
+	tupkey = _gin_parse_tuple_key(tup);
 
-	r = ApplySortComparator(buffer->key, false,
+	/*
+	 * We can be called from within TupleSort territories, which requires
+	 * us to not allocate in its memory context. To comply with that
+	 * requirement, use the buffer context instead.
+	 */
+	prev = MemoryContextSwitchTo(buffer->context);
+
+	r = ApplySortComparator(bufkey, false,
 							tupkey, false,
-							&buffer->ssup[buffer->attnum - 1]);
+							&buffer->ssup[attnum - 1]);
+
+	MemoryContextSwitchTo(prev);
 
 	return (r == 0);
 }
@@ -1372,6 +1437,8 @@ GinBufferKeyEquals(GinBuffer *buffer, GinTuple *tup)
 static bool
 GinBufferShouldTrim(GinBuffer *buffer, GinTuple *tup)
 {
+	Assert(!buffer->cached);
+
 	/* not enough TIDs to trim (1024 is somewhat arbitrary number) */
 	if (buffer->nfrozen < 1024)
 		return false;
@@ -1388,7 +1455,72 @@ GinBufferShouldTrim(GinBuffer *buffer, GinTuple *tup)
 }
 
 /*
- * GinBufferStoreTuple
+ * Unpack the buffered tuple: we're about to use or merge
+ * the contained TIDs or data.
+ */
+static void
+GinBufferUnpackCached(GinBuffer *buffer, int reserve_space)
+{
+	Datum		key;
+	GinTuple   *cached;
+	int			totitems;
+
+	Assert(buffer->cached != NULL);
+	Assert(buffer->nitems == 0);
+
+	cached = buffer->cached;
+	totitems = cached->nitems + reserve_space;
+	key = _gin_parse_tuple_key(cached);
+
+	buffer->category = cached->category;
+	buffer->keylen = cached->keylen;
+	buffer->attnum = cached->attrnum;
+
+	buffer->typlen = cached->typlen;
+	buffer->typbyval = cached->typbyval;
+
+	if (cached->category == GIN_CAT_NORM_KEY)
+		buffer->key = datumCopy(key, buffer->typbyval, buffer->typlen);
+	else
+		buffer->key = (Datum) 0;
+
+	/*
+	 * Ensure we can unpack all item pointers into the buffer's item array.
+	 */
+	if (buffer->items == NULL)
+	{
+		Size	maxitems = Max(buffer->maxitems, totitems);
+		buffer->items = palloc0(maxitems * sizeof(ItemPointerData));
+		buffer->maxitems = maxitems;
+	}
+	else if (buffer->maxitems < totitems)
+	{
+		buffer->items = repalloc(buffer->items,
+								 totitems * sizeof(ItemPointerData));
+		buffer->maxitems = totitems;
+	}
+	else
+	{
+		Assert(PointerIsValid(buffer->items) &&
+			   buffer->maxitems >= totitems);
+	}
+
+	/* Unpack the item pointers directly into the buffer's items array */
+	_gin_parse_tuple_items_into(cached, buffer->items,
+								buffer->maxitems);
+
+	buffer->nitems = cached->nitems;
+	buffer->nfrozen = 1;
+
+	buffer->cached = NULL;
+
+	AssertCheckItemPointers(buffer);
+
+	pfree(cached);
+}
+
+/*
+ * GinBufferStoreOrMergeTuple
  *		Add data (especially TID list) from a GIN tuple to the buffer.
  *
  * The buffer is expected to be empty (in which case it's initialized), or
@@ -1410,31 +1542,42 @@ GinBufferShouldTrim(GinBuffer *buffer, GinTuple *tup)
  * workers. But the workers merge the items as much as possible, so there
  * should not be too many.
  */
-static void
-GinBufferStoreTuple(GinBuffer *buffer, GinTuple *tup)
+void
+GinBufferStoreOrMergeTuple(GinBuffer *buffer, GinTuple *tup)
 {
-	ItemPointerData *items;
-	Datum		key;
+	MemoryContext prev;
 
+	prev = MemoryContextSwitchTo(buffer->context);
 	AssertCheckGinBuffer(buffer);
 
-	key = _gin_parse_tuple_key(tup);
-	items = _gin_parse_tuple_items(tup);
-
 	/* if the buffer is empty, set the fields (and copy the key) */
-	if (GinBufferIsEmpty(buffer))
+	if (buffer->nitems == 0 && buffer->cached == NULL)
 	{
-		buffer->category = tup->category;
-		buffer->keylen = tup->keylen;
-		buffer->attnum = tup->attrnum;
+		/*
+		 * Buffer is actually empty, so move the GinTuple into the right
+		 * context and then put it away for later use
+		 */
+		GinTuple   *tuple = palloc(tup->tuplen);
 
-		buffer->typlen = tup->typlen;
-		buffer->typbyval = tup->typbyval;
+		memcpy(tuple, tup, tup->tuplen);
+		buffer->cached = tuple;
+		MemoryContextSwitchTo(prev);
+		return;
+	}
 
-		if (tup->category == GIN_CAT_NORM_KEY)
-			buffer->key = datumCopy(key, buffer->typbyval, buffer->typlen);
-		else
-			buffer->key = (Datum) 0;
+	if (buffer->nitems == 0)
+	{
+		Assert(buffer->cached);
+		/*
+		 * We skipped decoding the previous GIN tuple, but now we definitely
+		 * need to merge the tuples, so we can't stave off deforming the
+		 * cached GIN tuple any longer.
+		 */
+		GinBufferUnpackCached(buffer, tup->nitems);
+		
+		Assert(buffer->nitems > 0);
+		Assert(buffer->nfrozen == 1);
+		Assert(buffer->cached == NULL);
 	}
 
 	/*
@@ -1453,7 +1596,7 @@ GinBufferStoreTuple(GinBuffer *buffer, GinTuple *tup)
 	 */
 	if ((buffer->nitems > 0) &&
 		(ItemPointerCompare(&buffer->items[buffer->nitems - 1],
-							GinTupleGetFirst(tup)) == 0))
+							GinTupleGetFirst(tup)) <= 0))
 		buffer->nfrozen = buffer->nitems;
 
 	/*
@@ -1479,54 +1622,142 @@ GinBufferStoreTuple(GinBuffer *buffer, GinTuple *tup)
 		buffer->nfrozen++;
 	}
 
-	/* add the new TIDs into the buffer, combine using merge-sort */
+	/*
+	 * Grow the buffer if we need to.
+	 */
+	if (buffer->nitems + tup->nitems > buffer->maxitems)
+	{
+		Size	size = sizeof(ItemPointerData) * (buffer->nitems + tup->nitems);
+		if (buffer->items == NULL)
+			buffer->items = palloc(size);
+		else
+			buffer->items = repalloc(buffer->items, size);
+
+		buffer->maxitems = (buffer->nitems + tup->nitems);
+	}
+
+	Assert(buffer->maxitems >= buffer->nitems + tup->nitems);
+
+	/* Add the new TIDs into the buffer, combine using merge-sort if needed */
 	{
 		int			nnew;
 		ItemPointer new;
 
 		/*
-		 * Resize the array - we do this first, because we'll dereference the
-		 * first unfrozen TID, which would fail if the array is NULL. We'll
-		 * still pass 0 as number of elements in that array though.
+		 * If the array wasn't allocated yet, do so now.
+		 *
+		 * Note that by now we know that buffer->maxitems is large enough to
+		 * fit all tuples, so we only need to allocate the data.
 		 */
 		if (buffer->items == NULL)
-			buffer->items = palloc((buffer->nitems + tup->nitems) * sizeof(ItemPointerData));
+		{
+			Assert(buffer->nitems == 0);
+			Assert(buffer->nfrozen == 0);
+
+			buffer->items = palloc(buffer->maxitems * sizeof(ItemPointerData));
+		}
+
+		/*
+		 * If the incoming data is completely after the current items, we can
+		 * just decode the TIDs directly into the buffer's items array, saving
+		 * allocations and memcpy's.
+		 */
+		if (likely(buffer->nfrozen == buffer->nitems))
+		{
+			_gin_parse_tuple_items_into(tup, &buffer->items[buffer->nitems],
+										buffer->maxitems - buffer->nitems);
+		}
 		else
-			buffer->items = repalloc(buffer->items,
-									 (buffer->nitems + tup->nitems) * sizeof(ItemPointerData));
+		{
+			ItemPointerData *items;
+			Assert(buffer->nfrozen < buffer->nitems);
+			items = _gin_parse_tuple_items(tup);
 
-		new = ginMergeItemPointers(&buffer->items[buffer->nfrozen], /* first unfronzen */
-								   (buffer->nitems - buffer->nfrozen),	/* num of unfrozen */
-								   items, tup->nitems, &nnew);
+			new = ginMergeItemPointers(&buffer->items[buffer->nfrozen], /* first unfronzen */
+									   (buffer->nitems - buffer->nfrozen),    /* num of unfrozen */
+									   items, tup->nitems, &nnew);
 
-		Assert(nnew == (tup->nitems + (buffer->nitems - buffer->nfrozen)));
+			Assert(nnew == (tup->nitems + (buffer->nitems - buffer->nfrozen)));
+			Assert(buffer->maxitems >= buffer->nfrozen + nnew);
 
-		memcpy(&buffer->items[buffer->nfrozen], new,
-			   nnew * sizeof(ItemPointerData));
+			memcpy(&buffer->items[buffer->nfrozen], new,
+				   nnew * sizeof(ItemPointerData));
 
-		pfree(new);
+			pfree(new);
+			/* free the decompressed TID list */
+			pfree(items);
+		}
 
 		buffer->nitems += tup->nitems;
+		/*
+		 * The first TID of the incoming item is the lowest we'll see
+		 * in this run, so we can always mark that one as frozen.
+		 */
+		buffer->nfrozen++;
 
+		/* Check the data is still consistent */
 		AssertCheckItemPointers(buffer);
 	}
 
-	/* free the decompressed TID list */
-	pfree(items);
+	MemoryContextSwitchTo(prev);
+}
+
+/*
+ * Build a GinTuple from the buffer's contents.
+ *
+ * On exit, the buffer has been reset.
+ */
+GinTuple *
+GinBufferBuildTuple(GinBuffer *buffer)
+{
+	MemoryContext prev = MemoryContextSwitchTo(buffer->context);
+	GinTuple   *result;
+
+	if (buffer->cached)
+	{
+		Assert(buffer->nitems == 0);
+		result = buffer->cached;
+		buffer->cached = NULL;
+	}
+	else
+	{
+		result = _gin_build_tuple(buffer->attnum, buffer->category,
+								  buffer->key, buffer->typlen,
+								  buffer->typbyval, buffer->items,
+								  buffer->nitems);
+
+		GinBufferReset(buffer);
+	}
+
+	MemoryContextSwitchTo(prev);
+	return result;
 }
 
 /*
  * GinBufferReset
  *		Reset the buffer into a state as if it contains no data.
  */
-static void
+void
 GinBufferReset(GinBuffer *buffer)
 {
 	Assert(!GinBufferIsEmpty(buffer));
 
-	/* release byref values, do nothing for by-val ones */
-	if ((buffer->category == GIN_CAT_NORM_KEY) && !buffer->typbyval)
-		pfree(DatumGetPointer(buffer->key));
+	/* release cached buffer tuple, if present */
+	if (buffer->cached)
+	{
+		Assert(buffer->nitems == 0);
+		pfree(buffer->cached);
+		buffer->cached = NULL;
+	}
+	else
+	{
+		/* release byref values, do nothing for by-val ones */
+		if ((buffer->category == GIN_CAT_NORM_KEY) && !buffer->typbyval
+			&& PointerIsValid(DatumGetPointer(buffer->key)))
+		{
+			pfree(DatumGetPointer(buffer->key));
+		}
+	}
 
 	/*
 	 * Not required, but makes it more likely to trigger NULL derefefence if
@@ -1542,6 +1773,14 @@ GinBufferReset(GinBuffer *buffer)
 
 	buffer->typlen = 0;
 	buffer->typbyval = 0;
+
+	/*
+	 * We don't reset the memory context, as that contains the items array,
+	 * which we don't want to have to re-allocate every time it gets huge.
+	 *
+	 * That's not all that likely, but still too expensive to do repeatedly
+	 * inside tuplesort code.
+	 */
 }
 
 /*
@@ -1565,7 +1804,7 @@ GinBufferTrim(GinBuffer *buffer)
  * GinBufferFree
  *		Release memory associated with the GinBuffer (including TID array).
  */
-static void
+void
 GinBufferFree(GinBuffer *buffer)
 {
 	if (buffer->items)
@@ -1576,6 +1815,7 @@ GinBufferFree(GinBuffer *buffer)
 		(buffer->category == GIN_CAT_NORM_KEY) && !buffer->typbyval)
 		pfree(DatumGetPointer(buffer->key));
 
+	MemoryContextDelete(buffer->context);
 	pfree(buffer);
 }
 
@@ -1585,7 +1825,7 @@ GinBufferFree(GinBuffer *buffer)
  *
  * Returns true if the buffer is either empty or for the same index key.
  */
-static bool
+bool
 GinBufferCanAddKey(GinBuffer *buffer, GinTuple *tup)
 {
 	/* empty buffer can accept data for any key */
@@ -1682,6 +1922,7 @@ _gin_parallel_merge(GinBuildState *state)
 			 * GinTuple.
 			 */
 			AssertCheckItemPointers(buffer);
+			Assert(!PointerIsValid(buffer->cached));
 
 			ginEntryInsert(&state->ginstate,
 						   buffer->attnum, buffer->key, buffer->category,
@@ -1708,6 +1949,7 @@ _gin_parallel_merge(GinBuildState *state)
 			 * GinTuple.
 			 */
 			AssertCheckItemPointers(buffer);
+			Assert(!PointerIsValid(buffer->cached));
 
 			ginEntryInsert(&state->ginstate,
 						   buffer->attnum, buffer->key, buffer->category,
@@ -1721,7 +1963,11 @@ _gin_parallel_merge(GinBuildState *state)
 		 * Remember data for the current tuple (either remember the new key,
 		 * or append if to the existing data).
 		 */
-		GinBufferStoreTuple(buffer, tup);
+		GinBufferStoreOrMergeTuple(buffer, tup);
+
+		/* Unpack the cached tuple, if it got cached */
+		if (buffer->cached)
+			GinBufferUnpackCached(buffer, 0);
 
 		/* Report progress */
 		pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
@@ -1732,6 +1978,7 @@ _gin_parallel_merge(GinBuildState *state)
 	if (!GinBufferIsEmpty(buffer))
 	{
 		AssertCheckItemPointers(buffer);
+		Assert(!PointerIsValid(buffer->cached));
 
 		ginEntryInsert(&state->ginstate,
 					   buffer->attnum, buffer->key, buffer->category,
@@ -1871,6 +2118,9 @@ _gin_process_worker_data(GinBuildState *state, Tuplesortstate *worker_sort,
 			GinBufferReset(buffer);
 		}
 
+		if (buffer->cached)
+			GinBufferUnpackCached(buffer, tup->nitems);
+
 		/*
 		 * We're about to add a GIN tuple to the buffer - check the memory
 		 * limit first, and maybe write out some of the data into the index
@@ -1907,7 +2157,7 @@ _gin_process_worker_data(GinBuildState *state, Tuplesortstate *worker_sort,
 		 * Remember data for the current tuple (either remember the new key,
 		 * or append if to the existing data).
 		 */
-		GinBufferStoreTuple(buffer, tup);
+		GinBufferStoreOrMergeTuple(buffer, tup);
 	}
 
 	/* flush data remaining in the buffer (for the last key) */
@@ -2351,17 +2601,36 @@ _gin_parse_tuple_items(GinTuple *a)
 {
 	int			len;
 	char	   *ptr;
-	int			ndecoded;
 	ItemPointer items;
 
 	len = a->tuplen - SHORTALIGN(offsetof(GinTuple, data) + a->keylen);
 	ptr = (char *) a + SHORTALIGN(offsetof(GinTuple, data) + a->keylen);
 
-	items = ginPostingListDecodeAllSegments((GinPostingList *) ptr, len, &ndecoded);
+	items = palloc(a->nitems * sizeof(ItemPointerData));
+
+	ginPostingListDecodeAllSegmentsInto((GinPostingList *) ptr, len,
+										items, a->nitems);
+
+	return items;
+}
+
+/*
+* _gin_parse_tuple_items_into
+ *		Decompress GinTuple's TIDs into the given TID array.
+ */
+static void
+_gin_parse_tuple_items_into(GinTuple *a, ItemPointer items, int nspace)
+{
+	int			len;
+	char	   *ptr;
+
+	Assert(nspace >= a->nitems && PointerIsValid(items));
 
-	Assert(ndecoded == a->nitems);
+	len = a->tuplen - SHORTALIGN(offsetof(GinTuple, data) + a->keylen);
+	ptr = (char *) a + SHORTALIGN(offsetof(GinTuple, data) + a->keylen);
 
-	return (ItemPointer) items;
+	ginPostingListDecodeAllSegmentsInto((GinPostingList *) ptr, len,
+										items, a->nitems);
 }
 
 /*
diff --git a/src/backend/access/gin/ginpostinglist.c b/src/backend/access/gin/ginpostinglist.c
index 48eadec87b0..671d1009a11 100644
--- a/src/backend/access/gin/ginpostinglist.c
+++ b/src/backend/access/gin/ginpostinglist.c
@@ -288,6 +288,73 @@ ginPostingListDecode(GinPostingList *plist, int *ndecoded_out)
 										   ndecoded_out);
 }
 
+/*
+ * Decode compressed posting lists into a pre-allocated array of item
+ * pointers.
+ * The posting lists must contain a total of exactly nptrs item pointers.
+ *
+ * See also ginPostingListDecodeAllSegments, which allocates a new
+ * item pointer array.
+ */
+void
+ginPostingListDecodeAllSegmentsInto(GinPostingList *segment, int len,
+									ItemPointer out, int nptrs)
+{
+	uint64		val;
+	char	   *endseg = ((char *) segment) + len;
+	int			ndecoded;
+	unsigned char *ptr;
+	unsigned char *endptr;
+
+	ndecoded = 0;
+
+	while ((char *) segment < endseg)
+	{
+		/* enlarge output array if needed */
+		if (ndecoded >= nptrs)
+		{
+			elog(ERROR,
+				 "Too many items to decode, expected %u, now at %u and counting",
+				 nptrs, ndecoded);
+		}
+
+		/* copy the first item */
+		Assert(OffsetNumberIsValid(ItemPointerGetOffsetNumber(&segment->first)));
+		Assert(ndecoded == 0 || ginCompareItemPointers(&segment->first, &out[ndecoded - 1]) > 0);
+		out[ndecoded] = segment->first;
+		ndecoded++;
+
+		val = itemptr_to_uint64(&segment->first);
+		ptr = segment->bytes;
+		endptr = segment->bytes + segment->nbytes;
+		while (ptr < endptr)
+		{
+			/* enlarge output array if needed */
+			if (ndecoded >= nptrs)
+			{
+				unsigned int minremaining = ((endseg - (char *) ptr) / sizeof(ItemPointerData));
+
+				elog(ERROR,
+					 "Too many items to decode, expected %u, now at %u and counting",
+					 (unsigned int) nptrs,
+					 (unsigned int) ndecoded + minremaining);
+			}
+
+			val += decode_varbyte(&ptr);
+
+			uint64_to_itemptr(val, &out[ndecoded]);
+			ndecoded++;
+		}
+		segment = GinNextPostingListSegment(segment);
+	}
+	
+	if (ndecoded != nptrs)
+	{
+		elog(ERROR, "Invalid decode count: Expected %d, got %d",
+			 nptrs, ndecoded);
+	}
+}
+
 /*
  * Decode multiple posting list segments into an array of item pointers.
  * The number of items is returned in *ndecoded_out. The segments are stored
diff --git a/src/backend/utils/sort/tuplesortvariants.c b/src/backend/utils/sort/tuplesortvariants.c
index 79bd29aa90e..ff4e4405796 100644
--- a/src/backend/utils/sort/tuplesortvariants.c
+++ b/src/backend/utils/sort/tuplesortvariants.c
@@ -88,8 +88,11 @@ static void writetup_index_brin(Tuplesortstate *state, LogicalTape *tape,
 								SortTuple *stup);
 static void readtup_index_brin(Tuplesortstate *state, SortTuple *stup,
 							   LogicalTape *tape, unsigned int len);
-static void writetup_index_gin(Tuplesortstate *state, LogicalTape *tape,
-							   SortTuple *stup);
+static void writetup_index_gin_to_tape(Tuplesortstate *state,
+									   LogicalTape *tape, GinTuple *tuple);
+static void writetup_index_gin_buffered(Tuplesortstate *state,
+										LogicalTape *tape, SortTuple *stup);
+static void flushwrites_index_gin(Tuplesortstate *state, LogicalTape *tape);
 static void readtup_index_gin(Tuplesortstate *state, SortTuple *stup,
 							  LogicalTape *tape, unsigned int len);
 static int	comparetup_datum(const SortTuple *a, const SortTuple *b,
@@ -101,6 +104,7 @@ static void writetup_datum(Tuplesortstate *state, LogicalTape *tape,
 static void readtup_datum(Tuplesortstate *state, SortTuple *stup,
 						  LogicalTape *tape, unsigned int len);
 static void freestate_cluster(Tuplesortstate *state);
+static void freestate_index_gin(Tuplesortstate *state);
 
 /*
  * Data structure pointed by "TuplesortPublic.arg" for the CLUSTER case.  Set by
@@ -135,6 +139,16 @@ typedef struct
 	bool		uniqueNullsNotDistinct; /* unique constraint null treatment */
 } TuplesortIndexBTreeArg;
 
+/*
+ * Data structure pointed by "TuplesortPublic.arg" for the index_gin subcase.
+ */
+typedef struct
+{
+	TuplesortIndexArg index;
+	GinBuffer  *buffer;
+} TuplesortIndexGinArg;
+
+
 /*
  * Data structure pointed by "TuplesortPublic.arg" for the index_hash subcase.
  */
@@ -593,6 +607,7 @@ tuplesort_begin_index_gin(Relation heapRel,
 	Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
 												   sortopt);
 	TuplesortPublic *base = TuplesortstateGetPublic(state);
+	TuplesortIndexGinArg *arg;
 	MemoryContext oldcontext;
 	int			i;
 	TupleDesc	desc = RelationGetDescr(indexRel);
@@ -617,6 +632,10 @@ tuplesort_begin_index_gin(Relation heapRel,
 	/* Prepare SortSupport data for each column */
 	base->sortKeys = (SortSupport) palloc0(base->nKeys *
 										   sizeof(SortSupportData));
+	arg = palloc0(sizeof(TuplesortIndexGinArg));
+	arg->index.indexRel = indexRel;
+	arg->index.heapRel = heapRel;
+	arg->buffer = GinBufferInit(indexRel);
 
 	for (i = 0; i < base->nKeys; i++)
 	{
@@ -645,10 +664,12 @@ tuplesort_begin_index_gin(Relation heapRel,
 
 	base->removeabbrev = removeabbrev_index_gin;
 	base->comparetup = comparetup_index_gin;
-	base->writetup = writetup_index_gin;
+	base->writetup = writetup_index_gin_buffered;
+	base->flushwrites = flushwrites_index_gin;
 	base->readtup = readtup_index_gin;
+	base->freestate = freestate_index_gin;
 	base->haveDatum1 = false;
-	base->arg = NULL;
+	base->arg = arg;
 
 	MemoryContextSwitchTo(oldcontext);
 
@@ -1930,11 +1951,13 @@ comparetup_index_gin(const SortTuple *a, const SortTuple *b,
 							   base->sortKeys);
 }
 
+/*
+ * Write the GinTuple to the tape.
+ */
 static void
-writetup_index_gin(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
+writetup_index_gin_to_tape(Tuplesortstate *state, LogicalTape *tape, GinTuple *tuple)
 {
 	TuplesortPublic *base = TuplesortstateGetPublic(state);
-	GinTuple   *tuple = (GinTuple *) stup->tuple;
 	unsigned int tuplen = tuple->tuplen;
 
 	tuplen = tuplen + sizeof(tuplen);
@@ -1944,6 +1967,53 @@ writetup_index_gin(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
 		LogicalTapeWrite(tape, &tuplen, sizeof(tuplen));
 }
 
+/*
+ * Merge or write the tuple to the GinBuffer if possible, flushing any
+ * conflicting state to disk when and where required.
+ */
+static void
+writetup_index_gin_buffered(Tuplesortstate *state, LogicalTape *tape, SortTuple *stup)
+{
+	TuplesortPublic *base = TuplesortstateGetPublic(state);
+	GinTuple   *otup;
+	GinTuple   *ntup = (GinTuple *) stup->tuple;
+	TuplesortIndexGinArg *arg = (TuplesortIndexGinArg *) base->arg;
+
+	Assert(PointerIsValid(arg));
+
+	if (GinBufferCanAddKey(arg->buffer, ntup))
+	{
+		GinBufferStoreOrMergeTuple(arg->buffer, ntup);
+		return;
+	}
+
+	otup = GinBufferBuildTuple(arg->buffer);
+
+	writetup_index_gin_to_tape(state, tape, otup);
+
+	pfree(otup);
+
+	Assert(GinBufferCanAddKey(arg->buffer, ntup));
+
+	GinBufferStoreOrMergeTuple(arg->buffer, ntup);
+}
+
+static void
+flushwrites_index_gin(Tuplesortstate *state, LogicalTape *tape)
+{
+	TuplesortPublic *base = TuplesortstateGetPublic(state);
+	TuplesortIndexGinArg *arg = (TuplesortIndexGinArg *) base->arg;
+
+	if (!GinBufferIsEmpty(arg->buffer))
+	{
+		GinTuple   *tuple = GinBufferBuildTuple(arg->buffer);
+
+		writetup_index_gin_to_tape(state, tape, tuple);
+		pfree(tuple);
+		Assert(GinBufferIsEmpty(arg->buffer));
+	}
+}
+
 static void
 readtup_index_gin(Tuplesortstate *state, SortTuple *stup,
 				  LogicalTape *tape, unsigned int len)
@@ -1969,6 +2039,17 @@ readtup_index_gin(Tuplesortstate *state, SortTuple *stup,
 	stup->datum1 = (Datum) 0;
 }
 
+static void
+freestate_index_gin(Tuplesortstate *state)
+{
+	TuplesortPublic *base = TuplesortstateGetPublic(state);
+	TuplesortIndexGinArg *arg = (TuplesortIndexGinArg *) base->arg;
+
+	Assert(arg != NULL);
+	Assert(GinBufferIsEmpty(arg->buffer));
+	GinBufferFree(arg->buffer);
+}
+
 /*
  * Routines specialized for DatumTuple case
  */
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 9840060997f..522e98109ae 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -3037,6 +3037,7 @@ TuplesortClusterArg
 TuplesortDatumArg
 TuplesortIndexArg
 TuplesortIndexBTreeArg
+TuplesortIndexGinArg
 TuplesortIndexHashArg
 TuplesortInstrumentation
 TuplesortMethod
-- 
2.45.2