org.apache.derby.impl.sql.compile
Class OptimizerImpl

java.lang.Object
  extended byorg.apache.derby.impl.sql.compile.OptimizerImpl
All Implemented Interfaces:
Optimizer
Direct Known Subclasses:
Level2OptimizerImpl

public class OptimizerImpl
extends java.lang.Object
implements Optimizer

This will be the Level 1 Optimizer. RESOLVE - it's a level 0 optimizer right now. Current State: o No costing services o We can only cost a derived table with a join once. 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
protected  JBitSet assignedTableMap
           
protected  CostEstimateImpl bestCost
           
protected  int[] bestJoinOrder
           
private  RowOrdering bestRowOrdering
           
private  boolean conglomerate_OneRowResultSet
           
protected  CostEstimateImpl currentCost
           
private  RowOrdering currentRowOrdering
           
protected  CostEstimateImpl currentSortAvoidanceCost
           
protected  long currentTime
           
(package private)  DataDictionary dDictionary
           
(package private)  boolean desiredJoinOrderFound
           
private  int[] firstLookOrder
           
private  boolean foundABestPlan
           
protected  int joinPosition
           
private  JoinStrategy[] joinStrategies
           
private static int JUMPING
           
protected  int maxMemoryPerTable
           
private static int NO_JUMP
           
(package private)  JBitSet nonCorrelatedTableMap
           
private  boolean noTimeout
           
(package private)  int numOptimizables
           
(package private)  int numTablesInQuery
           
protected  OptimizableList optimizableList
           
protected  boolean optimizerTrace
           
protected  boolean optimizerTraceHtml
           
private  CostEstimateImpl outermostCostEstimate
           
private  int permuteState
           
(package private)  OptimizablePredicateList predicateList
           
protected  int[] proposedJoinOrder
           
private static int READY_TO_JUMP
           
protected  RequiredRowOrdering requiredRowOrdering
           
private  boolean ruleBasedOptimization
           
protected  CostEstimate sortCost
           
private  int tableLockThreshold
           
protected  boolean timeExceeded
           
protected  long timeOptimizationStarted
           
private  boolean useStatistics
           
private static int WALK_HIGH
           
private static int WALK_LOW
           
 
Fields inherited from interface org.apache.derby.iapi.sql.compile.Optimizer
ADDING_UNORDERED_OPTIMIZABLE, CALLING_NEXT_ACCESS_PATH, CALLING_ON_JOIN_NODE, CHANGING_ACCESS_PATH_FOR_TABLE, CHEAPEST_PLAN_SO_FAR, COMPLETE_JOIN_ORDER, COMPOSITE_SEL_FROM_STATS, CONSIDERING_CONGLOMERATE, CONSIDERING_JOIN_ORDER, CONSIDERING_JOIN_STRATEGY, COST_INCLUDING_COMPOSITE_SEL_FROM_STATS, COST_INCLUDING_EXTRA_1ST_COL_SELECTIVITY, COST_INCLUDING_EXTRA_NONQUALIFIER_SELECTIVITY, COST_INCLUDING_EXTRA_QUALIFIER_SELECTIVITY, COST_INCLUDING_EXTRA_START_STOP, COST_INCLUDING_STATS_FOR_INDEX, COST_OF_CHEAPEST_PLAN_SO_FAR, COST_OF_CONGLOMERATE_SCAN1, COST_OF_CONGLOMERATE_SCAN2, COST_OF_CONGLOMERATE_SCAN3, COST_OF_CONGLOMERATE_SCAN4, COST_OF_CONGLOMERATE_SCAN5, COST_OF_CONGLOMERATE_SCAN6, COST_OF_CONGLOMERATE_SCAN7, COST_OF_N_SCANS, COST_OF_NONCOVERING_INDEX, COST_OF_SORTING, CURRENT_PLAN_IS_SA_PLAN, ESTIMATING_COST_OF_CONGLOMERATE, HJ_HASH_KEY_COLUMNS, HJ_SKIP_NO_JOIN_COLUMNS, HJ_SKIP_NOT_MATERIALIZABLE, ILLEGAL_USER_JOIN_ORDER, JOIN_ORDER_OPTIMIZATION, LOOKING_FOR_SPECIFIED_INDEX, MATCH_SINGLE_ROW_COST, MAX_MEMORY_PER_TABLE, MODIFYING_ACCESS_PATHS, MODULE, NO_BEST_PLAN, NO_MORE_CONGLOMERATES, NO_TABLES, NO_TIMEOUT, NON_COVERING_INDEX_COST, NORMAL_PLAN, PLAN_TYPE, REMEMBERING_BEST_ACCESS_PATH, REMEMBERING_BEST_ACCESS_PATH_SUBSTRING, REMEMBERING_BEST_JOIN_ORDER, REMEMBERING_BEST_SORT_AVOIDANCE_ACCESS_PATH_SUBSTRING, REMEMBERING_BEST_UNKNOWN_ACCESS_PATH_SUBSTRING, REMEMBERING_JOIN_STRATEGY, ROW_LOCK_ALL_CONSTANT_START_STOP, ROW_LOCK_UNDER_THRESHOLD, RULE_BASED_OPTIMIZATION, SCANNING_HEAP_FULL_MATCH_ON_UNIQUE_KEY, SHORT_CIRCUITING, SKIPPING_DUE_TO_EXCESS_MEMORY, SKIPPING_JOIN_ORDER, SORT_AVOIDANCE_PLAN, SORT_NEEDED_FOR_ORDERING, STARTED, TABLE_LOCK_NO_START_STOP, TABLE_LOCK_OVER_THRESHOLD, TIME_EXCEEDED, TOTAL_COST_NON_SA_PLAN, TOTAL_COST_SA_PLAN, TOTAL_COST_WITH_SORTING, USE_STATISTICS, USER_JOIN_ORDER_OPTIMIZED
 
