Top Description Inners Fields Constructors Methods
org.apache.derby.impl.sql.compile

pack-priv Class GroupByNode

extends SingleChildResultSetNode
Class Inheritance
Imports
java.util.ArrayList, .Collections, .Comparator, .List, org.apache.derby.catalog.IndexDescriptor, org.apache.derby.shared.common.error.StandardException, org.apache.derby.shared.common.reference.ClassName, .SQLState, org.apache.derby.iapi.services.classfile.VMOpcode, org.apache.derby.iapi.services.compiler.MethodBuilder, org.apache.derby.iapi.services.context.ContextManager, org.apache.derby.iapi.services.io.FormatableArrayHolder, org.apache.derby.shared.common.sanity.SanityManager, org.apache.derby.iapi.sql.LanguageFactory, .ResultColumnDescriptor, org.apache.derby.iapi.sql.compile.AccessPath, .CostEstimate, .Optimizable, .OptimizablePredicate, .OptimizablePredicateList, .Optimizer, .RequiredRowOrdering, .RowOrdering, org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor, .DataDictionary, org.apache.derby.iapi.store.access.ColumnOrdering, org.apache.derby.impl.sql.execute.AggregatorInfo, .AggregatorInfoList

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.

For the most part, it simply delegates operations to its bottomPRSet, which is currently expected to be a ProjectRestrictResultSet generated for a SelectNode.

Note

A GroupByNode extends FromTable since it can exist in a FromList.

There is a lot of room for optimizations here:

Nested and Inner Type Summary

Modifier and TypeClass and Description
private static class
GroupByNode.ExpressionSorter

Comparator class for GROUP BY expression substitution.

Field Summary

Modifier and TypeField and Description
private boolean
private int
private AggregatorInfoList
aggInfo

Information that is used at execution time to process aggregates.

private List<AggregateNode>
aggregates

The list of all aggregates in the query block that contains this group by.

pack-priv GroupByList
groupingList

The GROUP BY list

private ValueNode
private SubqueryList
private final boolean
pack-priv FromTable
parent

The parent to the GroupByNode.

private boolean
Inherited from org.apache.derby.impl.sql.compile.SingleChildResultSetNode:
childResulthasTrulyTheBestAccessPath

Constructor Summary

AccessConstructor and Description
pack-priv
GroupByNode(ResultSetNode
The child FromTable
bottomPR
,
GroupByList
The groupingList
groupingList
,
List<AggregateNode>
The list of aggregates from the query block. Since aggregation is done at the same time as grouping, we need them here.
aggregates
,
ValueNode
The having clause.
havingClause
,
SubqueryList
subqueries in the having clause.
havingSubquerys
,
int
NestingLevel of this group by node. This is used for error checking of group by queries with having clause.
nestingLevel
,
ContextManager
The context manager
cm
)

Constructor for a GroupByNode.

Method Summary

Modifier and TypeMethod and Description
private void
addAggregateColumns()

In the query rewrite involving aggregates, add the columns for aggregation.

private void
addAggregates()

Add the extra result columns required by the aggregates to the result list.

private void
addDistinctAggregatesToOrderBy()

Add any distinct aggregates to the order by list.

private void
addNewColumnsForAggregation()

Add a whole slew of columns needed for aggregation.

private void
addNewPRNode()

Add a new PR node for aggregation.

private ArrayList<SubstituteExpressionVisitor>

Returns:

havingRefsToSubstitute visitors array. Return any havingRefsToSubstitute visitors since it is too early to apply them yet; we need the AggregateNodes unmodified until after we add the new columns for aggregation (DERBY-4071).
addUnAggColumns
()

In the query rewrite for group by, add the columns on which we are doing the group by.

pack-priv void
considerPostOptimizeOptimizations(boolean
true if SELECT containing this vector/scalar aggregate has a restriction
selectHasPredicates
)

Consider any optimizations after the optimizer has chosen a plan.

