Обсуждение: planner missing a trick for foreign tables w/OR conditions

Consider a query such as:

SELECT * FROM a, b WHERE (a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45);

If a and/or b are regular tables, the query planner will cleverly
consider the possibility of using an index on a to filter for rows
with a.x = 42 OR a.x = 44, or of using an index on b to filter for
rows where b.y = 43 OR b.z = 45.  But if they are foreign tables, this
optimization isn't considered, because we don't intrinsically know
anything about what indexes are present on the foreign side.  However,
this optimization could potentially be quite valuable.  In fact, it's
arguably more useful here for regular tables, because even if no index
is present on the foreign side, applying the condition on the remote
side might eliminate enough data transfer overhead to win.  The only
situation in which I can really see it losing is if the simplified
qual ends up eliminating too few rows to cover the remote side's
processing costs; I'm not sure how possible that is, or how to know
whether it might be the case.

To see how this can torpedo performance, run the attached SQL file on
an empty database, and then run these quereis:

explain analyze SELECT other.id, other.title, local.id, local.title
FROM other INNER JOIN local ON other.id = local.id WHERE local.title =
md5(1::text) OR (local.title = md5(3::text) AND other.id = 3);

explain analyze SELECT other.id, other.title, frgn.id, frgn.title FROM
other INNER JOIN frgn ON other.id = frgn.id WHERE frgn.title =
md5(1::text) OR (frgn.title = md5(3::text) AND other.id = 3);

Thoughts?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Mon, Dec 16, 2013 at 12:41:43PM -0500, Robert Haas wrote:
> Consider a query such as:
> 
> SELECT * FROM a, b WHERE (a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45);
> 
> If a and/or b are regular tables, the query planner will cleverly
> consider the possibility of using an index on a to filter for rows
> with a.x = 42 OR a.x = 44, or of using an index on b to filter for
> rows where b.y = 43 OR b.z = 45.  But if they are foreign tables, this
> optimization isn't considered, because we don't intrinsically know
> anything about what indexes are present on the foreign side.  However,
> this optimization could potentially be quite valuable.  In fact, it's
> arguably more useful here for regular tables, because even if no index
> is present on the foreign side, applying the condition on the remote
> side might eliminate enough data transfer overhead to win.  The only
> situation in which I can really see it losing is if the simplified
> qual ends up eliminating too few rows to cover the remote side's
> processing costs; I'm not sure how possible that is, or how to know
> whether it might be the case.
> 
> To see how this can torpedo performance, run the attached SQL file on
> an empty database, and then run these quereis:

+1 for fixing this bug :)

Cheers,
David.
-- 
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778  AIM: dfetter666  Yahoo!: dfetter
Skype: davidfetter      XMPP: david.fetter@gmail.com
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

Robert Haas <robertmhaas@gmail.com> writes:
> Consider a query such as:
> SELECT * FROM a, b WHERE (a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45);

> If a and/or b are regular tables, the query planner will cleverly
> consider the possibility of using an index on a to filter for rows
> with a.x = 42 OR a.x = 44, or of using an index on b to filter for
> rows where b.y = 43 OR b.z = 45.  But if they are foreign tables, this
> optimization isn't considered, because we don't intrinsically know
> anything about what indexes are present on the foreign side.  However,
> this optimization could potentially be quite valuable.  In fact, it's
> arguably more useful here for regular tables, because even if no index
> is present on the foreign side, applying the condition on the remote
> side might eliminate enough data transfer overhead to win.  The only
> situation in which I can really see it losing is if the simplified
> qual ends up eliminating too few rows to cover the remote side's
> processing costs; I'm not sure how possible that is, or how to know
> whether it might be the case.

> Thoughts?

The problem is that that optimization is a crock; see the comments
for create_or_index_quals().  We can't just turn it loose to CNF-ify
every OR it might find.  The case that we support at the moment is
to CNF-ify whichever single OR condition looks like the best win,
and it's hard to see how to do that without any index knowledge.

In principle, when we're using remote estimates, we could probably
ask the remote server about each possibility ... but that could be
expensive.
        regards, tom lane

On Mon, Dec 16, 2013 at 2:04 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> The problem is that that optimization is a crock; see the comments
> for create_or_index_quals().  We can't just turn it loose to CNF-ify
> every OR it might find.  The case that we support at the moment is
> to CNF-ify whichever single OR condition looks like the best win,
> and it's hard to see how to do that without any index knowledge.
>
> In principle, when we're using remote estimates, we could probably
> ask the remote server about each possibility ... but that could be
> expensive.

Could we get by without actually converting to CNF?

Suppose we define JOINQUAL-STRIP(P, B), where P is a join clause and B
is a truth value.  Something like this:

JOINQUAL-STRIP(NOT Q, B) = NOT (JOINQUAL-STRIP(Q, NOT B))
JOINQUAL-STRIP(Q1 AND Q2 AND ... AND Qn, B) = the conjunction of
JOINQUAL-STRIP(Qi, B) for all i
JOINQUAL-STRIP(Q1 OR Q2 OR ... OR Qn, B) = the disjunction of
JOINQUAL-STRIP(Qi, B) for all i

For any join clause not of one of the above forms, JOINQUAL-STRIP(P,
B) is equal to P if there are no Vars in P referring to any table
other than the one for which we're constructing baserestrictinfo, and
to B otherwise.

Given this definition, we can take each join clause P and apply
JOINQUAL-STRIP(P, true) to it.  If the result is true, forget it.  If
the result is anything else, it's a simplified version of the original
AND/OR/NOT tree that we can apply on the remote side (if it's
pushdown-safe) to pre-filter the results.  In plain English, we walk
down through AND, OR, and NOT nodes and inspect what's underneath.
Whenever we find something that references only the remote table under
consideration, we keep it as is.  If we find something that touches
any other table, we assume it's true unless we're beneath an odd
number of negations, in which case we assume it's false.

e.g. if we start with (L1 AND R1) OR NOT(L2 OR R2), where the Li
reference local vars and the Ri only remote vars, we get (true AND R1)
OR NOT(false OR R2); after some trivial simplification, this reduces
to R1 OR NOT R2, which is indeed a suitable pre-filter.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> On Mon, Dec 16, 2013 at 2:04 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The problem is that that optimization is a crock; see the comments
>> for create_or_index_quals().  We can't just turn it loose to CNF-ify
>> every OR it might find.  The case that we support at the moment is
>> to CNF-ify whichever single OR condition looks like the best win,
>> and it's hard to see how to do that without any index knowledge.

> Could we get by without actually converting to CNF?

The hard part is not extracting the partial qual.  The hard part is
trying to make sure that adding this entirely-redundant scan qual doesn't
catastrophically degrade join size estimates.  The hack of making an
inverse adjustment to the original OR clause's selectivity works, more or
less, for a single join OR condition.  I don't think it works if there's
several modified OR conditions (possibly covering different sets of
relations).
        regards, tom lane

On Mon, Dec 16, 2013 at 6:59 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Mon, Dec 16, 2013 at 2:04 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> The problem is that that optimization is a crock; see the comments
>>> for create_or_index_quals().  We can't just turn it loose to CNF-ify
>>> every OR it might find.  The case that we support at the moment is
>>> to CNF-ify whichever single OR condition looks like the best win,
>>> and it's hard to see how to do that without any index knowledge.
>
>> Could we get by without actually converting to CNF?
>
> The hard part is not extracting the partial qual.  The hard part is
> trying to make sure that adding this entirely-redundant scan qual doesn't
> catastrophically degrade join size estimates.

OK, I had a feeling that's where the problem was likely to be.  Do you
have any thoughts about a more principled way of solving this problem?

I mean, off-hand, it's not clear to me that the comments about this
being a MAJOR HACK aren't overstated.  I mean, if we expect a join
qual for {X Y} to have a given selectivity, but then we pre-filter X
with a clause that is deliberately redundant with that join qual, then
the join qual does indeed become less selective when view as applying
to the surviving rows.  This does not strike me as very much different
from the oft-encountered problem of estimating selectivity for a = 1
AND b = 1, where a and b are correlated.  Whichever qual we apply
first changes the data distribution such that the selectivity of the
second qual is not the same as it would have been when applied to the
entirety of the data.  Estimating it that way would not be a hack; it
would be reality.

Now, it might be true that frobbing what is intended as a cache based
on the knowledge that the cache will never be flushed is a hack.

> The hack of making an
> inverse adjustment to the original OR clause's selectivity works, more or
> less, for a single join OR condition.  I don't think it works if there's
> several modified OR conditions (possibly covering different sets of
> relations).

I might be missing something, but I suspect it works fine if every
path for the relation is generating the same rows.  The partial qual
is definitely going to be applied before the join qual, so the join
qual will surely be hitting only data that's been pre-filtered by the
partial qual, and so its selectivity will be correspondingly more.
Where it seems to me that you'd run in to trouble is if we created one
path that doesn't bother enforcing the partial qual (relying on the
fact that it will be applied post-join) and another path that does.
Now you've got the same selectivity estimate for the join in two cases
where the incoming data distribution is significantly different, which
is bad.

Do you see another danger?

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> On Mon, Dec 16, 2013 at 6:59 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The hard part is not extracting the partial qual.  The hard part is
>> trying to make sure that adding this entirely-redundant scan qual doesn't
>> catastrophically degrade join size estimates.

> OK, I had a feeling that's where the problem was likely to be.  Do you
> have any thoughts about a more principled way of solving this problem?
> I mean, off-hand, it's not clear to me that the comments about this
> being a MAJOR HACK aren't overstated.

Well, the business about injecting the correction by adjusting a cached
selectivity is certainly a hack, but it's not one that I think is urgent
to get rid of; I don't foresee anything that's likely to break it soon.

> I might be missing something, but I suspect it works fine if every
> path for the relation is generating the same rows.

I had been thinking it would fall down if there are several OR conditions
affecting different collections of rels, but after going through the math
again, I'm now thinking I was wrong and it does in fact work out.  As you
say, we do depend on all paths generating the same rows, but since the
extracted single-rel quals are inserted as plain baserestrictinfo quals,
that'll be true.

A bigger potential objection is that we're opening ourselves to larger
problems with estimation failures due to correlated qual conditions, but
again I'm finding that the math doesn't bear that out.  It's reasonable
to assume that our estimate for the extracted qual will be better than
our estimate for the OR as a whole, so our adjusted size estimates for
the filtered base relations are probably OK.  And the adjustment to the
OR clause selectivity means that the size estimate for the join comes
out exactly the same.  We'll actually be better off than with what is
likely to happen now, which is that people manually extract the simplified
condition and insert it into the query explicitly.  PG doesn't realize
that that's redundant and so will underestimate the join size.

