Use simplehash.h instead of dynahash in SMgr

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index adfc6f67e2..aa7accbe1b 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -7616,6 +7616,7 @@ StartupXLOG(void)
 						(errmsg("last completed transaction was at log time %s",
 								timestamptz_to_str(xtime))));
 
+			elog(PANIC, "recovery PANIC");
 			InRedo = false;
 		}
 		else

From d8737afb5d368015522b57f502bf1eced4220689 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Thu, 22 Apr 2021 17:03:46 +1200
Subject: [PATCH v1] Use simplehash.h hashtables in SMgr

The hash table lookups done in SMgr can quite often be a bottleneck during
crash recovery.  Traditionally these use dynahash. Here we swap dynahash
out and use simplehash instead.  This improves lookup performance.

Some changes are required from simplehash.h here to make this work.  The
reason for this is that code external to smgr.c does point to the hashed
SMgrRelation. Since simplehash does reallocate the bucket array when
increasing the size of the table and also shuffle entries around during
deletes, code pointing directly into hash entries would be a bad idea. To
overcome this issue we only store a pointer to the SMgrRelationData in the
hash table entry and maintain a separate allocation for that data. This
does mean an additional pointer dereference during lookups, but only when
the hash value matches, so the significant majority of the time that will
only be done for the item we are actually looking for.

Since the hash table key is stored in the referenced SMgrRelation, we need
to add two new macros to allow simplehash to allocate the memory for the
SMgrEntry during inserts before it tries to set the key.  A new macro has
also been added to allow simplehash implementations to perform cleanup
when items are removed from the table.
---
 src/backend/storage/smgr/smgr.c | 173 +++++++++++++++++++++++++-------
 src/include/lib/simplehash.h    |  48 ++++++++-
 2 files changed, 182 insertions(+), 39 deletions(-)

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 4dc24649df..64a26e06c6 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -18,14 +18,50 @@
 #include "postgres.h"
 
 #include "access/xlog.h"
+#include "common/hashfn.h"
 #include "lib/ilist.h"
 #include "storage/bufmgr.h"
 #include "storage/ipc.h"
 #include "storage/md.h"
 #include "storage/smgr.h"
-#include "utils/hsearch.h"
 #include "utils/inval.h"
 
+/* Hash table entry type for SMgrRelationHash */
+typedef struct SMgrEntry
+{
+	int			status;			/* Hash table status */
+	uint32		hash;			/* Hash value (cached) */
+	SMgrRelation data;			/* Pointer to the SMgrRelationData */
+} SMgrEntry;
+
+static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
+static void smgr_entry_cleanup(SMgrRelation reln);
+
+/*
+ * Because simplehash.h does not provide a stable pointer to hash table
+ * entries, we don't make the element type a SMgrRelation directly, instead we
+ * use an SMgrEntry type which has a pointer to the data field.  simplehash can
+ * move entries around when adding or removing items from the hash table so
+ * having the SMgrRelation as a pointer inside the SMgrEntry allows external
+ * code to keep their own pointers to the SMgrRelation.  Relcache does this.
+ * We use the SH_ENTRY_INITIALIZER to allocate memory for the SMgrRelationData
+ * when a new entry is created.  We also define SH_ENTRY_CLEANUP to execute
+ * some cleanup when removing an item from the table.
+ */
+#define SH_PREFIX		smgrtable
+#define SH_ELEMENT_TYPE	SMgrEntry
+#define SH_KEY_TYPE		RelFileNodeBackend
+#define	SH_KEY			data->smgr_rnode
+#define SH_HASH_KEY(tb, key)	relfilenodebackend_hash(&key)
+#define SH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(RelFileNodeBackend)) == 0)
+#define	SH_SCOPE		static inline
+#define SH_STORE_HASH
+#define SH_GET_HASH(tb, a) a->hash
+#define SH_ENTRY_INITIALIZER(a) a->data = MemoryContextAlloc(TopMemoryContext, sizeof(SMgrRelationData))
+#define SH_ENTRY_CLEANUP(a) smgr_entry_cleanup(a->data)
+#define SH_DEFINE
+#define SH_DECLARE
+#include "lib/simplehash.h"
 
 /*
  * This struct of function pointers defines the API between smgr.c and
@@ -91,13 +127,62 @@ static const int NSmgr = lengthof(smgrsw);
  * Each backend has a hashtable that stores all extant SMgrRelation objects.
  * In addition, "unowned" SMgrRelation objects are chained together in a list.
  */
-static HTAB *SMgrRelationHash = NULL;
+static smgrtable_hash *SMgrRelationHash = NULL;
 
 static dlist_head unowned_relns;
 
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
 
+/*
+ * relfilenodebackend_hash
+ *		Custom rolled hash function for simplehash table.
+ *
+ * smgropen() is often a bottleneck in CPU bound workloads during crash
+ * recovery.  We make use of this custom hash function rather than using
+ * hash_bytes as it gives us a little bit more performance.
+ *
+ * XXX What if sizeof(Oid) is not 4?
+ */
+static inline uint32
+relfilenodebackend_hash(RelFileNodeBackend *rnode)
+{
+	uint32		hashkey;
+
+	hashkey = murmurhash32((uint32) rnode->node.spcNode);
+
+	/* rotate hashkey left 1 bit at each step */
+	hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
+
+	hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
+
+	hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+	hashkey ^= murmurhash32((uint32) rnode->backend);
+
+	return hashkey;
+}
+
+/*
+ * smgr_entry_cleanup
+ *		Cleanup code for simplehash.h to execute when removing an item from
+ *		the hash table.
+ */
+static void
+smgr_entry_cleanup(SMgrRelation reln)
+{
+	/*
+	 * Unhook the owner pointer, if any.  We only do this when we're certain
+	 * the entry is removed from the hash table.  This allows us to leave the
+	 * owner attached if the hash table delete were to fail for some reason.
+	 */
+	if (reln->smgr_owner)
+		*reln->smgr_owner = NULL;
+
+	pfree(reln);
+}
+
 
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
@@ -147,31 +232,26 @@ smgropen(RelFileNode rnode, BackendId backend)
 {
 	RelFileNodeBackend brnode;
 	SMgrRelation reln;
+	SMgrEntry  *entry;
 	bool		found;
 
-	if (SMgrRelationHash == NULL)
+	if (unlikely(SMgrRelationHash == NULL))
 	{
 		/* First time through: initialize the hash table */
-		HASHCTL		ctl;
-
-		ctl.keysize = sizeof(RelFileNodeBackend);
-		ctl.entrysize = sizeof(SMgrRelationData);
-		SMgrRelationHash = hash_create("smgr relation table", 400,
-									   &ctl, HASH_ELEM | HASH_BLOBS);
+		SMgrRelationHash = smgrtable_create(TopMemoryContext, 400, NULL);
 		dlist_init(&unowned_relns);
 	}
 
 	/* Look up or create an entry */
 	brnode.node = rnode;
 	brnode.backend = backend;
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &brnode,
-									  HASH_ENTER, &found);
+	entry = smgrtable_insert(SMgrRelationHash, brnode, &found);
+	reln = entry->data;
 
 	/* Initialize it if not present before */
 	if (!found)
 	{
-		/* hash_search already filled in the lookup key */
+		/* smgrtable_insert already filled in the lookup key */
 		reln->smgr_owner = NULL;
 		reln->smgr_targblock = InvalidBlockNumber;
 		for (int i = 0; i <= MAX_FORKNUM; ++i)
@@ -250,10 +330,11 @@ smgrexists(SMgrRelation reln, ForkNumber forknum)
 }
 
 /*
- *	smgrclose() -- Close and delete an SMgrRelation object.
+ *	smgrclose() -- Close and delete an SMgrRelation object but don't
+ *	remove from the SMgrRelationHash table.
  */
-void
-smgrclose(SMgrRelation reln)
+static inline void
+smgrclose_internal(SMgrRelation reln)
 {
 	SMgrRelation *owner;
 	ForkNumber	forknum;
@@ -266,17 +347,18 @@ smgrclose(SMgrRelation reln)
 	if (!owner)
 		dlist_delete(&reln->node);
 
-	if (hash_search(SMgrRelationHash,
-					(void *) &(reln->smgr_rnode),
-					HASH_REMOVE, NULL) == NULL)
-		elog(ERROR, "SMgrRelation hashtable corrupted");
+}
 
-	/*
-	 * Unhook the owner pointer, if any.  We do this last since in the remote
-	 * possibility of failure above, the SMgrRelation object will still exist.
-	 */
-	if (owner)
-		*owner = NULL;
+/*
+ *	smgrclose() -- Close and delete an SMgrRelation object.
+ */
+void
+smgrclose(SMgrRelation reln)
+{
+	smgrclose_internal(reln);
+
+	if (!smgrtable_delete(SMgrRelationHash, reln->smgr_rnode))
+		elog(ERROR, "SMgrRelation hashtable corrupted");
 }
 
 /*
@@ -285,17 +367,25 @@ smgrclose(SMgrRelation reln)
 void
 smgrcloseall(void)
 {
-	HASH_SEQ_STATUS status;
-	SMgrRelation reln;
+	smgrtable_iterator iterator;
+	SMgrEntry  *entry;
 
 	/* Nothing to do if hashtable not set up */
-	if (SMgrRelationHash == NULL)
+	if (unlikely(SMgrRelationHash == NULL))
 		return;
 
-	hash_seq_init(&status, SMgrRelationHash);
+	smgrtable_start_iterate(SMgrRelationHash, &iterator);
+	while ((entry = smgrtable_iterate(SMgrRelationHash, &iterator)) != NULL)
+		smgrclose_internal(entry->data);
 
-	while ((reln = (SMgrRelation) hash_seq_search(&status)) != NULL)
-		smgrclose(reln);
+	/*
+	 * Finally, remove all entries from the hash table.  This is done last and
+	 * in a single operation as we're unable to remove multiple entries in the
+	 * above loop due to deletes moving elements around in the table.
+	 * Additionally, it is much more efficient to just wipe out all entries
+	 * rather than doing individual deletes of each entry.
+	 */
+	smgrtable_truncate(SMgrRelationHash);
 }
 
 /*
@@ -309,17 +399,24 @@ smgrcloseall(void)
 void
 smgrclosenode(RelFileNodeBackend rnode)
 {
-	SMgrRelation reln;
+	SMgrEntry  *entry;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
+	entry = smgrtable_lookup(SMgrRelationHash, rnode);
+	if (entry != NULL)
+	{
+		/* Delete the entry, but skip the hash table delete... */
+		smgrclose_internal(entry->data);
 
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &rnode,
-									  HASH_FIND, NULL);
-	if (reln != NULL)
-		smgrclose(reln);
+		/*
+		 * ... as we can remove from the hash table directly due to already
+		 * having a pointer to the exact entry we want to delete.  This saves
+		 * an additional table lookup.
+		 */
+		smgrtable_delete_item(SMgrRelationHash, entry);
+	}
 }
 
 /*
diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index da51781e98..569104def0 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -50,6 +50,10 @@
  *	  - SH_HASH_KEY(table, key) - generate hash for the key
  *	  - SH_STORE_HASH - if defined the hash is stored in the elements
  *	  - SH_GET_HASH(tb, a) - return the field to store the hash in
+ *	  - SH_ENTRY_INITIALIZER(a) - if defined, the code in this macro is called
+ *		for new entries
+ *	  - SH_ENTRY_CLEANUP(a) - if defined, the code in this macro is called
+ *		when an entry is removed from the hash table.
  *
  *	  The element type is required to contain a "status" member that can store
  *	  the range of values defined in the SH_STATUS enum.
@@ -115,6 +119,7 @@
 #define SH_LOOKUP SH_MAKE_NAME(lookup)
 #define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash)
 #define SH_GROW SH_MAKE_NAME(grow)
+#define SH_TRUNCATE SH_MAKE_NAME(truncate)
 #define SH_START_ITERATE SH_MAKE_NAME(start_iterate)
 #define SH_START_ITERATE_AT SH_MAKE_NAME(start_iterate_at)
 #define SH_ITERATE SH_MAKE_NAME(iterate)
@@ -224,6 +229,9 @@ SH_SCOPE void SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry);
 /* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
 SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key);
 
+/* void <prefix>_truncate(<prefix>_hash *tb) */
+SH_SCOPE void SH_TRUNCATE(SH_TYPE * tb);
+
 /* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
 SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
 
@@ -634,6 +642,9 @@ restart:
 		if (entry->status == SH_STATUS_EMPTY)
 		{
 			tb->members++;
+#ifdef SH_ENTRY_INITIALIZER
+			SH_ENTRY_INITIALIZER(entry);
+#endif
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
 			SH_GET_HASH(tb, entry) = hash;
@@ -721,6 +732,9 @@ restart:
 
 			/* and fill the now empty spot */
 			tb->members++;
+#ifdef SH_ENTRY_INITIALIZER
+			SH_ENTRY_INITIALIZER(entry);
+#endif
 
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
@@ -856,7 +870,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 			SH_ELEMENT_TYPE *lastentry = entry;
 
 			tb->members--;
-
+#ifdef SH_ENTRY_CLEANUP
+			SH_ENTRY_CLEANUP(entry);
+#endif
 			/*
 			 * Backward shift following elements till either an empty element
 			 * or an element at its optimal position is encountered.
@@ -919,6 +935,9 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 	curelem = entry - &tb->data[0];
 
 	tb->members--;
+#ifdef SH_ENTRY_CLEANUP
+	SH_ENTRY_CLEANUP(entry);
+#endif
 
 	/*
 	 * Backward shift following elements till either an empty element or an
@@ -959,6 +978,30 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 	}
 }
 
+/*
+ * Remove all entries from the table making the table empty.
+ */
+SH_SCOPE void
+SH_TRUNCATE(SH_TYPE * tb)
+{
+	int			i;
+
+	for (i = 0; i < tb->size; i++)
+	{
+		SH_ELEMENT_TYPE *entry = &tb->data[i];
+		if (entry->status != SH_STATUS_EMPTY)
+		{
+			entry->status = SH_STATUS_EMPTY;
+
+#ifdef SH_ENTRY_CLEANUP
+			SH_ENTRY_CLEANUP(entry);
+#endif
+		}
+	}
+
+	tb->members = 0;
+}
+
 /*
  * Initialize iterator.
  */
@@ -1133,6 +1176,8 @@ SH_STAT(SH_TYPE * tb)
 #undef SH_DECLARE
 #undef SH_DEFINE
 #undef SH_GET_HASH
+#undef SH_ENTRY_INITIALIZER
+#undef SH_ENTRY_CLEANUP
 #undef SH_STORE_HASH
 #undef SH_USE_NONDEFAULT_ALLOCATOR
 #undef SH_EQUAL
@@ -1166,6 +1211,7 @@ SH_STAT(SH_TYPE * tb)
 #undef SH_LOOKUP
 #undef SH_LOOKUP_HASH
 #undef SH_GROW
+#undef SH_TRUNCATE
 #undef SH_START_ITERATE
 #undef SH_START_ITERATE_AT
 #undef SH_ITERATE
-- 
2.27.0

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 8310f73212..33e5cadd03 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -34,8 +34,6 @@ typedef struct SMgrEntry
 	SMgrRelation data;			/* Pointer to the SMgrRelationData */
 } SMgrEntry;
 
-static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
-
 /*
  * Because simplehash.h does not provide a stable pointer to hash table
  * entries, we don't make the element type a SMgrRelation directly, instead we
@@ -51,7 +49,7 @@ static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
 #define SH_ELEMENT_TYPE	SMgrEntry
 #define SH_KEY_TYPE		RelFileNodeBackend
 #define	SH_KEY			data->smgr_rnode
-#define SH_HASH_KEY(tb, key)	relfilenodebackend_hash(&key)
+#define SH_HASH_KEY(tb, key)	hash_bytes((const unsigned char *) &key, sizeof(RelFileNodeBackend))
 #define SH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(RelFileNodeBackend)) == 0)
 #define	SH_SCOPE		static inline
 #define SH_STORE_HASH
@@ -133,37 +131,6 @@ static dlist_head unowned_relns;
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
 
-/*
- * relfilenodebackend_hash
- *		Custom rolled hash function for simplehash table.
- *
- * smgropen() is often a bottleneck in CPU bound workloads during crash
- * recovery.  We make use of this custom hash function rather than using
- * hash_bytes as it gives us a little bit more performance.
- *
- * XXX What if sizeof(Oid) is not 4?
- */
-static inline uint32
-relfilenodebackend_hash(RelFileNodeBackend *rnode)
-{
-	uint32		hashkey;
-
-	hashkey = murmurhash32((uint32) rnode->node.spcNode);
-
-	/* rotate hashkey left 1 bit at each step */
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
-
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
-
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->backend);
-
-	return hashkey;
-}
-
-
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
  *								  managers.

From 3b4f2c964e40c36824ed18658a53f98568e20af7 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Thu, 22 Apr 2021 17:03:46 +1200
Subject: [PATCH v2] Use simplehash.h hashtables in SMgr

The hash table lookups done in SMgr can quite often be a bottleneck during
crash recovery.  Traditionally these use dynahash. Here we swap dynahash
out and use simplehash instead.  This improves lookup performance.

Some changes are required from simplehash.h here to make this work.  The
reason for this is that code external to smgr.c does point to the hashed
SMgrRelation. Since simplehash does reallocate the bucket array when
increasing the size of the table and also shuffle entries around during
deletes, code pointing directly into hash entries would be a bad idea. To
overcome this issue we only store a pointer to the SMgrRelationData in the
hash table entry and maintain a separate allocation for that data. This
does mean an additional pointer dereference during lookups, but only when
the hash value matches, so the significant majority of the time that will
only be done for the item we are actually looking for.

Since the hash table key is stored in the referenced SMgrRelation, we need
to add two new macros to allow simplehash to allocate the memory for the
SMgrEntry during inserts before it tries to set the key.  A new macro has
also been added to allow simplehash implementations to perform cleanup
when items are removed from the table.
---
 src/backend/storage/smgr/smgr.c | 111 ++++++++++++++++++++++++--------
 src/include/lib/simplehash.h    |  20 +++++-
 src/include/port/pg_bitutils.h  |  13 +++-
 3 files changed, 114 insertions(+), 30 deletions(-)

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 4dc24649df..8310f73212 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -18,14 +18,49 @@
 #include "postgres.h"
 
 #include "access/xlog.h"
+#include "common/hashfn.h"
 #include "lib/ilist.h"
 #include "storage/bufmgr.h"
 #include "storage/ipc.h"
 #include "storage/md.h"
 #include "storage/smgr.h"
-#include "utils/hsearch.h"
 #include "utils/inval.h"
 
+/* Hash table entry type for SMgrRelationHash */
+typedef struct SMgrEntry
+{
+	int			status;			/* Hash table status */
+	uint32		hash;			/* Hash value (cached) */
+	SMgrRelation data;			/* Pointer to the SMgrRelationData */
+} SMgrEntry;
+
+static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
+
+/*
+ * Because simplehash.h does not provide a stable pointer to hash table
+ * entries, we don't make the element type a SMgrRelation directly, instead we
+ * use an SMgrEntry type which has a pointer to the data field.  simplehash can
+ * move entries around when adding or removing items from the hash table so
+ * having the SMgrRelation as a pointer inside the SMgrEntry allows external
+ * code to keep their own pointers to the SMgrRelation.  Relcache does this.
+ * We use the SH_ENTRY_INITIALIZER to allocate memory for the SMgrRelationData
+ * when a new entry is created.  We also define SH_ENTRY_CLEANUP to execute
+ * some cleanup when removing an item from the table.
+ */
+#define SH_PREFIX		smgrtable
+#define SH_ELEMENT_TYPE	SMgrEntry
+#define SH_KEY_TYPE		RelFileNodeBackend
+#define	SH_KEY			data->smgr_rnode
+#define SH_HASH_KEY(tb, key)	relfilenodebackend_hash(&key)
+#define SH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(RelFileNodeBackend)) == 0)
+#define	SH_SCOPE		static inline
+#define SH_STORE_HASH
+#define SH_GET_HASH(tb, a) a->hash
+#define SH_ENTRY_INITIALIZER(a) a->data = MemoryContextAlloc(TopMemoryContext, sizeof(SMgrRelationData))
+#define SH_ENTRY_CLEANUP(a) pfree(a->data)
+#define SH_DEFINE
+#define SH_DECLARE
+#include "lib/simplehash.h"
 
 /*
  * This struct of function pointers defines the API between smgr.c and
@@ -91,13 +126,43 @@ static const int NSmgr = lengthof(smgrsw);
  * Each backend has a hashtable that stores all extant SMgrRelation objects.
  * In addition, "unowned" SMgrRelation objects are chained together in a list.
  */
-static HTAB *SMgrRelationHash = NULL;
+static smgrtable_hash *SMgrRelationHash = NULL;
 
 static dlist_head unowned_relns;
 
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
 
+/*
+ * relfilenodebackend_hash
+ *		Custom rolled hash function for simplehash table.
+ *
+ * smgropen() is often a bottleneck in CPU bound workloads during crash
+ * recovery.  We make use of this custom hash function rather than using
+ * hash_bytes as it gives us a little bit more performance.
+ *
+ * XXX What if sizeof(Oid) is not 4?
+ */
+static inline uint32
+relfilenodebackend_hash(RelFileNodeBackend *rnode)
+{
+	uint32		hashkey;
+
+	hashkey = murmurhash32((uint32) rnode->node.spcNode);
+
+	/* rotate hashkey left 1 bit at each step */
+	hashkey = pg_rotate_left32(hashkey, 1);
+	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
+
+	hashkey = pg_rotate_left32(hashkey, 1);
+	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
+
+	hashkey = pg_rotate_left32(hashkey, 1);
+	hashkey ^= murmurhash32((uint32) rnode->backend);
+
+	return hashkey;
+}
+
 
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
@@ -147,31 +212,26 @@ smgropen(RelFileNode rnode, BackendId backend)
 {
 	RelFileNodeBackend brnode;
 	SMgrRelation reln;
+	SMgrEntry  *entry;
 	bool		found;
 
-	if (SMgrRelationHash == NULL)
+	if (unlikely(SMgrRelationHash == NULL))
 	{
 		/* First time through: initialize the hash table */
-		HASHCTL		ctl;
-
-		ctl.keysize = sizeof(RelFileNodeBackend);
-		ctl.entrysize = sizeof(SMgrRelationData);
-		SMgrRelationHash = hash_create("smgr relation table", 400,
-									   &ctl, HASH_ELEM | HASH_BLOBS);
+		SMgrRelationHash = smgrtable_create(TopMemoryContext, 400, NULL);
 		dlist_init(&unowned_relns);
 	}
 
 	/* Look up or create an entry */
 	brnode.node = rnode;
 	brnode.backend = backend;
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &brnode,
-									  HASH_ENTER, &found);
+	entry = smgrtable_insert(SMgrRelationHash, brnode, &found);
+	reln = entry->data;
 
 	/* Initialize it if not present before */
 	if (!found)
 	{
-		/* hash_search already filled in the lookup key */
+		/* smgrtable_insert already filled in the lookup key */
 		reln->smgr_owner = NULL;
 		reln->smgr_targblock = InvalidBlockNumber;
 		for (int i = 0; i <= MAX_FORKNUM; ++i)
@@ -266,9 +326,7 @@ smgrclose(SMgrRelation reln)
 	if (!owner)
 		dlist_delete(&reln->node);
 
-	if (hash_search(SMgrRelationHash,
-					(void *) &(reln->smgr_rnode),
-					HASH_REMOVE, NULL) == NULL)
+	if (!smgrtable_delete(SMgrRelationHash, reln->smgr_rnode))
 		elog(ERROR, "SMgrRelation hashtable corrupted");
 
 	/*
@@ -285,17 +343,17 @@ smgrclose(SMgrRelation reln)
 void
 smgrcloseall(void)
 {
-	HASH_SEQ_STATUS status;
-	SMgrRelation reln;
+	smgrtable_iterator iterator;
+	SMgrEntry  *entry;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
 
-	hash_seq_init(&status, SMgrRelationHash);
+	smgrtable_start_iterate(SMgrRelationHash, &iterator);
 
-	while ((reln = (SMgrRelation) hash_seq_search(&status)) != NULL)
-		smgrclose(reln);
+	while ((entry = smgrtable_iterate(SMgrRelationHash, &iterator)) != NULL)
+		smgrclose(entry->data);
 }
 
 /*
@@ -309,17 +367,14 @@ smgrcloseall(void)
 void
 smgrclosenode(RelFileNodeBackend rnode)
 {
-	SMgrRelation reln;
+	SMgrEntry  *entry;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
-
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &rnode,
-									  HASH_FIND, NULL);
-	if (reln != NULL)
-		smgrclose(reln);
+	entry = smgrtable_lookup(SMgrRelationHash, rnode);
+	if (entry != NULL)
+		smgrclose(entry->data);
 }
 
 /*
diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index da51781e98..4fce182de6 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -50,6 +50,11 @@
  *	  - SH_HASH_KEY(table, key) - generate hash for the key
  *	  - SH_STORE_HASH - if defined the hash is stored in the elements
  *	  - SH_GET_HASH(tb, a) - return the field to store the hash in
+ *	  - SH_ENTRY_INITIALIZER(a) - if defined, the code in this macro is called
+ *		for new entries directly before any other internal code makes any
+ *		changes to setup the new entry
+ *	  - SH_ENTRY_CLEANUP(a) - if defined, the code in this macro is called
+ *		when an entry is removed from the hash table
  *
  *	  The element type is required to contain a "status" member that can store
  *	  the range of values defined in the SH_STATUS enum.
@@ -634,6 +639,9 @@ restart:
 		if (entry->status == SH_STATUS_EMPTY)
 		{
 			tb->members++;
+#ifdef SH_ENTRY_INITIALIZER
+			SH_ENTRY_INITIALIZER(entry);
+#endif
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
 			SH_GET_HASH(tb, entry) = hash;
@@ -721,6 +729,9 @@ restart:
 
 			/* and fill the now empty spot */
 			tb->members++;
+#ifdef SH_ENTRY_INITIALIZER
+			SH_ENTRY_INITIALIZER(entry);
+#endif
 
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
@@ -856,7 +867,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 			SH_ELEMENT_TYPE *lastentry = entry;
 
 			tb->members--;
-
+#ifdef SH_ENTRY_CLEANUP
+			SH_ENTRY_CLEANUP(entry);
+#endif
 			/*
 			 * Backward shift following elements till either an empty element
 			 * or an element at its optimal position is encountered.
@@ -919,6 +932,9 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 	curelem = entry - &tb->data[0];
 
 	tb->members--;
+#ifdef SH_ENTRY_CLEANUP
+	SH_ENTRY_CLEANUP(entry);
+#endif
 
 	/*
 	 * Backward shift following elements till either an empty element or an
@@ -1133,6 +1149,8 @@ SH_STAT(SH_TYPE * tb)
 #undef SH_DECLARE
 #undef SH_DEFINE
 #undef SH_GET_HASH
+#undef SH_ENTRY_INITIALIZER
+#undef SH_ENTRY_CLEANUP
 #undef SH_STORE_HASH
 #undef SH_USE_NONDEFAULT_ALLOCATOR
 #undef SH_EQUAL
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index f9b77ec278..581957fe55 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -215,7 +215,8 @@ extern int	(*pg_popcount64) (uint64 word);
 extern uint64 pg_popcount(const char *buf, int bytes);
 
 /*
- * Rotate the bits of "word" to the right by n bits.
+ * pg_rotate_right32
+ *		Rotate the bits of 'word' to the right by 'n' bits.
  */
 static inline uint32
 pg_rotate_right32(uint32 word, int n)
@@ -223,4 +224,14 @@ pg_rotate_right32(uint32 word, int n)
 	return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
 }
 
+/*
+ * pg_rotate_left32
+ *		Rotate the bits of 'word' to the left by 'n' bits.
+ */
+static inline uint32
+pg_rotate_left32(uint32 word, int n)
+{
+	return (word << n) | (word >> (sizeof(word) * BITS_PER_BYTE - n));
+}
+
 #endif							/* PG_BITUTILS_H */
-- 
2.21.0.windows.1

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 8310f73212..f291ded795 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -147,18 +147,19 @@ static inline uint32
 relfilenodebackend_hash(RelFileNodeBackend *rnode)
 {
 	uint32		hashkey;
+	uint32		hashkey2;
 
 	hashkey = murmurhash32((uint32) rnode->node.spcNode);
 
 	/* rotate hashkey left 1 bit at each step */
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
+	hashkey2 = murmurhash32((uint32) rnode->node.dbNode);
+	hashkey = hash_combine(hashkey, hashkey2);
 
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
+	hashkey2 = murmurhash32((uint32) rnode->node.relNode);
+	hashkey = hash_combine(hashkey, hashkey2);
 
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->backend);
+	hashkey2 = murmurhash32((uint32) rnode->backend);
+	hashkey = hash_combine(hashkey, hashkey2);
 
 	return hashkey;
 }

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index adfc6f67e2..5d34e06eab 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -7615,7 +7615,8 @@ StartupXLOG(void)
 				ereport(LOG,
 						(errmsg("last completed transaction was at log time %s",
 								timestamptz_to_str(xtime))));
-
+			smgrstats();
+			elog(PANIC, "recovery PANIC");
 			InRedo = false;
 		}
 		else
diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 64a26e06c6..850b51e316 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -183,6 +183,12 @@ smgr_entry_cleanup(SMgrRelation reln)
 	pfree(reln);
 }
 
+void
+smgrstats(void)
+{
+	if (SMgrRelationHash != NULL)
+		smgrtable_stat(SMgrRelationHash);
+}
 
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
diff --git a/src/include/storage/smgr.h b/src/include/storage/smgr.h
index a6fbf7b6a6..ac010af74a 100644
--- a/src/include/storage/smgr.h
+++ b/src/include/storage/smgr.h
@@ -77,6 +77,7 @@ typedef SMgrRelationData *SMgrRelation;
 #define SmgrIsTemp(smgr) \
 	RelFileNodeBackendIsTemp((smgr)->smgr_rnode)
 
+extern void smgrstats(void);
 extern void smgrinit(void);
 extern SMgrRelation smgropen(RelFileNode rnode, BackendId backend);
 extern bool smgrexists(SMgrRelation reln, ForkNumber forknum);

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 8310f73212..33e5cadd03 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -34,8 +34,6 @@ typedef struct SMgrEntry
 	SMgrRelation data;			/* Pointer to the SMgrRelationData */
 } SMgrEntry;
 
-static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
-
 /*
  * Because simplehash.h does not provide a stable pointer to hash table
  * entries, we don't make the element type a SMgrRelation directly, instead we
@@ -51,7 +49,7 @@ static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
 #define SH_ELEMENT_TYPE	SMgrEntry
 #define SH_KEY_TYPE		RelFileNodeBackend
 #define	SH_KEY			data->smgr_rnode
-#define SH_HASH_KEY(tb, key)	relfilenodebackend_hash(&key)
+#define SH_HASH_KEY(tb, key)	hash_bytes((const unsigned char *) &key, sizeof(RelFileNodeBackend))
 #define SH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(RelFileNodeBackend)) == 0)
 #define	SH_SCOPE		static inline
 #define SH_STORE_HASH
@@ -133,37 +131,6 @@ static dlist_head unowned_relns;
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
 
-/*
- * relfilenodebackend_hash
- *		Custom rolled hash function for simplehash table.
- *
- * smgropen() is often a bottleneck in CPU bound workloads during crash
- * recovery.  We make use of this custom hash function rather than using
- * hash_bytes as it gives us a little bit more performance.
- *
- * XXX What if sizeof(Oid) is not 4?
- */
-static inline uint32
-relfilenodebackend_hash(RelFileNodeBackend *rnode)
-{
-	uint32		hashkey;
-
-	hashkey = murmurhash32((uint32) rnode->node.spcNode);
-
-	/* rotate hashkey left 1 bit at each step */
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
-
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
-
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->backend);
-
-	return hashkey;
-}
-
-
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
  *								  managers.

From 3b4f2c964e40c36824ed18658a53f98568e20af7 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Thu, 22 Apr 2021 17:03:46 +1200
Subject: [PATCH v2] Use simplehash.h hashtables in SMgr

The hash table lookups done in SMgr can quite often be a bottleneck during
crash recovery.  Traditionally these use dynahash. Here we swap dynahash
out and use simplehash instead.  This improves lookup performance.

Some changes are required from simplehash.h here to make this work.  The
reason for this is that code external to smgr.c does point to the hashed
SMgrRelation. Since simplehash does reallocate the bucket array when
increasing the size of the table and also shuffle entries around during
deletes, code pointing directly into hash entries would be a bad idea. To
overcome this issue we only store a pointer to the SMgrRelationData in the
hash table entry and maintain a separate allocation for that data. This
does mean an additional pointer dereference during lookups, but only when
the hash value matches, so the significant majority of the time that will
only be done for the item we are actually looking for.

Since the hash table key is stored in the referenced SMgrRelation, we need
to add two new macros to allow simplehash to allocate the memory for the
SMgrEntry during inserts before it tries to set the key.  A new macro has
also been added to allow simplehash implementations to perform cleanup
when items are removed from the table.
---
 src/backend/storage/smgr/smgr.c | 111 ++++++++++++++++++++++++--------
 src/include/lib/simplehash.h    |  20 +++++-
 src/include/port/pg_bitutils.h  |  13 +++-
 3 files changed, 114 insertions(+), 30 deletions(-)

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 4dc24649df..8310f73212 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -18,14 +18,49 @@
 #include "postgres.h"
 
 #include "access/xlog.h"
+#include "common/hashfn.h"
 #include "lib/ilist.h"
 #include "storage/bufmgr.h"
 #include "storage/ipc.h"
 #include "storage/md.h"
 #include "storage/smgr.h"
-#include "utils/hsearch.h"
 #include "utils/inval.h"
 
+/* Hash table entry type for SMgrRelationHash */
+typedef struct SMgrEntry
+{
+	int			status;			/* Hash table status */
+	uint32		hash;			/* Hash value (cached) */
+	SMgrRelation data;			/* Pointer to the SMgrRelationData */
+} SMgrEntry;
+
+static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
+
+/*
+ * Because simplehash.h does not provide a stable pointer to hash table
+ * entries, we don't make the element type a SMgrRelation directly, instead we
+ * use an SMgrEntry type which has a pointer to the data field.  simplehash can
+ * move entries around when adding or removing items from the hash table so
+ * having the SMgrRelation as a pointer inside the SMgrEntry allows external
+ * code to keep their own pointers to the SMgrRelation.  Relcache does this.
+ * We use the SH_ENTRY_INITIALIZER to allocate memory for the SMgrRelationData
+ * when a new entry is created.  We also define SH_ENTRY_CLEANUP to execute
+ * some cleanup when removing an item from the table.
+ */
+#define SH_PREFIX		smgrtable
+#define SH_ELEMENT_TYPE	SMgrEntry
+#define SH_KEY_TYPE		RelFileNodeBackend
+#define	SH_KEY			data->smgr_rnode
+#define SH_HASH_KEY(tb, key)	relfilenodebackend_hash(&key)
+#define SH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(RelFileNodeBackend)) == 0)
+#define	SH_SCOPE		static inline
+#define SH_STORE_HASH
+#define SH_GET_HASH(tb, a) a->hash
+#define SH_ENTRY_INITIALIZER(a) a->data = MemoryContextAlloc(TopMemoryContext, sizeof(SMgrRelationData))
+#define SH_ENTRY_CLEANUP(a) pfree(a->data)
+#define SH_DEFINE
+#define SH_DECLARE
+#include "lib/simplehash.h"
 
 /*
  * This struct of function pointers defines the API between smgr.c and
@@ -91,13 +126,43 @@ static const int NSmgr = lengthof(smgrsw);
  * Each backend has a hashtable that stores all extant SMgrRelation objects.
  * In addition, "unowned" SMgrRelation objects are chained together in a list.
  */
-static HTAB *SMgrRelationHash = NULL;
+static smgrtable_hash *SMgrRelationHash = NULL;
 
 static dlist_head unowned_relns;
 
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
 
+/*
+ * relfilenodebackend_hash
+ *		Custom rolled hash function for simplehash table.
+ *
+ * smgropen() is often a bottleneck in CPU bound workloads during crash
+ * recovery.  We make use of this custom hash function rather than using
+ * hash_bytes as it gives us a little bit more performance.
+ *
+ * XXX What if sizeof(Oid) is not 4?
+ */
+static inline uint32
+relfilenodebackend_hash(RelFileNodeBackend *rnode)
+{
+	uint32		hashkey;
+
+	hashkey = murmurhash32((uint32) rnode->node.spcNode);
+
+	/* rotate hashkey left 1 bit at each step */
+	hashkey = pg_rotate_left32(hashkey, 1);
+	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
+
+	hashkey = pg_rotate_left32(hashkey, 1);
+	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
+
+	hashkey = pg_rotate_left32(hashkey, 1);
+	hashkey ^= murmurhash32((uint32) rnode->backend);
+
+	return hashkey;
+}
+
 
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
@@ -147,31 +212,26 @@ smgropen(RelFileNode rnode, BackendId backend)
 {
 	RelFileNodeBackend brnode;
 	SMgrRelation reln;
+	SMgrEntry  *entry;
 	bool		found;
 
-	if (SMgrRelationHash == NULL)
+	if (unlikely(SMgrRelationHash == NULL))
 	{
 		/* First time through: initialize the hash table */
-		HASHCTL		ctl;
-
-		ctl.keysize = sizeof(RelFileNodeBackend);
-		ctl.entrysize = sizeof(SMgrRelationData);
-		SMgrRelationHash = hash_create("smgr relation table", 400,
-									   &ctl, HASH_ELEM | HASH_BLOBS);
+		SMgrRelationHash = smgrtable_create(TopMemoryContext, 400, NULL);
 		dlist_init(&unowned_relns);
 	}
 
 	/* Look up or create an entry */
 	brnode.node = rnode;
 	brnode.backend = backend;
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &brnode,
-									  HASH_ENTER, &found);
+	entry = smgrtable_insert(SMgrRelationHash, brnode, &found);
+	reln = entry->data;
 
 	/* Initialize it if not present before */
 	if (!found)
 	{
-		/* hash_search already filled in the lookup key */
+		/* smgrtable_insert already filled in the lookup key */
 		reln->smgr_owner = NULL;
 		reln->smgr_targblock = InvalidBlockNumber;
 		for (int i = 0; i <= MAX_FORKNUM; ++i)
@@ -266,9 +326,7 @@ smgrclose(SMgrRelation reln)
 	if (!owner)
 		dlist_delete(&reln->node);
 
-	if (hash_search(SMgrRelationHash,
-					(void *) &(reln->smgr_rnode),
-					HASH_REMOVE, NULL) == NULL)
+	if (!smgrtable_delete(SMgrRelationHash, reln->smgr_rnode))
 		elog(ERROR, "SMgrRelation hashtable corrupted");
 
 	/*
@@ -285,17 +343,17 @@ smgrclose(SMgrRelation reln)
 void
 smgrcloseall(void)
 {
-	HASH_SEQ_STATUS status;
-	SMgrRelation reln;
+	smgrtable_iterator iterator;
+	SMgrEntry  *entry;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
 
-	hash_seq_init(&status, SMgrRelationHash);
+	smgrtable_start_iterate(SMgrRelationHash, &iterator);
 
-	while ((reln = (SMgrRelation) hash_seq_search(&status)) != NULL)
-		smgrclose(reln);
+	while ((entry = smgrtable_iterate(SMgrRelationHash, &iterator)) != NULL)
+		smgrclose(entry->data);
 }
 
 /*
@@ -309,17 +367,14 @@ smgrcloseall(void)
 void
 smgrclosenode(RelFileNodeBackend rnode)
 {
-	SMgrRelation reln;
+	SMgrEntry  *entry;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
-
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &rnode,
-									  HASH_FIND, NULL);
-	if (reln != NULL)
-		smgrclose(reln);
+	entry = smgrtable_lookup(SMgrRelationHash, rnode);
+	if (entry != NULL)
+		smgrclose(entry->data);
 }
 
 /*
diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index da51781e98..4fce182de6 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -50,6 +50,11 @@
  *	  - SH_HASH_KEY(table, key) - generate hash for the key
  *	  - SH_STORE_HASH - if defined the hash is stored in the elements
  *	  - SH_GET_HASH(tb, a) - return the field to store the hash in
+ *	  - SH_ENTRY_INITIALIZER(a) - if defined, the code in this macro is called
+ *		for new entries directly before any other internal code makes any
+ *		changes to setup the new entry
+ *	  - SH_ENTRY_CLEANUP(a) - if defined, the code in this macro is called
+ *		when an entry is removed from the hash table
  *
  *	  The element type is required to contain a "status" member that can store
  *	  the range of values defined in the SH_STATUS enum.
@@ -634,6 +639,9 @@ restart:
 		if (entry->status == SH_STATUS_EMPTY)
 		{
 			tb->members++;
+#ifdef SH_ENTRY_INITIALIZER
+			SH_ENTRY_INITIALIZER(entry);
+#endif
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
 			SH_GET_HASH(tb, entry) = hash;
@@ -721,6 +729,9 @@ restart:
 
 			/* and fill the now empty spot */
 			tb->members++;
+#ifdef SH_ENTRY_INITIALIZER
+			SH_ENTRY_INITIALIZER(entry);
+#endif
 
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
@@ -856,7 +867,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 			SH_ELEMENT_TYPE *lastentry = entry;
 
 			tb->members--;
-
+#ifdef SH_ENTRY_CLEANUP
+			SH_ENTRY_CLEANUP(entry);
+#endif
 			/*
 			 * Backward shift following elements till either an empty element
 			 * or an element at its optimal position is encountered.
@@ -919,6 +932,9 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 	curelem = entry - &tb->data[0];
 
 	tb->members--;
+#ifdef SH_ENTRY_CLEANUP
+	SH_ENTRY_CLEANUP(entry);
+#endif
 
 	/*
 	 * Backward shift following elements till either an empty element or an
@@ -1133,6 +1149,8 @@ SH_STAT(SH_TYPE * tb)
 #undef SH_DECLARE
 #undef SH_DEFINE
 #undef SH_GET_HASH
+#undef SH_ENTRY_INITIALIZER
+#undef SH_ENTRY_CLEANUP
 #undef SH_STORE_HASH
 #undef SH_USE_NONDEFAULT_ALLOCATOR
 #undef SH_EQUAL
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index f9b77ec278..581957fe55 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -215,7 +215,8 @@ extern int	(*pg_popcount64) (uint64 word);
 extern uint64 pg_popcount(const char *buf, int bytes);
 
 /*
- * Rotate the bits of "word" to the right by n bits.
+ * pg_rotate_right32
+ *		Rotate the bits of 'word' to the right by 'n' bits.
  */
 static inline uint32
 pg_rotate_right32(uint32 word, int n)
@@ -223,4 +224,14 @@ pg_rotate_right32(uint32 word, int n)
 	return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
 }
 
+/*
+ * pg_rotate_left32
+ *		Rotate the bits of 'word' to the left by 'n' bits.
+ */
+static inline uint32
+pg_rotate_left32(uint32 word, int n)
+{
+	return (word << n) | (word >> (sizeof(word) * BITS_PER_BYTE - n));
+}
+
 #endif							/* PG_BITUTILS_H */
-- 
2.21.0.windows.1

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 8310f73212..f291ded795 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -147,18 +147,19 @@ static inline uint32
 relfilenodebackend_hash(RelFileNodeBackend *rnode)
 {
 	uint32		hashkey;
+	uint32		hashkey2;
 
 	hashkey = murmurhash32((uint32) rnode->node.spcNode);
 
 	/* rotate hashkey left 1 bit at each step */
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
+	hashkey2 = murmurhash32((uint32) rnode->node.dbNode);
+	hashkey = hash_combine(hashkey, hashkey2);
 
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
+	hashkey2 = murmurhash32((uint32) rnode->node.relNode);
+	hashkey = hash_combine(hashkey, hashkey2);
 
-	hashkey = pg_rotate_left32(hashkey, 1);
-	hashkey ^= murmurhash32((uint32) rnode->backend);
+	hashkey2 = murmurhash32((uint32) rnode->backend);
+	hashkey = hash_combine(hashkey, hashkey2);
 
 	return hashkey;
 }

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index adfc6f67e2..5d34e06eab 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -7615,7 +7615,8 @@ StartupXLOG(void)
 				ereport(LOG,
 						(errmsg("last completed transaction was at log time %s",
 								timestamptz_to_str(xtime))));
-
+			smgrstats();
+			elog(PANIC, "recovery PANIC");
 			InRedo = false;
 		}
 		else
diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 64a26e06c6..850b51e316 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -183,6 +183,12 @@ smgr_entry_cleanup(SMgrRelation reln)
 	pfree(reln);
 }
 
+void
+smgrstats(void)
+{
+	if (SMgrRelationHash != NULL)
+		smgrtable_stat(SMgrRelationHash);
+}
 
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
diff --git a/src/include/storage/smgr.h b/src/include/storage/smgr.h
index a6fbf7b6a6..ac010af74a 100644
--- a/src/include/storage/smgr.h
+++ b/src/include/storage/smgr.h
@@ -77,6 +77,7 @@ typedef SMgrRelationData *SMgrRelation;
 #define SmgrIsTemp(smgr) \
 	RelFileNodeBackendIsTemp((smgr)->smgr_rnode)
 
+extern void smgrstats(void);
 extern void smgrinit(void);
 extern SMgrRelation smgropen(RelFileNode rnode, BackendId backend);
 extern bool smgrexists(SMgrRelation reln, ForkNumber forknum);

From ce604dfa855e765383656baf37bbc5ce51bb6034 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Thu, 22 Apr 2021 17:03:46 +1200
Subject: [PATCH v3] Use simplehash.h hashtables in SMgr

The hash table lookups done in SMgr can quite often be a bottleneck during
crash recovery.  Traditionally these use dynahash. Here we swap dynahash
out and use simplehash instead.  This improves lookup performance.

Some changes are required from simplehash.h here to make this work.  The
reason for this is that code external to smgr.c does point to the hashed
SMgrRelation. Since simplehash does reallocate the bucket array when
increasing the size of the table and also shuffle entries around during
deletes, code pointing directly into hash entries would be a bad idea. To
overcome this issue we only store a pointer to the SMgrRelationData in the
hash table entry and maintain a separate allocation for that data. This
does mean an additional pointer dereference during lookups, but only when
the hash value matches, so the significant majority of the time that will
only be done for the item we are actually looking for.

Since the hash table key is stored in the referenced SMgrRelation, we need
to add two new macros to allow simplehash to allocate the memory for the
SMgrEntry during inserts before it tries to set the key.  A new macro has
also been added to allow simplehash implementations to perform cleanup
when items are removed from the table.
---
 src/backend/storage/smgr/smgr.c | 111 ++++++++++++++++++++++++--------
 src/include/lib/simplehash.h    |  32 +++++++++
 2 files changed, 115 insertions(+), 28 deletions(-)

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 4dc24649df..209218f781 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -18,14 +18,49 @@
 #include "postgres.h"
 
 #include "access/xlog.h"
+#include "common/hashfn.h"
 #include "lib/ilist.h"
 #include "storage/bufmgr.h"
 #include "storage/ipc.h"
 #include "storage/md.h"
 #include "storage/smgr.h"
-#include "utils/hsearch.h"
 #include "utils/inval.h"
 
