Topological Execution
If A feeds C and B feeds C, then A and B can run together and C must wait. What that ordering buys — parallelism, correctness of order, selective rebuild — and the one thing it emphatically does not buy.
Who needs this, what one row is, and why the obvious build breaks
Every lesson starts from the consumer, because designing from the source outward is this domain's characteristic mistake.
What exactly does executing a graph in topological order guarantee, and what does a completed topological run still fail to tell you?
The engineer waiting for the morning build, and the engineer waiting to rebuild one branch during an incident. Both want the same property: work that can proceed does proceed, and work that must wait actually waits.
The unit is one node execution — one model built, one task run — and the ordering constraint between two of them. Everything in this lesson is about the *relation between two nodes*, never about the contents of either (DAGs in Data Pipelines).
Run the models in the order they were written, one at a time. It respects dependencies as long as the file order happens to be right, it is trivially debuggable, and the total time is the sum of every model.
The build takes as long as every model added together, even though most of them do not depend on each other. Two independent staging models built from two independent sources are serialised for no reason but filename order (Why Eight Cores Give You Four and a Half).
- The build takes as long as every model added together, even though most of them do not depend on each other. Two independent staging models built from two independent sources are serialised for no reason but filename order (Why Eight Cores Give You Four and a Half).
- A model is inserted and the file ordering no longer matches the dependency ordering. It builds successfully, reading the previous run's output of its upstream, and produces a plausible number that is one build stale — permanently (Stale Dashboards).
- One model fails. Everything after it in the list is skipped, including nodes on completely unrelated branches that would have been fine (When a Task Fails Mid-DAG).
- A fix to one model requires a rebuild. Without a notion of descendants, the only safe option is to run everything, which turns a one-model fix into a full-history rebuild (Compute Waste).
- The build finishes green. Every model ran, in order, and one of them consumed an empty upstream because ingestion silently produced nothing — and there is nothing in a completed topological run that could have noticed (The Pipeline Succeeded. The Data Is Wrong.).
What is actually happening
- A topological order is any sequence of nodes in which every node appears after all of its dependencies. For a graph with independent branches there are many valid orders, and the executor is free to choose among them (Topological Sort).
- The practical algorithm is Kahn's: repeatedly take every node whose dependencies are all complete, run them, mark them done, repeat. Each round of that loop is a level — a set of nodes that can genuinely run concurrently — so the same algorithm produces the ordering and the parallelism at once (Fork/Join).
- The number of levels is the graph's depth, and it is a hard floor on wall-clock time. Adding workers widens each level and does nothing to the number of levels, which is why deep graphs stay slow no matter what you provision (Amdahl's Law).
- Selective rebuild is the same ordering applied to a subgraph. Choose a node, take its descendant set by forward traversal, topologically order that set, run it. Everything outside the set is provably unaffected and must not be touched (Depth-First Search (DFS)).
- Failure handling falls out of the structure too. When a node fails, its descendants are unrunnable and everything else in the graph is unaffected. A good executor skips exactly the descendant set and continues with the rest, which turns one failure into one branch missing rather than one build lost (Partial Failure).
- What the ordering does not do is inspect anything. Topological execution is a statement about the *edges*; the nodes are opaque to it. A node that produced zero rows, duplicated rows or nonsense satisfies its ordering obligations perfectly (Data Tests).
Levels: what can run together, and what cannot
The rule is simple enough to state in one line. If A feeds C and B feeds C, then A and B may run at the same time, and C runs after both. Everything about parallel scheduling in a transformation build is that rule applied repeatedly.
Running the algorithm produces levels, and the levels are worth drawing because they make two properties visible that a flat list hides. The width of the widest level is the most parallelism the graph can ever use, and the number of levels is the floor on how long the build takes no matter how many workers exist.
That second number is the one people underestimate. A project with six sequential layers has at least six rounds, and if each round takes a couple of minutes then the build has a floor that no amount of provisioning touches. Reducing the floor means restructuring the graph — collapsing layers that exist only by convention, or splitting a long chain into independent branches (Model Layering).
Which node is the earliest one that is wrong, and can you prove what depends on it?
when The node is a leaf, or you have established that nothing downstream has been built since it broke.
cost Cheapest and the easiest to get wrong. If anything downstream did read the bad version, you have now created a disagreement between two models rather than fixed one (Validating a Backfill Before You Publish).
when The default. The earliest wrong node is identified and the graph is trusted to be complete.
cost Proportional to how wide the graph fans out below that node. Requires every node in the set to be idempotent, and requires the graph to have no missing edges (Reprocessing vs Retrying).
when Only some periods are wrong, and the models support a range parameter.
cost The cheapest correct option and the one with the most ways to go wrong — an off-by-one on the boundary leaves a gap or a double-count at the edges (Planning a Backfill).
when The graph is not trusted, the blast radius genuinely is everything, or the definition itself changed and all history must be recomputed.
cost Proportional to all history, on every node. It is also a fresh chance to break something that was correct, so it is not the safe option it is assumed to be.
when The affected period is closed, the consumers are few, and the recompute costs more than the error is worth.
cost The number in the warehouse stays wrong. This is a legitimate answer and it must be recorded somewhere consumers will find it, or it becomes a mystery six months later (Dataset Documentation).
Level 1 stg_orders stg_refunds stg_customers stg_products
| | | |
+------+------+ | |
| | |
Level 2 int_orders_enriched <-------+----------------+
|
Level 3 fct_orders
/ \
Level 4 customer_metrics revenue_daily
\ /
Level 5 exec_dashboard_extract
width of widest level : 4 -> the most parallelism this graph can use
number of levels : 5 -> the floor on wall-clock time, at any scale
critical path : stg_orders -> int -> fct -> metrics -> extract
Adding a sixth worker changes nothing here.
Removing a layer changes everything.When a node fails, what else is still runnable
A failure inside a graph is a much better situation than a failure inside a list, and most platforms throw the advantage away. The graph knows exactly which nodes become unrunnable when one fails: the descendant set, and nothing else. Every other branch is unaffected and could complete.
The default in many executors is to stop the whole build on the first failure. That is the conservative-looking choice and it is usually the expensive one — it wastes the branches that were healthy, it delays discovering whether they were healthy, and it converts one broken model into a morning with no fresh data at all.
The alternative has its own cost, and it must be stated to consumers rather than hidden. A build that skipped one branch leaves the platform partly fresh and partly stale, and a consumer joining a model from the fresh branch to one from the stale branch reads two different points in time. That is a real hazard and it is manageable; a silent one is not (Atomic Publish).
| Trigger | Symptom | Cause | Response |
|---|---|---|---|
stg_orders fails on a cast error. | The whole build aborts, including four staging models from unrelated sources that had already succeeded. | A stop-on-first-failure policy, which treats the graph as a sequence rather than as a set of independent branches. | Skip the descendant set and continue everything else. One broken source should cost one branch, not the morning (Partial Failure). |
stg_orders fails, and its descendants are skipped correctly. | fct_orders is yesterday's. revenue_daily, built from an unrelated branch, is today's. A dashboard joining them shows a mismatch nobody caused. | Per-node publication with no cross-node atomicity, which is the normal state of a transformation build. | Surface per-model freshness to consumers, and for models that must agree, publish them together or not at all (Freshness Monitoring). |
A grain test on stg_orders fails; the model itself built fine. | Descendants build anyway on data that is known to be wrong, and publish. | Tests configured to report rather than to gate. An assertion that runs after publication is a monitor, not a check (Data Tests). | Make test failures block the descendant set exactly as a build failure does. This is the only point at which ordering and correctness interact. |
| A transient warehouse error fails one node. | An entire branch skipped for a problem that would have gone away on a retry. | No retry policy at the node level, so infrastructure noise is indistinguishable from a real failure (Retries in Pipelines). | Retry idempotent nodes a bounded number of times before skipping descendants — and be sure they really are idempotent, because a retried appending node duplicates. |
| A node fails after writing some of its output. | A partially written relation that consumers can read, and that a retry will append to rather than replace. | A non-atomic write. The graph's guarantees stop at the boundary of each node and say nothing about what a node leaves behind (Atomic Publish). | Write to a staging location and swap on success, so a failed node leaves the previous version intact rather than a half-built one. |
What a correctly ordered build still does not know
Topological execution is a guarantee about edges. Every node ran after everything it reads. That is genuinely valuable — it removes a whole class of ordering bug — and it is easy to mistake for a broader promise than it makes.
Consider the two most common data incidents. An upstream extract produced zero rows because a source API changed its pagination: every node builds successfully, in perfect order, over an empty table, and the fact table gains nothing. A dimension gained duplicate keys from a non-idempotent re-run: every node builds successfully, in perfect order, and the join fans out. In both cases the ordering guarantee was honoured completely and the output is wrong.
This is why the assertions have to be *gates* rather than reports. A test that runs after the build tells you the bad data has published. A test that blocks descendants makes the ordering guarantee and the correctness question interact, which is the only way they ever do (Data Tests).
| Check | Expresses | Catches | Still misses |
|---|---|---|---|
| Every node completed in dependency order | No node read an upstream that had not been built this run. | Missing or misordered execution; a node inserted in the wrong place in a hand-maintained sequence. | Everything about content. Empty, duplicated and semantically wrong outputs all complete in perfect order (The Pipeline Succeeded. The Data Is Wrong.). |
| Source freshness assertion at every entry node | The data this build read was actually updated recently. | A source that stopped refreshing, an ingestion job that failed silently, a connector stuck at an old position. | A source that is fresh and wrong. It also fires falsely on any period where the source genuinely produced nothing (Freshness Checks). |
| Grain assertion on each node, blocking descendants | Each node produced the unit it claims to produce. | Fan-out joins, failed deduplication, an aggregate grouped by the wrong key. | Correct grain with wrong values. Uniqueness says nothing about whether the amount is right (Grain: What Does One Row Represent?). |
| Row count per node versus its own history | This build produced a normal amount of data. | A partial load, an empty upstream, a filter that suddenly excludes a category. | Any error that preserves volume, which is most value-level bugs, and slow drift of any kind (Volume Anomalies). |
| Re-running a closed period and comparing outputs | The graph is deterministic — a function of its inputs, not of when it ran. | A node reading mutable current state, an append that should have replaced, a now() inside logic. | Determinism is not correctness. A deterministic graph reproduces its wrong answers exactly, which makes them look reliable (Idempotent Data Pipelines). |
The first row is what topological execution provides. Every row below it has to be added deliberately, and a platform that stops at the first row has monitoring that structurally cannot see its most common failures.
How to build it
Most important first.
- Let the executor choose the order within a level. Any pinned order is either redundant with the graph or is encoding a dependency that should have been an edge.
- Set concurrency from what the warehouse can absorb rather than from the graph's width. Running the whole level at once when the warehouse queues them serially adds contention and no speed (Work Stealing).
- Make selective rebuild the default recovery action and full rebuild the exception that must be argued for. The descendant set is computable; running everything is the answer you give when you cannot compute it.
- On failure, skip the descendant set and continue everything else. Stopping the world on the first failure wastes the branches that were fine and delays discovering whether they were (Retries in Pipelines).
- Attach the data assertions to the node, so that a failing test blocks descendants exactly as a failing build would. That is the only way ordering and correctness interact at all — and it has to be built in deliberately (Data Quality).
- Measure the critical path and treat it as the freshness budget. Optimising a node that is not on it changes nothing a consumer can perceive (DP on DAGs).
What this actually promises
Naming the guarantee you do not have is worth more than naming the one you do — everything downstream inherits the weakest promise in the chain.
- Guaranteed: every node ran after everything it reads, on this run. That is the complete list of what topological execution promises.
- Guaranteed within the graph only. A node whose real dependency is outside the project — an ingestion job, a file drop, a manually maintained table — has no ordering guarantee at all, and the graph will not say so (Orchestration).
- Not guaranteed: that any node read *fresh* data. Ordering says "after", not "after it was updated today". A source that stopped refreshing yields a perfectly ordered build over yesterday's data (Freshness Checks).
- Not guaranteed: atomicity across nodes. Between the first node completing and the last, consumers reading two different models see two different vintages unless something else provides atomicity (Atomic Publish).
- Not guaranteed: anything about data correctness. This is the point the rest of the lesson exists to make.
Can I trust it?
A green pipeline is evidence that code ran. These four fields are the evidence that the data is right.
- The check that matters here is not about ordering at all — it is a source freshness assertion at every entry node, so a build over stale inputs fails rather than succeeding.
- Add per-node row-count and grain assertions that block descendants on failure. Without blocking, a test is a report about data that has already published (Data Tests).
- Both miss the case the ordering hides best: a node that read the correct upstream at the correct time and computed the wrong thing. Ordering is orthogonal to meaning, and no amount of correct sequencing produces a correct definition (Two Dashboards, Two Numbers).
- Freshness is bounded below by the critical path — the longest dependency chain — and that number is set by the shape of the graph rather than by the size of the cluster.
- Parallelism reduces total wall-clock time only up to the point where the widest level saturates available concurrency. Past that, every additional worker is idle and the build time is unchanged (Why Eight Cores Give You Four and a Half).
- Selective rebuild is the freshness lever during an incident: recovering one branch takes the length of that branch, not the length of the whole graph, which is frequently the difference between a corrected number before the morning meeting and after it.
- Adding an edge can lengthen the critical path and serialise two nodes that used to share a level. It is a correctness improvement and a freshness regression at the same time, and only one of the two is usually noticed.
- Removing an edge that was real produces a node that runs earlier and reads stale data successfully. This is the most dangerous single edit available in a transformation project (Stale Dashboards).
- Splitting a node into two adds a level if they are dependent and adds width if they are not. Which one you get is worth knowing before the change rather than after the build slows down.
- Recovery is selective rebuild: earliest wrong node, descendant set, topological order, run. The remainder of the graph is untouched and provably so (Reprocessing vs Retrying).
- Every node in the rebuilt set must be idempotent, or the second run of an appending node compounds the error it was meant to fix (Idempotent Data Pipelines).
- Validate before publishing the rebuilt branch. A rebuild that ran in the correct order and produced the wrong answer has failed in exactly the way this lesson warns about (Validating a Backfill Before You Publish).
What can go wrong
- A missing edge, so a node is placed in an earlier level and reads last run's output. Successful, ordered, and one generation stale.
- A stop-the-world failure policy that abandons branches unrelated to the failure, delaying everything and hiding whether those branches were healthy.
- Concurrency set from graph width rather than warehouse capacity, so a wide level causes contention and the build gets slower as it gets more parallel.
- A descendant rebuild that ran but stopped short of the leaves, leaving two models at different vintages.
- The mitigation failing: tests that run *after* the whole build rather than as node gates, so failing assertions describe data that consumers are already reading.
- "The DAG completed, so the data is correct." A completed topological run proves that ordering was respected. It says nothing about content, and the two most common data incidents — an empty upstream and a fan-out join — both complete successfully (The Pipeline Succeeded. The Data Is Wrong.).
- "More workers means a faster build." Only up to the width of the widest level, and only if the warehouse can actually execute them concurrently. Beyond that the critical path is the whole story (Amdahl's Law).
- "Topological order means the right order." It means *a* correct order. There are many, they differ substantially in duration and in how early failures surface, and choosing among them is an optimisation the ordering guarantee does not make for you.
- "Selective rebuild is risky, full rebuild is safe." A full rebuild is only safe if every node is idempotent — the same condition selective rebuild requires — and it additionally rewrites data that was known to be correct, which is a fresh opportunity to break it (What Backfills Break).
Operating it
- Per-level start and finish times, so the critical path is visible rather than inferred. The slowest node in the widest level is usually where the wall-clock time is (Pipeline Metrics).
- Warehouse concurrency and queue depth during the build. A level that runs "in parallel" while the warehouse serialises it is a common and invisible waste (The Backlog Arithmetic: Four Levers and a Drain Time).
- Skipped-node counts per run, split into skipped-because-upstream-failed and skipped-because-unselected. Those are very different situations and one summary number conflates them.
- At 10x model count, ordering stops being something a person can verify and the derived graph becomes load-bearing rather than convenient.
- At 100x, the critical path dominates and restructuring the graph — collapsing thin layers, breaking a long chain into independent branches — becomes the only remaining performance lever (Pipeline Parallelism: Different Items, Different Stages).
- Warehouse concurrency limits usually bind before graph width does, so beyond a certain size the executor is queueing rather than parallelising, and the graph's theoretical width is irrelevant (Parallelism Moves the Load Downstream).
- Parallel execution does not reduce compute cost — the same work is done. It reduces wall-clock time, and it can *increase* cost through contention and retries (Parallel Overhead).
- Selective rebuild is the genuine cost saving, and its size is entirely determined by the descendant set — a modelling property decided long before the incident (Cost Attribution).
- The most expensive habit is the full rebuild used as a substitute for knowing what changed. It costs proportional to all history to fix one day (Compute Waste).
- Maximum parallelism gives the fastest build and the most warehouse contention, and it makes failures arrive in a less predictable order. Constraining concurrency is often faster in practice than allowing everything.
- Skipping only the descendant set on failure keeps healthy branches moving and produces a build that is partly fresh and partly stale — which consumers must be told about, or they will read across the boundary.
- Selective rebuild is precise and requires trusting the graph completely. One missing edge and "provably unaffected" becomes "assumed unaffected", which is the assumption that produces the next incident.
Topological levels — what can run at the same time
Change an input and watch which number moves — and which one does not. Everything here comes from a model in this repository, not from a measurement.
Where this applies
Almost nothing here is universal. These labels say what each claim is specific to, and where a different engine, format, warehouse or scale would differ.
- GENERALTopological ordering, level-based parallelism and descendant-set rebuild are graph properties and behave identically in every executor. What differs is the failure policy — whether a failed node halts the build or only its descendants — and that is a configuration choice with real consequences.
- WAREHOUSE-SPECIFICAvailable concurrency is a warehouse property: some serialise beyond a configured slot count, some queue, some autoscale. The same graph therefore exhibits very different level durations across warehouses, and graph width is only useful up to whatever the engine will actually run at once.
Where the depth lives
This domain teaches how data moves and how you know it arrived intact. It hands the rest off by name.
- — Distributed Systems owns what it means for a set of nodes to agree that a level is complete, and what happens when the executor itself fails mid-level. This lesson assumes a reliable coordinator; that domain explains why that assumption costs something.