Re: postgres_fdw join pushdown (was Re: Custom/Foreign-Join-APIs)

Hi All,
It's been a long time since last patch on this thread was posted. I have started
to work on supporting join pushdown for postgres_fdw. Attached please find three
patches
1. pg_fdw_core.patch: changes in core related to user mapping handling, GUC
                      enable_foreignjoin
2. pg_fdw_join.patch: postgres_fdw changes for supporting join pushdown
3. pg_join_pd.patch: patch which combines both of these for easy testing.

This mail describes the high level changes included in the patch.

GUC enable_foreignjoin
======================
Like enable_*join GUCs, this GUC when ON allows planner to consider pushing down
joins to the foreign server. If OFF, foreign join paths will not be considered.

Building joinrel for joins involving foreign relations
======================================================
RelOptInfo gets a new field umid for user mapping id used for the given foreign
relation. For base relations it's set to the user mapping of effective user and
foreign server for that relation. While building RelOptInfo for a join between
two foreign relations, if server and user mapping of joining relations are same,
they are copied to the RelOptInfo of the join relation being built. Also,
fdwroutine is set in joinrel to indicate that the core code considers this join
as pushable. It should suffice just to check equality of the user mapping oid
since same user mapping implies same server.

Since user mapping oid is available in RelOptInfo, FDWs can get user
mapping information by using this oid, new function GetUserMappingById()
facilitates that.

Generating paths
================
If fdwroutine is set in joinrel, add_paths_to_joinrel() calls
GetForeignJoinPaths hook of corresponding FDW. For postgres_fdw the hook is
implemented by function postgresGetForeignJoinPaths(). Follows the description
of this function.

In order to avoid considering same joinrel again, fdw_private member of
RelOptInfo is set by this function and populated with FDW specific information
about joinrel. When this member is set, it indicates that the pushable paths
have been considered for the given joinrel.

A join between two foreign relations is considered safe to push down if
1. The joining sides are pushable
2. The type of join is OUTER or INNER (LEFT/RIGHT/FULL/INNER). SEMI and ANTI
   joins are not considered right now, because of difficulties in constructing
   the queries involving those. The join clauses of SEMI/ANTI joins are not in a
   form that can be readily converted to IN/EXISTS/NOT EXIST kind of expression.
   We might consider this as future optimization.
3. Joining sides do not have clauses which can not be pushed down to the foreign
   server. For an OUTER join this is important since those clauses need to be
   applied before performing the join and thus join can not be pushed to the
   foreign server. An example is
   SELECT * FROM ft1 LEFT JOIN (SELECT * FROM ft2 where local_cond) ft2 ON (join clause)
   Here the local_cond on ft2 needs to be executed before performing LEFT JOIN
   between ft1 and ft2.
   This condition can be relaxed for an INNER join by pulling the local clauses
   up the join tree. But this needs more investigation and is not considered in
   this version.
4. The join conditions (e.g. conditions in ON clause) are all safe to push down.
   This is important for OUTER joins as pushing down join clauses partially and
   applying rest locally changes the result. There are ways [1] by which partial
   OUTER join can be completed by applying unpushable clauses locally and then
   nullifying the nullable side and eliminating duplicate non-nullable side
   rows. But that's again out of scope of first version of postgres_fdw join
   pushdown.

A ForeignPath is created for a safe-to-push-down join. Recursively applying this
procedure ends in having a single ForeignPath node for whole pushable join tree,
which may represent a join between more than two foreign tables.

Generating plan
===============
postgresGetForeignPlan() is used to create plan from path chosen by the
optimizer for both joins and base relation scans. This function constructs the SQL to
be sent to the remote node and create ForeignPlan node.

The function first separates given scan_clauses into pushable and safe-to-push
clauses. For joinrel baserestrictlist is NIL and we are not considering
parameterized paths, so there are no scan clauses expected. Next the function
constructs the SQL to be sent to the foreign server. Then it constructs the
ForeignScan node. Rest of this section describes the logic to construct the SQL
for join; the logic is implemented as function deparseSelectSqlForRel().

deparseSelectSqlForRel() builds the SQL for given joinrel (and now for baserel
asd well) recursively.
For joinrels
1. it constructs SQL representing either side of join, by calling itself
   in recursive fashion.
2. These SQLs are converted into subqueries and become part of the FROM clause
   with appropriate JOIN type and clauses. The left and right subqueries are
   given aliases "l" and "r" respectively. The columns in each subquery are
   aliased as "a1", "a2", "a3" and so on. Thus the third column on left side can
   be referenced as "l.a3" at any recursion level.
3. Targetlist is added representing the columns in the join result expected at
   that level.
4. The join clauses are added as part of ON clause
5. Any clauses that planner has deemed fit to be evaluated at that level of join
   are added as part of WHERE clause.

It uses the same old logic for deparsing SQL for base relations, except for the
deparsing the targetlist. When plan is being constructed only for a base
relation, the targetlist (SELECT clause) is constructed by including all the
columns by looking at attrs_used. This does not work when the base relation is
part of the join being pushed down, since the join targetlist depend upon the
targetlist in RelOptInfo of base relation and not necessarily the targetlist
obtained from attrs_used.

Row marks
---------
Because of recursive nature of SQL, the names of relations referenced in row
marks are not available at the top level in SQL built for a given top level join
relation. Hence we have to add FOR SHARE/UPDATE clauses to the subqueries built
for foreign base relations. This causes all the rows participating in join (not
the join result) from the base relations to get locked (on foreign server).
Ideally for a top level row mark clause, we should be locking only those rows
(on foreign server) which are part of the top level join result. But that
requires flattening of the FROM clause constructed, which would require some
signficant intelligence in the deparser code. I have left this out of scope for
at least this version of the patch.

Examples of remote SQL can be found in the expected output of regression test postgres_fdw.sql.

Foreign plan execution
======================
For pushed down joins, the tuple descriptor for the result is obtained from the
targetlist of the plan. Accordingly the error callback and result handling has
been modified.

Explain output for a pushed down join provides the join expression that it
represents.

TODOs
=====
This patch is very much WIP patch to show case the approach and invite early
comments. I will continue to improve the patch and some of the areas that will
be improved are
1. Costing of foreign join paths.
2. Various TODOs in the patch, making it more readable, finishing etc.
3. Tests
4. Any comments/suggestions on approach or the attached patch.

In another thread Robert, Fujita-san and Kaigai-san are discussing about
EvalPlanQual support for foreign joins. Corresponding changes to postgres_fdw
will need to be added once those changes get committed.

Items that will be considered in subsequent patches for 9.6
===========================================================
1. Parameterized paths for join: For regular joins, the parameterized paths for
   joins consider the parameterization of the joining paths. In case of foreign
   join, we do not consider any specific paths for the joining foreign
   relations and it acts as a scan. It should be treated as if parameterizing a
   scan and not like regular join. This requires some work and even without that
   the functionality supported by this patch is quite useful. So, I have left it
   out of the scope for this patch and will be considered in subsequent patch.

2. Foreign join paths with pathkeys: There's my patch pending for considering
   pathkeys for foreign base relation scan. The support for foreign join paths
   with pathkeys will added once that patch gets committed.


Suggestions/comments are welcome.
--