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 e5793249cd [opt](hashtable) Modify default filled strategy to 75% 
(#18242)
e5793249cd is described below

commit e5793249cd6479beae073b9b5cb61b25bf19cd7e
Author: Xinyi Zou <[email protected]>
AuthorDate: Fri Mar 31 09:28:11 2023 +0800

    [opt](hashtable) Modify default filled strategy to 75% (#18242)
---
 be/CMakeLists.txt                              |   8 -
 be/src/common/config.h                         |   9 +
 be/src/vec/common/hash_table/hash_table.h      |  35 +-
 be/src/vec/common/hash_table/join_hash_map.h   | 133 -----
 be/src/vec/common/hash_table/join_hash_table.h | 733 -------------------------
 be/src/vec/exec/join/vhash_join_node.cpp       |   9 +-
 build.sh                                       |   5 -
 run-be-ut.sh                                   |   1 -
 8 files changed, 34 insertions(+), 899 deletions(-)

diff --git a/be/CMakeLists.txt b/be/CMakeLists.txt
index 18b058badd..8bb1100c51 100644
--- a/be/CMakeLists.txt
+++ b/be/CMakeLists.txt
@@ -564,14 +564,6 @@ if (USE_BTHREAD_SCANNER)
     set(CXX_COMMON_FLAGS "${CXX_COMMON_FLAGS} -DUSE_BTHREAD_SCANNER")
 endif()
 
-# STRICT_MEMORY_USE=ON` expects BE to use less memory, and gives priority to 
ensuring stability
-# when the cluster memory is limited.
-# TODO In the future, expect a dynamic soft memory limit, combined with 
real-time memory usage of the cluster,
-# to control the main memory consumers, including HashTable, LRU Cache 
elimination strategy,
-# ChunkAllocator cache strategy, Disk IO buffer cache strategy, etc.
-if (STRICT_MEMORY_USE)
-    add_compile_options(-DSTRICT_MEMORY_USE)
-endif()
 if (ENABLE_STACKTRACE)
     add_compile_options(-DENABLE_STACKTRACE)
 endif()
diff --git a/be/src/common/config.h b/be/src/common/config.h
index 1d899eccd8..dbc9887d08 100644
--- a/be/src/common/config.h
+++ b/be/src/common/config.h
@@ -67,6 +67,15 @@ CONF_String(mem_limit, "auto");
 // Soft memory limit as a fraction of hard memory limit.
 CONF_Double(soft_mem_limit_frac, "0.9");
 
+// When hash table capacity is greater than 2^double_grow_degree(default 2G), 
grow when 75% of the capacity is satisfied.
+// Increase can reduce the number of hash table resize, but may waste more 
memory.
+CONF_mInt32(hash_table_double_grow_degree, "31");
+
+// Expand the hash table before inserting data, the maximum expansion size.
+// There are fewer duplicate keys, reducing the number of resize hash tables
+// There are many duplicate keys, and the hash table filled bucket is far less 
than the hash table build bucket.
+CONF_mInt64(hash_table_pre_expanse_max_rows, "65535");
+
 // The maximum low water mark of the system `/proc/meminfo/MemAvailable`, Unit 
byte, default 1.6G,
 // actual low water mark=min(1.6G, MemTotal * 10%), avoid wasting too much 
memory on machines
 // with large memory larger than 16G.
diff --git a/be/src/vec/common/hash_table/hash_table.h 
b/be/src/vec/common/hash_table/hash_table.h
index ea4a6dda5a..1a1eafcc13 100644
--- a/be/src/vec/common/hash_table/hash_table.h
+++ b/be/src/vec/common/hash_table/hash_table.h
@@ -244,21 +244,17 @@ template <size_t initial_size_degree = 10>
 struct HashTableGrower {
     /// The state of this structure is enough to get the buffer size of the 
hash table.
     doris::vectorized::UInt8 size_degree = initial_size_degree;
-    doris::vectorized::Int64 double_grow_degree = 31; // 2GB
+    doris::vectorized::Int64 double_grow_degree = 
doris::config::hash_table_double_grow_degree;
 
     /// The size of the hash table in the cells.
     size_t buf_size() const { return 1ULL << size_degree; }
 
-#ifndef STRICT_MEMORY_USE
-    size_t max_fill() const { return 1ULL << (size_degree - 1); }
-#else
-    // When capacity is greater than 2G, grow when 75% of the capacity is 
satisfied.
+    // When capacity is greater than 2^double_grow_degree, grow when 75% of 
the capacity is satisfied.
     size_t max_fill() const {
         return size_degree < double_grow_degree
                        ? 1ULL << (size_degree - 1)
                        : (1ULL << size_degree) - (1ULL << (size_degree - 2));
     }
-#endif
 
     size_t mask() const { return buf_size() - 1; }
 
@@ -279,9 +275,6 @@ struct HashTableGrower {
 
     /// Set the buffer size by the number of elements in the hash table. Used 
when deserializing a hash table.
     void set(size_t num_elems) {
-#ifndef STRICT_MEMORY_USE
-        size_t fill_capacity = static_cast<size_t>(log2(num_elems - 1)) + 2;
-#else
         size_t fill_capacity = static_cast<size_t>(log2(num_elems - 1)) + 1;
         fill_capacity =
                 fill_capacity < double_grow_degree
@@ -289,7 +282,7 @@ struct HashTableGrower {
                         : (num_elems < (1ULL << fill_capacity) - (1ULL << 
(fill_capacity - 2))
                                    ? fill_capacity
                                    : fill_capacity + 1);
-#endif
+
         size_degree = num_elems <= 1 ? initial_size_degree
                                      : (initial_size_degree > fill_capacity ? 
initial_size_degree
                                                                             : 
fill_capacity);
@@ -311,6 +304,7 @@ class alignas(64) HashTableGrowerWithPrecalculation {
     doris::vectorized::UInt8 size_degree_ = initial_size_degree;
     size_t precalculated_mask = (1ULL << initial_size_degree) - 1;
     size_t precalculated_max_fill = 1ULL << (initial_size_degree - 1);
+    doris::vectorized::Int64 double_grow_degree = 
doris::config::hash_table_double_grow_degree;
 
 public:
     doris::vectorized::UInt8 size_degree() const { return size_degree_; }
@@ -319,7 +313,9 @@ public:
         size_degree_ += delta;
         DCHECK(size_degree_ <= 64);
         precalculated_mask = (1ULL << size_degree_) - 1;
-        precalculated_max_fill = 1ULL << (size_degree_ - 1);
+        precalculated_max_fill = size_degree_ < double_grow_degree
+                                         ? 1ULL << (size_degree_ - 1)
+                                         : (1ULL << size_degree_) - (1ULL << 
(size_degree_ - 2));
     }
 
     static constexpr auto initial_count = 1ULL << initial_size_degree;
@@ -344,12 +340,17 @@ public:
 
     /// Set the buffer size by the number of elements in the hash table. Used 
when deserializing a hash table.
     void set(size_t num_elems) {
-        size_degree_ =
-                num_elems <= 1
-                        ? initial_size_degree
-                        : ((initial_size_degree > 
static_cast<size_t>(log2(num_elems - 1)) + 2)
-                                   ? initial_size_degree
-                                   : (static_cast<size_t>(log2(num_elems - 1)) 
+ 2));
+        size_t fill_capacity = static_cast<size_t>(log2(num_elems - 1)) + 1;
+        fill_capacity =
+                fill_capacity < double_grow_degree
+                        ? fill_capacity + 1
+                        : (num_elems < (1ULL << fill_capacity) - (1ULL << 
(fill_capacity - 2))
+                                   ? fill_capacity
+                                   : fill_capacity + 1);
+
+        size_degree_ = num_elems <= 1 ? initial_size_degree
+                                      : (initial_size_degree > fill_capacity ? 
initial_size_degree
+                                                                             : 
fill_capacity);
         increase_size_degree(0);
     }
 
diff --git a/be/src/vec/common/hash_table/join_hash_map.h 
b/be/src/vec/common/hash_table/join_hash_map.h
deleted file mode 100644
index 089e968766..0000000000
--- a/be/src/vec/common/hash_table/join_hash_map.h
+++ /dev/null
@@ -1,133 +0,0 @@
-// 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.
-// This file is copied from
-// 
https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/HashMap.h
-// and modified by Doris
-
-#pragma once
-
-#include "vec/common/hash_table/hash_map.h"
-#include "vec/common/hash_table/join_hash_table.h"
-
-/** NOTE JoinHashMap could only be used for memmoveable (position independent) 
types.
-  * Example: std::string is not position independent in libstdc++ with C++11 
ABI or in libc++.
-  * Also, key in hash table must be of type, that zero bytes is compared 
equals to zero key.
-  */
-
-template <typename Key, typename Cell, typename Hash = DefaultHash<Key>,
-          typename Grower = HashTableGrower<>, typename Allocator = 
HashTableAllocator>
-class JoinHashMapTable : public JoinHashTable<Key, Cell, Hash, Grower, 
Allocator> {
-public:
-    using Self = JoinHashMapTable;
-    using Base = JoinHashTable<Key, Cell, Hash, Grower, Allocator>;
-
-    using key_type = Key;
-    using value_type = typename Cell::value_type;
-    using mapped_type = typename Cell::Mapped;
-
-    using LookupResult = typename Base::LookupResult;
-
-    using JoinHashTable<Key, Cell, Hash, Grower, Allocator>::JoinHashTable;
-
-    /// Merge every cell's value of current map into the destination map via 
emplace.
-    ///  Func should have signature void(Mapped & dst, Mapped & src, bool 
emplaced).
-    ///  Each filled cell in current map will invoke func once. If that map 
doesn't
-    ///  have a key equals to the given cell, a new cell gets emplaced into 
that map,
-    ///  and func is invoked with the third argument emplaced set to true. 
Otherwise
-    ///  emplaced is set to false.
-    template <typename Func>
-    void ALWAYS_INLINE merge_to_via_emplace(Self& that, Func&& func) {
-        for (auto it = this->begin(), end = this->end(); it != end; ++it) {
-            typename Self::LookupResult res_it;
-            bool inserted;
-            that.emplace(it->get_first(), res_it, inserted, it.get_hash());
-            func(*lookup_result_get_mapped(res_it), it->get_second(), 
inserted);
-        }
-    }
-
-    /// Merge every cell's value of current map into the destination map via 
find.
-    ///  Func should have signature void(Mapped & dst, Mapped & src, bool 
exist).
-    ///  Each filled cell in current map will invoke func once. If that map 
doesn't
-    ///  have a key equals to the given cell, func is invoked with the third 
argument
-    ///  exist set to false. Otherwise exist is set to true.
-    template <typename Func>
-    void ALWAYS_INLINE merge_to_via_find(Self& that, Func&& func) {
-        for (auto it = this->begin(), end = this->end(); it != end; ++it) {
-            auto res_it = that.find(it->get_first(), it.get_hash());
-            if (!res_it)
-                func(it->get_second(), it->get_second(), false);
-            else
-                func(*lookup_result_get_mapped(res_it), it->get_second(), 
true);
-        }
-    }
-
-    /// Call func(const Key &, Mapped &) for each hash map element.
-    template <typename Func>
-    void for_each_value(Func&& func) {
-        for (auto& v : *this) func(v.get_first(), v.get_second());
-    }
-
-    /// Call func(Mapped &) for each hash map element.
-    template <typename Func>
-    void for_each_mapped(Func&& func) {
-        for (auto& v : *this) func(v.get_second());
-    }
-
-    size_t get_size() {
-        size_t count = 0;
-        for (auto& v : *this) {
-            count += v.get_second().get_row_count();
-        }
-        return count;
-    }
-
-    mapped_type& ALWAYS_INLINE operator[](Key x) {
-        typename JoinHashMapTable::LookupResult it;
-        bool inserted;
-        this->emplace(x, it, inserted);
-
-        /** It may seem that initialization is not necessary for POD-types (or 
__has_trivial_constructor),
-          *  since the hash table memory is initially initialized with zeros.
-          * But, in fact, an empty cell may not be initialized with zeros in 
the following cases:
-          * - ZeroValueStorage (it only zeros the key);
-          * - after resizing and moving a part of the cells to the new half of 
the hash table, the old cells also have only the key to zero.
-          *
-          * On performance, there is almost always no difference, due to the 
fact that it->second is usually assigned immediately
-          *  after calling `operator[]`, and since `operator[]` is inlined, 
the compiler removes unnecessary initialization.
-          *
-          * Sometimes due to initialization, the performance even grows. This 
occurs in code like `++map[key]`.
-          * When we do the initialization, for new cells, it's enough to make 
`store 1` right away.
-          * And if we did not initialize, then even though there was zero in 
the cell,
-          *  the compiler can not guess about this, and generates the `load`, 
`increment`, `store` code.
-          */
-        if (inserted) new (lookup_result_get_mapped(it)) mapped_type();
-
-        return *lookup_result_get_mapped(it);
-    }
-
-    char* get_null_key_data() { return nullptr; }
-    bool has_null_key_data() const { return false; }
-};
-
-template <typename Key, typename Mapped, typename Hash = DefaultHash<Key>,
-          typename Grower = JoinHashTableGrower<>, typename Allocator = 
HashTableAllocator>
-using JoinHashMap = JoinHashMapTable<Key, HashMapCell<Key, Mapped, Hash>, 
Hash, Grower, Allocator>;
-
-template <typename Key, typename Mapped, typename Hash = DefaultHash<Key>,
-          typename Grower = JoinHashTableGrower<>, typename Allocator = 
HashTableAllocator>
-using JoinHashMapWithSavedHash =
-        JoinHashMapTable<Key, HashMapCellWithSavedHash<Key, Mapped, Hash>, 
Hash, Grower, Allocator>;
\ No newline at end of file
diff --git a/be/src/vec/common/hash_table/join_hash_table.h 
b/be/src/vec/common/hash_table/join_hash_table.h
deleted file mode 100644
index 5e51eeb62e..0000000000
--- a/be/src/vec/common/hash_table/join_hash_table.h
+++ /dev/null
@@ -1,733 +0,0 @@
-// 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 "vec/common/allocator.h"
-#include "vec/common/hash_table/hash_table.h"
-
-/** NOTE JoinHashTable could only be used for memmoveable (position 
independent) types.
-  * Example: std::string is not position independent in libstdc++ with C++11 
ABI or in libc++.
-  * Also, key in hash table must be of type, that zero bytes is compared 
equals to zero key.
-  */
-
-/** Determines the size of the join hash table, and when and how much it 
should be resized.
-  */
-template <size_t initial_size_degree = 10>
-struct JoinHashTableGrower {
-    /// The state of this structure is enough to get the buffer size of the 
join hash table.
-    doris::vectorized::UInt8 size_degree = initial_size_degree;
-    doris::vectorized::Int64 double_grow_degree = 31; // 2GB
-
-    size_t bucket_size() const { return 1ULL << (size_degree - 1); }
-
-    /// The size of the join hash table in the cells.
-    size_t buf_size() const { return 1ULL << size_degree; }
-
-    size_t max_fill() const { return buf_size(); }
-
-    size_t mask() const { return bucket_size() - 1; }
-
-    /// From the hash value, get the bucket id (first index) in the join hash 
table.
-    size_t place(size_t x) const { return x & mask(); }
-
-    /// Whether the join hash table is full. You need to increase the size of 
the hash table, or remove something unnecessary from it.
-    bool overflow(size_t elems) const { return elems >= max_fill(); }
-
-    /// Increase the size of the join hash table.
-    void increase_size() { size_degree += size_degree >= 23 ? 1 : 2; }
-
-    /// Set the buffer size by the number of elements in the join hash table. 
Used when deserializing a join hash table.
-    void set(size_t num_elems) {
-#ifndef STRICT_MEMORY_USE
-        size_t fill_capacity = static_cast<size_t>(log2(num_elems - 1)) + 2;
-#else
-        size_t fill_capacity = static_cast<size_t>(log2(num_elems - 1)) + 1;
-        fill_capacity =
-                fill_capacity < double_grow_degree
-                        ? fill_capacity + 1
-                        : (num_elems < (1ULL << fill_capacity) - (1ULL << 
(fill_capacity - 2))
-                                   ? fill_capacity
-                                   : fill_capacity + 1);
-#endif
-        size_degree = num_elems <= 1 ? initial_size_degree
-                                     : (initial_size_degree > fill_capacity ? 
initial_size_degree
-                                                                            : 
fill_capacity);
-    }
-
-    void set_buf_size(size_t buf_size_) {
-        size_degree = static_cast<size_t>(log2(buf_size_ - 1) + 1);
-    }
-};
-
-/** Determines the size of the join hash table, and when and how much it 
should be resized.
-  * This structure is aligned to cache line boundary and also occupies it all.
-  * Precalculates some values to speed up lookups and insertion into the 
JoinHashTable (and thus has bigger memory footprint than JoinHashTableGrower).
-  */
-template <size_t initial_size_degree = 8>
-class alignas(64) JoinHashTableGrowerWithPrecalculation {
-    /// The state of this structure is enough to get the buffer size of the 
join hash table.
-
-    doris::vectorized::UInt8 size_degree_ = initial_size_degree;
-    size_t precalculated_mask = (1ULL << (initial_size_degree - 1)) - 1;
-    size_t precalculated_max_fill = 1ULL << initial_size_degree;
-
-public:
-    doris::vectorized::UInt8 size_degree() const { return size_degree_; }
-
-    void increase_size_degree(doris::vectorized::UInt8 delta) {
-        size_degree_ += delta;
-        precalculated_mask = (1ULL << (size_degree_ - 1)) - 1;
-        precalculated_max_fill = 1ULL << size_degree_;
-    }
-
-    static constexpr auto initial_count = 1ULL << initial_size_degree;
-
-    /// If collision resolution chains are contiguous, we can implement erase 
operation by moving the elements.
-    static constexpr auto performs_linear_probing_with_single_step = true;
-
-    size_t bucket_size() const { return 1ULL << (size_degree_ - 1); }
-
-    /// The size of the join hash table in the cells.
-    size_t buf_size() const { return 1ULL << size_degree_; }
-
-    /// From the hash value, get the cell number in the join hash table.
-    size_t place(size_t x) const { return x & precalculated_mask; }
-
-    /// Whether the join hash table is full. You need to increase the size of 
the hash table, or remove something unnecessary from it.
-    bool overflow(size_t elems) const { return elems >= 
precalculated_max_fill; }
-
-    /// Increase the size of the join hash table.
-    void increase_size() { increase_size_degree(size_degree_ >= 23 ? 1 : 2); }
-
-    /// Set the buffer size by the number of elements in the join hash table. 
Used when deserializing a join hash table.
-    void set(size_t num_elems) {
-        size_degree_ =
-                num_elems <= 1
-                        ? initial_size_degree
-                        : ((initial_size_degree > 
static_cast<size_t>(log2(num_elems - 1)) + 2)
-                                   ? initial_size_degree
-                                   : (static_cast<size_t>(log2(num_elems - 1)) 
+ 2));
-        increase_size_degree(0);
-    }
-
-    void set_buf_size(size_t buf_size_) {
-        size_degree_ = static_cast<size_t>(log2(buf_size_ - 1) + 1);
-        increase_size_degree(0);
-    }
-};
-
-static_assert(sizeof(JoinHashTableGrowerWithPrecalculation<>) == 64);
-
-/** When used as a Grower, it turns a hash table into something like a lookup 
table.
-  * It remains non-optimal - the cells store the keys.
-  * Also, the compiler can not completely remove the code of passing through 
the collision resolution chain, although it is not needed.
-  * TODO Make a proper lookup table.
-  */
-template <size_t key_bits>
-struct JoinHashTableFixedGrower {
-    size_t bucket_size() const { return 1ULL << (key_bits - 1); }
-    size_t buf_size() const { return 1ULL << key_bits; }
-    size_t place(size_t x) const { return x & (bucket_size() - 1); }
-    bool overflow(size_t /*elems*/) const { return false; }
-
-    void increase_size() { __builtin_unreachable(); }
-    void set(size_t /*num_elems*/) {}
-    void set_buf_size(size_t /*buf_size_*/) {}
-};
-
-template <typename Key, typename Cell, typename Hash, typename Grower, 
typename Allocator>
-class JoinHashTable : private boost::noncopyable,
-                      protected Hash,
-                      protected Allocator,
-                      protected Cell::State,
-                      protected ZeroValueStorage<Cell::need_zero_value_storage,
-                                                 Cell> /// empty base 
optimization
-{
-protected:
-    friend class const_iterator;
-    friend class iterator;
-    friend class Reader;
-
-    template <typename, typename, typename, typename, typename, typename, 
size_t>
-    friend class TwoLevelHashTable;
-
-    template <typename SubMaps>
-    friend class StringHashTable;
-
-    using HashValue = size_t;
-    using Self = JoinHashTable;
-    using cell_type = Cell;
-
-    size_t m_size = 0;         /// Amount of elements
-    size_t m_no_zero_size = 0; /// Amount of elements except the element with 
zero key.
-    Cell* buf; /// A piece of memory for all elements except the element with 
zero key.
-
-    // bucket-chained hash table
-    // "first" is the buckets of the hash map, and it holds the index of the 
first key value saved in each bucket,
-    // while other keys can be found by following the indices saved in
-    // "next". "next[0]" represents the end of the list of keys in a bucket.
-    // 
https://dare.uva.nl/search?identifier=5ccbb60a-38b8-4eeb-858a-e7735dd37487
-    size_t* first;
-    size_t* next;
-
-    Grower grower;
-    int64_t _resize_timer_ns;
-
-    //factor that will trigger growing the hash table on insert.
-    static constexpr float MAX_BUCKET_OCCUPANCY_FRACTION = 1.0f;
-
-#ifdef DBMS_HASH_MAP_COUNT_COLLISIONS
-    mutable size_t collisions = 0;
-#endif
-
-    /// Find a cell with the same key or an empty cell, starting from the 
specified position and further along the collision resolution chain.
-    size_t ALWAYS_INLINE find_cell(const Key& x, size_t hash_value, size_t 
place_value) const {
-        while (place_value && !buf[place_value - 1].is_zero(*this) &&
-               !buf[place_value - 1].key_equals(x, hash_value, *this)) {
-            place_value = next[place_value];
-#ifdef DBMS_HASH_MAP_COUNT_COLLISIONS
-            ++collisions;
-#endif
-        }
-
-        return place_value;
-    }
-
-    std::pair<bool, size_t> ALWAYS_INLINE find_cell_opt(const Key& x, size_t 
hash_value,
-                                                        size_t place_value) 
const {
-        bool is_zero = false;
-        do {
-            if (!place_value) return {true, place_value};
-            is_zero = buf[place_value - 1].is_zero(*this); ///
-            if (is_zero || buf[place_value - 1].key_equals(x, hash_value, 
*this)) break;
-            place_value = next[place_value];
-        } while (true);
-
-        return {is_zero, place_value};
-    }
-
-    /// Find an empty cell, starting with the specified position and further 
along the collision resolution chain.
-    size_t ALWAYS_INLINE find_empty_cell(size_t place_value) const {
-        while (place_value && !buf[place_value - 1].is_zero(*this)) {
-            place_value = next[place_value];
-#ifdef DBMS_HASH_MAP_COUNT_COLLISIONS
-            ++collisions;
-#endif
-        }
-
-        return place_value;
-    }
-
-    void alloc(const Grower& new_grower) {
-        buf = reinterpret_cast<Cell*>(Allocator::alloc(new_grower.buf_size() * 
sizeof(Cell)));
-        first = reinterpret_cast<size_t*>(
-                Allocator::alloc(new_grower.bucket_size() * sizeof(size_t)));
-        memset(first, 0, new_grower.bucket_size() * sizeof(size_t));
-        next = reinterpret_cast<size_t*>(
-                Allocator::alloc((new_grower.buf_size() + 1) * 
sizeof(size_t)));
-        memset(next, 0, (new_grower.buf_size() + 1) * sizeof(size_t));
-        grower = new_grower;
-    }
-
-    void free() {
-        if (buf) {
-            Allocator::free(buf, get_buffer_size_in_bytes());
-            buf = nullptr;
-        }
-        if (first) {
-            Allocator::free(first, grower.bucket_size() * sizeof(size_t));
-            first = nullptr;
-        }
-        if (next) {
-            Allocator::free(next, (grower.buf_size() + 1) * sizeof(size_t));
-            next = nullptr;
-        }
-    }
-
-    /// Increase the size of the buffer.
-    void resize(size_t for_num_elems = 0, size_t for_buf_size = 0) {
-        SCOPED_RAW_TIMER(&_resize_timer_ns);
-#ifdef DBMS_HASH_MAP_DEBUG_RESIZES
-        Stopwatch watch;
-#endif
-
-        size_t old_size = grower.buf_size();
-
-        /** In case of exception for the object to remain in the correct state,
-          *  changing the variable `grower` (which determines the buffer size 
of the hash table)
-          *  is postponed for a moment after a real buffer change.
-          * The temporary variable `new_grower` is used to determine the new 
size.
-          */
-        Grower new_grower = grower;
-        if (for_num_elems) {
-            new_grower.set(for_num_elems);
-            if (new_grower.buf_size() <= old_size) return;
-        } else if (for_buf_size) {
-            new_grower.set_buf_size(for_buf_size);
-            if (new_grower.buf_size() <= old_size) return;
-        } else
-            new_grower.increase_size();
-
-        /// Expand the space.
-        buf = reinterpret_cast<Cell*>(Allocator::realloc(buf, 
get_buffer_size_in_bytes(),
-                                                         new_grower.buf_size() 
* sizeof(Cell)));
-        first = reinterpret_cast<size_t*>(Allocator::realloc(
-                first, get_bucket_size_in_bytes(), new_grower.bucket_size() * 
sizeof(size_t)));
-        memset(first, 0, new_grower.bucket_size() * sizeof(size_t));
-        next = reinterpret_cast<size_t*>(Allocator::realloc(
-                next, get_buffer_size_in_bytes(), (new_grower.buf_size() + 1) 
* sizeof(size_t)));
-        memset(next, 0, (new_grower.buf_size() + 1) * sizeof(size_t));
-        grower = new_grower;
-
-        /** Now some items may need to be moved to a new location.
-          * The element can stay in place, or move to a new location "on the 
right",
-          *  or move to the left of the collision resolution chain, because 
the elements to the left of it have been moved to the new "right" location.
-          */
-        size_t i = 0;
-        for (; i < m_no_zero_size; ++i)
-            if (!buf[i].is_zero(*this)) reinsert(i + 1, buf[i], 
buf[i].get_hash(*this));
-
-#ifdef DBMS_HASH_MAP_DEBUG_RESIZES
-        watch.stop();
-        std::cerr << std::fixed << std::setprecision(3) << "Resize from " << 
old_size << " to "
-                  << grower.buf_size() << " took " << watch.elapsedSeconds() 
<< " sec."
-                  << std::endl;
-#endif
-    }
-
-    /** Paste into the new buffer the value that was in the old buffer.
-      * Used when increasing the buffer size.
-      */
-    void reinsert(size_t place_value, Cell& x, size_t hash_value) {
-        size_t bucket_value = grower.place(hash_value);
-        next[place_value] = first[bucket_value];
-        first[bucket_value] = place_value;
-    }
-
-    void destroy_elements() {
-        if (!std::is_trivially_destructible_v<Cell>)
-            for (iterator it = begin(), it_end = end(); it != it_end; ++it) 
it.ptr->~Cell();
-    }
-
-    template <typename Derived, bool is_const>
-    class iterator_base {
-        using Container = std::conditional_t<is_const, const Self, Self>;
-        using cell_type = std::conditional_t<is_const, const Cell, Cell>;
-
-        Container* container;
-        cell_type* ptr;
-
-        friend class JoinHashTable;
-
-    public:
-        iterator_base() {}
-        iterator_base(Container* container_, cell_type* ptr_) : 
container(container_), ptr(ptr_) {}
-
-        bool operator==(const iterator_base& rhs) const { return ptr == 
rhs.ptr; }
-        bool operator!=(const iterator_base& rhs) const { return ptr != 
rhs.ptr; }
-
-        Derived& operator++() {
-            /// If iterator was pointed to ZeroValueStorage, move it to the 
beginning of the main buffer.
-            if (UNLIKELY(ptr->is_zero(*container)))
-                ptr = container->buf;
-            else
-                ++ptr;
-
-            /// Skip empty cells in the main buffer.
-            auto buf_end = container->buf + container->m_no_zero_size;
-            while (ptr < buf_end && ptr->is_zero(*container)) ++ptr;
-
-            return static_cast<Derived&>(*this);
-        }
-
-        auto& operator*() const { return *ptr; }
-        auto* operator->() const { return ptr; }
-
-        auto get_ptr() const { return ptr; }
-        size_t get_hash() const { return ptr->get_hash(*container); }
-
-        size_t get_collision_chain_length() const { ////////////// ?????????
-            return 0;
-        }
-
-        operator Cell*() const { return nullptr; }
-    };
-
-public:
-    using key_type = Key;
-    using value_type = typename Cell::value_type;
-
-    // Use lookup_result_get_mapped/Key to work with these values.
-    using LookupResult = Cell*;
-    using ConstLookupResult = const Cell*;
-
-    void reset_resize_timer() { _resize_timer_ns = 0; }
-    int64_t get_resize_timer_value() const { return _resize_timer_ns; }
-
-    size_t hash(const Key& x) const { return Hash::operator()(x); }
-
-    JoinHashTable() {
-        if (Cell::need_zero_value_storage) this->zero_value()->set_zero();
-        alloc(grower);
-    }
-
-    JoinHashTable(size_t reserve_for_num_elements) {
-        if (Cell::need_zero_value_storage) this->zero_value()->set_zero();
-        grower.set(reserve_for_num_elements);
-        alloc(grower);
-    }
-
-    JoinHashTable(JoinHashTable&& rhs) : buf(nullptr) { *this = 
std::move(rhs); }
-
-    ~JoinHashTable() {
-        destroy_elements();
-        free();
-    }
-
-    JoinHashTable& operator=(JoinHashTable&& rhs) {
-        destroy_elements();
-        free();
-
-        std::swap(buf, rhs.buf);
-        std::swap(m_size, rhs.m_size);
-        std::swap(m_no_zero_size, rhs.m_no_zero_size);
-        std::swap(first, rhs.first);
-        std::swap(next, rhs.next);
-        std::swap(grower, rhs.grower);
-
-        Hash::operator=(std::move(rhs));
-        Allocator::operator=(std::move(rhs));
-        Cell::State::operator=(std::move(rhs));
-        ZeroValueStorage<Cell::need_zero_value_storage, 
Cell>::operator=(std::move(rhs));
-
-        return *this;
-    }
-
-    class iterator : public iterator_base<iterator, false> {
-    public:
-        using iterator_base<iterator, false>::iterator_base;
-    };
-
-    class const_iterator : public iterator_base<const_iterator, true> {
-    public:
-        using iterator_base<const_iterator, true>::iterator_base;
-    };
-
-    const_iterator begin() const {
-        if (!buf) return end();
-
-        if (this->get_has_zero()) return iterator_to_zero();
-
-        const Cell* ptr = buf;
-        auto buf_end = buf + m_no_zero_size;
-        while (ptr < buf_end && ptr->is_zero(*this)) ++ptr;
-
-        return const_iterator(this, ptr);
-    }
-
-    const_iterator cbegin() const { return begin(); }
-
-    iterator begin() {
-        if (!buf) return end();
-
-        if (this->get_has_zero()) return iterator_to_zero();
-
-        Cell* ptr = buf;
-        auto buf_end = buf + m_no_zero_size;
-        while (ptr < buf_end && ptr->is_zero(*this)) ++ptr;
-
-        return iterator(this, ptr);
-    }
-
-    const_iterator end() const { return const_iterator(this, buf + 
m_no_zero_size); }
-    const_iterator cend() const { return end(); }
-    iterator end() { return iterator(this, buf + m_no_zero_size); }
-
-protected:
-    const_iterator iterator_to(const Cell* ptr) const { return 
const_iterator(this, ptr); }
-    iterator iterator_to(Cell* ptr) { return iterator(this, ptr); }
-    const_iterator iterator_to_zero() const { return 
iterator_to(this->zero_value()); }
-    iterator iterator_to_zero() { return iterator_to(this->zero_value()); }
-
-    /// If the key is zero, insert it into a special place and return true.
-    /// We don't have to persist a zero key, because it's not actually 
inserted.
-    /// That's why we just take a Key by value, an not a key holder.
-    bool ALWAYS_INLINE emplace_if_zero(Key x, LookupResult& it, bool& 
inserted, size_t hash_value) {
-        /// If it is claimed that the zero key can not be inserted into the 
table.
-        if (!Cell::need_zero_value_storage) return false;
-
-        if (Cell::is_zero(x, *this)) {
-            it = this->zero_value();
-
-            if (!this->get_has_zero()) {
-                ++m_size;
-                this->set_get_has_zero();
-                this->zero_value()->set_hash(hash_value);
-                inserted = true;
-            } else
-                inserted = false;
-
-            return true;
-        }
-
-        return false;
-    }
-
-    /// Only for non-zero keys. Find the right place, insert the key there, if 
it does not already exist. Set iterator to the cell in output parameter.
-    template <typename KeyHolder>
-    void ALWAYS_INLINE emplace_non_zero(KeyHolder&& key_holder, LookupResult& 
it, bool& inserted,
-                                        size_t hash_value) {
-        it = &buf[m_no_zero_size];
-
-        if (!buf[m_no_zero_size].is_zero(*this)) {
-            key_holder_discard_key(key_holder);
-            inserted = false;
-            return;
-        }
-
-        key_holder_persist_key(key_holder);
-        const auto& key = key_holder_get_key(key_holder);
-
-        new (&buf[m_no_zero_size]) Cell(key, *this);
-        buf[m_no_zero_size].set_hash(hash_value);
-        size_t bucket_value = grower.place(hash_value);
-        inserted = true;
-        ++m_size;
-        ++m_no_zero_size;
-        next[m_no_zero_size] = first[bucket_value];
-        first[bucket_value] = m_no_zero_size;
-
-        if (UNLIKELY(grower.overflow(m_size))) {
-            try {
-                resize();
-            } catch (...) {
-                /** If we have not resized successfully, then there will be 
problems.
-                  * There remains a key, but uninitialized mapped-value,
-                  *  which, perhaps, can not even be called a destructor.
-                  */
-                first[bucket_value] = next[m_no_zero_size];
-                next[m_no_zero_size] = 0;
-                --m_size;
-                --m_no_zero_size;
-                buf[m_no_zero_size].set_zero();
-                throw;
-            }
-        }
-    }
-
-public:
-    void expanse_for_add_elem(size_t num_elem) {
-        std::cout << "expanse_for_add_elem\n";
-        if (add_elem_size_overflow(num_elem)) {
-            resize(grower.buf_size() + num_elem);
-        }
-    }
-
-    /// Insert a value. In the case of any more complex values, it is better 
to use the `emplace` function.
-    std::pair<LookupResult, bool> ALWAYS_INLINE insert(const value_type& x) {
-        std::pair<LookupResult, bool> res;
-        size_t hash_value = hash(Cell::get_key(x));
-        if (!emplace_if_zero(Cell::get_key(x), res.first, res.second, 
hash_value)) {
-            emplace_non_zero(Cell::get_key(x), res.first, res.second, 
hash_value);
-        }
-
-        if (res.second) insert_set_mapped(lookup_result_get_mapped(res.first), 
x);
-
-        return res;
-    }
-
-    template <typename KeyHolder>
-    void ALWAYS_INLINE prefetch(KeyHolder& key_holder) {
-        key_holder_get_key(key_holder);
-        __builtin_prefetch(&buf[m_no_zero_size]);
-    }
-
-    /// Reinsert node pointed to by iterator
-    // void ALWAYS_INLINE reinsert(iterator& it, size_t hash_value) {
-    //     reinsert(*it.get_ptr(), hash_value);
-    // }
-
-    /** Insert the key.
-      * Return values:
-      * 'it' -- a LookupResult pointing to the corresponding key/mapped pair.
-      * 'inserted' -- whether a new key was inserted.
-      *
-      * You have to make `placement new` of value if you inserted a new key,
-      * since when destroying a hash table, it will call the destructor!
-      *
-      * Example usage:
-      *
-      * Map::iterator it;
-      * bool inserted;
-      * map.emplace(key, it, inserted);
-      * if (inserted)
-      *     new(&it->second) Mapped(value);
-      */
-    template <typename KeyHolder>
-    void ALWAYS_INLINE emplace(KeyHolder&& key_holder, LookupResult& it, bool& 
inserted) {
-        const auto& key = key_holder_get_key(key_holder);
-        emplace(key_holder, it, inserted, hash(key));
-    }
-
-    template <typename KeyHolder>
-    void ALWAYS_INLINE emplace(KeyHolder&& key_holder, LookupResult& it, bool& 
inserted,
-                               size_t hash_value) {
-        const auto& key = key_holder_get_key(key_holder);
-        if (!emplace_if_zero(key, it, inserted, hash_value))
-            emplace_non_zero(key_holder, it, inserted, hash_value);
-    }
-
-    /// Copy the cell from another hash table. It is assumed that the cell is 
not zero, and also that there was no such key in the table yet.
-    void ALWAYS_INLINE insert_unique_non_zero(const Cell* cell, size_t 
hash_value) {
-        memcpy(static_cast<void*>(&buf[m_no_zero_size]), cell, sizeof(*cell));
-        size_t bucket_value = grower.place();
-        ++m_size;
-        ++m_no_zero_size;
-        next[m_no_zero_size] = first[bucket_value];
-        first[bucket_value] = m_no_zero_size;
-
-        if (UNLIKELY(grower.overflow(m_size))) resize();
-    }
-
-    LookupResult ALWAYS_INLINE find(Key x) {
-        if (Cell::is_zero(x, *this)) return this->get_has_zero() ? 
this->zero_value() : nullptr;
-
-        size_t hash_value = hash(x);
-        auto [is_zero, place_value] = find_cell_opt(x, hash_value, 
first[grower.place(hash_value)]);
-
-        if (!place_value) return nullptr;
-
-        return !is_zero ? &buf[place_value - 1] : nullptr;
-    }
-
-    ConstLookupResult ALWAYS_INLINE find(Key x) const {
-        return const_cast<std::decay_t<decltype(*this)>*>(this)->find(x);
-    }
-
-    LookupResult ALWAYS_INLINE find(Key x, size_t hash_value) {
-        if (Cell::is_zero(x, *this)) return this->get_has_zero() ? 
this->zero_value() : nullptr;
-
-        size_t place_value = find_cell(x, hash_value, 
first[grower.place(hash_value)]);
-
-        if (!place_value) return nullptr;
-
-        return !buf[place_value - 1].is_zero(*this) ? &buf[place_value - 1] : 
nullptr;
-    }
-
-    bool ALWAYS_INLINE has(Key x) const {
-        if (Cell::is_zero(x, *this)) return this->get_has_zero();
-
-        size_t hash_value = hash(x);
-        size_t place_value = find_cell(x, hash_value, 
first[grower.place(hash_value)]);
-        return !place_value && !buf[place_value - 1].is_zero(*this);
-    }
-
-    bool ALWAYS_INLINE has(Key x, size_t hash_value) const {
-        if (Cell::is_zero(x, *this)) return this->get_has_zero();
-
-        size_t place_value = find_cell(x, hash_value, 
first[grower.place(hash_value)]);
-        return !place_value && !buf[place_value - 1].is_zero(*this);
-    }
-
-    void write(doris::vectorized::BufferWritable& wb) const {
-        Cell::State::write(wb);
-        doris::vectorized::write_var_uint(m_size, wb);
-
-        if (this->get_has_zero()) this->zero_value()->write(wb);
-
-        for (auto ptr = buf, buf_end = buf + m_no_zero_size; ptr < buf_end; 
++ptr)
-            if (!ptr->is_zero(*this)) ptr->write(wb);
-    }
-
-    void read(doris::vectorized::BufferReadable& rb) {
-        Cell::State::read(rb);
-
-        destroy_elements();
-        this->clear_get_has_zero();
-        m_size = 0;
-
-        size_t new_size = 0;
-        doris::vectorized::read_var_uint(new_size, rb);
-
-        free();
-        Grower new_grower = grower;
-        new_grower.set(new_size);
-        alloc(new_grower);
-
-        for (size_t i = 0; i < new_size; ++i) {
-            Cell x;
-            x.read(rb);
-            insert(Cell::get_key(x.get_value()));
-        }
-    }
-
-    size_t size() const { return m_size; }
-
-    size_t no_zero_size() const { return m_no_zero_size; }
-
-    bool empty() const { return 0 == m_size; }
-
-    float get_factor() const { return MAX_BUCKET_OCCUPANCY_FRACTION; }
-
-    bool should_be_shrink(int64_t valid_row) { return valid_row < get_factor() 
* (size() / 2.0); }
-
-    void init_buf_size(size_t reserve_for_num_elements) {
-        free();
-        grower.set(reserve_for_num_elements);
-        alloc(grower);
-    }
-
-    void delete_zero_key(Key key) {
-        if (this->get_has_zero() && Cell::is_zero(key, *this)) {
-            --m_size;
-            this->clear_get_has_zero();
-        }
-    }
-
-    void clear() {
-        destroy_elements();
-        this->clear_get_has_zero();
-        m_size = 0;
-        m_no_zero_size = 0;
-
-        memset(static_cast<void*>(buf), 0, grower.buf_size() * sizeof(*buf));
-    }
-
-    /// After executing this function, the table can only be destroyed,
-    ///  and also you can use the methods `size`, `empty`, `begin`, `end`.
-    void clear_and_shrink() {
-        destroy_elements();
-        this->clear_get_has_zero();
-        m_size = 0;
-        m_no_zero_size = 0;
-        free();
-    }
-
-    size_t get_buffer_size_in_bytes() const { return grower.buf_size() * 
sizeof(Cell); }
-
-    size_t get_bucket_size_in_bytes() const { return grower.bucket_size() * 
sizeof(Cell); }
-
-    size_t get_buffer_size_in_cells() const { return grower.buf_size(); }
-
-    bool add_elem_size_overflow(size_t add_size) const {
-        return grower.overflow(add_size + m_size);
-    }
-#ifdef DBMS_HASH_MAP_COUNT_COLLISIONS
-    size_t getCollisions() const { return collisions; }
-#endif
-};
\ No newline at end of file
diff --git a/be/src/vec/exec/join/vhash_join_node.cpp 
b/be/src/vec/exec/join/vhash_join_node.cpp
index 1baa7ddd31..9c8a8a10f0 100644
--- a/be/src/vec/exec/join/vhash_join_node.cpp
+++ b/be/src/vec/exec/join/vhash_join_node.cpp
@@ -100,9 +100,14 @@ struct ProcessHashTableBuild {
         hash_table_ctx.hash_table.reset_resize_timer();
 
         // only not build_unique, we need expanse hash table before insert data
+        // 1. There are fewer duplicate keys, reducing the number of resize 
hash tables
+        // can improve performance to a certain extent, about 2%-5%
+        // 2. There are many duplicate keys, and the hash table filled bucket 
is far less than
+        // the hash table build bucket, which may waste a lot of memory.
+        // TODO, use the NDV expansion of the key column in the optimizer 
statistics
         if (!_join_node->_build_unique) {
-            // _rows contains null row, which will cause hash table resize to 
be large.
-            
RETURN_IF_CATCH_BAD_ALLOC(hash_table_ctx.hash_table.expanse_for_add_elem(_rows));
+            
RETURN_IF_CATCH_BAD_ALLOC(hash_table_ctx.hash_table.expanse_for_add_elem(
+                    std::min<int>(_rows, 
config::hash_table_pre_expanse_max_rows)));
         }
 
         vector<int>& inserted_rows = 
_join_node->_inserted_rows[&_acquired_block];
diff --git a/build.sh b/build.sh
index fc1f84749f..8c5f18fa9a 100755
--- a/build.sh
+++ b/build.sh
@@ -295,9 +295,6 @@ fi
 if [[ -z "${ENABLE_STACKTRACE}" ]]; then
     ENABLE_STACKTRACE='ON'
 fi
-if [[ -z "${STRICT_MEMORY_USE}" ]]; then
-    STRICT_MEMORY_USE='OFF'
-fi
 
 if [[ -z "${USE_DWARF}" ]]; then
     USE_DWARF='OFF'
@@ -363,7 +360,6 @@ echo "Get params:
     USE_MEM_TRACKER     -- ${USE_MEM_TRACKER}
     USE_JEMALLOC        -- ${USE_JEMALLOC}
     USE_BTHREAD_SCANNER -- ${USE_BTHREAD_SCANNER}
-    STRICT_MEMORY_USE   -- ${STRICT_MEMORY_USE}
     ENABLE_STACKTRACE   -- ${ENABLE_STACKTRACE}
     DENABLE_CLANG_COVERAGE -- ${DENABLE_CLANG_COVERAGE}
 "
@@ -436,7 +432,6 @@ if [[ "${BUILD_BE}" -eq 1 ]]; then
         -DUSE_MEM_TRACKER="${USE_MEM_TRACKER}" \
         -DUSE_JEMALLOC="${USE_JEMALLOC}" \
         -DUSE_BTHREAD_SCANNER="${USE_BTHREAD_SCANNER}" \
-        -DSTRICT_MEMORY_USE="${STRICT_MEMORY_USE}" \
         -DENABLE_STACKTRACE="${ENABLE_STACKTRACE}" \
         -DUSE_AVX2="${USE_AVX2}" \
         -DGLIBC_COMPATIBILITY="${GLIBC_COMPATIBILITY}" \
diff --git a/run-be-ut.sh b/run-be-ut.sh
index efdd0afc79..ec3a98e686 100755
--- a/run-be-ut.sh
+++ b/run-be-ut.sh
@@ -196,7 +196,6 @@ cd "${CMAKE_BUILD_DIR}"
     -DUSE_DWARF="${USE_DWARF}" \
     -DUSE_MEM_TRACKER="${USE_MEM_TRACKER}" \
     -DUSE_JEMALLOC=OFF \
-    -DSTRICT_MEMORY_USE=OFF \
     -DEXTRA_CXX_FLAGS="${EXTRA_CXX_FLAGS}" \
     -DENABLE_CLANG_COVERAGE="${DENABLE_CLANG_COVERAGE}" \
     ${CMAKE_USE_CCACHE:+${CMAKE_USE_CCACHE}} \


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]


Reply via email to