ClickHouse / ClickHouse/ClickHouse

Add a `string_bounds` column statistic for String columns

Open
#114,498 3 comments 0 reactions 0 assignees View on GitHub
comp-mergetree feature st-need-info
Dominant language
C++
Stars
49.9k
Forks
9k
Avg merge
21h 32m
Merged PRs (30d)
515

Description

### Company or project name

ClickHouse

### Use case

Column statistics currently give string predicates almost nothing:

- Range predicates (`url < 'https://m'`, `tenant BETWEEN 'a' AND 'b'`) fall through to the
hard-coded `default_cond_range_factor = 0.33`, because `tdigest`/`basic`/`minmax` estimation
is numeric-only.
- `LIKE` / `ILIKE` always get the hard-coded `default_like_factor = 0.1`, whether the pattern
matches 30% of rows or zero.
- Equality against an impossible constant (e.g. `WHERE code = 'USA'` on a column where every
value is 2 bytes long, or a constant outside the column's value range) is still estimated as
if it could match.
- `StatisticsPartPruner` only supports numeric MinMax, so parts can never be skipped based on
statistics for string predicates — even on tables naturally clustered by a string column
(tenant/customer IDs), unless the column is in the primary key or a skipping index.
- There are no min/max string length or alphabet (all-ASCII) statistics for width estimates or
future execution fast paths.

All of these gaps are served by _bounds_, not frequencies — a statistic that is tiny, cheap to
build, and losslessly mergeable.

### Describe the solution you'd like

A new opt-in, string-specific column statistic, `string_bounds(K)` (default `K = 16`), storing
per column per part:

- truncated **min/max value bounds** — first `K` bytes of the smallest/largest string, each with
an explicit exactness state (exact vs. truncated), compared bytewise (`memcmp` order);
- exact **min/max string byte length**;
- an **all-ASCII flag**;
- a non-null row counter for coverage accounting.

```sql
CREATE TABLE t (k UInt64, url String STATISTICS(basic, uniq_v2, string_bounds(16)))
ENGINE = MergeTree ORDER BY k;

ALTER TABLE t ADD STATISTICS url TYPE string_bounds(16);
ALTER TABLE t MATERIALIZE STATISTICS url;
```

Initial uses:

1. **Impossibility detection** for `=` / `IN`: constants outside the value bounds or length
bounds estimate to zero (before `mcv`/`countmin`/NDV machinery runs).
2. **Range estimation** for `<`, `<=`, `>`, `>=`, `BETWEEN` on strings: deterministic 0/all
classification at the bounds, with an optional (setting-gated) interpolated point estimate
in between.
3. **`LIKE 'prefix%'` / `startsWith`**: convert extractable fixed prefixes into ranges (reusing
the existing `KeyCondition` prefix machinery) instead of the constant `default_like_factor`.
4. **Part pruning**: extend `StatisticsPartPruner` to string columns via the per-part bounds.

Properties that make this the cheapest member of the statistics family: ~60 bytes per column per
part, one `memcmp`-dominated pass per block to build, and exact, order-independent merging with
no error terms — unlike `mcv`/`histogram`, merging never degrades accuracy.

Scope for v1: `String`, `Nullable(String)`, and `LowCardinality` wrappers; explicit opt-in only
(not in `auto_statistics_types`). `FixedString(N)` (which needs zero-padded comparison
normalization) and nullable part pruning are follow-ups.

### Describe alternatives you've considered

- **Extending the existing numeric `minmax` statistic to strings** — rejected: it stores exact
typed values, whereas string bounds must be truncated with explicit exactness states, and the
length/alphabet fields have no home there.
- **Relying on `mcv` / `countmin` for strings** — those cover per-value frequencies of heavy
hitters; they cannot answer range, prefix, or impossibility questions, and don't support
part pruning.
- **Putting length bounds / ASCII flag into `basic`** — viable later (its serialization allows
additions), but keeping v1 a self-contained opt-in statistic leaves the default write path
untouched.
- **Storing full (untruncated) min/max values** — rejected: a single pathological long string
would balloon a payload loaded during planning for every selected part; truncated bounds with
exactness markers are the approach proven by Parquet (`is_min/max_value_exact`) and ORC
(`lowerBound`/`upperBound`).

### Additional context

DuckDB's per-segment string statistics drew my attention to this area in ClickHouse, which can benefit from zonemap-style min/max metadata applied to strings; similar truncated string min/max statistics also exist in Parquet and ORC.

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing numeric statistics implementation and the StatisticsPartPruner and KeyCondition entry points; the issue does not name specific files or tests. Trace how statistics are defined, serialized, merged, and used for predicates, then determine how the proposed opt-in string_bounds statistic would cover String, Nullable(String), and LowCardinality. Done means the statistic supports the listed SQL operations and part pruning with tests for bounds, lengths, ASCII coverage, and merging.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, sql
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.