Add semi-join pushdown to postgres_fdw

Hi Alexander,
Thanks for working on this. It's great to see FDW join pushdown scope
being expanded to more complex cases.

I am still figuring out the implementation. It's been a while I have
looked at join push down code.

But following change strikes me odd
 -- subquery using immutable function (can be sent to remote)
 PREPARE st3(int) AS SELECT * FROM ft1 t1 WHERE t1.c1 < $2 AND t1.c3
IN (SELECT c3 FROM ft2 t2 WHERE c1 > $1 AND date(c5) =
'1970-01-17'::date) ORDER BY c1;
 EXPLAIN (VERBOSE, COSTS OFF) EXECUTE st3(10, 20);
-                                                      QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
- Sort
+

QUERY PLAN
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Foreign Scan
    Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
-   Sort Key: t1.c1
-   ->  Nested Loop Semi Join
-         Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
-         Join Filter: (t1.c3 = t2.c3)
-         ->  Foreign Scan on public.ft1 t1
-               Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
-               Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8
FROM "S 1"."T 1" WHERE (("C 1" < 20))
-         ->  Materialize
-               Output: t2.c3
-               ->  Foreign Scan on public.ft2 t2
-                     Output: t2.c3
-                     Remote SQL: SELECT c3 FROM "S 1"."T 1" WHERE
(("C 1" > 10)) AND ((date(c5) = '1970-01-17'::date))
-(14 rows)
+   Relations: (public.ft1 t1) SEMI JOIN (public.ft2 t2)
+   Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6,
r1.c7, r1.c8 FROM "S 1"."T 1" r1 WHERE ((r1."C 1" < 20)) AND (EXISTS
(SELECT NULL FROM "S 1"."T 1" r3 WHERE ((r3."C 1" > 10)) AND
((date(r3.c5) = '1970-01-17'::date)) AND ((r1.c3 = r3.c3)))) ORDER BY
r1."C 1" ASC NULLS LAST
+(4 rows)

date_in | s | 1 | [0:0]={cstring}
date_in which will be used to cast a test to date is not immutable. So
the query should't be pushed down. May not be a problem with your
patch. Can you please check?

On Wed, Aug 24, 2022 at 12:55 PM Alexander Pyhalov
<a.pyhalov@postgrespro.ru> wrote:

Hi.

It's possible to extend deparsing in postgres_fdw, so that we can push
down semi-joins, which doesn't refer to inner reltarget. This allows
us to push down joins in queries like

SELECT * FROM ft1 t1 WHERE t1.c1 < 10 AND t1.c3 IN (SELECT c3 FROM ft2
t2 WHERE date(c5) = '1970-01-17'::date);

EXPLAIN (VERBOSE, COSTS OFF) SELECT * FROM ft1 t1 WHERE t1.c1 < 10 AND
t1.c3 IN (SELECT c3 FROM ft2 t2 WHERE date(c5) = '1970-01-17'::date);

QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Foreign Scan
Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
Relations: (public.ft1 t1) SEMI JOIN (public.ft2 t2)
Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6,
r1.c7, r1.c8 FROM "S 1"."T 1" r1 WHERE ((r1."C 1" < 10)) AND (EXISTS
(SELECT NULL FROM "S 1"."T 1" r3 WHERE ((date(r3.c5) =
'1970-01-17'::date)) AND ((r1.c3 = r3.c3))))

Thanks for working on this. It's great to see FDW join pushdown scope
being expanded to more complex cases.

I am still figuring out the implementation. It's been a while I have
looked at join push down code.

But following change strikes me odd
 -- subquery using immutable function (can be sent to remote)
 PREPARE st3(int) AS SELECT * FROM ft1 t1 WHERE t1.c1 < $2 AND t1.c3
IN (SELECT c3 FROM ft2 t2 WHERE c1 > $1 AND date(c5) =
'1970-01-17'::date) ORDER BY c1;
 EXPLAIN (VERBOSE, COSTS OFF) EXECUTE st3(10, 20);
-                                                      QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
- Sort
+

QUERY PLAN
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Foreign Scan
    Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
-   Sort Key: t1.c1
-   ->  Nested Loop Semi Join
-         Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
-         Join Filter: (t1.c3 = t2.c3)
-         ->  Foreign Scan on public.ft1 t1
-               Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
-               Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8
FROM "S 1"."T 1" WHERE (("C 1" < 20))
-         ->  Materialize
-               Output: t2.c3
-               ->  Foreign Scan on public.ft2 t2
-                     Output: t2.c3
-                     Remote SQL: SELECT c3 FROM "S 1"."T 1" WHERE
(("C 1" > 10)) AND ((date(c5) = '1970-01-17'::date))
-(14 rows)
+   Relations: (public.ft1 t1) SEMI JOIN (public.ft2 t2)
+   Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6,
r1.c7, r1.c8 FROM "S 1"."T 1" r1 WHERE ((r1."C 1" < 20)) AND (EXISTS
(SELECT NULL FROM "S 1"."T 1" r3 WHERE ((r3."C 1" > 10)) AND
((date(r3.c5) = '1970-01-17'::date)) AND ((r1.c3 = r3.c3)))) ORDER BY
r1."C 1" ASC NULLS LAST
+(4 rows)

