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 */