Class OptimizerImpl
java.lang.Object
org.apache.derby.impl.sql.compile.OptimizerImpl
- All Implemented Interfaces:
Optimizer
Optimizer uses OptimizableList to keep track of the best join order as it
builds it. For each available slot in the join order, we cost all of the
Optimizables from that slot til the end of the OptimizableList. Later,
we will choose the best Optimizable for that slot and reorder the list
accordingly.
In order to do this, we probably need to move the temporary pushing and
pulling of join clauses into Optimizer, since the logic will be different
for other implementations. (Of course, we're not pushing and pulling join
clauses between permutations yet.)
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate JBitSet
private CostEstimateImpl
private int[]
private boolean
private RowOrdering
private CostEstimateImpl
private OptimizerPlan
private RowOrdering
private CostEstimateImpl
private long
private DataDictionary
private boolean
private CostEstimate
private int[]
private boolean
private int
private JoinStrategy[]
private static final int
private LanguageConnectionContext
private int
private static final int
private JBitSet
private boolean
private int
private int
private OptimizableList
private CostEstimateImpl
private OptimizerPlan
private int
private OptimizablePredicateList
private int[]
private static final int
private boolean
private RequiredRowOrdering
private boolean
private CostEstimate
private int
private boolean
private double
private long
private boolean
private boolean
private static final int
private static final int
Fields inherited from interface org.apache.derby.iapi.sql.compile.Optimizer
JOIN_ORDER_OPTIMIZATION, MAX_DYNAMIC_MATERIALIZED_ROWS, MAX_MEMORY_PER_TABLE, MODULE, NO_TIMEOUT, NORMAL_PLAN, RULE_BASED_OPTIMIZATION, SORT_AVOIDANCE_PLAN, USE_STATISTICS
-
Constructor Summary
ConstructorsConstructorDescriptionOptimizerImpl
(OptimizableList optimizableList, OptimizablePredicateList predicateList, DataDictionary dDictionary, boolean ruleBasedOptimization, boolean noTimeout, boolean useStatistics, int maxMemoryPerTable, JoinStrategy[] joinStrategies, int tableLockThreshold, RequiredRowOrdering requiredRowOrdering, int numTablesInQuery, OptimizerPlan overridingPlan, LanguageConnectionContext lcc) -
Method Summary
Modifier and TypeMethodDescription(package private) void
addScopedPredicatesToList
(PredicateList pList, ContextManager cm) Add scoped predicates to this optimizer's predicateList.void
considerCost
(Optimizable optimizable, OptimizablePredicateList predList, CostEstimate estimatedCost, CostEstimate outerCost) This is the version of costOptimizable for non-base-tables.private void
costBasedCostOptimizable
(Optimizable optimizable, TableDescriptor td, ConglomerateDescriptor cd, OptimizablePredicateList predList, CostEstimate outerCost) This method decides whether the given conglomerate descriptor is cheapest based on cost, rather than based on rules.void
costOptimizable
(Optimizable optimizable, TableDescriptor td, ConglomerateDescriptor cd, OptimizablePredicateList predList, CostEstimate outerCost) Cost the current Optimizable with the specified OPL.void
Cost the current permutation.private void
Do any work that needs to be done after the current round of optimization has completed.private CostEstimate
estimateTotalCost
(OptimizablePredicateList predList, ConglomerateDescriptor cd, CostEstimate outerCost, Optimizable optimizable) Estimate the total cost of doing a join with the given optimizable.Return the DataDictionary that the Optimizer is using.Get the final estimated cost of the optimized query.getJoinStrategy
(int whichStrategy) Gets a join strategy by number (zero-based).getJoinStrategy
(String whichStrategy) Gets a join strategy by name.int
getLevel()
Get the level of this optimizer.int
(package private) CostEstimateImpl
getNewCostEstimate
(double theCost, double theRowCount, double theSingleScanRowCount) boolean
Iterate through the "decorated permutations", returning false when they are exhausted.boolean
Iterate through the permutations, returning false when the permutations are exhausted.int
Get the number of join strategies supported by this optimizer.getOptimizable
(int idx) Get the ith (0-based) Optimizable being considered by this Optimizer.int
Get the number of optimizables being considered by this Optimizer.Get the estimated cost of the optimized queryprivate UniqueTupleDescriptor
getTupleDescriptor
(Optimizable optimizable) Get the unique tuple descriptor of the current access path for an Optimizable.private int
Determine if we want to try "jumping" permutations with this OptimizerImpl, and (re-)initialize the permuteState field accordingly.private boolean
(package private) static boolean
isTableFunction
(Optimizable optimizable) Return true if the optimizable is a table functionprivate boolean
joinOrderMeetsDependencies
(int optNumber) Check to see if the optimizable corresponding to the received optNumber can legally be placed within the current join order.void
Modify the access path for each Optimizable, as necessary.private CostEstimate
void
This method is called before every "round" of optimization, where we define a "round" to be the period between the last time a call to getOptimizer() (on either a ResultSetNode or an OptimizerFactory) returned _this_ OptimizerImpl and the time a call to this OptimizerImpl's getNextPermutation() method returns FALSE.private void
Pull whatever optimizable is at joinPosition in the proposed join order from the join order, and update all corresponding state accordingly.(package private) void
pushPredicates
(Optimizable curTable, JBitSet outerTables) private double
recoverCostFromProposedJoinOrder
(boolean sortAvoidance) Iterate through all optimizables in the current proposedJoinOrder and find the accumulated sum of their estimated costs.private void
rememberBestCost
(CostEstimate currentCost, int planType) Is the cost of this join order lower than the best one we've found so far?private void
private void
ruleBasedCostOptimizable
(Optimizable optimizable, TableDescriptor td, ConglomerateDescriptor cd, OptimizablePredicateList predList, CostEstimate outerCost) This method decides whether the given conglomerate descriptor is cheapest based on rules, rather than based on cost estimates.void
setOuterRows
(double outerRows) Set the estimated number of outer rows - good for optimizing nested optimizables like subqueries and join nodes.int
Get the maximum number of estimated rows touched in a table before we decide to open the table with table locking (as opposed to row locking.private OptTrace
tracer()
Get the trace machineryprivate boolean
double
Tells whether any of the tables outer to the current one has a uniqueness condition on the given predicate list, and if so, how many times each unique key can be seen by the current table.void
updateBestPlanMaps
(short action, Object planKey) Process (i.e. add, load, or remove) current best join order as the best one for some outer query or ancestor node, represented by another OptimizerImpl or an instance of FromTable, respectively.boolean
If statistics should be considered by the optimizer while optimizing a query.
-
Field Details
-
lcc
-
dDictionary
-
numTablesInQuery
private int numTablesInQuery -
numOptimizables
private int numOptimizables -
assignedTableMap
-
optimizableList
-
overridingPlan
-
currentPlan
-
predicateList
-
proposedJoinOrder
private int[] proposedJoinOrder -
bestJoinOrder
private int[] bestJoinOrder -
joinPosition
private int joinPosition -
desiredJoinOrderFound
private boolean desiredJoinOrderFound -
NO_JUMP
private static final int NO_JUMP- See Also:
-
READY_TO_JUMP
private static final int READY_TO_JUMP- See Also:
-
JUMPING
private static final int JUMPING- See Also:
-
WALK_HIGH
private static final int WALK_HIGH- See Also:
-
WALK_LOW
private static final int WALK_LOW- See Also:
-
permuteState
private int permuteState -
firstLookOrder
private int[] firstLookOrder -
ruleBasedOptimization
private boolean ruleBasedOptimization -
outermostCostEstimate
-
currentCost
-
currentSortAvoidanceCost
-
bestCost
-
timeOptimizationStarted
private long timeOptimizationStarted -
currentTime
private long currentTime -
timeExceeded
private boolean timeExceeded -
noTimeout
private boolean noTimeout -
useStatistics
private boolean useStatistics -
tableLockThreshold
private int tableLockThreshold -
joinStrategies
-
requiredRowOrdering
-
foundABestPlan
private boolean foundABestPlan -
sortCost
-
currentRowOrdering
-
bestRowOrdering
-
maxMemoryPerTable
private int maxMemoryPerTable -
reloadBestPlan
private boolean reloadBestPlan -
savedJoinOrders
-
timeLimit
private double timeLimit -
finalCostEstimate
-
usingPredsPushedFromAbove
private boolean usingPredsPushedFromAbove -
bestJoinOrderUsedPredsFromAbove
private boolean bestJoinOrderUsedPredsFromAbove
-
-
Constructor Details
-
OptimizerImpl
OptimizerImpl(OptimizableList optimizableList, OptimizablePredicateList predicateList, DataDictionary dDictionary, boolean ruleBasedOptimization, boolean noTimeout, boolean useStatistics, int maxMemoryPerTable, JoinStrategy[] joinStrategies, int tableLockThreshold, RequiredRowOrdering requiredRowOrdering, int numTablesInQuery, OptimizerPlan overridingPlan, LanguageConnectionContext lcc) throws StandardException - Throws:
StandardException
-
-
Method Details
-
prepForNextRound
public void prepForNextRound()This method is called before every "round" of optimization, where we define a "round" to be the period between the last time a call to getOptimizer() (on either a ResultSetNode or an OptimizerFactory) returned _this_ OptimizerImpl and the time a call to this OptimizerImpl's getNextPermutation() method returns FALSE. Any re-initialization of state that is required before each round should be done in this method.- Specified by:
prepForNextRound
in interfaceOptimizer
-
initJumpState
private int initJumpState()Determine if we want to try "jumping" permutations with this OptimizerImpl, and (re-)initialize the permuteState field accordingly. -
tracingIsOn
private boolean tracingIsOn() -
getMaxMemoryPerTable
public int getMaxMemoryPerTable()- Specified by:
getMaxMemoryPerTable
in interfaceOptimizer
- Returns:
- the maximum number of bytes to be used per table.
-
getNextPermutation
Description copied from interface:Optimizer
Iterate through the permutations, returning false when the permutations are exhausted. NOTE - Implementers are responsible for hiding tree pruning of permutations behind this method call.- Specified by:
getNextPermutation
in interfaceOptimizer
- Returns:
- boolean True - An optimizable permutation remains. False - Permutations are exhausted.
- Throws:
StandardException
- Thrown on error- See Also:
-
rewindJoinOrder
- Throws:
StandardException
-
endOfRoundCleanup
Do any work that needs to be done after the current round of optimization has completed. For now this just means walking the subtrees for each optimizable and removing the "bestPlan" that we saved (w.r.t to this OptimizerImpl) from all of the nodes. If we don't do this post-optimization cleanup we can end up consuming a huge amount of memory for deeply- nested queries, which can lead to OOM errors. DERBY-1315.- Throws:
StandardException
-
recoverCostFromProposedJoinOrder
Iterate through all optimizables in the current proposedJoinOrder and find the accumulated sum of their estimated costs. This method is used to 'recover' cost estimate sums that have been lost due to the addition/subtraction of the cost estimate for the Optimizable at position "joinPosition". Ex. If the total cost for Optimizables at positions < joinPosition is 1500, and then the Optimizable at joinPosition has an estimated cost of 3.14E40, adding those two numbers effectively "loses" the 1500. When we later subtract 3.14E40 from the total cost estimate (as part of "pull" processing), we'll end up with 0 as the result--which is wrong. This method allows us to recover the "1500" that we lost in the process of adding and subtracting 3.14E40.- Throws:
StandardException
-
joinOrderMeetsDependencies
Check to see if the optimizable corresponding to the received optNumber can legally be placed within the current join order. More specifically, if the optimizable has any dependencies, check to see if those dependencies are satisified by the table map representing the current join order.- Throws:
StandardException
-
pullOptimizableFromJoinOrder
Pull whatever optimizable is at joinPosition in the proposed join order from the join order, and update all corresponding state accordingly.- Throws:
StandardException
-
pushPredicates
- Throws:
StandardException
-
getNextDecoratedPermutation
Description copied from interface:Optimizer
Iterate through the "decorated permutations", returning false when they are exhausted. NOTE - Implementers are responsible for hiding tree pruning of access methods behind this method call.- Specified by:
getNextDecoratedPermutation
in interfaceOptimizer
- Returns:
- boolean True - An optimizable decorated permutation remains. False - Decorated permutations are exhausted.
- Throws:
StandardException
- Thrown on error- See Also:
-
getTupleDescriptor
Get the unique tuple descriptor of the current access path for an Optimizable.- Throws:
StandardException
-
isTableFunction
Return true if the optimizable is a table function -
rememberBestCost
Is the cost of this join order lower than the best one we've found so far? If so, remember it. NOTE: If the user has specified a join order, it will be the only join order the optimizer considers, so it is OK to use costing to decide that it is the "best" join order.- Throws:
StandardException
- Thrown on error
-
costPermutation
Description copied from interface:Optimizer
Cost the current permutation. Caller is responsible for pushing all predicates which can be evaluated prior to costing.- Specified by:
costPermutation
in interfaceOptimizer
- Throws:
StandardException
- Thrown on error- See Also:
-
costOptimizable
public void costOptimizable(Optimizable optimizable, TableDescriptor td, ConglomerateDescriptor cd, OptimizablePredicateList predList, CostEstimate outerCost) throws StandardException Description copied from interface:Optimizer
Cost the current Optimizable with the specified OPL. Caller is responsible for pushing all predicates which can be evaluated prior to costing.- Specified by:
costOptimizable
in interfaceOptimizer
- Parameters:
optimizable
- The Optimizabletd
- TableDescriptor of the Optimizablecd
- The ConglomerateDescriptor for the conglom to cost (This should change to an object to represent access paths, but for now this is OK).predList
- The OptimizablePredicateList to applyouterCost
- The cost of the tables outer to the one being optimizer - tells how many outer rows there are.- Throws:
StandardException
- Thrown on error- See Also:
-
ruleBasedCostOptimizable
private void ruleBasedCostOptimizable(Optimizable optimizable, TableDescriptor td, ConglomerateDescriptor cd, OptimizablePredicateList predList, CostEstimate outerCost) throws StandardException This method decides whether the given conglomerate descriptor is cheapest based on rules, rather than based on cost estimates. The rules are: Covering matching indexes are preferred above all Non-covering matching indexes are next in order of preference Covering non-matching indexes are next in order of preference Heap scans are next in order of preference Non-covering, non-matching indexes are last in order of preference. In the current language architecture, there will always be a heap, so a non-covering, non-matching index scan will never be chosen. However, the optimizer may see a non-covering, non-matching index first, in which case it will choose it temporarily as the best conglomerate seen so far. NOTE: This method sets the cost in the optimizable, even though it doesn't use the cost to determine which access path to choose. There are two reasons for this: the cost might be needed to determine join order, and the cost information is copied to the query plan.- Throws:
StandardException
-
costBasedCostOptimizable
private void costBasedCostOptimizable(Optimizable optimizable, TableDescriptor td, ConglomerateDescriptor cd, OptimizablePredicateList predList, CostEstimate outerCost) throws StandardException This method decides whether the given conglomerate descriptor is cheapest based on cost, rather than based on rules. It compares the cost of using the given ConglomerateDescriptor with the cost of using the best ConglomerateDescriptor so far.- Throws:
StandardException
-
considerCost
public void considerCost(Optimizable optimizable, OptimizablePredicateList predList, CostEstimate estimatedCost, CostEstimate outerCost) throws StandardException This is the version of costOptimizable for non-base-tables.- Specified by:
considerCost
in interfaceOptimizer
- Parameters:
optimizable
- The OptimizablepredList
- The OptimizablePredicateList to applyestimatedCost
- The estimated cost of the given optimizableouterCost
- The cost of the tables outer to the one being optimizer - tells how many outer rows there are.- Throws:
StandardException
- Thrown on error- See Also:
-
getDataDictionary
Description copied from interface:Optimizer
Return the DataDictionary that the Optimizer is using. This is useful when an Optimizable needs to call optimize() on a child ResultSetNode.- Specified by:
getDataDictionary
in interfaceOptimizer
- Returns:
- DataDictionary DataDictionary that the Optimizer is using.
- See Also:
-
modifyAccessPaths
Description copied from interface:Optimizer
Modify the access path for each Optimizable, as necessary. This includes things like adding result sets to translate from index rows to base rows.- Specified by:
modifyAccessPaths
in interfaceOptimizer
- Throws:
StandardException
- Thrown on error- See Also:
-
newCostEstimate
-
getOptimizedCost
Description copied from interface:Optimizer
Get the estimated cost of the optimized query- Specified by:
getOptimizedCost
in interfaceOptimizer
- See Also:
-
getFinalCost
Description copied from interface:Optimizer
Get the final estimated cost of the optimized query. This should be the cost that corresponds to the best overall join order chosen by the optimizer, and thus this method should only be called after optimization is complete (i.e. when modifying access paths).- Specified by:
getFinalCost
in interfaceOptimizer
- See Also:
-
setOuterRows
public void setOuterRows(double outerRows) Description copied from interface:Optimizer
Set the estimated number of outer rows - good for optimizing nested optimizables like subqueries and join nodes.- Specified by:
setOuterRows
in interfaceOptimizer
- See Also:
-
tableLockThreshold
public int tableLockThreshold()Description copied from interface:Optimizer
Get the maximum number of estimated rows touched in a table before we decide to open the table with table locking (as opposed to row locking.- Specified by:
tableLockThreshold
in interfaceOptimizer
- See Also:
-
getNumberOfJoinStrategies
public int getNumberOfJoinStrategies()Get the number of join strategies supported by this optimizer.- Specified by:
getNumberOfJoinStrategies
in interfaceOptimizer
-
getJoinStrategy
Description copied from interface:Optimizer
Gets a join strategy by number (zero-based).- Specified by:
getJoinStrategy
in interfaceOptimizer
- See Also:
-
getJoinStrategy
Description copied from interface:Optimizer
Gets a join strategy by name. Returns null if not found. The look-up is case-insensitive.- Specified by:
getJoinStrategy
in interfaceOptimizer
- See Also:
-
uniqueJoinWithOuterTable
Description copied from interface:Optimizer
Tells whether any of the tables outer to the current one has a uniqueness condition on the given predicate list, and if so, how many times each unique key can be seen by the current table.- Specified by:
uniqueJoinWithOuterTable
in interfaceOptimizer
- Parameters:
predList
- The predicate list to check- Returns:
- <= 0 means there is no uniqueness condition > 0 means there is a uniqueness condition on an outer table, and the return value is the reciprocal of the maximum number of times the optimizer estimates that each unique key will be returned. For example, 0.5 means the optimizer thinks each distinct join key will be returned at most twice.
- Throws:
StandardException
- Thrown on error- See Also:
-
isPushable
-
estimateTotalCost
private CostEstimate estimateTotalCost(OptimizablePredicateList predList, ConglomerateDescriptor cd, CostEstimate outerCost, Optimizable optimizable) throws StandardException Estimate the total cost of doing a join with the given optimizable.- Throws:
StandardException
- Thrown on error
-
getLevel
public int getLevel()Description copied from interface:Optimizer
Get the level of this optimizer. -
getNewCostEstimate
CostEstimateImpl getNewCostEstimate(double theCost, double theRowCount, double theSingleScanRowCount) -
useStatistics
public boolean useStatistics()Description copied from interface:Optimizer
If statistics should be considered by the optimizer while optimizing a query. The user may disable the use of statistics by setting the property derby.optimizer.useStatistics or by using the property useStatistics in a query.- Specified by:
useStatistics
in interfaceOptimizer
- See Also:
-
updateBestPlanMaps
Process (i.e. add, load, or remove) current best join order as the best one for some outer query or ancestor node, represented by another OptimizerImpl or an instance of FromTable, respectively. Then iterate through our optimizableList and tell each Optimizable to do the same. See Optimizable.updateBestPlan() for more on why this is necessary.- Specified by:
updateBestPlanMaps
in interfaceOptimizer
- Parameters:
action
- Indicates whether to add, load, or remove the planplanKey
- Object to use as the map key when adding/looking up a plan. If this is an instance of OptimizerImpl then it corresponds to an outer query; otherwise it's some Optimizable above this OptimizerImpl that could potentially reject plans chosen by this OptimizerImpl.- Throws:
StandardException
-
addScopedPredicatesToList
Add scoped predicates to this optimizer's predicateList. This method is intended for use during the modifyAccessPath() phase of compilation, as it allows nodes (esp. SelectNodes) to add to the list of predicates available for the final "push" before code generation. Just as the constructor for this class allows a caller to specify a predicate list to use during the optimization phase, this method allows a caller to specify a predicate list to use during the modify-access-paths phase. Before adding the received predicates, this method also clears out any scoped predicates that might be sitting in OptimizerImpl's list from the last round of optimizing. This method should be in the Optimizer interface, but it relies on an argument type (PredicateList) which lives in an impl package.- Parameters:
pList
- List of predicates to add to this OptimizerImpl's own list for pushing.- Throws:
StandardException
-
tracer
Get the trace machinery -
getOptimizableCount
public int getOptimizableCount()Description copied from interface:Optimizer
Get the number of optimizables being considered by this Optimizer.- Specified by:
getOptimizableCount
in interfaceOptimizer
-
getOptimizable
Description copied from interface:Optimizer
Get the ith (0-based) Optimizable being considered by this Optimizer.- Specified by:
getOptimizable
in interfaceOptimizer
-