Берите Elastic. Там есть нечеткий поиск( Иавнов вместо Иванов), фасетный поиск(поиск по аттрибутам документа например фамилия судьи), поиск по регуляркам(т.е. вам не нужно будет обрабатывать результат поиска - нужно будет в поисковый запрос дописать то что вы хотели делать регуляркой самостоятельно), поиск по синонимам(в поисковой строке написали автомобиль а в тексте написано машина) и т.д и т.п.
Технология поиска, которую вы описываете называется полнотекстовый поиск. На миллионах документов работает быстро - именно её реализовывают elastic, sphinx и похожие программы. Эти программы используются на многих сайтах для поиска по большим объёмам имеющихся данных- на том же stackoverflow, instagram и т.п.
Бд можно взять postgres, т.к. там хорошо работает шардинг и репликация.
Язык можно взять тот который вы лучше знаете. Главное сервер брать помощнее, т.к. основную работу будет делать поисковая система. Говорят что новый php 7 кушает в два раза меньше оперативной памяти чем раньше, но на мой взгляд php фреймворки очень сильно уступают тому же python Django в плане удобства использования и долгосрочной поддержки уже написанного кода.