Как улучшить уже оптимизированный запрос, который занимает 18 секунд?

Итак, у меня есть vps с 512mb ram, и таблица MySQL, подобная этой:

CREATE TABLE `table1` (
  `id` int(20) unsigned NOT NULL auto_increment,
  `ts` timestamp NOT NULL default CURRENT_TIMESTAMP,
  `value1` char(31) collate utf8_unicode_ci default NULL,
  `value2` varchar(100) collate utf8_unicode_ci default NULL,
  `value3` varchar(100) collate utf8_unicode_ci default NULL,
  `value4` mediumtext collate utf8_unicode_ci,
  `type` varchar(30) collate utf8_unicode_ci NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `type` (`type`),
  KEY `date` (`ts`)
) ENGINE=MyISAM AUTO_INCREMENT=469692 DEFAULT CHARSET=utf8
  COLLATE=utf8_unicode_ci

Если я выполняю запрос, подобный этому, он занимает 2~18 секунд:

SELECT `id`, `ts`, `value1`, `value2`, `value3` FROM table1 WHERE
`type` = 'something' ORDER BY `id` DESC limit 0,10; 

EXPLAIN SELECT говорит мне:

  select_type: SIMPLE
         type: ref
possible_keys: type
          key: type
      key_len: 92
          ref: const
         rows: 7291
        Extra: Using where; Using filesort

Я думал, что 'using filesort' может быть проблемой, но оказалось. это не так. Если я уберу ORDER BY и LIMIT, то скорость запроса будет такой же. скорость запроса остается такой же (я отключил кэш запросов для тестирования с помощью SET @@query_cache_type=0;).

mysql> EXPLAIN SELECT `id`,`ts`,`value1`,`value2`, `value3` 
       FROM table1 WHERE `type` = 'something'\G

  select_type: SIMPLE
         type: ref
possible_keys: type
          key: type
      key_len: 92
          ref: const
         rows: 7291
        Extra: Using where

Не знаю, имеет ли это значение, но ряды приближение неточное:

SELECT COUNT(*) FROM table1 WHERE `type` = 'something';

Возвращает 22.8k строк.

Запрос кажется уже оптимизированным, я не знаю, как я могу еще больше улучшить его. Вся таблица содержит 370k строк и занимает около 4.6 GiB в размере. Может ли быть такое, что из-за того, что тип случайным образом меняется строка за строкой (случайное распределение во всей таблице). требуется 2~18 секунд только для получения данных с диска?

Забавно, что когда я использую тип, который содержит всего несколько сотен строк, эти запросы тоже медленные. MySQL возвращает строки со скоростью около 100 строк/сек!

|-------+------+-----------|
| count | time |   row/sec |
|-------+------+-----------|
| 22802 | 18.7 | 1219.3583 |
|    11 |  0.1 |      110. |
|   491 |  4.8 | 102.29167 |
|   705 |  5.6 | 125.89286 |
|   317 |  2.6 | 121.92308 |
|-------+------+-----------|

Почему это так медленно? Могу ли я еще больше оптимизировать запрос? Должен ли я переместить данные в меньшие таблицы?

Я думал, что автоматическое разбиение было бы хорошей идеей, чтобы сделать новый раздел для каждого типа динамически. Это невозможно, по многим причинам, включая то, что максимальное число разделов - 1024, и может быть сколько угодно типов. Я также мог бы попробовать разделение на уровне приложений разделение на уровне приложения, создавая новую таблицу для каждого нового типа. Я бы не делать этого, так как это влечет за собой большие сложности. Я не знаю, как я иметь уникальный идентификатор для всех строк во всех таблицах. Кроме того, если я достигну нескольких вставок/секунду, производительность значительно упадет.

Заранее спасибо.