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

pgsql: Use binary search instead of brute-force scan infindNamespace()

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-committers(at)postgresql(dot)org
Subject: pgsql: Use binary search instead of brute-force scan infindNamespace()
Date: 2012-05-25 18:36:37
Message-ID: E1SXzNN-0007Bo-0C@gemulon.postgresql.org (view raw or flat)
Thread:
Lists: pgsql-committers
Use binary search instead of brute-force scan in findNamespace().

The previous coding presented a significant bottleneck when dumping
databases containing many thousands of schemas, since the total time
spent searching would increase roughly as O(N^2) in the number of objects.
Noted by Jeff Janes, though I rewrote his proposed patch to use the
existing findObjectByOid infrastructure.

Since this is a longstanding performance bug, backpatch to all supported
versions.

Branch
------
REL8_3_STABLE

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

Modified Files
--------------
src/bin/pg_dump/common.c  |   19 ++++++++++++++++---
src/bin/pg_dump/pg_dump.c |   39 +++++++++++++++++----------------------
src/bin/pg_dump/pg_dump.h |    1 +
3 files changed, 34 insertions(+), 25 deletions(-)

pgsql-committers by date

Next:From: Tom LaneDate: 2012-05-25 21:35:55
Subject: pgsql: Fix string truncation to be multibyte-aware in text_name andbpc
Previous:From: Tom LaneDate: 2012-05-25 18:36:36
Subject: pgsql: Use binary search instead of brute-force scan infindNamespace()

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