Unnecessary join when using a reverse foreign-key filter and reverse foreign-key aggregate call

[Ben Davis]

(This started as #16554, but it was only half-valid, so I'm re-submitting the valid part here)

Django allows you to perform queries across reverse foreign key relationships. If, however, you need to access that same relationship in a filter and an aggregate call, the ORM creates unnecessary joins.

Example:

app/models.py

class Author(models.Model):
    first_name = models.CharField(max_length=30)
    last_name = models.CharField(max_length=30)
    email = models.EmailField()

class Book(models.Model):
    author = models.ForeignKey(Author, related_name='books')
    title = models.CharField(max_length=100)
    genre = models.CharField(max_length=20, choices=(
        ('SCIFI', 'SciFi'),
        ('FANTASY', 'Fantasy'),
        ('NONFICTION', 'NonFiction')
    ))
    published = models.DateField()
    pages = models.IntegerField()

The django query:

qs = Author.objects.annotate(pages_written=Sum('books__pages'))
qs = qs.filter(books__genre='SCIFI')
print qs.query

Generated SQL:

SELECT "app_author"."id", "app_author"."first_name", "app_author"."last_name", "app_author"."email", SUM("app_book"."pages") AS "pages_written" 
FROM "app_author" 
LEFT OUTER JOIN "app_book" ON ("app_author"."id" = "app_book"."author_id") 
INNER JOIN "app_book" T3 ON ("app_author"."id" = T3."author_id") 
WHERE T3."genre" = 'SCIFI'
GROUP BY "app_author"."id", "app_author"."first_name", "app_author"."last_name", "app_author"."email"

[Anssi Kääriäinen]

Confirmed. This is somewhat related to #10060, but not a duplicate of that ticket. I am a bit surprised if there is not a duplicate of this ticket, but I could not find any. Maybe I am just too tired...

The problem reported is not easy to fix. The main issue is that reverse (and m2m) filtering should be done using subqueries and WHERE EXISTS, WHERE pk IN or joining the subquery. As implemented now the joins generated will return duplicate rows, and that causes the problem. That is, the above query should be written as

SELECT ... 
FROM "app_author" 
LEFT OUTER JOIN "app_book" ON ("app_author"."id" = "app_book"."author_id")  
WHERE EXISTS (SELECT 1 FROM app_book T3 WHERE T3.author_id = app_author.id and t3.genre = 'SCIFI')
GROUP BY ...

or

SELECT ... 
FROM "app_author" 
LEFT OUTER JOIN "app_book" ON ("app_author"."id" = "app_book"."author_id") 
WHERE app_author.id IN (SELECT author_id FROM app_book T3 WHERE t3.genre = 'SCIFI')
GROUP BY ...

or

SELECT ... 
FROM "app_author" 
LEFT OUTER JOIN "app_book" ON ("app_author"."id" = "app_book"."author_id") 
JOIN (SELECT author_id FROM app_book T3 WHERE t3.genre = 'SCIFI') T5 ON ("app_author"."id" = T5."author_id") 
GROUP BY ...

I haven't tested the queries above, and as said I am a little tired... But the idea should at least be correct :)

[Tim Graham]

Updated test to apply cleanly and verified it's still an issue as of 98bcdfa8bd902addd4b8cf37d039b3597d58a45c.

[Piergiuseppe D'Abbraccio]

I'd like to work on this. I can confirm it still reproduces on main (2d9d619676): with a publisher having three books of 100/200/300 pages,

Publisher.objects.annotate(total=Sum("book__pages")).filter(book__pages__gt=150)

returns total=1200 instead of 600 (and Count("book") returns 6 instead of 3), because filter() adds a second INNER JOIN on book that duplicates the aggregated rows.

Proposed approach: when a filter() call is added to a query that already contains an aggregate and that filter would introduce a new multi-valued (reverse FK / m2m) join, compile the whole filter() call as a subquery (pk IN (SELECT pk ... WHERE <filter>)) instead of a new join. This keeps the documented semantics (a filter() after annotate() doesn't restrict the annotation), conditions within the same filter() call still share a single join, and filter() before annotate() is unaffected.

A rough prototype in Query.add_q() fixes the cases above and the full test suite passes on SQLite. Open questions before I polish it into a PR:

• IN (subquery) vs EXISTS, especially for MySQL performance;
• filters mixing an annotation reference with a multi-valued lookup, e.g. Q(total__gt=5) | Q(book__pages__gt=150);
• whether this should be treated as a bug fix (release note only) given that results change for existing queries.

Feedback on the direction would be very welcome before I open the PR.

[Piergiuseppe D'Abbraccio]

​PR

[Piergiuseppe D'Abbraccio]

Update on the approach: the PR uses EXISTS rather than the pk IN (...) I proposed above.

When every lookup in the filter() call goes through the same relation, the subquery starts from the related model, e.g. EXISTS(SELECT 1 FROM book WHERE rating >= 4 AND publisher_id = publisher.id), so the outer table isn't scanned twice. Otherwise it falls back to EXISTS on the model, correlated on pk.

On PostgreSQL 17 this took the reverse FK case from 69 ms to 24 ms (numbers in the PR). I haven't benchmarked MySQL yet; feedback welcome there.

[Piergiuseppe D'Abbraccio]

Update on the approach: the PR no longer uses EXISTS. Each such filter keeps its join and an equivalent pk IN (SELECT pk ...) subquery, back to what I proposed in comment:5. The compiler uses the subquery when no other clause references the join, so values() and order_by() on the same relation keep today's behaviour. A correlated EXISTS, as in split_exclude(), runs once per outer row on SQLite (0.1 ms to 220 ms on a selective m2m filter); pk IN doesn't, and is as fast as EXISTS on PostgreSQL and MySQL. Updated benchmarks for all three backends are in the PR. #33403 is covered by a test; #15049 (a later annotate() reusing the filter's join) is unchanged.