[CT-677] [Bug] Downstream models do not run correctly after NetworkX 2.8.1

[iknox-fa]

Is there an existing issue for this?

• I have searched the existing issues

Current Behavior

Any 1.0.x version of dbt installed after NetworkX 2.8.1 was released does not correctly run downstream models when using selection syntax. For some reason this does not seem to effect 1.1

Expected Behavior

All downstream models are run

Steps To Reproduce

Install dbt- @ v1.0.x
Create a project with a model_foo and downstream model_bar
Run dbt with selection dbt run --select +model_foo+
Observe that only model_foo is run

Relevant log output

No response

Environment

- OS: MacOS
- Python: 3.10
- dbt: 1.0.6

What database are you using dbt with?

postgres

Additional Context

No response

[barberscott]

https://github.com/networkx/networkx/milestone/21?closed=1 -- looks like 2.8.2 of networkx is incoming...

[barberscott]

2.8.1 broke, but 2.8.2 did not fix whatever is now wrong with the graph stuff and newtorkx.

[iknox-fa]

After quite a few hours of investigation, this is proving a VERY difficult bug to track down.
Here's a synopsis of the work so far.

We're doing this wrong

The issue can be traced back to our use of nx.single_source_shortest_path_length in dbt-core <1.1.x here and here.

Specifically, it's used to return a list of a given node's descendants, and by reversing the graph first, it's ancestors. However, that isn't really what that function is supposed to do! Using the DAG-specific nx.ancestors and nx.descendants works correctly in all versions and should have probably been what we did in the first place. The only downside to this approach is that nx.desc / nx.ances don't offer a max depth option but it's a simple enough thing to implement.

There's still a bug, even when we do it the "right way"

In researching this it was discovered that doing any kind of iteration over self.graph immediately before applying nx.single_source_shortest_path_length seems to "fix" it. This explains why dbt-core>=1.1 works correctly because we changed the method used to reverse the graph to one that actually iterates over it. This makes absolutely no sense since iterating over the graph should not mutate it in any way!!!

I suspect that either we are constructing the initial graph in such a way that causes problems unless it's iterated over OR there's a bug in networkx somewhere very very very not obvious. Unfortunately, I wasn't able to definitively pin down the source of this bug despite several days worth of effort.

[iknox-fa]

@jtcohen6 , @leahwicz Should we create another ticket to further investigate root cause here? I'm low-key concerned about not being able to pin down the exact root cause.... very low-key.

[jtcohen6]

@iknox-fa My inclination here is to move forward with the refactor that you've identified, after several days of detailed investigation. This is critical dbt functionality. It feels most important that we are confident in the approach we're taking going forward—specifically, that it is closely aligned with intended behavior of networkx.

We've now pinned dbt-core v1.0 to use networkx<2.8.1. dbt-core v1.1 is still allowing networkx<3 (since this error didn't occur there). Since we don't feel like we fully understand exactly why the extra iteration step added in v1.1 is working, let's either:

• Backport the change in New ancestor/descendant algo #5326 to 1.1.latest
• Pin v1.1 to a tighter upper bound of networkx

[leahwicz]

@jtcohen6 I like pinning 1.1 and not backporting since it's a change that introduces risk. We can add that to the RC2 that we are going to push out soon

[jtcohen6]

@leahwicz Agree with pinning as the safer bet for v1.1. Let's make sure that gets in for RC2.

[drewbanin]

I spent some time debugging this issue this morning. Two videos for you:

First, A walkthrough of using git bisect to find the first commit which breaks the graph traversal behavior in dbt Core

https://www.loom.com/share/084a91690e6744738063ad78c7b5e79e

The first commit in Networkx which causes the errant behavior is: networkx/networkx@f50fc70

Second, A deep dive with a debugger to figure out the root cause of the regression. I feel like I'm 90% of the way to understanding the culprit, but I'm missing the specific place where (surprise!) a cache is not being invalidated/updated

https://www.loom.com/share/a67fa29caaac436997e278742d61c031

Here's the code that I'm using to repro this issue: https://gist.github.com/drewbanin/60f3b6a5d19d8af694dc6830c8c986b3