Как снизить нагрузку на БД или какую БД использовать?
В порядке действий:анализ, что работает медленно (не "заказчик говорит медленно", а например  "запрос для товаров, при выборке по акциям и покупателям" работает 2 секунды)оптимизация кода, работающего с запросами (снижение числа запросов или более точные выборки) -- самая популярная проблема, - снижал на этом только этапе в 1000-1500 раз, 
- видел по 1500 запросов на страницу, 
- видел 1 запрос, но на всю таблицу и потом по коду с этими данными гигантская работа, когда можно было сделать 2 ооочень шустрых запроса в БД с конечными данными :)
- запросы в цикле, очень много раз видел (гуглить проблема N+1)оптимизация медленных запросовСделать запрос более быстрым, за счет или более точных выборок, или более верного синтаксиса, или стоит например раздробить на нексколько очень мелких, а бекендом все привести к нужному видуиндексы (сильно оптимизируют и бывают достаточны для решений многих бед со скоростью  на большой выборке)кеш на стороне БДкеш на стороне приложенияденормализация некоторых данных, например предагрегация (например меню сайта и нужно для каждого вывести число твоаров, каждый пункт связан с категорией, категорий много, чтобы каждый раз по 100 категорий на подсчет товаров для каждой не делать -- делать это сильно реже и хранить в некой агрегирующей табличке)С техниками типа шардинга/репликации никогда не работал
Миллионы записей - это совершенно обычный и, я бы сказал, крайне небольшой кейс для MySQL.
Самое быстрое: отпрофилировать запросы (например, performance_schema=1 и подключить sys-таблицы, они наполнятся данными по прошествии времени), найти неоптимизированные индексами и добавить недостающие индексы на этих таблицах.