You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "ArnavBalyan (via GitHub)" <gi...@apache.org> on 2026/08/15 10:33:31 UTC
[PR] GH-48231 [C++][Parquet] Add FSST encoding support for Parquet [arrow]
ArnavBalyan opened a new pull request, #50872:
URL: https://github.com/apache/arrow/pull/50872
### Rationale for this change
- Adds support for FSST Encoding for Parquet
### What changes are included in this PR?
- FSST Encoder/Decoder and third party dependencies for Parquet
### Are these changes tested?
- Unit tests, tested with live jobs
### Are there any user-facing changes?
- Yes, new encoding
* GitHub Issue: #48231
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-48231 [C++][Parquet] Add FSST encoding support for Parquet [arrow]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #50872:
URL: https://github.com/apache/arrow/pull/50872#discussion_r3789305255
##########
cpp/src/parquet/decoder.cc:
##########
@@ -1706,6 +1707,175 @@ class DeltaBitPackDecoder : public TypedDecoderImpl<DType> {
T last_value_;
};
+// ----------------------------------------------------------------------
+// FSST decoder
+
+class FsstDecoder final : public TypedDecoderImpl<ByteArrayType> {
+ public:
+ FsstDecoder(const ColumnDescriptor* descr,
+ const std::shared_ptr<Buffer>& symbol_table_body, MemoryPool* pool)
+ : TypedDecoderImpl<ByteArrayType>(descr, Encoding::FSST),
+ pool_(pool),
+ symbol_table_(internal::FsstSymbolTable::Deserialize(symbol_table_body)) {}
+
+ void SetData(int num_values, const uint8_t* data, int len) override;
+
+ int Decode(ByteArray* buffer, int max_values) override {
+ max_values = std::min(max_values, this->num_values_);
+ for (int i = 0; i < max_values; ++i) {
+ const int32_t begin = decoded_offsets_[value_index_];
+ const int32_t end = decoded_offsets_[value_index_ + 1];
+ buffer[i].ptr = begin == end ? nullptr : decoded_data_.data() + begin;
+ buffer[i].len = static_cast<uint32_t>(end - begin);
Review Comment:
FSST decoding uses `ptr == nullptr` to represent empty strings (`begin == end`). In this codebase `ByteArray::ptr == nullptr` is used as a sentinel for “no value” (and `operator std::string_view()` will build a string_view from `ptr`), so empty strings should not be represented with a null pointer.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-48231 [C++][Parquet] Add FSST encoding support for Parquet [arrow]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #50872:
URL: https://github.com/apache/arrow/pull/50872#discussion_r3789198134
##########
cpp/src/arrow/vendored/fsst/README.md:
##########
@@ -0,0 +1,9 @@
+# Vendored CWI FSST
+
+This directory contains the FSST8 implementation from
+https://github.com/cwida/fsst at commit
+`89f49c580c6388acf3b6ed2a49e1bfde6c05e616`.
+
+The sources are unchanged except for trailing-whitespace normalization.
Review Comment:
This README says the vendored FSST sources are "unchanged except for trailing-whitespace normalization", but at least the AVX512 `.inc` files contain duplicated header blocks and modified MIT license text (e.g., "E1PRESS"). Please either re-vendor to match upstream verbatim, or adjust this statement to accurately describe the non-whitespace changes being applied.
##########
cpp/src/parquet/fsst_internal.cc:
##########
@@ -0,0 +1,346 @@
+// 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.
+
+#include "parquet/fsst_internal.h"
+
+#include <algorithm>
+#include <array>
+#include <cstdint>
+#include <cstring>
+#include <limits>
+#include <numeric>
+#include <utility>
+
+#include "arrow/buffer.h"
+#include "arrow/result.h"
+#include "arrow/vendored/fsst/fsst.h"
+
+#include "parquet/exception.h"
+
+namespace parquet::internal {
+namespace {
+
+constexpr uint8_t kFsstEscape = 0xFF;
+
+} // namespace
+
+struct FsstSymbolTable::CwiState {
+ CwiState() { cwi_to_parquet_code.fill(kFsstEscape); }
+
+ ~CwiState() {
+ if (encoder != nullptr) {
+ fsst_destroy(encoder);
+ }
+ }
+
+ fsst_encoder_t* encoder = nullptr;
+ fsst_decoder_t decoder{};
+ std::array<uint8_t, 255> cwi_to_parquet_code;
+};
+
+FsstSymbolTable::~FsstSymbolTable() = default;
+
+FsstSymbolTable::FsstSymbolTable(std::vector<std::string> symbols)
+ : symbols_(std::move(symbols)), cwi_(std::make_unique<CwiState>()) {
+ InitializeCwiDecoder();
+}
+
+std::shared_ptr<FsstSymbolTable> FsstSymbolTable::Train(
+ const std::vector<std::string>& values) {
+ std::vector<size_t> lengths;
+ std::vector<const unsigned char*> inputs;
+ if (values.empty()) {
+ // CWI expects at least one input slot. A zero-length sample produces a
+ // fully usable table for encoding values on later pages.
+ static constexpr unsigned char kEmptyInput = 0;
+ lengths.push_back(0);
+ inputs.push_back(&kEmptyInput);
+ } else {
+ lengths.reserve(values.size());
+ inputs.reserve(values.size());
+ for (const std::string& value : values) {
+ lengths.push_back(value.size());
+ inputs.push_back(reinterpret_cast<const unsigned char*>(value.data()));
+ }
+ }
+
+ auto trained = std::make_unique<CwiState>();
+ trained->encoder = fsst_create(lengths.size(), lengths.data(), inputs.data(),
+ /*zeroTerminated=*/0);
+ if (trained->encoder == nullptr) {
+ throw ParquetException("CWI FSST failed to train a symbol table");
+ }
+ const fsst_decoder_t native_decoder = fsst_decoder(trained->encoder);
+
+ // The pinned CWI format stores nSymbols in byte 1 of its native export.
+ // We use it only to inspect the trained table; native bytes are never written
+ // to Parquet.
+ std::array<unsigned char, FSST_MAXHEADER> native_table{};
+ const unsigned int native_size = fsst_export(trained->encoder, native_table.data());
+ if (native_size < 17 || native_table[0] != 1) {
+ throw ParquetException("CWI FSST produced an invalid native symbol table");
+ }
+ const uint16_t symbol_count = native_table[1];
+ uint16_t histogram_count = 0;
+ for (int length = 0; length < 8; ++length) {
+ histogram_count += native_table[9 + length];
+ }
+ if (histogram_count != symbol_count) {
+ throw ParquetException("CWI FSST produced an inconsistent native symbol table");
+ }
+
+ std::vector<uint16_t> native_codes(symbol_count);
+ std::iota(native_codes.begin(), native_codes.end(), 0);
+ std::stable_sort(native_codes.begin(), native_codes.end(),
+ [&](uint16_t left, uint16_t right) {
+ return native_decoder.len[left] < native_decoder.len[right];
+ });
+
+ std::vector<std::string> symbols;
+ symbols.reserve(symbol_count);
+ for (uint16_t parquet_code = 0; parquet_code < symbol_count; ++parquet_code) {
+ const uint16_t native_code = native_codes[parquet_code];
+ const uint8_t length = native_decoder.len[native_code];
+ if (length == 0 || length > 8) {
+ throw ParquetException("CWI FSST produced an invalid symbol length");
+ }
+ trained->cwi_to_parquet_code[native_code] = static_cast<uint8_t>(parquet_code);
+ symbols.emplace_back(
+ reinterpret_cast<const char*>(&native_decoder.symbol[native_code]), length);
+ }
+
+ auto table = std::shared_ptr<FsstSymbolTable>(new FsstSymbolTable(std::move(symbols)));
+ table->cwi_->encoder = trained->encoder;
+ trained->encoder = nullptr;
+ table->cwi_->cwi_to_parquet_code = trained->cwi_to_parquet_code;
+ return table;
+}
+
+std::shared_ptr<FsstSymbolTable> FsstSymbolTable::Deserialize(
+ const std::shared_ptr<::arrow::Buffer>& body) {
+ constexpr int max_length = 8;
+ constexpr int64_t fixed_size = 9;
+ if (body == nullptr || body->size() < fixed_size || body->size() > 2049) {
+ throw ParquetException("Invalid FSST symbol table body size: ",
+ body == nullptr ? -1 : body->size());
+ }
+
+ const uint8_t* data = body->data();
+ const uint32_t symbol_count = data[0];
+
+ std::vector<uint32_t> histogram(max_length);
+ uint64_t histogram_sum = 0;
+ uint64_t expected_symbol_bytes = 0;
+ const uint8_t* histogram_data = data + 1;
+ for (int i = 0; i < max_length; ++i) {
+ histogram[i] = histogram_data[i];
+ histogram_sum += histogram[i];
+ expected_symbol_bytes += static_cast<uint64_t>(histogram[i]) * (i + 1);
+ }
+ if (histogram_sum != symbol_count) {
+ throw ParquetException("FSST length histogram does not match symbol count");
+ }
+ if (expected_symbol_bytes != static_cast<uint64_t>(body->size() - fixed_size)) {
+ throw ParquetException("FSST symbol data size does not match length histogram");
+ }
+
+ std::vector<std::string> symbols;
+ symbols.reserve(symbol_count);
+ const char* symbol_data = reinterpret_cast<const char*>(data + fixed_size);
+ int64_t offset = 0;
+ for (int length = 1; length <= max_length; ++length) {
+ for (uint32_t i = 0; i < histogram[length - 1]; ++i) {
+ symbols.emplace_back(symbol_data + offset, length);
+ offset += length;
+ }
+ }
+ return std::shared_ptr<FsstSymbolTable>(new FsstSymbolTable(std::move(symbols)));
+}
+
+std::shared_ptr<::arrow::Buffer> FsstSymbolTable::Serialize(
+ ::arrow::MemoryPool* pool) const {
+ constexpr int max_length = 8;
+ constexpr int64_t fixed_size = 9;
+ int64_t symbol_bytes = 0;
+ std::vector<uint32_t> histogram(max_length, 0);
+ for (const std::string& symbol : symbols_) {
+ ++histogram[symbol.size() - 1];
+ symbol_bytes += static_cast<int64_t>(symbol.size());
+ }
+
+ auto buffer = ::arrow::AllocateBuffer(fixed_size + symbol_bytes, pool).ValueOrDie();
Review Comment:
`AllocateBuffer(...).ValueOrDie()` will terminate the process on allocation failure instead of surfacing a Parquet/Arrow error. In libparquet code paths this should throw (via PARQUET_ASSIGN_OR_THROW / PARQUET_THROW_NOT_OK) rather than aborting.
##########
cpp/src/arrow/vendored/fsst/fsst_avx512_unroll4.inc:
##########
@@ -0,0 +1,228 @@
+// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT):
+// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT):
+// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT):
+// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT):
+//
+//
+//
+//
+// Copyright 2018-2020, CWI, TU Munich, FSU Jena
+// Copyright 2018-2020, CWI, TU Munich, FSU Jena
+// Copyright 2018-2020, CWI, TU Munich, FSU Jena
+// Copyright 2018-2020, CWI, TU Munich, FSU Jena
+//
+//
+//
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files
+// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files
+// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files
+// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files
+// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify,
+// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify,
+// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify,
+// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify,
+// merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+// merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+// merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+// merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+// furnished to do so, subject to the following conditions:
+// furnished to do so, subject to the following conditions:
+// furnished to do so, subject to the following conditions:
+//
+//
+//
+//
+// - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
+// - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
+// - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
+// - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
+//
+//
+//
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, E1PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, E2PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, E3PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, E4PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
Review Comment:
The vendored FSST AVX512 include files have a corrupted/duplicated license header (e.g., "E1PRESS" / "E2PRESS" instead of "EXPRESS"). Since this text is part of the upstream MIT header, it should be preserved verbatim when vendoring to avoid confusion and make upstream diffs auditable.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org