0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.sql.compile.JoinNode
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.services.compiler.MethodBuilder;
0027:
0028: import org.apache.derby.iapi.services.sanity.SanityManager;
0029:
0030: import org.apache.derby.iapi.error.StandardException;
0031:
0032: import org.apache.derby.iapi.sql.compile.Optimizable;
0033: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
0034: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
0035: import org.apache.derby.iapi.sql.compile.Optimizer;
0036: import org.apache.derby.iapi.sql.compile.Visitable;
0037: import org.apache.derby.iapi.sql.compile.Visitor;
0038: import org.apache.derby.iapi.sql.compile.CostEstimate;
0039: import org.apache.derby.iapi.sql.compile.RowOrdering;
0040: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
0041:
0042: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
0043: import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
0044: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
0045:
0046: import org.apache.derby.iapi.types.TypeId;
0047: import org.apache.derby.iapi.types.DataTypeDescriptor;
0048:
0049: import org.apache.derby.iapi.reference.SQLState;
0050: import org.apache.derby.iapi.reference.ClassName;
0051:
0052: import org.apache.derby.iapi.sql.Activation;
0053: import org.apache.derby.iapi.sql.ResultSet;
0054:
0055: import org.apache.derby.iapi.store.access.TransactionController;
0056:
0057: import org.apache.derby.iapi.services.loader.GeneratedMethod;
0058:
0059: import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
0060:
0061: import org.apache.derby.iapi.util.JBitSet;
0062: import org.apache.derby.iapi.util.PropertyUtil;
0063: import org.apache.derby.iapi.services.classfile.VMOpcode;
0064:
0065: import java.util.Properties;
0066: import java.util.Vector;
0067:
0068: /**
0069: * A JoinNode represents a join result set for either of the basic DML
0070: * operations: SELECT and INSERT. For INSERT - SELECT, any of the
0071: * fields in a JoinNode can be used (the JoinNode represents
0072: * the (join) SELECT statement in the INSERT - SELECT). For INSERT,
0073: * the resultColumns in the selectList will contain the names of the columns
0074: * being inserted into or updated.
0075: *
0076: * @author Jeff Lichtman
0077: */
0078:
0079: public class JoinNode extends TableOperatorNode {
0080: /* Join semantics */
0081: public static final int INNERJOIN = 1;
0082: public static final int CROSSJOIN = 2;
0083: public static final int LEFTOUTERJOIN = 3;
0084: public static final int RIGHTOUTERJOIN = 4;
0085: public static final int FULLOUTERJOIN = 5;
0086: public static final int UNIONJOIN = 6;
0087:
0088: private boolean optimized;
0089:
0090: private PredicateList leftPredicateList;
0091: private PredicateList rightPredicateList;
0092:
0093: protected boolean flattenableJoin = true;
0094: Vector aggregateVector;
0095: SubqueryList subqueryList;
0096: ValueNode joinClause;
0097: boolean joinClauseNormalized;
0098: PredicateList joinPredicates;
0099: ResultColumnList usingClause;
0100: //User provided optimizer overrides
0101: Properties joinOrderStrategyProperties;
0102:
0103: /**
0104: * Initializer for a JoinNode.
0105: *
0106: * @param leftResult The ResultSetNode on the left side of this join
0107: * @param rightResult The ResultSetNode on the right side of this join
0108: * @param onClause The ON clause
0109: * @param usingClause The USING clause
0110: * @param selectList The result column list for the join
0111: * @param tableProperties Properties list associated with the table
0112: * @param joinOrderStrategyProperties User provided optimizer overrides
0113: *
0114: * @exception StandardException Thrown on error
0115: */
0116: public void init(Object leftResult, Object rightResult,
0117: Object onClause, Object usingClause, Object selectList,
0118: Object tableProperties, Object joinOrderStrategyProperties)
0119: throws StandardException {
0120: super .init(leftResult, rightResult, tableProperties);
0121: resultColumns = (ResultColumnList) selectList;
0122: joinClause = (ValueNode) onClause;
0123: joinClauseNormalized = false;
0124: this .usingClause = (ResultColumnList) usingClause;
0125: this .joinOrderStrategyProperties = (Properties) joinOrderStrategyProperties;
0126:
0127: /* JoinNodes can be generated in the parser or at the end of optimization.
0128: * Those generated in the parser do not have resultColumns yet.
0129: */
0130: if (resultColumns != null) {
0131: /* A longer term assertion */
0132: if (SanityManager.DEBUG) {
0133: SanityManager
0134: .ASSERT(
0135: (leftResultSet.getReferencedTableMap() != null && rightResultSet
0136: .getReferencedTableMap() != null)
0137: || (leftResultSet
0138: .getReferencedTableMap() == null && rightResultSet
0139: .getReferencedTableMap() == null),
0140: "left and right referencedTableMaps are expected to either both be non-null or both be null");
0141: }
0142:
0143: /* Build the referenced table map (left || right) */
0144: if (leftResultSet.getReferencedTableMap() != null) {
0145: referencedTableMap = (JBitSet) leftResultSet
0146: .getReferencedTableMap().clone();
0147: referencedTableMap.or((JBitSet) rightResultSet
0148: .getReferencedTableMap());
0149: }
0150: }
0151: joinPredicates = (PredicateList) getNodeFactory().getNode(
0152: C_NodeTypes.PREDICATE_LIST, getContextManager());
0153: }
0154:
0155: /*
0156: * Optimizable interface
0157: */
0158:
0159: /**
0160: * @see org.apache.derby.iapi.sql.compile.Optimizable#optimizeIt
0161: *
0162: * @exception StandardException Thrown on error
0163: */
0164: public CostEstimate optimizeIt(Optimizer optimizer,
0165: OptimizablePredicateList predList, CostEstimate outerCost,
0166: RowOrdering rowOrdering) throws StandardException {
0167: optimizer
0168: .trace(Optimizer.CALLING_ON_JOIN_NODE, 0, 0, 0.0, null);
0169:
0170: // It's possible that a call to optimize the left/right will cause
0171: // a new "truly the best" plan to be stored in the underlying base
0172: // tables. If that happens and then we decide to skip that plan
0173: // (which we might do if the call to "considerCost()" below decides
0174: // the current path is infeasible or not the best) we need to be
0175: // able to revert back to the "truly the best" plans that we had
0176: // saved before we got here. So with this next call we save the
0177: // current plans using "this" node as the key. If needed, we'll
0178: // then make the call to revert the plans in OptimizerImpl's
0179: // getNextDecoratedPermutation() method.
0180: updateBestPlanMap(ADD_PLAN, this );
0181:
0182: /*
0183: ** RESOLVE: Most types of Optimizables only implement estimateCost(),
0184: ** and leave it up to optimizeIt() in FromTable to figure out the
0185: ** total cost of the join. For joins, though, we want to figure out
0186: ** the best plan for the join knowing how many outer rows there are -
0187: ** it could affect the join strategy significantly. So we implement
0188: ** optimizeIt() here, which overrides the optimizeIt() in FromTable.
0189: ** This assumes that the join strategy for which this join node is
0190: ** the inner table is a nested loop join, which will not be a valid
0191: ** assumption when we implement other strategies like materialization
0192: ** (hash join can work only on base tables).
0193: */
0194:
0195: /* RESOLVE - Need to figure out how to really optimize this node. */
0196:
0197: // RESOLVE: NEED TO SET ROW ORDERING OF SOURCES IN THE ROW ORDERING
0198: // THAT WAS PASSED IN.
0199: leftResultSet = optimizeSource(optimizer, leftResultSet,
0200: getLeftPredicateList(), outerCost);
0201:
0202: /* Move all joinPredicates down to the right.
0203: * RESOLVE - When we consider the reverse join order then
0204: * we will have to pull them back up and then push them
0205: * down to the other side when considering the reverse
0206: * join order.
0207: * RESOLVE - This logic needs to be looked at when we
0208: * implement full outer join.
0209: */
0210: // Walk joinPredicates backwards due to possible deletes
0211: for (int index = joinPredicates.size() - 1; index >= 0; index--) {
0212: JBitSet curBitSet;
0213: Predicate predicate;
0214:
0215: predicate = (Predicate) joinPredicates.elementAt(index);
0216: if (!predicate.getPushable()) {
0217: continue;
0218: }
0219: joinPredicates.removeElementAt(index);
0220: getRightPredicateList().addElement(predicate);
0221: }
0222:
0223: rightResultSet = optimizeSource(optimizer, rightResultSet,
0224: getRightPredicateList(), leftResultSet
0225: .getCostEstimate());
0226:
0227: costEstimate = getCostEstimate(optimizer);
0228:
0229: /*
0230: ** We add the costs for the inner and outer table, but the number
0231: ** of rows is that for the inner table only.
0232: */
0233: costEstimate.setCost(leftResultSet.getCostEstimate()
0234: .getEstimatedCost()
0235: + rightResultSet.getCostEstimate().getEstimatedCost(),
0236: rightResultSet.getCostEstimate().rowCount(),
0237: rightResultSet.getCostEstimate().rowCount());
0238:
0239: /*
0240: ** Some types of joins (e.g. outer joins) will return a different
0241: ** number of rows than is predicted by optimizeIt() in JoinNode.
0242: ** So, adjust this value now. This method does nothing for most
0243: ** join types.
0244: */
0245: adjustNumberOfRowsReturned(costEstimate);
0246:
0247: /*
0248: ** Get the cost of this result set in the context of the whole plan.
0249: */
0250: getCurrentAccessPath().getJoinStrategy().estimateCost(this ,
0251: predList, (ConglomerateDescriptor) null, outerCost,
0252: optimizer, costEstimate);
0253:
0254: optimizer.considerCost(this , predList, costEstimate, outerCost);
0255:
0256: /* Optimize subqueries only once, no matter how many times we're called */
0257: if ((!optimized) && (subqueryList != null)) {
0258: /* RESOLVE - Need to figure out how to really optimize this node.
0259: * Also need to figure out the pushing of the joinClause.
0260: */
0261: subqueryList.optimize(optimizer.getDataDictionary(),
0262: costEstimate.rowCount());
0263: subqueryList.modifyAccessPaths();
0264: }
0265:
0266: optimized = true;
0267:
0268: return costEstimate;
0269: }
0270:
0271: /**
0272: * @see Optimizable#pushOptPredicate
0273: *
0274: * @exception StandardException Thrown on error
0275: */
0276:
0277: public boolean pushOptPredicate(
0278: OptimizablePredicate optimizablePredicate)
0279: throws StandardException {
0280: if (SanityManager.DEBUG) {
0281: SanityManager
0282: .ASSERT(optimizablePredicate instanceof Predicate,
0283: "optimizablePredicate expected to be instanceof Predicate");
0284: SanityManager
0285: .ASSERT(!optimizablePredicate.hasSubquery()
0286: && !optimizablePredicate.hasMethodCall(),
0287: "optimizablePredicate either has a subquery or a method call");
0288: }
0289:
0290: /* Add the matching predicate to the joinPredicates */
0291: joinPredicates.addPredicate((Predicate) optimizablePredicate);
0292:
0293: /* Remap all of the ColumnReferences to point to the
0294: * source of the values.
0295: */
0296: RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
0297: ((Predicate) optimizablePredicate).getAndNode().accept(rcrv);
0298:
0299: return true;
0300: }
0301:
0302: /**
0303: * @see Optimizable#modifyAccessPath
0304: *
0305: * @exception StandardException Thrown on error
0306: */
0307: public Optimizable modifyAccessPath(JBitSet outerTables)
0308: throws StandardException {
0309: super .modifyAccessPath(outerTables);
0310:
0311: /* By the time we're done here, both the left and right
0312: * predicate lists should be empty because we pushed everything
0313: * down.
0314: */
0315: if (SanityManager.DEBUG) {
0316: if (getLeftPredicateList().size() != 0) {
0317: SanityManager
0318: .THROWASSERT("getLeftPredicateList().size() expected to be 0, not "
0319: + getLeftPredicateList().size());
0320: }
0321: if (getRightPredicateList().size() != 0) {
0322: SanityManager
0323: .THROWASSERT("getRightPredicateList().size() expected to be 0, not "
0324: + getRightPredicateList().size());
0325: }
0326: }
0327:
0328: return this ;
0329: }
0330:
0331: /**
0332: * Some types of joins (e.g. outer joins) will return a different
0333: * number of rows than is predicted by optimizeIt() in JoinNode.
0334: * So, adjust this value now. This method does nothing for most
0335: * join types.
0336: */
0337: protected void adjustNumberOfRowsReturned(CostEstimate costEstimate) {
0338: }
0339:
0340: /**
0341: * Return a ResultColumnList with all of the columns in this table.
0342: * (Used in expanding '*'s.)
0343: * NOTE: Since this method is for expanding a "*" in the SELECT list,
0344: * ResultColumn.expression will be a ColumnReference.
0345: *
0346: * @param allTableName The qualifier on the "*"
0347: *
0348: * @return ResultColumnList List of result columns from this table.
0349: *
0350: * @exception StandardException Thrown on error
0351: */
0352: public ResultColumnList getAllResultColumns(TableName allTableName)
0353: throws StandardException {
0354: /* We need special processing when there is a USING clause.
0355: * The resulting table will be the join columns from
0356: * the outer table followed by the non-join columns from
0357: * left side plus the non-join columns from the right side.
0358: */
0359: if (usingClause == null) {
0360: return getAllResultColumnsNoUsing(allTableName);
0361: }
0362:
0363: /* Get the logical left side of the join.
0364: * This is where the join columns come from.
0365: * (For RIGHT OUTER JOIN, the left is the right
0366: * and the right is the left and the JOIN is the NIOJ).
0367: */
0368: ResultSetNode logicalLeftRS = getLogicalLeftResultSet();
0369:
0370: // Get the join columns
0371: ResultColumnList joinRCL = logicalLeftRS.getAllResultColumns(
0372: null).getJoinColumns(usingClause);
0373:
0374: // Get the left and right RCLs
0375: ResultColumnList leftRCL = leftResultSet
0376: .getAllResultColumns(allTableName);
0377: ResultColumnList rightRCL = rightResultSet
0378: .getAllResultColumns(allTableName);
0379:
0380: /* Chop the join columns out of the both left and right.
0381: * Thanks to the ANSI committee, the join columns
0382: * do not belong to either table.
0383: */
0384: if (leftRCL != null) {
0385: leftRCL.removeJoinColumns(usingClause);
0386: }
0387: if (rightRCL != null) {
0388: rightRCL.removeJoinColumns(usingClause);
0389: }
0390:
0391: /* If allTableName is null, then we want to return the splicing
0392: * of the join columns followed by the non-join columns from
0393: * the left followed by the non-join columns from the right.
0394: * If not, then at most 1 side should match.
0395: * NOTE: We need to make sure that the RC's VirtualColumnIds
0396: * are correct (1 .. size).
0397: */
0398: if (leftRCL == null) {
0399: rightRCL.resetVirtualColumnIds();
0400: return rightRCL;
0401: } else if (rightRCL == null) {
0402: leftRCL.resetVirtualColumnIds();
0403: return leftRCL;
0404: } else {
0405: /* Both sides are non-null. This should only happen
0406: * if allTableName is null.
0407: */
0408: if (SanityManager.DEBUG) {
0409: if (allTableName != null) {
0410: SanityManager.THROWASSERT("allTableName ("
0411: + allTableName + ") expected to be null");
0412: }
0413: }
0414: joinRCL.destructiveAppend(leftRCL);
0415: joinRCL.destructiveAppend(rightRCL);
0416: joinRCL.resetVirtualColumnIds();
0417: return joinRCL;
0418: }
0419: }
0420:
0421: /**
0422: * Return a ResultColumnList with all of the columns in this table.
0423: * (Used in expanding '*'s.)
0424: * NOTE: Since this method is for expanding a "*" in the SELECT list,
0425: * ResultColumn.expression will be a ColumnReference.
0426: * NOTE: This method is handles the case when there is no USING clause.
0427: * The caller handles the case when there is a USING clause.
0428: *
0429: * @param allTableName The qualifier on the "*"
0430: *
0431: * @return ResultColumnList List of result columns from this table.
0432: *
0433: * @exception StandardException Thrown on error
0434: */
0435: private ResultColumnList getAllResultColumnsNoUsing(
0436: TableName allTableName) throws StandardException {
0437: ResultColumnList leftRCL = leftResultSet
0438: .getAllResultColumns(allTableName);
0439: ResultColumnList rightRCL = rightResultSet
0440: .getAllResultColumns(allTableName);
0441: /* If allTableName is null, then we want to return the spliced
0442: * left and right RCLs. If not, then at most 1 side should match.
0443: */
0444: if (leftRCL == null) {
0445: return rightRCL;
0446: } else if (rightRCL == null) {
0447: return leftRCL;
0448: } else {
0449: /* Both sides are non-null. This should only happen
0450: * if allTableName is null.
0451: */
0452: if (SanityManager.DEBUG) {
0453: if (allTableName != null) {
0454: SanityManager.THROWASSERT("allTableName ("
0455: + allTableName + ") expected to be null");
0456: }
0457: }
0458:
0459: // Return a spliced copy of the 2 lists
0460: ResultColumnList tempList = (ResultColumnList) getNodeFactory()
0461: .getNode(C_NodeTypes.RESULT_COLUMN_LIST,
0462: getContextManager());
0463: tempList.nondestructiveAppend(leftRCL);
0464: tempList.nondestructiveAppend(rightRCL);
0465: return tempList;
0466: }
0467: }
0468:
0469: /**
0470: * Try to find a ResultColumn in the table represented by this FromTable
0471: * that matches the name in the given ColumnReference.
0472: *
0473: * @param columnReference The columnReference whose name we're looking
0474: * for in the given table.
0475: *
0476: * @return A ResultColumn whose expression is the ColumnNode
0477: * that matches the ColumnReference.
0478: * Returns null if there is no match.
0479: *
0480: * @exception StandardException Thrown on error
0481: */
0482:
0483: public ResultColumn getMatchingColumn(
0484: ColumnReference columnReference) throws StandardException {
0485: /* Get the logical left and right sides of the join.
0486: * (For RIGHT OUTER JOIN, the left is the right
0487: * and the right is the left and the JOIN is the NIOJ).
0488: */
0489: ResultSetNode logicalLeftRS = getLogicalLeftResultSet();
0490: ResultSetNode logicalRightRS = getLogicalRightResultSet();
0491: ResultColumn leftRC = null;
0492: ResultColumn resultColumn = null;
0493: ResultColumn rightRC = null;
0494: ResultColumn usingRC = null;
0495:
0496: leftRC = logicalLeftRS.getMatchingColumn(columnReference);
0497:
0498: if (leftRC != null) {
0499: resultColumn = leftRC;
0500:
0501: /* Find out if the column is in the using clause */
0502: if (usingClause != null) {
0503: usingRC = usingClause.getResultColumn(leftRC.getName());
0504: }
0505: }
0506:
0507: /* We only search on the right if the column isn't in the
0508: * USING clause.
0509: */
0510: if (usingRC == null) {
0511: rightRC = logicalRightRS.getMatchingColumn(columnReference);
0512: }
0513:
0514: if (rightRC != null) {
0515: /* We must catch ambiguous column references for joins here,
0516: * since FromList only checks for ambiguous references between
0517: * nodes, not within a node.
0518: */
0519: if (leftRC != null) {
0520: throw StandardException.newException(
0521: SQLState.LANG_AMBIGUOUS_COLUMN_NAME,
0522: columnReference.getSQLColumnName());
0523: }
0524: resultColumn = rightRC;
0525: }
0526:
0527: /* Insert will bind the underlying result sets which have
0528: * tables twice. On the 2nd bind, resultColumns != null,
0529: * we must return the RC from the JoinNode's RCL which is above
0530: * the RC that we just found above. (Otherwise, the source
0531: * for the ColumnReference will be from the wrong ResultSet
0532: * at generate().)
0533: */
0534: if (resultColumns != null) {
0535: int rclSize = resultColumns.size();
0536: for (int index = 0; index < rclSize; index++) {
0537: ResultColumn rc = (ResultColumn) resultColumns
0538: .elementAt(index);
0539: VirtualColumnNode vcn = (VirtualColumnNode) rc
0540: .getExpression();
0541: if (resultColumn == vcn.getSourceColumn()) {
0542: resultColumn = rc;
0543: break;
0544: }
0545: }
0546: }
0547:
0548: return resultColumn;
0549: }
0550:
0551: /**
0552: * Bind the result columns of this ResultSetNode when there is no
0553: * base table to bind them to. This is useful for SELECT statements,
0554: * where the result columns get their types from the expressions that
0555: * live under them.
0556: *
0557: * @param fromListParam FromList to use/append to.
0558: *
0559: * @exception StandardException Thrown on error
0560: */
0561: public void bindResultColumns(FromList fromListParam)
0562: throws StandardException {
0563: super .bindResultColumns(fromListParam);
0564:
0565: /* Now we build our RCL */
0566: buildRCL();
0567:
0568: /* We cannot bind the join clause until after we've bound our
0569: * result columns. This is because the resultColumns from the
0570: * children are propagated and merged to create our resultColumns
0571: * in super.bindRCs(). If we bind the join clause prior to that
0572: * call, then the ColumnReferences in the join clause will point
0573: * to the children's RCLs at the time that they are bound, but
0574: * will end up pointing above themselves, to our resultColumns,
0575: * after the call to super.bindRCS().
0576: */
0577: deferredBindExpressions(fromListParam);
0578: }
0579:
0580: /**
0581: * Bind the result columns for this ResultSetNode to a base table.
0582: * This is useful for INSERT and UPDATE statements, where the
0583: * result columns get their types from the table being updated or
0584: * inserted into.
0585: * If a result column list is specified, then the verification that the
0586: * result column list does not contain any duplicates will be done when
0587: * binding them by name.
0588: *
0589: * @param targetTableDescriptor The TableDescriptor for the table being
0590: * updated or inserted into
0591: * @param targetColumnList For INSERT statements, the user
0592: * does not have to supply column
0593: * names (for example, "insert into t
0594: * values (1,2,3)". When this
0595: * parameter is null, it means that
0596: * the user did not supply column
0597: * names, and so the binding should
0598: * be done based on order. When it
0599: * is not null, it means do the binding
0600: * by name, not position.
0601: * @param statement Calling DMLStatementNode (Insert or Update)
0602: * @param fromListParam FromList to use/append to.
0603: *
0604: * @exception StandardException Thrown on error
0605: */
0606:
0607: public void bindResultColumns(
0608: TableDescriptor targetTableDescriptor, FromVTI targetVTI,
0609: ResultColumnList targetColumnList,
0610: DMLStatementNode statement, FromList fromListParam)
0611: throws StandardException {
0612: super .bindResultColumns(targetTableDescriptor, targetVTI,
0613: targetColumnList, statement, fromListParam);
0614:
0615: /* Now we build our RCL */
0616: buildRCL();
0617:
0618: /* We cannot bind the join clause until after we've bound our
0619: * result columns. This is because the resultColumns from the
0620: * children are propagated and merged to create our resultColumns
0621: * in super.bindRCs(). If we bind the join clause prior to that
0622: * call, then the ColumnReferences in the join clause will point
0623: * to the children's RCLs at the time that they are bound, but
0624: * will end up pointing above themselves, to our resultColumns,
0625: * after the call to super.bindRCS().
0626: */
0627: deferredBindExpressions(fromListParam);
0628: }
0629:
0630: /**
0631: * Build the RCL for this node. We propagate the RCLs up from the
0632: * children and splice them to form this node's RCL.
0633: *
0634: * @exception StandardException Thrown on error
0635: */
0636:
0637: private void buildRCL() throws StandardException {
0638: /* NOTE - we only need to build this list if it does not already
0639: * exist. This can happen in the degenerate case of an insert
0640: * select with a join expression in a derived table within the select.
0641: */
0642: if (resultColumns != null) {
0643: return;
0644: }
0645:
0646: ResultColumnList leftRCL;
0647: ResultColumnList rightRCL;
0648: ResultColumnList tmpRCL;
0649:
0650: /* We get a shallow copy of the left's ResultColumnList and its
0651: * ResultColumns. (Copy maintains ResultColumn.expression for now.)
0652: */
0653: resultColumns = leftResultSet.getResultColumns();
0654: leftRCL = resultColumns.copyListAndObjects();
0655: leftResultSet.setResultColumns(leftRCL);
0656:
0657: /* Replace ResultColumn.expression with new VirtualColumnNodes
0658: * in the ProjectRestrictNode's ResultColumnList. (VirtualColumnNodes include
0659: * pointers to source ResultSetNode, this, and source ResultColumn.)
0660: */
0661: resultColumns.genVirtualColumnNodes(leftResultSet, leftRCL,
0662: false);
0663:
0664: /*
0665: ** If this is a right outer join, we can get nulls on the left side,
0666: ** so change the types of the left result set to be nullable.
0667: */
0668: if (this instanceof HalfOuterJoinNode
0669: && ((HalfOuterJoinNode) this ).isRightOuterJoin()) {
0670: resultColumns.setNullability(true);
0671: }
0672:
0673: /* Now, repeat the process with the right's RCL */
0674: tmpRCL = rightResultSet.getResultColumns();
0675: rightRCL = tmpRCL.copyListAndObjects();
0676: rightResultSet.setResultColumns(rightRCL);
0677:
0678: /* Replace ResultColumn.expression with new VirtualColumnNodes
0679: * in the ProjectRestrictNode's ResultColumnList. (VirtualColumnNodes include
0680: * pointers to source ResultSetNode, this, and source ResultColumn.)
0681: */
0682: tmpRCL.genVirtualColumnNodes(rightResultSet, rightRCL, false);
0683: tmpRCL.adjustVirtualColumnIds(resultColumns.size());
0684:
0685: /*
0686: ** If this is a left outer join, we can get nulls on the right side,
0687: ** so change the types of the right result set to be nullable.
0688: */
0689: if (this instanceof HalfOuterJoinNode
0690: && !((HalfOuterJoinNode) this ).isRightOuterJoin()) {
0691: tmpRCL.setNullability(true);
0692: }
0693:
0694: /* Now we append the propagated RCL from the right to the one from
0695: * the left and call it our own.
0696: */
0697: resultColumns.nondestructiveAppend(tmpRCL);
0698: }
0699:
0700: private void deferredBindExpressions(FromList fromListParam)
0701: throws StandardException {
0702: /* Bind the expressions in the join clause */
0703: subqueryList = (SubqueryList) getNodeFactory().getNode(
0704: C_NodeTypes.SUBQUERY_LIST, getContextManager());
0705: aggregateVector = new Vector();
0706:
0707: /* ON clause */
0708: if (joinClause != null) {
0709: /* Create a new fromList with only left and right children before
0710: * binding the join clause. Valid column references in the join clause
0711: * are limited to columns from the 2 tables being joined. This
0712: * algorithm enforces that.
0713: */
0714: FromList fromList = (FromList) getNodeFactory().getNode(
0715: C_NodeTypes.FROM_LIST,
0716: getNodeFactory().doJoinOrderOptimization(),
0717: getContextManager());
0718: fromList.addElement((FromTable) leftResultSet);
0719: fromList.addElement((FromTable) rightResultSet);
0720:
0721: /* First bind with all tables in the from clause, to detect ambiguous
0722: * references. Push the left and right children to the front of the
0723: * fromListParam before binding the join clause. (We will
0724: * remove it before returning.) Valid column references in
0725: * the join clause are limited to columns from the 2 tables being
0726: * joined
0727: */
0728: fromListParam.insertElementAt(rightResultSet, 0);
0729: fromListParam.insertElementAt(leftResultSet, 0);
0730: joinClause = joinClause.bindExpression(fromListParam,
0731: subqueryList, aggregateVector);
0732:
0733: /* Now bind with two tables being joined. If this raises column not found exception,
0734: * then we have a reference to other tables in the from clause. Raise invalid
0735: * ON clause error to match DB2.
0736: */
0737: try {
0738: joinClause = joinClause.bindExpression(fromList,
0739: subqueryList, aggregateVector);
0740: } catch (StandardException se) {
0741: if (se.getSQLState().equals(
0742: SQLState.LANG_COLUMN_NOT_FOUND))
0743: throw StandardException
0744: .newException(SQLState.LANG_DB2_ON_CLAUSE_INVALID);
0745: throw se;
0746: }
0747:
0748: /* DB2 doesn't allow subquerries in the ON clause */
0749: if (subqueryList.size() > 0)
0750: throw StandardException
0751: .newException(SQLState.LANG_DB2_ON_CLAUSE_INVALID);
0752: /*
0753: ** We cannot have aggregates in the ON clause.
0754: ** In the future, if we relax this, we'll need
0755: ** to be able to pass the aggregateVector up
0756: ** the tree.
0757: */
0758: if (aggregateVector.size() > 0) {
0759: throw StandardException
0760: .newException(SQLState.LANG_NO_AGGREGATES_IN_ON_CLAUSE);
0761: }
0762:
0763: fromListParam.removeElementAt(0);
0764: fromListParam.removeElementAt(0);
0765: }
0766: /* USING clause */
0767: else if (usingClause != null) {
0768: /* Build a join clause from the usingClause, using the
0769: * exposed names in the left and right RSNs.
0770: * For each column in the list, we generate 2 ColumnReferences,
0771: * 1 for the left and 1 for the right. We bind each of these
0772: * to the appropriate side and build an equality predicate
0773: * between the 2. We bind the = and AND nodes by hand because
0774: * we have to bind the ColumnReferences a side at a time.
0775: * We need to bind the CRs a side at a time to ensure that
0776: * we don't find an bogus ambiguous column reference. (Bug 377)
0777: */
0778: joinClause = (AndNode) getNodeFactory().getNode(
0779: C_NodeTypes.AND_NODE, null, null,
0780: getContextManager());
0781: AndNode currAnd = (AndNode) joinClause;
0782: ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
0783: C_NodeTypes.BOOLEAN_CONSTANT_NODE, Boolean.TRUE,
0784: getContextManager());
0785:
0786: int usingSize = usingClause.size();
0787: for (int index = 0; index < usingSize; index++) {
0788: BinaryComparisonOperatorNode equalsNode;
0789: ColumnReference leftCR;
0790: ColumnReference rightCR;
0791: ResultColumn rc = (ResultColumn) usingClause
0792: .elementAt(index);
0793:
0794: /* currAnd starts as first point of insertion (leftOperand == null)
0795: * and becomes last point of insertion.
0796: */
0797: if (currAnd.getLeftOperand() != null) {
0798: currAnd.setRightOperand((AndNode) getNodeFactory()
0799: .getNode(C_NodeTypes.AND_NODE, null, null,
0800: getContextManager()));
0801: currAnd = (AndNode) currAnd.getRightOperand();
0802: }
0803:
0804: /* Create and bind the left CR */
0805: fromListParam.insertElementAt(leftResultSet, 0);
0806: leftCR = (ColumnReference) getNodeFactory().getNode(
0807: C_NodeTypes.COLUMN_REFERENCE, rc.getName(),
0808: ((FromTable) leftResultSet).getTableName(),
0809: getContextManager());
0810: leftCR = (ColumnReference) leftCR.bindExpression(
0811: fromListParam, subqueryList, aggregateVector);
0812: fromListParam.removeElementAt(0);
0813:
0814: /* Create and bind the right CR */
0815: fromListParam.insertElementAt(rightResultSet, 0);
0816: rightCR = (ColumnReference) getNodeFactory().getNode(
0817: C_NodeTypes.COLUMN_REFERENCE, rc.getName(),
0818: ((FromTable) rightResultSet).getTableName(),
0819: getContextManager());
0820: rightCR = (ColumnReference) rightCR.bindExpression(
0821: fromListParam, subqueryList, aggregateVector);
0822: fromListParam.removeElementAt(0);
0823:
0824: /* Create and insert the new = condition */
0825: equalsNode = (BinaryComparisonOperatorNode) getNodeFactory()
0826: .getNode(
0827: C_NodeTypes.BINARY_EQUALS_OPERATOR_NODE,
0828: leftCR, rightCR, getContextManager());
0829: equalsNode.bindComparisonOperator();
0830:
0831: currAnd.setLeftOperand(equalsNode);
0832: /* The right deep chain of AndNodes ends in a BinaryTrueNode.
0833: * NOTE: We set it for every AndNode, even though we will
0834: * overwrite it if this is not the last column in the list,
0835: * because postBindFixup() expects both the AndNode to have
0836: * both the left and right operands.
0837: */
0838: currAnd.setRightOperand(trueNode);
0839: currAnd.postBindFixup();
0840: }
0841: }
0842:
0843: if (joinClause != null) {
0844: /* If joinClause is a parameter, (where ?), then we assume
0845: * it will be a nullable boolean.
0846: */
0847: if (joinClause.requiresTypeFromContext()) {
0848: joinClause.setType(new DataTypeDescriptor(
0849: TypeId.BOOLEAN_ID, true));
0850: }
0851:
0852: /*
0853: ** Is the datatype of the JOIN clause BOOLEAN?
0854: **
0855: ** NOTE: This test is not necessary in SQL92 entry level, because
0856: ** it is syntactically impossible to have a non-Boolean JOIN clause
0857: ** in that level of the standard. But we intend to extend the
0858: ** language to allow Boolean user functions in the JOIN clause,
0859: ** so we need to test for the error condition.
0860: */
0861: TypeId joinTypeId = joinClause.getTypeId();
0862:
0863: /* If the where clause is not a built-in type, then generate a bound
0864: * conversion tree to a built-in type.
0865: */
0866: if (joinTypeId.userType()) {
0867: joinClause = joinClause.genSQLJavaSQLTree();
0868: }
0869:
0870: if (!joinClause.getTypeServices().getTypeId().equals(
0871: TypeId.BOOLEAN_ID)) {
0872: throw StandardException.newException(
0873: SQLState.LANG_NON_BOOLEAN_JOIN_CLAUSE,
0874: joinClause.getTypeServices().getTypeId()
0875: .getSQLTypeName());
0876: }
0877: }
0878: }
0879:
0880: /**
0881: * Put a ProjectRestrictNode on top of each FromTable in the FromList.
0882: * ColumnReferences must continue to point to the same ResultColumn, so
0883: * that ResultColumn must percolate up to the new PRN. However,
0884: * that ResultColumn will point to a new expression, a VirtualColumnNode,
0885: * which points to the FromTable and the ResultColumn that is the source for
0886: * the ColumnReference.
0887: * (The new PRN will have the original of the ResultColumnList and
0888: * the ResultColumns from that list. The FromTable will get shallow copies
0889: * of the ResultColumnList and its ResultColumns. ResultColumn.expression
0890: * will remain at the FromTable, with the PRN getting a new
0891: * VirtualColumnNode for each ResultColumn.expression.)
0892: * We then project out the non-referenced columns. If there are no referenced
0893: * columns, then the PRN's ResultColumnList will consist of a single ResultColumn
0894: * whose expression is 1.
0895: *
0896: * @param numTables Number of tables in the DML Statement
0897: * @param gbl The group by list, if any
0898: * @param fromList The from list, if any
0899: *
0900: * @return The generated ProjectRestrictNode atop the original FromTable.
0901: *
0902: * @exception StandardException Thrown on error
0903: */
0904: public ResultSetNode preprocess(int numTables, GroupByList gbl,
0905: FromList fromList) throws StandardException {
0906: ResultSetNode newTreeTop;
0907:
0908: newTreeTop = super .preprocess(numTables, gbl, fromList);
0909:
0910: /* Put the expression trees in conjunctive normal form.
0911: * NOTE - This needs to occur before we preprocess the subqueries
0912: * because the subquery transformations assume that any subquery operator
0913: * negation has already occurred.
0914: */
0915: if (joinClause != null) {
0916: normExpressions();
0917:
0918: /* Preprocess any subqueries in the join clause */
0919: if (subqueryList != null) {
0920: /* RESOLVE - In order to flatten a subquery in
0921: * the ON clause of an inner join we'd have to pass
0922: * the various lists from the outer select through to
0923: * ResultSetNode.preprocess() and overload
0924: * normExpressions in HalfOuterJoinNode. That's not
0925: * worth the effort, so we say that the ON clause
0926: * is not under a top level AND in normExpressions()
0927: * to ensure that subqueries in the ON clause do not
0928: * get flattened. That allows us to pass empty lists
0929: * to joinClause.preprocess() because we know that no
0930: * flattening will take place. (Bug #1206)
0931: */
0932: joinClause.preprocess(numTables,
0933: (FromList) getNodeFactory().getNode(
0934: C_NodeTypes.FROM_LIST,
0935: getNodeFactory()
0936: .doJoinOrderOptimization(),
0937: getContextManager()),
0938: (SubqueryList) getNodeFactory().getNode(
0939: C_NodeTypes.SUBQUERY_LIST,
0940: getContextManager()),
0941: (PredicateList) getNodeFactory().getNode(
0942: C_NodeTypes.PREDICATE_LIST,
0943: getContextManager()));
0944: }
0945:
0946: /* Pull apart the expression trees */
0947: joinPredicates.pullExpressions(numTables, joinClause);
0948: joinPredicates.categorize();
0949: joinClause = null;
0950: }
0951:
0952: return newTreeTop;
0953: }
0954:
0955: /**
0956: * Find the unreferenced result columns and project them out. This is used in pre-processing joins
0957: * that are not flattened into the where clause.
0958: */
0959: void projectResultColumns() throws StandardException {
0960: leftResultSet.projectResultColumns();
0961: rightResultSet.projectResultColumns();
0962: resultColumns.pullVirtualIsReferenced();
0963: super .projectResultColumns();
0964: }
0965:
0966: /** Put the expression trees in conjunctive normal form
0967: *
0968: * @exception StandardException Thrown on error
0969: */
0970: public void normExpressions() throws StandardException {
0971: if (joinClauseNormalized == true)
0972: return;
0973:
0974: /* For each expression tree:
0975: * o Eliminate NOTs (eliminateNots())
0976: * o Ensure that there is an AndNode on top of every
0977: * top level expression. (putAndsOnTop())
0978: * o Finish the job (changeToCNF())
0979: */
0980: joinClause = joinClause.eliminateNots(false);
0981: if (SanityManager.DEBUG) {
0982: if (!(joinClause.verifyEliminateNots())) {
0983: joinClause.treePrint();
0984: SanityManager
0985: .THROWASSERT("joinClause in invalid form: "
0986: + joinClause);
0987: }
0988: }
0989: joinClause = joinClause.putAndsOnTop();
0990: if (SanityManager.DEBUG) {
0991: if (!((joinClause instanceof AndNode) && (joinClause
0992: .verifyPutAndsOnTop()))) {
0993: joinClause.treePrint();
0994: SanityManager
0995: .THROWASSERT("joinClause in invalid form: "
0996: + joinClause);
0997: }
0998: }
0999: /* RESOLVE - ON clause is temporarily "not under a top
1000: * top level AND" until we figure out how to deal with
1001: * subqueries in the ON clause. (Bug 1206)
1002: */
1003: joinClause = joinClause.changeToCNF(false);
1004: if (SanityManager.DEBUG) {
1005: if (!((joinClause instanceof AndNode) && (joinClause
1006: .verifyChangeToCNF()))) {
1007: joinClause.treePrint();
1008: SanityManager
1009: .THROWASSERT("joinClause in invalid form: "
1010: + joinClause);
1011: }
1012: }
1013:
1014: joinClauseNormalized = true;
1015: }
1016:
1017: /**
1018: * Push expressions down to the first ResultSetNode which can do expression
1019: * evaluation and has the same referenced table map.
1020: * RESOLVE - This means only pushing down single table expressions to
1021: * DistinctNodes today. Once we have a better understanding of how
1022: * the optimizer will work, we can push down join clauses.
1023: *
1024: * @param outerPredicateList The PredicateList from the outer RS.
1025: *
1026: * @exception StandardException Thrown on error
1027: */
1028: public void pushExpressions(PredicateList outerPredicateList)
1029: throws StandardException {
1030: FromTable leftFromTable = (FromTable) leftResultSet;
1031: FromTable rightFromTable = (FromTable) rightResultSet;
1032:
1033: /* OuterJoinNodes are responsible for overriding this
1034: * method since they have different rules about where predicates
1035: * can be applied.
1036: */
1037: if (SanityManager.DEBUG) {
1038: if (this instanceof HalfOuterJoinNode) {
1039: SanityManager
1040: .THROWASSERT("JN.pushExpressions() not expected to be called for "
1041: + getClass().getName());
1042: }
1043: }
1044:
1045: /* We try to push "pushable"
1046: * predicates to 1 of 3 places:
1047: * o Predicates that only reference tables
1048: * on the left are pushed to the leftPredicateList.
1049: * o Predicates that only reference tables
1050: * on the right are pushed to the rightPredicateList.
1051: * o Predicates which reference tables on both
1052: * sides (and no others) are pushed to
1053: * the joinPredicates and may be pushed down
1054: * further during optimization.
1055: */
1056: // Left only
1057: pushExpressionsToLeft(outerPredicateList);
1058: leftFromTable.pushExpressions(getLeftPredicateList());
1059: // Right only
1060: pushExpressionsToRight(outerPredicateList);
1061: rightFromTable.pushExpressions(getRightPredicateList());
1062: // Join predicates
1063: grabJoinPredicates(outerPredicateList);
1064:
1065: /* By the time we're done here, both the left and right
1066: * predicate lists should be empty because we pushed everything
1067: * down.
1068: */
1069: if (SanityManager.DEBUG) {
1070: if (getLeftPredicateList().size() != 0) {
1071: SanityManager
1072: .THROWASSERT("getLeftPredicateList().size() expected to be 0, not "
1073: + getLeftPredicateList().size());
1074: }
1075: if (getRightPredicateList().size() != 0) {
1076: SanityManager
1077: .THROWASSERT("getRightPredicateList().size() expected to be 0, not "
1078: + getRightPredicateList().size());
1079: }
1080: }
1081: }
1082:
1083: protected void pushExpressionsToLeft(
1084: PredicateList outerPredicateList) throws StandardException {
1085: FromTable leftFromTable = (FromTable) leftResultSet;
1086:
1087: JBitSet leftReferencedTableMap = leftFromTable
1088: .getReferencedTableMap();
1089:
1090: /* Build a list of the single table predicates on left result set
1091: * that we can push down
1092: */
1093: // Walk outerPredicateList backwards due to possible deletes
1094: for (int index = outerPredicateList.size() - 1; index >= 0; index--) {
1095: JBitSet curBitSet;
1096: Predicate predicate;
1097:
1098: predicate = (Predicate) outerPredicateList.elementAt(index);
1099: if (!predicate.getPushable()) {
1100: continue;
1101: }
1102:
1103: curBitSet = predicate.getReferencedSet();
1104:
1105: /* Do we have a match? */
1106: if (leftReferencedTableMap.contains(curBitSet)) {
1107: /* Add the matching predicate to the push list */
1108: getLeftPredicateList().addPredicate(predicate);
1109:
1110: /* Remap all of the ColumnReferences to point to the
1111: * source of the values.
1112: * The tree is something like:
1113: * PRN1
1114: * |
1115: * JN (this)
1116: * / \
1117: * PRN2 PRN3
1118: * | |
1119: * FBT1 FBT2
1120: *
1121: * The ColumnReferences start off pointing to the RCL off of
1122: * PRN1. For optimization, we want them to point to the
1123: * RCL off of PRN2. In order to do that, we remap them
1124: * twice here. If optimization pushes them down to the
1125: * base table, it will remap them again.
1126: */
1127: RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
1128: predicate.getAndNode().accept(rcrv);
1129: predicate.getAndNode().accept(rcrv);
1130:
1131: /* Remove the matching predicate from the outer list */
1132: outerPredicateList.removeElementAt(index);
1133: }
1134: }
1135: }
1136:
1137: private void pushExpressionsToRight(PredicateList outerPredicateList)
1138: throws StandardException {
1139: FromTable rightFromTable = (FromTable) rightResultSet;
1140:
1141: JBitSet rightReferencedTableMap = rightFromTable
1142: .getReferencedTableMap();
1143:
1144: /* Build a list of the single table predicates on right result set
1145: * that we can push down
1146: */
1147: // Walk outerPredicateList backwards due to possible deletes
1148: for (int index = outerPredicateList.size() - 1; index >= 0; index--) {
1149: JBitSet curBitSet;
1150: Predicate predicate;
1151:
1152: predicate = (Predicate) outerPredicateList.elementAt(index);
1153: if (!predicate.getPushable()) {
1154: continue;
1155: }
1156:
1157: curBitSet = predicate.getReferencedSet();
1158:
1159: /* Do we have a match? */
1160: if (rightReferencedTableMap.contains(curBitSet)) {
1161: /* Add the matching predicate to the push list */
1162: getRightPredicateList().addPredicate(predicate);
1163:
1164: /* Remap all of the ColumnReferences to point to the
1165: * source of the values.
1166: * The tree is something like:
1167: * PRN1
1168: * |
1169: * JN (this)
1170: * / \
1171: * PRN2 PRN3
1172: * | |
1173: * FBT1 FBT2
1174: *
1175: * The ColumnReferences start off pointing to the RCL off of
1176: * PRN1. For optimization, we want them to point to the
1177: * RCL off of PRN3. In order to do that, we remap them
1178: * twice here. If optimization pushes them down to the
1179: * base table, it will remap them again.
1180: */
1181: RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
1182: predicate.getAndNode().accept(rcrv);
1183: predicate.getAndNode().accept(rcrv);
1184:
1185: /* Remove the matching predicate from the outer list */
1186: outerPredicateList.removeElementAt(index);
1187: }
1188: }
1189: }
1190:
1191: private void grabJoinPredicates(PredicateList outerPredicateList)
1192: throws StandardException {
1193: FromTable leftFromTable = (FromTable) leftResultSet;
1194: FromTable rightFromTable = (FromTable) rightResultSet;
1195:
1196: JBitSet leftReferencedTableMap = leftFromTable
1197: .getReferencedTableMap();
1198: JBitSet rightReferencedTableMap = rightFromTable
1199: .getReferencedTableMap();
1200:
1201: /* Build a list of the join predicates that we can push down */
1202: // Walk outerPredicateList backwards due to possible deletes
1203: for (int index = outerPredicateList.size() - 1; index >= 0; index--) {
1204: JBitSet curBitSet;
1205: Predicate predicate;
1206:
1207: predicate = (Predicate) outerPredicateList.elementAt(index);
1208: if (!predicate.getPushable()) {
1209: continue;
1210: }
1211:
1212: curBitSet = predicate.getReferencedSet();
1213:
1214: /* Do we have a match? */
1215: JBitSet innerBitSet = (JBitSet) rightReferencedTableMap
1216: .clone();
1217: innerBitSet.or(leftReferencedTableMap);
1218: if (innerBitSet.contains(curBitSet)) {
1219: /* Add the matching predicate to the push list */
1220: joinPredicates.addPredicate(predicate);
1221:
1222: /* Remap all of the ColumnReferences to point to the
1223: * source of the values.
1224: * The tree is something like:
1225: * PRN1
1226: * |
1227: * JN (this)
1228: * / \
1229: * PRN2 PRN3
1230: * | |
1231: * FBT1 FBT2
1232: *
1233: * The ColumnReferences start off pointing to the RCL off of
1234: * PRN1. For optimization, we want them to point to the
1235: * RCL off of PRN2 or PRN3. In order to do that, we remap them
1236: * twice here. If optimization pushes them down to the
1237: * base table, it will remap them again.
1238: */
1239: RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
1240: predicate.getAndNode().accept(rcrv);
1241: predicate.getAndNode().accept(rcrv);
1242:
1243: /* Remove the matching predicate from the outer list */
1244: outerPredicateList.removeElementAt(index);
1245: }
1246: }
1247: }
1248:
1249: /**
1250: * Flatten this JoinNode into the outer query block. The steps in
1251: * flattening are:
1252: * o Mark all ResultColumns as redundant, so that they are "skipped over"
1253: * at generate().
1254: * o Append the joinPredicates to the outer list.
1255: * o Create a FromList from the tables being joined and return
1256: * that list so that the caller will merge the 2 lists
1257: *
1258: * @param rcl The RCL from the outer query
1259: * @param outerPList PredicateList to append wherePredicates to.
1260: * @param sql The SubqueryList from the outer query
1261: * @param gbl The group by list, if any
1262: *
1263: * @return FromList The fromList from the underlying SelectNode.
1264: *
1265: * @exception StandardException Thrown on error
1266: */
1267: public FromList flatten(ResultColumnList rcl,
1268: PredicateList outerPList, SubqueryList sql, GroupByList gbl)
1269:
1270: throws StandardException {
1271: /* OuterJoinNodes should never get here.
1272: * (They can be transformed, but never
1273: * flattened directly.)
1274: */
1275: if (SanityManager.DEBUG) {
1276: if (this instanceof HalfOuterJoinNode) {
1277: SanityManager
1278: .THROWASSERT("JN.flatten() not expected to be called for "
1279: + getClass().getName());
1280: }
1281: }
1282:
1283: /* Build a new FromList composed of left and right children
1284: * NOTE: We must call FL.addElement() instead of FL.addFromTable()
1285: * since there is no exposed name. (And even if there was,
1286: * we could care less about unique exposed name checking here.)
1287: */
1288: FromList fromList = (FromList) getNodeFactory().getNode(
1289: C_NodeTypes.FROM_LIST,
1290: getNodeFactory().doJoinOrderOptimization(),
1291: getContextManager());
1292: fromList.addElement((FromTable) leftResultSet);
1293: fromList.addElement((FromTable) rightResultSet);
1294:
1295: /* Mark our RCL as redundant */
1296: resultColumns.setRedundant();
1297:
1298: /* Remap all ColumnReferences from the outer query to this node.
1299: * (We replace those ColumnReferences with clones of the matching
1300: * expression in the left and right's RCL.
1301: */
1302: rcl.remapColumnReferencesToExpressions();
1303: outerPList.remapColumnReferencesToExpressions();
1304: if (gbl != null) {
1305: gbl.remapColumnReferencesToExpressions();
1306: }
1307:
1308: if (joinPredicates.size() > 0) {
1309: outerPList.destructiveAppend(joinPredicates);
1310: }
1311:
1312: if (subqueryList != null && subqueryList.size() > 0) {
1313: sql.destructiveAppend(subqueryList);
1314: }
1315:
1316: return fromList;
1317: }
1318:
1319: /**
1320: * Currently we don't reordering any outer join w/ inner joins.
1321: */
1322: public boolean LOJ_reorderable(int numTables)
1323: throws StandardException {
1324: return false;
1325: }
1326:
1327: /**
1328: * Transform any Outer Join into an Inner Join where applicable.
1329: * (Based on the existence of a null intolerant
1330: * predicate on the inner table.)
1331: *
1332: * @param predicateTree The predicate tree for the query block
1333: *
1334: * @return The new tree top (OuterJoin or InnerJoin).
1335: *
1336: * @exception StandardException Thrown on error
1337: */
1338: public FromTable transformOuterJoins(ValueNode predicateTree,
1339: int numTables) throws StandardException {
1340: /* Can't flatten if no predicates in where clause. */
1341: if (predicateTree == null) {
1342: return this ;
1343: }
1344:
1345: /* See if left or right sides can be transformed */
1346: leftResultSet = ((FromTable) leftResultSet)
1347: .transformOuterJoins(predicateTree, numTables);
1348: rightResultSet = ((FromTable) rightResultSet)
1349: .transformOuterJoins(predicateTree, numTables);
1350:
1351: return this ;
1352: }
1353:
1354: /**
1355: * For joins, the tree will be (nodes are left out if the clauses
1356: * are empty):
1357: *
1358: * ProjectRestrictResultSet -- for the having and the select list
1359: * SortResultSet -- for the group by list
1360: * ProjectRestrictResultSet -- for the where and the select list (if no group or having)
1361: * the result set for the fromList
1362: *
1363: *
1364: * @exception StandardException Thrown on error
1365: */
1366: public void generate(ActivationClassBuilder acb, MethodBuilder mb)
1367: throws StandardException {
1368: generateCore(acb, mb, INNERJOIN, null, null);
1369: }
1370:
1371: /**
1372: * Generate the code for a qualified join node.
1373: *
1374: * @exception StandardException Thrown on error
1375: */
1376: public void generateCore(ActivationClassBuilder acb,
1377: MethodBuilder mb, int joinType) throws StandardException {
1378: generateCore(acb, mb, joinType, joinClause, subqueryList);
1379: }
1380:
1381: /**
1382: * Do the generation work for the join node hierarchy.
1383: *
1384: * @param acb The ActivationClassBuilder
1385: * @param mb the method the code is to go into
1386: * @param joinType The join type
1387: * @param joinClause The join clause, if any
1388: * @param subquerys The list of subqueries in the join clause, if any
1389: *
1390: * @exception StandardException Thrown on error
1391: */
1392: protected void generateCore(ActivationClassBuilder acb,
1393: MethodBuilder mb, int joinType, ValueNode joinClause,
1394: SubqueryList subquerys) throws StandardException {
1395: /* Put the predicates back into the tree */
1396: if (joinPredicates != null) {
1397: joinClause = joinPredicates.restorePredicates();
1398: joinPredicates = null;
1399: }
1400:
1401: /* Get the next ResultSet #, so that we can number this ResultSetNode, its
1402: * ResultColumnList and ResultSet.
1403: */
1404: assignResultSetNumber();
1405:
1406: /* Set the point of attachment in all subqueries attached
1407: * to this node.
1408: */
1409: if (subquerys != null && subquerys.size() > 0) {
1410: subquerys.setPointOfAttachment(resultSetNumber);
1411: }
1412:
1413: // build up the tree.
1414:
1415: /* Generate the JoinResultSet */
1416: /* Nested loop and hash are the only join strategy currently supporteds.
1417: * Right outer joins are transformed into left outer joins.
1418: */
1419: String joinResultSetString;
1420:
1421: if (joinType == LEFTOUTERJOIN) {
1422: joinResultSetString = ((Optimizable) rightResultSet)
1423: .getTrulyTheBestAccessPath().getJoinStrategy()
1424: .halfOuterJoinResultSetMethodName();
1425: } else {
1426: joinResultSetString = ((Optimizable) rightResultSet)
1427: .getTrulyTheBestAccessPath().getJoinStrategy()
1428: .joinResultSetMethodName();
1429: }
1430:
1431: acb.pushGetResultSetFactoryExpression(mb);
1432: int nargs = getJoinArguments(acb, mb, joinClause);
1433: mb.callMethod(VMOpcode.INVOKEINTERFACE, (String) null,
1434: joinResultSetString, ClassName.NoPutResultSet, nargs);
1435: }
1436:
1437: /**
1438: * Get the arguments to the join result set.
1439: *
1440: * @param acb The ActivationClassBuilder for the class we're building.
1441: * @param mb the method the generated code is going into
1442: * @param joinClause The join clause, if any
1443: *
1444: * @return The array of arguments to the join result set
1445: *
1446: * @exception StandardException Thrown on error
1447: */
1448: private int getJoinArguments(ActivationClassBuilder acb,
1449: MethodBuilder mb, ValueNode joinClause)
1450: throws StandardException {
1451: int numArgs = getNumJoinArguments();
1452:
1453: leftResultSet.generate(acb, mb); // arg 1
1454: mb.push(leftResultSet.resultColumns.size()); // arg 2
1455: rightResultSet.generate(acb, mb); // arg 3
1456: mb.push(rightResultSet.resultColumns.size()); // arg 4
1457:
1458: // Get our final cost estimate based on child estimates.
1459: costEstimate = getFinalCostEstimate();
1460:
1461: // for the join clause, we generate an exprFun
1462: // that evaluates the expression of the clause
1463: // against the current row of the child's result.
1464: // if the join clause is empty, we generate a function
1465: // that just returns true. (Performance tradeoff: have
1466: // this function for the empty join clause, or have
1467: // all non-empty join clauses check for a null at runtime).
1468:
1469: // generate the function and initializer:
1470: // Note: Boolean lets us return nulls (boolean would not)
1471: // private Boolean exprN()
1472: // {
1473: // return <<joinClause.generate(ps)>>;
1474: // }
1475: // static Method exprN = method pointer to exprN;
1476:
1477: // if there is no join clause, we just pass a null Expression.
1478: if (joinClause == null) {
1479: mb.pushNull(ClassName.GeneratedMethod); // arg 5
1480: } else {
1481: // this sets up the method and the static field.
1482: // generates:
1483: // Object userExprFun { }
1484: MethodBuilder userExprFun = acb.newUserExprFun();
1485:
1486: // join clause knows it is returning its value;
1487:
1488: /* generates:
1489: * return <joinClause.generate(acb)>;
1490: * and adds it to userExprFun
1491: */
1492: joinClause.generate(acb, userExprFun);
1493: userExprFun.methodReturn();
1494:
1495: // we are done modifying userExprFun, complete it.
1496: userExprFun.complete();
1497:
1498: // join clause is used in the final result set as an access of the new static
1499: // field holding a reference to this new method.
1500: // generates:
1501: // ActivationClass.userExprFun
1502: // which is the static field that "points" to the userExprFun
1503: // that evaluates the where clause.
1504: acb.pushMethodReference(mb, userExprFun); // arg 5
1505: }
1506:
1507: mb.push(resultSetNumber); // arg 6
1508:
1509: addOuterJoinArguments(acb, mb);
1510:
1511: // Does right side return a single row
1512: oneRowRightSide(acb, mb);
1513:
1514: // estimated row count
1515: mb.push(costEstimate.rowCount());
1516:
1517: // estimated cost
1518: mb.push(costEstimate.getEstimatedCost());
1519:
1520: //User may have supplied optimizer overrides in the sql
1521: //Pass them onto execute phase so it can be shown in
1522: //run time statistics.
1523: if (joinOrderStrategyProperties != null)
1524: mb.push(PropertyUtil
1525: .sortProperties(joinOrderStrategyProperties));
1526: else
1527: mb.pushNull("java.lang.String");
1528:
1529: return numArgs;
1530:
1531: }
1532:
1533: /**
1534: * @see ResultSetNode#getFinalCostEstimate
1535: *
1536: * Get the final CostEstimate for this JoinNode.
1537: *
1538: * @return The final CostEstimate for this JoinNode, which is sum
1539: * the costs for the inner and outer table. The number of rows,
1540: * though, is that for the inner table only.
1541: */
1542: public CostEstimate getFinalCostEstimate() throws StandardException {
1543: // If we already found it, just return it.
1544: if (finalCostEstimate != null)
1545: return finalCostEstimate;
1546:
1547: CostEstimate leftCE = leftResultSet.getFinalCostEstimate();
1548: CostEstimate rightCE = rightResultSet.getFinalCostEstimate();
1549:
1550: finalCostEstimate = getNewCostEstimate();
1551: finalCostEstimate.setCost(leftCE.getEstimatedCost()
1552: + rightCE.getEstimatedCost(), rightCE.rowCount(),
1553: rightCE.rowCount());
1554:
1555: return finalCostEstimate;
1556: }
1557:
1558: protected void oneRowRightSide(ActivationClassBuilder acb,
1559: MethodBuilder mb) throws StandardException {
1560: mb.push(rightResultSet.isOneRowResultSet());
1561: mb.push(rightResultSet.isNotExists()); //join is for NOT EXISTS
1562: }
1563:
1564: /**
1565: * Return the number of arguments to the join result set. This will
1566: * be overridden for other types of joins (for example, outer joins).
1567: */
1568: protected int getNumJoinArguments() {
1569: return 11;
1570: }
1571:
1572: /**
1573: * Generate and add any arguments specifict to outer joins.
1574: * (Expected to be overriden, where appropriate, in subclasses.)
1575: *
1576: * @param acb The ActivationClassBuilder
1577: * @param mb the method the generated code is to go into
1578: *
1579: * return The number of args added
1580: *
1581: * @exception StandardException Thrown on error
1582: */
1583: protected int addOuterJoinArguments(ActivationClassBuilder acb,
1584: MethodBuilder mb) throws StandardException {
1585: return 0;
1586: }
1587:
1588: /**
1589: * Convert the joinType to a string.
1590: *
1591: * @param joinType The joinType as an int.
1592: *
1593: * @return String The joinType as a String.
1594: */
1595: public static String joinTypeToString(int joinType) {
1596: switch (joinType) {
1597: case INNERJOIN:
1598: return "INNER JOIN";
1599:
1600: case CROSSJOIN:
1601: return "CROSS JOIN";
1602:
1603: case LEFTOUTERJOIN:
1604: return "LEFT OUTER JOIN";
1605:
1606: case RIGHTOUTERJOIN:
1607: return "RIGHT OUTER JOIN";
1608:
1609: case FULLOUTERJOIN:
1610: return "FULL OUTER JOIN";
1611:
1612: case UNIONJOIN:
1613: return "UNION JOIN";
1614:
1615: default:
1616: if (SanityManager.DEBUG) {
1617: SanityManager.ASSERT(false, "Unexpected joinType");
1618: }
1619: return null;
1620: }
1621: }
1622:
1623: protected PredicateList getLeftPredicateList()
1624: throws StandardException {
1625: if (leftPredicateList == null)
1626: leftPredicateList = (PredicateList) getNodeFactory()
1627: .getNode(C_NodeTypes.PREDICATE_LIST,
1628: getContextManager());
1629:
1630: return leftPredicateList;
1631: }
1632:
1633: protected PredicateList getRightPredicateList()
1634: throws StandardException {
1635: if (rightPredicateList == null)
1636: rightPredicateList = (PredicateList) getNodeFactory()
1637: .getNode(C_NodeTypes.PREDICATE_LIST,
1638: getContextManager());
1639:
1640: return rightPredicateList;
1641: }
1642:
1643: /**
1644: * Get the lock mode for the target of an update statement
1645: * (a delete or update). The update mode will always be row for
1646: * CurrentOfNodes. It will be table if there is no where clause.
1647: *
1648: * @return The lock mode
1649: */
1650: public int updateTargetLockMode() {
1651: /* Always use row locking if we have a join node.
1652: * We can only have a join node if there is a subquery that
1653: * got flattened, hence there is a restriction.
1654: */
1655: return TransactionController.MODE_RECORD;
1656: }
1657:
1658: /**
1659: * Mark this node and its children as not being a flattenable join.
1660: */
1661: void notFlattenableJoin() {
1662: flattenableJoin = false;
1663: leftResultSet.notFlattenableJoin();
1664: rightResultSet.notFlattenableJoin();
1665: }
1666:
1667: /**
1668: * Is this FromTable a JoinNode which can be flattened into
1669: * the parents FromList.
1670: *
1671: * @return boolean Whether or not this FromTable can be flattened.
1672: */
1673: public boolean isFlattenableJoinNode() {
1674: return flattenableJoin;
1675: }
1676:
1677: /**
1678: * Return whether or not the underlying ResultSet tree
1679: * is ordered on the specified columns.
1680: * RESOLVE - This method currently only considers the outermost table
1681: * of the query block.
1682: *
1683: * @param crs The specified ColumnReference[]
1684: * @param permuteOrdering Whether or not the order of the CRs in the array can be permuted
1685: * @param fbtVector Vector that is to be filled with the FromBaseTable
1686: *
1687: * @return Whether the underlying ResultSet tree
1688: * is ordered on the specified column.
1689: *
1690: * @exception StandardException Thrown on error
1691: */
1692: boolean isOrderedOn(ColumnReference[] crs, boolean permuteOrdering,
1693: Vector fbtVector) throws StandardException {
1694: /* RESOLVE - easiest thing for now is to only consider the leftmost child */
1695: return leftResultSet.isOrderedOn(crs, permuteOrdering,
1696: fbtVector);
1697: }
1698:
1699: /**
1700: * Prints the sub-nodes of this object. See QueryTreeNode.java for
1701: * how tree printing is supposed to work.
1702: *
1703: * @param depth The depth of this node in the tree
1704: */
1705:
1706: public void printSubNodes(int depth) {
1707: if (SanityManager.DEBUG) {
1708: super .printSubNodes(depth);
1709:
1710: if (subqueryList != null) {
1711: printLabel(depth, "subqueryList: ");
1712: subqueryList.treePrint(depth + 1);
1713: }
1714:
1715: if (joinClause != null) {
1716: printLabel(depth, "joinClause: ");
1717: joinClause.treePrint(depth + 1);
1718: }
1719:
1720: if (joinPredicates.size() != 0) {
1721: printLabel(depth, "joinPredicates: ");
1722: joinPredicates.treePrint(depth + 1);
1723: }
1724:
1725: if (usingClause != null) {
1726: printLabel(depth, "usingClause: ");
1727: usingClause.treePrint(depth + 1);
1728: }
1729: }
1730: }
1731:
1732: void setSubqueryList(SubqueryList subqueryList) {
1733: this .subqueryList = subqueryList;
1734: }
1735:
1736: void setAggregateVector(Vector aggregateVector) {
1737: this .aggregateVector = aggregateVector;
1738: }
1739:
1740: /**
1741: * Return the logical left result set for this qualified
1742: * join node.
1743: * (For RIGHT OUTER JOIN, the left is the right
1744: * and the right is the left and the JOIN is the NIOJ).
1745: */
1746: ResultSetNode getLogicalLeftResultSet() {
1747: return leftResultSet;
1748: }
1749:
1750: /**
1751: * Return the logical right result set for this qualified
1752: * join node.
1753: * (For RIGHT OUTER JOIN, the left is the right
1754: * and the right is the left and the JOIN is the NIOJ).
1755: */
1756: ResultSetNode getLogicalRightResultSet() {
1757: return rightResultSet;
1758: }
1759:
1760: /**
1761: * Accept a visitor, and call v.visit()
1762: * on child nodes as necessary.
1763: *
1764: * @param v the visitor
1765: *
1766: * @exception StandardException on error
1767: */
1768: public Visitable accept(Visitor v) throws StandardException {
1769: if (v.skipChildren(this )) {
1770: return v.visit(this );
1771: }
1772:
1773: Visitable returnNode = super .accept(v);
1774:
1775: if (resultColumns != null && !v.stopTraversal()) {
1776: resultColumns = (ResultColumnList) resultColumns.accept(v);
1777: }
1778:
1779: if (joinClause != null && !v.stopTraversal()) {
1780: joinClause = (ValueNode) joinClause.accept(v);
1781: }
1782:
1783: if (usingClause != null && !v.stopTraversal()) {
1784: usingClause = (ResultColumnList) usingClause.accept(v);
1785: }
1786:
1787: return returnNode;
1788: }
1789:
1790: // This method returns the table references in Join node, and this may be
1791: // needed for LOJ reordering. For example, we may have the following query:
1792: // (T JOIN S) LOJ (X LOJ Y)
1793: // The top most LOJ may be a join betw T and X and thus we can reorder the
1794: // LOJs. However, as of 10/2002, we don't reorder LOJ mixed with join.
1795: public JBitSet LOJgetReferencedTables(int numTables)
1796: throws StandardException {
1797: JBitSet map = new JBitSet(numTables);
1798:
1799: map = (JBitSet) leftResultSet.LOJgetReferencedTables(numTables);
1800: if (map == null)
1801: return null;
1802: else
1803: map.or((JBitSet) rightResultSet
1804: .LOJgetReferencedTables(numTables));
1805:
1806: return map;
1807: }
1808:
1809: }
|