This is an automated email from the ASF dual-hosted git repository. eldenmoon pushed a commit to branch cs_opt_version-3.1 in repository https://gitbox.apache.org/repos/asf/doris.git
commit 974d8ebe9858f3be0d5072801db9649d7c256c06 Author: HappenLee <[email protected]> AuthorDate: Wed Jul 9 21:50:03 2025 +0800 cherry pick like opt/lru-k --- be/src/olap/like_column_predicate.cpp | 21 ++---- be/src/olap/like_column_predicate.h | 65 +++++++++++++------ be/src/olap/lru_cache.cpp | 104 +++++++++++++++++++++++------ be/src/olap/lru_cache.h | 46 ++++++------- be/src/olap/page_cache.h | 3 +- be/src/runtime/memory/lru_cache_policy.h | 9 +-- be/src/vec/functions/like.cpp | 13 ++-- be/test/olap/lru_cache_test.cpp | 108 +++++++++++++++++++++++++++++-- be/test/olap/page_cache_test.cpp | 29 ++++++++- 9 files changed, 298 insertions(+), 100 deletions(-) diff --git a/be/src/olap/like_column_predicate.cpp b/be/src/olap/like_column_predicate.cpp index b441e982606..6da2aa3062f 100644 --- a/be/src/olap/like_column_predicate.cpp +++ b/be/src/olap/like_column_predicate.cpp @@ -62,15 +62,12 @@ uint16_t LikeColumnPredicate<T>::_evaluate_inner(const vectorized::IColumn& colu auto* nested_col_ptr = vectorized::check_and_get_column< vectorized::ColumnDictionary<vectorized::Int32>>(nested_col); auto& data_array = nested_col_ptr->get_data(); + const auto& dict_res = *_find_code_from_dictionary_column(*nested_col_ptr); if (!nullable_col->has_null()) { for (uint16_t i = 0; i != size; i++) { uint16_t idx = sel[i]; sel[new_size] = idx; - StringRef cell_value = nested_col_ptr->get_shrink_value(data_array[idx]); - unsigned char flag = 0; - static_cast<void>((_state->scalar_function)( - const_cast<vectorized::LikeSearchState*>(&_like_state), - StringRef(cell_value.data, cell_value.size), pattern, &flag)); + unsigned char flag = dict_res[data_array[idx]]; new_size += _opposite ^ flag; } } else { @@ -81,12 +78,7 @@ uint16_t LikeColumnPredicate<T>::_evaluate_inner(const vectorized::IColumn& colu new_size += _opposite; continue; } - - StringRef cell_value = nested_col_ptr->get_shrink_value(data_array[idx]); - unsigned char flag = 0; - static_cast<void>((_state->scalar_function)( - const_cast<vectorized::LikeSearchState*>(&_like_state), - StringRef(cell_value.data, cell_value.size), pattern, &flag)); + unsigned char flag = dict_res[data_array[idx]]; new_size += _opposite ^ flag; } } @@ -126,15 +118,12 @@ uint16_t LikeColumnPredicate<T>::_evaluate_inner(const vectorized::IColumn& colu if (column.is_column_dictionary()) { auto* nested_col_ptr = vectorized::check_and_get_column< vectorized::ColumnDictionary<vectorized::Int32>>(column); + const auto& dict_res = *_find_code_from_dictionary_column(*nested_col_ptr); auto& data_array = nested_col_ptr->get_data(); for (uint16_t i = 0; i != size; i++) { uint16_t idx = sel[i]; sel[new_size] = idx; - StringRef cell_value = nested_col_ptr->get_shrink_value(data_array[idx]); - unsigned char flag = 0; - static_cast<void>((_state->scalar_function)( - const_cast<vectorized::LikeSearchState*>(&_like_state), - StringRef(cell_value.data, cell_value.size), pattern, &flag)); + unsigned char flag = dict_res[data_array[idx]]; new_size += _opposite ^ flag; } } else { diff --git a/be/src/olap/like_column_predicate.h b/be/src/olap/like_column_predicate.h index 31763d45f7e..7402d8c9f5a 100644 --- a/be/src/olap/like_column_predicate.h +++ b/be/src/olap/like_column_predicate.h @@ -101,6 +101,7 @@ private: if (nested_col.is_column_dictionary()) { auto* nested_col_ptr = vectorized::check_and_get_column< vectorized::ColumnDictionary<vectorized::Int32>>(nested_col); + const auto& dict_res = *_find_code_from_dictionary_column(*nested_col_ptr); auto& data_array = nested_col_ptr->get_data(); for (uint16_t i = 0; i < size; i++) { if (null_map_data[i]) { @@ -112,18 +113,10 @@ private: continue; } - StringRef cell_value = nested_col_ptr->get_shrink_value(data_array[i]); + unsigned char flag = dict_res[data_array[i]]; if constexpr (is_and) { - unsigned char flag = 0; - static_cast<void>((_state->scalar_function)( - const_cast<vectorized::LikeSearchState*>(&_like_state), - StringRef(cell_value.data, cell_value.size), pattern, &flag)); flags[i] &= _opposite ^ flag; } else { - unsigned char flag = 0; - static_cast<void>((_state->scalar_function)( - const_cast<vectorized::LikeSearchState*>(&_like_state), - StringRef(cell_value.data, cell_value.size), pattern, &flag)); flags[i] = _opposite ^ flag; } } @@ -136,19 +129,12 @@ private: auto* nested_col_ptr = vectorized::check_and_get_column< vectorized::ColumnDictionary<vectorized::Int32>>(column); auto& data_array = nested_col_ptr->get_data(); + const auto& dict_res = *_find_code_from_dictionary_column(*nested_col_ptr); for (uint16_t i = 0; i < size; i++) { - StringRef cell_value = nested_col_ptr->get_shrink_value(data_array[i]); + unsigned char flag = dict_res[data_array[i]]; if constexpr (is_and) { - unsigned char flag = 0; - static_cast<void>((_state->scalar_function)( - const_cast<vectorized::LikeSearchState*>(&_like_state), - StringRef(cell_value.data, cell_value.size), pattern, &flag)); flags[i] &= _opposite ^ flag; } else { - unsigned char flag = 0; - static_cast<void>((_state->scalar_function)( - const_cast<vectorized::LikeSearchState*>(&_like_state), - StringRef(cell_value.data, cell_value.size), pattern, &flag)); flags[i] = _opposite ^ flag; } } @@ -159,6 +145,49 @@ private: } } + __attribute__((flatten)) std::vector<bool>* _find_code_from_dictionary_column( + const vectorized::ColumnDictI32& column) const { + std::vector<bool>* res = nullptr; + if (_segment_id_to_cached_res_flags.if_contains( + column.get_rowset_segment_id(), + [&res](const auto& pair) { res = &pair.second; })) { + return res; + } + + std::vector<bool> tmp_res(column.dict_size(), false); + for (int i = 0; i < column.dict_size(); i++) { + StringRef cell_value = column.get_shrink_value(i); + unsigned char flag = 0; + static_cast<void>((_state->scalar_function)( + const_cast<vectorized::LikeSearchState*>(&_like_state), + StringRef(cell_value.data, cell_value.size), pattern, &flag)); + tmp_res[i] = flag; + } + // Sometimes the dict is not initialized when run comparison predicate here, for example, + // the full page is null, then the reader will skip read, so that the dictionary is not + // inited. The cached code is wrong during this case, because the following page maybe not + // null, and the dict should have items in the future. + // + // Cached code may have problems, so that add a config here, if not opened, then + // we will return the code and not cache it. + if (!column.is_dict_empty() && config::enable_low_cardinality_cache_code) { + _segment_id_to_cached_res_flags.emplace( + std::pair {column.get_rowset_segment_id(), tmp_res}); + } + + _segment_id_to_cached_res_flags.if_contains( + column.get_rowset_segment_id(), [&res](const auto& pair) { res = &pair.second; }); + return res; + } + + mutable phmap::parallel_flat_hash_map< + std::pair<RowsetId, uint32_t>, std::vector<bool>, + phmap::priv::hash_default_hash<std::pair<RowsetId, uint32_t>>, + phmap::priv::hash_default_eq<std::pair<RowsetId, uint32_t>>, + std::allocator<std::pair<const std::pair<RowsetId, uint32_t>, int32_t>>, 4, + std::shared_mutex> + _segment_id_to_cached_res_flags; + std::string _debug_string() const override { std::string info = "LikeColumnPredicate"; return info; diff --git a/be/src/olap/lru_cache.cpp b/be/src/olap/lru_cache.cpp index 9bb21ef717d..673a13b5392 100644 --- a/be/src/olap/lru_cache.cpp +++ b/be/src/olap/lru_cache.cpp @@ -165,7 +165,7 @@ uint32_t HandleTable::element_count() const { return _elems; } -LRUCache::LRUCache(LRUCacheType type) : _type(type) { +LRUCache::LRUCache(LRUCacheType type, bool is_lru_k) : _type(type), _is_lru_k(is_lru_k) { // Make empty circular linked list _lru_normal.next = &_lru_normal; _lru_normal.prev = &_lru_normal; @@ -295,6 +295,17 @@ Cache::Handle* LRUCache::lookup(const CacheKey& key, uint32_t hash) { ++_hit_count; e->last_visit_time = UnixMillis(); } + + // If key not exist in cache, and is lru k cache, and key in visits list, + // then move the key to beginning of the visits list. + // key in visits list indicates that the key has been inserted once after the cache is full. + if (e == nullptr && _is_lru_k) { + auto it = _visits_lru_cache_map.find(hash); + if (it != _visits_lru_cache_map.end()) { + _visits_lru_cache_list.splice(_visits_lru_cache_list.begin(), _visits_lru_cache_list, + it->second); + } + } return reinterpret_cast<Cache::Handle*>(e); } @@ -306,10 +317,10 @@ void LRUCache::release(Cache::Handle* handle) { bool last_ref = false; { std::lock_guard l(_mutex); + // if last_ref is true, key may have been evict from the cache, + // or if it is lru k, first insert of key may have failed. last_ref = _unref(e); - if (last_ref) { - _usage -= e->total_size; - } else if (e->in_cache && e->refs == 1) { + if (e->in_cache && e->refs == 1) { // only exists in cache if (_usage > _capacity) { // take this opportunity and remove the item @@ -317,6 +328,8 @@ void LRUCache::release(Cache::Handle* handle) { DCHECK(removed); e->in_cache = false; _unref(e); + // `entry->in_cache = false` and `_usage -= entry->total_size;` and `_unref(entry)` should appear together. + // see the comment for old entry in `LRUCache::insert`. _usage -= e->total_size; last_ref = true; } else { @@ -391,6 +404,8 @@ void LRUCache::_evict_one_entry(LRUHandle* e) { DCHECK(removed); e->in_cache = false; _unref(e); + // `entry->in_cache = false` and `_usage -= entry->total_size;` and `_unref(entry)` should appear together. + // see the comment for old entry in `LRUCache::insert`. _usage -= e->total_size; } @@ -398,6 +413,42 @@ bool LRUCache::_check_element_count_limit() { return _element_count_capacity != 0 && _table.element_count() >= _element_count_capacity; } +// After cache is full, +// 1.Return false. If key has been inserted into the visits list before, +// key is allowed to be inserted into cache this time (this will trigger cache evict), +// and key is removed from the visits list. +// 2. Return true. If key not in visits list, insert it into visits list. +bool LRUCache::_lru_k_insert_visits_list(size_t total_size, visits_lru_cache_key visits_key) { + if (_usage + total_size > _capacity || + _check_element_count_limit()) { // this line no lock required + auto it = _visits_lru_cache_map.find(visits_key); + if (it != _visits_lru_cache_map.end()) { + _visits_lru_cache_usage -= it->second->second; + _visits_lru_cache_list.erase(it->second); + _visits_lru_cache_map.erase(it); + } else { + // _visits_lru_cache_list capacity is same as the cache itself. + // If _visits_lru_cache_list is full, some keys will also be evict. + while (_visits_lru_cache_usage + total_size > _capacity && + _visits_lru_cache_usage != 0) { + DCHECK(!_visits_lru_cache_map.empty()); + _visits_lru_cache_usage -= _visits_lru_cache_list.back().second; + _visits_lru_cache_map.erase(_visits_lru_cache_list.back().first); + _visits_lru_cache_list.pop_back(); + } + // 1. If true, insert key at the beginning of _visits_lru_cache_list. + // 2. If false, it means total_size > cache _capacity, preventing this insert. + if (_visits_lru_cache_usage + total_size <= _capacity) { + _visits_lru_cache_list.emplace_front(visits_key, total_size); + _visits_lru_cache_map[visits_key] = _visits_lru_cache_list.begin(); + _visits_lru_cache_usage += total_size; + } + return true; + } + } + return false; +} + Cache::Handle* LRUCache::insert(const CacheKey& key, uint32_t hash, void* value, size_t charge, CachePriority priority) { size_t handle_size = sizeof(LRUHandle) - 1 + key.size(); @@ -409,17 +460,22 @@ Cache::Handle* LRUCache::insert(const CacheKey& key, uint32_t hash, void* value, // because charge at this time is no longer the memory size, but an weight. e->total_size = (_type == LRUCacheType::SIZE ? handle_size + charge : charge); e->hash = hash; - e->refs = 2; // one for the returned handle, one for LRUCache. + e->refs = 1; // only one for the returned handle. e->next = e->prev = nullptr; - e->in_cache = true; + e->in_cache = false; e->priority = priority; e->type = _type; memcpy(e->key_data, key.data(), key.size()); e->last_visit_time = UnixMillis(); + LRUHandle* to_remove_head = nullptr; { std::lock_guard l(_mutex); + if (_is_lru_k && _lru_k_insert_visits_list(e->total_size, hash)) { + return reinterpret_cast<Cache::Handle*>(e); + } + // Free the space following strict LRU policy until enough space // is freed or the lru list is empty if (_cache_value_check_timestamp) { @@ -431,12 +487,21 @@ Cache::Handle* LRUCache::insert(const CacheKey& key, uint32_t hash, void* value, // insert into the cache // note that the cache might get larger than its capacity if not enough // space was freed - auto old = _table.insert(e); + auto* old = _table.insert(e); + e->in_cache = true; _usage += e->total_size; + e->refs++; // one for the returned handle, one for LRUCache. if (old != nullptr) { old->in_cache = false; + // `entry->in_cache = false` and `_usage -= entry->total_size;` and `_unref(entry)` should appear together. + // Whether the reference of the old entry is 0, the cache usage is subtracted here, + // because the old entry has been removed from the cache and should not be counted in the cache capacity, + // but the memory of the old entry is still tracked by the cache memory_tracker. + // After all the old handles are released, the old entry will be freed and the memory of the old entry + // will be released from the cache memory_tracker. + _usage -= old->total_size; + // if false, old entry is being used externally, just ref-- and sub _usage, if (_unref(old)) { - _usage -= old->total_size; // old is on LRU because it's in cache and its reference count // was just 1 (Unref returned 0) _lru_remove(old); @@ -465,14 +530,15 @@ void LRUCache::erase(const CacheKey& key, uint32_t hash) { e = _table.remove(key, hash); if (e != nullptr) { last_ref = _unref(e); - if (last_ref) { - _usage -= e->total_size; - if (e->in_cache) { - // locate in free list - _lru_remove(e); - } + // if last_ref is false or in_cache is false, e must not be in lru + if (last_ref && e->in_cache) { + // locate in free list + _lru_remove(e); } e->in_cache = false; + // `entry->in_cache = false` and `_usage -= entry->total_size;` and `_unref(entry)` should appear together. + // see the comment for old entry in `LRUCache::insert`. + _usage -= e->total_size; } } // free handle out of mutex, when last_ref is true, e must not be nullptr @@ -565,7 +631,8 @@ inline uint32_t ShardedLRUCache::_hash_slice(const CacheKey& s) { } ShardedLRUCache::ShardedLRUCache(const std::string& name, size_t capacity, LRUCacheType type, - uint32_t num_shards, uint32_t total_element_count_capacity) + uint32_t num_shards, uint32_t total_element_count_capacity, + bool is_lru_k) : _name(name), _num_shard_bits(Bits::FindLSBSetNonZero(num_shards)), _num_shards(num_shards), @@ -581,7 +648,7 @@ ShardedLRUCache::ShardedLRUCache(const std::string& name, size_t capacity, LRUCa (total_element_count_capacity + (_num_shards - 1)) / _num_shards; LRUCache** shards = new (std::nothrow) LRUCache*[_num_shards]; for (int s = 0; s < _num_shards; s++) { - shards[s] = new LRUCache(type); + shards[s] = new LRUCache(type, is_lru_k); shards[s]->set_capacity(per_shard); shards[s]->set_element_count_capacity(per_shard_element_count_capacity); } @@ -610,8 +677,9 @@ ShardedLRUCache::ShardedLRUCache(const std::string& name, size_t capacity, LRUCa uint32_t num_shards, CacheValueTimeExtractor cache_value_time_extractor, bool cache_value_check_timestamp, - uint32_t total_element_count_capacity) - : ShardedLRUCache(name, capacity, type, num_shards, total_element_count_capacity) { + uint32_t total_element_count_capacity, bool is_lru_k) + : ShardedLRUCache(name, capacity, type, num_shards, total_element_count_capacity, + is_lru_k) { for (int s = 0; s < _num_shards; s++) { _shards[s]->set_cache_value_time_extractor(cache_value_time_extractor); _shards[s]->set_cache_value_check_timestamp(cache_value_check_timestamp); diff --git a/be/src/olap/lru_cache.h b/be/src/olap/lru_cache.h index c285555d916..0b7da8754ff 100644 --- a/be/src/olap/lru_cache.h +++ b/be/src/olap/lru_cache.h @@ -26,30 +26,6 @@ namespace doris { -#define OLAP_CACHE_STRING_TO_BUF(cur, str, r_len) \ - do { \ - if (r_len > str.size()) { \ - memcpy(cur, str.c_str(), str.size()); \ - r_len -= str.size(); \ - cur += str.size(); \ - } else { \ - LOG(WARNING) << "construct cache key buf not enough."; \ - return CacheKey(nullptr, 0); \ - } \ - } while (0) - -#define OLAP_CACHE_NUMERIC_TO_BUF(cur, numeric, r_len) \ - do { \ - if (r_len > sizeof(numeric)) { \ - memcpy(cur, &numeric, sizeof(numeric)); \ - r_len -= sizeof(numeric); \ - cur += sizeof(numeric); \ - } else { \ - LOG(WARNING) << "construct cache key buf not enough."; \ - return CacheKey(nullptr, 0); \ - } \ - } while (0) - class Cache; class LRUCachePolicy; struct LRUHandle; @@ -62,6 +38,7 @@ enum LRUCacheType { static constexpr LRUCacheType DEFAULT_LRU_CACHE_TYPE = LRUCacheType::SIZE; static constexpr uint32_t DEFAULT_LRU_CACHE_NUM_SHARDS = 32; static constexpr size_t DEFAULT_LRU_CACHE_ELEMENT_COUNT_CAPACITY = 0; +static constexpr bool DEFAULT_LRU_CACHE_IS_LRU_K = false; class CacheKey { public: @@ -180,6 +157,10 @@ public: // // When the inserted entry is no longer needed, the key and // value will be passed to "deleter". + // + // if cache is lru k and cache is full, first insert of key will not succeed. + // + // Note: if is ShardedLRUCache, cache capacity = ShardedLRUCache_capacity / num_shards. virtual Handle* insert(const CacheKey& key, void* value, size_t charge, CachePriority priority = CachePriority::NORMAL) = 0; @@ -326,9 +307,12 @@ using LRUHandleSortedSet = std::set<std::pair<int64_t, LRUHandle*>>; // A single shard of sharded cache. class LRUCache { public: - LRUCache(LRUCacheType type); + LRUCache(LRUCacheType type, bool is_lru_k = DEFAULT_LRU_CACHE_IS_LRU_K); ~LRUCache(); + using visits_lru_cache_key = uint32_t; + using visits_lru_cache_pair = std::pair<visits_lru_cache_key, size_t>; + // Separate from constructor so caller can easily make an array of LRUCache PrunedInfo set_capacity(size_t capacity); void set_element_count_capacity(uint32_t element_count_capacity) { @@ -362,6 +346,7 @@ private: void _evict_from_lru_with_time(size_t total_size, LRUHandle** to_remove_head); void _evict_one_entry(LRUHandle* e); bool _check_element_count_limit(); + bool _lru_k_insert_visits_list(size_t total_size, visits_lru_cache_key visits_key); private: LRUCacheType _type; @@ -391,6 +376,12 @@ private: LRUHandleSortedSet _sorted_durable_entries_with_timestamp; uint32_t _element_count_capacity = 0; + + bool _is_lru_k = false; // LRU-K algorithm, K=2 + std::list<visits_lru_cache_pair> _visits_lru_cache_list; + std::unordered_map<visits_lru_cache_key, std::list<visits_lru_cache_pair>::iterator> + _visits_lru_cache_map; + size_t _visits_lru_cache_usage = 0; }; class ShardedLRUCache : public Cache { @@ -415,11 +406,12 @@ private: friend class LRUCachePolicy; explicit ShardedLRUCache(const std::string& name, size_t capacity, LRUCacheType type, - uint32_t num_shards, uint32_t element_count_capacity); + uint32_t num_shards, uint32_t element_count_capacity, bool is_lru_k); explicit ShardedLRUCache(const std::string& name, size_t capacity, LRUCacheType type, uint32_t num_shards, CacheValueTimeExtractor cache_value_time_extractor, - bool cache_value_check_timestamp, uint32_t element_count_capacity); + bool cache_value_check_timestamp, uint32_t element_count_capacity, + bool is_lru_k); void update_cache_metrics() const; diff --git a/be/src/olap/page_cache.h b/be/src/olap/page_cache.h index 32b6683e782..2b123e83c1e 100644 --- a/be/src/olap/page_cache.h +++ b/be/src/olap/page_cache.h @@ -97,7 +97,8 @@ public: DataPageCache(size_t capacity, uint32_t num_shards) : LRUCachePolicy(CachePolicy::CacheType::DATA_PAGE_CACHE, capacity, LRUCacheType::SIZE, config::data_page_cache_stale_sweep_time_sec, - num_shards) {} + num_shards, DEFAULT_LRU_CACHE_ELEMENT_COUNT_CAPACITY, true, true) { + } }; class IndexPageCache : public LRUCachePolicy { diff --git a/be/src/runtime/memory/lru_cache_policy.h b/be/src/runtime/memory/lru_cache_policy.h index 83c7f46585a..63b2abe2118 100644 --- a/be/src/runtime/memory/lru_cache_policy.h +++ b/be/src/runtime/memory/lru_cache_policy.h @@ -36,13 +36,13 @@ public: LRUCachePolicy(CacheType type, size_t capacity, LRUCacheType lru_cache_type, uint32_t stale_sweep_time_s, uint32_t num_shards = DEFAULT_LRU_CACHE_NUM_SHARDS, uint32_t element_count_capacity = DEFAULT_LRU_CACHE_ELEMENT_COUNT_CAPACITY, - bool enable_prune = true) + bool enable_prune = true, bool is_lru_k = DEFAULT_LRU_CACHE_IS_LRU_K) : CachePolicy(type, capacity, stale_sweep_time_s, enable_prune), _lru_cache_type(lru_cache_type) { if (check_capacity(capacity, num_shards)) { _cache = std::shared_ptr<ShardedLRUCache>( new ShardedLRUCache(type_string(type), capacity, lru_cache_type, num_shards, - element_count_capacity)); + element_count_capacity, is_lru_k)); } else { CHECK(ExecEnv::GetInstance()->get_dummy_lru_cache()); _cache = ExecEnv::GetInstance()->get_dummy_lru_cache(); @@ -55,14 +55,15 @@ public: uint32_t stale_sweep_time_s, uint32_t num_shards, uint32_t element_count_capacity, CacheValueTimeExtractor cache_value_time_extractor, - bool cache_value_check_timestamp, bool enable_prune = true) + bool cache_value_check_timestamp, bool enable_prune = true, + bool is_lru_k = DEFAULT_LRU_CACHE_IS_LRU_K) : CachePolicy(type, capacity, stale_sweep_time_s, enable_prune), _lru_cache_type(lru_cache_type) { if (check_capacity(capacity, num_shards)) { _cache = std::shared_ptr<ShardedLRUCache>( new ShardedLRUCache(type_string(type), capacity, lru_cache_type, num_shards, cache_value_time_extractor, cache_value_check_timestamp, - element_count_capacity)); + element_count_capacity, is_lru_k)); } else { CHECK(ExecEnv::GetInstance()->get_dummy_lru_cache()); _cache = ExecEnv::GetInstance()->get_dummy_lru_cache(); diff --git a/be/src/vec/functions/like.cpp b/be/src/vec/functions/like.cpp index 4ed14280e4c..f3aa71d03a0 100644 --- a/be/src/vec/functions/like.cpp +++ b/be/src/vec/functions/like.cpp @@ -509,11 +509,12 @@ Status FunctionLikeBase::execute_impl(FunctionContext* context, Block& block, size_t input_rows_count) const { const auto values_col = block.get_by_position(arguments[0]).column->convert_to_full_column_if_const(); - const auto* values = check_and_get_column<ColumnString>(values_col.get()); + const auto* values = + assert_cast<const ColumnString*, TypeCheckOnRelease::DISABLE>(values_col.get()); - if (!values) { - return Status::InternalError("Not supported input arguments types"); - } + // if (!values) { + // return Status::InternalError("Not supported input arguments types"); + // } // result column auto res = ColumnUInt8::create(); ColumnUInt8::Container& vec_res = res->get_data(); @@ -578,9 +579,7 @@ Status FunctionLikeBase::execute_substring(const ColumnString::Chars& values, } /// We check that the entry does not pass through the boundaries of strings. - if (pos + needle_size <= begin + value_offsets[i]) { - result[i] = 1; - } + result[i] = pos + needle_size <= begin + value_offsets[i]; // move to next string offset pos = begin + value_offsets[i]; diff --git a/be/test/olap/lru_cache_test.cpp b/be/test/olap/lru_cache_test.cpp index 8c260d69755..64fe925f15f 100644 --- a/be/test/olap/lru_cache_test.cpp +++ b/be/test/olap/lru_cache_test.cpp @@ -24,6 +24,7 @@ #include <iosfwd> #include <vector> +#include "gtest/gtest.h" #include "gtest/gtest_pred_impl.h" #include "runtime/memory/lru_cache_policy.h" #include "runtime/memory/lru_cache_value_base.h" @@ -105,6 +106,9 @@ public: // there is 16 shards in ShardedLRUCache // And the LRUHandle size is about 100B. So the cache size should big enough // to run the UT. + // kCacheSize needs to be an even number. if odd number, the cache will behave correctly, + // but the UT Test will fail because check(capacity / 2) will fail. + // In fact, Cache will waste an entry space. static const int kCacheSize = 1000 * 16; std::vector<int> _deleted_keys; std::vector<int> _deleted_values; @@ -325,7 +329,74 @@ TEST_F(CacheTest, Usage) { CacheKey key7("950"); insert_LRUCache(cache, key7, 950, CachePriority::DURABLE); - ASSERT_EQ(0, cache.get_usage()); // evict 298 698, because 950 + 98 > 1040, so insert failed + ASSERT_EQ( + 0, + cache.get_usage()); // evict 298 698, because 950 + 98 > 1040, data was freed when handle release. + + CacheKey key8("900"); + insert_LRUCache(cache, key8, 900, CachePriority::NORMAL); + ASSERT_EQ(998, cache.get_usage()); // 900 + 98 < 1050 +} + +TEST_F(CacheTest, UsageLRUK) { + LRUCache cache(LRUCacheType::SIZE, true); + cache.set_capacity(1050); + + // The lru usage is handle_size + charge. + // handle_size = sizeof(handle) - 1 + key size = 96 - 1 + 3 = 98 + CacheKey key1("100"); + insert_LRUCache(cache, key1, 100, CachePriority::NORMAL); + ASSERT_EQ(198, cache.get_usage()); // 100 + 98 + + CacheKey key2("200"); + insert_LRUCache(cache, key2, 200, CachePriority::DURABLE); + ASSERT_EQ(496, cache.get_usage()); // 198 + 298(d), d = DURABLE + + CacheKey key3("300"); + insert_LRUCache(cache, key3, 300, CachePriority::NORMAL); + ASSERT_EQ(894, cache.get_usage()); // 198 + 298(d) + 398 + + CacheKey key4("400"); + insert_LRUCache(cache, key4, 400, CachePriority::NORMAL); + // Data cache is full, not insert, visits lru cache not exist key=498(400 + 98) and insert it. + ASSERT_EQ(894, cache.get_usage()); + + insert_LRUCache(cache, key4, 400, CachePriority::NORMAL); + // Data cache 298(d) + 498, evict 198 398. visits lru cache exist key=498 + // and erase from visits lru cache, insert to Data cache. + ASSERT_EQ(796, cache.get_usage()); + + CacheKey key5("500"); + insert_LRUCache(cache, key5, 500, CachePriority::NORMAL); + // Data cache is full, not insert, visits lru cache not exist key=598(500 + 98) and insert it. + ASSERT_EQ(796, cache.get_usage()); + + CacheKey key6("600"); + insert_LRUCache(cache, key6, 600, CachePriority::NORMAL); + // Data cache is full, not insert, visits lru cache not exist key=698(600 + 98) and insert it, + // visits lru cache is full, evict key=598 from visits lru cache. + ASSERT_EQ(796, cache.get_usage()); + + insert_LRUCache(cache, key5, 500, CachePriority::NORMAL); + // Data cache is full, not insert, visits lru cache not exist key=598 and insert it. + // visits lru cache is full, evict key=698 from visits lru cache. + ASSERT_EQ(796, cache.get_usage()); + + insert_LRUCache(cache, key5, 500, CachePriority::NORMAL); + // Data cache 298(d) + 598, evict 498. visits lru cache exist key=598 + // and erase from visits lru cache, insert to Data cache. + ASSERT_EQ(896, cache.get_usage()); + + CacheKey key7("980"); + insert_LRUCache(cache, key7, 980, CachePriority::DURABLE); + // Data cache is full, not insert, visits lru cache not exist key=1078(980 + 98) + // but 1078 > capacity(1050), not insert visits lru cache. + ASSERT_EQ(896, cache.get_usage()); + + insert_LRUCache(cache, key7, 980, CachePriority::DURABLE); + // Ssame as above, data cache is full, not insert, visits lru cache not exist key=1078(980 + 98) + // but 1078 > capacity(1050), not insert visits lru cache. + ASSERT_EQ(896, cache.get_usage()); } TEST_F(CacheTest, Prune) { @@ -661,26 +732,51 @@ TEST_F(CacheTest, SetCapacity) { cache()->get_usage()); // Handle not be released, so key cannot be evicted. for (int i = 0; i < kCacheSize; i++) { + // The Key exists in the Cache, remove the old Entry from the Cache, and insert it again. Insert(i + kCacheSize, 2000 + i, 1); - EXPECT_EQ(-1, Lookup(i + kCacheSize)); // Cache is full, insert failed. + if (i < kCacheSize / 2) { + // Insert() will replace the entry with the same key in the cache, the replaced entry will + // not be freed because there are unreleased handles holding them. + // The current cache capacity(kCacheSize/2) is half of the cache usage(kCacheSize), + // Insert() method will immediately release the handle of the newly inserted entry, + // so the newly inserted entry will be freed, until cache usage is less than or equal to capacity. + ASSERT_GE(cache()->get_usage(), cache()->get_capacity()); + EXPECT_EQ(-1, Lookup(i + kCacheSize)); + } else if (i == kCacheSize / 2) { + // When cache usage is equal to cache capacity, Insert() will replace the old entry + // with the same key and will not free the entry after releasing the handle. + ASSERT_EQ(cache()->get_usage(), cache()->get_capacity()); + EXPECT_EQ(2000 + i, Lookup(i + kCacheSize)); + } else { + // When inserting at `i == kCacheSize / 2 + 1`, the cache usage is equal to the cache capacity, + // so the entry in the LRU list will be evicted (usage - 1) and then inserted (usage + 1). + // because the entry inserted is an existing key, the old entry with the same key is evicted (usage - 1), + // so the final cache usage is equal to (capacity - 1). + ASSERT_EQ(cache()->get_usage(), cache()->get_capacity() - 1); + EXPECT_EQ(2000 + i, Lookup(i + kCacheSize)); + } } ASSERT_EQ(kCacheSize / 2, cache()->get_capacity()); - ASSERT_EQ(kCacheSize, cache()->get_usage()); + // Here cache usage equals cache capacity - 1, because the entry inserted in the previous step + // at `i == kCacheSize / 2 + 1` was evicted, see the reason above. + // Entries held by unreleased handles in `handles` will not be counted in cache usage, + // but will still be counted in the memory tracker. + ASSERT_EQ(kCacheSize / 2 - 1, cache()->get_usage()); cache()->adjust_capacity_weighted(2); ASSERT_EQ(kCacheSize * 2, cache()->get_capacity()); - ASSERT_EQ(kCacheSize, cache()->get_usage()); + ASSERT_EQ(kCacheSize / 2 - 1, cache()->get_usage()); for (int i = 0; i < kCacheSize; i++) { Insert(i, 3000 + i, 1); EXPECT_EQ(3000 + i, Lookup(i)); } ASSERT_EQ(kCacheSize * 2, cache()->get_capacity()); - ASSERT_EQ(kCacheSize * 2, cache()->get_usage()); + ASSERT_EQ(kCacheSize * 1.5 - 1, cache()->get_usage()); cache()->adjust_capacity_weighted(0); ASSERT_EQ(0, cache()->get_capacity()); - ASSERT_EQ(kCacheSize, cache()->get_usage()); + ASSERT_EQ(0, cache()->get_usage()); for (auto it : handles) { cache()->release(it); diff --git a/be/test/olap/page_cache_test.cpp b/be/test/olap/page_cache_test.cpp index 1feb6152add..a6b9300c105 100644 --- a/be/test/olap/page_cache_test.cpp +++ b/be/test/olap/page_cache_test.cpp @@ -71,7 +71,8 @@ TEST_F(StoragePageCacheTest, data_page_only) { EXPECT_TRUE(found); } - // put too many page to eliminate first page + // Page Cache is LRU-K, K=2. + // Put too many page, after cache is full, no key is inserted twice and no evict occurs. for (int i = 0; i < 10 * kNumShards; ++i) { StoragePageCache::CacheKey key("bcd", 0, i); PageCacheHandle handle; @@ -95,6 +96,27 @@ TEST_F(StoragePageCacheTest, data_page_only) { EXPECT_FALSE(found); } + // After cache is full, no key is inserted twice and no evict occurs. + { + PageCacheHandle handle; + auto found = cache.lookup(key, &handle, page_type); + EXPECT_TRUE(found); + } + + // put too many page twice to eliminate first page + for (int i = 0; i < 10 * kNumShards; ++i) { + StoragePageCache::CacheKey key("bcde", 0, i); + PageCacheHandle handle; + auto* data = new DataPage(1024, true, page_type); + cache.insert(key, data, &handle, page_type, false); + auto found = cache.lookup(key, &handle, page_type); // after handle destruct, free data. + EXPECT_FALSE(found); + data = new DataPage(1024, true, page_type); + cache.insert(key, data, &handle, page_type, false); + found = cache.lookup(key, &handle, page_type); + EXPECT_TRUE(found); + } + // cache miss for eliminated key { PageCacheHandle handle; @@ -253,12 +275,13 @@ TEST_F(StoragePageCacheTest, mixed_pages) { EXPECT_FALSE(found_index); } - // cache miss for eliminated key { PageCacheHandle data_handle, index_handle; auto found_data = cache.lookup(data_key, &data_handle, page_type_data); auto found_index = cache.lookup(index_key, &index_handle, page_type_index); - EXPECT_FALSE(found_data); + // after cache is full, no key is inserted twice and no evict occurs + EXPECT_TRUE(found_data); + // cache miss for eliminated key EXPECT_FALSE(found_index); } } --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
