Hi Stamatis, Thank you for the idea about Hive. I looked at it some time ago and the codebase was substantially more complex to understand for me than in other projects, so I gave up. I'll try to do the analysis again. I'd like to mention that I also had a thought that maybe the implementation of a top-down optimization is not a concern of VolcanoPlanner, and the brand new planner may play well here. But from a practical perspective, of course, I keep a hope that we will find a less intrusive way to introduce efficient physical optimization into VolcanoPlanner :-)
Regards, Vladimir. вс, 8 дек. 2019 г. в 12:42, Stamatis Zampetakis <[email protected]>: > Thanks Vladimir for this great summary. It is really helpful to know how > the different projects use the optimizer and it certainly helps to identify > limitations on our implementation. > > I cannot provide any valuable feedback at the moment since I have to find > some time to read more carefully your analysis. > > In the meantime, I know that Hive is also using Calcite for quite some time > now so maybe you can get some new ideas (or complete your background study) > by looking in their code. > > @Haisheng: I think many people did appreciate the discussion for pull up > traits so I wouldn't say that we abandoned it. I had the impression that we > were waiting a design doc. > > In general it may not be feasible to cover all use cases with a single > optimizer. I wouldn't find it bad to introduce another planner if there are > enough reasons to do so. > > Best, > Stamatis > > > On Fri, Dec 6, 2019, 11:00 AM Vladimir Ozerov <[email protected]> wrote: > > > "all we know is their *collations*" -> "all we know is their *traits*" > > > > пт, 6 дек. 2019 г. в 12:57, Vladimir Ozerov <[email protected]>: > > > > > Hi Haisheng, > > > > > > Thank you for your response. Let me elaborate my note on join planning > > > first - what I was trying to say is not that rules on their own have > some > > > deficiencies. What I meant is that with current planner implementation, > > > users tend to separate join planning from the core optimization process > > > like this in the pseudo-code below. As a result, only one join > > permutation > > > is considered during physical planning, even though join rule may > > > potentially generate multiple plans worth exploring: > > > > > > RelNode optimizedLogicalNode = doJoinPlanning(logicalNode); > > > RelNode physicalNode = doPhysicalPlanning(optimizedLogicalNode); > > > > > > Now back to the main question. I re-read your thread about on-demand > > trait > > > propagation [1] carefully. I'd like to admit that when I was reading it > > for > > > the first time about a month ago, I failed to understand some details > due > > > to poor knowledge of different optimizer architectures. Now I > understand > > it > > > much better, and we definitely concerned with exactly the same > problem. I > > > feel that trait pull-up might be a step in the right direction, > however, > > it > > > seems to me that it is not the complete solution. Let me try to explain > > why > > > I think so. > > > > > > The efficient optimizer should try to save CPU as much as possible > > because > > > it allows us to explore more plans in a sensible amount of time. To > > achieve > > > that we should avoid redundant operations, and detect and prune > > inefficient > > > paths aggressively. As far as I understand the idea of trait pull-up, > we > > > essentially explore the space of possible physical properties of > children > > > nodes without forcing their implementation. But after that, the Calcite > > > will explore that nodes again, now in order to execute implementation > > > rules. I.e. we will do two dives - one to enumerate the nodes (trait > > > pull-up API), and the other one to implement them (implementation > rules), > > > while in Cascades one dive should be sufficient since exploration > invokes > > > the implementation rules as it goes. This is the first issue I see. > > > > > > The second one is more important - how to prune inefficient plans? > > > Currently, nodes are implemented independently and lack of context > > doesn't > > > allow us to estimates children's costs when implementing the parent, > > hence > > > branch-and-bound is not possible. Can trait pull-up API > > "List<RelTraitSet> > > > deriveTraitSets(RelNode, RelMetadataQuery)" help us with this? If the > > > children nodes are not implemented before the pull-up, all we know is > > their > > > collations, but not their costs. And without costs, pruning is not > > > possible. Please let me know if I missed something from the proposal. > > > > > > The possible architecture I had in mind after reading multiple papers, > > > which may answer all our questions, could look like this: > > > 1) We have a queue of nodes requiring optimization. Not a queue of > rules. > > > initial queue state is formed from the initial tree, top-down. > > > 2) The node is popped from the queue, and we enter > > > "node.optimize(maxCost)" call. It checks for matching rules, > prioritizes > > > them, and start their execution on by one. Execution of rules may > > re-insert > > > the current node into the queue, in which case this step is repeated, > > > possibly many times > > > 3) Logical-logical rules (transformations) produce new logical nodes > and > > > put them into the queue for further optimization > > > 4) Logical-physical rules (implementation) do the following: > > > 4.1) Costs of logical children are estimated. The cost of a logical > node > > > should be less than any cost of a possible physical node that may be > > > produced out of it. If the logical cost exceeds "maxCost", we stop and > > > return. The whole logical subspace is pruned even before exploration. > > > 4.2) Recursively call "childNode.optimize(maxCost - > currentLogicalCost)" > > > method, which returns a set of possible physical implementations of a > > > child. Returned physical children are already registered in proper > > > set/subset, but are not used for any pattern-matching, and doesn't > > trigger > > > more rule calls! > > > 4.3) Implementation rule checks the cost of the physical child. If it > is > > > greater than any other already observed child with the same traits, or > > > exceeds the "maxCost", it is discarded. Otherwise, the physical > > > implementation of the current node is produced and registered in the > > > optimizer. > > > > > > The pseudocode for physical implementation flow for join (two inputs): > > > > > > Collection<RelNode> optimizePhysical(Cost maxCost) { > > > // Estimated minimal self-cost. Any physical implementation of this > > > node should have greater self-cost > > > Cost logicalSelfCost = optimizer.getCost(this); > > > > > > // *Pruning #1*: whatever children we implement, the total cost > will > > > be greater than the passed maxCost, so do not explore further > > > Cost maxChildCost = maxCost - logicalSelfCost; > > > > > > Cost logicalILeftCost = optimizer.getCost(leftLogicalNode); > > > Cost logicalRightCost = optimizer.getCost(rightLogicalNode); > > > > > > if (logicalLeftCost + logicalRightCost > maxChildCost) { > > > return; > > > } > > > > > > // This is our equivalence set. > > > RelSet equivalenceSet = this.getSet(); > > > > > > // Get promising physical implementations of child nodes > recursively > > > List<RelNode> leftPhysicalNodes = > > > leftLogicalNode.optimizePhysical(maxChildCost); > > > List<RelNode> rightPhysicalNodes = > > > rightLigicalNode.optimizePhysical(maxChildCost); > > > > > > for (RelNode leftPhysicalNode : leftPhysicalNodes) { > > > for (RelNode rightPhysicalNode : rightPhysicalNodes) { > > > // *Pruning #2*: Combination of physical input costs is > > > already too expensive, give up > > > Cost physicalLeftCost = > optimizer.getCost(leftPhysicalNode); > > > Cost physicalRightCost = > > optimizer.getCost(rightPhysicalNode); > > > > > > if (logicalILeftCost + logicalRightCost > maxChildCost) { > > > continue. > > > } > > > > > > // Implement possible physical nodes for the given pair of > > > inputs (maybe more than one) > > > List<RelNode> physicalJoins = implement(leftPhysicalNode, > > > rightPhysicalNode); > > > > > > for (RelOptRule physicalJoin : physicalJoins) { > > > // *Pruning #3*: Do not consider implementation if we > have > > > another one with the same trait set and smaller cost) > > > Cost physicalJoinCost = > optimizer.getCost(physicalJoin); > > > Cost bestCostForTraitSet = > > > equivalenceSet.getBestCost(physicalJoin.getTraitSet()); > > > > > > if (physicalJoinCost > bestCostForTraitSet) { > > > continue. > > > } > > > > > > // This is a good implementation. Register it in the > set, > > > updating per-traitset best costs. > > > equivalenceSet.register(physicalJoin); > > > } > > > } > > > } > > > > > > // Return the best registered expressions with different traitsets > > > from the current set. > > > return equivalenceSet.getBestExps(); > > > } > > > > > > This is a very rough pseudo-code, only to demonstrate the basic idea on > > > how proper bottom-up propagation not only helps us set proper traits > for > > > the new physical node but also ensures that not optimal plans are > pruned > > as > > > early as possible. Real implementation should be better abstracted and > > > accept enforcers as well. > > > > > > Also, please notice that the pseudo-code doesn't show when logical > rules > > > are fired. This is a separate question. One possible straightforward > way > > is > > > to add the aforementioned physical routine to normal Volcano flow: > > > 1) Fire logical rule on a node and register new nodes > > > 2) Fire physical optimization as shown above, then invoke > > > "call.transformTo()" for every returned physical rel > > > 3) Re-trigger the process for newly created nodes and their parents > > > > > > A better approach is to interleave logical and physical optimizations, > so > > > they trigger each other recursively. But this would require a serious > > > redesign of a "rule queue" concept. > > > > > > Does it have any common points with your proposal? > > > > > > Regards, > > > Vladimir. > > > > > > [1] > > > > > > https://ponymail-vm.apache.org/_GUI_/thread.html/79dac47ea50b5dfbd3f234e368ed61d247fb0eb989f87fe01aedaf25@%3Cdev.calcite.apache.org%3E > > > > > > > > > пт, 6 дек. 2019 г. в 05:41, Haisheng Yuan <[email protected]>: > > > > > >> Oh, I forgot to mention that the join planning/reordering is not a big > > >> problem. Calcite just use the rule to generate a single alternative > > plan, > > >> which is not ideal. But we can't say Calcite is doing wrong. > > >> > > >> Ideally, we expect it generates multiple (neither all, nor single) > > >> bipartie graphs. The join reordering rule will cut each part into > > bipartie > > >> recursively and apply JoinCommutativity rule to generate more > > alternatives > > >> for each RelSet. It is just a different strategy. We can modify the > > rule, > > >> or create new join reordering rule to generate multiple plan > > >> alternatives. > > >> > > >> - Haisheng > > >> > > >> ------------------------------------------------------------------ > > >> 发件人：Haisheng Yuan<[email protected]> > > >> 日 期：2019年12月06日 09:07:43 > > >> 收件人：Vladimir Ozerov<[email protected]>; [email protected] ( > > >> [email protected])<[email protected]> > > >> 主 题：Re: Re: Volcano's problem with trait propagation: current state > and > > >> future > > >> > > >> Generally agree with what Vladimir said. I think what Calcite has is > > >> logical optimization or exploration, there are almost no physical > > >> optimization, Calcite leaves it to third party implementators. One of > my > > >> friends at University of Wisconsin–Madison database research group > told > > me > > >> that they gave up the idea of using Calcite in their project due to > this > > >> reason. > > >> > > >> Currently physical properties are requested in implementation rules, > or > > >> even logical exploration rules, But each rule is independent, the > > >> pattern-matched expression is not aware of what does the parent > operator > > >> want. Using AbstractConverter doesn't help, and is not promising. > > >> > > >> >> You shouldn't regiester all logical rules in the planner > > >> simultaneously,... as Drill does. > > >> That is because Calcite does too many redundant or duplicate rule > > >> matching, like all kinds of transpose (can't be avoided due to current > > >> design), matching physical operators. > > >> > > >> >> decoupling the logical planning from the physical one looks > > >> a bit weird to me because it violates the idea of Cascades framework. > > >> Orca optimizer fully adopted the design principle of Cascades > framework > > >> except that it separates into 3 phases: logical exploration, physical > > >> implementation, and optimization (property enforcing). And it might be > > >> easier if we want to enable parallel optimization by seperating into 3 > > >> phases. Orca does branch-and-bound in optimization phase, before > actual > > >> property derivation and enforcement, IIRC. It is highly efficient, > works > > >> pretty well, and battlefield-tested by many large financial and > > insurance > > >> companies. > > >> > > >> In my last thread about on-demand trait request, I gave the high-level > > >> general API for physical operators to derive and require physical > > >> properties, which is similar to Orca's design. But seems like the > > proposal > > >> of API change gets no love. > > >> > > >> - Haisheng > > >> > > >> ------------------------------------------------------------------ > > >> 发件人：Vladimir Ozerov<[email protected]> > > >> 日 期：2019年12月05日 22:22:43 > > >> 收件人：[email protected] ([email protected])< > > >> [email protected]> > > >> 主 题：Re: Volcano's problem with trait propagation: current state and > > future > > >> > > >> AbstractConverter-s are attractive because they effectively emulate > > >> straightforward recursive top-down optimization (Volcano/Cascades). > But > > >> instead of doing it with a recursive method call, which preserves the > > >> context, we do this in Calcite as a sequence of unrelated rule calls, > > thus > > >> losing the context. So with my current understanding, it could be > > thought > > >> of not as a search space explosion, but rather than the inefficient > > >> implementation of an otherwise straightforward parent->child->parent > > >> navigation, since we achieve this navigation indirectly through the > rule > > >> queue, rather than through a normal method call. In any case, the net > > >> result is wasted CPU. Perhaps this is not exponential waste, but some > > >> multiplication of otherwise optimal planning. As I mentioned, in our > > >> experiments with TPC-H, we observed a constant factor between 6-9x > > between > > >> the number of joins and the number of join implementation rule > > >> invocations. > > >> It doesn't growth past 9 even for complex queries, so I hope that this > > is > > >> not an exponent :-) > > >> > > >> Speaking of logical vs physical optimization, IMO it makes sense in > some > > >> cases. E.g. when doing predicate pushdown, you do not want to consider > > >> intermediate logical tree states for implementation, until the > predicate > > >> reaches its final position. So running separate logical planning phase > > >> with > > >> Volcano optimizer makes total sense to me, because it effectively > > prunes a > > >> lot of not optimal logical plans before they reach the physical > planning > > >> stage. The real problem to me is that we forced to remove join > planning > > >> from the physical optimization stage. Because the goal of join > planning > > >> not > > >> to generate a single optimal plan, like with predicate pushdown, but > > >> rather > > >> to generate a set of logical plans all of which should be implemented > > and > > >> estimated. And with AbstractConverter-s this is not possible because > of > > >> their multiplicator increases the rate of search space growth, making > > join > > >> planning inapplicable even for the small number of relations. So we > have > > >> to > > >> move them to the logical planning stage and pick only one permutation > > for > > >> physical planning. > > >> > > >> > > >> чт, 5 дек. 2019 г. в 15:35, Roman Kondakov <[email protected] > > >: > > >> > > >> > Vladimir, > > >> > > > >> > thank you for bringing it up. We are facing the same problems in > > Apache > > >> > Ignite project > > >> > and it would be great if Apache Calcite community will propose a > > >> > solution for this > > >> > issue. > > >> > > > >> > From my point of view an approach with abstract converters looks > more > > >> > promising, but as > > >> > you mentioned it suffers from polluting the search space. The latter > > can > > >> > be mitigated by > > >> > splitting a planning stage into the several phases: you shouldn't > > >> > register all logical rules in the planner simultaneously - it looks > > like > > >> > it is better to have several iterations of planning stage with > > different > > >> > sets of rules, as Drill does. > > >> > > > >> > Also I'd like to mention that decoupling the logical planning from > the > > >> > physical one looks > > >> > a bit weird to me because it violates the idea of Cascades > framework. > > >> > Possibly this decoupling is the consequence of some performance > > issues. > > >> > > > >> > > > >> > -- > > >> > Kind Regards > > >> > Roman Kondakov > > >> > > > >> > On 05.12.2019 14:24, Vladimir Ozerov wrote: > > >> > > Hi, > > >> > > > > >> > > As I mentioned before, we are building a distributed SQL engine > that > > >> uses > > >> > > Apache Calcite for query optimization. The key problem we faced is > > the > > >> > > inability to pull the physical traits of child relations > > efficiently. > > >> I'd > > >> > > like to outline my understanding of the problem (I guess it was > > >> already > > >> > > discussed multiple times) and ask the community to prove or > disprove > > >> the > > >> > > existence of that problem and its severity for the products which > > uses > > >> > > Apache Calcite and ask for ideas on how it could be improved in > the > > >> > future. > > >> > > > > >> > > I'll start with the simplified problem description and mentioned > > more > > >> > > complex use cases then. Consider that we have a logical tree and a > > >> set of > > >> > > implementation rules. Our goal is to find the optimal physical > tree > > by > > >> > > applying these rules. The classical Cascades-based approach > directs > > >> the > > >> > > optimization process from the top to the bottom (hence > "top-down"). > > >> > > However, the actual implementation of tree nodes still happens > > >> bottom-up. > > >> > > For the tree L1 <- L2, we enter "optimize(L1)", which recursively > > >> > delegates > > >> > > to "optimize(L2)". We then implement children nodes L1 <- [P2', > > P2''], > > >> > and > > >> > > return back to the parent, which is now able to pick promising > > >> > > implementations of the children nodes and reject bad ones with the > > >> > > branch-and-bound approach. AFAIK Pivotal's Orca works this way. > > >> > > > > >> > > The Apache Calcite is very different because it doesn't allow the > > >> > recursion > > >> > > so that we lose the context on which node requested the child > > >> > > transformation. This loss of context leads to the following > > problems: > > >> > > 1) The parent node cannot deduce it's physical properties during > the > > >> > > execution of the implementation rule, because Calcite expects the > > >> > > transformation to be applied before children nodes are > implemented. > > >> That > > >> > is > > >> > > if we are optimizing LogicalProject <- LogicalScan, we cannot set > > >> proper > > >> > > distribution and collation for the to be created PhysicalProject, > > >> because > > >> > > it depends on the distribution and collation of the children which > > is > > >> yet > > >> > > to be resolved. > > >> > > 2) The branch-and-bound cannot be used because it requires at > least > > >> one > > >> > > fully-built physical subtree. > > >> > > > > >> > > As a result of this limitation, products which rely on Apache > > Calcite > > >> for > > >> > > query optimization, use one or several workarounds: > > >> > > > > >> > > *1) Guess the physical properties of parent nodes before logical > > >> children > > >> > > are implemented* > > >> > > *Apache Flink* uses this strategy. The strategy is bad because of > > the > > >> > > number of combinations of traits growth exponentially with the > > number > > >> of > > >> > > attributes in the given RelNode, so you either explode the search > > >> space > > >> > or > > >> > > give up optimization opportunities. Consider the following tree: > > >> > > LogicalSort[a ASC] <- LogicalFilter <- LogicalScan > > >> > > The optimal implementation of the LogicalFilter is > > >> > PhysicalFilter[collation=a > > >> > > ASC] because it may eliminate the parent sort. But such > optimization > > >> > should > > >> > > happen only if we know that there is a physical implementation of > > scan > > >> > > allowing for this sort order, e.g. PhysicalIndexScan[collation=a > > ASC]. > > >> > I.e. > > >> > > we need to know the child physical properties first. Otherwise we > > >> > fallback > > >> > > to speculative approaches. With the *optimistic* approach, we emit > > all > > >> > > possible combinations of physical properties, with the hope that > the > > >> > child > > >> > > will satisfy some of them, thus expanding the search space > > >> exponentially. > > >> > > With the *pessimistic* approach, we just miss this optimization > > >> > opportunity > > >> > > even if the index exists. Apache Flink uses the pessimistic > > approach. > > >> > > > > >> > > *2) Use AbstractConverters* > > >> > > *Apache Drill* uses this strategy. The idea is to "glue" logical > and > > >> > > physical operators, so that implementation of a physical child > > >> > re-triggers > > >> > > implementation rule of a logical parent. The flow is as follows: > > >> > > - Invoke parent implementation rule - it either doesn't produce > new > > >> > > physical nodes or produce not optimized physical nodes (like in > the > > >> > Apache > > >> > > Flink case) > > >> > > - Invoke children implementation rules and create physical > children > > >> > > - Then converters kick-in and re-trigger parent implementation > rule > > >> > through > > >> > > the creation of an abstract converter > > >> > > - Finally, the parent implementation rule is fired again and now > it > > >> > > produces optimized node(s) since at least some of the physical > > >> > > distributions of children nodes are implemented. > > >> > > > > >> > > Note that this is essentially a hack to simulate the Cascades > flow! > > >> The > > >> > > problem is that AbstractConverters increase the complexity of > > planning > > >> > > because they do not have any context, so parent rules are just > > >> > re-triggered > > >> > > blindly. Consider the optimization of the following tree: > > >> > > LogicalJoin <- [LogicalScan1, LogicalScan2] > > >> > > With the converter approach, the join implementation rule will be > > >> fired > > >> > at > > >> > > least 3 times, while in reality, one call should be sufficient. In > > our > > >> > > experiments with TPC-H queries, the join rule implemented that way > > is > > >> > > typically called 6-9 times more often than expected. > > >> > > > > >> > > *3) Transformations (i.e. logical optimization) are decoupled from > > >> > > implementation (i.e. physical optimization)* > > >> > > Normally, you would like to mix both logical and physical rules > in a > > >> > single > > >> > > optimization program, because it is required for proper planning. > > That > > >> > is, > > >> > > you should consider both (Ax(BxC)) and ((AxB)xC) join ordering > > during > > >> > > physical optimization, because you do not know which one will > > produce > > >> the > > >> > > better plan in advance. > > >> > > But in some practical implementations of Calcite-based optimizers, > > >> this > > >> > is > > >> > > not the case, and join planning is performed as a separate HEP > > stage. > > >> > > Examples are Apache Drill and Apache Flink. > > >> > > I believe that lack of Cascades-style flow and branch-and-bound > are > > >> among > > >> > > the main reasons for this. At the very least for Apache Drill, > since > > >> it > > >> > > uses converters, so additional logical permutations will > > exponentially > > >> > > multiply the number of fired rules, which is already very big. > > >> > > > > >> > > Given all these problems I'd like to ask the community to share > > >> current > > >> > > thoughts and ideas on the future improvement of the Calcite > > optimizer. > > >> > One > > >> > > of the ideas being discussed in the community is "Pull-up Traits", > > >> which > > >> > > should allow the parent node to get physical properties of the > > >> children > > >> > > nodes. But in order to do this, you effectively need to implement > > >> > children, > > >> > > which IMO makes this process indistinguishable from the classical > > >> > recursive > > >> > > Cascades algorithm. > > >> > > > > >> > > Have you considered recursive transformations as an alternative > > >> solution > > >> > to > > >> > > that problem? I.e. instead of trying to guess or pull the physical > > >> > > properties of non-existent physical nodes, go ahead and actually > > >> > implement > > >> > > them directly from within the parent rule? This may resolve the > > >> problem > > >> > > with trait pull-up, as well as allow for branch-and-bound > > >> optimization. > > >> > > > > >> > > I would appreciate your feedback or any hints for future research. > > >> > > > > >> > > Regards, > > >> > > Vladimir. > > >> > > > > >> > > > >> > > >> > > >> > > >
