# colenc · Roadmap

> A pure-MoonBit, zero-FFI **columnar encoding kernel**: the column encodings an
> analytical engine needs, packaged as a reusable, verifiable, pluggable library
>
> Peer references: Parquet's `parquet-encoding` crate, DuckDB's built-in encoders
> License: Apache-2.0

**Status (2026-10)**: project scoped, design settled; **P0 through P4 complete in this package** — every v1 encoding family sits behind the facade dispatch, E1 to E6 are byte-identical to the reference, E7 round-trips with its scoreboard measured, and CI runs the three-backend matrix plus the byte-diff and container jobs
**Integration (P5)**: merged into moonlake's `main` — the Parquet reader routed through colenc, a write path added, and the spill format re-encoded (8.08 → 4.86 MiB on the bake-off workload)
**Release**: `superbigcup325/colenc@0.1.3` supersedes 0.1.2 on mooncakes. It carries the sparse HyperLogLog state: a sketch keeps a sorted array of its live entries and promotes to the dense register array once it outgrows `min(128, m / 8)`, with the hash, the rank rule, the estimator, the merge law and the v1 bytes unchanged. It is a state change inside one sketch, not an interface or format change, so a consumer that pins 0.1.2 upgrades by version alone. **0.1.2** (2026-10-26) shipped the Phase two surface and remains the version every earlier record names: the Roaring index, the bitmap and key-search rewrites, the `sketches` package (HyperLogLog and t-digest), the bitmap dispatch separation and the K1 to K6 kernel work. The archive consumer check exercises the packaged surface — both sketches, the reusable FSST model, the bitmap query APIs and the generic refusal — on all three backends before and after a publication
**Phase two (P6)**: the bitmap index landed — E8 Roaring is byte-identical to CRoaring, container shapes and the run-optimisation rule included, judged by pyroaring
**Follow-through (2026-10-26)**: 0.1.2 is published from `b1b2b7f`, tagged `v0.1.2`, and moonlake consumes it, so the packaging, publication, consumer-acceptance and baseline tasks are complete. [The follow-through record](NEXT-STEPS.md) carries the evidence and current work order, and [the implementation record](OPTIMIZATION-PLAN.md) retains the kernel scope and results. moonlake's 0.6.0 release preparation comes first, followed by a grouped-HLL cost refresh against 0.1.2 and the proposed budgeted-GROUP-BY input work. Neither requires a new kernel release. That refresh met sparse HLL's entry condition, so the two-state sketch shipped in 0.1.3 ([delivery record](NEXT-STEPS.md#sparse-hll-state-delivery-record), [cost table](SKETCHES.md#state-cost)); consumer FSST reuse and the Roaring index experiment remain conditional on consumer evidence

---

## 0. What this is

An analytical engine hands colenc a column of values; colenc produces or restores bytes through pluggable encoding families

The library itself only touches memory buffers (`BytesView` / `Buffer`) — no IO, no file format, no query logic

Three capabilities are why it exists:

- **Value-range narrowing**: pack an Int64 column down to N bits based on its actual range
- **Locality exploitation**: monotonic columns via DELTA, low-cardinality columns via dictionary, floats via byte-plane split
- **Verifiability**: every encoding can be diffed byte-for-byte against a reference implementation and read back in full by DuckDB, and those criteria never regress as the implementation evolves

Terminology: "columnar encoding" in this document always means **intra-column compression** (range narrowing / dictionary / delta / bit packing), never byte-stream compression (the DEFLATE / ZSTD / Snappy / Brotli / LZ4 layer). The two are different layers and can be stacked

## 1. Is / is not

| Is | Is not |
|---|---|
| A columnar encoding kernel (value sequence ⇄ encoded bytes) | A general compression library (bytes in, bytes out) |
| A pluggable set of encoding families behind one interface | A file-format library (no metadata / footer / page directory) |
| Pure MoonBit, zero FFI, identical on native and wasm-gc | A query engine (no planning / execution / optimization) |
| An engineering artifact with objective criteria | An experimental prototype (every encoding must be read back by the judge) |

### The seam with neighbours

| Neighbour | What it does | Where the seam is |
|---|---|---|
| Parquet container library (e.g. `mizchi/parquet`) | file structure, footer, page organization | it owns the container, colenc owns **page-level encoding** — complementary |
| Arrow IPC library (e.g. `MoonArrow`) | inter-process format read/write | IPC is an inter-process format; column encoding is intra-page compression — different layers |
| Byte-stream compressors (DEFLATE / Brotli / ZSTD / gzip family) | compress **bytes** | different layers, composable (column-encode first, then byte-stream compress) |
| Columnar execution engines (e.g. `moonlake`) | planning / execution / optimization | colenc is their storage substrate; the dependency is one-way |

## 2. Encoding family roadmap

Physical types: `Int32` / `Int64` / `Float` / `Double` / `ByteArray` / `Bool`

| # | Family | Applies to | Criteria strength | Status |
|---|---|---|---|---|
| E0 | PLAIN | all | round-trip + container interop | done — container interop |
| E1 | RLE / bit-packed hybrid | Int32/Int64/Bool + levels | round-trip + byte diff | done — byte-identical |
| E2 | Dictionary | low-cardinality ByteArray/Int | round-trip + byte diff | done — byte-identical, per-column fallback |
| E3 | DELTA_BINARY_PACKED | Int32/Int64 | round-trip + byte diff | done — byte-identical |
| E4 | DELTA_LENGTH_BYTE_ARRAY | ByteArray | round-trip + byte diff | done — byte-identical |
| E5 | DELTA_BYTE_ARRAY | ByteArray (shared prefixes) | round-trip + byte diff | done — byte-identical |
| E6 | BYTE_STREAM_SPLIT | Float/Double | round-trip + byte diff | done — byte-identical |
| E7 | FSST | ByteArray (high-cardinality short strings) | round-trip + compression scoreboard | done — round trip + scoreboard, no byte diff (§4 exception) |
| E8 | Roaring bitmap | Int32 ids (a set, not a sequence) | round-trip + byte diff | done — byte-identical to CRoaring, both container modes |

E0–E6 follow the Parquet spec; **choice bits align with the reference implementation** (RLE's run-selection heuristic, the dictionary threshold and bit-width derivation, DELTA's blocks of 128 for INT32 and 256 for INT64, with four miniblocks each). If the choice bits drift, byte diffing becomes meaningless, so these rules are spelled out one by one in the README

E7 FSST is not a native Parquet encoding, so its criteria are downgraded (§4)

E8 is the first phase-two family: a bitmap index rather than a page encoding. It keeps the byte layer by aligning to CRoaring through pyroaring — container shape (array while a container holds 4096 ids, bitmap above), the run-optimisation rule (a run form only when strictly smaller) and the offset-table rule. It has no container-interop layer, because a bitmap index is not a Parquet page encoding, and no slot in the generic `encode_column` / `decode_column` dispatch: its own `encode_roaring_column` / `decode_roaring_column` entry points keep the bitmap out of the call graph of a consumer that only decodes page families

## 3. Stage plan

Every stage has deliverables and an exit criterion, and **no stage starts until the previous one exits**

| Stage | Deliverable | Exit criterion |
|---|---|---|
| **P0** acceptance rig | `harness/`: reference-sample generation, page extraction, byte diffing, a minimal Parquet writer, DuckDB read-back | ① reference extraction is reproducible ② a file we assemble is read back by DuckDB with equal values ③ the extractor can carve out RLE / dictionary / DELTA / BYTE_STREAM_SPLIT pages |
| **P1** framework + E0 + E1 | `primitives/` (varint / zigzag / bit packing / bit width) + PLAIN + RLE hybrid bit packing + the dispatch skeleton | round-trip property and boundary battery all green; E1 byte-identical to the reference implementation; container interop end to end |
| **P2** dictionary | dictionary-page construction + packed indices + threshold fallback | round-trip + byte diff (rules stated explicitly) + a compression ratio for low-cardinality columns |
| **P3** delta family | E3 / E4 / E5 | all three round-trip + byte diff; monotonic-column ratios on the scoreboard |
| **P4** E6 + E7 | BYTE_STREAM_SPLIT + FSST | E6 full criteria; E7 round-trip + scoreboard |
| **P5** integration | consumed by a columnar engine: read-side hookup, write-side additions, spill serialization switched to encodings | consumer regression all green + on-disk size and IO gains recorded |
| **P6** bitmap index (phase two) | E8 Roaring: container shapes, run optimisation, portable serialization, set operations | round-trip properties green; every container shape byte-identical to CRoaring through pyroaring; the fixture generator proves each case still exercises the shape it names |
| **P7** sketches (phase two, implemented in 0.1.1) | Dedicated `sketches` package: HyperLogLog followed by t-digest | Recorded contracts in [SKETCHES.md](SKETCHES.md), register/serialization properties and the HLL statistical rig, then the t-digest structural and empirical-accuracy gates. Independent reference comparisons do not imply byte compatibility |

P0 is the feasibility precondition: if the acceptance rig cannot be made to work, the whole "use a reference implementation as judge" route does not hold, the design needs re-evaluation, and no encodings get piled on top

## 4. The acceptance system

Three layers, each stricter than the last:

| Layer | Means | Exit |
|---|---|---|
| Property | `moonbitlang/quickcheck` round-trip properties (random data covering extremes / empty / all-equal / monotonic / shuffled / very long runs / bit width 0) + a boundary battery | all green, never regressing as the implementation evolves |
| Byte | **byte-level diff** against a reference implementation's output (deterministic encodings; choice-bit rules stated explicitly) | byte-for-byte identical |
| Container | a Parquet file we wrote is read back in full by DuckDB with every value equal (relative tolerance 1e-9); tested in reverse too | provable end to end |

Criteria must not be weakened: a new encoding passes all three layers; if it cannot, it is demoted to the roadmap and declared in this document — the criteria are never bent to fit the implementation

Declared exceptions:

- **E7 FSST**: Parquet has no native FSST, so the byte and container layers do not apply; downgraded to round-trip properties + a compression-ratio / throughput scoreboard
- **Approximate aggregations (HLL, t-digest)**: no Parquet writer emits a sketch, so there is no reference byte stream to diff and no decode path to round-trip through. Criteria are properties plus a statistical rig, recorded in [sketches](SKETCHES.md) before the implementation starts
- **E8 Roaring**: the bitmap is an index, so the Parquet container layer does not apply. Round-trip properties and byte diffs against CRoaring apply to the reference-aligned paths. As documented in the README and harness, sequences such as adding after `run_optimize` can produce legal bytes different from CRoaring; those paths are judged by round trip, container invariants derived from the bytes and operand independence, with a separate layout regression pin

## 5. Scoreboard definitions

- **Compression ratio**: bytes relative to a PLAIN baseline, broken out by column kind (monotonic integer columns / high-cardinality string columns / dictionary-friendly low-cardinality columns / float columns)
- **Throughput**: encode and decode MB/s, listed **separately for native and wasm-gc**
- **Bitmap timing**: the current Roaring decode timer covers `from_bytes` plus `cardinality`, with MB/s normalized to the raw INT32 id size. Expanding the bitmap with `to_array` is outside that timer and needs a separate measurement
- **Integration regression**: the consumer's golden tests stay green

## 6. Explicitly deferred

Not in v1 (the boundary is written down to stop scope creep):

- **Byte-stream compression** (GZIP / ZSTD / Snappy / LZ4 / Brotli) — another layer
- **Full definition / repetition levels for nested types** — v1 handles flat columns only; the interface is reserved but not implemented
- **The Parquet container as a public API** — the acceptance rig's minimal writer makes no stability promise
- **SIMD kernels** — scalar + lookup tables to get the criteria passing first; vectorization is phase two
- **Page-level index / Bloom filter / encryption / column statistics**

Phase two, in progress:

- **Bitmap indexes** — Roaring format, cross-checked against the C/Java implementations file by file. Landed as E8 / P6: portable serialization byte-identical to CRoaring, container shapes and the run-optimisation rule aligned, set operations in place
- **Approximate aggregations**: HLL and t-digest are implemented in `sketches` and published in 0.1.1, with their contracts recorded before implementation. The HLL carries a dense and a sparse register state behind one format, and its rigs judge statistical error, register merge laws, serialization and the per-group state cost; the t-digest rig gates structure and absolute empirical rank-error ceilings while reporting the independent-reference comparison and order/merge spread. SQL adoption belongs to the consumer. See [sketches](SKETCHES.md) and [Next steps](NEXT-STEPS.md) for the current work order

## 7. Engineering conventions

- Zero FFI, zero runtime dependencies (quickcheck allowed at test time; DuckDB is a test-time judge only)
- Everything little-endian, no platform branches; native / wasm-gc / js behave identically
- Decoding errors are typed errors carrying an offset (able to say "byte N, item M"), never a panic
- Pre-commit gate: `moon info && moon fmt && moon check --deny-warn && moon test`

---

*This document is the public roadmap; it is updated as stages progress*

## Final reminder: update benchmarks

The kernel work in the [implementation record](OPTIMIZATION-PLAN.md) is done and
`docs/scoreboard.md` was regenerated after it, with the sketch and bitmap query
costs recorded in the [final record](NEXT-STEPS.md#final-benchmark-record).
Updating moonlake's end-to-end baseline against the actual registry dependency
is done: that project recorded the pair at `4de8077`, and the wide CSV cases came
out 6-11% faster than the 0.1.1 control in every round. The separate
[PLAIN probe](OPTIMIZATION-PLAN.md#exploratory-plain-record) measured a kernel
candidate, not a release or consumer acceptance result.