Skip to content

Commit 257417b

Browse files
authored
[feature](be) Support expression zonemap pruning (apache#63389)
Problem Summary: Support expression-based ZoneMap pruning for internal and Parquet scan paths. Supported expressions include comparisons, IN/NOT IN, IS NULL/IS NOT NULL, and starts_with. The implementation adds segment/page/row-group pruning, conservative fallback semantics, and profile counters, with BE unit and SQL regression coverage. CHAR string range statistics are supported through the trimmed logical bounds produced by ZoneMap deserialization, so CHAR predicates can participate in expression ZoneMap pruning. This follow-up also removes duplicated capability checks between `can_evaluate_zonemap_filter` and `evaluate_zonemap_filter`. Capability checks now focus on expression shape and NULL-literal cases, while storage/runtime datatype invariants are asserted with `DORIS_CHECK` in the evaluation path. The latest follow-up centralizes HybridSet-to-Field materialization for scalar and direct IN predicates, removes identity-cast unwrapping from expression ZoneMap matching, and lets null-aware runtime filters use ZoneMap pruning when the target zone has no NULL values while conservatively keeping zones that may contain NULL. The latest crash-fix follow-up makes comparison expression ZoneMap capability checks conservative when the scan slot type and literal type are not directly compatible, such as external table predicates comparing `Nullable(DateTimeV2(6))` with a `DateTimeV2(0)` literal. In that case Doris now skips expression ZoneMap pruning instead of triggering a BE `DORIS_CHECK`, leaving the normal expression evaluation path to filter rows. ### Release note Support expression-based ZoneMap pruning for scan predicates to skip data using ZoneMap statistics. ### Check List (For Author) - Test: Unit Test / Regression test / Format check - DORIS_HOME=<repo> ninja -C be/ut_build_ASAN Exprs Storage Exec Format doris_be_test - DORIS_HOME=<repo> ninja -C be/ut_build_ASAN Exprs doris_be_test - ./run-be-ut.sh --run --filter=SegmentFilterHelpersTest.* - ./run-be-ut.sh --run --filter=ScanNormalizePredicateTest.*:RuntimeFilterConsumerHelperTest.*:VRuntimeFilterWrapperSamplingTest.*:ScannerLateArrivalRFTest.* - ./run-be-ut.sh --run --filter=ParquetExprTest.test_expr_zonemap_* - ./run-be-ut.sh --run --filter=ExprZonemapFilterTest.* - ./run-be-ut.sh --run --filter='ExprZonemapFilterTest.FunctionStringStartsWithZonemapUsesPrefixRange:function_string_test.function_starts_with_test' - ./run-be-ut.sh --run --filter='ExprZonemapFilterTest.*:ParquetExprTest.test_expr_zonemap_*' - ninja -C be/ut_build_ASAN src/storage/CMakeFiles/Storage.dir/segment/segment.cpp.o src/storage/CMakeFiles/Storage.dir/segment/segment_iterator.cpp.o - ./run-be-ut.sh --run --filter=ParquetExprTest.test_expr_zonemap_page_filter_keeps_unsupported_results_and_counts_stats - doris-local-regression.sh all -d inverted_index_p0 -s test_index_range_in_select - ./run-regression-test.sh --conf <local-regression-conf> --run -d query_p0/expr_zonemap -s test_expr_zonemap_pruning - ./run-regression-test.sh --conf <local-regression-conf> --run -d query_p1/expr_zonemap -s test_expr_zonemap_pruning_p1 - doris-local-regression --network 10.26.20.3/24 all -d query_p0/expr_zonemap -s test_expr_zonemap_pruning - doris-local-regression --network 10.26.20.3/24 all -d query_p1/expr_zonemap -s test_expr_zonemap_pruning_p1 - doris-local-regression --network 10.26.20.3/24 all -d mtmv_p0 -s test_iceberg_mtmv -conf enableIcebergTest=true -conf iceberg_rest_uri_port=18283 -conf iceberg_minio_port=19001 -conf externalEnvIp=127.0.0.1 - build-support/clang-format.sh --files be/src/exprs/function/functions_comparison.h be/test/exprs/expr_zonemap_filter_test.cpp - build-support/check-format.sh --files be/src/exprs/function/functions_comparison.h be/test/exprs/expr_zonemap_filter_test.cpp - build-support/clang-format.sh - build-support/check-format.sh - doris-local-regression --network 10.26.20.3/24 run -d query_p0/expr_zonemap -s test_expr_zonemap_pruning - doris-local-regression --network 10.26.20.3/24 run -d query_p1/expr_zonemap -s test_expr_zonemap_pruning_p1 - git diff --check - Behavior changed: Yes. Supported scan predicates, including CHAR string predicates, can now prune data with expression ZoneMap evaluation. - Does this need documentation: No
1 parent f9105c3 commit 257417b

45 files changed

Lines changed: 3481 additions & 27 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎be/src/exec/operator/olap_scan_operator.cpp‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -229,6 +229,16 @@ Status OlapScanLocalState::_init_profile() {
229229
_stats_filtered_counter = ADD_COUNTER(_segment_profile, "RowsStatsFiltered", TUnit::UNIT);
230230
_stats_rp_filtered_counter =
231231
ADD_COUNTER(_segment_profile, "RowsZoneMapRuntimePredicateFiltered", TUnit::UNIT);
232+
_expr_zonemap_filtered_segment_counter =
233+
ADD_COUNTER(_segment_profile, "ExprZoneMapFilteredSegments", TUnit::UNIT);
234+
_expr_zonemap_filtered_page_counter =
235+
ADD_COUNTER(_segment_profile, "ExprZoneMapFilteredPages", TUnit::UNIT);
236+
_expr_zonemap_unusable_counter =
237+
ADD_COUNTER(_segment_profile, "ExprZoneMapUnusableEvals", TUnit::UNIT);
238+
_in_zonemap_point_check_counter =
239+
ADD_COUNTER(_segment_profile, "InZoneMapPointCheckCount", TUnit::UNIT);
240+
_in_zonemap_range_only_counter =
241+
ADD_COUNTER(_segment_profile, "InZoneMapRangeOnlyCount", TUnit::UNIT);
232242
_bf_filtered_counter = ADD_COUNTER(_segment_profile, "RowsBloomFilterFiltered", TUnit::UNIT);
233243
_dict_filtered_counter = ADD_COUNTER(_segment_profile, "SegmentDictFiltered", TUnit::UNIT);
234244
_del_filtered_counter = ADD_COUNTER(_scanner_profile, "RowsDelFiltered", TUnit::UNIT);

‎be/src/exec/operator/olap_scan_operator.h‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -164,6 +164,17 @@ class OlapScanLocalState final : public ScanLocalState<OlapScanLocalState> {
164164

165165
RuntimeProfile::Counter* _stats_filtered_counter = nullptr;
166166
RuntimeProfile::Counter* _stats_rp_filtered_counter = nullptr;
167+
// Number of whole segments skipped by expression ZoneMap evaluation.
168+
RuntimeProfile::Counter* _expr_zonemap_filtered_segment_counter = nullptr;
169+
// Number of pages skipped by expression ZoneMap evaluation after page index ranges are built.
170+
RuntimeProfile::Counter* _expr_zonemap_filtered_page_counter = nullptr;
171+
// Number of expression ZoneMap evaluations that reached the evaluator but could not use the
172+
// current ZoneMap context, such as missing slot/page ZoneMap or unusable range statistics.
173+
RuntimeProfile::Counter* _expr_zonemap_unusable_counter = nullptr;
174+
// Number of IN-predicate ZoneMap evaluations that used per-value point checks.
175+
RuntimeProfile::Counter* _in_zonemap_point_check_counter = nullptr;
176+
// Number of IN-predicate ZoneMap evaluations that fell back to min/max range overlap only.
177+
RuntimeProfile::Counter* _in_zonemap_range_only_counter = nullptr;
167178
RuntimeProfile::Counter* _bf_filtered_counter = nullptr;
168179
RuntimeProfile::Counter* _dict_filtered_counter = nullptr;
169180
RuntimeProfile::Counter* _del_filtered_counter = nullptr;

‎be/src/exec/runtime_filter/runtime_filter_consumer.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -100,7 +100,7 @@ Status RuntimeFilterConsumer::_get_push_exprs(std::vector<RuntimeFilterExprPtr>&
100100
node.in_predicate.__set_is_not_in(false);
101101
node.__set_opcode(TExprOpcode::FILTER_IN);
102102
node.__set_is_nullable(false);
103-
auto in_pred = VDirectInPredicate::create_shared(node, _wrapper->hybrid_set());
103+
auto in_pred = VDirectInPredicate::create_shared(node, _wrapper->hybrid_set(), true);
104104
in_pred->add_child(probe_ctx->root());
105105
auto wrapper = RuntimeFilterExpr::create_shared(
106106
node, in_pred, get_in_list_ignore_thredhold(_wrapper->hybrid_set()->size()),

‎be/src/exec/scan/olap_scanner.cpp‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -935,6 +935,14 @@ void OlapScanner::_collect_profile_before_close() {
935935
COUNTER_UPDATE(local_state->_rows_expr_cond_input_counter, stats.expr_cond_input_rows);
936936
COUNTER_UPDATE(local_state->_stats_filtered_counter, stats.rows_stats_filtered);
937937
COUNTER_UPDATE(local_state->_stats_rp_filtered_counter, stats.rows_stats_rp_filtered);
938+
COUNTER_UPDATE(local_state->_expr_zonemap_filtered_segment_counter,
939+
stats.expr_zonemap_filtered_segments);
940+
COUNTER_UPDATE(local_state->_expr_zonemap_filtered_page_counter,
941+
stats.expr_zonemap_filtered_pages);
942+
COUNTER_UPDATE(local_state->_expr_zonemap_unusable_counter, stats.expr_zonemap_unusable_evals);
943+
COUNTER_UPDATE(local_state->_in_zonemap_point_check_counter,
944+
stats.in_zonemap_point_check_count);
945+
COUNTER_UPDATE(local_state->_in_zonemap_range_only_counter, stats.in_zonemap_range_only_count);
938946
COUNTER_UPDATE(local_state->_dict_filtered_counter, stats.segment_dict_filtered);
939947
COUNTER_UPDATE(local_state->_bf_filtered_counter, stats.rows_bf_filtered);
940948
COUNTER_UPDATE(local_state->_del_filtered_counter, stats.rows_del_filtered);
Lines changed: 268 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,268 @@
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 "exprs/expr_zonemap_filter.h"
19+
20+
#include <algorithm>
21+
#include <set>
22+
#include <utility>
23+
24+
#include "common/check.h"
25+
#include "common/logging.h"
26+
#include "core/column/column.h"
27+
#include "core/data_type/data_type_nullable.h"
28+
#include "core/string_ref.h"
29+
#include "exprs/hybrid_set.h"
30+
#include "exprs/vexpr.h"
31+
#include "exprs/vexpr_context.h"
32+
#include "exprs/vliteral.h"
33+
#include "exprs/vslot_ref.h"
34+
#include "runtime/runtime_state.h"
35+
36+
namespace doris::expr_zonemap {
37+
namespace {
38+
39+
constexpr size_t kInZoneMapPointCheckThreshold = 64;
40+
41+
std::optional<std::pair<Field, DataTypePtr>> field_from_literal_expr(const VExprSPtr& expr) {
42+
auto literal = std::dynamic_pointer_cast<VLiteral>(expr);
43+
if (literal == nullptr) {
44+
return std::nullopt;
45+
}
46+
Field field;
47+
literal->get_column_ptr()->get(0, field);
48+
return std::make_pair(std::move(field), literal->get_data_type());
49+
}
50+
51+
bool value_in_range(const Field& value, const Field& min_value, const Field& max_value) {
52+
return value >= min_value && value <= max_value;
53+
}
54+
55+
} // namespace
56+
57+
TExprNode create_texpr_node_from_hybrid_set_value(const void* data, const PrimitiveType& type,
58+
int precision, int scale) {
59+
if (is_string_type(type)) {
60+
const auto* value = reinterpret_cast<const StringRef*>(data);
61+
auto field = Field::create_field<TYPE_STRING>(String(value->data, value->size));
62+
return create_texpr_node_from(field, type, precision, scale);
63+
}
64+
return create_texpr_node_from(data, type, precision, scale);
65+
}
66+
67+
Status materialize_hybrid_set_for_zonemap_filter(HybridSetBase& set, const DataTypePtr& data_type,
68+
InZonemapMaterializedSet* result) {
69+
DORIS_CHECK(result != nullptr);
70+
DORIS_CHECK(data_type != nullptr);
71+
const auto value_type = remove_nullable(data_type);
72+
DORIS_CHECK(value_type != nullptr);
73+
74+
result->contains_null = set.contain_null();
75+
result->values.clear();
76+
result->min_value = Field();
77+
result->max_value = Field();
78+
79+
auto* iterator = set.begin();
80+
while (iterator->has_next()) {
81+
const void* value = iterator->get_value();
82+
if (value != nullptr) {
83+
TExprNode literal_node = create_texpr_node_from_hybrid_set_value(
84+
value, value_type->get_primitive_type(), value_type->get_precision(),
85+
value_type->get_scale());
86+
auto literal = VLiteral::create_shared(literal_node);
87+
Field field;
88+
literal->get_column_ptr()->get(0, field);
89+
result->values.emplace_back(std::move(field));
90+
}
91+
iterator->next();
92+
}
93+
94+
if (!result->values.empty()) {
95+
auto minmax = std::ranges::minmax_element(
96+
result->values, [](const Field& lhs, const Field& rhs) { return lhs < rhs; });
97+
result->min_value = *minmax.min;
98+
result->max_value = *minmax.max;
99+
}
100+
return Status::OK();
101+
}
102+
103+
std::optional<SlotLiteral> extract_slot_and_literal(const VExprSPtrs& args) {
104+
if (args.size() != 2) {
105+
return std::nullopt;
106+
}
107+
108+
if (auto slot = std::dynamic_pointer_cast<VSlotRef>(args[0]); slot) {
109+
auto literal = field_from_literal_expr(args[1]);
110+
if (!literal.has_value()) {
111+
return std::nullopt;
112+
}
113+
auto [literal_value, literal_type] = std::move(*literal);
114+
return SlotLiteral {.slot_index = slot->column_id(),
115+
.slot_type = slot->data_type(),
116+
.literal = std::move(literal_value),
117+
.literal_type = std::move(literal_type),
118+
.literal_on_left = false};
119+
}
120+
121+
if (auto slot = std::dynamic_pointer_cast<VSlotRef>(args[1]); slot) {
122+
auto literal = field_from_literal_expr(args[0]);
123+
if (!literal.has_value()) {
124+
return std::nullopt;
125+
}
126+
auto [literal_value, literal_type] = std::move(*literal);
127+
return SlotLiteral {.slot_index = slot->column_id(),
128+
.slot_type = slot->data_type(),
129+
.literal = std::move(literal_value),
130+
.literal_type = std::move(literal_type),
131+
.literal_on_left = true};
132+
}
133+
134+
return std::nullopt;
135+
}
136+
137+
bool range_stats_usable_for_zonemap(const segment_v2::ZoneMap& zone_map,
138+
const DataTypePtr& data_type) {
139+
if (zone_map.pass_all || zone_map.has_nan || zone_map.has_positive_inf ||
140+
zone_map.has_negative_inf) {
141+
return false;
142+
}
143+
DORIS_CHECK(data_type != nullptr);
144+
auto primitive_type = remove_nullable(data_type)->get_primitive_type();
145+
DORIS_CHECK(field_types_compatible(zone_map.min_value.get_type(), primitive_type));
146+
DORIS_CHECK(field_types_compatible(zone_map.max_value.get_type(), primitive_type));
147+
return true;
148+
}
149+
150+
ZoneMapFilterResult eval_null_zonemap(const ZoneMapEvalContext& ctx, const VExprSPtrs& arguments,
151+
bool is_null) {
152+
DORIS_CHECK(arguments.size() == 1);
153+
auto slot = std::dynamic_pointer_cast<VSlotRef>(arguments[0]);
154+
DORIS_CHECK(slot != nullptr);
155+
auto zone_map_ptr = ctx.zone_map(slot->column_id());
156+
if (zone_map_ptr == nullptr) {
157+
return unsupported_zonemap_filter(ctx);
158+
}
159+
const auto& zone_map = *zone_map_ptr;
160+
if (is_null) {
161+
return zone_map.has_null ? ZoneMapFilterResult::kMayMatch : ZoneMapFilterResult::kNoMatch;
162+
}
163+
return zone_map.has_not_null ? ZoneMapFilterResult::kMayMatch : ZoneMapFilterResult::kNoMatch;
164+
}
165+
166+
ZoneMapFilterResult eval_in_zonemap(const ZoneMapEvalContext& ctx, const VExprSPtr& slot_expr,
167+
bool is_not_in, const std::vector<Field>& values,
168+
const Field& min_value, const Field& max_value) {
169+
auto slot = std::dynamic_pointer_cast<VSlotRef>(slot_expr);
170+
DORIS_CHECK(slot != nullptr);
171+
// Empty IN has no candidate values, while NOT IN with an empty set cannot filter anything.
172+
if (values.empty()) {
173+
return is_not_in ? ZoneMapFilterResult::kMayMatch : ZoneMapFilterResult::kNoMatch;
174+
}
175+
176+
// The caller has materialized the IN set and precomputed its non-null min/max. They must match
177+
// the expression slot type before being compared with storage zone-map statistics.
178+
DORIS_CHECK(!min_value.is_null());
179+
DORIS_CHECK(!max_value.is_null());
180+
auto data_type = remove_nullable(slot->data_type());
181+
DORIS_CHECK(data_type != nullptr);
182+
DORIS_CHECK(field_types_compatible(min_value.get_type(), data_type->get_primitive_type()));
183+
DORIS_CHECK(field_types_compatible(max_value.get_type(), data_type->get_primitive_type()));
184+
185+
// Re-check against the reader-schema type and the available zone map. Missing or unsupported
186+
// metadata must conservatively fall back to may-match.
187+
auto slot_type = fetch_compatible_slot_type(ctx, slot->column_id(), slot->data_type());
188+
if (slot_type == nullptr) {
189+
return unsupported_zonemap_filter(ctx);
190+
}
191+
auto zone_map_ptr = ctx.zone_map(slot->column_id());
192+
if (zone_map_ptr == nullptr) {
193+
return unsupported_zonemap_filter(ctx);
194+
}
195+
const auto& zone_map = *zone_map_ptr;
196+
// IN values are all non-null here, so an all-null zone cannot match.
197+
if (!zone_map.has_not_null) {
198+
return ZoneMapFilterResult::kNoMatch;
199+
}
200+
201+
if (!range_stats_usable_for_zonemap(zone_map, slot_type)) {
202+
return unsupported_zonemap_filter(ctx);
203+
}
204+
205+
if (is_not_in) {
206+
// NOT IN can only prune when the whole zone contains exactly one non-null value and that
207+
// value is excluded by the set. Wider ranges may contain values that are not filtered.
208+
if (zone_map.min_value == zone_map.max_value) {
209+
const bool only_value_is_filtered = std::ranges::any_of(
210+
values, [&](const Field& value) { return value == zone_map.min_value; });
211+
return only_value_is_filtered ? ZoneMapFilterResult::kNoMatch
212+
: ZoneMapFilterResult::kMayMatch;
213+
}
214+
return ZoneMapFilterResult::kMayMatch;
215+
}
216+
217+
// First use the materialized IN-set min/max to rule out disjoint zone-map ranges.
218+
if (zone_map.max_value < min_value || zone_map.min_value > max_value) {
219+
return ZoneMapFilterResult::kNoMatch;
220+
}
221+
222+
// For large IN sets, avoid checking every point on the scan hot path. The range overlap above
223+
// is only a coarse may-match signal.
224+
if (values.size() > kInZoneMapPointCheckThreshold) {
225+
++ctx.stats.in_zonemap_range_only_count;
226+
return ZoneMapFilterResult::kMayMatch;
227+
}
228+
229+
// For small IN sets, verify whether any candidate value can fall into the zone-map range.
230+
++ctx.stats.in_zonemap_point_check_count;
231+
for (const auto& value : values) {
232+
if (value_in_range(value, zone_map.min_value, zone_map.max_value)) {
233+
return ZoneMapFilterResult::kMayMatch;
234+
}
235+
}
236+
return ZoneMapFilterResult::kNoMatch;
237+
}
238+
239+
// Return the only slot ordinal referenced by a zonemap-evaluable expression. A negative result is
240+
// the conservative fallback marker for unsupported expressions, multi-slot expressions, or invalid
241+
// slot ordinals, so callers can skip schema-indexed zonemap pruning safely.
242+
int single_slot_zonemap_index(const VExprContextSPtr& ctx) {
243+
DORIS_CHECK(ctx != nullptr);
244+
const auto& root = ctx->root();
245+
DORIS_CHECK(root != nullptr);
246+
if (!root->can_evaluate_zonemap_filter()) {
247+
return -1;
248+
}
249+
250+
std::set<int> slot_indexes;
251+
root->collect_slot_column_ids(slot_indexes);
252+
if (slot_indexes.size() != 1) {
253+
return -1;
254+
}
255+
256+
return *slot_indexes.begin();
257+
}
258+
259+
bool is_expr_zonemap_filter_enabled(const RuntimeState* state) {
260+
if (state == nullptr) {
261+
return true;
262+
}
263+
const auto& query_options = state->query_options();
264+
return !query_options.__isset.enable_expr_zonemap_filter ||
265+
query_options.enable_expr_zonemap_filter;
266+
}
267+
268+
} // namespace doris::expr_zonemap

0 commit comments

Comments
 (0)