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

Public Member Functions
	DistributedPlanner (PlannerContext ctx)

ArrayList< PlanFragment >	createPlanFragments (PlanNode singleNodePlan) throws ImpalaException

PlanFragment	createInsertFragment (PlanFragment inputFragment, InsertStmt insertStmt, Analyzer analyzer, ArrayList< PlanFragment > fragments) throws InternalException

Private Member Functions
PlanFragment	createPlanFragments (PlanNode root, boolean isPartitioned, long perNodeMemLimit, ArrayList< PlanFragment > fragments) throws InternalException, NotImplementedException

long	getNumDistinctValues (List< Expr > exprs)

PlanFragment	createMergeFragment (PlanFragment inputFragment) throws InternalException

PlanFragment	createScanFragment (PlanNode node)

PlanFragment	createCrossJoinFragment (CrossJoinNode node, PlanFragment rightChildFragment, PlanFragment leftChildFragment, long perNodeMemLimit, ArrayList< PlanFragment > fragments) throws InternalException

PlanFragment	createHashJoinFragment (HashJoinNode node, PlanFragment rightChildFragment, PlanFragment leftChildFragment, long perNodeMemLimit, ArrayList< PlanFragment > fragments) throws InternalException

boolean	isCompatPartition (DataPartition lhsPartition, DataPartition rhsPartition, List< Expr > lhsJoinExprs, List< Expr > rhsJoinExprs, Analyzer analyzer)

DataPartition	getCompatPartition (List< Expr > srcJoinExprs, DataPartition srcPartition, List< Expr > joinExprs, Analyzer analyzer)

PlanFragment	createUnionNodeFragment (UnionNode unionNode, ArrayList< PlanFragment > childFragments, ArrayList< PlanFragment > fragments) throws InternalException

PlanFragment	createSelectNodeFragment (SelectNode selectNode, ArrayList< PlanFragment > childFragments)

void	connectChildFragment (PlanNode node, int childIdx, PlanFragment childFragment) throws InternalException

PlanFragment	createParentFragment (PlanFragment childFragment, DataPartition parentPartition) throws InternalException

PlanFragment	createAggregationFragment (AggregationNode node, PlanFragment childFragment, ArrayList< PlanFragment > fragments) throws InternalException

PlanFragment	createAnalyticFragment (PlanNode node, PlanFragment childFragment, ArrayList< PlanFragment > fragments) throws InternalException

PlanFragment	createOrderByFragment (SortNode node, PlanFragment childFragment, ArrayList< PlanFragment > fragments) throws InternalException

Private Attributes
final PlannerContext	ctx_

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

Detailed Description

The distributed planner is responsible for creating an executable, distributed plan from a single-node plan that can be sent to the backend.

Definition at line 42 of file DistributedPlanner.java.

Constructor & Destructor Documentation

com.cloudera.impala.planner.DistributedPlanner.DistributedPlanner ( PlannerContext ctx )

inline

Definition at line 47 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.ctx_.

Member Function Documentation

void com.cloudera.impala.planner.DistributedPlanner.connectChildFragment	(	PlanNode	node,
		int	childIdx,
		PlanFragment	childFragment
	)		throws InternalException

inlineprivate

Replace node's child at index childIdx with an ExchangeNode that receives its input from childFragment.

Definition at line 640 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.ctx_, and com.cloudera.impala.planner.PlannerContext.getNextNodeId().

Referenced by com.cloudera.impala.planner.DistributedPlanner.createCrossJoinFragment(), com.cloudera.impala.planner.DistributedPlanner.createHashJoinFragment(), and com.cloudera.impala.planner.DistributedPlanner.createUnionNodeFragment().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createAggregationFragment	(	AggregationNode	node,
		PlanFragment	childFragment,
		ArrayList< PlanFragment >	fragments
	)		throws InternalException

inlineprivate

Returns a fragment that materializes the aggregation result of 'node'. If the child fragment is partitioned, the result fragment will be partitioned on the grouping exprs of 'node'. If 'node' is phase 1 of a 2-phase DISTINCT aggregation, this will simply add 'node' to the child fragment and return the child fragment; the new fragment will be created by the subsequent call of createAggregationFragment() for the phase 2 AggregationNode.

Definition at line 681 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.createParentFragment(), com.cloudera.impala.planner.DistributedPlanner.ctx_, com.cloudera.impala.planner.PlannerContext.getNextNodeId(), com.cloudera.impala.planner.PlannerContext.getRootAnalyzer(), and com.cloudera.impala.planner.DataPartition.UNPARTITIONED.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createAnalyticFragment	(	PlanNode	node,
		PlanFragment	childFragment,
		ArrayList< PlanFragment >	fragments
	)		throws InternalException

inlineprivate

Returns a fragment that produces the output of either an AnalyticEvalNode or of the SortNode that provides the input to an AnalyticEvalNode. ('node' can be either an AnalyticEvalNode or a SortNode). The returned fragment is either partitioned on the Partition By exprs or unpartitioned in the absence of such exprs.

Definition at line 832 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.createParentFragment(), com.cloudera.impala.planner.DistributedPlanner.ctx_, com.cloudera.impala.planner.SortNode.getInputPartition(), com.cloudera.impala.planner.AnalyticEvalNode.getOrderByElements(), com.cloudera.impala.planner.AnalyticEvalNode.getPartitionExprs(), com.cloudera.impala.planner.PlannerContext.getRootAnalyzer(), and com.cloudera.impala.planner.DataPartition.UNPARTITIONED.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createCrossJoinFragment	(	CrossJoinNode	node,
		PlanFragment	rightChildFragment,
		PlanFragment	leftChildFragment,
		long	perNodeMemLimit,
		ArrayList< PlanFragment >	fragments
	)		throws InternalException

inlineprivate

Modifies the leftChildFragment to execute a cross join. The right child input is provided by an ExchangeNode, which is the destination of the rightChildFragment's output.

Definition at line 273 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.connectChildFragment().

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createHashJoinFragment	(	HashJoinNode	node,
		PlanFragment	rightChildFragment,
		PlanFragment	leftChildFragment,
		long	perNodeMemLimit,
		ArrayList< PlanFragment >	fragments
	)		throws InternalException

inlineprivate

Creates either a broadcast join or a repartitioning join, depending on the expected cost. If any of the inputs to the cost computation is unknown, it assumes the cost will be 0. Costs being equal, it'll favor partitioned over broadcast joins. If perNodeMemLimit > 0 and the size of the hash table for a broadcast join is expected to exceed that mem limit, switches to partitioned join instead. TODO: revisit the choice of broadcast as the default TODO: don't create a broadcast join if we already anticipate that this will exceed the query's memory budget.

Definition at line 294 of file DistributedPlanner.java.

References com.cloudera.impala.analysis.Expr.cloneList(), com.cloudera.impala.planner.DistributedPlanner.connectChildFragment(), com.cloudera.impala.planner.DistributedPlanner.ctx_, com.cloudera.impala.analysis.JoinOperator.FULL_OUTER_JOIN, com.cloudera.impala.planner.DistributedPlanner.getCompatPartition(), com.cloudera.impala.planner.PlannerContext.getNextFragmentId(), com.cloudera.impala.planner.PlannerContext.getNextNodeId(), com.cloudera.impala.planner.PlannerContext.HASH_TBL_SPACE_OVERHEAD, com.cloudera.impala.planner.DistributedPlanner.isCompatPartition(), and com.cloudera.impala.analysis.JoinOperator.RIGHT_ANTI_JOIN.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createInsertFragment	(	PlanFragment	inputFragment,
		InsertStmt	insertStmt,
		Analyzer	analyzer,
		ArrayList< PlanFragment >	fragments
	)		throws InternalException

inline

Makes a cost-based decision on whether to repartition the output of 'inputFragment' before feeding its data into the table sink of the given 'insertStmt'. Considers user-supplied plan hints to determine whether to repartition or not. Returns a plan fragment that partitions the output of 'inputFragment' on the partition exprs of 'insertStmt', unless the expected number of partitions is less than the number of nodes on which inputFragment runs. If it ends up creating a new fragment, appends that to 'fragments'.

Definition at line 181 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.ctx_, com.cloudera.impala.planner.PlannerContext.getNextFragmentId(), com.cloudera.impala.planner.PlannerContext.getNextNodeId(), com.cloudera.impala.planner.DistributedPlanner.getNumDistinctValues(), and com.cloudera.impala.analysis.Expr.isSubset().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createMergeFragment ( PlanFragment inputFragment ) throws InternalException

inlineprivate

Return unpartitioned fragment that merges the input fragment's output via an ExchangeNode. Requires that input fragment be partitioned.

