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


1 /*
2
3    Derby - Class org.apache.derby.impl.sql.compile.GroupByNode
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.context.ContextManager;
25
26 import org.apache.derby.iapi.store.access.ColumnOrdering;
27
28 import org.apache.derby.iapi.sql.compile.AccessPath;
29 import org.apache.derby.iapi.sql.compile.Optimizable;
30 import org.apache.derby.iapi.sql.compile.OptimizableList;
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.Visitable;
36 import org.apache.derby.iapi.sql.compile.Visitor;
37 import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
38 import org.apache.derby.iapi.sql.compile.RowOrdering;
39 import org.apache.derby.iapi.sql.compile.C_NodeTypes;
40
41 import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
42 import org.apache.derby.iapi.reference.ClassName;
43
44 import org.apache.derby.iapi.sql.dictionary.DataDictionary;
45 import org.apache.derby.iapi.sql.dictionary.DataDictionaryContext;
46 import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
47 import org.apache.derby.catalog.IndexDescriptor;
48
49 import org.apache.derby.iapi.sql.execute.ExecutionContext;
50
51 import org.apache.derby.iapi.sql.Activation;
52 import org.apache.derby.iapi.sql.LanguageFactory;
53 import org.apache.derby.iapi.sql.ResultColumnDescriptor;
54 import org.apache.derby.iapi.sql.ResultSet;
55
56 import org.apache.derby.iapi.error.StandardException;
57
58 import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
59 import org.apache.derby.impl.sql.execute.AggregatorInfo;
60 import org.apache.derby.impl.sql.execute.AggregatorInfoList;
61
62 import org.apache.derby.iapi.services.compiler.MethodBuilder;
63
64 import org.apache.derby.iapi.services.sanity.SanityManager;
65
66 import org.apache.derby.iapi.services.io.FormatableArrayHolder;
67 import org.apache.derby.iapi.util.JBitSet;
68
69 import org.apache.derby.impl.sql.compile.MaxMinAggregateDefinition;
70 import org.apache.derby.iapi.services.classfile.VMOpcode;
71
72 import java.util.Vector ;
73 import java.util.Properties ;
74
75
76 /**
77  * A GroupByNode represents a result set for a grouping operation
78  * on a select. Note that this includes a SELECT with aggregates
79  * and no grouping columns (in which case the select list is null)
80  * It has the same description as its input result set.
81  * <p>
82  * For the most part, it simply delegates operations to its bottomPRSet,
83  * which is currently expected to be a ProjectRestrictResultSet generated
84  * for a SelectNode.
85  * <p>
86  * NOTE: A GroupByNode extends FromTable since it can exist in a FromList.
87  * <p>
88  * There is a lot of room for optimizations here: <UL>
89  * <LI> agg(distinct x) group by x => agg(x) group by x (for min and max) </LI>
90  * <LI> min()/max() use index scans if possible, no sort may
91  * be needed. </LI>
92  * </UL>
93  *
94  * @author jerry, aggregates by jamie
95  *
96  */
97 public class GroupByNode extends SingleChildResultSetNode
98 {
99     /**
100      * The GROUP BY list
101      */
102     GroupByList groupingList;
103
104     /**
105      * The list of all aggregates in the query block
106      * that contains this group by.
107      */
108     Vector aggregateVector;
109
110     /**
111      * Information that is used at execution time to
112      * process aggregates.
113      */
114     private AggregatorInfoList aggInfo;
115
116     /**
117      * The parent to the GroupByNode. If we need to
118      * generate a ProjectRestrict over the group by
119      * then this is set to that node. Otherwise it
120      * is null.
121      */
122     FromTable parent;
123
124     private boolean addDistinctAggregate;
125     private boolean singleInputRowOptimization;
126     private int addDistinctAggregateColumnNum;
127
128     // Is the source in sorted order
129 private boolean isInSortedOrder;
130
131     /**
132      * Intializer for a GroupByNode.
133      *
134      * @param bottomPR The child FromTable
135      * @param groupingList The groupingList
136      * @param aggregateVector The vector of aggregates from
137      * the query block. Since aggregation is done
138      * at the same time as grouping, we need them
139      * here.
140      * @param tableProperties Properties list associated with the table
141      *
142      * @exception StandardException Thrown on error
143      */
144     public void init(
145                         Object bottomPR,
146                         Object groupingList,
147                         Object aggregateVector,
148                         Object tableProperties)
149             throws StandardException
150     {
151         super.init(bottomPR, tableProperties);
152
153         /* Group by without aggregates gets xformed into distinct */
154         if (SanityManager.DEBUG)
155         {
156             SanityManager.ASSERT(((Vector ) aggregateVector).size() > 0,
157                 "aggregateVector expected to be non-empty");
158             if (!(childResult instanceof Optimizable))
159             {
160                 SanityManager.THROWASSERT("childResult, " + childResult.getClass().getName() +
161                     ", expected to be instanceof Optimizable");
162             }
163             if (!(childResult instanceof FromTable))
164             {
165                 SanityManager.THROWASSERT("childResult, " + childResult.getClass().getName() +
166                     ", expected to be instanceof FromTable");
167             }
168         }
169
170         ResultColumnList newBottomRCL;
171         this.groupingList = (GroupByList) groupingList;
172         this.aggregateVector = (Vector ) aggregateVector;
173         this.parent = this;
174
175         /*
176         ** The first thing we do is put ourselves on
177         ** top of the SELECT. The select becomes the
178         ** childResult. So our RCL becomes its RCL (so
179         ** nodes above it now point to us). Map our
180         ** RCL to its columns.
181         */
182         newBottomRCL = childResult.getResultColumns().copyListAndObjects();
183         resultColumns = childResult.getResultColumns();
184         childResult.setResultColumns(newBottomRCL);
185
186         /*
187         ** We have aggregates, so we need to add
188         ** an extra PRNode and we also have to muck around
189         ** with our trees a might.
190         */
191         addAggregates();
192
193         /* We say that the source is never in sorted order if there is a distinct aggregate.
194          * (Not sure what happens if it is, so just skip it for now.)
195          * Otherwise, we check to see if the source is in sorted order on any permutation
196          * of the grouping columns.)
197          */
198         if (! addDistinctAggregate && groupingList != null)
199         {
200             ColumnReference[] crs =
201                                 new ColumnReference[this.groupingList.size()];
202
203             // Now populate the CR array and see if ordered
204 int glSize = this.groupingList.size();
205             int index;
206             for (index = 0; index < glSize; index++)
207             {
208                 GroupByColumn gc =
209                         (GroupByColumn) this.groupingList.elementAt(index);
210                 if (gc.getColumnExpression() instanceof ColumnReference)
211                 {
212                     crs[index] = (ColumnReference)gc.getColumnExpression();
213                 }
214                 else
215                 {
216                     isInSortedOrder = false;
217                     break;
218                 }
219                 
220             }
221             if (index == glSize) {
222                 isInSortedOrder = childResult.isOrderedOn(crs, true, (Vector )null);
223             }
224         }
225     }
226
227     /**
228      * Get whether or not the source is in sorted order.
229      *
230      * @return Whether or not the source is in sorted order.
231      */
232     boolean getIsInSortedOrder()
233     {
234         return isInSortedOrder;
235     }
236
237     /**
238      * Add the extra result columns required by the aggregates
239      * to the result list.
240      *
241      * @exception standard exception
242      */
243     private void addAggregates()
244         throws StandardException
245     {
246         addNewPRNode();
247         addNewColumnsForAggregation();
248         addDistinctAggregatesToOrderBy();
249     }
250
251     /**
252      * Add any distinct aggregates to the order by list.
253      * Asserts that there are 0 or more distincts.
254      */
255     private void addDistinctAggregatesToOrderBy()
256     {
257         int numDistinct = numDistinctAggregates(aggregateVector);
258         if (numDistinct != 0)
259         {
260             if (SanityManager.DEBUG)
261             {
262                 SanityManager.ASSERT(numDistinct == 1,
263                     "Should not have more than 1 distinct aggregate per Group By node");
264             }
265             
266             AggregatorInfo agg = null;
267             int count = aggInfo.size();
268             for (int i = 0; i < count; i++)
269             {
270                 agg = (AggregatorInfo) aggInfo.elementAt(i);
271                 if (agg.isDistinct())
272                 {
273                     break;
274                 }
275             }
276
277             if (SanityManager.DEBUG)
278             {
279                 SanityManager.ASSERT(agg != null && agg.isDistinct());
280             }
281
282             addDistinctAggregate = true;
283             addDistinctAggregateColumnNum = agg.getInputColNum();
284         }
285     }
286     
287     /**
288      * Add a new PR node for aggregation. Put the
289      * new PR under the sort.
290      *
291      * @exception standard exception
292      */
293     private void addNewPRNode()
294         throws StandardException
295     {
296         /*
297         ** Get the new PR, put above the GroupBy.
298         */
299         parent = (FromTable) getNodeFactory().getNode(
300                                         C_NodeTypes.PROJECT_RESTRICT_NODE,
301                                         this, // child
302 resultColumns, // result column list
303 null, // restriction
304 null, // restriction list
305 null, // project subqueries
306 null, // restrict subqueries
307 tableProperties,
308                                         getContextManager());
309
310
311         /*
312         ** Reset the bottom RCL to be empty.
313         */
314         childResult.setResultColumns((ResultColumnList)
315                                             getNodeFactory().getNode(
316                                                 C_NodeTypes.RESULT_COLUMN_LIST,
317                                                 getContextManager()));
318
319         /*
320         ** Set the group by RCL to be empty
321         */
322         resultColumns = (ResultColumnList) getNodeFactory().getNode(
323                                             C_NodeTypes.RESULT_COLUMN_LIST,
324                                             getContextManager());
325
326     }
327
328     /**
329      * In the query rewrite for group by, add the columns on which
330      * we are doing the group by.
331
332      * @see #addNewColumnsForAggregation
333      */
334     private void addUnAggColumns() throws StandardException
335     {
336         ResultColumnList bottomRCL = childResult.getResultColumns();
337         ResultColumnList groupByRCL = resultColumns;
338
339         int sz = groupingList.size();
340         for (int i = 0; i < sz; i++)
341         {
342             GroupByColumn gbc = (GroupByColumn) groupingList.elementAt(i);
343             ResultColumn newRC = (ResultColumn) getNodeFactory().getNode(
344                     C_NodeTypes.RESULT_COLUMN,
345                     "##UnaggColumn",
346                     gbc.getColumnExpression(),
347                     getContextManager());
348
349             // add this result column to the bottom rcl
350 bottomRCL.addElement(newRC);
351             newRC.markGenerated();
352             newRC.bindResultColumnToExpression();
353             newRC.setVirtualColumnId(bottomRCL.size());
354             
355             // now add this column to the groupbylist
356 ResultColumn gbRC = (ResultColumn) getNodeFactory().getNode(
357                     C_NodeTypes.RESULT_COLUMN,
358                     "##UnaggColumn",
359                     gbc.getColumnExpression(),
360                     getContextManager());
361             groupByRCL.addElement(gbRC);
362             gbRC.markGenerated();
363             gbRC.bindResultColumnToExpression();
364             gbRC.setVirtualColumnId(groupByRCL.size());
365
366             /*
367              ** Reset the original node to point to the
368              ** Group By result set.
369              */
370             VirtualColumnNode vc = (VirtualColumnNode) getNodeFactory().getNode(
371                     C_NodeTypes.VIRTUAL_COLUMN_NODE,
372                     this, // source result set.
373 gbRC,
374                     new Integer (groupByRCL.size()),
375                     getContextManager());
376
377             // we replace each group by expression
378 // in the projection list with a virtual column node
379 // that effectively points to a result column
380 // in the result set doing the group by
381 SubstituteExpressionVisitor se =
382                 new SubstituteExpressionVisitor(
383                         gbc.getColumnExpression(),
384                         vc,
385                         AggregateNode.class);
386             parent.getResultColumns().accept(se);
387
388             // finally reset gbc to its new position.
389 gbc.setColumnPosition(bottomRCL.size());
390         }
391     }
392
393     /**
394      * Add a whole slew of columns needed for
395      * aggregation. Basically, for each aggregate we add
396      * 2 columns: the aggregate input expression
397      * and the aggregator column. The input expression is
398      * taken directly from the aggregator node. The aggregator
399      * is the run time aggregator. We add it to the RC list
400      * as a new object coming into the sort node.
401      * <P>
402      * At this point this is invoked, we have the following
403      * tree: <UL>
404      * PR - (PARENT): RCL is the original select list
405      * |
406      * PR - GROUP BY: RCL is empty
407      * |
408      * PR - FROM TABLE: RCL is empty </UL> <P>
409      *
410      * For each ColumnReference in PR RCL <UL>
411      * <LI> clone the ref </LI>
412      * <LI> create a new RC in the bottom RCL and set it
413      * to the col ref </LI>
414      * <LI> create a new RC in the GROUPBY RCL and set it to
415      * point to the bottom RC </LI>
416      * <LI> reset the top PR ref to point to the new GROUPBY
417      * RC
418      *
419      * For each aggregate in aggregateVector <UL>
420      * <LI> create RC in FROM TABLE. Fill it with
421      * aggs Operator.
422      * <LI> create RC in FROM TABLE for agg result</LI>
423      * <LI> create RC in FROM TABLE for aggregator</LI>
424      * <LI> create RC in GROUPBY for agg input, set it
425      * to point to FROM TABLE RC </LI>
426      * <LI> create RC in GROUPBY for agg result</LI>
427      * <LI> create RC in GROUPBY for aggregator</LI>
428      * <LI> replace Agg with reference to RC for agg result </LI>
429      *
430      * @exception standard exception
431      */
432     private void addNewColumnsForAggregation()
433         throws StandardException
434     {
435         aggInfo = new AggregatorInfoList();
436         if (groupingList != null)
437         {
438             addUnAggColumns();
439         }
440         addAggregateColumns();
441     }
442     
443     /**
444      * In the query rewrite involving aggregates, add the columns for
445      * aggregation.
446      *
447      * @see #addNewColumnsForAggregation
448      */
449     private void addAggregateColumns() throws StandardException
450     {
451         DataDictionary dd = getDataDictionary();
452         AggregateNode aggregate = null;
453         ColumnReference newColumnRef;
454         ResultColumn newRC;
455         ResultColumn tmpRC;
456         ResultColumn aggInputRC;
457         ResultColumnList bottomRCL = childResult.getResultColumns();
458         ResultColumnList groupByRCL = resultColumns;
459         ResultColumnList aggRCL;
460         int aggregatorVColId;
461         int aggInputVColId;
462         int aggResultVColId;
463         
464         /*
465          ** Now process all of the aggregates. Replace
466          ** every aggregate with an RC. We toss out
467          ** the list of RCs, we need to get each RC
468          ** as we process its corresponding aggregate.
469          */
470         LanguageFactory lf = getLanguageConnectionContext().getLanguageFactory();
471         
472         ReplaceAggregatesWithCRVisitor replaceAggsVisitor =
473             new ReplaceAggregatesWithCRVisitor(
474                     (ResultColumnList) getNodeFactory().getNode(
475                             C_NodeTypes.RESULT_COLUMN_LIST,
476                             getContextManager()),
477                 ((FromTable) childResult).getTableNumber());
478         parent.getResultColumns().accept(replaceAggsVisitor);
479
480         /*
481         ** For each aggregate
482         */
483         int alSize = aggregateVector.size();
484         for (int index = 0; index < alSize; index++)
485         {
486             aggregate = (AggregateNode) aggregateVector.elementAt(index);
487
488             /*
489             ** AGG RESULT: Set the aggregate result to null in the
490             ** bottom project restrict.
491             */
492             newRC = (ResultColumn) getNodeFactory().getNode(
493                     C_NodeTypes.RESULT_COLUMN,
494                     "##aggregate result",
495                     aggregate.getNewNullResultExpression(),
496                     getContextManager());
497             newRC.markGenerated();
498             newRC.bindResultColumnToExpression();
499             bottomRCL.addElement(newRC);
500             newRC.setVirtualColumnId(bottomRCL.size());
501             aggResultVColId = newRC.getVirtualColumnId();
502
503             /*
504             ** Set the GB aggregrate result column to
505             ** point to this. The GB aggregate result
506             ** was created when we called
507             ** ReplaceAggregatesWithColumnReferencesVisitor()
508             */
509             newColumnRef = (ColumnReference) getNodeFactory().getNode(
510                     C_NodeTypes.COLUMN_REFERENCE,
511                     newRC.getName(),
512                     null,
513                     getContextManager());
514             newColumnRef.setSource(newRC);
515             newColumnRef.setType(newRC.getExpressionType());
516             newColumnRef.setNestingLevel(this.getLevel());
517             newColumnRef.setSourceLevel(this.getLevel());
518             tmpRC = (ResultColumn) getNodeFactory().getNode(
519                     C_NodeTypes.RESULT_COLUMN,
520                     newRC.getColumnName(),
521                     newColumnRef,
522                     getContextManager());
523             tmpRC.markGenerated();
524             tmpRC.bindResultColumnToExpression();
525             groupByRCL.addElement(tmpRC);
526             tmpRC.setVirtualColumnId(groupByRCL.size());
527
528             /*
529             ** Set the column reference to point to
530             ** this.
531             */
532             newColumnRef = aggregate.getGeneratedRef();
533             newColumnRef.setSource(tmpRC);
534
535             /*
536             ** AGG INPUT: Create a ResultColumn in the bottom
537             ** project restrict that has the expression that is
538             ** to be aggregated
539             */
540             newRC = aggregate.getNewExpressionResultColumn(dd);
541             newRC.markGenerated();
542             newRC.bindResultColumnToExpression();
543             bottomRCL.addElement(newRC);
544             newRC.setVirtualColumnId(bottomRCL.size());
545             aggInputVColId = newRC.getVirtualColumnId();
546             aggInputRC = newRC;
547     
548             /*
549             ** Add a reference to this column into the
550             ** group by columns.
551             */
552             tmpRC = getColumnReference(newRC, dd);
553             groupByRCL.addElement(tmpRC);
554             tmpRC.setVirtualColumnId(groupByRCL.size());
555
556             /*
557             ** AGGREGATOR: Add a getAggregator method call
558             ** to the bottom result column list.
559             */
560             newRC = aggregate.getNewAggregatorResultColumn(dd);
561             newRC.markGenerated();
562             newRC.bindResultColumnToExpression();
563             bottomRCL.addElement(newRC);
564             newRC.setVirtualColumnId(bottomRCL.size());
565             aggregatorVColId = newRC.getVirtualColumnId();
566
567             /*
568             ** Add a reference to this column in the Group By result
569             ** set.
570             */
571             tmpRC = getColumnReference(newRC, dd);
572             groupByRCL.addElement(tmpRC);
573             tmpRC.setVirtualColumnId(groupByRCL.size());
574
575             /*
576             ** Piece together a fake one column rcl that we will use
577             ** to generate a proper result description for input
578             ** to this agg if it is a user agg.
579             */
580             aggRCL = (ResultColumnList) getNodeFactory().getNode(
581                     C_NodeTypes.RESULT_COLUMN_LIST,
582                     getContextManager());
583             aggRCL.addElement(aggInputRC);
584
585             /*
586             ** Note that the column ids in the row are 0 based
587             ** so we have to subtract 1.
588             */
589             aggInfo.addElement(new AggregatorInfo(
590                     aggregate.getAggregateName(),
591                     aggregate.getAggregatorClassName(),
592                     aggInputVColId - 1, // aggregate input column
593 aggResultVColId -1, // the aggregate result column
594 aggregatorVColId - 1, // the aggregator column
595 aggregate.isDistinct(),
596                     lf.getResultDescription(aggRCL.makeResultDescriptors(), "SELECT")
597             ));
598         }
599     }
600
601     /**
602      * Return the parent node to this one, if there is
603      * one. It will return 'this' if there is no generated
604      * node above this one.
605      *
606      * @return the parent node
607      */
608     public FromTable getParent()
609     {
610         return parent;
611     }
612
613
614     /*
615      * Optimizable interface
616      */
617
618     /**
619      * @see Optimizable#optimizeIt
620      *
621      * @exception StandardException Thrown on error
622      */
623     public CostEstimate optimizeIt(
624                             Optimizer optimizer,
625                             OptimizablePredicateList predList,
626                             CostEstimate outerCost,
627                             RowOrdering rowOrdering)
628             throws StandardException
629     {
630         // RESOLVE: NEED TO FACTOR IN THE COST OF GROUPING (SORTING) HERE
631 CostEstimate childCost = ((Optimizable) childResult).optimizeIt(
632                                                     optimizer,
633                                                     predList,
634                                                     outerCost,
635                                                     rowOrdering);
636
637         CostEstimate retval = super.optimizeIt(
638                                                 optimizer,
639                                                 predList,
640                                                 outerCost,
641                                                 rowOrdering
642                                               );
643
644         return retval;
645     }
646
647     /**
648      * @see Optimizable#estimateCost
649      *
650      * @exception StandardException Thrown on error
651      */
652     public CostEstimate estimateCost(OptimizablePredicateList predList,
653                                         ConglomerateDescriptor cd,
654                                         CostEstimate outerCost,
655                                         Optimizer optimizer,
656                                         RowOrdering rowOrdering
657                                         )
658             throws StandardException
659     {
660         // RESOLVE: NEED TO FACTOR IN THE COST OF GROUPING (SORTING) HERE
661 //
662 CostEstimate childCost = ((Optimizable) childResult).estimateCost(
663                                                     predList,
664                                                     cd,
665                                                     outerCost,
666                                                     optimizer,
667                                                     rowOrdering);
668
669         CostEstimate costEstimate = getCostEstimate(optimizer);
670         costEstimate.setCost(childCost.getEstimatedCost(),
671                             childCost.rowCount(),
672                             childCost.singleScanRowCount());
673
674         return costEstimate;
675     }
676
677     /**
678      * @see org.apache.derby.iapi.sql.compile.Optimizable#pushOptPredicate
679      *
680      * @exception StandardException Thrown on error
681      */
682
683     public boolean pushOptPredicate(OptimizablePredicate optimizablePredicate)
684             throws StandardException
685     {
686         return ((Optimizable) childResult).pushOptPredicate(optimizablePredicate);
687     }
688
689     /**
690      * Convert this object to a String. See comments in QueryTreeNode.java
691      * for how this should be done for tree printing.
692      *
693      * @return This object as a String
694      */
695
696     public String toString()
697     {
698         if (SanityManager.DEBUG)
699         {
700             return "singleInputRowOptimization: " + singleInputRowOptimization + "\n" +
701                 childResult.toString() + "\n" + super.toString();
702         }
703         else
704         {
705             return "";
706         }
707     }
708
709     /**
710      * Evaluate whether or not the subquery in a FromSubquery is flattenable.
711      * Currently, a FSqry is flattenable if all of the following are true:
712      * o Subquery is a SelectNode.
713      * o It contains no top level subqueries. (RESOLVE - we can relax this)
714      * o It does not contain a group by or having clause
715      * o It does not contain aggregates.
716      *
717      * @param fromList The outer from list
718      *
719      * @return boolean Whether or not the FromSubquery is flattenable.
720      */
721     public boolean flattenableInFromSubquery(FromList fromList)
722     {
723         /* Can't flatten a GroupByNode */
724         return false;
725     }
726
727     /**
728      * Optimize this GroupByNode.
729      *
730      * @param dataDictionary The DataDictionary to use for optimization
731      * @param predicates The PredicateList to optimize. This should
732      * be a join predicate.
733      * @param outerRows The number of outer joining rows
734      *
735      * @return ResultSetNode The top of the optimized subtree
736      *
737      * @exception StandardException Thrown on error
738      */
739
740     public ResultSetNode optimize(DataDictionary dataDictionary,
741                                   PredicateList predicates,
742                                   double outerRows)
743                     throws StandardException
744     {
745         /* We need to implement this method since a PRN can appear above a
746          * SelectNode in a query tree.
747          */
748         childResult = (FromTable) childResult.optimize(
749                                             dataDictionary,
750                                             predicates,
751                                             outerRows);
752         Optimizer optimizer = getOptimizer(
753                         (FromList) getNodeFactory().getNode(
754                                     C_NodeTypes.FROM_LIST,
755                                     getNodeFactory().doJoinOrderOptimization(),
756                                     getContextManager()),
757                         predicates,
758                         dataDictionary,
759                         (RequiredRowOrdering) null);
760
761         // RESOLVE: NEED TO FACTOR IN COST OF SORTING AND FIGURE OUT HOW
762 // MANY ROWS HAVE BEEN ELIMINATED.
763 costEstimate = optimizer.newCostEstimate();
764
765         costEstimate.setCost(childResult.getCostEstimate().getEstimatedCost(),
766                             childResult.getCostEstimate().rowCount(),
767                             childResult.getCostEstimate().singleScanRowCount());
768
769         return this;
770     }
771
772     ResultColumnDescriptor[] makeResultDescriptors(ExecutionContext ec)
773     {
774         return childResult.makeResultDescriptors(ec);
775     }
776
777     /**
778      * Return whether or not the underlying ResultSet tree will return
779      * a single row, at most.
780      * This is important for join nodes where we can save the extra next
781      * on the right side if we know that it will return at most 1 row.
782      *
783      * @return Whether or not the underlying ResultSet tree will return a single row.
784      * @exception StandardException Thrown on error
785      */
786     public boolean isOneRowResultSet() throws StandardException
787     {
788         // Only consider scalar aggregates for now
789 return ((groupingList == null) || (groupingList.size() == 0));
790     }
791
792     /**
793      * generate the sort result set operating over the source
794      * resultset. Adds distinct aggregates to the sort if
795      * necessary.
796      *
797      * @exception StandardException Thrown on error
798      */
799     public void generate(ActivationClassBuilder acb,
800                                 MethodBuilder mb)
801                             throws StandardException
802     {
803         int orderingItem = 0;
804         int aggInfoItem = 0;
805         FormatableArrayHolder orderingHolder;
806
807         /* Get the next ResultSet#, so we can number this ResultSetNode, its
808          * ResultColumnList and ResultSet.
809          */
810         assignResultSetNumber();
811
812         // Get the final cost estimate from the child.
813 costEstimate = childResult.getFinalCostEstimate();
814
815         /*
816         ** Get the column ordering for the sort. Note that
817         ** for a scalar aggegate we may not have any ordering
818         ** columns (if there are no distinct aggregates).
819         ** WARNING: if a distinct aggregate is passed to
820         ** SortResultSet it assumes that the last column
821         ** is the distinct one. If this assumption changes
822         ** then SortResultSet will have to change.
823         */
824         orderingHolder = acb.getColumnOrdering(groupingList);
825         if (addDistinctAggregate)
826         {
827             orderingHolder = acb.addColumnToOrdering(
828                                     orderingHolder,
829                                     addDistinctAggregateColumnNum);
830         }
831
832         if (SanityManager.DEBUG)
833         {
834             if (SanityManager.DEBUG_ON("AggregateTrace"))
835             {
836                 StringBuffer s = new StringBuffer ();
837                     
838                 s.append("Group by column ordering is (");
839                 ColumnOrdering[] ordering =
840                         (ColumnOrdering[])orderingHolder.getArray(ColumnOrdering.class);
841
842                 for (int i = 0; i < ordering.length; i++)
843                 {
844                     s.append(ordering[i].getColumnId());
845                     s.append(" ");
846                 }
847                 s.append(")");
848                 SanityManager.DEBUG("AggregateTrace", s.toString());
849             }
850         }
851
852         orderingItem = acb.addItem(orderingHolder);
853
854         /*
855         ** We have aggregates, so save the aggInfo
856         ** struct in the activation and store the number
857         */
858         if (SanityManager.DEBUG)
859         {
860             SanityManager.ASSERT(aggInfo != null,
861                     "aggInfo not set up as expected");
862         }
863         aggInfoItem = acb.addItem(aggInfo);
864
865         acb.pushGetResultSetFactoryExpression(mb);
866
867         // Generate the child ResultSet
868 childResult.generate(acb, mb);
869         mb.push(isInSortedOrder);
870         mb.push(aggInfoItem);
871         mb.push(orderingItem);
872
873         resultColumns.generateHolder(acb, mb);
874
875         mb.push(resultColumns.getTotalColumnSize());
876         mb.push(resultSetNumber);
877
878         /* Generate a (Distinct)ScalarAggregateResultSet if scalar aggregates */
879         if ((groupingList == null) || (groupingList.size() == 0))
880         {
881             genScalarAggregateResultSet(acb, mb);
882         }
883         /* Generate a (Distinct)GroupedAggregateResultSet if grouped aggregates */
884         else
885         {
886             genGroupedAggregateResultSet(acb, mb);
887         }
888     }
889
890     /**
891      * Generate the code to evaluate scalar aggregates.
892      *
893      */
894     private void genScalarAggregateResultSet(ActivationClassBuilder acb,
895                                                    MethodBuilder mb)
896     {
897         /* Generate the (Distinct)ScalarAggregateResultSet:
898          * arg1: childExpress - Expression for childResult
899          * arg2: isInSortedOrder - true if source result set in sorted order
900          * arg3: aggregateItem - entry in saved objects for the aggregates,
901          * arg4: orderItem - entry in saved objects for the ordering
902          * arg5: Activation
903          * arg6: rowAllocator - method to construct rows for fetching
904          * from the sort
905          * arg7: row size
906          * arg8: resultSetNumber
907          * arg9: Whether or not to perform min optimization.
908          */
909         String resultSet = (addDistinctAggregate) ? "getDistinctScalarAggregateResultSet" : "getScalarAggregateResultSet";
910
911         mb.push(singleInputRowOptimization);
912         mb.push(costEstimate.rowCount());
913         mb.push(costEstimate.getEstimatedCost());
914
915         mb.callMethod(VMOpcode.INVOKEINTERFACE, (String ) null, resultSet,
916                 ClassName.NoPutResultSet, 10);
917     }
918
919     /**
920      * Generate the code to evaluate grouped aggregates.
921      *
922      */
923     private void genGroupedAggregateResultSet(ActivationClassBuilder acb,
924                                                    MethodBuilder mb)
925                 throws StandardException
926     {
927         /* Generate the (Distinct)GroupedAggregateResultSet:
928          * arg1: childExpress - Expression for childResult
929          * arg2: isInSortedOrder - true if source result set in sorted order
930          * arg3: aggregateItem - entry in saved objects for the aggregates,
931          * arg4: orderItem - entry in saved objects for the ordering
932          * arg5: Activation
933          * arg6: rowAllocator - method to construct rows for fetching
934          * from the sort
935          * arg7: row size
936          * arg8: resultSetNumber
937          */
938         String resultSet = (addDistinctAggregate) ? "getDistinctGroupedAggregateResultSet" : "getGroupedAggregateResultSet";
939     
940         mb.push(costEstimate.rowCount());
941         mb.push(costEstimate.getEstimatedCost());
942
943         mb.callMethod(VMOpcode.INVOKEINTERFACE, (String ) null, resultSet,
944                 ClassName.NoPutResultSet, 9);
945
946     }
947
948     ///////////////////////////////////////////////////////////////
949 //
950 // UTILITIES
951 //
952 ///////////////////////////////////////////////////////////////
953 /**
954      * Method for creating a new result column referencing
955      * the one passed in.
956      *
957      * @param targetRC the source
958      * @param dd
959      *
960      * @return the new result column
961      *
962      * @exception StandardException on error
963      */
964     private ResultColumn getColumnReference(ResultColumn targetRC,
965                                 DataDictionary dd)
966         throws StandardException
967     {
968         ColumnReference tmpColumnRef;
969         ResultColumn newRC;
970     
971         tmpColumnRef = (ColumnReference) getNodeFactory().getNode(
972                                             C_NodeTypes.COLUMN_REFERENCE,
973                                             targetRC.getName(),
974                                             null,
975                                             getContextManager());
976         tmpColumnRef.setSource(targetRC);
977         tmpColumnRef.setType(targetRC.getExpressionType());
978         tmpColumnRef.setNestingLevel(this.getLevel());
979         tmpColumnRef.setSourceLevel(this.getLevel());
980         newRC = (ResultColumn) getNodeFactory().getNode(
981                                     C_NodeTypes.RESULT_COLUMN,
982                                     targetRC.getColumnName(),
983                                     tmpColumnRef,
984                                     getContextManager());
985         newRC.markGenerated();
986         newRC.bindResultColumnToExpression();
987         return newRC;
988     }
989
990     /**
991      * Consider any optimizations after the optimizer has chosen a plan.
992      * Optimizations include:
993      * o min optimization for scalar aggregates
994      * o max optimization for scalar aggregates
995      *
996      * @param selectHasPredicates true if SELECT containing this
997      * vector/scalar aggregate has a restriction
998      *
999      * @exception StandardException on error
1000     */
1001    void considerPostOptimizeOptimizations(boolean selectHasPredicates)
1002        throws StandardException
1003    {
1004        /* Consider the optimization for min with asc index on that column or
1005         * max with desc index on that column:
1006         * o No group by
1007         * o One of:
1008         * o min/max(ColumnReference) is only aggregate && source is
1009         * ordered on the ColumnReference
1010         * o min/max(ConstantNode)
1011         * The optimization of the other way around (min with desc index or
1012         * max with asc index) has the same restrictions with the additional
1013         * temporary restriction of no qualifications at all (because
1014         * we don't have true backward scans).
1015         */
1016        if (groupingList == null)
1017        {
1018            if (aggregateVector.size() == 1)
1019            {
1020                AggregateNode an = (AggregateNode) aggregateVector.elementAt(0);
1021                AggregateDefinition ad = an.getAggregateDefinition();
1022                if (ad instanceof MaxMinAggregateDefinition)
1023                {
1024                    if (an.getOperand() instanceof ColumnReference)
1025                    {
1026                        /* See if the underlying ResultSet tree
1027                         * is ordered on the ColumnReference.
1028                         */
1029                        ColumnReference[] crs = new ColumnReference[1];
1030                        crs[0] = (ColumnReference) an.getOperand();
1031                        
1032                        Vector tableVector = new Vector ();
1033                        boolean minMaxOptimizationPossible = isOrderedOn(crs, false, tableVector);
1034                        if (SanityManager.DEBUG)
1035                        {
1036                            SanityManager.ASSERT(tableVector.size() <= 1, "bad number of FromBaseTables returned by isOrderedOn() -- "+tableVector.size());
1037                        }
1038
1039                        if (minMaxOptimizationPossible)
1040                        {
1041                            boolean ascIndex = true;
1042                            int colNum = crs[0].getColumnNumber();
1043                            
1044                            /* Check if we have an access path, this will be
1045                             * null in a join case (See Beetle 4423)
1046                             */
1047                            AccessPath accessPath= getTrulyTheBestAccessPath();
1048                            if (accessPath == null)
1049                                return;
1050                            IndexDescriptor id = accessPath.
1051                                                getConglomerateDescriptor().
1052                                                getIndexDescriptor();
1053                            int[] keyColumns = id.baseColumnPositions();
1054                            boolean[] isAscending = id.isAscending();
1055                            for (int i = 0; i < keyColumns.length; i++)
1056                            {
1057                                /* in such a query: select min(c3) from
1058                                 * tab1 where c1 = 2 and c2 = 5, if prefix keys
1059                                 * have equality operator, then we can still use
1060                                 * the index. The checking of equality operator
1061                                 * has been done in isStrictlyOrderedOn.
1062                                 */
1063                                if (colNum == keyColumns[i])
1064                                {
1065                                    if (! isAscending[i])
1066                                        ascIndex = false;
1067                                    break;
1068                                }
1069                            }
1070                            FromBaseTable fbt = (FromBaseTable)tableVector.firstElement();
1071                            MaxMinAggregateDefinition temp = (MaxMinAggregateDefinition)ad;
1072
1073                            /* MAX ASC NULLABLE
1074                             * ---- ----------
1075                             * TRUE TRUE TRUE/FALSE = Special Last Key Scan (ASC Index Last key with null skips)
1076                             * TRUE FALSE TRUE/FALSE = JustDisableBulk(DESC index 1st key with null skips)
1077                             * FALSE TRUE TRUE/FALSE = JustDisableBulk(ASC index 1st key)
1078                             * FALSE FALSE TRUE/FALSE = Special Last Key Scan(Desc Index Last Key)
1079                             */
1080
1081                            if (((!temp.isMax()) && ascIndex) ||
1082                                ((temp.isMax()) && !ascIndex))
1083                            {
1084                                fbt.disableBulkFetch();
1085                                singleInputRowOptimization = true;
1086                            }
1087                            /*
1088                            ** Max optimization with asc index or min with
1089                            ** desc index is currently more
1090                            ** restrictive than otherwise.
1091                            ** We are getting the store to return the last
1092                            ** row from an index (for the time being, the
1093                            ** store cannot do real backward scans). SO
1094                            ** we cannot do this optimization if we have
1095                            ** any predicates at all.
1096                            */
1097                            else if (!selectHasPredicates &&
1098                                     ((temp.isMax() && ascIndex) ||
1099                                      (!temp.isMax() && !ascIndex )))
1100                            {
1101                                fbt.disableBulkFetch();
1102                                fbt.doSpecialMaxScan();
1103                                singleInputRowOptimization = true;
1104                            }
1105                        }
1106                    }
1107                    else if (an.getOperand() instanceof ConstantNode)
1108                    {
1109                        singleInputRowOptimization = true;
1110                    }
1111                }
1112            }
1113        }
1114    }
1115}
1116

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags