Narrowing down possible combinations in a many-to-many relationship

Question

Assumptions

I have the following 3 database tables:

Foobar:

• id
• name

Tag:

• id
• name

Foobar_Tags:

• id
• foobar_id
• tag_id

There are many Foobar's and they are randomly tagged with one or more tags.

Problem

I receive a list of tags - e.g. ('tag1', 'tag2', 'tag3')

Now I want get a list of tags that are associated with foobar's where the foobar's are also associated with the received list of tags.

To visualize this more:

• foobar_1 has tags 'tag1', 'tag2'
• foobar_2 has tags 'tag2', 'tag3'
• requested tags: 'tag2'
  • result: 'tag1', 'tag3'
• requested tags: 'tag1'
  • result: 'tag2'
• requested tags: 'tag3'
  • result: 'tag2'
• requested tags: 'tag1', 'tag2'
  • result: None

Current approach

I'm using Django and my current approach looks like this (foobar to tags is a simple m2m field):

if tag_list:
    available_tags = Tag.objects
    for tag in tag_list:
        available_tags = available_tags.filter(foobar__tags__tag=tag).exclude(tag=tag)
    available_tags = available_tags.distinct()          
else:
    available_tags = Tag.objects.all()

available_tags = available_tags.annotate(num_foobars=Count('foobar', distinct=True)) \
                                                  .order_by('-num_foobars') \
                                                  .exclude(num_foobars=0)

I get the results I want but I'm not sure I'm using the correct approach here. The resulting SQL contains already 8 INNER JOINS when just filtering for 2 tags and grows immensely per added tag making it very slow.

Example SQL

This is the generated SQL when looking up ('tag1', 'tag2')

SELECT DISTINCT 
    "tag"."id", 
    "tag"."name", 
    COUNT(DISTINCT "foobar_tags"."foobar_id") AS "num_foobars" 
FROM "tag" 
INNER JOIN "foobar_tags" ON ( "tag"."id" = "foobar_tags"."tag_id" ) 
INNER JOIN "foobar" ON ( "foobar_tags"."foobar_id" = "foobar"."id" ) 
INNER JOIN "foobar_tags" T4 ON ( "foobar"."id" = T4."foobar_id" ) 
INNER JOIN "tag" T5 ON ( T4."tag_id" = T5."id" ) 
INNER JOIN "foobar_tags" T6 ON ( "tag"."id" = T6."tag_id" ) 
INNER JOIN "foobar" T7 ON ( T6."foobar_id" = T7."id" ) 
INNER JOIN "foobar_tags" T8 ON ( T7."id" = T8."foobar_id" ) 
INNER JOIN "tag" T9 ON ( T8."tag_id" = T9."id" ) 
WHERE (T5."name" = 'tag1' 
    AND NOT ("tag"."name" = 'tag1') 
    AND T9."name" = 'tag2' 
    AND NOT ("tag"."name" = 'tag2')) 
GROUP BY "tag"."id", "tag"."name" 
HAVING NOT (COUNT(DISTINCT "foobar_tags"."foobar_id") = 0) 
ORDER BY "num_foobars" DESC

Questions

• Can the query be optimized (either with the Django ORM or raw SQL) ?
• Is there are name for this problem (for further search) ?

Answer 1

There is no need for a join for every additional tag. Suppose the query contains tag1 and tag2, here is the sql for it:

select distinct tags.id, tags.name from tags inner join foobar_tags 
   on tags.id = foobar_tags.tagId 
   where fooId in 
      (select fooId from tags t inner join foobar_tags ft on t.id = ft.tagId 
          where 
             (select count(distinct name) from foobar_tags inner join tags 
               on tags.id = foobar_tags.tagId
               where fooId = ft.fooId and tags.name in('tag2','tag1')--tags query
             ) = 2 --number of tags in the query
    )
    AND
    name not in ('tag2','tag1')--tags query

we find all foos that have all tags by counting their associated tags which are belong to our query tags.This count should be equal to number of query tags. Then we return tags of the matched foos except the tags that belong to query tags.

You can generate this query for any number of tags and the number of joins will be unchanged.

Here is a fiddle for it.