Feature: Auto-align string min/max truncate length so range pruning doesn't silently fail

[wubx]

Summary

String column min/max statistics are truncated to the first 16 characters by
default (STATS_STRING_PREFIX_LEN = 16). When a string column's distinguishing
bytes live after position 16 (very common for encodings like
date + fixed-prefix + serial), block-level range pruning becomes completely
ineffective: every block ends up with an identical [min, max], so range
pruning keeps all blocks and dumps the full workload onto the bloom stage.

The current remedy is to have the user manually declare
STATS_TRUNCATE_LEN N per column. This requires the user to (1) know the
option exists, (2) be able to read range pruning: A to B in EXPLAIN and
diagnose truncation, and (3) know the right length. Each of these is a wall
most users hit silently.

This issue proposes making the engine handle this automatically, backed by a
reproducible benchmark showing the cost of longer min/max is effectively zero.

Environment

• Databend Query v1.2.925-nightly-1f0ac2a483 (rust 1.94.0-nightly)
• FUSE engine, object storage backend
• 2,000,000,000 rows, ~2384 blocks

Reproduction

Two tables, identical 2B-row data, differing only in STATS_TRUNCATE_LEN.
The data has the first 16 chars identical across all rows; distinguishing
bytes start after position 16.

-- A: cluster key uses full 32 chars, but min/max uses default truncation (16)
CREATE TABLE cmp_a (
  contract_no VARCHAR NULL,
  notify_date INT NULL
) ENGINE=FUSE CLUSTER BY linear(SUBSTRING(contract_no FROM 1 FOR 32));

-- C: same clustering, but declares STATS_TRUNCATE_LEN 32 on the column
CREATE TABLE cmp_c (
  contract_no VARCHAR NULL STATS_TRUNCATE_LEN 32,
  notify_date INT NULL
) ENGINE=FUSE CLUSTER BY linear(SUBSTRING(contract_no FROM 1 FOR 32));

Prefix cardinality of the test data (sampled 20M rows):

prefix length	distinct values
first 16 chars	1
first 24 chars	709
full 32 chars	~20,000,000

Observed behavior

Point query WHERE contract_no = '<existing value>' on each table:

cmp_a (default truncate 16):

read rows: 5826593
blocks: <range pruning: 2384 to 2384 cost: 89 ms,
         bloom index read cost: 1568 ms,
         bloom pruning: 2384 to 7 cost: 1568 ms>

cmp_c (STATS_TRUNCATE_LEN 32):

read rows: 810592
blocks: <range pruning: 2381 to 17 cost: 6 ms,
         bloom index read cost: 19 ms,
         bloom pruning: 17 to 1 cost: 19 ms>

	cmp_a (default 16)	cmp_c (truncate 32)
block range pruning	2384 → 2384 (nothing pruned)	2381 → 17
blocks entering bloom	2384	17
bloom stage cost	1568 ms	19 ms
rows read	5.83M	0.81M

End-to-end cold point-query latency (querying 10 distinct values, one shot each,
to avoid bloom-meta cache hits):

	cmp_a (default 16)	cmp_c (truncate 32)
cold latency	1669–1753 ms	64–120 ms
average	~1700 ms	~90 ms

~19x slower, purely because the default 16-char truncation lands on a
non-distinguishing prefix.

Key finding: longer min/max costs effectively nothing

The usual objection to increasing truncation length is index bloat. Measured
via fuse_snapshot / fuse_block on the same 2B-row data:

	default 16 (cmp_a)	truncate 32 (cmp_c)	delta
uncompressed bytes	104,500,002,120	104,500,002,074	~0
on-disk size	11.719 GB	11.719 GB	0.006%
bloom index size	2,463,723,000	2,463,719,029	~0
block count	2384	2381	—

min/max is stored once per block, so extending each entry from 16 to 32
chars adds only tens of KB across 2384 blocks — negligible against 11.7 GB of
data. The storage saved by truncating to 16 is meaningless, yet it creates a
very hard-to-diagnose performance cliff.

Related trap: a non-prefix SUBSTRING in the cluster key silently breaks range pruning

