Many-to-many tag filter query with a junction table get slower with more tags. Can it be faster?
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;