Index: src/include/nodes/relation.h
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/include/nodes/relation.h,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 relation.h
--- src/include/nodes/relation.h 16 Jul 2009 20:55:44 -0000 1.1.1.1
+++ src/include/nodes/relation.h 8 Aug 2009 00:23:31 -0000
@@ -386,6 +386,14 @@
* list just to avoid recomputing the best inner indexscan repeatedly for
* similar outer relations. See comments for InnerIndexscanInfo.
*/
+
+ /*
+ * information used during the planning of hierarchical joins
+ * (set only when using pushing the join down to the children!)
+ */
+ bool has_children; /* are there any inheritance relations */
+ List *children_rels; /* inheritance relations */
+ List *constraints; /* inheritance constraints */
} RelOptInfo;
/*
Index: src/backend/utils/misc/Makefile
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/utils/misc/Makefile,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 Makefile
--- src/backend/utils/misc/Makefile 19 Feb 2008 10:30:09 -0000 1.1.1.1
+++ src/backend/utils/misc/Makefile 8 Aug 2009 00:23:30 -0000
@@ -14,7 +14,7 @@
override CPPFLAGS := -I$(srcdir) $(CPPFLAGS)
-OBJS = guc.o help_config.o pg_rusage.o ps_status.o superuser.o tzparser.o
+OBJS = guc.o help_config.o intervaltree.o pg_rusage.o ps_status.o superuser.o tzparser.o
# This location might depend on the installation directories. Therefore
# we can't subsitute it into pg_config.h.
Index: src/backend/utils/misc/postgresql.conf.sample
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/utils/misc/postgresql.conf.sample,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 postgresql.conf.sample
--- src/backend/utils/misc/postgresql.conf.sample 4 Aug 2009 16:08:36 -0000 1.1.1.1
+++ src/backend/utils/misc/postgresql.conf.sample 8 Aug 2009 00:23:31 -0000
@@ -219,6 +219,7 @@
#default_statistics_target = 100 # range 1-10000
#constraint_exclusion = partition # on, off, or partition
+#join_inheritance = off # on or off
#cursor_tuple_fraction = 0.1 # range 0.0-1.0
#from_collapse_limit = 8
#join_collapse_limit = 8 # 1 disables collapsing of explicit
Index: src/backend/utils/misc/guc.c
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/utils/misc/guc.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 guc.c
--- src/backend/utils/misc/guc.c 4 Aug 2009 16:08:36 -0000 1.1.1.1
+++ src/backend/utils/misc/guc.c 8 Aug 2009 00:23:31 -0000
@@ -663,6 +663,16 @@
true, NULL, NULL
},
{
+ {"join_inheritance", PGC_USERSET, QUERY_TUNING_OTHER,
+ gettext_noop("Enables the planner to push a join to the children of tables."),
+ gettext_noop("This algorithm pushes the join between the children"
+ "of the two relations instead of making append of"
+ "the children and performing the join.")
+ },
+ &join_inheritance,
+ false, NULL, NULL
+ },
+ {
{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Enables genetic query optimization."),
gettext_noop("This algorithm attempts to do planning without "
Index: src/backend/utils/cache/lsyscache.c
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/utils/cache/lsyscache.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 lsyscache.c
--- src/backend/utils/cache/lsyscache.c 11 Jun 2009 14:49:05 -0000 1.1.1.1
+++ src/backend/utils/cache/lsyscache.c 8 Aug 2009 00:23:30 -0000
@@ -80,6 +80,80 @@
return result;
}
+
+/*
+ * get_op_optypes_strategy
+ *
+ * Get the operator's strategy number given the data types
+ * of the left are right operands. Returns 0 if not found.
+ */
+int
+get_op_optypes_strategy(Oid opno, Oid lefttype, Oid righttype)
+{
+ StrategyNumber op_strategy = 0;
+ CatCList *catlist;
+ bool op_negated;
+ int i;
+
+ /*
+ * Find all the pg_amop entries containing the operator.
+ */
+ catlist = SearchSysCacheList(AMOPOPID, 1,
+ ObjectIdGetDatum(opno),
+ 0, 0, 0);
+
+ /*
+ * If we can't find any opfamily containing the op, perhaps it is a <>
+ * operator. See if it has a negator that is in an opfamily.
+ */
+ op_negated = false;
+ if (catlist->n_members == 0)
+ {
+ Oid op_negator = get_negator(opno);
+
+ if (OidIsValid(op_negator))
+ {
+ op_negated = true;
+ ReleaseSysCacheList(catlist);
+ catlist = SearchSysCacheList(AMOPOPID, 1,
+ ObjectIdGetDatum(op_negator),
+ 0, 0, 0);
+ }
+ }
+
+ /* Now search the opfamilies */
+ for (i = 0; i < catlist->n_members; i++)
+ {
+ HeapTuple op_tuple = &catlist->members[i]->tuple;
+ Form_pg_amop op_form = (Form_pg_amop) GETSTRUCT(op_tuple);
+
+ /* must be btree */
+ if (op_form->amopmethod != BTREE_AM_OID)
+ continue;
+
+ if (lefttype != op_form->amoplefttype &&
+ righttype != op_form->amoprighttype)
+ continue;
+
+ /* Get the operator's btree strategy number */
+ op_strategy = (StrategyNumber) op_form->amopstrategy;
+ Assert(op_strategy >= 1 && op_strategy <= 5);
+
+ if (op_negated)
+ {
+ /* Only consider negators that are = */
+ if (op_strategy != BTEqualStrategyNumber)
+ continue;
+ op_strategy = ROWCOMPARE_NE;
+ }
+ }
+
+ ReleaseSysCacheList(catlist);
+
+ return op_strategy;
+}
+
+
/*
* get_op_opfamily_properties
*
Index: src/backend/optimizer/path/Makefile
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/optimizer/path/Makefile,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 Makefile
--- src/backend/optimizer/path/Makefile 19 Feb 2008 10:30:07 -0000 1.1.1.1
+++ src/backend/optimizer/path/Makefile 8 Aug 2009 00:23:30 -0000
@@ -13,6 +13,6 @@
include $(top_builddir)/src/Makefile.global
OBJS = allpaths.o clausesel.o costsize.o equivclass.o indxpath.o \
- joinpath.o joinrels.o orindxpath.o pathkeys.o tidpath.o
+ joininheritance.o joinpath.o joinrels.o orindxpath.o pathkeys.o tidpath.o
include $(top_srcdir)/src/backend/common.mk
Index: src/backend/optimizer/path/allpaths.c
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/optimizer/path/allpaths.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 allpaths.c
--- src/backend/optimizer/path/allpaths.c 6 Jul 2009 18:26:30 -0000 1.1.1.1
+++ src/backend/optimizer/path/allpaths.c 8 Aug 2009 00:23:30 -0000
@@ -457,6 +457,13 @@
}
}
}
+
+ /*
+ * Link the child RelOptInfo with the parents.
+ * Needed later for pushing the join down to the child relations
+ */
+ rel->has_children = true;
+ rel->children_rels = lappend(rel->children_rels, childrel);
}
/*
Index: src/backend/optimizer/path/joinrels.c
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/optimizer/path/joinrels.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 joinrels.c
--- src/backend/optimizer/path/joinrels.c 23 Jul 2009 17:42:06 -0000 1.1.1.1
+++ src/backend/optimizer/path/joinrels.c 8 Aug 2009 00:23:30 -0000
@@ -14,7 +14,9 @@
*/
#include "postgres.h"
+#include "optimizer/cost.h"
#include "optimizer/joininfo.h"
+#include "optimizer/joininheritance.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
@@ -27,8 +29,6 @@
ListCell *other_rels);
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel);
-static bool is_dummy_rel(RelOptInfo *rel);
-static void mark_dummy_rel(RelOptInfo *rel);
static bool restriction_is_constant_false(List *restrictlist);
@@ -239,6 +239,19 @@
elog(ERROR, "failed to build any %d-way joins", level);
}
+ /* Add any inherited append paths */
+ if (join_inheritance &&
+ (constraint_exclusion == CONSTRAINT_EXCLUSION_ON ||
+ constraint_exclusion == CONSTRAINT_EXCLUSION_PARTITION))
+ {
+ foreach(r, result_rels)
+ {
+ RelOptInfo *rel = (RelOptInfo *) lfirst(r);
+ add_inherited_append_path(rel);
+ }
+ }
+
+
return result_rels;
}
@@ -620,6 +633,41 @@
return joinrel;
}
+
+ /* Check and create inherited joins */
+ if (can_create_inherited_joins(root, rel1, rel2, sjinfo, restrictlist))
+ {
+ create_inherited_joins(root, joinrel, rel1, rel2, sjinfo, restrictlist);
+ }
+
+ /* Make paths for this join relation */
+ make_paths_for_join_rel(root, joinrel, rel1, rel2, sjinfo, restrictlist);
+
+ bms_free(joinrelids);
+
+ return joinrel;
+}
+
+
+/*
+ * make_paths_for_join_rel
+ * Given a join relation and two component rels from which it can be made,
+ * consider all possible paths that use the two component rels as outer
+ * and inner rel respectively. Add these paths to the join rel's pathlist
+ * if they survive comparison with other paths (and remove any existing
+ * paths that are dominated by these paths).
+ *
+ * Modifies the pathlist field of the joinrel node to contain the best
+ * paths found so far.
+ */
+void
+make_paths_for_join_rel(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *rel1,
+ RelOptInfo *rel2,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist)
+{
/*
* Consider paths using each rel as both outer and inner. Depending on
* the join type, a provably empty outer or inner rel might mean the join
@@ -741,9 +789,6 @@
break;
}
- bms_free(joinrelids);
-
- return joinrel;
}
@@ -939,7 +984,7 @@
*
* If so, it will have a single path that is dummy.
*/
-static bool
+bool
is_dummy_rel(RelOptInfo *rel)
{
return (rel->cheapest_total_path != NULL &&
@@ -949,7 +994,7 @@
/*
* Mark a rel as proven empty.
*/
-static void
+void
mark_dummy_rel(RelOptInfo *rel)
{
/* Set dummy size estimate */
Index: src/include/optimizer/paths.h
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/include/optimizer/paths.h,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 paths.h
--- src/include/optimizer/paths.h 11 Jun 2009 14:49:11 -0000 1.1.1.1
+++ src/include/optimizer/paths.h 8 Aug 2009 00:23:31 -0000
@@ -103,6 +103,15 @@
RelOptInfo *rel1, RelOptInfo *rel2);
extern bool have_join_order_restriction(PlannerInfo *root,
RelOptInfo *rel1, RelOptInfo *rel2);
+extern void make_paths_for_join_rel(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *rel1,
+ RelOptInfo *rel2,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist);
+
+extern bool is_dummy_rel(RelOptInfo *rel);
+extern void mark_dummy_rel(RelOptInfo *rel);
/*
* equivclass.c
Index: src/include/optimizer/cost.h
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/include/optimizer/cost.h,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 cost.h
--- src/include/optimizer/cost.h 11 Jun 2009 14:49:11 -0000 1.1.1.1
+++ src/include/optimizer/cost.h 8 Aug 2009 00:23:31 -0000
@@ -60,6 +60,7 @@
extern bool enable_mergejoin;
extern bool enable_hashjoin;
extern int constraint_exclusion;
+extern bool join_inheritance;
extern double clamp_row_est(double nrows);
extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
Index: src/backend/optimizer/util/var.c
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/optimizer/util/var.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 var.c
--- src/backend/optimizer/util/var.c 11 Jun 2009 14:48:59 -0000 1.1.1.1
+++ src/backend/optimizer/util/var.c 8 Aug 2009 00:23:30 -0000
@@ -671,6 +671,15 @@
break;
}
}
+ if (IsA(node, RestrictInfo))
+ {
+ RestrictInfo *rInfo = (RestrictInfo *) node;
+
+ /* recurse on the clause expression */
+ return expression_tree_walker((Node *) rInfo->clause,
+ pull_var_clause_walker, (void *) context);
+ }
+
return expression_tree_walker(node, pull_var_clause_walker,
(void *) context);
}
Index: src/backend/optimizer/util/plancat.c
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/optimizer/util/plancat.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 plancat.c
--- src/backend/optimizer/util/plancat.c 16 Jul 2009 06:33:43 -0000 1.1.1.1
+++ src/backend/optimizer/util/plancat.c 8 Aug 2009 00:23:30 -0000
@@ -625,6 +625,10 @@
safe_constraints = lappend(safe_constraints, pred);
}
+ /* Store the safe constraints in the relation. Will need them later if
+ * it is possible to create inherited joins */
+ rel->constraints = safe_constraints;
+
/*
* The constraints are effectively ANDed together, so we can just try to
* refute the entire collection at once. This may allow us to make proofs
Index: doc/src/sgml/config.sgml
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/doc/src/sgml/config.sgml,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 config.sgml
--- doc/src/sgml/config.sgml 4 Aug 2009 16:08:35 -0000 1.1.1.1
+++ doc/src/sgml/config.sgml 8 Aug 2009 00:23:30 -0000
@@ -2247,6 +2247,21 @@
+
+ join_inheritance (boolean)
+
+ join_inheritance> configuration parameter
+
+
+
+ Enables the planner to push a join to the children of tables. When this
+ option is enabled, the planner pushes the join between the children of
+ the two relations instead of making append of the children and performing
+ the join. The default is off>.
+
+
+
+
cursor_tuple_fraction (floating point)
Index: src/include/utils/lsyscache.h
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/include/utils/lsyscache.h,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 lsyscache.h
--- src/include/utils/lsyscache.h 11 Jun 2009 14:49:13 -0000 1.1.1.1
+++ src/include/utils/lsyscache.h 8 Aug 2009 00:23:31 -0000
@@ -32,6 +32,7 @@
extern bool op_in_opfamily(Oid opno, Oid opfamily);
extern int get_op_opfamily_strategy(Oid opno, Oid opfamily);
+extern int get_op_optypes_strategy(Oid opno, Oid lefttype, Oid righttype);
extern void get_op_opfamily_properties(Oid opno, Oid opfamily,
int *strategy,
Oid *lefttype,
Index: src/backend/optimizer/prep/prepunion.c
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/optimizer/prep/prepunion.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 prepunion.c
--- src/backend/optimizer/prep/prepunion.c 6 Jul 2009 18:26:30 -0000 1.1.1.1
+++ src/backend/optimizer/prep/prepunion.c 8 Aug 2009 00:23:30 -0000
@@ -1632,11 +1632,65 @@
context->child_relid);
return (Node *) phv;
}
+ if (IsA(node, RestrictInfo))
+ {
+ /*
+ * We have to process RestrictInfo nodes specially.
+ * Needed for the join inheritance feature.
+ */
+ RestrictInfo *oldinfo = (RestrictInfo *) node;
+ RestrictInfo *newinfo = makeNode(RestrictInfo);
+
+ /* Copy all flat-copiable fields */
+ memcpy(newinfo, oldinfo, sizeof(RestrictInfo));
+
+ /* Recursively fix the clause itself */
+ newinfo->clause = (Expr *)
+ adjust_appendrel_attrs_mutator((Node *) oldinfo->clause, context);
+
+ /* and the modified version, if an OR clause */
+ newinfo->orclause = (Expr *)
+ adjust_appendrel_attrs_mutator((Node *) oldinfo->orclause, context);
+
+ /* adjust relid sets too */
+ newinfo->clause_relids = adjust_relid_set(oldinfo->clause_relids,
+ context->parent_relid,
+ context->child_relid);
+ newinfo->required_relids = adjust_relid_set(oldinfo->required_relids,
+ context->parent_relid,
+ context->child_relid);
+ newinfo->left_relids = adjust_relid_set(oldinfo->left_relids,
+ context->parent_relid,
+ context->child_relid);
+ newinfo->right_relids = adjust_relid_set(oldinfo->right_relids,
+ context->parent_relid,
+ context->child_relid);
+ newinfo->nullable_relids = adjust_relid_set(oldinfo->nullable_relids,
+ context->parent_relid,
+ context->child_relid);
+
+ /*
+ * Reset cached derivative fields, since these might need to have
+ * different values when considering the child relation.
+ */
+ newinfo->eval_cost.startup = -1;
+ newinfo->norm_selec = -1;
+ newinfo->outer_selec = -1;
+ newinfo->left_ec = NULL;
+ newinfo->right_ec = NULL;
+ newinfo->left_em = NULL;
+ newinfo->right_em = NULL;
+ newinfo->scansel_cache = NIL;
+ newinfo->left_bucketsize = -1;
+ newinfo->right_bucketsize = -1;
+
+ return (Node *) newinfo;
+ }
+
/* Shouldn't need to handle planner auxiliary nodes here */
Assert(!IsA(node, SpecialJoinInfo));
Assert(!IsA(node, AppendRelInfo));
Assert(!IsA(node, PlaceHolderInfo));
- Assert(!IsA(node, RestrictInfo));
/*
* NOTE: we do not need to recurse into sublinks, because they should
Index: src/backend/optimizer/plan/createplan.c
===================================================================
RCS file: /home/hherodot/cvsroot/PostgreSQL_8_4_0/src/backend/optimizer/plan/createplan.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 createplan.c
--- src/backend/optimizer/plan/createplan.c 17 Jul 2009 23:19:34 -0000 1.1.1.1
+++ src/backend/optimizer/plan/createplan.c 8 Aug 2009 00:23:30 -0000
@@ -3011,7 +3011,7 @@
{
EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
- if (em->em_is_const || em->em_is_child)
+ if (em->em_is_const || (em->em_is_child && !join_inheritance))
continue;
tle = tlist_member((Node *) em->em_expr, tlist);
@@ -3047,7 +3047,7 @@
List *exprvars;
ListCell *k;
- if (em->em_is_const || em->em_is_child)
+ if (em->em_is_const || (em->em_is_child && !join_inheritance))
continue;
sortexpr = em->em_expr;
exprvars = pull_var_clause((Node *) sortexpr,
Index: src/backend/utils/misc/intervaltree.c
===================================================================
RCS file: src/backend/utils/misc/intervaltree.c
diff -N src/backend/utils/misc/intervaltree.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/backend/utils/misc/intervaltree.c 1 Jan 1970 00:00:00 -0000
@@ -0,0 +1,1420 @@
+/*-------------------------------------------------------------------------
+ *
+ * intervaltree.c
+ *
+ * Contains the functions used to implement an interval
+ * tree using red-black-trees as described in the book
+ * "Introduction To Algorithms" by Cormen, Leisserson, and Rivest.
+ *
+ * IDENTIFICATION
+ * $PostgreSQL: pgsql/src/backend/utils/intervaltree.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "executor/executor.h"
+#include "optimizer/clauses.h"
+#include "nodes/execnodes.h"
+#include "parser/parse_oper.h"
+#include "utils/intervaltree.h"
+
+
+/* Functions to build intervals from constraints */
+
+static void adjust_intervals_from_constraint(List *intervals,
+ Node *constraint,
+ Var* target_var);
+
+static void adjust_intervals_from_and_constraints(List *intervals,
+ BoolExpr *constraint,
+ Var* target_var);
+
+static void adjust_intervals_from_or_constraints(List *intervals,
+ BoolExpr *constraint,
+ Var* target_var);
+
+static void adjust_intervals_from_op_constraint(List *intervals,
+ OpExpr *constraint,
+ Var* target_var);
+
+
+/* Function prototypes for IntervalTree helper functions */
+
+static Const *maxConst(Const *a, Const *b, Const *c);
+
+static void it_insert_interval_helper(IntervalTree *tree,
+ IntervalTreeNode *new_node);
+
+static bool it_get_overlaping_intervals_helper(IntervalTree *tree,
+ IntervalTreeNode *node,
+ ConstInterval *interval,
+ List **results);
+
+static void it_destroy_interval_tree_helper(IntervalTree *tree,
+ IntervalTreeNode *node,
+ bool deep);
+
+static void it_delete_fix_up(IntervalTree *tree, IntervalTreeNode *node);
+static void it_fix_up_max_high(IntervalTree *tree, IntervalTreeNode *node);
+
+static void it_left_rotate(IntervalTree *tree, IntervalTreeNode *node);
+static void it_right_rotate(IntervalTree *tree, IntervalTreeNode *node);
+
+static IntervalTreeNode *it_find_interval_tree_node(IntervalTree *tree,
+ ConstInterval *interval);
+
+
+/* Constants to represent negative and positive infinity */
+Const MIN_CONST = { };
+Const MAX_CONST = { };
+
+
+/****************** Functions for ConstInterval ***************/
+
+/*
+ * const_less_than
+ *
+ * Returns true if "a" is less than "b". The flag strict is
+ * determines whether the inequality check should be strict
+ * or not.
+ * if strict=true, the function returns (a < b)
+ * if strict=false, the function returns (a <= b)
+ */
+bool
+const_less_than(Const *a, Const *b, bool strict)
+{
+ char *op;
+ List *opnames;
+ Expr *test_expr;
+ Datum test_result;
+ MemoryContext oldcontext;
+ EState *estate;
+ ExprState *test_exprstate;
+ bool is_null;
+
+ /* Check for the infinity values first */
+ if (a == &MIN_CONST || b == &MAX_CONST)
+ return true;
+ else if (a == &MAX_CONST || b == &MIN_CONST)
+ return false;
+
+ /* Build the operator string */
+ if (strict)
+ {
+ op = (char *) palloc(2*sizeof(char));
+ op[0] = '<';
+ op[1] = '\0';
+ }
+ else
+ {
+ op = (char *) palloc(3*sizeof(char));
+ op[0] = '<';
+ op[1] = '=';
+ op[2] = '\0';
+ }
+
+ /* Build the expression */
+ opnames = list_make1(makeString(op));
+ test_expr = make_op(NULL, opnames, (Node *) a, (Node *) b, -1);
+
+ /* Evaluate the test. For this we need an EState. */
+ estate = CreateExecutorState();
+
+ /* We can use the estate's working context to avoid memory leaks. */
+ oldcontext = MemoryContextSwitchTo(estate->es_query_cxt);
+
+ /* Prepare and execute the expression */
+ test_exprstate = ExecPrepareExpr(test_expr, estate);
+ test_result = ExecEvalExprSwitchContext(test_exprstate,
+ GetPerTupleExprContext(estate),
+ &is_null, NULL);
+
+ /* Get back to outer memory context */
+ MemoryContextSwitchTo(oldcontext);
+
+ /* Release all the junk we just created */
+ FreeExecutorState(estate);
+
+ return DatumGetBool(test_result);
+}
+
+
+/*
+ * create_inf_interval
+ *
+ * Creates a new interval that represents the entire domain i.e. (-inf, inf)
+ * The new interval is allocated using palloc.
+ */
+ConstInterval *
+create_inf_interval(RelOptInfo *rel)
+{
+ ConstInterval *interval = (ConstInterval *) palloc(sizeof(ConstInterval));
+
+ interval->low = &MIN_CONST;
+ interval->low_closed = false;
+ interval->high = &MAX_CONST;
+ interval->high_closed = false;
+ interval->rel = rel;
+
+ return interval;
+}
+
+
+/*
+ * create_interval
+ *
+ * Creates a new interval that could be open, closed or partially closed
+ * The new interval is allocated using palloc.
+ */
+ConstInterval *
+create_interval(RelOptInfo *rel, Const *low, bool low_closed,
+ Const *high, bool high_closed)
+{
+ ConstInterval *interval = (ConstInterval *) palloc(sizeof(ConstInterval));
+
+ interval->low = low;
+ interval->low_closed = low_closed;
+ interval->high = high;
+ interval->high_closed = high_closed;
+ interval->rel = rel;
+
+ return interval;
+}
+
+
+/*
+ * copy_interval
+ *
+ * Creates and returns a new interval as a copy of the input interval.
+ * Note that the Const values and the rel are NOT copied.
+ */
+ConstInterval *
+copy_interval(ConstInterval *interval)
+{
+ ConstInterval *new_interval = (ConstInterval *) palloc(sizeof(ConstInterval));
+
+ new_interval->low = interval->low;
+ new_interval->low_closed = interval->low_closed;
+ new_interval->high = interval->high;
+ new_interval->high_closed = interval->high_closed;
+ new_interval->rel = interval->rel;
+
+ return new_interval;
+}
+
+
+/*
+ * set_interval_low_point
+ *
+ * Sets the low point of the interval. If the low point of the interval is
+ * already set, then the new low is set only if it is higher than the old one.
+ */
+void
+set_interval_low_point(ConstInterval *interval, Const *low, bool low_closed)
+{
+ if (interval == NULL || low == NULL)
+ return;
+
+ if (interval->low == &MIN_CONST ||
+ const_less_than(interval->low, low, true))
+ {
+ /* The new low is higher than the old one */
+ interval->low = low;
+ interval->low_closed = low_closed;
+ }
+}
+
+
+/*
+ * set_interval_high_point
+ *
+ * Sets the high point of the interval. If the high point of the interval is
+ * already set, then the new high is set only if it is less than the old one.
+ */
+void
+set_interval_high_point(ConstInterval *interval, Const *high, bool high_closed)
+{
+ if (interval == NULL || high == NULL)
+ return;
+
+ if (interval->high == &MAX_CONST ||
+ const_less_than(high, interval->high, true))
+ {
+ /* The new high is lower than the old one */
+ interval->high = high;
+ interval->high_closed = high_closed;
+ }
+}
+
+
+/*
+ * interval_overlap
+ *
+ * Returns true if the two intervals overlap. This functions handles any type
+ * of intervals (open, closed, partially closed), one sided intervals and
+ * intervals the represent a single point (i.e. [x, x]).
+ *
+ * The general idea here is that the two intervals overlap if and only if
+ * the low value of one interval is between the low and high values of
+ * the other. Whether the inequality is strict or not, depends on whether
+ * the intervals are closed or open.
+ */
+bool
+interval_overlap(ConstInterval *a, ConstInterval *b)
+{
+ if (const_less_than(a->low, b->low, !a->low_closed)) {
+ return const_less_than(b->low, a->high, !b->low_closed || !a->high_closed);
+ } else {
+ return const_less_than(a->low, b->high, !a->low_closed || !b->high_closed);
+ }
+}
+
+
+/*
+ * is_interval_inf
+ *
+ * Returns true if this interval represents (-inf, inf)
+ */
+bool
+is_interval_inf(ConstInterval *interval)
+{
+ return (interval->low == &MIN_CONST && interval->high == &MAX_CONST);
+}
+
+
+/*
+ * is_any_interval_inf
+ *
+ * Returns true if any interval in the list represents (-inf, inf)
+ */
+bool
+is_any_interval_inf(List *interval_list)
+{
+ ListCell *lc_interval;
+
+ foreach(lc_interval, interval_list)
+ {
+ ConstInterval *interval = (ConstInterval *) lfirst(lc_interval);
+ if (interval->low == &MIN_CONST && interval->high == &MAX_CONST)
+ return true;
+ }
+
+ return false;
+}
+
+
+/************** Functions to build intervals from constraints ****************/
+
+
+/*
+ * get_intervals_from_constraints
+ *
+ * This function is responsible for creating intervals based on the relation's
+ * constraints and the target var. It returns a list of ConstInterval objects,
+ * all of which are associated with the input rel. The list will contain
+ * at least one interval in it. If not intervals can be build, then the
+ * returned interval represents (-inf, inf).
+ */
+List *
+get_intervals_from_constraints(RelOptInfo *rel, Var *target_var)
+{
+ List *intervals;
+ ListCell *lc_constraint;
+
+ /* Create a new interval */
+ intervals = list_make1(create_inf_interval(rel));
+
+ if (target_var == NULL)
+ return intervals;
+
+ /* Adjust the intervals based on the constraints */
+ foreach(lc_constraint, rel->constraints)
+ {
+ Node *constraint = (Node *) lfirst(lc_constraint);
+ adjust_intervals_from_constraint(intervals, constraint, target_var);
+ }
+
+ return intervals;
+}
+
+
+/*
+ * adjust_intervals_from_constraint
+ *
+ * This is the high level function for adjusting all intervals seen
+ * so far based on the input constraint. It simply delicates the task
+ * down depending on the type of the constraint - operator expression,
+ * OR expression, or AND expression. See corresponding function's
+ * comments for additional information.
+ *
+ * It assumes that the intervals list contains at least one interval.
+ */
+static void
+adjust_intervals_from_constraint(List *intervals,
+ Node *constraint,
+ Var* target_var)
+{
+ /* Call the appropriate method */
+ if (is_opclause(constraint))
+ {
+ adjust_intervals_from_op_constraint(intervals,
+ (OpExpr *)constraint, target_var);
+ }
+ else if (or_clause(constraint))
+ {
+ adjust_intervals_from_or_constraints(intervals,
+ (BoolExpr *)constraint, target_var);
+ }
+ else if (and_clause(constraint))
+ {
+ adjust_intervals_from_and_constraints(intervals,
+ (BoolExpr *)constraint, target_var);
+ }
+}
+
+
+/*
+ * adjust_intervals_from_and_constraints
+ *
+ * The input constraint represents an AND expression of constraints.
+ * All intervals in the input list are adjusted accordingly using
+ * AND semantics.
+ *
+ * It assumes that the intervals list contains at least one interval.
+ *
+ * Example:
+ * Suppose the intervals list contains (-inf, inf) and [8, 12)
+ * Suppose the constraint is (a > 5 and a <= 10).
+ * The intervals will be adjusted and become (5, 10] and [8, 10].
+ */
+static void
+adjust_intervals_from_and_constraints(List *intervals,
+ BoolExpr *constraint,
+ Var* target_var)
+{
+ ListCell *lc_constraint;
+
+ /* Iterate through the constraints to modify the intervals */
+ foreach(lc_constraint, constraint->args)
+ {
+ Node *constraint = (Node *)lfirst(lc_constraint);
+ adjust_intervals_from_constraint(intervals, constraint, target_var);
+ }
+}
+
+
+/*
+ * adjust_intervals_from_or_constraints
+ *
+ * The input constraint represents an OR expression of constraints.
+ * All intervals in the input list are adjusted accordingly using
+ * OR semantics.
+ *
+ * The general idea of this function is the following: First, it makes a
+ * copy of the intervals list for each constraint in the OR constraint.
+ * Then, it adjusts each list with the corresponding constraint. Finally,
+ * it concatenates all intervals together.
+ *
+ * It assumes that the intervals list contains at least one interval.
+ *
+ * Example:
+ * Suppose the intervals list contains (-inf, inf) and [8, 12)
+ * Suppose the constraint is (a > 5 or a <= 10).
+ * The intervals will be adjusted and become:
+ * (5, inf), (-inf, 10], [8, 12) and [8, 10]
+ */
+static void
+adjust_intervals_from_or_constraints(List *intervals,
+ BoolExpr *constraint,
+ Var* target_var)
+{
+ List *all_intervals = NIL; /* List of lists of intervals */
+
+ ListCell *lc_constraint;
+ ListCell *lc_interval;
+ ListCell *lc_interval_list;
+
+ int num_copies;
+ int i;
+
+ /* Create a new interval list for each constraint, except the first one */
+ all_intervals = lappend(all_intervals, intervals);
+ num_copies = list_length(constraint->args) - 1;
+
+ for (i = 0; i < num_copies; ++i)
+ {
+ List *new_intervals = NIL;
+
+ foreach(lc_interval, intervals)
+ {
+ ConstInterval *interval = (ConstInterval *) lfirst(lc_interval);
+ new_intervals = lappend(new_intervals, copy_interval(interval));
+ }
+ all_intervals = lappend(all_intervals, new_intervals);
+ }
+
+ /* Adjust each interval list with the appropriate constraints */
+ forboth(lc_constraint, constraint->args,
+ lc_interval_list, all_intervals)
+ {
+ Node *constraint = (Node *)lfirst(lc_constraint);
+ List *new_intervals = (List *) lfirst(lc_interval_list);
+
+ adjust_intervals_from_constraint(new_intervals, constraint, target_var);
+ }
+
+ /*
+ * Concat the interval lists together.
+ * Note that the first list is the input one
+ */
+ i = 0;
+ foreach(lc_interval_list, all_intervals)
+ {
+ List *new_intervals = (List *) lfirst(lc_interval_list);
+ if (i > 0)
+ {
+ intervals = list_concat(intervals, new_intervals);
+ }
+ ++i;
+ }
+}
+
+
+/*
+ * adjust_intervals_from_op_constraint
+ *
+ * This functions modifies the input intervals based on the input contraint.
+ * The input expression should be a binary expression of the form "var op const"
+ * or "const op var", where the expression's var should match the target var.
+ * If this is the case, then the appropriate side of the intervals is set to
+ * the expression's const.
+ *
+ * For example, if the expression is "var1 > const1", then const1 is set as
+ * the low point of the intervals and is marked as open.
+ *
+ * In the case where the operator is the equality operator, both sides of
+ * the intervals are set to const and are set as closed.
+ *
+ * If the expression does not meet the above criteria or the const is null,
+ * then the intervals are not modified.
+ */
+static void
+adjust_intervals_from_op_constraint(List *intervals,
+ OpExpr *constraint,
+ Var* target_var)
+{
+ Node *leftop;
+ Node *rightop;
+ Node *expr_var;
+ Const *expr_const;
+ bool var_on_left;
+ Oid opno;
+ StrategyNumber op_strategy;
+ ListCell *lc_interval;
+
+ /* Get the expression components */
+ leftop = get_leftop((Expr *) constraint);
+ rightop = get_rightop((Expr *) constraint);
+ opno = constraint->opno;
+
+ /* Is a binary opclause? */
+ if (rightop == NULL)
+ return;
+
+ /* Get the const and var from the expression */
+ if (IsA(rightop, Const))
+ {
+ expr_var = leftop;
+ expr_const = (Const *) rightop;
+ var_on_left = true;
+ }
+ else if (IsA(leftop, Const))
+ {
+ expr_var = rightop;
+ expr_const = (Const *) leftop;
+ var_on_left = false;
+ }
+
+ /* Is expression var the same as the input var? */
+ if (!equal(expr_var, target_var))
+ return;
+
+ /* We don't care about consts that are null */
+ if (expr_const == NULL || expr_const->constisnull)
+ return;
+
+ /* Get the strategy and adjust the intervals */
+ op_strategy = get_op_optypes_strategy(opno, target_var->vartype,
+ expr_const->consttype);
+
+ foreach(lc_interval, intervals)
+ {
+ ConstInterval *interval = (ConstInterval *)lfirst(lc_interval);
+
+ switch (op_strategy) {
+ case BTLessStrategyNumber:
+ case BTLessEqualStrategyNumber:
+ {
+ /* Less than [or equal] */
+ bool closed = (op_strategy == BTLessEqualStrategyNumber);
+ if (var_on_left)
+ set_interval_high_point(interval, expr_const, closed);
+ else
+ set_interval_low_point(interval, expr_const, closed);
+ break;
+ }
+ case BTEqualStrategyNumber:
+ {
+ /* Equality i.e. a point interval */
+ set_interval_low_point(interval, expr_const, true);
+ set_interval_high_point(interval, expr_const, true);
+ break;
+ }
+ case BTGreaterEqualStrategyNumber:
+ case BTGreaterStrategyNumber:
+ {
+ /* Less than [or equal] */
+ bool closed = (op_strategy == BTGreaterEqualStrategyNumber);
+ if (var_on_left)
+ set_interval_low_point(interval, expr_const, closed);
+ else
+ set_interval_high_point(interval, expr_const, closed);
+ break;
+ }
+ default:
+ {
+ /* Nothing to do */
+ break;
+ }
+ } /* End switch statement on op_strategy */
+ } /* End foreach interval loop */
+
+}
+
+
+/*
+ * maxConst
+ *
+ * Returns the maximum between the two consts
+ */
+static Const *
+maxConst(Const *a, Const *b, Const *c)
+{
+ Const *max = const_less_than(a, b, true) ? b : a;
+ return const_less_than(max, c, true) ? c : max;
+}
+
+
+/**************** Functions for IntervalTreeNode ********************/
+
+/*
+ * it_create_interval_tree_node
+ *
+ * Creates and returns a new interval tree node associated with the
+ * new interval.
+ * The new node is allocated using palloc.
+ */
+IntervalTreeNode *
+it_create_interval_tree_node(ConstInterval *newInterval)
+{
+ IntervalTreeNode *node = (IntervalTreeNode *) palloc(
+ sizeof(IntervalTreeNode));
+
+ /* Set the keys appropriately */
+ if (newInterval == NULL) {
+ node->storedInterval = NULL;
+ node->key = NULL;
+ node->high = NULL;
+ node->maxHigh = NULL;
+ } else {
+ node->storedInterval = newInterval;
+ node->key = newInterval->low;
+ node->high = newInterval->high;
+ node->maxHigh = newInterval->high;
+ }
+
+ /* Initializations */
+ node->red = false;
+ node->left = NULL;
+ node->right = NULL;
+ node->parent = NULL;
+
+ return node;
+}
+
+
+/**************** Functions for IntervalTreeNode ********************/
+
+/*
+ * it_create_interval_tree
+ *
+ * Creates a new interval tree node. This function initializes the root
+ * and nil tree nodes. The point of using these sentinels is so that
+ * the root and nil nodes do not require special cases in the code
+ */
+IntervalTree *
+it_create_interval_tree()
+{
+ IntervalTree *tree = (IntervalTree *) palloc(sizeof(IntervalTree));
+ IntervalTreeNode *nil;
+ IntervalTreeNode *root;
+
+ /* Create the nil node */
+ nil = it_create_interval_tree_node(NULL);
+ nil->left = nil->right = nil->parent = nil;
+ nil->red = false;
+ nil->key = nil->high = nil->maxHigh = &MIN_CONST;
+ nil->storedInterval = NULL;
+ tree->nil = nil;
+
+ /* Create the root node */
+ root = it_create_interval_tree_node(NULL);
+ root->parent = root->left = root->right = nil;
+ root->key = root->high = root->maxHigh = &MAX_CONST;
+ root->red = false;
+ root->storedInterval = NULL;
+ tree->root = root;
+
+ return tree;
+}
+
+
+/*
+ * it_destroy_interval_tree
+ *
+ * Clears the memory allocated for the tree and the tree nodes.
+ * If the deep flag is set, the intervals are freed as well.
+ * Note that the const values are not deleted.
+ */
+void
+it_destroy_interval_tree(IntervalTree *tree, bool deep)
+{
+ if (tree == NULL)
+ return;
+
+ it_destroy_interval_tree_helper(tree, tree->root->left, deep);
+
+ pfree(tree->nil);
+ pfree(tree->root);
+ pfree(tree);
+ tree = NULL;
+}
+
+
+/*
+ * it_is_interval_tree_empty
+ *
+ * Returns true if the interval tree is empty
+ */
+bool
+it_is_interval_tree_empty(IntervalTree *tree)
+{
+ return tree->root->left == tree->nil;
+}
+
+
+/*
+ * it_insert_interval
+ *
+ * Creates a new interval node which contains the appropriate key and
+ * info pointers and inserts it into the tree. This function returns
+ * a pointer to the newly inserted node which is guaranteed to be
+ * valid until this node is deleted.
+ *
+ * new_nterval is the interval to insert. The left end point is used as
+ * the key.
+ */
+IntervalTreeNode *
+it_insert_interval(IntervalTree *tree, ConstInterval *new_interval)
+{
+ IntervalTreeNode * y;
+ IntervalTreeNode * x;
+ IntervalTreeNode * new_node;
+
+ /* Insert the new node and fix up the high value */
+ x = it_create_interval_tree_node(new_interval);
+ it_insert_interval_helper(tree, x);
+ it_fix_up_max_high(tree, x->parent);
+
+ /* Re-balance the tree using rotations */
+ new_node = x;
+ x->red = true;
+ while (x->parent->red)
+ {
+ if (x->parent == x->parent->parent->left)
+ {
+ y = x->parent->parent->right;
+ if (y->red)
+ {
+ x->parent->red = false;
+ y->red = false;
+ x->parent->parent->red = true;
+ x = x->parent->parent;
+ }
+ else
+ {
+ if (x == x->parent->right)
+ {
+ x = x->parent;
+ it_left_rotate(tree, x);
+ }
+ x->parent->red = false;
+ x->parent->parent->red = true;
+ it_right_rotate(tree, x->parent->parent);
+ }
+ }
+ else
+ {
+ /*
+ * Case for x->parent == x->parent->parent->right
+ * this part is just like the section above with
+ * left and right interchanged
+ */
+ y = x->parent->parent->left;
+ if (y->red)
+ {
+ x->parent->red = false;
+ y->red = false;
+ x->parent->parent->red = true;
+ x = x->parent->parent;
+ }
+ else
+ {
+ if (x == x->parent->left)
+ {
+ x = x->parent;
+ it_right_rotate(tree, x);
+ }
+ x->parent->red = false;
+ x->parent->parent->red = true;
+ it_left_rotate(tree, x->parent->parent);
+ }
+ }
+ }
+
+ tree->root->left->red = false;
+
+ return new_node;
+}
+
+
+/*
+ * it_delete_interval
+ *
+ * Delete the specified interval from the tree. The interval is determined
+ * to be in the tree via the use of pointer equality.
+ *
+ * The deleted interval is returned or NULL if not found.
+ */
+ConstInterval *
+it_delete_interval(IntervalTree *tree, ConstInterval *interval)
+{
+ IntervalTreeNode *node;
+
+ if (interval != NULL)
+ {
+ /* Search for the interval node containing the interval */
+ node = it_find_interval_tree_node(tree, interval);
+ if (node != tree->nil)
+ {
+ return it_delete_interval_tree_node(tree, node);
+ }
+ }
+ return NULL;
+}
+
+
+/*
+ * it_delete_interval_tree_node
+ *
+ * Deleted the provided tree node from the tree. Note that the insert method
+ * returns the tree node, hence someone might save it and delete later
+ * without having to search for the node. This functions also makes sure
+ * to fix up the high value of each affected node as well as to restore
+ * the red-black tree properties.
+ *
+ * Returns the deleted interval.
+ */
+ConstInterval *
+it_delete_interval_tree_node(IntervalTree *tree, IntervalTreeNode *node)
+{
+ IntervalTreeNode *y;
+ IntervalTreeNode *x;
+ ConstInterval * return_value = node->storedInterval;
+
+ y = ((node->left == tree->nil) || (node->right == tree->nil)) ? node
+ : it_get_successor_of(tree, node);
+ x = (y->left == tree->nil) ? y->right : y->left;
+
+ x->parent = y->parent;
+ if (tree->root == x->parent)
+ {
+ tree->root->left = x;
+ }
+ else
+ {
+ if (y == y->parent->left)
+ y->parent->left = x;
+ else
+ y->parent->right = x;
+ }
+
+ if (y != node) /* y should not be nil in this case */
+ {
+ /* y is the node to splice out and x is its child */
+ y->maxHigh = &MIN_CONST;
+ y->left = node->left;
+ y->right = node->right;
+ y->parent = node->parent;
+ node->left->parent = node->right->parent = y;
+
+ if (node == node->parent->left)
+ node->parent->left = y;
+ else
+ node->parent->right = y;
+
+ it_fix_up_max_high(tree, x->parent);
+ if (!(y->red))
+ {
+ y->red = node->red;
+ it_delete_fix_up(tree, x);
+ }
+ else
+ {
+ y->red = node->red;
+ }
+ pfree(node);
+ }
+ else
+ {
+ it_fix_up_max_high(tree, x->parent);
+ if (!(y->red))
+ {
+ it_delete_fix_up(tree, x);
+ }
+ pfree(y);
+ }
+
+ return return_value;
+}
+
+
+/*
+ * it_get_overlaping_intervals
+ *
+ * Returns a list containing pointers to intervals in the tree that overlap
+ * with the provided interval. The interval could be open, closed, partially
+ * closed, one sided or point. This algorithm runs in O(max(N,k*log(N)))
+ * where N is the number of intervals in the tree and k is the number of
+ * overlapping intervals (results).
+ *
+ * Look at the comments of getOverlapingIntervalsHelper for algorithmic
+ * details.
+ */
+List *
+it_get_overlaping_intervals(IntervalTree *tree, ConstInterval *interval)
+{
+ List *results = NIL;
+ IntervalTreeNode *node = tree->root->left;
+
+ it_get_overlaping_intervals_helper(tree, node, interval, &results);
+
+ return results;
+}
+
+
+/*
+ * it_get_left_overlaping_intervals
+ *
+ * Returns a list containing pointers to intervals in the tree that are
+ * to the left of the provided interval. The interval could be open, closed,
+ * partially closed, one sided or point.
+ *
+ * Suppose A is an interval in the tree such that A1 < A < A2 and B is the
+ * input interval such that B1 < B < B2. The interval A is included in the
+ * results list if it is possible for A <= B. If the strict flag is set,
+ * then the check condition is A < B.
+ *
+ * This is equivalent to gathering the intervals that overlap with the
+ * interval (-inf, B2). If the strict flag is set, then the B2 side must
+ * be open.
+ */
+List *
+it_get_left_overlaping_intervals(IntervalTree *tree,
+ ConstInterval *interval,
+ bool strict)
+{
+ List *results = NIL;
+ IntervalTreeNode *node = tree->root->left;
+ Const *old_const = interval->low;
+ bool old_closed = interval->high_closed;
+
+ /* Adjust the low end point and the high interval type */
+ interval->low = &MIN_CONST;
+ interval->high_closed = strict ? false : interval->high_closed;
+
+ /* Get the overlapping intervals */
+ it_get_overlaping_intervals_helper(tree, node, interval, &results);
+
+ /* Restore original interval */
+ interval->low = old_const;
+ interval->high_closed = old_closed;
+
+ return results;
+}
+
+
+/*
+ * it_get_right_overlaping_intervals
+ *
+ * Returns a list containing pointers to intervals in the tree that are
+ * to the right of the provided interval. The interval could be open, closed,
+ * partially closed, one sided or point.
+ *
+ * Suppose A is an interval in the tree such that A1 < A < A2 and B is the
+ * input interval such that B1 < B < B2. The interval A is included in the
+ * results list if it is possible for A >= B. If the strict flag is set,
+ * then the check condition is A > B.
+ *
+ * This is equivalent to gathering the intervals that overlap with the
+ * interval (B1, inf). If the strict flag is set, then the B1 side must
+ * be open.
+ */
+List *
+it_get_right_overlaping_intervals(IntervalTree *tree,
+ ConstInterval *interval,
+ bool strict)
+{
+ List *results = NIL;
+ IntervalTreeNode *node = tree->root->left;
+ Const *old_const = interval->high;
+ bool old_closed = interval->low_closed;
+
+ /* Adjust the high end point and the low interval type */
+ interval->high = &MAX_CONST;
+ interval->low_closed = strict ? false : interval->low_closed;
+
+ /* Get the overlapping intervals */
+ it_get_overlaping_intervals_helper(tree, node, interval, &results);
+
+ /* Restore original interval */
+ interval->high = old_const;
+ interval->low_closed = old_closed;
+
+ return results;
+}
+
+
+/*
+ * it_get_successor_of
+ *
+ * This function returns the successor of node or nil if no successor exists.
+ */
+IntervalTreeNode *
+it_get_successor_of(IntervalTree *tree, IntervalTreeNode *node)
+{
+ IntervalTreeNode *successor = node->right;
+
+ if (tree->nil != successor)
+ {
+ /* Returns the minimum of the right subtree of node */
+ while (successor->left != tree->nil)
+ {
+ successor = successor->left;
+ }
+ return successor;
+ }
+ else
+ {
+ /* Go up the tree */
+ successor = node->parent;
+ while (node == successor->right)
+ {
+ node = successor;
+ successor = successor->parent;
+ }
+ if (successor == tree->root)
+ return tree->nil;
+ return successor;
+ }
+}
+
+
+/*
+ * it_get_predecessor_of
+ *
+ * This function returns the predecessor of node or nil if no successor exists.
+ */
+IntervalTreeNode *
+it_get_predecessor_of(IntervalTree *tree, IntervalTreeNode *node)
+{
+ IntervalTreeNode *predecessor = node->left;
+
+ if (tree->nil != predecessor)
+ {
+ /* Returns the maximum of the left subtree of node */
+ while (predecessor->right != tree->nil)
+ {
+ predecessor = predecessor->right;
+ }
+ return predecessor;
+ }
+ else
+ {
+ /* Go up the tree */
+ predecessor = node->parent;
+ while (node == predecessor->left)
+ {
+ if (predecessor == tree->root)
+ return tree->nil;
+ node = predecessor;
+ predecessor = predecessor->parent;
+ }
+ return predecessor;
+ }
+}
+
+
+/*
+ * insertIntervalHelper
+ *
+ * A helper method for inserting intervals into the tree. The node is
+ * inserted into the tree as if it were a regular binary tree.
+ */
+static void
+it_insert_interval_helper(IntervalTree *tree, IntervalTreeNode *new_node)
+{
+ IntervalTreeNode *temp_node;
+ IntervalTreeNode *new_parent;
+ bool placeLeft = true;
+
+ new_node->left = new_node->right = tree->nil;
+ new_parent = tree->root;
+ temp_node = tree->root->left;
+
+ /* Find the insertion point. y is the new parent */
+ while (temp_node != tree->nil)
+ {
+ new_parent = temp_node;
+ if (const_less_than(new_node->key, temp_node->key, true))
+ {
+ temp_node = temp_node->left;
+ placeLeft = true;
+ }
+ else
+ {
+ temp_node = temp_node->right;
+ placeLeft = false;
+ }
+ }
+
+ /* Make the insertion */
+ new_node->parent = new_parent;
+ if ((new_parent == tree->root) || placeLeft)
+ new_parent->left = new_node;
+ else
+ new_parent->right = new_node;
+}
+
+
+/*
+ * getOverlapingIntervalsHelper
+ *
+ * A helper functions to traverse the tree recursively and find overlapping
+ * intervals. It returns true if we found an overlapping interval in the
+ * subtree under node.
+ *
+ * Input:
+ * tree is the interval tree to search
+ * node represents the current node in the search
+ * interval is the interval we are looking for overlaps
+ * results is the list in which we append the results
+ *
+ * The pruning algorithm is based on the following: Two intervals A and B
+ * overlap only when both A.low <= B.high and A.high >= B.low. When searching
+ * the tree for nodes overlapping with a given interval, we can immediately
+ * skip:
+ * - all nodes to the right of nodes whose low value is past the end of
+ * the given interval.
+ * - all nodes that have their maximum 'high' value below the start of
+ * the given interval.
+ *
+ * This means that any time we take the left branch down the tree we must
+ * also check the right branch if and only if we find an overlapping
+ * interval in that left branch. Note this is a recursive condition
+ * because if we go left at the root then go left again at the first
+ * left child and find an overlap in the left subtree of the left child
+ * of root we must recursively check the right subtree of the left child
+ * of root as well as the right child of root.
+ */
+static bool
+it_get_overlaping_intervals_helper(IntervalTree *tree,
+ IntervalTreeNode *node,
+ ConstInterval *interval,
+ List **results)
+{
+ int found_overlap = 0;
+ bool try_right_branch = false;
+
+ if (node != tree->nil)
+ {
+ /* Check for an overlap */
+ if (interval_overlap(interval, node->storedInterval))
+ {
+ *results = lappend(*results, node->storedInterval);
+ found_overlap = 1;
+ }
+
+ /* Go left or mark for going right */
+ if (const_less_than(interval->low, node->left->maxHigh, false))
+ {
+ found_overlap += it_get_overlaping_intervals_helper(tree,
+ node->left, interval, results);
+ }
+ else
+ {
+ try_right_branch = true;
+ }
+
+ /* Go right if needed */
+ if (try_right_branch || (found_overlap > 0))
+ {
+ found_overlap += it_get_overlaping_intervals_helper(tree,
+ node->right, interval, results);
+ }
+ }
+
+ return (found_overlap > 0);
+}
+
+
+/*
+ * destroyIntervalTreeHelper
+ *
+ * Clears the memory allocated by the tree nodes recursively.
+ * If the deep flag is set, the intervals are freed as well.
+ * Note that the Const values are not deleted.
+ */
+static void
+it_destroy_interval_tree_helper(IntervalTree *tree,
+ IntervalTreeNode *node,
+ bool deep)
+{
+ if (node != tree->nil)
+ {
+ it_destroy_interval_tree_helper(tree, node->left, deep);
+ it_destroy_interval_tree_helper(tree, node->right, deep);
+
+ if (deep && node->storedInterval != NULL)
+ pfree(node->storedInterval);
+ pfree(node);
+ node = NULL;
+ }
+}
+
+
+/*
+ * deleteFixUp
+ *
+ * Performs rotations and changes colors to restore red-black properties
+ * after a node is deleted
+ *
+ * node is the child of the spliced out node in it_delete_interval_tree_node.
+ */
+static void
+it_delete_fix_up(IntervalTree *tree, IntervalTreeNode *node)
+{
+ IntervalTreeNode *temp_node;
+ IntervalTreeNode *root_left = tree->root->left;
+
+ while ((!node->red) && (root_left != node))
+ {
+ if (node == node->parent->left)
+ {
+ /* The node is a left child */
+ temp_node = node->parent->right;
+ if (temp_node->red)
+ {
+ temp_node->red = false;
+ node->parent->red = true;
+ it_left_rotate(tree, node->parent);
+ temp_node = node->parent->right;
+ }
+ if ((!temp_node->right->red) && (!temp_node->left->red))
+ {
+ temp_node->red = true;
+ node = node->parent;
+ }
+ else
+ {
+ if (!temp_node->right->red)
+ {
+ temp_node->left->red = false;
+ temp_node->red = true;
+ it_right_rotate(tree, temp_node);
+ temp_node = node->parent->right;
+ }
+
+ temp_node->red = node->parent->red;
+ node->parent->red = false;
+ temp_node->right->red = false;
+ it_left_rotate(tree, node->parent);
+ node = root_left; /* this is to exit while loop */
+ }
+ }
+ else
+ {
+ /* The node is a right child */
+ /* The code below has left and right switched from above */
+ temp_node = node->parent->left;
+ if (temp_node->red)
+ {
+ temp_node->red = false;
+ node->parent->red = true;
+ it_right_rotate(tree, node->parent);
+ temp_node = node->parent->left;
+ }
+ if ((!temp_node->right->red) && (!temp_node->left->red))
+ {
+ temp_node->red = true;
+ node = node->parent;
+ }
+ else
+ {
+ if (!temp_node->left->red)
+ {
+ temp_node->right->red = false;
+ temp_node->red = true;
+ it_left_rotate(tree, temp_node);
+ temp_node = node->parent->left;
+ }
+
+ temp_node->red = node->parent->red;
+ node->parent->red = false;
+ temp_node->left->red = false;
+ it_right_rotate(tree, node->parent);
+ node = root_left; /* this is to exit while loop */
+ }
+ }
+ }
+
+ node->red = false;
+}
+
+
+/*
+ * fixUpMaxHigh
+ *
+ * Travels up to the root fixing the maxHigh fields after an insertion
+ * or deletion. maxHigh is the maximum between the high value of the
+ * current node and the maxHigh's of the two children.
+ *
+ * node is the starting point.
+ */
+static void
+it_fix_up_max_high(IntervalTree *tree, IntervalTreeNode *node)
+{
+ while (node != tree->root)
+ {
+ node->maxHigh = maxConst(node->high, node->left->maxHigh, node->right->maxHigh);
+ node = node->parent;
+ }
+}
+
+
+/*
+ * leftRotate
+ *
+ * Performs a left rotation to balance the tree. Basically this makes the
+ * parent of x be to the left of x, x the parent of its parent before the
+ * rotation and fixes other pointers accordingly. It also updates the
+ * maxHigh fields of x and y after rotation.
+ */
+static void
+it_left_rotate(IntervalTree *tree, IntervalTreeNode *x)
+{
+ IntervalTreeNode *y;
+
+ /* Initializations */
+ y = x->right;
+ x->right = y->left;
+
+ /* Make the rotation */
+ if (y->left != tree->nil)
+ y->left->parent = x;
+ y->parent = x->parent;
+
+ if (x == x->parent->left)
+ x->parent->left = y;
+ else
+ x->parent->right = y;
+
+ y->left = x;
+ x->parent = y;
+
+ /* Adjust the maxHigh fields */
+ x->maxHigh = maxConst(x->high, x->left->maxHigh, x->right->maxHigh);
+ y->maxHigh = maxConst(x->maxHigh, y->right->maxHigh, y->high);
+}
+
+
+/*
+ * rightRotate
+ *
+ * Performs a right rotation to balance the tree. Basically this makes the
+ * parent of x be to the left of x, x the parent of its parent before the
+ * rotation and fixes other pointers accordingly. It also updates the
+ * maxHigh fields of x and y after rotation.
+ */
+static void
+it_right_rotate(IntervalTree *tree, IntervalTreeNode *y)
+{
+ IntervalTreeNode *x;
+
+ /* Initializations */
+ x = y->left;
+ y->left = x->right;
+
+ /* Make the rotation */
+ if (tree->nil != x->right)
+ x->right->parent = y;
+ x->parent = y->parent;
+
+ if (y == y->parent->left) {
+ y->parent->left = x;
+ } else {
+ y->parent->right = x;
+ }
+ x->right = y;
+ y->parent = x;
+
+ /* Adjust the maxHigh fields */
+ y->maxHigh = maxConst(y->high, y->left->maxHigh, y->right->maxHigh);
+ x->maxHigh = maxConst(x->left->maxHigh, y->maxHigh, x->high);
+}
+
+
+/*
+ * findIntervalTreeNode
+ *
+ * Given an interval, it traverses the tree to find the tree node
+ * that holds this interval. The intervals are compared using simple
+ * pointer equality.
+ */
+static IntervalTreeNode *
+it_find_interval_tree_node(IntervalTree *tree, ConstInterval *interval)
+{
+ IntervalTreeNode *node = tree->root->left;
+
+ while (node != tree->nil && node->storedInterval != interval)
+ {
+ if (const_less_than(interval->low, node->key, true))
+ node = node->left;
+ else
+ node = node->right;
+ }
+
+ return node;
+}
+
Index: src/include/utils/intervaltree.h
===================================================================
RCS file: src/include/utils/intervaltree.h
diff -N src/include/utils/intervaltree.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/include/utils/intervaltree.h 1 Jan 1970 00:00:00 -0000
@@ -0,0 +1,129 @@
+/*-------------------------------------------------------------------------
+ *
+ * intervaltree.h
+ * prototypes for intervaltree.c.
+ *
+ * Contains the structures and functions used to implement an interval
+ * tree using red-black-trees as described in the book
+ * "Introduction To Algorithms" by Cormen, Leisserson, and Rivest.
+ *
+ * $PostgreSQL: pgsql/src/include/utils/intervaltree.h
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#ifndef INTERVALTREE_H_
+#define INTERVALTREE_H_
+
+#include "nodes/relation.h"
+
+/****** Definition and functions for ConstInterval ******/
+
+/*
+ * Represents an interval of Const structures. This interval could be
+ * open, closed or partially open. It could also be one sided or
+ * represent the entire domain.
+ */
+typedef struct ConstInterval {
+ Const *low; /* The low boundary */
+ bool low_closed; /* Is the low boundary closed? */
+ Const *high; /* The high boundary */
+ bool high_closed; /* Is the high boundary closed? */
+
+ RelOptInfo *rel; /* The data for this interval - a relation */
+
+} ConstInterval;
+
+
+extern bool const_less_than(Const *a, Const *b, bool strict);
+
+extern ConstInterval *create_inf_interval(RelOptInfo *rel);
+extern ConstInterval *create_interval(RelOptInfo *rel,
+ Const *low, bool low_closed,
+ Const *high, bool high_closed);
+extern ConstInterval *copy_interval(ConstInterval *interval);
+
+extern void set_interval_low_point(ConstInterval *interval,
+ Const *low, bool low_closed);
+extern void set_interval_high_point(ConstInterval *interval,
+ Const *high, bool high_closed);
+
+extern bool interval_overlap(ConstInterval *a, ConstInterval *b);
+extern bool is_interval_inf(ConstInterval *interval);
+extern bool is_any_interval_inf(List *interval_list);
+
+extern List *get_intervals_from_constraints(RelOptInfo *rel,
+ Var *target_var);
+
+
+/****** Definition and functions for IntervalTreeNode ******/
+
+/*
+ * Represents an Interval Tree node. It contains pointers to the actual
+ * interval, the child nodes and the parent node.
+ */
+typedef struct IntervalTreeNode {
+ ConstInterval *storedInterval; /* The actual interval */
+ Const *key; /* The key used in the tree - the low value */
+ Const *high; /* The high value of the interval */
+ Const *maxHigh; /* The maximum high boundary of the subtree */
+ bool red; /* If red == false then the node is black */
+ struct IntervalTreeNode *left; /* The left tree node */
+ struct IntervalTreeNode *right; /* The right tree node */
+ struct IntervalTreeNode *parent; /* The parent tree node */
+
+} IntervalTreeNode;
+
+
+extern IntervalTreeNode *it_create_interval_tree_node(ConstInterval *newInterval);
+
+
+/****** Definition and functions for IntervalTree ******/
+
+/*
+ * Represents an interval tree.
+ *
+ * A sentinel is used for root and for nil. These sentinels are created
+ * when it_create_interval_tree is called. root->left should always point to
+ * the node which is the root of the tree. nil points to a node which
+ * should always be black but has arbitrary children and parent and no
+ * key or info. The point of using these sentinels is so that the root
+ * and nil nodes do not require special cases in the code
+ */
+typedef struct IntervalTree {
+ IntervalTreeNode *root; /* The root node of the tree */
+ IntervalTreeNode *nil; /* Represents a nil node */
+
+} IntervalTree;
+
+
+extern IntervalTree *it_create_interval_tree(void);
+
+extern void it_destroy_interval_tree(IntervalTree *tree, bool deep);
+
+extern bool it_is_interval_tree_empty(IntervalTree *tree);
+
+extern IntervalTreeNode *it_insert_interval(IntervalTree *tree,
+ ConstInterval *interval);
+extern ConstInterval *it_delete_interval(IntervalTree *tree,
+ ConstInterval *interval);
+extern ConstInterval *it_delete_interval_tree_node(IntervalTree *tree,
+ IntervalTreeNode* node);
+
+extern List *it_get_overlaping_intervals(IntervalTree *tree,
+ ConstInterval *interval);
+extern List *it_get_left_overlaping_intervals(IntervalTree *tree,
+ ConstInterval *interval,
+ bool strict);
+extern List *it_get_right_overlaping_intervals(IntervalTree *tree,
+ ConstInterval *interval,
+ bool strict);
+
+extern IntervalTreeNode *it_get_successor_of(IntervalTree *tree,
+ IntervalTreeNode *node);
+extern IntervalTreeNode *it_get_predecessor_of(IntervalTree *tree,
+ IntervalTreeNode *node);
+
+
+
+#endif /* INTERVALTREE_H_ */
Index: src/backend/optimizer/path/joininheritance.c
===================================================================
RCS file: src/backend/optimizer/path/joininheritance.c
diff -N src/backend/optimizer/path/joininheritance.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/backend/optimizer/path/joininheritance.c 1 Jan 1970 00:00:00 -0000
@@ -0,0 +1,1444 @@
+/*-------------------------------------------------------------------------
+ *
+ * joininheritance.c
+ * Routines to handle join inheritance.
+ *
+ *
+ *
+ * IDENTIFICATION
+ * $PostgreSQL: pgsql/src/backend/optimizer/path/joininheritance.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/skey.h"
+#include "optimizer/clauses.h"
+#include "optimizer/cost.h"
+#include "optimizer/joininheritance.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
+#include "optimizer/predtest.h"
+#include "optimizer/plancat.h"
+#include "optimizer/prep.h"
+#include "optimizer/restrictinfo.h"
+#include "optimizer/var.h"
+#include "utils/fmgroids.h"
+#include "utils/intervaltree.h"
+#include "utils/lsyscache.h"
+
+
+/* General option to turn the feature on/off */
+bool join_inheritance = false;
+
+/* Helpful structures for creating the child joins */
+typedef struct childJoin
+{
+ RelOptInfo *join;
+ RelOptInfo *rel1;
+ RelOptInfo *rel2;
+ List *restrictlist;
+} ChildJoin;
+
+typedef struct matchRels
+{
+ RelOptInfo *probing_rel;
+ List *matching_rels;
+ bool match_all;
+} MatchRels;
+
+/* Functions for creating the child join relations */
+
+static List *build_child_join_rels(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *rel1,
+ RelOptInfo *rel2,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist);
+
+static List *get_child_join_rels(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *rel1,
+ RelOptInfo *rel2,
+ List *restrictlist);
+
+
+/* Functions to find child relations matching */
+
+static List *get_matching_child_rels(PlannerInfo *root,
+ RelOptInfo *build_rel,
+ RelOptInfo *probe_rel,
+ List *restrictlist);
+
+static List *get_matching_child_rels_helper(PlannerInfo *root,
+ RelOptInfo *build_rel,
+ RelOptInfo *probe_rel,
+ RestrictInfo *rinfo);
+
+static void matching_list_conjuction(List *l1, List *l2);
+
+static void matching_list_disjuction(List *l1, List *l2);
+
+static List *get_overlaping_intervals(IntervalTree *tree,
+ ConstInterval *interval,
+ StrategyNumber op_strategy);
+
+
+/* Functions to make adjustments from parent join rels to child join rels */
+
+static void adjust_child_join_relation(RelOptInfo *parent_joinrel,
+ RelOptInfo *child_joinrel,
+ List *appinfos);
+
+static List *adjust_child_restrict_list(PlannerInfo *root,
+ List *parent_restrictlist,
+ List *appinfos);
+
+static void adjust_inherited_eq_classes(List *parent_restrictlist,
+ List *child_restrictlist);
+
+
+/* General helper functions */
+
+static bool is_restrictlist_joinable_for_children(List *restrictlist);
+
+static bool is_restrictinfo_joinable_for_children(RestrictInfo *rinfo);
+
+static List *get_app_infos_for_child_rels(PlannerInfo *root,
+ RelOptInfo *childrel);
+
+static Var *get_translated_var(PlannerInfo *root,
+ RelOptInfo *childrel,
+ Var *parent_var);
+
+static bool inherited_equal_vars(Var *var1, Var *var2, List *appInfos);
+
+static int count_inh_equal_vars(List * list1, List *list2, List *appInfos);
+
+static void clean_matching_rels_list(List *matches);
+
+
+/*
+ * can_create_inherited_joins
+ *
+ * Checks whether the join is between two relations with inheritance.
+ * If the join could be pushed to the childrels, return true and
+ * false otherwise.
+ */
+bool
+can_create_inherited_joins(PlannerInfo *root,
+ RelOptInfo* rel1,
+ RelOptInfo* rel2,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist)
+{
+ List *join_vars;
+ List *rel1_vars;
+ List *rel2_vars;
+ ListCell *lc;
+ bool rel1found = false;
+ bool rel2found = false;
+ List *appInfos;
+
+ /* Skip the test if join inheritance is disabled */
+ if (!join_inheritance || constraint_exclusion == CONSTRAINT_EXCLUSION_OFF)
+ return false;
+
+ /* Check for inheritance of the joining tables */
+ if (rel1 == NULL || rel2 == NULL
+ || !rel1->has_children || !rel2->has_children)
+ return false;
+
+ /* We only support inner joins */
+ if (sjinfo->jointype != JOIN_INNER)
+ return false;
+
+ /* Check if the restrict list is joinable for child joins */
+ if (!is_restrictlist_joinable_for_children(restrictlist))
+ return false;
+
+ /*Get all the join condition variables */
+ join_vars = pull_var_clause( (Node *) restrictlist, false );
+
+ /* Check rel1 and rel2 constraints */
+ rel1_vars = pull_var_clause( (Node *) rel1->constraints, false );
+ rel2_vars = pull_var_clause( (Node *) rel2->constraints, false );
+
+ rel1found = count_inh_equal_vars( join_vars, rel1_vars, NULL ) > 0 ;
+ rel2found = count_inh_equal_vars( join_vars, rel2_vars, NULL ) > 0;
+
+ list_free(rel1_vars);
+ list_free(rel2_vars);
+
+ if( !rel1found )
+ {
+ foreach( lc, rel1->children_rels )
+ {
+ RelOptInfo *rel = (RelOptInfo *) lfirst(lc);
+ appInfos = get_app_infos_for_child_rels( root, rel );
+
+ rel1_vars = pull_var_clause( (Node *) rel->constraints, false );
+ rel1found = count_inh_equal_vars( join_vars, rel1_vars, appInfos) > 0;
+
+ list_free(rel1_vars);
+ list_free(appInfos);
+
+ if( rel1found )
+ break;
+ }
+ }
+
+ if( !rel2found )
+ {
+ foreach( lc, rel2->children_rels )
+ {
+ RelOptInfo *rel = (RelOptInfo *) lfirst(lc);
+ appInfos = get_app_infos_for_child_rels( root, rel );
+
+ rel2_vars = pull_var_clause( (Node *) rel->constraints, false );
+ rel2found = count_inh_equal_vars( join_vars, rel2_vars, appInfos) > 0;
+
+ list_free(rel2_vars);
+ list_free(appInfos);
+
+ if( rel2found )
+ break;
+ }
+ }
+
+ list_free( join_vars );
+
+ return rel1found && rel2found;
+}
+
+
+/*
+ * create_inherited_joins
+ *
+ * The main function for creating inherited joins. The two input rels
+ * are expected to contain child relations and are part of joinrel.
+ * This function creates join relations for joining the child
+ * relations together. The sjinfo and the restrictlist of the
+ * parent join is inherited by the children.
+ *
+ * Note: This function should only be called if can_create_inherited_joins
+ * returns true.
+ */
+void
+create_inherited_joins(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *rel1,
+ RelOptInfo *rel2,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist)
+{
+ List *childjoins = NIL;
+ ListCell *lc_childjoin;
+
+ if (joinrel->has_children)
+ {
+ /* We have previously expanded this join */
+ childjoins = get_child_join_rels(root, joinrel, rel1, rel2, restrictlist);
+ }
+ else
+ {
+ /* This is the first time we are considering this join */
+ childjoins = build_child_join_rels(root, joinrel, rel1, rel2, sjinfo, restrictlist);
+ }
+
+ /* Build paths for all the child joins */
+ foreach(lc_childjoin, childjoins)
+ {
+ ChildJoin *childjoin = (ChildJoin *) lfirst(lc_childjoin);
+ RelOptInfo *childjoinrel = childjoin->join;
+
+ /* Set estimates of the joinrel's size. */
+ childjoinrel->width = joinrel->width;
+ set_joinrel_size_estimates(root, childjoinrel,
+ childjoin->rel1, childjoin->rel2, sjinfo, childjoin->restrictlist);
+
+ /* Consider all paths for this particular join */
+ make_paths_for_join_rel(root, childjoinrel,
+ childjoin->rel1, childjoin->rel2, sjinfo, childjoin->restrictlist);
+ }
+
+ /* The list is allocated either in get_child_join_rels() or build_child_join_rels() */
+ list_free_deep(childjoins);
+}
+
+
+/*
+ * add_inherited_append_path
+ *
+ * If the join relation has child join relations, we find the best
+ * path for each child join and create an append path that
+ * unions all the best paths of the children.
+ */
+extern void add_inherited_append_path(RelOptInfo *joinrel)
+{
+ List *childpaths = NIL;
+ ListCell *lc_childrel;
+
+ if (joinrel->has_children == false)
+ return;
+
+ /* Find and save the cheapest paths for the child relations */
+ foreach(lc_childrel, joinrel->children_rels)
+ {
+ RelOptInfo *childrel = (RelOptInfo *) lfirst(lc_childrel);
+
+ set_cheapest(childrel);
+ childpaths = lappend(childpaths, childrel->cheapest_total_path);
+ }
+
+ /* Build and add the append path in the join rel */
+ if (childpaths == NIL)
+ mark_dummy_rel(joinrel);
+ else
+ add_path(joinrel, (Path *) create_append_path(joinrel, childpaths));
+}
+
+
+/********* Functions for creating the child join relations ***********/
+
+/*
+ * build_child_join_rels
+ *
+ * This functions is responsible for figuring out which child joins will
+ * produce tuples and create RelOptInfo objects for them. It creates
+ * and returns a list of ChildJoin objects which contain the child join
+ * rel, the two rels that are joined to create that child join, and
+ * the adjusted restrict info list for the child join.
+ */
+static List *
+build_child_join_rels(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *rel1,
+ RelOptInfo *rel2,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist)
+{
+ List *childjoins = NIL; /* List of ChildJoin objects */
+ List *matches = NIL; /* List of MatchRels objects */
+ RelOptInfo *build_rel;
+ RelOptInfo *probe_rel;
+ ListCell *lc_match;
+
+ /* Select build and probe rels */
+ if (list_length(rel1->children_rels) < list_length(rel2->children_rels))
+ {
+ build_rel = rel1;
+ probe_rel = rel2;
+ }
+ else
+ {
+ build_rel = rel2;
+ probe_rel = rel1;
+ }
+
+ /* Get all the matching relations */
+ matches = get_matching_child_rels(root, build_rel, probe_rel, restrictlist);
+
+ foreach(lc_match, matches)
+ {
+ MatchRels *match = (MatchRels *) lfirst(lc_match);
+ RelOptInfo *probing_rel;
+ List *matching_rels;
+ ListCell *lc_matching_rel;
+
+ probing_rel = match->probing_rel;
+
+ /* Get the matching rels */
+ if (match->match_all)
+ matching_rels = build_rel->children_rels;
+ else
+ matching_rels = match->matching_rels;
+
+ /* Create all child join relations that can be joined */
+ foreach(lc_matching_rel, matching_rels)
+ {
+ RelOptInfo *matching_rel = (RelOptInfo *) lfirst(lc_matching_rel);
+ RelOptInfo *childjoinrel;
+ List *childrestrictlist;
+ Relids joinrelids;
+ ChildJoin *childjoin;
+ List *appinfos = NIL;
+
+ /* We should never try to join two overlapping sets of rels. */
+ Assert(!bms_overlap(probing_rel->relids, matching_rel->relids));
+
+ /* Construct Relids set that identifies the joinrel. */
+ joinrelids = bms_union(probing_rel->relids, matching_rel->relids);
+
+ /* Build the join RelOptInfo */
+ childjoinrel = build_join_rel(root, joinrelids,
+ probing_rel, matching_rel, sjinfo, NULL);
+
+ /* Add the app infos for all the child relations into the list */
+ appinfos = list_concat_unique_ptr(appinfos,
+ get_app_infos_for_child_rels(root, probing_rel));
+ appinfos = list_concat_unique_ptr(appinfos,
+ get_app_infos_for_child_rels(root, matching_rel));
+
+ /* Adjust the child rel and the child restrict list */
+ adjust_child_join_relation(joinrel, childjoinrel, appinfos);
+ childrestrictlist = adjust_child_restrict_list(root, restrictlist, appinfos);
+
+ /* The constraints of the joins is simply the union of the child constraints */
+ childjoinrel->constraints = list_concat(childjoinrel->constraints,
+ list_copy(probing_rel->constraints));
+ childjoinrel->constraints = list_concat(childjoinrel->constraints,
+ list_copy(matching_rel->constraints));
+
+ /* Keep track of this child join */
+ joinrel->has_children = true;
+ joinrel->children_rels = lappend(joinrel->children_rels, childjoinrel);
+
+ childjoin = (ChildJoin *) palloc(sizeof(ChildJoin));
+ childjoin->join = childjoinrel;
+ childjoin->rel1 = probing_rel;
+ childjoin->rel2 = matching_rel;
+ childjoin->restrictlist = childrestrictlist;
+
+ childjoins = lappend(childjoins, childjoin);
+
+ /* Clean up */
+ bms_free(joinrelids);
+ list_free(appinfos);
+ }
+ }
+
+ /* Clean up */
+ clean_matching_rels_list(matches);
+
+ return childjoins;
+}
+
+
+/*
+ * get_child_join_rels
+ *
+ * This function is called when we already know the child join rels
+ * that will produce tuples. These child join rels are the children
+ * of the join rel. What we need to do here is to figure out which
+ * rels from rel1 and rel2 are used to create each one of them.
+ *
+ * The function creates and returns a list of ChildJoin objects
+ * which contain the child join rel, the two rels that are joined
+ * to create that child join, and the adjusted restrict info list
+ * for the child join.
+ */
+static List *
+get_child_join_rels(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *rel1,
+ RelOptInfo *rel2,
+ List *restrictlist)
+{
+ List *childjoins = NIL;
+ ListCell *lc_join_child;
+ ListCell *lc_rel1_child;
+ ListCell *lc_rel2_child;
+
+ /* Traverse the child join rels to find their child rels */
+ foreach(lc_join_child, joinrel->children_rels)
+ {
+ RelOptInfo *childjoinrel = (RelOptInfo *) lfirst(lc_join_child);
+ RelOptInfo *rel1_childrel = NULL;
+ RelOptInfo *rel2_childrel = NULL;
+ List *childrestrictlist = NIL;
+ List *appinfos = NIL;
+ ChildJoin *childjoin;
+
+ if (is_dummy_rel(childjoinrel))
+ continue;
+
+ /* Find the first child rel */
+ foreach(lc_rel1_child, rel1->children_rels)
+ {
+ RelOptInfo *rel1_child = (RelOptInfo *) lfirst(lc_rel1_child);
+
+ if (bms_is_subset(rel1_child->relids, childjoinrel->relids))
+ {
+ rel1_childrel = rel1_child;
+ break;
+ }
+ }
+
+ /* Find the second child rel */
+ foreach(lc_rel2_child, rel2->children_rels)
+ {
+ RelOptInfo *rel2_child = (RelOptInfo *) lfirst(lc_rel2_child);
+
+ if (bms_is_subset(rel2_child->relids, childjoinrel->relids))
+ {
+ rel2_childrel = rel2_child;
+ break;
+ }
+ }
+
+ if (rel1_childrel == NULL || rel2_childrel == NULL)
+ continue;
+
+ /* Add the app infos for all the child relations into the list */
+ appinfos = list_concat_unique_ptr(appinfos,
+ get_app_infos_for_child_rels(root, rel1_childrel));
+ appinfos = list_concat_unique_ptr(appinfos,
+ get_app_infos_for_child_rels(root, rel2_childrel));
+
+ /* Adjust the child restrict list */
+ childrestrictlist = adjust_child_restrict_list(root, restrictlist, appinfos);
+
+ /* Record this child join */
+ childjoin = (ChildJoin *) palloc(sizeof(ChildJoin));
+ childjoin->join = childjoinrel;
+ childjoin->rel1 = rel1_childrel;
+ childjoin->rel2 = rel2_childrel;
+ childjoin->restrictlist = childrestrictlist;
+
+ childjoins = lappend(childjoins, childjoin);
+
+ /* Clean up */
+ list_free(appinfos);
+ }
+
+ return childjoins;
+}
+
+
+
+/************** Functions to find child relations matching **************/
+
+
+/*
+ * get_matching_child_rels
+ *
+ * Given a list of restrict info, this function will find and return
+ * which child relations from the two input relations can join with
+ * each other. The actual algorithmic details are described in
+ * get_matching_child_rels_helper. This function is responsible
+ * for traversing the list of restrict infos (which could
+ * represent an expression of ANDs and ORs) and adjusting the
+ * matching results accordingly.
+ *
+ * For example, supposed that based on one restrict info R1 can
+ * join S1, and based on another restrict info R1 can join S1 and S2.
+ * If the two restrict infos are ANDed together, then we induce that
+ * R1 can only join S1. If the two restrict infos are ORed together,
+ * then we induce that R1 can join both S1 and S2.
+ */
+static List *
+get_matching_child_rels(PlannerInfo *root,
+ RelOptInfo *build_rel,
+ RelOptInfo *probe_rel,
+ List *restrictlist)
+{
+ List *result = NIL; /* List of MatchRels objects */
+ ListCell *lc_rinfo;
+
+ foreach(lc_rinfo, restrictlist)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *)lfirst(lc_rinfo);
+ List *partial_results = NIL;
+
+ if (is_opclause(rinfo->clause))
+ {
+ /* The clause is a simple binary expression */
+ partial_results = get_matching_child_rels_helper(root,
+ build_rel, probe_rel, rinfo);
+ }
+ else if (restriction_is_or_clause(rinfo))
+ {
+ ListCell *lc_orarg;
+
+ /* Go through all the OR arguments from the args list */
+ foreach (lc_orarg, ((BoolExpr *) rinfo->orclause)->args)
+ {
+ List *or_matches = NIL;
+ Node *orarg = (Node *) lfirst(lc_orarg);
+
+ /* OR arguments should be ANDs or sub-RestrictInfos */
+ if (and_clause(orarg))
+ or_matches = get_matching_child_rels(root,
+ build_rel, probe_rel, ((BoolExpr *) orarg)->args);
+ else if (IsA(orarg, RestrictInfo))
+ or_matches = get_matching_child_rels_helper(root,
+ build_rel, probe_rel, (RestrictInfo *) orarg);
+
+ if (or_matches == NIL)
+ {
+ /* Something went wrong */
+ clean_matching_rels_list(partial_results);
+ clean_matching_rels_list(result);
+ return NIL;
+ }
+
+ if (partial_results == NIL)
+ {
+ /* First OR result */
+ partial_results = or_matches;
+ }
+ else
+ {
+ /* We need to OR the two lists together */
+ matching_list_disjuction(partial_results, or_matches);
+
+ /* We don't need matches anymore */
+ clean_matching_rels_list(or_matches);
+ }
+ }
+ }
+ else
+ {
+ clean_matching_rels_list(result);
+ return NIL;
+ }
+
+ /* Integrate the partial results with the total results */
+ if (partial_results == NIL)
+ {
+ clean_matching_rels_list(result);
+ return NIL; /* Something went wrong */
+ }
+
+ if (result == NIL)
+ {
+ /* First result */
+ result = partial_results;
+ }
+ else
+ {
+ /* We need to AND the two lists together */
+ matching_list_conjuction(result, partial_results);
+
+ /* We don't need matches anymore */
+ clean_matching_rels_list(partial_results);
+ }
+ }
+
+ return result;
+}
+
+
+/*
+ * get_matching_child_rels_helper
+ *
+ * This function implements the main matching algorithm between the child
+ * relations of the two input relations.
+ *
+ * Input:
+ * build_rel - the constraints from the child relations of this relation
+ * will be used to create an interval tree.
+ * probe_rel - the constraints from the child relations of this relation
+ * will be used to probe the interval tree.
+ * rinfo - the restrict info for this join. It is expected to represent
+ * a binary expression between two Vars that correspond to
+ * the two input relations.
+ *
+ * Output:
+ * A list of MatchRels objects. Each object represents the triple
+ * .
+ * If the match_all flag is set, the matching_rels list is set to NIL
+ * and shows that the probing child rel matches all build child rels.
+ *
+ * Algorithm:
+ * The child relations of the build_rel are traversed and intervals are
+ * created based on their constraints. Those intervals are inserted into
+ * the interval tree in NlogN time, where N is the number of intervals.
+ * This child relations of the probe_rel are traversed and intervals are
+ * created based on their constraints. Those intervals are used to probe
+ * the interval tree and find the overlapping intervals from the tree.
+ * Probing takes a total of O(M*max(N,k*log(N))), where M is the number
+ * of probing intervals and k the number of matching intervals.
+ *
+ * Optimization:
+ * If the build intervals represent (-inf, inf) they are not placed into
+ * the tree (even though it could handle them). Instead, the corresponding
+ * relations are placed in a separate list for faster look up.
+ */
+static List *
+get_matching_child_rels_helper(PlannerInfo *root,
+ RelOptInfo *build_rel,
+ RelOptInfo *probe_rel,
+ RestrictInfo *rinfo)
+{
+ List *result = NIL; /* List of MatchRels objects */
+ List *all_matching_rels = NIL; /* List of rels that join with all other rels */
+ IntervalTree *tree; /* Interval tree for the build rel */
+
+ OpExpr *rinfo_clause;
+ Node *leftop;
+ Node *rightop;
+ Var *build_var;
+ Var *probe_var;
+ Oid rinfo_opno;
+ bool build_left;
+ StrategyNumber op_strategy;
+
+ ListCell *lc_build_child;
+ ListCell *lc_probe_child;
+
+ /* The restrict info clause should be a binary operator between two vars */
+ if (!is_opclause(rinfo->clause))
+ return NIL;
+
+ rinfo_clause = (OpExpr *) rinfo->clause;
+ leftop = get_leftop((Expr *) rinfo_clause);
+ rightop = get_rightop((Expr *) rinfo_clause);
+
+ if (!IsA(leftop, Var) || rightop == NULL || !IsA(rightop, Var))
+ return NIL;
+
+ /* Select corresponding build and probe vars */
+ if (bms_is_member(((Var *) leftop)->varno, build_rel->relids) &&
+ bms_is_member(((Var *) rightop)->varno, probe_rel->relids))
+ {
+ build_var = (Var *) leftop;
+ probe_var = (Var *) rightop;
+ build_left = true;
+ }
+ else if (bms_is_member(((Var *) leftop)->varno, probe_rel->relids) &&
+ bms_is_member(((Var *) rightop)->varno, build_rel->relids))
+ {
+ build_var = (Var *) rightop;
+ probe_var = (Var *) leftop;
+ build_left = false;
+ }
+ else
+ {
+ return NIL;
+ }
+
+ /* Get and adjust the rinfo's clause strategy */
+ rinfo_opno = rinfo_clause->opno;
+ if (build_left == false)
+ {
+ /* Commute the operator so that the build is on the left */
+ rinfo_opno = get_commutator(rinfo_opno);
+ if (!OidIsValid(rinfo_opno))
+ return NIL;
+ }
+
+ op_strategy = get_op_optypes_strategy(rinfo_opno, build_var->vartype, probe_var->vartype);
+ if (op_strategy < 1 || op_strategy > 5 )
+ return NIL;
+
+
+ /* Build the interval tree */
+ tree = it_create_interval_tree();
+ foreach(lc_build_child, build_rel->children_rels)
+ {
+ RelOptInfo *build_childrel = (RelOptInfo *) lfirst(lc_build_child);
+ List *intervals;
+ Var *translated_var;
+
+ /* Get the interval and place it in the tree (or list) */
+ translated_var = get_translated_var(root, build_childrel, build_var);
+ intervals = get_intervals_from_constraints(build_childrel, translated_var);
+
+ if (is_any_interval_inf(intervals))
+ {
+ /* Some interval represents the entire domain,
+ * so it will match all other rels */
+ all_matching_rels = lappend(all_matching_rels, build_childrel);
+ list_free_deep(intervals); /* not needed */
+ }
+ else
+ {
+ /* Insert the intervals into the tree */
+ ListCell *lc_interval;
+
+ foreach(lc_interval, intervals)
+ {
+ /* Insert each interval into the tree */
+ ConstInterval *interval = (ConstInterval *) lfirst(lc_interval);
+ it_insert_interval(tree, interval);
+ }
+
+ list_free(intervals);
+ }
+ }
+
+ /* Probe the interval tree */
+ foreach(lc_probe_child, probe_rel->children_rels)
+ {
+ RelOptInfo *probe_childrel = (RelOptInfo *) lfirst(lc_probe_child);
+
+ /* Record the matching results in a MatchRels object */
+ MatchRels *match_rels = (MatchRels *) palloc(sizeof(MatchRels));
+ match_rels->probing_rel = probe_childrel;
+ match_rels->matching_rels = NIL;
+
+ if (it_is_interval_tree_empty(tree))
+ {
+ /* If the interval tree is empty, then everything matches */
+ match_rels->match_all = true;
+ }
+ else
+ {
+ List *intervals;
+ Var *translated_var;
+
+ /* Get the probing interval */
+ translated_var = get_translated_var(root, probe_childrel, probe_var);
+ intervals = get_intervals_from_constraints(probe_childrel, translated_var);
+
+ if (is_any_interval_inf(intervals))
+ {
+ /* Everything matches */
+ match_rels->match_all = true;
+ }
+ else
+ {
+ List *matching_rels = NIL;
+ List *overlaps = NIL;
+ ListCell *lc_overlap;
+ ListCell *lc_interval;
+
+ /* Go through all probing intervals */
+ foreach(lc_interval, intervals)
+ {
+ ConstInterval *interval = (ConstInterval *) lfirst(lc_interval);
+
+ /* Get the overlapping intervals */
+ overlaps = get_overlaping_intervals(tree, interval, op_strategy);
+
+ foreach(lc_overlap, overlaps)
+ {
+ ConstInterval *overlap = (ConstInterval *) lfirst(lc_overlap);
+ matching_rels = list_append_unique_ptr(matching_rels, overlap->rel);
+ }
+ }
+
+ /* Add the rels that match with everything */
+ matching_rels = list_concat(matching_rels, list_copy(all_matching_rels));
+
+ match_rels->matching_rels = matching_rels;
+ match_rels->match_all = false;
+
+ list_free(overlaps);
+ }
+
+ /* Clean up */
+ list_free(intervals);
+ }
+
+ result = lappend(result, match_rels);
+ }
+
+ /* Clean up */
+ it_destroy_interval_tree(tree, true);
+ list_free(all_matching_rels);
+
+ return result;
+}
+
+
+/*
+ * matching_list_conjuction
+ *
+ * The two input lists should be two parallel lists of MatchRels object.
+ * For each pair of MatchRels objects, the matching_rels lists are
+ * conjucted together.
+ *
+ * Note that l1 is destructively modified to include the conjuctive list.
+ * This method could be more general and return a new list but it seem
+ * wasteful to allocate and deallocate so much memory.
+ */
+static void
+matching_list_conjuction(List *l1, List *l2)
+{
+ ListCell *lc_match1;
+ ListCell *lc_match2;
+
+ if (l1 == NIL || l2 == NIL)
+ return;
+
+ forboth(lc_match1, l1, lc_match2, l2)
+ {
+ MatchRels *match1 = (MatchRels *) lfirst(lc_match1);
+ MatchRels *match2 = (MatchRels *) lfirst(lc_match2);
+
+ if (match1->match_all)
+ {
+ /* New match is simply match2 */
+ match1->matching_rels = list_copy(match2->matching_rels);
+ match1->match_all = match2->match_all;
+ }
+ else if (match2->match_all)
+ {
+ /* New match is simply match1 - nothing to do */
+ }
+ else
+ {
+ List *new_matching_rels = NIL;
+ ListCell *lc_matchrel1;
+ ListCell *lc_matchrel2;
+
+ /* We need the intersection of the two lists */
+ if (match1->matching_rels != NIL && match2->matching_rels != NIL)
+ {
+ foreach (lc_matchrel1, match1->matching_rels)
+ {
+ RelOptInfo *rel1 = (RelOptInfo *) lfirst(lc_matchrel1);
+
+ foreach (lc_matchrel2, match2->matching_rels)
+ {
+ RelOptInfo *rel2 = (RelOptInfo *) lfirst(lc_matchrel2);
+
+ if (rel1 == rel2)
+ {
+ /* Found a match. No need to append unique since both lists
+ * have unique rels */
+ new_matching_rels = lappend(new_matching_rels, rel1);
+ continue;
+ }
+ }
+ }
+ }
+
+ /* Set the new list of matching rels */
+ list_free(match1->matching_rels);
+ match1->matching_rels = new_matching_rels;
+
+ } /* End else */
+ } /* End forboth */
+}
+
+
+/*
+ * matching_list_disjuction
+ *
+ * The two input lists should be two parallel lists of MatchRels object.
+ * For each pair of MatchRels objects, the matching_rels lists are
+ * disjucted together.
+ *
+ * Note that l1 is destructively modified to include the disjuctive list.
+ * This method could be more general and return a new list but it seem
+ * wasteful to allocate and deallocate so much memory.
+ */
+static void
+matching_list_disjuction(List *l1, List *l2)
+{
+ ListCell *lc_match1;
+ ListCell *lc_match2;
+
+ if (l1 == NIL || l2 == NIL)
+ return;
+
+ forboth(lc_match1, l1, lc_match2, l2)
+ {
+ MatchRels *match1 = (MatchRels *) lfirst(lc_match1);
+ MatchRels *match2 = (MatchRels *) lfirst(lc_match2);
+
+ if (match1->match_all)
+ {
+ /* Matching all overules - nothing to do */
+ }
+ else if (match2->match_all)
+ {
+ /* match1 (which is the resulting match) now matches all */
+ list_free(match1->matching_rels);
+ match1->matching_rels = NIL;
+ match1->match_all = true;
+ }
+ else
+ {
+ /* We need the union of the two lists */
+ match1->matching_rels = list_concat_unique_ptr(match1->matching_rels,
+ match2->matching_rels);
+ }
+ } /* End forboth */
+}
+
+
+/*
+ * get_overlaping_intervals
+ *
+ * Returns a list with intervals from the tree that "overlap" with the input
+ * interval. Overlapping depends on the op_strategy, which is assumed to
+ * refer to the build side been the left.
+ *
+ * For example, if op_strategy is "=", then this function returns the intervals
+ * from the tree that overlap with the input interval. If the op_strategy is "<",
+ * then this function returns all intervals from the tree that could be to the
+ * left of the input interval.
+ */
+static List *
+get_overlaping_intervals(IntervalTree *tree,
+ ConstInterval *interval,
+ StrategyNumber op_strategy)
+{
+ List *results = NIL;
+
+ switch (op_strategy) {
+ case BTLessStrategyNumber:
+ results = it_get_left_overlaping_intervals(tree, interval, true);
+ break;
+
+ case BTLessEqualStrategyNumber:
+ results = it_get_left_overlaping_intervals(tree, interval, false);
+ break;
+
+ case BTEqualStrategyNumber:
+ results = it_get_overlaping_intervals(tree, interval);
+ break;
+
+ case BTGreaterEqualStrategyNumber:
+ results = it_get_right_overlaping_intervals(tree, interval, false);
+ break;
+
+ case BTGreaterStrategyNumber:
+ results = it_get_right_overlaping_intervals(tree, interval, true);
+ break;
+
+ default:
+ break;
+ } /* End switch statement on op_strategy */
+
+ return results;
+}
+
+
+/* Functions to make adjustments from parent join rels to child join rels */
+
+/*
+ * adjust_child_join_relation
+ *
+ * Adjust the attributes in several lists in the new child join relation.
+ *
+ * The parent_joinrel is needed to adjust the different attributes.
+ * The list of AppendRelInfo's is needed to map the attributes from the
+ * parent to the child.
+ */
+static void
+adjust_child_join_relation(RelOptInfo *parent_joinrel,
+ RelOptInfo *child_joinrel,
+ List *appinfos)
+{
+ AppendRelInfo *appinfo;
+ ListCell *lc_app;
+
+ Assert(list_length(appinfos) != 0);
+
+ /*
+ * We need to adjust all the child lists based on the corresponding
+ * parent lists. First, we make the adjustments using the first
+ * AppendRelInfo and the parent lsits.
+ */
+ lc_app = list_head(appinfos);
+ appinfo = (AppendRelInfo *) lfirst(lc_app);
+
+ child_joinrel->baserestrictinfo = (List *)
+ adjust_appendrel_attrs((Node *) parent_joinrel->baserestrictinfo, appinfo);
+ child_joinrel->joininfo = (List *)
+ adjust_appendrel_attrs((Node *) parent_joinrel->joininfo, appinfo);
+ child_joinrel->reltargetlist = (List *)
+ adjust_appendrel_attrs((Node *) parent_joinrel->reltargetlist, appinfo);
+
+ /*
+ * Adjusting makes a deep copy of the lists. Hence, for the remaining
+ * AppendRelInfo's, we create temp lists to adjust and then clear them out.
+ */
+ lc_app = ((lc_app)->next);
+ while (lc_app != ((void *)0))
+ {
+ List *temp_baserestrictinfo = child_joinrel->baserestrictinfo;
+ List *temp_joininfo = child_joinrel->joininfo;
+ List *temp_reltargetlist = child_joinrel->reltargetlist;
+
+ appinfo = (AppendRelInfo *) lfirst(lc_app);
+
+ /* Make the adjustments */
+ child_joinrel->baserestrictinfo = (List *)
+ adjust_appendrel_attrs((Node *) temp_baserestrictinfo, appinfo);
+ child_joinrel->joininfo = (List *)
+ adjust_appendrel_attrs((Node *) temp_joininfo, appinfo);
+ child_joinrel->reltargetlist = (List *)
+ adjust_appendrel_attrs((Node *) temp_reltargetlist, appinfo);
+
+ /* Clear the temp lists */
+ list_free_deep(temp_baserestrictinfo);
+ list_free_deep(temp_joininfo);
+ list_free_deep(temp_reltargetlist);
+
+ lc_app = ((lc_app)->next);
+ }
+}
+
+/*
+ * adjust_child_restrict_list
+ *
+ * Adjust the restrict list of the child join based on the
+ * parent_restrictlist. It also takes care of any equivalence relations.
+ *
+ * The list of AppendRelInfo's is needed to map the attributes from
+ * the parent to the child.
+ *
+ * It returns a new list with the adjusted restrict list.
+ */
+static List *
+adjust_child_restrict_list(PlannerInfo *root,
+ List *parent_restrictlist,
+ List *appinfos)
+{
+ List *child_restrictlist = NIL;
+ AppendRelInfo *appinfo;
+ ListCell *lc_app;
+
+ Assert(list_length(appinfos) != 0);
+
+ /*
+ * First, we adjust the restrict list using the first AppendRelInfo
+ * and the parent lsit.
+ */
+ lc_app = list_head(appinfos);
+ appinfo = (AppendRelInfo *) lfirst(lc_app);
+ child_restrictlist = (List *)
+ adjust_appendrel_attrs((Node *) parent_restrictlist, appinfo);
+
+ /*
+ * Adjusting makes a deep copy of the lists. Hence, for the remaining
+ * AppendRelInfo's, we create temp lists to adjust and then clear them out.
+ */
+ lc_app = ((lc_app)->next);
+ while (lc_app != ((void *)0))
+ {
+ List *temp_restrictlist = child_restrictlist;
+ appinfo = (AppendRelInfo *) lfirst(lc_app);
+
+ child_restrictlist = (List *)
+ adjust_appendrel_attrs((Node *) temp_restrictlist, appinfo);
+
+ list_free_deep(temp_restrictlist);
+ lc_app = ((lc_app)->next);
+ }
+
+ /* We also need to process the equivalence classes for the child relation */
+ adjust_inherited_eq_classes(parent_restrictlist, child_restrictlist);
+
+ return child_restrictlist;
+}
+
+
+/*
+ * adjust_inherited_eq_classes
+ *
+ * This functions takes in a restrict list for the parent join and one for
+ * the child join. They are expected to have the exact same structure. It
+ * traverses the child restrict infos and adjusts the children's equivalence
+ * members and classes.
+ */
+static void
+adjust_inherited_eq_classes(List *parent_restrictlist,
+ List *child_restrictlist)
+{
+ ListCell *lc_parent_rinfo;
+ ListCell *lc_child_rinfo;
+
+ /* The two lists should have the same structure */
+ Assert(list_length(parent_restrictlist) == list_length(child_restrictlist));
+
+ /* Traverse the two lists in parallel */
+ forboth(lc_parent_rinfo, parent_restrictlist,
+ lc_child_rinfo, child_restrictlist)
+ {
+ RestrictInfo *parent_rinfo = (RestrictInfo *)lfirst(lc_parent_rinfo);
+ RestrictInfo *child_rinfo = (RestrictInfo *)lfirst(lc_child_rinfo);
+
+ /* Only rinfo with op clauses can have equivalence relations */
+ if (is_opclause(child_rinfo->clause))
+ {
+ ListCell *lc_member;
+
+ /* Adjust the left equivalence class */
+ if (parent_rinfo->left_ec != NULL)
+ {
+ Node *left = get_leftop(child_rinfo->clause);
+ child_rinfo->left_ec = parent_rinfo->left_ec;
+
+ /* Find the left equivalence member */
+ foreach(lc_member, child_rinfo->left_ec->ec_members)
+ {
+ EquivalenceMember *member = (EquivalenceMember *)lfirst(lc_member);
+ if (equal(left, member->em_expr))
+ {
+ child_rinfo->left_em = member;
+ break;
+ }
+ }
+ }
+
+ /* Adjust the right equivalence class */
+ if (parent_rinfo->right_ec != NULL)
+ {
+ Node *right = get_rightop(child_rinfo->clause);
+ child_rinfo->right_ec = parent_rinfo->right_ec;
+
+ /* Find the right equivalence member */
+ foreach(lc_member, child_rinfo->right_ec->ec_members)
+ {
+ EquivalenceMember *member = (EquivalenceMember *)lfirst(lc_member);
+ if (equal(right, member->em_expr))
+ {
+ child_rinfo->right_em = member;
+ break;
+ }
+ }
+ }
+ } // End if opclause
+ } // End forboth loop
+
+}
+
+
+/********************* General helper functions **************************/
+
+/*
+ * is_restrictlist_joinable_for_children
+ *
+ * Check to see if the restrict list is joinable for child joins. A list
+ * is joinable if each restrict info is joinable. A restrict info is joinable
+ * if it represents an operator expresion (opexpr) between two variables
+ * (Var nodes).
+ */
+static bool
+is_restrictlist_joinable_for_children(List *restrictlist)
+{
+ ListCell *lc_rinfo;
+
+ foreach(lc_rinfo, restrictlist)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *)lfirst(lc_rinfo);
+
+ /* If a single rinfo is not joinable, then the whole list is not */
+ if (!is_restrictinfo_joinable_for_children(rinfo))
+ return false;
+ }
+
+ /* All rinfo in the list are joinable */
+ return true;
+}
+
+
+/*
+ * is_restrictinfo_joinable_for_children
+ *
+ * Check to see if the restrict info is joinable for child joins.
+ * A restrict info is joinable if it represents an operator
+ * expresion (opexpr) between two variables (Var nodes).
+ */
+static bool
+is_restrictinfo_joinable_for_children(RestrictInfo *rinfo)
+{
+ if (is_opclause(rinfo->clause))
+ {
+ Node *left = get_leftop(rinfo->clause);
+ Node *right = get_rightop(rinfo->clause);
+
+ /* The rinfo is joinable iff both arguments are Var nodes */
+ if (left != NULL && right != NULL &&
+ IsA(left, Var) && IsA(right, Var))
+ return true;
+ }
+ else if (restriction_is_or_clause(rinfo))
+ {
+ bool result = false;
+ ListCell *lc_orarg;
+
+ /* Go through all the OR arguments from the args list */
+ foreach (lc_orarg, ((BoolExpr *) rinfo->orclause)->args)
+ {
+ Node *orarg = (Node *) lfirst(lc_orarg);
+
+ /* OR arguments should be ANDs or sub-RestrictInfos */
+ if (and_clause(orarg))
+ result = is_restrictlist_joinable_for_children(((BoolExpr *) orarg)->args);
+ else if (IsA(orarg, RestrictInfo))
+ result = is_restrictinfo_joinable_for_children((RestrictInfo *) orarg);
+ else
+ result = false;
+
+ /* If a single argument is not joinable,
+ * then the whole OR-clause is not */
+ if (!result)
+ return false;
+ }
+
+ /* All arguments are joinable */
+ return true;
+ }
+
+ return false;
+}
+
+
+/*
+ * get_app_infos_for_child_rels
+ *
+ * Get the AppendRelInfo's that correspond to the input childrel.
+ * If childrel is a base relation, then the corresponding
+ * AppendRelInfo is returned. If childrel is a join rel, then
+ * the AppendRelInfo's returned correspond to the child relations
+ * that participate in the join.
+ */
+static List *
+get_app_infos_for_child_rels(PlannerInfo *root, RelOptInfo *childrel)
+{
+ List *appinfos = NIL;
+ ListCell *lc_app;
+
+ /* Find the AppendRelInfo's */
+ foreach(lc_app, root->append_rel_list)
+ {
+ AppendRelInfo *app = (AppendRelInfo *) lfirst(lc_app);
+
+ if(bms_is_member(app->child_relid, childrel->relids))
+ {
+ appinfos = lappend(appinfos, app);
+ }
+ }
+
+ return appinfos;
+}
+
+
+/*
+ * get_translated_var
+ *
+ * Returns the var from the child relation that corresponds to the
+ * parent var.
+ */
+static Var *
+get_translated_var(PlannerInfo *root, RelOptInfo *childrel, Var *parent_var)
+{
+ Var *result = NULL;
+ ListCell *lc_app;
+
+ /* Search for the AppendRelInfo */
+ foreach(lc_app, root->append_rel_list)
+ {
+ AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc_app);
+
+ if(appinfo->parent_relid == parent_var->varno &&
+ bms_is_member(appinfo->child_relid, childrel->relids))
+ {
+ /* Found it, let's get the translated var */
+ AttrNumber index = parent_var->varattno;
+
+ if( index > 0 && index <= list_length(appinfo->translated_vars))
+ {
+ result = (Var *) list_nth(appinfo->translated_vars, index - 1);
+ break;
+ }
+ }
+ }
+
+ return result;
+}
+
+
+/*
+ * inherited_equal_vars
+ *
+ * Check whether the two variable are the same
+ * even in the inheritance case when we have
+ * a mapping in place.
+ *
+ * Note: In the inherited case the second variable should
+ * be the one that will be check for inheritance match.
+ */
+static bool
+inherited_equal_vars(Var *var1, Var *var2, List *appInfos)
+{
+ ListCell *lc;
+ AppendRelInfo *info;
+
+ if ( var1 == NULL || var2 == NULL )
+ return false;
+
+ /* Check the straightforward case */
+ if ( var1 ->varno == var2->varno
+ && var1->varattno == var2->varattno )
+ return true;
+
+ /*
+ * Check the inherited case
+ *
+ * Note: In the inherited case the second variable should
+ * be the one that will be check for inheritance match
+ */
+
+ if( appInfos == NIL )
+ return false;
+
+
+ foreach( lc, appInfos )
+ {
+ info = (AppendRelInfo *) lfirst(lc);
+ if (info->child_relid == var2->varno)
+ {
+ AttrNumber ind = var2->varattno;
+
+ if( ind > 0
+ && ind <= list_length(info->translated_vars)
+ && equal(list_nth(info->translated_vars, ind - 1), var2 )
+ )
+ return true;
+ }
+ }
+
+ return false;
+}
+
+
+/*
+ * count_inh_equal_vars
+ *
+ * Count the number of equal variables in a two list of variables
+ * Note: appInfo is only used by the inherited_equal_vars function
+ */
+static int
+count_inh_equal_vars(List * list1, List *list2, List *appInfos )
+{
+ ListCell *lc1, *lc2;
+ Var *var1, *var2;
+ int result = 0;
+
+ foreach( lc1, list1 )
+ {
+ var1 = (Var *) lfirst(lc1);
+ foreach( lc2, list2 )
+ {
+ var2 = (Var *) lfirst(lc2);
+ if( inherited_equal_vars(var1, var2, appInfos) )
+ result++;
+ }
+ }
+
+ return result;
+}
+
+
+/*
+ * clean_matching_rels_list
+ *
+ * Clears out (deallocates memory) the input list of MatchRels objects.
+ */
+static void
+clean_matching_rels_list(List *matches)
+{
+ ListCell *lc_match;
+
+ if (matches == NULL)
+ return;
+
+ foreach(lc_match, matches)
+ {
+ MatchRels *match = (MatchRels *) lfirst(lc_match);
+ list_free(match->matching_rels);
+ }
+
+ list_free_deep(matches);
+}
+
Index: src/include/optimizer/joininheritance.h
===================================================================
RCS file: src/include/optimizer/joininheritance.h
diff -N src/include/optimizer/joininheritance.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/include/optimizer/joininheritance.h 1 Jan 1970 00:00:00 -0000
@@ -0,0 +1,32 @@
+/*-------------------------------------------------------------------------
+ *
+ * joininheritance.h
+ * prototypes for joininheritance.c.
+ *
+ *
+ * $PostgreSQL: pgsql/src/include/optimizer/joininheritance.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef JOININHERITANCE_H
+#define JOININHERITANCE_H
+
+#include "nodes/relation.h"
+
+
+extern bool can_create_inherited_joins(PlannerInfo *root,
+ RelOptInfo* rel1,
+ RelOptInfo* rel2,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist);
+
+extern void create_inherited_joins(PlannerInfo *root,
+ RelOptInfo *joinrel,
+ RelOptInfo *rel1,
+ RelOptInfo *rel2,
+ SpecialJoinInfo *sjinfo,
+ List *restrictlist);
+
+extern void add_inherited_append_path(RelOptInfo *joinrel);
+
+#endif /* JOININHERITANCE_H */