From 965d76f972bec5595e84a8e8567636cb3ba7a1f2 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Fri, 25 May 2012 14:35:47 -0400 Subject: [PATCH] Use binary search instead of brute-force scan in findNamespace(). The previous coding presented a significant bottleneck when dumping databases containing many thousands of schemas, since the total time spent searching would increase roughly as O(N^2) in the number of objects. Noted by Jeff Janes, though I rewrote his proposed patch to use the existing findObjectByOid infrastructure. Since this is a longstanding performance bug, backpatch to all supported versions. --- src/bin/pg_dump/common.c | 19 ++++++++++++++++--- src/bin/pg_dump/pg_dump.c | 39 +++++++++++++++++---------------------- src/bin/pg_dump/pg_dump.h | 1 + 3 files changed, 34 insertions(+), 25 deletions(-) diff --git a/src/bin/pg_dump/common.c b/src/bin/pg_dump/common.c index 48a97392e14..a27fd151c99 100644 --- a/src/bin/pg_dump/common.c +++ b/src/bin/pg_dump/common.c @@ -50,14 +50,17 @@ static TableInfo *tblinfo; static TypeInfo *typinfo; static FuncInfo *funinfo; static OprInfo *oprinfo; +static NamespaceInfo *nspinfo; static int numTables; static int numTypes; static int numFuncs; static int numOperators; +static int numNamespaces; static DumpableObject **tblinfoindex; static DumpableObject **typinfoindex; static DumpableObject **funinfoindex; static DumpableObject **oprinfoindex; +static DumpableObject **nspinfoindex; static void flagInhTables(TableInfo *tbinfo, int numTables, @@ -78,7 +81,6 @@ static int strInArray(const char *pattern, char **arr, int arr_size); TableInfo * getSchemaData(int *numTablesPtr) { - NamespaceInfo *nsinfo; AggInfo *agginfo; InhInfo *inhinfo; RuleInfo *ruleinfo; @@ -94,7 +96,6 @@ getSchemaData(int *numTablesPtr) FdwInfo *fdwinfo; ForeignServerInfo *srvinfo; DefaultACLInfo *daclinfo; - int numNamespaces; int numAggregates; int numInherits; int numRules; @@ -113,7 +114,8 @@ getSchemaData(int *numTablesPtr) if (g_verbose) write_msg(NULL, "reading schemas\n"); - nsinfo = getNamespaces(&numNamespaces); + nspinfo = getNamespaces(&numNamespaces); + nspinfoindex = buildIndexArray(nspinfo, numNamespaces, sizeof(NamespaceInfo)); /* * getTables should be done as soon as possible, so as to minimize the @@ -714,6 +716,17 @@ findOprByOid(Oid oid) return (OprInfo *) findObjectByOid(oid, oprinfoindex, numOperators); } +/* + * findNamespaceByOid + * finds the entry (in nspinfo) of the namespace with the given oid + * returns NULL if not found + */ +NamespaceInfo * +findNamespaceByOid(Oid oid) +{ + return (NamespaceInfo *) findObjectByOid(oid, nspinfoindex, numNamespaces); +} + /* * findParentsByOid diff --git a/src/bin/pg_dump/pg_dump.c b/src/bin/pg_dump/pg_dump.c index b518280130f..8f9c4301912 100644 --- a/src/bin/pg_dump/pg_dump.c +++ b/src/bin/pg_dump/pg_dump.c @@ -116,10 +116,6 @@ char g_comment_end[10]; static const CatalogId nilCatalogId = {0, 0}; -/* these are to avoid passing around info for findNamespace() */ -static NamespaceInfo *g_namespaces; -static int g_numNamespaces; - /* flags for various command-line long options */ static int binary_upgrade = 0; static int disable_dollar_quoting = 0; @@ -2408,8 +2404,7 @@ getNamespaces(int *numNamespaces) selectDumpableNamespace(&nsinfo[1]); - g_namespaces = nsinfo; - g_numNamespaces = *numNamespaces = 2; + *numNamespaces = 2; return nsinfo; } @@ -2462,8 +2457,7 @@ getNamespaces(int *numNamespaces) PQclear(res); destroyPQExpBuffer(query); - g_namespaces = nsinfo; - g_numNamespaces = *numNamespaces = ntups; + *numNamespaces = ntups; return nsinfo; } @@ -2474,36 +2468,37 @@ getNamespaces(int *numNamespaces) * getNamespaces * * NB: for pre-7.3 source database, we use object OID to guess whether it's - * a system object or not. In 7.3 and later there is no guessing. + * a system object or not. In 7.3 and later there is no guessing, and we + * don't use objoid at all. */ static NamespaceInfo * findNamespace(Oid nsoid, Oid objoid) { - int i; + NamespaceInfo *nsinfo; if (g_fout->remoteVersion >= 70300) { - for (i = 0; i < g_numNamespaces; i++) - { - NamespaceInfo *nsinfo = &g_namespaces[i]; - - if (nsoid == nsinfo->dobj.catId.oid) - return nsinfo; - } - write_msg(NULL, "schema with OID %u does not exist\n", nsoid); - exit_nicely(); + nsinfo = findNamespaceByOid(nsoid); } else { - /* This code depends on the layout set up by getNamespaces. */ + /* This code depends on the dummy objects set up by getNamespaces. */ + Oid i; + if (objoid > g_last_builtin_oid) i = 0; /* user object */ else i = 1; /* system object */ - return &g_namespaces[i]; + nsinfo = findNamespaceByOid(i); } - return NULL; /* keep compiler quiet */ + if (nsinfo == NULL) + { + write_msg(NULL, "schema with OID %u does not exist\n", nsoid); + exit_nicely(); + } + + return nsinfo; } /* diff --git a/src/bin/pg_dump/pg_dump.h b/src/bin/pg_dump/pg_dump.h index 5e57bd9b891..5858d545ff0 100644 --- a/src/bin/pg_dump/pg_dump.h +++ b/src/bin/pg_dump/pg_dump.h @@ -482,6 +482,7 @@ extern TableInfo *findTableByOid(Oid oid); extern TypeInfo *findTypeByOid(Oid oid); extern FuncInfo *findFuncByOid(Oid oid); extern OprInfo *findOprByOid(Oid oid); +extern NamespaceInfo *findNamespaceByOid(Oid oid); extern void simple_oid_list_append(SimpleOidList *list, Oid val); extern void simple_string_list_append(SimpleStringList *list, const char *val); -- 2.39.5