0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.sql.compile.OptimizerImpl
0004:
0005: Licensed to the Apache Software Foundation (ASF) under one or more
0006: contributor license agreements. See the NOTICE file distributed with
0007: this work for additional information regarding copyright ownership.
0008: The ASF licenses this file to you under the Apache License, Version 2.0
0009: (the "License"); you may not use this file except in compliance with
0010: the License. You may obtain a copy of the License at
0011:
0012: http://www.apache.org/licenses/LICENSE-2.0
0013:
0014: Unless required by applicable law or agreed to in writing, software
0015: distributed under the License is distributed on an "AS IS" BASIS,
0016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0017: See the License for the specific language governing permissions and
0018: limitations under the License.
0019:
0020: */
0021:
0022: package org.apache.derby.impl.sql.compile;
0023:
0024: import org.apache.derby.iapi.services.sanity.SanityManager;
0025:
0026: import org.apache.derby.iapi.error.StandardException;
0027:
0028: import org.apache.derby.iapi.sql.compile.JoinStrategy;
0029: import org.apache.derby.iapi.sql.compile.Optimizable;
0030: import org.apache.derby.iapi.sql.compile.OptimizableList;
0031: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
0032: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
0033: import org.apache.derby.iapi.sql.compile.Optimizer;
0034: import org.apache.derby.iapi.sql.compile.CostEstimate;
0035: import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
0036: import org.apache.derby.iapi.sql.compile.RowOrdering;
0037: import org.apache.derby.iapi.sql.compile.AccessPath;
0038:
0039: import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
0040:
0041: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
0042: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
0043: import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
0044:
0045: import org.apache.derby.catalog.IndexDescriptor;
0046: import org.apache.derby.iapi.reference.SQLState;
0047:
0048: import org.apache.derby.iapi.util.JBitSet;
0049: import org.apache.derby.iapi.util.StringUtil;
0050:
0051: import java.util.Properties;
0052: import java.util.HashMap;
0053:
0054: /**
0055: * This will be the Level 1 Optimizer.
0056: * RESOLVE - it's a level 0 optimizer right now.
0057: * Current State:
0058: * o No costing services
0059: * o We can only cost a derived table with a join once.
0060: *
0061: * Optimizer uses OptimizableList to keep track of the best join order as it
0062: * builds it. For each available slot in the join order, we cost all of the
0063: * Optimizables from that slot til the end of the OptimizableList. Later,
0064: * we will choose the best Optimizable for that slot and reorder the list
0065: * accordingly.
0066: * In order to do this, we probably need to move the temporary pushing and
0067: * pulling of join clauses into Optimizer, since the logic will be different
0068: * for other implementations. (Of course, we're not pushing and pulling join
0069: * clauses between permutations yet.)
0070: */
0071:
0072: public class OptimizerImpl implements Optimizer {
0073:
0074: DataDictionary dDictionary;
0075: /* The number of tables in the query as a whole. (Size of bit maps.) */
0076: int numTablesInQuery;
0077: /* The number of optimizables in the list to optimize */
0078: int numOptimizables;
0079:
0080: /* Bit map of tables that have already been assigned to slots.
0081: * Useful for pushing join clauses as slots are assigned.
0082: */
0083: protected JBitSet assignedTableMap;
0084: protected OptimizableList optimizableList;
0085: OptimizablePredicateList predicateList;
0086: JBitSet nonCorrelatedTableMap;
0087:
0088: protected int[] proposedJoinOrder;
0089: protected int[] bestJoinOrder;
0090: protected int joinPosition;
0091: boolean desiredJoinOrderFound;
0092:
0093: /* This implements a state machine to jump start to a appearingly good join
0094: * order, when the number of tables is high, and the optimization could take
0095: * a long time. A good start can prune better, and timeout sooner. Otherwise,
0096: * it may take forever to exhaust or timeout (see beetle 5870). Basically after
0097: * we jump, we walk the high part, then fall when we reach the peak, finally we
0098: * walk the low part til where we jumped to.
0099: */
0100: private static final int NO_JUMP = 0;
0101: private static final int READY_TO_JUMP = 1;
0102: private static final int JUMPING = 2;
0103: private static final int WALK_HIGH = 3;
0104: private static final int WALK_LOW = 4;
0105: private int permuteState;
0106: private int[] firstLookOrder;
0107:
0108: private boolean ruleBasedOptimization;
0109:
0110: private CostEstimateImpl outermostCostEstimate;
0111: protected CostEstimateImpl currentCost;
0112: protected CostEstimateImpl currentSortAvoidanceCost;
0113: protected CostEstimateImpl bestCost;
0114:
0115: protected long timeOptimizationStarted;
0116: protected long currentTime;
0117: protected boolean timeExceeded;
0118: private boolean noTimeout;
0119: private boolean useStatistics;
0120: private int tableLockThreshold;
0121:
0122: private JoinStrategy[] joinStrategies;
0123:
0124: protected RequiredRowOrdering requiredRowOrdering;
0125:
0126: private boolean foundABestPlan;
0127:
0128: protected CostEstimate sortCost;
0129:
0130: private RowOrdering currentRowOrdering = new RowOrderingImpl();
0131: private RowOrdering bestRowOrdering = new RowOrderingImpl();
0132:
0133: private boolean conglomerate_OneRowResultSet;
0134:
0135: // optimizer trace
0136: protected boolean optimizerTrace;
0137: protected boolean optimizerTraceHtml;
0138:
0139: // max memory use per table
0140: protected int maxMemoryPerTable;
0141:
0142: // Whether or not we need to reload the best plan for an Optimizable
0143: // when we "pull" it. If the latest complete join order was the
0144: // best one so far, then the Optimizable will already have the correct
0145: // best plan loaded so we don't need to do the extra work. But if
0146: // the most recent join order was _not_ the best, then this flag tells
0147: // us that we need to reload the best plan when pulling.
0148: private boolean reloadBestPlan;
0149:
0150: // Set of optimizer->bestJoinOrder mappings used to keep track of which
0151: // of this OptimizerImpl's "bestJoinOrder"s was the best with respect to a
0152: // a specific outer query; the outer query is represented by an instance
0153: // of Optimizer. Each outer query could potentially have a different
0154: // idea of what this OptimizerImpl's "best join order" is, so we have
0155: // to keep track of them all.
0156: private HashMap savedJoinOrders;
0157:
0158: // Value used to figure out when/if we've timed out for this
0159: // Optimizable.
0160: protected double timeLimit;
0161:
0162: // Cost estimate for the final "best join order" that we chose--i.e.
0163: // the one that's actually going to be generated.
0164: CostEstimate finalCostEstimate;
0165:
0166: /* Status variables used for "jumping" to previous best join
0167: * order when possible. In particular, this helps when this
0168: * optimizer corresponds to a subquery and we are trying to
0169: * find out what the best join order is if we do a hash join
0170: * with the subquery instead of a nested loop join. In that
0171: * case the previous best join order will have the best join
0172: * order for a nested loop, so we want to start there when
0173: * considering hash join because odds are that same join order
0174: * will give us the best cost for hash join, as well. We
0175: * only try this, though, if neither the previous round of
0176: * optimization nor this round relies on predicates that have
0177: * been pushed down from above--because that's the scenario
0178: * for which the best join order is likely to be same for
0179: * consecutive rounds.
0180: */
0181: private boolean usingPredsPushedFromAbove;
0182: private boolean bestJoinOrderUsedPredsFromAbove;
0183:
0184: protected OptimizerImpl(OptimizableList optimizableList,
0185: OptimizablePredicateList predicateList,
0186: DataDictionary dDictionary, boolean ruleBasedOptimization,
0187: boolean noTimeout, boolean useStatistics,
0188: int maxMemoryPerTable, JoinStrategy[] joinStrategies,
0189: int tableLockThreshold,
0190: RequiredRowOrdering requiredRowOrdering,
0191: int numTablesInQuery) throws StandardException {
0192: if (SanityManager.DEBUG) {
0193: SanityManager.ASSERT(optimizableList != null,
0194: "optimizableList is not expected to be null");
0195: }
0196:
0197: outermostCostEstimate = getNewCostEstimate(0.0d, 1.0d, 1.0d);
0198:
0199: currentCost = getNewCostEstimate(0.0d, 0.0d, 0.0d);
0200:
0201: currentSortAvoidanceCost = getNewCostEstimate(0.0d, 0.0d, 0.0d);
0202:
0203: bestCost = getNewCostEstimate(Double.MAX_VALUE,
0204: Double.MAX_VALUE, Double.MAX_VALUE);
0205:
0206: // Verify that any Properties lists for user overrides are valid
0207: optimizableList.verifyProperties(dDictionary);
0208:
0209: this .numTablesInQuery = numTablesInQuery;
0210: numOptimizables = optimizableList.size();
0211: proposedJoinOrder = new int[numOptimizables];
0212: if (numTablesInQuery > 6) {
0213: permuteState = READY_TO_JUMP;
0214: firstLookOrder = new int[numOptimizables];
0215: } else
0216: permuteState = NO_JUMP;
0217:
0218: /* Mark all join positions as unused */
0219: for (int i = 0; i < numOptimizables; i++)
0220: proposedJoinOrder[i] = -1;
0221:
0222: bestJoinOrder = new int[numOptimizables];
0223: joinPosition = -1;
0224: this .optimizableList = optimizableList;
0225: this .predicateList = predicateList;
0226: this .dDictionary = dDictionary;
0227: this .ruleBasedOptimization = ruleBasedOptimization;
0228: this .noTimeout = noTimeout;
0229: this .maxMemoryPerTable = maxMemoryPerTable;
0230: this .joinStrategies = joinStrategies;
0231: this .tableLockThreshold = tableLockThreshold;
0232: this .requiredRowOrdering = requiredRowOrdering;
0233: this .useStatistics = useStatistics;
0234:
0235: /* initialize variables for tracking permutations */
0236: assignedTableMap = new JBitSet(numTablesInQuery);
0237:
0238: /*
0239: ** Make a map of the non-correlated tables, which are the tables
0240: ** in the list of Optimizables we're optimizing. An reference
0241: ** to a table that is not defined in the list of Optimizables
0242: ** is presumed to be correlated.
0243: */
0244: nonCorrelatedTableMap = new JBitSet(numTablesInQuery);
0245: for (int tabCtr = 0; tabCtr < numOptimizables; tabCtr++) {
0246: Optimizable curTable = optimizableList
0247: .getOptimizable(tabCtr);
0248: nonCorrelatedTableMap.or(curTable.getReferencedTableMap());
0249: }
0250:
0251: /* Get the time that optimization starts */
0252: timeOptimizationStarted = System.currentTimeMillis();
0253: reloadBestPlan = false;
0254: savedJoinOrders = null;
0255: timeLimit = Double.MAX_VALUE;
0256:
0257: usingPredsPushedFromAbove = false;
0258: bestJoinOrderUsedPredsFromAbove = false;
0259: }
0260:
0261: /**
0262: * This method is called before every "round" of optimization, where
0263: * we define a "round" to be the period between the last time a call to
0264: * getOptimizer() (on either a ResultSetNode or an OptimizerFactory)
0265: * returned _this_ OptimizerImpl and the time a call to this OptimizerImpl's
0266: * getNextPermutation() method returns FALSE. Any re-initialization
0267: * of state that is required before each round should be done in this
0268: * method.
0269: */
0270: public void prepForNextRound() {
0271: // We initialize reloadBestPlan to false so that if we end up
0272: // pulling an Optimizable before we find a best join order
0273: // (which can happen if there is no valid join order for this
0274: // round) we won't inadvertently reload the best plans based
0275: // on some previous round.
0276: reloadBestPlan = false;
0277:
0278: /* Since we're preparing for a new round, we have to clear
0279: * out the "bestCost" from the previous round to ensure that,
0280: * when this round of optimizing is done, bestCost will hold
0281: * the best cost estimate found _this_ round, if there was
0282: * one. If there was no best cost found (which can happen if
0283: * there is no feasible join order) then bestCost will remain
0284: * at Double.MAX_VALUE. Then when outer queries check the
0285: * cost and see that it is so high, they will reject whatever
0286: * outer join order they're trying in favor of something that's
0287: * actually valid (and therefore cheaper).
0288: *
0289: * Note that we do _not_ reset the "foundABestPlan" variable nor
0290: * the "bestJoinOrder" array. This is because it's possible that
0291: * a "best join order" may not exist for the current round, in
0292: * which case this OptimizerImpl must know whether or not it found
0293: * a best join order in a previous round (foundABestPlan) and if
0294: * so what the corresponding join order was (bestJoinOrder). This
0295: * information is required so that the correct query plan can be
0296: * generated after optimization is complete, even if that best
0297: * plan was not found in the most recent round.
0298: */
0299: bestCost = getNewCostEstimate(Double.MAX_VALUE,
0300: Double.MAX_VALUE, Double.MAX_VALUE);
0301:
0302: /* If we have predicates that were pushed down to this OptimizerImpl
0303: * from an outer query, then we reset the timeout state to prepare for
0304: * the next round of optimization. Otherwise if we timed out during
0305: * a previous round and then we get here for another round, we'll
0306: * immediately "timeout" again before optimizing any of the Optimizables
0307: * in our list. This is okay if we don't have any predicates from
0308: * outer queries because in that case the plan we find this round
0309: * will be the same one we found in the previous round, in which
0310: * case there's no point in resetting the timeout state and doing
0311: * the work a second time. But if we have predicates from an outer
0312: * query, those predicates could help us find a much better plan
0313: * this round than we did in previous rounds--so we reset the timeout
0314: * state to ensure that we have a chance to consider plans that
0315: * can take advantage of the pushed predicates.
0316: */
0317: usingPredsPushedFromAbove = false;
0318: if ((predicateList != null) && (predicateList.size() > 0)) {
0319: for (int i = predicateList.size() - 1; i >= 0; i--) {
0320: // If the predicate is "scoped", then we know it was pushed
0321: // here from an outer query.
0322: if (((Predicate) predicateList.getOptPredicate(i))
0323: .isScopedForPush()) {
0324: usingPredsPushedFromAbove = true;
0325: break;
0326: }
0327: }
0328: }
0329:
0330: if (usingPredsPushedFromAbove) {
0331: timeOptimizationStarted = System.currentTimeMillis();
0332: timeExceeded = false;
0333: }
0334:
0335: /* If user specified the optimizer override for a fixed
0336: * join order, then desiredJoinOrderFound could be true
0337: * when we get here. We have to reset it to false in
0338: * prep for the next round of optimization. Otherwise
0339: * we'd end up quitting the optimization before ever
0340: * finding a plan for this round, and that could, among
0341: * other things, lead to a never-ending optimization
0342: * phase in certain situations. DERBY-1866.
0343: */
0344: desiredJoinOrderFound = false;
0345: }
0346:
0347: public int getMaxMemoryPerTable() {
0348: return maxMemoryPerTable;
0349: }
0350:
0351: /**
0352: * @see Optimizer#getNextPermutation
0353: *
0354: * @exception StandardException Thrown on error
0355: */
0356: public boolean getNextPermutation() throws StandardException {
0357: /* Don't get any permutations if there is nothing to optimize */
0358: if (numOptimizables < 1) {
0359: if (optimizerTrace) {
0360: trace(NO_TABLES, 0, 0, 0.0, null);
0361: }
0362:
0363: endOfRoundCleanup();
0364: return false;
0365: }
0366:
0367: /* Make sure that all Optimizables init their access paths.
0368: * (They wait until optimization since the access path
0369: * references the optimizer.)
0370: */
0371: optimizableList.initAccessPaths(this );
0372:
0373: /*
0374: ** Experiments show that optimization time only starts to
0375: ** become a problem with seven tables, so only check for
0376: ** too much time if there are more than seven tables.
0377: ** Also, don't check for too much time if user has specified
0378: ** no timeout.
0379: */
0380: if ((!timeExceeded) && (numTablesInQuery > 6) && (!noTimeout)) {
0381: /*
0382: ** Stop optimizing if the time spent optimizing is greater than
0383: ** the current best cost.
0384: */
0385: currentTime = System.currentTimeMillis();
0386: timeExceeded = (currentTime - timeOptimizationStarted) > timeLimit;
0387:
0388: if (optimizerTrace && timeExceeded) {
0389: trace(TIME_EXCEEDED, 0, 0, 0.0, null);
0390: }
0391: }
0392:
0393: if (bestCost.isUninitialized()
0394: && foundABestPlan
0395: && ((!usingPredsPushedFromAbove && !bestJoinOrderUsedPredsFromAbove) || timeExceeded)) {
0396: /* We can get here if this OptimizerImpl is for a subquery
0397: * that timed out for a previous permutation of the outer
0398: * query, but then the outer query itself did _not_ timeout.
0399: * In that case we'll end up back here for another round of
0400: * optimization, but our timeExceeded flag will be true.
0401: * We don't want to reset all of the timeout state here
0402: * because that could lead to redundant work (see comments
0403: * in prepForNextRound()), but we also don't want to return
0404: * without having a plan, because then we'd return an unfairly
0405: * high "bestCost" value--i.e. Double.MAX_VALUE. Note that
0406: * we can't just revert back to whatever bestCost we had
0407: * prior to this because that cost is for some previous
0408: * permutation of the outer query--not the current permutation--
0409: * and thus would be incorrect. So instead we have to delay
0410: * the timeout until we find a complete (and valid) join order,
0411: * so that we can return a valid cost estimate. Once we have
0412: * a valid cost we'll then go through the timeout logic
0413: * and stop optimizing.
0414: *
0415: * All of that said, instead of just trying the first possible
0416: * join order, we jump to the join order that gave us the best
0417: * cost in previous rounds. We know that such a join order exists
0418: * because that's how our timeout value was set to begin with--so
0419: * if there was no best join order, we never would have timed out
0420: * and thus we wouldn't be here.
0421: *
0422: * We can also get here if we've already optimized the list
0423: * of optimizables once (in a previous round of optimization)
0424: * and now we're back to do it again. If that's true AND
0425: * we did *not* receive any predicates pushed from above AND
0426: * the bestJoinOrder from the previous round did *not* depend
0427: * on predicates pushed from above, then we'll jump to the
0428: * previous join order and start there. NOTE: if after jumping
0429: * to the previous join order and calculating the cost we haven't
0430: * timed out, we will continue looking at other join orders (as
0431: * usual) until we exhaust them all or we time out.
0432: */
0433: if (permuteState != JUMPING) {
0434: // By setting firstLookOrder to our target join order
0435: // and then setting our permuteState to JUMPING, we'll
0436: // jump to the target join order and get the cost. That
0437: // cost will then be saved as bestCost, allowing us to
0438: // proceed with normal timeout logic.
0439: if (firstLookOrder == null)
0440: firstLookOrder = new int[numOptimizables];
0441: for (int i = 0; i < numOptimizables; i++)
0442: firstLookOrder[i] = bestJoinOrder[i];
0443: permuteState = JUMPING;
0444:
0445: /* If we already assigned at least one position in the
0446: * join order when this happened (i.e. if joinPosition
0447: * is greater than *or equal* to zero; DERBY-1777), then
0448: * reset the join order before jumping. The call to
0449: * rewindJoinOrder() here will put joinPosition back
0450: * to 0. But that said, we'll then end up incrementing
0451: * joinPosition before we start looking for the next
0452: * join order (see below), which means we need to set
0453: * it to -1 here so that it gets incremented to "0" and
0454: * then processing can continue as normal from there.
0455: * Note: we don't need to set reloadBestPlan to true
0456: * here because we only get here if we have *not* found
0457: * a best plan yet.
0458: */
0459: if (joinPosition >= 0) {
0460: rewindJoinOrder();
0461: joinPosition = -1;
0462: }
0463: }
0464:
0465: // Reset the timeExceeded flag so that we'll keep going
0466: // until we find a complete join order. NOTE: we intentionally
0467: // do _not_ reset the timeOptimizationStarted value because we
0468: // we want to go through this timeout logic for every
0469: // permutation, to make sure we timeout as soon as we have
0470: // our first complete join order.
0471: timeExceeded = false;
0472: }
0473:
0474: /*
0475: ** Pick the next table in the join order, if there is an unused position
0476: ** in the join order, and the current plan is less expensive than
0477: ** the best plan so far, and the amount of time spent optimizing is
0478: ** still less than the cost of the best plan so far, and a best
0479: ** cost has been found in the current join position. Otherwise,
0480: ** just pick the next table in the current position.
0481: */
0482: boolean joinPosAdvanced = false;
0483:
0484: /* Determine if the current plan is still less expensive than
0485: * the best plan so far. If bestCost is uninitialized then
0486: * we want to return false here; if we didn't, then in the (rare)
0487: * case where the current cost is greater than Double.MAX_VALUE
0488: * (esp. if it's Double.POSITIVE_INFINITY, which can occur
0489: * for very deeply nested queries with long FromLists) we would
0490: * give up on the current plan even though we didn't have a
0491: * best plan yet, which would be wrong. Also note: if we have
0492: * a required row ordering then we might end up using the
0493: * sort avoidance plan--but we don't know at this point
0494: * which plan (sort avoidance or "normal") we're going to
0495: * use, so we error on the side of caution and only short-
0496: * circuit if both currentCost and currentSortAvoidanceCost
0497: * (if the latter is applicable) are greater than bestCost.
0498: */
0499: boolean alreadyCostsMore = !bestCost.isUninitialized()
0500: && (currentCost.compare(bestCost) > 0)
0501: && ((requiredRowOrdering == null) || (currentSortAvoidanceCost
0502: .compare(bestCost) > 0));
0503:
0504: if ((joinPosition < (numOptimizables - 1)) && !alreadyCostsMore
0505: && (!timeExceeded)) {
0506: /*
0507: ** Are we either starting at the first join position (in which
0508: ** case joinPosition will be -1), or has a best cost been found
0509: ** in the current join position? The latter case might not be
0510: ** true if there is no feasible join order.
0511: */
0512: if ((joinPosition < 0)
0513: || optimizableList.getOptimizable(
0514: proposedJoinOrder[joinPosition])
0515: .getBestAccessPath().getCostEstimate() != null) {
0516: joinPosition++;
0517: joinPosAdvanced = true;
0518:
0519: /*
0520: ** When adding a table to the join order, the best row
0521: ** row ordering for the outer tables becomes the starting
0522: ** point for the row ordering of the current table.
0523: */
0524: bestRowOrdering.copy(currentRowOrdering);
0525: }
0526: } else {
0527: if (optimizerTrace) {
0528: /*
0529: ** Not considered short-circuiting if all slots in join
0530: ** order are taken.
0531: */
0532: if (joinPosition < (numOptimizables - 1)) {
0533: trace(SHORT_CIRCUITING, 0, 0, 0.0, null);
0534: }
0535: }
0536:
0537: // If we short-circuited the current join order then we need
0538: // to make sure that, when we start pulling optimizables to find
0539: // a new join order, we reload the best plans for those
0540: // optimizables as we pull them. Otherwise we could end up
0541: // generating a plan for an optimizable even though that plan
0542: // was part of a short-circuited (and thus rejected) join
0543: // order.
0544: if (joinPosition < (numOptimizables - 1))
0545: reloadBestPlan = true;
0546: }
0547:
0548: if (permuteState == JUMPING && !joinPosAdvanced
0549: && joinPosition >= 0) {
0550: //not feeling well in the middle of jump
0551: // Note: we have to make sure we reload the best plans
0552: // as we rewind since they may have been clobbered
0553: // (as part of the current join order) before we gave
0554: // up on jumping.
0555: reloadBestPlan = true;
0556: rewindJoinOrder(); //fall
0557: permuteState = NO_JUMP; //give up
0558: }
0559:
0560: /*
0561: ** The join position becomes < 0 when all the permutations have been
0562: ** looked at.
0563: */
0564: while (joinPosition >= 0) {
0565: int nextOptimizable = 0;
0566:
0567: if (desiredJoinOrderFound || timeExceeded) {
0568: /*
0569: ** If the desired join order has been found (which will happen
0570: ** if the user specifies a join order), pretend that there are
0571: ** no more optimizables at this join position. This will cause
0572: ** us to back out of the current join order.
0573: **
0574: ** Also, don't look at any more join orders if we have taken
0575: ** too much time with this optimization.
0576: */
0577: nextOptimizable = numOptimizables;
0578: } else if (permuteState == JUMPING) //still jumping
0579: {
0580: /* We're "jumping" to a join order that puts the optimizables
0581: ** with the lowest estimated costs first (insofar as it
0582: ** is legal to do so). The "firstLookOrder" array holds the
0583: ** ideal join order for position <joinPosition> up thru
0584: ** position <numOptimizables-1>. So here, we look at the
0585: ** ideal optimizable to place at <joinPosition> and see if
0586: ** it's legal; if it is, then we're done. Otherwise, we
0587: ** swap it with <numOptimizables-1> and see if that gives us
0588: ** a legal join order w.r.t <joinPosition>. If not, then we
0589: ** swap it with <numOptimizables-2> and check, and if that
0590: ** fails, then we swap it with <numOptimizables-3>, and so
0591: ** on. For example, assume we have 6 optimizables whose
0592: ** order from least expensive to most expensive is 2, 1, 4,
0593: ** 5, 3, 0. Assume also that we've already verified the
0594: ** legality of the first two positions--i.e. that joinPosition
0595: ** is now "2". That means that "firstLookOrder" currently
0596: ** contains the following:
0597: **
0598: ** [ pos ] 0 1 2 3 4 5
0599: ** [ opt ] 2 1 4 5 3 0
0600: **
0601: ** Then at this point, we do the following:
0602: **
0603: ** -- Check to see if the ideal optimizable "4" is valid
0604: ** at its current position (2)
0605: ** -- If opt "4" is valid, then we're done; else we
0606: ** swap it with the value at position _5_:
0607: **
0608: ** [ pos ] 0 1 2 3 4 5
0609: ** [ opt ] 2 1 0 5 3 4
0610: **
0611: ** -- Check to see if optimizable "0" is valid at its
0612: ** new position (2).
0613: ** -- If opt "0" is valid, then we're done; else we
0614: ** put "0" back in its original position and swap
0615: ** the ideal optimizer ("4") with the value at
0616: ** position _4_:
0617: **
0618: ** [ pos ] 0 1 2 3 4 5
0619: ** [ opt ] 2 1 3 5 4 0
0620: **
0621: ** -- Check to see if optimizable "3" is valid at its
0622: ** new position (2).
0623: ** -- If opt "3" is valid, then we're done; else we
0624: ** put "3" back in its original position and swap
0625: ** the ideal optimizer ("4") with the value at
0626: ** position _3_:
0627: **
0628: ** [ pos ] 0 1 2 3 4 5
0629: ** [ opt ] 2 1 5 4 3 0
0630: **
0631: ** -- Check to see if optimizable "5" is valid at its
0632: ** new position (2).
0633: ** -- If opt "5" is valid, then we're done; else we've
0634: ** tried all the available optimizables and none
0635: ** of them are legal at position 2. In this case,
0636: ** we give up on "JUMPING" and fall back to normal
0637: ** join-order processing.
0638: */
0639:
0640: int idealOptimizable = firstLookOrder[joinPosition];
0641: nextOptimizable = idealOptimizable;
0642: int lookPos = numOptimizables;
0643: int lastSwappedOpt = -1;
0644:
0645: Optimizable nextOpt;
0646: for (nextOpt = optimizableList
0647: .getOptimizable(nextOptimizable); !(nextOpt
0648: .legalJoinOrder(assignedTableMap)); nextOpt = optimizableList
0649: .getOptimizable(nextOptimizable)) {
0650: // Undo last swap, if we had one.
0651: if (lastSwappedOpt >= 0) {
0652: firstLookOrder[joinPosition] = idealOptimizable;
0653: firstLookOrder[lookPos] = lastSwappedOpt;
0654: }
0655:
0656: if (lookPos > joinPosition + 1) {
0657: // we still have other possibilities; get the next
0658: // one by "swapping" it into the current position.
0659: lastSwappedOpt = firstLookOrder[--lookPos];
0660: firstLookOrder[joinPosition] = lastSwappedOpt;
0661: firstLookOrder[lookPos] = idealOptimizable;
0662: nextOptimizable = lastSwappedOpt;
0663: } else {
0664: // we went through all of the available optimizables
0665: // and none of them were legal in the current position;
0666: // so we give up and fall back to normal processing.
0667: // Note: we have to make sure we reload the best plans
0668: // as we rewind since they may have been clobbered
0669: // (as part of the current join order) before we got
0670: // here.
0671: if (joinPosition > 0) {
0672: joinPosition--;
0673: reloadBestPlan = true;
0674: rewindJoinOrder();
0675: }
0676: permuteState = NO_JUMP;
0677: break;
0678: }
0679: }
0680:
0681: if (permuteState == NO_JUMP)
0682: continue;
0683:
0684: if (joinPosition == numOptimizables - 1) {
0685: // we just set the final position within our
0686: // "firstLookOrder" join order; now go ahead
0687: // and search for the best join order, starting from
0688: // the join order stored in "firstLookOrder". This
0689: // is called walking "high" because we're searching
0690: // the join orders that are at or "above" (after) the
0691: // order found in firstLookOrder. Ex. if we had three
0692: // optimizables and firstLookOrder was [1 2 0], then
0693: // the "high" would be [1 2 0], [2 0 1] and [2 1 0];
0694: // the "low" would be [0 1 2], [0 2 1], and [1 0 2].
0695: // We walk the "high" first, then fall back and
0696: // walk the "low".
0697: permuteState = WALK_HIGH;
0698: }
0699: } else {
0700: /* Find the next unused table at this join position */
0701: nextOptimizable = proposedJoinOrder[joinPosition] + 1;
0702:
0703: for (; nextOptimizable < numOptimizables; nextOptimizable++) {
0704: boolean found = false;
0705: for (int posn = 0; posn < joinPosition; posn++) {
0706: /*
0707: ** Is this optimizable already somewhere
0708: ** in the join order?
0709: */
0710: if (proposedJoinOrder[posn] == nextOptimizable) {
0711: found = true;
0712: break;
0713: }
0714: }
0715:
0716: /* Check to make sure that all of the next optimizable's
0717: * dependencies have been satisfied.
0718: */
0719: if (nextOptimizable < numOptimizables) {
0720: Optimizable nextOpt = optimizableList
0721: .getOptimizable(nextOptimizable);
0722: if (!(nextOpt.legalJoinOrder(assignedTableMap))) {
0723: if (optimizerTrace) {
0724: trace(SKIPPING_JOIN_ORDER,
0725: nextOptimizable, 0, 0.0, null);
0726: }
0727:
0728: /*
0729: ** If this is a user specified join order then it is illegal.
0730: */
0731: if (!optimizableList.optimizeJoinOrder()) {
0732: if (optimizerTrace) {
0733: trace(ILLEGAL_USER_JOIN_ORDER, 0,
0734: 0, 0.0, null);
0735: }
0736:
0737: throw StandardException
0738: .newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
0739: }
0740: continue;
0741: }
0742: }
0743:
0744: if (!found) {
0745: break;
0746: }
0747: }
0748:
0749: }
0750:
0751: /*
0752: ** We are going to try an optimizable at the current join order
0753: ** position. Is there one already at that position?
0754: */
0755: if (proposedJoinOrder[joinPosition] >= 0) {
0756: /*
0757: ** We are either going to try another table at the current
0758: ** join order position, or we have exhausted all the tables
0759: ** at the current join order position. In either case, we
0760: ** need to pull the table at the current join order position
0761: ** and remove it from the join order.
0762: */
0763: Optimizable pullMe = optimizableList
0764: .getOptimizable(proposedJoinOrder[joinPosition]);
0765:
0766: /*
0767: ** Subtract the cost estimate of the optimizable being
0768: ** removed from the total cost estimate.
0769: **
0770: ** The total cost is the sum of all the costs, but the total
0771: ** number of rows is the number of rows returned by the
0772: ** innermost optimizable.
0773: */
0774: double prevRowCount;
0775: double prevSingleScanRowCount;
0776: int prevPosition = 0;
0777: if (joinPosition == 0) {
0778: prevRowCount = outermostCostEstimate.rowCount();
0779: prevSingleScanRowCount = outermostCostEstimate
0780: .singleScanRowCount();
0781: } else {
0782: prevPosition = proposedJoinOrder[joinPosition - 1];
0783: CostEstimate localCE = optimizableList
0784: .getOptimizable(prevPosition)
0785: .getBestAccessPath().getCostEstimate();
0786: prevRowCount = localCE.rowCount();
0787: prevSingleScanRowCount = localCE
0788: .singleScanRowCount();
0789: }
0790:
0791: /*
0792: ** If there is no feasible join order, the cost estimate
0793: ** in the best access path may never have been set.
0794: ** In this case, do not subtract anything from the
0795: ** current cost, since nothing was added to the current
0796: ** cost.
0797: */
0798: double newCost = currentCost.getEstimatedCost();
0799: double pullCost = 0.0;
0800: CostEstimate pullCostEstimate = pullMe
0801: .getBestAccessPath().getCostEstimate();
0802: if (pullCostEstimate != null) {
0803: pullCost = pullCostEstimate.getEstimatedCost();
0804:
0805: newCost -= pullCost;
0806:
0807: /*
0808: ** It's possible for newCost to go negative here due to
0809: ** loss of precision.
0810: */
0811: if (newCost < 0.0)
0812: newCost = 0.0;
0813: }
0814:
0815: /* If we are choosing a new outer table, then
0816: * we rest the starting cost to the outermostCost.
0817: * (Thus avoiding any problems with floating point
0818: * accuracy and going negative.)
0819: */
0820: if (joinPosition == 0) {
0821: if (outermostCostEstimate != null) {
0822: newCost = outermostCostEstimate
0823: .getEstimatedCost();
0824: } else {
0825: newCost = 0.0;
0826: }
0827: }
0828:
0829: currentCost.setCost(newCost, prevRowCount,
0830: prevSingleScanRowCount);
0831:
0832: /*
0833: ** Subtract from the sort avoidance cost if there is a
0834: ** required row ordering.
0835: **
0836: ** NOTE: It is not necessary here to check whether the
0837: ** best cost was ever set for the sort avoidance path,
0838: ** because it considerSortAvoidancePath() would not be
0839: ** set if there cost were not set.
0840: */
0841: if (requiredRowOrdering != null) {
0842: if (pullMe.considerSortAvoidancePath()) {
0843: AccessPath ap = pullMe
0844: .getBestSortAvoidancePath();
0845: double prevEstimatedCost = 0.0d;
0846:
0847: /*
0848: ** Subtract the sort avoidance cost estimate of the
0849: ** optimizable being removed from the total sort
0850: ** avoidance cost estimate.
0851: **
0852: ** The total cost is the sum of all the costs, but the
0853: ** total number of rows is the number of rows returned
0854: ** by the innermost optimizable.
0855: */
0856: if (joinPosition == 0) {
0857: prevRowCount = outermostCostEstimate
0858: .rowCount();
0859: prevSingleScanRowCount = outermostCostEstimate
0860: .singleScanRowCount();
0861: /* If we are choosing a new outer table, then
0862: * we rest the starting cost to the outermostCost.
0863: * (Thus avoiding any problems with floating point
0864: * accuracy and going negative.)
0865: */
0866: prevEstimatedCost = outermostCostEstimate
0867: .getEstimatedCost();
0868: } else {
0869: CostEstimate localCE = optimizableList
0870: .getOptimizable(prevPosition)
0871: .getBestSortAvoidancePath()
0872: .getCostEstimate();
0873: prevRowCount = localCE.rowCount();
0874: prevSingleScanRowCount = localCE
0875: .singleScanRowCount();
0876: prevEstimatedCost = currentSortAvoidanceCost
0877: .getEstimatedCost()
0878: - ap.getCostEstimate()
0879: .getEstimatedCost();
0880: }
0881:
0882: currentSortAvoidanceCost.setCost(
0883: prevEstimatedCost, prevRowCount,
0884: prevSingleScanRowCount);
0885:
0886: /*
0887: ** Remove the table from the best row ordering.
0888: ** It should not be necessary to remove it from
0889: ** the current row ordering, because it is
0890: ** maintained as we step through the access paths
0891: ** for the current Optimizable.
0892: */
0893: bestRowOrdering.removeOptimizable(pullMe
0894: .getTableNumber());
0895:
0896: /*
0897: ** When removing a table from the join order,
0898: ** the best row ordering for the remaining outer tables
0899: ** becomes the starting point for the row ordering of
0900: ** the current table.
0901: */
0902: bestRowOrdering.copy(currentRowOrdering);
0903: }
0904: }
0905:
0906: /*
0907: ** Pull the predicates at from the optimizable and put
0908: ** them back in the predicate list.
0909: **
0910: ** NOTE: This is a little inefficient because it pulls the
0911: ** single-table predicates, which are guaranteed to always
0912: ** be pushed to the same optimizable. We could make this
0913: ** leave the single-table predicates where they are.
0914: */
0915: pullMe.pullOptPredicates(predicateList);
0916:
0917: /*
0918: ** When we pull an Optimizable we need to go through and
0919: ** load whatever best path we found for that Optimizable
0920: ** with respect to _this_ OptimizerImpl. An Optimizable
0921: ** can have different "best paths" for different Optimizer
0922: ** Impls if there are subqueries beneath it; we need to make
0923: ** sure that when we pull it, it's holding the best path as
0924: ** as we determined it to be for _us_.
0925: **
0926: ** NOTE: We we only reload the best plan if it's necessary
0927: ** to do so--i.e. if the best plans aren't already loaded.
0928: ** The plans will already be loaded if the last complete
0929: ** join order we had was the best one so far, because that
0930: ** means we called "rememberAsBest" on every Optimizable
0931: ** in the list and, as part of that call, we will run through
0932: ** and set trulyTheBestAccessPath for the entire subtree.
0933: ** So if we haven't tried any other plans since then,
0934: ** we know that every Optimizable (and its subtree) already
0935: ** has the correct best plan loaded in its trulyTheBest
0936: ** path field. It's good to skip the load in this case
0937: ** because 'reloading best plans' involves walking the
0938: ** entire subtree of _every_ Optimizable in the list, which
0939: ** can be expensive if there are deeply nested subqueries.
0940: */
0941: if (reloadBestPlan)
0942: pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this );
0943:
0944: /* Mark current join position as unused */
0945: proposedJoinOrder[joinPosition] = -1;
0946: }
0947:
0948: /* Have we exhausted all the optimizables at this join position? */
0949: if (nextOptimizable >= numOptimizables) {
0950: /*
0951: ** If we're not optimizing the join order, remember the first
0952: ** join order.
0953: */
0954: if (!optimizableList.optimizeJoinOrder()) {
0955: // Verify that the user specified a legal join order
0956: if (!optimizableList
0957: .legalJoinOrder(numTablesInQuery)) {
0958: if (optimizerTrace) {
0959: trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0,
0960: null);
0961: }
0962:
0963: throw StandardException
0964: .newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
0965: }
0966:
0967: if (optimizerTrace) {
0968: trace(USER_JOIN_ORDER_OPTIMIZED, 0, 0, 0.0,
0969: null);
0970: }
0971:
0972: desiredJoinOrderFound = true;
0973: }
0974:
0975: if (permuteState == READY_TO_JUMP && joinPosition > 0
0976: && joinPosition == numOptimizables - 1) {
0977: permuteState = JUMPING;
0978:
0979: /* A simple heuristics is that the row count we got indicates a potentially
0980: * good join order. We'd like row count to get big as late as possible, so
0981: * that less load is carried over.
0982: */
0983: double rc[] = new double[numOptimizables];
0984: for (int i = 0; i < numOptimizables; i++) {
0985: firstLookOrder[i] = i;
0986: CostEstimate ce = optimizableList
0987: .getOptimizable(i).getBestAccessPath()
0988: .getCostEstimate();
0989: if (ce == null) {
0990: permuteState = READY_TO_JUMP; //come again?
0991: break;
0992: }
0993: rc[i] = ce.singleScanRowCount();
0994: }
0995: if (permuteState == JUMPING) {
0996: boolean doIt = false;
0997: int temp;
0998: for (int i = 0; i < numOptimizables; i++) //simple selection sort
0999: {
1000: int k = i;
1001: for (int j = i + 1; j < numOptimizables; j++)
1002: if (rc[j] < rc[k])
1003: k = j;
1004: if (k != i) {
1005: rc[k] = rc[i]; //destroy the bridge
1006: temp = firstLookOrder[i];
1007: firstLookOrder[i] = firstLookOrder[k];
1008: firstLookOrder[k] = temp;
1009: doIt = true;
1010: }
1011: }
1012:
1013: if (doIt) {
1014: joinPosition--;
1015: rewindJoinOrder(); //jump from ground
1016: continue;
1017: } else
1018: permuteState = NO_JUMP; //never
1019: }
1020: }
1021:
1022: /*
1023: ** We have exhausted all the optimizables at this level.
1024: ** Go back up one level.
1025: */
1026:
1027: /* Go back up one join position */
1028: joinPosition--;
1029:
1030: /* Clear the assigned table map for the previous position
1031: * NOTE: We need to do this here to for the dependency tracking
1032: */
1033: if (joinPosition >= 0) {
1034: Optimizable pullMe = optimizableList
1035: .getOptimizable(proposedJoinOrder[joinPosition]);
1036:
1037: /*
1038: ** Clear the bits from the table at this join position.
1039: ** This depends on them having been set previously.
1040: ** NOTE: We need to do this here to for the dependency tracking
1041: */
1042: assignedTableMap
1043: .xor(pullMe.getReferencedTableMap());
1044: }
1045:
1046: if (joinPosition < 0 && permuteState == WALK_HIGH) //reached peak
1047: {
1048: joinPosition = 0; //reset, fall down the hill
1049: permuteState = WALK_LOW;
1050: }
1051: continue;
1052: }
1053:
1054: /*
1055: ** We have found another optimizable to try at this join position.
1056: */
1057: proposedJoinOrder[joinPosition] = nextOptimizable;
1058:
1059: if (permuteState == WALK_LOW) {
1060: boolean finishedCycle = true;
1061: for (int i = 0; i < numOptimizables; i++) {
1062: if (proposedJoinOrder[i] < firstLookOrder[i]) {
1063: finishedCycle = false;
1064: break;
1065: } else if (proposedJoinOrder[i] > firstLookOrder[i]) //done
1066: break;
1067: }
1068: if (finishedCycle) {
1069: // We just set proposedJoinOrder[joinPosition] above, so
1070: // if we're done we need to put it back to -1 to indicate
1071: // that it's an empty slot. Then we rewind and pull any
1072: // other Optimizables at positions < joinPosition.
1073: // Note: we have to make sure we reload the best plans
1074: // as we rewind since they may have been clobbered
1075: // (as part of the current join order) before we got
1076: // here.
1077: proposedJoinOrder[joinPosition] = -1;
1078: joinPosition--;
1079: if (joinPosition >= 0) {
1080: reloadBestPlan = true;
1081: rewindJoinOrder();
1082: joinPosition = -1;
1083: }
1084:
1085: permuteState = READY_TO_JUMP;
1086: endOfRoundCleanup();
1087: return false;
1088: }
1089: }
1090:
1091: /* Re-init (clear out) the cost for the best access path
1092: * when placing a table.
1093: */
1094: optimizableList.getOptimizable(nextOptimizable)
1095: .getBestAccessPath().setCostEstimate(
1096: (CostEstimate) null);
1097:
1098: /* Set the assigned table map to be exactly the tables
1099: * in the current join order.
1100: */
1101: assignedTableMap.clearAll();
1102: for (int index = 0; index <= joinPosition; index++) {
1103: assignedTableMap.or(optimizableList.getOptimizable(
1104: proposedJoinOrder[index])
1105: .getReferencedTableMap());
1106: }
1107:
1108: if (optimizerTrace) {
1109: trace(CONSIDERING_JOIN_ORDER, 0, 0, 0.0, null);
1110: }
1111:
1112: Optimizable nextOpt = optimizableList
1113: .getOptimizable(nextOptimizable);
1114:
1115: nextOpt.startOptimizing(this , currentRowOrdering);
1116:
1117: pushPredicates(optimizableList
1118: .getOptimizable(nextOptimizable), assignedTableMap);
1119:
1120: return true;
1121: }
1122:
1123: endOfRoundCleanup();
1124: return false;
1125: }
1126:
1127: private void rewindJoinOrder() throws StandardException {
1128: for (;; joinPosition--) {
1129: Optimizable pullMe = optimizableList
1130: .getOptimizable(proposedJoinOrder[joinPosition]);
1131: pullMe.pullOptPredicates(predicateList);
1132: if (reloadBestPlan)
1133: pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this );
1134: proposedJoinOrder[joinPosition] = -1;
1135: if (joinPosition == 0)
1136: break;
1137: }
1138: currentCost.setCost(0.0d, 0.0d, 0.0d);
1139: currentSortAvoidanceCost.setCost(0.0d, 0.0d, 0.0d);
1140: assignedTableMap.clearAll();
1141: }
1142:
1143: /**
1144: * Do any work that needs to be done after the current round
1145: * of optimization has completed. For now this just means walking
1146: * the subtrees for each optimizable and removing the "bestPlan"
1147: * that we saved (w.r.t to this OptimizerImpl) from all of the
1148: * nodes. If we don't do this post-optimization cleanup we
1149: * can end up consuming a huge amount of memory for deeply-
1150: * nested queries, which can lead to OOM errors. DERBY-1315.
1151: */
1152: private void endOfRoundCleanup() throws StandardException {
1153: for (int i = 0; i < numOptimizables; i++) {
1154: optimizableList.getOptimizable(i).updateBestPlanMap(
1155: FromTable.REMOVE_PLAN, this );
1156: }
1157: }
1158:
1159: /*
1160: ** Push predicates from this optimizer's list to the given optimizable,
1161: ** as appropriate given the outer tables.
1162: **
1163: ** @param curTable The Optimizable to push predicates down to
1164: ** @param outerTables A bit map of outer tables
1165: **
1166: ** @exception StandardException Thrown on error
1167: */
1168: void pushPredicates(Optimizable curTable, JBitSet outerTables)
1169: throws StandardException {
1170: /*
1171: ** Push optimizable clauses to current position in join order.
1172: **
1173: ** RESOLVE - We do not push predicates with subqueries not materializable.
1174: */
1175:
1176: int numPreds = predicateList.size();
1177: JBitSet predMap = new JBitSet(numTablesInQuery);
1178: JBitSet curTableNums = null;
1179: BaseTableNumbersVisitor btnVis = null;
1180: boolean pushPredNow = false;
1181: int tNum;
1182: Predicate pred;
1183:
1184: /* Walk the OptimizablePredicateList. For each OptimizablePredicate,
1185: * see if it can be assigned to the Optimizable at the current join
1186: * position.
1187: *
1188: * NOTE - We walk the OPL backwards since we will hopefully be deleted
1189: * entries as we walk it.
1190: */
1191: for (int predCtr = numPreds - 1; predCtr >= 0; predCtr--) {
1192: pred = (Predicate) predicateList.getOptPredicate(predCtr);
1193:
1194: /* Skip over non-pushable predicates */
1195: if (!isPushable(pred)) {
1196: continue;
1197: }
1198:
1199: /* Make copy of referenced map so that we can do destructive
1200: * manipulation on the copy.
1201: */
1202: predMap.setTo(pred.getReferencedMap());
1203:
1204: /* Clear bits representing those tables that have already been
1205: * assigned, except for the current table. The outer table map
1206: * includes the current table, so if the predicate is ready to
1207: * be pushed, predMap will end up with no bits set.
1208: */
1209: for (int index = 0; index < predMap.size(); index++) {
1210: if (outerTables.get(index)) {
1211: predMap.clear(index);
1212: }
1213: }
1214:
1215: /*
1216: ** Only consider non-correlated variables when deciding where
1217: ** to push predicates down to.
1218: */
1219: predMap.and(nonCorrelatedTableMap);
1220:
1221: /* At this point what we've done is figure out what FromTables
1222: * the predicate references (using the predicate's "referenced
1223: * map") and then: 1) unset the table numbers for any FromTables
1224: * that have already been optimized, 2) unset the table number
1225: * for curTable, which we are about to optimize, and 3) cleared
1226: * out any remaining table numbers which do NOT directly
1227: * correspond to UN-optimized FromTables in this OptimizerImpl's
1228: * optimizableList.
1229: *
1230: * Note: the optimizables in this OptImpl's optimizableList are
1231: * called "non-correlated".
1232: *
1233: * So at this point predMap holds a list of tableNumbers which
1234: * correspond to "non-correlated" FromTables that are referenced
1235: * by the predicate but that have NOT yet been optimized. If any
1236: * such FromTable exists then we canNOT push the predicate yet.
1237: * We can only push the predicate if every FromTable that it
1238: * references either 1) has already been optimized, or 2) is
1239: * about to be optimized (i.e. the FromTable is curTable itself).
1240: * We can check for this condition by seeing if predMap is empty,
1241: * which is what the following line does.
1242: */
1243: pushPredNow = (predMap.getFirstSetBit() == -1);
1244:
1245: /* If the predicate is scoped, there's more work to do. A
1246: * scoped predicate's "referenced map" may not be in sync
1247: * with its actual column references. Or put another way,
1248: * the predicate's referenced map may not actually represent
1249: * the tables that are referenced by the predicate. For
1250: * example, assume the query tree is something like:
1251: *
1252: * SelectNode0
1253: * (PRN0, PRN1)
1254: * | |
1255: * T1 UnionNode
1256: * / |
1257: * PRN2 PRN3
1258: * | |
1259: * SelectNode1 SelectNode2
1260: * (PRN4, PRN5) (PRN6)
1261: * | | |
1262: * T2 T3 T4
1263: *
1264: * Assume further that we have an equijoin predicate between
1265: * T1 and the Union node, and that the column reference that
1266: * points to the Union ultimately maps to T3. The predicate
1267: * will then be scoped to PRN2 and PRN3 and the newly-scoped
1268: * predicates will get passed to the optimizers for SelectNode1
1269: * and SelectNode2--which brings us here. Assume for this
1270: * example that we're here for SelectNode1 and that "curTable"
1271: * is PRN4. Since the predicate has been scoped to SelectNode1,
1272: * its referenced map will hold the table numbers for T1 and
1273: * PRN2--it will NOT hold the table number for PRN5, even
1274: * though PRN5 (T3) is the actual target for the predicate.
1275: * Given that, the above logic will determine that the predicate
1276: * should be pushed to curTable (PRN4)--but that's not correct.
1277: * We said at the start that the predicate ultimately maps to
1278: * T3--so we should NOT be pushing it to T2. And hence the
1279: * need for some additional logic. DERBY-1866.
1280: */
1281: if (pushPredNow && pred.isScopedForPush()
1282: && (numOptimizables > 1)) {
1283: if (btnVis == null) {
1284: curTableNums = new JBitSet(numTablesInQuery);
1285: btnVis = new BaseTableNumbersVisitor(curTableNums);
1286: }
1287:
1288: /* What we want to do is find out if the scoped predicate
1289: * is really supposed to be pushed to curTable. We do
1290: * that by getting the base table numbers referenced by
1291: * curTable along with curTable's own table number. Then
1292: * we get the base table numbers referenced by the scoped
1293: * predicate. If the two sets have at least one table
1294: * number in common, then we know that the predicate
1295: * should be pushed to curTable. In the above example
1296: * predMap will end up holding the base table number
1297: * for T3, and thus this check will fail when curTable
1298: * is PRN4 but will pass when it is PRN5, which is what
1299: * we want.
1300: */
1301: tNum = ((FromTable) curTable).getTableNumber();
1302: curTableNums.clearAll();
1303: btnVis.setTableMap(curTableNums);
1304: ((FromTable) curTable).accept(btnVis);
1305: if (tNum >= 0)
1306: curTableNums.set(tNum);
1307:
1308: btnVis.setTableMap(predMap);
1309: pred.accept(btnVis);
1310:
1311: predMap.and(curTableNums);
1312: if ((predMap.getFirstSetBit() == -1))
1313: pushPredNow = false;
1314: }
1315:
1316: /*
1317: ** Finally, push the predicate down to the Optimizable at the
1318: ** end of the current proposed join order, if it can be evaluated
1319: ** there.
1320: */
1321: if (pushPredNow) {
1322: /* Push the predicate and remove it from the list */
1323: if (curTable.pushOptPredicate(pred)) {
1324: predicateList.removeOptPredicate(predCtr);
1325: }
1326: }
1327: }
1328: }
1329:
1330: /**
1331: * @see Optimizer#getNextDecoratedPermutation
1332: *
1333: * @exception StandardException Thrown on error
1334: */
1335: public boolean getNextDecoratedPermutation()
1336: throws StandardException {
1337: boolean retval;
1338: Optimizable curOpt = optimizableList
1339: .getOptimizable(proposedJoinOrder[joinPosition]);
1340: double originalRowCount = 0.0;
1341:
1342: // RESOLVE: Should we step through the different join strategies here?
1343:
1344: /* Returns true until all access paths are exhausted */
1345: retval = curOpt.nextAccessPath(this ,
1346: (OptimizablePredicateList) null, currentRowOrdering);
1347:
1348: // If the previous path that we considered for curOpt was _not_ the best
1349: // path for this round, then we need to revert back to whatever the
1350: // best plan for curOpt was this round. Note that the cost estimate
1351: // for bestAccessPath could be null here if the last path that we
1352: // checked was the only one possible for this round.
1353: if ((curOpt.getBestAccessPath().getCostEstimate() != null)
1354: && (curOpt.getCurrentAccessPath().getCostEstimate() != null)) {
1355: // Note: we can't just check to see if bestCost is cheaper
1356: // than currentCost because it's possible that currentCost
1357: // is actually cheaper--but it may have been 'rejected' because
1358: // it would have required too much memory. So we just check
1359: // to see if bestCost and currentCost are different. If so
1360: // then we know that the most recent access path (represented
1361: // by "current" access path) was not the best.
1362: if (curOpt.getBestAccessPath().getCostEstimate().compare(
1363: curOpt.getCurrentAccessPath().getCostEstimate()) != 0) {
1364: curOpt.updateBestPlanMap(FromTable.LOAD_PLAN, curOpt);
1365: } else if (curOpt.getBestAccessPath().getCostEstimate()
1366: .rowCount() < curOpt.getCurrentAccessPath()
1367: .getCostEstimate().rowCount()) {
1368: // If currentCost and bestCost have the same cost estimate
1369: // but currentCost has been rejected because of memory, we
1370: // still need to revert the plans. In this case the row
1371: // count for currentCost will be greater than the row count
1372: // for bestCost, so that's what we just checked.
1373: curOpt.updateBestPlanMap(FromTable.LOAD_PLAN, curOpt);
1374: }
1375: }
1376:
1377: /* If we needed to revert plans for curOpt, we just did it above.
1378: * So we no longer need to keep the previous best plan--and in fact,
1379: * keeping it can lead to extreme memory usage for very large
1380: * queries. So delete the stored plan for curOpt. DERBY-1315.
1381: */
1382: curOpt.updateBestPlanMap(FromTable.REMOVE_PLAN, curOpt);
1383:
1384: /*
1385: ** When all the access paths have been looked at, we know what the
1386: ** cheapest one is, so remember it. Only do this if a cost estimate
1387: ** has been set for the best access path - one will not have been
1388: ** set if no feasible plan has been found.
1389: */
1390: CostEstimate ce = curOpt.getBestAccessPath().getCostEstimate();
1391: if ((!retval) && (ce != null)) {
1392: /*
1393: ** Add the cost of the current optimizable to the total cost.
1394: ** The total cost is the sum of all the costs, but the total
1395: ** number of rows is the number of rows returned by the innermost
1396: ** optimizable.
1397: */
1398: currentCost.setCost(currentCost.getEstimatedCost()
1399: + ce.getEstimatedCost(), ce.rowCount(), ce
1400: .singleScanRowCount());
1401:
1402: if (curOpt.considerSortAvoidancePath()
1403: && requiredRowOrdering != null) {
1404: /* Add the cost for the sort avoidance path, if there is one */
1405: ce = curOpt.getBestSortAvoidancePath()
1406: .getCostEstimate();
1407:
1408: currentSortAvoidanceCost.setCost(
1409: currentSortAvoidanceCost.getEstimatedCost()
1410: + ce.getEstimatedCost(), ce.rowCount(),
1411: ce.singleScanRowCount());
1412: }
1413:
1414: if (optimizerTrace) {
1415: trace(TOTAL_COST_NON_SA_PLAN, 0, 0, 0.0, null);
1416: if (curOpt.considerSortAvoidancePath()) {
1417: trace(TOTAL_COST_SA_PLAN, 0, 0, 0.0, null);
1418: }
1419: }
1420:
1421: /* Do we have a complete join order? */
1422: if (joinPosition == (numOptimizables - 1)) {
1423: if (optimizerTrace) {
1424: trace(COMPLETE_JOIN_ORDER, 0, 0, 0.0, null);
1425: }
1426:
1427: /* Add cost of sorting to non-sort-avoidance cost */
1428: if (requiredRowOrdering != null) {
1429: boolean gotSortCost = false;
1430:
1431: /* Only get the sort cost once */
1432: if (sortCost == null) {
1433: sortCost = newCostEstimate();
1434: }
1435: /* requiredRowOrdering records if the bestCost so far is
1436: * sort-needed or not, as done in rememberBestCost. If
1437: * the bestCost so far is sort-needed, and assume
1438: * currentCost is also sort-needed, we want this comparison
1439: * to be as accurate as possible. Different plans may
1440: * produce different estimated row count (eg., heap scan
1441: * vs. index scan during a join), sometimes the difference
1442: * could be very big. However the actual row count should
1443: * be only one value. So when comparing these two plans,
1444: * we want them to have the same sort cost. We want to
1445: * take the smaller row count, because a better estimation
1446: * (eg. through index) would yield a smaller number. We
1447: * adjust the bestCost here if it had a bigger rowCount
1448: * estimate. The performance improvement of doing this
1449: * sometimes is quite dramatic, eg. from 17 sec to 0.5 sec,
1450: * see beetle 4353.
1451: */
1452: else if (requiredRowOrdering.getSortNeeded()) {
1453: if (bestCost.rowCount() > currentCost
1454: .rowCount()) {
1455: // adjust bestCost
1456: requiredRowOrdering.estimateCost(bestCost
1457: .rowCount(), bestRowOrdering,
1458: sortCost);
1459: double oldSortCost = sortCost
1460: .getEstimatedCost();
1461: requiredRowOrdering.estimateCost(
1462: currentCost.rowCount(),
1463: bestRowOrdering, sortCost);
1464: gotSortCost = true;
1465: bestCost.setCost(bestCost
1466: .getEstimatedCost()
1467: - oldSortCost
1468: + sortCost.getEstimatedCost(),
1469: sortCost.rowCount(), currentCost
1470: .singleScanRowCount());
1471: } else if (bestCost.rowCount() < currentCost
1472: .rowCount()) {
1473: // adjust currentCost's rowCount
1474: currentCost.setCost(currentCost
1475: .getEstimatedCost(), bestCost
1476: .rowCount(), currentCost
1477: .singleScanRowCount());
1478: }
1479: }
1480:
1481: /* This does not figure out if sorting is necessary, just
1482: * an asumption that sort is needed; if the assumption is
1483: * wrong, we'll look at sort-avoidance cost as well, later
1484: */
1485: if (!gotSortCost) {
1486: requiredRowOrdering.estimateCost(currentCost
1487: .rowCount(), bestRowOrdering, sortCost);
1488: }
1489:
1490: originalRowCount = currentCost.rowCount();
1491:
1492: currentCost.setCost(currentCost.getEstimatedCost()
1493: + sortCost.getEstimatedCost(), sortCost
1494: .rowCount(), currentCost
1495: .singleScanRowCount());
1496:
1497: if (optimizerTrace) {
1498: trace(COST_OF_SORTING, 0, 0, 0.0, null);
1499: trace(TOTAL_COST_WITH_SORTING, 0, 0, 0.0, null);
1500: }
1501: }
1502:
1503: /*
1504: ** Is the cost of this join order lower than the best one we've
1505: ** found so far?
1506: **
1507: ** NOTE: If the user has specified a join order, it will be the
1508: ** only join order the optimizer considers, so it is OK to use
1509: ** costing to decide that it is the "best" join order.
1510: **
1511: ** For very deeply nested queries, it's possible that the optimizer
1512: ** will return an estimated cost of Double.INFINITY, which is
1513: ** greater than our uninitialized cost of Double.MAX_VALUE and
1514: ** thus the "compare" check below will return false. So we have
1515: ** to check to see if bestCost is uninitialized and, if so, we
1516: ** save currentCost regardless of what value it is--because we
1517: ** haven't found anything better yet.
1518: **
1519: ** That said, it's also possible for bestCost to be infinity
1520: ** AND for current cost to be infinity, as well. In that case
1521: ** we can't really tell much by comparing the two, so for lack
1522: ** of better alternative we look at the row counts. See
1523: ** CostEstimateImpl.compare() for more.
1524: */
1525: if ((!foundABestPlan)
1526: || (currentCost.compare(bestCost) < 0)
1527: || bestCost.isUninitialized()) {
1528: rememberBestCost(currentCost, Optimizer.NORMAL_PLAN);
1529:
1530: // Since we just remembered all of the best plans,
1531: // no need to reload them when pulling Optimizables
1532: // from this join order.
1533: reloadBestPlan = false;
1534: } else
1535: reloadBestPlan = true;
1536:
1537: /* Subtract cost of sorting from non-sort-avoidance cost */
1538: if (requiredRowOrdering != null) {
1539: /*
1540: ** The cost could go negative due to loss of precision.
1541: */
1542: double newCost = currentCost.getEstimatedCost()
1543: - sortCost.getEstimatedCost();
1544: if (newCost < 0.0)
1545: newCost = 0.0;
1546:
1547: currentCost.setCost(newCost, originalRowCount,
1548: currentCost.singleScanRowCount());
1549: }
1550:
1551: /*
1552: ** This may be the best sort-avoidance plan if there is a
1553: ** required row ordering, and we are to consider a sort
1554: ** avoidance path on the last Optimizable in the join order.
1555: */
1556: if (requiredRowOrdering != null
1557: && curOpt.considerSortAvoidancePath()) {
1558: if (requiredRowOrdering
1559: .sortRequired(bestRowOrdering) == RequiredRowOrdering.NOTHING_REQUIRED) {
1560: if (optimizerTrace) {
1561: trace(CURRENT_PLAN_IS_SA_PLAN, 0, 0, 0.0,
1562: null);
1563: }
1564:
1565: if ((currentSortAvoidanceCost.compare(bestCost) <= 0)
1566: || bestCost.isUninitialized()) {
1567: rememberBestCost(currentSortAvoidanceCost,
1568: Optimizer.SORT_AVOIDANCE_PLAN);
1569: }
1570: }
1571: }
1572: }
1573: }
1574:
1575: return retval;
1576: }
1577:
1578: /**
1579: * Is the cost of this join order lower than the best one we've
1580: * found so far? If so, remember it.
1581: *
1582: * NOTE: If the user has specified a join order, it will be the
1583: * only join order the optimizer considers, so it is OK to use
1584: * costing to decide that it is the "best" join order.
1585: * @exception StandardException Thrown on error
1586: */
1587: private void rememberBestCost(CostEstimate currentCost, int planType)
1588: throws StandardException {
1589: foundABestPlan = true;
1590:
1591: if (optimizerTrace) {
1592: trace(CHEAPEST_PLAN_SO_FAR, 0, 0, 0.0, null);
1593: trace(PLAN_TYPE, planType, 0, 0.0, null);
1594: trace(COST_OF_CHEAPEST_PLAN_SO_FAR, 0, 0, 0.0, null);
1595: }
1596:
1597: /* Remember the current cost as best */
1598: bestCost.setCost(currentCost);
1599:
1600: // Our time limit for optimizing this round is the time we think
1601: // it will take us to execute the best join order that we've
1602: // found so far (across all rounds of optimizing). In other words,
1603: // don't spend more time optimizing this OptimizerImpl than we think
1604: // it's going to take to execute the best plan. So if we've just
1605: // found a new "best" join order, use that to update our time limit.
1606: if (bestCost.getEstimatedCost() < timeLimit)
1607: timeLimit = bestCost.getEstimatedCost();
1608:
1609: /*
1610: ** Remember the current join order and access path
1611: ** selections as best.
1612: ** NOTE: We want the optimizer trace to print out in
1613: ** join order instead of in table number order, so
1614: ** we use 2 loops.
1615: */
1616: bestJoinOrderUsedPredsFromAbove = usingPredsPushedFromAbove;
1617: for (int i = 0; i < numOptimizables; i++) {
1618: bestJoinOrder[i] = proposedJoinOrder[i];
1619: }
1620: for (int i = 0; i < numOptimizables; i++) {
1621: optimizableList.getOptimizable(bestJoinOrder[i])
1622: .rememberAsBest(planType, this );
1623: }
1624:
1625: /* Remember if a sort is not needed for this plan */
1626: if (requiredRowOrdering != null) {
1627: if (planType == Optimizer.SORT_AVOIDANCE_PLAN)
1628: requiredRowOrdering.sortNotNeeded();
1629: else
1630: requiredRowOrdering.sortNeeded();
1631: }
1632:
1633: if (optimizerTrace) {
1634: if (requiredRowOrdering != null) {
1635: trace(SORT_NEEDED_FOR_ORDERING, planType, 0, 0.0, null);
1636: }
1637: trace(REMEMBERING_BEST_JOIN_ORDER, 0, 0, 0.0, null);
1638: }
1639: }
1640:
1641: /**
1642: * @see org.apache.derby.iapi.sql.compile.Optimizer#costPermutation
1643: *
1644: * @exception StandardException Thrown on error
1645: */
1646: public void costPermutation() throws StandardException {
1647: /*
1648: ** Get the cost of the outer plan so far. This gives us the current
1649: ** estimated rows, ordering, etc.
1650: */
1651: CostEstimate outerCost;
1652: if (joinPosition == 0) {
1653: outerCost = outermostCostEstimate;
1654: } else {
1655: /*
1656: ** NOTE: This is somewhat problematic. We assume here that the
1657: ** outer cost from the best access path for the outer table
1658: ** is OK to use even when costing the sort avoidance path for
1659: ** the inner table. This is probably OK, since all we use
1660: ** from the outer cost is the row count.
1661: */
1662: outerCost = optimizableList.getOptimizable(
1663: proposedJoinOrder[joinPosition - 1])
1664: .getBestAccessPath().getCostEstimate();
1665: }
1666:
1667: /* At this point outerCost should be non-null (DERBY-1777).
1668: * Do the assertion here so that we catch it right away;
1669: * otherwise we'd end up with an NPE somewhere further
1670: * down the tree and it'd be harder to figure out where
1671: * it came from.
1672: */
1673: if (SanityManager.DEBUG) {
1674: SanityManager.ASSERT(outerCost != null,
1675: "outerCost is not expected to be null");
1676: }
1677:
1678: Optimizable optimizable = optimizableList
1679: .getOptimizable(proposedJoinOrder[joinPosition]);
1680:
1681: /*
1682: ** Don't consider non-feasible join strategies.
1683: */
1684: if (!optimizable.feasibleJoinStrategy(predicateList, this )) {
1685: return;
1686: }
1687:
1688: /* Cost the optimizable at the current join position */
1689: optimizable.optimizeIt(this , predicateList, outerCost,
1690: currentRowOrdering);
1691: }
1692:
1693: /**
1694: * @see org.apache.derby.iapi.sql.compile.Optimizer#costOptimizable
1695: *
1696: * @exception StandardException Thrown on error
1697: */
1698: public void costOptimizable(Optimizable optimizable,
1699: TableDescriptor td, ConglomerateDescriptor cd,
1700: OptimizablePredicateList predList, CostEstimate outerCost)
1701: throws StandardException {
1702: /*
1703: ** Don't consider non-feasible join strategies.
1704: */
1705: if (!optimizable.feasibleJoinStrategy(predList, this )) {
1706: return;
1707: }
1708:
1709: /*
1710: ** Classify the predicates according to the given conglomerate.
1711: ** The predicates are classified as start keys, stop keys,
1712: ** qualifiers, and none-of-the-above. They are also ordered
1713: ** to match the ordering of columns in keyed conglomerates (no
1714: ** ordering is done for heaps).
1715: */
1716: // if (predList != null)
1717: // predList.classify(optimizable, cd);
1718: if (ruleBasedOptimization) {
1719: ruleBasedCostOptimizable(optimizable, td, cd, predList,
1720: outerCost);
1721: } else {
1722: costBasedCostOptimizable(optimizable, td, cd, predList,
1723: outerCost);
1724: }
1725: }
1726:
1727: /**
1728: * This method decides whether the given conglomerate descriptor is
1729: * cheapest based on rules, rather than based on cost estimates.
1730: * The rules are:
1731: *
1732: * Covering matching indexes are preferred above all
1733: * Non-covering matching indexes are next in order of preference
1734: * Covering non-matching indexes are next in order of preference
1735: * Heap scans are next in order of preference
1736: * Non-covering, non-matching indexes are last in order of
1737: * preference.
1738: *
1739: * In the current language architecture, there will always be a
1740: * heap, so a non-covering, non-matching index scan will never be
1741: * chosen. However, the optimizer may see a non-covering, non-matching
1742: * index first, in which case it will choose it temporarily as the
1743: * best conglomerate seen so far.
1744: *
1745: * NOTE: This method sets the cost in the optimizable, even though it
1746: * doesn't use the cost to determine which access path to choose. There
1747: * are two reasons for this: the cost might be needed to determine join
1748: * order, and the cost information is copied to the query plan.
1749: */
1750: private void ruleBasedCostOptimizable(Optimizable optimizable,
1751: TableDescriptor td, ConglomerateDescriptor cd,
1752: OptimizablePredicateList predList, CostEstimate outerCost)
1753: throws StandardException {
1754: /* CHOOSE BEST CONGLOMERATE HERE */
1755: ConglomerateDescriptor conglomerateDescriptor = null;
1756: ConglomerateDescriptor bestConglomerateDescriptor = null;
1757: AccessPath bestAp = optimizable.getBestAccessPath();
1758: int lockMode = optimizable.getCurrentAccessPath().getLockMode();
1759:
1760: /*
1761: ** If the current conglomerate better than the best so far?
1762: ** The pecking order is:
1763: ** o covering index useful for predicates
1764: ** (if there are predicates)
1765: ** o index useful for predicates (if there are predicates)
1766: ** o covering index
1767: ** o table scan
1768: */
1769:
1770: /*
1771: ** If there is more than one conglomerate descriptor
1772: ** choose any index that is potentially useful.
1773: */
1774: if (predList != null && predList.useful(optimizable, cd)) {
1775: /*
1776: ** Do not let a non-covering matching index scan supplant a
1777: ** covering matching index scan.
1778: */
1779: boolean newCoveringIndex = optimizable.isCoveringIndex(cd);
1780: if ((!bestAp.getCoveringIndexScan())
1781: || bestAp.getNonMatchingIndexScan()
1782: || newCoveringIndex) {
1783: bestAp.setCostEstimate(estimateTotalCost(predList, cd,
1784: outerCost, optimizable));
1785: bestAp.setConglomerateDescriptor(cd);
1786: bestAp.setNonMatchingIndexScan(false);
1787: bestAp.setCoveringIndexScan(newCoveringIndex);
1788:
1789: bestAp.setLockMode(optimizable.getCurrentAccessPath()
1790: .getLockMode());
1791:
1792: optimizable.rememberJoinStrategyAsBest(bestAp);
1793: }
1794:
1795: return;
1796: }
1797:
1798: /* Remember the "last" covering index.
1799: * NOTE - Since we don't have costing, we just go for the
1800: * last one since that's as good as any
1801: */
1802: if (optimizable.isCoveringIndex(cd)) {
1803: bestAp.setCostEstimate(estimateTotalCost(predList, cd,
1804: outerCost, optimizable));
1805: bestAp.setConglomerateDescriptor(cd);
1806: bestAp.setNonMatchingIndexScan(true);
1807: bestAp.setCoveringIndexScan(true);
1808:
1809: bestAp.setLockMode(optimizable.getCurrentAccessPath()
1810: .getLockMode());
1811:
1812: optimizable.rememberJoinStrategyAsBest(bestAp);
1813: return;
1814: }
1815:
1816: /*
1817: ** If this is the heap, and the best conglomerate so far is a
1818: ** non-covering, non-matching index scan, pick the heap.
1819: */
1820: if ((!bestAp.getCoveringIndexScan())
1821: && bestAp.getNonMatchingIndexScan() && (!cd.isIndex())) {
1822: bestAp.setCostEstimate(estimateTotalCost(predList, cd,
1823: outerCost, optimizable));
1824:
1825: bestAp.setConglomerateDescriptor(cd);
1826:
1827: bestAp.setLockMode(optimizable.getCurrentAccessPath()
1828: .getLockMode());
1829:
1830: optimizable.rememberJoinStrategyAsBest(bestAp);
1831:
1832: /*
1833: ** No need to set non-matching index scan and covering
1834: ** index scan, as these are already correct.
1835: */
1836: return;
1837: }
1838:
1839: /*
1840: ** If all else fails, and no conglomerate has been picked yet,
1841: ** pick this one.
1842: */
1843: bestConglomerateDescriptor = bestAp.getConglomerateDescriptor();
1844: if (bestConglomerateDescriptor == null) {
1845: bestAp.setCostEstimate(estimateTotalCost(predList, cd,
1846: outerCost, optimizable));
1847:
1848: bestAp.setConglomerateDescriptor(cd);
1849:
1850: /*
1851: ** We have determined above that this index is neither covering
1852: ** nor matching.
1853: */
1854: bestAp.setCoveringIndexScan(false);
1855: bestAp.setNonMatchingIndexScan(cd.isIndex());
1856:
1857: bestAp.setLockMode(optimizable.getCurrentAccessPath()
1858: .getLockMode());
1859:
1860: optimizable.rememberJoinStrategyAsBest(bestAp);
1861: }
1862:
1863: return;
1864: }
1865:
1866: /**
1867: * This method decides whether the given conglomerate descriptor is
1868: * cheapest based on cost, rather than based on rules. It compares
1869: * the cost of using the given ConglomerateDescriptor with the cost
1870: * of using the best ConglomerateDescriptor so far.
1871: */
1872: private void costBasedCostOptimizable(Optimizable optimizable,
1873: TableDescriptor td, ConglomerateDescriptor cd,
1874: OptimizablePredicateList predList, CostEstimate outerCost)
1875: throws StandardException {
1876: CostEstimate estimatedCost = estimateTotalCost(predList, cd,
1877: outerCost, optimizable);
1878:
1879: // Before considering the cost, make sure we set the optimizable's
1880: // "current" cost to be the one that we found. Doing this allows
1881: // us to compare "current" with "best" later on to find out if
1882: // the "current" plan is also the "best" one this round--if it's
1883: // not then we'll have to revert back to whatever the best plan is.
1884: // That check is performed in getNextDecoratedPermutation() of
1885: // this class.
1886: optimizable.getCurrentAccessPath().setCostEstimate(
1887: estimatedCost);
1888:
1889: /*
1890: ** Skip this access path if it takes too much memory.
1891: **
1892: ** NOTE: The default assumption here is that the number of rows in
1893: ** a single scan is the total number of rows divided by the number
1894: ** of outer rows. The optimizable may over-ride this assumption.
1895: */
1896: // RESOLVE: The following call to memoryUsageOK does not behave
1897: // correctly if outerCost.rowCount() is POSITIVE_INFINITY; see
1898: // DERBY-1259.
1899: if (!optimizable.memoryUsageOK(estimatedCost.rowCount()
1900: / outerCost.rowCount(), maxMemoryPerTable)) {
1901: if (optimizerTrace) {
1902: trace(SKIPPING_DUE_TO_EXCESS_MEMORY, 0, 0, 0.0, null);
1903: }
1904: return;
1905: }
1906:
1907: /* Pick the cheapest cost for this particular optimizable. */
1908: AccessPath ap = optimizable.getBestAccessPath();
1909: CostEstimate bestCostEstimate = ap.getCostEstimate();
1910:
1911: if ((bestCostEstimate == null)
1912: || bestCostEstimate.isUninitialized()
1913: || (estimatedCost.compare(bestCostEstimate) < 0)) {
1914: ap.setConglomerateDescriptor(cd);
1915: ap.setCostEstimate(estimatedCost);
1916: ap.setCoveringIndexScan(optimizable.isCoveringIndex(cd));
1917:
1918: /*
1919: ** It's a non-matching index scan either if there is no
1920: ** predicate list, or nothing in the predicate list is useful
1921: ** for limiting the scan.
1922: */
1923: ap.setNonMatchingIndexScan((predList == null)
1924: || (!(predList.useful(optimizable, cd))));
1925: ap.setLockMode(optimizable.getCurrentAccessPath()
1926: .getLockMode());
1927: optimizable.rememberJoinStrategyAsBest(ap);
1928: }
1929:
1930: /*
1931: ** Keep track of the best sort-avoidance path if there is a
1932: ** required row ordering.
1933: */
1934: if (requiredRowOrdering != null) {
1935: /*
1936: ** The current optimizable can avoid a sort only if the
1937: ** outer one does, also (if there is an outer one).
1938: */
1939: if (joinPosition == 0
1940: || optimizableList.getOptimizable(
1941: proposedJoinOrder[joinPosition - 1])
1942: .considerSortAvoidancePath()) {
1943: /*
1944: ** There is a required row ordering - does the proposed access
1945: ** path avoid a sort?
1946: */
1947: if (requiredRowOrdering.sortRequired(
1948: currentRowOrdering, assignedTableMap) == RequiredRowOrdering.NOTHING_REQUIRED) {
1949: ap = optimizable.getBestSortAvoidancePath();
1950: bestCostEstimate = ap.getCostEstimate();
1951:
1952: /* Is this the cheapest sort-avoidance path? */
1953: if ((bestCostEstimate == null)
1954: || bestCostEstimate.isUninitialized()
1955: || (estimatedCost.compare(bestCostEstimate) < 0)) {
1956: ap.setConglomerateDescriptor(cd);
1957: ap.setCostEstimate(estimatedCost);
1958: ap.setCoveringIndexScan(optimizable
1959: .isCoveringIndex(cd));
1960:
1961: /*
1962: ** It's a non-matching index scan either if there is no
1963: ** predicate list, or nothing in the predicate list is
1964: ** useful for limiting the scan.
1965: */
1966: ap
1967: .setNonMatchingIndexScan((predList == null)
1968: || (!(predList.useful(
1969: optimizable, cd))));
1970: ap.setLockMode(optimizable
1971: .getCurrentAccessPath().getLockMode());
1972: optimizable.rememberJoinStrategyAsBest(ap);
1973: optimizable.rememberSortAvoidancePath();
1974:
1975: /*
1976: ** Remember the current row ordering as best
1977: */
1978: currentRowOrdering.copy(bestRowOrdering);
1979: }
1980: }
1981: }
1982: }
1983: }
1984:
1985: /**
1986: * This is the version of costOptimizable for non-base-tables.
1987: *
1988: * @see Optimizer#considerCost
1989: *
1990: * @exception StandardException Thrown on error
1991: */
1992: public void considerCost(Optimizable optimizable,
1993: OptimizablePredicateList predList,
1994: CostEstimate estimatedCost, CostEstimate outerCost)
1995: throws StandardException {
1996: /*
1997: ** Don't consider non-feasible join strategies.
1998: */
1999: if (!optimizable.feasibleJoinStrategy(predList, this )) {
2000: return;
2001: }
2002:
2003: // Before considering the cost, make sure we set the optimizable's
2004: // "current" cost to be the one that we received. Doing this allows
2005: // us to compare "current" with "best" later on to find out if
2006: // the "current" plan is also the "best" one this round--if it's
2007: // not then we'll have to revert back to whatever the best plan is.
2008: // That check is performed in getNextDecoratedPermutation() of
2009: // this class.
2010: optimizable.getCurrentAccessPath().setCostEstimate(
2011: estimatedCost);
2012:
2013: /*
2014: ** Skip this access path if it takes too much memory.
2015: **
2016: ** NOTE: The default assumption here is that the number of rows in
2017: ** a single scan is the total number of rows divided by the number
2018: ** of outer rows. The optimizable may over-ride this assumption.
2019: */
2020:
2021: // RESOLVE: The following call to memoryUsageOK does not behave
2022: // correctly if outerCost.rowCount() is POSITIVE_INFINITY; see
2023: // DERBY-1259.
2024: if (!optimizable.memoryUsageOK(estimatedCost.rowCount()
2025: / outerCost.rowCount(), maxMemoryPerTable)) {
2026: if (optimizerTrace) {
2027: trace(SKIPPING_DUE_TO_EXCESS_MEMORY, 0, 0, 0.0, null);
2028: }
2029: return;
2030: }
2031:
2032: /* Pick the cheapest cost for this particular optimizable.
2033: * NOTE: Originally, the code only chose the new access path if
2034: * it was cheaper than the old access path. However, I (Jerry)
2035: * found that the new and old costs were the same for a derived
2036: * table and the old access path did not have a join strategy
2037: * associated with it in that case. So, we now choose the new
2038: * access path if it is the same cost or cheaper than the current
2039: * access path.
2040: */
2041: AccessPath ap = optimizable.getBestAccessPath();
2042: CostEstimate bestCostEstimate = ap.getCostEstimate();
2043:
2044: if ((bestCostEstimate == null)
2045: || bestCostEstimate.isUninitialized()
2046: || (estimatedCost.compare(bestCostEstimate) <= 0)) {
2047: ap.setCostEstimate(estimatedCost);
2048: optimizable.rememberJoinStrategyAsBest(ap);
2049: }
2050:
2051: /*
2052: ** Keep track of the best sort-avoidance path if there is a
2053: ** required row ordering.
2054: */
2055: if (requiredRowOrdering != null) {
2056: /*
2057: ** The current optimizable can avoid a sort only if the
2058: ** outer one does, also (if there is an outer one).
2059: */
2060: if (joinPosition == 0
2061: || optimizableList.getOptimizable(
2062: proposedJoinOrder[joinPosition - 1])
2063: .considerSortAvoidancePath()) {
2064: /*
2065: ** There is a required row ordering - does the proposed access
2066: ** path avoid a sort?
2067: */
2068: if (requiredRowOrdering.sortRequired(
2069: currentRowOrdering, assignedTableMap) == RequiredRowOrdering.NOTHING_REQUIRED) {
2070: ap = optimizable.getBestSortAvoidancePath();
2071: bestCostEstimate = ap.getCostEstimate();
2072:
2073: /* Is this the cheapest sort-avoidance path? */
2074: if ((bestCostEstimate == null)
2075: || bestCostEstimate.isUninitialized()
2076: || (estimatedCost.compare(bestCostEstimate) < 0)) {
2077: ap.setCostEstimate(estimatedCost);
2078: optimizable.rememberJoinStrategyAsBest(ap);
2079: optimizable.rememberSortAvoidancePath();
2080:
2081: /*
2082: ** Remember the current row ordering as best
2083: */
2084: currentRowOrdering.copy(bestRowOrdering);
2085: }
2086: }
2087: }
2088: }
2089: }
2090:
2091: /**
2092: * @see org.apache.derby.iapi.sql.compile.Optimizer#getDataDictionary
2093: */
2094:
2095: public DataDictionary getDataDictionary() {
2096: return dDictionary;
2097: }
2098:
2099: /**
2100: * @see Optimizer#modifyAccessPaths
2101: *
2102: * @exception StandardException Thrown on error
2103: */
2104: public void modifyAccessPaths() throws StandardException {
2105: if (optimizerTrace) {
2106: trace(MODIFYING_ACCESS_PATHS, 0, 0, 0.0, null);
2107: }
2108:
2109: if (!foundABestPlan) {
2110: if (optimizerTrace) {
2111: trace(NO_BEST_PLAN, 0, 0, 0.0, null);
2112: }
2113:
2114: throw StandardException
2115: .newException(SQLState.LANG_NO_BEST_PLAN_FOUND);
2116: }
2117:
2118: /* Change the join order of the list of optimizables */
2119: optimizableList.reOrder(bestJoinOrder);
2120:
2121: /* Form a bit map of the tables as they are put into the join order */
2122: JBitSet outerTables = new JBitSet(numOptimizables);
2123:
2124: /* Modify the access path of each table, as necessary */
2125: for (int ictr = 0; ictr < numOptimizables; ictr++) {
2126: Optimizable optimizable = optimizableList
2127: .getOptimizable(ictr);
2128:
2129: /* Current table is treated as an outer table */
2130: outerTables.or(optimizable.getReferencedTableMap());
2131:
2132: /*
2133: ** Push any appropriate predicates from this optimizer's list
2134: ** to the optimizable, as appropriate.
2135: */
2136: pushPredicates(optimizable, outerTables);
2137:
2138: optimizableList.setOptimizable(ictr, optimizable
2139: .modifyAccessPath(outerTables));
2140: }
2141: }
2142:
2143: /** @see Optimizer#newCostEstimate */
2144: public CostEstimate newCostEstimate() {
2145: return new CostEstimateImpl();
2146: }
2147:
2148: /** @see Optimizer#getOptimizedCost */
2149: public CostEstimate getOptimizedCost() {
2150: return bestCost;
2151: }
2152:
2153: /**
2154: * @see Optimizer#getFinalCost
2155: *
2156: * Sum up the cost of all of the trulyTheBestAccessPaths
2157: * for the Optimizables in our list. Assumption is that
2158: * we only get here after optimization has completed--i.e.
2159: * while modifying access paths.
2160: */
2161: public CostEstimate getFinalCost() {
2162: // If we already did this once, just return the result.
2163: if (finalCostEstimate != null)
2164: return finalCostEstimate;
2165:
2166: // The total cost is the sum of all the costs, but the total
2167: // number of rows is the number of rows returned by the innermost
2168: // optimizable.
2169: finalCostEstimate = getNewCostEstimate(0.0d, 0.0d, 0.0d);
2170: CostEstimate ce = null;
2171: for (int i = 0; i < bestJoinOrder.length; i++) {
2172: ce = optimizableList.getOptimizable(bestJoinOrder[i])
2173: .getTrulyTheBestAccessPath().getCostEstimate();
2174:
2175: finalCostEstimate.setCost(finalCostEstimate
2176: .getEstimatedCost()
2177: + ce.getEstimatedCost(), ce.rowCount(), ce
2178: .singleScanRowCount());
2179: }
2180:
2181: return finalCostEstimate;
2182: }
2183:
2184: /** @see Optimizer#setOuterRows */
2185: public void setOuterRows(double outerRows) {
2186: outermostCostEstimate.setCost(outermostCostEstimate
2187: .getEstimatedCost(), outerRows, outermostCostEstimate
2188: .singleScanRowCount());
2189: }
2190:
2191: /** @see Optimizer#tableLockThreshold */
2192: public int tableLockThreshold() {
2193: return tableLockThreshold;
2194: }
2195:
2196: /**
2197: * Get the number of join strategies supported by this optimizer.
2198: */
2199: public int getNumberOfJoinStrategies() {
2200: return joinStrategies.length;
2201: }
2202:
2203: /** @see Optimizer#getJoinStrategy */
2204: public JoinStrategy getJoinStrategy(int whichStrategy) {
2205: if (SanityManager.DEBUG) {
2206: if (whichStrategy < 0
2207: || whichStrategy >= joinStrategies.length) {
2208: SanityManager.THROWASSERT("whichStrategy value "
2209: + whichStrategy
2210: + " out of range - should be between 0 and "
2211: + (joinStrategies.length - 1));
2212: }
2213:
2214: if (joinStrategies[whichStrategy] == null) {
2215: SanityManager.THROWASSERT("Strategy " + whichStrategy
2216: + " not filled in.");
2217: }
2218: }
2219:
2220: return joinStrategies[whichStrategy];
2221: }
2222:
2223: /** @see Optimizer#getJoinStrategy */
2224: public JoinStrategy getJoinStrategy(String whichStrategy) {
2225: JoinStrategy retval = null;
2226: String upperValue = StringUtil.SQLToUpperCase(whichStrategy);
2227:
2228: for (int i = 0; i < joinStrategies.length; i++) {
2229: if (upperValue.equals(joinStrategies[i].getName())) {
2230: retval = joinStrategies[i];
2231: }
2232: }
2233:
2234: return retval;
2235: }
2236:
2237: /**
2238: @see Optimizer#uniqueJoinWithOuterTable
2239:
2240: @exception StandardException Thrown on error
2241: */
2242: public double uniqueJoinWithOuterTable(
2243: OptimizablePredicateList predList) throws StandardException {
2244: double retval = -1.0;
2245: double numUniqueKeys = 1.0;
2246: double currentRows = currentCost.rowCount();
2247:
2248: if (predList != null) {
2249:
2250: for (int i = joinPosition - 1; i >= 0; i--) {
2251: Optimizable opt = optimizableList
2252: .getOptimizable(proposedJoinOrder[i]);
2253: double uniqueKeysThisOptimizable = opt
2254: .uniqueJoin(predList);
2255: if (uniqueKeysThisOptimizable > 0.0)
2256: numUniqueKeys *= opt.uniqueJoin(predList);
2257: }
2258: }
2259:
2260: if (numUniqueKeys != 1.0) {
2261: retval = numUniqueKeys / currentRows;
2262: }
2263:
2264: return retval;
2265: }
2266:
2267: private boolean isPushable(OptimizablePredicate pred) {
2268: /* Predicates which contain subqueries that are not materializable are
2269: * not currently pushable.
2270: */
2271: if (pred.hasSubquery()) {
2272: return false;
2273: } else {
2274: return true;
2275: }
2276: }
2277:
2278: /**
2279: * Estimate the total cost of doing a join with the given optimizable.
2280: *
2281: * @exception StandardException Thrown on error
2282: */
2283: private CostEstimate estimateTotalCost(
2284: OptimizablePredicateList predList,
2285: ConglomerateDescriptor cd, CostEstimate outerCost,
2286: Optimizable optimizable) throws StandardException {
2287: /* Get the cost of a single scan */
2288: CostEstimate resultCost = optimizable.estimateCost(predList,
2289: cd, outerCost, this , currentRowOrdering);
2290:
2291: return resultCost;
2292: }
2293:
2294: /** @see Optimizer#getLevel */
2295: public int getLevel() {
2296: return 1;
2297: }
2298:
2299: public CostEstimateImpl getNewCostEstimate(double theCost,
2300: double theRowCount, double theSingleScanRowCount) {
2301: return new CostEstimateImpl(theCost, theRowCount,
2302: theSingleScanRowCount);
2303: }
2304:
2305: // Optimzer trace
2306: public void trace(int traceFlag, int intParam1, int intParam2,
2307: double doubleParam, Object objectParam1) {
2308: }
2309:
2310: /** @see Optimizer#useStatistics */
2311: public boolean useStatistics() {
2312: return useStatistics && optimizableList.useStatistics();
2313: }
2314:
2315: /**
2316: * Process (i.e. add, load, or remove) current best join order as the
2317: * best one for some outer query or ancestor node, represented by another
2318: * OptimizerImpl or an instance of FromTable, respectively. Then
2319: * iterate through our optimizableList and tell each Optimizable
2320: * to do the same. See Optimizable.updateBestPlan() for more on why
2321: * this is necessary.
2322: *
2323: * @param action Indicates whether to add, load, or remove the plan
2324: * @param planKey Object to use as the map key when adding/looking up
2325: * a plan. If this is an instance of OptimizerImpl then it corresponds
2326: * to an outer query; otherwise it's some Optimizable above this
2327: * OptimizerImpl that could potentially reject plans chosen by this
2328: * OptimizerImpl.
2329: */
2330: protected void updateBestPlanMaps(short action, Object planKey)
2331: throws StandardException {
2332: // First we process this OptimizerImpl's best join order. If there's
2333: // only one optimizable in the list, then there's only one possible
2334: // join order, so don't bother.
2335: if (numOptimizables > 1) {
2336: int[] joinOrder = null;
2337: if (action == FromTable.REMOVE_PLAN) {
2338: if (savedJoinOrders != null) {
2339: savedJoinOrders.remove(planKey);
2340: if (savedJoinOrders.size() == 0)
2341: savedJoinOrders = null;
2342: }
2343: } else if (action == FromTable.ADD_PLAN) {
2344: // If the savedJoinOrder map already exists, search for the
2345: // join order for the target optimizer and reuse that.
2346: if (savedJoinOrders == null)
2347: savedJoinOrders = new HashMap();
2348: else
2349: joinOrder = (int[]) savedJoinOrders.get(planKey);
2350:
2351: // If we don't already have a join order array for the optimizer,
2352: // create a new one.
2353: if (joinOrder == null)
2354: joinOrder = new int[numOptimizables];
2355:
2356: // Now copy current bestJoinOrder and save it.
2357: for (int i = 0; i < bestJoinOrder.length; i++)
2358: joinOrder[i] = bestJoinOrder[i];
2359:
2360: savedJoinOrders.put(planKey, joinOrder);
2361: } else {
2362: // If we get here, we want to load the best join order from our
2363: // map into this OptimizerImpl's bestJoinOrder array.
2364:
2365: // If we don't have any join orders saved, then there's nothing to
2366: // load. This can happen if the optimizer tried some join order
2367: // for which there was no valid plan.
2368: if (savedJoinOrders != null) {
2369: joinOrder = (int[]) savedJoinOrders.get(planKey);
2370: if (joinOrder != null) {
2371: // Load the join order we found into our
2372: // bestJoinOrder array.
2373: for (int i = 0; i < joinOrder.length; i++)
2374: bestJoinOrder[i] = joinOrder[i];
2375: }
2376: }
2377: }
2378: }
2379:
2380: // Now iterate through all Optimizables in this OptimizerImpl's
2381: // list and add/load/remove the best plan "mapping" for each one,
2382: // as described in in Optimizable.updateBestPlanMap().
2383: for (int i = optimizableList.size() - 1; i >= 0; i--) {
2384: optimizableList.getOptimizable(i).updateBestPlanMap(action,
2385: planKey);
2386: }
2387: }
2388:
2389: /**
2390: * Add scoped predicates to this optimizer's predicateList. This method
2391: * is intended for use during the modifyAccessPath() phase of
2392: * compilation, as it allows nodes (esp. SelectNodes) to add to the
2393: * list of predicates available for the final "push" before code
2394: * generation. Just as the constructor for this class allows a
2395: * caller to specify a predicate list to use during the optimization
2396: * phase, this method allows a caller to specify a predicate list to
2397: * use during the modify-access-paths phase.
2398: *
2399: * Before adding the received predicates, this method also
2400: * clears out any scoped predicates that might be sitting in
2401: * OptimizerImpl's list from the last round of optimizing.
2402: *
2403: * @param pList List of predicates to add to this OptimizerImpl's
2404: * own list for pushing.
2405: */
2406: protected void addScopedPredicatesToList(PredicateList pList)
2407: throws StandardException {
2408: if ((pList == null) || (pList == predicateList))
2409: // nothing to do.
2410: return;
2411:
2412: if (predicateList == null)
2413: // in this case, there is no 'original' predicateList, so we
2414: // can just create one.
2415: predicateList = new PredicateList();
2416:
2417: // First, we need to go through and remove any predicates in this
2418: // optimizer's list that may have been pushed here from outer queries
2419: // during the previous round(s) of optimization. We know if the
2420: // predicate was pushed from an outer query because it will have
2421: // been scoped to the node for which this OptimizerImpl was
2422: // created.
2423: Predicate pred = null;
2424: for (int i = predicateList.size() - 1; i >= 0; i--) {
2425: pred = (Predicate) predicateList.getOptPredicate(i);
2426: if (pred.isScopedForPush())
2427: predicateList.removeOptPredicate(i);
2428: }
2429:
2430: // Now transfer scoped predicates in the received list to
2431: // this OptimizerImpl's list, where appropriate.
2432: for (int i = pList.size() - 1; i >= 0; i--) {
2433: pred = (Predicate) pList.getOptPredicate(i);
2434: if (pred.isScopedToSourceResultSet()) {
2435: // Clear the scoped predicate's scan flags; they'll be set
2436: // as appropriate when they make it to the restrictionList
2437: // of the scoped pred's source result set.
2438: pred.clearScanFlags();
2439: predicateList.addOptPredicate(pred);
2440: pList.removeOptPredicate(i);
2441: }
2442: }
2443:
2444: return;
2445: }
2446:
2447: }
|