寻找最长前缀的算法

一尘不染

寻找最长前缀的算法

sql

第一个是带前缀的表

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 脚本，它对每条记录进行大量查询。这个脚本：

从调用表中取一个数字，在循环中做从 length(number) 到 1 => $prefix 的子串

执行查询： `select count(*) from prefixes where code like '$prefix'`

如果计数> 0，则取第一个前缀并写入表
第一个问题是查询计数 - 它是`call_records * length(number).` 第二个问题是LIKE表达。恐怕这些很慢。

我试图通过以下方式解决第二个问题：

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

这加快了每个查询的速度，但并没有解决一般问题。

我现在有20k 个前缀和170k 个号码，我的旧解决方案很糟糕。看起来我需要一些没有循环的新解决方案。

每个通话记录或类似内容只有一个查询。

阅读 174

2021-05-30

共1个答案

一尘不染

我假设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 树索引（假设列类型text）。

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

这对于具有单个搜索词的直接查询非常有用，并且使Trigram索引在比较时看起来很糟糕：

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

总运行时间：3.816 毫秒（trgm_gin_idx）
总运行时间：0.147 毫秒（text_pattern_idx）
然而，查询规划器不会考虑这个索引来连接两个表。我以前见过这个限制。对此，我还没有一个有意义的解释。

部分/功能 B 树索引
对具有部分索引的部分字符串使用相等性检查的替代方法。这可以在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 毫秒
然而，虽然这个查询还不错——它的性能与带有 trigram 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，但是动态 SQL withEXECUTE强制每次迭代都重新规划查询。现在它使用所有定制的索引。

此外，这适用于任何范围的前缀长度。该函数采用范围的两个参数，但我用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 更通用，更长的前缀更短。

2021-05-30