Algorytm znajdowania najdłuższego prefiksu

Zakładam typ danych textdla odpowiednich kolumn.

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

„Proste” rozwiązanie

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;

Kluczowe elementy:

DISTINCT ONjest rozszerzeniem standardu SQL Postgres DISTINCT. Znajdź szczegółowe wyjaśnienie zastosowanej techniki zapytań w tej pokrewnej odpowiedzi na SO .
ORDER BY p.code DESCwybiera najdłuższe dopasowanie, ponieważ '1234'sortuje po '123'(w kolejności rosnącej).

Proste skrzypce SQL .

Bez indeksu zapytanie działałoby przez bardzo długi czas (nie czekało, aż zakończy się). Aby zrobić to szybko, potrzebujesz obsługi indeksu. Wspomniane indeksy trygramu dostarczone przez moduł dodatkowy pg_trgmsą dobrym kandydatem. Musisz wybrać między indeksem GIN i GiST. Pierwszy znak liczb to po prostu szum i można go wykluczyć z indeksu, co czyni go dodatkowo indeksem funkcjonalnym.
W moich testach funkcjonalny indeks GIN trygramu wygrał wyścig z indeksem GiST trigramu (zgodnie z oczekiwaniami):

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

Zaawansowane dbfiddle tutaj .

Wszystkie wyniki testów pochodzą z lokalnej instalacji testowej Postgres 9.1 ze zmniejszoną konfiguracją: 17 tys. Numerów i 2 tys. Kodów:

Całkowity czas działania: 1719,552 ms (trigram GiST)
Całkowity czas działania: 912,329 ms (trygram GIN)

Jeszcze szybciej

Nieudana próba z `text_pattern_ops`

Kiedy zignorujemy rozpraszającą uwagę pierwszą postać hałasu, sprowadza się ona do podstawowego dopasowania zakotwiczonego w lewo wzoru. Dlatego próbowałem funkcjonalnego indeksu B-drzewa z klasą operatoratext_pattern_ops (zakładając typ kolumny text).

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

Działa to doskonale w przypadku bezpośrednich zapytań z jednym wyszukiwanym terminem i sprawia, że indeks trigram wygląda źle w porównaniu:

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

Całkowity czas działania: 3,816 ms (trgm_gin_idx)
Całkowity czas działania: 0,147 ms (text_pattern_idx)

Jednak planista zapytań nie uwzględni tego indeksu przy łączeniu dwóch tabel. Widziałem to ograniczenie wcześniej. Nie mam jeszcze sensownego wyjaśnienia tego.

Częściowe / funkcjonalne indeksy B-drzewa

Alternatywą jest użycie kontroli równości częściowych ciągów z częściowymi indeksami. To może być używany w JOIN.

Ponieważ zazwyczaj mamy tylko ograniczoną liczbę different lengthsprefiksów, możemy zbudować rozwiązanie podobne do prezentowanego tutaj z częściowymi indeksami.

Powiedzmy, że mamy prefiksy od 1 do 5 znaków. Utwórz kilka częściowych indeksów funkcjonalnych, po jednym dla każdej odrębnej długości prefiksu:

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;

Ponieważ są to indeksy częściowe , wszystkie razem są niewiele większe niż pojedynczy pełny indeks.

Dodaj pasujące indeksy dla liczb (biorąc pod uwagę wiodący znak szumu):

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;

Chociaż te indeksy zawierają tylko podciąg i są częściowe, każdy obejmuje większość lub całość tabeli. Są więc znacznie większe niż pojedynczy indeks całkowity - z wyjątkiem długich liczb. I nakładają więcej pracy na operacje zapisu. To koszt niesamowitej prędkości.

Jeśli ten koszt jest dla Ciebie zbyt wysoki (ważna jest wydajność zapisu / zbyt wiele operacji zapisu / problem z miejscem na dysku), możesz pominąć te indeksy. Reszta jest jeszcze szybsza, jeśli nie tak szybka, jak mogłaby być ...

Jeśli liczby nigdy nie są krótsze niż nznaki, usuń zbędne WHEREklauzule z niektórych lub wszystkich, a także usuń odpowiednią WHEREklauzulę z wszystkich kolejnych zapytań.

Rekurencyjne CTE

Przy całej dotychczasowej konfiguracji liczyłem na bardzo eleganckie rozwiązanie z rekurencyjnym 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;

Całkowity czas działania: 1045,115 ms

Jednak chociaż to zapytanie nie jest złe - działa tak dobrze, jak prosta wersja z indeksem GIN trygramu - nie zapewnia tego, do czego dążyłem. Termin rekurencyjny jest planowany tylko raz, więc nie można użyć najlepszych indeksów. Tylko termin nierekurencyjny może.

UNION ALL

Ponieważ mamy do czynienia z niewielką liczbą rekurencji, możemy po prostu przeliterować je iteracyjnie. Pozwala to zoptymalizować plany dla każdego z nich. (Tracimy jednak rekursywne wykluczanie już udanych liczb. Więc jest jeszcze miejsce na ulepszenia, szczególnie w przypadku szerszego zakresu długości prefiksów)):

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;

Całkowity czas pracy: 57,578 ms (!!)

Wreszcie przełom!

Funkcja SQL

Zawijanie tego w funkcję SQL usuwa narzut związany z planowaniem zapytań do ponownego użycia:

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

Połączenie:

SELECT * FROM f_longest_prefix_sql();

Całkowity czas działania: 17,138 ms (!!!)

Funkcja PL / pgSQL z dynamicznym SQL

Ta funkcja plpgsql jest podobna do rekurencyjnej CTE powyżej, ale dynamiczny SQL EXECUTEwymusza ponowne zaplanowanie zapytania dla każdej iteracji. Teraz wykorzystuje wszystkie dostosowane indeksy.

Dodatkowo działa to dla dowolnego zakresu długości prefiksów. Funkcja przyjmuje dwa parametry dla zakresu, ale przygotowałem ją z DEFAULTwartościami, więc działa również bez wyraźnych parametrów:

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

Ostatni krok nie może być łatwo opakowany w jedną funkcję. Albo nazwij to tak:

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

Całkowity czas działania: 27,1313 ms

Lub użyj innej funkcji SQL jako opakowania:

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

Połączenie:

SELECT * FROM f_longest_prefix3();

Całkowity czas działania: 37,622 ms

Trochę wolniej z powodu wymaganego narzutu związanego z planowaniem. Ale bardziej wszechstronny niż SQL i krótszy dla dłuższych prefiksów.

Erwin Brandstetter
źródło

Nadal sprawdzam, ale wygląda świetnie! Twój pomysł „odwróć” jak operator - genialny. Dlaczego byłem taki głupi; (

Korjavin Ivan

Łał! to całkiem edycja. chciałbym móc ponownie głosować.

swasheck

Uczę się z twojej niesamowitej odpowiedzi więcej niż przez ostatnie dwa lata. 17-30 ms w stosunku do kilku godzin w moim rozwiązaniu pętli? To magia.

Korjavin Ivan

@KorjavinIvan: Cóż, jak udokumentowano, testowałem ze zmniejszoną konfiguracją 2k prefiksów / 17k liczb. Ale to powinno się całkiem dobrze skalować, a moja maszyna testowa była małym serwerem. Więc powinieneś pozostać znacznie poniżej sekundy ze swoim prawdziwym przypadkiem.

Erwin Brandstetter

Dobra odpowiedź ... Czy znasz rozszerzenie prefiksu dimitri ? Czy możesz to uwzględnić przy porównywaniu przypadków testowych?

MatheusOl