Computing Tree Edit Distance Between Query Plans

Tree edit distance (TED) measures the minimum weighted cost of inserting, deleting, and relabeling nodes to turn one plan tree into another, giving an exact structural distance where the weighted node-diff score gives a fast approximation. This runbook applies the Zhang-Shasha algorithm to canonical plan trees: it sets the insert, delete, and relabel costs that make the distance meaningful, normalizes labels so unstable identifiers do not inflate the result, and pins down the $O(n^{2}\cdot min(depth,leaves)^{2})$ cost that makes TED dangerous on wide partition-fanout plans. It is the exact-distance companion to graph-diff scoring for execution plan trees.

Use TED when you need a provably minimal edit script — for example to rank several candidate plans by how far each drifts from an anchored baseline, or to explain which sequence of operator edits separates two plans. Reach for the faster weighted node-diff instead when you only need a scalar gate verdict on every capture.

Symptom Identification and Production Thresholds #

Treat each of the following as a hard numeric breach condition, not a guideline. Every threshold assumes labels have already been normalized per the remediation below.

1. Raw TED above the block band. The normalized edit distance ted_norm = raw_ted / max(|T_base|, |T_cand|) exceeds 0.30. A normalized distance above 0.30 means roughly a third of the tree was rewritten — an access-path or join-topology regression, not incidental churn.
2. Relabel-heavy distance with zero inserts. $raw_{ted} \ge 4$ while the edit script contains only relabels. A pure-relabel distance of 4 or more almost always signals an operator swap on a hot path (for example an index scan demoted to a sequential scan across four partitions).
3. Compute time blowup. Single-pair TED wall-time exceeds 120 ms p95, or 250 ms p99. Zhang-Shasha is cubic in the worst case; crossing these bounds means a wide plan is being compared node-for-node without collapsing.
4. Distance instability across identical captures. Two TED runs on the same fingerprint pair differ by more than 0 — any non-zero variance on identical inputs means labels are non-deterministic and the distance is meaningless.
5. Insert/delete imbalance. The edit script’s insert count minus delete count has absolute value above 3, indicating a large subtree appeared or vanished (partition pruning changed, or a join was added).

When condition 1 fires together with either 2 or 5, escalate immediately: that combination is a structural regression with a named edit path, not noise.

Root Cause Analysis #

Unstable node labels. The most common cause of an inflated distance is labels that vary between captures — a scan labeled with its estimated row count, or an alias-qualified relation name that changes when the query is re-parenthesized. Zhang-Shasha treats any label difference as a relabel with non-zero cost, so unstable labels manufacture edits that never happened. Confirm label stability by hashing the label multiset of two captures of the same plan:

for v in baseline candidate; do
  jq -r '.. | objects | select(.operator) | .operator + "|" + (.relation // "-")' "${v}_dag.json" \
    | sort | md5sum
done

If the two digests differ for a plan you know is unchanged, the labels carry volatile fields — normalize before you ever compute distance.

Ordered vs. unordered children. Zhang-Shasha assumes ordered trees: the leftmost child of a join is distinct from the rightmost. Plan trees are only partially ordered — the two inputs of a hash join can appear in either order without changing execution — so a build/probe-side swap registers as a costly delete-plus-insert. Detect an order-only difference by comparing the sorted child operator sets at each join:

SELECT node_id,
       array_agg(child_op ORDER BY child_op) AS sorted_children
FROM candidate_plan_edges
WHERE parent_op IN ('Hash Join', 'Merge Join', 'Nested Loop')
GROUP BY node_id;

If the sorted child sets match the baseline but raw TED is non-zero, canonicalize child order (sort children by operator then relation) before indexing.

O(n³) blowup on wide plans. Zhang-Shasha’s cost is $O(|T_{base}|\cdot |T_{cand}|\cdot min(depth_{base}, leaves_{base})\cdot min(depth_{cand}, leaves_{cand}))$, which approaches cubic on bushy partition-fanout plans with hundreds of sibling scans. A single comparison can then dominate a whole scoring batch. Identify the offenders by node count before they time out:

SELECT plan_fingerprint,
       (SELECT count(*) FROM jsonb_path_query(dag_json, '$.**')) AS node_count
FROM canonical_plan_dag
ORDER BY node_count DESC
LIMIT 10;

Any plan above ~400 nodes should be collapsed (score partition subtrees as one node) before TED, or routed to the faster weighted node-diff instead.

Step-by-Step Remediation #

1. Normalize labels to the stable operator identity. Strip cost, row, and alias volatility so equal operators compare equal. Sort children so the tree is genuinely ordered.

from __future__ import annotations

from dataclasses import dataclass


@dataclass(frozen=True)
class TNode:
    label: str
    children: tuple["TNode", ...] = ()


def normalize(node: dict) -> TNode:
    """Reduce a raw plan node to a stable label + order-canonical children."""
    op = node["Node Type"]
    rel = node.get("Relation Name", "-")
    label = f"{op}:{rel}"                       # no costs, no row counts
    kids = [normalize(c) for c in node.get("Plans", [])]
    kids.sort(key=lambda n: n.label)            # impose a deterministic order
    return TNode(label=label, children=tuple(kids))

2. Compute the distance with weighted Zhang-Shasha. Unit insert and delete, weighted relabel keyed off an access-path severity map.

RELABEL_WEIGHTS: dict[frozenset[str], float] = {
    frozenset({"Index Only Scan", "Seq Scan"}): 3.0,
    frozenset({"Hash Join", "Nested Loop"}): 3.0,
    frozenset({"Index Scan", "Bitmap Heap Scan"}): 1.5,
    frozenset({"Sort", "Incremental Sort"}): 0.5,
}
DEFAULT_RELABEL = 2.0
INSERT_COST = 1.0
DELETE_COST = 1.0


