У Вас есть 2 задачи: задача найти вхождения строки, и задача выбрать из результатов случайные 10.
Это 2 разные задачи :)
Первую задачу логично решать используя инструменты предназначенные для поиска, например Sphinx.
sphinxsearch.com
Он быстро вернет Вам id подходящих записей.
Из них средставами PHP выбираем сколько надо случайных, далее запрос в SQL
select ... where id in (1,2,3,4...)
В Вашем случае это будет наиболее производительное и масштабируемое решение.
PS Мне не очень понятна сама идея вывода 10
случайных записей соответствующих паттерну. Не лучше ли выводить 10 самых релевантных? :) Или у вас слишком общий паттерн и о релевантности речи не идет? Уточните этот момент пожалуйста.
