Re: join removal

Robert Haas <robertmhaas@gmail.com> writes:
> On Sat, Mar 27, 2010 at 4:11 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I'm not seeing how that would occur or would matter, but the worst case
>> answer is to restart the scan of the SpecialJoinInfos from scratch any
>> time you succeed in doing a join removal.

> Well, say you have something like

> SELECT 1 FROM A LEFT JOIN (B LEFT JOIN C ON Pbc) ON Pab

> I think that the SpecialJoinInfo structure for the join between B and
> C will match the criteria I articulated upthread, but the one for the
> join between A and {B C} will not.  If C had not been in the query
> from the begining then we'd have had:

> SELECT 1 FROM A LEFT JOIN B ON Pab

> ...under which circumstances the SpecialJoinInfo would match the
> aforementioned criteria.

I experimented with this and found that you're correct: the tests on the
different SpecialJoinInfos do interact, which I hadn't believed
initially.  The reason for this is that when we find out we can remove a
particular rel, we have to remove the bits for it in other relations'
attr_needed bitmaps.  In the above example, we first discover we can
remove C.  Whatever B vars were used in Pbc will have an attr_needed
set of {B,C}, and that C bit will prevent us from deciding that B can
be removed when we are examining the upper SpecialJoinInfo (which will
not consider C to be part of either min_lefthand or min_righthand).
So we have to remove the C bits when we remove C.

Attached is an extremely quick-and-dirty, inadequately commented draft
patch that does it along the lines you are suggesting.  This was just to
see if I could get it to work at all; it's not meant for application in
anything like its current state.  However, I feel a very strong
temptation to finish it up and apply it before we enter beta.  As you
noted, this way is a lot cheaper than the original coding, whether one
focuses on the cost of failing cases or the cost when the optimization
is successful.  And if we hold it off till 9.1, then any bug fixes that
have to be made in the area later will need to be made against two
significantly different implementations, which will be a real PITA.

Things that would need to be cleaned up:

* I left join_is_removable where it was, mainly so that it was easy to
compare how much it changed for this usage (not a lot).  I'm not sure
that joinpath.c is an appropriate place for it anymore, though I can't
see any obviously better place either.  Any thoughts on that?

* The removed relation has to be taken out of the set of baserels
somehow, else for example the Assert in make_one_rel will fail.
The current hack is to change its reloptkind to RELOPT_OTHER_MEMBER_REL,
which I think is a bit unclean.  We could try deleting it from the
simple_rel_array altogether, but I'm worried that that could result in
dangling-pointer failures, since we're probably not going to go to the
trouble of removing every single reference to the rel from the planner
data structures.  A possible compromise is to invent another reloptkind
value that is only used for "dead" relations.

* It would be good to not count the removed relation in
root->total_table_pages.  If we made either of the changes suggested
above then we could move the calculation of total_table_pages down to
after remove_useless_joins and ignore the removed relation(s)
appropriately.  Otherwise I'm tempted to just subtract off the relation
size from total_table_pages on-the-fly when we remove it.

* I'm not sure yet about the adjustment of PlaceHolder bitmaps --- we
might need to break fix_placeholder_eval_levels into two steps to get
it right.

* Still need to reverse out the now-dead code from the original patch,
in particular the NoOpPath support.

Thoughts?

            regards, tom lane

Index: src/backend/optimizer/path/joinpath.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v
retrieving revision 1.131
diff -c -r1.131 joinpath.c
*** src/backend/optimizer/path/joinpath.c    22 Mar 2010 13:57:15 -0000    1.131
--- src/backend/optimizer/path/joinpath.c    28 Mar 2010 03:50:58 -0000
***************
*** 22,32 ****
  #include "optimizer/paths.h"


- static bool join_is_removable(PlannerInfo *root, RelOptInfo *joinrel,
-                   RelOptInfo *outerrel, RelOptInfo *innerrel,
-                   List *restrictlist, JoinType jointype);
- static void generate_outer_only(PlannerInfo *root, RelOptInfo *joinrel,
-                     RelOptInfo *outerrel);
  static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
                       RelOptInfo *outerrel, RelOptInfo *innerrel,
                       List *restrictlist, List *mergeclause_list,