def _relabel(a: str, b: str) -> float:
    if a == b:
        return 0.0
    op_a, op_b = a.split(":", 1)[0], b.split(":", 1)[0]
    return RELABEL_WEIGHTS.get(frozenset({op_a, op_b}), DEFAULT_RELABEL)


def _postorder(root: TNode) -> tuple[list[TNode], list[int]]:
    """Return nodes in post-order plus each node's leftmost-leaf index."""
    nodes: list[TNode] = []
    lmld: list[int] = []

    def visit(n: TNode) -> int:
        first_leaf = len(nodes)
        for i, c in enumerate(n.children):
            leaf = visit(c)
            if i == 0:
                first_leaf = leaf
        nodes.append(n)
        lmld.append(first_leaf)
        return first_leaf if n.children else len(nodes) - 1

    visit(root)
    return nodes, lmld


def tree_edit_distance(t1: TNode, t2: TNode) -> float:
    n1, l1 = _postorder(t1)
    n2, l2 = _postorder(t2)
    keyroots1 = _keyroots(l1)
    keyroots2 = _keyroots(l2)
    td = [[0.0] * len(n2) for _ in range(len(n1))]

    for i in keyroots1:
        for j in keyroots2:
            _forest_dist(i, j, n1, n2, l1, l2, td)
    return td[len(n1) - 1][len(n2) - 1]


def _keyroots(lmld: list[int]) -> list[int]:
    seen: dict[int, int] = {}
    for i, leaf in enumerate(lmld):
        seen[leaf] = i            # last node sharing a leftmost leaf wins
    return sorted(seen.values())


def _forest_dist(i, j, n1, n2, l1, l2, td) -> None:
    fd = [[0.0] * (j - l2[j] + 2) for _ in range(i - l1[i] + 2)]
    for di in range(1, i - l1[i] + 2):
        fd[di][0] = fd[di - 1][0] + DELETE_COST
    for dj in range(1, j - l2[j] + 2):
        fd[0][dj] = fd[0][dj - 1] + INSERT_COST
    for di in range(l1[i], i + 1):
        for dj in range(l2[j], j + 1):
            x, y = di - l1[i] + 1, dj - l2[j] + 1
            if l1[di] == l1[i] and l2[dj] == l2[j]:
                cost = _relabel(n1[di].label, n2[dj].label)
                fd[x][y] = min(fd[x - 1][y] + DELETE_COST,
                               fd[x][y - 1] + INSERT_COST,
                               fd[x - 1][y - 1] + cost)
                td[di][dj] = fd[x][y]
            else:
                fd[x][y] = min(fd[x - 1][y] + DELETE_COST,
                               fd[x][y - 1] + INSERT_COST,
                               fd[l1[di] - l1[i]][l2[dj] - l2[j]] + td[di][dj])

3. Normalize and route. Divide by the larger tree size and apply the bands.

def route(t1: TNode, t2: TNode) -> tuple[float, str]:
    raw = tree_edit_distance(t1, t2)
    size = max(len(_postorder(t1)[0]), len(_postorder(t2)[0]), 1)
    norm = raw / size
    flag = "REGRESSION" if norm > 0.30 else "DRIFT" if norm > 0.15 else "STABLE"
    return round(norm, 4), flag

Running the router on a plan whose only change is an index-scan demotion across four partitions prints:

ted_raw=12.0 ted_norm=0.2727 flag=DRIFT changed=Index Only Scan->Seq Scan x4

4. Collapse wide plans before scoring if step 3 exceeds the latency band. Replace each partition-fanout subtree with a single synthetic node so node_count drops below 400, then re-run.

Verification Checklist #

• [ ] Two captures of a known-unchanged plan produce ted_raw == 0.0 (label stability confirmed).
• [ ] Child ordering is canonicalized so a hash-join build/probe swap yields ted_raw == 0.0.
• [ ] ted_norm for the affected fingerprint has fallen back under 0.30 on the last three captures.
• [ ] Single-pair TED p95 wall-time is under 120 ms and p99 under 250 ms.
• [ ] Every plan above 400 nodes is collapsed or routed to weighted node-diff before TED runs.
• [ ] RELABEL_WEIGHTS covers all access-path pairs your engine can emit after its latest upgrade.
• [ ] The insert-minus-delete imbalance is within $\pm 3$ for any plan flagged STABLE.
• [ ] The normalized distance and edit script are exported as OpenTelemetry span attributes for correlation.

Compatibility and Engine-Specific Notes #

The Zhang-Shasha core is engine-agnostic, but the fields you fold into each node’s label differ per engine. Map them before building the tree.

MySQL exposes no distinct merge-join operator, so collapse its equivalents into the hash-join relabel weight rather than letting them fall to DEFAULT_RELABEL. On distributed engines a single logical scan can expand into per-range operators, so collapse range-fanout subtrees before indexing or the width term dominates the cubic cost. For the cross-engine label mapping that feeds normalization, ground it in normalizing query plans for cross-engine comparison, and derive the fingerprint that pairs the two trees from plan hashing algorithms for SQL engines.

Related #

• Statistical Distance Algorithms for Plan Drift — aggregates per-capture edit distances into a drift signal over time.
• Detecting Join Type Shifts in Execution Plans — turns the relabel edits TED surfaces into a targeted join-topology alert.
• Plan Hashing Algorithms for SQL Engines — the fingerprint that guarantees the two trees you compare belong to the same query.
• Normalizing Query Plans for Cross-Engine Comparison — the label-normalization prerequisite that keeps the distance meaningful.

← Back to Graph-Diff Scoring for Execution Plan Trees