Re: Trait propagation guidelines
Hi, Vladimir. As another topic, it is highly recommended that you split the aggregation in logical stages, not only for traits related matters. It is true that you need to annotate the node with different flags or subclasses and it's a large refactor. But after that, you may find much much bigger benefits. The most important benefit is aggregation pushing down. For example, the query: select t1.value, agg(t2.value) from t1 join t2 on t1.key = t2.key; You may be able to generate such plan: PhysicalAggregatePhase(group=t1.value, method=agg_final(t2.value)) Exchange(dist = t1.value) Join (t1.key = t2.key) Exchange(dist = t1.key) scan(t1) Exchange(dist = t2.key) PhysicalAggregationPhase(group = t2.key, f_partial(a)) scan(t2) The pushed "PhysicalAggregationPhase(group = t2.key, f_partial(a))" may be able to reduce the input data size of the exchange operation dramatically. There has been lots of research on aggregation push down. But partial aggregate pushing down could achieve much more benefits: 1. Unlike pushing down a full aggregation, the partial aggregate requires no extra exchanges. So it could be a pure gain. 2. The pushing down can apply to any aggregation functions, including user-defined aggregation functions. 3. By introducing the middle phase (the 3-pass aggregation implementation). Aggregation can be splitted into any number of phases and partial aggregation can be pushed down through any number of joins, somewhat like: AggregatePhase(final) Exchange AggregatePhase(middle) JOIN Exchange AggregatePhase(middle) JOIN Exchange AggregatePhase(middle) ... JOIN Exchange AggregatePhase(partial) TableScan ... Note that AggregatePhase(middle) could work in an adaptive manner: after processing some data, if it discovers no data reduction, it could just degenerate to a NOP operation and can be very light weight. Thanks, Jinpeng Wu On Sat, May 29, 2021 at 8:32 AM Haisheng Yuan wrote: > > 2) Optimization requests are basically sent to RelSet-s, not RelSubset-s, > > as we make pairwise comparisons between the requested RelSubset and other > > subsets in the set [5][6]. > > I agree with you. There could be some waste when the new delivered / > required traitset is generated by "passThrough"/ "derive", in which case, > we only need enforcer between the pair of subsets, instead of pairing with > all other required / delivered subsets in the RelSet. i.e. > In the MEMO group, we have 2 required traitsets: > 1) Hash[a] Sort[b] > 2) Hash[b] Sort[c] > > When we try to pass Hash[a] Sort[b] to one of physical operators say > Project, we found that we can pass down Hash[a] down to its child, then we > get a new physical Project with traitset Hash[a], we only need enforcer > between Hash[a] and Hash[a]Sort[b], but currently in method > "addConverters", we also generate enforcer between Hash[a] and > Hash[b]Sort[c], which is not actually what we want. > > I think it is definitely worth trying to optimize. > > Regards, > Haisheng Yuan > On 2021/05/28 19:15:03, Haisheng Yuan wrote: > > Hi Vladimir, > > > > The top-down optimizer does NOT require implementation rule to generate > 1 to 1 physical operator for a logical operator, as you can see, if you > generate a 2 phase physical aggregates for the logical aggregate in the > implementation rule, it still works. Window is special because we can > reshuffle the execution order of window functions, and that order makes a > difference according to different parent physical property request. A > single converged physical Window operator catered for this speciality. > However as I said I don't think it is a common scenario. > > > > > the whole decision of whether to go with 1-phase or 2-phase > > > aggregate is a physical decision that should be made based on > available (or > > > assumed) input traits. > > What is the problem of generating both 1-phase and 2-phase aggregates > and choose the best one based on the cost? > > > > Let's see the following query: > > select a, min(b) from (select * from foo, bar where foo.a=bar.a) t group > by a; > > suppose foo is randomly distributed fact table, and bar is randomly > distributed dimension table. > > Consider the 2 following plans: > > 1) > > PhysicalAggregate > >+-- HashJoin > > +-- HashDistribute by a > > +-- TableScan on foo > > +-- HashDistribute by a > > +-- TableScan on bar > > > > 2) > > PhysicalAggregate(global) > >+-- HashDistribute by a > > + PhysicalAggregate(local) > > + HashJoin > > +-- TableScan on
Re: Trait propagation guidelines
> 2) Optimization requests are basically sent to RelSet-s, not RelSubset-s, > as we make pairwise comparisons between the requested RelSubset and other > subsets in the set [5][6]. I agree with you. There could be some waste when the new delivered / required traitset is generated by "passThrough"/ "derive", in which case, we only need enforcer between the pair of subsets, instead of pairing with all other required / delivered subsets in the RelSet. i.e. In the MEMO group, we have 2 required traitsets: 1) Hash[a] Sort[b] 2) Hash[b] Sort[c] When we try to pass Hash[a] Sort[b] to one of physical operators say Project, we found that we can pass down Hash[a] down to its child, then we get a new physical Project with traitset Hash[a], we only need enforcer between Hash[a] and Hash[a]Sort[b], but currently in method "addConverters", we also generate enforcer between Hash[a] and Hash[b]Sort[c], which is not actually what we want. I think it is definitely worth trying to optimize. Regards, Haisheng Yuan On 2021/05/28 19:15:03, Haisheng Yuan wrote: > Hi Vladimir, > > The top-down optimizer does NOT require implementation rule to generate 1 to > 1 physical operator for a logical operator, as you can see, if you generate a > 2 phase physical aggregates for the logical aggregate in the implementation > rule, it still works. Window is special because we can reshuffle the > execution order of window functions, and that order makes a difference > according to different parent physical property request. A single converged > physical Window operator catered for this speciality. However as I said I > don't think it is a common scenario. > > > the whole decision of whether to go with 1-phase or 2-phase > > aggregate is a physical decision that should be made based on available (or > > assumed) input traits. > What is the problem of generating both 1-phase and 2-phase aggregates and > choose the best one based on the cost? > > Let's see the following query: > select a, min(b) from (select * from foo, bar where foo.a=bar.a) t group by a; > suppose foo is randomly distributed fact table, and bar is randomly > distributed dimension table. > Consider the 2 following plans: > 1) > PhysicalAggregate >+-- HashJoin > +-- HashDistribute by a > +-- TableScan on foo > +-- HashDistribute by a > +-- TableScan on bar > > 2) > PhysicalAggregate(global) >+-- HashDistribute by a > + PhysicalAggregate(local) > + HashJoin > +-- TableScan on foo > +-- Broadcast >+-- TableScan on bar > > Can you tell that the single phase aggregate plan is always better than the 2 > phase aggregate plan? > > > Therefore, the typical way to optimize > > LogicalAggregate is to split in the physical phase (implementation rule, > > pass-through, derive). Practical systems like Dremio [1] and Flink [2] > > work this way. > Dremio and Flink work this way doesn't mean it is a good way. Greenplum Orca > and Alibaba MaxCompute optimizer work in another way. In Flink and Dremio, > they have HashAggPRule to generate 1 phase HashAgg and 2 phase HashAgg, > SortAggPRule to generate 1 phase SortAgg and 2 phase SortAgg. However do you > think there is possibility that the global SortAgg combined with local > HashAgg, or the global HashAgg combined with local SortAgg may perform better > in difference cases? Are you going to generate all the 4 combinations in the > implementation rule? There are some cases we found we'd better to split the > aggregate into 3 phase aggregate [1], in which case, will the implementation > rule generate 3 HashAggs or 3 SortAggs, or all the 6 combinations? > > In our system, we have 1 phase, 2 phase, 3 phase logical aggregate rules to > transform the LogicalAggregate to another kind of logical aggregate(s) with > phase info, say LogicalXXXAggregate, then our physical aggregate rules match > this kind of node to generate HashAgg or StreamAgg. Of course, in the logical > rules, we can add business logic to guess the possible traits delivered by > child nodes to determine whether the rule definitely won't generate a better > alternative and may decide to abort this transformation early. But I would > rather let the cost model decide. > > Admittedly, the current top-down optimization is not pure on-demand request > oriented, because it will always generate a physical request regardless the > parent nodes' trait request. For example the following query in a > non-distributed environment: > select a, b, c, max(d) from foo group by a, b, c order by a desc; > > It will first generate a StreamAgg[a ASC, b ASC, c ASC] no matter what the > parent node requires, then the "passThrough" tells StreamAgg that parent > requires [a DESC], we get a StreamAgg[a
Re: Trait propagation guidelines
Hi Vladimir, The top-down optimizer does NOT require implementation rule to generate 1 to 1 physical operator for a logical operator, as you can see, if you generate a 2 phase physical aggregates for the logical aggregate in the implementation rule, it still works. Window is special because we can reshuffle the execution order of window functions, and that order makes a difference according to different parent physical property request. A single converged physical Window operator catered for this speciality. However as I said I don't think it is a common scenario. > the whole decision of whether to go with 1-phase or 2-phase > aggregate is a physical decision that should be made based on available (or > assumed) input traits. What is the problem of generating both 1-phase and 2-phase aggregates and choose the best one based on the cost? Let's see the following query: select a, min(b) from (select * from foo, bar where foo.a=bar.a) t group by a; suppose foo is randomly distributed fact table, and bar is randomly distributed dimension table. Consider the 2 following plans: 1) PhysicalAggregate +-- HashJoin +-- HashDistribute by a +-- TableScan on foo +-- HashDistribute by a +-- TableScan on bar 2) PhysicalAggregate(global) +-- HashDistribute by a + PhysicalAggregate(local) + HashJoin +-- TableScan on foo +-- Broadcast +-- TableScan on bar Can you tell that the single phase aggregate plan is always better than the 2 phase aggregate plan? > Therefore, the typical way to optimize > LogicalAggregate is to split in the physical phase (implementation rule, > pass-through, derive). Practical systems like Dremio [1] and Flink [2] > work this way. Dremio and Flink work this way doesn't mean it is a good way. Greenplum Orca and Alibaba MaxCompute optimizer work in another way. In Flink and Dremio, they have HashAggPRule to generate 1 phase HashAgg and 2 phase HashAgg, SortAggPRule to generate 1 phase SortAgg and 2 phase SortAgg. However do you think there is possibility that the global SortAgg combined with local HashAgg, or the global HashAgg combined with local SortAgg may perform better in difference cases? Are you going to generate all the 4 combinations in the implementation rule? There are some cases we found we'd better to split the aggregate into 3 phase aggregate [1], in which case, will the implementation rule generate 3 HashAggs or 3 SortAggs, or all the 6 combinations? In our system, we have 1 phase, 2 phase, 3 phase logical aggregate rules to transform the LogicalAggregate to another kind of logical aggregate(s) with phase info, say LogicalXXXAggregate, then our physical aggregate rules match this kind of node to generate HashAgg or StreamAgg. Of course, in the logical rules, we can add business logic to guess the possible traits delivered by child nodes to determine whether the rule definitely won't generate a better alternative and may decide to abort this transformation early. But I would rather let the cost model decide. Admittedly, the current top-down optimization is not pure on-demand request oriented, because it will always generate a physical request regardless the parent nodes' trait request. For example the following query in a non-distributed environment: select a, b, c, max(d) from foo group by a, b, c order by a desc; It will first generate a StreamAgg[a ASC, b ASC, c ASC] no matter what the parent node requires, then the "passThrough" tells StreamAgg that parent requires [a DESC], we get a StreamAgg[a DESC, b ASC, c ASC]. It would be ideal if we only generate StreamAgg[a DESC, b ASC, c ASC] by request, but I don't think that will make much difference, the bottleneck relies on the join order enumeration and the Project related operation. Regards, Haisheng Yuan [1] https://github.com/greenplum-db/gporca/blob/master/libgpopt/src/xforms/CXformSplitDQA.cpp On 2021/05/28 09:17:45, Vladimir Ozerov wrote: > Hi Jinpeng, Haisheng, > > Thank you for your inputs. I really appreciate that. Let me try to address > some of your comments and share some experience with the implementation of > optimizers for a distributed engine I am currently working with. > > First of all, I would argue that multiple logical operators do not have a > 1-1 mapping to physical operators, and Window is not special here. For > instance, LogicalAggregate doesn't have 1-1 mapping to physical aggregates > because the physical implementation can be either 1-phase or 2-phase. It > doesn't matter that the 2-phase aggregate is a composition of two 1-phase > aggregates: the whole decision of whether to go with 1-phase or 2-phase > aggregate is a physical decision that should be made based on available (or > assumed) input traits. > >
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Great, that is the correct way to change it and that should be the default
implementation.
On 2021/05/28 17:41:15, Vladimir Ozerov wrote:
> BTW, I tried to change the implementation to:
>
> 1: protected boolean isTransformationRule(VolcanoRuleCall match) {
> 2:return match.getRule() instanceof TransformationRule;
> 3: }
>
> It solved my problem - plans returned to normal. In the Apache Calcite
> repo, only 4 tests in the TopDowOptTest class failed due to a minor
> operator reordering.
>
> пт, 28 мая 2021 г. в 20:37, Vladimir Ozerov :
>
> > Hi Jinpeng,
> >
> > Thank you for the clarification. When I saw the code in question for the
> > first time, my first thought was that it was perhaps designed for gradual
> > migration. The main problem is that the current implementation discards
> > parts of the plan *silently*, which might be difficult to spot. I
> > only spotted the problem in my specific case because I had ~100 tests with
> > complex queries. Otherwise, I would happily proceed with the new rule
> > without knowing that I lost important parts of the search space.
> >
> > That said, I think we can do the following:
> >
> >1. Emit a warning if or even throw an exception if the transformation
> >rule produced a physical node. This should be trivial to implement - add
> > an
> >expected node type to VolcanoRuleCall (e.g., "logical", "physical",
> > "any").
> >The warning/exception should contain a proper fix suggestion - to
> > override
> >the VolcanoPlanner.isTransformationRule.
> >2. Alternatively - do a breaking change. Apache Calcite doesn't have a
> >major release cadence. It is normal practice in many products to do
> >breaking changes in minor releases. Even popular products like Mongo or
> >DataStax do it regularly. We may inform the user in the first release and
> >change to "rule instanceof TransformationRule" in the next release.
> >
> > Does it make sense?
> >
> > Regards,
> > Vladimir.
> >
> > пт, 28 мая 2021 г. в 19:33, Jinpeng Wu :
> >
> >> Hi, Vladimir. Good catch! There could be some improvements here.
> >>
> >> Actually, this problem was discovered early when the top-down rule driver
> >> was designed. At that time, no rule was annotated as "TransformationRule".
> >> Moreover, it is impossible to ask every calcite user who designed their
> >> own
> >> rules to annotate the existing code. So the top-down rule driver was
> >> designed so that it can:
> >> 1. Work in chaos: even if there are no hints for rule types, it can still
> >> work. Some opportunities may be lost, but NO failures, NO exceptions, and
> >> NO worse than the original driver. People can migrate to the new driver
> >> without concern.
> >> 2. Be Improvable: Users can refactor their code, if they want, step by
> >> step. As rule types become more and more accurate, the system achieves
> >> more
> >> and more benefits
> >> 3. Be easy to customize: the default implementation is designed for the
> >> most common cases, so that most users can benefit from it without much
> >> effort. But it is not possible to fulfill all requirements as different
> >> systems could have very different patterns to define logical and
> >> physical. That's why the isTransformationRule method is put in
> >> VolcanoPlanner and marked as protected: overwriting it can be very simple.
> >>
> >> Moreover, losing some "derive" opportunities is not as serious as
> >> imagination. As I mentioned in previous discussions, parents are in charge
> >> of raising as many requirements as possible. During "derive", if specific
> >> traits were not built by children, it means that no parents were requiring
> >> that. And if parents finally require that traits in the latter
> >> optimization, passThrough methods get called and new physical nodes are
> >> generated and "derive" get called again.
> >> I tested it on millions of queries, with or without correct rule types, in
> >> my own product. The performance of group pruning varies a lot. But the
> >> output plans are almost the same. Only one obvious exception was
> >> discovered: the spool node. That's because spool nodes cannot "passThough"
> >> parent traits (it could have multiple parents and current framework cannot
> >> handle such a situation) while it can "derive" input traits.
> >>
> >> Of course, this conclusion may not apply to your product as we could have
> >> quite different rule sets. I am just sharing some of my experiences. Maybe
> >> the current implementation of "isTransformationRule" is not good enough.
> >> If
> >> you have any better solutions, please share them.
> >>
> >> Thanks,
> >> Jinpeng Wu
> >>
> >> On Fri, May 28, 2021 at 7:10 PM Vladimir Ozerov
> >> wrote:
> >>
> >> > Hi,
> >> >
> >> > I have an optimizer that uses top-down VolcanoPlanner and has a
> >> > ConverterRule for every LogicalNode. I have a new requirement when one
> >> of
> >> > the physical rules must emit several physical nodes instead of one. I
> >> tried
> >>
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
BTW, I tried to change the implementation to:
1: protected boolean isTransformationRule(VolcanoRuleCall match) {
2:return match.getRule() instanceof TransformationRule;
3: }
It solved my problem - plans returned to normal. In the Apache Calcite
repo, only 4 tests in the TopDowOptTest class failed due to a minor
operator reordering.
пт, 28 мая 2021 г. в 20:37, Vladimir Ozerov :
> Hi Jinpeng,
>
> Thank you for the clarification. When I saw the code in question for the
> first time, my first thought was that it was perhaps designed for gradual
> migration. The main problem is that the current implementation discards
> parts of the plan *silently*, which might be difficult to spot. I
> only spotted the problem in my specific case because I had ~100 tests with
> complex queries. Otherwise, I would happily proceed with the new rule
> without knowing that I lost important parts of the search space.
>
> That said, I think we can do the following:
>
>1. Emit a warning if or even throw an exception if the transformation
>rule produced a physical node. This should be trivial to implement - add an
>expected node type to VolcanoRuleCall (e.g., "logical", "physical", "any").
>The warning/exception should contain a proper fix suggestion - to override
>the VolcanoPlanner.isTransformationRule.
>2. Alternatively - do a breaking change. Apache Calcite doesn't have a
>major release cadence. It is normal practice in many products to do
>breaking changes in minor releases. Even popular products like Mongo or
>DataStax do it regularly. We may inform the user in the first release and
>change to "rule instanceof TransformationRule" in the next release.
>
> Does it make sense?
>
> Regards,
> Vladimir.
>
> пт, 28 мая 2021 г. в 19:33, Jinpeng Wu :
>
>> Hi, Vladimir. Good catch! There could be some improvements here.
>>
>> Actually, this problem was discovered early when the top-down rule driver
>> was designed. At that time, no rule was annotated as "TransformationRule".
>> Moreover, it is impossible to ask every calcite user who designed their
>> own
>> rules to annotate the existing code. So the top-down rule driver was
>> designed so that it can:
>> 1. Work in chaos: even if there are no hints for rule types, it can still
>> work. Some opportunities may be lost, but NO failures, NO exceptions, and
>> NO worse than the original driver. People can migrate to the new driver
>> without concern.
>> 2. Be Improvable: Users can refactor their code, if they want, step by
>> step. As rule types become more and more accurate, the system achieves
>> more
>> and more benefits
>> 3. Be easy to customize: the default implementation is designed for the
>> most common cases, so that most users can benefit from it without much
>> effort. But it is not possible to fulfill all requirements as different
>> systems could have very different patterns to define logical and
>> physical. That's why the isTransformationRule method is put in
>> VolcanoPlanner and marked as protected: overwriting it can be very simple.
>>
>> Moreover, losing some "derive" opportunities is not as serious as
>> imagination. As I mentioned in previous discussions, parents are in charge
>> of raising as many requirements as possible. During "derive", if specific
>> traits were not built by children, it means that no parents were requiring
>> that. And if parents finally require that traits in the latter
>> optimization, passThrough methods get called and new physical nodes are
>> generated and "derive" get called again.
>> I tested it on millions of queries, with or without correct rule types, in
>> my own product. The performance of group pruning varies a lot. But the
>> output plans are almost the same. Only one obvious exception was
>> discovered: the spool node. That's because spool nodes cannot "passThough"
>> parent traits (it could have multiple parents and current framework cannot
>> handle such a situation) while it can "derive" input traits.
>>
>> Of course, this conclusion may not apply to your product as we could have
>> quite different rule sets. I am just sharing some of my experiences. Maybe
>> the current implementation of "isTransformationRule" is not good enough.
>> If
>> you have any better solutions, please share them.
>>
>> Thanks,
>> Jinpeng Wu
>>
>> On Fri, May 28, 2021 at 7:10 PM Vladimir Ozerov
>> wrote:
>>
>> > Hi,
>> >
>> > I have an optimizer that uses top-down VolcanoPlanner and has a
>> > ConverterRule for every LogicalNode. I have a new requirement when one
>> of
>> > the physical rules must emit several physical nodes instead of one. I
>> tried
>> > to convert a ConverterRule to a normal rule that emits physical nodes.
>> Even
>> > though the new rule has exactly the same pattern and logic as the
>> previous
>> > ConverterRule, plans changed. Analysis showed that this likely due to a
>> bug
>> > in the top-down optimizer as explained below.
>> >
>> > When optimizing a logical node, the top-down
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Hi Jinpeng, Thank you for the clarification. When I saw the code in question for the first time, my first thought was that it was perhaps designed for gradual migration. The main problem is that the current implementation discards parts of the plan *silently*, which might be difficult to spot. I only spotted the problem in my specific case because I had ~100 tests with complex queries. Otherwise, I would happily proceed with the new rule without knowing that I lost important parts of the search space. That said, I think we can do the following: 1. Emit a warning if or even throw an exception if the transformation rule produced a physical node. This should be trivial to implement - add an expected node type to VolcanoRuleCall (e.g., "logical", "physical", "any"). The warning/exception should contain a proper fix suggestion - to override the VolcanoPlanner.isTransformationRule. 2. Alternatively - do a breaking change. Apache Calcite doesn't have a major release cadence. It is normal practice in many products to do breaking changes in minor releases. Even popular products like Mongo or DataStax do it regularly. We may inform the user in the first release and change to "rule instanceof TransformationRule" in the next release. Does it make sense? Regards, Vladimir. пт, 28 мая 2021 г. в 19:33, Jinpeng Wu : > Hi, Vladimir. Good catch! There could be some improvements here. > > Actually, this problem was discovered early when the top-down rule driver > was designed. At that time, no rule was annotated as "TransformationRule". > Moreover, it is impossible to ask every calcite user who designed their own > rules to annotate the existing code. So the top-down rule driver was > designed so that it can: > 1. Work in chaos: even if there are no hints for rule types, it can still > work. Some opportunities may be lost, but NO failures, NO exceptions, and > NO worse than the original driver. People can migrate to the new driver > without concern. > 2. Be Improvable: Users can refactor their code, if they want, step by > step. As rule types become more and more accurate, the system achieves more > and more benefits > 3. Be easy to customize: the default implementation is designed for the > most common cases, so that most users can benefit from it without much > effort. But it is not possible to fulfill all requirements as different > systems could have very different patterns to define logical and > physical. That's why the isTransformationRule method is put in > VolcanoPlanner and marked as protected: overwriting it can be very simple. > > Moreover, losing some "derive" opportunities is not as serious as > imagination. As I mentioned in previous discussions, parents are in charge > of raising as many requirements as possible. During "derive", if specific > traits were not built by children, it means that no parents were requiring > that. And if parents finally require that traits in the latter > optimization, passThrough methods get called and new physical nodes are > generated and "derive" get called again. > I tested it on millions of queries, with or without correct rule types, in > my own product. The performance of group pruning varies a lot. But the > output plans are almost the same. Only one obvious exception was > discovered: the spool node. That's because spool nodes cannot "passThough" > parent traits (it could have multiple parents and current framework cannot > handle such a situation) while it can "derive" input traits. > > Of course, this conclusion may not apply to your product as we could have > quite different rule sets. I am just sharing some of my experiences. Maybe > the current implementation of "isTransformationRule" is not good enough. If > you have any better solutions, please share them. > > Thanks, > Jinpeng Wu > > On Fri, May 28, 2021 at 7:10 PM Vladimir Ozerov > wrote: > > > Hi, > > > > I have an optimizer that uses top-down VolcanoPlanner and has a > > ConverterRule for every LogicalNode. I have a new requirement when one of > > the physical rules must emit several physical nodes instead of one. I > tried > > to convert a ConverterRule to a normal rule that emits physical nodes. > Even > > though the new rule has exactly the same pattern and logic as the > previous > > ConverterRule, plans changed. Analysis showed that this likely due to a > bug > > in the top-down optimizer as explained below. > > > > When optimizing a logical node, the top-down first schedules the > > transformation rules, and then implementation rules. The logic to check > > whether the rule is transformation rule or not is located in > > VolcanoPlanner.isTransformationRule [1]. The rule scheduling logic > ensures > > that a given rule is executed either as a transformation rule, or an > > implementation rule, but not both. See TopDowRuleQueue.popMatch. The > > top-down optimizer schedules tasks in a stack. So even though the > > transformation rules are scheduled before
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Hi, Vladimir. Good catch! There could be some improvements here.
Actually, this problem was discovered early when the top-down rule driver
was designed. At that time, no rule was annotated as "TransformationRule".
Moreover, it is impossible to ask every calcite user who designed their own
rules to annotate the existing code. So the top-down rule driver was
designed so that it can:
1. Work in chaos: even if there are no hints for rule types, it can still
work. Some opportunities may be lost, but NO failures, NO exceptions, and
NO worse than the original driver. People can migrate to the new driver
without concern.
2. Be Improvable: Users can refactor their code, if they want, step by
step. As rule types become more and more accurate, the system achieves more
and more benefits
3. Be easy to customize: the default implementation is designed for the
most common cases, so that most users can benefit from it without much
effort. But it is not possible to fulfill all requirements as different
systems could have very different patterns to define logical and
physical. That's why the isTransformationRule method is put in
VolcanoPlanner and marked as protected: overwriting it can be very simple.
Moreover, losing some "derive" opportunities is not as serious as
imagination. As I mentioned in previous discussions, parents are in charge
of raising as many requirements as possible. During "derive", if specific
traits were not built by children, it means that no parents were requiring
that. And if parents finally require that traits in the latter
optimization, passThrough methods get called and new physical nodes are
generated and "derive" get called again.
I tested it on millions of queries, with or without correct rule types, in
my own product. The performance of group pruning varies a lot. But the
output plans are almost the same. Only one obvious exception was
discovered: the spool node. That's because spool nodes cannot "passThough"
parent traits (it could have multiple parents and current framework cannot
handle such a situation) while it can "derive" input traits.
Of course, this conclusion may not apply to your product as we could have
quite different rule sets. I am just sharing some of my experiences. Maybe
the current implementation of "isTransformationRule" is not good enough. If
you have any better solutions, please share them.
Thanks,
Jinpeng Wu
On Fri, May 28, 2021 at 7:10 PM Vladimir Ozerov wrote:
> Hi,
>
> I have an optimizer that uses top-down VolcanoPlanner and has a
> ConverterRule for every LogicalNode. I have a new requirement when one of
> the physical rules must emit several physical nodes instead of one. I tried
> to convert a ConverterRule to a normal rule that emits physical nodes. Even
> though the new rule has exactly the same pattern and logic as the previous
> ConverterRule, plans changed. Analysis showed that this likely due to a bug
> in the top-down optimizer as explained below.
>
> When optimizing a logical node, the top-down first schedules the
> transformation rules, and then implementation rules. The logic to check
> whether the rule is transformation rule or not is located in
> VolcanoPlanner.isTransformationRule [1]. The rule scheduling logic ensures
> that a given rule is executed either as a transformation rule, or an
> implementation rule, but not both. See TopDowRuleQueue.popMatch. The
> top-down optimizer schedules tasks in a stack. So even though the
> transformation rules are scheduled before implementation rules, the latter
> executed first.
>
> If an implementation rule produces a physical node, this node will be
> notified about input traits in the "derive" phase. In contrast,
> transformation rules produce logical nodes only, and this happens after the
> derivation of the inputs is completed. Therefore, if the top-down optimizer
> mistakenly treats an implementation rule as a transformation rule, "derive"
> will not be called on the produced physical nodes, leading to incomplete
> search space exploration.
>
> It seems, that this is exactly what happens in the current implementation.
> The VolcanoPlanner.isTransformationRule looks like this:
>
> 1: protected boolean isTransformationRule(VolcanoRuleCall match) {
> 2:if (match.getRule() instanceof SubstitutionRule) {
> 3: return true;
> 4:}
> 5:if (match.getRule() instanceof ConverterRule
> 6:&& match.getRule().getOutTrait() == rootConvention) {
> 7: return false;
> 8:}
> 9:return match.getRule().getOperand().trait == Convention.NONE
> 10:|| match.getRule().getOperand().trait == null;
> 11: }
>
> If the rule is a ConverterRule and it produces the node with the target
> convention, it is treated as an implementation rule (lines 5-6). But if the
> rule is not a ConverterRule, the method tries to deduce the rule's type
> from the incoming convention (lines 9-10). In practice, implementation
> rules either do not care about the incoming trait or expect the NONE
Re: [DISCUSS] Towards Calcite 1.27.0
I did a pass over the JIRA issues marked for 1.27.0 release.
I moved some that were promising but not close to be resolved in 1.28.0 and
for others that there was not much (or any) progress I removed the fix
version tag.
After the cleanup it seems that there are three/four issues [1] that could
possibly go in rather fast (in the next day or so).
I left some comments under each case so I am waiting for feedback to
prepare the first release candidate.
Please let me know ASAP if there is some other issue that is not in the
list [1] and needs to be in 1.27.0.
Best,
Stamatis
[1]
https://issues.apache.org/jira/secure/Dashboard.jspa?selectPageId=12333950
On Mon, May 24, 2021 at 10:10 PM Ruben Q L wrote:
> I'll pick 3-5 PRs too.
>
> Ruben
>
> On Mon, May 24, 2021 at 8:34 PM Julian Hyde
> wrote:
>
> > Thanks Rui! Just pick 5 PRs that look interesting to you, and assign the
> > JIRA to yourself (as active reviewer). If you need help/advice, mention
> > people in the JIRA comments.
> >
> > We need 4 more volunteers…
> >
> > Julian
> >
> >
> > > On May 24, 2021, at 11:28 AM, Rui Wang wrote:
> > >
> > > Please tag me on PRs that you need my help. I will check those soon.
> > >
> > >
> > > -Rui
> > >
> > > On Mon, May 24, 2021 at 11:06 AM Julian Hyde wrote:
> > >
> > >> We still need 5 committers to review 5 PRs each. Please reply to this
> > >> email to volunteer.
> > >>
> > >> On Fri, May 21, 2021 at 3:41 PM Stamatis Zampetakis <
> zabe...@gmail.com>
> > >> wrote:
> > >>>
> > >>> I agree with Julian, we should get the 1.27.0 out as soon as
> possible.
> > >>>
> > >>> I can try to prepare RC0 between the 28 and 30 of May, if people
> agree
> > on
> > >>> this.
> > >>> Alternatively, I will have a bit more time around 17 to 20 of June.
> > >>>
> > >>> I will try to get 2-3 PRs in before starting the RC.
> > >>>
> > >>> Best,
> > >>> Stamatis
> > >>>
> > >>>
> > >>> On Fri, May 21, 2021 at 9:15 PM Julian Hyde
> wrote:
> > >>>
> > Now Avatica 1.18 has been released (thanks, Francis!) we should
> press
> > >> on
> > with Calcite 1.27.
> >
> > Who is release manager? Stamatis, You volunteered to be release
> > manager
> > for 1.27 [1] but I would be happy to jump in. Let me know.
> >
> > There is a backlog of PRs that look good enough to go into 1.27. How
> > to
> > tackle these? I think we need 4 or 5 committers to each look over 4
> or
> > >> 5
> > PRs in the next few days. Please reply to this email if you are
> > >> prepared to
> > help.
> >
> > Julian
> >
> > [1]
> >
> > >>
> >
> https://lists.apache.org/thread.html/re5702a648df18f56e786d770cdce86101164ae419eee94ae947652d4%40%3Cdev.calcite.apache.org%3E
> >
> > On 2021/03/09 14:29:16, Stamatis Zampetakis
> > wrote:
> > > Many thanks for moving this forward Julian, much appreciated.
> > >
> > > At the moment the main blocker is the Avatica release ([1,2]) that
> in
> > turn
> > > waits for CALCITE-4503 [3].
> > > It would be great if somebody has some cycles to review and merge
> the
> > > respective PR [4].
> > >
> > > Best,
> > > Stamatis
> > >
> > > [1] https://issues.apache.org/jira/browse/CALCITE-4528
> > > [2] https://issues.apache.org/jira/browse/CALCITE-4488
> > > [3] https://issues.apache.org/jira/browse/CALCITE-4503
> > > [4] https://github.com/apache/calcite-avatica/pull/138
> > >
> > > On Sun, Feb 28, 2021 at 2:22 AM Julian Hyde
> > >> wrote:
> > >
> > >> Vladimir,
> > >>
> > >> Thanks for finding this bug. Please log it.
> > >>
> > >> I don't intend to fix any more bugs in this area before 1.27. It
> > >> has
> > >> been a huge effort on my part, and I have not received any help
> > >> from
> > >> anyone.
> > >>
> > >> Julian
> > >>
> > >> On Wed, Feb 24, 2021 at 3:57 PM Vladimir Sitnikov
> > >> wrote:
> > >>>
> > >>> Thanks for pushing this forward.
> > >>>
> > >>> Would you please add search/sarg shrinking to RexShrinker?
> > >>>
> > >>> There are failures though:
> > >>>
> > >>> @Test void singleFuzzyTest() {
> > >>>Random r = new Random();
> > >>>r.setSeed(6321443803263498676L);
> > >>>RexFuzzer fuzzer = new RexFuzzer(rexBuilder, typeFactory);
> > >>>generateRexAndCheckTrueFalse(fuzzer, r);
> > >>> }
> > >>>
> > >>> yields
> > >>>
> > >>> $node isAlwaysTrue, so it should simplify to TRUE unknownAsFalse
> > >>>
> > >>> SEARCH(-(COALESCE(?0.int0, CASE(=(CASE(false,
> > >> SEARCH(?0.notNullInt0,
> > >>> Sarg[(0..2]; NULL AS FALSE]), true), NOT(IS NOT TRUE(false))),
> > >> -(+(100500),
> > >>> -(CASE(true, 1, 100500), CASE(=(?0.notNullBool0,
> > >> ?0.notNullBool0),
> > >>> null:INTEGER, ?0.notNullInt1))), CASE(=(COALESCE(0, ?0.int1),
> > >> 1), 1,
> > >>> =(COALESCE(0, ?0.int1), -(null, ?0.int1)), CASE(?0.notNullBool0,
> >
Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Hi,
I have an optimizer that uses top-down VolcanoPlanner and has a
ConverterRule for every LogicalNode. I have a new requirement when one of
the physical rules must emit several physical nodes instead of one. I tried
to convert a ConverterRule to a normal rule that emits physical nodes. Even
though the new rule has exactly the same pattern and logic as the previous
ConverterRule, plans changed. Analysis showed that this likely due to a bug
in the top-down optimizer as explained below.
When optimizing a logical node, the top-down first schedules the
transformation rules, and then implementation rules. The logic to check
whether the rule is transformation rule or not is located in
VolcanoPlanner.isTransformationRule [1]. The rule scheduling logic ensures
that a given rule is executed either as a transformation rule, or an
implementation rule, but not both. See TopDowRuleQueue.popMatch. The
top-down optimizer schedules tasks in a stack. So even though the
transformation rules are scheduled before implementation rules, the latter
executed first.
If an implementation rule produces a physical node, this node will be
notified about input traits in the "derive" phase. In contrast,
transformation rules produce logical nodes only, and this happens after the
derivation of the inputs is completed. Therefore, if the top-down optimizer
mistakenly treats an implementation rule as a transformation rule, "derive"
will not be called on the produced physical nodes, leading to incomplete
search space exploration.
It seems, that this is exactly what happens in the current implementation.
The VolcanoPlanner.isTransformationRule looks like this:
1: protected boolean isTransformationRule(VolcanoRuleCall match) {
2:if (match.getRule() instanceof SubstitutionRule) {
3: return true;
4:}
5:if (match.getRule() instanceof ConverterRule
6:&& match.getRule().getOutTrait() == rootConvention) {
7: return false;
8:}
9:return match.getRule().getOperand().trait == Convention.NONE
10:|| match.getRule().getOperand().trait == null;
11: }
If the rule is a ConverterRule and it produces the node with the target
convention, it is treated as an implementation rule (lines 5-6). But if the
rule is not a ConverterRule, the method tries to deduce the rule's type
from the incoming convention (lines 9-10). In practice, implementation
rules either do not care about the incoming trait or expect the NONE trait.
Therefore, it seems that currently, the top-down optimizer treats many
implementation rules as physical rules, and as a result, cannot notify
physical nodes produced from these rules about trait derivation.
This explains why in my case everything was ok when all implementation
rules were ConverterRules, and why I lost some optimal plans when the rule
was refactored to a non-converter variant.
Do you agree that this a bug? If yes, shouldn't we refactor that code to
just check whether the rule is an instance of TransformationRule? Since
this is a breaking change, we may add a special flag that preserves the old
behavior by default but allows for the new behavior to overcome the
aforementioned problem.
Regards,
Vladimir.
[1]
https://github.com/apache/calcite/blob/calcite-1.26.0/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoPlanner.java#L1398-L1408
Re: Trait propagation guidelines
Hi Jinpeng, Haisheng, Thank you for your inputs. I really appreciate that. Let me try to address some of your comments and share some experience with the implementation of optimizers for a distributed engine I am currently working with. First of all, I would argue that multiple logical operators do not have a 1-1 mapping to physical operators, and Window is not special here. For instance, LogicalAggregate doesn't have 1-1 mapping to physical aggregates because the physical implementation can be either 1-phase or 2-phase. It doesn't matter that the 2-phase aggregate is a composition of two 1-phase aggregates: the whole decision of whether to go with 1-phase or 2-phase aggregate is a physical decision that should be made based on available (or assumed) input traits. Consider the following logical tree: LogicalAggregate[group=$0, agg=SUM($1)] Input If I do the split on the logical phase with a separate transformation rule, I will get the following tree: LogicalAggregate[group=$0, agg=SUM($1)] LogicalAggregate[group=$0, agg=SUM($1)] Input Now we have an infinite loop because the rule takes one aggregate and produces two aggregates. To fix that, we may extend the LogicalAggregate with some flag or so. But this (1) potentially breaks other LogicalAggregate optimizations (e.g., transpose with other operators), and (2) breaks the whole idea of the logical operators because the execution phase (pre-aggregate of final aggregate) is a property of concrete backend, not a property of relational algebra. Therefore, the typical way to optimize LogicalAggregate is to split in the physical phase (implementation rule, pass-through, derive). Practical systems like Dremio [1] and Flink [2] work this way. That said, as an optimizer developer, I need the flexibility to emit any physical trees for the given logical operator, and 1-1 mapping cannot be assumed. Calcite's API allows for that, and I am not aware of formal documentation or guidelines that discourage that. Now the question when exactly to emit the operators. Normally, we produce operators from rules. As discussed above, if the logical operator may produce different physical trees depending on input traits, the recommendation is to emit all combinations, even though we do not know whether there would be good inputs for that alternatives. This contradicts the idea of the guided top-down search, where we explore the search space in response to a concrete optimization request, rather than with a pessimistic assumption that a certain plan might be required in the future. I found a way to mitigate this problem partially. Funny, my solution is almost similar to what Haisheng proposed for the Window operator. 1. For every logical operator, I emit a single physical operator from the implementation rule, maintaining the exact 1-1 mapping. The emitted operators (1) have a special flag "template" which makes their const infinite, (2) never exposes or demands non-default traits except for convention, (3) have OMAKASE derivation mode. 2. When the input is optimized, the "derive" is called on the template, which produces the concrete physical tree, that is not necessarily 1-1 to the original logical node. Before rule: LogicalAggregate[group=$0, agg=SUM($1)] LogicalInput After rule: PhysicalAggregate[group=$0, agg=SUM($1), template=true, cost=infinite] LogicalInput After "derive" if the input is not shared on $0: PhysicalAggregate[group=$0, agg=SUM($1)] Exchange PhysicalAggregate[group=$0, agg=SUM($1)] PhysicalInputNotSharded After "derive" if the input is shared on $0: PhysicalAggregate[group=$0, agg=SUM($1)] PhysicalInputNotSharded This approach allows me to avoid the generation of unnecessary alternatives by delaying the optimization to derive phase. The aggregate split is implemented in rules in Dremio/Flink, but in my case, this logic migrates to "derive". This solution worked well for the whole TPC-DS suite until we wanted to optimize combinations of operators rather than individual operators. A good example is TPC-DS query 1 [3]. During the logical optimization, we get the following logical tree, which is exactly the case that I demonstrated at the beginning of this mail thread: G1: Aggregate(groupBy=[ctr_store_sk]) G2: Aggregate(groupBy=[ctr_customer_sk, ctr_store_sk] And this is where I got stuck. I need to do a simple thing - propagate an optimization request from G1 to G2, informing G2 that it should consider the distribution [ctr_store_sk]. I can deliver that request to my physical template in G2 through "convert". But the problem is that the current Calcite implementation doesn't allow me to satisfy this request later on in the derivation stage. Instead, I am forced to emit the final execution tree from the "passThrough" method, which will not be notified at the derivation stage. I prepared a scheme [4] that demonstrates the problem. It feels that I almost achieved what I need. The last step is to ensure that "derive" is called
[jira] [Created] (CALCITE-4625) Release Calcite 1.27.0
Stamatis Zampetakis created CALCITE-4625: Summary: Release Calcite 1.27.0 Key: CALCITE-4625 URL: https://issues.apache.org/jira/browse/CALCITE-4625 Project: Calcite Issue Type: Task Reporter: Stamatis Zampetakis Assignee: Stamatis Zampetakis Fix For: 1.27.0 Issue to track 1.27.0 release -- This message was sent by Atlassian Jira (v8.3.4#803005)
Deduplicate correlate variables question.
Hi, calciters ) I am trying to figure out why DeduplicateCorrelateVariables [1] is called only if withExpand [2] flag is true ? Why we don`t need to deduplicate in appropriate case ? [1] https://github.com/apache/calcite/blob/master/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java#L2881 [2] https://github.com/apache/calcite/blob/master/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java#L6209 Thanks !