+/* Hash table entry type for SMgrRelationHash */
+typedef struct SMgrEntry
+{
+	int			status;			/* Hash table status */
+	uint32		hash;			/* Hash value (cached) */
+	SMgrRelation data;			/* Pointer to the SMgrRelationData */
+} SMgrEntry;
+
+static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
+
+/*
+ * Because simplehash.h does not provide a stable pointer to hash table
+ * entries, we don't make the element type a SMgrRelation directly, instead we
+ * use an SMgrEntry type which has a pointer to the data field.  simplehash can
+ * move entries around when adding or removing items from the hash table so
+ * having the SMgrRelation as a pointer inside the SMgrEntry allows external
+ * code to keep their own pointers to the SMgrRelation.  Relcache does this.
+ * We use the SH_ENTRY_INITIALIZER to allocate memory for the SMgrRelationData
+ * when a new entry is created.  We also define SH_ENTRY_CLEANUP to execute
+ * some cleanup when removing an item from the table.
+ */
+#define SH_PREFIX		smgrtable
+#define SH_ELEMENT_TYPE	SMgrEntry
+#define SH_KEY_TYPE		RelFileNodeBackend
+#define SH_KEY			data->smgr_rnode
+#define SH_HASH_KEY(tb, key)	relfilenodebackend_hash(&key)
+#define SH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(RelFileNodeBackend)) == 0)
+#define SH_SCOPE		static inline
+#define SH_STORE_HASH
+#define SH_GET_HASH(tb, a) a->hash
+#define SH_ENTRY_INITIALIZER(a) a->data = MemoryContextAlloc(TopMemoryContext, sizeof(SMgrRelationData))
+#define SH_ENTRY_CLEANUP(a) pfree(a->data)
+#define SH_DEFINE
+#define SH_DECLARE
+#include "lib/simplehash.h"
 
 /*
  * This struct of function pointers defines the API between smgr.c and
@@ -91,13 +126,43 @@ static const int NSmgr = lengthof(smgrsw);
  * Each backend has a hashtable that stores all extant SMgrRelation objects.
  * In addition, "unowned" SMgrRelation objects are chained together in a list.
  */
-static HTAB *SMgrRelationHash = NULL;
+static smgrtable_hash *SMgrRelationHash = NULL;
 
 static dlist_head unowned_relns;
 
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
 
+/*
+ * relfilenodebackend_hash
+ *		Custom rolled hash function for simplehash table.
+ *
+ * smgropen() is often a bottleneck in CPU bound workloads during crash
+ * recovery.  We make use of this custom hash function rather than using
+ * hash_bytes as it gives us a little bit more performance.
+ *
+ * XXX What if sizeof(Oid) is not 4?
+ */
+static inline uint32
+relfilenodebackend_hash(RelFileNodeBackend *rnode)
+{
+	uint32		hashkey;
+
+	hashkey = murmurhash32((uint32) rnode->node.spcNode);
+
+	/* rotate hashkey left 1 bit at each step */
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
+
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
+
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->backend);
+
+	return hashkey;
+}
+
 
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
@@ -147,31 +212,26 @@ smgropen(RelFileNode rnode, BackendId backend)
 {
 	RelFileNodeBackend brnode;
 	SMgrRelation reln;
+	SMgrEntry  *entry;
 	bool		found;
 
-	if (SMgrRelationHash == NULL)
+	if (unlikely(SMgrRelationHash == NULL))
 	{
 		/* First time through: initialize the hash table */
-		HASHCTL		ctl;
-
-		ctl.keysize = sizeof(RelFileNodeBackend);
-		ctl.entrysize = sizeof(SMgrRelationData);
-		SMgrRelationHash = hash_create("smgr relation table", 400,
-									   &ctl, HASH_ELEM | HASH_BLOBS);
+		SMgrRelationHash = smgrtable_create(TopMemoryContext, 400, NULL);
 		dlist_init(&unowned_relns);
 	}
 
 	/* Look up or create an entry */
 	brnode.node = rnode;
 	brnode.backend = backend;
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &brnode,
-									  HASH_ENTER, &found);
+	entry = smgrtable_insert(SMgrRelationHash, brnode, &found);
+	reln = entry->data;
 
 	/* Initialize it if not present before */
 	if (!found)
 	{
-		/* hash_search already filled in the lookup key */
+		/* smgrtable_insert already filled in the lookup key */
 		reln->smgr_owner = NULL;
 		reln->smgr_targblock = InvalidBlockNumber;
 		for (int i = 0; i <= MAX_FORKNUM; ++i)
@@ -266,9 +326,7 @@ smgrclose(SMgrRelation reln)
 	if (!owner)
 		dlist_delete(&reln->node);
 
-	if (hash_search(SMgrRelationHash,
-					(void *) &(reln->smgr_rnode),
-					HASH_REMOVE, NULL) == NULL)
+	if (!smgrtable_delete(SMgrRelationHash, reln->smgr_rnode))
 		elog(ERROR, "SMgrRelation hashtable corrupted");
 
 	/*
@@ -285,17 +343,17 @@ smgrclose(SMgrRelation reln)
 void
 smgrcloseall(void)
 {
-	HASH_SEQ_STATUS status;
-	SMgrRelation reln;
+	smgrtable_iterator iterator;
+	SMgrEntry  *entry;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
 
-	hash_seq_init(&status, SMgrRelationHash);
+	smgrtable_start_iterate(SMgrRelationHash, &iterator);
 
-	while ((reln = (SMgrRelation) hash_seq_search(&status)) != NULL)
-		smgrclose(reln);
+	while ((entry = smgrtable_iterate(SMgrRelationHash, &iterator)) != NULL)
+		smgrclose(entry->data);
 }
 
 /*
@@ -309,17 +367,14 @@ smgrcloseall(void)
 void
 smgrclosenode(RelFileNodeBackend rnode)
 {
-	SMgrRelation reln;
+	SMgrEntry  *entry;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
-
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &rnode,
-									  HASH_FIND, NULL);
-	if (reln != NULL)
-		smgrclose(reln);
+	entry = smgrtable_lookup(SMgrRelationHash, rnode);
+	if (entry != NULL)
+		smgrclose(entry->data);
 }
 
 /*
diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index da51781e98..2c4fc7e8c4 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -50,6 +50,13 @@
  *	  - SH_HASH_KEY(table, key) - generate hash for the key
  *	  - SH_STORE_HASH - if defined the hash is stored in the elements
  *	  - SH_GET_HASH(tb, a) - return the field to store the hash in
+ *	  - SH_ENTRY_INITIALIZER(a) - if defined, the code in this macro is called
+ *		for new entries directly before any other internal code makes any
+ *		changes to setup the new entry.  This could be used to do things like
+ *		initialize memory for the bucket.
+ *	  - SH_ENTRY_CLEANUP(a) - if defined, the code in this macro is called
+ *		when an entry is removed from the hash table.  This could be used to
+ *		free memory allocated in the bucket by SH_ENTRY_INITIALIZER
  *
  *	  The element type is required to contain a "status" member that can store
  *	  the range of values defined in the SH_STATUS enum.
@@ -464,6 +471,17 @@ SH_DESTROY(SH_TYPE * tb)
 SH_SCOPE void
 SH_RESET(SH_TYPE * tb)
 {
+#ifdef SH_ENTRY_CLEANUP
+	/* Execute the cleanup code when SH_ENTRY_CLEANUP has been defined */
+	for (int i = 0; i < tb->size; i++)
+	{
+		SH_ELEMENT_TYPE *entry = &tb->data[i];
+
+		if (entry->status == SH_STATUS_IN_USE)
+			SH_ENTRY_CLEANUP(entry);
+	}
+#endif
+
 	memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size);
 	tb->members = 0;
 }
@@ -634,6 +652,9 @@ restart:
 		if (entry->status == SH_STATUS_EMPTY)
 		{
 			tb->members++;
+#ifdef SH_ENTRY_INITIALIZER
+			SH_ENTRY_INITIALIZER(entry);
+#endif
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
 			SH_GET_HASH(tb, entry) = hash;
@@ -721,6 +742,9 @@ restart:
 
 			/* and fill the now empty spot */
 			tb->members++;
+#ifdef SH_ENTRY_INITIALIZER
+			SH_ENTRY_INITIALIZER(entry);
+#endif
 
 			entry->SH_KEY = key;
 #ifdef SH_STORE_HASH
@@ -856,6 +880,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
 			SH_ELEMENT_TYPE *lastentry = entry;
 
 			tb->members--;
+#ifdef SH_ENTRY_CLEANUP
+			SH_ENTRY_CLEANUP(entry);
+#endif
 
 			/*
 			 * Backward shift following elements till either an empty element
@@ -919,6 +946,9 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 	curelem = entry - &tb->data[0];
 
 	tb->members--;
+#ifdef SH_ENTRY_CLEANUP
+	SH_ENTRY_CLEANUP(entry);
+#endif
 
 	/*
 	 * Backward shift following elements till either an empty element or an
@@ -1133,6 +1163,8 @@ SH_STAT(SH_TYPE * tb)
 #undef SH_DECLARE
 #undef SH_DEFINE
 #undef SH_GET_HASH
+#undef SH_ENTRY_INITIALIZER
+#undef SH_ENTRY_CLEANUP
 #undef SH_STORE_HASH
 #undef SH_USE_NONDEFAULT_ALLOCATOR
 #undef SH_EQUAL
-- 
2.27.0

From 3974822be2b094c229bad9f638d3189f0892b81d Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 18 Jun 2021 04:22:11 +1200
Subject: [PATCH v1 1/2] Add a new hash table type which has stable pointers

This is named generichash.  It's similar and takes most of the code from
simplehash.h but provides stable pointers to hashed elements.  simplehash
will move these around which means it's not possible to have anything
point to your hash entry.

generichash.h allocates elements in "segments", by default 256 at a time.
When those are filled another segment is allocated.  When items are
removed from the table new items will try to fill from the lowest segment
with available space.  This should help reduce fragmentation of the data.

Sequential over the table should remain fast.  We use a bitmap to record
which elements of each segment are in use.  This allows us to quickly loop
over only used elements and skip to the next segment.

Make use of this new hash table type to help speed up the locallock table
in lock.c
---
 src/backend/storage/lmgr/lock.c    |  115 ++-
 src/backend/utils/cache/relcache.c |    9 +-
 src/include/lib/generichash.h      | 1409 ++++++++++++++++++++++++++++
 src/include/storage/lock.h         |    2 +-
 4 files changed, 1484 insertions(+), 51 deletions(-)
 create mode 100644 src/include/lib/generichash.h

diff --git a/src/backend/storage/lmgr/lock.c b/src/backend/storage/lmgr/lock.c
index 108b4d9023..081a06b417 100644
--- a/src/backend/storage/lmgr/lock.c
+++ b/src/backend/storage/lmgr/lock.c
@@ -37,6 +37,7 @@
 #include "access/twophase_rmgr.h"
 #include "access/xact.h"
 #include "access/xlog.h"
+#include "common/hashfn.h"
 #include "miscadmin.h"
 #include "pg_trace.h"
 #include "pgstat.h"
@@ -270,6 +271,19 @@ typedef struct
 
 static volatile FastPathStrongRelationLockData *FastPathStrongRelationLocks;
 
+#define GH_PREFIX				locallocktable
+#define GH_ELEMENT_TYPE			LOCALLOCK
+#define GH_KEY_TYPE				LOCALLOCKTAG
+#define GH_KEY					tag
+#define GH_HASH_KEY(tb, key)	hash_bytes((unsigned char *) &key, sizeof(LOCALLOCKTAG))
+#define GH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(LOCALLOCKTAG)) == 0)
+#define GH_ALLOCATE(b)			MemoryContextAllocExtended(TopMemoryContext, b, MCXT_ALLOC_HUGE)
+#define GH_ALLOCATE_ZERO(b)		MemoryContextAllocExtended(TopMemoryContext, b, MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO)
+#define GH_FREE(p)				pfree(p)
+#define GH_SCOPE				static inline
+#define GH_DECLARE
+#define GH_DEFINE
+#include "lib/generichash.h"
 
 /*
  * Pointers to hash tables containing lock state
@@ -279,7 +293,7 @@ static volatile FastPathStrongRelationLockData *FastPathStrongRelationLocks;
  */
 static HTAB *LockMethodLockHash;
 static HTAB *LockMethodProcLockHash;
-static HTAB *LockMethodLocalHash;
+static locallocktable_hash *LockMethodLocalHash;
 
 
 /* private state for error cleanup */
@@ -467,15 +481,9 @@ InitLocks(void)
 	 * ought to be empty in the postmaster, but for safety let's zap it.)
 	 */
 	if (LockMethodLocalHash)
-		hash_destroy(LockMethodLocalHash);
+		locallocktable_destroy(LockMethodLocalHash);
 
-	info.keysize = sizeof(LOCALLOCKTAG);
-	info.entrysize = sizeof(LOCALLOCK);
-
-	LockMethodLocalHash = hash_create("LOCALLOCK hash",
-									  16,
-									  &info,
-									  HASH_ELEM | HASH_BLOBS);
+	LockMethodLocalHash = locallocktable_create(16);
 }
 
 
@@ -606,22 +614,37 @@ LockHeldByMe(const LOCKTAG *locktag, LOCKMODE lockmode)
 	localtag.lock = *locktag;
 	localtag.mode = lockmode;
 
-	locallock = (LOCALLOCK *) hash_search(LockMethodLocalHash,
-										  (void *) &localtag,
-										  HASH_FIND, NULL);
+	locallock = locallocktable_lookup(LockMethodLocalHash, localtag);
 
 	return (locallock && locallock->nLocks > 0);
 }
 
 #ifdef USE_ASSERT_CHECKING
 /*
- * GetLockMethodLocalHash -- return the hash of local locks, for modules that
- *		evaluate assertions based on all locks held.
+ * GetLockMethodLocalLocks -- returns an array of all LOCALLOCKs stored in
+ *		LockMethodLocalHash.
+ *
+ * The caller must pfree the return value when done. *size is set to the
+ * number of elements in the returned array.
  */
-HTAB *
-GetLockMethodLocalHash(void)
+LOCALLOCK **
+GetLockMethodLocalLocks(uint32 *size)
 {
-	return LockMethodLocalHash;
+	locallocktable_iterator iterator;
+	LOCALLOCK **locallocks;
+	LOCALLOCK  *locallock;
+	uint32		i = 0;
+
+	locallocks = (LOCALLOCK **) palloc(sizeof(LOCALLOCK *) *
+									   LockMethodLocalHash->members);
+
+	locallocktable_start_iterate(LockMethodLocalHash, &iterator);
+	while ((locallock = locallocktable_iterate(LockMethodLocalHash,
+											   &iterator)) != NULL)
+		locallocks[i++] = locallock;
+
+	*size = i;
+	return locallocks;
 }
 #endif
 
@@ -661,9 +684,7 @@ LockHasWaiters(const LOCKTAG *locktag, LOCKMODE lockmode, bool sessionLock)
 	localtag.lock = *locktag;
 	localtag.mode = lockmode;
 
-	locallock = (LOCALLOCK *) hash_search(LockMethodLocalHash,
-										  (void *) &localtag,
-										  HASH_FIND, NULL);
+	locallock = locallocktable_lookup(LockMethodLocalHash, localtag);
 
 	/*
 	 * let the caller print its own error message, too. Do not ereport(ERROR).
@@ -823,9 +844,7 @@ LockAcquireExtended(const LOCKTAG *locktag,
 	localtag.lock = *locktag;
 	localtag.mode = lockmode;
 
-	locallock = (LOCALLOCK *) hash_search(LockMethodLocalHash,
-										  (void *) &localtag,
-										  HASH_ENTER, &found);
+	locallock = locallocktable_insert(LockMethodLocalHash, localtag, &found);
 
 	/*
 	 * if it's a new locallock object, initialize it
@@ -1390,9 +1409,7 @@ RemoveLocalLock(LOCALLOCK *locallock)
 		SpinLockRelease(&FastPathStrongRelationLocks->mutex);
 	}
 
-	if (!hash_search(LockMethodLocalHash,
-					 (void *) &(locallock->tag),
-					 HASH_REMOVE, NULL))
+	if (!locallocktable_delete(LockMethodLocalHash, locallock->tag))
 		elog(WARNING, "locallock table corrupted");
 
 	/*
@@ -2002,9 +2019,7 @@ LockRelease(const LOCKTAG *locktag, LOCKMODE lockmode, bool sessionLock)
 	localtag.lock = *locktag;
 	localtag.mode = lockmode;
 
-	locallock = (LOCALLOCK *) hash_search(LockMethodLocalHash,
-										  (void *) &localtag,
-										  HASH_FIND, NULL);
+	locallock = locallocktable_lookup(LockMethodLocalHash, localtag);
 
 	/*
 	 * let the caller print its own error message, too. Do not ereport(ERROR).
@@ -2178,7 +2193,7 @@ LockRelease(const LOCKTAG *locktag, LOCKMODE lockmode, bool sessionLock)
 void
 LockReleaseAll(LOCKMETHODID lockmethodid, bool allLocks)
 {
-	HASH_SEQ_STATUS status;
+	locallocktable_iterator iterator;
 	LockMethod	lockMethodTable;
 	int			i,
 				numLockModes;
@@ -2216,9 +2231,10 @@ LockReleaseAll(LOCKMETHODID lockmethodid, bool allLocks)
 	 * pointers.  Fast-path locks are cleaned up during the locallock table
 	 * scan, though.
 	 */
-	hash_seq_init(&status, LockMethodLocalHash);
+	locallocktable_start_iterate(LockMethodLocalHash, &iterator);
 
