Wrong JOIN with nested FKs
Sebastian Goll
I'd like to draw your attention to ticket #16715:
"Wrong JOIN with nested null-able foreign keys"
https://code.djangoproject.com/ticket/16715
It seems that the Django query generator sometimes picks the wrong join type in the following situation:
Model A
| (Relation A/B: null=True)
v
Model B
| (Relation B/C: null=False)
v
Model C
A priori, the correct/default join for Relation A/B is LEFT OUTER JOIN, while the correct join for Relation B/C is INNER JOIN.
However, when combining all three models, the join between Model B and C must be promoted to LEFT OUTER JOIN. If we wouldn't do that, instances of Model A that do not reference an instance of Model B would be missing in the resulting queryset: the INNER JOIN wouldn't be able find the matching Model C with a primary key of NULL which results from the join between Models A and B for As without referenced Bs.
This promotion works in most cases and is done in django/db/models/sql/query.py, methods 'promote_alias' and 'promote_alias_chain' of class Query.
However, the promotion fails, and Django falls back to the wrong INNER JOIN for Relation B/C in at least some cases involving 'select_related' and 'values'. In those cases the relation between A and B can either be an explicit foreign key (A -> B) or an implicit/reverse one such as introduced by one-to-one relations (e.g. in multi-table inheritance).
I outlined those cases in #16715. I also provided two semi-elaborate tests for my observation ("wrong-join-test-r16910.patch" and "nested-foreign-key-test-r16914.patch").
What do you think? Is this something that can be fixed easily? My fears are that this points to some deeper problem within the query generator, in which the generator fails to correctly promote the join type for the nested relation.
Sebastian.
Sebastian Goll
I'm afraid I'll have to reply to my own message because nobody else did. ;) Please read on. Also, please note that the original report is now over five weeks old, with no real solution yet in sight.
On Thu, 29 Sep 2011 21:52:23 +0200
Sebastian Goll <sebasti...@gmx.de> wrote:
> I'd like to draw your attention to ticket #16715:
>
> "Wrong JOIN with nested null-able foreign keys"
> https://code.djangoproject.com/ticket/16715
I think this is a serious bug which should be further investigated. There is the possibility that also other queries do not work as expected, when multiple models with (null-able) foreign keys are involved.
Can somebody please tell me if the latest test I supplied is valid ("nested-foreign-key-test-r16914.patch")? I'd like to get the confirmation that this is indeed a bug and not somehow intended behavior.
If this is indeed a bug, what would be the best way to fix it? Unfortunately, I'm not fluent in the internals of the Django query generator, so at least some help is required here.
In fact, any help in resolving this issue is greatly appreciated.
For a summary, please see my original post to this list (in case you didn't receive it):
"Wrong JOIN with nested FKs"
http://groups.google.com/group/django-developers/msg/4c5dcff7beaf06d9
Sebastian.
Russell Keith-Magee
> Hello,
>
> I'm afraid I'll have to reply to my own message because nobody else did. ;) Please read on. Also, please note that the original report is now over five weeks old, with no real solution yet in sight.
>
>
> On Thu, 29 Sep 2011 21:52:23 +0200
> Sebastian Goll <sebasti...@gmx.de> wrote:
>
>> I'd like to draw your attention to ticket #16715:
>>
>> "Wrong JOIN with nested null-able foreign keys"
>> https://code.djangoproject.com/ticket/16715
>
> I think this is a serious bug which should be further investigated. There is the possibility that also other queries do not work as expected, when multiple models with (null-able) foreign keys are involved.
It is certainly a bug. However, I disagree that it is "serious" -- at
least, not by the measure that the Django project applies.
We certainly don't like queries that return the wrong results, but
being pragmatic, unless:
1) The query is clearly a common case, or
2) The query will cause data to be irretrievably lost, or
3) The behavior has changed in the last release
then we don't consider it critical. To clarify -- (1) gets triggered
when mailing lists and IRC are full of people who have hit the
problem; (2) applies to deletion queries; (3) relates to interaction
with new features and our backwards compatibility policy.
Unfortunately, there are plenty of ORM bugs that result in incorrect
queries, and many of them are *much* older than 5 weeks. You've done a
lot of work here triaging the problem, but I wouldn't 100% rule out
the possibility that there are other, very closely related tickets.
So - how do you get this problem fixed? Well, fixing bugs deep in the
ORM take a lot of time, and there's a limited subset of people with
enough experience in the ORM to do the job. Unfortunately, there's no
good fix to this end of the problem. All I can suggest is:
1) Build your own experience with the internals of the ORM. As part
of this learning process, document what you learn -- we would very
much like to have better documentation of the internals of Django's
ORM, but writing that documentation takes time.
2) Build your value to those in the core team that can help you.
Rather than focussing on just this one bug which is obviously
important to you personally, find other ORM-related bugs and help out.
It's basic human nature to want to help people who have helped you,
and you can exploit this to your own benefit -- if you do triage and
provide patches for other ORM bugs, you earn a whole lot of karma with
the people who are in a position to help you, which increases the
chances that your pet bug will get attention.
Sorry that I can't offer you a "wave this wand and your ticket will be
fixed" solution, though :-)
Yours,
Russ Magee %-)
Łukasz Langa
1) Build your own experience with the internals of the ORM. As part
of this learning process, document what you learn -- we would very
much like to have better documentation of the internals of Django's
ORM, but writing that documentation takes time.
Best regards,
Łukasz Langa
Senior Systems Architecture Engineer
IT Infrastructure Department
Grupa Allegro Sp. z o.o.
Russell Keith-Magee
> Wiadomość napisana przez Russell Keith-Magee w dniu 3 paź 2011, o godz.
> 16:07:
>
> 1) Build your own experience with the internals of the ORM. As part
> of this learning process, document what you learn -- we would very
> much like to have better documentation of the internals of Django's
> ORM, but writing that documentation takes time.
>
>
> How would you like to see that done? I find this interesting, if only to see
> how suitable would increasing support for multiple inheritance be.
Documentation of the internals of the query engine has been on the
'nice to have' list for a long time, but I can't say I've given any
deep thought to what that documentation would look like. It doesn't
need to be as comprehensive as a beginners tutorial -- we can assume
that if you're spelunking around the ORM internals, you're not a
complete novice. A few topics you might want to cover include:
* Explaining the data structures used by the query.sql module
* Explaining the lifecycle of query construction
* Explaining the query vs compiler separation
Beyond that, he (or she) who paints the bikeshed gets to pick the color :-)
I would also add that as with all documentation, the first draft is
the hard draft. Once there is *some* documentation, it's a lot easier
for other people to contribute and come up with suggestions about how
it could be better. A first cut of accurate, lifecycle complete but
detail incomplete documentation may be enough to get the ball rolling.
Yours,
Russ Magee %-)
Sebastian Goll
Russell Keith-Magee <rus...@keith-magee.com> wrote:
> 1) Build your own experience with the internals of the ORM. As part
> of this learning process, document what you learn -- we would very
> much like to have better documentation of the internals of Django's
> ORM, but writing that documentation takes time.
Alright. I spent most of last night (heck, the entire last night!) digging through files in the Django db/models/sql folder. I still don't understand half of what I see there, but I think I might have found the root of the select_related/values problem.
I attached another patch to #16715 (a very simple patch) which has the potential to fix this bug in the right place ("patch-nested-foreign-keys-with-test-r16923.patch").
I think I identified two places in "django/db/models/sql/compiler.py" and "django/db/models/sql/query.py" which make invalid assumptions about null-able fields/references. Changing these to what I think is the correct/intended behavior resolves the issue. More details about this in #16715.
Maybe more importantly, my patch does not to my knowledge introduce any new bugs, as measured by the outcome of the Django test suite.
Please let me know what you think. I spent several hours on this patch, let's hope it was not a total waste of time. ;)
Sebastian.
Sebastian Goll
akaariai has proposed a patch that solves the bug described below.
It is attached to ticket #16715. How do we proceed from here?
Sebastian.
On Thu, 29 Sep 2011 21:52:23 +0200
Sebastian Goll <sebasti...@gmx.de> wrote: