Fix mishandling of equivalence-class tests in parameterized plans.

Given a three-or-more-way equivalence class, such as X.Y = Y.Y = Z.Z,
it was possible for the planner to omit one of the quals needed to
enforce that all members of the equivalence class are actually equal.
This only happened in the case of a parameterized join node for two
of the relations, that is a plan tree like

	Nested Loop
	  ->  Scan X
	  ->  Nested Loop
	    ->  Scan Y
	    ->  Scan Z
	          Filter: Z.Z = X.X

The eclass machinery normally expects to apply X.X = Y.Y when those
two relations are joined, but in this shape of plan tree they aren't
joined until the top node --- and, if the lower nested loop is marked
as parameterized by X, the top node will assume that the relevant eclass
condition(s) got pushed down into the lower node.  On the other hand,
the scan of Z assumes that it's only responsible for constraining Z.Z
to match any one of the other eclass members.  So one or another of
the required quals sometimes fell between the cracks, depending on
whether consideration of the eclass in get_joinrel_parampathinfo()
for the lower nested loop chanced to generate X.X = Y.Y or X.X = Z.Z
as the appropriate constraint there.  If it generated the latter,
it'd erroneously suppose that the Z scan would take care of matters.
To fix, force X.X = Y.Y to be generated and applied at that join node
when this case occurs.

This is *extremely* hard to hit in practice, because various planner
behaviors conspire to mask the problem; starting with the fact that the
planner doesn't really like to generate a parameterized plan of the
above shape.  (It might have been impossible to hit it before we
tweaked things to allow this plan shape for star-schema cases.)  Many
thanks to Alexander Kirkouski for submitting a reproducible test case.

The bug can be demonstrated in all branches back to 9.2 where parameterized
paths were introduced, so back-patch that far.

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 48be45dffc974a3c9818a6ba9b7e74262cd5ffa6..6e41fd039f169947bd1da3f27c45bcf93d3240d7 100644 (file)
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -987,13 +987,31 @@ generate_base_implied_equalities_broken(PlannerInfo *root,
  *
  * join_relids should always equal bms_union(outer_relids, inner_rel->relids).
  * We could simplify this function's API by computing it internally, but in
- * all current uses, the caller has the value at hand anyway.
+ * most current uses, the caller has the value at hand anyway.
  */
 List *
 generate_join_implied_equalities(PlannerInfo *root,
                                 Relids join_relids,
                                 Relids outer_relids,
                                 RelOptInfo *inner_rel)
+{
+   return generate_join_implied_equalities_for_ecs(root,
+                                                   root->eq_classes,
+                                                   join_relids,
+                                                   outer_relids,
+                                                   inner_rel);
+}
+
+/*
+ * generate_join_implied_equalities_for_ecs
+ *   As above, but consider only the listed ECs.
+ */
+List *
+generate_join_implied_equalities_for_ecs(PlannerInfo *root,
+                                        List *eclasses,
+                                        Relids join_relids,
+                                        Relids outer_relids,
+                                        RelOptInfo *inner_rel)
 {
    List       *result = NIL;
    Relids      inner_relids = inner_rel->relids;
@@ -1015,7 +1033,7 @@ generate_join_implied_equalities(PlannerInfo *root,
        nominal_join_relids = join_relids;
    }
 
-   foreach(lc, root->eq_classes)
+   foreach(lc, eclasses)
    {
        EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
        List       *sublist = NIL;

diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 3c34711ab3b18312e138ba09266b6b00366e3b3f..127f65076f53bf46b21822a14829f035c179820e 100644 (file)
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -982,6 +982,7 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
    Relids      inner_and_req;
    List       *pclauses;
    List       *eclauses;
+   List       *dropped_ecs;
    double      rows;
    ListCell   *lc;
 
@@ -1035,6 +1036,7 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
                                                required_outer,
                                                joinrel);
    /* We only want ones that aren't movable to lower levels */
+   dropped_ecs = NIL;
    foreach(lc, eclauses)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
@@ -1051,13 +1053,79 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
                                           joinrel->relids,
                                           join_and_req));
 #endif
