skip to content
techgopal
rss
// FEATURE

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

ItemValue
LanguageRust, no JVM, no DataFusion
Crates in the layer file35, of which 2 are test infrastructure (krishiv-testkit, krishiv-sim)
LayersL0 to L7; the layer rule is enforced by a tool in CI
Data format in memoryApache Arrow record batches
Plan format between processeskrishiv.plan.v1 (protobuf), versioned
unsafe allowed inthe memory, allocator, kernels and FFI crates only; every block has a // SAFETY: comment
True forKrishiv 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.

  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.
Real output of 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?

LayerCratesJob
L0krishiv-common, krishiv-allocerrors, config registry, redaction, secrets
L1types, memory, store, udf-sdk, connector-sdkdata types, memory pools and spill files, object-store settings
L2kernels, functions, iocast, datetime, hash, string and decimal kernels; the function registry; Parquet, CSV, JSON, Avro, text scans
L3sql, plan, optimizerparse, logical IR, analysis, rules
L4exec, plan-codec, state, streamphysical plan, operators, codec
L5session, shuffle, scheduler, connectorsties a session together; cuts a plan into stages
L6connect, flight-sql, mcp, server, python, ui-assetssurfaces other programs talk to
L7krishiv (facade), cli, bench-runner, testkit, simwhat 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).

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.
FIG. 1. The Krishiv crates by layer, read from xtask/layers.toml and each crate's Cargo.toml. Krishiv 0.2 line.
LayerCrates in the layer file
L0alloc, common
L1connector-sdk, memory, store, types, udf-sdk
L2functions, io, kernels
L3optimizer, plan, sql
L4exec, plan-codec, state, stream
L5connectors-cdc, connectors-delta, connectors-iceberg, connectors-kafka, scheduler, session, shuffle
L6connect, flight-sql, mcp, python, server, ui-assets
L7bench-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.

// subscribe