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

From: Tom Lane <[email-masked]>
Date: Tue, 01 Mar 2022 21:05:02 -0500

Robert Haas <[email-masked]> writes:
> I agree. My question is: why shouldn't every case where we can deduce
> an implied inequality be reasonably likely to show a benefit?

Maybe it will be, if we can deal with the issue you already mentioned
about not misestimating the resulting partially-redundant conditions.

> Second, it looks to me like the patch takes the rather naive strategy
> of enforcing the derived clauses everywhere that they can legally be
> put, which seems certain not to be optimal.

I'm not sure about that ... it's basically what we do with derived
equalities.  However, there's enough structure in the equivalence-class
case that we don't end up enforcing redundant quals.  It's not clear
to me whether the same can be said here.

> I don't know whether attaching something to the equivalence class data
> structure is the right idea or not. Presumably, we don't want to make
> an extra pass over the query tree to gather the information needed for
> this kind of optimization, and it feels like we need to know which
> vars are EMs before we try to derive alternate/additional quals.

Yeah, we don't want to make an additional pass over the tree, and
we also would rather not add an additional set of per-operator
catalog lookups.  We might be able to generalize the code that looks
for equality operators so that it looks for "any btree operator"
with the same number of lookups, and then have it feed the results
down either the EquivalenceClass path or the inequality path
as appropriate.  At the end, after we've formed all the ECs, we
could have a go at matching up the inequality structures with the
ECs.  But I don't agree that ECs are a necessary prerequisite.
Here are a couple of other patterns that might be worth looking for:

* "a > b AND b > c" allows deducing "a > c", whether or not any
of those values appears in an EC.

* "a > const1 AND a > const2" can be simplified to either "a > const1"
or "a > const2" depending on which constant is larger.  (The predicate
proof mechanism already has a form of this, but we don't typically
apply it in a way that would result in dropping the redundant qual.)

It's entirely possible that one or both of these patterns is not
worth looking for.  But I would say that it's equally unproven
that deriving "a > c" from "a = b AND b > c" is worth the cycles.
I'll grant that it's most likely going to be a win if we can use
any of these patterns to generate a restriction clause from what
had been join clauses.  Beyond that it's much less clear.

			regards, tom lane

---

From: Robert Haas <[email-masked]>
Date: Wed, 2 Mar 2022 10:46:15 -0500

> about not misestimating the resulting partially-redundant conditions.

OK.

> to me whether the same can be said here.

I mean, to go back to the example of a.x < 42 and a.x = b.x, there are
three possible choices as to where to enforce the qual (a, b, both).
That's a meaningful choice, independent of any estimation issue. I
think it is reasonably common to have cases where a.x < 42 is very
selective and b.x < 42 hardly filters out anything at all, or the
other way around. Certainly, that kind of situation came up a lot in
PostgreSQL-based applications that I wrote myself back in the day. If
we're just talking about btree operators, *maybe* we can say it's
cheap enough that we don't care, but color me a tad skeptical.

> ECs.

Interesting idea.

> But I don't agree that ECs are a necessary prerequisite.

Pretty much all of the cases that I've run across involve an equijoin
plus an inequality, so if somebody asked me which problem we ought to
put most effort into solving, I'd say that one. Cases like "a>1 and
a>2" or a same-table case like "a=b and b>3" haven't been as common in
my experience, and haven't caused as much trouble when they do happen.
Part of that is because if you have something like "a>1 and a>2" in
your query, it may be easy for you to just tweak the query generation
to avoid it, and if "a=b and b>3" is coming up a lot, you may choose
to adjust your data model (e.g. choose to store NULL in b to indicate
same-as-a), whereas if you have something like
"orders.orderno=order_lines.orderno and order_lines.orderno<10000,"
what are you going to do to avoid that exactly? If you normalize your
order data and then want to find the old orders, this problem arises
ineluctably.

But having said that, I'm not *against* doing something about those
cases if it's cheap or falls out naturally. If we could detect for
free that the user had written a>1 and a>2, it'd certainly be
beneficial to drop the former qual and keep only the latter. If the
user writes a>b and b>c and all those columns are in one table I don't
see how it helps to derive a>c, because we're still going to need to
check the other two quals anyway so we've just created more work. But
if those columns are not all in the same table then I'd say chances
are really pretty good. Like, suppose it's x.a>y.b and y.b>x.c. Well,
like I say, I don't really see people writing queries like that
myself, but if they do, it seems pretty obvious that deriving x.a>x.c
has the potential to save a LOT of trouble. If it's x.a>y.b and
y.b>z.c I don't feel quite so optimistic, but it may be that we would
like to do the x-z join first, and if we do, enforcing x.a>z.c at that
level to shrink the join product seems like a very strong idea. It is
a slight loss if we run that qual on lots of rows and it never fails,
but it is a gigantic win if it filters out a bunch of stuff. I bet a
lot of users would be VERY happy to pay the cost of testing x.a>z.c at
the x-z join level even on queries where the statistics suggest that
it will be entirely useless, because it won't cost that much to check
it, and if by some chance the statistics are misleading, it might
prevent a really bad outcome where the query runs for a super-long
time and they get paged. So the questions in my mind here are all
about whether we can detect this stuff cheaply and whether anybody
wants to do the work to make it happen, not whether we'd get a benefit
in the cases where it kicks in.

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

---

From: Tom Lane <[email-masked]>
Date: Wed, 02 Mar 2022 11:09:27 -0500

Robert Haas <[email-masked]> writes:
> So the questions in my mind here are all

Right, my worries are mostly about the first point.

			regards, tom lane

---

From: Robert Haas <[email-masked]>
Date: Wed, 2 Mar 2022 12:29:06 -0500

> Right, my worries are mostly about the first point.

OK, cool.

---

From: Andy Fan <[email-masked]>
Date: Tue, 8 Mar 2022 21:44:37 +0800

> > Right, my worries are mostly about the first point.

I have finished the PoC for planning timing improvement and joinrel rows
estimation.
the design considers the requirement we can enforce any corrective quals
during
execution (rather than must execute the RestirctInfo which user provides),
but
nothing is coded for that part so far.

Copy the commit message here for easy discussion.

== Planning timing part ==
Patch 1:   expand the duties of check_mergejoinable to check non-equal btree
    operators as well to support the EC Filter function.  A new field
    named btreeineqopfamilies is added in RestictInfo and it is set
    with the same round syscache search for check_mergejoinable. Because
    of this, check_mergejoinable is renamed to check_btreeable.
    The bad part of this is it only works for opclause so far.

Patch 2:   Introduce ec_filters in EquivalenceClass struct, the semantics
is that the quals can
    be applied to any EquivalenceMember in this EC. Later this information
is used
    to generate new RestrictInfo and was distributed to related RelOptInfo
very
    soon.  There are 3 major steps here:

    a). In distribute_qual_to_rels to gather the ineq quallist.
    b). After deconstruct_jointree, distribute_filter_quals_to_eclass
distributes
    these ineq-quallist to the related EC's ef_filters.
    c). generate_base_implied_equalities_no_const scan the ec_filters and
distribute
    the restrictinfo to related RelOptInfo.

Patch 3:     Reduce some planning cost for deriving qual for EC filter
feature.
    Mainly changes include:
    1. Check if the qual is simple enough by checking rinfo->right_relids
and
    info->right_relids, save the pull_varnos of rinfo->clause calls.
    2. check contain_volatile_functions against RestrictInfo, so that
    the result can be shared with following calls.
    3. By employing the RestictInfo->btreeineqfamility which is calculating.
    with the same round of calculating  RestrictInfo->mergeopfamilies. In
this
    way we save some calls for syscache.
    4. Calculating the opfamility and amstrategy at
    distribute_filter_quals_to_eclass and cache the results in
EquivalenceFilter.
    if no suitable opfamility and amstrategy are found, bypass the qual
immediately
    and at last using the cached value
generate_base_implied_equalities_no_const.

    After this change, there is a testcase changed unexpectedly in
equivclass.out
    (compared with Patch-2 expectation file.)

    create user regress_user_ectest;
    grant select on ec0 to regress_user_ectest;
    grant select on ec1 to regress_user_ectest;

    set session authorization regress_user_ectest;

    -- with RLS active, the non-leakproof a.ff = 43 clause is not treated
    -- as a suitable source for an EquivalenceClass; currently, this is true
    -- even though the RLS clause has nothing to do directly with the EC
    explain (costs off)
    regression->   select * from ec0 a, ec1 b
    regression->   where a.ff = b.ff and a.ff = 43::bigint::int8alias1;

    The b.ff = 43 has disappeared from ec1 b. But since it even didn't shown
    before the EC filter, so I'm not sure my changes here make something
wrong,
    maybe fix an issue by accident?

== Join Rel size estimation part ==

I have revist the strategy before,  the main reasons are 1).  we should
consider every
qual *equally*.  2).  In the past, I just wanted to get the same result as
ec filters doesn't
happen,  but later I found that even if there is no ec filter, we still
have some estimation error
clearly.  for example:

create table ec_t1000 (a int);
insert into ec_t1000 select i from generate_series(1, 1000)i;
create table ec_t110 (a int);
insert into ec_t110 select i from generate_series(1, 110) i;
create table ec_t200 (a int);
insert into ec_t200 select i from generate_series(1, 200) i;
analyze ec_t1000, ec_t110, ec_t200;

query 1: explain select * from ec_t1000, ec_t110 where ec_t1000.a =
ec_t110.a and ec_t1000.a > 100; -- (0.9)

query 2: explain select * from ec_t1000, ec_t110 where ec_t1000.a =
ec_t110.a and ec_t110.a > 100; --  (0.1)

query 3: explain select * from ec_t1000, ec_t110 , ec_t200 where ec_t1000.a
= ec_t110.a and ec_t110.a = ec_t200.a and ec_t1000.a > 100;

query 4: explain select * from ec_t1000, ec_t110 , ec_t200 where ec_t1000.a
= ec_t110.a and ec_t110.a = ec_t200.a and ec_t110.a > 100;

query 5: explain select * from ec_t1000, ec_t110 , ec_t200 where ec_t1000.a
= ec_t110.a and ec_t110.a = ec_t200.a and ec_t200.a > 100;

we can see query 1 is the same as query 2,  and query 3/4/5 should be the
same as well. The fact
is not. Here is the result on the current master and patched version.

| Query Id | Real rows | Est. Rows at master | Est. rows with patched |
|----------+-----------+---------------------+------------------------|
|        1 |        10 |                  99 |                     10 |
|        2 |        10 |                  10 |                     10 |
|        3 |        10 |                  20 |                     11 |
|        4 |        10 |                   2 |                     11 |
|        5 |        10 |                  11 |                     11 |

Patch 4:  Prepare the code for CorrectiveQual structure.
    Just refactor the method for 2-level loop in
    generate_base_implied_equalities_no_const, no other things are changed.

Patch 5:   struct CorrectiveQuals is as simple as a List of RestrictInfo,
the properties
of it are:  a). only one restrictinfo on this group should be counted for
any joinrel
size estimation. b). at least 1 restrictinfo in this group should be
executed during
execution. In this  commit, only the size estimation issue is tried.

    PlannerInfo.correlative_quals is added to manage all the
CorrectiveQuals at
    subquery level. RelOptInfo.cqual_indexes is a List * to indicate a which
    CorrectiveQuals this relation is related to. This is designed for easy
to check if
    the both sides of joinrel correlated to the same CorrectiveQuals. The
reason why
    "List *" will be explained later.

    The overall design of handing the joinrel size estimation is:
    a). At the base relation level, we just count everything with the
correlative
    quals. b). During any level joinrel size estimation, we just keep 1
side's
    cqual (short for corrective qual) selectivity by eliminating the other
