KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > sql > compile > UnionNode


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