Anatomy of a Spark-compatible query engine in Rust
// contents
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
| Item | Value |
|---|---|
| Language | Rust, no JVM, no DataFusion |
| Crates in the layer file | 35, of which 2 are test infrastructure (krishiv-testkit, krishiv-sim) |
| Layers | L0 to L7; the layer rule is enforced by a tool in CI |
| Data format in memory | Apache Arrow record batches |
| Plan format between processes | krishiv.plan.v1 (protobuf), versioned |
unsafe allowed in | the memory, allocator, kernels and FFI crates only; every block has a // SAFETY: comment |
| True for | Krishiv 0.2 (embedded) |
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.
- 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. - 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. - 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. - Optimize (
krishiv-optimizer). Rules run in batches to a fixed point: constant folding, predicate pushdown, column pruning, join ordering and a few more.EXPLAIN VERBOSEprints the steps it took. - 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. - 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. - 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. - 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.
krishiv sql for the query above (a pre-release Krishiv 0.2.0 debug build, an empty table). The plan text is shown exactly as printed.How are the crates layered?
| Layer | Crates | Job |
|---|---|---|
| L0 | krishiv-common, krishiv-alloc | errors, config registry, redaction, secrets |
| L1 | types, memory, store, udf-sdk, connector-sdk | data types, memory pools and spill files, object-store settings |
| L2 | kernels, functions, io | cast, datetime, hash, string and decimal kernels; the function registry; Parquet, CSV, JSON, Avro, text scans |
| L3 | sql, plan, optimizer | parse, logical IR, analysis, rules |
| L4 | exec, plan-codec, state, stream | physical plan, operators, codec |
| L5 | session, shuffle, scheduler, connectors | ties a session together; cuts a plan into stages |
| L6 | connect, flight-sql, mcp, server, python, ui-assets | surfaces other programs talk to |
| L7 | krishiv (facade), cli, bench-runner, testkit, sim | what users and tests touch |
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).
xtask/layers.toml and each crate's Cargo.toml. Krishiv 0.2 line.| Layer | Crates in the layer file |
|---|---|
| L0 | alloc, common |
| L1 | connector-sdk, memory, store, types, udf-sdk |
| L2 | functions, io, kernels |
| L3 | optimizer, plan, sql |
| L4 | exec, plan-codec, state, stream |
| L5 | connectors-cdc, connectors-delta, connectors-iceberg, connectors-kafka, scheduler, session, shuffle |
| L6 | connect, flight-sql, mcp, python, server, ui-assets |
| L7 | bench-runner, cli, krishiv, sim, testkit |
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 · 2. This post · 3. Why I built my own CMS.
New deep dives by email
One email per post, no spam, unsubscribe any time.