postgres_fdw: Fix costing of remote sorts without remote estimates

Hi,

Thank you very much for the work and the excellent explanation of the approach.

Please find a few questions / observations inline,

On Tue, Sep 29, 2026 at 10:10 AM Jelte Fennema-Nio <postgres@jeltef.nl> wrote:

tl;dr simpler code that results in better plans

Without use_remote_estimate, postgres_fdw has no way to know what a remote
sort costs. The heuristic used so far was to multiply the path's cost by
DEFAULT_FDW_SORT_MULTIPLIER (1.2). Commit f18c944b61 introduced it and
its message explains that the intent of that constant was to prefer a
remote sort over a local one (if a sort is useful). In practice that
doesn't actually work in lots of cases though.

The surcharge has no relation to the number of rows being sorted, so for an
expensive path that produces few rows, such as an aggregate or a join, it is
arbitrarily larger than the cost of actually sorting the output. Since the
alternative, a local Sort over the unsorted foreign path, is costed
accurately, the pushed-down sort always lost in those cases. See the
expected regress output changes in the patch for examples.

The later commit ffab494a4d ran into this issue too[1]. It tried to fix
this in two ways depending on the situation:

1. By calculating what a local sort would be and using that same value
for the remote.
2. By reducing DEFAULT_FDW_SORT_MULTIPLIER to 1.05 in one place in the
code, which was noted in the thread as being chosen fairly
arbitrarily to improve some plans[1].

This commit generalizes that first approach and uses it for every sorted
foreign path, with one slight improvement: Instead of using the full cost of
the local sort, it's multiplied by a fraction (0.8). That way the remote
and local sort don't tie, but the remote sort is preferred. This answers
the open question from [1]: no percentage of the path cost is reasonable,
because the surcharge should scale with the sort, not with the path.

* Regression tests check plan shape only. However, a visually
inspected better looking plan might not be a faster plan.
* Regression tests might not contain sufficient data size for us to
draw a strong conclusion. Sort cost grows as N·log N while scan cost
grows linearly. Behavior at 10M+ rows could be quite different.
* A corner case would be if the remote has an index on the sort key,
the real sort is nearly free. The new costing charges 80% of a full
sort, which could push the planner away from remote-ordered scans it
used to pick for large base tables.
* The patch in a way calls out that 1.2 and 1.05 were arbitrary. It
then brings in 0.8 without showing why 0.8 is better than 0.6 or 0.95.
Wouldn't the same criticism apply to the new constant.
* The patch mentions that the new plans are better, we should probably
compare the plans with use_remote_estimate = true. The remote planner
is aware of things the local heuristic can't fathom, e.g. Remote
indexes etc. What would happen in these cases ?

This changes a bunch of plans in our existing tests for the better:

1. Pushing down a Sort node to the remote side
2. Changing a local merge join on top of remotely sorted scan to a hash
join over unsorted remote scan.
3. Changing a local merge append over multiple remotely sorted scans to
a hash aggregate over unsorted remote scans.

To make a convincing case for this patch, I would,

1. Run the regression and benchmark queries with use_remote_estimate =
true and record those plans. Then show that the new local-estimate
plans match them more often than the old ones do.
2. Try TPC-H or TPC-DS over a sharded postgres_fdw setup. Report how
many plans changed, how many got faster or slower, and by how much.
3. Try different values for the heuristic fraction.
4. Look for worst cases and regressions with the current heuristic value.

Currently I don't have time to test with the above variations. I will
bookmark this work and try out some tests when I get some cycles.

Thank you once again for the work,
Narayanan

On Thu, 1 Oct 2026 at 02:12, Narayanan Venkateswaran
<narayananvpostgres@gmail.com> wrote:

meta: Can you please not copy paste your LLM output verbatim?

* Regression tests check plan shape only. However, a visually
inspected better looking plan might not be a faster plan.

The logic in postgres_fdw is that more pushdown to the remote is
always better. No need for benchmarks.

* A corner case would be if the remote has an index on the sort key,
the real sort is nearly free. The new costing charges 80% of a full
sort, which could push the planner away from remote-ordered scans it
used to pick for large base tables.

No, because the local sort would still be more expensive than the remote sort.

* The patch in a way calls out that 1.2 and 1.05 were arbitrary. It
then brings in 0.8 without showing why 0.8 is better than 0.6 or 0.95.
Wouldn't the same criticism apply to the new constant.

Yes it's arbitrary, but the exact constant doesn't matter. I tried
different factors. As long as the remote sort is significantly cheaper
than a local sort it will always be picked.

* The patch mentions that the new plans are better, we should probably
compare the plans with use_remote_estimate = true. The remote planner
is aware of things the local heuristic can't fathom, e.g. Remote
indexes etc. What would happen in these cases ?

We have tests, they don't change. This logic is only used when remote
estimates are unavailable.

On Thu, 1 Oct 2026 at 02:12, Narayanan Venkateswaran
<narayananvpostgres@gmail.com> wrote:

Hi,

It is very kind of you to reply to my comments on the work. This is
very nice work, thank you.

On Thu, Oct 1, 2026 at 8:17 PM Jelte Fennema-Nio <postgres@jeltef.nl> wrote:

On Thu, 1 Oct 2026 at 02:12, Narayanan Venkateswaran
<narayananvpostgres@gmail.com> wrote:

meta: Can you please not copy paste your LLM output verbatim?

You observed correctly. I was unfamiliar with this part of the
codebase and did use LLMs to understand the area better. I posted only
what I understood and was hoping that my comments will give attention
to good work.

Thank you,
Narayanan

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

On Fri Oct 2, 2026 at 6:29 PM CEST, Rui Zhao wrote:

