Skip to content

Commit 349cd15

Browse files
authored
[Enhancement](zonemap) Support column-vs-column comparisons in expression zone map pruning (apache#67774)
Zone map pruning only fires when a predicate compares a column against a constant. A predicate over two columns of the same table, `WHERE a != b` or `WHERE a < b`, never participates, so every segment and every Parquet row group is read even when the two columns' min/max ranges make the predicate unsatisfiable. Everything on the path except the leaf already supports this. `ZoneMapEvalContext` is keyed per slot and the segment-level and Parquet row-group-level callers already populate an entry for every slot a compound expression references, which is why cross-column AND / OR compounds prune today. What was missing is the comparison operator's capability gate: it accepts one slot plus one literal and nothing else, so a two-slot comparison is dropped before evaluation. This PR adds the slot-vs-slot shape next to the existing slot-vs-literal one and gives the six always-false tests a single implementation shared by both. With the left operand's non-null values in `[lmin, lmax]` and the right operand's in `[rmin, rmax]`, the comparison cannot be TRUE for any row when: | operator | condition | | --- | --- | | `=` | `lmin > rmax \|\| rmin > lmax` | | `!=` | `lmin == lmax && rmin == rmax && lmin == rmin` | | `<` | `lmin >= rmax` | | `<=` | `lmin > rmax` | | `>` | `rmin >= lmax` | | `>=` | `rmin > lmax` | Substituting the degenerate range `[literal, literal]` for the right operand reduces each row to the slot-vs-literal test already in the tree, so the single-column path keeps its exact current behaviour. The existing tests passing unchanged is the mechanical check on that. `kNoMatch` means "no row in this zone can make the conjunct TRUE", not "every row is FALSE", so NULL does not weaken these rules: a WHERE conjunct discards FALSE and NULL alike, and the bounds summarize exactly the non-null values. A column with no non-null value at all makes the comparison NULL on every row and returns `kNoMatch` unconditionally. One trap for reviewers: `can_evaluate` must not be widened. It is shared by dictionary filtering and by `can_evaluate_equality`, and both dereference `extract_slot_and_literal` behind a `DORIS_CHECK`, so accepting a slot-vs-slot expression there would abort. This PR adds a separate `can_evaluate_slot_slot` and ORs it into `can_evaluate_zonemap_filter` only; a unit test pins that down. Three deliberate limitations: a cast around either operand is rejected, because the bounds are raw stored values and the optimizer inserts a cast whenever the two column types differ; on Parquet a floating column pair does not prune at all, because Parquet bounds omit NaN without reporting how many were skipped, which would flip the `!=` rule; and VARIANT, JSONB, ARRAY/MAP/STRUCT and aggregate-state columns are not admitted, because `Field` compares any two of their values as equal, and a segment types a VARIANT path slot by its inferred leaf type, which the expression's VARIANT type would not match. The v1 Parquet reader is excluded from slot-vs-slot pruning entirely, because that reader is being removed. `_process_expr_zonemap_filter` restricts itself to single-slot conjuncts (the v1 page path already required a single column), so column-vs-column pruning runs on native segments and the v2 Parquet reader only. This also moots the v1-specific slot-vs-slot review threads here (malformed fixed-width statistics, VARBINARY mapping, and the adjusted-UTC timestamp rollback tracked by the now-closed apache#68118). The v1 single-column path keeps the decimal-domain and NaN fixes described next. A limitation on the v1 single-column path came out of review. `ParquetPredicate::parse_min_max_value` decodes v1 bounds in the file's own logical type, while `_type_matches` compares only primitive types, so a file DECIMAL at scale 3 and a table DECIMAL at scale 2 both passed and their unscaled payloads were then compared as if they shared a domain. The v1 reader now leaves the zone map out unless the file and table types agree, which is the check `format_v2` already applies. That costs pruning in three narrow places, all of them correctness-driven: a DATETIMEV2 or TIMESTAMPTZ column whose declared scale differs from the Parquet unit loses expression zone map pruning entirely, which is the widest practical case and matches the policy already written down for the slot-vs-literal path; a decimal pair differing only in precision is domain-identical yet also skipped; and IS NULL / IS NOT NULL pruning goes with it, because a zone map carrying only the null flags leaves min/max at `TYPE_NULL` and any range predicate would then fail `range_stats_usable_for_zonemap`'s type check. This also fixes a bug it uncovered. The flag that carries "these bounds came from Parquet, so a hidden NaN is possible" was only ever set in the format_v2 reader; the v1 reader assigned the slot's data type and left the flag at its default, so the NaN guard never fired on that path. Two DOUBLE columns whose Parquet bounds both read `[1.0, 1.0]` were then pruned by the `!=` rule even when one of them hid a NaN, dropping a row that should have come back. The rule now lives in one setter on `SlotZoneMap` that assigns the type and the flag together, and all three Parquet call sites go through it. The hidden version and TSO columns need no special handling here: since apache#65684, a single-version segment reads them through a `ConstantColumnReader` whose zone map holds the substituted value, so pruning sees the same value the rows come back with.
1 parent 7a7e86c commit 349cd15

9 files changed

Lines changed: 1342 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
@@ -250,6 +250,39 @@ std::optional<SlotLiteral> extract_slot_and_literal(const VExprSPtrs& args) {
250250
return std::nullopt;
251251
}
252252

253+
std::optional<SlotSlot> extract_slot_and_slot(const VExprSPtrs& args) {
254+
if (args.size() != 2) {
255+
return std::nullopt;
256+
}
257+
auto left = std::dynamic_pointer_cast<VSlotRef>(args[0]);
258+
auto right = std::dynamic_pointer_cast<VSlotRef>(args[1]);
259+
if (left == nullptr || right == nullptr) {
260+
return std::nullopt;
261+
}
262+
return SlotSlot {.left_slot_index = left->column_id(),
263+
.left_type = left->data_type(),
264+
.right_slot_index = right->column_id(),
265+
.right_type = right->data_type()};
266+
}
267+
268+
bool contains_slot_slot_comparison(const VExprSPtr& expr) {
269+
if (expr == nullptr) {
270+
return false;
271+
}
272+
// A comparison node's two operands are its children, so a slot-vs-slot leaf is a node whose
273+
// children are two VSlotRef. extract_slot_and_slot accepts a same-column pair too, which is the
274+
// point: `a < a` has one column id but is still slot-vs-slot.
275+
if (extract_slot_and_slot(expr->children()).has_value()) {
276+
return true;
277+
}
278+
for (const auto& child : expr->children()) {
279+
if (contains_slot_slot_comparison(child)) {
280+
return true;
281+
}
282+
}
283+
return false;
284+
}
285+
253286
std::optional<SlotLiteral> extract_array_contains_slot_and_literal(const VExprSPtrs& args) {
254287
if (args.size() != 2) {
255288
return std::nullopt;

‎be/src/exprs/expr_zonemap_filter.h‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,21 @@ struct SlotLiteral {
9797
bool literal_on_left;
9898
};
9999

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

121136
std::optional<SlotLiteral> extract_slot_and_literal(const VExprSPtrs& args);
122137

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

125150
ZoneMapFilterResult evaluate_array_contains_zonemap(const ZoneMapEvalContext& ctx,

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

Lines changed: 152 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,7 @@
5050
#include "exprs/vexpr.h"
5151
#include "storage/index/index_reader_helper.h"
5252
#include "storage/index/inverted/inverted_index_iterator.h"
53+
#include "storage/olap_define.h"
5354

5455
namespace doris {
5556
/** Comparison functions: ==, !=, <, >, <=, >=.
@@ -293,16 +294,43 @@ inline Op symmetric_op(Op op) {
293294
__builtin_unreachable();
294295
}
295296

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

300-
auto slot_type = expr_zonemap::fetch_compatible_slot_type(ctx, slot_literal->slot_index,
301-
slot_literal->slot_type);
325+
inline ZoneMapFilterResult evaluate_slot_literal(const ZoneMapEvalContext& ctx,
326+
const expr_zonemap::SlotLiteral& slot_literal,
327+
Op op) {
328+
auto slot_type = expr_zonemap::fetch_compatible_slot_type(ctx, slot_literal.slot_index,
329+
slot_literal.slot_type);
302330
if (slot_type == nullptr) {
303331
return unsupported_zonemap_filter(ctx);
304332
}
305-
auto zone_map_ptr = ctx.zone_map(slot_literal->slot_index);
333+
auto zone_map_ptr = ctx.zone_map(slot_literal.slot_index);
306334
if (zone_map_ptr == nullptr) {
307335
return unsupported_zonemap_filter(ctx);
308336
}
@@ -314,42 +342,95 @@ inline ZoneMapFilterResult evaluate(const ZoneMapEvalContext& ctx, const VExprSP
314342
return unsupported_zonemap_filter(ctx);
315343
}
316344

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

351-
// keep this to avoid compile failure with g++.
352-
__builtin_unreachable();
423+
inline ZoneMapFilterResult evaluate(const ZoneMapEvalContext& ctx, const VExprSPtrs& arguments,
424+
Op op) {
425+
if (auto slot_literal = expr_zonemap::extract_slot_and_literal(arguments);
426+
slot_literal.has_value()) {
427+
return evaluate_slot_literal(ctx, *slot_literal, op);
428+
}
429+
auto slot_slot = expr_zonemap::extract_slot_and_slot(arguments);
430+
// can_evaluate_zonemap_filter accepts exactly the two shapes handled above, so reaching this
431+
// point means the capability gate and this evaluator went out of sync.
432+
DORIS_CHECK(slot_slot.has_value());
433+
return evaluate_slot_slot(ctx, *slot_slot, op);
353434
}
354435

355436
inline bool can_evaluate(const VExprSPtrs& arguments) {
@@ -377,6 +458,40 @@ inline bool can_evaluate(const VExprSPtrs& arguments) {
377458
return true;
378459
}
379460

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

738853
bool can_evaluate_zonemap_filter(const VExprSPtrs& arguments) const override {
739-
return comparison_zonemap_detail::op_from_name(name).has_value() &&
740-
comparison_zonemap_detail::can_evaluate(arguments);
854+
if (!comparison_zonemap_detail::op_from_name(name).has_value()) {
855+
return false;
856+
}
857+
return comparison_zonemap_detail::can_evaluate(arguments) ||
858+
comparison_zonemap_detail::can_evaluate_slot_slot(arguments);
741859
}
742860

743861
ZoneMapFilterResult evaluate_dictionary_filter(const DictionaryEvalContext& ctx,

0 commit comments

Comments
 (0)