This is an automated email from the ASF dual-hosted git repository.
HappenLee 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 8707cc80fdf [improvement](be) Prune sparse IN predicates with full-set
zone map checks (#70559)
8707cc80fdf is described below
commit 8707cc80fdfd16b3c7dfde868a711714e734ba0f
Author: HappenLee <[email protected]>
AuthorDate: Wed Nov 18 14:18:16 2026 +0800
[improvement](be) Prune sparse IN predicates with full-set zone map checks
(#70559)
### Background
Doris uses segment and page zone maps to exclude data ranges before
reading rows. A storage IN predicate currently compares the zone's
bounds with the minimum and maximum IN values. Row-level membership
checks still use the full IN set.
### What problem does this PR solve?
Issue Number: None
Related PR: None
PR Type: Enhancement
Problem Summary:
Sparse IN lists can retain zones containing no candidate values. For
example, `IN (10, 30)` retains a zone bounded by `[11, 29]` because the
bounding ranges overlap. Check the existing typed `HybridSet` for a
value inside the zone after the cheap bounds check. Most of the diff
adds tests for pruning boundaries and conservative fallbacks.
### Details
- **Before and after:** Segment and page zone maps can now reject gaps
within an IN list's bounding range. Inclusive endpoints remain
candidates; row-level membership checks remain unchanged.
- **Configs and defaults:** Reuse `in_zonemap_point_check_threshold`
(default `8192`). Sets above the threshold retain bounds-only checks.
Dense-domain containers also retain bounds-only checks to avoid scanning
an entire domain for each zone.
- **Impact on existing users:** Sparse IN predicates may read fewer
segments and pages. Eligible checks take O(N) per zone, bounded by the
configured threshold, and use O(1) additional space. No workload latency
benchmark has been run.
- **Behavior change:** More selective metadata pruning. Negated
predicates and IN sets containing NaN retain conservative handling.
### Testing
- Local ASAN on the development baseline: `./run-be-ut.sh -j 48 --run
--filter='InListPredicateZoneMapTest.*:HybridSetTest.*:ExprZonemapFilterTest.*'`
passed all 78 tests, including 11 new tests and an exhaustive comparison
against set intersection for 741 integer ranges.
- Coverage includes fixed and dynamic sets, inclusive endpoints,
NULL/empty sets, negative predicates, threshold boundaries, dense-domain
fallback, binary strings, predicate cloning, decimals, datetime
fractions, NaNs, signed zero and infinities. `SparseIntegerSet`
exercises the gap that bounds-only checking retains.
- On the rebased master branch: clang-format 16, build hygiene and `git
diff --check` passed. The ASAN suite has not been rerun on this rebased
baseline.
- Local clang-tidy on the development baseline was blocked by a
pre-existing unmatched `NOLINTEND` in `core/types.h`.
### Notes for Reviewers
- **Scope and reuse:** Only the storage IN predicate and its unit tests
change. The implementation reuses the existing
`HybridSet::contains_any_in_range` interface.
- **Concurrency and lifetime:** The scan reads the predicate's existing
set; the change adds no mutable predicate state, ownership changes or
locks.
- **Parallel paths:** Both native segment and page pruning call this
method. Expression zone-map filtering already uses the range helper.
Parquet statistics and delete predicates are outside this change.
- **Preconditions and fallbacks:** Readers already bypass unusable zone
maps. Comments and tests explain the negative-predicate, dense-domain
and NaN cases.
- **Compatibility:** No storage-format, protocol, persistence or
write-path changes; no new configuration or FE/BE variables.
- **Observability:** Existing scan pruning counters expose skipped data;
no new per-zone logging is introduced.
### Release note
Improve segment and page pruning for sparse IN predicates.
### Check List (For Author)
- Behavior changed: Yes (see Details).
- Does this need documentation: No.
- Pre-submission status: Partially verified: local ASAN passed on the
development baseline; the rebased master branch needs CI validation. See
Testing for the local clang-tidy limitation.
### AI Disclosure
- Tool: Codex (GPT-6).
- Generated: Implementation, unit tests and this description.
- Human review: Pending maintainer review.
---
be/src/storage/predicate/in_list_predicate.h | 26 ++-
.../storage/predicate/in_list_predicate_test.cpp | 249 +++++++++++++++++++++
2 files changed, 273 insertions(+), 2 deletions(-)
diff --git a/be/src/storage/predicate/in_list_predicate.h
b/be/src/storage/predicate/in_list_predicate.h
index 10595e9db95..bea5b0af926 100644
--- a/be/src/storage/predicate/in_list_predicate.h
+++ b/be/src/storage/predicate/in_list_predicate.h
@@ -17,10 +17,12 @@
#pragma once
+#include <cmath>
#include <cstdint>
#include <roaring/roaring.hh>
#include "common/compiler_util.h"
+#include "common/config.h"
#include "common/exception.h"
#include "core/column/column_dictionary.h"
#include "core/column/column_execute_util.h"
@@ -239,8 +241,28 @@ public:
return false;
}
if constexpr (PT == PredicateType::IN_LIST) {
- return Compare::less_equal(zone_map.min_value.template
get<Type>(), _max_value) &&
- Compare::greater_equal(zone_map.max_value.template
get<Type>(), _min_value);
+ // Inverting IN (10, 30) can match values in [11, 29], so
positive-IN pruning is unsafe.
+ if (_opposite) {
+ return true;
+ }
+ if (!Compare::less_equal(zone_map.min_value.template get<Type>(),
_max_value) ||
+ !Compare::greater_equal(zone_map.max_value.template
get<Type>(), _min_value)) {
+ return false;
+ }
+ // Bound the work per zone map, including containers whose
iterators scan a dense
+ // domain rather than just the IN values: a SMALLINT bitmap has
65,536 positions.
+ if (_values->size() > config::in_zonemap_point_check_threshold ||
+ !_values->supports_fast_range_lookup()) {
+ return true;
+ }
+ if constexpr (Type == TYPE_FLOAT || Type == TYPE_DOUBLE) {
+ // NaN IN (NaN) is true under Doris equality, but the range
lookup ignores NaNs.
+ if (std::isnan(_max_value)) {
+ return true;
+ }
+ }
+ // Overlapping bounds alone cannot reject IN (10, 30) against a
zone in [11, 29].
+ return _values->contains_any_in_range(zone_map.min_value,
zone_map.max_value);
} else {
return true;
}
diff --git a/be/test/storage/predicate/in_list_predicate_test.cpp
b/be/test/storage/predicate/in_list_predicate_test.cpp
new file mode 100644
index 00000000000..5d6d09048b0
--- /dev/null
+++ b/be/test/storage/predicate/in_list_predicate_test.cpp
@@ -0,0 +1,249 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <initializer_list>
+#include <limits>
+#include <memory>
+#include <string>
+
+#include "common/config.h"
+#include "core/data_type/data_type_date_or_datetime_v2.h"
+#include "core/data_type/data_type_decimal.h"
+#include "core/data_type/data_type_number.h"
+#include "core/data_type/data_type_string.h"
+#include "exprs/bitset_container.h"
+#include "storage/predicate/predicate_creator.h"
+
+namespace doris {
+namespace {
+
+template <PrimitiveType Type>
+segment_v2::ZoneMap make_zone_map(const typename
PrimitiveTypeTraits<Type>::CppType& min,
+ const typename
PrimitiveTypeTraits<Type>::CppType& max) {
+ segment_v2::ZoneMap zone_map;
+ zone_map.has_not_null = true;
+ zone_map.min_value = Field::create_field<Type>(min);
+ zone_map.max_value = Field::create_field<Type>(max);
+ return zone_map;
+}
+
+template <PrimitiveType Type>
+std::shared_ptr<ColumnPredicate> make_in_predicate(
+ std::initializer_list<typename PrimitiveTypeTraits<Type>::CppType>
values,
+ const DataTypePtr& data_type) {
+ auto set = build_set<Type>();
+ for (const auto& value : values) {
+ if constexpr (is_string_type(Type)) {
+ const StringRef ref(value);
+ set->insert(&ref);
+ } else {
+ set->insert(&value);
+ }
+ }
+ return create_in_list_predicate<PredicateType::IN_LIST>(0, "c", data_type,
set, false);
+}
+
+} // namespace
+
+class InListPredicateZoneMapTest : public testing::Test {
+protected:
+ void SetUp() override {
+ _saved_threshold = config::in_zonemap_point_check_threshold;
+ config::in_zonemap_point_check_threshold = 8192;
+ }
+
+ void TearDown() override { config::in_zonemap_point_check_threshold =
_saved_threshold; }
+
+private:
+ int32_t _saved_threshold = 0;
+};
+
+TEST_F(InListPredicateZoneMapTest, SparseIntegerSet) {
+ auto predicate = make_in_predicate<TYPE_INT>({10, 30},
std::make_shared<DataTypeInt32>());
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_INT>(11, 12)));
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_INT>(11, 29)));
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_INT>(0, 9)));
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_INT>(31, 40)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(10, 10)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(30, 30)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(0, 10)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(29, 40)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(0, 40)));
+}
+
+TEST_F(InListPredicateZoneMapTest, FixedIntegerSet) {
+ auto set = std::make_shared<HybridSet<TYPE_INT, FixedContainer<int32_t,
2>>>(false);
+ for (int32_t value : {10, 30}) {
+ set->insert(&value);
+ }
+ auto predicate = create_in_list_predicate<PredicateType::IN_LIST>(
+ 0, "c", std::make_shared<DataTypeInt32>(), set, false);
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_INT>(11, 29)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(10, 10)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(30, 30)));
+}
+
+TEST_F(InListPredicateZoneMapTest, IntegerRangesMatchSetIntersection) {
+ const std::initializer_list<int32_t> values {-5, 0, 9, 30};
+ auto predicate = make_in_predicate<TYPE_INT>(values,
std::make_shared<DataTypeInt32>());
+ for (int32_t min = -6; min <= 31; ++min) {
+ for (int32_t max = min; max <= 31; ++max) {
+ const bool intersects = std::ranges::any_of(
+ values, [&](int32_t value) { return min <= value && value
<= max; });
+ EXPECT_EQ(intersects,
predicate->evaluate_and(make_zone_map<TYPE_INT>(min, max)))
+ << min << ", " << max;
+ }
+ }
+}
+
+TEST_F(InListPredicateZoneMapTest, NullAndEmptySets) {
+ auto predicate = make_in_predicate<TYPE_INT>({10, 30},
std::make_shared<DataTypeInt32>());
+ segment_v2::ZoneMap zone_map;
+ EXPECT_FALSE(predicate->evaluate_and(zone_map));
+ zone_map.has_null = true;
+ EXPECT_FALSE(predicate->evaluate_and(zone_map));
+ zone_map = make_zone_map<TYPE_INT>(11, 29);
+ zone_map.has_null = true;
+ EXPECT_FALSE(predicate->evaluate_and(zone_map));
+ zone_map.max_value = Field::create_field<TYPE_INT>(30);
+ EXPECT_TRUE(predicate->evaluate_and(zone_map));
+
+ auto set = build_set<TYPE_INT>();
+ for (bool contains_null : {false, true}) {
+ if (contains_null) {
+ set->insert(static_cast<const void*>(nullptr));
+ }
+ auto empty_predicate =
create_in_list_predicate<PredicateType::IN_LIST>(
+ 0, "c", std::make_shared<DataTypeInt32>(), set, false);
+ EXPECT_FALSE(empty_predicate->evaluate_and(make_zone_map<TYPE_INT>(0,
100)));
+ }
+}
+
+TEST_F(InListPredicateZoneMapTest, NegativePredicatesRemainConservative) {
+ auto set = build_set<TYPE_INT>();
+ for (int32_t value : {10, 30}) {
+ set->insert(&value);
+ }
+ auto not_in = create_in_list_predicate<PredicateType::NOT_IN_LIST>(
+ 0, "c", std::make_shared<DataTypeInt32>(), set, false);
+ auto opposite_in = create_in_list_predicate<PredicateType::IN_LIST>(
+ 0, "c", std::make_shared<DataTypeInt32>(), set, true);
+ for (const auto& predicate : {not_in, opposite_in}) {
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(11, 29)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(31, 40)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(10, 10)));
+ }
+}
+
+TEST_F(InListPredicateZoneMapTest, ExactCheckThreshold) {
+ auto predicate = make_in_predicate<TYPE_INT>({10, 30},
std::make_shared<DataTypeInt32>());
+ config::in_zonemap_point_check_threshold = 2;
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_INT>(11, 29)));
+ config::in_zonemap_point_check_threshold = 1;
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(11, 29)));
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_INT>(31, 40)));
+ config::in_zonemap_point_check_threshold = 0;
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_INT>(11, 29)));
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_INT>(0, 9)));
+}
+
+TEST_F(InListPredicateZoneMapTest, DenseDomainSetUsesBoundsOnly) {
+ auto set = std::make_shared<HybridSet<TYPE_SMALLINT,
BitSetContainer<int16_t>>>(false);
+ for (int16_t value : {10, 30}) {
+ set->insert(&value);
+ }
+ auto predicate = create_in_list_predicate<PredicateType::IN_LIST>(
+ 0, "c", std::make_shared<DataTypeInt16>(), set, false);
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_SMALLINT>(11, 29)));
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_SMALLINT>(31,
40)));
+}
+
+TEST_F(InListPredicateZoneMapTest, StringSetsPreserveBinaryOrdering) {
+ auto predicate = make_in_predicate<TYPE_STRING>(
+ {std::string("a\0a", 3), std::string("a\0z", 3)},
std::make_shared<DataTypeString>());
+ EXPECT_FALSE(predicate->evaluate_and(
+ make_zone_map<TYPE_STRING>(std::string("a\0b", 3),
std::string("a\0y", 3))));
+ EXPECT_TRUE(predicate->evaluate_and(
+ make_zone_map<TYPE_STRING>(std::string("a\0a", 3),
std::string("a\0a", 3))));
+ auto clone = predicate->clone(1);
+ predicate.reset();
+ EXPECT_FALSE(clone->evaluate_and(
+ make_zone_map<TYPE_STRING>(std::string("a\0b", 3),
std::string("a\0y", 3))));
+ EXPECT_TRUE(clone->evaluate_and(
+ make_zone_map<TYPE_STRING>(std::string("a\0y", 3),
std::string("a\0z", 3))));
+
+ auto dynamic = make_in_predicate<TYPE_STRING>({"", "a", "c", "e", "g",
"i", "k", "m", "o"},
+
std::make_shared<DataTypeString>());
+ EXPECT_FALSE(dynamic->evaluate_and(make_zone_map<TYPE_STRING>("b", "b")));
+ EXPECT_TRUE(dynamic->evaluate_and(make_zone_map<TYPE_STRING>("", "")));
+ EXPECT_TRUE(dynamic->evaluate_and(make_zone_map<TYPE_STRING>("n", "o")));
+}
+
+TEST_F(InListPredicateZoneMapTest, DecimalSet) {
+ auto predicate = make_in_predicate<TYPE_DECIMAL64>({Decimal64(-1234),
Decimal64(5678)},
+
std::make_shared<DataTypeDecimal64>(18, 2));
+ EXPECT_FALSE(predicate->evaluate_and(
+ make_zone_map<TYPE_DECIMAL64>(Decimal64(-1000), Decimal64(5000))));
+ EXPECT_TRUE(predicate->evaluate_and(
+ make_zone_map<TYPE_DECIMAL64>(Decimal64(-1234),
Decimal64(-1234))));
+ EXPECT_TRUE(predicate->evaluate_and(
+ make_zone_map<TYPE_DECIMAL64>(Decimal64(5000), Decimal64(5678))));
+}
+
+TEST_F(InListPredicateZoneMapTest, DatetimeSet) {
+ DateV2Value<DateTimeV2ValueType> low;
+ low.unchecked_set_time(2024, 1, 1, 0, 0, 0, 123456);
+ DateV2Value<DateTimeV2ValueType> high;
+ high.unchecked_set_time(2024, 1, 1, 0, 0, 0, 654321);
+ DateV2Value<DateTimeV2ValueType> middle;
+ middle.unchecked_set_time(2024, 1, 1, 0, 0, 0, 500000);
+ auto predicate = make_in_predicate<TYPE_DATETIMEV2>({low, high},
+
std::make_shared<DataTypeDateTimeV2>(6));
+
EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_DATETIMEV2>(middle,
middle)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_DATETIMEV2>(low,
low)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_DATETIMEV2>(middle,
high)));
+}
+
+TEST_F(InListPredicateZoneMapTest, FloatingPointSet) {
+ auto predicate =
+ make_in_predicate<TYPE_DOUBLE>({10.0, 30.0},
std::make_shared<DataTypeFloat64>());
+ EXPECT_FALSE(predicate->evaluate_and(make_zone_map<TYPE_DOUBLE>(11.0,
29.0)));
+ EXPECT_TRUE(predicate->evaluate_and(make_zone_map<TYPE_DOUBLE>(30.0,
30.0)));
+
+ auto with_nan =
+ make_in_predicate<TYPE_DOUBLE>({10.0, 30.0,
std::numeric_limits<double>::quiet_NaN()},
+
std::make_shared<DataTypeFloat64>());
+ auto zone_map = make_zone_map<TYPE_DOUBLE>(11.0, 29.0);
+ zone_map.has_nan = true;
+ EXPECT_TRUE(with_nan->evaluate_and(zone_map));
+ const auto nan = std::numeric_limits<double>::quiet_NaN();
+ auto only_nan = make_in_predicate<TYPE_DOUBLE>({nan},
std::make_shared<DataTypeFloat64>());
+ EXPECT_TRUE(only_nan->evaluate_and(make_zone_map<TYPE_DOUBLE>(nan, nan)));
+
+ auto zero = make_in_predicate<TYPE_FLOAT>({-0.0F, 1.0F},
std::make_shared<DataTypeFloat32>());
+ EXPECT_TRUE(zero->evaluate_and(make_zone_map<TYPE_FLOAT>(0.0F, 0.0F)));
+ const auto inf = std::numeric_limits<double>::infinity();
+ auto infinities =
+ make_in_predicate<TYPE_DOUBLE>({-inf, inf},
std::make_shared<DataTypeFloat64>());
+ EXPECT_FALSE(infinities->evaluate_and(make_zone_map<TYPE_DOUBLE>(0.0,
0.0)));
+ EXPECT_TRUE(infinities->evaluate_and(make_zone_map<TYPE_DOUBLE>(inf,
inf)));
+}
+
+} // namespace doris
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]