/root/doris/be/src/olap/column_predicate.h

Source (jump to first uncovered line)
// 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 <roaring/roaring.hh>

#include "olap/rowset/segment_v2/bitmap_index_reader.h"
#include "olap/rowset/segment_v2/bloom_filter.h"
#include "olap/rowset/segment_v2/inverted_index_reader.h"
#include "olap/schema.h"
#include "olap/selection_vector.h"
#include "vec/columns/column.h"

using namespace doris::segment_v2;

namespace doris {

class Schema;

struct PredicateParams {
    std::vector<std::string> values;
    bool marked_by_runtime_filter = false;
};

enum class PredicateType {
    UNKNOWN = 0,
    EQ = 1,
    NE = 2,
    LT = 3,
    LE = 4,
    GT = 5,
    GE = 6,
    IN_LIST = 7,
    NOT_IN_LIST = 8,
    IS_NULL = 9,
    IS_NOT_NULL = 10,
    BF = 11,            // BloomFilter
    BITMAP_FILTER = 12, // BitmapFilter
    MATCH = 13,         // fulltext match
};

inline std::string type_to_string(PredicateType type) {
    switch (type) {
    case PredicateType::UNKNOWN:
        return "UNKNOWN";

    case PredicateType::EQ:
        return "EQ";

    case PredicateType::NE:
        return "NE";

    case PredicateType::LT:
        return "LT";

    case PredicateType::LE:
        return "LE";

    case PredicateType::GT:
        return "GT";

    case PredicateType::GE:
        return "GE";

    case PredicateType::IN_LIST:
        return "IN_LIST";

    case PredicateType::NOT_IN_LIST:
        return "NOT_IN_LIST";

    case PredicateType::IS_NULL:
        return "IS_NULL";

    case PredicateType::IS_NOT_NULL:
        return "IS_NOT_NULL";

    case PredicateType::BF:
        return "BF";
    default:
        return "";
    };

    return "";
}

struct PredicateTypeTraits {
    static constexpr bool is_range(PredicateType type) {
        return (type == PredicateType::LT || type == PredicateType::LE ||
                type == PredicateType::GT || type == PredicateType::GE);
    }

    static constexpr bool is_bloom_filter(PredicateType type) { return type == PredicateType::BF; }

    static constexpr bool is_list(PredicateType type) {
        return (type == PredicateType::IN_LIST || type == PredicateType::NOT_IN_LIST);
    }

    static constexpr bool is_equal_or_list(PredicateType type) {
        return (type == PredicateType::EQ || type == PredicateType::IN_LIST);
    }

    static constexpr bool is_comparison(PredicateType type) {
        return (type == PredicateType::EQ || type == PredicateType::NE ||
                type == PredicateType::LT || type == PredicateType::LE ||
                type == PredicateType::GT || type == PredicateType::GE);
    }
};

#define EVALUATE_BY_SELECTOR(EVALUATE_IMPL_WITH_NULL_MAP, EVALUATE_IMPL_WITHOUT_NULL_MAP) \
    const bool is_dense_column = pred_col.size() == size;                                 \
    for (uint16_t i = 0; i < size; i++) {                                                 \
        uint16_t idx = is_dense_column ? i : sel[i];                                      \
        if constexpr (is_nullable) {                                                      \
            if (EVALUATE_IMPL_WITH_NULL_MAP(idx)) {                                       \
                sel[new_size++] = idx;                                                    \
            }                                                                             \
        } else {                                                                          \
            if (EVALUATE_IMPL_WITHOUT_NULL_MAP(idx)) {                                    \
                sel[new_size++] = idx;                                                    \
            }                                                                             \
        }                                                                                 \
    }

class ColumnPredicate {
public:
    explicit ColumnPredicate(uint32_t column_id, bool opposite = false)
            : _column_id(column_id), _opposite(opposite) {
        _predicate_params = std::make_shared<PredicateParams>();
    }

    virtual ~ColumnPredicate() = default;

    virtual PredicateType type() const = 0;

    //evaluate predicate on Bitmap
    virtual Status evaluate(BitmapIndexIterator* iterator, uint32_t num_rows,
                            roaring::Roaring* roaring) const = 0;

    //evaluate predicate on inverted
    virtual Status evaluate(const Schema& schema, InvertedIndexIterator* iterator,
                            uint32_t num_rows, roaring::Roaring* bitmap) const {
        return Status::NotSupported(
                "Not Implemented evaluate with inverted index, please check the predicate");
    }

    // evaluate predicate on IColumn
    // a short circuit eval way
    virtual uint16_t evaluate(const vectorized::IColumn& column, uint16_t* sel,
                              uint16_t size) const {
        return size;
    }
    virtual void evaluate_and(const vectorized::IColumn& column, const uint16_t* sel, uint16_t size,
                              bool* flags) const {}
    virtual void evaluate_or(const vectorized::IColumn& column, const uint16_t* sel, uint16_t size,
                             bool* flags) const {}

