Algoritmo para encontrar o prefixo mais longo

Eu tenho duas mesas.

O primeiro é uma tabela com prefixos

code name price
343  ek1   10
3435 nt     4
3432 ek2    2

O segundo é o registro de chamadas com números de telefone

number        time
834353212     10
834321242     20
834312345     30

Preciso escrever um script que encontre o prefixo mais longo dos prefixos para cada registro e escreva todos esses dados na terceira tabela, assim:

 number        code   ....
 834353212     3435
 834321242     3432
 834312345     343

Para o número 834353212, devemos aparar '8' e, em seguida, encontrar o código mais longo da tabela de prefixos, seu 3435.
Sempre devemos soltar primeiro '8' e o prefixo deve estar no início.

Eu resolvi essa tarefa há muito tempo, de maneira muito ruim. Foi um script perl terrível, que faz muitas consultas para cada registro. Este script:

1. Pegue um número da tabela de chamadas, faça a substring do comprimento (número) para 1 => prefixo $ no loop

2. Faça a consulta: selecione count (*) em prefixos em que códigos como '$ prefix'

3. Se contar> 0, pegue os primeiros prefixos e escreva na tabela

O primeiro problema é a contagem de consultas - é call_records * length(number). O segundo problema são LIKEexpressões. Receio que sejam lentos.

Tentei resolver o segundo problema:

CREATE EXTENSION pg_trgm;
CREATE INDEX prefix_idx ON prefix USING gist (code gist_trgm_ops);

Isso acelera cada consulta, mas não resolveu o problema em geral.

Agora tenho prefixos de 20k e números de 170k , e minha solução antiga é ruim. Parece que preciso de uma nova solução sem loops.

Apenas uma consulta para cada registro de chamada ou algo assim.

Estou assumindo o tipo de dados textpara as colunas relevantes.

CREATE TABLE prefix (code text, name text, price int);
CREATE TABLE num (number text, time int);

Solução "Simples"

SELECT DISTINCT ON (1)
       n.number, p.code
FROM   num n
JOIN   prefix p ON right(n.number, -1) LIKE (p.code || '%')
ORDER  BY n.number, p.code DESC;

Elementos chave:

DISTINCT ONé uma extensão do Postgres do padrão SQL DISTINCT. Encontre uma explicação detalhada para a técnica de consulta usada nesta resposta relacionada no SO .
ORDER BY p.code DESCescolhe a correspondência mais longa, porque '1234'classifica depois '123'(em ordem crescente).

Violino simples do SQL .

Sem índice, a consulta seria executada por muito tempo (não esperou para vê-la terminar). Para tornar isso rápido, você precisa de suporte ao índice. Os índices trigramas que você mencionou, fornecidos pelo módulo adicional, pg_trgmsão um bom candidato. Você precisa escolher entre o índice GIN e GiST. O primeiro caractere dos números é apenas ruído e pode ser excluído do índice, tornando-o um índice funcional.
Nos meus testes, um índice GIN de trigrama funcional venceu a corrida sobre um índice GiST de trigrama (conforme o esperado):

CREATE INDEX num_trgm_gin_idx ON num USING gin (right(number, -1) gin_trgm_ops);

Dbfiddle avançado aqui .

Todos os resultados de teste são de uma instalação de teste local do Postgres 9.1 com uma configuração reduzida: números de 17k e códigos de 2k:

• Tempo de execução total: 1719.552 ms (trigram GiST)
• Tempo de execução total: 912.329 ms (trigram GIN)

Muito mais rápido ainda

Falha na tentativa com text_pattern_ops

Quando ignoramos o primeiro caractere de ruído perturbador, ele se resume à correspondência básica de padrões ancorados à esquerda . Portanto, tentei um índice de árvore B funcional com a classe de operadortext_pattern_ops (assumindo o tipo de coluna text).

CREATE INDEX num_text_pattern_idx ON num(right(number, -1) text_pattern_ops);

Isso funciona de maneira excelente para consultas diretas com um único termo de pesquisa e faz com que o índice trigrama pareça ruim em comparação:

SELECT * FROM num WHERE right(number, -1) LIKE '2345%'

• Tempo de execução total: 3.816 ms (trgm_gin_idx)
• Tempo de execução total: 0,147 ms (text_pattern_idx)

