Bei 5 Mio. Datensätzen würde ich mir noch keine Gedanken um Partitionierung und Co. machen.
Solange der Rechner nicht ein alte Krücke ist und man kein SW-Implementierungsfehler macht dürften Indize und genügend Speicher (wenn möglich sollten alle Indizes von der
DB im Speicher gehalten werden können) ausreichen. Solltest du mal in den Bereich Mrd-Datensätze kommen dann können wir wieder uns unterhalten.