Я решил очень похожую задачу с помощью MySQL.
У меня в похожей, как у вас, таблице со списком людей порядка 100 млн записей, и примерно 60 полей. Вся база занимает порядка 30 ГБ вместе с индексами.
Скорость выполнения запросов: 30-200 мс, естественно благодаря индексам. При таких объемах нужно оптимизировать запросы и без индексов никак.