Automatic Encoding Selection for Columnar Storage

The friction you feel comes from three realities: datasets are heterogeneous, distributions drift, and re-encoding large volumes is expensive. Manual encoding selection — a handful of global rules, a spreadsheet of column exceptions, or a single cluster-wide switch — fails because it treats columns as static primitives instead of the high-variance signals they are. The result: wasted terabytes on high-cardinality strings, wasted CPU on non‑vectorizable decoding, and brittle pipelines that break when a new field suddenly becomes high-cardinality or nearly-sorted.

Contents

• Why manual encoding selection breaks at scale
• What to collect at write-time: essential column statistics and sketches
• Designing a practical cost model and robust heuristics
• Where the auto-tuner lives: writer integration and format hooks
• A deployable checklist: practical application, canaries, and rollback

Why manual encoding selection breaks at scale

Manual rules are fragile because they assume a small, stable search space. In practice:

• Column distributions vary widely across tables and over time (IDs, categorical labels, free-form text, timestamps, embeddings). A single rule like “dictionary for strings” either wastes CPU/memory on high-cardinality IDs or misses wins on repetitive status fields. . (parquet.apache.org)
• Encodings interact with compression codecs and page layout: a per-column decision can be suboptimal at page-level, and formats like Parquet expose page metadata you can exploit for skipping and page-level selection. . (parquet.apache.org)
• Writers and downstream readers have different capabilities; picking an encoding the reader can’t handle or that blows writer memory causes operational incidents. Formats such as ORC implement write-time heuristics (e.g., automatic dictionary selection after an initial row group) precisely because static choices fail at production scale. . (orc.apache.org)

Because of these factors, an effective solution must be write-time, per-stream (page/row‑group) and workload-aware — i.e., an auto-tuner.

What to collect at write-time: essential column statistics and sketches

You cannot auto-tune what you haven’t measured. At write time collect a compact set of statistics and sketches that are cheap to compute and that accurately predict encoding behavior on the full block.

Mandatory counters and small aggregates (per page and per-rowgroup):

• num_values, null_count — baseline.
• min, max — needed for predicate-driven page skipping and bit-width computation. . (parquet.apache.org)
• total_bytes, avg_length, std_length — for byte-array cost models.
• distinct_count (approx.) — use HyperLogLog or Theta sketches for memory‑efficient NDV estimates. A compact HLL (~12KB) gives <1% error for large sets. . (redis.io)

Sketches and sample-based structures:

• Top‑K / heavy hitters — maintain a Frequent‑Items or SpaceSaving sketch to detect Zipfian distributions and dominant values that favor dictionary or RLE. Use Apache DataSketches ItemsSketch for production-grade heavy-hitter estimates. . (datasketches.apache.org)
• Quantiles / histograms — use KLL or t‑digest for approximating value distributions and delta distributions (for numeric columns) so you can estimate deltas and bitwidths efficiently. KLL offers provable bounds and very small serialized size. . (datasketches.apache.org)
• Reservoir sample (e.g., 10k–50k records) — keep a uniform sample to simulate compression and encoding on representative data without re-encoding the whole block.
• Run‑length metrics — compute avg_run_length, fraction_covered_by_runs, and longest_run by scanning the sample; these predict RLE effectiveness.
• Delta stability / monotonicity score — for integer/timestamp columns compute the mean and variance of consecutive differences (delta mean and delta stddev). A low delta stddev and a high monotonicity score favour delta encodings.

Operational considerations:

• Collect stats at page granularity when possible: Parquet and ORC support page/stripe metadata and allow page skipping using min/max. Page-level selection increases compression wins at the cost of slightly more metadata. . (parquet.apache.org)
• Emit these summaries to a compact writer-internal metadata structure and to your monitoring pipeline (metrics + log samples) so the auto-tuner can reason about historical behavior without scanning raw files.

Designing a practical cost model and robust heuristics

An auto‑tuner must compare encodings on a common currency. I use a cost model that blends estimated storage and read-time CPU into a single score and then apply safety heuristics.

Core score

• Define a weighted cost:
  • score(enc) = w_bytes * est_bytes(enc) + w_cpu * est_cpu_cycles(enc) * E[reads_per_time]
  • Choose w_bytes and w_cpu to reflect your business priorities (operational cost per GB vs. CPU cost per cycle or per second).
• For many production systems you’ll set w_bytes to the price-per-GB-month (hot storage) and w_cpu to the marginal cost of CPU (or a normalized cycle unit measured from microbenchmarks).

Estimating est_bytes(enc)

• Use the reservoir sample to build a tight estimator:
  • For DICTIONARY: est_bytes ≈ dict_serialized_size + index_bits * N / 8
  • dict_serialized_size = sum(len(unique_value)) + pointer_overheads
  • index_bits = ceil(log2(dict_cardinality))
  • For BIT_PACKED/DELTA_BINARY_PACKED: derive bitwidth = ceil(log2(range_or_delta_range)) and est_bytes ≈ (bitwidth * N) / 8 + header.
  • For RLE: use run statistics: est_bytes ≈ sum(run_headers) + sum(encoded_values_for_runs), simplified to est_bytes ≈ (num_runs * run_header_size) + num_run_values * value_size.
  • After you compute the pre-compression estimate, simulate the selected compression codec against the sample (e.g., compress the encoded sample with ZSTD or Snappy) to estimate final compressed bytes; real compressors are dataset-dependent and the simulation beats analytic guesses.

Estimating est_cpu_cycles(enc)

• Use microbenchmarks (reproducible across your hardware) to measure decode cycles per encoded value for each encoding + compression codec pair. For example, vectorized delta+bitpack decoders show strong SIMD speedups per Lemire and Boytsov’s work on vectorized integer decoding. Use those numbers as priors and re-calibrate with your own microbenchmarks. . (arxiv.org)

A pragmatic pseudo-code scorer

def score_encoding(enc, stats, sample, weights, microbenchmarks):
    bytes_est = estimate_bytes(enc, stats, sample)          # analytic + compress(sample)
    cpu_per_value = microbenchmarks[enc]['decode_cycles']  # measured
    read_cost = weights['read_freq'] * (bytes_est * weights['io_cost_per_byte']
                                        + stats['num_values'] * cpu_per_value * weights['cpu_cost_per_cycle'])
    write_overhead = estimate_write_overhead(enc, stats)   # dictionary build memory/time
    return weights['w_bytes'] * bytes_est + weights['w_cpu'] * read_cost + weights['w_write'] * write_overhead

Heuristics layered over the cost model

• Stability guardrail: require a minimum relative improvement (e.g., 5% combined-score reduction) before switching a stable file format or policy; tiny wins don’t justify operational churn.
• Memory cap: disallow dictionary if estimated dictionary size > configured writer memory fraction.
• Reader compatibility: if any downstream reader doesn’t support DELTA_BYTE_ARRAY or RLE_DICTIONARY for your writer_version, exclude those encodings. Reference the implementation compatibility table before enabling format‑specific encodings. . (parquet.apache.org)
• Workload-aware weighting: if a column is hot in queries (E[reads_per_time] large) bias the model toward CPU‑friendly encodings even if they use a few more bytes; conversely for cold archival tables bias toward smallest bytes.

Contrarian but practical insight

• Don’t over‑dictionary small strings by default. Dictionary encoding looks attractive, but on wide tables you’ll pay dictionary-creation memory and a dictionary page per rowgroup; if cardinality is high, indices can actually cost more than raw strings. A quick distinct_ratio = distinct_count / num_values check avoids this. . (parquet.apache.org)

Where the auto-tuner lives: writer integration and format hooks

Auto-selection belongs in the writer pipeline, with decisions scoped to the smallest unit that is both measurable and practical to re-encode later.

Granularity of decision

• Per-page (finest): maximum compression wins. Parquet and ORC both allow page/stripe encodings and page- or stripe-level metadata for min/max and skipping. Use this when your writer can materialize and inspect page-level samples cheaply. . (parquet.apache.org)
• Per-rowgroup/stripe (practical default): simpler state and metadata. Most production Parquet writers decide per-rowgroup (e.g., 64–256MB row groups).
• Per-file (rare): only for fully immutable archival data where per-column cost is stable.

Integration points and metadata

• Sampling and sketches live in the write buffer (small CPU/memory footprint) and flush into the rowgroup/page metadata. The writer must:
  • Expose a choose_encoding(column_stats, sample) hook that returns the encoding for that page/rowgroup.
  • Record the chosen encoding into the file’s column metadata and (optionally) write a ColumnIndex/PageIndex so readers can skip pages efficiently. Parquet explicitly supports both encodings and page index structures. . (parquet.apache.org)
• Respect writer properties: parquet.enable_dictionary, per-column dictionary_page_size, data_page_row_count_limit, and writer_version influence which encodings are legal and when the writer will gracefully fall back. Many Arrow/Parquet writer implementations provide these knobs. . (arrow.apache.org)

Implementation pattern (event sequence)

1. Buffer rows until page/rowgroup boundary or size threshold.
2. Update sketches and reservoir samples incrementally.
3. At boundary, simulate candidate encodings on the sample and compute score(enc).
4. Apply stability heuristics and choose encoding.
5. Emit pages encoded accordingly and write succinct per-page metadata (min/max, chosen encoding id, dictionary page if used).
6. Persist the sketches/statistics to metrics/monitoring for later analysis or re-tuning.

Interoperability checklist

• Ensure chosen encodings are supported by the consumer stack (Parquet ImplementationStatus and Arrow readers plan compatibility). . (parquet.apache.org)
• Avoid experimental encodings unless you deploy a backward-compatible reader roll-out plan.

A deployable checklist: practical application, canaries, and rollback

A production-safe rollout follows the classic measurement → canary → rollout → monitor → rollback loop, specialized for encodings.

Step 1 — Offline validation

• Use a representative corpus (sample files from recent writes) and run the auto-tuner offline.
• For each column, compute est_bytes(enc) and est_cpu_cycles(enc) and rank encodings. Keep the top‑k candidates and a confidence score derived from sample size.

Step 2 — Microbenchmarks and priors

• Run decode microbenchmarks per encoding + compression pair on your target hardware to fill microbenchmarks[enc]['decode_cycles'] used in the model. Re-run these on major hardware classes (Xeon, Graviton, AMD EPYC) because SIMD characteristics differ. . (arxiv.org)

Step 3 — Canary writes

• Canary by dataset (write new rowgroups with auto-selected encodings for a small percent of traffic) or by rowgroup (one in N rowgroups).
• Monitor: bytes_on_disk, bytes_read_per_query, decode CPU, query latency p50/p95, and predicate pushdown effectiveness (pages skipped). Instrument per-column metrics for a rolling 24–72 hour window.

Step 4 — Acceptance and thresholds

• Define clear pass/fail rules. Example:
  • Accept if combined score improves by ≥ 5% and no client p95 latency regression > 5%.
  • Fail if error rates increase, or memory pressure during writes exceeds safe limits.

Step 5 — Rollback and compaction strategy

• Don’t mutate existing files in-place. Write new files using the chosen encodings and retire old files via a background compaction pipeline. This preserves an easy rollback path: stop using new files and keep old files as the canonical data while investigating.
• If an immediate rollback is needed, mark the auto-tuner decision in a control table and launch a controlled re-encode job to produce replacement files using the safe encoding. Use low‑priority IO and a rate limit to avoid disrupting cluster load.

Safety primitives (must-haves)

Important: Always validate reader compatibility and writer memory constraints before enabling a new encoding in production. Also maintain an audit trail mapping file/rowgroup → chosen encoding for forensic and rollback purposes.

Monitoring signals to watch

• Storage: total bytes / column; compression ratio delta.
• Query performance: decode CPU cycles per query, read bytes per query, p95 latency.
• Operational: write latency, writer OOMs, and dictionary page growth rate.

Example illustrative estimate (one quick mental model)
| Encoding | When it shines | Rough sample estimate formula |
|---|---:|---|
| PLAIN | Very high cardinality strings, random floats | size ≈ N * avg_len |
| DICTIONARY | Low cardinality strings (top‑k heavy) | size ≈ dict_size + N * index_bits/8 |
| DELTA_BINARY_PACKED | Integer sequences with small deltas | size ≈ header + N * avg_delta_bits/8 |
| RLE | Few distinct values in long runs | size ≈ runs * header + distinct_values * value_size |

(Concrete numbers should be computed from your sample + compression sim; the above is illustrative.)

Sources

Parquet encodings and data pages - Official Parquet documentation describing available encodings (DICTIONARY, DELTA_BINARY_PACKED, DELTA_LENGTH_BYTE_ARRAY, RLE, BIT_PACKED) and their characteristics; used to explain encoding capabilities and trade-offs. (parquet.apache.org)

Parquet page index: layout to support page skipping - Documentation of Parquet page/column indices and how min/max statistics enable page skipping; used to justify page-level stats and skipping. (parquet.apache.org)

Arrow Columnar Format - Arrow specification describing dictionary semantics, zero‑copy design, and vectorization-friendly layout; used to justify vectorized decode assumptions and dictionary metadata patterns. (arrow.apache.org)

Apache DataSketches — KLL Sketch documentation - KLL quantiles sketch docs and rationale; used for histogram/quantile sketch recommendations and bounds. (datasketches.apache.org)

Apache DataSketches — Frequent Items (heavy hitters) - Documentation of frequent-items sketches for top-K and heavy-hitter detection; used to recommend heavy-hitter sketches for dictionary/RLE decisions. (datasketches.apache.org)

ORC Specification v1 - ORC file format specification explaining encoding choices and the fact that some ORC writers auto-select encodings after initial stripes; used as an industry example of write-time heuristics. (orc.apache.org)

Decoding billions of integers per second through vectorization (Lemire & Boytsov) - Academic paper describing SIMD‑friendly integer decoding and the performance benefits of vectorized bit-packing/delta schemes; used to inform CPU cost modeling and vectorization priors. (arxiv.org)

Redis HyperLogLog documentation - Explanation of HyperLogLog properties and typical memory/error trade-offs; used to motivate NDV estimation choices. (redis.io)

Parquet implementation status and encodings support table - Compatibility matrix for encodings and compressors across readers/writers; used to advise reader/format compatibility checks. (parquet.apache.org)

Every practical auto-tuner I’ve shipped follows a simple loop: measure small and fast (sketches + samples), predict using a compact cost model (bytes + CPU), canary the change where it matters, and keep an explicit safe rollback path (write new files, retire old ones). Treat encoding selection as an operational control loop — instrument, simulate, canary, and then let the numbers, not gut instinct, drive production encoding decisions.