BtrBlocks: Efficient Columnar Compression for Data Lakes (SIGMOD 2023)

Maximilian Kuschewski and Viktor Leis (TU München) with David Sauerwein and Adnan Alhomssi (FAU Erlangen-Nürnberg). Proc. ACM Manag. Data 1(2), article 118, June 2023. T1, read from the authors' PDF. Open source at github.com/maxi-k/btrblocks.

The successor columnar-format-evaluation asked for: a next-generation format's design paper, from people who are not selling a warehouse.

The premise: parquet is not slow, it is slow per compressed byte

The paper's target is a cloud-specific failure. Networks stopped being the bottleneck — a c5n.18xlarge has 100 Gbit — so what limits an S3 scan is decompression, and "inefficient decompression makes scans CPU-bound and thus increases query time and cost."

The sharpest idea here is a metric correction, and it explains why nobody noticed. Decompression throughput is normally quoted against the uncompressed size, and by that measure every Parquet variant clears 50 GB/s — far above the 12.5 GB/s the network can deliver, so decompression looks free. But data arrives compressed, so the number that decides whether the wire is saturated is

T_c = compressed data size ÷ decompression time

which is T_u divided by the compression factor. Measured that way Parquet+Zstd manages 24.8 Gbit/s against a 100 Gbit link: the better a format compresses, the worse it does on the metric that matters, because the same CPU time now covers fewer bytes off the wire. This is a real trap for this spoke's habit of quoting compression ratios.

The design

Seven existing encodings plus one new one, all chosen for decompression speed and usable in a cascade (RLE, then bit-packing):

Two structural departures from Parquet. Encoding choice is made by sampling, not by hard-coded rules or a user flag: sample multiple small chunks spread across the block, compress the sample with every candidate scheme, take the winner. Sampling ~1% of a 64k block chooses the optimal scheme (or within 2% of it) far more often than sampling one contiguous range does. And metadata is not in the file — BtrBlocks emits only blocks of compressed data, on the argument that statistics and indices should be prunable before a high-latency request, which is precisely the round-trip problem Parquet's footer causes.

What was measured

The Public BI Benchmark — 43 real Tableau workbook tables, 2,451 columns, 119.5 GB in memory — chosen over TPC-H because generated data is unrepresentative: strings are 71.5% of PBI by volume and compress 10.1× on average, against 3.3× in TPC-H, and PBI's denormalised integers compress 5.4× against TPC-H's 1.6×.

Compression ratio, combined, on PBI — and BtrBlocks does not win it:

End-to-end S3 scan of the five largest PBI datasets (whole files, 16 MB chunks, each dataset loaded 10,000 times; c5n.18xlarge at $3.89/h plus $0.0004 per 1,000 GETs):

1.8× cheaper than the best Parquet configuration, 2.6× cheaper than uncompressed Parquet, and at 86 Gbit/s it nearly saturates a link whose ceiling for this client is 91 Gbit/s with no compression at all. No Parquet variant can.

The authors also check the obvious objection — that this is just SIMD. A scalar reimplementation of every decompression routine is 17% slower and still 2.3× faster than the fastest Parquet variant, which is their argument that the gap is in the format rather than in the implementation.

The conclusion the spoke should keep

Asked whether to fix Parquet instead, they answer that they tried to want to:

"improving existing widespread formats such as Parquet is more desirable than creating a new data format: For users, there would be no costly data migration, no breaking changes … Unfortunately, our experiments indicate that low-level improvements are not enough, and integrating larger parts of BtrBlocks … will cause version incompatibilities. Such a 'Parquet v3' would not share much with the original besides the name."

That is the honest version of what a replacement format costs, from the people proposing one.

Caveats

• The authors wrote both sides. BtrBlocks is theirs; the Parquet numbers come from their own harness (Arrow C++ low-level API, rowgroup size tuned to 2^17, parallel over rowgroups and columns). It is a university group with nothing to sell, which is why this reads T1, but nobody independent has re-run it.
• One instance type, one cloud, 2023 prices. The whole argument is calibrated to 100 Gbit networking and a specific cost ratio between compute and requests.
• Compression ratio is a real loss against Zstd on real-world data, and a workload that stores far more than it scans would pay for the speed in storage bills.
• No query engine ran. The benchmark loads and decompresses; the paper says a real OLAP system would widen the gap, and does not show it.

Related

parquet · orc · apache-arrow · columnar-format-evaluation · storage-compute-disaggregation · clickhouse · analytical-databases