So at this point I'm pretty much talked into it.  We could eliminate the
dependence on indexes entirely, and replace this code with a step that
simply tries to pull single-base-relation quals out of ORs wherever it can
find one.  You could argue that the produced quals would sometimes not be
worth testing for, but we could apply a heuristic that says to forget it
unless the estimated selectivity of the extracted qual is less than,
I dunno, 0.5 maybe.  (I wonder if it'd be worth inserting a check that
there's not already a manually-generated equivalent clause, too ...)

A very nice thing about this is we could do this step ahead of relation
size estimate setting and thus remove the redundant work that currently
happens in set_plain_rel_size when the optimization fires.  Which is
another aspect of the current code that's a hack, so getting rid of it
would be a net reduction in hackiness.
        regards, tom lane

On Tue, Dec 17, 2013 at 12:28 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I had been thinking it would fall down if there are several OR conditions
> affecting different collections of rels, but after going through the math
> again, I'm now thinking I was wrong and it does in fact work out.  As you
> say, we do depend on all paths generating the same rows, but since the
> extracted single-rel quals are inserted as plain baserestrictinfo quals,
> that'll be true.

OK.

> A bigger potential objection is that we're opening ourselves to larger
> problems with estimation failures due to correlated qual conditions, but
> again I'm finding that the math doesn't bear that out.  It's reasonable
> to assume that our estimate for the extracted qual will be better than
> our estimate for the OR as a whole, so our adjusted size estimates for
> the filtered base relations are probably OK.  And the adjustment to the
> OR clause selectivity means that the size estimate for the join comes
> out exactly the same.  We'll actually be better off than with what is
> likely to happen now, which is that people manually extract the simplified
> condition and insert it into the query explicitly.  PG doesn't realize
> that that's redundant and so will underestimate the join size.

I had not thought of that, but it seems like a valid point.

> So at this point I'm pretty much talked into it.  We could eliminate the
> dependence on indexes entirely, and replace this code with a step that
> simply tries to pull single-base-relation quals out of ORs wherever it can
> find one.  You could argue that the produced quals would sometimes not be
> worth testing for, but we could apply a heuristic that says to forget it
> unless the estimated selectivity of the extracted qual is less than,
> I dunno, 0.5 maybe.

This is an area where I think things are very different from local and
remote tables.  For a local table, the cost of transmitting a row from
one plan node to another is basically zero.  For a remote table, it's
potentially far higher, although unfortunately it's hard to know
exactly.  But if the qual is cheap to evaluate, and we're getting back
a lot of rows, I suspect even eliminating 5-10% of them could work out
to a win.  With a local table, 50% sounds like a reasonable number.

Another point to ponder is that there could be places where this
actually changes the plan significantly for the better.  Pre-filtering
one side of a join might, for example, reduce the amount of data on
one side to the point where a hash join is chosen over some other
strategy.  I don't know that this will actually help all that many
people but the best case is pretty dramatic for those it does help:
the partial qual might be almost as selective as the join condition
itself.

>  (I wonder if it'd be worth inserting a check that
> there's not already a manually-generated equivalent clause, too ...)

Sounds a little too clever IMHO.

> A very nice thing about this is we could do this step ahead of relation
> size estimate setting and thus remove the redundant work that currently
> happens in set_plain_rel_size when the optimization fires.  Which is
> another aspect of the current code that's a hack, so getting rid of it
> would be a net reduction in hackiness.

I'm not sure that would save anything measurable performance-wise, but
the hackiness reduction would be nice to have.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 17 December 2013 17:28, Tom Lane <tgl@sss.pgh.pa.us> wrote:

> So at this point I'm pretty much talked into it.  We could eliminate the
> dependence on indexes entirely, and replace this code with a step that
> simply tries to pull single-base-relation quals out of ORs wherever it can
> find one.  You could argue that the produced quals would sometimes not be
> worth testing for, but we could apply a heuristic that says to forget it
> unless the estimated selectivity of the extracted qual is less than,
> I dunno, 0.5 maybe.  (I wonder if it'd be worth inserting a check that
> there's not already a manually-generated equivalent clause, too ...)

Sounds sensible.

What surprises me is we don't have an API that allows an FDW to decide
what it can accept or not. It seems strange to have a unilateral
decision by our planner about what another planner is capable of.
Should we extend the API to allow the question to be asked?

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

Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Dec 17, 2013 at 12:28 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> (I wonder if it'd be worth inserting a check that
>> there's not already a manually-generated equivalent clause, too ...)

> Sounds a little too clever IMHO.

The argument for doing it is that we might otherwise find ourselves
degrading the plans for previously-manually-optimized queries.  On the
other hand, the existing index-driven code has probably forestalled the
need for many people to do that; at least, I don't recall seeing much
discussion of doing that sort of thing by hand.

I'm happy to leave the issue out of the first version of the patch,
anyway.
        regards, tom lane

Simon Riggs <simon@2ndQuadrant.com> writes:
> What surprises me is we don't have an API that allows an FDW to decide
> what it can accept or not. It seems strange to have a unilateral
> decision by our planner about what another planner is capable of.

Uh, what?

There's certainly missing features in our FDW APIs --- no ability to push
over joins or aggregates for instance --- but none of that has anything to
do with assumptions about what the other end is capable of.  We're just
not done inventing those APIs.
        regards, tom lane

Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Dec 17, 2013 at 12:28 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> So at this point I'm pretty much talked into it.  We could eliminate the
>> dependence on indexes entirely, and replace this code with a step that
>> simply tries to pull single-base-relation quals out of ORs wherever it can
>> find one.  You could argue that the produced quals would sometimes not be
>> worth testing for, but we could apply a heuristic that says to forget it
>> unless the estimated selectivity of the extracted qual is less than,
>> I dunno, 0.5 maybe.

> This is an area where I think things are very different from local and
> remote tables.  For a local table, the cost of transmitting a row from
> one plan node to another is basically zero.  For a remote table, it's
> potentially far higher, although unfortunately it's hard to know
> exactly.  But if the qual is cheap to evaluate, and we're getting back
> a lot of rows, I suspect even eliminating 5-10% of them could work out
> to a win.  With a local table, 50% sounds like a reasonable number.

I used 90% as a cutoff in the attached draft patch.  Not sure if it's
worth expending a lot of sweat on the point.

Preliminary testing of this makes it look like a good idea.  In
particular, it will now extract restriction clauses from ORs even if
those clauses have nothing to do with indexes, as exhibited in the
second new regression test case.  (I was unhappy to find that there were
no regression tests covering this behavior at all; though I guess that's
not so surprising given that orindxpath.c dates from before we could put
EXPLAIN output into the regression tests.)

A cosmetic issue that has to be resolved is where to put the new code.
orindxpath.c is clearly now a misnomer; in fact, I don't think that the
code in this form belongs in optimizer/path/ at all.  There's some
argument for putting it in initsplan.c, but that file is pretty big
already.  Maybe a new file in optimizer/util/?  Any thoughts on that?

Also, there's some janitorial cleanup work that remains to be done.
I believe that make_restrictinfo_from_bitmapqual is now dead code,
and generate_bitmap_or_paths could now be static-ified and probably
simplified by dropping its restriction_only option.  I've not investigated
in detail what we could get rid of once create_or_index_quals is gone.

            regards, tom lane

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 96fe50f..88a566e 100644
*** a/src/backend/optimizer/path/allpaths.c
--- b/src/backend/optimizer/path/allpaths.c
*************** set_plain_rel_size(PlannerInfo *root, Re
*** 362,378 ****

      /* Mark rel with estimated output rows, width, etc */
      set_baserel_size_estimates(root, rel);
-
-     /*
-      * Check to see if we can extract any restriction conditions from join
-      * quals that are OR-of-AND structures.  If so, add them to the rel's
-      * restriction list, and redo the above steps.
-      */
-     if (create_or_index_quals(root, rel))
-     {
-         check_partial_indexes(root, rel);
-         set_baserel_size_estimates(root, rel);
-     }
  }

  /*
--- 362,367 ----
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 606734a..0e05107 100644
*** a/src/backend/optimizer/path/indxpath.c
--- b/src/backend/optimizer/path/indxpath.c
*************** choose_bitmap_and(PlannerInfo *root, Rel
*** 1354,1360 ****
       * we can remove this limitation.  (But note that this also defends
       * against flat-out duplicate input paths, which can happen because
       * match_join_clauses_to_index will find the same OR join clauses that
!      * create_or_index_quals has pulled OR restriction clauses out of.)
       *
       * For the same reason, we reject AND combinations in which an index
       * predicate clause duplicates another clause.    Here we find it necessary
--- 1354,1361 ----
       * we can remove this limitation.  (But note that this also defends
       * against flat-out duplicate input paths, which can happen because
       * match_join_clauses_to_index will find the same OR join clauses that
!      * extract_restriction_or_clauses has pulled OR restriction clauses out
!      * of.)
       *
       * For the same reason, we reject AND combinations in which an index
       * predicate clause duplicates another clause.    Here we find it necessary
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c
index 16f29d3..5a8d73b 100644
*** a/src/backend/optimizer/path/orindxpath.c
--- b/src/backend/optimizer/path/orindxpath.c
***************
*** 15,187 ****

  #include "postgres.h"

  #include "optimizer/cost.h"
  #include "optimizer/paths.h"
  #include "optimizer/restrictinfo.h"


! /*----------
!  * create_or_index_quals
   *      Examine join OR-of-AND quals to see if any useful restriction OR
   *      clauses can be extracted.  If so, add them to the query.
   *
!  * Although a join clause must reference other relations overall,
!  * an OR of ANDs clause might contain sub-clauses that reference just this
!  * relation and can be used to build a restriction clause.
   * For example consider
   *        WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
   * We can transform this into
   *        WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
   *            AND (a.x = 42 OR a.x = 44)
   *            AND (b.y = 43 OR b.z = 45);
!  * which opens the potential to build OR indexscans on a and b.  In essence
!  * this is a partial transformation to CNF (AND of ORs format).  It is not
!  * complete, however, because we do not unravel the original OR --- doing so
!  * would usually bloat the qualification expression to little gain.
   *
   * The added quals are partially redundant with the original OR, and therefore
!  * will cause the size of the joinrel to be underestimated when it is finally
   * formed.    (This would be true of a full transformation to CNF as well; the
   * fault is not really in the transformation, but in clauselist_selectivity's
!  * inability to recognize redundant conditions.)  To minimize the collateral
!  * damage, we want to minimize the number of quals added.  Therefore we do
!  * not add every possible extracted restriction condition to the query.
!  * Instead, we search for the single restriction condition that generates
!  * the most useful (cheapest) OR indexscan, and add only that condition.
!  * This is a pretty ad-hoc heuristic, but quite useful.
!  *
!  * We can then compensate for the redundancy of the added qual by poking
!  * the recorded selectivity of the original OR clause, thereby ensuring
!  * the added qual doesn't change the estimated size of the joinrel when
!  * it is finally formed.  This is a MAJOR HACK: it depends on the fact
!  * that clause selectivities are cached and on the fact that the same
!  * RestrictInfo node will appear in every joininfo list that might be used
!  * when the joinrel is formed.    And it probably isn't right in cases where
!  * the size estimation is nonlinear (i.e., outer and IN joins).  But it
!  * beats not doing anything.
!  *
!  * NOTE: one might think this messiness could be worked around by generating
!  * the indexscan path with a small path->rows value, and not touching the
!  * rel's baserestrictinfo or rel->rows.  However, that does not work.
!  * The optimizer's fundamental design assumes that every general-purpose
!  * Path for a given relation generates the same number of rows.  Without
!  * this assumption we'd not be able to optimize solely on the cost of Paths,
!  * but would have to take number of output rows into account as well.
!  * (The parameterized-paths stuff almost fixes this, but not quite...)
!  *
!  * 'rel' is the relation entry for which quals are to be created
!  *
!  * If successful, adds qual(s) to rel->baserestrictinfo and returns TRUE.
!  * If no quals available, returns FALSE and doesn't change rel.
   *
!  * Note: check_partial_indexes() must have been run previously.
!  *----------
   */
! bool
! create_or_index_quals(PlannerInfo *root, RelOptInfo *rel)
  {
!     BitmapOrPath *bestpath = NULL;
!     RestrictInfo *bestrinfo = NULL;
!     List       *newrinfos;
!     RestrictInfo *or_rinfo;
!     Selectivity or_selec,
!                 orig_selec;
!     ListCell   *i;

!     /* Skip the whole mess if no indexes */
!     if (rel->indexlist == NIL)
          return false;

      /*
!      * Find potentially interesting OR joinclauses.  We can use any joinclause
!      * that is considered safe to move to this rel by the parameterized-path
!      * machinery, even though what we are going to do with it is not exactly a
!      * parameterized path.
       */
!     foreach(i, rel->joininfo)
      {
!         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);

!         if (restriction_is_or_clause(rinfo) &&
!             join_clause_is_movable_to(rinfo, rel))
          {
!             /*
!              * Use the generate_bitmap_or_paths() machinery to estimate the
!              * value of each OR clause.  We can use regular restriction
!              * clauses along with the OR clause contents to generate
!              * indexquals.    We pass restriction_only = true so that any
!              * sub-clauses that are actually joins will be ignored.
!              */
!             List       *orpaths;
!             ListCell   *k;
!
!             orpaths = generate_bitmap_or_paths(root, rel,
!                                                list_make1(rinfo),
!                                                rel->baserestrictinfo,
!                                                true);

!             /* Locate the cheapest OR path */
!             foreach(k, orpaths)
              {
!                 BitmapOrPath *path = (BitmapOrPath *) lfirst(k);

!                 Assert(IsA(path, BitmapOrPath));
!                 if (bestpath == NULL ||
!                     path->path.total_cost < bestpath->path.total_cost)
                  {
!                     bestpath = path;
!                     bestrinfo = rinfo;
                  }
              }
          }
!     }

!     /* Fail if no suitable clauses found */
!     if (bestpath == NULL)
!         return false;

      /*
!      * Convert the path's indexclauses structure to a RestrictInfo tree. We
!      * include any partial-index predicates so as to get a reasonable
!      * representation of what the path is actually scanning.
       */
!     newrinfos = make_restrictinfo_from_bitmapqual((Path *) bestpath,
!                                                   true, true);

!     /* It's possible we get back something other than a single OR clause */
!     if (list_length(newrinfos) != 1)
!         return false;
!     or_rinfo = (RestrictInfo *) linitial(newrinfos);
!     Assert(IsA(or_rinfo, RestrictInfo));
!     if (!restriction_is_or_clause(or_rinfo))
!         return false;

      /*
!      * OK, add it to the rel's restriction list.
       */
!     rel->baserestrictinfo = list_concat(rel->baserestrictinfo, newrinfos);

      /*
!      * Adjust the original OR clause's cached selectivity to compensate for
!      * the selectivity of the added (but redundant) lower-level qual. This
!      * should result in the join rel getting approximately the same rows
!      * estimate as it would have gotten without all these shenanigans. (XXX
!      * major hack alert ... this depends on the assumption that the
!      * selectivity will stay cached ...)
       */
      or_selec = clause_selectivity(root, (Node *) or_rinfo,
                                    0, JOIN_INNER, NULL);
!     if (or_selec > 0 && or_selec < 1)
      {
!         orig_selec = clause_selectivity(root, (Node *) bestrinfo,
!                                         0, JOIN_INNER, NULL);
!         bestrinfo->norm_selec = orig_selec / or_selec;
!         /* clamp result to sane range */
!         if (bestrinfo->norm_selec > 1)
!             bestrinfo->norm_selec = 1;
!         /* It isn't an outer join clause, so no need to adjust outer_selec */
!     }

!     /* Tell caller to recompute partial index status and rowcount estimate */
!     return true;
  }
--- 15,341 ----

  #include "postgres.h"

+ #include "optimizer/clauses.h"
  #include "optimizer/cost.h"
  #include "optimizer/paths.h"
  #include "optimizer/restrictinfo.h"

+ static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel);
+ static Expr *extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel);
+ static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
+                        Expr *orclause, RestrictInfo *join_or_rinfo);

