Two separate points. 1. I recall that there is an important class of plans that first forms the Cartesian product of some very small relations, and then joins everything else to it. Does anyone else encounter these plans? Would these plans be unavailable if we made your proposed change?
2. If I join on a low cardinality attribute (eg customers to suppliers on state) the result is almost as bad a cross join. I presume you would want to treat this join similarly. If so, it would make sense to have the rules on selectivity (or similar) rather than structure alone. Julian > On Feb 12, 2021, at 23:04, Vladimir Ozerov <[email protected]> wrote: > > Hi, > > Join order planning is an important optimization problem. The widely-used > heuristic is to consider all bushy trees without cross-joins. There is > proof [1] that a pair of commute and associate rules is a complete ruleset > to explore all bushy trees without the cross-joins if the initial join tree > has no cross-joins. > > In Apache Calcite, we do not suppress cross-products. As a result, even > simple join topologies, like a chain, cannot be planned in a reasonable > time for more than 6-7 tables. How do you feel if we add an optional > cross-join suppression to the JoinAssociateRule, and possibly > JoinPushThroughJoinRule? > > The cross-join suppression is not the only problem with the exhaustive join > planning in Apache Calcite. But at the very least, it is simple to > implement, and it extends the number of tables in a join that could be > planned exhaustively for some topologies by additional 2-5 tables. > > Regards, > Vladimir. > > [1] https://dl.acm.org/doi/10.14778/2732977.2732997
