Во-первых, вы можете использовать NOT REGEXP
вместо подзапроса.
SELECT parent
FROM video
WHERE filename NOT REGEXP '(s[0-9]{2}\e[0-9]{2})|([[:<:]][0-9]{3}[[:>:]])'
GROUP BY parent
При использовании REGEXP
или NOT REGEXP
индексы не имеют значения. Чтобы сделать его более эффективным, если этого еще недостаточно, вам придется взглянуть на использование других строковые функции или оператор LIKE
.