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

Re: pgsql: Eliminate some more O(N^2) behaviors in pg_dump/pg_restore.

From: Bruce Momjian <bruce(at)momjian(dot)us>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: pgsql-committers(at)postgresql(dot)org
Subject: Re: pgsql: Eliminate some more O(N^2) behaviors in pg_dump/pg_restore.
Date: 2012-05-30 00:55:25
Message-ID: 20120530005525.GM20260@momjian.us (view raw or flat)
Thread:
Lists: pgsql-committers
On Tue, May 29, 2012 at 12:38:51AM +0000, Tom Lane wrote:
> Eliminate some more O(N^2) behaviors in pg_dump/pg_restore.
> 
> This patch fixes three places (which AFAICT is all of them) where runtime
> was O(N^2) in the number of TOC entries, by using an index array to replace
> linear searches of the TOC list.  This performance issue is a bit less bad
> than those recently fixed, because it depends on the number of items dumped
> not the number in the source database, so the problem can be dodged by
> doing partial dumps.
> 
> The previous coding already had an instance of one of the two index arrays
> needed, but it was only calculated in parallel-restore cases; now we need
> it all the time.  I also chose to move the arrays into the ArchiveHandle
> data structure, to make this code a bit more ready for the day that we
> try to sling multiple ArchiveHandles around in pg_dump or pg_restore.
> 
> Since we still need some server-side work before pg_dump can really cope
> nicely with tens of thousands of tables, there's probably little point in
> back-patching.

Great, thanks.  This will help speed up pg_upgrade.

-- 
  Bruce Momjian  <bruce(at)momjian(dot)us>        http://momjian.us
  EnterpriseDB                             http://enterprisedb.com

  + It's impossible for everything to be true. +

In response to

pgsql-committers by date

Next:From: Tom LaneDate: 2012-05-30 03:22:29
Subject: pgsql: Rewrite --section option to decouple it from--schema-only/--dat
Previous:From: Simon RiggsDate: 2012-05-29 19:34:20
Subject: Re: Re: [COMMITTERS] pgsql: Send new protocol keepalive messages to standby servers.

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