Skip to content

Architecture

Keyten is an embedded engine driven primarily through the Python DataFrame/LazyFrame API. Local queries need no server or daemon. The same repository also builds an optional headless worker that accepts serialized plans for collect_on() and collect_distributed(). One engine owns everything from the byte layout of a column to local, spilled, and remote execution.

The system divides into three planes. The data plane defines what a column physically is. The query plane turns an API call chain into an optimized plan and executes it. The runtime owns the shared state both lean on: workers, caches, memory.

The data plane

Every column is a sequence of blocks behind one 64-byte, cache-line-aligned cell header. The header shape never changes; what sits behind it does — each block independently picks the cheapest encoding that describes its rows: constant, arithmetic sequence, bit-packed frame-of-reference, delta, run-length, dictionary codes, short text packed into order-preserving 64-bit words, string views, or plain lanes. Blocks are immutable once published; the reference count is the only thing that ever changes, so sharing a column is a pointer bump and a query result can outlive its source.

Metadata rides the same structure. Blocks carry their own statistics — min/max bounds and attributes like sortedness — that kernels consult before touching a payload. At rest, the native format adds table-level metadata beside the data: ingest-time distinct-count sketches, column-global dictionaries shared by every block of a text column, and per-value block indexes that take a point predicate straight to the blocks that can match. All of it is derived at write time by measurement, none of it is configured, and a reader that predates a metadata kind skips it untouched.

One consequence deserves its own sentence: because the engine computes on the encoded form, a query moves a fraction of the bytes an uncompressed engine moves — and on modern hardware, bytes moved is the budget that runs out first.

The query plane

LazyFrame methods build a plan tree, type-checked eagerly — an unknown column errs where it is introduced, and the error rides the plan to collect(). The optimizer rewrites the tree to a fixed point: constant and identity folding, predicate pushdown (into scans, and through joins exactly where legality allows), projection pruning, slice absorption. Every rewrite must leave the answer identical; optimized plans are continuously verified against their unoptimized twins.

The optimized plan lowers onto a block-parallel pipeline: workers claim block-sized units of work from the source, stream each one through the fused scan predicate and map stages, and push it into the query's sink — the stage that accumulates the answer. Sinks are where execution strategy lives, and there is a family of them: plain table assembly, streaming top-k, global aggregates, a graduated set of grouping engines, sorts, the window barrier, join probe chains, and native-file writers that stream results to disk.

Two ideas repeat across the sinks. First, strategies graduate by measurement: a group-by is served by a hash table of one kind or another — vectorized and columnar in the common case, scattering to per-partition tables when an ingest sketch says the key is high-cardinality, folding runs in place with no hash at all when block metadata proves the key arrives clustered — and a general engine remains as the fallback for the shapes the specialized ones decline. Every strategy is pinned to produce identical results. Second, work is skipped by proof, not hope: zone statistics answer predicates before payloads decode, dictionary-coded text is compared and grouped in the code domain without materializing strings, join probes consult a membership filter before the hash table, and sortedness metadata lets an already-ordered sort return its input.

Barriers — group, sort, window, join build sides — are also where the memory budget bites: each consults a self-derived allowance and spills to disk as ordinary native tables when it would exceed it. Map-only plans never need it; they stream in constant memory.

The runtime

One runtime owns process-wide state: the worker pool and its sizing, and the identity-keyed registries that make repeated queries cheap — assembled-column caches, shared dictionary handles, loaded block indexes. Shared state has one owner by design. Underneath, a block-pool allocator serves the power-of-two buffers the block grid produces.

Cancellation and progress flow through a per-query context, checked at block boundaries: a cancelled query returns at the next one, and progress counts blocks and rows as they pass.

Beyond one machine

The same boundaries extend outward. A plan serializes to a compact versioned wire form; a worker process executes shipped plans and streams sealed result blocks back — the at-rest encodings are the transport, so results travel compressed with no re-encoding step. collect_distributed() partitions eligible native scans, workers compute partial aggregates, and the coordinator merges them through the same sink contracts the parallel executor uses. Unsplittable serializable plans run whole on one worker; process-local plans stay local. See remote and distributed execution for the current boundary.

Invariants worth knowing

  • One cell shape, many encodings. Kernels branch on kind and encoding explicitly; there is no dynamic dispatch in a hot per-block loop.
  • Blocks are immutable once built. Concat, filter, gather, and eager DataFrame mutation publish new cells; existing lazy snapshots keep their old handles.
  • Plans type-check eagerly, execute lazily. Errors are values in the plan, surfaced at collect — nothing panics for ordinary misuse.
  • Every strategy is an optimization, never a semantic. Specialized group engines, encoded-domain fast paths, and spilled execution must all match the naive path bit for bit — except documented float reassociation under parallelism, the one carve-out.
  • Decisions are derived. Encodings, strategy choice, partition counts, and budgets come from measured properties of the data and machine, not from configuration.

Where to look next

The per-topic engine pages go deeper: cells and encodings, the query optimizer, execution and parallelism. Every published performance claim is measured on the public benchmark board, reproducible from a fresh clone.