Da gibt es Unmengen an Faktoren. Gute Indizes sind ganz wichtig (hat himitsu ja schon gesagt) und dann ist auch ein wichtiger Faktor, wie viele Daten deine
Query denn tatsächlich zurückliefert. Der beste Index hilft nicht viel, wenn deine Abfragen tausende Zeilen als Ergebnis liefern müssen. Hinzu kommt auch, wie viele User gleichzeitig die
DB mit Abfragen quälen. Bei richtig großen Datenbanken werden Datenbanken auf verschiedene Rechner verteilt (z.B. eine große Tabelle auf Rechner 1, eine andere auf Rechner 2 und den ganzen Kleinkram auf Rechner 3. Mann kann in manchen großen DBs sogar einzelne Spalten von Tabellen auslagern), aber dafür müssen es schon sehr viele Datensätze und User sein, damit sich der Aufwand wirklich lohnt.
Im Kleinen gilt meist: Kluge Indizes und sinnvolles Design von Tabellen und Abfragen (um mit den Indizes möglichst schnell die wenigen benötigten Datensätze zu finden). Damit kann man die Grenze schon recht weit nach oben verschieben