Converting NOT IN to anti-joins during planning

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Converting NOT IN to anti-joins during planning

David Rowley-3
Way back in [1] I proposed that we allow NOT IN subqueries to be
converted into an anti-join where the subquery cannot return any NULL
values.   As Tom pointed out to me, I had neglected to consider that
the outer side producing NULLs can cause the anti-join plan to produce
incorrect results.  The difference is that a NOT IN where the subquery
returns no results filters nothing, otherwise it filters the nulls,
plus the records that exist in the subquery.

More recently over on [2], Jim and Zheng have re-proposed making
improvements in this area. Their ideas are slightly different from
mine as they propose to add an OR .. IS NULL clause to the join
condition to handle the outer side being NULL with empty subquery
problem.  Before Jim and Zheng's patch arrived I managed to fix the
known problems with my 4-year-old patch thinking it would have been
welcome, but it seems that's not the case, perhaps due to the
differing ideas we have on how this should work. At that time I didn't
think the other patch actually existed yet... oops

Anyway, I don't really want to drop my patch as I believe what it does
is correct and there's debate on the other thread about how good an
idea adding these OR clauses to the join quals is... (forces nested
loop plan (see [3])),  but it appears Jim and Zheng are fairly set on
that idea.  Hence...

I'm moving my patch here, so it can be debated without interfering
with the other work that's going on in this area.  There has also been
some review of my patch in [4], and of course, originally in [1].

The background is really.

1. Seems fine to do this transformation when there are no nulls.
2. We don't want to cost anything to decide on to do the
transformation or not, i.e do it regardless, in all possible cases
where it's valid to do so. We already do that for NOT EXISTS, no
apparent reason to think this case is any different.
3. Need to consider what planner overhead there is from doing this and
failing to do the conversion due lack of evidence for no NULLs.

I've not done #3, at least not with the latest patch.

There's already a CF entry [5] for this patch, although its targeting PG13.

The latest patch is attached.

[1] https://www.postgresql.org/message-id/CAApHDvqRB-iFBy68%3DdCgqS46aRep7AuN2pou4KTwL8kX9YOcTQ%40mail.gmail.com
[2] https://www.postgresql.org/message-id/1550706289606-0.post@...
[3] https://www.postgresql.org/message-id/CAKJS1f_ZwXtzPz6wDpBXgAVYuxforsqpc6hBw05Y6aPGcOONfA%40mail.gmail.com
[4] https://www.postgresql.org/message-id/18203.1551543939%40sss.pgh.pa.us
[5] https://commitfest.postgresql.org/22/2020/

--
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

not_in_anti_join_v1.3.patch (68K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

Jim Finnerty
Actually, we're working hard to integrate the two approaches.  I haven't had
time since I returned to review your patch, but I understand that you were
checking for strict predicates as part of the nullness checking criteria,
and we definitely must have that.  Zheng tells me that he has combined your
patch with ours, but before we put out a new patch, we're trying to figure
out how to preserve the existing NOT IN execution plan in the case where the
materialized subplan fits in memory.  This (good) plan is effectively an
in-memory hash anti-join.

This is tricky to do because the NOT IN Subplan to anti-join transformation
currently happens early in the planning process, whereas the decision to
materialize is made much later, when the best path is being converted into a
Plan.

Zheng is exploring whether we can defer doing the transformation until Plan
generation time.  If we can do that, then we can generate the
highest-performing plan in all (known) cases.



-----
Jim Finnerty, AWS, Amazon Aurora PostgreSQL
--
Sent from: http://www.postgresql-archive.org/PostgreSQL-hackers-f1928748.html

Jim Finnerty, AWS, Amazon Aurora PostgreSQL
Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

David Rowley-3
Hi Jim,

Thanks for replying here.

On Wed, 6 Mar 2019 at 16:37, Jim Finnerty <[hidden email]> wrote:

>
> Actually, we're working hard to integrate the two approaches.  I haven't had
> time since I returned to review your patch, but I understand that you were
> checking for strict predicates as part of the nullness checking criteria,
> and we definitely must have that.  Zheng tells me that he has combined your
> patch with ours, but before we put out a new patch, we're trying to figure
> out how to preserve the existing NOT IN execution plan in the case where the
> materialized subplan fits in memory.  This (good) plan is effectively an
> in-memory hash anti-join.
>
> This is tricky to do because the NOT IN Subplan to anti-join transformation
> currently happens early in the planning process, whereas the decision to
> materialize is made much later, when the best path is being converted into a
> Plan.

I guess you're still going with the OR ... IS NULL in your patch then?
otherwise, you'd likely find that the transformation (when NULLs are
not possible) is always a win since it'll allow hash anti-joins. (see
#2 in the original email on this thread)  FWIW I mentioned in [1] and
Tom confirmed in [2] that we both think hacking the join condition to
add an OR .. IS NULL is a bad idea. I guess you're not deterred by
that?

I'd say your next best move is, over on the other thread, to put up
your argument against what Tom and I mentioned, then detail out what
exactly you're planning. Likely this will save time. I personally
don't think that ignoring this part is going to allow you to progress
your patch too much further in PostgreSQL. Consensus about how $thing
works is something that's needed before the $thing can ever be
committed. Sometimes lack of objection can count, but an unaddressed
objection is not consensus. Not trying to make this hard, just trying
to explain the process.

[1] https://www.postgresql.org/message-id/CAKJS1f8q4S%2B5Z7WSRDWJd__SwqMr12JdWKXTDo35ptzneRvZnw%40mail.gmail.com
[2] https://www.postgresql.org/message-id/5420.1551487529%40sss.pgh.pa.us

--
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

David Rowley-3
In reply to this post by David Rowley-3
On Wed, 6 Mar 2019 at 12:54, David Rowley <[hidden email]> wrote:
> The latest patch is attached.

Rebased version after pgindent run.

--
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

not_in_anti_join_v1.4.patch (69K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

Antonin Houska-2
David Rowley <[hidden email]> wrote:

> On Wed, 6 Mar 2019 at 12:54, David Rowley <[hidden email]> wrote:
> > The latest patch is attached.
>
> Rebased version after pgindent run.

I've spent some time looking into this.

One problem I see is that SubLink can be in the JOIN/ON clause and thus it's
not necessarily at the top of the join tree. Consider this example:

CREATE TABLE a(i int);
CREATE TABLE b(j int);
CREATE TABLE c(k int NOT NULL);
CREATE TABLE d(l int);

  SELECT *
    FROM
        a
        JOIN b ON b.j NOT IN
                ( SELECT
                        c.k
                    FROM
                        c)
        JOIN d ON b.j = d.l;

Here the b.j=d.l condition makes the planner think that the "b.j NOT IN
(SELECT c.k FROM c)" sublink cannot receive NULL values of b.j, but that's not
true: it's possible that ((a JOIN b) ANTI JOIN c) is evaluated before "d" is
joined to the other tables, so the NULL values of b.j are not filtered out
early enough.

I thought it would help if find_innerjoined_rels(), when called from
expressions_are_not_nullable(), only collected rels (and quals) from the
subtree below the sublink, but that does not seem to help:

CREATE TABLE e(m int);

  SELECT *
    FROM
        a
        JOIN e ON a.i = e.m
        JOIN b ON a.i NOT IN
                ( SELECT
                        c.k
                    FROM
                        c)
        JOIN d ON COALESCE(a.i, 0) = COALESCE(d.l, 0);

Here it might seem that the a.i=e.m condition eliminates NULL values from the
ANTI JOIN input, but it's probably hard to prove at query preparation time
that

     (((a JOIN e) JOIN b) ANTI JOIN c) JOIN d

won't eventually be optimized to

     (((a JOIN d) JOIN b) ANTI JOIN c) JOIN e

Since the join condition between "a" and "d" is not strict in this case, the
ANTI JOIN will receive the NULL values of a.i.

It seems tricky, I've got no idea of an alternative approach right now.

--
Antonin Houska
Web: https://www.cybertec-postgresql.com


Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

Antonin Houska-2
Antonin Houska <[hidden email]> wrote:

> One problem I see is that SubLink can be in the JOIN/ON clause and thus it's
> not necessarily at the top of the join tree. Consider this example:
>
> CREATE TABLE a(i int);
> CREATE TABLE b(j int);
> CREATE TABLE c(k int NOT NULL);
> CREATE TABLE d(l int);
>
>   SELECT *
>     FROM
>         a
>         JOIN b ON b.j NOT IN
>                 ( SELECT
>                         c.k
>                     FROM
>                         c)
>         JOIN d ON b.j = d.l;
>
> Here the b.j=d.l condition makes the planner think that the "b.j NOT IN
> (SELECT c.k FROM c)" sublink cannot receive NULL values of b.j, but that's not
> true: it's possible that ((a JOIN b) ANTI JOIN c) is evaluated before "d" is
> joined to the other tables, so the NULL values of b.j are not filtered out
> early enough.
>
> I thought it would help if find_innerjoined_rels(), when called from
> expressions_are_not_nullable(), only collected rels (and quals) from the
> subtree below the sublink, but that does not seem to help:
>
> CREATE TABLE e(m int);
>
>   SELECT *
>     FROM
>         a
>         JOIN e ON a.i = e.m
>         JOIN b ON a.i NOT IN
>                 ( SELECT
>                         c.k
>                     FROM
>                         c)
>         JOIN d ON COALESCE(a.i, 0) = COALESCE(d.l, 0);
>
> Here it might seem that the a.i=e.m condition eliminates NULL values from the
> ANTI JOIN input, but it's probably hard to prove at query preparation time
> that
>
>      (((a JOIN e) JOIN b) ANTI JOIN c) JOIN d
>
> won't eventually be optimized to
>
>      (((a JOIN d) JOIN b) ANTI JOIN c) JOIN e
>
> Since the join condition between "a" and "d" is not strict in this case, the
> ANTI JOIN will receive the NULL values of a.i.
>
> It seems tricky, I've got no idea of an alternative approach right now.

Just one idea: perhaps we could use something like PlaceHolderVar to enforce
evaluation of the inner join expression ("a.i=e.m" in the example above) at
certain level of the join tree (in particular, below the ANTI JOIN) -
something like make_outerjoininfo() does here:

        /* Else, prevent join from being formed before we eval the PHV */
        min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);