--- 22,27 ----
***************
*** 84,109 ****
      List       *mergeclause_list = NIL;

      /*
-      * 0. Consider join removal.  This is always the most efficient strategy,
-      * so if it works, there's no need to consider anything further.
-      */
-     if (join_is_removable(root, joinrel, outerrel, innerrel,
-                           restrictlist, jointype))
-     {
-         generate_outer_only(root, joinrel, outerrel);
-         return;
-     }
-
-     /*
       * Find potential mergejoin clauses.  We can skip this if we are not
       * interested in doing a mergejoin.  However, mergejoin is currently our
       * only way of implementing full outer joins, so override mergejoin
       * disable if it's a full join.
-      *
-      * Note: do this after join_is_removable(), because this sets the
-      * outer_is_left flags in the mergejoin clauses, while join_is_removable
-      * uses those flags for its own purposes.  Currently, they set the flags
-      * the same way anyway, but let's avoid unnecessary entanglement.
       */
      if (enable_mergejoin || jointype == JOIN_FULL)
          mergeclause_list = select_mergejoin_clauses(root,
--- 79,88 ----
***************
*** 165,182 ****
   * we set the transient flag outer_is_left to identify which side is which.
   */
  static inline bool
! clause_sides_match_join(RestrictInfo *rinfo, RelOptInfo *outerrel,
!                         RelOptInfo *innerrel)
  {
!     if (bms_is_subset(rinfo->left_relids, outerrel->relids) &&
!         bms_is_subset(rinfo->right_relids, innerrel->relids))
      {
          /* lefthand side is outer */
          rinfo->outer_is_left = true;
          return true;
      }
!     else if (bms_is_subset(rinfo->left_relids, innerrel->relids) &&
!              bms_is_subset(rinfo->right_relids, outerrel->relids))
      {
          /* righthand side is outer */
          rinfo->outer_is_left = false;
--- 144,161 ----
   * we set the transient flag outer_is_left to identify which side is which.
   */
  static inline bool
! clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids,
!                         Relids innerrelids)
  {
!     if (bms_is_subset(rinfo->left_relids, outerrelids) &&
!         bms_is_subset(rinfo->right_relids, innerrelids))
      {
          /* lefthand side is outer */
          rinfo->outer_is_left = true;
          return true;
      }
!     else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
!              bms_is_subset(rinfo->right_relids, outerrelids))
      {
          /* righthand side is outer */
          rinfo->outer_is_left = false;
***************
*** 187,193 ****

  /*
   * join_is_removable
!  *      Determine whether we need not perform the join at all, because
   *      it will just duplicate its left input.
   *
   * This is true for a left join for which the join condition cannot match
--- 166,172 ----

  /*
   * join_is_removable
!  *      Determine whether we need not perform a special join at all, because
   *      it will just duplicate its left input.
   *
   * This is true for a left join for which the join condition cannot match
***************
*** 195,213 ****
   * cases, but we don't have the infrastructure to prove them.)  We also
   * have to check that the inner side doesn't generate any variables needed
   * above the join.
-  *
-  * Note: there is no need to consider the symmetrical case of duplicating the
-  * right input, because add_paths_to_joinrel() will be called with each rel
-  * on the outer side.
   */
! static bool
! join_is_removable(PlannerInfo *root,
!                   RelOptInfo *joinrel,
!                   RelOptInfo *outerrel,
!                   RelOptInfo *innerrel,
!                   List *restrictlist,
!                   JoinType jointype)
  {
      List       *clause_list = NIL;
      ListCell   *l;
      int            attroff;
--- 174,186 ----
   * cases, but we don't have the infrastructure to prove them.)  We also
   * have to check that the inner side doesn't generate any variables needed
   * above the join.
   */
! bool
! join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
  {
+     int            innerrelid;
+     RelOptInfo *innerrel;
+     Relids        joinrelids;
      List       *clause_list = NIL;
      ListCell   *l;
      int            attroff;
***************
*** 220,227 ****
       * now we just make sure there are indexes of some sort or other.  If none
       * of them are unique, join removal will still fail, just slightly later.
       */
!     if (jointype != JOIN_LEFT ||
!         innerrel->reloptkind == RELOPT_JOINREL ||
          innerrel->rtekind != RTE_RELATION ||
          innerrel->indexlist == NIL)
          return false;
--- 193,207 ----
       * now we just make sure there are indexes of some sort or other.  If none
       * of them are unique, join removal will still fail, just slightly later.
       */
!     if (sjinfo->jointype != JOIN_LEFT ||
!         sjinfo->delay_upper_joins ||
!         bms_membership(sjinfo->min_righthand) != BMS_SINGLETON)
!         return false;
!
!     innerrelid = bms_singleton_member(sjinfo->min_righthand);
!     innerrel = find_base_rel(root, innerrelid);
!
!     if (innerrel->reloptkind != RELOPT_BASEREL ||
          innerrel->rtekind != RTE_RELATION ||
          innerrel->indexlist == NIL)
          return false;
***************
*** 239,249 ****
       * theory that the system attributes are somewhat less likely to be wanted
       * and should be tested last.
       */
      for (attroff = innerrel->max_attr - innerrel->min_attr;
           attroff >= 0;
           attroff--)
      {
!         if (!bms_is_subset(innerrel->attr_needed[attroff], joinrel->relids))
              return false;
      }

--- 219,231 ----
       * theory that the system attributes are somewhat less likely to be wanted
       * and should be tested last.
       */
+     joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
+
      for (attroff = innerrel->max_attr - innerrel->min_attr;
           attroff >= 0;
           attroff--)
      {
!         if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids))
              return false;
      }

***************
*** 256,262 ****
          PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);

          if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids) &&
!             !bms_is_subset(phinfo->ph_needed, joinrel->relids))
              return false;
      }

