IntersectOrExceptNode


1   /*
2   
3      Derby - Class org.apache.derby.impl.sql.compile.IntersectNode
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.reference.ClassName;
25  
26  import org.apache.derby.iapi.services.sanity.SanityManager;
27  import org.apache.derby.iapi.services.classfile.VMOpcode;
28  import org.apache.derby.iapi.services.compiler.MethodBuilder;
29  import org.apache.derby.iapi.services.context.ContextManager;
30  
31  import org.apache.derby.iapi.error.StandardException;
32  
33  import org.apache.derby.iapi.sql.compile.NodeFactory;
34  import org.apache.derby.iapi.sql.compile.Optimizable;
35  import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
36  import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
37  import org.apache.derby.iapi.sql.compile.Optimizer;
38  import org.apache.derby.iapi.sql.compile.CostEstimate;
39  import org.apache.derby.iapi.sql.compile.RowOrdering;
40  import org.apache.derby.iapi.sql.compile.C_NodeTypes;
41  
42  import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
43  
44  import org.apache.derby.iapi.reference.SQLState;
45  
46  import org.apache.derby.iapi.types.DataTypeDescriptor;
47  
48  import org.apache.derby.iapi.util.JBitSet;
49  import org.apache.derby.iapi.util.ReuseFactory;
50  
51  import java.sql.Types  ;
52  
53  import java.util.BitSet  ;
54  
55  /**
56   * A IntersectOrExceptNode represents an INTERSECT or EXCEPT DML statement.
57   *
58   * @author Jack Klebanoff
59   */
60  
61  public class IntersectOrExceptNode extends SetOperatorNode
62  {
63      /* Currently we implement INTERSECT and EXCEPT by rewriting
64       *   t1 (INTERSECT|EXCEPT) [ALL] t2
65       * as (roughly)
66       *   setOpResultSet( opType, all, (select * from t1 order by 1,2,...n), (select * from t2 ORDER BY 1,2,...,n))
67       * where n is the number of columns in t1 (which must be the same as the number of columns in t2),
68       * and opType is INTERSECT, or EXCEPT.
69       *
70       * The setOpResultSet result set simultaneously scans through its two ordered inputs and
71       * performs the intersect or except.
72       *
73       * There are other query plans that may be more efficient, depending on the sizes. One plan is
74       * to make a hash table from one of the input tables and then look up each row of the other input
75       * table in the hash table.  However, we have not yet implemented spilling to disk in the
76       * BackingStoreHashtable class: currently the whole hash table is in RAM. If we were to use it
77       * we would blow up on large input tables.
78       */
79  
80      private int opType;
81      public static final int INTERSECT_OP = 1;
82      public static final int EXCEPT_OP = 2;
83  
84      /* Only optimize it once */
85      /* Only call addNewNodes() once */
86      private boolean addNewNodesCalled;
87  
88      private int[] intermediateOrderByColumns; // The input result sets will be ordered on these columns. 0 indexed
89      private int[] intermediateOrderByDirection; // ascending = 1, descending = -1
90  
91      /**
92       * Initializer for a SetOperatorNode.
93       *
94       * @param leftResult        The ResultSetNode on the left side of this union
95       * @param rightResult       The ResultSetNode on the right side of this union
96       * @param all               Whether or not this is an ALL.
97       * @param tableProperties   Properties list associated with the table
98       *
99       * @exception StandardException     Thrown on error
100      */
101 
102     public void init( Object   opType,
103                       Object   leftResult,
104                       Object   rightResult,
105                       Object   all,
106                       Object   tableProperties)
107         throws StandardException
108     {
109         super.init( leftResult, rightResult, all, tableProperties);
110         this.opType = ((Integer  ) opType).intValue();
111     }
112 
113     private int getOpType()
114     {
115         return opType;
116     }
117     
118     /**
119      * Push order by lists down to the children so that we can implement the intersect/except
120      * by scan of the two sorted inputs.
121      *
122      * @param numTables         Number of tables in the DML Statement
123      * @param gbl               The group by list, if any
124      * @param fromList          The from list, if any
125      *
126      * @return The preprocessed ResultSetNode that can be optimized
127      *
128      * @exception StandardException     Thrown on error
129      */
130 
131     public ResultSetNode preprocess(int numTables,
132                                     GroupByList gbl,
133                                     FromList fromList)
134                                 throws StandardException
135     {
136         // RESOLVE: We are in a quandary as to when and how we should generate order by lists. SelectNode processing
137         // requires order by lists at the start of preprocess. That is why we are doing it here. However we can
138         // pick any column ordering. Depending on the child expressions the optimizer may be able to avoid a
139         // sort if we pick the right column ordering. For instance if one of the child expressions is
140         // "select <key columns>, <other expressions> from T" where there is a unique index on <key columns>
141         // then we can just generate an order by on the key columns and the optimizer should use the unique index
142         // to produce the sorted result set. However the ResultSetNode class does not make it easy to
143         // find the structure of the query expression. Furthermore we most want to avoid a sort on the larger
144         // input, but the size estimate is not available at preprocess time.
145 
146         intermediateOrderByColumns = new int[ getResultColumns().size()];
147         intermediateOrderByDirection = new int[ intermediateOrderByColumns.length];
148         /* If there is an order by on the result of the intersect then use that because we know that doing so
149          * will avoid a sort.  If the output of the intersect/except is small relative to its inputs then in some
150          * cases it would be better to sort the inputs on a different sequence of columns, but it is hard to analyze
151          * the input query expressions to see if a sort can be avoided.
152          */
153         if( orderByList != null)
154         {
155             BitSet colsOrdered = new BitSet( intermediateOrderByColumns.length);
156             int orderByListSize = orderByList.size();
157             int intermediateOrderByIdx = 0;
158             for( int i = 0; i < orderByListSize; i++)
159             {
160                 if( colsOrdered.get(i))
161                     continue;
162                 OrderByColumn orderByColumn = orderByList.getOrderByColumn(i);
163                 intermediateOrderByDirection[intermediateOrderByIdx] = orderByColumn.isAscending() ? 1 : -1;
164                 int columnIdx = orderByColumn.getResultColumn().getColumnPosition() - 1;
165                 intermediateOrderByColumns[intermediateOrderByIdx] = columnIdx;
166                 colsOrdered.set( columnIdx);
167                 intermediateOrderByIdx++;
168             }
169             for( int i = 0; i < intermediateOrderByColumns.length; i++)
170             {
171                 if( ! colsOrdered.get(i))
172                 {
173                     intermediateOrderByDirection[intermediateOrderByIdx] = 1;
174                     intermediateOrderByColumns[intermediateOrderByIdx] = i;
175                     intermediateOrderByIdx++;
176                 }
177             }
178             orderByList = null; // It will be pushed down.
179         }
180         else // The output of the intersect/except does not have to be ordered
181         {
182             // Pick an intermediate ordering that minimizes the cost.
183             // RESOLVE: how do you do that?
184             for( int i = 0; i < intermediateOrderByColumns.length; i++)
185             {
186                 intermediateOrderByDirection[i] = 1;
187                 intermediateOrderByColumns[i] = i;
188             }
189         }
190         pushOrderingDown( leftResultSet);
191         pushOrderingDown( rightResultSet);
192 
193         return super.preprocess( numTables, gbl, fromList);
194     } // end of preprocess
195 
196     private void pushOrderingDown( ResultSetNode rsn)
197         throws StandardException
198     {
199         ContextManager cm = getContextManager();
200         NodeFactory nf = getNodeFactory();
201         OrderByList orderByList = (OrderByList) nf.getNode( C_NodeTypes.ORDER_BY_LIST, cm);
202         for( int i = 0; i < intermediateOrderByColumns.length; i++)
203         {
204             OrderByColumn orderByColumn = (OrderByColumn)
205               nf.getNode( C_NodeTypes.ORDER_BY_COLUMN,
206               nf.getNode(C_NodeTypes.INT_CONSTANT_NODE,
207                      ReuseFactory.getInteger( intermediateOrderByColumns[i] + 1),
208                      cm),
209                           cm);
210             if( intermediateOrderByDirection[i] < 0)
211                 orderByColumn.setDescending();
212             orderByList.addOrderByColumn( orderByColumn);
213         }
214         orderByList.bindOrderByColumns( rsn);
215         rsn.pushOrderByList( orderByList);
216     } // end of pushOrderingDown
217                                                             
218     /**
219      * @see org.apache.derby.iapi.sql.compile.Optimizable#estimateCost
220      */
221     public CostEstimate estimateCost( OptimizablePredicateList predList,
222                                       ConglomerateDescriptor cd,
223                                       CostEstimate outerCost,
224                                       Optimizer optimizer,
225                                       RowOrdering rowOrdering)
226                           throws StandardException
227     {
228         leftResultSet = optimizeSource(
229                             optimizer,
230                             leftResultSet,
231                             (PredicateList) null,
232                             outerCost);
233 
234         rightResultSet = optimizeSource(
235                             optimizer,
236                             rightResultSet,
237                             (PredicateList) null,
238                             outerCost);
239 
240         CostEstimate costEstimate = getCostEstimate(optimizer);
241         CostEstimate leftCostEstimate = leftResultSet.getCostEstimate();
242         CostEstimate rightCostEstimate = rightResultSet.getCostEstimate();
243         // The cost is the sum of the two child costs plus the cost of sorting the union.
244         costEstimate.setCost( leftCostEstimate.getEstimatedCost() + rightCostEstimate.getEstimatedCost(),
245                               getRowCountEstimate( leftCostEstimate.rowCount(),
246                                                    rightCostEstimate.rowCount()),
247                               getSingleScanRowCountEstimate( leftCostEstimate.singleScanRowCount(),
248                                                              rightCostEstimate.singleScanRowCount()));
249 
250         return costEstimate;
251     } // End of estimateCost
252 
253     /**
254      * @see Optimizable#modifyAccessPath
255      *
256      * @exception StandardException     Thrown on error
257      */
258     public Optimizable modifyAccessPath(JBitSet outerTables) throws StandardException
259     {
260         Optimizable retOptimizable;
261         retOptimizable = super.modifyAccessPath(outerTables);
262 
263         /* We only want call addNewNodes() once */
264         if (addNewNodesCalled)
265         {
266             return retOptimizable;
267         }
268         return (Optimizable) addNewNodes();
269     }
270 
271     /**
272      * @see ResultSetNode#modifyAccessPaths
273      *
274      * @exception StandardException     Thrown on error
275      */
276     public ResultSetNode modifyAccessPaths() throws StandardException
277     {
278         ResultSetNode retRSN;
279         retRSN = super.modifyAccessPaths();
280 
281         /* We only want call addNewNodes() once */
282         if (addNewNodesCalled)
283         {
284             return retRSN;
285         }
286         return addNewNodes();
287     }
288 
289     /**
290      * Add any new ResultSetNodes that are necessary to the tree.
291      * We wait until after optimization to do this in order to
292      * make it easier on the optimizer.
293      *
294      * @return (Potentially new) head of the ResultSetNode tree.
295      *
296      * @exception StandardException     Thrown on error
297      */
298     private ResultSetNode addNewNodes()
299         throws StandardException
300     {
301         /* Only call addNewNodes() once */
302         if (addNewNodesCalled)
303         {
304             return this;
305         }
306 
307         addNewNodesCalled = true;
308 
309         if( orderByList == null)
310             return this;
311         // Generate an order by node on top of the intersect/except
312         return (ResultSetNode) getNodeFactory().getNode( C_NodeTypes.ORDER_BY_NODE,
313                                                          this,
314                                                          orderByList,
315                                                          tableProperties,
316                                                          getContextManager());
317     } // end of addNewNodes
318 
319     /**
320      * Generate the code.
321      *
322      * @exception StandardException     Thrown on error
323      */
324     public void generate( ActivationClassBuilder acb,
325                           MethodBuilder mb)
326         throws StandardException
327     {
328 
329         /* Get the next ResultSet #, so that we can number this ResultSetNode, its
330          * ResultColumnList and ResultSet.
331          */
332         assignResultSetNumber();
333 
334         // Get our final cost estimate based on the child estimates.
335         costEstimate = getFinalCostEstimate();
336 
337         // build up the tree.
338 
339         /* Generate the SetOpResultSet. Arguments:
340          *  1) expression for left child ResultSet
341          *  2) expression for right child ResultSet
342          *  3) activation
343          *  4) resultSetNumber
344          *  5) estimated row count
345          *  6) estimated cost
346          *  7) opType
347          *  8) all
348          *  9) close method
349          *  10) intermediateOrderByColumns saved object index
350          *  11) intermediateOrderByDirection saved object index
351          */
352 
353         acb.pushGetResultSetFactoryExpression(mb); // instance for getSetOpResultSet
354 
355         getLeftResultSet().generate( acb, mb);
356         getRightResultSet().generate( acb, mb);
357 
358         acb.pushThisAsActivation(mb);
359         mb.push(resultSetNumber);
360         mb.push( costEstimate.getEstimatedRowCount());
361         mb.push( costEstimate.getEstimatedCost());
362         mb.push( getOpType());
363         mb.push( all);
364         mb.push( getCompilerContext().addSavedObject( intermediateOrderByColumns));
365         mb.push( getCompilerContext().addSavedObject( intermediateOrderByDirection));
366 
367         mb.callMethod(VMOpcode.INVOKEINTERFACE,
368                       (String  ) null,
369                       "getSetOpResultSet",
370                       ClassName.NoPutResultSet, 10);
371     } // end of generate
372 
373     /**
374      * @see ResultSetNode#getFinalCostEstimate
375      *
376      * Get the final CostEstimate for this IntersectOrExceptNode.
377      *
378      * @return  The final CostEstimate for this IntersectOrExceptNode,
379      *  which is the sum of the two child costs.  The final number of
380      *  rows depends on whether this is an INTERSECT or EXCEPT (see
381      *  getRowCountEstimate() in this class for more).
382      */
383     public CostEstimate getFinalCostEstimate()
384         throws StandardException
385     {
386         if (finalCostEstimate != null)
387             return finalCostEstimate;
388 
389         CostEstimate leftCE = leftResultSet.getFinalCostEstimate();
390         CostEstimate rightCE = rightResultSet.getFinalCostEstimate();
391 
392         finalCostEstimate = getNewCostEstimate();
393         finalCostEstimate.setCost(
394             leftCE.getEstimatedCost() + rightCE.getEstimatedCost(),
395             getRowCountEstimate(leftCE.rowCount(), rightCE.rowCount()),
396             getSingleScanRowCountEstimate(leftCE.singleScanRowCount(),
397                 rightCE.singleScanRowCount()));
398 
399         return finalCostEstimate;
400     }
401 
402     String   getOperatorName()
403     {
404         switch( opType)
405         {
406         case INTERSECT_OP:
407             return "INTERSECT";
408 
409         case EXCEPT_OP:
410             return "EXCEPT";
411         }
412         if( SanityManager.DEBUG)
413             SanityManager.THROWASSERT( "Invalid intersectOrExcept opType: " + opType);
414         return "?";
415     }
416     
417     double getRowCountEstimate( double leftRowCount, double rightRowCount)
418     {
419         switch( opType)
420         {
421         case INTERSECT_OP:
422             // The result has at most min( leftRowCount, rightRowCount). Estimate the actual row count at
423             // half that.
424             return Math.min( leftRowCount, rightRowCount)/2;
425 
426         case EXCEPT_OP:
427             // The result has at most leftRowCount rows and at least
428             // max(0, leftRowCount - rightRowCount) rows.  Use the mean
429             // of those two as the estimate.
430             return (leftRowCount + Math.max(0, leftRowCount - rightRowCount))/2;
431         }
432         if( SanityManager.DEBUG)
433             SanityManager.THROWASSERT( "Invalid intersectOrExcept opType: " + opType);
434         return 1.0;
435     } // end of getRowCountEstimate
436     
437     double getSingleScanRowCountEstimate( double leftSingleScanRowCount, double rightSingleScanRowCount)
438     {
439         return getRowCountEstimate( leftSingleScanRowCount, rightSingleScanRowCount);
440     }
441 }
442
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags