No tak já jsem pracoval s tabulkami cca. 20 mil. záznamů v MySQL a můžu potvrdit, že to nefunguje zrovna moc optimálně - indexy v tomhle případě sice pomůžou, ale i tak kolikrát nějaký i celkem jednoduchý dotaz trvá několik vteřin.
Důležitý asi nebude jenom typ databáze, ale i disk, určitě u velkého množství záznamů bych zvolil SSD, ta databáze ve výsledku stejně bude mít při tomhle objemu pár desítek gigabajtů, což se tam vejde.
Další věc jsou různé statistiky. Já jsem to řešil tak, že jsem ty statistiky průběžně generoval do jiné tabulky, a pak jsem promazával tu hlavní, kam se zapisovalo. Můžeš například vydumpovat data do určitého ID, ty zakomprimovat, zazálohovat a smazat s tabulky (samozřejmě co si potom vyjedeš statistiky co potřebuješ).
Mírné navýšení výkonu MySQL také provede příkaz Optimize table, ale zamyká tabulky, což je trošku problém.
V každém případe určitě použij SSD disky!