Columnar execution · Rust core
Fast CPUs wait on RAM.
Keyten moves fewer bytes.
Keyten is a compact Rust dataframe engine that keeps columnar data compressed through scans, joins, grouping, windows, and time-series work.
pip install keyten64 bytesper Cell header
2,048 rowsper block
13block encodings
Out of coreautomatic spilling
Architecture
One 64-byte cell,
from disk to kernel.
Columns are split into 2,048-row blocks. Every block begins with a 64-byte, cache-line-aligned Cell that also serves as its on-disk record and in-memory header. Native reads mmap those records. Untouched blocks pass through a query by reference, and sealed result blocks can travel over the wire in the same format.
Kernels can work on the encoding itself. A frame-of-reference block sums as base × count + Σ residuals. Short strings pack into a u64 whose integer order matches lexical order, so comparisons, groups, and joins use the integer paths. Strings materialize when a consumer asks for them.
struct Cell64 bytes · exactly one cache line
- identity + length:
kind, enc, attrs, rc, len - payload pointer + size, absent for Constant and Sequence
meta[32]: zone map, encoding parameters, small values inline
Encodings
Every block picks
its own encoding.
Every 2,048-row block chooses an encoding from its values. Neighbors may disagree. One run of IDs can become Sequence, while the next block collapses thousands of repeated values into a payload-free Constant header. Try each data shape and watch the builder choose.
the block2,048 rows
7 7 7 7 7 7 7 7 7 7 7 7 …
builder: one distinct → Constant { 7 }
the choiceCONST
One value rides in the header. The block allocates zero payload bytes.
The writer makes column-wide choices too. It records a distinct-count sketch, then adds a global dictionary, an FSST symbol table, or a per-value block index when the measured cost says the structure will pay for itself. Their calibration constants live in one cost model, with the source for each number beside it.
Statistics
Prove which blocks
need decoding.
Keyten checks statistics first. A zone map can settle an entire comparison while its payload remains sealed. For equality checks, per-value block indexes point straight at the few blocks that might match, while projection pushdown leaves every unused column file closed.
Parquet scans follow the same path. Keyten reads pages natively, seals them into its encodings, and builds zone maps as it goes, which lets footer statistics eliminate entire row groups. For some files, count, min, and max come from the footer alone.
df.filter(kt.col("px") > 250)zone maps, one column
Only two payloads need decoding. Five blocks fall entirely below 250. Block b03 sits above it and produces a constant-true mask from metadata.
Execution
One block size,
across the whole query.
The executor works in storage-sized blocks. Workers pull them through fused filter and map stages, then feed aggregation, sort, window, or join sinks. At those same boundaries, Keyten reports progress, checks for cancellation, and adjusts parallelism to fit the machine running the query.
Stateful operators get a budget from the host. When a sort, group-by, or join outgrows that budget, it writes ordinary native tables to disk and continues from there.
one query, every corework-stealing workers
blocks 1,481 / 4,096 · rows 3.0Mcancel lands at the next block boundary
Data can outgrow RAM. Sorts write and merge runs. Group-bys and joins partition to disk, while map pipelines stream with constant memory.
Scale
Run the same plan
on a worker fleet.
A single machine eventually runs into its memory bandwidth. collect_distributed() serializes the lazy plan, sends native-scan fragments to a supplied worker list, and streams compressed result blocks back to the caller. Decomposable aggregates merge across the fleet. A serializable plan that cannot split runs whole on one worker; an in-memory plan stays local. distributed execution: landing · under active development
the querylazy plan
query = (
kt.scan_native("trades.k10dir")
.filter(kt.col("qty") > 100)
.group_by("sym")
.agg(kt.col("notional").sum())
)plan ⇢ versioned wire form · results ⇠ compressed blocks
laptopevery core
query.collect()
One process. Keyten selects parallelism and a spill budget from the host.
fleetown channels each
query.collect_distributed(workers)
Workers compute mergeable partial aggregates in the same engine. Unsplittable file plans run whole on one worker.
Proof
The claims come with
tests and scripts.
The test suite runs every rewritten plan beside the original and compares their results, which catches an optimizer rule that changes the answer. explain() prints the plan before it runs. Published benchmark results include the commands needed to reproduce them from a fresh clone.
collect(optimize(plan))≡collect(plan)
bit-exact · enforced across the test suite
pip install keyten