Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Please disregard this email. I sent it to the wrong thread, sorry.
вс, 13 июн. 2021 г. в 19:56, Vladimir Ozerov :
> Hi,
>
> I tried to apply different approaches, but eventually, I failed to achieve
> my goals. It seems that the current implementation cannot handle the
> required scenario, as explained below.
>
> Consider the following tree:
> LogicalAggregate1[group=[b,c]]
> LogicalAggregate2[group=[a,b,c]]
> LogicalInput
>
> I want to find the plan to do these two aggregations without an exchange
> in between because they may have compatible distributions. Example:
> PhysicalAggregate1[group=[b,c]] // SHARDED[b,c]
> PhysicalAggregate2[group=[a,b,c]] // SHARDED[b,c]
> Exchange// SHARDED[b,c]
> PhysicalInput // SHARDED[?]
>
> The fundamental problem is that it is impossible to save the optimization
> request and resolve traits in the "derive" phase afterward. What we need is
> to send the optimization request "SHARDED by [b,c] in any order" to
> PhysicalAggregate2, and use it in the derive phase so that the new
> PhysicalAggregate2 is created with [b,c] or [c,b], but strictly without
> [a]. Unfortunately, this doesn't work because the nodes emitted from the
> pass-through do not participate in the "derive" phase.
>
> This could be fixed with a trivial change - to allow certain nodes emitted
> from the "passThrough" to participate in "derive". We can do that using a
> marker interface or an extension to a PhysicalRel interface. For example:
> interface PhysicalRel {
> boolean enforceDerive();
> }
>
> When set to "true", the node would not be added to the pass-through cache.
> This way, we may use this node as *storage* for the optimization request.
> When the "derive" is called later, we know both the parent requirements and
> the child traits. This would be sufficient to solve my problem. I already
> tried to do this by disabling the pass-through cache completely and
> confirmed that the required plan is found.
>
> Do you have any objections to such a change?
>
> Regards,
> Vladimir.
>
>
> вс, 30 мая 2021 г. в 12:54, Jinpeng Wu :
>
>> Hi, Vladimir. I mean the error part only. I am comfortable with the other
>> changes.
>>
>> If changing isTransformationRule could have unexpected consequences, one
>> possible way is reserving current logic and only adding a newline checking
>> the "implements TransformationRule''. Even though we remove the original
>> logic completely, users who prefer legacy logic to avoid risks can
>> overwrite the method by simply copying several lines of code. That's
>> totally acceptable. But if errors are issued, that's no longer a choice.
>>
>> In any case, if errors should be reported, we should provide an option to
>> suppress the errors.
>>
>> Thanks,
>> Jinpeng
>>
>> On Sun, May 30, 2021 at 4:59 PM Vladimir Ozerov
>> wrote:
>>
>> > Hi Jinpeng,
>> >
>> > Do you mean the whole change or the error part only?
>> >
>> > My concern is that if we change the implementation of
>> > VolcanoPlanner.isTransformationRule, then some transformation rules that
>> > are not marked as "implements TransformationRule" will be treated as
>> > implementation rules, which may lead to some other hidden negative
>> > consequences.
>> >
>> > Ease of upgrade and predictable behavior is often in conflict with each
>> > other when planning migration paths. I am not insisting on the error,
>> but
>> > personally, I am more comfortable with products that fail fast, forcing
>> me
>> > to do the right things rather as early as possible.
>> >
>> > Regards,
>> > Vladimir.
>> >
>> > [1]
>> >
>> >
>> https://github.com/apache/calcite/blob/calcite-1.26.0/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java#L96-L100
>> >
>> > вс, 30 мая 2021 г. в 10:45, Jinpeng Wu :
>> >
>> > > Hi.
>> > >
>> > > Warnings and Fixing isTransformationRule are good solutions. But I am
>> > still
>> > > concerned about reporting an error. It will force users to do a large
>> > > refactoring on existing codes before they can migrate to the new rule
>> > > driver. Any refactoring can be risky, especially for those critical
>> > > services. It leaves those systems no choice but to keep using old
>> > versions
>> > > of calcite. However, we usually can still get a good plan even without
>> > > correct rule types. I don't think it worthwhile to introduce that
>> change.
>> > >
>> > > Thanks
>> > > Jinpeng Wu
>> > >
>> > > On Sun, May 30, 2021 at 5:19 AM Vladimir Ozerov
>> > > wrote:
>> > >
>> > > > Great. Does the community have any objections to the following fix?
>> > > > 1. Add a flag to a rule call instance with the expected node type.
>> In
>> > the
>> > > > case of a mismatch, we will print a warning once per rule per JVM
>> > > instance
>> > > > to avoid too many messages. Alternatively, we may print a warning
>> per
>> > > rule
>> > > > per VolcanoPlanner, but I am concerned with too many repetitive
>> > messages
>> > > > because VolcanoPlanner is
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Hi,
I tried to apply different approaches, but eventually, I failed to achieve
my goals. It seems that the current implementation cannot handle the
required scenario, as explained below.
Consider the following tree:
LogicalAggregate1[group=[b,c]]
LogicalAggregate2[group=[a,b,c]]
LogicalInput
I want to find the plan to do these two aggregations without an exchange in
between because they may have compatible distributions. Example:
PhysicalAggregate1[group=[b,c]] // SHARDED[b,c]
PhysicalAggregate2[group=[a,b,c]] // SHARDED[b,c]
Exchange// SHARDED[b,c]
PhysicalInput // SHARDED[?]
The fundamental problem is that it is impossible to save the optimization
request and resolve traits in the "derive" phase afterward. What we need is
to send the optimization request "SHARDED by [b,c] in any order" to
PhysicalAggregate2, and use it in the derive phase so that the new
PhysicalAggregate2 is created with [b,c] or [c,b], but strictly without
[a]. Unfortunately, this doesn't work because the nodes emitted from the
pass-through do not participate in the "derive" phase.
This could be fixed with a trivial change - to allow certain nodes emitted
from the "passThrough" to participate in "derive". We can do that using a
marker interface or an extension to a PhysicalRel interface. For example:
interface PhysicalRel {
boolean enforceDerive();
}
When set to "true", the node would not be added to the pass-through cache.
This way, we may use this node as *storage* for the optimization request.
When the "derive" is called later, we know both the parent requirements and
the child traits. This would be sufficient to solve my problem. I already
tried to do this by disabling the pass-through cache completely and
confirmed that the required plan is found.
Do you have any objections to such a change?
Regards,
Vladimir.
вс, 30 мая 2021 г. в 12:54, Jinpeng Wu :
> Hi, Vladimir. I mean the error part only. I am comfortable with the other
> changes.
>
> If changing isTransformationRule could have unexpected consequences, one
> possible way is reserving current logic and only adding a newline checking
> the "implements TransformationRule''. Even though we remove the original
> logic completely, users who prefer legacy logic to avoid risks can
> overwrite the method by simply copying several lines of code. That's
> totally acceptable. But if errors are issued, that's no longer a choice.
>
> In any case, if errors should be reported, we should provide an option to
> suppress the errors.
>
> Thanks,
> Jinpeng
>
> On Sun, May 30, 2021 at 4:59 PM Vladimir Ozerov
> wrote:
>
> > Hi Jinpeng,
> >
> > Do you mean the whole change or the error part only?
> >
> > My concern is that if we change the implementation of
> > VolcanoPlanner.isTransformationRule, then some transformation rules that
> > are not marked as "implements TransformationRule" will be treated as
> > implementation rules, which may lead to some other hidden negative
> > consequences.
> >
> > Ease of upgrade and predictable behavior is often in conflict with each
> > other when planning migration paths. I am not insisting on the error, but
> > personally, I am more comfortable with products that fail fast, forcing
> me
> > to do the right things rather as early as possible.
> >
> > Regards,
> > Vladimir.
> >
> > [1]
> >
> >
> https://github.com/apache/calcite/blob/calcite-1.26.0/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java#L96-L100
> >
> > вс, 30 мая 2021 г. в 10:45, Jinpeng Wu :
> >
> > > Hi.
> > >
> > > Warnings and Fixing isTransformationRule are good solutions. But I am
> > still
> > > concerned about reporting an error. It will force users to do a large
> > > refactoring on existing codes before they can migrate to the new rule
> > > driver. Any refactoring can be risky, especially for those critical
> > > services. It leaves those systems no choice but to keep using old
> > versions
> > > of calcite. However, we usually can still get a good plan even without
> > > correct rule types. I don't think it worthwhile to introduce that
> change.
> > >
> > > Thanks
> > > Jinpeng Wu
> > >
> > > On Sun, May 30, 2021 at 5:19 AM Vladimir Ozerov
> > > wrote:
> > >
> > > > Great. Does the community have any objections to the following fix?
> > > > 1. Add a flag to a rule call instance with the expected node type. In
> > the
> > > > case of a mismatch, we will print a warning once per rule per JVM
> > > instance
> > > > to avoid too many messages. Alternatively, we may print a warning per
> > > rule
> > > > per VolcanoPlanner, but I am concerned with too many repetitive
> > messages
> > > > because VolcanoPlanner is usually instantiated per SQL query.
> > > > 2. In the next release, (1) replace the warning with an error, (2)
> > change
> > > > VolcanoPlanner.isTransformationRule as discussed above.
> > > >
> > > >
> > > >
> > > > Пт, 28 мая 2021 г. в 21:27, Haisheng Yuan :
> > > >
> > > > >
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Hi, Vladimir. I mean the error part only. I am comfortable with the other
changes.
If changing isTransformationRule could have unexpected consequences, one
possible way is reserving current logic and only adding a newline checking
the "implements TransformationRule''. Even though we remove the original
logic completely, users who prefer legacy logic to avoid risks can
overwrite the method by simply copying several lines of code. That's
totally acceptable. But if errors are issued, that's no longer a choice.
In any case, if errors should be reported, we should provide an option to
suppress the errors.
Thanks,
Jinpeng
On Sun, May 30, 2021 at 4:59 PM Vladimir Ozerov wrote:
> Hi Jinpeng,
>
> Do you mean the whole change or the error part only?
>
> My concern is that if we change the implementation of
> VolcanoPlanner.isTransformationRule, then some transformation rules that
> are not marked as "implements TransformationRule" will be treated as
> implementation rules, which may lead to some other hidden negative
> consequences.
>
> Ease of upgrade and predictable behavior is often in conflict with each
> other when planning migration paths. I am not insisting on the error, but
> personally, I am more comfortable with products that fail fast, forcing me
> to do the right things rather as early as possible.
>
> Regards,
> Vladimir.
>
> [1]
>
> https://github.com/apache/calcite/blob/calcite-1.26.0/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java#L96-L100
>
> вс, 30 мая 2021 г. в 10:45, Jinpeng Wu :
>
> > Hi.
> >
> > Warnings and Fixing isTransformationRule are good solutions. But I am
> still
> > concerned about reporting an error. It will force users to do a large
> > refactoring on existing codes before they can migrate to the new rule
> > driver. Any refactoring can be risky, especially for those critical
> > services. It leaves those systems no choice but to keep using old
> versions
> > of calcite. However, we usually can still get a good plan even without
> > correct rule types. I don't think it worthwhile to introduce that change.
> >
> > Thanks
> > Jinpeng Wu
> >
> > On Sun, May 30, 2021 at 5:19 AM Vladimir Ozerov
> > wrote:
> >
> > > Great. Does the community have any objections to the following fix?
> > > 1. Add a flag to a rule call instance with the expected node type. In
> the
> > > case of a mismatch, we will print a warning once per rule per JVM
> > instance
> > > to avoid too many messages. Alternatively, we may print a warning per
> > rule
> > > per VolcanoPlanner, but I am concerned with too many repetitive
> messages
> > > because VolcanoPlanner is usually instantiated per SQL query.
> > > 2. In the next release, (1) replace the warning with an error, (2)
> change
> > > VolcanoPlanner.isTransformationRule as discussed above.
> > >
> > >
> > >
> > > Пт, 28 мая 2021 г. в 21:27, Haisheng Yuan :
> > >
> > > > 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
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Hi Jinpeng,
Do you mean the whole change or the error part only?
My concern is that if we change the implementation of
VolcanoPlanner.isTransformationRule, then some transformation rules that
are not marked as "implements TransformationRule" will be treated as
implementation rules, which may lead to some other hidden negative
consequences.
Ease of upgrade and predictable behavior is often in conflict with each
other when planning migration paths. I am not insisting on the error, but
personally, I am more comfortable with products that fail fast, forcing me
to do the right things rather as early as possible.
Regards,
Vladimir.
[1]
https://github.com/apache/calcite/blob/calcite-1.26.0/core/src/main/java/org/apache/calcite/plan/volcano/VolcanoRuleCall.java#L96-L100
вс, 30 мая 2021 г. в 10:45, Jinpeng Wu :
> Hi.
>
> Warnings and Fixing isTransformationRule are good solutions. But I am still
> concerned about reporting an error. It will force users to do a large
> refactoring on existing codes before they can migrate to the new rule
> driver. Any refactoring can be risky, especially for those critical
> services. It leaves those systems no choice but to keep using old versions
> of calcite. However, we usually can still get a good plan even without
> correct rule types. I don't think it worthwhile to introduce that change.
>
> Thanks
> Jinpeng Wu
>
> On Sun, May 30, 2021 at 5:19 AM Vladimir Ozerov
> wrote:
>
> > Great. Does the community have any objections to the following fix?
> > 1. Add a flag to a rule call instance with the expected node type. In the
> > case of a mismatch, we will print a warning once per rule per JVM
> instance
> > to avoid too many messages. Alternatively, we may print a warning per
> rule
> > per VolcanoPlanner, but I am concerned with too many repetitive messages
> > because VolcanoPlanner is usually instantiated per SQL query.
> > 2. In the next release, (1) replace the warning with an error, (2) change
> > VolcanoPlanner.isTransformationRule as discussed above.
> >
> >
> >
> > Пт, 28 мая 2021 г. в 21:27, Haisheng Yuan :
> >
> > > 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
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Hi.
Warnings and Fixing isTransformationRule are good solutions. But I am still
concerned about reporting an error. It will force users to do a large
refactoring on existing codes before they can migrate to the new rule
driver. Any refactoring can be risky, especially for those critical
services. It leaves those systems no choice but to keep using old versions
of calcite. However, we usually can still get a good plan even without
correct rule types. I don't think it worthwhile to introduce that change.
Thanks
Jinpeng Wu
On Sun, May 30, 2021 at 5:19 AM Vladimir Ozerov wrote:
> Great. Does the community have any objections to the following fix?
> 1. Add a flag to a rule call instance with the expected node type. In the
> case of a mismatch, we will print a warning once per rule per JVM instance
> to avoid too many messages. Alternatively, we may print a warning per rule
> per VolcanoPlanner, but I am concerned with too many repetitive messages
> because VolcanoPlanner is usually instantiated per SQL query.
> 2. In the next release, (1) replace the warning with an error, (2) change
> VolcanoPlanner.isTransformationRule as discussed above.
>
>
>
> Пт, 28 мая 2021 г. в 21:27, Haisheng Yuan :
>
> > 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
Re: Top-down optimizer cannot explore the search space because physical rule is treated as transformation rule
Great. Does the community have any objections to the following fix?
1. Add a flag to a rule call instance with the expected node type. In the
case of a mismatch, we will print a warning once per rule per JVM instance
to avoid too many messages. Alternatively, we may print a warning per rule
per VolcanoPlanner, but I am concerned with too many repetitive messages
because VolcanoPlanner is usually instantiated per SQL query.
2. In the next release, (1) replace the warning with an error, (2) change
VolcanoPlanner.isTransformationRule as discussed above.
Пт, 28 мая 2021 г. в 21:27, Haisheng Yuan :
> 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
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
