how to speed ilike

Hello

I have a task to make postgres find user records no matter if they are
spelled correctly. In particular I have to find names with Lithuanian
letters even if the user searches using latin letters. For example
search criteria 'kestas' should find 'Kęstas'. I've made a function that
converts lithuanian letters to latin and use it like fnk_latin(username)
ILIKE fnk_latin('kestas'). It works OK.

Now the problem is performance. On test data base I have 20000 records
of users, and it takes 3 seconds to get result. On production database
there could be a lot more. How would you advice to improve performance?
Maybe some special index would help? As user names are update rarely
it's the read speed I'm interested in.

--
Julius Tuskenis
Programavimo skyriaus vadovas
UAB nSoft
mob. +37068233050