Что делать, когда растет база данных?
Разработать функционал архивирования заказов. Перемещать из 1 базы с текущими заказами в базу архивных заказов. хранить там. Выборку производить только по запросу архивированных данных.
профит в использовании чистой информации, ненужная хранится на полках
Я бы сначала привёл в порядок индексы таблицы, так как тот же поиск по неиндексированному полю - это очень плохо.
Далее, можно сделать аналогичную по структуре таблицу а-ля "order_archive", туда автоматически переносить все старые/выполненные/еще-по-каким-то-условиям-отобранные, короче, уже не актуальные заказы. И если нужно какую-то статистику, искать уже по ней, не трогая актуальные. Желательно этот поиск вынести с рабочего сервера, интернет-магазину ни к чему видимые пользователями лаги.
В довесок к вышеперечисленному, если хочется очень быстрых запросов в плане статистики, можно настроить Sphinx и искать по нему, он очень быстр (пробовал), или ElasticSearch (собираюсь пробовать)