Handling Plan Hash Collisions Across Schema Versions

Handling plan hash collisions across schema versions means separating two failure modes that a naive fingerprint conflates: a true collision, where two structurally different plans resolve to one identical plan_hash, and fingerprint churn, where one unchanged plan produces a brand-new hash after a DDL migration. This runbook gives the exact detection thresholds for each, a root-cause walk through OID reuse and canonicalization gaps, and a production Python fix that qualifies relation names, resolves object identifiers to stable names, and salts the digest with a schema version. It is the schema-durability layer beneath the plan hashing stage and refines the canonicalize-then-digest pipeline built in how to generate deterministic query plan hashes in Python.

Symptom Identification and Production Thresholds #

A fingerprint that is stable within one schema version but unstable across a DDL migration is a defect, not a regression signal. Treat the following as hard numeric breaches; each fires an alert on the plan_fingerprint_health job rather than the query-regression queue.

1. True-collision detection. Two distinct canonical plan bodies map to one plan_hash. The operational ceiling is zero collisions per 10^9 distinct fingerprints. A digest truncated to 64 bits reaches a 50% birthday-collision probability at only $~5.06 \times 10^9$ stored fingerprints (2^32), so any store retaining fewer than 128 bits is already over budget on a large fleet.
2. Post-migration churn breach. The unexpected-new-fingerprint ratio exceeds 5% of critical-path fingerprints when the migration altered $\le 5\%$ of the referenced relations. A DDL that touches one lookup table must not re-key 30% of your baselines; a wide gap means non-schema metadata is leaking into the digest.
3. OID-keyed drift. More than 0 fingerprints change after an operation that preserves logical structure but reassigns object identifiers — pg_dump/restore, TRUNCATE, CREATE TABLE ... LIKE swaps, or a REPLACE-style table rename. OID reuse must never reach the hash.
4. Cross-schema aliasing. Two relations sharing a bare relname across different schemas (resolved by search_path) produce one identical fingerprint. This is a namespace collision: the schema qualifier is missing from the canonical key.
5. Baseline re-attach storm. More than 2% of captured plans fail to join their historical baseline in the 15 minutes following a migration, breaking p95 telemetry continuity for those query_fingerprint keys.

When breach 1 or 3 fires, freeze promotion of new baselines until the digest defect is fixed — a colliding fingerprint silently overwrites an unrelated query’s history.

Root Cause Analysis #

Every cross-version fingerprint defect traces to one of four domains. Each carries a command that confirms or eliminates it before you touch the hasher.

OID reuse and numeric identifiers in the tree. PostgreSQL reuses object identifiers freely, and a plan that embeds a raw OID (or an OID-derived alias) re-keys the instant a table is recreated. Prove whether your captured plans carry OIDs and whether any have been reassigned:

-- PostgreSQL: current OID vs a stored fingerprint's expected OID
SELECT c.relname, c.oid AS current_oid, c.relnamespace::regnamespace AS schema
FROM pg_class c
WHERE c.relname = ANY(ARRAY['orders','order_items','customers'])
ORDER BY c.relname;

If current_oid differs from the value recorded at baseline capture while relname and schema are unchanged, the churn is pure OID reuse — fix the canonicalizer, do not re-baseline.

Unqualified relation names. When the canonical tree stores orders instead of sales.orders, two same-named tables in different schemas collide, and a migration that moves a table between schemas produces spurious churn. Confirm the ambiguity directly:

-- PostgreSQL: same relname living in more than one schema
SELECT relname, count(*) AS schema_count,
       string_agg(relnamespace::regnamespace::text, ', ' ORDER BY relnamespace::regnamespace::text) AS schemas
FROM pg_class
WHERE relkind = 'r'
GROUP BY relname
HAVING count(*) > 1;

Any row here is a latent collision until the canonicalizer qualifies names with their schema.

Canonicalization gaps on schema-scoped metadata. Column position numbers, default expression OIDs, statistics timestamps, and per-session search_path echoes ride into the plan after a migration even when the plan shape is identical. Diff the raw key sets of a pre- and post-migration capture to find the leaking field:

comm -3 \
  <(jq -r 'paths | join(".")' pre_migration_plan.json | sort -u) \
  <(jq -r 'paths | join(".")' post_migration_plan.json | sort -u)

Any key present on only one side, for a query whose structure did not change, must be added to the volatile-strip set or normalized before the digest.

Hash truncation. Storing a shortened digest to save index bytes is the only root cause that produces true collisions rather than churn. A 32-bit or 64-bit truncation trades storage for a birthday-bounded collision rate that grows quadratically with fingerprint count. Retain the full 256-bit digest, or at minimum 128 bits, and index the prefix separately if lookup width is the concern.

Step-by-Step Remediation #

1. Make the canonicalizer schema-aware and OID-free #

Qualify every relation with its schema, drop numeric identifiers, and mix a schema_version salt into the digest so a deliberate DDL rollout produces a controlled, expected new fingerprint rather than silent churn. The salt lets you diff “hash changed because schema changed” against “hash changed for no reason.”

import hashlib
import json
from dataclasses import dataclass
from typing import Any, FrozenSet

import structlog
from opentelemetry import trace

log = structlog.get_logger("plan_fingerprint.schema")
tracer = trace.get_tracer("plan_fingerprint.schema")

# Numeric / session-scoped identifiers that must never reach the digest.
OID_KEYS: FrozenSet[str] = frozenset({
    "Relation OID", "reloid", "relid", "Index OID", "indexrelid",
    "Function OID", "Constraint OID", "typid", "attrelid",
})


@dataclass(frozen=True)
class SchemaFingerprint:
    query_fingerprint: str
    plan_hash: str          # full 64-hex-char (256-bit) digest, never truncated
    schema_version: str
    salted: bool


class SchemaAwareCanonicalizer:
    """Canonicalize a plan so its fingerprint survives OID reuse and schema moves."""

    def __init__(self, oid_to_qualified: dict[int, str]) -> None:
        # e.g. {16487: "sales.orders", 16502: "sales.order_items"}
        self._names = oid_to_qualified

    def _rewrite(self, node: Any) -> Any:
        if isinstance(node, dict):
            out: dict[str, Any] = {}
            for key, value in node.items():
                if key in OID_KEYS:
                    continue  # strip raw identifiers outright
                if key == "Relation Name" and "Schema" in node:
                    out[key] = f"{node['Schema']}.{value}"  # qualify with schema
                    continue
                out[key] = self._rewrite(value)
            return dict(sorted(out.items()))
        if isinstance(node, list):
            return [self._rewrite(item) for item in node]
        if isinstance(node, float):
            return round(node, 4)
        return node

    def fingerprint(self, plan: dict, schema_version: str) -> SchemaFingerprint:
        with tracer.start_as_current_span("schema_fingerprint") as span:
            canonical = self._rewrite(plan)
            body = json.dumps(
                canonical, sort_keys=True, separators=(",", ":"), ensure_ascii=False
            )
            # Salt binds the digest to a declared schema version so intentional
            # DDL churn is distinguishable from accidental drift.
            salted = f"{schema_version}\x1f{body}".encode("utf-8")
            digest = hashlib.sha256(salted).hexdigest()          # 256-bit, full width
            structural = hashlib.sha256(body.encode("utf-8")).hexdigest()
            span.set_attribute("plan.schema_version", schema_version)
            span.set_attribute("plan.hash", digest)
            log.info("schema_fingerprint",
                     schema_version=schema_version, plan_hash=digest[:12])
            return SchemaFingerprint(structural, digest, schema_version, salted=True)

Expected: two captures of one unchanged query taken before and after a pg_dump/restore that reassigns OIDs yield an identical query_fingerprint (the structural digest) and, under the same schema_version, an identical plan_hash.

2. Resolve OIDs to stable qualified names on a replica #

Build the oid_to_qualified map from the catalog on a read replica so the lookup never contends with the primary, mirroring the isolation used across the EXPLAIN capture and storage workflows.

import asyncpg


async def load_oid_map(dsn: str) -> dict[int, str]:
    conn = await asyncpg.connect(dsn)
    try:
        rows = await conn.fetch(
            "SELECT c.oid, n.nspname || '.' || c.relname AS qualified "
            "FROM pg_class c JOIN pg_namespace n ON n.oid = c.relnamespace "
            "WHERE c.relkind IN ('r','p','m')"
        )
        return {int(r["oid"]): r["qualified"] for r in rows}
    finally:
        await conn.close()

3. Classify the change instead of blindly re-anchoring #

Compare the structural digest and the salted plan_hash to decide whether a change is stable, churn, or a collision, and route each outcome differently.

def classify(prev: SchemaFingerprint, curr: SchemaFingerprint) -> str:
    if prev.query_fingerprint == curr.query_fingerprint:
        # same plan structure
        return "STABLE" if prev.plan_hash == curr.plan_hash else "CHURN"
    # different structure
    return "COLLISION" if prev.plan_hash == curr.plan_hash else "REGRESSION"

Expected routing output for a migration that only reassigned OIDs:

{"pair": "orders_by_region", "structural_match": true, "hash_match": true, "verdict": "STABLE"}

A CHURN verdict re-canonicalizes and re-anchors the baseline under the new schema_version; a COLLISION verdict quarantines the fingerprint and fails the build, because it means the digest is too narrow. The schema metadata that authorizes a controlled re-anchor is validated by schema validation for baseline metadata before any new baseline is promoted.

Verification Checklist #

Run these after changing the canonicalizer and before it keys any baseline:

• [ ] Every key in OID_KEYS is stripped, and no numeric object identifier appears in the serialized body.
• [ ] Relation names are schema-qualified (schema.table), verified against the cross-schema relname query returning zero unresolved duplicates.
• [ ] The stored plan_hash retains the full 256-bit digest (64 hex chars); no column truncates below 128 bits.
• [ ] A pg_dump/restore that reassigns OIDs yields an identical query_fingerprint for an unchanged query.
• [ ] Moving a table between schemas produces a different fingerprint (namespace change is semantic), not a silent match.
• [ ] The schema_version salt changes the plan_hash for a declared migration and leaves it stable within a version.
• [ ] Post-migration unexpected-new-fingerprint ratio stays $\le 5\%$ when $\le 5\%$ of referenced relations were altered.
• [ ] Baseline re-attach failure stays $\le 2\%$ in the 15 minutes after a migration.

Compatibility and Engine-Specific Notes #

The collision-versus-churn split is universal, but the identifier hazards differ sharply by engine.

MySQL surfaces no schema layer, so qualify with the database name and strip AUTO_INCREMENT and generated-column expression metadata before hashing. On distributed engines the descriptor version is the natural salt — feed it as schema_version so a range rebalance never reads as a fingerprint change. In all three, keep the same volatile-stripping discipline established for deterministic Python hashing so runtime noise and identifiers stay out of the digest together.

Related #

• How to Generate Deterministic Query Plan Hashes in Python — the base canonicalize-then-digest pipeline this page hardens against schema change.
• Schema Validation for Baseline Metadata — validates the schema version that authorizes a controlled re-anchor.
• Core Architecture & Baselining Fundamentals — the reference architecture this fingerprint work belongs to.

← Back to Plan Hashing Algorithms for SQL Engines