pgsql: Fix O(N^2) behavior in pg_dump for large numbers of owned sequen

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-committers(at)postgresql(dot)org
Subject: pgsql: Fix O(N^2) behavior in pg_dump for large numbers of owned sequen
Date: 2012-03-31 18:43:07
Message-ID: E1SE3GV-0000r9-CY@gemulon.postgresql.org
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-committers

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.

Branch
------
REL8_4_STABLE

Details
-------
http://git.postgresql.org/pg/commitdiff/80c40f07eb31aa70d245a25b4a5b9ad1d010c431

Modified Files
--------------
src/bin/pg_dump/common.c | 3 +++
src/bin/pg_dump/pg_dump.c | 41 +++++++++++++++++++++++------------------
src/bin/pg_dump/pg_dump.h | 1 +
3 files changed, 27 insertions(+), 18 deletions(-)

Browse pgsql-committers by date

  From Date Subject
Next Message Tom Lane 2012-03-31 19:51:57 pgsql: Fix O(N^2) behavior in pg_dump when many objects are in dependen
Previous Message Tom Lane 2012-03-31 17:17:12 Re: [COMMITTERS] pgsql: Add PGDLLIMPORT to ScanKeywords and NumScanKeywords.