Skip to content

Commit 601c18a

Browse files
LuciferYangHappenLee
authored andcommitted
[improvement](zonemap) Support column-vs-column expression zone map pruning
### What problem does this PR solve? Issue Number: None Related PR: #67774 Problem Summary: Backport column-to-column expression zone map pruning to branch-4.2. Share the six interval non-match rules with literal comparisons, retain conservative handling for NULL, NaN, truncated strings and unsupported types, and carry the Parquet v1 correctness guards and unit/regression coverage. Preserve the branch-4.2 BloomFilterProbe interfaces. Unlike master, 4.2 substitutes the hidden version column after reading a single-version rowset, so exclude its on-disk placeholder statistics from segment and page expression pruning. ### Release note Support column-to-column comparisons in expression zone map pruning for native segments and Parquet V2 row groups. ### Check List (For Author) - Test: clang-format 16.0.6, check-format and git diff --check passed. All 43 regression golden labels match; the generated golden file is unchanged from the original PR. BE build and focused unit-test execution were attempted; no local runtime test has completed with the incomplete third-party package. - Behavior changed: Yes. More predicates can prune; unsupported statistics keep candidates, and hidden-version placeholders are excluded on branch-4.2. - Does this need documentation: No. Backport of an existing feature. (cherry picked from commit 349cd15)
1 parent 627eb86 commit 601c18a

11 files changed

Lines changed: 1354 additions & 81 deletions

File tree

‎be/src/exprs/expr_zonemap_filter.cpp‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -265,6 +265,39 @@ std::optional<SlotLiteral> extract_slot_and_literal(const VExprSPtrs& args) {
265265
return std::nullopt;
266266
}
267267

268+
std::optional<SlotSlot> extract_slot_and_slot(const VExprSPtrs& args) {
269+
if (args.size() != 2) {
270+
return std::nullopt;
271+
}
272+
auto left = std::dynamic_pointer_cast<VSlotRef>(args[0]);
273+
auto right = std::dynamic_pointer_cast<VSlotRef>(args[1]);
274+
if (left == nullptr || right == nullptr) {
275+
return std::nullopt;
276+
}
277+
return SlotSlot {.left_slot_index = left->column_id(),
278+
.left_type = left->data_type(),
279+
.right_slot_index = right->column_id(),
280+
.right_type = right->data_type()};
281+
}
282+
283+
bool contains_slot_slot_comparison(const VExprSPtr& expr) {
284+
if (expr == nullptr) {
285+
return false;
286+
}
287+
// A comparison node's two operands are its children, so a slot-vs-slot leaf is a node whose
288+
// children are two VSlotRef. extract_slot_and_slot accepts a same-column pair too, which is the
289+
// point: `a < a` has one column id but is still slot-vs-slot.
290+
if (extract_slot_and_slot(expr->children()).has_value()) {
291+
return true;
292+
}
293+
for (const auto& child : expr->children()) {
294+
if (contains_slot_slot_comparison(child)) {
295+
return true;
296+
}
297+
}
298+
return false;
299+
}
300+
268301
std::optional<BloomFilterProbe> extract_bloom_filter_probe(const VExprSPtr& expr) {
269302
if (expr == nullptr || expr->data_type() == nullptr) {
270303
return std::nullopt;

‎be/src/exprs/expr_zonemap_filter.h‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -100,6 +100,21 @@ struct SlotLiteral {
100100
bool literal_on_left;
101101
};
102102

103+
// A comparison whose both operands are plain slot references, e.g. `WHERE a != b`. Unlike
104+
// SlotLiteral there is no flag to flip the operator: with two slots the argument order already is
105+
// the expression order, so evaluators use the comparison operator as written.
106+
struct SlotSlot {
107+
// Slot ordinals of the left and right operand. Both are keys used to look up the corresponding
108+
// reader-schema type and zone map from ZoneMapEvalContext, same as SlotLiteral::slot_index.
109+
int left_slot_index;
110+
// Type carried by the left slot expression. Kept separately for the same reason as
111+
// SlotLiteral::slot_type: evaluation first has to verify the expression binding is compatible
112+
// with the reader-schema type held by the context.
113+
DataTypePtr left_type;
114+
int right_slot_index;
115+
DataTypePtr right_type;
116+
};
117+
103118
enum class BloomFilterPathKind {
104119
STRUCT_FIELD,
105120
LIST_ELEMENT,
@@ -123,6 +138,16 @@ struct BloomFilterProbe {
123138

124139
std::optional<SlotLiteral> extract_slot_and_literal(const VExprSPtrs& args);
125140

141+
// Both operands must be bare VSlotRef. A cast around a slot is deliberately rejected: the zone map
142+
// holds raw stored values, so comparing across a cast would need the cast applied to the bounds.
143+
std::optional<SlotSlot> extract_slot_and_slot(const VExprSPtrs& args);
144+
145+
// True if the expression tree contains a slot-vs-slot comparison leaf (two VSlotRef operands),
146+
// at the root or nested under AND/OR, including two references to the same column (`a < a`). The v1
147+
// Parquet reader uses this to exclude slot-vs-slot pruning entirely: counting distinct columns is
148+
// not enough because a same-column pair still has one column id.
149+
bool contains_slot_slot_comparison(const VExprSPtr& expr);
150+
126151
std::optional<BloomFilterProbe> extract_bloom_filter_probe(const VExprSPtr& expr);
127152

128153
std::optional<BloomFilterProbe> extract_bloom_filter_predicate_probe(const VExprSPtr& expr);

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

Lines changed: 152 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,7 @@
4949
#include "exprs/vexpr.h"
5050
#include "runtime/runtime_state.h"
5151
#include "storage/index/index_reader_helper.h"
52+
#include "storage/olap_define.h"
5253

5354
namespace doris {
5455
#include "common/compile_check_begin.h"
@@ -300,16 +301,43 @@ inline Op symmetric_op(Op op) {
300301
__builtin_unreachable();
301302
}
302303

303-
inline ZoneMapFilterResult evaluate(const ZoneMapEvalContext& ctx, const VExprSPtrs& arguments,
304-
Op op) {
305-
auto slot_literal = expr_zonemap::extract_slot_and_literal(arguments);
304+
// Return true when `L <op> R` cannot be TRUE for any row, given that every non-null value of the
305+
// left operand lies in [lmin, lmax] and every non-null value of the right operand lies in
306+
// [rmin, rmax]. This only compares the four bounds: callers must already have rejected zone maps
307+
// whose bounds are unusable and columns that hold no non-null value at all.
308+
//
309+
// The slot-vs-literal path passes the literal as the degenerate range [literal, literal], which
310+
// reduces every branch below to the plain slot-vs-literal test it replaced.
311+
inline bool range_vs_range_no_match(const Field& lmin, const Field& lmax, const Field& rmin,
312+
const Field& rmax, Op op) {
313+
switch (op) {
314+
case Op::EQ:
315+
// Disjoint ranges cannot share a value.
316+
return lmin > rmax || rmin > lmax;
317+
case Op::NE:
318+
// Only provable when both sides collapse to the same single value.
319+
return lmin == lmax && rmin == rmax && lmin == rmin;
320+
case Op::LT:
321+
return lmin >= rmax;
322+
case Op::LE:
323+
return lmin > rmax;
324+
case Op::GT:
325+
return rmin >= lmax;
326+
case Op::GE:
327+
return rmin > lmax;
328+
}
329+
__builtin_unreachable();
330+
}
306331

307-
auto slot_type = expr_zonemap::fetch_compatible_slot_type(ctx, slot_literal->slot_index,
308-
slot_literal->slot_type);
332+
inline ZoneMapFilterResult evaluate_slot_literal(const ZoneMapEvalContext& ctx,
333+
const expr_zonemap::SlotLiteral& slot_literal,
334+
Op op) {
335+
auto slot_type = expr_zonemap::fetch_compatible_slot_type(ctx, slot_literal.slot_index,
336+
slot_literal.slot_type);
309337
if (slot_type == nullptr) {
310338
return unsupported_zonemap_filter(ctx);
311339
}
312-
auto zone_map_ptr = ctx.zone_map(slot_literal->slot_index);
340+
auto zone_map_ptr = ctx.zone_map(slot_literal.slot_index);
313341
if (zone_map_ptr == nullptr) {
314342
return unsupported_zonemap_filter(ctx);
315343
}
@@ -321,42 +349,95 @@ inline ZoneMapFilterResult evaluate(const ZoneMapEvalContext& ctx, const VExprSP
321349
return unsupported_zonemap_filter(ctx);
322350
}
323351

324-
const auto effective_op = slot_literal->literal_on_left ? symmetric_op(op) : op;
325-
const auto& literal = slot_literal->literal;
352+
const auto effective_op = slot_literal.literal_on_left ? symmetric_op(op) : op;
353+
const auto& literal = slot_literal.literal;
326354
const bool literal_is_nan = literal.is_nan();
327355
const bool hidden_nan_can_match = (effective_op == Op::EQ && literal_is_nan) ||
328356
(effective_op == Op::NE && !literal_is_nan) ||
329357
(effective_op == Op::GT && !literal_is_nan) ||
330358
effective_op == Op::GE;
331-
if (ctx.floating_nan_count_unknown(slot_literal->slot_index) && hidden_nan_can_match) {
359+
if (ctx.floating_nan_count_unknown(slot_literal.slot_index) && hidden_nan_can_match) {
332360
// Parquet bounds omit NaNs, so only operators that cannot match a hidden NaN may prune.
333361
return unsupported_zonemap_filter(ctx);
334362
}
335-
switch (effective_op) {
336-
case Op::EQ:
337-
return literal < zone_map.min_value || zone_map.max_value < literal
338-
? ZoneMapFilterResult::kNoMatch
339-
: ZoneMapFilterResult::kMayMatch;
340-
case Op::NE:
341-
return zone_map.min_value == literal && zone_map.max_value == literal
342-
? ZoneMapFilterResult::kNoMatch
343-
: ZoneMapFilterResult::kMayMatch;
344-
case Op::LT:
345-
return zone_map.min_value >= literal ? ZoneMapFilterResult::kNoMatch
346-
: ZoneMapFilterResult::kMayMatch;
347-
case Op::LE:
348-
return zone_map.min_value > literal ? ZoneMapFilterResult::kNoMatch
349-
: ZoneMapFilterResult::kMayMatch;
350-
case Op::GT:
351-
return zone_map.max_value <= literal ? ZoneMapFilterResult::kNoMatch
352-
: ZoneMapFilterResult::kMayMatch;
353-
case Op::GE:
354-
return zone_map.max_value < literal ? ZoneMapFilterResult::kNoMatch
355-
: ZoneMapFilterResult::kMayMatch;
363+
return range_vs_range_no_match(zone_map.min_value, zone_map.max_value, literal, literal,
364+
effective_op)
365+
? ZoneMapFilterResult::kNoMatch
366+
: ZoneMapFilterResult::kMayMatch;
367+
}
368+
369+
inline ZoneMapFilterResult evaluate_slot_slot(const ZoneMapEvalContext& ctx,
370+
const expr_zonemap::SlotSlot& slot_slot, Op op) {
371+
const auto left_type = expr_zonemap::fetch_compatible_slot_type(ctx, slot_slot.left_slot_index,
372+
slot_slot.left_type);
373+
const auto right_type = expr_zonemap::fetch_compatible_slot_type(
374+
ctx, slot_slot.right_slot_index, slot_slot.right_type);
375+
if (left_type == nullptr || right_type == nullptr) {
376+
// The context skips a slot entirely when the segment cannot apply predicates on it.
377+
return unsupported_zonemap_filter(ctx);
378+
}
379+
const auto left_zone_map = ctx.zone_map(slot_slot.left_slot_index);
380+
const auto right_zone_map = ctx.zone_map(slot_slot.right_slot_index);
381+
if (left_zone_map == nullptr || right_zone_map == nullptr) {
382+
// A slot can be present with a data type but no zone map, so this is a separate check.
383+
return unsupported_zonemap_filter(ctx);
384+
}
385+
// A column holding no non-null value makes the comparison NULL on every row, which never
386+
// satisfies a WHERE conjunct. This must run before the range checks below: an all-null zone map
387+
// leaves min/max default-constructed as TYPE_NULL, which the range checks would fatal on.
388+
if (!left_zone_map->has_not_null || !right_zone_map->has_not_null) {
389+
return ZoneMapFilterResult::kNoMatch;
390+
}
391+
if (!expr_zonemap::range_stats_usable_for_zonemap(*left_zone_map, left_type) ||
392+
!expr_zonemap::range_stats_usable_for_zonemap(*right_zone_map, right_type)) {
393+
return unsupported_zonemap_filter(ctx);
394+
}
395+
// A native string zone-map max of exactly MAX_ZONE_MAP_INDEX_SIZE bytes was bumped upward,
396+
// and may also have been truncated (segments written before the carry fix may hold a bump
397+
// that wrapped on 0xff), so a bound of that length is not a reliable fence for a two-sided
398+
// proof. A shorter bound is the exact value; the bump never changes the length, so this also
399+
// rejects those wrapped bounds.
400+
// The test only decides whether to trust the bound as a fence. A Parquet-sourced string bound
401+
// shorter than the cap is not necessarily exact, but it is a spec-conservative min/max, which
402+
// is all a range proof needs; do not tighten this to assume exactness below the cap.
403+
// data_types_compatible pairs strings only with strings, so checking one side's type is enough
404+
// to know all four bounds are strings.
405+
if (is_string_type(remove_nullable(left_type)->get_primitive_type())) {
406+
auto is_untruncated = [](const Field& f) {
407+
return f.get<TYPE_STRING>().size() < MAX_ZONE_MAP_INDEX_SIZE;
408+
};
409+
if (!is_untruncated(left_zone_map->min_value) ||
410+
!is_untruncated(left_zone_map->max_value) ||
411+
!is_untruncated(right_zone_map->min_value) ||
412+
!is_untruncated(right_zone_map->max_value)) {
413+
return unsupported_zonemap_filter(ctx);
414+
}
415+
}
416+
// Parquet bounds omit NaN without recording how many were skipped, so a zone map that looks
417+
// like a single point may still hide one, which would flip the NE rule from false to true. The
418+
// slot-vs-literal path can reason per operator because it knows whether the literal is NaN;
419+
// with two slots there is no literal, so bail out for every operator instead.
420+
if (ctx.floating_nan_count_unknown(slot_slot.left_slot_index) ||
421+
ctx.floating_nan_count_unknown(slot_slot.right_slot_index)) {
422+
return unsupported_zonemap_filter(ctx);
356423
}
424+
return range_vs_range_no_match(left_zone_map->min_value, left_zone_map->max_value,
425+
right_zone_map->min_value, right_zone_map->max_value, op)
426+
? ZoneMapFilterResult::kNoMatch
427+
: ZoneMapFilterResult::kMayMatch;
428+
}
357429

358-
// keep this to avoid compile failure with g++.
359-
__builtin_unreachable();
430+
inline ZoneMapFilterResult evaluate(const ZoneMapEvalContext& ctx, const VExprSPtrs& arguments,
431+
Op op) {
432+
if (auto slot_literal = expr_zonemap::extract_slot_and_literal(arguments);
433+
slot_literal.has_value()) {
434+
return evaluate_slot_literal(ctx, *slot_literal, op);
435+
}
436+
auto slot_slot = expr_zonemap::extract_slot_and_slot(arguments);
437+
// can_evaluate_zonemap_filter accepts exactly the two shapes handled above, so reaching this
438+
// point means the capability gate and this evaluator went out of sync.
439+
DORIS_CHECK(slot_slot.has_value());
440+
return evaluate_slot_slot(ctx, *slot_slot, op);
360441
}
361442

362443
inline bool can_evaluate(const VExprSPtrs& arguments) {
@@ -384,6 +465,40 @@ inline bool can_evaluate(const VExprSPtrs& arguments) {
384465
return true;
385466
}
386467

468+
// Accept a comparison whose both operands are slot references. Kept separate from can_evaluate on
469+
// purpose: can_evaluate also gates dictionary filtering and can_evaluate_equality, and both of
470+
// those dereference extract_slot_and_literal behind a DORIS_CHECK, so widening it would abort on a
471+
// slot-vs-slot expression. Only can_evaluate_zonemap_filter ORs this in.
472+
inline bool can_evaluate_slot_slot(const VExprSPtrs& arguments) {
473+
auto slot_slot = expr_zonemap::extract_slot_and_slot(arguments);
474+
if (!slot_slot.has_value()) {
475+
return false;
476+
}
477+
DORIS_CHECK(slot_slot->left_type != nullptr);
478+
DORIS_CHECK(slot_slot->right_type != nullptr);
479+
// Reject types whose slot-slot bounds cannot be compared safely:
480+
// - VARBINARY: v1 Parquet produces a TYPE_STRING bound for it, which
481+
// range_stats_usable_for_zonemap aborts on instead of falling back.
482+
// - VARIANT: a segment types a path slot by its inferred leaf type (a typed `v.a` is INT), so
483+
// fetch_compatible_slot_type's check against the VARIANT expression type would fail.
484+
// - ARRAY/MAP/STRUCT, JSONB, aggregate states: Field orders every pair of them as equal.
485+
// A truncated string bound is rejected later, in evaluate_slot_slot, by its length.
486+
const auto excluded = [](const DataTypePtr& type) {
487+
const auto primitive_type = remove_nullable(type)->get_primitive_type();
488+
return is_varbinary(primitive_type) || primitive_type == TYPE_VARIANT ||
489+
primitive_type == TYPE_JSONB || is_complex_type(primitive_type) ||
490+
is_var_len_object(primitive_type);
491+
};
492+
if (excluded(slot_slot->left_type) || excluded(slot_slot->right_type)) {
493+
return false;
494+
}
495+
// The two zone maps' Fields are compared directly and Field comparison throws on mismatched
496+
// non-string types, so reject incompatible column pairs here. A pair differing only by width or
497+
// decimal scale never reaches this point anyway, because the optimizer inserts a cast and a
498+
// cast is not a VSlotRef.
499+
return expr_zonemap::data_types_compatible(slot_slot->left_type, slot_slot->right_type);
500+
}
501+
387502
inline bool can_evaluate_equality(const VExprSPtrs& arguments, Op op) {
388503
if (op != Op::EQ || !can_evaluate(arguments)) {
389504
return false;
@@ -657,8 +772,11 @@ class FunctionComparison : public IFunction {
657772
}
658773

659774
bool can_evaluate_zonemap_filter(const VExprSPtrs& arguments) const override {
660-
return comparison_zonemap_detail::op_from_name(name).has_value() &&
661-
comparison_zonemap_detail::can_evaluate(arguments);
775+
if (!comparison_zonemap_detail::op_from_name(name).has_value()) {
776+
return false;
777+
}
778+
return comparison_zonemap_detail::can_evaluate(arguments) ||
779+
comparison_zonemap_detail::can_evaluate_slot_slot(arguments);
662780
}
663781

664782
ZoneMapFilterResult evaluate_dictionary_filter(const DictionaryEvalContext& ctx,

0 commit comments

Comments
 (0)