Postgresql

查找最長前綴的算法

  • June 23, 2020

我有兩張桌子。

第一個是帶有前綴的表

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

其次是帶有電話號碼的通話記錄

number        time
834353212     10
834321242     20
834312345     30

我需要編寫一個腳本，從每條記錄的前綴中找到最長的前綴，並將所有這些數據寫入第三個表，如下所示：

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

對於數字 834353212，我們必須修剪“8”，然後從前綴表中找到最長的程式碼，即 3435。

我們必須始終刪除第一個“8”並且前綴必須在開頭。

我很久以前就以非常糟糕的方式解決了這個任務。它是可怕的 perl 腳本，它對每條記錄進行大量查詢。這個腳本：

  1. 從呼叫表中取一個數字，在循環中執行從長度（數字）到 1 => $prefix 的子字元串
  2. 執行查詢： select count(*) from prefixes where code like ‘$prefix’
  3. 如果 count>0 則取第一個前綴並寫入表

第一個問題是查詢計數 - 它是call_records * length(number). 第二個問題是LIKE表達式。恐怕那些很慢。

我試圖通過以下方式解決第二個問題：

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

這加快了每個查詢，但一般沒有解決問題。

我現在有20k前綴和170k號碼，而我的舊解決方案很糟糕。看起來我需要一些沒有循環的新解決方案。

每個通話記錄或類似的東西只有一個查詢。

我假設text相關列的數據類型。

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

“簡單”的解決方案

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;

關鍵要素：

DISTINCT ON是 SQL 標準的 Postgres 擴展DISTINCT。在有關 SO 的相關答案中找到所用查詢技術的詳細說明。

ORDER BY p.code DESC選擇最長的匹配，因為'1234'排序後'123'（按升序）。

簡單的SQL 小提琴。

如果沒有索引，查詢會執行很長時間（迫不及待地看到它完成）。為了加快速度，您需要索引支持。您提到的由附加模組提供的三元組索引pg_trgm是一個很好的候選者。您必須在 GIN 和 GiST 索引之間進行選擇。數字的第一個字元只是雜訊，可以從索引中排除，使其成為一個功能索引。

在我的測試中，功能性三元組 GIN 索引贏得了三元組 GiST 索引的比賽（如預期的那樣）：

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

高級dbfiddle在這裡。

所有測試結果均來自本地 Postgres 9.1 測試安裝，設置減少：17k 個數字和 2k 個程式碼：

  • 總執行時間：1719.552 毫秒（trigram GiST）
  • 總執行時間：912.329 毫秒（trigram GIN）

快得多

嘗試失敗text_pattern_ops

一旦我們忽略了令人分心的第一個雜訊字元，它就歸結為基本的左錨模式匹配。因此，我嘗試了一個帶有 操作符類text_pattern_ops的功能 B-tree 索引（假設為 column type text）。

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

這對於使用單個搜尋詞的直接查詢非常有效，並且相比之下三元組索引看起來很糟糕：

SELECT * FROM num WHERE right(number, -1) LIKE '2345%'
  • 總執行時間：3.816 毫秒（trgm_gin_idx）
  • 總執行時間：0.147 毫秒（text_pattern_idx）

但是，查詢規劃器不會考慮使用此索引來連接兩個表。我以前見過這個限制。我對此還沒有一個有意義的解釋。

部分/功能 B-tree 索引

另一種方法是對具有部分索引的部分字元串使用相等檢查。這可以用於JOIN.

由於我們通常只有有限數量的different lengthsfor 前綴，因此我們可以建構一個類似於此處介紹的帶有部分索引的解決方案。

比如說，我們有1到5 個字元的前綴。創建多個部分功能索引，每個不同的前綴長度一個：

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;

由於這些是部分索引，因此它們加在一起幾乎不比單個完整索引大。

為數字添加匹配索引（考慮前導雜訊字元）：

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;

雖然這些索引每個都只包含一個子字元串並且是部分的，但每個索引都覆蓋了表的大部分或全部。所以它們加起來比一個單一的總索引要大得多——除了長數字。他們為寫操作強加了更多的工作。這就是驚人速度的代價。

如果該成本對您來說太高（寫入性能很重要/寫入操作過多/磁碟空間問題），您可以跳過這些索引。其餘的仍然更快，如果不是盡可能快的話……

如果數字永遠不會比n字元短，則從部分或全部中刪除多餘WHERE的子句，並WHERE從所有後續查詢中刪除相應的子句。

遞歸 CTE

到目前為止，我希望通過遞歸 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;
  • 總執行時間：1045.115 毫秒

然而，雖然這個查詢還不錯——它的性能與帶有三元組 GIN 索引的簡單版本差不多——但它並沒有達到我的目標。遞歸項只計劃一次，因此不能使用最佳索引。只有非遞歸項可以。

聯合所有

由於我們正在處理少量遞歸，我們可以迭代地拼出它們。這允許為每個人優化計劃。（不過，我們失去了對已經成功的數字的遞歸排除。因此仍有一些改進的空間，尤其是對於更廣泛的前綴長度）：

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;
  • 總執行時間：57.578 毫秒（！！）

終於有突破了！

SQL 函式

將其包裝到 SQL 函式中可以消除重複使用的查詢計劃成本：

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

稱呼：

SELECT * FROM f_longest_prefix_sql();
  • 總執行時間：17.138 毫秒（！！！）

帶有動態 SQL 的 PL/pgSQL 函式

這個 plpgsql 函式很像上面的遞歸 CTE，但是動態 SQLEXECUTE會強制每次迭代都重新規劃查詢。現在它利用了所有定制的索引。

此外，這適用於任何範圍的前綴長度。該函式採用兩個參數作為範圍，但我用DEFAULT值準備了它，因此它也可以在沒有顯式參數的情況下工作：

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

最後一步不能輕易地包裝到一個函式中。 要麼這樣稱呼它：

SELECT DISTINCT ON (1)
      number, code
FROM   f_longest_prefix_prefix2() x
ORDER  BY number, code DESC;
  • 總執行時間：27.413 毫秒

或者使用另一個 SQL 函式作為包裝器：

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

稱呼：

SELECT * FROM f_longest_prefix3();
  • 總執行時間：37.622 毫秒

由於所需的計劃成本，速度有點慢。但比 SQL 更通用，更長的前綴更短。

引用自：https://dba.stackexchange.com/questions/43415

相關問答

Postgresql

為讀取性能配置 PostgreSQL

  • January 29, 2021
檢視問答
Postgresql

應用一長串 LIKE 模式的最佳方法？

  • August 18, 2020
檢視問答
Postgresql

使用臨時表的高效 PostgreSQL 更新

  • December 13, 2019
檢視問答
Postgresql

由於行估計非常不准確，全文搜尋緩慢

  • March 11, 2018
檢視問答
Postgresql

> 30 秒慢查詢

  • February 14, 2017
檢視問答
Postgresql

如何联合 2 個子查詢以減少從繁瑣的表中檢索數據？

  • January 13, 2016
檢視問答