Re: a path towards replacing GEQO with something better

On Wed, Jun 9, 2021 at 9:24 PM John Naylor <john(dot)naylor(at)enterprisedb(dot)com> wrote:
> 3) It actually improves the existing exhaustive search, because the complexity of the join order problem depends on the query shape: a "chain" shape (linear) vs. a "star" shape (as in star schema), for the most common examples. The size of the DP table grows like this (for n >= 4):
>
> Chain: (n^3 - n) / 6 (including bushy plans)
> Star: (n - 1) * 2^(n - 2)
>
> n chain star
> --------------------
> 4 10 12
> 5 20 32
> 6 35 80
> 7 56 192
> 8 84 448
> 9 120 1024
> 10 165 2304
> 11 220 5120
> 12 286 11264
> 13 364 24576
> 14 455 53248
> 15 560 114688
> ...
> 64 43680 290536219160925437952

I don't quite understand the difference between the "chain" case and
the "star" case. Can you show sample queries for each one? e.g. SELECT
... FROM a_1, a_2, ..., a_n WHERE <something>?

One idea I just ran across in
https://15721.courses.cs.cmu.edu/spring2020/papers/22-costmodels/p204-leis.pdf
is to try to economize by skipping consideration of bushy plans. We
could start doing that when some budget is exceeded, similar to what
you are proposing here, but probably the budget for skipping
consideration of bushy plans would be smaller than the budget for
switching to IDP. The idea of skipping bushy plan generation in some
cases makes sense to me intuitively because most of the plans
PostgreSQL generates are mostly left-deep, and even when we do
generate bushy plans, they're not always a whole lot better than the
nearest equivalent left-deep plan. The paper argues that considering
bushy plans makes measurable gains, but also that failure to consider
such plans isn't catastrophically bad.

--
Robert Haas
EDB: http://www.enterprisedb.com