Constructor Summary
protected OptimizerImpl(OptimizableList optimizableList, OptimizablePredicateList predicateList, DataDictionary dDictionary, boolean ruleBasedOptimization, boolean noTimeout, boolean useStatistics, int maxMemoryPerTable, JoinStrategy[] joinStrategies, int tableLockThreshold, RequiredRowOrdering requiredRowOrdering, int numTablesInQuery)
           
 
Method Summary
 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 costPermutation()
          Cost the current permutation.
private  CostEstimate estimateTotalCost(OptimizablePredicateList predList, ConglomerateDescriptor cd, CostEstimate outerCost, Optimizable optimizable)
          Estimate the total cost of doing a join with the given optimizable.
 DataDictionary getDataDictionary()
          Return the DataDictionary that the Optimizer is using.
 JoinStrategy getJoinStrategy(int whichStrategy)
          Gets a join strategy by number (zero-based).
 JoinStrategy getJoinStrategy(java.lang.String whichStrategy)
          Gets a join strategy by name.
 int getLevel()
          Get the level of this optimizer.
 int getMaxMemoryPerTable()
           
 CostEstimateImpl getNewCostEstimate(double theCost, double theRowCount, double theSingleScanRowCount)
           
 boolean getNextDecoratedPermutation()
          Iterate through the "decorated permutations", returning false when they are exhausted.
 boolean getNextPermutation()
          Iterate through the permutations, returning false when the permutations are exhausted.
 int getNumberOfJoinStrategies()
          Get the number of join strategies supported by this optimizer.
 CostEstimate getOptimizedCost()
          Get the estimated cost of the optimized query
private  boolean isPushable(OptimizablePredicate pred)
           
 void modifyAccessPaths()
          Modify the access path for each Optimizable, as necessary.
 CostEstimate newCostEstimate()
          Get a new CostEstimate object
(package private)  void pushPredicates(Optimizable curTable, JBitSet outerTables)
           
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 rewindJoinOrder()
           
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 tableLockThreshold()
          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.
 void trace(int traceFlag, int intParam1, int intParam2, double doubleParam, java.lang.Object objectParam1)
          Optimizer trace.
 double uniqueJoinWithOuterTable(OptimizablePredicateList predList)
          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.
 boolean useStatistics()
          If statistics should be considered by the optimizer while optimizing a query.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

dDictionary

DataDictionary dDictionary

numTablesInQuery

