Antoine Pitrou created PARQUET-2414:
---------------------------------------
Summary: [Format] Expand BYTE_STREAM_SPLIT to support
FIXED_LEN_BYTE_ARRAY
Key: PARQUET-2414
URL: https://issues.apache.org/jira/browse/PARQUET-2414
Project: Parquet
Issue Type: Improvement
Components: parquet-format
Reporter: Antoine Pitrou
In PARQUET-1622 we added the BYTE_STREAM_SPLIT which, while simple to
implement, allows to significantly improve compression efficiency on FLOAT and
DOUBLE columns.
In PARQUET-758 we added the FLOAT16 logical type which annotates a 2-byte-wide
FIXED_LEN_BYTE_ARRAY column to denote that it contains 16-bit IEEE binary
floating-point (colloquially called "half float").
This issue proposed to widen the types supported by the BYTE_STREAM_SPLIT. By
allowing the BYTE_STREAM_SPLIT on any FIXED_LEN_BYTE_ARRAY column, we can
automatically improve compression efficiency on various column types
including:
* half-float data
* fixed-width decimal data
I've run compression measurements on various pieces of sample data which I
detail below.
h2. Float16 data
I've downloaded the sample datasets from
https://userweb.cs.txstate.edu/~burtscher/research/datasets/FPsingle/ ,
uncompressed them and converted them to half-float using NumPy. Two files
had to be discarded because of overflow when converting to half-float.
I've then run three different compression algorithms (lz4, zstd, snappy),
optionally preceded by a byte-stream-split encoded with 2 streams
(corresponding to the byte width of the FLBA columns. Here are the results:
{code}
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| name | uncompressed | lz4 | bss_lz4 | snappy |
bss_snappy | zstd | bss_zstd | bss_ratio_lz4 | bss_ratio_snappy |
bss_ratio_zstd |
+================+================+========+===========+==========+==============+========+============+=================+====================+==================+
| msg_sp.sp | 72526464.00 | 1.42 | 1.94 | 1.38 |
1.78 | 2.28 | 2.71 | 1.37 | 1.30 |
1.18 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| msg_sppm.sp | 69748966.00 | 18.90 | 29.05 | 11.38 |
14.39 | 45.81 | 71.49 | 1.54 | 1.26 |
1.56 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| msg_sweep3d.sp | 31432806.00 | 2.06 | 3.20 | 1.03 |
1.94 | 11.77 | 17.00 | 1.55 | 1.89 |
1.44 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| num_brain.sp | 35460000.00 | 1.02 | 1.51 | 1.01 |
1.49 | 1.26 | 1.81 | 1.49 | 1.48 |
1.44 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| num_comet.sp | 26836992.00 | 1.45 | 1.74 | 1.42 |
1.69 | 1.64 | 2.07 | 1.20 | 1.19 |
1.26 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| num_control.sp | 39876186.00 | 1.35 | 1.49 | 1.37 |
1.53 | 1.70 | 1.93 | 1.11 | 1.12 |
1.14 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| num_plasma.sp | 8772400.00 | 123.88 | 152.12 | 1.00 |
1.80 | 259.58 | 405.96 | 1.23 | 1.80 |
1.56 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| obs_error.sp | 15540204.00 | 1.05 | 1.51 | 1.02 |
1.46 | 2.06 | 3.55 | 1.44 | 1.43 |
1.72 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| obs_info.sp | 4732632.00 | 1.08 | 1.74 | 1.00 |
1.61 | 2.60 | 3.63 | 1.62 | 1.61 |
1.40 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| obs_spitzer.sp | 49545216.00 | 1.00 | 1.01 | 1.00 |
1.01 | 1.22 | 1.35 | 1.01 | 1.01 |
1.11 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| obs_temp.sp | 9983568.00 | 1.00 | 1.00 | 1.00 |
1.00 | 1.08 | 1.17 | 1.00 | 1.00 |
1.08 |
+----------------+----------------+--------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
{code}
Explanation:
* the columns "lz4", "snappy", "zstd" shows the compression ratio achieved with
the respective compressors (i.e. uncompressed size divided by compressed size)
* the columns "bss_lz4", "bss_snappy", "bss_zstd" are similar, but with a
byte-stream-split encoding applied first
* the columns "bss_ratio_lz4", "bss_ratio_snappy", "bss_ratio_zstd" show
the additional compression ratio achieved by prepending the byte-stream-split
encoding step (i.e. compressed size divided by encoded+compressed size).
h3. (reference) Float32 data
For reference, here are the measurements for the same data without first
converting
to half-float.
{code}
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| name | uncompressed | lz4 | bss_lz4 | snappy | bss_snappy
| zstd | bss_zstd | bss_ratio_lz4 | bss_ratio_snappy | bss_ratio_zstd
|
+================+================+=======+===========+==========+==============+========+============+=================+====================+==================+
| msg_sp.sp | 145052928.00 | 1.00 | 1.45 | 1.00 | 1.39
| 1.12 | 1.66 | 1.46 | 1.39 | 1.48
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| msg_sppm.sp | 139497932.00 | 8.56 | 8.66 | 5.64 | 5.90
| 12.51 | 11.16 | 1.01 | 1.05 | 0.89
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| msg_sweep3d.sp | 62865612.00 | 1.01 | 2.80 | 1.02 | 1.68
| 5.50 | 9.41 | 2.76 | 1.66 | 1.71
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| num_brain.sp | 70920000.00 | 1.00 | 1.31 | 1.00 | 1.30
| 1.13 | 1.43 | 1.31 | 1.30 | 1.27
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| num_comet.sp | 53673984.00 | 1.08 | 1.27 | 1.08 | 1.27
| 1.15 | 1.36 | 1.17 | 1.18 | 1.18
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| num_control.sp | 79752372.00 | 1.01 | 1.12 | 1.01 | 1.13
| 1.08 | 1.21 | 1.11 | 1.12 | 1.12
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| num_plasma.sp | 17544800.00 | 1.00 | 140.74 | 1.01 | 1.30
| 279.49 | 310.68 | 141.29 | 1.30 | 1.11
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| obs_error.sp | 31080408.00 | 1.12 | 1.37 | 1.16 | 1.29
| 1.73 | 3.10 | 1.22 | 1.11 | 1.80
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| obs_info.sp | 9465264.00 | 1.07 | 1.42 | 1.00 | 1.29
| 2.25 | 3.04 | 1.33 | 1.29 | 1.35
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| obs_spitzer.sp | 99090432.00 | 1.02 | 1.11 | 1.01 | 1.12
| 1.20 | 1.31 | 1.09 | 1.10 | 1.09
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| obs_temp.sp | 19967136.00 | 1.00 | 1.12 | 1.00 | 1.13
| 1.08 | 1.19 | 1.12 | 1.13 | 1.10
|
+----------------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
{code}
h3. Comments
The additional efficiency of the byte-stream-split encoding step is very
significant
on most files (except {code}obs_temp.sp{code} which generally doesn't compress
at all),
with additional gains usually around 30%.
The byte-stream-split encoding test is, perhaps surprisingly, on average as
beneficial
on Float16 data as it is on Float32 data.
h2. Decimal data from OpenStreetMap changesets
I've downloaded one of the recent OSM changesets file {{changesets-231030.orc}},
and loaded the four decimal columns from the first stripe of that file.
Those columns look like:
{code}
pyarrow.RecordBatch
min_lat: decimal128(9, 7)
max_lat: decimal128(9, 7)
min_lon: decimal128(10, 7)
max_lon: decimal128(10, 7)
----
min_lat:
[51.5288506,51.0025063,51.5326805,51.5248871,51.5266800,51.5261841,51.5264130,51.5238914,59.9463692,59.9513092,...,50.8238277,52.1707376,44.2701598,53.1589748,43.5988333,37.7867167,45.5448822,null,50.7998334,50.5653478]
max_lat:
[51.5288620,51.0047760,51.5333176,51.5289383,51.5291901,51.5300598,51.5264130,51.5238914,59.9525642,59.9561501,...,50.8480772,52.1714300,44.3790161,53.1616817,43.6001496,37.7867913,45.5532716,null,51.0188961,50.5691352]
min_lon:
[-0.1465242,-1.0052705,-0.1566335,-0.1485492,-0.1418076,-0.1550623,-0.1539768,-0.1432930,10.7782278,10.7719727,...,10.6863813,13.2218676,19.8840738,8.9128186,1.4030591,-122.4212761,18.6789571,null,-4.2085209,8.6851671]
max_lon:
[-0.1464925,-0.9943439,-0.1541054,-0.1413791,-0.1411505,-0.1453212,-0.1539768,-0.1432930,10.7898550,10.7994537,...,10.7393494,13.2298706,20.2262343,8.9183611,1.4159345,-122.4212503,18.6961594,null,-4.0496079,8.6879264]
{code}
Here are the compression measurements using the same methodology as above.
The number of byte-stream-split streams is the respective byte width of
each FLBA column (i.e., 4 for latitudes and 5 for longitudes).
{code}
+---------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| name | uncompressed | lz4 | bss_lz4 | snappy | bss_snappy |
zstd | bss_zstd | bss_ratio_lz4 | bss_ratio_snappy | bss_ratio_zstd |
+=========+================+=======+===========+==========+==============+========+============+=================+====================+==================+
| min_lat | 4996652.00 | 1.00 | 1.01 | 1.00 | 1.03 |
1.05 | 1.12 | 1.01 | 1.03 | 1.07 |
+---------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| max_lat | 4996652.00 | 1.00 | 1.01 | 1.00 | 1.03 |
1.05 | 1.13 | 1.01 | 1.03 | 1.07 |
+---------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| min_lon | 6245825.00 | 1.00 | 1.14 | 1.00 | 1.16 |
1.15 | 1.31 | 1.14 | 1.16 | 1.14 |
+---------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| max_lon | 6245825.00 | 1.00 | 1.14 | 1.00 | 1.16 |
1.15 | 1.31 | 1.14 | 1.16 | 1.14 |
+---------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
{code}
h3. Comments
On this dataset, compression efficiency is generally quite poor and
byte-stream-split
encoding brings almost no additional efficiency to the table. It can be assumed
that
OSM changeset entries have geographical coordinates all over the place
(literally!)
and therefore do not offer many opportunities for compression.
h2. Decimal data from an OpenStreetMap region
I've chosen a small region of the world (Belgium) whose geographical coordinates
presumably allow for better compression by being much more clustered. The file
{{belgium-latest.osm.pbf}} was converted to ORC for easier handling, resulting
in a 745 MB ORC file.
I've then loaded the decimal columns from the first stripe in that file:
{code}
pyarrow.RecordBatch
lat: decimal128(9, 7)
lon: decimal128(10, 7)
----
lat:
[50.4443865,50.4469017,50.4487890,50.4499558,50.4523446,50.4536530,50.4571053,50.4601436,50.4631197,50.4678563,...,51.1055899,51.1106197,51.1049620,51.1047010,51.1104755,51.0997955,51.1058101,51.1010664,51.1014336,51.1055106]
lon:
[3.6857362,3.6965046,3.7074481,3.7173626,3.8126033,3.9033178,3.9193678,3.9253319,3.9292409,3.9332670,...,4.6663214,4.6699997,4.6720536,4.6655159,4.6666372,4.6680394,4.6747172,4.6684242,4.6713693,4.6644899]
{code}
Here are the compression measurements for these columns:
{code}
+--------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| name | uncompressed | lz4 | bss_lz4 | snappy | bss_snappy |
zstd | bss_zstd | bss_ratio_lz4 | bss_ratio_snappy | bss_ratio_zstd |
+========+================+=======+===========+==========+==============+========+============+=================+====================+==================+
| lat | 12103680.00 | 1.00 | 1.63 | 1.00 | 1.63 |
1.18 | 1.73 | 1.63 | 1.63 | 1.47 |
+--------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
| lon | 15129600.00 | 1.00 | 1.93 | 1.00 | 1.90 |
1.27 | 2.06 | 1.93 | 1.90 | 1.62 |
+--------+----------------+-------+-----------+----------+--------------+--------+------------+-----------------+--------------------+------------------+
{code}
h3. Comments
This dataset shows that a byte-stream-split encoding test before compression
achieves a very significant additional efficiency compared to compression alone.
h2. Discussion
h3. Benefits
These examples show that extending the BYTE_STREAM_SPLIT encoding to
FIXED_LEN_BYTE_ARRAY columns (even regardless of their logical types) can
yield very significant compression efficiency improvements on two specific
types of FIXED_LEN_BYTE_ARRAY data: FLOAT16 data and DECIMAL data.
h3. Implementation complexity
BYTE_STREAM_SPLIT, even byte width-agnostic, is almost trivial to implement.
A simple implementation can yield good performance with a minimum of work.
For example, the non-SIMD-optimized BYTE_STREAM_SPLIT encoding and decoding
routines in Parquet C++ amount to a mere total of ~200 lines of code, despite
explicitly-unrolled loops:
https://github.com/apache/arrow/blob/4e58f7ca0016c2b2d8a859a0c5965df3b15523e0/cpp/src/arrow/util/byte_stream_split_internal.h#L593-L702
These routines achieve several GB/s on FLOAT and DOUBLE data, both for encoding
and decoding.
h2. TODO
Try to make the tables above nicer :-)
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
