Class OptimizerImpl

  • All Implemented Interfaces:
    Optimizer

    class OptimizerImpl
    extends java.lang.Object
    implements 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 Detail

      • numTablesInQuery

        private int numTablesInQuery
      • numOptimizables

        private int numOptimizables
      • assignedTableMap

        private JBitSet assignedTableMap
      • nonCorrelatedTableMap

        private JBitSet nonCorrelatedTableMap
      • proposedJoinOrder

        private int[] proposedJoinOrder
      • bestJoinOrder

        private int[] bestJoinOrder
      • joinPosition

        private int joinPosition
      • desiredJoinOrderFound

        private boolean desiredJoinOrderFound
      • permuteState

        private int permuteState
      • firstLookOrder

        private int[] firstLookOrder
      • ruleBasedOptimization

        private boolean ruleBasedOptimization
      • timeOptimizationStarted

        private long timeOptimizationStarted
      • currentTime

        private long currentTime
      • timeExceeded

        private boolean timeExceeded
      • noTimeout

        private boolean noTimeout
      • useStatistics

        private boolean useStatistics
      • tableLockThreshold

        private int tableLockThreshold
      • foundABestPlan

        private boolean foundABestPlan
      • currentRowOrdering

        private RowOrdering currentRowOrdering
      • maxMemoryPerTable

        private int maxMemoryPerTable
      • reloadBestPlan

        private boolean reloadBestPlan
      • savedJoinOrders

        private java.util.HashMap<java.lang.Object,​int[]> savedJoinOrders
      • timeLimit

        private double timeLimit
      • usingPredsPushedFromAbove

        private boolean usingPredsPushedFromAbove
      • bestJoinOrderUsedPredsFromAbove

        private boolean bestJoinOrderUsedPredsFromAbove
    • Method Detail

      • 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 interface Optimizer
      • 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 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()
      • endOfRoundCleanup

        private void endOfRoundCleanup()
                                throws StandardException
        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

        private double recoverCostFromProposedJoinOrder​(boolean sortAvoidance)
                                                 throws StandardException
        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

        private boolean joinOrderMeetsDependencies​(int optNumber)
                                            throws StandardException
        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

        private void pullOptimizableFromJoinOrder()
                                           throws StandardException
        Pull whatever optimizable is at joinPosition in the proposed join order from the join order, and update all corresponding state accordingly.
        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()
      • isTableFunction

        static boolean isTableFunction​(Optimizable optimizable)
        Return true if the optimizable is a table function
      • 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
      • 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
      • 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()
      • 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
      • 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)
      • 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

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

        public void updateBestPlanMaps​(short action,
                                       java.lang.Object planKey)
                                throws StandardException
        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 interface Optimizer
        Parameters:
        action - Indicates whether to add, load, or remove the plan
        planKey - 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

        void addScopedPredicatesToList​(PredicateList pList,
                                       ContextManager cm)
                                throws StandardException
        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

        private OptTrace 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 interface Optimizer
      • getOptimizable

        public Optimizable getOptimizable​(int idx)
        Description copied from interface: Optimizer
        Get the ith (0-based) Optimizable being considered by this Optimizer.
        Specified by:
        getOptimizable in interface Optimizer