Column-Level Lineage and the Cost of Tracking It

A column in a report is wrong. The report’s query selects it from a view, the view computes it from two columns of a table, and that table is loaded by a job whose SQL reads three upstream tables. The column that produced the wrong value is somewhere in that chain, and locating it by reading code means reading every layer and re-reading it whenever any of them changes.

Answering it from lineage metadata takes seconds, if the metadata exists, and the reason it often does not is that the fine-grained version is genuinely hard to compute.

Three granularities with different costs

Lineage is usually described at one of three levels, and they are not versions of the same thing; they are different products.

Job-level lineage says that job B read dataset X and wrote dataset Y. It is trivially cheap to record, because it is a fact the scheduler already knows: it launched B, and B declared its inputs and outputs. Every orchestration system can produce it with no analysis at all.

Dataset-level lineage is job-level lineage composed into a graph: X feeds Y, Y feeds Z. The cost is graph construction and storage, and the hard part is identity, since the same dataset may be named differently by different jobs. It answers impact analysis questions of the form “if X changes, what breaks”, which is the question that arises before any change to a shared dataset.

Column-level lineage says that Y.total is computed from X.amount and X.tax. It cannot be observed; it must be derived from the query text, which means parsing SQL, resolving names against a catalog, and tracking expressions through subqueries, views, and joins. This is the level that answers “why is this number wrong”, and it is the level that costs a SQL front end and a model of the catalog.

The cost gap is large enough to be the deciding factor. Job-level lineage is a few hundred bytes per run. Column-level lineage requires an analysis that is roughly as expensive as query planning, applied to every query in the estate, and rerun whenever either the query or any referenced schema changes.

Why column lineage needs a parser rather than a regex

The naive approach matches column names in the query text and records a dependency. It fails on the first query that does anything interesting.

A column can appear in a query without being selected: in a WHERE clause, in a GROUP BY, in a join condition, in an ORDER BY. Whether those count as lineage depends on the semantics being modelled. A filter on status changes the output’s content and therefore its values, so a data-flow notion of lineage should include it; a structural notion that only tracks values copied from input to output would exclude it. The two notions give different answers for the same query, and a lineage system has to declare which it implements.

A column can be selected under a different name, computed by an expression, or produced by an aggregate. sum(amount) AS total creates an output column whose value depends on every input row’s amount, not on a single row’s. That dependency is what makes a lineage edge directional and why an aggregate’s output cannot be traced back to one input row.

A column can come from a subquery or a common table expression, which means the dependency has to be resolved through a scope chain. SELECT t.x FROM (SELECT a AS x FROM base) t requires resolving x to a in an inner scope, then to base.a. The same resolution machinery that a query engine uses for name binding is what a lineage analyser needs, which is why lineage implementations are usually built on an existing SQL parser and validator.

Wildcards break the analysis in a way that is specific and common. SELECT * FROM base produces a dependency on every column of base, and INSERT INTO target SELECT * FROM base produces an edge per column only if the analyser knows base’s schema at the time. A schema change that adds a column silently changes what the wildcard means, and lineage recorded before the change is wrong for runs after it. Some systems refuse to expand wildcards without a catalog snapshot; others expand against the current schema and mark the result as approximate.

-- Three output columns, three different dependency shapes.
SELECT
  o.id,                        -- direct copy of one input column
  o.amount * (1 + o.rate),     -- computed from two columns of the same row
  sum(o.amount) OVER (PARTITION BY o.customer_id)  -- depends on all rows of the partition
FROM orders o
WHERE o.status <> 'cancelled';  -- a filter dependency, if the model includes predicates

The scale of the dependency graph

A column-level graph over a warehouse is large, and its size is the reason implementations choose approximations.

The edge count grows with the product of columns and queries rather than with the number of tables. A table of 200 columns written by a query that reads three tables of similar width contributes up to 600 edges, and a view layered on top contributes as many again. A warehouse with a few thousand tables and tens of thousands of queries can produce millions of edges, and each edge needs to be versioned if the graph is to answer questions about a past state.

The versioning is the expensive part. A lineage graph is not a static object; it changes with every schema change and every query rewrite. Storing the graph as of a given time requires either keeping every version or keeping a log of edge additions and removals, and the log grows with the rate of change rather than the size of the estate. Queries that ask “what fed this column on the day the report was wrong” then have to reconstruct the graph at that time, which is a temporal query over the log.

Two design choices reduce the burden. The first is to store edges with a validity interval rather than with a version number, so a query for a point in time is an interval containment test rather than a replay. The second is to record edges only for columns that are actually used downstream, which requires knowing the downstream use and therefore tends to be done after the fact rather than at write time.

Provenance is not lineage

Lineage says which columns a value depends on. Provenance says which rows contributed to a particular output row, and the two differ in a way that matters for debugging.

A lineage edge from orders.amount to report.total tells you that the report’s total depends on the amount column. It does not tell you which order rows were summed, and if the report’s total is wrong, the offending rows are what has to be found. Row-level provenance records, for each output row, the set of input rows that produced it, and for an aggregate that set can be enormous: a total over a million orders has a million contributing rows, and materialising that relationship per output row is larger than the data itself.

This is why full provenance is rarely materialised and instead recomputed on demand by replaying the query with instrumentation. The replay is expensive but bounded to the query being investigated, and it produces an answer that is exact. The practical arrangement is to keep column lineage always, and to treat row provenance as a forensic operation performed when a specific defect needs tracing.

The distinction also explains why “lineage” tools that only track tables are insufficient for debugging even though they are sufficient for impact analysis. Impact analysis asks which jobs to rerun; debugging asks which rows to inspect. The graph that answers the first is coarse and cheap, and the graph that answers the second is fine and expensive, and treating them as one product leads to a system that is either too expensive to maintain or too coarse to be useful. A distribution drift flag on a column is a concrete case: the flag says the column changed, and the upstream set says whether anything upstream changed at the same time.

Static analysis and observed lineage disagree

There are two ways to obtain column lineage, and they produce different graphs.

Static analysis parses the query and derives dependencies from its structure. It works before the query has ever run, which means it can warn about an impact before a change is deployed. It is also subject to every limitation of parsing: dynamic SQL assembled at runtime is invisible to it, temporary views created inside a session may not be in the catalog, and dialect extensions may not parse.

Observed lineage instruments execution and records what the query actually read and wrote, typically from the engine’s own scan and commit events. It is exact about what happened, including dynamic SQL, and it is blind to what has not run. It also reports only the columns the engine actually touched, which for a query with a short-circuiting filter or a partition-pruning predicate is a subset of the columns the query names.

The two are complementary and the disagreement between them is itself a signal. A static edge with no observed counterpart means a query is defined but never executed, or executes with pruning that skips the column. An observed edge with no static counterpart means dynamic SQL is in use, which is worth knowing because it is also invisible to most other forms of review.

# Compose two column-level edges: (src_table, src_col) -> (dst_table, dst_col).
# Transitive closure over a small graph, iterative to avoid recursion limits.
def upstream_of(edges, target, limit=100):
    parents = {}
    for src, dst in edges:
        parents.setdefault(dst, set()).add(src)
    seen, frontier = set(), [target]
    while frontier and len(seen) < limit:
        node = frontier.pop()
        for p in parents.get(node, ()):
            if p not in seen:
                seen.add(p)
                frontier.append(p)
    return seen

What lineage enables that nothing else does

Three capabilities follow directly from a column-level graph, and each has a cost that justifies the analysis only if it is used.

Impact analysis before a change: given a proposed rename or type change, the set of downstream columns that will break is a reachability query. Without the graph, the answer comes from searching query text for the column name, which finds the references that spell it the same way and misses the ones behind views.

Root-cause localisation after a defect: given a wrong column, the upstream set narrows the search from a whole estate to a handful of sources. This is the capability that pays for the analysis, because a defect investigation without it is a manual traversal of the same graph.

Dead-column detection: a column with no downstream edges is either unused or used through a wildcard, and the second case is why the answer is a candidate list rather than a deletion list.

The capabilities that lineage does not enable are worth stating too. It does not tell whether a value is correct, because a dependency edge is not a correctness claim. It does not tell how a value was transformed, because an edge records that a dependency exists rather than the expression that defines it. And it does not survive a change in the analysis tool: two lineage systems that model predicates differently will disagree on the same estate, and the disagreement will be attributed to the data rather than to the model. The graph is a model of the pipeline, and like the schema contract it is derived from, its value depends on the model being declared rather than assumed.