Plan nodes

Goal

Document what the plan nodes mean.

This is useful because the plan is the interface between the planner, the optimizations, and the evaluator; thus, components need to be written to a common understanding of the plan's meaning.

The information would be better located in comments in the nodes' source files.

Common fields

PlanNodeId id
- Must be unique within a given plan tree
List outputSymbols

Nodes

In the order they appear in PlanNode.java

A check mark ✓ indicates that the description of the node is complete.

OutputNode ✓

Returns rows back to the user as a side effect. The columns sent to the user are those of its output symbol list.

Fields:

PlanNode source
List columnNames
- Labels for the returned columns, in a parallel list to the output symbols list

ProjectNode ✓

Creates new columns as functions of existing ones.

Fields:

PlanNode source
Assignments assignments
- maps Symbol to defining Expression

TableScanNode

Reads rows in from a table provided by a connector.

Fields:

TableHandle table
- TODO this should be some specification of the table, as opposed to a transaction-scoped execution object, so that unit tests don't have to create transactions just to make plans.
Optional tableLayout
- TODO Why is this optional?
Map<Symbol, ColumnHandle> assignments
- the columns that are being read from the Table
TupleDomain currentConstraint
- temporary field used during predicate pushdown?
Expression originalConstraint
- for human-readable output of pushed-down predicate

ValuesNode

Produces a literal sequence of rows.

Fields:

List<List> rows
- Columns are parallel to the output symbol list

AggregationNode

For each set of grouping keys:

For each bag of rows with common values of the grouping:
- Feed that bag of rows into a set of aggregators, with each producing a single column.

Produces a column for each aggregation, and for each of the keys used in any grouping set.

Implemented by HashAggregationOperator, or for an empty set of grouping keys, AggregationOperator.

TODO fix comment at the top of AggregationOperator.java
TODO why does HashAggregationOperator have getGlobalAggregationOutput, if global aggregation uses AggregationOperator instead?

HashAggregationOperator is implemented by either SpillableHashAggregationBuilder or InMemoryHashAggregationBuilder, depending on the Session's "spill_enabled" property. Presumably the future goal is for that to be determined by the planner and/or executor.

As a special case, for FINAL/SINGLE aggregation with an empty set of grouping keys, it produces a single row.

TODO why not handle that in the translation from SQL? Because it's implied by handling multiple grouping sets within a single plan node?

TODO what about null values of the grouping keys?

Fields:

PlanNode source
Map<Symbol, Aggregation> assignments
- FunctionCall call
- Signature signature
- Optional mask
  - A boolean used for implementing per-aggregate FILTER clauses (coming from a boolean projection), or for implementing DISTINCT aggregators (coming from a MarkDistinctNode)
List<List> groupingSets
Step step { PARTIAL, FINAL, INTERMEDIATE, SINGLE }
- An AggregationNode is either SINGLE, or a part of a sequence: PARTIAL, INTERMEDIATE*, FINAL
- Note that this is global across all aggregations done by this node
Optional hashSymbol
- If specified, the node will expect, and pass through, a column with a hash of the all of the keys used in any grouping set, for each input row. This can save work if the same hash can be used e.g. for aggregation and exchange.
  - TODO what about multiple grouping sets? Which input row's hash gets passed through for a less specific grouping set?
Optional groupIdSymbol
- If there are multiple grouping sets, this output column will produce a unique value for each of the grouping sets
  - TODO add verify check to AggregationNode ctor that this is present iff there are multiple grouping sets.

MarkDistinctNode ✓

Projects on the markerSymbol, which is a boolean which is true for only one row per unique combination of distinctSymbols.

Uses:

to create a masking flag for use with a DISTINCT aggregator.
in scalar correlated subqueries

Fields:

PlanNode source
Symbol markerSymbol
List distinctSymbols
Optional hashSymbol

FilterNode ✓

Only passes rows for which the boolean predicate is non-null and true.

Fields:

PlanNode source
Expression predicate

WindowNode

Fields:

PlanNode source
Set prePartitionedInputs
Specification specification
- List partitionBy
- List orderBy
- Map<Symbol, SortOrder> orderings
  - SortOrder is actually a collation (ascending/descending, and nulls first/last), and doesn't specify what to order on.
    - TODO Presumably this is actually just the collations, parallel to the orderBy list?
int preSortedOrderPrefix
Map<Symbol, Function> windowFunctions
- Function fields:
  - FunctionCall functionCall (type shared with simple row expressions)
    - QualifiedName name
    - Optional window
      - List partitionBy
      - Optional orderBy
        
        List sortItems
        
        Expression sortKey
        
        Ordering ordering {ASCENDING, DESCENDING}
        
        NullOrdering nullOrdering {FIRST, LAST, UNDEFINED}
      - Optional frame
        
        Type type {RANGE, ROWS}
        
        FrameBound start
        
        Type type {UNBOUNDED_PRECEDING, PRECEDING, CURRENT_ROW, FOLLOWING, UNBOUNDED_FOLLOWING}
        
        Optional value
        
        Optional originalValue
        
        Optional end
    - Optional filter
    - boolean distinct
    - List arguments
  - Signature signature
  - Frame frame
    - WindowFrame.Type type {RANGE, ROWS}
    - FrameBound.Type startType {UNBOUNDED_PRECEDING, PRECEDING, CURRENT_ROW, FOLLOWING, UNBOUNDED_FOLLOWING}
    - Optional startValue
    - FrameBound.Type endType
    - Optional endValue
