8000 Fix O(N^2) behavior in pg_dump for large numbers of owned sequences. · jandas/postgres@b77da19 · GitHub
[go: up one dir, main page]
Skip to content

Commit b77da19

Browse files
tglsfdctglsfdc
committed
Fix O(N^2) behavior in pg_dump for large numbers of owned sequences.
The loop that matched owned sequences to their owning tables required time proportional to number of owned sequences times number of tables; although this work was only expended in selective-dump situations, which is probably why the issue wasn't recognized long since. Refactor slightly so that we can perform this work after the index array for findTableByOid has been set up, reducing the time to O(M log N). Per gripe from Mike Roest. Since this is a longstanding performance bug, backpatch to all supported versions.
1 parent 6205bb6 commit b77da19

File tree

3 files changed

+27
-18
lines changed

3 files changed

+27
-18
lines changed

‎src/bin/pg_dump/common.c

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -126,6 +126,9 @@ getSchemaData(int *numTablesPtr)
126126
tblinfo = getTables(&numTables);
127127
tblinfoindex = buildIndexArray(tblinfo, numTables, sizeof(TableInfo));
128128

129+
/* Do this after we've built tblinfoindex */
130+
getOwnedSeqs(tblinfo, numTables);
131+
129132
if (g_verbose)
130133
write_msg(NULL, "reading user-defined functions\n");
131134
funinfo = getFuncs(&numFuncs);

‎src/bin/pg_dump/pg_dump.c

Lines changed: 23 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -3856,38 +3856,43 @@ getTables(int *numTables)
38563856

38573857
PQclear(res);
38583858

3859+
destroyPQExpBuffer(query);
3860+
3861+
return tblinfo;
3862+
}
3863+
3864+
/*
3865+
* getOwnedSeqs
3866+
* identify owned sequences and mark them as dumpable if owning table is
3867+
*
3868+
* We used to do this in getTables(), but it's better to do it after the
3869+
* index used by findTableByOid() has been set up.
3870+
*/
3871+
void
3872+
getOwnedSeqs(TableInfo tblinfo[], int numTables)
3873+
{
3874+
int i;
3875+
38593876
/*
38603877
* Force sequences that are "owned" by table columns to be dumped whenever
38613878
* their owning table is being dumped.
38623879
*/
3863-
for (i = 0; i < ntups; i++)
3880+
for (i = 0; i < numTables; i++)
38643881
{
38653882
TableInfo *seqinfo = &tblinfo[i];
3866-
int j;
3883+
TableInfo *owning_tab;
38673884

38683885
if (!OidIsValid(seqinfo->owning_tab))
38693886
continue; /* not an owned sequence */
38703887
if (seqinfo->dobj.dump)
38713888
continue; /* no need to search */
3872-
3873-
/* can't use findTableByOid yet, unfortunately */
3874-
for (j = 0; j < ntups; j++)
3889+
owning_tab = findTableByOid(seqinfo->owning_tab);
3890+
if (owning_tab && owning_tab->dobj.dump)
38753891
{
3876-
if (tblinfo[j].dobj.catId.oid == seqinfo->owning_tab)
3877-
{
3878-
if (tblinfo[j].dobj.dump)
3879-
{
3880-
seqinfo->interesting = true;
3881-
seqinfo->dobj.dump = true;
3882-
}
3883-
break;
3884-
}
3892+
seqinfo->interesting = true;
3893+
seqinfo->dobj.dump = true;
38853894
}
38863895
}
3887-
3888-
destroyPQExpBuffer(query);
3889-
3890-
return tblinfo;
38913896
}
38923897

38933898
/*

‎src/bin/pg_dump/pg_dump.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -514,6 +514,7 @@ extern OpclassInfo *getOpclasses(int *numOpclasses);
514514
extern OpfamilyInfo *getOpfamilies(int *numOpfamilies);
515515
extern ConvInfo *getConversions(int *numConversions);
516516
extern TableInfo *getTables(int *numTables);
517+
extern void getOwnedSeqs(TableInfo tblinfo[], int numTables);
517518
extern InhInfo *getInherits(int *numInherits);
518519
extern void getIndexes(TableInfo tblinfo[], int numTables);
519520
extern void getConstraints(TableInfo tblinfo[], int numTables);

0 commit comments

Comments
 (0)
0