Haisheng and Xiening, thanks for sharing these wonderful ideas. I believe this will be a huge improvement and definitely benefits all users.
>From my experience of upgrading calcite version, there are always some changes in the new version which may lead to unexpected behavior due to a lack of enough integration tests with other systems even though it is a minor version. Currently, the VolcanoPlanner is proved to be production-ready and it has to be stable to make sure that other systems built on it would not have much trouble after using the new calcite version. So from my side, I wish we can provide an option to use the new planner at least considering its huge changes. Best, Chunwei On Tue, Apr 21, 2020 at 2:42 PM Андрей Цвелодуб <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 > > > >>>>>>>>>> > > > >>>>>>>>>> > > > >>>>>>>>>> > > > >>>>>>>>>> > > > >>>>>>>>>> > > > >>>>>>>>>> > > > >>>>>>>>>> > > > >>>>>>>>> > > > >>>>>>>> > > > >>>>>>> > > > >>>>> > > > >>>>> > > > >>> > > > >> > > > >> > > > > > > > > >
