Algorithmus zum Finden des längsten Präfixes

Ich gehe von einem Datentyp textfür die relevanten Spalten aus.

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

"Einfache" Lösung

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;

Schlüsselelemente:

DISTINCT ONist eine Postgres-Erweiterung des SQL-Standards DISTINCT. Eine ausführliche Erklärung für die verwendete Abfragetechnik finden Sie in dieser Antwort auf SO .
ORDER BY p.code DESCwählt die längste Übereinstimmung aus, da '1234'nach '123'(in aufsteigender Reihenfolge) sortiert wird .

Einfache SQL-Geige .

Ohne Index würde die Abfrage sehr lange ausgeführt (ich habe nicht darauf gewartet, dass sie beendet wird). Um dies schnell zu machen, benötigen Sie Indexunterstützung. Die von Ihnen erwähnten Trigrammindizes, die vom Zusatzmodul bereitgestellt werden, pg_trgmsind ein guter Kandidat. Sie müssen zwischen GIN und GiST Index wählen. Das erste Zeichen der Zahlen ist nur Rauschen und kann aus dem Index ausgeschlossen werden, wodurch es zusätzlich zu einem Funktionsindex wird.
In meinen Tests hat ein funktionaler Trigramm-GIN-Index das Rennen über einen Trigramm-GiST-Index gewonnen (wie erwartet):

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

Fortgeschrittene dbfiddle hier .

Alle Testergebnisse stammen aus einer lokalen Postgres 9.1-Testinstallation mit einem reduzierten Setup: 17.000 Nummern und 2.000 Codes:

Gesamtlaufzeit: 1719,552 ms (Trigramm GiST)
Gesamtlaufzeit: 912,329 ms (Trigramm GIN)

Noch viel schneller

Fehlgeschlagener Versuch mit `text_pattern_ops`

Sobald wir das ablenkende erste Rauschzeichen ignorieren, kommt es auf die grundlegende links verankerte Musterübereinstimmung an. Deshalb habe ich einen funktionalen B-Tree-Index mit der Operator-Klassetext_pattern_ops versucht (unter der Annahme eines Spaltentyps text).

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

Dies funktioniert hervorragend bei direkten Abfragen mit einem einzelnen Suchbegriff und lässt den Trigrammindex im Vergleich schlecht aussehen:

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

Gesamtlaufzeit: 3.816 ms (trgm_gin_idx)
Gesamtlaufzeit: 0,147 ms (text_pattern_idx)

Der Abfrageplaner berücksichtigt diesen Index jedoch nicht für die Verknüpfung zweier Tabellen. Ich habe diese Einschränkung schon einmal gesehen. Ich habe noch keine aussagekräftige Erklärung dafür.

Partielle / funktionale B-Baum-Indizes

Die Alternative ist die Verwendung von Gleichheitsprüfungen für Teilzeichenfolgen mit Teilindizes. Dies kann in einem verwendet werden JOIN.

Da wir normalerweise nur eine begrenzte Anzahl von different lengthsPräfixen haben, können wir eine ähnliche Lösung wie die hier vorgestellte mit Teilindizes erstellen.

Angenommen, wir haben Präfixe im Bereich von 1 und 5 Zeichen. Erstellen Sie eine Reihe von Teilfunktionsindizes, einen für jede bestimmte Präfixlänge:

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;

Da diese Teilindizes, sind sie alle zusammen kaum größer als ein einziger vollständiger Index.

Fügen Sie übereinstimmende Indizes für Zahlen hinzu (unter Berücksichtigung des führenden Rauschzeichens):

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;

Während diese Indizes jeweils nur einen Teilstring enthalten und teilweise sind, deckt jeder den größten Teil oder die gesamte Tabelle ab. Sie sind also zusammen viel größer als ein einzelner Gesamtindex - mit Ausnahme langer Zahlen. Und sie erfordern mehr Arbeit für Schreibvorgänge. Das ist das Kosten für erstaunliche Geschwindigkeit.

Wenn diese Kosten für Sie zu hoch sind (Schreibleistung ist wichtig / zu viele Schreibvorgänge / Speicherplatz ein Problem), können Sie diese Indizes überspringen. Der Rest ist noch schneller, wenn auch nicht ganz so schnell wie es sein könnte ...

Wenn Zahlen niemals kürzer als nZeichen sind, löschen Sie redundante WHEREKlauseln von einigen oder allen und löschen Sie auch die entsprechendenWHERE Klausel aus allen folgenden Abfragen.

Rekursiver CTE

Bei all dem Setup hoffte ich auf eine sehr elegante Lösung mit einem rekursiven CTE :

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;

Gesamtlaufzeit: 1045,115 ms

Obwohl diese Abfrage nicht schlecht ist - sie funktioniert ungefähr so gut wie die einfache Version mit einem Trigramm-GIN-Index - liefert sie nicht das, was ich mir vorgenommen habe. Der rekursive Term ist nur einmal geplant, sodass nicht die besten Indizes verwendet werden können. Nur der nicht rekursive Term kann.

UNION ALL

Da es sich um eine kleine Anzahl von Rekursionen handelt, können wir sie einfach iterativ formulieren. Dies ermöglicht optimierte Pläne für jeden von ihnen. (Wir verlieren jedoch den rekursiven Ausschluss bereits erfolgreicher Zahlen. Es gibt also noch Verbesserungspotenzial, insbesondere für einen größeren Bereich von Präfixlängen.)

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;

Gesamtlaufzeit: 57.578 ms (!!)

Endlich ein Durchbruch!

SQL-Funktion

Wenn Sie dies in eine SQL-Funktion packen, entfällt der Aufwand für die Abfrageplanung für die wiederholte Verwendung:

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

Anruf:

SELECT * FROM f_longest_prefix_sql();

Gesamtlaufzeit: 17.138 ms (!!!)

PL / pgSQL-Funktion mit dynamischem SQL

Diese plpgsql-Funktion ähnelt dem obigen rekursiven CTE, aber das dynamische SQL EXECUTEerzwingt, dass die Abfrage für jede Iteration neu geplant wird. Jetzt werden alle maßgeschneiderten Indizes verwendet.

Zusätzlich funktioniert dies für jeden Bereich von Präfixlängen. Die Funktion verwendet zwei Parameter für den Bereich, aber ich habe sie mit DEFAULTWerten vorbereitet , sodass sie auch ohne explizite Parameter funktioniert:

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

Der letzte Schritt kann nicht einfach in die eine Funktion eingebunden werden. Entweder rufen Sie es wie folgt aus :

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

Gesamtlaufzeit: 27.413 ms

Oder verwenden Sie eine andere SQL-Funktion als 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$;

Anruf:

SELECT * FROM f_longest_prefix3();

Gesamtlaufzeit: 37.622 ms

Etwas langsamer aufgrund des erforderlichen Planungsaufwands. Aber vielseitiger als SQL und kürzer für längere Präfixe.

Erwin Brandstetter
quelle

Ich überprüfe immer noch, sieht aber ausgezeichnet aus! Ihre Idee "umgekehrt" wie Operator - genial. Warum ich so dumm war; (

Korjavin Ivan

whoah! Das ist schon die Bearbeitung. Ich wünschte, ich könnte wieder upvoten.

Swasheck

Ich lerne aus Ihrer erstaunlichen Antwort mehr als in den letzten zwei Jahren. 17-30 ms gegen mehrere Stunden in meiner Schleifenlösung? Das ist eine Magie.

Korjavin Ivan

@KorjavinIvan: Nun, wie dokumentiert, habe ich mit einem reduzierten Setup von 2k Präfixen / 17k Zahlen getestet. Aber das sollte ziemlich gut skalieren und meine Testmaschine war ein winziger Server. Sie sollten also mit Ihrem realen Fall weit unter einer Sekunde bleiben.

Erwin Brandstetter

Schöne Antwort ... Kennen Sie die Präfixerweiterung des Dimitri ? Könnten Sie das in Ihren Testfallvergleich einbeziehen?

MatheusOl