Thread: Costing foreign joins in postgres_fdw

Ashutosh Bapat wrote:
> Costs for foreign queries are either obtained from the foreign server using EXPLAIN (if
> use_remote_estimate is ON) otherwise they are cooked up locally based on the statistics available. For
> joins as well, we have to do the same. If use_remote_estimates [1] is ON, we can get the costs from
> the foreign server. Rest of the mail discusses approaches for estimating the costs when
> use_remote_estimates is OFF.
> 
> 
> 1. Unlike base relations where the table data "has to be" fetched from the foreign server, a join
> doesn't "have to be" fetched from the foreign server. So, even if use_remote_estimate is OFF for a
> base relation, we do try to estimate something locally. But for a join that's not compulsory, so we
> can choose not to estimate anything and not push down the join if use_remote_estimate is OFF. Whether
> we do that depends upon how well we can estimate the join cost when use_remote_estimate is OFF.
> 
> 2. Locally estimating the cost of join that will be performed on the foreign server is difficult
> because we do not know which join strategy the foreign server is going to use, which in turn depends
> upon the availability of indexes, work memory, statistics about joining expressions etc. One way to do
> this is to use the cost of cheapest local join path built upon foreign outer and inner paths, to
> estimate the cost of executing the join at the foreign server The startup and run time costs for
> sending, parsing and planning query at the foreign server as well as the cost to fetch the tuples need
> to be adjusted, so that it doesn't get counted twice. We may assume that the cost for the foreign join
> will be some factor of the adjusted cost, like we have done for estimating cost of sort pushdown. The
> reason we choose cheapest path with foreign inner and outer paths is because that's likely to be a
> closer to the real estimate than the path which does not have foreign inner and outer paths. In the
> absence of such path, we should probably not push the join down since no local path has found pushing
> inner and outer to be cheaper and it's likely (certainly not a rule) that pushing the join in question
> down is not going to be cheaper than the local paths.
> 
> 
> 1st option is easy but it sounds too restrictive. 2nd option liberal but is complex.

My gut feeling is that for a join where all join predicates can be pushed down, it
will usually be a win to push the join to the foreign server.

So in your first scenario, I'd opt for always pushing down the join
if possible if use_remote_estimate is OFF.

Your second scenario is essentially to estimate that a pushed down join will
always be executed as a nested loop join, which will in most cases produce
an unfairly negative estimate.

What about using local statistics to come up with an estimated row count for
the join and use that as the basis for an estimate?  My idea here is that it
is always be a win to push down a join unless the result set is so large that
transferring it becomes the bottleneck.
Maybe, to come up with something remotely realistic, a formula like

sum of locally estimated costs of sequential scan for the base table
plus count of estimated result rows (times a factor)

Yours,
Laurenz Albe

On Fri, Dec 18, 2015 at 8:09 AM, Albe Laurenz <laurenz.albe@wien.gv.at> wrote:
> My gut feeling is that for a join where all join predicates can be pushed down, it
> will usually be a win to push the join to the foreign server.
>
> So in your first scenario, I'd opt for always pushing down the join
> if possible if use_remote_estimate is OFF.
>
> Your second scenario is essentially to estimate that a pushed down join will
> always be executed as a nested loop join, which will in most cases produce
> an unfairly negative estimate.

+1 to all that.  Whatever we do here for costing in detail, it should
be set up so that the pushed-down join wins unless there's some pretty
tangible reason to think, in a particular case, that it will lose.

> What about using local statistics to come up with an estimated row count for
> the join and use that as the basis for an estimate?  My idea here is that it
> is always be a win to push down a join unless the result set is so large that
> transferring it becomes the bottleneck.

This also sounds about right.

> Maybe, to come up with something remotely realistic, a formula like
>
> sum of locally estimated costs of sequential scan for the base table
> plus count of estimated result rows (times a factor)

Was this meant to say "the base tables", plural?

I think whatever we do here should try to extend the logic in
postgres_fdw's estimate_path_cost_size() to foreign tables in some
reasonably natural way, but I'm not sure exactly what that should look
like.  Maybe do what that function currently does for single-table
scans, and then add all the values up, or something like that.  I'm a
little worried, though, that the planner might then view a query that
will be executed remotely as a nested loop with inner index-scan as
not worth pushing down, because in that case the join actually will
not touch every row from both tables, as a hash or merge join would.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas wrote:
>> Maybe, to come up with something remotely realistic, a formula like
>>
>> sum of locally estimated costs of sequential scan for the base table
>> plus count of estimated result rows (times a factor)
>
> Was this meant to say "the base tables", plural?

Yes.

> I think whatever we do here should try to extend the logic in
> postgres_fdw's estimate_path_cost_size() to foreign tables in some
> reasonably natural way, but I'm not sure exactly what that should look
> like.  Maybe do what that function currently does for single-table
> scans, and then add all the values up, or something like that.  I'm a
> little worried, though, that the planner might then view a query that
> will be executed remotely as a nested loop with inner index-scan as
> not worth pushing down, because in that case the join actually will
> not touch every row from both tables, as a hash or merge join would.

That's exactly what I meant, minus a contribution for the estimated
result set size.

There are cases where a nested loop is faster than a hash join,
but I think it is rare that this is by orders of magnitude.

So I'd say it is a decent rough estimate, and that's the best we can
hope for here, if we cannot ask the remote server.

Yours,
Laurenz Albe