Compress GIN posting lists, for smaller index size.

GIN posting lists are now encoded using varbyte-encoding, which allows them
to fit in much smaller space than the straight ItemPointer array format used
before. The new encoding is used for both the lists stored in-line in entry
tree items, and in posting tree leaf pages.

To maintain backwards-compatibility and keep pg_upgrade working, the code
can still read old-style pages and tuples. Posting tree leaf pages in the
new format are flagged with GIN_COMPRESSED flag, to distinguish old and new
format pages. Likewise, entry tree tuples in the new format have a
GIN_ITUP_COMPRESSED flag set in a bit that was previously unused.

This patch bumps GIN_CURRENT_VERSION from 1 to 2. New indexes created with
version 9.4 will therefore have version number 2 in the metapage, while old
pg_upgraded indexes will have version 1. The code treats them the same, but
it might be come handy in the future, if we want to drop support for the
uncompressed format.

Alexander Korotkov and me. Reviewed by Tomas Vondra and Amit Langote.

1 files changed, 43 insertions, 24 deletions

diff --git a/src/backend/access/gin/gininsert.c b/src/backend/access/gin/gininsert.c
index 5e6f627a76b..cd9c7c120b3 100644
--- a/src/backend/access/gin/gininsert.c
+++ b/src/backend/access/gin/gininsert.c
@@ -53,31 +53,42 @@ addItemPointersToLeafTuple(GinState *ginstate,
 	Datum		key;
 	GinNullCategory category;
 	IndexTuple	res;
+	ItemPointerData *newItems,
+			   *oldItems;
+	int			oldNPosting,
+				newNPosting;
+	GinPostingList *compressedList;
 
 	Assert(!GinIsPostingTree(old));
 
 	attnum = gintuple_get_attrnum(ginstate, old);
 	key = gintuple_get_key(ginstate, old, &category);
 
-	/* try to build tuple with room for all the items */
-	res = GinFormTuple(ginstate, attnum, key, category,
-					   NULL, nitem + GinGetNPosting(old),
-					   false);
+	/* merge the old and new posting lists */
+	oldItems = ginReadTuple(ginstate, attnum, old, &oldNPosting);
 
-	if (res)
+	newNPosting = oldNPosting + nitem;
+	newItems = (ItemPointerData *) palloc(sizeof(ItemPointerData) * newNPosting);
+
+	newNPosting = ginMergeItemPointers(newItems,
+									   items, nitem,
+									   oldItems, oldNPosting);
+
+	/* Compress the posting list, and try to a build tuple with room for it */
+	res = NULL;
+	compressedList = ginCompressPostingList(newItems, newNPosting, GinMaxItemSize,
+											NULL);
+	pfree(newItems);
+	if (compressedList)
 	{
-		/* good, small enough */
-		uint32		newnitem;
-
-		/* fill in the posting list with union of old and new TIDs */
-		newnitem = ginMergeItemPointers(GinGetPosting(res),
-										GinGetPosting(old),
-										GinGetNPosting(old),
-										items, nitem);
-		/* merge might have eliminated some duplicate items */
-		GinShortenTuple(res, newnitem);
+		res = GinFormTuple(ginstate, attnum, key, category,
+						   (char *) compressedList,
+						   SizeOfGinPostingList(compressedList),
+						   newNPosting,
+						   false);
+		pfree(compressedList);
 	}
-	else
+	if (!res)
 	{
 		/* posting list would be too big, convert to posting tree */
 		BlockNumber postingRoot;
@@ -88,8 +99,8 @@ addItemPointersToLeafTuple(GinState *ginstate,
 		 * already be in order with no duplicates.
 		 */
 		postingRoot = createPostingTree(ginstate->index,
-										GinGetPosting(old),
-										GinGetNPosting(old),
+										oldItems,
+										oldNPosting,
 										buildStats);
 
 		/* Now insert the TIDs-to-be-added into the posting tree */
@@ -98,9 +109,10 @@ addItemPointersToLeafTuple(GinState *ginstate,
 							  buildStats);
 
 		/* And build a new posting-tree-only result tuple */
-		res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, true);
+		res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, 0, true);
 		GinSetPostingTree(res, postingRoot);
 	}
+	pfree(oldItems);
 
 	return res;
 }
@@ -119,12 +131,19 @@ buildFreshLeafTuple(GinState *ginstate,
 					ItemPointerData *items, uint32 nitem,
 					GinStatsData *buildStats)
 {
-	IndexTuple	res;
+	IndexTuple	res = NULL;
+	GinPostingList *compressedList;
 
 	/* try to build a posting list tuple with all the items */
-	res = GinFormTuple(ginstate, attnum, key, category,
-					   items, nitem, false);
-
+	compressedList = ginCompressPostingList(items, nitem, GinMaxItemSize, NULL);
+	if (compressedList)
+	{
+		res = GinFormTuple(ginstate, attnum, key, category,
+						   (char *) compressedList,
+						   SizeOfGinPostingList(compressedList),
+						   nitem, false);
+		pfree(compressedList);
+	}
 	if (!res)
 	{
 		/* posting list would be too big, build posting tree */
@@ -134,7 +153,7 @@ buildFreshLeafTuple(GinState *ginstate,
 		 * Build posting-tree-only result tuple.  We do this first so as to
 		 * fail quickly if the key is too big.
 		 */
-		res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, true);
+		res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, 0, true);
 
 		/*
 		 * Initialize a new posting tree with the TIDs.