From O(N³) to O(1): Scaling M2M Validation in Django

Adding a few cities to a delivery zone is instant. Adding 5,000 cities ran over 5,000 database round-trips and regularly timed out the request. The root causes were two common Django patterns that don't scale: validating with per-row .exists() calls, and writing Many-to-Many relations with .add(). Here's the replacement.

---

The Problem

A shipping group links a set of cities to a delivery zone. The model is straightforward:

class ShippingGroup(models.Model):
    name = models.CharField(max_length=255)
    country = models.ForeignKey(Country, on_delete=models.CASCADE)
    cities = models.ManyToManyField(City)

When an admin creates a new shipping group, the endpoint needs to validate that none of the selected cities already belong to a competing group in the same region. The original code did this with a triple-nested loop:

for storefront in storefronts:
    for state in states:
        for city in cities:
            if ShippingGroup.objects.filter(
                company=self.company, storefronts=storefront,
                country=country, states=state, cities=city
            ).exists():
                raise ParseError("A shipping group already covers this city.")

For 5 storefronts, 10 states, and 100 cities, that's 5 × 10 × 100 = 5,000 individual .exists() queries. Just to validate the write hasn't even happened yet. And when the validation passes, the write itself used .add():

shipping_group.cities.add(*city_ids)

Under the hood, .add() first issues a SELECT to find which IDs don't already exist in the junction table, then issues a single INSERT for the remaining rows. Neither step is batched: the deduplication query grows to match the full ID set, and the single large INSERT can lock the table. For 5,000 cities, the SELECT + INSERT plus the 5,000 validation queries made the request timeout long before it finished.

---

The Solution

Three pieces: validate with in-memory set intersection instead of per-row queries, write directly to the .through table in batches, and offload past a threshold to a background task.

Step 1: Validate with set intersection, not per-row .exists()

Instead of checking each city against each existing group one query at a time, fetch all potentially conflicting groups in one query with a Prefetch that hoists the related IDs onto each instance. Then intersect locally:

from django.db.models import Prefetch

def validate_no_overlap(country, storefront_ids, state_ids, city_ids):
    # Fetch every group that might conflict, with all related IDs attached
    existing = ShippingGroup.objects.filter(
        country=country,
    ).prefetch_related(
        Prefetch(
            "storefronts",
            queryset=Storefront.objects.only("id"),
            to_attr="prefetched_storefronts",
        ),
        Prefetch(
            "states",
            queryset=State.objects.only("id"),
            to_attr="prefetched_states",
        ),
        Prefetch(
            "cities",
            queryset=City.objects.only("id"),
            to_attr="prefetched_cities",
        ),
    )

    request_storefronts = set(storefront_ids)
    request_states = set(state_ids)
    request_cities = set(city_ids)

    for group in existing:
        group_sfs = {sf.id for sf in group.prefetched_storefronts}
        group_sts = {st.id for st in group.prefetched_states}
        group_cts = {ct.id for ct in group.prefetched_cities}

        if (
            request_storefronts & group_sfs
            and request_states & group_sts
            and request_cities & group_cts
        ):
            raise ValidationError(
                f"A shipping group already covers this region."
            )

One query to fetch the groups, one query per Prefetch for the related IDs. Typically 3 to 5 queries total regardless of how many storefronts, states, or cities are being checked. The intersection runs entirely in Python, where a set membership check is O(1).

The to_attr on each Prefetch is the key detail: it hoists the filtered queryset onto each ShippingGroup instance as a plain list of objects (prefetched_storefronts, etc.), rather than leaving it as a lazily-evaluated queryset that would re-query on access. The set comprehensions then extract just the IDs for intersection.

Step 2: Write to the .through table directly

.add() looks like a bulk operation, but Django's Many-to-Many manager inserts rows one at a time. For a large set of IDs, the correct approach is to go directly to the auto-generated through model and use bulk_create:

through_model = ShippingGroup.cities.through
batch_size = 500

for i in range(0, len(city_ids), batch_size):
    chunk = city_ids[i : i + batch_size]

    # Verify these IDs actually exist in the database before inserting
    valid_ids = set(
        City.objects.filter(id__in=chunk, country=country_id)
        .values_list("id", flat=True)
    )

    objs = [
        through_model(shippinggroup_id=group_id, city_id=cid)
        for cid in valid_ids
    ]
    through_model.objects.bulk_create(objs, ignore_conflicts=True)

Three things happening here:

• Batching in chunks of 500 keeps the transaction size bounded and prevents a single massive INSERT from locking the table for too long.
• ignore_conflicts=True skips rows that already exist: no duplicate-key error, no need to pre-filter existing relations. If a city is already assigned to this group, the insert is silently ignored.
• Pre-validating IDs against the database (City.objects.filter(id__in=chunk)) ensures you're not inserting garbage IDs that would fail a foreign key constraint. It's one query per batch, not one per row.

For 5,000 cities, that's 10 batches × 2 queries each = 20 queries instead of 5,000 inserts.

Step 3: Offload past a threshold to a background task

Even with batched bulk writes, processing 10,000+ rows synchronously will make the HTTP request hang. At some size, the operation belongs in a queue:

THRESHOLD = 500

def create_shipping_group(data):
    group = ShippingGroup.objects.create(name=data["name"], country=country)

    city_count = len(data["city_ids"])
    if city_count > THRESHOLD:
        assign_cities_to_group.delay(
            city_ids=data["city_ids"],
            country_id=country.id,
            group_id=group.id,
        )
    else:
        # Small enough — do it inline. At this count the SELECT + INSERT
        # in .add() is fast enough and keeps the code simpler.
        cities = City.objects.filter(id__in=data["city_ids"], country=country)
        group.cities.add(*cities.values_list("id", flat=True))

    return group

Below 500 cities: synchronous .add() is fine. Above 500: a Celery task takes over, the request returns immediately with the group created but cities still being assigned in the background. The task uses the same batched bulk_create path from Step 2.

Threshold choice matters: 500 was picked because it's well under a typical request timeout even with a slow database, but it's a number you should tune against your own infrastructure.

---

Why This Works

Validation is constant-time relative to the input size. The Prefetch queries are bounded by the number of existing groups in the country, not the number of cities being validated. Set intersection is O(n) in Python and negligible at typical group counts.

.through + bulk_create skips the deduplication penalty and avoids table locks. Under the hood, .add() runs a large SELECT to find which IDs are already in the table, then issues one giant INSERT for the rest — both unbounded operations. With ignore_conflicts=True, bulk_create skips the deduplication step entirely, and batching keeps the transactions small enough to avoid locking.

ignore_conflicts means idempotent writes. You can retry the Celery task without worrying about partial progress from a previous attempt. Rows that were already inserted in a prior batch are silently skipped on retry.

The threshold keeps the API responsive. Synchronous for small inputs (the common case), asynchronous for large ones without changing the interface. The caller always gets the same response shape. The group exists, cities are either assigned or being assigned.

---

Design Decision: The .through Model Changes What You're Responsible For

Using through_model.objects.bulk_create() instead of group.cities.add() means you're bypassing Django's Many-to-Many manager entirely. That's the point: the manager isn't designed for batch writes. But it also means you lose two things the manager normally gives you for free:

• Signal dispatch. .add() fires m2m_changed signals that might be expected by other parts of the system (audit logs, cache invalidation). Writing to the through table directly does not. If those signals matter, you need to fire them manually or postpone logging to a post-write step.
• Validation. The manager checks that the related object exists before inserting. Step 2 compensates with an explicit City.objects.filter(id__in=chunk) pre-check. If you skip that check and insert a non-existent ID, you get a ForeignKeyViolation in Postgres instead of a clean Django error.

Neither of these is a bad trade. Just a trade you should know you're making.

---

The Result

The validation step went from 5,000 queries — one per city-state-storefront combination — to about 5 regardless of input size. The write went from a single large INSERT with no batching to 10 batched chunks of 500 with idempotent conflict handling, or a background task for counts above the threshold.

The pattern (validate with set intersection, write to .through in batches, offload past a threshold) applies to any Django model with a large Many-to-Many field: tags, categories, user teams, regional assignments, or anywhere else you're adding hundreds or thousands of rows to a junction table.

How are you handling large Many-to-Many writes in your Django apps? Are you going through the through table directly, or have you found a different approach? Drop it in the comments.

¡Hasta luego!