This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch branch-4.2
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/branch-4.2 by this push:
new c3259a554e1 branch-4.2: [improvement](be) Add up SNII position counts
a run at a time in selective decode #69891 (#69956)
c3259a554e1 is described below
commit c3259a554e1cb3585036e2e697fcb4f1a930e7f4
Author: github-actions[bot]
<41898282+github-actions[bot]@users.noreply.github.com>
AuthorDate: Tue Nov 3 10:01:50 2026 +0800
branch-4.2: [improvement](be) Add up SNII position counts a run at a time
in selective decode #69891 (#69956)
Cherry-picked from #69891
Co-authored-by: Jack <[email protected]>
---
.../storage/index/inverted/snii/format/prx_pod.cpp | 47 +++++++++-----
.../index/inverted/snii/format/prx_pod_test.cpp | 75 ++++++++++++++++++++++
2 files changed, 105 insertions(+), 17 deletions(-)
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 d6ef8638802..62ca0274910 100644
--- a/be/src/storage/index/inverted/snii/format/prx_pod.cpp
+++ b/be/src/storage/index/inverted/snii/format/prx_pod.cpp
@@ -23,6 +23,7 @@
#include <chrono>
#include <cstddef>
#include <limits>
+#include <numeric>
#include <span>
#include <vector>
@@ -819,6 +820,9 @@ bool should_decode_full_prx_positions(std::span<const
SelectedRange> selected,
return covered_runs * 4 >= total_runs * 3;
}
+// The count of every document of the window is decoded to find where the
selected documents' deltas
+// start, and a sparse candidate set selects none in most runs. So a run is
added up whole, with no
+// branch per document, and then walked from one selected document to the next.
Status decode_selected_pfor_count_ranges(ByteSource* src, uint32_t doc_count,
std::span<const uint32_t>
doc_ordinals,
std::vector<SelectedRange>& selected,
@@ -832,7 +836,6 @@ Status decode_selected_pfor_count_ranges(ByteSource* src,
uint32_t doc_count,
pos_off.push_back(0);
*selected_pos_count = 0;
- uint32_t delta_begin = 0;
size_t next_doc = 0;
*total_pos_count = 0;
*max_frequency = 0;
@@ -841,24 +844,34 @@ Status decode_selected_pfor_count_ranges(ByteSource* src,
uint32_t doc_count,
for (uint32_t run_begin = 0; run_begin < doc_count; run_begin +=
kFrqBaseUnit) {
const uint32_t run_len = std::min<uint32_t>(kFrqBaseUnit, doc_count -
run_begin);
RETURN_IF_ERROR(pfor_decode(src, run_len, run_buf.data()));
+ uint64_t run_sum = 0;
+ uint32_t run_max = 0;
+ uint32_t run_min = std::numeric_limits<uint32_t>::max();
for (uint32_t i = 0; i < run_len; ++i) {
- const uint32_t d = run_begin + i;
- const uint32_t count = run_buf[i];
- *max_frequency = std::max(*max_frequency, count);
- *has_zero_frequency |= count == 0;
- *total_pos_count += count;
- if (*total_pos_count > kMaxWindowPositions) {
- return Status::Error<ErrorCode::INVERTED_INDEX_FILE_CORRUPTED,
false>(
- "prx: pos_count sum exceeds sane cap");
- }
- if (next_doc < doc_ordinals.size() && doc_ordinals[next_doc] == d)
{
- selected.emplace_back(delta_begin, delta_begin + count,
*selected_pos_count);
- *selected_pos_count += count;
- pos_off.push_back(*selected_pos_count);
- ++next_doc;
- }
- delta_begin += count;
+ run_sum += run_buf[i];
+ run_max = std::max(run_max, run_buf[i]);
+ run_min = std::min(run_min, run_buf[i]);
+ }
+ *max_frequency = std::max(*max_frequency, run_max);
+ *has_zero_frequency |= run_min == 0;
+ if (*total_pos_count + run_sum > kMaxWindowPositions) {
+ return Status::Error<ErrorCode::INVERTED_INDEX_FILE_CORRUPTED,
false>(
+ "prx: pos_count sum exceeds sane cap");
+ }
+ // Under the cap, so every sum below fits 32 bits.
+ auto delta_begin = static_cast<uint32_t>(*total_pos_count);
+ const uint32_t* walked = run_buf.data();
+ for (; next_doc < doc_ordinals.size() && doc_ordinals[next_doc] -
run_begin < run_len;
+ ++next_doc) {
+ const uint32_t* doc = run_buf.data() + (doc_ordinals[next_doc] -
run_begin);
+ delta_begin = std::accumulate(walked, doc, delta_begin);
+ selected.emplace_back(delta_begin, delta_begin + *doc,
*selected_pos_count);
+ *selected_pos_count += *doc;
+ pos_off.push_back(*selected_pos_count);
+ delta_begin += *doc;
+ walked = doc + 1;
}
+ *total_pos_count += run_sum;
}
if (next_doc != doc_ordinals.size()) {
return Status::Error<ErrorCode::INVERTED_INDEX_FILE_CORRUPTED, false>(
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 8ff976e2a2c..695ffa3bddc 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
@@ -957,6 +957,81 @@ TEST(SniiPrxPod, SelectiveCsrRejectsInvalidOrdinals) {
}
}
+// The counts of a PFOR run are added up whole, then walked from one selected
document to the next.
+// Sparse and dense selections, the first and last documents of runs, and
documents with no positions
+// or with enough to be PFOR exceptions all come out as the input, with the
shape of the whole window.
+TEST(SniiPrxPod, SelectivePforMatchesInputForRandomWindows) {
+ std::mt19937 rng(20261030);
+ for (int round = 0; round < 300; ++round) {
+ const uint32_t doc_count = 1 + rng() % (3 * kFrqBaseUnit + 20);
+ const uint32_t style = rng() % 3;
+ PerDoc docs(doc_count);
+ PrxDecodedShape want_shape {.total_docs = doc_count};
+ for (auto& doc : docs) {
+ uint32_t count = 1 + rng() % 3;
+ if (style >= 1 && rng() % 5 == 0) {
+ count = 0;
+ } else if (style == 2 && rng() % 50 == 0) {
+ count = 300 + rng() % 900;
+ }
+ uint32_t position = rng() % 50;
+ for (uint32_t i = 0; i < count; ++i) {
+ doc.push_back(position);
+ position += 1 + rng() % 40;
+ }
+ want_shape.total_positions += count;
+ want_shape.max_frequency = std::max(want_shape.max_frequency,
count);
+ want_shape.has_zero_frequency |= count == 0;
+ }
+ std::vector<uint32_t> ordinals;
+ const uint32_t mode = rng() % 4;
+ for (uint32_t d = 0; d < doc_count; ++d) {
+ const bool run_edge = d % kFrqBaseUnit == 0 || d % kFrqBaseUnit ==
kFrqBaseUnit - 1;
+ const bool take = mode == 0 ? (rng() % 40 == 0)
+ : mode == 1 ? (rng() % 2 == 0)
+ : mode == 2 ? run_edge
+ : (d == 0 || d + 1 == doc_count);
+ if (take) {
+ ordinals.push_back(d);
+ }
+ }
+ SCOPED_TRACE("round=" + std::to_string(round) + " docs=" +
std::to_string(doc_count) +
+ " style=" + std::to_string(style) + " mode=" +
std::to_string(mode));
+ const std::vector<uint8_t> encoded = BuildProfileFrame(docs,
PrxCodec::kPfor);
+ std::vector<uint32_t> expected_flat;
+ std::vector<uint32_t> expected_offsets;
+ ExpectedSelectiveCsr(docs, ordinals, &expected_flat,
&expected_offsets);
+ std::vector<uint32_t> flat;
+ std::vector<uint32_t> offsets;
+ PrxDecodedShape shape;
+ PrxDecodeContext context {.shape = &shape};
+ ByteSource source((Slice(encoded)));
+ ASSERT_TRUE(
+ read_prx_window_csr_selective(&source, ordinals, &flat,
&offsets, &context).ok());
+ EXPECT_EQ(flat, expected_flat);
+ EXPECT_EQ(offsets, expected_offsets);
+ EXPECT_EQ(shape.total_docs, want_shape.total_docs);
+ EXPECT_EQ(shape.total_positions, want_shape.total_positions);
+ EXPECT_EQ(shape.max_frequency, want_shape.max_frequency);
+ EXPECT_EQ(shape.has_zero_frequency, want_shape.has_zero_frequency);
+ }
+}
+
+// A run is checked against the cap as a whole, and its sum is kept in 64
bits: these counts add up
+// to 2^38, which is 0 in 32 bits and would match the declared total.
+TEST(SniiPrxPod, SelectivePforRejectsCountsAboveTheCap) {
+ const std::vector<uint32_t> freqs(kFrqBaseUnit, 1U << 30);
+ const std::vector<uint8_t> encoded = MakePforWindow(kFrqBaseUnit, 0,
freqs, {});
+ const std::vector<uint32_t> ordinals = {3};
+ std::vector<uint32_t> flat;
+ std::vector<uint32_t> offsets;
+ ByteSource source((Slice(encoded)));
+ const Status status = read_prx_window_csr_selective(&source, ordinals,
&flat, &offsets);
+ EXPECT_TRUE(status.is<doris::ErrorCode::INVERTED_INDEX_FILE_CORRUPTED>())
<< status;
+ EXPECT_NE(status.to_string().find("pos_count sum exceeds sane cap"),
std::string::npos)
+ << status;
+}
+
// Multiple docs, positions ascending within each doc, no shared baseline
across
// docs.
TEST(SniiPrxPod, MultiDocRoundTrip) {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
