Наверное в случае такого количества данных я бы сделал отдельную таблицу (архив) куда бросал все обработанные записи, если они никогда не станут 0, смысл на них тратить время. И не нужны никакие индексы вообще.
Кстати, подумай над тем, что бы соединить массив в 1 строку и сделать 1 запрос по любому из слов в строке. Если строка получается длинная можно разбить на несколько, в любом случае запрос станет быстрее. WAYS, сегодня в 13:56
Используйте кеш, и 1й совет. Иного способа просто нет. Так же рекомендую сделать что бы поиск начинался с более 2-3х символов, дабы сократить кол-во результатов. Да и лимит не забывайте.