0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.sql.compile.FromTable
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.context.ContextManager;
0025:
0026: import org.apache.derby.iapi.sql.compile.Optimizable;
0027: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
0028: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
0029: import org.apache.derby.iapi.sql.compile.Optimizer;
0030: import org.apache.derby.iapi.sql.compile.CostEstimate;
0031: import org.apache.derby.iapi.sql.compile.JoinStrategy;
0032: import org.apache.derby.iapi.sql.compile.AccessPath;
0033: import org.apache.derby.iapi.sql.compile.RowOrdering;
0034: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
0035:
0036: import org.apache.derby.iapi.sql.dictionary.*;
0037:
0038: import org.apache.derby.iapi.types.DataTypeDescriptor;
0039:
0040: import org.apache.derby.iapi.error.StandardException;
0041: import org.apache.derby.iapi.services.sanity.SanityManager;
0042:
0043: import org.apache.derby.iapi.reference.SQLState;
0044: import org.apache.derby.iapi.error.StandardException;
0045:
0046: import org.apache.derby.impl.sql.execute.HashScanResultSet;
0047:
0048: import org.apache.derby.iapi.util.JBitSet;
0049: import org.apache.derby.iapi.services.io.FormatableBitSet;
0050: import org.apache.derby.iapi.util.StringUtil;
0051: import org.apache.derby.catalog.UUID;
0052:
0053: import java.util.Enumeration;
0054: import java.util.Properties;
0055: import java.util.Vector;
0056: import java.util.HashMap;
0057:
0058: /**
0059: * A FromTable represents a table in the FROM clause of a DML statement.
0060: * It can be either a base table, a subquery or a project restrict.
0061: *
0062: * @see FromBaseTable
0063: * @see FromSubquery
0064: * @see ProjectRestrictNode
0065: *
0066: * @author Jeff Lichtman
0067: */
0068: abstract class FromTable extends ResultSetNode implements Optimizable {
0069: Properties tableProperties;
0070: String correlationName;
0071: TableName corrTableName;
0072: int tableNumber;
0073: /* (Query block) level is 0-based. */
0074: /* RESOLVE - View resolution will have to update the level within
0075: * the view tree.
0076: */
0077: int level;
0078: // hashKeyColumns are 0-based column #s within the row returned by the store for hash scans
0079: int[] hashKeyColumns;
0080:
0081: // overrides for hash join
0082: int initialCapacity = HashScanResultSet.DEFAULT_INITIAL_CAPACITY;
0083: float loadFactor = HashScanResultSet.DEFAULT_LOADFACTOR;
0084: int maxCapacity = HashScanResultSet.DEFAULT_MAX_CAPACITY;
0085:
0086: AccessPathImpl currentAccessPath;
0087: AccessPathImpl bestAccessPath;
0088: AccessPathImpl bestSortAvoidancePath;
0089: AccessPathImpl trulyTheBestAccessPath;
0090:
0091: private int joinStrategyNumber;
0092:
0093: protected String userSpecifiedJoinStrategy;
0094:
0095: protected CostEstimate bestCostEstimate;
0096:
0097: private FormatableBitSet refCols;
0098:
0099: private double perRowUsage = -1;
0100:
0101: private boolean considerSortAvoidancePath;
0102:
0103: /**
0104: Set of object->trulyTheBestAccessPath mappings used to keep track
0105: of which of this Optimizable's "trulyTheBestAccessPath" was the best
0106: with respect to a specific outer query or ancestor node. In the case
0107: of an outer query, the object key will be an instance of OptimizerImpl.
0108: In the case of an ancestor node, the object key will be that node itself.
0109: Each ancestor node or outer query could potentially have a different
0110: idea of what this Optimizable's "best access path" is, so we have to
0111: keep track of them all.
0112: */
0113: private HashMap bestPlanMap;
0114:
0115: /** Operations that can be performed on bestPlanMap. */
0116: protected static final short REMOVE_PLAN = 0;
0117: protected static final short ADD_PLAN = 1;
0118: protected static final short LOAD_PLAN = 2;
0119:
0120: /** the original unbound table name */
0121: protected TableName origTableName;
0122:
0123: /**
0124: * Initializer for a table in a FROM list.
0125: *
0126: * @param correlationName The correlation name
0127: * @param tableProperties Properties list associated with the table
0128: */
0129: public void init(Object correlationName, Object tableProperties) {
0130: this .correlationName = (String) correlationName;
0131: this .tableProperties = (Properties) tableProperties;
0132: tableNumber = -1;
0133: bestPlanMap = null;
0134: }
0135:
0136: /**
0137: * Get this table's correlation name, if any.
0138: */
0139: public String getCorrelationName() {
0140: return correlationName;
0141: }
0142:
0143: /*
0144: * Optimizable interface
0145: */
0146:
0147: /**
0148: * @see org.apache.derby.iapi.sql.compile.Optimizable#optimizeIt
0149: *
0150: * @exception StandardException Thrown on error
0151: *
0152: */
0153: public CostEstimate optimizeIt(Optimizer optimizer,
0154: OptimizablePredicateList predList, CostEstimate outerCost,
0155: RowOrdering rowOrdering) throws StandardException {
0156: // It's possible that a call to optimize the left/right will cause
0157: // a new "truly the best" plan to be stored in the underlying base
0158: // tables. If that happens and then we decide to skip that plan
0159: // (which we might do if the call to "considerCost()" below decides
0160: // the current path is infeasible or not the best) we need to be
0161: // able to revert back to the "truly the best" plans that we had
0162: // saved before we got here. So with this next call we save the
0163: // current plans using "this" node as the key. If needed, we'll
0164: // then make the call to revert the plans in OptimizerImpl's
0165: // getNextDecoratedPermutation() method.
0166: updateBestPlanMap(ADD_PLAN, this );
0167:
0168: CostEstimate singleScanCost = estimateCost(predList,
0169: (ConglomerateDescriptor) null, outerCost, optimizer,
0170: rowOrdering);
0171:
0172: /* Make sure there is a cost estimate to set */
0173: getCostEstimate(optimizer);
0174:
0175: setCostEstimate(singleScanCost);
0176:
0177: /* Optimize any subqueries that need to get optimized and
0178: * are not optimized any where else. (Like those
0179: * in a RowResultSetNode.)
0180: */
0181: optimizeSubqueries(getDataDictionary(), costEstimate.rowCount());
0182:
0183: /*
0184: ** Get the cost of this result set in the context of the whole plan.
0185: */
0186: getCurrentAccessPath().getJoinStrategy().estimateCost(this ,
0187: predList, (ConglomerateDescriptor) null, outerCost,
0188: optimizer, getCostEstimate());
0189:
0190: optimizer.considerCost(this , predList, getCostEstimate(),
0191: outerCost);
0192:
0193: return getCostEstimate();
0194: }
0195:
0196: /**
0197: @see Optimizable#nextAccessPath
0198: @exception StandardException Thrown on error
0199: */
0200: public boolean nextAccessPath(Optimizer optimizer,
0201: OptimizablePredicateList predList, RowOrdering rowOrdering)
0202: throws StandardException {
0203: int numStrat = optimizer.getNumberOfJoinStrategies();
0204: boolean found = false;
0205: AccessPath ap = getCurrentAccessPath();
0206:
0207: /*
0208: ** Most Optimizables have no ordering, so tell the rowOrdering that
0209: ** this Optimizable is unordered, if appropriate.
0210: */
0211: if (userSpecifiedJoinStrategy != null) {
0212: /*
0213: ** User specified a join strategy, so we should look at only one
0214: ** strategy. If there is a current strategy, we have already
0215: ** looked at the strategy, so go back to null.
0216: */
0217: if (ap.getJoinStrategy() != null) {
0218: ap.setJoinStrategy((JoinStrategy) null);
0219:
0220: found = false;
0221: } else {
0222: ap.setJoinStrategy(optimizer
0223: .getJoinStrategy(userSpecifiedJoinStrategy));
0224:
0225: if (ap.getJoinStrategy() == null) {
0226: throw StandardException.newException(
0227: SQLState.LANG_INVALID_JOIN_STRATEGY,
0228: userSpecifiedJoinStrategy,
0229: getBaseTableName());
0230: }
0231:
0232: found = true;
0233: }
0234: } else if (joinStrategyNumber < numStrat) {
0235: /* Step through the join strategies. */
0236: ap.setJoinStrategy(optimizer
0237: .getJoinStrategy(joinStrategyNumber));
0238:
0239: joinStrategyNumber++;
0240:
0241: found = true;
0242:
0243: optimizer.trace(Optimizer.CONSIDERING_JOIN_STRATEGY,
0244: tableNumber, 0, 0.0, ap.getJoinStrategy());
0245: }
0246:
0247: /*
0248: ** Tell the RowOrdering about columns that are equal to constant
0249: ** expressions.
0250: */
0251: tellRowOrderingAboutConstantColumns(rowOrdering, predList);
0252:
0253: return found;
0254: }
0255:
0256: /** Most Optimizables cannot be ordered */
0257: protected boolean canBeOrdered() {
0258: return false;
0259: }
0260:
0261: /** @see Optimizable#getCurrentAccessPath */
0262: public AccessPath getCurrentAccessPath() {
0263: return currentAccessPath;
0264: }
0265:
0266: /** @see Optimizable#getBestAccessPath */
0267: public AccessPath getBestAccessPath() {
0268: return bestAccessPath;
0269: }
0270:
0271: /** @see Optimizable#getBestSortAvoidancePath */
0272: public AccessPath getBestSortAvoidancePath() {
0273: return bestSortAvoidancePath;
0274: }
0275:
0276: /** @see Optimizable#getTrulyTheBestAccessPath */
0277: public AccessPath getTrulyTheBestAccessPath() {
0278: return trulyTheBestAccessPath;
0279: }
0280:
0281: /** @see Optimizable#rememberSortAvoidancePath */
0282: public void rememberSortAvoidancePath() {
0283: considerSortAvoidancePath = true;
0284: }
0285:
0286: /** @see Optimizable#considerSortAvoidancePath */
0287: public boolean considerSortAvoidancePath() {
0288: return considerSortAvoidancePath;
0289: }
0290:
0291: /** @see Optimizable#rememberJoinStrategyAsBest */
0292: public void rememberJoinStrategyAsBest(AccessPath ap) {
0293: Optimizer optimizer = ap.getOptimizer();
0294:
0295: ap.setJoinStrategy(getCurrentAccessPath().getJoinStrategy());
0296:
0297: optimizer.trace(Optimizer.REMEMBERING_JOIN_STRATEGY,
0298: tableNumber, 0, 0.0, getCurrentAccessPath()
0299: .getJoinStrategy());
0300:
0301: if (ap == bestAccessPath) {
0302: optimizer.trace(
0303: Optimizer.REMEMBERING_BEST_ACCESS_PATH_SUBSTRING,
0304: tableNumber, 0, 0.0, ap);
0305: } else if (ap == bestSortAvoidancePath) {
0306: optimizer
0307: .trace(
0308: Optimizer.REMEMBERING_BEST_SORT_AVOIDANCE_ACCESS_PATH_SUBSTRING,
0309: tableNumber, 0, 0.0, ap);
0310: } else {
0311: /* We currently get here when optimizing an outer join.
0312: * (Problem predates optimizer trace change.)
0313: * RESOLVE - fix this at some point.
0314: if (SanityManager.DEBUG)
0315: {
0316: SanityManager.THROWASSERT(
0317: "unknown access path type");
0318: }
0319: */
0320: optimizer
0321: .trace(
0322: Optimizer.REMEMBERING_BEST_UNKNOWN_ACCESS_PATH_SUBSTRING,
0323: tableNumber, 0, 0.0, ap);
0324: }
0325: }
0326:
0327: /** @see Optimizable#getTableDescriptor */
0328: public TableDescriptor getTableDescriptor() {
0329: if (SanityManager.DEBUG) {
0330: SanityManager
0331: .THROWASSERT("getTableDescriptor() not expected to be called for "
0332: + getClass().toString());
0333: }
0334:
0335: return null;
0336: }
0337:
0338: /**
0339: * @see org.apache.derby.iapi.sql.compile.Optimizable#pushOptPredicate
0340: *
0341: * @exception StandardException Thrown on error
0342: */
0343:
0344: public boolean pushOptPredicate(
0345: OptimizablePredicate optimizablePredicate)
0346: throws StandardException {
0347: return false;
0348: }
0349:
0350: /**
0351: * @see Optimizable#pullOptPredicates
0352: *
0353: * @exception StandardException Thrown on error
0354: */
0355: public void pullOptPredicates(
0356: OptimizablePredicateList optimizablePredicates)
0357: throws StandardException {
0358: /* For most types of Optimizable, do nothing */
0359: return;
0360: }
0361:
0362: /**
0363: * @see Optimizable#modifyAccessPath
0364: *
0365: * @exception StandardException Thrown on error
0366: */
0367: public Optimizable modifyAccessPath(JBitSet outerTables)
0368: throws StandardException {
0369: /* For most types of Optimizable, do nothing */
0370: return this ;
0371: }
0372:
0373: /**
0374: * @see Optimizable#isCoveringIndex
0375: * @exception StandardException Thrown on error
0376: */
0377: public boolean isCoveringIndex(ConglomerateDescriptor cd)
0378: throws StandardException {
0379: return false;
0380: }
0381:
0382: /** @see Optimizable#getProperties */
0383: public Properties getProperties() {
0384: return tableProperties;
0385: }
0386:
0387: /** @see Optimizable#setProperties */
0388: public void setProperties(Properties tableProperties) {
0389: this .tableProperties = tableProperties;
0390: }
0391:
0392: /** @see Optimizable#verifyProperties
0393: * @exception StandardException Thrown on error
0394: */
0395: public void verifyProperties(DataDictionary dDictionary)
0396: throws StandardException {
0397: if (tableProperties == null) {
0398: return;
0399: }
0400: /* Check here for:
0401: * invalid properties key
0402: * invalid joinStrategy
0403: * invalid value for hashInitialCapacity
0404: * invalid value for hashLoadFactor
0405: * invalid value for hashMaxCapacity
0406: */
0407: boolean indexSpecified = false;
0408: Enumeration e = tableProperties.keys();
0409: while (e.hasMoreElements()) {
0410: String key = (String) e.nextElement();
0411: String value = (String) tableProperties.get(key);
0412:
0413: if (key.equals("joinStrategy")) {
0414: userSpecifiedJoinStrategy = StringUtil
0415: .SQLToUpperCase(value);
0416: } else if (key.equals("hashInitialCapacity")) {
0417: initialCapacity = getIntProperty(value, key);
0418:
0419: // verify that the specified value is valid
0420: if (initialCapacity <= 0) {
0421: throw StandardException
0422: .newException(
0423: SQLState.LANG_INVALID_HASH_INITIAL_CAPACITY,
0424: String.valueOf(initialCapacity));
0425: }
0426: } else if (key.equals("hashLoadFactor")) {
0427: try {
0428: loadFactor = Float.valueOf(value).floatValue();
0429: } catch (NumberFormatException nfe) {
0430: throw StandardException
0431: .newException(
0432: SQLState.LANG_INVALID_NUMBER_FORMAT_FOR_OVERRIDE,
0433: value, key);
0434: }
0435:
0436: // verify that the specified value is valid
0437: if (loadFactor <= 0.0 || loadFactor > 1.0) {
0438: throw StandardException.newException(
0439: SQLState.LANG_INVALID_HASH_LOAD_FACTOR,
0440: value);
0441: }
0442: } else if (key.equals("hashMaxCapacity")) {
0443: maxCapacity = getIntProperty(value, key);
0444:
0445: // verify that the specified value is valid
0446: if (maxCapacity <= 0) {
0447: throw StandardException.newException(
0448: SQLState.LANG_INVALID_HASH_MAX_CAPACITY,
0449: String.valueOf(maxCapacity));
0450: }
0451: } else {
0452: // No other "legal" values at this time
0453: throw StandardException.newException(
0454: SQLState.LANG_INVALID_FROM_TABLE_PROPERTY, key,
0455: "joinStrategy");
0456: }
0457: }
0458: }
0459:
0460: /** @see Optimizable#getName
0461: * @exception StandardException Thrown on error
0462: */
0463: public String getName() throws StandardException {
0464: return getExposedName();
0465: }
0466:
0467: /** @see Optimizable#getBaseTableName */
0468: public String getBaseTableName() {
0469: return "";
0470: }
0471:
0472: /** @see Optimizable#convertAbsoluteToRelativeColumnPosition */
0473: public int convertAbsoluteToRelativeColumnPosition(
0474: int absolutePosition) {
0475: return absolutePosition;
0476: }
0477:
0478: /** @see Optimizable#updateBestPlanMap */
0479: public void updateBestPlanMap(short action, Object planKey)
0480: throws StandardException {
0481: if (action == REMOVE_PLAN) {
0482: if (bestPlanMap != null) {
0483: bestPlanMap.remove(planKey);
0484: if (bestPlanMap.size() == 0)
0485: bestPlanMap = null;
0486: }
0487:
0488: return;
0489: }
0490:
0491: AccessPath bestPath = getTrulyTheBestAccessPath();
0492: AccessPathImpl ap = null;
0493: if (action == ADD_PLAN) {
0494: // If we get to this method before ever optimizing this node, then
0495: // there will be no best path--so there's nothing to do.
0496: if (bestPath == null)
0497: return;
0498:
0499: // If the bestPlanMap already exists, search for an
0500: // AccessPath for the received key and use that if we can.
0501: if (bestPlanMap == null)
0502: bestPlanMap = new HashMap();
0503: else
0504: ap = (AccessPathImpl) bestPlanMap.get(planKey);
0505:
0506: // If we don't already have an AccessPath for the key,
0507: // create a new one. If the key is an OptimizerImpl then
0508: // we might as well pass it in to the AccessPath constructor;
0509: // otherwise just pass null.
0510: if (ap == null) {
0511: if (planKey instanceof Optimizer)
0512: ap = new AccessPathImpl((Optimizer) planKey);
0513: else
0514: ap = new AccessPathImpl((Optimizer) null);
0515: }
0516:
0517: ap.copy(bestPath);
0518: bestPlanMap.put(planKey, ap);
0519: return;
0520: }
0521:
0522: // If we get here, we want to load the best plan from our map
0523: // into this Optimizable's trulyTheBestAccessPath field.
0524:
0525: // If we don't have any plans saved, then there's nothing to load.
0526: // This can happen if the key is an OptimizerImpl that tried some
0527: // join order for which there was no valid plan.
0528: if (bestPlanMap == null)
0529: return;
0530:
0531: ap = (AccessPathImpl) bestPlanMap.get(planKey);
0532:
0533: // It might be the case that there is no plan stored for
0534: // the key, in which case there's nothing to load.
0535: if ((ap == null) || (ap.getCostEstimate() == null))
0536: return;
0537:
0538: // We found a best plan in our map, so load it into this Optimizable's
0539: // trulyTheBestAccessPath field.
0540: bestPath.copy(ap);
0541: return;
0542: }
0543:
0544: /** @see Optimizable#rememberAsBest */
0545: public void rememberAsBest(int planType, Optimizer optimizer)
0546: throws StandardException {
0547: AccessPath bestPath = null;
0548:
0549: switch (planType) {
0550: case Optimizer.NORMAL_PLAN:
0551: bestPath = getBestAccessPath();
0552: break;
0553:
0554: case Optimizer.SORT_AVOIDANCE_PLAN:
0555: bestPath = getBestSortAvoidancePath();
0556: break;
0557:
0558: default:
0559: if (SanityManager.DEBUG) {
0560: SanityManager.THROWASSERT("Invalid plan type "
0561: + planType);
0562: }
0563: }
0564:
0565: getTrulyTheBestAccessPath().copy(bestPath);
0566:
0567: // Since we just set trulyTheBestAccessPath for the current
0568: // join order of the received optimizer, take note of what
0569: // that path is, in case we need to "revert" back to this
0570: // path later. See Optimizable.updateBestPlanMap().
0571: // Note: Since this call descends all the way down to base
0572: // tables, it can be relatively expensive when we have deeply
0573: // nested subqueries. So in an attempt to save some work, we
0574: // skip the call if this node is a ProjectRestrictNode whose
0575: // child is an Optimizable--in that case the ProjectRestrictNode
0576: // will in turn call "rememberAsBest" on its child and so
0577: // the required call to updateBestPlanMap() will be
0578: // made at that time. If we did it here, too, then we would
0579: // just end up duplicating the work.
0580: if (!(this instanceof ProjectRestrictNode))
0581: updateBestPlanMap(ADD_PLAN, optimizer);
0582: else {
0583: ProjectRestrictNode prn = (ProjectRestrictNode) this ;
0584: if (!(prn.getChildResult() instanceof Optimizable))
0585: updateBestPlanMap(ADD_PLAN, optimizer);
0586: }
0587:
0588: /* also store the name of the access path; i.e index name/constraint
0589: * name if we're using an index to access the base table.
0590: */
0591: ConglomerateDescriptor cd = bestPath
0592: .getConglomerateDescriptor();
0593:
0594: if (isBaseTable()) {
0595: DataDictionary dd = getDataDictionary();
0596: TableDescriptor td = getTableDescriptor();
0597: getTrulyTheBestAccessPath()
0598: .initializeAccessPathName(dd, td);
0599: }
0600:
0601: setCostEstimate(bestPath.getCostEstimate());
0602:
0603: bestPath.getOptimizer().trace(
0604: Optimizer.REMEMBERING_BEST_ACCESS_PATH, tableNumber,
0605: planType, 0.0, bestPath);
0606: }
0607:
0608: /** @see Optimizable#startOptimizing */
0609: public void startOptimizing(Optimizer optimizer,
0610: RowOrdering rowOrdering) {
0611: resetJoinStrategies(optimizer);
0612:
0613: considerSortAvoidancePath = false;
0614:
0615: /*
0616: ** If there are costs associated with the best and sort access
0617: ** paths, set them to their maximum values, so that any legitimate
0618: ** access path will look cheaper.
0619: */
0620: CostEstimate ce = getBestAccessPath().getCostEstimate();
0621:
0622: if (ce != null)
0623: ce.setCost(Double.MAX_VALUE, Double.MAX_VALUE,
0624: Double.MAX_VALUE);
0625:
0626: ce = getBestSortAvoidancePath().getCostEstimate();
0627:
0628: if (ce != null)
0629: ce.setCost(Double.MAX_VALUE, Double.MAX_VALUE,
0630: Double.MAX_VALUE);
0631:
0632: if (!canBeOrdered())
0633: rowOrdering.addUnorderedOptimizable(this );
0634: }
0635:
0636: /**
0637: * This method is called when this table is placed in a potential
0638: * join order, or when a new conglomerate is being considered.
0639: * Set this join strategy number to 0 to indicate that
0640: * no join strategy has been considered for this table yet.
0641: */
0642: protected void resetJoinStrategies(Optimizer optimizer) {
0643: joinStrategyNumber = 0;
0644: getCurrentAccessPath().setJoinStrategy((JoinStrategy) null);
0645: }
0646:
0647: /**
0648: * @see Optimizable#estimateCost
0649: *
0650: * @exception StandardException Thrown on error
0651: */
0652: public CostEstimate estimateCost(OptimizablePredicateList predList,
0653: ConglomerateDescriptor cd, CostEstimate outerCost,
0654: Optimizer optimizer, RowOrdering rowOrdering)
0655: throws StandardException {
0656: if (SanityManager.DEBUG) {
0657: SanityManager
0658: .THROWASSERT("estimateCost() not expected to be called for "
0659: + getClass().toString());
0660: }
0661:
0662: return null;
0663: }
0664:
0665: /**
0666: * Get the final CostEstimate for this FromTable.
0667: *
0668: * @return The final CostEstimate for this FromTable, which is
0669: * the costEstimate of trulyTheBestAccessPath if there is one.
0670: * If there's no trulyTheBestAccessPath for this node, then
0671: * we just return the value stored in costEstimate as a default.
0672: */
0673: public CostEstimate getFinalCostEstimate() throws StandardException {
0674: // If we already found it, just return it.
0675: if (finalCostEstimate != null)
0676: return finalCostEstimate;
0677:
0678: if (getTrulyTheBestAccessPath() == null)
0679: finalCostEstimate = costEstimate;
0680: else
0681: finalCostEstimate = getTrulyTheBestAccessPath()
0682: .getCostEstimate();
0683:
0684: return finalCostEstimate;
0685: }
0686:
0687: /** @see Optimizable#isBaseTable */
0688: public boolean isBaseTable() {
0689: return false;
0690: }
0691:
0692: /** @see Optimizable#isMaterializable
0693: *
0694: * @exception StandardException Thrown on error
0695: */
0696: public boolean isMaterializable() throws StandardException {
0697: /* Derived tables are materializable
0698: * iff they are not correlated with an outer query block.
0699: */
0700:
0701: HasCorrelatedCRsVisitor visitor = new HasCorrelatedCRsVisitor();
0702: accept(visitor);
0703: return !(visitor.hasCorrelatedCRs());
0704: }
0705:
0706: /** @see Optimizable#supportsMultipleInstantiations */
0707: public boolean supportsMultipleInstantiations() {
0708: return true;
0709: }
0710:
0711: /** @see Optimizable#getTableNumber */
0712: public int getTableNumber() {
0713: return tableNumber;
0714: }
0715:
0716: /** @see Optimizable#hasTableNumber */
0717: public boolean hasTableNumber() {
0718: return tableNumber >= 0;
0719: }
0720:
0721: /** @see Optimizable#forUpdate */
0722: public boolean forUpdate() {
0723: return false;
0724: }
0725:
0726: /** @see Optimizable#initialCapacity */
0727: public int initialCapacity() {
0728: if (SanityManager.DEBUG) {
0729: SanityManager.THROWASSERT("Not expected to be called");
0730: }
0731:
0732: return 0;
0733: }
0734:
0735: /** @see Optimizable#loadFactor */
0736: public float loadFactor() {
0737: if (SanityManager.DEBUG) {
0738: SanityManager.THROWASSERT("Not expected to be called");
0739: }
0740:
0741: return 0.0F;
0742: }
0743:
0744: /** @see Optimizable#maxCapacity */
0745: public int maxCapacity(JoinStrategy joinStrategy,
0746: int maxMemoryPerTable) throws StandardException {
0747: return joinStrategy.maxCapacity(maxCapacity, maxMemoryPerTable,
0748: getPerRowUsage());
0749: }
0750:
0751: private double getPerRowUsage() throws StandardException {
0752: if (perRowUsage < 0) {
0753: // Do not use getRefCols() because the cached refCols may no longer be valid.
0754: FormatableBitSet refCols = resultColumns
0755: .getReferencedFormatableBitSet(cursorTargetTable(),
0756: true, false);
0757: perRowUsage = 0.0;
0758:
0759: /* Add up the memory usage for each referenced column */
0760: for (int i = 0; i < refCols.size(); i++) {
0761: if (refCols.isSet(i)) {
0762: ResultColumn rc = (ResultColumn) resultColumns
0763: .elementAt(i);
0764: DataTypeDescriptor expressionType = rc
0765: .getExpressionType();
0766: if (expressionType != null)
0767: perRowUsage += expressionType
0768: .estimatedMemoryUsage();
0769: }
0770: }
0771:
0772: /*
0773: ** If the proposed conglomerate is a non-covering index, add the
0774: ** size of the RowLocation column to the total.
0775: **
0776: ** NOTE: We don't have a DataTypeDescriptor representing a
0777: ** REF column here, so just add a constant here.
0778: */
0779: ConglomerateDescriptor cd = getCurrentAccessPath()
0780: .getConglomerateDescriptor();
0781: if (cd != null) {
0782: if (cd.isIndex() && (!isCoveringIndex(cd))) {
0783: // workaround for a jikes bug. Can't directly reference a
0784: // double with a value of 12.0 in this classfile.
0785: double baseIndexUsage = 1.0;
0786: perRowUsage += (baseIndexUsage + 11);
0787: }
0788: }
0789: }
0790: return perRowUsage;
0791: } // end of getPerRowUsage
0792:
0793: /** @see Optimizable#hashKeyColumns */
0794: public int[] hashKeyColumns() {
0795: if (SanityManager.DEBUG) {
0796: SanityManager.ASSERT(hashKeyColumns != null,
0797: "hashKeyColumns expected to be non-null");
0798: }
0799:
0800: return hashKeyColumns;
0801: }
0802:
0803: /** @see Optimizable#setHashKeyColumns */
0804: public void setHashKeyColumns(int[] columnNumbers) {
0805: hashKeyColumns = columnNumbers;
0806: }
0807:
0808: /**
0809: * @see Optimizable#feasibleJoinStrategy
0810: *
0811: * @exception StandardException Thrown on error
0812: */
0813: public boolean feasibleJoinStrategy(
0814: OptimizablePredicateList predList, Optimizer optimizer)
0815: throws StandardException {
0816: return getCurrentAccessPath().getJoinStrategy().feasible(this ,
0817: predList, optimizer);
0818: }
0819:
0820: /** @see Optimizable#memoryUsageOK */
0821: public boolean memoryUsageOK(double rowCount, int maxMemoryPerTable)
0822: throws StandardException {
0823: /*
0824: ** Don't enforce maximum memory usage for a user-specified join
0825: ** strategy.
0826: */
0827: if (userSpecifiedJoinStrategy != null)
0828: return true;
0829:
0830: int intRowCount = (rowCount > Integer.MAX_VALUE) ? Integer.MAX_VALUE
0831: : (int) rowCount;
0832: return intRowCount <= maxCapacity(getCurrentAccessPath()
0833: .getJoinStrategy(), maxMemoryPerTable);
0834: }
0835:
0836: /**
0837: * @see Optimizable#legalJoinOrder
0838: */
0839: public boolean legalJoinOrder(JBitSet assignedTableMap) {
0840: // Only those subclasses with dependencies need to override this.
0841: return true;
0842: }
0843:
0844: /**
0845: * @see Optimizable#getNumColumnsReturned
0846: */
0847: public int getNumColumnsReturned() {
0848: return resultColumns.size();
0849: }
0850:
0851: /**
0852: * @see Optimizable#isTargetTable
0853: */
0854: public boolean isTargetTable() {
0855: return false;
0856: }
0857:
0858: /**
0859: * @see Optimizable#isOneRowScan
0860: *
0861: * @exception StandardException Thrown on error
0862: */
0863: public boolean isOneRowScan() throws StandardException {
0864: /* We simply return isOneRowResultSet() for all
0865: * subclasses except for EXISTS FBT where
0866: * the semantics differ between 1 row per probe
0867: * and whether or not there can be more than 1
0868: * rows that qualify on a scan.
0869: */
0870: return isOneRowResultSet();
0871: }
0872:
0873: /**
0874: * @see Optimizable#initAccessPaths
0875: */
0876: public void initAccessPaths(Optimizer optimizer) {
0877: if (currentAccessPath == null) {
0878: currentAccessPath = new AccessPathImpl(optimizer);
0879: }
0880: if (bestAccessPath == null) {
0881: bestAccessPath = new AccessPathImpl(optimizer);
0882: }
0883: if (bestSortAvoidancePath == null) {
0884: bestSortAvoidancePath = new AccessPathImpl(optimizer);
0885: }
0886: if (trulyTheBestAccessPath == null) {
0887: trulyTheBestAccessPath = new AccessPathImpl(optimizer);
0888: }
0889: }
0890:
0891: /**
0892: * @see Optimizable#uniqueJoin
0893: *
0894: * @exception StandardException Thrown on error
0895: */
0896: public double uniqueJoin(OptimizablePredicateList predList)
0897: throws StandardException {
0898: return -1.0;
0899: }
0900:
0901: private FormatableBitSet getRefCols() {
0902: if (refCols == null)
0903: refCols = resultColumns.getReferencedFormatableBitSet(
0904: cursorTargetTable(), true, false);
0905:
0906: return refCols;
0907: }
0908:
0909: /**
0910: * Return the user specified join strategy, if any for this table.
0911: *
0912: * @return The user specified join strategy, if any for this table.
0913: */
0914: String getUserSpecifiedJoinStrategy() {
0915: if (tableProperties == null) {
0916: return null;
0917: }
0918:
0919: return tableProperties.getProperty("joinStrategy");
0920: }
0921:
0922: /**
0923: * Is this a table that has a FOR UPDATE
0924: * clause. Overridden by FromBaseTable.
0925: *
0926: * @return true/false
0927: */
0928: protected boolean cursorTargetTable() {
0929: return false;
0930: }
0931:
0932: protected CostEstimate getCostEstimate(Optimizer optimizer) {
0933: if (costEstimate == null) {
0934: costEstimate = optimizer.newCostEstimate();
0935: }
0936: return costEstimate;
0937: }
0938:
0939: /*
0940: ** This gets a cost estimate for doing scratch calculations. Typically,
0941: ** it will hold the estimated cost of a conglomerate. If the optimizer
0942: ** decides the scratch cost is lower than the best cost estimate so far,
0943: ** it will copy the scratch cost to the non-scratch cost estimate,
0944: ** which is allocated above.
0945: */
0946: protected CostEstimate getScratchCostEstimate(Optimizer optimizer) {
0947: if (scratchCostEstimate == null) {
0948: scratchCostEstimate = optimizer.newCostEstimate();
0949: }
0950:
0951: return scratchCostEstimate;
0952: }
0953:
0954: /**
0955: * Set the cost estimate in this node to the given cost estimate.
0956: */
0957: protected void setCostEstimate(CostEstimate newCostEstimate) {
0958: costEstimate = getCostEstimate();
0959:
0960: costEstimate.setCost(newCostEstimate);
0961: }
0962:
0963: /**
0964: * Assign the cost estimate in this node to the given cost estimate.
0965: */
0966: protected void assignCostEstimate(CostEstimate newCostEstimate) {
0967: costEstimate = newCostEstimate;
0968: }
0969:
0970: /**
0971: * Convert this object to a String. See comments in QueryTreeNode.java
0972: * for how this should be done for tree printing.
0973: *
0974: * @return This object as a String
0975: */
0976:
0977: public String toString() {
0978: if (SanityManager.DEBUG) {
0979: return "correlation Name: "
0980: + correlationName
0981: + "\n"
0982: + (corrTableName != null ? corrTableName.toString()
0983: : "null") + "\n" + "tableNumber "
0984: + tableNumber + "\n" + "level " + level + "\n"
0985: + super .toString();
0986: } else {
0987: return "";
0988: }
0989: }
0990:
0991: /**
0992: * Return a ResultColumnList with all of the columns in this table.
0993: * (Used in expanding '*'s.)
0994: * NOTE: Since this method is for expanding a "*" in the SELECT list,
0995: * ResultColumn.expression will be a ColumnReference.
0996: *
0997: * @param allTableName The qualifier on the "*"
0998: *
0999: * @return ResultColumnList List of result columns from this table.
1000: *
1001: * @exception StandardException Thrown on error
1002: */
1003: public ResultColumnList getResultColumnsForList(
1004: TableName allTableName, ResultColumnList inputRcl,
1005: TableName tableName) throws StandardException {
1006: ResultColumnList rcList = null;
1007: ResultColumn resultColumn;
1008: ValueNode valueNode;
1009: String columnName;
1010: TableName exposedName;
1011: TableName toCompare;
1012:
1013: /* If allTableName is non-null, then we must check to see if it matches
1014: * our exposed name.
1015: */
1016:
1017: if (correlationName == null)
1018: toCompare = tableName;
1019: else {
1020: if (allTableName != null)
1021: toCompare = makeTableName(allTableName.getSchemaName(),
1022: correlationName);
1023: else
1024: toCompare = makeTableName(null, correlationName);
1025: }
1026:
1027: if (allTableName != null && !allTableName.equals(toCompare)) {
1028: return null;
1029: }
1030:
1031: /* Cache exposed name for this table.
1032: * The exposed name becomes the qualifier for each column
1033: * in the expanded list.
1034: */
1035: if (correlationName == null) {
1036: exposedName = tableName;
1037: } else {
1038: exposedName = makeTableName(null, correlationName);
1039: }
1040:
1041: rcList = (ResultColumnList) getNodeFactory().getNode(
1042: C_NodeTypes.RESULT_COLUMN_LIST, getContextManager());
1043:
1044: /* Build a new result column list based off of resultColumns.
1045: * NOTE: This method will capture any column renaming due to
1046: * a derived column list.
1047: */
1048: int inputSize = inputRcl.size();
1049: for (int index = 0; index < inputSize; index++) {
1050: // Build a ResultColumn/ColumnReference pair for the column //
1051: columnName = ((ResultColumn) inputRcl.elementAt(index))
1052: .getName();
1053: valueNode = (ValueNode) getNodeFactory().getNode(
1054: C_NodeTypes.COLUMN_REFERENCE, columnName,
1055: exposedName, getContextManager());
1056: resultColumn = (ResultColumn) getNodeFactory().getNode(
1057: C_NodeTypes.RESULT_COLUMN, columnName, valueNode,
1058: getContextManager());
1059:
1060: // Build the ResultColumnList to return //
1061: rcList.addResultColumn(resultColumn);
1062: }
1063: return rcList;
1064: }
1065:
1066: /**
1067: * Push expressions down to the first ResultSetNode which can do expression
1068: * evaluation and has the same referenced table map.
1069: * RESOLVE - This means only pushing down single table expressions to
1070: * ProjectRestrictNodes today. Once we have a better understanding of how
1071: * the optimizer will work, we can push down join clauses.
1072: *
1073: * @param predicateList The PredicateList.
1074: *
1075: * @exception StandardException Thrown on error
1076: */
1077: void pushExpressions(PredicateList predicateList)
1078: throws StandardException {
1079: if (SanityManager.DEBUG) {
1080: SanityManager.ASSERT(predicateList != null,
1081: "predicateList is expected to be non-null");
1082: }
1083: }
1084:
1085: /**
1086: * Get the exposed name for this table, which is the name that can
1087: * be used to refer to it in the rest of the query.
1088: *
1089: * @return The exposed name of this table.
1090: *
1091: * @exception StandardException Thrown on error
1092: */
1093: public String getExposedName() throws StandardException {
1094: if (SanityManager.DEBUG)
1095: SanityManager
1096: .THROWASSERT("getExposedName() not expected to be called for "
1097: + this .getClass().getName());
1098: return null;
1099: }
1100:
1101: /**
1102: * Set the table # for this table.
1103: *
1104: * @param tableNumber The table # for this table.
1105: */
1106: public void setTableNumber(int tableNumber) {
1107: /* This should only be called if the tableNumber has not been set yet */
1108: if (SanityManager.DEBUG)
1109: SanityManager.ASSERT(this .tableNumber == -1,
1110: "tableNumber is not expected to be already set");
1111: this .tableNumber = tableNumber;
1112: }
1113:
1114: /**
1115: * Return a TableName node representing this FromTable.
1116: * Expect this to be overridden (and used) by subclasses
1117: * that may set correlationName to null.
1118: *
1119: * @return a TableName node representing this FromTable.
1120: * @exception StandardException Thrown on error
1121: */
1122: public TableName getTableName() throws StandardException {
1123: if (correlationName == null)
1124: return null;
1125:
1126: if (corrTableName == null) {
1127: corrTableName = makeTableName(null, correlationName);
1128: }
1129:
1130: return corrTableName;
1131: }
1132:
1133: /**
1134: * Set the (query block) level (0-based) for this FromTable.
1135: *
1136: * @param level The query block level for this FromTable.
1137: */
1138: public void setLevel(int level) {
1139: this .level = level;
1140: }
1141:
1142: /**
1143: * Get the (query block) level (0-based) for this FromTable.
1144: *
1145: * @return int The query block level for this FromTable.
1146: */
1147: public int getLevel() {
1148: return level;
1149: }
1150:
1151: /**
1152: * Decrement (query block) level (0-based) for this FromTable.
1153: * This is useful when flattening a subquery.
1154: *
1155: * @param decrement The amount to decrement by.
1156: */
1157: void decrementLevel(int decrement) {
1158: if (SanityManager.DEBUG) {
1159: /* NOTE: level doesn't get propagated
1160: * to nodes generated after binding.
1161: */
1162: if (level < decrement && level != 0) {
1163: SanityManager.THROWASSERT("level (" + level
1164: + ") expected to be >= decrement (" + decrement
1165: + ")");
1166: }
1167: }
1168: /* NOTE: level doesn't get propagated
1169: * to nodes generated after binding.
1170: */
1171: if (level > 0) {
1172: level -= decrement;
1173: }
1174: }
1175:
1176: /**
1177: * Get a schema descriptor for the given table.
1178: * Uses this.corrTableName.
1179: *
1180: * @return Schema Descriptor
1181: *
1182: * @exception StandardException throws on schema name
1183: * that doesn't exist
1184: */
1185: public SchemaDescriptor getSchemaDescriptor()
1186: throws StandardException {
1187: return getSchemaDescriptor(corrTableName);
1188: }
1189:
1190: /**
1191: * Get a schema descriptor for the given table.
1192: *
1193: * @param tableName the table name
1194: *
1195: * @return Schema Descriptor
1196: *
1197: * @exception StandardException throws on schema name
1198: * that doesn't exist
1199: */
1200: public SchemaDescriptor getSchemaDescriptor(TableName tableName)
1201: throws StandardException {
1202: SchemaDescriptor sd;
1203:
1204: sd = getSchemaDescriptor(tableName.getSchemaName());
1205:
1206: return sd;
1207: }
1208:
1209: /**
1210: * Determine whether or not the specified name is an exposed name in
1211: * the current query block.
1212: *
1213: * @param name The specified name to search for as an exposed name.
1214: * @param schemaName Schema name, if non-null.
1215: * @param exactMatch Whether or not we need an exact match on specified schema and table
1216: * names or match on table id.
1217: *
1218: * @return The FromTable, if any, with the exposed name.
1219: *
1220: * @exception StandardException Thrown on error
1221: */
1222: protected FromTable getFromTableByName(String name,
1223: String schemaName, boolean exactMatch)
1224: throws StandardException {
1225: // Only FromBaseTables have schema names
1226: if (schemaName != null) {
1227: return null;
1228: }
1229:
1230: if (getExposedName().equals(name)) {
1231: return this ;
1232: }
1233: return null;
1234: }
1235:
1236: /**
1237: * Is this FromTable a JoinNode which can be flattened into
1238: * the parents FromList.
1239: *
1240: * @return boolean Whether or not this FromTable can be flattened.
1241: */
1242: public boolean isFlattenableJoinNode() {
1243: return false;
1244: }
1245:
1246: /**
1247: * no LOJ reordering for this FromTable.
1248: */
1249: public boolean LOJ_reorderable(int numTables)
1250: throws StandardException {
1251: return false;
1252: }
1253:
1254: /**
1255: * Transform any Outer Join into an Inner Join where applicable.
1256: * (Based on the existence of a null intolerant
1257: * predicate on the inner table.)
1258: *
1259: * @param predicateTree The predicate tree for the query block
1260: *
1261: * @return The new tree top (OuterJoin or InnerJoin).
1262: *
1263: * @exception StandardException Thrown on error
1264: */
1265: public FromTable transformOuterJoins(ValueNode predicateTree,
1266: int numTables) throws StandardException {
1267: return this ;
1268: }
1269:
1270: /**
1271: * Fill the referencedTableMap with this ResultSetNode.
1272: *
1273: * @param passedMap The table map to fill in.
1274: */
1275: public void fillInReferencedTableMap(JBitSet passedMap) {
1276: if (tableNumber != -1) {
1277: passedMap.set(tableNumber);
1278: }
1279: }
1280:
1281: /**
1282: * Mark as updatable all the columns in the result column list of this
1283: * FromBaseTable that match the columns in the given update column list.
1284: * If the list is null, it means all the columns are updatable.
1285: *
1286: * @param updateColumns A Vector representing the columns
1287: * that can be updated.
1288: */
1289: protected void markUpdatableByCursor(Vector updateColumns) {
1290: resultColumns.markUpdatableByCursor(updateColumns);
1291: }
1292:
1293: /**
1294: * Flatten this FromTable into the outer query block. The steps in
1295: * flattening are:
1296: * o Mark all ResultColumns as redundant, so that they are "skipped over"
1297: * at generate().
1298: * o Append the wherePredicates to the outer list.
1299: * o Return the fromList so that the caller will merge the 2 lists
1300: *
1301: * @param rcl The RCL from the outer query
1302: * @param outerPList PredicateList to append wherePredicates to.
1303: * @param sql The SubqueryList from the outer query
1304: * @param gbl The group by list, if any
1305: *
1306: * @return FromList The fromList from the underlying SelectNode.
1307: *
1308: * @exception StandardException Thrown on error
1309: */
1310: public FromList flatten(ResultColumnList rcl,
1311: PredicateList outerPList, SubqueryList sql, GroupByList gbl)
1312:
1313: throws StandardException {
1314: if (SanityManager.DEBUG) {
1315: SanityManager
1316: .THROWASSERT("flatten() not expected to be called for "
1317: + this );
1318: }
1319: return null;
1320: }
1321:
1322: /**
1323: * Optimize any subqueries that haven't been optimized any where
1324: * else. This is useful for a RowResultSetNode as a derived table
1325: * because it doesn't get optimized otherwise.
1326: *
1327: * @exception StandardException Thrown on error
1328: */
1329: void optimizeSubqueries(DataDictionary dd, double rowCount)
1330: throws StandardException {
1331: }
1332:
1333: /**
1334: * Tell the given RowOrdering about any columns that are constant
1335: * due to their being equality comparisons with constant expressions.
1336: */
1337: protected void tellRowOrderingAboutConstantColumns(
1338: RowOrdering rowOrdering, OptimizablePredicateList predList) {
1339: /*
1340: ** Tell the RowOrdering about columns that are equal to constant
1341: ** expressions.
1342: */
1343: if (predList != null) {
1344: for (int i = 0; i < predList.size(); i++) {
1345: Predicate pred = (Predicate) predList
1346: .getOptPredicate(i);
1347:
1348: /* Is it an = comparison with a constant expression? */
1349: if (pred.equalsComparisonWithConstantExpression(this )) {
1350: /* Get the column being compared to the constant */
1351: ColumnReference cr = pred.getRelop()
1352: .getColumnOperand(this );
1353:
1354: if (cr != null) {
1355: /* Tell RowOrdering that the column is always ordered */
1356: rowOrdering.columnAlwaysOrdered(this , cr
1357: .getColumnNumber());
1358: }
1359: }
1360: }
1361: }
1362:
1363: }
1364:
1365: public boolean needsSpecialRCLBinding() {
1366: return false;
1367: }
1368:
1369: /**
1370: * Sets the original or unbound table name for this FromTable.
1371: *
1372: * @param tableName the unbound table name
1373: *
1374: */
1375: public void setOrigTableName(TableName tableName) {
1376: this .origTableName = tableName;
1377: }
1378:
1379: /**
1380: * Gets the original or unbound table name for this FromTable.
1381: * The tableName field can be changed due to synonym resolution.
1382: * Use this method to retrieve the actual unbound tablename.
1383: *
1384: * @return TableName the original or unbound tablename
1385: *
1386: */
1387: public TableName getOrigTableName() {
1388: return this.origTableName;
1389: }
1390: }
|