An import job timed out at 100k rows because of one `in` check on a list

The import feature lets a business upload a CSV of customers. For months it handled files of a few thousand rows without anyone noticing it. Then a new customer uploaded their full CRM export, 112,000 rows, and the job died:

[2026-10-14 09:41:07] worker.ERROR: Job imports.customers (id=55102) exceeded timeout of 3600s
[2026-10-14 09:41:07] worker.WARNING: killed pid=8121 rss=410MB rows_processed=61840

An hour, and barely past halfway. Memory was fine, CPU on that worker was pinned at 100% for the entire run, and the database showed almost no load. Whatever was slow, it was pure Python.

A first measurement

We generated synthetic files of different sizes and timed the job locally:

Each time the input doubled, the run time roughly quadrupled. That pattern is the signature of quadratic work: O(n²). Something was doing work proportional to the number of rows, once per row.

Finding the line

cProfile pointed straight at it:

python -m cProfile -s cumulative -m imports.run --file customers_20k.csv | head -20

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.020    0.020   31.402   31.402 run.py:1(<module>)
        1   30.912   30.912   31.310   31.310 customers.py:42(import_rows)
    20000    0.211    0.000    0.211    0.000 customers.py:88(normalise_email)
    ...

Nearly all the time was tottime inside import_rows itself, not in anything it called. That means the cost was in plain operations on that function's own lines. The function:

def import_rows(rows):
    seen_emails = []
    existing = [c.email for c in Customer.objects.only("email")]
    created, skipped = [], []

    for row in rows:
        email = normalise_email(row["email"])
        if email in existing or email in seen_emails:
            skipped.append(row)
            continue
        seen_emails.append(email)
        created.append(Customer(email=email, name=row["name"]))

    Customer.objects.bulk_create(created, batch_size=1000)
    return len(created), len(skipped)

Two lists, existing and seen_emails, and an in check against each on every row.

Why in on a list is slow

x in some_list checks elements one by one until it finds a match or reaches the end. For a list of length m, that is up to m comparisons. It is O(m), and for values that are not in the list (most rows in an import) it always scans everything.

In this loop:

• existing held every customer already in the account. For the new customer it was empty, but for an established account it could be tens of thousands.
• seen_emails grew by one per row, so on row k it held about k entries.

Summing the second check over n rows gives roughly 1 + 2 + ... + n, which is about n²/2 comparisons. For 112,000 rows that is over six billion string comparisons, each a Python-level operation. No wonder it needed hours.

Why sets and dicts are fast

A set or dict stores items in a hash table. Checking membership computes the hash of the value and looks in one bucket. On average that is O(1), independent of the collection's size. The Python documentation's time complexity table lists x in s as O(n) for lists and O(1) average for sets and dicts.

The fix is literally changing two brackets. That is why this bug is so common: the slow and fast versions look almost the same, and with small test data they run at the same speed.

Environment

1. Use sets for membership

def import_rows(rows):
    existing = set(Customer.objects.values_list("email", flat=True))
    seen = set()
    created, skipped = [], []

    for row in rows:
        email = normalise_email(row["email"])
        if email in existing or email in seen:
            skipped.append(row)
            continue
        seen.add(email)
        created.append(Customer(email=email, name=row["name"]))

    Customer.objects.bulk_create(created, batch_size=1000)
    return len(created), len(skipped)

Building existing is one O(m) pass. Each loop iteration is now O(1) on average. The whole function is O(n + m) instead of O(n × m + n²).

We also switched from only("email") to values_list(..., flat=True), which avoids building a model instance for every existing customer. That change is small next to the set, but it cut memory too.

2. When you need the item, not just "is it there", use a dict

Later the same job learned to update existing customers instead of skipping them. That needs the record, not a yes/no. A dict keyed by email keeps lookups O(1):

existing = {c.email: c for c in Customer.objects.filter(account=account)}

for row in rows:
    email = normalise_email(row["email"])
    if (customer := existing.get(email)) is not None:
        customer.name = row["name"]
        to_update.append(customer)
    else:
        ...

3. Let the database do it when the data is too big for memory

For accounts with millions of customers, loading every email into a set is not ideal either. For those we use a unique index on (account_id, email) and bulk_create(..., ignore_conflicts=True), so the database does the duplicate check with an index lookup. The in-memory set remains for duplicates inside the file itself.

1. Micro-benchmark with timeit. We measured the membership check alone to confirm the theory before looking at the full job:

import timeit

setup = "data = [f'user{i}@example.com' for i in range(100_000)]; s = set(data); x = 'missing@example.com'"
print(timeit.timeit("x in data", setup=setup, number=1_000))
print(timeit.timeit("x in s", setup=setup, number=1_000))

1.21
0.000031

A thousand lookups for a missing value: about 1.2 seconds on the list, about 31 microseconds on the set, on one laptop. The exact numbers depend on the machine; the ratio is the point.

2. The same scaling table, after the fix:

Doubling the rows now roughly doubles the time. Linear, as expected.

3. A test that guards the complexity, not a wall-clock number. Timing assertions in CI are flaky. We instead assert that run time grows roughly linearly, using a large ratio of headroom:

def test_import_scales_linearly(make_rows):
    small = timed(lambda: import_rows(make_rows(5_000)))
    large = timed(lambda: import_rows(make_rows(40_000)))
    # 8x input. Linear would be ~8x time; quadratic would be ~64x.
    assert large / small < 20

On the old code the ratio was about 60. On the new code it is about 8. The threshold of 20 is loose enough to survive a noisy CI runner and tight enough to catch a return to quadratic behaviour.

4. Lint for the pattern. We added a review checklist item: "membership checks inside loops use a set or dict". Linters such as Ruff flag some related patterns, like PERF401 for manual list building, but none reliably catch in list inside a loop, so it stays a review rule.

5. Security implications. A quadratic path on user-supplied input is also a denial-of-service risk: anyone allowed to upload a file could tie up a worker for hours. Beyond the fix, we added a row limit per upload with a clear error message, and the worker timeout now marks the import as failed and notifies the user instead of retrying it three more times.

Takeaways

• x in list scans the whole list. Inside a loop, it makes the loop O(n²).
• Use a set for "have I seen this", a dict when you need the matching item.
• Time doubling-sized inputs. Four times slower per doubling means quadratic.
• Test scaling ratios, not absolute times, so the check is stable in CI.

References: Python sets, timeit module, The Python profilers, Django bulk_create.