--- 238,244 ----
          PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);

          if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids) &&
!             !bms_is_subset(phinfo->ph_needed, joinrelids))
              return false;
      }

***************
*** 267,282 ****
       * it's what we want.  The mergejoinability test also eliminates clauses
       * containing volatile functions, which we couldn't depend on.
       */
!     foreach(l, restrictlist)
      {
          RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);

          /*
           * If we find a pushed-down clause, it must have come from above the
           * outer join and it must contain references to the inner rel.    (If it
           * had only outer-rel variables, it'd have been pushed down into the
           * outer rel.)    Therefore, we can conclude that join removal is unsafe
           * without any examination of the clause contents.
           */
          if (restrictinfo->is_pushed_down)
              return false;
--- 249,270 ----
       * it's what we want.  The mergejoinability test also eliminates clauses
       * containing volatile functions, which we couldn't depend on.
       */
!     foreach(l, innerrel->joininfo)
      {
          RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);

+         /* Ignore clauses not pertinent to this join */
+         if (!bms_is_subset(restrictinfo->required_relids, joinrelids))
+             continue;
+
          /*
           * If we find a pushed-down clause, it must have come from above the
           * outer join and it must contain references to the inner rel.    (If it
           * had only outer-rel variables, it'd have been pushed down into the
           * outer rel.)    Therefore, we can conclude that join removal is unsafe
           * without any examination of the clause contents.
+          *
+          * XXX still appropriate?
           */
          if (restrictinfo->is_pushed_down)
              return false;
***************
*** 289,295 ****
          /*
           * Check if clause has the form "outer op inner" or "inner op outer".
           */
!         if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
              continue;            /* no good for these input relations */

          /* OK, add to list */
--- 277,284 ----
          /*
           * Check if clause has the form "outer op inner" or "inner op outer".
           */
!         if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
!                                      innerrel->relids))
              continue;            /* no good for these input relations */

          /* OK, add to list */
