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

pgsql: Limit the number of rel sets considered inconsider_index_join_o

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-committers(at)postgresql(dot)org
Subject: pgsql: Limit the number of rel sets considered inconsider_index_join_o
Date: 2012-11-01 18:09:01
Message-ID: E1TTzCP-0006wH-LU@gemulon.postgresql.org (view raw or flat)
Thread:
Lists: pgsql-committers
Limit the number of rel sets considered in consider_index_join_outer_rels.

In bug #7626, Brian Dunavant exposes a performance problem created by
commit 3b8968f25232ad09001bf35ab4cc59f5a501193e: that commit attempted to
consider *all* possible combinations of indexable join clauses, but if said
clauses join to enough different relations, there's an exponential increase
in the number of outer-relation sets considered.

In Brian's example, all the clauses come from the same equivalence class,
which means it's redundant to use more than one of them in an indexscan
anyway.  So we can prevent the problem in this class of cases (which is
probably the majority of real examples) by rejecting combinations that
would only serve to add a known-redundant clause.

But that still leaves us exposed to exponential growth of planning time
when the query has a lot of non-equivalence join clauses that are usable
with the same index.  I chose to prevent such cases by setting an upper
limit on the number of relation sets considered, equal to ten times the
number of index clauses considered so far.  (This sliding limit still
allows new relsets to be added on as we move to additional index columns,
which is probably more important than considering even more combinations of
clauses for the previous column.)  This should keep the amount of work done
roughly linear rather than exponential in the apparent query complexity.
This part of the fix is pretty ad-hoc; but without a clearer idea of
real-world cases for which this would result in markedly inferior plans,
it's hard to see how to do better.

Branch
------
master

Details
-------
http://git.postgresql.org/pg/commitdiff/19e36477b383c62009361b2221cb51e9f63132d9

Modified Files
--------------
src/backend/optimizer/path/indxpath.c |   64 +++++++++++++++++++++++++++++++--
1 files changed, 61 insertions(+), 3 deletions(-)

pgsql-committers by date

Next:From: Tom LaneDate: 2012-11-01 23:49:20
Subject: pgsql: Fix bogus handling of $(X) (i.e.,".exe") in isolationtester Mak
Previous:From: Peter EisentrautDate: 2012-11-01 04:05:33
Subject: Re: [COMMITTERS] pgsql: Preserve intermediate .c files in coverage mode

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