Skip site navigation (1) Skip section navigation (2)

pgsql: Fix O(N^2) behavior in pg_dump when many objects are independen

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 when many objects are independen
Date: 2012-03-31 19:51:57
Message-ID: E1SE4L7-0001s3-5B@gemulon.postgresql.org (view raw or flat)
Thread:
Lists: pgsql-committers
Fix O(N^2) behavior in pg_dump when many objects are in dependency loops.

Combining the loop workspace with the record of already-processed objects
might have been a cute trick, but it behaves horridly if there are many
dependency loops to repair: the time spent in the first step of findLoop()
grows as O(N^2).  Instead use a separate flag array indexed by dump ID,
which we can check in constant time.  The length of the workspace array
is now never more than the actual length of a dependency chain, which
should be reasonably short in all cases of practical interest.  The code
is noticeably easier to understand this way, too.

Per gripe from Mike Roest.  Since this is a longstanding performance bug,
backpatch to all supported versions.

Branch
------
master

Details
-------
http://git.postgresql.org/pg/commitdiff/d5881c036a913d31a5b0f56519cce76ca3b3e587

Modified Files
--------------
src/bin/pg_dump/pg_dump_sort.c |  117 ++++++++++++++++++++--------------------
1 files changed, 58 insertions(+), 59 deletions(-)

pgsql-committers by date

Next:From: Peter EisentrautDate: 2012-04-01 23:40:33
Subject: pgsql: Fix recently introduced typo in NLS file lists
Previous:From: Tom LaneDate: 2012-03-31 18:43:07
Subject: pgsql: Fix O(N^2) behavior in pg_dump for large numbers of ownedsequen

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group