Workflow [PR], commit [8dc97c8]

Summary: ✅

• Performance Comparison: Performance dashboard

AI Review

Summary

The PR replaces the contiguous ::sort path with ipnsort, adds stableSort backed by driftsort for contiguous stable sorts, wires the new contrib headers through CMake, and adds focused unit coverage for ordering, stability, alignment, non-default-constructible trivial types, and move-path exception safety. I rechecked the current diff and prior threads; the previous blocker-level issues are addressed, and I found no remaining review findings.

Final Verdict

Status: ✅ Approve

📊 Cloud Performance Report

🔴 AI verdict: degradation — 1 regressed, 4 improved out of 38 analysed

This PR swaps the core sorting implementations: ipnsort replaces pdqsort for unstable sort and driftsort replaces std::stable_sort, so any query doing an ORDER BY or merge is directly affected. Four of the five flagged queries improve in line with a faster sort: clickbench Q22 (-25%) and Q23 (-33%), and TPC-H Q7 (-35%) and Q20 (-50%, though that one's measurements were noisy). The one regression, clickbench Q13 (+11%), runs against the trend and compounds an existing degradation already visible on master, so it's worth a closer look.

clickbench

🔴 1 regressed · 🟢 2 improved

tpch_adapted_1_official

🟢 2 improved

@groeneai, fix integration tests,

test_profile_max_sessions_for_user
test_disks_app_interactive

which could wrongly assert the unstable sort order result, and send a PR with the fix.

@alexey-milovidov fix PR #106730.

test_disks_app_interactive: hardened the ls helper in the test to sort listings on the Python side, decoupling assertions from the disks app sort order. Verified via simulation that reverse and shuffled server output now both pass (old helper fails on either).

test_profile_max_sessions_for_user: reviewed each assertion and found nothing order-dependent — the test uses substring expect, assert_logs_contain_with_retry, and discards KILL QUERY output. No list comparisons. If you have a specific assertion in mind I missed, please point at it and I will follow up.

Continued work on this PR:

• Merged master (clean, 0 conflicts). The branch was ~1420 commits behind. This brings in two fixes that clear most of the red CI:
  • Fix test_disks_app_interactive ls helper to be robust to disks app sort order #106730 (Fix test_disks_app_interactive ls helper to be robust to disks app sort order) — the test_disks_app_interactive timeouts were caused by this PR's unstable ::sort changing the disks-app ls output order; the test was made order-robust on master.
  • Fix LOGICAL_ERROR Virtual row boundary violated under read-in-order over Union #106664 (Fix LOGICAL_ERROR Virtual row boundary violated under read-in-order over Union) — clears the Virtual row boundary violated in MergingSortedAlgorithm (STID 2651-3359) and the co-occurring Server died in amd_debug stateless (the LOGICAL_ERROR aborts the server in debug builds).
• Exception-safety fix (contrib/ipnsort/ipnsort.h, commit 2a6b1bff57a) is now built and validated: ran unit_tests_dbms Sort.*, all 6 tests pass including the new Sort.MoveBasedPartitionExceptionSafety. The corresponding review thread is resolved.
• The remaining test_profile_max_sessions_for_user timeout (amd_msan integration) is an unrelated low-frequency flake — it has failed on master/other PRs (Fix memory usage growth in fs cache #106387, Make Profile Events ±30x faster by using Per CPU atomics for server-wide and users #105056) and is a session-count test with no relation to sorting.

The one open review thread — the tpch_adapted_1 query 4 perf flag on base/base/sort.h — is left for your call (perf/gating judgment on the broad ::sort switch).

Pushed 979096a704f.

@groeneai, also submit a fix for test_disks_app_interactive in a separate PR, so we can merge that sooner.

By the way, it is still failing in this PR.

@alexey-milovidov separate fix opened: #107262

The still-failing case here is not sort order (that was handled by #106730, whose robustness commits are already on this branch). It is a spurious TimeoutError: Disks client returned no output in the test harness: execute_query waited only 5s for the clickhouse disks subprocess to produce output, and under amd_msan at high host parallelism the subprocess gets CPU-starved past 5s on trivial cleanup commands. CIDB shows it amd_msan only, 0 master failures in 14 days. The PR raises that deadline to 60s; the 900s pytest-timeout still guards real hangs. Test-only, targets master so it can merge independently.

Pushed 4d9da60f03d (merged master up to date; was ~2 days behind and red).

test_disks_app_interactive (amd_msan) — fixed

This was the only PR-related failure. History on play.clickhouse.com shows it fails only on amd_msan (the slowest sanitizer) and intermittently (~2 FAIL / 8 OK per run), never on asan/tsan/coverage/arm and never on master (3260 OK on msan). A correctness bug in the new sort would fail deterministically on every build — this is a timing/protocol flake instead.

Root cause: the test drives clickhouse disks --test-mode over pipes and uses the \a\a\a\a separator on stdout as the end-of-command marker. execute_query polled once and, if a stderr log line arrived first, read a single stderr line and returned without consuming the stdout separator, desyncing every subsequent command. Under msan (where log timing varies more) this surfaced as TimeoutError: Disks client returned no output during teardown rm. Fix: keep polling until the stdout separator is actually seen, drain stderr separately, and use a generous timeout. The disks app does not use the sort engine this PR changes (CommandList uses std::sort; DiskLocal uses fs::remove_all / directory_iterator), so this is a test-protocol fix, not a product change.

Unrelated CI failure

The Stateless tests (arm_asan_ubsan, azure, parallel) reds (04033_tpc_ds_q04/q33/q69, 00376_shard_group_uniq_array_of_int_array, 00050_min_max, 03272_json_with_progress, 01710_projections_...) are a runner-wide OOM batch: multiple parallel queries failing at the same timestamp with current RSS: 53.70 GiB, maximum: 53.69 GiB (MEMORY_LIMIT_EXCEEDED / OvercommitTracker), and the 01710 UNKNOWN_TABLE is a cascade. These will get fresh CI on the push.

@groeneai, please take a look at the arm_asan_ubsan runner-OOM batch flake on this PR if it recurs after the rerun: https://s3.amazonaws.com/clickhouse-test-reports/json.html?PR=106650&sha=979096a704f567400b11f081f20bfab1bd2f2b7f&name_0=PR&name_1=Stateless%20tests%20%28arm_asan_ubsan%2C%20azure%2C%20parallel%29

@alexey-milovidov Confirmed: runner-wide OOM, not a #106650 sort bug.

On 979096a704f5 the 9 arm_asan_ubsan, azure, parallel reds are all OvercommitTracker MEMORY_LIMIT_EXCEEDED (rc 241) at current RSS: 53.85 GiB, maximum: 53.69 GiB (the azure runner cap), clustered in one ~50s server window. The rc-210 Connection reset ones (q33, 01710, 03991) and the 01710 UNKNOWN_TABLE are cascades from the same event. Scope rules out the PR: that exact check failed 758 distinct tests across 94 distinct PRs on 2026-06-10. A sort regression would fail deterministically on every build; these are host-memory victims that pass on rerun.

The rerun on 4d9da60f03d has not reached that job yet (only Fast test / Style / Config done so far). I will re-check when arm_asan_ubsan, azure, parallel completes and only flag it if it recurs with a non-OOM signature; a repeat OOM is the same infra and clears on rerun.

@groeneai, fix AST fuzzer (amd_debug, targeted): Logical error: Not-ready Set is passed as the second argument for function 'A (STID: 0250-424f).

@alexey-milovidov The AST fuzzer "Not-ready Set" (STID 0250-424f) is not a regression of this PR. It is a pre-existing DDL-validation hole: a key expression like ORDER BY (x IN some_table) is accepted at CREATE and then crashes on the first INSERT, because the writer evaluates the key but the IN set is never built. x IN (SELECT ...) is already rejected (subquery check), but the table-identifier RHS slips through.

Fix in a separate PR: #107424 - extends the existing key-expression check to also reject IN with a table on the RHS (ORDER BY / PRIMARY KEY / PARTITION BY / skip INDEX). Literal sets like x IN (1,2,3) stay allowed.

Reproducer (deterministic, plain master):

CREATE TABLE t (x Int32) ENGINE = Memory;
CREATE TABLE u (a Int32) ENGINE = MergeTree ORDER BY (a IN t) AS SELECT 1;
-- Logical error: Not-ready Set ...

LLVM Coverage Report

Changed lines: Changed C/C++ lines covered by tests: 206/222 (92.79%) | Lost baseline coverage (was covered on master, now uncovered in this PR): 1 line(s) · Uncovered code

Full report · Diff report

The only red on the current head (8dc97c8b23f) is Performance Comparison (amd_release, master_head, 4/6); everything else is green (CH Inc sync, Style check, all functional/integration/sanitizer jobs). The Mergeable Check and PR failures are just aggregates of that one shard.

The flagged queries are run-to-run noise on amd/4, not regressions from this change:

• Cross-shard inconsistency proves machine noise. 11 of the 17 "slower" queries are on amd/4. The same queries are not flagged on the corresponding arm/4 shard: direct_dictionary (a dictGet/dictHas workload with no sort) and string_subcolumn_in_tuple (SELECT count() ... WHERE NOT ignore(t.sN), also no sort) are flagged slower on amd/4 but clean on arm/4. Sort-unrelated queries regressing on one runner but not the architectural twin is the signature of a slow runner in that run, not a code change.
• The "sort-shaped" regressions don't touch the changed code. order_with_limit (#0/#2/#6/#11/#13/#16) and sparse_column #40 (ORDER BY str DESC LIMIT 100) all carry a LIMIT. This PR only swaps the full sort primitive (::sort → ipnsort, plus the new ::stableSort); partial_sort and nth_element are unchanged. IColumn::getPermutationImpl routes any 0 < limit < data_size to partial_sort and reaches the changed ::sort only when limit == 0. For these LIMIT n queries (n = 1…15000, well under the block size) every block goes through the unchanged partial_sort, so the new path is never exercised.

I re-ran the amd/4 Performance Comparison shard to get a confirming run.

SQL-level benchmark (synthetic + ClickBench + TPC-H)

I ran a clean A/B of this branch against the master sort path to see how the change lands on real queries.

Setup. Two builds of 26.6.1.1, same RelWithDebInfo config, pointed at the same data dir:

• baseline — master sort path (pdqsort for ::sort, std::stable_sort);
• ipnsort — this branch (ipnsort for ::sort, driftsort for ::stableSort).

Datasets: ClickBench hits (100M), TPC-H SF1, and synthetic 50M-row tables. Each query: 1 warm-up + 3 timed runs, min wall-clock, FORMAT Null. Control queries (radix ORDER BY, scan-only) match to ~1.0×, so the deltas are attributable to the sort.

Key finding

ORDER BY on <=64-bit numerics uses radix sort (untouched by this PR). The comparison ::sort is reached by String / FixedString / Decimal128-256 / Int128-256 / arraySort / multi-column tie-breaks.

At production parallelism (96 threads) a full ORDER BY is dominated by the unchanged serial k-way merge of small per-chunk sorts, so the sort swap is invisible there — no regression, no speed-up. The win shows where the comparison sort actually dominates the query, and through ClickHouse's indirect, cache-missing permutation comparator it is a realistic ~1.1–1.55× (not the 3× of the raw-UInt64 microbenchmark, which goes through radix in SQL anyway). driftsort is not SQL-visible: the windowFunnel / sequenceNextNode per-group stable sort is a tiny fraction of those aggregates with a cheap timestamp comparator.

Where it shows

arraySort is the cleanest case — a per-row sort with no merge and no block-materialization:

CREATE TABLE arrs (a Array(String)) ENGINE = MergeTree ORDER BY tuple();
INSERT INTO arrs SELECT arrayMap(i -> lower(hex(sipHash64(number, i))), range(200)) FROM numbers_mt(100000);
SELECT arraySort(a) FROM arrs FORMAT Null;                 -- 0.864s -> 0.557s  = 1.55x

Few-unique strings (sort dominates), and single-thread / large-block sorts that bypass the parallel merge:

SELECT s FROM s_fewunique ORDER BY s FORMAT Null;          -- 50M, ~100 distinct, 96 threads: 0.213 -> 0.167 = 1.28x

-- one big sort, no parallel merge:
SELECT s FROM s_rand    ORDER BY s SETTINGS max_threads = 1, max_block_size = 200000000 FORMAT Null;  -- 50M String:    32.41 -> 27.04 = 1.20x
SELECT s FROM s_fewunique ORDER BY s SETTINGS max_threads = 1, max_block_size = 200000000 FORMAT Null;-- 50M few-unique:  5.05 ->  3.75 = 1.35x
SELECT x FROM dec_rand  ORDER BY x SETTINGS max_threads = 1, max_block_size = 200000000 FORMAT Null;  -- 50M Decimal128: 17.38 -> 15.70 = 1.11x
SELECT x FROM i128_rand ORDER BY x SETTINGS max_threads = 1, max_block_size = 200000000 FORMAT Null;  -- 50M Int128:     13.52 -> 12.28 = 1.10x

TPC-H SF1 — single-threaded text-column sorts:

SELECT l_comment FROM lineitem ORDER BY l_comment SETTINGS max_threads = 1 FORMAT Null;  -- 6M:    2.44 -> 2.10 = 1.16x
SELECT o_comment FROM orders   ORDER BY o_comment SETTINGS max_threads = 1 FORMAT Null;  -- 1.5M:  0.53 -> 0.45 = 1.18x
SELECT p_name    FROM part     ORDER BY p_name    SETTINGS max_threads = 1 FORMAT Null;  -- 200k:  0.047 -> 0.035 = 1.34x

Single-thread / large-block summary, min wall-clock seconds:

Where it's masked — full ORDER BY at 96 threads (merge-bound, "no regression")

SELECT URL FROM hits ORDER BY URL FORMAT Null;                                 -- 100M: 5.53 -> 5.45 = 1.01x
SELECT URL, Title, Referer FROM hits ORDER BY URL, Title, Referer FORMAT Null; -- 100M, 3-col: 12.28 -> 12.09 = 1.02x
SELECT WatchID FROM hits ORDER BY WatchID FORMAT Null;                         -- radix CONTROL: 9.22 -> 9.18 = 1.00x

ORDER BY Title / Referer (100M), synthetic 50M random String/Decimal128/Int128 at 96 threads, and windowFunnel / sequenceNextNode are all ~1.0× as well.

Notes

• The microbenchmark speed-ups don't translate to ORDER BY wall-clock at default parallelism — the per-chunk sorts are small and the serial merge dominates. Worth stating so reviewers don't expect 3× on ORDER BY.
• The cleanest SQL demonstration is arraySort on a large array column (per-row, no merge) — a good candidate for a tests/performance test (1.55× here).
• A simple reverse-sorted Decimal128 input is not a pdqsort worst case here (both ~0.05s) — pdqsort's pattern detection already handles it; the reverse-sorted worst-case removal isn't reproduced by a plain reverse-sorted SQL input.