В реляционных БД
нельзя сделать серебрянную пулю которая всегда будет успешно стрелять.
Чаще всего в БД делают так. Анализируют какие группы запросов наиболее тяжелые
и пытаются материализовать по 1 mat view на каждую группу.
Можно сделать более детальный партишенинг (у вас шардинг) тами образом чтобы искомые данные
всегда лежали в маленькой части таблицы.
Поиск идет в одной из шард, определяемой по дате.
Попробуйте более детальную дату. От суток - к часам. От часов к минутам.
Для поиска используется 2-3 поля, которые являются какими-либо идентификаторами, сильно сужающими выборку (до нескольких записей в пределах нужной даты).
Если у вас есть тренд на использование 1-2 дней (оперативная информация)
то отгрузите этот опер-период в отдельную свехр-быструю БД (Redis)
и сгенерируйте все возможные комбинации запросов и ответов.
Звучит странно но такая материализация может быть выгоднее чем точечные
запросы (которые у вас не являеются OLTP т.к. возвращают в общем случае
более чем 1 строку).
Есть несколько отделов: операционный центр, диспуты, коллекторы, бухгалтерия, аудит, комплаенс, профильные отделы по разным группам транзакций, сопровождение бизнеса и другие. В отделах есть разделение на функции, и в итоге им нужны множества атрибутов для поиска. Всего получается заметно больше 50 множеств, что делает невозможным создание частично индексированных реплик под каждую такую группу пользователей.
Здесь я не очень понял, является ли указание отдела взаимоисключающим. Но попробуйте
подумать направлении фасетов (facets). Это почти
тот-же партишенинг-шардинг но ключ
партишенинга будет сочетанием нескольких атрибутов. 
