Algoritmo para encontrar el prefijo más largo

Asumo el tipo de datos textpara las columnas relevantes.

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

"Solución simple

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 clave:

DISTINCT ONes una extensión de Postgres del estándar SQL DISTINCT. Encuentre una explicación detallada de la técnica de consulta utilizada en esta respuesta relacionada en SO .
ORDER BY p.code DESCelige la coincidencia más larga, porque se '1234'ordena después '123'(en orden ascendente).

Simple SQL Fiddle .

Sin índice, la consulta se ejecute por un muy largo tiempo (no esperó para ver que se termine). Para hacer esto rápido, necesita soporte de índice. Los índices de trigrama que mencionó, suministrados por el módulo adicional pg_trgmson un buen candidato. Tienes que elegir entre el índice GIN y GiST. El primer carácter de los números es solo ruido y puede excluirse del índice, lo que lo convierte en un índice funcional además.
En mis pruebas, un índice GIN trigram funcional ganó la carrera sobre un índice GiST trigram (como se esperaba):

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

Avanzado dbfiddle aquí .

Todos los resultados de la prueba son de una instalación de prueba local de Postgres 9.1 con una configuración reducida: 17k números y 2k códigos:

Tiempo de ejecución total: 1719.552 ms (trigram GiST)
Tiempo de ejecución total: 912.329 ms (trigram GIN)

Mucho más rápido todavía

Intento fallido con `text_pattern_ops`

Una vez que ignoramos el primer carácter de ruido de distracción, se reduce a la coincidencia de patrón anclada izquierda básica . Por lo tanto, probé un índice de árbol B funcional con la clase de operadortext_pattern_ops (suponiendo el tipo de columna text).

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

Esto funciona excelentemente para consultas directas con un solo término de búsqueda y hace que el índice de trigrama se vea mal en comparación:

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

Tiempo de ejecución total: 3.816 ms (trgm_gin_idx)
Tiempo de ejecución total: 0.147 ms (text_pattern_idx)

Sin embargo , el planificador de consultas no considerará este índice para unir dos tablas. He visto esta limitación antes. Todavía no tengo una explicación significativa para esto.

Índices de árbol B parciales / funcionales

La alternativa es usar verificaciones de igualdad en cadenas parciales con índices parciales. Esto se puede usar en a JOIN.

Como normalmente solo tenemos un número limitado de different lengthsprefijos for, podemos construir una solución similar a la presentada aquí con índices parciales.

Digamos que tenemos prefijos que van de 1 a 5 caracteres. Cree una serie de índices funcionales parciales, uno para cada longitud de prefijo distinta:

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 se trata de índices parciales , todos juntos son apenas más grandes que un solo índice completo.

Agregue índices coincidentes para los números (teniendo en cuenta el carácter de ruido inicial):

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;

Si bien estos índices solo contienen una subcadena cada uno y son parciales, cada uno cubre la mayor parte o la totalidad de la tabla. Por lo tanto, son mucho más grandes juntos que un índice total único, excepto para números largos. E imponen más trabajo para las operaciones de escritura. Ese es el costo de una velocidad increíble.

Si ese costo es demasiado alto para usted (el rendimiento de escritura es importante / demasiadas operaciones de escritura / espacio en disco un problema), puede omitir estos índices. El resto es aún más rápido, si no tan rápido como podría ser ...

Si los números nunca son más cortos que los ncaracteres, elimine las WHEREcláusulas redundantes de algunos o todos, y también elimine la WHEREcláusula correspondiente de todas las consultas siguientes.

CTE recursivo

Con toda la configuración hasta ahora, esperaba una solución muy elegante con un 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;

Tiempo de ejecución total: 1045.115 ms

Sin embargo, aunque esta consulta no es mala, funciona tan bien como la versión simple con un índice GIN de trigrama, no ofrece lo que buscaba. El término recursivo se planifica una sola vez, por lo que no puede usar los mejores índices. Solo el término no recursivo puede.

UNIÓN TODO

Como estamos lidiando con un pequeño número de recursiones, podemos explicarlas de forma iterativa. Esto permite planes optimizados para cada uno de ellos. (Sin embargo, perdemos la exclusión recursiva de números ya exitosos. Por lo tanto, todavía hay margen de mejora, especialmente para un rango más amplio de longitudes de prefijos)):

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;

Tiempo de ejecución total: 57.578 ms (!!)

Un avance, por fin!

Función SQL

Al envolver esto en una función SQL, se elimina la sobrecarga de planificación de consultas 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$;

Llamada:

SELECT * FROM f_longest_prefix_sql();

Tiempo de ejecución total: 17.138 ms (!!!)

Función PL / pgSQL con SQL dinámico

Esta función plpgsql es muy parecida al CTE recursivo anterior, pero el SQL dinámico EXECUTEobliga a que la consulta se vuelva a planificar para cada iteración. Ahora hace uso de todos los índices personalizados.

Además, esto funciona para cualquier rango de longitudes de prefijo. La función toma dos parámetros para el rango, pero la preparé con DEFAULTvalores, por lo que también funciona sin 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$;

El paso final no se puede incluir fácilmente en una función. O simplemente llámalo así:

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

Tiempo de ejecución total: 27.413 ms

O use otra función SQL como contenedor:

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$;

Llamada:

SELECT * FROM f_longest_prefix3();

Tiempo de ejecución total: 37.622 ms

Un poco más lento debido a la sobrecarga de planificación requerida. Pero más versátil que SQL y más corto para prefijos más largos.

Erwin Brandstetter
fuente

Todavía estoy revisando, ¡pero se ve excelente! Su idea "revertir" como operador - brillante. Por qué era tan estúpido; (

Korjavin Ivan

whoah! Esa es toda la edición. Desearía poder votar de nuevo.

swasheck

Aprendo de tu asombrosa respuesta más que en los últimos dos años. 17-30 ms contra varias horas en mi solución de bucle? Eso es una magia

Korjavin Ivan

@KorjavinIvan: Bueno, como documentado, probé con una configuración reducida de 2k prefijos / 17k números. Pero esto debería escalar bastante bien y mi máquina de prueba era un servidor pequeño. Por lo tanto, debe permanecer mucho menos de un segundo con su caso de la vida real.

Erwin Brandstetter

Buena respuesta ... ¿Conoces la extensión del prefijo dimitri ? ¿Podría incluir eso en su comparación de casos de prueba?

MatheusOl