dbt-core usage of NetworkX: API usage and slowdowns

[nv-rliu]

Hi. I would like to understand what parts of dbt-core depends on algorithms from Networkx. What nx API calls it uses the most, for what purposes, and if you've ever experienced any slowdowns when scaling up graph sizes?

Searching in previous discussions, I noticed that a community member proposed switching to rustworkx to reduce the time it takes to create graphs in workflows. I'm assuming this was a concern due to NetworkX's pure-Python implementation being "slow"?

[nanjeshramesh]

Looked at core/dbt/graph/graph.py on the 1.10.latest branch since main has moved on (more on that below). The Graph class wraps a plain nx.DiGraph and the manifest's dependency edges live in that.

API surface used:

• nx.bfs_edges, through a filtered nx.subgraph_view, for ancestors() and descendants(). The subgraph view is there to exclude parent_test edges from traversal.
• nx.descendants directly, for get_dependent_nodes().
• Plain DiGraph mutation for get_subset_graph: copy(), in_degree/out_degree, remove_nodes_from, add_edges_from, used in a loop that strips nodes outside the selection while rewiring transitive edges around them so dependents of a removed node still see its ancestors.

The one thing worth noticing: select_children and select_parents, which is what backs dbt run --select and is on the hot path for basically every invocation, do not use nx.ancestors/descendants at all. They hand roll a layer by layer BFS over graph.out_edges/in_edges directly. I'd guess that's because ancestors/descendants don't give an easy hook for the parent_test edge exclusion, so they went manual instead of wrapping another subgraph_view per call. That manual version is where I'd expect any per invocation cost to concentrate on a big graph, rather than in bfs_edges itself.

get_subset_graph is the other place I'd look. It's an iterative node removal loop with an is-this-node-safe-to-drop check on every pass, that's more of a graph size concern than a networkx-specific one, but it does mean the subgraph selection step doesn't scale linearly with model count.

On the rustworkx thread, I think your hypothesis was right, just already answered a different way. dbt-core's main branch has moved off this file structure entirely, graph resolution now lives in crates/dbt-tasks-sa/src/graph.rs as part of the Fusion rewrite. So the project already made the same call the community discussion was proposing, it just did it as a full engine rewrite rather than a drop in networkx to rustworkx swap.