int numTablesInQuery

numOptimizables

int numOptimizables

assignedTableMap

protected JBitSet assignedTableMap

optimizableList

protected OptimizableList optimizableList

predicateList

OptimizablePredicateList predicateList

nonCorrelatedTableMap

JBitSet nonCorrelatedTableMap

proposedJoinOrder

protected int[] proposedJoinOrder

bestJoinOrder

protected int[] bestJoinOrder

joinPosition

protected int joinPosition

desiredJoinOrderFound

boolean desiredJoinOrderFound

NO_JUMP

private static final int NO_JUMP
See Also:
Constant Field Values

READY_TO_JUMP

private static final int READY_TO_JUMP
See Also:
Constant Field Values

JUMPING

private static final int JUMPING
See Also:
Constant Field Values

WALK_HIGH

private static final int WALK_HIGH
See Also:
Constant Field Values

WALK_LOW

private static final int WALK_LOW
See Also:
Constant Field Values

permuteState

private int permuteState

firstLookOrder

private int[] firstLookOrder

ruleBasedOptimization

private boolean ruleBasedOptimization

outermostCostEstimate

private CostEstimateImpl outermostCostEstimate

currentCost

protected CostEstimateImpl currentCost

currentSortAvoidanceCost

protected CostEstimateImpl currentSortAvoidanceCost

bestCost

protected CostEstimateImpl bestCost

timeOptimizationStarted

protected long timeOptimizationStarted

currentTime

protected long currentTime

timeExceeded

protected boolean timeExceeded

noTimeout

private boolean noTimeout

useStatistics

private boolean useStatistics

tableLockThreshold

private int tableLockThreshold

joinStrategies

private JoinStrategy[] joinStrategies

requiredRowOrdering

protected RequiredRowOrdering requiredRowOrdering

foundABestPlan

private boolean foundABestPlan

sortCost

protected CostEstimate sortCost

currentRowOrdering

private RowOrdering currentRowOrdering

bestRowOrdering

private RowOrdering bestRowOrdering

conglomerate_OneRowResultSet

private boolean conglomerate_OneRowResultSet

optimizerTrace

protected boolean optimizerTrace

optimizerTraceHtml

protected boolean optimizerTraceHtml

maxMemoryPerTable

protected int maxMemoryPerTable
Constructor Detail

OptimizerImpl

protected OptimizerImpl(OptimizableList optimizableList,
                        OptimizablePredicateList predicateList,
                        DataDictionary dDictionary,
                        boolean ruleBasedOptimization,
                        boolean noTimeout,
                        boolean useStatistics,
                        int maxMemoryPerTable,
                        JoinStrategy[] joinStrategies,
                        int tableLockThreshold,
                        RequiredRowOrdering requiredRowOrdering,
                        int numTablesInQuery)
                 throws StandardException
Method Detail

getMaxMemoryPerTable

public int getMaxMemoryPerTable()
Specified by:
getMaxMemoryPerTable in interface Optimizer
Returns:
the maximum number of bytes to be used per table.

getNextPermutation

public boolean getNextPermutation()
                           throws StandardException
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 interface Optimizer
Returns:
boolean True - An optimizable permutation remains. False - Permutations are exhausted.
Throws:
StandardException - Thrown on error
See Also:
Optimizer.getNextPermutation()

rewindJoinOrder

private void rewindJoinOrder()
                      throws StandardException
Throws:
StandardException

pushPredicates

void pushPredicates(Optimizable curTable,
                    JBitSet outerTables)
              throws StandardException
Throws:
StandardException

getNextDecoratedPermutation

public boolean getNextDecoratedPermutation()
                                    throws StandardException
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 interface Optimizer
Returns:
boolean True - An optimizable decorated permutation remains. False - Decorated permutations are exhausted.
Throws:
StandardException - Thrown on error
See Also:
Optimizer.getNextDecoratedPermutation()

rememberBestCost

private void rememberBestCost(CostEstimate currentCost,
                              int planType)
                       throws StandardException
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

