Skip to content

Commit 170822d

Browse files
martin.foo838claude
andcommitted
[improvement](be) Let each SNII index spend a size budget on faster .prx windows
### What problem does this PR solve? Issue Number: None Related PR: #69649 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 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%. 10M rows each, same binary, one stream load per table, size against the smallest frames (0): - AgentLogs: index +4.59% with 30, +3.37% with the budget (table +2.13%, +1.57%). The phrase queries read the same frames: all PFOR for DS1, DS2, DS6, DS7, A6 and A9 with both, and 326 against 324 zstd frames of 5011 for DS4, 1049 against 1041 of 25930 for A10. - TextBench: index +0.89% with 30, +0.79% with the budget (table +0.51%, +0.45%). Most windows stay zstd either way (P1 'connection reset': 582 against 583 zstd frames of 599). - Data bytes are identical; the index written with 0 and with 30 is byte-for-byte the size the previous binary writes. - Hot queries, budget data against 30 data in one process (6-10 paired cycles, ratio of medians per cycle): all 25 AgentLogs and 15 TextBench queries 0.96-1.04, the same results. - 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 their size; snii_prx_zstd_min_saving_percent defaults to -1 for this, and 0-100 still sets a fixed percentage. ### Check List (For Author) - Test: Unit Test (SniiPrxZstdBudget: the prior share, the windows zstd shrinks least traded first, the bound under a descending order, windows with nothing to trade; SniiPrxPodTest: the faster frame and when the budget is asked; SniiStreamedWriterSessionTest: windows that save 1-29% through the ordinary and the streamed build, where 30 trades all of them and the budget at most 8%; SniiWriterPrxZstdSaving: the default and the config mapping). Manual test: index size of 10M-row AgentLogs and TextBench loads with 0, 30 and the budget, frames read per codec from query profiles. - Behavior changed: Yes (the default .prx codec choice of newly written segments; existing segments are read as before) - Does this need documentation: No Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent 751bdfa commit 170822d

11 files changed

Lines changed: 398 additions & 19 deletions

File tree

‎be/src/common/config.cpp‎

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1428,10 +1428,12 @@ DEFINE_mInt32(snii_dict_block_zstd_level, "3");
14281428
DEFINE_mInt32(snii_prx_zstd_level, "3");
14291429
// A .prx window is stored zstd-compressed only if that frame is smaller than the PFOR one by at
14301430
// least this percentage; 0 picks the smaller frame. Every read of a zstd window pays a
1431-
// decompression that PFOR does not, and on text positions zstd beats PFOR by 20-30% only on the
1432-
// large windows of frequent terms, which are the ones phrase queries read most: 30 costs about 2%
1433-
// of the index size. Readers handle every codec, so changing this never affects existing segments.
1434-
DEFINE_mInt32(snii_prx_zstd_min_saving_percent, "30");
1431+
// decompression that PFOR does not, but how much zstd saves depends on the data, so no one
1432+
// percentage fits all data. The default (negative) lets each index choose: it stores in their
1433+
// faster frame the windows zstd shrinks least, spending at most 8% of their smallest size (see
1434+
// format::PrxZstdBudget). Readers handle every codec, so changing this never affects existing
1435+
// segments.
1436+
DEFINE_mInt32(snii_prx_zstd_min_saving_percent, "-1");
14351437
// Zstd level for direct-load .prx regions. Compaction rewrites them using snii_prx_zstd_level.
14361438
DEFINE_mInt32(snii_prx_zstd_level_direct_load, "3");
14371439
// G16-d: target SNII dict block size in bytes; 0 uses the format default

‎be/src/common/config.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1467,7 +1467,8 @@ DECLARE_mInt32(inverted_index_max_buffered_docs);
14671467
DECLARE_mInt32(snii_dict_block_zstd_level);
14681468
DECLARE_mInt32(snii_prx_zstd_level);
14691469
// A .prx window is stored zstd-compressed only if that frame is smaller than the PFOR one by at
1470-
// least this percentage; 0 picks the smaller frame. Affects segments written from now on.
1470+
// least this percentage; 0 picks the smaller frame. Negative (the default) lets each index choose
1471+
// within a size budget. Affects segments written from now on.
14711472
DECLARE_mInt32(snii_prx_zstd_min_saving_percent);
14721473
// Patch C: prx zstd level for DIRECT-LOAD segments only (default 3, cheaper
14731474
// import); compaction rewrites at snii_prx_zstd_level so settled segments are

‎be/src/storage/index/index_file_writer.cpp‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -146,6 +146,8 @@ void snii_resolve_index_write_params(bool is_direct_load, bool has_norms,
146146
input->prx_zstd_level = std::clamp(
147147
is_direct_load ? config::snii_prx_zstd_level_direct_load : config::snii_prx_zstd_level,
148148
3, 19);
149+
// Negative: the index chooses the percentage within its own size budget.
150+
input->prx_zstd_budget = config::snii_prx_zstd_min_saving_percent < 0;
149151
input->prx_window_limits.zstd_min_saving_percent =
150152
static_cast<uint32_t>(std::clamp(config::snii_prx_zstd_min_saving_percent, 0, 100));
151153
// G16-d: dict block size experiment knob; <= 0 keeps the format default.

‎be/src/storage/index/inverted/snii/format/prx_pod.cpp‎

Lines changed: 84 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -488,6 +488,88 @@ AutoPrxCodecChoice select_auto_prx_codec(size_t pfor_payload_size, size_t plain_
488488
return choice;
489489
}
490490

491+
void PrxZstdBudget::add(uint64_t smallest_frame_bytes) {
492+
_smallest_bytes += smallest_frame_bytes;
493+
count_window();
494+
}
495+
496+
bool PrxZstdBudget::trade(uint64_t zstd_frame_bytes, uint64_t faster_extra_bytes,
497+
uint32_t saving_percent) {
498+
_smallest_bytes += zstd_frame_bytes;
499+
const bool faster =
500+
saving_percent < _min_saving_percent &&
501+
(_spent_bytes + faster_extra_bytes) * 100 <= _smallest_bytes * kPrxZstdBudgetPercent;
502+
if (faster) {
503+
_spent_bytes += faster_extra_bytes;
504+
}
505+
_extra_by_saving[std::min<uint32_t>(saving_percent, 100)] += faster_extra_bytes;
506+
count_window();
507+
return faster;
508+
}
509+
510+
void PrxZstdBudget::count_window() {
511+
if (++_windows < kPrxZstdBudgetWarmupWindows) {
512+
return;
513+
}
514+
// The largest share whose trades, over the windows seen so far, fit the budget. A window whose
515+
// saving is p percent is traded under every share above p, so the trades of share s are the
516+
// buckets below s.
517+
const uint64_t allowed = _smallest_bytes * kPrxZstdBudgetPercent / 100;
518+
uint64_t extra = 0;
519+
uint32_t share = 0;
520+
while (share < 100 && extra + _extra_by_saving[share] <= allowed) {
521+
extra += _extra_by_saving[share];
522+
++share;
523+
}
524+
_min_saving_percent = share;
525+
}
526+
527+
namespace {
528+
529+
uint64_t chosen_frame_size(PrxCodec codec, size_t pfor_payload_size, size_t plain_payload_size,
530+
size_t compressed_payload_size) {
531+
switch (codec) {
532+
case PrxCodec::kPfor:
533+
return pfor_frame_size(pfor_payload_size);
534+
case PrxCodec::kZstd:
535+
return zstd_frame_size(plain_payload_size, compressed_payload_size);
536+
default:
537+
return raw_frame_size(plain_payload_size);
538+
}
539+
}
540+
541+
} // namespace
542+
543+
AutoPrxCodecChoice choose_auto_prx_codec(const PrxWindowLimits& limits, size_t pfor_payload_size,
544+
size_t plain_payload_size, size_t compressed_payload_size,
545+
bool has_compressed) {
546+
const auto select = [&](uint32_t zstd_min_saving_percent) {
547+
return select_auto_prx_codec(pfor_payload_size, plain_payload_size, compressed_payload_size,
548+
has_compressed, limits.max_uncomp_bytes,
549+
zstd_min_saving_percent);
550+
};
551+
PrxZstdBudget* const budget = limits.zstd_budget;
552+
if (budget == nullptr) {
553+
return select(limits.zstd_min_saving_percent);
554+
}
555+
const auto bytes = [&](AutoPrxCodecChoice choice) {
556+
return chosen_frame_size(choice.codec, pfor_payload_size, plain_payload_size,
557+
compressed_payload_size);
558+
};
559+
const AutoPrxCodecChoice smallest = select(0);
560+
if (smallest.codec != PrxCodec::kZstd || pfor_payload_size > limits.max_uncomp_bytes) {
561+
budget->add(bytes(smallest));
562+
return smallest;
563+
}
564+
// Never zstd: PFOR, or raw when that is smaller still.
565+
const AutoPrxCodecChoice faster = select(100);
566+
const uint64_t zstd_bytes = bytes(smallest);
567+
const uint64_t pfor_bytes = pfor_frame_size(pfor_payload_size);
568+
const auto saving_percent = static_cast<uint32_t>((pfor_bytes - zstd_bytes) * 100 / pfor_bytes);
569+
return budget->trade(zstd_bytes, bytes(faster) - zstd_bytes, saving_percent) ? faster
570+
: smallest;
571+
}
572+
491573
namespace {
492574

493575
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,
555637
testing::note_prx_raw_build();
556638
RETURN_IF_ERROR(zstd_compress(plain.view(), zstd_level, &compressed));
557639
}
558-
const AutoPrxCodecChoice choice = select_auto_prx_codec(
559-
payload.size(), plain.size(), compressed.size(), has_compressed,
560-
limits.max_uncomp_bytes, limits.zstd_min_saving_percent);
640+
const AutoPrxCodecChoice choice = choose_auto_prx_codec(
641+
limits, payload.size(), plain.size(), compressed.size(), has_compressed);
561642
DCHECK(choice.readable);
562643
if (choice.codec == PrxCodec::kZstd) {
563644
write_zstd_compressed(plain.view(), Slice(compressed), sink);

‎be/src/storage/index/inverted/snii/format/prx_pod.h‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717

1818
#pragma once
1919

20+
#include <array>
2021
#include <cstddef>
2122
#include <cstdint>
2223
#include <span>
@@ -73,12 +74,52 @@ AutoPrxCodecChoice select_auto_prx_codec(size_t pfor_payload_size, size_t plain_
7374
uint32_t max_uncomp_bytes,
7475
uint32_t zstd_min_saving_percent = 0);
7576

77+
// Decides which .prx windows of one index of one segment are stored in a larger frame that reads
78+
// faster. Every read of a zstd window pays a decompression that PFOR does not, so storing a window
79+
// whose smallest frame is zstd in its PFOR (or smaller raw) frame trades bytes for reads. How much
80+
// zstd saves depends on the data: a fixed share (zstd_min_saving_percent) of 30 spends about 8% more
81+
// bytes on the windows of agent logs, about 5% on those of service logs, and much more on data whose
82+
// windows zstd shrinks by just under the share. The budget instead spends at most
83+
// kPrxZstdBudgetPercent of the smallest frames, on the windows zstd shrinks least: a window is
84+
// traded when its saving is below the share whose trades, over the windows seen so far, fit the
85+
// budget, and when what has actually been spent still fits it, so no order of windows can make it
86+
// spend more. Until kPrxZstdBudgetWarmupWindows windows are seen the share is
87+
// kPrxZstdBudgetPriorPercent. Writer-only and deterministic for a given input.
88+
inline constexpr uint32_t kPrxZstdBudgetPercent = 8;
89+
inline constexpr uint32_t kPrxZstdBudgetPriorPercent = 30;
90+
inline constexpr uint32_t kPrxZstdBudgetWarmupWindows = 64;
91+
92+
class PrxZstdBudget {
93+
public:
94+
// Records a window that has nothing to trade: zstd is not its smallest frame, or PFOR is not
95+
// readable.
96+
void add(uint64_t smallest_frame_bytes);
97+
// Records a window whose smallest frame is zstd. `faster_extra_bytes` is what its faster frame
98+
// costs on top of the zstd one, `saving_percent` how much smaller the zstd frame is than the PFOR
99+
// one, in whole percent of the PFOR frame. Returns whether to store the faster frame.
100+
bool trade(uint64_t zstd_frame_bytes, uint64_t faster_extra_bytes, uint32_t saving_percent);
101+
// A window saving less than this share is traded if the budget allows.
102+
uint32_t min_saving_percent() const { return _min_saving_percent; }
103+
104+
private:
105+
void count_window();
106+
107+
// The extra bytes of trading each window seen, by its saving_percent.
108+
std::array<uint64_t, 101> _extra_by_saving {};
109+
uint64_t _smallest_bytes = 0;
110+
uint64_t _spent_bytes = 0;
111+
uint32_t _windows = 0;
112+
uint32_t _min_saving_percent = kPrxZstdBudgetPriorPercent;
113+
};
114+
76115
struct PrxWindowLimits {
77116
uint32_t max_docs;
78117
uint32_t max_positions;
79118
uint32_t max_uncomp_bytes;
80119
// Writer-only choice, ignored by readers: see select_auto_prx_codec.
81120
uint32_t zstd_min_saving_percent = 0;
121+
// Writer-only: when set, the segment's budget chooses the share instead.
122+
PrxZstdBudget* zstd_budget = nullptr;
82123
};
83124

84125
enum class PrxWindowBuildOutcome : uint8_t {
@@ -92,6 +133,12 @@ inline constexpr PrxWindowLimits kReaderPrxWindowLimits {
92133
.max_uncomp_bytes = 256U * 1024 * 1024,
93134
};
94135

136+
// The codec of a window under the writer's limits: select_auto_prx_codec with the fixed share, or,
137+
// when the limits carry a budget, the smallest frame unless the budget trades it for a faster one.
138+
AutoPrxCodecChoice choose_auto_prx_codec(const PrxWindowLimits& limits, size_t pfor_payload_size,
139+
size_t plain_payload_size, size_t compressed_payload_size,
140+
bool has_compressed);
141+
95142
// Writer policies may tighten, but never exceed, the reader's allocation
96143
// guards. Keeping this validation in the format layer makes it impossible for
97144
// a caller to configure a writer that emits frames the current reader rejects.

‎be/src/storage/index/inverted/snii/writer/logical_index_writer.cpp‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -556,7 +556,9 @@ LogicalIndexWriter::LogicalIndexWriter(const SniiIndexInput& in, TrackedNullDoci
556556
: in.mem_reporter->make_reservation()),
557557
bsbf_bytes_reservation_(in.mem_reporter == nullptr
558558
? MemoryReporter::Reservation()
559-
: in.mem_reporter->make_reservation()) {}
559+
: in.mem_reporter->make_reservation()) {
560+
prx_window_limits_.zstd_budget = in.prx_zstd_budget ? &prx_zstd_budget_ : nullptr;
561+
}
560562

561563
Status LogicalIndexWriter::reserve_term_hash_for_append() {
562564
if (memory_reporter_ == nullptr || term_hashes_.size() < term_hashes_.capacity()) {

‎be/src/storage/index/inverted/snii/writer/logical_index_writer.h‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,9 @@ struct SniiIndexInput {
7676
// tests may only tighten them to exercise extreme-window behavior without
7777
// allocating hundreds of MiB.
7878
format::PrxWindowLimits prx_window_limits = format::kReaderPrxWindowLimits;
79+
// When set, the .prx windows of the index share one format::PrxZstdBudget, which replaces
80+
// prx_window_limits.zstd_min_saving_percent.
81+
bool prx_zstd_budget = false;
7982
// Lexicographically sorted terms with ascending-docid postings. Used when
8083
// `term_source` is null (callers that already hold a materialized vector,
8184
// e.g. unit tests). The writer reads but does not retain these.
@@ -360,6 +363,8 @@ class LogicalIndexWriter {
360363
int dict_block_zstd_level_ = 3;
361364
int prx_zstd_level_ = 3;
362365
format::PrxWindowLimits prx_window_limits_ = format::kReaderPrxWindowLimits;
366+
// The windows of the index share it when SniiIndexInput::prx_zstd_budget is set.
367+
format::PrxZstdBudget prx_zstd_budget_;
363368
// The DICT region (zstd-compressed blocks) is staged here as blocks flush. It must
364369
// land contiguously AFTER the posting region (which streams concurrently to the
365370
// output), so it cannot stream directly; the orchestrator streams it into the

‎be/src/storage/index/inverted/snii/writer/posting_prx_encoder.cpp‎

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -176,8 +176,7 @@ Status encode_position_payloads(const PostingPositionView& positions,
176176

177177
Status choose_position_codec(PostingByteBuffer* plain, PostingByteBuffer* pfor,
178178
PostingByteBuffer* compressed, int level, bool singleton,
179-
uint32_t byte_limit, uint32_t zstd_min_saving_percent,
180-
format::PrxCodec* codec) {
179+
const format::PrxWindowLimits& limits, format::PrxCodec* codec) {
181180
if (level >= 0) {
182181
*codec = format::PrxCodec::kRaw;
183182
if (level > 0) {
@@ -187,15 +186,16 @@ Status choose_position_codec(PostingByteBuffer* plain, PostingByteBuffer* pfor,
187186
return Status::OK();
188187
}
189188
*codec = singleton ? format::PrxCodec::kRaw : format::PrxCodec::kPfor;
189+
const uint32_t byte_limit = limits.max_uncomp_bytes;
190190
const bool use_zstd = plain->size() >= format::kPrxAutoZstdMinBytes;
191191
if (singleton || plain->size() > byte_limit || (!use_zstd && pfor->size() <= byte_limit)) {
192192
return Status::OK();
193193
}
194194
if (use_zstd) {
195195
RETURN_IF_ERROR(compress_posting_bytes(plain, -level, compressed));
196196
}
197-
*codec = format::select_auto_prx_codec(pfor->size(), plain->size(), compressed->size(),
198-
use_zstd, byte_limit, zstd_min_saving_percent)
197+
*codec = format::choose_auto_prx_codec(limits, pfor->size(), plain->size(), compressed->size(),
198+
use_zstd)
199199
.codec;
200200
return Status::OK();
201201
}
@@ -451,9 +451,8 @@ Status PostingPrxEncoder::build_replayable(const PostingPositionView& positions,
451451
return Status::OK();
452452
}
453453
format::PrxCodec codec = format::PrxCodec::kRaw;
454-
RETURN_IF_ERROR(choose_position_codec(
455-
&plain, &pfor, &compressed, level, freqs.size() == 1 && freqs.front() == 1,
456-
limits.max_uncomp_bytes, limits.zstd_min_saving_percent, &codec));
454+
RETURN_IF_ERROR(choose_position_codec(&plain, &pfor, &compressed, level,
455+
freqs.size() == 1 && freqs.front() == 1, limits, &codec));
457456
ByteSink header;
458457
header.put_u8(static_cast<uint8_t>(codec));
459458
header.put_varint32(

0 commit comments

Comments
 (0)