Mysql быстрая сортировка по ФИО

Есть табличка - 1млн человек, есть разные данные, внешние ключи и тд. Необходимо быстро (насколько это возможно) выбрать из таблички данные, отсортированные по ФИО.

Слегка почитал про индексы, которые улучшают выборку. Сделал индекс BTREE f_name + i_name + o_name, и по BTREE индексу для каждого поля. При EXPLAIN ни один индекс не используется. Даже при ORDER BY f_name (одно поле) - не используется ничего.

Подскажите, пожалуйста, как быть.

UPD1:

CREATE TABLE `table` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `group_id` int(10) unsigned NOT NULL DEFAULT '0',
  `division_id` int(10) unsigned DEFAULT NULL,
  `parent_id` int(10) unsigned DEFAULT NULL,
  `category_id` int(10) unsigned DEFAULT NULL,
  `f_name` varchar(255) NOT NULL DEFAULT '',
  `i_name` varchar(255) NOT NULL DEFAULT '',
  `o_name` varchar(255) DEFAULT NULL,
  `birth_date` date DEFAULT NULL,
  `address` varchar(255) DEFAULT NULL,
  `phone` varchar(255) DEFAULT NULL,
  `mail` varchar(255) DEFAULT NULL,
  `status` varchar(45) DEFAULT NULL,
  `check` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `addr_object_id` char(36) DEFAULT NULL,
  `addr_house_id` char(36) DEFAULT NULL,
  `addr_room` char(36) DEFAULT NULL,
  `place_id` int(10) unsigned DEFAULT NULL,
  `check_from` datetime DEFAULT NULL,
  `check_to` datetime DEFAULT NULL,
  `check_period` varchar(45) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `FK_table_1` (`group_id`),
  KEY `FK_table_2` (`division_id`),
  KEY `FK_table_3` (`parent_id`),
  KEY `FK_table_4` (`place_id`),
  KEY `FK_table_5` (`category_id`),
  KEY `Index_F` (`f_name`),
  KEY `Index_I` (`i_name`),
  KEY `Index_FIO` (`f_name`,`i_name`) USING BTREE,
  KEY `Index_division` (`division_id`),
  CONSTRAINT `FK_table_1` FOREIGN KEY (`group_id`) REFERENCES `groups` `id`),
  CONSTRAINT `FK_table_2` FOREIGN KEY (`division_id`) REFERENCES `divisions` (`id`) ON DELETE SET NULL ON UPDATE SET NULL,
  CONSTRAINT `FK_table_3` FOREIGN KEY (`parent_id`) REFERENCES `table` (`id`),
  CONSTRAINT `FK_table_4` FOREIGN KEY (`place_id`) REFERENCES `places` (`id`),
  CONSTRAINT `FK_table_5` FOREIGN KEY (`category_id`) REFERENCES `categories` (`id`) ON DELETE SET NULL ON UPDATE SET NULL
) ENGINE=MyISAM AUTO_INCREMENT=398351 DEFAULT CHARSET=utf8

Запрос:

EXPLAIN SELECT * FROM table ORDER BY f_name

Ответ:

id, select_type, table, type, possible_keys, key, key_len, ref, rows, Extra
1, 'SIMPLE', 'cooperators', 'ALL', '', '', '', '', 383343, 'Using filesort'