This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new a724443eb9 [Improvement](predicate) optimize short-circuit predicates
(#18278)
a724443eb9 is described below
commit a724443eb92a84a2c0167033cf08ec95b1369d96
Author: Gabriel <[email protected]>
AuthorDate: Tue Apr 4 10:21:41 2023 +0800
[Improvement](predicate) optimize short-circuit predicates (#18278)
For scan node with no vectorized predicate, the input column for the first
short-circuit predicate is dense and we don't need to access the selector
column.
This PR improve performance by ~30% on TPCH Q3.
---
be/src/exprs/block_bloom_filter.hpp | 2 +-
be/src/exprs/bloom_filter_func.h | 59 ++++++++++++++++++++++++++++--------
be/src/olap/bloom_filter_predicate.h | 36 ++++++++++------------
be/src/olap/column_predicate.h | 15 +++++++++
be/src/olap/comparison_predicate.h | 49 ++++++++++++++----------------
be/src/olap/in_list_predicate.h | 42 +++++++++----------------
be/src/olap/null_predicate.cpp | 13 ++++----
7 files changed, 123 insertions(+), 93 deletions(-)
diff --git a/be/src/exprs/block_bloom_filter.hpp
b/be/src/exprs/block_bloom_filter.hpp
index 2dd6e3cb4f..2a9be09981 100644
--- a/be/src/exprs/block_bloom_filter.hpp
+++ b/be/src/exprs/block_bloom_filter.hpp
@@ -195,7 +195,7 @@ private:
static constexpr uint32_t kRehash[8] __attribute__((aligned(32))) =
{BLOOM_HASH_CONSTANTS};
// Get 32 more bits of randomness from a 32-bit hash:
- static uint32_t rehash32to32(const uint32_t hash) {
+ static ALWAYS_INLINE uint32_t rehash32to32(const uint32_t hash) {
// Constants generated by uuidgen(1) with the -r flag
static constexpr uint64_t m = 0x7850f11ec6d14889ULL;
static constexpr uint64_t a = 0x6773610597ca4c63ULL;
diff --git a/be/src/exprs/bloom_filter_func.h b/be/src/exprs/bloom_filter_func.h
index 7b9236f39a..d127a4c19b 100644
--- a/be/src/exprs/bloom_filter_func.h
+++ b/be/src/exprs/bloom_filter_func.h
@@ -184,7 +184,8 @@ public:
virtual void insert_fixed_len(const char* data) = 0;
virtual uint16_t find_fixed_len_olap_engine(const char* data, const uint8*
nullmap,
- uint16_t* offsets, int number)
= 0;
+ uint16_t* offsets, int number,
+ bool is_parse_column) = 0;
virtual void find_fixed_len(const char* data, const uint8* nullmap, int
number,
uint8* results) = 0;
@@ -213,17 +214,49 @@ struct CommonFindOp {
}
uint16_t find_batch_olap_engine(const BloomFilterAdaptor& bloom_filter,
const char* data,
- const uint8* nullmap, uint16_t* offsets,
int number) const {
+ const uint8* nullmap, uint16_t* offsets,
int number,
+ const bool is_parse_column) const {
uint16_t new_size = 0;
- for (int i = 0; i < number; i++) {
- uint16_t idx = offsets[i];
- if (nullmap != nullptr && nullmap[idx]) {
- continue;
+ if (is_parse_column) {
+ if (nullmap == nullptr) {
+ for (int i = 0; i < number; i++) {
+ uint16_t idx = offsets[i];
+ if (!bloom_filter.test_element(*((T*)data + idx))) {
+ continue;
+ }
+ offsets[new_size++] = idx;
+ }
+ } else {
+ for (int i = 0; i < number; i++) {
+ uint16_t idx = offsets[i];
+ if (nullmap[idx]) {
+ continue;
+ }
+ if (!bloom_filter.test_element(*((T*)data + idx))) {
+ continue;
+ }
+ offsets[new_size++] = idx;
+ }
}
- if (!bloom_filter.test_element(*((T*)data + idx))) {
- continue;
+ } else {
+ if (nullmap == nullptr) {
+ for (int i = 0; i < number; i++) {
+ if (!bloom_filter.test_element(*((T*)data + i))) {
+ continue;
+ }
+ offsets[new_size++] = i;
+ }
+ } else {
+ for (int i = 0; i < number; i++) {
+ if (nullmap[i]) {
+ continue;
+ }
+ if (!bloom_filter.test_element(*((T*)data + i))) {
+ continue;
+ }
+ offsets[new_size++] = i;
+ }
}
- offsets[new_size++] = idx;
}
return new_size;
}
@@ -267,7 +300,8 @@ struct StringFindOp {
}
uint16_t find_batch_olap_engine(const BloomFilterAdaptor& bloom_filter,
const char* data,
- const uint8* nullmap, uint16_t* offsets,
int number) const {
+ const uint8* nullmap, uint16_t* offsets,
int number,
+ const bool is_parse_column) const {
LOG(FATAL) << "StringFindOp does not support find_batch_olap_engine";
return 0;
}
@@ -414,8 +448,9 @@ public:
}
uint16_t find_fixed_len_olap_engine(const char* data, const uint8*
nullmap, uint16_t* offsets,
- int number) override {
- return dummy.find_batch_olap_engine(*_bloom_filter, data, nullmap,
offsets, number);
+ int number, const bool
is_parse_column) override {
+ return dummy.find_batch_olap_engine(*_bloom_filter, data, nullmap,
offsets, number,
+ is_parse_column);
}
void find_fixed_len(const char* data, const uint8* nullmap, int number,
diff --git a/be/src/olap/bloom_filter_predicate.h
b/be/src/olap/bloom_filter_predicate.h
index 986fc0211f..d845871393 100644
--- a/be/src/olap/bloom_filter_predicate.h
+++ b/be/src/olap/bloom_filter_predicate.h
@@ -76,13 +76,13 @@ private:
}
}
} else if (IRuntimeFilter::enable_use_batch(_be_exec_version, T)) {
- new_size = _specific_filter->find_fixed_len_olap_engine(
- (char*)reinterpret_cast<
+ const auto& data =
+ reinterpret_cast<
const
vectorized::PredicateColumnType<PredicateEvaluateType<T>>*>(
&column)
- ->get_data()
- .data(),
- null_map, sel, size);
+ ->get_data();
+ new_size =
_specific_filter->find_fixed_len_olap_engine((char*)data.data(), null_map,
+ sel, size,
data.size() != size);
} else {
uint24_t tmp_uint24_value;
auto get_cell_value = [&tmp_uint24_value](auto& data) {
@@ -95,24 +95,20 @@ private:
}
};
- auto pred_col_data =
+ auto& pred_col =
reinterpret_cast<
const
vectorized::PredicateColumnType<PredicateEvaluateType<T>>*>(
&column)
- ->get_data()
- .data();
- for (uint16_t i = 0; i < size; i++) {
- uint16_t idx = sel[i];
- sel[new_size] = idx;
-
- if constexpr (is_nullable) {
- new_size += !null_map[idx] &&
_specific_filter->find_olap_engine(
-
get_cell_value(pred_col_data[idx]));
- } else {
- new_size +=
-
_specific_filter->find_olap_engine(get_cell_value(pred_col_data[idx]));
- }
- }
+ ->get_data();
+
+ auto pred_col_data = pred_col.data();
+#define EVALUATE_WITH_NULL_IMPL(IDX) \
+ !null_map[IDX] &&
_specific_filter->find_olap_engine(get_cell_value(pred_col_data[IDX]))
+#define EVALUATE_WITHOUT_NULL_IMPL(IDX) \
+ _specific_filter->find_olap_engine(get_cell_value(pred_col_data[IDX]))
+ EVALUATE_BY_SELECTOR(EVALUATE_WITH_NULL_IMPL,
EVALUATE_WITHOUT_NULL_IMPL)
+#undef EVALUATE_WITH_NULL_IMPL
+#undef EVALUATE_WITHOUT_NULL_IMPL
}
return new_size;
}
diff --git a/be/src/olap/column_predicate.h b/be/src/olap/column_predicate.h
index 824b65a07d..a7553740e8 100644
--- a/be/src/olap/column_predicate.h
+++ b/be/src/olap/column_predicate.h
@@ -121,6 +121,21 @@ struct PredicateTypeTraits {
}
};
+#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)
diff --git a/be/src/olap/comparison_predicate.h
b/be/src/olap/comparison_predicate.h
index 5bc9115399..e2b85f38b5 100644
--- a/be/src/olap/comparison_predicate.h
+++ b/be/src/olap/comparison_predicate.h
@@ -504,25 +504,6 @@ private:
}
}
- template <bool is_nullable, typename TArray, typename TValue>
- uint16_t _base_loop(uint16_t* sel, uint16_t size, const uint8_t*
__restrict null_map,
- const TArray* __restrict data_array, const TValue&
value) const {
- uint16_t new_size = 0;
- for (uint16_t i = 0; i < size; ++i) {
- uint16_t idx = sel[i];
- if constexpr (is_nullable) {
- if (_opposite ^ (!null_map[idx] && _operator(data_array[idx],
value))) {
- sel[new_size++] = idx;
- }
- } else {
- if (_opposite ^ _operator(data_array[idx], value)) {
- sel[new_size++] = idx;
- }
- }
- }
- return new_size;
- }
-
template <bool is_nullable>
uint16_t _base_evaluate(const vectorized::IColumn* column, const uint8_t*
null_map,
uint16_t* sel, uint16_t size) const {
@@ -530,7 +511,8 @@ private:
if constexpr (std::is_same_v<T, StringRef>) {
auto* dict_column_ptr =
vectorized::check_and_get_column<vectorized::ColumnDictI32>(column);
- auto* data_array = dict_column_ptr->get_data().data();
+ auto& pred_col = dict_column_ptr->get_data();
+ auto pred_col_data = pred_col.data();
auto dict_code =
_find_code_from_dictionary_column(*dict_column_ptr);
if constexpr (PT == PredicateType::EQ) {
@@ -538,20 +520,33 @@ private:
return _opposite ? size : 0;
}
}
-
- return _base_loop<is_nullable>(sel, size, null_map,
data_array, dict_code);
+ uint16_t new_size = 0;
+#define EVALUATE_WITH_NULL_IMPL(IDX) \
+ _opposite ^ (!null_map[IDX] && _operator(pred_col_data[IDX], dict_code))
+#define EVALUATE_WITHOUT_NULL_IMPL(IDX) _opposite ^
_operator(pred_col_data[IDX], dict_code)
+ EVALUATE_BY_SELECTOR(EVALUATE_WITH_NULL_IMPL,
EVALUATE_WITHOUT_NULL_IMPL)
+#undef EVALUATE_WITH_NULL_IMPL
+#undef EVALUATE_WITHOUT_NULL_IMPL
+
+ return new_size;
} else {
LOG(FATAL) << "column_dictionary must use StringRef
predicate.";
return 0;
}
} else {
- auto* data_array =
+ auto& pred_col =
vectorized::check_and_get_column<
vectorized::PredicateColumnType<PredicateEvaluateType<Type>>>(column)
- ->get_data()
- .data();
-
- return _base_loop<is_nullable>(sel, size, null_map, data_array,
_value);
+ ->get_data();
+ auto pred_col_data = pred_col.data();
+ uint16_t new_size = 0;
+#define EVALUATE_WITH_NULL_IMPL(IDX) \
+ _opposite ^ (!null_map[IDX] && _operator(pred_col_data[IDX], _value))
+#define EVALUATE_WITHOUT_NULL_IMPL(IDX) _opposite ^
_operator(pred_col_data[IDX], _value)
+ EVALUATE_BY_SELECTOR(EVALUATE_WITH_NULL_IMPL,
EVALUATE_WITHOUT_NULL_IMPL)
+#undef EVALUATE_WITH_NULL_IMPL
+#undef EVALUATE_WITHOUT_NULL_IMPL
+ return new_size;
}
}
diff --git a/be/src/olap/in_list_predicate.h b/be/src/olap/in_list_predicate.h
index 81ba744935..ac8bd3859c 100644
--- a/be/src/olap/in_list_predicate.h
+++ b/be/src/olap/in_list_predicate.h
@@ -447,33 +447,21 @@ private:
LOG(FATAL) << "column_dictionary must use StringRef
predicate.";
}
} else {
- auto* nested_col_ptr = vectorized::check_and_get_column<
-
vectorized::PredicateColumnType<PredicateEvaluateType<Type>>>(column);
- auto& data_array = nested_col_ptr->get_data();
-
- for (uint16_t i = 0; i < size; i++) {
- uint16_t idx = sel[i];
- if constexpr (is_nullable) {
- if ((*null_map)[idx]) {
- if constexpr (is_opposite) {
- sel[new_size++] = idx;
- }
- continue;
- }
- }
-
- if constexpr (!is_opposite) {
- if (_operator(_values->find(reinterpret_cast<const
T*>(&data_array[idx])),
- false)) {
- sel[new_size++] = idx;
- }
- } else {
- if (!_operator(_values->find(reinterpret_cast<const
T*>(&data_array[idx])),
- false)) {
- sel[new_size++] = idx;
- }
- }
- }
+ auto& pred_col =
+ vectorized::check_and_get_column<
+
vectorized::PredicateColumnType<PredicateEvaluateType<Type>>>(column)
+ ->get_data();
+ auto pred_col_data = pred_col.data();
+
+#define EVALUATE_WITH_NULL_IMPL(IDX) \
+ is_opposite ^ \
+ (!(*null_map)[IDX] && \
+ _operator(_values->find(reinterpret_cast<const
T*>(&pred_col_data[IDX])), false))
+#define EVALUATE_WITHOUT_NULL_IMPL(IDX) \
+ is_opposite ^ _operator(_values->find(reinterpret_cast<const
T*>(&pred_col_data[IDX])), false)
+ EVALUATE_BY_SELECTOR(EVALUATE_WITH_NULL_IMPL,
EVALUATE_WITHOUT_NULL_IMPL)
+#undef EVALUATE_WITH_NULL_IMPL
+#undef EVALUATE_WITHOUT_NULL_IMPL
}
return new_size;
}
diff --git a/be/src/olap/null_predicate.cpp b/be/src/olap/null_predicate.cpp
index c0cc938be8..fe081d9be4 100644
--- a/be/src/olap/null_predicate.cpp
+++ b/be/src/olap/null_predicate.cpp
@@ -53,12 +53,13 @@ uint16_t NullPredicate::evaluate(const vectorized::IColumn&
column, uint16_t* se
if (!nullable->has_null()) {
return _is_null ? 0 : size;
}
- auto& null_map = nullable->get_null_map_data();
- for (uint16_t i = 0; i < size; ++i) {
- uint16_t idx = sel[i];
- sel[new_size] = idx;
- new_size += (null_map[idx] == _is_null);
- }
+ auto& pred_col = nullable->get_null_map_data();
+ constexpr bool is_nullable = true;
+#define EVALUATE_WITH_NULL_IMPL(IDX) pred_col[IDX] == _is_null
+#define EVALUATE_WITHOUT_NULL_IMPL(IDX) true
+ EVALUATE_BY_SELECTOR(EVALUATE_WITH_NULL_IMPL,
EVALUATE_WITHOUT_NULL_IMPL)
+#undef EVALUATE_WITH_NULL_IMPL
+#undef EVALUATE_WITHOUT_NULL_IMPL
return new_size;
} else {
if (_is_null) return 0;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
