Technical note

Our math

Abstract

A PerformanceRegression is a verdict reached in seven steps from two cumulative counters. This note derives each step, states the assumptions it needs and measures where they fail. The figures run the engine's own arithmetic, in your browser.

$$f\ge 1+\theta$$ $$|\hat{\tau }-t_d|\le \tau$$ $$p\le \alpha$$

Fig. 0 The split slides along the series; Q(k) is drawn as it goes, and the engine keeps the maximum.

OverviewSeven steps from a counter to a verdictEach stage can stop the analysis. The lab below plays a new query every few seconds; the stage that stops it turns red.

01Samples$x_t=\frac{\Delta T}{\Delta C}$Interval means from the cumulative counters.

02Floors$n\ge 10,N\ge 100$Enough points and calls to estimate a spread.

03Pre-filter$f-1\ge \theta$Cheap rejection of small shifts.

04E-divisive$\mathrm{argmax}Q\left(k\right)$Where did the distribution change?

05Tolerance$|\hat{\tau }-t_d|\le \tau$Was it this deploy?

06Welch$p\le \alpha$Is the difference more than noise?

07Verdict$c=1-p$Detected, with a score to rank it.

LabRun the whole engineThe Go correlation engine's own arithmetic, on a new synthetic query every few seconds. Watch which stage stops it.

deploy $t_d$change point $\hat{\tau }$window meansshaded band: ±τ tolerance

Regression size

Noise, per-call CV

Calls per scrape

Lands after deploy

Autocorrelation φ

Scrape interval

—

Window 30 min each side · θ = 0.20 · α = 0.05 · floors 10 samples and 100 calls · tolerance max(2, 0.2 × 30) = 6 min.

DerivationFrom counters to samplesThe number PostgreSQL shows is not the number we analyse.

§1Interval means

pg_stat_statements exposes two monotone counters per query: the calls $C$ and the total execution time $T$ in milliseconds, both accumulated since the last reset. Its mean_exec_time is their ratio, which is a mean over the whole history. We scrape both counters and analyse the mean of the calls made since the previous scrape:

$$x_t=\frac{T_t-T_{t-1}}{C_t-C_{t-1}}=\frac{\Delta T_t}{\Delta C_t}$$

The cumulative mean is slow for a precise reason. If a query ran $n_{\text{pre}}$ calls at mean $\mu$ and then $n_{\text{post}}$ calls at $\mu +\delta$, the counter reports

$$\frac{T}{C}=\mu +\delta ·\frac{n_{\text{post}}}{n_{\text{pre}}+n_{\text{post}}}$$

so after a deploy it moves only by the share of calls made since. A step of +100% needs as many calls after the deploy as before it just to read +50%. The interval mean reads the step at the next scrape.

Resets

A counter that goes down (a restart, pg_stat_statements_reset(), a change in stats_since) makes $\Delta C$ negative. That interval is discarded, not clamped, because its calls belong to no window. The cumulative mean jumps at a reset; the interval means do not.

interval mean $x_t$cumulative mean $T/C$

Step

Step lands at

Counter reset

DerivationGates before statisticsFloors decide when we are allowed to answer, not how often the answer is wrong.

§2Floors and the pre-filter

Both windows (before and after the deploy) must clear two floors. Samples protect the machinery: the t-test and the energy statistic estimate a spread from the data, so they need points, $n\ge n_{\text{min}}=10$. Executions bound the precision of the window's mean: the standard error of a mean of $N$ calls with per-call coefficient of variation $\text{CV}$ is

$$\text{SE}\left(\overline{x}\right)/\mu =\frac{\text{CV}}{\sqrt{N}}$$

With $N=100$ and $\text{CV}=1$, a window mean is good to about ±10% at one standard error. Windows with fewer calls return InsufficientData, which is different from NoRegression: the first says "we could not tell".

The pre-filter compares the call-weighted window means, $\overline{x}=\frac{\sum \Delta T}{\sum \Delta C}$, and stops when

$$f-1<\theta =0.20⟹\text{NoRegression}$$

It is an optimisation and a guard: the expensive stages run only on shifts big enough to matter.

Per-call CV

Calls in the window

Scrapes in the window

Stage 1Finding the change with energyE-divisive means asks whether two stretches of the series come from the same distribution, not only whether their means differ.

§3The energy statistic

For two samples $A=a_1\dots a_{n_a}$ and $B=b_1\dots b_{n_b}$ let $D(A,B)$ be the mean absolute distance across them. The energy distance of Székely and Rizzo [1] compares the cross distance with the distances inside each sample:

$$ℰ=2D_{ab}-D_{aa}-D_{bb}{D}_{ab}=\frac{1}{n_a{n}_b}\sum _{i,j}|a_i-b_j|$$

It is zero exactly when the two samples have the same distribution (in the limit) and grows with any difference: location, spread or shape. Scaled by the sample sizes it becomes the statistic the engine evaluates at every admissible split $k$ of the series, with within-sample distances averaged over unordered pairs [2]:

$$Q\left(k\right)=\frac{2n_a{n}_b}{n_a+n_b}(D_{ab}-\frac{D_{aa}}{2}-\frac{D_{bb}}{2})\hat{\tau }=\underset{m\le k\le n-m}{\mathrm{argmax}}Q\left(k\right)$$

Here $n_a=k$, $n_b=n-k$, and $m=max(3,\lfloor n/10\rfloor )$ keeps a change from being "found" in the first or last few points. A split is kept only if $Q>0$. Evaluating all splits costs $O\left(n^2\right)$ because moving the split one step changes each sum by one row and one column.

Why not just split at the deploy?

Rolling deploys and connection draining spread the shift over minutes, and the collector adds scrape granularity. Letting the data place the split gives the shift's real start, and the next stage asks whether that start is close enough to the deploy to blame it.

left of the splitright of the splitargmax Q

Shift in the middle

Noise

Stage 1bWas it this deploy?A change point is only evidence about a deploy if it is close to it.

§4The tolerance window

Let $t_d$ be the deploy time and $\hat{\tau }$ the located change. The change is attributed to the deploy only if

$$|\hat{\tau }-t_d|\le \tau =max(2\text{min},0.2W)$$

where $W$ is the analysis window. Making the allowance a fraction of the window keeps the same relative slack for a tight 10-minute window and a loose 60-minute one; the floor keeps short windows from shrinking it to nothing.

The order matters. The engine checks the tolerance before the significance test, so a shift that is very significant but starts twenty minutes before the deploy is reported as unrelated background change, never as a regression of this deploy. This is the step that turns a change detector into an attribution tool.

A trade-off, not a free parameter

A wide tolerance catches slow rollouts and attributes more unrelated shifts to the deploy. A narrow one does the opposite. Under a Poisson process of unrelated shifts the expected number of coincidences grows linearly in $\tau$.

Window W

Located change $\hat{\tau }$

Stage 2Is it more than noise?Welch's t-test on the two segments the data itself found.

§5Welch's t-test

The two segments on either side of $\hat{\tau }$ are compared without assuming equal variances. A latency regression often changes the spread as well as the mean, so the pooled-variance Student test would be the wrong tool [3]:

$$t=\frac{{\overline{x}}_b-{\overline{x}}_a}{\sqrt{\frac{s_a^2}{n_a}+\frac{s_b^2}{n_b}}}$$

The reference distribution is Student's $t$ with the Welch–Satterthwaite degrees of freedom,

$$\nu =\frac{{(\frac{s_a^2}{n_a}+\frac{s_b^2}{n_b})}^2}{\frac{{(s_a^2/n_a)}^2}{n_a-1}+\frac{{(s_b^2/n_b)}^2}{n_b-1}}$$

and the two-sided p-value has a closed form through the regularised incomplete beta function, which is what the engine computes with a continued fraction [4]:

$$p=P\left(\right|T_{\nu }|\ge |t\left|\right)=I_{\nu /(\nu +t^2)}(\frac{\nu }{2},\frac{1}{2})$$

The test is applied to the per-interval means $x_t$, not to individual calls. By the central limit theorem those are much closer to normal than the heavy-tailed per-call latencies, which is why a test that assumes normality is defensible here at all.

Change in the mean

Interval-mean CV

Points before

Points after

InterpretationWhat the score meansconfidenceScore is 1 − p. It ranks detections. It is not the probability that the regression is real.

§6A p-value is not a posterior

The p-value answers "if nothing changed, how often would noise alone look at least this extreme?". Reading $1-p$ as "the chance the change is real" inverts the conditional. How far apart the two can be is bounded, without any assumption about the prior, by the calibration of Sellke, Bayarri and Berger [5]. For $p<1/e$ the Bayes factor in favour of "no change" is at least $B\left(p\right)=-ep\ln p$, so with even prior odds

$$P(H_0\mid \text{data})\ge {(1+\frac{1}{-ep\ln p})}^{-1}$$

p	score 1 − p	P(no change) ≥
0.05	0.95	0.29
0.01	0.99	0.11
0.001	0.999	0.018
0.0001	0.9999	0.0025

A score of 0.95 can leave a 29% chance that nothing changed. That is why the score is documented as a ranking and a threshold input, and why it should not be quoted as a probability.

p-value

CaveatThe search inflates significanceChoosing the split from the data, then testing it as if it had been chosen in advance, is optimistic.

§7Maximally selected statistics

Stage 1 picks the split with the largest $Q$. Stage 2 then tests that split with a t-test whose reference distribution assumes the split was fixed beforehand. Under "no change" a t-statistic at a fixed split has $p\sim \text{Uniform}(0,1)$, but the split $k^{\ast }$ that maximises a separation statistic is by construction the one where the two sides look most different, so the p-value $p_{k\ast }$ at that split is too small:

$$P(p_{k\ast }\le \alpha \mid H_0)>\alpha$$

The statistical literature calls this the problem of maximally selected statistics and corrects for it with a p-value that accounts for the search [6]. E-divisive means itself does so with a permutation test over the whole search [1].

The figure draws series with no change at all, applies stages 1 and 2 exactly as the engine does, and histograms the p-values. A correct test would be flat. With independent noise the lab typically puts 35–39% of them below 0.05; with autocorrelated noise, far more.

What protects production

Three other gates sit around this one: the pre-filter (a real +20% is required), the tolerance (the located change must sit near the deploy) and the floors. Through the whole pipeline the measured share of no-change analyses reported as Detected is much lower than the raw p-value rate; the roadmap tracks the calibration work.

Points per series

Autocorrelation φ

Dashed line: what a correctly calibrated test would give.

DesignHow many calls you needSensitivity is bought with executions. This is the price list.

§8Sample size for a target effect

To detect a relative change $\delta$ in the mean at size $\alpha =0.05$ (two-sided) with power $1-\beta =0.8$, a two-sample comparison needs, per window,

$$N\approx \frac{2{(z_{\alpha /2}+z_{\beta })}^2{\text{CV}}^2}{{\delta }^2}=\frac{15.7{\text{CV}}^2}{{\delta }^2}$$

using $z_{\alpha /2}=1.96$ and $z_{\beta }=0.84$. The cost is quadratic in both noise and ambition: halving the smallest change you care about quadruples the calls you need. A query with CV = 1 needs about 390 calls per window to see +20% reliably, and about 1,570 to see +10%.

This is the asymptotic normal approximation for means, and it ignores the search of §7, so it is optimistic for small windows. Treat it as a lower bound when choosing --min-executions and the window length.

Per-call CV

Smallest change δ

HonestyWhere the math stopsThe two assumptions that matter most, and what happens when they fail.

Independent intervals

The t-test and the permutation argument assume the interval means are independent. Serially correlated noise (a slow checkpoint, a cache warming) inflates the false-positive rate, as the selection lab shows with φ > 0.

Counters, not calls

The mean of an interval hides its composition: a shift in the mix of parameter values looks the same as a slower plan. That is why a detection carries a plan diff and an externalCauseSuspected flag.

ReproducibilityThe page runs the engine's mathNot a re-implementation we hope is close.

Every widget above calls one dependency-free module, docs/assets/math/math-core.js, a line-by-line port of internal/correlation/engine.go: the interval means, the minimum segment length, the incremental energy statistic, the Lanczos log-gamma, the incomplete beta continued fraction and the decision order of evaluateQuery. A Go test (internal/correlation/mathpage_test.go) feeds fixed series, generated by that module, to the real engine and fails if the verdict, the change point, $t$, $\nu$ or $p$ differ, so the page cannot drift from the code without CI noticing. Noise in the lab is a seeded log-normal per call (so the mean of $c$ calls has coefficient of variation $\text{CV}/\sqrt{c}$), with optional AR(1) correlation, from a fixed seed so every figure is reproducible.

For the full operational description of each stage, flag and CRD field, see the Detection Algorithm and the Configuration Reference. To run the engine itself on a workload, open the Playground.

References

• [1]D. S. Matteson and N. A. James, “A nonparametric approach for multiple change point analysis of multivariate data”, JASA 109(505), 2014. doi:10.1080/01621459.2013.849605
• [2]G. J. Székely and M. L. Rizzo, “Energy statistics: a class of statistics based on distances”, Journal of Statistical Planning and Inference 143(8), 2013.
• [3]B. L. Welch, “The generalization of ‘Student's’ problem when several different population variances are involved”, Biometrika 34, 1947.
• [4]W. H. Press et al., Numerical Recipes, §6.4 “Incomplete beta function” (continued fraction by the modified Lentz method).
• [5]T. Sellke, M. J. Bayarri and J. O. Berger, “Calibration of p values for testing precise null hypotheses”, The American Statistician 55(1), 2001.
• [6]R. Miller and D. Siegmund, “Maximally selected chi square statistics”, Biometrics 38, 1982; B. Lausen and M. Schumacher, “Maximally selected rank statistics”, Biometrics 48, 1992.
• [7]D. Daly et al., “The use of change point detection to identify software performance regressions in a continuous integration system”, ICPE 2020. arXiv:2003.00584

Licensed under Apache 2.0 — see LICENSE.