Scoring Plan Drift with Jensen-Shannon Divergence

Jensen–Shannon divergence turns two bags of plan-cost samples into a single bounded number that says how far a candidate execution’s cost distribution has moved from the anchored baseline. This runbook covers the parts that decide whether that number is trustworthy: how to bin the samples, how to smooth the empty bins that would otherwise send the math to infinity, why base-2 and base-e give different ceilings, and the exact thresholds and numerical-stability checks that separate a real regression from an artifact of the binning grid.

The measure is attractive because it is symmetric and always finite — unlike raw Kullback–Leibler divergence, which explodes the moment the baseline assigns zero probability to a bin the candidate populates. It is the scoring core of Statistical Distance Algorithms for Plan Drift Detection; this guide is the operator’s view of the three things that break it in production: empty bins, mismatched supports, and too few samples.

Symptom Identification and Production Thresholds #

Treat each of the following as a hard, numeric breach condition, not a guideline. The score referenced throughout is the base-2 Jensen–Shannon divergence, which is bounded in [0.0, 1.0].

1. Sustained warn-band drift. The base-2 score stays above 0.1 for three consecutive capture windows on the same fingerprint. A single spike is noise; three in a row is a distribution that has genuinely moved.
2. Single-capture block. The base-2 score exceeds 0.25 on any one window. That is a large enough shift to gate a deploy on its own.
3. Empty-baseline instability. More than 4 of the 32 bins are empty on the baseline side. Above that count the smoothing floor, not the data, is driving a meaningful fraction of the score.
4. Support mismatch. The candidate’s value range exceeds the baseline range by more than $3\times$. The shared grid then stretches so far that most mass collapses into one bin and the score is artificially deflated.
5. Thin candidate window. Fewer than 200 candidate samples. Below that the histogram is too sparse for the divergence to be stable; treat the result as WARN, never PASS.
6. Log-base mismatch. A score reported against the natural log reads at most 0.693 (that is, ln 2), not 1.0. A raw natural-log value of 0.35 is a normalized 0.505 — dangerously close to the block band while looking safe.

Root Cause Analysis #

Empty bins (zero-probability mass). When a baseline bin holds no samples, its probability is zero, and the KL term inside the divergence contains a log(p / 0) that is undefined. Additive smoothing repairs it, but if the smoothing floor is set too high relative to the sample count, empty bins start contributing real score. Count the empty baseline bins directly from the captured samples:

WITH b AS (
  SELECT width_bucket(total_cost,
           (SELECT min(total_cost) FROM plan_cost_sample WHERE query_hash = $1),
           (SELECT max(total_cost) FROM plan_cost_sample WHERE query_hash = $1),
           32) AS bin
  FROM plan_cost_sample
  WHERE query_hash = $1 AND is_anchored
)
SELECT 32 - count(DISTINCT bin) AS empty_baseline_bins
FROM b;

Mismatched supports. If the candidate contains an outlier far outside the baseline range, the union grid stretches and both densities flatten into the low bins. The divergence then understates a real shift. Compare the two ranges before trusting a low score:

SELECT
  min(total_cost) FILTER (WHERE is_anchored)      AS base_min,
  max(total_cost) FILTER (WHERE is_anchored)      AS base_max,
  min(total_cost) FILTER (WHERE NOT is_anchored)  AS cand_min,
  max(total_cost) FILTER (WHERE NOT is_anchored)  AS cand_max
FROM plan_cost_sample
WHERE query_hash = $1;

Too few samples. A sparse candidate histogram is dominated by which bin each of a handful of samples happens to fall into. The score becomes a coin flip between captures. Confirm the depth of the candidate window before acting on any single number:

psql -qAtX -d prod_replica -c \
  "SELECT count(*) FROM plan_cost_sample WHERE query_hash = '$FP' AND NOT is_anchored"

Step-by-Step Remediation #

1. Pull both distributions and bin them on one grid. Fetch anchored and candidate cost samples for the fingerprint and score them with an explicit per-bin breakdown so you can see which bin drives the divergence:

from __future__ import annotations

import math
from dataclasses import dataclass

import asyncpg
import structlog

log = structlog.get_logger("plandrift.js")

N_BINS = 32
EPSILON = 1e-9            # additive floor for empty bins
JS_WARN = 0.1
JS_BLOCK = 0.25


@dataclass(frozen=True)
class BinDiagnostic:
    index: int
    baseline_p: float
    candidate_p: float
    js_contribution: float
    baseline_empty: bool


def _grid(lo: float, hi: float, n: int = N_BINS) -> list[float]:
    span = (hi - lo) or 1.0
    step = span / n
    return [lo + step * i for i in range(n + 1)]


def _density(samples: list[float], edges: list[float]) -> list[float]:
    n = len(edges) - 1
    lo, step = edges[0], (edges[-1] - edges[0]) / n
    counts = [0.0] * n
    for value in samples:
        i = int((value - lo) / step) if step else 0
        counts[min(max(i, 0), n - 1)] += 1.0
    total = math.fsum(c + EPSILON for c in counts)
    return [(c + EPSILON) / total for c in counts]


