Skip to content

Commit 73cc7d3

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 45ca31d commit 73cc7d3

File tree

3 files changed

+31
-23
lines changed

3 files changed

+31
-23
lines changed

‎src/bin/pg_dump/common.c

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -48,16 +48,19 @@ static TableInfo *tblinfo;
4848
static TypeInfo *typinfo;
4949
static FuncInfo *funinfo;
5050
static OprInfo *oprinfo;
51+
static NamespaceInfo *nspinfo;
5152
static int numTables;
5253
static int numTypes;
5354
static int numFuncs;
5455
static int numOperators;
5556
static int numCollations;
57+
static int numNamespaces;
5658
static DumpableObject **tblinfoindex;
5759
static DumpableObject **typinfoindex;
5860
static DumpableObject **funinfoindex;
5961
static DumpableObject **oprinfoindex;
6062
static DumpableObject **collinfoindex;
63+
static DumpableObject **nspinfoindex;
6164

6265

6366
static void flagInhTables(TableInfo *tbinfo, int numTables,
@@ -81,7 +84,6 @@ getSchemaData(Archive *fout, int *numTablesPtr)
8184
ExtensionInfo *extinfo;
8285
InhInfo *inhinfo;
8386
CollInfo *collinfo;
84-
int numNamespaces;
8587
int numExtensions;
8688
int numAggregates;
8789
int numInherits;
@@ -101,7 +103,8 @@ getSchemaData(Archive *fout, int *numTablesPtr)
101103

102104
if (g_verbose)
103105
write_msg(NULL, "reading schemas\n");
104-
getNamespaces(fout, &numNamespaces);
106+
nspinfo = getNamespaces(fout, &numNamespaces);
107+
nspinfoindex = buildIndexArray(nspinfo, numNamespaces, sizeof(NamespaceInfo));
105108

106109
/*
107110
* getTables should be done as soon as possible, so as to minimize the
@@ -732,6 +735,17 @@ findCollationByOid(Oid oid)
732735
return (CollInfo *) findObjectByOid(oid, collinfoindex, numCollations);
733736
}
734737

738+
/*
739+
* findNamespaceByOid
740+
* finds the entry (in nspinfo) of the namespace with the given oid
741+
* returns NULL if not found
742+
*/
743+
NamespaceInfo *
744+
findNamespaceByOid(Oid oid)
745+
{
746+
return (NamespaceInfo *) findObjectByOid(oid, nspinfoindex, numNamespaces);
747+
}
748+
735749

736750
/*
737751
* findParentsByOid

‎src/bin/pg_dump/pg_dump.c

Lines changed: 14 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -129,10 +129,6 @@ char g_comment_end[10];
129129

130130
static const CatalogId nilCatalogId = {0, 0};
131131

132-
/* these are to avoid passing around info for findNamespace() */
133-
static NamespaceInfo *g_namespaces;
134-
static int g_numNamespaces;
135-
136132
/* flags for various command-line long options */
137133
static int binary_upgrade = 0;
138134
static int disable_dollar_quoting = 0;
@@ -2595,8 +2591,7 @@ getNamespaces(Archive *fout, int *numNamespaces)
25952591

25962592
selectDumpableNamespace(&nsinfo[1]);
25972593

2598-
g_namespaces = nsinfo;
2599-
g_numNamespaces = *numNamespaces = 2;
2594+
*numNamespaces = 2;
26002595

26012596
return nsinfo;
26022597
}
@@ -2648,8 +2643,7 @@ getNamespaces(Archive *fout, int *numNamespaces)
26482643
PQclear(res);
26492644
destroyPQExpBuffer(query);
26502645

2651-
g_namespaces = nsinfo;
2652-
g_numNamespaces = *numNamespaces = ntups;
2646+
*numNamespaces = ntups;
26532647

26542648
return nsinfo;
26552649
}
@@ -2660,35 +2654,34 @@ getNamespaces(Archive *fout, int *numNamespaces)
26602654
* getNamespaces
26612655
*
26622656
* NB: for pre-7.3 source database, we use object OID to guess whether it's
2663-
* a system object or not. In 7.3 and later there is no guessing.
2657+
* a system object or not. In 7.3 and later there is no guessing, and we
2658+
* don't use objoid at all.
26642659
*/
26652660
static NamespaceInfo *
26662661
findNamespace(Archive *fout, Oid nsoid, Oid objoid)
26672662
{
2668-
int i;
2663+
NamespaceInfo *nsinfo;
26692664

26702665
if (fout->remoteVersion >= 70300)
26712666
{
2672-
for (i = 0; i < g_numNamespaces; i++)
2673-
{
2674-
NamespaceInfo *nsinfo = &g_namespaces[i];
2675-
2676-
if (nsoid == nsinfo->dobj.catId.oid)
2677-
return nsinfo;
2678-
}
2679-
exit_horribly(NULL, "schema with OID %u does not exist\n", nsoid);
2667+
nsinfo = findNamespaceByOid(nsoid);
26802668
}
26812669
else
26822670
{
2683-
/* This code depends on the layout set up by getNamespaces. */
2671+
/* This code depends on the dummy objects set up by getNamespaces. */
2672+
Oid i;
2673+
26842674
if (objoid > g_last_builtin_oid)
26852675
i = 0; /* user object */
26862676
else
26872677
i = 1; /* system object */
2688-
return &g_namespaces[i];
2678+
nsinfo = findNamespaceByOid(i);
26892679
}
26902680

2691-
return NULL; /* keep compiler quiet */
2681+
if (nsinfo == NULL)
2682+
exit_horribly(NULL, "schema with OID %u does not exist\n", nsoid);
2683+
2684+
return nsinfo;
26922685
}
26932686

26942687
/*

‎src/bin/pg_dump/pg_dump.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -511,6 +511,7 @@ extern TypeInfo *findTypeByOid(Oid oid);
511511
extern FuncInfo *findFuncByOid(Oid oid);
512512
extern OprInfo *findOprByOid(Oid oid);
513513
extern CollInfo *findCollationByOid(Oid oid);
514+
extern NamespaceInfo *findNamespaceByOid(Oid oid);
514515

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

0 commit comments

Comments
 (0)