Selecting Things in All of the Nominated Categories
Tags: django, python, sql, webdev
Published: 2023-05-11 08:44:00

I came across a problem this week, that I was sure, had a canonical solution (i.e. standard and documented). But no, not that I could find. So yet again a process of reading, searching, testing, trying, talking (on [Stack Overflow](https://stackoverflow.com/), with [ChatGPT](https://chat.openai.com/)) and resulting notes and even a [sandbox](https://codesandbox.io) (demo). 

## Problem Statement

**The context:** A database (nominally behind a website) containing Things, and those Things are in Categories. 

**The environment:** [Django](https://www.djangoproject.com/) as a web framework and Python as a backend, but raw SQL will do if needed.

In the Django context the simplest scenario is:

```python
from django.db import models

class Thing(models.Model):
    name = models.CharField('Name of the Thing', max_length=100)

class Category(models.Model):
    name = models.CharField('Name of the Category', max_length=100)
    things = models.ManyToManyField(Thing,
                                    verbose_name='Things',
                                    related_name='categories')
```
Which of course is backed by three tables in a (nominally, [Postgresql](https://www.postgresql.org/), though I did trials in [SQLite](https://www.sqlite.org)) database (in pro forma - Django will actually use slightly different names depending on context for such tables):

- `thing` which has one thing per row
- `category` - which has one category per row
- `thing_category` - which has a (thing id, category id) row for each relationship between things and categories.

You might prefer to think of things and categories in some other way more familiar to you (anything at all, with a many-to-many relationship suffices), perhaps students and courses, papers and authors, people and interests, food and its properties ... whatever really, I have several applications so asked this question in the general terms of things and categories.

**The task:** Given a list of categories, say [1, 4, 7, 23], write one query which returns all the things that are in all of these categories (but not limited to them, i.e. can be in other categories as well).

In turns out that the partner problem, finding all the things that are in any of those categories is easy. In Django:

```python
things = Thing.objects.filter(categories__in=[1, 4, 7, 23])
```

{% collapsible although... %} this returns duplicate things, a wonderfully bizarre feature of Django, and to prevent that one needs to add `.distinct()` {% endcollapsible %}

This, in effect, is an ANY/OR result, returning all things that are in any of the listed categories, alternately, all things that are in category 1 **or** category 4 **or** category 7 **or** category 23.

What I need is an ALL/AND result, returning all things that in _all_ of the listed categories, alternately, all things that are category 1 **and** category 4 **and** category 7 **and** category 23.

## Solutions

**TLDR:** {% spoiler solution %} 
```python
cats = [1, 4, 7, 23]
things = Thing.objects.annotate(
            cat_count=Count('id', filter=Q(categories__in=cats))
         ).filter(cat_count=len(cats))
```
 {% endspoiler %}

### Field Lookups 
![Field Look Up](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uh5t10v1o27ocexk4gjp.jpg)
`categories__in` is what Django calls a [field lookup](https://docs.djangoproject.com/en/4.2/topics/db/queries/#field-lookups). They are very handy and the first port-of-call was to try and find a field lookup that does this. Alas none was to be found. The `__in` lookup is used to perform an ANY/OR match. There is no equivalent for ALL/AND lookups like say `__in_all` - alas. It's possible to write [custom lookups](https://docs.djangoproject.com/en/4.2/howto/custom-lookups/) and I have done that before, and was tempted here, but the SQL solution is non-trivial to implement in a custom lookup (can be done, but the method is poorly documented and would need more research).

Turns out the SQL should I (or someone else) choose to build a lookup like `__in_all` can work on the joining table alone, so with the tables and example above:

```SQL
SELECT thing_id
FROM thing_category
WHERE category_id in (1, 4, 7, 23)
GROUP BY thing_id
HAVING Count(*) = 4;
```

This works well because the WHERE clause excludes all other categories, so only those in the list will be counted by the Count(*) function. To wit, this fetches all the relations that are (at least) in the listed categories (they may be in more). Precisely what I am targeting. Of course, this assumes there are no duplicate rows in the table (a safe assumption with Django joining tables).

Interestingly, the `__in` lookup which returns the ANY/OR set of things can be written in similar SQL as:

```SQL
SELECT thing_id
FROM thing_category
WHERE category_id in (1, 4, 7, 23)
GROUP BY thing_id
HAVING Count(*) >= 1;
```

In lieu of a custom lookup or [raw SQL](https://docs.djangoproject.com/en/4.2/topics/db/sql/) query though, a better Django solution is preferred.

### Filtered Counts 
![Filters](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s9zb6zaylod6wfxa7ptx.png)
Django filters are often a challenge to write. It is both a wonderful abstraction of the underlying database and, at the same time, a very different approach and way of thinking. There's always this small challenge with Django, if you have SQL you know works, translating that to Django filter.

It turns out the Django [Count](https://docs.djangoproject.com/en/4.2/ref/models/querysets/#id9) aggregate function has a (poorly documented) filter argument.

This:

```python
things = Thing.objects.annotate(cat_count=Count('categories'))
```

is fairly standard Django (that many will recognise), which adds a count of the categories as an attribute named `cat_count` to each of returned `things`.

But we don't want a count of the categories every thing is in, we want a count of the categories from our list that each thing is in. It turns out Django supports that through the rather poorly documented filter addition to the Count aggregate.

So we can limit the count to that list of desire categories using a Count filter, and that does use a field lookup! As in:

```python
cats = [1, 4, 7, 23]
things = Thing.objects.annotate(cat_count=Count('categories', filter=Q(categories__in=cats)))
```

And now we have all things annotated with a count of categories from 0 to 4 (the length of cats) as the Count was only on a filtered set of them. 

To get all things that are in ALL categories we can filter for those that have 4 reported, so:

```python
cats = [1, 4, 7, 23]
things = Thing.objects.annotate(cat_count=Count('categories', filter=Q(categories__in=cats)))
things = things.filter(cat_count=len(cats))
```

### Revisiting ANY/OR (a digression)

Ironically, we of course replicate what the `__in` lookup does using this annotation too, so that this:

```python
cats = [1, 4, 7, 23]
things = Thing.objects.filter(categories__in=cats)
```

is _almost_ the same (as in, produces the same results as):

```python
cats = [1, 4, 7, 23]
things = Thing.objects.annotate(cat_count=Count('categories', filter=Q(categories__in=cats)))
things = things.filter(cat_count__gte=1)
```

Which uses the `__gte` field lookup. Alas, the first cut, duplicates things, Django does a lazy join and then filter on the join table, so things appear once per matching category. Doh! Like that would be of use to anyone, ever, in any context? So We have to help Django do the sensible thing and explicitly request distinct things:

```python
cats = [1, 4, 7, 23]
things = Thing.objects.filter(categories__in=cats).distinct()
```

And now the two queries return near identical results (the ordering can be different unless we specify it). 

### Drilling down to SQL
![Drill](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wt8kuav210lygb0juu51.jpg)
We can of course ask Django for the SQL it generates (turns out that's not trivial but that is a digression for another article). And it's interesting to compare the SQL that the `__in` lookup generates compared with our annotating approach.

Here's what an __in lookup generates (in pro forma):

```SQL
SELECT DISTINCT thing.id, thing.name
FROM thing
INNER JOIN category_things ON (thing.id = category_things.thing_id)
WHERE category_things.category_id IN (1, 4, 7, 23)
```

and here's what our annotation approach produces (in pro forma):

```SQL
SELECT 
  thing.id, 
  thing.name, 
  COUNT(category_things.category_id) 
    FILTER (WHERE category_things.category_id IN (1, 4, 7, 23)) 
      AS "cat_count"
FROM thing
LEFT OUTER JOIN 
  category_things ON (thing.id = category_things.thing_id)
GROUP BY 
  thing.id, thing.name
HAVING 
  COUNT(category_things.category_id) 
  FILTER (WHERE (category_things.category_id IN (1, 4, 7, 23))) 
  >= 1
```

Django's SQL clearly does not adhere to [DRY](https://docs.djangoproject.com/en/4.2/misc/design-philosophies/#don-t-repeat-yourself-dry), given it reproduces `COUNT(category_things.category_id) FILTER (WHERE category_things.category_id IN (1, 4, 7, 23))` in two places while this is also valid (and tested, it works):

```SQL
SELECT 
  thing.id, 
  thing.name, 
  COUNT(category_things.category_id) 
    FILTER (WHERE category_things.category_id IN (1, 4, 7, 23)) 
      AS "cat_count"
FROM thing
LEFT OUTER JOIN 
  category_things ON (thing.id = category_things.thing_id)
GROUP BY 
  thing.id, thing.name
HAVING 
  cat_count >= 1
```
{% collapsible caveat %} _this may be an artefact of the SQL drill down, or generation, which as I said is not trivial in Django, but the subject for another article, point here being is we are not necessarily seeing here the SQL Django actually sends to the database engine - though in all honesty it pretty likely is_ {% endcollapsible %}

For completeness of course the SQL for the ALL/AND request that I was pursuing at outset becomes:

```SQL
SELECT 
  thing.id, 
  thing.name, 
  COUNT(category_things.category_id) 
    FILTER (WHERE category_things.category_id IN (1, 4, 7, 23)) 
      AS "cat_count"
FROM thing
LEFT OUTER JOIN 
  category_things ON (thing.id = category_things.thing_id)
GROUP BY 
  thing.id, thing.name
HAVING 
  cat_count = 4
```

## The Research Effort
![Researcher](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ps65nv3qqhr4s9uijqba.png)
For the record, the trail of research that went into the notes, that morphed into this article, on realisation that esoteric snippets of acquired knowledge are worth recording and sharing are:

- [Stack Overflow: Django](https://stackoverflow.com/questions/76193289/django-many2many-query-to-find-all-things-in-a-group-of-categories/76193754?noredirect=1#comment134395967_76193754)
- [Stack Overflow: SQL](https://stackoverflow.com/questions/76208347/select-all-things-in-a-given-list-of-categories-or-more-categories/76210455#76210455)
- [CodeSandbox: Experiments with simple models](https://codesandbox.io/p/sandbox/django-m2m-test-cizmud)