!
! /*
!  * extract_restriction_or_clauses
   *      Examine join OR-of-AND quals to see if any useful restriction OR
   *      clauses can be extracted.  If so, add them to the query.
   *
!  * Although a join clause must reference multiple relations overall,
!  * an OR of ANDs clause might contain sub-clauses that reference just one
!  * relation and can be used to build a restriction clause for that rel.
   * For example consider
   *        WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
   * We can transform this into
   *        WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
   *            AND (a.x = 42 OR a.x = 44)
   *            AND (b.y = 43 OR b.z = 45);
!  * which allows the latter clauses to be applied during the scans of a and b,
!  * perhaps as index qualifications, and in any case reducing the number of
!  * rows arriving at the join.  In essence this is a partial transformation to
!  * CNF (AND of ORs format).  It is not complete, however, because we do not
!  * unravel the original OR --- doing so would usually bloat the qualification
!  * expression to little gain.
   *
   * The added quals are partially redundant with the original OR, and therefore
!  * would cause the size of the joinrel to be underestimated when it is finally
   * formed.    (This would be true of a full transformation to CNF as well; the
   * fault is not really in the transformation, but in clauselist_selectivity's
!  * inability to recognize redundant conditions.)  We can compensate for this
!  * redundancy by changing the cached selectivity of the original OR clause,
!  * cancelling out the (valid) reduction in the estimated sizes of the base
!  * relations so that the estimated joinrel size remains the same.  This is
!  * a MAJOR HACK: it depends on the fact that clause selectivities are cached
!  * and on the fact that the same RestrictInfo node will appear in every
!  * joininfo list that might be used when the joinrel is formed.
!  * And it doesn't work in cases where the size estimation is nonlinear
!  * (i.e., outer and IN joins).    But it beats not doing anything.
   *
!  * We examine each base relation to see if join clauses associated with it
!  * contain extractable restriction conditions.    If so, add those conditions
!  * to the rel's baserestrictinfo and update the cached selectivities of the
!  * join clauses.  Note that the same join clause will be examined afresh
!  * from the point of view of each baserel that participates in it, so its
!  * cached selectivity may get updated multiple times.
   */
