Encontrando strings semelhantes com o PostgreSQL rapidamente

Do jeito que você tem, a semelhança entre todos os elementos e todos os outros elementos da tabela deve ser calculada (quase uma junção cruzada). Se sua tabela tiver 1.000 linhas, já são 1.000.000 (!) cálculos de similaridade, antes esses podem ser verificados em relação à condição e classificados. Escala terrivelmente.

Use SET pg_trgm.similarity_threshold e o % operador em vez disso. Ambos são fornecidos pelo pg_trgm módulo. Desta forma, um índice trigrama GiST pode ser usado com grande efeito.

O parâmetro de configuração pg_trgm.similarity_threshold substituiu as funções set_limit() e show_limit() no Postgres 9.6. As funções obsoletas ainda funcionam (a partir do Postgres 13). Além disso, o desempenho dos índices GIN e GiST melhorou de várias maneiras desde o Postgres 9.1.

Tente em vez disso:

SET pg_trgm.similarity_threshold = 0.8;  -- Postgres 9.6 or later
  
SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name
FROM   names n1
JOIN   names n2 ON n1.name <> n2.name
               AND n1.name % n2.name
ORDER  BY sim DESC;

Mais rápido por ordens de magnitude, mas ainda lento.

pg_trgm.similarity_threshold é uma opção "personalizada", que pode ser tratada como qualquer outra opção. Ver:

Consulte um parâmetro (configuração postgresql.conf) como "max_connections"

Você pode querer restringir o número de pares possíveis adicionando pré-condições (como combinar as primeiras letras) antes junção cruzada (e suporte isso com um índice funcional correspondente). O desempenho de uma junção cruzada deteriora com O(N²) .

Isso não funciona porque você não pode fazer referência a colunas de saída em WHERE ou HAVING cláusulas:

WHERE ... sim > 0.8

Isso está de acordo com o padrão SQL (que é tratado de maneira bastante flexível por alguns outros RDBMS). Por outro lado:

ORDER BY sim DESC

Funciona porque as colunas de saída podem ser usado em GROUP BY e ORDER BY . Ver:

O PostgreSQL reutilizando o resultado da computação na consulta selecionada

Caso de teste

Fiz um teste rápido no meu antigo servidor de teste para verificar minhas declarações.
PostgreSQL 9.1.4. Tempos medidos com EXPLAIN ANALYZE (melhor de 5).

CREATE TEMP table t AS 
SELECT some_col AS name FROM some_table LIMIT 1000;  -- real life test strings

Primeira rodada de testes com índice GIN:

CREATE INDEX t_gin ON t USING gin(name gin_trgm_ops);  -- round1: with GIN index

Segunda rodada de testes com índice GIST:

DROP INDEX t_gin;
CREATE INDEX t_gist ON t USING gist(name gist_trgm_ops);

Nova consulta:

SELECT set_limit(0.8);

SELECT similarity(n1.name, n2.name) AS sim, n1.name, n2.name
FROM   t n1
JOIN   t n2 ON n1.name <> n2.name
           AND n1.name % n2.name
ORDER  BY sim DESC;

Índice GIN usado, 64 hits:tempo de execução total:484,022 ms
Índice GIST usado, 64 hits:tempo de execução total:248,772 ms

Consulta antiga:

SELECT (similarity(n1.name, n2.name)) as sim, n1.name, n2.name
FROM   t n1, t n2
WHERE  n1.name != n2.name
AND    similarity(n1.name, n2.name) > 0.8
ORDER  BY sim DESC;

Índice GIN não usado, 64 hits:tempo de execução total:6345,833 ms
índice GIST não usado, 64 hits:tempo de execução total:6335,975 ms

Caso contrário, resultados idênticos. Conselho é bom. E isso é para apenas 1.000 linhas !

GIN ou GiST?

O GIN geralmente oferece desempenho de leitura superior:

Diferença entre o índice GiST e GIN

Mas não neste caso em particular!

Isso pode ser implementado de forma bastante eficiente por índices GiST, mas não por índices GIN.

Índice de várias colunas em 3 campos com tipos de dados heterogêneos