public CostEstimate
estimateCost(OptimizablePredicateList
The predicate list to optimize against
predList
,
ConglomerateDescriptor
The conglomerate descriptor to get the cost of
cd
,
CostEstimate
The estimated cost of the part of the plan outer to this optimizable.
outerCost
,
Optimizer
The optimizer to use to help estimate the cost
optimizer
,
RowOrdering
The row ordering for all the tables in the join order, including this one.
rowOrdering
)

Overrides org.apache.derby.impl.sql.compile.FromTable.estimateCost.

Implements org.apache.derby.iapi.sql.compile.Optimizable.estimateCost.

Estimate the cost of scanning this Optimizable using the given predicate list with the given conglomerate.

pack-priv boolean

Returns:

boolean Whether or not the FromSubquery is flattenable.
flattenableInFromSubquery
(FromList
The outer from list
fromList
)

Overrides org.apache.derby.impl.sql.compile.SingleChildResultSetNode.flattenableInFromSubquery.

Evaluate whether or not the subquery in a FromSubquery is flattenable.

pack-priv void
generate(ActivationClassBuilder
The ActivationClassBuilder for the class being built
acb
,
MethodBuilder
The method for the generated code to go into
mb
)

Overrides org.apache.derby.impl.sql.compile.QueryTreeNode.generate.

generate the sort result set operating over the source result set.

private void
genGroupedAggregateResultSet(ActivationClassBuilder acb, MethodBuilder mb)

Generate the code to evaluate grouped aggregates.

private void
genScalarAggregateResultSet(ActivationClassBuilder acb, MethodBuilder mb)

Generate the code to evaluate scalar aggregates.

private ResultColumn

Returns:

the new result column
getColumnReference
(ResultColumn
the source
targetRC
,
DataDictionary dd)

Method for creating a new result column referencing the one passed in.

pack-priv boolean

Returns:

Whether or not the source is in sorted order.
getIsInSortedOrder
()

Get whether or not the source is in sorted order.

pack-priv final FromTable

Returns:

the parent node
getParent
()

Return the parent node to this one, if there is one.

pack-priv boolean

Returns:

Whether or not the underlying ResultSet tree will return a single row.
isOneRowResultSet
()

Overrides org.apache.derby.impl.sql.compile.SingleChildResultSetNode.isOneRowResultSet.

Return whether or not the underlying ResultSet tree will return a single row, at most.

pack-priv ResultColumnDescriptor[]
pack-priv ResultSetNode

Returns:

ResultSetNode The top of the optimized subtree
optimize
(DataDictionary
The DataDictionary to use for optimization
dataDictionary
,
PredicateList
The PredicateList to optimize. This should be a join predicate.
predicates
,
double
The number of outer joining rows
outerRows
)

Overrides org.apache.derby.impl.sql.compile.SingleChildResultSetNode.optimize.

Optimize this GroupByNode.

public CostEstimate
optimizeIt(Optimizer
Optimizer to use.
optimizer
,
OptimizablePredicateList
The predicate list to optimize against
predList
,
CostEstimate
The CostEstimate for the outer tables in the join order, telling how many times this Optimizable will be scanned.
outerCost
,
RowOrdering
The row ordering for all the tables in the join order, including this one.
rowOrdering
)

Overrides org.apache.derby.impl.sql.compile.FromTable.optimizeIt.

Implements org.apache.derby.iapi.sql.compile.Optimizable.optimizeIt.

Choose the best access path for this Optimizable.

pack-priv void
printSubNodes(int
The depth of this node in the tree
depth
)

Overrides org.apache.derby.impl.sql.compile.SingleChildResultSetNode.printSubNodes.

Prints the sub-nodes of this object.

public boolean
pushOptPredicate(OptimizablePredicate
OptimizablePredicate to push down.
optimizablePredicate
)

Overrides org.apache.derby.impl.sql.compile.FromTable.pushOptPredicate.

Implements org.apache.derby.iapi.sql.compile.Optimizable.pushOptPredicate.

