ClickHouse · alexey-milovidov · Mar 3, 2025 · Aug 23, 2024 · Aug 25, 2024 · Aug 30, 2024
diff --git a/programs/local/LocalServer.cpp b/programs/local/LocalServer.cpp
@@ -831,6 +831,9 @@ void LocalServer::processConfig()
     /// Initialize a dummy query cache.
     global_context->setQueryCache(0, 0, 0, 0);
 
+    /// Initialize a dummy query condition cache.
+    global_context->setQueryConditionCache(DEFAULT_QUERY_CONDITION_CACHE_POLICY, 0, 0);
+
     /// Initialize allowed tiers
     global_context->getAccessControl().setAllowTierSettings(server_settings[ServerSetting::allow_feature_tier]);
 

diff --git a/programs/server/Server.cpp b/programs/server/Server.cpp
@@ -279,6 +279,9 @@ namespace ServerSetting
     extern const ServerSettingsUInt64 page_cache_chunk_size;
     extern const ServerSettingsUInt64 page_cache_mmap_size;
     extern const ServerSettingsUInt64 page_cache_size;
+    extern const ServerSettingsString query_condition_cache_policy;
+    extern const ServerSettingsUInt64 query_condition_cache_size;
+    extern const ServerSettingsDouble query_condition_cache_size_ratio;
     extern const ServerSettingsBool page_cache_use_madv_free;
     extern const ServerSettingsBool page_cache_use_transparent_huge_pages;
     extern const ServerSettingsBool prepare_system_log_tables_on_startup;
@@ -1715,6 +1718,16 @@ try
     }
     global_context->setQueryCache(query_cache_max_size_in_bytes, query_cache_max_entries, query_cache_query_cache_max_entry_size_in_bytes, query_cache_max_entry_size_in_rows);
 
+    String query_condition_cache_policy = server_settings[ServerSetting::query_condition_cache_policy];
+    size_t query_condition_cache_size = server_settings[ServerSetting::query_condition_cache_size];
+    double query_condition_cache_size_ratio = server_settings[ServerSetting::query_condition_cache_size_ratio];
+    if (query_condition_cache_size > max_cache_size)
+    {
+        query_condition_cache_size = max_cache_size;
+        LOG_INFO(log, "Lowered query condition cache size to {} because the system has limited RAM", formatReadableSizeWithBinarySuffix(query_condition_cache_size));
+    }
+    global_context->setQueryConditionCache(query_condition_cache_policy, query_condition_cache_size, query_condition_cache_size_ratio);
+
 #if USE_EMBEDDED_COMPILER
     size_t compiled_expression_cache_max_size_in_bytes = server_settings[ServerSetting::compiled_expression_cache_size];
     size_t compiled_expression_cache_max_elements = server_settings[ServerSetting::compiled_expression_cache_elements_size];
@@ -2010,6 +2023,7 @@ try
             global_context->updateSkippingIndexCacheConfiguration(*config);
             global_context->updateMMappedFileCacheConfiguration(*config);
             global_context->updateQueryCacheConfiguration(*config);
+            global_context->updateQueryConditionCacheConfiguration(*config);
 
             CompressionCodecEncrypted::Configuration::instance().tryLoad(*config, "encryption_codecs");
 #if USE_SSL

diff --git a/src/Access/Common/AccessType.h b/src/Access/Common/AccessType.h
@@ -173,6 +173,7 @@ enum class AccessType : uint8_t
     M(SYSTEM_DROP_SKIPPING_INDEX_CACHE, "SYSTEM DROP SKIPPING INDEX CACHE, DROP SKIPPING INDEX CACHE", GLOBAL, SYSTEM_DROP_CACHE) \
     M(SYSTEM_DROP_MMAP_CACHE, "SYSTEM DROP MMAP, DROP MMAP CACHE, DROP MMAP", GLOBAL, SYSTEM_DROP_CACHE) \
     M(SYSTEM_DROP_QUERY_CACHE, "SYSTEM DROP QUERY, DROP QUERY CACHE, DROP QUERY", GLOBAL, SYSTEM_DROP_CACHE) \
+    M(SYSTEM_DROP_QUERY_CONDITION_CACHE, "SYSTEM DROP QUERY CONDITION, DROP QUERY CONDITION CACHE, DROP QUERY CONDITION", GLOBAL, SYSTEM_DROP_CACHE) \
     M(SYSTEM_DROP_COMPILED_EXPRESSION_CACHE, "SYSTEM DROP COMPILED EXPRESSION, DROP COMPILED EXPRESSION CACHE, DROP COMPILED EXPRESSIONS", GLOBAL, SYSTEM_DROP_CACHE) \
     M(SYSTEM_DROP_FILESYSTEM_CACHE, "SYSTEM DROP FILESYSTEM CACHE, DROP FILESYSTEM CACHE", GLOBAL, SYSTEM_DROP_CACHE) \
     M(SYSTEM_DROP_DISTRIBUTED_CACHE, "SYSTEM DROP DISTRIBUTED CACHE, DROP DISTRIBUTED CACHE", GLOBAL, SYSTEM_DROP_CACHE) \

diff --git a/src/Common/ProfileEvents.cpp b/src/Common/ProfileEvents.cpp
@@ -75,6 +75,8 @@
     M(SkippingIndexCacheWeightLost, "Approximate number of bytes evicted from the secondary index cache.", ValueType::Number) \
     M(QueryCacheHits, "Number of times a query result has been found in the query cache (and query computation was avoided). Only updated for SELECT queries with SETTING use_query_cache = 1.", ValueType::Number) \
     M(QueryCacheMisses, "Number of times a query result has not been found in the query cache (and required query computation). Only updated for SELECT queries with SETTING use_query_cache = 1.", ValueType::Number) \
+    M(QueryConditionCacheHits, "Number of times an entry has been found in the query condition cache (and reading of marks can be skipped). Only updated for SELECT queries with SETTING use_query_condition_cache = 1.", ValueType::Number) \
+    M(QueryConditionCacheMisses, "Number of times an entry has not been found in the query condition cache (and reading of mark cannot be skipped). Only updated for SELECT queries with SETTING use_query_condition_cache = 1.", ValueType::Number) \
     /* Each page cache chunk access increments exactly one of the following 5 PageCacheChunk* counters. */ \
     /* Something like hit rate: (PageCacheChunkShared + PageCacheChunkDataHits) / [sum of all 5]. */ \
     M(PageCacheChunkMisses, "Number of times a chunk has not been found in the userspace page cache.", ValueType::Number) \

diff --git a/src/Core/Defines.h b/src/Core/Defines.h
@@ -115,6 +115,9 @@ static constexpr auto DEFAULT_QUERY_CACHE_MAX_SIZE = 1_GiB;
 static constexpr auto DEFAULT_QUERY_CACHE_MAX_ENTRIES = 1024uz;
 static constexpr auto DEFAULT_QUERY_CACHE_MAX_ENTRY_SIZE_IN_BYTES = 1_MiB;
 static constexpr auto DEFAULT_QUERY_CACHE_MAX_ENTRY_SIZE_IN_ROWS = 30'000'000uz;
+static constexpr auto DEFAULT_QUERY_CONDITION_CACHE_POLICY = "SLRU";
+static constexpr auto DEFAULT_QUERY_CONDITION_CACHE_MAX_SIZE = 100_MiB;
+static constexpr auto DEFAULT_QUERY_CONDITION_CACHE_SIZE_RATIO = 0.5l;
 
 /// Query profiler cannot work with sanitizers.
 /// Sanitizers are using quick "frame walking" stack unwinding (this implies -fno-omit-frame-pointer)

