Graph-Diff Scoring for Execution Plan Trees

Graph-diff scoring compares two canonical execution-plan DAGs structurally — matching subtrees, diffing operator nodes and parent-child edges, and rolling the changes into a single weighted structural-change score — so that an access-path flip or a join-topology rewrite is caught even when the optimizer’s headline cost estimate barely moves. This guide specifies the canonical DAG contract the scorer consumes, the deterministic node-identity formula that makes two captures comparable, a production asyncio implementation of the weighted node-diff walk, and the exact score bands that turn a diff into a PASS / WARN / FAIL verdict.

Cost deltas answer “did the plan get more expensive?”; graph-diff scoring answers the orthogonal question “did the plan change shape, and where?” A plan can hold its total cost flat while swapping an Index Only Scan for a Bitmap Heap Scan or promoting a Hash Join to a Nested Loop over a large inner relation — moves that are structurally alarming yet cost-invisible. This stage exists to score exactly those structural mutations, independent of the cost-delta path.

Architectural Boundaries #

The scorer is a pure structural comparator. It consumes exactly two inputs — a baseline canonical plan DAG and a candidate canonical plan DAG, both keyed by the same deterministic plan fingerprint — and it emits exactly two outputs: a scalar structural_score in [0.0, 1.0] and an ordered list of changed_operators. It never opens a write transaction against the plan store, never re-parses raw EXPLAIN text, and never reads cost timings; those responsibilities belong upstream and downstream respectively.

Upstream, the two DAGs arrive already normalized. The plan-normalization stage has stripped volatile fields (actual row counts, buffer numbers, per-run timings), canonicalized operator labels across engines, and assigned each node a stable identity so that the same logical operator carries the same id across two captures. Without that guarantee the diff degenerates into noise: every node looks changed because every node was relabeled. The scorer treats an unnormalized DAG as a hard input error, not something to repair inline.

Downstream, the structural_score and changed_operators list fan out to three consumers. The regression rule engine folds the score into its verdict alongside the cost-delta signal. The join-type-shift detector subscribes to the changed_operators list to confirm topology flips it independently suspects. And the plan-drift distance layer aggregates the score over time to distinguish a one-off structural blip from sustained drift.

Holding that boundary is what makes the score trustworthy. If the scorer starts re-parsing raw plans or reaching into the cost store, two captures of an identical plan can produce different scores, and a structural verdict that flickers is worse than no verdict at all.

Deterministic Routing and Schema Enforcement #

Every score is a function of two typed DAGs and nothing else. A plan node is validated against this JSON Schema before it enters the diff; a node that fails validation aborts the comparison rather than being silently coerced, because a dropped node_id is the single most common cause of a phantom “everything changed” diff.

{
  "$id": "https://queryplan.org/schemas/canonical-plan-node.json",
  "type": "object",
  "additionalProperties": false,
  "required": ["node_id", "operator", "relation", "depth", "child_ordinal", "children"],
  "properties": {
    "node_id":       { "type": "string", "pattern": "^[a-f0-9]{16}$" },
    "operator":      { "type": "string", "minLength": 1 },
    "relation":      { "type": ["string", "null"] },
    "depth":         { "type": "integer", "minimum": 0 },
    "child_ordinal": { "type": "integer", "minimum": 0 },
    "children":      { "type": "array", "items": { "$ref": "#" } }
  }
}

The node_id is not random; it is a stable hash of the node’s position and role so that the same logical operator carries the same id across two captures of the same fingerprint. The formula is deterministic and engine-agnostic:

node_id = blake2b(f"{operator}|{relation or '-'}|{depth}|{child_ordinal}", digest_size=8).hexdigest()

Because the id folds in depth and child_ordinal but deliberately excludes volatile cost and row numbers, a node that merely got more expensive keeps its id (so it is a relabel candidate, not an insert/delete), while a node that moved to a new position in the tree gets a new id (correctly registering as topology change). Sharding the scorer across workers uses a partition key derived from the fingerprint so both DAGs for one query always land on the same worker:

