Two-Sample Tests for Distribution Drift in a Column

A price column keeps its mean, its minimum, and its maximum. Its null rate is unchanged. Every aggregate in the profile is stable, and the column has still changed: the distribution has become bimodal, because a new source reports in a different currency and the values cluster in a second band that the mean averages away.

Detecting this requires comparing the shape of the column against its past shape, which means comparing distributions rather than summaries. The statistics for doing that are well established, and applying them to warehouse columns involves three decisions that the statistics do not make: what to compare against, how to bin, and how to account for the number of comparisons.

What a distribution test can and cannot say

A two-sample test asks whether two samples are consistent with having been drawn from the same distribution. It returns a statistic and a p-value, where the p-value is the probability of a statistic at least as extreme, given that the null hypothesis of identical distributions is true.

The p-value is not the probability that the distributions differ, and it is not a measure of how much they differ. It is a measure of evidence against a specific null, and its value depends on the sample size as much as on the difference. With a million rows per side, a difference of a fraction of a percent in the mean produces a vanishingly small p-value, because the test’s power grows with the sample. Every large table is therefore “significantly different” from every other large table, and a pipeline that alerts on p-values will alert on every column, every period.

The quantity that carries operational meaning is the effect size: how far apart the distributions are, measured in a way that does not grow with the sample. For the Kolmogorov-Smirnov statistic, that is the statistic itself, the maximum absolute difference between the two empirical distribution functions, which is bounded in $[0,1]$ and does not depend on $n$ in its definition. A statistic of 0.01 is a negligible reshape; a statistic of 0.2 is a substantial one. The test’s critical value scales as $\sqrt{(n_1+n_2)/(n_1 n_2)}$, so at large $n$ the threshold for significance becomes tiny while the statistic stays interpretable.

The practical rule is to threshold the effect size and use the p-value only to avoid firing on samples too small to be meaningful. That inverts the usual reading of a test, and it is the correct inversion for monitoring, where the question is “is the change big enough to matter” rather than “is there evidence of any change at all”.

Three statistics and the shapes they detect

The common tests differ in which kind of difference they are sensitive to, and the choice follows from what a column’s plausible faults look like.

The Kolmogorov-Smirnov two-sample test compares empirical distribution functions and is sensitive to any difference in shape, location, or scale. Its statistic is $\sup_x |F_1(x) - F_2(x)|$, the largest vertical gap between the two step functions, which is computable from sorted samples in time proportional to the sum of their sizes. It is most sensitive to a shift in the middle of the distribution and least sensitive at the tails, because the empirical distribution functions are closest together where the density is lowest. A fault that adds a small cluster of extreme values at the top of a column is a fault it can miss.

The chi-square test on binned counts compares frequencies per bin and is sensitive to differences anywhere the bins are defined. Its statistic is $\sum (O_i - E_i)^2 / E_i$ over bins, with degrees of freedom reduced by one for the total and by the number of estimated parameters. It is more flexible than Kolmogorov-Smirnov because the bins can be chosen to concentrate sensitivity where it matters, and it is more fragile because a bin with a very small expected count makes the statistic unstable; the usual guidance is that expected counts below about five per bin make the approximation unreliable.

The population stability index is a symmetric divergence over bins, $\sum_i (a_i - b_i) \ln(a_i / b_i)$ where $a$ and $b$ are the proportions in bin $i$ for the two samples. It is not a test and has no p-value, which is its advantage for monitoring: a fixed threshold such as 0.1 for a moderate shift and 0.25 for a large one is used as a convention, and the number is comparable across columns and periods without reference to sample size. Its weakness is that it is unbounded and asymmetric in a specific way: it grows without limit when a bin present in one sample is empty in the other, so an empty bin produces an arbitrarily large index. That behaviour is often exactly what is wanted, since a bin that appears or disappears is the strongest kind of drift, but it means the index cannot be averaged across columns without care.

Binning decides the answer

For the binned statistics, the binning is part of the model, and different binnings give different verdicts on the same data.

Equal-width bins over the observed range are simple and are dominated by the tails, since a heavy-tailed column puts almost all its mass in the first bin or two and the remaining bins are nearly empty. That arrangement detects a change in the tail and misses a change in the bulk.

Equal-frequency bins, derived from quantiles of a reference sample, put equal mass in each bin and are therefore sensitive to changes in the bulk. Their problem is that the bins are defined by the reference, so a shift in the sample moves mass across boundaries in a way that is measured correctly, but a new sample whose range extends beyond the reference’s range falls outside all bins. Handling that requires explicit underflow and overflow bins, which must not be silently dropped, since dropping them is how a new cluster of extreme values becomes invisible.

The choice of reference matters as much as the bins. Comparing each period to the immediately preceding one detects change and drifts: a slow, monotone shift moves by a small amount each period, each comparison is below threshold, and the column has travelled a long way over a year. Comparing against a fixed reference detects cumulative drift and never adapts to a legitimate change in the data, so it alerts forever after a real business change. The usual compromise is to keep both: a fixed reference for the long-horizon question and a rolling comparison for the short-horizon one, with different thresholds for each.