diff --git a/src/Core/ServerSettings.cpp b/src/Core/ServerSettings.cpp
@@ -511,6 +511,10 @@ namespace DB
     DECLARE(UInt64, compiled_expression_cache_size, DEFAULT_COMPILED_EXPRESSION_CACHE_MAX_SIZE, R"(Sets the cache size (in bytes) for [compiled expressions](../../operations/caches.md).)", 0) \
     \
     DECLARE(UInt64, compiled_expression_cache_elements_size, DEFAULT_COMPILED_EXPRESSION_CACHE_MAX_ENTRIES, R"(Sets the cache size (in elements) for [compiled expressions](../../operations/caches.md).)", 0) \
+    DECLARE(String, query_condition_cache_policy, DEFAULT_QUERY_CONDITION_CACHE_POLICY, "Query condition cache policy name.", 0) \
+    DECLARE(UInt64, query_condition_cache_size, DEFAULT_QUERY_CONDITION_CACHE_MAX_SIZE, "Size of the query condition cache.", 0) \
+    DECLARE(Double, query_condition_cache_size_ratio, DEFAULT_QUERY_CONDITION_CACHE_SIZE_RATIO, "The size of the protected queue in the query condition cache relative to the cache's total size.", 0) \
+    \
     DECLARE(Bool, disable_internal_dns_cache, false, "Disable internal DNS caching at all.", 0) \
     DECLARE(UInt64, dns_cache_max_entries, 10000, R"(Internal DNS cache max entries.)", 0) \
     DECLARE(Int32, dns_cache_update_period, 15, "Internal DNS cache update period in seconds.", 0) \

diff --git a/src/Core/Settings.cpp b/src/Core/Settings.cpp
@@ -4377,7 +4377,14 @@ Possible values:
     DECLARE(Bool, enable_sharing_sets_for_mutations, true, R"(
 Allow sharing set objects build for IN subqueries between different tasks of the same mutation. This reduces memory usage and CPU consumption
 )", 0) \
-    \
+    DECLARE(Bool, use_query_condition_cache, false, R"(
+Enable the query condition cache.
+
+Possible values:
+
+- 0 - Disabled
+- 1 - Enabled
+)", 0) \
     DECLARE(Bool, optimize_rewrite_sum_if_to_count_if, true, R"(
 Rewrite sumIf() and sum(if()) function countIf() function when logically equivalent
 )", 0) \

diff --git a/src/Core/SettingsChangesHistory.cpp b/src/Core/SettingsChangesHistory.cpp
@@ -79,6 +79,7 @@ const VersionToSettingsChangesMap & getSettingsChangesHistory()
             {"output_format_parquet_bloom_filter_flush_threshold_bytes", 128 * 1024 * 1024, 128 * 1024 * 1024, "New setting."},
             {"output_format_pretty_max_rows", 10000, 1000, "It is better for usability - less amount to scroll."},
             {"restore_replicated_merge_tree_to_shared_merge_tree", false, false, "New setting."},
+            {"use_query_condition_cache", false, false, "New setting."},
             {"parallel_replicas_only_with_analyzer", false, true, "Parallel replicas is supported only with analyzer enabled"},
             {"s3_allow_multipart_copy", true, true, "New setting."},
         });

diff --git a/src/Interpreters/ActionsDAG.cpp b/src/Interpreters/ActionsDAG.cpp
@@ -26,6 +26,7 @@
 #include <stack>
 #include <base/sort.h>
 #include <Common/JSONBuilder.h>
+#include <Common/SipHash.h>
 #include <DataTypes/DataTypeSet.h>
 
 #include <absl/container/flat_hash_map.h>
@@ -135,6 +136,38 @@ void ActionsDAG::Node::toTree(JSONBuilder::JSONMap & map) const
         map.add("Compiled", is_function_compiled);
 }
 
+size_t ActionsDAG::Node::getHash() const
+{
+    SipHash hash_state;
+    updateHash(hash_state);
+    return hash_state.get64();
+}
+
+void ActionsDAG::Node::updateHash(SipHash & hash_state) const
+{
+    hash_state.update(type);
+
+    if (!result_name.empty())
+        hash_state.update(result_name);
+
+    if (result_type)
+        hash_state.update(result_type->getName());
+
+    if (function_base)
+        hash_state.update(function_base->getName());
+
+    if (function)
+        hash_state.update(function->getName());
+
+    hash_state.update(is_function_compiled);
+    hash_state.update(is_deterministic_constant);
+
+    if (column)
+        hash_state.update(column->getName());
+
+    for (const auto & child : children)
+        child->updateHash(hash_state);
+}
 
 ActionsDAG::ActionsDAG(const NamesAndTypesList & inputs_)
 {

diff --git a/src/Interpreters/ActionsDAG.h b/src/Interpreters/ActionsDAG.h
@@ -4,6 +4,7 @@
 #include <Core/ColumnsWithTypeAndName.h>
 #include <Core/NamesAndTypes.h>
 #include <Core/Names.h>
+#include <Common/SipHash.h>
 #include <Interpreters/Context_fwd.h>
 
 #include "config.h"
@@ -93,6 +94,9 @@ class ActionsDAG
         /// If result of this not is deterministic. Checks only this node, not a subtree.
         bool isDeterministic() const;
         void toTree(JSONBuilder::JSONMap & map) const;
+        size_t getHash() const;
+    private:
+        void updateHash(SipHash & hash_state) const;
     };
 
     /// NOTE: std::list is an implementation detail.