def js_base2(p: list[float], q: list[float]) -> tuple[float, list[BinDiagnostic]]:
    m = [(pi + qi) / 2.0 for pi, qi in zip(p, q)]
    diagnostics: list[BinDiagnostic] = []
    total = 0.0
    for i, (pi, qi, mi) in enumerate(zip(p, q, m)):
        contrib = 0.5 * pi * math.log2(pi / mi) + 0.5 * qi * math.log2(qi / mi)
        total += contrib
        diagnostics.append(BinDiagnostic(i, qi, pi, contrib, qi <= EPSILON * 2))
    return total, diagnostics


async def diagnose(pool: asyncpg.Pool, query_hash: str) -> None:
    rows = await pool.fetch(
        "SELECT total_cost, is_anchored FROM plan_cost_sample WHERE query_hash = $1",
        query_hash,
    )
    baseline = [float(r["total_cost"]) for r in rows if r["is_anchored"]]
    candidate = [float(r["total_cost"]) for r in rows if not r["is_anchored"]]

    if len(baseline) < 200 or len(candidate) < 200:
        log.warning("thin_support", baseline_n=len(baseline), candidate_n=len(candidate))
        return

    edges = _grid(min(baseline + candidate), max(baseline + candidate))
    q = _density(baseline, edges)
    p = _density(candidate, edges)
    js, bins = js_base2(p, q)
    flag = "BLOCK" if js > JS_BLOCK else "WARN" if js > JS_WARN else "PASS"
    worst = max(bins, key=lambda b: b.js_contribution)
    log.info(
        "js_diagnosed", query_hash=query_hash, js=round(js, 4), flag=flag,
        worst_bin=worst.index, worst_contribution=round(worst.js_contribution, 4),
        empty_baseline_bins=sum(1 for b in bins if b.baseline_empty),
    )

Running it against a fingerprint whose tail has shifted emits a single structured line that names the offending bin:

2026-07-18T09:14:02Z [info] js_diagnosed query_hash=7f21…ac js=0.184 flag=WARN worst_bin=27 worst_contribution=0.071 empty_baseline_bins=4

2. If empty_baseline_bins exceeds 4, do not raise the smoothing floor. Raising EPSILON hides the instability instead of fixing it. Instead lower the resolution so each bin holds real mass — 16 bins over the same support usually clears it — and re-score. Confirm the drift score falls into a stable range across two captures before trusting the new grid.

3. If the supports are mismatched, winsorize the candidate. Clip the candidate at its 99th percentile before binning so one runaway sample cannot stretch the grid:

UPDATE plan_cost_sample
SET total_cost = LEAST(total_cost,
      (SELECT percentile_cont(0.99) WITHIN GROUP (ORDER BY total_cost)
       FROM plan_cost_sample WHERE query_hash = $1 AND NOT is_anchored))
WHERE query_hash = $1 AND NOT is_anchored;

4. Normalize any base-e score before comparing to thresholds. If a downstream tool reports natural-log divergence, divide by math.log(2) (that is, 0.6931) to bring it onto the [0.0, 1.0] scale the 0.1 and 0.25 thresholds assume. Never compare a base-e number to a base-2 threshold.

5. Pin the capture window and re-anchor. Once the score is stable, set the window depth and re-anchor the baseline so future captures score against the corrected reference:

drift_scoring:
  n_bins: 32
  smoothing_epsilon: 1e-9
  min_samples: 200
  js_warn_threshold: 0.1
  js_block_threshold: 0.25
  log_base: 2

Verification Checklist #

• [ ] The base-2 Jensen–Shannon score for the fingerprint is below 0.1 on the last three consecutive captures.
• [ ] empty_baseline_bins is 4 or fewer at the chosen bin count.
• [ ] The candidate range is within $3\times$ of the baseline range after winsorizing.
• [ ] Both the baseline and candidate windows carry at least 200 samples.
• [ ] Every score compared to a threshold is base-2, or a base-e value already divided by 0.6931.
• [ ] The worst_bin contribution corresponds to a real cost shift, not an empty-bin smoothing artifact.
• [ ] smoothing_epsilon is 1e-9 and was not raised to mask instability.
• [ ] The re-anchored baseline was promoted only after two clean capture cycles.

Compatibility and Engine-Specific Notes #

The divergence math is engine-agnostic; the samples you feed it are not. Map the source of the cost distribution per engine before wiring the collector.

On PostgreSQL you can seed the baseline grid directly from histogram_bounds in pg_stats and avoid re-binning entirely. MySQL’s equi-height buckets already carry roughly equal mass, so empty-bin instability is rarer but tail resolution is coarser. On distributed engines a single fingerprint can be served from ranges on different storage tiers, so capture the candidate window from one gateway node or the supports will not align. Ground the cross-engine cost mapping in Cost Estimation Mapping Across PostgreSQL and MySQL before trusting a cross-engine drift comparison.

Related #

• Statistical Distance Algorithms for Plan Drift Detection — the parent guide covering PSI, Wasserstein, and the full scoring stage.
• Tuning Thresholds for False Positive Reduction — the noise filter that consumes the drift flag downstream.
• Tracking Cost Deltas Across Baseline Versions — the scalar comparator the divergence score complements.
• Graph-Diff Scoring for Execution-Plan Trees — the structural signal to correlate when a cost shift coincides with an operator change.
• Defining Regression Thresholds for Query Plans — how the 0.1 and 0.25 bands fit the wider threshold model.

← Back to Statistical Distance Algorithms for Plan Drift Detection