Particionar Tabela

Bom dia Galera.

Tenho uma tabela no MySql com a seguinte configuração:

CREATE TABLE `tabela` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `ddd` int(2) DEFAULT NULL,
 `telefone` varchar(11) NOT NULL DEFAULT '',
 `numero` int(10) NOT NULL DEFAULT '0',
 `cep` varchar(8) NOT NULL DEFAULT '',
 `cidade` varchar(40) NOT NULL DEFAULT '',
 `endereco` varchar(60) NOT NULL DEFAULT '',
 `complemento` varchar(50) DEFAULT NULL,
 `bairro` varchar(60) DEFAULT NULL,
 `estado` varchar(30) DEFAULT NULL,
 `nome` varchar(150) NOT NULL DEFAULT '',
 PRIMARY KEY (`id`),
 KEY `telefone` (`telefone`),
 KEY `cep` (`cep`,`numero`),
 KEY `ddd` (`ddd`),
 KEY `cidade` (`cidade`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Esta tabela esta atualmente com cerca de 27 millhoes de registros, e como tenho que efetuar consultas com relacionamento com outras tabelas da base, esta consumindo muito tempo para retornar dados, que em geral estes resultados tambem sao milhares de registros e em alguns casos (estado de SP e RJ e MG) milhoes de registros.

Bom como o titulo do post, estou querendo particionar esta tabela (mysql 5.6) para melhorar a performance das consultas. Neste sentido gostaria de uma ajuda de vocês no que se refere o tipo de partição melhor para os tipos de dados armazenados.

Em resumo:
-> qual tipo de partição vocês indicam?
-> qual coluna devo utilizar para tal partição?

Desde já agradeço a colaboração!