a path towards replacing GEQO with something better

Hi,

On occasion it comes up that the genetic query optimizer (GEQO) doesn't produce particularly great plans, and is slow ([1] for example). The only alternative that has gotten as far as a prototype patch (as far as I know) is simulated annealing some years ago, which didn't seem to get far.

The join problem as it pertains to Postgres has been described within the community in
[Gustaffson, 2017] and [Stroffek & Kovarik, 2007].

The fact that there is much more interest than code in this area indicates that this is a hard problem. I hadn't given it much thought myself until by chance I came across [Neumann, 2018], which describes a number of interesting ideas. The key takeaway is that you want a graceful transition between exhaustive search and heuristic search. In other words, if the space of possible join orderings is just slightly larger than the maximum allowed exhaustive search, then the search should be *almost* exhaustive. This not only increases the chances of finding a good plan, but also has three engineering advantages I can think of:

1) It's natural to re-use data structures etc. already used by the existing dynamic programming (DP) algorithm. Framing the problem as extending DP greatly lowers the barrier to making realistic progress. If the problem is framed as "find an algorithm as a complete drop-in replacement for GEQO", it's a riskier project in my view.

2) We can still keep GEQO around (with some huge limit by default) for a few years as an escape hatch, while we refine the replacement. If there is some bug that prevents finding a plan, we can emit a WARNING and fall back to GEQO. Or if a user encounters a regression in a big query, they can lower the limit to restore the plan they had in an earlier version.

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

The math behind this is described in detail in [Ono & Lohman, 1990]. I verified this in Postgres by instrumenting the planner to count how many times it calls make_join_rel().

Imagine having a "join enumeration budget" that, if exceeded, prevents advancing to the next join level. Given the above numbers and a query with some combination of chain and star shapes, a budget of 400 can guarantee an exhaustive search when there are up to 8 relations. For a pure chain join, we can do an exhaustive search on up to 13 relations, for a similar cost of time and space. Out of curiosity I tested HEAD with a chain query having 64 tables found in the SQLite tests [2] and found exhaustive search to take only twice as long as GEQO. If we have some 30-way join, and some (> 400) budget, it's actually possible that we will complete the exhaustive search and get the optimal plan. This is a bottom-up way of determining the complexity. Rather than configuring a number-of-relations threshold and possibly have exponential behavior blow up in their faces, users can configure something that somewhat resembles the runtime cost.

Now, I'll walk through one way that a greedy heuristic can integrate with DP. In our 30-way join example, if we use up our budget and don't have a valid plan, we'll break out of DP at the last join level we completed. Since we already have built a number of joinrels, we build upon that work as we proceed. The approach I have in mind is described in [Kossmann & Stocker, 2000], which the authors call "iterative dynamic programming" (IDP). I'll describe one of the possible variants here. Let's say we only got as far as join level 8, so we've created up to 8-way joinrels. We pick the best few (maybe 5%) of these 8-way joinrels by some measure (doesn't have to be the full cost model) and on top of each of them create a full plan quickly: At each join level, we only pick one base relation (again by some measure) to create one new joinrel and then move to the next join level. This is very fast, even with hundreds of relations.

Once we have one valid, complete plan, we can technically stop at any time (Coding this much is also a good proof-of-concept). How much additional effort we expend to find a good plan could be another budget we have.  With a complete plan obtained quickly, we also have an upper bound on the measure of the cheapest overall plan, so with that we can prune any more expensive plans as we iterate through the 8-way joinrels. Once we have a set of complete plans, we pick some of them to improve the part of the plan picked during the greedy step. For some size k (typically between 4 and 7), we divide the greedy-step part of the join into k-sized sections. So with our 30-table join where we started with an 8-way joinrel, we have 22 tables. If k=5, we run standard dynamic programming (including the standard cost model) on four 5-table sections and then once the last 2-table section.

You can also think of it like this: We quickly find 5 tables that likely would be good to join next, find the optimal join order among the 5, then add that to our joinrel. We keep doing that until we get a valid plan. The only difference is, performing the greedy step to completion allows us to prune subsequent bad intermediate steps.

By "some measure" above I'm being a bit hand-wavy, but at least in the literature I've read, fast heuristic algorithms seem to use simpler and cheaper-to-compute metrics like intermediate result size or selectivity, rather than a full cost function. That's a detail to be worked out. Also, it must be said that in choosing among intermediate steps we need to be careful to include things like:

- interesting sort orders
- patition-wise joins
- parameterized paths

Further along the lines of extending DP that's kind of orthogonal to the above is the possibility of doing pruning during the initial DP step. Looking again at how quickly the join enumeration for star queries grows with increasing "n", it makes sense that a large number of those are bad plans. In [Das & Haritsa, 2006], the authors demonstrate a method of extending the reach of DP by pruning joinrels at each join level by two criteria:

1) Whether the joinrel contains a hub relation (i.e. is the center of a star)
2) A skyline function taking into account cost, cardinality, and selectivity

This way, the worst joinrels of star queries are pruned and the initial join budget I mentioned above goes a lot farther.

There are quite a few details and variations I left out (testing, for one), but this is enough to show the idea. I plan on working on this during the PG15 cycle. I'd appreciate any feedback on the above.
--

[1] https://www.postgresql.org/message-id/15658.1241278636@sss.pgh.pa.us

[Stroffek & Kovarik, 2007] https://www.pgcon.org/2007/schedule/attachments/28-Execution_Plan_Optimization_Techniques_Stroffek_Kovarik.pdf

[Gustaffson, 2017]  https://www.postgresql.eu/events/pgconfeu2017/sessions/session/1586/slides/26/Through_the_Joining_Glass-PGConfeu-DanielGustafsson.pdf

[Neumann, 2018] Adaptive Optimization of Very Large Join Queries. https://dl.acm.org/doi/10.1145/3183713.3183733

[Ono & Lohman, 1990] Measuring the Complexity of Join Enumeration in Query Optimization. https://www.csd.uoc.gr/~hy460/pdf/MeasuringtheComplexityofJoinEnumerationinQueryOptimization.PDF

[2] https://www.sqlite.org/sqllogictest/file?name=test/select5.test
(Note: there are no explicit join clauses so "from" limits didn't have an effect in my quick test.)

[Kossmann & Stocker, 2000] Iterative dynamic programming: a new class of query optimization algorithms. https://doi.org/10.1145/352958.352982

[Das & Haritsa, 2006] Robust Heuristics for Scalable Optimization of Complex SQL Queries. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.549.4331&rep=rep1&type=pdf
--