one. so
    the size estimation for a mergeable join selectivity becomes to:

    rows = R1.rows X r2.rows X 1 / Max (ndistval_of_colA,
 ndistinval_of_colB) X 1 /
    Selectivity(R1's CorrectiveQual).

    r1.rows X 1 / Selectivity(R1's CorrectiveQual) eliminates the impact of
    CorrectiveQual on R1.  After this,  the JoinRel of (R1, R2) still be
impacted by
    this CorrectiveQual but "just once" in this level.  Later if
JoinRel(R1, R2) needs
    to join with R3,  and R3 is impacted by this CorectiveQuals as well. We
    need to keep one and eliminate the other one as above again.

    The algorithm for which Selectivity should be eliminated and which one
should be
    kept is:

    When we join 2 inner_rel and outer_rel with a mergeable join
restrictinfo, if
    both sides is impacted with the same CorrectiveQual, we first choose
which "side"
    to eliminating based on which side of the restrictinfo has a higher
distinct
    value. The reason for this is more or less because we used
"Max"(ndistinctValT1,
    ndistinctValT2). After deciding which "side" to eliminate, the real
eliminating
    selectivity is RelOptInfo->cqual_selectivity[n],  The left one still
takes effect
  and is noted in the joinrel->cqual_selectivitity[n].

    Introduction of RelOptInfo->cqual_selectivity:

     The number of elements in cqual_selecitity equals
     the length of cqual_indexes. The semantics is which
     Selectivity in the corresponding CorectiveQuals's qual
     list is taking effect. At any time, only 1 Qual
     Selectivity is counted for any-level of joinrel size estimation.

    In reality, it is possible to have many CorrectiveQuals, but for design
    discussion, the current implementation only takes care of the 1
CorrectiveQuals.
    This would be helpful for PoC/review/discussion.

    Some flow for the key data:

    1. root->corrective_quals is initialized at
    generate_base_implied_equalities_no_const stage. we create a
CorrectiveQual in
    this list for each ec_filter and fill the RestrictInfo part for it. At
    the same time, we note that which RelOptInfo (cqual_indexes) is related
to this cqual.

    2. RelOptInfo->cqual_selecitity for baserel is set at the end of
set_rel_size,
    at this time, the selectivity for every RestrictInfo is calculated, we
can just
    fetch the cached value.  As for joinrel, it is maintained in
    calc_join_cqual_selectivity, this function would return the Selectivity
to
    eliminate and set the above value.

    Limitation in this PoC:
    1. Only support 1 CorrectiveQual in root->correlative_quals
    2. Only tested with INNER_JOIN.
    3. Inherited tables are not supported.

I find it is hard to explain things clearly without the code. Any feedback
is welcome.

-- 
Best Regards
Andy Fan

---

From: Andy Fan <[email-masked]>
Date: Thu, 17 Mar 2022 11:13:15 +0800

Hi:

I just tested more cases for the estimation issue for this feature, and we
can
find **we get a more accurate/stable estimation than before**. Here is the
test
cases and result (by comparing the master version and patched version).

create table ec_t110 as select i::int as a from generate_series(1, 110) i;
create table ec_t200 as select i::int as a from generate_series(1, 200) i;
create table ec_t500 as select i::int as a from generate_series(1, 500) i;
create table ec_t800 as select i::int as a from generate_series(1, 800) i;
create table ec_t1000 as select i::int as a from generate_series(1, 1000) i;

analyze;

-- 2 table joins.
explain analyze select * from ec_t1000, ec_t110 where ec_t1000.a =
ec_t110.a and ec_t1000.a > 100; -- (0.9)
explain analyze select * from ec_t1000, ec_t110 where ec_t1000.a =
ec_t110.a and ec_t110.a > 100; --  (0.1)

-- 3 table joins.
explain analyze select * from ec_t1000, ec_t110 , ec_t200 where ec_t1000.a
= ec_t110.a and ec_t110.a = ec_t200.a and ec_t1000.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200 where ec_t1000.a
= ec_t110.a and ec_t110.a = ec_t200.a and ec_t110.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200 where ec_t1000.a
= ec_t110.a and ec_t110.a = ec_t200.a and ec_t200.a > 100;

-- 4 table joins.
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500 where
ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a = ec_t200.a
and ec_t1000.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500 where
ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a = ec_t200.a
and ec_t110.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500 where
ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a = ec_t200.a
and ec_t200.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500 where
ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a = ec_t200.a
and ec_t500.a > 100;

-- 5 table joins.
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500, ec_t800
where ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a =
ec_t200.a and ec_t500.a = ec_t800.a and ec_t1000.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500, ec_t800
where ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a =
ec_t200.a and ec_t500.a = ec_t800.a and ec_t110.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500, ec_t800
where ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a =
ec_t200.a and ec_t500.a = ec_t800.a and ec_t200.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500, ec_t800
where ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a =
ec_t200.a and ec_t500.a = ec_t800.a and ec_t500.a > 100;
explain analyze select * from ec_t1000, ec_t110 , ec_t200, ec_t500, ec_t800
where ec_t1000.a = ec_t110.a and ec_t110.a = ec_t200.a and ec_t500.a =
ec_t200.a and ec_t500.a = ec_t800.a and ec_t800.a > 100;

| Query Id | Real rows | Est. Rows at master | Est. rows with patched |
table # |
|----------+-----------+---------------------+------------------------+---------|
|        1 |        10 |                  99 |                     10 |
  2 |
|        2 |        10 |                  10 |                     10 |
  2 |
|        3 |        10 |                  20 |                     11 |
  3 |
|        4 |        10 |                   2 |                     11 |
  3 |
|        5 |        10 |                  11 |                     11 |
  3 |
|        6 |        10 |                  10 |                      9 |
  4 |
|        7 |        10 |                   1 |                      9 |
  4 |
|        8 |        10 |                   6 |                      9 |
  4 |
|        9 |        10 |                   9 |                      9 |
  4 |
|       10 |        10 |                   8 |                      8 |
  5 |
|       11 |        10 |                   1 |                      8 |
  5 |
|       12 |        10 |                   5 |                      8 |
  5 |
|       13 |        10 |                   7 |                      8 |
  5 |
|       14 |        10 |                   8 |                      8 |
  5 |

In the past, we can just use the qual user provided to do estimation. As for
now, since we introduce the CorrectiveQuals design, we still keep just only
1
qual counted, but we can choose the best one in CorrectiveQuals no matter
which
one is provided by the user. we gain a better and stable estimation because
of this.

I'm happy about the overall design but not pretty confident about the
method to
"choose the best one to keep". So I did some test case as many as I can to
find
something is wrong, so far so good.

I'm also happy with how to keep only one qual in CorrectiveQuals (not
choose the
best one). Assume we just have 1 EC filter in this query for simplicity. At
the
beginning, all the baserel have been impacted by CorrectiveQual. When join 2
relations, we rollback 1 side and keep the other one. when we join this
joinrel
with another rel,  we rollback 1 side and keep the other one and so forth.

(rollback is not changing some things which we already computed, it is only
used when estimating size for coming joinrel).

The patchset can be applied cleanly with
9e98583898c347e007958c8a09911be2ea4acfb9.

---

From: Andres Freund <[email-masked]>
Date: Mon, 21 Mar 2022 18:41:33 -0700

Hi,

> I have finished the PoC for planning timing improvement and joinrel rows

This currently crashes on cfbot:
https://api.cirrus-ci.com/v1/task/6158455839916032/logs/cores.log
https://cirrus-ci.com/task/6158455839916032

As this is clearly not 15 material, I've set the target version as 16. But it
might be good to just move the whole entry to the next CF...

Greetings,

Andres Freund

---

From: Andy Fan <[email-masked]>
Date: Thu, 24 Mar 2022 10:21:41 +0800

Hi:

Thanks for take care of this.

> https://cirrus-ci.com/task/6158455839916032
The crash happens at my own Assert statement. I assume we know the
Selectivity
for a RestrictInfo after set_rel_size, however  this is not true for foreign
table with use_remote_estimate=true. Since we are in a design discussion
stage,
I just disable this feature for foreign tables and can fix it later. Would
this be the
right way to go?

> might be good to just move the whole entry to the next CF...
Thanks for doing that.  I tried but didn't find how to move it to the next
CF.

Here is the latest code. I have rebased the code with the latest master
a1bc4d3590b.

-- 
Best Regards
Andy Fan

---

From: Thomas Munro <[email-masked]>
Date: Tue, 17 May 2022 10:51:52 +1200

On Thu, Mar 24, 2022 at 3:22 PM Andy Fan <[email-masked]> wrote:
> Here is the latest code. I have rebased the code with the latest master a1bc4d3590b.

FYI this is failing with an unexpected plan in the partition_join test:

https://api.cirrus-ci.com/v1/artifact/task/6090435050340352/log/src/test/regress/regression.diffs

---

From: Andy Fan <[email-masked]>
Date: Tue, 17 May 2022 10:00:35 +0800

> https://api.cirrus-ci.com/v1/artifact/task/6090435050340352/log/src/test/regress/regression.diffs

Thanks.  But I will wait to see if anyone will show interest with this. Or
else
Moving alone is not a great experience.

-- 
Best Regards
Andy Fan

---

From: Andrey Lepikhov <[email-masked]>
Date: Thu, 7 Jul 2022 14:11:06 +0300

On 17/5/2022 05:00, Andy Fan wrote:
> Thanks.  But I will wait to see if anyone will show interest with this. 
> Or else
To move forward I've rebased your patchset onto new master, removed 
annoying tailing backspaces and applied two regression test changes, 
caused by second patch: first of changes are legal, second looks normal 
but should be checked on optimality.
As I see, a consensus should be found for the questions:
1. Case of redundant clauses (x < 100 and x < 1000)
2. Planning time degradation for trivial OLTP queries

-- 
regards,
Andrey Lepikhov
Postgres Professional

From 9bc8ce0021869cef0ce6029d8aaf2a363434e268 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 6 Jul 2022 14:44:56 +0300
Subject: [PATCH 1/6] Expand the duties of check_mergejoinable to check
 non-equal btree operator as well to support the EC Filter function.  A new
 field named btreeineqopfamilies is added into RestictInfo and it is set with
 the same round syscache search for check_mergejoinable. because of this,
 check_mergejoinable is renamed to check_btreeable.

The bad part of this is it only works for opclause so far.
---
 src/backend/optimizer/plan/initsplan.c    | 35 +++++++++++------------
 src/backend/optimizer/util/restrictinfo.c |  1 +
 src/backend/utils/cache/lsyscache.c       | 35 +++++++++++++++++++++++
 src/include/nodes/pathnodes.h             |  1 +
 src/include/utils/lsyscache.h             |  1 +
 5 files changed, 55 insertions(+), 18 deletions(-)

diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 023efbaf09..fa2bfbfb72 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -76,7 +76,7 @@ static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
 static bool check_equivalence_delay(PlannerInfo *root,
 									RestrictInfo *restrictinfo);
 static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
-static void check_mergejoinable(RestrictInfo *restrictinfo);
+static void check_btreeable(RestrictInfo *restrictinfo);
 static void check_hashjoinable(RestrictInfo *restrictinfo);
 static void check_memoizable(RestrictInfo *restrictinfo);
 
@@ -1874,8 +1874,11 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 	 * We check "mergejoinability" of every clause, not only join clauses,
 	 * because we want to know about equivalences between vars of the same
 	 * relation, or between vars and consts.
+	 *
+	 * We also checked the btree-able properity at the same round of checking
+	 * mergejoinability to support ec filter function.
 	 */
-	check_mergejoinable(restrictinfo);
+	check_btreeable(restrictinfo);
 
 	/*
 	 * If it is a true equivalence clause, send it to the EquivalenceClass
@@ -2389,7 +2392,7 @@ process_implied_equality(PlannerInfo *root,
 	 * from an EquivalenceClass; but we could have reduced the original clause
 	 * to a constant.
 	 */
-	check_mergejoinable(restrictinfo);
+	check_btreeable(restrictinfo);
 
 	/*
 	 * Note we don't do initialize_mergeclause_eclasses(); the caller can
@@ -2456,8 +2459,8 @@ build_implied_join_equality(PlannerInfo *root,
 									 NULL,	/* outer_relids */
 									 nullable_relids);	/* nullable_relids */
 
-	/* Set mergejoinability/hashjoinability flags */
-	check_mergejoinable(restrictinfo);
+	/* Set btreeability/hashjoinability flags */
+	check_btreeable(restrictinfo);
 	check_hashjoinable(restrictinfo);
 	check_memoizable(restrictinfo);
 
@@ -2641,20 +2644,16 @@ match_foreign_keys_to_quals(PlannerInfo *root)
  *****************************************************************************/
 
 /*
- * check_mergejoinable
- *	  If the restrictinfo's clause is mergejoinable, set the mergejoin
- *	  info fields in the restrictinfo.
- *
- *	  Currently, we support mergejoin for binary opclauses where
- *	  the operator is a mergejoinable operator.  The arguments can be
- *	  anything --- as long as there are no volatile functions in them.
+ * check_btreeable
+ *	  If the restrictinfo's clause is btreeable, set the mergejoin
+ *	  info field and btreeineq info field in the restrictinfo. btreeable
+ *	  now is a superset of mergeable.
  */
 static void
-check_mergejoinable(RestrictInfo *restrictinfo)
+check_btreeable(RestrictInfo *restrictinfo)
 {
 	Expr	   *clause = restrictinfo->clause;
 	Oid			opno;
-	Node	   *leftarg;
 
 	if (restrictinfo->pseudoconstant)
 		return;
@@ -2664,11 +2663,11 @@ check_mergejoinable(RestrictInfo *restrictinfo)
 		return;
 
 	opno = ((OpExpr *) clause)->opno;
-	leftarg = linitial(((OpExpr *) clause)->args);
 
-	if (op_mergejoinable(opno, exprType(leftarg)) &&
-		!contain_volatile_functions((Node *) restrictinfo))
-		restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
+	if (!contain_volatile_functions((Node *) restrictinfo))
+		get_btree_opfamilies(opno,
+							 &restrictinfo->mergeopfamilies,
+							 &restrictinfo->btreeineqopfamilies);
 
 	/*
 	 * Note: op_mergejoinable is just a hint; if we fail to find the operator
diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c
index ef8df3d098..e09196d26f 100644
--- a/src/backend/optimizer/util/restrictinfo.c
+++ b/src/backend/optimizer/util/restrictinfo.c
@@ -201,6 +201,7 @@ make_restrictinfo_internal(PlannerInfo *root,
 	restrictinfo->outer_selec = -1;
 
 	restrictinfo->mergeopfamilies = NIL;
+	restrictinfo->btreeineqopfamilies = NIL;
 
 	restrictinfo->left_ec = NULL;
 	restrictinfo->right_ec = NULL;
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 1b7e11b93e..91cd813ce8 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -389,6 +389,41 @@ get_mergejoin_opfamilies(Oid opno)
 	return result;
 }
 
+/*
+ * TODO:  get_mergejoin_opfamilies shoud be replaced with this function.
+ */
+void
+get_btree_opfamilies(Oid opno,
+					 List **mergeable_opfamilies,
+					 List **unmergeable_btree_opfamilies)
+{
+	CatCList   *catlist;
+	int			i;
+
+	/*
+	 * Search pg_amop to see find out all the btree opfamilies.
+	 */
+	catlist = SearchSysCacheList1(AMOPOPID, ObjectIdGetDatum(opno));
+
+	for (i = 0; i < catlist->n_members; i++)
+	{
+		HeapTuple	tuple = &catlist->members[i]->tuple;
+		Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple);
+
+		if (aform->amopmethod == BTREE_AM_OID)
+		{
+			if (aform->amopstrategy == BTEqualStrategyNumber)
+				*mergeable_opfamilies = lappend_oid(*mergeable_opfamilies,
+													aform->amopfamily);
+			else
+				*unmergeable_btree_opfamilies = lappend_oid(*unmergeable_btree_opfamilies,
+															aform->amopfamily);
+		}
+	}
+
+	ReleaseSysCacheList(catlist);
+}
+
 /*
  * get_compatible_hash_operators
  *		Get the OID(s) of hash equality operator(s) compatible with the given
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index b88cfb8dc0..f407f1852d 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2305,6 +2305,7 @@ typedef struct RestrictInfo
 	 * mergejoinable, else NIL
 	 */
 	List	   *mergeopfamilies;
