Thread

Commits

Check we don't misoptimize a NOT IN where the subquery returns no rows.
- 3396138a6de3 12.0 landed

NOT IN subquery optimization

Finnerty, Jim <jfinnert@amazon.com> — 2019-02-20T23:44:49Z

The semantics of NOT IN (SELECT ...) are subtly different from the semantics
of NOT EXISTS (SELECT ...).  These differences center on how NULLs are
treated, and in general can result in statements that are harder to optimize
and slower to execute than the apparently similar NOT EXISTS statement.

A little over a year ago, Christian Antognini authored the blog "/How Well a
Query Optimizer Handles Subqueries?/" summarizing his findings about the
performance of PostgreSQL, MySQL, and Oracle on various subqueries:

   
https://antognini.ch/2017/12/how-well-a-query-optimizer-handles-subqueries/

His position was that you can classify the optimizations as correct or
incorrect, and based on that he provided the following comparison summary
(see below).  In short, PostgreSQL was the worst of the three systems:

    "Summary

        The number of queries that the query optimizers handle correctly are
the following:

        Oracle Database 12.2: 72 out of 80
        MySQL 8.0.3: 67 out of 80
        PostgreSQL 10.0: 60 out of 80

    Since not all queries are handled correctly, for best performance it is
sometimes necessary to rewrite them."

The subqueries that were found to be optimized "incorrectly" were almost
entirely due to poor or absent NOT IN subquery optimization.

The PostgreSQL community has been aware of the deficiencies in NOT IN
optimization for quite some time.  Based on an analysis of
psgsql-performance posts between 2013 and 2015, Robert Haas identified NOT
IN optimization as one of the common root causes of performance problems.

We have been working on improved optimization of NOT IN, and we would like
to share this optimizaton with the community.  With respect to the test
cases mentioned in the blog post mentioned above, it will elevate PostgreSQL
from "worst" to "first".  Generally the performance gains are large when the
optimization applies, though we have found one test case where performance
is worse.  We are investigating this now to see if we can disable the
optimization in that case.

We would like to include a patch for this change in the current commitfest. 
This thread can be used to track comments about this optimization.




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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-02-21T00:40:44Z

Jim Finnerty <jfinnert@amazon.com> writes:
> We have been working on improved optimization of NOT IN, and we would like
> to share this optimizaton with the community.

The idea that's been kicked around in the past is to detect whether the
subselect's output column(s) can be proved NOT NULL, and if so, convert
to an antijoin just like NOT EXISTS.  Is that what you're doing, or
something different?

> We would like to include a patch for this change in the current commitfest. 

Generally, people just send patches, they don't ask for permission first
;-)

Having said that, we have a general policy that we don't like complex
patches that first show up for the last commitfest of a dev cycle.
So unless this is a pretty small patch, it's probably going to get
delayed to v13.  Still, we'd like to have it in the queue, so submit
away ...

			regards, tom lane

Re: NOT IN subquery optimization

Finnerty, Jim <jfinnert@amazon.com> — 2019-02-21T01:53:25Z

re: The idea that's been kicked around in the past is to detect whether the
subselect's output column(s) can be proved NOT NULL, and if so, convert
to an antijoin just like NOT EXISTS

basically, yes.  this will handle nullability of both the outer and inner
correlated expression(s), multiple expressions, presence or absence of
predicates in the WHERE clause, and whether the correlated expressions are
on the null-padded side of an outer join.  If it is judged to be more
efficient, then it transforms the NOT IN sublink into an anti-join.

some complications enter into the decision to transform NOT IN to anti-join
based on whether a bitmap plan will/not be used, or whether it will/not be
eligible for PQ.



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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-02-21T02:11:06Z

Jim Finnerty <jfinnert@amazon.com> writes:
> re: The idea that's been kicked around in the past is to detect whether the
> subselect's output column(s) can be proved NOT NULL, and if so, convert
> to an antijoin just like NOT EXISTS

> basically, yes.  this will handle nullability of both the outer and inner
> correlated expression(s), multiple expressions, presence or absence of
> predicates in the WHERE clause, and whether the correlated expressions are
> on the null-padded side of an outer join.  If it is judged to be more
> efficient, then it transforms the NOT IN sublink into an anti-join.

Hmm, that seems overcomplicated ...

> some complications enter into the decision to transform NOT IN to anti-join
> based on whether a bitmap plan will/not be used, or whether it will/not be
> eligible for PQ.

... and that even more so, considering that this decision really needs
to be taken long before cost estimates would be available.

As far as I can see, there should be no situation where we'd not want
to transform to antijoin if we can prove it's semantically valid to
do so.  If there are cases where that comes out as a worse plan,
that indicates a costing error that would be something to address
separately (because it'd also be a problem for other antijoin cases).
Also, as long as it nearly always wins, I'm not going to cry too hard
if there are corner cases where it makes the wrong choice.  That's not
something that's possible to avoid completely.

			regards, tom lane

Re: NOT IN subquery optimization

Finnerty, Jim <jfinnert@amazon.com> — 2019-02-21T03:27:47Z

We can always correctly transform a NOT IN to a correlated NOT EXISTS.  In
almost all cases it is more efficient to do so.  In the one case that we've
found that is slower it does come down to a more general costing issue, so
that's probably the right way to think about it.



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

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-02-21T20:44:14Z

On Thu, 21 Feb 2019 at 16:27, Jim Finnerty <jfinnert@amazon.com> wrote:
> We can always correctly transform a NOT IN to a correlated NOT EXISTS.  In
> almost all cases it is more efficient to do so.  In the one case that we've
> found that is slower it does come down to a more general costing issue, so
> that's probably the right way to think about it.

I worked on this over 4 years ago [1]. I think the patch there is not
completely broken and seems just to need a few things fixed. I rebased
it on top of current master and looked at it. I think the main
remaining issue is fixing the code that ensures the outer side join
quals can't be NULL.  The code that's there looks broken still since
it attempts to use quals from any inner joined rel for proofs that
NULLs will be removed.  That might not work so well in a case like:
SELECT * FROM t1 LEFT JOIN t2 ON t1.a = t2.a AND t2.b NOT IN(select b
from t3),  however, I'd need to think harder about that since if there
was such a qual then the planner should convert the left join into an
inner join. But anyway, the function expressions_are_not_nullable()
was more intended to work with targetlists to ensure exprs there can't
be NULL. I just had done a poor job of trying to modify that into
allowing it to take exprs from any random place, likely that should be
a new function and expressions_are_not_nullable() should be put back
to what Tom ended up with.

I've attached the rebased and still broken version.

[1] https://www.postgresql.org/message-id/CAApHDvqRB-iFBy68%3DdCgqS46aRep7AuN2pou4KTwL8kX9YOcTQ%40mail.gmail.com

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

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-02-25T12:31:53Z

On Fri, 22 Feb 2019 at 09:44, David Rowley <david.rowley@2ndquadrant.com> wrote:
> I've attached the rebased and still broken version.

I set about trying to make a less broken version of this.

A quick reminder of the semantics of NOT IN:

1. WHERE <nullable_column> NOT IN(SELECT <not null column> FROM table);

If table is non-empty:
will filter out rows where <nullable_column> is NULL
and only show values that are not in <not null column>

If table is empty:
Filters nothing.

2. WHERE <nonnullable_column> NOT IN(SELECT <null column> FROM table);

If table contains NULLs in the <null column> no records will match.

The previous patch handled #2 correctly but neglected to do anything
about #1.  For #1 the only way we can implement this as a planner only
change is to insist that the outer side expressions also are not null.
If we could have somehow tested if "table" was non-empty then we could
have added a IS NOT NULL clause to the outer query and converted to an
anti-join, but ... can't know that during planning and can't add the
IS NOT NULL regardless as, if "table" is empty we will filter NULLs
when we shouldn't.

In the attached, I set about fixing #1 by determining if the outer
expressions could be NULL by checking

1. If expression is a Var from an inner joined relation it can't be
NULL if there's a NOT NULL constraint on the column; or
2. If expression is a Var from an inner joined relation and there is a
strict WHERE/ON clause, the expression can't be NULL; or
3. If expression is a Var from an outer joined relation check for
quals that were specified in the same syntactical level as the NOT IN
for proofs that NULL will be filtered.

An example of #3 is:

SELECT * FROM t1 LEFT JOIN t2 on t1.a = t2.a WHERE t2.a IS NOT NULL
AND t2.a NOT IN(SELECT a FROM t3); -- t2 becomes INNER JOINed later in
planning, but...
or;
SELECT * FROM t1 LEFT JOIN t2 on t1.a = t2.a AND t2.a NOT IN(SELECT a FROM t3);

In the latter of the two, the t1.a = t2.a join conditions ensures that
NULLs can't exist where the NOT IN is evaluated.

I implemented #3 by passing the quals down to
pull_up_sublinks_qual_recurse().  At the top level call 'node' and
'notnull_proofs' are the same, but that changes in recursive calls
like the one we make inside the is_andclause() condition.

Comments welcome.

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

Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-02-25T17:38:22Z

I'm attaching a working patch following the discussion.

You can also find the following patch description is the commit message:
NOT IN to ANTI JOIN transformation

    The semantics of ANTI JOIN were created to match the semantics of NOT
    EXISTS, which enables NOT EXISTS subqueries to be efficiently executed
    as a kind of join.  NOT IN subqueries have different NULL semantics than
    NOT EXISTS, but since there is no special join operator for NOT IN it is
    generally executed as a nested sub-plan.  It is possible, however, to
    transform NOT IN to a correlated NOT EXISTS so that it can be executed
    it as an ANTI JOIN with additional correlated predicates.

    A general transformation from NOT IN to NOT EXISTS for the
    single-expression case (the multi-expression case is just ANDs of the
    single-expressions) is:
        t1.x NOT IN (SELECT t2.y from t2 where p) <=> NOT EXISTS (select 1
                from t2 where (y=x or y is NULL or x is NULL) and p).

    If x or y is non-nullable, we can safely remove the predicate "x
    is NULL" or "y is NULL", and if there is no predicate p,
    then "x is NULL" may be factored out of the subquery.
    Experiments show that if we can remove one or the other ORed
    predicates, or if we can factor out the "x is NULL", then
    execution is typically much faster.

    Basically, for the single expression case (we also handle the multi
    expression case), we try to do the following transformation:
    When p does not exist:
        t1.x not in (t2.y) => ANTI JOIN t1(Filter: x is not null), t2 on
        join condition: t1.x=t2.y or t2.y is null.
    When x is non-nullable:
        t1.x not in (t2.y where p) => ANTI JOIN t1, t2 on join condition:
        (t1.x=t2.y or t2.y is null) and p.

    We implemented a nullability test routine is_node_nonnullable().
    Currently it handles Var, TargetEntry, CoalesceExpr and Const. Outer
    joins are taken into consideration in the nullability test.

    We adjust and apply reduce_outer_joins() before the transformation so 
    that the outer joins have an opportunity to be converted to inner joins
    prior to the transformation.

    Using this transformation, we measured performance improvements of
    two to three orders of magnitude on most queries in a development
    environment. In our performance experiments, table s (small) has 11
    rows, table l (large) has 1 million rows. s.n and l.n have NULL
    values. s.nn and l.nn are NOT NULL.

        s.n not in (l.n)          1150 ms -> 0.49 ms
        s.nn not in (l.nn)      1120 ms -> 0.45 ms
        l.n not in (l.n)   over   20 min -> 1700 ms
        l.nn not in (l.nn) over 20 min -> 220 ms
        l.n not in (s.n)               63 ms -> 750 ms
        l.nn not in (s.nn)          58 ms -> 46 ms

    For the only case that performance drops - l.n not in (s.n). It is
    likely to be resolved by ending the nested loop anti join early as
    soon as we find NULL inner tuple entry/entries that satisfies the
    join condition during execution. This is still under investigation.

Comments are welcome.

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

On 2/25/19, 7:32 AM, "David Rowley" <david.rowley@2ndquadrant.com> wrote:

    On Fri, 22 Feb 2019 at 09:44, David Rowley <david.rowley@2ndquadrant.com> wrote:
    > I've attached the rebased and still broken version.
    
    I set about trying to make a less broken version of this.
    
    A quick reminder of the semantics of NOT IN:
    
    1. WHERE <nullable_column> NOT IN(SELECT <not null column> FROM table);
    
    If table is non-empty:
    will filter out rows where <nullable_column> is NULL
    and only show values that are not in <not null column>
    
    If table is empty:
    Filters nothing.
    
    2. WHERE <nonnullable_column> NOT IN(SELECT <null column> FROM table);
    
    If table contains NULLs in the <null column> no records will match.
    
    The previous patch handled #2 correctly but neglected to do anything
    about #1.  For #1 the only way we can implement this as a planner only
    change is to insist that the outer side expressions also are not null.
    If we could have somehow tested if "table" was non-empty then we could
    have added a IS NOT NULL clause to the outer query and converted to an
    anti-join, but ... can't know that during planning and can't add the
    IS NOT NULL regardless as, if "table" is empty we will filter NULLs
    when we shouldn't.
    
    In the attached, I set about fixing #1 by determining if the outer
    expressions could be NULL by checking
    
    1. If expression is a Var from an inner joined relation it can't be
    NULL if there's a NOT NULL constraint on the column; or
    2. If expression is a Var from an inner joined relation and there is a
    strict WHERE/ON clause, the expression can't be NULL; or
    3. If expression is a Var from an outer joined relation check for
    quals that were specified in the same syntactical level as the NOT IN
    for proofs that NULL will be filtered.
    
    An example of #3 is:
    
    SELECT * FROM t1 LEFT JOIN t2 on t1.a = t2.a WHERE t2.a IS NOT NULL
    AND t2.a NOT IN(SELECT a FROM t3); -- t2 becomes INNER JOINed later in
    planning, but...
    or;
    SELECT * FROM t1 LEFT JOIN t2 on t1.a = t2.a AND t2.a NOT IN(SELECT a FROM t3);
    
    In the latter of the two, the t1.a = t2.a join conditions ensures that
    NULLs can't exist where the NOT IN is evaluated.
    
    I implemented #3 by passing the quals down to
    pull_up_sublinks_qual_recurse().  At the top level call 'node' and
    'notnull_proofs' are the same, but that changes in recursive calls
    like the one we make inside the is_andclause() condition.
    
    Comments welcome.
    
    -- 
     David Rowley                   http://www.2ndQuadrant.com/
     PostgreSQL Development, 24x7 Support, Training & Services

Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-02-25T22:51:30Z

Resend the patch with a whitespace removed so that "git apply patch" works directly.

---
Zheng Li, AWS, Amazon Aurora PostgreSQL

On 2/25/19, 12:39 PM, "Li, Zheng" <zhelli@amazon.com> wrote:

    I'm attaching a working patch following the discussion.
    
    You can also find the following patch description is the commit message:
    NOT IN to ANTI JOIN transformation
    
        The semantics of ANTI JOIN were created to match the semantics of NOT
        EXISTS, which enables NOT EXISTS subqueries to be efficiently executed
        as a kind of join.  NOT IN subqueries have different NULL semantics than
        NOT EXISTS, but since there is no special join operator for NOT IN it is
        generally executed as a nested sub-plan.  It is possible, however, to
        transform NOT IN to a correlated NOT EXISTS so that it can be executed
        it as an ANTI JOIN with additional correlated predicates.
    
        A general transformation from NOT IN to NOT EXISTS for the
        single-expression case (the multi-expression case is just ANDs of the
        single-expressions) is:
            t1.x NOT IN (SELECT t2.y from t2 where p) <=> NOT EXISTS (select 1
                    from t2 where (y=x or y is NULL or x is NULL) and p).
    
        If x or y is non-nullable, we can safely remove the predicate "x
        is NULL" or "y is NULL", and if there is no predicate p,
        then "x is NULL" may be factored out of the subquery.
        Experiments show that if we can remove one or the other ORed
        predicates, or if we can factor out the "x is NULL", then
        execution is typically much faster.
    
        Basically, for the single expression case (we also handle the multi
        expression case), we try to do the following transformation:
        When p does not exist:
            t1.x not in (t2.y) => ANTI JOIN t1(Filter: x is not null), t2 on
            join condition: t1.x=t2.y or t2.y is null.
        When x is non-nullable:
            t1.x not in (t2.y where p) => ANTI JOIN t1, t2 on join condition:
            (t1.x=t2.y or t2.y is null) and p.
    
        We implemented a nullability test routine is_node_nonnullable().
        Currently it handles Var, TargetEntry, CoalesceExpr and Const. Outer
        joins are taken into consideration in the nullability test.
    
        We adjust and apply reduce_outer_joins() before the transformation so 
        that the outer joins have an opportunity to be converted to inner joins
        prior to the transformation.
    
        Using this transformation, we measured performance improvements of
        two to three orders of magnitude on most queries in a development
        environment. In our performance experiments, table s (small) has 11
        rows, table l (large) has 1 million rows. s.n and l.n have NULL
        values. s.nn and l.nn are NOT NULL.
    
            s.n not in (l.n)          1150 ms -> 0.49 ms
            s.nn not in (l.nn)      1120 ms -> 0.45 ms
            l.n not in (l.n)   over   20 min -> 1700 ms
            l.nn not in (l.nn) over 20 min -> 220 ms
            l.n not in (s.n)               63 ms -> 750 ms
            l.nn not in (s.nn)          58 ms -> 46 ms
    
        For the only case that performance drops - l.n not in (s.n). It is
        likely to be resolved by ending the nested loop anti join early as
        soon as we find NULL inner tuple entry/entries that satisfies the
        join condition during execution. This is still under investigation.
    
    Comments are welcome.
    
    With Regards,
    ---
    Zheng Li, AWS, Amazon Aurora PostgreSQL
    
    On 2/25/19, 7:32 AM, "David Rowley" <david.rowley@2ndquadrant.com> wrote:
    
        On Fri, 22 Feb 2019 at 09:44, David Rowley <david.rowley@2ndquadrant.com> wrote:
        > I've attached the rebased and still broken version.
        
        I set about trying to make a less broken version of this.
        
        A quick reminder of the semantics of NOT IN:
        
        1. WHERE <nullable_column> NOT IN(SELECT <not null column> FROM table);
        
        If table is non-empty:
        will filter out rows where <nullable_column> is NULL
        and only show values that are not in <not null column>
        
        If table is empty:
        Filters nothing.
        
        2. WHERE <nonnullable_column> NOT IN(SELECT <null column> FROM table);
        
        If table contains NULLs in the <null column> no records will match.
        
        The previous patch handled #2 correctly but neglected to do anything
        about #1.  For #1 the only way we can implement this as a planner only
        change is to insist that the outer side expressions also are not null.
        If we could have somehow tested if "table" was non-empty then we could
        have added a IS NOT NULL clause to the outer query and converted to an
        anti-join, but ... can't know that during planning and can't add the
        IS NOT NULL regardless as, if "table" is empty we will filter NULLs
        when we shouldn't.
        
        In the attached, I set about fixing #1 by determining if the outer
        expressions could be NULL by checking
        
        1. If expression is a Var from an inner joined relation it can't be
        NULL if there's a NOT NULL constraint on the column; or
        2. If expression is a Var from an inner joined relation and there is a
        strict WHERE/ON clause, the expression can't be NULL; or
        3. If expression is a Var from an outer joined relation check for
        quals that were specified in the same syntactical level as the NOT IN
        for proofs that NULL will be filtered.
        
        An example of #3 is:
        
        SELECT * FROM t1 LEFT JOIN t2 on t1.a = t2.a WHERE t2.a IS NOT NULL
        AND t2.a NOT IN(SELECT a FROM t3); -- t2 becomes INNER JOINed later in
        planning, but...
        or;
        SELECT * FROM t1 LEFT JOIN t2 on t1.a = t2.a AND t2.a NOT IN(SELECT a FROM t3);
        
        In the latter of the two, the t1.a = t2.a join conditions ensures that
        NULLs can't exist where the NOT IN is evaluated.
        
        I implemented #3 by passing the quals down to
        pull_up_sublinks_qual_recurse().  At the top level call 'node' and
        'notnull_proofs' are the same, but that changes in recursive calls
        like the one we make inside the is_andclause() condition.
        
        Comments welcome.
        
        -- 
         David Rowley                   http://www.2ndQuadrant.com/
         PostgreSQL Development, 24x7 Support, Training & Services

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-02-25T23:19:57Z

On Tue, 26 Feb 2019 at 11:51, Li, Zheng <zhelli@amazon.com> wrote:
> Resend the patch with a whitespace removed so that "git apply patch" works directly.

I had a quick look at this and it seems to be broken for the empty
table case I mentioned up thread.

Quick example:

Setup:

create table t1 (a int);
create table t2 (a int not null);
insert into t1 values(NULL),(1),(2);

select * from t1 where a not in(select a from t2);

Patched:
 a
---
 1
 2
(2 rows)

Master:
 a
---

 1
 2
(3 rows)

This will be due to the fact you're adding an a IS NOT NULL qual to
the scan of a:

postgres=# explain select * from t1 where a not in(select a from t2);
                            QUERY PLAN
------------------------------------------------------------------
 Hash Anti Join  (cost=67.38..152.18 rows=1268 width=4)
   Hash Cond: (t1.a = t2.a)
   ->  Seq Scan on t1  (cost=0.00..35.50 rows=2537 width=4)
         Filter: (a IS NOT NULL)
   ->  Hash  (cost=35.50..35.50 rows=2550 width=4)
         ->  Seq Scan on t2  (cost=0.00..35.50 rows=2550 width=4)
(6 rows)

but as I mentioned, you can't do that as t2 might be empty and there's
no way to know that during planning.

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

Re: NOT IN subquery optimization

Richard Guo <riguo@pivotal.io> — 2019-02-26T10:24:36Z

Greenplum Database does this optimization. The idea is to use a new join
type, let's call it JOIN_LASJ_NOTIN, and its semantic regarding NULL is
defined as below:

1. If there is a NULL in the outer side, and the inner side is empty, the
   NULL should be part of the outputs.

2. If there is a NULL in the outer side, and the inner side is not empty,
   the NULL should not be part of the outputs.

3. If there is a NULL in the inner side, no outputs should be produced.

An example plan looks like:

gpadmin=# explain (costs off)  select * from t1 where a not in(select a
from t2);
            QUERY PLAN
-----------------------------------
 Hash Left Anti Semi (Not-In) Join
   Hash Cond: (t1.a = t2.a)
   ->  Seq Scan on t1
   ->  Hash
         ->  Seq Scan on t2
(5 rows)

Thanks
Richard

On Tue, Feb 26, 2019 at 7:20 AM David Rowley <david.rowley@2ndquadrant.com>
wrote:

> On Tue, 26 Feb 2019 at 11:51, Li, Zheng <zhelli@amazon.com> wrote:
> > Resend the patch with a whitespace removed so that "git apply patch"
> works directly.
>
> I had a quick look at this and it seems to be broken for the empty
> table case I mentioned up thread.
>
> Quick example:
>
> Setup:
>
> create table t1 (a int);
> create table t2 (a int not null);
> insert into t1 values(NULL),(1),(2);
>
> select * from t1 where a not in(select a from t2);
>
> Patched:
>  a
> ---
>  1
>  2
> (2 rows)
>
> Master:
>  a
> ---
>
>  1
>  2
> (3 rows)
>
> This will be due to the fact you're adding an a IS NOT NULL qual to
> the scan of a:
>
> postgres=# explain select * from t1 where a not in(select a from t2);
>                             QUERY PLAN
> ------------------------------------------------------------------
>  Hash Anti Join  (cost=67.38..152.18 rows=1268 width=4)
>    Hash Cond: (t1.a = t2.a)
>    ->  Seq Scan on t1  (cost=0.00..35.50 rows=2537 width=4)
>          Filter: (a IS NOT NULL)
>    ->  Hash  (cost=35.50..35.50 rows=2550 width=4)
>          ->  Seq Scan on t2  (cost=0.00..35.50 rows=2550 width=4)
> (6 rows)
>
> but as I mentioned, you can't do that as t2 might be empty and there's
> no way to know that during planning.
>
> --
>  David Rowley
> https://urldefense.proofpoint.com/v2/url?u=http-3A__www.2ndQuadrant.com_&d=DwIBaQ&c=lnl9vOaLMzsy2niBC8-h_K-7QJuNJEsFrzdndhuJ3Sw&r=5r3cnfZPUDOHrMiXq8Mq2g&m=dE1nglE17x3nD-oH_BrF0r4SLaFnQKzwwJBJGpDoaaA&s=dshupMomMvkDAd92918cU21AJ1E1s7QwbrxIGSRxZA8&e=
>  PostgreSQL Development, 24x7 Support, Training & Services
>
>

Re: NOT IN subquery optimization

Finnerty, Jim <jfinnert@amazon.com> — 2019-02-26T14:07:42Z

The problem is that the special optimization that was proposed for the case
where the subquery has no WHERE clause isn't valid when the subquery returns
no rows.  That additional optimization needs to be removed, and preferably
replaced with some sort of efficient run-time test.





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

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-02-26T20:51:41Z

On Wed, 27 Feb 2019 at 03:07, Jim Finnerty <jfinnert@amazon.com> wrote:
>
> The problem is that the special optimization that was proposed for the case
> where the subquery has no WHERE clause isn't valid when the subquery returns
> no rows.  That additional optimization needs to be removed, and preferably
> replaced with some sort of efficient run-time test.

That is one option, however, the join type that Richard mentions, to
satisfy point #3, surely only can work for Hash joins and perhaps
Merge joins that required a sort, assuming there's some way for the
sort to communicate about if it found NULLs or not. Either way, we
need to have looked at the entire inner side to ensure there are no
nulls. Probably it would be possible to somehow team that up with a
planner check to see if the inner exprs could be NULL then just
implement points #1 and #2 for other join methods.

If you're proposing to do that for this thread then I can take my
planner only patch somewhere else.  I only posted my patch as I pretty
much already had what I thought you were originally talking about.
However, please be aware there are current patents around adding
execution time smarts in this area, so it's probably unlikely you'll
find a way to do this in the executor that does not infringe on those.
Probably no committer would want to touch it.  I think my patch covers
a good number of use cases and as far as I understand, does not go
near any current patents.

Please let me know if I should move my patch to another thread. I
don't want to hi-jack this if you're going in another direction.

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

Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-02-27T00:05:41Z

I agree we will need some runtime smarts (such as a new anti join type as pointed out by Richard) to "ultimately" account for all the cases of NOT IN queries.

