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