+	List		*btreeineqopfamilies; /* btree families except the mergeable ones */
 
 	/*
 	 * cache space for mergeclause processing; NULL if not yet set
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index b8dd27d4a9..5b5fac0397 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -79,6 +79,7 @@ extern bool get_ordering_op_properties(Oid opno,
 extern Oid	get_equality_op_for_ordering_op(Oid opno, bool *reverse);
 extern Oid	get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type);
 extern List *get_mergejoin_opfamilies(Oid opno);
+extern void get_btree_opfamilies(Oid opno, List **mergeable_opfamilies, List **unmergeable_btree_opfamilies);
 extern bool get_compatible_hash_operators(Oid opno,
 										  Oid *lhs_opno, Oid *rhs_opno);
 extern bool get_op_hash_functions(Oid opno,
-- 
2.37.0

From e67d5767ae85606f99d696874d53388bac6543b7 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 6 Jul 2022 15:36:19 +0300
Subject: [PATCH 2/6] Introudce ec_filters in EquivalenceClass struct, the
 semantics is the quals can be applied to any EquivalenceMember in this EC.
 Later this information is used to generate new RestrictInfo and was
 distributed to related RelOptInfo very soon.

There are 3 major steps here:
a). In distribute_qual_to_rels to gather the ineq quallist.
b). After deconstruct_jointree, distribute_filter_quals_to_eclass distribute
these ineq-quallist to the related EC's ef_filters.
c). generate_base_implied_equalities_no_const scan the ec_filters and distriubte
the restrictinfo to related RelOptInfo.

Author: David Rowley at 2015-12 [1]
Andy Fan rebases this patch to current latest code.
---
 .../postgres_fdw/expected/postgres_fdw.out    |  36 ++--
 src/backend/nodes/outfuncs.c                  |  14 ++
 src/backend/optimizer/path/equivclass.c       | 182 ++++++++++++++++++
 src/backend/optimizer/plan/initsplan.c        |  96 +++++++--
 src/backend/utils/cache/lsyscache.c           |  28 +++
 src/include/nodes/nodes.h                     |   1 +
 src/include/nodes/pathnodes.h                 |  37 ++++
 src/include/optimizer/paths.h                 |   1 +
 src/include/utils/lsyscache.h                 |   1 +
 src/test/regress/expected/equivclass.out      |  45 ++++-
 src/test/regress/expected/join.out            |  22 +--
 src/test/regress/expected/merge.out           |  16 +-
 src/test/regress/expected/partition_join.out  |  43 +++--
 src/test/regress/sql/equivclass.sql           |  12 ++
 14 files changed, 460 insertions(+), 74 deletions(-)

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 44457f930c..2758049f5b 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -1545,12 +1545,12 @@ SELECT t1.c1, ss.a, ss.b FROM (SELECT c1 FROM "S 1"."T 3" WHERE c1 = 50) t1 INNE
 -- full outer join + inner join
 EXPLAIN (VERBOSE, COSTS OFF)
 SELECT t1.c1, t2.c1, t3.c1 FROM ft4 t1 INNER JOIN ft5 t2 ON (t1.c1 = t2.c1 + 1 and t1.c1 between 50 and 60) FULL JOIN ft4 t3 ON (t2.c1 = t3.c1) ORDER BY t1.c1, t2.c1, t3.c1 LIMIT 10;
-                                                                                                                                                 QUERY PLAN                                                                                                                                                 
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                                                                                                                                           QUERY PLAN                                                                                                                                                                           
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Foreign Scan
    Output: t1.c1, t2.c1, t3.c1
    Relations: ((public.ft4 t1) INNER JOIN (public.ft5 t2)) FULL JOIN (public.ft4 t3)
-   Remote SQL: SELECT r1.c1, r2.c1, r4.c1 FROM (("S 1"."T 3" r1 INNER JOIN "S 1"."T 4" r2 ON (((r1.c1 = (r2.c1 + 1))) AND ((r1.c1 >= 50)) AND ((r1.c1 <= 60)))) FULL JOIN "S 1"."T 3" r4 ON (((r2.c1 = r4.c1)))) ORDER BY r1.c1 ASC NULLS LAST, r2.c1 ASC NULLS LAST, r4.c1 ASC NULLS LAST LIMIT 10::bigint
+   Remote SQL: SELECT r1.c1, r2.c1, r4.c1 FROM (("S 1"."T 3" r1 INNER JOIN "S 1"."T 4" r2 ON (((r1.c1 = (r2.c1 + 1))) AND (((r2.c1 + 1) >= 50)) AND (((r2.c1 + 1) <= 60)) AND ((r1.c1 >= 50)) AND ((r1.c1 <= 60)))) FULL JOIN "S 1"."T 3" r4 ON (((r2.c1 = r4.c1)))) ORDER BY r1.c1 ASC NULLS LAST, r2.c1 ASC NULLS LAST, r4.c1 ASC NULLS LAST LIMIT 10::bigint
 (4 rows)
 
 SELECT t1.c1, t2.c1, t3.c1 FROM ft4 t1 INNER JOIN ft5 t2 ON (t1.c1 = t2.c1 + 1 and t1.c1 between 50 and 60) FULL JOIN ft4 t3 ON (t2.c1 = t3.c1) ORDER BY t1.c1, t2.c1, t3.c1 LIMIT 10;
@@ -2335,12 +2335,12 @@ SELECT ft4.c1, q.* FROM ft4 LEFT JOIN (SELECT 13, ft1.c1, ft2.c1 FROM ft1 RIGHT
 UPDATE ft5 SET c3 = null where c1 % 9 = 0;
 EXPLAIN (VERBOSE, COSTS OFF)
 SELECT ft5, ft5.c1, ft5.c2, ft5.c3, ft4.c1, ft4.c2 FROM ft5 left join ft4 on ft5.c1 = ft4.c1 WHERE ft4.c1 BETWEEN 10 and 30 ORDER BY ft5.c1, ft4.c1;
-                                                                                                                                QUERY PLAN                                                                                                                                 
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                                                                                                                    QUERY PLAN                                                                                                                                                     
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Foreign Scan
    Output: ft5.*, ft5.c1, ft5.c2, ft5.c3, ft4.c1, ft4.c2
    Relations: (public.ft5) INNER JOIN (public.ft4)
-   Remote SQL: SELECT CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1.c1, r1.c2, r1.c3) END, r1.c1, r1.c2, r1.c3, r2.c1, r2.c2 FROM ("S 1"."T 4" r1 INNER JOIN "S 1"."T 3" r2 ON (((r1.c1 = r2.c1)) AND ((r2.c1 >= 10)) AND ((r2.c1 <= 30)))) ORDER BY r1.c1 ASC NULLS LAST
+   Remote SQL: SELECT CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1.c1, r1.c2, r1.c3) END, r1.c1, r1.c2, r1.c3, r2.c1, r2.c2 FROM ("S 1"."T 4" r1 INNER JOIN "S 1"."T 3" r2 ON (((r1.c1 = r2.c1)) AND ((r2.c1 >= 10)) AND ((r2.c1 <= 30)) AND ((r1.c1 >= 10)) AND ((r1.c1 <= 30)))) ORDER BY r1.c1 ASC NULLS LAST
 (4 rows)
 
 SELECT ft5, ft5.c1, ft5.c2, ft5.c3, ft4.c1, ft4.c2 FROM ft5 left join ft4 on ft5.c1 = ft4.c1 WHERE ft4.c1 BETWEEN 10 and 30 ORDER BY ft5.c1, ft4.c1;
@@ -2362,8 +2362,8 @@ SET enable_hashjoin TO false;
 EXPLAIN (VERBOSE, COSTS OFF)
 SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = ft4.c1
     AND ft1.c2 = ft5.c1 AND ft1.c2 = local_tbl.c1 AND ft1.c1 < 100 AND ft2.c1 < 100 FOR UPDATE;
-                                                                                                                                                                                                                                                                                                                                                                                                                                               QUERY PLAN                                                                                                                                                                                                                                                                                                                                                                                                                                               
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                                                                                                                                                                                                                                                                                                                                                                                                                                      QUERY PLAN                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  LockRows
    Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft4.c1, ft4.c2, ft4.c3, ft5.c1, ft5.c2, ft5.c3, local_tbl.c1, local_tbl.c2, local_tbl.c3, ft1.*, ft2.*, ft4.*, ft5.*, local_tbl.ctid
    ->  Merge Join
@@ -2373,7 +2373,7 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f
          ->  Foreign Scan
                Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.*, ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.*, ft4.c1, ft4.c2, ft4.c3, ft4.*, ft5.c1, ft5.c2, ft5.c3, ft5.*
                Relations: (((public.ft1) INNER JOIN (public.ft2)) INNER JOIN (public.ft4)) INNER JOIN (public.ft5)
-               Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END, r3.c1, r3.c2, r3.c3, CASE WHEN (r3.*)::text IS NOT NULL THEN ROW(r3.c1, r3.c2, r3.c3) END, r4.c1, r4.c2, r4.c3, CASE WHEN (r4.*)::text IS NOT NULL THEN ROW(r4.c1, r4.c2, r4.c3) END FROM ((("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")) AND ((r2."C 1" < 100)) AND ((r1."C 1" < 100)))) INNER JOIN "S 1"."T 3" r3 ON (((r1.c2 = r3.c1)))) INNER JOIN "S 1"."T 4" r4 ON (((r1.c2 = r4.c1)))) ORDER BY r1.c2 ASC NULLS LAST FOR UPDATE OF r1 FOR UPDATE OF r2 FOR UPDATE OF r3 FOR UPDATE OF r4
+               Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END, r3.c1, r3.c2, r3.c3, CASE WHEN (r3.*)::text IS NOT NULL THEN ROW(r3.c1, r3.c2, r3.c3) END, r4.c1, r4.c2, r4.c3, CASE WHEN (r4.*)::text IS NOT NULL THEN ROW(r4.c1, r4.c2, r4.c3) END FROM ((("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")) AND ((r2."C 1" < 100)) AND ((r2."C 1" < 100)) AND ((r1."C 1" < 100)) AND ((r1."C 1" < 100)))) INNER JOIN "S 1"."T 3" r3 ON (((r1.c2 = r3.c1)))) INNER JOIN "S 1"."T 4" r4 ON (((r1.c2 = r4.c1)))) ORDER BY r1.c2 ASC NULLS LAST FOR UPDATE OF r1 FOR UPDATE OF r2 FOR UPDATE OF r3 FOR UPDATE OF r4
                ->  Merge Join
                      Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.*, ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.*, ft4.c1, ft4.c2, ft4.c3, ft4.*, ft5.c1, ft5.c2, ft5.c3, ft5.*
                      Merge Cond: (ft1.c2 = ft5.c1)
@@ -2391,12 +2391,12 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f
                                              Sort Key: ft1.c1
                                              ->  Foreign Scan on public.ft1
                                                    Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.*
-                                                   Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE
+                                                   Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND (("C 1" < 100)) FOR UPDATE
                                        ->  Materialize
                                              Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.*
                                              ->  Foreign Scan on public.ft2
                                                    Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.*
-                                                   Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE
+                                                   Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND (("C 1" < 100)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE
                            ->  Sort
                                  Output: ft4.c1, ft4.c2, ft4.c3, ft4.*
                                  Sort Key: ft4.c1
@@ -5705,25 +5705,25 @@ UPDATE ft2 AS target SET (c2) = (
 EXPLAIN (VERBOSE, COSTS OFF)
 UPDATE ft2 d SET c2 = CASE WHEN random() >= 0 THEN d.c2 ELSE 0 END
   FROM ft2 AS t WHERE d.c1 = t.c1 AND d.c1 > 1000;
-                                                                                                                                                                                       QUERY PLAN                                                                                                                                                                                        
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                                                                                                                                                                   QUERY PLAN                                                                                                                                                                                                    
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Update on public.ft2 d
    Remote SQL: UPDATE "S 1"."T 1" SET c2 = $2 WHERE ctid = $1
    ->  Foreign Scan
          Output: CASE WHEN (random() >= '0'::double precision) THEN d.c2 ELSE 0 END, d.ctid, d.*, t.*
          Relations: (public.ft2 d) INNER JOIN (public.ft2 t)
-         Remote SQL: SELECT r1.c2, r1.ctid, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")) AND ((r1."C 1" > 1000)))) FOR UPDATE OF r1
-         ->  Hash Join
+         Remote SQL: SELECT r1.c2, r1.ctid, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")) AND ((r2."C 1" > 1000)) AND ((r1."C 1" > 1000)))) FOR UPDATE OF r1
+         ->  Merge Join
                Output: d.c2, d.ctid, d.*, t.*
-               Hash Cond: (d.c1 = t.c1)
+               Merge Cond: (d.c1 = t.c1)
                ->  Foreign Scan on public.ft2 d
                      Output: d.c2, d.ctid, d.*, d.c1
                      Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8, ctid FROM "S 1"."T 1" WHERE (("C 1" > 1000)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE
-               ->  Hash
+               ->  Materialize
                      Output: t.*, t.c1
                      ->  Foreign Scan on public.ft2 t
                            Output: t.*, t.c1
-                           Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1"
+                           Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" > 1000)) ORDER BY "C 1" ASC NULLS LAST
 (17 rows)
 
 UPDATE ft2 d SET c2 = CASE WHEN random() >= 0 THEN d.c2 ELSE 0 END
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 05f27f044b..b19462c758 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2665,6 +2665,17 @@ _outEquivalenceMember(StringInfo str, const EquivalenceMember *node)
 	WRITE_OID_FIELD(em_datatype);
 }
 
+static void
+_outEquivalenceFilter(StringInfo str, const EquivalenceFilter *node)
+{
+	WRITE_NODE_TYPE("EQUIVALENCEFILTER");
+
+	WRITE_NODE_FIELD(ef_const);
+	WRITE_OID_FIELD(ef_opno);
+	WRITE_BOOL_FIELD(ef_const_is_left);
+	WRITE_UINT_FIELD(ef_source_rel);
+}
+
 static void
 _outPathKey(StringInfo str, const PathKey *node)
 {
@@ -4496,6 +4507,9 @@ outNode(StringInfo str, const void *obj)
 			case T_EquivalenceMember:
 				_outEquivalenceMember(str, obj);
 				break;
+			case T_EquivalenceFilter:
+				_outEquivalenceFilter(str, obj);
+				break;
 			case T_PathKey:
 				_outPathKey(str, obj);
 				break;
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 60c0e3f108..89c7f0dc39 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -19,6 +19,7 @@
 #include <limits.h>
 
 #include "access/stratnum.h"
+#include "catalog/pg_am.h"
 #include "catalog/pg_type.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
@@ -1232,6 +1233,37 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 	}
 }
 
+/*
+ * finds the opfamily and strategy number for the specified 'opno' and 'method'
+ * access method. Returns True if one is found and sets 'family' and
+ * 'amstrategy', or returns False if none are found.
+ */
+static bool
+find_am_family_and_stategy(Oid opno, Oid method, Oid *family, int *amstrategy)
+{
+	List *opfamilies;
+	ListCell *l;
+	int strategy;
+
+	opfamilies = get_opfamilies(opno, method);
+
+	foreach(l, opfamilies)
+	{
+		Oid opfamily = lfirst_oid(l);
+
+		strategy = get_op_opfamily_strategy(opno, opfamily);
+
+		if (strategy)
+		{
+			*amstrategy = strategy;
+			*family = opfamily;
+			return true;
+		}
+	}
+
+	return false;
+}
+
 /*
  * generate_base_implied_equalities when EC contains no pseudoconstants
  */
@@ -1241,6 +1273,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 {
 	EquivalenceMember **prev_ems;
 	ListCell   *lc;
+	ListCell   *lc2;
 
 	/*
 	 * We scan the EC members once and track the last-seen member for each
@@ -1302,6 +1335,57 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 				rinfo->right_em = cur_em;
 			}
 		}
+
+		/*
+		 * Also push any EquivalenceFilter clauses down into all relations
+		 * other than the one which the filter actually originated from.
+		 */
+		foreach(lc2, ec->ec_filters)
+		{
+			EquivalenceFilter *ef = (EquivalenceFilter *) lfirst(lc2);
+			Expr *leftexpr;
+			Expr *rightexpr;
+			int strategy;
+			Oid opno;
+			Oid family;
+
+			if (ef->ef_source_rel == relid)
+				continue;
+
+			if (!find_am_family_and_stategy(ef->ef_opno, BTREE_AM_OID,
+				&family, &strategy))
+				continue;
+
+			if (ef->ef_const_is_left)
+			{
+				leftexpr = (Expr *) ef->ef_const;
+				rightexpr = cur_em->em_expr;
+			}
+			else
+			{
+				leftexpr = cur_em->em_expr;
+				rightexpr = (Expr *) ef->ef_const;
+			}
+
+			opno = get_opfamily_member(family,
+										exprType((Node *) leftexpr),
+										exprType((Node *) rightexpr),
+										strategy);
+
+			if (opno == InvalidOid)
+				continue;
+
+			process_implied_equality(root, opno,
+										ec->ec_collation,
+										leftexpr,
+										rightexpr,
+										bms_copy(ec->ec_relids),
+										bms_copy(cur_em->em_nullable_relids),
+										ec->ec_min_security,
+										ec->ec_below_outer_join,
+										false);
+		}
+
 		prev_ems[relid] = cur_em;
 	}
 
@@ -1883,6 +1967,104 @@ create_join_clause(PlannerInfo *root,
 	return rinfo;
 }
 
