You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@calcite.apache.org by "Christian Beikov (JIRA)" <ji...@apache.org> on 2017/08/29 10:08:00 UTC
[jira] [Comment Edited] (CALCITE-1965) Support outer joins for
materialized views
[ https://issues.apache.org/jira/browse/CALCITE-1965?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16145024#comment-16145024 ]
Christian Beikov edited comment on CALCITE-1965 at 8/29/17 10:07 AM:
---------------------------------------------------------------------
In order to support right joins I'd need this normalization step with an addition that right joins are rewritten to left joins. I guess the check of the structure can be easily done during OEQ determination.
I haven't thought about full outer joins, derived tables/subqueries or union rewrites yet, but I tried to come up with some examples for left and right outer joins.
Essentially OEQ must be an ordered set of ordered sets. The ordering is given by doing a depth-first search in the join tree, collecting the predicates of joins when going upwards. You will understand what I mean when you see examples.
During matching, we would do a prefix match of the query's OEQ against the view's OEQ. Since left joins are row preserving, a view can join more than a query and still being applicable. The matching would work like this:
1. Assert that the query's EQ contains all of the view's EQ and let qEQ1 = qEQ - vEQ
2. Try to find a suffix match for qOEQ in vOEQ and assert qEQ1 contains the prefix pOEQ. let vOEQ1 = vOEQ - pOEQ
3. Check that qOEQ is contained in the right order in vOEQ1
I think this should handle the equivalences for joins.
As for your examples, this approach wouldn't match:
{noformat}
View1: select a.id, b.id, c.id from a left join b on a.a = b.a left join c on b.a = c.c;
EQ={} OEQ={a.a, b.a, c.c}
Query1: select a.id, b.id, c.id from a left join c on a.a = c.c left join b on a.a = b.a;
EQ={} OEQ={a.a, c.c, b.a}
=> doesn't match order
View2: select a.id, b.id, c.id from a left join b on a.a = b.a right join c on b.a = c.c;
View2': select a.id, b.id, c.id from c left join (a left join b on a.a = b.a) on c.c = b.a;
EQ={} OEQ={a.a, b.a, c.c}
Query2: select a.id, b.id, c.id from a right join c on a.a = c.c left join b on a.a = b.a;
Query2': select a.id, b.id, c.id from c left join a on c.c = a.a left join b on a.a = b.a;
EQ={} OEQ={c.c, a.a, b.a}
=> doesn't match order
{noformat}
The examples I did so far were to illustrate how mixing left and right joins plays out
*View 1*
{noformat}
select *
from a
left join b on a.a = b.a
left join c on b.b = c.b
ljoin(a.a = b.a)
/ \
table(a) ljoin(b.b = c.b)
/ \
table(b) table(c)
EQ={}
OEQ={a.a, b.a}{b.b, c.b}
{noformat}
_Query 1.1_
{noformat}
select *
from a
join b on a.a = b.a
left join c on b.b = c.b
ijoin(a.a = b.a)
/ \
table(a) ljoin(b.b = c.b)
/ \
table(b) table(c)
EQ={a.a, b.a}
OEQ={b.b, c.b}
=> since the query's EQ {a.a, b.a} matched as prefix in the view's OEQ, we need a is not null predicate
select *
from v1
where b.a is not null
{noformat}
_Query 1.2_
{noformat}
select *
from a
join b on a.a = b.a
join c on b.b = c.b
ijoin(a.a = b.a)
/ \
table(a) ijoin(b.b = c.b)
/ \
table(b) table(c)
EQ={a.a, b.a}{b.b, c.b}
OEQ={}
=> query's EQ matched as prefix in the view's OEQ
select *
from v1
where b.a is not null and c.b is not null
{noformat}
_Query 1.3_
{noformat}
select *
from a
join b on a.a = b.a
ijoin(a.a = b.a)
/ \
table(a) table(b)
EQ={a.a, b.a}
OEQ={}
=> query's EQ matched as prefix in the view's OEQ => pOEQ = vEQ
=> query's OEQ trivially also matches the view's OEQ - pOEQ
select *
from v1
where b.a is not null
{noformat}
_Query 1.4_
{noformat}
select *
from a
join d on a.a = d.a
join b on a.a = b.a
left join c on b.b = c.b
ijoin(a.a = b.a)
/ \
ijoin(a.a = d.a) ljoin(b.b = c.b)
/ \ / \
table(a) table(d) table(b) table(c)
EQ={a.a, b.a, d.a}
OEQ={b.b, c.b}
=> since the query's EQ {a.a, b.a} matched as prefix in the view's OEQ, we need a is not null predicate
=> we also need a compensation join since d.a didn't match
select *
from v1
join d on a.a = d.a
where b.a is not null
{noformat}
*View 2*
{noformat}
select *
from a
left join b on a.a = b.a
right join c on b.b = c.b
=> needs join order rewriting
parenthesis are just to clarify precedence
select *
from c
left join (
a left join b on a.a = b.a
) on b.b = c.b
ljoin(c.b = b.b)
/ \
table(c) ljoin(a.a = b.a)
/ \
table(a) table(b)
EQ={}
OEQ={c.b, b.b}{a.a, b.a}
=> since join order changed, the sets changed order too, just like elements
=> the first element is always the left join source
{noformat}
_Query 2.1_
{noformat}
select *
from c
left join b on c.b = b.b
left join a on b.a = a.a
ljoin(c.b = b.b)
/ \
table(c) ljoin(b.a = a.a)
/ \
table(b) table(a)
EQ={}
OEQ={c.b, b.b}{b.a, a.a}
=> no rewrite since the order of the OEQ is different i.e. {a.a, b.a}!={b.a, a.a}
{noformat}
_Query 2.2_
{noformat}
select *
from c
left join b on c.b = b.b
ljoin(c.b = b.b)
/ \
table(c) table(b)
EQ={}
OEQ={c.b, b.b}
=> rewrite since qOEQ is a prefix of vOEQ
select *
from v2
{noformat}
*View 3*
{noformat}
select *
from a
left join b on a.a = b.a
right join c on b.b = c.b
left join d on c.c = d.c
=> needs join order rewriting
parenthesis are just to clarify precedence
select *
from c
left join (
a left join b on a.a = b.a
) on b.b = c.b
left join d on c.c = d.c
ljoin(c.c = d.c)
/ \
ljoin(c.b = b.b) table(d)
/ \
table(c) ljoin(a.a = b.a)
/ \
table(a) table(b)
EQ={}
OEQ={c.b, b.b}{a.a, b.a}{c.c, d.c}
{noformat}
*View 4*
{noformat}
select *
from a
left join b on a.a = b.a
right join c on b.b = c.b
left join d on c.c = d.c
right join e on d.d = e.d
=> needs join order rewriting
parenthesis are just to clarify precedence
select *
from e
left join(
c left join (
a left join b on a.a = b.a
) on b.b = c.b
left join d on c.c = d.c
) on d.d = e.d
ljoin(e.d = d.d)
/ \
table(e) ljoin(c.c = d.c)
/ \
ljoin(c.b = b.b) table(d)
/ \
table(c) ljoin(a.a = b.a)
/ \
table(a) table(b)
EQ={}
OEQ={e.d, d.d}{c.b, b.b}{a.a, b.a}{c.c, d.c}
{noformat}
was (Author: christian.beikov):
In order to support right joins I'd need this normalization step with an addition that right joins are rewritten to left joins. I guess the check of the structure can be easily done during OEQ determination.
I haven't thought about full outer joins, derived tables/subqueries or union rewrites yet, but I tried to come up with some examples for left and right outer joins.
Essentially OEQ must be an ordered set of ordered sets. The ordering is given by doing a depth-first search in the join tree, collecting the predicates of joins when going upwards. You will understand what I mean when you see examples.
During matching, we would do a prefix match of the query's OEQ against the view's OEQ. Since left joins are row preserving, a view can join more than a query and still being applicable. The matching would work like this:
1. Assert that the query's EQ contains all of the view's EQ and let qEQ1 = qEQ - vEQ
2. Try to find a suffix match for qOEQ in vOEQ and assert qEQ1 contains the prefix pOEQ. let vOEQ1 = vOEQ - pOEQ
3. Check that qOEQ is contained in the right order in vOEQ1
I think this should handle the equivalences for joins.
As for your examples, this approach wouldn't match:
{noformat}
View1: select a.id, b.id, c.id from a left join b on a.a = b.a left join c on b.a = c.c;
EQ={} OEQ={a.a, b.a, c.c}
Query1: select a.id, b.id, c.id from a left join c on a.a = c.c left join b on a.a = b.a;
EQ={} OEQ={a.a, c.c, b.a}
=> doesn't match order
View2: select a.id, b.id, c.id from a left join b on a.a = b.a right join c on b.a = c.c;
View2': select a.id, b.id, c.id from c left join (a left join b on a.a = b.a) on c.c = b.a;
EQ={} OEQ={a.a, b.a, c.c}
Query2: select a.id, b.id, c.id from a right join c on a.a = c.c left join b on a.a = b.a;
Query2': select a.id, b.id, c.id from c left join a on c.c = a.a left join b on a.a = b.a;
EQ={} OEQ={c.c, a.a, b.a}
=> doesn't match order
{noformat}
The examples I did so far were to illustrate how mixing left and right joins plays out
*View 1*
{noformat}
select *
from a
left join b on a.a = b.a
left join c on b.b = c.b
ljoin(a.a = b.a)
/ \
table(a) ljoin(b.b = c.b)
/ \
table(b) table(c)
EQ={}
OEQ={a.a, b.a}{b.b, c.b}
{noformat}
_Query 1.1_
{noformat}
select *
from a
join b on a.a = b.a
left join c on b.b = c.b
ijoin(a.a = b.a)
/ \
table(a) ljoin(b.b = c.b)
/ \
table(b) table(c)
EQ={a.a, b.a}
OEQ={b.b, c.b}
=> since the query's EQ {a.a, b.a} matched as prefix in the view's OEQ, we need a is not null predicate
select *
from v1
where b.a is not null
{noformat}
_Query 1.2_
{noformat}
select *
from a
join b on a.a = b.a
join c on b.b = c.b
ijoin(a.a = b.a)
/ \
table(a) ijoin(b.b = c.b)
/ \
table(b) table(c)
EQ={a.a, b.a}{b.b, c.b}
OEQ={}
=> query's EQ matched as prefix in the view's OEQ
select *
from v1
where b.a is not null and c.b is not null
{noformat}
_Query 1.3_
{noformat}
select *
from a
join b on a.a = b.a
ijoin(a.a = b.a)
/ \
table(a) table(b)
EQ={a.a, b.a}
OEQ={}
=> query's EQ matched as prefix in the view's OEQ => pOEQ = vEQ
=> query's OEQ trivially also matches the view's OEQ - pOEQ
select *
from v1
where b.a is not null
{noformat}
*View 2*
{noformat}
select *
from a
left join b on a.a = b.a
right join c on b.b = c.b
=> needs join order rewriting
parenthesis are just to clarify precedence
select *
from c
left join (
a left join b on a.a = b.a
) on b.b = c.b
ljoin(c.b = b.b)
/ \
table(c) ljoin(a.a = b.a)
/ \
table(a) table(b)
EQ={}
OEQ={c.b, b.b}{a.a, b.a}
=> since join order changed, the sets changed order too, just like elements
=> the first element is always the left join source
{noformat}
_Query 2.1_
{noformat}
select *
from c
left join b on c.b = b.b
left join a on b.a = a.a
ljoin(c.b = b.b)
/ \
table(c) ljoin(b.a = a.a)
/ \
table(b) table(a)
EQ={}
OEQ={c.b, b.b}{b.a, a.a}
=> no rewrite since the order of the OEQ is different i.e. {a.a, b.a}!={b.a, a.a}
{noformat}
_Query 2.2_
{noformat}
select *
from c
left join b on c.b = b.b
ljoin(c.b = b.b)
/ \
table(c) table(b)
EQ={}
OEQ={c.b, b.b}
=> rewrite since qOEQ is a prefix of vOEQ
select *
from v2
{noformat}
*View 3*
{noformat}
select *
from a
left join b on a.a = b.a
right join c on b.b = c.b
left join d on c.c = d.c
=> needs join order rewriting
parenthesis are just to clarify precedence
select *
from c
left join (
a left join b on a.a = b.a
) on b.b = c.b
left join d on c.c = d.c
ljoin(c.c = d.c)
/ \
ljoin(c.b = b.b) table(d)
/ \
table(c) ljoin(a.a = b.a)
/ \
table(a) table(b)
EQ={}
OEQ={c.b, b.b}{a.a, b.a}{c.c, d.c}
{noformat}
*View 4*
{noformat}
select *
from a
left join b on a.a = b.a
right join c on b.b = c.b
left join d on c.c = d.c
right join e on d.d = e.d
=> needs join order rewriting
parenthesis are just to clarify precedence
select *
from e
left join(
c left join (
a left join b on a.a = b.a
) on b.b = c.b
left join d on c.c = d.c
) on d.d = e.d
ljoin(e.d = d.d)
/ \
table(e) ljoin(c.c = d.c)
/ \
ljoin(c.b = b.b) table(d)
/ \
table(c) ljoin(a.a = b.a)
/ \
table(a) table(b)
EQ={}
OEQ={e.d, d.d}{c.b, b.b}{a.a, b.a}{c.c, d.c}
{noformat}
> Support outer joins for materialized views
> ------------------------------------------
>
> Key: CALCITE-1965
> URL: https://issues.apache.org/jira/browse/CALCITE-1965
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Reporter: Christian Beikov
> Assignee: Julian Hyde
>
> Currently, only inner joins are supported for materialized view substitutions. The support for outer joins involves creating new pulled up predicates in case of outer joins that represent semantics of the join. For a join predicate like "a.id = b.id" the inner join just pulls up that predicate. When having a left join like e.g. {{select * from a left join b on a.id = b.id}}, the actual pulled up predicate would be {{OR(=(a.id, b.id),ISNULL(b.id))}}. For a right join it would be {{OR(=(a.id, b.id),ISNULL(a.id))}} and for a full outer join it would be {{OR(=(a.id, b.id),ISNULL(a.id),ISNULL(b.id))}}
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)