One complex problem a query optimizer has to solve is finding the optimal join order since the execution time for different join orders can vary by several orders of magnitude. Plans with cross-products are likely to be inefficient, and many optimizers exclude them from the consideration using a technique known as cross-product suppression.
The number of cross-product free join orders for a query depends on join conditions between inputs. In this blog post, we discuss the complexity of the cross-product free join order enumeration for three common join graph topologies: clique, star, and chain.
Determining the best join order is a well-known NP-hard problem that cannot be solved in polynomial time in a general case. Let's estimate the number of possible join orders in the query based on the number of inputs. We already did that in our previous blog post, but we repeat that exercise here for clarity.
Consider that our system can execute two-way joins, like `AxB` or `BxA`. To join three inputs, we perform two two-way joins in a certain order. E.g., `Ax(CxB)` means that we first join `C` to `B` and then join `A` to the result. How many different join orders are there for N inputs?
First, we count the number of different orders of leaf nodes. Intuitively, for `N` inputs, we have `N` alternatives for the first position, `N-1` alternatives for the second position, etc., which gives us `N!` orders.
Next, for every particular leaf order, we determine the number of possible two-way join orders, which is the number of ways of associating `N-1` applications of a binary operator. This number is equal to the Catalan number `C(N-1)`.
The Catalan number of `N` is determined as follows:
We combine both parts to get the final formula:
Consider the TPC-DS suite. Query 3 joins three tables, which gives 12 join orders, an easy target. Query 17 joins eight tables, which gives more than 17 million join orders. Many optimizers would already give up on exhaustive enumeration at this point. Finally, query 64 has a sub-plan that joins eighteen tables, giving us ~830 sextillion join orders, big trouble.
The straightforward enumeration is impractical for complex queries, so any production-grade optimizer must use some heuristic to keep the planning time sane.
The common wisdom is that plans with cross-products are likely to be inefficient. If we exclude such plans from consideration, we may substantially reduce the number of alternative join orders.
Note that this is merely a heuristic, and there are some queries where the optimal plan contains cross-products. For example, if we join a fact table to two dimension tables with highly selective predicates, it might be better to execute a cross-join on dimension tables and join the result with the fact table.
We introduce the join topology, a graph where vertices are inputs and edges are join conditions. The topology is called a clique when every input has a join condition with every other input. The topology is called a star when one input is joined to all other inputs. The topology is called a chain when two inputs are joined with one other input, and the rest are joined with two other inputs.
Now, let's count the number of cross-product free join orders for each topology.
The cross-product suppression is not applicable for clique by definition since every input has join conditions with every other input. Therefore, the number of cross-product free join orders in cliques equals to the formula above.
The chain topology with `N` relations has `N-1` join conditions. Let us create a base sequence of relations, such that the first and the last relation participate in one condition, and the rest relations participate in two conditions. For example, for three relations `A`, `B`, and `C`, the sequence would be: `A-B-C` (or `C-B-A`).
We first calculate the number of possible parenthesizations for the sequence, which is `C(N-1)`. For example, the sequence `A-B-C` has two valid parenthesizations: `(A(BC))` and `((AB)C)`. For each parenthesization, we flip the order of relations within every parenthesis, which gives us `2^(N-1)` combinations. For example, for the parenthesization `((AB)C)`, there are `2^(3-1)=4` join orders:
The final formula is:
For star queries, we count the number of left-deep trees starting with the fact table, giving us `(N-1)!` possible trees. For every such tree, we commute individual joins, which gives us `2^(N-1)` alternatives per tree.
The final formula is:
Consider the TPC-DS query 17 again. The join graph topology for this query looks as follows:
Without the cross-product suppression, there are `17,297,280` possible join orders. To count the number of cross-product free join orders, we implement a simple bottom-up join enumerator that discards the join orders with cross-products. The enumerator gives us `211,200` cross-product free join orders, roughly `1.3%` of all possible join orders. This example demonstrates how cross-join suppression may decrease the number of considered joins by several orders of magnitude.
Chain topologies produce the smallest number of cross-product free join orders, followed by star and clique. Real queries usually have mixed topologies, so counting the number of cross-product free join orders in them is not straightforward. Nevertheless, the number of plans with cross-products is vastly more than the number of cross-product free plans for most queries. Therefore, cross-product suppression is an important heuristic that allows discarding plenty of not optimal plans in advance.
Since the complexity remains exponential even for chain topologies, the cross-product suppression alone is not sufficient for production-grade databases. State-of-the-art optimizers attack the problem from two angles:
Altogether, these techniques allow query optimizers to find sensible join orders even for very complex queries, though the optimality is usually not guaranteed.
The join order enumeration is a well-known NP-hard problem that cannot be solved in a polynomial time. Modern query optimizers apply various heuristics to limit the search space. One of the most important heuristics is a cross-product suppression that discards cross-joins from consideration, reducing the number of considered join orders. This heuristic may miss some optimal plans with cross-products, and the overall complexity remains exponential. Therefore, the usage of cross-product suppression alone is rarely sufficient for state-of-the-art product-grade optimizers.
In future posts, we will see how the cross-product suppression and memoization may further improve the optimizer's performance. We will also discuss modern join enumeration algorithms and their implementations in practical optimizers. Stay tuned!
We are always ready to help you with your query engine design. Just let us know.
We help technology companies build innovative data management products.
