Тут нужно говорить о типе информации и о типе запросов. Ну а также об архитектуре всей системы.
Другими словами, при одной организации базы не будут справляться, при другой - будут.
Например, есть бооооольшая таблица с ФИО и паспортами и адресом жительства (город, дом, квартира) , есть индексы по ФИО, номеру паспорта и адресу. Такая база будет нормально работать при поиске конкретных записей, но если мы хотим сделать выборку по городу, то можем потерпеть неудачу из-за большого количества записей в таблице.
Соответственно можно попробовать оптимизировать - разбить таблицу по городам. Каждуму городу отдельную таблицу - тогда выборку по ФИО и номеру паспорта придется делать запросом ко многим таблицам сразу, но при этом выборка по городам будет значительно быстрее.
Можно еще оптимизировать - создать отдельную таблицу по ФИО и паспорту с указанием таблиц городов, а можно отдельно сделать таблицы по каждой букве алфавита.
И так далее.. Это называется нормализацией информации. Но все зависит от типов запросов.
Нельзя, увы, сделать базу под все запросы сразу... Но и для этого есть OLAP-кубы, но это отдельная песнь...
И да, и оракл и сайбейс и ростгрес могут как справляться, так и несправляться - как данные будут организованы, и как к ним будут запросы строиться. Все эти базы нормально работают с миллионами записей в таблицах, весь вопрос как мы этими таблицами будем оперировать...
Что касается архитектуры: то очень часто нужно кешировать какую-то информацию вне баз данных - например на промежуточных серверах, архитектура приложений 3tier или multitier
en.wikipedia.org/wiki/Multitier_architecture (а в русской версии этой статьи фигня написана)
