Hi Andrii, > Obviously, from what is written here, I could guess that this would require > me to change my physical planning rules, even if only by implementing a > marker interface. You don't need to change your physical rules, it will be treated as equal as logical rules and be applied together with the real logical rules, no more logical/physical rules difference. This is also how current VolcanoPlanner works.
> I don't want you to think that I somehow resent the changes you are pushing. Don't get me wrong. I am seriously thinking of revert these changes, since most people like the idea of adding new planner, why don't we make all the plan changes in the new planner, instead of forcing people changing test cases for the code changes that they might not need in VolcanoPlanner during upgrade. I didn't intend to replace VolcanoPlanner, thought just change the search strategy and add trait derivation mechanism, because most of the code in VolcanoPlanner can be reused. But since many agree to add new planner and replace VolcanoPlanner as the final goal, I won't be against most people's decision. Is there any recommended approach to make that happen smoothly besides coding and testing work? We need to be aware that the new planner might be co-exist with VolcanoPlanner for 5 or more years, or even never replace VolcanoPlanner. More thoughts are welcome. Haisheng On 2020/04/21 19:56:25, Андрей Цвелодуб <a.tsvelo...@gmail.com> wrote: > Hello Haisheng, > > > To keep backward compatibility, all the un-marked rules will be treated > as logical rules, except rules that uses AbstractConverter as rule operand, > these rules still need to applied top-down, or random order. > Obviously, from what is written here, I could guess that this would require > me to change my physical planning rules, even if only by implementing a > marker interface. I am not saying this is a bad thing, but this is a thing > that should be communicated and planned ahead in case the VolcanoPlanner is > modified. > > > Looks like I have to revert changes in CALCITE-2970 and CALCITE-3753, > because they will cause another tons of plan changes. > I see you are still bitter due to all the discussions on this list lately, > I'm sorry. I don't want you to think that I somehow resent the changes you > are pushing, au contraire I support them and would be happy to help if I > can. I just want the process of these changes to be executed in the best > possible way. > As I see there are already several opinions in this thread that basically > align with what I am saying, so I guess I am not the crazy guy running > around and yelling "the end is nigh!". > > Thank you for taking these mumbled thoughts into account. > > Bestest Regards, > Andrii Tsvielodub > > On Tue, 21 Apr 2020 at 21:08, Haisheng Yuan <hy...@apache.org> wrote: > > > Hi Andrii, > > > > > I guess changing the planner would lead to changes in tons of rules and > > even more tests. > > Obviously you didn't read through my email. You are not required to do any > > changes to your rule if you don't want to, but if you do, just need to mark > > the rule to tell planner whether it is a physical rule or not, simply by > > implementing an empty interface. > > > > > many on this list already experienced problems with upgrading even > > between the minor versions of Calcite. > > Sorry to see the problem you have experienced when upgrading Calcite. > > Looks like I have to revert changes in CALCITE-2970 and CALCITE-3753, > > because they will cause another tons of plan changes. > > > > But I will see if I can add a setting to use the old search strategy, > > which can be left untouched. > > > > Haisheng > > > > On 2020/04/21 06:33:08, Андрей Цвелодуб <a.tsvelo...@gmail.com> wrote: > > > Hello everyone, > > > > > > First of all, thanks for this great effort of improving the core parts of > > > the framework we all are using, > > > I believe this is long overdue and hope this will have benefits both for > > > the maintainers and users of the library. > > > > > > I don't have anything to say about the general idea at the moment, > > > but I want to make a point that maintaining the old implementation of > > > VolcanoPlanner during > > > the initial stages of implementing the new planner is absolutely > > CRITICAL. > > > As a lot of users of Calcite do various customizations to the engine, to > > > the rules > > > and all that is there in between, I believe changing the implementation > > of > > > the core component > > > would have a huge impact on most users of the library. I think many on > > this > > > list > > > already experienced problems with upgrading even between the minor > > versions > > > of Calcite, > > > so I guess changing the planner would lead to changes in tons of rules > > and > > > even more tests. > > > > > > I don't have anything against replacing VolcanoPlanner as a final goal of > > > this effort, > > > but I don't think that modifying it directly and merging it to master is > > a > > > viable development approach. > > > While I understand how burdensome it is to maintain several parallel core > > > components at once > > > (we did this while moving the engine of our product to Calcite), we > > should > > > still respect those who depend > > > on it and not introduce the risks related to the development of a new > > > component into existing processing flows. > > > > > > A good model to try to follow would be the way new Garbage Collectors are > > > introduced in Java. > > > First, add it as an experimental option, then make it generally > > available, > > > then after everyone agrees > > > this is the best option - make it the default one. > > > With this approach, everyone can then move to the new planner at their > > own > > > pace, guaranteeing a smooth transition overall. > > > Yes, this could take some time, maybe even a year, but this is the price > > of > > > doing major changes in a popular framework. > > > > > > Again, thank you for initiating this discussion and leading this effort. > > > > > > Best Regards, > > > Andrii Tsvielodub > > > > > > On Tue, 21 Apr 2020 at 07:51, Jinpeng Wu <wjpabc...@gmail.com> wrote: > > > > > > > Hi, Xiening. > > > > > > > > Regarding calculating the logical cost, here are some ways I though: > > > > 1. Logical rel may implement their own computeSelfCost method. Some > > > > rels can provide such information, for example the > > > > LogicalProject/LogicalFilter contains nearly the same information as > > their > > > > physical implementations. If we don't have enough confidence, just > > return > > > > zeroCost is also OK, as it only affects pruning. > > > > 2. Logical rel tells its parents what its physical input could be > > after > > > > implementation. Then the problem come back to calculating lower bound > > of a > > > > physical rel. > > > > There should always be ways. The only problem is how to find a pretty > > one. > > > > > > > > Regarding the risk, new planner do have different risk. It is not > > because > > > > new planner could stop us doing something wrong but we can decide when > > to > > > > use the new one. Some scenarios: > > > > 1. If modifying the VolcanoPlanner directly, the only way user could > > > > control the risk is not to upgrade calcite version until it is > > considered > > > > stable. You know, it is quite different from keeping calcite updated > > and > > > > switching to the new planner at a proper time. > > > > 2. It is very importance for SLA control. For the important business > > and > > > > jobs, we may keep using the old and stable planner. And use the new one > > > > only for jobs that have fault tolerance. And this helps testing new > > planner > > > > with actual scenarios. > > > > 3. It is helpful when upgrading online services. When the new planner > > > > happened to have some bugs, we can switch to the old planner directly > > > > without rollback the whole service. > > > > 4. With all these ways to prevent issues becoming disasters, we are not > > > > vulnerable to making mistakes. This not only enables faster iterations > > but > > > > also let us have enough time to resolve big bugs, like considering it > > in > > > > detail and applying a time-consuming refactoring for it. To work > > around a > > > > critical bug using tricky ways usually introduces more issues. > > > > > > > > Thanks, > > > > Jinpeng > > > > > > > > On Tue, Apr 21, 2020 at 2:04 AM Xiening Dai <xndai....@gmail.com> > > wrote: > > > > > > > > > Hi Jinpeng, > > > > > > > > > > Regarding this comment - I believe there are ways to calculate the > > > > logical > > > > > cost, but I think it’s not that simple as "cardinality * > > > > unit_copy_cost.”, > > > > > would you provide more details of other different ways? Just the > > > > algorithm > > > > > description or pseudo code would help us understand. Thanks. > > > > > > > > > > Regarding the approach of creating new planner, I don’t think a new > > > > > planner would lower the risk. We don’t know what we don’t know. If we > > > > > introduced an issue while modifying the planner, most likely we > > would do > > > > > the same with new planner class. A new planner doesn’t necessarily > > > > prevent > > > > > the issue from happening, but just delay its surfacing, which is > > worse > > > > IMO. > > > > > > > > > > There’s one obvious benefit with new planner is that we can provide > > some > > > > > sort of isolation so the change won’t cause test baseline updates, > > which > > > > > could be painful at times. We should see if we could use planner > > config > > > > to > > > > > achieve the same if we decide to just modify the current planner. > > > > > > > > > > > > > > > > On Apr 20, 2020, at 8:32 AM, Haisheng Yuan <hy...@apache.org> > > wrote: > > > > > > > > > > > > Igor, > > > > > > > > > > > > That's great. > > > > > > > > > > > > On 2020/04/20 11:17:49, Seliverstov Igor <gvvinbl...@gmail.com> > > wrote: > > > > > >> Haisheng, Xiening, > > > > > >> > > > > > >> Ok, Now I see how it should work. > > > > > >> > > > > > >> Thanks for your replies. > > > > > >> > > > > > >> Regards, > > > > > >> Igor > > > > > >> > > > > > >>> 20 апр. 2020 г., в 09:56, Seliverstov Igor <gvvinbl...@gmail.com > > > > > > > > написал(а): > > > > > >>> > > > > > >>> Haisheng, Xiening, > > > > > >>> > > > > > >>> Thanks for clarifying. > > > > > >>> > > > > > >>> In this proposal, we are not trying to split logical and physical > > > > > planning entirely. - actually I was in doubt about an idea of entire > > > > > splitting logical and physical phases, if you aren't going to, I > > have no > > > > > objections. > > > > > >>> > > > > > >>> But it returns me to my first question: how we will propagate > > traits > > > > > in bottom-up manner using proposed approach. (See [DISCUSS] Proposal > > to > > > > add > > > > > API to force rules matching specific rels for details) > > > > > >>> > > > > > >>> One of inconveniences of current VolcanoPlanner implementation is > > > > > amount of tricks that we need to get desired behaviour. It would be > > great > > > > > if some of issues (or all of them) were solved in the new approach. > > > > > >>> > > > > > >>> Regards, > > > > > >>> Igor > > > > > >>> > > > > > >>> пн, 20 апр. 2020 г., 7:02 Xiening Dai <xndai....@gmail.com > > <mailto: > > > > > xndai....@gmail.com>>: > > > > > >>> Hi Igor, > > > > > >>> > > > > > >>> Your comment - "because actual cost may be calculated correctly > > using > > > > > physical operators only. So won't be able to implement Branch and > > Bound > > > > > Space Pruning.“ is actually not true. In Cascade’s lower bound / > > upper > > > > > bound pruning algorithm, you can get cost lower bound of input > > RelNode > > > > > using cardinality * unit_copy_cost. The unit_copy_cost is a constant, > > > > which > > > > > stands for the minimal cost for processing a tuple from the input. So > > > > this > > > > > will be the minimal cost the input RelNode can achieve, and if this > > is > > > > > indeed larger than the current best cost, this input node can be > > pruned. > > > > > >>> > > > > > >>> In this proposal, we are not trying to split logical and physical > > > > > planning entirely. But for any given equivalent set, we would need to > > > > > finish exploration before implementation. But for the entire memo > > tree, > > > > > each set could be in different planning stage, and an equivalent set > > can > > > > be > > > > > pruned even before it’s implemented. A text book example of > > > > aforementioned > > > > > “lower bound / upper bound pruning” would be the join ordering case. > > > > > >>> > > > > > >>> Regarding #3, I think we can still achieve that (partially) > > through > > > > > this proposal. Remember every time when we start the optimization, we > > > > pass > > > > > down an upper bound limit. Initially this upper bound for root is > > > > infinite > > > > > - meaning that no feasible plan is available. Every time when we > > find a > > > > > physical plan we update this upper bound, then start the search > > again. We > > > > > could stop the search when the cost is less than a pre-defined > > threshold > > > > - > > > > > which gives you a “good enough” plan with early termination. Still > > this > > > > > wouldn't avoid the logical exploration. For that, you would probably > > > > > archive through rule configurations, and avoid some expansive > > > > > transformation to keep the cost down. > > > > > >>> > > > > > >>> > > > > > >>>> On Apr 19, 2020, at 7:30 PM, Haisheng Yuan <hy...@apache.org > > > > <mailto: > > > > > hy...@apache.org>> wrote: > > > > > >>>> > > > > > >>>> Igor, > > > > > >>>> > > > > > >>>> a) Given current Calcite's stats derivation strategy, mixing > > logical > > > > > and physical planning won't make it better. I hope you went through > > my > > > > > email to the end, currently operators inside a memo group don't share > > > > stats > > > > > info, each operator's stats may differ with the other one, and the > > > > > RelSubset's best node and stats may vary during optimization. So > > logical > > > > > and physical rule pruning are not safe at the moment, otherwise it > > almost > > > > > implies changing downstream project's cost model silently. > > > > > >>>> > > > > > >>>> On the other hand, ensuring child group exploration task finish > > > > first > > > > > will make rule mutual exclusivity check possible, like the result of > > > > > ReduceExpressionRule won't need trigger the same rule again, The join > > > > > result of JoinCommuteRule won't need trigger JoinCommuteRule and > > > > > ReduceExpressionRule again. > > > > > >>>> > > > > > >>>> More importantly, most if not all the the long planning queries > > in > > > > > Calcite are not caused by too many alternatives, but mutual > > triggering, > > > > or > > > > > cyclic triggering, which can be avoided by customizing the rules > > instead > > > > of > > > > > using the default one. Unless you use dynamic programming (Calcite > > use > > > > > heuristic) on join reordering (left-deep, right-deep, bushy), space > > > > pruning > > > > > won't help make long / infinite running query faster. > > > > > >>>> > > > > > >>>> b) No evidence shows current version of Calcite will return the > > most > > > > > promising plan in first planning iteration. Instead of praying for > > > > getting > > > > > good enough plan in the first iteration, why not focus on fixing > > rules > > > > that > > > > > causes the issue? > > > > > >>>> > > > > > >>>> c) That is not the goal. > > > > > >>>> > > > > > >>>> On 2020/04/19 15:14:57, Seliverstov Igor <gvvinbl...@gmail.com > > > > > <mailto:gvvinbl...@gmail.com>> wrote: > > > > > >>>>> Haisheng, > > > > > >>>>> > > > > > >>>>> From my point of view splitting logical and physical planning > > parts > > > > > isn’t a good idea. > > > > > >>>>> > > > > > >>>>> I think so because actual cost may be calculated correctly > > using > > > > > physical operators only. So that we: > > > > > >>>>> a) won't be able to implement Branch and Bound Space Pruning > > (as > > > > far > > > > > as I understand, at exploring time there are no physical operators, > > no > > > > > correct costs, but assumptions only, I don’t think we should rely on > > > > them) > > > > > >>>>> b) won’t be able to get good enough plan (without Branch and > > Bound > > > > > Space Pruning it’s non-trivial task to get right search direction and > > > > most > > > > > promising plans in first planning iterations) > > > > > >>>>> c) won’t be able to tune the good enough plan during several > > > > similar > > > > > queries are executed > > > > > >>>>> > > > > > >>>>> Regards, > > > > > >>>>> Igor > > > > > >>>>> > > > > > >>>>> > > > > > >>>>>> 19 апр. 2020 г., в 17:37, Haisheng Yuan <hy...@apache.org > > > > <mailto: > > > > > hy...@apache.org>> написал(а): > > > > > >>>>>> > > > > > >>>>>> Hi Igor, > > > > > >>>>>> > > > > > >>>>>> You can't have your cake and eat it. > > > > > >>>>>> But one feasible work item definitely we can do is that once > > > > > timeout, stop exploring, use the first available physical operator in > > > > each > > > > > group and optimize it. > > > > > >>>>>> > > > > > >>>>>> Because most, if not all, of the long / infinite running > > > > > optimizations are caused by project related transpose, join > > reordering > > > > > (join commute + associative), constant reduction for large expression > > > > (see > > > > > CALCITE-3460), all of which are logical transformations rules and > > many of > > > > > which have corresponding JIRAs. So another alternative is, let's fix > > > > these > > > > > bugs to improve Calcite to make timeout option less usable. > > > > > >>>>>> > > > > > >>>>>> Another thing worth noting is that sql server optimizer > > timeout > > > > > mechanism is not based on clock time, but the number of optimization > > > > tasks > > > > > it has done [1]. > > > > > >>>>>> > > > > > >>>>>> [1] > > > > > > > > > > > https://techcommunity.microsoft.com/t5/sql-server-support/understanding-optimizer-timeout-and-how-complex-queries-can-be/ba-p/319188 > > > > > < > > > > > > > > > > > https://techcommunity.microsoft.com/t5/sql-server-support/understanding-optimizer-timeout-and-how-complex-queries-can-be/ba-p/319188 > > > > > > > > > > > >>>>>> > > > > > >>>>>> Regards, > > > > > >>>>>> Haisheng > > > > > >>>>>> > > > > > >>>>>> On 2020/04/19 11:31:27, Seliverstov Igor < > > gvvinbl...@gmail.com > > > > > <mailto:gvvinbl...@gmail.com>> wrote: > > > > > >>>>>>> Haisheng, > > > > > >>>>>>> > > > > > >>>>>>> Ok, then such notification isn't needed > > > > > >>>>>>> > > > > > >>>>>>> But in this case we don't have any control over how long > > planning > > > > > takes > > > > > >>>>>>> > > > > > >>>>>>> For some systems it's necessary to get good enough plan > > right now > > > > > instead > > > > > >>>>>>> of best one after while > > > > > >>>>>>> > > > > > >>>>>>> For example we've been considering a case when a query is > > > > > optimised several > > > > > >>>>>>> times in short iterations in case it's impossible to get the > > best > > > > > plan in > > > > > >>>>>>> reasonable period of time (for example there is an SLA for > > > > > response time) > > > > > >>>>>>> > > > > > >>>>>>> This mean we need all needed physical implementations after > > each > > > > > logical > > > > > >>>>>>> transformation is applied. > > > > > >>>>>>> > > > > > >>>>>>> Regards, > > > > > >>>>>>> Igor > > > > > >>>>>>> > > > > > >>>>>>> > > > > > >>>>>>> вс, 19 апр. 2020 г., 13:55 Haisheng Yuan <hy...@apache.org > > > > > <mailto:hy...@apache.org>>: > > > > > >>>>>>> > > > > > >>>>>>>> Hi Igor, > > > > > >>>>>>>> > > > > > >>>>>>>> There will be no rule queue anymore. Y will be fully > > explored > > > > > (logical > > > > > >>>>>>>> rules are matched and applied) before it can be implemented > > and > > > > > optimized. > > > > > >>>>>>>> > > > > > >>>>>>>> Thanks, > > > > > >>>>>>>> Haisheng > > > > > >>>>>>>> > > > > > >>>>>>>> On 2020/04/19 10:11:45, Seliverstov Igor < > > gvvinbl...@gmail.com > > > > > <mailto:gvvinbl...@gmail.com>> wrote: > > > > > >>>>>>>>> Hi Haisheng, > > > > > >>>>>>>>> > > > > > >>>>>>>>> Great explanation, thanks. > > > > > >>>>>>>>> > > > > > >>>>>>>>> One thing I'd like to cover in advance is trait propagation > > > > > process (I > > > > > >>>>>>>> need > > > > > >>>>>>>>> it for Apache Ignite SQL engine implementation). > > > > > >>>>>>>>> > > > > > >>>>>>>>> For example: > > > > > >>>>>>>>> > > > > > >>>>>>>>> There are two nodes: Rel X and its child node Rel Y > > > > > >>>>>>>>> > > > > > >>>>>>>>> Both nodes are in Optimized state, and there is a Logical > > rule > > > > > for Rel Y > > > > > >>>>>>>> in > > > > > >>>>>>>>> a rules queue matched, > > > > > >>>>>>>>> > > > > > >>>>>>>>> After logical rule is applied, there is a logical rel Rel > > Y' > > > > and > > > > > >>>>>>>> containing > > > > > >>>>>>>>> it set moves into Exploring state (since there is a logical > > > > node > > > > > which > > > > > >>>>>>>> has > > > > > >>>>>>>>> to be implemented) > > > > > >>>>>>>>> > > > > > >>>>>>>>> After whole process Exploring -> ... -> Optimized we need > > to > > > > > force parent > > > > > >>>>>>>>> Rel X set to switch its state from Optimized to Optimizing > > to > > > > > peek the > > > > > >>>>>>>>> newly implemented child and (possible) produce a new Rel X' > > > > > physical rel > > > > > >>>>>>>> on > > > > > >>>>>>>>> the basis of previously requested from the Rel X set > > traits. > > > > > >>>>>>>>> > > > > > >>>>>>>>> If a new Rel X' is produced, a Rel X' parent should move > > its > > > > > state > > > > > >>>>>>>>> Optimized -> Optimizing and repeat described above > > operations. > > > > > >>>>>>>>> > > > > > >>>>>>>>> Does it look like true? > > > > > >>>>>>>>> > > > > > >>>>>>>>> Regards, > > > > > >>>>>>>>> Igor > > > > > >>>>>>>>> > > > > > >>>>>>>>> > > > > > >>>>>>>>> вс, 19 апр. 2020 г., 6:52 Haisheng Yuan < > > > > h.y...@alibaba-inc.com > > > > > <mailto:h.y...@alibaba-inc.com>>: > > > > > >>>>>>>>> > > > > > >>>>>>>>>> Hi, > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> In the past few months, we have discussed a lot about > > Cascades > > > > > style > > > > > >>>>>>>>>> top-down optimization, including on-demand trait > > > > > derivation/request, > > > > > >>>>>>>> rule > > > > > >>>>>>>>>> apply, branch and bound space pruning. Now we think it is > > time > > > > > to move > > > > > >>>>>>>>>> towards these targets. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> We will separate it into several small issues, and each > > one > > > > can > > > > > be > > > > > >>>>>>>>>> integrated as a standalone, independent feature, and most > > > > > importantly, > > > > > >>>>>>>>>> meanwhile keep backward compatibility. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> 1. Top-down trait request > > > > > >>>>>>>>>> In other words, pass traits requirements from parent > > nodes to > > > > > child > > > > > >>>>>>>> nodes. > > > > > >>>>>>>>>> The trait requests happens after all the logical > > > > transformation > > > > > rules > > > > > >>>>>>>> and > > > > > >>>>>>>>>> physical implementation rules are done, in a top-down > > manner, > > > > > driven > > > > > >>>>>>>> from > > > > > >>>>>>>>>> root set. e.g.: > > > > > >>>>>>>>>> SELECT a, sum(c) FROM > > > > > >>>>>>>>>> (SELECT * FROM R JOIN S USING (a, b)) t > > > > > >>>>>>>>>> GROUP BY a; > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Suppose we have the following plan tree in the MEMO, and > > let's > > > > > only > > > > > >>>>>>>>>> consider distribution for simplicity, each group > > represents a > > > > > RelSet > > > > > >>>>>>>> in the > > > > > >>>>>>>>>> MEMO. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Group 1: Agg on [a] > > > > > >>>>>>>>>> Group 2: +-- MergeJoin on [a, b] > > > > > >>>>>>>>>> Group 3: |--- TableScan R > > > > > >>>>>>>>>> Group 4: +--- TableScan S > > > > > >>>>>>>>>> | Group No | Operator | Derived Traits | Required > > Traits | > > > > > >>>>>>>>>> | ----------- | ------------- | --------------- | > > > > > --------------- | > > > > > >>>>>>>>>> | Group 1 | Aggregate | Hash[a] | N/A > > > > > | > > > > > >>>>>>>>>> | Group 2 | MergeJoin | Hash[a,b] | Hash[a] > > > > | > > > > > >>>>>>>>>> | Group 3 | TableScan R | None | Hash[a,b] > > | > > > > > >>>>>>>>>> | Group 4 | TableScan S | None | Hash[a,b] > > | > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> We will add new interface PhysicalNode (or extending > > RelNode) > > > > > with > > > > > >>>>>>>>>> methods: > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> - Pair<RelTraitSet,List<RelTraitSet>> > > > > requireTraits(RelTraitSet > > > > > >>>>>>>> required); > > > > > >>>>>>>>>> pair.left is the current operator's new traitset, > > pair.right > > > > is > > > > > the > > > > > >>>>>>>> list > > > > > >>>>>>>>>> of children's required traitset. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> - RelNode passThrough(RelTraitSet required); > > > > > >>>>>>>>>> Default implementation will call above method > > requireTraits() > > > > > and > > > > > >>>>>>>>>> RelNode.copy() to create new RelNode. Available to be > > > > overriden > > > > > for > > > > > >>>>>>>>>> physical operators to customize the logic. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> The planner will call above method on MergeJoin operator > > to > > > > > pass the > > > > > >>>>>>>>>> required traits (Hash[a]) to Mergejoin's child operators. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> We will get a new MergeJoin: > > > > > >>>>>>>>>> MergeJoin hash[a] > > > > > >>>>>>>>>> |---- TableScan R hash[a] (RelSubset) > > > > > >>>>>>>>>> +---- TableScan S hash[a] (RelSubset) > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Now the MEMO group looks like: > > > > > >>>>>>>>>> | Group No | Operator | Derived Traits | Required > > > > > Traits > > > > > >>>>>>>> | > > > > > >>>>>>>>>> | ---------- | -------- ----- | -------------------- | > > > > > >>>>>>>>>> --------------------- | > > > > > >>>>>>>>>> | Group1 | Aggregate | Hash[a] | N/A > > > > > >>>>>>>>>> | > > > > > >>>>>>>>>> | Group2 | MergeJoin | Hash[a,b], Hash[a]| Hash[a] > > > > > >>>>>>>>>> | > > > > > >>>>>>>>>> | Group3 | TableScan R | None | > > > > Hash[a,b], > > > > > >>>>>>>> Hash[a] > > > > > >>>>>>>>>> | > > > > > >>>>>>>>>> | Group4 | TableScan S | None | > > > > Hash[a,b], > > > > > >>>>>>>> Hash[a] > > > > > >>>>>>>>>> | > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Calcite user may choose to ignore / not implement the > > > > interface > > > > > to keep > > > > > >>>>>>>>>> the original behavior. Each physical operator, according > > to > > > > its > > > > > own > > > > > >>>>>>>> logic, > > > > > >>>>>>>>>> decides whether passThrough() should pass traits down or > > not > > > > by > > > > > >>>>>>>> returning: > > > > > >>>>>>>>>> - a non-null RelNode, which means it can pass down > > > > > >>>>>>>>>> - null object, which means can't pass down > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> 2. Provide option to disable AbstractConverter > > > > > >>>>>>>>>> Once the plan can request traits in top-down way in the > > > > > framework, many > > > > > >>>>>>>>>> system don't need AbstractConverter anymore, since it is > > just > > > > a > > > > > >>>>>>>>>> intermediate operator to generate physical sort / > > exchange. > > > > For > > > > > those, > > > > > >>>>>>>> we > > > > > >>>>>>>>>> can provide option to disable AbstractConverter, generate > > > > > physical > > > > > >>>>>>>> enforcer > > > > > >>>>>>>>>> directly by adding a method to interface Convention: > > > > > >>>>>>>>>> - RelNode enforce(RelNode node, RelTraitSet traits); > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> The default implementation may just calling > > > > > >>>>>>>> changeTraitsUsingConverters(), > > > > > >>>>>>>>>> but people may choose to override it if the system has > > special > > > > > needs, > > > > > >>>>>>>> like > > > > > >>>>>>>>>> several traits must implement together, or the position of > > > > > collation in > > > > > >>>>>>>>>> RelTraitSet is before distribution. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> 3. Top-down driven, on-demand rule apply > > > > > >>>>>>>>>> For every RelNode in a RelSet, rule is matched and applied > > > > > >>>>>>>> sequentially, > > > > > >>>>>>>>>> newly generated RelNodes are added to the end of RelNode > > list > > > > > in the > > > > > >>>>>>>> RelSet > > > > > >>>>>>>>>> waiting for rule apply. RuleQueue and DeferringRuleCall > > is not > > > > > needed > > > > > >>>>>>>>>> anymore. This will make space pruning and rule mutual > > > > > exclusivity check > > > > > >>>>>>>>>> possible. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> There are 3 stages for each RelSet: > > > > > >>>>>>>>>> a). Exploration: logical transformation, yields logical > > nodes > > > > > >>>>>>>>>> b). Implementation: physical transformation, yields > > physical > > > > > nodes > > > > > >>>>>>>>>> c). Optimization: trait request, enforcement > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> The general process looks like: > > > > > >>>>>>>>>> - optimize RelSet X: > > > > > >>>>>>>>>> implement RelSet X > > > > > >>>>>>>>>> for each physical relnode in RelSet X: > > > > > >>>>>>>>>> // pass down trait requests to child RelSets > > > > > >>>>>>>>>> for each child RelSet Y of current relnode: > > > > > >>>>>>>>>> optimize RelSet Y > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> - implement RelSet X: > > > > > >>>>>>>>>> if X has been implemented: > > > > > >>>>>>>>>> return > > > > > >>>>>>>>>> explore RelSet X > > > > > >>>>>>>>>> for each relnode in RelSet X: > > > > > >>>>>>>>>> apply physical rules > > > > > >>>>>>>>>> - explore RelSet X: > > > > > >>>>>>>>>> if X has been explored > > > > > >>>>>>>>>> return > > > > > >>>>>>>>>> for each relnode in RelSet X: > > > > > >>>>>>>>>> // ensure each child RelSet of current relnode is > > > > explored > > > > > >>>>>>>>>> for each child RelSet Y of current relnode: > > > > > >>>>>>>>>> explore RelSet Y > > > > > >>>>>>>>>> apply logical rules on current relnode > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Basically it is a state machine with several states: > > > > > Initialized, > > > > > >>>>>>>>>> Explored, Exploring, Implemented, Implementing, Optimized, > > > > > Optimizing > > > > > >>>>>>>> and > > > > > >>>>>>>>>> several transition methods: exploreRelSet, exploreRelNode, > > > > > >>>>>>>> implementRelSet, > > > > > >>>>>>>>>> implementRelNode, optimizeRelSet, optimizeRelNode... > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> To achieve this, we need to mark the rules either logical > > rule > > > > > or > > > > > >>>>>>>> physical > > > > > >>>>>>>>>> rule. > > > > > >>>>>>>>>> To keep backward compatibility, all the un-marked rules > > will > > > > be > > > > > >>>>>>>> treated as > > > > > >>>>>>>>>> logical rules, except rules that uses AbstractConverter as > > > > rule > > > > > >>>>>>>> operand, > > > > > >>>>>>>>>> these rules still need to applied top-down, or random > > order. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> 4. On-demand, bottom-up trait derivation > > > > > >>>>>>>>>> It is called bottom-up, but actually driven by top-down, > > > > > happens same > > > > > >>>>>>>> time > > > > > >>>>>>>>>> as top-down trait request, in optimization stage mentioned > > > > > above. Many > > > > > >>>>>>>>>> Calcite based bigdata system only propagate traits on > > Project > > > > > and > > > > > >>>>>>>> Filter by > > > > > >>>>>>>>>> writing rules, which is very limited. In fact, we can > > extend > > > > > trait > > > > > >>>>>>>>>> propagation/derivation to all the operators, without > > rules, by > > > > > adding > > > > > >>>>>>>>>> interface PhysicalNode (or extending RelNode) with method: > > > > > >>>>>>>>>> - RelNode derive(RelTraitSet traits, int childId); > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Given the following plan (only consider distribution for > > > > > simplicity): > > > > > >>>>>>>>>> Agg [a,b] > > > > > >>>>>>>>>> +-- MergeJoin [a] > > > > > >>>>>>>>>> |---- TableScan R > > > > > >>>>>>>>>> +--- TableScan S > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Hash[a] won't satisfy Hash[a,b] without special treatment, > > > > > because > > > > > >>>>>>>> there > > > > > >>>>>>>>>> isn't a mechanism to coordinate traits between children. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Now we call derive method on Agg [a,b] node, > > derive(Hash[a], > > > > > 0), we get > > > > > >>>>>>>>>> the new node: > > > > > >>>>>>>>>> Agg [a] > > > > > >>>>>>>>>> +-- MergeJoin [a] (RelSubset) > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> We will provide different matching type, so each operator > > can > > > > > specify > > > > > >>>>>>>> what > > > > > >>>>>>>>>> kind of matching type it requires its children: > > > > > >>>>>>>>>> - MatchType getMatchType(RelTrait trait, int childId); > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> a) Exact: Hash[a,b] exact match Hash[a,b], aka, satisfy > > > > > >>>>>>>>>> b) Partial: Hash[a] partial match Hash[a,b] > > > > > >>>>>>>>>> c) Permuted: Sort[a,b,c] permuted match Sort[c,b,a] > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> In addition, optimization order is provided for each > > opertor > > > > to > > > > > >>>>>>>> specify: > > > > > >>>>>>>>>> a) left to right > > > > > >>>>>>>>>> b) right to left > > > > > >>>>>>>>>> c) both > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> For example, for query SELECT * FROM R join S on R.a=S.a > > and > > > > > R.b=S.b > > > > > >>>>>>>> and > > > > > >>>>>>>>>> R.c=S.c: > > > > > >>>>>>>>>> Suppose R is distributed by a,b, and S is distributed by > > c. > > > > > >>>>>>>>>> MergeJoin [a,b,c] > > > > > >>>>>>>>>> |--- TableScan R [a,b] > > > > > >>>>>>>>>> +-- TableScan S [c] > > > > > >>>>>>>>>> a) left to right, call derive(Hash[a,b], 0), we get > > MergeJoin > > > > > [a,b] > > > > > >>>>>>>>>> b) right to left, call derive(Hash[c], 1), we get > > MergeJoin > > > > > [c], most > > > > > >>>>>>>>>> likely a bad plan > > > > > >>>>>>>>>> c) both, get above 2 plans. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> For system that doesn't have a fine-tuned stats and cost > > > > model, > > > > > it may > > > > > >>>>>>>> not > > > > > >>>>>>>>>> be able to make a right decision based purely on cost. > > > > Probably > > > > > we > > > > > >>>>>>>> need to > > > > > >>>>>>>>>> provide the MergeJoin with both children's derived > > traitset > > > > > list. > > > > > >>>>>>>>>> - List<RelNode> derive(List<List<RelTraitSet>>); > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Of course, all above methods are optional to implement for > > > > > those who > > > > > >>>>>>>>>> doesn't need this feature. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> 5. Branch and Bound Space Pruning > > > > > >>>>>>>>>> After we implement on-demand, top-down trait enforcement > > and > > > > > >>>>>>>> rule-apply, > > > > > >>>>>>>>>> we can pass the cost limit at the time of passing down > > > > required > > > > > >>>>>>>> traits, as > > > > > >>>>>>>>>> described in the classical Cascades paper. Right now, > > Calcite > > > > > doesn't > > > > > >>>>>>>>>> provide group level logical properties, including stats > > info, > > > > > each > > > > > >>>>>>>> operator > > > > > >>>>>>>>>> in the same group has its own logical property and the > > stats > > > > > may vary, > > > > > >>>>>>>> so > > > > > >>>>>>>>>> we can only do limited space pruning for trait > > enforcement, > > > > > still > > > > > >>>>>>>> good. But > > > > > >>>>>>>>>> if we agree to add option to share group level stats > > between > > > > > relnodes > > > > > >>>>>>>> in a > > > > > >>>>>>>>>> RelSet, we will be able to do more aggresive space > > pruning, > > > > > which will > > > > > >>>>>>>> help > > > > > >>>>>>>>>> boost the performance of join reorder planning. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> With all that being said, how do we move forward? > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> There are 2 ways: > > > > > >>>>>>>>>> a) Modify on current VolcanoPlanner. > > > > > >>>>>>>>>> Pros: code reuse, existing numerous test cases and > > > > > infrastructure, > > > > > >>>>>>>> fast > > > > > >>>>>>>>>> integration > > > > > >>>>>>>>>> Cons: changing code always brings risk > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> b) Add a new XXXXPlanner > > > > > >>>>>>>>>> Pros: no risk, no tech debt, no need to worry about > > backward > > > > > >>>>>>>>>> compatability > > > > > >>>>>>>>>> Cons: separate test cases for new planner, one more > > planner to > > > > > >>>>>>>> maintain > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> We'd like to hear the community's thoughts and advices. > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> Thanks. > > > > > >>>>>>>>>> - Haisheng > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> > > > > > >>>>>>>>>> > > > > > >>>>>>>>> > > > > > >>>>>>>> > > > > > >>>>>>> > > > > > >>>>> > > > > > >>>>> > > > > > >>> > > > > > >> > > > > > >> > > > > > > > > > > > > > > > > > > > >