-	while ((locallock = (LOCALLOCK *) hash_seq_search(&status)) != NULL)
+	while ((locallock = locallocktable_iterate(LockMethodLocalHash,
+											   &iterator)) != NULL)
 	{
 		/*
 		 * If the LOCALLOCK entry is unused, we must've run out of shared
@@ -2452,15 +2468,16 @@ LockReleaseAll(LOCKMETHODID lockmethodid, bool allLocks)
 void
 LockReleaseSession(LOCKMETHODID lockmethodid)
 {
-	HASH_SEQ_STATUS status;
+	locallocktable_iterator iterator;
 	LOCALLOCK  *locallock;
 
 	if (lockmethodid <= 0 || lockmethodid >= lengthof(LockMethods))
 		elog(ERROR, "unrecognized lock method: %d", lockmethodid);
 
-	hash_seq_init(&status, LockMethodLocalHash);
+	locallocktable_start_iterate(LockMethodLocalHash, &iterator);
 
-	while ((locallock = (LOCALLOCK *) hash_seq_search(&status)) != NULL)
+	while ((locallock = locallocktable_iterate(LockMethodLocalHash,
+											   &iterator)) != NULL)
 	{
 		/* Ignore items that are not of the specified lock method */
 		if (LOCALLOCK_LOCKMETHOD(*locallock) != lockmethodid)
@@ -2484,12 +2501,13 @@ LockReleaseCurrentOwner(LOCALLOCK **locallocks, int nlocks)
 {
 	if (locallocks == NULL)
 	{
-		HASH_SEQ_STATUS status;
+		locallocktable_iterator iterator;
 		LOCALLOCK  *locallock;
 
-		hash_seq_init(&status, LockMethodLocalHash);
+		locallocktable_start_iterate(LockMethodLocalHash, &iterator);
 
-		while ((locallock = (LOCALLOCK *) hash_seq_search(&status)) != NULL)
+		while ((locallock = locallocktable_iterate(LockMethodLocalHash,
+												   &iterator)) != NULL)
 			ReleaseLockIfHeld(locallock, false);
 	}
 	else
@@ -2583,12 +2601,13 @@ LockReassignCurrentOwner(LOCALLOCK **locallocks, int nlocks)
 
 	if (locallocks == NULL)
 	{
-		HASH_SEQ_STATUS status;
+		locallocktable_iterator iterator;
 		LOCALLOCK  *locallock;
 
-		hash_seq_init(&status, LockMethodLocalHash);
+		locallocktable_start_iterate(LockMethodLocalHash, &iterator);
 
-		while ((locallock = (LOCALLOCK *) hash_seq_search(&status)) != NULL)
+		while ((locallock = locallocktable_iterate(LockMethodLocalHash,
+												   &iterator)) != NULL)
 			LockReassignOwner(locallock, parent);
 	}
 	else
@@ -3220,7 +3239,7 @@ LockRefindAndRelease(LockMethod lockMethodTable, PGPROC *proc,
 void
 AtPrepare_Locks(void)
 {
-	HASH_SEQ_STATUS status;
+	locallocktable_iterator iterator;
 	LOCALLOCK  *locallock;
 
 	/*
@@ -3229,9 +3248,10 @@ AtPrepare_Locks(void)
 	 * Fast-path locks are an exception, however: we move any such locks to
 	 * the main table before allowing PREPARE TRANSACTION to succeed.
 	 */
-	hash_seq_init(&status, LockMethodLocalHash);
+	locallocktable_start_iterate(LockMethodLocalHash, &iterator);
 
-	while ((locallock = (LOCALLOCK *) hash_seq_search(&status)) != NULL)
+	while ((locallock = locallocktable_iterate(LockMethodLocalHash,
+											   &iterator)) != NULL)
 	{
 		TwoPhaseLockRecord record;
 		LOCALLOCKOWNER *lockOwners = locallock->lockOwners;
@@ -3331,7 +3351,7 @@ void
 PostPrepare_Locks(TransactionId xid)
 {
 	PGPROC	   *newproc = TwoPhaseGetDummyProc(xid, false);
-	HASH_SEQ_STATUS status;
+	locallocktable_iterator iterator;
 	LOCALLOCK  *locallock;
 	LOCK	   *lock;
 	PROCLOCK   *proclock;
@@ -3354,9 +3374,10 @@ PostPrepare_Locks(TransactionId xid)
 	 * pointing to the same proclock, and we daren't end up with any dangling
 	 * pointers.
 	 */
-	hash_seq_init(&status, LockMethodLocalHash);
+	locallocktable_start_iterate(LockMethodLocalHash, &iterator);
 
-	while ((locallock = (LOCALLOCK *) hash_seq_search(&status)) != NULL)
+	while ((locallock = locallocktable_iterate(LockMethodLocalHash,
+											   &iterator)) != NULL)
 	{
 		LOCALLOCKOWNER *lockOwners = locallock->lockOwners;
 		bool		haveSessionLock;
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index d55ae016d0..85b1c52870 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -3004,12 +3004,13 @@ void
 AssertPendingSyncs_RelationCache(void)
 {
 	HASH_SEQ_STATUS status;
-	LOCALLOCK  *locallock;
+	LOCALLOCK **locallocks;
 	Relation   *rels;
 	int			maxrels;
 	int			nrels;
 	RelIdCacheEnt *idhentry;
 	int			i;
+	uint32		nlocallocks;
 
 	/*
 	 * Open every relation that this transaction has locked.  If, for some
@@ -3022,9 +3023,10 @@ AssertPendingSyncs_RelationCache(void)
 	maxrels = 1;
 	rels = palloc(maxrels * sizeof(*rels));
 	nrels = 0;
-	hash_seq_init(&status, GetLockMethodLocalHash());
-	while ((locallock = (LOCALLOCK *) hash_seq_search(&status)) != NULL)
+	locallocks = GetLockMethodLocalLocks(&nlocallocks);
+	for (i = 0; i < nlocallocks; i++)
 	{
+		LOCALLOCK  *locallock = locallocks[i];
 		Oid			relid;
 		Relation	r;
 
@@ -3044,6 +3046,7 @@ AssertPendingSyncs_RelationCache(void)
 		}
 		rels[nrels++] = r;
 	}
+	pfree(locallocks);
 
 	hash_seq_init(&status, RelationIdCache);
 	while ((idhentry = (RelIdCacheEnt *) hash_seq_search(&status)) != NULL)
diff --git a/src/include/lib/generichash.h b/src/include/lib/generichash.h
new file mode 100644
index 0000000000..3e075d1676
--- /dev/null
+++ b/src/include/lib/generichash.h
@@ -0,0 +1,1409 @@
+/*
+ * generichash.h
+ *
+ *	  A hashtable implementation which can be included into .c files to
+ *	  provide a fast hash table implementation specific to the given type.
+ *
+ *	  GH_ELEMENT_TYPE defines the data type that the hashtable stores.  Each
+ *	  instance of GH_ELEMENT_TYPE which is stored in the hash table is done so
+ *	  inside a GH_SEGMENT.  These GH_SEGMENTs are allocated on demand and
+ *	  store GH_ITEMS_PER_SEGMENT each.  After items are removed from the hash
+ *	  table, the next inserted item's data will be stored in the earliest free
+ *	  item in the earliest free segment.  This helps keep the actual data
+ *	  compact even when the bucket array has become large.
+ *
+ *	  The bucket array is an array of GH_BUCKET and is dynamically allocated
+ *	  and may grow as more items are added to the table.  The GH_BUCKET type
+ *	  is very narrow and stores just 2 uint32 values.  One of these is the
+ *	  hash value and the other is the index into the segments which are used
+ *	  to directly look up the stored GH_ELEMENT_TYPE type.
+ *
+ *	  During inserts, hash table collisions are dealt with using linear
+ *	  probing, this means that instead of doing something like chaining with a
+ *	  linked list, we use the first free bucket which comes after the optimal
+ *	  bucket.  This is much more CPU cache efficient than traversing a linked
+ *	  list.  When we're unable to use the most optimal bucket, we may also
+ *	  move the contexts of subsequent buckets around so that we keep items as
+ *	  close to their most optimal position as possible.  This prevents
+ *	  excessively long linear probes during lookups.
+ *
+ *	  During hash table deletes, we must attempt to move the contents of
+ *	  buckets that are not in their optimal position up to either their
+ *	  optimal position, or as close as we can get to it.  During lookups, this
+ *	  means that we can stop searching for a non-existing item as soon as we
+ *	  find an empty bucket.
+ *
+ *	  Empty buckets are denoted by their 'index' field being set to
+ *	  GH_UNUSED_BUCKET_INDEX.  This is done rather than adding a special field
+ *	  so that we can keep the GH_BUCKET type as narrow as possible.
+ *	  Conveniently sizeof(GH_BUCKET) is 8, which allows 8 of these to fit on a
+ *	  single 64-byte cache line. It's important to keep this type as narrow as
+ *	  possible so that we can perform hash lookups by hitting as few
+ *	  cache lines as possible.
+ *
+ *	  The implementation here is similar to simplehash.h but has the following
+ *	  benefits:
+ *
+ *	  - Pointers to elements are stable and are not moved around like they are
+ *		in simplehash.h
+ *	  - Sequential scans of the hash table remain very fast even when the
+ *		table is sparsely populated.
+ *	  - Moving the contents of buckets around during inserts and deletes is
+ *		generally cheaper here due to GH_BUCKET being very narrow.
+ *
+ * If none of the above points are important for the given use case then,
+ * please consider using simplehash.h instead.
+ *
+ *
+ * Portions Copyright (c) 2021, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *		src/include/lib/generichash.h
+ *
+ */
+
+#include "port/pg_bitutils.h"
+
+/* helpers */
+#define GH_MAKE_PREFIX(a) CppConcat(a,_)
+#define GH_MAKE_NAME(name) GH_MAKE_NAME_(GH_MAKE_PREFIX(GH_PREFIX),name)
+#define GH_MAKE_NAME_(a,b) CppConcat(a,b)
+
+/* type declarations */
+#define GH_TYPE GH_MAKE_NAME(hash)
+#define GH_BUCKET GH_MAKE_NAME(bucket)
+#define GH_SEGMENT GH_MAKE_NAME(segment)
+#define GH_ITERATOR GH_MAKE_NAME(iterator)
+
+/* function declarations */
+#define GH_CREATE GH_MAKE_NAME(create)
+#define GH_DESTROY GH_MAKE_NAME(destroy)
+#define GH_RESET GH_MAKE_NAME(reset)
+#define GH_INSERT GH_MAKE_NAME(insert)
+#define GH_INSERT_HASH GH_MAKE_NAME(insert_hash)
+#define GH_DELETE GH_MAKE_NAME(delete)
+#define GH_LOOKUP GH_MAKE_NAME(lookup)
+#define GH_LOOKUP_HASH GH_MAKE_NAME(lookup_hash)
+#define GH_GROW GH_MAKE_NAME(grow)
+#define GH_START_ITERATE GH_MAKE_NAME(start_iterate)
+#define GH_ITERATE GH_MAKE_NAME(iterate)
+
+/* internal helper functions (no externally visible prototypes) */
+#define GH_NEXT_ONEBIT GH_MAKE_NAME(next_onebit)
+#define GH_NEXT_ZEROBIT GH_MAKE_NAME(next_zerobit)
+#define GH_INDEX_TO_ELEMENT GH_MAKE_NAME(index_to_element)
+#define GH_MARK_SEGMENT_ITEM_USED GH_MAKE_NAME(mark_segment_item_used)
+#define GH_MARK_SEGMENT_ITEM_UNUSED GH_MAKE_NAME(mark_segment_item_unused)
+#define GH_GET_NEXT_UNUSED_ENTRY GH_MAKE_NAME(get_next_unused_entry)
+#define GH_REMOVE_ENTRY GH_MAKE_NAME(remove_entry)
+#define GH_SET_BUCKET_IN_USE GH_MAKE_NAME(set_bucket_in_use)
+#define GH_SET_BUCKET_EMPTY GH_MAKE_NAME(set_bucket_empty)
+#define GH_IS_BUCKET_IN_USE GH_MAKE_NAME(is_bucket_in_use)
+#define GH_COMPUTE_PARAMETERS GH_MAKE_NAME(compute_parameters)
+#define GH_NEXT GH_MAKE_NAME(next)
+#define GH_PREV GH_MAKE_NAME(prev)
+#define GH_DISTANCE_FROM_OPTIMAL GH_MAKE_NAME(distance)
+#define GH_INITIAL_BUCKET GH_MAKE_NAME(initial_bucket)
+#define GH_INSERT_HASH_INTERNAL GH_MAKE_NAME(insert_hash_internal)
+#define GH_LOOKUP_HASH_INTERNAL GH_MAKE_NAME(lookup_hash_internal)
+
+/*
+ * When allocating memory to store instances of GH_ELEMENT_TYPE, how many
+ * should we allocate at once?  This must be a power of 2 and at least
+ * GH_BITS_PER_WORD.
+ */
+#ifndef GH_ITEMS_PER_SEGMENT
+#define GH_ITEMS_PER_SEGMENT	256
+#endif
+
+/* A special index to set GH_BUCKET->index to when it's not in use */
+#define GH_UNUSED_BUCKET_INDEX	PG_UINT32_MAX
+
+/*
+ * Macros for translating a bucket's index into the segment and another to
+ * determine the item number within the segment.
+ */
+#define GH_INDEX_SEGMENT(i)	(i) / GH_ITEMS_PER_SEGMENT
+#define GH_INDEX_ITEM(i)	(i) % GH_ITEMS_PER_SEGMENT
+
+ /*
+  * How many elements do we need in the bitmap array to store a bit for each
+  * of GH_ITEMS_PER_SEGMENT.  Keep the word size native to the processor.
+  */
+#if SIZEOF_VOID_P >= 8
+
+#define GH_BITS_PER_WORD		64
+#define GH_BITMAP_WORD			uint64
+#define GH_RIGHTMOST_ONE_POS(x) pg_rightmost_one_pos64(x)
+
+#else
+
+#define GH_BITS_PER_WORD		32
+#define GH_BITMAP_WORD			uint32
+#define GH_RIGHTMOST_ONE_POS(x) pg_rightmost_one_pos32(x)
+
+#endif
+
+/* Sanity check on GH_ITEMS_PER_SEGMENT setting */
+#if GH_ITEMS_PER_SEGMENT < GH_BITS_PER_WORD
+#error "GH_ITEMS_PER_SEGMENT must be >= than GH_BITS_PER_WORD"
+#endif
+
+/* Ensure GH_ITEMS_PER_SEGMENT is a power of 2 */
+#if GH_ITEMS_PER_SEGMENT & (GH_ITEMS_PER_SEGMENT - 1) != 0
+#error "GH_ITEMS_PER_SEGMENT must be a power of 2"
+#endif
+
+#define GH_BITMAP_WORDS			(GH_ITEMS_PER_SEGMENT / GH_BITS_PER_WORD)
+#define GH_WORDNUM(x)			((x) / GH_BITS_PER_WORD)
+#define GH_BITNUM(x)			((x) % GH_BITS_PER_WORD)
+
+/* generate forward declarations necessary to use the hash table */
+#ifdef GH_DECLARE
+
+typedef struct GH_BUCKET
+{
+	uint32		hashvalue;		/* Hash value for this bucket */
+	uint32		index;			/* Index to the actual data */
+}			GH_BUCKET;
+
+typedef struct GH_SEGMENT
+{
+	uint32		nitems;			/* Number of items stored */
+	GH_BITMAP_WORD used_items[GH_BITMAP_WORDS]; /* A 1-bit for each used item
+												 * in the items array */
+	GH_ELEMENT_TYPE items[GH_ITEMS_PER_SEGMENT];	/* the actual data */
+}			GH_SEGMENT;
+
+/* type definitions */
+
+/*
+ * GH_TYPE
+ *		Hash table metadata type
+ */
+typedef struct GH_TYPE
+{
+	/*
+	 * Size of bucket array.  Note that the maximum number of elements is
+	 * lower (GH_MAX_FILLFACTOR)
+	 */
+	uint32		size;
+
+	/* mask for bucket and size calculations, based on size */
+	uint32		sizemask;
+
+	/* the number of elements stored */
+	uint32		members;
+
+	/* boundary after which to grow hashtable */
+	uint32		grow_threshold;
+
+	/* how many elements are there in the segments array */
+	uint32		nsegments;
+
+	/* the number of elements in the used_segments array */
+	uint32		used_segment_words;
+
+	/*
+	 * The first segment we should search in for an empty slot.  This will be
+	 * the first segment that GH_GET_NEXT_UNUSED_ENTRY will search in when
+	 * looking for an unused entry.  We'll increase the value of this when we
+	 * fill a segment and we'll lower it down when we delete an item from a
+	 * segment lower than this value.
+	 */
+	uint32		first_free_segment;
+
+	/* dynamically allocated array of hash buckets */
+	GH_BUCKET  *buckets;
+
+	/* an array of segment pointers to store data */
+	GH_SEGMENT **segments;
+
+	/*
+	 * A bitmap of non-empty segments.  A 1-bit denotes that the corresponding
+	 * segment is non-empty.
+	 */
+	GH_BITMAP_WORD *used_segments;
+
+#ifdef GH_HAVE_PRIVATE_DATA
+	/* user defined data, useful for callbacks */
+	void	   *private_data;
+#endif
+}			GH_TYPE;
+
+/*
+ * GH_ITERATOR
+ *		Used when looping over the contents of the hash table.
+ */
+typedef struct GH_ITERATOR
+{
+	int32		cursegidx;		/* current segment. -1 means not started */
+	int32		curitemidx;		/* current item within cursegidx, -1 means not
+								 * started */
+	uint32		found_members;	/* number of items visitied so far in the loop */
+	uint32		total_members;	/* number of items that existed at the start
+								 * iteration. */
+}			GH_ITERATOR;
+
+/* externally visible function prototypes */
+
+#ifdef GH_HAVE_PRIVATE_DATA
+/* <prefix>_hash <prefix>_create(uint32 nbuckets, void *private_data) */
+GH_SCOPE	GH_TYPE *GH_CREATE(uint32 nbuckets, void *private_data);
+#else
+/* <prefix>_hash <prefix>_create(uint32 nbuckets) */
+GH_SCOPE	GH_TYPE *GH_CREATE(uint32 nbuckets);
+#endif
+
+/* void <prefix>_destroy(<prefix>_hash *tb) */
+GH_SCOPE void GH_DESTROY(GH_TYPE * tb);
+
+/* void <prefix>_reset(<prefix>_hash *tb) */
+GH_SCOPE void GH_RESET(GH_TYPE * tb);
+
+/* void <prefix>_grow(<prefix>_hash *tb) */
+GH_SCOPE void GH_GROW(GH_TYPE * tb, uint32 newsize);
+
+/* <element> *<prefix>_insert(<prefix>_hash *tb, <key> key, bool *found) */
+GH_SCOPE	GH_ELEMENT_TYPE *GH_INSERT(GH_TYPE * tb, GH_KEY_TYPE key,
+									   bool *found);
+
+/*
+ * <element> *<prefix>_insert_hash(<prefix>_hash *tb, <key> key, uint32 hash,
+ * 								   bool *found)
+ */
+GH_SCOPE	GH_ELEMENT_TYPE *GH_INSERT_HASH(GH_TYPE * tb, GH_KEY_TYPE key,
+											uint32 hash, bool *found);
+
+/* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
+GH_SCOPE	GH_ELEMENT_TYPE *GH_LOOKUP(GH_TYPE * tb, GH_KEY_TYPE key);
+
+/* <element> *<prefix>_lookup_hash(<prefix>_hash *tb, <key> key, uint32 hash) */
+GH_SCOPE	GH_ELEMENT_TYPE *GH_LOOKUP_HASH(GH_TYPE * tb, GH_KEY_TYPE key,
+											uint32 hash);
+
+/* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
+GH_SCOPE bool GH_DELETE(GH_TYPE * tb, GH_KEY_TYPE key);
+
+/* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
+GH_SCOPE void GH_START_ITERATE(GH_TYPE * tb, GH_ITERATOR * iter);
+
+/* <element> *<prefix>_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
+GH_SCOPE	GH_ELEMENT_TYPE *GH_ITERATE(GH_TYPE * tb, GH_ITERATOR * iter);
+
+#endif							/* GH_DECLARE */
+
+/* generate implementation of the hash table */
+#ifdef GH_DEFINE
+
+/*
+ * The maximum size for the hash table.  This must be a power of 2.  We cannot
+ * make this PG_UINT32_MAX + 1 because we use GH_UNUSED_BUCKET_INDEX denote an
+ * empty bucket.  Doing so would mean we could accidentally set a used
+ * bucket's index to GH_UNUSED_BUCKET_INDEX.
+ */
+#define GH_MAX_SIZE ((uint32) PG_INT32_MAX + 1)
+
+/* normal fillfactor, unless already close to maximum */
+#ifndef GH_FILLFACTOR
+#define GH_FILLFACTOR (0.9)
+#endif
+/* increase fillfactor if we otherwise would error out */
+#define GH_MAX_FILLFACTOR (0.98)
+/* grow if actual and optimal location bigger than */
+#ifndef GH_GROW_MAX_DIB
+#define GH_GROW_MAX_DIB 25
+#endif
+/*
+ * Grow if more than this number of buckets needs to be moved when inserting.
+ */
+#ifndef GH_GROW_MAX_MOVE
+#define GH_GROW_MAX_MOVE 150
+#endif
+#ifndef GH_GROW_MIN_FILLFACTOR
+/* but do not grow due to GH_GROW_MAX_* if below */
+#define GH_GROW_MIN_FILLFACTOR 0.1
+#endif
+
+/*
+ * Wrap the following definitions in include guards, to avoid multiple
+ * definition errors if this header is included more than once.  The rest of
+ * the file deliberately has no include guards, because it can be included
+ * with different parameters to define functions and types with non-colliding
+ * names.
+ */
+#ifndef GENERICHASH_H
+#define GENERICHASH_H
+
+#ifdef FRONTEND
+#define gh_error(...) pg_log_error(__VA_ARGS__)
+#define gh_log(...) pg_log_info(__VA_ARGS__)
+#else
+#define gh_error(...) elog(ERROR, __VA_ARGS__)
+#define gh_log(...) elog(LOG, __VA_ARGS__)
+#endif
+
+#endif							/* GENERICHASH_H */
+
+/*
+ * Gets the position of the first 1-bit which comes after 'prevbit' in the
+ * 'words' array.  'nwords' is the size of the 'words' array.
+ */
+static inline int32
+GH_NEXT_ONEBIT(GH_BITMAP_WORD * words, uint32 nwords, int32 prevbit)
+{
+	uint32		wordnum;
+
+	prevbit++;
+
+	wordnum = GH_WORDNUM(prevbit);
+	if (wordnum < nwords)
+	{
+		GH_BITMAP_WORD mask = (~(GH_BITMAP_WORD) 0) << GH_BITNUM(prevbit);
+		GH_BITMAP_WORD word = words[wordnum] & mask;
+
+		if (word != 0)
+			return wordnum * GH_BITS_PER_WORD + GH_RIGHTMOST_ONE_POS(word);
+
+		for (++wordnum; wordnum < nwords; wordnum++)
+		{
+			word = words[wordnum];
+
+			if (word != 0)
+			{
+				int32		result = wordnum * GH_BITS_PER_WORD;
+
+				result += GH_RIGHTMOST_ONE_POS(word);
+				return result;
+			}
+		}
+	}
+	return -1;
+}
+
+/*
+ * Gets the position of the first 0-bit which comes after 'prevbit' in the
+ * 'words' array.  'nwords' is the size of the 'words' array.
+ *
+ * This is similar to GH_NEXT_ONEBIT but flips the bits before operating on
+ * each GH_BITMAP_WORD.
+ */
+static inline int32
+GH_NEXT_ZEROBIT(GH_BITMAP_WORD * words, uint32 nwords, int32 prevbit)
+{
+	uint32		wordnum;
+
+	prevbit++;
+
+	wordnum = GH_WORDNUM(prevbit);
+	if (wordnum < nwords)
+	{
+		GH_BITMAP_WORD mask = (~(GH_BITMAP_WORD) 0) << GH_BITNUM(prevbit);
+		GH_BITMAP_WORD word = ~(words[wordnum] & mask); /* flip bits */
+
+		if (word != 0)
+			return wordnum * GH_BITS_PER_WORD + GH_RIGHTMOST_ONE_POS(word);
+
+		for (++wordnum; wordnum < nwords; wordnum++)
+		{
+			word = ~words[wordnum]; /* flip bits */
+
+			if (word != 0)
+			{
+				int32		result = wordnum * GH_BITS_PER_WORD;
+
+				result += GH_RIGHTMOST_ONE_POS(word);
+				return result;
+			}
+		}
+	}
+	return -1;
+}
+
+/*
+ * Finds the hash table entry for a given GH_BUCKET's 'index'.
+ */
+static inline GH_ELEMENT_TYPE *
+GH_INDEX_TO_ELEMENT(GH_TYPE * tb, uint32 index)
+{
+	GH_SEGMENT *seg;
+	uint32		segidx;
+	uint32		item;
+
+	segidx = GH_INDEX_SEGMENT(index);
+	item = GH_INDEX_ITEM(index);
+
+	Assert(segidx < tb->nsegments);
+
+	seg = tb->segments[segidx];
+
+	Assert(seg != NULL);
+
+	/* ensure this segment is marked as used */
+	Assert(seg->used_items[GH_WORDNUM(item)] & (((GH_BITMAP_WORD) 1) << GH_BITNUM(item)));
+
+	return &seg->items[item];
+}
+
+static inline void
+GH_MARK_SEGMENT_ITEM_USED(GH_TYPE * tb, GH_SEGMENT * seg, uint32 segidx,
+						  uint32 segitem)
+{
+	uint32		word = GH_WORDNUM(segitem);
+	uint32		bit = GH_BITNUM(segitem);
+
+	/* ensure this item is not marked as used */
+	Assert((seg->used_items[word] & (((GH_BITMAP_WORD) 1) << bit)) == 0);
+
+	/* switch on the used bit */
+	seg->used_items[word] |= (((GH_BITMAP_WORD) 1) << bit);
+
+	/* if the segment was previously empty then mark it as used */
+	if (seg->nitems == 0)
+	{
+		word = GH_WORDNUM(segidx);
+		bit = GH_BITNUM(segidx);
+
+		/* switch on the used bit for this segment */
+		tb->used_segments[word] |= (((GH_BITMAP_WORD) 1) << bit);
+	}
+	seg->nitems++;
+}
+
+static inline void
+GH_MARK_SEGMENT_ITEM_UNUSED(GH_TYPE * tb, GH_SEGMENT * seg, uint32 segidx,
+							uint32 segitem)
+{
+	uint32		word = GH_WORDNUM(segitem);
+	uint32		bit = GH_BITNUM(segitem);
+
+	/* ensure this item is marked as used */
+	Assert((seg->used_items[word] & (((GH_BITMAP_WORD) 1) << bit)) != 0);
+
+	/* switch off the used bit */
+	seg->used_items[word] &= ~(((GH_BITMAP_WORD) 1) << bit);
+
+	/* when removing the last item mark the segment as unused */
+	if (seg->nitems == 1)
+	{
+		word = GH_WORDNUM(segidx);
+		bit = GH_BITNUM(segidx);
+
+		/* switch off the used bit for this segment */
+		tb->used_segments[word] &= ~(((GH_BITMAP_WORD) 1) << bit);
+	}
+
+	seg->nitems--;
+}
+
+/*
+ * Returns the first unused entry from the first non-full segment and set
+ * *index to the index of the returned entry.
+ */
+static inline GH_ELEMENT_TYPE *
+GH_GET_NEXT_UNUSED_ENTRY(GH_TYPE * tb, uint32 *index)
+{
+	GH_SEGMENT *seg;
+	uint32		segidx = tb->first_free_segment;
+	uint32		itemidx;
+
+	seg = tb->segments[segidx];
+
+	/* find the first segment with an unused item */
+	while (seg != NULL && seg->nitems == GH_ITEMS_PER_SEGMENT)
+		seg = tb->segments[++segidx];
+
+	tb->first_free_segment = segidx;
+
+	/* allocate the segment if it's not already */
+	if (seg == NULL)
+	{
+		seg = GH_ALLOCATE(sizeof(GH_SEGMENT));
+		tb->segments[segidx] = seg;
+
+		seg->nitems = 0;
+		memset(seg->used_items, 0, sizeof(seg->used_items));
+		/* no need to zero the items array */
+
+		/* use the first slot in this segment */
+		itemidx = 0;
+	}
+	else
+	{
+		/* find the first unused item in this segment */
+		itemidx = GH_NEXT_ZEROBIT(seg->used_items, GH_BITMAP_WORDS, -1);
+		Assert(itemidx >= 0);
+	}
+
+	/* this is a good spot to ensure nitems matches the bits in used_items */
+	Assert(seg->nitems == pg_popcount((const char *) seg->used_items, GH_ITEMS_PER_SEGMENT / 8));
+
+	GH_MARK_SEGMENT_ITEM_USED(tb, seg, segidx, itemidx);
+
+	*index = segidx * GH_ITEMS_PER_SEGMENT + itemidx;
+	return &seg->items[itemidx];
+
+}
+
+/*
+ * Remove the entry denoted by 'index' from its segment.
+ */
+static inline void
+GH_REMOVE_ENTRY(GH_TYPE * tb, uint32 index)
+{
+	GH_SEGMENT *seg;
+	uint32		segidx = GH_INDEX_SEGMENT(index);
+	uint32		item = GH_INDEX_ITEM(index);
+
+	Assert(segidx < tb->nsegments);
+	seg = tb->segments[segidx];
+	Assert(seg != NULL);
+
+	GH_MARK_SEGMENT_ITEM_UNUSED(tb, seg, segidx, item);
+
+	/*
+	 * Lower the first free segment index to point to this segment so that the
+	 * next insert will store in this segment.  If it's already pointing to an
+	 * earlier segment, then leave it be.
+	 */
+	if (tb->first_free_segment > segidx)
+		tb->first_free_segment = segidx;
+}
+
+/*
+ * Set 'bucket' as in use by 'index'.
+ */
+static inline void
+GH_SET_BUCKET_IN_USE(GH_BUCKET * bucket, uint32 index)
+{
+	bucket->index = index;
+}
+
+/*
+ * Mark 'bucket' as unused.
+ */
+static inline void
+GH_SET_BUCKET_EMPTY(GH_BUCKET * bucket)
+{
+	bucket->index = GH_UNUSED_BUCKET_INDEX;
+}
+
+/*
+ * Return true if 'bucket' is in use.
+ */
+static inline bool
+GH_IS_BUCKET_IN_USE(GH_BUCKET * bucket)
+{
+	return bucket->index != GH_UNUSED_BUCKET_INDEX;
+}
+
+ /*
+  * Compute sizing parameters for hashtable.  Called when creating and growing
+  * the hashtable.
+  */
+static inline void
+GH_COMPUTE_PARAMETERS(GH_TYPE * tb, uint32 newsize)
+{
+	uint32		size;
+
+	/*
+	 * Ensure the bucket array size has not exceeded GH_MAX_SIZE or wrapped
+	 * back to zero.
+	 */
+	if (newsize == 0 || newsize > GH_MAX_SIZE)
+		gh_error("hash table too large");
+
+	/*
+	 * Ensure we don't build a table that can't store an entire single segment
+	 * worth of data.
+	 */
+	size = Max(newsize, GH_ITEMS_PER_SEGMENT);
+
+	/* round up size to the next power of 2 */
+	size = pg_nextpower2_32(size);
+
+	/* now set size */
+	tb->size = size;
+	tb->sizemask = tb->size - 1;
+
+	/* calculate how many segments we'll need to store 'size' items */
+	tb->nsegments = pg_nextpower2_32(size / GH_ITEMS_PER_SEGMENT);
+
+	/*
+	 * Calculate the number of bitmap words needed to store a bit for each
+	 * segment.
+	 */
+	tb->used_segment_words = (tb->nsegments + GH_BITS_PER_WORD - 1) / GH_BITS_PER_WORD;
+
+	/*
+	 * Compute the next threshold at which we need to grow the hash table
+	 * again.
+	 */
+	if (tb->size == GH_MAX_SIZE)
+		tb->grow_threshold = (uint32) (((double) tb->size) * GH_MAX_FILLFACTOR);
+	else
+		tb->grow_threshold = (uint32) (((double) tb->size) * GH_FILLFACTOR);
+}
+
+/* return the optimal bucket for the hash */
+static inline uint32
+GH_INITIAL_BUCKET(GH_TYPE * tb, uint32 hash)
+{
+	return hash & tb->sizemask;
+}
+
+/* return the next bucket after the current, handling wraparound */
+static inline uint32
+GH_NEXT(GH_TYPE * tb, uint32 curelem, uint32 startelem)
+{
+	curelem = (curelem + 1) & tb->sizemask;
+
+	Assert(curelem != startelem);
+
+	return curelem;
+}
+
+/* return the bucket before the current, handling wraparound */
+static inline uint32
+GH_PREV(GH_TYPE * tb, uint32 curelem, uint32 startelem)
+{
+	curelem = (curelem - 1) & tb->sizemask;
+
+	Assert(curelem != startelem);
+
+	return curelem;
+}
+
+/* return the distance between a bucket and its optimal position */
+static inline uint32
+GH_DISTANCE_FROM_OPTIMAL(GH_TYPE * tb, uint32 optimal, uint32 bucket)
+{
+	if (optimal <= bucket)
+		return bucket - optimal;
+	else
+		return (tb->size + bucket) - optimal;
+}
+
+/*
+ * Create a hash table with 'nbuckets' buckets.
+ */
+GH_SCOPE	GH_TYPE *
+#ifdef GH_HAVE_PRIVATE_DATA
+GH_CREATE(uint32 nbuckets, void *private_data)
+#else
+GH_CREATE(uint32 nbuckets)
+#endif
+{
+	GH_TYPE    *tb;
+	uint32		size;
+	uint32		i;
+
+	tb = GH_ALLOCATE_ZERO(sizeof(GH_TYPE));
+
+#ifdef GH_HAVE_PRIVATE_DATA
+	tb->private_data = private_data;
+#endif
+
+	/* increase nelements by fillfactor, want to store nelements elements */
+	size = (uint32) Min((double) GH_MAX_SIZE, ((double) nbuckets) / GH_FILLFACTOR);
+
+	GH_COMPUTE_PARAMETERS(tb, size);
+
+	tb->buckets = GH_ALLOCATE(sizeof(GH_BUCKET) * tb->size);
+
+	/* ensure all the buckets are set to empty */
+	for (i = 0; i < tb->size; i++)
+		GH_SET_BUCKET_EMPTY(&tb->buckets[i]);
+
+	tb->segments = GH_ALLOCATE_ZERO(sizeof(GH_SEGMENT *) * tb->nsegments);
+	tb->used_segments = GH_ALLOCATE_ZERO(sizeof(GH_BITMAP_WORD) * tb->used_segment_words);
+	return tb;
+}
+
+/* destroy a previously created hash table */
+GH_SCOPE void
+GH_DESTROY(GH_TYPE * tb)
+{
+	GH_FREE(tb->buckets);
+
+	/* Free each segment one by one */
+	for (uint32 n = 0; n < tb->nsegments; n++)
+	{
+		if (tb->segments[n] != NULL)
+			GH_FREE(tb->segments[n]);
+	}
+
+	GH_FREE(tb->segments);
+	GH_FREE(tb->used_segments);
+
+	pfree(tb);
+}
+
+/* reset the contents of a previously created hash table */
+GH_SCOPE void
+GH_RESET(GH_TYPE * tb)
+{
+	int32		i = -1;
+	uint32		x;
+
+	/* reset each used segment one by one */
+	while ((i = GH_NEXT_ONEBIT(tb->used_segments, tb->used_segment_words,
+							   i)) >= 0)
+	{
+		GH_SEGMENT *seg = tb->segments[i];
+
+		Assert(seg != NULL);
+
+		seg->nitems = 0;
+		memset(seg->used_items, 0, sizeof(seg->used_items));
+	}
+
+	/* empty every bucket */
+	for (x = 0; x < tb->size; x++)
+		GH_SET_BUCKET_EMPTY(&tb->buckets[x]);
+
+	/* zero the used segment bits */
+	memset(tb->used_segments, 0, sizeof(GH_BITMAP_WORD) * tb->used_segment_words);
+
+	/* and mark the table as having zero members */
+	tb->members = 0;
+
+	/* ensure we start putting any new items in the first segment */
+	tb->first_free_segment = 0;
+}
+
+/*
+ * Grow a hash table to at least 'newsize' buckets.
+ *
+ * Usually this will automatically be called by insertions/deletions, when
+ * necessary. But resizing to the exact input size can be advantageous
+ * performance-wise, when known at some point.
+ */
+GH_SCOPE void
+GH_GROW(GH_TYPE * tb, uint32 newsize)
+{
+	uint32		oldsize = tb->size;
+	uint32		oldnsegments = tb->nsegments;
+	uint32		oldusedsegmentwords = tb->used_segment_words;
+	GH_BUCKET  *oldbuckets = tb->buckets;
+	GH_SEGMENT **oldsegments = tb->segments;
+	GH_BITMAP_WORD *oldusedsegments = tb->used_segments;
+	GH_BUCKET  *newbuckets;
+	uint32		i;
+	uint32		startelem = 0;
+	uint32		copyelem;
+
+	Assert(oldsize == pg_nextpower2_32(oldsize));
+
+	/* compute parameters for new table */
+	GH_COMPUTE_PARAMETERS(tb, newsize);
+
+	tb->buckets = GH_ALLOCATE(sizeof(GH_ELEMENT_TYPE) * tb->size);
+
+	/* Ensure all the buckets are set to empty */
+	for (i = 0; i < tb->size; i++)
+		GH_SET_BUCKET_EMPTY(&tb->buckets[i]);
+
+	newbuckets = tb->buckets;
+
+	/*
+	 * Copy buckets from the old buckets to newbuckets. We theoretically could
+	 * use GH_INSERT here, to avoid code duplication, but that's more general
+	 * than we need. We neither want tb->members increased, nor do we need to
+	 * do deal with deleted elements, nor do we need to compare keys. So a
+	 * special-cased implementation is a lot faster.  Resizing can be time
+	 * consuming and frequent, that's worthwhile to optimize.
+	 *
+	 * To be able to simply move buckets over, we have to start not at the
+	 * first bucket (i.e oldbuckets[0]), but find the first bucket that's
+	 * either empty or is occupied by an entry at its optimal position. Such a
+	 * bucket has to exist in any table with a load factor under 1, as not all
+	 * buckets are occupied, i.e. there always has to be an empty bucket.  By
+	 * starting at such a bucket we can move the entries to the larger table,
+	 * without having to deal with conflicts.
+	 */
+
+	/* search for the first element in the hash that's not wrapped around */
+	for (i = 0; i < oldsize; i++)
+	{
+		GH_BUCKET  *oldbucket = &oldbuckets[i];
+		uint32		hash;
+		uint32		optimal;
+
+		if (!GH_IS_BUCKET_IN_USE(oldbucket))
+		{
+			startelem = i;
+			break;
+		}
+
+		hash = oldbucket->hashvalue;
+		optimal = GH_INITIAL_BUCKET(tb, hash);
+
+		if (optimal == i)
+		{
+			startelem = i;
+			break;
+		}
+	}
+
+	/* and copy all elements in the old table */
+	copyelem = startelem;
+	for (i = 0; i < oldsize; i++)
+	{
+		GH_BUCKET  *oldbucket = &oldbuckets[copyelem];
+
+		if (GH_IS_BUCKET_IN_USE(oldbucket))
+		{
+			uint32		hash;
+			uint32		startelem;
+			uint32		curelem;
+			GH_BUCKET  *newbucket;
+
+			hash = oldbucket->hashvalue;
+			startelem = GH_INITIAL_BUCKET(tb, hash);
+			curelem = startelem;
+
+			/* find empty element to put data into */
+			for (;;)
+			{
+				newbucket = &newbuckets[curelem];
+
+				if (!GH_IS_BUCKET_IN_USE(newbucket))
+					break;
+
+				curelem = GH_NEXT(tb, curelem, startelem);
+			}
+
+			/* copy entry to new slot */
+			memcpy(newbucket, oldbucket, sizeof(GH_BUCKET));
+		}
+
+		/* can't use GH_NEXT here, would use new size */
+		copyelem++;
+		if (copyelem >= oldsize)
+			copyelem = 0;
+	}
+
+	GH_FREE(oldbuckets);
+
+	/*
+	 * Enlarge the segment array so we can store enough segments for the new
+	 * hash table capacity.
+	 */
+	tb->segments = GH_ALLOCATE(sizeof(GH_SEGMENT *) * tb->nsegments);
+	memcpy(tb->segments, oldsegments, sizeof(GH_SEGMENT *) * oldnsegments);
+	/* zero the newly extended part of the array */
+	memset(&tb->segments[oldnsegments], 0, sizeof(GH_SEGMENT *) *
+		   (tb->nsegments - oldnsegments));
+	GH_FREE(oldsegments);
+
+	/*
+	 * The majority of tables will only ever need one bitmap word to store
+	 * used segments, so we only bother to reallocate the used_segments array
+	 * if the number of bitmap words has actually changed.
+	 */
+	if (tb->used_segment_words != oldusedsegmentwords)
+	{
+		tb->used_segments = GH_ALLOCATE(sizeof(GH_BITMAP_WORD) *
+										tb->used_segment_words);
+		memcpy(tb->used_segments, oldusedsegments, sizeof(GH_BITMAP_WORD) *
+			   oldusedsegmentwords);
+		memset(&tb->used_segments[oldusedsegmentwords], 0,
+			   sizeof(GH_BITMAP_WORD) * (tb->used_segment_words -
+										 oldusedsegmentwords));
+
+		GH_FREE(oldusedsegments);
+	}
+}
+
+/*
+ * This is a separate static inline function, so it can be reliably be inlined
+ * into its wrapper functions even if GH_SCOPE is extern.
+ */
+static inline GH_ELEMENT_TYPE *
+GH_INSERT_HASH_INTERNAL(GH_TYPE * tb, GH_KEY_TYPE key, uint32 hash, bool *found)
+{
+	uint32		startelem;
+	uint32		curelem;
+	GH_BUCKET  *buckets;
+	uint32		insertdist;
+
+restart:
+	insertdist = 0;
+
+	/*
+	 * To avoid doing the grow check inside the loop, we do the grow check
+	 * regardless of if the key is present.  This also lets us avoid having to
+	 * re-find our position in the hashtable after resizing.
+	 *
+	 * Note that this also reached when resizing the table due to
+	 * GH_GROW_MAX_DIB / GH_GROW_MAX_MOVE.
+	 */
+	if (unlikely(tb->members >= tb->grow_threshold))
+	{
+		/* this may wrap back to 0 when we're already at GH_MAX_SIZE */
+		GH_GROW(tb, tb->size * 2);
+	}
+
+	/* perform the insert starting the bucket search at optimal location */
+	buckets = tb->buckets;
+	startelem = GH_INITIAL_BUCKET(tb, hash);
+	curelem = startelem;
+	for (;;)
+	{
+		GH_BUCKET  *bucket = &buckets[curelem];
+		GH_ELEMENT_TYPE *entry;
+		uint32		curdist;
+		uint32		curhash;
+		uint32		curoptimal;
+
+		/* any empty bucket can directly be used */
+		if (!GH_IS_BUCKET_IN_USE(bucket))
+		{
+			uint32		index;
+
+			/* and add the new entry */
+			tb->members++;
+
+			entry = GH_GET_NEXT_UNUSED_ENTRY(tb, &index);
+			entry->GH_KEY = key;
+			bucket->hashvalue = hash;
+			GH_SET_BUCKET_IN_USE(bucket, index);
+			*found = false;
+			return entry;
+		}
+
+		curhash = bucket->hashvalue;
+
+		if (curhash == hash)
+		{
+			/*
+			 * The hash value matches so we just need to ensure the key
+			 * matches too.  To do that, we need to lookup the entry in the
+			 * segments using the index stored in the bucket.
+			 */
+			entry = GH_INDEX_TO_ELEMENT(tb, bucket->index);
+
+			/* if we find a match, we're done */
+			if (GH_EQUAL(tb, key, entry->GH_KEY))
+			{
+				Assert(GH_IS_BUCKET_IN_USE(bucket));
+				*found = true;
+				return entry;
+			}
+		}
+
+		/*
+		 * For non-empty, non-matching buckets we have to decide whether to
+		 * skip over or move the colliding entry.  When the colliding
+		 * element's distance to its optimal position is smaller than the
+		 * to-be-inserted entry's, we shift the colliding entry (and its
+		 * followers) one bucket closer to their optimal position.
+		 */
+		curoptimal = GH_INITIAL_BUCKET(tb, curhash);
+		curdist = GH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem);
+
+		if (insertdist > curdist)
+		{
+			GH_ELEMENT_TYPE *entry;
+			GH_BUCKET  *lastbucket = bucket;
+			uint32		emptyelem = curelem;
+			uint32		moveelem;
+			int32		emptydist = 0;
+			uint32		index;
+
+			/* find next empty bucket */
+			for (;;)
+			{
+				GH_BUCKET  *emptybucket;
+
+				emptyelem = GH_NEXT(tb, emptyelem, startelem);
+				emptybucket = &buckets[emptyelem];
+
+				if (!GH_IS_BUCKET_IN_USE(emptybucket))
+				{
+					lastbucket = emptybucket;
+					break;
+				}
+
+				/*
+				 * To avoid negative consequences from overly imbalanced
+				 * hashtables, grow the hashtable if collisions would require
+				 * us to move a lot of entries.  The most likely cause of such
+				 * imbalance is filling a (currently) small table, from a
+				 * currently big one, in hashtable order.  Don't grow if the
+				 * hashtable would be too empty, to prevent quick space
+				 * explosion for some weird edge cases.
+				 */
+				if (unlikely(++emptydist > GH_GROW_MAX_MOVE) &&
+					((double) tb->members / tb->size) >= GH_GROW_MIN_FILLFACTOR)
+				{
+					tb->grow_threshold = 0;
+					goto restart;
+				}
+			}
+
+			/* shift forward, starting at last occupied element */
+
+			/*
+			 * TODO: This could be optimized to be one memcpy in many cases,
+			 * excepting wrapping around at the end of ->data. Hasn't shown up
+			 * in profiles so far though.
+			 */
+			moveelem = emptyelem;
+			while (moveelem != curelem)
+			{
+				GH_BUCKET  *movebucket;
+
+				moveelem = GH_PREV(tb, moveelem, startelem);
+				movebucket = &buckets[moveelem];
+
+				memcpy(lastbucket, movebucket, sizeof(GH_BUCKET));
+				lastbucket = movebucket;
+			}
+
+			/* and add the new entry */
+			tb->members++;
+
+			entry = GH_GET_NEXT_UNUSED_ENTRY(tb, &index);
+			entry->GH_KEY = key;
+			bucket->hashvalue = hash;
+			GH_SET_BUCKET_IN_USE(bucket, index);
+			*found = false;
+			return entry;
+		}
+
+		curelem = GH_NEXT(tb, curelem, startelem);
+		insertdist++;
+
+		/*
+		 * To avoid negative consequences from overly imbalanced hashtables,
+		 * grow the hashtable if collisions lead to large runs. The most
+		 * likely cause of such imbalance is filling a (currently) small
+		 * table, from a currently big one, in hashtable order.  Don't grow if
+		 * the hashtable would be too empty, to prevent quick space explosion
+		 * for some weird edge cases.
+		 */
+		if (unlikely(insertdist > GH_GROW_MAX_DIB) &&
+			((double) tb->members / tb->size) >= GH_GROW_MIN_FILLFACTOR)
+		{
+			tb->grow_threshold = 0;
+			goto restart;
+		}
+	}
+}
+
+/*
+ * Insert the key into the hashtable, set *found to true if the key already
+ * exists, false otherwise. Returns the hashtable entry in either case.
+ */
+GH_SCOPE	GH_ELEMENT_TYPE *
+GH_INSERT(GH_TYPE * tb, GH_KEY_TYPE key, bool *found)
+{
+	uint32		hash = GH_HASH_KEY(tb, key);
+
+	return GH_INSERT_HASH_INTERNAL(tb, key, hash, found);
+}
+
+/*
+ * Insert the key into the hashtable using an already-calculated hash. Set
+ * *found to true if the key already exists, false otherwise. Returns the
+ * hashtable entry in either case.
+ */
+GH_SCOPE	GH_ELEMENT_TYPE *
+GH_INSERT_HASH(GH_TYPE * tb, GH_KEY_TYPE key, uint32 hash, bool *found)
+{
+	return GH_INSERT_HASH_INTERNAL(tb, key, hash, found);
+}
+
+/*
+ * This is a separate static inline function, so it can be reliably be inlined
+ * into its wrapper functions even if GH_SCOPE is extern.
+ */
+static inline GH_ELEMENT_TYPE *
+GH_LOOKUP_HASH_INTERNAL(GH_TYPE * tb, GH_KEY_TYPE key, uint32 hash)
+{
+	const uint32 startelem = GH_INITIAL_BUCKET(tb, hash);
+	uint32		curelem = startelem;
+
+	for (;;)
+	{
+		GH_BUCKET  *bucket = &tb->buckets[curelem];
+
+		if (!GH_IS_BUCKET_IN_USE(bucket))
+			return NULL;
+
+		if (bucket->hashvalue == hash)
+		{
+			GH_ELEMENT_TYPE *entry;
+
+			/*
+			 * The hash value matches so we just need to ensure the key
+			 * matches too.  To do that, we need to lookup the entry in the
+			 * segments using the index stored in the bucket.
+			 */
+			entry = GH_INDEX_TO_ELEMENT(tb, bucket->index);
+
+			/* if we find a match, we're done */
+			if (GH_EQUAL(tb, key, entry->GH_KEY))
+				return entry;
+		}
+
+		/*
+		 * TODO: we could stop search based on distance. If the current
+		 * buckets's distance-from-optimal is smaller than what we've skipped
+		 * already, the entry doesn't exist.
+		 */
+
+		curelem = GH_NEXT(tb, curelem, startelem);
+	}
+}
+
+/*
+ * Lookup an entry in the hash table.  Returns NULL if key not present.
+ */
+GH_SCOPE	GH_ELEMENT_TYPE *
+GH_LOOKUP(GH_TYPE * tb, GH_KEY_TYPE key)
+{
+	uint32		hash = GH_HASH_KEY(tb, key);
+
+	return GH_LOOKUP_HASH_INTERNAL(tb, key, hash);
+}
+
+/*
+ * Lookup an entry in the hash table using an already-calculated hash.
+ *
+ * Returns NULL if key not present.
+ */
+GH_SCOPE	GH_ELEMENT_TYPE *
+GH_LOOKUP_HASH(GH_TYPE * tb, GH_KEY_TYPE key, uint32 hash)
+{
+	return GH_LOOKUP_HASH_INTERNAL(tb, key, hash);
+}
+
+/*
+ * Delete an entry from hash table by key.  Returns whether to-be-deleted key
+ * was present.
+ */
+GH_SCOPE bool
+GH_DELETE(GH_TYPE * tb, GH_KEY_TYPE key)
+{
+	uint32		hash = GH_HASH_KEY(tb, key);
+	uint32		startelem = GH_INITIAL_BUCKET(tb, hash);
+	uint32		curelem = startelem;
+
+	for (;;)
+	{
+		GH_BUCKET  *bucket = &tb->buckets[curelem];
+
+		if (!GH_IS_BUCKET_IN_USE(bucket))
+			return false;
+
+		if (bucket->hashvalue == hash)
+		{
+			GH_ELEMENT_TYPE *entry;
+
+			entry = GH_INDEX_TO_ELEMENT(tb, bucket->index);
+
+			if (GH_EQUAL(tb, key, entry->GH_KEY))
+			{
+				GH_BUCKET  *lastbucket = bucket;
+
+				/* mark the entry as unused */
+				GH_REMOVE_ENTRY(tb, bucket->index);
+				/* and mark the bucket unused */
+				GH_SET_BUCKET_EMPTY(bucket);
+
+				tb->members--;
+
+				/*
+				 * Backward shift following buckets till either an empty
+				 * bucket or a bucket at its optimal position is encountered.
+				 *
+				 * While that sounds expensive, the average chain length is
+				 * short, and deletions would otherwise require tombstones.
+				 */
+				for (;;)
+				{
+					GH_BUCKET  *curbucket;
+					uint32		curhash;
+					uint32		curoptimal;
+
+					curelem = GH_NEXT(tb, curelem, startelem);
+					curbucket = &tb->buckets[curelem];
+
+					if (!GH_IS_BUCKET_IN_USE(curbucket))
+						break;
+
+					curhash = curbucket->hashvalue;
+					curoptimal = GH_INITIAL_BUCKET(tb, curhash);
+
+					/* current is at optimal position, done */
+					if (curoptimal == curelem)
+					{
+						GH_SET_BUCKET_EMPTY(lastbucket);
+						break;
+					}
+
+					/* shift */
+					memcpy(lastbucket, curbucket, sizeof(GH_BUCKET));
+					GH_SET_BUCKET_EMPTY(curbucket);
+
+					lastbucket = curbucket;
+				}
+
+				return true;
+			}
+		}
+		/* TODO: return false; if the distance is too big */
+
+		curelem = GH_NEXT(tb, curelem, startelem);
+	}
+}
+
+/*
+ * Initialize iterator.
+ */
+GH_SCOPE void
+GH_START_ITERATE(GH_TYPE * tb, GH_ITERATOR * iter)
+{
+	iter->cursegidx = -1;
+	iter->curitemidx = -1;
+	iter->found_members = 0;
+	iter->total_members = tb->members;
+}
+
+/*
+ * Iterate over all entries in the hashtable. Return the next occupied entry,
+ * or NULL if there are no more entries.
+ *
+ * During iteration the only current entry in the hash table and any entry
+ * which was previously visited in the loop may be deleted.  Deletion of items
+ * not yet visited is prohibited as are insertions of new entries.
+ */
+GH_SCOPE	GH_ELEMENT_TYPE *
+GH_ITERATE(GH_TYPE * tb, GH_ITERATOR * iter)
+{
+	/*
+	 * Bail if we've already visited all members.  This check allows us to
+	 * exit quickly in cases where the table is large but it only contains a
+	 * small number of records.  This also means that inserts into the table
+	 * are not possible during iteration.  If that is done then we may not
+	 * visit all items in the table.  Rather than ever removing this check to
+	 * allow table insertions during iteration, we should add another iterator
+	 * where insertions are safe.
+	 */
+	if (iter->found_members == iter->total_members)
+		return NULL;
+
+	for (;;)
+	{
+		GH_SEGMENT *seg;
+
+		/* need a new segment? */
+		if (iter->curitemidx == -1)
+		{
+			iter->cursegidx = GH_NEXT_ONEBIT(tb->used_segments,
+											 tb->used_segment_words,
+											 iter->cursegidx);
+
+			/* no more segments with items? We're done */
+			if (iter->cursegidx == -1)
+				return NULL;
+		}
+
+		seg = tb->segments[iter->cursegidx];
+
+		/* if the segment has items then it certainly shouldn't be NULL */
+		Assert(seg != NULL);
+		/* advance to the next used item in this segment */
+		iter->curitemidx = GH_NEXT_ONEBIT(seg->used_items, GH_BITMAP_WORDS,
+										  iter->curitemidx);
+		if (iter->curitemidx >= 0)
+		{
+			iter->found_members++;
+			return &seg->items[iter->curitemidx];
+		}
+
+		/*
+		 * GH_NEXT_ONEBIT returns -1 when there are no more bits.  We just
+		 * loop again to fetch the next segment.
+		 */
+	}
+}
+
+#endif							/* GH_DEFINE */
+
+/* undefine external parameters, so next hash table can be defined */
+#undef GH_PREFIX
+#undef GH_KEY_TYPE
+#undef GH_KEY
+#undef GH_ELEMENT_TYPE
+#undef GH_HASH_KEY
+#undef GH_SCOPE
+#undef GH_DECLARE
+#undef GH_DEFINE
+#undef GH_EQUAL
+#undef GH_ALLOCATE
+#undef GH_ALLOCATE_ZERO
+#undef GH_FREE
+
+/* undefine locally declared macros */
+#undef GH_MAKE_PREFIX
+#undef GH_MAKE_NAME
+#undef GH_MAKE_NAME_
+#undef GH_ITEMS_PER_SEGMENT
+#undef GH_UNUSED_BUCKET_INDEX
+#undef GH_INDEX_SEGMENT
+#undef GH_INDEX_ITEM
+#undef GH_BITS_PER_WORD
+#undef GH_BITMAP_WORD
+#undef GH_RIGHTMOST_ONE_POS
+#undef GH_BITMAP_WORDS
+#undef GH_WORDNUM
+#undef GH_BITNUM
+#undef GH_RAW_ALLOCATOR
+#undef GH_MAX_SIZE
+#undef GH_FILLFACTOR
+#undef GH_MAX_FILLFACTOR
+#undef GH_GROW_MAX_DIB
+#undef GH_GROW_MAX_MOVE
+#undef GH_GROW_MIN_FILLFACTOR
+
+/* types */
+#undef GH_TYPE
+#undef GH_BUCKET
+#undef GH_SEGMENT
+#undef GH_ITERATOR
+
+/* external function names */
+#undef GH_CREATE
+#undef GH_DESTROY
+#undef GH_RESET
+#undef GH_INSERT
+#undef GH_INSERT_HASH
+#undef GH_DELETE
+#undef GH_LOOKUP
+#undef GH_LOOKUP_HASH
+#undef GH_GROW
+#undef GH_START_ITERATE
+#undef GH_ITERATE
+
+/* internal function names */
+#undef GH_NEXT_ONEBIT
+#undef GH_NEXT_ZEROBIT
+#undef GH_INDEX_TO_ELEMENT
+#undef GH_MARK_SEGMENT_ITEM_USED
+#undef GH_MARK_SEGMENT_ITEM_UNUSED
+#undef GH_GET_NEXT_UNUSED_ENTRY
+#undef GH_REMOVE_ENTRY
+#undef GH_SET_BUCKET_IN_USE
+#undef GH_SET_BUCKET_EMPTY
+#undef GH_IS_BUCKET_IN_USE
+#undef GH_COMPUTE_PARAMETERS
+#undef GH_NEXT
+#undef GH_PREV
+#undef GH_DISTANCE_FROM_OPTIMAL
+#undef GH_INITIAL_BUCKET
+#undef GH_INSERT_HASH_INTERNAL
+#undef GH_LOOKUP_HASH_INTERNAL
diff --git a/src/include/storage/lock.h b/src/include/storage/lock.h
index 9b2a421c32..a268879b1c 100644
--- a/src/include/storage/lock.h
+++ b/src/include/storage/lock.h
@@ -561,7 +561,7 @@ extern void LockReleaseCurrentOwner(LOCALLOCK **locallocks, int nlocks);
 extern void LockReassignCurrentOwner(LOCALLOCK **locallocks, int nlocks);
 extern bool LockHeldByMe(const LOCKTAG *locktag, LOCKMODE lockmode);
 #ifdef USE_ASSERT_CHECKING
-extern HTAB *GetLockMethodLocalHash(void);
+extern LOCALLOCK **GetLockMethodLocalLocks(uint32 *size);
 #endif
 extern bool LockHasWaiters(const LOCKTAG *locktag,
 						   LOCKMODE lockmode, bool sessionLock);
-- 
2.27.0

From d3689d5e3bdd1b9aac57a104540ccfabc4f33997 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 22 Jun 2021 00:31:53 +1200
Subject: [PATCH v1 2/2] Use generichash.h hashtables in SMgr

The hash table lookups done in SMgr can quite often be a bottleneck during
crash recovery.  Traditionally these use dynahash. Here we swap dynahash
out and use generichash instead.  This improves lookup performance.
---
 src/backend/storage/smgr/smgr.c | 82 +++++++++++++++++++++++----------
 1 file changed, 58 insertions(+), 24 deletions(-)

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 4dc24649df..77dd402479 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -18,14 +18,30 @@
 #include "postgres.h"
 
 #include "access/xlog.h"
+#include "common/hashfn.h"
 #include "lib/ilist.h"
 #include "storage/bufmgr.h"
 #include "storage/ipc.h"
 #include "storage/md.h"
 #include "storage/smgr.h"
-#include "utils/hsearch.h"
 #include "utils/inval.h"
-
+#include "utils/memutils.h"
+
+static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
+
+#define GH_PREFIX		smgrtable
+#define GH_ELEMENT_TYPE	SMgrRelationData
+#define GH_KEY_TYPE		RelFileNodeBackend
+#define GH_KEY			smgr_rnode
+#define GH_HASH_KEY(tb, key)	relfilenodebackend_hash(&key)
+#define GH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(RelFileNodeBackend)) == 0)
+#define GH_ALLOCATE(b)			MemoryContextAllocExtended(TopMemoryContext, b, MCXT_ALLOC_HUGE)
+#define GH_ALLOCATE_ZERO(b)		MemoryContextAllocExtended(TopMemoryContext, b, MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO)
+#define GH_FREE(p)				pfree(p)
+#define GH_SCOPE		static inline
+#define GH_DECLARE
+#define GH_DEFINE
+#include "lib/generichash.h"
 
 /*
  * This struct of function pointers defines the API between smgr.c and
@@ -91,13 +107,43 @@ static const int NSmgr = lengthof(smgrsw);
  * Each backend has a hashtable that stores all extant SMgrRelation objects.
  * In addition, "unowned" SMgrRelation objects are chained together in a list.
  */
-static HTAB *SMgrRelationHash = NULL;
+static smgrtable_hash *SMgrRelationHash = NULL;
 
 static dlist_head unowned_relns;
 
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
 
+/*
+ * relfilenodebackend_hash
+ *		Custom rolled hash function for simplehash table.
+ *
+ * smgropen() is often a bottleneck in CPU bound workloads during crash
+ * recovery.  We make use of this custom hash function rather than using
+ * hash_bytes as it gives us a little bit more performance.
+ *
+ * XXX What if sizeof(Oid) is not 4?
+ */
+static inline uint32
+relfilenodebackend_hash(RelFileNodeBackend *rnode)
+{
+	uint32		hashkey;
+
+	hashkey = murmurhash32((uint32) rnode->node.spcNode);
+
+	/* rotate hashkey left 1 bit at each step */
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
+
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
+
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->backend);
+
+	return hashkey;
+}
+
 
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
@@ -149,29 +195,22 @@ smgropen(RelFileNode rnode, BackendId backend)
 	SMgrRelation reln;
 	bool		found;
 
-	if (SMgrRelationHash == NULL)
+	if (unlikely(SMgrRelationHash == NULL))
 	{
 		/* First time through: initialize the hash table */
-		HASHCTL		ctl;
-
-		ctl.keysize = sizeof(RelFileNodeBackend);
-		ctl.entrysize = sizeof(SMgrRelationData);
-		SMgrRelationHash = hash_create("smgr relation table", 400,
-									   &ctl, HASH_ELEM | HASH_BLOBS);
+		SMgrRelationHash = smgrtable_create(400);
 		dlist_init(&unowned_relns);
 	}
 
 	/* Look up or create an entry */
 	brnode.node = rnode;
 	brnode.backend = backend;
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &brnode,
-									  HASH_ENTER, &found);
+	reln = smgrtable_insert(SMgrRelationHash, brnode, &found);
 
 	/* Initialize it if not present before */
 	if (!found)
 	{
-		/* hash_search already filled in the lookup key */
+		/* smgrtable_insert already filled in the lookup key */
 		reln->smgr_owner = NULL;
 		reln->smgr_targblock = InvalidBlockNumber;
 		for (int i = 0; i <= MAX_FORKNUM; ++i)
@@ -266,9 +305,7 @@ smgrclose(SMgrRelation reln)
 	if (!owner)
 		dlist_delete(&reln->node);
 
-	if (hash_search(SMgrRelationHash,
-					(void *) &(reln->smgr_rnode),
-					HASH_REMOVE, NULL) == NULL)
+	if (!smgrtable_delete(SMgrRelationHash, reln->smgr_rnode))
 		elog(ERROR, "SMgrRelation hashtable corrupted");
 
 	/*
@@ -285,16 +322,16 @@ smgrclose(SMgrRelation reln)
 void
 smgrcloseall(void)
 {
-	HASH_SEQ_STATUS status;
+	smgrtable_iterator iterator;
 	SMgrRelation reln;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
 
-	hash_seq_init(&status, SMgrRelationHash);
+	smgrtable_start_iterate(SMgrRelationHash, &iterator);
 
-	while ((reln = (SMgrRelation) hash_seq_search(&status)) != NULL)
+	while ((reln = smgrtable_iterate(SMgrRelationHash, &iterator)) != NULL)
 		smgrclose(reln);
 }
 
@@ -314,10 +351,7 @@ smgrclosenode(RelFileNodeBackend rnode)
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
-
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &rnode,
-									  HASH_FIND, NULL);
+	reln = smgrtable_lookup(SMgrRelationHash, rnode);
 	if (reln != NULL)
 		smgrclose(reln);
 }
-- 
2.27.0

From 50268dcf6484af095fb7485758de1b44e9375a51 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 3 Aug 2021 16:10:29 +1200
Subject: [PATCH v2] Use densehash.h hashtables in SMgr

The hash table lookups done in SMgr can quite often be a bottleneck during
crash recovery.  Traditionally these use dynahash. Here we swap dynahash
out and use densehash instead.  This improves lookup performance.
---
 src/backend/storage/smgr/smgr.c |   82 +-
 src/include/lib/densehash.h     | 1436 +++++++++++++++++++++++++++++++
 2 files changed, 1496 insertions(+), 22 deletions(-)
 create mode 100644 src/include/lib/densehash.h

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 0fcef4994b..3fa9c21c4b 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -18,6 +18,7 @@
 #include "postgres.h"
 
 #include "access/xlogutils.h"
+#include "common/hashfn.h"
 #include "lib/ilist.h"
 #include "storage/bufmgr.h"
 #include "storage/ipc.h"
@@ -25,6 +26,25 @@
 #include "storage/smgr.h"
 #include "utils/hsearch.h"
 #include "utils/inval.h"
+#include "utils/memutils.h"
+
+static inline uint32 relfilenodebackend_hash(RelFileNodeBackend *rnode);
+
+#define DH_PREFIX				smgrtable
+#define DH_ELEMENT_TYPE			SMgrRelationData
+#define DH_KEY_TYPE				RelFileNodeBackend
+#define DH_KEY					smgr_rnode
+#define DH_HASH_KEY(tb, key)	relfilenodebackend_hash(&key)
+#define DH_EQUAL(tb, a, b)		(memcmp(&a, &b, sizeof(RelFileNodeBackend)) == 0)
+#define DH_SCOPE				static inline
+#define DH_STORE_HASH
+#define DH_GET_HASH(tb, a)		a->hash
+#define DH_ALLOCATE(b)			MemoryContextAlloc(TopMemoryContext, (b))
+#define DH_ALLOCATE_ZERO(b)		MemoryContextAllocZero(TopMemoryContext, (b))
+#define DH_FREE(p)				pfree(p)
+#define DH_DEFINE
+#define DH_DECLARE
+#include "lib/densehash.h"
 
 
 /*
@@ -91,13 +111,43 @@ static const int NSmgr = lengthof(smgrsw);
  * Each backend has a hashtable that stores all extant SMgrRelation objects.
  * In addition, "unowned" SMgrRelation objects are chained together in a list.
  */
-static HTAB *SMgrRelationHash = NULL;
+static smgrtable_hash *SMgrRelationHash = NULL;
 
 static dlist_head unowned_relns;
 
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
 
+/*
+ * relfilenodebackend_hash
+ *		Custom rolled hash function for simplehash table.
+ *
+ * smgropen() is often a bottleneck in CPU bound workloads during crash
+ * recovery.  We make use of this custom hash function rather than using
+ * hash_bytes as it gives us a little bit more performance.
+ *
+ * XXX What if sizeof(Oid) is not 4?
+ */
+static inline uint32
+relfilenodebackend_hash(RelFileNodeBackend *rnode)
+{
+	uint32		hashkey;
+
+	hashkey = murmurhash32((uint32) rnode->node.spcNode);
+
+	/* rotate hashkey left 1 bit at each step */
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->node.dbNode);
+
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->node.relNode);
+
+	hashkey = pg_rotate_right32(hashkey, 31);
+	hashkey ^= murmurhash32((uint32) rnode->backend);
+
+	return hashkey;
+}
+
 
 /*
  *	smgrinit(), smgrshutdown() -- Initialize or shut down storage
@@ -149,29 +199,22 @@ smgropen(RelFileNode rnode, BackendId backend)
 	SMgrRelation reln;
 	bool		found;
 
-	if (SMgrRelationHash == NULL)
+	if (unlikely(SMgrRelationHash == NULL))
 	{
 		/* First time through: initialize the hash table */
-		HASHCTL		ctl;
-
-		ctl.keysize = sizeof(RelFileNodeBackend);
-		ctl.entrysize = sizeof(SMgrRelationData);
-		SMgrRelationHash = hash_create("smgr relation table", 400,
-									   &ctl, HASH_ELEM | HASH_BLOBS);
+		SMgrRelationHash = smgrtable_create(400);
 		dlist_init(&unowned_relns);
 	}
 
 	/* Look up or create an entry */
 	brnode.node = rnode;
 	brnode.backend = backend;
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &brnode,
-									  HASH_ENTER, &found);
+	reln = smgrtable_insert(SMgrRelationHash, brnode, &found);
 
 	/* Initialize it if not present before */
 	if (!found)
 	{
-		/* hash_search already filled in the lookup key */
+		/* smgrtable_insert already filled in the lookup key */
 		reln->smgr_owner = NULL;
 		reln->smgr_targblock = InvalidBlockNumber;
 		for (int i = 0; i <= MAX_FORKNUM; ++i)
@@ -266,9 +309,7 @@ smgrclose(SMgrRelation reln)
 	if (!owner)
 		dlist_delete(&reln->node);
 
-	if (hash_search(SMgrRelationHash,
-					(void *) &(reln->smgr_rnode),
-					HASH_REMOVE, NULL) == NULL)
+	if (!smgrtable_delete(SMgrRelationHash, reln->smgr_rnode))
 		elog(ERROR, "SMgrRelation hashtable corrupted");
 
 	/*
@@ -285,16 +326,16 @@ smgrclose(SMgrRelation reln)
 void
 smgrcloseall(void)
 {
-	HASH_SEQ_STATUS status;
+	smgrtable_iterator iterator;
 	SMgrRelation reln;
 
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
 
-	hash_seq_init(&status, SMgrRelationHash);
+	smgrtable_start_iterate(SMgrRelationHash, &iterator);
 
-	while ((reln = (SMgrRelation) hash_seq_search(&status)) != NULL)
+	while ((reln = smgrtable_iterate(SMgrRelationHash, &iterator)) != NULL)
 		smgrclose(reln);
 }
 
@@ -314,10 +355,7 @@ smgrclosenode(RelFileNodeBackend rnode)
 	/* Nothing to do if hashtable not set up */
 	if (SMgrRelationHash == NULL)
 		return;
-
-	reln = (SMgrRelation) hash_search(SMgrRelationHash,
-									  (void *) &rnode,
-									  HASH_FIND, NULL);
+	reln = smgrtable_lookup(SMgrRelationHash, rnode);
 	if (reln != NULL)
 		smgrclose(reln);
 }
diff --git a/src/include/lib/densehash.h b/src/include/lib/densehash.h
new file mode 100644
index 0000000000..26fab94479
--- /dev/null
+++ b/src/include/lib/densehash.h
@@ -0,0 +1,1436 @@
+/*
+ * densehash.h
+ *
+ *	  A hashtable implementation which can be included into .c files to
+ *	  provide a fast hash table implementation specific to the given type.
+ *
+ *	  DH_ELEMENT_TYPE defines the data type that the hashtable stores.  These
+ *	  are allocated DH_ITEMS_PER_SEGMENT at a time and stored inside a
+ *	  DH_SEGMENT.  Each DH_SEGMENT is allocated on demand only when there are
+ *	  no free slots to store another DH_ELEMENT_TYPE in an existing segment.
+ *	  After items are removed from the hash table, the next inserted item's
+ *	  data will be stored in the earliest free item in the earliest segment
+ *	  with a free slot.  This helps keep the actual data compact, or "dense"
+ *	  even when the bucket array has become large.
+ *
+ *	  The bucket array is an array of DH_BUCKET and is dynamically allocated
+ *	  and may grow as more items are added to the table.  The DH_BUCKET type
+ *	  is very narrow and stores just 2 uint32 values.  One of these is the
+ *	  hash value and the other is the index into the segments which are used
+ *	  to directly look up the stored DH_ELEMENT_TYPE type.
+ *
+ *	  During inserts, hash table collisions are dealt with using linear
+ *	  probing, this means that instead of doing something like chaining with a
+ *	  linked list, we use the first free bucket which comes after the optimal
+ *	  bucket.  This is much more CPU cache efficient than traversing a linked
+ *	  list.  When we're unable to use the most optimal bucket, we may also
+ *	  move the contents of subsequent buckets around so that we keep items as
+ *	  close to their most optimal position as possible.  This prevents
+ *	  excessively long linear probes during lookups.
+ *
+ *	  During hash table deletes, we must attempt to move the contents of
+ *	  buckets that are not in their optimal position up to either their
+ *	  optimal position, or as close as we can get to it.  During lookups, this
+ *	  means that we can stop searching for a non-existing item as soon as we
+ *	  find an empty bucket.
+ *
+ *	  Empty buckets are denoted by their 'index' field being set to
+ *	  DH_UNUSED_BUCKET_INDEX.  This is done rather than adding a special field
+ *	  so that we can keep the DH_BUCKET type as narrow as possible.
+ *	  Conveniently sizeof(DH_BUCKET) is 8, which allows 8 of these to fit on a
+ *	  single 64-byte cache line. It's important to keep this type as narrow as
+ *	  possible so that we can perform hash lookups by hitting as few
+ *	  cache lines as possible.
+ *
+ *	  The implementation here is similar to simplehash.h but has the following
+ *	  benefits:
+ *
+ *	  - Pointers to elements are stable and are not moved around like they are
+ *		in simplehash.h
+ *	  - Sequential scans of the hash table remain very fast even when the
+ *		table is sparsely populated.
+ *	  - Both simplehash.h and densehash.h may move items around during inserts
+ *		and deletes.  If DH_ELEMENT_TYPE is large, since simplehash.h stores
+ *		the data in the hash bucket, these operations may become expensive in
+ *		simplehash.h.  In densehash.h these remain fairly cheap as the bucket
+ *		is always 8 bytes wide due to the hash entry being stored in the
+ *		DH_SEGMENT.
+ *
+ * If none of the above points are important for the given use case then,
+ * please consider using simplehash.h instead.
+ *
+ *
+ * Portions Copyright (c) 2021, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *		src/include/lib/densehash.h
+ *
+ */
+
+#include "port/pg_bitutils.h"
+
+/* helpers */
+#define DH_MAKE_PREFIX(a) CppConcat(a,_)
+#define DH_MAKE_NAME(name) DH_MAKE_NAME_(DH_MAKE_PREFIX(DH_PREFIX),name)
+#define DH_MAKE_NAME_(a,b) CppConcat(a,b)
+
+/* type declarations */
+#define DH_TYPE DH_MAKE_NAME(hash)
+#define DH_BUCKET DH_MAKE_NAME(bucket)
+#define DH_SEGMENT DH_MAKE_NAME(segment)
+#define DH_ITERATOR DH_MAKE_NAME(iterator)
+
+/* function declarations */
+#define DH_CREATE DH_MAKE_NAME(create)
+#define DH_DESTROY DH_MAKE_NAME(destroy)
+#define DH_RESET DH_MAKE_NAME(reset)
+#define DH_INSERT DH_MAKE_NAME(insert)
+#define DH_INSERT_HASH DH_MAKE_NAME(insert_hash)
+#define DH_DELETE DH_MAKE_NAME(delete)
+#define DH_LOOKUP DH_MAKE_NAME(lookup)
+#define DH_LOOKUP_HASH DH_MAKE_NAME(lookup_hash)
+#define DH_GROW DH_MAKE_NAME(grow)
+#define DH_START_ITERATE DH_MAKE_NAME(start_iterate)
+#define DH_ITERATE DH_MAKE_NAME(iterate)
+
+/* internal helper functions (no externally visible prototypes) */
+#define DH_NEXT_ONEBIT DH_MAKE_NAME(next_onebit)
+#define DH_NEXT_ZEROBIT DH_MAKE_NAME(next_zerobit)
+#define DH_INDEX_TO_ELEMENT DH_MAKE_NAME(index_to_element)
+#define DH_MARK_SEGMENT_ITEM_USED DH_MAKE_NAME(mark_segment_item_used)
+#define DH_MARK_SEGMENT_ITEM_UNUSED DH_MAKE_NAME(mark_segment_item_unused)
+#define DH_GET_NEXT_UNUSED_ENTRY DH_MAKE_NAME(get_next_unused_entry)
+#define DH_REMOVE_ENTRY DH_MAKE_NAME(remove_entry)
+#define DH_SET_BUCKET_IN_USE DH_MAKE_NAME(set_bucket_in_use)
+#define DH_SET_BUCKET_EMPTY DH_MAKE_NAME(set_bucket_empty)
+#define DH_IS_BUCKET_IN_USE DH_MAKE_NAME(is_bucket_in_use)
+#define DH_COMPUTE_PARAMETERS DH_MAKE_NAME(compute_parameters)
+#define DH_NEXT DH_MAKE_NAME(next)
+#define DH_PREV DH_MAKE_NAME(prev)
+#define DH_DISTANCE_FROM_OPTIMAL DH_MAKE_NAME(distance)
+#define DH_INITIAL_BUCKET DH_MAKE_NAME(initial_bucket)
+#define DH_INSERT_HASH_INTERNAL DH_MAKE_NAME(insert_hash_internal)
+#define DH_LOOKUP_HASH_INTERNAL DH_MAKE_NAME(lookup_hash_internal)
+
+/*
+ * When allocating memory to store instances of DH_ELEMENT_TYPE, how many
+ * should we allocate at once?  This must be a power of 2 and at least
+ * DH_BITS_PER_WORD.
+ */
+#ifndef DH_ITEMS_PER_SEGMENT
+#define DH_ITEMS_PER_SEGMENT	256
+#endif
+
+/* A special index to set DH_BUCKET->index to when it's not in use */
+#define DH_UNUSED_BUCKET_INDEX	PG_UINT32_MAX
+
+/*
+ * Macros for translating a bucket's index into the segment index and another
+ * to determine the item number within the segment.
+ */
+#define DH_INDEX_SEGMENT(i)	(i) / DH_ITEMS_PER_SEGMENT
+#define DH_INDEX_ITEM(i)	(i) % DH_ITEMS_PER_SEGMENT
+
+ /*
+  * How many elements do we need in the bitmap array to store a bit for each
+  * of DH_ITEMS_PER_SEGMENT.  Keep the word size native to the processor.
+  */
+#if SIZEOF_VOID_P >= 8
+
+#define DH_BITS_PER_WORD		64
+#define DH_BITMAP_WORD			uint64
+#define DH_RIGHTMOST_ONE_POS(x) pg_rightmost_one_pos64(x)
+
+#else
+
+#define DH_BITS_PER_WORD		32
+#define DH_BITMAP_WORD			uint32
+#define DH_RIGHTMOST_ONE_POS(x) pg_rightmost_one_pos32(x)
+
+#endif
+
+/* Sanity check on DH_ITEMS_PER_SEGMENT setting */
+#if DH_ITEMS_PER_SEGMENT < DH_BITS_PER_WORD
+#error "DH_ITEMS_PER_SEGMENT must be >= than DH_BITS_PER_WORD"
+#endif
+
+/* Ensure DH_ITEMS_PER_SEGMENT is a power of 2 */
+#if DH_ITEMS_PER_SEGMENT & (DH_ITEMS_PER_SEGMENT - 1) != 0
+#error "DH_ITEMS_PER_SEGMENT must be a power of 2"
+#endif
+
+#define DH_BITMAP_WORDS			(DH_ITEMS_PER_SEGMENT / DH_BITS_PER_WORD)
+#define DH_WORDNUM(x)			((x) / DH_BITS_PER_WORD)
+#define DH_BITNUM(x)			((x) % DH_BITS_PER_WORD)
+
+/* generate forward declarations necessary to use the hash table */
+#ifdef DH_DECLARE
+
+typedef struct DH_BUCKET
+{
+	uint32		hashvalue;		/* Hash value for this bucket */
+	uint32		index;			/* Index to the actual data */
+}			DH_BUCKET;
+
+typedef struct DH_SEGMENT
+{
+	uint32		nitems;			/* Number of items stored */
+	DH_BITMAP_WORD used_items[DH_BITMAP_WORDS]; /* A 1-bit for each used item
+												 * in the items array */
+	DH_ELEMENT_TYPE items[DH_ITEMS_PER_SEGMENT];	/* the actual data */
+}			DH_SEGMENT;
+
+/* type definitions */
+
+/*
+ * DH_TYPE
+ *		Hash table metadata type
+ */
+typedef struct DH_TYPE
+{
+	/*
+	 * Size of bucket array.  Note that the maximum number of elements is
+	 * lower (DH_MAX_FILLFACTOR)
+	 */
+	uint32		size;
+
+	/* mask for bucket and size calculations, based on size */
+	uint32		sizemask;
+
+	/* the number of elements stored */
+	uint32		members;
+
+	/* boundary after which to grow hashtable */
+	uint32		grow_threshold;
+
+	/* how many elements are there in the segments array */
+	uint32		nsegments;
+
+	/* the number of elements in the used_segments array */
+	uint32		used_segment_words;
+
+	/*
+	 * The first segment we should search in for an empty slot.  This will be
+	 * the first segment that DH_GET_NEXT_UNUSED_ENTRY will search in when
+	 * looking for an unused entry.  We'll increase the value of this when we
+	 * fill a segment and we'll lower it down when we delete an item from a
+	 * segment lower than this value.
+	 */
+	uint32		first_free_segment;
+
+	/* dynamically allocated array of hash buckets */
+	DH_BUCKET  *buckets;
+
+	/* an array of segment pointers to store data */
+	DH_SEGMENT **segments;
+
+	/*
+	 * A bitmap of non-empty segments.  A 1-bit denotes that the corresponding
+	 * segment is non-empty.
+	 */
+	DH_BITMAP_WORD *used_segments;
+
+#ifdef DH_HAVE_PRIVATE_DATA
+	/* user defined data, useful for callbacks */
+	void	   *private_data;
+#endif
+}			DH_TYPE;
+
+/*
+ * DH_ITERATOR
+ *		Used when looping over the contents of the hash table.
+ */
+typedef struct DH_ITERATOR
+{
+	int32		cursegidx;		/* current segment. -1 means not started */
+	int32		curitemidx;		/* current item within cursegidx, -1 means not
+								 * started */
+	uint32		found_members;	/* number of items visitied so far in the loop */
+	uint32		total_members;	/* number of items that existed at the start
+								 * iteration. */
+}			DH_ITERATOR;
+
+/* externally visible function prototypes */
+
+#ifdef DH_HAVE_PRIVATE_DATA
+/* <prefix>_hash <prefix>_create(uint32 nbuckets, void *private_data) */
+DH_SCOPE	DH_TYPE *DH_CREATE(uint32 nbuckets, void *private_data);
+#else
+/* <prefix>_hash <prefix>_create(uint32 nbuckets) */
+DH_SCOPE	DH_TYPE *DH_CREATE(uint32 nbuckets);
+#endif
+
+/* void <prefix>_destroy(<prefix>_hash *tb) */
+DH_SCOPE void DH_DESTROY(DH_TYPE * tb);
+
+/* void <prefix>_reset(<prefix>_hash *tb) */
+DH_SCOPE void DH_RESET(DH_TYPE * tb);
+
+/* void <prefix>_grow(<prefix>_hash *tb) */
+DH_SCOPE void DH_GROW(DH_TYPE * tb, uint32 newsize);
+
+/* <element> *<prefix>_insert(<prefix>_hash *tb, <key> key, bool *found) */
+DH_SCOPE	DH_ELEMENT_TYPE *DH_INSERT(DH_TYPE * tb, DH_KEY_TYPE key,
+									   bool *found);
+
+/*
+ * <element> *<prefix>_insert_hash(<prefix>_hash *tb, <key> key, uint32 hash,
+ * 								   bool *found)
+ */
+DH_SCOPE	DH_ELEMENT_TYPE *DH_INSERT_HASH(DH_TYPE * tb, DH_KEY_TYPE key,
+											uint32 hash, bool *found);
+
+/* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
+DH_SCOPE	DH_ELEMENT_TYPE *DH_LOOKUP(DH_TYPE * tb, DH_KEY_TYPE key);
+
+/* <element> *<prefix>_lookup_hash(<prefix>_hash *tb, <key> key, uint32 hash) */
+DH_SCOPE	DH_ELEMENT_TYPE *DH_LOOKUP_HASH(DH_TYPE * tb, DH_KEY_TYPE key,
+											uint32 hash);
+
+/* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
+DH_SCOPE bool DH_DELETE(DH_TYPE * tb, DH_KEY_TYPE key);
+
+/* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
+DH_SCOPE void DH_START_ITERATE(DH_TYPE * tb, DH_ITERATOR * iter);
+
+/* <element> *<prefix>_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
+DH_SCOPE	DH_ELEMENT_TYPE *DH_ITERATE(DH_TYPE * tb, DH_ITERATOR * iter);
+
+#endif							/* DH_DECLARE */
+
+/* generate implementation of the hash table */
+#ifdef DH_DEFINE
+
+/*
+ * The maximum size for the hash table.  This must be a power of 2.  We cannot
+ * make this PG_UINT32_MAX + 1 because we use DH_UNUSED_BUCKET_INDEX denote an
+ * empty bucket.  Doing so would mean we could accidentally set a used
+ * bucket's index to DH_UNUSED_BUCKET_INDEX.
+ */
+#define DH_MAX_SIZE ((uint32) PG_INT32_MAX + 1)
+
+/* normal fillfactor, unless already close to maximum */
+#ifndef DH_FILLFACTOR
+#define DH_FILLFACTOR (0.9)
+#endif
+/* increase fillfactor if we otherwise would error out */
+#define DH_MAX_FILLFACTOR (0.98)
+/* grow if actual and optimal location bigger than */
+#ifndef DH_GROW_MAX_DIB
+#define DH_GROW_MAX_DIB 25
+#endif
+/*
+ * Grow if more than this number of buckets needs to be moved when inserting.
+ */
+#ifndef DH_GROW_MAX_MOVE
+#define DH_GROW_MAX_MOVE 150
+#endif
+#ifndef DH_GROW_MIN_FILLFACTOR
+/* but do not grow due to DH_GROW_MAX_* if below */
+#define DH_GROW_MIN_FILLFACTOR 0.1
+#endif
+
+/*
+ * Wrap the following definitions in include guards, to avoid multiple
+ * definition errors if this header is included more than once.  The rest of
+ * the file deliberately has no include guards, because it can be included
+ * with different parameters to define functions and types with non-colliding
+ * names.
+ */
+#ifndef DENSEHASH_H
+#define DENSEHASH_H
+
+#ifdef FRONTEND
+#define gh_error(...) pg_log_error(__VA_ARGS__)
+#define gh_log(...) pg_log_info(__VA_ARGS__)
+#else
+#define gh_error(...) elog(ERROR, __VA_ARGS__)
+#define gh_log(...) elog(LOG, __VA_ARGS__)
+#endif
+
+#endif							/* DENSEHASH_H */
+
+/*
+ * Gets the position of the first 1-bit which comes after 'prevbit' in the
+ * 'words' array.  'nwords' is the size of the 'words' array.
+ */
+static inline int32
+DH_NEXT_ONEBIT(DH_BITMAP_WORD * words, uint32 nwords, int32 prevbit)
+{
+	uint32		wordnum;
+
+	prevbit++;
+
+	wordnum = DH_WORDNUM(prevbit);
+	if (wordnum < nwords)
+	{
+		DH_BITMAP_WORD mask = (~(DH_BITMAP_WORD) 0) << DH_BITNUM(prevbit);
+		DH_BITMAP_WORD word = words[wordnum] & mask;
+
+		if (word != 0)
+			return wordnum * DH_BITS_PER_WORD + DH_RIGHTMOST_ONE_POS(word);
+
+		for (++wordnum; wordnum < nwords; wordnum++)
+		{
+			word = words[wordnum];
+
+			if (word != 0)
+			{
+				int32		result = wordnum * DH_BITS_PER_WORD;
+
+				result += DH_RIGHTMOST_ONE_POS(word);
+				return result;
+			}
+		}
+	}
+	return -1;
+}
+
+/*
+ * Gets the position of the first 0-bit which comes after 'prevbit' in the
+ * 'words' array.  'nwords' is the size of the 'words' array.
+ *
+ * This is similar to DH_NEXT_ONEBIT but flips the bits before operating on
+ * each DH_BITMAP_WORD.
+ */
+static inline int32
+DH_NEXT_ZEROBIT(DH_BITMAP_WORD * words, uint32 nwords, int32 prevbit)
+{
+	uint32		wordnum;
+
+	prevbit++;
+
+	wordnum = DH_WORDNUM(prevbit);
+	if (wordnum < nwords)
+	{
+		DH_BITMAP_WORD mask = (~(DH_BITMAP_WORD) 0) << DH_BITNUM(prevbit);
+		DH_BITMAP_WORD word = ~(words[wordnum] & mask); /* flip bits */
+
+		if (word != 0)
+			return wordnum * DH_BITS_PER_WORD + DH_RIGHTMOST_ONE_POS(word);
+
+		for (++wordnum; wordnum < nwords; wordnum++)
+		{
+			word = ~words[wordnum]; /* flip bits */
+
+			if (word != 0)
+			{
+				int32		result = wordnum * DH_BITS_PER_WORD;
+
+				result += DH_RIGHTMOST_ONE_POS(word);
+				return result;
+			}
+		}
+	}
+	return -1;
+}
+
+/*
+ * Finds the hash table entry for a given DH_BUCKET's 'index'.
+ */
+static inline DH_ELEMENT_TYPE *
+DH_INDEX_TO_ELEMENT(DH_TYPE * tb, uint32 index)
+{
+	DH_SEGMENT *seg;
+	uint32		segidx;
+	uint32		item;
+
+	segidx = DH_INDEX_SEGMENT(index);
+	item = DH_INDEX_ITEM(index);
+
+	Assert(segidx < tb->nsegments);
+
+	seg = tb->segments[segidx];
+
+	Assert(seg != NULL);
+
+	/* ensure this segment is marked as used */
+	Assert(seg->used_items[DH_WORDNUM(item)] & (((DH_BITMAP_WORD) 1) << DH_BITNUM(item)));
+
+	return &seg->items[item];
+}
+
+static inline void
+DH_MARK_SEGMENT_ITEM_USED(DH_TYPE * tb, DH_SEGMENT * seg, uint32 segidx,
+						  uint32 segitem)
+{
+	uint32		word = DH_WORDNUM(segitem);
+	uint32		bit = DH_BITNUM(segitem);
+
+	/* ensure this item is not marked as used */
+	Assert((seg->used_items[word] & (((DH_BITMAP_WORD) 1) << bit)) == 0);
+
+	/* switch on the used bit */
+	seg->used_items[word] |= (((DH_BITMAP_WORD) 1) << bit);
+
+	/* if the segment was previously empty then mark it as used */
+	if (seg->nitems == 0)
+	{
+		word = DH_WORDNUM(segidx);
+		bit = DH_BITNUM(segidx);
+
+		/* switch on the used bit for this segment */
+		tb->used_segments[word] |= (((DH_BITMAP_WORD) 1) << bit);
+	}
+	seg->nitems++;
+}
+
+static inline void
+DH_MARK_SEGMENT_ITEM_UNUSED(DH_TYPE * tb, DH_SEGMENT * seg, uint32 segidx,
+							uint32 segitem)
+{
+	uint32		word = DH_WORDNUM(segitem);
+	uint32		bit = DH_BITNUM(segitem);
+
+	/* ensure this item is marked as used */
+	Assert((seg->used_items[word] & (((DH_BITMAP_WORD) 1) << bit)) != 0);
+
+	/* switch off the used bit */
+	seg->used_items[word] &= ~(((DH_BITMAP_WORD) 1) << bit);
+
+	/* when removing the last item mark the segment as unused */
+	if (seg->nitems == 1)
+	{
+		word = DH_WORDNUM(segidx);
+		bit = DH_BITNUM(segidx);
+
+		/* switch off the used bit for this segment */
+		tb->used_segments[word] &= ~(((DH_BITMAP_WORD) 1) << bit);
+	}
+
+	seg->nitems--;
+}
+
+/*
+ * Returns the first unused entry from the first non-full segment and set
+ * *index to the index of the returned entry.
+ */
+static inline DH_ELEMENT_TYPE *
+DH_GET_NEXT_UNUSED_ENTRY(DH_TYPE * tb, uint32 *index)
+{
+	DH_SEGMENT *seg;
+	uint32		segidx = tb->first_free_segment;
+	uint32		itemidx;
+
+	seg = tb->segments[segidx];
+
+	/* find the first segment with an unused item */
+	while (seg != NULL && seg->nitems == DH_ITEMS_PER_SEGMENT)
+		seg = tb->segments[++segidx];
+
+	tb->first_free_segment = segidx;
+
+	/* allocate the segment if it's not already */
+	if (seg == NULL)
+	{
+		seg = DH_ALLOCATE(sizeof(DH_SEGMENT));
+		tb->segments[segidx] = seg;
+
+		seg->nitems = 0;
+		memset(seg->used_items, 0, sizeof(seg->used_items));
+		/* no need to zero the items array */
+
+		/* use the first slot in this segment */
+		itemidx = 0;
+	}
+	else
+	{
+		/* find the first unused item in this segment */
+		itemidx = DH_NEXT_ZEROBIT(seg->used_items, DH_BITMAP_WORDS, -1);
+		Assert(itemidx >= 0);
+	}
+
+	/* this is a good spot to ensure nitems matches the bits in used_items */
+	Assert(seg->nitems == pg_popcount((const char *) seg->used_items, DH_ITEMS_PER_SEGMENT / 8));
+
+	DH_MARK_SEGMENT_ITEM_USED(tb, seg, segidx, itemidx);
+
+	*index = segidx * DH_ITEMS_PER_SEGMENT + itemidx;
+	return &seg->items[itemidx];
+
+}
+
+/*
+ * Remove the entry denoted by 'index' from its segment.
+ */
+static inline void
+DH_REMOVE_ENTRY(DH_TYPE * tb, uint32 index)
+{
+	DH_SEGMENT *seg;
+	uint32		segidx = DH_INDEX_SEGMENT(index);
+	uint32		item = DH_INDEX_ITEM(index);
+
+	Assert(segidx < tb->nsegments);
+	seg = tb->segments[segidx];
+	Assert(seg != NULL);
+
+	DH_MARK_SEGMENT_ITEM_UNUSED(tb, seg, segidx, item);
+
+	/*
+	 * Lower the first free segment index to point to this segment so that the
+	 * next insert will store in this segment.  If it's already set to a lower
+	 * segment number then don't adjust as we want to consume slots from the
+	 * earliest segment first.
+	 */
+	if (tb->first_free_segment > segidx)
+		tb->first_free_segment = segidx;
+}
+
+/*
+ * Set 'bucket' as in use by 'index'.
+ */
+static inline void
+DH_SET_BUCKET_IN_USE(DH_BUCKET * bucket, uint32 index)
+{
+	bucket->index = index;
+}
+
+/*
+ * Mark 'bucket' as unused.
+ */
+static inline void
+DH_SET_BUCKET_EMPTY(DH_BUCKET * bucket)
+{
+	bucket->index = DH_UNUSED_BUCKET_INDEX;
+}
+
+/*
+ * Return true if 'bucket' is in use.
+ */
+static inline bool
+DH_IS_BUCKET_IN_USE(DH_BUCKET * bucket)
+{
+	return bucket->index != DH_UNUSED_BUCKET_INDEX;
+}
+
+ /*
+  * Compute sizing parameters for hashtable.  Called when creating and growing
+  * the hashtable.
+  */
+static inline void
+DH_COMPUTE_PARAMETERS(DH_TYPE * tb, uint32 newsize)
+{
+	uint32		size;
+
+	/*
+	 * Ensure the bucket array size has not exceeded DH_MAX_SIZE or wrapped
+	 * back to zero.
+	 */
+	if (newsize == 0 || newsize > DH_MAX_SIZE)
+		gh_error("hash table too large");
+
+	/*
+	 * Ensure we don't build a table that can't store an entire single segment
+	 * worth of data.
+	 */
+	size = Max(newsize, DH_ITEMS_PER_SEGMENT);
+
+	/* round up size to the next power of 2 */
+	size = pg_nextpower2_32(size);
+
+	/* now set size */
+	tb->size = size;
+	tb->sizemask = tb->size - 1;
+
+	/* calculate how many segments we'll need to store 'size' items */
+	tb->nsegments = pg_nextpower2_32(size / DH_ITEMS_PER_SEGMENT);
+
+	/*
+	 * Calculate the number of bitmap words needed to store a bit for each
+	 * segment.
+	 */
+	tb->used_segment_words = (tb->nsegments + DH_BITS_PER_WORD - 1) / DH_BITS_PER_WORD;
+
+	/*
+	 * Compute the next threshold at which we need to grow the hash table
+	 * again.
+	 */
+	if (tb->size == DH_MAX_SIZE)
+		tb->grow_threshold = (uint32) (((double) tb->size) * DH_MAX_FILLFACTOR);
+	else
+		tb->grow_threshold = (uint32) (((double) tb->size) * DH_FILLFACTOR);
+}
+
+/* return the optimal bucket for the hash */
+static inline uint32
+DH_INITIAL_BUCKET(DH_TYPE * tb, uint32 hash)
+{
+	return hash & tb->sizemask;
+}
+
+/* return the next bucket after the current, handling wraparound */
+static inline uint32
+DH_NEXT(DH_TYPE * tb, uint32 curelem, uint32 startelem)
+{
+	curelem = (curelem + 1) & tb->sizemask;
+
+	Assert(curelem != startelem);
+
+	return curelem;
+}
+
+/* return the bucket before the current, handling wraparound */
+static inline uint32
+DH_PREV(DH_TYPE * tb, uint32 curelem, uint32 startelem)
+{
+	curelem = (curelem - 1) & tb->sizemask;
+
+	Assert(curelem != startelem);
+
+	return curelem;
+}
+
+/* return the distance between a bucket and its optimal position */
+static inline uint32
+DH_DISTANCE_FROM_OPTIMAL(DH_TYPE * tb, uint32 optimal, uint32 bucket)
+{
+	if (optimal <= bucket)
+		return bucket - optimal;
+	else
+		return (tb->size + bucket) - optimal;
+}
+
+/*
+ * Create a hash table with 'nbuckets' buckets.
+ */
+DH_SCOPE	DH_TYPE *
+#ifdef DH_HAVE_PRIVATE_DATA
+DH_CREATE(uint32 nbuckets, void *private_data)
+#else
+DH_CREATE(uint32 nbuckets)
+#endif
+{
+	DH_TYPE    *tb;
+	uint32		size;
+	uint32		i;
+
+	tb = DH_ALLOCATE_ZERO(sizeof(DH_TYPE));
+
+#ifdef DH_HAVE_PRIVATE_DATA
+	tb->private_data = private_data;
+#endif
+
+	/* increase nelements by fillfactor, want to store nelements elements */
+	size = (uint32) Min((double) DH_MAX_SIZE, ((double) nbuckets) / DH_FILLFACTOR);
+
+	DH_COMPUTE_PARAMETERS(tb, size);
+
+	tb->buckets = DH_ALLOCATE(sizeof(DH_BUCKET) * tb->size);
+
+	/* ensure all the buckets are set to empty */
+	for (i = 0; i < tb->size; i++)
+		DH_SET_BUCKET_EMPTY(&tb->buckets[i]);
+
+	tb->segments = DH_ALLOCATE_ZERO(sizeof(DH_SEGMENT *) * tb->nsegments);
+	tb->used_segments = DH_ALLOCATE_ZERO(sizeof(DH_BITMAP_WORD) * tb->used_segment_words);
+	return tb;
+}
+
+/* destroy a previously created hash table */
+DH_SCOPE void
+DH_DESTROY(DH_TYPE * tb)
+{
+	DH_FREE(tb->buckets);
+
+	/* Free each segment one by one */
+	for (uint32 n = 0; n < tb->nsegments; n++)
+	{
+		if (tb->segments[n] != NULL)
+			DH_FREE(tb->segments[n]);
+	}
+
+	DH_FREE(tb->segments);
+	DH_FREE(tb->used_segments);
+
+	pfree(tb);
+}
+
+/* reset the contents of a previously created hash table */
+DH_SCOPE void
+DH_RESET(DH_TYPE * tb)
+{
+	int32		i = -1;
+	uint32		x;
+
+	/* reset each used segment one by one */
+	while ((i = DH_NEXT_ONEBIT(tb->used_segments, tb->used_segment_words,
+							   i)) >= 0)
+	{
+		DH_SEGMENT *seg = tb->segments[i];
+
+		Assert(seg != NULL);
+
+		seg->nitems = 0;
+		memset(seg->used_items, 0, sizeof(seg->used_items));
+	}
+
+	/* empty every bucket */
+	for (x = 0; x < tb->size; x++)
+		DH_SET_BUCKET_EMPTY(&tb->buckets[x]);
+
+	/* zero the used segment bits */
+	memset(tb->used_segments, 0, sizeof(DH_BITMAP_WORD) * tb->used_segment_words);
+
+	/* and mark the table as having zero members */
+	tb->members = 0;
+
+	/* ensure we start putting any new items in the first segment */
+	tb->first_free_segment = 0;
+}
+
+/*
+ * Grow a hash table to at least 'newsize' buckets.
+ *
+ * Usually this will automatically be called by insertions/deletions, when
+ * necessary. But resizing to the exact input size can be advantageous
+ * performance-wise, when known at some point.
+ */
+DH_SCOPE void
+DH_GROW(DH_TYPE * tb, uint32 newsize)
+{
+	uint32		oldsize = tb->size;
+	uint32		oldnsegments = tb->nsegments;
+	uint32		oldusedsegmentwords = tb->used_segment_words;
+	DH_BUCKET  *oldbuckets = tb->buckets;
+	DH_SEGMENT **oldsegments = tb->segments;
+	DH_BITMAP_WORD *oldusedsegments = tb->used_segments;
+	DH_BUCKET  *newbuckets;
+	uint32		i;
+	uint32		startelem = 0;
+	uint32		copyelem;
+
+	Assert(oldsize == pg_nextpower2_32(oldsize));
+
+	/* compute parameters for new table */
+	DH_COMPUTE_PARAMETERS(tb, newsize);
+
+	tb->buckets = DH_ALLOCATE(sizeof(DH_ELEMENT_TYPE) * tb->size);
+
+	/* Ensure all the buckets are set to empty */
+	for (i = 0; i < tb->size; i++)
+		DH_SET_BUCKET_EMPTY(&tb->buckets[i]);
+
+	newbuckets = tb->buckets;
+
+	/*
+	 * Copy buckets from the old buckets to newbuckets. We theoretically could
+	 * use DH_INSERT here, to avoid code duplication, but that's more general
+	 * than we need. We neither want tb->members increased, nor do we need to
+	 * do deal with deleted elements, nor do we need to compare keys. So a
+	 * special-cased implementation is a lot faster.  Resizing can be time
+	 * consuming and frequent, that's worthwhile to optimize.
+	 *
+	 * To be able to simply move buckets over, we have to start not at the
+	 * first bucket (i.e oldbuckets[0]), but find the first bucket that's
+	 * either empty or is occupied by an entry at its optimal position. Such a
+	 * bucket has to exist in any table with a load factor under 1, as not all
+	 * buckets are occupied, i.e. there always has to be an empty bucket.  By
+	 * starting at such a bucket we can move the entries to the larger table,
+	 * without having to deal with conflicts.
+	 */
+
+	/* search for the first element in the hash that's not wrapped around */
+	for (i = 0; i < oldsize; i++)
+	{
+		DH_BUCKET  *oldbucket = &oldbuckets[i];
+		uint32		hash;
+		uint32		optimal;
+
+		if (!DH_IS_BUCKET_IN_USE(oldbucket))
+		{
+			startelem = i;
+			break;
+		}
+
+		hash = oldbucket->hashvalue;
+		optimal = DH_INITIAL_BUCKET(tb, hash);
+
+		if (optimal == i)
+		{
+			startelem = i;
+			break;
+		}
+	}
+
+	/* and copy all elements in the old table */
+	copyelem = startelem;
+	for (i = 0; i < oldsize; i++)
+	{
+		DH_BUCKET  *oldbucket = &oldbuckets[copyelem];
+
+		if (DH_IS_BUCKET_IN_USE(oldbucket))
+		{
+			uint32		hash;
+			uint32		startelem;
+			uint32		curelem;
+			DH_BUCKET  *newbucket;
+
+			hash = oldbucket->hashvalue;
+			startelem = DH_INITIAL_BUCKET(tb, hash);
+			curelem = startelem;
+
+			/* find empty element to put data into */
+			for (;;)
+			{
+				newbucket = &newbuckets[curelem];
+
+				if (!DH_IS_BUCKET_IN_USE(newbucket))
+					break;
+
+				curelem = DH_NEXT(tb, curelem, startelem);
+			}
+
+			/* copy entry to new slot */
+			memcpy(newbucket, oldbucket, sizeof(DH_BUCKET));
+		}
+
+		/* can't use DH_NEXT here, would use new size */
+		copyelem++;
+		if (copyelem >= oldsize)
+			copyelem = 0;
+	}
+
+	DH_FREE(oldbuckets);
+
+	/*
+	 * Enlarge the segment array so we can store enough segments for the new
+	 * hash table capacity.
+	 */
+	tb->segments = DH_ALLOCATE(sizeof(DH_SEGMENT *) * tb->nsegments);
+	memcpy(tb->segments, oldsegments, sizeof(DH_SEGMENT *) * oldnsegments);
+	/* zero the newly extended part of the array */
+	memset(&tb->segments[oldnsegments], 0, sizeof(DH_SEGMENT *) *
+		   (tb->nsegments - oldnsegments));
+	DH_FREE(oldsegments);
+
+	/*
+	 * The majority of tables will only ever need one bitmap word to store
+	 * used segments, so we only bother to reallocate the used_segments array
+	 * if the number of bitmap words has actually changed.
+	 */
+	if (tb->used_segment_words != oldusedsegmentwords)
+	{
+		tb->used_segments = DH_ALLOCATE(sizeof(DH_BITMAP_WORD) *
+										tb->used_segment_words);
+		memcpy(tb->used_segments, oldusedsegments, sizeof(DH_BITMAP_WORD) *
+			   oldusedsegmentwords);
+		memset(&tb->used_segments[oldusedsegmentwords], 0,
+			   sizeof(DH_BITMAP_WORD) * (tb->used_segment_words -
+										 oldusedsegmentwords));
+
+		DH_FREE(oldusedsegments);
+	}
+}
+
+/*
+ * This is a separate static inline function, so it can be reliably be inlined
+ * into its wrapper functions even if DH_SCOPE is extern.
+ */
+static inline DH_ELEMENT_TYPE *
+DH_INSERT_HASH_INTERNAL(DH_TYPE * tb, DH_KEY_TYPE key, uint32 hash, bool *found)
+{
+	uint32		startelem;
+	uint32		curelem;
+	DH_BUCKET  *buckets;
+	uint32		insertdist;
+
+restart:
+	insertdist = 0;
+
+	/*
+	 * To avoid doing the grow check inside the loop, we do the grow check
+	 * regardless of if the key is present.  This also lets us avoid having to
+	 * re-find our position in the hashtable after resizing.
+	 *
+	 * Note that this also reached when resizing the table due to
+	 * DH_GROW_MAX_DIB / DH_GROW_MAX_MOVE.
+	 */
+	if (unlikely(tb->members >= tb->grow_threshold))
+	{
+		/* this may wrap back to 0 when we're already at DH_MAX_SIZE */
+		DH_GROW(tb, tb->size * 2);
+	}
+
+	/* perform the insert starting the bucket search at optimal location */
+	buckets = tb->buckets;
+	startelem = DH_INITIAL_BUCKET(tb, hash);
+	curelem = startelem;
+	for (;;)
+	{
+		DH_BUCKET  *bucket = &buckets[curelem];
+		DH_ELEMENT_TYPE *entry;
+		uint32		curdist;
+		uint32		curhash;
+		uint32		curoptimal;
+
+		/* any empty bucket can directly be used */
+		if (!DH_IS_BUCKET_IN_USE(bucket))
+		{
+			uint32		index;
+
+			/* and add the new entry */
+			tb->members++;
+
+			entry = DH_GET_NEXT_UNUSED_ENTRY(tb, &index);
+			entry->DH_KEY = key;
+			bucket->hashvalue = hash;
+			DH_SET_BUCKET_IN_USE(bucket, index);
+			*found = false;
+			return entry;
+		}
+
+		curhash = bucket->hashvalue;
+
+		if (curhash == hash)
+		{
+			/*
+			 * The hash value matches so we just need to ensure the key
+			 * matches too.  To do that, we need to lookup the entry in the
+			 * segments using the index stored in the bucket.
+			 */
+			entry = DH_INDEX_TO_ELEMENT(tb, bucket->index);
+
+			/* if we find a match, we're done */
+			if (DH_EQUAL(tb, key, entry->DH_KEY))
+			{
+				Assert(DH_IS_BUCKET_IN_USE(bucket));
+				*found = true;
+				return entry;
+			}
+		}
+
+		/*
+		 * For non-empty, non-matching buckets we have to decide whether to
+		 * skip over or move the colliding entry.  When the colliding
+		 * element's distance to its optimal position is smaller than the
+		 * to-be-inserted entry's, we shift the colliding entry (and its
+		 * followers) one bucket closer to their optimal position.
+		 */
+		curoptimal = DH_INITIAL_BUCKET(tb, curhash);
+		curdist = DH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem);
+
+		if (insertdist > curdist)
+		{
+			DH_ELEMENT_TYPE *entry;
+			DH_BUCKET  *lastbucket = bucket;
+			uint32		emptyelem = curelem;
+			uint32		moveelem;
+			int32		emptydist = 0;
+			uint32		index;
+
+			/* find next empty bucket */
+			for (;;)
+			{
+				DH_BUCKET  *emptybucket;
+
+				emptyelem = DH_NEXT(tb, emptyelem, startelem);
+				emptybucket = &buckets[emptyelem];
+
+				if (!DH_IS_BUCKET_IN_USE(emptybucket))
+				{
+					lastbucket = emptybucket;
+					break;
+				}
+
+				/*
+				 * To avoid negative consequences from overly imbalanced
+				 * hashtables, grow the hashtable if collisions would require
+				 * us to move a lot of entries.  The most likely cause of such
+				 * imbalance is filling a (currently) small table, from a
+				 * currently big one, in hashtable order.  Don't grow if the
+				 * hashtable would be too empty, to prevent quick space
+				 * explosion for some weird edge cases.
+				 */
+				if (unlikely(++emptydist > DH_GROW_MAX_MOVE) &&
+					((double) tb->members / tb->size) >= DH_GROW_MIN_FILLFACTOR)
+				{
+					tb->grow_threshold = 0;
+					goto restart;
+				}
+			}
+
+			/* shift forward, starting at last occupied element */
+
+			/*
+			 * TODO: This could be optimized to be one memcpy in many cases,
+			 * excepting wrapping around at the end of ->data. Hasn't shown up
+			 * in profiles so far though.
+			 */
+			moveelem = emptyelem;
+			while (moveelem != curelem)
+			{
+				DH_BUCKET  *movebucket;
+
+				moveelem = DH_PREV(tb, moveelem, startelem);
+				movebucket = &buckets[moveelem];
+
+				memcpy(lastbucket, movebucket, sizeof(DH_BUCKET));
+				lastbucket = movebucket;
+			}
+
+			/* and add the new entry */
+			tb->members++;
+
+			entry = DH_GET_NEXT_UNUSED_ENTRY(tb, &index);
+			entry->DH_KEY = key;
+			bucket->hashvalue = hash;
+			DH_SET_BUCKET_IN_USE(bucket, index);
+			*found = false;
+			return entry;
+		}
+
+		curelem = DH_NEXT(tb, curelem, startelem);
+		insertdist++;
+
+		/*
+		 * To avoid negative consequences from overly imbalanced hashtables,
+		 * grow the hashtable if collisions lead to large runs. The most
+		 * likely cause of such imbalance is filling a (currently) small
+		 * table, from a currently big one, in hashtable order.  Don't grow if
+		 * the hashtable would be too empty, to prevent quick space explosion
+		 * for some weird edge cases.
+		 */
+		if (unlikely(insertdist > DH_GROW_MAX_DIB) &&
+			((double) tb->members / tb->size) >= DH_GROW_MIN_FILLFACTOR)
+		{
+			tb->grow_threshold = 0;
+			goto restart;
+		}
+	}
+}
+
+/*
+ * Insert the key into the hashtable, set *found to true if the key already
+ * exists, false otherwise. Returns the hashtable entry in either case.
+ */
+DH_SCOPE	DH_ELEMENT_TYPE *
+DH_INSERT(DH_TYPE * tb, DH_KEY_TYPE key, bool *found)
+{
+	uint32		hash = DH_HASH_KEY(tb, key);
+
+	return DH_INSERT_HASH_INTERNAL(tb, key, hash, found);
+}
+
+/*
+ * Insert the key into the hashtable using an already-calculated hash. Set
+ * *found to true if the key already exists, false otherwise. Returns the
+ * hashtable entry in either case.
+ */
+DH_SCOPE	DH_ELEMENT_TYPE *
+DH_INSERT_HASH(DH_TYPE * tb, DH_KEY_TYPE key, uint32 hash, bool *found)
+{
+	return DH_INSERT_HASH_INTERNAL(tb, key, hash, found);
+}
+
+/*
+ * This is a separate static inline function, so it can be reliably be inlined
+ * into its wrapper functions even if DH_SCOPE is extern.
+ */
+static inline DH_ELEMENT_TYPE *
+DH_LOOKUP_HASH_INTERNAL(DH_TYPE * tb, DH_KEY_TYPE key, uint32 hash)
+{
+	const uint32 startelem = DH_INITIAL_BUCKET(tb, hash);
+	uint32		curelem = startelem;
+
+	for (;;)
+	{
+		DH_BUCKET  *bucket = &tb->buckets[curelem];
+
+		if (!DH_IS_BUCKET_IN_USE(bucket))
+			return NULL;
+
+		if (bucket->hashvalue == hash)
+		{
+			DH_ELEMENT_TYPE *entry;
+
+			/*
+			 * The hash value matches so we just need to ensure the key
+			 * matches too.  To do that, we need to lookup the entry in the
+			 * segments using the index stored in the bucket.
+			 */
+			entry = DH_INDEX_TO_ELEMENT(tb, bucket->index);
+
+			/* if we find a match, we're done */
+			if (DH_EQUAL(tb, key, entry->DH_KEY))
+				return entry;
+		}
+
+		/*
+		 * TODO: we could stop search based on distance. If the current
+		 * buckets's distance-from-optimal is smaller than what we've skipped
+		 * already, the entry doesn't exist.
+		 */
+
+		curelem = DH_NEXT(tb, curelem, startelem);
+	}
+}
+
+/*
+ * Lookup an entry in the hash table.  Returns NULL if key not present.
+ */
+DH_SCOPE	DH_ELEMENT_TYPE *
+DH_LOOKUP(DH_TYPE * tb, DH_KEY_TYPE key)
+{
+	uint32		hash = DH_HASH_KEY(tb, key);
+
+	return DH_LOOKUP_HASH_INTERNAL(tb, key, hash);
+}
+
+/*
+ * Lookup an entry in the hash table using an already-calculated hash.
+ *
+ * Returns NULL if key not present.
+ */
+DH_SCOPE	DH_ELEMENT_TYPE *
+DH_LOOKUP_HASH(DH_TYPE * tb, DH_KEY_TYPE key, uint32 hash)
+{
+	return DH_LOOKUP_HASH_INTERNAL(tb, key, hash);
+}
+
+/*
+ * Delete an entry from hash table by key.  Returns whether to-be-deleted key
+ * was present.
+ */
+DH_SCOPE bool
+DH_DELETE(DH_TYPE * tb, DH_KEY_TYPE key)
+{
+	uint32		hash = DH_HASH_KEY(tb, key);
+	uint32		startelem = DH_INITIAL_BUCKET(tb, hash);
+	uint32		curelem = startelem;
+
+	for (;;)
+	{
+		DH_BUCKET  *bucket = &tb->buckets[curelem];
+
+		if (!DH_IS_BUCKET_IN_USE(bucket))
+			return false;
+
+		if (bucket->hashvalue == hash)
+		{
+			DH_ELEMENT_TYPE *entry;
+
+			entry = DH_INDEX_TO_ELEMENT(tb, bucket->index);
+
+			if (DH_EQUAL(tb, key, entry->DH_KEY))
+			{
+				DH_BUCKET  *lastbucket = bucket;
+
+				/* mark the entry as unused */
+				DH_REMOVE_ENTRY(tb, bucket->index);
+				/* and mark the bucket unused */
+				DH_SET_BUCKET_EMPTY(bucket);
+
+				tb->members--;
+
+				/*
+				 * Backward shift following buckets till either an empty
+				 * bucket or a bucket at its optimal position is encountered.
+				 *
+				 * While that sounds expensive, the average chain length is
+				 * short, and deletions would otherwise require tombstones.
+				 */
+				for (;;)
+				{
+					DH_BUCKET  *curbucket;
+					uint32		curhash;
+					uint32		curoptimal;
+
+					curelem = DH_NEXT(tb, curelem, startelem);
+					curbucket = &tb->buckets[curelem];
+
+					if (!DH_IS_BUCKET_IN_USE(curbucket))
+						break;
+
+					curhash = curbucket->hashvalue;
+					curoptimal = DH_INITIAL_BUCKET(tb, curhash);
+
+					/* current is at optimal position, done */
+					if (curoptimal == curelem)
+					{
+						DH_SET_BUCKET_EMPTY(lastbucket);
+						break;
+					}
+
+					/* shift */
+					memcpy(lastbucket, curbucket, sizeof(DH_BUCKET));
+					DH_SET_BUCKET_EMPTY(curbucket);
+
+					lastbucket = curbucket;
+				}
+
+				return true;
+			}
+		}
+		/* TODO: return false; if the distance is too big */
+
+		curelem = DH_NEXT(tb, curelem, startelem);
+	}
+}
+
+/*
+ * Initialize iterator.
+ */
+DH_SCOPE void
+DH_START_ITERATE(DH_TYPE * tb, DH_ITERATOR * iter)
+{
+	iter->cursegidx = -1;
+	iter->curitemidx = -1;
+	iter->found_members = 0;
+	iter->total_members = tb->members;
+}
+
+/*
+ * Iterate over all entries in the hashtable. Return the next occupied entry,
+ * or NULL if there are no more entries.
+ *
+ * During iteration the only current entry in the hash table and any entry
+ * which was previously visited in the loop may be deleted.  Deletion of items
+ * not yet visited is prohibited as are insertions of new entries.
+ */
+DH_SCOPE	DH_ELEMENT_TYPE *
+DH_ITERATE(DH_TYPE * tb, DH_ITERATOR * iter)
+{
+	/*
+	 * Bail if we've already visited all members.  This check allows us to
+	 * exit quickly in cases where the table is large but it only contains a
+	 * small number of records.  This also means that inserts into the table
+	 * are not possible during iteration.  If that is done then we may not
+	 * visit all items in the table.  Rather than ever removing this check to
+	 * allow table insertions during iteration, we should add another iterator
+	 * where insertions are safe.
+	 */
+	if (iter->found_members == iter->total_members)
+		return NULL;
+
+	for (;;)
+	{
+		DH_SEGMENT *seg;
+
+		/* need a new segment? */
+		if (iter->curitemidx == -1)
+		{
+			iter->cursegidx = DH_NEXT_ONEBIT(tb->used_segments,
+											 tb->used_segment_words,
+											 iter->cursegidx);
+
+			/* no more segments with items? We're done */
+			if (iter->cursegidx == -1)
+				return NULL;
+		}
+
+		seg = tb->segments[iter->cursegidx];
+
+		/* if the segment has items then it certainly shouldn't be NULL */
+		Assert(seg != NULL);
+
+		/*
+		 * Advance to the next used item in this segment.  For full segments
+		 * we bypass the bitmap and just skip to the next item, otherwise we
+		 * consult the bitmap to find the next used item.
+		 */
+		if (seg->nitems == DH_ITEMS_PER_SEGMENT)
+		{
+			if (iter->curitemidx == DH_ITEMS_PER_SEGMENT - 1)
+				iter->curitemidx = -1;
+			else
+			{
+				iter->curitemidx++;
+				iter->found_members++;
+				return &seg->items[iter->curitemidx];
+			}
+		}
+		else
+		{
+			iter->curitemidx = DH_NEXT_ONEBIT(seg->used_items,
+											  DH_BITMAP_WORDS,
+											  iter->curitemidx);
+
+			if (iter->curitemidx >= 0)
+			{
+				iter->found_members++;
+				return &seg->items[iter->curitemidx];
+			}
+		}
+
+		/*
+		 * DH_NEXT_ONEBIT returns -1 when there are no more bits.  We just
+		 * loop again to fetch the next segment.
+		 */
+	}
+}
+
+#endif							/* DH_DEFINE */
+
+/* undefine external parameters, so next hash table can be defined */
+#undef DH_PREFIX
+#undef DH_KEY_TYPE
+#undef DH_KEY
+#undef DH_ELEMENT_TYPE
+#undef DH_HASH_KEY
+#undef DH_SCOPE
+#undef DH_DECLARE
+#undef DH_DEFINE
+#undef DH_EQUAL
+#undef DH_ALLOCATE
+#undef DH_ALLOCATE_ZERO
+#undef DH_FREE
+
+/* undefine locally declared macros */
+#undef DH_MAKE_PREFIX
+#undef DH_MAKE_NAME
+#undef DH_MAKE_NAME_
+#undef DH_ITEMS_PER_SEGMENT
+#undef DH_UNUSED_BUCKET_INDEX
+#undef DH_INDEX_SEGMENT
+#undef DH_INDEX_ITEM
+#undef DH_BITS_PER_WORD
+#undef DH_BITMAP_WORD
+#undef DH_RIGHTMOST_ONE_POS
+#undef DH_BITMAP_WORDS
+#undef DH_WORDNUM
+#undef DH_BITNUM
+#undef DH_RAW_ALLOCATOR
+#undef DH_MAX_SIZE
+#undef DH_FILLFACTOR
+#undef DH_MAX_FILLFACTOR
+#undef DH_GROW_MAX_DIB
+#undef DH_GROW_MAX_MOVE
+#undef DH_GROW_MIN_FILLFACTOR
+
+/* types */
+#undef DH_TYPE
+#undef DH_BUCKET
+#undef DH_SEGMENT
+#undef DH_ITERATOR
+
+/* external function names */
+#undef DH_CREATE
+#undef DH_DESTROY
+#undef DH_RESET
+#undef DH_INSERT
+#undef DH_INSERT_HASH
+#undef DH_DELETE
+#undef DH_LOOKUP
+#undef DH_LOOKUP_HASH
+#undef DH_GROW
+#undef DH_START_ITERATE
+#undef DH_ITERATE
+
+/* internal function names */
+#undef DH_NEXT_ONEBIT
+#undef DH_NEXT_ZEROBIT
+#undef DH_INDEX_TO_ELEMENT
+#undef DH_MARK_SEGMENT_ITEM_USED
+#undef DH_MARK_SEGMENT_ITEM_UNUSED
+#undef DH_GET_NEXT_UNUSED_ENTRY
+#undef DH_REMOVE_ENTRY
+#undef DH_SET_BUCKET_IN_USE
+#undef DH_SET_BUCKET_EMPTY
+#undef DH_IS_BUCKET_IN_USE
+#undef DH_COMPUTE_PARAMETERS
+#undef DH_NEXT
+#undef DH_PREV
+#undef DH_DISTANCE_FROM_OPTIMAL
+#undef DH_INITIAL_BUCKET
+#undef DH_INSERT_HASH_INTERNAL
+#undef DH_LOOKUP_HASH_INTERNAL
-- 
2.30.2