Class CardinalityBasedJoinOrderingBase

java.lang.Object
se.liu.ida.hefquin.engine.queryproc.impl.loptimizer.heuristics.CardinalityBasedJoinOrderingBase
All Implemented Interfaces:
HeuristicForLogicalOptimization
Direct Known Subclasses:
CardinalityBasedJoinOrderingWithRequests
public abstract class CardinalityBasedJoinOrderingBase extends Object implements HeuristicForLogicalOptimization
Base class for heuristics that use cardinality estimates to decide on a join order for the subplans of a multiway join or a binary join. The heuristic is applied recursively to all joins within the given plan. The actual join ordering algorithm implemented in this class is a greedy one. It first determines cardinality estimates for all the subplans of the corresponding join. Given these estimates, the algorithm picks the subplan with the lowest cardinality estimate to become the first plan in the join order. Thereafter, the algorithm performs an iteration where each step picks the next subplan for the join. This decision is based on estimated join cardinalities. However, as candidates to be picked as the next subplan, the algorithm considers only the subplans that have a join variable with the subplans that have already been selected so far, which is done to avoid cross products (unless a cross product is unavoidable). The actual cardinality estimation approach, both for the cardinalities of the subplans and for the join cardinalities, may be different for each subclass.

  • Field Details

  • Constructor Details

    • CardinalityBasedJoinOrderingBase

      public CardinalityBasedJoinOrderingBase(QueryProcContext ctxt)

    • CardinalityBasedJoinOrderingBase

      public CardinalityBasedJoinOrderingBase(CardinalityEstimator cardEst)

  • Method Details

    • apply

      public LogicalPlan apply(LogicalPlan inputPlan) throws LogicalOptimizationException
      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
      Throws:
      LogicalOptimizationException

    • _apply

      protected LogicalPlan _apply(LogicalPlan inputPlan) throws LogicalOptimizationException
      Throws:
      LogicalOptimizationException

    • reorder

      protected boolean reorder(LogicalPlan[] plans) throws LogicalOptimizationException
      Changes the order of the subplans in the given array by using the greedy algorithm described above for this class.
      Parameters:
      plans - - the list of plans that should be reordered
      Returns:
      true if the order of the plans in the given list has indeed been changed
      Throws:
      LogicalOptimizationException

    • determineIdxOfSmallestCardinality

      protected int determineIdxOfSmallestCardinality(LogicalPlan[] plans)
      Compares the given plans in terms of their estimated cardinalities and, for the plan that has the smallest estimated cardinality, returns the index of this plan within the given list.

    • determineNextPlan

      protected Pair<LogicalPlan,Integer> determineNextPlan(List<LogicalPlan> selectedPlans, int joinCardOfSelectedPlans, List<LogicalPlan> nextCandidates)
      Returns the plan from the given list of next candidates that has the lowest join cardinality with a plan consisting of the given selected plans, and that join cardinality will be returned as well. The implementation of this function assumes that the given list of next candidates is nonempty.

    • estimateJoinCardinality

      protected abstract int estimateJoinCardinality(List<LogicalPlan> selectedPlans, int joinCardOfSelectedPlans, LogicalPlan nextCandidate)
      Implementations of this function estimate the cardinality of the join between the result of joining the given selected plans and the result of the given next candidate. Implementations that require the individual cardinality estimates for each of the plans can get these estimates by accessing QueryPlan.getQueryPlanningInfo(). The estimated join cardinality of joining the given selected plans is also passed to this function, in case it is needed by some implementation.

    • containsJoinOp

      protected static boolean containsJoinOp(LogicalPlan logicalPlan)
      Recursively checks whether the given logical plan contains any join operators (LogicalOpJoin or LogicalOpMultiwayJoin).

      This method inspects the root operator of the given plan and, if it is neither a LogicalOpJoin nor a LogicalOpMultiwayJoin, it traverses all subplans to perform the same check.

      Parameters:
      logicalPlan - the logical plan to inspect
      Returns:
      true if the plan contains at least one LogicalOpJoin or LogicalOpMultiwayJoin operator, false otherwise