However, given that the March CommitFest is imminent and the runtime smarts patent concerns David had pointed out (which I was not aware of before), we would not move that direction at the moment.

I propose that we collaborate to build one patch from the two patches submitted in this thread for the CF. The two patches are for the same purpose and similar. However, they differ in the following ways as far as I can tell:

Nullability Test:
-David's patch uses strict predicates for nullability test.
-Our patch doesn't use strict predicates, but it accounts for COALESCE and null-padded rows from outer join. In addition, we made reduce_outer_joins() work before the transformation which makes the nullability test more accurate.

Anti Join Transformation:
-Dvaid's patch does the transformation when both inner and outer outputs are non-nullable.
-With the latest fix (for the empty table case), our patch does the transformation as long as the outer is non-nullable regardless of the inner nullability, experiments show that the results are always faster.

David, please let me know what you think. If you would like to collaborate, I'll start merging with your code on using strict predicates to make a better Nullability Test.

Thanks,
Zheng

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-02-27T00:13:54Z

"Li, Zheng" <zhelli@amazon.com> writes:
> However, given that the March CommitFest is imminent and the runtime smarts patent concerns David had pointed out (which I was not aware of before), we would not move that direction at the moment.

> I propose that we collaborate to build one patch from the two patches submitted in this thread for the CF.

TBH, I think it's very unlikely that any patch for this will be seriously
considered for commit in v12.  It would be against project policy, and
spending a lot of time reviewing the patch would be quite unfair to other
patches that have been in the queue longer.  Therefore, I'd suggest that
you not bend things out of shape just to have some patch to submit before
March 1.  It'd be better to work with the goal of having a coherent patch
ready for the first v13 CF, probably July-ish.

			regards, tom lane

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-02-27T00:24:26Z

On Wed, 27 Feb 2019 at 13:05, Li, Zheng <zhelli@amazon.com> wrote:
> -With the latest fix (for the empty table case), our patch does the transformation as long as the outer is non-nullable regardless of the inner nullability, experiments show that the results are always faster.

Hi Zheng,

I'm interested to know how this works without testing for inner
nullability.  If any of the inner side's join exprs are NULL then no
records can match. What do you propose to work around that?

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

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-02-27T00:26:26Z

On Wed, 27 Feb 2019 at 13:13, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> "Li, Zheng" <zhelli@amazon.com> writes:
> > However, given that the March CommitFest is imminent and the runtime smarts patent concerns David had pointed out (which I was not aware of before), we would not move that direction at the moment.
>
> > I propose that we collaborate to build one patch from the two patches submitted in this thread for the CF.
>
> TBH, I think it's very unlikely that any patch for this will be seriously
> considered for commit in v12.  It would be against project policy, and
> spending a lot of time reviewing the patch would be quite unfair to other
> patches that have been in the queue longer.  Therefore, I'd suggest that
> you not bend things out of shape just to have some patch to submit before
> March 1.  It'd be better to work with the goal of having a coherent patch
> ready for the first v13 CF, probably July-ish.

FWIW, I did add this to the March CF, but I set the target version to
13.  I wasn't considering this for PG12. I see Zheng was, but I agree
with you on PG13 being the target for this.

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

Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-02-27T00:41:12Z

I'm totally fine with setting the target to PG13.

--
I'm interested to know how this works without testing for inner
nullability.  If any of the inner side's join exprs are NULL then no
records can match. What do you propose to work around that?
--

We still check for inner side's nullability, when it is nullable we
append a "var is NULL" to the anti join condition. So every outer
tuple is going to evaluate to true on the join condition when there
is indeed a null entry in the inner. 
Actually I think the nested loop anti join can end early in this case,
but I haven't find a way to do it properly, this may be one other reason
why we need a new join type for NOT IN.

e.g.
explain select count(*) from s where u not in (select n from l);
                                     QUERY PLAN
------------------------------------------------------------------------------------
 Aggregate  (cost=2892.88..2892.89 rows=1 width=8)
   ->  Nested Loop Anti Join  (cost=258.87..2892.88 rows=1 width=0)
         ->  Seq Scan on s  (cost=0.00..1.11 rows=11 width=4)
         ->  Bitmap Heap Scan on l  (cost=258.87..262.88 rows=1 width=4)
               Recheck Cond: ((s.u = n) OR (n IS NULL))
               ->  BitmapOr  (cost=258.87..258.87 rows=1 width=0)
                     ->  Bitmap Index Scan on l_n  (cost=0.00..4.43 rows=1 width=0)
                           Index Cond: (s.u = n)
                     ->  Bitmap Index Scan on l_n  (cost=0.00..4.43 rows=1 width=0)
                           Index Cond: (n IS NULL)

Zheng

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-02-27T00:48:08Z

On Wed, 27 Feb 2019 at 13:41, Li, Zheng <zhelli@amazon.com> wrote:
> We still check for inner side's nullability, when it is nullable we
> append a "var is NULL" to the anti join condition. So every outer
> tuple is going to evaluate to true on the join condition when there
> is indeed a null entry in the inner.

That's possible, at least providing the var is NULL is an OR
condition, but the problem there is that you force the plan into a
nested loop join. That's unfortunately not going to perform very well
when the number of rows to process is large.

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

Re: NOT IN subquery optimization

Richard Guo <riguo@pivotal.io> — 2019-02-27T06:14:16Z

On Wed, Feb 27, 2019 at 4:52 AM David Rowley <david.rowley@2ndquadrant.com>
wrote:

> On Wed, 27 Feb 2019 at 03:07, Jim Finnerty <jfinnert@amazon.com> wrote:
>
> If you're proposing to do that for this thread then I can take my
> planner only patch somewhere else.  I only posted my patch as I pretty
> much already had what I thought you were originally talking about.
> However, please be aware there are current patents around adding
> execution time smarts in this area, so it's probably unlikely you'll
> find a way to do this in the executor that does not infringe on those.
> Probably no committer would want to touch it.  I think my patch covers
> a good number of use cases and as far as I understand, does not go
> near any current patents.
>
> Thanks for pointing out the patent concerns. I was not aware of that
before.
Could you please provide some clue where I can find more info about the
patents?

Thanks
Richard

Re: NOT IN subquery optimization

Richard Guo <riguo@pivotal.io> — 2019-03-01T02:27:04Z

On Tue, Feb 26, 2019 at 6:51 AM Li, Zheng <zhelli@amazon.com> wrote:

> Resend the patch with a whitespace removed so that "git apply patch" works
> directly.
>
>

Hi Zheng,

I have reviewed your patch. Good job except two issues I can find:

1. The patch would give wrong results when the inner side is empty. In this
case, the whole data from outer side should be in the outputs. But with the
patch, we will lose the NULLs from outer side.

2. Because of the new added predicate 'OR (var is NULL)', we cannot use hash
join or merge join to do the ANTI JOIN.  Nested loop becomes the only
choice,
which is low-efficency.

Thanks
Richard

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-01T12:53:03Z

On Fri, 1 Mar 2019 at 15:27, Richard Guo <riguo@pivotal.io> wrote:
> I have reviewed your patch. Good job except two issues I can find:
>
> 1. The patch would give wrong results when the inner side is empty. In this
> case, the whole data from outer side should be in the outputs. But with the
> patch, we will lose the NULLs from outer side.
>
> 2. Because of the new added predicate 'OR (var is NULL)', we cannot use hash
> join or merge join to do the ANTI JOIN.  Nested loop becomes the only choice,
> which is low-efficency.

Yeah. Both of these seem pretty fundamental, so setting the patch to
waiting on author.

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

Re: NOT IN subquery optimization

Andres Freund <andres@anarazel.de> — 2019-03-01T16:35:21Z

Hi,

On March 1, 2019 4:53:03 AM PST, David Rowley <david.rowley@2ndquadrant.com> wrote:
>On Fri, 1 Mar 2019 at 15:27, Richard Guo <riguo@pivotal.io> wrote:
>> I have reviewed your patch. Good job except two issues I can find:
>>
>> 1. The patch would give wrong results when the inner side is empty.
>In this
>> case, the whole data from outer side should be in the outputs. But
>with the
>> patch, we will lose the NULLs from outer side.
>>
>> 2. Because of the new added predicate 'OR (var is NULL)', we cannot
>use hash
>> join or merge join to do the ANTI JOIN.  Nested loop becomes the only
>choice,
>> which is low-efficency.
>
>Yeah. Both of these seem pretty fundamental, so setting the patch to
>waiting on author.

I've not checked, but could we please make sure these cases are covered in the regression tests today with a single liner? Seems people had to rediscover them a number of times now, and unless this thread results in an integrated feature soonish, it seems likely other people will again.

Andres
-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-01T16:44:17Z

Andres Freund <andres@anarazel.de> writes:
> On March 1, 2019 4:53:03 AM PST, David Rowley <david.rowley@2ndquadrant.com> wrote:
>> On Fri, 1 Mar 2019 at 15:27, Richard Guo <riguo@pivotal.io> wrote:
>>> 1. The patch would give wrong results when the inner side is empty.
>>> 2. Because of the new added predicate 'OR (var is NULL)', we cannot
>>> use hash join or merge join to do the ANTI JOIN.

