Миллионы строк для современных СУБД - сущая ерунда.
Максимально быстро зависит не просто тупо от БД.
А от вашего мозга - какую сделаете структуру БД, какие индексы и пр. и пр.
Хотите максимально быстро - Tarantool.
Но это как из пушки по воробьям.
Я точно могу знать что mysql в один момент перестанет справляться, это учитывая тот факт, что категорически не буду юзать JOIN
Вообще цель такая, складировать данные, но складировать так, чтобы данные по полю разбивались по регионам и по алфавиту, то есть получается такая база(органическая) и схожая всё таки с графовой.
По поводу Neo4j хотелось бы услышать от бывалых :)