From: Tom Lane <tgl@sss.pgh.pa.us>
To: pgsql-hackers@lists.postgresql.org
Subject: Experimenting with hash tables inside pg_dump
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0"
Content-ID: <2595103.1634855164.0@sss.pgh.pa.us>
Date: Thu, 21 Oct 2021 18:27:25 -0400
Message-ID: <2595220.1634855245@sss.pgh.pa.us>
Archived-At: 
 <https://www.postgresql.org/message-id/2595220.1634855245%40sss.pgh.pa.us>
Precedence: bulk

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <2595103.1634855164.1@sss.pgh.pa.us>

Today, pg_dump does a lot of internal lookups via binary search
in presorted arrays.  I thought it might improve matters
to replace those binary searches with hash tables, theoretically
converting O(log N) searches into O(1) searches.  So I tried making
a hash table indexed by CatalogId (tableoid+oid) with simplehash.h,
and replacing as many data structures as I could with that.

This makes the code shorter and (IMO anyway) cleaner, but

(a) the executable size increases by a few KB --- apparently, even
the minimum subset of simplehash.h's functionality is code-wasteful.

(b) I couldn't measure any change in performance at all.  I tried
it on the regression database and on a toy DB with 10000 simple
tables.  Maybe on a really large DB you'd notice some difference,
but I'm not very optimistic now.

So this experiment feels like a failure, but I thought I'd post
the patch and results for the archives' sake.  Maybe somebody
will think of a way to improve matters.  Or maybe it's worth
doing just to shorten the code?

			regards, tom lane


------- =_aaaaaaaaaa0
Content-Type: text/x-diff; name="use-simplehash-in-pg-dump-1.patch";
	charset="us-ascii"
Content-ID: <2595103.1634855164.2@sss.pgh.pa.us>
Content-Description: use-simplehash-in-pg-dump-1.patch
Content-Transfer-Encoding: quoted-printable

diff --git a/src/bin/pg_dump/common.c b/src/bin/pg_dump/common.c
index 1f24e79665..49932fd598 100644
--- a/src/bin/pg_dump/common.c
+++ b/src/bin/pg_dump/common.c
@@ -18,6 +18,14 @@
 #include <ctype.h>
 =

 #include "catalog/pg_class_d.h"
+#include "catalog/pg_collation_d.h"
+#include "catalog/pg_extension_d.h"
+#include "catalog/pg_namespace_d.h"
+#include "catalog/pg_operator_d.h"
+#include "catalog/pg_proc_d.h"
+#include "catalog/pg_publication_d.h"
+#include "catalog/pg_type_d.h"
+#include "common/hashfn.h"
 #include "fe_utils/string_utils.h"
 #include "pg_backup_archiver.h"
 #include "pg_backup_utils.h"
@@ -31,54 +39,54 @@ static int	allocedDumpIds =3D 0;
 static DumpId lastDumpId =3D 0;	/* Note: 0 is InvalidDumpId */
 =

 /*
- * Variables for mapping CatalogId to DumpableObject
- */
-static bool catalogIdMapValid =3D false;
-static DumpableObject **catalogIdMap =3D NULL;
-static int	numCatalogIds =3D 0;
-
-/*
- * These variables are static to avoid the notational cruft of having to =
pass
- * them into findTableByOid() and friends.  For each of these arrays, we =
build
- * a sorted-by-OID index array immediately after the objects are fetched,
- * and then we use binary search in findTableByOid() and friends.  (qsort=
'ing
- * the object arrays themselves would be simpler, but it doesn't work bec=
ause
- * pg_dump.c may have already established pointers between items.)
+ * Infrastructure for mapping CatalogId to DumpableObject
+ *
+ * We use a hash table generated by simplehash.h.  That infrastructure
+ * requires all the hash table entries to be the same size, and it also
+ * expects that it can move them around when resizing the table.  So we
+ * cannot make the DumpableObjects be elements of the hash table directly=
;
+ * instead, the hash table elements contain pointers to DumpableObjects.
+ *
+ * It turns out to be convenient to also use this data structure to map
+ * CatalogIds to owning extensions, if any.  Since extension membership
+ * data is read before creating most DumpableObjects, either one of dobj
+ * and ext could be NULL.
  */
-static DumpableObject **tblinfoindex;
-static DumpableObject **typinfoindex;
-static DumpableObject **funinfoindex;
-static DumpableObject **oprinfoindex;
-static DumpableObject **collinfoindex;
-static DumpableObject **nspinfoindex;
-static DumpableObject **extinfoindex;
-static DumpableObject **pubinfoindex;
-static int	numTables;
-static int	numTypes;
-static int	numFuncs;
-static int	numOperators;
-static int	numCollations;
-static int	numNamespaces;
-static int	numExtensions;
-static int	numPublications;
-
-/* This is an array of object identities, not actual DumpableObjects */
-static ExtensionMemberId *extmembers;
-static int	numextmembers;
+typedef struct _catalogIdMapEntry
+{
+	CatalogId	catId;			/* the indexed CatalogId */
+	uint32		status;			/* hash status */
+	uint32		hashval;		/* hash code for the CatalogId */
+	DumpableObject *dobj;		/* the associated DumpableObject, if any */
+	ExtensionInfo *ext;			/* owning extension, if any */
+} CatalogIdMapEntry;
+
+#define SH_PREFIX		catalogid
+#define SH_ELEMENT_TYPE	CatalogIdMapEntry
+#define SH_KEY_TYPE		CatalogId
+#define	SH_KEY			catId
+#define SH_HASH_KEY(tb, key)	hash_bytes((const unsigned char *) &(key), s=
izeof(CatalogId))
+#define SH_EQUAL(tb, a, b)		((a).oid =3D=3D (b).oid && (a).tableoid =3D=3D=
 (b).tableoid)
+#define SH_STORE_HASH
+#define SH_GET_HASH(tb, a) (a)->hashval
+#define	SH_SCOPE		static inline
+#define SH_RAW_ALLOCATOR	pg_malloc0
+#define SH_DECLARE
+#define SH_DEFINE
+#include "lib/simplehash.h"
+
+#define CATALOGIDHASH_INITIAL_SIZE	10000
+
+static catalogid_hash *catalogIdHash =3D NULL;
 =

 static void flagInhTables(Archive *fout, TableInfo *tbinfo, int numTables=
,
 						  InhInfo *inhinfo, int numInherits);
 static void flagInhIndexes(Archive *fout, TableInfo *tblinfo, int numTabl=
es);
 static void flagInhAttrs(DumpOptions *dopt, TableInfo *tblinfo, int numTa=
bles);
-static DumpableObject **buildIndexArray(void *objArray, int numObjs,
-										Size objSize);
-static int	DOCatalogIdCompare(const void *p1, const void *p2);
-static int	ExtensionMemberIdCompare(const void *p1, const void *p2);
 static void findParentsByOid(TableInfo *self,
 							 InhInfo *inhinfo, int numInherits);
 static int	strInArray(const char *pattern, char **arr, int arr_size);
-static IndxInfo *findIndexByOid(Oid oid, DumpableObject **idxinfoindex,
-								int numIndexes);
+static IndxInfo *findIndexByOid(Oid oid);
 =

 =

 /*
@@ -89,14 +97,16 @@ TableInfo *
 getSchemaData(Archive *fout, int *numTablesPtr)
 {
 	TableInfo  *tblinfo;
-	TypeInfo   *typinfo;
-	FuncInfo   *funinfo;
-	OprInfo    *oprinfo;
-	CollInfo   *collinfo;
-	NamespaceInfo *nspinfo;
 	ExtensionInfo *extinfo;
-	PublicationInfo *pubinfo;
 	InhInfo    *inhinfo;
+	int			numTables;
+	int			numTypes;
+	int			numFuncs;
+	int			numOperators;
+	int			numCollations;
+	int			numNamespaces;
+	int			numExtensions;
+	int			numPublications;
 	int			numAggregates;
 	int			numInherits;
 	int			numRules;
@@ -123,14 +133,12 @@ getSchemaData(Archive *fout, int *numTablesPtr)
 	 */
 	pg_log_info("reading extensions");
 	extinfo =3D getExtensions(fout, &numExtensions);
-	extinfoindex =3D buildIndexArray(extinfo, numExtensions, sizeof(Extensio=
nInfo));
 =

 	pg_log_info("identifying extension members");
 	getExtensionMembership(fout, extinfo, numExtensions);
 =

 	pg_log_info("reading schemas");
-	nspinfo =3D getNamespaces(fout, &numNamespaces);
-	nspinfoindex =3D buildIndexArray(nspinfo, numNamespaces, sizeof(Namespac=
eInfo));
+	(void) getNamespaces(fout, &numNamespaces);
 =

 	/*
 	 * getTables should be done as soon as possible, so as to minimize the
@@ -140,19 +148,15 @@ getSchemaData(Archive *fout, int *numTablesPtr)
 	 */
 	pg_log_info("reading user-defined tables");
 	tblinfo =3D getTables(fout, &numTables);
-	tblinfoindex =3D buildIndexArray(tblinfo, numTables, sizeof(TableInfo));
 =

-	/* Do this after we've built tblinfoindex */
 	getOwnedSeqs(fout, tblinfo, numTables);
 =

 	pg_log_info("reading user-defined functions");
-	funinfo =3D getFuncs(fout, &numFuncs);
-	funinfoindex =3D buildIndexArray(funinfo, numFuncs, sizeof(FuncInfo));
+	(void) getFuncs(fout, &numFuncs);
 =

 	/* this must be after getTables and getFuncs */
 	pg_log_info("reading user-defined types");
-	typinfo =3D getTypes(fout, &numTypes);
-	typinfoindex =3D buildIndexArray(typinfo, numTypes, sizeof(TypeInfo));
+	(void) getTypes(fout, &numTypes);
 =

 	/* this must be after getFuncs, too */
 	pg_log_info("reading procedural languages");
@@ -162,8 +166,7 @@ getSchemaData(Archive *fout, int *numTablesPtr)
 	getAggregates(fout, &numAggregates);
 =

 	pg_log_info("reading user-defined operators");
-	oprinfo =3D getOperators(fout, &numOperators);
-	oprinfoindex =3D buildIndexArray(oprinfo, numOperators, sizeof(OprInfo))=
;
+	(void) getOperators(fout, &numOperators);
 =

 	pg_log_info("reading user-defined access methods");
 	getAccessMethods(fout, &numAccessMethods);
@@ -196,8 +199,7 @@ getSchemaData(Archive *fout, int *numTablesPtr)
 	getDefaultACLs(fout, &numDefaultACLs);
 =

 	pg_log_info("reading user-defined collations");
-	collinfo =3D getCollations(fout, &numCollations);
-	collinfoindex =3D buildIndexArray(collinfo, numCollations, sizeof(CollIn=
fo));
+	(void) getCollations(fout, &numCollations);
 =

 	pg_log_info("reading user-defined conversions");
 	getConversions(fout, &numConversions);
@@ -250,9 +252,7 @@ getSchemaData(Archive *fout, int *numTablesPtr)
 	getPolicies(fout, tblinfo, numTables);
 =

 	pg_log_info("reading publications");
-	pubinfo =3D getPublications(fout, &numPublications);
-	pubinfoindex =3D buildIndexArray(pubinfo, numPublications,
-								   sizeof(PublicationInfo));
+	(void) getPublications(fout, &numPublications);
 =

 	pg_log_info("reading publication membership");
 	getPublicationTables(fout, tblinfo, numTables);
@@ -375,34 +375,15 @@ flagInhIndexes(Archive *fout, TableInfo tblinfo[], i=
nt numTables)
 	int			i,
 				j,
 				k;
-	DumpableObject ***parentIndexArray;
-
-	parentIndexArray =3D (DumpableObject ***)
-		pg_malloc0(getMaxDumpId() * sizeof(DumpableObject **));
 =

 	for (i =3D 0; i < numTables; i++)
 	{
-		TableInfo  *parenttbl;
 		IndexAttachInfo *attachinfo;
 =

 		if (!tblinfo[i].ispartition || tblinfo[i].numParents =3D=3D 0)
 			continue;
 =

 		Assert(tblinfo[i].numParents =3D=3D 1);
-		parenttbl =3D tblinfo[i].parents[0];
-
-		/*
-		 * We need access to each parent table's index list, but there is no
-		 * index to cover them outside of this function.  To avoid having to
-		 * sort every parent table's indexes each time we come across each of
-		 * its partitions, create an indexed array for each parent the first
-		 * time it is required.
-		 */
-		if (parentIndexArray[parenttbl->dobj.dumpId] =3D=3D NULL)
-			parentIndexArray[parenttbl->dobj.dumpId] =3D
-				buildIndexArray(parenttbl->indexes,
-								parenttbl->numIndexes,
-								sizeof(IndxInfo));
 =

 		attachinfo =3D (IndexAttachInfo *)
 			pg_malloc0(tblinfo[i].numIndexes * sizeof(IndexAttachInfo));
@@ -414,9 +395,7 @@ flagInhIndexes(Archive *fout, TableInfo tblinfo[], int=
 numTables)
 			if (index->parentidx =3D=3D 0)
 				continue;
 =

-			parentidx =3D findIndexByOid(index->parentidx,
-									   parentIndexArray[parenttbl->dobj.dumpId],
-									   parenttbl->numIndexes);
+			parentidx =3D findIndexByOid(index->parentidx);
 			if (parentidx =3D=3D NULL)
 				continue;
 =

@@ -457,11 +436,6 @@ flagInhIndexes(Archive *fout, TableInfo tblinfo[], in=
t numTables)
 			k++;
 		}
 	}
