8000 Fix mishandling of equivalence-class tests in parameterized plans. · prmdeveloper/postgres@72edc8f · GitHub
[go: up one dir, main page]
Skip to content

Commit 72edc8f

Browse files
tglsfdctglsfdc
committed
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.
1 parent 596f936 commit 72edc8f

File tree

5 files changed

+149
-9
lines changed

5 files changed

+149
-9
lines changed

‎src/backend/optimizer/path/equivclass.c

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -988,13 +988,31 @@ generate_base_implied_equalities_broken(PlannerInfo *root,
988988
*
989989
* join_relids should always equal bms_union(outer_relids, inner_rel->relids).
990990
* We could simplify this function's API by computing it internally, but in
991-
* all current uses, the caller has the value at hand anyway.
991+
* most current uses, the caller has the value at hand anyway.
992992
*/
993993
List *
994994
generate_join_implied_equalities(PlannerInfo *root,
995995
Relids join_relids,
996996
Relids outer_relids,
997997
RelOptInfo *inner_rel)
998+
{
999+
return generate_join_implied_equalities_for_ecs(root,
1000+
root->eq_classes,
1001+
join_relids,
1002+
outer_relids,
1003+
inner_rel);
1004+
}
1005+
1006+
/*
1007+
* generate_join_implied_equalities_for_ecs
1008+
* As above, but consider only the listed ECs.
1009+
*/
1010+
List *
1011+
generate_join_implied_equalities_for_ecs(PlannerInfo *root,
1012+
List *eclasses,
1013+
Relids join_relids,
1014+
Relids outer_relids,
1015+
RelOptInfo *inner_rel)
9981016
{
9991017
List *result = NIL;
10001018
Relids inner_relids = inner_rel->relids;
@@ -1016,7 +1034,7 @@ generate_join_implied_equalities(PlannerInfo *root,
10161034
nominal_join_relids = join_relids;
10171035
}
10181036

1019-
foreach(lc, root->eq_classes)
1037+
foreach(lc, eclasses)
10201038
{
10211039
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
10221040
List *sublist = NIL;

‎src/backend/optimizer/util/relnode.c

Lines changed: 75 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -952,6 +952,7 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
952952
Relids inner_and_req;
953953
List *pclauses;
954954
List *eclauses;
955+
List *dropped_ecs;
955956
double rows;
956957
ListCell *lc;
957958

@@ -1005,6 +1006,7 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
10051006
required_outer,
10061007
joinrel);
10071008
/* We only want ones that aren't movable to lower levels */
1009+
dropped_ecs = NIL;
10081010
foreach(lc, eclauses)
10091011
{
10101012
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
@@ -1021,13 +1023,79 @@ get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
10211023
joinrel->relids,
10221024
join_and_req));
10231025
#endif
1024-
if (!join_clause_is_movable_into(rinfo,
1025-
outer_path->parent->relids,
1026-
outer_and_req) &&
1027-
!join_clause_is_movable_into(rinfo,
1028-
inner_path->parent->relids,
1029-
inner_and_req))
1030-
pclauses = lappend(pclauses, rinfo);
1026+
if (join_clause_is_movable_into(rinfo,
1027+
outer_path->parent->relids,
1028+
outer_and_req))
1029+
continue; /* drop if movable into LHS */
1030+
if (join_clause_is_movable_into(rinfo,
1031+
inner_path->parent->relids,
1032+
inner_and_req))
1033+
{
1034+
/* drop if movable into RHS, but remember EC for use below */
1035+
Assert(rinfo->left_ec == rinfo->right_ec);
1036+
dropped_ecs = lappend(dropped_ecs, rinfo->left_ec);
1037+
continue;
1038+
}
1039+
pclauses = lappend(pclauses, rinfo);
1040+
}
1041+
1042+
/*
1043+
* EquivalenceClasses are harder to deal with than we could wish, because
1044+
* of the fact that a given EC can generate different clauses depending on
1045+
* context. Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
1046+
* LHS and RHS of the current join and Z is in required_outer, and further
1047+
* suppose that the inner_path is parameterized by both X and Z. The code
1048+
* above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
1049+
* and in the latter case will have discarded it as being movable into the
1050+
* RHS. However, the EC machinery might have produced either Y.Y = X.X or
1051+
* Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
1052+
* not have produced both, and we can't readily tell from here which one
1053+
* it did pick. If we add no clause to this join, we'll end up with
1054+
* insufficient enforcement of the EC; either Z.Z or X.X will fail to be
1055+
* constrained to be equal to the other members of the EC. (When we come
1056+
* to join Z to this X/Y path, we will certainly drop whichever EC clause
1057+
* is generated at that join, so this omission won't get fixed later.)
1058+
*
1059+
* To handle this, for each EC we discarded such a clause from, try to
1060+
* generate a clause connecting the required_outer rels to the join's LHS
1061+
* ("Z.Z = X.X" in the terms of the above example). If successful, and if
1062+
* the clause can't be moved to the LHS, add it to the current join's
1063+
* restriction clauses. (If an EC cannot generate such a clause then it
1064+
* has nothing that needs to be enforced here, while if the clause can be
1065+
* moved into the LHS then it should have been enforced within that path.)
1066+
*
1067+
* Note that we don't need similar processing for ECs whose clause was
1068+
* considered to be movable into the LHS, because the LHS can't refer to
1069+
* the RHS so there is no comparable ambiguity about what it might
1070+
* actually be enforcing internally.
1071+
*/
1072+
if (dropped_ecs)
1073+
{
1074+
Relids real_outer_and_req;
1075+
1076+
real_outer_and_req = bms_union(outer_path->parent->relids,
1077+
required_outer);
1078+
eclauses =
1079+
generate_join_implied_equalities_for_ecs(root,
1080+
dropped_ecs,
1081+
real_outer_and_req,
1082+
required_outer,
1083+
outer_path->parent);
1084+
foreach(lc, eclauses)
1085+
{
1086+
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1087+
1088+
/* As above, can't quite assert this here */
1089+
#ifdef NOT_USED
1090+
Assert(join_clause_is_movable_into(rinfo,
1091+
outer_path->parent->relids,
1092+
real_outer_and_req));
1093+
#endif
1094+
if (!join_clause_is_movable_into(rinfo,
1095+
outer_path->parent->relids,
1096+
outer_and_req))
1097+
pclauses = lappend(pclauses, rinfo);
1098+
}
10311099
}
10321100