Push an OptimizablePredicate down, if this node accepts it.

public String

Returns:

This object as a String
toString
()

Overrides org.apache.derby.impl.sql.compile.FromTable.toString.

Convert this object to a String.

Inherited from org.apache.derby.impl.sql.compile.SingleChildResultSetNode:
acceptChildrenaddNewPredicateadjustForSortEliminationadjustForSortEliminationchangeAccessPathdecrementLevelensurePredicateListforUpdategetChildResultgetFinalCostEstimategetFromTableByNamegetTrulyTheBestAccessPathinitAccessPathsisNotExistsisOrderedOnmodifyAccessPathspreprocesspullOptPredicatespushExpressionsreferencesSessionSchemareferencesTargetreflectionNeededForProjectionsetChildResultsetLevelsubqueryReferencesTargetupdateBestPlanMapupdateTargetLockMode

Field Detail

addDistinctAggregateback to summary
private boolean addDistinctAggregate
addDistinctAggregateColumnNumback to summary
private int addDistinctAggregateColumnNum
aggInfoback to summary
private AggregatorInfoList aggInfo

Information that is used at execution time to process aggregates.

aggregatesback to summary
private List<AggregateNode> aggregates

The list of all aggregates in the query block that contains this group by.

groupingListback to summary
pack-priv GroupByList groupingList

The GROUP BY list

havingClauseback to summary
private ValueNode havingClause
havingSubquerysback to summary
private SubqueryList havingSubquerys
isInSortedOrderback to summary
private final boolean isInSortedOrder
parentback to summary
pack-priv FromTable parent

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.

singleInputRowOptimizationback to summary
private boolean singleInputRowOptimization

Constructor Detail

GroupByNodeback to summary
pack-priv GroupByNode(ResultSetNode bottomPR, GroupByList groupingList, List<AggregateNode> aggregates, ValueNode havingClause, SubqueryList havingSubquerys, int nestingLevel, ContextManager cm) throws StandardException

Constructor for a GroupByNode.

Parameters
bottomPR:ResultSetNode

The child FromTable

groupingList:GroupByList

The groupingList

aggregates:List<AggregateNode>

The list of aggregates from the query block. Since aggregation is done at the same time as grouping, we need them here.

havingClause:ValueNode

The having clause.

havingSubquerys:SubqueryList

subqueries in the having clause.

nestingLevel:int

NestingLevel of this group by node. This is used for error checking of group by queries with having clause.

cm:ContextManager

The context manager

Exceptions
StandardException:
Thrown on error

Method Detail

addAggregateColumnsback to summary
private void addAggregateColumns() throws StandardException

In the query rewrite involving aggregates, add the columns for aggregation.

See Also
addNewColumnsForAggregation
addAggregatesback to summary
private void addAggregates() throws StandardException

Add the extra result columns required by the aggregates to the result list.

Exceptions
StandardException:
standard exception policy
addDistinctAggregatesToOrderByback to summary
private void addDistinctAggregatesToOrderBy()

Add any distinct aggregates to the order by list. Asserts that there are 0 or more distincts.

addNewColumnsForAggregationback to summary
private void addNewColumnsForAggregation() throws StandardException

Add a whole slew of columns needed for aggregation. Basically, for each aggregate we add 3 columns: the aggregate input expression and the aggregator column and a column where the aggregate result is stored. 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.

At this point this is invoked, we have the following tree:

    PR - (PARENT): RCL is the original select list | PR - GROUP BY: RCL is empty | PR - FROM TABLE: RCL is empty

For each ColumnReference in PR RCL

  • clone the ref
  • create a new RC in the bottom RCL and set it to the col ref
  • create a new RC in the GROUPBY RCL and set it to point to the bottom RC
  • reset the top PR ref to point to the new GROUPBY RC
For each aggregate in aggregates
  • create RC in FROM TABLE. Fill it with aggs Operator.
  • create RC in FROM TABLE for agg result
  • create RC in FROM TABLE for aggregator
  • create RC in GROUPBY for agg input, set it to point to FROM TABLE RC
  • create RC in GROUPBY for agg result
  • create RC in GROUPBY for aggregator
  • replace Agg with reference to RC for agg result
