What is the Catalyst optimizer?

Summary

• Catalyst is the extensible query optimizer inside Spark SQL. SQL statements, DataFrame calls and Dataset code all pass through it, and they share one execution engine whichever language you use.
• Catalyst represents a query as a tree and transforms it with rules in four phases: analysis, logical optimization, physical planning and code generation.
• Logical optimization is rule-based (constant folding, predicate pushdown, projection pruning, null propagation, Boolean expression simplification). Physical planning generates candidate plans and selects one with a cost model.
• Current Spark adds table statistics from ANALYZE TABLE, an optional cost-based optimizer (off by default) and Adaptive Query Execution (on by default since Spark 3.2.0).
• EXPLAIN EXTENDED in SQL, or df.explain(mode="extended") in PySpark, prints the parsed, analyzed, optimized and physical plans.

What is the Catalyst optimizer?

Catalyst is the query optimizer at the core of Spark SQL. It takes what you write in SQL or with the DataFrame and Dataset APIs, represents it as a tree, and rewrites that tree with rules until it has a physical plan Spark can execute. Spark uses the same execution engine whichever API or language expresses the computation, so a PySpark job and the equivalent SQL statement are both optimized by Catalyst. That's also the practical case for DataFrames and SQL over RDD code: Catalyst can only optimize operations whose structure it can see.

How Catalyst is built: trees and rules

The Spark SQL authors laid out Catalyst's design in an April 2015 Databricks engineering post. It had two goals: make it easy to add new optimization techniques to Spark SQL, and let outside developers extend the optimizer. Catalyst is written in Scala and relies on the language's pattern matching to express transformations.
Every query becomes an immutable tree of nodes: attributes, literals, filters, joins, aggregates. A rule is a function from one tree to another tree. Catalyst groups rules into batches and runs each batch until it reaches a fixed point, the moment the tree stops changing. Adding an optimization means adding a rule, not rewriting the planner.

The four phases of Catalyst

Phase	What Catalyst does	Why it matters
Analysis	Resolves table and column references against the catalog and assigns types. An attribute stays unresolved until Catalyst knows its type and which input it comes from.	Errors such as a misspelled column surface here, before any data is read.
Logical optimization	Applies rule-based rewrites to the logical plan: constant folding, predicate pushdown, projection pruning, null propagation and Boolean expression simplification.	Removes work before execution. Filters move toward the data and unused columns are pruned.
Physical planning	Generates one or more physical plans from operators that match Spark's execution engine, then selects one with a cost model.	Decides how the work runs, for example which join algorithm to use.
Code generation	Generates Java bytecode for the selected plan.	In-memory processing is often CPU-bound, and generated code speeds up execution.

What Catalyst works with beyond rules

When that 2015 post was written, cost-based optimization was used only to choose join algorithms. Current Spark surrounds the rule engine with three more inputs:

• Statistics. ANALYZE TABLE ... COMPUTE STATISTICS stores table and column statistics in the catalog, "to be used by the query optimizer to find a better query execution plan."
• Cost-based optimization (CBO). spark.sql.cbo.enabled (default false) enables CBO for estimating plan statistics, and spark.sql.cbo.joinReorder.enabled (default false) adds join reordering. If you enable CBO, keep statistics current.
• Adaptive Query Execution (AQE). Spark SQL re-optimizes the plan in the middle of execution using runtime statistics. It's controlled by spark.sql.adaptive.enabled, on by default since Spark 3.2.0, and it coalesces post-shuffle partitions, converts sort-merge joins to broadcast joins, and splits skewed sort-merge join tasks.

How to see what Catalyst did

from pyspark.sql import functions as F

shipped = (
    spark.table("orders")
    .filter(F.col("status") == "shipped")
    .select("order_id", "amount")
)

shipped.explain(mode="extended")

The extended output has four sections: == Parsed Logical Plan ==, == Analyzed Logical Plan ==, == Optimized Logical Plan == and == Physical Plan ==. Comparing the analyzed and optimized plans shows the rules at work. In SQL, EXPLAIN EXTENDED <statement> prints the same four plans, EXPLAIN FORMATTED splits the physical plan into an outline and node details, and EXPLAIN COST adds statistics when they're available.

Extending Catalyst

Extension points let libraries add SQL behavior without forking Spark. spark.sql.extensions takes a comma-separated list of classes that configure SparkSessionExtensions, and when several extensions add rules or planner strategies, they apply in the order listed. Delta Lake uses this mechanism: you enable it by setting spark.sql.extensions to io.delta.sql.DeltaSparkSessionExtension. For debugging, spark.sql.optimizer.excludedRules disables optimizer rules by name, though rules required for correctness can't be excluded.

How Databricks approaches query optimization

Databricks Runtime includes Apache Spark and adds its own components, so the concepts above, and EXPLAIN, apply on Databricks too. Photon, the Databricks-native vectorized query engine, is compatible with Apache Spark APIs; when it reaches an operation it doesn't support, it falls back to the Spark runtime for the remainder of that operation, and the Spark UI shows Photon operators in their own color in the query DAG. Predictive optimization runs ANALYZE, along with OPTIMIZE and VACUUM, on Unity Catalog managed tables, so statistics get collected without a manually scheduled job.

FAQs

Does Catalyst optimize RDD code?

No. Catalyst works on Spark SQL plans. The RDD API doesn't give Spark information about the structure of the data or the computation, so those optimizations don't apply to it.

Do I need to turn Catalyst on?

No. Every SQL, DataFrame and Dataset query goes through it. You configure the layers around it: AQE is on by default, and CBO and its join reordering are off by default.

Does Spark Connect change how queries are optimized?

No. A Spark Connect client sends unresolved logical plans to the server over gRPC. The server translates them into Spark's logical plan operators, and from there the standard Spark execution process, with all of its optimizations, takes over.