在 SQL 中，如何检查一个字符串是否是同一 table 中任何其他字符串的子字符串？

Question

我有 table 个充满字符串 (TEXT) 的字符串，我想获取所有作为同一 table 中任何其他字符串的子字符串的字符串。例如，如果我的 table:

中有这三个字符串

WORD        WORD_ID
cup         0
cake        1
cupcake     2

作为我查询的结果，我想得到这样的结果：

WORD        WORD_ID        SUBSTRING        SUBSTRING_ID
cupcake     2              cup              0
cupcake     2              cake             1

我知道我可以使用两个循环（使用 Python 或 JS）来完成此操作，方法是遍历 table 中的每个单词并将其与同一个 table 中的每个单词匹配]，但我不确定如何使用 SQL（PostgreSQL 就此而言）。

Answer 1

使用自连接：

select w1.word, w1.word_id, w2.word, w2.word_id
from words w1
join words w2
on w1.word <> w2.word
and w1.word like format('%%%s%%', w2.word);

  word   | word_id | word | word_id 
---------+---------+------+---------
 cupcake |       2 | cup  |       0
 cupcake |       2 | cake |       1
(2 rows)

Answer 2

我会这样处理：

select w1.word_id, w1.word, w2.word_id as substring_id w2.word as substring
from words w1 join
     words w2
     on w1.word like '%' || w2.word || '%' and w1.word <> w2.word;

注意：这可能比在应用程序中执行循环要快一点。但是，此查询将在 Postgres 中作为嵌套循环实现，因此速度不会非常快。

Answer 3

问题

该任务有可能使您的数据库服务器停止 tables non-trivial 大小，因为它是一个 O(N²) 问题，只要因为你不能为它使用索引。

在顺序扫描中，您必须检查两行的所有可能组合，即 n * (n-1) / 2 组合 - Postgres 将运行 n * n-1 测试，因为要排除反向重复并不容易组合。如果您对第一场比赛感到满意，它会变得更便宜 - 多少取决于数据分布。对于许多匹配，Postgres 会提前找到一行的匹配并且可以跳过测试其余的。对于少数匹配项，无论如何都必须执行大部分检查。

无论哪种方式，性能都会随着 table 中行数的增加而迅速下降。使用 EXPLAIN ANALYZE 和 table 中的 10、100、1000 等行测试每个查询以亲自查看。

解决方案

在 word 上创建一个 三字母索引 - 最好是 GIN.

CREATE INDEX tbl_word_trgm_gin_idx ON tbl USING gin (word gin_trgm_ops);

详情：

PostgreSQL LIKE query performance variations

到目前为止，两个答案中的查询都不会使用索引，即使您有索引也是如此。使用可以实际使用该索引的查询：

列出所有匹配（根据问题body）：
使用 LATERAL CROSS JOIN:

SELECT t2.word_id, t2.word, t1.word_id, t1.word
FROM   tbl t1
     , LATERAL (
   SELECT word_id, word
   FROM   tbl
   WHERE  word_id <> t1.word_id
   AND    word like format('%%%s%%', t1.word)
   ) t2;

仅获取具有 any 匹配项的行（根据您的标题）：使用 EXISTS semi-join:

SELECT t1.word_id, t1.word
FROM   tbl t1
WHERE EXISTS (
   SELECT 1
   FROM   tbl
   WHERE  word_id <> t1.word_id
   AND    word like format('%%%s%%', t1.word)
   );

在 SQL 中，如何检查一个字符串是否是同一 table 中任何其他字符串的子字符串？

In SQL, how to check if a string is the substring of any other string in the same table?

sql

postgresql

loops

pattern-matching

string-function

问题

解决方案