| /* |
| |
| Derby - Class org.apache.derby.impl.sql.compile.OptimizerImpl |
| |
| Licensed to the Apache Software Foundation (ASF) under one or more |
| contributor license agreements. See the NOTICE file distributed with |
| this work for additional information regarding copyright ownership. |
| The ASF licenses this file to you under the Apache License, Version 2.0 |
| (the "License"); you may not use this file except in compliance with |
| the License. You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, software |
| distributed under the License is distributed on an "AS IS" BASIS, |
| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| See the License for the specific language governing permissions and |
| limitations under the License. |
| |
| */ |
| |
| package org.apache.derby.impl.sql.compile; |
| |
| import java.util.HashMap; |
| import org.apache.derby.iapi.error.StandardException; |
| import org.apache.derby.iapi.reference.SQLState; |
| import org.apache.derby.iapi.services.context.ContextManager; |
| import org.apache.derby.iapi.services.io.ArrayUtil; |
| import org.apache.derby.shared.common.sanity.SanityManager; |
| import org.apache.derby.iapi.sql.compile.AccessPath; |
| import org.apache.derby.iapi.sql.compile.CostEstimate; |
| import org.apache.derby.iapi.sql.compile.JoinStrategy; |
| import org.apache.derby.iapi.sql.compile.OptTrace; |
| import org.apache.derby.iapi.sql.compile.Optimizable; |
| import org.apache.derby.iapi.sql.compile.OptimizableList; |
| import org.apache.derby.iapi.sql.compile.OptimizablePredicate; |
| import org.apache.derby.iapi.sql.compile.OptimizablePredicateList; |
| import org.apache.derby.iapi.sql.compile.Optimizer; |
| import org.apache.derby.iapi.sql.compile.OptimizerPlan; |
| import org.apache.derby.iapi.sql.compile.RequiredRowOrdering; |
| import org.apache.derby.iapi.sql.compile.RowOrdering; |
| import org.apache.derby.iapi.sql.conn.LanguageConnectionContext; |
| import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor; |
| import org.apache.derby.iapi.sql.dictionary.DataDictionary; |
| import org.apache.derby.iapi.sql.dictionary.TableDescriptor; |
| import org.apache.derby.iapi.sql.dictionary.UniqueTupleDescriptor; |
| import org.apache.derby.iapi.util.JBitSet; |
| import org.apache.derby.iapi.util.StringUtil; |
| |
| /** |
| * 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.) |
| */ |
| |
| class OptimizerImpl implements Optimizer |
| { |
| private LanguageConnectionContext lcc; |
| |
| private DataDictionary dDictionary; |
| /* The number of tables in the query as a whole. (Size of bit maps.) */ |
| private int numTablesInQuery; |
| /* The number of optimizables in the list to optimize */ |
| private int numOptimizables; |
| |
| /* Bit map of tables that have already been assigned to slots. |
| * Useful for pushing join clauses as slots are assigned. |
| * Enforcement of ordering dependencies is done through |
| * assignedTableMap. |
| */ |
| private JBitSet assignedTableMap; |
| private OptimizableList optimizableList; |
| private OptimizerPlan overridingPlan; |
| private OptimizerPlan currentPlan; |
| private OptimizablePredicateList predicateList; |
| private JBitSet nonCorrelatedTableMap; |
| |
| private int[] proposedJoinOrder; |
| private int[] bestJoinOrder; |
| private int joinPosition; |
| private boolean desiredJoinOrderFound; |
| |
| /* This implements a state machine to jump start to a appearingly good join |
| * order, when the number of tables is high, and the optimization could take |
| * a long time. A good start can prune better, and timeout sooner. |
| * Otherwise, it may take forever to exhaust or timeout (see beetle 5870). |
| * Basically after we jump, we walk the high part, then fall when we reach |
| * the peak, finally we walk the low part until where we jumped to. |
| */ |
| private static final int NO_JUMP = 0; |
| private static final int READY_TO_JUMP = 1; |
| private static final int JUMPING = 2; |
| private static final int WALK_HIGH = 3; |
| private static final int WALK_LOW = 4; |
| private int permuteState; |
| private int[] firstLookOrder; |
| |
| private boolean ruleBasedOptimization; |
| |
| private CostEstimateImpl outermostCostEstimate; |
| private CostEstimateImpl currentCost; |
| private CostEstimateImpl currentSortAvoidanceCost; |
| private CostEstimateImpl bestCost; |
| |
| private long timeOptimizationStarted; |
| private long currentTime; |
| private boolean timeExceeded; |
| private boolean noTimeout; |
| private boolean useStatistics; |
| private int tableLockThreshold; |
| |
| private JoinStrategy[] joinStrategies; |
| |
| private RequiredRowOrdering requiredRowOrdering; |
| |
| private boolean foundABestPlan; |
| |
| private CostEstimate sortCost; |
| |
| private RowOrdering currentRowOrdering = new RowOrderingImpl(); |
| private RowOrdering bestRowOrdering = new RowOrderingImpl(); |
| |
| // max memory use per table |
| private int maxMemoryPerTable; |
| |
| // Whether or not we need to reload the best plan for an Optimizable |
| // when we "pull" [1] it. If the latest complete join order was the |
| // best one so far, then the Optimizable will already have the correct |
| // best plan loaded so we don't need to do the extra work. But if |
| // the most recent join order was _not_ the best, then this flag tells |
| // us that we need to reload the best plan when pulling. |
| // |
| // [1]: As part of the iteration through the join orders, the optimizer has |
| // to "pull" Optimizables from the the join order before re-placing them in |
| // a different order. As an example, in order to get from: |
| // |
| // { HOJ, TAB_V, TAB_D } to |
| // |
| // { HOJ, TAB_D, TAB_V} |
| // |
| // the optimizer will first pull TAB_D from the join order, then |
| // it will pull TAB_V, then it will place TAB_D, and finally place |
| // TAB_V. I.e.: |
| // |
| // { HOJ, TAB_V, - } |
| // { HOJ, -, - } |
| // { HOJ, TAB_D, - } |
| // { HOJ, TAB_D, TAB_V } |
| |
| private boolean reloadBestPlan; |
| |
| // Set of optimizer->bestJoinOrder mappings used to keep track of which |
| // of this OptimizerImpl's "bestJoinOrder"s was the best with respect to a |
| // a specific outer query; the outer query is represented by an instance |
| // of Optimizer. Each outer query could potentially have a different |
| // idea of what this OptimizerImpl's "best join order" is, so we have |
| // to keep track of them all. |
| private HashMap<Object,int[]> savedJoinOrders; |
| |
| // Value used to figure out when/if we've timed out for this |
| // Optimizable. |
| private double timeLimit; |
| |
| // Cost estimate for the final "best join order" that we chose--i.e. |
| // the one that's actually going to be generated. |
| private CostEstimate finalCostEstimate; |
| |
| /* Status variables used for "jumping" to previous best join |
| * order when possible. In particular, this helps when this |
| * optimizer corresponds to a subquery and we are trying to |
| * find out what the best join order is if we do a hash join |
| * with the subquery instead of a nested loop join. In that |
| * case the previous best join order will have the best join |
| * order for a nested loop, so we want to start there when |
| * considering hash join because odds are that same join order |
| * will give us the best cost for hash join, as well. We |
| * only try this, though, if neither the previous round of |
| * optimization nor this round relies on predicates that have |
| * been pushed down from above--because that's the scenario |
| * for which the best join order is likely to be same for |
| * consecutive rounds. |
| */ |
| private boolean usingPredsPushedFromAbove; |
| private boolean bestJoinOrderUsedPredsFromAbove; |
| |
| 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 |
| { |
| if (SanityManager.DEBUG) { |
| SanityManager.ASSERT(optimizableList != null, |
| "optimizableList is not expected to be null"); |
| } |
| |
| outermostCostEstimate = getNewCostEstimate(0.0d, 1.0d, 1.0d); |
| |
| currentCost = getNewCostEstimate(0.0d, 0.0d, 0.0d); |
| |
| currentSortAvoidanceCost = getNewCostEstimate(0.0d, 0.0d, 0.0d); |
| |
| bestCost = |
| getNewCostEstimate( |
| Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE); |
| |
| // Verify that any Properties lists for user overrides are valid |
| optimizableList.verifyProperties(dDictionary); |
| |
| this.numTablesInQuery = numTablesInQuery; |
| numOptimizables = optimizableList.size(); |
| proposedJoinOrder = new int[numOptimizables]; |
| if (initJumpState() == READY_TO_JUMP) |
| firstLookOrder = new int[numOptimizables]; |
| |
| /* Mark all join positions as unused */ |
| for (int i = 0; i < numOptimizables; i++) |
| proposedJoinOrder[i] = -1; |
| |
| bestJoinOrder = new int[numOptimizables]; |
| joinPosition = -1; |
| |
| this.optimizableList = optimizableList; |
| this.overridingPlan = overridingPlan; |
| this.predicateList = predicateList; |
| this.dDictionary = dDictionary; |
| this.ruleBasedOptimization = ruleBasedOptimization; |
| this.noTimeout = noTimeout; |
| this.maxMemoryPerTable = maxMemoryPerTable; |
| this.joinStrategies = joinStrategies; |
| this.tableLockThreshold = tableLockThreshold; |
| this.requiredRowOrdering = requiredRowOrdering; |
| this.useStatistics = useStatistics; |
| this.lcc = lcc; |
| |
| /* initialize variables for tracking permutations */ |
| assignedTableMap = new JBitSet(numTablesInQuery); |
| |
| /* |
| ** Make a map of the non-correlated tables, which are the tables |
| ** in the list of Optimizables we're optimizing. An reference |
| ** to a table that is not defined in the list of Optimizables |
| ** is presumed to be correlated. |
| */ |
| nonCorrelatedTableMap = new JBitSet(numTablesInQuery); |
| for (int tabCtr = 0; tabCtr < numOptimizables; tabCtr++) |
| { |
| Optimizable curTable = optimizableList.getOptimizable(tabCtr); |
| nonCorrelatedTableMap.or(curTable.getReferencedTableMap()); |
| } |
| |
| /* Get the time that optimization starts */ |
| timeOptimizationStarted = System.currentTimeMillis(); |
| reloadBestPlan = false; |
| savedJoinOrders = null; |
| timeLimit = Double.MAX_VALUE; |
| |
| usingPredsPushedFromAbove = false; |
| bestJoinOrderUsedPredsFromAbove = false; |
| |
| // Optimization started |
| if (tracingIsOn()) |
| { |
| tracer().traceStartQueryBlock( |
| timeOptimizationStarted, hashCode(), optimizableList ); |
| } |
| |
| // make sure that optimizer overrides are bound and left-deep |
| if ( overridingPlan != null ) |
| { |
| if ( !overridingPlan.isBound() ) |
| { |
| throw StandardException.newException( |
| SQLState.LANG_UNRESOLVED_ROW_SOURCE ); |
| } |
| |
| int actualRowSourceCount = optimizableList.size(); |
| int overriddenRowSourceCount = overridingPlan.countLeafNodes(); |
| if ( actualRowSourceCount != overriddenRowSourceCount ) |
| { |
| throw StandardException.newException( |
| SQLState.LANG_BAD_ROW_SOURCE_COUNT, |
| overriddenRowSourceCount, |
| actualRowSourceCount ); |
| } |
| } |
| } |
| |
| /** |
| * 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. |
| */ |
| public void prepForNextRound() |
| { |
| // We initialize reloadBestPlan to false so that if we end up |
| // pulling an Optimizable before we find a best join order |
| // (which can happen if there is no valid join order for this |
| // round) we won't inadvertently reload the best plans based |
| // on some previous round. |
| reloadBestPlan = false; |
| |
| /* Since we're preparing for a new round, we have to clear |
| * out the "bestCost" from the previous round to ensure that, |
| * when this round of optimizing is done, bestCost will hold |
| * the best cost estimate found _this_ round, if there was |
| * one. If there was no best cost found (which can happen if |
| * there is no feasible join order) then bestCost will remain |
| * at Double.MAX_VALUE. Then when outer queries check the |
| * cost and see that it is so high, they will reject whatever |
| * outer join order they're trying in favor of something that's |
| * actually valid (and therefore cheaper). |
| * |
| * Note that we do _not_ reset the "foundABestPlan" variable nor |
| * the "bestJoinOrder" array. This is because it's possible that |
| * a "best join order" may not exist for the current round, in |
| * which case this OptimizerImpl must know whether or not it found |
| * a best join order in a previous round (foundABestPlan) and if |
| * so what the corresponding join order was (bestJoinOrder). This |
| * information is required so that the correct query plan can be |
| * generated after optimization is complete, even if that best |
| * plan was not found in the most recent round. |
| */ |
| bestCost = getNewCostEstimate( |
| Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE); |
| |
| /* If we have predicates that were pushed down to this OptimizerImpl |
| * from an outer query, then we reset the timeout state to prepare for |
| * the next round of optimization. Otherwise if we timed out during |
| * a previous round and then we get here for another round, we'll |
| * immediately "timeout" again before optimizing any of the Optimizables |
| * in our list. This is okay if we don't have any predicates from |
| * outer queries because in that case the plan we find this round |
| * will be the same one we found in the previous round, in which |
| * case there's no point in resetting the timeout state and doing |
| * the work a second time. But if we have predicates from an outer |
| * query, those predicates could help us find a much better plan |
| * this round than we did in previous rounds--so we reset the timeout |
| * state to ensure that we have a chance to consider plans that |
| * can take advantage of the pushed predicates. |
| */ |
| usingPredsPushedFromAbove = false; |
| if ((predicateList != null) && (predicateList.size() > 0)) |
| { |
| for (int i = predicateList.size() - 1; i >= 0; i--) |
| { |
| // If the predicate is "scoped", then we know it was pushed |
| // here from an outer query. |
| if (((Predicate)predicateList. |
| getOptPredicate(i)).isScopedForPush()) |
| { |
| usingPredsPushedFromAbove = true; |
| break; |
| } |
| } |
| } |
| |
| if (usingPredsPushedFromAbove) |
| { |
| timeOptimizationStarted = System.currentTimeMillis(); |
| timeExceeded = false; |
| } |
| |
| /* If user specified the optimizer override for a fixed |
| * join order, then desiredJoinOrderFound could be true |
| * when we get here. We have to reset it to false in |
| * prep for the next round of optimization. Otherwise |
| * we'd end up quitting the optimization before ever |
| * finding a plan for this round, and that could, among |
| * other things, lead to a never-ending optimization |
| * phase in certain situations. DERBY-1866. |
| */ |
| desiredJoinOrderFound = false; |
| |
| /* |
| * If we JUMPed permutations last round, it's possible that we timed out |
| * before finishing all of the jump processing (most likely we ended in |
| * the middle of a WALK_LOW). So reset the jump state here to make sure |
| * we get a clean start. Failure to do so can lead to execution of |
| * code-paths that are not expected and thus incorrect cost estimates |
| * (most notably, an uninitialized bestCost, which we should never see). |
| * DERBY-1905. |
| */ |
| initJumpState(); |
| } |
| |
| /** |
| * Determine if we want to try "jumping" permutations with this |
| * OptimizerImpl, and (re-)initialize the permuteState field accordingly. |
| */ |
| private int initJumpState() { |
| permuteState = (numTablesInQuery >= 6 ? READY_TO_JUMP : NO_JUMP); |
| return permuteState; |
| } |
| |
| private boolean tracingIsOn() { return lcc.optimizerTracingIsOn(); } |
| |
| public int getMaxMemoryPerTable() |
| { |
| return maxMemoryPerTable; |
| } |
| |
| /** |
| * @see Optimizer#getNextPermutation |
| * |
| * @exception StandardException Thrown on error |
| */ |
| public boolean getNextPermutation() |
| throws StandardException |
| { |
| /* Don't get any permutations if there is nothing to optimize */ |
| if (numOptimizables < 1) |
| { |
| if ( tracingIsOn() ) { tracer().traceVacuous(); } |
| |
| endOfRoundCleanup(); |
| return false; |
| } |
| |
| /* Make sure that all Optimizables init their access paths. |
| * (They wait until optimization since the access path |
| * references the optimizer.) |
| */ |
| optimizableList.initAccessPaths(this); |
| |
| /* |
| ** Experiments show that optimization time only starts to |
| ** become a problem with seven tables, so only check for |
| ** too much time if there are more than seven tables. |
| ** Also, don't check for too much time if user has specified |
| ** no timeout. |
| */ |
| if ( ( ! timeExceeded ) && |
| (numTablesInQuery > 6) && |
| ( ! noTimeout) ) |
| { |
| /* |
| ** Stop optimizing if the time spent optimizing is greater than |
| ** the current best cost. |
| */ |
| currentTime = System.currentTimeMillis(); |
| timeExceeded = (currentTime - timeOptimizationStarted) > timeLimit; |
| |
| if (tracingIsOn() && timeExceeded) |
| { |
| tracer().traceTimeout( currentTime, bestCost ); |
| } |
| } |
| |
| if (bestCost.isUninitialized() && foundABestPlan && |
| ((!usingPredsPushedFromAbove && !bestJoinOrderUsedPredsFromAbove) |
| || timeExceeded)) |
| { |
| /* We can get here if this OptimizerImpl is for a subquery |
| * that timed out for a previous permutation of the outer |
| * query, but then the outer query itself did _not_ timeout. |
| * In that case we'll end up back here for another round of |
| * optimization, but our timeExceeded flag will be true. |
| * We don't want to reset all of the timeout state here |
| * because that could lead to redundant work (see comments |
| * in prepForNextRound()), but we also don't want to return |
| * without having a plan, because then we'd return an unfairly |
| * high "bestCost" value--i.e. Double.MAX_VALUE. Note that |
| * we can't just revert back to whatever bestCost we had |
| * prior to this because that cost is for some previous |
| * permutation of the outer query--not the current permutation-- |
| * and thus would be incorrect. So instead we have to delay |
| * the timeout until we find a complete (and valid) join order, |
| * so that we can return a valid cost estimate. Once we have |
| * a valid cost we'll then go through the timeout logic |
| * and stop optimizing. |
| * |
| * All of that said, instead of just trying the first possible |
| * join order, we jump to the join order that gave us the best |
| * cost in previous rounds. We know that such a join order exists |
| * because that's how our timeout value was set to begin with--so |
| * if there was no best join order, we never would have timed out |
| * and thus we wouldn't be here. |
| * |
| * We can also get here if we've already optimized the list |
| * of optimizables once (in a previous round of optimization) |
| * and now we're back to do it again. If that's true AND |
| * we did *not* receive any predicates pushed from above AND |
| * the bestJoinOrder from the previous round did *not* depend |
| * on predicates pushed from above, then we'll jump to the |
| * previous join order and start there. NOTE: if after jumping |
| * to the previous join order and calculating the cost we haven't |
| * timed out, we will continue looking at other join orders (as |
| * usual) until we exhaust them all or we time out. |
| */ |
| if (permuteState != JUMPING) |
| { |
| // By setting firstLookOrder to our target join order |
| // and then setting our permuteState to JUMPING, we'll |
| // jump to the target join order and get the cost. That |
| // cost will then be saved as bestCost, allowing us to |
| // proceed with normal timeout logic. |
| if (firstLookOrder == null) |
| firstLookOrder = new int[numOptimizables]; |
| System.arraycopy( |
| bestJoinOrder, 0, firstLookOrder, 0, numOptimizables); |
| permuteState = JUMPING; |
| |
| /* If we already assigned at least one position in the |
| * join order when this happened (i.e. if joinPosition |
| * is greater than *or equal* to zero; DERBY-1777), then |
| * reset the join order before jumping. The call to |
| * rewindJoinOrder() here will put joinPosition back |
| * to 0. But that said, we'll then end up incrementing |
| * joinPosition before we start looking for the next |
| * join order (see below), which means we need to set |
| * it to -1 here so that it gets incremented to "0" and |
| * then processing can continue as normal from there. |
| * Note: we don't need to set reloadBestPlan to true |
| * here because we only get here if we have *not* found |
| * a best plan yet. |
| */ |
| if (joinPosition >= 0) |
| { |
| rewindJoinOrder(); |
| joinPosition = -1; |
| } |
| } |
| |
| // Reset the timeExceeded flag so that we'll keep going |
| // until we find a complete join order. NOTE: we intentionally |
| // do _not_ reset the timeOptimizationStarted value because we |
| // we want to go through this timeout logic for every |
| // permutation, to make sure we timeout as soon as we have |
| // our first complete join order. |
| timeExceeded = false; |
| } |
| |
| /* |
| ** Pick the next table in the join order, if there is an unused position |
| ** in the join order, and the current plan is less expensive than |
| ** the best plan so far, and the amount of time spent optimizing is |
| ** still less than the cost of the best plan so far, and a best |
| ** cost has been found in the current join position. Otherwise, |
| ** just pick the next table in the current position. |
| */ |
| boolean joinPosAdvanced = false; |
| |
| /* Determine if the current plan is still less expensive than |
| * the best plan so far. If bestCost is uninitialized then |
| * we want to return false here; if we didn't, then in the (rare) |
| * case where the current cost is greater than Double.MAX_VALUE |
| * (esp. if it's Double.POSITIVE_INFINITY, which can occur |
| * for very deeply nested queries with long FromLists) we would |
| * give up on the current plan even though we didn't have a |
| * best plan yet, which would be wrong. Also note: if we have |
| * a required row ordering then we might end up using the |
| * sort avoidance plan--but we don't know at this point |
| * which plan (sort avoidance or "normal") we're going to |
| * use, so we error on the side of caution and only short- |
| * circuit if both currentCost and currentSortAvoidanceCost |
| * (if the latter is applicable) are greater than bestCost. |
| */ |
| boolean alreadyCostsMore = |
| !bestCost.isUninitialized() && |
| (currentCost.compare(bestCost) > 0) && |
| ((requiredRowOrdering == null) || |
| (currentSortAvoidanceCost.compare(bestCost) > 0)); |
| |
| if ((joinPosition < (numOptimizables - 1)) && |
| !alreadyCostsMore && |
| ( ! timeExceeded ) |
| ) |
| { |
| /* |
| ** Are we either starting at the first join position (in which |
| ** case joinPosition will be -1), or has a best cost been found |
| ** in the current join position? The latter case might not be |
| ** true if there is no feasible join order. |
| */ |
| if ((joinPosition < 0) || |
| optimizableList.getOptimizable( |
| proposedJoinOrder[joinPosition]). |
| getBestAccessPath().getCostEstimate() != null) |
| { |
| joinPosition++; |
| joinPosAdvanced = true; |
| |
| /* |
| ** When adding a table to the join order, the best row |
| ** row ordering for the outer tables becomes the starting |
| ** point for the row ordering of the current table. |
| */ |
| bestRowOrdering.copy(currentRowOrdering); |
| } |
| } |
| else |
| { |
| // If we short-circuited the current join order then we need |
| // to make sure that, when we start pulling optimizables to find |
| // a new join order, we reload the best plans for those |
| // optimizables as we pull them. Otherwise we could end up |
| // generating a plan for an optimizable even though that plan |
| // was part of a short-circuited (and thus rejected) join |
| // order. |
| if (joinPosition < (numOptimizables - 1)) |
| { |
| if (tracingIsOn()) |
| { |
| tracer().traceShortCircuiting |
| ( |
| timeExceeded, optimizableList.getOptimizable( proposedJoinOrder[joinPosition] ), joinPosition |
| ); |
| } |
| |
| reloadBestPlan = true; |
| } |
| } |
| |
| if (permuteState == JUMPING && !joinPosAdvanced && joinPosition >= 0) |
| { |
| //not feeling well in the middle of jump |
| // Note: we have to make sure we reload the best plans |
| // as we rewind since they may have been clobbered |
| // (as part of the current join order) before we gave |
| // up on jumping. |
| reloadBestPlan = true; |
| rewindJoinOrder(); //fall |
| permuteState = NO_JUMP; //give up |
| } |
| |
| /* |
| ** The join position becomes < 0 when all the permutations have been |
| ** looked at. |
| */ |
| while (joinPosition >= 0) |
| { |
| int nextOptimizable = proposedJoinOrder[joinPosition] + 1; |
| if (proposedJoinOrder[joinPosition] >= 0) |
| { |
| /* We are either going to try another table at the current |
| * join order position, or we have exhausted all the tables |
| * at the current join order position. In either case, we |
| * need to pull the table at the current join order position |
| * and remove it from the join order. Do this BEFORE we |
| * search for the next optimizable so that assignedTableMap, |
| * which is updated to reflect the PULL, has the correct |
| * information for enforcing join order depdendencies. |
| * DERBY-3288. |
| */ |
| pullOptimizableFromJoinOrder(); |
| } |
| |
| if (desiredJoinOrderFound || timeExceeded) |
| { |
| /* |
| ** If the desired join order has been found (which will happen |
| ** if the user specifies a join order), pretend that there are |
| ** no more optimizables at this join position. This will cause |
| ** us to back out of the current join order. |
| ** |
| ** Also, don't look at any more join orders if we have taken |
| ** too much time with this optimization. |
| */ |
| nextOptimizable = numOptimizables; |
| } |
| else if (permuteState == JUMPING) //still jumping |
| { |
| /* We're "jumping" to a join order that puts the optimizables |
| ** with the lowest estimated costs first (insofar as it |
| ** is legal to do so). The "firstLookOrder" array holds the |
| ** ideal join order for position <joinPosition> up thru |
| ** position <numOptimizables-1>. So here, we look at the |
| ** ideal optimizable to place at <joinPosition> and see if |
| ** it's legal; if it is, then we're done. Otherwise, we |
| ** swap it with <numOptimizables-1> and see if that gives us |
| ** a legal join order w.r.t <joinPosition>. If not, then we |
| ** swap it with <numOptimizables-2> and check, and if that |
| ** fails, then we swap it with <numOptimizables-3>, and so |
| ** on. For example, assume we have 6 optimizables whose |
| ** order from least expensive to most expensive is 2, 1, 4, |
| ** 5, 3, 0. Assume also that we've already verified the |
| ** legality of the first two positions--i.e. that joinPosition |
| ** is now "2". That means that "firstLookOrder" currently |
| ** contains the following: |
| ** |
| ** [ pos ] 0 1 2 3 4 5 |
| ** [ opt ] 2 1 4 5 3 0 |
| ** |
| ** Then at this point, we do the following: |
| ** |
| ** -- Check to see if the ideal optimizable "4" is valid |
| ** at its current position (2) |
| ** -- If opt "4" is valid, then we're done; else we |
| ** swap it with the value at position _5_: |
| ** |
| ** [ pos ] 0 1 2 3 4 5 |
| ** [ opt ] 2 1 0 5 3 4 |
| ** |
| ** -- Check to see if optimizable "0" is valid at its |
| ** new position (2). |
| ** -- If opt "0" is valid, then we're done; else we |
| ** put "0" back in its original position and swap |
| ** the ideal optimizer ("4") with the value at |
| ** position _4_: |
| ** |
| ** [ pos ] 0 1 2 3 4 5 |
| ** [ opt ] 2 1 3 5 4 0 |
| ** |
| ** -- Check to see if optimizable "3" is valid at its |
| ** new position (2). |
| ** -- If opt "3" is valid, then we're done; else we |
| ** put "3" back in its original position and swap |
| ** the ideal optimizer ("4") with the value at |
| ** position _3_: |
| ** |
| ** [ pos ] 0 1 2 3 4 5 |
| ** [ opt ] 2 1 5 4 3 0 |
| ** |
| ** -- Check to see if optimizable "5" is valid at its |
| ** new position (2). |
| ** -- If opt "5" is valid, then we're done; else we've |
| ** tried all the available optimizables and none |
| ** of them are legal at position 2. In this case, |
| ** we give up on "JUMPING" and fall back to normal |
| ** join-order processing. |
| */ |
| |
| int idealOptimizable = firstLookOrder[joinPosition]; |
| nextOptimizable = idealOptimizable; |
| int lookPos = numOptimizables; |
| int lastSwappedOpt = -1; |
| |
| Optimizable nextOpt; |
| for (nextOpt = optimizableList.getOptimizable(nextOptimizable); |
| !(nextOpt.legalJoinOrder(assignedTableMap)); |
| nextOpt = optimizableList.getOptimizable(nextOptimizable)) |
| { |
| // Undo last swap, if we had one. |
| if (lastSwappedOpt >= 0) { |
| firstLookOrder[joinPosition] = idealOptimizable; |
| firstLookOrder[lookPos] = lastSwappedOpt; |
| } |
| |
| if (lookPos > joinPosition + 1) { |
| // we still have other possibilities; get the next |
| // one by "swapping" it into the current position. |
| lastSwappedOpt = firstLookOrder[--lookPos]; |
| firstLookOrder[joinPosition] = lastSwappedOpt; |
| firstLookOrder[lookPos] = idealOptimizable; |
| nextOptimizable = lastSwappedOpt; |
| } |
| else { |
| // we went through all of the available optimizables |
| // and none of them were legal in the current position; |
| // so we give up and fall back to normal processing. |
| // Note: we have to make sure we reload the best plans |
| // as we rewind since they may have been clobbered |
| // (as part of the current join order) before we got |
| // here. |
| if (joinPosition > 0) { |
| joinPosition--; |
| reloadBestPlan = true; |
| rewindJoinOrder(); |
| } |
| permuteState = NO_JUMP; |
| break; |
| } |
| } |
| |
| if (permuteState == NO_JUMP) |
| continue; |
| |
| if (joinPosition == numOptimizables - 1) { |
| // we just set the final position within our |
| // "firstLookOrder" join order; now go ahead |
| // and search for the best join order, starting from |
| // the join order stored in "firstLookOrder". This |
| // is called walking "high" because we're searching |
| // the join orders that are at or "above" (after) the |
| // order found in firstLookOrder. Ex. if we had three |
| // optimizables and firstLookOrder was [1 2 0], then |
| // the "high" would be [1 2 0], [2 0 1] and [2 1 0]; |
| // the "low" would be [0 1 2], [0 2 1], and [1 0 2]. |
| // We walk the "high" first, then fall back and |
| // walk the "low". |
| permuteState = WALK_HIGH; |
| } |
| } |
| else |
| { |
| /* Find the next unused table at this join position */ |
| for ( ; nextOptimizable < numOptimizables; nextOptimizable++) |
| { |
| boolean found = false; |
| for (int posn = 0; posn < joinPosition; posn++) |
| { |
| /* |
| ** Is this optimizable already somewhere |
| ** in the join order? |
| */ |
| if (proposedJoinOrder[posn] == nextOptimizable) |
| { |
| found = true; |
| break; |
| } |
| } |
| |
| /* No need to check the dependencies if the optimizable |
| * is already in the join order--because we should have |
| * checked its dependencies before putting it there. |
| */ |
| if (found) |
| { |
| if (SanityManager.DEBUG) |
| { |
| // Doesn't hurt to check in SANE mode, though... |
| if ((nextOptimizable < numOptimizables) && |
| !joinOrderMeetsDependencies(nextOptimizable)) |
| { |
| SanityManager.THROWASSERT( |
| "Found optimizable '" + nextOptimizable + |
| "' in current join order even though " + |
| "its dependencies were NOT satisfied."); |
| } |
| } |
| |
| continue; |
| } |
| |
| /* Check to make sure that all of the next optimizable's |
| * dependencies have been satisfied. |
| */ |
| if ((nextOptimizable < numOptimizables) && |
| !joinOrderMeetsDependencies(nextOptimizable)) |
| { |
| if (tracingIsOn()) |
| { |
| tracer().traceSkippingJoinOrder |
| ( nextOptimizable, joinPosition, ArrayUtil.copy( proposedJoinOrder ), (JBitSet) assignedTableMap.clone() ); |
| } |
| |
| /* |
| ** If this is a user specified join order then it is illegal. |
| */ |
| if ( ! optimizableList.optimizeJoinOrder()) |
| { |
| if (tracingIsOn()) { tracer().traceIllegalUserJoinOrder(); } |
| |
| throw StandardException.newException( |
| SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER); |
| } |
| |
| continue; |
| } |
| |
| break; |
| } |
| } |
| |
| /* Have we exhausted all the optimizables at this join position? */ |
| if (nextOptimizable >= numOptimizables) |
| { |
| /* |
| ** If we're not optimizing the join order, remember the first |
| ** join order. |
| */ |
| if ( ! optimizableList.optimizeJoinOrder()) |
| { |
| // Verify that the user specified a legal join order |
| if ( ! optimizableList.legalJoinOrder(numTablesInQuery)) |
| { |
| if (tracingIsOn()) { tracer().traceIllegalUserJoinOrder(); } |
| |
| throw StandardException.newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER); |
| } |
| |
| if (tracingIsOn()) { tracer().traceUserJoinOrderOptimized(); } |
| |
| desiredJoinOrderFound = true; |
| } |
| |
| if (permuteState == READY_TO_JUMP && joinPosition > 0 && joinPosition == numOptimizables-1) |
| { |
| permuteState = JUMPING; |
| |
| /* A simple heuristics is that the row count we got |
| * indicates a potentially good join order. We'd like row |
| * count to get big as late as possible, so |
| * that less load is carried over. |
| */ |
| double rc[] = new double[numOptimizables]; |
| for (int i = 0; i < numOptimizables; i++) |
| { |
| firstLookOrder[i] = i; |
| CostEstimate ce = optimizableList.getOptimizable(i). |
| getBestAccessPath().getCostEstimate(); |
| if (ce == null) |
| { |
| permuteState = READY_TO_JUMP; //come again? |
| break; |
| } |
| rc[i] = ce.singleScanRowCount(); |
| } |
| if (permuteState == JUMPING) |
| { |
| boolean doIt = false; |
| int temp; |
| for (int i = 0; i < numOptimizables; i++) //simple selection sort |
| { |
| int k = i; |
| for (int j = i+1; j < numOptimizables; j++) |
| if (rc[j] < rc[k]) k = j; |
| if (k != i) |
| { |
| rc[k] = rc[i]; //destroy the bridge |
| temp = firstLookOrder[i]; |
| firstLookOrder[i] = firstLookOrder[k]; |
| firstLookOrder[k] = temp; |
| doIt = true; |
| } |
| } |
| |
| if (doIt) |
| { |
| joinPosition--; |
| rewindJoinOrder(); //jump from ground |
| continue; |
| } |
| else permuteState = NO_JUMP; //never |
| } |
| } |
| |
| /* |
| ** We have exhausted all the optimizables at this level. |
| ** Go back up one level. |
| */ |
| |
| /* Go back up one join position */ |
| joinPosition--; |
| |
| if (joinPosition < 0 && permuteState == WALK_HIGH) //reached peak |
| { |
| joinPosition = 0; //reset, fall down the hill |
| permuteState = WALK_LOW; |
| } |
| continue; |
| } |
| |
| /* |
| ** We have found another optimizable to try at this join position. |
| */ |
| proposedJoinOrder[joinPosition] = nextOptimizable; |
| |
| if (permuteState == WALK_LOW) |
| { |
| boolean finishedCycle = true; |
| for (int i = 0; i < numOptimizables; i++) |
| { |
| if (proposedJoinOrder[i] < firstLookOrder[i]) |
| { |
| finishedCycle = false; |
| break; |
| } |
| else if (proposedJoinOrder[i] > firstLookOrder[i]) //done |
| break; |
| } |
| if (finishedCycle) |
| { |
| // We just set proposedJoinOrder[joinPosition] above, so |
| // if we're done we need to put it back to -1 to indicate |
| // that it's an empty slot. Then we rewind and pull any |
| // other Optimizables at positions < joinPosition. |
| // Note: we have to make sure we reload the best plans |
| // as we rewind since they may have been clobbered |
| // (as part of the current join order) before we got |
| // here. |
| proposedJoinOrder[joinPosition] = -1; |
| joinPosition--; |
| if (joinPosition >= 0) |
| { |
| reloadBestPlan = true; |
| rewindJoinOrder(); |
| joinPosition = -1; |
| } |
| |
| permuteState = READY_TO_JUMP; |
| endOfRoundCleanup(); |
| return false; |
| } |
| } |
| |
| /* Re-init (clear out) the cost for the best access path |
| * when placing a table. |
| */ |
| optimizableList.getOptimizable(nextOptimizable). |
| getBestAccessPath().setCostEstimate((CostEstimate) null); |
| |
| if (tracingIsOn()) |
| { |
| tracer().traceJoinOrderConsideration |
| ( joinPosition, ArrayUtil.copy( proposedJoinOrder ), (JBitSet) assignedTableMap.clone() ); |
| } |
| |
| Optimizable nextOpt = |
| optimizableList.getOptimizable(nextOptimizable); |
| |
| /* Update the assigned table map to include the newly-placed |
| * Optimizable in the current join order. Assumption is that |
| * this OR can always be undone using an XOR, which will only |
| * be true if none of the Optimizables have overlapping table |
| * maps. The XOR itself occurs as part of optimizable "PULL" |
| * processing. |
| */ |
| if (SanityManager.DEBUG) |
| { |
| JBitSet optMap = |
| (JBitSet)nextOpt.getReferencedTableMap().clone(); |
| |
| optMap.and(assignedTableMap); |
| if (optMap.getFirstSetBit() != -1) |
| { |
| SanityManager.THROWASSERT( |
| "Found multiple optimizables that share one or " + |
| "more referenced table numbers (esp: '" + |
| optMap + "'), but that should not be the case."); |
| } |
| } |
| |
| assignedTableMap.or(nextOpt.getReferencedTableMap()); |
| nextOpt.startOptimizing(this, currentRowOrdering); |
| |
| pushPredicates( |
| optimizableList.getOptimizable(nextOptimizable), |
| assignedTableMap); |
| |
| return true; |
| } |
| |
| endOfRoundCleanup(); |
| return false; |
| } |
| |
| private void rewindJoinOrder() |
| throws StandardException |
| { |
| for (; ; joinPosition--) |
| { |
| Optimizable pullMe = |
| optimizableList.getOptimizable( |
| proposedJoinOrder[joinPosition]); |
| pullMe.pullOptPredicates(predicateList); |
| if (reloadBestPlan) |
| pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this); |
| proposedJoinOrder[joinPosition] = -1; |
| if (joinPosition == 0) break; |
| } |
| currentCost.setCost(0.0d, 0.0d, 0.0d); |
| currentSortAvoidanceCost.setCost(0.0d, 0.0d, 0.0d); |
| assignedTableMap.clearAll(); |
| } |
| |
| /** |
| * 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. |
| */ |
| private void endOfRoundCleanup() |
| throws StandardException |
| { |
| for (int i = 0; i < numOptimizables; i++) |
| { |
| optimizableList.getOptimizable(i). |
| updateBestPlanMap(FromTable.REMOVE_PLAN, this); |
| } |
| } |
| |
| /** |
| * 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. |
| */ |
| private double recoverCostFromProposedJoinOrder(boolean sortAvoidance) |
| throws StandardException |
| { |
| double recoveredCost = 0.0d; |
| for (int i = 0; i < joinPosition; i++) |
| { |
| if (sortAvoidance) |
| { |
| recoveredCost += |
| optimizableList.getOptimizable(proposedJoinOrder[i]) |
| .getBestSortAvoidancePath().getCostEstimate() |
| .getEstimatedCost(); |
| } |
| else |
| { |
| recoveredCost += |
| optimizableList.getOptimizable(proposedJoinOrder[i]) |
| .getBestAccessPath().getCostEstimate() |
| .getEstimatedCost(); |
| } |
| } |
| |
| return recoveredCost; |
| } |
| |
| /** |
| * 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. |
| */ |
| private boolean joinOrderMeetsDependencies(int optNumber) |
| throws StandardException |
| { |
| Optimizable nextOpt = optimizableList.getOptimizable(optNumber); |
| return nextOpt.legalJoinOrder(assignedTableMap); |
| } |
| |
| /** |
| * Pull whatever optimizable is at joinPosition in the proposed |
| * join order from the join order, and update all corresponding |
| * state accordingly. |
| */ |
| private void pullOptimizableFromJoinOrder() |
| throws StandardException |
| { |
| Optimizable pullMe = |
| optimizableList.getOptimizable(proposedJoinOrder[joinPosition]); |
| |
| /* |
| ** Subtract the cost estimate of the optimizable being |
| ** removed from the total cost estimate. |
| ** |
| ** The total cost is the sum of all the costs, but the total |
| ** number of rows is the number of rows returned by the |
| ** innermost optimizable. |
| */ |
| double prevRowCount; |
| double prevSingleScanRowCount; |
| int prevPosition = 0; |
| if (joinPosition == 0) |
| { |
| prevRowCount = outermostCostEstimate.rowCount(); |
| prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount(); |
| } |
| else |
| { |
| prevPosition = proposedJoinOrder[joinPosition - 1]; |
| CostEstimate localCE = |
| optimizableList. |
| getOptimizable(prevPosition). |
| getBestAccessPath(). |
| getCostEstimate(); |
| prevRowCount = localCE.rowCount(); |
| prevSingleScanRowCount = localCE.singleScanRowCount(); |
| } |
| |
| /* |
| ** If there is no feasible join order, the cost estimate |
| ** in the best access path may never have been set. |
| ** In this case, do not subtract anything from the |
| ** current cost, since nothing was added to the current |
| ** cost. |
| */ |
| double newCost = currentCost.getEstimatedCost(); |
| CostEstimate pullCostEstimate = |
| pullMe.getBestAccessPath().getCostEstimate(); |
| if (pullCostEstimate != null) |
| { |
| double pullCost = pullCostEstimate.getEstimatedCost(); |
| |
| newCost -= pullCost; |
| |
| /* |
| ** It's possible for newCost to go negative here due to |
| ** loss of precision--but that should ONLY happen if the |
| ** optimizable we just pulled was at position 0. If we |
| ** have a newCost that is <= 0 at any other time, then |
| ** it's the result of a different kind of precision loss-- |
| ** namely, the estimated cost of pullMe was so large that |
| ** we lost the precision of the accumulated cost as it |
| ** existed prior to pullMe. Then when we subtracted |
| ** pullMe's cost out, we ended up setting newCost to zero. |
| ** That's an unfortunate side effect of optimizer cost |
| ** estimates that grow too large. If that's what happened |
| ** here,try to make some sense of things by adding up costs |
| ** as they existed prior to pullMe... |
| */ |
| if (newCost <= 0.0) |
| { |
| if (joinPosition == 0) |
| newCost = 0.0; |
| else |
| newCost = recoverCostFromProposedJoinOrder(false); |
| } |
| } |
| |
| /* If we are choosing a new outer table, then |
| * we rest the starting cost to the outermostCost. |
| * (Thus avoiding any problems with floating point |
| * accuracy and going negative.) |
| */ |
| if (joinPosition == 0) |
| { |
| if (outermostCostEstimate != null) |
| { |
| newCost = outermostCostEstimate.getEstimatedCost(); |
| } |
| else |
| { |
| newCost = 0.0; |
| } |
| } |
| |
| currentCost.setCost( |
| newCost, |
| prevRowCount, |
| prevSingleScanRowCount); |
| |
| /* |
| ** Subtract from the sort avoidance cost if there is a |
| ** required row ordering. |
| ** |
| ** NOTE: It is not necessary here to check whether the |
| ** best cost was ever set for the sort avoidance path, |
| ** because it considerSortAvoidancePath() would not be |
| ** set if there cost were not set. |
| */ |
| if (requiredRowOrdering != null) |
| { |
| if (pullMe.considerSortAvoidancePath()) |
| { |
| AccessPath ap = pullMe.getBestSortAvoidancePath(); |
| double prevEstimatedCost; |
| |
| /* |
| ** Subtract the sort avoidance cost estimate of the |
| ** optimizable being removed from the total sort |
| ** avoidance cost estimate. |
| ** |
| ** The total cost is the sum of all the costs, but the |
| ** total number of rows is the number of rows returned |
| ** by the innermost optimizable. |
| */ |
| if (joinPosition == 0) |
| { |
| prevRowCount = outermostCostEstimate.rowCount(); |
| prevSingleScanRowCount = |
| outermostCostEstimate.singleScanRowCount(); |
| |
| /* If we are choosing a new outer table, then |
| * we rest the starting cost to the outermostCost. |
| * (Thus avoiding any problems with floating point |
| * accuracy and going negative.) |
| */ |
| prevEstimatedCost = |
| outermostCostEstimate.getEstimatedCost(); |
| } |
| else |
| { |
| CostEstimate localCE = |
| optimizableList. |
| getOptimizable(prevPosition). |
| getBestSortAvoidancePath(). |
| getCostEstimate(); |
| prevRowCount = localCE.rowCount(); |
| prevSingleScanRowCount = localCE.singleScanRowCount(); |
| prevEstimatedCost = |
| currentSortAvoidanceCost.getEstimatedCost() - |
| ap.getCostEstimate().getEstimatedCost(); |
| } |
| |
| // See discussion above for "newCost"; same applies here. |
| if (prevEstimatedCost <= 0.0) |
| { |
| if (joinPosition == 0) |
| prevEstimatedCost = 0.0; |
| else |
| { |
| prevEstimatedCost = |
| recoverCostFromProposedJoinOrder(true); |
| } |
| } |
| |
| currentSortAvoidanceCost.setCost( |
| prevEstimatedCost, |
| prevRowCount, |
| prevSingleScanRowCount); |
| |
| /* |
| ** Remove the table from the best row ordering. |
| ** It should not be necessary to remove it from |
| ** the current row ordering, because it is |
| ** maintained as we step through the access paths |
| ** for the current Optimizable. |
| */ |
| bestRowOrdering.removeOptimizable(pullMe.getTableNumber()); |
| |
| /* |
| ** When removing a table from the join order, |
| ** the best row ordering for the remaining outer tables |
| ** becomes the starting point for the row ordering of |
| ** the current table. |
| */ |
| bestRowOrdering.copy(currentRowOrdering); |
| } |
| } |
| |
| /* |
| ** Pull the predicates at from the optimizable and put |
| ** them back in the predicate list. |
| ** |
| ** NOTE: This is a little inefficient because it pulls the |
| ** single-table predicates, which are guaranteed to always |
| ** be pushed to the same optimizable. We could make this |
| ** leave the single-table predicates where they are. |
| */ |
| pullMe.pullOptPredicates(predicateList); |
| |
| /* |
| ** When we pull an Optimizable we need to go through and |
| ** load whatever best path we found for that Optimizable |
| ** with respect to this OptimizerImpl. The reason is that |
| ** we could be pulling the Optimizable for the last time |
| ** (before returning false), in which case we want it (the |
| ** Optimizable) to be holding the best access path that it |
| ** had at the time we found bestJoinOrder. This ensures |
| ** that the access path which is generated and executed for |
| ** the Optimizable matches the the access path decisions |
| ** made by this OptimizerImpl for the best join order. |
| ** |
| ** NOTE: We we only reload the best plan if it's necessary |
| ** to do so--i.e. if the best plans aren't already loaded. |
| ** The plans will already be loaded if the last complete |
| ** join order we had was the best one so far, because that |
| ** means we called "rememberAsBest" on every Optimizable |
| ** in the list and, as part of that call, we will run through |
| ** and set trulyTheBestAccessPath for the entire subtree. |
| ** So if we haven't tried any other plans since then, |
| ** we know that every Optimizable (and its subtree) already |
| ** has the correct best plan loaded in its trulyTheBest |
| ** path field. It's good to skip the load in this case |
| ** because 'reloading best plans' involves walking the |
| ** entire subtree of _every_ Optimizable in the list, which |
| ** can be expensive if there are deeply nested subqueries. |
| */ |
| if (reloadBestPlan) |
| pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this); |
| |
| /* Mark current join position as unused */ |
| proposedJoinOrder[joinPosition] = -1; |
| |
| /* If we didn't advance the join position then the optimizable |
| * which currently sits at proposedJoinOrder[joinPosition]--call |
| * it PULL_ME--is *not* going to remain there. Instead, we're |
| * going to pull that optimizable from its position and attempt |
| * to put another one in its place. That said, when we try to |
| * figure out which of the other optimizables to place at |
| * joinPosition, we'll first do some "dependency checking", the |
| * result of which relies on the contents of assignedTableMap. |
| * Since assignedTableMap currently holds info about PULL_ME |
| * and since PULL_ME is *not* going to remain in the join order, |
| * we need to remove the info for PULL_ME from assignedTableMap. |
| * Otherwise an Optimizable which depends on PULL_ME could |
| * incorrectly be placed in the join order *before* PULL_ME, |
| * which would violate the dependency and lead to incorrect |
| * results. DERBY-3288. |
| */ |
| assignedTableMap.xor(pullMe.getReferencedTableMap()); |
| } |
| |
| /* |
| ** Push predicates from this optimizer's list to the given optimizable, |
| ** as appropriate given the outer tables. |
| ** |
| ** @param curTable The Optimizable to push predicates down to |
| ** @param outerTables A bit map of outer tables |
| ** |
| ** @exception StandardException Thrown on error |
| */ |
| void pushPredicates(Optimizable curTable, JBitSet outerTables) |
| throws StandardException |
| { |
| /* |
| ** Push optimizable clauses to current position in join order. |
| ** |
| ** RESOLVE - We do not push predicates with subqueries not materializable. |
| */ |
| |
| int numPreds = predicateList.size(); |
| JBitSet predMap = new JBitSet(numTablesInQuery); |
| JBitSet curTableNums = null; |
| BaseTableNumbersVisitor btnVis = null; |
| int tNum; |
| Predicate pred; |
| |
| /* Walk the OptimizablePredicateList. For each OptimizablePredicate, |
| * see if it can be assigned to the Optimizable at the current join |
| * position. |
| * |
| * NOTE - We walk the OPL backwards since we will hopefully be deleted |
| * entries as we walk it. |
| */ |
| for (int predCtr = numPreds - 1; predCtr >= 0; predCtr--) |
| { |
| pred = (Predicate)predicateList.getOptPredicate(predCtr); |
| |
| /* Skip over non-pushable predicates */ |
| if (! isPushable(pred)) |
| { |
| continue; |
| } |
| |
| /* Make copy of referenced map so that we can do destructive |
| * manipulation on the copy. |
| */ |
| predMap.setTo(pred.getReferencedMap()); |
| |
| /* Clear bits representing those tables that have already been |
| * assigned, except for the current table. The outer table map |
| * includes the current table, so if the predicate is ready to |
| * be pushed, predMap will end up with no bits set. |
| */ |
| for (int index = 0; index < predMap.size(); index++) |
| { |
| if (outerTables.get(index)) |
| { |
| predMap.clear(index); |
| } |
| } |
| |
| /* |
| ** Only consider non-correlated variables when deciding where |
| ** to push predicates down to. |
| */ |
| predMap.and(nonCorrelatedTableMap); |
| |
| /* At this point what we've done is figure out what FromTables |
| * the predicate references (using the predicate's "referenced |
| * map") and then: 1) unset the table numbers for any FromTables |
| * that have already been optimized, 2) unset the table number |
| * for curTable, which we are about to optimize, and 3) cleared |
| * out any remaining table numbers which do NOT directly |
| * correspond to UN-optimized FromTables in this OptimizerImpl's |
| * optimizableList. |
| * |
| * Note: the optimizables in this OptImpl's optimizableList are |
| * called "non-correlated". |
| * |
| * So at this point predMap holds a list of tableNumbers which |
| * correspond to "non-correlated" FromTables that are referenced |
| * by the predicate but that have NOT yet been optimized. If any |
| * such FromTable exists then we canNOT push the predicate yet. |
| * We can only push the predicate if every FromTable that it |
| * references either 1) has already been optimized, or 2) is |
| * about to be optimized (i.e. the FromTable is curTable itself). |
| * We can check for this condition by seeing if predMap is empty, |
| * which is what the following line does. |
| */ |
| boolean pushPredNow = (predMap.getFirstSetBit() == -1); |
| |
| /* If the predicate is scoped, there's more work to do. A |
| * scoped predicate's "referenced map" may not be in sync |
| * with its actual column references. Or put another way, |
| * the predicate's referenced map may not actually represent |
| * the tables that are referenced by the predicate. For |
| * example, assume the query tree is something like: |
| * |
| * SelectNode0 |
| * (PRN0, PRN1) |
| * | | |
| * T1 UnionNode |
| * / | |
| * PRN2 PRN3 |
| * | | |
| * SelectNode1 SelectNode2 |
| * (PRN4, PRN5) (PRN6) |
| * | | | |
| * T2 T3 T4 |
| * |
| * Assume further that we have an equijoin predicate between |
| * T1 and the Union node, and that the column reference that |
| * points to the Union ultimately maps to T3. The predicate |
| * will then be scoped to PRN2 and PRN3 and the newly-scoped |
| * predicates will get passed to the optimizers for SelectNode1 |
| * and SelectNode2--which brings us here. Assume for this |
| * example that we're here for SelectNode1 and that "curTable" |
| * is PRN4. Since the predicate has been scoped to SelectNode1, |
| * its referenced map will hold the table numbers for T1 and |
| * PRN2--it will NOT hold the table number for PRN5, even |
| * though PRN5 (T3) is the actual target for the predicate. |
| * Given that, the above logic will determine that the predicate |
| * should be pushed to curTable (PRN4)--but that's not correct. |
| * We said at the start that the predicate ultimately maps to |
| * T3--so we should NOT be pushing it to T2. And hence the |
| * need for some additional logic. DERBY-1866. |
| */ |
| if (pushPredNow && pred.isScopedForPush() && (numOptimizables > 1)) |
| { |
| if (btnVis == null) |
| { |
| curTableNums = new JBitSet(numTablesInQuery); |
| btnVis = new BaseTableNumbersVisitor(curTableNums); |
| } |
| |
| /* What we want to do is find out if the scoped predicate |
| * is really supposed to be pushed to curTable. We do |
| * that by getting the base table numbers referenced by |
| * curTable along with curTable's own table number. Then |
| * we get the base table numbers referenced by the scoped |
| * predicate. If the two sets have at least one table |
| * number in common, then we know that the predicate |
| * should be pushed to curTable. In the above example |
| * predMap will end up holding the base table number |
| * for T3, and thus this check will fail when curTable |
| * is PRN4 but will pass when it is PRN5, which is what |
| * we want. |
| */ |
| tNum = ((FromTable)curTable).getTableNumber(); |
| curTableNums.clearAll(); |
| btnVis.setTableMap(curTableNums); |
| ((FromTable)curTable).accept(btnVis); |
| if (tNum >= 0) |
| curTableNums.set(tNum); |
| |
| btnVis.setTableMap(predMap); |
| pred.accept(btnVis); |
| |
| predMap.and(curTableNums); |
| if ((predMap.getFirstSetBit() == -1)) |
| pushPredNow = false; |
| } |
| |
| /* |
| ** Finally, push the predicate down to the Optimizable at the |
| ** end of the current proposed join order, if it can be evaluated |
| ** there. |
| */ |
| if (pushPredNow) |
| { |
| /* Push the predicate and remove it from the list */ |
| if (curTable.pushOptPredicate(pred)) |
| { |
| predicateList.removeOptPredicate(predCtr); |
| } |
| } |
| } |
| } |
| |
| /** |
| * @see Optimizer#getNextDecoratedPermutation |
| * |
| * @exception StandardException Thrown on error |
| */ |
| public boolean getNextDecoratedPermutation() |
| throws StandardException |
| { |
| boolean retval; |
| Optimizable curOpt = |
| optimizableList.getOptimizable(proposedJoinOrder[joinPosition]); |
| double originalRowCount = 0.0; |
| |
| // RESOLVE: Should we step through the different join strategies here? |
| |
| while ( true ) |
| { |
| /* Returns true until all access paths are exhausted */ |
| retval = curOpt.nextAccessPath(this, (OptimizablePredicateList) null, currentRowOrdering); |
| |
| // if the user didn't specify an explicit plan, we're ok |
| if ( overridingPlan == null ) { break; } |
| if ( !retval ) { break; } |
| |
| // if we've already found the right access path for this location in |
| // the join order, then we move on to the next position |
| if ( currentPlan != null ) |
| { |
| if ( currentPlan.countLeafNodes() == (joinPosition+1) ) |
| { |
| retval = false; |
| break; |
| } |
| } |
| |
| // at this point, figure out if the plan so far is a prefix of the desired plan |
| OptimizerPlan candidate = OptimizerPlan.makeRowSource( getTupleDescriptor( curOpt ), dDictionary ); |
| if ( candidate == null ) |
| { |
| retval = false; |
| break; |
| } |
| if ( currentPlan != null ) |
| { |
| candidate = new OptimizerPlan.Join |
| ( |
| curOpt.getCurrentAccessPath().getJoinStrategy(), |
| currentPlan, |
| candidate |
| ); |
| } |
| |
| if ( candidate.isLeftPrefixOf( overridingPlan ) ) |
| { |
| currentPlan = candidate; |
| break; |
| } |
| |
| // well, that decoration didn't match up with the user-specified plan. |
| // try again |
| } |
| |
| // If the previous path that we considered for curOpt was _not_ the best |
| // path for this round, then we need to revert back to whatever the |
| // best plan for curOpt was this round. Note that the cost estimate |
| // for bestAccessPath could be null here if the last path that we |
| // checked was the only one possible for this round. |
| if ((curOpt.getBestAccessPath().getCostEstimate() != null) && |
| (curOpt.getCurrentAccessPath().getCostEstimate() != null)) |
| { |
| // Note: we can't just check to see if bestCost is cheaper |
| // than currentCost because it's possible that currentCost |
| // is actually cheaper--but it may have been 'rejected' because |
| // it would have required too much memory. So we just check |
| // to see if bestCost and currentCost are different. If so |
| // then we know that the most recent access path (represented |
| // by "current" access path) was not the best. |
| if (curOpt.getBestAccessPath().getCostEstimate().compare( |
| curOpt.getCurrentAccessPath().getCostEstimate()) != 0) |
| { |
| curOpt.updateBestPlanMap(FromTable.LOAD_PLAN, curOpt); |
| } |
| else if (curOpt.getBestAccessPath().getCostEstimate().rowCount() < |
| curOpt.getCurrentAccessPath().getCostEstimate().rowCount()) |
| { |
| // If currentCost and bestCost have the same cost estimate |
| // but currentCost has been rejected because of memory, we |
| // still need to revert the plans. In this case the row |
| // count for currentCost will be greater than the row count |
| // for bestCost, so that's what we just checked. |
| curOpt.updateBestPlanMap(FromTable.LOAD_PLAN, curOpt); |
| } |
| } |
| |
| /* If we needed to revert plans for curOpt, we just did it above. |
| * So we no longer need to keep the previous best plan--and in fact, |
| * keeping it can lead to extreme memory usage for very large |
| * queries. So delete the stored plan for curOpt. DERBY-1315. |
| */ |
| curOpt.updateBestPlanMap(FromTable.REMOVE_PLAN, curOpt); |
| |
| /* |
| ** When all the access paths have been looked at, we know what the |
| ** cheapest one is, so remember it. Only do this if a cost estimate |
| ** has been set for the best access path - one will not have been |
| ** set if no feasible plan has been found. |
| */ |
| CostEstimate ce = curOpt.getBestAccessPath().getCostEstimate(); |
| if ( ( ! retval ) && (ce != null)) |
| { |
| /* |
| ** Add the cost of the current optimizable to the total cost. |
| ** The total cost is the sum of all the costs, but the total |
| ** number of rows is the number of rows returned by the innermost |
| ** optimizable. |
| */ |
| currentCost.setCost( |
| currentCost.getEstimatedCost() + ce.getEstimatedCost(), |
| ce.rowCount(), |
| ce.singleScanRowCount()); |
| |
| if (curOpt.considerSortAvoidancePath() && |
| requiredRowOrdering != null) |
| { |
| /* Add the cost for the sort avoidance path, if there is one */ |
| ce = curOpt.getBestSortAvoidancePath().getCostEstimate(); |
| |
| currentSortAvoidanceCost.setCost( |
| currentSortAvoidanceCost.getEstimatedCost() + |
| ce.getEstimatedCost(), |
| ce.rowCount(), |
| ce.singleScanRowCount()); |
| } |
| |
| if (tracingIsOn()) |
| { |
| tracer().traceCostWithoutSortAvoidance( currentCost ); |
| if (curOpt.considerSortAvoidancePath()) { tracer().traceCostWithSortAvoidance( currentSortAvoidanceCost ); } |
| } |
| |
| /* Do we have a complete join order? */ |
| if ( joinPosition == (numOptimizables - 1) ) |
| { |
| if (tracingIsOn()) { tracer().traceCompleteJoinOrder(); } |
| |
| /* Add cost of sorting to non-sort-avoidance cost */ |
| if (requiredRowOrdering != null) |
| { |
| boolean gotSortCost = false; |
| |
| /* Only get the sort cost once */ |
| if (sortCost == null) |
| { |
| sortCost = newCostEstimate(); |
| } |
| /* requiredRowOrdering records if the bestCost so far is |
| * sort-needed or not, as done in rememberBestCost. If |
| * the bestCost so far is sort-needed, and assume |
| * currentCost is also sort-needed, we want this comparison |
| * to be as accurate as possible. Different plans may |
| * produce different estimated row count (eg., heap scan |
| * vs. index scan during a join), sometimes the difference |
| * could be very big. However the actual row count should |
| * be only one value. So when comparing these two plans, |
| * we want them to have the same sort cost. We want to |
| * take the smaller row count, because a better estimation |
| * (eg. through index) would yield a smaller number. We |
| * adjust the bestCost here if it had a bigger rowCount |
| * estimate. The performance improvement of doing this |
| * sometimes is quite dramatic, eg. from 17 sec to 0.5 sec, |
| * see beetle 4353. |
| */ |
| else if (requiredRowOrdering.getSortNeeded()) |
| { |
| if (bestCost.rowCount() > currentCost.rowCount()) |
| { |
| // adjust bestCost |
| requiredRowOrdering.estimateCost( |
| bestCost.rowCount(), |
| bestRowOrdering, |
| sortCost |
| ); |
| double oldSortCost = sortCost.getEstimatedCost(); |
| requiredRowOrdering.estimateCost( |
| currentCost.rowCount(), |
| bestRowOrdering, |
| sortCost |
| ); |
| gotSortCost = true; |
| bestCost.setCost(bestCost.getEstimatedCost() - |
| oldSortCost + |
| sortCost.getEstimatedCost(), |
| sortCost.rowCount(), |
| currentCost.singleScanRowCount()); |
| } |
| else if (bestCost.rowCount() < currentCost.rowCount()) |
| { |
| // adjust currentCost's rowCount |
| currentCost.setCost(currentCost.getEstimatedCost(), |
| bestCost.rowCount(), |
| currentCost.singleScanRowCount()); |
| } |
| } |
| |
| /* This does not figure out if sorting is necessary, just |
| * an asumption that sort is needed; if the assumption is |
| * wrong, we'll look at sort-avoidance cost as well, later |
| */ |
| if (! gotSortCost) |
| { |
| requiredRowOrdering.estimateCost( |
| currentCost.rowCount(), |
| bestRowOrdering, |
| sortCost |
| ); |
| } |
| |
| originalRowCount = currentCost.rowCount(); |
| |
| currentCost.setCost(currentCost.getEstimatedCost() + |
| sortCost.getEstimatedCost(), |
| sortCost.rowCount(), |
| currentCost.singleScanRowCount() |
| ); |
| |
| if (tracingIsOn()) { tracer().traceSortCost( sortCost, currentCost ); } |
| } |
| |
| /* |
| ** Is the cost of this join order lower than the best one we've |
| ** found so far? |
| ** |
| ** 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. |
| ** |
| ** For very deeply nested queries, it's possible that the optimizer |
| ** will return an estimated cost of Double.INFINITY, which is |
| ** greater than our uninitialized cost of Double.MAX_VALUE and |
| ** thus the "compare" check below will return false. So we have |
| ** to check to see if bestCost is uninitialized and, if so, we |
| ** save currentCost regardless of what value it is--because we |
| ** haven't found anything better yet. |
| ** |
| ** That said, it's also possible for bestCost to be infinity |
| ** AND for current cost to be infinity, as well. In that case |
| ** we can't really tell much by comparing the two, so for lack |
| ** of better alternative we look at the row counts. See |
| ** CostEstimateImpl.compare() for more. |
| */ |
| if ((! foundABestPlan) || |
| (currentCost.compare(bestCost) < 0) || |
| bestCost.isUninitialized()) |
| { |
| rememberBestCost(currentCost, Optimizer.NORMAL_PLAN); |
| |
| // Since we just remembered all of the best plans, |
| // no need to reload them when pulling Optimizables |
| // from this join order. |
| reloadBestPlan = false; |
| } |
| else |
| reloadBestPlan = true; |
| |
| /* Subtract cost of sorting from non-sort-avoidance cost */ |
| if (requiredRowOrdering != null) |
| { |
| /* |
| ** The cost could go negative due to loss of precision. |
| */ |
| double newCost = currentCost.getEstimatedCost() - |
| sortCost.getEstimatedCost(); |
| if (newCost < 0.0) |
| newCost = 0.0; |
| |
| currentCost.setCost(newCost, |
| originalRowCount, |
| currentCost.singleScanRowCount() |
| ); |
| } |
| |
| /* |
| ** This may be the best sort-avoidance plan if there is a |
| ** required row ordering, and we are to consider a sort |
| ** avoidance path on the last Optimizable in the join order. |
| */ |
| if (requiredRowOrdering != null && |
| curOpt.considerSortAvoidancePath()) |
| { |
| if (requiredRowOrdering.sortRequired( |
| bestRowOrdering, |
| optimizableList, |
| proposedJoinOrder) == |
| RequiredRowOrdering.NOTHING_REQUIRED) |
| { |
| if (tracingIsOn()) { tracer().traceCurrentPlanAvoidsSort( bestCost, currentSortAvoidanceCost ); } |
| |
| if ((currentSortAvoidanceCost.compare(bestCost) <= 0) |
| || bestCost.isUninitialized()) |
| { |
| rememberBestCost(currentSortAvoidanceCost, |
| Optimizer.SORT_AVOIDANCE_PLAN); |
| } |
| } |
| } |
| } |
| } |
| |
| return retval; |
| } |
| |
| /** |
| * Get the unique tuple descriptor of the current access path for an Optimizable. |
| */ |
| private UniqueTupleDescriptor getTupleDescriptor( Optimizable optimizable ) |
| throws StandardException |
| { |
| if ( isTableFunction( optimizable ) ) |
| { |
| ProjectRestrictNode prn = (ProjectRestrictNode) optimizable; |
| return ((StaticMethodCallNode) ((FromVTI) prn.getChildResult()).getMethodCall() ).ad; |
| } |
| else |
| { |
| return optimizable.getCurrentAccessPath().getConglomerateDescriptor(); |
| } |
| } |
| |
| /** Return true if the optimizable is a table function */ |
| static boolean isTableFunction( Optimizable optimizable ) |
| { |
| if ( !( optimizable instanceof ProjectRestrictNode ) ) { return false; } |
| |
| ResultSetNode rsn = ((ProjectRestrictNode) optimizable).getChildResult(); |
| if ( !( rsn instanceof FromVTI ) ) { return false; } |
| |
| return ( ((FromVTI) rsn).getMethodCall() instanceof StaticMethodCallNode ); |
| } |
| |
| /** |
| * 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. |
| * @exception StandardException Thrown on error |
| */ |
| private void rememberBestCost(CostEstimate currentCost, int planType) |
| throws StandardException |
| { |
| foundABestPlan = true; |
| |
| if (tracingIsOn()) { tracer().traceCheapestPlanSoFar( planType, currentCost ); } |
| |
| /* Remember the current cost as best */ |
| bestCost.setCost(currentCost); |
| |
| // Our time limit for optimizing this round is the time we think |
| // it will take us to execute the best join order that we've |
| // found so far (across all rounds of optimizing). In other words, |
| // don't spend more time optimizing this OptimizerImpl than we think |
| // it's going to take to execute the best plan. So if we've just |
| // found a new "best" join order, use that to update our time limit. |
| if (bestCost.getEstimatedCost() < timeLimit) |
| timeLimit = bestCost.getEstimatedCost(); |
| |
| /* |
| ** Remember the current join order and access path |
| ** selections as best. |
| ** NOTE: We want the optimizer trace to print out in |
| ** join order instead of in table number order, so |
| ** we use 2 loops. |
| */ |
| bestJoinOrderUsedPredsFromAbove = usingPredsPushedFromAbove; |
| |
| System.arraycopy( |
| proposedJoinOrder, 0, bestJoinOrder, 0, numOptimizables); |
| |
| for (int i = 0; i < numOptimizables; i++) |
| { |
| optimizableList.getOptimizable(bestJoinOrder[i]). |
| rememberAsBest(planType, this); |
| } |
| |
| /* Remember if a sort is not needed for this plan */ |
| if (requiredRowOrdering != null) |
| { |
| if (planType == Optimizer.SORT_AVOIDANCE_PLAN) |
| requiredRowOrdering.sortNotNeeded(); |
| else |
| requiredRowOrdering.sortNeeded(); |
| } |
| |
| if (tracingIsOn()) |
| { |
| if (requiredRowOrdering != null) { tracer().traceSortNeededForOrdering( planType, requiredRowOrdering ); } |
| tracer().traceRememberingBestJoinOrder |
| ( joinPosition, ArrayUtil.copy( bestJoinOrder ), planType, currentCost, (JBitSet) assignedTableMap.clone() ); |
| } |
| } |
| |
| /** |
| * @see org.apache.derby.iapi.sql.compile.Optimizer#costPermutation |
| * |
| * @exception StandardException Thrown on error |
| */ |
| public void costPermutation() throws StandardException |
| { |
| /* |
| ** Get the cost of the outer plan so far. This gives us the current |
| ** estimated rows, ordering, etc. |
| */ |
| CostEstimate outerCost; |
| if (joinPosition == 0) |
| { |
| outerCost = outermostCostEstimate; |
| } |
| else |
| { |
| /* |
| ** NOTE: This is somewhat problematic. We assume here that the |
| ** outer cost from the best access path for the outer table |
| ** is OK to use even when costing the sort avoidance path for |
| ** the inner table. This is probably OK, since all we use |
| ** from the outer cost is the row count. |
| */ |
| outerCost = |
| optimizableList.getOptimizable( |
| proposedJoinOrder[joinPosition - 1]). |
| getBestAccessPath().getCostEstimate(); |
| } |
| |
| /* At this point outerCost should be non-null (DERBY-1777). |
| * Do the assertion here so that we catch it right away; |
| * otherwise we'd end up with an NPE somewhere further |
| * down the tree and it'd be harder to figure out where |
| * it came from. |
| */ |
| if (SanityManager.DEBUG) |
| { |
| SanityManager.ASSERT(outerCost != null, |
| "outerCost is not expected to be null"); |
| } |
| |
| Optimizable optimizable = optimizableList.getOptimizable(proposedJoinOrder[joinPosition]); |
| |
| /* |
| ** Don't consider non-feasible join strategies. |
| */ |
| if ( ! optimizable.feasibleJoinStrategy(predicateList, this)) |
| { |
| return; |
| } |
| |
| /* Cost the optimizable at the current join position */ |
| optimizable.optimizeIt(this, |
| predicateList, |
| outerCost, |
| currentRowOrdering); |
| } |
| |
| /** |
| * @see org.apache.derby.iapi.sql.compile.Optimizer#costOptimizable |
| * |
| * @exception StandardException Thrown on error |
| */ |
| public void costOptimizable(Optimizable optimizable, |
| TableDescriptor td, |
| ConglomerateDescriptor cd, |
| OptimizablePredicateList predList, |
| CostEstimate outerCost) |
| throws StandardException |
| { |
| /* |
| ** Don't consider non-feasible join strategies. |
| */ |
| if ( ! optimizable.feasibleJoinStrategy(predList, this)) |
| { |
| return; |
| } |
| |
| /* |
| ** Classify the predicates according to the given conglomerate. |
| ** The predicates are classified as start keys, stop keys, |
| ** qualifiers, and none-of-the-above. They are also ordered |
| ** to match the ordering of columns in keyed conglomerates (no |
| ** ordering is done for heaps). |
| */ |
| // if (predList != null) |
| // predList.classify(optimizable, cd); |
| |
| if (ruleBasedOptimization) |
| { |
| ruleBasedCostOptimizable(optimizable, |
| td, |
| cd, |
| predList, |
| outerCost); |
| } |
| else |
| { |
| costBasedCostOptimizable(optimizable, |
| td, |
| cd, |
| predList, |
| outerCost); |
| } |
| } |
| |
| /** |
| * 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. |
| */ |
| private void ruleBasedCostOptimizable(Optimizable optimizable, |
| TableDescriptor td, |
| ConglomerateDescriptor cd, |
| OptimizablePredicateList predList, |
| CostEstimate outerCost) |
| throws StandardException |
| { |
| /* CHOOSE BEST CONGLOMERATE HERE */ |
| AccessPath bestAp = optimizable.getBestAccessPath(); |
| |
| /* |
| ** If the current conglomerate better than the best so far? |
| ** The pecking order is: |
| ** o covering index useful for predicates |
| ** (if there are predicates) |
| ** o index useful for predicates (if there are predicates) |
| ** o covering index |
| ** o table scan |
| */ |
| |
| /* |
| ** If there is more than one conglomerate descriptor |
| ** choose any index that is potentially useful. |
| */ |
| if (predList != null && |
| predList.useful(optimizable, cd)) |
| { |
| /* |
| ** Do not let a non-covering matching index scan supplant a |
| ** covering matching index scan. |
| */ |
| boolean newCoveringIndex = optimizable.isCoveringIndex(cd); |
| if ( ( ! bestAp.getCoveringIndexScan()) || |
| bestAp.getNonMatchingIndexScan() || |
| newCoveringIndex ) |
| { |
| bestAp.setCostEstimate( |
| estimateTotalCost( |
| predList, |
| cd, |
| outerCost, |
| optimizable |
| ) |
| ); |
| bestAp.setConglomerateDescriptor(cd); |
| bestAp.setNonMatchingIndexScan(false); |
| bestAp.setCoveringIndexScan(newCoveringIndex); |
| |
| bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode()); |
| |
| optimizable.rememberJoinStrategyAsBest(bestAp); |
| } |
| |
| return; |
| } |
| |
| /* Remember the "last" covering index. |
| * NOTE - Since we don't have costing, we just go for the |
| * last one since that's as good as any |
| */ |
| if (optimizable.isCoveringIndex(cd)) |
| { |
| bestAp.setCostEstimate( |
| estimateTotalCost(predList, |
| cd, |
| outerCost, |
| optimizable) |
| ); |
| bestAp.setConglomerateDescriptor(cd); |
| bestAp.setNonMatchingIndexScan(true); |
| bestAp.setCoveringIndexScan(true); |
| |
| bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode()); |
| |
| optimizable.rememberJoinStrategyAsBest(bestAp); |
| return; |
| } |
| |
| /* |
| ** If this is the heap, and the best conglomerate so far is a |
| ** non-covering, non-matching index scan, pick the heap. |
| */ |
| if ( ( ! bestAp.getCoveringIndexScan()) && |
| bestAp.getNonMatchingIndexScan() && |
| ( ! cd.isIndex() ) |
| ) |
| { |
| bestAp.setCostEstimate( |
| estimateTotalCost(predList, |
| cd, |
| outerCost, |
| optimizable) |
| ); |
| |
| bestAp.setConglomerateDescriptor(cd); |
| |
| bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode()); |
| |
| optimizable.rememberJoinStrategyAsBest(bestAp); |
| |
| /* |
| ** No need to set non-matching index scan and covering |
| ** index scan, as these are already correct. |
| */ |
| return; |
| } |
| |
| |
| /* |
| ** If all else fails, and no conglomerate has been picked yet, |
| ** pick this one. |
| */ |
| ConglomerateDescriptor bestConglomerateDescriptor = |
| bestAp.getConglomerateDescriptor(); |
| |
| if (bestConglomerateDescriptor == null) |
| { |
| bestAp.setCostEstimate( |
| estimateTotalCost(predList, |
| cd, |
| outerCost, |
| optimizable) |
| ); |
| |
| bestAp.setConglomerateDescriptor(cd); |
| |
| /* |
| ** We have determined above that this index is neither covering |
| ** nor matching. |
| */ |
| bestAp.setCoveringIndexScan(false); |
| bestAp.setNonMatchingIndexScan(cd.isIndex()); |
| |
| bestAp.setLockMode(optimizable.getCurrentAccessPath().getLockMode()); |
| |
| optimizable.rememberJoinStrategyAsBest(bestAp); |
| } |
| } |
| |
| /** |
| * 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. |
| */ |
| private void costBasedCostOptimizable(Optimizable optimizable, |
| TableDescriptor td, |
| ConglomerateDescriptor cd, |
| OptimizablePredicateList predList, |
| CostEstimate outerCost) |
| throws StandardException |
| { |
| CostEstimate estimatedCost = estimateTotalCost(predList, |
| cd, |
| outerCost, |
| optimizable); |
| |
| // Before considering the cost, make sure we set the optimizable's |
| // "current" cost to be the one that we found. Doing this allows |
| // us to compare "current" with "best" later on to find out if |
| // the "current" plan is also the "best" one this round--if it's |
| // not then we'll have to revert back to whatever the best plan is. |
| // That check is performed in getNextDecoratedPermutation() of |
| // this class. |
| optimizable.getCurrentAccessPath().setCostEstimate(estimatedCost); |
| |
| /* |
| ** Skip this access path if it takes too much memory. |
| ** |
| ** NOTE: The default assumption here is that the number of rows in |
| ** a single scan is the total number of rows divided by the number |
| ** of outer rows. The optimizable may over-ride this assumption. |
| */ |
| // RESOLVE: The following call to memoryUsageOK does not behave |
| // correctly if outerCost.rowCount() is POSITIVE_INFINITY; see |
| // DERBY-1259. |
| if( ! optimizable.memoryUsageOK( estimatedCost.rowCount() / outerCost.rowCount(), maxMemoryPerTable)) |
| { |
| if (tracingIsOn()) { tracer().traceSkippingBecauseTooMuchMemory( maxMemoryPerTable ); } |
| return; |
| } |
| |
| /* Pick the cheapest cost for this particular optimizable. */ |
| AccessPath ap = optimizable.getBestAccessPath(); |
| CostEstimate bestCostEstimate = ap.getCostEstimate(); |
| |
| if ((bestCostEstimate == null) || |
| bestCostEstimate.isUninitialized() || |
| (estimatedCost.compare(bestCostEstimate) < 0)) |
| { |
| ap.setConglomerateDescriptor(cd); |
| ap.setCostEstimate(estimatedCost); |
| ap.setCoveringIndexScan(optimizable.isCoveringIndex(cd)); |
| |
| /* |
| ** It's a non-matching index scan either if there is no |
| ** predicate list, or nothing in the predicate list is useful |
| ** for limiting the scan. |
| */ |
| ap.setNonMatchingIndexScan( |
| (predList == null) || |
| ( ! ( predList.useful(optimizable, cd) ) ) |
| ); |
| ap.setLockMode(optimizable.getCurrentAccessPath().getLockMode()); |
| optimizable.rememberJoinStrategyAsBest(ap); |
| } |
| |
| /* |
| ** Keep track of the best sort-avoidance path if there is a |
| ** required row ordering. |
| */ |
| if (requiredRowOrdering != null) |
| { |
| /* |
| ** The current optimizable can avoid a sort only if the |
| ** outer one does, also (if there is an outer one). |
| */ |
| if (joinPosition == 0 || |
| optimizableList.getOptimizable( |
| proposedJoinOrder[joinPosition - 1]). |
| considerSortAvoidancePath()) |
| { |
| /* |
| ** There is a required row ordering - does the proposed access |
| ** path avoid a sort? |
| */ |
| if (requiredRowOrdering.sortRequired(currentRowOrdering, |
| assignedTableMap, |
| optimizableList, |
| proposedJoinOrder) |
| ==RequiredRowOrdering.NOTHING_REQUIRED) |
| { |
| ap = optimizable.getBestSortAvoidancePath(); |
| bestCostEstimate = ap.getCostEstimate(); |
| |
| /* Is this the cheapest sort-avoidance path? */ |
| if ((bestCostEstimate == null) || |
| bestCostEstimate.isUninitialized() || |
| (estimatedCost.compare(bestCostEstimate) < 0)) |
| { |
| ap.setConglomerateDescriptor(cd); |
| ap.setCostEstimate(estimatedCost); |
| ap.setCoveringIndexScan( |
| optimizable.isCoveringIndex(cd)); |
| |
| /* |
| ** It's a non-matching index scan either if there is no |
| ** predicate list, or nothing in the predicate list is |
| ** useful for limiting the scan. |
| */ |
| ap.setNonMatchingIndexScan( |
| (predList == null) || |
| ( ! (predList.useful(optimizable, cd)) ) |
| ); |
| ap.setLockMode( |
| optimizable.getCurrentAccessPath().getLockMode()); |
| optimizable.rememberJoinStrategyAsBest(ap); |
| optimizable.rememberSortAvoidancePath(); |
| |
| /* |
| ** Remember the current row ordering as best |
| */ |
| currentRowOrdering.copy(bestRowOrdering); |
| } |
| } |
| } |
| } |
| } |
| |
| /** |
| * This is the version of costOptimizable for non-base-tables. |
| * |
| * @see Optimizer#considerCost |
| * |
| * @exception StandardException Thrown on error |
| */ |
| public void considerCost(Optimizable optimizable, |
| OptimizablePredicateList predList, |
| CostEstimate estimatedCost, |
| CostEstimate outerCost) |
| throws StandardException |
| { |
| /* |
| ** Don't consider non-feasible join strategies. |
| */ |
| if ( ! optimizable.feasibleJoinStrategy(predList, this)) |
| { |
| return; |
| } |
| |
| // Before considering the cost, make sure we set the optimizable's |
| // "current" cost to be the one that we received. Doing this allows |
| // us to compare "current" with "best" later on to find out if |
| // the "current" plan is also the "best" one this round--if it's |
| // not then we'll have to revert back to whatever the best plan is. |
| // That check is performed in getNextDecoratedPermutation() of |
| // this class. |
| optimizable.getCurrentAccessPath().setCostEstimate(estimatedCost); |
| |
| /* |
| ** Skip this access path if it takes too much memory. |
| ** |
| ** NOTE: The default assumption here is that the number of rows in |
| ** a single scan is the total number of rows divided by the number |
| ** of outer rows. The optimizable may over-ride this assumption. |
| */ |
| |
| // RESOLVE: The following call to memoryUsageOK does not behave |
| // correctly if outerCost.rowCount() is POSITIVE_INFINITY; see |
| // DERBY-1259. |
| if( ! optimizable.memoryUsageOK( estimatedCost.rowCount() / outerCost.rowCount(), |
| maxMemoryPerTable)) |
| { |
| if (tracingIsOn()) { tracer().traceSkippingBecauseTooMuchMemory( maxMemoryPerTable ); } |
| return; |
| } |
| |
| /* Pick the cheapest cost for this particular optimizable. |
| * NOTE: Originally, the code only chose the new access path if |
| * it was cheaper than the old access path. However, I (Jerry) |
| * found that the new and old costs were the same for a derived |
| * table and the old access path did not have a join strategy |
| * associated with it in that case. So, we now choose the new |
| * access path if it is the same cost or cheaper than the current |
| * access path. |
| */ |
| AccessPath ap = optimizable.getBestAccessPath(); |
| CostEstimate bestCostEstimate = ap.getCostEstimate(); |
| |
| if ((bestCostEstimate == null) || |
| bestCostEstimate.isUninitialized() || |
| (estimatedCost.compare(bestCostEstimate) <= 0)) |
| { |
| ap.setCostEstimate(estimatedCost); |
| optimizable.rememberJoinStrategyAsBest(ap); |
| } |
| |
| /* |
| ** Keep track of the best sort-avoidance path if there is a |
| ** required row ordering. |
| */ |
| if (requiredRowOrdering != null) |
| { |
| /* |
| ** The current optimizable can avoid a sort only if the |
| ** outer one does, also (if there is an outer one). |
| */ |
| if (joinPosition == 0 || |
| optimizableList.getOptimizable( |
| proposedJoinOrder[joinPosition - 1]). |
| considerSortAvoidancePath()) |
| { |
| /* |
| ** There is a required row ordering - does the proposed access |
| ** path avoid a sort? |
| */ |
| if (requiredRowOrdering.sortRequired(currentRowOrdering, |
| assignedTableMap, |
| optimizableList, |
| proposedJoinOrder) |
| == RequiredRowOrdering.NOTHING_REQUIRED) |
| { |
| ap = optimizable.getBestSortAvoidancePath(); |
| bestCostEstimate = ap.getCostEstimate(); |
| |
| /* Is this the cheapest sort-avoidance path? */ |
| if ((bestCostEstimate == null) || |
| bestCostEstimate.isUninitialized() || |
| (estimatedCost.compare(bestCostEstimate) < 0)) |
| { |
| ap.setCostEstimate(estimatedCost); |
| optimizable.rememberJoinStrategyAsBest(ap); |
| optimizable.rememberSortAvoidancePath(); |
| |
| /* |
| ** Remember the current row ordering as best |
| */ |
| currentRowOrdering.copy(bestRowOrdering); |
| } |
| } |
| } |
| } |
| } |
| |
| /** |
| * @see org.apache.derby.iapi.sql.compile.Optimizer#getDataDictionary |
| */ |
| |
| public DataDictionary getDataDictionary() |
| { |
| return dDictionary; |
| } |
| |
| /** |
| * @see Optimizer#modifyAccessPaths |
| * |
| * @exception StandardException Thrown on error |
| */ |
| public void modifyAccessPaths() throws StandardException |
| { |
| if (tracingIsOn()) { tracer().traceModifyingAccessPaths( hashCode() ); } |
| |
| if ( ! foundABestPlan) |
| { |
| if (tracingIsOn()) { tracer().traceNoBestPlan(); } |
| |
| throw StandardException.newException(SQLState.LANG_NO_BEST_PLAN_FOUND); |
| } |
| |
| /* Change the join order of the list of optimizables */ |
| optimizableList.reOrder(bestJoinOrder); |
| |
| /* Form a bit map of the tables as they are put into the join order */ |
| JBitSet outerTables = new JBitSet(numOptimizables); |
| |
| /* Modify the access path of each table, as necessary */ |
| for (int ictr = 0; ictr < numOptimizables; ictr++) |
| { |
| Optimizable optimizable = optimizableList.getOptimizable(ictr); |
| |
| /* Current table is treated as an outer table */ |
| outerTables.or(optimizable.getReferencedTableMap()); |
| |
| /* |
| ** Push any appropriate predicates from this optimizer's list |
| ** to the optimizable, as appropriate. |
| */ |
| pushPredicates(optimizable, outerTables); |
| |
| optimizableList.setOptimizable( |
| ictr, |
| optimizable.modifyAccessPath(outerTables)); |
| } |
| } |
| |
| private CostEstimate newCostEstimate() |
| { |
| return new CostEstimateImpl(); |
| } |
| |
| /** @see Optimizer#getOptimizedCost */ |
| public CostEstimate getOptimizedCost() |
| { |
| return bestCost; |
| } |
| |
| /** |
| * @see Optimizer#getFinalCost |
| * |
| * Sum up the cost of all of the trulyTheBestAccessPaths |
| * for the Optimizables in our list. Assumption is that |
| * we only get here after optimization has completed--i.e. |
| * while modifying access paths. |
| */ |
| public CostEstimate getFinalCost() |
| { |
| // If we already did this once, just return the result. |
| if (finalCostEstimate != null) |
| return finalCostEstimate; |
| |
| // The total cost is the sum of all the costs, but the total |
| // number of rows is the number of rows returned by the innermost |
| // optimizable. |
| finalCostEstimate = getNewCostEstimate(0.0d, 0.0d, 0.0d); |
| |
| for (int i = 0; i < bestJoinOrder.length; i++) |
| { |
| CostEstimate ce = optimizableList.getOptimizable(bestJoinOrder[i]) |
| .getTrulyTheBestAccessPath().getCostEstimate(); |
| |
| finalCostEstimate.setCost( |
| finalCostEstimate.getEstimatedCost() + ce.getEstimatedCost(), |
| ce.rowCount(), |
| ce.singleScanRowCount()); |
| } |
| |
| return finalCostEstimate; |
| } |
| |
| /** @see Optimizer#setOuterRows */ |
| public void setOuterRows(double outerRows) |
| { |
| outermostCostEstimate.setCost( |
| outermostCostEstimate.getEstimatedCost(), |
| outerRows, |
| outermostCostEstimate.singleScanRowCount()); |
| } |
| |
| /** @see Optimizer#tableLockThreshold */ |
| public int tableLockThreshold() |
| { |
| return tableLockThreshold; |
| } |
| |
| /** |
| * Get the number of join strategies supported by this optimizer. |
| */ |
| public int getNumberOfJoinStrategies() |
| { |
| return joinStrategies.length; |
| } |
| |
| /** @see Optimizer#getJoinStrategy */ |
| public JoinStrategy getJoinStrategy(int whichStrategy) { |
| if (SanityManager.DEBUG) { |
| if (whichStrategy < 0 || whichStrategy >= joinStrategies.length) { |
| SanityManager.THROWASSERT("whichStrategy value " + |
| whichStrategy + |
| " out of range - should be between 0 and " + |
| (joinStrategies.length - 1)); |
| } |
| |
| if (joinStrategies[whichStrategy] == null) { |
| SanityManager.THROWASSERT("Strategy " + whichStrategy + |
| " not filled in."); |
| } |
| } |
| |
| return joinStrategies[whichStrategy]; |
| } |
| |
| /** @see Optimizer#getJoinStrategy */ |
| public JoinStrategy getJoinStrategy(String whichStrategy) { |
| JoinStrategy retval = null; |
| String upperValue = StringUtil.SQLToUpperCase(whichStrategy); |
| |
| for (int i = 0; i < joinStrategies.length; i++) { |
| if (upperValue.equals(joinStrategies[i].getName())) { |
| retval = joinStrategies[i]; |
| } |
| } |
| |
| return retval; |
| } |
| |
| /** |
| @see Optimizer#uniqueJoinWithOuterTable |
| |
| @exception StandardException Thrown on error |
| */ |
| public double uniqueJoinWithOuterTable(OptimizablePredicateList predList) |
| throws StandardException |
| { |
| double retval = -1.0; |
| double numUniqueKeys = 1.0; |
| double currentRows = currentCost.rowCount(); |
| |
| if (predList != null) |
| { |
| |
| for (int i = joinPosition - 1; i >= 0; i--) |
| { |
| Optimizable opt = optimizableList.getOptimizable( |
| proposedJoinOrder[i]); |
| double uniqueKeysThisOptimizable = opt.uniqueJoin(predList); |
| if (uniqueKeysThisOptimizable > 0.0) |
| numUniqueKeys *= opt.uniqueJoin(predList); |
| } |
| } |
| |
| if (numUniqueKeys != 1.0) |
| { |
| retval = numUniqueKeys / currentRows; |
| } |
| |
| return retval; |
| } |
| |
| private boolean isPushable(OptimizablePredicate pred) |
| { |
| /* Predicates which contain subqueries that are not materializable are |
| * not currently pushable. |
| */ |
| if (pred.hasSubquery()) |
| { |
| return false; |
| } |
| else |
| { |
| return true; |
| } |
| } |
| |
| /** |
| * Estimate the total cost of doing a join with the given optimizable. |
| * |
| * @exception StandardException Thrown on error |
| */ |
| private CostEstimate estimateTotalCost(OptimizablePredicateList predList, |
| ConglomerateDescriptor cd, |
| CostEstimate outerCost, |
| Optimizable optimizable) |
| throws StandardException |
| { |
| /* Get the cost of a single scan */ |
| CostEstimate resultCost = |
| optimizable.estimateCost(predList, |
| cd, |
| outerCost, |
| this, |
| currentRowOrdering); |
| |
| return resultCost; |
| } |
| |
| /** @see Optimizer#getLevel */ |
| public int getLevel() |
| { |
| return 2; |
| } |
| |
| CostEstimateImpl getNewCostEstimate(double theCost, |
| double theRowCount, |
| double theSingleScanRowCount) |
| { |
| return new CostEstimateImpl(theCost, theRowCount, theSingleScanRowCount); |
| } |
| |
| /** @see Optimizer#useStatistics */ |
| public boolean useStatistics() { return useStatistics && optimizableList.useStatistics(); } |
| |
| /** |
| * 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. |
| * |
| * @param action Indicates whether to add, load, or remove the plan |
| * @param 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. |
| */ |
| public void updateBestPlanMaps(short action, |
| Object planKey) throws StandardException |
| { |
| // First we process this OptimizerImpl's best join order. If there's |
| // only one optimizable in the list, then there's only one possible |
| // join order, so don't bother. |
| if (numOptimizables > 1) |
| { |
| int [] joinOrder = null; |
| if (action == FromTable.REMOVE_PLAN) |
| { |
| if (savedJoinOrders != null) |
| { |
| savedJoinOrders.remove(planKey); |
| if (savedJoinOrders.isEmpty()) { |
| savedJoinOrders = null; |
| } |
| } |
| } |
| else if (action == FromTable.ADD_PLAN) |
| { |
| // If the savedJoinOrder map already exists, search for the |
| // join order for the target optimizer and reuse that. |
| if (savedJoinOrders == null) |
| savedJoinOrders = new HashMap<Object,int[]>(); |
| else |
| joinOrder = savedJoinOrders.get(planKey); |
| |
| // If we don't already have a join order array for the optimizer, |
| // create a new one. |
| if (joinOrder == null) |
| joinOrder = new int[numOptimizables]; |
| |
| System.arraycopy( |
| bestJoinOrder, 0, joinOrder, 0, bestJoinOrder.length); |
| |
| savedJoinOrders.put(planKey, joinOrder); |
| } |
| else |
| { |
| // If we get here, we want to load the best join order from our |
| // map into this OptimizerImpl's bestJoinOrder array. |
| |
| // If we don't have any join orders saved, then there's nothing to |
| // load. This can happen if the optimizer tried some join order |
| // for which there was no valid plan. |
| if (savedJoinOrders != null) |
| { |
| joinOrder = savedJoinOrders.get(planKey); |
| if (joinOrder != null) |
| { |
| System.arraycopy( |
| joinOrder, 0, bestJoinOrder, 0, joinOrder.length); |
| } |
| } |
| } |
| } |
| |
| // Now iterate through all Optimizables in this OptimizerImpl's |
| // list and add/load/remove the best plan "mapping" for each one, |
| // as described in in Optimizable.updateBestPlanMap(). |
| for (int i = optimizableList.size() - 1; i >= 0; i--) |
| { |
| optimizableList.getOptimizable(i). |
| updateBestPlanMap(action, planKey); |
| } |
| } |
| |
| /** |
| * 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. |
| * |
| * @param pList List of predicates to add to this OptimizerImpl's |
| * own list for pushing. |
| */ |
| void addScopedPredicatesToList(PredicateList pList, ContextManager cm) |
| throws StandardException |
| { |
| if ((pList == null) || (pList == predicateList)) |
| // nothing to do. |
| return; |
| |
| if (predicateList == null) |
| // in this case, there is no 'original' predicateList, so we |
| // can just create one. |
| predicateList = new PredicateList(cm); |
| |
| // First, we need to go through and remove any predicates in this |
| // optimizer's list that may have been pushed here from outer queries |
| // during the previous round(s) of optimization. We know if the |
| // predicate was pushed from an outer query because it will have |
| // been scoped to the node for which this OptimizerImpl was |
| // created. |
| Predicate pred; |
| for (int i = predicateList.size() - 1; i >= 0; i--) { |
| pred = (Predicate)predicateList.getOptPredicate(i); |
| if (pred.isScopedForPush()) |
| predicateList.removeOptPredicate(i); |
| } |
| |
| // Now transfer scoped predicates in the received list to |
| // this OptimizerImpl's list, where appropriate. |
| for (int i = pList.size() - 1; i >= 0; i--) |
| { |
| pred = (Predicate)pList.getOptPredicate(i); |
| if (pred.isScopedToSourceResultSet()) |
| { |
| // Clear the scoped predicate's scan flags; they'll be set |
| // as appropriate when they make it to the restrictionList |
| // of the scoped pred's source result set. |
| pred.clearScanFlags(); |
| predicateList.addOptPredicate(pred); |
| pList.removeOptPredicate(i); |
| } |
| } |
| } |
| |
| /** Get the trace machinery */ |
| private OptTrace tracer() { return lcc.getOptimizerTracer(); } |
| |
| public int getOptimizableCount() { return optimizableList.size(); } |
| |
| public Optimizable getOptimizable( int idx ) { return optimizableList.getOptimizable( idx ); } |
| } |