Algoritma untuk menemukan awalan terpanjang

Saya mengasumsikan tipe data textuntuk kolom yang relevan.

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

Solusi "Sederhana"

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;

Elemen kunci:

DISTINCT ONadalah ekstensi Postgres dari standar SQL DISTINCT. Temukan penjelasan terperinci untuk teknik kueri yang digunakan dalam jawaban terkait ini di SO .
ORDER BY p.code DESCmemilih pertandingan terlama, karena urutan '1234'setelah '123'(dalam urutan menaik).

Biola SQL Sederhana .

Tanpa indeks, kueri akan berjalan untuk waktu yang sangat lama (tidak menunggu sampai selesai). Untuk mempercepat ini, Anda memerlukan dukungan indeks. Indeks trigram yang Anda sebutkan, yang disediakan oleh modul tambahan pg_trgmadalah kandidat yang baik. Anda harus memilih antara indeks GIN dan GiST. Karakter pertama dari angka-angka hanyalah noise dan dapat dikecualikan dari indeks, menjadikannya sebagai indeks fungsional sebagai tambahan.
Dalam tes saya, indeks GIN trigram fungsional memenangkan perlombaan atas indeks trigram GiST (seperti yang diharapkan):

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

Dbfiddle tingkat lanjut di sini .

Semua hasil tes berasal dari instalasi tes Postgres 9.1 lokal dengan pengaturan yang dikurangi: angka 17k dan kode 2k:

Total runtime: 1719.552 ms (trigram GiST)
Total runtime: 912.329 ms (trigram GIN)

Jauh lebih cepat

Upaya gagal dengan `text_pattern_ops`

Setelah kita mengabaikan karakter noise pertama yang mengganggu, itu turun ke pertandingan pola dasar berlabuh kiri . Oleh karena itu saya mencoba indeks B-tree fungsional dengan kelas operatortext_pattern_ops (dengan asumsi tipe kolom text).

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

Ini berfungsi baik untuk kueri langsung dengan satu istilah pencarian dan membuat indeks trigram terlihat buruk sebagai perbandingan:

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

Total runtime: 3,816 ms (trgm_gin_idx)
Total runtime: 0,147 ms (text_pattern_idx)

Namun , perencana kueri tidak akan mempertimbangkan indeks ini untuk bergabung dengan dua tabel. Saya telah melihat batasan ini sebelumnya. Saya belum memiliki penjelasan yang berarti untuk ini.

Indeks pohon-B sebagian / fungsional

Alternatifnya menggunakan pemeriksaan kesetaraan pada string parsial dengan indeks parsial. Ini dapat digunakan dalam JOIN.

Karena biasanya kami hanya memiliki sejumlah terbatas different lengthsuntuk awalan, kami dapat membangun solusi yang mirip dengan yang disajikan di sini dengan indeks parsial.

Katakanlah, kami memiliki awalan mulai dari 1 hingga 5 karakter. Buat sejumlah indeks fungsional parsial, satu untuk setiap panjang awalan yang berbeda:

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;

Karena ini adalah sebagian indeks, semuanya bersama-sama hampir tidak lebih besar dari satu indeks lengkap.

Tambahkan indeks yang cocok untuk angka (dengan memperhitungkan karakter derau terkemuka):

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;

Meskipun indeks ini hanya memiliki masing-masing substring dan sebagian, masing-masing mencakup sebagian besar atau seluruh tabel. Jadi mereka jauh lebih besar bersama daripada satu indeks total - kecuali untuk angka yang panjang. Dan mereka memaksakan lebih banyak pekerjaan untuk operasi penulisan. Itulah biaya untuk kecepatan luar biasa.

Jika biaya itu terlalu tinggi untuk Anda (kinerja penulisan penting / terlalu banyak operasi penulisan / ruang disk menjadi masalah), Anda dapat melewati indeks ini. Sisanya masih lebih cepat, jika tidak secepat ...

Jika angka tidak pernah lebih pendek dari nkarakter, jatuhkan WHEREklausa yang berlebihan dari beberapa atau semua, dan jatuhkan juga WHEREklausa yang sesuai dari semua kueri berikut.

CTE rekursif

Dengan semua pengaturan sejauh ini saya berharap untuk solusi yang sangat elegan dengan CTE rekursif :

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;

Total runtime: 1045,115 ms

Namun, meskipun kueri ini tidak buruk - kinerjanya sebagus versi sederhana dengan indeks GIN trigram - itu tidak memberikan apa yang saya tuju. Istilah rekursif hanya direncanakan sekali, sehingga tidak dapat menggunakan indeks terbaik. Hanya istilah non-rekursif yang bisa.

UNION ALL

Karena kita berurusan dengan sejumlah kecil rekursi, kita bisa menguraikannya berulang-ulang. Ini memungkinkan rencana yang dioptimalkan untuk masing-masingnya. (Namun, kami kehilangan pengecualian rekursif dari angka yang sudah sukses. Jadi masih ada ruang untuk perbaikan, terutama untuk rentang panjang awalan yang lebih luas)):

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;

Total runtime: 57,578 ms (!!)

Terobosan, akhirnya!

Fungsi SQL

Membungkus ini ke dalam fungsi SQL menghapus overhead perencanaan kueri untuk penggunaan berulang:

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

Panggilan:

SELECT * FROM f_longest_prefix_sql();

Total runtime: 17.138 ms (!!!)

PL / pgSQL berfungsi dengan SQL dinamis

Fungsi plpgsql ini sangat mirip dengan CTE rekursif di atas, tetapi SQL dinamis dengan EXECUTEmemaksa kueri untuk direncanakan ulang untuk setiap iterasi. Sekarang ia menggunakan semua indeks yang disesuaikan.

Selain itu ini berfungsi untuk berbagai rentang panjang awalan. Fungsi ini mengambil dua parameter untuk rentang, tetapi saya menyiapkannya dengan DEFAULTnilai, sehingga berfungsi tanpa parameter eksplisit juga:

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

Langkah terakhir tidak bisa dimasukkan ke dalam satu fungsi dengan mudah. Entah sebut saja seperti ini:

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

Total runtime: 27,413 ms

Atau gunakan fungsi SQL lain sebagai pembungkus:

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

Panggilan:

SELECT * FROM f_longest_prefix3();

Total runtime: 37.622 ms

Sedikit lebih lambat karena overhead perencanaan yang diperlukan. Tetapi lebih fleksibel daripada SQL dan lebih pendek untuk awalan yang lebih panjang.

Erwin Brandstetter
sumber

Saya masih memeriksa, tetapi terlihat luar biasa! Gagasan Anda "terbalik" seperti operator - brilian. Mengapa saya begitu bodoh; (

Korjavin Ivan

whoah! itu cukup edit. Saya berharap saya dapat membenarkan lagi.

swasheck

Saya belajar dari jawaban Anda yang luar biasa lebih dari dua tahun terakhir. 17-30 ms terhadap beberapa jam dalam solusi loop saya? Itu keajaiban.

Korjavin Ivan

@ KorjavinIvan: Yaa, seperti yang didokumentasikan, saya menguji dengan pengaturan awalan 2k / 17k yang berkurang. Tetapi skala ini seharusnya cukup baik dan mesin uji saya adalah server kecil. Jadi, Anda harus tetap berada di bawah satu detik dengan kasus kehidupan nyata Anda.

Erwin Brandstetter

Jawaban yang bagus ... Apakah Anda tahu ekstensi awalan dimitri ? Bisakah Anda memasukkannya dalam perbandingan kasus uji Anda?

MatheusOl