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

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.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan	A help class that wraps a LogicalPlan together with some information about this plan that is relevant for the algorithm of the main class (CardinalityBasedJoinOrderingBase and that may be relevant for implementations of the abstract functions.

Constructor Summary

Constructors

Constructor	Description
CardinalityBasedJoinOrderingBase()

Method Summary

Modifier and Type	Method	Description
LogicalPlan	apply(LogicalPlan inputPlan)	Applies this heuristics to the given plan and returns the resulting, potentially rewritten plan.
protected int	determineLowestValue(int[] values)	Determines the smallest of the values in the given array and, then, returns the position of this value in the given array.
protected Pair<CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan,Integer>	determineNextPlan(List<CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan> selectedPlans, int joinCardOfSelectedPlans, List<CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan> 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.
protected abstract int[]	estimateCardinalities(LogicalPlan[] plans)	Implementations of this function determine or estimate the cardinality of each of the given plans.
protected abstract int	estimateJoinCardinality(List<CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan> selectedPlans, int joinCardOfSelectedPlans, CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan 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.
protected void	reorder(LogicalPlan[] plans)	Changes the order of the subplans in the given array by using the greedy algorithm described above for this class.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

CardinalityBasedJoinOrderingBase

public CardinalityBasedJoinOrderingBase()

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

reorder

protected void 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.

Throws:

LogicalOptimizationException

determineLowestValue

protected int determineLowestValue(int[] values)

Determines the smallest of the values in the given array and, then, returns the position of this value in the given array.

determineNextPlan

protected Pair<CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan,Integer> determineNextPlan(List<CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan> selectedPlans,
 int joinCardOfSelectedPlans,
 List<CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan> nextCandidates)
                                                                                         throws LogicalOptimizationException

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.

Throws:

LogicalOptimizationException

estimateCardinalities

protected abstract int[] estimateCardinalities(LogicalPlan[] plans)
                                        throws LogicalOptimizationException

Implementations of this function determine or estimate the cardinality of each of the given plans. That is, the returned array contains as many entries as there are plans in the given array such that the i-th entry in the returned array is the cardinality of the i-th plan.

Throws:

LogicalOptimizationException

estimateJoinCardinality

protected abstract int estimateJoinCardinality(List<CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan> selectedPlans,
 int joinCardOfSelectedPlans,
 CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan nextCandidate)
                                        throws LogicalOptimizationException

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 CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan.cardinality. The estimated join cardinality of joining the given selected plans is also passed to this function, in case it is needed by some implementation.

Throws:

LogicalOptimizationException