Re: planner missing a trick for foreign tables w/OR conditions - Mailing list pgsql-hackers

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
  --