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.

diff --git a/src/bin/pg_dump/common.c b/src/bin/pg_dump/common.c
index aae1e481eb6dc50c1f9afa0876509cd1a6230a65..48a97392e14081296a05a564a75f831fd89aaa8b 100644 (file)
--- a/src/bin/pg_dump/common.c
+++ b/src/bin/pg_dump/common.c
@@ -126,6 +126,9 @@ getSchemaData(int *numTablesPtr)
    tblinfo = getTables(&numTables);
    tblinfoindex = buildIndexArray(tblinfo, numTables, sizeof(TableInfo));
 
+   /* Do this after we've built tblinfoindex */
+   getOwnedSeqs(tblinfo, numTables);
+
    if (g_verbose)
        write_msg(NULL, "reading user-defined functions\n");
    funinfo = getFuncs(&numFuncs);

diff --git a/src/bin/pg_dump/pg_dump.c b/src/bin/pg_dump/pg_dump.c
index 0c243841e51d8432bf0906e4d43c6569b1936681..b518280130f34d962819be4ad1180405a1309c40 100644 (file)
--- a/src/bin/pg_dump/pg_dump.c
+++ b/src/bin/pg_dump/pg_dump.c
@@ -3856,38 +3856,43 @@ getTables(int *numTables)
 
    PQclear(res);
 
+   destroyPQExpBuffer(query);
+
+   return tblinfo;
+}
+
+/*
+ * getOwnedSeqs
+ *   identify owned sequences and mark them as dumpable if owning table is
+ *
+ * We used to do this in getTables(), but it's better to do it after the
+ * index used by findTableByOid() has been set up.
+ */
+void
+getOwnedSeqs(TableInfo tblinfo[], int numTables)
+{
+   int         i;
+
    /*
     * Force sequences that are "owned" by table columns to be dumped whenever
     * their owning table is being dumped.
     */
-   for (i = 0; i < ntups; i++)
+   for (i = 0; i < numTables; i++)
    {
        TableInfo  *seqinfo = &tblinfo[i];
-       int         j;
+       TableInfo  *owning_tab;
 
        if (!OidIsValid(seqinfo->owning_tab))
            continue;           /* not an owned sequence */
        if (seqinfo->dobj.dump)
            continue;           /* no need to search */
-
-       /* can't use findTableByOid yet, unfortunately */
-       for (j = 0; j < ntups; j++)
+       owning_tab = findTableByOid(seqinfo->owning_tab);
+       if (owning_tab && owning_tab->dobj.dump)
        {
-           if (tblinfo[j].dobj.catId.oid == seqinfo->owning_tab)
-           {
-               if (tblinfo[j].dobj.dump)
-               {
-                   seqinfo->interesting = true;
-                   seqinfo->dobj.dump = true;
-               }
-               break;
-           }
+           seqinfo->interesting = true;
+           seqinfo->dobj.dump = true;
        }
    }
-
-   destroyPQExpBuffer(query);
-
-   return tblinfo;
 }
 
 /*

diff --git a/src/bin/pg_dump/pg_dump.h b/src/bin/pg_dump/pg_dump.h
index 8e2575ffb45d48e0b9889763c3aee27751ebe170..5e57bd9b891f03fb4282d19ea6c9e39365b5c1d8 100644 (file)
--- a/src/bin/pg_dump/pg_dump.h
+++ b/src/bin/pg_dump/pg_dump.h
@@ -514,6 +514,7 @@ extern OpclassInfo *getOpclasses(int *numOpclasses);
 extern OpfamilyInfo *getOpfamilies(int *numOpfamilies);
 extern ConvInfo *getConversions(int *numConversions);
 extern TableInfo *getTables(int *numTables);
+extern void getOwnedSeqs(TableInfo tblinfo[], int numTables);
 extern InhInfo *getInherits(int *numInherits);
 extern void getIndexes(TableInfo tblinfo[], int numTables);
 extern void getConstraints(TableInfo tblinfo[], int numTables);