[kullervo]

Jag förutsätter att du använder en av de vanligare SQL-databserna.

Det låter som det bara handlar om svenska personer. Eftersom det bara bor 10 miljoner pers i Sverige kan det inte vara problem med de där sökningarna. Släng på ett standardindex på alla kolumnerna, läs manualen till din databasmotor för index och se om du inte kan slänga in mer specifika index (booleska tänker jag på i första hand) när du tagit reda på vad de är vanligt att söka på. Så länge tabellen inte uppdateras mycket kan du köra massor av index men förmodligen räcker det med få väl utvalda istället.