И насколько увеличит время выборки при тяжелых запросах.
Также в базе будут храниться данные аналитики. Ориентировочно будет не менее миллиарда записей.
Тут на 90% все будет зависеть от того какие запросы вы будете гонять. И да NoSQL можно использовать.
Учитывая большую инерционность такой маркетинговой информации (емейл и домен почти никогда не переименовывается и редко удаляется) то можно делать две денормализованные таблички
Emails-2-domains
email | domainlist
user@site.com | [ google.com, yahoo.com, ..... ]
Domains-2-emails
И тут связи будут в обратную сторону. От домена к списку людей.