[HN Gopher] BtrBlocks: Efficient Columnar Compression for Data L...
___________________________________________________________________
BtrBlocks: Efficient Columnar Compression for Data Lakes [pdf]
Author : eatonphil
Score : 118 points
Date : 2023-09-16 11:08 UTC (11 hours ago)
(HTM) web link (www.cs.cit.tum.de)
(TXT) w3m dump (www.cs.cit.tum.de)
| BenoitP wrote:
| 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.
| thesz wrote:
| We, probably, will be even better off by leaving cost model
| craft to the system.
|
| I recently had to look into various TPC benchmarks and some of
| them are very non-trivial to cost-estimate. I found at several
| queries in TPC-DS that join the same table to itself four (4)
| times. Even triangles (join with itself three times) are hard,
| squares like these in TPC-DS are even harder.
| datadeft wrote:
| I would be happy if Parquet or ORC was used in most DWHs. The
| difference between JSON and Parquet is much bigger than the
| difference between Parquet and BtrBlocks.
| hinkley wrote:
| As with most frustrations in my career, many of the expensive
| bits come down to hoarding. We don't know what will spark joy
| so the system has to be able to do anything at any time. This
| is not free. Sometimes it's goddamned expensive.
|
| I have in this decade encountered systems that still have to
| run overnight. Meanwhile I'm spending multiple developer
| salaries maintaining a system that might be asked to answer a
| question in ten seconds, or might not be asked any questions
| for days at a time.
|
| Somebody save me.
| abeppu wrote:
| 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?
| sakras wrote:
| 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 wrote:
| 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.
| wood_spirit wrote:
| 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.
| ayhanfuat wrote:
| 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/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-4b...
| (zhihanz / @zhihanz1205)
| https://twitter.com/zhihanz1205/status/1702196118472536166
| wmertens wrote:
| > 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.
| mrits wrote:
| 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 wrote:
| [flagged]
| Loic wrote:
| Corresponding source code: https://github.com/maxi-k/btrblocks
| zX41ZdbW wrote:
| It's strange to see no comparison with ClickHouse's MergeTree
| format in the article.
| amadio wrote:
| 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/...
| (also in arXiv here: https://arxiv.org/abs/2204.09043).
| bastawhiz wrote:
| How would someone who doesn't subscribe to a journal of physics
| keep up on these sorts of developments?
| amadio wrote:
| 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 wrote:
| 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.
| birdyrooster wrote:
| Turn that data lake into a data lagoon. Are you with me?
| glogla wrote:
| Only if I can be your data dragoon.
| j-pb wrote:
| Viktor Leis's working group consistently produces interesting
| fundamental database research. AdaptiveRadixTries,
| HeightOptimisedTrees, and the Umbra database system are all done
| by them.
| jandrewrogers wrote:
| 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.
| giovannibonetti wrote:
| DuckDB uses Adaptive Radix Trees/Tries:
|
| https://duckdb.org/2022/07/27/art-storage.html
___________________________________________________________________
(page generated 2023-09-16 23:01 UTC)