> I've not checked, but could we please make sure these cases are covered
> in the regression tests today with a single liner?

I'm not sure if the second one is actually a semantics bug or just a
misoptimization?  But yeah, +1 for putting in some simple tests for
corner cases right now.  Anyone want to propose a specific patch?

			regards, tom lane

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-01T22:28:00Z

On Sat, 2 Mar 2019 at 05:44, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> Andres Freund <andres@anarazel.de> writes:
> > I've not checked, but could we please make sure these cases are covered
> > in the regression tests today with a single liner?
>
> I'm not sure if the second one is actually a semantics bug or just a
> misoptimization?  But yeah, +1 for putting in some simple tests for
> corner cases right now.  Anyone want to propose a specific patch?

The second is just reducing the planner's flexibility to produce a
good plan.  The first is a bug. Proposed regression test attached.

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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-01T22:57:58Z

David Rowley <david.rowley@2ndquadrant.com> writes:
> On Sat, 2 Mar 2019 at 05:44, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I'm not sure if the second one is actually a semantics bug or just a
>> misoptimization?  But yeah, +1 for putting in some simple tests for
>> corner cases right now.  Anyone want to propose a specific patch?

> The second is just reducing the planner's flexibility to produce a
> good plan.  The first is a bug. Proposed regression test attached.

LGTM, pushed.

			regards, tom lane

Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-03-01T22:58:42Z

Thanks all for the feedbacks! I'm working on a refined patch.

Although adding "or var is NULL" to the anti join condition forces the planner to choose nested loop anti join, it is always faster compared to the original plan. In order to enable the transformation from NOT IN to anti join when the inner/outer is nullable, we have to add some NULL test to the join condition.

We could make anti join t1, t2 on (t1.x = t2.y or t2.y IS NULL) eligible for hashjoin, it would require changes in allowing this special join quals for hash join as well as changes in hash join executor to handle NULL accordingly for the case.

Another option of transformation is to add "is not false" on top of the join condition.

Regards,
Zheng
On 3/1/19, 5:28 PM, "David Rowley" <david.rowley@2ndquadrant.com> wrote:

    On Sat, 2 Mar 2019 at 05:44, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    >
    > Andres Freund <andres@anarazel.de> writes:
    > > I've not checked, but could we please make sure these cases are covered
    > > in the regression tests today with a single liner?
    >
    > I'm not sure if the second one is actually a semantics bug or just a
    > misoptimization?  But yeah, +1 for putting in some simple tests for
    > corner cases right now.  Anyone want to propose a specific patch?

    The second is just reducing the planner's flexibility to produce a
    good plan.  The first is a bug. Proposed regression test attached.

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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-01T23:13:56Z

"Li, Zheng" <zhelli@amazon.com> writes:
> Although adding "or var is NULL" to the anti join condition forces the planner to choose nested loop anti join, it is always faster compared to the original plan.

TBH, I am *really* skeptical of sweeping claims like that.  The existing
code will typically produce a hashed-subplan plan, which ought not be
that awful as long as the subquery result doesn't blow out memory.
It certainly is going to beat a naive nested loop.

			regards, tom lane

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-01T23:16:26Z

On Sat, 2 Mar 2019 at 12:13, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> "Li, Zheng" <zhelli@amazon.com> writes:
> > Although adding "or var is NULL" to the anti join condition forces the planner to choose nested loop anti join, it is always faster compared to the original plan.
>
> TBH, I am *really* skeptical of sweeping claims like that.  The existing
> code will typically produce a hashed-subplan plan, which ought not be
> that awful as long as the subquery result doesn't blow out memory.
> It certainly is going to beat a naive nested loop.

It's pretty easy to show the claim is false using master and NOT EXISTS.

create table small(a int not null);
create table big (a int not null);
insert into small select generate_Series(1,1000);
insert into big select x%1000+1 from generate_Series(1,1000000) x;

select count(*) from big b where not exists(select 1 from small s
where s.a = b.a);
Time: 178.575 ms

select count(*) from big b where not exists(select 1 from small s
where s.a = b.a or s.a is null);
Time: 38049.969 ms (00:38.050)


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

Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-03-01T23:39:05Z

The current transformation would not add "or s.a is NULL" in the example provided since it is non-nullable. You will be comparing these two cases in terms of the transformation:

select count(*) from big b where not exists(select 1 from small s
where s.a = b.a);
Time: 51.416 ms

select count(*) from big b where a not in (select a from s);
Time: 890.088 ms

 But if s.a is nullable, yes, you have proved my previous statement is false... I should have used almost always.
However, if s.a is nullable, we would do this transformation:
    select count(*) from big b where not exists(select 1 from small s
    where s.a = b.a or s.a is null);

It's possible to stop the nested loop join early during execution once we find an inner Null entry because every outer tuple is
going to evaluate to true on the join condition.

Zheng

On 3/1/19, 6:17 PM, "David Rowley" <david.rowley@2ndquadrant.com> wrote:

    On Sat, 2 Mar 2019 at 12:13, Tom Lane <tgl@sss.pgh.pa.us> wrote:
    >
    > "Li, Zheng" <zhelli@amazon.com> writes:
    > > Although adding "or var is NULL" to the anti join condition forces the planner to choose nested loop anti join, it is always faster compared to the original plan.
    >
    > TBH, I am *really* skeptical of sweeping claims like that.  The existing
    > code will typically produce a hashed-subplan plan, which ought not be
    > that awful as long as the subquery result doesn't blow out memory.
    > It certainly is going to beat a naive nested loop.
    
    It's pretty easy to show the claim is false using master and NOT EXISTS.
    
    create table small(a int not null);
    create table big (a int not null);
    insert into small select generate_Series(1,1000);
    insert into big select x%1000+1 from generate_Series(1,1000000) x;
    
    select count(*) from big b where not exists(select 1 from small s
    where s.a = b.a);
    Time: 178.575 ms
    
    select count(*) from big b where not exists(select 1 from small s
    where s.a = b.a or s.a is null);
    Time: 38049.969 ms (00:38.050)
    
    
    -- 
     David Rowley                   http://www.2ndQuadrant.com/
     PostgreSQL Development, 24x7 Support, Training & Services

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-02T00:11:46Z

On Sat, 2 Mar 2019 at 12:39, Li, Zheng <zhelli@amazon.com> wrote:
> However, if s.a is nullable, we would do this transformation:
>     select count(*) from big b where not exists(select 1 from small s
>     where s.a = b.a or s.a is null);

I understand you're keen to make this work, but you're assuming again
that forcing the planner into a nested loop plan is going to be a win
over the current behaviour. It may well be in some cases, but it's
very simple to show cases where it's a significant regression.

Using the same tables from earlier, and again with master:

alter table small alter column a drop not null;
select * from big where a not in(select a from small);
Time: 430.283 ms

Here's what you're proposing:

select * from big b where not exists(select 1 from small s where s.a =
b.a or s.a is null);
Time: 37419.646 ms (00:37.420)

about 80 times slower. Making "small" a little less small would likely
see that gap grow even further.

I think you're fighting a losing battle here with adding OR quals to
the join condition. This transformation happens so early in planning
that you really can't cost it out either.  I think the only way that
could be made to work satisfactorily would be with some execution
level support for it.  Short of that, you're left with just adding
checks that either side of the join cannot produce NULL values...
That's what I've proposed in [1].

[1] https://www.postgresql.org/message-id/CAKJS1f_OA5VeZx8A8H8mkj3uqEgOtmHBGCUA6%2BxqgmUJ6JQURw%40mail.gmail.com

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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-02T00:45:29Z

David Rowley <david.rowley@2ndquadrant.com> writes:
> I think you're fighting a losing battle here with adding OR quals to
> the join condition.

Yeah --- that has a nontrivial risk of making things significantly worse,
which makes it a hard sell.  I think the most reasonable bet here is
simply to not perform the transformation if we can't prove the inner side
NOT NULL.  That's going to catch most of the useful cases anyway IMO.

			regards, tom lane

Re: NOT IN subquery optimization

Finnerty, Jim <jfinnert@amazon.com> — 2019-03-02T12:34:10Z

Folks - I was away on vacation for the month of February, and can give this
my attention again.

I agree with Tom's comment above - when the cost of the NOT IN is dominated
by the cost of the outer scan (i.e. when the cardinality of the outer
relation is large relative to the cardinality of the subquery), and if the
inner cardinality is small enough to fit in memory, then the current
implementation does an efficient hash lookup into an in-memory structure,
and that's a very fast way to do the NOT IN.  It almost achieves the
lower-bound cost of scanning the outer relation.  It can also parallelizes
easily, whether or not we currently can do that.  In these cases, the
current plan is the preferred plan, and we should keep it.

preferred in-memory hash lookup plan:  https://explain.depesz.com/s/I1kN

