Subject: Condition pushdown: why (=) is pushed down into join, but BETWEEN or >= is not?

From: Dmitry Astapov <[email-masked]>
Date: Wed, 12 May 2021 11:41:20 +0100

Hi!
I am trying to understand the behaviour of the query planner regarding the
push-down of the conditions "through" the join.

Lets say that I have tables a(adate date, aval text) and b(bdate date, bval
text), and I create a view:

create view v as
   select a.adate, a.aval, b.bval from a join b on (a.adate = b.bdate);

Now, when I do (explain select * from v where adate='2021-05-12') I can see
that condition (= '2021-05-12') is used by the planned for table access to
both a and b.

However, if I use range-like condition (this is probably not a correct
terminology, but I am not familiar with the correct one) like BETWEEN or
(>='2021-05-21'), I will see that planner will use this condition to access
a, but not b. It seems that the type of join (inner or left) does not
really matter.

DB fiddle that illustrates this;
https://www.db-fiddle.com/f/pT2PwUkhJWuX9skWiBWXoL/0

In my experiments, I was never able to get an execution plan that "pushes
down" any condition apart from (=) through to the right side of the join,
which is rather surprising and leads to suboptimal planner estimates and
execution plans whenever view like the above is a part of a bigger query
with more joins on top.

Equally surprising is that I was unable to find documentation or past
mailing list discussions of this or similar topic, which leads me to
believe that I am just not familiar with the proper terminology and can't
come up with the right search terms.

Can you please tell me what is the proper way to describe this
behaviour/phenomenon (so that I can use it as search terms) and/or provide
me with references to the parts of the source code that determines which
conditions would be "pushed down" and which are not?

PS As far as I can see, this behaviour is consistent between versions 9.5,
10, 11, 12 and 13.

-- 
D. Astapov

---

From: Tom Lane <[email-masked]>
Date: Wed, 12 May 2021 11:54:06 -0400

> push-down of the conditions "through" the join.

I think your mental model is wrong.  What's actually happening here is
that the planner uses equivalence classes to deduce implied conditions.
That is, we have the join condition a.adate = b.bdate and then you've
added the where condition a.adate = '2021-05-12'.  Transitivity implies
that b.bdate = '2021-05-12', so we deduce that condition and are able
to apply it at the relation scan of b.  Furthermore, having restricted
both a.adate and b.bdate to the same constant value at the scan level,
we no longer need to apply the join condition a.adate = b.bdate at all.
This is important not only to avoid the (probably minor) inefficiency
of rechecking the join condition, but because if we believed that all
three conditions were independently applicable, we'd come out with a
serious underestimate of the size of the join result.

> down" any condition apart from (=) through to the right side of the join,

None of the argument sketched above works for non-equality conditions.
There are some situations where you could probably figure out how to
use transitivity to deduce some implied condition, but cleaning things
up so that you don't have redundant conditions fouling up the join
size estimates seems like a hard problem.

Another issue is that we could easily expend a lot of cycles on deductions
that lead nowhere, because once you try to open up the mechanism to
consider operators other than equality, there will be a lot of things that
it looks at and then fails to do anything with.  The equivalence class
mechanism is tied into the same logic that considers merge and hash joins,
so we are expending lots of cycles anytime we see an equality operator,
and not so much for other operators.

> come up with the right search terms.

src/backend/optimizer/README has a discussion of equivalence classes.

			regards, tom lane

---

From: Dmitry Astapov <[email-masked]>
Date: Wed, 12 May 2021 18:56:00 +0100

> serious underestimate of the size of the join result.

Thank you very much, my mental model was indeed incorrect, and the above is
very helpful.
Am I right in thinking that elimination the join condition is actually
quite important part of the process?
Could it possibly be the main reason for =ANY/(x IN (..)) not to be
optimized the same way?

> size estimates seems like a hard problem.

I agree about inequality conditions, this problem seems to be rather hard
to tackle in the general case.

Is it still hard when one thinks about =ANY or (column in (val1, val2,
val3, ...)) as well?
I am thinking that =ANY would be a decent workaround for (x BETWEEN a AND
b) in quite a lot of cases, if it was propagated to all the columns in the
equivalence class.

> src/backend/optimizer/README has a discussion of equivalence classes.
Thank you, this gives me a plethora of keywords for further searches.

I realize that it is possibly off-topic here, but what about workarounds
for inequality constraints, joins and views? Maybe you could give me some
pointers here as well?

My tables are large to huge (think OLAP, not OLTP). I found out when I have
a view that joins several (2 to 10) tables on the column that is
semantically the same in all of them (let's say it is ID and we join on
ID), I do not have many avenues to efficiently select from such view for a
list of IDs at the same time.

I could:
1) Do lots of fast queries and union them:
select * from vw where id=ID1 union all select * from vw where id=ID2
....., which is only really feasible if the query is generated by the
program

2)expose all ID columns from all the tables used in the view body and do:
select * from vw where id=ANY() and id1=ANY() and id2=ANY() and id3=ANY()
.....
This only works well if the view hierarchy is flat (no views on views). If
there are other views that use this use, re-exports of extra columns
quickly snowballs, you might need column renaming if same view ends up
being used more than once through two different dependency paths. Plus
people not familiar with the problem tend to omit "clearly superfluous"
columns from the new views they build on top.

3)forbid views that join tables larger than a certain size/dismantle views
that become inefficient (this only works if the problem is detected fast
enough and the view did not become popular yet)

So all of the workarounds I see in front of me right now are somewhat sad,
but they are necessary, as not doing them means that queries would take
hours or days instead of minutes.

Is there anything better that I have not considered in terms of workarounds?

-- 
D. Astapov

---

From: Tom Lane <[email-masked]>
Date: Thu, 13 May 2021 19:21:57 -0400

> Could it possibly be the main reason for =ANY/(x IN (..)) not to be

Yup.

> Is it still hard when one thinks about =ANY or (column in (val1, val2,

Yeah.  For instance, if you have
   WHERE a = b AND a IN (1,2,3)
then yes, you could deduce "b IN (1,2,3)", but this would not give you
license to drop the "a = b" condition.  So now you have to figure out
what the selectivity of that is after the application of the partially
redundant IN clauses.

I recall somebody (David Rowley, maybe?  Too lazy to check archives.)
working on this idea awhile ago, but he didn't get to the point of
a committable patch.

			regards, tom lane

---

From: David Rowley <[email-masked]>
Date: Fri, 14 May 2021 16:21:52 +1200

> working on this idea awhile ago, but he didn't get to the point of

Yeah. Me. The discussion is in [1].

David

[1] https://www.postgresql.org/message-id/flat/CAKJS1f9FK_X_5HKcPcSeimy16Owe3EmPmmGsGWLcKkj_rW9s6A%40mail.gmail.com

---

From: Andy Fan <[email-masked]>
Date: Mon, 17 May 2021 10:52:22 +0800

>
>
> So now you have to figure out

Would marking the new added RestrictInfo.norm_selec > 1 be OK?

clause_selectivity_ext

        /*
         * If the clause is marked redundant, always return 1.0.
         */
        if (rinfo->norm_selec > 1)
            return (Selectivity) 1.0;

-- 
Best Regards
Andy Fan (https://www.aliyun.com/)

---

From: David Rowley <[email-masked]>
Date: Thu, 20 May 2021 00:14:47 +1200

> Would marking the new added RestrictInfo.norm_selec > 1 be OK?

There would be cases you'd want to not count the additional clauses in
the selectivity estimation and there would be cases you would want to.

For example:

SELECT ... FROM t1 INNER JOIN t2 ON t1.dt = t2.dt WHERE t1.dt BETWEEN
'date1' AND 'date2';

If you derived that t2.dt is also BETWEEN 'date1' AND 'date2' then
you'd most likely want to include those quals for scans feeding merge,
hash and non-parameterized nested loop joins, so you'd also want to
count them in your selectivity estimations, else you'd feed junk
values into the join selectivity estimations.

Parameterized nested loop joins might be different as if you were
looping up an index for t1.dt values on some index on t2.dt, then
you'd likely not want to bother also filtering out the between clause
values too. They're redundant in that case.

I imagined we'd have some functions in equivclass.c that allows you to
choose if you wanted the additional filters or not.

Tom's example, WHERE a = b AND a IN (1,2,3), if a and b were in the
same relation then you'd likely never want to include the additional
quals.  The only reason I could think that it would be a good idea is
if "b" had an index but "a" didn't.  I've not checked the code, but
the index matching code might already allow that to work anyway.

David

---

From: Andy Fan <[email-masked]>
Date: Thu, 20 May 2021 13:21:42 +0800

> values into the join selectivity estimations.
Yes, you are correct.

> values too. They're redundant in that case.
I do not truly understand this.

> choose if you wanted the additional filters or not.

Sounds like a good idea.

> the index matching code might already allow that to work anyway.
+1 for this feature overall.