public inbox for [email protected]help / color / mirror / Atom feed
Re: A new strategy for pull-up correlated ANY_SUBLINK 8+ messages / 6 participants [nested] [flat]
* Re: A new strategy for pull-up correlated ANY_SUBLINK @ 2023-10-12 23:14 Alena Rybakina <[email protected]> 0 siblings, 1 reply; 8+ messages in thread From: Alena Rybakina @ 2023-10-12 23:14 UTC (permalink / raw) To: Andy Fan <[email protected]>; +Cc: pgsql-hackers; Tom Lane <[email protected]>; vignesh C <[email protected]>; Richard Guo <[email protected]>; Andrey Lepikhov <[email protected]> On 12.10.2023 10:52, Andy Fan wrote: > > Unfortunately, I found a request when sublink did not pull-up, as > in the > > examples above. I couldn't quite figure out why. > > I'm not sure what you mean with the "above", I guess it should be the > "below"? Yes, you are right) > > explain (analyze, costs off, buffers) > select b.x, b.x, a.y > from b > left join a > on b.x=a.x and > *b.t in > (select max(a0.t) * > from a a0 > where a0.x = b.x and > a0.t = b.t); > > ... > > SubPlan 2 > > > Here the sublink can't be pulled up because of its reference to > the LHS of left join, the original logic is that no matter the 'b.t > in ..' > returns the true or false, the rows in LHS will be returned. If we > pull it up to LHS, some rows in LHS will be filtered out, which > breaks its original semantics. Thanks for the explanation, it became more clear to me here. > I thought it would be: > > explain (analyze, costs off, buffers) > select b.x, b.x, a.y > from b > left join a on > b.x=a.x and > *b.t = > (select max(a0.t) * > from a a0 > where a0.x = b.x and > a0.t <= b.t); > > QUERY PLAN > --------------------------------------------------------------------------------------------------------------------- > Hash Right Join (actual time=1.181..67.927 rows=1000 loops=1) > Hash Cond: (a.x = b.x) > *Join Filter: (b.t = (SubPlan 2))* > Buffers: shared hit=3546 > -> Seq Scan on a (actual time=0.022..17.109 rows=100000 loops=1) > Buffers: shared hit=541 > -> Hash (actual time=1.065..1.068 rows=1000 loops=1) > Buckets: 4096 Batches: 1 Memory Usage: 72kB > Buffers: shared hit=5 > -> Seq Scan on b (actual time=0.049..0.401 rows=1000 > loops=1) > Buffers: shared hit=5 > SubPlan 2 > -> Result (actual time=0.025..0.025 rows=1 loops=1000) > Buffers: shared hit=3000 > InitPlan 1 (returns $2) > -> Limit (actual time=0.024..0.024 rows=1 loops=1000) > Buffers: shared hit=3000 > -> Index Only Scan Backward using a_t_x_idx on > a a0 (actual time=0.023..0.023 rows=1 loops=1000) > Index Cond: ((t IS NOT NULL) AND (t <= > b.t) AND (x = b.x)) > Heap Fetches: 1000 > Buffers: shared hit=3000 > Planning Time: 0.689 ms > Execution Time: 68.220 ms > (23 rows) > > If you noticed, it became possible after replacing the "in" > operator with "=". > > I didn't notice much difference between the 'in' and '=', maybe I > missed something? It seems to me that the expressions "=" and "IN" are equivalent here due to the fact that the aggregated subquery returns only one value, and the result with the "IN" operation can be considered as the intersection of elements on the left and right. In this query, we have some kind of set on the left, among which there will be found or not only one element on the right. In general, this expression can be considered as b=const, so push down will be applied to b and we can filter b during its scanning by the subquery's result. But I think your explanation is necessary here, that this is all possible, because we can pull up the sublink here, since filtering is allowed on the right side (the nullable side) and does not break the semantics of LHS. But in contrast, I also added two queries where pull-up is impossible and it is not done here. Otherwise if filtering was applied on the left it would be mistake. To be honest, I'm not sure if this explanation is needed in the test anymore, so I didn't add it. explain (costs off) SELECT * FROM tenk1 A LEFT JOIN tenk2 B ON A.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); QUERY PLAN ----------------------------------------------------------------- Nested Loop Left Join Join Filter: (SubPlan 2) -> Seq Scan on tenk1 a -> Materialize -> Seq Scan on tenk2 b SubPlan 2 -> Result InitPlan 1 (returns $1) -> Limit -> Index Scan using tenk2_hundred on tenk2 c Index Cond: (hundred IS NOT NULL) Filter: (odd = b.odd) (12 rows) explain (costs off) SELECT * FROM tenk1 A LEFT JOIN tenk2 B ON A.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd)); QUERY PLAN ----------------------------------- Nested Loop Left Join Join Filter: (hashed SubPlan 1) -> Seq Scan on tenk1 a -> Materialize -> Seq Scan on tenk2 b SubPlan 1 -> HashAggregate Group Key: c.odd -> Seq Scan on tenk2 c (9 rows) > I took the liberty of adding this to your patch and added myself > as reviewer, if you don't mind. > > Sure, the patch after your modification looks better than the original. > I'm not sure how the test case around "because of got one row" is > relevant to the current changes. After we reach to some agreement > on the above discussion, I think v4 is good for committer to review! Thank you!) I am ready to discuss it. -- Regards, Alena Rybakina Attachments: [text/x-patch] pull-up.diff (3.7K, ../../[email protected]/3-pull-up.diff) download | inline diff: diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out index b70b346696d..0b8f28b157f 100644 --- a/src/test/regress/expected/subselect.out +++ b/src/test/regress/expected/subselect.out @@ -2028,7 +2028,7 @@ ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); -> Seq Scan on tenk2 b (11 rows) --- we can pull up the aggregate sublink into the subquery scan because of got one row. +-- we can pull up the aggregate sublink into RHS of a left join. explain (costs off) SELECT * FROM tenk1 A LEFT JOIN tenk2 B ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); @@ -2052,7 +2052,6 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); Filter: (odd = b.odd) (16 rows) --- we can pull up the aggregate sublink into the JoinExpr. explain (costs off) SELECT * FROM tenk1 A LEFT JOIN tenk2 B ON B.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd)); @@ -2071,3 +2070,39 @@ ON B.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd)); -> Seq Scan on tenk2 c (11 rows) +-- we can't pull up the aggregate sublink into LHS of a left join. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON A.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +----------------------------------------------------------------- + Nested Loop Left Join + Join Filter: (SubPlan 2) + -> Seq Scan on tenk1 a + -> Materialize + -> Seq Scan on tenk2 b + SubPlan 2 + -> Result + InitPlan 1 (returns $1) + -> Limit + -> Index Scan using tenk2_hundred on tenk2 c + Index Cond: (hundred IS NOT NULL) + Filter: (odd = b.odd) +(12 rows) + +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON A.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd)); + QUERY PLAN +----------------------------------- + Nested Loop Left Join + Join Filter: (hashed SubPlan 1) + -> Seq Scan on tenk1 a + -> Materialize + -> Seq Scan on tenk2 b + SubPlan 1 + -> HashAggregate + Group Key: c.odd + -> Seq Scan on tenk2 c +(9 rows) + diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql index 5d33eb39baa..c02513c4989 100644 --- a/src/test/regress/sql/subselect.sql +++ b/src/test/regress/sql/subselect.sql @@ -1001,12 +1001,20 @@ explain (costs off) SELECT * FROM tenk1 A INNER JOIN tenk2 B ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); --- we can pull up the aggregate sublink into the subquery scan because of got one row. +-- we can pull up the aggregate sublink into RHS of a left join. explain (costs off) SELECT * FROM tenk1 A LEFT JOIN tenk2 B ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); --- we can pull up the aggregate sublink into the JoinExpr. explain (costs off) SELECT * FROM tenk1 A LEFT JOIN tenk2 B -ON B.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd)); \ No newline at end of file +ON B.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd)); + +-- we can't pull up the aggregate sublink into LHS of a left join. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON A.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); + +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON A.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd)); \ No newline at end of file ^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: A new strategy for pull-up correlated ANY_SUBLINK @ 2023-10-13 07:04 Andy Fan <[email protected]> parent: Alena Rybakina <[email protected]> 0 siblings, 2 replies; 8+ messages in thread From: Andy Fan @ 2023-10-13 07:04 UTC (permalink / raw) To: Alena Rybakina <[email protected]>; +Cc: pgsql-hackers; Tom Lane <[email protected]>; vignesh C <[email protected]>; Richard Guo <[email protected]>; Andrey Lepikhov <[email protected]> > > It seems to me that the expressions "=" and "IN" are equivalent here due > to the fact that the aggregated subquery returns only one value, and the > result with the "IN" operation can be considered as the intersection of > elements on the left and right. In this query, we have some kind of set on > the left, among which there will be found or not only one element on the > right. > Yes, they are equivalent at the final result, but there are some differences at the execution level. the '=' case will be transformed to a Subplan whose subPlanType is EXPR_SUBLINK, so if there is more than 1 rows is returned in the subplan, error will be raised. select * from tenk1 where ten = (select ten from tenk1 i where i.two = tenk1.two ); ERROR: more than one row returned by a subquery used as an expression However the IN case would not. select * from tenk1 where ten = (select ten from tenk1 i where i.two = tenk1.two ) is OK. I think the test case you added is not related to this feature. the difference is there even without the patch. so I kept the code you changed, but not for the test case. I took the liberty of adding this to your patch and added myself as >> reviewer, if you don't mind. >> > Sure, the patch after your modification looks better than the original. > I'm not sure how the test case around "because of got one row" is > relevant to the current changes. After we reach to some agreement > on the above discussion, I think v4 is good for committer to review! > > > Thank you!) I am ready to discuss it. > Actually I meant to discuss the "Unfortunately, I found a request..", looks we have reached an agreement there:) -- Best Regards Andy Fan ^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: A new strategy for pull-up correlated ANY_SUBLINK @ 2023-10-13 07:29 Andy Fan <[email protected]> parent: Andy Fan <[email protected]> 1 sibling, 0 replies; 8+ messages in thread From: Andy Fan @ 2023-10-13 07:29 UTC (permalink / raw) To: Tom Lane <[email protected]>; Alena Rybakina <[email protected]>; +Cc: pgsql-hackers; vignesh C <[email protected]>; Richard Guo <[email protected]>; Andrey Lepikhov <[email protected]> Hi Tom, Would you like to have a look at this? The change is not big and the optimization has also been asked for many times. The attached is the v5 version and I also try my best to write a good commit message. Here is the commit fest entry: https://commitfest.postgresql.org/45/4268/ Attachments: [application/octet-stream] v5-0001-Pull-up-ANY-SUBLINK-with-the-necessary-lateral-su.patch (15.0K, ../../CAKU4AWrbNbgDHkCgF7=g_gHKKJS=SsPwY9ssQkQdt0_jGT9gJQ@mail.gmail.com/3-v5-0001-Pull-up-ANY-SUBLINK-with-the-necessary-lateral-su.patch) download | inline diff: From 4ba98ddafde4269a2e2897ac0167d82a05067f56 Mon Sep 17 00:00:00 2001 From: Andy Fan <[email protected]> Date: Fri, 13 Oct 2023 14:39:34 +0800 Subject: [PATCH v5] Pull up ANY-SUBLINK with the necessary lateral support. For ANY-SUBLINK, we adopted a two-stage pull-up approach to handle different types of scenarios. In the first stage, the sublink is pulled up as a subquery. Because of this, when writing this code, we did not have the ability to perform lateral joins, and therefore, we were unable to pull up Var with varlevelsup=1. Now that we have the ability to use lateral joins, we can eliminate this limitation. Author: Andy Fan <[email protected]> Reviewed-by: Tom Lane <[email protected]> Reviewed-by: Richard Guo <[email protected]> Reviewed-by: Alena Rybakina <[email protected]> Reviewed-by: Andrey Lepikhov <[email protected]> --- .../postgres_fdw/expected/postgres_fdw.out | 6 +- contrib/postgres_fdw/sql/postgres_fdw.sql | 4 +- src/backend/optimizer/plan/subselect.c | 15 ++- src/test/regress/expected/join.out | 14 +-- src/test/regress/expected/subselect.out | 102 ++++++++++++++++++ src/test/regress/sql/join.sql | 8 +- src/test/regress/sql/subselect.sql | 32 ++++++ 7 files changed, 161 insertions(+), 20 deletions(-) diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index 144c114d0fe..932a18624a8 100644 --- a/contrib/postgres_fdw/expected/postgres_fdw.out +++ b/contrib/postgres_fdw/expected/postgres_fdw.out @@ -11633,7 +11633,7 @@ CREATE FOREIGN TABLE foreign_tbl (b int) CREATE FOREIGN TABLE foreign_tbl2 () INHERITS (foreign_tbl) SERVER loopback OPTIONS (table_name 'base_tbl'); EXPLAIN (VERBOSE, COSTS OFF) -SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); +SELECT a FROM base_tbl WHERE (a, random() > 0) IN (SELECT a, random() > 0 FROM foreign_tbl); QUERY PLAN ----------------------------------------------------------------------------- Seq Scan on public.base_tbl @@ -11641,7 +11641,7 @@ SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); Filter: (SubPlan 1) SubPlan 1 -> Result - Output: base_tbl.a + Output: base_tbl.a, (random() > '0'::double precision) -> Append -> Async Foreign Scan on public.foreign_tbl foreign_tbl_1 Remote SQL: SELECT NULL FROM public.base_tbl @@ -11649,7 +11649,7 @@ SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); Remote SQL: SELECT NULL FROM public.base_tbl (11 rows) -SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); +SELECT a FROM base_tbl WHERE (a, random() > 0) IN (SELECT a, random() > 0 FROM foreign_tbl); a --- 1 diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql index a303bfb322d..033b5b815da 100644 --- a/contrib/postgres_fdw/sql/postgres_fdw.sql +++ b/contrib/postgres_fdw/sql/postgres_fdw.sql @@ -3854,8 +3854,8 @@ CREATE FOREIGN TABLE foreign_tbl2 () INHERITS (foreign_tbl) SERVER loopback OPTIONS (table_name 'base_tbl'); EXPLAIN (VERBOSE, COSTS OFF) -SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); -SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); +SELECT a FROM base_tbl WHERE (a, random() > 0) IN (SELECT a, random() > 0 FROM foreign_tbl); +SELECT a FROM base_tbl WHERE (a, random() > 0) IN (SELECT a, random() > 0 FROM foreign_tbl); -- Clean up DROP FOREIGN TABLE foreign_tbl CASCADE; diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index 7a9fe88fec3..f46ec3d1826 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -1278,14 +1278,21 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, List *subquery_vars; Node *quals; ParseState *pstate; + Relids sub_ref_outer_relids = NULL; + bool use_lateral = false; Assert(sublink->subLinkType == ANY_SUBLINK); /* - * The sub-select must not refer to any Vars of the parent query. (Vars of - * higher levels should be okay, though.) + * If the sub-select refers to any Vars of the parent query, we so let's + * considering it as LATERAL. (Vars of higher levels don't matter here.) */ - if (contain_vars_of_level((Node *) subselect, 1)) + sub_ref_outer_relids = pull_varnos_of_level(NULL, (Node *) subselect, 1); + + use_lateral = !bms_is_empty(sub_ref_outer_relids) && + bms_is_subset(sub_ref_outer_relids, available_rels); + + if (!use_lateral && !bms_is_empty(sub_ref_outer_relids)) return NULL; /* @@ -1323,7 +1330,7 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, nsitem = addRangeTableEntryForSubquery(pstate, subselect, makeAlias("ANY_subquery", NIL), - false, + use_lateral, false); rte = nsitem->p_rte; parse->rtable = lappend(parse->rtable, rte); diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index b95d30f6586..156aca128ab 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -5251,7 +5251,7 @@ reset enable_nestloop; explain (costs off) select a.unique1, b.unique2 from onek a left join onek b on a.unique1 = b.unique2 - where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1); + where (b.unique2, random() > 0) = any (select q1, random() > 0 from int8_tbl c where c.q1 < b.unique1); QUERY PLAN ---------------------------------------------------------- Hash Join @@ -5267,7 +5267,7 @@ select a.unique1, b.unique2 select a.unique1, b.unique2 from onek a left join onek b on a.unique1 = b.unique2 - where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1); + where (b.unique2, random() > 0) = any (select q1, random() > 0 from int8_tbl c where c.q1 < b.unique1); unique1 | unique2 ---------+--------- 123 | 123 @@ -7173,12 +7173,12 @@ select * from (values (0), (1)) v(id), lateral (select * from int8_tbl t1, lateral (select * from (select * from int8_tbl t2 - where q1 = any (select q2 from int8_tbl t3 + where (q1, random() > 0) = any (select q2, random() > 0 from int8_tbl t3 where q2 = (select greatest(t1.q1,t2.q2)) and (select v.id=0)) offset 0) ss2) ss where t1.q1 = ss.q2) ss0; - QUERY PLAN ----------------------------------------------------------------------- + QUERY PLAN +------------------------------------------------------------------------------- Nested Loop Output: "*VALUES*".column1, t1.q1, t1.q2, ss2.q1, ss2.q2 -> Seq Scan on public.int8_tbl t1 @@ -7195,7 +7195,7 @@ lateral (select * from int8_tbl t1, Filter: (SubPlan 3) SubPlan 3 -> Result - Output: t3.q2 + Output: t3.q2, (random() > '0'::double precision) One-Time Filter: $4 InitPlan 1 (returns $2) -> Result @@ -7212,7 +7212,7 @@ select * from (values (0), (1)) v(id), lateral (select * from int8_tbl t1, lateral (select * from (select * from int8_tbl t2 - where q1 = any (select q2 from int8_tbl t3 + where (q1, random() > 0) = any (select q2, random() > 0 from int8_tbl t3 where q2 = (select greatest(t1.q1,t2.q2)) and (select v.id=0)) offset 0) ss2) ss where t1.q1 = ss.q2) ss0; diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out index a3a4d03d104..17df6b5dc9c 100644 --- a/src/test/regress/expected/subselect.out +++ b/src/test/regress/expected/subselect.out @@ -1926,3 +1926,105 @@ select * from x for update; Output: subselect_tbl.f1, subselect_tbl.f2, subselect_tbl.f3 (2 rows) +-- Pull-up the direct-correlated ANY_SUBLINK +explain (costs off) +select * from tenk1 A where hundred in (select hundred from tenk2 B where B.odd = A.odd); + QUERY PLAN +------------------------------------------------------------ + Hash Join + Hash Cond: ((a.odd = b.odd) AND (a.hundred = b.hundred)) + -> Seq Scan on tenk1 a + -> Hash + -> HashAggregate + Group Key: b.odd, b.hundred + -> Seq Scan on tenk2 b +(7 rows) + +explain (costs off) +select * from tenk1 A where exists +(select 1 from tenk2 B +where A.hundred in (select C.hundred FROM tenk2 C +WHERE c.odd = b.odd)); + QUERY PLAN +--------------------------------- + Nested Loop Semi Join + Join Filter: (SubPlan 1) + -> Seq Scan on tenk1 a + -> Materialize + -> Seq Scan on tenk2 b + SubPlan 1 + -> Seq Scan on tenk2 c + Filter: (odd = b.odd) +(8 rows) + +-- we should only try to pull up the sublink into RHS of a left join +-- but a.hundred is not avaiable. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +--------------------------------- + Nested Loop Left Join + Join Filter: (SubPlan 1) + -> Seq Scan on tenk1 a + -> Materialize + -> Seq Scan on tenk2 b + SubPlan 1 + -> Seq Scan on tenk2 c + Filter: (odd = b.odd) +(8 rows) + +-- we should only try to pull up the sublink into RHS of a left join +-- but a.odd is not avaiable for this. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = a.odd); + QUERY PLAN +--------------------------------- + Nested Loop Left Join + Join Filter: (SubPlan 1) + -> Seq Scan on tenk1 a + -> Materialize + -> Seq Scan on tenk2 b + SubPlan 1 + -> Seq Scan on tenk2 c + Filter: (odd = a.odd) +(8 rows) + +-- should be able to pull up since all the references is available +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +------------------------------------------------------------------------ + Nested Loop Left Join + -> Seq Scan on tenk1 a + -> Materialize + -> Hash Join + Hash Cond: ((b.odd = c.odd) AND (b.hundred = c.hundred)) + -> Seq Scan on tenk2 b + -> Hash + -> HashAggregate + Group Key: c.odd, c.hundred + -> Seq Scan on tenk2 c +(10 rows) + +-- we can pull up the sublink into the inner JoinExpr. +explain (costs off) +SELECT * FROM tenk1 A INNER JOIN tenk2 B +ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +------------------------------------------------- + Hash Join + Hash Cond: (c.odd = b.odd) + -> Hash Join + Hash Cond: (a.hundred = c.hundred) + -> Seq Scan on tenk1 a + -> Hash + -> HashAggregate + Group Key: c.odd, c.hundred + -> Seq Scan on tenk2 c + -> Hash + -> Seq Scan on tenk2 b +(11 rows) + diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql index 3e5032b04dd..2121caf7e3e 100644 --- a/src/test/regress/sql/join.sql +++ b/src/test/regress/sql/join.sql @@ -1852,11 +1852,11 @@ reset enable_nestloop; explain (costs off) select a.unique1, b.unique2 from onek a left join onek b on a.unique1 = b.unique2 - where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1); + where (b.unique2, random() > 0) = any (select q1, random() > 0 from int8_tbl c where c.q1 < b.unique1); select a.unique1, b.unique2 from onek a left join onek b on a.unique1 = b.unique2 - where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1); + where (b.unique2, random() > 0) = any (select q1, random() > 0 from int8_tbl c where c.q1 < b.unique1); -- -- test full-join strength reduction @@ -2578,7 +2578,7 @@ select * from (values (0), (1)) v(id), lateral (select * from int8_tbl t1, lateral (select * from (select * from int8_tbl t2 - where q1 = any (select q2 from int8_tbl t3 + where (q1, random() > 0) = any (select q2, random() > 0 from int8_tbl t3 where q2 = (select greatest(t1.q1,t2.q2)) and (select v.id=0)) offset 0) ss2) ss where t1.q1 = ss.q2) ss0; @@ -2587,7 +2587,7 @@ select * from (values (0), (1)) v(id), lateral (select * from int8_tbl t1, lateral (select * from (select * from int8_tbl t2 - where q1 = any (select q2 from int8_tbl t3 + where (q1, random() > 0) = any (select q2, random() > 0 from int8_tbl t3 where q2 = (select greatest(t1.q1,t2.q2)) and (select v.id=0)) offset 0) ss2) ss where t1.q1 = ss.q2) ss0; diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql index bd2e39efd48..49ce5fc99a8 100644 --- a/src/test/regress/sql/subselect.sql +++ b/src/test/regress/sql/subselect.sql @@ -968,3 +968,35 @@ select * from (with x as (select 2 as y) select * from x) ss; explain (verbose, costs off) with x as (select * from subselect_tbl) select * from x for update; + +-- Pull-up the direct-correlated ANY_SUBLINK +explain (costs off) +select * from tenk1 A where hundred in (select hundred from tenk2 B where B.odd = A.odd); + +explain (costs off) +select * from tenk1 A where exists +(select 1 from tenk2 B +where A.hundred in (select C.hundred FROM tenk2 C +WHERE c.odd = b.odd)); + +-- we should only try to pull up the sublink into RHS of a left join +-- but a.hundred is not avaiable. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + +-- we should only try to pull up the sublink into RHS of a left join +-- but a.odd is not avaiable for this. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = a.odd); + +-- should be able to pull up since all the references is available +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + +-- we can pull up the sublink into the inner JoinExpr. +explain (costs off) +SELECT * FROM tenk1 A INNER JOIN tenk2 B +ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); -- 2.21.0 ^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: A new strategy for pull-up correlated ANY_SUBLINK @ 2023-10-13 08:39 Alena Rybakina <[email protected]> parent: Andy Fan <[email protected]> 1 sibling, 1 reply; 8+ messages in thread From: Alena Rybakina @ 2023-10-13 08:39 UTC (permalink / raw) To: Andy Fan <[email protected]>; +Cc: pgsql-hackers; Tom Lane <[email protected]>; vignesh C <[email protected]>; Richard Guo <[email protected]>; Andrey Lepikhov <[email protected]> On 13.10.2023 10:04, Andy Fan wrote: > > It seems to me that the expressions "=" and "IN" are equivalent > here due to the fact that the aggregated subquery returns only one > value, and the result with the "IN" operation can be considered as > the intersection of elements on the left and right. In this query, > we have some kind of set on the left, among which there will be > found or not only one element on the right. > > > Yes, they are equivalent at the final result, but there are some > differences at the execution level. the '=' case will be transformed > to a Subplan whose subPlanType is EXPR_SUBLINK, so if there > is more than 1 rows is returned in the subplan, error will be raised. > > select * from tenk1 where > ten = (select ten from tenk1 i where i.two = tenk1.two ); > > ERROR: more than one row returned by a subquery used as an expression > > However the IN case would not. > select * from tenk1 where > ten = (select ten from tenk1 i where i.two = tenk1.two ) is OK. > > I think the test case you added is not related to this feature. the > difference is there even without the patch. so I kept the code > you changed, but not for the test case. Yes, I understand and agree with you that we should delete the last queries, except to one. The query below have a different result compared to master, and it is correct. Without your patch: explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); QUERY PLAN ----------------------------------------------------------------------------- Nested Loop Left Join -> Seq Scan on tenk1 a -> Materialize -> Seq Scan on tenk2 b Filter: (SubPlan 2) SubPlan 2 -> Result InitPlan 1 (returns $1) -> Limit -> Index Scan using tenk2_hundred on tenk2 c Index Cond: (hundred IS NOT NULL) Filter: (odd = b.odd) (12 rows) After your patch: postgres=# explain (costs off) SELECT * FROM tenk1 A LEFT JOIN tenk2 B ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); QUERY PLAN -------------------------------------------------------------- Nested Loop Left Join -> Seq Scan on tenk1 a -> Materialize -> Nested Loop -> Seq Scan on tenk2 b *-> Subquery Scan on "ANY_subquery" Filter: (b.hundred = "ANY_subquery".min)* -> Aggregate -> Seq Scan on tenk2 c Filter: (odd = b.odd) (10 rows) > >> I took the liberty of adding this to your patch and added >> myself as reviewer, if you don't mind. >> >> Sure, the patch after your modification looks better than the >> original. >> I'm not sure how the test case around "because of got one row" is >> relevant to the current changes. After we reach to some agreement >> on the above discussion, I think v4 is good for committer to review! > > Thank you!) I am ready to discuss it. > > Actually I meant to discuss the "Unfortunately, I found a request..", > looks > we have reached an agreement there:) > Yes, we have) -- Regards, Alena Rybakina Attachments: [text/x-patch] pull-up.diff (2.1K, ../../[email protected]/3-pull-up.diff) download | inline diff: diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out index 17df6b5dc9c..e41b728df83 100644 --- a/src/test/regress/expected/subselect.out +++ b/src/test/regress/expected/subselect.out @@ -2028,3 +2028,27 @@ ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); -> Seq Scan on tenk2 b (11 rows) +-- we can pull up the aggregate sublink into RHS of a left join. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +--------------------------------------------------------------------------------------- + Nested Loop Left Join + -> Seq Scan on tenk1 a + -> Materialize + -> Nested Loop + -> Seq Scan on tenk2 b + -> Memoize + Cache Key: b.hundred, b.odd + Cache Mode: binary + -> Subquery Scan on "ANY_subquery" + Filter: (b.hundred = "ANY_subquery".min) + -> Result + InitPlan 1 (returns $1) + -> Limit + -> Index Scan using tenk2_hundred on tenk2 c + Index Cond: (hundred IS NOT NULL) + Filter: (odd = b.odd) +(16 rows) + diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql index 49ce5fc99a8..2f3601a0582 100644 --- a/src/test/regress/sql/subselect.sql +++ b/src/test/regress/sql/subselect.sql @@ -1000,3 +1000,8 @@ ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); explain (costs off) SELECT * FROM tenk1 A INNER JOIN tenk2 B ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + +-- we can pull up the aggregate sublink into RHS of a left join. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); \ No newline at end of file ^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: A new strategy for pull-up correlated ANY_SUBLINK @ 2024-01-26 12:46 vignesh C <[email protected]> parent: Alena Rybakina <[email protected]> 0 siblings, 1 reply; 8+ messages in thread From: vignesh C @ 2024-01-26 12:46 UTC (permalink / raw) To: Alena Rybakina <[email protected]>; +Cc: Andy Fan <[email protected]>; pgsql-hackers; Tom Lane <[email protected]>; Richard Guo <[email protected]>; Andrey Lepikhov <[email protected]> On Fri, 13 Oct 2023 at 14:09, Alena Rybakina <[email protected]> wrote: > > On 13.10.2023 10:04, Andy Fan wrote: >> >> It seems to me that the expressions "=" and "IN" are equivalent here due to the fact that the aggregated subquery returns only one value, and the result with the "IN" operation can be considered as the intersection of elements on the left and right. In this query, we have some kind of set on the left, among which there will be found or not only one element on the right. > > > Yes, they are equivalent at the final result, but there are some > differences at the execution level. the '=' case will be transformed > to a Subplan whose subPlanType is EXPR_SUBLINK, so if there > is more than 1 rows is returned in the subplan, error will be raised. > > select * from tenk1 where > ten = (select ten from tenk1 i where i.two = tenk1.two ); > > ERROR: more than one row returned by a subquery used as an expression > > However the IN case would not. > select * from tenk1 where > ten = (select ten from tenk1 i where i.two = tenk1.two ) is OK. > > > I think the test case you added is not related to this feature. the > difference is there even without the patch. so I kept the code > you changed, but not for the test case. > > Yes, I understand and agree with you that we should delete the last queries, except to one. > > The query below have a different result compared to master, and it is correct. > > > Without your patch: > > explain (costs off) > +SELECT * FROM tenk1 A LEFT JOIN tenk2 B > ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); > QUERY PLAN > ----------------------------------------------------------------------------- > Nested Loop Left Join > -> Seq Scan on tenk1 a > -> Materialize > -> Seq Scan on tenk2 b > Filter: (SubPlan 2) > SubPlan 2 > -> Result > InitPlan 1 (returns $1) > -> Limit > -> Index Scan using tenk2_hundred on tenk2 c > Index Cond: (hundred IS NOT NULL) > Filter: (odd = b.odd) > (12 rows) > > > After your patch: > > postgres=# explain (costs off) > SELECT * FROM tenk1 A LEFT JOIN tenk2 B > ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); > > QUERY PLAN > -------------------------------------------------------------- > Nested Loop Left Join > -> Seq Scan on tenk1 a > -> Materialize > -> Nested Loop > -> Seq Scan on tenk2 b > -> Subquery Scan on "ANY_subquery" > Filter: (b.hundred = "ANY_subquery".min) > -> Aggregate > -> Seq Scan on tenk2 c > Filter: (odd = b.odd) > (10 rows) > > >>> I took the liberty of adding this to your patch and added myself as reviewer, if you don't mind. >> >> Sure, the patch after your modification looks better than the original. >> I'm not sure how the test case around "because of got one row" is >> relevant to the current changes. After we reach to some agreement >> on the above discussion, I think v4 is good for committer to review! >> >> >> Thank you!) I am ready to discuss it. > > > Actually I meant to discuss the "Unfortunately, I found a request..", looks > we have reached an agreement there:) > > Yes, we have) Hi Andy Fan, If the changes of Alena are ok, can you merge the changes and post an updated version so that CFBot can apply the patch and verify the changes. As currently CFBot is trying to apply only Alena's changes and failing with the following at [1]: === Applying patches on top of PostgreSQL commit ID fba2112b1569fd001a9e54dfdd73fd3cb8f16140 === === applying patch ./pull-up.diff patching file src/test/regress/expected/subselect.out Hunk #1 succeeded at 1926 with fuzz 2 (offset -102 lines). patching file src/test/regress/sql/subselect.sql Hunk #1 FAILED at 1000. 1 out of 1 hunk FAILED -- saving rejects to file src/test/regress/sql/subselect.sql.rej [1] - http://cfbot.cputube.org/patch_46_4268.log Regards, Vignesh ^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: A new strategy for pull-up correlated ANY_SUBLINK @ 2024-02-13 10:50 Alexander Korotkov <[email protected]> parent: vignesh C <[email protected]> 0 siblings, 1 reply; 8+ messages in thread From: Alexander Korotkov @ 2024-02-13 10:50 UTC (permalink / raw) To: vignesh C <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Andy Fan <[email protected]>; pgsql-hackers; Tom Lane <[email protected]>; Richard Guo <[email protected]>; Andrey Lepikhov <[email protected]> Hi! > If the changes of Alena are ok, can you merge the changes and post an > updated version so that CFBot can apply the patch and verify the > changes. As currently CFBot is trying to apply only Alena's changes > and failing with the following at [1]: I think this is a very nice and pretty simple optimization. I've merged the changes by Alena, and slightly revised the code changes in convert_ANY_sublink_to_join(). I'm going to push this if there are no objections. ------ Regards, Alexander Korotkov Attachments: [application/octet-stream] 0001-Pull-up-ANY-SUBLINK-with-the-necessary-lateral-su-v6.patch (16.4K, ../../CAPpHfduAWZKpfe0Th+AJ4pGkJpBuSAgY5X0Xc0-XmUYOSYPm-g@mail.gmail.com/2-0001-Pull-up-ANY-SUBLINK-with-the-necessary-lateral-su-v6.patch) download | inline diff: From fd8834f8e651c47fd4ee03b9fe84ec87fe33a53d Mon Sep 17 00:00:00 2001 From: Andy Fan <[email protected]> Date: Fri, 13 Oct 2023 14:39:34 +0800 Subject: [PATCH] Pull up ANY-SUBLINK with the necessary lateral support. For ANY-SUBLINK, we adopted a two-stage pull-up approach to handle different types of scenarios. In the first stage, the sublink is pulled up as a subquery. Because of this, when writing this code, we did not have the ability to perform lateral joins, and therefore, we were unable to pull up Var with varlevelsup=1. Now that we have the ability to use lateral joins, we can eliminate this limitation. Author: Andy Fan <[email protected]> Reviewed-by: Tom Lane <[email protected]> Reviewed-by: Richard Guo <[email protected]> Reviewed-by: Alena Rybakina <[email protected]> Reviewed-by: Andrey Lepikhov <[email protected]> --- .../postgres_fdw/expected/postgres_fdw.out | 6 +- contrib/postgres_fdw/sql/postgres_fdw.sql | 4 +- src/backend/optimizer/plan/subselect.c | 17 ++- src/test/regress/expected/join.out | 14 +- src/test/regress/expected/subselect.out | 126 ++++++++++++++++++ src/test/regress/sql/join.sql | 8 +- src/test/regress/sql/subselect.sql | 37 +++++ 7 files changed, 192 insertions(+), 20 deletions(-) diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index b5a38aeb214..c355e8f3f7d 100644 --- a/contrib/postgres_fdw/expected/postgres_fdw.out +++ b/contrib/postgres_fdw/expected/postgres_fdw.out @@ -11894,7 +11894,7 @@ CREATE FOREIGN TABLE foreign_tbl (b int) CREATE FOREIGN TABLE foreign_tbl2 () INHERITS (foreign_tbl) SERVER loopback OPTIONS (table_name 'base_tbl'); EXPLAIN (VERBOSE, COSTS OFF) -SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); +SELECT a FROM base_tbl WHERE (a, random() > 0) IN (SELECT a, random() > 0 FROM foreign_tbl); QUERY PLAN ----------------------------------------------------------------------------- Seq Scan on public.base_tbl @@ -11902,7 +11902,7 @@ SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); Filter: (SubPlan 1) SubPlan 1 -> Result - Output: base_tbl.a + Output: base_tbl.a, (random() > '0'::double precision) -> Append -> Async Foreign Scan on public.foreign_tbl foreign_tbl_1 Remote SQL: SELECT NULL FROM public.base_tbl @@ -11910,7 +11910,7 @@ SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); Remote SQL: SELECT NULL FROM public.base_tbl (11 rows) -SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); +SELECT a FROM base_tbl WHERE (a, random() > 0) IN (SELECT a, random() > 0 FROM foreign_tbl); a --- 1 diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql index f410c3db4e6..812e7646e16 100644 --- a/contrib/postgres_fdw/sql/postgres_fdw.sql +++ b/contrib/postgres_fdw/sql/postgres_fdw.sql @@ -3988,8 +3988,8 @@ CREATE FOREIGN TABLE foreign_tbl2 () INHERITS (foreign_tbl) SERVER loopback OPTIONS (table_name 'base_tbl'); EXPLAIN (VERBOSE, COSTS OFF) -SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); -SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl); +SELECT a FROM base_tbl WHERE (a, random() > 0) IN (SELECT a, random() > 0 FROM foreign_tbl); +SELECT a FROM base_tbl WHERE (a, random() > 0) IN (SELECT a, random() > 0 FROM foreign_tbl); -- Clean up DROP FOREIGN TABLE foreign_tbl CASCADE; diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index 3115d79ad98..47e14723d2b 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -1278,14 +1278,23 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, List *subquery_vars; Node *quals; ParseState *pstate; + Relids sub_ref_outer_relids; + bool use_lateral; Assert(sublink->subLinkType == ANY_SUBLINK); /* - * The sub-select must not refer to any Vars of the parent query. (Vars of - * higher levels should be okay, though.) + * If the sub-select refers to any Vars of the parent query, we so let's + * considering it as LATERAL. (Vars of higher levels don't matter here.) */ - if (contain_vars_of_level((Node *) subselect, 1)) + sub_ref_outer_relids = pull_varnos_of_level(NULL, (Node *) subselect, 1); + use_lateral = !bms_is_empty(sub_ref_outer_relids); + + /* + * Check that sub-select refers nothing outside of available_rels of the + * parent query. + */ + if (!bms_is_subset(sub_ref_outer_relids, available_rels)) return NULL; /* @@ -1323,7 +1332,7 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, nsitem = addRangeTableEntryForSubquery(pstate, subselect, makeAlias("ANY_subquery", NIL), - false, + use_lateral, false); rte = nsitem->p_rte; parse->rtable = lappend(parse->rtable, rte); diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 9c08d0134ca..0c2cba89213 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -5277,7 +5277,7 @@ reset enable_nestloop; explain (costs off) select a.unique1, b.unique2 from onek a left join onek b on a.unique1 = b.unique2 - where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1); + where (b.unique2, random() > 0) = any (select q1, random() > 0 from int8_tbl c where c.q1 < b.unique1); QUERY PLAN ---------------------------------------------------------- Hash Join @@ -5293,7 +5293,7 @@ select a.unique1, b.unique2 select a.unique1, b.unique2 from onek a left join onek b on a.unique1 = b.unique2 - where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1); + where (b.unique2, random() > 0) = any (select q1, random() > 0 from int8_tbl c where c.q1 < b.unique1); unique1 | unique2 ---------+--------- 123 | 123 @@ -8210,12 +8210,12 @@ select * from (values (0), (1)) v(id), lateral (select * from int8_tbl t1, lateral (select * from (select * from int8_tbl t2 - where q1 = any (select q2 from int8_tbl t3 + where (q1, random() > 0) = any (select q2, random() > 0 from int8_tbl t3 where q2 = (select greatest(t1.q1,t2.q2)) and (select v.id=0)) offset 0) ss2) ss where t1.q1 = ss.q2) ss0; - QUERY PLAN ----------------------------------------------------------------------- + QUERY PLAN +------------------------------------------------------------------------------- Nested Loop Output: "*VALUES*".column1, t1.q1, t1.q2, ss2.q1, ss2.q2 -> Seq Scan on public.int8_tbl t1 @@ -8232,7 +8232,7 @@ lateral (select * from int8_tbl t1, Filter: (SubPlan 3) SubPlan 3 -> Result - Output: t3.q2 + Output: t3.q2, (random() > '0'::double precision) One-Time Filter: $4 InitPlan 1 (returns $2) -> Result @@ -8249,7 +8249,7 @@ select * from (values (0), (1)) v(id), lateral (select * from int8_tbl t1, lateral (select * from (select * from int8_tbl t2 - where q1 = any (select q2 from int8_tbl t3 + where (q1, random() > 0) = any (select q2, random() > 0 from int8_tbl t3 where q2 = (select greatest(t1.q1,t2.q2)) and (select v.id=0)) offset 0) ss2) ss where t1.q1 = ss.q2) ss0; diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out index a3a4d03d104..e41b728df83 100644 --- a/src/test/regress/expected/subselect.out +++ b/src/test/regress/expected/subselect.out @@ -1926,3 +1926,129 @@ select * from x for update; Output: subselect_tbl.f1, subselect_tbl.f2, subselect_tbl.f3 (2 rows) +-- Pull-up the direct-correlated ANY_SUBLINK +explain (costs off) +select * from tenk1 A where hundred in (select hundred from tenk2 B where B.odd = A.odd); + QUERY PLAN +------------------------------------------------------------ + Hash Join + Hash Cond: ((a.odd = b.odd) AND (a.hundred = b.hundred)) + -> Seq Scan on tenk1 a + -> Hash + -> HashAggregate + Group Key: b.odd, b.hundred + -> Seq Scan on tenk2 b +(7 rows) + +explain (costs off) +select * from tenk1 A where exists +(select 1 from tenk2 B +where A.hundred in (select C.hundred FROM tenk2 C +WHERE c.odd = b.odd)); + QUERY PLAN +--------------------------------- + Nested Loop Semi Join + Join Filter: (SubPlan 1) + -> Seq Scan on tenk1 a + -> Materialize + -> Seq Scan on tenk2 b + SubPlan 1 + -> Seq Scan on tenk2 c + Filter: (odd = b.odd) +(8 rows) + +-- we should only try to pull up the sublink into RHS of a left join +-- but a.hundred is not avaiable. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +--------------------------------- + Nested Loop Left Join + Join Filter: (SubPlan 1) + -> Seq Scan on tenk1 a + -> Materialize + -> Seq Scan on tenk2 b + SubPlan 1 + -> Seq Scan on tenk2 c + Filter: (odd = b.odd) +(8 rows) + +-- we should only try to pull up the sublink into RHS of a left join +-- but a.odd is not avaiable for this. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = a.odd); + QUERY PLAN +--------------------------------- + Nested Loop Left Join + Join Filter: (SubPlan 1) + -> Seq Scan on tenk1 a + -> Materialize + -> Seq Scan on tenk2 b + SubPlan 1 + -> Seq Scan on tenk2 c + Filter: (odd = a.odd) +(8 rows) + +-- should be able to pull up since all the references is available +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +------------------------------------------------------------------------ + Nested Loop Left Join + -> Seq Scan on tenk1 a + -> Materialize + -> Hash Join + Hash Cond: ((b.odd = c.odd) AND (b.hundred = c.hundred)) + -> Seq Scan on tenk2 b + -> Hash + -> HashAggregate + Group Key: c.odd, c.hundred + -> Seq Scan on tenk2 c +(10 rows) + +-- we can pull up the sublink into the inner JoinExpr. +explain (costs off) +SELECT * FROM tenk1 A INNER JOIN tenk2 B +ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +------------------------------------------------- + Hash Join + Hash Cond: (c.odd = b.odd) + -> Hash Join + Hash Cond: (a.hundred = c.hundred) + -> Seq Scan on tenk1 a + -> Hash + -> HashAggregate + Group Key: c.odd, c.hundred + -> Seq Scan on tenk2 c + -> Hash + -> Seq Scan on tenk2 b +(11 rows) + +-- we can pull up the aggregate sublink into RHS of a left join. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); + QUERY PLAN +--------------------------------------------------------------------------------------- + Nested Loop Left Join + -> Seq Scan on tenk1 a + -> Materialize + -> Nested Loop + -> Seq Scan on tenk2 b + -> Memoize + Cache Key: b.hundred, b.odd + Cache Mode: binary + -> Subquery Scan on "ANY_subquery" + Filter: (b.hundred = "ANY_subquery".min) + -> Result + InitPlan 1 (returns $1) + -> Limit + -> Index Scan using tenk2_hundred on tenk2 c + Index Cond: (hundred IS NOT NULL) + Filter: (odd = b.odd) +(16 rows) + diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql index e1db2025db6..257f727a2be 100644 --- a/src/test/regress/sql/join.sql +++ b/src/test/regress/sql/join.sql @@ -1864,11 +1864,11 @@ reset enable_nestloop; explain (costs off) select a.unique1, b.unique2 from onek a left join onek b on a.unique1 = b.unique2 - where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1); + where (b.unique2, random() > 0) = any (select q1, random() > 0 from int8_tbl c where c.q1 < b.unique1); select a.unique1, b.unique2 from onek a left join onek b on a.unique1 = b.unique2 - where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1); + where (b.unique2, random() > 0) = any (select q1, random() > 0 from int8_tbl c where c.q1 < b.unique1); -- -- test full-join strength reduction @@ -3038,7 +3038,7 @@ select * from (values (0), (1)) v(id), lateral (select * from int8_tbl t1, lateral (select * from (select * from int8_tbl t2 - where q1 = any (select q2 from int8_tbl t3 + where (q1, random() > 0) = any (select q2, random() > 0 from int8_tbl t3 where q2 = (select greatest(t1.q1,t2.q2)) and (select v.id=0)) offset 0) ss2) ss where t1.q1 = ss.q2) ss0; @@ -3047,7 +3047,7 @@ select * from (values (0), (1)) v(id), lateral (select * from int8_tbl t1, lateral (select * from (select * from int8_tbl t2 - where q1 = any (select q2 from int8_tbl t3 + where (q1, random() > 0) = any (select q2, random() > 0 from int8_tbl t3 where q2 = (select greatest(t1.q1,t2.q2)) and (select v.id=0)) offset 0) ss2) ss where t1.q1 = ss.q2) ss0; diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql index bd2e39efd48..2f3601a0582 100644 --- a/src/test/regress/sql/subselect.sql +++ b/src/test/regress/sql/subselect.sql @@ -968,3 +968,40 @@ select * from (with x as (select 2 as y) select * from x) ss; explain (verbose, costs off) with x as (select * from subselect_tbl) select * from x for update; + +-- Pull-up the direct-correlated ANY_SUBLINK +explain (costs off) +select * from tenk1 A where hundred in (select hundred from tenk2 B where B.odd = A.odd); + +explain (costs off) +select * from tenk1 A where exists +(select 1 from tenk2 B +where A.hundred in (select C.hundred FROM tenk2 C +WHERE c.odd = b.odd)); + +-- we should only try to pull up the sublink into RHS of a left join +-- but a.hundred is not avaiable. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + +-- we should only try to pull up the sublink into RHS of a left join +-- but a.odd is not avaiable for this. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = a.odd); + +-- should be able to pull up since all the references is available +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + +-- we can pull up the sublink into the inner JoinExpr. +explain (costs off) +SELECT * FROM tenk1 A INNER JOIN tenk2 B +ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd); + +-- we can pull up the aggregate sublink into RHS of a left join. +explain (costs off) +SELECT * FROM tenk1 A LEFT JOIN tenk2 B +ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd); \ No newline at end of file -- 2.39.3 (Apple Git-145) ^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: A new strategy for pull-up correlated ANY_SUBLINK @ 2024-02-15 09:51 Andy Fan <[email protected]> parent: Alexander Korotkov <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Andy Fan @ 2024-02-15 09:51 UTC (permalink / raw) To: Alexander Korotkov <[email protected]>; +Cc: vignesh C <[email protected]>; Alena Rybakina <[email protected]>; Andy Fan <[email protected]>; pgsql-hackers; Tom Lane <[email protected]>; Richard Guo <[email protected]>; Andrey Lepikhov <[email protected]>; [email protected] Hi Alexander, > Hi! > >> If the changes of Alena are ok, can you merge the changes and post an >> updated version so that CFBot can apply the patch and verify the >> changes. As currently CFBot is trying to apply only Alena's changes >> and failing with the following at [1]: > > I think this is a very nice and pretty simple optimization. I've > merged the changes by Alena, and slightly revised the code changes in > convert_ANY_sublink_to_join(). I'm going to push this if there are no > objections. Thanks for picking up this! I double checked the patch, it looks good to me. -- Best Regards Andy Fan ^ permalink raw reply [nested|flat] 8+ messages in thread
* [PATCH v20 6/8] Row pattern recognition patch (docs). @ 2024-05-24 02:26 Tatsuo Ishii <[email protected]> 0 siblings, 0 replies; 8+ messages in thread From: Tatsuo Ishii @ 2024-05-24 02:26 UTC (permalink / raw) --- doc/src/sgml/advanced.sgml | 82 ++++++++++++++++++++++++++++++++++++ doc/src/sgml/func.sgml | 54 ++++++++++++++++++++++++ doc/src/sgml/ref/select.sgml | 38 ++++++++++++++++- 3 files changed, 172 insertions(+), 2 deletions(-) diff --git a/doc/src/sgml/advanced.sgml b/doc/src/sgml/advanced.sgml index 755c9f1485..b0b1d1c51e 100644 --- a/doc/src/sgml/advanced.sgml +++ b/doc/src/sgml/advanced.sgml @@ -537,6 +537,88 @@ WHERE pos < 3; <literal>rank</literal> less than 3. </para> + <para> + Row pattern common syntax can be used to perform row pattern recognition + in a query. The row pattern common syntax includes two sub + clauses: <literal>DEFINE</literal> + and <literal>PATTERN</literal>. <literal>DEFINE</literal> defines + definition variables along with an expression. The expression must be a + logical expression, which means it must + return <literal>TRUE</literal>, <literal>FALSE</literal> + or <literal>NULL</literal>. The expression may comprise column references + and functions. Window functions, aggregate functions and subqueries are + not allowed. An example of <literal>DEFINE</literal> is as follows. + +<programlisting> +DEFINE + LOWPRICE AS price <= 100, + UP AS price > PREV(price), + DOWN AS price < PREV(price) +</programlisting> + + Note that <function>PREV</function> returns the price column in the + previous row if it's called in a context of row pattern recognition. Thus in + the second line the definition variable "UP" is <literal>TRUE</literal> + when the price column in the current row is greater than the price column + in the previous row. Likewise, "DOWN" is <literal>TRUE</literal> when when + the price column in the current row is lower than the price column in the + previous row. + </para> + <para> + Once <literal>DEFINE</literal> exists, <literal>PATTERN</literal> can be + used. <literal>PATTERN</literal> defines a sequence of rows that satisfies + certain conditions. For example following <literal>PATTERN</literal> + defines that a row starts with the condition "LOWPRICE", then one or more + rows satisfy "UP" and finally one or more rows satisfy "DOWN". Note that + "+" means one or more matches. Also you can use "*", which means zero or + more matches. If a sequence of rows which satisfies the PATTERN is found, + in the starting row of the sequence of rows all window functions and + aggregates are shown in the target list. Note that aggregations only look + into the matched rows, rather than whole frame. On the second or + subsequent rows all window functions are NULL. Aggregates are NULL or 0 + (count case) depending on its aggregation definition. For rows that do not + match on the PATTERN, all window functions and aggregates are shown AS + NULL too, except count showing 0. This is because the rows do not match, + thus they are in an empty frame. Example of a <literal>SELECT</literal> + using the <literal>DEFINE</literal> and <literal>PATTERN</literal> clause + is as follows. + +<programlisting> +SELECT company, tdate, price, + first_value(price) OVER w, + max(price) OVER w, + count(price) OVER w +FROM stock + WINDOW w AS ( + PARTITION BY company + ORDER BY tdate + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN (LOWPRICE UP+ DOWN+) + DEFINE + LOWPRICE AS price <= 100, + UP AS price > PREV(price), + DOWN AS price < PREV(price) +); +</programlisting> +<screen> + company | tdate | price | first_value | max | count +----------+------------+-------+-------------+-----+------- + company1 | 2023-07-01 | 100 | 100 | 200 | 4 + company1 | 2023-07-02 | 200 | | | 0 + company1 | 2023-07-03 | 150 | | | 0 + company1 | 2023-07-04 | 140 | | | 0 + company1 | 2023-07-05 | 150 | | | 0 + company1 | 2023-07-06 | 90 | 90 | 130 | 4 + company1 | 2023-07-07 | 110 | | | 0 + company1 | 2023-07-08 | 130 | | | 0 + company1 | 2023-07-09 | 120 | | | 0 + company1 | 2023-07-10 | 130 | | | 0 +(10 rows) +</screen> + </para> + <para> When a query involves multiple window functions, it is possible to write out each one with a separate <literal>OVER</literal> clause, but this is diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml index 17c44bc338..8dbab31300 100644 --- a/doc/src/sgml/func.sgml +++ b/doc/src/sgml/func.sgml @@ -23124,6 +23124,7 @@ SELECT count(*) FROM sometable; returns <literal>NULL</literal> if there is no such row. </para></entry> </row> + </tbody> </tgroup> </table> @@ -23163,6 +23164,59 @@ SELECT count(*) FROM sometable; Other frame specifications can be used to obtain other effects. </para> + <para> + Row pattern recognition navigation functions are listed in + <xref linkend="functions-rpr-navigation-table"/>. These functions + can be used to describe DEFINE clause of Row pattern recognition. + </para> + + <table id="functions-rpr-navigation-table"> + <title>Row Pattern Navigation Functions</title> + <tgroup cols="1"> + <thead> + <row> + <entry role="func_table_entry"><para role="func_signature"> + Function + </para> + <para> + Description + </para></entry> + </row> + </thead> + + <tbody> + <row> + <entry role="func_table_entry"><para role="func_signature"> + <indexterm> + <primary>prev</primary> + </indexterm> + <function>prev</function> ( <parameter>value</parameter> <type>anyelement</type> ) + <returnvalue>anyelement</returnvalue> + </para> + <para> + Returns the column value at the previous row; + returns NULL if there is no previous row in the window frame. + </para></entry> + </row> + + <row> + <entry role="func_table_entry"><para role="func_signature"> + <indexterm> + <primary>next</primary> + </indexterm> + <function>next</function> ( <parameter>value</parameter> <type>anyelement</type> ) + <returnvalue>anyelement</returnvalue> + </para> + <para> + Returns the column value at the next row; + returns NULL if there is no next row in the window frame. + </para></entry> + </row> + + </tbody> + </tgroup> + </table> + <note> <para> The SQL standard defines a <literal>RESPECT NULLS</literal> or diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml index 066aed44e6..8f18718d58 100644 --- a/doc/src/sgml/ref/select.sgml +++ b/doc/src/sgml/ref/select.sgml @@ -969,8 +969,8 @@ WINDOW <replaceable class="parameter">window_name</replaceable> AS ( <replaceabl The <replaceable class="parameter">frame_clause</replaceable> can be one of <synopsis> -{ RANGE | ROWS | GROUPS } <replaceable>frame_start</replaceable> [ <replaceable>frame_exclusion</replaceable> ] -{ RANGE | ROWS | GROUPS } BETWEEN <replaceable>frame_start</replaceable> AND <replaceable>frame_end</replaceable> [ <replaceable>frame_exclusion</replaceable> ] +{ RANGE | ROWS | GROUPS } <replaceable>frame_start</replaceable> [ <replaceable>frame_exclusion</replaceable> ] [row_pattern_common_syntax] +{ RANGE | ROWS | GROUPS } BETWEEN <replaceable>frame_start</replaceable> AND <replaceable>frame_end</replaceable> [ <replaceable>frame_exclusion</replaceable> ] [row_pattern_common_syntax] </synopsis> where <replaceable>frame_start</replaceable> @@ -1077,6 +1077,40 @@ EXCLUDE NO OTHERS a given peer group will be in the frame or excluded from it. </para> + <para> + The + optional <replaceable class="parameter">row_pattern_common_syntax</replaceable> + defines the <firstterm>row pattern recognition condition</firstterm> for + this + window. <replaceable class="parameter">row_pattern_common_syntax</replaceable> + includes following subclauses. <literal>AFTER MATCH SKIP PAST LAST + ROW</literal> or <literal>AFTER MATCH SKIP TO NEXT ROW</literal> controls + how to proceed to next row position after a match + found. With <literal>AFTER MATCH SKIP PAST LAST ROW</literal> (the + default) next row position is next to the last row of previous match. On + the other hand, with <literal>AFTER MATCH SKIP TO NEXT ROW</literal> next + row position is always next to the last row of previous + match. <literal>DEFINE</literal> defines definition variables along with a + boolean expression. <literal>PATTERN</literal> defines a sequence of rows + that satisfies certain conditions using variables defined + in <literal>DEFINE</literal> clause. If the variable is not defined in + the <literal>DEFINE</literal> clause, it is implicitly assumed + following is defined in the <literal>DEFINE</literal> clause. + +<synopsis> +<literal>variable_name</literal> AS TRUE +</synopsis> + + Note that the maximu number of variables defined + in <literal>DEFINE</literal> clause is 26. + +<synopsis> +[ AFTER MATCH SKIP PAST LAST ROW | AFTER MATCH SKIP TO NEXT ROW ] +PATTERN <replaceable class="parameter">pattern_variable_name</replaceable>[+] [, ...] +DEFINE <replaceable class="parameter">definition_varible_name</replaceable> AS <replaceable class="parameter">expression</replaceable> [, ...] +</synopsis> + </para> + <para> The purpose of a <literal>WINDOW</literal> clause is to specify the behavior of <firstterm>window functions</firstterm> appearing in the query's -- 2.25.1 ----Next_Part(Fri_May_24_11_39_19_2024_763)-- Content-Type: Text/X-Patch; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="v20-0007-Row-pattern-recognition-patch-tests.patch" ^ permalink raw reply [nested|flat] 8+ messages in thread
end of thread, other threads:[~2024-05-24 02:26 UTC | newest] Thread overview: 8+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2023-10-12 23:14 Re: A new strategy for pull-up correlated ANY_SUBLINK Alena Rybakina <[email protected]> 2023-10-13 07:04 ` Andy Fan <[email protected]> 2023-10-13 07:29 ` Andy Fan <[email protected]> 2023-10-13 08:39 ` Alena Rybakina <[email protected]> 2024-01-26 12:46 ` vignesh C <[email protected]> 2024-02-13 10:50 ` Alexander Korotkov <[email protected]> 2024-02-15 09:51 ` Andy Fan <[email protected]> 2024-05-24 02:26 [PATCH v20 6/8] Row pattern recognition patch (docs). Tatsuo Ishii <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox