You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by li...@apache.org on 2026/04/16 05:20:42 UTC
(doris) branch master updated: [Exec](set) use bitset container to speed up hash set (#62532)
This is an automated email from the ASF dual-hosted git repository.
lihaopeng 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 443158109a8 [Exec](set) use bitset container to speed up hash set (#62532)
443158109a8 is described below
commit 443158109a8c7ef1be9b732e8f9833d607979df1
Author: HappenLee <ha...@selectdb.com>
AuthorDate: Thu Apr 16 13:20:35 2026 +0800
[Exec](set) use bitset container to speed up hash set (#62532)
use bitset container to speed up hash set
```
before:
SELECT count() from hits_100m WHERE FlashMajor IN (0, 1, 2, 3, 4, 5)
+----------+
| count() |
+----------+
| 99997497 |
+----------+
1 row in set (0.411 sec)
after:
SELECT count() from hits_100m WHERE FlashMajor IN (0, 1, 2, 3, 4, 5)
+----------+
| count() |
+----------+
| 99997497 |
+----------+
1 row in set (0.36 sec)
```
---
be/src/exprs/bitset_container.h | 156 +++++++++++++++++++++++++++++++
be/src/exprs/create_predicate_function.h | 3 +
be/src/exprs/hybrid_set.h | 7 ++
3 files changed, 166 insertions(+)
diff --git a/be/src/exprs/bitset_container.h b/be/src/exprs/bitset_container.h
new file mode 100644
index 00000000000..a230d3b98eb
--- /dev/null
+++ b/be/src/exprs/bitset_container.h
@@ -0,0 +1,156 @@
+// 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 <array>
+#include <cstddef>
+#include <cstdint>
+#include <type_traits>
+#include <vector>
+
+#include "common/compiler_util.h"
+
+namespace doris {
+
+template <typename T>
+struct BitSetContainerTraits {
+ static constexpr size_t RANGE = 0;
+};
+
+template <>
+struct BitSetContainerTraits<int8_t> {
+ static constexpr size_t RANGE = 256;
+};
+
+template <>
+struct BitSetContainerTraits<int16_t> {
+ static constexpr size_t RANGE = 65536;
+};
+
+template <typename T>
+class BitSetContainer {
+public:
+ using Self = BitSetContainer;
+ using ElementType = T;
+
+ static_assert(std::is_same_v<T, int8_t> || std::is_same_v<T, int16_t>,
+ "BitSetContainer only supports int8_t or int16_t");
+
+ static constexpr size_t RANGE = BitSetContainerTraits<T>::RANGE;
+
+ class Iterator {
+ public:
+ explicit Iterator(const std::array<bool, RANGE>* data, size_t index)
+ : _data(data), _index(index) {
+ _find_next();
+ }
+
+ Iterator& operator++() {
+ ++_index;
+ _find_next();
+ return *this;
+ }
+
+ Iterator operator++(int) {
+ Iterator ret_val = *this;
+ ++(*this);
+ return ret_val;
+ }
+
+ bool operator==(Iterator other) const { return _index == other._index; }
+ bool operator!=(Iterator other) const { return !(*this == other); }
+
+ T operator*() const { return static_cast<T>(_index); }
+
+ T* operator->() const {
+ _cached_value = static_cast<T>(_index);
+ return &_cached_value;
+ }
+
+ using iterator_category = std::forward_iterator_tag;
+ using difference_type = std::ptrdiff_t;
+ using value_type = T;
+ using pointer = const T*;
+ using reference = const T&;
+
+ private:
+ void _find_next() {
+ while (_index < RANGE && !(*_data)[_index]) {
+ ++_index;
+ }
+ }
+
+ const std::array<bool, RANGE>* _data;
+ size_t _index;
+ mutable T _cached_value = T();
+ };
+
+ BitSetContainer() { _data.fill(false); }
+
+ ~BitSetContainer() = default;
+
+ ALWAYS_INLINE void insert(const T& value) {
+ auto idx = _to_index(value);
+ if (!_data[idx]) {
+ _data[idx] = true;
+ _size++;
+ }
+ }
+
+ ALWAYS_INLINE bool find(const T& value) const { return _data[_to_index(value)]; }
+
+ void clear() {
+ _data.fill(false);
+ _size = 0;
+ }
+
+ size_t size() const { return _size; }
+
+ Iterator begin() const { return Iterator(&_data, 0); }
+ Iterator end() const { return Iterator(&_data, RANGE); }
+
+ template <typename ColumnData>
+ void find_batch(const ColumnData& data, size_t rows, std::vector<bool>& results) const {
+ results.resize(rows);
+ for (size_t i = 0; i < rows; ++i) {
+ results[i] = find(data[i]);
+ }
+ }
+
+ template <typename ColumnData>
+ void find_batch(const ColumnData& data, size_t rows, std::vector<uint8_t>& results) const {
+ results.resize(rows);
+ for (size_t i = 0; i < rows; ++i) {
+ results[i] = find(data[i]) ? 1 : 0;
+ }
+ }
+
+private:
+ ALWAYS_INLINE constexpr size_t _to_index(T value) const {
+ if constexpr (std::is_same_v<T, int8_t>) {
+ return static_cast<uint8_t>(value);
+ } else {
+ return static_cast<uint16_t>(value);
+ }
+ }
+
+ std::array<bool, RANGE> _data;
+ size_t _size = 0;
+};
+
+} // namespace doris
\ No newline at end of file
diff --git a/be/src/exprs/create_predicate_function.h b/be/src/exprs/create_predicate_function.h
index ee8f3a5e927..41c45fce193 100644
--- a/be/src/exprs/create_predicate_function.h
+++ b/be/src/exprs/create_predicate_function.h
@@ -50,6 +50,9 @@ public:
static BasePtr get_function(bool null_aware) {
if constexpr (is_string_type(type)) {
return new StringSet<>(null_aware);
+ } else if constexpr (type == TYPE_TINYINT || type == TYPE_SMALLINT) {
+ using CppType = typename PrimitiveTypeTraits<type>::CppType;
+ return new HybridSet<type, BitSetContainer<CppType>>(null_aware);
} else if constexpr (N >= 1 && N <= FIXED_CONTAINER_MAX_SIZE) {
using CppType = typename PrimitiveTypeTraits<type>::CppType;
return new HybridSet<type, FixedContainer<CppType, N>>(null_aware);
diff --git a/be/src/exprs/hybrid_set.h b/be/src/exprs/hybrid_set.h
index 087e8265216..28e664043d5 100644
--- a/be/src/exprs/hybrid_set.h
+++ b/be/src/exprs/hybrid_set.h
@@ -27,6 +27,7 @@
#include "core/data_type/primitive_type.h"
#include "exec/common/hash_table/phmap_fwd_decl.h"
#include "exec/runtime_filter/utils.h"
+#include "exprs/bitset_container.h"
#include "exprs/filter_base.h"
namespace doris {
@@ -135,6 +136,12 @@ struct IsFixedContainer : std::false_type {};
template <typename T, size_t N>
struct IsFixedContainer<FixedContainer<T, N>> : std::true_type {};
+template <typename T>
+struct IsBitSetContainer : std::false_type {};
+
+template <typename T>
+struct IsBitSetContainer<BitSetContainer<T>> : std::true_type {};
+
/**
* Dynamic Container uses phmap::flat_hash_set.
* @tparam T Element Type
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org