David,
I tried to implement your suggestions, here are the patches.
The first patch mostly moves some code around without changing
functionality. It modifies innerrel_is_unique to not only cache the fact
that the relation is unique, but also
cache the index that guarantees uniqueness.
The second patch adds the unique self join removal code. It goes along
the lines of your plan. I didn't even have to examine join clauses
because the constraints imposed by innerrel_is_unique are strong enough
to guarantee that when it finds the same unique index for both
relations, the join can be removed. Namely, it requires mergejoinable
equality clauses for all columns of a unique index.
As a simple benchmark, I measured the duration of query_planner and
remove_useless_self_joins with clock_gettime() on the regression tests.
The following table shows average times in microseconds, median over 11
runs. First row is with this patch, and the second row doesn't call
remove_useless_self_joins and just calls clock_gettime to measure its
overhead.
query_planner remove_useless_self_joins
with removal 39.61 0.61
no removal 39.45 0.38
So, on this workload, unique self join removal adds about 0.2 mcs, or
0.6% of total time, to query_planner. I also tried a query that joins 26
relations, remove_useless_self_joins takes about 40 mcs. Still, this
time grows quadratically with number of relations we have to process, so
in the final patch I limit it to join_collapse_limit, which brings the
time down to 15 mcs. This is negligible compared to the total
query_planner time, which for 8 relations is about 3 ms, that is, 3
orders of magnitude higher.
These benchmarks mostly measure the path where we don't remove any
joins. I didn't time the join removal itself, because it wins quite some
time by allowing to plan one relation and one join less.
--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
>From ad5f5b59265762b3674068ee3656baec3ec66b70 Mon Sep 17 00:00:00 2001
From: Alexander Kuzmenkov <a.kuzmen...@postgrespro.ru>
Date: Wed, 13 Jun 2018 21:45:32 +0300
Subject: [PATCH 2/2] Remove unique self joins.
---
src/backend/optimizer/plan/analyzejoins.c | 513 ++++++++++++++++++++++++++++++
src/backend/optimizer/plan/planmain.c | 5 +
src/include/optimizer/planmain.h | 1 +
src/test/regress/expected/join.out | 38 ++-
src/test/regress/sql/join.sql | 16 +
5 files changed, 569 insertions(+), 4 deletions(-)
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index c03010c..f593a17 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -22,12 +22,15 @@
*/
#include "postgres.h"
+#include "catalog/pg_class.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
+#include "optimizer/predtest.h"
+#include "optimizer/restrictinfo.h"
#include "optimizer/tlist.h"
#include "optimizer/var.h"
#include "utils/lsyscache.h"
@@ -1122,3 +1125,513 @@ is_innerrel_unique_for(PlannerInfo *root,
/* Let rel_is_distinct_for() do the hard work */
return rel_is_distinct_for(root, innerrel, clause_list, unique_index);
}
+
+static bool
+set_varno_walker(Node *node, void *context)
+{
+ if (node == NULL)
+ return false;
+
+ if (IsA(node, Var))
+ ((Var *) node)->varno = (Index) (intptr_t) context;
+
+ return expression_tree_walker(node, set_varno_walker, context);
+}
+
+/*
+ * Replace varno with 'relid' for all Vars in the expression.
+ */
+static void
+set_varno(Expr *expr, Index relid)
+{
+ set_varno_walker((Node *) expr, (void*) (intptr_t) relid);
+}
+
+static bool
+references_relation_walker(Node *node, void *context)
+{
+ if (node == NULL)
+ return false;
+
+ if (IsA(node, Var))
+ return ((Var *) node)->varno == (Index) (intptr_t) context;
+
+ return expression_tree_walker(node, references_relation_walker, context);
+}
+
+/*
+ * Check whether the expression has any Vars from the relation identified
+ * by 'relid'. For EquivalenceClass nodes, checks the equivalence members.
+ */
+static bool
+references_relation(Node *node, Index relid)
+{
+ if (IsA(node, EquivalenceClass))
+ {
+ EquivalenceClass *ec = (EquivalenceClass *) node;
+ ListCell *lc;
+ foreach (lc, ec->ec_members)
+ {
+ if (references_relation(
+ (Node *) ((EquivalenceMember *) lfirst(lc))->em_expr,
+ relid))
+ {
+ return true;
+ }
+ }
+ return false;
+ }
+ return references_relation_walker(node, (void *) (intptr_t) relid);
+}
+
+/*
+ * Substitute newId for oldId in relids.
+ */
+static void
+change_relid(Relids *relids, Index oldId, Index newId)
+{
+ if (bms_is_member(oldId, *relids))
+ *relids = bms_add_member(bms_del_member(*relids, oldId), newId);
+}
+
+/*
+ * Remove a relation after we have proven that it participates only in an
+ * unneeded unique self join.
+ *
+ * The joinclauses list is destructively changed.
+ */
+static void
+remove_self_join_rel(PlannerInfo *root, Relids joinrelids, List *joinclauses,
+ RelOptInfo *toKeep, RelOptInfo *toRemove)
+{
+ ListCell *prev, *cell, *next;
+ List *toAppend;
+
+ /*
+ * Join clauses become restriction clauses, when Vars of the relation we
+ * remove are replaced with corresponding Vars of the one we keep.
+ * Restriction clauses from the removed relation are as well transferred
+ * to the remaining one.
+ */
+ toAppend = list_concat(joinclauses, toRemove->baserestrictinfo);
+
+ /*
+ * Append the filters from the removed relation to the remaining one.
+ */
+ foreach(cell, toAppend)
+ {
+ RestrictInfo *oldRinfo = lfirst_node(RestrictInfo, cell);
+ RestrictInfo *newRinfo = NULL;
+ Expr *newClause = NULL;
+
+ /*
+ * Do not add multiple clauses derived from the same equivalence class.
+ */
+ if (is_redundant_derived_clause(oldRinfo, toKeep->baserestrictinfo))
+ continue;
+
+ /*
+ * Make a copy of the clause and replace the references to the removed
+ * relation with references to the remaining one.
+ */
+ newClause = (Expr *) copyObject(oldRinfo->clause);
+ set_varno(newClause, toKeep->relid);
+
+ /*
+ * After we have replaced the Vars, check that the resulting clause is
+ * not implied by the existing ones.
+ */
+ if (!contain_mutable_functions((Node *) newClause)
+ && predicate_implied_by(list_make1(newClause), toKeep->baserestrictinfo,
+ /* weak = */ false ))
+ continue; /* provably implied by r1 */
+
+ /*
+ * If the clause has the form of "X=X", replace it with null test.
+ */
+ if (oldRinfo->mergeopfamilies)
+ {
+ Assert(is_opclause(newClause));
+ Expr *leftOp = (Expr *) get_leftop(newClause);
+ Expr *rightOp = (Expr *) get_rightop(newClause);
+ if (leftOp != NULL && equal(leftOp, rightOp))
+ {
+ NullTest *test = makeNode(NullTest);
+ test->arg = leftOp;
+ test->nulltesttype = IS_NOT_NULL;
+ test->argisrow = false;
+ test->location = -1;
+ newClause = (Expr *) test;
+ }
+ }
+
+ /*
+ * Finally, correct the relids of the old rinfo, and replace the clause
+ * with the one we just constructed, and append it to the remaining
+ * relation.
+ */
+ newRinfo = copyObject(oldRinfo);
+ newRinfo->clause = newClause;
+ change_relid(&newRinfo->required_relids, toRemove->relid, toKeep->relid);
+ change_relid(&newRinfo->left_relids, toRemove->relid, toKeep->relid);
+ change_relid(&newRinfo->right_relids, toRemove->relid, toKeep->relid);
+ change_relid(&newRinfo->clause_relids, toRemove->relid, toKeep->relid);
+ toKeep->baserestrictinfo = lappend(toKeep->baserestrictinfo, newRinfo);
+ }
+
+ /*
+ * Remove the relation from the planner data structures.
+ */
+ remove_rel_from_query(root, toRemove->relid, joinrelids);
+
+ /*
+ * The equivalence classes that reference the removed rel can't also
+ * reference anything other than the remaining rel, or else this
+ * optimization wouldn't work (see rel_used_above_join).
+ *
+ * This means we don't have any ECs that can generate join clauses,
+ * and only have the ECs that can generate restrictions. But the restrictions
+ * have been generated already, and we've just transferred them to the
+ * remaining relation from join clauses and from the restrictions of the
+ * removed relation.
+ *
+ * Therefore, we don't need anymore the ECs that reference the removed
+ * relation, and can delete them.
+ */
+ prev = NULL;
+ cell = NULL;
+ next = list_head(root->eq_classes);
+ while (next)
+ {
+ prev = cell;
+ cell = next;
+ next = lnext(next);
+
+ if (references_relation(lfirst(cell), toRemove->relid))
+ {
+ root->eq_classes = list_delete_cell(root->eq_classes, cell, prev);
+ cell = prev;
+ }
+ }
+}
+
+/*
+ * Test whether the relations are joined on the same unique column.
+ */
+static bool
+is_unique_self_join(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer,
+ RelOptInfo *inner, List *restrictlist)
+{
+ IndexOptInfo *outeridx = NULL;
+ IndexOptInfo *inneridx = NULL;
+
+ innerrel_is_unique(root, joinrelids, inner->relids,
+ outer, JOIN_INNER, restrictlist, true, &outeridx);
+ if (!outeridx)
+ return false;
+
+ innerrel_is_unique(root, joinrelids, outer->relids,
+ inner, JOIN_INNER, restrictlist, true, &inneridx);
+ if (!inneridx)
+ return false;
+
+ /* We must have the same unique index for both relations. */
+ if (outeridx->indexoid != inneridx->indexoid)
+ return false;
+
+ /* A sanity check: this is the same index on the same relation. */
+ Assert(root->simple_rte_array[outer->relid]->relid
+ == root->simple_rte_array[inner->relid]->relid);
+
+ return true;
+}
+
+/*
+ * Scratch space for the unique self join removal code.
+ */
+typedef struct
+{
+ /* Temporary array for relation ids. */
+ Index *relids;
+
+ /*
+ * Array of Relids, one for each relation, indexed by relation id.
+ * Each element is a set of relation ids with which this relation
+ * has a special join.
+ */
+ Relids *special_join_rels;
+
+ /* Bitmapset for join relids that is used to avoid reallocation. */
+ Relids joinrelids;
+} UsjScratch;
+
+/*
+ * Find and remove unique self joins in a group of base relations that have
+ * the same Oid.
+ *
+ * Returns IntList of the relids that were removed.
+ */
+static List *
+remove_self_joins_one_group(PlannerInfo *root, Index *relids, int n, UsjScratch *scratch)
+{
+ Relids joinrelids = scratch->joinrelids;
+ List *result = NIL;
+ int i, o;
+
+ if (n < 2)
+ return NIL;
+
+ for (o = 0; o < n; o++)
+ {
+ RelOptInfo *outer;
+
+ if (relids[o] == 0)
+ /* Already removed. */
+ continue;
+
+ outer = root->simple_rel_array[relids[o]];
+ for (i = o + 1; i < n; i++)
+ {
+ RelOptInfo *inner;
+ List *restrictlist;
+
+ if (relids[i] == 0)
+ /* Already removed. */
+ continue;
+
+ inner = root->simple_rel_array[relids[i]];
+
+ /*
+ * Unique semi and left joins are processed by reduce_unique_semijoins
+ * and remove_useless_left_joins respectively, so we don't have to
+ * deal with them here. For full and anti joins, this optimization does
+ * not apply. Therefore, we do nothing if these relations have
+ * a special join.
+ */
+ if (bms_is_member(relids[i], scratch->special_join_rels[relids[o]]))
+ continue;
+
+ /* Reuse joinrelids bitset to avoid reallocation. */
+ joinrelids = bms_del_members(joinrelids, joinrelids);
+
+ /*
+ * We only deal with base rels here, so their relids bitset
+ * contains only one member -- their relid.
+ */
+ joinrelids = bms_add_member(joinrelids, relids[o]);
+ joinrelids = bms_add_member(joinrelids, relids[i]);
+
+ /* Is it a unique self join? */
+ restrictlist = build_joinrel_restrictlist(root, joinrelids, outer,
+ inner);
+ if (!is_unique_self_join(root, joinrelids, outer, inner,
+ restrictlist))
+ continue;
+
+ /* A relation can be removed if it is not referenced above the join. */
+ if (rel_used_above_join(root, joinrelids, inner))
+ {
+ if (rel_used_above_join(root, joinrelids, outer))
+ /*
+ * Both relations are referenced above the join, can't remove
+ * either one.
+ */
+ continue;
+ else
+ {
+ /* Remove outer. */
+ remove_self_join_rel(root, joinrelids, restrictlist,
+ inner, outer);
+ result = lappend_int(result, relids[o]);
+ relids[o] = 0;
+ break;
+ }
+ }
+ else
+ {
+ /* Remove inner. */
+ remove_self_join_rel(root, joinrelids, restrictlist,
+ outer, inner);
+ result = lappend_int(result, relids[i]);
+ relids[i] = 0;
+ }
+ }
+ }
+
+ scratch->joinrelids = joinrelids;
+ return result;
+}
+
+/*
+ * A qsort comparator to sort the relids by the relation Oid.
+ */
+static int
+compare_rte(const Index *left, const Index *right, PlannerInfo *root)
+{
+ return root->simple_rte_array[*left]->relid
+ < root->simple_rte_array[*right]->relid;
+}
+
+/*
+ * Find and remove unique self joins on a particular level of the join tree.
+ */
+static void
+remove_self_joins_one_level(PlannerInfo *root, List **joinlist, UsjScratch *scratch)
+{
+ ListCell *lc;
+ List *relidsToRemove = NIL;
+ Oid groupOid;
+ int groupStart;
+ int i;
+ int n = 0;
+ Index *relid_ascending = scratch->relids;
+
+ /*
+ * Collect the ids of base relations at this level of the join tree.
+ */
+ foreach (lc, *joinlist)
+ {
+ RangeTblRef *ref = (RangeTblRef *) lfirst(lc);
+ if (!IsA(ref, RangeTblRef))
+ continue;
+
+ /*
+ * We only care about base relations from which we select something.
+ */
+ if (root->simple_rte_array[ref->rtindex]->rtekind == RTE_RELATION
+ && root->simple_rte_array[ref->rtindex]->relkind == RELKIND_RELATION
+ && root->simple_rel_array[ref->rtindex] != NULL)
+ {
+ relid_ascending[n++] = ref->rtindex;
+ }
+
+ /*
+ * Limit the number of joins we process to control the quadratic behavior.
+ */
+ if (n > join_collapse_limit)
+ break;
+ }
+
+ if (n < 2)
+ return;
+
+ /*
+ * Find and process the groups of relations that have same Oid.
+ */
+ qsort_arg(relid_ascending, n, sizeof(*relid_ascending),
+ (qsort_arg_comparator) compare_rte, root);
+ groupOid = root->simple_rte_array[relid_ascending[0]]->relid;
+ groupStart = 0;
+ for (i = 1; i < n; i++)
+ {
+ RangeTblEntry *rte = root->simple_rte_array[relid_ascending[i]];
+ Assert(rte->relid != InvalidOid);
+ if (rte->relid != groupOid)
+ {
+ relidsToRemove = list_concat(relidsToRemove,
+ remove_self_joins_one_group(root, &relid_ascending[groupStart],
+ i - groupStart, scratch));
+ groupOid = rte->relid;
+ groupStart = i;
+ }
+ }
+ Assert(groupOid != InvalidOid);
+ Assert(groupStart < n);
+ relidsToRemove = list_concat(relidsToRemove,
+ remove_self_joins_one_group(root, &relid_ascending[groupStart],
+ n - groupStart, scratch));
+
+ /*
+ * Delete the removed relations from joinlist.
+ */
+ foreach(lc, relidsToRemove)
+ {
+ Index indexToRemove = lfirst_int(lc);
+ ListCell *prev = NULL, *next = NULL;
+ ListCell *lc2 = list_head(*joinlist);
+ while (lc2)
+ {
+ next = lnext(lc2);
+ if (castNode(RangeTblRef, lfirst(lc2))->rtindex == indexToRemove)
+ *joinlist = list_delete_cell(*joinlist, lc2, prev);
+ else
+ prev = lc2;
+ lc2 = next;
+ }
+ }
+
+ return;
+}
+
+/*
+ * Find and remove unique self joins on a single level of a join tree, and
+ * recurse to handle deeper levels.
+ */
+static void
+remove_self_joins_recurse(PlannerInfo *root, List **joinlist, UsjScratch *scratch)
+{
+ ListCell *lc;
+ foreach (lc, *joinlist)
+ {
+ switch (((Node*) lfirst(lc))->type)
+ {
+ case T_List:
+ remove_self_joins_recurse(root, (List **) &lfirst(lc), scratch);
+ break;
+ case T_RangeTblRef:
+ break;
+ default:
+ Assert(false);
+ }
+ }
+ remove_self_joins_one_level(root, joinlist, scratch);
+}
+
+/*
+ * Find out which relations have special joins to which.
+ */
+static void
+find_special_joins(PlannerInfo *root, Relids *special_join_rels)
+{
+ ListCell *lc;
+ foreach(lc, root->join_info_list)
+ {
+ SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);
+ int bit = -1;
+ while ((bit = bms_next_member(info->min_lefthand, bit)) >= 0)
+ {
+ RelOptInfo *rel = find_base_rel(root, bit);
+ special_join_rels[rel->relid] =
+ bms_add_members(special_join_rels[rel->relid], info->min_righthand);
+ }
+
+ bit = -1;
+ while ((bit = bms_next_member(info->min_righthand, bit)) >= 0)
+ {
+ RelOptInfo *rel = find_base_rel(root, bit);
+ special_join_rels[rel->relid] =
+ bms_add_members(special_join_rels[rel->relid], info->min_lefthand);
+ }
+ }
+}
+
+/*
+ * Find and remove unique self joins in the entire join tree.
+ *
+ * First, we cache some data that will be needed later.
+ * Then, for each jointree level, we group all the participating
+ * base relations by their relation Oid. For every pair of relations in a
+ * group, we try to remove the join they make.
+ */
+void
+remove_useless_self_joins(PlannerInfo *root, List **joinlist)
+{
+ UsjScratch scratch;
+
+ scratch.relids = palloc(root->simple_rel_array_size * sizeof(Index));
+ scratch.special_join_rels = palloc0(root->simple_rel_array_size * sizeof(Relids));
+ scratch.joinrelids = NULL;
+
+ find_special_joins(root, scratch.special_join_rels);
+ remove_self_joins_recurse(root, joinlist, &scratch);
+}
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 8e4abbe..12c3868 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -199,6 +199,11 @@ query_planner(PlannerInfo *root, List *tlist,
reduce_unique_semijoins(root);
/*
+ * Remove self joins on a unique column.
+ */
+ remove_useless_self_joins(root, &joinlist);
+
+ /*
* Now distribute "placeholders" to base rels as needed. This has to be
* done after join removal because removal could change whether a
* placeholder is evaluable at a base rel.
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 4805f74..501bb9a 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -111,6 +111,7 @@ extern bool innerrel_is_unique(PlannerInfo *root,
Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel,
JoinType jointype, List *restrictlist, bool force_cache,
IndexOptInfo **unique_index);
+extern void remove_useless_self_joins(PlannerInfo *root, List **jointree);
/*
* prototypes for plan/setrefs.c
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index dc6262b..05e9403 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4307,11 +4307,13 @@ explain (costs off)
select p.* from
(parent p left join child c on (p.k = c.k)) join parent x on p.k = x.k
where p.k = 1 and p.k = 2;
- QUERY PLAN
---------------------------
+ QUERY PLAN
+------------------------------------------------
Result
- One-Time Filter: false
-(2 rows)
+ One-Time Filter: (false AND false)
+ -> Index Scan using parent_pkey on parent p
+ Index Cond: (k = 1)
+(4 rows)
-- bug 5255: this is not optimizable by join removal
begin;
@@ -4427,6 +4429,34 @@ select * from
----+----+----+----
(0 rows)
+-- test that semi- or inner self-joins on a unique column are removed
+create table sj (a int unique, b int);
+insert into sj values (1, null), (null, 2), (2, 1);
+analyze sj;
+select p.* from sj p, sj q where q.a = p.a and q.b = q.a - 1;
+ a | b
+---+---
+ 2 | 1
+(1 row)
+
+explain (costs off)
+select p.* from sj p, sj q where q.a = p.a and q.b = q.a - 1;
+ QUERY PLAN
+-----------------------------------------------
+ Seq Scan on sj p
+ Filter: ((a IS NOT NULL) AND (b = (a - 1)))
+(2 rows)
+
+explain (costs off)
+select * from sj p
+where exists (select * from sj q
+ where q.a = p.a and q.b < 10);
+ QUERY PLAN
+------------------------------------------
+ Seq Scan on sj p
+ Filter: ((a IS NOT NULL) AND (b < 10))
+(2 rows)
+
--
-- Test hints given on incorrect column references are useful
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index d3ba2a1..7620981 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1527,6 +1527,22 @@ select * from
select * from
int8_tbl x join (int4_tbl x cross join int4_tbl y(ff)) j on q1 = f1; -- ok
+-- test that semi- or inner self-joins on a unique column are removed
+
+create table sj (a int unique, b int);
+insert into sj values (1, null), (null, 2), (2, 1);
+analyze sj;
+
+select p.* from sj p, sj q where q.a = p.a and q.b = q.a - 1;
+
+explain (costs off)
+select p.* from sj p, sj q where q.a = p.a and q.b = q.a - 1;
+
+explain (costs off)
+select * from sj p
+where exists (select * from sj q
+ where q.a = p.a and q.b < 10);
+
--
-- Test hints given on incorrect column references are useful
--
--
2.7.4
>From 73779316a164bee22c301c5e4d518d4afb92066e Mon Sep 17 00:00:00 2001
From: Alexander Kuzmenkov <a.kuzmen...@postgrespro.ru>
Date: Wed, 13 Jun 2018 20:56:03 +0300
Subject: [PATCH 1/2] Preparatory refactoring
---
src/backend/nodes/equalfuncs.c | 7 +-
src/backend/optimizer/path/indxpath.c | 16 +-
src/backend/optimizer/path/joinpath.c | 6 +-
src/backend/optimizer/plan/analyzejoins.c | 233 +++++++++++++++---------------
src/backend/optimizer/plan/planmain.c | 2 +-
src/backend/optimizer/util/pathnode.c | 2 +-
src/backend/optimizer/util/relnode.c | 26 ++--
src/include/nodes/relation.h | 6 +-
src/include/optimizer/pathnode.h | 5 +
src/include/optimizer/paths.h | 2 +-
src/include/optimizer/planmain.h | 5 +-
11 files changed, 157 insertions(+), 153 deletions(-)
diff --git a/src/backend/nodes/equalfuncs.c b/src/backend/nodes/equalfuncs.c
index 6a971d0..fd02dc8 100644
--- a/src/backend/nodes/equalfuncs.c
+++ b/src/backend/nodes/equalfuncs.c
@@ -166,9 +166,10 @@ _equalVar(const Var *a, const Var *b)
COMPARE_SCALAR_FIELD(vartypmod);
COMPARE_SCALAR_FIELD(varcollid);
COMPARE_SCALAR_FIELD(varlevelsup);
- COMPARE_SCALAR_FIELD(varnoold);
- COMPARE_SCALAR_FIELD(varoattno);
- COMPARE_LOCATION_FIELD(location);
+ /*
+ * Parse location and old varno/varattno may differ even when
+ * the variables are logically the same.
+ */
return true;
}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index f295558..78b05f1 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -2961,10 +2961,10 @@ ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
}
/*
- * relation_has_unique_index_for
+ * relation_get_unique_index_for
* Determine whether the relation provably has at most one row satisfying
* a set of equality conditions, because the conditions constrain all
- * columns of some unique index.
+ * columns of some unique index, and return that index.
*
* The conditions can be represented in either or both of two ways:
* 1. A list of RestrictInfo nodes, where the caller has already determined
@@ -2982,8 +2982,8 @@ ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
* this routine automatically adds in any usable baserestrictinfo clauses.
* (Note that the passed-in restrictlist will be destructively modified!)
*/
-bool
-relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
+IndexOptInfo *
+relation_get_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
List *restrictlist,
List *exprlist, List *oprlist)
{
@@ -2993,7 +2993,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
/* Short-circuit if no indexes... */
if (rel->indexlist == NIL)
- return false;
+ return NULL;
/*
* Examine the rel's restriction clauses for usable var = const clauses
@@ -3034,7 +3034,7 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
/* Short-circuit the easy case */
if (restrictlist == NIL && exprlist == NIL)
- return false;
+ return NULL;
/* Examine each index of the relation ... */
foreach(ic, rel->indexlist)
@@ -3131,10 +3131,10 @@ relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
/* Matched all columns of this index? */
if (c == ind->ncolumns)
- return true;
+ return ind;
}
- return false;
+ return NULL;
}
/*
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 642f951..0c11761 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -176,7 +176,8 @@ add_paths_to_joinrel(PlannerInfo *root,
innerrel,
JOIN_INNER,
restrictlist,
- false);
+ false,
+ NULL /*unique_index*/);
break;
default:
extra.inner_unique = innerrel_is_unique(root,
@@ -185,7 +186,8 @@ add_paths_to_joinrel(PlannerInfo *root,
innerrel,
jointype,
restrictlist,
- false);
+ false,
+ NULL /*unique_index*/);
break;
}
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 0e73f9c..c03010c 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -39,14 +39,15 @@ static void remove_rel_from_query(PlannerInfo *root, int relid,
static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
- List *clause_list);
+ List *clause_list, IndexOptInfo **unique_index);
static Oid distinct_col_search(int colno, List *colnos, List *opids);
static bool is_innerrel_unique_for(PlannerInfo *root,
Relids joinrelids,
Relids outerrelids,
RelOptInfo *innerrel,
JoinType jointype,
- List *restrictlist);
+ List *restrictlist,
+ IndexOptInfo **unique_index);
/*
@@ -58,7 +59,7 @@ static bool is_innerrel_unique_for(PlannerInfo *root,
* data structures that have to be updated are accessible via "root".
*/
List *
-remove_useless_joins(PlannerInfo *root, List *joinlist)
+remove_useless_left_joins(PlannerInfo *root, List *joinlist)
{
ListCell *lc;
@@ -146,55 +147,17 @@ clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids,
}
/*
- * join_is_removable
- * Check whether we need not perform this special join at all, because
- * it will just duplicate its left input.
- *
- * This is true for a left join for which the join condition cannot match
- * more than one inner-side row. (There are other possibly interesting
- * cases, but we don't have the infrastructure to prove them.) We also
- * have to check that the inner side doesn't generate any variables needed
- * above the join.
+ * Check whether any attributes of the relation are used above the
+ * join specified by joinrelids.
*/
static bool
-join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
+rel_used_above_join(PlannerInfo *root, Relids joinrelids, RelOptInfo *rel)
{
- int innerrelid;
- RelOptInfo *innerrel;
- Relids joinrelids;
- List *clause_list = NIL;
ListCell *l;
int attroff;
/*
- * Must be a non-delaying left join to a single baserel, else we aren't
- * going to be able to do anything with it.
- */
- if (sjinfo->jointype != JOIN_LEFT ||
- sjinfo->delay_upper_joins)
- return false;
-
- if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
- return false;
-
- innerrel = find_base_rel(root, innerrelid);
-
- /*
- * Before we go to the effort of checking whether any innerrel variables
- * are needed above the join, make a quick check to eliminate cases in
- * which we will surely be unable to prove uniqueness of the innerrel.
- */
- if (!rel_supports_distinctness(root, innerrel))
- return false;
-
- /* Compute the relid set for the join we are considering */
- joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
-
- /*
- * We can't remove the join if any inner-rel attributes are used above the
- * join.
- *
- * Note that this test only detects use of inner-rel attributes in higher
+ * This test only detects use of inner-rel attributes in higher
* join conditions and the target list. There might be such attributes in
* pushed-down conditions at this join, too. We check that case below.
*
@@ -203,101 +166,112 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
* theory that the system attributes are somewhat less likely to be wanted
* and should be tested last.
*/
- for (attroff = innerrel->max_attr - innerrel->min_attr;
+ for (attroff = rel->max_attr - rel->min_attr;
attroff >= 0;
attroff--)
{
- if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids))
- return false;
+ if (!bms_is_subset(rel->attr_needed[attroff], joinrelids))
+ return true;
}
/*
- * Similarly check that the inner rel isn't needed by any PlaceHolderVars
+ * Similarly check that the relation isn't needed by any PlaceHolderVars
* that will be used above the join. We only need to fail if such a PHV
- * actually references some inner-rel attributes; but the correct check
+ * actually references some relation attributes; but the correct check
* for that is relatively expensive, so we first check against ph_eval_at,
- * which must mention the inner rel if the PHV uses any inner-rel attrs as
+ * which must mention the relation if the PHV uses any relation attrs as
* non-lateral references. Note that if the PHV's syntactic scope is just
- * the inner rel, we can't drop the rel even if the PHV is variable-free.
+ * the given relation, we can't drop the rel even if the PHV is variable-free.
*/
foreach(l, root->placeholder_list)
{
PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
- if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
- return false; /* it references innerrel laterally */
+ if (bms_overlap(phinfo->ph_lateral, rel->relids))
+ return true; /* it references this relation laterally */
if (bms_is_subset(phinfo->ph_needed, joinrelids))
continue; /* PHV is not used above the join */
- if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
- continue; /* it definitely doesn't reference innerrel */
- if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids))
- return false; /* there isn't any other place to eval PHV */
+ if (!bms_overlap(phinfo->ph_eval_at, rel->relids))
+ continue; /* it definitely doesn't reference this relation */
+ if (bms_is_subset(phinfo->ph_eval_at, rel->relids))
+ return true; /* there isn't any other place to eval PHV */
if (bms_overlap(pull_varnos((Node *) phinfo->ph_var->phexpr),
- innerrel->relids))
- return false; /* it does reference innerrel */
+ rel->relids))
+ return true; /* it does reference this relation */
}
/*
- * Search for mergejoinable clauses that constrain the inner rel against
- * either the outer rel or a pseudoconstant. If an operator is
- * mergejoinable then it behaves like equality for some btree opclass, so
- * it's what we want. The mergejoinability test also eliminates clauses
- * containing volatile functions, which we couldn't depend on.
+ * Check for pushed-down clauses referencing the inner rel. If there is
+ * such a clause then join removal has to be disallowed. We have to
+ * check this despite the previous attr_needed checks because of the
+ * possibility of pushed-down clauses referencing the rel.
*/
- foreach(l, innerrel->joininfo)
+ foreach(l, rel->joininfo)
{
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
+ if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids)
+ && bms_is_member(rel->relid, restrictinfo->clause_relids))
+ return true;
+ }
- /*
- * If it's not a join clause for this outer join, we can't use it.
- * Note that if the clause is pushed-down, then it is logically from
- * above the outer join, even if it references no other rels (it might
- * be from WHERE, for example).
- */
- if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
- {
- /*
- * If such a clause actually references the inner rel then join
- * removal has to be disallowed. We have to check this despite
- * the previous attr_needed checks because of the possibility of
- * pushed-down clauses referencing the rel.
- */
- if (bms_is_member(innerrelid, restrictinfo->clause_relids))
- return false;
- continue; /* else, ignore; not useful here */
- }
+ return false;
+}
- /* Ignore if it's not a mergejoinable clause */
- if (!restrictinfo->can_join ||
- restrictinfo->mergeopfamilies == NIL)
- continue; /* not mergejoinable */
- /*
- * Check if clause has the form "outer op inner" or "inner op outer",
- * and if so mark which side is inner.
- */
- if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
- innerrel->relids))
- continue; /* no good for these input relations */
+/*
+ * join_is_removable
+ * Check whether we need not perform this special join at all, because
+ * it will just duplicate its left input.
+ *
+ * This is true for a left join for which the join condition cannot match
+ * more than one inner-side row. (There are other possibly interesting
+ * cases, but we don't have the infrastructure to prove them.) We also
+ * have to check that the inner side doesn't generate any variables needed
+ * above the join.
+ */
+static bool
+join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
+{
+ int innerrelid;
+ RelOptInfo *innerrel;
+ Relids joinrelids;
- /* OK, add to list */
- clause_list = lappend(clause_list, restrictinfo);
- }
+ /*
+ * Must be a non-delaying left join to a single baserel, else we aren't
+ * going to be able to do anything with it.
+ */
+ if (sjinfo->jointype != JOIN_LEFT ||
+ sjinfo->delay_upper_joins)
+ return false;
+
+ if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
+ return false;
+
+ innerrel = find_base_rel(root, innerrelid);
/*
- * Now that we have the relevant equality join clauses, try to prove the
- * innerrel distinct.
+ * Before we go to the effort of checking whether any innerrel variables
+ * are needed above the join, make a quick check to eliminate cases in
+ * which we will surely be unable to prove uniqueness of the innerrel.
*/
- if (rel_is_distinct_for(root, innerrel, clause_list))
- return true;
+ if (!rel_supports_distinctness(root, innerrel))
+ return false;
+
+ /* Compute the relid set for the join we are considering */
+ joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
/*
- * Some day it would be nice to check for other methods of establishing
- * distinctness.
+ * We can't remove the join if any inner-rel attributes are used above the
+ * join.
*/
- return false;
-}
+ if (rel_used_above_join(root, joinrelids, innerrel))
+ return false;
+
+ return is_innerrel_unique_for(root, joinrelids, sjinfo->min_lefthand,
+ innerrel, sjinfo->jointype, innerrel->joininfo,
+ NULL /*unique_index*/);
+}
/*
* Remove the target relid from the planner's data structures, having
@@ -568,7 +542,7 @@ reduce_unique_semijoins(PlannerInfo *root)
/* Test whether the innerrel is unique for those clauses. */
if (!innerrel_is_unique(root,
joinrelids, sjinfo->min_lefthand, innerrel,
- JOIN_SEMI, restrictlist, true))
+ JOIN_SEMI, restrictlist, true, NULL /*unique_index*/))
continue;
/* OK, remove the SpecialJoinInfo from the list. */
@@ -601,7 +575,7 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
* reference to unique indexes. Make sure there's at least one
* suitable unique index. It must be immediately enforced, and if
* it's a partial index, it must match the query. (Keep these
- * conditions in sync with relation_has_unique_index_for!)
+ * conditions in sync with relation_get_unique_index_for!)
*/
ListCell *lc;
@@ -643,9 +617,13 @@ rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
* Note that the passed-in clause_list may be destructively modified! This
* is OK for current uses, because the clause_list is built by the caller for
* the sole purpose of passing to this function.
+ *
+ * If unique_index is not null, it is set to point to the index that guarantees
+ * uniqueness for a base relation.
*/
static bool
-rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
+rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
+ IndexOptInfo **unique_index)
{
/*
* We could skip a couple of tests here if we assume all callers checked
@@ -658,11 +636,14 @@ rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
{
/*
* Examine the indexes to see if we have a matching unique index.
- * relation_has_unique_index_for automatically adds any usable
+ * relation_get_unique_index_for automatically adds any usable
* restriction clauses for the rel, so we needn't do that here.
*/
- if (relation_has_unique_index_for(root, rel, clause_list, NIL, NIL))
- return true;
+ IndexOptInfo *index = relation_get_unique_index_for(root, rel, clause_list,
+ NIL, NIL);
+ if (unique_index)
+ *unique_index = index;
+ return index != NULL;
}
else if (rel->rtekind == RTE_SUBQUERY)
{
@@ -966,6 +947,9 @@ distinct_col_search(int colno, List *colnos, List *opids)
* heuristic about whether to cache negative answers; it should be "true"
* if making an inquiry that is not part of the normal bottom-up join search
* sequence.
+ *
+ * If unique_index_out is not null, it is set to point to the index that
+ * guarantees uniqueness of a base relation.
*/
bool
innerrel_is_unique(PlannerInfo *root,
@@ -974,10 +958,15 @@ innerrel_is_unique(PlannerInfo *root,
RelOptInfo *innerrel,
JoinType jointype,
List *restrictlist,
- bool force_cache)
+ bool force_cache,
+ IndexOptInfo **unique_index_out)
{
MemoryContext old_context;
ListCell *lc;
+ IndexOptInfo *unique_index = NULL;
+
+ if (unique_index_out)
+ *unique_index_out = NULL;
/* Certainly can't prove uniqueness when there are no joinclauses */
if (restrictlist == NIL)
@@ -999,10 +988,14 @@ innerrel_is_unique(PlannerInfo *root,
*/
foreach(lc, innerrel->unique_for_rels)
{
- Relids unique_for_rels = (Relids) lfirst(lc);
+ Relids unique_for_rels = (Relids) linitial(lfirst(lc));
if (bms_is_subset(unique_for_rels, outerrelids))
+ {
+ if (unique_index_out)
+ *unique_index_out = lsecond(lfirst(lc));
return true; /* Success! */
+ }
}
/*
@@ -1019,7 +1012,7 @@ innerrel_is_unique(PlannerInfo *root,
/* No cached information, so try to make the proof. */
if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
- jointype, restrictlist))
+ jointype, restrictlist, &unique_index))
{
/*
* Cache the positive result for future probes, being sure to keep it
@@ -1033,9 +1026,12 @@ innerrel_is_unique(PlannerInfo *root,
*/
old_context = MemoryContextSwitchTo(root->planner_cxt);
innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
- bms_copy(outerrelids));
+ list_make2(bms_copy(outerrelids), unique_index));
MemoryContextSwitchTo(old_context);
+ if (unique_index_out)
+ *unique_index_out = unique_index;
+
return true; /* Success! */
}
else
@@ -1081,7 +1077,8 @@ is_innerrel_unique_for(PlannerInfo *root,
Relids outerrelids,
RelOptInfo *innerrel,
JoinType jointype,
- List *restrictlist)
+ List *restrictlist,
+ IndexOptInfo **unique_index)
{
List *clause_list = NIL;
ListCell *lc;
@@ -1123,5 +1120,5 @@ is_innerrel_unique_for(PlannerInfo *root,
}
/* Let rel_is_distinct_for() do the hard work */
- return rel_is_distinct_for(root, innerrel, clause_list);
+ return rel_is_distinct_for(root, innerrel, clause_list, unique_index);
}
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 7a34abc..8e4abbe 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -190,7 +190,7 @@ query_planner(PlannerInfo *root, List *tlist,
* jointree preprocessing, but the necessary information isn't available
* until we've built baserel data structures and classified qual clauses.
*/
- joinlist = remove_useless_joins(root, joinlist);
+ joinlist = remove_useless_left_joins(root, joinlist);
/*
* Also, reduce any semijoins with unique inner rels to plain inner joins.
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index dbf9adc..e0abc2c 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1583,7 +1583,7 @@ create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
* clauses for the rel, as well.
*/
if (rel->rtekind == RTE_RELATION && sjinfo->semi_can_btree &&
- relation_has_unique_index_for(root, rel, NIL,
+ relation_get_unique_index_for(root, rel, NIL,
sjinfo->semi_rhs_exprs,
sjinfo->semi_operators))
{
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 82b7842..845bb93 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -38,14 +38,10 @@ typedef struct JoinHashEntry
static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *input_rel);
-static List *build_joinrel_restrictlist(PlannerInfo *root,
- RelOptInfo *joinrel,
- RelOptInfo *outer_rel,
- RelOptInfo *inner_rel);
static void build_joinrel_joinlist(RelOptInfo *joinrel,
RelOptInfo *outer_rel,
RelOptInfo *inner_rel);
-static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
+static List *subbuild_joinrel_restrictlist(Relids joinrelids,
List *joininfo_list,
List *new_restrictlist);
static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
@@ -505,7 +501,7 @@ build_join_rel(PlannerInfo *root,
*/
if (restrictlist_ptr)
*restrictlist_ptr = build_joinrel_restrictlist(root,
- joinrel,
+ joinrel->relids,
outer_rel,
inner_rel);
return joinrel;
@@ -607,7 +603,7 @@ build_join_rel(PlannerInfo *root,
* caller might or might not need the restrictlist, but I need it anyway
* for set_joinrel_size_estimates().)
*/
- restrictlist = build_joinrel_restrictlist(root, joinrel,
+ restrictlist = build_joinrel_restrictlist(root, joinrel->relids,
outer_rel, inner_rel);
if (restrictlist_ptr)
*restrictlist_ptr = restrictlist;
@@ -964,7 +960,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
* the various joinlist entries ultimately refer to RestrictInfos
* pushed into them by distribute_restrictinfo_to_rels().
*
- * 'joinrel' is a join relation node
+ * 'joinrelids' is a join relation id set
* 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
* to form joinrel.
*
@@ -977,9 +973,9 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
* RestrictInfo nodes are no longer context-dependent. Instead, just include
* the original nodes in the lists made for the join relation.
*/
-static List *
+List *
build_joinrel_restrictlist(PlannerInfo *root,
- RelOptInfo *joinrel,
+ Relids joinrelids,
RelOptInfo *outer_rel,
RelOptInfo *inner_rel)
{
@@ -990,8 +986,8 @@ build_joinrel_restrictlist(PlannerInfo *root,
* eliminating any duplicates (important since we will see many of the
* same clauses arriving from both input relations).
*/
- result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
- result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result);
+ result = subbuild_joinrel_restrictlist(joinrelids, outer_rel->joininfo, NIL);
+ result = subbuild_joinrel_restrictlist(joinrelids, inner_rel->joininfo, result);
/*
* Add on any clauses derived from EquivalenceClasses. These cannot be
@@ -1000,7 +996,7 @@ build_joinrel_restrictlist(PlannerInfo *root,
*/
result = list_concat(result,
generate_join_implied_equalities(root,
- joinrel->relids,
+ joinrelids,
outer_rel->relids,
inner_rel));
@@ -1026,7 +1022,7 @@ build_joinrel_joinlist(RelOptInfo *joinrel,
}
static List *
-subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
+subbuild_joinrel_restrictlist(Relids joinrelids,
List *joininfo_list,
List *new_restrictlist)
{
@@ -1036,7 +1032,7 @@ subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
- if (bms_is_subset(rinfo->required_relids, joinrel->relids))
+ if (bms_is_subset(rinfo->required_relids, joinrelids))
{
/*
* This clause becomes a restriction clause for the joinrel, since
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 5af4840..362ae10 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -505,8 +505,10 @@ typedef struct PartitionSchemeData *PartitionScheme;
* populate these fields, for base rels; but someday they might be used for
* join rels too:
*
- * unique_for_rels - list of Relid sets, each one being a set of other
- * rels for which this one has been proven unique
+ * unique_for_rels - list of (Relids, IndexOptInfo*) lists, where Relids
+ * is a set of other rels for which this one has been proven
+ * unique, and IndexOptInfo* is an index that makes it unique,
+ * if any.
* non_unique_for_rels - list of Relid sets, each one being a set of
* other rels for which we have tried and failed to prove
* this one unique
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index e99ae36..da1cc30 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -271,6 +271,11 @@ extern RelOptInfo *build_join_rel(PlannerInfo *root,
RelOptInfo *inner_rel,
SpecialJoinInfo *sjinfo,
List **restrictlist_ptr);
+
+extern List *build_joinrel_restrictlist(PlannerInfo *root,
+ Relids joinrelids,
+ RelOptInfo *outer_rel,
+ RelOptInfo *inner_rel);
extern Relids min_join_parameterization(PlannerInfo *root,
Relids joinrelids,
RelOptInfo *outer_rel,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index cafde30..57ee855 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -71,7 +71,7 @@ extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel);
* routines to generate index paths
*/
extern void create_index_paths(PlannerInfo *root, RelOptInfo *rel);
-extern bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
+extern IndexOptInfo *relation_get_unique_index_for(PlannerInfo *root, RelOptInfo *rel,
List *restrictlist,
List *exprlist, List *oprlist);
extern bool indexcol_is_bool_constant_for_query(IndexOptInfo *index,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index c8ab028..4805f74 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -103,13 +103,14 @@ extern void match_foreign_keys_to_quals(PlannerInfo *root);
/*
* prototypes for plan/analyzejoins.c
*/
-extern List *remove_useless_joins(PlannerInfo *root, List *joinlist);
+extern List *remove_useless_left_joins(PlannerInfo *root, List *joinlist);
extern void reduce_unique_semijoins(PlannerInfo *root);
extern bool query_supports_distinctness(Query *query);
extern bool query_is_distinct_for(Query *query, List *colnos, List *opids);
extern bool innerrel_is_unique(PlannerInfo *root,
Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel,
- JoinType jointype, List *restrictlist, bool force_cache);
+ JoinType jointype, List *restrictlist, bool force_cache,
+ IndexOptInfo **unique_index);
/*
* prototypes for plan/setrefs.c
--
2.7.4
