Ik heb onder MySQL een database met zo'n 400 miljoen records (gemiddeld 500 inserts per minuut) die gesplitst is in tabellen van 20-30 miljoen records, en het ophalen van een willekeurig record duurt een fractie van een seconde, mits geïndiceerd. Het doorzoeken van de hele database wanneer een kolom geen index heeft duurt bijna een kwartier.
Bij 20000 records zou ik me niet zo bijzonder veel zorgen maken ;-)