6 ms·

BtrBlocks: Efficient Columnar Compression for Data Lakes [pdf]

138 points by eatonphil 3y ago

sakras 3y ago
I’ve been really excited about this paper since I went to the presentation at SIGMOD for it. I think the key innovation here is that it’s the first open standard for a format that’s just a simple combination of lightweight encodings. As far as I’m aware, most columnar DBMS already have storage like this, so it’s not very novel from a technical perspective. However, the data science/big data world has been bogged down by inefficient, clunky formats like Parquet for quite a while and so I applaud any steps towards bridging the gap between the two worlds.
- FridgeSeal 3y ago
  On the other hand, the popularity and language-independence of parquet has seen a fantastic explosion of tools/products/libraries that I think is really healthy. Generally with “data stuff” you’re chained to whatever the dominant language and tools do (for the longest time, Python and Spark) and you’d have to accomodate them and their idiosyncrasies directly. Nowadays though, basically everything has a pq lib, there’s tools at all scales: DuckDB, ClickHouse, Databend, etc. The Arrow internal representation of parquet means we’ve escaped the dominance of single massive packages (e.g. pandas and spark dataframes) as the only way to deal with certain datasets. I think it’s great what we’ve managed to get via Parquet, even if it’s a little bit clunky.
  - sanderjd 3y ago
    Yeah I agree with both of you. The data ... milieu is both very frustrating and very exciting at the moment, in my opinion. There is a ton of noise - lots of vendors with big marketing budgets, endless blog spam, etc. - but also quite a bit of real signal - new or remixed stuff compared with 10 or even 5 years ago, that is really useful.
    - FridgeSeal 3y ago
      Yeah the signal/noise ratio is super interesting. The advertising budgets screech real loud, but the interesting things that make it through are real interesting. What I’m very much hoping is things stay in the current style of “mostly” language independent formats and tools. I’ve written more than enough Python and Scala/Spark and I’ve moved on that I don’t ever want to go back to the abysmal landscape that was “Python or bust”.
Loic 3y ago
Corresponding source code: https://github.com/maxi-k/btrblocks https://github.com/maxi-k/btrblocks
j-pb 3y ago
Viktor Leis's working group consistently produces interesting fundamental database research. AdaptiveRadixTries, HeightOptimisedTrees, and the Umbra database system are all done by them.
- giovannibonetti 3y ago
  DuckDB uses Adaptive Radix Trees/Tries: https://duckdb.org/2022/07/27/art-storage.html https://duckdb.org/2022/07/27/art-storage.html
- jandrewrogers 3y ago
  ART is an elegant way of thinking about the problem of index representation. I've been using ART variants for almost 15 years now. The algorithm was somewhat common in supercomputing/HPC (used to index some types of sparse data models), which is where I originally came across it. In addition to being performant, ART is considerably more expressive and flexible than people might assume.
zX41ZdbW 3y ago
It's strange to see no comparison with ClickHouse's MergeTree format in the article.
birdyrooster 3y ago
Turn that data lake into a data lagoon. Are you with me?
- glogla 3y ago
  Only if I can be your data dragoon.
BenoitP 3y ago
So, something between parquet/ORC (a bit more compressed) and arrow (very CPU scan-friendly) I wish we could specify what we intend to do to data, craft a cost model, and let a 4th gen system optimize around that. Something that would pick and choose between the different compression techniques in this paper and also the ones from arrow and parquet.
- abeppu 3y ago
  While I wish there were good principled methods for determining these choices, isn't a meaningful limitation that often when you first start writing the data, you typically don't know all of the ways it will eventually be used? Sometimes, the team tasked with making data available for various forms of bulk processing has to guess at what teams and mandates might exist years from when they are setting up the data lake, or even what compliance requirements will arise. E.g. as different areas introduce data protection laws, perhaps your datalake which could previously assume that records are written but not deleted has to support queries to find PII values associated with a person who has issued a delete request, and you're forced to rewrite lots of files. Or a downstream team starts using vector DBs and wants to assemble datasets by doing queries for records which match any of 100k IDs, which have associated vectors in regions of interest, and you need something that's not a single scan but also not a large number of point lookups. Etc, etc. How do you have a principled method for optimizing for unknown future use cases? Does it make sense to talk about a probability distribution over future queries?
  - hodgesrm 3y ago
    This sounds a lot like Codd's framing of the relational model "problem" in his 1970 ACM paper. [0] His solution was to decouple logical from physical access. That framing and the solution still seem correct to me for the data lake use case. This implies that any lower level storage formats we pick can morph to better optimized forms in a way that does not alter query semantics. It's not possible to solve this without adding refinements to the framing, such as whether data is mutable/immutable, and adding infrastucture to the solution, like metadata management and alternate projections of data. Vertica/C-Store introduced the latter a couple of decades ago. [1] Plus ça change... [0] https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf [1] https://web.stanford.edu/class/cs345d-01/rl/cstore.pdf https://web.stanford.edu/class/cs345d-01/rl/cstore.pdf