The number of bins is a second free parameter with a known trade. Too few bins and a localized change is averaged into a large bin and disappears; too many and each bin’s count becomes small enough that sampling noise dominates, producing false flags. A rule of thumb from the histogram literature relates the bin count to the sample size as roughly the cube root of $n$, which for a million rows gives about a hundred bins. For monitoring, fewer bins are usually chosen deliberately, because a stable index across periods is worth more than resolution that fires on noise.

import math

def psi(reference, current, edges):
    """Population stability index over pre-defined bin edges, with overflow bins."""
    def proportions(values):
        counts = [0] * (len(edges) + 1)      # one extra bin for values above the top edge
        for v in values:
            i = 0
            while i < len(edges) and v >= edges[i]:
                i += 1
            counts[i] += 1
        total = len(values) or 1
        return [c / total for c in counts]

    a, b = proportions(reference), proportions(current)
    # Floor avoids division by zero for an empty bin; the floor is the sensitivity limit.
    eps = 1e-6
    return sum((max(x, eps) - max(y, eps)) * math.log(max(x, eps) / max(y, eps))
               for x, y in zip(a, b))

Comparing many columns at once

A table of two hundred columns, each tested at a one percent significance level, produces about two false flags per period even when nothing has changed. Across a thousand tables the number is in the thousands, and the alerts are indistinguishable from the real ones.

The multiple-comparison correction is arithmetic: to hold the family-wise error rate at $\alpha$ across $m$ tests, each test is conducted at $\alpha/m$, which is the Bonferroni bound. It is conservative, since it assumes the tests are independent and they usually are not, and it is simple enough to implement as a threshold change. Its cost is statistical power: at $\alpha = 0.01$ and $m = 200$, each test runs at $5 \times 10^{-5}$, and a real but modest drift may not reach significance.

The alternative is to control the false discovery rate rather than the family-wise rate, which allows a proportion of the flagged tests to be false as long as the proportion is bounded. The Benjamini-Hochberg procedure sorts the $m$ p-values and compares the $i$-th smallest to $i \alpha / m$, flagging all tests up to the largest $i$ that satisfies the inequality. It has more power than Bonferroni and is the appropriate choice when the goal is to produce a reviewable list rather than to make a single yes-or-no decision.

Both procedures assume the tests are independent or positively correlated. Columns in a table are often strongly correlated, since a derived column moves with its inputs, and correlated tests make both procedures conservative. The practical consequence is that a cluster of flags on correlated columns is likely to be one real change, not several, which is why the output should be grouped by correlation before it is presented.

Drift is not always a fault

The single largest source of noise in distribution monitoring is legitimate change. A new product category adds values to a categorical column. A pricing change shifts a numeric column’s mode. A source system’s backfill rewrites a month of history.

None of these are detectable as faults from the distribution alone, because the distribution comparison is exactly the measurement that a legitimate change and a fault both produce. The distinction has to come from outside the statistics: from a declaration that a change is expected, from a lineage graph that shows which upstream change could have caused it, or from a correlation with a change in a different column that is known to be legitimate.

This is where column-level lineage earns its cost. A drift flag on a column whose upstream set changed on the same day is a change to investigate in one place; a drift flag on a column whose upstream set is unchanged is a fault to investigate everywhere. The lineage does not diagnose the fault, but it partitions the search space, which is most of the work.

A second discriminator is whether the drift is accompanied by a change in the relationships between columns. A column that shifts alone is suspicious. A set of columns that shift together, preserving their joint relationships, is more likely to be a population change than a transform error, because a transform error usually breaks an arithmetic relationship while a population change preserves it. Testing that requires comparing a joint distribution rather than marginals, which is more expensive and is the reason it is done on a sample.

The cost of the comparison itself

Comparing full distributions requires materializing them, and the cost is a scan of both samples. For a warehouse column that is not cheap, and it is the reason drift checks run on a sample or on a pre-aggregated sketch rather than on the raw column.

The pre-aggregation route stores a histogram per partition, computed once at write time and reused by every subsequent comparison. A histogram with a hundred bins is a few hundred bytes per partition, and comparing two of them is arithmetic on a hundred numbers. That reduces the check to a metadata operation and makes daily comparison of every column feasible, at the cost of fixing the bins at write time, so the bins cannot be chosen after seeing the data.

Sketches provide the middle ground: a structure such as a quantile sketch summarises the distribution in bounded space with a known error, is mergeable across partitions, and can be re-quantiled at read time to any binning. The error is the trade: a sketch that compresses a distribution into a few kilobytes cannot resolve a difference smaller than its own accuracy, so the smallest detectable drift is set by the sketch’s size rather than by the data. Choosing that size is a decision about which drifts matter, made once, and the check’s sensitivity is bounded by it thereafter.

The partition-level statistics already stored by the table format are the cheapest source of all, since minimum and maximum per column are free. They detect a change in range and nothing else, which makes them a first filter: a column whose range has not moved cannot have drifted much, and one whose range has moved has earned a closer look.