ExpressionIdAssigner is used by the ExpressionResolver to assign unique expression IDs to NamedExpressions (AttributeReferences and Aliases). This is necessary to ensure that Optimizer performs its work correctly and does not produce correctness issues.

The framework works the following way:

• Each leaf operator must have unique output IDs (even if it's the same table, view, or CTE).
• The AttributeReferences get propagated "upwards" through the operator tree with their IDs preserved.
• Each Alias gets assigned a new unique ID and it sticks with it after it gets converted to an AttributeReference when it is outputted from the operator that produced it.
• Any operator may have AttributeReferences with the same IDs in its output given it is the same attribute. Thus, **no multi-child operator may have children with conflicting AttributeReference IDs**. In other words, two subtrees must not output the AttributeReferences with the same IDs, since relations, views and CTEs all output unique attributes, and Aliases get assigned new IDs as well. ExpressionIdAssigner.assertOutputsHaveNoConflictingExpressionIds is used to assert this invariant.

For SQL queries, this framework provides correctness just by reallocating relation outputs and by validating the invariants mentioned above. Reallocation is done in Resolver.handleLeafOperator. If all the relations (even if it's the same table) have unique output IDs, the expression ID assignment will be correct, because there are no duplicate IDs in a pure unresolved tree. The old ID -> new ID mapping is not needed in this case. For example, consider this query:

SELECT * FROM t AS t1 CROSS JOIN t AS t2 ON t1.col1 = t2.col1

The analyzed plan should be:

Project [col1#0, col2#1, col1#2, col2#3]
+- Join Cross, (col1#0 = col1#2)
   :- SubqueryAlias t1
   :   +- Relation t[col1#0,col2#1] parquet
   +- SubqueryAlias t2
       +- Relation t[col1#2,col2#3] parquet

and not:

Project [col1#0, col2#1, col1#0, col2#1]
+- Join Cross, (col1#0 = col1#0)
   :- SubqueryAlias t1
   :   +- Relation t[col1#0,col2#1] parquet
   +- SubqueryAlias t2
       +- Relation t[col1#0,col2#1] parquet

Because in the latter case the join condition is always true.

For DataFrame programs we need the full power of ExpressionIdAssigner, and old ID -> new ID mapping comes in handy, because DataFrame programs pass _partially_ resolved plans to the Resolver, which may consist of duplicate subtrees, and thus will have already assigned expression IDs. These already resolved duplicate subtrees with assigned IDs will conflict. Hence, we need to reallocate all the leaf node outputs _and_ remap old IDs to the new ones. Also, DataFrame programs may introduce the same Aliases in different parts of the query plan, so we just reallocate all the Aliases.

For example, consider this DataFrame program:

spark.range(0, 10).select($"id").write.format("parquet").saveAsTable("t")
val alias = ($"id" + 1).as("id")
spark.table("t").select(alias).select(alias)

The analyzed plan should be:

Project [(id#6L + cast(1 as bigint)) AS id#13L]
+- Project [(id#4L + cast(1 as bigint)) AS id#6L]
   +- SubqueryAlias spark_catalog.default.t
      +- Relation spark_catalog.default.t[id#4L] parquet

and not:

Project [(id#6L + cast(1 as bigint)) AS id#6L]
+- Project [(id#4L + cast(1 as bigint)) AS id#6L]
   +- SubqueryAlias spark_catalog.default.t
      +- Relation spark_catalog.default.t[id#4L] parquet

Because the latter case will confuse the Optimizer and the top Project will be eliminated leading to incorrect result.

There's an important caveat here: the leftmost branch of a logical plan tree. In this branch we need to preserve the expression IDs wherever possible because DataFrames may reference each other using their attributes. This also makes sense for performance reasons.

Consider this example:

val df1 = spark.range(0, 10).select($"id")
val df2 = spark.range(5, 15).select($"id")
df1.union(df2).filter(df1("id") === 5)

In this example df("id") references lower id attribute by expression ID, so union must not reassign expression IDs in df1 (left child). Referencing df2 (right child) is not supported in Spark.

The ExpressionIdAssigner covers both SQL and DataFrame scenarios with single approach and is integrated in the single-pass analysis framework.

The ExpressionIdAssigner is used in the following way:

• When the Resolver traverses the tree downwards prior to starting bottom-up analysis, we build the mappingStack by calling withNewMapping (i.e. mappingStack.push) for every child of a multi-child operator, so we have a separate stack entry (separate mapping) for each branch. This way sibling branches' mappings are isolated from each other and attribute IDs are reused only within the same branch. Initially we push None, because the mapping needs to be initialized later with the correct output of a resolved operator.
• When the bottom-up analysis starts, we assign IDs to all the NamedExpressions which are present in operators starting from the LeafNodes using mapExpression. createMapping is called right after each LeafNode is resolved, and first remapped attributes come from that LeafNode. This is done in Resolver.handleLeafOperator for each logical plan tree branch except the leftmost.
• Once the child branch is resolved, withNewMapping ends by calling mappingStack.pop.
• After the multi-child operator is resolved, we call createMapping to initialize the mapping with attributes _chosen_ (e.g. Union.mergeChildOutputs) by that operator's resolution algorithm and remap _old_ expression IDs to those chosen attributes.
• Continue remapping expressions until we reach the root of the operator tree.