catalyst

sql/catalyst/ is Spark's tree-rewrite framework. It defines the logical plan, the expression tree, the analyzer, the rule-based optimizer, and the data types that flow through SQL queries. Catalyst is implementation-agnostic - the same trees back the classic SparkSession and the Spark Connect client.

Purpose

• Provide a generic TreeNode[T] substrate for plan and expression trees.
• Parse SQL into an unresolved tree.
• Resolve identifiers, types, and references against a catalog.
• Apply a fixed set of rule batches that rewrite the plan.
• Define the public type system that the rest of the SQL stack uses.

Directory layout

sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/
  trees/                       - TreeNode, TreePattern, RuleExecutor base
  rules/                       - Rule, RuleExecutor, batch infrastructure
  expressions/                 - Expression hierarchy (Literal, Add, If, ...)
  expressions/codegen/         - per-expression code generation
  expressions/aggregate/       - aggregate functions
  plans/logical/               - LogicalPlan and operators (Project, Filter, Join, ...)
  plans/physical/              - Physical-plan-side support types (Distribution, Partitioning)
  analysis/                    - Analyzer, FunctionRegistry, ResolveReferences, etc.
  optimizer/                   - Optimizer batches and rules
  parser/                      - ANTLR grammar (.g4) and ParserDriver
  catalog/                     - SessionCatalog, ExternalCatalog (Hive bridge entry)
  encoders/                    - ExpressionEncoder for Dataset[T]
  csv/, json/, xml/            - Per-format option/parser support shared with sql/core
  rules/                       - rule infrastructure shared by analyzer and optimizer
  util/                        - DateTimeUtils, NumberUtils, ArrayBasedMapData, ...
  types/                       - DataType subclasses
  streaming/                   - StreamTest plumbing for catalyst-only tests

Key abstractions

Type / file	What it is
TreeNode[T] (sql/catalyst/.../trees/TreeNode.scala)	Base of every plan and expression node.
Rule[T] (sql/catalyst/.../rules/Rule.scala)	A function from tree to tree that runs in the RuleExecutor.
RuleExecutor[T] (sql/catalyst/.../rules/RuleExecutor.scala)	Runs Batches of rules to a fixed point or a max iteration.
LogicalPlan (sql/catalyst/.../plans/logical/LogicalPlan.scala)	Base of all logical operators.
Expression (sql/catalyst/.../expressions/Expression.scala)	Base of everything that produces a value.
Analyzer (sql/catalyst/.../analysis/Analyzer.scala)	Walks an unresolved plan and resolves it.
Optimizer (sql/catalyst/.../optimizer/Optimizer.scala)	Applies the canonical rule batches to a resolved plan.
SessionCatalog (sql/catalyst/.../catalog/SessionCatalog.scala)	The runtime catalog facade used by the analyzer.
FunctionRegistry (sql/catalyst/.../analysis/FunctionRegistry.scala)	Built-in and user-registered SQL functions.
ParserInterface (sql/catalyst/.../parser/ParserInterface.scala)	The pluggable parser entry point. Default impl uses ANTLR.
ExpressionEncoder[T] (sql/catalyst/.../encoders/ExpressionEncoder.scala)	Converts JVM objects to/from InternalRow for Datasets.

How a plan is built

graph TD
    A[SQL string] -->|"AstBuilder + ANTLR"| B["Unresolved LogicalPlan"]
    BD[DataFrame DSL] --> B
    B --> C[Analyzer]
    C -->|"resolve relations, references, functions"| D[Resolved LogicalPlan]
    D --> E[Optimizer]
    E -->|"PushDownPredicate, ColumnPruning, ConstantFolding, ..."| F[Optimized LogicalPlan]
    F --> G[Hand-off to SparkPlanner in sql/core]

Analyzer batches

The analyzer (sql/catalyst/.../analysis/Analyzer.scala) declares a sequence of named batches. Frequently-edited rules:

• ResolveRelations - turn UnresolvedRelation into a concrete table/view.
• ResolveReferences - bind column names to ordinal positions.
• ResolveFunctions - look up UDFs and built-ins in FunctionRegistry.
• TypeCoercion rules (in analysis/TypeCoercion.scala) - apply implicit casts.
• CleanupAliases - drop redundant Alias wrappers before optimization.

Failures here become AnalysisExceptions and are mapped through the error-class system in sql/catalyst/.../errors/.

Optimizer batches

Optimizer runs a long list of batches (Operator Optimization, Subquery, Decorrelate Inner Query, Replace Operators, ...). Common rules:

• ColumnPruning - drop columns that nothing reads.
• PushDownPredicate - move filters past joins and aggregations.
• ConstantFolding - evaluate Literal-only subtrees at plan time.
• OptimizeIn - rewrite IN with many literals to a hash-set lookup.
• RewritePredicateSubquery - rewrite correlated subqueries to joins.

Rules are kept idempotent and visit-bounded with TreePattern bits (sql/catalyst/.../trees/TreePatternBits.scala) to skip irrelevant subtrees.

Code generation

Each Expression may implement doGenCode(ctx, ev): ExprCode. The shared CodegenContext (sql/catalyst/.../expressions/codegen/CodegenContext.scala) collects the generated source lines, common imports, and helper functions. The actual JVM compilation is done at the sql/core level by WholeStageCodegenExec using Janino.

Type system

sql/api/src/main/scala/org/apache/spark/sql/types/ declares the public DataType hierarchy (IntegerType, StringType, ArrayType, StructType, MapType, VariantType, ...). sql/catalyst/.../types/ adds catalyst-specific helpers and the DataTypeUtils extension points. Schema inference and JSON/CSV parsing all funnel through these types.

Catalog plumbing

SessionCatalog mediates between the analyzer and the underlying catalog provider. The default in-memory provider is InMemoryCatalog. HiveExternalCatalog (in sql/hive) is the production provider that talks to a Hive metastore.

For DataSource V2, the analyzer also consults the v2 CatalogManager/CatalogPlugin API (sql/catalyst/.../connector/catalog/).

Integration points

• Imported by sql/core (the analyzer and optimizer are run from there) and by sql/connect/server (which translates protobuf into Catalyst commands).
• Has no dependency on core/; that one-way arrow is enforced by the build to keep Catalyst usable in environments without a SparkContext (notably the Connect client).
• The MLlib pipeline writers serialize Catalyst types when materializing models to Parquet.

Entry points for modification

• Add a new logical operator: subclass LogicalPlan, give it an analyzed flag, and update the relevant rule in Analyzer so it gets resolved.
• Add a new optimizer rule: extend Rule[LogicalPlan], register it in Optimizer.batches, and add a unit test in sql/catalyst/src/test/.../optimizer/.
• Add a SQL function: add an Expression subclass under expressions/, register it in FunctionRegistry, add docs to gen-sql-functions-docs.py, and add a golden-file test.
• Modify the parser: edit the ANTLR grammar in sql/catalyst/.../parser/SqlBaseParser.g4 and the corresponding AstBuilder.scala. Run build/sbt catalyst/compile to regenerate.