v5-0002-Experimental-support-for-unique-indexes.patch

From 7fd5af8b4767516c905d7cbbdc942e8d4643d025 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Sat, 27 Jul 2019 16:34:31 -0700
Subject: [PATCH v5 2/3] Experimental support for unique indexes.

I have written a pretty sloppy implementation of unique index support
for posting list compression, just to give us an idea of how it could be
done.  This seems to be a loss for performance, so it's unlikely to go
much further than this.
---
 src/backend/access/gist/gist.c        |  3 +-
 src/backend/access/hash/hashinsert.c  |  4 +-
 src/backend/access/index/genam.c      | 26 +++++++++-
 src/backend/access/nbtree/nbtinsert.c | 71 +++++++++++++++++++++++----
 src/backend/access/nbtree/nbtpage.c   |  2 +-
 src/backend/access/nbtree/nbtsearch.c |  2 +-
 src/backend/access/nbtree/nbtsort.c   |  3 +-
 src/include/access/genam.h            |  3 +-
 8 files changed, 96 insertions(+), 18 deletions(-)

diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index e9ca4b8252..cfdea23cec 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -1650,7 +1650,8 @@ gistprunepage(Relation rel, Page page, Buffer buffer, Relation heapRel)
 	if (XLogStandbyInfoActive() && RelationNeedsWAL(rel))
 		latestRemovedXid =
 			index_compute_xid_horizon_for_tuples(rel, heapRel, buffer,
-												 deletable, ndeletable);
+												 deletable, ndeletable,
+												 false);
 
 	if (ndeletable > 0)
 	{
diff --git a/src/backend/access/hash/hashinsert.c b/src/backend/access/hash/hashinsert.c
index 89876d2ccd..807e0ecd84 100644
--- a/src/backend/access/hash/hashinsert.c
+++ b/src/backend/access/hash/hashinsert.c
@@ -362,8 +362,8 @@ _hash_vacuum_one_page(Relation rel, Relation hrel, Buffer metabuf, Buffer buf)
 		TransactionId latestRemovedXid;
 
 		latestRemovedXid =
-			index_compute_xid_horizon_for_tuples(rel, hrel, buf,
-												 deletable, ndeletable);
+			index_compute_xid_horizon_for_tuples(rel, hrel, buf, deletable,
+												 ndeletable, false);
 
 		/*
 		 * Write-lock the meta page so that we can decrement tuple count.
diff --git a/src/backend/access/index/genam.c b/src/backend/access/index/genam.c
index 2599b5d342..c075e6c7c7 100644
--- a/src/backend/access/index/genam.c
+++ b/src/backend/access/index/genam.c
@@ -273,6 +273,8 @@ BuildIndexValueDescription(Relation indexRelation,
 	return buf.data;
 }
 
+#include "access/nbtree.h"
+
 /*
  * Get the latestRemovedXid from the table entries pointed at by the index
  * tuples being deleted.
@@ -282,7 +284,8 @@ index_compute_xid_horizon_for_tuples(Relation irel,
 									 Relation hrel,
 									 Buffer ibuf,
 									 OffsetNumber *itemnos,
-									 int nitems)
+									 int nitems,
+									 bool btree)
 {
 	ItemPointerData *ttids =
 	(ItemPointerData *) palloc(sizeof(ItemPointerData) * nitems);
@@ -298,6 +301,27 @@ index_compute_xid_horizon_for_tuples(Relation irel,
 		iitemid = PageGetItemId(ipage, itemnos[i]);
 		itup = (IndexTuple) PageGetItem(ipage, iitemid);
 
+		if (btree)
+		{
+			/*
+			 * FIXME: This is a gross modularity violation.  Clearly B-Tree
+			 * ought to pass us heap TIDs, and not require that we figure it
+			 * out on its behalf.  Also, this is just wrong, since we're
+			 * assuming that the oldest xmin is available from the lowest heap
+			 * TID.
+			 *
+			 * I haven't bothered to fix this because unique index support is
+			 * just a PoC, and will probably stay that way.  Also, since
+			 * WAL-logging is currently very inefficient, it doesn't seem very
+			 * likely that anybody will get an overly-optimistic view of the
+			 * cost of WAL logging just because we were sloppy here.
+			 */
+			if (BTreeTupleIsPosting(itup))
+			{
+				ItemPointerCopy(BTreeTupleGetHeapTID(itup), &ttids[i]);
+				continue;
+			}
+		}
 		ItemPointerCopy(&itup->t_tid, &ttids[i]);
 	}
 
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index f0c1174e2a..4da28d9518 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -432,7 +432,6 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
 			}
 
 			curitemid = PageGetItemId(page, offset);
-			Assert(!BTreeTupleIsPosting(curitup));
 
 			/*
 			 * We can skip items that are marked killed.
@@ -449,14 +448,34 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
 			if (!ItemIdIsDead(curitemid))
 			{
 				ItemPointerData htid;
+				bool		posting;
 				bool		all_dead;
+				bool		posting_all_dead;
+				int			npost;
 
 				if (_bt_compare(rel, itup_key, page, offset) != 0)
 					break;		/* we're past all the equal tuples */
 
 				/* okay, we gotta fetch the heap tuple ... */
 				curitup = (IndexTuple) PageGetItem(page, curitemid);
