You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@calcite.apache.org by Haisheng Yuan <hy...@apache.org> on 2020/07/20 03:23:47 UTC
[DISCUSS] New Join Type: ANTI_NOTIN
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
Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Julian Hyde <jh...@gmail.com>.
Here’s the logical plan:
Project(a.*)
Filter(condition: “notIn IS TRUE")
GeneralizedSemiJoin(condition=‘left.a=right.b’, computes={notIn: “!= ALL”})
Scan(foo)
Scan(bar)
The “notIn” column is a 3-valued boolean column computed for each record from the left input.
GeneralizedSemiJoin would be able to compute columns such as “!= ALL”, “!= ANY”, “< ALL”, etc. Each returns TRUE/FALSE/UNKOWN.
There may be multiple such columns.
A physical implementation would be able to apply filters, e.g. "notIn IS TRUE OR notIn IS UNKNOWN”. And therefore potentially return fewer rows, or convert itself to an ordinary inner semi-join.
> On Jul 24, 2020, at 10:05 PM, Haisheng Yuan <hy...@apache.org> wrote:
>
> I am not sure I get your idea.
> What will the logical plan and physical plan look like for the following query?
> SELECT * FROM foo WHERE a NOT IN (SELECT b FROM bar); -- bar.b is nullable
>
>
> On 2020/07/23 01:35:44, Julian Hyde <jh...@gmail.com> wrote:
>> How about a semi-join algorithm that adds column that hold the nature of the match? This algorithm can be used to evaluate 3-valued IN and 3-valued NOT IN queries.
>>
>> Generalizing further, it could compute any “ANY (predicate)” or “ALL (predicate)” condition as a column with values TRUE/FALSE/UNKNOWN. For instance “empno NOT IN …” is equivalent to “ALL(empno <> …)”.
>>
>> Here is an example.
>>
>> Emp table:
>>
>> empno deptno mgr
>> ===== ====== ====
>> 100 10 NULL
>> 101 10 100
>> 102 20 101
>> 103 30 100
>> 104 30 103
>> 105 40 NULL
>>
>>
>> The semi-join algorithm calculates the following intermediate result SJ:
>>
>> empno deptno mgrs match anyNulls allNulls
>> ===== ====== =========== ===== ======== ========
>> 100 10 [NULL, 100] TRUE TRUE FALSE
>> 101 10 [NULL, 100] FALSE TRUE FALSE
>> 102 20 [101] FALSE FALSE FALSE
>> 103 30 [100, 103] TRUE FALSE FALSE
>> 104 30 [100, 103] FALSE FALSE TRUE
>> 105 40 [NULL] FALSE TRUE TRUE
>>
>> So it can answer the following query:
>>
>> SELECT empno,
>> deptno,
>> empno IN (SELECT mgr FROM Emp
>> WHERE deptno = e.deptno) AS “in",
>> empno NOT IN (SELECT mgr FROM Emp
>> WHERE deptno = e.deptno) AS “notIn"
>> FROM Emp AS e;
>>
>> empno deptno in notIn
>> ===== ====== ======= =====
>> 100 10 TRUE FALSE
>> 101 10 FALSE UNKNOWN
>> 102 20 FALSE TRUE
>> 103 30 TRUE FALSE
>> 104 40 FALSE FALSE
>> 105 50 UNKNOWN UNKNOWN
>>
>> by mapping it to the output of the semi-join algorithm:
>>
>> SELECT empno, deptno,
>> case when allNulls then unknown else match end AS “in”,
>> case when anyNulls then unknown else not match end AS “notIn”
>> FROM SJ
>>
>>
>>
>>
>>
>>
>>
>>
>>> On Jul 22, 2020, at 8:57 AM, Vladimir Sitnikov <si...@gmail.com> wrote:
>>>
>>> Julian> Vladimir said he *expected* Oracle would implement (3-valued) NOT
>>> IN efficiently. (Back in the day, when I was at Oracle, they certainly did
>>> not.) Does anyone have any evidence that they do?
>>>
>>> Well, Oracle has "null aware" joins since Oracle 11g which is more than 10
>>> years old.
>>> I have not tested the actual performance of the `null-aware join`, however,
>>> it would be extremely surprising, if `null-aware join` was less efficient
>>> than "manually crafted aggregate + join + join + whatever".
>>>
>>> That is why I think it is important to be able to generate regular "not in"
>>> plans.
>>>
>>> Vladimir
>>
>>
Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Stamatis Zampetakis <za...@gmail.com>.
Actually this is a very interesting topic not only for the particular case
of NOT IN subqueries demonstrated at the beginning of this thread but for
other kinds of subqueries as well.
If I understood well the initial proposal of Haisheng is to introduce
another special kind of join at the logical level (algebra) specific to one
kind of NOT IN subqueries.
Then this would be a 1-1 translation to a physical join operator capable of
handling joins in the presence of nulls such as the null-aware joins
advocated by Oracle [1].
Undeniably there are performance benefits of using this kind of null aware
algorithms as it is also shown in the experiments of the respective paper
[1].
Other databases such as SQL server choose to model this case as regular
ANTI JOIN by adding disjunction predicates. This representation looks nice
at the logical level
but without further transformation this can only be evaluated by a nested
loop join algorithm (NLJ) so it is not that great.
Nevertheless databases with special null-aware joins could transform this
disjunctive anti-join to a physical operator that is more efficient that a
NLJ.
Postgres has also been considering NOT IN optimizations for some time now
[3] but I am not sure if it is implemented at the moment.
Another approach worth mentioning is the one implemented in HyPer [4]. The
authors introduce special join operators (namely marked join) for NOT IN,
EXISTS and other kinds of subquery clauses
at the logical (algebra) level that are later mapped to regular or
null-aware anti joins. The fact that I like in these non-standard join
operators is that they can transform complex subquery constructs to
re-orderable joins.
To sum up I agree (as everybody else I guess) that we need a join
abstraction for NOT IN and other subquery constructs in our logical
algebra.
Which one is better from those mentioned before I am not sure but I have to
say that I like the genericity in the approach from HyPer.
(For Calcite, this most likely means a new RelNode as Ruben suggested).
On the physical side things are easier since everybody has some ideas on
how the algorithm should work.
Julian gave an example and also more details can be found in the papers
mentioned previously and the web.
At the moment we should focus on the logical side of things and decide
which representation we would like to adopt.
Best,
Stamatis
[1] Enhanced Subquery optimizations in Oracle (
http://www.vldb.org/pvldb/vol2/vldb09-423.pdf)
[2] https://sqlchitchat.com/sqldev/tsql/semi-joins-in-sql-server/
[3]
https://www.postgresql.org/message-id/flat/CAKJS1f82pqjqe3WT9_xREmXyG20aOkHc-XqkKZG_yMA7JVJ3Tw@mail.gmail.com
[4] The complete story of joins (in HyPer)
https://pdfs.semanticscholar.org/ff3b/b9c6f3c71e6c10f12e45f600af72c2cd57eb.pdf
On Sat, Jul 25, 2020 at 8:05 AM Haisheng Yuan <hy...@apache.org> wrote:
> I am not sure I get your idea.
> What will the logical plan and physical plan look like for the following
> query?
> SELECT * FROM foo WHERE a NOT IN (SELECT b FROM bar); -- bar.b is nullable
>
>
> On 2020/07/23 01:35:44, Julian Hyde <jh...@gmail.com> wrote:
> > How about a semi-join algorithm that adds column that hold the nature of
> the match? This algorithm can be used to evaluate 3-valued IN and 3-valued
> NOT IN queries.
> >
> > Generalizing further, it could compute any “ANY (predicate)” or “ALL
> (predicate)” condition as a column with values TRUE/FALSE/UNKNOWN. For
> instance “empno NOT IN …” is equivalent to “ALL(empno <> …)”.
> >
> > Here is an example.
> >
> > Emp table:
> >
> > empno deptno mgr
> > ===== ====== ====
> > 100 10 NULL
> > 101 10 100
> > 102 20 101
> > 103 30 100
> > 104 30 103
> > 105 40 NULL
> >
> >
> > The semi-join algorithm calculates the following intermediate result SJ:
> >
> > empno deptno mgrs match anyNulls allNulls
> > ===== ====== =========== ===== ======== ========
> > 100 10 [NULL, 100] TRUE TRUE FALSE
> > 101 10 [NULL, 100] FALSE TRUE FALSE
> > 102 20 [101] FALSE FALSE FALSE
> > 103 30 [100, 103] TRUE FALSE FALSE
> > 104 30 [100, 103] FALSE FALSE TRUE
> > 105 40 [NULL] FALSE TRUE TRUE
> >
> > So it can answer the following query:
> >
> > SELECT empno,
> > deptno,
> > empno IN (SELECT mgr FROM Emp
> > WHERE deptno = e.deptno) AS “in",
> > empno NOT IN (SELECT mgr FROM Emp
> > WHERE deptno = e.deptno) AS “notIn"
> > FROM Emp AS e;
> >
> > empno deptno in notIn
> > ===== ====== ======= =====
> > 100 10 TRUE FALSE
> > 101 10 FALSE UNKNOWN
> > 102 20 FALSE TRUE
> > 103 30 TRUE FALSE
> > 104 40 FALSE FALSE
> > 105 50 UNKNOWN UNKNOWN
> >
> > by mapping it to the output of the semi-join algorithm:
> >
> > SELECT empno, deptno,
> > case when allNulls then unknown else match end AS “in”,
> > case when anyNulls then unknown else not match end AS “notIn”
> > FROM SJ
> >
> >
> >
> >
> >
> >
> >
> >
> > > On Jul 22, 2020, at 8:57 AM, Vladimir Sitnikov <
> sitnikov.vladimir@gmail.com> wrote:
> > >
> > > Julian> Vladimir said he *expected* Oracle would implement (3-valued)
> NOT
> > > IN efficiently. (Back in the day, when I was at Oracle, they certainly
> did
> > > not.) Does anyone have any evidence that they do?
> > >
> > > Well, Oracle has "null aware" joins since Oracle 11g which is more
> than 10
> > > years old.
> > > I have not tested the actual performance of the `null-aware join`,
> however,
> > > it would be extremely surprising, if `null-aware join` was less
> efficient
> > > than "manually crafted aggregate + join + join + whatever".
> > >
> > > That is why I think it is important to be able to generate regular
> "not in"
> > > plans.
> > >
> > > Vladimir
> >
> >
>
Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Haisheng Yuan <hy...@apache.org>.
I am not sure I get your idea.
What will the logical plan and physical plan look like for the following query?
SELECT * FROM foo WHERE a NOT IN (SELECT b FROM bar); -- bar.b is nullable
On 2020/07/23 01:35:44, Julian Hyde <jh...@gmail.com> wrote:
> How about a semi-join algorithm that adds column that hold the nature of the match? This algorithm can be used to evaluate 3-valued IN and 3-valued NOT IN queries.
>
> Generalizing further, it could compute any “ANY (predicate)” or “ALL (predicate)” condition as a column with values TRUE/FALSE/UNKNOWN. For instance “empno NOT IN …” is equivalent to “ALL(empno <> …)”.
>
> Here is an example.
>
> Emp table:
>
> empno deptno mgr
> ===== ====== ====
> 100 10 NULL
> 101 10 100
> 102 20 101
> 103 30 100
> 104 30 103
> 105 40 NULL
>
>
> The semi-join algorithm calculates the following intermediate result SJ:
>
> empno deptno mgrs match anyNulls allNulls
> ===== ====== =========== ===== ======== ========
> 100 10 [NULL, 100] TRUE TRUE FALSE
> 101 10 [NULL, 100] FALSE TRUE FALSE
> 102 20 [101] FALSE FALSE FALSE
> 103 30 [100, 103] TRUE FALSE FALSE
> 104 30 [100, 103] FALSE FALSE TRUE
> 105 40 [NULL] FALSE TRUE TRUE
>
> So it can answer the following query:
>
> SELECT empno,
> deptno,
> empno IN (SELECT mgr FROM Emp
> WHERE deptno = e.deptno) AS “in",
> empno NOT IN (SELECT mgr FROM Emp
> WHERE deptno = e.deptno) AS “notIn"
> FROM Emp AS e;
>
> empno deptno in notIn
> ===== ====== ======= =====
> 100 10 TRUE FALSE
> 101 10 FALSE UNKNOWN
> 102 20 FALSE TRUE
> 103 30 TRUE FALSE
> 104 40 FALSE FALSE
> 105 50 UNKNOWN UNKNOWN
>
> by mapping it to the output of the semi-join algorithm:
>
> SELECT empno, deptno,
> case when allNulls then unknown else match end AS “in”,
> case when anyNulls then unknown else not match end AS “notIn”
> FROM SJ
>
>
>
>
>
>
>
>
> > On Jul 22, 2020, at 8:57 AM, Vladimir Sitnikov <si...@gmail.com> wrote:
> >
> > Julian> Vladimir said he *expected* Oracle would implement (3-valued) NOT
> > IN efficiently. (Back in the day, when I was at Oracle, they certainly did
> > not.) Does anyone have any evidence that they do?
> >
> > Well, Oracle has "null aware" joins since Oracle 11g which is more than 10
> > years old.
> > I have not tested the actual performance of the `null-aware join`, however,
> > it would be extremely surprising, if `null-aware join` was less efficient
> > than "manually crafted aggregate + join + join + whatever".
> >
> > That is why I think it is important to be able to generate regular "not in"
> > plans.
> >
> > Vladimir
>
>
Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Julian Hyde <jh...@gmail.com>.
How about a semi-join algorithm that adds column that hold the nature of the match? This algorithm can be used to evaluate 3-valued IN and 3-valued NOT IN queries.
Generalizing further, it could compute any “ANY (predicate)” or “ALL (predicate)” condition as a column with values TRUE/FALSE/UNKNOWN. For instance “empno NOT IN …” is equivalent to “ALL(empno <> …)”.
Here is an example.
Emp table:
empno deptno mgr
===== ====== ====
100 10 NULL
101 10 100
102 20 101
103 30 100
104 30 103
105 40 NULL
The semi-join algorithm calculates the following intermediate result SJ:
empno deptno mgrs match anyNulls allNulls
===== ====== =========== ===== ======== ========
100 10 [NULL, 100] TRUE TRUE FALSE
101 10 [NULL, 100] FALSE TRUE FALSE
102 20 [101] FALSE FALSE FALSE
103 30 [100, 103] TRUE FALSE FALSE
104 30 [100, 103] FALSE FALSE TRUE
105 40 [NULL] FALSE TRUE TRUE
So it can answer the following query:
SELECT empno,
deptno,
empno IN (SELECT mgr FROM Emp
WHERE deptno = e.deptno) AS “in",
empno NOT IN (SELECT mgr FROM Emp
WHERE deptno = e.deptno) AS “notIn"
FROM Emp AS e;
empno deptno in notIn
===== ====== ======= =====
100 10 TRUE FALSE
101 10 FALSE UNKNOWN
102 20 FALSE TRUE
103 30 TRUE FALSE
104 40 FALSE FALSE
105 50 UNKNOWN UNKNOWN
by mapping it to the output of the semi-join algorithm:
SELECT empno, deptno,
case when allNulls then unknown else match end AS “in”,
case when anyNulls then unknown else not match end AS “notIn”
FROM SJ
> On Jul 22, 2020, at 8:57 AM, Vladimir Sitnikov <si...@gmail.com> wrote:
>
> Julian> Vladimir said he *expected* Oracle would implement (3-valued) NOT
> IN efficiently. (Back in the day, when I was at Oracle, they certainly did
> not.) Does anyone have any evidence that they do?
>
> Well, Oracle has "null aware" joins since Oracle 11g which is more than 10
> years old.
> I have not tested the actual performance of the `null-aware join`, however,
> it would be extremely surprising, if `null-aware join` was less efficient
> than "manually crafted aggregate + join + join + whatever".
>
> That is why I think it is important to be able to generate regular "not in"
> plans.
>
> Vladimir
Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Vladimir Sitnikov <si...@gmail.com>.
Julian> Vladimir said he *expected* Oracle would implement (3-valued) NOT
IN efficiently. (Back in the day, when I was at Oracle, they certainly did
not.) Does anyone have any evidence that they do?
Well, Oracle has "null aware" joins since Oracle 11g which is more than 10
years old.
I have not tested the actual performance of the `null-aware join`, however,
it would be extremely surprising, if `null-aware join` was less efficient
than "manually crafted aggregate + join + join + whatever".
That is why I think it is important to be able to generate regular "not in"
plans.
Vladimir
Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Julian Hyde <jh...@gmail.com>.
Haisheng,
You are confusing logical and physical algebra.
A target DB might have physical operators that can implement several logical operators. Just because an IN list is represented as an OR it doesn’t mean that it has to be executed as an OR.
We don’t HAVE TO add every physical operation into our logical algebra. We may choose to. There is a tradeoff - if we add a feature to our logical language, we have to revisit all of our transformation rules to deal with it.
Vladimir said he *expected* Oracle would implement (3-valued) NOT IN efficiently. (Back in the day, when I was at Oracle, they certainly did not.) Does anyone have any evidence that they do?
Julian
> On Jul 21, 2020, at 1:17 PM, Haisheng Yuan <hy...@apache.org> wrote:
>
> Thanks Julian for explaining the NOT IN to everyone. I am sorry for not making myself clear.
>
> For that kind of simple 2-valued logic uncorrelated NOT IN subquery, SQL Server and Greenplum can generate efficient plan with null aware ANTI SEMI join.
>
> Hash ANTI SEMI Join for NOT IN
> Join Condition: t1.a = t2.a
> -> Table Scan on t1
> -> Hash
> -> Table Scan on t2
>
> ANTI_NOTIN can be interpreted as null awareness ANTI joins. As vlsi pointed out, Oracle supports that too.
>
> Of course, that requires the query executor to deal specifically with this kind of join. But optimizer should not be the database's bottleneck, it should generate as good plan as possible, if the query executor can support the operator, that is good. If not, downstream project just disable it.
>
> Just like "a in (1,2,3...1000)", many databases (Greenplum, Postgres, Tidb ...) support implicit lookup inside the Filter operator, it doesn't need to be expanded to OR, or an explicit inner join. The implicit lookup is more efficient. I think the downstream would love to adapt to support the good plan, if not, they can choose to disable it, or rewrite to the form they support during post-processing stage after best plan is generated. But we can't limit us not to generate this kind of plan because some downstream project might not support it.
>
> On 2020/07/21 18:41:39, Julian Hyde <jh...@apache.org> wrote:
>> I want to remind everyone how hard it is to evaluate NOT IN queries.
>> Here is an example query:
>>
>> sqlline> !connect
>> jdbc:calcite:model=core/build/resources/test/hsqldb-model.json sa sa
>>> !set outputFormat csv
>>> EXPLAIN PLAN FOR SELECT * FROM dept WHERE deptno NOT IN (SELECT mgr FROM emp);
>> EnumerableCalc(expr#0..6=[{inputs}], expr#7=[0], expr#8=[=($t3, $t7)],
>> expr#9=[IS NULL($t6)], expr#10=[>=($t4, $t3)], expr#11=[AND($t9,
>> $t10)], expr#12=[OR($t8, $t11)], proj#0..2=[{exprs}],
>> $condition=[$t12])
>> EnumerableHashJoin(condition=[=($0, $5)], joinType=[left])
>> EnumerableNestedLoopJoin(condition=[true], joinType=[inner])
>> JdbcToEnumerableConverter
>> JdbcTableScan(table=[[SCOTT, DEPT]])
>> JdbcToEnumerableConverter
>> JdbcAggregate(group=[{}], c=[COUNT()], ck=[COUNT($3)])
>> JdbcTableScan(table=[[SCOTT, EMP]])
>> JdbcToEnumerableConverter
>> JdbcAggregate(group=[{0, 1}])
>> JdbcProject(MGR=[$3], i=[true])
>> JdbcTableScan(table=[[SCOTT, EMP]])
>>> EXPLAIN PLAN WITHOUT IMPLEMENTATION FOR SELECT * FROM dept WHERE deptno NOT IN (SELECT mgr FROM emp);
>> LogicalProject(DEPTNO=[$0], DNAME=[$1], LOC=[$2])
>> LogicalFilter(condition=[NOT(IN($0, {
>> LogicalProject(MGR=[$3])
>> JdbcTableScan(table=[[SCOTT, EMP]])
>> }))])
>> JdbcTableScan(table=[[SCOTT, DEPT]])
>>
>> Why is the physical plan so complicated? Because 'mgr' is nullable. We
>> need to account for 3 different cases:
>>
>> 1. dept.deptno is NULL (and therefore 'deptno NOT IN ...' evaluates to
>> UNKNOWN for every row where dept.deptno is NULL);
>> 2. dept.deptno is not NULL and the sub-query returns at least one NULL
>> value for mgr (and therefore 'deptno not in ...' evaluates to UNKNOWN
>> for every row);
>> 3. dept.deptno is not NULL and the sub-query returns only non-NULL
>> values of mgr (and therefore 'deptno not in ...' evaluates to TRUE or
>> FALSE for every row).
>>
>> To distinguish between cases 2 and 3, the plan counts the number of
>> values and the number of not-null values from the sub-query.
>>
>> I say that 'NOT IN is toxic' because a single null value in the
>> sub-query affects the result. The IN sub-query returns 3 values and
>> relational join can only account for two - match or not match.
>>
>> There are actually cases where we care about the 3 values of IN. For
>> example 'SELECT *, deptno IN (SELECT mgr FROM emp) FROM dept'. But
>> usually IN occurs inside WHERE, and we can safely fold UNKNOWN into
>> FALSE.
>>
>> It is tempting to talk about the cases where there are no NULL keys,
>> or UNKNOWN can safely be folded into FALSE. But I think we should be
>> talking about 3-valued IN (e.g. the scalar sub-query in the previous
>> paragraph). If we can solve that, we can easily convert to a solution
>> for 3-valued NOT IN.
>>
>> Julian
>>
>> On Mon, Jul 20, 2020 at 11:25 PM Haisheng Yuan <hy...@apache.org> wrote:
>>>
>>> I think they might be orthogonal.
>>> It is all about sub-query.
>>>
>>> On 2020/07/21 05:48:54, Danny Chan <yu...@gmail.com> wrote:
>>>> If it is only constant NOT IN predicate, how difficult it is to rewrite it into a normal composite AND predicate before entering the planning phrase ?
>>>>
>>>> Best,
>>>> Danny Chan
>>>> 在 2020年7月21日 +0800 PM12:35，Haisheng Yuan <hy...@apache.org>，写道：
>>>>> Thanks Jinpeng for providing a good example for not in subquery.
>>>>>
>>>>> I 100% agree with you that correlated query won't be represented by ANTI_NOTIN join type, and it is not the proposal's intention. Here what we are discussing is not to use ANTI_NOTIN to represent all the NOT IN sub-queries, that is impossible. Instead, if you take a close look at the example query, it is a simple uncorrelated NOT IN sub-query. That is the target. Let's focus on that kind of query, ask ourselves this question: Can such a simple query be transformed into a ANTI join to make the plan efficient?
>>>>>
>>>>> Sadly no. The reality is that this kind of query is not uncommon, may be much more common than correlated NOT IN sub-queries.
>>>>>
>>>>>
>>>>> Reply to Julian:
>>>>>>> How about making a sub-query type (in RexSubQuery), so it is gone
>>>>>>> before we reach algebra.
>>>>> It will be nice to have a NOT_IN subquery type, without expanding NOT IN to NOT(IN....).
>>>>> However, if there is no ANTI_NOTIN in the join type (without reaching algebra), does that mean the optimizer still can't generate efficient plan for simple NOT IN sub-queries?
>>>>>
>>>>>>> ANTI_NOTIN is a terrible name. ANTI means 'opposite' to ANTI_NOTIN is
>>>>>>> the opposite of NOT IN?!
>>>>> It depends how people interpret ANTI. You interpret it as "opposite", I interpret it as "ANTI JOIN", means "anti join for NOT IN, instead of NOT EXISTS". But it is just a naming issue, I am OK to change it whatever name that makes sense to the community, as long as it can convey the meaning.
>>>>>
>>>>> Thanks,
>>>>> Haisheng
>>>>>
>>>>> On 2020/07/21 03:02:20, Jinpeng Wu <wj...@gmail.com> wrote:
>>>>>> 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 <jh...@apache.org> 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 <hy...@apache.org> 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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com>
>>>>>>> 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<jh...@apache.org>
>>>>>>>>>>> 日 期：2020年07月20日 11:56:35
>>>>>>>>>>> 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org>
>>>>>>> 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
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>
>>>>>>
>>>>
>>
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Haisheng Yuan <hy...@apache.org>.
Thanks Julian for explaining the NOT IN to everyone. I am sorry for not making myself clear.
For that kind of simple 2-valued logic uncorrelated NOT IN subquery, SQL Server and Greenplum can generate efficient plan with null aware ANTI SEMI join.
Hash ANTI SEMI Join for NOT IN
Join Condition: t1.a = t2.a
-> Table Scan on t1
-> Hash
-> Table Scan on t2
ANTI_NOTIN can be interpreted as null awareness ANTI joins. As vlsi pointed out, Oracle supports that too.
Of course, that requires the query executor to deal specifically with this kind of join. But optimizer should not be the database's bottleneck, it should generate as good plan as possible, if the query executor can support the operator, that is good. If not, downstream project just disable it.
Just like "a in (1,2,3...1000)", many databases (Greenplum, Postgres, Tidb ...) support implicit lookup inside the Filter operator, it doesn't need to be expanded to OR, or an explicit inner join. The implicit lookup is more efficient. I think the downstream would love to adapt to support the good plan, if not, they can choose to disable it, or rewrite to the form they support during post-processing stage after best plan is generated. But we can't limit us not to generate this kind of plan because some downstream project might not support it.
On 2020/07/21 18:41:39, Julian Hyde <jh...@apache.org> wrote:
> I want to remind everyone how hard it is to evaluate NOT IN queries.
> Here is an example query:
>
> sqlline> !connect
> jdbc:calcite:model=core/build/resources/test/hsqldb-model.json sa sa
> > !set outputFormat csv
> > EXPLAIN PLAN FOR SELECT * FROM dept WHERE deptno NOT IN (SELECT mgr FROM emp);
> EnumerableCalc(expr#0..6=[{inputs}], expr#7=[0], expr#8=[=($t3, $t7)],
> expr#9=[IS NULL($t6)], expr#10=[>=($t4, $t3)], expr#11=[AND($t9,
> $t10)], expr#12=[OR($t8, $t11)], proj#0..2=[{exprs}],
> $condition=[$t12])
> EnumerableHashJoin(condition=[=($0, $5)], joinType=[left])
> EnumerableNestedLoopJoin(condition=[true], joinType=[inner])
> JdbcToEnumerableConverter
> JdbcTableScan(table=[[SCOTT, DEPT]])
> JdbcToEnumerableConverter
> JdbcAggregate(group=[{}], c=[COUNT()], ck=[COUNT($3)])
> JdbcTableScan(table=[[SCOTT, EMP]])
> JdbcToEnumerableConverter
> JdbcAggregate(group=[{0, 1}])
> JdbcProject(MGR=[$3], i=[true])
> JdbcTableScan(table=[[SCOTT, EMP]])
> > EXPLAIN PLAN WITHOUT IMPLEMENTATION FOR SELECT * FROM dept WHERE deptno NOT IN (SELECT mgr FROM emp);
> LogicalProject(DEPTNO=[$0], DNAME=[$1], LOC=[$2])
> LogicalFilter(condition=[NOT(IN($0, {
> LogicalProject(MGR=[$3])
> JdbcTableScan(table=[[SCOTT, EMP]])
> }))])
> JdbcTableScan(table=[[SCOTT, DEPT]])
>
> Why is the physical plan so complicated? Because 'mgr' is nullable. We
> need to account for 3 different cases:
>
> 1. dept.deptno is NULL (and therefore 'deptno NOT IN ...' evaluates to
> UNKNOWN for every row where dept.deptno is NULL);
> 2. dept.deptno is not NULL and the sub-query returns at least one NULL
> value for mgr (and therefore 'deptno not in ...' evaluates to UNKNOWN
> for every row);
> 3. dept.deptno is not NULL and the sub-query returns only non-NULL
> values of mgr (and therefore 'deptno not in ...' evaluates to TRUE or
> FALSE for every row).
>
> To distinguish between cases 2 and 3, the plan counts the number of
> values and the number of not-null values from the sub-query.
>
> I say that 'NOT IN is toxic' because a single null value in the
> sub-query affects the result. The IN sub-query returns 3 values and
> relational join can only account for two - match or not match.
>
> There are actually cases where we care about the 3 values of IN. For
> example 'SELECT *, deptno IN (SELECT mgr FROM emp) FROM dept'. But
> usually IN occurs inside WHERE, and we can safely fold UNKNOWN into
> FALSE.
>
> It is tempting to talk about the cases where there are no NULL keys,
> or UNKNOWN can safely be folded into FALSE. But I think we should be
> talking about 3-valued IN (e.g. the scalar sub-query in the previous
> paragraph). If we can solve that, we can easily convert to a solution
> for 3-valued NOT IN.
>
> Julian
>
> On Mon, Jul 20, 2020 at 11:25 PM Haisheng Yuan <hy...@apache.org> wrote:
> >
> > I think they might be orthogonal.
> > It is all about sub-query.
> >
> > On 2020/07/21 05:48:54, Danny Chan <yu...@gmail.com> wrote:
> > > If it is only constant NOT IN predicate, how difficult it is to rewrite it into a normal composite AND predicate before entering the planning phrase ?
> > >
> > > Best,
> > > Danny Chan
> > > 在 2020年7月21日 +0800 PM12:35，Haisheng Yuan <hy...@apache.org>，写道：
> > > > Thanks Jinpeng for providing a good example for not in subquery.
> > > >
> > > > I 100% agree with you that correlated query won't be represented by ANTI_NOTIN join type, and it is not the proposal's intention. Here what we are discussing is not to use ANTI_NOTIN to represent all the NOT IN sub-queries, that is impossible. Instead, if you take a close look at the example query, it is a simple uncorrelated NOT IN sub-query. That is the target. Let's focus on that kind of query, ask ourselves this question: Can such a simple query be transformed into a ANTI join to make the plan efficient?
> > > >
> > > > Sadly no. The reality is that this kind of query is not uncommon, may be much more common than correlated NOT IN sub-queries.
> > > >
> > > >
> > > > Reply to Julian:
> > > > > > How about making a sub-query type (in RexSubQuery), so it is gone
> > > > > > before we reach algebra.
> > > > It will be nice to have a NOT_IN subquery type, without expanding NOT IN to NOT(IN....).
> > > > However, if there is no ANTI_NOTIN in the join type (without reaching algebra), does that mean the optimizer still can't generate efficient plan for simple NOT IN sub-queries?
> > > >
> > > > > > ANTI_NOTIN is a terrible name. ANTI means 'opposite' to ANTI_NOTIN is
> > > > > > the opposite of NOT IN?!
> > > > It depends how people interpret ANTI. You interpret it as "opposite", I interpret it as "ANTI JOIN", means "anti join for NOT IN, instead of NOT EXISTS". But it is just a naming issue, I am OK to change it whatever name that makes sense to the community, as long as it can convey the meaning.
> > > >
> > > > Thanks,
> > > > Haisheng
> > > >
> > > > On 2020/07/21 03:02:20, Jinpeng Wu <wj...@gmail.com> wrote:
> > > > > 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 <jh...@apache.org> 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 <hy...@apache.org> 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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com>
> > > > > > 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<jh...@apache.org>
> > > > > > > > > > 日 期：2020年07月20日 11:56:35
> > > > > > > > > > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org>
> > > > > > 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
> > > > > > > > > > >
> > > > > > > > > > >
> > > > > > > > > >
> > > > > > > > >
> > > > > > > >
> > > > > >
> > > > >
> > >
>
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Vladimir Sitnikov <si...@gmail.com>.
Just in case: Oracle DB has 'null aware' joins. For instance: 'hash join
anti na' which is a single join with two inputs.
I expect that databases can implement 'not in' semantics efficiently (at
least they should be more efficient than enumerable)
Vladimir
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Julian Hyde <jh...@apache.org>.
I want to remind everyone how hard it is to evaluate NOT IN queries.
Here is an example query:
sqlline> !connect
jdbc:calcite:model=core/build/resources/test/hsqldb-model.json sa sa
> !set outputFormat csv
> EXPLAIN PLAN FOR SELECT * FROM dept WHERE deptno NOT IN (SELECT mgr FROM emp);
EnumerableCalc(expr#0..6=[{inputs}], expr#7=[0], expr#8=[=($t3, $t7)],
expr#9=[IS NULL($t6)], expr#10=[>=($t4, $t3)], expr#11=[AND($t9,
$t10)], expr#12=[OR($t8, $t11)], proj#0..2=[{exprs}],
$condition=[$t12])
EnumerableHashJoin(condition=[=($0, $5)], joinType=[left])
EnumerableNestedLoopJoin(condition=[true], joinType=[inner])
JdbcToEnumerableConverter
JdbcTableScan(table=[[SCOTT, DEPT]])
JdbcToEnumerableConverter
JdbcAggregate(group=[{}], c=[COUNT()], ck=[COUNT($3)])
JdbcTableScan(table=[[SCOTT, EMP]])
JdbcToEnumerableConverter
JdbcAggregate(group=[{0, 1}])
JdbcProject(MGR=[$3], i=[true])
JdbcTableScan(table=[[SCOTT, EMP]])
> EXPLAIN PLAN WITHOUT IMPLEMENTATION FOR SELECT * FROM dept WHERE deptno NOT IN (SELECT mgr FROM emp);
LogicalProject(DEPTNO=[$0], DNAME=[$1], LOC=[$2])
LogicalFilter(condition=[NOT(IN($0, {
LogicalProject(MGR=[$3])
JdbcTableScan(table=[[SCOTT, EMP]])
}))])
JdbcTableScan(table=[[SCOTT, DEPT]])
Why is the physical plan so complicated? Because 'mgr' is nullable. We
need to account for 3 different cases:
1. dept.deptno is NULL (and therefore 'deptno NOT IN ...' evaluates to
UNKNOWN for every row where dept.deptno is NULL);
2. dept.deptno is not NULL and the sub-query returns at least one NULL
value for mgr (and therefore 'deptno not in ...' evaluates to UNKNOWN
for every row);
3. dept.deptno is not NULL and the sub-query returns only non-NULL
values of mgr (and therefore 'deptno not in ...' evaluates to TRUE or
FALSE for every row).
To distinguish between cases 2 and 3, the plan counts the number of
values and the number of not-null values from the sub-query.
I say that 'NOT IN is toxic' because a single null value in the
sub-query affects the result. The IN sub-query returns 3 values and
relational join can only account for two - match or not match.
There are actually cases where we care about the 3 values of IN. For
example 'SELECT *, deptno IN (SELECT mgr FROM emp) FROM dept'. But
usually IN occurs inside WHERE, and we can safely fold UNKNOWN into
FALSE.
It is tempting to talk about the cases where there are no NULL keys,
or UNKNOWN can safely be folded into FALSE. But I think we should be
talking about 3-valued IN (e.g. the scalar sub-query in the previous
paragraph). If we can solve that, we can easily convert to a solution
for 3-valued NOT IN.
Julian
On Mon, Jul 20, 2020 at 11:25 PM Haisheng Yuan <hy...@apache.org> wrote:
>
> I think they might be orthogonal.
> It is all about sub-query.
>
> On 2020/07/21 05:48:54, Danny Chan <yu...@gmail.com> wrote:
> > If it is only constant NOT IN predicate, how difficult it is to rewrite it into a normal composite AND predicate before entering the planning phrase ?
> >
> > Best,
> > Danny Chan
> > 在 2020年7月21日 +0800 PM12:35，Haisheng Yuan <hy...@apache.org>，写道：
> > > Thanks Jinpeng for providing a good example for not in subquery.
> > >
> > > I 100% agree with you that correlated query won't be represented by ANTI_NOTIN join type, and it is not the proposal's intention. Here what we are discussing is not to use ANTI_NOTIN to represent all the NOT IN sub-queries, that is impossible. Instead, if you take a close look at the example query, it is a simple uncorrelated NOT IN sub-query. That is the target. Let's focus on that kind of query, ask ourselves this question: Can such a simple query be transformed into a ANTI join to make the plan efficient?
> > >
> > > Sadly no. The reality is that this kind of query is not uncommon, may be much more common than correlated NOT IN sub-queries.
> > >
> > >
> > > Reply to Julian:
> > > > > How about making a sub-query type (in RexSubQuery), so it is gone
> > > > > before we reach algebra.
> > > It will be nice to have a NOT_IN subquery type, without expanding NOT IN to NOT(IN....).
> > > However, if there is no ANTI_NOTIN in the join type (without reaching algebra), does that mean the optimizer still can't generate efficient plan for simple NOT IN sub-queries?
> > >
> > > > > ANTI_NOTIN is a terrible name. ANTI means 'opposite' to ANTI_NOTIN is
> > > > > the opposite of NOT IN?!
> > > It depends how people interpret ANTI. You interpret it as "opposite", I interpret it as "ANTI JOIN", means "anti join for NOT IN, instead of NOT EXISTS". But it is just a naming issue, I am OK to change it whatever name that makes sense to the community, as long as it can convey the meaning.
> > >
> > > Thanks,
> > > Haisheng
> > >
> > > On 2020/07/21 03:02:20, Jinpeng Wu <wj...@gmail.com> wrote:
> > > > 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 <jh...@apache.org> 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 <hy...@apache.org> 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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com>
> > > > > 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<jh...@apache.org>
> > > > > > > > > 日 期：2020年07月20日 11:56:35
> > > > > > > > > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org>
> > > > > 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
> > > > > > > > > >
> > > > > > > > > >
> > > > > > > > >
> > > > > > > >
> > > > > > >
> > > > >
> > > >
> >
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Haisheng Yuan <hy...@apache.org>.
I think they might be orthogonal.
It is all about sub-query.
On 2020/07/21 05:48:54, Danny Chan <yu...@gmail.com> wrote:
> If it is only constant NOT IN predicate, how difficult it is to rewrite it into a normal composite AND predicate before entering the planning phrase ?
>
> Best,
> Danny Chan
> 在 2020年7月21日 +0800 PM12:35，Haisheng Yuan <hy...@apache.org>，写道：
> > Thanks Jinpeng for providing a good example for not in subquery.
> >
> > I 100% agree with you that correlated query won't be represented by ANTI_NOTIN join type, and it is not the proposal's intention. Here what we are discussing is not to use ANTI_NOTIN to represent all the NOT IN sub-queries, that is impossible. Instead, if you take a close look at the example query, it is a simple uncorrelated NOT IN sub-query. That is the target. Let's focus on that kind of query, ask ourselves this question: Can such a simple query be transformed into a ANTI join to make the plan efficient?
> >
> > Sadly no. The reality is that this kind of query is not uncommon, may be much more common than correlated NOT IN sub-queries.
> >
> >
> > Reply to Julian:
> > > > How about making a sub-query type (in RexSubQuery), so it is gone
> > > > before we reach algebra.
> > It will be nice to have a NOT_IN subquery type, without expanding NOT IN to NOT(IN....).
> > However, if there is no ANTI_NOTIN in the join type (without reaching algebra), does that mean the optimizer still can't generate efficient plan for simple NOT IN sub-queries?
> >
> > > > ANTI_NOTIN is a terrible name. ANTI means 'opposite' to ANTI_NOTIN is
> > > > the opposite of NOT IN?!
> > It depends how people interpret ANTI. You interpret it as "opposite", I interpret it as "ANTI JOIN", means "anti join for NOT IN, instead of NOT EXISTS". But it is just a naming issue, I am OK to change it whatever name that makes sense to the community, as long as it can convey the meaning.
> >
> > Thanks,
> > Haisheng
> >
> > On 2020/07/21 03:02:20, Jinpeng Wu <wj...@gmail.com> wrote:
> > > 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 <jh...@apache.org> 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 <hy...@apache.org> 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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com>
> > > > 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<jh...@apache.org>
> > > > > > > > 日 期：2020年07月20日 11:56:35
> > > > > > > > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org>
> > > > 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
> > > > > > > > >
> > > > > > > > >
> > > > > > > >
> > > > > > >
> > > > > >
> > > >
> > >
>
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Danny Chan <yu...@gmail.com>.
If it is only constant NOT IN predicate, how difficult it is to rewrite it into a normal composite AND predicate before entering the planning phrase ?
Best,
Danny Chan
在 2020年7月21日 +0800 PM12:35，Haisheng Yuan <hy...@apache.org>，写道：
> Thanks Jinpeng for providing a good example for not in subquery.
>
> I 100% agree with you that correlated query won't be represented by ANTI_NOTIN join type, and it is not the proposal's intention. Here what we are discussing is not to use ANTI_NOTIN to represent all the NOT IN sub-queries, that is impossible. Instead, if you take a close look at the example query, it is a simple uncorrelated NOT IN sub-query. That is the target. Let's focus on that kind of query, ask ourselves this question: Can such a simple query be transformed into a ANTI join to make the plan efficient?
>
> Sadly no. The reality is that this kind of query is not uncommon, may be much more common than correlated NOT IN sub-queries.
>
>
> Reply to Julian:
> > > How about making a sub-query type (in RexSubQuery), so it is gone
> > > before we reach algebra.
> It will be nice to have a NOT_IN subquery type, without expanding NOT IN to NOT(IN....).
> However, if there is no ANTI_NOTIN in the join type (without reaching algebra), does that mean the optimizer still can't generate efficient plan for simple NOT IN sub-queries?
>
> > > ANTI_NOTIN is a terrible name. ANTI means 'opposite' to ANTI_NOTIN is
> > > the opposite of NOT IN?!
> It depends how people interpret ANTI. You interpret it as "opposite", I interpret it as "ANTI JOIN", means "anti join for NOT IN, instead of NOT EXISTS". But it is just a naming issue, I am OK to change it whatever name that makes sense to the community, as long as it can convey the meaning.
>
> Thanks,
> Haisheng
>
> On 2020/07/21 03:02:20, Jinpeng Wu <wj...@gmail.com> wrote:
> > 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 <jh...@apache.org> 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 <hy...@apache.org> 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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com>
> > > 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<jh...@apache.org>
> > > > > > > 日 期：2020年07月20日 11:56:35
> > > > > > > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org>
> > > 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
> > > > > > > >
> > > > > > > >
> > > > > > >
> > > > > >
> > > > >
> > >
> >
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Haisheng Yuan <hy...@apache.org>.
Thanks Jinpeng for providing a good example for not in subquery.
I 100% agree with you that correlated query won't be represented by ANTI_NOTIN join type, and it is not the proposal's intention. Here what we are discussing is not to use ANTI_NOTIN to represent all the NOT IN sub-queries, that is impossible. Instead, if you take a close look at the example query, it is a simple uncorrelated NOT IN sub-query. That is the target. Let's focus on that kind of query, ask ourselves this question: Can such a simple query be transformed into a ANTI join to make the plan efficient?
Sadly no. The reality is that this kind of query is not uncommon, may be much more common than correlated NOT IN sub-queries.
Reply to Julian:
> > How about making a sub-query type (in RexSubQuery), so it is gone
> > before we reach algebra.
It will be nice to have a NOT_IN subquery type, without expanding NOT IN to NOT(IN....).
However, if there is no ANTI_NOTIN in the join type (without reaching algebra), does that mean the optimizer still can't generate efficient plan for simple NOT IN sub-queries?
> > ANTI_NOTIN is a terrible name. ANTI means 'opposite' to ANTI_NOTIN is
> > the opposite of NOT IN?!
It depends how people interpret ANTI. You interpret it as "opposite", I interpret it as "ANTI JOIN", means "anti join for NOT IN, instead of NOT EXISTS". But it is just a naming issue, I am OK to change it whatever name that makes sense to the community, as long as it can convey the meaning.
Thanks,
Haisheng
On 2020/07/21 03:02:20, Jinpeng Wu <wj...@gmail.com> wrote:
> 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 <jh...@apache.org> 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 <hy...@apache.org> 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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com>
> > 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<jh...@apache.org>
> > > > > > 日 期：2020年07月20日 11:56:35
> > > > > > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org>
> > 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
> > > > > > >
> > > > > > >
> > > > > >
> > > > >
> > > >
> >
>
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Jinpeng Wu <wj...@gmail.com>.
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 <jh...@apache.org> 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 <hy...@apache.org> 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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com>
> 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<jh...@apache.org>
> > > > > 日 期：2020年07月20日 11:56:35
> > > > > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org>
> 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
> > > > > >
> > > > > >
> > > > >
> > > >
> > >
>
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Julian Hyde <jh...@apache.org>.
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 <hy...@apache.org> 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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com> 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<jh...@apache.org>
> > > > 日 期：2020年07月20日 11:56:35
> > > > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org> 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
> > > > >
> > > > >
> > > >
> > >
> >
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Haisheng Yuan <hy...@apache.org>.
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 <hy...@apache.org> 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 <ru...@gmail.com> 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 <h....@alibaba-inc.com> 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<jh...@apache.org>
> > > 日 期：2020年07月20日 11:56:35
> > > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org> 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
> > > >
> > > >
> > >
> >
>
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Haisheng Yuan <hy...@apache.org>.
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 <ru...@gmail.com> 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 <h....@alibaba-inc.com> 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<jh...@apache.org>
> > 日 期：2020年07月20日 11:56:35
> > 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org> 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
> > >
> > >
> >
>
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Ruben Q L <ru...@gmail.com>.
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 <h....@alibaba-inc.com> 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<jh...@apache.org>
> 日 期：2020年07月20日 11:56:35
> 收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org> 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
> >
> >
>
Re: Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Haisheng Yuan <h....@alibaba-inc.com>.
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<jh...@apache.org>
日 期：2020年07月20日 11:56:35
收件人：dev@calcite.apache.org<de...@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 <hy...@apache.org> 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
>
>
Re: [DISCUSS] New Join Type: ANTI_NOTIN
Posted by Julian Hyde <jh...@apache.org>.
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 <hy...@apache.org> 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
>
>