Unlike the typical use of PHV, we would not have to check whether the
expression is not evaluated too low in the tree because the quals collected by
find_innerjoined_rels() should not reference nullable side of any outer join.

--
Antonin Houska
Web: https://www.cybertec-postgresql.com


Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

Simon Riggs
In reply to this post by David Rowley-3
On Wed, 6 Mar 2019 at 04:11, David Rowley <[hidden email]> wrote:
Hi Jim,

Thanks for replying here.

On Wed, 6 Mar 2019 at 16:37, Jim Finnerty <[hidden email]> wrote:
>
> Actually, we're working hard to integrate the two approaches.  I haven't had
> time since I returned to review your patch, but I understand that you were
> checking for strict predicates as part of the nullness checking criteria,
> and we definitely must have that.  Zheng tells me that he has combined your
> patch with ours, but before we put out a new patch, we're trying to figure
> out how to preserve the existing NOT IN execution plan in the case where the
> materialized subplan fits in memory.  This (good) plan is effectively an
> in-memory hash anti-join.
>
> This is tricky to do because the NOT IN Subplan to anti-join transformation
> currently happens early in the planning process, whereas the decision to
> materialize is made much later, when the best path is being converted into a
> Plan.

I guess you're still going with the OR ... IS NULL in your patch then?
otherwise, you'd likely find that the transformation (when NULLs are
not possible) is always a win since it'll allow hash anti-joins. (see
#2 in the original email on this thread)  FWIW I mentioned in [1] and
Tom confirmed in [2] that we both think hacking the join condition to
add an OR .. IS NULL is a bad idea. I guess you're not deterred by
that?

Surely we want both?

1. Transform when we can
2. Else apply some other approach if the cost can be reduced by doing it

--
Simon Riggs                http://www.2ndQuadrant.com/
PostgreSQL Solutions for the Enterprise
Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

David Rowley-3
On Fri, 14 Jun 2019 at 20:41, Simon Riggs <[hidden email]> wrote:

>
> On Wed, 6 Mar 2019 at 04:11, David Rowley <[hidden email]> wrote:
>>
>> Hi Jim,
>>
>> Thanks for replying here.
>>
>> On Wed, 6 Mar 2019 at 16:37, Jim Finnerty <[hidden email]> wrote:
>> >
>> > Actually, we're working hard to integrate the two approaches.  I haven't had
>> > time since I returned to review your patch, but I understand that you were
>> > checking for strict predicates as part of the nullness checking criteria,
>> > and we definitely must have that.  Zheng tells me that he has combined your
>> > patch with ours, but before we put out a new patch, we're trying to figure
>> > out how to preserve the existing NOT IN execution plan in the case where the
>> > materialized subplan fits in memory.  This (good) plan is effectively an
>> > in-memory hash anti-join.
>> >
>> > This is tricky to do because the NOT IN Subplan to anti-join transformation
>> > currently happens early in the planning process, whereas the decision to
>> > materialize is made much later, when the best path is being converted into a
>> > Plan.
>>
>> I guess you're still going with the OR ... IS NULL in your patch then?
>> otherwise, you'd likely find that the transformation (when NULLs are
>> not possible) is always a win since it'll allow hash anti-joins. (see
>> #2 in the original email on this thread)  FWIW I mentioned in [1] and
>> Tom confirmed in [2] that we both think hacking the join condition to
>> add an OR .. IS NULL is a bad idea. I guess you're not deterred by
>> that?
>
>
> Surely we want both?
>
> 1. Transform when we can
> 2. Else apply some other approach if the cost can be reduced by doing it

Maybe.  If the scope for the conversion is reduced to only add the OR
.. IS NULL join clause when the subplan could not be hashed then it's
maybe less likely to cause performance regressions. Remember that this
forces the planner to use a nested loop join since no other join
algorithms support OR clauses. I think Jim and Zheng have now changed
their patch to do that.  If we can perform a parameterised nested loop
join then that has a good chance of being better than scanning the
subquery multiple times, however, if there's no index to do a
parameterized nested loop, then we need to do a normal nested loop
which will perform poorly, but so will the non-hashed subplan...

# create table t1 (a int);
CREATE TABLE
# create table t2 (a int);
CREATE TABLE
# set work_mem = '64kB';
SET
# insert into t1 select generate_Series(1,10000);
INSERT 0 10000
# insert into t2 select generate_Series(1,10000);
INSERT 0 10000
# explain analyze select count(*) from t1 where a not in(select a from t2);
                                                        QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=1668739.50..1668739.51 rows=1 width=8) (actual
time=7079.077..7079.077 rows=1 loops=1)
   ->  Seq Scan on t1  (cost=0.00..1668725.16 rows=5738 width=0)
(actual time=7079.072..7079.072 rows=0 loops=1)
         Filter: (NOT (SubPlan 1))
         Rows Removed by Filter: 10000
         SubPlan 1
           ->  Materialize  (cost=0.00..262.12 rows=11475 width=4)
(actual time=0.004..0.397 rows=5000 loops=10000)
                 ->  Seq Scan on t2  (cost=0.00..159.75 rows=11475
width=4) (actual time=0.019..4.921 rows=10000 loops=1)
 Planning Time: 0.348 ms
 Execution Time: 7079.309 ms
(9 rows)

# explain analyze select count(*) from t1 where not exists(select 1
from t2 where t1.a = t2.a or t2.a is null);
                                                       QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=1250873.25..1250873.26 rows=1 width=8) (actual
time=7263.980..7263.980 rows=1 loops=1)
   ->  Nested Loop Anti Join  (cost=0.00..1250858.97 rows=5709
width=0) (actual time=7263.976..7263.976 rows=0 loops=1)
         Join Filter: ((t1.a = t2.a) OR (t2.a IS NULL))
         Rows Removed by Join Filter: 49995000
         ->  Seq Scan on t1  (cost=0.00..159.75 rows=11475 width=4)
(actual time=0.013..2.350 rows=10000 loops=1)
         ->  Materialize  (cost=0.00..262.12 rows=11475 width=4)
(actual time=0.004..0.396 rows=5000 loops=10000)
               ->  Seq Scan on t2  (cost=0.00..159.75 rows=11475
width=4) (actual time=0.007..4.075 rows=10000 loops=1)
 Planning Time: 0.086 ms
 Execution Time: 7264.141 ms
(9 rows)

When the index exists the transformation is certainly much better.

# create index on t2(a);
CREATE INDEX
# explain analyze select count(*) from t1 where not exists(select 1
from t2 where t1.a = t2.a or t2.a is null);
                                                              QUERY
PLAN
---------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=111342.50..111342.51 rows=1 width=8) (actual
time=29.580..29.581 rows=1 loops=1)
   ->  Nested Loop Anti Join  (cost=7.10..111342.50 rows=1 width=0)
(actual time=29.574..29.622 rows=0 loops=1)
         ->  Seq Scan on t1  (cost=0.00..145.00 rows=10000 width=4)
(actual time=0.010..0.883 rows=10000 loops=1)
         ->  Bitmap Heap Scan on t2  (cost=7.10..11.11 rows=1 width=4)
(actual time=0.002..0.002 rows=1 loops=10000)
               Recheck Cond: ((t1.a = a) OR (a IS NULL))
               Heap Blocks: exact=10000
               ->  BitmapOr  (cost=7.10..7.10 rows=1 width=0) (actual
time=0.002..0.002 rows=0 loops=10000)
                     ->  Bitmap Index Scan on t2_a_idx
(cost=0.00..0.30 rows=1 width=0) (actual time=0.001..0.001 rows=1
loops=10000)
                           Index Cond: (a = t1.a)
                     ->  Bitmap Index Scan on t2_a_idx
(cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0
loops=10000)
                           Index Cond: (a IS NULL)
 Planning Time: 0.311 ms
 Execution Time: 29.670 ms
(13 rows)

The big "IF" here is if we can calculate the size of the subplan to
know if it'll be hashed or not at the point in planning where this
conversion is done. I personally can't quite see how that'll work
reliably without actually planning the subquery, which I really doubt
is something we'd consider doing just for a cost estimate. Remember
the subquery may not just be a single relation scan, it could be a
complex query containing many joins and UNION / GROUP BY / DISTINCT /
HAVING clauses etc.

However, if there turns out to be some good way to do that that I
can't see then I think that each patch should be separate so that they
can be accepted or rejected on their own merits. The problem, for now,
is that the patches conflict with each other. I don't really want to
base mine on Jim and Zheng's patch, perhaps they feel the same about
basing theirs on mine.

--
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services


Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

zhengli
-----
   The big "IF" here is if we can calculate the size of the subplan to
    know if it'll be hashed or not at the point in planning where this
    conversion is done. I personally can't quite see how that'll work
    reliably without actually planning the subquery, which I really doubt
    is something we'd consider doing just for a cost estimate. Remember
    the subquery may not just be a single relation scan, it could be a
    complex query containing many joins and UNION / GROUP BY / DISTINCT /
    HAVING clauses etc.
-----

In our latest patch, we plan the subquery right before conversion, we only
proceed with the ANTI JOIN conversion if subplan_is_hashable(subplan) is
false. To avoid re-planning the subquery again in a later phase, I think we can
keep a pointer to the subplan in SubLink.

-----------
Zheng Li
AWS, Amazon Aurora PostgreSQL
 

On 6/14/19, 5:51 AM, "David Rowley" <[hidden email]> wrote:

    On Fri, 14 Jun 2019 at 20:41, Simon Riggs <[hidden email]> wrote:
    >
    > On Wed, 6 Mar 2019 at 04:11, David Rowley <[hidden email]> wrote:
    >>
    >> Hi Jim,
    >>
    >> Thanks for replying here.
    >>
    >> On Wed, 6 Mar 2019 at 16:37, Jim Finnerty <[hidden email]> wrote:
    >> >
    >> > Actually, we're working hard to integrate the two approaches.  I haven't had
    >> > time since I returned to review your patch, but I understand that you were
    >> > checking for strict predicates as part of the nullness checking criteria,
    >> > and we definitely must have that.  Zheng tells me that he has combined your
    >> > patch with ours, but before we put out a new patch, we're trying to figure
    >> > out how to preserve the existing NOT IN execution plan in the case where the
    >> > materialized subplan fits in memory.  This (good) plan is effectively an
    >> > in-memory hash anti-join.
    >> >
    >> > This is tricky to do because the NOT IN Subplan to anti-join transformation
    >> > currently happens early in the planning process, whereas the decision to
    >> > materialize is made much later, when the best path is being converted into a
    >> > Plan.
    >>
    >> I guess you're still going with the OR ... IS NULL in your patch then?
    >> otherwise, you'd likely find that the transformation (when NULLs are
    >> not possible) is always a win since it'll allow hash anti-joins. (see
    >> #2 in the original email on this thread)  FWIW I mentioned in [1] and
    >> Tom confirmed in [2] that we both think hacking the join condition to
    >> add an OR .. IS NULL is a bad idea. I guess you're not deterred by
    >> that?
    >
    >
    > Surely we want both?
    >
    > 1. Transform when we can
    > 2. Else apply some other approach if the cost can be reduced by doing it
   
    Maybe.  If the scope for the conversion is reduced to only add the OR
    .. IS NULL join clause when the subplan could not be hashed then it's
    maybe less likely to cause performance regressions. Remember that this
    forces the planner to use a nested loop join since no other join
    algorithms support OR clauses. I think Jim and Zheng have now changed
    their patch to do that.  If we can perform a parameterised nested loop
    join then that has a good chance of being better than scanning the
    subquery multiple times, however, if there's no index to do a
    parameterized nested loop, then we need to do a normal nested loop
    which will perform poorly, but so will the non-hashed subplan...
   
    # create table t1 (a int);
    CREATE TABLE
    # create table t2 (a int);
    CREATE TABLE
    # set work_mem = '64kB';
    SET
    # insert into t1 select generate_Series(1,10000);
    INSERT 0 10000
    # insert into t2 select generate_Series(1,10000);
    INSERT 0 10000
    # explain analyze select count(*) from t1 where a not in(select a from t2);
                                                            QUERY PLAN
    --------------------------------------------------------------------------------------------------------------------------
     Aggregate  (cost=1668739.50..1668739.51 rows=1 width=8) (actual
    time=7079.077..7079.077 rows=1 loops=1)
       ->  Seq Scan on t1  (cost=0.00..1668725.16 rows=5738 width=0)
    (actual time=7079.072..7079.072 rows=0 loops=1)
             Filter: (NOT (SubPlan 1))
             Rows Removed by Filter: 10000
             SubPlan 1
               ->  Materialize  (cost=0.00..262.12 rows=11475 width=4)
    (actual time=0.004..0.397 rows=5000 loops=10000)
                     ->  Seq Scan on t2  (cost=0.00..159.75 rows=11475
    width=4) (actual time=0.019..4.921 rows=10000 loops=1)
     Planning Time: 0.348 ms
     Execution Time: 7079.309 ms
    (9 rows)
   
    # explain analyze select count(*) from t1 where not exists(select 1
    from t2 where t1.a = t2.a or t2.a is null);
                                                           QUERY PLAN
    ------------------------------------------------------------------------------------------------------------------------
     Aggregate  (cost=1250873.25..1250873.26 rows=1 width=8) (actual
    time=7263.980..7263.980 rows=1 loops=1)
       ->  Nested Loop Anti Join  (cost=0.00..1250858.97 rows=5709
    width=0) (actual time=7263.976..7263.976 rows=0 loops=1)
             Join Filter: ((t1.a = t2.a) OR (t2.a IS NULL))
             Rows Removed by Join Filter: 49995000
             ->  Seq Scan on t1  (cost=0.00..159.75 rows=11475 width=4)
    (actual time=0.013..2.350 rows=10000 loops=1)
             ->  Materialize  (cost=0.00..262.12 rows=11475 width=4)
    (actual time=0.004..0.396 rows=5000 loops=10000)
                   ->  Seq Scan on t2  (cost=0.00..159.75 rows=11475
    width=4) (actual time=0.007..4.075 rows=10000 loops=1)
     Planning Time: 0.086 ms
     Execution Time: 7264.141 ms
    (9 rows)
   
    When the index exists the transformation is certainly much better.
   
    # create index on t2(a);
    CREATE INDEX
    # explain analyze select count(*) from t1 where not exists(select 1
    from t2 where t1.a = t2.a or t2.a is null);
                                                                  QUERY
    PLAN
    ---------------------------------------------------------------------------------------------------------------------------------------
     Aggregate  (cost=111342.50..111342.51 rows=1 width=8) (actual
    time=29.580..29.581 rows=1 loops=1)
       ->  Nested Loop Anti Join  (cost=7.10..111342.50 rows=1 width=0)
    (actual time=29.574..29.622 rows=0 loops=1)
             ->  Seq Scan on t1  (cost=0.00..145.00 rows=10000 width=4)
    (actual time=0.010..0.883 rows=10000 loops=1)
             ->  Bitmap Heap Scan on t2  (cost=7.10..11.11 rows=1 width=4)
    (actual time=0.002..0.002 rows=1 loops=10000)
                   Recheck Cond: ((t1.a = a) OR (a IS NULL))
                   Heap Blocks: exact=10000
                   ->  BitmapOr  (cost=7.10..7.10 rows=1 width=0) (actual
    time=0.002..0.002 rows=0 loops=10000)
                         ->  Bitmap Index Scan on t2_a_idx
    (cost=0.00..0.30 rows=1 width=0) (actual time=0.001..0.001 rows=1
    loops=10000)
                               Index Cond: (a = t1.a)
                         ->  Bitmap Index Scan on t2_a_idx
    (cost=0.00..4.29 rows=1 width=0) (actual time=0.001..0.001 rows=0
    loops=10000)
                               Index Cond: (a IS NULL)
     Planning Time: 0.311 ms
     Execution Time: 29.670 ms
    (13 rows)
   
    The big "IF" here is if we can calculate the size of the subplan to
    know if it'll be hashed or not at the point in planning where this
    conversion is done. I personally can't quite see how that'll work
    reliably without actually planning the subquery, which I really doubt
    is something we'd consider doing just for a cost estimate. Remember
    the subquery may not just be a single relation scan, it could be a
    complex query containing many joins and UNION / GROUP BY / DISTINCT /
    HAVING clauses etc.
   
    However, if there turns out to be some good way to do that that I
    can't see then I think that each patch should be separate so that they
    can be accepted or rejected on their own merits. The problem, for now,
    is that the patches conflict with each other. I don't really want to
    base mine on Jim and Zheng's patch, perhaps they feel the same about
    basing theirs on mine.
   
    --
     David Rowley                   http://www.2ndQuadrant.com/
     PostgreSQL Development, 24x7 Support, Training & Services
   
   
   

Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

David Rowley-3
In reply to this post by Antonin Houska-2
On Mon, 27 May 2019 at 20:43, Antonin Houska <[hidden email]> wrote:
> I've spent some time looking into this.

Thank you for having a look at this.

> One problem I see is that SubLink can be in the JOIN/ON clause and thus it's
> not necessarily at the top of the join tree. Consider this example:
>
> CREATE TABLE a(i int);
> CREATE TABLE b(j int);
> CREATE TABLE c(k int NOT NULL);
> CREATE TABLE d(l int);
>
>   SELECT *
>     FROM
>         a
>         JOIN b ON b.j NOT IN
>                 ( SELECT
>                         c.k
>                     FROM
>                         c)
>         JOIN d ON b.j = d.l;
hmm yeah. Since the proofs that are being used in
expressions_are_not_nullable assume the join has already taken place,
then we'll either need to not use the join conditions are proofs in
that case, or just disable the optimisation instead.   I think it's
fine to just disable the optimisation since it seem rather unlikely
that someone would write a join condition like that.  Plus it seems
quite a bit more complex to validate that the optimisation would even
be correct if NULLs were not possible.

I've attached a patch which restricts the pullups to FromExpr quals.
Anything below a JoinExpr disables the optimisation now.

--
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

not_in_anti_join_v2.patch (77K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Converting NOT IN to anti-joins during planning

Antonin Houska-2
David Rowley <[hidden email]> wrote:

> On Mon, 27 May 2019 at 20:43, Antonin Houska <[hidden email]> wrote:
> > I've spent some time looking into this.
>
> Thank you for having a look at this.
>
> > One problem I see is that SubLink can be in the JOIN/ON clause and thus it's
> > not necessarily at the top of the join tree. Consider this example:
> >
> > CREATE TABLE a(i int);
> > CREATE TABLE b(j int);
> > CREATE TABLE c(k int NOT NULL);
> > CREATE TABLE d(l int);
> >
> >   SELECT *
> >     FROM
> >         a
> >         JOIN b ON b.j NOT IN
> >                 ( SELECT
> >                         c.k
> >                     FROM
> >                         c)
> >         JOIN d ON b.j = d.l;
>
> hmm yeah. Since the proofs that are being used in
> expressions_are_not_nullable assume the join has already taken place,
> then we'll either need to not use the join conditions are proofs in
> that case, or just disable the optimisation instead.   I think it's
> fine to just disable the optimisation since it seem rather unlikely
> that someone would write a join condition like that.  Plus it seems
> quite a bit more complex to validate that the optimisation would even
> be correct if NULLs were not possible.
>
> I've attached a patch which restricts the pullups to FromExpr quals.
> Anything below a JoinExpr disables the optimisation now.

ok. The planner pulls-up other sublinks located in the ON clause, but it'd be
quite tricky to do the same for the NOT IN case.

Now that we only consider the WHERE clause, I wonder if the code can be
simplified a bit more. In particular, pull_up_sublinks_jointree_recurse()
passes valid pointer for notnull_proofs to pull_up_sublinks_qual_recurse(),
while it also passes under_joinexpr=true. The latter should imply that NOT IN
won't be converted to ANTI JOIN anyway, so no notnull_proofs should be needed.

BTW, I'm not sure if notnull_proofs=j->quals is correct in cases like this:

        case JOIN_LEFT:
                j->quals = pull_up_sublinks_qual_recurse(root, j->quals,
                         &j->rarg,
                         rightrelids,
                         NULL, NULL, j->quals,
                         true);

Even if j->quals evaluates to NULL or FALSE (due to NULL value on its input),
it does not remove any rows (possibly containing NULL values) from the input
of the SubLink's expression.

I'm not even sure that expressions_are_not_nullable() needs the notnull_proofs
argument. Now that we only consider SubLinks in the WHERE clause, it seems to
me that nonnullable_vars is always a subset of nonnullable_inner_vars, isn't
it?

A few more minor findings:

@@ -225,10 +227,13 @@ pull_up_sublinks(PlannerInfo *root)
  *
  * In addition to returning the possibly-modified jointree node, we return
  * a relids set of the contained rels into *relids.
+ *
+ * under_joinexpr must be passed as true if 'jtnode' is or is under a
+ * JoinExpr.
  */
 static Node *
 pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
-                                                                 Relids *relids)
+                                                                 Relids *relids, bool under_joinexpr)
 {
        if (jtnode == NULL)
        {


The comment "if 'jtnode' is or is under ..." is unclear.


* is_NOTANY_compatible_with_antijoin()

  **  "'outerquery' is the parse of the query" -> "'outerquery' is the parse tree of the query"

  ** "2.  We assume that each join qual is an OpExpr" -> "2.  We assume that
     each sublink expression is an OpExpr" ?

  ** (OpExpr *) lfirst(lc) -> lfirst_node(OpExpr, lc)

  ** The kind of bool expression (AND_EXPR) might need to be tested here too:

+       /* Extract exprs from multiple expressions ANDed together */
+       else if (IsA(testexpr, BoolExpr))


* find_innerjoined_rels()

 "we locate all WHERE and JOIN/ON quals that constrain these rels add them to"
 ->
 " ... and add them ..."


* get_attnotnull()

  The comment says that FALSE is returned if the attribute is dropped, however
  the function it does not test att_tup->attisdropped. (This patch should not
  call the function for a dropped attribute, so I'm only saying that the
  function code is not consistent with the comment.)

--
Antonin Houska
Web: https://www.cybertec-postgresql.com