Postgres, levenshtein distance and nested queries
I suggest to use a trigram index provided by the additional module pg_trgm.  Combine that with the length of the string to get a valid pre-selection.


Drop the columns T4,T16 and T64 (faster in a single statement), and run VACUUM FULL or CLUSTER.
Install pg_trgm. Details here:


Full Text Search With PostgreSQL

Create a GiST index on tl and length(tl).


There are a details to be observed. Related answers on dba.SE involving pg_trgm:


https://dba.stackexchange.com/search?q=pg_trgm