ClickHouse / ClickHouse/ClickHouse

Uninterruptible CPU-bound function evaluation over a large value

Open
#112,203 14 comments 0 reactions 1 assignee Claimed by @george-larionov View on GitHub
clickgap-analyzed comp-query-execution culprit-pr-not-found
Dominant language
C++
Stars
49.9k
Forks
9k
Avg merge
20h 33m
Merged PRs (30d)
501

Description

## Summary

Expensive scalar functions (like `replaceRegexpAll`) are un-interruptible while running on single large value (e.g. long string). `KILL QUERY`, `max_execution_time`, and `OvercommitTracker` pressure is ineffective because there is no place to check for them. When the arguments are constant, the call additionally runs during **query analysis / planning** (`ActionsDAG::tryFoldFunctionToConstant` → `IExecutableFunction::executeImplDryRun`), *before* the execution pipeline exists — so it is outside the cancellation/time-limit machinery entirely.

This affects many functions, demonstrated below with `replaceRegexpAll`. Observed hanging ~16 min (963 s) on a single query in a stress run, tripping the `Hung check failed, possible deadlock found` detector.

## Reproducer

```sql
SELECT length(replaceRegexpAll(repeat(repeat('1', 1000000), 4), '[0-9]{1,3}', 'x'));
```

Both the input (`repeat(repeat('1', 1000000), 4)` — 4M characters) and the pattern are constant, so the call is folded during analysis. (The AST fuzzer generated this from `04496_jit_regexp_no_quadratic.sql`.)

## Evidence (from CI)

`Stress test (amd_tsan)`, sha `85359752060b481071afb23e26f93273904878e4` (v26.8.1). Processlist at hung-check time:

- `elapsed: 963.28`, `is_cancelled: 1` (cancellation requested, ignored), `peak_memory_usage: ~2.15 GiB`.
- `QueryAnalysisMicroseconds: 5890110`, `QueryPlanBuildMicroseconds: 5237410` — essentially all time is in analysis/planning, not execution.
- Hung thread stack (top frames):
```
re2::DFA::AnalyzeSearch / re2::DFA::Search → RE2::Match
DB::ReplaceRegexpImpl<…NameReplaceRegexpAll>::processString (src/Functions/ReplaceRegexpImpl.h:175)
DB::FunctionStringReplace<…>::executeImpl
DB::IExecutableFunction::defaultImplementationForConstantArguments
DB::IFunction::executeImplDryRun
DB::ActionsDAG::tryFoldFunctionToConstant
DB::PlannerActionsVisitorImpl::visitImpl → DB::buildExpressionAnalysisResult
DB::Planner::buildPlanForQueryNode
DB::InterpreterSelectQueryAnalyzer::getQueryPlan
```

## Root cause and scope

**The core issue: no interrupt point inside per-value evaluation.** `ReplaceRegexpImpl::processString` has no cancellation/deadline check. So one call over a single large value is atomic — nothing external can stop it until it returns.

Additionally (perhaps not relevant to the issue) constant folding means this all happens in `ActionsDAG::tryFoldFunctionToConstant` which has no interrupt machinery at all (so `max_execution_time`, `KILL QUERY`, and `OvercommitTracker` can't do anything anyway).

Execution phase polls for cancellation in between blocks, so the issue still persists there since the problem is a single large input.

Some similar situations are already handled:
- Oversized generators have hard caps: `repeat` (`max_repeat_times = 1'000'000`, `max_string_size = 1<<30`), `arrayWithConstant` (`max_array_size_in_columns_bytes = 1e9`, throws `TOO_LARGE_ARRAY_SIZE`), `range` (`function_range_max_elements_in_block`).
- Allocation-bound work is caught by memory tracking → `MEMORY_LIMIT_EXCEEDED`.

The uncovered quadrant is **compute-bound work over a large-but-legal value**: our 4 MB input is well under `repeat`'s 1 GiB cap, and the RE2 DFA burns CPU without allocating, so neither guard fires. Other functions with the same potential issue include the regex/search family (`replaceRegexp*`, `extractAll`, `countMatches`, `match`/`multiMatch*`, `like`/`ilike`), `*LevenshteinDistance*`/`editDistance` (genuinely O(n·m)), UTF-8/ICU transforms, and array functions (`arraySort`, `arrayDistinct`, `arrayIntersect`, lambda `arrayMap`/`arrayFilter`) over a big-but-legal array.

## Why it matters

The defect defeats the server's load-shedding/recovery mechanisms, which is the dangerous part under concurrency:

- `max_execution_time`, `KILL QUERY`, and `OvercommitTracker`'s "please stop and free memory" request are all ignored while the call runs.
- Client timeout + retry naturally produces multiple identical queries, and client disconnect doesn't interrupt the call, so stuck evaluations accumulate, each holding a request thread and memory.
- As memory approaches the cap, `OvercommitTracker` fires but cannot reclaim from the uninterruptible holders, so it kills innocent, interruptible queries (`Code: 241`) while the real holders persist — a memory-pinned state the server cannot recover from without a restart. Graceful shutdown then also waits on those threads (this is why the stress hung-check tripped).

Magnitude note: the 963 s figure is inflated by TSan (~5–15×) and RE2 DFA-cache thrashing under the stress config's memory pressure (the test is literally `04496_jit_regexp_no_quadratic`). In a normal build the same query is slow-but-finite; the reliability concern is the uninterruptibility/limit-bypass, not the exact duration.

## Suggested fix direction (suggested by AI)

Per-function checkpoints alone don't scale (whack-a-mole across dozens of functions). Prioritize the centralized levers:

1. **Govern constant-folding centrally.** `tryFoldFunctionToConstant` is a single choke point and always a size-1 call — give the dry-run a deadline (from `max_execution_time` / `max_estimated_execution_time`), a cancellation hook, and/or an input-size cap. This bounds the planning-phase amplifier for *every* function at once, with no per-row-loop reasoning needed.
2. **One cheap, shared, strided interrupt check** for the worst compute-bound per-element loops (e.g. `processString` and peers). Cost is negligible if done right: a relaxed atomic-flag load + `unlikely` branch, strided (every N iterations / N bytes, e.g. `if ((++counter & 0x3FFF) == 0)`) so it stays out of the innermost hot path and can't inhibit vectorization. Ideally driven by the existing real-time query-profiler signal (already fires ~1/s) setting a thread-local flag, so there is no new hot-path timing logic. (Caveat: this helps when the loop iterates during the hang — true for `replaceRegexpAll`'s incremental matching; a function whose long pole is one monolithic library call needs input bounding or a library-level deadline instead.)
3. The existing generator size caps + memory tracking already cover the oversized-generator and allocation-bound sub-classes — no need to re-solve those.

## Related

- Related: https://github.com/ClickHouse/ClickHouse/issues/47272 — "Allow cancelling queries in the middle of blocking operations." Same goal (queries must honor cancellation) but scoped to blocking *syscalls* (signal → `EINTR`) and explicitly *not* about `max_execution_time`. It does not address CPU-bound evaluation loops or the constant-folding/analysis phase, so this is a distinct case; a sufficiently general interrupt-flag framework could serve both if the project chooses to unify them.
- Surfaced via the generic `Hung check failed, possible deadlock found` bucket (https://github.com/ClickHouse/ClickHouse/issues/107941), which matches by test name only and does not track this specific cause.
- CI report: https://s3.amazonaws.com/clickhouse-test-reports/json.html?PR=110449&sha=85359752060b481071afb23e26f93273904878e4&name_0=PR&name_1=Stress%20test%20%28amd_tsan%29

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.