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 1db4b1d3050 [fix](be) Validate SNII BKD splits against global bounds
(#66864)
1db4b1d3050 is described below
commit 1db4b1d3050fa85d825567ca8f82193118277c18
Author: Jack <[email protected]>
AuthorDate: Wed Aug 19 09:38:33 2026 +0800
[fix](be) Validate SNII BKD splits against global bounds (#66864)
### What problem does this PR solve?
Issue Number: None
Related PR: #66052
Problem Summary:
A CRC-valid SNII BKD index whose split catalogue was ordered but outside
its persisted global bounds could open successfully and silently route
queries to the wrong leaf. The issue reproduces with values 0 through 19
split into two leaves: changing the persisted split from 10 to 30 makes
a point lookup for 15 inspect leaf 0 while the matching point remains in
leaf 1.
This PR validates the complete non-decreasing `min_value <=
split_values... <= max_value` chain when opening the index and asserts
the same invariant when encoding. Equal adjacent values and splits equal
to either inclusive global bound remain valid.
---
be/src/storage/index/snii/bkd/bkd_index_block.cpp | 41 +++++++++----------
be/src/storage/index/snii/bkd/bkd_index_block.h | 15 ++++---
.../storage/index/snii/bkd/bkd_corruption_test.cpp | 46 ++++++++++++++++++++++
.../index/snii/bkd/bkd_index_block_test.cpp | 44 +++++++++++++++++++++
4 files changed, 118 insertions(+), 28 deletions(-)
diff --git a/be/src/storage/index/snii/bkd/bkd_index_block.cpp
b/be/src/storage/index/snii/bkd/bkd_index_block.cpp
index 40735c8b363..a4157201574 100644
--- a/be/src/storage/index/snii/bkd/bkd_index_block.cpp
+++ b/be/src/storage/index/snii/bkd/bkd_index_block.cpp
@@ -140,20 +140,21 @@ Status decode_header(ByteSource* src, BkdIndexHeader*
header) {
return Status::OK();
}
-// Non-decreasing rather than strictly increasing: a value spanning several
leaves
-// makes consecutive leaves start at the same value. Comparison is unsigned
-// byte-wise from offset 0 (INV-1), i.e. plain memcmp over the sortable bytes.
-// An unordered array would silently route the binary search to the wrong leaf
--
-// wrong results with no error -- so it must never survive open.
-Status validate_split_order(Slice splits, size_t bytes_per_dim, uint32_t
leaf_count) {
- for (uint32_t i = 1; i + 1 < leaf_count; ++i) {
- const uint8_t* previous = splits.data() + (i - 1) * bytes_per_dim;
+// The whole routing catalogue is one non-decreasing chain. Equality is legal:
a
+// value spanning several leaves makes consecutive leaves start at that value,
+// including at either global bound. Comparison is unsigned byte-wise from
offset
+// 0 (INV-1), i.e. plain memcmp over the sortable bytes.
+bool value_order_is_valid(Slice min_value, Slice max_value, Slice splits,
size_t bytes_per_dim,
+ uint32_t leaf_count) {
+ const uint8_t* previous = min_value.data();
+ for (uint32_t i = 0; i + 1 < leaf_count; ++i) {
const uint8_t* current = splits.data() + i * bytes_per_dim;
if (std::memcmp(previous, current, bytes_per_dim) > 0) {
- return corrupted("split_values are not in ascending order");
+ return false;
}
+ previous = current;
}
- return Status::OK();
+ return std::memcmp(previous, max_value.data(), bytes_per_dim) <= 0;
}
// Leaf directory: delta-varint64 offsets, then varint32 counts (design 5.1).
@@ -245,20 +246,12 @@ void encode_bkd_index_block(const BkdIndexHeader& header,
Slice min_value, Slice
DORIS_CHECK_EQ(min_value.size(), bytes_per_dim);
DORIS_CHECK_EQ(max_value.size(), bytes_per_dim);
DORIS_CHECK_EQ(split_values.size(), (header.leaf_count - 1) *
bytes_per_dim);
+ DORIS_CHECK(value_order_is_valid(min_value, max_value, split_values,
bytes_per_dim,
+ header.leaf_count));
payload.put_bytes(min_value);
payload.put_bytes(max_value);
payload.put_bytes(split_values);
- // The reader binary-searches this array and indexes the leaf directory
- // without re-checking, so both orderings are asserted where they are
- // produced. Comparison is unsigned byte-wise from offset 0 (INV-1),
which
- // is exactly memcmp over the sortable bytes.
- for (uint32_t i = 1; i + 1 < header.leaf_count; ++i) {
- DORIS_CHECK_LE(std::memcmp(split_values.data() + (i - 1) *
bytes_per_dim,
- split_values.data() + i *
bytes_per_dim, bytes_per_dim),
- 0);
- }
-
uint64_t previous_offset = 0;
uint64_t total_points = 0;
for (size_t i = 0; i < leaves.size(); ++i) {
@@ -332,8 +325,12 @@ Status BkdIndexBlockReader::decode_payload(Slice payload,
uint64_t data_length)
Slice splits;
RETURN_IF_ERROR(src.get_bytes(static_cast<size_t>((leaf_count - 1) *
bytes_per_dim), &splits));
- RETURN_IF_ERROR(
- validate_split_order(splits, static_cast<size_t>(bytes_per_dim),
header.leaf_count));
+ const auto value_width = static_cast<size_t>(bytes_per_dim);
+ const Slice min_value(bounds.data(), value_width);
+ const Slice max_value(bounds.data() + value_width, value_width);
+ if (!value_order_is_valid(min_value, max_value, splits, value_width,
header.leaf_count)) {
+ return corrupted("global bounds and split_values are not in ascending
order");
+ }
std::vector<LeafRef> leaves;
RETURN_IF_ERROR(decode_leaf_directory(&src, header, data_length, &leaves));
diff --git a/be/src/storage/index/snii/bkd/bkd_index_block.h
b/be/src/storage/index/snii/bkd/bkd_index_block.h
index d4c82fd0166..679676c956b 100644
--- a/be/src/storage/index/snii/bkd/bkd_index_block.h
+++ b/be/src/storage/index/snii/bkd/bkd_index_block.h
@@ -46,7 +46,7 @@
// --- present only when leaf_count > 0 ---
// min_value bytes[bytes_per_dim]
// max_value bytes[bytes_per_dim]
-// split_values bytes[(leaf_count - 1) * bytes_per_dim] ascending,
fixed width
+// split_values bytes[(leaf_count - 1) * bytes_per_dim] ascending
inside min/max
// leaf_offsets delta-varint64[leaf_count] strictly
increasing
// leaf_counts varint32[leaf_count]
//
@@ -71,7 +71,8 @@ namespace doris::snii::bkd {
// through BkdIndexBlockReader::open.
//
// min_value / max_value : exactly bytes_per_dim bytes, empty iff leaf_count
== 0
-// split_values : (leaf_count - 1) * bytes_per_dim bytes,
non-decreasing
+// split_values : (leaf_count - 1) * bytes_per_dim bytes, with
+// min_value <= splits... <= max_value
// leaves : leaf_count entries, offsets strictly increasing,
// counts summing to header.point_count
void encode_bkd_index_block(const BkdIndexHeader& header, Slice min_value,
Slice max_value,
@@ -100,9 +101,10 @@ public:
// capability boundary, so the caller reports "index unavailable" instead
of a
// damaged segment. Every other rejection (bad magic, unknown field_type,
// bytes_per_dim disagreeing with field_type, array lengths disagreeing
with
- // leaf_count, unordered split values, non-increasing or out-of-range leaf
- // offsets, leaf counts not summing to point_count, trailing bytes, crc
- // mismatch, truncation) -> INVERTED_INDEX_FILE_CORRUPTED.
+ // leaf_count, min_value above max_value, split values outside the global
+ // bounds or unordered, non-increasing or out-of-range leaf offsets, leaf
+ // counts not summing to point_count, trailing bytes, crc mismatch,
+ // truncation) -> INVERTED_INDEX_FILE_CORRUPTED.
static Status open(Slice framed, uint64_t data_length,
BkdIndexBlockReader* out);
const BkdIndexHeader& header() const { return header_; }
@@ -152,7 +154,8 @@ private:
BkdIndexHeader header_;
// min_value followed by max_value, one allocation. Empty for an empty
index.
std::vector<uint8_t> bounds_;
- // (leaf_count - 1) * bytes_per_dim bytes, non-decreasing, fixed width.
+ // (leaf_count - 1) * bytes_per_dim bytes, non-decreasing inside the
inclusive
+ // global bounds, fixed width.
std::vector<uint8_t> split_values_;
std::vector<LeafRef> leaves_;
};
diff --git a/be/test/storage/index/snii/bkd/bkd_corruption_test.cpp
b/be/test/storage/index/snii/bkd/bkd_corruption_test.cpp
index e6ef8160750..55ef5d07ec9 100644
--- a/be/test/storage/index/snii/bkd/bkd_corruption_test.cpp
+++ b/be/test/storage/index/snii/bkd/bkd_corruption_test.cpp
@@ -744,6 +744,52 @@ TEST(BkdCorruptionTest,
AbsurdPointsPerLeafIsRejectedAtOpen) {
}
}
+TEST(BkdCorruptionTest,
SelfConsistentSplitAboveGlobalMaximumIsRejectedBeforeQueryRouting) {
+ std::vector<Point> points;
+ for (uint32_t i = 0; i < 20; ++i) {
+ points.push_back(Point {static_cast<int64_t>(i), i});
+ }
+ Image original;
+ ASSERT_TRUE(build_image(points, 10, &original).ok());
+ const std::vector<uint8_t> data_bytes(
+ original.bytes.begin() + static_cast<long>(original.data_begin),
+ original.bytes.begin() + static_cast<long>(original.data_begin +
original.data_size));
+ IndexPayload payload;
+ ASSERT_TRUE(parse_payload(payload_of(original.index_bytes()), &payload));
+ ASSERT_EQ(payload.leaf_count, 2U);
+
+ ByteSource tail {Slice(payload.tail)};
+ Slice min_value;
+ Slice max_value;
+ Slice old_split;
+ Slice directory;
+ ASSERT_TRUE(tail.get_bytes(kBytesPerDim, &min_value).ok());
+ ASSERT_TRUE(tail.get_bytes(kBytesPerDim, &max_value).ok());
+ ASSERT_TRUE(tail.get_bytes(kBytesPerDim, &old_split).ok());
+ ASSERT_TRUE(tail.get_bytes(tail.remaining(), &directory).ok());
+ ASSERT_EQ(std::memcmp(min_value.data(), sortable_bigint(0).data(),
kBytesPerDim), 0);
+ ASSERT_EQ(std::memcmp(max_value.data(), sortable_bigint(19).data(),
kBytesPerDim), 0);
+ ASSERT_EQ(std::memcmp(old_split.data(), sortable_bigint(10).data(),
kBytesPerDim), 0);
+
+ const std::vector<uint8_t> malformed_split = sortable_bigint(30);
+ ByteSink rebuilt;
+ rebuilt.put_bytes(min_value);
+ rebuilt.put_bytes(max_value);
+ rebuilt.put_bytes(Slice(malformed_split));
+ rebuilt.put_bytes(directory);
+ payload.tail = rebuilt.take();
+ const Image damaged = assemble(reframe(encode_payload(payload)),
data_bytes);
+
+ // Before the open-time invariant was enforced, this CRC-valid image opened
+ // successfully and a point lookup for 15 silently returned no rows: split
30
+ // routed the query to leaf 0 while doc 15 remained in leaf 1.
+ MemoryFileReader file(damaged.bytes);
+ std::unique_ptr<BkdReader> reader;
+ const Status status = BkdReader::open(&file, damaged.sections, &reader);
+ EXPECT_TRUE(is_rejected(status, "split above global maximum"));
+ EXPECT_EQ(reader, nullptr);
+}
+
TEST(BkdCorruptionTest, InflatedLeafBlockLengthFieldsAreRejectedAtQueryTime) {
// A leaf block starts with { point_count varint32, value_mode u8,
// common_prefix_len varint32, ... } and ends with { docid_block_offset
diff --git a/be/test/storage/index/snii/bkd/bkd_index_block_test.cpp
b/be/test/storage/index/snii/bkd/bkd_index_block_test.cpp
index 106fbf53ed5..1c7ca52c16e 100644
--- a/be/test/storage/index/snii/bkd/bkd_index_block_test.cpp
+++ b/be/test/storage/index/snii/bkd/bkd_index_block_test.cpp
@@ -544,6 +544,50 @@ TEST(SniiBkdIndexBlock,
SplitValuesNotAscendingIsCorrupted) {
EXPECT_TRUE(IsCorrupted(open_raw(raw, &reader)));
}
+TEST(SniiBkdIndexBlock, GlobalMinimumAboveMaximumIsCorrupted) {
+ RawIndexBlock raw = valid_three_leaf_block();
+ raw.point_count = 4;
+ raw.doc_count = 4;
+ raw.leaf_count = 1;
+ raw.min_value = sortable_bigint(20);
+ raw.max_value = sortable_bigint(19);
+ raw.split_values.clear();
+ raw.leaf_offset_deltas = {0};
+ raw.leaf_counts = {4};
+
+ BkdIndexBlockReader reader;
+ EXPECT_TRUE(IsCorrupted(open_raw(raw, &reader)));
+}
+
+TEST(SniiBkdIndexBlock, SplitValueBelowGlobalMinimumIsCorrupted) {
+ RawIndexBlock raw = valid_three_leaf_block();
+ raw.split_values.clear();
+ append_bytes(&raw.split_values, sortable_bigint(-6));
+ append_bytes(&raw.split_values, sortable_bigint(200));
+
+ BkdIndexBlockReader reader;
+ EXPECT_TRUE(IsCorrupted(open_raw(raw, &reader)));
+}
+
+TEST(SniiBkdIndexBlock, SplitValueAboveGlobalMaximumIsCorrupted) {
+ RawIndexBlock raw = valid_three_leaf_block();
+ raw.split_values.clear();
+ append_bytes(&raw.split_values, sortable_bigint(100));
+ append_bytes(&raw.split_values, sortable_bigint(301));
+
+ BkdIndexBlockReader reader;
+ EXPECT_TRUE(IsCorrupted(open_raw(raw, &reader)));
+}
+
+TEST(SniiBkdIndexBlock, SplitValuesMayEqualInclusiveGlobalBounds) {
+ RawIndexBlock raw = valid_three_leaf_block();
+ raw.min_value = sortable_bigint(100);
+ raw.max_value = sortable_bigint(200);
+
+ BkdIndexBlockReader reader;
+ EXPECT_TRUE(open_raw(raw, &reader).ok());
+}
+
// Ordering is UNSIGNED byte comparison, MSB first (INV-1). 0x80.. sorts above
// 0x7F.. even though the same bytes read as a signed value would not.
TEST(SniiBkdIndexBlock, SplitValueOrderingIsUnsignedByteWise) {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
