Таблица с 80 миллионами записей и добавление индекса занимает более 18 часов (или навсегда)! Что теперь?

Краткое описание того, что произошло. Я работаю с 71 миллионом записей (немного по сравнению с миллиардами записей, обработанных другими). В другом потоке кто-то предположил, что текущая настройка моего кластера не подходит для моих нужд. Моя таблица имеет следующую структуру:

CREATE TABLE `IPAddresses` (
  `id` int(11) unsigned NOT NULL auto_increment,
  `ipaddress` bigint(20) unsigned default NULL,
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM;

И я добавил 71 миллион записей, а затем сделал:

ALTER TABLE IPAddresses ADD INDEX(ipaddress);

Прошло 14 часов, а операция все еще не завершена. Погуглив, я обнаружил, что есть хорошо известный подход к решению этой проблемы - разбиение на разделы. Я понимаю, что теперь мне нужно разбить мою таблицу на разделы на основе IP-адреса, но могу ли я сделать это без воссоздания всей таблицы? Я имею в виду, через оператор ALTER? Если да, то было одно требование, гласящее, что столбец, который будет секционироваться, должен быть первичным ключом. Я буду использовать идентификатор этого ip-адреса при построении другой таблицы, поэтому ipaddress не является моим первичным ключом. Как разделить мою таблицу на части в этом сценарии?