Cache the finalized cardinality in uniq_v2 statistics

Project: ClickHouse/ClickHouse | Language: C++ | Concepts: caching, algorithmic-optimization, testing-strategy | Difficulty: mid
Link: https://github.com/ClickHouse/ClickHouse/pull/113357

The problem

The uniq_v2 statistics estimator was recomputing the number of distinct values (cardinality) every time it was requested, even if the underlying data had not changed. This caused significant redundant computation during query planning, especially for wide tables with many columns, leading to slow query planning times.

Why it's non-trivial

A naive fix might just cache the last computed value, but this is unsafe unless the cache is always invalidated whenever the underlying statistics state changes (e.g., after merges, deserialization, or data updates). Failing to do so could return stale or incorrect results. The fix must also be thread-safe and efficient, since statistics may be accessed concurrently during query planning.

The approach

1. Add a cache field for cardinality

A new atomic member variable is introduced to cache the cardinality result, with a sentinel value of 0 meaning "not computed yet":

+    /// Cached result of estimateCardinality + 1. Zero (0) means "not computed yet".
+    mutable std::atomic<UInt64> cached_cardinality_plus_one{0};

This is added to the StatisticsUniqV2 class. The "+1" encoding allows distinguishing between the legitimate cardinality value 0 (all values are NULL) and the "not computed yet" sentinel.

2. Use the cache in estimateCardinality()

The main logic of estimateCardinality() is updated to check the cache before recomputing, and to store the computed value for future calls:

+    if (UInt64 cached = cached_cardinality_plus_one)
+        return cached - 1;

If the cache is set, it returns the cached value minus one (to undo the "+1" encoding).

If not cached, it computes the cardinality as before, then caches it:

+    const UInt64 cardinality = column->isNullAt(0) ? 0 : column->getUInt(0);
+
+    cached_cardinality_plus_one = cardinality + 1;
+
+    return cardinality;

This ensures that subsequent calls are fast and avoid redundant computation.

3. Add a performance test for plan-time statistics

A new test fixture is added to measure the planning time impact of this optimization. It creates a table with 401 statistics columns and runs an EXPLAIN PLAN query with many conditions, ensuring that the statistics code path is exercised:

+    <!--
+        Plan-time cost of uniq_v2 statistics, which no other performance test covers.
+        ...
+    -->
+    <settings>
+        <allow_statistics>1</allow_statistics>
+        <use_statistics>1</use_statistics>
+        <materialize_statistics_on_insert>1</materialize_statistics_on_insert>
+    </settings>
+    <create_query>
+        CREATE TABLE tab (
+            k UInt64,
+            c0 UInt64, c1 UInt64, ..., c399 UInt64
+        )
+        ENGINE = MergeTree ORDER BY k
+        SETTINGS auto_statistics_types = 'basic, uniq_v2', min_bytes_for_wide_part = 0
+    </create_query>
+    ...
+    <query><![CDATA[
+        EXPLAIN PLAN SELECT count() FROM tab WHERE c0 != 1000 AND c1 != 1001 AND ...
+    ]]></query>

This test ensures that future changes do not regress the performance improvement.

From the review thread

No notable review discussion on this PR.

Takeaways

• Cache expensive pure computations, but always invalidate or recompute the cache when the underlying state may change.
  Use a sentinel value to distinguish "not computed" from valid results, especially when 0 is a valid value.

• Performance tests should target the real-world bottleneck, not just correctness.
  Adding a test that measures planning time with wide tables and many columns ensures that the optimization is both effective and protected against regression.

• Use atomic variables for caches that may be accessed concurrently, even if the computation is idempotent.
  This prevents data races and ensures thread safety in read-mostly scenarios.