Как оптимизировать COUNT(*)?
создайте таблицу в ней что то типа rows_matched
при инсерте нужной фразы добавляйте 1
при удалении вычитайте

по итогу у вас вместо тяжелого селекта очень легкий запрос
Будет ли от этого оптимизация или будет еще хуже?
В описанной ситуации, скорее всего, будет.
Вот пример для таблицы на 5 млн строк:
> EXPLAIN ANALYZE select count(*) from u where val like 'xz%';
-> Aggregate: count(0)  (actual time=358.829..358.829 rows=1 loops=1)
    -> Filter: (u.val like 'xz%')  (cost=1081.88 rows=4995) (actual time=0.388..358.196 rows=4995 loops=1)
        -> Index range scan on u using u_val  (cost=1081.88 rows=4995) (actual time=0.383..356.709 rows=4995 loops=1)

> EXPLAIN ANALYZE select count(*) from (select id from u where val like 'zx%' limit 11) q;
-> Aggregate: count(0)  (actual time=1.609..1.609 rows=1 loops=1)
    -> Table scan on q  (actual time=0.002..0.005 rows=11 loops=1)
        -> Materialize  (actual time=1.594..1.601 rows=11 loops=1)
            -> Limit: 11 row(s)  (actual time=0.089..1.560 rows=11 loops=1)
                -> Filter: (u.val like 'zx%')  (cost=1183.58 rows=5465) (actual time=0.088..1.555 rows=11 loops=1)
                    -> Index range scan on u using u_val  (cost=1183.58 rows=5465) (actual time=0.082..1.537 rows=11 loops=1)

Ускорение более чем в 200 раз. Разумеется, тут важно, что строк, подходящих под условие, в таблице значительно больше 10 - в данном случае 5.5 тысяч. Если подходящих строк будет в пределах нескольких десятков, разница будет не особо заметна.