-
-
Notifications
You must be signed in to change notification settings - Fork 191
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Analyzing self-referential foreign keys triggering an infinite loop #1268
Comments
Terrible news: this isn't an infinite loop, it's exponential time! The exponent is the max depth (15), and the base is however many foreign keys are cyclical on the query (3 in the repro). So this roughly creates a foreign key tree of size 3¹⁵. Right now, a tree of foreign key nodes is acyclical, so we determine the max depth at analysis time. There are two "solutions" here:
I'm attempting #2. I've got something that handles the above case just fine, but it's broken some other self-referential tests. I'll continue working on this. |
@Hydrocharged Thanks for the update here. Is there anyway to memoize the search to make it faster? I'm curious what MySQL does here |
It's possible that MySQL may memoize the resulting trees, but I'm not sure how significant the speedup would be with the partial rewrite. Right now it takes forever (might even be practically infinite given memory pressure) to construct the tree given enough foreign keys. Caching the resulting nodes is a part of Solution 2, which also creates a cyclical tree. With the rewrite, fetching a memoized tree versus constructing a new one won't have a large enough of a speedup to be worth the additional complexity, at least not right now. We'd need to do a lot more state tracking for not just foreign keys, but tables as well. I'd wager that MySQL is doing something closer to the partial rewrite, but they very well may be memoizing the resulting tree to really optimize execution times. |
The cause seems to be related to the FK depth rule
repro:
The text was updated successfully, but these errors were encountered: