001: /*
002:
003: Derby - Class org.apache.derby.impl.sql.compile.UnionNode
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.sql.compile;
023:
024: import org.apache.derby.iapi.services.compiler.MethodBuilder;
025:
026: import org.apache.derby.iapi.services.sanity.SanityManager;
027:
028: import org.apache.derby.iapi.error.StandardException;
029:
030: import org.apache.derby.iapi.sql.compile.Optimizable;
031: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
032: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
033: import org.apache.derby.iapi.sql.compile.Optimizer;
034: import org.apache.derby.iapi.sql.compile.CostEstimate;
035: import org.apache.derby.iapi.sql.compile.RowOrdering;
036: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
037:
038: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
039:
040: import org.apache.derby.iapi.reference.SQLState;
041: import org.apache.derby.iapi.reference.ClassName;
042:
043: import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
044:
045: import org.apache.derby.iapi.types.DataTypeDescriptor;
046:
047: import org.apache.derby.iapi.util.JBitSet;
048: import org.apache.derby.iapi.services.classfile.VMOpcode;
049:
050: /**
051: * A UnionNode represents a UNION in a DML statement. It contains a boolean
052: * telling whether the union operation should eliminate duplicate rows.
053: *
054: * @author Jeff Lichtman
055: */
056:
057: public class UnionNode extends SetOperatorNode {
058: /* Only optimize it once */
059: /* Only call addNewNodes() once */
060: private boolean addNewNodesCalled;
061:
062: /* Is this a UNION ALL generated for a table constructor -- a VALUES expression with multiple rows. */
063: boolean tableConstructor;
064:
065: /* True if this is the top node of a table constructor */
066: boolean topTableConstructor;
067:
068: /**
069: * Initializer for a UnionNode.
070: *
071: * @param leftResult The ResultSetNode on the left side of this union
072: * @param rightResult The ResultSetNode on the right side of this union
073: * @param all Whether or not this is a UNION ALL.
074: * @param tableConstructor Whether or not this is from a table constructor.
075: * @param tableProperties Properties list associated with the table
076: *
077: * @exception StandardException Thrown on error
078: */
079:
080: public void init(Object leftResult, Object rightResult, Object all,
081: Object tableConstructor, Object tableProperties)
082: throws StandardException {
083: super .init(leftResult, rightResult, all, tableProperties);
084:
085: /* Is this a UNION ALL for a table constructor? */
086: this .tableConstructor = ((Boolean) tableConstructor)
087: .booleanValue();
088: } // end of init
089:
090: /**
091: * Mark this as the top node of a table constructor.
092: */
093: public void markTopTableConstructor() {
094: topTableConstructor = true;
095: }
096:
097: /**
098: * Tell whether this is a UNION for a table constructor.
099: */
100: boolean tableConstructor() {
101: return tableConstructor;
102: }
103:
104: /**
105: * Check for (and reject) ? parameters directly under the ResultColumns.
106: * This is done for SELECT statements. Don't reject parameters that
107: * are in a table constructor - these are allowed, as long as the
108: * table constructor is in an INSERT statement or each column of the
109: * table constructor has at least one non-? column. The latter case
110: * is checked below, in bindExpressions().
111: *
112: * @exception StandardException Thrown if a ? parameter found
113: * directly under a ResultColumn
114: */
115: public void rejectParameters() throws StandardException {
116: if (!tableConstructor())
117: super .rejectParameters();
118: }
119:
120: /**
121: * Set the type of column in the result column lists of each
122: * source of this union tree to the type in the given result column list
123: * (which represents the result columns for an insert).
124: * This is only for table constructors that appear in insert statements.
125: *
126: * @param typeColumns The ResultColumnList containing the desired result
127: * types.
128: *
129: * @exception StandardException Thrown on error
130: */
131: void setTableConstructorTypes(ResultColumnList typeColumns)
132: throws StandardException {
133: if (SanityManager.DEBUG) {
134: SanityManager
135: .ASSERT(resultColumns.size() <= typeColumns.size(),
136: "More columns in ResultColumnList than in base table.");
137: }
138:
139: ResultSetNode rsn;
140:
141: /*
142: ** Should only set types of ? parameters to types of result columns
143: ** if it's a table constructor.
144: */
145: if (tableConstructor()) {
146: /* By looping through the union nodes, we avoid recursion */
147: for (rsn = this ; rsn instanceof UnionNode;) {
148: UnionNode union = (UnionNode) rsn;
149:
150: /*
151: ** Assume that table constructors are left-deep trees of UnionNodes
152: ** with RowResultSet nodes on the right.
153: */
154: if (SanityManager.DEBUG)
155: SanityManager
156: .ASSERT(
157: union.rightResultSet instanceof RowResultSetNode,
158: "A "
159: + union.rightResultSet
160: .getClass()
161: .getName()
162: + " is on the right of a union in a table constructor");
163:
164: ((RowResultSetNode) union.rightResultSet)
165: .setTableConstructorTypes(typeColumns);
166:
167: rsn = union.leftResultSet;
168: }
169:
170: /* The last node on the left should be a result set node */
171: if (SanityManager.DEBUG)
172: SanityManager
173: .ASSERT(
174: rsn instanceof RowResultSetNode,
175: "A "
176: + rsn.getClass().getName()
177: + " is at the left end of a table constructor");
178:
179: ((RowResultSetNode) rsn)
180: .setTableConstructorTypes(typeColumns);
181: }
182: }
183:
184: /*
185: * Optimizable interface
186: */
187:
188: /**
189: * @see org.apache.derby.iapi.sql.compile.Optimizable#optimizeIt
190: *
191: * @exception StandardException Thrown on error
192: */
193: public CostEstimate optimizeIt(Optimizer optimizer,
194: OptimizablePredicateList predList, CostEstimate outerCost,
195: RowOrdering rowOrdering) throws StandardException {
196: /*
197: ** RESOLVE: Most types of Optimizables only implement estimateCost(),
198: ** and leave it up to optimizeIt() in FromTable to figure out the
199: ** total cost of the join. For unions, though, we want to figure out
200: ** the best plan for the sources knowing how many outer rows there are -
201: ** it could affect their strategies significantly. So we implement
202: ** optimizeIt() here, which overrides the optimizeIt() in FromTable.
203: ** This assumes that the join strategy for which this union node is
204: ** the inner table is a nested loop join, which will not be a valid
205: ** assumption when we implement other strategies like materialization
206: ** (hash join can work only on base tables).
207: */
208:
209: /* optimize() both resultSets */
210:
211: // If we have predicates from an outer block, we want to try
212: // to push them down to this node's children. However, we can't
213: // just push the predicates down as they are; instead, we
214: // need to scope them for the child result sets first, and
215: // then push the scoped versions. This is all done in the
216: // call to pushOptPredicate() here; for more, see that method's
217: // definition in SetOperatorNode. NOTE: If we're considering a
218: // hash join then we do not push the predicates because we'll
219: // need the predicates to be at this level in order to find
220: // out if one of them is an equijoin predicate that can be used
221: // for the hash join.
222: if ((predList != null)
223: && !getCurrentAccessPath().getJoinStrategy()
224: .isHashJoin()) {
225: for (int i = predList.size() - 1; i >= 0; i--) {
226: if (pushOptPredicate(predList.getOptPredicate(i)))
227: predList.removeOptPredicate(i);
228: }
229: }
230:
231: // It's possible that a call to optimize the left/right will cause
232: // a new "truly the best" plan to be stored in the underlying base
233: // tables. If that happens and then we decide to skip that plan
234: // (which we might do if the call to "considerCost()" below decides
235: // the current path is infeasible or not the best) we need to be
236: // able to revert back to the "truly the best" plans that we had
237: // saved before we got here. So with this next call we save the
238: // current plans using "this" node as the key. If needed, we'll
239: // then make the call to revert the plans in OptimizerImpl's
240: // getNextDecoratedPermutation() method.
241: updateBestPlanMap(ADD_PLAN, this );
242:
243: leftResultSet = optimizeSource(optimizer, leftResultSet,
244: getLeftOptPredicateList(), outerCost);
245:
246: rightResultSet = optimizeSource(optimizer, rightResultSet,
247: getRightOptPredicateList(), outerCost);
248:
249: CostEstimate costEstimate = getCostEstimate(optimizer);
250:
251: /* The cost is the sum of the two child costs */
252: costEstimate
253: .setCost(leftResultSet.getCostEstimate()
254: .getEstimatedCost(), leftResultSet
255: .getCostEstimate().rowCount(), leftResultSet
256: .getCostEstimate().singleScanRowCount()
257: + rightResultSet.getCostEstimate()
258: .singleScanRowCount());
259:
260: costEstimate.add(rightResultSet.costEstimate, costEstimate);
261:
262: /*
263: ** Get the cost of this result set in the context of the whole plan.
264: */
265: getCurrentAccessPath().getJoinStrategy().estimateCost(this ,
266: predList, (ConglomerateDescriptor) null, outerCost,
267: optimizer, costEstimate);
268:
269: optimizer.considerCost(this , predList, costEstimate, outerCost);
270:
271: return costEstimate;
272: }
273:
274: /**
275: * DERBY-649: Handle pushing predicates into UnionNodes. It is possible to push
276: * single table predicates that are binaryOperations or inListOperations.
277: *
278: * Predicates of the form <columnReference> <RELOP> <constant> or <columnReference>
279: * IN <constantList> are currently handled. Since these predicates would allow
280: * optimizer to pick available indices, pushing them provides maximum benifit.
281: *
282: * It should be possible to expand this logic to cover more cases. Even pushing
283: * expressions (like a+b = 10) into SELECTs would improve performance, even if
284: * they don't allow use of index. It would mean evaluating expressions closer to
285: * data and hence could avoid sorting or other overheads that UNION may require.
286: *
287: * Note that the predicates are not removed after pushing. This is to ensure if
288: * pushing is not possible or only partially feasible.
289: *
290: * @param predicateList List of single table predicates to push
291: *
292: * @exception StandardException Thrown on error
293: */
294: public void pushExpressions(PredicateList predicateList)
295: throws StandardException {
296: // If left or right side is a UnionNode, further push the predicate list
297: // Note, it is OK not to push these predicates since they are also evaluated
298: // in the ProjectRestrictNode. There are other types of operations possible
299: // here in addition to UnionNode or SelectNode, like RowResultSetNode.
300: if (leftResultSet instanceof UnionNode)
301: ((UnionNode) leftResultSet).pushExpressions(predicateList);
302: else if (leftResultSet instanceof SelectNode)
303: predicateList.pushExpressionsIntoSelect(
304: (SelectNode) leftResultSet, true);
305:
306: if (rightResultSet instanceof UnionNode)
307: ((UnionNode) rightResultSet).pushExpressions(predicateList);
308: else if (rightResultSet instanceof SelectNode)
309: predicateList.pushExpressionsIntoSelect(
310: (SelectNode) rightResultSet, true);
311: }
312:
313: /**
314: * @see Optimizable#modifyAccessPath
315: *
316: * @exception StandardException Thrown on error
317: */
318: public Optimizable modifyAccessPath(JBitSet outerTables)
319: throws StandardException {
320: Optimizable retOptimizable;
321: retOptimizable = super .modifyAccessPath(outerTables);
322:
323: /* We only want call addNewNodes() once */
324: if (addNewNodesCalled) {
325: return retOptimizable;
326: }
327: return (Optimizable) addNewNodes();
328: }
329:
330: /**
331: * @see ResultSetNode#modifyAccessPaths
332: *
333: * @exception StandardException Thrown on error
334: */
335: public ResultSetNode modifyAccessPaths() throws StandardException {
336: ResultSetNode retRSN;
337: retRSN = super .modifyAccessPaths();
338:
339: /* We only want call addNewNodes() once */
340: if (addNewNodesCalled) {
341: return retRSN;
342: }
343: return addNewNodes();
344: }
345:
346: /**
347: * Add any new ResultSetNodes that are necessary to the tree.
348: * We wait until after optimization to do this in order to
349: * make it easier on the optimizer.
350: *
351: * @return (Potentially new) head of the ResultSetNode tree.
352: *
353: * @exception StandardException Thrown on error
354: */
355: private ResultSetNode addNewNodes() throws StandardException {
356: ResultSetNode treeTop = this ;
357:
358: /* Only call addNewNodes() once */
359: if (addNewNodesCalled) {
360: return this ;
361: }
362:
363: addNewNodesCalled = true;
364:
365: /* RESOLVE - We'd like to generate any necessary NormalizeResultSets
366: * above our children here, in the tree. However, doing so causes
367: * the following query to fail because the where clause goes against
368: * the NRS instead of the Union:
369: * SELECT TABLE_TYPE
370: * FROM SYS.SYSTABLES,
371: * (VALUES ('T','TABLE') ,
372: * ('S','SYSTEM TABLE') , ('V', 'VIEW')) T(TTABBREV,TABLE_TYPE)
373: * WHERE TTABBREV=TABLETYPE;
374: * Thus, we are forced to skip over generating the nodes in the tree
375: * and directly generate the execution time code in generate() instead.
376: * This solves the problem for some unknown reason.
377: */
378:
379: /* Simple solution (for now) to eliminating duplicates -
380: * generate a distinct above the union.
381: */
382: if (!all) {
383: /* We need to generate a NormalizeResultSetNode above us if the column
384: * types and lengths don't match. (We need to do it here, since they
385: * will end up agreeing in the PRN, which will be the immediate
386: * child of the DistinctNode, which means that the NormalizeResultSet
387: * won't get generated above the PRN.)
388: */
389: if (!columnTypesAndLengthsMatch()) {
390: treeTop = genNormalizeResultSetNode(this , false);
391: }
392:
393: treeTop = (ResultSetNode) getNodeFactory().getNode(
394: C_NodeTypes.DISTINCT_NODE,
395: treeTop.genProjectRestrict(), Boolean.FALSE,
396: tableProperties, getContextManager());
397: /* HACK - propagate our table number up to the new DistinctNode
398: * so that arbitrary hash join will work correctly. (Otherwise it
399: * could have a problem dividing up the predicate list at the end
400: * of modifyAccessPath() because the new child of the PRN above
401: * us would have a tableNumber of -1 instead of our tableNumber.)
402: */
403: ((FromTable) treeTop).setTableNumber(tableNumber);
404: treeTop.setReferencedTableMap((JBitSet) referencedTableMap
405: .clone());
406: all = true;
407: }
408:
409: /* Generate the OrderByNode if a sort is still required for
410: * the order by.
411: */
412: if (orderByList != null) {
413: treeTop = (ResultSetNode) getNodeFactory().getNode(
414: C_NodeTypes.ORDER_BY_NODE, treeTop, orderByList,
415: tableProperties, getContextManager());
416: }
417: return treeTop;
418: }
419:
420: /**
421: * Convert this object to a String. See comments in QueryTreeNode.java
422: * for how this should be done for tree printing.
423: *
424: * @return This object as a String
425: */
426:
427: public String toString() {
428: if (SanityManager.DEBUG) {
429: return "tableConstructor: " + tableConstructor + "\n"
430: + super .toString();
431: } else {
432: return "";
433: }
434: }
435:
436: /**
437: * Bind the expressions under this TableOperatorNode. This means
438: * binding the sub-expressions, as well as figuring out what the
439: * return type is for each expression.
440: *
441: * @exception StandardException Thrown on error
442: */
443:
444: public void bindExpressions(FromList fromListParam)
445: throws StandardException {
446: super .bindExpressions(fromListParam);
447:
448: /*
449: ** Each ? parameter in a table constructor that is not in an insert
450: ** statement takes its type from the first non-? in its column
451: ** of the table constructor. It's an error to have a column that
452: ** has all ?s. Do this only for the top of the table constructor
453: ** list - we don't want to do this for every level of union node
454: ** in the table constructor. Also, don't do this for an INSERT -
455: ** the types of the ? parameters come from the columns being inserted
456: ** into in that case.
457: */
458: if (topTableConstructor && (!insertSource)) {
459: /*
460: ** Step through all the rows in the table constructor to
461: ** get the type of the first non-? in each column.
462: */
463: DataTypeDescriptor[] types = new DataTypeDescriptor[leftResultSet
464: .getResultColumns().size()];
465:
466: ResultSetNode rsn;
467: int numTypes = 0;
468:
469: /* By looping through the union nodes, we avoid recursion */
470: for (rsn = this ; rsn instanceof SetOperatorNode;) {
471: SetOperatorNode setOperator = (SetOperatorNode) rsn;
472:
473: /*
474: ** Assume that table constructors are left-deep trees of
475: ** SetOperatorNodes with RowResultSet nodes on the right.
476: */
477: if (SanityManager.DEBUG)
478: SanityManager
479: .ASSERT(
480: setOperator.rightResultSet instanceof RowResultSetNode,
481: "A "
482: + setOperator.rightResultSet
483: .getClass()
484: .getName()
485: + " is on the right side of a setOperator in a table constructor");
486:
487: RowResultSetNode rrsn = (RowResultSetNode) setOperator.rightResultSet;
488:
489: numTypes += getParamColumnTypes(types, rrsn);
490:
491: rsn = setOperator.leftResultSet;
492: }
493:
494: /* The last node on the left should be a result set node */
495: if (SanityManager.DEBUG)
496: SanityManager.ASSERT(rsn instanceof RowResultSetNode);
497:
498: numTypes += getParamColumnTypes(types,
499: (RowResultSetNode) rsn);
500:
501: /* Are there any columns that are all ? parameters? */
502: if (numTypes < types.length) {
503: throw StandardException
504: .newException(SQLState.LANG_TABLE_CONSTRUCTOR_ALL_PARAM_COLUMN);
505: }
506:
507: /*
508: ** Loop through the nodes again. This time, look for parameter
509: ** nodes, and give them the type from the type array we just
510: ** constructed.
511: */
512: for (rsn = this ; rsn instanceof SetOperatorNode;) {
513: SetOperatorNode setOperator = (SetOperatorNode) rsn;
514: RowResultSetNode rrsn = (RowResultSetNode) setOperator.rightResultSet;
515:
516: setParamColumnTypes(types, rrsn);
517:
518: rsn = setOperator.leftResultSet;
519: }
520:
521: setParamColumnTypes(types, (RowResultSetNode) rsn);
522: }
523: }
524:
525: /**
526: * Generate the code for this UnionNode.
527: *
528: * @exception StandardException Thrown on error
529: */
530: public void generate(ActivationClassBuilder acb, MethodBuilder mb)
531: throws StandardException {
532: /* By the time we get here we should be a union all.
533: * (We created a DistinctNode above us, if needed,
534: * to eliminate the duplicates earlier.)
535: */
536: if (SanityManager.DEBUG) {
537: SanityManager.ASSERT(all, "all expected to be true");
538: }
539:
540: /* Get the next ResultSet #, so that we can number this ResultSetNode, its
541: * ResultColumnList and ResultSet.
542: */
543: assignResultSetNumber();
544:
545: // Get our final cost estimate based on the child estimates.
546: costEstimate = getFinalCostEstimate();
547:
548: // build up the tree.
549:
550: acb.pushGetResultSetFactoryExpression(mb); // instance for getUnionResultSet
551:
552: /* Generate the left and right ResultSets */
553: leftResultSet.generate(acb, mb);
554:
555: /* Do we need a NormalizeResultSet above the left ResultSet? */
556: if (!resultColumns.isExactTypeAndLengthMatch(leftResultSet
557: .getResultColumns())) {
558: acb.pushGetResultSetFactoryExpression(mb);
559: mb.swap();
560: generateNormalizationResultSet(acb, mb,
561: getCompilerContext().getNextResultSetNumber(),
562: makeResultDescription());
563: }
564:
565: rightResultSet.generate(acb, mb);
566:
567: /* Do we need a NormalizeResultSet above the right ResultSet? */
568: if (!resultColumns.isExactTypeAndLengthMatch(rightResultSet
569: .getResultColumns())) {
570: acb.pushGetResultSetFactoryExpression(mb);
571: mb.swap();
572: generateNormalizationResultSet(acb, mb,
573: getCompilerContext().getNextResultSetNumber(),
574: makeResultDescription());
575: }
576:
577: /* Generate the UnionResultSet:
578: * arg1: leftExpression - Expression for leftResultSet
579: * arg2: rightExpression - Expression for rightResultSet
580: * arg3: Activation
581: * arg4: resultSetNumber
582: * arg5: estimated row count
583: * arg6: estimated cost
584: * arg7: close method
585: */
586:
587: mb.push(resultSetNumber);
588: mb.push(costEstimate.rowCount());
589: mb.push(costEstimate.getEstimatedCost());
590:
591: mb.callMethod(VMOpcode.INVOKEINTERFACE, (String) null,
592: "getUnionResultSet", ClassName.NoPutResultSet, 5);
593: }
594:
595: /**
596: * @see ResultSetNode#getFinalCostEstimate
597: *
598: * Get the final CostEstimate for this UnionNode.
599: *
600: * @return The final CostEstimate for this UnionNode, which is
601: * the sum of the two child costs.
602: */
603: public CostEstimate getFinalCostEstimate() throws StandardException {
604: // If we already found it, just return it.
605: if (finalCostEstimate != null)
606: return finalCostEstimate;
607:
608: CostEstimate leftCE = leftResultSet.getFinalCostEstimate();
609: CostEstimate rightCE = rightResultSet.getFinalCostEstimate();
610:
611: finalCostEstimate = getNewCostEstimate();
612: finalCostEstimate.setCost(leftCE.getEstimatedCost(), leftCE
613: .rowCount(), leftCE.singleScanRowCount()
614: + rightCE.singleScanRowCount());
615:
616: finalCostEstimate.add(rightCE, finalCostEstimate);
617: return finalCostEstimate;
618: }
619:
620: String getOperatorName() {
621: return "UNION";
622: }
623: }
|