public void costPermutation()
                     throws StandardException
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 interface Optimizer
Returns:
Nothing.
Throws:
StandardException - Thrown on error
See Also:
Optimizer.costPermutation()

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 interface Optimizer
Parameters:
optimizable - The Optimizable
td - TableDescriptor of the Optimizable
cd - 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 apply
outerCost - The cost of the tables outer to the one being optimizer - tells how many outer rows there are.
Returns:
Nothing.
Throws:
StandardException - Thrown on error
See Also:
Optimizer.costOptimizable(org.apache.derby.iapi.sql.compile.Optimizable, org.apache.derby.iapi.sql.dictionary.TableDescriptor, org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor, org.apache.derby.iapi.sql.compile.OptimizablePredicateList, org.apache.derby.iapi.sql.compile.CostEstimate)

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 interface Optimizer
Parameters:
optimizable - The Optimizable
predList - The OptimizablePredicateList to apply
estimatedCost - The estimated cost of the given optimizable
outerCost - The cost of the tables outer to the one being optimizer - tells how many outer rows there are.
Returns:
Nothing.
Throws:
StandardException - Thrown on error
See Also:
Optimizer.considerCost(org.apache.derby.iapi.sql.compile.Optimizable, org.apache.derby.iapi.sql.compile.OptimizablePredicateList, org.apache.derby.iapi.sql.compile.CostEstimate, org.apache.derby.iapi.sql.compile.CostEstimate)

getDataDictionary

public DataDictionary 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 interface Optimizer
Returns:
DataDictionary DataDictionary that the Optimizer is using.
See Also:
Optimizer.getDataDictionary()

modifyAccessPaths

public void modifyAccessPaths()
                       throws StandardException
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 interface Optimizer
Throws:
StandardException - Thrown on error
See Also:
Optimizer.modifyAccessPaths()

newCostEstimate

public CostEstimate newCostEstimate()
Description copied from interface: Optimizer
Get a new CostEstimate object

Specified by:
newCostEstimate in interface Optimizer
See Also:
Optimizer.newCostEstimate()

getOptimizedCost

public CostEstimate getOptimizedCost()
Description copied from interface: Optimizer
Get the estimated cost of the optimized query

Specified by:
getOptimizedCost in interface Optimizer
See Also:
Optimizer.getOptimizedCost()

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 interface Optimizer
See Also:
Optimizer.setOuterRows(double)

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 interface Optimizer
See Also:
Optimizer.tableLockThreshold()

getNumberOfJoinStrategies

public int getNumberOfJoinStrategies()
Get the number of join strategies supported by this optimizer.

Specified by:
getNumberOfJoinStrategies in interface Optimizer

getJoinStrategy

public JoinStrategy getJoinStrategy(int whichStrategy)
Description copied from interface: Optimizer
Gets a join strategy by number (zero-based).

Specified by:
getJoinStrategy in interface Optimizer
See Also:
Optimizer.getJoinStrategy(int)

getJoinStrategy

public JoinStrategy getJoinStrategy(java.lang.String whichStrategy)
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 interface Optimizer
See Also:
Optimizer.getJoinStrategy(int)

uniqueJoinWithOuterTable

public double uniqueJoinWithOuterTable(OptimizablePredicateList predList)
                                throws StandardException
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 interface Optimizer
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:
Optimizer.uniqueJoinWithOuterTable(org.apache.derby.iapi.sql.compile.OptimizablePredicateList)

isPushable

private boolean isPushable(OptimizablePredicate pred)

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.

Specified by:
getLevel in interface Optimizer
Returns:
The level of this optimizer.
See Also:
Optimizer.getLevel()

getNewCostEstimate

public CostEstimateImpl getNewCostEstimate(double theCost,
                                           double theRowCount,
                                           double theSingleScanRowCount)

trace

public void trace(int traceFlag,
                  int intParam1,
                  int intParam2,
                  double doubleParam,
                  java.lang.Object objectParam1)
Description copied from interface: Optimizer
Optimizer trace.

Specified by:
trace in interface Optimizer

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 interface Optimizer
See Also:
Optimizer.useStatistics()

Built on Mon 2007-06-04 09:58:47+0400, from revision ???

Apache Derby V10.1 Engine Documentation - Copyright © 1997,2005 The Apache Software Foundation or its licensors, as applicable.