MySql большое количество Rows examined

У меня вопрос к спецам по MySql. В логе медленных запросов есть вот такой запрос:

select *
from `orders`
where (
        `id` = 'подольск'
        or `startpoint` like '%подольск%'
        or `endpoint` like '%подольск%'
        or `ic_txt` like '%подольск%'
        or `manager_txt` like '%подольск%'
        or `car_type_text` like '%подольск%'
        or `cargo_type_txt` like '%подольск%'
        or `car_count` like '%подольск%'
        or `dispatcher_txt` like '%подольск%'
        or `start_street` like '%подольск%'
        or `end_street` like '%подольск%'
    )
    and `deleted_at` is null
    and `state_id` not in (5, 6, 7, 8, 9)
order by `created_at` desc
limit 25 offset 0

Данный запрос возвращает всего три записи.

И Rows_examined: 114082 что значит обработано 114082 строк.

Если убрать из этого запроса LIKE и выбрать количество записей

select count(*)
from `orders`
where
    `deleted_at` is null
    and `state_id` not in (5, 6, 7, 8, 9)

То мы получим всего 300 штук.

Всего записей в таблице 114105 (на момент выполнения запроса было 114082 видимо). Т.е. перебираются все записи в таблице. Чего, по моему мнению, происходить не должно. Я бы ожидал, будут обработаны всего 300 записей, а остальные отброшены по индексу.

Индексы для полей deleted_at и state_id присутсвуют.

EXPLAIN показывает следующее:

+----+-------------+--------+-------+-----------------------------+ | id | select_type | table | type | possible_keys | +----+-------------+--------+-------+-----------------------------+ | 1 | SIMPLE | orders | index | PRIMARY,deleted_at,state_id | +----+-------------+--------+-------+-----------------------------+

+------------+---------+------+------+-------------+ | key | key_len | ref | rows | Extra | +------------+---------+------+------+-------------+ | created_at | 4 | NULL | 71 | Using where | +------------+---------+------+------+-------------+

Насколько я понимаю, индексу MySql видит, но не считает нужным их использовать.

Есть какие либо идеи?

PS: В EXPLAIN как я вижу показывает обработку всего 71 строки (возможно кеш). Почему тогда в боевом варианте такие вещи происходят?