# Anatomy of a Spark-compatible query engine in Rust

> How a SQL string becomes Arrow batches in a Spark-compatible engine written in Rust: parser, planner, optimizer, executor and the crate layers.

Published 2026-11-17 · Canonical: https://techgopal.com/post/query-engine-anatomy-rust

---

> **Summary.** A SQL string passes through eight steps in Krishiv: entry, parse, analyze, optimize, physical plan, plan codec, execute, output. Each step lives in a crate, and the crates sit in eight layers (L0 to L7) where a crate may depend only on its own layer or a lower one. A tool checks that rule on every change. This post walks one query through the layers and says which parts exist today and which are still placeholders.

## Key facts

## What happens when I run a SQL query?

Take `spark.sql("SELECT l_returnflag, sum(l_quantity) FROM lineitem GROUP BY l_returnflag")`. Eight steps run, in this order.

1. **Entry.** A session receives the string. Python goes through a PySpark-shaped package over PyO3 handles; embedded Rust calls the session directly; the CLI (`krishiv sql`) drives the same session.
2. **Parse** (`krishiv-sql`). A hand-written lexer and parser build an AST with source spans, then a lowering step turns it into the logical IR. The spans are why an error can show the SQL line with a caret under the problem.
3. **Analyze** (`krishiv-plan`). Names are resolved, implicit casts applied, function calls typed against a registry. The registry's arity and availability come from a vendored table taken from Spark, not from my memory of Spark.
4. **Optimize** (`krishiv-optimizer`). Rules run in batches to a fixed point: constant folding, predicate pushdown, column pruning, join ordering and a few more. `EXPLAIN VERBOSE` prints the steps it took.
5. **Physical plan** (`krishiv-exec`). The optimized plan becomes a tree of physical nodes with no live handles in it. Handles (files, memory reservations) are created later, on the worker that runs the plan.
6. **Plan codec** (`krishiv-plan-codec`). The physical plan can be written as protobuf bytes and read back. This is the form a plan takes between processes. The in-process path skips it, and a test keeps the round trip honest.
7. **Execute** (`krishiv-exec`). The operator graph is split into pipelines at "breakers" (aggregate, sort, the build side of a join). An async driver runs each pipeline and checks for cancellation, memory aborts and spill requests at every batch boundary.
8. **Output.** Results are a stream of Arrow record batches. Python reads them through the Arrow PyCapsule interface, so pyarrow, Polars and DuckDB can consume a result without copying buffers.

![EXPLAIN output showing the parsed, analyzed, optimized and physical plans of a group-by query.](/api/v1/media/380349749456273408/raw)

## How are the crates layered?

**FIG. 1** is this table drawn as a dependency diagram: columns are layers, each column depends only on columns to its left, and the arrows show the direct dependencies of one crate (`exec`).

![Layered dependency diagram of the Krishiv crates from L0 on the left to L7 on the right, with arrows from the exec crate to the crates it depends on.](/api/v1/media/380349747971489792/raw)

`krishiv-exec` depends directly on `common`, `functions`, `io`, `kernels`, `memory`, `optimizer`, `plan`, `types` and `udf-sdk`.

## Why enforce layers with a tool?

Because the temptation is constant. The logical plan crate must not know about the Spark Connect wire format, so protobuf is translated at the boundary and the layer file lists `prost`, `tonic` and others as forbidden for `krishiv-plan`. A rule in a document is a wish. A rule that fails the build is a design. The same file keeps the test crates from being depended on by product crates.

## What is not built yet?

The honest list: `krishiv-state`, `krishiv-stream`, `krishiv-flight-sql`, the connector SDK and the four connector crates (Kafka, Iceberg, Delta, CDC) are placeholders with a short `lib.rs`. The scheduler can cut a plan into stages at its exchanges and run them as tasks in one process, but a session still runs every query on one worker. Spark Connect, streaming, incremental views and distributed execution are not in 0.2.

## Why does "Spark-compatible" need so much machinery?

Because compatibility is observable behaviour, not an API list. Integer overflow, string-to-date casts, `NULL` ordering and the hash used by `hash()` (Murmur3 with seed 42) must match, per Spark version. So the function table, the error classes and the golden test data are vendored from Spark's own sources and checked against a real Spark run, and any deliberate divergence is opt-in per expression.

## What should I read next?

The next post in the series is about the CMS, Vyasa. If you want to follow one query in more depth, the Krishiv blog has a post on reading `EXPLAIN ANALYZE`.

*Series: [1. Three projects, one person](/three-projects-one-person) · 2. This post · 3. Why I built my own CMS.*