wood_spirit 3y ago
Many years back I found that the actual performance of orc and parquet and avro was dominated by the optimisations of the client libraries you used to access them rather than the theoretical pros and cons of the formats themselves. (IIRC on spark chose parquet, on presto choose orc etc?) Hopefully the gaping performance gaps have closed.
- sanderjd 3y ago
  I have spent hours trying to find what I believe must be a memory leak in snowflake's python client that seems to make a query that gets the serialized data (<10GB) locally in under 10 seconds, but requires over a minute to return to the caller. So, yep, this has been my conclusion too!
  - chrisjc 3y ago
    Which Python Client? The one using ADBC/nanoarrow? If not, the issue might be related to converting columnar data to row-based. https://www.youtube.com/watch?v=9FOp160CZYE https://www.youtube.com/watch?v=9FOp160CZYE
- ayhanfuat 3y ago
  This came up in a Twitter discussion, too. Contains a link to an interesting paper which I copied below. > As someone who work with C++ parquet readers and writers I say that different configurations can easily result in 10x differences in size -- the default behavior is usually very poor (Tony Wang / @marsupialtail_2) https://twitter.com/marsupialtail_2/status/1702185015503888391 https://twitter.com/marsupialtail_2/status/17021850155038883... > TUM have written a great summary about performance niches around parquet file IO performance, @DatabendLabs adopted a lot of optimizations mentioned in the summary and result is great in practice. https://dl.gi.de/server/api/core/bitstreams/9c8435ee-d478-4b0e-9e3f-94f39a9e7090/content https://dl.gi.de/server/api/core/bitstreams/9c8435ee-d478-4b... (zhihanz / @zhihanz1205) https://twitter.com/zhihanz1205/status/1702196118472536166 https://twitter.com/zhihanz1205/status/1702196118472536166
wmertens 3y ago
> CONCLUSION > We introduced BtrBlocks, an open columnar compression format for data lakes. By analyzing a collection of real-world datasets, we selected a pool of fast encoding schemes for this use case. Additionally, we introduced Pseudodecimal Encoding, a novel compression scheme for floating-point numbers. Using our sample-based compression scheme selection algorithm and our generic framework for cascading compression, we showed that, compared to existing data lake formats, BtrBlocks achieves a high compression factor, competitive compression speed and superior decompression performance. BtrBlocks is open source and available at https://github.com/maxi-k/btrblocks https://github.com/maxi-k/btrblocks.
- mrits 3y ago
  It is interesting and I'd love to look over some details benchmarks on the differences. Storing floats as integers overcome several of their challenges. The example of dollar units would be a good candidate for a short delta compression. I doubt I'd ever used columnar compression again as I felt it too difficult to fight DBAs on keeping the original sorting and schema preserved in an optimal way. I do find it really interesting though.
326327234723 3y ago
[flagged]
amadio 3y ago
Sad that the author seems to be unaware of similar work, but in high energy physics: https://iopscience.iop.org/article/10.1088/1742-6596/2438/1/012118/meta https://iopscience.iop.org/article/10.1088/1742-6596/2438/1/... (also in arXiv here: https://arxiv.org/abs/2204.09043 https://arxiv.org/abs/2204.09043).
- bastawhiz 3y ago
  How would someone who doesn't subscribe to a journal of physics keep up on these sorts of developments?
  - amadio 3y ago
    By searching for "columnar data" in Google Scholar or even just plain Google, for example. Thorough literature review is a must for any researcher.
    - bastawhiz 3y ago
      I mean, that supposes you're a "researcher". It's a bit of a stretch for a software engineer looking to make their database better to dig into physics work. Which is to say, I can't say it's "sad" that someone wouldn't stray too fast outside their field to find research which isn't well publicized. It's like someone saying "do your own research" to a non technical person about a deeply technical subject.

