Hi colleagues,
I prepared (relatively) simple reproducer for the problem [1]. It can be
executed with three commands:
git clone https://github.com/devozerov/calcite-optimizer.git
cd calcite-optimizer
mvn clean test
Please do not pay attention to stuff located inside "org.apache.calcite"
package, as it is most likely of little interest for the given problem. I
removed a lot of unrelated stuff for the sake of simplicity, so some things
may seem strange or unnecessary.
So what is going on here?
1) We have a distributed engine that should assemble data from remote
nodes. Let's say, we have three distribution types [2]:
ANY - abstract unknown distribution, which is yet to be resolved during
physical planning. This is the default
REPLICATED - this is how the tables are organized - they are copied to all
nodes
SINGLETON - in this example, this is the distribution of a final aggregator
node which is enforced during physical planning
REPLICATED satisfies SINGLETON. SINGLETON doesn't satisfy REPLICATED.
2) There is a query "SELECT FUNC(f) FROM t", which is converted to the
following form with LOGICAL convention during logical planning:
RootLogicalRel[convention=LOGICAL, distribution=ANY]
-> ProjectLogicalRel[convention=LOGICAL, distribution=ANY]
-> MapScanLogicalRel[convention=LOGICAL, distribution=ANY]
3) Then, during physical planning we need to resolve and propagate
distributions, and enforce [convention=PHYSICAL, distribution=SINGLETON],
possibly injecting exchange operators in between. In this specific case, no
exchanges are needed, because scans are always REPLICATED, projection
inherits scan distribution, and for the root node is ok to use REPLICATED
input instead of SINGLETON, since the first one satisfies the latter. The
expected physical tree is:
RootPhysicalRel[convention=PHYSICAL, distribution=SINGLETON]
-> ProjectPhysicalRel[convention=PHYSICAL, distribution=REPLICATED]
-> MapScanPhysicalRel[convention=PHYSICAL, distribution=REPLICATED]
4) There are three physical rules for each operator, which are organized as
follows:
4.1) RootPhysicalRule [4] - converts RootLogicalRel node, enforcing
SINGLETON distribution on its input. As a result, an appropriate exchange
is injected later from DistributionTraitDef [3]. As I said, in this
specific query exchange is not needed
4.2) MapScanPhysicalRule [5] - converts MapScanLogicalRel. At this point,
we resolve input distribution.
4.3) ProjectPhysicalRule [6] - transforms logical project to physical
project *ONLY* if there is an underlying physical input with REPLICATED or
SINGLETON distribution.
5) Original case fails because the rules are executed as follows:
5.1) RootPhysicalRule - do transform
5.2) ProjectPhysicalRule - do nothing at this point
5.3) MapScanPhysicalRule - do transform
I would like ProjectPhysicalRule to be re-fired again, but this doesn't
happen.
There are two workarounds for this, and both concern me.
*Workaround 1*: set "canConvertConvention" to "true". In this case, rules
are executed in the way I would expect. But I observe too many rule
invocations and unnecessary trait conversions because enabling this flag
leads to matching every rel in a set with every other. For example, Volcano
tries to convert SINGLETON -> REPLICATED, while it is never actually needed
by my engine. And this is how rules are executed:
1) RootPhysicalRule - expected
2) RootPhysicalRule - fired again, because I created a converted node on
the previous step
3) ProjectPhysicalRule - expected
4) ProjectPhysicalRule - fired again for the same reason as p.2
5) MapScanPhysicalRule - expected
6) ProjectPhysicalRule - parent rule is called as I would expect - this is
where the missing physical project appear
7) RootPhysicalRule - called because its child was transformed
+ ExpandConversionRule is called multiple times, and sometimes it creates
nodes, which are otherwise completely unnecessary. Such as the
aforementioned SINGLETON -> REPLICATED conversion.
So in the end, it works as I would expect even for much more complex plans.
But produces a litter which I cannot control
Resulting plan:
RootPhysicalRel.PHYSICAL.SINGLETON.[](input=ProjectPhysicalRel#91)
ProjectPhysicalRel.PHYSICAL.REPLICATED.[](input=MapScanPhysicalRel#81,
...))
MapScanPhysicalRel.PHYSICAL.REPLICATED.[](table=[t],projects=[0])
*Workaround 2*: add exchanges for ANY distribution and produce
transformation with ANY distribution in the project rule. This is what
Drill does. But it also produces a litter. This time these are unnecessary
exchanges; we pessimistically create them when input is ANY, and if it
eventually resolved to any compatible distribution, the exchange stays
there. As far as I understand, Drill's ExcessiveExchangeIdentifier removes
that stuff after planning separately.
Resulting plan:
RootPhysicalRel.PHYSICAL.SINGLETON.[](input=UnicastExchangePhysicalRel#30)
UnicastExchangePhysicalRel.PHYSICAL.SINGLETON.[](input=ProjectPhysicalRel#29,hashFields=[0])
// Not needed!
ProjectPhysicalRel.PHYSICAL.ANY.[](input=MapScanPhysicalRel#25,...))
MapScanPhysicalRel.PHYSICAL.REPLICATED.[](table=[t],projects=[0])
So as you can see, it is possible to force Calcite to do what I need in
this specific case - to re-execute the rules of parent nodes after the
child has changed. But this workarounds creates some unnecessary
intermediate nodes. With complex queries, this may increase planning time
significantly.
My main question is - what key part of converters logic or Calcite
framework I am missing? Why I cannot force the Calcite to call parent rules
out of the box, but converters seem to do that at the cost of additional
litter?
Thank you very much in advance.
Vladimir.
[1]
https://github.com/devozerov/calcite-optimizer/blob/master/src/test/java/devozerov/OptimizerTest.java
[2]
https://github.com/devozerov/calcite-optimizer/blob/master/src/main/java/devozerov/distribution/DistributionTrait.java
[3]
https://github.com/devozerov/calcite-optimizer/blob/master/src/main/java/devozerov/distribution/DistributionTraitDef.java
[4]
https://github.com/devozerov/calcite-optimizer/blob/master/src/main/java/devozerov/physical/RootPhysicalRule.java
[5]
https://github.com/devozerov/calcite-optimizer/blob/master/src/main/java/devozerov/physical/MapScanPhysicalRule.java
[6]
https://github.com/devozerov/calcite-optimizer/blob/master/src/main/java/devozerov/physical/ProjectPhysicalRule.java
[7]
https://github.com/devozerov/calcite-optimizer/blob/master/src/main/java/devozerov/HazelcastConventions.java#L38
вт, 29 окт. 2019 г. в 11:26, Vladimir Ozerov <ppoze...@gmail.com>:
> Hi everybody,
>
> First of all, thank you for answers and suggestions. Let me address them
> briefly:
> 1) I use two conventions at the moment, LOGICAL and PHYSICAL. I agree with
> you that this might be overkill, and there is a chance that in the final
> solution we may end up with only one. But meanwhile having this separation
> seems handy, because on the first stage I enforce the optimizer to
> propagate NONE -> LOGICAL conversions. Then I have a clean logical tree
> *before* any physical distribution stuff is involved, which I can use for
> internal post-processing before going logical. I would propose to keep it
> out of scope at the moment. Let's just consider that the goal is to convert
> from one convention to another.
> 2) Operands with "any" matchers are already used
> 3) The reason why I would like to avoid the "Project" rule fire on the
> first run, is that it doesn't enforce any distribution on its child
> ("Scan"). Instead, it needs to derive the distribution from the scan.
>
> To make the problem more clear, let me prepare a simple reproducer for the
> issue.
>
> Regards,
> Vladimir.
>
> вт, 29 окт. 2019 г. в 10:01, Seliverstov Igor <gvvinbl...@gmail.com>:
>
>> Vladimir,
>>
>> I guess Project rule doesn't have a child matcher. Put into it child "any"
>> match rule and it will apply on each child node transformation.
>>
>> Regards,
>> Igor
>>
>>
>> вт, 29 окт. 2019 г., 7:07 Danny Chan <yuzhao....@gmail.com>:
>>
>> > Vladimir, all you need to do is to change the convention of the root
>> node,
>> > the volcano would propagate the convention to all its input nodes when
>> > registering them to the planner. You can take this code [1] for
>> reference :)
>> >
>> > [1]
>> >
>> https://github.com/apache/calcite/blob/1ef2821695ca6e10fbad7b8efe7246c4a20143af/core/src/main/java/org/apache/calcite/tools/Programs.java#L324
>> >
>> > Best,
>> > Danny Chan
>> > 在 2019年10月29日 +0800 AM5:24，dev@calcite.apache.org，写道：
>> > >
>> > > n of the scan.
>> >
>>
>