! void
! extract_restriction_or_clauses(PlannerInfo *root)
  {
!     Index        rti;

!     /* Examine each baserel for potential join OR clauses */
!     for (rti = 1; rti < root->simple_rel_array_size; rti++)
!     {
!         RelOptInfo *rel = root->simple_rel_array[rti];
!         ListCell   *lc;
!
!         /* there may be empty slots corresponding to non-baserel RTEs */
!         if (rel == NULL)
!             continue;
!
!         Assert(rel->relid == rti);        /* sanity check on array */
!
!         /* ignore RTEs that are "other rels" */
!         if (rel->reloptkind != RELOPT_BASEREL)
!             continue;
!
!         /*
!          * Find potentially interesting OR joinclauses.  We can use any
!          * joinclause that is considered safe to move to this rel by the
!          * parameterized-path machinery, even though what we are going to do
!          * with it is not exactly a parameterized path.
!          *
!          * However, it seems best to ignore clauses that have been marked
!          * redundant (by setting norm_selec > 1).  That likely can't happen
!          * for OR clauses, but let's be safe.
!          */
!         foreach(lc, rel->joininfo)
!         {
!             RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
!
!             if (restriction_is_or_clause(rinfo) &&
!                 join_clause_is_movable_to(rinfo, rel) &&
!                 rinfo->norm_selec <= 1)
!             {
!                 /* Try to extract a qual for this rel only */
!                 Expr       *orclause = extract_or_clause(rinfo, rel);
!
!                 /*
!                  * If successful, decide whether we want to use the clause,
!                  * and insert it into the rel's restrictinfo list if so.
!                  */
!                 if (orclause)
!                     consider_new_or_clause(root, rel, orclause, rinfo);
!             }
!         }
!     }
! }
!
! /*
!  * Is the given primitive (non-OR) RestrictInfo safe to move to the rel?
!  */
! static bool
! is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel)
! {
!     /*
!      * We want clauses that mention the rel, and only the rel.    So in
!      * particular pseudoconstant clauses can be rejected quickly.  Then check
!      * the clause's Var membership.
!      */
!     if (rinfo->pseudoconstant)
!         return false;
!     if (!bms_equal(rinfo->clause_relids, rel->relids))
!         return false;
!
!     /* We don't want extra evaluations of any volatile functions */
!     if (contain_volatile_functions((Node *) rinfo->clause))
          return false;

+     return true;
+ }
+
+ /*
+  * Try to extract a restriction clause mentioning only "rel" from the given
+  * join OR-clause.
+  *
+  * We must be able to extract at least one qual for this rel from each of
+  * the arms of the OR, else we can't use it.
+  *
+  * Returns an OR clause (not a RestrictInfo!) pertaining to rel, or NULL
+  * if no OR clause could be extracted.
+  */
+ static Expr *
+ extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel)
+ {
+     List       *clauselist = NIL;
+     ListCell   *lc;
+
      /*
!      * Scan each arm of the input OR clause.  Notice we descend into
!      * or_rinfo->orclause, which has RestrictInfo nodes embedded below the
!      * toplevel OR/AND structure.  This is useful because we can use the info
!      * in those nodes to make is_safe_restriction_clause_for()'s checks
!      * cheaper.  We'll strip those nodes from the returned tree, though,
!      * meaning that fresh ones will be built if the clause is accepted as a
!      * restriction clause.    This might seem wasteful --- couldn't we re-use
!      * the existing RestrictInfos?    But that'd require assuming that
!      * selectivity and other cached data is computed exactly the same way for
!      * a restriction clause as for a join clause, which seems undesirable.
       */
!     Assert(or_clause((Node *) or_rinfo->orclause));
!     foreach(lc, ((BoolExpr *) or_rinfo->orclause)->args)
      {
!         Node       *orarg = (Node *) lfirst(lc);
!         List       *subclauses = NIL;

!         /* OR arguments should be ANDs or sub-RestrictInfos */
!         if (and_clause(orarg))
          {
!             List       *andargs = ((BoolExpr *) orarg)->args;
!             ListCell   *lc2;

!             foreach(lc2, andargs)
              {
!                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);

!                 Assert(IsA(rinfo, RestrictInfo));
!                 if (restriction_is_or_clause(rinfo))
                  {
!                     /*
!                      * Recurse to deal with nested OR.    Note we *must* recurse
!                      * here, this isn't just overly-tense optimization: we
!                      * have to descend far enough to find and strip all
!                      * RestrictInfos in the expression.
!                      */
!                     Expr       *suborclause;
!
!                     suborclause = extract_or_clause(rinfo, rel);
!                     if (suborclause)
!                         subclauses = lappend(subclauses, suborclause);
                  }
+                 else if (is_safe_restriction_clause_for(rinfo, rel))
+                     subclauses = lappend(subclauses, rinfo->clause);
              }
          }
!         else
!         {
!             Assert(IsA(orarg, RestrictInfo));
!             Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
!             if (is_safe_restriction_clause_for((RestrictInfo *) orarg, rel))
!                 subclauses = lappend(subclauses,
!                                      ((RestrictInfo *) orarg)->clause);
!         }

!         /*
!          * If nothing could be extracted from this arm, we can't do anything
!          * with this OR clause.
!          */
!         if (subclauses == NIL)
!             return NULL;
!
!         /*
!          * OK, add subclause(s) to the result OR.  If we found more than one,
!          * we need an AND node.
!          */
!         clauselist = lappend(clauselist, make_ands_explicit(subclauses));
!     }

      /*
!      * If we got a restriction clause from every arm, wrap them up in an OR
!      * node.  (In theory the OR node might be unnecessary, if there was only
!      * one arm --- but then the input OR node was also redundant.)
       */
