Collaboration diagram for com.cloudera.impala.planner.AnalyticPlanner:

Classes
class	PartitionGroup

class	SortGroup

class	WindowGroup

Public Member Functions
	AnalyticPlanner (List< TupleId > stmtTupleIds, AnalyticInfo analyticInfo, Analyzer analyzer, PlannerContext ctx)

PlanNode	createSingleNodePlan (PlanNode root, List< Expr > groupingExprs, List< Expr > inputPartitionExprs) throws ImpalaException

Private Member Functions
void	mergeSortGroups (List< SortGroup > sortGroups)

void	mergePartitionGroups (List< PartitionGroup > partitionGroups, int numNodes)

void	computeInputPartitionExprs (List< PartitionGroup > partitionGroups, List< Expr > groupingExprs, int numNodes, List< Expr > inputPartitionExprs)

void	orderGroups (List< PartitionGroup > partitionGroups)

SortInfo	createSortInfo (PlanNode input, List< Expr > sortExprs, List< Boolean > isAsc, List< Boolean > nullsFirst)

PlanNode	createSortGroupPlan (PlanNode root, SortGroup sortGroup, List< Expr > partitionExprs) throws ImpalaException

Expr	createNullMatchingEquals (List< Expr > exprs, TupleId inputTid, ExprSubstitutionMap bufferedSmap)

Expr	createNullMatchingEqualsAux (List< Expr > elements, int i, TupleId inputTid, ExprSubstitutionMap bufferedSmap)

List< WindowGroup >	collectWindowGroups ()

List< SortGroup >	collectSortGroups (List< WindowGroup > windowGroups)

List< PartitionGroup >	collectPartitionGroups (List< SortGroup > sortGroups)

Private Attributes
final List< TupleId >	stmtTupleIds_

final AnalyticInfo	analyticInfo_

final Analyzer	analyzer_

final PlannerContext	ctx_

Static Private Attributes
static final Logger	LOG = LoggerFactory.getLogger(AnalyticPlanner.class)

Detailed Description

The analytic planner adds plan nodes to an existing plan tree in order to implement the AnalyticInfo of a given query stmt. The resulting plan reflects similarities among analytic exprs with respect to partitioning, ordering and windowing to reduce data exchanges and sorts (the exchanges and sorts are currently not minimal). The generated plan has the following structure: ... ( ( ( analytic node <– group of analytic exprs with compatible window )+ <– group of analytic exprs with compatible ordering sort node? )+ <– group of analytic exprs with compatible partitioning hash exchange? )* <– group of analytic exprs that have different partitioning input plan node ...

Definition at line 68 of file AnalyticPlanner.java.

Constructor & Destructor Documentation

com.cloudera.impala.planner.AnalyticPlanner.AnalyticPlanner	(	List< TupleId >	stmtTupleIds,
		AnalyticInfo	analyticInfo,
		Analyzer	analyzer,
		PlannerContext	ctx
	)

inline

Definition at line 83 of file AnalyticPlanner.java.

References com.cloudera.impala.planner.AnalyticPlanner.analyticInfo_, com.cloudera.impala.planner.AnalyticPlanner.analyzer_, com.cloudera.impala.planner.AnalyticPlanner.ctx_, com.cloudera.impala.analysis.AggregateInfoBase.getOutputTupleId(), and com.cloudera.impala.planner.AnalyticPlanner.stmtTupleIds_.

Member Function Documentation

List<PartitionGroup> com.cloudera.impala.planner.AnalyticPlanner.collectPartitionGroups ( List< SortGroup > sortGroups )

inlineprivate

Extract a minimal set of PartitionGroups from sortGroups.

Definition at line 812 of file AnalyticPlanner.java.

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan().

List<SortGroup> com.cloudera.impala.planner.AnalyticPlanner.collectSortGroups ( List< WindowGroup > windowGroups )

inlineprivate

Partitions the windowGroups into SortGroups based on compatible order by exprs.

Definition at line 732 of file AnalyticPlanner.java.

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan().

List<WindowGroup> com.cloudera.impala.planner.AnalyticPlanner.collectWindowGroups ( )

inlineprivate

Extract a minimal set of WindowGroups from analyticExprs.

Definition at line 603 of file AnalyticPlanner.java.

References com.cloudera.impala.planner.AnalyticPlanner.analyticInfo_, com.cloudera.impala.analysis.AnalyticInfo.getAnalyticExprs(), and com.cloudera.impala.analysis.AggregateInfoBase.getOutputTupleDesc().

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan().

void com.cloudera.impala.planner.AnalyticPlanner.computeInputPartitionExprs	(	List< PartitionGroup >	partitionGroups,
		List< Expr >	groupingExprs,
		int	numNodes,
		List< Expr >	inputPartitionExprs
	)

inlineprivate

