RFC: Improve Plan Algorithm With Column Level Lineage

[cmgoffena13]

Summary

SQLMesh OSS's plan algorithm is not as efficient as Tobiko Cloud. There are numerous efficiency improvements that can be introduced into the plan logic by introducing column level lineage.

Plan Algorithm Comparison

Parent users has id, email, username. Child A selects id, email. Child B selects only id. Grandchild C selects id from A.

        users
 (id, email, username)
       /         \
      /           \
     A             B
(id, email)       (id)
     |
     C
    (id)

Change (to users)	OSS today	Tobiko Cloud (inferred)
Add phone	A, B, C skip	Same
Change email expression	A, B, C rebuild	A rebuilds; B, C skip
Drop unused username	A, B, C rebuild	A, B, C skip (users still rebuilds)
Change WHERE statement	A, B, C rebuild	A, B, C rebuild

Current Pseudo-Code

plan (DAG order)
  │
  ├─ new model ──────────────────────── BREAKING
  │
  ├─ directly modified
  │     ├─ kind change / SELECT * ───── BREAKING
  │     └─ compare old vs new query
  │           ├─ only added columns ─── NON_BREAKING
  │           └─ anything else ──────── BREAKING
  │
  └─ indirectly modified
        ├─ parent NON_BREAKING ──────── SKIP
        └─ parent BREAKING ──────────── REBUILD

Future Pseudo-Code

plan (DAG order)
  │
  ├─ new model ──────────────────────── BREAKING
  │
  ├─ directly modified
  │     ├─ kind change / SELECT * /
  │     │  can't render / Python ────── BREAKING   (same as today)
  │     └─ column diff (old vs new)
  │           ├─ only added columns ─── NON_BREAKING
  │           ├─ whole row set changed ─ BREAKING   (WHERE / JOIN / …)
  │           └─ some columns dirty ─── rebuild self
  │                                      (descendants decided below)
  │
  └─ indirectly modified
        ask lineage: do I depend on a dirty column?
          ├─ no ─────────────────────── SKIP
          └─ yes ────────────────────── REBUILD
              (and mark my outputs dirty
               so grandchildren can ask the same)

Logic Simplified

• Directly Modified - Model's own query/data changed. Fingerprint data hash changed. It will rebuild itself (unless forward-only, ignore)
• Indirectly Modified - Model's SQL did not change. A parent did. Current logic copies parent's "category". Future logic will use column-level to determine "category"

Category	This model	Meaning
BREAKING / NON_BREAKING	Direct	Always rebuild self. Difference is only what descendants do today.
INDIRECT_BREAKING	Indirect	Rebuild this model
INDIRECT_NON_BREAKING	Indirect	Skip — reuse the old physical table

For children descendants, we can improve the logic to determine categories INDIRECT_BREAKING or INDIRECT_NON_BREAKING by looking at the column level changes. We would traverse the table lineage and for each model that has children, we would determine for each column:

This column	Means	If the child reads it
Clean	Same as before	Does not force a rebuild. INDIRECT_NON_BREAKING
Dirty	Not the same (rewritten, from a dirty parent column, or row set changed)	Forces INDIRECT_BREAKING
Added	New column	Does not force a rebuild. INDIRECT_NON_BREAKING
Removed	Column is gone	Forces INDIRECT_BREAKING

Then:

• Any dirty/removed column the child reads → model is INDIRECT_BREAKING → keep labeling that model’s outputs for its children.
• Child reads only clean/added → model is INDIRECT_NON_BREAKING → all of its outputs are clean (this parent won’t force descendants to rebuild).
• Can’t prove → INDIRECT_BREAKING (same as today).

Goal: more models correctly land on INDIRECT_NON_BREAKING and are not rebuilt.

High Level Pieces

We need three major pieces here:

1. Column diff on the changed model
   Did this change only some columns, or the whole row set (WHERE / JOIN / etc.)? List clean, dirty, added, removed.

2. Ask who reads those columns
   Using lineage (and filters/joins, not just SELECT): which downstream models/columns actually depend on the dirty columns?

3. Rebuild only that cone
   The changed model still rebuilds. Descendants that lineage says are untouched skip. That’s B skipping when email changed, and C skipping when it only uses A’s id and A’s rows didn’t move.

Right now OSS does some of piece 1. It answers "did we only add columns to the model?" -- It does not list columns. Current logic treats "additive" as non-breaking. Anything else that isn't just a pure add ends with a "not sure" conclusion -> rebuild everyone.

Only comparison happens in sqlmesh/core/definition.py in is_breaking_change function right now. Current logic determines breaking or non_breaking. Then that affects descendants.

Starting Pieces

Already there	Role today	What it becomes
sqlmesh/core/model/definition.py — is_breaking_change / _is_only_projection_additions	Additive or not (False / None)	Piece 1: column diff: clean, dirty, added, removed
sqlmesh/core/snapshot/categorizer.py — categorize_change	Maps that to NON_BREAKING / BREAKING on the direct model	Same job, richer input
sqlmesh/core/plan/builder.py — _categorize_snapshot	Direct path calls categorizer; indirect path copies the "category" of the parent	Piece 3: indirect path asks lineage instead of copying "category" from parent
sqlmesh/core/lineage.py	UI/LSP column graph	Piece 2: “does this descendant depend on a dirty column?”

Initial Steps

To be determined. We have to be very careful about this because we're modifying core logic. This also introduces a much bigger layer of checks. How do we keep this performant?

References

Tobiko Cloud claims:

• "Tobiko Cloud comes with even more change categorization capabilities than open-source SQLMesh, such as advanced column-level impact analysis." -- https://sqlmesh.readthedocs.io/en/stable/cloud/features/costs_savings/#where-to-find-cost-and-savings-information
• "Unaffected Downstream: SQLMesh understands SQL, so we skip re-execution if a downstream model is not affected by an upstream change." -- https://sqlmesh.readthedocs.io/en/stable/cloud/features/costs_savings/#where-to-find-cost-and-savings-information
• "While this study focuses on benchmarking SQLMesh against dbt Core, we also evaluated Tobiko Cloud, the hosted version of SQLMesh, to examine its handling of breaking changes. SQLMesh uses column-level lineage to differentiate between breaking and non-breaking changes — and Tobiko Cloud extends this capability with more surgical change categorization, refining how downstream updates are processed when a column is modified. This further reduces time and compute spent on backfills, making Tobiko Cloud even more performant than its counterpart — by a factor of seven." -- https://medium.com/dbsql-sme-engineering/databricks-benchmark-study-shows-sqlmesh-outperforms-dbt-core-by-orders-of-magnitude-on-speed-and-0f3b6f281888