Definition at line 245 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.ctx_, com.cloudera.impala.planner.PlannerContext.getNextFragmentId(), com.cloudera.impala.planner.PlannerContext.getNextNodeId(), and com.cloudera.impala.planner.DataPartition.UNPARTITIONED.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createOrderByFragment	(	SortNode	node,
		PlanFragment	childFragment,
		ArrayList< PlanFragment >	fragments
	)		throws InternalException

inlineprivate

Returns a new unpartitioned fragment that materializes the result of the given SortNode. If the child fragment is partitioned, returns a new fragment with a sort-merging exchange that merges the results of the partitioned sorts. The offset and limit are adjusted in the child and parent plan nodes to produce the correct result.

Definition at line 878 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.createParentFragment(), offset, and com.cloudera.impala.planner.DataPartition.UNPARTITIONED.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createParentFragment	(	PlanFragment	childFragment,
		DataPartition	parentPartition
	)		throws InternalException

inlineprivate

Create a new fragment containing a single ExchangeNode that consumes the output of childFragment, set the destination of childFragment to the new parent and the output partition of childFragment to that of the new parent. TODO: the output partition of a child isn't necessarily the same as the data partition of the receiving parent (if there is more materialization happening in the parent, such as during distinct aggregation). Do we care about the data partition of the parent being applicable to the output of the parent (it's correct for the input).

Definition at line 659 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.ctx_, com.cloudera.impala.planner.PlannerContext.getNextFragmentId(), and com.cloudera.impala.planner.PlannerContext.getNextNodeId().

Referenced by com.cloudera.impala.planner.DistributedPlanner.createAggregationFragment(), com.cloudera.impala.planner.DistributedPlanner.createAnalyticFragment(), and com.cloudera.impala.planner.DistributedPlanner.createOrderByFragment().

ArrayList<PlanFragment> com.cloudera.impala.planner.DistributedPlanner.createPlanFragments ( PlanNode singleNodePlan ) throws ImpalaException

inline

Create plan fragments for a single-node plan considering a set of execution options. The fragments are returned in a list such that element i of that list can only consume output of the following fragments j > i.

TODO: take data partition of the plan fragments into account; in particular, coordinate between hash partitioning for aggregation and hash partitioning for analytic computation more generally than what createQueryPlan() does right now (the coordination only happens if the same select block does both the aggregation and analytic computation).

Definition at line 62 of file DistributedPlanner.java.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createPlanFragments	(	PlanNode	root,
		boolean	isPartitioned,
		long	perNodeMemLimit,
		ArrayList< PlanFragment >	fragments
	)		throws InternalException, NotImplementedException

inlineprivate

Return plan fragment that produces result of 'root'; recursively creates all input fragments to the returned fragment. If a new fragment is created, it is appended to 'fragments', so that each fragment is preceded by those from which it consumes the output. If 'isPartitioned' is false, the returned fragment is unpartitioned; otherwise it may be partitioned, depending on whether its inputs are partitioned; the partition function is derived from the inputs.

Definition at line 93 of file DistributedPlanner.java.

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createScanFragment ( PlanNode node )

inlineprivate

Create new randomly-partitioned fragment containing a single scan node. TODO: take bucketing into account to produce a naturally hash-partitioned fragment TODO: hbase scans are range-partitioned on the row key

Definition at line 264 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.ctx_, com.cloudera.impala.planner.PlannerContext.getNextFragmentId(), and com.cloudera.impala.planner.DataPartition.RANDOM.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createSelectNodeFragment	(	SelectNode	selectNode,
		ArrayList< PlanFragment >	childFragments
	)

inlineprivate

Adds the SelectNode as the new plan root to the child fragment and returns the child fragment.

Definition at line 625 of file DistributedPlanner.java.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

PlanFragment com.cloudera.impala.planner.DistributedPlanner.createUnionNodeFragment	(	UnionNode	unionNode,
		ArrayList< PlanFragment >	childFragments,
		ArrayList< PlanFragment >	fragments
	)		throws InternalException

inlineprivate

Returns a new fragment with a UnionNode as its root. The data partition of the returned fragment and how the data of the child fragments is consumed depends on the data partitions of the child fragments:

All child fragments are unpartitioned or partitioned: The returned fragment has an UNPARTITIONED or RANDOM data partition, respectively. The UnionNode absorbs the plan trees of all child fragments.
Mixed partitioned/unpartitioned child fragments: The returned fragment is RANDOM partitioned. The plan trees of all partitioned child fragments are absorbed into the UnionNode. All unpartitioned child fragments are connected to the UnionNode via a RANDOM exchange, and remain unchanged otherwise.

Definition at line 566 of file DistributedPlanner.java.

References com.cloudera.impala.planner.DistributedPlanner.connectChildFragment(), com.cloudera.impala.planner.DistributedPlanner.ctx_, com.cloudera.impala.planner.PlannerContext.getNextFragmentId(), com.cloudera.impala.planner.PlanFragment.isPartitioned(), com.cloudera.impala.planner.DataPartition.RANDOM, and com.cloudera.impala.planner.DataPartition.UNPARTITIONED.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createPlanFragments().

DataPartition com.cloudera.impala.planner.DistributedPlanner.getCompatPartition	(	List< Expr >	srcJoinExprs,
		DataPartition	srcPartition,
		List< Expr >	joinExprs,
		Analyzer	analyzer
	)

inlineprivate

Returns a new data partition that is suitable for creating an exchange node to feed a partitioned hash join. The hash join is assumed to be placed in a fragment with an existing data partition that is compatible with either the lhs or rhs join exprs (srcPartition belongs to the fragment and srcJoinExprs are the compatible exprs). The returned partition uses the given joinExprs which are assumed to be the lhs or rhs join exprs, whichever srcJoinExprs are not. The returned data partition has two important properties to ensure correctness:

It has exactly the same number of hash exprs as the srcPartition (IMPALA-1307), possibly by removing redundant exprs from joinExprs or adding some joinExprs multiple times to match the srcPartition
The hash exprs are ordered based on their corresponding 'matches' in the existing srcPartition (IMPALA-1324). Returns null if no compatible data partition could be constructed. TODO: Move parts of this function into DataPartition as appropriate. TODO: Make comment less operational and more semantic.

Definition at line 537 of file DistributedPlanner.java.

References com.cloudera.impala.analysis.Analyzer.equivExprs().

Referenced by com.cloudera.impala.planner.DistributedPlanner.createHashJoinFragment().

long com.cloudera.impala.planner.DistributedPlanner.getNumDistinctValues ( List< Expr > exprs )

inlineprivate

Returns the product of the distinct value estimates of the individual exprs or -1 if any of them doesn't have a distinct value estimate.

Definition at line 163 of file DistributedPlanner.java.

Referenced by com.cloudera.impala.planner.DistributedPlanner.createInsertFragment().

boolean com.cloudera.impala.planner.DistributedPlanner.isCompatPartition	(	DataPartition	lhsPartition,
		DataPartition	rhsPartition,
		List< Expr >	lhsJoinExprs,
		List< Expr >	rhsJoinExprs,
		Analyzer	analyzer
	)

inlineprivate

Returns true if the lhs and rhs partitions are physically compatible for executing a partitioned join with the given lhs/rhs join exprs. Physical compatibility means that lhs/rhs exchange nodes hashing on exactly those partition expressions are guaranteed to send two rows with identical partition-expr values to the same node. The requirements for physical compatibility are:

Number of exprs must be the same
The lhs partition exprs are identical to the lhs join exprs and the rhs partition exprs are identical to the rhs join exprs
Or for each expr in the lhs partition, there must be an equivalent expr in the rhs partition at the same ordinal position within the expr list (4. The expr types must be identical, but that is enforced later in PlanFragment) Conditions 2 and 3 are similar but not the same due to outer joins, e.g., for full outer joins condition 3 can never be met, but condition 2 can. TODO: Move parts of this function into DataPartition as appropriate.

Definition at line 498 of file DistributedPlanner.java.

References com.cloudera.impala.analysis.Analyzer.equivExprs().

Referenced by com.cloudera.impala.planner.DistributedPlanner.createHashJoinFragment().

Member Data Documentation

final PlannerContext com.cloudera.impala.planner.DistributedPlanner.ctx_

private

Definition at line 45 of file DistributedPlanner.java.

final Logger com.cloudera.impala.planner.DistributedPlanner.LOG = LoggerFactory.getLogger(DistributedPlanner.class)

staticprivate

Definition at line 43 of file DistributedPlanner.java.

The documentation for this class was generated from the following file:

fe/src/main/java/com/cloudera/impala/planner/DistributedPlanner.java

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation