Join push-down support for foreign tables

Hi all,

In 2011 I proposed join push-down support for foreign tables, which
would improve performance of queries which contain join between
foreign tables in one server, but it has not finished before time-up.
This performance improvement would widen application range of foreign
tables, so I'd like to tackle the work again.

The descriptions below are based on previous discussions and additional studies.

Background
==========

At the moment FDWs can't handle join, so every join are processed on
local side even if the source relations are on the same server. It's
apparently inefficient to fetch possible rows from remote and join
them on local and waste some of them since join condition doesn't
match. If FDW (typically SQL-based FDWs like postgres_fdw) can get
control of JOIN operation, it would optimize queries for source tables
into a join query and avoid transfer of un-match rows.

With this improvement, most of joins in usual use, especially joins
between large foreign tables which don't match much, would become
remarkablly fast, for the reasons below.

a) less data transfer
Especially for inner joins, result of join is usually much smaller
than source tables. If the original target list doesn't contain join
keys, FDW might be able to omit from the SELECT list of remote queries
because they are only necessary on remote side.

b) more optimization on remote side
Join query would provide remote data source more optimization chances,
such as using index.

Changes expected
================

In the past development trial, these changes seem necessary at least.

(1) Add server oid field to RelOptInfo
This attribute is set only when the RelOptInfo is a joinrel, and all
underlying base relations are foreign tables and they have same server
oid. This field is set through join consideration from lower join
level to high (many tables) level, IOW from the bottom to the top. If
all base relations joined in a query are on same server, top
RelOptInfo which represents final output has valid server oid. In
such case, whole query could be pushed down to the server and user can
get most efficient result.

New helper function GetFdwRoutineByServerId(Oid serverid) which
returns FdwRoutine of given server oid would be handy.

(2) Add new path node for foreign join
New path node ForeignJoinPath, which inherits JoinPath like other join
path nodes, represents a join between ForeignPath or ForeignJoinPath.
ForeignJoinPath has fdw_private list to hold FDW-specific information
through the path consideration phase. This is similar to fdw_private
of ForeignPath path node.

This node cares only type of join such as INNER JOIN and LEFT OUTER
JOIN, but doesn't care how to do it. IOW foreign join is not special
case of existing join nodes such as nested loops, merge join and hash
join. FDW can implement a foreign join in arbitrary way, for
instance, file_fdw can have already-joined file for particular
combination for optimization, and postgres_fdw can generate a SELECT
query which contains JOIN clause and avoid essentially unnecessary
data transfer.

At the moment I'm not sure whether we should support SEMI/ANTI join in
the context of foreign join. It would require postgres_fdw (or other
SQL-based FDWs) to generate query with subquery connected with IN/NOT
IN clause, but it seems too far to head to in the first version.

We (and especially FDW authors) need to note that join push-down is
not the best way in some situations. In most cases OUTER JOIN
populates data on remote side more than current FDWs transfer,
especially for FULL OUTER JOIN and
CROSS JOIN (cartesian product).

(3) Add new plan node for foreign join
New plan node ForeignJoin, which inherits Join like other join plan
nodes. This node is similar to other join plan nodes such as
NestLoop, MergeJoin and HashJoin, but it delegates actual processing
to FDW associated to the server.

This means that new plan state node for ForeignJoin, say
ForeignJoinState, is also needed.

(4) Add new FDW API functions
Adding Join push-down support requires some functions to be added to
FdwRoutine to give control to FDWs.

a) GetForeignJoinPaths()
This allows FDWs to provide alternative join paths for a join
RelOptInfo. This is called from add_paths_to_joinrel() after
considering other join possibilities, and FDW should call add_path()
for each possible foreign join path. Foreign join paths are built
similarly to existing join paths, in a bottom-up manner.

FDWs may push ordered or unordered paths here, but combination of sort
keys would bloat up easily if FDW has no information about efficient
patterns such as remote indexes. FDW should not add too many paths to
prevent exponential overhead of join combination.

b) GetForeignJoinPlan()
This creates ForeignJoin plan node from ForeignJoinPath and other
planner infromation.

c) Executor functions for ForeignJoin plan node
A set of funcitons for executing ForeignJoin plan node is also needed.
Begin/ReScan/Iterate/End are basic operations of a plan node, so we
need to provide them for ForeignJoin node.

Issues
======

(1) Separate cost estimation phases?
For existing join paths, planner estimates their costs in two phaeses.
In the first phase initial_cost_foo(), here foo is one of
nestloop/mergejoin/hashjoin, produces lower-bound estimates for
elimination. The second phase is done for only promising paths which
passed add_path_precheck(), by final_cost_foo() for cost and result
size. I'm not sure that we need to follow this manner, since FDWs
would be able to estimate final cost/size with their own methods.

(2) How to reflect cost of transfer
Cost of transfer is dominant in foreign table operations, including
foreign scans. It would be nice to have some mechanism to reflect
actual time of transfer to the cost estimation. An idea is to have a
FDW option which represents cost factor of transfer, say
transfer_cost.

(3) SELECT-with-Join SQL generation in postgres_fdw
Probably Postgres-XC's shipping code would help us for implementing
deparse JOIN SQL, but I've not studied it fully, I'll continue the
study.

(4) criteria for push-down
It is assumed that FDWs can push joins down to remote when all foreign
tables are in same server. IMO a SERVER objects represents a logical
data source. For instance database for postgres_fdw and other
connection-based FDWs, and disk volumes (or directory?) for file_fdw.
Is this reasonable assumption?

Perhaps more issues would come out later, but I'd like to get comments
about the design.

(5) Terminology
I used "foreign join" as a process which joins foreign tables on
*remote* side, but is this enough intuitive? Another idea is using
"remote join", is this more appropriate for this kind of process? I
hesitate to use "remote join" because it implies client-server FDWs,
but foreign join is not limited to such FDWs, e.g. file_fdw can have
extra file which is already joined files accessed via foreign tables.

--
Shigeru HANADA