partition_key = int(plan_fingerprint[:8], 16) % SCORER_SHARD_COUNT

The pipeline itself is a strict, ordered sequence, and each stage narrows what the next must consider:

1. Subtree matching aligns nodes by node_id. Identically-id’d subtrees on both sides are matched and excluded from further scoring — an unchanged subtree contributes zero.
2. Relabel scoring handles matched positions whose operator differs. The cost is looked up in the operator substitution weight table, not treated as a flat unit — swapping Index Only Scan for Seq Scan is far more significant than swapping Sort for Incremental Sort.
3. Edge topology diff scores nodes present on one side only: an inserted or deleted operator, or a parent-edge that moved. These carry the heaviest unit weight because a new join node reshapes execution.
4. Weighted aggregation normalizes the accumulated change against the size of the larger tree, yielding structural_score in [0.0, 1.0].

Production-Ready Implementation #

The scorer below is an asyncio service. It loads the two DAGs through an asyncpg pool, walks them with the weighted node-diff pipeline, instruments every comparison with OpenTelemetry spans and metrics, and emits structured logs through structlog. The scoring walk is pure; the only I/O is the read-only DAG fetch.

from __future__ import annotations

import os
from dataclasses import dataclass, field
from typing import Iterable

import asyncpg
import structlog
from opentelemetry import metrics, trace

log = structlog.get_logger(__name__)
tracer = trace.get_tracer(__name__)
meter = metrics.get_meter(__name__)

SCORE_DURATION = meter.create_histogram("graphdiff_score_compute_ms", unit="ms")
SCORE_VALUE = meter.create_histogram("graphdiff_structural_score", unit="1")
CHANGED_OPS = meter.create_counter("graphdiff_changed_operators_total", unit="1")

# --- Operator substitution weight table (relabel cost, 0..1) ---------------
# Higher = a more alarming access-path or join-topology change.
SUBSTITUTION_WEIGHTS: dict[tuple[str, str], float] = {
    ("Index Only Scan", "Seq Scan"): 0.95,
    ("Index Scan", "Seq Scan"): 0.90,
    ("Hash Join", "Nested Loop"): 1.00,
    ("Merge Join", "Nested Loop"): 0.95,
    ("Index Scan", "Bitmap Heap Scan"): 0.55,
    ("Sort", "Incremental Sort"): 0.20,
    ("Aggregate", "GroupAggregate"): 0.30,
}
DEFAULT_RELABEL_WEIGHT = 0.60   # unknown operator swap
INSERT_DELETE_WEIGHT = 1.00     # a node present on one side only
SCORE_BLOCK = 0.35              # structural_score at or above this -> FAIL


@dataclass(frozen=True)
class PlanNode:
    node_id: str
    operator: str
    relation: str | None
    depth: int
    child_ordinal: int
    children: tuple["PlanNode", ...] = ()


@dataclass
class StructuralDiff:
    fingerprint: str
    structural_score: float
    changed_operators: list[str] = field(default_factory=list)
    verdict: str = "PASS"


def _index_by_id(root: PlanNode) -> dict[str, PlanNode]:
    flat: dict[str, PlanNode] = {}
    stack = [root]
    while stack:
        n = stack.pop()
        flat[n.node_id] = n
        stack.extend(n.children)
    return flat


def _relabel_cost(old_op: str, new_op: str) -> float:
    if old_op == new_op:
        return 0.0
    return SUBSTITUTION_WEIGHTS.get(
        (old_op, new_op),
        SUBSTITUTION_WEIGHTS.get((new_op, old_op), DEFAULT_RELABEL_WEIGHT),
    )


def score_trees(fingerprint: str, baseline: PlanNode, candidate: PlanNode) -> StructuralDiff:
    """Weighted node-diff over two canonical DAGs. Pure and deterministic."""
    base = _index_by_id(baseline)
    cand = _index_by_id(candidate)
    all_ids: Iterable[str] = set(base) | set(cand)

    accumulated = 0.0
    changed: list[str] = []
    for nid in all_ids:
        b, c = base.get(nid), cand.get(nid)
        if b is not None and c is not None:
            cost = _relabel_cost(b.operator, c.operator)
            if cost > 0.0:
                accumulated += cost
                changed.append(f"{b.operator}->{c.operator}@{nid}")
        else:                                   # insert or delete
            present = b or c
            accumulated += INSERT_DELETE_WEIGHT
            verb = "del" if c is None else "ins"
            changed.append(f"{verb}:{present.operator}@{nid}")

    denom = max(len(base), len(cand), 1)
    structural_score = min(accumulated / denom, 1.0)
    verdict = "FAIL" if structural_score >= SCORE_BLOCK else (
        "WARN" if structural_score >= 0.15 else "PASS"
    )
    return StructuralDiff(fingerprint, round(structural_score, 4), changed, verdict)


class GraphDiffScorer:
    def __init__(self, pool: asyncpg.Pool) -> None:
        self._pool = pool

    async def _load_dag(self, fingerprint: str, version: str) -> PlanNode:
        row = await self._pool.fetchrow(
            "SELECT dag_json FROM canonical_plan_dag "
            "WHERE plan_fingerprint = $1 AND version = $2",
            fingerprint, version,
        )
        if row is None:
            raise LookupError(f"no DAG for {fingerprint}@{version}")
        return _from_json(row["dag_json"])

    async def compare(self, fingerprint: str, base_v: str, cand_v: str) -> StructuralDiff:
        with tracer.start_as_current_span("graphdiff.compare") as span:
            span.set_attribute("plan_fingerprint", fingerprint)
            baseline = await self._load_dag(fingerprint, base_v)
            candidate = await self._load_dag(fingerprint, cand_v)
            diff = score_trees(fingerprint, baseline, candidate)
            SCORE_VALUE.record(diff.structural_score, {"verdict": diff.verdict})
            CHANGED_OPS.add(len(diff.changed_operators), {"verdict": diff.verdict})
            span.set_attribute("structural_score", diff.structural_score)
            span.set_attribute("verdict", diff.verdict)
            log.info("graphdiff_scored", fingerprint=fingerprint,
                     score=diff.structural_score, verdict=diff.verdict,
                     changed=len(diff.changed_operators))
            return diff


def _from_json(raw: dict) -> PlanNode:
    return PlanNode(
        node_id=raw["node_id"], operator=raw["operator"],
        relation=raw.get("relation"), depth=raw["depth"],
        child_ordinal=raw["child_ordinal"],
        children=tuple(_from_json(c) for c in raw.get("children", [])),
    )


async def build_pool() -> asyncpg.Pool:
    return await asyncpg.create_pool(
        dsn=os.environ["GRAPHDIFF_DSN"],
        min_size=2,
        max_size=int(os.environ.get("GRAPHDIFF_POOL_MAX", "8")),
        command_timeout=5.0,
    )

Two properties keep this correct at scale. First, an unchanged subtree contributes nothing because both sides share the same node_id, so the score is dominated by real structural change rather than tree size. Second, the substitution weight table encodes domain knowledge directly: a Hash Join demoted to a Nested Loop scores a full 1.00 even though it is a single relabel, because that one swap is often the entire regression.

Threshold Reference #

The score bands below convert a structural_score into a verdict, and the operational SLOs define when the scorer itself is unhealthy. Both are wired to alerting.

A $structural_{score} \ge 0.35$ is a hard block because, given the weight table, it can only be reached by either an access-path flip on a scan (weight ≥ 0.90) or a join-topology insert (weight 1.00) over a small tree — both worth stopping a deploy for. Encode the block band as a Prometheus alert:

groups:
  - name: graphdiff-scorer
    rules:
      - alert: GraphDiffStructuralRegression
        expr: |
          histogram_quantile(0.95,
            sum(rate(graphdiff_structural_score_bucket[10m])) by (le)
          ) >= 0.35
        for: 10m
        labels:
          severity: page
        annotations:
          summary: "p95 structural_score >= 0.35 for 10m — plan topology regressing"
          runbook: "Inspect changed_operators; confirm access-path flip via join-shift detector before rollback."

      - alert: GraphDiffScorerSlow
        expr: |
          histogram_quantile(0.95,
            sum(rate(graphdiff_score_compute_ms_bucket[5m])) by (le)
          ) > 60
        for: 5m
        labels:
          severity: warn
        annotations:
          summary: "Scorer p95 compute > 60ms — check wide-plan node counts and pool health"

Failure Scenarios and Root Cause Analysis #

1. Phantom full-tree diff after a normalization change. Symptom: structural_score jumps to near 1.0 across the whole fleet at once, with every node reported changed. Root cause: an upstream normalization rule changed how node_id is derived, so no ids match across captures. Diagnose by comparing id overlap between the two versions:

SELECT count(*) FILTER (WHERE b.node_id IS NOT NULL) AS matched,
       count(*) AS total_candidate
FROM candidate_nodes c
LEFT JOIN baseline_nodes b USING (node_id)
WHERE c.plan_fingerprint = '9c2f4a1b7e0d3f88';

Mitigation: pin the node_id formula and re-seed baselines through the normalization stage before re-scoring; never patch the id formula inside the scorer.

2. Missed regression from over-broad subtree matching. Symptom: an obvious $Hash Join \to Nested Loop$ flip scores PASS. Root cause: the operator was excluded from the id because relation was null on both sides, so the swap fell into a matched-but-unscored subtree. Diagnose:

jq -r '.. | objects | select(.operator=="Nested Loop") | .node_id' candidate_dag.json

Mitigation: ensure join nodes always carry child_ordinal and depth in the id so a topology move re-registers as insert/delete rather than a silent match.

3. Score latency blowup on wide plans. Symptom: graphdiff_score_compute_ms p95 exceeds 60 ms on analytical queries. Root cause: partition-wise plans with hundreds of child scans inflate node counts, and _index_by_id walks every node. Diagnose by node count:

SELECT plan_fingerprint, jsonb_array_length(dag_json->'children') AS top_children
FROM canonical_plan_dag ORDER BY top_children DESC LIMIT 10;

Mitigation: cap comparison depth for partition-fanout plans and score partition subtrees as a single collapsed node; raise GRAPHDIFF_POOL_MAX if load latency, not walk time, dominates.

4. Cross-shard score divergence. Symptom: the same fingerprint yields different scores on retry. Root cause: SCORER_SHARD_COUNT changed at runtime, so the two DAGs for one query hashed to different workers reading different cache states. Mitigation: treat SCORER_SHARD_COUNT as immutable; re-shard only through a full drain.

5. Weight-table staleness after an engine upgrade. Symptom: a new operator (for example a newly-introduced parallel scan variant) always scores DEFAULT_RELABEL_WEIGHT, masking its true severity. Mitigation: audit SUBSTITUTION_WEIGHTS against the engine’s operator catalog each major upgrade and add explicit pairs for new access paths.

Configuration Reference #

Raise score_block toward 0.45 if benign incremental-sort or aggregate-strategy swaps dominate your FAIL rate; lower score_warn only when you want early visibility into single-operator relabels. Move one variable per change so the calibration stays reproducible against replayed captures. For the exact-distance companion to this weighted score, see the runbook on computing tree edit distance between query plans.

Related #

• Statistical Distance Algorithms for Plan Drift — aggregates the structural score over time to separate a one-off change from sustained drift.
• Detecting Join Type Shifts in Execution Plans — the downstream detector that subscribes to the changed_operators list to confirm topology flips.
• Plan Hashing Algorithms for SQL Engines — produces the plan fingerprint that keys both DAGs fed to the scorer.
• Normalizing Query Plans for Cross-Engine Comparison — the upstream stage that canonicalizes operators and assigns the stable node ids this scorer depends on.
• Computing Tree Edit Distance Between Query Plans — the exact edit-distance method that complements this weighted node-diff score.

← Back to Regression Detection & Rule Engines