| // 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. |
| |
| #pragma once |
| |
| #include <gen_cpp/Metrics_types.h> |
| #include <gen_cpp/PaloInternalService_types.h> |
| #include <glog/logging.h> |
| #include <stddef.h> |
| |
| #include <boost/container/detail/std_fwd.hpp> |
| #include <boost/lexical_cast.hpp> |
| #include <cstdint> |
| #include <iterator> |
| #include <limits> |
| #include <memory> |
| #include <set> |
| #include <sstream> |
| #include <string> |
| #include <utility> |
| #include <variant> |
| #include <vector> |
| |
| #include "common/compare.h" |
| #include "common/status.h" |
| #include "core/data_type/define_primitive_type.h" |
| #include "core/data_type/primitive_type.h" |
| #include "core/type_limit.h" |
| #include "core/types.h" |
| #include "core/value/ipv4_value.h" |
| #include "core/value/ipv6_value.h" |
| #include "core/value/time_value.h" |
| #include "core/value/vdatetime_value.h" |
| #include "exprs/function/cast/cast_to_string.h" |
| #include "runtime/runtime_profile.h" |
| #include "storage/olap_common.h" |
| #include "storage/olap_tuple.h" |
| #include "storage/olap_utils.h" |
| #include "storage/predicate/filter_olap_param.h" |
| |
| namespace doris { |
| |
| /** |
| * @brief Column's value range |
| **/ |
| template <PrimitiveType primitive_type> |
| class ColumnValueRange { |
| public: |
| using CppType = typename PrimitiveTypeTraits<primitive_type>::CppType; |
| using SetType = std::set<CppType, doris::Less<CppType>>; |
| using IteratorType = typename SetType::iterator; |
| |
| ColumnValueRange(); |
| |
| ColumnValueRange(std::string col_name, bool is_nullable_col, int precision, int scale); |
| |
| // should add fixed value before add range |
| Status add_fixed_value(const CppType& value); |
| |
| // should remove fixed value after add fixed value |
| void remove_fixed_value(const CppType& value); |
| |
| Status add_range(SQLFilterOp op, CppType value); |
| |
| bool is_fixed_value_range() const; |
| |
| bool is_scope_value_range() const; |
| |
| bool is_empty_value_range() const; |
| |
| bool is_fixed_value_convertible() const; |
| |
| bool is_range_value_convertible() const; |
| |
| void convert_to_range_value(); |
| |
| bool convert_to_avg_range_value(std::vector<OlapTuple>& begin_scan_keys, |
| std::vector<OlapTuple>& end_scan_keys, bool& begin_include, |
| bool& end_include, int32_t max_scan_key_num); |
| |
| bool convert_to_close_range(std::vector<OlapTuple>& begin_scan_keys, |
| std::vector<OlapTuple>& end_scan_keys, bool& begin_include, |
| bool& end_include); |
| |
| constexpr bool is_reject_split_type() const { return _is_reject_split_type; } |
| |
| void intersection(ColumnValueRange<primitive_type>& range); |
| |
| void set_empty_value_range() { |
| _fixed_values.clear(); |
| _low_value = TYPE_MAX; |
| _high_value = TYPE_MIN; |
| _contain_null = false; |
| } |
| |
| const SetType& get_fixed_value_set() const { return _fixed_values; } |
| |
| CppType get_range_max_value() const { return _high_value; } |
| |
| CppType get_range_min_value() const { return _low_value; } |
| |
| const CppType* get_range_max_value_ptr() const { return &_high_value; } |
| |
| const CppType* get_range_min_value_ptr() const { return &_low_value; } |
| |
| SQLFilterOp get_range_high_op() const { return _high_op; } |
| |
| SQLFilterOp get_range_low_op() const { return _low_op; } |
| |
| bool is_low_value_minimum() const { return Compare::equal(_low_value, TYPE_MIN); } |
| |
| bool is_high_value_maximum() const { return Compare::equal(_high_value, TYPE_MAX); } |
| |
| bool is_begin_include() const { return _low_op == FILTER_LARGER_OR_EQUAL; } |
| |
| bool is_end_include() const { return _high_op == FILTER_LESS_OR_EQUAL; } |
| |
| PrimitiveType type() const { return _column_type; } |
| |
| const std::string& column_name() const { return _column_name; } |
| |
| bool contain_null() const { return _contain_null; } |
| |
| size_t get_fixed_value_size() const { return _fixed_values.size(); } |
| |
| void set_whole_value_range() { |
| _fixed_values.clear(); |
| _low_value = TYPE_MIN; |
| _high_value = TYPE_MAX; |
| _low_op = FILTER_LARGER_OR_EQUAL; |
| _high_op = FILTER_LESS_OR_EQUAL; |
| _contain_null = _is_nullable_col; |
| } |
| |
| bool is_whole_value_range() const { |
| DCHECK(_is_nullable_col || !contain_null()) |
| << "Non-nullable column cannot contains null value"; |
| |
| return _fixed_values.empty() && Compare::equal(_low_value, TYPE_MIN) && |
| Compare::equal(_high_value, TYPE_MAX) && _low_op == FILTER_LARGER_OR_EQUAL && |
| _high_op == FILTER_LESS_OR_EQUAL && _is_nullable_col == contain_null(); |
| } |
| |
| // only two case will set range contain null, call by temp_range in olap scan node |
| // 'is null' and 'is not null' |
| // 1. if the pred is 'is null' means the range should be |
| // empty in fixed_range and _high_value < _low_value |
| // 2. if the pred is 'is not null' means the range should be whole range and |
| // 'is not null' be effective |
| void set_contain_null(bool contain_null) { |
| if (contain_null) { |
| set_empty_value_range(); |
| } else { |
| set_whole_value_range(); |
| } |
| _contain_null = _is_nullable_col && contain_null; |
| } |
| |
| int precision() const { return _precision; } |
| |
| int scale() const { return _scale; } |
| |
| static void add_fixed_value_range(ColumnValueRange<primitive_type>& range, SQLFilterOp op, |
| const CppType& value) { |
| static_cast<void>(range.add_fixed_value(value)); |
| } |
| |
| static void remove_fixed_value_range(ColumnValueRange<primitive_type>& range, SQLFilterOp op, |
| const CppType& value) { |
| range.remove_fixed_value(value); |
| } |
| |
| static void empty_function(ColumnValueRange<primitive_type>& range, SQLFilterOp op, |
| const CppType& value) {} |
| |
| static void add_value_range(ColumnValueRange<primitive_type>& range, SQLFilterOp op, |
| const CppType& value) { |
| static_cast<void>(range.add_range(op, value)); |
| } |
| |
| static ColumnValueRange<primitive_type> create_empty_column_value_range(bool is_nullable_col, |
| int precision, |
| int scale) { |
| return ColumnValueRange<primitive_type>("", TYPE_MAX, TYPE_MIN, is_nullable_col, false, |
| precision, scale); |
| } |
| |
| protected: |
| bool is_in_range(const CppType& value); |
| |
| private: |
| ColumnValueRange(std::string col_name, const CppType& min, const CppType& max, |
| bool is_nullable_col, bool contain_null, int precision, int scale); |
| |
| const static CppType TYPE_MIN; // Column type's min value |
| const static CppType TYPE_MAX; // Column type's max value |
| |
| std::string _column_name; |
| PrimitiveType _column_type; // Column type (eg: TINYINT,SMALLINT,INT,BIGINT) |
| CppType _low_value; // Column's low value, closed interval at left |
| CppType _high_value; // Column's high value, open interval at right |
| SQLFilterOp _low_op; |
| SQLFilterOp _high_op; |
| SetType _fixed_values; // Column's fixed int value |
| |
| bool _is_nullable_col; |
| bool _contain_null; |
| int _precision; |
| int _scale; |
| |
| static constexpr bool _is_reject_split_type = |
| primitive_type == PrimitiveType::TYPE_FLOAT || |
| primitive_type == PrimitiveType::TYPE_DOUBLE || |
| primitive_type == PrimitiveType::TYPE_LARGEINT || |
| primitive_type == PrimitiveType::TYPE_DECIMALV2 || |
| primitive_type == PrimitiveType::TYPE_VARCHAR || |
| primitive_type == PrimitiveType::TYPE_CHAR || |
| primitive_type == PrimitiveType::TYPE_STRING || |
| primitive_type == PrimitiveType::TYPE_BOOLEAN || |
| primitive_type == PrimitiveType::TYPE_DATETIME || |
| primitive_type == PrimitiveType::TYPE_DATETIMEV2 || |
| primitive_type == PrimitiveType::TYPE_TIMESTAMPTZ || |
| primitive_type == PrimitiveType::TYPE_DECIMAL256; |
| }; |
| template <> |
| const typename ColumnValueRange<TYPE_FLOAT>::CppType ColumnValueRange<TYPE_FLOAT>::TYPE_MIN; |
| template <> |
| const typename ColumnValueRange<TYPE_FLOAT>::CppType ColumnValueRange<TYPE_FLOAT>::TYPE_MAX; |
| template <> |
| const typename ColumnValueRange<TYPE_DOUBLE>::CppType ColumnValueRange<TYPE_DOUBLE>::TYPE_MIN; |
| template <> |
| const typename ColumnValueRange<TYPE_DOUBLE>::CppType ColumnValueRange<TYPE_DOUBLE>::TYPE_MAX; |
| |
| /// OlapScanKeys accumulates multi-column prefix scan keys from per-column ColumnValueRange |
| /// constraints, and converts them into OlapScanRange objects for the storage layer. |
| /// |
| /// Overall pipeline (with examples for table t(k1 INT, k2 INT, v INT)): |
| /// |
| /// 1. _normalize_conjuncts() (scan_operator.cpp) |
| /// Parses SQL WHERE conjuncts into per-column ColumnValueRange objects. |
| /// e.g. "WHERE k1 IN (1,2) AND k2 = 10" |
| /// => ColumnValueRange<k1>: fixed_values = {1, 2} |
| /// => ColumnValueRange<k2>: fixed_values = {10} |
| /// |
| /// 2. _build_key_ranges_and_filters() (olap_scan_operator.cpp) |
| /// Iterates key columns in schema order, calling extend_scan_key() for each column |
| /// to expand internal _begin_scan_keys / _end_scan_keys. |
| /// |
| /// 3. extend_scan_key() (this class) |
| /// Appends one more column dimension to existing scan keys (Cartesian product for |
| /// fixed values, or min/max for range values). |
| /// After k1: _begin_scan_keys = [(1), (2)] _end_scan_keys = [(1), (2)] |
| /// After k2: _begin_scan_keys = [(1,10), (2,10)] _end_scan_keys = [(1,10), (2,10)] |
| /// |
| /// 4. get_key_range() (olap_scan_common.cpp) |
| /// Converts each (_begin_scan_keys[i], _end_scan_keys[i]) pair into an OlapScanRange. |
| /// => OlapScanRange{ begin=(1,10), end=(1,10), has_lower_bound=true, ... } |
| /// => OlapScanRange{ begin=(2,10), end=(2,10), has_lower_bound=true, ... } |
| /// |
| /// 5. If no key predicates exist, get_key_range returns empty; the caller creates a single |
| /// default OlapScanRange with has_lower_bound=false (represents full table scan). |
| /// |
| class OlapScanKeys { |
| public: |
| /// Extend internal scan key pairs with the next key column's ColumnValueRange. |
| /// |
| /// - If the range has fixed values, produces a Cartesian product of existing keys |
| /// and the fixed values (subject to max_scan_key_num limit). |
| /// - If the range is a scope (min..max), appends min to begin keys and max to end keys, |
| /// and sets _has_range_value=true (no further columns can be appended). |
| /// |
| /// @param exact_value [out]: true if the range covers the column's values exactly |
| /// (can be erased from residual predicates). |
| /// @param eos [out]: true if the range is provably empty (no rows to scan). |
| /// @param should_break[out]: true if the range cannot be encoded and we should stop. |
| template <PrimitiveType primitive_type> |
| Status extend_scan_key(ColumnValueRange<primitive_type>& range, int32_t max_scan_key_num, |
| bool* exact_value, bool* eos, bool* should_break); |
| |
| /// Convert accumulated scan key pairs into OlapScanRange objects for the storage layer. |
| Status get_key_range(std::vector<std::unique_ptr<OlapScanRange>>* key_range); |
| |
| bool has_range_value() const { return _has_range_value; } |
| |
| void clear() { |
| _has_range_value = false; |
| _begin_scan_keys.clear(); |
| _end_scan_keys.clear(); |
| } |
| |
| std::string debug_string() { |
| std::stringstream ss; |
| DCHECK(_begin_scan_keys.size() == _end_scan_keys.size()); |
| ss << "ScanKeys:"; |
| |
| for (int i = 0; i < _begin_scan_keys.size(); ++i) { |
| ss << "ScanKey=" << (_begin_include ? "[" : "(") << _begin_scan_keys[i].debug_string() |
| << " : " << _end_scan_keys[i].debug_string() << (_end_include ? "]" : ")"); |
| } |
| return ss.str(); |
| } |
| |
| size_t size() { |
| DCHECK(_begin_scan_keys.size() == _end_scan_keys.size()); |
| return _begin_scan_keys.size(); |
| } |
| |
| void set_is_convertible(bool is_convertible) { _is_convertible = is_convertible; } |
| |
| private: |
| std::vector<OlapTuple> _begin_scan_keys; |
| std::vector<OlapTuple> _end_scan_keys; |
| bool _has_range_value = false; |
| bool _begin_include = false; |
| bool _end_include = false; |
| bool _is_convertible = false; |
| }; |
| |
| using ColumnValueRangeType = std::variant< |
| ColumnValueRange<TYPE_TINYINT>, ColumnValueRange<TYPE_SMALLINT>, ColumnValueRange<TYPE_INT>, |
| ColumnValueRange<TYPE_BIGINT>, ColumnValueRange<TYPE_LARGEINT>, |
| ColumnValueRange<TYPE_FLOAT>, ColumnValueRange<TYPE_DOUBLE>, ColumnValueRange<TYPE_IPV4>, |
| ColumnValueRange<TYPE_IPV6>, ColumnValueRange<TYPE_CHAR>, ColumnValueRange<TYPE_VARCHAR>, |
| ColumnValueRange<TYPE_STRING>, ColumnValueRange<TYPE_DATE>, ColumnValueRange<TYPE_DATEV2>, |
| ColumnValueRange<TYPE_DATETIME>, ColumnValueRange<TYPE_DATETIMEV2>, |
| ColumnValueRange<TYPE_TIMESTAMPTZ>, ColumnValueRange<TYPE_DECIMALV2>, |
| ColumnValueRange<TYPE_BOOLEAN>, ColumnValueRange<TYPE_DECIMAL32>, |
| ColumnValueRange<TYPE_DECIMAL64>, ColumnValueRange<TYPE_DECIMAL128I>, |
| ColumnValueRange<TYPE_DECIMAL256>>; |
| |
| template <PrimitiveType primitive_type> |
| const typename ColumnValueRange<primitive_type>::CppType |
| ColumnValueRange<primitive_type>::TYPE_MIN = |
| type_limit<typename ColumnValueRange<primitive_type>::CppType>::min(); |
| template <PrimitiveType primitive_type> |
| const typename ColumnValueRange<primitive_type>::CppType |
| ColumnValueRange<primitive_type>::TYPE_MAX = |
| type_limit<typename ColumnValueRange<primitive_type>::CppType>::max(); |
| |
| template <PrimitiveType primitive_type> |
| ColumnValueRange<primitive_type>::ColumnValueRange() |
| : _column_type(INVALID_TYPE), _precision(-1), _scale(-1) {} |
| |
| template <PrimitiveType primitive_type> |
| ColumnValueRange<primitive_type>::ColumnValueRange(std::string col_name, const CppType& min, |
| const CppType& max, bool is_nullable_col, |
| bool contain_null, int precision, int scale) |
| : _column_name(std::move(col_name)), |
| _column_type(primitive_type), |
| _low_value(min), |
| _high_value(max), |
| _low_op(FILTER_LARGER_OR_EQUAL), |
| _high_op(FILTER_LESS_OR_EQUAL), |
| _is_nullable_col(is_nullable_col), |
| _contain_null(is_nullable_col && contain_null), |
| _precision(precision), |
| _scale(scale) {} |
| |
| template <PrimitiveType primitive_type> |
| ColumnValueRange<primitive_type>::ColumnValueRange(std::string col_name, bool is_nullable_col, |
| int precision, int scale) |
| : ColumnValueRange(std::move(col_name), TYPE_MIN, TYPE_MAX, is_nullable_col, |
| is_nullable_col, precision, scale) {} |
| |
| template <PrimitiveType primitive_type> |
| Status ColumnValueRange<primitive_type>::add_fixed_value(const CppType& value) { |
| if (INVALID_TYPE == _column_type) { |
| return Status::InternalError("AddFixedValue failed, Invalid type"); |
| } |
| |
| _fixed_values.insert(value); |
| _contain_null = false; |
| |
| _high_value = TYPE_MIN; |
| _low_value = TYPE_MAX; |
| |
| return Status::OK(); |
| } |
| |
| template <PrimitiveType primitive_type> |
| void ColumnValueRange<primitive_type>::remove_fixed_value(const CppType& value) { |
| _fixed_values.erase(value); |
| } |
| |
| template <PrimitiveType primitive_type> |
| bool ColumnValueRange<primitive_type>::is_fixed_value_range() const { |
| return _fixed_values.size() != 0; |
| } |
| |
| template <PrimitiveType primitive_type> |
| bool ColumnValueRange<primitive_type>::is_scope_value_range() const { |
| return Compare::greater(_high_value, _low_value); |
| } |
| |
| template <PrimitiveType primitive_type> |
| bool ColumnValueRange<primitive_type>::is_empty_value_range() const { |
| if (INVALID_TYPE == _column_type) { |
| return true; |
| } |
| |
| return (!is_fixed_value_range() && !is_scope_value_range() && !contain_null()); |
| } |
| |
| template <PrimitiveType primitive_type> |
| bool ColumnValueRange<primitive_type>::is_fixed_value_convertible() const { |
| if (is_fixed_value_range()) { |
| return false; |
| } |
| |
| if (!is_enumeration_type(_column_type)) { |
| return false; |
| } |
| |
| return true; |
| } |
| |
| template <PrimitiveType primitive_type> |
| bool ColumnValueRange<primitive_type>::is_range_value_convertible() const { |
| if (!is_fixed_value_range()) { |
| return false; |
| } |
| |
| if (TYPE_NULL == _column_type || TYPE_BOOLEAN == _column_type) { |
| return false; |
| } |
| |
| return true; |
| } |
| |
| // The return value indicates whether eos. |
| template <PrimitiveType primitive_type> |
| bool ColumnValueRange<primitive_type>::convert_to_close_range( |
| std::vector<OlapTuple>& begin_scan_keys, std::vector<OlapTuple>& end_scan_keys, |
| bool& begin_include, bool& end_include) { |
| if constexpr (!_is_reject_split_type) { |
| begin_include = true; |
| end_include = true; |
| |
| bool is_empty = false; |
| |
| if (!is_begin_include()) { |
| if (Compare::equal(_low_value, TYPE_MAX)) { |
| is_empty = true; |
| } else { |
| ++_low_value; |
| } |
| } |
| |
| if (!is_end_include()) { |
| if (Compare::equal(_high_value, TYPE_MIN)) { |
| is_empty = true; |
| } else { |
| --_high_value; |
| } |
| } |
| |
| if (Compare::less(_high_value, _low_value)) { |
| is_empty = true; |
| } |
| |
| if (is_empty && !contain_null()) { |
| begin_scan_keys.clear(); |
| end_scan_keys.clear(); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // The return value indicates whether the split result is range or fixed value. |
| template <PrimitiveType primitive_type> |
| bool ColumnValueRange<primitive_type>::convert_to_avg_range_value( |
| std::vector<OlapTuple>& begin_scan_keys, std::vector<OlapTuple>& end_scan_keys, |
| bool& begin_include, bool& end_include, int32_t max_scan_key_num) { |
| if constexpr (!_is_reject_split_type) { |
| CppType min_value = get_range_min_value(); |
| CppType max_value = get_range_max_value(); |
| if constexpr (primitive_type == PrimitiveType::TYPE_DATE) { |
| min_value.set_type(TimeType::TIME_DATE); |
| max_value.set_type(TimeType::TIME_DATE); |
| } |
| auto empty_range_only_null = Compare::greater(min_value, max_value); |
| if (empty_range_only_null) { |
| // Not contain null will be disposed in `convert_to_close_range`, return eos. |
| DCHECK(contain_null()); |
| } |
| |
| auto no_split = [&]() -> bool { |
| begin_scan_keys.emplace_back(); |
| if (contain_null()) { |
| begin_scan_keys.back().add_null(); |
| } else { |
| begin_scan_keys.back().add_field( |
| Field::create_field<primitive_type>(get_range_min_value())); |
| } |
| end_scan_keys.emplace_back(); |
| if (empty_range_only_null) { |
| end_scan_keys.back().add_null(); |
| } else { |
| end_scan_keys.back().add_field( |
| Field::create_field<primitive_type>(get_range_max_value())); |
| } |
| return true; |
| }; |
| if (empty_range_only_null || max_scan_key_num == 1) { |
| return no_split(); |
| } |
| |
| auto cast = [](const CppType& value) { |
| if constexpr (primitive_type == PrimitiveType::TYPE_DATE || |
| primitive_type == PrimitiveType::TYPE_DATEV2) { |
| return value; |
| } else { |
| return (int128_t)value; |
| } |
| }; |
| |
| // When CppType is date, we can not convert it to integer number and calculate distance. |
| // In other case, we convert element to int128 to avoit overflow. |
| int128_t step_size_may_overflow = (cast(max_value) - min_value) / max_scan_key_num; |
| |
| constexpr size_t MAX_STEP_SIZE = 1 << 20; |
| // When the step size is too large, the range is easy to not really contain data. |
| if (step_size_may_overflow > MAX_STEP_SIZE) { |
| return no_split(); |
| } |
| int step_size = cast_set<int>(step_size_may_overflow); |
| int real_step_size = 0; |
| |
| // Add null key if contain null, must do after no_split check |
| if (contain_null()) { |
| begin_scan_keys.emplace_back(); |
| begin_scan_keys.back().add_null(); |
| end_scan_keys.emplace_back(); |
| end_scan_keys.back().add_null(); |
| } |
| while (true) { |
| begin_scan_keys.emplace_back(); |
| begin_scan_keys.back().add_field(Field::create_field<primitive_type>(min_value)); |
| |
| if (cast(max_value) - min_value < step_size) { |
| min_value = max_value; |
| } else { |
| min_value += step_size; |
| } |
| |
| end_scan_keys.emplace_back(); |
| end_scan_keys.back().add_field(Field::create_field<primitive_type>(min_value)); |
| |
| if (Compare::equal(min_value, max_value)) { |
| break; |
| } |
| ++min_value; |
| ++real_step_size; |
| if (real_step_size > MAX_STEP_SIZE) { |
| throw Exception(Status::InternalError( |
| "convert_to_avg_range_value meet error. type={}, step_size={}", |
| int(primitive_type), step_size)); |
| } |
| } |
| |
| return step_size != 0; |
| } |
| return false; |
| } |
| |
| template <PrimitiveType primitive_type> |
| void ColumnValueRange<primitive_type>::convert_to_range_value() { |
| if (!is_range_value_convertible()) { |
| return; |
| } |
| |
| if (!_fixed_values.empty()) { |
| _low_value = *_fixed_values.begin(); |
| _low_op = FILTER_LARGER_OR_EQUAL; |
| _high_value = *_fixed_values.rbegin(); |
| _high_op = FILTER_LESS_OR_EQUAL; |
| _fixed_values.clear(); |
| } |
| } |
| |
| template <PrimitiveType primitive_type> |
| Status ColumnValueRange<primitive_type>::add_range(SQLFilterOp op, const CppType value) { |
| if (INVALID_TYPE == _column_type) { |
| return Status::InternalError("AddRange failed, Invalid type"); |
| } |
| |
| // add range means range should not contain null |
| _contain_null = false; |
| |
| if (is_fixed_value_range()) { |
| std::pair<IteratorType, IteratorType> bound_pair = _fixed_values.equal_range(value); |
| |
| switch (op) { |
| case FILTER_LARGER: { |
| _fixed_values.erase(_fixed_values.begin(), bound_pair.second); |
| break; |
| } |
| |
| case FILTER_LARGER_OR_EQUAL: { |
| _fixed_values.erase(_fixed_values.begin(), bound_pair.first); |
| break; |
| } |
| |
| case FILTER_LESS: { |
| if (bound_pair.first == _fixed_values.find(value)) { |
| _fixed_values.erase(bound_pair.first, _fixed_values.end()); |
| } else { |
| _fixed_values.erase(bound_pair.second, _fixed_values.end()); |
| } |
| |
| break; |
| } |
| |
| case FILTER_LESS_OR_EQUAL: { |
| _fixed_values.erase(bound_pair.second, _fixed_values.end()); |
| break; |
| } |
| |
| default: { |
| return Status::InternalError("Add Range fail! Unsupported SQLFilterOp."); |
| } |
| } |
| |
| _high_value = TYPE_MIN; |
| _low_value = TYPE_MAX; |
| } else { |
| if (Compare::greater(_high_value, _low_value)) { |
| switch (op) { |
| case FILTER_LARGER: { |
| if (Compare::greater_equal(value, _low_value)) { |
| _low_value = value; |
| _low_op = op; |
| } |
| |
| break; |
| } |
| |
| case FILTER_LARGER_OR_EQUAL: { |
| if (Compare::greater(value, _low_value)) { |
| _low_value = value; |
| _low_op = op; |
| } |
| |
| break; |
| } |
| |
| case FILTER_LESS: { |
| if (Compare::less_equal(value, _high_value)) { |
| _high_value = value; |
| _high_op = op; |
| } |
| |
| break; |
| } |
| |
| case FILTER_LESS_OR_EQUAL: { |
| if (Compare::less(value, _high_value)) { |
| _high_value = value; |
| _high_op = op; |
| } |
| |
| break; |
| } |
| |
| default: { |
| return Status::InternalError("Add Range fail! Unsupported SQLFilterOp."); |
| } |
| } |
| } |
| |
| if (FILTER_LARGER_OR_EQUAL == _low_op && FILTER_LESS_OR_EQUAL == _high_op && |
| Compare::equal(_high_value, _low_value)) { |
| RETURN_IF_ERROR(add_fixed_value(_high_value)); |
| _high_value = TYPE_MIN; |
| _low_value = TYPE_MAX; |
| } |
| } |
| |
| return Status::OK(); |
| } |
| |
| template <PrimitiveType primitive_type> |
| bool ColumnValueRange<primitive_type>::is_in_range(const CppType& value) { |
| switch (_high_op) { |
| case FILTER_LESS: { |
| switch (_low_op) { |
| case FILTER_LARGER: { |
| return Compare::less(value, _high_value) && Compare::greater(value, _low_value); |
| } |
| |
| case FILTER_LARGER_OR_EQUAL: { |
| return Compare::less(value, _high_value) && Compare::greater_equal(value, _low_value); |
| } |
| |
| default: { |
| DCHECK(false); |
| } |
| } |
| |
| break; |
| } |
| |
| case FILTER_LESS_OR_EQUAL: { |
| switch (_low_op) { |
| case FILTER_LARGER: { |
| return Compare::less_equal(value, _high_value) && Compare::greater(value, _low_value); |
| } |
| |
| case FILTER_LARGER_OR_EQUAL: { |
| return Compare::less_equal(value, _high_value) && |
| Compare::greater_equal(value, _low_value); |
| } |
| |
| default: { |
| DCHECK(false); |
| } |
| } |
| } |
| |
| default: { |
| DCHECK(false); |
| } |
| } |
| |
| return false; |
| } |
| |
| template <PrimitiveType primitive_type> |
| void ColumnValueRange<primitive_type>::intersection(ColumnValueRange<primitive_type>& range) { |
| // 1. clear if column type not match |
| if (_column_type != range._column_type) { |
| set_empty_value_range(); |
| } |
| |
| // 2. clear if any range is empty |
| if (is_empty_value_range() || range.is_empty_value_range()) { |
| set_empty_value_range(); |
| } |
| |
| SetType result_values; |
| // 3. fixed_value intersection, fixed value range do not contain null |
| if (is_fixed_value_range() || range.is_fixed_value_range()) { |
| if (is_fixed_value_range() && range.is_fixed_value_range()) { |
| set_intersection(_fixed_values.begin(), _fixed_values.end(), |
| range._fixed_values.begin(), range._fixed_values.end(), |
| std::inserter(result_values, result_values.begin())); |
| } else if (is_fixed_value_range() && !range.is_fixed_value_range()) { |
| IteratorType iter = _fixed_values.begin(); |
| |
| while (iter != _fixed_values.end()) { |
| if (range.is_in_range(*iter)) { |
| result_values.insert(*iter); |
| } |
| ++iter; |
| } |
| } else if (!is_fixed_value_range() && range.is_fixed_value_range()) { |
| IteratorType iter = range._fixed_values.begin(); |
| while (iter != range._fixed_values.end()) { |
| if (this->is_in_range(*iter)) { |
| result_values.insert(*iter); |
| } |
| ++iter; |
| } |
| } |
| |
| if (!result_values.empty()) { |
| _fixed_values = std::move(result_values); |
| _contain_null = false; |
| _high_value = TYPE_MIN; |
| _low_value = TYPE_MAX; |
| } else { |
| set_empty_value_range(); |
| } |
| } else { |
| if (contain_null() && range.contain_null()) { |
| // if both is_whole_range to keep the same, else set_contain_null |
| if (!is_whole_value_range() || !range.is_whole_value_range()) { |
| set_contain_null(true); |
| } |
| } else { |
| static_cast<void>(add_range(range._high_op, range._high_value)); |
| static_cast<void>(add_range(range._low_op, range._low_value)); |
| } |
| } |
| } |
| |
| /// Extend the accumulated scan key pairs (_begin_scan_keys / _end_scan_keys) by appending |
| /// one more key column's ColumnValueRange. |
| /// |
| /// Called once per key column in schema order by _build_key_ranges_and_filters(). |
| /// The function handles two kinds of ColumnValueRange: |
| /// (A) Fixed values — from IN / = predicates (begin == end for each value, point lookup) |
| /// (B) Scope range — from > / >= / < / <= predicates (begin = min, end = max) |
| /// |
| /// ======== Example 1: Two fixed-value columns (IN + =) ======== |
| /// Table t(k1 INT, k2 INT, v INT), key columns = (k1, k2). |
| /// WHERE k1 IN (1, 2) AND k2 = 10 |
| /// |
| /// Call 1: extend_scan_key(k1's range {fixed_values={1,2}}) |
| /// _begin_scan_keys was empty, so create one pair per fixed value: |
| /// _begin = [(1), (2)] _end = [(1), (2)] include=[true, true] |
| /// |
| /// Call 2: extend_scan_key(k2's range {fixed_values={10}}) |
| /// _begin is non-empty, so do Cartesian product (existing keys × new fixed values): |
| /// _begin = [(1,10), (2,10)] _end = [(1,10), (2,10)] include=[true, true] |
| /// |
| /// ======== Example 2: Fixed + range (IN + between) ======== |
| /// WHERE k1 IN (1, 2) AND k2 >= 5 AND k2 < 10 |
| /// |
| /// Call 1: extend_scan_key(k1's range {fixed_values={1,2}}) |
| /// _begin = [(1), (2)] _end = [(1), (2)] |
| /// |
| /// Call 2: extend_scan_key(k2's range {scope [5, 10)}) |
| /// k2 is a scope range, so append min=5 to all begin keys, max=10 to all end keys: |
| /// _begin = [(1,5), (2,5)] _end = [(1,10), (2,10)] |
| /// _begin_include = true (>=) _end_include = false (<) |
| /// Set _has_range_value = true → no further columns can be appended. |
| /// |
| /// ======== Example 3: Single range column ======== |
| /// WHERE k1 >= 100 AND k1 <= 200 |
| /// |
| /// Call 1: extend_scan_key(k1's range {scope [100, 200]}) |
| /// _begin was empty, so create one pair: |
| /// _begin = [(100)] _end = [(200)] include=[true, true] |
| /// Set _has_range_value = true. |
| /// |
| /// ======== Example 4: Too many fixed values (exceeds max_scan_key_num) ======== |
| /// WHERE k1 IN (1, 2, ..., 10000) — exceeds limit |
| /// |
| /// If is_range_value_convertible(): convert fixed set {1..10000} to scope [1, 10000], |
| /// then extend as a range (same as Example 3), and set *exact_value = false |
| /// (the predicate must be kept for residual filtering). |
| /// |
| /// If NOT convertible (e.g. BOOLEAN/NULL type): set *should_break = true, stop extending. |
| /// |
| /// ======== Example 5: Range splitting (convert_to_avg_range_value) ======== |
| /// WHERE k1 >= 1 AND k1 <= 100, with max_scan_key_num = 4 |
| /// If k1 is an integer type that supports splitting: |
| /// convert_to_close_range: adjust to closed range [1, 100] |
| /// convert_to_avg_range_value: split into ~4 sub-ranges: |
| /// _begin = [(1), (26), (51), (76)] _end = [(25), (50), (75), (100)] |
| /// Set _has_range_value = true. |
| /// |
| /// @param range [in/out] The next key column's ColumnValueRange (may be mutated |
| /// if fixed values must be converted to a range). |
| /// @param max_scan_key_num [in] Upper limit on total number of scan key pairs. |
| /// @param exact_value [out] Set to true if the column's predicate is fully captured |
| /// by scan keys (can be erased from residual filters). |
| /// @param eos [out] Set to true if the range is provably empty. |
| /// @param should_break [out] Set to true if extending must stop (un-convertible overflow). |
| template <PrimitiveType primitive_type> |
| Status OlapScanKeys::extend_scan_key(ColumnValueRange<primitive_type>& range, |
| int32_t max_scan_key_num, bool* exact_value, bool* eos, |
| bool* should_break) { |
| using ConstIterator = typename ColumnValueRange<primitive_type>::SetType::const_iterator; |
| |
| // 1. If the column's value range is empty (contradictory predicates, e.g. k1 > 10 AND k1 < 5), |
| // clear all accumulated keys — no rows can match. |
| if (range.is_empty_value_range()) { |
| _begin_scan_keys.clear(); |
| _end_scan_keys.clear(); |
| return Status::OK(); |
| } |
| |
| // 2. Once a previous column was extended as a scope range, we cannot append more columns, |
| // because the begin/end keys would have different semantics per pair. |
| // e.g. after k1 in [5, 10), appending k2 values is meaningless for short-key index. |
| if (_has_range_value) { |
| return Status::OK(); |
| } |
| |
| // 3. Overflow check: if fixed_value_count × existing_key_count > max_scan_key_num, |
| // Cartesian product would be too large. |
| // - If convertible: degrade fixed values {v1,v2,...} to scope [min(v), max(v)], |
| // set *exact_value = false (keep predicate as residual filter). |
| // - If not convertible (BOOLEAN etc.): stop extending (*should_break = true). |
| auto scan_keys_size = _begin_scan_keys.empty() ? 1 : _begin_scan_keys.size(); |
| if (range.is_fixed_value_range()) { |
| if (range.get_fixed_value_size() > max_scan_key_num / scan_keys_size) { |
| if (range.is_range_value_convertible()) { |
| range.convert_to_range_value(); |
| *exact_value = false; |
| } else { |
| *should_break = true; |
| return Status::OK(); |
| } |
| } |
| } else { |
| // 4. Range-splitting optimization: if this is the FIRST key column and it's a scope |
| // range on a splittable integer type, try to split [low, high] into multiple |
| // sub-ranges for parallel / pipelined scanning. |
| // e.g. k1 in [1, 100] with max_scan_key_num=4 → [(1,25), (26,50), (51,75), (76,100)] |
| if (_begin_scan_keys.empty() && range.is_fixed_value_convertible() && _is_convertible && |
| !range.is_reject_split_type()) { |
| *eos |= range.convert_to_close_range(_begin_scan_keys, _end_scan_keys, _begin_include, |
| _end_include); |
| |
| if (!(*eos) && |
| range.convert_to_avg_range_value(_begin_scan_keys, _end_scan_keys, _begin_include, |
| _end_include, max_scan_key_num)) { |
| _has_range_value = true; |
| } |
| return Status::OK(); |
| } |
| } |
| |
| // ==================================================================== |
| // 5. Actually extend scan keys with this column's values. |
| // ==================================================================== |
| |
| if (range.is_fixed_value_range()) { |
| // ---- 5a. Fixed values (IN / =): point lookup, begin == end per value. ---- |
| if (_begin_scan_keys.empty()) { |
| // First column: create one key pair per fixed value. |
| // e.g. k1 IN (1, 2) → _begin=[(1),(2)] _end=[(1),(2)] |
| auto fixed_value_set = range.get_fixed_value_set(); |
| ConstIterator iter = fixed_value_set.begin(); |
| |
| for (; iter != fixed_value_set.end(); ++iter) { |
| _begin_scan_keys.emplace_back(); |
| _begin_scan_keys.back().add_field(Field::create_field<primitive_type>(*iter)); |
| _end_scan_keys.emplace_back(); |
| _end_scan_keys.back().add_field(Field::create_field<primitive_type>(*iter)); |
| } |
| |
| if (range.contain_null()) { |
| _begin_scan_keys.emplace_back(); |
| _begin_scan_keys.back().add_null(); |
| _end_scan_keys.emplace_back(); |
| _end_scan_keys.back().add_null(); |
| } |
| } else { |
| // Subsequent column: Cartesian product of existing keys × new fixed values. |
| // e.g. existing = [(1),(2)], k2 IN (10, 20) |
| // → [(1,10),(1,20),(2,10),(2,20)] |
| auto fixed_value_set = range.get_fixed_value_set(); |
| size_t original_key_range_size = _begin_scan_keys.size(); |
| |
| for (int i = 0; i < original_key_range_size; ++i) { |
| OlapTuple start_base_key_range = _begin_scan_keys[i]; |
| OlapTuple end_base_key_range = _end_scan_keys[i]; |
| |
| ConstIterator iter = fixed_value_set.begin(); |
| |
| for (; iter != fixed_value_set.end(); ++iter) { |
| // Reuse i-th slot for the first value, append new slots for the rest. |
| if (iter == fixed_value_set.begin()) { |
| _begin_scan_keys[i].add_field(Field::create_field<primitive_type>(*iter)); |
| _end_scan_keys[i].add_field(Field::create_field<primitive_type>(*iter)); |
| } else { |
| _begin_scan_keys.push_back(start_base_key_range); |
| _begin_scan_keys.back().add_field( |
| Field::create_field<primitive_type>(*iter)); |
| _end_scan_keys.push_back(end_base_key_range); |
| _end_scan_keys.back().add_field(Field::create_field<primitive_type>(*iter)); |
| } |
| } |
| |
| if (range.contain_null()) { |
| _begin_scan_keys.push_back(start_base_key_range); |
| _begin_scan_keys.back().add_null(); |
| _end_scan_keys.push_back(end_base_key_range); |
| _end_scan_keys.back().add_null(); |
| } |
| } |
| } |
| |
| // Fixed values are always closed intervals (begin == end, point lookup). |
| _begin_include = true; |
| _end_include = true; |
| } else { |
| // ---- 5b. Scope range (> / >= / < / <=): append min to begin, max to end. ---- |
| // After this, no more columns can be appended (_has_range_value = true), |
| // because the range semantics only apply to the last appended column. |
| // e.g. existing = [(1),(2)], k2 >= 5 AND k2 < 10 |
| // → _begin = [(1,5),(2,5)] _end = [(1,10),(2,10)] |
| // → begin_include=true, end_include=false |
| _has_range_value = true; |
| |
| // Special case: max < min means the range itself is empty, |
| // but contain_null() is true, so only null values match this column. |
| if (Compare::less(range.get_range_max_value(), range.get_range_min_value())) { |
| CHECK(range.contain_null()); |
| if (_begin_scan_keys.empty()) { |
| _begin_scan_keys.emplace_back(); |
| _begin_scan_keys.back().add_null(); |
| _end_scan_keys.emplace_back(); |
| _end_scan_keys.back().add_null(); |
| } else { |
| for (int i = 0; i < _begin_scan_keys.size(); ++i) { |
| _begin_scan_keys[i].add_null(); |
| _end_scan_keys[i].add_null(); |
| } |
| } |
| } else if (_begin_scan_keys.empty()) { |
| // First column as a range: |
| // e.g. k1 >= 100 AND k1 <= 200 → _begin=[(100)] _end=[(200)] |
| _begin_scan_keys.emplace_back(); |
| if (range.contain_null()) { |
| _begin_scan_keys.back().add_null(); |
| } else { |
| _begin_scan_keys.back().add_field( |
| Field::create_field<primitive_type>(range.get_range_min_value())); |
| } |
| _end_scan_keys.emplace_back(); |
| _end_scan_keys.back().add_field( |
| Field::create_field<primitive_type>(range.get_range_max_value())); |
| } else { |
| // Subsequent column as a range: append min/max to every existing key pair. |
| for (int i = 0; i < _begin_scan_keys.size(); ++i) { |
| if (range.contain_null()) { |
| _begin_scan_keys[i].add_null(); |
| } else { |
| _begin_scan_keys[i].add_field( |
| Field::create_field<primitive_type>(range.get_range_min_value())); |
| } |
| } |
| |
| for (int i = 0; i < _end_scan_keys.size(); ++i) { |
| _end_scan_keys[i].add_field( |
| Field::create_field<primitive_type>(range.get_range_max_value())); |
| } |
| } |
| _begin_include = range.is_begin_include(); |
| _end_include = range.is_end_include(); |
| } |
| |
| return Status::OK(); |
| } |
| |
| } // namespace doris |
