Hi Julian, Thank you for sharing these issues. We end up with almost the same ideas. We attempted to add an input permute to Join, which allowed us to avoid projects. However, that complicates the integration with other rules, just as you mention in [2]. Globally unique column IDs seem like a better option from that perspective. Moreover, unique IDs may simplify the implementation of other optimizations. For example, many join enumeration techniques, whether DP-based or top-down, require the decomposition of the join graph into independent vertices (inputs) and edges (conditions) and careful reconstruction of the alternative join trees, and RexInputRef is not very suitable for that process. Another possible example is recently reported [3].
There are hundreds of usages of the RexInputRef, so the implementation of this idea might be prohibitively expensive. But putting this problem aside, do you envision any other potential blockers for the implementation of that idea? Regards, Vladimir. [1] https://github.com/apache/calcite/pull/2359 [2] https://issues.apache.org/jira/browse/CALCITE-62 [3] https://issues.apache.org/jira/browse/CALCITE-4534 вт, 9 мар. 2021 г. в 22:40, Julian Hyde <[email protected]>: > I investigated something similar a long time ago. We noticed that a > lot of trivial Project operators were being generated to compensate > for field re-ordering due to join transposition. And so the idea was > to allow each RelNode (and especially Join) to permute its output > fields. > > Here is the case: https://issues.apache.org/jira/browse/CALCITE-62. > https://issues.apache.org/jira/browse/CALCITE-55 is related. > > The problem, as I noted in CALCITE-62, is that people writing rules > have another mapping to deal with. > > I believe that other systems, such as Spark's Catalyst planner, use > globally unique IDs for columns (as opposed to Calcite, whose column > references are only locally unique, ordinals of the input > operator(s)). Globally unique IDs would be superior for this problem > but perhaps introduce other challenges. > > Julian > > On Sun, Mar 7, 2021 at 11:25 PM Vladimir Ozerov <[email protected]> > wrote: > > > > Hi, > > > > Currently, the order of attributes is used to define operators > equivalence. > > This leads to several interesting problems, such as possible duplication > of > > expressions (e.g., "a,a,b") or additional work in rules to detect trivial > > projects and/or input permutations (e.g. "a,b -> b,a"). > > > > But the biggest problem is the join order planning. In Calcite, AxB is > not > > equivalent to BxA: > > > > 1. It makes the ruleset [JoinCommuteRule, JoinAssociateRule] > > insufficient to explore all bushy trees because the commute operation > adds > > a project on top of the new join (AxB -> project(BxA)), thus not > > allowing for the associate rule to be executed on the upper join. The > > solution is to add the ProjectJoinTransposeRule to the ruleset, but > this > > increases the planning time dramatically, making Apache Calcite > unsuitable > > for the cost-based join planning even for relatively simple join > graphs. > > 2. It increases the number of join-related rule calls, which > complicates > > the implementation of the new join enumeration planning rules (e.g. > > top-down enumerators) because duplicate derivations compromise > performance. > > > > My question is - has the community considered an idea to make the order > of > > columns a common property of all operators, somewhat similar to the > trait, > > but without an explicit enforcer? > > > > For example, consider the following MEMO which the planner creates when > > trying to transform the join AxB to BxA: > > > > G1: { Scan1[table=t1, cols=a,b] } > > G2: { Scan2[table=t2, cols=c,d] } > > G3: { AxB[G1, G2], Project[G4, cols=$2,$3,$0,$1] } > > G4: { BxA[G2, G1] } > > > > However, if we make the column order part of the MEMO, we may potentially > > have something like this: > > > > G1: { Scan1[table=t1, cols=a,b] } > > G2: { Scan2[table=t2, cols=c,d] } > > G3 [cols=G1.$0, G1.$1, G2.$0, G2.$1]: { AxB[G1, G2], BxA[G2, G1] } > > > > Notice, how we were able to put AxB and BxA to the same equivalence > group. > > To my knowledge, CockroachDB uses a somewhat similar design. > > > > I realize that this is rather a radical idea, and more design work is > > required to come with a proper proposal. At this point, I just would like > > to kindly ask the community to share high-level feedback on that. Were > > similar ideas proposed before? > > > > Thank you, > > Vladimir. >
