Встал такой вопрос: как быстро работать с 20-100 милионами записей (возможно до 300-500 млн.)
Какую бд взять? MySQL сразу отпадает, т.к. после 1млн. записей он отдыхает.

Прошу посоветовать, обосновав. 

АдамАдамович, это вы разделом ошиблись, вам сюда - http://forum.vingrad.ru/index.php?showforum=153

да и вообще выбор не большой: MS SQL Server или Oracle, если сервер на никсах - то выбора нету   

DB/2 рулит...   
И кластеров, кластеров побольше... 

Kesh, это же сколько денег надо...

а вообще вопрос некорректный: все зависит от записей, если там пара integer-полей и не нужны никакие сложные запросы, то может и MySQL потянет   

АдамАдамович, насчёт того, что мускул падает на миллионе записей- это маловероятно, что Вы, простите, с ними делаете? ;)
Если бесплатную и с открытыми исходниками, то советую PostgreSQL, не жалко денег- Oracle или MSSQL Server, тут всё зависит от религии  

Вообще таблица такая:
id (int) | name (text) | dop (text) | owner (text) | price (float)

А мускул не умерает а просто идет курить ...  10-20 секунд - это не нормально. 

АдамАдамович, если Вы выбираете данные, ну допустим так:то, возможно серваку не хватает памяти. Если же выборка идёт с условием, то нужно смотреть на сложность условия.
А ещё вполне может быть, что у Вас индексы неверно расставлены в таблице, а это ой как сильно, в некоторых случаях, влияет на скорость выборки.
К выбору СУБД стоит подходить осознано, взвесив все "за" и "против", учитывая особенности той или иной СУБД, имея перед глазами хотя бы предварительную структуру баз данных с которыми будет происходить работа. 

Я бы с dbf'ами работал  

да, смотря ,конечно, по длинне строковых полей, можно и интербейз-фаерберд юзать. Работать будет. Тока индексы нормально создать нужно будет  

сначала не обратил на это внимания, но сейчас прокомментирую.
Есть оператор сотовой связи X, весь биллинг, вообще всё данные хранятся в оракле 8й и 9й версий. Когда оператор X желает провести рассылку смс миллиону своих абонентов, ему приходится делать соответственно выборку из БД. Вот эта выборка занимает гораздо больше 10 секунд 
так что я бы не утверждал о "ненормальности" такой скорости  

У меня более 10 млн. в таблице и летает от 0,06 до 1, а если не можешь правильно спроектировать БД и составить правильно и оптимально SQL-запросы, а также разумно повесить индексы, то это еще совсем не означает, что СУБД корявая!!!