Applying CUSUM Drift Detection to Plan Cost Series

CUSUM (cumulative sum) change-point detection catches the regression that fixed thresholds are structurally blind to: a plan cost that creeps up a fraction of a percent per deploy until, weeks later, the query is twice as expensive without any single sample ever breaching a per-sample gate. This runbook applies a two-sided CUSUM control scheme to a per-fingerprint plan-cost time series, tunes its slack and decision-interval parameters to a target false-alarm rate, and ships a streaming implementation with structured logs and OpenTelemetry metrics. It is the accumulating-evidence complement to the static gates described in Tuning Thresholds for False Positive Reduction.

Symptom Identification and Production Thresholds #

A fixed gate asks a memoryless question of every sample: is this one point over the line? Slow drift answers “no” every single time while the mean marches upward. CUSUM instead accumulates the signed distance of each sample from a reference mean, so small persistent excursions add up until they cross a decision interval. Standardize every cost sample as $z_{i} = (x_{i} − \mu 0) / \sigma 0$ against the anchored baseline mean $\mu 0$ and standard deviation $\sigma 0$, then treat these as breach conditions:

1. Sub-threshold upward drift. The per-sample cost delta stays below the static gate of 0.12 (12%) for $\ge 40$ consecutive captures, yet the trailing 50-sample mean rises by more than $0.8\sigma 0$ relative to $\mu 0$. No single point trips the gate; the trend is unmistakable.
2. High-side statistic breach. The one-sided upper sum S_h exceeds the decision interval h = 5.0 (in standardized units) with slack k = 0.5. This pairing targets a sustained $1\sigma 0$ mean shift and yields an in-control average run length near 465 samples — roughly one false alarm per 465 clean captures.
3. Persistent positive increments. The number of consecutive samples for which S_h strictly increases reaches $\ge 8$, confirming the excursion is directional rather than a symmetric wobble around the mean.
4. Baseline mean escape. The 50-sample rolling mean of raw cost leaves the band $\mu 0 \pm 2\sigma 0$ and does not return within 10 samples, indicating the process center itself has moved rather than a transient spike.

Fire on condition 2 as the primary trigger. Conditions 1, 3, and 4 are corroborating evidence you attach to the alert so an on-call engineer can distinguish a genuine change point from a mistuned detector.

Root Cause Analysis #

When a CUSUM detector misbehaves it is almost always because a parameter or a baseline assumption is wrong, not because the math failed. Three failure domains account for nearly every misfire.

Mistuned slack parameter k. The slack k is the reference value subtracted from each standardized sample; it sets the smallest sustained shift the chart will accumulate. Setting k too small (below 0.25) makes the sum drift upward on ordinary noise and floods on-call with false change points; setting it too large (above 1.0) lets a real $1\sigma 0$ creep pass unaccumulated. The canonical choice detects a shift of 2k standard deviations, so k = 0.5 targets a $1\sigma 0$ move. Diagnose a mistuned k by replaying history and counting alerts against known-clean windows:

-- Pull the per-fingerprint cost series to replay CUSUM offline
SELECT captured_at,
       plan_cost,
       avg(plan_cost) OVER w AS roll_mean,
       stddev_samp(plan_cost) OVER w AS roll_std
FROM plan_cost_series
WHERE query_fingerprint = $1
  AND captured_at >= now() - interval '30 days'
WINDOW w AS (ORDER BY captured_at ROWS BETWEEN 49 PRECEDING AND CURRENT ROW)
ORDER BY captured_at;

If replaying the last 30 days with your current k produces more than one alert per 465 clean samples, k is too small.

Non-stationary baseline. CUSUM assumes the in-control mean $\mu 0$ and deviation $\sigma 0$ are fixed. Legitimate capacity events — a hardware upgrade, a data-retention purge, an intentional index build — shift the true center, and a detector anchored to a stale $\mu 0$ will fire forever. After any approved change point, re-estimate $\mu 0$ and $\sigma 0$ from the new regime and reset the statistic to zero. The anchored baseline that seeds $\mu 0$ should come from the dynamic-threshold machinery in Setting Dynamic Thresholds for Query Regression Alerts, not from a hand-set constant.

Seasonality and autocorrelation. Plan cost for many workloads has a diurnal or weekly rhythm — batch loads inflate estimates every night at 02:00, month-end reporting widens scans. Raw CUSUM interprets a predictable daily rise as drift. Deseasonalize before standardizing by subtracting a same-phase moving average (for example, the value 24 hours prior) so the detector sees residuals, not the seasonal component. Where the drift is better characterized as a shift in the whole cost distribution rather than its mean, reach instead for the divergence measures in Statistical Distance Algorithms for Plan Drift.

Step-by-Step Remediation #

The implementation is a streaming two-sided CUSUM: it reads the per-fingerprint cost series from the store, standardizes each sample against the anchored baseline, updates the upper and lower sums, and emits a change point with structured context the moment either sum crosses the decision interval.

1. Instantiate the detector with tuned parameters. Seed $\mu 0$ and $\sigma 0$ from the anchored baseline, set k = 0.5 and h = 5.0.

import asyncio
from dataclasses import dataclass

import asyncpg
import structlog
from opentelemetry import metrics

