以列值作为连接列前缀的高效自连接

Question

如何有效地将一组字符串转换为一个表，以便每个字符串都映射到以其为前缀的所有其他字符串？

我使用 PostgreSQL 14 并处理一个包含约 55,000 个字符串的表

medical_codes

（不同分类系统的医疗代码，例如 ICD-10）。每个的长度在 3 到 8 个字母之间。我现在想高效地构建一个查找表，将每个字符串

a

映射到所有其他字符串

b

，使得

a

是

b

的前缀。例如。给定：

代码
A04
A04.1
A04.2
A05
A06

我想生成：

前缀	代码
A04	A04
A04	A04.1
A04	A04.2
A04.1	A04.1
A04.2	A04.2
A05	A05
A06	A06

一个简单的实现虽然有效，但效率极低，是

SELECT
    prefix_code.code AS prefix,
    specific_code.code AS code
FROM
    medical_codes AS prefix_code
    INNER JOIN medical_codes AS specific_code ON specific_code.code LIKE prefix_code.code || '%'

唉，即使是

varchar_pattern_ops

上的

medical_codes(code)

索引在这里也无济于事，因为搜索模式是动态构建的。我还尝试考虑代码的长度：

CREATE INDEX medical_codes_code_length_idx ON medical_codes (length(code));

SELECT
    prefix_code.code AS prefix_id,
    specific_code.code AS code_id
FROM
    medical_codes AS prefix_code
    INNER JOIN medical_codes AS specific_code ON length(specific_code.code) >= length(prefix_code.code)
WHERE
    specific_code.code LIKE prefix_code.code || '%'

...这有点帮助，但仍然很慢。

有更有效的方法吗？也许可以组成一个执行“分而治之”方法的查询，从最短的字符串开始，然后对每个字符串进行递归以找到更长的匹配字符串？

Answer 1

我有一个灵丹妙药给你，但不太容易找到：
创建 SP-GiST 索引并使用 “starts-with”运算符

^@

索引：

CREATE INDEX medical_codes_code_spgist_idx ON medical_codes USING spgist(code);

查询：

WITH prefix(code) AS (
   VALUES
     ('A04')
   , ('A04.1')
   , ('A04.2')
   , ('A05')
   , ('A06')
   )
SELECT p.code AS prefix, c.code
FROM   prefix p
LEFT   JOIN medical_codes c ON c.code ^@ p.code
ORDER  BY 1, 2;  -- optional

小提琴——Postgres 16
小提琴——Postgres 14

我始终如一地获得时间< 1 ms。

运算符

^@

没有在 Postgres 14 中记录。但它已经存在了。自 Postgres 15 起就对其进行了记录（并进行了改进）。请参阅：

• PostgreSQL LIKE 查询性能变化

我原本希望它也能与 Postgres 16 中的 B 树

COLLATE "C"

索引一起使用。但由于某种原因，我只能通过 SP-GiST 索引获得出色的查询计划。不知道为什么会这样。