This is an automated email from the ASF dual-hosted git repository.
airborne12 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 0571eb6a580 [improvement](be) Let each SNII index spend a size budget
on faster .prx windows (#69769)
0571eb6a580 is described below
commit 0571eb6a58047cafb19e2f2b31d7856ff55db2fa
Author: Jack <[email protected]>
AuthorDate: Thu Oct 29 09:09:25 2026 +0800
[improvement](be) Let each SNII index spend a size budget on faster .prx
windows (#69769)
### What problem does this PR solve?
Issue Number: None
Related PR: #69649, #69770
Problem Summary: #69649 stores a .prx window as PFOR instead of zstd
when zstd saves less than `snii_prx_zstd_min_saving_percent` (30) of the
PFOR frame, because every read of a zstd window pays a decompression.
What that costs and buys depends on how much zstd saves on the data.
Replaying the 1.6M windows of 10M AgentLogs rows, 30 spends 8% more
bytes on the windows zstd compresses and cuts their decode time by 42%;
on the windows of TextBench service logs it spends 5% and cuts 6%; on
data whose windows zstd shrinks by just under 30% it stores every window
as PFOR. No single percentage fits all data.
Each index of a segment now spends a size budget instead:
`PrxZstdBudget`, owned by its `LogicalIndexWriter` and reached through
`PrxWindowLimits`, so the resident and the spilled encoder, and the
ordinary and the compaction build, all use it. A window whose smallest
frame is zstd is stored in its faster frame (PFOR, or raw when smaller)
when
- its saving is below the share whose trades, over the windows the index
has seen, fit 8% of their smallest frames, which puts the budget on the
windows zstd shrinks least, and
- the bytes the index has actually traded, this window included, still
fit 8% of the smallest frames seen. This makes 8% a bound for any order
of windows: fed the TextBench windows from the largest saving to the
smallest, the share alone spends 36%.
Until it has seen 64 windows the share is 30, the previous default. The
windows counted are those that get a zstd frame (a plain payload of at
least 512 bytes), the only ones whose codec a share decides; singleton
and short windows are written as before and counted neither in the
allowance nor in the warmup. The choice uses the frames the writer
builds anyway: nothing is compressed twice or scanned ahead, and the
same input gives the same bytes. `snii_prx_zstd_min_saving_percent` now
defaults to -1 (the budget); 0-100 keeps a fixed share, 0 the smallest
frame.
The budget is 8% rather than less: with it the AgentLogs phrase queries
below read nearly the same frames as with 30, while in the replay a 5%
budget cuts the decode time by 31% instead of 39%.
Same binary, one stream load per table, size against the smallest frames
(0):
| data | index, 30 | index, budget | table, 30 | table, budget |
|---|---|---|---|---|
| AgentLogs 99M rows | +4.13% | +3.65% | +1.92% | +1.69% |
| AgentLogs 10M rows | +4.59% | +3.37% | +2.13% | +1.57% |
| TextBench 12M rows | +0.89% | +0.79% | +0.51% | +0.45% |
- The phrase queries read the same frames with 30 and with the budget:
at 99M rows all PFOR for DS1, DS6, DS7, A6 and A9 (for example 107,307
frames for DS7), and about 11,170 zstd frames of about 259,000 for A10
with both; on TextBench most windows stay zstd either way (582 against
583 zstd frames of 599 for 'connection reset').
- Hot queries in one process, budget data against 30 data with the same
read path (paired cycles: 6 for the 25 AgentLogs queries at 10M rows, 10
for the 15 TextBench queries): 0.96-1.06 and 0.97-1.05; every query
returns the same result.
- Against the data written before #69649 (smallest frames), the 11
AgentLogs phrase queries at 99M rows take 0.83x in geometric mean with
the budget data (DS7 0.63x, A6 0.67x, A9 0.70x, DS4 0.74x, A10 0.77x),
as with 30 (0.83x). This run also had the read-path change of #69770,
which does not touch the PFOR windows these queries read.
- Data bytes are identical, and the index written with 0 and with 30 has
exactly the size the previous binary writes.
- Write cost: the choice adds about 48 ns per window, 79 ms over the
1.6M AgentLogs windows.
### Release note
SNII now chooses per index how many position windows to store in the
faster but larger PFOR form, spending at most 8% of the size of the
windows zstd compresses; `snii_prx_zstd_min_saving_percent` defaults to
-1 for this, and 0-100 still sets a fixed percentage.
---
be/src/common/config.cpp | 10 +-
be/src/common/config.h | 3 +-
be/src/storage/index/index_file_writer.cpp | 2 +
.../storage/index/inverted/snii/format/prx_pod.cpp | 87 ++++++++++++++++-
.../storage/index/inverted/snii/format/prx_pod.h | 51 ++++++++++
.../inverted/snii/writer/logical_index_writer.cpp | 4 +-
.../inverted/snii/writer/logical_index_writer.h | 5 +
.../inverted/snii/writer/posting_prx_encoder.cpp | 13 ++-
.../snii/compaction/snii_streamed_session_test.cpp | 107 +++++++++++++++++++++
.../index/inverted/snii/format/prx_pod_test.cpp | 107 +++++++++++++++++++++
.../snii/writer/snii_writer_golden_bytes_test.cpp | 32 +++++-
11 files changed, 402 insertions(+), 19 deletions(-)
diff --git a/be/src/common/config.cpp b/be/src/common/config.cpp
index fad0547b0ee..15871fab17d 100644
--- a/be/src/common/config.cpp
+++ b/be/src/common/config.cpp
@@ -1428,10 +1428,12 @@ DEFINE_mInt32(snii_dict_block_zstd_level, "3");
DEFINE_mInt32(snii_prx_zstd_level, "3");
// A .prx window is stored zstd-compressed only if that frame is smaller than
the PFOR one by at
// least this percentage; 0 picks the smaller frame. Every read of a zstd
window pays a
-// decompression that PFOR does not, and on text positions zstd beats PFOR by
20-30% only on the
-// large windows of frequent terms, which are the ones phrase queries read
most: 30 costs about 2%
-// of the index size. Readers handle every codec, so changing this never
affects existing segments.
-DEFINE_mInt32(snii_prx_zstd_min_saving_percent, "30");
+// decompression that PFOR does not, but how much zstd saves depends on the
data, so no one
+// percentage fits all data. The default (negative) lets each index choose: it
stores in their
+// faster frame the windows zstd shrinks least, spending at most 8% of the
smallest size of the
+// windows that get a zstd frame (see format::PrxZstdBudget). Readers handle
every codec, so
+// changing this never affects existing segments.
+DEFINE_mInt32(snii_prx_zstd_min_saving_percent, "-1");
// Zstd level for direct-load .prx regions. Compaction rewrites them using
snii_prx_zstd_level.
DEFINE_mInt32(snii_prx_zstd_level_direct_load, "3");
// Handing a few small page-cache reads to the shared prefetch pool costs more
than the reads: a
diff --git a/be/src/common/config.h b/be/src/common/config.h
index 997d7d39fb6..bc11a54e172 100644
--- a/be/src/common/config.h
+++ b/be/src/common/config.h
@@ -1467,7 +1467,8 @@ DECLARE_mInt32(inverted_index_max_buffered_docs);
DECLARE_mInt32(snii_dict_block_zstd_level);
DECLARE_mInt32(snii_prx_zstd_level);
// A .prx window is stored zstd-compressed only if that frame is smaller than
the PFOR one by at
-// least this percentage; 0 picks the smaller frame. Affects segments written
from now on.
+// least this percentage; 0 picks the smaller frame. Negative (the default)
lets each index choose
+// within a size budget. Affects segments written from now on.
DECLARE_mInt32(snii_prx_zstd_min_saving_percent);
// Patch C: prx zstd level for DIRECT-LOAD segments only (default 3, cheaper
// import); compaction rewrites at snii_prx_zstd_level so settled segments are
diff --git a/be/src/storage/index/index_file_writer.cpp
b/be/src/storage/index/index_file_writer.cpp
index dd3f86fe1b2..4b6abcbcb03 100644
--- a/be/src/storage/index/index_file_writer.cpp
+++ b/be/src/storage/index/index_file_writer.cpp
@@ -146,6 +146,8 @@ void snii_resolve_index_write_params(bool is_direct_load,
bool has_norms,
input->prx_zstd_level = std::clamp(
is_direct_load ? config::snii_prx_zstd_level_direct_load :
config::snii_prx_zstd_level,
3, 19);
+ // Negative: the index chooses the percentage within its own size budget.
+ input->prx_zstd_budget = config::snii_prx_zstd_min_saving_percent < 0;
input->prx_window_limits.zstd_min_saving_percent =
static_cast<uint32_t>(std::clamp(config::snii_prx_zstd_min_saving_percent, 0,
100));
// G16-d: dict block size experiment knob; <= 0 keeps the format default.
diff --git a/be/src/storage/index/inverted/snii/format/prx_pod.cpp
b/be/src/storage/index/inverted/snii/format/prx_pod.cpp
index b7c22771b9b..8500e23e543 100644
--- a/be/src/storage/index/inverted/snii/format/prx_pod.cpp
+++ b/be/src/storage/index/inverted/snii/format/prx_pod.cpp
@@ -488,6 +488,88 @@ AutoPrxCodecChoice select_auto_prx_codec(size_t
pfor_payload_size, size_t plain_
return choice;
}
+void PrxZstdBudget::add(uint64_t smallest_frame_bytes) {
+ _smallest_bytes += smallest_frame_bytes;
+ count_window();
+}
+
+bool PrxZstdBudget::trade(uint64_t zstd_frame_bytes, uint64_t
faster_extra_bytes,
+ uint32_t saving_percent) {
+ _smallest_bytes += zstd_frame_bytes;
+ const bool faster =
+ saving_percent < _min_saving_percent &&
+ (_spent_bytes + faster_extra_bytes) * 100 <= _smallest_bytes *
kPrxZstdBudgetPercent;
+ if (faster) {
+ _spent_bytes += faster_extra_bytes;
+ }
+ _extra_by_saving[std::min<uint32_t>(saving_percent, 100)] +=
faster_extra_bytes;
+ count_window();
+ return faster;
+}
+
+void PrxZstdBudget::count_window() {
+ if (++_windows < kPrxZstdBudgetWarmupWindows) {
+ return;
+ }
+ // The largest share whose trades, over the windows seen so far, fit the
budget. A window whose
+ // saving is p percent is traded under every share above p, so the trades
of share s are the
+ // buckets below s.
+ const uint64_t allowed = _smallest_bytes * kPrxZstdBudgetPercent / 100;
+ uint64_t extra = 0;
+ uint32_t share = 0;
+ while (share < 100 && extra + _extra_by_saving[share] <= allowed) {
+ extra += _extra_by_saving[share];
+ ++share;
+ }
+ _min_saving_percent = share;
+}
+
+namespace {
+
+uint64_t chosen_frame_size(PrxCodec codec, size_t pfor_payload_size, size_t
plain_payload_size,
+ size_t compressed_payload_size) {
+ switch (codec) {
+ case PrxCodec::kPfor:
+ return pfor_frame_size(pfor_payload_size);
+ case PrxCodec::kZstd:
+ return zstd_frame_size(plain_payload_size, compressed_payload_size);
+ default:
+ return raw_frame_size(plain_payload_size);
+ }
+}
+
+} // namespace
+
+AutoPrxCodecChoice choose_auto_prx_codec(const PrxWindowLimits& limits, size_t
pfor_payload_size,
+ size_t plain_payload_size, size_t
compressed_payload_size,
+ bool has_compressed) {
+ const auto select = [&](uint32_t zstd_min_saving_percent) {
+ return select_auto_prx_codec(pfor_payload_size, plain_payload_size,
compressed_payload_size,
+ has_compressed, limits.max_uncomp_bytes,
+ zstd_min_saving_percent);
+ };
+ PrxZstdBudget* const budget = limits.zstd_budget;
+ if (budget == nullptr) {
+ return select(limits.zstd_min_saving_percent);
+ }
+ const auto bytes = [&](AutoPrxCodecChoice choice) {
+ return chosen_frame_size(choice.codec, pfor_payload_size,
plain_payload_size,
+ compressed_payload_size);
+ };
+ const AutoPrxCodecChoice smallest = select(0);
+ if (smallest.codec != PrxCodec::kZstd || pfor_payload_size >
limits.max_uncomp_bytes) {
+ budget->add(bytes(smallest));
+ return smallest;
+ }
+ // Never zstd: PFOR, or raw when that is smaller still.
+ const AutoPrxCodecChoice faster = select(100);
+ const uint64_t zstd_bytes = bytes(smallest);
+ const uint64_t pfor_bytes = pfor_frame_size(pfor_payload_size);
+ const auto saving_percent = static_cast<uint32_t>((pfor_bytes -
zstd_bytes) * 100 / pfor_bytes);
+ return budget->trade(zstd_bytes, bytes(faster) - zstd_bytes,
saving_percent) ? faster
+
: smallest;
+}
+
namespace {
void write_zstd_compressed(Slice plain, Slice compressed, ByteSink* sink) {
@@ -555,9 +637,8 @@ Status build_prx_window_auto_from_flat(std::span<const
uint32_t> positions_flat,
testing::note_prx_raw_build();
RETURN_IF_ERROR(zstd_compress(plain.view(), zstd_level,
&compressed));
}
- const AutoPrxCodecChoice choice = select_auto_prx_codec(
- payload.size(), plain.size(), compressed.size(),
has_compressed,
- limits.max_uncomp_bytes, limits.zstd_min_saving_percent);
+ const AutoPrxCodecChoice choice = choose_auto_prx_codec(
+ limits, payload.size(), plain.size(), compressed.size(),
has_compressed);
DCHECK(choice.readable);
if (choice.codec == PrxCodec::kZstd) {
write_zstd_compressed(plain.view(), Slice(compressed), sink);
diff --git a/be/src/storage/index/inverted/snii/format/prx_pod.h
b/be/src/storage/index/inverted/snii/format/prx_pod.h
index 22ca2f8287f..2b95ab4aad9 100644
--- a/be/src/storage/index/inverted/snii/format/prx_pod.h
+++ b/be/src/storage/index/inverted/snii/format/prx_pod.h
@@ -17,6 +17,7 @@
#pragma once
+#include <array>
#include <cstddef>
#include <cstdint>
#include <span>
@@ -73,12 +74,56 @@ AutoPrxCodecChoice select_auto_prx_codec(size_t
pfor_payload_size, size_t plain_
uint32_t max_uncomp_bytes,
uint32_t zstd_min_saving_percent = 0);
+// Decides which .prx windows of one index of one segment are stored in a
larger frame that reads
+// faster. Every read of a zstd window pays a decompression that PFOR does
not, so storing a window
+// whose smallest frame is zstd in its PFOR (or smaller raw) frame trades
bytes for reads. How much
+// zstd saves depends on the data: a fixed share (zstd_min_saving_percent) of
30 spends about 8% more
+// bytes on the windows of agent logs, about 5% on those of service logs, and
much more on data whose
+// windows zstd shrinks by just under the share. The budget instead spends at
most
+// kPrxZstdBudgetPercent of the smallest frames of the windows that get a zstd
frame (a plain
+// payload of at least kPrxAutoZstdMinBytes), the only ones whose codec a
share decides, on the
+// windows zstd shrinks least: a window is traded when its saving is below the
share whose trades,
+// over the windows seen so far, fit the budget, and when what has actually
been spent still fits
+// it, so no order of windows can make it spend more. Until
kPrxZstdBudgetWarmupWindows windows are
+// seen the share is kPrxZstdBudgetPriorPercent. Windows written without a
zstd frame (a singleton,
+// or too short to compress) are not counted: no share changes them, and
counting their bytes would
+// let an index of many short posting lists grow its large windows by more
than the budget.
+// Writer-only and deterministic for a given input.
+inline constexpr uint32_t kPrxZstdBudgetPercent = 8;
+inline constexpr uint32_t kPrxZstdBudgetPriorPercent = 30;
+inline constexpr uint32_t kPrxZstdBudgetWarmupWindows = 64;
+
+class PrxZstdBudget {
+public:
+ // Records a window that has nothing to trade: zstd is not its smallest
frame, or PFOR is not
+ // readable.
+ void add(uint64_t smallest_frame_bytes);
+ // Records a window whose smallest frame is zstd. `faster_extra_bytes` is
what its faster frame
+ // costs on top of the zstd one, `saving_percent` how much smaller the
zstd frame is than the PFOR
+ // one, in whole percent of the PFOR frame. Returns whether to store the
faster frame.
+ bool trade(uint64_t zstd_frame_bytes, uint64_t faster_extra_bytes,
uint32_t saving_percent);
+ // A window saving less than this share is traded if the budget allows.
+ uint32_t min_saving_percent() const { return _min_saving_percent; }
+
+private:
+ void count_window();
+
+ // The extra bytes of trading each window seen, by its saving_percent.
+ std::array<uint64_t, 101> _extra_by_saving {};
+ uint64_t _smallest_bytes = 0;
+ uint64_t _spent_bytes = 0;
+ uint32_t _windows = 0;
+ uint32_t _min_saving_percent = kPrxZstdBudgetPriorPercent;
+};
+
struct PrxWindowLimits {
uint32_t max_docs;
uint32_t max_positions;
uint32_t max_uncomp_bytes;
// Writer-only choice, ignored by readers: see select_auto_prx_codec.
uint32_t zstd_min_saving_percent = 0;
+ // Writer-only: when set, the segment's budget chooses the share instead.
+ PrxZstdBudget* zstd_budget = nullptr;
};
enum class PrxWindowBuildOutcome : uint8_t {
@@ -92,6 +137,12 @@ inline constexpr PrxWindowLimits kReaderPrxWindowLimits {
.max_uncomp_bytes = 256U * 1024 * 1024,
};
+// The codec of a window under the writer's limits: select_auto_prx_codec with
the fixed share, or,
+// when the limits carry a budget, the smallest frame unless the budget trades
it for a faster one.
+AutoPrxCodecChoice choose_auto_prx_codec(const PrxWindowLimits& limits, size_t
pfor_payload_size,
+ size_t plain_payload_size, size_t
compressed_payload_size,
+ bool has_compressed);
+
// Writer policies may tighten, but never exceed, the reader's allocation
// guards. Keeping this validation in the format layer makes it impossible for
// a caller to configure a writer that emits frames the current reader rejects.
diff --git a/be/src/storage/index/inverted/snii/writer/logical_index_writer.cpp
b/be/src/storage/index/inverted/snii/writer/logical_index_writer.cpp
index 2a540a37fcd..54167f73d9b 100644
--- a/be/src/storage/index/inverted/snii/writer/logical_index_writer.cpp
+++ b/be/src/storage/index/inverted/snii/writer/logical_index_writer.cpp
@@ -556,7 +556,9 @@ LogicalIndexWriter::LogicalIndexWriter(const
SniiIndexInput& in, TrackedNullDoci
:
in.mem_reporter->make_reservation()),
bsbf_bytes_reservation_(in.mem_reporter == nullptr
? MemoryReporter::Reservation()
- :
in.mem_reporter->make_reservation()) {}
+ :
in.mem_reporter->make_reservation()) {
+ prx_window_limits_.zstd_budget = in.prx_zstd_budget ? &prx_zstd_budget_ :
nullptr;
+}
Status LogicalIndexWriter::reserve_term_hash_for_append() {
if (memory_reporter_ == nullptr || term_hashes_.size() <
term_hashes_.capacity()) {
diff --git a/be/src/storage/index/inverted/snii/writer/logical_index_writer.h
b/be/src/storage/index/inverted/snii/writer/logical_index_writer.h
index 7a3375f74f1..9213fe6d98f 100644
--- a/be/src/storage/index/inverted/snii/writer/logical_index_writer.h
+++ b/be/src/storage/index/inverted/snii/writer/logical_index_writer.h
@@ -76,6 +76,9 @@ struct SniiIndexInput {
// tests may only tighten them to exercise extreme-window behavior without
// allocating hundreds of MiB.
format::PrxWindowLimits prx_window_limits = format::kReaderPrxWindowLimits;
+ // When set, the .prx windows of the index share one
format::PrxZstdBudget, which replaces
+ // prx_window_limits.zstd_min_saving_percent.
+ bool prx_zstd_budget = false;
// Lexicographically sorted terms with ascending-docid postings. Used when
// `term_source` is null (callers that already hold a materialized vector,
// e.g. unit tests). The writer reads but does not retain these.
@@ -360,6 +363,8 @@ private:
int dict_block_zstd_level_ = 3;
int prx_zstd_level_ = 3;
format::PrxWindowLimits prx_window_limits_ =
format::kReaderPrxWindowLimits;
+ // The windows of the index share it when SniiIndexInput::prx_zstd_budget
is set.
+ format::PrxZstdBudget prx_zstd_budget_;
// The DICT region (zstd-compressed blocks) is staged here as blocks
flush. It must
// land contiguously AFTER the posting region (which streams concurrently
to the
// output), so it cannot stream directly; the orchestrator streams it into
the
diff --git a/be/src/storage/index/inverted/snii/writer/posting_prx_encoder.cpp
b/be/src/storage/index/inverted/snii/writer/posting_prx_encoder.cpp
index 36ebed0338f..9797c2b919c 100644
--- a/be/src/storage/index/inverted/snii/writer/posting_prx_encoder.cpp
+++ b/be/src/storage/index/inverted/snii/writer/posting_prx_encoder.cpp
@@ -176,8 +176,7 @@ Status encode_position_payloads(const PostingPositionView&
positions,
Status choose_position_codec(PostingByteBuffer* plain, PostingByteBuffer* pfor,
PostingByteBuffer* compressed, int level, bool
singleton,
- uint32_t byte_limit, uint32_t
zstd_min_saving_percent,
- format::PrxCodec* codec) {
+ const format::PrxWindowLimits& limits,
format::PrxCodec* codec) {
if (level >= 0) {
*codec = format::PrxCodec::kRaw;
if (level > 0) {
@@ -187,6 +186,7 @@ Status choose_position_codec(PostingByteBuffer* plain,
PostingByteBuffer* pfor,
return Status::OK();
}
*codec = singleton ? format::PrxCodec::kRaw : format::PrxCodec::kPfor;
+ const uint32_t byte_limit = limits.max_uncomp_bytes;
const bool use_zstd = plain->size() >= format::kPrxAutoZstdMinBytes;
if (singleton || plain->size() > byte_limit || (!use_zstd && pfor->size()
<= byte_limit)) {
return Status::OK();
@@ -194,8 +194,8 @@ Status choose_position_codec(PostingByteBuffer* plain,
PostingByteBuffer* pfor,
if (use_zstd) {
RETURN_IF_ERROR(compress_posting_bytes(plain, -level, compressed));
}
- *codec = format::select_auto_prx_codec(pfor->size(), plain->size(),
compressed->size(),
- use_zstd, byte_limit,
zstd_min_saving_percent)
+ *codec = format::choose_auto_prx_codec(limits, pfor->size(),
plain->size(), compressed->size(),
+ use_zstd)
.codec;
return Status::OK();
}
@@ -451,9 +451,8 @@ Status PostingPrxEncoder::build_replayable(const
PostingPositionView& positions,
return Status::OK();
}
format::PrxCodec codec = format::PrxCodec::kRaw;
- RETURN_IF_ERROR(choose_position_codec(
- &plain, &pfor, &compressed, level, freqs.size() == 1 &&
freqs.front() == 1,
- limits.max_uncomp_bytes, limits.zstd_min_saving_percent, &codec));
+ RETURN_IF_ERROR(choose_position_codec(&plain, &pfor, &compressed, level,
+ freqs.size() == 1 && freqs.front()
== 1, limits, &codec));
ByteSink header;
header.put_u8(static_cast<uint8_t>(codec));
header.put_varint32(
diff --git
a/be/test/storage/index/inverted/snii/compaction/snii_streamed_session_test.cpp
b/be/test/storage/index/inverted/snii/compaction/snii_streamed_session_test.cpp
index 3eabe97a226..939f8fda618 100644
---
a/be/test/storage/index/inverted/snii/compaction/snii_streamed_session_test.cpp
+++
b/be/test/storage/index/inverted/snii/compaction/snii_streamed_session_test.cpp
@@ -23,6 +23,7 @@
#include <limits>
#include <memory>
#include <numeric>
+#include <random>
#include <span>
#include <string>
#include <type_traits>
@@ -706,6 +707,112 @@ TEST(SniiStreamedWriterSessionTest,
TightByteLimitKeepsReadableLegacySlimFrame)
EXPECT_EQ(entry.enc, format::DictEntryEnc::kSlim);
}
+namespace {
+
+// Documents 0..docs-1 with six positions each. In every window of
kFrqBaseUnit documents the first
+// `repeated` share one list, which zstd stores about once; the others ascend
by random steps of 1 to
+// 15, about four bits each for both zstd and PFOR.
+std::vector<PostingDoc> partly_repeated_positions(std::mt19937* rng, uint32_t
docs,
+ uint32_t repeated) {
+ std::uniform_int_distribution<uint32_t> step(1, 15);
+ std::vector<PostingDoc> out(docs);
+ for (uint32_t doc = 0; doc < docs; ++doc) {
+ out[doc].docid = doc;
+ if (doc % format::kFrqBaseUnit < repeated) {
+ out[doc].positions = {2, 9, 11, 20, 27, 33};
+ continue;
+ }
+ uint32_t position = 0;
+ for (int i = 0; i < 6; ++i) {
+ position += step(*rng);
+ out[doc].positions.push_back(position);
+ }
+ }
+ return out;
+}
+
+// The smallest frame of a window and its frame without zstd.
+std::pair<uint64_t, uint64_t> window_frames(std::span<const PostingDoc> docs) {
+ std::vector<uint32_t> flat;
+ std::vector<uint32_t> freqs;
+ for (const PostingDoc& doc : docs) {
+ flat.insert(flat.end(), doc.positions.begin(), doc.positions.end());
+ freqs.push_back(static_cast<uint32_t>(doc.positions.size()));
+ }
+ const auto frame = [&](uint32_t zstd_min_saving_percent) {
+ format::PrxWindowLimits limits = format::kReaderPrxWindowLimits;
+ limits.zstd_min_saving_percent = zstd_min_saving_percent;
+ ByteSink sink;
+ assert_ok(format::build_prx_window_flat(flat, freqs, -3, limits,
&sink));
+ return static_cast<uint64_t>(sink.size());
+ };
+ return {frame(0), frame(100)};
+}
+
+} // namespace
+
+// Every window here is smaller as zstd, by less than 30%. The fixed share
stores all of them in
+// their faster frame; the budget only as many as kPrxZstdBudgetPercent of the
smallest frames pays
+// for, in the ordinary build and in the streamed one alike.
+TEST(SniiStreamedWriterSessionTest,
PrxZstdBudgetBoundsTheBytesTradedForFasterReads) {
+ std::mt19937 rng(20261028);
+ std::vector<TermPostings> terms;
+ uint64_t smallest_bytes = 0;
+ uint64_t faster_bytes = 0;
+ // How much zstd saves depends on its own overheads, so keep the terms
whose two windows both
+ // save something and less than 30%.
+ for (uint32_t t = 0; t < 2000 && terms.size() < 150; ++t) {
+ std::vector<PostingDoc> docs =
+ partly_repeated_positions(&rng, 2 * format::kFrqBaseUnit, 20 +
t % 120);
+ uint64_t term_smallest = 0;
+ uint64_t term_faster = 0;
+ bool kept = true;
+ for (size_t begin = 0; begin < docs.size(); begin +=
format::kFrqBaseUnit) {
+ const auto [smallest, faster] =
+ window_frames(std::span(docs).subspan(begin,
format::kFrqBaseUnit));
+ kept &= smallest < faster && (faster - smallest) * 100 < faster *
30;
+ term_smallest += smallest;
+ term_faster += faster;
+ }
+ if (kept) {
+ smallest_bytes += term_smallest;
+ faster_bytes += term_faster;
+ terms.push_back(make_term("t" + std::to_string(10000 + t),
std::move(docs)));
+ }
+ }
+ ASSERT_EQ(terms.size(), 150);
+ // Trading every window does not fit the budget.
+ ASSERT_GT((faster_bytes - smallest_bytes) * 100,
+ smallest_bytes * format::kPrxZstdBudgetPercent);
+
+ const auto written = [&](bool streamed, bool budget, uint32_t
zstd_min_saving_percent) {
+ SniiIndexInput input;
+ input.index_id = 74;
+ input.index_suffix = "prx_budget";
+ input.config = format::IndexConfig::kDocsPositions;
+ input.doc_count = 2 * format::kFrqBaseUnit;
+ input.prx_zstd_budget = budget;
+ input.prx_window_limits.zstd_min_saving_percent =
zstd_min_saving_percent;
+ input.terms = terms;
+ MemoryFile file;
+ assert_ok(streamed ? write_streamed_index(std::move(input), &file)
+ : write_ordinary_index(std::move(input), &file));
+ return file.bytes_written();
+ };
+ for (bool streamed : {false, true}) {
+ const uint64_t smallest = written(streamed, false, 0);
+ const uint64_t fixed = written(streamed, false, 30);
+ const uint64_t budgeted = written(streamed, true, 30);
+ // The windows land in the posting region as they are; the lengths
recorded for them move
+ // the rest of the segment by a few bytes per term.
+ const uint64_t slack = 16 * terms.size();
+ EXPECT_GE(fixed + slack, smallest + (faster_bytes - smallest_bytes))
<< streamed;
+ EXPECT_GT(budgeted, smallest + slack) << streamed;
+ EXPECT_LE(budgeted, smallest + smallest_bytes *
format::kPrxZstdBudgetPercent / 100 + slack)
+ << streamed;
+ }
+}
+
#ifdef BE_TEST
TEST(SniiStreamedWriterSessionTest, AutoCodecChoosesSmallestReadableRawFrame) {
// All three codecs are reader-safe here. Complete frame sizes are
PFOR=707,
diff --git a/be/test/storage/index/inverted/snii/format/prx_pod_test.cpp
b/be/test/storage/index/inverted/snii/format/prx_pod_test.cpp
index dded71d4455..56b3aa1f869 100644
--- a/be/test/storage/index/inverted/snii/format/prx_pod_test.cpp
+++ b/be/test/storage/index/inverted/snii/format/prx_pod_test.cpp
@@ -44,12 +44,19 @@ using doris::snii::pfor_encode;
using doris::snii::Slice;
using doris::snii::format::build_prx_window;
using doris::snii::format::build_prx_window_flat;
+using doris::snii::format::choose_auto_prx_codec;
using doris::snii::format::kFrqBaseUnit;
+using doris::snii::format::kPrxZstdBudgetPercent;
+using doris::snii::format::kPrxZstdBudgetPriorPercent;
+using doris::snii::format::kPrxZstdBudgetWarmupWindows;
+using doris::snii::format::kReaderPrxWindowLimits;
using doris::snii::format::PrxCodec;
using doris::snii::format::PrxCsrAllocationGate;
using doris::snii::format::PrxDecodeContext;
using doris::snii::format::PrxDecodeStats;
using doris::snii::format::PrxDecodedShape;
+using doris::snii::format::PrxWindowLimits;
+using doris::snii::format::PrxZstdBudget;
using doris::snii::format::read_prx_window;
using doris::snii::format::read_prx_window_csr;
using doris::snii::format::read_prx_window_csr_for_selection;
@@ -1488,6 +1495,106 @@ TEST(SniiPrxPodTest,
ZstdMinSavingAboveOneHundredPercentIsRejected) {
EXPECT_FALSE(doris::snii::format::validate_prx_window_limits(limits).ok());
}
+namespace {
+
+// Records a window whose zstd frame is `zstd` bytes and whose PFOR frame is
`pfor` bytes.
+bool trade(PrxZstdBudget* budget, uint64_t zstd, uint64_t pfor) {
+ return budget->trade(zstd, pfor - zstd, static_cast<uint32_t>((pfor -
zstd) * 100 / pfor));
+}
+
+} // namespace
+
+TEST(SniiPrxZstdBudget, KeepsThePriorShareUntilItHasSeenEnoughWindows) {
+ PrxZstdBudget budget;
+ for (uint32_t i = 0; i + 1 < kPrxZstdBudgetWarmupWindows; ++i) {
+ // zstd saves 50%, above the prior share: the window keeps zstd.
+ EXPECT_FALSE(trade(&budget, 500, 1000));
+ EXPECT_EQ(budget.min_saving_percent(), kPrxZstdBudgetPriorPercent);
+ }
+ EXPECT_FALSE(trade(&budget, 500, 1000));
+ // Trading these windows would double their bytes: the share stops right
below their saving.
+ EXPECT_EQ(budget.min_saving_percent(), 50);
+}
+
+// Nine windows in ten save 60% and one saves 5%. Trading the 5% windows costs
50 bytes for every
+// 4,550 bytes of zstd frames, about 1.1%, so every one of them is traded and
none of the others.
+TEST(SniiPrxZstdBudget, TradesTheWindowsZstdShrinksLeast) {
+ PrxZstdBudget budget;
+ for (int round = 0; round < 100; ++round) {
+ for (int i = 0; i < 9; ++i) {
+ EXPECT_FALSE(trade(&budget, 400, 1000)) << round;
+ }
+ EXPECT_TRUE(trade(&budget, 950, 1000)) << round;
+ }
+ EXPECT_EQ(budget.min_saving_percent(), 60);
+}
+
+// The share comes from the windows already seen, so a window saving less than
all of them is below
+// it whatever it costs. Here every window saves less than the one before;
what the segment has
+// actually spent still never exceeds the budget.
+TEST(SniiPrxZstdBudget, NeverSpendsMoreThanTheBudgetWhateverTheOrder) {
+ PrxZstdBudget budget;
+ uint64_t zstd_bytes = 0;
+ uint64_t spent = 0;
+ uint32_t traded = 0;
+ for (uint64_t zstd = 100; zstd <= 990; ++zstd) {
+ zstd_bytes += zstd;
+ if (trade(&budget, zstd, 1000)) {
+ spent += 1000 - zstd;
+ ++traded;
+ }
+ ASSERT_LE(spent * 100, zstd_bytes * kPrxZstdBudgetPercent) << "zstd
frame " << zstd;
+ }
+ EXPECT_GT(traded, 0);
+}
+
+// Windows with nothing to trade count toward the bytes the budget is a share
of.
+TEST(SniiPrxZstdBudget, WindowsWithNothingToTradeCountTowardTheBudget) {
+ PrxZstdBudget budget;
+ for (int i = 0; i < 640; ++i) {
+ budget.add(1000);
+ }
+ // Nothing traded yet, so every share fits.
+ EXPECT_EQ(budget.min_saving_percent(), 100);
+ for (int i = 0; i < 64; ++i) {
+ EXPECT_TRUE(trade(&budget, 900, 1000)) << i;
+ }
+}
+
+// Frame sizes below: a PFOR payload of p bytes is a (p + 7)-byte frame, a raw
payload of r bytes an
+// (r + 7)-byte frame, and a zstd payload of c bytes from a 2000-byte plain
payload a (c + 9)-byte
+// frame (for payloads of 128 to 16383 bytes).
+TEST(SniiPrxPodTest, ChooseAutoCodecTradesWithTheBudgetOnlyWhenItHasOne) {
+ PrxWindowLimits limits = kReaderPrxWindowLimits;
+ limits.zstd_min_saving_percent = 30;
+ // zstd frame 900 against PFOR frame 1000 saves 10%: the fixed share
stores PFOR.
+ EXPECT_EQ(choose_auto_prx_codec(limits, 993, 2000, 891, true).codec,
PrxCodec::kPfor);
+
+ PrxZstdBudget budget;
+ limits.zstd_budget = &budget;
+ // The budget replaces the fixed share. The first window would cost 100
bytes against a budget
+ // of 72, the second fits a budget of 144.
+ EXPECT_EQ(choose_auto_prx_codec(limits, 993, 2000, 891, true).codec,
PrxCodec::kZstd);
+ EXPECT_EQ(choose_auto_prx_codec(limits, 993, 2000, 891, true).codec,
PrxCodec::kPfor);
+}
+
+TEST(SniiPrxPodTest, ChooseAutoCodecTradesZstdOnlyForAReadableFasterFrame) {
+ PrxZstdBudget budget;
+ for (uint32_t i = 0; i < kPrxZstdBudgetWarmupWindows; ++i) {
+ budget.add(10000);
+ }
+ PrxWindowLimits limits = kReaderPrxWindowLimits;
+ limits.zstd_budget = &budget;
+ // PFOR frame 1107, raw frame 1007, zstd frame 900: the faster frame is
raw.
+ EXPECT_EQ(choose_auto_prx_codec(limits, 1100, 1000, 891, true).codec,
PrxCodec::kRaw);
+ // PFOR beyond the reader byte limit and the plain payload within it: zstd
is the only readable
+ // compressed frame and stays.
+ limits.max_uncomp_bytes = 1500;
+ EXPECT_EQ(choose_auto_prx_codec(limits, 1600, 1400, 500, true).codec,
PrxCodec::kZstd);
+ // No zstd frame below kPrxAutoZstdMinBytes: nothing to trade.
+ EXPECT_EQ(choose_auto_prx_codec(limits, 300, 400, 0, false).codec,
PrxCodec::kPfor);
+}
+
// [functional] F-RT-small: a small flat window round-trips through the CSR
reader
// (codec=pfor path) back to the original per-doc positions.
TEST(SniiPrxPodTest, SmallFlatWindowRoundTripsViaCsr) {
diff --git
a/be/test/storage/index/inverted/snii/writer/snii_writer_golden_bytes_test.cpp
b/be/test/storage/index/inverted/snii/writer/snii_writer_golden_bytes_test.cpp
index e9a74d04f3a..0a729b3a024 100644
---
a/be/test/storage/index/inverted/snii/writer/snii_writer_golden_bytes_test.cpp
+++
b/be/test/storage/index/inverted/snii/writer/snii_writer_golden_bytes_test.cpp
@@ -46,6 +46,11 @@
#include "util/slice.h"
namespace doris::segment_v2 {
+
+// index_file_writer.cpp keeps it out of its anonymous namespace for this test.
+void snii_resolve_index_write_params(bool is_direct_load, bool has_norms,
+ doris::snii::writer::SniiIndexInput*
input);
+
namespace {
constexpr int64_t kIndexId = 9;
@@ -320,12 +325,30 @@ constexpr uint64_t kGoldenKeywordDocsOnly =
0x27cec04c70573201ULL;
// The default of the knob is part of the written format's behavior: the
fixture above pins it to 0
// for the digests, so this reads the value a fresh process starts with.
-TEST(SniiWriterPrxZstdSaving, DefaultIsThirtyPercent) {
- EXPECT_EQ(config::snii_prx_zstd_min_saving_percent, 30);
+TEST(SniiWriterPrxZstdSaving, DefaultLetsEachIndexSpendItsBudget) {
+ EXPECT_EQ(config::snii_prx_zstd_min_saving_percent, -1);
+}
+
+TEST(SniiWriterPrxZstdSaving, NegativeConfigGivesEachIndexABudget) {
+ const int32_t saved = config::snii_prx_zstd_min_saving_percent;
+ const auto resolve = [](int32_t value) {
+ config::snii_prx_zstd_min_saving_percent = value;
+ doris::snii::writer::SniiIndexInput input;
+ input.config = doris::snii::format::IndexConfig::kDocsPositions;
+ snii_resolve_index_write_params(/*is_direct_load=*/true,
/*has_norms=*/false, &input);
+ return input;
+ };
+ EXPECT_TRUE(resolve(-1).prx_zstd_budget);
+ EXPECT_FALSE(resolve(0).prx_zstd_budget);
+ EXPECT_EQ(resolve(0).prx_window_limits.zstd_min_saving_percent, 0);
+ EXPECT_FALSE(resolve(30).prx_zstd_budget);
+ EXPECT_EQ(resolve(30).prx_window_limits.zstd_min_saving_percent, 30);
+ EXPECT_EQ(resolve(150).prx_window_limits.zstd_min_saving_percent, 100);
+ config::snii_prx_zstd_min_saving_percent = saved;
}
// Every document repeats the same positions, so a window is far smaller as
zstd than as PFOR.
-// 0 and 30 keep zstd; 100 never picks it, so the segment is larger.
+// 0, 30 and the budget keep zstd; 100 never picks it, so the segment is
larger.
TEST_F(SniiWriterGoldenBytes, PrxZstdMinSavingConfigReachesTheWriter) {
std::vector<std::string> rows;
for (int doc = 0; doc < 2000; ++doc) {
@@ -345,7 +368,10 @@ TEST_F(SniiWriterGoldenBytes,
PrxZstdMinSavingConfigReachesTheWriter) {
const size_t thirty = written_size("saving_30", meta, rows);
config::snii_prx_zstd_min_saving_percent = 100;
const size_t never_zstd = written_size("saving_100", meta, rows);
+ config::snii_prx_zstd_min_saving_percent = -1;
+ const size_t budgeted = written_size("saving_budget", meta, rows);
EXPECT_EQ(thirty, smallest);
+ EXPECT_EQ(budgeted, smallest);
EXPECT_GT(never_zstd, smallest + 1000) << "smallest=" << smallest;
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