-       if (!join_clause_is_movable_into(rinfo,
-                                        outer_path->parent->relids,
-                                        outer_and_req) &&
-           !join_clause_is_movable_into(rinfo,
-                                        inner_path->parent->relids,
-                                        inner_and_req))
-           pclauses = lappend(pclauses, rinfo);
+       if (join_clause_is_movable_into(rinfo,
+                                       outer_path->parent->relids,
+                                       outer_and_req))
+           continue;           /* drop if movable into LHS */
+       if (join_clause_is_movable_into(rinfo,
+                                       inner_path->parent->relids,
+                                       inner_and_req))
+       {
+           /* drop if movable into RHS, but remember EC for use below */
+           Assert(rinfo->left_ec == rinfo->right_ec);
+           dropped_ecs = lappend(dropped_ecs, rinfo->left_ec);
+           continue;
+       }
+       pclauses = lappend(pclauses, rinfo);
+   }
+
+   /*
+    * EquivalenceClasses are harder to deal with than we could wish, because
+    * of the fact that a given EC can generate different clauses depending on
+    * context.  Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
+    * LHS and RHS of the current join and Z is in required_outer, and further
+    * suppose that the inner_path is parameterized by both X and Z.  The code
+    * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
+    * and in the latter case will have discarded it as being movable into the
+    * RHS.  However, the EC machinery might have produced either Y.Y = X.X or
+    * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
+    * not have produced both, and we can't readily tell from here which one
+    * it did pick.  If we add no clause to this join, we'll end up with
+    * insufficient enforcement of the EC; either Z.Z or X.X will fail to be
+    * constrained to be equal to the other members of the EC.  (When we come
+    * to join Z to this X/Y path, we will certainly drop whichever EC clause
+    * is generated at that join, so this omission won't get fixed later.)
+    *
+    * To handle this, for each EC we discarded such a clause from, try to
+    * generate a clause connecting the required_outer rels to the join's LHS
+    * ("Z.Z = X.X" in the terms of the above example).  If successful, and if
+    * the clause can't be moved to the LHS, add it to the current join's
+    * restriction clauses.  (If an EC cannot generate such a clause then it
+    * has nothing that needs to be enforced here, while if the clause can be
+    * moved into the LHS then it should have been enforced within that path.)
+    *
+    * Note that we don't need similar processing for ECs whose clause was
+    * considered to be movable into the LHS, because the LHS can't refer to
+    * the RHS so there is no comparable ambiguity about what it might
+    * actually be enforcing internally.
+    */
+   if (dropped_ecs)
+   {
+       Relids      real_outer_and_req;
+
+       real_outer_and_req = bms_union(outer_path->parent->relids,
+                                      required_outer);
+       eclauses =
+           generate_join_implied_equalities_for_ecs(root,
+                                                    dropped_ecs,
+                                                    real_outer_and_req,
+                                                    required_outer,
+                                                    outer_path->parent);
+       foreach(lc, eclauses)
+       {
+           RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+           /* As above, can't quite assert this here */
+#ifdef NOT_USED
+           Assert(join_clause_is_movable_into(rinfo,
+                                              outer_path->parent->relids,
+                                              real_outer_and_req));
+#endif
+           if (!join_clause_is_movable_into(rinfo,
+                                            outer_path->parent->relids,
+                                            outer_and_req))
+               pclauses = lappend(pclauses, rinfo);
+       }
    }
 
    /*

diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 7757741c10467ad621f5be3d13ae086f4b8144e3..1adae680706aac5535cbd0d09a34786ae79f1d8b 100644 (file)
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -130,6 +130,11 @@ extern List *generate_join_implied_equalities(PlannerInfo *root,
                                 Relids join_relids,
                                 Relids outer_relids,
                                 RelOptInfo *inner_rel);
+extern List *generate_join_implied_equalities_for_ecs(PlannerInfo *root,
+                                        List *eclasses,
+                                        Relids join_relids,
+                                        Relids outer_relids,
+                                        RelOptInfo *inner_rel);
 extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
 extern void add_child_rel_equivalences(PlannerInfo *root,
                           AppendRelInfo *appinfo,

diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 8676bc9f1d364f4eb58b6c80e3e0590baf69f6e3..c33acc562e4549e0ff928f06209c5f8a26ff77b7 100644 (file)
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -2236,6 +2236,38 @@ where t4.thousand = t5.unique1 and ss.x1 = t4.tenthous and ss.x2 = t5.stringu1;
   1000
 (1 row)
 
+--
+-- regression test: check a case where we formerly missed including an EC
+-- enforcement clause because it was expected to be handled at scan level
+--
+explain (costs off)
+select a.f1, b.f1, t.thousand, t.tenthous from
+  tenk1 t,
+  (select sum(f1)+1 as f1 from int4_tbl i4a) a,
+  (select sum(f1) as f1 from int4_tbl i4b) b
+where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
+                                                      QUERY PLAN                                                       
+-----------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+   ->  Aggregate
+         ->  Seq Scan on int4_tbl i4b
+   ->  Nested Loop
+         Join Filter: ((sum(i4b.f1)) = ((sum(i4a.f1) + 1)))
+         ->  Aggregate
+               ->  Seq Scan on int4_tbl i4a
+         ->  Index Only Scan using tenk1_thous_tenthous on tenk1 t
+               Index Cond: ((thousand = (sum(i4b.f1))) AND (tenthous = ((((sum(i4a.f1) + 1)) + (sum(i4b.f1))) + 999)))
+(9 rows)
+
+select a.f1, b.f1, t.thousand, t.tenthous from
+  tenk1 t,
+  (select sum(f1)+1 as f1 from int4_tbl i4a) a,
+  (select sum(f1) as f1 from int4_tbl i4b) b
+where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
+ f1 | f1 | thousand | tenthous 
+----+----+----------+----------
+(0 rows)
+
 --
 -- Clean up
 --

diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 67c4d3956cc9b01db54c3f9e6df97593418c29f2..9e212bb169ffe8ac09e59af242e0085f897878bd 100644 (file)
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -391,6 +391,23 @@ from
   tenk1 t5
 where t4.thousand = t5.unique1 and ss.x1 = t4.tenthous and ss.x2 = t5.stringu1;
 
+--
+-- regression test: check a case where we formerly missed including an EC
+-- enforcement clause because it was expected to be handled at scan level
+--
+explain (costs off)
+select a.f1, b.f1, t.thousand, t.tenthous from
+  tenk1 t,
+  (select sum(f1)+1 as f1 from int4_tbl i4a) a,
+  (select sum(f1) as f1 from int4_tbl i4b) b
+where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
+
+select a.f1, b.f1, t.thousand, t.tenthous from
+  tenk1 t,
+  (select sum(f1)+1 as f1 from int4_tbl i4a) a,
+  (select sum(f1) as f1 from int4_tbl i4b) b
+where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
+
 
 --
 -- Clean up