On Wed, Jun 9, 2021 at 9:24 PM John Naylor <john.nay...@enterprisedb.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
