Non è una questione di records, perchè anche access può contenere milioni di records. E' una questione di cose che si possono fare.

MySql fino alla 4 non supporta le viste e le stored procedures e anche le foreign keys sono limitate. Per il resto è veloce e affidabile (meglio la versione sotto linux).

Postgree è un RDBMS molto simile a oracle che puoi trovare su internet.