Algorithmus zum Finden des längsten Präfixes

11

Ich habe zwei Tische.

Das erste ist eine Tabelle mit Präfixen

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

An zweiter Stelle stehen Anruflisten mit Telefonnummern

number        time
834353212     10
834321242     20
834312345     30

Ich muss ein Skript schreiben, das das längste Präfix aus den Präfixen für jeden Datensatz findet, und all diese Daten wie folgt in die dritte Tabelle schreiben:

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

Für die Nummer 834353212 müssen wir '8' kürzen und dann den längsten Code aus der Präfixtabelle finden, nämlich 3435.
Wir müssen immer zuerst '8' löschen und das Präfix muss am Anfang stehen.

Ich habe diese Aufgabe vor langer Zeit auf sehr schlechte Weise gelöst. Es war ein schreckliches Perl-Skript, das viele Abfragen für jeden Datensatz ausführt. Dieses Skript:

  1. Nehmen Sie eine Nummer aus der Aufruftabelle und führen Sie eine Teilzeichenfolge von Länge (Nummer) bis 1 => $ Präfix in der Schleife aus

  2. Führen Sie die Abfrage aus: Wählen Sie count (*) aus Präfixen aus, wobei Code wie '$ prefix'

  3. Wenn count> 0 ist, nehmen Sie die ersten Präfixe und schreiben Sie in die Tabelle

Das erste Problem ist die Anzahl der Abfragen call_records * length(number). Das zweite Problem sind LIKEAusdrücke. Ich fürchte, die sind langsam.

Ich habe versucht, das zweite Problem zu lösen, indem ich:

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

Das beschleunigt jede Abfrage, hat aber das Problem im Allgemeinen nicht gelöst.

Ich habe 20k Präfixe und 170k Zahlen jetzt, und meine alte Lösung ist schlecht. Sieht so aus, als ob ich eine neue Lösung ohne Schleifen brauche.

Nur eine Abfrage für jeden Anrufdatensatz oder ähnliches.

Korjavin Ivan
quelle
2
Ich bin mir nicht sicher, ob codein der ersten Tabelle das gleiche Präfix wie später steht. Könnten Sie es bitte klarstellen? Eine Korrektur der Beispieldaten und der gewünschten Ausgabe (damit Sie Ihrem Problem leichter folgen können) ist ebenfalls willkommen.
Dekso
Ja. Du hast recht. Ich habe vergessen, über '8' zu schreiben. Vielen Dank.
Korjavin Ivan
2
Das Präfix muss am Anfang stehen, oder?
Dekso
Ja. Vom zweiten Platz. 8 $ Präfix $ Zahlen
Korjavin Ivan
Was ist die Kardinalität Ihrer Tische? 100.000 Zahlen? Wie viele Präfixe?
Erwin Brandstetter

Antworten:

21

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
5
whoah! Das ist schon die Bearbeitung. Ich wünschte, ich könnte wieder upvoten.
Swasheck
3
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
1
@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
1
Schöne Antwort ... Kennen Sie die Präfixerweiterung des Dimitri ? Könnten Sie das in Ihren Testfallvergleich einbeziehen?
MatheusOl
0

Eine Zeichenfolge S ist ein Präfix einer Zeichenfolge T, wenn T zwischen S und SZ liegt, wobei Z lexikografisch größer ist als jede andere Zeichenfolge (z. B. 99999999 mit genügend 9en, um die längste mögliche Telefonnummer im Datensatz zu überschreiten, oder manchmal funktioniert 0xFF).

Das längste gemeinsame Präfix für ein gegebenes T ist auch lexikographisch maximal, so dass eine einfache Gruppe von und max es findet.

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

Wenn dies langsam ist, liegt dies wahrscheinlich an den berechneten Ausdrücken. Sie können also auch versuchen, p.code || '999999' in einer Spalte in der Codetabelle mit einem eigenen Index usw. zu materialisieren.

KWillets
quelle