!     if (clauselist != NIL)
!         return make_orclause(clauselist);
!     return NULL;
! }

! /*
!  * Consider whether a successfully-extracted restriction OR clause is
!  * actually worth using.  If so, add it to the planner's data structures,
!  * and adjust the original join clause (join_or_rinfo) to compensate.
!  */
! static void
! consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
!                        Expr *orclause, RestrictInfo *join_or_rinfo)
! {
!     RestrictInfo *or_rinfo;
!     Selectivity or_selec,
!                 orig_selec;

      /*
!      * Build a RestrictInfo from the new OR clause.  We can assume it's valid
!      * as a base restriction clause.
       */
!     or_rinfo = make_restrictinfo(orclause,
!                                  true,
!                                  false,
!                                  false,
!                                  NULL,
!                                  NULL,
!                                  NULL);

      /*
!      * Estimate its selectivity.  (We could have done this earlier, but doing
!      * it on the RestrictInfo representation allows the result to get cached,
!      * saving work later.)
       */
      or_selec = clause_selectivity(root, (Node *) or_rinfo,
                                    0, JOIN_INNER, NULL);
!
!     /*
!      * The clause is only worth adding to the query if it rejects a useful
!      * fraction of the base relation's rows; otherwise, it's just going to
!      * cause duplicate computation (since we will still have to check the
!      * original OR clause when the join is formed).  Somewhat arbitrarily, we
!      * set the selectivity threshold at 0.9.
!      */
!     if (or_selec > 0.9)
!         return;                    /* forget it */
!
!     /*
!      * OK, add it to the rel's restriction-clause list.
!      */
!     rel->baserestrictinfo = lappend(rel->baserestrictinfo, or_rinfo);
!
!     /*
!      * Adjust the original join OR clause's cached selectivity to compensate
!      * for the selectivity of the added (but redundant) lower-level qual. This
!      * should result in the join rel getting approximately the same rows
!      * estimate as it would have gotten without all these shenanigans.
!      *
!      * XXX major hack alert: this depends on the assumption that the
!      * selectivity will stay cached.
!      *
!      * XXX another major hack: we adjust only norm_selec, the cached
!      * selectivity for JOIN_INNER semantics, even though the join clause
!      * might've been an outer-join clause.  This is partly because we can't
!      * easily identify the relevant SpecialJoinInfo here, and partly because
!      * the linearity assumption we're making would fail anyway.  (If it is an
!      * outer-join clause, "rel" must be on the nullable side, else we'd not
!      * have gotten here.  So the computation of the join size is going to be
!      * quite nonlinear, and it's not clear what we ought to do with
!      * outer_selec even if we could compute its original value correctly.)
!      */
!     if (or_selec > 0)
      {
!         SpecialJoinInfo sjinfo;

!         /*
!          * Make up a SpecialJoinInfo for JOIN_INNER semantics.    (Compare
!          * approx_tuple_count() in costsize.c.)
!          */
!         sjinfo.type = T_SpecialJoinInfo;
!         sjinfo.min_lefthand = bms_difference(join_or_rinfo->clause_relids,
!                                              rel->relids);
!         sjinfo.min_righthand = rel->relids;
!         sjinfo.syn_lefthand = sjinfo.min_lefthand;
!         sjinfo.syn_righthand = sjinfo.min_righthand;
!         sjinfo.jointype = JOIN_INNER;
!         /* we don't bother trying to make the remaining fields valid */
!         sjinfo.lhs_strict = false;
!         sjinfo.delay_upper_joins = false;
!         sjinfo.join_quals = NIL;
!
!         /* Compute inner-join size */
!         orig_selec = clause_selectivity(root, (Node *) join_or_rinfo,
!                                         0, JOIN_INNER, &sjinfo);
!
!         /* And hack cached selectivity so join size remains the same */
!         join_or_rinfo->norm_selec = orig_selec / or_selec;
!         /* ensure result stays in sane range, in particular not "redundant" */
!         if (join_or_rinfo->norm_selec > 1)
!             join_or_rinfo->norm_selec = 1;
!         /* as explained above, we don't touch outer_selec */
!     }
  }
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 3a4e836..a74ba30 100644
*** a/src/backend/optimizer/plan/planmain.c
--- b/src/backend/optimizer/plan/planmain.c
*************** query_planner(PlannerInfo *root, List *t
*** 195,200 ****
--- 195,206 ----
      create_lateral_join_info(root);

      /*
+      * Look for join OR clauses that we can extract single-relation
+      * restriction OR clauses from.
+      */
+     extract_restriction_or_clauses(root);
+
+     /*
       * We should now have size estimates for every actual table involved in
       * the query, and we also know which if any have been deleted from the
       * query by join removal; so we can compute total_table_pages.
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 999adaa..5e85ba6 100644
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** extern Expr *adjust_rowcompare_for_index
*** 65,71 ****
   * orindxpath.c
   *      additional routines for indexable OR clauses
   */
! extern bool create_or_index_quals(PlannerInfo *root, RelOptInfo *rel);

  /*
   * tidpath.h
--- 65,71 ----
   * orindxpath.c
   *      additional routines for indexable OR clauses
   */
! extern void extract_restriction_or_clauses(PlannerInfo *root);

  /*
   * tidpath.h
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 85113a9..83cbde8 100644
*** a/src/test/regress/expected/join.out
--- b/src/test/regress/expected/join.out
*************** where thousand = (q1 + q2);
*** 2710,2715 ****
--- 2710,2762 ----
  (12 rows)

  --
+ -- test extraction of restriction OR clauses from join OR clause
+ -- (we used to only do this for indexable clauses)
+ --
+ explain (costs off)
+ select * from tenk1 a join tenk1 b on
+   (a.unique1 = 1 and b.unique1 = 2) or (a.unique2 = 3 and b.hundred = 4);
+                                            QUERY PLAN
+ -------------------------------------------------------------------------------------------------
+  Nested Loop
+    Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = 3) AND (b.hundred = 4)))
+    ->  Bitmap Heap Scan on tenk1 b
+          Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+          ->  BitmapOr
+                ->  Bitmap Index Scan on tenk1_unique1
+                      Index Cond: (unique1 = 2)
+                ->  Bitmap Index Scan on tenk1_hundred
+                      Index Cond: (hundred = 4)
+    ->  Materialize
+          ->  Bitmap Heap Scan on tenk1 a
+                Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
+                ->  BitmapOr
+                      ->  Bitmap Index Scan on tenk1_unique1
+                            Index Cond: (unique1 = 1)
+                      ->  Bitmap Index Scan on tenk1_unique2
+                            Index Cond: (unique2 = 3)
+ (17 rows)
+
+ explain (costs off)
+ select * from tenk1 a join tenk1 b on
+   (a.unique1 = 1 and b.unique1 = 2) or (a.unique2 = 3 and b.ten = 4);
+                                          QUERY PLAN
+ ---------------------------------------------------------------------------------------------
+  Nested Loop
+    Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = 3) AND (b.ten = 4)))
+    ->  Seq Scan on tenk1 b
+          Filter: ((unique1 = 2) OR (ten = 4))
+    ->  Materialize
+          ->  Bitmap Heap Scan on tenk1 a
+                Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
+                ->  BitmapOr
+                      ->  Bitmap Index Scan on tenk1_unique1
+                            Index Cond: (unique1 = 1)
+                      ->  Bitmap Index Scan on tenk1_unique2
+                            Index Cond: (unique2 = 3)
+ (12 rows)
+
+ --
  -- test placement of movable quals in a parameterized join tree
  --
  set effective_cache_size = '128MB';
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 718175b..2168c55 100644
*** a/src/test/regress/sql/join.sql
--- b/src/test/regress/sql/join.sql
*************** select * from
*** 706,711 ****
--- 706,723 ----
  where thousand = (q1 + q2);

  --
+ -- test extraction of restriction OR clauses from join OR clause
+ -- (we used to only do this for indexable clauses)
+ --
+
+ explain (costs off)
+ select * from tenk1 a join tenk1 b on
+   (a.unique1 = 1 and b.unique1 = 2) or (a.unique2 = 3 and b.hundred = 4);
+ explain (costs off)
+ select * from tenk1 a join tenk1 b on
+   (a.unique1 = 1 and b.unique1 = 2) or (a.unique2 = 3 and b.ten = 4);
+
+ --
  -- test placement of movable quals in a parameterized join tree
  --