date_in | s | 1 | [0:0]={cstring}
date_in which will be used to cast a test to date is not immutable. So
the query should't be pushed down. May not be a problem with your
patch. Can you please check?

--
Best Wishes,
Ashutosh Bapat

Ashutosh Bapat писал 2022-08-29 17:12:

Hi Alexander,
Thanks for working on this. It's great to see FDW join pushdown scope
being expanded to more complex cases.

I am still figuring out the implementation. It's been a while I have
looked at join push down code.

But following change strikes me odd
-- subquery using immutable function (can be sent to remote)
PREPARE st3(int) AS SELECT * FROM ft1 t1 WHERE t1.c1 < $2 AND t1.c3
IN (SELECT c3 FROM ft2 t2 WHERE c1 > $1 AND date(c5) =
'1970-01-17'::date) ORDER BY c1;
EXPLAIN (VERBOSE, COSTS OFF) EXECUTE st3(10, 20);
-                                                      QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
- Sort
+

QUERY PLAN
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Foreign Scan
Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
-   Sort Key: t1.c1
-   ->  Nested Loop Semi Join
-         Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, 
t1.c8
-         Join Filter: (t1.c3 = t2.c3)
-         ->  Foreign Scan on public.ft1 t1
-               Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, 
t1.c7, t1.c8
-               Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8
FROM "S 1"."T 1" WHERE (("C 1" < 20))
-         ->  Materialize
-               Output: t2.c3
-               ->  Foreign Scan on public.ft2 t2
-                     Output: t2.c3
-                     Remote SQL: SELECT c3 FROM "S 1"."T 1" WHERE
(("C 1" > 10)) AND ((date(c5) = '1970-01-17'::date))
-(14 rows)
+   Relations: (public.ft1 t1) SEMI JOIN (public.ft2 t2)
+   Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6,
r1.c7, r1.c8 FROM "S 1"."T 1" r1 WHERE ((r1."C 1" < 20)) AND (EXISTS
(SELECT NULL FROM "S 1"."T 1" r3 WHERE ((r3."C 1" > 10)) AND
((date(r3.c5) = '1970-01-17'::date)) AND ((r1.c3 = r3.c3)))) ORDER BY
r1."C 1" ASC NULLS LAST
+(4 rows)

date_in | s | 1 | [0:0]={cstring}
date_in which will be used to cast a test to date is not immutable. So
the query should't be pushed down. May not be a problem with your
patch. Can you please check?

Hi.

It is not related to my change and works as expected. As I see, we have
expression FuncExprdate(oid = 2029, args=Var ) = Const(type date)
(date(r3.c5) = '1970-01-17'::date).
Function is

# select proname, provolatile from pg_proc where oid=2029;
proname | provolatile
---------+-------------
date | i

So it's shippable.
--
Best regards,
Alexander Pyhalov,
Postgres Professional

2022年8月30日(火) 15:58 Alexander Pyhalov <a.pyhalov@postgrespro.ru>:

Ashutosh Bapat писал 2022-08-29 17:12:

Hi Alexander,
Thanks for working on this. It's great to see FDW join pushdown scope
being expanded to more complex cases.

I am still figuring out the implementation. It's been a while I have
looked at join push down code.

But following change strikes me odd
-- subquery using immutable function (can be sent to remote)
PREPARE st3(int) AS SELECT * FROM ft1 t1 WHERE t1.c1 < $2 AND t1.c3
IN (SELECT c3 FROM ft2 t2 WHERE c1 > $1 AND date(c5) =
'1970-01-17'::date) ORDER BY c1;
EXPLAIN (VERBOSE, COSTS OFF) EXECUTE st3(10, 20);
-                                                      QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
- Sort
+

QUERY PLAN
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Foreign Scan
Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7, t1.c8
-   Sort Key: t1.c1
-   ->  Nested Loop Semi Join
-         Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6, t1.c7,
t1.c8
-         Join Filter: (t1.c3 = t2.c3)
-         ->  Foreign Scan on public.ft1 t1
-               Output: t1.c1, t1.c2, t1.c3, t1.c4, t1.c5, t1.c6,
t1.c7, t1.c8
-               Remote SQL: SELECT "C 1", c2, c3, c4, c5, c6, c7, c8
FROM "S 1"."T 1" WHERE (("C 1" < 20))
-         ->  Materialize
-               Output: t2.c3
-               ->  Foreign Scan on public.ft2 t2
-                     Output: t2.c3
-                     Remote SQL: SELECT c3 FROM "S 1"."T 1" WHERE
(("C 1" > 10)) AND ((date(c5) = '1970-01-17'::date))
-(14 rows)
+   Relations: (public.ft1 t1) SEMI JOIN (public.ft2 t2)
+   Remote SQL: SELECT r1."C 1", r1.c2, r1.c3, r1.c4, r1.c5, r1.c6,
r1.c7, r1.c8 FROM "S 1"."T 1" r1 WHERE ((r1."C 1" < 20)) AND (EXISTS
(SELECT NULL FROM "S 1"."T 1" r3 WHERE ((r3."C 1" > 10)) AND
((date(r3.c5) = '1970-01-17'::date)) AND ((r1.c3 = r3.c3)))) ORDER BY
r1."C 1" ASC NULLS LAST
+(4 rows)

date_in | s | 1 | [0:0]={cstring}
date_in which will be used to cast a test to date is not immutable. So
the query should't be pushed down. May not be a problem with your
patch. Can you please check?

