Все верно - [B]Все зависит от реализации[/B], как эти 25 миллионов обновляться потом будут, кем и как часто, если сомневаетесь в чем то - поставьте демку и сгенерите эти 25 миллионов случайных записей, посмотрите как ведет себя система. Я делал аналог кинопоиска - засунул всего один миллион актеров в инфоблок, так в админке невозможно работать стало при пролистывании ИБ. Потом разбил на М и Ж, потом разбил М(и Ж) начиная с букв A B C ...., потом еще какие-то извращения были, пришел к своим таблицам, вместо ИБ. И админку для управления пришлось дописывать.
Пробовал те же манипуляции с WP и phpBB - импорт актеров также занимал больше суток.
Так что дело в реализации, можно и свои таблицы неправильно составить или индекс "забыть". Или с JOIN переборщить или неправильно составить.