Thread: Converting NOT IN to anti-joins during planning
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@n3.nabble.com [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
Attachment
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
Hi Jim, Thanks for replying here. On Wed, 6 Mar 2019 at 16:37, Jim Finnerty <jfinnert@amazon.com> 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
On Wed, 6 Mar 2019 at 12:54, David Rowley <david.rowley@2ndquadrant.com> wrote: > The latest patch is attached. Rebased version after pgindent run. -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services
Attachment
David Rowley <david.rowley@2ndquadrant.com> wrote:
> On Wed, 6 Mar 2019 at 12:54, David Rowley <david.rowley@2ndquadrant.com> 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
Antonin Houska <ah@cybertec.at> 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
On Wed, 6 Mar 2019 at 04:11, David Rowley <david.rowley@2ndquadrant.com> wrote:
Hi Jim,
Thanks for replying here.
On Wed, 6 Mar 2019 at 16:37, Jim Finnerty <jfinnert@amazon.com> 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
On Fri, 14 Jun 2019 at 20:41, Simon Riggs <simon@2ndquadrant.com> wrote:
>
> On Wed, 6 Mar 2019 at 04:11, David Rowley <david.rowley@2ndquadrant.com> wrote:
>>
>> Hi Jim,
>>
>> Thanks for replying here.
>>
>> On Wed, 6 Mar 2019 at 16:37, Jim Finnerty <jfinnert@amazon.com> 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
-----
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" <david.rowley@2ndquadrant.com> wrote:
On Fri, 14 Jun 2019 at 20:41, Simon Riggs <simon@2ndquadrant.com> wrote:
>
> On Wed, 6 Mar 2019 at 04:11, David Rowley <david.rowley@2ndquadrant.com> wrote:
>>
>> Hi Jim,
>>
>> Thanks for replying here.
>>
>> On Wed, 6 Mar 2019 at 16:37, Jim Finnerty <jfinnert@amazon.com> 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
On Mon, 27 May 2019 at 20:43, Antonin Houska <ah@cybertec.at> 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
Attachment
David Rowley <david.rowley@2ndquadrant.com> wrote:
> On Mon, 27 May 2019 at 20:43, Antonin Houska <ah@cybertec.at> 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
David, will we hear from you on this patch during this month? It sounds from Antonin's review that it needs a few changes. Thanks -- Álvaro Herrera https://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
On Tue, 3 Sep 2019 at 09:21, Alvaro Herrera <alvherre@2ndquadrant.com> wrote: > David, will we hear from you on this patch during this month? > It sounds from Antonin's review that it needs a few changes. Thanks for checking. I'm currently quite committed with things away from the community and it's unlikely I'll get to this in September. I'll kick it out to the next 'fest now. Antonin, Thank you for the review. I will respond to it when I get time again. -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services
On Tue, Sep 03, 2019 at 01:13:43PM +1200, David Rowley wrote: > Antonin, Thank you for the review. I will respond to it when I get > time again. It has been close to three months since this last update, so marked the patch as returned with feedback. -- Michael
Attachment
On Mon, May 27, 2019 at 4:44 PM Antonin Houska <ah@cybertec.at> wrote:
David Rowley <david.rowley@2ndquadrant.com> wrote:
> On Wed, 6 Mar 2019 at 12:54, David Rowley <david.rowley@2ndquadrant.com> 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.
Would this be an issue? Suppose the b.j is NULL when ((a JOIN b) ANTI JOIN c)
is evaluated, after the evaluation, the NULL is still there. and can be filtered
out later with b.j = d.l; Am I missing something?
Best Regards
Andy Fan (https://www.aliyun.com/)