Hi.

It is not related to my change and works as expected. As I see, we have
expression FuncExprdate(oid = 2029, args=Var ) = Const(type date)
(date(r3.c5) = '1970-01-17'::date).
Function is

# select proname, provolatile from pg_proc where oid=2029;
proname | provolatile
---------+-------------
date | i

So it's shippable.

This entry was marked as "Needs review" in the CommitFest app but cfbot
reports the patch no longer applies.

We've marked it as "Waiting on Author". As CommitFest 2022-11 is
currently underway, this would be an excellent time update the patch.

Once you think the patchset is ready for review again, you (or any
interested party) can move the patch entry forward by visiting

https://commitfest.postgresql.org/40/3838/

and changing the status to "Needs review".

Thanks

Ian Barwick

Ian Lawrence Barwick писал 2022-11-04 02:21:

This entry was marked as "Needs review" in the CommitFest app but cfbot
reports the patch no longer applies.

We've marked it as "Waiting on Author". As CommitFest 2022-11 is
currently underway, this would be an excellent time update the patch.

Once you think the patchset is ready for review again, you (or any
interested party) can move the patch entry forward by visiting

https://commitfest.postgresql.org/40/3838/

and changing the status to "Needs review".

Hi. I've rebased the patch.
--
Best regards,
Alexander Pyhalov,
Postgres Professional

Hi Mr.Pyhalov.

Thank you for work on this useful patch.
I'm starting to review v2 patch.
I have cheked we can apply v2 patch to commit ec386948948c1708c0c28c48ef08b9c4dd9d47cc
(Date:Thu Dec 1 12:56:21 2022 +0100).
I briefly looked at this whole thing and did step execute this
by running simple queries such as the followings.

query1) select * from f_t1 a1 where a1.c1 in (select c1 from f_t2);
query2) select * from f_t1 a1 join f_t3 a2 on a1.c1 = a2.c1 where a1.c1 in (select c1 from f_t3) ;
query3) update f_t2 set c1 = 1 from f_t1 a1 where a1.c2 = f_t2.c2 and exists (select null from f_t2 where c1 = a1.c1);

Although I haven't seen all of v2 patch, for now I have the following questions.

question1)

+ if (jointype == JOIN_SEMI && bms_is_member(var->varno, innerrel->relids) && !bms_is_member(var->varno, outerrel->relids))

It takes time for me to find in what case this condition is true.
There is cases in which this condition is true for semi-join of two baserels
when running query which joins more than two relations such as query2 and query3.
Running queries such as query2, you maybe want to pushdown of only semi-join path of
joinrel(outerrel) defined by (f_t1 a1 join f_t3 a2 on a1.c1 = a2.c1) and baserel(innerrel) f_t3
because of safety deparse. So you add this condition.
Becouase of this limitation, your patch can't push down subquery expression
"exists (select null from f_t2 where c1 = a1.c1)" in query3.
I think, it is one of difficulty points for semi-join pushdown.
This is my understanding of the intent of this condition and the restrictions imposed by this condition.
Is my understanding right?
I think if there are comments for the intent of this condition and the restrictions imposed by this condition
then they help PostgreSQL developper. What do you think?

question2) In foreign_join_ok

* Constructing queries representing ANTI joins is hard, hence

Is this true? Is it hard to expand your approach to ANTI join pushdown?

question3) You use variables whose name is "addl_condXXX" in the following code.

appendStringInfo(addl_conds, "EXISTS (SELECT NULL FROM %s", join_sql_i.data);

Does this naming mean additional literal?
Is there more complehensive naming, such as "subquery_exprXXX"?

question4) Although really detail, there is expression making space such as
"ft4.c2 = ft2.c2" and one making no space such as "c1=ftupper.c1".
Is there reason for this difference? If not, need we use same policy for making space?

Later, I'm going to look at part of your patch which is used when running more complex query.

Sincerely yours,
Yuuki Fujii

--
Yuuki Fujii
Information Technology R&D Center Mitsubishi Electric Corporation

Hi, Yuki.

Thanks for looking at this patch.

Fujii.Yuki@df.MitsubishiElectric.co.jp писал 2022-12-03 06:02:

question1)

+ if (jointype == JOIN_SEMI && bms_is_member(var->varno,

innerrel->relids) && !bms_is_member(var->varno, outerrel->relids))
It takes time for me to find in what case this condition is true.
There is cases in which this condition is true for semi-join of two
baserels
when running query which joins more than two relations such as
query2 and query3.
Running queries such as query2, you maybe want to pushdown of only
semi-join path of
joinrel(outerrel) defined by (f_t1 a1 join f_t3 a2 on a1.c1 = a2.c1)
and baserel(innerrel) f_t3
because of safety deparse. So you add this condition.
Becouase of this limitation, your patch can't push down subquery
expression
"exists (select null from f_t2 where c1 = a1.c1)" in query3.
I think, it is one of difficulty points for semi-join pushdown.
This is my understanding of the intent of this condition and the
restrictions imposed by this condition.
Is my understanding right?

IIRC, planner can create semi-join, which targetlist references Vars
from inner join relation. However, it's deparsed as exists and so we
can't reference it from SQL. So, there's this check - if Var is
referenced in semi-join target list, it can't be pushed down.
You can see this if comment out this check.

EXPLAIN (verbose, costs off)
SELECT ft2.*, ft4.* FROM ft2 INNER JOIN
(SELECT * FROM ft4 WHERE EXISTS (
SELECT 1 FROM ft2 WHERE ft2.c2=ft4.c2)) ft4
ON ft2.c2 = ft4.c1
INNER JOIN
(SELECT * FROM ft2 WHERE EXISTS (
SELECT 1 FROM ft4 WHERE ft2.c2=ft4.c2)) ft21
ON ft2.c2 = ft21.c2
WHERE ft2.c1 > 900
ORDER BY ft2.c1 LIMIT 10;

will fail with
EXPLAIN SELECT r8.c2, r9.c2 FROM "S 1"."T 1" r8 WHERE (EXISTS (SELECT
NULL FROM "S 1"."T 3" r9 WHERE ((r8.c2 = r9.c2))))

Here you can see that
SELECT * FROM ft2 WHERE EXISTS (
SELECT 1 FROM ft4 WHERE ft2.c2=ft4.c2)

was transformed to
SELECT r8.c2, r9.c2 FROM "S 1"."T 1" r8 WHERE (EXISTS (SELECT NULL FROM
"S 1"."T 3" r9 WHERE ((r8.c2 = r9.c2))))

where our exists subquery is referenced from tlist. It's fine for plan
(relations, participating in semi-join, can be referenced in tlist),
but is not going to work with EXISTS subquery.
BTW, there's a comment in joinrel_target_ok(). It tells exactly that -

5535 if (jointype == JOIN_SEMI && bms_is_member(var->varno,
innerrel->relids) && !bms_is_member(var->varno, outerrel->relids))
5536 {
5537 /* We deparse semi-join as exists() subquery, and
so can't deparse references to inner rel in join target list. */
5538 ok = false;
5539 break;
5540 }

Expanded comment.

question2) In foreign_join_ok

* Constructing queries representing ANTI joins is hard, hence

Is this true? Is it hard to expand your approach to ANTI join
pushdown?

I haven't tried, so don't know.

question3) You use variables whose name is "addl_condXXX" in the
following code.

appendStringInfo(addl_conds, "EXISTS (SELECT NULL FROM %s",

join_sql_i.data);
Does this naming mean additional literal?
Is there more complehensive naming, such as "subquery_exprXXX"?

The naming means additional conditions (for WHERE clause, by analogy
with ignore_conds and remote_conds). Not sure if subquery_expr sounds
better, but if you come with better idea, I'm fine with renaming them.

question4) Although really detail, there is expression making space
such as
"ft4.c2 = ft2.c2" and one making no space such as "c1=ftupper.c1".
Is there reason for this difference? If not, need we use same policy
for making space?

Fixed.

--
Best regards,
Alexander Pyhalov,
Postgres Professional

Hi Mr.Pyhalov.

Thank you for fixing it and giving more explanation.

IIRC, planner can create semi-join, which targetlist references Vars
from inner join relation. However, it's deparsed as exists and so we
can't reference it from SQL. So, there's this check - if Var is
referenced in semi-join target list, it can't be pushed down.
You can see this if comment out this check.

EXPLAIN (verbose, costs off)
SELECT ft2.*, ft4.* FROM ft2 INNER JOIN
(SELECT * FROM ft4 WHERE EXISTS (
SELECT 1 FROM ft2 WHERE ft2.c2=ft4.c2)) ft4
ON ft2.c2 = ft4.c1
INNER JOIN
(SELECT * FROM ft2 WHERE EXISTS (
SELECT 1 FROM ft4 WHERE ft2.c2=ft4.c2)) ft21
ON ft2.c2 = ft21.c2
WHERE ft2.c1 > 900
ORDER BY ft2.c1 LIMIT 10;

will fail with
EXPLAIN SELECT r8.c2, r9.c2 FROM "S 1"."T 1" r8 WHERE (EXISTS (SELECT
NULL FROM "S 1"."T 3" r9 WHERE ((r8.c2 = r9.c2))))

Here you can see that
SELECT * FROM ft2 WHERE EXISTS (
SELECT 1 FROM ft4 WHERE ft2.c2=ft4.c2)

was transformed to
SELECT r8.c2, r9.c2 FROM "S 1"."T 1" r8 WHERE (EXISTS (SELECT NULL
FROM "S 1"."T 3" r9 WHERE ((r8.c2 = r9.c2))))

where our exists subquery is referenced from tlist. It's fine for plan
(relations, participating in semi-join, can be referenced in tlist),
but is not going to work with EXISTS subquery.
BTW, there's a comment in joinrel_target_ok(). It tells exactly that -

5535 if (jointype == JOIN_SEMI &&
bms_is_member(var->varno,
innerrel->relids) && !bms_is_member(var->varno, outerrel->relids))
5536 {
5537 /* We deparse semi-join as exists() subquery, and
so can't deparse references to inner rel in join target list. */
5538 ok = false;
5539 break;
5540 }

Expanded comment.

Thank you for expanding your comment and giving examples.
Thanks to the above examples, I understood in what case planner wolud create semi-join,
which targetlist references Vars from inner join relation.

question2) In foreign_join_ok

* Constructing queries representing ANTI joins is hard, hence

Is this true? Is it hard to expand your approach to ANTI join
pushdown?

I haven't tried, so don't know.

I understand the situation.

The naming means additional conditions (for WHERE clause, by analogy
with ignore_conds and remote_conds). Not sure if subquery_expr sounds
better, but if you come with better idea, I'm fine with renaming them.

Sure.

question4) Although really detail, there is expression making space
such as
"ft4.c2 = ft2.c2" and one making no space such as "c1=ftupper.c1".
Is there reason for this difference? If not, need we use same
policy for making space?

Thank you.

Later, I'm going to look at other part of your patch.

Sincerely yours,
Yuuki Fujii

--
Yuuki Fujii
Information Technology R&D Center Mitsubishi Electric Corporation

Hi.

I took a quick look at the patch. It needs a rebase, although it applies
fine using patch.

A couple minor comments:

1) addl_conds seems a bit hard to understand, I'd use either the full
wording (additional_conds) or maybe extra_conds

2) some of the lines got quite long, and need a wrap

3) unknown_subquery_rels name is a bit misleading - AFAIK it's the rels
that can't be referenced from upper rels (per what the .h says). So they
are known, but hidden. Is there a better name?

4) joinrel_target_ok() needs a better comment, explaining *when* the
reltarget is safe for pushdown. The conditions are on the same row, but
the project style is to break after '&&'.

Also, I'd write

if (!IsA(var, Var))
continue;

which saves one level of nesting. IMHO that makes it more readable.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Hi.

Tomas Vondra писал 2023-01-19 20:49:

I took a quick look at the patch. It needs a rebase, although it
applies
fine using patch.

A couple minor comments:

1) addl_conds seems a bit hard to understand, I'd use either the full
wording (additional_conds) or maybe extra_conds

Renamed to additional_conds.

2) some of the lines got quite long, and need a wrap

Splitted some of them. Not sure if it's enough.

3) unknown_subquery_rels name is a bit misleading - AFAIK it's the rels
that can't be referenced from upper rels (per what the .h says). So
they
are known, but hidden. Is there a better name?

Renamed to hidden_subquery_rels. These are rels, which can't be referred
to from upper join levels.

4) joinrel_target_ok() needs a better comment, explaining *when* the
reltarget is safe for pushdown. The conditions are on the same row, but
the project style is to break after '&&'.

Added comment. It seems to be a rephrasing of lower comment in
joinrel_target_ok().

--
Best regards,
Alexander Pyhalov,
Postgres Professional

Hi, Alexander!

Thank you for working on this. I believe this is a very interesting patch,
which significantly improves our FDW-based distributed facilities. This is
why I decided to review this.

On Fri, Jan 20, 2023 at 11:00 AM Alexander Pyhalov <a.pyhalov@postgrespro.ru>
wrote:

Tomas Vondra писал 2023-01-19 20:49:

I took a quick look at the patch. It needs a rebase, although it
applies
fine using patch.

A couple minor comments:

1) addl_conds seems a bit hard to understand, I'd use either the full
wording (additional_conds) or maybe extra_conds

Renamed to additional_conds.

2) some of the lines got quite long, and need a wrap

Splitted some of them. Not sure if it's enough.

3) unknown_subquery_rels name is a bit misleading - AFAIK it's the rels
that can't be referenced from upper rels (per what the .h says). So
they
are known, but hidden. Is there a better name?

Renamed to hidden_subquery_rels. These are rels, which can't be referred
to from upper join levels.

4) joinrel_target_ok() needs a better comment, explaining *when* the
reltarget is safe for pushdown. The conditions are on the same row, but
the project style is to break after '&&'.

Added comment. It seems to be a rephrasing of lower comment in
joinrel_target_ok().

+   /*
+    * We can't push down join if its reltarget is not safe
+    */
+   if (!joinrel_target_ok(root, joinrel, jointype, outerrel, innerrel))
        return false;

As I get joinrel_target_ok() function do meaningful checks only for semi
join and always return false for all other kinds of joins. I think we
should call this only for semi join and name the function accordingly.

+ fpinfo->unknown_subquery_rels =
bms_union(fpinfo_o->unknown_subquery_rels,
+
fpinfo_i->unknown_subquery_rels);

Should the comment before this code block be revised?

+       case JOIN_SEMI:
+           fpinfo->joinclauses = list_concat(fpinfo->joinclauses,
+                                             fpinfo_i->remote_conds);
+           fpinfo->joinclauses = list_concat(fpinfo->joinclauses,
+                                              fpinfo->remote_conds);
+           fpinfo->remote_conds = list_copy(fpinfo_o->remote_conds);
+           fpinfo->unknown_subquery_rels =
bms_union(fpinfo->unknown_subquery_rels,
+                                           innerrel->relids);
+           break;

I think that comment before switch() should be definitely revised.

+ Relids hidden_subquery_rels; /* relids, which can't be referred to
+ * from upper relations */

Could this definition contain the positive part? Can't be referred to from
upper relations, but used internally for semi joins (or something like
that)?

Also, I think the machinery around the append_conds could be somewhat
simpler if we turn them into a list (list of strings). I think that should
make code clearer and also save us some memory allocations.

In [1] you've referenced the cases, when your patch can't push down
semi-joins. It doesn't seem impossible to handle these cases, but that
would make the patch much more complicated. I'm OK to continue with a
simpler patch to handle the majority of cases. Could you please add the
cases, which can't be pushed down with the current patch, to the test suite?

Links
1.
/messages/by-id/816fa8b1bc2da09a87484d1ef239a332@postgrespro.ru

------
Regards,
Alexander Korotkov

Alexander Korotkov писал 2023-10-30 19:05:

Hi, Alexander!

Thank you for working on this. I believe this is a very interesting
patch, which significantly improves our FDW-based distributed
facilities. This is why I decided to review this.

Hi. Thanks for reviewing.

+   /*
+    * We can't push down join if its reltarget is not safe
+    */
+   if (!joinrel_target_ok(root, joinrel, jointype, outerrel,
innerrel))
return false;

As I get joinrel_target_ok() function do meaningful checks only for
semi join and always return false for all other kinds of joins. I
think we should call this only for semi join and name the function
accordingly.

Done.

+ fpinfo->unknown_subquery_rels =
bms_union(fpinfo_o->unknown_subquery_rels,
+
fpinfo_i->unknown_subquery_rels);

Should the comment before this code block be revised?

Updated comment.

+       case JOIN_SEMI:
+           fpinfo->joinclauses = list_concat(fpinfo->joinclauses,
+                                             fpinfo_i->remote_conds);
+           fpinfo->joinclauses = list_concat(fpinfo->joinclauses,
+                                              fpinfo->remote_conds);
+           fpinfo->remote_conds = list_copy(fpinfo_o->remote_conds);
+           fpinfo->unknown_subquery_rels =
bms_union(fpinfo->unknown_subquery_rels,
+                                           innerrel->relids);
+           break;

I think that comment before switch() should be definitely revised.

+ Relids hidden_subquery_rels; /* relids, which can't be referred to
+ * from upper relations */

Could this definition contain the positive part? Can't be referred to
from upper relations, but used internally for semi joins (or something
like that)?

Made comment a bit more verbose.

Also, I think the machinery around the append_conds could be somewhat
simpler if we turn them into a list (list of strings). I think that
should make code clearer and also save us some memory allocations.

I've tried to rewrite it as managing lists.. to find out that these are
not lists.
I mean, in deparseFromExprForRel() we replace lists from both side with
one condition.
This allows us to preserve conditions hierarchy. We should merge these
conditions
in the end of IS_JOIN_REL(foreignrel) branch, or we'll push them too
high. And if we
deparse them in this place as StringInfo, I see no benefit to convert
them to lists.

In [1] you've referenced the cases, when your patch can't push down
semi-joins. It doesn't seem impossible to handle these cases, but
that would make the patch much more complicated. I'm OK to continue
with a simpler patch to handle the majority of cases. Could you
please add the cases, which can't be pushed down with the current
patch, to the test suite?

There are several cases when we can't push down semi-join in current
patch.

1) When target list has attributes from inner relation, which are
equivalent to some attributes of outer
relation, we fail to notice this.

2) When we examine A join B and decide that we can't push it down, this
decision is final - we state it in fdw_private of joinrel,
and so if we consider joining these relations in another order, we don't
reconsider.
This means that if later examine B join A, we don't try to push it down.
As semi-join can be executed as JOIN_UNIQUE_INNER or JOIN_UNIQUE_OUTER,
this can be a problem - we look at some of these paths and remember that
we can't push down such join.

--
Best regards,
Alexander Pyhalov,
Postgres Professional

Hi, Alexander!

On Tue, Oct 31, 2023 at 1:07 PM Alexander Pyhalov
<a.pyhalov@postgrespro.ru> wrote:

There are several cases when we can't push down semi-join in current
patch.

1) When target list has attributes from inner relation, which are
equivalent to some attributes of outer
relation, we fail to notice this.

2) When we examine A join B and decide that we can't push it down, this
decision is final - we state it in fdw_private of joinrel,
and so if we consider joining these relations in another order, we don't
reconsider.
This means that if later examine B join A, we don't try to push it down.
As semi-join can be executed as JOIN_UNIQUE_INNER or JOIN_UNIQUE_OUTER,
this can be a problem - we look at some of these paths and remember that
we can't push down such join.

Thank you for the revision.

I've revised the patch myself. I've replaced StringInfo with
additional conds into a list of strings as I proposed before. I think
the code became much clearer. Also, it gets rid of some unnecessary
allocations.

I think the code itself is not in bad shape. But patch lacks some
high-level description of semi-joins processing as well as comments on
each manipulation with additional conds. Could you please add this?

------
Regards,
Alexander Korotkov

Alexander Korotkov писал(а) 2023-11-27 03:49:

Thank you for the revision.

I've revised the patch myself. I've replaced StringInfo with
additional conds into a list of strings as I proposed before. I think
the code became much clearer. Also, it gets rid of some unnecessary
allocations.

I think the code itself is not in bad shape. But patch lacks some
high-level description of semi-joins processing as well as comments on
each manipulation with additional conds. Could you please add this?

Hi. The updated patch looks better. It seems I've failed to fix logic in
deparseFromExprForRel() when tried to convert StringInfos to Lists.

I've added some comments. The most complete description of how SEMI-JOIN
is processed, is located in deparseFromExprForRel(). Unfortunately,
there seems to be no single place, describing current JOIN deparsing
logic.