-
-	for (i =3D 0; i < numTables; i++)
-		if (parentIndexArray[i])
-			pg_free(parentIndexArray[i]);
-	pg_free(parentIndexArray);
 }
 =

 /* flagInhAttrs -
@@ -596,7 +570,7 @@ flagInhAttrs(DumpOptions *dopt, TableInfo *tblinfo, in=
t numTables)
 /*
  * AssignDumpId
  *		Given a newly-created dumpable object, assign a dump ID,
- *		and enter the object into the lookup table.
+ *		and enter the object into the lookup tables.
  *
  * The caller is expected to have filled in objType and catId,
  * but not any of the other standard fields of a DumpableObject.
@@ -615,6 +589,7 @@ AssignDumpId(DumpableObject *dobj)
 	dobj->nDeps =3D 0;
 	dobj->allocDeps =3D 0;
 =

+	/* Add object to dumpIdMap[], enlarging that array if need be */
 	while (dobj->dumpId >=3D allocedDumpIds)
 	{
 		int			newAlloc;
@@ -637,8 +612,25 @@ AssignDumpId(DumpableObject *dobj)
 	}
 	dumpIdMap[dobj->dumpId] =3D dobj;
 =

-	/* mark catalogIdMap invalid, but don't rebuild it yet */
-	catalogIdMapValid =3D false;
+	/* If it has a valid CatalogId, enter it into the hash table */
+	if (OidIsValid(dobj->catId.tableoid))
+	{
+		CatalogIdMapEntry *entry;
+		bool		found;
+
+		/* Initialize CatalogId hash table if not done yet */
+		if (catalogIdHash =3D=3D NULL)
+			catalogIdHash =3D catalogid_create(CATALOGIDHASH_INITIAL_SIZE, NULL);
+
+		entry =3D catalogid_insert(catalogIdHash, dobj->catId, &found);
+		if (!found)
+		{
+			entry->dobj =3D NULL;
+			entry->ext =3D NULL;
+		}
+		Assert(entry->dobj =3D=3D NULL);
+		entry->dobj =3D dobj;
+	}
 }
 =

 /*
@@ -679,140 +671,19 @@ findObjectByDumpId(DumpId dumpId)
  * Find a DumpableObject by catalog ID
  *
  * Returns NULL for unknown ID
- *
- * We use binary search in a sorted list that is built on first call.
- * If AssignDumpId() and findObjectByCatalogId() calls were freely interm=
ixed,
- * the code would work, but possibly be very slow.  In the current usage
- * pattern that does not happen, indeed we build the list at most twice.
  */
 DumpableObject *
 findObjectByCatalogId(CatalogId catalogId)
 {
-	DumpableObject **low;
-	DumpableObject **high;
-
-	if (!catalogIdMapValid)
-	{
-		if (catalogIdMap)
-			free(catalogIdMap);
-		getDumpableObjects(&catalogIdMap, &numCatalogIds);
-		if (numCatalogIds > 1)
-			qsort((void *) catalogIdMap, numCatalogIds,
-				  sizeof(DumpableObject *), DOCatalogIdCompare);
-		catalogIdMapValid =3D true;
-	}
-
-	/*
-	 * We could use bsearch() here, but the notational cruft of calling
-	 * bsearch is nearly as bad as doing it ourselves; and the generalized
-	 * bsearch function is noticeably slower as well.
-	 */
-	if (numCatalogIds <=3D 0)
-		return NULL;
-	low =3D catalogIdMap;
-	high =3D catalogIdMap + (numCatalogIds - 1);
-	while (low <=3D high)
-	{
-		DumpableObject **middle;
-		int			difference;
-
-		middle =3D low + (high - low) / 2;
-		/* comparison must match DOCatalogIdCompare, below */
-		difference =3D oidcmp((*middle)->catId.oid, catalogId.oid);
-		if (difference =3D=3D 0)
-			difference =3D oidcmp((*middle)->catId.tableoid, catalogId.tableoid);
-		if (difference =3D=3D 0)
-			return *middle;
-		else if (difference < 0)
-			low =3D middle + 1;
-		else
-			high =3D middle - 1;
-	}
-	return NULL;
-}
-
-/*
- * Find a DumpableObject by OID, in a pre-sorted array of one type of obj=
ect
- *
- * Returns NULL for unknown OID
- */
-static DumpableObject *
-findObjectByOid(Oid oid, DumpableObject **indexArray, int numObjs)
-{
-	DumpableObject **low;
-	DumpableObject **high;
+	CatalogIdMapEntry *entry;
 =

-	/*
-	 * This is the same as findObjectByCatalogId except we assume we need no=
t
-	 * look at table OID because the objects are all the same type.
-	 *
-	 * We could use bsearch() here, but the notational cruft of calling
-	 * bsearch is nearly as bad as doing it ourselves; and the generalized
-	 * bsearch function is noticeably slower as well.
-	 */
-	if (numObjs <=3D 0)
-		return NULL;
-	low =3D indexArray;
-	high =3D indexArray + (numObjs - 1);
-	while (low <=3D high)
-	{
-		DumpableObject **middle;
-		int			difference;
-
-		middle =3D low + (high - low) / 2;
-		difference =3D oidcmp((*middle)->catId.oid, oid);
-		if (difference =3D=3D 0)
-			return *middle;
-		else if (difference < 0)
-			low =3D middle + 1;
-		else
-			high =3D middle - 1;
-	}
-	return NULL;
-}
-
-/*
- * Build an index array of DumpableObject pointers, sorted by OID
- */
-static DumpableObject **
-buildIndexArray(void *objArray, int numObjs, Size objSize)
-{
-	DumpableObject **ptrs;
-	int			i;
+	if (catalogIdHash =3D=3D NULL)
+		return NULL;			/* no objects exist yet */
 =

-	if (numObjs <=3D 0)
+	entry =3D catalogid_lookup(catalogIdHash, catalogId);
+	if (entry =3D=3D NULL)
 		return NULL;
-
-	ptrs =3D (DumpableObject **) pg_malloc(numObjs * sizeof(DumpableObject *=
));
-	for (i =3D 0; i < numObjs; i++)
-		ptrs[i] =3D (DumpableObject *) ((char *) objArray + i * objSize);
-
-	/* We can use DOCatalogIdCompare to sort since its first key is OID */
-	if (numObjs > 1)
-		qsort((void *) ptrs, numObjs, sizeof(DumpableObject *),
-			  DOCatalogIdCompare);
-
-	return ptrs;
-}
-
-/*
- * qsort comparator for pointers to DumpableObjects
- */
-static int
-DOCatalogIdCompare(const void *p1, const void *p2)
-{
-	const DumpableObject *obj1 =3D *(DumpableObject *const *) p1;
-	const DumpableObject *obj2 =3D *(DumpableObject *const *) p2;
-	int			cmpval;
-
-	/*
-	 * Compare OID first since it's usually unique, whereas there will only =
be
-	 * a few distinct values of tableoid.
-	 */
-	cmpval =3D oidcmp(obj1->catId.oid, obj2->catId.oid);
-	if (cmpval =3D=3D 0)
-		cmpval =3D oidcmp(obj1->catId.tableoid, obj2->catId.tableoid);
-	return cmpval;
+	return entry->dobj;
 }
 =

 /*
@@ -886,119 +757,169 @@ removeObjectDependency(DumpableObject *dobj, DumpI=
d refId)
 =

 /*
  * findTableByOid
- *	  finds the entry (in tblinfo) of the table with the given oid
+ *	  finds the DumpableObject for the table with the given oid
  *	  returns NULL if not found
  */
 TableInfo *
 findTableByOid(Oid oid)
 {
-	return (TableInfo *) findObjectByOid(oid, tblinfoindex, numTables);
+	CatalogId	catId;
+	DumpableObject *dobj;
+
+	catId.tableoid =3D RelationRelationId;
+	catId.oid =3D oid;
+	dobj =3D findObjectByCatalogId(catId);
+	Assert(dobj =3D=3D NULL || dobj->objType =3D=3D DO_TABLE);
+	return (TableInfo *) dobj;
+}
+
+/*
+ * findIndexByOid
+ *	  finds the DumpableObject for the index with the given oid
+ *	  returns NULL if not found
+ */
+static IndxInfo *
+findIndexByOid(Oid oid)
+{
+	CatalogId	catId;
+	DumpableObject *dobj;
+
+	catId.tableoid =3D RelationRelationId;
+	catId.oid =3D oid;
+	dobj =3D findObjectByCatalogId(catId);
+	Assert(dobj =3D=3D NULL || dobj->objType =3D=3D DO_INDEX);
+	return (IndxInfo *) dobj;
 }
 =

 /*
  * findTypeByOid
- *	  finds the entry (in typinfo) of the type with the given oid
+ *	  finds the DumpableObject for the type with the given oid
  *	  returns NULL if not found
  */
 TypeInfo *
 findTypeByOid(Oid oid)
 {
-	return (TypeInfo *) findObjectByOid(oid, typinfoindex, numTypes);
+	CatalogId	catId;
+
+	catId.tableoid =3D TypeRelationId;
+	catId.oid =3D oid;
+	return (TypeInfo *) findObjectByCatalogId(catId);
 }
 =

 /*
  * findFuncByOid
- *	  finds the entry (in funinfo) of the function with the given oid
+ *	  finds the DumpableObject for the function with the given oid
  *	  returns NULL if not found
  */
 FuncInfo *
 findFuncByOid(Oid oid)
 {
-	return (FuncInfo *) findObjectByOid(oid, funinfoindex, numFuncs);
+	CatalogId	catId;
+
+	catId.tableoid =3D ProcedureRelationId;
+	catId.oid =3D oid;
+	return (FuncInfo *) findObjectByCatalogId(catId);
 }
 =

 /*
  * findOprByOid
- *	  finds the entry (in oprinfo) of the operator with the given oid
+ *	  finds the DumpableObject for the operator with the given oid
  *	  returns NULL if not found
  */
 OprInfo *
 findOprByOid(Oid oid)
 {
-	return (OprInfo *) findObjectByOid(oid, oprinfoindex, numOperators);
+	CatalogId	catId;
+
+	catId.tableoid =3D OperatorRelationId;
+	catId.oid =3D oid;
+	return (OprInfo *) findObjectByCatalogId(catId);
 }
 =

 /*
  * findCollationByOid
- *	  finds the entry (in collinfo) of the collation with the given oid
+ *	  finds the DumpableObject for the collation with the given oid
  *	  returns NULL if not found
  */
 CollInfo *
 findCollationByOid(Oid oid)
 {
-	return (CollInfo *) findObjectByOid(oid, collinfoindex, numCollations);
+	CatalogId	catId;
+
+	catId.tableoid =3D CollationRelationId;
+	catId.oid =3D oid;
+	return (CollInfo *) findObjectByCatalogId(catId);
 }
 =

 /*
  * findNamespaceByOid
- *	  finds the entry (in nspinfo) of the namespace with the given oid
+ *	  finds the DumpableObject for the namespace with the given oid
  *	  returns NULL if not found
  */
 NamespaceInfo *
 findNamespaceByOid(Oid oid)
 {
-	return (NamespaceInfo *) findObjectByOid(oid, nspinfoindex, numNamespace=
s);
+	CatalogId	catId;
+
+	catId.tableoid =3D NamespaceRelationId;
+	catId.oid =3D oid;
+	return (NamespaceInfo *) findObjectByCatalogId(catId);
 }
 =

 /*
  * findExtensionByOid
- *	  finds the entry (in extinfo) of the extension with the given oid
+ *	  finds the DumpableObject for the extension with the given oid
  *	  returns NULL if not found
  */
 ExtensionInfo *
 findExtensionByOid(Oid oid)
 {
-	return (ExtensionInfo *) findObjectByOid(oid, extinfoindex, numExtension=
s);
+	CatalogId	catId;
+
+	catId.tableoid =3D ExtensionRelationId;
+	catId.oid =3D oid;
+	return (ExtensionInfo *) findObjectByCatalogId(catId);
 }
 =

 /*
  * findPublicationByOid
- *	  finds the entry (in pubinfo) of the publication with the given oid
+ *	  finds the DumpableObject for the publication with the given oid
  *	  returns NULL if not found
  */
 PublicationInfo *
 findPublicationByOid(Oid oid)
 {
-	return (PublicationInfo *) findObjectByOid(oid, pubinfoindex, numPublica=
tions);
-}
+	CatalogId	catId;
 =

