OnPair is a Rust codec for compressing string columns while keeping every row independently accessible. It populates a dictionary of up to 2^16 patterns recurring across the column, then encodes each row as a sequence of indices into it. Decoding just looks up each index and copies out the bytes, so columns decompress at high throughput, and any single row can be read or dropped without touching the ones around it.
- Fast decompression. The decoder looks up each index and copies out the bytes, with no entropy-decoding stage in the hot path, so decoding sustains high throughput.
- Random access. Each row is a self-contained run of codes, so it decodes on its own, with no block to unpack and no neighbours to rebuild.
- Efficient compression. OnPair reaches ratios competitive with far heavier methods while keeping its encoding pass fast, so strong compression comes at a fraction of the usual cost.
- Compressed-domain search. Evaluate equality, prefix, and substring predicates without decoding rows back to bytes.
OnPair is designed for high-cardinality columns, whose many distinct values tend to share substrings rather than repeat in full. On low-cardinality columns it is better to deduplicate first: encode the column as references to the distinct values, then run OnPair over that set of unique strings. Deduplication removes the value-level repetition, and OnPair compresses the substring redundancy that remains.
Benchmarks comparing OnPair against the main comparable string-compression algorithms are in progress.
cargo add onpairuse onpair::{compress, Config, DECODE_PADDING};
// Three values in the Arrow layout OnPair takes: one byte buffer plus offsets.
let values = b"catdogbird";
let offsets = [0u32, 3, 6, 10]; // "cat", "dog", "bird"
let column = compress(values, &offsets, Config::default()).unwrap();
let view = column.view();
// A value decodes to its original length, so a buffer of the longest value plus
// DECODE_PADDING (which absorbs the decoder's 16-byte tail write) fits any row.
let max_len = 4; // longest value in this column
let mut decoded = Vec::<u8>::with_capacity(max_len + DECODE_PADDING);
// SAFETY: capacity >= this row's decoded length + DECODE_PADDING.
let len = unsafe { view.decompress_row_into(1, decoded.spare_capacity_mut()) };
unsafe { decoded.set_len(len) }; // SAFETY: decode initialized `len` bytes.
assert_eq!(decoded, b"dog");Config::default() caps the dictionary at 2^12 entries; raise max_dict_bits
for a larger one, up to 2^16.
- In-memory interchange format
- OnPair: Short Strings Compression for Fast Random Access
- C++ reference implementation
OnPair is licensed under Apache-2.0.