RFC: Improve Plan Algorithm With Column Level Lineage

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:

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.
Ask who reads those columns
Using lineage (and filters/joins, not just SELECT): which downstream models/columns actually depend on the dirty columns?
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

Nailing down that the better categorization of INDIRECT models to INDIRECT_BREAKING and INDIRECT_NON_BREAKING would happen in the PlanBuilder._categorize_snapshot method in sqlmesh/core/plan/builder.py

The column_dependencies function in sqlmesh/core/lineage.py is a good starting point for logic. It gets upstream dependencies on a column. There's probably a more efficient way to get column upstream dependencies than looping through and calling that function though. Need to make sure its accurate as well. One caveat is this function does not factor in columns that only appear in WHERE statements; There might be more.

We have modified_snapshots in ContextDiff in sqlmesh/core/context_diff.py.…

@tripleaceme

Hey @tripleaceme -- this is not in a state to be implemented just yet, more work needs done in figuring out how to safely implement the changes to the plan command. The RFC stands for "Request for Comment" -- basically means this isn't ready yet, but feedback/discussion is welcome to help get it in a "Ready" state and collaborate on an approach.

Given the scope of the issue, the other TSC members / maintainers will also need to be involved before any work to the codebase begins. We'll need to be very intentional with this.

If you want to investigate some of the sections of code presented and report findings here, I'd appreciate it!

@cmgoffena13

Trimmed to a summary as you asked, @cmgoffena13 — and sorry for the wall of text, and for being slow to cut it down.

Is it feasible? Yes for the projection cases in your table — the email rewrite and dropping unused username — behind a flag and staged. Not yet for anything that moves the row set.

Top three blockers

Column lineage is projection-only, and the gap is in sqlglot rather than SQLMesh. sqlglot/lineage.py::to_node builds its recursion set from find_all_in_scope(select, exp.Column), where select is just the projection being resolved. WHERE, JOIN ... ON, GROUP BY, HAVING and QUALIFY are never scanned. So the "change a WHERE" row of your own table yields an empty dirty set, and a naive gate would skip B and C silently. This is the one place where a partial implementation is worse than none. The predicates are reachable — Node.source keeps FROM/JOIN/WHERE — but attributing them to columns is a new traversal.
Row-set changes have no column to hang off. A parent's row count changing moves COUNT(*), window functions and aggregates in a child with no column edge at all. That needs a distinguished "row set" pseudo-column that poisons every child column, rather than an entry in the column diff.
Plan-time cost, plus a cache bug that doubles it. sqlmesh/core/lineage.py::CACHE is keyed on model.name and guarded by id(model). A plan needs the new and the previous model of the same name, so they evict each other on every alternation — three qualify + build_scope passes where two would do. The id() guard is also a latent false-hit once old snapshot models are transient.

One unrelated win worth landing on its own merits. sqlglot 30.x can resolve every output column in one call with a shared cache, but lineage() types its first parameter so it cannot reach it. Measured 4.1x on a synthetic 200-model project (3339ms → 817ms on the walk phase). It speeds up the existing UI and LSP path too, independent of this RFC.

Agreed that _categorize_snapshot is where this lands, and the WHERE caveat you flagged is blocker 1 above. I have the detailed working — every claim cited to file and function, plus benchmark method and run-to-run variance — and I'll hold it until it's useful. Say the word and I'll post it here or put it wherever suits you better.

@tripleaceme

Hey @tripleaceme -- I appreciate the initiative, but 3700 words of analysis isn't the right fit for an RFC thread. These are meant for conversation, not design docs. Please edit this down to a high-level summary: is this feasible? What are the top 2-3 blockers? If you want to share the detailed breakdown, hold it until we've had initial discussions. We need scannable contributions here so people can actually engage.

Discovered the sqlmesh.core.lineage.column_dependencies function that given a column, will show which upstream models provide the column (or columns needed for the calculation). So if SUM(quanity * price) AS revenue is provided as the column, it will go upstream and find the models that provide quantity and price. Only intakes one column though.

More functionality can obviously be added to the sqlmesh.core.lineage module. Needs better testing because it was developed for the IDE Extension/Web UI specifically.

Nailing down that the better categorization of INDIRECT models to INDIRECT_BREAKING and INDIRECT_NON_BREAKING would happen in the PlanBuilder._categorize_snapshot method in sqlmesh/core/plan/builder.py

The column_dependencies function in sqlmesh/core/lineage.py is a good starting point for logic. It gets upstream dependencies on a column. There's probably a more efficient way to get column upstream dependencies than looping through and calling that function though. Need to make sure its accurate as well. One caveat is this function does not factor in columns that only appear in WHERE statements; There might be more.

We have modified_snapshots in ContextDiff in sqlmesh/core/context_diff.py. That gives us the (new, old) snapshots for DIRECT models. We can use this to get the column changes, which can be done within _categorize_snapshots. Once we have those columns, we get upstream column dependencies on the children models to check if any of them lead back. If they do lead back, we can categorize according.

Starting to think about if it would make sense to store column lineage in the state backend. That could help improve performance because then we could do incremental updates to the lineage rather than recompute every plan.

Since all of these changes can be contained within _categorize_snapshot, we could easily put in an opt-in/dev flag there to keep the old behavior active as we start building out the logic and testing categorizations

Edited my earlier comment down to a summary — feasibility and three blockers. Three short notes on yours:

"Probably a more efficient way than looping through column_dependencies" — there is. sqlglot 30.x resolves every output column in one call with a shared cache and scope metadata; sqlmesh/core/lineage.py::lineage types its first parameter as str | exp.Column, so it can't reach that mode and each column re-walks shared upstream nodes. I measured 4.1x on a synthetic 200-model project. Worth widening regardless of this RFC, since the UI and LSP pay it too.

The WHERE caveat — that's the blocker I'd rank first, and it's in sqlglot rather than here: to_node only scans the projection, so a WHERE-only change produces an empty dirty set rather than an uncertain one. Failing closed matters more than failing accurately.

Storing lineage in the state backend — it also removes the previous-model half of the per-plan cost, not just recomputation. Worth deciding early either way, because it's what makes ColumnDiff serialisable-from-day-one or not, and _get_orphaned_indirect_change_category has to stay conservative without it.

@tripleaceme

@tripleaceme row set changes, any changes in WHERE, JOIN ... ON, GROUP BY, HAVING and QUALIFY, will probably have a rebuild everything downstream flag. We can't determine how it changes the dataset, so it would fallback to have everything rebuilt. We can see if that can be improved later.

When you say its a blocker in sqlglot, do you mean sqlglot doesn't have the functionality? I'd imagine we'd have to figure out the best way to do it, but it sounds like sqlglot just doesn't have an "easy" way to do it.

do you mean sqlglot doesn't have the functionality?

Absent rather than hard. sqlglot/lineage.py::to_node builds its recursion set as source_columns = set(find_all_in_scope(select, exp.Column)), where select is the single projection being resolved; the only widening is a UDTF branch. Predicates are never scanned. Attribution would be a new traversal, maybe 40 lines.

But your fallback means we don't need it. If any change to WHERE / JOIN ... ON / GROUP BY / HAVING / QUALIFY rebuilds everything downstream, we never need to know which column a predicate touched — only that one changed. That primitive already exists in _is_only_projection_additions' lockstep walk. Checked against main, duckdb:

change to the model	`is_breaking_change`
added column only	`False`
`WHERE` changed	`None`
`WHERE` changed inside a CTE	`None`
predicate moved `WHERE` → `JOIN ... ON`	`None`
`GROUP BY` changed	`None`
projection expression rewritten	`None`

So the gap isn't lineage — it's that the last row returns the same None as every row above it. The work is splitting today's single "can't prove" into "row set moved → rebuild all downstream" and "only projections changed → ask lineage". Lineage then only ever runs on the case sqlglot does handle, which drops my first blocker to a return-type change on something that already works.

That also flips the risk I named. It's no longer a silent skip from an empty dirty set; it's under-detecting a row-set change so it reads as projection-only. So the split has to default to "row set moved" and narrow only when the walk proves nothing outside projections changed — which is what that walk does today.

Navigation Menu

Repository navigation

RFC: Improve Plan Algorithm With Column Level Lineage #6062

Summary

Plan Algorithm Comparison

Current Pseudo-Code

Future Pseudo-Code

Logic Simplified

High Level Pieces

Starting Pieces

Initial Steps

References

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

RFC: Improve Plan Algorithm With Column Level Lineage #6062

Description

Summary

Plan Algorithm Comparison

Current Pseudo-Code

Future Pseudo-Code

Logic Simplified

High Level Pieces

Starting Pieces

Initial Steps

References

Activity

tripleaceme commented on Sep 17, 2026

cmgoffena13 commented on Sep 18, 2026

tripleaceme commented on Sep 18, 2026

cmgoffena13 commented on Sep 20, 2026

cmgoffena13 commented on Oct 10, 2026

cmgoffena13 commented on Oct 18, 2026

tripleaceme commented on Oct 18, 2026

cmgoffena13 commented on Oct 18, 2026

tripleaceme commented on Oct 18, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions