Foreign join search stops on the first try

Hi.

I was investigating why foreign join is not happening and found the
following issue. When we search for foreign join path we stop on the
first try. For example, in case
A JOIN B JOIN C where all of them are foreign tables on the same server
firstly we estimate A JOIN B, A JOIN C and B JOIN C costs. Then we
select one of them (let's say A JOIN B) and estimate (A JOIN B) JOIN C
cost. On this stage we fill in joinrel->fdw_private in joinrel (A, B,
C). Now we could look at A JOIN (B JOIN C), but we don't, as
in contrib/postgres_fdw/postgres_fdw.c:5962 (in
postgresGetForeignJoinPaths()) we have:

/*
* Skip if this join combination has been considered already.
*/
if (joinrel->fdw_private)
return;

This can lead to situation when A JOIN B JOIN C cost is not correctly
estimated (as we don't look at another join orders) and foreign join is
not pushed down when it would be efficient.

Attached patch tries to fix this. Now we collect different join paths
for joinrels, if join is possible at all. However, as we don't know what
path is really selected, we can't precisely estimate fpinfo costs.

The following example shows the case, when we fail to push down foreign
join due to mentioned issue.

create extension postgres_fdw;

DO $d$
BEGIN
EXECUTE $$CREATE SERVER loopback FOREIGN DATA WRAPPER
postgres_fdw
OPTIONS (dbname '$$||current_database()||$$',
port '$$||current_setting('port')||$$'
)$$;
END
$d$;

create user MAPPING FOR PUBLIC SERVER loopback ;

CREATE SCHEMA test;

CREATE TABLE test.district (
d_id smallint NOT NULL PRIMARY KEY,
d_next_o_id integer NOT NULL,
d_name varchar(100) NOT NULL
);

CREATE TABLE test.stock (
s_i_id integer NOT NULL PRIMARY KEY,
s_quantity smallint NOT NULL,
s_data varchar(100) NOT NULL
);

CREATE TABLE test.order_line (
ol_o_id integer NOT NULL PRIMARY KEY,
ol_i_id integer NOT NULL,
ol_d_id smallint NOT NULL
);

import foreign schema test from server loopback into public ;

INSERT INTO district SELECT i, 20000 + 20*i , 'test' FROM
generate_series(1,10) i;
INSERT INTO stock SELECT i, round(random()*100) + 10, 'test data' FROM
generate_series(1,10000) i;
INSERT INTO order_line SELECT i, i%10000, i%10 FROM
generate_series(1,30000) i;

analyze test.order_line, test.district ,test.stock;
analyze order_line, district ,stock;

Without patch:

explain analyze verbose SELECT * FROM order_line, stock, district WHERE
ol_d_id = 1 AND d_id = 1 AND (ol_o_id < d_next_o_id) AND ol_o_id >=
(d_next_o_id - 20) AND s_i_id = ol_i_id AND s_quantity < 11;

QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=382.31..966.86 rows=2 width=37) (actual
time=5.459..5.466 rows=0 loops=1)
Output: order_line.ol_o_id, order_line.ol_i_id, order_line.ol_d_id,
stock.s_i_id, stock.s_quantity, stock.s_data, district.d_id,
district.d_next_o_id, district.d_name
Hash Cond: (order_line.ol_i_id = stock.s_i_id)
-> Foreign Scan (cost=100.00..683.29 rows=333 width=21) (actual
time=2.773..2.775 rows=2 loops=1)
Output: order_line.ol_o_id, order_line.ol_i_id,
order_line.ol_d_id, district.d_id, district.d_next_o_id, district.d_name
Relations: (public.order_line) INNER JOIN (public.district)
Remote SQL: SELECT r1.ol_o_id, r1.ol_i_id, r1.ol_d_id, r3.d_id,
r3.d_next_o_id, r3.d_name FROM (test.order_line r1 INNER JOIN
test.district r3 ON (((r1.ol_o_id < r3.d_next_o_id)) AND ((r1.ol_o_id >=
(r3.d_next_o_id - 20))) AND ((r3.d_id = 1)) AND ((r1.ol_d_id = 1))))
-> Hash (cost=281.42..281.42 rows=71 width=16) (actual
time=2.665..2.665 rows=48 loops=1)
Output: stock.s_i_id, stock.s_quantity, stock.s_data
Buckets: 1024 Batches: 1 Memory Usage: 11kB
-> Foreign Scan on public.stock (cost=100.00..281.42 rows=71
width=16) (actual time=2.625..2.631 rows=48 loops=1)
Output: stock.s_i_id, stock.s_quantity, stock.s_data
Remote SQL: SELECT s_i_id, s_quantity, s_data FROM
test.stock WHERE ((s_quantity < 11))
Planning Time: 1.812 ms
Execution Time: 8.534 ms
(15 rows)

With patch:

explain analyze verbose SELECT * FROM order_line, stock, district WHERE
ol_d_id = 1 AND d_id = 1 AND (ol_o_id < d_next_o_id) AND ol_o_id >=
(d_next_o_id - 20) AND s_i_id = ol_i_id AND s_quantity < 11;


QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Foreign Scan (cost=100.00..974.88 rows=2 width=37) (actual
time=3.399..3.400 rows=0 loops=1)
Output: order_line.ol_o_id, order_line.ol_i_id, order_line.ol_d_id,
stock.s_i_id, stock.s_quantity, stock.s_data, district.d_id,
district.d_next_o_id, district.d_name
Relations: ((public.order_line) INNER JOIN (public.district)) INNER
JOIN (public.stock)
Remote SQL: SELECT r1.ol_o_id, r1.ol_i_id, r1.ol_d_id, r2.s_i_id,
r2.s_quantity, r2.s_data, r3.d_id, r3.d_next_o_id, r3.d_name FROM
((test.order_line r1 INNER JOIN test.district r3 ON (((r1.ol_o_id <
r3.d_next_o_id)) AND ((r1.ol_o_id >= (r3.d_next_o_id - 20))) AND
((r3.d_id = 1)) AND ((r1.ol_d_id = 1)))) INNER JOIN test.stock r2 ON
(((r1.ol_i_id = r2.s_i_id)) AND ((r2.s_quantity < 11))))
Planning Time: 0.928 ms
Execution Time: 4.511 ms

--
Best regards,
Alexander Pyhalov,
Postgres Professional

This code was written long ago. So I may have some recollection
errors. But AFAIR, the reasons we wanted to avoid repeated
estimation/planning for the same foreign join rel were
1. If use_remote_estimate = true, we fetch EXPLAIN output from the
foreign server for various pathkeys. Fetching EXPLAIN output is
expensive. Irrespective of the join order being considered locally, we
expect the foreign server to give us the same cost since the join is
the same. So we avoid running EXPLAIN again and again.
2. If use_remote_estimate = false, the logic to estimate a foreign
join locally is independent of the join order so should yield same
cost again and again. For some reason that doesn't seem to be the case
here.

On Tue, Jan 25, 2022 at 1:26 PM Alexander Pyhalov
<a(dot)pyhalov(at)postgrespro(dot)ru> wrote:

>
> Without patch:
>
> explain analyze verbose SELECT * FROM order_line, stock, district WHERE
> ol_d_id = 1 AND d_id = 1 AND (ol_o_id < d_next_o_id) AND ol_o_id >=
> (d_next_o_id - 20) AND s_i_id = ol_i_id AND s_quantity < 11;
... clipped
> test.stock WHERE ((s_quantity < 11))
> Planning Time: 1.812 ms
> Execution Time: 8.534 ms
> (15 rows)
>
> With patch:
>
> explain analyze verbose SELECT * FROM order_line, stock, district WHERE
> ol_d_id = 1 AND d_id = 1 AND (ol_o_id < d_next_o_id) AND ol_o_id >=
> (d_next_o_id - 20) AND s_i_id = ol_i_id AND s_quantity < 11;
>
... clipped
> Planning Time: 0.928 ms
> Execution Time: 4.511 ms

It is surprising that the planning time halves with the patch. I
expected it to increase slightly since we will compute estimates
thrice instead of once.

What is use_remote_estimate? Is it ON/OFF?

If we want to proceed along this line, we should take care not to fire
more EXPLAIN queries on the foreign server.

--
Best Wishes,
Ashutosh Bapat

Ashutosh Bapat писал 2022-01-25 17:08:
> This code was written long ago. So I may have some recollection
> errors. But AFAIR, the reasons we wanted to avoid repeated
> estimation/planning for the same foreign join rel were
> 1. If use_remote_estimate = true, we fetch EXPLAIN output from the
> foreign server for various pathkeys. Fetching EXPLAIN output is
> expensive. Irrespective of the join order being considered locally, we
> expect the foreign server to give us the same cost since the join is
> the same. So we avoid running EXPLAIN again and again.
> 2. If use_remote_estimate = false, the logic to estimate a foreign
> join locally is independent of the join order so should yield same
> cost again and again. For some reason that doesn't seem to be the case
> here.

Hi.
use_remote_estimate was set to false in our case, and yes, it fixed this
issue.
The problem is that if use_remote_estimate = false, the logic to
estimate a foreign join locally
is not independent from the join order.

In above example, without patch we see plan with cost:
cost=382.31..966.86 rows=2 width=37

If we avoid exiting on (joinrel->fdw_private), we can see in gdb the
following cases, when joining all 3 relations:

case 1:
outerrel:relids (stock, order_line), startup_cost = 100, total_cost =
2415.9200000000001, rel_startup_cost = 0, rel_total_cost = 2315.5,
retrieved_rows = 21
innerrel: relid (district) startup_cost = 100, total_cost =
101.14500000000001, rel_startup_cost = 0, rel_total_cost = 1.125,
retrieved_rows = 1
joinrel: startup_cost = 100, total_cost = 2416.875, retrieved_rows = 2

case 2:
outerrel: relids (district, order_line), startup_cost = 100, total_cost
= 281.41999999999996, rel_total_cost = 180, retrieved_rows = 71
innerrel: relid (stock), startup_cost = 100, total_cost =
683.28500000000008, rel_startup_cost = 0, rel_total_cost = 576.625,
retrieved_rows = 333
joinrel: startup_cost = 100, total_cost = 974.88, retrieved_rows = 2

So, (stock join order_line) join district has different cost from
(district join order_line) join stock.

>
> On Tue, Jan 25, 2022 at 1:26 PM Alexander Pyhalov
> <a(dot)pyhalov(at)postgrespro(dot)ru> wrote:
>
>
> It is surprising that the planning time halves with the patch. I
> expected it to increase slightly since we will compute estimates
> thrice instead of once.

I wouldn't look at estimate times here precisely (and would looked at
costs). Real example where we found it had 100 times more data, but
effect was the same. Here some differences in planing time could be
related to restarting instances with or without patches.

>
> What is use_remote_estimate? Is it ON/OFF?
>

Yes, it was off.

> If we want to proceed along this line, we should take care not to fire
> more EXPLAIN queries on the foreign server.

You are correct. Fixed patch to avoid extensive join search when
use_remote_estimate is true.

--
Best regards,
Alexander Pyhalov,
Postgres Professional