[MySQL] sposób wyszukiwania imion Opcje

[szybki]

Posiadam dwie kolumny, imię i nazwisko ok milion rekordów. W jaki sposób będzie najbardziej wydajny? REGEXP czy FULLTEXT? To musi działać w taki sposób, aby zapytanie zwróciło ZAWSZE wszystkie wyniki (oczywiście zapytanie jest stronicowane), uwzględniać pl znaki.