138 points by eatonphil 3y ago

I’ve been really excited about this paper since I went to the presentation at SIGMOD for it. I think the key innovation here is that it’s the first open standard for a format that’s just a simple combination of lightweight encodings. As far as I’m aware, most columnar DBMS already have storage like this, so it’s not very novel from a technical perspective. However, the data science/big data world has been bogged down by inefficient, clunky formats like Parquet for quite a while and so I applaud any steps towards bridging the gap between the two worlds.

FridgeSeal 3y ago
On the other hand, the popularity and language-independence of parquet has seen a fantastic explosion of tools/products/libraries that I think is really healthy. Generally with “data stuff” you’re chained to whatever the dominant language and tools do (for the longest time, Python and Spark) and you’d have to accomodate them and their idiosyncrasies directly. Nowadays though, basically everything has a pq lib, there’s tools at all scales: DuckDB, ClickHouse, Databend, etc. The Arrow internal representation of parquet means we’ve escaped the dominance of single massive packages (e.g. pandas and spark dataframes) as the only way to deal with certain datasets. I think it’s great what we’ve managed to get via Parquet, even if it’s a little bit clunky.
- sanderjd 3y ago
  Yeah I agree with both of you. The data ... milieu is both very frustrating and very exciting at the moment, in my opinion. There is a ton of noise - lots of vendors with big marketing budgets, endless blog spam, etc. - but also quite a bit of real signal - new or remixed stuff compared with 10 or even 5 years ago, that is really useful.
  - FridgeSeal 3y ago
    Yeah the signal/noise ratio is super interesting. The advertising budgets screech real loud, but the interesting things that make it through are real interesting. What I’m very much hoping is things stay in the current style of “mostly” language independent formats and tools. I’ve written more than enough Python and Scala/Spark and I’ve moved on that I don’t ever want to go back to the abysmal landscape that was “Python or bust”.

Loic 3y ago

Corresponding source code: https://github.com/maxi-k/btrblocks https://github.com/maxi-k/btrblocks

j-pb 3y ago

Viktor Leis's working group consistently produces interesting fundamental database research. AdaptiveRadixTries, HeightOptimisedTrees, and the Umbra database system are all done by them.

giovannibonetti 3y ago
DuckDB uses Adaptive Radix Trees/Tries: https://duckdb.org/2022/07/27/art-storage.html https://duckdb.org/2022/07/27/art-storage.html
jandrewrogers 3y ago
ART is an elegant way of thinking about the problem of index representation. I've been using ART variants for almost 15 years now. The algorithm was somewhat common in supercomputing/HPC (used to index some types of sparse data models), which is where I originally came across it. In addition to being performant, ART is considerably more expressive and flexible than people might assume.

zX41ZdbW 3y ago

It's strange to see no comparison with ClickHouse's MergeTree format in the article.

birdyrooster 3y ago

Turn that data lake into a data lagoon. Are you with me?

glogla 3y ago
Only if I can be your data dragoon.

BenoitP 3y ago

So, something between parquet/ORC (a bit more compressed) and arrow (very CPU scan-friendly) I wish we could specify what we intend to do to data, craft a cost model, and let a 4th gen system optimize around that. Something that would pick and choose between the different compression techniques in this paper and also the ones from arrow and parquet.

abeppu 3y ago
While I wish there were good principled methods for determining these choices, isn't a meaningful limitation that often when you first start writing the data, you typically don't know all of the ways it will eventually be used? Sometimes, the team tasked with making data available for various forms of bulk processing has to guess at what teams and mandates might exist years from when they are setting up the data lake, or even what compliance requirements will arise. E.g. as different areas introduce data protection laws, perhaps your datalake which could previously assume that records are written but not deleted has to support queries to find PII values associated with a person who has issued a delete request, and you're forced to rewrite lots of files. Or a downstream team starts using vector DBs and wants to assemble datasets by doing queries for records which match any of 100k IDs, which have associated vectors in regions of interest, and you need something that's not a single scan but also not a large number of point lookups. Etc, etc. How do you have a principled method for optimizing for unknown future use cases? Does it make sense to talk about a probability distribution over future queries?
- hodgesrm 3y ago
  This sounds a lot like Codd's framing of the relational model "problem" in his 1970 ACM paper. [0] His solution was to decouple logical from physical access. That framing and the solution still seem correct to me for the data lake use case. This implies that any lower level storage formats we pick can morph to better optimized forms in a way that does not alter query semantics. It's not possible to solve this without adding refinements to the framing, such as whether data is mutable/immutable, and adding infrastucture to the solution, like metadata management and alternate projections of data. Vertica/C-Store introduced the latter a couple of decades ago. [1] Plus ça change... [0] https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf [1] https://web.stanford.edu/class/cs345d-01/rl/cstore.pdf https://web.stanford.edu/class/cs345d-01/rl/cstore.pdf