-/*
- * findIndexByOid
- *		find the entry of the index with the given oid
- *
- * This one's signature is different from the previous ones because we la=
ck a
- * global array of all indexes, so caller must pass their array as argume=
nt.
- */
-static IndxInfo *
-findIndexByOid(Oid oid, DumpableObject **idxinfoindex, int numIndexes)
-{
-	return (IndxInfo *) findObjectByOid(oid, idxinfoindex, numIndexes);
+	catId.tableoid =3D PublicationRelationId;
+	catId.oid =3D oid;
+	return (PublicationInfo *) findObjectByCatalogId(catId);
 }
 =

+
 /*
- * setExtensionMembership
- *	  accept and save data about which objects belong to extensions
+ * recordExtensionMembership
+ *	  Record that the object identified by the given catalog ID
+ *	  belongs to the given extension
  */
 void
-setExtensionMembership(ExtensionMemberId *extmems, int nextmems)
+recordExtensionMembership(CatalogId catId, ExtensionInfo *ext)
 {
-	/* Sort array in preparation for binary searches */
-	if (nextmems > 1)
-		qsort((void *) extmems, nextmems, sizeof(ExtensionMemberId),
-			  ExtensionMemberIdCompare);
-	/* And save */
-	extmembers =3D extmems;
-	numextmembers =3D nextmems;
+	CatalogIdMapEntry *entry;
+	bool		found;
+
+	/* CatalogId hash table must exist, if we have an ExtensionInfo */
+	Assert(catalogIdHash !=3D NULL);
+
+	/* Add reference to CatalogId hash */
+	entry =3D catalogid_insert(catalogIdHash, catId, &found);
+	if (!found)
+	{
+		entry->dobj =3D NULL;
+		entry->ext =3D NULL;
+	}
+	Assert(entry->ext =3D=3D NULL);
+	entry->ext =3D ext;
 }
 =

 /*
@@ -1008,56 +929,15 @@ setExtensionMembership(ExtensionMemberId *extmems, =
int nextmems)
 ExtensionInfo *
 findOwningExtension(CatalogId catalogId)
 {
-	ExtensionMemberId *low;
-	ExtensionMemberId *high;
+	CatalogIdMapEntry *entry;
 =

-	/*
-	 * We could use bsearch() here, but the notational cruft of calling
-	 * bsearch is nearly as bad as doing it ourselves; and the generalized
-	 * bsearch function is noticeably slower as well.
-	 */
-	if (numextmembers <=3D 0)
-		return NULL;
-	low =3D extmembers;
-	high =3D extmembers + (numextmembers - 1);
-	while (low <=3D high)
-	{
-		ExtensionMemberId *middle;
-		int			difference;
-
-		middle =3D low + (high - low) / 2;
-		/* comparison must match ExtensionMemberIdCompare, below */
-		difference =3D oidcmp(middle->catId.oid, catalogId.oid);
-		if (difference =3D=3D 0)
-			difference =3D oidcmp(middle->catId.tableoid, catalogId.tableoid);
-		if (difference =3D=3D 0)
-			return middle->ext;
-		else if (difference < 0)
-			low =3D middle + 1;
-		else
-			high =3D middle - 1;
-	}
-	return NULL;
-}
-
-/*
- * qsort comparator for ExtensionMemberIds
- */
-static int
-ExtensionMemberIdCompare(const void *p1, const void *p2)
-{
-	const ExtensionMemberId *obj1 =3D (const ExtensionMemberId *) p1;
-	const ExtensionMemberId *obj2 =3D (const ExtensionMemberId *) p2;
-	int			cmpval;
+	if (catalogIdHash =3D=3D NULL)
+		return NULL;			/* no objects exist yet */
 =

-	/*
-	 * Compare OID first since it's usually unique, whereas there will only =
be
-	 * a few distinct values of tableoid.
-	 */
-	cmpval =3D oidcmp(obj1->catId.oid, obj2->catId.oid);
-	if (cmpval =3D=3D 0)
-		cmpval =3D oidcmp(obj1->catId.tableoid, obj2->catId.tableoid);
-	return cmpval;
+	entry =3D catalogid_lookup(catalogIdHash, catalogId);
+	if (entry =3D=3D NULL)
+		return NULL;
+	return entry->ext;
 }
 =

 =

