Re: [PATCH] postgres_fdw: Fix cost estimation for semi join pushdown

Hi,

Since v1 did not receive any replies, I thought I would try to explain
the issue more clearly, this time with a demonstration where the plan
actually changes.

Attached is v2. The code change itself is unchanged; I have replaced
the regression test because the v1 test produced the same EXPLAIN
output with and without the fix.

PROBLEM DESCRIPTION

When postgres_fdw estimates locally whether a join is worth pushing
down (use_remote_estimate = off, the default),
estimate_path_cost_size() does:

nrows = fpinfo_i->rows * fpinfo_o->rows;
...
run_cost += nrows * join_cost.per_tuple;
nrows = clamp_row_est(nrows * fpinfo->joinclause_sel);
run_cost += nrows * remote_conds_cost.per_tuple;

For an inner join, joinclause_sel is a probability per cross-product
row pair, so scaling the cross product by it yields the join's output
size. For a semi join, however, joinclause_sel (computed by
clauselist_selectivity(), i.e. eqjoinsel_semi()) represents the
fraction of outer rows that have at least one match in the inner
relation -- a probability per outer row, rather than per row pair.

As a result, multiplying it into the cross product appears to charge
the remote quals on

outer_rows * inner_rows * P(match)

rows, while the semi join can produce at most

outer_rows * P(match)

rows.

This can inflate that cost term by roughly the inner relation's row
count and make semi-join pushdown look more expensive than it actually
is.

This also seems consistent with how foreign_join_ok() already treats
post-join local conditions: they are quals applied to the join output,
rather than predicates whose selectivity is combined with the cross
product.

DEMONSTRATION

Using loopback postgres_fdw with all cost settings at their defaults,
the inner table holds the 100 distinct values 0-99; the outer table
has 200 rows (a = 1..200) whose join column is b = i % 100. Every
outer row has a match, so the planner estimates the semi join's output
at the full 200 outer rows (joinclause_sel = 1), while the cross
product is 200 * 100 = 20,000 rows.

The query also has five pushed-down quals on the outer relation:

SELECT t1.a
FROM ft1 t1
WHERE t1.a >= 0 AND t1.a >= -1 AND t1.a >= -2
AND t1.a >= -3 AND t1.a >= -4
AND EXISTS (SELECT 1 FROM ft2 t2 WHERE t2.b = t1.b);

Without the patch, the planner chooses to fetch both tables and perform
the semi join locally:

Hash Semi Join (cost=224.25..274.50 rows=200)
Hash Cond: (t1.b = t2.b)
-> Foreign Scan on ft1 t1
-> Hash
-> Foreign Scan on ft2 t2

With the patch, the whole semi join is pushed down as one remote query
(abridged):

Foreign Scan (cost=100.00..202.00 rows=200)
Relations: (ft1 t1) SEMI JOIN (ft2 t2)
Remote SQL: SELECT r1.a FROM t1 r1 WHERE ((r1.a >= 0)) AND ...
AND EXISTS (SELECT NULL FROM t2 r2
WHERE ((r1.b = r2.b)))

For comparison, I made the losing pushed-down path visible before the
patch by temporarily disabling the local join strategies; no cost
parameter was changed:

before after
startup 100.00 100.00
other costs 49.50 49.50
join quals on cross
product 50.00 50.00
pushed-down quals 250.00 2.50
------------------------------------------------
total 449.50 202.00

local semi join 274.50 274.50

The total costs above come from EXPLAIN; the individual components
follow from the cost model's inputs. The cross product is 20,000
rows, joinclause_sel is 1, and each of the five quals costs one
cpu_operator_cost (0.0025) per row. Thus the remote quals contribute

20,000 * 5 * 0.0025 = 250.00

to the cost before the fix, instead of

200 * 5 * 0.0025 = 2.50.

The 247.50 difference accounts for the change in the pushed-down path's
total cost, which in this example is enough to change the selected plan
from the 274.50 local semi join to the 202.00 pushed-down path.

The new regression test uses this setup. At default settings it plans
the local semi join without the fix and the pushed-down Foreign Scan
with it. The postgres_fdw regression suite passes with the fix; with
only the code change reverted, this new test fails.

I've registered the patch in the PG20-3 CommitFest.

I would appreciate any comments or suggestions.

Regards,
Ziming Zhang