]> granicus.if.org Git - postgresql/commit
Fix O(N^2) behavior in pg_dump when many objects are in dependency loops.
authorTom Lane <tgl@sss.pgh.pa.us>
Sat, 31 Mar 2012 19:51:27 +0000 (15:51 -0400)
committerTom Lane <tgl@sss.pgh.pa.us>
Sat, 31 Mar 2012 19:51:27 +0000 (15:51 -0400)
commitb1be1294cc3b3fbccc05294b3f67180f53d63ef3
tree8ca6f76f179c53a8d6e7e7ff0ae959b52dfa8f38
parent55eb256789e43cc1b6113fe82efdc34a370aa8a2
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.
src/bin/pg_dump/pg_dump_sort.c