This is a case that we would want to avoid the transform, because when both
the inner and outer are nullable and the outer is large and the inner is
small, the transformed plan would Scan and Materialize the inner for each
row of the outer row, which is very slow compared to the untransformed plan:

slow case for the transformation: https://explain.depesz.com/s/0CBB

However, if the inner is too large to fit into memory, then the transformed
plan is faster on all of our other test cases, although our test cases are
far from complete.  If the current solution supports parallel scan of the
outer, for example, then PQ could have lower elapsed time than the non-PQ
nested loop solution.

Also, remember that the issue with the empty inner was just a bug that was
the result of trying to do an additional optimization in the case where
there is no WHERE clause in the subquery.  That bug has been fixed.  The
general case transformation described in the base note produces the correct
result in all cases, including the empty subquery case.







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

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-02T13:34:20Z

On Sat, 2 Mar 2019 at 13:45, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> David Rowley <david.rowley@2ndquadrant.com> writes:
> > I think you're fighting a losing battle here with adding OR quals to
> > the join condition.
>
> Yeah --- that has a nontrivial risk of making things significantly worse,
> which makes it a hard sell.  I think the most reasonable bet here is
> simply to not perform the transformation if we can't prove the inner side
> NOT NULL.  That's going to catch most of the useful cases anyway IMO.

Did you mean outer side NOT NULL?   The OR col IS NULL was trying to
solve the outer side nullability problem when the inner side is empty.
  Of course, the inner side needs to not produce NULLs either, but
that's due to the fact that if a NULL exists in the inner side then
the anti-join should not produce any records.

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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-02T16:25:39Z

David Rowley <david.rowley@2ndquadrant.com> writes:
> On Sat, 2 Mar 2019 at 13:45, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Yeah --- that has a nontrivial risk of making things significantly worse,
>> which makes it a hard sell.  I think the most reasonable bet here is
>> simply to not perform the transformation if we can't prove the inner side
>> NOT NULL.  That's going to catch most of the useful cases anyway IMO.

> Did you mean outer side NOT NULL?

Sorry, sloppy thinking.

>   Of course, the inner side needs to not produce NULLs either, but
> that's due to the fact that if a NULL exists in the inner side then
> the anti-join should not produce any records.

Right.  So the path of least resistance is to transform to antijoin
only if we can prove both of those things (and maybe we need to check
that the join operator is strict, too?  -ENOCAFFEINE).  The question
before us is what is the cost-benefit ratio of trying to cope with
additional cases.  I'm skeptical that it's attractive: the cost
certainly seems high, and I don't know that there are very many
real-world cases where we'd get a win.

Hmm ... thinking about the strictness angle some more: what we really
need to optimize NOT IN, IIUC, is an assumption that the join operator
will never return NULL.  While not having NULL inputs is certainly a
*necessary* condition for that (assuming a strict operator) it's not a
*sufficient* condition.  Any Postgres function/operator is capable
of returning NULL whenever it feels like it.  So checking strictness
does not lead to a mathematically correct optimization.

My initial thought about plugging that admittedly-academic point is
to insist that the join operator be both strict and a member of a
btree opclass (hash might be OK too; less sure about other index types).
The system already contains assumptions that btree comparators never
return NULL.  I doubt that this costs us any real-world applicability,
because if the join operator can neither merge nor hash, we're screwed
anyway for finding a join plan that's better than nested-loop.

			regards, tom lane

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-03T03:53:31Z

On Sun, 3 Mar 2019 at 05:25, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Hmm ... thinking about the strictness angle some more: what we really
> need to optimize NOT IN, IIUC, is an assumption that the join operator
> will never return NULL.  While not having NULL inputs is certainly a
> *necessary* condition for that (assuming a strict operator) it's not a
> *sufficient* condition.  Any Postgres function/operator is capable
> of returning NULL whenever it feels like it.  So checking strictness
> does not lead to a mathematically correct optimization.

That's something I didn't think of.

> My initial thought about plugging that admittedly-academic point is
> to insist that the join operator be both strict and a member of a
> btree opclass (hash might be OK too; less sure about other index types).
> The system already contains assumptions that btree comparators never
> return NULL.  I doubt that this costs us any real-world applicability,
> because if the join operator can neither merge nor hash, we're screwed
> anyway for finding a join plan that's better than nested-loop.

Why strict? If both inputs are non-NULL, then what additional
guarantees does strict give us?

I implemented a btree opfamily check in my version of the patch. Not
so sure about hash, can you point me in the direction of a mention of
how this is guarantees for btree?

The attached v1.2 does this adds a regression test using the LINE
type. This has an operator named '=', but no btree opfamily. A few
other types are in this boat too, per:

select typname from pg_type t where not exists(select 1 from pg_amop
where amoplefttype = t.oid and amopmethod=403) and exists (select 1
from pg_operator where oprleft = t.oid and oprname = '=');

The list of builtin types that have a hash opfamily but no btree
opfamily that support NOT IN are not very exciting, so doing the same
for hash might not be worth the extra code.

select typname from pg_type t where exists(select 1 from pg_amop where
amoplefttype = t.oid and amopmethod=405) and exists (select 1 from
pg_operator where oprleft = t.oid and oprname = '=') and not
exists(select 1 from pg_amop where amoplefttype = t.oid and
amopmethod=403);
 typname
---------
 xid
 cid
 aclitem
(3 rows)

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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-03T04:11:35Z

David Rowley <david.rowley@2ndquadrant.com> writes:
> On Sun, 3 Mar 2019 at 05:25, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> My initial thought about plugging that admittedly-academic point is
>> to insist that the join operator be both strict and a member of a
>> btree opclass (hash might be OK too; less sure about other index types).

> Why strict? If both inputs are non-NULL, then what additional
> guarantees does strict give us?

Yeah, if we're verifying the inputs are non-null, I think that probably
doesn't matter.

> I implemented a btree opfamily check in my version of the patch. Not
> so sure about hash, can you point me in the direction of a mention of
> how this is guarantees for btree?

https://www.postgresql.org/docs/devel/btree-support-funcs.html
quoth

    The comparison function must take two non-null values A and B and
    return an int32 value that is < 0, 0, or > 0 when A < B, A = B, or A >
    B, respectively. A null result is disallowed: all values of the data
    type must be comparable.

(At the code level, this is implicit in the fact that the comparison
function will be called via FunctionCall2Coll or a sibling, and those
all throw an error if the called function returns NULL.)

Now, it doesn't say in so many words that the comparison operators
have to yield results consistent with the comparison support function,
but I think that's pretty obvious ...

For hash, the equivalent constraint is that the hash function has to
work for every possible input value.  I suppose it's possible that
the associated equality operator would sometimes return null, but
it's hard to think of a practical reason for doing so.

I've not dug in the code, but I wouldn't be too surprised if
nodeMergejoin.c or nodeHashjoin.c, or the stuff related to hash
grouping or hash aggregation, also contain assumptions about
the equality operators not returning null.

> The list of builtin types that have a hash opfamily but no btree
> opfamily that support NOT IN are not very exciting, so doing the same
> for hash might not be worth the extra code.

Agreed for builtin types, but there might be some extensions out there
where this doesn't hold.  It's not terribly hard to imagine a data type
that hasn't got a linear sort order but is amenable to hashing.
(The in-core xid type is an example, actually.)

			regards, tom lane

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-03T13:34:42Z

On Sun, 3 Mar 2019 at 17:11, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> (At the code level, this is implicit in the fact that the comparison
> function will be called via FunctionCall2Coll or a sibling, and those
> all throw an error if the called function returns NULL.)
>
> Now, it doesn't say in so many words that the comparison operators
> have to yield results consistent with the comparison support function,
> but I think that's pretty obvious ...

Ah okay. I can get it to misbehave by setting fcinfo->isnull = true in
the debugger from int4eq(). I see the NULL result there is not
verified as that's just translated into "false" by ExecInterpExpr()'s
EEOP_QUAL case.  If you're saying something doing that is
fundamentally broken, then I guess we're okay.

> David Rowley <david.rowley@2ndquadrant.com> writes:
> > The list of builtin types that have a hash opfamily but no btree
> > opfamily that support NOT IN are not very exciting, so doing the same
> > for hash might not be worth the extra code.
>
> Agreed for builtin types, but there might be some extensions out there
> where this doesn't hold.  It's not terribly hard to imagine a data type
> that hasn't got a linear sort order but is amenable to hashing.

On reflection, it seems pretty easy to add this check, so I've done so
in the attached.

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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-03T15:42:29Z

David Rowley <david.rowley@2ndquadrant.com> writes:
> On Sun, 3 Mar 2019 at 17:11, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> (At the code level, this is implicit in the fact that the comparison
>> function will be called via FunctionCall2Coll or a sibling, and those
>> all throw an error if the called function returns NULL.)

> Ah okay. I can get it to misbehave by setting fcinfo->isnull = true in
> the debugger from int4eq(). I see the NULL result there is not
> verified as that's just translated into "false" by ExecInterpExpr()'s
> EEOP_QUAL case.  If you're saying something doing that is
> fundamentally broken, then I guess we're okay.

