Algorithme pour trouver le préfixe le plus long

Je suppose que le type de données textpour les colonnes pertinentes.

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

Solution "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;

Éléments clé:

DISTINCT ONest une extension Postgres du standard SQL DISTINCT. Trouvez une explication détaillée de la technique de requête utilisée dans cette réponse connexe sur SO .
ORDER BY p.code DESCsélectionne la correspondance la plus longue, car '1234'trie après '123'(dans l'ordre croissant).

Simple SQL Fiddle .

Sans index, la requête s'exécuterait très longtemps (n'attendait pas pour la voir se terminer). Pour rendre cela rapide, vous avez besoin d'un support d'index. Les index de trigrammes que vous avez mentionnés, fournis par le module supplémentaire, pg_trgmsont un bon candidat. Vous devez choisir entre l'index GIN et GiST. Le premier caractère des nombres n'est que du bruit et peut être exclu de l'index, ce qui en fait un index fonctionnel en plus.
Lors de mes tests, un index trigramme GIN fonctionnel a remporté la course sur un index trigramme GiST (comme prévu):

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

Dbfiddle avancé ici .

Tous les résultats des tests proviennent d'une installation de test Postgres 9.1 locale avec une configuration réduite: 17k numéros et 2k codes:

Durée d'exécution totale: 1719,552 ms (trigramme GiST)
Durée d' exécution totale: 912,329 ms (trigramme GIN)

Beaucoup plus rapide encore

Échec de la tentative avec `text_pattern_ops`

Une fois que nous ignorons le premier caractère de bruit distrayant, cela revient à une correspondance de modèle ancrée à gauche de base . J'ai donc essayé un index fonctionnel B-tree avec la classe d'opérateurtext_pattern_ops (en supposant le type de colonne text).

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

Cela fonctionne parfaitement pour les requêtes directes avec un seul terme de recherche et rend l'index du trigramme mauvais en comparaison:

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

Durée d'exécution totale: 3,816 ms (trgm_gin_idx)
Durée d' exécution totale: 0,147 ms (text_pattern_idx)

Cependant , le planificateur de requêtes ne tiendra pas compte de cet index pour joindre deux tables. J'ai déjà vu cette limitation. Je n'ai pas encore d'explication valable à cela.

Index B-tree partiels / fonctionnels

L'alternative consiste à utiliser des contrôles d'égalité sur des chaînes partielles avec des index partiels. Cela peut être utilisé dans un fichier JOIN.

Comme nous n'avons généralement qu'un nombre limité de different lengthspréfixes for, nous pouvons créer une solution similaire à celle présentée ici avec des index partiels.

Disons, nous avons des préfixes allant de 1 à 5 caractères. Créez un certain nombre d'index fonctionnels partiels, un pour chaque longueur de préfixe distinct:

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;

Puisqu'il s'agit d' index partiels , tous ensemble sont à peine plus grands qu'un seul index complet.

Ajoutez des index correspondants pour les nombres (en tenant compte du premier caractère de bruit):

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;

Bien que ces index ne contiennent chacun qu'une sous-chaîne et soient partiels, chacun couvre la plupart ou la totalité de la table. Ils sont donc beaucoup plus grands ensemble qu'un seul indice total - à l'exception des nombres longs. Et ils imposent plus de travail pour les opérations d'écriture. Voilà le coût d'une vitesse incroyable.

Si ce coût est trop élevé pour vous (les performances d'écriture sont importantes / trop d'opérations d'écriture / d'espace disque sont un problème), vous pouvez ignorer ces index. Le reste est encore plus rapide, sinon aussi rapide qu'il pourrait l'être ...

Si les nombres ne sont jamais plus courts que les ncaractères, supprimez les WHEREclauses redondantes de tout ou partie, et supprimez également la WHEREclause correspondante de toutes les requêtes suivantes.

CTE récursif

Avec toute la configuration jusqu'à présent, j'espérais une solution très élégante avec un CTE récursif :

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;

Durée totale: 1045.115 ms

Cependant, bien que cette requête ne soit pas mauvaise - elle fonctionne à peu près aussi bien que la version simple avec un index GIN trigram - elle ne fournit pas ce que je visais. Le terme récursif n'est prévu qu'une seule fois, il ne peut donc pas utiliser les meilleurs index. Seul le terme non récursif peut.

UNION ALL

Comme nous avons affaire à un petit nombre de récursions, nous pouvons simplement les énoncer de manière itérative. Cela permet des plans optimisés pour chacun d'eux. (Nous perdons cependant l'exclusion récursive des numéros déjà réussis. Il y a donc encore une marge d'amélioration, en particulier pour une plus large gamme de longueurs de préfixe)):

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;

Durée d' exécution totale: 57,578 ms (!!)

Une percée enfin!

Fonction SQL

L'encapsulation dans une fonction SQL supprime la surcharge de planification des requêtes pour une utilisation répétée:

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

Appel:

SELECT * FROM f_longest_prefix_sql();

Durée d' exécution totale: 17,138 ms (!!!)

Fonction PL / pgSQL avec SQL dynamique

Cette fonction plpgsql ressemble beaucoup au CTE récursif ci-dessus, mais le SQL dynamique avec EXECUTEoblige à replanifier la requête pour chaque itération. Maintenant, il utilise tous les index personnalisés.

De plus, cela fonctionne pour n'importe quelle plage de longueurs de préfixe. La fonction prend deux paramètres pour la plage, mais je l'ai préparée avec des DEFAULTvaleurs, elle fonctionne donc aussi sans paramètres explicites:

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

La dernière étape ne peut pas être facilement intégrée à une seule fonction. Soit il suffit de l'appeler ainsi:

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

Durée totale: 27,413 ms

Ou utilisez une autre fonction SQL comme 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$;

Appel:

SELECT * FROM f_longest_prefix3();

Durée totale: 37,622 ms

Un peu plus lent en raison des frais généraux de planification requis. Mais plus polyvalent que SQL et plus court pour les préfixes plus longs.

Erwin Brandstetter
la source

Je vérifie toujours, mais semble excellent! Votre idée "inverse" comme opérateur - génial. Pourquoi j'étais si stupide; (

Korjavin Ivan

whoah! c'est tout à fait le montage. J'aimerais pouvoir voter à nouveau.

swasheck

J'apprends de votre réponse étonnante plus que depuis deux ans. 17-30 ms contre plusieurs heures dans ma solution de boucle? C'est une magie.

Korjavin Ivan

@KorjavinIvan: Eh bien, comme documenté, j'ai testé avec une configuration réduite de 2k préfixes / 17k nombres. Mais cela devrait assez bien évoluer et ma machine de test était un petit serveur. Donc, vous devriez rester bien moins d'une seconde avec votre cas réel.

Erwin Brandstetter

Bonne réponse ... Connaissez-vous l' extension du préfixe de dimitri ? Pourriez-vous inclure cela dans votre comparaison de cas de test?

MatheusOl