10 ms·

Float Compression 3: Filters

67 points by ibobev 4y ago

gnufx 4y ago
That's reporting better figures with general compression than I'd expect from experience. Anyway, I'd expect to reach for zfp.io for arrays of floating point data. It's certainly an old observation that the compression method you want to use is data-dependent, even for similar kinds of data. Long ago it was found that there was a dramatic difference in x-ray crystallography image data depending on whether they were taken with a lab source (low resolution) or at a synchrotron (high resolution -- sharper peaks).
- aras_p 4y ago
  I have a new post (https://aras-p.info/blog/2023/02/03/Float-Compression-5-Science/ https://aras-p.info/blog/2023/02/03/Float-Compression-5-Scie...) comparing zfp, fpzip, spdp, ndzip, streamvbyte libraries for compressing this same data set. All in lossless, single threaded mode so far (just like all the other experiments before). zfp performance is... "underwhelming" to say the least :( (fpzip is pretty good though, if only a bit slow at decompression). Maybe zfp is much better on 3D or 4D data, and/or in lossy mode. Which might be a topic for a future post.
zX41ZdbW 4y ago
Interesting to match with the observations from the practice of using ClickHouse[1][2] for time series: 1. Reordering to SOA helps a lot - this is the whole point of column-oriented databases. 2. Specialized codecs like Gorilla[3], DoubleDelta[4], and FPC[5] lose to simply using ZSTD[6] compression in most cases, both in compression ratio and in performance. 3. Specialized time-series DBMS like InfluxDB or TimescaleDB lose to general-purpose relational OLAP DBMS like ClickHouse [7][8][9]. [1] https://clickhouse.com/blog/optimize-clickhouse-codecs-compression-schema https://clickhouse.com/blog/optimize-clickhouse-codecs-compr... [2] https://github.com/ClickHouse/ClickHouse https://github.com/ClickHouse/ClickHouse [3] https://clickhouse.com/docs/en/sql-reference/statements/create/table/#gorilla https://clickhouse.com/docs/en/sql-reference/statements/crea... [4] https://clickhouse.com/docs/en/sql-reference/statements/create/table/#doubledelta https://clickhouse.com/docs/en/sql-reference/statements/crea... [5] https://clickhouse.com/docs/en/sql-reference/statements/create/table/#fpc https://clickhouse.com/docs/en/sql-reference/statements/crea... [6] https://github.com/facebook/zstd/ https://github.com/facebook/zstd/ [7] https://arxiv.org/pdf/2204.09795.pdf https://arxiv.org/pdf/2204.09795.pdf "SciTS: A Benchmark for Time-Series Databases in Scientific Experiments and Industrial Internet of Things" (2022) [8] https://gitlab.com/gitlab-org/incubation-engineering/apm/apm/-/issues/ https://gitlab.com/gitlab-org/incubation-engineering/apm/apm... https://gitlab.com/gitlab-org/incubation-engineering/apm/apm/-/issues/4 https://gitlab.com/gitlab-org/incubation-engineering/apm/apm... [9] https://www.sciencedirect.com/science/article/pii/S1877050919310439/pdf?md5=ecc390cfc9d0be432ca0c218985c94d5&pid=1-s2.0-S1877050919310439-main.pdf https://www.sciencedirect.com/science/article/pii/S187705091...
- xyzzy_plugh 4y ago
  Putting your obvious bias due to affiliation with ClickHouse aside, this is quite disingenuous. Comparing OLAP and OLTP is usually just a waste of time. They solve different problems. This blog post linked within your gitlab issue is quite impartial, relatively speaking, and disputes most of these claims: https://www.timescale.com/blog/what-is-clickhouse-how-does-it-compare-to-postgresql-and-timescaledb-and-how-does-it-perform-for-time-series-data/ https://www.timescale.com/blog/what-is-clickhouse-how-does-i... This also similarly matches my experience operating properly tuned instances. Lastly, regarding the following > Specialized codecs like Gorilla[3], DoubleDelta[4], and FPC[5] lose to simply using ZSTD[6] compression in most cases, both in compression ratio and in performance. I'd love to see some data because this is a very broad generalization that has never remotely been true in my experience. At comparable block sizes, with proper tuning, double delta can absolutely smoke zstd. In fact, while zstd can achieve quite impressive compression and performance, I almost never reach for it as it's rarely optimal when I benchmark, compared to lz4 or xz or snappy or even sometimes gzip. It depends on many factors -- what data, how much data, block size, disk or storage medium, network. Your whole post puts a rather sour taste in my mouth about ClickHouse.
  - zX41ZdbW 4y ago
    I have tested these codecs on the metrics data (like CPU usage). One experiment is detailed here: https://www.youtube.com/live/0fSp9SF8N8A?feature=share&t=1764 https://www.youtube.com/live/0fSp9SF8N8A?feature=share&t=176... Another experiment is described in the linked blog post: https://clickhouse.com/blog/optimize-clickhouse-codecs-compression-schema https://clickhouse.com/blog/optimize-clickhouse-codecs-compr... It compares codes on the weather dataset (NOAA). The comment about "DoubleDelta" codec from the ClickHouse codebase: /** NOTE DoubleDelta is surprisingly bad name. The only excuse is that it comes from an academic paper. * Most people will think that "double delta" is just applying delta transform twice. * But in fact it is something more than applying delta transform twice. */
segfaultbuserr 4y ago
Another technique I've read about is "block" floating point. In many problems like signal processing or physics simulations, the order of magnitude of the data is often close to each other within a region. Instead of giving each float its own significand and exponent, they can be grouped together and shared to save some bandwidth or space in a hardware implementation for real-time processing. Unfortunately it's often not very suitable in software, as the non-standard word size is awkward to handle.
- Avlin67 4y ago
  but you can use fp16 and fp32 and there is the hardware today
- Dylan16807 4y ago
  GPU drivers have a version of that, and using a standard word size too. Three 9-bit significands and a 5-bit shared exponent.
- buildbot 4y ago
  We use this at Microsoft for AI! https://proceedings.neurips.cc/paper/2020/file/747e32ab0fea7fbd2ad9ec03daa3f840-Paper.pdf https://proceedings.neurips.cc/paper/2020/file/747e32ab0fea7...
  - segfaultbuserr 4y ago
    Very cool, thanks for sharing!
- Someone 4y ago
  That’s, loosely, what “Reorder bytes + Delta” does, isn’t it? It groups together the first bytes of floats, delta encodes them and then compresses them, and repeats that for the second, third, and fourth bytes. The first byte of a IEEE float has 7/8 of the exponent. If these are successive measurements, chances are they have lots of series of identical values, and the delta-encoded stream will have lots of zeroes.
  - 4y ago
chrsig 4y ago
The example though uses a three dimensional vector and suggests turning that into an SoA form. My question is: In the case of component vectors like that, given that many operations wind up in operations like dot products, do the advantages still apply? I don't have any experience programming with simd instructions specifically, so the memory access patterns get a bit murky to me. The same goes for cuda, for example, which has a native float4 type. It's making row ordering so convenient, and going for SoA seems like you need to walk away from that.
- tubs 4y ago
  This is only for serialisation not for in memory use.
dhsysusbsjsi 4y ago
For comparison how TimescaleDB does it: https://www.timescale.com/blog/time-series-compression-algorithms-explained/ https://www.timescale.com/blog/time-series-compression-algor...
sdenton4 4y ago
Those who do not understand parquet are doomed to reinvent it.
- inimino 4y ago
  Those who reinvent it will understand it better than those who thought they understood it.
ArchD 4y ago
For the "Reorder floats + Delta", I wonder if he did anything special to prevent floating-point errors. Floating-point operations (e.g. minus followed by plus) do not necessarily round-trip because their results are not exactly mathematically correct, i.e. sometimes y + (x - y) != x. Otherwise, the compression is lossy.
- aras_p 4y ago
  (blog post author) I'm not doing operations on floats. The data is floats, yes, but the XOR is obviously not on floats; and Delta is not either. Both are just interpreting data as 4-byte unsigned integers or 1-byte unsigned integers depending on the filter.
xioxox 4y ago
This byte reordering trick has also been done elsewhere. For example, the HDF5 file format supports a "shuffle" filter which reorders the bytes.
- aras_p 4y ago
  (post author) All of this has been done elsewhere! I'm just trying to try various approaches that are out there, on "my own data".
  - xioxox 4y ago
    Sorry, I didn't mean to suggest you were claiming it was discovered by you. It was more on giving some background and a different name for it.

67 points by ibobev 4y ago

That's reporting better figures with general compression than I'd expect from experience. Anyway, I'd expect to reach for zfp.io for arrays of floating point data. It's certainly an old observation that the compression method you want to use is data-dependent, even for similar kinds of data. Long ago it was found that there was a dramatic difference in x-ray crystallography image data depending on whether they were taken with a lab source (low resolution) or at a synchrotron (high resolution -- sharper peaks).

aras_p 4y ago
I have a new post (https://aras-p.info/blog/2023/02/03/Float-Compression-5-Science/ https://aras-p.info/blog/2023/02/03/Float-Compression-5-Scie...) comparing zfp, fpzip, spdp, ndzip, streamvbyte libraries for compressing this same data set. All in lossless, single threaded mode so far (just like all the other experiments before). zfp performance is... "underwhelming" to say the least :( (fpzip is pretty good though, if only a bit slow at decompression). Maybe zfp is much better on 3D or 4D data, and/or in lossy mode. Which might be a topic for a future post.

zX41ZdbW 4y ago

Interesting to match with the observations from the practice of using ClickHouse[1][2] for time series: 1. Reordering to SOA helps a lot - this is the whole point of column-oriented databases. 2. Specialized codecs like Gorilla[3], DoubleDelta[4], and FPC[5] lose to simply using ZSTD[6] compression in most cases, both in compression ratio and in performance. 3. Specialized time-series DBMS like InfluxDB or TimescaleDB lose to general-purpose relational OLAP DBMS like ClickHouse [7][8][9]. [1] https://clickhouse.com/blog/optimize-clickhouse-codecs-compression-schema https://clickhouse.com/blog/optimize-clickhouse-codecs-compr... [2] https://github.com/ClickHouse/ClickHouse https://github.com/ClickHouse/ClickHouse [3] https://clickhouse.com/docs/en/sql-reference/statements/create/table/#gorilla https://clickhouse.com/docs/en/sql-reference/statements/crea... [4] https://clickhouse.com/docs/en/sql-reference/statements/create/table/#doubledelta https://clickhouse.com/docs/en/sql-reference/statements/crea... [5] https://clickhouse.com/docs/en/sql-reference/statements/create/table/#fpc https://clickhouse.com/docs/en/sql-reference/statements/crea... [6] https://github.com/facebook/zstd/ https://github.com/facebook/zstd/ [7] https://arxiv.org/pdf/2204.09795.pdf https://arxiv.org/pdf/2204.09795.pdf "SciTS: A Benchmark for Time-Series Databases in Scientific Experiments and Industrial Internet of Things" (2022) [8] https://gitlab.com/gitlab-org/incubation-engineering/apm/apm/-/issues/ https://gitlab.com/gitlab-org/incubation-engineering/apm/apm... https://gitlab.com/gitlab-org/incubation-engineering/apm/apm/-/issues/4 https://gitlab.com/gitlab-org/incubation-engineering/apm/apm... [9] https://www.sciencedirect.com/science/article/pii/S1877050919310439/pdf?md5=ecc390cfc9d0be432ca0c218985c94d5&pid=1-s2.0-S1877050919310439-main.pdf https://www.sciencedirect.com/science/article/pii/S187705091...

xyzzy_plugh 4y ago
Putting your obvious bias due to affiliation with ClickHouse aside, this is quite disingenuous. Comparing OLAP and OLTP is usually just a waste of time. They solve different problems. This blog post linked within your gitlab issue is quite impartial, relatively speaking, and disputes most of these claims: https://www.timescale.com/blog/what-is-clickhouse-how-does-it-compare-to-postgresql-and-timescaledb-and-how-does-it-perform-for-time-series-data/ https://www.timescale.com/blog/what-is-clickhouse-how-does-i... This also similarly matches my experience operating properly tuned instances. Lastly, regarding the following > Specialized codecs like Gorilla[3], DoubleDelta[4], and FPC[5] lose to simply using ZSTD[6] compression in most cases, both in compression ratio and in performance. I'd love to see some data because this is a very broad generalization that has never remotely been true in my experience. At comparable block sizes, with proper tuning, double delta can absolutely smoke zstd. In fact, while zstd can achieve quite impressive compression and performance, I almost never reach for it as it's rarely optimal when I benchmark, compared to lz4 or xz or snappy or even sometimes gzip. It depends on many factors -- what data, how much data, block size, disk or storage medium, network. Your whole post puts a rather sour taste in my mouth about ClickHouse.
- zX41ZdbW 4y ago
  I have tested these codecs on the metrics data (like CPU usage). One experiment is detailed here: https://www.youtube.com/live/0fSp9SF8N8A?feature=share&t=1764 https://www.youtube.com/live/0fSp9SF8N8A?feature=share&t=176... Another experiment is described in the linked blog post: https://clickhouse.com/blog/optimize-clickhouse-codecs-compression-schema https://clickhouse.com/blog/optimize-clickhouse-codecs-compr... It compares codes on the weather dataset (NOAA). The comment about "DoubleDelta" codec from the ClickHouse codebase: /** NOTE DoubleDelta is surprisingly bad name. The only excuse is that it comes from an academic paper. * Most people will think that "double delta" is just applying delta transform twice. * But in fact it is something more than applying delta transform twice. */

segfaultbuserr 4y ago

Another technique I've read about is "block" floating point. In many problems like signal processing or physics simulations, the order of magnitude of the data is often close to each other within a region. Instead of giving each float its own significand and exponent, they can be grouped together and shared to save some bandwidth or space in a hardware implementation for real-time processing. Unfortunately it's often not very suitable in software, as the non-standard word size is awkward to handle.

Avlin67 4y ago
but you can use fp16 and fp32 and there is the hardware today
Dylan16807 4y ago
GPU drivers have a version of that, and using a standard word size too. Three 9-bit significands and a 5-bit shared exponent.
buildbot 4y ago
We use this at Microsoft for AI! https://proceedings.neurips.cc/paper/2020/file/747e32ab0fea7fbd2ad9ec03daa3f840-Paper.pdf https://proceedings.neurips.cc/paper/2020/file/747e32ab0fea7...
- segfaultbuserr 4y ago
  Very cool, thanks for sharing!
Someone 4y ago
That’s, loosely, what “Reorder bytes + Delta” does, isn’t it? It groups together the first bytes of floats, delta encodes them and then compresses them, and repeats that for the second, third, and fourth bytes. The first byte of a IEEE float has 7/8 of the exponent. If these are successive measurements, chances are they have lots of series of identical values, and the delta-encoded stream will have lots of zeroes.
- 4y ago

chrsig 4y ago

The example though uses a three dimensional vector and suggests turning that into an SoA form. My question is: In the case of component vectors like that, given that many operations wind up in operations like dot products, do the advantages still apply? I don't have any experience programming with simd instructions specifically, so the memory access patterns get a bit murky to me. The same goes for cuda, for example, which has a native float4 type. It's making row ordering so convenient, and going for SoA seems like you need to walk away from that.

tubs 4y ago
This is only for serialisation not for in memory use.

dhsysusbsjsi 4y ago

For comparison how TimescaleDB does it: https://www.timescale.com/blog/time-series-compression-algorithms-explained/ https://www.timescale.com/blog/time-series-compression-algor...

sdenton4 4y ago

Those who do not understand parquet are doomed to reinvent it.

inimino 4y ago
Those who reinvent it will understand it better than those who thought they understood it.

ArchD 4y ago

For the "Reorder floats + Delta", I wonder if he did anything special to prevent floating-point errors. Floating-point operations (e.g. minus followed by plus) do not necessarily round-trip because their results are not exactly mathematically correct, i.e. sometimes y + (x - y) != x. Otherwise, the compression is lossy.

aras_p 4y ago
(blog post author) I'm not doing operations on floats. The data is floats, yes, but the XOR is obviously not on floats; and Delta is not either. Both are just interpreting data as 4-byte unsigned integers or 1-byte unsigned integers depending on the filter.

xioxox 4y ago

This byte reordering trick has also been done elsewhere. For example, the HDF5 file format supports a "shuffle" filter which reorders the bytes.

aras_p 4y ago
(post author) All of this has been done elsewhere! I'm just trying to try various approaches that are out there, on "my own data".
- xioxox 4y ago
  Sorry, I didn't mean to suggest you were claiming it was discovered by you. It was more on giving some background and a different name for it.