+/*
+ * distribute_filter_quals_to_eclass
+ *		For each OpExpr in quallist look for an eclass which has an Expr
+ *		matching the Expr in the OpExpr. If a match is found we add a new
+ *		EquivalenceFilter to the eclass containing the filter details.
+ */
+void
+distribute_filter_quals_to_eclass(PlannerInfo *root, List *quallist)
+{
+	ListCell *l;
+
+	/* fast path for when no eclasses have been generated */
+	if (root->eq_classes == NIL)
+		return;
+
+	/*
+	 * For each qual in quallist try and find an eclass which contains the
+	 * non-Const part of the OpExpr. We'll tag any matches that we find onto
+	 * the correct eclass.
+	 */
+	foreach(l, quallist)
+	{
+		OpExpr	   *opexpr = (OpExpr *) lfirst(l);
+		Expr	   *leftexpr = (Expr *) linitial(opexpr->args);
+		Expr	   *rightexpr = (Expr *) lsecond(opexpr->args);
+		Const	   *constexpr;
+		Expr	   *varexpr;
+		Relids		exprrels;
+		int			relid;
+		bool		const_isleft;
+		ListCell *l2;
+
+		/*
+		 * Determine if the the OpExpr is in the form "expr op const" or
+		 * "const op expr".
+		 */
+		if (IsA(leftexpr, Const))
+		{
+			constexpr = (Const *) leftexpr;
+			varexpr = rightexpr;
+			const_isleft = true;
+		}
+		else
+		{
+			constexpr = (Const *) rightexpr;
+			varexpr = leftexpr;
+			const_isleft = false;
+		}
+
+		exprrels = pull_varnos(root, (Node *) varexpr);
+
+		/* should be filtered out, but we need to determine relid anyway */
+		if (!bms_get_singleton_member(exprrels, &relid))
+			continue;
+
+		/* search for a matching eclass member in all eclasses */
+		foreach(l2, root->eq_classes)
+		{
+			EquivalenceClass *ec = (EquivalenceClass *) lfirst(l2);
+			ListCell *l3;
+
+			if (ec->ec_broken || ec->ec_has_volatile)
+				continue;
+
+			/*
+			 * if the eclass has a const then that const will serve as the
+			 * filter, we needn't add any others.
+			 */
+			if (ec->ec_has_const)
+				continue;
+
+			/* skip this eclass no members exist which belong to this relid */
+			if (!bms_is_member(relid, ec->ec_relids))
+				continue;
+
+			foreach(l3, ec->ec_members)
+			{
+				EquivalenceMember *em = (EquivalenceMember *) lfirst(l3);
+
+				if (!bms_is_member(relid, em->em_relids))
+					continue;
+
+				if (equal(em->em_expr, varexpr))
+				{
+					EquivalenceFilter *efilter;
+					efilter = makeNode(EquivalenceFilter);
+					efilter->ef_const = (Const *) copyObject(constexpr);
+					efilter->ef_const_is_left = const_isleft;
+					efilter->ef_opno = opexpr->opno;
+					efilter->ef_source_rel = relid;
+
+					ec->ec_filters = lappend(ec->ec_filters, efilter);
+					break;		/* Onto the next eclass */
+				}
+			}
+		}
+	}
+}
 
 /*
  * reconsider_outer_join_clauses
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index fa2bfbfb72..f86276b667 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -53,7 +53,7 @@ static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
 static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
 								 bool below_outer_join,
 								 Relids *qualscope, Relids *inner_join_rels,
-								 List **postponed_qual_list);
+								 List **postponed_qual_list, List **filter_qual_list);
 static void process_security_barrier_quals(PlannerInfo *root,
 										   int rti, Relids qualscope,
 										   bool below_outer_join);
@@ -70,7 +70,8 @@ static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 									Relids qualscope,
 									Relids ojscope,
 									Relids outerjoin_nonnullable,
-									List **postponed_qual_list);
+									List **postponed_qual_list,
+									List **filter_qual_list);
 static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
 								  Relids *nullable_relids_p, bool is_pushed_down);
 static bool check_equivalence_delay(PlannerInfo *root,
@@ -650,6 +651,43 @@ create_lateral_join_info(PlannerInfo *root)
 	}
 }
 
+/*
+ * is_simple_filter_qual
+ *             Analyzes an OpExpr to determine if it may be useful as an
+ *             EquivalenceFilter. Returns true if the OpExpr may be of some use, or
+ *             false if it should not be used.
+ */
+static bool
+is_simple_filter_qual(PlannerInfo *root, OpExpr *expr)
+{
+	Expr *leftexpr;
+	Expr *rightexpr;
+
+	if (!IsA(expr, OpExpr))
+			return false;
+
+	if (list_length(expr->args) != 2)
+			return false;
+
+	leftexpr = (Expr *) linitial(expr->args);
+	rightexpr = (Expr *) lsecond(expr->args);
+
+	/* XXX should we restrict these to simple Var op Const expressions? */
+	if (IsA(leftexpr, Const))
+	{
+		if (bms_membership(pull_varnos(root, (Node *) rightexpr)) == BMS_SINGLETON &&
+			!contain_volatile_functions((Node *) rightexpr))
+			return true;
+	}
+	else if (IsA(rightexpr, Const))
+	{
+		if (bms_membership(pull_varnos(root, (Node *) leftexpr)) == BMS_SINGLETON &&
+			!contain_volatile_functions((Node *) leftexpr))
+			return true;
+	}
+
+	return false;
+}
 
 /*****************************************************************************
  *
@@ -690,6 +728,7 @@ deconstruct_jointree(PlannerInfo *root)
 	Relids		qualscope;
 	Relids		inner_join_rels;
 	List	   *postponed_qual_list = NIL;
+	List	   *filter_qual_list = NIL;
 
 	/* Start recursion at top of jointree */
 	Assert(root->parse->jointree != NULL &&
@@ -700,11 +739,14 @@ deconstruct_jointree(PlannerInfo *root)
 
 	result = deconstruct_recurse(root, (Node *) root->parse->jointree, false,
 								 &qualscope, &inner_join_rels,
-								 &postponed_qual_list);
+								 &postponed_qual_list, &filter_qual_list);
 
 	/* Shouldn't be any leftover quals */
 	Assert(postponed_qual_list == NIL);
 
+	/* try and match each filter_qual_list item up with an eclass. */
+	distribute_filter_quals_to_eclass(root, filter_qual_list);
+
 	return result;
 }
 
@@ -725,6 +767,8 @@ deconstruct_jointree(PlannerInfo *root)
  *		or free this, either)
  *	*postponed_qual_list is a list of PostponedQual structs, which we can
  *		add quals to if they turn out to belong to a higher join level
+ *	*filter_qual_list is appended to with a list of quals which may be useful
+ *		include as EquivalenceFilters.
  *	Return value is the appropriate joinlist for this jointree node
  *
  * In addition, entries will be added to root->join_info_list for outer joins.
@@ -732,7 +776,7 @@ deconstruct_jointree(PlannerInfo *root)
 static List *
 deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 					Relids *qualscope, Relids *inner_join_rels,
-					List **postponed_qual_list)
+					List **postponed_qual_list, List **filter_qual_list)
 {
 	List	   *joinlist;
 
@@ -785,7 +829,8 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 											   below_outer_join,
 											   &sub_qualscope,
 											   inner_join_rels,
-											   &child_postponed_quals);
+											   &child_postponed_quals,
+											   filter_qual_list);
 			*qualscope = bms_add_members(*qualscope, sub_qualscope);
 			sub_members = list_length(sub_joinlist);
 			remaining--;
@@ -819,7 +864,8 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 										below_outer_join, JOIN_INNER,
 										root->qual_security_level,
 										*qualscope, NULL, NULL,
-										NULL);
+										NULL,
+										filter_qual_list);
 			else
 				*postponed_qual_list = lappend(*postponed_qual_list, pq);
 		}
@@ -835,7 +881,8 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 									below_outer_join, JOIN_INNER,
 									root->qual_security_level,
 									*qualscope, NULL, NULL,
-									postponed_qual_list);
+									postponed_qual_list,
+									filter_qual_list);
 		}
 	}
 	else if (IsA(jtnode, JoinExpr))
@@ -873,11 +920,13 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 				leftjoinlist = deconstruct_recurse(root, j->larg,
 												   below_outer_join,
 												   &leftids, &left_inners,
-												   &child_postponed_quals);
+												   &child_postponed_quals,
+												   filter_qual_list);
 				rightjoinlist = deconstruct_recurse(root, j->rarg,
 													below_outer_join,
 													&rightids, &right_inners,
-													&child_postponed_quals);
+													&child_postponed_quals,
+													filter_qual_list);
 				*qualscope = bms_union(leftids, rightids);
 				*inner_join_rels = *qualscope;
 				/* Inner join adds no restrictions for quals */
@@ -890,11 +939,13 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 				leftjoinlist = deconstruct_recurse(root, j->larg,
 												   below_outer_join,
 												   &leftids, &left_inners,
-												   &child_postponed_quals);
+												   &child_postponed_quals,
+												   filter_qual_list);
 				rightjoinlist = deconstruct_recurse(root, j->rarg,
 													true,
 													&rightids, &right_inners,
-													&child_postponed_quals);
+													&child_postponed_quals,
+													filter_qual_list);
 				*qualscope = bms_union(leftids, rightids);
 				*inner_join_rels = bms_union(left_inners, right_inners);
 				nonnullable_rels = leftids;
@@ -904,11 +955,13 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 				leftjoinlist = deconstruct_recurse(root, j->larg,
 												   below_outer_join,
 												   &leftids, &left_inners,
-												   &child_postponed_quals);
+												   &child_postponed_quals,
+												   filter_qual_list);
 				rightjoinlist = deconstruct_recurse(root, j->rarg,
 													below_outer_join,
 													&rightids, &right_inners,
-													&child_postponed_quals);
+													&child_postponed_quals,
+													filter_qual_list);
 				*qualscope = bms_union(leftids, rightids);
 				*inner_join_rels = bms_union(left_inners, right_inners);
 				/* Semi join adds no restrictions for quals */
@@ -925,11 +978,13 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 				leftjoinlist = deconstruct_recurse(root, j->larg,
 												   true,
 												   &leftids, &left_inners,
-												   &child_postponed_quals);
+												   &child_postponed_quals,
+												   filter_qual_list);
 				rightjoinlist = deconstruct_recurse(root, j->rarg,
 													true,
 													&rightids, &right_inners,
-													&child_postponed_quals);
+													&child_postponed_quals,
+													filter_qual_list);
 				*qualscope = bms_union(leftids, rightids);
 				*inner_join_rels = bms_union(left_inners, right_inners);
 				/* each side is both outer and inner */
@@ -1013,7 +1068,8 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
 									root->qual_security_level,
 									*qualscope,
 									ojscope, nonnullable_rels,
-									postponed_qual_list);
+									postponed_qual_list,
+									filter_qual_list);
 		}
 
 		/* Now we can add the SpecialJoinInfo to join_info_list */
@@ -1117,6 +1173,7 @@ process_security_barrier_quals(PlannerInfo *root,
 									qualscope,
 									qualscope,
 									NULL,
+									NULL,
 									NULL);
 		}
 		security_level++;
@@ -1610,7 +1667,8 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 						Relids qualscope,
 						Relids ojscope,
 						Relids outerjoin_nonnullable,
-						List **postponed_qual_list)
+						List **postponed_qual_list,
+						List **filter_qual_list)
 {
 	Relids		relids;
 	bool		is_pushed_down;
@@ -1967,6 +2025,10 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 
 	/* No EC special case applies, so push it into the clause lists */
 	distribute_restrictinfo_to_rels(root, restrictinfo);
+
+	/* Check if the qual looks useful to harvest as an EquivalenceFilter */
+	if (filter_qual_list != NULL && is_simple_filter_qual(root, (OpExpr *) clause))
+		*filter_qual_list = lappend(*filter_qual_list, clause);
 }
 
 /*
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 91cd813ce8..b0243925e4 100644
--- a/src/backend/utils/cache/lsyscache.c
+++ b/src/backend/utils/cache/lsyscache.c
@@ -341,6 +341,34 @@ get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type)
 	return result;
 }
 
+/*
+ * get_opfamilies
+ *		Returns a list of Oids of each opfamily which 'opno' belonging to
+ *		'method' access method.
+ */
+List *
+get_opfamilies(Oid opno, Oid method)
+{
+	List	   *result = NIL;
+	CatCList   *catlist;
+	int			i;
+
+	catlist = SearchSysCacheList1(AMOPOPID, ObjectIdGetDatum(opno));
+
+	for (i = 0; i < catlist->n_members; i++)
+	{
+		HeapTuple	tuple = &catlist->members[i]->tuple;
+		Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple);
+
+		if (aform->amopmethod == method)
+			result = lappend_oid(result, aform->amopfamily);
+	}
+
+	ReleaseSysCacheList(catlist);
+
+	return result;
+}
+
 /*
  * get_mergejoin_opfamilies
  *		Given a putatively mergejoinable operator, return a list of the OIDs
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index 7ce1fc4deb..ba879ab3e9 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -277,6 +277,7 @@ typedef enum NodeTag
 	T_LimitPath,
 	/* these aren't subclasses of Path: */
 	T_EquivalenceClass,
+	T_EquivalenceFilter,
 	T_EquivalenceMember,
 	T_PathKey,
 	T_PathKeyInfo,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index f407f1852d..f80b47ae2c 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1132,6 +1132,7 @@ typedef struct EquivalenceClass
 	List	   *ec_members;		/* list of EquivalenceMembers */
 	List	   *ec_sources;		/* list of generating RestrictInfos */
 	List	   *ec_derives;		/* list of derived RestrictInfos */
+	List	   *ec_filters;
 	Relids		ec_relids;		/* all relids appearing in ec_members, except
 								 * for child members (see below) */
 	bool		ec_has_const;	/* any pseudoconstants in ec_members? */
@@ -1144,6 +1145,42 @@ typedef struct EquivalenceClass
 	struct EquivalenceClass *ec_merged; /* set if merged into another EC */
 } EquivalenceClass;
 
