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]

Reply via email to