Optimized nested pagination is broken for m2m fields

[SupImDos]

Describe the Bug

Nested pagination through m2m fields is broken with the optimizer enabled. This appears to be because using .prefetch_related() with a QuerySet annotated with a Window function where partition_by is an m2m field causes an extra join and duplicate results.

Reproducible Example

See a minimal reproducible example here:

• Branch: mre/nested-pagination-m2m
• Commit: 5469f26

In the unit test above, the expected result of the query is:

{
  "tagConn": {
    "edges": [
      {
        "node": {
          "name": "Tag 1",
          "issues": {
            "edges": [
              {"node": {"name": "Issue 1"}},
              {"node": {"name": "Issue 2"}}
            ]
          }
        }
      },
      {
        "node": {
          "name": "Tag 2",
          "issues": {
            "edges": [
              {"node": {"name": "Issue 2"}},
              {"node": {"name": "Issue 3"}}
            ]
          }
        }
      }
    ]
  }
}

However, the test fails, and the actual result of the query is:

{
  "tagConn": {
    "edges": [
      {
        "node": {
          "name": "Tag 1",
          "issues": {
            "edges": [
              {"node": {"name": "Issue 1"}},
              {"node": {"name": "Issue 2"}},
              {"node": {"name": "Issue 2"}}  // Duplicate!
            ]
          }
        }
      },
      {
        "node": {
          "name": "Tag 2",
          "issues": {
            "edges": [
              {"node": {"name": "Issue 2"}},
              {"node": {"name": "Issue 2"}},  // Duplicate!
              {"node": {"name": "Issue 3"}}
            ]
          }
        }
      }
    ]
  }
}

System Information

• Operating system: MacoS
• Strawberry version: 0.247.0
• Strawberry Django version: 0.49.1

Additional Context

It appears that this is caused by the implementation of apply_window_pagination().

As suggested above, when you annotate a .prefetch_related() QuerySet with a Window function and refer back to the other side of the m2m, you add another join - causing duplicate results. When Django introduced the ability to prefetch with sliced querysets (which Strawberry-Django isn't directly using) they had to do a bunch of hacks to combine calls to filter together (see QuerySet._next_is_sticky() and _filter_prefetch_queryset()).

To demonstrate the difference directly with the Django ORM see: a6f4e31.

In the unit test above, Strawberry-Django produces the following SQL query for the paginated prefetch:

SELECT *
FROM
  (SELECT ("projects_issue_tags"."tag_id") AS "_prefetch_related_val_tag_id",
          "projects_issue"."name" AS "col1",
          "projects_issue"."id" AS "col2",
          ROW_NUMBER() OVER (PARTITION BY "projects_issue_tags"."tag_id"
                             ORDER BY "projects_issue"."id" ASC) AS "_strawberry_row_number",
          COUNT(1) OVER (PARTITION BY "projects_issue_tags"."tag_id") AS "_strawberry_total_count"
   FROM "projects_issue"
   LEFT OUTER JOIN "projects_issue_tags" ON ("projects_issue"."id" = "projects_issue_tags"."issue_id")
   INNER JOIN "projects_issue_tags" T4 ON ("projects_issue"."id" = T4."issue_id")
   WHERE T4."tag_id" IN (1,
                         2)
   ORDER BY "projects_issue"."id" ASC) "qualify"
WHERE "_strawberry_row_number" <= 2
ORDER BY "col2" ASC

Whereas Django produces this SQL query for the paginated prefetch:

SELECT "_prefetch_related_val_tag_id",
       "col1",
       "col2"
FROM
  (SELECT *
   FROM
     (SELECT ("projects_issue_tags"."tag_id") AS "_prefetch_related_val_tag_id",
             "projects_issue"."name" AS "col1",
             "projects_issue"."id" AS "col2",
             ROW_NUMBER() OVER (PARTITION BY "projects_issue_tags"."tag_id"
                                ORDER BY "projects_issue"."id" ASC) AS "qual0"
      FROM "projects_issue"
      INNER JOIN "projects_issue_tags" ON ("projects_issue"."id" = "projects_issue_tags"."issue_id")
      WHERE "projects_issue_tags"."tag_id" IN (1,
                                               2)
      ORDER BY "projects_issue"."id" ASC) "qualify"
   WHERE ("qual0" > 0
          AND "qual0" <= 2)) "qualify_mask"
ORDER BY "col2" ASC

Note the extra LEFT OUTER JOIN which causes the issue.

Potential Solution

As noted in the apply_window_pagination() docstring, Django 4.2+ actually supports sliced QuerySets in .prefetch_related() now.

The solution here may be to actually use Django's inbuilt support for .prefetch_related() QuerySet slicing. However, this means we can't annotate _strawberry_total_count onto the nodes anymore. It is likely that we would need to refactor that functionality onto the parent records, maybe using a subquery count and OuterRef?

Upvote & Fund

• We're using Polar.sh so you can upvote and help fund this issue.
• We receive the funding once the issue is completed & confirmed by you.
• Thank you in advance for helping prioritize & fund our backlog.

[SupImDos]

For reference, our understanding is that (at a high level) the current nested pagination looks like this:

tag_queryset.prefetch_related(
    Prefetch(
        "issues",
        queryset=issue_queryset.annotate(
            _strawberry_row_number=Window(
                RowNumber(),
                partition_by=["tags"],
                order_by=[...],
            ),
            _strawberry_total_count=Window(
                Count(1),
                partition_by=["tags"],
            ),
        ).filter(
            _strawberry_row_number__gt=5,
            _strawberry_row_number__lte=10,
        ),
    )
)

But to work correctly, it could be updated to something like this:

tag_queryset.prefetch_related(
    Prefetch(
        "issues",
        queryset=issue_queryset[5:10],
        to_attr="_strawberry_optimized_issues",
    )
).annotate(
    _strawberry_total_count_issues=Subquery(
        issue_queryset.filter(tags=OuterRef("pk"))
        .values("tags")
        .annotate(total_count=Count("pk"))
        .values("total_count"),
    )
)

The main complexity here is how to get Strawberry / Strawberry-Django to:

1. Recognise that a tag's issues will actually be on the _strawberry_optimized_issues attribute (instead of issues)
2. Recognise that a tag's issue count will actually be on the _strawberry_total_count_issues attribute (instead of annotated on its issues as _strawberry_total_count)

The other complexity is how to calculate things like cursor / start_cursor / end_cursor / has_previous_page / has_next_page - but I think conceptually it should still possible.

[bellini666]

Hey @SupImDos ,

I was doing some tests on this and discovered that the issue is with Django.

If I do this in your test_nested_pagination_m2m for example right after creating/assigning the issues/tags:

Tag.objects.prefetch_related(
    Prefetch("issues", queryset=Issue.objects.all().annotate(foo=F("tags")))
)

I get duplicated issues as well. This is the SQL generated:

SELECT ("projects_issue_tags"."tag_id") AS "_prefetch_related_val_tag_id",
       "projects_issue"."name",
       "projects_issue"."id",
       "projects_issue"."kind",
       "projects_issue"."priority",
       "projects_issue"."milestone_id",
       "projects_issue_tags"."tag_id" AS "foo"
FROM "projects_issue"
LEFT OUTER JOIN "projects_issue_tags" ON ("projects_issue"."id" = "projects_issue_tags"."issue_id")
INNER JOIN "projects_issue_tags" T4 ON ("projects_issue"."id" = T4."issue_id")
WHERE T4."tag_id" IN (3,
                      4)
ORDER BY "projects_issue"."id" ASC

The only thing I did here was to annotate "projects_issue_tags"."tag_id", which is also annotated by the prefetcher (see the first selected column), but Django is forcing a new join for that instead of using the same one, which it should.

We can try to find a related issue for this or report it to django.

In the meantime, I would like to find a way to workaround this without having to rewrite this, because as you already pointed out, the challenge will probably be even greater.

I was trying to play with the QuerySet.query object from the Prefetch object to see if I can force the join to be reused, but so far I got nothing. Will continue trying

[bellini666]

Opened this issue on the Django bug tracker: https://code.djangoproject.com/ticket/36035

[Eraldo]

Opened this issue on the Django bug tracker: https://code.djangoproject.com/ticket/36035

Thank you for putting in the effort and figuring out what was going on there. 🙏

[bellini666]

Btw, it seems that we might get a bug fix soon: https://code.djangoproject.com/ticket/36035#comment:1

I tested the patch they mentioned and it indeed fixes the issue. I'll try to workaround some solution for strawberry-django in the meantime

[bellini666]

The only workaround I found was to monkey patch django =P

Although I prefer to avoid doing that, this seems safe as the monkey patched functions share the same code in all supported versions (4.2, 5.0 and 5.1) and we are not going to apply this for 5.2 which is going to contain the fix.

The PR is opened here: #681