Package se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple

Class DPBasedJoinPlanOptimizer

java.lang.Object

se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.JoinPlanOptimizerBase

se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.DPBasedJoinPlanOptimizer

All Implemented Interfaces:

JoinPlanOptimizer

Direct Known Subclasses:

DPBasedBushyJoinPlanOptimizer, DPBasedLinearJoinPlanOptimizer

public abstract class DPBasedJoinPlanOptimizer
extends JoinPlanOptimizerBase

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	DPBasedJoinPlanOptimizer.DynamicProgrammingOptimizerImpl
protected static class	DPBasedJoinPlanOptimizer.OptimalPlansPerStage

Nested classes/interfaces inherited from class se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.JoinPlanOptimizerBase

JoinPlanOptimizerBase.EnumerationAlgorithm

Field Summary

Fields

Modifier and Type	Field	Description
protected final CostModel	costModel

Constructor Summary

Constructors

Constructor	Description
DPBasedJoinPlanOptimizer(CostModel costModel)

Method Summary

Modifier and Type	Method	Description
protected boolean	determineOptimalCandidatesAtStageN(List<List<PhysicalPlan>> subsets, DPBasedJoinPlanOptimizer.OptimalPlansPerStage optPlansPerStage, boolean ignoreCartesianProductJoins)	For each of the sets of plans in 'subsets', determines the best possible join plan and adds this best plan to 'optPlansPerStage'.
protected static <T> List<List<T>>	getAllSubSets(List<T> superset, int n)	This method returns all subsets (with the given size) of the given superset.
protected JoinPlanOptimizerBase.EnumerationAlgorithm	initializeEnumerationAlgorithm(List<PhysicalPlan> subplans)
protected abstract <T> List<Pair<List<T>,List<T>>>	splitIntoSubSets(List<T> superset)

Methods inherited from class se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.JoinPlanOptimizerBase

determineJoinPlan

Methods inherited from class java.lang.Object

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

Methods inherited from interface se.liu.ida.hefquin.engine.queryproc.impl.poptimizer.simple.JoinPlanOptimizer

determineJoinPlan

Field Details

costModel

protected final CostModel costModel

Constructor Details

DPBasedJoinPlanOptimizer

public DPBasedJoinPlanOptimizer(CostModel costModel)

Method Details

initializeEnumerationAlgorithm

protected JoinPlanOptimizerBase.EnumerationAlgorithm initializeEnumerationAlgorithm(List<PhysicalPlan> subplans)

Specified by:

initializeEnumerationAlgorithm in class JoinPlanOptimizerBase

splitIntoSubSets

protected abstract <T> List<Pair<List<T>,List<T>>> splitIntoSubSets(List<T> superset)

getAllSubSets

protected static <T> List<List<T>> getAllSubSets(List<T> superset,
 int n)

This method returns all subsets (with the given size) of the given superset.

determineOptimalCandidatesAtStageN

protected boolean determineOptimalCandidatesAtStageN(List<List<PhysicalPlan>> subsets,
 DPBasedJoinPlanOptimizer.OptimalPlansPerStage optPlansPerStage,
 boolean ignoreCartesianProductJoins)
                                              throws PhysicalOptimizationException

For each of the sets of plans in 'subsets', determines the best possible join plan and adds this best plan to 'optPlansPerStage'.

Parameters:

subsets - is the set of all sets of plans to be considered at this stage, where all these sets are assumed to be of the same size

optPlansPerStage - contains the optimal join plans for every proper subset of every set of plans in 'subsets', these optimal join plans were determined in the earlier stages of the DP algorithm

ignoreCartesianProductJoins - is given as true if this function has to ignore any joins that would produce cartesian products (i.e., joins between subplans that don't share any variable)

Returns:

true if at least one possible join plan was added; the only case in which this may be false is if 'ignoreCartesianProductJoins' is true and none of the sets of plans in 'subsets' can be split into two disjoint subsets that share a variable.

Throws:

PhysicalOptimizationException