From 7dbadc3e9bfa19d638927dc4a2026caf53e94090 Mon Sep 17 00:00:00 2001 From: Richard Guo Date: Fri, 4 Sep 2026 15:39:18 +0900 Subject: [PATCH v2 1/2] Fix more duplicate qual clauses in parameterized paths Commit f836b688f ensured that at most one clone of a join clause is chosen for a parameterized path, so long as the clone variants differ textually. Two ways remained to end up enforcing the same condition more than once, which wastes execution effort and applies the clause's selectivity multiple times, underestimating the row count. If a commuting outer join nulls no Var referenced by a particular qual, the clone variants of that qual are textually identical, and the incompatible_relids test cannot tell them apart. To fix, enforce just the first surviving variant, identified by rinfo_serial. The other case is in get_joinrel_parampathinfo, where the clause-recovery pass for dropped EquivalenceClasses queries the EC machinery with a context that overlaps the preceding loop's, so the derived-clause cache can hand back a clause that that loop already accepted. To fix, skip any clause that is already present in the collected list. Also add assertions verifying that the clauses to be enforced at a join or within a parameterized path contain no duplicate rinfo_serial, to catch any remaining or future violations. Back-patch to v19, as with commit f836b688f. Author: Richard Guo Author: Tom Lane Reviewed-by: Tom Lane Discussion: https://postgr.es/m/CAMbWs4_Ezb1Lnj7BqcTQSysC6B5UFZxfhib8xr6rqpu5uqr8dA@mail.gmail.com Backpatch-through: 19 --- src/backend/optimizer/util/relnode.c | 146 +++++++++++++++++++-------- src/test/regress/expected/join.out | 55 ++++++++++ src/test/regress/sql/join.sql | 22 ++++ 3 files changed, 183 insertions(+), 40 deletions(-) diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 8862004cbad..b8539e00f08 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -63,6 +63,9 @@ static List *build_joinrel_restrictlist(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo); +#ifdef USE_ASSERT_CHECKING +static bool no_duplicate_clause_serials(List *clauses); +#endif static void build_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel); @@ -1422,6 +1425,27 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, joinrel->reltarget->width = clamp_width_est(tuple_width); } +#ifdef USE_ASSERT_CHECKING +/* + * Check that a list of restriction clauses contains no two clauses with the + * same rinfo_serial, ie, that we have not accepted more than one clone of the + * same clause for evaluation at the same plan level. + */ +static bool +no_duplicate_clause_serials(List *clauses) +{ + Bitmapset *serials = NULL; + + foreach_node(RestrictInfo, rinfo, clauses) + { + if (bms_is_member(rinfo->rinfo_serial, serials)) + return false; + serials = bms_add_member(serials, rinfo->rinfo_serial); + } + return true; +} +#endif + /* * build_joinrel_restrictlist * build_joinrel_joinlist @@ -1499,6 +1523,9 @@ build_joinrel_restrictlist(PlannerInfo *root, inner_rel, sjinfo)); + /* We should not have accepted multiple clones of the same clause */ + Assert(no_duplicate_clause_serials(result)); + return result; } @@ -1756,36 +1783,60 @@ get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel, */ joinrelids = bms_union(baserel->relids, required_outer); pclauses = NIL; + pserials = NULL; foreach(lc, baserel->joininfo) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); + if (!join_clause_is_movable_into(rinfo, + baserel->relids, + joinrelids)) + continue; + /* - * A clone clause must not be enforced here if an outer join it is - * incompatible with has already been computed below the point of - * evaluation; some other clone is the right one to apply. + * If it's a clone clause, drop variants that are incompatible with an + * outer join already computed below the point of evaluation; some + * other variant is the right one to apply. + * + * Multiple variants can survive that test under one parameterization, + * but only when they are textually identical, which happens when a + * commuting outer join nulls no Var actually referenced by the + * clause. (Otherwise, a variant's extra nullingrels put that outer + * join into its clause_relids, so being movable here means the join + * is part of the parameterization, and the lesser variant is rejected + * above.) Identical variants still differ in required_relids and + * incompatible_relids, and join-level clause selection needs all of + * them: each is the sole legal choice in some join order. Here, + * though, that distinction is not meaningful, since the same + * ParamPathInfo serves every join order that can use the path, and an + * identical variant is correct in any of them. So enforce just the + * first survivor, identifying later ones by matching rinfo_serial; + * enforcing them too would waste execution effort and apply the + * clause's selectivity multiple times. */ - if ((rinfo->has_clone || rinfo->is_clone) && - bms_overlap(rinfo->incompatible_relids, joinrelids)) - continue; + if (rinfo->has_clone || rinfo->is_clone) + { + if (bms_overlap(rinfo->incompatible_relids, joinrelids)) + continue; + if (bms_is_member(rinfo->rinfo_serial, pserials)) + continue; + } - if (join_clause_is_movable_into(rinfo, - baserel->relids, - joinrelids)) - pclauses = lappend(pclauses, rinfo); + pclauses = lappend(pclauses, rinfo); + pserials = bms_add_member(pserials, rinfo->rinfo_serial); } /* - * Add in joinclauses generated by EquivalenceClasses, too. (These - * necessarily satisfy join_clause_is_movable_into; but in assert-enabled - * builds, let's verify that.) + * Add in joinclauses generated by EquivalenceClasses, too, folding their + * serial numbers into pserials. (These clauses necessarily satisfy + * join_clause_is_movable_into; but in assert-enabled builds, let's verify + * that.) */ eqclauses = generate_join_implied_equalities(root, joinrelids, required_outer, baserel, NULL); -#ifdef USE_ASSERT_CHECKING foreach(lc, eqclauses) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); @@ -1793,18 +1844,12 @@ get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel, Assert(join_clause_is_movable_into(rinfo, baserel->relids, joinrelids)); + pserials = bms_add_member(pserials, rinfo->rinfo_serial); } -#endif pclauses = list_concat(pclauses, eqclauses); - /* Compute set of serial numbers of the enforced clauses */ - pserials = NULL; - foreach(lc, pclauses) - { - RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); - - pserials = bms_add_member(pserials, rinfo->rinfo_serial); - } + /* We should not have accepted multiple clones of the same clause */ + Assert(no_duplicate_clause_serials(pclauses)); /* Estimate the number of rows returned by the parameterized scan */ rows = get_parameterized_baserel_size(root, baserel, pclauses); @@ -1861,6 +1906,7 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel, Relids outer_and_req; Relids inner_and_req; List *pclauses; + Bitmapset *pserials; List *eclauses; List *dropped_ecs; double rows; @@ -1897,25 +1943,33 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel, inner_and_req = NULL; /* inner path does not accept parameters */ pclauses = NIL; + pserials = NULL; foreach(lc, joinrel->joininfo) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); - /* As above, reject clones incompatible with a computed outer join */ - if ((rinfo->has_clone || rinfo->is_clone) && - bms_overlap(rinfo->incompatible_relids, join_and_req)) + if (!join_clause_is_movable_into(rinfo, + joinrel->relids, + join_and_req) || + 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)) continue; - if (join_clause_is_movable_into(rinfo, - joinrel->relids, - join_and_req) && - !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); + /* As above, apply only one variant of a clone clause */ + if (rinfo->has_clone || rinfo->is_clone) + { + if (bms_overlap(rinfo->incompatible_relids, join_and_req)) + continue; + if (bms_is_member(rinfo->rinfo_serial, pserials)) + continue; + } + + pclauses = lappend(pclauses, rinfo); + pserials = bms_add_member(pserials, rinfo->rinfo_serial); } /* Consider joinclauses generated by EquivalenceClasses, too */ @@ -1974,6 +2028,12 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel, * 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.) * + * In cases where an EC needs to constrain EC members that are newly + * computable at this join, it can emit clauses that it already returned + * above and we accepted into pclauses. Hence, do a final list-membership + * check before accepting more clauses. (Pointer comparison should be + * enough to detect duplicates, since ECs cache derived clauses.) + * * 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 @@ -1998,10 +2058,13 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel, Assert(join_clause_is_movable_into(rinfo, outer_path->parent->relids, real_outer_and_req)); - if (!join_clause_is_movable_into(rinfo, - outer_path->parent->relids, - outer_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 (list_member_ptr(pclauses, rinfo)) + continue; /* drop if already accepted */ + pclauses = lappend(pclauses, rinfo); } } @@ -2012,6 +2075,9 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel, */ *restrict_clauses = list_concat(pclauses, *restrict_clauses); + /* We should not have accepted multiple clones of the same clause */ + Assert(no_duplicate_clause_serials(*restrict_clauses)); + /* If we already have a PPI for this parameterization, just return it */ if ((ppi = find_param_path_info(joinrel, required_outer))) return ppi; diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index cee3a7b1f22..afe06d3d480 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -6738,6 +6738,61 @@ select count(*) from int4_tbl t1 left join 25 (1 row) +-- +-- check that identical clone variants of an outer-join qual are not +-- enforced multiple times in a parameterized path +-- +explain (costs off) +select * from onek t1 + left join onek t2 on t1.unique1 = t2.unique1 + left join onek t3 on t2.unique1 = t3.unique1 + left join onek t4 on t3.unique1 = t4.unique1 and t3.ten = t4.ten + 0 + and t2.unique2 = t4.unique2 + 0 +where t1.unique1 < 1; + QUERY PLAN +------------------------------------------------------------ + Nested Loop Left Join + Join Filter: (t2.unique2 = (t4.unique2 + 0)) + -> Nested Loop Left Join + -> Nested Loop Left Join + -> Index Scan using onek_unique1 on onek t1 + Index Cond: (unique1 < 1) + -> Index Scan using onek_unique1 on onek t2 + Index Cond: (unique1 = t1.unique1) + -> Index Scan using onek_unique1 on onek t3 + Index Cond: (unique1 = t2.unique1) + -> Index Scan using onek_unique1 on onek t4 + Index Cond: (unique1 = t3.unique1) + Filter: (t3.ten = (ten + 0)) +(13 rows) + +explain (costs off) +select * from onek t1 + left join onek t2 on t1.unique1 = t2.unique1 + left join onek t3 on t2.unique1 = t3.unique1 + left join (onek t4 join onek t5 on t4.ten = t5.ten) + on t3.unique1 = t5.unique1 and t3.hundred = t4.unique1 + t5.two + and t2.unique2 = t4.unique2 +where t1.unique1 < 1; + QUERY PLAN +----------------------------------------------------------------------------------- + Nested Loop Left Join + -> Nested Loop Left Join + -> Nested Loop Left Join + -> Index Scan using onek_unique1 on onek t1 + Index Cond: (unique1 < 1) + -> Index Scan using onek_unique1 on onek t2 + Index Cond: (unique1 = t1.unique1) + -> Index Scan using onek_unique1 on onek t3 + Index Cond: (unique1 = t2.unique1) + -> Nested Loop + Join Filter: ((t4.ten = t5.ten) AND (t3.hundred = (t4.unique1 + t5.two))) + -> Index Scan using onek_unique2 on onek t4 + Index Cond: (unique2 = t2.unique2) + -> Index Scan using onek_unique1 on onek t5 + Index Cond: (unique1 = t3.unique1) +(15 rows) + -- -- test successful handling of full join underneath left join (bug #14105) -- diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql index b353073f21e..19f5524fa44 100644 --- a/src/test/regress/sql/join.sql +++ b/src/test/regress/sql/join.sql @@ -2424,6 +2424,28 @@ select count(*) from int4_tbl t1 left join join int4_tbl t4 on t3.cnt = t4.f1) on t2.bx = t3.cnt + t4.f1; +-- +-- check that identical clone variants of an outer-join qual are not +-- enforced multiple times in a parameterized path +-- + +explain (costs off) +select * from onek t1 + left join onek t2 on t1.unique1 = t2.unique1 + left join onek t3 on t2.unique1 = t3.unique1 + left join onek t4 on t3.unique1 = t4.unique1 and t3.ten = t4.ten + 0 + and t2.unique2 = t4.unique2 + 0 +where t1.unique1 < 1; + +explain (costs off) +select * from onek t1 + left join onek t2 on t1.unique1 = t2.unique1 + left join onek t3 on t2.unique1 = t3.unique1 + left join (onek t4 join onek t5 on t4.ten = t5.ten) + on t3.unique1 = t5.unique1 and t3.hundred = t4.unique1 + t5.two + and t2.unique2 = t4.unique2 +where t1.unique1 < 1; + -- -- test successful handling of full join underneath left join (bug #14105) -- -- 2.37.1 (Apple Git-137.1)