diff --git a/src/bin/pg_dump/pg_backup.h b/src/bin/pg_dump/pg_backup.h
index 3c1cd858a8..6af10a85a2 100644
--- a/src/bin/pg_dump/pg_backup.h
+++ b/src/bin/pg_dump/pg_backup.h
@@ -236,6 +236,7 @@ typedef struct Archive
 =

 typedef struct
 {
+	/* Note: this struct must not contain any unused bytes */
 	Oid			tableoid;
 	Oid			oid;
 } CatalogId;
diff --git a/src/bin/pg_dump/pg_dump.c b/src/bin/pg_dump/pg_dump.c
index ed8ed2f266..948615a5b9 100644
--- a/src/bin/pg_dump/pg_dump.c
+++ b/src/bin/pg_dump/pg_dump.c
@@ -17901,12 +17901,10 @@ getExtensionMembership(Archive *fout, ExtensionI=
nfo extinfo[],
 	PQExpBuffer query;
 	PGresult   *res;
 	int			ntups,
-				nextmembers,
 				i;
 	int			i_classid,
 				i_objid,
 				i_refobjid;
-	ExtensionMemberId *extmembers;
 	ExtensionInfo *ext;
 =

 	/* Nothing to do if no extensions */
@@ -17931,12 +17929,7 @@ getExtensionMembership(Archive *fout, ExtensionIn=
fo extinfo[],
 	i_objid =3D PQfnumber(res, "objid");
 	i_refobjid =3D PQfnumber(res, "refobjid");
 =

-	extmembers =3D (ExtensionMemberId *) pg_malloc(ntups * sizeof(ExtensionM=
emberId));
-	nextmembers =3D 0;
-
 	/*
-	 * Accumulate data into extmembers[].
-	 *
 	 * Since we ordered the SELECT by referenced ID, we can expect that
 	 * multiple entries for the same extension will appear together; this
 	 * saves on searches.
@@ -17963,16 +17956,11 @@ getExtensionMembership(Archive *fout, ExtensionI=
nfo extinfo[],
 			continue;
 		}
 =

-		extmembers[nextmembers].catId =3D objId;
-		extmembers[nextmembers].ext =3D ext;
-		nextmembers++;
+		recordExtensionMembership(objId, ext);
 	}
 =

 	PQclear(res);
 =

-	/* Remember the data for use later */
-	setExtensionMembership(extmembers, nextmembers);
-
 	destroyPQExpBuffer(query);
 }
 =

diff --git a/src/bin/pg_dump/pg_dump.h b/src/bin/pg_dump/pg_dump.h
index 29af845ece..cc55e598ec 100644
--- a/src/bin/pg_dump/pg_dump.h
+++ b/src/bin/pg_dump/pg_dump.h
@@ -647,16 +647,6 @@ typedef struct _SubscriptionInfo
 	char	   *subpublications;
 } SubscriptionInfo;
 =

-/*
- * We build an array of these with an entry for each object that is an
- * extension member according to pg_depend.
- */
-typedef struct _extensionMemberId
-{
-	CatalogId	catId;			/* tableoid+oid of some member object */
-	ExtensionInfo *ext;			/* owning extension */
-} ExtensionMemberId;
-
 /*
  *	common utility functions
  */
@@ -682,7 +672,7 @@ extern NamespaceInfo *findNamespaceByOid(Oid oid);
 extern ExtensionInfo *findExtensionByOid(Oid oid);
 extern PublicationInfo *findPublicationByOid(Oid oid);
 =

-extern void setExtensionMembership(ExtensionMemberId *extmems, int nextme=
ms);
+extern void recordExtensionMembership(CatalogId catId, ExtensionInfo *ext=
);
 extern ExtensionInfo *findOwningExtension(CatalogId catalogId);
 =

 extern void parseOidArray(const char *str, Oid *array, int arraysize);

------- =_aaaaaaaaaa0--