There is a second, related pitfall worth calling out. Range pruning always uses
the original full column's min/max (truncated to STATS_STRING_PREFIX_LEN),
never the cluster-key expression. The cluster key only controls the physical
ordering of rows. So if the cluster key uses SUBSTRING(col FROM k FOR n)
with k > 1, the first k-1 chars are excluded from the sort order — and if
those skipped chars vary across rows, the original column's prefix min/max
overlaps across blocks and range pruning fails completely.

Verified with 5M-row tables, same data, differing only in the cluster key:

table	first 4 chars	cluster key	block range pruning
A	varying (cyclic)	SUBSTRING(col FROM 1 FOR 16) (from start)	6 → 1 (works)
B	varying (cyclic)	SUBSTRING(col FROM 5 FOR 12) (skips 4)	6 → 6 (fails)
C	fixed constant	SUBSTRING(col FROM 5 FOR 12) (skips 4)	6 → 1 (works)
D	random	SUBSTRING(col FROM 5 FOR 12) (skips 4)	6 → 6 (fails)
E	random	SUBSTRING(col FROM 1 FOR 16) (from start)	6 → 1 (works)

Summary of the rule:

skipped prefix	SUBSTRING from start	SUBSTRING skipping the prefix
fixed constant	works	works
varying / random	works	fails

So: a SUBSTRING cluster key that does not start at position 1 breaks
range pruning whenever the skipped leading chars vary (whether cyclic or truly
random). The only safe case is when the skipped prefix is a constant. This is
another instance where the physical ordering and the column-level min/max are
misaligned, and the engine gives no warning about it.

This strengthens proposal #4 below (diagnostics): a non-prefix SUBSTRING in a
cluster key on a string column is almost always a mistake worth warning about.

Proposed improvements (in priority order)

1. Auto-align truncate length to the cluster key (highest value)

The engine already knows the cluster key expression
(system.tables.cluster_by returns (SUBSTRING(contract_no FROM 1 FOR 32))).
If a user clusters by SUBSTRING(col FROM 1 FOR N), they clearly consider the
first N chars meaningful for ordering. At CREATE TABLE, the engine could parse
this and default that column's min/max truncate length to N (unless the user
set STATS_TRUNCATE_LEN explicitly). This eliminates the self-contradictory
"cluster by 32 / stats by 16" configuration at the source, which is exactly the
bug in this report.

2. Adaptive truncation at write time

When writing a block, the engine already scans the column to compute min/max.
It could also note where min and max diverge. If they are still identical at 16
chars, extend the stored prefix until they differ (capped at e.g. 64/128). Cost
is a few extra bytes per block (negligible, as shown); benefit is zero user
involvement.

3. Raise the default STATS_STRING_PREFIX_LEN

16 is overly conservative given the measured near-zero cost. A larger default
(e.g. 64) would cover most real-world encodings (order/contract numbers, UUIDs,
phone+timestamp). Best as a global fallback stacked with (1)/(2).

4. If auto-alignment is out of scope: at least warn and diagnose

Even without automatic behavior, the engine could surface the misalignment:

• CREATE-time warning when a string column's effective STATS_TRUNCATE_LEN
  is shorter than the length implied by its cluster key (e.g. cluster by
  SUBSTRING(col FROM 1 FOR 32) but stats truncate at 16).
• CREATE-time warning when a cluster key uses a non-prefix
  SUBSTRING(col FROM k FOR n) with k > 1 on a string column — as shown in
  the "Related trap" section, this almost always defeats range pruning.
• EXPLAIN hint when block range pruning keeps ~100% of blocks
  (range pruning: N to N) on an equality filter over a string column, pointing
  at likely min/max truncation.

These are cheap to implement and would turn a silent performance cliff into an
actionable message.

Rationale

Measured storage cost of longer min/max is negligible, so a conservative
default that saves almost no space should not be traded for a performance cliff
users cannot easily self-diagnose. Having the engine do the right thing
automatically is friendlier than requiring users to discover and declare a
per-column option.

[wubx]

https://gist.github.com/wubx/c7a7d754ec5ec7d84b3aa7945bafec3f