Re: postgres_fdw: Fix costing of remote sorts without remote estimates

Hi Jelte,

Thanks for working on this. Estimating the sort cost separately makes
sense to me, especially for joins and aggregates that return few rows.

1. I found a regression with a local filter and LIMIT:

CREATE EXTENSION postgres_fdw;
SELECT current_database() AS dbname,
current_user AS username,
current_setting('port') AS port,
split_part(current_setting('unix_socket_directories'), ',', 1)
AS socket_dir
\gset
CREATE SERVER loopback FOREIGN DATA WRAPPER postgres_fdw
OPTIONS (dbname :'dbname', host :'socket_dir', port :'port',
use_remote_estimate 'false');
CREATE USER MAPPING FOR CURRENT_USER SERVER loopback
OPTIONS (user :'username');

CREATE TABLE sort_src (id int, payload text);
INSERT INTO sort_src
SELECT i, repeat('x', 512) FROM generate_series(1, 20000) i;
CREATE FOREIGN TABLE sort_ft (id int, payload text) SERVER loopback
OPTIONS (table_name 'sort_src');
ANALYZE sort_src;
ANALYZE sort_ft;

CREATE FUNCTION local_filter(int) RETURNS boolean
LANGUAGE plpgsql IMMUTABLE AS $$
BEGIN
RETURN $1 > 0;
END
$$;

SET work_mem = '4MB';
EXPLAIN (ANALYZE, VERBOSE, COSTS OFF, TIMING OFF,
SUMMARY OFF, BUFFERS OFF)
SELECT id, payload FROM sort_ft
WHERE local_filter(id) ORDER BY id LIMIT 10;

With v1:

Limit (actual rows=10.00 loops=1)
Output: id, payload
-> Sort (actual rows=10.00 loops=1)
Output: id, payload
Sort Key: sort_ft.id
Sort Method: top-N heapsort Memory: 35kB
-> Foreign Scan on public.sort_ft (actual rows=20000.00 loops=1)
Output: id, payload
Filter: local_filter(sort_ft.id)
Remote SQL: SELECT id, payload FROM public.sort_src

On master or with my 0001 on top of v1:

Limit (actual rows=10.00 loops=1)
Output: id, payload
-> Foreign Scan on public.sort_ft (actual rows=10.00 loops=1)
Output: id, payload
Filter: local_filter(sort_ft.id)
Remote SQL: SELECT id, payload FROM public.sort_src ORDER BY
id ASC NULLS LAST

All three return the same rows. With v1, the local scan filters all
20,000 rows before sorting. With 0001, it stops after 10 rows.

The reason is this: estimate_path_cost_size() includes the local
filter's per-row cost in run_cost before calling
adjust_foreign_path_cost_for_sort(). That function moves the full
filter cost into startup_cost, where LIMIT cannot reduce it.

Here are the relevant costs for v1 and v1 + 0001. The first two cost
columns are for the Sort/ForeignScan; the last is the total cost of
the query with LIMIT 10:

path startup total LIMIT 10 total
v1 remote sort 11593.22 15833.22 11599.58
v1 local Sort 11073.07 11089.74 11073.10
0001 remote sort 6593.22 15833.22 6607.08

In v1, the local Sort has lower startup and total costs, so it wins.
0001 keeps the local filter cost in run_cost. The remote startup cost
then drops by 5000, and LIMIT can reduce the remaining local work.
After LIMIT, the remote path costs 6607.08 versus 11073.10 for the
local Sort plan, so remote ordering wins.

0001 fixes the local filter costs and can be applied on its own on top
of v1.

2. Local projection costs can also prevent LIMIT pushdown. Using
sort_ft above:

CREATE FUNCTION sort_project(int) RETURNS int
LANGUAGE plpgsql IMMUTABLE COST 8 AS $$
BEGIN
RETURN $1;
END
$$;
EXPLAIN (ANALYZE, VERBOSE, COSTS OFF, TIMING OFF,
SUMMARY OFF, BUFFERS OFF)
SELECT sort_project(id), sort_project(id + 1)
FROM sort_ft ORDER BY id LIMIT 10;

With v1:

Limit (actual rows=10.00 loops=1)
Output: (sort_project(id)), (sort_project((id + 1))), id
-> Foreign Scan on public.sort_ft (actual rows=10.00 loops=1)
Output: sort_project(id), sort_project((id + 1)), id
Remote SQL: SELECT id FROM public.sort_src ORDER BY id ASC NULLS LAST

On master or with my 0001 and 0002 on top of v1:

Foreign Scan on public.sort_ft (actual rows=10.00 loops=1)
Output: sort_project(id), sort_project((id + 1)), id
Remote SQL: SELECT id FROM public.sort_src ORDER BY id ASC NULLS
LAST LIMIT 10::bigint

The reason is this: when v1 estimates the path with remote ORDER BY and
LIMIT, estimate_path_cost_size() adds the local target's full per-row
cost to run_cost before calling adjust_foreign_path_cost_for_sort().
That call moves the cost of projecting all 20,000 rows into
startup_cost, which LIMIT cannot reduce. The path with a local Limit
keeps projection in run_cost and charges only the rows it consumes, so
it wins. Both plans shown above project 10 rows. In v1, the candidate
with remote LIMIT is overcosted; 0002 fixes that estimate.

0002 fixes the local projection costs and applies on top of 0001.
Each patch includes its regression tests.

Core regression and the postgres_fdw regression, isolation and TAP
tests passed with 0001 alone and with both patches applied.

After finding the first issue, I checked for other local costs being
included in the remote sort's input cost. That led me to the projection
issue in point 2. I also checked the costs of remote scans, filters,
joins and aggregation, and haven't found another instance of this
problem.

Regards,
Rui