+/*
+ * EquivalenceFilter - List of filters on Consts which belong to the
+ * EquivalenceClass.
+ *
+ * When building the equivalence classes we also collected a list of quals in
+ * the form of; "Expr op Const" and "Const op Expr". These are collected in the
+ * hope that we'll later generate an equivalence class which contains the
+ * "Expr" part. For example, if we parse a query such as;
+ *
+ *		SELECT * FROM t1 INNER JOIN t2 ON t1.id = t2.id WHERE t1.id < 10;
+ *
+ * then since we'll end up with an equivalence class containing {t1.id,t2.id},
+ * we'll tag the "< 10" filter onto the eclass. We are able to do this because
+ * the eclass proves equality between each class member, therefore all members
+ * must be below 10.
+ *
+ * EquivalenceFilters store the details required to allow us to push these
+ * filter clauses down into other relations which share an equivalence class
+ * containing a member which matches the expression of this EquivalenceFilter.
+ *
+ * ef_const is the Const value which this filter should filter against.
+ * ef_opno is the operator to filter on.
+ * ef_const_is_left marks if the OpExpr was in the form "Const op Expr" or
+ * "Expr op Const".
+ * ef_source_rel is the relation id of where this qual originated from.
+ */
+typedef struct EquivalenceFilter
+{
+	NodeTag		type;
+
+	Const	   *ef_const;		/* the constant expression to filter on */
+	Oid			ef_opno;		/* Operator Oid of filter operator */
+	bool		ef_const_is_left; /* Is the Const on the left of the OpExrp? */
+	Index		ef_source_rel;	/* relid of originating relation. */
+} EquivalenceFilter;
+
 /*
  * If an EC contains a const and isn't below-outer-join, any PathKey depending
  * on it must be redundant, since there's only one possible value of the key.
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index b6e137cf83..79553778cd 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -127,6 +127,7 @@ extern bool process_equivalence(PlannerInfo *root,
 extern Expr *canonicalize_ec_expression(Expr *expr,
 										Oid req_type, Oid req_collation);
 extern void reconsider_outer_join_clauses(PlannerInfo *root);
+extern void distribute_filter_quals_to_eclass(PlannerInfo *root, List *quallist);
 extern EquivalenceClass *get_eclass_for_sort_expr(PlannerInfo *root,
 												  Expr *expr,
 												  Relids nullable_relids,
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index 5b5fac0397..e0ed28f330 100644
--- a/src/include/utils/lsyscache.h
+++ b/src/include/utils/lsyscache.h
@@ -78,6 +78,7 @@ extern bool get_ordering_op_properties(Oid opno,
 									   Oid *opfamily, Oid *opcintype, int16 *strategy);
 extern Oid	get_equality_op_for_ordering_op(Oid opno, bool *reverse);
 extern Oid	get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type);
+extern List *get_opfamilies(Oid opno, Oid method);
 extern List *get_mergejoin_opfamilies(Oid opno);
 extern void get_btree_opfamilies(Oid opno, List **mergeable_opfamilies, List **unmergeable_btree_opfamilies);
 extern bool get_compatible_hash_operators(Oid opno,
diff --git a/src/test/regress/expected/equivclass.out b/src/test/regress/expected/equivclass.out
index 126f7047fe..92fcec1158 100644
--- a/src/test/regress/expected/equivclass.out
+++ b/src/test/regress/expected/equivclass.out
@@ -407,14 +407,14 @@ set session authorization regress_user_ectest;
 explain (costs off)
   select * from ec0 a, ec1 b
   where a.ff = b.ff and a.ff = 43::bigint::int8alias1;
-                 QUERY PLAN                  
----------------------------------------------
+                              QUERY PLAN                              
+----------------------------------------------------------------------
  Nested Loop
    ->  Index Scan using ec0_pkey on ec0 a
          Index Cond: (ff = '43'::int8alias1)
    ->  Index Scan using ec1_pkey on ec1 b
          Index Cond: (ff = a.ff)
-         Filter: (f1 < '5'::int8alias1)
+         Filter: ((f1 < '5'::int8alias1) AND (ff = '43'::int8alias1))
 (6 rows)
 
 reset session authorization;
@@ -451,3 +451,42 @@ explain (costs off)  -- this should not require a sort
    Filter: (f1 = 'foo'::name)
 (2 rows)
 
+-- test equivalence filters
+explain (costs off)
+  select * from ec0
+  inner join ec1 on ec0.ff = ec1.ff
+  where ec0.ff between 1 and 10;
+                         QUERY PLAN                         
+------------------------------------------------------------
+ Nested Loop
+   Join Filter: (ec0.ff = ec1.ff)
+   ->  Bitmap Heap Scan on ec0
+         Recheck Cond: ((ff >= 1) AND (ff <= 10))
+         ->  Bitmap Index Scan on ec0_pkey
+               Index Cond: ((ff >= 1) AND (ff <= 10))
+   ->  Materialize
+         ->  Bitmap Heap Scan on ec1
+               Recheck Cond: ((ff >= 1) AND (ff <= 10))
+               ->  Bitmap Index Scan on ec1_pkey
+                     Index Cond: ((ff >= 1) AND (ff <= 10))
+(11 rows)
+
+explain (costs off)
+  select * from ec0
+  inner join ec1 on ec0.ff = ec1.ff
+  where ec1.ff between 1 and 10;
+                         QUERY PLAN                         
+------------------------------------------------------------
+ Nested Loop
+   Join Filter: (ec0.ff = ec1.ff)
+   ->  Bitmap Heap Scan on ec0
+         Recheck Cond: ((ff >= 1) AND (ff <= 10))
+         ->  Bitmap Index Scan on ec0_pkey
+               Index Cond: ((ff >= 1) AND (ff <= 10))
+   ->  Materialize
+         ->  Bitmap Heap Scan on ec1
+               Recheck Cond: ((ff >= 1) AND (ff <= 10))
+               ->  Bitmap Index Scan on ec1_pkey
+                     Index Cond: ((ff >= 1) AND (ff <= 10))
+(11 rows)
+
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 2538bd6a79..f173074621 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -3337,7 +3337,7 @@ where t1.unique2 < 42 and t1.stringu1 > t2.stringu2;
    Join Filter: (t1.stringu1 > t2.stringu2)
    ->  Nested Loop
          ->  Seq Scan on int4_tbl i1
-               Filter: (f1 = 0)
+               Filter: ((f1 = 0) AND (11 < 42))
          ->  Index Scan using tenk1_unique2 on tenk1 t1
                Index Cond: ((unique2 = (11)) AND (unique2 < 42))
    ->  Index Scan using tenk1_unique1 on tenk1 t2
@@ -6544,23 +6544,22 @@ where exists (select 1 from tenk1 t3
 ---------------------------------------------------------------------------------
  Nested Loop
    Output: t1.unique1, t2.hundred
-   ->  Hash Join
+   ->  Nested Loop
          Output: t1.unique1, t3.tenthous
-         Hash Cond: (t3.thousand = t1.unique1)
+         Join Filter: (t1.unique1 = t3.thousand)
+         ->  Index Only Scan using onek_unique1 on public.onek t1
+               Output: t1.unique1
+               Index Cond: (t1.unique1 < 1)
          ->  HashAggregate
                Output: t3.thousand, t3.tenthous
                Group Key: t3.thousand, t3.tenthous
                ->  Index Only Scan using tenk1_thous_tenthous on public.tenk1 t3
                      Output: t3.thousand, t3.tenthous
-         ->  Hash
-               Output: t1.unique1
-               ->  Index Only Scan using onek_unique1 on public.onek t1
-                     Output: t1.unique1
-                     Index Cond: (t1.unique1 < 1)
+                     Index Cond: (t3.thousand < 1)
    ->  Index Only Scan using tenk1_hundred on public.tenk1 t2
          Output: t2.hundred
          Index Cond: (t2.hundred = t3.tenthous)
-(18 rows)
+(17 rows)
 
 -- ... unless it actually is unique
 create table j3 as select unique1, tenthous from onek;
@@ -6578,15 +6577,16 @@ where exists (select 1 from j3
    Output: t1.unique1, t2.hundred
    ->  Nested Loop
          Output: t1.unique1, j3.tenthous
+         Join Filter: (t1.unique1 = j3.unique1)
          ->  Index Only Scan using onek_unique1 on public.onek t1
                Output: t1.unique1
                Index Cond: (t1.unique1 < 1)
          ->  Index Only Scan using j3_unique1_tenthous_idx on public.j3
                Output: j3.unique1, j3.tenthous
-               Index Cond: (j3.unique1 = t1.unique1)
+               Index Cond: (j3.unique1 < 1)
    ->  Index Only Scan using tenk1_hundred on public.tenk1 t2
          Output: t2.hundred
          Index Cond: (t2.hundred = j3.tenthous)
-(13 rows)
+(14 rows)
 
 drop table j3;
diff --git a/src/test/regress/expected/merge.out b/src/test/regress/expected/merge.out
index af670e28e7..ab3a711d61 100644
--- a/src/test/regress/expected/merge.out
+++ b/src/test/regress/expected/merge.out
@@ -1437,17 +1437,17 @@ SELECT explain_merge('
 MERGE INTO ex_mtarget t USING ex_msource s ON t.a = s.a AND t.a < -1000
 WHEN MATCHED AND t.a < 10 THEN
 	DO NOTHING');
-                           explain_merge                            
---------------------------------------------------------------------
+                        explain_merge                         
+--------------------------------------------------------------
  Merge on ex_mtarget t (actual rows=0 loops=1)
    ->  Hash Join (actual rows=0 loops=1)
-         Hash Cond: (s.a = t.a)
-         ->  Seq Scan on ex_msource s (actual rows=1 loops=1)
-         ->  Hash (actual rows=0 loops=1)
-               Buckets: xxx  Batches: xxx  Memory Usage: xxx
-               ->  Seq Scan on ex_mtarget t (actual rows=0 loops=1)
+         Hash Cond: (t.a = s.a)
+         ->  Seq Scan on ex_mtarget t (actual rows=0 loops=1)
+               Filter: (a < '-1000'::integer)
+               Rows Removed by Filter: 54
+         ->  Hash (never executed)
+               ->  Seq Scan on ex_msource s (never executed)
                      Filter: (a < '-1000'::integer)
-                     Rows Removed by Filter: 54
 (9 rows)
 
 DROP TABLE ex_msource, ex_mtarget;
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 03926a8413..3be9a2bed5 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -186,17 +186,17 @@ SELECT t1.a, t1.c, t2.b, t2.c FROM (SELECT 50 phv, * FROM prt1 WHERE prt1.b = 0)
 -- Join with pruned partitions from joining relations
 EXPLAIN (COSTS OFF)
 SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.b AND t1.a < 450 AND t2.b > 250 AND t1.b = 0 ORDER BY t1.a, t2.b;
-                     QUERY PLAN                      
------------------------------------------------------
+                            QUERY PLAN                             
+-------------------------------------------------------------------
  Sort
    Sort Key: t1.a
    ->  Hash Join
          Hash Cond: (t2.b = t1.a)
          ->  Seq Scan on prt2_p2 t2
-               Filter: (b > 250)
+               Filter: ((b > 250) AND (b < 450))
          ->  Hash
                ->  Seq Scan on prt1_p2 t1
-                     Filter: ((a < 450) AND (b = 0))
+                     Filter: ((a < 450) AND (a > 250) AND (b = 0))
 (9 rows)
 
 SELECT t1.a, t1.c, t2.b, t2.c FROM prt1 t1, prt2 t2 WHERE t1.a = t2.b AND t1.a < 450 AND t2.b > 250 AND t1.b = 0 ORDER BY t1.a, t2.b;
@@ -3089,16 +3089,18 @@ SELECT t1.a, t1.c, t2.b, t2.c FROM prt1_adv t1 INNER JOIN prt2_adv t2 ON (t1.a =
          ->  Hash Join
                Hash Cond: (t2_1.b = t1_1.a)
                ->  Seq Scan on prt2_adv_p1 t2_1
+                     Filter: (b < 300)
                ->  Hash
                      ->  Seq Scan on prt1_adv_p1 t1_1
                            Filter: ((a < 300) AND (b = 0))
          ->  Hash Join
                Hash Cond: (t2_2.b = t1_2.a)
                ->  Seq Scan on prt2_adv_p2 t2_2
+                     Filter: (b < 300)
                ->  Hash
                      ->  Seq Scan on prt1_adv_p2 t1_2
                            Filter: ((a < 300) AND (b = 0))
-(15 rows)
+(17 rows)
 
 SELECT t1.a, t1.c, t2.b, t2.c FROM prt1_adv t1 INNER JOIN prt2_adv t2 ON (t1.a = t2.b) WHERE t1.a < 300 AND t1.b = 0 ORDER BY t1.a, t2.b;
   a  |  c   |  b  |  c   
@@ -3128,16 +3130,18 @@ SELECT t1.a, t1.c, t2.b, t2.c FROM prt1_adv t1 INNER JOIN prt2_adv t2 ON (t1.a =
          ->  Hash Join
                Hash Cond: (t2_1.b = t1_1.a)
                ->  Seq Scan on prt2_adv_p1 t2_1
+                     Filter: ((b >= 100) AND (b < 300))
                ->  Hash
                      ->  Seq Scan on prt1_adv_p1 t1_1
                            Filter: ((a >= 100) AND (a < 300) AND (b = 0))
          ->  Hash Join
                Hash Cond: (t2_2.b = t1_2.a)
                ->  Seq Scan on prt2_adv_p2 t2_2
+                     Filter: ((b >= 100) AND (b < 300))
                ->  Hash
                      ->  Seq Scan on prt1_adv_p2 t1_2
                            Filter: ((a >= 100) AND (a < 300) AND (b = 0))
-(15 rows)
+(17 rows)
 
 SELECT t1.a, t1.c, t2.b, t2.c FROM prt1_adv t1 INNER JOIN prt2_adv t2 ON (t1.a = t2.b) WHERE t1.a >= 100 AND t1.a < 300 AND t1.b = 0 ORDER BY t1.a, t2.b;
   a  |  c   |  b  |  c   
@@ -4681,27 +4685,32 @@ SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b = t2
                      Filter: ((b >= 125) AND (b < 225))
                ->  Hash
                      ->  Seq Scan on beta_neg_p1 t2_1
+                           Filter: ((b >= 125) AND (b < 225))
          ->  Hash Join
-               Hash Cond: ((t2_2.a = t1_2.a) AND (t2_2.b = t1_2.b))
-               ->  Seq Scan on beta_neg_p2 t2_2
+               Hash Cond: ((t1_2.a = t2_2.a) AND (t1_2.b = t2_2.b))
+               ->  Seq Scan on alpha_neg_p2 t1_2
+                     Filter: ((b >= 125) AND (b < 225))
                ->  Hash
-                     ->  Seq Scan on alpha_neg_p2 t1_2
+                     ->  Seq Scan on beta_neg_p2 t2_2
                            Filter: ((b >= 125) AND (b < 225))
          ->  Hash Join
-               Hash Cond: ((t2_4.a = t1_4.a) AND (t2_4.b = t1_4.b))
+               Hash Cond: ((t1_4.a = t2_4.a) AND (t1_4.b = t2_4.b))
                ->  Append
-                     ->  Seq Scan on beta_pos_p1 t2_4
-                     ->  Seq Scan on beta_pos_p2 t2_5
-                     ->  Seq Scan on beta_pos_p3 t2_6
+                     ->  Seq Scan on alpha_pos_p1 t1_4
+                           Filter: ((b >= 125) AND (b < 225))
+                     ->  Seq Scan on alpha_pos_p2 t1_5
+                           Filter: ((b >= 125) AND (b < 225))
+                     ->  Seq Scan on alpha_pos_p3 t1_6
+                           Filter: ((b >= 125) AND (b < 225))
                ->  Hash
                      ->  Append
-                           ->  Seq Scan on alpha_pos_p1 t1_4
+                           ->  Seq Scan on beta_pos_p1 t2_4
                                  Filter: ((b >= 125) AND (b < 225))
-                           ->  Seq Scan on alpha_pos_p2 t1_5
+                           ->  Seq Scan on beta_pos_p2 t2_5
                                  Filter: ((b >= 125) AND (b < 225))
-                           ->  Seq Scan on alpha_pos_p3 t1_6
+                           ->  Seq Scan on beta_pos_p3 t2_6
                                  Filter: ((b >= 125) AND (b < 225))
-(29 rows)
+(34 rows)
 
 SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b = t2.b) WHERE t1.b >= 125 AND t1.b < 225 ORDER BY t1.a, t1.b;
  a  |  b  |  c   | a  |  b  |  c   
diff --git a/src/test/regress/sql/equivclass.sql b/src/test/regress/sql/equivclass.sql
index 247b0a3105..dae83c4196 100644
--- a/src/test/regress/sql/equivclass.sql
+++ b/src/test/regress/sql/equivclass.sql
@@ -269,3 +269,15 @@ create temp view overview as
   select f1::information_schema.sql_identifier as sqli, f2 from undername;
 explain (costs off)  -- this should not require a sort
   select * from overview where sqli = 'foo' order by sqli;
+
+
+-- test equivalence filters
+explain (costs off)
+  select * from ec0
+  inner join ec1 on ec0.ff = ec1.ff
+  where ec0.ff between 1 and 10;
+
+explain (costs off)
+  select * from ec0
+  inner join ec1 on ec0.ff = ec1.ff
+  where ec1.ff between 1 and 10;
-- 
2.37.0

From b19ec90394d5d933028355725754b4bb7a8c9094 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 6 Jul 2022 15:47:30 +0300
Subject: [PATCH 3/6] Reduce some planning cost for deriving qual for EC filter
 feature.

Mainly changes includes:
1. Check if the qual is simple enough by checking rinfo->right_relids and
info->right_relids, save the pull_varnos of rinfo->clause calls.
2. check contain_volatile_functions against RestrictInfo, so that
the result can be shared with following calls.
3. By employing the RestictInfo->btreeineqfamility which is calculating.
with same round of calculating  RestrictInfo->mergeopfamilies. In this
way we save the some calls for syscache.
4. Calculating the opfamility and amstrategy at
distribute_filter_quals_to_eclass and cache the results in EquivalenceFilter.
if no suitable opfamility and amstrategy are found, bypass the qual immediately
and at last using the cached value generate_base_implied_equalities_no_const.

After this change, there is an testcase changed unexpectedly in equivclass.out
(compared with David's expectation file.)

The b.ff = 43 is disappeared from ec1 b. But since it even didn't shown
before the EC filter, so I'm not sure my changes here make something wrong,
maybe fix a issue by accidental?
---
 src/backend/nodes/outfuncs.c             |  2 +
 src/backend/optimizer/path/equivclass.c  | 57 +++++++++++++-----------
 src/backend/optimizer/plan/initsplan.c   | 50 +++++----------------
 src/include/nodes/pathnodes.h            |  2 +
 src/test/regress/expected/equivclass.out |  6 +--
 5 files changed, 47 insertions(+), 70 deletions(-)

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index b19462c758..f31f1de983 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2674,6 +2674,8 @@ _outEquivalenceFilter(StringInfo str, const EquivalenceFilter *node)
 	WRITE_OID_FIELD(ef_opno);
 	WRITE_BOOL_FIELD(ef_const_is_left);
 	WRITE_UINT_FIELD(ef_source_rel);
+	WRITE_OID_FIELD(opfamily);
+	WRITE_INT_FIELD(amstrategy);
 }
 
 static void
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 89c7f0dc39..38bbc325b0 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1234,19 +1234,17 @@ generate_base_implied_equalities_const(PlannerInfo *root,
 }
 
 /*
- * finds the opfamily and strategy number for the specified 'opno' and 'method'
- * access method. Returns True if one is found and sets 'family' and
- * 'amstrategy', or returns False if none are found.
+ * finds the operator id for the specified 'opno' and 'method' and 'opfamilies'
+ * Returns True if one is found and sets 'opfamily_p' and 'amstrategy_p' or returns
+ * False if none are found.
  */
 static bool