--
Best regards,
Alexander Pyhalov,
Postgres Professional

Hi, Alexander!

On Mon, Nov 27, 2023 at 5:11 PM Alexander Pyhalov
<a.pyhalov@postgrespro.ru> wrote:

Alexander Korotkov писал(а) 2023-11-27 03:49:

Thank you for the revision.

I've revised the patch myself. I've replaced StringInfo with
additional conds into a list of strings as I proposed before. I think
the code became much clearer. Also, it gets rid of some unnecessary
allocations.

I think the code itself is not in bad shape. But patch lacks some
high-level description of semi-joins processing as well as comments on
each manipulation with additional conds. Could you please add this?

Hi. The updated patch looks better. It seems I've failed to fix logic in
deparseFromExprForRel() when tried to convert StringInfos to Lists.

I've added some comments. The most complete description of how SEMI-JOIN
is processed, is located in deparseFromExprForRel(). Unfortunately,
there seems to be no single place, describing current JOIN deparsing
logic.

Looks good to me. I've made some grammar and formatting adjustments.
Also, I've written the commit message.

Now, I think this looks good. I'm going to push this if no objections.

------
Regards,
Alexander Korotkov

Alexander Korotkov писал(а) 2023-12-03 23:52:

Hi, Alexander!

On Mon, Nov 27, 2023 at 5:11 PM Alexander Pyhalov
<a.pyhalov@postgrespro.ru> wrote:

Alexander Korotkov писал(а) 2023-11-27 03:49:

Thank you for the revision.

I've revised the patch myself. I've replaced StringInfo with
additional conds into a list of strings as I proposed before. I think
the code became much clearer. Also, it gets rid of some unnecessary
allocations.

I think the code itself is not in bad shape. But patch lacks some
high-level description of semi-joins processing as well as comments on
each manipulation with additional conds. Could you please add this?

Hi. The updated patch looks better. It seems I've failed to fix logic
in
deparseFromExprForRel() when tried to convert StringInfos to Lists.

I've added some comments. The most complete description of how
SEMI-JOIN
is processed, is located in deparseFromExprForRel(). Unfortunately,
there seems to be no single place, describing current JOIN deparsing
logic.

Looks good to me. I've made some grammar and formatting adjustments.
Also, I've written the commit message.

Now, I think this looks good. I'm going to push this if no objections.

------
Regards,
Alexander Korotkov

Hi. No objections from my side.

Perhaps, some rephrasing is needed in comment in semijoin_target_ok():

"The planner can create semi-joins, which refer to inner rel
vars in its target list."

Perhaps, change "semi-joins, which refer" to "a semi-join, which refers
...",
as later we speak about "its" target list.

--
Best regards,
Alexander Pyhalov,
Postgres Professional

Hello,

While playing with this feature I found the following.

Two foreign tables:
postgres@demo_postgres_fdw(17.0)=# \det aircrafts|seats
List of foreign tables
Schema | Table | Server
--------+-----------+-------------
public | aircrafts | demo_server
public | seats | demo_server
(2 rows)

This query uses optimization:

postgres@demo_postgres_fdw(17.0)=# EXPLAIN (costs off, verbose) SELECT *
FROM aircrafts a
WHERE a.aircraft_code = '320' AND EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
QUERY PLAN >
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------->
Foreign Scan
Output: a.aircraft_code, a.model, a.range
Relations: (public.aircrafts a) SEMI JOIN (public.seats s)
Remote SQL: SELECT r1.aircraft_code, r1.model, r1.range FROM bookings.aircrafts r1 WHERE ((r1.aircraft_code = '320')) AND EXISTS (SELECT NULL FROM bookings.seats r2 WHERE ((r2.aircraft_code =>
(4 rows)

But optimization not used for NOT EXISTS:

postgres@demo_postgres_fdw(17.0)=# EXPLAIN (costs off, verbose) SELECT *
FROM aircrafts a
WHERE a.aircraft_code = '320' AND NOT EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------
Nested Loop Anti Join
Output: a.aircraft_code, a.model, a.range
-> Foreign Scan on public.aircrafts a
Output: a.aircraft_code, a.model, a.range
Remote SQL: SELECT aircraft_code, model, range FROM bookings.aircrafts WHERE ((aircraft_code = '320'))
-> Materialize
Output: s.aircraft_code
-> Foreign Scan on public.seats s
Output: s.aircraft_code
Remote SQL: SELECT aircraft_code FROM bookings.seats WHERE ((aircraft_code = '320'))
(10 rows)

Also, optimization not used after deleting first condition (a.aircraft_code = '320'):

postgres@demo_postgres_fdw(17.0)=# EXPLAIN (costs off, verbose) SELECT *
FROM aircrafts a
WHERE EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
QUERY PLAN
--------------------------------------------------------------------------------
Hash Join
Output: a.aircraft_code, a.model, a.range
Inner Unique: true
Hash Cond: (a.aircraft_code = s.aircraft_code)
-> Foreign Scan on public.aircrafts a
Output: a.aircraft_code, a.model, a.range
Remote SQL: SELECT aircraft_code, model, range FROM bookings.aircrafts
-> Hash
Output: s.aircraft_code
-> HashAggregate
Output: s.aircraft_code
Group Key: s.aircraft_code
-> Foreign Scan on public.seats s
Output: s.aircraft_code
Remote SQL: SELECT aircraft_code FROM bookings.seats
(15 rows)

But the worst thing is that replacing AND with OR causes breaking session and server restart:

postgres@demo_postgres_fdw(17.0)=# EXPLAIN (costs off, verbose) SELECT *
FROM aircrafts a
WHERE a.aircraft_code = '320' OR EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
server closed the connection unexpectedly
This probably means the server terminated abnormally
before or while processing the request.
The connection to the server was lost. Attempting reset: Failed.
The connection to the server was lost. Attempting reset: Failed.

--
Pavel Luzanov
Postgres Professional:https://postgrespro.com

On Fri, Feb 9, 2024 at 10:08 PM Pavel Luzanov <p.luzanov@postgrespro.ru> wrote:

While playing with this feature I found the following.

Two foreign tables:
postgres@demo_postgres_fdw(17.0)=# \det aircrafts|seats
List of foreign tables
Schema | Table | Server
--------+-----------+-------------
public | aircrafts | demo_server
public | seats | demo_server
(2 rows)

This query uses optimization:

postgres@demo_postgres_fdw(17.0)=# EXPLAIN (costs off, verbose) SELECT *
FROM aircrafts a
WHERE a.aircraft_code = '320' AND EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
QUERY PLAN >
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------->
Foreign Scan
Output: a.aircraft_code, a.model, a.range
Relations: (public.aircrafts a) SEMI JOIN (public.seats s)
Remote SQL: SELECT r1.aircraft_code, r1.model, r1.range FROM bookings.aircrafts r1 WHERE ((r1.aircraft_code = '320')) AND EXISTS (SELECT NULL FROM bookings.seats r2 WHERE ((r2.aircraft_code =>
(4 rows)

But optimization not used for NOT EXISTS:

postgres@demo_postgres_fdw(17.0)=# EXPLAIN (costs off, verbose) SELECT *
FROM aircrafts a
WHERE a.aircraft_code = '320' AND NOT EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------
Nested Loop Anti Join
Output: a.aircraft_code, a.model, a.range
-> Foreign Scan on public.aircrafts a
Output: a.aircraft_code, a.model, a.range
Remote SQL: SELECT aircraft_code, model, range FROM bookings.aircrafts WHERE ((aircraft_code = '320'))
-> Materialize
Output: s.aircraft_code
-> Foreign Scan on public.seats s
Output: s.aircraft_code
Remote SQL: SELECT aircraft_code FROM bookings.seats WHERE ((aircraft_code = '320'))
(10 rows)

Also, optimization not used after deleting first condition (a.aircraft_code = '320'):

postgres@demo_postgres_fdw(17.0)=# EXPLAIN (costs off, verbose) SELECT *
FROM aircrafts a
WHERE EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
QUERY PLAN
--------------------------------------------------------------------------------
Hash Join
Output: a.aircraft_code, a.model, a.range
Inner Unique: true
Hash Cond: (a.aircraft_code = s.aircraft_code)
-> Foreign Scan on public.aircrafts a
Output: a.aircraft_code, a.model, a.range
Remote SQL: SELECT aircraft_code, model, range FROM bookings.aircrafts
-> Hash
Output: s.aircraft_code
-> HashAggregate
Output: s.aircraft_code
Group Key: s.aircraft_code
-> Foreign Scan on public.seats s
Output: s.aircraft_code
Remote SQL: SELECT aircraft_code FROM bookings.seats
(15 rows)

But the worst thing is that replacing AND with OR causes breaking session and server restart:

postgres@demo_postgres_fdw(17.0)=# EXPLAIN (costs off, verbose) SELECT *
FROM aircrafts a
WHERE a.aircraft_code = '320' OR EXISTS (
SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
server closed the connection unexpectedly
This probably means the server terminated abnormally
before or while processing the request.
The connection to the server was lost. Attempting reset: Failed.
The connection to the server was lost. Attempting reset: Failed.

Thank you, Pavel. I'm looking into this.

------
Regards,
Alexander Korotkov

Hi, Pavel!

On Fri, Feb 9, 2024 at 10:08 PM Pavel Luzanov <p.luzanov@postgrespro.ru> wrote:

But optimization not used for NOT EXISTS:

Right, anti-joins are not supported yet.

Also, optimization not used after deleting first condition (a.aircraft_code = '320'):

This is a costing issue. Optimization worlds for me when set
"use_remote_estimate = true" for the server;

But the worst thing is that replacing AND with OR causes breaking session and server restart:

I haven't managed to reproduce this yet. Could you give more details:
machine, OS, compile options, backtrace?

------
Regards,
Alexander Korotkov

Hi, Alexander!

On 12.02.2024 05:27, Alexander Korotkov wrote:

But the worst thing is that replacing AND with OR causes breaking session and server restart:

I haven't managed to reproduce this yet. Could you give more details:
machine, OS, compile options, backtrace?

We already had off-list conversation with Alexander Pyhalov.

Yesterday, after rebuilding the server, I can't reproduce the error.
I have good reason to believe that the problem was on my side.
On Friday, I tested another patch and built the server several times.
Most likely, I just made a mistake during the server build.

Sorry for the noise.

--
Pavel Luzanov
Postgres Professional:https://postgrespro.com