0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.sql.compile.GroupByNode
0004:
0005: Licensed to the Apache Software Foundation (ASF) under one or more
0006: contributor license agreements. See the NOTICE file distributed with
0007: this work for additional information regarding copyright ownership.
0008: The ASF licenses this file to you under the Apache License, Version 2.0
0009: (the "License"); you may not use this file except in compliance with
0010: the License. You may obtain a copy of the License at
0011:
0012: http://www.apache.org/licenses/LICENSE-2.0
0013:
0014: Unless required by applicable law or agreed to in writing, software
0015: distributed under the License is distributed on an "AS IS" BASIS,
0016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0017: See the License for the specific language governing permissions and
0018: limitations under the License.
0019:
0020: */
0021:
0022: package org.apache.derby.impl.sql.compile;
0023:
0024: import org.apache.derby.iapi.services.context.ContextManager;
0025:
0026: import org.apache.derby.iapi.store.access.ColumnOrdering;
0027:
0028: import org.apache.derby.iapi.sql.compile.AccessPath;
0029: import org.apache.derby.iapi.sql.compile.Optimizable;
0030: import org.apache.derby.iapi.sql.compile.OptimizableList;
0031: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
0032: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
0033: import org.apache.derby.iapi.sql.compile.Optimizer;
0034: import org.apache.derby.iapi.sql.compile.CostEstimate;
0035: import org.apache.derby.iapi.sql.compile.Visitable;
0036: import org.apache.derby.iapi.sql.compile.Visitor;
0037: import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
0038: import org.apache.derby.iapi.sql.compile.RowOrdering;
0039: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
0040:
0041: import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
0042: import org.apache.derby.iapi.reference.ClassName;
0043:
0044: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
0045: import org.apache.derby.iapi.sql.dictionary.DataDictionaryContext;
0046: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
0047: import org.apache.derby.catalog.IndexDescriptor;
0048:
0049: import org.apache.derby.iapi.sql.execute.ExecutionContext;
0050:
0051: import org.apache.derby.iapi.sql.Activation;
0052: import org.apache.derby.iapi.sql.LanguageFactory;
0053: import org.apache.derby.iapi.sql.ResultColumnDescriptor;
0054: import org.apache.derby.iapi.sql.ResultSet;
0055:
0056: import org.apache.derby.iapi.error.StandardException;
0057:
0058: import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
0059: import org.apache.derby.impl.sql.execute.AggregatorInfo;
0060: import org.apache.derby.impl.sql.execute.AggregatorInfoList;
0061:
0062: import org.apache.derby.iapi.services.compiler.MethodBuilder;
0063:
0064: import org.apache.derby.iapi.services.sanity.SanityManager;
0065:
0066: import org.apache.derby.iapi.services.io.FormatableArrayHolder;
0067: import org.apache.derby.iapi.util.JBitSet;
0068:
0069: import org.apache.derby.impl.sql.compile.MaxMinAggregateDefinition;
0070: import org.apache.derby.iapi.services.classfile.VMOpcode;
0071:
0072: import java.util.Vector;
0073: import java.util.Properties;
0074:
0075: /**
0076: * A GroupByNode represents a result set for a grouping operation
0077: * on a select. Note that this includes a SELECT with aggregates
0078: * and no grouping columns (in which case the select list is null)
0079: * It has the same description as its input result set.
0080: * <p>
0081: * For the most part, it simply delegates operations to its bottomPRSet,
0082: * which is currently expected to be a ProjectRestrictResultSet generated
0083: * for a SelectNode.
0084: * <p>
0085: * NOTE: A GroupByNode extends FromTable since it can exist in a FromList.
0086: * <p>
0087: * There is a lot of room for optimizations here: <UL>
0088: * <LI> agg(distinct x) group by x => agg(x) group by x (for min and max) </LI>
0089: * <LI> min()/max() use index scans if possible, no sort may
0090: * be needed. </LI>
0091: * </UL>
0092: *
0093: * @author jerry, aggregates by jamie
0094: *
0095: */
0096: public class GroupByNode extends SingleChildResultSetNode {
0097: /**
0098: * The GROUP BY list
0099: */
0100: GroupByList groupingList;
0101:
0102: /**
0103: * The list of all aggregates in the query block
0104: * that contains this group by.
0105: */
0106: Vector aggregateVector;
0107:
0108: /**
0109: * Information that is used at execution time to
0110: * process aggregates.
0111: */
0112: private AggregatorInfoList aggInfo;
0113:
0114: /**
0115: * The parent to the GroupByNode. If we need to
0116: * generate a ProjectRestrict over the group by
0117: * then this is set to that node. Otherwise it
0118: * is null.
0119: */
0120: FromTable parent;
0121:
0122: private boolean addDistinctAggregate;
0123: private boolean singleInputRowOptimization;
0124: private int addDistinctAggregateColumnNum;
0125:
0126: // Is the source in sorted order
0127: private boolean isInSortedOrder;
0128:
0129: /**
0130: * Intializer for a GroupByNode.
0131: *
0132: * @param bottomPR The child FromTable
0133: * @param groupingList The groupingList
0134: * @param aggregateVector The vector of aggregates from
0135: * the query block. Since aggregation is done
0136: * at the same time as grouping, we need them
0137: * here.
0138: * @param tableProperties Properties list associated with the table
0139: *
0140: * @exception StandardException Thrown on error
0141: */
0142: public void init(Object bottomPR, Object groupingList,
0143: Object aggregateVector, Object tableProperties)
0144: throws StandardException {
0145: super .init(bottomPR, tableProperties);
0146:
0147: /* Group by without aggregates gets xformed into distinct */
0148: if (SanityManager.DEBUG) {
0149: SanityManager.ASSERT(((Vector) aggregateVector).size() > 0,
0150: "aggregateVector expected to be non-empty");
0151: if (!(childResult instanceof Optimizable)) {
0152: SanityManager.THROWASSERT("childResult, "
0153: + childResult.getClass().getName()
0154: + ", expected to be instanceof Optimizable");
0155: }
0156: if (!(childResult instanceof FromTable)) {
0157: SanityManager.THROWASSERT("childResult, "
0158: + childResult.getClass().getName()
0159: + ", expected to be instanceof FromTable");
0160: }
0161: }
0162:
0163: ResultColumnList newBottomRCL;
0164: this .groupingList = (GroupByList) groupingList;
0165: this .aggregateVector = (Vector) aggregateVector;
0166: this .parent = this ;
0167:
0168: /*
0169: ** The first thing we do is put ourselves on
0170: ** top of the SELECT. The select becomes the
0171: ** childResult. So our RCL becomes its RCL (so
0172: ** nodes above it now point to us). Map our
0173: ** RCL to its columns.
0174: */
0175: newBottomRCL = childResult.getResultColumns()
0176: .copyListAndObjects();
0177: resultColumns = childResult.getResultColumns();
0178: childResult.setResultColumns(newBottomRCL);
0179:
0180: /*
0181: ** We have aggregates, so we need to add
0182: ** an extra PRNode and we also have to muck around
0183: ** with our trees a might.
0184: */
0185: addAggregates();
0186:
0187: /* We say that the source is never in sorted order if there is a distinct aggregate.
0188: * (Not sure what happens if it is, so just skip it for now.)
0189: * Otherwise, we check to see if the source is in sorted order on any permutation
0190: * of the grouping columns.)
0191: */
0192: if (!addDistinctAggregate && groupingList != null) {
0193: ColumnReference[] crs = new ColumnReference[this .groupingList
0194: .size()];
0195:
0196: // Now populate the CR array and see if ordered
0197: int glSize = this .groupingList.size();
0198: int index;
0199: for (index = 0; index < glSize; index++) {
0200: GroupByColumn gc = (GroupByColumn) this .groupingList
0201: .elementAt(index);
0202: if (gc.getColumnExpression() instanceof ColumnReference) {
0203: crs[index] = (ColumnReference) gc
0204: .getColumnExpression();
0205: } else {
0206: isInSortedOrder = false;
0207: break;
0208: }
0209:
0210: }
0211: if (index == glSize) {
0212: isInSortedOrder = childResult.isOrderedOn(crs, true,
0213: (Vector) null);
0214: }
0215: }
0216: }
0217:
0218: /**
0219: * Get whether or not the source is in sorted order.
0220: *
0221: * @return Whether or not the source is in sorted order.
0222: */
0223: boolean getIsInSortedOrder() {
0224: return isInSortedOrder;
0225: }
0226:
0227: /**
0228: * Add the extra result columns required by the aggregates
0229: * to the result list.
0230: *
0231: * @exception standard exception
0232: */
0233: private void addAggregates() throws StandardException {
0234: addNewPRNode();
0235: addNewColumnsForAggregation();
0236: addDistinctAggregatesToOrderBy();
0237: }
0238:
0239: /**
0240: * Add any distinct aggregates to the order by list.
0241: * Asserts that there are 0 or more distincts.
0242: */
0243: private void addDistinctAggregatesToOrderBy() {
0244: int numDistinct = numDistinctAggregates(aggregateVector);
0245: if (numDistinct != 0) {
0246: if (SanityManager.DEBUG) {
0247: SanityManager
0248: .ASSERT(numDistinct == 1,
0249: "Should not have more than 1 distinct aggregate per Group By node");
0250: }
0251:
0252: AggregatorInfo agg = null;
0253: int count = aggInfo.size();
0254: for (int i = 0; i < count; i++) {
0255: agg = (AggregatorInfo) aggInfo.elementAt(i);
0256: if (agg.isDistinct()) {
0257: break;
0258: }
0259: }
0260:
0261: if (SanityManager.DEBUG) {
0262: SanityManager.ASSERT(agg != null && agg.isDistinct());
0263: }
0264:
0265: addDistinctAggregate = true;
0266: addDistinctAggregateColumnNum = agg.getInputColNum();
0267: }
0268: }
0269:
0270: /**
0271: * Add a new PR node for aggregation. Put the
0272: * new PR under the sort.
0273: *
0274: * @exception standard exception
0275: */
0276: private void addNewPRNode() throws StandardException {
0277: /*
0278: ** Get the new PR, put above the GroupBy.
0279: */
0280: parent = (FromTable) getNodeFactory().getNode(
0281: C_NodeTypes.PROJECT_RESTRICT_NODE, this , // child
0282: resultColumns, // result column list
0283: null, // restriction
0284: null, // restriction list
0285: null, // project subqueries
0286: null, // restrict subqueries
0287: tableProperties, getContextManager());
0288:
0289: /*
0290: ** Reset the bottom RCL to be empty.
0291: */
0292: childResult
0293: .setResultColumns((ResultColumnList) getNodeFactory()
0294: .getNode(C_NodeTypes.RESULT_COLUMN_LIST,
0295: getContextManager()));
0296:
0297: /*
0298: ** Set the group by RCL to be empty
0299: */
0300: resultColumns = (ResultColumnList) getNodeFactory().getNode(
0301: C_NodeTypes.RESULT_COLUMN_LIST, getContextManager());
0302:
0303: }
0304:
0305: /**
0306: * In the query rewrite for group by, add the columns on which
0307: * we are doing the group by.
0308:
0309: * @see #addNewColumnsForAggregation
0310: */
0311: private void addUnAggColumns() throws StandardException {
0312: ResultColumnList bottomRCL = childResult.getResultColumns();
0313: ResultColumnList groupByRCL = resultColumns;
0314:
0315: int sz = groupingList.size();
0316: for (int i = 0; i < sz; i++) {
0317: GroupByColumn gbc = (GroupByColumn) groupingList
0318: .elementAt(i);
0319: ResultColumn newRC = (ResultColumn) getNodeFactory()
0320: .getNode(C_NodeTypes.RESULT_COLUMN,
0321: "##UnaggColumn", gbc.getColumnExpression(),
0322: getContextManager());
0323:
0324: // add this result column to the bottom rcl
0325: bottomRCL.addElement(newRC);
0326: newRC.markGenerated();
0327: newRC.bindResultColumnToExpression();
0328: newRC.setVirtualColumnId(bottomRCL.size());
0329:
0330: // now add this column to the groupbylist
0331: ResultColumn gbRC = (ResultColumn) getNodeFactory()
0332: .getNode(C_NodeTypes.RESULT_COLUMN,
0333: "##UnaggColumn", gbc.getColumnExpression(),
0334: getContextManager());
0335: groupByRCL.addElement(gbRC);
0336: gbRC.markGenerated();
0337: gbRC.bindResultColumnToExpression();
0338: gbRC.setVirtualColumnId(groupByRCL.size());
0339:
0340: /*
0341: ** Reset the original node to point to the
0342: ** Group By result set.
0343: */
0344: VirtualColumnNode vc = (VirtualColumnNode) getNodeFactory()
0345: .getNode(C_NodeTypes.VIRTUAL_COLUMN_NODE,
0346: this , // source result set.
0347: gbRC, new Integer(groupByRCL.size()),
0348: getContextManager());
0349:
0350: // we replace each group by expression
0351: // in the projection list with a virtual column node
0352: // that effectively points to a result column
0353: // in the result set doing the group by
0354: SubstituteExpressionVisitor se = new SubstituteExpressionVisitor(
0355: gbc.getColumnExpression(), vc, AggregateNode.class);
0356: parent.getResultColumns().accept(se);
0357:
0358: // finally reset gbc to its new position.
0359: gbc.setColumnPosition(bottomRCL.size());
0360: }
0361: }
0362:
0363: /**
0364: * Add a whole slew of columns needed for
0365: * aggregation. Basically, for each aggregate we add
0366: * 2 columns: the aggregate input expression
0367: * and the aggregator column. The input expression is
0368: * taken directly from the aggregator node. The aggregator
0369: * is the run time aggregator. We add it to the RC list
0370: * as a new object coming into the sort node.
0371: * <P>
0372: * At this point this is invoked, we have the following
0373: * tree: <UL>
0374: * PR - (PARENT): RCL is the original select list
0375: * |
0376: * PR - GROUP BY: RCL is empty
0377: * |
0378: * PR - FROM TABLE: RCL is empty </UL> <P>
0379: *
0380: * For each ColumnReference in PR RCL <UL>
0381: * <LI> clone the ref </LI>
0382: * <LI> create a new RC in the bottom RCL and set it
0383: * to the col ref </LI>
0384: * <LI> create a new RC in the GROUPBY RCL and set it to
0385: * point to the bottom RC </LI>
0386: * <LI> reset the top PR ref to point to the new GROUPBY
0387: * RC
0388: *
0389: * For each aggregate in aggregateVector <UL>
0390: * <LI> create RC in FROM TABLE. Fill it with
0391: * aggs Operator.
0392: * <LI> create RC in FROM TABLE for agg result</LI>
0393: * <LI> create RC in FROM TABLE for aggregator</LI>
0394: * <LI> create RC in GROUPBY for agg input, set it
0395: * to point to FROM TABLE RC </LI>
0396: * <LI> create RC in GROUPBY for agg result</LI>
0397: * <LI> create RC in GROUPBY for aggregator</LI>
0398: * <LI> replace Agg with reference to RC for agg result </LI>
0399: *
0400: * @exception standard exception
0401: */
0402: private void addNewColumnsForAggregation() throws StandardException {
0403: aggInfo = new AggregatorInfoList();
0404: if (groupingList != null) {
0405: addUnAggColumns();
0406: }
0407: addAggregateColumns();
0408: }
0409:
0410: /**
0411: * In the query rewrite involving aggregates, add the columns for
0412: * aggregation.
0413: *
0414: * @see #addNewColumnsForAggregation
0415: */
0416: private void addAggregateColumns() throws StandardException {
0417: DataDictionary dd = getDataDictionary();
0418: AggregateNode aggregate = null;
0419: ColumnReference newColumnRef;
0420: ResultColumn newRC;
0421: ResultColumn tmpRC;
0422: ResultColumn aggInputRC;
0423: ResultColumnList bottomRCL = childResult.getResultColumns();
0424: ResultColumnList groupByRCL = resultColumns;
0425: ResultColumnList aggRCL;
0426: int aggregatorVColId;
0427: int aggInputVColId;
0428: int aggResultVColId;
0429:
0430: /*
0431: ** Now process all of the aggregates. Replace
0432: ** every aggregate with an RC. We toss out
0433: ** the list of RCs, we need to get each RC
0434: ** as we process its corresponding aggregate.
0435: */
0436: LanguageFactory lf = getLanguageConnectionContext()
0437: .getLanguageFactory();
0438:
0439: ReplaceAggregatesWithCRVisitor replaceAggsVisitor = new ReplaceAggregatesWithCRVisitor(
0440: (ResultColumnList) getNodeFactory().getNode(
0441: C_NodeTypes.RESULT_COLUMN_LIST,
0442: getContextManager()), ((FromTable) childResult)
0443: .getTableNumber());
0444: parent.getResultColumns().accept(replaceAggsVisitor);
0445:
0446: /*
0447: ** For each aggregate
0448: */
0449: int alSize = aggregateVector.size();
0450: for (int index = 0; index < alSize; index++) {
0451: aggregate = (AggregateNode) aggregateVector
0452: .elementAt(index);
0453:
0454: /*
0455: ** AGG RESULT: Set the aggregate result to null in the
0456: ** bottom project restrict.
0457: */
0458: newRC = (ResultColumn) getNodeFactory().getNode(
0459: C_NodeTypes.RESULT_COLUMN, "##aggregate result",
0460: aggregate.getNewNullResultExpression(),
0461: getContextManager());
0462: newRC.markGenerated();
0463: newRC.bindResultColumnToExpression();
0464: bottomRCL.addElement(newRC);
0465: newRC.setVirtualColumnId(bottomRCL.size());
0466: aggResultVColId = newRC.getVirtualColumnId();
0467:
0468: /*
0469: ** Set the GB aggregrate result column to
0470: ** point to this. The GB aggregate result
0471: ** was created when we called
0472: ** ReplaceAggregatesWithColumnReferencesVisitor()
0473: */
0474: newColumnRef = (ColumnReference) getNodeFactory().getNode(
0475: C_NodeTypes.COLUMN_REFERENCE, newRC.getName(),
0476: null, getContextManager());
0477: newColumnRef.setSource(newRC);
0478: newColumnRef.setType(newRC.getExpressionType());
0479: newColumnRef.setNestingLevel(this .getLevel());
0480: newColumnRef.setSourceLevel(this .getLevel());
0481: tmpRC = (ResultColumn) getNodeFactory().getNode(
0482: C_NodeTypes.RESULT_COLUMN, newRC.getColumnName(),
0483: newColumnRef, getContextManager());
0484: tmpRC.markGenerated();
0485: tmpRC.bindResultColumnToExpression();
0486: groupByRCL.addElement(tmpRC);
0487: tmpRC.setVirtualColumnId(groupByRCL.size());
0488:
0489: /*
0490: ** Set the column reference to point to
0491: ** this.
0492: */
0493: newColumnRef = aggregate.getGeneratedRef();
0494: newColumnRef.setSource(tmpRC);
0495:
0496: /*
0497: ** AGG INPUT: Create a ResultColumn in the bottom
0498: ** project restrict that has the expression that is
0499: ** to be aggregated
0500: */
0501: newRC = aggregate.getNewExpressionResultColumn(dd);
0502: newRC.markGenerated();
0503: newRC.bindResultColumnToExpression();
0504: bottomRCL.addElement(newRC);
0505: newRC.setVirtualColumnId(bottomRCL.size());
0506: aggInputVColId = newRC.getVirtualColumnId();
0507: aggInputRC = newRC;
0508:
0509: /*
0510: ** Add a reference to this column into the
0511: ** group by columns.
0512: */
0513: tmpRC = getColumnReference(newRC, dd);
0514: groupByRCL.addElement(tmpRC);
0515: tmpRC.setVirtualColumnId(groupByRCL.size());
0516:
0517: /*
0518: ** AGGREGATOR: Add a getAggregator method call
0519: ** to the bottom result column list.
0520: */
0521: newRC = aggregate.getNewAggregatorResultColumn(dd);
0522: newRC.markGenerated();
0523: newRC.bindResultColumnToExpression();
0524: bottomRCL.addElement(newRC);
0525: newRC.setVirtualColumnId(bottomRCL.size());
0526: aggregatorVColId = newRC.getVirtualColumnId();
0527:
0528: /*
0529: ** Add a reference to this column in the Group By result
0530: ** set.
0531: */
0532: tmpRC = getColumnReference(newRC, dd);
0533: groupByRCL.addElement(tmpRC);
0534: tmpRC.setVirtualColumnId(groupByRCL.size());
0535:
0536: /*
0537: ** Piece together a fake one column rcl that we will use
0538: ** to generate a proper result description for input
0539: ** to this agg if it is a user agg.
0540: */
0541: aggRCL = (ResultColumnList) getNodeFactory()
0542: .getNode(C_NodeTypes.RESULT_COLUMN_LIST,
0543: getContextManager());
0544: aggRCL.addElement(aggInputRC);
0545:
0546: /*
0547: ** Note that the column ids in the row are 0 based
0548: ** so we have to subtract 1.
0549: */
0550: aggInfo.addElement(new AggregatorInfo(aggregate
0551: .getAggregateName(), aggregate
0552: .getAggregatorClassName(), aggInputVColId - 1, // aggregate input column
0553: aggResultVColId - 1, // the aggregate result column
0554: aggregatorVColId - 1, // the aggregator column
0555: aggregate.isDistinct(), lf.getResultDescription(
0556: aggRCL.makeResultDescriptors(), "SELECT")));
0557: }
0558: }
0559:
0560: /**
0561: * Return the parent node to this one, if there is
0562: * one. It will return 'this' if there is no generated
0563: * node above this one.
0564: *
0565: * @return the parent node
0566: */
0567: public FromTable getParent() {
0568: return parent;
0569: }
0570:
0571: /*
0572: * Optimizable interface
0573: */
0574:
0575: /**
0576: * @see Optimizable#optimizeIt
0577: *
0578: * @exception StandardException Thrown on error
0579: */
0580: public CostEstimate optimizeIt(Optimizer optimizer,
0581: OptimizablePredicateList predList, CostEstimate outerCost,
0582: RowOrdering rowOrdering) throws StandardException {
0583: // RESOLVE: NEED TO FACTOR IN THE COST OF GROUPING (SORTING) HERE
0584: CostEstimate childCost = ((Optimizable) childResult)
0585: .optimizeIt(optimizer, predList, outerCost, rowOrdering);
0586:
0587: CostEstimate retval = super .optimizeIt(optimizer, predList,
0588: outerCost, rowOrdering);
0589:
0590: return retval;
0591: }
0592:
0593: /**
0594: * @see Optimizable#estimateCost
0595: *
0596: * @exception StandardException Thrown on error
0597: */
0598: public CostEstimate estimateCost(OptimizablePredicateList predList,
0599: ConglomerateDescriptor cd, CostEstimate outerCost,
0600: Optimizer optimizer, RowOrdering rowOrdering)
0601: throws StandardException {
0602: // RESOLVE: NEED TO FACTOR IN THE COST OF GROUPING (SORTING) HERE
0603: //
0604: CostEstimate childCost = ((Optimizable) childResult)
0605: .estimateCost(predList, cd, outerCost, optimizer,
0606: rowOrdering);
0607:
0608: CostEstimate costEstimate = getCostEstimate(optimizer);
0609: costEstimate.setCost(childCost.getEstimatedCost(), childCost
0610: .rowCount(), childCost.singleScanRowCount());
0611:
0612: return costEstimate;
0613: }
0614:
0615: /**
0616: * @see org.apache.derby.iapi.sql.compile.Optimizable#pushOptPredicate
0617: *
0618: * @exception StandardException Thrown on error
0619: */
0620:
0621: public boolean pushOptPredicate(
0622: OptimizablePredicate optimizablePredicate)
0623: throws StandardException {
0624: return ((Optimizable) childResult)
0625: .pushOptPredicate(optimizablePredicate);
0626: }
0627:
0628: /**
0629: * Convert this object to a String. See comments in QueryTreeNode.java
0630: * for how this should be done for tree printing.
0631: *
0632: * @return This object as a String
0633: */
0634:
0635: public String toString() {
0636: if (SanityManager.DEBUG) {
0637: return "singleInputRowOptimization: "
0638: + singleInputRowOptimization + "\n"
0639: + childResult.toString() + "\n" + super .toString();
0640: } else {
0641: return "";
0642: }
0643: }
0644:
0645: /**
0646: * Evaluate whether or not the subquery in a FromSubquery is flattenable.
0647: * Currently, a FSqry is flattenable if all of the following are true:
0648: * o Subquery is a SelectNode.
0649: * o It contains no top level subqueries. (RESOLVE - we can relax this)
0650: * o It does not contain a group by or having clause
0651: * o It does not contain aggregates.
0652: *
0653: * @param fromList The outer from list
0654: *
0655: * @return boolean Whether or not the FromSubquery is flattenable.
0656: */
0657: public boolean flattenableInFromSubquery(FromList fromList) {
0658: /* Can't flatten a GroupByNode */
0659: return false;
0660: }
0661:
0662: /**
0663: * Optimize this GroupByNode.
0664: *
0665: * @param dataDictionary The DataDictionary to use for optimization
0666: * @param predicates The PredicateList to optimize. This should
0667: * be a join predicate.
0668: * @param outerRows The number of outer joining rows
0669: *
0670: * @return ResultSetNode The top of the optimized subtree
0671: *
0672: * @exception StandardException Thrown on error
0673: */
0674:
0675: public ResultSetNode optimize(DataDictionary dataDictionary,
0676: PredicateList predicates, double outerRows)
0677: throws StandardException {
0678: /* We need to implement this method since a PRN can appear above a
0679: * SelectNode in a query tree.
0680: */
0681: childResult = (FromTable) childResult.optimize(dataDictionary,
0682: predicates, outerRows);
0683: Optimizer optimizer = getOptimizer((FromList) getNodeFactory()
0684: .getNode(C_NodeTypes.FROM_LIST,
0685: getNodeFactory().doJoinOrderOptimization(),
0686: getContextManager()), predicates,
0687: dataDictionary, (RequiredRowOrdering) null);
0688:
0689: // RESOLVE: NEED TO FACTOR IN COST OF SORTING AND FIGURE OUT HOW
0690: // MANY ROWS HAVE BEEN ELIMINATED.
0691: costEstimate = optimizer.newCostEstimate();
0692:
0693: costEstimate.setCost(childResult.getCostEstimate()
0694: .getEstimatedCost(), childResult.getCostEstimate()
0695: .rowCount(), childResult.getCostEstimate()
0696: .singleScanRowCount());
0697:
0698: return this ;
0699: }
0700:
0701: ResultColumnDescriptor[] makeResultDescriptors(ExecutionContext ec) {
0702: return childResult.makeResultDescriptors(ec);
0703: }
0704:
0705: /**
0706: * Return whether or not the underlying ResultSet tree will return
0707: * a single row, at most.
0708: * This is important for join nodes where we can save the extra next
0709: * on the right side if we know that it will return at most 1 row.
0710: *
0711: * @return Whether or not the underlying ResultSet tree will return a single row.
0712: * @exception StandardException Thrown on error
0713: */
0714: public boolean isOneRowResultSet() throws StandardException {
0715: // Only consider scalar aggregates for now
0716: return ((groupingList == null) || (groupingList.size() == 0));
0717: }
0718:
0719: /**
0720: * generate the sort result set operating over the source
0721: * resultset. Adds distinct aggregates to the sort if
0722: * necessary.
0723: *
0724: * @exception StandardException Thrown on error
0725: */
0726: public void generate(ActivationClassBuilder acb, MethodBuilder mb)
0727: throws StandardException {
0728: int orderingItem = 0;
0729: int aggInfoItem = 0;
0730: FormatableArrayHolder orderingHolder;
0731:
0732: /* Get the next ResultSet#, so we can number this ResultSetNode, its
0733: * ResultColumnList and ResultSet.
0734: */
0735: assignResultSetNumber();
0736:
0737: // Get the final cost estimate from the child.
0738: costEstimate = childResult.getFinalCostEstimate();
0739:
0740: /*
0741: ** Get the column ordering for the sort. Note that
0742: ** for a scalar aggegate we may not have any ordering
0743: ** columns (if there are no distinct aggregates).
0744: ** WARNING: if a distinct aggregate is passed to
0745: ** SortResultSet it assumes that the last column
0746: ** is the distinct one. If this assumption changes
0747: ** then SortResultSet will have to change.
0748: */
0749: orderingHolder = acb.getColumnOrdering(groupingList);
0750: if (addDistinctAggregate) {
0751: orderingHolder = acb.addColumnToOrdering(orderingHolder,
0752: addDistinctAggregateColumnNum);
0753: }
0754:
0755: if (SanityManager.DEBUG) {
0756: if (SanityManager.DEBUG_ON("AggregateTrace")) {
0757: StringBuffer s = new StringBuffer();
0758:
0759: s.append("Group by column ordering is (");
0760: ColumnOrdering[] ordering = (ColumnOrdering[]) orderingHolder
0761: .getArray(ColumnOrdering.class);
0762:
0763: for (int i = 0; i < ordering.length; i++) {
0764: s.append(ordering[i].getColumnId());
0765: s.append(" ");
0766: }
0767: s.append(")");
0768: SanityManager.DEBUG("AggregateTrace", s.toString());
0769: }
0770: }
0771:
0772: orderingItem = acb.addItem(orderingHolder);
0773:
0774: /*
0775: ** We have aggregates, so save the aggInfo
0776: ** struct in the activation and store the number
0777: */
0778: if (SanityManager.DEBUG) {
0779: SanityManager.ASSERT(aggInfo != null,
0780: "aggInfo not set up as expected");
0781: }
0782: aggInfoItem = acb.addItem(aggInfo);
0783:
0784: acb.pushGetResultSetFactoryExpression(mb);
0785:
0786: // Generate the child ResultSet
0787: childResult.generate(acb, mb);
0788: mb.push(isInSortedOrder);
0789: mb.push(aggInfoItem);
0790: mb.push(orderingItem);
0791:
0792: resultColumns.generateHolder(acb, mb);
0793:
0794: mb.push(resultColumns.getTotalColumnSize());
0795: mb.push(resultSetNumber);
0796:
0797: /* Generate a (Distinct)ScalarAggregateResultSet if scalar aggregates */
0798: if ((groupingList == null) || (groupingList.size() == 0)) {
0799: genScalarAggregateResultSet(acb, mb);
0800: }
0801: /* Generate a (Distinct)GroupedAggregateResultSet if grouped aggregates */
0802: else {
0803: genGroupedAggregateResultSet(acb, mb);
0804: }
0805: }
0806:
0807: /**
0808: * Generate the code to evaluate scalar aggregates.
0809: *
0810: */
0811: private void genScalarAggregateResultSet(
0812: ActivationClassBuilder acb, MethodBuilder mb) {
0813: /* Generate the (Distinct)ScalarAggregateResultSet:
0814: * arg1: childExpress - Expression for childResult
0815: * arg2: isInSortedOrder - true if source result set in sorted order
0816: * arg3: aggregateItem - entry in saved objects for the aggregates,
0817: * arg4: orderItem - entry in saved objects for the ordering
0818: * arg5: Activation
0819: * arg6: rowAllocator - method to construct rows for fetching
0820: * from the sort
0821: * arg7: row size
0822: * arg8: resultSetNumber
0823: * arg9: Whether or not to perform min optimization.
0824: */
0825: String resultSet = (addDistinctAggregate) ? "getDistinctScalarAggregateResultSet"
0826: : "getScalarAggregateResultSet";
0827:
0828: mb.push(singleInputRowOptimization);
0829: mb.push(costEstimate.rowCount());
0830: mb.push(costEstimate.getEstimatedCost());
0831:
0832: mb.callMethod(VMOpcode.INVOKEINTERFACE, (String) null,
0833: resultSet, ClassName.NoPutResultSet, 10);
0834: }
0835:
0836: /**
0837: * Generate the code to evaluate grouped aggregates.
0838: *
0839: */
0840: private void genGroupedAggregateResultSet(
0841: ActivationClassBuilder acb, MethodBuilder mb)
0842: throws StandardException {
0843: /* Generate the (Distinct)GroupedAggregateResultSet:
0844: * arg1: childExpress - Expression for childResult
0845: * arg2: isInSortedOrder - true if source result set in sorted order
0846: * arg3: aggregateItem - entry in saved objects for the aggregates,
0847: * arg4: orderItem - entry in saved objects for the ordering
0848: * arg5: Activation
0849: * arg6: rowAllocator - method to construct rows for fetching
0850: * from the sort
0851: * arg7: row size
0852: * arg8: resultSetNumber
0853: */
0854: String resultSet = (addDistinctAggregate) ? "getDistinctGroupedAggregateResultSet"
0855: : "getGroupedAggregateResultSet";
0856:
0857: mb.push(costEstimate.rowCount());
0858: mb.push(costEstimate.getEstimatedCost());
0859:
0860: mb.callMethod(VMOpcode.INVOKEINTERFACE, (String) null,
0861: resultSet, ClassName.NoPutResultSet, 9);
0862:
0863: }
0864:
0865: ///////////////////////////////////////////////////////////////
0866: //
0867: // UTILITIES
0868: //
0869: ///////////////////////////////////////////////////////////////
0870: /**
0871: * Method for creating a new result column referencing
0872: * the one passed in.
0873: *
0874: * @param targetRC the source
0875: * @param dd
0876: *
0877: * @return the new result column
0878: *
0879: * @exception StandardException on error
0880: */
0881: private ResultColumn getColumnReference(ResultColumn targetRC,
0882: DataDictionary dd) throws StandardException {
0883: ColumnReference tmpColumnRef;
0884: ResultColumn newRC;
0885:
0886: tmpColumnRef = (ColumnReference) getNodeFactory().getNode(
0887: C_NodeTypes.COLUMN_REFERENCE, targetRC.getName(), null,
0888: getContextManager());
0889: tmpColumnRef.setSource(targetRC);
0890: tmpColumnRef.setType(targetRC.getExpressionType());
0891: tmpColumnRef.setNestingLevel(this .getLevel());
0892: tmpColumnRef.setSourceLevel(this .getLevel());
0893: newRC = (ResultColumn) getNodeFactory().getNode(
0894: C_NodeTypes.RESULT_COLUMN, targetRC.getColumnName(),
0895: tmpColumnRef, getContextManager());
0896: newRC.markGenerated();
0897: newRC.bindResultColumnToExpression();
0898: return newRC;
0899: }
0900:
0901: /**
0902: * Consider any optimizations after the optimizer has chosen a plan.
0903: * Optimizations include:
0904: * o min optimization for scalar aggregates
0905: * o max optimization for scalar aggregates
0906: *
0907: * @param selectHasPredicates true if SELECT containing this
0908: * vector/scalar aggregate has a restriction
0909: *
0910: * @exception StandardException on error
0911: */
0912: void considerPostOptimizeOptimizations(boolean selectHasPredicates)
0913: throws StandardException {
0914: /* Consider the optimization for min with asc index on that column or
0915: * max with desc index on that column:
0916: * o No group by
0917: * o One of:
0918: * o min/max(ColumnReference) is only aggregate && source is
0919: * ordered on the ColumnReference
0920: * o min/max(ConstantNode)
0921: * The optimization of the other way around (min with desc index or
0922: * max with asc index) has the same restrictions with the additional
0923: * temporary restriction of no qualifications at all (because
0924: * we don't have true backward scans).
0925: */
0926: if (groupingList == null) {
0927: if (aggregateVector.size() == 1) {
0928: AggregateNode an = (AggregateNode) aggregateVector
0929: .elementAt(0);
0930: AggregateDefinition ad = an.getAggregateDefinition();
0931: if (ad instanceof MaxMinAggregateDefinition) {
0932: if (an.getOperand() instanceof ColumnReference) {
0933: /* See if the underlying ResultSet tree
0934: * is ordered on the ColumnReference.
0935: */
0936: ColumnReference[] crs = new ColumnReference[1];
0937: crs[0] = (ColumnReference) an.getOperand();
0938:
0939: Vector tableVector = new Vector();
0940: boolean minMaxOptimizationPossible = isOrderedOn(
0941: crs, false, tableVector);
0942: if (SanityManager.DEBUG) {
0943: SanityManager.ASSERT(
0944: tableVector.size() <= 1,
0945: "bad number of FromBaseTables returned by isOrderedOn() -- "
0946: + tableVector.size());
0947: }
0948:
0949: if (minMaxOptimizationPossible) {
0950: boolean ascIndex = true;
0951: int colNum = crs[0].getColumnNumber();
0952:
0953: /* Check if we have an access path, this will be
0954: * null in a join case (See Beetle 4423)
0955: */
0956: AccessPath accessPath = getTrulyTheBestAccessPath();
0957: if (accessPath == null)
0958: return;
0959: IndexDescriptor id = accessPath
0960: .getConglomerateDescriptor()
0961: .getIndexDescriptor();
0962: int[] keyColumns = id.baseColumnPositions();
0963: boolean[] isAscending = id.isAscending();
0964: for (int i = 0; i < keyColumns.length; i++) {
0965: /* in such a query: select min(c3) from
0966: * tab1 where c1 = 2 and c2 = 5, if prefix keys
0967: * have equality operator, then we can still use
0968: * the index. The checking of equality operator
0969: * has been done in isStrictlyOrderedOn.
0970: */
0971: if (colNum == keyColumns[i]) {
0972: if (!isAscending[i])
0973: ascIndex = false;
0974: break;
0975: }
0976: }
0977: FromBaseTable fbt = (FromBaseTable) tableVector
0978: .firstElement();
0979: MaxMinAggregateDefinition temp = (MaxMinAggregateDefinition) ad;
0980:
0981: /* MAX ASC NULLABLE
0982: * ---- ----------
0983: * TRUE TRUE TRUE/FALSE = Special Last Key Scan (ASC Index Last key with null skips)
0984: * TRUE FALSE TRUE/FALSE = JustDisableBulk(DESC index 1st key with null skips)
0985: * FALSE TRUE TRUE/FALSE = JustDisableBulk(ASC index 1st key)
0986: * FALSE FALSE TRUE/FALSE = Special Last Key Scan(Desc Index Last Key)
0987: */
0988:
0989: if (((!temp.isMax()) && ascIndex)
0990: || ((temp.isMax()) && !ascIndex)) {
0991: fbt.disableBulkFetch();
0992: singleInputRowOptimization = true;
0993: }
0994: /*
0995: ** Max optimization with asc index or min with
0996: ** desc index is currently more
0997: ** restrictive than otherwise.
0998: ** We are getting the store to return the last
0999: ** row from an index (for the time being, the
1000: ** store cannot do real backward scans). SO
1001: ** we cannot do this optimization if we have
1002: ** any predicates at all.
1003: */
1004: else if (!selectHasPredicates
1005: && ((temp.isMax() && ascIndex) || (!temp
1006: .isMax() && !ascIndex))) {
1007: fbt.disableBulkFetch();
1008: fbt.doSpecialMaxScan();
1009: singleInputRowOptimization = true;
1010: }
1011: }
1012: } else if (an.getOperand() instanceof ConstantNode) {
1013: singleInputRowOptimization = true;
1014: }
1015: }
1016: }
1017: }
1018: }
1019: }
|