Re: Why should invalidate all of the caches of HANDLERS when adding a new RelNode class in JaninoRelMetadataProvider.revise() method?
Hi, James. Thanks very much for your kind reply. Actually I am not worrying about the polymorphic calls. And I know that cascading simple if statements works well in some scenarios. I was just wondering whether a bunch of instance-of would be much slower than simple comparisons of integers. Let alone further optimizations that jvm could apply to simple switch-case. Well, if the performance data shows an acceptable deviation, it shall be ok. Thanks, Jinpeng On Mon, Jan 17, 2022 at 2:44 PM James Starr wrote: > Cascading if statements such as the ones generated, are generally faster > than polymorphic calls in java. Do you worry about polymorphic calls to > rel nodes? The map look up is at least a magnitudes more expensive than the > dispatch. The key generation for the map look was also a magnitude more > expensive. Even then it is near impossible to measure a difference with > large real world queries that do any meaningful optimization as long as the > metadata system is fairly efficient. Jacques implemented the dispatch with > a map, and his measurements were within a standard deviation. > > James > > On Sun, Jan 16, 2022 at 9:17 PM Jinpeng Wu wrote: > > > Hi, James. I just noticed the change. And I have a little concern about > > it. > > > > The original implementation uses a switch-case against the class id (an > > integer). So it has to regenerate the handler after a new relnode type > > arrives. It could be bad for some adhoc optimization processes. But it is > > friendly to long-live services who will achieve best performance after > > fully warmed up. > > > > The new design uses a bunch of if-else and instance-of operators. To my > > understanding, those operators are much heavier than a switch-case > against > > an integer value, especially for such hot operations of metadata query. > So > > I wonder whether it will affect the overall latencies. > > > > Thank you. > > Jinpeng Wu > > > > > > On Mon, Jan 17, 2022 at 9:42 AM guangyuan wang > > > wrote: > > > > > Thank you very much for your answer. > > > > > > James Starr 于2022年1月17日周一 09:09写道： > > > > > > > That is old code. The generated code depends on knowing all types of > > rel > > > > node, so all the code must be regenerated after discovering a new > type > > or > > > > rel node. Apache calcite main does not have this requirement. > > > > > > > > James > > > > > > > > On Sun, Jan 16, 2022 at 4:35 PM guangyuan wang < > > wangguangy...@apache.org > > > > > > > > wrote: > > > > > > > > > Yes, I can. > > > > > Here is the link: > > > > > > > > > > > > > > > > > > > > https://github.com/apache/calcite/blob/7655bd735f10de5be1eca8bb9af475b3b2ac63b6/core/src/main/java/org/apache/calcite/rel/metadata/JaninoRelMetadataProvider.java#L481 > > > > > > > > > > Jacques Nadeau 于2022年1月17日周一 03:09写道： > > > > > > > > > > > Can you please provide a url link to the line of code you are > > > referring > > > > > to > > > > > > in github? > > > > > > > > > > > > On Sat, Jan 15, 2022, 5:52 PM guangyuan wang < > > > wangguangy...@apache.org > > > > > > > > > > > wrote: > > > > > > > > > > > > > Thank you very much for your answer. > > > > > > > I'm reading source code these days, I'm a little confused about > > > the " > > > > > > > JaninoRelMetadataProvider.revise()" method. > > > > > > > So I'd like to know the reason why invalidate all of the caches > > of > > > > > > HANDLERS > > > > > > > when adding a new RelNode class to ALL_RELS. > > > > > > > > > > > > > > Jacques Nadeau 于2022年1月16日周日 02:04写道： > > > > > > > > > > > > > > > I should you produce a test case that represents the specific > > > > concern > > > > > > you > > > > > > > > have as opposed to proposing a snippet of code. I'm not sure > > what > > > > you > > > > > > > > propose is necessary. I think their is implicit expected > logic > > > > that a > > > > > > > > revise should only influence an exception outcome, not a > value > > > > > outco
Re: Why should invalidate all of the caches of HANDLERS when adding a new RelNode class in JaninoRelMetadataProvider.revise() method?
Hi, James. I just noticed the change. And I have a little concern about
it.
The original implementation uses a switch-case against the class id (an
integer). So it has to regenerate the handler after a new relnode type
arrives. It could be bad for some adhoc optimization processes. But it is
friendly to long-live services who will achieve best performance after
fully warmed up.
The new design uses a bunch of if-else and instance-of operators. To my
understanding, those operators are much heavier than a switch-case against
an integer value, especially for such hot operations of metadata query. So
I wonder whether it will affect the overall latencies.
Thank you.
Jinpeng Wu
On Mon, Jan 17, 2022 at 9:42 AM guangyuan wang
wrote:
> Thank you very much for your answer.
>
> James Starr 于2022年1月17日周一 09:09写道：
>
> > That is old code. The generated code depends on knowing all types of rel
> > node, so all the code must be regenerated after discovering a new type or
> > rel node. Apache calcite main does not have this requirement.
> >
> > James
> >
> > On Sun, Jan 16, 2022 at 4:35 PM guangyuan wang >
> > wrote:
> >
> > > Yes, I can.
> > > Here is the link:
> > >
> > >
> >
> https://github.com/apache/calcite/blob/7655bd735f10de5be1eca8bb9af475b3b2ac63b6/core/src/main/java/org/apache/calcite/rel/metadata/JaninoRelMetadataProvider.java#L481
> > >
> > > Jacques Nadeau 于2022年1月17日周一 03:09写道：
> > >
> > > > Can you please provide a url link to the line of code you are
> referring
> > > to
> > > > in github?
> > > >
> > > > On Sat, Jan 15, 2022, 5:52 PM guangyuan wang <
> wangguangy...@apache.org
> > >
> > > > wrote:
> > > >
> > > > > Thank you very much for your answer.
> > > > > I'm reading source code these days, I'm a little confused about
> the "
> > > > > JaninoRelMetadataProvider.revise()" method.
> > > > > So I'd like to know the reason why invalidate all of the caches of
> > > > HANDLERS
> > > > > when adding a new RelNode class to ALL_RELS.
> > > > >
> > > > > Jacques Nadeau 于2022年1月16日周日 02:04写道：
> > > > >
> > > > > > I should you produce a test case that represents the specific
> > concern
> > > > you
> > > > > > have as opposed to proposing a snippet of code. I'm not sure what
> > you
> > > > > > propose is necessary. I think their is implicit expected logic
> > that a
> > > > > > revise should only influence an exception outcome, not a value
> > > outcome.
> > > > > > Only value outcomes are cached so I don't see where there would
> be
> > a
> > > > > > problem.
> > > > > >
> > > > > > If you're revising value outcomes based on revise call (not just
> > > > > exception
> > > > > > outcomes), I think you're probably breaking the expected
> contract.
> > (I
> > > > say
> > > > > > think here because I don't think docs make this clear and wasn't
> > the
> > > > > person
> > > > > > that wrote the original code.)
> > > > > >
> > > > > > On Sat, Jan 15, 2022, 3:23 AM guangyuan wang <
> > > wangguangy...@apache.org
> > > > >
> > > > > > wrote:
> > > > > >
> > > > > > > Dear community
> > > > > > >
> > > > > > > Why should invalidate all of the caches of HANDLERS when
> adding a
> > > new
> > > > > > > RelNode class in JaninoRelMetadataProvider.revise() method?
> > > > > > >
> > > > > > > The Codes are below:
> > > > > > >
> > > > > > > package org.apache.calcite.rel.metadata
> > > > > > >
> > > > > > > public class JaninoRelMetadataProvider implements
> > > > RelMetadataProvider {
> > > > > > >
> > > > > > > synchronized MetadataHandler> H
> > > > > revise(
> > > > > > >
> > > > > > > Class rClass, MetadataDef def) {
> > > > > > > if (ALL_RELS.add(rClass)) {
> > > > > > > HANDLERS.invalidateAll();
> > > > > > > }
> > > > > > > //noinspection unchecked
> > > > > > > return (H) create(def);
> > > > > > > }
> > > > > > >
> > > > > > > }
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> >
>
Re: [DISCUSS] Extends RelDistribution to support more distribution types
Hi, Jing.
I'm not worrying about existing queries being affected. But I am just
providing some suggestions. If you don't handle traits derivations
correctly, your new queries may not perform as well as those old queries
using classic distribution types.
Metadata queries can not only return concrete values, but also properties.
Like what areColumnUnique does, you may just use an "skewInfo" metadata
which returns a boolean value (or together with some other information if
available).
Regards,
JInpeng Wu
On Wed, Dec 22, 2021 at 12:41 PM Jing Zhang wrote:
> Sorry for typo.
> so it would effect existed sql behavior. => it would not effect existed sql
> behavior.
>
>
> Jing Zhang 于2021年12月22日周三 12:36写道：
>
> > Hi Jinpeng,
> > Thanks for response.
> > I guess we say different solution to solve data skew, please correct me
> if
> > I am wrong.
> >
> > What you say is for cases hot keys could be known in advance and stored
> in
> > metadata. So we could query whether there is data skew and skew values
> > from RelMetadataQuery. The optimization is used in Hive.
> >
> > What I say is an alternative approach which we could not list hot keys in
> > advance. Just like the hot words of search engines, we know that this
> > phenomenon exists but there is no way to list hot words in advance.
> > To avoid data skew for normal hash distribution, we introduce a special
> > hash distribution. It would send records with the same hash key to one
> of N
> > downstream instead of the same downstream.
> >
> > I add a new distribution type, but only trigger this distribution type
> > under specified conditions, so it would effect existed sql behavior.
> > For example, user could enable this optimization by specify the hint,
> like
> > the following.
> > > select p.x, p.y, b.z, b.pt_year, b.pt_mon, b.pt_day
> > > from default_catalog.default_database.probe as p
> > > join partition_table_3 /*+ PARTITIONED_JOIN('BUCKET_NUM'= '16')*/ for
> > system_time as of p.proc_time as b
> > > on p.x=b.x and p.y=b.y
> >
> > WDYT?
> >
> > Best,
> > Jing Zhang
> >
> > Jinpeng Wu 于2021年12月22日周三 11:45写道：
> >
> >> Hi, Jing. I still don't get your point of adding new distribution
> types.
> >>
> >> I think what you need is a new metadata indicating whether there are
> >> skewed
> >> values. By looking it up through RelMetadataQuery, you may boost (or
> even
> >> make it INF) the cost of two-pass agg or shuffled join and make other
> >> implementations win.
> >>
> >> Adding new shuffle types is not as simple as it appears to be. You may
> >> need
> >> to adjust the traits passthrough and derivation logica. And compared
> with
> >> metadata query, you may need to maintain the skew values during
> operators'
> >> implementation rules, which introduces difficulties for further
> >> maintenance.
> >>
> >> Thanks
> >>
> >> On Wed, Dec 22, 2021 at 11:05 AM Jing Zhang
> wrote:
> >>
> >> > Hi Julian,
> >> > Make sense.
> >> > Then a new newAdded RelDistribution type requires a strong reason.
> >> > I have created a JIRA [1] to track this requirement.
> >> >
> >> > [1] https://issues.apache.org/jira/browse/CALCITE-4957
> >> >
> >> > Best,
> >> > Jing Zhang
> >> >
> >> > Julian Hyde 于2021年12月22日周三 08:04写道：
> >> >
> >> > > I think you should contribute a change that adds a new value to the
> >> enum.
> >> > > I know that enums are not easily extensible, but in cases like this,
> >> that
> >> > > can be a feature rather than a bug.
> >> > >
> >> > > There are not very many distribution types, and new distribution
> types
> >> > are
> >> > > rarely invented. Requiring people to contribute to the enum is a
> >> useful
> >> > > forcing function: the various groups who use Calcite are forced to
> >> > describe
> >> > > their use cases, and when people discover that they have the same
> use
> >> > > cases, we tend to get reusable code.
> >> > >
> >> > > Converting an enum to an interface makes things a lot less concrete.
> >> It
> >> > is
> >> > > more difficult to reason about a piece of code, and there are bugs
> >> > because
> >> > > you can’t review a ’switch’ expression and say ‘
Re: [DISCUSS] Extends RelDistribution to support more distribution types
Hi, Jing. I still don't get your point of adding new distribution types. I think what you need is a new metadata indicating whether there are skewed values. By looking it up through RelMetadataQuery, you may boost (or even make it INF) the cost of two-pass agg or shuffled join and make other implementations win. Adding new shuffle types is not as simple as it appears to be. You may need to adjust the traits passthrough and derivation logica. And compared with metadata query, you may need to maintain the skew values during operators' implementation rules, which introduces difficulties for further maintenance. Thanks On Wed, Dec 22, 2021 at 11:05 AM Jing Zhang wrote: > Hi Julian, > Make sense. > Then a new newAdded RelDistribution type requires a strong reason. > I have created a JIRA [1] to track this requirement. > > [1] https://issues.apache.org/jira/browse/CALCITE-4957 > > Best, > Jing Zhang > > Julian Hyde 于2021年12月22日周三 08:04写道： > > > I think you should contribute a change that adds a new value to the enum. > > I know that enums are not easily extensible, but in cases like this, that > > can be a feature rather than a bug. > > > > There are not very many distribution types, and new distribution types > are > > rarely invented. Requiring people to contribute to the enum is a useful > > forcing function: the various groups who use Calcite are forced to > describe > > their use cases, and when people discover that they have the same use > > cases, we tend to get reusable code. > > > > Converting an enum to an interface makes things a lot less concrete. It > is > > more difficult to reason about a piece of code, and there are bugs > because > > you can’t review a ’switch’ expression and say ‘yes, that covers all > cases’. > > > > Julian > > > > > On Dec 21, 2021, at 12:33 AM, Jing Zhang wrote: > > > > > > Hi community, > > > I hope to extend `RelDistribution` to support more distribution types > in > > > order to solve data skew in the normal hash distribution. > > > > > > When we use hash distribution to bring all records with the same hash > key > > > to the same place, the job performance would be poor if there exists > hot > > > keys. > > > There is a solution to solve this problem, we could send a hot key to > one > > > of serval downstream tasks, chosen at random. > > > In HashJoin, we could use random hash partition in one side, for the > > other > > > input to the join, records relating to the hot key need to be > replicated > > to > > > all downstream tasks handling that key. > > > In HashAggregate, we could split the aggregate into partial-final if > all > > > the aggregation functions support splitting. > > > The 10th chapter in the book "Designing Data Intensive Applications" > also > > > refers this solution to solve data skew. > > > > > > Anyway, we should first extend `RelDistribution` to support more > > > distribution types, for example, hash random type. > > > However, `RelDistribution.Type` is enum class which is not extensible. > > > I would not add the new types in enum `RelDistribution.Type` directly. > > > I prefer to do a refactor on `RelDistribution.Type` to make it > extensible > > > and add the new types in the subclass in the external execution engine > > (e.g > > > Flink). > > > > > > For example, there is a lookup join in Flink. is typically used to > > enrich a > > > table with data that is queried from an external system. > > > For the following query > > >> select p.x, p.y, b.z, b.pt_year, b.pt_mon, b.pt_day > > >> from default_catalog.default_database.probe as p > > >> join partition_table_3 for system_time as of p.proc_time as b > > >> on p.x=b.x and p.y=b.y > > > > > > When use normal hash distribution. > > > The logical plan is as following, > > > +- LookupJoin(joinType=[InnerJoin], lookup=[x=x, y=y], select=[x, y, > > x0, > > > y0, z, pt_year, pt_mon, pt_day]) > > > +- Exchange(distribution=[hash[x, y]]) > > > +- TableSourceScan(table=[[default_catalog, default_database, > > > probe, source: [CollectionTableSource(x, y)]]], fields=[x, y]) > > > > > > If enable data_skew solution in hint, the logical plan is as following, > > > +- LookupJoin(joinType=[InnerJoin], lookup=[x=x, y=y], select=[x, y, > > x0, > > > y0, z, pt_year, pt_mon, pt_day]) > > > +- Exchange(distribution=[hash_random(key=[x, y], bucket_num=8)]) > > > +- TableSourceScan(table=[[default_catalog, default_database, > > > probe, source: [CollectionTableSource(x, y)]]], fields=[x, y]) > > > > > > What do you think? > > > > > > [1] > > > > > > https://nightlies.apache.org/flink/flink-docs-master/docs/dev/table/sql/queries/joins/#lookup-join > > > > > > Best, > > > Jing Zhang > > > > >
[jira] [Created] (CALCITE-4920) Introduce logical space pruning to TopDownRuleDriver
Jinpeng Wu created CALCITE-4920: --- Summary: Introduce logical space pruning to TopDownRuleDriver Key: CALCITE-4920 URL: https://issues.apache.org/jira/browse/CALCITE-4920 Project: Calcite Issue Type: Improvement Reporter: Jinpeng Wu Assignee: Jinpeng Wu Last year, we submit a PR, introducing the TopDownRuleDriver. The rule driver implements the top-down search strategy as suggested by the Cascades frameworks[1] and provides a basic branch and bound pruning mechanism according to the upper bound cost and lower bound cost as suggested by the Columbia paper[2]. However, the previous version of TopDownRuleDriver can only prune implementation rules and enforcement rules, not transformation rules. The reason is major about logical properties. In the classic volcano/cascades model, logical properties, such as output row count, are properties that bind to an equivalent set and will never change during optimization. The Columbia optimizer[2] highly depends on this premise. However, calcite does not obey such rules. In calcite, logical properties of a RelSubset are likely to change during optimization. Actually, calcite is not the only optimizer engine that suffers. Orca's logical properties of an equivalent set also change. And it cannot have logical pruning, either. How does the logical properties problem prevent logical pruning? Take this plan as an example: sink <- op1 <- op2 <- scan. By applying a transformation rule, op1 <- op2 is transformed to op3 <- op4. So we get a new alternative plan, say sink <- op3 <- op4 <- scan, in which op3 is in the same equivalent set as op1. After implementations and enforcements, the sub plan (op1 <- op2 <- scan) gets fully optimized and yield a winner with cost C1. And now we are going to optimize op3. We know another plan in the same equivalent set has a cost of C1. So we can use C1 as a cost limit while optimizing op3. In the first step, we should build op3 into a physical plan, say impl-op3, and compute its self-cost as SC3. Ideally, if SC3 is already greater than C1, then we can decide that op3 will never be part of the best plan, thus the optimization of op4 can be skipped. That's the basic though of group pruning in the Columbia optimizer[2]. Here comes the problem: when we calculate the self-cost of impl-op3, we need to leverage the metadata, like row count, of impl-op3, which will in turn ask impl-op3's input to derive its own metadata. However, the equivalent set of op4 is not yet fully explored and its row count may not be the final one. So the self-cost of impl-op3 may be incorrect. If we just apply group pruning according to such cost, op4 will lost its opportunities to explore, and also the opportunities to become the best. To ensure correctness, we require that all descendants are fully explored when calculating a node's cost. That's why our first version of TopDownRuleDriver only prunes implementation rules and enforcement rules. In the passed one year, We tried some ways to solve the problem. For example, we tried to make calcite's logical properties stable, as Xiening proposed. But the proposal was rejected as the changes of metadata after transformations are natural. We also tried to identify, by categories or annotations, rules who will never change the logical properties and give up the pruning for other rules. But we still failed because it introduced too much complexity for rule designers. Those failures drive us to consider the problem from the very essence: if we cannot make SC3 stable, what about we give up the usage of SC3 and leverage other costs for pruning? Here is a simple description of the new though. After achieving C1, we eagerly build op3 and op4, without further exploration on them. Because op4's input, the scan, is fully optimized during the optimization of op1, we can compute a stable cumulative cost of impl-op4. Let's denote it as C4. And if we find that C4 is already greater than C1, then we know C4 will never be the best node and some optimization steps could be skipped (to make it simple, let impl-op4 be the only input of impl-op3): 1. The enforcement rules among impl-sink, impl-op3 and impl-op4, as well as trait pass-though. These steps are not handle properly in previous version. 2. The traits derivation of impl-op4 and impl-op3. 3. The explorations of op3, if the substitution of explorations always use op4 as input. This is the key of logical pruning. I will explain it in more details later on. Note that, the exploration of op4 is not pruned as we don't know whether op4's other alternatives would yield a lower cost. Moreover, the implementation of op3 is not skipped as it is already applied. But the implementation of other alternatives of op3 could be skipped if the exploration is pruned. The new solution is a hy
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
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 o
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 > > +-- HashDistri
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
Re: Trait propagation guidelines
Hi, Vladimir. Firstly, let me explain how the current solution handles your problems. It is true that the current solution is not perfect. But it does solve most problems. One thing to clarify is that, build rules are not necessary to build all possible candidates. The key point is that parent should raise as many requirements to inputs as possible. Your first problem is, "we do not know what the parent needs". Actually we do not need to. Considering that parent has raised all its possible requirements, we only need to provide one initial implementation. If it is not the one parent wants, sooner or later, the passThrough method gets called. And the desired implementation gets built. Maybe the initial implementation is wasty, but it is essential in the current solution. As you have discovered, all passThrough and derive calls are applied and only applied to it. It helps us to avoid duplicate passThrough requests. Your second problem, and the key problem, is "we do not know which physical children are available". If a parent really fires all possible requirements, it could be very wasty. As a workaround, we introduce a metadata called PulledUpTraits and relies on the RelMetaDataQuery to collect all possible delivered traits from descendants. However, this does not solve all problems, as it highly depends on how descendants have been built and how traits have been derived at the moment RelMetaDataQuery is called. Some opportunities could be missed. So we tend to fire all possible candidates that have different input requirements if the candidates count is acceptable, such as aggregations. And I saw your alternative solution. It is really impressive. In summary, I saw two key differences: 1. Traits "derive" and "passThrough" are applied to a logical node rather than a physical node (the initial implementation I mentioned above) 2. The "passThrough" and "derive" procedures are integrated into RelOptRule.onMatch But I still don't get it on how this solution handles the wasty problems. Taking the aggregations in previous discussion as an example, what should calculateInputTraitSet returns in PhysicalAggregateRule? Will it return ANY or dist[a]? If it returns dist[a], then the two-pass implementation should never be fired, as it already ask inputs to satisfy the dist[a] requirement. That is, calculateInputTraitSet already decides the implementation before optimizing children. It is simple to solve this problem: making calculateInputTraitSet return multiple requiredInputTraits, instead of a single one. So calculateInputTraitSet needs to collect all possible trait requirements. And then in the later part, those requirements are passed to the children's optimize procedure one by one. Now, it comes to the bottom aggregation. It already knows that a parent requires dist[a] traits. Can calculateInputTraitSet omit some requiredInputTraits now? I am afraid not. Because at this moment, calculateInputTraitSet has no idea whether dist[a,b] could be a better solution. For example, when the input table is a clustered table and the data was already clustered by [a, b]. The opportunities could be hidden deeply in descendants. So calculateInputTraitSet still needs to collect all possible trait requirements for inputs, plus the requirements from parents. Another interesting point is, can a child reject its parent's requirement? Note that children can always satisfy parents requirements: the worst case is injecting an extra exchange node. By default, a child should never reject a parent's requirement as it does not know whether this requirement would result in the best candidates ( or the only candidate ). To decide whether input can reject the requirement is complicated. One systematic solution is the group pruning mechanism. Whatever, it is not practical to decide it in an onMatch method call. Finally, if all required traits should need to pass to the children and children always satisfy that requirements, all possible candidates that have different input requirements will be created during the createPhysicalAggregates step. This is actually similar to the current solution. Remind me if I have any misunderstandings. Thanks, Jinpeng Wu On Thu, May 27, 2021 at 6:31 PM Vladimir Ozerov wrote: > Hi Jinpeng, > > Thank you, I would try this approach with aggregates. But as I mentioned in > the previous email, it is not ideal, because we may generate wasteful > alternatives. This is so because we generate the physical nodes outside of > the optimization context: (1) we do not know what the parent needs, and (2) > we do not know which physical children are available. For example, if there > is only a single Aggregate on top of the Scan, I can generate only a single > good alternative after the input is optimized instead of pessimistically > emitting both 1-phase and 2-phase aggregates. > > Speaking of imaginary alternative i
Re: Trait propagation guidelines
Hi，Vladimir. This could be a picture of how calcite optimize the two aggregates problem: step 1: Without any hints for pruning, BOTH implementation of aggregations should be built and held in memo. For the top aggregation, the one-pass implementation requests a HASH_DISTRIBUTED [a] distribution to its input and the two-pass implementation requests an "ANY" distribution to its input. When bottom aggregation gets built, it also builds two implementations. So we get 4 valids candidates: // Candidate 1. top agg is one-pass and bottom agg is one-pass PhysicalAggregate[group=[a], F2_phase2(c)] Exchange[dist[a]] PhysicalAggregate[group=[a,b], F1_phase2(c)] Exchange[dist[a,b]] ... // Candidate 2. top agg is one-pass and bottom agg is two-pass PhysicalAggregate[group=[a], F2_phase2(c)] Exchange[dist[a]] PhysicalAggregate[group=[a,b], F1_phase2(c)] Exchange[dist[a,b]] PhysicalAggregate[group=[a,b], F1_phase1(c)] ... // Candidate 3. top agg is two-pass, bottom agg is one-pass PhysicalAggregate[group=[a], F2_phase2(c)] Exchange[dist[a]] PhysicalAggregate[group=[a], F2_phase1(c)] PhysicalAggregate[group=[a,b], F1_phase2(c)] Exchange[dist[a,b]] ... // Candidate 4. top agg is two-pass, bottom agg is two-pass PhysicalAggregate[group=[a], F2_phase2(c)] Exchange[dist[a]] PhysicalAggregate[group=[a], F2_phase1(c)] PhysicalAggregate[group=[a,b], F1_phase2(c)] Exchange[dist[a,b]] PhysicalAggregate[group=[a,b], F1_phase1(c)] ... step 2: No matter which aggregation is built first. The calcite framework passes the HASH_DISTRIBUTED[a] trait requirement through bottom aggregation, both implementations. Note that a concrete physical node only needs to consider its own implementation. And we get two more valid candidates: // Candidate 5. passThrough called on candidate1 PhysicalAggregate[group=[a], F2_phase2(c)] PhysicalAggregate[group=[a,b], F1_phase2(c)] // deliver dist[a] Exchange[dist[a]] ... // Candidate 6. passThrough called on candidate2 PhysicalAggregate[group=[a], F2_phase2(c)] PhysicalAggregate[group=[a,b], F1_phase2(c)] // deliver dist[a] Exchange[dist[a]] PhysicalAggregate[group=[a,b], F1_phase1(c)] ... step 3: The cost model chooses the best candidate. Note that Candidate 5 is not always the best. For example, when it is detected, from stats or other, that data is skewed on key [a], Candidate 2 may be better. When it is detected that NDV(a, b) = 0.99 * ROWCOUNT() , Candidate 6 is preferred, as partial aggregate can reduce little data. So it is not wasty to build all those candidates. Most of the above works are done by calcite frameworks. Users only need to: 1. Fire both implementations during aggregation builds. 2. Overwrite the passThroughTraits method. Thanks, Jinpeng Wu On Thu, May 27, 2021 at 8:19 AM Haisheng Yuan wrote: > Another point I would like to mention is that it is not recommended to > override method "passThrough" and "derive" directly, override > "passThroughTraits" and "deriveTraits" instead, so that we can make sure > only the same type of physical node is created and no nested relnodes or > additional RelSets are created, unless you know you have to create > different type of nodes. For example, if the table foo has an btree index > on column a, and the parent relnode is requesting ordering on column a, > then we may consider to override "passThrough" of TableScan to return an > IndexScan instead of a TableScan. > > Regards, > Haisheng Yuan > On 2021/05/26 22:45:20, Haisheng Yuan wrote: > > Hi Vladimir, > > > > 1. You need a logical rule to split the aggregate into a local aggregate > and global aggregate, for example: > > > https://github.com/greenplum-db/gporca/blob/master/libgpopt/src/xforms/CXformSplitGbAgg.cpp > > Only implementation rules can convert a logical node to a physical node > or multiple physical nodes. > > After physical implementation, you have 2 physical alternatives: > > 1) single phase global physical aggregate, > > 2) 2 phase physical aggregate with local and global aggregate. > > It should be up to the cost to decide which one to choose. > > > > 2. Given a desired traitset from parent node, the current relnode only > needs to generate a single relnode after passing down the traitset. Given a > traitset delivered by child node, the current relnode only derive a single > relnode. Quite unlike other optimizer, in Calcite's top-down optimizer, you > don't need to worry about issuing multiple optimization requests to inputs, > which is handled by Calcite framework secretly. i.e. > > SELECT a, b, min(c) from foo group by a, b; > > In many other optimizer, we probably need ask the aggregate to issue 3 >
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Hi. In some SQL engine, the query select * from A where c1 not in ( select c1 from B where B.c2 = A.c2); is transformed to a plan like select * from A LEFT ANTI JOIN B on A.c2 = B.c2 AND (A.c1 = B.c1 OR A.c1 is null OR B.c1 is null); Here, the "LEFT ANTI JOIN" is nothing more than traditional definition. One thing seems to be a problem is that A.c1 cannot be used as a join key in the new plan. However, the problem is also there for ANTI_NOTIN, and even other NOT-IN-SUBQUERY physical implementations. Thanks, Qiupeng On Tue, Jul 21, 2020 at 5:30 AM Julian Hyde wrote: > How about making a sub-query type (in RexSubQuery), so it is gone > before we reach algebra. > > ANTI_NOTIN is a terrible name. ANTI means 'opposite' to ANTI_NOTIN is > the opposite of NOT IN?! > > On Mon, Jul 20, 2020 at 1:00 PM Haisheng Yuan wrote: > > > > Typo: > > We can just add a security guard saying that it is supported. > > Should be > > We can just add a security guard saying that it is NOT supported. > > > > On 2020/07/20 19:57:34, Haisheng Yuan wrote: > > > I am not sure I got your implication by "pollute". If you mean > changes, yes, it requires some changes in rules. Do we need to change > enumerables? Not necessary. We can just add a security guard saying that it > is supported. Not everyone requires the Enumerable operators to support > everything. More importantly, currently there is no logic or rules to > translate sub-query directly to SEMI/ANTI joins, let alone translating > directly to ANTI_NOTIN. Currently NOT IN is expanded to NOT(IN ...) before > entering RelNode land. That means we don't even have the chance to generate > the NOT IN anti join. Is that still a concern? > > > > > > Even if some day, some contributor extends Calcite's parser and > SubqueryRemovalRule to be able to transform NOT_IN subquery into NOT IN > anti join, we still have chance to disable it. Is that still a concern? > > > > > > There are many ways to play it safe. > > > > > > > Brainstorming: maybe we could consider it as a separate logical > operator > > > > (with its corresponding enumerable implementation)? > > > It doesn't sound cool. It requires much more work. You have to > duplicate all the rules, metadata handler that deal with LogicalJoin, and > for some rule that matches Join base class, you have to check it is a > LogicalJoin or the logical operator for ANTI_NOTIN. > > > > > > On 2020/07/20 08:28:42, Ruben Q L wrote: > > > > I have some concerns that this new type would "pollute" the existing > Join > > > > logic, rules and enumerable implementations. > > > > > > > > Brainstorming: maybe we could consider it as a separate logical > operator > > > > (with its corresponding enumerable implementation)? > > > > > > > > > > > > Le lun. 20 juil. 2020 à 06:08, Haisheng Yuan > a > > > > écrit : > > > > > > > > > I agree that NOT IN is toxic, and it is error-prone. > > > > > But you can't prevent people writing SQL with not in sub-queries, > would > > > > > you rather let optimizer generate inefficient plan? > > > > > > > > > > - Haisheng > > > > > > > > > > -- > > > > > 发件人：Julian Hyde > > > > > 日 期：2020年07月20日 11:56:35 > > > > > 收件人：dev@calcite.apache.org > > > > > 主 题：Re: [DISCUSS] New Join Type: ANTI_NOTIN > > > > > > > > > > Yuck! > > > > > > > > > > NOT IN is toxic. I'd rather keep it out of the algebra. > > > > > > > > > > On Sun, Jul 19, 2020 at 8:24 PM Haisheng Yuan > wrote: > > > > > > > > > > > > Hi all, > > > > > > > > > > > > Currently, JoinRelType.ANTI only represents NOT_EXISTS subquery > (thanks > > > > > to Ruben for reminding). > > > > > > For some simple boolean context NOT_IN subquery, we can't > transform it > > > > > to ANTI join. e.g.: > > > > > > > > > > > > SELECT * FROM foo WHERE a NOT IN (SELECT b FROM bar); -- bar.b is > > > > > nullable > > > > > > > > > > > > Because if there is a null value in the results of subquery, the > NOT IN > > > > > predicate will return false, the whole query returns empty. And in > Calcite, > > > > > the plan for this kind of query is inefficient. > > > > > > > > > > > > If we have ANTI_NOTIN to represent this kind of join, we can > generate > > > > > more efficient plan, as long as the query executor support it. > > > > > > > > > > > > Thoughts? > > > > > > > > > > > > Haisheng Yuan > > > > > > > > > > > > > > > > > > > > > > > > >
[jira] [Created] (CALCITE-4050) Traits Propagation for EnumerableMergeJoin Produces Incorrect Result
Jinpeng Wu created CALCITE-4050: --- Summary: Traits Propagation for EnumerableMergeJoin Produces Incorrect Result Key: CALCITE-4050 URL: https://issues.apache.org/jira/browse/CALCITE-4050 Project: Calcite Issue Type: Bug Reporter: Jinpeng Wu In EnumerableMergeJoin's deriveTraits method, it uses a Map to record mapping from left keys to right keys (the keyMap variable). However, the left keys could have duplicate entries. One example is JdbcTest.testJoinInCorrelatedSubQuery, the expected plan is EnumerableProject(deptno=[$0], name=[$1], employees=[$2], location=[$3]) EnumerableMergeJoin(condition=[AND(=($0, $5), =($0, $4))], joinType=[inner]) EnumerableSort(sort0=[$0], dir0=[ASC]) EnumerableTableScan(table=[[hr, depts]]) EnumerableSort(sort0=[$1], sort1=[$0], dir0=[ASC], dir1=[ASC]) ... where left keys are [0, 0] , and right keys are [1, 0]. Deriving right child's traits may result in incorrect output. -- This message was sent by Atlassian Jira (v8.3.4#803005)
Re: [DISCUSS] Towards Cascades Optimizer
Hi, Roman. Your suggestion is good and that's what I thought before. I even added a VolcanoPlannerFactory in my code to allow user to specify their own planner. But I also see that Julian is more of keeping one planner. This has been a long discussion. I think it can hardly goes to a consensus until a solution is considered as the best one, which is, as you mentioned, fastest, stable and backward compatible. So how about we just move forward, making our solution good enough first? One thing to clarify is that Haisheng and I are actually from the same team. It looks like we raised two different solutions, but actually they are two different components of a same planner. Haisheng is focusing more on trait propagation while I focus on pruning. Even for the conflict, we already have many discussions in private and the conclusion is that I will find another solution without AC. So Haisheng's interference is not a problem for me. As your planner is a brand new one, I think it should not be a problem for you, either. The differences between Haisheng and me lies in how we contribute those efforts to community. Haisheng is confident that he's code is fully controllable and the new feature is useful for ordinary volcano procedure. So he modified the VolcanoPlanner directly. As for my code, it is controllable now. But I am not so confident when trying something aggressive in the future. Later on, I will value Julian's advice, trying to keep one planner. I agree that modifying the VolcanoPlanner directly does not necessary to make it unstable or incompatible. It will surely slow me down when I move forward, but not impossible. Also, I don't think one planner is the only way to go. For example, if the planner has if/else blocks to check flags everywhere, it is no better than having another planner and switching between implementations by settings. Thanks, Jinpeng On Tue, May 12, 2020 at 2:16 AM Julian Hyde wrote: > If there’s a way for all of these efforts to be committed to master, > disabled by default, but such that they can be enabled by setting a flag, > then we can at least avoid merge conflicts. > > I hope that this “trunk-based development” approach is technically > feasible. If the rule and metadata APIs are essentially unchanged, and the > planner API is evolved smoothly, we should be able to do it. > > From the perspective of the project and community, this is certainly a > good problem to have. An embarrassment of riches. > > From the perspective of the developers, we should their work as painless > as possible. We, the community, also owe it them to make a timely decision > about which effort (or efforts) we wish to support long-term. > > Julian > > > > On May 11, 2020, at 7:04 AM, Roman Kondakov > wrote: > > > > Hi Jinpeng, > > > > Apache Calcite community has entered into the interesting situation: we > > have several concurrent efforts of building the new Cascades style > > optimizers. I can see at least three activities (correct me if I'm > wrong): > > > > 1. Haisheng's gradual rebuilding of VolcanoPlanner [1] > > 2. Jinpeng's new CascadesPlanner based on VolcanoPlanner [2] > > 3. My brand new CascadesPlanner [3] > > > > All these activities are independent and may interfere with each other. > > It is not good. We still don't know which approach is better and which > > optimizer will be the most efficient while keeping backward > compatibility. > > > > In my opinion we must refrain from breaking changes in the master branch > > right now because it can break other optimizers. > > > > I think we need to develop a further strategy for activities related to > > the new optimizers: > > - find out the way how we will choose the new default Cascades optimizer > > for Calcite: it should be stable, fast and backward-compatible > > optimizer. If all optimizers will prove to be stable and backward > > compatible, may be we need to choose the fastest one? > > - think about the possibility of using plug-in optimizers: it would be a > > great feature for users if they want to use their custom optimizer for > > specific tasks or research purposes. It can be configured with > > FrameworkConfig.setPlanner(new CustomPlanner()). > > > > What do you think? > > > > [1] https://github.com/apache/calcite/pull/1953 > > [2] https://github.com/apache/calcite/pull/1950 > > [3] https://github.com/apache/calcite/pull/1948 > > > > > > -- > > Kind Regards > > Roman Kondakov > > > > > > On 11.05.2020 11:12, Jinpeng Wu wrote: > >> Hi, Roman. > >> > >> Thanks to Julian's tips, I added a CoreCascadeQuidemTest to the code. It > >> runs iq files that CoreQuidemTest would run
Re: [DISCUSS] Towards Cascades Optimizer
Hi, Roman. Thanks to Julian's tips, I added a CoreCascadeQuidemTest to the code. It runs iq files that CoreQuidemTest would runs and uses CascadePlanner instead of VolcanoPlanner to generate physical plans. Currently all tests have passed. There are some plan changes but they are actually equivalent plans in different forms. I‘ve also committed those plan changes as '.cas' files. Moreover, if you would like to set -Dcalcite.cascade=true during tests, all test cases will use the new planner for planning. There would be some failures, typically because there's no common ways across all tests to tell whether a RelNode is physical or logical. When I was running the tests, I found that Haisheng's latest changes has a conflict with my PR. The new planner relies on AbstractConverter to tell whether a subset canConvert/needConvert to another subset. Haisheng's change will remove AbstractConverter and break this. Currently, I switch off top-down trait propagation in new planner to work around. I will merge these two top-down processing together later on to completely address this problem. One thing to recall is that, while I am writing a new planner, Haisheng modified the VolcanoPlanner directly and used a flag to switch on/off the new feature. I need to decide how to merge them: to keep a separated planner and invoke the new trait propagation interfaces or to modified the volcano planner directly. I am trying the first way now. But of course, if keeping one planner is preferred, I can also take the second way. Thanks, Jinpeng On Fri, May 1, 2020 at 6:40 AM Haisheng Yuan wrote: > Hi all, > > As planned in my proposal, I opened the pull request [1] for CALCITE-3896 > to achieve: > 1. Top-down trait request > 2. Bottom-up trait derivation > 3. Trait enforcement without AbstractConverter > > The feature can be turned on or off by a flag, either through property > config file or VolcanoPlanner set method. Since Calcite doesn't turn on > AbstractConverter until latest master, I just disabled AbstractConverter by > turning on top-down trait request, now all tests passed. > > In our system, 99 tpcds queries' test results show almost no plan diff, > but the number of relnodes created during optimization is reduced by 10~15% > average (even without space pruning). I believe for other systems using > VolcanoPlanner, more than 20% reduction can be expected. > > It also has top-down rule apply in mind, later can be evolved to top-down > rule apply and space pruning, e.g. integrating code from Jingpeng and > Roman's. But the interface that is exposed to user, as described in the > proposal, can remain the same. > > Haisheng > > [1] https://github.com/apache/calcite/pull/1953 > > > On 2020/04/30 18:01:26, Julian Hyde wrote: > > If your test cases are SQL scripts, it might be fairly straightforward > to port them to Quidem (.iq) files. Plenty of examples in > https://github.com/apache/calcite/tree/master/core/src/test/resources/sql > <https://github.com/apache/calcite/tree/master/core/src/test/resources/sql > >. > > > > Quidem files are basically SQL scripts. Expected output is embedded in > the script. You can run the script once, and if the output looks right, > overwrite the input file with the output. > > > > Julian > > > > > > > On Apr 30, 2020, at 3:26 AM, Jinpeng Wu wrote: > > > > > > Sure. I will add more cases to my PR. > > > > > > I did not design more cases because our own product has a test > frameworks, > > > which contains thousands of actual user queries. > > > Calcite's code base is quite different. I cannot just migrate cases to > > > calcite. So it may take some time. > > > > > > On Wed, Apr 29, 2020 at 4:27 AM Roman Kondakov > > > > wrote: > > > > > >> Hi Jinpeng, > > >> > > >> I went through your PR and it seemed very impressive to me. It is very > > >> similar to what I did, but you've reused many existing logic from the > > >> Volcano planner. We should definitely stay in sync in our > experiments. I > > >> believe the future Cascades planner will be the kind combination of > our > > >> works. > > >> > > >> Is there any way to run tests that are close to the real system query > > >> execution? May be with Enumerable convention, or, better, with > > >> convention that supports distribution trait? I just want to look > through > > >> your planner's optimization steps more thoroughly. I've found some > tests > > >> in org.apache.calcite.plan.volcano package, but they use synthetic > > >> conventions and nodes. May be I missed something. > > >> >
Re: [DISCUSS] Towards Cascades Optimizer
Sure. I will add more cases to my PR. I did not design more cases because our own product has a test frameworks, which contains thousands of actual user queries. Calcite's code base is quite different. I cannot just migrate cases to calcite. So it may take some time. On Wed, Apr 29, 2020 at 4:27 AM Roman Kondakov wrote: > Hi Jinpeng, > > I went through your PR and it seemed very impressive to me. It is very > similar to what I did, but you've reused many existing logic from the > Volcano planner. We should definitely stay in sync in our experiments. I > believe the future Cascades planner will be the kind combination of our > works. > > Is there any way to run tests that are close to the real system query > execution? May be with Enumerable convention, or, better, with > convention that supports distribution trait? I just want to look through > your planner's optimization steps more thoroughly. I've found some tests > in org.apache.calcite.plan.volcano package, but they use synthetic > conventions and nodes. May be I missed something. > > Thank you for sharing your work! > > -- > Kind Regards > Roman Kondakov > > > On 28.04.2020 15:19, Jinpeng Wu wrote: > > Hi, Roman. It's great to see your proposal. Actually my team has also > been > > working on a cascade planner based on calcite. And we already have some > > outcome as well. Maybe we can combine our works. > > > > I've pushed my code as https://github.com/apache/calcite/pull/1950 . > > > > Our works have many places in common. We both developed a new > > CascadePlanner and avoid modifying the old VolcanoPlanner directly. We > > both implemented the top-down search strategy according to the > > Columnbia optimizer > > generator > > < > https://15721.courses.cs.cmu.edu/spring2019/papers/22-optimizer1/xu-columbia-thesis1998.pdf > >。But > > we also have some differences. > > > > The first difference is that I try to reuse the existing VolcanoPlanner > as > > much as possible. My CascadePlanner inherits from the existing > > VolcanoPlanner. Except that it overwrites ruleQueue and findBestPlan > method > > to rearrange rule applies, most logic generally inherit from > > VolcanoPlanner. For example, > > - It reuses the RelSet and RelSubset class and the register method > > - Rules are fired as soon as a RelNode is registered (In the > > Columnbia optimizer generator, rules are not fired until exploring). The > > ApplyRule task controls when to invoke the onMatch method of a RuleMatch. > > This design have a benefit that we do not need to worry about missing a > > rule or firing a rule multiple times. > > - It leverages AbstractConverter to pass traits requirements down. So > > currently AC is still essential in my code. > > This makes the new planner highly compatible with the old VolcanoPlanner. > > Features like MV and Hints can apply to it directly. And I tried to > change > > VolcanoPlanner to the new CascadePlanner in tests. Most tests passed. > > Several cases did fail. I know the reason and how to fix them. But I am > > still thinking about making them as "won't fix" as the ruleset violates > > some basic principles of top-down trait requests. > > > > The second difference is that our design have the ability for space > > pruning. Currently it contains a simply LowerBoundCost metadata to > compute > > the lower bound of a RelNdoe. Because logical properties like cardinality > > of a RelSet is not stable across exploring, it is required that a group > to > > be fully explored (implementation rules and enforcement rules should > never > > modify the logical properties) before it can provide a valid lower bound > > cost. Because of that, logical search space pruning is not supported now. > > It can only pruned out implementation rules and enforcement rules. > Testing > > with cases in our own product, the new planner saves about 10% rule > > applies. I am still considering how to support logical space pruning, > > looking forwards to have more improvements. > > > > Hope my code will help. > > > > Thanks, > > Jinpeng > > > > > > On Tue, Apr 28, 2020 at 11:22 AM Xiening Dai > wrote: > > > >> For #1, aside from that we need to be able to build physical nodes based > >> on a convention. For example, if we merge two EnumerableProject, we > would > >> want to create an EnumerableProject as a result, instead of > LogicalProject. > >> The RelBuilder change I work on would help this case. > >> > >> For #2, I don’t think it’s just a bug. If the physica
Re: [DISCUSS] Towards Cascades Optimizer
>>>>>>> You don't need to change your physical rules, it will be treated > as > >>>>>> equal > >>>>>>>>> as logical rules and be applied together with the real logical > rules, > >>>>>> no > >>>>>>>>> more logical/physical rules difference. This is also how current > >>>>>>>>> VolcanoPlanner works. > >>>>>>>>> > >>>>>>>>>> I don't want you to think that I somehow resent the changes you > are > >>>>>>>>> pushing. > >>>>>>>>> Don't get me wrong. I am seriously thinking of revert these > changes, > >>>>>> since > >>>>>>>>> most people like the idea of adding new planner, why don't we > make > >>>>>> all the > >>>>>>>>> plan changes in the new planner, instead of forcing people > changing > >>>>>> test > >>>>>>>>> cases for the code changes that they might not need in > VolcanoPlanner > >>>>>>>>> during upgrade. > >>>>>>>>> > >>>>>>>>> I didn't intend to replace VolcanoPlanner, thought just change > the > >>>>>> search > >>>>>>>>> strategy and add trait derivation mechanism, because most of the > code > >>>>>> in > >>>>>>>>> VolcanoPlanner can be reused. But since many agree to add new > planner > >>>>>> and > >>>>>>>>> replace VolcanoPlanner as the final goal, I won't be against most > >>>>>> people's > >>>>>>>>> decision. > >>>>>>>>> > >>>>>>>>> Is there any recommended approach to make that happen smoothly > besides > >>>>>>>>> coding and testing work? We need to be aware that the new planner > >>>>>> might be > >>>>>>>>> co-exist with VolcanoPlanner for 5 or more years, or even never > >>>>>> replace > >>>>>>>>> VolcanoPlanner. > >>>>>>>>> > >>>>>>>>> More thoughts are welcome. > >>>>>>>>> > >>>>>>>>> Haisheng > >>>>>>>>> > >>>>>>>>> On 2020/04/21 19:56:25, Андрей Цвелодуб > >>>>>> wrote: > >>>>>>>>>> Hello Haisheng, > >>>>>>>>>> > >>>>>>>>>>> To keep backward compatibility, all the un-marked rules will be > >>>>>> treated > >>>>>>>>>> as logical rules, except rules that uses AbstractConverter as > rule > >>>>>>>>> operand, > >>>>>>>>>> these rules still need to applied top-down, or random order. > >>>>>>>>>> Obviously, from what is written here, I could guess that this > would > >>>>>>>>> require > >>>>>>>>>> me to change my physical planning rules, even if only by > >>>>>> implementing a > >>>>>>>>>> marker interface. I am not saying this is a bad thing, but this > is a > >>>>>>>>> thing > >>>>>>>>>> that should be communicated and planned ahead in case the > >>>>>> VolcanoPlanner > >>>>>>>>> is > >>>>>>>>>> modified. > >>>>>>>>>> > >>>>>>>>>>> Looks like I have to revert changes in CALCITE-2970 and > >>>>>> CALCITE-3753, > >>>>>>>>>> because they will cause another tons of plan changes. > >>>>>>>>>> I see you are still bitter due to all the discussions on this > list > >>>>>>>>> lately, > >>>>>>>>>> I'm sorry. I don't want you to think that I somehow resent the > >>>>>> changes > >>>>>>>>> you > >>>>>>>>>> are pushing, au contraire I support them and would be happy to > help > >>>>>> if I > >>>>>
Re: [DISCUSS] Towards Cascades Optimizer
Hi, Xiening. Regarding calculating the logical cost, here are some ways I though: 1. Logical rel may implement their own computeSelfCost method. Some rels can provide such information, for example the LogicalProject/LogicalFilter contains nearly the same information as their physical implementations. If we don't have enough confidence, just return zeroCost is also OK, as it only affects pruning. 2. Logical rel tells its parents what its physical input could be after implementation. Then the problem come back to calculating lower bound of a physical rel. There should always be ways. The only problem is how to find a pretty one. Regarding the risk, new planner do have different risk. It is not because new planner could stop us doing something wrong but we can decide when to use the new one. Some scenarios: 1. If modifying the VolcanoPlanner directly, the only way user could control the risk is not to upgrade calcite version until it is considered stable. You know, it is quite different from keeping calcite updated and switching to the new planner at a proper time. 2. It is very importance for SLA control. For the important business and jobs, we may keep using the old and stable planner. And use the new one only for jobs that have fault tolerance. And this helps testing new planner with actual scenarios. 3. It is helpful when upgrading online services. When the new planner happened to have some bugs, we can switch to the old planner directly without rollback the whole service. 4. With all these ways to prevent issues becoming disasters, we are not vulnerable to making mistakes. This not only enables faster iterations but also let us have enough time to resolve big bugs, like considering it in detail and applying a time-consuming refactoring for it. To work around a critical bug using tricky ways usually introduces more issues. Thanks, Jinpeng On Tue, Apr 21, 2020 at 2:04 AM Xiening Dai wrote: > Hi Jinpeng, > > Regarding this comment - I believe there are ways to calculate the logical > cost, but I think it’s not that simple as "cardinality * unit_copy_cost.”, > would you provide more details of other different ways? Just the algorithm > description or pseudo code would help us understand. Thanks. > > Regarding the approach of creating new planner, I don’t think a new > planner would lower the risk. We don’t know what we don’t know. If we > introduced an issue while modifying the planner, most likely we would do > the same with new planner class. A new planner doesn’t necessarily prevent > the issue from happening, but just delay its surfacing, which is worse IMO. > > There’s one obvious benefit with new planner is that we can provide some > sort of isolation so the change won’t cause test baseline updates, which > could be painful at times. We should see if we could use planner config to > achieve the same if we decide to just modify the current planner. > > > > On Apr 20, 2020, at 8:32 AM, Haisheng Yuan wrote: > > > > Igor, > > > > That's great. > > > > On 2020/04/20 11:17:49, Seliverstov Igor wrote: > >> Haisheng, Xiening, > >> > >> Ok, Now I see how it should work. > >> > >> Thanks for your replies. > >> > >> Regards, > >> Igor > >> > >>> 20 апр. 2020 г., в 09:56, Seliverstov Igor > написал(а): > >>> > >>> Haisheng, Xiening, > >>> > >>> Thanks for clarifying. > >>> > >>> In this proposal, we are not trying to split logical and physical > planning entirely. - actually I was in doubt about an idea of entire > splitting logical and physical phases, if you aren't going to, I have no > objections. > >>> > >>> But it returns me to my first question: how we will propagate traits > in bottom-up manner using proposed approach. (See [DISCUSS] Proposal to add > API to force rules matching specific rels for details) > >>> > >>> One of inconveniences of current VolcanoPlanner implementation is > amount of tricks that we need to get desired behaviour. It would be great > if some of issues (or all of them) were solved in the new approach. > >>> > >>> Regards, > >>> Igor > >>> > >>> пн, 20 апр. 2020 г., 7:02 Xiening Dai xndai@gmail.com>>: > >>> Hi Igor, > >>> > >>> Your comment - "because actual cost may be calculated correctly using > physical operators only. So won't be able to implement Branch and Bound > Space Pruning.“ is actually not true. In Cascade’s lower bound / upper > bound pruning algorithm, you can get cost lower bound of input RelNode > using cardinality * unit_copy_cost. The unit_copy_cost is a constant, which > stands for the minimal cost for processing a tuple from the input. So this > will be the minimal cost the input RelNode can achieve, and if this is > indeed larger than the current best cost, this input node can be pruned. > >>> > >>> In this proposal, we are not trying to split logical and physical > planning entirely. But for any given equivalent set, we would need to > finish exploration before implementation. But for the entire memo tree, > each set could be in different