-find_am_family_and_stategy(Oid opno, Oid method, Oid *family, int *amstrategy)
+find_am_family_and_stategy(Oid opno, Oid method, List *opfamilies,
+						   Oid *opfamily_p, int *amstrategy_p)
 {
-	List *opfamilies;
 	ListCell *l;
 	int strategy;
 
-	opfamilies = get_opfamilies(opno, method);
-
 	foreach(l, opfamilies)
 	{
 		Oid opfamily = lfirst_oid(l);
@@ -1255,8 +1253,8 @@ find_am_family_and_stategy(Oid opno, Oid method, Oid *family, int *amstrategy)
 
 		if (strategy)
 		{
-			*amstrategy = strategy;
-			*family = opfamily;
+			*opfamily_p = opfamily;
+			*amstrategy_p = strategy;
 			return true;
 		}
 	}
@@ -1345,17 +1343,11 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 			EquivalenceFilter *ef = (EquivalenceFilter *) lfirst(lc2);
 			Expr *leftexpr;
 			Expr *rightexpr;
-			int strategy;
 			Oid opno;
-			Oid family;
 
 			if (ef->ef_source_rel == relid)
 				continue;
 
-			if (!find_am_family_and_stategy(ef->ef_opno, BTREE_AM_OID,
-				&family, &strategy))
-				continue;
-
 			if (ef->ef_const_is_left)
 			{
 				leftexpr = (Expr *) ef->ef_const;
@@ -1367,10 +1359,10 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 				rightexpr = (Expr *) ef->ef_const;
 			}
 
-			opno = get_opfamily_member(family,
+			opno = get_opfamily_member(ef->opfamily,
 										exprType((Node *) leftexpr),
 										exprType((Node *) rightexpr),
-										strategy);
+										ef->amstrategy);
 
 			if (opno == InvalidOid)
 				continue;
@@ -1989,9 +1981,12 @@ distribute_filter_quals_to_eclass(PlannerInfo *root, List *quallist)
 	 */
 	foreach(l, quallist)
 	{
-		OpExpr	   *opexpr = (OpExpr *) lfirst(l);
-		Expr	   *leftexpr = (Expr *) linitial(opexpr->args);
-		Expr	   *rightexpr = (Expr *) lsecond(opexpr->args);
+		RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
+		OpExpr *opexpr = (OpExpr *)(rinfo->clause);
+
+		Oid opfamily;
+		int amstrategy;
+
 		Const	   *constexpr;
 		Expr	   *varexpr;
 		Relids		exprrels;
@@ -2003,25 +1998,31 @@ distribute_filter_quals_to_eclass(PlannerInfo *root, List *quallist)
 		 * Determine if the the OpExpr is in the form "expr op const" or
 		 * "const op expr".
 		 */
-		if (IsA(leftexpr, Const))
+		if (bms_is_empty(rinfo->left_relids))
 		{
-			constexpr = (Const *) leftexpr;
-			varexpr = rightexpr;
+			constexpr = (Const *) get_leftop(rinfo->clause);
+			varexpr = (Expr *) get_rightop(rinfo->clause);
 			const_isleft = true;
+			exprrels = rinfo->right_relids;
 		}
 		else
 		{
-			constexpr = (Const *) rightexpr;
-			varexpr = leftexpr;
+			constexpr = (Const *) get_rightop(rinfo->clause);
+			varexpr = (Expr *) get_leftop(rinfo->clause);
 			const_isleft = false;
+			exprrels = rinfo->left_relids;
 		}
 
-		exprrels = pull_varnos(root, (Node *) varexpr);
-
 		/* should be filtered out, but we need to determine relid anyway */
 		if (!bms_get_singleton_member(exprrels, &relid))
 			continue;
 
+		if (!find_am_family_and_stategy(opexpr->opno, BTREE_AM_OID,
+										rinfo->btreeineqopfamilies,
+										&opfamily,
+										&amstrategy))
+			continue;
+
 		/* search for a matching eclass member in all eclasses */
 		foreach(l2, root->eq_classes)
 		{
@@ -2057,6 +2058,8 @@ distribute_filter_quals_to_eclass(PlannerInfo *root, List *quallist)
 					efilter->ef_const_is_left = const_isleft;
 					efilter->ef_opno = opexpr->opno;
 					efilter->ef_source_rel = relid;
+					efilter->opfamily = opfamily;
+					efilter->amstrategy = amstrategy;
 
 					ec->ec_filters = lappend(ec->ec_filters, efilter);
 					break;		/* Onto the next eclass */
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index f86276b667..d7a173b327 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -651,44 +651,6 @@ create_lateral_join_info(PlannerInfo *root)
 	}
 }
 
-/*
- * is_simple_filter_qual
- *             Analyzes an OpExpr to determine if it may be useful as an
- *             EquivalenceFilter. Returns true if the OpExpr may be of some use, or
- *             false if it should not be used.
- */
-static bool
-is_simple_filter_qual(PlannerInfo *root, OpExpr *expr)
-{
-	Expr *leftexpr;
-	Expr *rightexpr;
-
-	if (!IsA(expr, OpExpr))
-			return false;
-
-	if (list_length(expr->args) != 2)
-			return false;
-
-	leftexpr = (Expr *) linitial(expr->args);
-	rightexpr = (Expr *) lsecond(expr->args);
-
-	/* XXX should we restrict these to simple Var op Const expressions? */
-	if (IsA(leftexpr, Const))
-	{
-		if (bms_membership(pull_varnos(root, (Node *) rightexpr)) == BMS_SINGLETON &&
-			!contain_volatile_functions((Node *) rightexpr))
-			return true;
-	}
-	else if (IsA(rightexpr, Const))
-	{
-		if (bms_membership(pull_varnos(root, (Node *) leftexpr)) == BMS_SINGLETON &&
-			!contain_volatile_functions((Node *) leftexpr))
-			return true;
-	}
-
-	return false;
-}
-
 /*****************************************************************************
  *
  *	  JOIN TREE PROCESSING
@@ -1678,6 +1640,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 	bool		maybe_outer_join;
 	Relids		nullable_relids;
 	RestrictInfo *restrictinfo;
+	int	relid;
 
 	/*
 	 * Retrieve all relids mentioned within the clause.
@@ -2027,8 +1990,15 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 	distribute_restrictinfo_to_rels(root, restrictinfo);
 
 	/* Check if the qual looks useful to harvest as an EquivalenceFilter */
-	if (filter_qual_list != NULL && is_simple_filter_qual(root, (OpExpr *) clause))
-		*filter_qual_list = lappend(*filter_qual_list, clause);
+	if (filter_qual_list != NULL &&
+		is_opclause(restrictinfo->clause) &&
+		!contain_volatile_functions((Node *)restrictinfo) && // Cachable
+		restrictinfo->btreeineqopfamilies != NIL &&  /* ineq expression */
+		/* simple & common enough filter, one side references one relation and the other one is a constant */
+		((bms_is_empty(restrictinfo->left_relids) && bms_get_singleton_member(restrictinfo->right_relids, &relid)) ||
+		 (bms_is_empty(restrictinfo->right_relids) && bms_get_singleton_member(restrictinfo->left_relids, &relid)))
+		)
+		*filter_qual_list = lappend(*filter_qual_list, restrictinfo);
 }
 
 /*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index f80b47ae2c..942a52fcac 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1179,6 +1179,8 @@ typedef struct EquivalenceFilter
 	Oid			ef_opno;		/* Operator Oid of filter operator */
 	bool		ef_const_is_left; /* Is the Const on the left of the OpExrp? */
 	Index		ef_source_rel;	/* relid of originating relation. */
+	Oid			opfamily;
+	int			amstrategy;
 } EquivalenceFilter;
 
 /*
diff --git a/src/test/regress/expected/equivclass.out b/src/test/regress/expected/equivclass.out
index 92fcec1158..980bd3817d 100644
--- a/src/test/regress/expected/equivclass.out
+++ b/src/test/regress/expected/equivclass.out
@@ -407,14 +407,14 @@ set session authorization regress_user_ectest;
 explain (costs off)
   select * from ec0 a, ec1 b
   where a.ff = b.ff and a.ff = 43::bigint::int8alias1;
-                              QUERY PLAN                              
-----------------------------------------------------------------------
+                 QUERY PLAN                  
+---------------------------------------------
  Nested Loop
    ->  Index Scan using ec0_pkey on ec0 a
          Index Cond: (ff = '43'::int8alias1)
    ->  Index Scan using ec1_pkey on ec1 b
          Index Cond: (ff = a.ff)
-         Filter: ((f1 < '5'::int8alias1) AND (ff = '43'::int8alias1))
+         Filter: (f1 < '5'::int8alias1)
 (6 rows)
 
 reset session authorization;
-- 
2.37.0

From e84fa416c5e55fcdb250bfbb0125fa2fc75013df Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 6 Jul 2022 15:48:00 +0300
Subject: [PATCH 4/6] Prepare the code for CorrectiveQual structure. Just
 refactor the method for 2-level loop in
 generate_base_implied_equalities_no_const, no other things is changed.

---
 src/backend/optimizer/path/equivclass.c | 61 +++++++++++++++----------
 1 file changed, 37 insertions(+), 24 deletions(-)

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 38bbc325b0..b3e5ebfbb1 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1333,17 +1333,33 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 				rinfo->right_em = cur_em;
 			}
 		}
+		prev_ems[relid] = cur_em;
+	}
 
-		/*
-		 * Also push any EquivalenceFilter clauses down into all relations
-		 * other than the one which the filter actually originated from.
-		 */
-		foreach(lc2, ec->ec_filters)
+	pfree(prev_ems);
+
+
+	/*
+	 * Also push any EquivalenceFilter clauses down into all relations
+	 * other than the one which the filter actually originated from.
+	 */
+	foreach(lc2, ec->ec_filters)
+	{
+		EquivalenceFilter *ef = (EquivalenceFilter *) lfirst(lc2);
+		Expr *leftexpr;
+		Expr *rightexpr;
+		Oid opno;
+		int relid;
+
+		if (ec->ec_broken)
+			break;
+
+		foreach(lc, ec->ec_members)
 		{
-			EquivalenceFilter *ef = (EquivalenceFilter *) lfirst(lc2);
-			Expr *leftexpr;
-			Expr *rightexpr;
-			Oid opno;
+			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+
+			if (!bms_get_singleton_member(cur_em->em_relids, &relid))
+				continue;
 
 			if (ef->ef_source_rel == relid)
 				continue;
@@ -1360,29 +1376,26 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 			}
 
 			opno = get_opfamily_member(ef->opfamily,
-										exprType((Node *) leftexpr),
-										exprType((Node *) rightexpr),
-										ef->amstrategy);
+									   exprType((Node *) leftexpr),
+									   exprType((Node *) rightexpr),
+									   ef->amstrategy);
 
 			if (opno == InvalidOid)
 				continue;
 
+
 			process_implied_equality(root, opno,
-										ec->ec_collation,
-										leftexpr,
-										rightexpr,
-										bms_copy(ec->ec_relids),
-										bms_copy(cur_em->em_nullable_relids),
-										ec->ec_min_security,
-										ec->ec_below_outer_join,
-										false);
+									 ec->ec_collation,
+									 leftexpr,
+									 rightexpr,
+									 bms_copy(ec->ec_relids),
+									 bms_copy(cur_em->em_nullable_relids),
+									 ec->ec_min_security,
+									 ec->ec_below_outer_join,
+									 false);
 		}
-
-		prev_ems[relid] = cur_em;
 	}
 
-	pfree(prev_ems);
-
 	/*
 	 * We also have to make sure that all the Vars used in the member clauses
 	 * will be available at any join node we might try to reference them at.
-- 
2.37.0

From 03e75cf5db6b607cd62d2fdcd1b44e56fccaf3cf Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 6 Jul 2022 15:52:36 +0300
Subject: [PATCH 5/6] CorrectiveQuals is as simple as a List of RestrictInfo,
 a). only one restrictinfo on this group should be counted for any joinrel
 estimation. b). at least 1 restrictinfo in this group should be executed
 during execution. In this commit, only rows estimation issue is addressed.

PlannerInfo.correlative_quals is added to manage all the CorrectiveQuals at
subquery level. RelOptInfo.cqual_indexes is a List * to indicate a which
CorrectiveQuals this relation related to. This is designed for easy to check if
the both sides of joinrel correlated to the same CorrectiveQuals. Why isn't the
type a Bitmapset * will be explained later.

The overall design of handing the joinrel size estimation is:
a). At the base relation level, we just count everything with the correlative
quals. b). During the any level joinrel size estimation, we just keep 1 side's
cqual (short for corrective qual) selectivity by eliminated the other one. so
the size estimation for a mergeable join selectivity becomes to:

rows = R1.rows X r2.rows X 1 / Max (ndistval_of_colA,  ndistinval_of_colB) X 1 /
Selectivity(R1's CorrectiveQual).

r1.rows X 1 / Selectivity(R1's CorrectiveQual) eliminated the impact of
CorrectiveQual on R1. After this,  the JoinRel of (R1, R2) still be impacted by
this CorrectiveQual but just one in this level.  Later if JoinRel(R1, R2) needs
to join with R3,  and R3 is impacted by this CorectiveQuals as well. This we
need to keep one and eliminating the other one as above again.

The algorithm for which Selectivity should be eliminated and which one should be
kept is:

When we join 2 inner_rel and outer_rel with a mergeable join restrictinfo, if
both sides is impacted with the same CorrectiveQual, we first choose which "side"
to eliminating based on which side of the restrictinfo has a higher distinct
value. The reason for this is more or less because we used "Max"(ndistinctValT1,
ndistinctValT2). After decide which "side" to eliminating, the real eliminating
selecitity is the side of RelOptInfo->cqual_selectivity[n]

Selectivity *RelOptInfo->cqual_selectivity:

 The number of elements in cqual_selecitity equals
 the length of cqual_indexes. The semantics is which
 selectivity in the corresponding CorectiveQuals's qual
 list is taking effect. At only time, only 1 Qual
 Selectivity is counted for any-level of joinrel.

and the other side's RelOptInfo->cqual_selectivty is used to set the upper
joinrel->cqual_selecivity.

In reality, it is possible for to have many CorrectiveQuals, but for design
discussion, the current implementation only take care of the 1 CorrectiveQuals.
this would be helpful for PoC/review/discussion.

1. root->corrective_quals is initialized at
generate_base_implied_equalities_no_const stage. we create a CorrectiveQual in
this list for each ec_filter and fill the RestrictInfo part for this cqual. At
the same time, we note which RelOptInfo (cqual_indexes) has related to this cqual.

2. RelOptInfo->cqual_selecitity for baserel is set at the end of set_rel_size,
at this time, the selectivity for every RestrictInfo is calcuated, we can just
fetch the cached value.  As for joinrel, it is maintained in
calc_join_cqual_selectivity, this function would return the Selectivity to
eliminate and set the above value.

Limitation in this PoC:
1. Only support 1 CorrectiveQual in root->correlative_quals
2. Only tested with INNER_JOIN.
3. Inherited table is not supported.
---
 src/backend/nodes/outfuncs.c              |   1 +
 src/backend/optimizer/path/allpaths.c     |  27 ++++
 src/backend/optimizer/path/costsize.c     | 182 ++++++++++++++++++++++
 src/backend/optimizer/path/equivclass.c   |  48 ++++--
 src/backend/optimizer/plan/planner.c      |   1 +
 src/backend/optimizer/prep/prepjointree.c |   1 +
 src/include/nodes/nodes.h                 |   1 +
 src/include/nodes/pathnodes.h             |  36 ++++-
 8 files changed, 280 insertions(+), 17 deletions(-)

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index f31f1de983..5e0434df1e 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2676,6 +2676,7 @@ _outEquivalenceFilter(StringInfo str, const EquivalenceFilter *node)
 	WRITE_UINT_FIELD(ef_source_rel);
 	WRITE_OID_FIELD(opfamily);
 	WRITE_INT_FIELD(amstrategy);
+	WRITE_NODE_FIELD(rinfo);
 }
 
 static void
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index e9342097e5..2ee28a94fc 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -463,6 +463,33 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel,
 	 * We insist that all non-dummy rels have a nonzero rowcount estimate.
 	 */
 	Assert(rel->rows > 0 || IS_DUMMY_REL(rel));