1. I found a regression with a local filter and LIMIT:
2. Local projection costs can also prevent LIMIT pushdown. Using
sort_ft above:

Thanks for the review and finding these plan-regressions. It turns out
that the underlying problem isn't specific to my patch. With slightly
different queries master picks the same kind of bad plans. I did not use
your suggested fixes. Instead I changed estimate_path_cost_size() to
build up the costs in the order the work happens: remote work, then
transfer, then local work. That approach results in less code, and
that code is also easier to understand (imo). See the newly attached
patchset for details. It contains three preparatory patches before my
original patch:

1. Starts using run_cost instead of total_cost to make the fix easier to
understand and also fixes a small bug
2. Adds tests to show the bad plans on master
3. Fixes the bad plans in the tests introduced by 2
4. My original patch (I only improved the comments a bit)

Hi Jelte,

Thanks for separating the remote and local costs. The patch order is
clearer, and both examples from my last mail now get the expected plans.
I found two remaining aggregate-costing cases in 0003.

The attached patches add the examples below as regression tests.
They use ft1 and ft2 from postgres_fdw.sql, and your local_filter and
local_project functions.

1. My 0001 fixes the missing remote projection cost for rows filtered
out by local HAVING.

CREATE FUNCTION remote_value(bigint) RETURNS bigint
LANGUAGE plpgsql IMMUTABLE COST 100 AS $$
BEGIN
RETURN $1;
END
$$;
-- Allow remote_value() to be pushed down to the remote server.
ALTER EXTENSION postgres_fdw ADD FUNCTION remote_value(bigint);
ALTER SERVER loopback OPTIONS (ADD extensions 'postgres_fdw');

EXPLAIN (VERBOSE)
SELECT c2, remote_value(sum(c1)), count(*)
FROM ft1 GROUP BY c2 ORDER BY c2;

EXPLAIN (VERBOSE)
SELECT c2, remote_value(sum(c1)), count(*)
FROM ft1 GROUP BY c2
HAVING local_filter(count(*)::int) ORDER BY c2;

Both are Foreign Scans with exactly the same Remote SQL:

SELECT c2, public.remote_value(sum("C 1")), count(*)
FROM "S 1"."T 1" GROUP BY 1 ORDER BY c2 ASC NULLS LAST

Their estimated startup costs are:

v2 v2 + my 0001 + my 0002
without local HAVING 131.23 131.23
with local HAVING 129.48 131.23

The reason is that estimate_path_cost_size() adds
remote_tlist_cost.per_tuple * rows before costing the sort. Here rows
already includes the local HAVING selectivity: only 3 rows are expected
to remain out of the 10 fetched rows.
With remote_value's declared COST of 100, this removes
7 * 100 * cpu_operator_cost = 1.75 from startup cost, although the
remote server still evaluates remote_value() for all 10 fetched rows.
EXPLAIN ANALYZE returned 10 rows in both cases.

0001 uses retrieved_rows for that charge. Its test raises remote_value's
COST from 100 to 200 to check that startup cost increases by
(200 - 100) * 10 * cpu_operator_cost for the 10 fetched rows:

ALTER FUNCTION remote_value(bigint) COST 200;
EXPLAIN (VERBOSE)
SELECT c2, remote_value(sum(c1)), count(*)
FROM ft1 GROUP BY c2
HAVING local_filter(count(*)::int) ORDER BY c2;

With 0001, the increase is charged for all 10 rows as expected.

2. My 0002 fixes duplicate charges for remotely computed expressions
in local projection costs.

CREATE FUNCTION remote_key(int) RETURNS int
LANGUAGE plpgsql IMMUTABLE COST 100 AS $$
BEGIN
RETURN $1;
END
$$;
ALTER EXTENSION postgres_fdw ADD FUNCTION remote_key(int);
ALTER FUNCTION local_project(int) COST 9;

EXPLAIN (VERBOSE)
SELECT local_project(remote_key(c2)), count(*)
FROM ft1 GROUP BY remote_key(c2) ORDER BY remote_key(c2);

EXPLAIN (VERBOSE)
SELECT local_project(remote_key(c2)),
local_project(remote_key(c2) + 1), count(*)
FROM ft1 GROUP BY remote_key(c2) ORDER BY remote_key(c2);

Again, both are Foreign Scans with the same Remote SQL:

SELECT count(*), public.remote_key(c2) FROM "S 1"."T 1"
GROUP BY 2 ORDER BY public.remote_key(c2) ASC NULLS LAST

Their estimated total costs are:

v2 v2 + my 0001 + my 0002
one local projection 383.58 381.08
two local projections 386.33 381.33
increase 2.75 0.25

Compared with one local projection, two local projections should add
only 0.25: 10 * (9 + 1) * cpu_operator_cost. Each of the 10 rows needs
one extra local_project() call, with COST 9, and one integer addition,
with cost 1.

On v2, the increase is 0.25 + 2.50 = 2.75. The extra 2.50 is
10 * 100 * cpu_operator_cost: another charge for remote_key(), whose
result is already fetched. Here 100 is remote_key's declared COST.

The reason is that estimate_path_cost_size() adds the whole target cost,
then subtracts the remote tlist cost once:

run_cost += target->cost.per_tuple * rows;
if (IS_UPPER_REL(foreignrel))
run_cost -= remote_tlist_cost.per_tuple * rows;

Even the first query counts remote_key(c2) twice in the target: once
inside local_project() and once as the grouping/sort output. The remote
tlist cost is subtracted only once. The second local projection adds
another reference, but the deduction stays the same.

0002 adds replace_remote_projection_exprs() to replace every reference
to a fetched expression with a Var in a copy used for costing. It then
costs that copy, charging only the local work.

The two attachments apply on top of v2, in order. Core regression and
the postgres_fdw tests passed.

Regards,
Rui