10331101
/*

‎src/include/optimizer/paths.h

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -114,6 +114,11 @@ extern List *generate_join_implied_equalities(PlannerInfo *root,
114114
Relids join_relids,
115115
Relids outer_relids,
116116
RelOptInfo *inner_rel);
117+
extern List *generate_join_implied_equalities_for_ecs(PlannerInfo *root,
118+
List *eclasses,
119+
Relids join_relids,
120+
Relids outer_relids,
121+
RelOptInfo *inner_rel);
117122
extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
118123
extern void add_child_rel_equivalences(PlannerInfo *root,
119124
AppendRelInfo *appinfo,

‎src/test/regress/expected/join.out

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2202,6 +2202,38 @@ where t4.thousand = t5.unique1 and ss.x1 = t4.tenthous and ss.x2 = t5.stringu1;
22022202
1000
22032203
(1 row)
22042204

2205+
--
2206+
-- regression test: check a case where we formerly missed including an EC
2207+
-- enforcement clause because it was expected to be handled at scan level
2208+
--
2209+
explain (costs off)
2210+
select a.f1, b.f1, t.thousand, t.tenthous from
2211+
tenk1 t,
2212+
(select sum(f1)+1 as f1 from int4_tbl i4a) a,
2213+
(select sum(f1) as f1 from int4_tbl i4b) b
2214+
where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
2215+
QUERY PLAN
2216+
-----------------------------------------------------------------------------------------------------------------------
2217+
Nested Loop
2218+
-> Aggregate
2219+
-> Seq Scan on int4_tbl i4b
2220+
-> Nested Loop
2221+
Join Filter: ((sum(i4b.f1)) = ((sum(i4a.f1) + 1)))
2222+
-> Aggregate
2223+
-> Seq Scan on int4_tbl i4a
2224+
-> Index Only Scan using tenk1_thous_tenthous on tenk1 t
2225+
Index Cond: ((thousand = (sum(i4b.f1))) AND (tenthous = ((((sum(i4a.f1) + 1)) + (sum(i4b.f1))) + 999)))
2226+
(9 rows)
2227+
2228+
select a.f1, b.f1, t.thousand, t.tenthous from
2229+
tenk1 t,
2230+
(select sum(f1)+1 as f1 from int4_tbl i4a) a,
2231+
(select sum(f1) as f1 from int4_tbl i4b) b
2232+
where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
2233+
f1 | f1 | thousand | tenthous
2234+
----+----+----------+----------
2235+
(0 rows)
2236+
22052237
--
22062238
-- Clean up
22072239
--

‎src/test/regress/sql/join.sql

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -379,6 +379,23 @@ from
379379
tenk1 t5
380380
where t4.thousand = t5.unique1 and ss.x1 = t4.tenthous and ss.x2 = t5.stringu1;
381381

382+
--
383+
-- regression test: check a case where we formerly missed including an EC
384+
-- enforcement clause because it was expected to be handled at scan level
385+
--
386+
explain (costs off)
387+
select a.f1, b.f1, t.thousand, t.tenthous from
388+
tenk1 t,
389+
(select sum(f1)+1 as f1 from int4_tbl i4a) a,
390+
(select sum(f1) as f1 from int4_tbl i4b) b
391+
where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
392+
393+
select a.f1, b.f1, t.thousand, t.tenthous from
394+
tenk1 t,
395+
(select sum(f1)+1 as f1 from int4_tbl i4a) a,
396+
(select sum(f1) as f1 from int4_tbl i4b) b
397+
where b.f1 = t.thousand and a.f1 = b.f1 and (a.f1+b.f1+999) = t.tenthous;
398+
382399

383400
--
384401
-- Clean up

0 commit comments

Comments
 (0)
0