.

For a query like,

	  select c1, sum(c2), max(c3)
	  from t1 
	  group by c1;
	  
the query tree ends up looking like this:
	    ProjectRestrictNode RCL -> (ptr to GBN(column[0]), ptr to GBN(column[1]), ptr to GBN(column[4]))
	              |
	    GroupByNode RCL->(C1, SUM(C2), <agg-input>, , MAX(C3), <agg-input>, <aggregator>)
	              |
	    ProjectRestrict RCL->(C1, C2, C3)
	              |
	    FromBaseTable
	    
The RCL of the GroupByNode contains all the unagg (or grouping columns) followed by 3 RC's for each aggregate in this order: the final computed aggregate value, the aggregate input and the aggregator function.

The Aggregator function puts the results in the first of the 3 RC's and the PR resultset in turn picks up the value from there.

The notation (ptr to GBN(column[0])) basically means that it is a pointer to the 0th RC in the RCL of the GroupByNode.

The addition of these unagg and agg columns to the GroupByNode and to the PRN is performed in addUnAggColumns and addAggregateColumns.

Note that that addition of the GroupByNode is done after the query is optimized (in SelectNode#modifyAccessPaths) which means a fair amount of patching up is needed to account for generated group by columns.

Exceptions
StandardException:
standard exception policy
addNewPRNodeback to summary
private void addNewPRNode() throws StandardException

Add a new PR node for aggregation. Put the new PR under the sort.

Exceptions
StandardException:
standard exception policy
addUnAggColumnsback to summary
private ArrayList<SubstituteExpressionVisitor> addUnAggColumns() throws StandardException

In the query rewrite for group by, add the columns on which we are doing the group by.

Returns:ArrayList<SubstituteExpressionVisitor>

havingRefsToSubstitute visitors array. Return any havingRefsToSubstitute visitors since it is too early to apply them yet; we need the AggregateNodes unmodified until after we add the new columns for aggregation (DERBY-4071).

See Also
addNewColumnsForAggregation
considerPostOptimizeOptimizationsback to summary
pack-priv void considerPostOptimizeOptimizations(boolean selectHasPredicates) throws StandardException

Consider any optimizations after the optimizer has chosen a plan. Optimizations include: o min optimization for scalar aggregates o max optimization for scalar aggregates

Parameters
selectHasPredicates:boolean

true if SELECT containing this vector/scalar aggregate has a restriction

Exceptions
StandardException:
on error
estimateCostback to summary
public CostEstimate estimateCost(OptimizablePredicateList predList, ConglomerateDescriptor cd, CostEstimate outerCost, Optimizer optimizer, RowOrdering rowOrdering) throws StandardException

Overrides org.apache.derby.impl.sql.compile.FromTable.estimateCost.

Implements org.apache.derby.iapi.sql.compile.Optimizable.estimateCost.

Doc from org.apache.derby.iapi.sql.compile.Optimizable.estimateCost.

Estimate the cost of scanning this Optimizable using the given predicate list with the given conglomerate. It is assumed that the predicate list has already been classified. This cost estimate is just for one scan, not for the life of the query.

Parameters
predList:OptimizablePredicateList

The predicate list to optimize against

cd:ConglomerateDescriptor

The conglomerate descriptor to get the cost of

outerCost:CostEstimate

The estimated cost of the part of the plan outer to this optimizable.

optimizer:Optimizer

The optimizer to use to help estimate the cost

rowOrdering:RowOrdering

The row ordering for all the tables in the join order, including this one.

Returns:CostEstimate

The estimated cost of doing the scan

Annotations
@Override
Exceptions
StandardException:
Thrown on error
See Also
Optimizable#estimateCost
flattenableInFromSubqueryback to summary
pack-priv boolean flattenableInFromSubquery(FromList fromList)

Overrides org.apache.derby.impl.sql.compile.SingleChildResultSetNode.flattenableInFromSubquery.

Evaluate whether or not the subquery in a FromSubquery is flattenable. Currently, a FSqry is flattenable if all of the following are true: o Subquery is a SelectNode. o It contains no top level subqueries. (RESOLVE - we can relax this) o It does not contain a group by or having clause o It does not contain aggregates.

Parameters
fromList:FromList

The outer from list

Returns:boolean

boolean Whether or not the FromSubquery is flattenable.

Annotations
@Override
generateback to summary
pack-priv void generate(ActivationClassBuilder acb, MethodBuilder mb) throws StandardException

Overrides org.apache.derby.impl.sql.compile.QueryTreeNode.generate.

generate the sort result set operating over the source result set. Adds distinct aggregates to the sort if necessary.

Parameters
acb:ActivationClassBuilder

Doc from org.apache.derby.impl.sql.compile.QueryTreeNode.generate.

The ActivationClassBuilder for the class being built

mb:MethodBuilder

Doc from org.apache.derby.impl.sql.compile.QueryTreeNode.generate.

The method for the generated code to go into

Annotations
@Override
Exceptions
StandardException:
Thrown on error
genGroupedAggregateResultSetback to summary
private void genGroupedAggregateResultSet(ActivationClassBuilder acb, MethodBuilder mb) throws StandardException

Generate the code to evaluate grouped aggregates.

genScalarAggregateResultSetback to summary
private void genScalarAggregateResultSet(ActivationClassBuilder acb, MethodBuilder mb)

Generate the code to evaluate scalar aggregates.

getColumnReferenceback to summary
private ResultColumn getColumnReference(ResultColumn targetRC, DataDictionary dd) throws StandardException

Method for creating a new result column referencing the one passed in.

Parameters
targetRC:ResultColumn

the source

Returns:ResultColumn

the new result column

Exceptions
StandardException:
on error
getIsInSortedOrderback to summary
pack-priv boolean getIsInSortedOrder()

Get whether or not the source is in sorted order.

Returns:boolean

Whether or not the source is in sorted order.

getParentback to summary
pack-priv final FromTable getParent()

Return the parent node to this one, if there is one. It will return 'this' if there is no generated node above this one.

Returns:FromTable

the parent node

isOneRowResultSetback to summary
pack-priv boolean isOneRowResultSet() throws StandardException

Overrides org.apache.derby.impl.sql.compile.SingleChildResultSetNode.isOneRowResultSet.

Return whether or not the underlying ResultSet tree will return a single row, at most. This is important for join nodes where we can save the extra next on the right side if we know that it will return at most 1 row.

Returns:boolean

Whether or not the underlying ResultSet tree will return a single row.

Annotations
@Override
Exceptions
StandardException:
Thrown on error
makeResultDescriptorsback to summary
pack-priv ResultColumnDescriptor[] makeResultDescriptors()

Overrides org.apache.derby.impl.sql.compile.ResultSetNode.makeResultDescriptors.

Annotations
@Override
optimizeback to summary
pack-priv ResultSetNode optimize(DataDictionary dataDictionary, PredicateList predicates, double outerRows) throws StandardException

Overrides org.apache.derby.impl.sql.compile.SingleChildResultSetNode.optimize.

Optimize this GroupByNode.

Parameters
dataDictionary:DataDictionary

The DataDictionary to use for optimization

predicates:PredicateList

The PredicateList to optimize. This should be a join predicate.

outerRows:double

The number of outer joining rows

Returns:ResultSetNode

ResultSetNode The top of the optimized subtree

Annotations
@Override
Exceptions
StandardException:
Thrown on error
optimizeItback to summary
public CostEstimate optimizeIt(Optimizer optimizer, OptimizablePredicateList predList, CostEstimate outerCost, RowOrdering rowOrdering) throws StandardException

Overrides org.apache.derby.impl.sql.compile.FromTable.optimizeIt.

Implements org.apache.derby.iapi.sql.compile.Optimizable.optimizeIt.

Doc from org.apache.derby.iapi.sql.compile.Optimizable.optimizeIt.

Choose the best access path for this Optimizable.

Parameters
optimizer:Optimizer

Optimizer to use.

predList:OptimizablePredicateList

The predicate list to optimize against

outerCost:CostEstimate

The CostEstimate for the outer tables in the join order, telling how many times this Optimizable will be scanned.

rowOrdering:RowOrdering

The row ordering for all the tables in the join order, including this one.

Returns:CostEstimate

The optimizer's estimated cost of the best access path.

Annotations
@Override
Exceptions
StandardException:
Thrown on error
See Also
Optimizable#optimizeIt
printSubNodesback to summary
pack-priv void printSubNodes(int depth)

Overrides org.apache.derby.impl.sql.compile.SingleChildResultSetNode.printSubNodes.

Prints the sub-nodes of this object. See QueryTreeNode.java for how tree printing is supposed to work.

Parameters
depth:int

The depth of this node in the tree

Annotations
@Override
pushOptPredicateback to summary
public boolean pushOptPredicate(OptimizablePredicate optimizablePredicate) throws StandardException

Overrides org.apache.derby.impl.sql.compile.FromTable.pushOptPredicate.

Implements org.apache.derby.iapi.sql.compile.Optimizable.pushOptPredicate.

Doc from org.apache.derby.iapi.sql.compile.Optimizable.pushOptPredicate.

Push an OptimizablePredicate down, if this node accepts it.

Parameters
optimizablePredicate:OptimizablePredicate

OptimizablePredicate to push down.

Returns:boolean

Whether or not the predicate was pushed down.

Annotations
@Override
Exceptions
StandardException:
Thrown on error
See Also
org.apache.derby.iapi.sql.compile.Optimizable#pushOptPredicate
toStringback to summary
public String toString()

Overrides org.apache.derby.impl.sql.compile.FromTable.toString.

Convert this object to a String. See comments in QueryTreeNode.java for how this should be done for tree printing.

Returns:String

This object as a String

Annotations
@Override
org.apache.derby.impl.sql.compile back to summary

private Class GroupByNode.ExpressionSorter

extends Object
implements Comparator<SubstituteExpressionVisitor>
Class Inheritance
  • java.lang.Object
  • org.apache.derby.impl.sql.compile.GroupByNode.ExpressionSorter
All Implemented Interfaces
java.util.Comparator

Comparator class for GROUP BY expression substitution. This class enables the sorting of a collection of SubstituteExpressionVisitor instances. We sort the visitors during the tree manipulation processing in order to process expressions of higher complexity prior to expressions of lower complexity. Processing the expressions in this order ensures that we choose the best match for an expression, and thus avoids problems where we substitute a sub-expression instead of the full expression. For example, if the statement is: ... GROUP BY a+b, a, a*(a+b), a+b+c we'll process those expressions in the order: a*(a+b), a+b+c, a+b, then a.

Constructor Summary

AccessConstructor and Description
private

Method Summary

Modifier and TypeMethod and Description
public int
compare(SubstituteExpressionVisitor
the first object to be compared.
o1
,
SubstituteExpressionVisitor
the second object to be compared.
o2
)

Implements java.util.Comparator.compare.

Compares its two arguments for order.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Constructor Detail

ExpressionSorterback to summary
private ExpressionSorter()

Method Detail

compareback to summary
public int compare(SubstituteExpressionVisitor o1, SubstituteExpressionVisitor o2)

Implements java.util.Comparator.compare.

Doc from java.util.Comparator.compare.

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

The implementor must ensure that signum(compare(x, y)) == -signum(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that signum(compare(x, z))==signum(compare(y, z)) for all z.

Parameters
o1:SubstituteExpressionVisitor

the first object to be compared.

o2:SubstituteExpressionVisitor

the second object to be compared.

Returns:int

a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.