Slow queryset building when using __in lookup with a large list of values against a related field

[Adam Sołtysik]

When we call something like queryset.filter(id__in=large_list), the query runs several times slower than the same query executed manually, even if there are no rows returned.

Example (function added in tests/basic/tests.py, testing on Postgres):

    def test_id_in(self):
        import time

        values = list(range(-100000, 0))

        t = time.perf_counter()
        print(Article.objects.filter(id__in=values))
        print(f'{(time.perf_counter() - t):.3f} s')

        t = time.perf_counter()
        with connection.cursor() as cursor:
            cursor.execute('SELECT * FROM basic_article WHERE id = ANY(%s)', [values])
            print(cursor.fetchall())
        print(f'{(time.perf_counter() - t):.3f} s')

Results (python runtests.py basic -k id_in):

<QuerySet []>
0.584 s
[]
0.176 s

Note that I'm using ANY as ​recommended by psycopg, but the same happens with a manually constructed query with IN.

Another situation when this slowdown appears is removing a large number of items from a M2M relation.

[Jacob Walls]

Thanks for the bench. I think we should tentatively accept this for investigation. I suggested opening a ticket for the issue of large collections of values when looking at another profile, but it might have gotten lost in the shuffle.. (My concern at the time with the ​PR was that we weren't optimizing the right thing, but I'm glad to look at a new approach.)

[Simon Charette]

Could this be a duplicate of #37211?

[Adam Sołtysik]

Indeed we're talking about the same thing, and performance is much better with that PR applied. Nice to see it being worked on.

However, the manually executed query is still noticably faster. In my benchmark, we get from 0.584 s to 0.235 s, which is ~1.3x slower than the 0.176 s.

That could be considered reasonable as an ORM abstraction cost, but a bigger slowdown remains with M2M, which I also mentioned. Here's a benchmark (added in tests/many_to_many/tests.py):

    def test_m2m_remove(self):
        import time

        values = list(range(-100000, 0))
        article = Article.objects.create()

        t = time.perf_counter()
        article.publications.remove(*values)
        # or (same time):
        # Article.publications.through.objects.filter(article=article, publication__in=values).delete()
        print(f'{(time.perf_counter() - t):.3f} s')

        t = time.perf_counter()
        with connection.cursor() as cursor:
            cursor.execute('''
                DELETE FROM many_to_many_article_publications
                WHERE article_id = %s AND publication_id = ANY(%s)
            ''', [article.id, values])
        print(f'{(time.perf_counter() - t):.3f} s')

Best results:

• 0.638 s for ORM on main
• 0.314 s for ORM with the PR
• 0.143 s for cursor.execute

So ~2.2x slower here, if I didn't miss anything.

On one hand, this discussion could be potentially continued in ​https://github.com/django/django/pull/21605, but on the other hand, this could be a different matter than the compilation to ANY, so maybe it's worth keeping this issue separate?

[Simon Charette]

So ~2.2x slower here, if I didn't miss anything.

There could be other factors at play but without profiling the execution it's hard to tell what's to blame. Since you already have a setup for all branches would you mind providing some profiling details against the MR for #37211 and share them here an ​on the forum thread? I suspect ​the creation of the OrderedSet to exclude None plays a role in the slowdown.

[Simon Charette]

There's nothing to assign the ticket to you for Vishy, can't you see there is an active discussion on what should be done next between Adam and I?

[Vishy]

My bad. I assumed there's work to be done despite ​#21605, since you mentioned profiling to find other performance related factors.

[Adam Sołtysik]

Since you already have a setup for all branches would you mind providing some profiling details against the MR for #37211 and share them here an ​on the forum thread?

I found that it's creating the queryset, qs = qs.filter(publication__in=values), that takes half of the whole remove operation's time. And when we change the lookup to id__in, it's much faster for some reason (but still responsible for that 1.3x slowdown in the first benchmark).

I pinned it down to build_filter and these 2 calls inside (the second ones gets 3-4x slower with the publication__in lookup):

value = self.resolve_lookup_value(value, can_reuse, allow_joins, summarize)

condition = self.build_lookup(lookups, col, value)

But the rabbit hole gets deeper, and I currently don't have the time to proceed from here - if anyone wants to profile it further and/or prepare a fix, feel free. At least now we know that it's a different matter than #37211.

I will also add a comment on the forum.

[Simon Charette]

Thank you for providing more details.

The main difference between filter(id__in=values) and filter(related_field__in=values) is that the former resolves to django.db.models.lookups.In and the latter to django.db.models.fields.related_lookups.RelatedIn.

RelatedIn.get_prep_lookup does a significant amount of transformation on a direct/literal right-hand-side mainly

1. ​It calls the get_normalized_value ​function which results in two isinstance checks and ​an unnecessary tuple creation (as the first member is always taken) for each member of values.
2. It ​then calls target_field.get_prep_value for each member values but that's something lookups.In via FieldGetDbPrepValueIterableMixin which means we're doing it twice in this case since we don't mark self.prepare_rhs = False`.