Optimizar la consulta de PostgreSQL con la función levenshtein().

Tengo una tabla con aproximadamente 7 millones de registros. La tabla tiene una columna de nombre y apellido que quiero buscar utilizando la función de distancia levenshtein().

select levenshtein('JOHN', first_name) as fn_distance,
       levenshtein('DOE', last_name) as ln_distance,
       id,
       first_name as "firstName",
       last_name as "lastName"
  from person
 where first_name is not null
   and last_name is not null
   and levenshtein('JOHN', first_name) <= 2
   and levenshtein('DOE', last_name) <= 2
 order by 1, 2
 limit 50;

La búsqueda anterior es lenta (4 – 5 segundos), ¿qué puedo hacer para mejorar el rendimiento? ¿Debo crear índices en las dos columnas o algo más?

Después de añadir los siguientes índices:

create index first_name_idx on person using gin (first_name gin_trgm_ops);

create index last_name_idx on person using gin(last_name gin_trgm_ops);

La consulta ahora tarda ~11 segundos. 🙁

Nueva consulta:

select similarity('JOHN', first_name) as fnsimilarity,
       similarity('DOW', last_name) as lnsimilarity,
       first_name as "firstName",
       last_name as "lastName",
       npi
  from person
 where first_name is not null
   and last_name is not null
   and similarity('JOHN', first_name) >= 0.2
   and similarity('DOW', last_name) >= 0.2
 order by 1 desc, 2 desc, npi
 limit 50;