Александр Аксентьев я так понимаю там одним индексом не обойдешься, скорее всего нужно фильтровать еще по другим полям - значит нужен будет сложный индекс, и при этом правильный (зависит от порядка выполнения запроса).
LaJokero , надеюсь про Нормализацю данных вы уже знаете. Далее читайте вот это:
https://ruhighload.com/%D0%98%D0%BD%D0%B4%D0%B5%D0...
Далее пробуйте разные индексы и тестируйте производительность (напишите тест скрипт для этого, который сбрасывает кеши (дисковый и БД)) - естественно, на тестовом сервере, потому что добавление или удаление индекса на таблице такого размера может заблокировать ее на пару часов.
Разделить таблицу тоже можно, но, не зная структуры таблиц и ваши SQL запросы - советовать сложно.