Optional hashSymbol

RowNumberNode

foo

TopNRowNumberNode

foo

LimitNode

foo

DistinctLimitNode

foo

TopNNode ✓

Passes the top count rows according to the given order.

Fields:

PlanNode source
long count
List orderBy
Map<Symbol, SortOrder> orderings
- actually the collations of the columns in the orderBy
Step step { PARTIAL, FINAL, SINGLE }
- A TopNNode is either SINGLE, or a part of a sequence: PARTIAL, FINAL

SampleNode

foo

SortNode

foo

RemoteSourceNode

foo

JoinNode ✓

Implements either cross join or hash join or spatial join.

For hash join, it builds up the hash table from the right child, and then streams through the rows of the left child.

A "match" occurs if all the equijoin criteria match, and the filter evaluates to true. An equijoin criterion does not match if one of the join keys are null.

The outer join types produce an output row even when there is not a match, filling in the other side with nulls.

For spatial join, it builds up the R-Tree from the right child, and then streams through the rows of the left child. The equijoin criterion must be empty. The filter must be made of conjuncts one of which represents a spatial relationship ST_Contains, ST_Intersects or ST_Distance.

The arguments of the spatial function must be non-scalar expressions. One of the arguments must use symbols from left side of the join, the other from right side.

Spatial relationship expressed using ST_Distance function must use less than or less than or equals operator to compare ST_Distance value with a radius. The radius must be either scalar expression or must use symbols only from the right (build) side of the join.

A "match" occurs if spatial relationship holds and the remainder of the filter evaluates to true.

Fields:

Type type {InnerJoin, LeftJoin, RightJoin, FullJoin}
PlanNode left
PlanNode right
List criteria
- Symbol left
- Symbol right
List outputSymbols
- Symbols from left, then symbols from right
Optional filter
Optional leftHashSymbol
Optional rightHashSymbol
Optional distributionType {PARTITIONED, REPLICATED}
- Set by DetermineJoinDistributionType optimization, and then used by the AddExchanges optimization to enforce partitioning of children

SemiJoinNode

Builds a hash table of the keys in filteringSource, and projects onto each row from source a boolean which says whether the key matched in the hash table. That boolean is null if the key is null in the source.

Rationale for producing a boolean: use of CASE with IN: https://blogs.msdn.microsoft.com/craigfr/2006/08/23/subqueries-in-case-expressions/

Fields:

PlanNode source
PlanNode filteringSource
Symbol sourceJoinSymbol
Symbol filteringSourceJoinSymbol
Symbol semiJoinOutput
- TODO assert that this is boolean in ValidateDependenciesChecker or some other place
Optional sourceHashSymbol
Optional filteringSourceHashSymbol
Optional distributionType {PARTITIONED, REPLICATED}
- Set by DetermineJoinDistributionType optimization, and then used by the AddExchanges optimization to enforce partitioning of children

IndexJoinNode

Raptor only, going away in some future Raptor v2

Output includes all symbols from both sources.

Type type {INNER, SOURCE_OUTER}
PlanNode probeSource
PlanNode indexSource
List criteria
Optional probeHashSymbol
Optional indexHashSymbol

IndexSourceNode

Raptor only, going away in some future Raptor v2

Fields:

IndexHandle indexHandle
TableHandle tableHandle
Optional tableLayout
- "Only necessary for event listeners"
Set lookupSymbols
- Must be included in outputSymbols, and in keys of assignments
List outputSymbols
Map<Symbol, ColumnHandle> assignments
TupleDomain effectiveTupleDomain
- "General summary of how the output columns will be constrained"

TableWriterNode

foo

DeleteNode

foo

MetadataDeleteNode

foo

TableFinishNode

foo

UnnestNode

foo

ExchangeNode

Fields:

Type type {GATHER, REPARTITION, REPLICATE}
Scope scope {LOCAL, REMOTE}
List sources
- The exchange node consumes the union of all the rows provided by the sources. The columns are matched up by position in the "inputs" list entries.
- TODO Why not use a child UnionNode instead?
PartitioningScheme partitioningScheme
- Partitioning partitioning
  - PartitioningHandle handle
    - Optional connectorId
    - Optional transactionHandle
    - ConnectorPartitioningHandle connectorHandle
      - boolean isSingleNode()
      - boolean isCoordinatorOnly()
  - List arguments
    - Each ArgumentBinding has a non-null value of exactly one of:
      - Symbol column
      - NullableValue constant
- List outputLayout
  - These are the output columns of the ExchangeNode
- Optional hashColumn
  - If present, it must be contained in the outputLayout
- boolean replicateNulls
- Optional<int[]> bucketToPartition
List<List> inputs
- Parallel to the sources

UnionNode

foo

IntersectNode

foo

EnforceSingleRowNode

foo

GroupIdNode

foo

ExplainAnalyzeNode ✓

Waits for the query to finish, then outputs a single row with a single symbol, containing a string describing the plan.

Fields:

PlanNode source
Symbol outputSymbol

ApplyNode

Invokes an anonymous function whose body is the subquery. Contains an input relation as its left child, a subquery relation as its right child and a parameter (correlation) map.

see https://docs.google.com/document/d/18HN7peS2eR8lZsErqcmnoWyMEPb6p4OQeidH1JP_EkA/edit#