Skip to content

Commit a49a9b2

Browse files
committed
[fix](be) Prevent score leakage across Boolean search branches
1 parent 379f648 commit a49a9b2

6 files changed

Lines changed: 430 additions & 3 deletions

File tree

‎be/src/exprs/vcompound_pred.h‎

Lines changed: 31 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020

2121
#include <algorithm>
2222
#include <cstdint>
23+
#include <memory>
2324

2425
#include "common/logging.h"
2526
#include "common/status.h"
@@ -29,7 +30,9 @@
2930
#include "exprs/vectorized_fn_call.h"
3031
#include "exprs/vexpr_context.h"
3132
#include "exprs/vexpr_fwd.h"
33+
#include "storage/compaction/collection_similarity.h"
3234
#include "storage/index/zone_map/zonemap_eval_context.h"
35+
#include "util/defer_op.h"
3336
#include "util/simd/bits.h"
3437

3538
namespace doris {
@@ -270,9 +273,24 @@ class VCompoundPred : public VectorizedFnCall {
270273
}
271274
}
272275

276+
// NOLINTNEXTLINE(readability-function-size,readability-function-cognitive-complexity): Keep each operator's bitmap and score updates together.
273277
Status evaluate_inverted_index(VExprContext* context, uint32_t segment_num_rows) override {
274278
segment_v2::InvertedIndexResultBitmap res;
275279
bool all_pass = true;
280+
auto index_context = context->get_index_context();
281+
auto query_context = index_context->get_index_query_context();
282+
auto parent_similarity =
283+
query_context != nullptr ? query_context->collection_similarity : nullptr;
284+
CollectionSimilarityPtr branch_similarity;
285+
if (parent_similarity != nullptr) {
286+
branch_similarity = std::make_shared<CollectionSimilarity>();
287+
query_context->collection_similarity = branch_similarity;
288+
}
289+
Defer restore_similarity {[&]() {
290+
if (branch_similarity != nullptr) {
291+
query_context->collection_similarity = parent_similarity;
292+
}
293+
}};
276294

277295
switch (_op) {
278296
case TExprOpcode::COMPOUND_OR: {
@@ -296,7 +314,7 @@ class VCompoundPred : public VectorizedFnCall {
296314
} else {
297315
res |= *index_result;
298316
}
299-
if (inverted_index_context->get_score_runtime() == nullptr) {
317+
if (branch_similarity == nullptr) {
300318
if (res.get_data_bitmap()->cardinality() == segment_num_rows) {
301319
break; // Early exit if result is full
302320
}
@@ -362,8 +380,19 @@ class VCompoundPred : public VectorizedFnCall {
362380
"Compound operator must be AND, OR, or NOT to execute with inverted index.");
363381
}
364382

383+
if (branch_similarity != nullptr && _op != TExprOpcode::COMPOUND_NOT) {
384+
auto scores = branch_similarity->release_scores();
385+
if (!scores.empty() && (!all_pass || res.is_empty())) {
386+
return Status::Error<ErrorCode::INVERTED_INDEX_NOT_SUPPORTED>(
387+
"Cannot score a compound predicate with incomplete index evaluation");
388+
}
389+
if (all_pass && !res.is_empty()) {
390+
DORIS_CHECK(res.get_data_bitmap() != nullptr);
391+
parent_similarity->merge_scores(scores, *res.get_data_bitmap());
392+
}
393+
}
365394
if (all_pass && !res.is_empty()) {
366-
context->get_index_context()->set_index_result_for_expr(this, res);
395+
index_context->set_index_result_for_expr(this, res);
367396
}
368397
return Status::OK();
369398
}

‎be/src/storage/compaction/collection_similarity.cpp‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,15 @@ void CollectionSimilarity::collect(segment_v2::rowid_t row_id, float score) {
2626
_bm25_scores[row_id] += score;
2727
}
2828

29+
void CollectionSimilarity::merge_scores(const ScoreMap& scores,
30+
const roaring::Roaring& matched_rows) {
31+
for (const auto& [row_id, score] : scores) {
32+
if (matched_rows.contains(row_id)) {
33+
collect(row_id, score);
34+
}
35+
}
36+
}
37+
2938
void CollectionSimilarity::get_bm25_scores(roaring::Roaring* row_bitmap,
3039
IColumn::MutablePtr& scores,
3140
std::unique_ptr<std::vector<uint64_t>>& row_ids,
@@ -165,4 +174,4 @@ void CollectionSimilarity::find_top_k_scores(const roaring::Roaring* row_bitmap,
165174
}
166175
}
167176

168-
} // namespace doris
177+
} // namespace doris

‎be/src/storage/compaction/collection_similarity.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,8 @@ class CollectionSimilarity {
4949

5050
void collect(segment_v2::rowid_t row_id, float score);
5151

52+
void merge_scores(const ScoreMap& scores, const roaring::Roaring& matched_rows);
53+
5254
// Hands the collected scores over to the caller and leaves this instance empty.
5355
// A reader that computes per-document scores inside its own query() cannot return them
5456
// through the query API, so it publishes them into a throwaway CollectionSimilarity that the
Lines changed: 222 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,222 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#include <gtest/gtest.h>
19+
20+
#include <cstdint>
21+
#include <initializer_list>
22+
#include <memory>
23+
#include <string>
24+
#include <unordered_map>
25+
#include <vector>
26+
27+
#include "core/data_type/primitive_type.h"
28+
#include "exprs/score_runtime.h"
29+
#include "exprs/vcompound_pred.h"
30+
#include "exprs/vexpr_context.h"
31+
#include "storage/compaction/collection_similarity.h"
32+
#include "storage/index/index_iterator.h"
33+
#include "storage/index/index_query_context.h"
34+
35+
namespace doris {
36+
namespace {
37+
38+
class ScoredBitmapExpr final : public VExpr {
39+
public:
40+
ScoredBitmapExpr(std::initializer_list<uint32_t> rows, float score) : _score(score) {
41+
set_node_type(TExprNodeType::MATCH_PRED);
42+
for (uint32_t row : rows) {
43+
_rows.add(row);
44+
}
45+
}
46+
47+
const std::string& expr_name() const override {
48+
static const std::string name = "ScoredBitmapExpr";
49+
return name;
50+
}
51+
52+
Status execute(VExprContext*, Block*, int*) const override { return Status::OK(); }
53+
54+
Status execute_column_impl(VExprContext*, const Block*, const Selector*, size_t,
55+
ColumnPtr&) const override {
56+
return Status::OK();
57+
}
58+
59+
Status evaluate_inverted_index(VExprContext* context, uint32_t) override {
60+
auto index_context = context->get_index_context();
61+
auto query_context = index_context->get_index_query_context();
62+
for (uint32_t row : _rows) {
63+
query_context->collection_similarity->collect(row, _score);
64+
}
65+
index_context->set_index_result_for_expr(
66+
this,
67+
segment_v2::InvertedIndexResultBitmap(std::make_shared<roaring::Roaring>(_rows),
68+
std::make_shared<roaring::Roaring>()));
69+
return Status::OK();
70+
}
71+
72+
private:
73+
roaring::Roaring _rows;
74+
float _score;
75+
};
76+
77+
class UnindexedExpr final : public VExpr {
78+
public:
79+
const std::string& expr_name() const override {
80+
static const std::string name = "UnindexedExpr";
81+
return name;
82+
}
83+
84+
Status execute(VExprContext*, Block*, int*) const override { return Status::OK(); }
85+
86+
Status execute_column_impl(VExprContext*, const Block*, const Selector*, size_t,
87+
ColumnPtr&) const override {
88+
return Status::OK();
89+
}
90+
91+
Status evaluate_inverted_index(VExprContext*, uint32_t) override { return Status::OK(); }
92+
};
93+
94+
std::shared_ptr<VCompoundPred> make_compound(TExprOpcode::type op, VExprSPtr left,
95+
VExprSPtr right) {
96+
TExprNode node;
97+
node.__set_type(create_type_desc(PrimitiveType::TYPE_BOOLEAN));
98+
node.__set_node_type(TExprNodeType::COMPOUND_PRED);
99+
node.__set_opcode(op);
100+
node.__set_num_children(2);
101+
node.__set_is_nullable(false);
102+
auto expr = VCompoundPred::create_shared(node);
103+
expr->add_child(left);
104+
expr->add_child(right);
105+
return expr;
106+
}
107+
108+
std::shared_ptr<VCompoundPred> make_not(VExprSPtr child) {
109+
TExprNode node;
110+
node.__set_type(create_type_desc(PrimitiveType::TYPE_BOOLEAN));
111+
node.__set_node_type(TExprNodeType::COMPOUND_PRED);
112+
node.__set_opcode(TExprOpcode::COMPOUND_NOT);
113+
node.__set_num_children(1);
114+
node.__set_is_nullable(false);
115+
auto expr = VCompoundPred::create_shared(node);
116+
expr->add_child(child);
117+
return expr;
118+
}
119+
120+
TEST(VCompoundPredScoreTest, FailedAndBranchDoesNotContributeToOrScore) {
121+
auto first = make_compound(
122+
TExprOpcode::COMPOUND_AND,
123+
std::make_shared<ScoredBitmapExpr>(std::initializer_list<uint32_t> {1, 2, 4}, 1.0F),
124+
std::make_shared<ScoredBitmapExpr>(std::initializer_list<uint32_t> {1, 2, 5}, 2.0F));
125+
auto second = make_compound(
126+
TExprOpcode::COMPOUND_AND,
127+
std::make_shared<ScoredBitmapExpr>(std::initializer_list<uint32_t> {1, 2, 3, 4, 5},
128+
3.0F),
129+
std::make_shared<ScoredBitmapExpr>(std::initializer_list<uint32_t> {1, 3, 4, 5}, 4.0F));
130+
auto root = make_compound(TExprOpcode::COMPOUND_OR, first, second);
131+
132+
std::vector<std::unique_ptr<segment_v2::IndexIterator>> iterators;
133+
std::vector<IndexFieldNameAndTypePair> storage_types;
134+
std::unordered_map<ColumnId, std::unordered_map<const VExpr*, bool>> status_map;
135+
segment_v2::ColumnIteratorOptions iterator_options;
136+
auto score_runtime = std::make_shared<ScoreRuntime>(nullptr, false, 0);
137+
auto index_context = std::make_shared<IndexExecContext>(
138+
iterators, storage_types, status_map, score_runtime, nullptr, iterator_options);
139+
auto query_context = std::make_shared<segment_v2::IndexQueryContext>();
140+
query_context->collection_similarity = std::make_shared<CollectionSimilarity>();
141+
auto root_similarity = query_context->collection_similarity;
142+
index_context->set_index_query_context(query_context);
143+
auto expr_context = VExprContext::create_shared(root);
144+
expr_context->set_index_context(index_context);
145+
146+
ASSERT_TRUE(root->evaluate_inverted_index(expr_context.get(), 6).ok());
147+
const auto* result = index_context->get_index_result_for_expr(root.get());
148+
ASSERT_NE(result, nullptr);
149+
EXPECT_EQ(result->get_data_bitmap()->cardinality(), 5);
150+
EXPECT_EQ(query_context->collection_similarity, root_similarity);
151+
152+
auto scores = root_similarity->release_scores();
153+
ASSERT_EQ(scores.size(), 5);
154+
EXPECT_FLOAT_EQ(scores.at(1), 10.0F);
155+
EXPECT_FLOAT_EQ(scores.at(2), 3.0F);
156+
EXPECT_FLOAT_EQ(scores.at(3), 7.0F);
157+
EXPECT_FLOAT_EQ(scores.at(4), 7.0F);
158+
EXPECT_FLOAT_EQ(scores.at(5), 7.0F);
159+
}
160+
161+
TEST(VCompoundPredScoreTest, NotBranchDoesNotContributeToOrScore) {
162+
auto negative = make_not(
163+
std::make_shared<ScoredBitmapExpr>(std::initializer_list<uint32_t> {1, 2}, 1.0F));
164+
auto positive =
165+
std::make_shared<ScoredBitmapExpr>(std::initializer_list<uint32_t> {1, 3}, 5.0F);
166+
auto root = make_compound(TExprOpcode::COMPOUND_OR, negative, positive);
167+
168+
std::vector<std::unique_ptr<segment_v2::IndexIterator>> iterators;
169+
std::vector<IndexFieldNameAndTypePair> storage_types;
170+
std::unordered_map<ColumnId, std::unordered_map<const VExpr*, bool>> status_map;
171+
segment_v2::ColumnIteratorOptions iterator_options;
172+
auto score_runtime = std::make_shared<ScoreRuntime>(nullptr, false, 0);
173+
auto index_context = std::make_shared<IndexExecContext>(
174+
iterators, storage_types, status_map, score_runtime, nullptr, iterator_options);
175+
auto query_context = std::make_shared<segment_v2::IndexQueryContext>();
176+
query_context->collection_similarity = std::make_shared<CollectionSimilarity>();
177+
index_context->set_index_query_context(query_context);
178+
auto expr_context = VExprContext::create_shared(root);
179+
expr_context->set_index_context(index_context);
180+
181+
ASSERT_TRUE(root->evaluate_inverted_index(expr_context.get(), 4).ok());
182+
const auto* result = index_context->get_index_result_for_expr(root.get());
183+
ASSERT_NE(result, nullptr);
184+
EXPECT_EQ(result->get_data_bitmap()->cardinality(), 3);
185+
EXPECT_TRUE(result->get_data_bitmap()->contains(0));
186+
EXPECT_TRUE(result->get_data_bitmap()->contains(1));
187+
EXPECT_TRUE(result->get_data_bitmap()->contains(3));
188+
189+
auto scores = query_context->collection_similarity->release_scores();
190+
ASSERT_EQ(scores.size(), 2);
191+
EXPECT_FLOAT_EQ(scores.at(1), 5.0F);
192+
EXPECT_FLOAT_EQ(scores.at(3), 5.0F);
193+
}
194+
195+
TEST(VCompoundPredScoreTest, IncompleteScoredBranchReturnsErrorWithoutPublishingScores) {
196+
auto root = make_compound(
197+
TExprOpcode::COMPOUND_AND,
198+
std::make_shared<ScoredBitmapExpr>(std::initializer_list<uint32_t> {1}, 1.0F),
199+
std::make_shared<UnindexedExpr>());
200+
201+
std::vector<std::unique_ptr<segment_v2::IndexIterator>> iterators;
202+
std::vector<IndexFieldNameAndTypePair> storage_types;
203+
std::unordered_map<ColumnId, std::unordered_map<const VExpr*, bool>> status_map;
204+
segment_v2::ColumnIteratorOptions iterator_options;
205+
auto score_runtime = std::make_shared<ScoreRuntime>(nullptr, false, 0);
206+
auto index_context = std::make_shared<IndexExecContext>(
207+
iterators, storage_types, status_map, score_runtime, nullptr, iterator_options);
208+
auto query_context = std::make_shared<segment_v2::IndexQueryContext>();
209+
query_context->collection_similarity = std::make_shared<CollectionSimilarity>();
210+
auto parent_similarity = query_context->collection_similarity;
211+
index_context->set_index_query_context(query_context);
212+
auto expr_context = VExprContext::create_shared(root);
213+
expr_context->set_index_context(index_context);
214+
215+
auto status = root->evaluate_inverted_index(expr_context.get(), 2);
216+
EXPECT_EQ(status.code(), ErrorCode::INVERTED_INDEX_NOT_SUPPORTED);
217+
EXPECT_EQ(query_context->collection_similarity, parent_similarity);
218+
EXPECT_TRUE(parent_similarity->release_scores().empty());
219+
}
220+
221+
} // namespace
222+
} // namespace doris
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
-- This file is automatically generated. You should know what you did if you want to edit this
2+
-- !search --
3+
1 1.3714
4+
10 1.2833
5+
2 0.8781
6+
4 0.4932
7+
5 0.4932
8+
6 1.5112
9+
7 0.4932
10+
9 1.5553
11+
12+
-- !match --
13+
1 1.3714
14+
10 1.2833
15+
2 0.8781
16+
4 0.4932
17+
5 0.4932
18+
6 1.5112
19+
7 0.4932
20+
9 1.5553
21+
22+
-- !match_warm --
23+
1 1.3714
24+
10 1.2833
25+
2 0.8781
26+
4 0.4932
27+
5 0.4932
28+
6 1.5112
29+
7 0.4932
30+
9 1.5553
31+
32+
-- !failed_and --
33+
1 0.4932
34+
10 0.4052
35+
4 0.4932
36+
5 0.4932
37+
6 0.4932
38+
7 0.4932
39+
9 0.4932
40+
41+
-- !failed_and_reversed --
42+
1 0.4932
43+
10 0.4052
44+
4 0.4932
45+
5 0.4932
46+
6 0.4932
47+
7 0.4932
48+
9 0.4932
49+
50+
-- !not_branch --
51+
1 0.4932
52+
10 0.4052
53+
3 0
54+
4 0.4932
55+
5 0.4932
56+
6 0.4932
57+
7 0.4932
58+
8 0
59+
9 0.4932
60+

0 commit comments

Comments
 (0)