Package se.liu.ida.hefquin.engine.queryproc.impl.loptimizer.heuristics

Class UnionPullUp

java.lang.Object
se.liu.ida.hefquin.engine.queryproc.impl.loptimizer.heuristics.UnionPullUp
All Implemented Interfaces:
HeuristicForLogicalOptimization
public class UnionPullUp extends Object implements HeuristicForLogicalOptimization
Pulls up all (multiway) union operators in the given plan as high up as possible. The rationale of this heuristics is that it opens more options when doing the join optimization during the physical query optimization. For instance, consider the following plan:
mj( req_fm1^(s,p,?x), mu( req_fm2^(?x,?y,?z), req_fm3^(?x,?y,?z) ) )
In this case, the join can be implemented only by using a local join algorithm (e.g., hash join), which also means that the two requests within the union are executed by physical request operators and, thus, end up retrieving all triples from fm2 and from fm3. In contrast, after pulling up the union operator, the resulting plan is:
mu( mj( req_fm1^(s,p,?x), req_fm2^(?x,?y,?z) ), mj( req_fm1^(s,p,?x), req_fm3^(?x,?y,?z) ) )
Now, the two joins can be turned into bind joins, and it is even possible to pick two different join strategies for them. Attention: It has turned out that UnionPullUp typically does more harm than good, because it has the tendency to turn a join-over-union source assignment into a (multiway) union with many join subplans (in particular for cases in which there are several unions in the join-over-union source assignment, because in these cases every combination of requests under the different unions ends up as a separate join). If, thereafter, these many join subplans are predominantly implemented as symmetric hash joins, then the execution plan will do many more requests than what would be necessary for the joins of the original join-over-union source assignment. An alternative heuristic that does not have this problem is PushJoinUnderUnionWithRequests.

  • Constructor Details

    • UnionPullUp

      public UnionPullUp()

  • Method Details

    • apply

      public LogicalPlan apply(LogicalPlan inputPlan)
      Description copied from interface: HeuristicForLogicalOptimization
      Applies this heuristics to the given plan and returns the resulting, potentially rewritten plan.
      Specified by:
      apply in interface HeuristicForLogicalOptimization

    • hasUnionRoot

      public boolean hasUnionRoot(LogicalPlan plan)

    • rewritePlanWithUnaryRootAndUnionChild

      public LogicalPlan rewritePlanWithUnaryRootAndUnionChild(UnaryLogicalOp rootOp, LogicalPlan subPlan)
      Based on the assumption that the given subplan has a union operator as its root operator, this function pulls up that union by pushing the given unary operator to be the root of each of the children of the union.

    • rewritePlanWithUnionRootAndUnionChild

      public LogicalPlan rewritePlanWithUnionRootAndUnionChild(List<LogicalPlan> plansWithUnionRoot, List<LogicalPlan> plansWithNonUnionRoot)
      Based on the assumptions that i) the plans in the given lists have all been subplans of a union and ii) the given list of union-rooted plans is nonempty, merges all these union-rooted plans (plansWithUnionRoot) into a single union-root plan that has all the subplans of the given union-rooted plans as its subplans, together with all the plans given in the other list (plansWithNonUnionRoot).

    • rewritePlanWithJoinOverUnion

      public LogicalPlan rewritePlanWithJoinOverUnion(List<LogicalPlan> plansWithUnionRoot, List<LogicalPlan> plansWithNonUnionRoot)
      Based on the assumptions that i) the plans in the given lists have all been subplans of a join and ii) the given list of union-rooted plans is nonempty, pulls the unions out of these union-rooted plans by joining all their subplans with one another, and also with all the plans given in the other list (plansWithNonUnionRoot).