Оптимизируйте запросы и БД.
Просто написать запрос — недостаточно, важно написать его так, чтобы операции выподнились в оптимальном порядке.
dev.mysql.com/doc/refman/5.5/en/execution-plan-information.html
Т.е. к примеру делать объединение данных а потом фильтрацию заведомо дольще чем сначала отфтльтровать, а потом объединить, исключить использование оператора IN, итд итп.
Партиции! Посмотрите в сторону секционирования.
Потом надо смотреть производительность сервера, узким местом может быть диск, посмотрите что показывает iostat в время выполнения запроса.
Нет, нельзя привязаться к объему ОЗУ. Зависит от индексов, типов операций, нагрузки на диск, а если движек InnoDB, то есть смысл тюнить параметры.
Короче. Несколько были такие таблицы в MySQL 4.xx — все работало нормально если аккуратно. В 5.x должно работать гораздо лучше, т.к. средств новых появилось больше. Указанные Вами объемы (10-20 млн строк) нормально обрабатывал на ноутбуке.