Preparing your workspaceloading the brief, studio & editor…

Loadingone moment…

Plan a backfill through a dependency graph · Python scenario · D8LooP

Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.

CODE WORKSPACE

Plan a backfill through a dependency graph

A bug in one transformation was fixed, and the table it produces has to be rebuilt. Everything that reads that table is now stale, and everything that reads those is stale too. The current practice is to rerun the whole DAG, which takes eleven hours and rebuilds a lot of data that never changed. Write plan_backfill(dag, completed, targets, max_parallel). The dag maps each task to its upstream dependencies.

Function to write

plan_backfill(dag: dict, completed: list, targets: list, max_parallel: int) -> dict

A dict with the waves of tasks to run in order, the blocked tasks and the full affected set.

How to approach it

Invert the graph to find what is downstream, then schedule that set in waves.

Sample cases

+ 2 held back until you submit

one upstream table changed

Everything downstream of the changed task must rerun, and one branch of the graph must not.

Input

Argument 1

{
  'extract_orders': [],
  'extract_customers': [],
  'clean_orders': [
    'extract_orders'
  ],
  'clean_customers': [
    'extract_customers'
  ],
  'join_facts': [
    'clean_orders',
    'clean_customers'
  ],
  'daily_metrics': [
    'join_facts'
  ],
  'weekly_report': [
    'daily_metrics'
  ],
  'unrelated_report': [
    'extract_customers'
  ],
  'needs_missing': [
    'never_defined'
  ]
}

Argument 2

[
  'extract_orders',
  'extract_customers',
  'clean_orders',
  'clean_customers',
  'join_facts',
  'daily_metrics'
]

Argument 3

[
  'clean_orders'
]

Argument 4

Returns

{
  'waves': [
    [
      'clean_orders'
    ],
    [
      'join_facts'
    ],
    [
      'daily_metrics'
    ],
    [
      'weekly_report'
    ]
  ],
  'blocked': [],
  'affected': [
    'clean_orders',
    'daily_metrics',
    'join_facts',
    'weekly_report'
  ]
}

nothing to backfill

No targets means no waves rather than a plan to rerun the whole graph.

Input

Argument 1

{
  'extract_orders': [],
  'extract_customers': [],
  'clean_orders': [
    'extract_orders'
  ],
  'clean_customers': [
    'extract_customers'
  ],
  'join_facts': [
    'clean_orders',
    'clean_customers'
  ],
  'daily_metrics': [
    'join_facts'
  ],
  'weekly_report': [
    'daily_metrics'
  ],
  'unrelated_report': [
    'extract_customers'
  ],
  'needs_missing': [
    'never_defined'
  ]
}

Argument 2

[
  'extract_orders',
  'extract_customers',
  'clean_orders',
  'clean_customers',
  'join_facts',
  'daily_metrics'
]

Argument 3

[] (empty list)

Argument 4

Returns

{
  'waves': [],
  'blocked': [],
  'affected': []
}

unlimited parallelism

With no cap each wave is everything that is ready, which shows the true critical path.

Input

Argument 1

{
  'extract_orders': [],
  'extract_customers': [],
  'clean_orders': [
    'extract_orders'
  ],
  'clean_customers': [
    'extract_customers'
  ],
  'join_facts': [
    'clean_orders',
    'clean_customers'
  ],
  'daily_metrics': [
    'join_facts'
  ],
  'weekly_report': [
    'daily_metrics'
  ],
  'unrelated_report': [
    'extract_customers'
  ],
  'needs_missing': [
    'never_defined'
  ]
}

Argument 2

[
  'extract_orders',
  'extract_customers',
  'clean_orders',
  'clean_customers',
  'join_facts',
  'daily_metrics'
]

Argument 3

[
  'extract_customers'
]

Argument 4

Returns

{
  'waves': [
    [
      'extract_customers'
    ],
    [
      'clean_customers',
      'unrelated_report'
    ],
    [
      'join_facts'
    ],
    [
      'daily_metrics'
    ],
    [
      'weekly_report'
    ]
  ],
  'blocked': [],
  'affected': [
    'clean_customers',
    'daily_metrics',
    'extract_customers',
    'join_facts',
    'unrelated_report',
    'weekly_report'
  ]
}

Constraints

1The affected set is the targets plus everything transitively downstream of them. A task that does not read an affected table is not affected.
2A task may run when every affected upstream has already run in an earlier wave, and every unaffected upstream is in completed.
3An upstream that is neither affected nor completed means the task cannot run safely. It is blocked, and so is everything downstream of it.
4Group the runs into waves: each wave is every task that is ready, sorted alphabetically, capped at max_parallel.
5Tasks that cannot run — blocked or in a cycle — are reported and the planning terminates rather than looping.
6A target that is not in the dag affects nothing.
7A max_parallel of zero or less describes no plan at all.
8Return the waves, the blocked tasks sorted, and the affected set sorted.

Worked example

Rebuilding clean_orders makes join_facts stale, which makes daily_metrics stale, which makes weekly_report stale. Four tasks, not nine — unrelated_report reads extract_customers and nothing else, so it does not change and does not need to run. join_facts also depends on clean_customers, which is not affected. It does not need to be rerun, but it does need to have run: it is in completed, so join_facts can proceed. If it were neither affected nor completed, running join_facts would join against a table that does not exist, and the plan has to refuse rather than produce it. The waves matter as much as the set. With a cap of 2 the plan is a sequence, because this chain has no width — each task genuinely waits for the one before. A plan that lists four tasks without saying they are sequential invites somebody to launch them together and get four different kinds of wrong.

What this tests

Reachability in the downstream direction, which is the opposite of the direction a scheduler normally walks, plus the distinction between an upstream that must be rerun and one that must merely exist. Both are what make a backfill minimal instead of total.

PYTHONplan_backfill(dag: dict, completed: list, targets: list, max_parallel: int) -> dict

AI evaluation

The reviewer reads your query.

Submit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.

Desktop only

This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.

Read the library instead Back to modules