0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.sql.compile.SetOperatorNode
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.AccessPath;
0029: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
0030: import org.apache.derby.iapi.sql.compile.CostEstimate;
0031: import org.apache.derby.iapi.sql.compile.Optimizable;
0032: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
0033: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
0034:
0035: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
0036: import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
0037:
0038: import org.apache.derby.iapi.reference.SQLState;
0039: import org.apache.derby.iapi.types.DataTypeDescriptor;
0040:
0041: import org.apache.derby.iapi.util.JBitSet;
0042:
0043: import java.util.HashMap;
0044:
0045: /**
0046: * A SetOperatorNode represents a UNION, INTERSECT, or EXCEPT in a DML statement. Binding and optimization
0047: * preprocessing is the same for all of these operations, so they share bind methods in this abstract class.
0048: *
0049: * The class contains a boolean telling whether the operation should eliminate
0050: * duplicate rows.
0051: *
0052: * @author Jeff Lichtman
0053: */
0054:
0055: abstract class SetOperatorNode extends TableOperatorNode {
0056: /**
0057: ** Tells whether to eliminate duplicate rows. all == TRUE means do
0058: ** not eliminate duplicates, all == FALSE means eliminate duplicates.
0059: */
0060: boolean all;
0061:
0062: OrderByList orderByList;
0063:
0064: // List of scoped predicates for pushing during optimization.
0065: private PredicateList leftOptPredicates;
0066: private PredicateList rightOptPredicates;
0067:
0068: // List of original (unscoped) predicates that we tried to push
0069: // during the most recent phase of optimization.
0070: private PredicateList pushedPredicates;
0071:
0072: // Mapping of original predicates to scoped predicates, used to
0073: // avoid re-scoping predicates unnecessarily.
0074: private HashMap leftScopedPreds;
0075: private HashMap rightScopedPreds;
0076:
0077: /**
0078: * Initializer for a SetOperatorNode.
0079: *
0080: * @param leftResult The ResultSetNode on the left side of this union
0081: * @param rightResult The ResultSetNode on the right side of this union
0082: * @param all Whether or not this is an ALL.
0083: * @param tableProperties Properties list associated with the table
0084: *
0085: * @exception StandardException Thrown on error
0086: */
0087:
0088: public void init(Object leftResult, Object rightResult, Object all,
0089: Object tableProperties) throws StandardException {
0090: super .init(leftResult, rightResult, tableProperties);
0091:
0092: this .all = ((Boolean) all).booleanValue();
0093:
0094: /* resultColumns cannot be null, so we make a copy of the left RCL
0095: * for now. At bind() time, we need to recopy the list because there
0096: * may have been a "*" in the list. (We will set the names and
0097: * column types at that time, as expected.)
0098: */
0099: resultColumns = leftResultSet.getResultColumns()
0100: .copyListAndObjects();
0101: }
0102:
0103: /**
0104: * @see Optimizable#modifyAccessPath
0105: *
0106: * @exception StandardException Thrown on error
0107: */
0108: public Optimizable modifyAccessPath(JBitSet outerTables,
0109: PredicateList predList) throws StandardException {
0110: // When we optimized this node we attempted to push predicates down to
0111: // the children, which means the best access path for the children
0112: // might depend on those predicates. So now that we're preparing
0113: // to generate the best paths, we have to push those same predicates
0114: // down again (this is the last time) so that the children can use
0115: // them as appropriate. NOTE: If our final choice for join strategy
0116: // is a hash join, then we do not push the predicates because we'll
0117: // need them to be at this level in order to find out which of them
0118: // is the equijoin predicate that is required by hash join.
0119: if ((predList != null)
0120: && !getTrulyTheBestAccessPath().getJoinStrategy()
0121: .isHashJoin()) {
0122: for (int i = predList.size() - 1; i >= 0; i--)
0123: if (pushOptPredicate(predList.getOptPredicate(i)))
0124: predList.removeOptPredicate(i);
0125: }
0126:
0127: /*
0128: * It's possible that we tried to push a predicate down to this node's
0129: * children but failed to do so. This can happen if this node's
0130: * children both match the criteria for pushing a predicate (namely,
0131: * they reference base tables) but the children's children do not.
0132: * Ex.
0133: * select * from
0134: * (select i,j from t2 UNION
0135: * values (1,1),(2,2),(3,3),(4,4) UNION
0136: * select i,j from t1
0137: * ) x0 (i,j),
0138: * t5 where x0.i = t5.i;
0139: *
0140: * This will yield a tree resembling the following:
0141: *
0142: * UNION
0143: * / \
0144: * UNION SELECT (T1)
0145: * / \
0146: * SELECT (T2) VALUES
0147: *
0148: * In this case the top UNION ("this") will push the predicate down,
0149: * but the second UNION will _not_ push the predicate because
0150: * it can't be pushed to the VALUES clause. This means that
0151: * after we're done modifying the paths for "this" node (the top
0152: * UNION), the predicate will still be sitting in our leftOptPredicates
0153: * list. If that's the case, then we have to make sure the predicate,
0154: * which was _not_ enforced in the left child, is enforced at this
0155: * level. We do that by generating a ProjectRestrictNode above this
0156: * node. Yes, this means the predicate will actually be applied
0157: * twice to the right child (in this case), but that's okay as it
0158: * won't affect the results.
0159: */
0160:
0161: // Get the cost estimate for this node so that we can put it in
0162: // the new ProjectRestrictNode, if one is needed.
0163: CostEstimate ce = getFinalCostEstimate();
0164:
0165: // Modify this node's access paths.
0166: ResultSetNode topNode = (ResultSetNode) modifyAccessPath(outerTables);
0167:
0168: /* Now see if there are any left over predicates; if so, then we
0169: * have to generate a ProjectRestrictNode. Note: we walk the
0170: * entire chain of UnionNodes (if there is a chain) and see if
0171: * any UnionNode at any level has un-pushed predicates; if so, then
0172: * we use a PRN to enforce the predicate at this, the top-most
0173: * UnionNode.
0174: */
0175: if (hasUnPushedPredicates()) {
0176: // When we generate the project restrict node, we pass in the
0177: // "pushedPredicates" list because that has the predicates in
0178: // _unscoped_ form, which means they are intended for _this_
0179: // node instead of this node's children. That's exactly what
0180: // we want.
0181: ResultSetNode prnRSN = (ResultSetNode) getNodeFactory()
0182: .getNode(C_NodeTypes.PROJECT_RESTRICT_NODE,
0183: topNode, // Child ResultSet
0184: topNode.getResultColumns(), // Projection
0185: null, // Restriction
0186: pushedPredicates, // Restriction as PredicateList
0187: null, // Subquerys in Projection
0188: null, // Subquerys in Restriction
0189: null, // Table properties
0190: getContextManager());
0191: prnRSN.costEstimate = ce.cloneMe();
0192: prnRSN.setReferencedTableMap(topNode
0193: .getReferencedTableMap());
0194: topNode = prnRSN;
0195: }
0196:
0197: return (Optimizable) topNode;
0198: }
0199:
0200: /**
0201: * @see org.apache.derby.iapi.sql.compile.Optimizable#pushOptPredicate
0202: *
0203: * Take a predicate and push it down to both the left AND right result
0204: * sets. Return "true" if we successfully pushed it to both sides,
0205: * and "false" otherwise. The assumption is that if we return "true",
0206: * the caller will take the predicate and remove it from its own list
0207: * of predicates to evaluate; if we return false, then the predicate
0208: * will be evaluated at the level of the caller. So returning "false"
0209: * means that the left and right result sets for this node will be fully
0210: * returned, and then the predicate will be evaluated against the
0211: * <set-operator> of those result sets (as of DERBY-805, the only set
0212: * operator calling this method is UnionNode). If we can push the
0213: * predicate down to both children, though, we can evaluate it closer
0214: * to store, which means that each child result set returns only the
0215: * correctly qualified rows, and thus the calling set operator will
0216: * have a smaller result set on which to operate, which can boost
0217: * performance.
0218: *
0219: * That said, if we can't push the predicate to _both_ sides, we don't
0220: * push it at all. The reason is that if we push to one side but not
0221: * to the other, we would have to ask the question of whether we should
0222: * return "true" (meaning that the predicate would be removed from the
0223: * caller's list and thus would _not_ be evaluated at the <set-operator>
0224: * level) or "false" (meaning that the caller would keep the predicate
0225: * and evaluate it at the <set-operator> level). Depending on the query
0226: * in question, both answers could end up returning incorrect results.
0227: *
0228: * For example, if we push it to the right but not to the left, then
0229: * leave it in the caller's list, the optimizer for the caller might
0230: * decide to use the predicate to do a hash join with some outer result
0231: * set (if the predicate is an equijoin predicate). That would result
0232: * in materialization of the calling node and of its children--but since
0233: * we pushed a predicate that depends on the outer table down into the
0234: * right child, materialization of the right child will only return the
0235: * rows that join with the _first_ row of the outer result set, which
0236: * is wrong.
0237: *
0238: * If, on the other hand, we push the predicate to one side and then tell
0239: * the caller to remove it from its list, the side to which we did _not_
0240: * push the predicate could return rows that aren't qualified. Then,
0241: * since the caller removed the predicate from its list, it (the caller)
0242: * will not evaluate the predicate on its own result set--and thus we
0243: * can end up returning rows that we weren't supposed to return.
0244: *
0245: * So all of that said, only push (and return "true") if we think we
0246: * can push the predicate to both sides.
0247: *
0248: * @exception StandardException Thrown on error
0249: */
0250: public boolean pushOptPredicate(
0251: OptimizablePredicate optimizablePredicate)
0252: throws StandardException {
0253: // This method was added to SetOperatorNode as part of DERBY-805,
0254: // which was only targeted for UnionNodes. So for now, we don't
0255: // do anything if "this" isn't a Union. This check can be removed
0256: // when support for other SetOperators is added.
0257: if (!(this instanceof UnionNode))
0258: return false;
0259:
0260: // We only handle certain types of predicates here; if the received
0261: // predicate doesn't qualify, then don't push it.
0262: Predicate pred = (Predicate) optimizablePredicate;
0263: if (!pred.pushableToSubqueries())
0264: return false;
0265:
0266: // Check to see if the child nodes reference any base tables; if either
0267: // child does not reference at least one base table, then we don't try
0268: // to push the predicate.
0269: boolean canPush = false;
0270:
0271: JBitSet tableNums = new JBitSet(getReferencedTableMap().size());
0272: BaseTableNumbersVisitor btnVis = new BaseTableNumbersVisitor(
0273: tableNums);
0274:
0275: // Check the left child.
0276: leftResultSet.accept(btnVis);
0277: canPush = (tableNums.getFirstSetBit() != -1);
0278:
0279: /* If we can't push it to _both_ children, then we don't push at all.
0280: * RESOLVE: We can add the ability to push a predicate to one side
0281: * only by putting a ProjectRestrictNode between the union node and
0282: * the child as a place to park the predicate. To make things simple,
0283: * we might want to always put ProjectRestrictNodes under both sides
0284: * of the union during preprocessing (i.e. after binding but before
0285: * optimization). In some cases the extra nodes won't be needed, but
0286: * PRNs (and the corresponding ProjectRestrictResultSets) are cheap.
0287: * Also, we could eliminate unnecessary ProjectRestrictNodes at the
0288: * end of optimization (possibly in modifyAccessPaths()). Until all
0289: * of that is implemented, though, we only push if we can push to
0290: * both sides...
0291: */
0292: if (!canPush)
0293: return false;
0294:
0295: // Check the right child.
0296: tableNums.clearAll();
0297: rightResultSet.accept(btnVis);
0298: canPush = (tableNums.getFirstSetBit() != -1);
0299: if (!canPush)
0300: return false;
0301:
0302: // Get a list of all of the underlying base tables that this node
0303: // references. We pass this down when scoping so that we can tell
0304: // if the operands are actually supposed to be scoped to _this_
0305: // node's children. Note that in order for the predicate to
0306: // have been pushed this far, at least one of its operands must
0307: // apply to this node--we don't know which one it is, though,
0308: // so we use this tableNums info to figure that out.
0309: tableNums.clearAll();
0310: this .accept(btnVis);
0311:
0312: /* What we want to do here is push the predicate to the left/right
0313: * child. That means that we need to find the equivalent column(s)
0314: * in each child.
0315: * Ex:
0316: *
0317: * select * from
0318: * (select i,j from t1 union select i,j from t2) X1,
0319: * (select a,b from t3 union select a,b from t4) X2
0320: * where X1.j = X2.b;
0321: *
0322: * In this example, X1.j maps to "t1" for the left side of the
0323: * union (X1) and "t2" for the right side of the union. So we have
0324: * to get versions of the predicate that are appropriate to each
0325: * side. That's what the call to getPredScopedForResultSet()
0326: * in the following code does.
0327: */
0328:
0329: // For details on how this whichRC variable is used, see the
0330: // comments in BinaryRelationalOperatorNode.getScopedOperand().
0331: int[] whichRC = new int[] { -1 };
0332:
0333: // See if we already have a scoped version of the predicate cached,
0334: // and if so just use that.
0335: Predicate scopedPred = null;
0336: if (leftScopedPreds == null)
0337: leftScopedPreds = new HashMap();
0338: else
0339: scopedPred = (Predicate) leftScopedPreds.get(pred);
0340: if (scopedPred == null) {
0341: scopedPred = pred.getPredScopedForResultSet(tableNums,
0342: leftResultSet, whichRC);
0343: leftScopedPreds.put(pred, scopedPred);
0344: }
0345:
0346: // Add the scoped predicate to our list for the left child.
0347: getLeftOptPredicateList().addOptPredicate(scopedPred);
0348:
0349: scopedPred = null;
0350: if (rightScopedPreds == null)
0351: rightScopedPreds = new HashMap();
0352: else
0353: scopedPred = (Predicate) rightScopedPreds.get(pred);
0354: if (scopedPred == null) {
0355: scopedPred = pred.getPredScopedForResultSet(tableNums,
0356: rightResultSet, whichRC);
0357: rightScopedPreds.put(pred, scopedPred);
0358: }
0359:
0360: // Add the scoped predicate to our list for the right child.
0361: getRightOptPredicateList().addOptPredicate(scopedPred);
0362:
0363: // Add the predicate (in its original form) to our list of predicates
0364: // that we've pushed during this phase of optimization. We need to
0365: // keep this list of pushed predicates around so that we can do
0366: // a "pull" of them later, if needed. We also need this list for
0367: // cases where predicates are not pushed all the way down; see
0368: // modifyAccessPaths() in this class for more.
0369: if (pushedPredicates == null)
0370: pushedPredicates = new PredicateList();
0371:
0372: pushedPredicates.addOptPredicate(pred);
0373: return true;
0374: }
0375:
0376: /**
0377: * @see Optimizable#pullOptPredicates
0378: *
0379: * @exception StandardException Thrown on error
0380: */
0381: public void pullOptPredicates(
0382: OptimizablePredicateList optimizablePredicates)
0383: throws StandardException {
0384: if (pushedPredicates == null)
0385: // we didn't push anything, so nothing to pull.
0386: return;
0387:
0388: // It's possible that we tried to push a predicate down to this
0389: // SetOperatorNode's children but weren't actually able to do so
0390: // (see modifyAccessPaths() in this class for details on when that
0391: // can happen). In that case the predicates will still be sitting
0392: // in the left/right predicate list; we can ignore them here by
0393: // just discarding them. When it comes time to modifyAccessPaths,
0394: // though, we'll handle them correctly--i.e. we'll generate a
0395: // ProjectRestrictNode over this node to ensure the predicates are
0396: // enforced.
0397:
0398: if (leftOptPredicates != null)
0399: leftOptPredicates.removeAllElements();
0400:
0401: if (rightOptPredicates != null)
0402: rightOptPredicates.removeAllElements();
0403:
0404: /* Note that predicates which have been explicitly scoped should
0405: * not be pulled. The reason is that a scoped predicate can only
0406: * be pushed to a specific, target result set. When it comes time
0407: * to pull the predicate up, there's no need to pull the scoped
0408: * predicate because it, by definition, was only intended for this
0409: * specific result set and therefore cannot be pushed anywhere else.
0410: * So at "pull" time, we can just discard the scoped predicates. We
0411: * do, however, need to pull the original, unscoped predicate from
0412: * which the scoped predicate was created because we can potentially
0413: * push that predicate elsewhere
0414: */
0415: Predicate pred = null;
0416: RemapCRsVisitor rcrv = new RemapCRsVisitor(false);
0417: for (int i = 0; i < pushedPredicates.size(); i++) {
0418: pred = (Predicate) pushedPredicates.getOptPredicate(i);
0419: if (pred.isScopedForPush()) {
0420: /* We don't need to pull the predicate if it's scoped, but
0421: * since scoped predicates are cached between rounds of
0422: * optimization, it's possible that we'll reuse the scoped
0423: * predicate again in a later round. So to make sure we
0424: * get a "fresh start" in later rounds, we un-remap the
0425: * predicate here.
0426: */
0427: pred.getAndNode().accept(rcrv);
0428: continue;
0429: }
0430: optimizablePredicates.addOptPredicate(pred);
0431: }
0432:
0433: // We're done with the pushedPredicates list, so clear it out
0434: // in preparation for another phase of optimization.
0435: pushedPredicates.removeAllElements();
0436: }
0437:
0438: /**
0439: * It's possible that we tried to push predicates to this node's
0440: * children but failed to do so. This can happen if this node's
0441: * children both satisfy the criteria for pushing a predicate
0442: * (namely, they reference base tables) but the children's
0443: * children do not (see modifyAccessPaths() above for an example
0444: * of how that can happen). So this method will walk the chain
0445: * of nodes beneath this one and determine if any SetOperatorNode
0446: * at any level has predicates that were not successfully pushed
0447: * to both of its children (note: this currently only applies
0448: * to UnionNodes).
0449: *
0450: * @return True if any UnionNode (or actually, any SetOperatorNode)
0451: * in the chain of SetOperatorNodes (starting with this one) has
0452: * unpushed predicates; false otherwise.
0453: */
0454: protected boolean hasUnPushedPredicates() {
0455: // Check this node.
0456: if (((leftOptPredicates != null) && (leftOptPredicates.size() > 0))
0457: || ((rightOptPredicates != null) && (rightOptPredicates
0458: .size() > 0))) {
0459: return true;
0460: }
0461:
0462: // Now check the children.
0463: if ((leftResultSet instanceof SetOperatorNode)
0464: && ((SetOperatorNode) leftResultSet)
0465: .hasUnPushedPredicates()) {
0466: return true;
0467: }
0468:
0469: return ((rightResultSet instanceof SetOperatorNode) && ((SetOperatorNode) rightResultSet)
0470: .hasUnPushedPredicates());
0471: }
0472:
0473: /**
0474: * Convert this object to a String. See comments in QueryTreeNode.java
0475: * for how this should be done for tree printing.
0476: *
0477: * @return This object as a String
0478: */
0479:
0480: public String toString() {
0481: if (SanityManager.DEBUG) {
0482: return "all: "
0483: + all
0484: + "\n"
0485: + "orderByList: "
0486: + (orderByList != null ? orderByList.toString()
0487: : "null") + "\n" + super .toString();
0488: } else {
0489: return "";
0490: }
0491: }
0492:
0493: /**
0494: * Bind the result columns of this ResultSetNode when there is no
0495: * base table to bind them to. This is useful for SELECT statements,
0496: * where the result columns get their types from the expressions that
0497: * live under them.
0498: *
0499: * @param fromListParam FromList to use/append to.
0500: *
0501: * @exception StandardException Thrown on error
0502: */
0503: public void bindResultColumns(FromList fromListParam)
0504: throws StandardException {
0505: super .bindResultColumns(fromListParam);
0506:
0507: /* Now we build our RCL */
0508: buildRCL();
0509: }
0510:
0511: /**
0512: * Bind the result columns for this ResultSetNode to a base table.
0513: * This is useful for INSERT and UPDATE statements, where the
0514: * result columns get their types from the table being updated or
0515: * inserted into.
0516: * If a result column list is specified, then the verification that the
0517: * result column list does not contain any duplicates will be done when
0518: * binding them by name.
0519: *
0520: * @param targetTableDescriptor The TableDescriptor for the table being
0521: * updated or inserted into
0522: * @param targetColumnList For INSERT statements, the user
0523: * does not have to supply column
0524: * names (for example, "insert into t
0525: * values (1,2,3)". When this
0526: * parameter is null, it means that
0527: * the user did not supply column
0528: * names, and so the binding should
0529: * be done based on order. When it
0530: * is not null, it means do the binding
0531: * by name, not position.
0532: * @param statement Calling DMLStatementNode (Insert or Update)
0533: * @param fromListParam FromList to use/append to.
0534: *
0535: * @exception StandardException Thrown on error
0536: */
0537:
0538: public void bindResultColumns(
0539: TableDescriptor targetTableDescriptor, FromVTI targetVTI,
0540: ResultColumnList targetColumnList,
0541: DMLStatementNode statement, FromList fromListParam)
0542: throws StandardException {
0543: super .bindResultColumns(targetTableDescriptor, targetVTI,
0544: targetColumnList, statement, fromListParam);
0545:
0546: /* Now we build our RCL */
0547: buildRCL();
0548: }
0549:
0550: /**
0551: * Build the RCL for this node. We propagate the RCL up from the
0552: * left child to form this node's RCL.
0553: *
0554: * @exception StandardException Thrown on error
0555: */
0556:
0557: private void buildRCL() throws StandardException {
0558: /* Verify that both sides of the union have the same # of columns in their
0559: * RCL.
0560: */
0561: if (leftResultSet.getResultColumns().size() != rightResultSet
0562: .getResultColumns().size()) {
0563: throw StandardException.newException(
0564: SQLState.LANG_UNION_UNMATCHED_COLUMNS,
0565: getOperatorName());
0566: }
0567:
0568: /* We need to recreate resultColumns for this node, since there
0569: * may have been 1 or more *'s in the left's SELECT list.
0570: */
0571: resultColumns = leftResultSet.getResultColumns()
0572: .copyListAndObjects();
0573:
0574: /* Create new expressions with the dominant types after verifying
0575: * union compatibility between left and right sides.
0576: */
0577: resultColumns.setUnionResultExpression(rightResultSet
0578: .getResultColumns(), tableNumber, level,
0579: getOperatorName());
0580: }
0581:
0582: /**
0583: * Bind the result columns of a table constructor to the types in the
0584: * given ResultColumnList. Use when inserting from a table constructor,
0585: * and there are nulls in the values clauses.
0586: *
0587: * @param rcl The ResultColumnList with the types to bind to
0588: *
0589: * @exception StandardException Thrown on error.
0590: */
0591: public void bindUntypedNullsToResultColumns(ResultColumnList rcl)
0592: throws StandardException {
0593: /*
0594: ** If the RCL from the parent is null, then
0595: ** the types are coming from the union itself.
0596: ** So we have to cross check the two child
0597: ** rcls.
0598: */
0599: if (rcl == null) {
0600: ResultColumnList lrcl = rightResultSet.getResultColumns();
0601: ResultColumnList rrcl = leftResultSet.getResultColumns();
0602:
0603: leftResultSet.bindUntypedNullsToResultColumns(rrcl);
0604: rightResultSet.bindUntypedNullsToResultColumns(lrcl);
0605: } else {
0606: leftResultSet.bindUntypedNullsToResultColumns(rcl);
0607: rightResultSet.bindUntypedNullsToResultColumns(rcl);
0608: }
0609: }
0610:
0611: /**
0612: * Get the parameter types from the given RowResultSetNode into the
0613: * given array of types. If an array position is already filled in,
0614: * don't clobber it.
0615: *
0616: * @param types The array of types to fill in
0617: * @param rrsn The RowResultSetNode from which to take the param types
0618: *
0619: * @return The number of new types found in the RowResultSetNode
0620: */
0621: int getParamColumnTypes(DataTypeDescriptor[] types,
0622: RowResultSetNode rrsn) throws StandardException {
0623: int numTypes = 0;
0624:
0625: /* Look for columns where we have not found a non-? yet. */
0626: for (int i = 0; i < types.length; i++) {
0627: if (types[i] == null) {
0628: ResultColumn rc = (ResultColumn) rrsn
0629: .getResultColumns().elementAt(i);
0630: if (!(rc.getExpression().requiresTypeFromContext())) {
0631: types[i] = rc.getExpressionType();
0632: numTypes++;
0633: }
0634: }
0635: }
0636:
0637: return numTypes;
0638: }
0639:
0640: /**
0641: * Set the type of each ? parameter in the given RowResultSetNode
0642: * according to its ordinal position in the given array of types.
0643: *
0644: * @param types An array of types containing the proper type for each
0645: * ? parameter, by ordinal position.
0646: * @param rrsn A RowResultSetNode that could contain ? parameters whose
0647: * types need to be set.
0648: *
0649: * @exception StandardException Thrown on error
0650: */
0651: void setParamColumnTypes(DataTypeDescriptor[] types,
0652: RowResultSetNode rrsn) throws StandardException {
0653: /*
0654: ** Look for ? parameters in the result column list
0655: ** of each RowResultSetNode
0656: */
0657: ResultColumnList rrcl = rrsn.getResultColumns();
0658: int rrclSize = rrcl.size();
0659: for (int index = 0; index < rrclSize; index++) {
0660: ResultColumn rc = (ResultColumn) rrcl.elementAt(index);
0661:
0662: if (rc.getExpression().requiresTypeFromContext()) {
0663: /*
0664: ** We found a ? - set its type to the type from the
0665: ** type array.
0666: */
0667: rc.getExpression().setType(types[index]);
0668: }
0669: }
0670: }
0671:
0672: /**
0673: * Bind the expressions in the target list. This means binding the
0674: * sub-expressions, as well as figuring out what the return type is
0675: * for each expression. This is useful for EXISTS subqueries, where we
0676: * need to validate the target list before blowing it away and replacing
0677: * it with a SELECT true.
0678: *
0679: * @exception StandardException Thrown on error
0680: */
0681:
0682: public void bindTargetExpressions(FromList fromListParam)
0683: throws StandardException {
0684: leftResultSet.bindTargetExpressions(fromListParam);
0685: rightResultSet.bindTargetExpressions(fromListParam);
0686: }
0687:
0688: /**
0689: * Push the order by list down from the cursor node
0690: * into its child result set so that the optimizer
0691: * has all of the information that it needs to
0692: * consider sort avoidance.
0693: *
0694: * @param orderByList The order by list
0695: */
0696: void pushOrderByList(OrderByList orderByList) {
0697: this .orderByList = orderByList;
0698: }
0699:
0700: /**
0701: * Put a ProjectRestrictNode on top of each FromTable in the FromList.
0702: * ColumnReferences must continue to point to the same ResultColumn, so
0703: * that ResultColumn must percolate up to the new PRN. However,
0704: * that ResultColumn will point to a new expression, a VirtualColumnNode,
0705: * which points to the FromTable and the ResultColumn that is the source for
0706: * the ColumnReference.
0707: * (The new PRN will have the original of the ResultColumnList and
0708: * the ResultColumns from that list. The FromTable will get shallow copies
0709: * of the ResultColumnList and its ResultColumns. ResultColumn.expression
0710: * will remain at the FromTable, with the PRN getting a new
0711: * VirtualColumnNode for each ResultColumn.expression.)
0712: * We then project out the non-referenced columns. If there are no referenced
0713: * columns, then the PRN's ResultColumnList will consist of a single ResultColumn
0714: * whose expression is 1.
0715: *
0716: * @param numTables Number of tables in the DML Statement
0717: * @param gbl The group by list, if any
0718: * @param fromList The from list, if any
0719: *
0720: * @return The preprocessed ResultSetNode that can be optimized
0721: *
0722: * @exception StandardException Thrown on error
0723: */
0724:
0725: public ResultSetNode preprocess(int numTables, GroupByList gbl,
0726: FromList fromList) throws StandardException {
0727: ResultSetNode newTop = this ;
0728:
0729: /* RESOLVE - what does numTables and referencedTableMap mean here? */
0730: leftResultSet = leftResultSet.preprocess(numTables, gbl,
0731: fromList);
0732: rightResultSet = rightResultSet.preprocess(numTables, gbl,
0733: fromList);
0734:
0735: /* Build the referenced table map (left || right) */
0736: referencedTableMap = (JBitSet) leftResultSet
0737: .getReferencedTableMap().clone();
0738: referencedTableMap.or((JBitSet) rightResultSet
0739: .getReferencedTableMap());
0740:
0741: /* If this is a UNION without an all and we have
0742: * an order by then we can consider eliminating the sort for the
0743: * order by. All of the columns in the order by list must
0744: * be ascending in order to do this. There are 2 cases:
0745: * o The order by list is an in order prefix of the columns
0746: * in the select list. In this case the output of the
0747: * sort from the distinct will be in the right order
0748: * so we simply eliminate the order by list.
0749: * o The order by list is a subset of the columns in the
0750: * the select list. In this case we need to reorder the
0751: * columns in the select list so that the ordering columns
0752: * are an in order prefix of the select list and put a PRN
0753: * above the select so that the shape of the result set
0754: * is as expected.
0755: */
0756: if ((!all) && orderByList != null && orderByList.allAscending()) {
0757: /* Order by list currently restricted to columns in select
0758: * list, so we will always eliminate the order by here.
0759: */
0760: if (orderByList.isInOrderPrefix(resultColumns)) {
0761: orderByList = null;
0762: }
0763: /* RESOLVE - We currently only eliminate the order by if it is
0764: * a prefix of the select list. We do not currently do the
0765: * elimination if the order by is not a prefix because the code
0766: * doesn't work. The problem has something to do with the
0767: * fact that we generate additional nodes between the union
0768: * and the PRN (for reordering that we would generate here)
0769: * when modifying the access paths. VCNs under the PRN can be
0770: * seen as correlated since their source resultset is the Union
0771: * which is no longer the result set directly under them. This
0772: * causes the wrong code to get generated. (jerry - 11/3/98)
0773: * (bug 59)
0774: */
0775: }
0776:
0777: return newTop;
0778: }
0779:
0780: /**
0781: * Ensure that the top of the RSN tree has a PredicateList.
0782: *
0783: * @param numTables The number of tables in the query.
0784: * @return ResultSetNode A RSN tree with a node which has a PredicateList on top.
0785: *
0786: * @exception StandardException Thrown on error
0787: */
0788: public ResultSetNode ensurePredicateList(int numTables)
0789: throws StandardException {
0790: return genProjectRestrict(numTables);
0791: }
0792:
0793: /**
0794: * Verify that a SELECT * is valid for this type of subquery.
0795: *
0796: * @param outerFromList The FromList from the outer query block(s)
0797: * @param subqueryType The subquery type
0798: *
0799: * @exception StandardException Thrown on error
0800: */
0801: public void verifySelectStarSubquery(FromList outerFromList,
0802: int subqueryType) throws StandardException {
0803: /* Check both sides - SELECT * is not valid on either side */
0804: leftResultSet.verifySelectStarSubquery(outerFromList,
0805: subqueryType);
0806: rightResultSet.verifySelectStarSubquery(outerFromList,
0807: subqueryType);
0808: }
0809:
0810: /**
0811: * Determine whether or not the specified name is an exposed name in
0812: * the current query block.
0813: *
0814: * @param name The specified name to search for as an exposed name.
0815: * @param schemaName Schema name, if non-null.
0816: * @param exactMatch Whether or not we need an exact match on specified schema and table
0817: * names or match on table id.
0818: *
0819: * @return The FromTable, if any, with the exposed name.
0820: *
0821: * @exception StandardException Thrown on error
0822: */
0823: protected FromTable getFromTableByName(String name,
0824: String schemaName, boolean exactMatch)
0825: throws StandardException {
0826: /* We search both sides for a TableOperatorNode (join nodes)
0827: * but only the left side for a UnionNode.
0828: */
0829: return leftResultSet.getFromTableByName(name, schemaName,
0830: exactMatch);
0831: }
0832:
0833: /**
0834: * Set the result column for the subquery to a boolean true,
0835: * Useful for transformations such as
0836: * changing:
0837: * where exists (select ... from ...)
0838: * to:
0839: * where (select true from ...)
0840: *
0841: * NOTE: No transformation is performed if the ResultColumn.expression is
0842: * already the correct boolean constant.
0843: *
0844: * @param onlyConvertAlls Boolean, whether or not to just convert *'s
0845: *
0846: * @exception StandardException Thrown on error
0847: */
0848: public void setResultToBooleanTrueNode(boolean onlyConvertAlls)
0849: throws StandardException {
0850: super .setResultToBooleanTrueNode(onlyConvertAlls);
0851: leftResultSet.setResultToBooleanTrueNode(onlyConvertAlls);
0852: rightResultSet.setResultToBooleanTrueNode(onlyConvertAlls);
0853: }
0854:
0855: /**
0856: * This ResultSet is the source for an Insert. The target RCL
0857: * is in a different order and/or a superset of this RCL. In most cases
0858: * we will reorder and/or add defaults to the current RCL so that is
0859: * matches the target RCL. Those RSNs whose generate() method does
0860: * not handle projects will insert a PRN, with a new RCL which matches
0861: * the target RCL, above the current RSN.
0862: * NOTE - The new or enhanced RCL will be fully bound.
0863: *
0864: * @param numTargetColumns # of columns in target RCL
0865: * @param colMap int array representation of correspondence between
0866: * RCLs - colmap[i] = -1 -> missing in current RCL
0867: * colmap[i] = j -> targetRCL(i) <-> thisRCL(j+1)
0868: * @param dataDictionary DataDictionary to use
0869: * @param targetTD TableDescriptor for target if the target is not a VTI, null if a VTI
0870: * @param targetVTI Target description if it is a VTI, null if not a VTI
0871: *
0872: * @return ResultSetNode The new top of the tree
0873: *
0874: * @exception StandardException Thrown on error
0875: */
0876: public ResultSetNode enhanceRCLForInsert(int numTargetColumns,
0877: int[] colMap, DataDictionary dataDictionary,
0878: TableDescriptor targetTD, FromVTI targetVTI)
0879: throws StandardException {
0880: // our newResultCols are put into the bound form straight away.
0881: ResultColumnList newResultCols = (ResultColumnList) getNodeFactory()
0882: .getNode(C_NodeTypes.RESULT_COLUMN_LIST,
0883: getContextManager());
0884: int numResultSetColumns = resultColumns.size();
0885:
0886: /* Create a massaged version of the source RCL.
0887: * (Much simpler to build new list and then assign to source,
0888: * rather than massage the source list in place.)
0889: */
0890: for (int index = 0; index < numTargetColumns; index++) {
0891: ResultColumn newResultColumn;
0892: ResultColumn oldResultColumn;
0893: ColumnReference newColumnReference;
0894:
0895: if (colMap[index] != -1) {
0896: // getResultColumn uses 1-based positioning, so offset the colMap entry appropriately
0897: oldResultColumn = resultColumns
0898: .getResultColumn(colMap[index] + 1);
0899:
0900: newColumnReference = (ColumnReference) getNodeFactory()
0901: .getNode(C_NodeTypes.COLUMN_REFERENCE,
0902: oldResultColumn.getName(), null,
0903: getContextManager());
0904: /* The ColumnReference points to the source of the value */
0905: newColumnReference.setSource(oldResultColumn);
0906: // colMap entry is 0-based, columnId is 1-based.
0907: newColumnReference.setType(oldResultColumn
0908: .getExpressionType());
0909:
0910: // Source of an insert, so nesting levels must be 0
0911: newColumnReference.setNestingLevel(0);
0912: newColumnReference.setSourceLevel(0);
0913:
0914: // because the insert already copied the target table's
0915: // column descriptors into the result, we grab it from there.
0916: // alternatively, we could do what the else clause does,
0917: // and look it up in the DD again.
0918: newResultColumn = (ResultColumn) getNodeFactory()
0919: .getNode(C_NodeTypes.RESULT_COLUMN,
0920: oldResultColumn.getType(),
0921: newColumnReference, getContextManager());
0922: } else {
0923: newResultColumn = genNewRCForInsert(targetTD,
0924: targetVTI, index + 1, dataDictionary);
0925: }
0926:
0927: newResultCols.addResultColumn(newResultColumn);
0928: }
0929:
0930: /* The generated ProjectRestrictNode now has the ResultColumnList
0931: * in the order that the InsertNode expects.
0932: * NOTE: This code here is an exception to several "rules":
0933: * o This is the only ProjectRestrictNode that is currently
0934: * generated outside of preprocess().
0935: * o The UnionNode is the only node which is not at the
0936: * top of the query tree which has ColumnReferences under
0937: * its ResultColumnList prior to expression push down.
0938: */
0939: return (ResultSetNode) getNodeFactory().getNode(
0940: C_NodeTypes.PROJECT_RESTRICT_NODE, this , newResultCols,
0941: null, null, null, null, tableProperties,
0942: getContextManager());
0943: }
0944:
0945: /**
0946: * Evaluate whether or not the subquery in a FromSubquery is flattenable.
0947: * Currently, a FSqry is flattenable if all of the following are true:
0948: * o Subquery is a SelectNode. (ie, not a RowResultSetNode or a UnionNode)
0949: * o It contains no top level subqueries. (RESOLVE - we can relax this)
0950: * o It does not contain a group by or having clause
0951: * o It does not contain aggregates.
0952: *
0953: * @param fromList The outer from list
0954: *
0955: * @return boolean Whether or not the FromSubquery is flattenable.
0956: */
0957: public boolean flattenableInFromSubquery(FromList fromList) {
0958: /* Unions in FromSubquerys are not flattenable. */
0959: return false;
0960: }
0961:
0962: /**
0963: * Return whether or not to materialize this ResultSet tree.
0964: *
0965: * @return Whether or not to materialize this ResultSet tree.
0966: * would return valid results.
0967: *
0968: * @exception StandardException Thrown on error
0969: */
0970: public boolean performMaterialization(JBitSet outerTables)
0971: throws StandardException {
0972: // RESOLVE - just say no to materialization right now - should be a cost based decision
0973: return false;
0974:
0975: /* Actual materialization, if appropriate, will be placed by our parent PRN.
0976: * This is because PRN might have a join condition to apply. (Materialization
0977: * can only occur before that.
0978: */
0979: //return true;
0980: }
0981:
0982: /**
0983: * @return the operator name: "UNION", "INTERSECT", or "EXCEPT"
0984: */
0985: abstract String getOperatorName();
0986:
0987: /**
0988: * Retrieve the list of optimizable predicates that are
0989: * targeted for the left child. Create a new (empty)
0990: * list if the list is null.
0991: */
0992: PredicateList getLeftOptPredicateList() throws StandardException {
0993: if (leftOptPredicates == null) {
0994: leftOptPredicates = (PredicateList) getNodeFactory()
0995: .getNode(C_NodeTypes.PREDICATE_LIST,
0996: getContextManager());
0997: }
0998:
0999: return leftOptPredicates;
1000: }
1001:
1002: /**
1003: * Retrieve the list of optimizable predicates that are
1004: * targeted for the right child. Create a new (empty)
1005: * list if the list is null.
1006: */
1007: PredicateList getRightOptPredicateList() throws StandardException {
1008: if (rightOptPredicates == null) {
1009: rightOptPredicates = (PredicateList) getNodeFactory()
1010: .getNode(C_NodeTypes.PREDICATE_LIST,
1011: getContextManager());
1012: }
1013:
1014: return rightOptPredicates;
1015: }
1016:
1017: }
|