No, what I'm thinking of is this bit in _bt_compare:

            result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func,
                                                     scankey->sk_collation,
                                                     datum,
                                                     scankey->sk_argument));

You absolutely will get errors during btree insertions and searches
if a datatype's btree comparison functions ever return NULL (for
non-NULL inputs).

For hash indexes, that kind of restriction only directly applies to
hash-calculation functions, which perhaps are not as tightly tied to the
opclass's user-visible operators as is the case for btree opclasses.
But I think you might be able to find places in hash join or grouping
that are calling the actual equality operator and not allowing for it
to return NULL.

			regards, tom lane

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-03T22:02:45Z

On Mon, 4 Mar 2019 at 04:42, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> David Rowley <david.rowley@2ndquadrant.com> writes:
> > On Sun, 3 Mar 2019 at 17:11, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >> (At the code level, this is implicit in the fact that the comparison
> >> function will be called via FunctionCall2Coll or a sibling, and those
> >> all throw an error if the called function returns NULL.)
>
> > Ah okay. I can get it to misbehave by setting fcinfo->isnull = true in
> > the debugger from int4eq(). I see the NULL result there is not
> > verified as that's just translated into "false" by ExecInterpExpr()'s
> > EEOP_QUAL case.  If you're saying something doing that is
> > fundamentally broken, then I guess we're okay.
>
> No, what I'm thinking of is this bit in _bt_compare:
>
>             result = DatumGetInt32(FunctionCall2Coll(&scankey->sk_func,
>                                                      scankey->sk_collation,
>                                                      datum,
>                                                      scankey->sk_argument));
>
> You absolutely will get errors during btree insertions and searches
> if a datatype's btree comparison functions ever return NULL (for
> non-NULL inputs).

I understand this is the case if an index happens to be used, but
there's no guarantee that's going to be the case. I was looking at the
case where an index was not used.

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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-03T22:06:05Z

David Rowley <david.rowley@2ndquadrant.com> writes:
> On Mon, 4 Mar 2019 at 04:42, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> You absolutely will get errors during btree insertions and searches
>> if a datatype's btree comparison functions ever return NULL (for
>> non-NULL inputs).

> I understand this is the case if an index happens to be used, but
> there's no guarantee that's going to be the case. I was looking at the
> case where an index was not used.

Not following your point?  An index opclass is surely not going to be
designed on the assumption that it can never be used in an index.
Therefore, its support functions can't return NULL unless the index AM
allows that.

			regards, tom lane

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-03T22:14:25Z

On Mon, 4 Mar 2019 at 11:06, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> David Rowley <david.rowley@2ndquadrant.com> writes:
> > On Mon, 4 Mar 2019 at 04:42, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >> You absolutely will get errors during btree insertions and searches
> >> if a datatype's btree comparison functions ever return NULL (for
> >> non-NULL inputs).
>
> > I understand this is the case if an index happens to be used, but
> > there's no guarantee that's going to be the case. I was looking at the
> > case where an index was not used.
>
> Not following your point?  An index opclass is surely not going to be
> designed on the assumption that it can never be used in an index.
> Therefore, its support functions can't return NULL unless the index AM
> allows that.

I agree that it makes sense that the behaviour of the two match. I was
trying to hint towards that when I said:

> If you're saying something doing that is
> fundamentally broken, then I guess we're okay.

but likely I didn't make that very clear.

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

Re: Re: NOT IN subquery optimization

David Steele <david@pgmasters.net> — 2019-03-05T08:21:32Z

On 2/27/19 2:26 AM, David Rowley wrote:
> On Wed, 27 Feb 2019 at 13:13, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>
>> "Li, Zheng" <zhelli@amazon.com> writes:
>>> However, given that the March CommitFest is imminent and the runtime smarts patent concerns David had pointed out (which I was not aware of before), we would not move that direction at the moment.
>>
>>> I propose that we collaborate to build one patch from the two patches submitted in this thread for the CF.
>>
>> TBH, I think it's very unlikely that any patch for this will be seriously
>> considered for commit in v12.  It would be against project policy, and
>> spending a lot of time reviewing the patch would be quite unfair to other
>> patches that have been in the queue longer.  Therefore, I'd suggest that
>> you not bend things out of shape just to have some patch to submit before
>> March 1.  It'd be better to work with the goal of having a coherent patch
>> ready for the first v13 CF, probably July-ish.
> 
> FWIW, I did add this to the March CF, but I set the target version to
> 13.  I wasn't considering this for PG12. I see Zheng was, but I agree
> with you on PG13 being the target for this.

Looks like the target version of 13 was removed but I have added it back.

Regards,
-- 
-David
david@pgmasters.net

Re: Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-05T08:53:27Z

On Tue, 5 Mar 2019 at 21:21, David Steele <david@pgmasters.net> wrote:
>
> On 2/27/19 2:26 AM, David Rowley wrote:
> > FWIW, I did add this to the March CF, but I set the target version to
> > 13.  I wasn't considering this for PG12. I see Zheng was, but I agree
> > with you on PG13 being the target for this.
>
> Looks like the target version of 13 was removed but I have added it back.

The problem seems to be that there are now 2 CF entries for this
thread. I originally added [1], but later Zheng added [2].  From what
Jim mentioned when he opened this thread I had the idea that no patch
existed yet, so I posted the one I already had written for this 4
years ago thinking that might be useful to base new work on.  I guess
Zheng's patch already exists when Jim opened this thread as a patch
appeared fairly quickly afterwards.  If that's true then I understand
that they wouldn't want to drop the work they'd already done in favour
of picking mine up.

I'm not all that sure what do to about this. It's going to cause quite
a bit of confusion having two patches in one thread. Part of me feels
that I've hijacked this thread and that I should just drop my patch
altogether and help review Zheng's patch, but I'm struggling a bit to
do that as I've not managed to find problems with my version, but a
few have been pointed out with the other patch  (of course, there may
be some yet undiscovered issues with my version too).

Alternatively, I could take my patch to another thread, but there does
not seem to be much sense in that. It might not solve the confusion
problem.  The best thing would be that if we could work together to
make this work, however, we both seem to have fairly different ideas
on how it should work. Tom and I both agree that Zheng and Jim's
proposal to add OR x IS NULL clauses to the join condition is most
likely a no go area due to it disallowing hash and merge anti-joins.
The last I can understand from Jim is that they appear to disagree
with that and want to do the transformation based on costs.  Perhaps
they're working on some new ideas to make that more feasible. I'm
interested to hear the latest on this.

[1] https://commitfest.postgresql.org/22/2020/
[2] https://commitfest.postgresql.org/22/2023/

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

Re: NOT IN subquery optimization

David Steele <david@pgmasters.net> — 2019-03-05T09:10:55Z

On 3/5/19 10:53 AM, David Rowley wrote:
> On Tue, 5 Mar 2019 at 21:21, David Steele <david@pgmasters.net> wrote:
>>
>> On 2/27/19 2:26 AM, David Rowley wrote:
>>> FWIW, I did add this to the March CF, but I set the target version to
>>> 13.  I wasn't considering this for PG12. I see Zheng was, but I agree
>>> with you on PG13 being the target for this.
>>
>> Looks like the target version of 13 was removed but I have added it back.
> 
> The problem seems to be that there are now 2 CF entries for this
> thread. I originally added [1], but later Zheng added [2].  From what
> Jim mentioned when he opened this thread I had the idea that no patch
> existed yet, so I posted the one I already had written for this 4
> years ago thinking that might be useful to base new work on.

Yeah, I just figured this out when I got to your patch which was 
properly marked as PG13 and then saw they were pointing at the same thread.

At the very least one of the patch entries should be closed, or moved to 
a new thread.

I'm not sure if I have an issue with competing patches on the same 
thread.  I've seen that before and it can lead to a good outcome.  It 
case, as you say, also lead to confusion.

Regards,
-- 
-David
david@pgmasters.net

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-05T09:22:26Z

On Sun, 3 Mar 2019 at 01:34, Jim Finnerty <jfinnert@amazon.com> wrote:
> I agree with Tom's comment above - when the cost of the NOT IN is dominated
> by the cost of the outer scan (i.e. when the cardinality of the outer
> relation is large relative to the cardinality of the subquery), and if the
> inner cardinality is small enough to fit in memory, then the current
> implementation does an efficient hash lookup into an in-memory structure,
> and that's a very fast way to do the NOT IN.  It almost achieves the
> lower-bound cost of scanning the outer relation.  It can also parallelizes
> easily, whether or not we currently can do that.  In these cases, the
> current plan is the preferred plan, and we should keep it.

If you do the conversion to anti-join (without hacking at the join
quals and assuming no nulls are possible), then the planner can decide
what's best.  The planner may choose a hash join which is not hugely
different from a hashed subplan, however from the testing I've done
the Hash Join is a bit faster. I imagine there's been more motivation
over the years to optimise that over hashed subplans.  As far as I
know, there's no parallel query support for hashed subplans, but I
know there is for hash joins.  In short, I don't think it makes any
sense to not translate into an anti-join (when possible). I think the
best anti-join plan will always be a win over the subquery. The
planner could make a mistake of course, but that's a different issue.
We certainly don't consider keeping the subquery around for NOT
EXISTS.

> This is a case that we would want to avoid the transform, because when both
> the inner and outer are nullable and the outer is large and the inner is
> small, the transformed plan would Scan and Materialize the inner for each
> row of the outer row, which is very slow compared to the untransformed plan:
>
> slow case for the transformation: https://explain.depesz.com/s/0CBB

Well, that's because you're forcing the planner into a corner in
regards to the join condition. It has no choice but to nested loop
that join.

> However, if the inner is too large to fit into memory, then the transformed
> plan is faster on all of our other test cases, although our test cases are
> far from complete.  If the current solution supports parallel scan of the
> outer, for example, then PQ could have lower elapsed time than the non-PQ
> nested loop solution.

I'm having a little trouble understanding this.  From what I
understand the code adds an OR .. IS NULL clause to the join
condition. Is this still the case with what you've been testing here?
If so, I'm surprised to hear all your test cases are faster. If
there's an OR clause in the join condition then the planner has no
choice but to use a nested loop join, so it's very surprising that you
would find that faster with larger data sets.

Or does the code your testing implement this a different way? Perhaps
with some execution level support?

> Also, remember that the issue with the empty inner was just a bug that was
> the result of trying to do an additional optimization in the case where
> there is no WHERE clause in the subquery.  That bug has been fixed.  The
> general case transformation described in the base note produces the correct
> result in all cases, including the empty subquery case.

I'm not sure why lack of WHERE clause in the subquery counts for
anything here.  The results set from the subquery can be empty or not
empty with or without a WHERE clause.  The only way you'll know it's
empty during planning is if some gating qual says so, but that's yet
to be determined by the time the transformation should be done.

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

Re: NOT IN subquery optimization

Tom Lane <tgl@sss.pgh.pa.us> — 2019-03-05T14:37:55Z

David Steele <david@pgmasters.net> writes:
> I'm not sure if I have an issue with competing patches on the same 
> thread.  I've seen that before and it can lead to a good outcome.  It 
> case, as you say, also lead to confusion.

It's a bit of a shame that the cfbot will only be testing one of them
at a time if we leave it like this.  I kind of lean towards the
two-thread, two-CF-entry approach because of that.  The amount of
confusion is a constant.

			regards, tom lane

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-05T23:25:46Z

On Wed, 6 Mar 2019 at 03:37, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> David Steele <david@pgmasters.net> writes:
> > I'm not sure if I have an issue with competing patches on the same
> > thread.  I've seen that before and it can lead to a good outcome.  It
> > case, as you say, also lead to confusion.
>
> It's a bit of a shame that the cfbot will only be testing one of them
> at a time if we leave it like this.  I kind of lean towards the
> two-thread, two-CF-entry approach because of that.  The amount of
> confusion is a constant.

That sounds fine. I'll take mine elsewhere since I didn't start this thread.

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

Re: NOT IN subquery optimization

David Rowley <david.rowley@2ndquadrant.com> — 2019-03-05T23:56:40Z

On Wed, 6 Mar 2019 at 12:25, David Rowley <david.rowley@2ndquadrant.com> wrote:
> That sounds fine. I'll take mine elsewhere since I didn't start this thread.

Moved to https://www.postgresql.org/message-id/CAKJS1f82pqjqe3WT9_xREmXyG20aOkHc-XqkKZG_yMA7JVJ3Tw%40mail.gmail.com

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

Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-03-16T21:07:04Z

Hey, here is our latest patch. Major changes in this patch include:
1. Use the original hashed subplan if the inner fits in memory as decided by subplan_is_hashable().
2. Fixed the inner relation empty case by adding an inner relation existence check when we pull x out as a filter on the outer (see details below).
3. Integrate David Rowley's routine to use strict predicates and inner join conditions when checking nullability of a Var.

Detailed description of the patch:

    NOT IN to ANTI JOIN transformation
    
    If the NOT IN subquery is not eligible for hashed subplan as decided by
    subplan_is_hashable(), do the following NOT IN to ANTI JOIN
    transformation:
    
    Single expression:
        When x is nullable:
        t1.x not in (t2.y where p) =>
        ANTI JOIN
        t1 (Filter: t1.x IS NOT NULL or NOT EXISTS (select 1 from t2 where p)),
        t2 on join condition (t1.x=t2.y or t2.y IS NULL)
        and p.
        The predicate "t2.y IS NULL" can be removed if y is non-nullable.
    
        When x is non-nullable:
        t1.x not in (t2.y where p) =>
        ANTI JOIN t1, t2 on join condition (t1.x=t2.y or t2.y IS NULL)
        and p.
        The predicate "t2.y IS NULL" can be removed if y is non-nullable.
    
    Multi expression:
        If all xi's are nullable:
        (x1, x2, ... xn) not in (y1, y2, ... yn ) =>
        ANTI JOIN t1, t2 on join condition:
        ((t1.x1 = t2.y1) and ... (t1.xi = t2.yi) ... and
         (t1.xn = t2.yn)) IS NOT FALSE.
    
        If at least one xi is non-nuallable:
        (x1, x2, ... xn) not in (y1, y2, ... yn ) =>
        ANTI JOIN t1, t2 on join condition:
        (t1.x1 = t2.y1 or t2.y1 IS NULL or t1.x1 IS NULL) and ...
        (t1.xi = t2.yi or t2.yi IS NULL) ... and
        (t1.xn = t2.yn or t2.yn IS NULL or t1.xn IS NULL).
    
    Add nullability testing routine is_node_nonnullable(), currently it
    handles Var, TargetEntry, CoalesceExpr and Const. It uses strict
    predicates, inner join conditions and NOT NULL constraint to check
    the nullability of a Var.
    
    Adjust and apply reduce_outer_joins() before the transformation so
    that the outer joins have an opportunity to be converted to inner joins
    prior to the transformation.
    
    We measured performance improvements of two to five orders of magnitude
    on most queries in a development environment. In our performance experiments,
    table s (small) has 11 rows, table l (large) has 1 million rows. s.n and l.n
    have NULL value. s.nn and l.nn are NOT NULL. Index is created on each column.
    
    Cases using hash anti join:
    l.nn not in (l.nn) 21900s -> 235ms
    l.nn not in (l.nn where u>0) 22000s -> 240ms
    l.n not in (l.nn) 21900s -> 238ms
    l.n not in (l.nn where u>0) 22000s -> 248ms
    
    Cases using index nested loop anti join
    s.n not in (l.nn) 360ms -> 0.5ms
    s.n not in (l.nn where u>0) 390ms -> 0.6ms
    s.nn not in (l.nn) 365ms -> 0.5ms
    s.nn not in (l.nn where u>0) 390ms -> 0.5ms
    
    Cases using bitmap heap scan on the inner and nested loop anti join:
    s.n not in (l.n) 360ms -> 0.7ms
    l.n not in (l.n) 21900s ->  1.6s
    l.n not in (l.n where u>0) 22000s -> 1680ms
    s.nn not in (l.n) 360ms -> 0.5ms
    l.nn not in (l.n) 21900s -> 1650ms
    l.nn not in (l.n where u>0) 22000s -> 1660ms
    
    Cases using the original hashed subplan:
    l.n not in (s.n) 63ms -> 63ms
    l.nn not in (s.nn) 63ms -> 63ms
    l.n not in (s.n where u>0) 63ms -> 63ms

Comments are welcome.

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

Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-06-14T21:38:24Z

In our patch, we only proceed with the ANTI JOIN transformation if
subplan_is_hashable(subplan) is
false, it requires the subquery to be planned at this point.

To avoid planning the subquery again later on, I want to keep a pointer of
the subplan in SubLink so that we can directly reuse the subplan when
needed. However, this change breaks initdb for some reason and I'm trying to
figure it out.

I'll send the rebased patch in the following email since it's been a while.



--
Sent from: http://www.postgresql-archive.org/PostgreSQL-hackers-f1928748.html

Re: [UNVERIFIED SENDER] Re: NOT IN subquery optimization

Zheng (Zane) Li <zhelli@amazon.com> — 2019-06-14T21:41:06Z

Rebased patch is attached.

Comments are welcome.

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

On 6/14/19, 5:39 PM, "zhengli" <zhelli@amazon.com> wrote:

    In our patch, we only proceed with the ANTI JOIN transformation if
    subplan_is_hashable(subplan) is
    false, it requires the subquery to be planned at this point.
    
    To avoid planning the subquery again later on, I want to keep a pointer of
    the subplan in SubLink so that we can directly reuse the subplan when
    needed. However, this change breaks initdb for some reason and I'm trying to
    figure it out.
    
    I'll send the rebased patch in the following email since it's been a while.
    
    
    
    --
    Sent from: http://www.postgresql-archive.org/PostgreSQL-hackers-f1928748.html