Так как запрос
SELECT
`tele_id` FROM `webms`
WHERE
`link` LIKE "%mp4"
AND `blocked` = 0
AND `tele_id` IS NOT NULL
AND `tele_id` <> ''
AND `board` = "b"
ORDER BY
rand()
LIMIT 1;
То нужно создать составной индекс на все эти поля. Однако, индексы не работают для текстовых полей с wildcard в начале. Вернее, индекс может использоваться для поиска строки ДО первой wildcard.
Решение простое — разворачивать строку и при создании индекса и при запросе.
То есть, запрос будет начинаться так:
SELECT
`tele_id` FROM `webms`
WHERE
REVERSE(`link`) LIKE "4pm%"
...
И создание индекса:
CREATE INDEX
index_name
ON
webms(REVERSE(link), blocked, tele_id, board);
P.S. с ORDER BY RAND() ты ещё хапнешь горя, поэтому уже сейчас выброси его.
P.P.S. Текстовые поля в БД почти во всех случаях не должны быть NULLable. У поля должно быть одно пустое значение и в случае текстового — это пустая строка. Исключения составляют случаи, когда на текстовое поле нужно создать уникальный констреинт (то есть, если логика подразумевает существование только одного непустого значения и бесконечное количество NULL-значений) или если поле используется в каких-то coalesce.