+
+	/* Now calculating the selectivity impacted by Corrective Qual */
+	if (!rte->inh)  /* not supported in this PoC */
+	{
+		ListCell *l;
+		int i = 0;
+		rel->cqual_selectivity = palloc(sizeof(Selectivity) * list_length(rel->cqual_indexes));
+
+		foreach(l, rel->cqual_indexes)
+		{
+			int cq_index = lfirst_int(l);
+			CorrelativeQuals *cquals = list_nth_node(CorrelativeQuals, root->correlative_quals, cq_index);
+			ListCell *l2;
+			bool found = false;
+			foreach(l2, cquals->corr_restrictinfo)
+			{
+				RestrictInfo *rinfo = lfirst_node(RestrictInfo, l2);
+				if (bms_equal(rinfo->clause_relids, rel->relids))
+				{
+					found = true;
+					rel->cqual_selectivity[i] = rinfo->norm_selec > 0 ? rinfo->norm_selec : rinfo->outer_selec;
+					Assert(rel->cqual_selectivity[i] > 0);
+				}
+			}
+			Assert(found);
+		}
+	}
 }
 
 /*
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index fcc26b01a4..03b92a2a88 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -5428,6 +5428,138 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
 	return nrows;
 }
 
+
+/*
+ * Given a mergeable RestrictInfo, find out which relid should be used for
+ * eliminating Corrective Qual Selectivity.
+ */
+static int
+find_relid_to_eliminate(PlannerInfo *root, RestrictInfo *rinfo)
+{
+	int left_relid,  right_relid;
+	RelOptInfo *lrel, *rrel;
+	bool res;
+
+	res = bms_get_singleton_member(rinfo->left_relids, &left_relid);
+	Assert(res);
+	res = bms_get_singleton_member(rinfo->left_relids, &right_relid);
+	Assert(res);
+
+	lrel = root->simple_rel_array[left_relid];
+	rrel = root->simple_rel_array[right_relid];
+
+	/* XXX: Assumed only one CorrectiveQual exists */
+
+	if (lrel->cqual_selectivity[0] > rrel->cqual_selectivity[0])
+		return left_relid;
+
+	return right_relid;
+}
+
+/*
+ * calc_join_cqual_selectivity
+ *
+ *	When join two relations, if both sides are impacted by the same CorrectiveQuals,
+ * we need to eliminate one of them and note the other one for future eliminating when join
+ * another corrective relation. or else just note the joinrel still being impacted by the
+ * single sides's CorrectiveQuals.
+ *
+ * Return value is the Selectivity we need to eliminate for estimating the current
+ * joinrel.
+ */
+static double
+calc_join_cqual_selectivity(PlannerInfo *root,
+							RelOptInfo *joinrel,
+							RelOptInfo *outer_rel,
+							RelOptInfo *inner_rel,
+							RestrictInfo *rinfo)
+{
+	double res = 1;
+	ListCell *lc1, *lc2;
+	Selectivity left_sel;  /* The cqual selectivity still impacted on this joinrel. */
+
+	/*
+	 * Find how many CorrectiveQual for this joinrel and allocate space for each left Selectivity
+	 * for each CorrectiveQual here.
+	 */
+	List	*final_cq_list = list_union_int(outer_rel->cqual_indexes, inner_rel->cqual_indexes);
+
+	joinrel->cqual_selectivity = palloc(sizeof(Selectivity) * list_length(final_cq_list));
+
+	foreach(lc1, outer_rel->cqual_indexes)
+	{
+		int outer_cq_index = lfirst_int(lc1);
+		int inner_cq_pos = -1;
+		int outer_idx = foreach_current_index(lc1);
+		int curr_sel_len;
+
+		/*
+		 * Check if the same corrective quals applied in both sides,
+		 * if yes, we need to decide which one to eliminate and which one
+		 * to keep. or else, we just keep the selectivity for feature use.
+		 */
+		foreach(lc2, inner_rel->cqual_indexes)
+		{
+			if (outer_cq_index == lfirst_int(lc2))
+				inner_cq_pos = foreach_current_index(lc2);
+		}
+
+		if (inner_cq_pos >= 0)
+		{
+			/* Find the CorrectiveQual which impacts both side. */
+			int relid = find_relid_to_eliminate(root, rinfo);
+			if (bms_is_member(relid, outer_rel->relids))
+			{
+				/* XXXX: we assume only 1 CorrectiveQual exist, so [0] directly. */
+				res *= outer_rel->cqual_selectivity[0];
+				left_sel = inner_rel->cqual_selectivity[0];
+			}
+			else
+			{
+				/* XXXX: we assume only 1 CorrectiveQual exist */
+				res *= inner_rel->cqual_selectivity[0];
+				left_sel = outer_rel->cqual_selectivity[0];
+			}
+		}
+		else
+		{
+			/* Only shown in outer side. */
+			left_sel = outer_rel->cqual_selectivity[outer_idx];
+		}
+
+		/*
+		 * If any side of join relation is impacted by a cqual, it is impacted for the joinrel
+		 * for sure.
+		 */
+		curr_sel_len = list_length(joinrel->cqual_indexes);
+		joinrel->cqual_indexes = lappend_int(joinrel->cqual_indexes, outer_idx);
+
+		joinrel->cqual_selectivity[curr_sel_len] = left_sel;
+		// elog(INFO, "left_sel %f", left_sel);
+	}
+
+	/* Push any cqual information which exists in inner_rel only to join rel. */
+	foreach(lc1, inner_rel->cqual_indexes)
+	{
+		int inner_cq_index = lfirst_int(lc1);
+		int curr_sel_len;
+
+		if (list_member_int(outer_rel->cqual_indexes, inner_cq_index))
+			/* have been handled in the previous loop */
+			continue;
+
+		curr_sel_len = list_length(joinrel->cqual_indexes);
+		joinrel->cqual_selectivity[curr_sel_len] = inner_rel->cqual_selectivity[foreach_current_index(lc1)];
+	}
+
+	pfree(final_cq_list);
+
+	// elog(INFO, "Final adjust sel (%s): %f", bmsToString(joinrel->relids), res);
+
+	return res;
+}
+
+
 /*
  * calc_joinrel_size_estimate
  *		Workhorse for set_joinrel_size_estimates and
@@ -5571,6 +5703,56 @@ calc_joinrel_size_estimate(PlannerInfo *root,
 			break;
 	}
 
+	{
+		Selectivity m1 = 1;
+		bool should_eliminate = false;
+		RestrictInfo *rinfo;
+
+		// XXX: For hack only, the aim is the "only one" restrictinfo is the one impacted by "the only one"
+		// CorrectiveQuals. for example:
+		// SELECT * FROM t1, t2, t3 WHERE t1.a = t2.a and t2.a = t3.a and t3.a > 2;
+
+		if (list_length(root->correlative_quals) == 1 &&
+			list_length(restrictlist) == 1 &&
+			jointype == JOIN_INNER)
+		{
+			int left_relid, right_relid;
+			rinfo = linitial_node(RestrictInfo, restrictlist);
+			if (rinfo->mergeopfamilies != NIL &&
+				bms_get_singleton_member(rinfo->left_relids, &left_relid) &&
+				bms_get_singleton_member(rinfo->right_relids, &right_relid))
+			{
+				List *interset_cq_indexes = list_intersection_int(
+					root->simple_rel_array[left_relid]->cqual_indexes,
+					root->simple_rel_array[right_relid]->cqual_indexes);
+
+				if (interset_cq_indexes != NIL &&
+					!root->simple_rte_array[left_relid]->inh &&
+					!root->simple_rte_array[right_relid]->inh)
+					should_eliminate = true;
+			}
+		}
+
+		// elog(INFO, "joinrel: %s, %d", bmsToString(joinrel->relids), should_eliminate);
+
+		if (should_eliminate)
+			m1 = calc_join_cqual_selectivity(root, joinrel, outer_rel, inner_rel, rinfo);
+
+		/* elog(INFO, */
+		/*	 "joinrelids: %s, outer_rel: %s, inner_rel: %s, join_clauselist: %s outer rows: %f, inner_rows: %f, join rows: %f, jselec: %f, m1 = %f, m2 = %f", */
+		/*	 bmsToString(joinrel->relids), */
+		/*	 bmsToString(outer_rel->relids), */
+		/*	 bmsToString(inner_rel->relids), */
+		/*	 bmsToString(join_list_relids), */
+		/*	 outer_rel->rows, */
+		/*	 inner_rel->rows, */
+		/*	 nrows, */
+		/*	 jselec, */
+		/*	 m1, */
+		/*	 m2); */
+		nrows /= m1;
+	}
+
 	return clamp_row_est(nrows);
 }
 
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index b3e5ebfbb1..3efeb1f333 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -1272,6 +1272,8 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 	EquivalenceMember **prev_ems;
 	ListCell   *lc;
 	ListCell   *lc2;
+	int	start_cq_index = list_length(root->correlative_quals);
+	int	ef_index = 0;
 
 	/*
 	 * We scan the EC members once and track the last-seen member for each
@@ -1338,9 +1340,11 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 
 	pfree(prev_ems);
 
+	if (ec->ec_broken)
+		goto ec_filter_done;
 
 	/*
-	 * Also push any EquivalenceFilter clauses down into all relations
+	 * Push any EquivalenceFilter clauses down into all relations
 	 * other than the one which the filter actually originated from.
 	 */
 	foreach(lc2, ec->ec_filters)
@@ -1350,19 +1354,25 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 		Expr *rightexpr;
 		Oid opno;
 		int relid;
-
-		if (ec->ec_broken)
-			break;
+		CorrelativeQuals *cquals = makeNode(CorrelativeQuals);
 
 		foreach(lc, ec->ec_members)
 		{
 			EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
+			RelOptInfo *rel;
+			RestrictInfo *rinfo;
 
 			if (!bms_get_singleton_member(cur_em->em_relids, &relid))
 				continue;
 
+			rel = root->simple_rel_array[relid];
+
 			if (ef->ef_source_rel == relid)
+			{
+				rel->cqual_indexes = lappend_int(rel->cqual_indexes, start_cq_index + ef_index);
+				cquals->corr_restrictinfo = lappend(cquals->corr_restrictinfo, ef->rinfo);
 				continue;
+			}
 
 			if (ef->ef_const_is_left)
 			{
@@ -1383,19 +1393,28 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 			if (opno == InvalidOid)
 				continue;
 
-
-			process_implied_equality(root, opno,
-									 ec->ec_collation,
-									 leftexpr,
-									 rightexpr,
-									 bms_copy(ec->ec_relids),
-									 bms_copy(cur_em->em_nullable_relids),
-									 ec->ec_min_security,
-									 ec->ec_below_outer_join,
-									 false);
+			rinfo = process_implied_equality(root, opno,
+											 ec->ec_collation,
+											 leftexpr,
+											 rightexpr,
+											 bms_copy(ec->ec_relids),
+											 bms_copy(cur_em->em_nullable_relids),
+											 ec->ec_min_security,
+											 ec->ec_below_outer_join,
+											 false);
+			cquals->corr_restrictinfo = lappend(cquals->corr_restrictinfo, rinfo);
+			rel->cqual_indexes = lappend_int(rel->cqual_indexes, start_cq_index + ef_index);
 		}
+
+		ef_index += 1;
+
+		root->correlative_quals = lappend(root->correlative_quals, cquals);
 	}
 
+ec_filter_done:
+	/*
+	 * XXX this label can be removed after moving ec_filter to the end of this function.
+	 */
 	/*
 	 * We also have to make sure that all the Vars used in the member clauses
 	 * will be available at any join node we might try to reference them at.
@@ -2073,6 +2092,7 @@ distribute_filter_quals_to_eclass(PlannerInfo *root, List *quallist)
 					efilter->ef_source_rel = relid;
 					efilter->opfamily = opfamily;
 					efilter->amstrategy = amstrategy;
+					efilter->rinfo = rinfo;
 
 					ec->ec_filters = lappend(ec->ec_filters, efilter);
 					break;		/* Onto the next eclass */
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 06ad856eac..2be2429454 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -619,6 +619,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 	root->multiexpr_params = NIL;
 	root->eq_classes = NIL;
 	root->ec_merging_done = false;
+	root->correlative_quals = NIL;
 	root->all_result_relids =
 		parse->resultRelation ? bms_make_singleton(parse->resultRelation) : NULL;
 	root->leaf_result_relids = NULL;	/* we'll find out leaf-ness later */
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 0bd99acf83..d427de6f85 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -999,6 +999,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->multiexpr_params = NIL;
 	subroot->eq_classes = NIL;
 	subroot->ec_merging_done = false;
+	subroot->correlative_quals = NIL;
 	subroot->all_result_relids = NULL;
 	subroot->leaf_result_relids = NULL;
 	subroot->append_rel_list = NIL;
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index ba879ab3e9..8800a05252 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -278,6 +278,7 @@ typedef enum NodeTag
 	/* these aren't subclasses of Path: */
 	T_EquivalenceClass,
 	T_EquivalenceFilter,
+	T_CorrelativeQuals,
 	T_EquivalenceMember,
 	T_PathKey,
 	T_PathKeyInfo,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 942a52fcac..1e9bb39277 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -251,6 +251,8 @@ struct PlannerInfo
 
 	bool		ec_merging_done;	/* set true once ECs are canonical */
 
+	List		*correlative_quals;  /* list of CorrelativeQuals for this subquery */
+
 	List	   *canon_pathkeys; /* list of "canonical" PathKeys */
 
 	List	   *left_join_clauses;	/* list of RestrictInfos for mergejoinable
@@ -767,6 +769,18 @@ typedef struct RelOptInfo
 	 * Indexes in PlannerInfo's eq_classes list of ECs that mention this rel
 	 */
 	Bitmapset  *eclass_indexes;
+	List		*cqual_indexes; /* Indexes in PlannerInfo's correlative_quals list of
+								 * CorrelativeQuals that this rel has applied. It is valid
+								 * on both baserel and joinrel. Used to quick check is the
+								 * both sides contains the same CorrectiveQuals object.
+								 */
+	Selectivity	*cqual_selectivity; /*
+								   * The number of elements in cqual_selectivity equals
+								   * the length of cqual_indexes. The semantics is which
+								   * selectivity in the corresponding CorectiveQuals's qual
+								   * list is taking effect. At only time, only 1 Qual
+								   * Selectivity is counted for any-level of joinrel.
+								   */
 	PlannerInfo *subroot;		/* if subquery */
 	List	   *subplan_params; /* if subquery */
 	/* wanted number of parallel workers */
@@ -1181,8 +1195,24 @@ typedef struct EquivalenceFilter
 	Index		ef_source_rel;	/* relid of originating relation. */
 	Oid			opfamily;
 	int			amstrategy;
+	struct RestrictInfo	*rinfo;		/* source restrictInfo for this EquivalenceFilter */
 } EquivalenceFilter;
 