Determine the partition group that has the maximum intersection in terms of the estimated ndv of the partition exprs with groupingExprs. That partition group is placed at the front of partitionGroups, with its partition exprs reduced to the intersection, and the intersecting groupingExprs are returned in inputPartitionExprs.

Definition at line 200 of file AnalyticPlanner.java.

References com.cloudera.impala.planner.AnalyticPlanner.analyzer_.

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan().

Expr com.cloudera.impala.planner.AnalyticPlanner.createNullMatchingEquals	(	List< Expr >	exprs,
		TupleId	inputTid,
		ExprSubstitutionMap	bufferedSmap
	)

inlineprivate

Create a predicate that checks if all exprs are equal or both sides are null.

Definition at line 439 of file AnalyticPlanner.java.

References com.cloudera.impala.planner.AnalyticPlanner.analyzer_, and com.cloudera.impala.planner.AnalyticPlanner.createNullMatchingEqualsAux().

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSortGroupPlan().

Expr com.cloudera.impala.planner.AnalyticPlanner.createNullMatchingEqualsAux	(	List< Expr >	elements,
		int	i,
		TupleId	inputTid,
		ExprSubstitutionMap	bufferedSmap
	)

inlineprivate

Create an unanalyzed predicate that checks if elements >= i are equal or both sides are null.

The predicate has the form ((lhs[i] is null && rhs[i] is null) || ( lhs[i] is not null && rhs[i] is not null && lhs[i] = rhs[i])) && <createEqualsAux(i + 1)>

Definition at line 456 of file AnalyticPlanner.java.

References com.cloudera.impala.planner.AnalyticPlanner.analyzer_.

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createNullMatchingEquals().

PlanNode com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan	(	PlanNode	root,
		List< Expr >	groupingExprs,
		List< Expr >	inputPartitionExprs
	)		throws ImpalaException

inline

Return plan tree that augments 'root' with plan nodes that implement single-node evaluation of the AnalyticExprs in analyticInfo. This plan takes into account a possible hash partition of its input on 'groupingExprs'; if this is non-null, it returns in 'inputPartitionExprs' a subset of the grouping exprs which should be used for the aggregate hash partitioning during the parallelization of 'root'. TODO: when generating sort orders for the sort groups, optimize the ordering of the partition exprs (so that subsequent sort operations see the input sorted on a prefix of their required sort exprs) TODO: when merging sort groups, recognize equivalent exprs (using the equivalence classes) rather than looking for expr equality

Definition at line 109 of file AnalyticPlanner.java.

PlanNode com.cloudera.impala.planner.AnalyticPlanner.createSortGroupPlan	(	PlanNode	root,
		SortGroup	sortGroup,
		List< Expr >	partitionExprs
	)		throws ImpalaException

inlineprivate

Create plan tree for the entire sort group, including all contained window groups. Marks the SortNode as requiring its input to be partitioned if partitionExprs is not null (partitionExprs represent the data partition of the entire partition group of which this sort group is a part).

Definition at line 334 of file AnalyticPlanner.java.

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan().

SortInfo com.cloudera.impala.planner.AnalyticPlanner.createSortInfo	(	PlanNode	input,
		List< Expr >	sortExprs,
		List< Boolean >	isAsc,
		List< Boolean >	nullsFirst
	)

inlineprivate

Create SortInfo, including sort tuple, to sort entire input row on sortExprs.

Definition at line 270 of file AnalyticPlanner.java.

References com.cloudera.impala.planner.AnalyticPlanner.analyzer_, com.cloudera.impala.analysis.TupleDescriptor.getSlots(), com.cloudera.impala.planner.PlanNode.getTupleIds(), com.cloudera.impala.analysis.Expr.isBoundByTupleIds(), and com.cloudera.impala.analysis.Expr.substituteList().

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSortGroupPlan().

void com.cloudera.impala.planner.AnalyticPlanner.mergePartitionGroups	(	List< PartitionGroup >	partitionGroups,
		int	numNodes
	)

inlineprivate

Coalesce partition groups for which the intersection of their partition exprs has ndv estimate > numNodes, so that the resulting plan still parallelizes across all nodes.

Definition at line 168 of file AnalyticPlanner.java.

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan().

void com.cloudera.impala.planner.AnalyticPlanner.mergeSortGroups ( List< SortGroup > sortGroups )

inlineprivate

Coalesce sort groups that have compatible partition-by exprs and have a prefix relationship.

Definition at line 145 of file AnalyticPlanner.java.

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan().

void com.cloudera.impala.planner.AnalyticPlanner.orderGroups ( List< PartitionGroup > partitionGroups )

inlineprivate

Order partition groups (and the sort groups within them) by increasing totalOutputTupleSize. This minimizes the total volume of data that needs to be repartitioned and sorted. Also move the non-partitioning partition group to the end.

Definition at line 238 of file AnalyticPlanner.java.

Referenced by com.cloudera.impala.planner.AnalyticPlanner.createSingleNodePlan().