It is still on my radar. I have been busy these days, but will send out a design doc in a few days. But just a heads up, the change would be larger than everyone's expected.
- Haisheng ------------------------------------------------------------------ 发件人：Danny Chan<yuzhao....@gmail.com> 日 期：2020年01月07日 17:29:46 收件人：<dev@calcite.apache.org> 主 题：Re: [DISCUSS] Proposal to add API to force rules matching specific rels Hi, guys, it seems that the discussion silent now, so do we have some conclusion that can contribute to current code, i.e. the suggested API change or new abstraction ? Or better, can someone give a design doc so that we can push and make that implemented ? Personally I was always looking forward to the result, because Apache Flink suffers for the bad planning performance for Join re-order or traits auto-adapter. Best, Danny Chan 在 2019年11月20日 +0800 AM2:14，Vladimir Ozerov <ppoze...@gmail.com>，写道： > HI Igor, > > Thank you for the details. Meanwhile, I solved it with separation of > conversion rules from the physical optimization rules. So the first pass > creates physical nodes with unknown physical properties (top-bottom), while > subsequent processing of the leaf nodes triggers rules which convert "bad" > physical nodes to "good" physical nodes with know distribution and > collation. > > Regards, > Vladimir. > > пн, 18 нояб. 2019 г. в 13:43, Seliverstov Igor <gvvinbl...@gmail.com>: > > > Vladimir, > > > > Hope it may help you. > > > > Currently we applied the next way (just rough description): > > > > 1) We created an API to derive possible traits permutations on the basis > > of children traits (quite similar to one, described in «On Demand trait > > set request» topic) > > > > 2) added a general rule that copies Logical nodes, but requesting our > > convention from their children (IGNITE convention, ANY distribution, EMPTY > > collation) and sets importance of old Logical nodes to zero - so, we have a > > Logical parent which input satisfies any possible distribution and no rules > > matched to previous logical node any more. > > > > 3) Physical rules to create physical rel nodes only if physical traits may > > be derived (there is no «barrier», described in one of previous messages) - > > derived traits are a collection, we don’t create a physical rel node for > > each possible traits set, also we may set zero importance for previously > > created rel nodes to decrease search space. > > > > Now we know actual and required distribution, we don’t need > > AbstractConverters and able just call TraitDef.convert() method inside a > > rule. > > A rule still able to produce the same output several times, but > > «memorization" inside the planner solves it for us. > > > > preliminary tests show almost zero overhead of the approach. > > > > Regards, > > Igor > > > > > > > 14 нояб. 2019 г., в 14:49, Vladimir Ozerov <ppoze...@gmail.com> > > написал(а): > > > > > > Hi Xing, > > > > > > Thanks for your suggestion. Yes, this may help, and if I get your idea > > > right, I already had it in my reproducer: > > > 1) Create the converted physical input: > > > > > https://github.com/devozerov/calcite-optimizer/blob/master/src/main/java/devozerov/physical/ProjectPhysicalRule.java#L49 > > > 2) Use it in case no physical children were found: > > > > > https://github.com/devozerov/calcite-optimizer/blob/master/src/main/java/devozerov/physical/ProjectPhysicalRule.java#L79 > > > > > > This idea is borrowed from Apache Drill physical rules. But the problem > > is > > > that this approach leads to a suboptimal plan - parent node doesn't know > > > the future distribution of a child node. And as a result, it doesn't know > > > it's own distribution. So the final plan is constructed in that way: > > > 1.1) Root enforced "SINGLETON" on its child: > > > -> PhysicalRoot[SINGLETON] > > > -> Converter[SINGLETON] > > > -> PhysicalProject[*ANY*] > > > -> PhysicalScan[REPLICATED] > > > > > > 1.2) But since the child (PhysicalProject) failed to infer distribution > > > during rule call, it falls back to ANY distribution. In order to satisfy > > > SINGLETON distribution of a parent, we inject an exchange in the final > > plan: > > > -> PhysicalRoot[SINGLETON] > > > * -> Exchange[SINGLETON]* > > > -> PhysicalProject[*ANY*] > > > -> PhysicalScan[REPLICATED] > > > > > > 2) But this is a suboptimal plan. The optimal plan is: > > > -> PhysicalRoot[SINGLETON] > > > -> PhysicalProject[REPLICATED] > > > -> PhysicalScan[REPLICATED] > > > > > > You may observe it in my tests: > > > 1) > > > > > https://github.com/devozerov/calcite-optimizer/blob/master/src/test/java/devozerov/OptimizerTest.java#L46 > > > - > > > works as you described and produces not optimal plan with exchange > > > 2) > > > > > https://github.com/devozerov/calcite-optimizer/blob/master/src/test/java/devozerov/OptimizerTest.java#L30 > > > - > > > rely on AbstractConverter-s and produce an optimal plan with bottom-up > > > trait propagation at the cost of significantly increased planning time > > > > > > Regards, > > > Vladimir. > > > > > > пт, 8 нояб. 2019 г. в 16:15, XING JIN <jinxing.co...@gmail.com>: > > > > > > > Hi Vladimir, > > > > > > > > I think the way PlannerTests#GoodSingleRule and EnumerableXXXRule work > > may > > > > help you ~ > > > > They work by a top-down fashion, but when matching parent, they convert > > the > > > > children explicitly. > > > > You may try below steps: > > > > 1. Construct a rule LogicalParentRule to match the LogicalParent without > > > > distribution/physical requirement for the LogicalChild; > > > > 2. In this rule, you call 'planner.changeTraits' on the LogicalChild to > > > > build a new child with physical convention. Note that at this moment > > only > > > > an empty RelSubset is created and no PhysicalChild exists. > > > > 3. Then set the RelNode to be the new input of LogicalParent; > > > > > > > > By above steps, you can build a parent-child relationship between > > > > LogicalParent and PhysicalChild, and at last the PhysicalParentRule > > will be > > > > fired based on this relationship. > > > > > > > > I have a commit to illustrate my idea, check VolcanoPlannerTest#testDEV > > in > > > > below link, hope it may help you ~ > > > > https://github.com/jinxing64/calcite/tree/demo > > > > > > > > Also I'm +1 with Seliverstov that to get all parents of a set, which > > > > against the current check in RelSubset#getParentRels > > > > > > > > Best, > > > > Jin > > > > > > > > Vladimir Ozerov <ppoze...@gmail.com> 于2019年11月5日周二 下午6:41写道： > > > > > > > > > Hi Xiening, > > > > > > > > > > I read the thread about on-demand trait requests. It seems pretty > > similar > > > > > to what I am trying to achieve, as it facilitates the bottom-up > > > > propagation > > > > > of physical traits. In fact, both your and my strategy propagate > > > > > traits > > > > > bottom-up, but I do this through rules, which also fire bottom-up, > > while > > > > in > > > > > your case only the traits are propagated bottom-up, while rules > > continue > > > > > working in a top-down fashion. > > > > > > > > > > However, I am thinking of how I would potentially implement my > > optimizer > > > > > with your approach, and it feels like with on-demand traits resulting > > > > > implementation of metadata queries may become very complex to that > > point > > > > > that it will look like another set of rules, parallel to the already > > > > > existing ruleset. For example, consider that I have a couple of > > > > distributed > > > > > tables in an OLTP application. These tables have a number of indexes, > > > > and I > > > > > would like to join them. First, I have a number of choices on how to > > join > > > > > tables with respect to distribution. Then, I have a number of choices > > on > > > > > which access method to use. Because sometimes it is beneficial to pick > > > > > index scans instead of table scans even without index conditions, for > > > > > example, to preserve a comfortable collation. So when my logical scan > > > > > receives such metadata request, it typically cannot return all > > > > > possible > > > > > combinations, because there are too many of them. Instead, some > > > > heuristical > > > > > or cost-based logic will be used to calculate a couple of most > > > > prospective > > > > > ones. But it seems that we will have to duplicate the same logic in > > > > > the > > > > > corresponding rule, aren't we? > > > > > > > > > > I would love to read your design because this is a really interesting > > > > > topic, and it is of great importance for the distributed engines > > > > developed > > > > > on top of Calcite since proper use of distribution and collation is > > > > > the > > > > key > > > > > success factor for efficient query optimization. > > > > > > > > > > Regards, > > > > > Vladimir. > > > > > > > > > > пт, 1 нояб. 2019 г. в 00:40, Xiening Dai <xndai....@gmail.com>: > > > > > > > > > > > Actually we solved this problem in our setup using a mechanism > > > > > > called > > > > > > “Pull-Up Traits”, which explores the possible trait set of > > > > > > children’s > > > > > input > > > > > > to decide parent’s physical properties. In order to determine child > > > > input > > > > > > trait, you would have to look at child’s children, and all the way > > > > > > to > > > > the > > > > > > leaves nodes or a barrier. A barrier is a rel node which cannot > > > > > > derive > > > > > any > > > > > > traits regardless the input. A good example would be a user define > > > > > function > > > > > > which would throw off any distribution or collation. Then we realize > > > > just > > > > > > pulling up is not enough, sometimes we would need to look at > > > > > > parent’s > > > > > > requirement as well. So we try to solve this in a unified framework, > > > > > which > > > > > > we call “On Demand Trait” and implement it as part of the framework > > > > > > so > > > > > > anyone can be benefited. I hope Haisheng can share a design doc once > > we > > > > > > have more concrete ideas. > > > > > > > > > > > > > > > > > > > On Oct 31, 2019, at 11:37 AM, Jinfeng Ni <j...@apache.org> wrote: > > > > > > > > > > > > > > Hi Vladimir, > > > > > > > > > > > > > > The SubsetTransformer interface and the iterating over the > > > > > > > RelNodes > > > > > > > within a RelSubset in Drill is exactly implemented to do the trait > > > > > > > propagation. We also had to rely on AbstractConverter to fire > > > > > > > necessary rule to avoid the CanNotPlan issue. At some point, > > > > > > > Calcite > > > > > > > community chooses to remove AbstractConverter and Drill had to > > > > > > > add it > > > > > > > back, which is probably one of the main reasons for us to continue > > > > > > > using a Calcite fork. I still remember we constantly had to deal > > > > with > > > > > > > the dilemma between "CanNotPlan" and long planing time due to > > > > explored > > > > > > > search space. > > > > > > > > > > > > > > Glad to see more people are joining the effort to solve this long > > > > > > > overdue issue, something missing in Calcite's core optimizer > > > > framework > > > > > > > "since before Calcite was Calcite" (Jacques's words). > > > > > > > > > > > > > > Jinfeng > > > > > > > > > > > > > > > > > > > > > On Thu, Oct 31, 2019 at 3:38 AM Vladimir Ozerov > > > > > > > <ppoze...@gmail.com> > > > > > > wrote: > > > > > > > > > > > > > > > > Hi Danny, > > > > > > > > > > > > > > > > Thank you very much for the links. What is described here is > > > > > > > > pretty > > > > > much > > > > > > > > similar to the problem I describe. Especially the discussion > > > > > > > > about > > > > > trait > > > > > > > > propagation, as this is basically what I need - to explore > > > > > > > > potential > > > > > > traits > > > > > > > > of children before optimizing parents. And this is basically > > > > > > > > what > > > > > Drill > > > > > > > > already does with it's SubsetTransformer: > > > > > > > > 1) There is a SubsetTransformer interface, which iterates over > > > > > physical > > > > > > > > relations of the given subset [1] > > > > > > > > 2) If you want to make a physical project, you iterate over > > > > > > > > physical > > > > > > > > relations of the input subset and create possible physical > > > > > > > > projects > > > > > [2] > > > > > > > > 3) But if you cannot find any physical input, then you trigger > > > > > creation > > > > > > of > > > > > > > > a "bad" physical project, which is very likely to have poor cost > > > > > > because it > > > > > > > > cannot take advantage of input's distribution information [3] > > > > > > > > So, step 2 - is a trait set propagation which is needed by many > > > > > > > > distributed engines. Step 3 - an attempt to workaround current > > > > > > > > VolcanoPlanner behavior, when a parent rule is fired only if > > > > produced > > > > > > child > > > > > > > > node has compatible trait set. > > > > > > > > > > > > > > > > I do not know Calcite's architecture that good but at first > > > > > > > > glance, > > > > > the > > > > > > > > proposed ability to re-fire rules of a specific Rel seems good > > > > enough. > > > > > > It > > > > > > > > doesn't expand search space, because no new nodes are created, > > > > > > > > and > > > > it > > > > > > seems > > > > > > > > to be relatively simple to implement. > > > > > > > > > > > > > > > > [1] > > > > > > > > > > > > > > > > > > > > > > > > > https://github.com/apache/drill/blob/1.16.0/exec/java-exec/src/main/java/org/apache/drill/exec/planner/physical/SubsetTransformer.java > > > > > > > > [2] > > > > > > > > > > > > > > > > > > > > > > > > > https://github.com/apache/drill/blob/1.16.0/exec/java-exec/src/main/java/org/apache/drill/exec/planner/physical/ProjectPrule.java#L66 > > > > > > > > [3] > > > > > > > > > > > > > > > > > > > > > > > > > https://github.com/apache/drill/blob/1.16.0/exec/java-exec/src/main/java/org/apache/drill/exec/planner/physical/ProjectPrule.java#L69 > > > > > > > > > > > > > > > > чт, 31 окт. 2019 г. в 12:21, Danny Chan <yuzhao....@gmail.com>: > > > > > > > > > > > > > > > > > Thanks Vladimir for bringing up this discussion ! > > > > > > > > > > > > > > > > > > Did you notice that there is a JIRA issue about this problem > > > > > > > > > ? [1] > > > > > > Also a > > > > > > > > > discussion about how to propagate the traits [2] > > > > > > > > > > > > > > > > > > [1] https://issues.apache.org/jira/browse/CALCITE-2970 > > > > > > > > > [2] > > > > > > > > > > > > > > > > > > > > > > > > > > https://ponymail-vm.apache.org/_GUI_/thread.html/79dac47ea50b5dfbd3f234e368ed61d247fb0eb989f87fe01aedaf25@%3Cdev.calcite.apache.org%3E > > > > > > > > > > > > > > > > > > Best, > > > > > > > > > Danny Chan > > > > > > > > > 在 2019年10月31日 +0800 PM3:56，Vladimir Ozerov <ppoze...@gmail.com > > > > > ，写道： > > > > > > > > > > Hi colleagues, > > > > > > > > > > > > > > > > > > > > I would like to discuss with the community the possibility > > > > > > > > > > of > > > > > adding a > > > > > > > > > new > > > > > > > > > > public method to VolcanoPlanner which will forcefully > > > > > > > > > > re-trigger > > > > the > > > > > > > > > rules > > > > > > > > > > for the specific rel. This is a follow up of a discussion > > > > > > > > > > started > > > > in > > > > > > the > > > > > > > > > > other thread [1]. > > > > > > > > > > > > > > > > > > > > **Problem statement** > > > > > > > > > > When converting between conventions during optimization > > > > > VolcanoPlanner > > > > > > > > > > prefers the top-bottom approach, so that the nodes are > > > > > > > > > > converted > > > > > from > > > > > > the > > > > > > > > > > root. But in some cases, the intermediate node must be > > > > > > > > > > converted > > > > > after > > > > > > > > > its > > > > > > > > > > children. This is especially true for distributed SQL > > > > > > > > > > engines, > > > > which > > > > > > rely > > > > > > > > > > on distribution traits during the optimization process: it > > > > > > > > > > is not > > > > > > > > > possible > > > > > > > > > > to efficiently choose a proper physical implementation of a > > > > > > > > > > parent > > > > > > node > > > > > > > > > > unless the physical representation of a child node is known. > > > > > > > > > > > > > > > > > > > > It seems that presently VolcanoPlanner cannot address such > > > > > > > > > > cases > > > > by > > > > > > > > > > default. Consider that we have two nodes and associated > > > > > > > > > > rules > > > > which > > > > > > > > > convert > > > > > > > > > > them to physical counterparts: > > > > > > > > > > [LogicalParent <- LogicalChild] > > > > > > > > > > The parent should be converted after the child. When the > > > > > > > > > > child is > > > > > > > > > > converted, the physical node is created: > > > > > > > > > > [LogicalParent <- {LogicalChild, PhysicalChild}] > > > > > > > > > > In order to finish the optimization process, we need to > > > > > > > > > > convert > > > > the > > > > > > > > > parent. > > > > > > > > > > But parent rules are not fired, because PhysicalChild has > > > > > > > > > > traits > > > > > > > > > > incompatible with LogicalParent. > > > > > > > > > > > > > > > > > > > > Presently the problem could be solved in two ways: > > > > > > > > > > 1) Always produce conversions when going top-down. In this > > > > > > > > > > case, I > > > > > > first > > > > > > > > > > create a physical parent, then a physical child. The > > > > > > > > > > problem is > > > > that > > > > > > > > > > created parent is not optimal because it didn't know child > > > > > > distribution > > > > > > > > > at > > > > > > > > > > the time of creation. So the full flow would be: create a > > > > > > > > > > bad > > > > > parent, > > > > > > > > > > create a good child, create a good parent. > > > > > > > > > > 1.1) [LogicalParent <- LogicalChild] > > > > > > > > > > 1.2) [{LogicalParent, PhysicalParentBad} <- LogicalChild] > > > > > > > > > > 1.3) [{LogicalParent, PhysicalParentBad} <- {LogicalChild, > > > > > > > > > PhysicalChild}] > > > > > > > > > > 1.4) [{LogicalParent, PhysicalParentBad, > > > > > > > > > > PhysicalParentGood} <- > > > > > > > > > > {LogicalChild, PhysicalChild}] > > > > > > > > > > What is worse, the creation of a not optimal parent will > > > > > > > > > > trigger > > > > > > rules on > > > > > > > > > > its parent, which in turn may create a not optimal > > > > > > > > > > parent-parent > > > > > node, > > > > > > > > > etc. > > > > > > > > > > > > > > > > > > > > 2) Make sure that your convention returns true for > > > > > > > > > > Convention.canConvertConvention. In this case, every time a > > > > > > > > > > new > > > > rel > > > > > is > > > > > > > > > > added to a RelSet, its traitset will be compared to > > > > > > > > > > traitsets of > > > > all > > > > > > > > > other > > > > > > > > > > rels in the set. For every pair of traitset we may ask the > > > > > > > > > > engine > > > > to > > > > > > > > > create > > > > > > > > > > a relevant AbstractConverter. The net effect is that > > > > > > > > > "physical-to-logical" > > > > > > > > > > converter is created, which re-triggers the rule on the > > > > > > > > > > logical > > > > > parent > > > > > > > > > > since their conventions are compatible: > > > > > > > > > > 2.1) [LogicalParent <- LogicalChild] > > > > > > > > > > 2.2) [LogicalParent <- {LogicalChild, PhysicalChild}] > > > > > > > > > > 2.3) [LogicalParent <- {LogicalChild, PhysicalChild, > > > > > > > > > > PhysicalToLogicalConverter}] > > > > > > > > > > 2.4) [{LogicalParent, PhysicalParent} <- {LogicalChild, > > > > > PhysicalChild, > > > > > > > > > > PhysicalToLogicalConverter}] > > > > > > > > > > > > > > > > > > > > The problem with that approach is that it is too > > > > > > > > > > coarse-grained > > > > > since > > > > > > we > > > > > > > > > > operate on traitsets rather than rels. As a result, > > > > > > > > > > additional > > > > > memory > > > > > > and > > > > > > > > > > CPU pressure are introduced because usually too many > > > > > > > > > > converters > > > > are > > > > > > > > > > created, which triggers the rules over and over again. > > > > > > > > > > > > > > > > > > > > **Affected products** > > > > > > > > > > At the moment two distributed engines are being developed > > > > > > > > > > for > > > > > > Hazelcast > > > > > > > > > and > > > > > > > > > > Apache Ignite. Both require bottom-up optimization and > > > > > > > > > > currently > > > > > rely > > > > > > on > > > > > > > > > > the second workaround. > > > > > > > > > > Another example is Apache Drill. I do not know whether its > > > > community > > > > > > is > > > > > > > > > > concerned with the issue, but it also uses bottom-up > > > > > > > > > > optimization > > > > > for > > > > > > > > > many > > > > > > > > > > rules and employs both the aforementioned workarounds. As a > > > > result, > > > > > I > > > > > > > > > guess > > > > > > > > > > that Drill's optimizer also creates too many rels during > > > > > optimization > > > > > > and > > > > > > > > > > suffer from huge search space. Please correct me if I am > > > > > > > > > > wrong. > > > > > > > > > > > > > > > > > > > > **Proposal** > > > > > > > > > > The key problem is that there is no way to re-fire rules on > > > > > > > > > > a > > > > > specific > > > > > > > > > > node. The original problem could have been solved, if it > > > > > > > > > > would be > > > > > > > > > possible > > > > > > > > > > to re-fire rules on a LogicalParent without creating any > > > > additional > > > > > > rels. > > > > > > > > > > That would lead to a clear optimization flow: > > > > > > > > > > 2.1) [LogicalParent <- LogicalChild] > > > > > > > > > > 2.2) [LogicalParent <- {LogicalChild, PhysicalChild}] > > > > > > > > > > 2.3) [{LogicalParent, PhysicalParent} <- {LogicalChild, > > > > > > PhysicalChild}] > > > > > > > > > > > > > > > > > > > > We can add the following method to VolcanoPlanner > > > > > > > > > > (RelOptPlanner?) > > > > > > > > > > interface: > > > > > > > > > > void fireRules(RelNode rel) > > > > > > > > > > > > > > > > > > > > This method will fire the rules on a passed node in a > > > > > > > > > > deferred > > > > mode > > > > > > as if > > > > > > > > > > it was the new node just added to the optimizer. This would > > > > require > > > > > > > > > slight > > > > > > > > > > changes to RuleQueue.addMatch method, and possibly some > > > > > > > > > > other > > > > > places. > > > > > > > > > > > > > > > > > > > > Usage example: > > > > > > > > > > class PhysicalChildRule extends RelOptRule { > > > > > > > > > > void onMatch(RelOptRuleCall call) { > > > > > > > > > > LogicalChild logicalRel = call.get(0); > > > > > > > > > > PhysicalChild physicalRel = ...; > > > > > > > > > > > > > > > > > > > > call.transformTo(physicalRel); > > > > > > > > > > optimizer.fireRules(logicalRel); > > > > > > > > > > } > > > > > > > > > > } > > > > > > > > > > > > > > > > > > > > What does the community think about such a method? Does it > > > > > > > > > > make > > > > any > > > > > > sense > > > > > > > > > > to you? If not, do you aware of any other ways on how to > > > > > > > > > > organize > > > > > > > > > bottom-up > > > > > > > > > > optimization with VolcanoPlanner without the creation of > > > > additional > > > > > > rels? > > > > > > > > > > > > > > > > > > > > If the community is OK in general, I can create try to > > > > > > > > > > create a PR > > > > > > with a > > > > > > > > > > prototype. > > > > > > > > > > > > > > > > > > > > Would appreciate your feedback. > > > > > > > > > > > > > > > > > > > > Regards, > > > > > > > > > > Vladimir. > > > > > > > > > > > > > > > > > > > > [1] > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > https://ponymail-vm.apache.org/_GUI_/thread.html/13e7ab2040bfa4902db6647992ec4203ceb0262cfcb28d38ef7e9e32@%3Cdev.calcite.apache.org%3E > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >
