How could I optimize this SQL request to find similarity in name ? (pg_trgm.similarity)

Question

I have created a query which takes about 15 min to complete with 20.000+ records

What I'm trying to do is pairing clients with similarity in their full name

My current query :

SELECT      a.full_name, a.id, b.id
FROM        debtors as a
INNER JOIN  debtors as b on similarity(a.full_name, b.full_name) >= 0.6
WHERE       a.id != b.id
ORDER BY    a.full_name, a.id

Is it normal that it is taking so long ? If not would there be a way to speed up this process ?

I have tried indexing the full_name column, but it is not helping

EDIT: Thanks to @JonasMetzler, I manage to reduce that time to 1 minute

Links :

https://dba.stackexchange.com/questions/103821/best-index-for-similarity-function

https://stackoverflow.com/a/11250001/11940866