Return early for constant sorting keys

perfloop/clickhouse · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_8ebwekrder

Verdict

VERIFIED · settled 2026-08-07 · merged as ClickHouse/ClickHouse#113899

What happened: The paired measurements met the required improvement.

Hypothesis

Source inspection of src/Interpreters/sortBlock.cpp showed that getColumnsWithSortDescription marks each resolved key as column_const (lines 102–125), while isAlreadySorted only uses those descriptors to detect collation before calling isAlreadySortedImpl (lines 391–417). That implementation then visits every adjacent row (lines 288–290); PartialSortingLess skips constant descriptors, so when all sorting keys are constant every comparison deterministically returns equal. Inspection of MergeTreeDataWriter.cpp showed this probe runs once per writeTempPartImpl invocation with a nonempty sort description before stableGetPermutation (lines 775–785). No runtime profile was run, so the CPU impact remains hypothesized. The removed delta is the O(N × K) row-pair/constant-key loop for an N-row INSERT block with K all-constant sort keys, at one probe per part-write. Confirm with a focused isAlreadySorted or writeTempPartImpl benchmark sweeping 64K, 256K, and 1M rows and one versus multiple ColumnConst keys; CPU samples or an instrumented comparison counter should show the row-comparison loop disappear while sortedness and output permutations remain unchanged.

Change to test: While isAlreadySorted scans resolved sort columns for collation, also track whether every descriptor is column_const and return true before constructing the comparator or scanning row pairs. Retain the existing collation and adjacent-row paths whenever any sort key is non-constant.

Where it lives

perfloop/clickhouse · src/Storages/MergeTree/MergeTreeSink.cpp

Evidence

MergeTree inserts with constant and mixed sorting keys at 64K, 256K, and 1M rows · 10 sample pairs

metric baseline candidate paired median change confidence range required result
constant_sorting_us_65536_1key 66 2 −97% (−64) −90 to −56 < −1 PASSED
constant_sorting_us_262144_1key 266.8 2 −99.3% (−264.8) −296 to −243 < −1 PASSED
constant_sorting_us_1000000_1key 1106 2 −99.7% (−1103) −1160 to −1020 < −1 PASSED
constant_sorting_us_65536_4keys 296.5 3 −99% (−293.5) −295 to −293 < −1 PASSED
constant_sorting_us_262144_4keys 1168 3 −99.7% (−1165) −1167 to −1164 < −1 PASSED
constant_sorting_us_1000000_4keys 4449 4 −99.9% (−4445) −4491 to −4439 < −1 PASSED
constant_insert_end_to_end_latency_us_1000000_4keys 24548 20201 −17.5% (−4302) −4723 to −3735 < −1000 PASSED
constant_insert_cpu_us_1000000_4keys 20732 16301 −20.6% (−4261) −5581 to −3673 < −1000 PASSED
mixed_sorting_us_65536_1key 135 134 −0.7% (−1) −3 to 0 ≤ 50 PASSED
mixed_sorting_us_262144_1key 547.8 528 −3.6% (−19.75) −23.5 to −18.5 ≤ 100 PASSED
mixed_sorting_us_1000000_1key 2067 1948 −5.8% (−119.5) −138 to −103 ≤ 500 PASSED
mixed_sorting_us_65536_4keys 224 232 +3.8% (+8.5) +5 to +14.5 ≤ 50 PASSED
mixed_sorting_us_262144_4keys 892 922.5 +3.8% (+33.75) +19 to +45 ≤ 100 PASSED
mixed_sorting_us_1000000_4keys 3400 3500 +2.9% (+100) +5 to +178.5 ≤ 500 PASSED

Checks: 1 of 1 passed. Verification: no defect found.

Timeline