Many-to-many tag filter query with a junction table get slower with more tags. Can it be faster? Part 1

I have this query to find some videos containing all given tags. Here with tags 1,9,27,13,67 as an example.

SELECT *
FROM video v
WHERE v.id IN (
    SELECT tr1.vid as video_id FROM (SELECT video_id vid FROM tag_rel WHERE tag_id=1) tr1
    INNER JOIN (SELECT video_id vid FROM tag_rel WHERE tag_id=9) tr2 USING (vid)
    INNER JOIN (SELECT video_id vid FROM tag_rel WHERE tag_id=27) tr3 USING (vid)
    INNER JOIN (SELECT video_id vid FROM tag_rel WHERE tag_id=13) tr4 USING (vid)
    INNER JOIN (SELECT video_id vid FROM tag_rel WHERE tag_id=67) tr5 USING (vid)
    -- more joins if more tags -- 
)
AND is_x=0
AND is_y=0
AND deleted IS NULL
LIMIT 0, 60


It executes in ~1.6 seconds.

If I run the inner select alone, it executes in ~0.8 seconds, and the result is 77 video ids.

Now, if I replace the inner select with these (example) video ids:

SELECT *
FROM video v
WHERE v.id IN (
    1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77
)
AND is_x=0
AND is_y=0
AND deleted IS NULL
LIMIT 0, 60


This query executes in ~0.06 seconds. 

Question 1: Why is this the case, and why doesn't the full query run in ~0.86 seconds, which is the sum of the two operations (get video ids by tags and get videos by video ids)?

Part 2

For my application, I can't inject the ids because the inner select might return millions of ids. So I need them in one query, together with the support of checking is_x, is_y and deleted, and offsetting the limit for pagination.

I have spent months going back and forth, and this is the fastest query for most cases.

Question 2: Can this whole query be done faster/better with other techniques?

Question 3: By adding more tags, the query gets drastically slower, but isn't more joins just filtering down the number of possible results for the engine, so it should be faster with more tags?

Info

tag_rel contains about half a billion rows with about .5 million unique tag ids. The video table has around 30 million rows.

Full query explain:

----------------------------------------------------------------------------------------------------------------------------------------------------------------------
| id | select_type | table   | partitions | type   | possible_keys            | key     | key_len | ref                           | rows    | filtered | Extra       |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
|  1 | SIMPLE      | tag_rel | NULL       | ref    | tag_id,video_id          | tag_id  | 4       | const                         | 1847596 |   100.00 | Using index |
|  1 | SIMPLE      | tag_rel | NULL       | eq_ref | tag_id,video_id          | tag_id  | 8       | const,db.tag_rel.video_id     |       1 |   100.00 | Using index |
|  1 | SIMPLE      | tag_rel | NULL       | eq_ref | tag_id,video_id          | tag_id  | 8       | const,db.tag_rel.video_id     |       1 |   100.00 | Using index |
|  1 | SIMPLE      | tag_rel | NULL       | eq_ref | tag_id,video_id          | tag_id  | 8       | const,db.tag_rel.video_id     |       1 |   100.00 | Using index |
|  1 | SIMPLE      | tag_rel | NULL       | eq_ref | tag_id,video_id          | tag_id  | 8       | const,db.tag_rel.video_id     |       1 |   100.00 | Using index |
|  1 | SIMPLE      | v       | NULL       | eq_ref | PRIMARY,is_x_2,deleted   | PRIMARY | 4       | db.tag_rel.video_id           |       1 |    50.00 | Using where |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------


Indexes:

tag_rel.tag_id      = unique(tag_id, video_id)
tag_rel.video_id    = unique(video_id, tag_id)
video.is_x_2        = (is_x, is_y, deleted)
Let's compare your two queries in part 1. Assume you have 100 videos and 10 tags evenly distributed. Every:

SELECT video_id vid FROM tag_rel WHERE tag_id=...


then produces 10 rows. If you join n of those the amount of rows that have to be examined is 10^n. In your example, n is 5 so 100000 rows. The result is then filtered down to whatever amount of videos that have all those tags, and compared with the videos that satisfy the other predicates. This comparison once again multiplies the numbers of rows that have to be compared.

For second query it is sufficient to examine 1000 rows given the assumptions above. This is of course greatly simplified but should give you an idea of the amount of extra work that has to be done in the first case.

What you want to do is to find the videos that have all tags, i.e.:

FORALL x:p(x)

FORALL is the universal quantifier (see for example: https://en.wikipedia.org/wiki/Quantifier_(logic)). Unfortenate, there is no operator in SQL that directly implements this. One way to overcome this is to translate it to an existential quantifier:

FORALL x:p(x) &lt;=> NOT EXISTS x:NOT p(x)

This can be implemented in SQL, however most people find it more intuitive to count the distinct number of tags per movie and compare it to the length of tag list. Your query would then become:

SELECT video_id vid 
FROM tag_rel 
WHERE tag_id in (1,9,27,13,67)
GROUP BY video_id
HAVING COUNT(tag_id) = 5 -- 5 is the number of tags


Now we can simply join this back with videos:

SELECT v.* -- dont use * in your code
FROM video v
JOIN (
    SELECT video_id vid 
    FROM tag_rel 
    WHERE tag_id in (1,9,27,13,67)
    GROUP BY video_id
    HAVING COUNT(tag_id) = 5 -- 5 is the number of tags
) t
    ON t.video_id = v.video_id
WHERE is_x=0
  AND is_y=0
  AND deleted IS NULL;


The list of tags can easily be replaced by a select. 

Apparently this question is not as efficient as the original, but I'll still add a possible optimization:

SELECT v.* -- dont use * in your code
FROM video v
JOIN (
    SELECT video_id vid 
    FROM tag_rel 
    WHERE tag_id in (1,9,27,13,67)
    GROUP BY video_id
    HAVING COUNT(tag_id) = 5 -- 5 is the number of tags
    LIMIT 0, 60
) t
    ON t.video_id = v.video_id
WHERE is_x=0
  AND is_y=0
  AND deleted IS NULL
LIMIT 0, 60;