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.
codew pierwszej tabeli jest taki sam jak przedrostek później. Czy możesz to wyjaśnić? A niektóre poprawki przykładowych danych i pożądanych danych wyjściowych (aby łatwiej było śledzić problem) będą również mile widziane.