groupbynode.java

derby database source code.good for you.

/*

   Derby - Class org.apache.derby.impl.sql.compile.GroupByNode

   Copyright 1998, 2004 The Apache Software Foundation or its licensors, as applicable.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

 */

package	org.apache.derby.impl.sql.compile;

import org.apache.derby.iapi.services.context.ContextManager;

import org.apache.derby.iapi.store.access.ColumnOrdering;

import org.apache.derby.iapi.sql.compile.AccessPath;
import org.apache.derby.iapi.sql.compile.Optimizable;
import org.apache.derby.iapi.sql.compile.OptimizableList;
import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
import org.apache.derby.iapi.sql.compile.Optimizer;
import org.apache.derby.iapi.sql.compile.CostEstimate;
import org.apache.derby.iapi.sql.compile.Visitable;
import org.apache.derby.iapi.sql.compile.Visitor;
import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
import org.apache.derby.iapi.sql.compile.RowOrdering;
import org.apache.derby.iapi.sql.compile.C_NodeTypes;

import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
import org.apache.derby.iapi.reference.ClassName;

import org.apache.derby.iapi.sql.dictionary.DataDictionary;
import org.apache.derby.iapi.sql.dictionary.DataDictionaryContext;
import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
import org.apache.derby.catalog.IndexDescriptor;

import org.apache.derby.iapi.sql.execute.ExecutionContext;

import org.apache.derby.iapi.sql.Activation; 
import org.apache.derby.iapi.sql.LanguageFactory;
import org.apache.derby.iapi.sql.ResultColumnDescriptor;
import org.apache.derby.iapi.sql.ResultSet;

import org.apache.derby.iapi.error.StandardException;

import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
import org.apache.derby.impl.sql.execute.AggregatorInfo;
import org.apache.derby.impl.sql.execute.AggregatorInfoList;

import org.apache.derby.iapi.services.compiler.MethodBuilder;

import org.apache.derby.iapi.services.sanity.SanityManager;

import org.apache.derby.iapi.services.io.FormatableArrayHolder;
import org.apache.derby.iapi.util.JBitSet;

import org.apache.derby.impl.sql.compile.MaxMinAggregateDefinition;
import org.apache.derby.iapi.services.classfile.VMOpcode;

import java.util.Vector;
import java.util.Properties;


/**
 * A GroupByNode represents a result set for a grouping operation
 * on a select.  Note that this includes a SELECT with aggregates
 * and no grouping columns (in which case the select list is null)
 * It has the same description as its input result set.
 * <p>
 * For the most part, it simply delegates operations to its bottomPRSet,
 * which is currently expected to be a ProjectRestrictResultSet generated
 * for a SelectNode.
 * <p>
 * NOTE: A GroupByNode extends FromTable since it can exist in a FromList.
 * <p>
 * There is a lot of room for optimizations here: <UL>
 * <LI> agg(distinct x) group by x => agg(x) group by x (for min and max) </LI>
 * <LI> min()/max() use index scans if possible, no sort may 
 *		be needed. </LI>
 * </UL>
 *
 * @author jerry, aggregates by jamie
 *
 */
public class GroupByNode extends SingleChildResultSetNode
{
	/**
	 * The GROUP BY list
	 */
	GroupByList groupingList;

	/**
	 * The list of all aggregates in the query block
	 * that contains this group by.
	 */
	Vector	aggregateVector;

	/**
	 * Information that is used at execution time to
	 * process aggregates.
	 */
	private AggregatorInfoList	aggInfo;

	/**
	 * The parent to the GroupByNode.  If we need to
	 * generate a ProjectRestrict over the group by
	 * then this is set to that node.  Otherwise it
	 * is null.
	 */
	FromTable	parent;

	private boolean	addDistinctAggregate;
	private boolean singleInputRowOptimization;
	private int		addDistinctAggregateColumnNum;

	// Is the source in sorted order
	private boolean isInSortedOrder;

	/**
	 * Intializer for a GroupByNode.
	 *
	 * @param bottomPR	The child FromTable
	 * @param groupingList	The groupingList
	 * @param aggregateVector	The vector of aggregates from
	 *		the query block.  Since aggregation is done
	 *		at the same time as grouping, we need them
	 *		here.
	 * @param tableProperties	Properties list associated with the table
	 *
	 * @exception StandardException		Thrown on error
	 */
	public void init(
						Object  bottomPR,
						Object groupingList,
						Object	aggregateVector,
						Object tableProperties)
			throws StandardException
	{
		super.init(bottomPR, tableProperties);

		/* Group by without aggregates gets xformed into distinct */
		if (SanityManager.DEBUG)
		{
			SanityManager.ASSERT(((Vector) aggregateVector).size() > 0,
				"aggregateVector expected to be non-empty");
			if (!(childResult instanceof Optimizable))
			{
				SanityManager.THROWASSERT("childResult, " + childResult.getClass().getName() +
					", expected to be instanceof Optimizable");
			}
			if (!(childResult instanceof FromTable))
			{
				SanityManager.THROWASSERT("childResult, " + childResult.getClass().getName() +
					", expected to be instanceof FromTable");
			}
		}

		ResultColumnList newBottomRCL;
		this.groupingList = (GroupByList) groupingList;
		this.aggregateVector = (Vector) aggregateVector;
		this.parent = this;

		/*
		** The first thing we do is put ourselves on
		** top of the SELECT.  The select becomes the
		** childResult.  So our RCL becomes its RCL (so
		** nodes above it now point to us).  Map our
		** RCL to its columns.
		*/
		newBottomRCL = childResult.getResultColumns().copyListAndObjects();
		resultColumns = childResult.getResultColumns();
		childResult.setResultColumns(newBottomRCL);

		/*
		** We have aggregates, so we need to add
		** an extra PRNode and we also have to muck around
		** with our trees a might.
		*/
		addAggregates();

		/* We say that the source is never in sorted order if there is a distinct aggregate.
		 * (Not sure what happens if it is, so just skip it for now.)
		 * Otherwise, we check to see if the source is in sorted order on any permutation
		 * of the grouping columns.)
		 */
		if (! addDistinctAggregate && groupingList != null)
		{
			ColumnReference[] crs =
								new ColumnReference[this.groupingList.size()];

			// Now populate the CR array and see if ordered
			int glSize = this.groupingList.size();
			for (int index = 0; index < glSize; index++)
			{
				GroupByColumn gc =
						(GroupByColumn) this.groupingList.elementAt(index);
				crs[index] = gc.getColumnReference();
			}

			isInSortedOrder = childResult.isOrderedOn(crs, true, (Vector)null);
		}
	}

	/**
	 * Get whether or not the source is in sorted order.
	 *
	 * @return Whether or not the source is in sorted order.
	 */
	boolean getIsInSortedOrder()
	{
		return isInSortedOrder;
	}

	/**
	 * Add the extra result columns required by the aggregates
	 * to the result list.
	 * 
	 * @exception standard exception
	 */
	private void addAggregates()
		throws StandardException
	{
		addNewPRNode();
		addNewColumnsForAggregation();
		addDistinctAggregatesToOrderBy();
	}

	/**
	 * Add any distinct aggregates to the order by list.
	 * Asserts that there are 0 or more distincts.
	 */
	private void addDistinctAggregatesToOrderBy()
	{
		int numDistinct = numDistinctAggregates(aggregateVector);
		if (numDistinct != 0)
		{
			if (SanityManager.DEBUG)
			{
				SanityManager.ASSERT(numDistinct == 1,
					"Should not have more than 1 distinct aggregate per Group By node");
			}
			
			AggregatorInfo agg = null;
			int count = aggInfo.size();
			for (int i = 0; i < count; i++)
			{
				agg = (AggregatorInfo) aggInfo.elementAt(i);
				if (agg.isDistinct())
				{
					break;
				}
			}

			if (SanityManager.DEBUG)
			{
				SanityManager.ASSERT(agg != null && agg.isDistinct());
			}

			addDistinctAggregate = true;
			addDistinctAggregateColumnNum = agg.getInputColNum();
		}
	}
	
	/**
	 * Add a new PR node for aggregation.  Put the
	 * new PR under the sort.
	 *		
	 * @exception standard exception
	 */
	private void addNewPRNode()
		throws StandardException
	{
		/*
		** Get the new PR, put above the GroupBy.  
		*/
		parent = (FromTable) getNodeFactory().getNode(
										C_NodeTypes.PROJECT_RESTRICT_NODE,
										this, 	// child
										resultColumns,		// result column list
										null,				// restriction
										null,				// restriction list
										null,				// project subqueries
										null,				// restrict subqueries
										tableProperties,
										getContextManager());


		/*
		** Reset the bottom RCL to be empty.
		*/
		childResult.setResultColumns((ResultColumnList)
											getNodeFactory().getNode(
												C_NodeTypes.RESULT_COLUMN_LIST,
												getContextManager()));

		/*
		** Set the group by RCL to be empty
		*/
		resultColumns = (ResultColumnList) getNodeFactory().getNode(
											C_NodeTypes.RESULT_COLUMN_LIST,
											getContextManager());

	}


	/**
	 * Add a whole slew of columns needed for 
	 * aggregation. Basically, for each aggregate we add
	 * 2 columns: the aggregate input expression
	 * and the aggregator column.  The input expression is
	 * taken directly from the aggregator node.  The aggregator
	 * is the run time aggregator.  We add it to the RC list
	 * as a new object coming into the sort node.
	 * <P>
	 * At this point this is invoked, we have the following
	 * tree: <UL>
	 *      PR - (PARENT): RCL is the original select list
	 *       |
	 *      PR - GROUP BY:  RCL is empty
	 *       |
	 *      PR - FROM TABLE: RCL is empty </UL> <P>
	 *
	 * For each ColumnReference in PR RCL <UL>
	 *	<LI> clone the ref </LI>
	 *	<LI> create a new RC in the bottom RCL and set it 
	 *		 to the col ref </LI>
	 *	<LI> create a new RC in the GROUPBY RCL and set it to 
	 *		 point to the bottom RC </LI>
	 *	<LI> reset the top PR ref to point to the new GROUPBY
	 *		 RC	
	 *
	 * For each aggregate in aggregateVector <UL>
	 *	<LI> create RC in FROM TABLE.  Fill it with 
	 * 		aggs Operator.
	 *	<LI> create RC in FROM TABLE for agg result</LI>
	 *	<LI> create RC in FROM TABLE for aggregator</LI>
	 *	<LI> create RC in GROUPBY for agg input, set it
	 *		to point to FROM TABLE RC </LI>
	 *	<LI> create RC in GROUPBY for agg result</LI>
	 *	<LI> create RC in GROUPBY for aggregator</LI>
	 *	<LI> replace Agg with reference to RC for agg result </LI>
	 *
	 * @exception standard exception
	 */
	private void addNewColumnsForAggregation()
		throws StandardException
	{
		/*
		** Now we have two new nodes, the sort and a new PR above
		** it.  They all map to the child result set.  Now we must
		** find every aggregate and massage the tree.  For now we
		** will examine every result column of the original select
		** list.
		*/
		DataDictionary			dd;
		AggregateNode	aggregate = null;
		ColumnReference	newColumnRef;