No entanto , o planejador de consultas não considerará esse índice para ingressar em duas tabelas. Eu já vi essa limitação antes. Ainda não tenho uma explicação significativa para isso.

Índices de árvore B parcial / funcional

A alternativa é usar verificações de igualdade em cadeias parciais com índices parciais. Isso pode ser usado em a JOIN.

Como normalmente temos apenas um número limitado de different lengthsprefixos, podemos criar uma solução semelhante à apresentada aqui com índices parciais.

Digamos, temos prefixos que variam de 1 a 5 caracteres. Crie um número de índices funcionais parciais, um para cada comprimento de prefixo distinto:

CREATE INDEX prefix_code_idx5 ON prefix(code) WHERE length(code) = 5;
CREATE INDEX prefix_code_idx4 ON prefix(code) WHERE length(code) = 4;
CREATE INDEX prefix_code_idx3 ON prefix(code) WHERE length(code) = 3;
CREATE INDEX prefix_code_idx2 ON prefix(code) WHERE length(code) = 2;
CREATE INDEX prefix_code_idx1 ON prefix(code) WHERE length(code) = 1;

Como esses são índices parciais , todos eles juntos são pouco maiores que um único índice completo.

Adicione índices correspondentes para números (levando em consideração o caractere de ruído principal):

CREATE INDEX num_number_idx5 ON num(substring(number, 2, 5)) WHERE length(number) >= 6;
CREATE INDEX num_number_idx4 ON num(substring(number, 2, 4)) WHERE length(number) >= 5;
CREATE INDEX num_number_idx3 ON num(substring(number, 2, 3)) WHERE length(number) >= 4;
CREATE INDEX num_number_idx2 ON num(substring(number, 2, 2)) WHERE length(number) >= 3;
CREATE INDEX num_number_idx1 ON num(substring(number, 2, 1)) WHERE length(number) >= 2;

Embora esses índices mantenham apenas uma substring e sejam parciais, cada um cobre a maior parte ou a totalidade da tabela. Portanto, eles são muito maiores juntos que um único índice total - exceto números longos. E eles impõem mais trabalho para operações de gravação. Esse é o custo para uma velocidade incrível.

Se esse custo for alto demais para você (o desempenho da gravação é importante / muitas operações de gravação / espaço em disco é um problema), você pode pular esses índices. O resto ainda é mais rápido, se não tão rápido quanto poderia ser ...

Se os números nunca forem mais curtos que os ncaracteres, elimine WHEREcláusulas redundantes de algumas ou de todas e também elimine a WHEREcláusula correspondente de todas as consultas a seguir.

CTE recursiva

Com toda a configuração até agora, eu esperava uma solução muito elegante com um CTE recursivo :

WITH RECURSIVE cte AS (
   SELECT n.number, p.code, 4 AS len
   FROM   num n
   LEFT    JOIN prefix p
            ON  substring(number, 2, 5) = p.code
            AND length(n.number) >= 6  -- incl. noise character
            AND length(p.code) = 5

   UNION ALL 
   SELECT c.number, p.code, len - 1
   FROM    cte c
   LEFT   JOIN prefix p
            ON  substring(number, 2, c.len) = p.code
            AND length(c.number) >= c.len+1  -- incl. noise character
            AND length(p.code) = c.len
   WHERE    c.len > 0
   AND    c.code IS NULL
   )
SELECT number, code
FROM   cte
WHERE  code IS NOT NULL;

• Tempo de execução total: 1045.115 ms

No entanto, embora essa consulta não seja ruim - ela é tão boa quanto a versão simples com um índice GIN de trigrama -, ela não fornece o que eu estava buscando. O termo recursivo é planejado apenas uma vez, portanto, ele não pode usar os melhores índices. Somente o termo não recursivo pode.

UNIÃO TUDO

Como estamos lidando com um pequeno número de recursões, podemos apenas explicá-las iterativamente. Isso permite planos otimizados para cada um deles. (Porém, perdemos a exclusão recursiva de números já bem-sucedidos. Portanto, ainda há espaço para melhorias, especialmente para uma variedade maior de comprimentos de prefixos)):

SELECT DISTINCT ON (1) number, code
FROM  (
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 5) = p.code
            AND length(n.number) >= 6  -- incl. noise character
            AND length(p.code) = 5
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 4) = p.code
            AND length(n.number) >= 5
            AND length(p.code) = 4
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 3) = p.code
            AND length(n.number) >= 4
            AND length(p.code) = 3
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 2) = p.code
            AND length(n.number) >= 3
            AND length(p.code) = 2
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 1) = p.code
            AND length(n.number) >= 2
            AND length(p.code) = 1
   ) x
ORDER BY number, code DESC;

• Tempo de execução total: 57,578 ms (!!)

Um avanço, finalmente!

Função SQL

O agrupamento em uma função SQL remove a sobrecarga de planejamento da consulta para uso repetido:

CREATE OR REPLACE FUNCTION f_longest_prefix()
  RETURNS TABLE (number text, code text) LANGUAGE sql AS
$func$
SELECT DISTINCT ON (1) number, code
FROM  (
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 5) = p.code
            AND length(n.number) >= 6  -- incl. noise character
            AND length(p.code) = 5
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 4) = p.code
            AND length(n.number) >= 5
            AND length(p.code) = 4
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 3) = p.code
            AND length(n.number) >= 4
            AND length(p.code) = 3
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 2) = p.code
            AND length(n.number) >= 3
            AND length(p.code) = 2
   UNION ALL 
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(number, 2, 1) = p.code
            AND length(n.number) >= 2
            AND length(p.code) = 1
   ) x
ORDER BY number, code DESC
$func$;

Ligar:

SELECT * FROM f_longest_prefix_sql();

• Tempo de execução total: 17.138 ms (!!!)

Função PL / pgSQL com SQL dinâmico

Essa função plpgsql é muito parecida com a CTE recursiva acima, mas o SQL dinâmico EXECUTEforça a consulta a ser planejada novamente para cada iteração. Agora ele faz uso de todos os índices personalizados.

Além disso, isso funciona para qualquer faixa de tamanho de prefixo. A função usa dois parâmetros para o intervalo, mas eu a preparei com DEFAULTvalores, portanto também funciona sem parâmetros explícitos:

CREATE OR REPLACE FUNCTION f_longest_prefix2(_min int = 1, _max int = 5)
  RETURNS TABLE (number text, code text) LANGUAGE plpgsql AS
$func$
BEGIN
FOR i IN REVERSE _max .. _min LOOP  -- longer matches first
   RETURN QUERY EXECUTE '
   SELECT n.number, p.code
   FROM   num n
   JOIN   prefix p
            ON  substring(n.number, 2, $1) = p.code
            AND length(n.number) >= $1+1  -- incl. noise character
            AND length(p.code) = $1'
   USING i;
END LOOP;
END
$func$;

O passo final não pode ser envolvido facilmente na única função. Ou apenas chame assim:

SELECT DISTINCT ON (1)
       number, code
FROM   f_longest_prefix_prefix2() x
ORDER  BY number, code DESC;

• Tempo de execução total: 27.413 ms

Ou use outra função SQL como wrapper:

CREATE OR REPLACE FUNCTION f_longest_prefix3(_min int = 1, _max int = 5)
  RETURNS TABLE (number text, code text) LANGUAGE sql AS
$func$
SELECT DISTINCT ON (1)
       number, code
FROM   f_longest_prefix_prefix2($1, $2) x
ORDER  BY number, code DESC
$func$;

Ligar:

SELECT * FROM f_longest_prefix3();

• Tempo de execução total: 37.622 ms

Um pouco mais lento devido à sobrecarga de planejamento necessária. Mas mais versátil que o SQL e mais curto para prefixos mais longos.

Uma string S é um prefixo de uma string T, se T estiver entre S e SZ, em que Z é lexicograficamente maior que qualquer outra string (por exemplo, 99999999 com 9's suficientes para exceder o maior número de telefone possível no conjunto de dados ou, às vezes, 0xFF funcionará).

O prefixo comum mais longo para qualquer T também é lexicograficamente máximo, portanto, um simples grupo by e max o encontrará.

select n.number, max(p.code) 
from prefixes p
join numbers n 
on substring(n.number, 2, 255) between p.code and p.code || '99999999'
group by n.number

Se isso for lento, provavelmente é devido às expressões calculadas, então você também pode tentar materializar p.code || '999999' em uma coluna na tabela de códigos com seu próprio índice, etc.