log = structlog.get_logger("cusum.plancost")
meter = metrics.get_meter("cusum.plancost")

_sh_gauge = meter.create_gauge("cusum_upper_sum", description="upper CUSUM statistic S_h")
_cp_counter = meter.create_counter("cusum_change_point_total", description="emitted change points")


@dataclass
class CusumState:
    baseline_mean: float
    baseline_std: float
    slack_k: float = 0.5          # targets a 1σ mean shift
    interval_h: float = 5.0       # ARL0 ≈ 465 samples in control
    s_high: float = 0.0
    s_low: float = 0.0
    run_length: int = 0

    def update(self, x: float) -> str:
        sigma = max(self.baseline_std, 1e-9)
        z = (x - self.baseline_mean) / sigma
        self.s_high = max(0.0, self.s_high + z - self.slack_k)
        self.s_low = max(0.0, self.s_low - z - self.slack_k)
        self.run_length += 1
        if self.s_high > self.interval_h:
            verdict = "DRIFT_UP"
        elif self.s_low > self.interval_h:
            verdict = "DRIFT_DOWN"
        else:
            verdict = "IN_CONTROL"
        return verdict

    def reset(self) -> None:
        self.s_high = self.s_low = 0.0
        self.run_length = 0

2. Stream the series and act on the first crossing. Reset the statistic on emission so one change point does not cascade into a storm of duplicates.

SERIES_SQL = """
SELECT captured_at, plan_cost
FROM plan_cost_series
WHERE query_fingerprint = $1
ORDER BY captured_at
"""


async def run_detector(dsn: str, fingerprint: str,
                       baseline_mean: float, baseline_std: float) -> None:
    state = CusumState(baseline_mean=baseline_mean, baseline_std=baseline_std)
    pool = await asyncpg.create_pool(dsn, min_size=1, max_size=2)
    try:
        async with pool.acquire() as conn:
            async for record in conn.cursor(SERIES_SQL, fingerprint):
                verdict = state.update(float(record["plan_cost"]))
                _sh_gauge.set(state.s_high, {"fingerprint": fingerprint})
                if verdict != "IN_CONTROL":
                    _cp_counter.add(1, {"fingerprint": fingerprint, "direction": verdict})
                    log.warning("cusum_change_point", fingerprint=fingerprint,
                                direction=verdict, s_high=round(state.s_high, 2),
                                run_length=state.run_length,
                                at=record["captured_at"].isoformat())
                    state.reset()
    finally:
        await pool.close()


if __name__ == "__main__":
    import os
    asyncio.run(run_detector(os.environ["QP_STORE_DSN"], "b7c1e2", 1840.0, 96.0))

3. Read the emitted change point. A confirmed upward drift produces one structured line pinpointing the sample where the accumulated evidence crossed h:

2026-07-18T09:41:06Z [warning] cusum_change_point fingerprint=b7c1e2 direction=DRIFT_UP s_high=5.37 run_length=52 at=2026-07-18T09:40:00Z

4. Validate, then re-anchor. Confirm the drift on a replica with EXPLAIN (ANALYZE, BUFFERS) and compare estimated cost against the baseline. If the new cost regime is legitimate (approved capacity change), re-estimate $\mu 0$ and $\sigma 0$ from the post-change window and restart the detector so it stops re-firing. If it is a regression, route it to the standard remediation path and keep the old $\mu 0$ so recovery is detectable.

Verification Checklist #

Confirm each item before you consider the detector tuned and the drift resolved:

• [ ] Replaying the last 30 days of the fingerprint’s series produces at most one change point per 465 in-control samples.
• [ ] s_high returns to 0.0 after each emitted change point (the reset fired).
• [ ] The slack k and interval h in production match the values validated against historical replay (k = 0.5, h = 5.0).
• [ ] $\mu 0$ and $\sigma 0$ were re-estimated from the post-change window after every approved capacity event.
• [ ] The cost series is deseasonalized (same-phase residuals) if the workload has a diurnal or weekly cycle.
• [ ] A synthetic $1\sigma 0$ step injected into a test series is detected within 10 samples.
• [ ] The cusum_change_point_total counter and cusum_upper_sum gauge are visible in the observability backend and wired to an alert.
• [ ] Every emitted change point carries the fingerprint, direction, and crossing timestamp for triage.

Compatibility and Engine-Specific Notes #

CUSUM operates on a numeric cost series, so it is engine-agnostic — but the cost figure you feed it, and its calibration, differ by source engine.

Because MySQL’s query_cost is a unitless heuristic rather than a disk-time estimate, widen the $\sigma 0$ floor so ordinary jitter does not accumulate; the same caution applies to the weighting caveats in Setting Dynamic Thresholds for Query Regression Alerts. On distributed engines the cost of one fingerprint can shift purely from a range rebalance, so treat a rebalancing event as an approved change point and re-anchor rather than paging.

Related #

• ← Back to Tuning Thresholds for False Positive Reduction (parent topic)
• When the whole cost distribution moves, not just its mean: Statistical Distance Algorithms for Plan Drift
• Seed μ0 from an adaptive baseline: Setting Dynamic Thresholds for Query Regression Alerts
• Wider context: Regression Detection & Rule Engines

← Back to Tuning Thresholds for False Positive Reduction