wgtmac commented on code in PR #48345: URL: https://github.com/apache/arrow/pull/48345#discussion_r3985658698
########## cpp/src/arrow/util/alp/alp_internal.h: ########## @@ -0,0 +1,849 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +// Adaptive Lossless floating-Point (ALP) compression implementation + +#pragma once + +#include <optional> +#include <span> +#include <vector> + +#include "arrow/result.h" +#include "arrow/status.h" +#include "arrow/util/alp/alp_constants_internal.h" +#include "arrow/util/bit_util.h" +#include "arrow/util/visibility.h" + +namespace arrow::util::alp { + +// ---------------------------------------------------------------------- +// ALP Overview +// +// IMPORTANT: For abstract interfaces or examples how to use ALP, consult +// alp_codec_internal.h. +// This file implements adaptive lossless floating-point compression for +// decimals (ALP) (https://dl.acm.org/doi/10.1145/3626717). ALP converts each +// float into a decimal where it can, using an exponent and factor chosen per +// vector: c(f) = int64(f * 10^exponent * 10^-factor). It then encodes the +// converted integers with a frame of reference and bit-packs them. +// A value the conversion cannot round-trip becomes an exception. ALP stores +// exceptions separately and patches them back into the vector after decoding. +// +// ========================================================================== +// ALP COMPRESSION/DECOMPRESSION PIPELINE +// ========================================================================== +// +// COMPRESSION FLOW: +// ----------------- +// +// Input: float/double array +// | +// v +// +------------------------------------------------------------------+ +// | 1. SAMPLING & PRESET GENERATION | +// | * Sample vectors from dataset | +// | * Try all exponent/factor combinations (e, f) | +// | * Select best k combinations for preset | +// +------------------------------------+-----------------------------+ +// | preset.combinations +// v +// +------------------------------------------------------------------+ +// | 2. PER-VECTOR COMPRESSION | +// | a) Find best (e,f) from preset for this vector | +// | b) Encode: encoded[i] = int64(value[i] * 10^e * 10^-f) | +// | c) Verify: if decode(encoded[i]) != value[i] -> exception | +// | d) Replace exceptions with placeholder value | +// +------------------------------------+-----------------------------+ +// | encoded integers + exceptions +// v +// +------------------------------------------------------------------+ +// | 3. FRAME OF REFERENCE (FOR) | +// | * Find min value in encoded integers | +// | * Subtract min from all values: delta[i] = encoded[i] - min | +// +------------------------------------+-----------------------------+ +// | delta values (smaller range) +// v +// +------------------------------------------------------------------+ +// | 4. BIT PACKING | +// | * Calculate bit_width = std::bit_width(max_delta), i.e. the | +// | number of bits needed to hold max_delta | +// | * Pack each value into bit_width bits | +// | * Result: tightly packed binary data | +// +------------------------------------+-----------------------------+ +// | packed bytes +// v +// +------------------------------------------------------------------+ +// | 5. SERIALIZATION (offset-based interleaved layout) | +// | [Header][Offsets...][Vector₀][Vector₁]... | +// | where each Vector = [AlpInfo|ForInfo|Data] | +// +------------------------------------------------------------------+ +// +// +// DECOMPRESSION FLOW: +// ------------------- +// +// Serialized bytes -> AlpEncodedVector::Load() +// | +// v +// +------------------------------------------------------------------+ +// | 1. BIT UNPACKING | +// | * Extract bit_width from metadata | +// | * Unpack each value from bit_width bits -> delta values | +// +------------------------------------+-----------------------------+ +// | delta values +// v +// +------------------------------------------------------------------+ +// | 2. REVERSE FRAME OF REFERENCE (unFOR) | +// | * Add back min: encoded[i] = delta[i] + frame_of_reference | +// +------------------------------------+-----------------------------+ +// | encoded integers +// v +// +------------------------------------------------------------------+ +// | 3. DECODE | +// | * Apply inverse formula: value[i] = encoded[i] * 10^-e * 10^f | +// +------------------------------------+-----------------------------+ +// | decoded floats (with placeholders) +// v +// +------------------------------------------------------------------+ +// | 4. PATCH EXCEPTIONS | +// | * Replace values at exception_positions[] with exceptions[] | +// +------------------------------------+-----------------------------+ +// | +// v +// Output: Original float/double array (lossless!) +// +// ========================================================================== + +// ---------------------------------------------------------------------- +// AlpExponentAndFactor + +/// \brief Helper struct to encapsulate the exponent and factor +struct AlpExponentAndFactor { + uint8_t exponent{0}; + uint8_t factor{0}; + + bool operator==(const AlpExponentAndFactor& other) const { + return exponent == other.exponent && factor == other.factor; + } + + /// \brief Comparison operator for deterministic std::map ordering + bool operator<(const AlpExponentAndFactor& other) const { + if (exponent != other.exponent) return exponent < other.exponent; + return factor < other.factor; + } Review Comment: ```suggestion std::strong_ordering operator<=>(const AlpExponentAndFactor& other) const = default; ``` We are on C++20 so it should be pretty simple to define this. ########## cpp/src/arrow/util/alp/alp_constants_internal.h: ########## @@ -0,0 +1,288 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +// Constants and type traits for ALP (Adaptive Lossless floating-Point) compression. +// Spec: https://github.com/apache/parquet-format/blob/master/Encodings.md#alp + +#pragma once + +#include <cstdint> + +#include "arrow/util/logging.h" + +namespace arrow::util::alp { + +// ---------------------------------------------------------------------- +// AlpConstants + +/// \brief Constants for Adaptive Lossless floating-Point (ALP) compression +/// See: https://github.com/apache/parquet-format/blob/master/Encodings.md#alp +class AlpConstants { + public: + /// Default number of elements compressed together as a unit. + /// The format supports arbitrary power-of-2 sizes via log_vector_size in the + /// page header (up to 2^kMaxLogVectorSize). + static constexpr int64_t kAlpVectorSize = 1024; + + /// Minimum supported log_vector_size value, i.e. a vector size of 8. + /// Mandated by the format spec (Encodings.md, "Must be in the inclusive + /// range [3, 15]"). + static constexpr uint8_t kMinLogVectorSize = 3; + + /// Maximum supported log_vector_size value. Capped at 15 because per-vector + /// element counts are stored as uint16_t (max 65535), and 2^16 = 65536 + /// would overflow. The cap allows vector sizes up to 32768. + static constexpr uint8_t kMaxLogVectorSize = 15; + + /// Sampling constants below are from the ALP paper (Afroozeh et al., + /// "ALP: Adaptive Lossless floating-Point Compression", SIGMOD 2023). + + /// Number of elements to use when determining sampling parameters. + static constexpr int64_t kSamplerVectorSize = 4096; + + /// Total number of elements in a rowgroup for sampling purposes. + /// 122880 = kSamplerVectorSize * 30 rowgroup vectors. + static constexpr int64_t kSamplerRowgroupSize = 122880; Review Comment: Does it mean that we restart sampling for every new row group? ########## cpp/src/arrow/util/alp/alp_constants_internal.h: ########## @@ -0,0 +1,288 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +// Constants and type traits for ALP (Adaptive Lossless floating-Point) compression. +// Spec: https://github.com/apache/parquet-format/blob/master/Encodings.md#alp + +#pragma once + +#include <cstdint> + +#include "arrow/util/logging.h" + +namespace arrow::util::alp { + +// ---------------------------------------------------------------------- +// AlpConstants + +/// \brief Constants for Adaptive Lossless floating-Point (ALP) compression +/// See: https://github.com/apache/parquet-format/blob/master/Encodings.md#alp +class AlpConstants { + public: + /// Default number of elements compressed together as a unit. + /// The format supports arbitrary power-of-2 sizes via log_vector_size in the + /// page header (up to 2^kMaxLogVectorSize). + static constexpr int64_t kAlpVectorSize = 1024; + + /// Minimum supported log_vector_size value, i.e. a vector size of 8. + /// Mandated by the format spec (Encodings.md, "Must be in the inclusive + /// range [3, 15]"). + static constexpr uint8_t kMinLogVectorSize = 3; + + /// Maximum supported log_vector_size value. Capped at 15 because per-vector + /// element counts are stored as uint16_t (max 65535), and 2^16 = 65536 + /// would overflow. The cap allows vector sizes up to 32768. + static constexpr uint8_t kMaxLogVectorSize = 15; + + /// Sampling constants below are from the ALP paper (Afroozeh et al., + /// "ALP: Adaptive Lossless floating-Point Compression", SIGMOD 2023). + + /// Number of elements to use when determining sampling parameters. + static constexpr int64_t kSamplerVectorSize = 4096; + + /// Total number of elements in a rowgroup for sampling purposes. + /// 122880 = kSamplerVectorSize * 30 rowgroup vectors. + static constexpr int64_t kSamplerRowgroupSize = 122880; + + /// Number of samples to collect per vector during the sampling phase. Review Comment: This comment is a little bit complicated. Is it better to move these sampler related constants directly to alp_sampler.cc where they are used? -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