    virtual bool support_zonemap() const { return true; }

    virtual bool evaluate_and(const std::pair<WrapperField*, WrapperField*>& statistic) const {
        return true;
    }

    virtual bool is_always_true(const std::pair<WrapperField*, WrapperField*>& statistic) const {
        return false;
    }

    virtual bool evaluate_del(const std::pair<WrapperField*, WrapperField*>& statistic) const {
        return false;
    }

    virtual bool evaluate_and(const BloomFilter* bf) const { return true; }

    virtual bool evaluate_and(const StringRef* dict_words, const size_t dict_count) const {
        return true;
    }

    virtual bool can_do_bloom_filter(bool ngram) const { return false; }

    // used to evaluate pre read column in lazy materialization
    // now only support integer/float
    // a vectorized eval way
    virtual void evaluate_vec(const vectorized::IColumn& column, uint16_t size, bool* flags) const {
        DCHECK(false) << "should not reach here";
    }
    virtual void evaluate_and_vec(const vectorized::IColumn& column, uint16_t size,
                                  bool* flags) const {
        DCHECK(false) << "should not reach here";
    }

    virtual std::string get_search_str() const {
        DCHECK(false) << "should not reach here";
        return "";
    }

    virtual void set_page_ng_bf(std::unique_ptr<segment_v2::BloomFilter>) {
        DCHECK(false) << "should not reach here";
    }
    uint32_t column_id() const { return _column_id; }

    bool opposite() const { return _opposite; }

    virtual std::string debug_string() const {
        return _debug_string() + ", column_id=" + std::to_string(_column_id) +
               ", opposite=" + (_opposite ? "true" : "false");
    }

    /// Some predicates need to be cloned for each segment.
    virtual bool need_to_clone() const { return false; }

    virtual void clone(ColumnPredicate** to) const { LOG(FATAL) << "clone not supported"; }

    virtual int get_filter_id() const { return -1; }
    // now InListPredicateBase BloomFilterColumnPredicate BitmapFilterColumnPredicate  = true
    virtual bool is_filter() const { return false; }
    PredicateFilterInfo get_filtered_info() const {
        return PredicateFilterInfo {static_cast<int>(type()), _evaluated_rows - 1,
                                    _evaluated_rows - 1 - _passed_rows};
    }

    std::shared_ptr<PredicateParams> predicate_params() { return _predicate_params; }

    const std::string pred_type_string(PredicateType type) {
        switch (type) {
        case PredicateType::EQ:
            return "eq";
        case PredicateType::NE:
            return "ne";
        case PredicateType::LT:
            return "lt";
        case PredicateType::LE:
            return "le";
        case PredicateType::GT:
            return "gt";
        case PredicateType::GE:
            return "ge";
        case PredicateType::IN_LIST:
            return "in";
        case PredicateType::NOT_IN_LIST:
            return "not_in";
        case PredicateType::IS_NULL:
            return "is_null";
        case PredicateType::IS_NOT_NULL:
            return "is_not_null";
        case PredicateType::BF:
            return "bf";
        case PredicateType::MATCH:
            return "match";
        default:
            return "unknown";
        }
    }

protected:
    // Just prevent access not align memory address coredump
    template <class T>
    T _get_zone_map_value(void* data_ptr) const {
        T res;
        memcpy(&res, data_ptr, sizeof(T));
        return res;
    }

    virtual std::string _debug_string() const = 0;

    uint32_t _column_id;
    // TODO: the value is only in delete condition, better be template value
    bool _opposite;
    std::shared_ptr<PredicateParams> _predicate_params;
    mutable uint64_t _evaluated_rows = 1;
    mutable uint64_t _passed_rows = 0;
};

} //namespace doris

Coverage Report

Created: 2024-11-18 10:37

Line	Count	Source (jump to first uncovered line)
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		#pragma once
19
20		#include <roaring/roaring.hh>
21
22		#include "olap/rowset/segment_v2/bitmap_index_reader.h"
23		#include "olap/rowset/segment_v2/bloom_filter.h"
24		#include "olap/rowset/segment_v2/inverted_index_reader.h"
25		#include "olap/schema.h"
26		#include "olap/selection_vector.h"
27		#include "vec/columns/column.h"
28
29		using namespace doris::segment_v2;
30
31		namespace doris {
32
33		class Schema;
34
35		struct PredicateParams {
36		std::vector<std::string> values;
37		bool marked_by_runtime_filter = false;
38		};
39
40		enum class PredicateType {
41		UNKNOWN = 0,
42		EQ = 1,
43		NE = 2,
44		LT = 3,
45		LE = 4,
46		GT = 5,
47		GE = 6,
48		IN_LIST = 7,
49		NOT_IN_LIST = 8,
50		IS_NULL = 9,
51		IS_NOT_NULL = 10,
52		BF = 11, // BloomFilter
53		BITMAP_FILTER = 12, // BitmapFilter
54		MATCH = 13, // fulltext match
55		};
56
57	0	inline std::string type_to_string(PredicateType type) {
58	0	switch (type) {
59	0	case PredicateType::UNKNOWN:
60	0	return "UNKNOWN";
61
62	0	case PredicateType::EQ:
63	0	return "EQ";
64
65	0	case PredicateType::NE:
66	0	return "NE";
67
68	0	case PredicateType::LT:
69	0	return "LT";
70
71	0	case PredicateType::LE:
72	0	return "LE";
73
74	0	case PredicateType::GT:
75	0	return "GT";
76
77	0	case PredicateType::GE:
78	0	return "GE";
79
80	0	case PredicateType::IN_LIST:
81	0	return "IN_LIST";
82
83	0	case PredicateType::NOT_IN_LIST:
84	0	return "NOT_IN_LIST";
85
86	0	case PredicateType::IS_NULL:
87	0	return "IS_NULL";
88
89	0	case PredicateType::IS_NOT_NULL:
90	0	return "IS_NOT_NULL";
91
92	0	case PredicateType::BF:
93	0	return "BF";
94	0	default:
95	0	return "";
96	0	};
97
98	0	return "";
99	0	}
100
101		struct PredicateTypeTraits {
102	347	static constexpr bool is_range(PredicateType type) {
103	347	return (type == PredicateType::LT \|\| type == PredicateType::LE \|\|
104	347	type == PredicateType::GT \|\| type == PredicateType::GE);
105	347	}
106
107	20	static constexpr bool is_bloom_filter(PredicateType type) { return type == PredicateType::BF; }
108
109	0	static constexpr bool is_list(PredicateType type) {
110	0	return (type == PredicateType::IN_LIST \|\| type == PredicateType::NOT_IN_LIST);
111	0	}
112
113	0	static constexpr bool is_equal_or_list(PredicateType type) {
114	0	return (type == PredicateType::EQ \|\| type == PredicateType::IN_LIST);
115	0	}
116
117	0	static constexpr bool is_comparison(PredicateType type) {
118	0	return (type == PredicateType::EQ \|\| type == PredicateType::NE \|\|
119	0	type == PredicateType::LT \|\| type == PredicateType::LE \|\|
120	0	type == PredicateType::GT \|\| type == PredicateType::GE);
121	0	}
122		};
123
124		#define EVALUATE_BY_SELECTOR(EVALUATE_IMPL_WITH_NULL_MAP, EVALUATE_IMPL_WITHOUT_NULL_MAP) \
125	1.58k	const bool is_dense_column = pred_col.size() == size; \
126	3.90M	for (uint16_t i = 0; i < size; i++) { \
127	3.90M	uint16_t idx = is_dense_column ? i : sel[i]; \
128	3.90M	if constexpr (is_nullable) { \
129	4.00k	if (EVALUATE_IMPL_WITH_NULL_MAP(idx)) { \
130	3.61k	sel[new_size++] = idx; \
131	3.61k	} \
132	3.89M	} else { \
133	3.89M	if (EVALUATE_IMPL_WITHOUT_NULL_MAP(idx)) { \
134	3.82M	sel[new_size++] = idx; \
135	3.82M	} \
136	3.89M	} \
137	3.90M	}
138
139		class ColumnPredicate {
140		public:
141		explicit ColumnPredicate(uint32_t column_id, bool opposite = false)
142	111	: _column_id(column_id), _opposite(opposite) {
143	111	_predicate_params = std::make_shared<PredicateParams>();
144	111	}
145
146	111	virtual ~ColumnPredicate() = default;
147
148		virtual PredicateType type() const = 0;
149
150		//evaluate predicate on Bitmap
151		virtual Status evaluate(BitmapIndexIterator* iterator, uint32_t num_rows,
152		roaring::Roaring* roaring) const = 0;
153
154		//evaluate predicate on inverted
155		virtual Status evaluate(const Schema& schema, InvertedIndexIterator* iterator,
156	0	uint32_t num_rows, roaring::Roaring* bitmap) const {
157	0	return Status::NotSupported(
158	0	"Not Implemented evaluate with inverted index, please check the predicate");
159	0	}
160
161		// evaluate predicate on IColumn
162		// a short circuit eval way
163		virtual uint16_t evaluate(const vectorized::IColumn& column, uint16_t* sel,
164	0	uint16_t size) const {
165	0	return size;
166	0	}
167		virtual void evaluate_and(const vectorized::IColumn& column, const uint16_t* sel, uint16_t size,
168	0	bool* flags) const {}
169		virtual void evaluate_or(const vectorized::IColumn& column, const uint16_t* sel, uint16_t size,
170	0	bool* flags) const {}
171
172	0	virtual bool support_zonemap() const { return true; }
173
174	0	virtual bool evaluate_and(const std::pair<WrapperField, WrapperField>& statistic) const {
175	0	return true;
176	0	}
177
178	0	virtual bool is_always_true(const std::pair<WrapperField, WrapperField>& statistic) const {
179	0	return false;
180	0	}
181
182	0	virtual bool evaluate_del(const std::pair<WrapperField, WrapperField>& statistic) const {
183	0	return false;
184	0	}
185
186	0	virtual bool evaluate_and(const BloomFilter* bf) const { return true; }
187
188	0	virtual bool evaluate_and(const StringRef* dict_words, const size_t dict_count) const {
189	0	return true;
190	0	}
191
192	0	virtual bool can_do_bloom_filter(bool ngram) const { return false; }
193
194		// used to evaluate pre read column in lazy materialization
195		// now only support integer/float
196		// a vectorized eval way
197	0	virtual void evaluate_vec(const vectorized::IColumn& column, uint16_t size, bool* flags) const {
198	0	DCHECK(false) << "should not reach here";
199	0	}
200		virtual void evaluate_and_vec(const vectorized::IColumn& column, uint16_t size,
201	0	bool* flags) const {
202	0	DCHECK(false) << "should not reach here";
203	0	}
204
205	0	virtual std::string get_search_str() const {
206	0	DCHECK(false) << "should not reach here";
207	0	return "";
208	0	}
209
210	0	virtual void set_page_ng_bf(std::unique_ptr<segment_v2::BloomFilter>) {
211	0	DCHECK(false) << "should not reach here";
212	0	}
213	6.49k	uint32_t column_id() const { return _column_id; }
214
215	0	bool opposite() const { return _opposite; }
216
217	0	virtual std::string debug_string() const {
218	0	return _debug_string() + ", column_id=" + std::to_string(_column_id) +
219	0	", opposite=" + (_opposite ? "true" : "false");
220	0	}
221
222		/// Some predicates need to be cloned for each segment.
223	0	virtual bool need_to_clone() const { return false; }
224
225	0	virtual void clone(ColumnPredicate** to) const { LOG(FATAL) << "clone not supported"; }
226
227	0	virtual int get_filter_id() const { return -1; }
228		// now InListPredicateBase BloomFilterColumnPredicate BitmapFilterColumnPredicate = true
229	0	virtual bool is_filter() const { return false; }
230	0	PredicateFilterInfo get_filtered_info() const {
231	0	return PredicateFilterInfo {static_cast<int>(type()), _evaluated_rows - 1,
232	0	_evaluated_rows - 1 - _passed_rows};
233	0	}
234
235	0	std::shared_ptr<PredicateParams> predicate_params() { return _predicate_params; }
236
237	0	const std::string pred_type_string(PredicateType type) {
238	0	switch (type) {
239	0	case PredicateType::EQ:
240	0	return "eq";
241	0	case PredicateType::NE:
242	0	return "ne";
243	0	case PredicateType::LT:
244	0	return "lt";
245	0	case PredicateType::LE:
246	0	return "le";
247	0	case PredicateType::GT:
248	0	return "gt";
249	0	case PredicateType::GE:
250	0	return "ge";
251	0	case PredicateType::IN_LIST:
252	0	return "in";
253	0	case PredicateType::NOT_IN_LIST:
254	0	return "not_in";
255	0	case PredicateType::IS_NULL:
256	0	return "is_null";
257	0	case PredicateType::IS_NOT_NULL:
258	0	return "is_not_null";
259	0	case PredicateType::BF:
260	0	return "bf";
261	0	case PredicateType::MATCH:
262	0	return "match";
263	0	default:
264	0	return "unknown";
265	0	}
266	0	}
267
268		protected:
269		// Just prevent access not align memory address coredump
270		template <class T>
271	0	T _get_zone_map_value(void* data_ptr) const {
272	0	T res;
273	0	memcpy(&res, data_ptr, sizeof(T));
274	0	return res;
275	0	} Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueIiEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueIaEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueIsEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueIlEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueInEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueIfEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueIdEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueINS_11decimal12_tEEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueINS_9StringRefEEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueIjEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueImEET_Pv Unexecuted instantiation: _ZNK5doris15ColumnPredicate19_get_zone_map_valueIbEET_Pv
276
277		virtual std::string _debug_string() const = 0;
278
279		uint32_t _column_id;
280		// TODO: the value is only in delete condition, better be template value
281		bool _opposite;
282		std::shared_ptr<PredicateParams> _predicate_params;
283		mutable uint64_t _evaluated_rows = 1;
284		mutable uint64_t _passed_rows = 0;
285		};
286
287		} //namespace doris