寻找最长前缀的算法

Question

我有两张表。 第一张是一个带有前缀的表。

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. 从通话表中获取一个号码，在循环中将其截取为长度(number)到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个号码，我的旧解决方案很糟糕。看起来我需要一些新的解决方案，而不是使用循环。 每个通话记录只需要一个查询或类似的操作。

- Korjavin Ivan

---

我不太确定第一个表格中的“code”是否与后面的前缀相同。你能否请澄清一下？同时，如果你能修正一下示例数据和期望输出（以便更容易理解你的问题），那将非常受欢迎。 - dezso

是的，你说得对。我忘记写关于“8”的事情了。谢谢你。 - Korjavin Ivan

前缀必须放在句子开头，对吗？ - dezso

是的。从第二名开始。8$prefix$numbers - Korjavin Ivan

你的表的基数是多少？10万个数字？有多少个前缀？ - Erwin Brandstetter

20k个前缀，约170k个数字。 - Korjavin Ivan

我觉得我有一种更快的东西。你的设置中最短和最长的前缀是什么？ - Erwin Brandstetter

最短的是1，最长的是10。但是超过50%的前缀长度在5-8之间。 - Korjavin Ivan

Answer 1

假设相关列的数据类型为text。

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

“简单”解决方案

SELECT DISTINCT ON (n.number)
       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标准DISTINCT的Postgres扩展。参见：

• 在每个GROUP BY组中选择第一行？。

ORDER BY p.code DESC选择最长匹配，因为'1234'在升序排序中位于'123'之后。

db<>fiddle 这里
_{旧版sqlfiddle}

没有索引，这个查询运行时间非常长（没等到它完成就放弃了）。我们需要索引支持。三元组索引（由附加模块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（假设列类型为text）的函数B-tree索引。

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）

然而，查询规划器在连接两个表时不会考虑这个索引（在LATERAL连接存在之前）。

部分/功能B树索引

另一种方法是使用部分字符串的等值检查和部分索引。这可以在JOIN中使用。

由于我们通常只有有限数量的不同长度的前缀，我们可以构建一个类似于这里介绍的部分索引的解决方案：

• 空间索引能帮助"范围-排序-限制"查询吗

假设我们的前缀长度从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索引的简单版本一样好 - 但它没有达到我想要的效果。递归项只计划执行一次，所以它不能使用最佳索引。只有非递归项可以。

UNION ALL

由于我们处理的是少量递归，我们可以迭代地将它们列出来。这样可以为每个递归项优化计划。（尽管我们失去了对已成功数字的递归排除，但对于更广泛的前缀长度仍然有改进的空间）：

SELECT DISTINCT ON (number)
       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 (number)
       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 函数

这个 PL/pgSQL 函数与上面的递归 CTE 非常相似，但是使用 EXECUTE 的动态 SQL 强制查询在每次迭代时重新计划。现在它利用了所有定制的索引。

此外，它适用于任何范围的前缀长度。该函数接受两个参数作为范围，但我已经准备好了带有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 (number)
       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 (number)
       number, code
FROM   f_longest_prefix_prefix2($1, $2) x
ORDER  BY number, code DESC
$func$;

电话：

SELECT * FROM f_longest_prefix3();

• 总运行时间：37.622 毫秒

由于所需的规划开销，稍微慢一些。但比 SQL 更灵活，对于较长的前缀更短。

- Erwin Brandstetter

---

我还在检查，但看起来非常棒！你的“反向”操作符的想法真是太聪明了。为什么我之前那么愚蠢呢；( - Korjavin Ivan

我刚刚完成了检查。没问题。这比我预期的要好得多。谢谢！太棒了！ - Korjavin Ivan

哇！这次编辑太棒了。我希望我能再次点赞。 - swasheck

我从你的精彩回答中学到了比过去两年还多的知识。17-30毫秒对比我之前的循环解决方案需要几个小时？这简直是魔法。 - Korjavin Ivan

@KorjavinIvan：嗯，根据记录，我使用了一个较小的设置，包括2k个前缀和17k个号码进行了测试。但是这应该可以很好地扩展，并且我的测试机器只是一台小型服务器。所以在你的实际情况下，你应该能够在不到一秒的时间内完成。 - Erwin Brandstetter

好答案... 你知道dimitri的前缀扩展吗？你能在你的测试用例比较中包含它吗？ - MatheusOl

Answer 2

一个字符串S是字符串T的前缀，当且仅当T位于S和SZ之间，其中Z在字典顺序上大于任何其他字符串（例如99999999，有足够多的9超过数据集中可能的最长电话号码，或者有时0xFF也可以）。 对于任何给定的T，最长公共前缀也是字典顺序上的最大值，因此简单的分组和最大值操作就能找到它。

select n.number, max(p.code) 
from prefixes p
join numbers n 
on substring(n.number, 2, 255) between p.code and p.code || '99999999'
group by n.number

如果这个速度慢，很可能是由于计算表达式的原因，所以你也可以尝试将 p.code ||'999999' 实例化为代码表中的一个列，并给它自己建立索引等。

- KWillets

Answer 3

尽管Erwin一如既往地给出了令人惊叹的高效答案，但它似乎依赖于需要匹配的前缀字符数量，这可能难以维护；在电信行业中，e164前缀实际上是任意的，并且可能非常长，特别是如果你要处理一个已经有着很长国家代码的国家的地理前缀。

还有一种性能较差但复杂度较低的解决方案，类似于KWillets建议的方法，仍然使用索引，但效率不如之前：

-- Create a table of prefixes and populate it with test data.
create table prefix (code text not null);
insert into prefix select generate_series::text from generate_series(1, 20000);

-- Index on prefix table is obviously very important.
create index prefix_idx on prefix (code);

-- Create 170K random phone numbers.
create table number (e164 text);
insert into number select round(random() * 10000000000) from generate_series(1, 170000);

create or replace function find_prefix(_e164 text) returns text stable language sql as $$
  select max(code) from prefix where code <= _e164
$$;

-- Perform the query
explain analyse select e164, find_prefix(e164) from number;

这段代码在我的笔记本上运行170K个数字大约需要30秒（每秒5K个CDR）。 请注意，该代码生成的是最接近的前缀，可能并不实际匹配该数字。在生产环境中，您需要包含类似于starts_with的内容来确保返回的前缀是一个实际匹配项。

- Doctor Eval