Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Oct 30, 2012 at 5:57 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I looked into the complaint of unreasonable planner runtime in bug #7626,
>> http://archives.postgresql.org/pgsql-bugs/2012-10/msg00232.php
> You know, when I read this, my first thought was ... why is this an
> exponential relationship instead of a linear one?
Because it's considering *combinations* of outer relations for a
parameterized scan. For instance consider an index on t(a,b)
and a queryWHERE t.a = x.c1 AND t.b = y.c2
There are three different parameterized paths we could create: one
relying on x only, one relying on y only, one relying on both.
The one relying on y only is probably going to suck, if this is a
btree index, but at the level we're working at here that's not yet
apparent. The other two are definitely both worthy of consideration,
since it might or might not be worth it to join x and y first in order
to use both conditions in scanning t.
So in general, given join clauses that reference N different outer
relations, you could have as many as 2^N-1 sets of outer relations that
could possibly generate usefully-different parameterized paths. In
practice, since all these clauses must be usable with the same index,
there's probably not nearly that many useful combinations --- but again,
it's hard to know exactly which ones are winners in advance of doing any
cost calculations.
regards, tom lane