SQL: как проверить, является ли строка подстрокой любой другой строки в той же таблице

У меня есть таблица, полная строк (текста), и мне нравится получать все строки, которые являются подстроками любой другой строки в той же таблице. Например, если бы у меня были эти три строки в моей таблице: 

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, если уж на то пошло).

Я был бы очень счастлив, если бы кто-нибудь здесь мог помочь мне в этом.

3 3
sql loops postgresql pattern-matching string-function

3 ответа:

Используйте self-join: 

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)
2

Задача

Задача потенциально может остановить ваш сервер баз данных для таблиц нетривиального размера, так как этоO(N2) проблема, пока вы не можете использовать для нее индекс.

При последовательном сканировании вы должны проверить каждую возможную комбинацию из двух строк, то есть комбинации n * (n-1) / 2 - Postgres будет выполнять тесты n * n-1, так как не так просто исключить обратные повторяющиеся комбинации. Если вас устраивает первый матч, то он становится дешевле - сколько зависит от того, как вы его проведете. распределение данных. Для многих матчей Postgres найдет совпадение для строки раньше и может пропустить тестирование остальных. Для некоторых матчей большинство проверок все равно приходится выполнять.

В любом случае производительность быстро ухудшается с увеличением числа строк в таблице. Проверьте каждый запрос с помощью EXPLAIN ANALYZE и 10, 100, 1000 и т. д. строки в таблице, чтобы увидеть сами.

Решение

Создайте индекс триграммы на word - предпочтительно Джин .

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

Подробности:

Запросы в обоих ответах до сих пор не использовали бы индекс, даже если бы он у вас был. Используйте запрос, который действительно может работать с этим индексом:

Перечислить все совпадения (в соответствии с телом вопроса):
Используйте a 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)
   );
1

Я бы подошел к этому так: 

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, поэтому он не будет слишком быстрым.

0