Обсуждение: 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.pyhalov@postgrespro.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.pyhalov@postgrespro.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