Paieška + rūšiavimas pagal daug laukelių.

Sveiki,

Situacija yra tokia, tarkim yra lentelė vartotojai, kurioje yra įvairus jų duomenys.
Kiti vartotojai gali atlikti paiešką iš tos lentelės pagal įvairius kriterijus,
pvz. Vardą, Lytį, Gimimo datą, šalį, Miestą, ūgį ir t.t. šių parametrų yra apie 10 ateityje gali prisidėti ir daugiau.
Be to dar tas sąrašas gali būti rūšiuojamas pagal vieną ir kelių laukų pvz. (prisijungimo arba registracijos laikas).

Prašymas/klausimas būtų man nereikia gatavo sprendimo, gal kas nors užvestumėt ant kelio kaip tokiu atveju daroma paieša.

Ta prasme paieškos gali būtį vykdoma pagal įvairius parametrus, vieni ieškos tik pagal vardą, kiti lytį,
kiti lytį+miestą+varda, kiti lytį+šalį ar miestą+šalį+šalį amžių, na tų variantų yra tikrai nemažai plius dar rūšiavimas.

Kadangi mysql naudoja indeksus leftmost principu, tai negi mano atveju kiekvienam variantui reikės kuri skirtingus indeksus?
Gal yra ir kitokių variantų?
Be to vydant paiešką kai mysql pilnai naudoja indeksą ir pradžių veikia greitai, bet nuėjus į kokį 30 puslapį užklausa pailgėja labai stipriai,
nors įrašų skaičius nėra kažkoks labai didelis, jis nuolat kinta bet tarkim 5-10M.

Ačiū už bet kokią pagalbą.