***************
*** 1031,1037 ****
          /*
           * Check if clause has the form "outer op inner" or "inner op outer".
           */
!         if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
              continue;            /* no good for these input relations */

          hashclauses = lappend(hashclauses, restrictinfo);
--- 1020,1027 ----
          /*
           * Check if clause has the form "outer op inner" or "inner op outer".
           */
!         if (!clause_sides_match_join(restrictinfo, outerrel->relids,
!                                      innerrel->relids))
              continue;            /* no good for these input relations */

          hashclauses = lappend(hashclauses, restrictinfo);
***************
*** 1216,1222 ****
          /*
           * Check if clause has the form "outer op inner" or "inner op outer".
           */
!         if (!clause_sides_match_join(restrictinfo, outerrel, innerrel))
          {
              have_nonmergeable_joinclause = true;
              continue;            /* no good for these input relations */
--- 1206,1213 ----
          /*
           * Check if clause has the form "outer op inner" or "inner op outer".
           */
!         if (!clause_sides_match_join(restrictinfo, outerrel->relids,
!                                      innerrel->relids))
          {
              have_nonmergeable_joinclause = true;
              continue;            /* no good for these input relations */
Index: src/backend/optimizer/plan/planmain.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v
retrieving revision 1.117
diff -c -r1.117 planmain.c
*** src/backend/optimizer/plan/planmain.c    2 Jan 2010 16:57:47 -0000    1.117
--- src/backend/optimizer/plan/planmain.c    28 Mar 2010 03:50:58 -0000
***************
*** 29,34 ****
--- 29,37 ----
  #include "utils/selfuncs.h"


+ static List *remove_useless_joins(PlannerInfo *root, List *joinlist);
+
+
  /*
   * query_planner
   *      Generate a path (that is, a simplified plan) for a basic query,
***************
*** 249,254 ****
--- 252,264 ----
      fix_placeholder_eval_levels(root);

      /*
+      * Remove any useless outer joins.  Ideally this would be done during
+      * jointree preprocessing, but the necessary information isn't available
+      * until now.
+      */
+     joinlist = remove_useless_joins(root, joinlist);
+
+     /*
       * Ready to do the primary planning.
       */
      final_rel = make_one_rel(root, joinlist);
***************
*** 404,406 ****
--- 414,579 ----
      *cheapest_path = cheapestpath;
      *sorted_path = sortedpath;
  }
+
+ extern bool
+ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
+ static void
+ remove_rel_from_query(PlannerInfo *root, int relid);
+ static List *
+ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
+
+ static List *
+ remove_useless_joins(PlannerInfo *root, List *joinlist)
+ {
+     ListCell   *lc;
+
+ restart:
+     foreach(lc, root->join_info_list)
+     {
+         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
+         int innerrelid;
+         int nremoved;
+
+         if (!join_is_removable(root, sjinfo))
+             continue;
+
+         /*
+          * Currently, join_is_removable can only succeed when the sjinfo's
+          * righthand is a single baserel.  Remove that rel from the joinlist.
+          */
+         innerrelid = bms_singleton_member(sjinfo->min_righthand);
+
+         remove_rel_from_query(root, innerrelid);
+
+         nremoved = 0;
+         joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
+         if (nremoved != 1)
+             elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
+
+         /*
+          * We can delete this SpecialJoinInfo too, since it's no longer of
+          * interest.
+          */
+         root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
+
+         /*
+          * Restart the scan.  This is necessary to ensure we find all removable
+          * joins independently of ordering of the join_info_list (note that
+          * removal of attr_needed bits may make a join appear removable that
+          * did not before).  Also, since we just deleted the current list
+          * cell, we'd have to have some hack to continue the list search
+          * anyway.
+          */
+         goto restart;
+     }
+
+     return joinlist;
+ }
+
+ /*
+  * Remove the target relid from the planner's data structures.
+  *
+  * We are not terribly thorough here.  We must make sure that the rel is
+  * no longer visible as a baserel, and that attributes of other baserels
+  * are no longer marked as being needed at joins involving this rel.
+  * We don't have to bother removing join quals involving the rel from the
+  * joininfo lists; they'll just get ignored since we will never form a
+  * join relation that appears to match them.
+  */
+ static void
+ remove_rel_from_query(PlannerInfo *root, int relid)
+ {
+     RelOptInfo *rel = find_base_rel(root, relid);
+     Index        rti;
+     ListCell   *l;
+
+     /*
+      * Mark the rel as an "other" rel instead of a "base" rel, since it
+      * is no longer part of the join tree.  (Could we remove it from
+      * the baserel array altogether?  Or use a dedicated reloptkind?)
+      */
+     rel->reloptkind = RELOPT_OTHER_MEMBER_REL;
+
+     /*
+      * Remove references to the rel from other baserels' attr_needed arrays.
+      */
+     for (rti = 1; rti < root->simple_rel_array_size; rti++)
+     {
+         RelOptInfo *otherrel = root->simple_rel_array[rti];
+         int            attroff;
+
+         /* there may be empty slots corresponding to non-baserel RTEs */
+         if (otherrel == NULL)
+             continue;
+
+         Assert(otherrel->relid == rti);        /* sanity check on array */
+
+         for (attroff = otherrel->max_attr - otherrel->min_attr;
+              attroff >= 0;
+              attroff--)
+         {
+             otherrel->attr_needed[attroff] =
+                 bms_del_member(otherrel->attr_needed[attroff], relid);
+         }
+     }
+
+     /*
+      * Likewise remove references from PlaceHolderVar data structures.
+      */
+     foreach(l, root->placeholder_list)
+     {
+         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
+
+         phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
+         phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
+     }
+ }
+
+ /*
+  * Remove any occurrences of the target relid from a joinlist structure.
+  *
+  * It's easiest to build a whole new list structure, so we handle it that
+  * way.  Efficiency is not a big deal here.
+  *
+  * *nremoved is incremented by the number of occurrences removed (there
+  * should be exactly one, but the caller checks that).
+  */
+ static List *
+ remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
+ {
+     List       *result = NIL;
+     ListCell   *jl;
+
+     foreach(jl, joinlist)
+     {
+         Node       *jlnode = (Node *) lfirst(jl);
+
+         if (IsA(jlnode, RangeTblRef))
+         {
+             int            varno = ((RangeTblRef *) jlnode)->rtindex;
+
+             if (varno == relid)
+                 (*nremoved)++;
+             else
+                 result = lappend(result, jlnode);
+         }
+         else if (IsA(jlnode, List))
+         {
+             /* Recurse to handle subproblem */
+             List   *sublist;
+
+             sublist = remove_rel_from_joinlist((List *) jlnode,
+                                                relid, nremoved);
+             /* Avoid including empty sub-lists in the result */
+             if (sublist)
+                 result = lappend(result, sublist);
+         }
+         else
+         {
+             elog(ERROR, "unrecognized joinlist node type: %d",
+                  (int) nodeTag(jlnode));
+         }
+     }
+
+     return result;
+ }
Index: src/test/regress/expected/join.out
===================================================================
RCS file: /cvsroot/pgsql/src/test/regress/expected/join.out,v
retrieving revision 1.44
diff -c -r1.44 join.out
*** src/test/regress/expected/join.out    22 Mar 2010 13:57:16 -0000    1.44
--- src/test/regress/expected/join.out    28 Mar 2010 03:50:59 -0000
***************
*** 2494,2499 ****
--- 2494,2531 ----
  --
  -- test join removal
  --
+ begin;
+ CREATE TEMP TABLE a (id int PRIMARY KEY, b_id int);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "a_pkey" for table "a"
+ CREATE TEMP TABLE b (id int PRIMARY KEY, c_id int);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "b_pkey" for table "b"
+ CREATE TEMP TABLE c (id int PRIMARY KEY);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "c_pkey" for table "c"
+ INSERT INTO a VALUES (0, 0), (1, NULL);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ INSERT INTO c VALUES (0), (1);
+ -- all three cases should be optimizable into a simple seqscan
+ explain (costs off) SELECT a.* FROM a LEFT JOIN b ON a.b_id = b.id;
+   QUERY PLAN
+ ---------------
+  Seq Scan on a
+ (1 row)
+
+ explain (costs off) SELECT b.* FROM b LEFT JOIN c ON b.c_id = c.id;
+   QUERY PLAN
+ ---------------
+  Seq Scan on b
+ (1 row)
+
+ explain (costs off)
+   SELECT a.* FROM a LEFT JOIN (b left join c on b.c_id = c.id)
+   ON (a.b_id = b.id);
+   QUERY PLAN
+ ---------------
+  Seq Scan on a
+ (1 row)
+
+ rollback;
  create temp table parent (k int primary key, pd int);
  NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "parent_pkey" for table "parent"
  create temp table child (k int unique, cd int);
***************
*** 2540,2542 ****
--- 2572,2595 ----
           ->  Seq Scan on child c
  (5 rows)

+ -- bug 5255: this is not optimizable by join removal
+ begin;
+ CREATE TEMP TABLE a (id int PRIMARY KEY);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "a_pkey" for table "a"
+ CREATE TEMP TABLE b (id int PRIMARY KEY, a_id int);
+ NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "b_pkey" for table "b"
+ INSERT INTO a VALUES (0), (1);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ SELECT * FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+  id | a_id | id
+ ----+------+----
+   1 |      |
+ (1 row)
+
+ SELECT b.* FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+  id | a_id
+ ----+------
+   1 |
+ (1 row)
+
+ rollback;
Index: src/test/regress/sql/join.sql
===================================================================
RCS file: /cvsroot/pgsql/src/test/regress/sql/join.sql,v
retrieving revision 1.33
diff -c -r1.33 join.sql
*** src/test/regress/sql/join.sql    22 Mar 2010 13:57:16 -0000    1.33
--- src/test/regress/sql/join.sql    28 Mar 2010 03:50:59 -0000
***************
*** 572,577 ****
--- 572,595 ----
  -- test join removal
  --

+ begin;
+
+ CREATE TEMP TABLE a (id int PRIMARY KEY, b_id int);
+ CREATE TEMP TABLE b (id int PRIMARY KEY, c_id int);
+ CREATE TEMP TABLE c (id int PRIMARY KEY);
+ INSERT INTO a VALUES (0, 0), (1, NULL);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+ INSERT INTO c VALUES (0), (1);
+
+ -- all three cases should be optimizable into a simple seqscan
+ explain (costs off) SELECT a.* FROM a LEFT JOIN b ON a.b_id = b.id;
+ explain (costs off) SELECT b.* FROM b LEFT JOIN c ON b.c_id = c.id;
+ explain (costs off)
+   SELECT a.* FROM a LEFT JOIN (b left join c on b.c_id = c.id)
+   ON (a.b_id = b.id);
+
+ rollback;
+
  create temp table parent (k int primary key, pd int);
  create temp table child (k int unique, cd int);
  insert into parent values (1, 10), (2, 20), (3, 30);
***************
*** 590,592 ****
--- 608,623 ----
    select p.*, linked from parent p
      left join (select c.*, true as linked from child c) as ss
      on (p.k = ss.k);
+
+ -- bug 5255: this is not optimizable by join removal
+ begin;
+
+ CREATE TEMP TABLE a (id int PRIMARY KEY);
+ CREATE TEMP TABLE b (id int PRIMARY KEY, a_id int);
+ INSERT INTO a VALUES (0), (1);
+ INSERT INTO b VALUES (0, 0), (1, NULL);
+
+ SELECT * FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+ SELECT b.* FROM b LEFT JOIN a ON (b.a_id = a.id) WHERE (a.id IS NULL OR a.id > 0);
+
+ rollback;