Re: *_collapse_limit, geqo_threshold

Noah Misch <noah(at)leadboat(dot)com> writes:
> With joins between statistically indistinguishable columns, I see planning times
> change by a factor of ~4 for each join added or removed (postgres 8.3). Varying
> join_collapse_limit in the neighborhood of the actual number of joins has a
> similar effect. See attachment with annotated timings. The example uses a
> single table joined to itself, but using distinct tables with identical contents
> yields the same figures.

Hey, some hard data! Thanks for doing that.

> The expontential factor seems smaller for real queries. I have a query of
> sixteen joins that takes 71s to plan deterministically; it looks like this:

> SELECT 1 FROM fact JOIN dim0 ... JOIN dim6
> JOIN t t0 ON fact.key = t.key AND t.x = MCV0
> LEFT JOIN t t1 ON fact.key = t.key AND t.x = MCV1
> JOIN t t2 ON fact.key = t.key AND t.x = MCV2
> LEFT JOIN t t3 ON fact.key = t.key AND t.x = NON-MCV0
> LEFT JOIN t t4 ON fact.key = t.key AND t.x = NON-MCV1
> LEFT JOIN t t5 ON fact.key = t.key AND t.x = NON-MCV2
> LEFT JOIN t t6 ON fact.key = t.key AND t.x = NON-MCV3
> LEFT JOIN t t7 ON fact.key = t.key AND t.x = NON-MCV4

I'm confused here --- I think you must have over-anonymized your query.
Surely the ON conditions for the left joins should be referencing t3,
t4, etc?

> For the real query, removing one join drops plan time to 26s, and
> removing two drops the time to 11s. I don't have a good theory for
> the multiplier changing from 4 for the trivial demonstration to ~2.5
> for this real query.

The rule of thumb that says that an n-way join requires 2^n work is only
true if we consider every single combination of possible joins, which
normally we don't. The planner prefers join paths that follow join
clauses, and will only consider clauseless joins when it has no other
choice. I believe that real queries tend to be pretty non-flat in this
space and so the number of join paths to consider is a lot less than 2^n.
Your synthesized query, on the other hand, allows any relation to be
joined to any other --- it might not look that way, but after creating
derived equalities there will be a potential join clause linking every
relation to every other one. So I think you were testing the worst case,
and I'm not surprised that more-typical queries would show a slower
growth curve.

This is why I don't trust benchmarking the planner on artificial
queries. Still, I appreciate your work, because it gives us at least
some hard data to go on.

regards, tom lane