3

我有一个满是字符串（TEXT）的表，我喜欢在同一个表中获取所有其他字符串的子字符串。例如，如果我的表中有这三个字符串：

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）来做到这一点，但我不确定如何使用 SQL（PostgreSQL对于这个问题）。

4

3 回答 3

3

使用自联接：

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)
于 2015-11-13T23:21:27.820 回答
1

问题

该任务有可能使您的数据库服务器停止使用非平凡大小的表，因为只要您不能为其使用索引，它就是一个O(N²)问题。

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

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

解决方案

在- 最好是GIN上创建一个三元组索引。word

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

细节：

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

列出所有匹配项（根据问题正文）：
使用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;

要获取任何匹配的行（根据您的标题）：使用EXISTS半联接：

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)
   );
于 2015-11-14T03:13:38.070 回答
0

我会这样处理：

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 中作为嵌套循环实现，因此不会非常快。

于 2015-11-13T23:25:33.773 回答