Mysql Создание производительности индекса сортировки для простого частого запроса

Я работаю над таблицей mysql с примерно 4 миллионами записей сообщений и пытаюсь выбрать последние 50 сообщений на основе метки времени.

Дополнительным требованием является то, что возвращаемые сообщения не начинаются с фиксированного префикса.

Проблема в том, что один запрос занимает примерно 25% процессорного времени и занимает около 1,5 секунд. Запрос часто выполняется несколькими клиентами и вызывает проблемы с производительностью на нашем 8-ядерном db-сервере.

SELECT * FROM largeTable
WHERE msg NOT LIKE 'myPrefix%'
ORDER BY timestamp DESC LIMIT 0, 50;

Я попытался профилировать с помощью встроенного в MySQL профилировщика, вот результат для запроса:

+----------------------+----------+
| Status               | Duration |
+----------------------+----------+
| starting             | 0.000044 |
| checking permissions | 0.000004 |
| Opening tables       | 0.000010 |
| init                 | 0.000019 |
| System lock          | 0.000005 |
| optimizing           | 0.000005 |
| statistics           | 0.000007 |
| preparing            | 0.000007 |
| Sorting result       | 0.000002 |
| executing            | 0.000002 |
| Sending data         | 0.000006 |
| Creating sort index  | 0.788023 |
| end                  | 0.000009 |
| query end            | 0.000003 |
| closing tables       | 0.000009 |
| freeing items        | 0.000012 |
| cleaning up          | 0.000010 |
+----------------------+----------+

Сначала я подумал, что, возможно, проблема в том, что он проверяет префикс для всех записей, но после профилирования.

| Creating sort index  | 0.788023 |

Кажется, виновник. Таким образом, пункт ORDER BY?
Как я могу ускорить это?
Есть какой-то тип индекса, который я могу построить, чтобы это исправить?
Новые сообщения добавляются примерно каждые несколько секунд, в то время как запросы происходят чаще.

Спасибо за вашу помощь!

Изменить: Спасибо за комментарии, вот запрошенная информация.

База данных создается и заполняется не моим кодом, а каким-то внешним сервисом python. Я еще не добавил никаких индексов.

Объясните вывод:

id:1
select_type:SIMPLE
table:largeTable
type:ALL
possible_keys:NULL
key: NULL
key_len:NULL
ref: NULL
rows: 3492633
Extra: Using where; Using filesort

Структура таблицы:

 CREATE TABLE `largeTable` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`timestamp` int(10) unsigned NOT NULL,
`client_id` int(11) unsigned NOT NULL,
`name` varchar(32) NOT NULL,
`msg` varchar(528) NOT NULL,
`target_id` int(11) unsigned DEFAULT NULL,
`target_name` varchar(32) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `client` (`client_id`)
) ENGINE=MyISAM AUTO_INCREMENT=4013829 DEFAULT CHARSET=utf8 |