Hi All,
PFA patch to get data sorted from the foreign server (postgres_fdw)
according to the pathkeys useful for merge join.
For a given base relation (extendable to join when that becomes available
in postgres_fdw), the patch tries to find merge joinable clauses. It then
adds paths with pathkeys extracted out of these merge joinable clauses. The
merge joinable clauses form equivalence classes. The patch searches in
root->eq_classes for equivalence members belonging to the given relation.
For every such expression it creates a single member pathkey list and
corresponding path. The test postgres_fdw.sql has an existing join which
uses merge join. With this patch the data is sorted on the foreign server
than locally.
While mergejoinable clauses can be obtained from rel->joininfo as well. But
rel->joininfo contains other clauses as well and we need extra efforts to
remove duplicates if the same expression appears in multiple merge joinable
clauses.
Two joining relations can have multiple merge joinable clauses, requiring
multi-member pathkeys so that merge join is efficient to the maximum
extent. The order in which the expressions appears in pathkeys can change
the costs of sorting the data according to the pathkeys, depending upon the
expressions and the presence of indexes containing those expressions. Thus
ideally we would need to club all the expressions appearing in all the
clauses for given two relations and create paths with pathkeys for every
order of these expressions.That explodes the number of possible paths. We
may restrict the number of paths created by considering only certain orders
like sort_inner_and_outer(). In any case, costing such paths increases the
planning time which may not be worth it. So, this patch uses a heuristic
approach of creating single member pathkeys path for every merge joinable
expression.
The pathkeys need to be canonicalised using make_canonical_pathkey(), which
is a static function. I have added a TODO and comments in the patch
explaining possible ways to avoid "extern"alization of this function.
Comments/suggestions are welcome.
--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company
diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 0159bf5..ddb05f2 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -3383,22 +3383,22 @@ select tableoid::regclass, * from bar order by 1,2;
bar2 | 4 | 144
bar2 | 7 | 77
(6 rows)
-- Check UPDATE with inherited target and an appendrel subquery
explain (verbose, costs off)
update bar set f2 = f2 + 100
from
( select f1 from foo union all select f1+3 from foo ) ss
where bar.f1 = ss.f1;
- QUERY PLAN
---------------------------------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------------------------------------------
Update on public.bar
Update on public.bar
Foreign Update on public.bar2
Remote SQL: UPDATE public.loct2 SET f2 = $2 WHERE ctid = $1
-> Hash Join
Output: bar.f1, (bar.f2 + 100), bar.ctid, (ROW(foo.f1))
Hash Cond: (foo.f1 = bar.f1)
-> Append
-> Seq Scan on public.foo
Output: ROW(foo.f1), foo.f1
@@ -3410,41 +3410,44 @@ where bar.f1 = ss.f1;
-> Foreign Scan on public.foo2 foo2_1
Output: ROW((foo2_1.f1 + 3)), (foo2_1.f1 + 3)
Remote SQL: SELECT f1 FROM public.loct1
-> Hash
Output: bar.f1, bar.f2, bar.ctid
-> Seq Scan on public.bar
Output: bar.f1, bar.f2, bar.ctid
-> Merge Join
Output: bar2.f1, (bar2.f2 + 100), bar2.f3, bar2.ctid, (ROW(foo.f1))
Merge Cond: (bar2.f1 = foo.f1)
- -> Sort
+ -> Foreign Scan on public.bar2
Output: bar2.f1, bar2.f2, bar2.f3, bar2.ctid
- Sort Key: bar2.f1
- -> Foreign Scan on public.bar2
- Output: bar2.f1, bar2.f2, bar2.f3, bar2.ctid
- Remote SQL: SELECT f1, f2, f3, ctid FROM public.loct2 FOR UPDATE
- -> Sort
+ Remote SQL: SELECT f1, f2, f3, ctid FROM public.loct2 ORDER BY f1 ASC FOR UPDATE
+ -> Materialize
Output: (ROW(foo.f1)), foo.f1
- Sort Key: foo.f1
- -> Append
- -> Seq Scan on public.foo
- Output: ROW(foo.f1), foo.f1
+ -> Merge Append
+ Sort Key: foo.f1
+ -> Sort
+ Output: (ROW(foo.f1)), foo.f1
+ Sort Key: foo.f1
+ -> Seq Scan on public.foo
+ Output: ROW(foo.f1), foo.f1
-> Foreign Scan on public.foo2
Output: ROW(foo2.f1), foo2.f1
- Remote SQL: SELECT f1 FROM public.loct1
- -> Seq Scan on public.foo foo_1
- Output: ROW((foo_1.f1 + 3)), (foo_1.f1 + 3)
+ Remote SQL: SELECT f1 FROM public.loct1 ORDER BY f1 ASC
+ -> Sort
+ Output: (ROW((foo_1.f1 + 3))), ((foo_1.f1 + 3))
+ Sort Key: ((foo_1.f1 + 3))
+ -> Seq Scan on public.foo foo_1
+ Output: ROW((foo_1.f1 + 3)), (foo_1.f1 + 3)
-> Foreign Scan on public.foo2 foo2_1
Output: ROW((foo2_1.f1 + 3)), (foo2_1.f1 + 3)
- Remote SQL: SELECT f1 FROM public.loct1
-(45 rows)
+ Remote SQL: SELECT f1 FROM public.loct1 ORDER BY (f1 + 3) ASC
+(48 rows)
update bar set f2 = f2 + 100
from
( select f1 from foo union all select f1+3 from foo ) ss
where bar.f1 = ss.f1;
select tableoid::regclass, * from bar order by 1,2;
tableoid | f1 | f2
----------+----+-----
bar | 1 | 211
bar | 2 | 222
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index cd4ed0c..02d17d2 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -251,20 +251,21 @@ static void postgresExplainForeignScan(ForeignScanState *node,
static void postgresExplainForeignModify(ModifyTableState *mtstate,
ResultRelInfo *rinfo,
List *fdw_private,
int subplan_index,
ExplainState *es);
static bool postgresAnalyzeForeignTable(Relation relation,
AcquireSampleRowsFunc *func,
BlockNumber *totalpages);
static List *postgresImportForeignSchema(ImportForeignSchemaStmt *stmt,
Oid serverOid);
+static List *generate_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel);
/*
* Helper functions
*/
static void estimate_path_cost_size(PlannerInfo *root,
RelOptInfo *baserel,
List *join_conds,
List *pathkeys,
double *p_rows, int *p_width,
Cost *p_startup_cost, Cost *p_total_cost);
@@ -501,90 +502,223 @@ postgresGetForeignRelSize(PlannerInfo *root,
set_baserel_size_estimates(root, baserel);
/* Fill in basically-bogus cost estimates for use later. */
estimate_path_cost_size(root, baserel, NIL, NIL,
&fpinfo->rows, &fpinfo->width,
&fpinfo->startup_cost, &fpinfo->total_cost);
}
}
/*
- * postgresGetForeignPaths
- * Create possible scan paths for a scan on the foreign table
+ * generate_pathkeys_for_relation
+ * Function collects "interesting" pathkeys for given relation. The caller is
+ * possibily going to create paths with these pathkeys so as to get the data
+ * sorted according to the pathkeys.
+ * Following pathkeys are of interest here.
+ * 1. query pathkeys
+ * 2. pathkeys arising out of the equivalence classes
+ * Comments in the function explain these two in details.
+ *
+ * TODO: This function requires make_canonical_pathkey() to be "extern"alized.
+ * The function is required to get pathkey corresponding to a given equivalence
+ * class if there exists one already or create one otherwise. There are two ways
+ * we can avoid "extern"alization
+ * 1. Create a wrapper exerna function returning pathkey with inputs root and
+ * equivalence class. Having this function pathkeys.c would avoid
+ * "extern"alization of the function.
+ * 2. Move generate_pathkeys_for_relation() to pathkeys.c. Considering that this
+ * function is heuristically finding the "interesting" pathkeys, it may not
+ * be very useful in general, and thus can not be part of the core.
*/
-static void
-postgresGetForeignPaths(PlannerInfo *root,
- RelOptInfo *baserel,
- Oid foreigntableid)
+static List *
+generate_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel)
{
- PgFdwRelationInfo *fpinfo = (PgFdwRelationInfo *) baserel->fdw_private;
- ForeignPath *path;
- List *ppi_list;
- ListCell *lc;
- List *usable_pathkeys = NIL;
-
- /*
- * Create simplest ForeignScan path node and add it to baserel. This path
- * corresponds to SeqScan path of regular tables (though depending on what
- * baserestrict conditions we were able to send to remote, there might
- * actually be an indexscan happening there). We already did all the work
- * to estimate cost and size of this path.
- */
- path = create_foreignscan_path(root, baserel,
- fpinfo->rows,
- fpinfo->startup_cost,
- fpinfo->total_cost,
- NIL, /* no pathkeys */
- NULL, /* no outer rel either */
- NIL); /* no fdw_private list */
- add_path(baserel, (Path *) path);
+ List *usable_pklist = NIL; /* List of pathkeys to be returned */
+ List *usable_pathkeys = NIL; /* List of pathkey nodes gathered */
+ ListCell *lc;
+ bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
/*
* Determine whether we can potentially push query pathkeys to the remote
* side, avoiding a local sort.
*/
foreach(lc, root->query_pathkeys)
{
PathKey *pathkey = (PathKey *) lfirst(lc);
EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
Expr *em_expr;
/*
* is_foreign_expr would detect volatile expressions as well, but
* ec_has_volatile saves some cycles.
*/
if (!pathkey_ec->ec_has_volatile &&
- (em_expr = find_em_expr_for_rel(pathkey_ec, baserel)) &&
- is_foreign_expr(root, baserel, em_expr))
+ (em_expr = find_em_expr_for_rel(pathkey_ec, rel)) &&
+ is_foreign_expr(root, rel, em_expr))
usable_pathkeys = lappend(usable_pathkeys, pathkey);
else
{
/*
* The planner and executor don't have any clever strategy for
* taking data sorted by a prefix of the query's pathkeys and
* getting it to be sorted by all of those pathekeys. We'll just
* end up resorting the entire data set. So, unless we can push
* down all of the query pathkeys, forget it.
*/
list_free(usable_pathkeys);
usable_pathkeys = NIL;
break;
}
}
- /* Create a path with useful pathkeys, if we found one. */
- if (usable_pathkeys != NULL)
+ if (usable_pathkeys)
+ usable_pklist = list_make1(usable_pathkeys);
+
+ /*
+ * Check equivalence classes where this relation appears. Getting data
+ * ordered on corresponding expressions might help merge join. A join
+ * between two relations might have multiple merge joinable clauses and
+ * might require the data to be sorted on all the expressions involved. But
+ * we do not have knowledge about the indexes present on the foreign server.
+ * The cost of sorting data on multiple expressions can vary greatly based on
+ * the kind of expressions and their presence in an index. Hence for now, we
+ * create paths with single pathkey.
+ * Nothing to do if the relation does is not part of any equivalence class.
+ */
+ if (!rel->has_eclass_joins)
+ return usable_pklist;
+
+ foreach(lc, root->eq_classes)
+ {
+ EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc);
+ Expr *em_expr;
+ List *pathkeys;
+
+ /*
+ * Won't generate joinclauses if const, single-member or has
+ * volatile expression.
+ */
+ if (cur_ec->ec_has_const || cur_ec->ec_has_volatile ||
+ list_length(cur_ec->ec_members) <= 1)
+ continue;
+
+ /*
+ * Equivalence classes covering relations other than the current one
+ * are of interest here.
+ */
+ if (!is_child_rel &&
+ bms_subset_compare(rel->relids, cur_ec->ec_relids) != BMS_SUBSET1)
+ continue;
+
+ /*
+ * In case of child relation, we need to check that the
+ * equivalence class indicates a join to a relation other than
+ * parents, other children and itself (something similar to above).
+ * Otherwise we will end up creating useless paths. The code below is
+ * similar to generate_implied_equalities_for_column(), which might
+ * give a hint.
+ */
+ if (is_child_rel)
+ {
+ ListCell *lc_em;
+ Relids parent_relids = find_childrel_parents(root, rel);
+ bool has_other_rel_joins = false;
+ foreach(lc_em, cur_ec->ec_members)
+ {
+ EquivalenceMember *other_em = lfirst(lc_em);
+
+ /*
+ * Ignore equivalence members which correspond to children
+ * or same relation or to parent relations
+ */
+ if (other_em->em_is_child ||
+ bms_overlap(rel->relids, other_em->em_relids) ||
+ bms_overlap(parent_relids, other_em->em_relids))
+ continue;
+
+ /* Found one "other" relation */
+ has_other_rel_joins = true;
+ break;
+ }
+
+ /*
+ * If this child relation doesn't join with relations other than
+ * parents, other children or itself, no use getting data sorted.
+ */
+ if (!has_other_rel_joins)
+ continue;
+ }
+
+ /*
+ * If there exists an equivalence member which entirely belongs to
+ * the current relation and corresponding expression is pushable to
+ * the foreign server, create single element pathkeys for the same.
+ * This equivalence class might be part of pathkeys derived from
+ * root->query_pathkeys, but the respective paths might cost
+ * different. add_path will discard any inferior paths.
+ */
+ if ((em_expr = find_em_expr_for_rel(cur_ec, rel)) &&
+ is_foreign_expr(root, rel, em_expr))
+ {
+
+ pathkeys = list_make1(make_canonical_pathkey(root, cur_ec,
+ linitial_oid(cur_ec->ec_opfamilies),
+ BTLessStrategyNumber,
+ false));
+ usable_pklist = lappend(usable_pklist, pathkeys);
+ }
+ }
+
+ return usable_pklist;
+}
+
+/*
+ * postgresGetForeignPaths
+ * Create possible scan paths for a scan on the foreign table
+ */
+static void
+postgresGetForeignPaths(PlannerInfo *root,
+ RelOptInfo *baserel,
+ Oid foreigntableid)
+{
+ PgFdwRelationInfo *fpinfo = (PgFdwRelationInfo *) baserel->fdw_private;
+ ForeignPath *path;
+ List *ppi_list;
+ ListCell *lc;
+ List *usable_pklist = NIL; /* List of all pathkeys */
+
+ /*
+ * Create simplest ForeignScan path node and add it to baserel. This path
+ * corresponds to SeqScan path of regular tables (though depending on what
+ * baserestrict conditions we were able to send to remote, there might
+ * actually be an indexscan happening there). We already did all the work
+ * to estimate cost and size of this path.
+ */
+ path = create_foreignscan_path(root, baserel,
+ fpinfo->rows,
+ fpinfo->startup_cost,
+ fpinfo->total_cost,
+ NIL, /* no pathkeys */
+ NULL, /* no outer rel either */
+ NIL); /* no fdw_private list */
+ add_path(baserel, (Path *) path);
+
+ usable_pklist = generate_pathkeys_for_relation(root, baserel);
+
+ /* Create one path for each set of pathkeys we found above. */
+ foreach (lc, usable_pklist)
{
double rows;
int width;
Cost startup_cost;
Cost total_cost;
+ List *usable_pathkeys = lfirst(lc);
estimate_path_cost_size(root, baserel, NIL, usable_pathkeys,
&rows, &width, &startup_cost, &total_cost);
add_path(baserel, (Path *)
create_foreignscan_path(root, baserel,
rows,
startup_cost,
total_cost,
usable_pathkeys,
diff --git a/contrib/postgres_fdw/postgres_fdw.h b/contrib/postgres_fdw/postgres_fdw.h
index f243de8..d13a244 100644
--- a/contrib/postgres_fdw/postgres_fdw.h
+++ b/contrib/postgres_fdw/postgres_fdw.h
@@ -106,17 +106,17 @@ extern void deparseUpdateSql(StringInfo buf, PlannerInfo *root,
extern void deparseDeleteSql(StringInfo buf, PlannerInfo *root,
Index rtindex, Relation rel,
List *returningList,
List **retrieved_attrs);
extern void deparseAnalyzeSizeSql(StringInfo buf, Relation rel);
extern void deparseAnalyzeSql(StringInfo buf, Relation rel,
List **retrieved_attrs);
extern void deparseStringLiteral(StringInfo buf, const char *val);
extern Expr *find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel);
extern void appendOrderByClause(StringInfo buf, PlannerInfo *root,
- RelOptInfo *baserel, List *pathkeys);
+ RelOptInfo *baserel, List *pathkeys);
/* in shippable.c */
extern bool is_builtin(Oid objectId);
extern bool is_shippable(Oid objectId, Oid classId, PgFdwRelationInfo *fpinfo);
#endif /* POSTGRES_FDW_H */
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index c6b5d78..b81cc49 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -21,43 +21,40 @@
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/plannodes.h"
#include "optimizer/clauses.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/tlist.h"
#include "utils/lsyscache.h"
-static PathKey *make_canonical_pathkey(PlannerInfo *root,
- EquivalenceClass *eclass, Oid opfamily,
- int strategy, bool nulls_first);
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
/****************************************************************************
* PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
****************************************************************************/
/*
* make_canonical_pathkey
* Given the parameters for a PathKey, find any pre-existing matching
* pathkey in the query's list of "canonical" pathkeys. Make a new
* entry if there's not one already.
*
* Note that this function must not be used until after we have completed
* merging EquivalenceClasses. (We don't try to enforce that here; instead,
* equivclass.c will complain if a merge occurs after root->canon_pathkeys
* has become nonempty.)
*/
-static PathKey *
+PathKey *
make_canonical_pathkey(PlannerInfo *root,
EquivalenceClass *eclass, Oid opfamily,
int strategy, bool nulls_first)
{
PathKey *pk;
ListCell *lc;
MemoryContext oldcontext;
/* The passed eclass might be non-canonical, so chase up to the top */
while (eclass->ec_merged)
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 87123a5..5ef6e1a 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -197,12 +197,15 @@ extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root,
extern List *select_outer_pathkeys_for_merge(PlannerInfo *root,
List *mergeclauses,
RelOptInfo *joinrel);
extern List *make_inner_pathkeys_for_merge(PlannerInfo *root,
List *mergeclauses,
List *outer_pathkeys);
extern List *truncate_useless_pathkeys(PlannerInfo *root,
RelOptInfo *rel,
List *pathkeys);
extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern PathKey *make_canonical_pathkey(PlannerInfo *root,
+ EquivalenceClass *eclass, Oid opfamily,
+ int strategy, bool nulls_first);
#endif /* PATHS_H */
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
