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

Class CardinalityBasedJoinOrderingWithRequests

java.lang.Object

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

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

All Implemented Interfaces:

HeuristicForLogicalOptimization

public class CardinalityBasedJoinOrderingWithRequests
extends CardinalityBasedJoinOrderingBase

This class is an implementation of CardinalityBasedJoinOrderingBase that uses cardinality requests. That is, this class implements the function CardinalityBasedJoinOrderingBase.estimateCardinalities(LogicalPlan[] plans) by, first, issuing cardinality requests for every request operator within each of the given plans; then, for each given plan, the cardinalities for obtained for the corresponding request operators are aggregated. Currently, this aggregation is just a sum, ignoring whether there are filters or l2g operators in the plans. The implementation of the second of the abstract functions of the base class, CardinalityBasedJoinOrderingBase.estimateJoinCardinality(List<AnnotatedLogicalPlan> selectedPlans, int joinCardOfSelectedPlans, AnnotatedLogicalPlan nextCandidate), simply returns the cardinality estimate of the given next candidate subplan. Hence, when deciding which next candidate subplan to add to the join order, this implementation greedily picks the candidate with the lowest cardinality (without considering join cardinalities or anything even more sophisticated). Subclasses may change this behavior. The current implementation of this class assumes that all logical plans under joins (i.e., all plans for which the cardinality needs to be estimated) are either: i) a single request, ii) a filter over a request, iii) an l2g over a request, iv) a filter over an l2g over a request, v) an l2g over a filter over a request, vi) a union over any of the aforementioned options, or vii) an l2g over a union over any of the aforementioned (non-union) options.

Nested Class Summary

Nested classes/interfaces inherited from class se.liu.ida.hefquin.engine.queryproc.impl.loptimizer.heuristics.CardinalityBasedJoinOrderingBase

CardinalityBasedJoinOrderingBase.AnnotatedLogicalPlan

Field Summary

Fields

Modifier and Type	Field	Description
protected final QueryProcContext	ctxt

Constructor Summary

Constructors

Constructor	Description
CardinalityBasedJoinOrderingWithRequests(QueryProcContext ctxt)

Method Summary

Modifier and Type	Method	Description
protected int[]	estimateCardinalities(LogicalPlan[] plans)	Implementations of this function determine or estimate the cardinality of each of the given plans.
protected 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 List<LogicalOpRequest<?,?>>	extractAllRequestOps(LogicalPlan plan)	Extracts all request operators from the given plan such that the resulting list of these operators will be ordered in the order in which the operators can be found by a depth-first traversal of the given plan.
protected List<LogicalOpRequest<?,?>>[]	extractAllRequestOps(LogicalPlan[] plans)	Extracts all request operators from the given list of plans such that, for each of the plans, the resulting list of these operators is ordered in the order in which the operators can be found by a depth-first traversal of the plan.

Methods inherited from class se.liu.ida.hefquin.engine.queryproc.impl.loptimizer.heuristics.CardinalityBasedJoinOrderingBase

apply, determineLowestValue, determineNextPlan, reorder

Methods inherited from class java.lang.Object

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

Field Details

ctxt

protected final QueryProcContext ctxt

Constructor Details

CardinalityBasedJoinOrderingWithRequests

public CardinalityBasedJoinOrderingWithRequests(QueryProcContext ctxt)

Method Details

estimateCardinalities

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

Description copied from class: CardinalityBasedJoinOrderingBase

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.

Specified by:

estimateCardinalities in class CardinalityBasedJoinOrderingBase

Throws:

LogicalOptimizationException

estimateJoinCardinality

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

Description copied from class: CardinalityBasedJoinOrderingBase

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.

Specified by:

estimateJoinCardinality in class CardinalityBasedJoinOrderingBase

extractAllRequestOps

protected List<LogicalOpRequest<?,?>>[] extractAllRequestOps(LogicalPlan[] plans)

Extracts all request operators from the given list of plans such that, for each of the plans, the resulting list of these operators is ordered in the order in which the operators can be found by a depth-first traversal of the plan.

extractAllRequestOps

protected List<LogicalOpRequest<?,?>> extractAllRequestOps(LogicalPlan plan)

Extracts all request operators from the given plan such that the resulting list of these operators will be ordered in the order in which the operators can be found by a depth-first traversal of the given plan.