diff --git a/src/Interpreters/Cache/QueryConditionCache.cpp b/src/Interpreters/Cache/QueryConditionCache.cpp
@@ -0,0 +1,101 @@
+#include <Interpreters/Cache/QueryConditionCache.h>
+#include <Storages/MergeTree/MergeTreeData.h>
+#include "Interpreters/Cache/FileSegmentInfo.h"
+
+namespace ProfileEvents
+{
+    extern const Event QueryConditionCacheHits;
+    extern const Event QueryConditionCacheMisses;
+};
+
+namespace DB
+{
+
+QueryConditionCache::QueryConditionCache(const String & cache_policy, size_t max_size_in_bytes, double size_ratio)
+    : cache(cache_policy, max_size_in_bytes, 0, size_ratio)
+{
+}
+
+std::optional<QueryConditionCache::MatchingMarks> QueryConditionCache::read(const UUID & table_id, const String & part_name, size_t condition_hash)
+{
+    Key key = {table_id, part_name, condition_hash};
+
+    if (auto entry = cache.get(key))
+    {
+        ProfileEvents::increment(ProfileEvents::QueryConditionCacheHits);
+
+        std::lock_guard lock(entry->mutex);
+        return {entry->matching_marks};
+    }
+
+    ProfileEvents::increment(ProfileEvents::QueryConditionCacheMisses);
+
+    return std::nullopt;
+}
+
+void QueryConditionCache::write(const UUID & table_id, const String & part_name, size_t condition_hash, const MarkRanges & mark_ranges, size_t marks_count, bool has_final_mark)
+{
+    Key key = {table_id, part_name, condition_hash};
+
+    auto load_func = [&](){ return std::make_shared<Entry>(marks_count); };
+    auto [entry, _] = cache.getOrSet(key, load_func);
+
+    chassert(marks_count == entry->matching_marks.size());
+
+    /// Set MarkRanges to false, so there is no need to read these marks again later.
+    {
+        std::lock_guard lock(entry->mutex);
+        for (const auto & mark_range : mark_ranges)
+            std::fill(entry->matching_marks.begin() + mark_range.begin, entry->matching_marks.begin() + mark_range.end, false);
+
+        if (has_final_mark)
+            entry->matching_marks[marks_count - 1] = false;
+
+        LOG_DEBUG(
+            logger,
+            "table_id: {}, part_name: {}, condition_hash: {}, marks_count: {}, has_final_mark: {}, (ranges: {})",
+            table_id,
+            part_name,
+            condition_hash,
+            marks_count,
+            has_final_mark,
+            toString(mark_ranges));
+    }
+}
+
+void QueryConditionCache::clear()
+{
+    cache.clear();
+}
+
+void QueryConditionCache::setMaxSizeInBytes(size_t max_size_in_bytes)
+{
+    cache.setMaxSizeInBytes(max_size_in_bytes);
+}
+
+bool QueryConditionCache::Key::operator==(const Key & other) const
+{
+    return table_id == other.table_id && part_name == other.part_name && condition_hash == other.condition_hash;
+}
+
+QueryConditionCache::Entry::Entry(size_t mark_count)
+    : matching_marks(mark_count, true) /// by default, all marks potentially are potential matches
+{
+}
+
+size_t QueryConditionCache::KeyHasher::operator()(const Key & key) const
+{
+    SipHash hash;
+    hash.update(key.table_id);
+    hash.update(key.part_name);
+    hash.update(key.condition_hash);
+    return hash.get64();
+}
+
+size_t QueryConditionCache::QueryConditionCacheEntryWeight::operator()(const Entry & entry) const
+{
+    /// Estimate the memory size of `std::vector<bool>`, for bool values, only 1 bit per element.
+    size_t dynamic_memory = (entry.matching_marks.capacity() + 7) / 8; /// Round up to bytes.
+    return sizeof(decltype(entry.matching_marks)) + dynamic_memory;
+}
+}
diff --git a/src/Interpreters/Cache/QueryConditionCache.h b/src/Interpreters/Cache/QueryConditionCache.h
@@ -0,0 +1,66 @@
+#pragma once
+
+#include <Common/CacheBase.h>
+#include <Storages/MergeTree/MarkRange.h>
+
+namespace DB
+{
+
+/// Cache the mark filter corresponding to the query condition,
+/// which helps to quickly filter out useless Marks and speed up the query when the index is not hit.
+class QueryConditionCache
+{
+public:
+    /// 0 means none of the rows in the mark match the predicate. We can skip such marks.
+    /// 1 means at least one row in the mark matches the predicate. We need to read such marks.
+    using MatchingMarks = std::vector<bool>;
+
+    QueryConditionCache(const String & cache_policy, size_t max_size_in_bytes, double size_ratio);
+
+    /// Read the filter and return empty if it does not exist.
+    std::optional<MatchingMarks> read(const UUID & table_id, const String & part_name, size_t condition_hash);
+
+    /// Take out the mark filter corresponding to the query condition and set it to false on the corresponding mark.
+    void write(const UUID & table_id, const String & part_name, size_t condition_hash, const MarkRanges & mark_ranges, size_t marks_count, bool has_final_mark);
+
+    void clear();
+
+    void setMaxSizeInBytes(size_t max_size_in_bytes);
+
+private:
+    struct Key
+    {
+        const UUID table_id;
+        const String part_name;
+        const size_t condition_hash;
+
+        bool operator==(const Key & other) const;
+    };
+
+    struct Entry
+    {
+        MatchingMarks matching_marks;
+        std::mutex mutex;
+
+        explicit Entry(size_t mark_count);
+    };
+
+    struct KeyHasher
+    {
+        size_t operator()(const Key & key) const;
+    };
+
+    struct QueryConditionCacheEntryWeight
+    {
+        size_t operator()(const Entry & entry) const;
+    };
+
+    using Cache = CacheBase<Key, Entry, KeyHasher, QueryConditionCacheEntryWeight>;
+    Cache cache;
+
+    LoggerPtr logger = getLogger("QueryConditionCache");
+};
+
+using QueryConditionCachePtr = std::shared_ptr<QueryConditionCache>;
+
+}