Skip to content

Commit 0571eb6

Browse files
authored
[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.
1 parent 24dc776 commit 0571eb6

11 files changed

Lines changed: 402 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 the smallest size of the
1434+
// windows that get a zstd frame (see format::PrxZstdBudget). Readers handle every codec, so
1435+
// changing this never affects existing 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
// Handing a few small page-cache reads to the shared prefetch pool costs more than the reads: a

‎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: 51 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,56 @@ 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 of the windows that get a zstd frame (a plain
84+
// payload of at least kPrxAutoZstdMinBytes), the only ones whose codec a share decides, on the
85+
// windows zstd shrinks least: a window is traded when its saving is below the share whose trades,
86+
// over the windows seen so far, fit the budget, and when what has actually been spent still fits
87+
// it, so no order of windows can make it spend more. Until kPrxZstdBudgetWarmupWindows windows are
88+
// seen the share is kPrxZstdBudgetPriorPercent. Windows written without a zstd frame (a singleton,
89+
// or too short to compress) are not counted: no share changes them, and counting their bytes would
90+
// let an index of many short posting lists grow its large windows by more than the budget.
91+
// Writer-only and deterministic for a given input.
92+
inline constexpr uint32_t kPrxZstdBudgetPercent = 8;
93+
inline constexpr uint32_t kPrxZstdBudgetPriorPercent = 30;
94+
inline constexpr uint32_t kPrxZstdBudgetWarmupWindows = 64;
95+
96+
class PrxZstdBudget {
97+
public:
98+
// Records a window that has nothing to trade: zstd is not its smallest frame, or PFOR is not
99+
// readable.
100+
void add(uint64_t smallest_frame_bytes);
101+
// Records a window whose smallest frame is zstd. `faster_extra_bytes` is what its faster frame
102+
// costs on top of the zstd one, `saving_percent` how much smaller the zstd frame is than the PFOR
103+
// one, in whole percent of the PFOR frame. Returns whether to store the faster frame.
104+
bool trade(uint64_t zstd_frame_bytes, uint64_t faster_extra_bytes, uint32_t saving_percent);
105+
// A window saving less than this share is traded if the budget allows.
106+
uint32_t min_saving_percent() const { return _min_saving_percent; }
107+
108+
private:
109+
void count_window();
110+
111+
// The extra bytes of trading each window seen, by its saving_percent.
112+
std::array<uint64_t, 101> _extra_by_saving {};
113+
uint64_t _smallest_bytes = 0;
114+
uint64_t _spent_bytes = 0;
115+
uint32_t _windows = 0;
116+
uint32_t _min_saving_percent = kPrxZstdBudgetPriorPercent;
117+
};
118+
76119
struct PrxWindowLimits {
77120
uint32_t max_docs;
78121
uint32_t max_positions;
79122
uint32_t max_uncomp_bytes;
80123
// Writer-only choice, ignored by readers: see select_auto_prx_codec.
81124
uint32_t zstd_min_saving_percent = 0;
125+
// Writer-only: when set, the segment's budget chooses the share instead.
126+
PrxZstdBudget* zstd_budget = nullptr;
82127
};
83128

84129
enum class PrxWindowBuildOutcome : uint8_t {
@@ -92,6 +137,12 @@ inline constexpr PrxWindowLimits kReaderPrxWindowLimits {
92137
.max_uncomp_bytes = 256U * 1024 * 1024,
93138
};
94139

140+
// The codec of a window under the writer's limits: select_auto_prx_codec with the fixed share, or,
141+
// when the limits carry a budget, the smallest frame unless the budget trades it for a faster one.
142+
AutoPrxCodecChoice choose_auto_prx_codec(const PrxWindowLimits& limits, size_t pfor_payload_size,
143+
size_t plain_payload_size, size_t compressed_payload_size,
144+
bool has_compressed);
145+
95146
// Writer policies may tighten, but never exceed, the reader's allocation
96147
// guards. Keeping this validation in the format layer makes it impossible for
97148
// 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)