You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@parquet.apache.org by "Antoine Pitrou (Jira)" <ji...@apache.org> on 2023/12/14 18:56:00 UTC
[jira] [Commented] (PARQUET-2414) [Format] Expand BYTE_STREAM_SPLIT to support FIXED_LEN_BYTE_ARRAY
[ https://issues.apache.org/jira/browse/PARQUET-2414?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17796880#comment-17796880 ]
Antoine Pitrou commented on PARQUET-2414:
-----------------------------------------
cc [~anjakefala] [~gszadovszky] [~wgtmac]
> [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
> Priority: Minor
> Attachments: bss_fp16.png, bss_osm_belgium.png, bss_osm_changesets.png
>
>
> 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" show 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 original single-precision floating-point data.
> {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 {{obs_temp.sp}} 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. Addendum
> See the attached PNG files for nicer versions of the tables above.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org