wood_spirit 3y ago

Many years back I found that the actual performance of orc and parquet and avro was dominated by the optimisations of the client libraries you used to access them rather than the theoretical pros and cons of the formats themselves. (IIRC on spark chose parquet, on presto choose orc etc?) Hopefully the gaping performance gaps have closed.

sanderjd 3y ago
I have spent hours trying to find what I believe must be a memory leak in snowflake's python client that seems to make a query that gets the serialized data (<10GB) locally in under 10 seconds, but requires over a minute to return to the caller. So, yep, this has been my conclusion too!
- chrisjc 3y ago
  Which Python Client? The one using ADBC/nanoarrow? If not, the issue might be related to converting columnar data to row-based. https://www.youtube.com/watch?v=9FOp160CZYE https://www.youtube.com/watch?v=9FOp160CZYE
ayhanfuat 3y ago
This came up in a Twitter discussion, too. Contains a link to an interesting paper which I copied below. > As someone who work with C++ parquet readers and writers I say that different configurations can easily result in 10x differences in size -- the default behavior is usually very poor (Tony Wang / @marsupialtail_2) https://twitter.com/marsupialtail_2/status/1702185015503888391 https://twitter.com/marsupialtail_2/status/17021850155038883... > TUM have written a great summary about performance niches around parquet file IO performance, @DatabendLabs adopted a lot of optimizations mentioned in the summary and result is great in practice. https://dl.gi.de/server/api/core/bitstreams/9c8435ee-d478-4b0e-9e3f-94f39a9e7090/content https://dl.gi.de/server/api/core/bitstreams/9c8435ee-d478-4b... (zhihanz / @zhihanz1205) https://twitter.com/zhihanz1205/status/1702196118472536166 https://twitter.com/zhihanz1205/status/1702196118472536166

wmertens 3y ago

> CONCLUSION > We introduced BtrBlocks, an open columnar compression format for data lakes. By analyzing a collection of real-world datasets, we selected a pool of fast encoding schemes for this use case. Additionally, we introduced Pseudodecimal Encoding, a novel compression scheme for floating-point numbers. Using our sample-based compression scheme selection algorithm and our generic framework for cascading compression, we showed that, compared to existing data lake formats, BtrBlocks achieves a high compression factor, competitive compression speed and superior decompression performance. BtrBlocks is open source and available at https://github.com/maxi-k/btrblocks https://github.com/maxi-k/btrblocks.

mrits 3y ago
It is interesting and I'd love to look over some details benchmarks on the differences. Storing floats as integers overcome several of their challenges. The example of dollar units would be a good candidate for a short delta compression. I doubt I'd ever used columnar compression again as I felt it too difficult to fight DBAs on keeping the original sorting and schema preserved in an optimal way. I do find it really interesting though.

326327234723 3y ago

[flagged]

amadio 3y ago

Sad that the author seems to be unaware of similar work, but in high energy physics: https://iopscience.iop.org/article/10.1088/1742-6596/2438/1/012118/meta https://iopscience.iop.org/article/10.1088/1742-6596/2438/1/... (also in arXiv here: https://arxiv.org/abs/2204.09043 https://arxiv.org/abs/2204.09043).

bastawhiz 3y ago
How would someone who doesn't subscribe to a journal of physics keep up on these sorts of developments?
- amadio 3y ago
  By searching for "columnar data" in Google Scholar or even just plain Google, for example. Thorough literature review is a must for any researcher.
  - bastawhiz 3y ago
    I mean, that supposes you're a "researcher". It's a bit of a stretch for a software engineer looking to make their database better to dig into physics work. Which is to say, I can't say it's "sad" that someone wouldn't stray too fast outside their field to find research which isn't well publicized. It's like someone saying "do your own research" to a non technical person about a deeply technical subject.