Skip to content

Commit 965d76f

Browse files
tglsfdctglsfdc
committed
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.
1 parent c676f83 commit 965d76f

File tree

3 files changed

+34
-25
lines changed

3 files changed

+34
-25
lines changed

‎src/bin/pg_dump/common.c

Lines changed: 16 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -50,14 +50,17 @@ static TableInfo *tblinfo;
5050
static TypeInfo *typinfo;
5151
static FuncInfo *funinfo;
5252
static OprInfo *oprinfo;
53+
static NamespaceInfo *nspinfo;
5354
static int numTables;
5455
static int numTypes;
5556
static int numFuncs;
5657
static int numOperators;
58+
static int numNamespaces;
5759
static DumpableObject **tblinfoindex;
5860
static DumpableObject **typinfoindex;
5961
static DumpableObject **funinfoindex;
6062
static DumpableObject **oprinfoindex;
63+
static DumpableObject **nspinfoindex;
6164

6265

6366
static void flagInhTables(TableInfo *tbinfo, int numTables,
@@ -78,7 +81,6 @@ static int strInArray(const char *pattern, char **arr, int arr_size);
7881
TableInfo *
7982
getSchemaData(int *numTablesPtr)
8083
{
81-
NamespaceInfo *nsinfo;
8284
AggInfo *agginfo;
8385
InhInfo *inhinfo;
8486
RuleInfo *ruleinfo;
@@ -94,7 +96,6 @@ getSchemaData(int *numTablesPtr)
9496
FdwInfo *fdwinfo;
9597
ForeignServerInfo *srvinfo;
9698
DefaultACLInfo *daclinfo;
97-
int numNamespaces;
9899
int numAggregates;
99100
int numInherits;
100101
int numRules;
@@ -113,7 +114,8 @@ getSchemaData(int *numTablesPtr)
113114

114115
if (g_verbose)
115116
write_msg(NULL, "reading schemas\n");
116-
nsinfo = getNamespaces(&numNamespaces);
117+
nspinfo = getNamespaces(&numNamespaces);
118+
nspinfoindex = buildIndexArray(nspinfo, numNamespaces, sizeof(NamespaceInfo));
117119

118120
/*
119121
* getTables should be done as soon as possible, so as to minimize the
@@ -714,6 +716,17 @@ findOprByOid(Oid oid)
714716
return (OprInfo *) findObjectByOid(oid, oprinfoindex, numOperators);
715717
}
716718

719+
/*
720+
* findNamespaceByOid
721+
* finds the entry (in nspinfo) of the namespace with the given oid
722+
* returns NULL if not found
723+
*/
724+
NamespaceInfo *
725+
findNamespaceByOid(Oid oid)
726+
{
727+
return (NamespaceInfo *) findObjectByOid(oid, nspinfoindex, numNamespaces);
728+
}
729+
717730

718731
/*
719732
* findParentsByOid

‎src/bin/pg_dump/pg_dump.c

Lines changed: 17 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -116,10 +116,6 @@ char g_comment_end[10];
116116

117117
static const CatalogId nilCatalogId = {0, 0};
118118

119-
/* these are to avoid passing around info for findNamespace() */
120-
static NamespaceInfo *g_namespaces;
121-
static int g_numNamespaces;
122-
123119
/* flags for various command-line long options */
124120
static int binary_upgrade = 0;
125121
static int disable_dollar_quoting = 0;
@@ -2408,8 +2404,7 @@ getNamespaces(int *numNamespaces)
24082404

24092405
selectDumpableNamespace(&nsinfo[1]);
24102406

2411-
g_namespaces = nsinfo;
2412-
g_numNamespaces = *numNamespaces = 2;
2407+
*numNamespaces = 2;
24132408

24142409
return nsinfo;
24152410
}
@@ -2462,8 +2457,7 @@ getNamespaces(int *numNamespaces)
24622457
PQclear(res);
24632458
destroyPQExpBuffer(query);
24642459

2465-
g_namespaces = nsinfo;
2466-
g_numNamespaces = *numNamespaces = ntups;
2460+
*numNamespaces = ntups;
24672461

24682462
return nsinfo;
24692463
}
@@ -2474,36 +2468,37 @@ getNamespaces(int *numNamespaces)
24742468
* getNamespaces
24752469
*
24762470
* NB: for pre-7.3 source database, we use object OID to guess whether it's
2477-
* a system object or not. In 7.3 and later there is no guessing.
2471+
* a system object or not. In 7.3 and later there is no guessing, and we
2472+
* don't use objoid at all.
24782473
*/
24792474
static NamespaceInfo *
24802475
findNamespace(Oid nsoid, Oid objoid)
24812476
{
2482-
int i;
2477+
NamespaceInfo *nsinfo;
24832478

24842479
if (g_fout->remoteVersion >= 70300)
24852480
{
2486-
for (i = 0; i < g_numNamespaces; i++)
2487-
{
2488-
NamespaceInfo *nsinfo = &g_namespaces[i];
2489-
2490-
if (nsoid == nsinfo->dobj.catId.oid)
2491-
return nsinfo;
2492-
}
2493-
write_msg(NULL, "schema with OID %u does not exist\n", nsoid);
2494-
exit_nicely();
2481+
nsinfo = findNamespaceByOid(nsoid);
24952482
}
24962483
else
24972484
{
2498-
/* This code depends on the layout set up by getNamespaces. */
2485+
/* This code depends on the dummy objects set up by getNamespaces. */
2486+
Oid i;
2487+
24992488
if (objoid > g_last_builtin_oid)
25002489
i = 0; /* user object */
25012490
else
25022491
i = 1; /* system object */
2503-
return &g_namespaces[i];
2492+
nsinfo = findNamespaceByOid(i);
25042493
}
25052494

2506-
return NULL; /* keep compiler quiet */
2495+
if (nsinfo == NULL)
2496+
{
2497+
write_msg(NULL, "schema with OID %u does not exist\n", nsoid);
2498+
exit_nicely();
2499+
}
2500+
2501+
return nsinfo;
25072502
}
25082503

25092504
/*

‎src/bin/pg_dump/pg_dump.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -482,6 +482,7 @@ extern TableInfo *findTableByOid(Oid oid);
482482
extern TypeInfo *findTypeByOid(Oid oid);
483483
extern FuncInfo *findFuncByOid(Oid oid);
484484
extern OprInfo *findOprByOid(Oid oid);
485+
extern NamespaceInfo *findNamespaceByOid(Oid oid);
485486

486487
extern void simple_oid_list_append(SimpleOidList *list, Oid val);
487488
extern void simple_string_list_append(SimpleStringList *list, const char *val);

0 commit comments

Comments
 (0)