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

From: Tomas Vondra <[email-masked]>
Date: Thu, 17 Feb 2022 22:17:36 +0100

On 2/17/22 21:15, Robert Haas wrote:
> On Tue, Feb 1, 2022 at 10:08 AM Andy Fan <[email-masked]> wrote:
>> To address the row estimation issue, The most straightforward way to fix this is to
>> ignore the derived clauses when figuring out the RelOptInfo->rows on base relation.
>> To note which clause is derived from this patch, I added a new field "EquivalenceClass *
>> derived" in RestrictInfo. and then added a  included_derived  option in clauselist_selectivity_ext,
>> during the set_xxx_rel_size function, we can pass the included_derived=false.  This strategy
>> should be used in get_parameterized_baserel_size.   In all the other cases, include_derived=true
>> is used. which are finished in commit 2. (Commit 1 is Daivd's patch, I just  rebased it)
> 
> That doesn't sound correct to me.
> 
> Suppose that we have A.x = B.x and also A.x < 42. We can choose to
> enforce A.x < 42 or we can choose to enforce B.x < 42 or we can do
> both. In general, any of those could be right: if either one of those
> two is highly selective while the other is not very selective at all,
> it's going to be fastest to enforce only the more selective qual. But
> if both are selective then it may be best to enforce both, so let's
> suppose we do that. If we don't adopt the proposal above and just do
> nothing, then our row count estimates for both A and B will include
> the effect of checking x < 42, and so they will be correct, but the
> row count estimate for join(A, B) will include the effect of checking
> x < 42 twice, and so it will be too low, which can mess up the plan at
> higher levels.
> 
> But discounting the effect of B.x < 42 when estimating the size of B
> is also incorrect. Now, the row count estimate for join(A, B) will
> include the effect of x < 42 only once, which is good. However, the
> row count estimate for B will be too high, because it will not include
> the effect of B.x < 42. And that means that the cost estimate for
> join(A, B) will be wrong. It will be too high, because it's going to
> think that it has more rows coming from the B side of the join than
> what is actually the case. And that can also mess up the plan at
> higher levels.
> 
> I think we could get around this problem by having multiple
> RelOptInfos (or something similar that is lighter-weight) for each
> relation. Today, we'd create a RelOptInfo for A, one for B, and one
> for join(A, B), and the paths for the join are created by joining a
> path for A to a path for B. Now imagine that we have instead 5
> RelOptInfos, for {A}, {A|x<42}, {B}, {B|x<42}, and join(A, B). The
> legal paths for that last one can be created by joining {A} to
> {B|x<42} or {A|x<42} to {B} or {A|x<42} to {B|x<42}. Each of those 5
> RelOptInfos can have its own cardinality estimate, and it seems pretty
> straightforward to see how to get both the scan cardinality and the
> join cardinality correct. Now I think this is decidedly non-trivial to
> implement, and I also hear the voice of Tom Lane saying that's going
> to be expensive in both time and memory, and he's not wrong.
> 

IMHO the whole problem is we're unable to estimate the join clause as a
conditional probability, i.e.

   P(A.x = B.x | (A.x < 42) & (B.x < 42))

so maybe instead of trying to generate additional RelOptInfo items we
should think about improving that. The extra RelOptInfos don't really
solve this, because even if you decide to join A|x<42 to B|x<42 it does
nothing to improve the join clause estimate.

With equality clauses we don't have this issue, because if you derive
clauses at the baserel level, the join clause becomes no-op with
selecitivity 1.0. But for inequalities that does not work ...

Interestingly enough, the patch [1] tries to do something like this by
applying extended statistics to joins, and using baserestrictinfos as
"conditions" for statistics on both sides.

It actually deals with a more general form of this case, because the
clauses don't need to reference the same attribute - so for example this
would work too, assuming there is extended stats object on the columns
on each side:

  P(A.c = B.d | (A.e < 42) & (B.f < 42))

[1] https://commitfest.postgresql.org/36/3055/

> On the other hand, I completely agree with David's comments on the
> other thread to the effect that holding our breath is not getting us
> anywhere. People don't keep asking for this feature because it's a
> stupid thing that nobody really wants, and when Tom alleges that it
> will rarely pay off, I think he's pretty far off the mark. The only
> time we need to consider doing any extra work is when we have
> something like the example discussed here, namely A.x = B.x and A.x <
> 42. If there is a variable that is part of an equivalence class and
> also is used in a scan qual, what are the chances that the implied
> inequality is useful? There's no way to estimate that mathematically -
> it's all about what you think human beings are typically going to do -
> but I'd say it's probably better than 50%. I know that when I was
> regularly doing application programming on top of PostgreSQL I was
> VERY aware of this limitation of the optimizer and habitually thought
> about which table to write the inequality against. That kept me out of
> trouble most of the time, but it sure seems like we're punting the
> optimizer's job to the end user.
> 

Not sure. In my experience queries with both a join clause and other
clauses referencing the same attribute are pretty rare. But I agree if
we can do the expensive stuff only when actually needed, with no cost in
the 99.999% other cases, I don't see why not. Of course, code complexity
is a cost too.

> And even then, I still sometimes couldn't stay out of trouble, because
> sometimes I knew that the implied inequality really ought to be
> enforced against both sides of the join to get a decent plan. In that
> case, the only way to get the optimizer to do what I wanted was to
> duplicate the qual. But that runs headlong into the exact problem that
> we're talking about here: now the join selectivity is going to be
> messed up, and then some other part of the plan would get messed up. I
> still remember the frustration associated with that scenario more than
> 10 years later. You can't even fix it by uglifying your query with a
> planner hint, because we don't support those either. Which brings me
> to another point: it's incoherent to simultaneously argue that we
> shouldn't have planner hints but rather focus on improving the
> planner, and at the same time refuse to improve the planner because it
> would make planning too expensive. I actually think we should do both,
> because I neither believe that it's impossible to fix this particular
> problem nor that it is possible to create a planner so good that it
> always makes the right decisions without any explicit input from a
> human being. But the only way you can think this problem is unfixable
> and at the same time think we don't need hints is if you think this
> problem is fake.
> 

IMHO to deal with the estimates it'd be enough to allow calculating
conditional probabilities.

No comment regarding hints ...

regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

---

From: Robert Haas <[email-masked]>
Date: Thu, 17 Feb 2022 17:16:31 -0500

> nothing to improve the join clause estimate.

I guess I hadn't considered that angle. I think the extra RelOptInfos
(or whatever) actually do solve a problem, because enforcing a
high-selectivity join qual against both sides is potentially quite
wasteful, and you need some way to decide whether to do it on one
side, the other, or both. But it's also true that I was wrong to
assume independence ... and if we could avoid assuming that, then the
join selectivity would work itself out without any of the machinery
that I just proposed.

>   P(A.c = B.d | (A.e < 42) & (B.f < 42))

That'd be cool.

> the 99.999% other cases, I don't see why not. Of course, code complexity

Right. I mean, we could have a planner GUC to control whether the
optimization is used even in cases where we see that it's possible.
But Tom keeps arguing that it is possible in many queries and would
benefit few queries, and I'm not seeing why that should be so. I think
it's likely to benefit many of the queries to which it applies.

-- 
Robert Haas
EDB: http://www.enterprisedb.com

---

From: Tomas Vondra <[email-masked]>
Date: Sat, 19 Feb 2022 01:16:53 +0100

> join selectivity would work itself out without any of the machinery

True. We kinda already have this issue for the equality clauses, and
having paths with the condition pushed down (or not) seems like a
natural approach.

>>   P(A.c = B.d | (A.e < 42) & (B.f < 42))

Yeah, but the patch implementing this still needs more work.

> it's likely to benefit many of the queries to which it applies.

Maybe. Although the example I linked some time ago shows a pretty
dramatic improvement, due to picking merge join + index scan, and not
realizing we'll have to skip a lot of data. But that's just one
anecdotal example.

Anyway, I think the best way to deal with these (perfectly legitimate)
concerns is to show how expensive it is for queries not not having such
join/restriction clauses, with the cost being close to 0. And then for
queries with such clauses but not benefiting from the change (a bit like
a worst case).

regards

[1]
https://www.postgresql.org/message-id/CA%2B1Wm9U_sP9237f7OH7O%3D-UTab71DWOO4Qc-vnC78DfsJQBCwQ%40mail.gmail.com

---

From: Andy Fan <[email-masked]>
Date: Mon, 21 Feb 2022 15:46:07 +0800

> Yeah, but the patch implementing this still needs more work.
Thanks for that patch. That patch has been on my study list for a long
time and it can fix the other real case I met some day ago.  I spent one
day studying it again yesterday just that the result does not deserve
sharing at the current stage.   As for the purpose here,  if we have
extended statistics, I believe it can work well.  But requiring extended
statistics for this feature does not look very reasonable to me.  Do you
think we can go further in direction for the issue here?   and it would
be super great that you can take a look at the commit 3 [1].  IIUC,
It can solve the issue and is pretty straightforward.

[1]
https://www.postgresql.org/message-id/CAKU4AWrdeQZ8xvf%3DDVhndUs%3DRGn8oVoSJvYK3Yj7uWq2%3Ddt%3DMg%40mail.gmail.com

-- 
Best Regards
Andy Fan