Skip to content

Commit 9a48f81

Browse files
authored
[fix](be) Fall back from expensive Hyperscan bounded repeats (apache#66788)
Problem Summary: Hyperscan can spend excessive time and memory compiling bounded repetitions with large limits. Doris now detects regex quantifiers above 50 before every direct Hyperscan compiler entry point. LIKE and REGEXP paths with a compatible fallback use RE2; compiler paths without a fallback reject the pattern before Hyperscan compilation. The guard follows ClickHouse SlowWithHyperscanChecker and searches the raw regular expression. This intentionally uses the same conservative best-effort classification instead of maintaining a partial Hyperscan grammar parser. The new `enable_hyperscan_fallback` session variable controls strictness. It defaults to `true`, preserving fallback behavior. When set to `false`, Doris returns the interception or Hyperscan compilation error instead of falling back. Normal query execution and request-scoped synchronous Stream Load propagate this option through `TQueryOptions`. Asynchronous Broker Load and Routine Load session inheritance are outside this PR scope and retain their historical option defaults. ### Release note Add `enable_hyperscan_fallback`. It defaults to `true`; setting it to `false` returns an error when Hyperscan cannot compile or safely process the regular expression on supported request-scoped paths. ### Check List (For Author) - Test: - Targeted BE unit tests for LIKE/REGEXP, MATCH_REGEXP, multi-match, and inverted-index regexp v1/v2 - `DORIS_THIRDPARTY=$PWD/thirdparty FE_UT_PARALLEL=48 ./run-fe-ut.sh --run org.apache.doris.nereids.load.NereidsLoadScanProviderTest,org.apache.doris.qe.SessionVariablesTest` (25 passed) - `DORIS_THIRDPARTY=$PWD/thirdparty ./build.sh --fe -j 48` - BE clang-format and clang-tidy - Behavior changed: Yes. Expensive bounded repeats are intercepted before Hyperscan compilation, and request-scoped sessions may disable the RE2 fallback. The default remains fallback enabled. - Does this need documentation: No
1 parent 556d748 commit 9a48f81

16 files changed

Lines changed: 383 additions & 10 deletions

File tree

‎be/src/exprs/function/like.cpp‎

Lines changed: 39 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,6 @@
1919

2020
#include <fmt/format.h>
2121
#include <hs/hs_compile.h>
22-
#include <re2/stringpiece.h>
2322

2423
#include <cstddef>
2524
#include <ostream>
@@ -34,8 +33,10 @@
3433
#include "core/column/column_vector.h"
3534
#include "core/string_ref.h"
3635
#include "exprs/function/simple_function_factory.h"
36+
#include "util/hyperscan_util.h"
3737

3838
namespace doris {
39+
3940
// A regex to match any regex pattern is equivalent to a substring search.
4041
static const RE2 SUBSTRING_RE(R"((?:\.\*)*([^\.\^\{\[\(\|\)\]\}\+\*\?\$\\]*)(?:\.\*)*)");
4142

@@ -183,8 +184,9 @@ struct VectorEndsWithSearchState : public VectorPatternSearchState {
183184
}
184185
};
185186

186-
Status LikeSearchState::clone(LikeSearchState& cloned) {
187+
Status LikeSearchState::clone(LikeSearchState& cloned) const {
187188
cloned.set_search_string(search_string);
189+
cloned.enable_hyperscan_fallback = enable_hyperscan_fallback;
188190

189191
std::string re_pattern;
190192
FunctionLike::convert_like_pattern(this, pattern_str, &re_pattern);
@@ -452,7 +454,8 @@ Status FunctionLikeBase::regexp_fn(const LikeSearchState* state, const ColumnStr
452454

453455
hs_database_t* database = nullptr;
454456
hs_scratch_t* scratch = nullptr;
455-
if (hs_prepare(nullptr, re_pattern.c_str(), &database, &scratch).ok()) { // use hyperscan
457+
auto hs_status = hs_prepare(nullptr, re_pattern.c_str(), &database, &scratch);
458+
if (hs_status.ok()) { // use hyperscan
456459
auto sz = val.size();
457460
for (size_t i = 0; i < sz; i++) {
458461
const auto& str_ref = val.get_data_at(i);
@@ -467,6 +470,9 @@ Status FunctionLikeBase::regexp_fn(const LikeSearchState* state, const ColumnStr
467470
hs_free_scratch(scratch);
468471
hs_free_database(database);
469472
} else { // fallback to re2
473+
if (!state->enable_hyperscan_fallback) {
474+
return hs_status;
475+
}
470476
RE2::Options opts;
471477
opts.set_never_nl(false);
472478
opts.set_dot_nl(true);
@@ -487,8 +493,19 @@ Status FunctionLikeBase::regexp_fn(const LikeSearchState* state, const ColumnStr
487493
}
488494

489495
// hyperscan compile expression to database and allocate scratch space
496+
bool FunctionLikeBase::should_fallback_to_re2(std::string_view regexp) {
497+
return is_hyperscan_regexp_expensive(regexp);
498+
}
499+
490500
Status FunctionLikeBase::hs_prepare(FunctionContext* context, const char* expression,
491501
hs_database_t** database, hs_scratch_t** scratch) {
502+
if (should_fallback_to_re2(expression)) {
503+
*database = nullptr;
504+
*scratch = nullptr;
505+
// Callers either fall back to RE2 or return this status based on the session variable.
506+
return Status::RuntimeError<false>(HYPERSCAN_BOUNDED_REPEAT_ERROR);
507+
}
508+
492509
hs_compile_error_t* compile_err;
493510
auto res = hs_compile(expression, HS_FLAG_DOTALL | HS_FLAG_ALLOWEMPTY | HS_FLAG_UTF8,
494511
HS_MODE_BLOCK, nullptr, database, &compile_err);
@@ -497,7 +514,7 @@ Status FunctionLikeBase::hs_prepare(FunctionContext* context, const char* expres
497514
*database = nullptr;
498515
std::string error_message = compile_err->message;
499516
hs_free_compile_error(compile_err);
500-
// Do not call FunctionContext::set_error here, since we do not want to cancel the query here.
517+
// Callers either fall back to RE2 or return this status based on the session variable.
501518
return Status::RuntimeError<false>("hs_compile regex pattern error:" + error_message);
502519
}
503520
hs_free_compile_error(compile_err);
@@ -506,7 +523,7 @@ Status FunctionLikeBase::hs_prepare(FunctionContext* context, const char* expres
506523
hs_free_database(*database);
507524
*database = nullptr;
508525
*scratch = nullptr;
509-
// Do not call FunctionContext::set_error here, since we do not want to cancel the query here.
526+
// Callers either fall back to RE2 or return this status based on the session variable.
510527
return Status::RuntimeError<false>("hs_alloc_scratch allocate scratch space error");
511528
}
512529

@@ -942,12 +959,19 @@ Status FunctionLike::construct_like_const_state(FunctionContext* context, const
942959

943960
hs_database_t* database = nullptr;
944961
hs_scratch_t* scratch = nullptr;
945-
if (try_hyperscan && hs_prepare(context, re_pattern.c_str(), &database, &scratch).ok()) {
962+
Status hs_status;
963+
if (try_hyperscan) {
964+
hs_status = hs_prepare(context, re_pattern.c_str(), &database, &scratch);
965+
}
966+
if (try_hyperscan && hs_status.ok()) {
946967
// use hyperscan
947968
state->search_state.hs_database.reset(database);
948969
state->search_state.hs_scratch.reset(scratch);
949970
} else {
950971
// fallback to re2
972+
if (try_hyperscan && !state->search_state.enable_hyperscan_fallback) {
973+
return hs_status;
974+
}
951975
// reset hs_database to nullptr to indicate not use hyperscan
952976
state->search_state.hs_database.reset();
953977
state->search_state.hs_scratch.reset();
@@ -974,6 +998,8 @@ Status FunctionLike::open(FunctionContext* context, FunctionContext::FunctionSta
974998
}
975999
std::shared_ptr<LikeState> state = std::make_shared<LikeState>();
9761000
state->is_like_pattern = true;
1001+
state->search_state.enable_hyperscan_fallback =
1002+
context->state()->query_options().enable_hyperscan_fallback;
9771003
state->function = like_fn;
9781004
state->scalar_function = like_fn_scalar;
9791005
if (context->is_col_constant(2)) {
@@ -1004,6 +1030,8 @@ Status FunctionRegexpLike::open(FunctionContext* context,
10041030
std::shared_ptr<LikeState> state = std::make_shared<LikeState>();
10051031
context->set_function_state(scope, state);
10061032
state->is_like_pattern = false;
1033+
state->search_state.enable_hyperscan_fallback =
1034+
context->state()->query_options().enable_hyperscan_fallback;
10071035
state->function = regexp_fn;
10081036
state->scalar_function = regexp_fn_scalar;
10091037
if (context->is_col_constant(1)) {
@@ -1035,12 +1063,16 @@ Status FunctionRegexpLike::open(FunctionContext* context,
10351063
} else {
10361064
hs_database_t* database = nullptr;
10371065
hs_scratch_t* scratch = nullptr;
1038-
if (hs_prepare(context, pattern_str.c_str(), &database, &scratch).ok()) {
1066+
auto hs_status = hs_prepare(context, pattern_str.c_str(), &database, &scratch);
1067+
if (hs_status.ok()) {
10391068
// use hyperscan
10401069
state->search_state.hs_database.reset(database);
10411070
state->search_state.hs_scratch.reset(scratch);
10421071
} else {
10431072
// fallback to re2
1073+
if (!state->search_state.enable_hyperscan_fallback) {
1074+
return hs_status;
1075+
}
10441076
// reset hs_database to nullptr to indicate not use hyperscan
10451077
state->search_state.hs_database.reset();
10461078
state->search_state.hs_scratch.reset();

‎be/src/exprs/function/like.h‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@
2929
#include <functional>
3030
#include <memory>
3131
#include <string>
32+
#include <string_view>
3233

3334
#include "common/status.h"
3435
#include "core/block/column_numbers.h"
@@ -182,6 +183,8 @@ struct LikeSearchState {
182183

183184
std::string pattern_str;
184185

186+
bool enable_hyperscan_fallback = true;
187+
185188
/// Used for LIKE predicates if the pattern is a constant argument, and is either a
186189
/// constant string or has a constant string at the beginning or end of the pattern.
187190
/// This will be set in order to check for that pattern in the corresponding part of
@@ -226,7 +229,7 @@ struct LikeSearchState {
226229

227230
LikeSearchState() = default;
228231

229-
Status clone(LikeSearchState& cloned);
232+
Status clone(LikeSearchState& cloned) const;
230233

231234
void set_search_string(const std::string& search_string_arg) {
232235
search_string = search_string_arg;
@@ -292,6 +295,8 @@ class FunctionLikeBase : public IFunction {
292295
friend struct VectorEndsWithSearchState;
293296

294297
protected:
298+
static bool should_fallback_to_re2(std::string_view regexp);
299+
295300
Status vector_const(const ColumnString& values, const StringRef* pattern_val,
296301
ColumnUInt8::Container& result, const LikeFn& function,
297302
LikeSearchState* search_state) const;

‎be/src/exprs/function/match.cpp‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@
2525
#include "storage/index/index_reader_helper.h"
2626
#include "storage/index/inverted/analyzer/analyzer.h"
2727
#include "util/debug_points.h"
28+
#include "util/hyperscan_util.h"
2829

2930
namespace doris {
3031

@@ -506,6 +507,10 @@ Status FunctionMatchRegexp::execute_match(FunctionContext* context, const std::s
506507
hs_compile_error_t* compile_err = nullptr;
507508
hs_scratch_t* scratch = nullptr;
508509

510+
if (is_hyperscan_regexp_expensive(pattern)) {
511+
return Status::Error<ErrorCode::INDEX_INVALID_PARAMETERS>(HYPERSCAN_BOUNDED_REPEAT_ERROR);
512+
}
513+
509514
if (hs_compile(pattern.data(), HS_FLAG_DOTALL | HS_FLAG_ALLOWEMPTY | HS_FLAG_UTF8,
510515
HS_MODE_BLOCK, nullptr, &database, &compile_err) != HS_SUCCESS) {
511516
std::string err_message = "hyperscan compilation failed: ";

‎be/src/exprs/function/regexps.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,7 @@
3333

3434
#include "common/exception.h"
3535
#include "core/string_ref.h"
36+
#include "util/hyperscan_util.h"
3637

3738
namespace doris::multiregexps {
3839

@@ -144,6 +145,9 @@ Regexps constructRegexps(const std::vector<String>& str_patterns,
144145

145146
for (auto& pattern : patterns) {
146147
LOG(INFO) << "pattern: " << pattern << "\n";
148+
if (is_hyperscan_regexp_expensive(pattern)) {
149+
throw doris::Exception(Status::InvalidArgument(HYPERSCAN_BOUNDED_REPEAT_ERROR));
150+
}
147151
}
148152

149153
hs_error_t err;

‎be/src/storage/index/inverted/query/regexp_query.cpp‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@
2323

2424
#include "common/logging.h"
2525
#include "util/debug_points.h"
26+
#include "util/hyperscan_util.h"
2627

2728
namespace doris::segment_v2 {
2829

@@ -39,6 +40,9 @@ void RegexpQuery::add(const InvertedIndexQueryInfo& query_info) {
3940
}
4041

4142
const std::string& pattern = query_info.term_infos[0].get_single_term();
43+
if (is_hyperscan_regexp_expensive(pattern)) {
44+
throw Exception(ErrorCode::INVALID_ARGUMENT, HYPERSCAN_BOUNDED_REPEAT_ERROR);
45+
}
4246
auto prefix = get_regex_prefix(pattern);
4347

4448
hs_database_t* database = nullptr;

‎be/src/storage/index/inverted/query_v2/regexp_query/regexp_weight.cpp‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,7 @@
4141
#include "storage/index/inverted/query_v2/nullable_scorer.h"
4242
#include "storage/index/inverted/query_v2/segment_postings.h"
4343
#include "storage/index/inverted/util/string_helper.h"
44+
#include "util/hyperscan_util.h"
4445

4546
CL_NS_USE(index)
4647

@@ -70,6 +71,9 @@ ScorerPtr RegexpWeight::scorer(const QueryExecutionContext& context,
7071

7172
ScorerPtr RegexpWeight::regexp_scorer(const QueryExecutionContext& context,
7273
const std::string& binding_key) {
74+
if (is_hyperscan_regexp_expensive(_pattern)) {
75+
throw Exception(ErrorCode::INVALID_ARGUMENT, HYPERSCAN_BOUNDED_REPEAT_ERROR);
76+
}
7377
auto prefix = get_regex_prefix(_pattern);
7478

7579
hs_database_t* database = nullptr;

‎be/src/util/hyperscan_util.cpp‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
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 "util/hyperscan_util.h"
19+
20+
#include <re2/re2.h>
21+
#include <re2/stringpiece.h>
22+
23+
#include <charconv>
24+
25+
namespace doris {
26+
namespace {
27+
28+
bool is_larger_than_fifty(std::string_view str) {
29+
int number = 0;
30+
auto [_, error] = std::from_chars(str.data(), str.data() + str.size(), number);
31+
return error == std::errc() && number > 50;
32+
}
33+
34+
class SlowWithHyperscanChecker {
35+
public:
36+
SlowWithHyperscanChecker()
37+
: _searcher_one_repeat(R"(\{\s*([\d]+)\s*,?\s*})"),
38+
_searcher_two_repeats(R"(\{\s*([\d]+)\s*,\s*([\d]+)\s*\})") {}
39+
40+
bool is_slow(std::string_view regexp) const {
41+
return is_slow_one_repeat(regexp) || is_slow_two_repeats(regexp);
42+
}
43+
44+
private:
45+
bool is_slow_one_repeat(std::string_view regexp) const {
46+
re2::StringPiece haystack(regexp.data(), regexp.size());
47+
re2::StringPiece matches[2];
48+
size_t start_pos = 0;
49+
while (start_pos < haystack.size()) {
50+
if (!_searcher_one_repeat.Match(haystack, start_pos, haystack.size(),
51+
re2::RE2::Anchor::UNANCHORED, matches, 2)) {
52+
break;
53+
}
54+
55+
start_pos = matches[0].data() - haystack.data() + matches[0].size();
56+
if (is_larger_than_fifty({matches[1].data(), matches[1].size()})) {
57+
return true;
58+
}
59+
}
60+
return false;
61+
}
62+
63+
bool is_slow_two_repeats(std::string_view regexp) const {
64+
re2::StringPiece haystack(regexp.data(), regexp.size());
65+
re2::StringPiece matches[3];
66+
size_t start_pos = 0;
67+
while (start_pos < haystack.size()) {
68+
if (!_searcher_two_repeats.Match(haystack, start_pos, haystack.size(),
69+
re2::RE2::Anchor::UNANCHORED, matches, 3)) {
70+
break;
71+
}
72+
73+
start_pos = matches[0].data() - haystack.data() + matches[0].size();
74+
if (is_larger_than_fifty({matches[1].data(), matches[1].size()}) ||
75+
is_larger_than_fifty({matches[2].data(), matches[2].size()})) {
76+
return true;
77+
}
78+
}
79+
return false;
80+
}
81+
82+
re2::RE2 _searcher_one_repeat;
83+
re2::RE2 _searcher_two_repeats;
84+
};
85+
86+
} // namespace
87+
88+
bool is_hyperscan_regexp_expensive(std::string_view regexp) {
89+
static const SlowWithHyperscanChecker slow_with_hyperscan_checker;
90+
return slow_with_hyperscan_checker.is_slow(regexp);
91+
}
92+
93+
} // namespace doris

‎be/src/util/hyperscan_util.h‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
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+
#pragma once
19+
20+
#include <string_view>
21+
22+
namespace doris {
23+
24+
inline constexpr std::string_view HYPERSCAN_BOUNDED_REPEAT_ERROR =
25+
"Skip hyperscan compilation because bounded repetition exceeds 50";
26+
27+
bool is_hyperscan_regexp_expensive(std::string_view regexp);
28+
29+
} // namespace doris

0 commit comments

Comments
 (0)