+
+/*
+ * Currently it is as simple as a List of RestrictInfo, it means a). For any joinrel size
+ * estimation, only one restrictinfo on this group should be counted. b). During execution,
+ * at least 1 restrictinfo in this group should be executed.
+ *
+ * Define it as a Node just for better extendability, we can stripe it to a List *
+ * if we are sure nothing else is needed.
+ */
+typedef struct CorrelativeQuals
+{
+	NodeTag	type;
+	List	*corr_restrictinfo;
+} CorrelativeQuals;
+
 /*
  * If an EC contains a const and isn't below-outer-join, any PathKey depending
  * on it must be redundant, since there's only one possible value of the key.
@@ -2872,7 +2902,7 @@ typedef enum
  *
  * flags indicating what kinds of grouping are possible.
  * partial_costs_set is true if the agg_partial_costs and agg_final_costs
- * 		have been initialized.
+ *		have been initialized.
  * agg_partial_costs gives partial aggregation costs.
  * agg_final_costs gives finalization costs.
  * target_parallel_safe is true if target is parallel safe.
@@ -2902,8 +2932,8 @@ typedef struct
  * limit_tuples is an estimated bound on the number of output tuples,
  *		or -1 if no LIMIT or couldn't estimate.
  * count_est and offset_est are the estimated values of the LIMIT and OFFSET
- * 		expressions computed by preprocess_limit() (see comments for
- * 		preprocess_limit() for more information).
+ *		expressions computed by preprocess_limit() (see comments for
+ *		preprocess_limit() for more information).
  */
 typedef struct
 {
-- 
2.37.0

From b05f3381a5cfde1d3e628b829fe2e7cff3649804 Mon Sep 17 00:00:00 2001
From: "Andrey V. Lepikhov" <[email-masked]>
Date: Wed, 6 Jul 2022 15:54:24 +0300
Subject: [PATCH 6/6] Disable ec filter for foregin table for now. We do need
 support EC filter against for foreign table, but when fixing the cost model
 issue, we need to know the selecvitiy of the qual on foregin table. However
 it is impossible for now to know that when use_remote_estimate = true. see
 for postgresGetForeignRelSize. Since we currently only doing PoC for this
 cost-model-fix algorithm, I just disable that for foregin table. At last, we
 need improve the use_remote_estimate somehow to get the selectivity.

---
 .../postgres_fdw/expected/postgres_fdw.out    | 36 +++++++++----------
 src/backend/optimizer/path/allpaths.c         |  2 +-
 src/backend/optimizer/path/equivclass.c       | 14 ++++++++
 src/backend/optimizer/plan/initsplan.c        |  9 +++--
 4 files changed, 40 insertions(+), 21 deletions(-)

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 2758049f5b..44457f930c 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -1545,12 +1545,12 @@ SELECT t1.c1, ss.a, ss.b FROM (SELECT c1 FROM "S 1"."T 3" WHERE c1 = 50) t1 INNE
 -- full outer join + inner join
 EXPLAIN (VERBOSE, COSTS OFF)
 SELECT t1.c1, t2.c1, t3.c1 FROM ft4 t1 INNER JOIN ft5 t2 ON (t1.c1 = t2.c1 + 1 and t1.c1 between 50 and 60) FULL JOIN ft4 t3 ON (t2.c1 = t3.c1) ORDER BY t1.c1, t2.c1, t3.c1 LIMIT 10;
-                                                                                                                                                                           QUERY PLAN                                                                                                                                                                           
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                                                                                                                 QUERY PLAN                                                                                                                                                 
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Foreign Scan
    Output: t1.c1, t2.c1, t3.c1
    Relations: ((public.ft4 t1) INNER JOIN (public.ft5 t2)) FULL JOIN (public.ft4 t3)
-   Remote SQL: SELECT r1.c1, r2.c1, r4.c1 FROM (("S 1"."T 3" r1 INNER JOIN "S 1"."T 4" r2 ON (((r1.c1 = (r2.c1 + 1))) AND (((r2.c1 + 1) >= 50)) AND (((r2.c1 + 1) <= 60)) AND ((r1.c1 >= 50)) AND ((r1.c1 <= 60)))) FULL JOIN "S 1"."T 3" r4 ON (((r2.c1 = r4.c1)))) ORDER BY r1.c1 ASC NULLS LAST, r2.c1 ASC NULLS LAST, r4.c1 ASC NULLS LAST LIMIT 10::bigint
+   Remote SQL: SELECT r1.c1, r2.c1, r4.c1 FROM (("S 1"."T 3" r1 INNER JOIN "S 1"."T 4" r2 ON (((r1.c1 = (r2.c1 + 1))) AND ((r1.c1 >= 50)) AND ((r1.c1 <= 60)))) FULL JOIN "S 1"."T 3" r4 ON (((r2.c1 = r4.c1)))) ORDER BY r1.c1 ASC NULLS LAST, r2.c1 ASC NULLS LAST, r4.c1 ASC NULLS LAST LIMIT 10::bigint
 (4 rows)
 
 SELECT t1.c1, t2.c1, t3.c1 FROM ft4 t1 INNER JOIN ft5 t2 ON (t1.c1 = t2.c1 + 1 and t1.c1 between 50 and 60) FULL JOIN ft4 t3 ON (t2.c1 = t3.c1) ORDER BY t1.c1, t2.c1, t3.c1 LIMIT 10;
@@ -2335,12 +2335,12 @@ SELECT ft4.c1, q.* FROM ft4 LEFT JOIN (SELECT 13, ft1.c1, ft2.c1 FROM ft1 RIGHT
 UPDATE ft5 SET c3 = null where c1 % 9 = 0;
 EXPLAIN (VERBOSE, COSTS OFF)
 SELECT ft5, ft5.c1, ft5.c2, ft5.c3, ft4.c1, ft4.c2 FROM ft5 left join ft4 on ft5.c1 = ft4.c1 WHERE ft4.c1 BETWEEN 10 and 30 ORDER BY ft5.c1, ft4.c1;
-                                                                                                                                                    QUERY PLAN                                                                                                                                                     
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                                                                                                QUERY PLAN                                                                                                                                 
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Foreign Scan
    Output: ft5.*, ft5.c1, ft5.c2, ft5.c3, ft4.c1, ft4.c2
    Relations: (public.ft5) INNER JOIN (public.ft4)
-   Remote SQL: SELECT CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1.c1, r1.c2, r1.c3) END, r1.c1, r1.c2, r1.c3, r2.c1, r2.c2 FROM ("S 1"."T 4" r1 INNER JOIN "S 1"."T 3" r2 ON (((r1.c1 = r2.c1)) AND ((r2.c1 >= 10)) AND ((r2.c1 <= 30)) AND ((r1.c1 >= 10)) AND ((r1.c1 <= 30)))) ORDER BY r1.c1 ASC NULLS LAST
+   Remote SQL: SELECT CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1.c1, r1.c2, r1.c3) END, r1.c1, r1.c2, r1.c3, r2.c1, r2.c2 FROM ("S 1"."T 4" r1 INNER JOIN "S 1"."T 3" r2 ON (((r1.c1 = r2.c1)) AND ((r2.c1 >= 10)) AND ((r2.c1 <= 30)))) ORDER BY r1.c1 ASC NULLS LAST
 (4 rows)
 
 SELECT ft5, ft5.c1, ft5.c2, ft5.c3, ft4.c1, ft4.c2 FROM ft5 left join ft4 on ft5.c1 = ft4.c1 WHERE ft4.c1 BETWEEN 10 and 30 ORDER BY ft5.c1, ft4.c1;
@@ -2362,8 +2362,8 @@ SET enable_hashjoin TO false;
 EXPLAIN (VERBOSE, COSTS OFF)
 SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = ft4.c1
     AND ft1.c2 = ft5.c1 AND ft1.c2 = local_tbl.c1 AND ft1.c1 < 100 AND ft2.c1 < 100 FOR UPDATE;
-                                                                                                                                                                                                                                                                                                                                                                                                                                                                      QUERY PLAN                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                                                                                                                                                                                                                                                                                                                                                                                                               QUERY PLAN                                                                                                                                                                                                                                                                                                                                                                                                                                               
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  LockRows
    Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft4.c1, ft4.c2, ft4.c3, ft5.c1, ft5.c2, ft5.c3, local_tbl.c1, local_tbl.c2, local_tbl.c3, ft1.*, ft2.*, ft4.*, ft5.*, local_tbl.ctid
    ->  Merge Join
@@ -2373,7 +2373,7 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f
          ->  Foreign Scan
                Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.*, ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.*, ft4.c1, ft4.c2, ft4.c3, ft4.*, ft5.c1, ft5.c2, ft5.c3, ft5.*
                Relations: (((public.ft1) INNER JOIN (public.ft2)) INNER JOIN (public.ft4)) INNER JOIN (public.ft5)
-               Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END, r3.c1, r3.c2, r3.c3, CASE WHEN (r3.*)::text IS NOT NULL THEN ROW(r3.c1, r3.c2, r3.c3) END, r4.c1, r4.c2, r4.c3, CASE WHEN (r4.*)::text IS NOT NULL THEN ROW(r4.c1, r4.c2, r4.c3) END FROM ((("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")) AND ((r2."C 1" < 100)) AND ((r2."C 1" < 100)) AND ((r1."C 1" < 100)) AND ((r1."C 1" < 100)))) INNER JOIN "S 1"."T 3" r3 ON (((r1.c2 = r3.c1)))) INNER JOIN "S 1"."T 4" r4 ON (((r1.c2 = r4.c1)))) ORDER BY r1.c2 ASC NULLS LAST FOR UPDATE OF r1 FOR UPDATE OF r2 FOR UPDATE OF r3 FOR UPDATE OF r4
+               Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END, r3.c1, r3.c2, r3.c3, CASE WHEN (r3.*)::text IS NOT NULL THEN ROW(r3.c1, r3.c2, r3.c3) END, r4.c1, r4.c2, r4.c3, CASE WHEN (r4.*)::text IS NOT NULL THEN ROW(r4.c1, r4.c2, r4.c3) END FROM ((("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")) AND ((r2."C 1" < 100)) AND ((r1."C 1" < 100)))) INNER JOIN "S 1"."T 3" r3 ON (((r1.c2 = r3.c1)))) INNER JOIN "S 1"."T 4" r4 ON (((r1.c2 = r4.c1)))) ORDER BY r1.c2 ASC NULLS LAST FOR UPDATE OF r1 FOR UPDATE OF r2 FOR UPDATE OF r3 FOR UPDATE OF r4
                ->  Merge Join
                      Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.*, ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.*, ft4.c1, ft4.c2, ft4.c3, ft4.*, ft5.c1, ft5.c2, ft5.c3, ft5.*
                      Merge Cond: (ft1.c2 = ft5.c1)
@@ -2391,12 +2391,12 @@ SELECT * FROM ft1, ft2, ft4, ft5, local_tbl WHERE ft1.c1 = ft2.c1 AND ft1.c2 = f
                                              Sort Key: ft1.c1
                                              ->  Foreign Scan on public.ft1
                                                    Output: ft1.c1, ft1.c2, ft1.c3, ft1.c4, ft1.c5, ft1.c6, ft1.c7, ft1.c8, ft1.*
-                                                   Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND (("C 1" < 100)) FOR UPDATE
+                                                   Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) FOR UPDATE
                                        ->  Materialize
                                              Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.*
                                              ->  Foreign Scan on public.ft2
                                                    Output: ft2.c1, ft2.c2, ft2.c3, ft2.c4, ft2.c5, ft2.c6, ft2.c7, ft2.c8, ft2.*
-                                                   Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) AND (("C 1" < 100)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE
+                                                   Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" < 100)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE
                            ->  Sort
                                  Output: ft4.c1, ft4.c2, ft4.c3, ft4.*
                                  Sort Key: ft4.c1
@@ -5705,25 +5705,25 @@ UPDATE ft2 AS target SET (c2) = (
 EXPLAIN (VERBOSE, COSTS OFF)
 UPDATE ft2 d SET c2 = CASE WHEN random() >= 0 THEN d.c2 ELSE 0 END
   FROM ft2 AS t WHERE d.c1 = t.c1 AND d.c1 > 1000;
-                                                                                                                                                                                                   QUERY PLAN                                                                                                                                                                                                    
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+                                                                                                                                                                                       QUERY PLAN                                                                                                                                                                                        
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  Update on public.ft2 d
    Remote SQL: UPDATE "S 1"."T 1" SET c2 = $2 WHERE ctid = $1
    ->  Foreign Scan
          Output: CASE WHEN (random() >= '0'::double precision) THEN d.c2 ELSE 0 END, d.ctid, d.*, t.*
          Relations: (public.ft2 d) INNER JOIN (public.ft2 t)
-         Remote SQL: SELECT r1.c2, r1.ctid, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")) AND ((r2."C 1" > 1000)) AND ((r1."C 1" > 1000)))) FOR UPDATE OF r1
-         ->  Merge Join
+         Remote SQL: SELECT r1.c2, r1.ctid, CASE WHEN (r1.*)::text IS NOT NULL THEN ROW(r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6, r1.c7, r1.c8) END, CASE WHEN (r2.*)::text IS NOT NULL THEN ROW(r2."C 1", r2.c2, r2.c3, r2.c4, r2.c5, r2.c6, r2.c7, r2.c8) END FROM ("S 1"."T 1" r1 INNER JOIN "S 1"."T 1" r2 ON (((r1."C 1" = r2."C 1")) AND ((r1."C 1" > 1000)))) FOR UPDATE OF r1
+         ->  Hash Join
                Output: d.c2, d.ctid, d.*, t.*
-               Merge Cond: (d.c1 = t.c1)
+               Hash Cond: (d.c1 = t.c1)
                ->  Foreign Scan on public.ft2 d
                      Output: d.c2, d.ctid, d.*, d.c1
                      Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8, ctid FROM "S 1"."T 1" WHERE (("C 1" > 1000)) ORDER BY "C 1" ASC NULLS LAST FOR UPDATE
-               ->  Materialize
+               ->  Hash
                      Output: t.*, t.c1
                      ->  Foreign Scan on public.ft2 t
                            Output: t.*, t.c1
-                           Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1" WHERE (("C 1" > 1000)) ORDER BY "C 1" ASC NULLS LAST
+                           Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8 FROM "S 1"."T 1"
 (17 rows)
 
 UPDATE ft2 d SET c2 = CASE WHEN random() >= 0 THEN d.c2 ELSE 0 END
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 2ee28a94fc..eb4ecc8478 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -465,7 +465,7 @@ set_rel_size(PlannerInfo *root, RelOptInfo *rel,
 	Assert(rel->rows > 0 || IS_DUMMY_REL(rel));
 
 	/* Now calculating the selectivity impacted by Corrective Qual */
-	if (!rte->inh)  /* not supported in this PoC */
+	if (!rte->inh)  /* Inherited table is not supported in this PoC */
 	{
 		ListCell *l;
 		int i = 0;
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 3efeb1f333..7b8124e1f2 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -21,6 +21,7 @@
 #include "access/stratnum.h"
 #include "catalog/pg_am.h"
 #include "catalog/pg_type.h"
+#include "catalog/pg_class.h"
 #include "nodes/makefuncs.h"
 #include "nodes/nodeFuncs.h"
 #include "optimizer/appendinfo.h"
@@ -1365,6 +1366,19 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
 			if (!bms_get_singleton_member(cur_em->em_relids, &relid))
 				continue;
 
+			if (root->simple_rte_array[relid]->relkind == RELKIND_FOREIGN_TABLE)
+			{
+				/*
+				 * We do need support EC filter against for foreign table, but when fixing
+				 * the cost model issue, we need to know the selecvitiy of the qual on foregin
+				 * table. However it is impossible for now to know that when use_remote_estimate = true.
+				 * see for postgresGetForeignRelSize. Since we currently only doing PoC for
+				 * this cost-model-fix algorithm, I just disable that for foregin table. At last,
+				 * we need improve the use_remote_estimate somehow to get the selectivity.
+				 */
+				continue;
+			}
+
 			rel = root->simple_rel_array[relid];
 
 			if (ef->ef_source_rel == relid)
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index d7a173b327..9153b8d296 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -1991,9 +1991,14 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
 
 	/* Check if the qual looks useful to harvest as an EquivalenceFilter */
 	if (filter_qual_list != NULL &&
+
+		// Must be an OpExpr for now.
 		is_opclause(restrictinfo->clause) &&
-		!contain_volatile_functions((Node *)restrictinfo) && // Cachable
-		restrictinfo->btreeineqopfamilies != NIL &&  /* ineq expression */
+		// Checking volatile against RestrictInfo so that the result can be cached.
+		!contain_volatile_functions((Node *)restrictinfo) &&
+
+		restrictinfo->btreeineqopfamilies != NIL && /* ineq expression */
+
 		/* simple & common enough filter, one side references one relation and the other one is a constant */
 		((bms_is_empty(restrictinfo->left_relids) && bms_get_singleton_member(restrictinfo->right_relids, &relid)) ||
 		 (bms_is_empty(restrictinfo->right_relids) && bms_get_singleton_member(restrictinfo->left_relids, &relid)))
-- 
2.37.0

---

From: Ian Lawrence Barwick <[email-masked]>
Date: Fri, 4 Nov 2022 12:02:39 +0900

> 2. Planning time degradation for trivial OLTP queries

Hi

cfbot reports the patch no longer applies [1].  As CommitFest 2022-11 is
currently underway, this would be an excellent time to update the patch.

[1] http://cfbot.cputube.org/patch_40_3524.log

Thanks

Ian Barwick

---

From: Andy Fan <[email-masked]>
Date: Tue, 8 Nov 2022 17:04:00 +0800

> currently underway, this would be an excellent time to update the patch.

Thank you Ian & Andrey for taking care of this!  I am planning to start
a new  thread for this topic in 2 weeks,  and will post an update patch
at  that time.

-- 
Best Regards
Andy Fan