Hi Stamatis,
Thanks for your comment. I think my example didn't make it clear.
When a logical operator is created, it doesn't have any physical,
propertyand it shouldn't have. When a physical operator is created,
e.g. in Enumerable convention, it only creates an intuitive traitset
with it, and requests it children the corresponding ones.
For operators such as Join, Aggregate, Window, which may deliver
multiple different traitsets, when the parent operator is created and
request its traitset, it might be good to know what are the poosible
traitset that the child operator can deliver. e.g.
SELECT DISTINCT c, b FROM
( SELECT R.c c, S.b b FROM R, S
WHERE R.a=S.a and R.b=S.b and R.c=S.c) t;
Suppose R is ordered by (c, b, a), and S is ordered by (b, c, a).
Here is the logical plan:
Aggregate
+--- InnerJoin
|--- TableScan on R
+--- TableScan on S
When we create a physical merge join for the inner join, it may just
have collation sorted on a,b,c. Then the aggreate on top of join will
request another sort on c,b, thus we miss the best plan. What we
can do is requesting all the order combinations, which is n!, like
how the Values operator does. But that is too much.
If we can provide an approach that can minimize the possiple traitset
that the child operator may deliver, we can reduce the chance of missing
good plans. For the above query, the Aggregate operator can derive
possible traitsets that its child operator join can deliver, in which case,
the possiple traitsets of join is
1. collation on (a,b,c) based on join condition,
2. collation on (c,b,a) based on left child,
3. collation on (b,c,a) based on right child
So we can request Aggregate sorted by (c,b) and Join sorted by (c,b,a).
The number of traiset requests and plan alternatives can be reduced.
The DerivedTraitSets can be used to derive the possible traitsets from
Join, and pass through Project, Filter etc...
This is just an example of non-distributed system, for distributed system,
it can save much more by considering the possible distribution delivered
by child operators.
One thing that concerns me is it highly relies on the traiset system of the
underlying physical system. Like Enumerable doesn't consider distribution,
because it is single-node system, but Hive/Flink are distributed system.
- Haisheng
------------------------------------------------------------------
发件人：Stamatis Zampetakis<zabe...@gmail.com>
日 期：2019年10月18日 14:53:41
收件人：<dev@calcite.apache.org>
主 题：Re: [DISCUSS] On-demand traitset request
Hi Haisheng,
This is an interesting topic but somehow in my mind I thought that this
mechanism is already in place.
When an operator (logical or physical) is created its traitset is
determined in bottom-up fashion using the create
static factory method present in almost all operators. In my mind this is
in some sense the applicability function
mentioned in [1].
Now during optimization we proceed in top-down manner and we request
certain traitsets from the operators.
If it happens and they contain already the requested traits nothing needs
to be done.
In your example when we are about to create the sort-merge join we can
check what traitsets are present in the inputs
and if possible request those. Can you elaborate a bit more why do we need
a new type of metadata?
Anyway if we cannot do it at the moment it makes sense to complete the
missing bits since what you are describing
was already mentioned in the original design of the Volcano optimizer [1].
"If a move to be pursued is the exploration of a normal query processing
algorithm such as merge-join, its cost is calculated by the algorithm's
cost function. The algorithm's applicability function determines the
physical properly vectors for the algorithms inputs, and their costs and
optimal plans are found by invoking FindBestPlan for the inputs. For some
binary operators, the actual physical properties of the inputs are not as
important as the consistency of physical properties among the inputs. For
example, for a sort-based implementation of intersection, i.e., an
algorithm very similar to merge-join, any sort order of the two inputs will
suffice as long as the two inputs are sorted in the same way. Similarly,
for a parallel join, any partitioning of join inputs across multiple
processing nodes is acceptable if both inputs are partitioned using
Compatible partitioning rules. For these cases, the search engine permits
the optimizer implementor to specify a number of physical property vectors
to be tried. For example, for the intersection of two inputs R and S with
attributes A, B, and C where R is sorted on (A,B,C) and S is sorted on
(B,A,C), both these sort orders can be specified by the optimizer
implementor and will be optimized by the generated optimizer, while other
possible sort orders, e.g., (C,B,A), will be ignored. " [1]
Best,
Stamatis
[1]
https://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/Papers/Volcano-graefe.pdf
On Fri, Oct 18, 2019 at 4:56 AM Haisheng Yuan <h.y...@alibaba-inc.com>
wrote:
> TL;DR
> Both top-down physical TraitSet request and bottom-up TraitSet
> derivation have their strongth and weakness, we propose
> on-demand TraitSet request to combine the above two, to reduce
> the number of plan alternatives that are genereated, especially
> in distributed system.
>
> e.g.
> select * from foo join bar on f1=b1 and f2=b2 and f3=b3;
>
> In non-distributed system, we can generate a sort merge join,
> requesting foo sorted by f1,f2,f3 and bar sorted by b1,b2,b3.
> But if foo happens to be sorted by f3,f2,f1, we may miss the
> chance of making use of the delivered ordering of foo. Because
> if we require bar to be sorted by b3,b2,b1, we don't need to
> sort on foo anymore. There are so many choices, n!, not even
> considering asc/desc and null direction. We can't request all
> the possible traitsets in top-down way, and can't derive all the
> possible traitsets in bottom-up way either.
>
> We propose on-demand traitset request by adding a new type
> of metadata DerivedTraitSets into the built-in metadata system.
>
> List<RelTraitSet> deriveTraitSets(RelNode, RelMetadataQuery)
>
> In this metadata, every operator returns several possbile traitsets
> that may be derived from this operator.
>
> Using above query as an example, the tablescan on foo should
> return traiset with collation on f3, f2, f1.
>
> In physical implementation rules, e.g. the SortMergeJoinRule,
> it gets possible traitsets from both child operators, uses the join
> keys to eliminate useless traitsets, leaves out usefull traitsets,
> and requests corresponding traitset on the other child.
>
> This relies on the feature of AbstractConverter, which is turned
> off by default, due to performance issue [1].
>
> Thoughts?
>
> [1] https://issues.apache.org/jira/browse/CALCITE-2970
>
> Haisheng
>
>