-				htid = curitup->t_tid;
+
+				if (!BTreeTupleIsPosting(curitup))
+				{
+					htid = curitup->t_tid;
+					posting = false;
+					posting_all_dead = true;
+				}
+				else
+				{
+					posting = true;
+					/* Initial assumption */
+					posting_all_dead = true;
+				}
+
+				npost = 0;
+doposttup:
+				if (posting)
+					htid = *BTreeTupleGetPostingN(curitup, npost);
 
 				/*
 				 * If we are doing a recheck, we expect to find the tuple we
@@ -467,6 +486,9 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
 					ItemPointerCompare(&htid, &itup->t_tid) == 0)
 				{
 					found = true;
+					posting_all_dead = false;
+					if (posting)
+						goto nextpost;
 				}
 
 				/*
@@ -532,8 +554,7 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
 					 * not part of this chain because it had a different index
 					 * entry.
 					 */
-					htid = itup->t_tid;
-					if (table_index_fetch_tuple_check(heapRel, &htid,
+					if (table_index_fetch_tuple_check(heapRel, &itup->t_tid,
 													  SnapshotSelf, NULL))
 					{
 						/* Normal case --- it's still live */
@@ -591,7 +612,7 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
 													RelationGetRelationName(rel))));
 					}
 				}
-				else if (all_dead)
+				else if (all_dead && !posting)
 				{
 					/*
 					 * The conflicting tuple (or whole HOT chain) is dead to
@@ -610,6 +631,35 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
 					else
 						MarkBufferDirtyHint(insertstate->buf, true);
 				}
+				else if (posting)
+				{
+nextpost:
+					if (!all_dead)
+						posting_all_dead = false;
+
+					/* Iterate over single posting list tuple */
+					npost++;
+					if (npost < BTreeTupleGetNPosting(curitup))
+						goto doposttup;
+
+					/*
+					 * Mark posting tuple dead if all hot chains whose root is
+					 * contained in posting tuple have tuples that are all
+					 * dead
+					 */
+					if (posting_all_dead)
+					{
+						ItemIdMarkDead(curitemid);
+						opaque->btpo_flags |= BTP_HAS_GARBAGE;
+
+						if (nbuf != InvalidBuffer)
+							MarkBufferDirtyHint(nbuf, true);
+						else
+							MarkBufferDirtyHint(insertstate->buf, true);
+					}
+
+					/* Move on to next index tuple */
+				}
 			}
 		}
 
@@ -784,7 +834,7 @@ _bt_findinsertloc(Relation rel,
 		/*
 		 * If the target page is full, try to compress the page
 		 */
-		if (PageGetFreeSpace(page) < insertstate->itemsz && !checkingunique)
+		if (PageGetFreeSpace(page) < insertstate->itemsz)
 		{
 			_bt_compress_one_page(rel, insertstate->buf, heapRel);
 			insertstate->bounds_valid = false;		/* paranoia */
@@ -2595,12 +2645,13 @@ _bt_compress_one_page(Relation rel, Buffer buffer, Relation heapRel)
 	int			natts = IndexRelationGetNumberOfAttributes(rel);
 
 	/*
-	 * Don't use compression for indexes with INCLUDEd columns and unique
-	 * indexes.
+	 * Don't use compression for indexes with INCLUDEd columns.
+	 *
+	 * Unique indexes can benefit from ad-hoc compression, though we don't do
+	 * this during CREATE INDEX.
 	 */
 	use_compression = (IndexRelationGetNumberOfKeyAttributes(rel) ==
-					   IndexRelationGetNumberOfAttributes(rel) &&
-					   !rel->rd_index->indisunique);
+					   IndexRelationGetNumberOfAttributes(rel));
 	if (!use_compression)
 		return;
 
diff --git a/src/backend/access/nbtree/nbtpage.c b/src/backend/access/nbtree/nbtpage.c
index 86c662d4e6..985418065b 100644
--- a/src/backend/access/nbtree/nbtpage.c
+++ b/src/backend/access/nbtree/nbtpage.c
@@ -1121,7 +1121,7 @@ _bt_delitems_delete(Relation rel, Buffer buf,
 	if (XLogStandbyInfoActive() && RelationNeedsWAL(rel))
 		latestRemovedXid =
 			index_compute_xid_horizon_for_tuples(rel, heapRel, buf,
-												 itemnos, nitems);
+												 itemnos, nitems, true);
 
 	/* No ereport(ERROR) until changes are logged */
 	START_CRIT_SECTION();
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 20975970d6..ffcfd21593 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -557,7 +557,7 @@ _bt_compare_posting(Relation rel,
 	itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
 	result = _bt_compare(rel, key, page, offnum);
 
-	if (BTreeTupleIsPosting(itup) && result == 0)
+	if (BTreeTupleIsPosting(itup) && result == 0 && key->scantid)
 	{
 		int			low,
 					high,
diff --git a/src/backend/access/nbtree/nbtsort.c b/src/backend/access/nbtree/nbtsort.c
index b058599aa4..846e60a452 100644
--- a/src/backend/access/nbtree/nbtsort.c
+++ b/src/backend/access/nbtree/nbtsort.c
@@ -1253,7 +1253,8 @@ _bt_load(BTWriteState *wstate, BTSpool *btspool, BTSpool *btspool2)
 
 	/*
 	 * Don't use compression for indexes with INCLUDEd columns and unique
-	 * indexes.
+	 * indexes.  Note that unique indexes are supported with retail
+	 * insertions.
 	 */
 	use_compression = (IndexRelationGetNumberOfKeyAttributes(wstate->index) ==
 					   IndexRelationGetNumberOfAttributes(wstate->index) &&
diff --git a/src/include/access/genam.h b/src/include/access/genam.h
index 8c053be2ca..f9866ce7f9 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -193,7 +193,8 @@ extern TransactionId index_compute_xid_horizon_for_tuples(Relation irel,
 														  Relation hrel,
 														  Buffer ibuf,
 														  OffsetNumber *itemnos,
-														  int nitems);
+														  int nitems,
+														  bool btree);
 
 /*
  * heap-or-index access to system catalogs (in genam.c)
-- 
2.17.1