SQL查詢查找具有最匹配關鍵字的行

Question

我對SQL非常不滿，我想知道我可以運行哪些SQL來解決下面我懷疑是NP-Complete問題的問題，但我是確定查詢需要很長時間才能運行大型數據集，因爲這將作爲後臺任務完成。一個標準的sql語句是首選，但如果需要存儲過程，那就這樣吧。 SQL需要在Postgres 9.3上運行。

問題：給定一組包含一組關鍵字的文章，找到包含最多匹配關鍵字的每篇文章的前n篇文章。

一個下調的文章表的版本是這樣的：

CREATE TABLE article (
    id character varying(36) NOT NULL, -- primary key of article 
    keywords character varying,   -- comma separated set of keywords 

    CONSTRAINT pk_article PRIMARY KEY (id) 
); 

-- Test Data 
INSERT INTO article(id, keywords) VALUES(0, 'red,green,blue'); 
INSERT INTO article(id, keywords) VALUES(1, 'red,green,yellow'); 
INSERT INTO article(id, keywords) VALUES(2, 'purple,orange,blue'); 
INSERT INTO article(id, keywords) VALUES(3, 'lime,violet,ruby,teal'); 
INSERT INTO article(id, keywords) VALUES(4, 'red,green,blue,yellow'); 
INSERT INTO article(id, keywords) VALUES(5, 'yellow,brown,black'); 
INSERT INTO article(id, keywords) VALUES(6, 'black,white,blue'); 

這將導致這對SELECT * FROM article;查詢：

Table: article 
------------------------ 
id keywords    
------------------------ 
0 red,green,blue  
1 red,green,yellow  
2 purple,orange,blue 
3 lime,violet,ruby,teal 
4 red,green,blue,yellow 
5 yellow,brown,black 
6 black,white,blue 

假設我想找到的前3篇每條包含最多匹配關鍵字的文章，那麼輸出應該是這樣的：

------------------------ 
id related 
------------------------ 
0 4,1,6 
1 4,0,5 
2 0,4,6 
3 null 
4 0,1,6 
5 1,6 
6 5,0,4 

Answer 1

與@a_horse commented一樣：使用標準化設計會更簡單（除了使其他任務更簡單/更清潔），但仍然不是微不足道的。

而且，數據類型爲character varying(36)的PK列是高度可疑的（並且效率低下），應該最可能是integer type或至少是uuid。

這裏是根據你設計的一個可能的解決方案，是：

WITH cte AS (
    SELECT id, string_to_array(a.keywords, ',') AS keys 
    FROM article a 
    ) 
SELECT id, string_agg(b_id, ',') AS best_matches 
FROM (
    SELECT a.id, b.id AS b_id 
     , row_number() OVER (PARTITION BY a.id ORDER BY ct.ct DESC, b.id) AS rn 
    FROM cte a 
    LEFT JOIN cte b ON a.id <> b.id AND a.keys && b.keys 
    LEFT JOIN LATERAL (
     SELECT count(*) AS ct 
     FROM (
     SELECT * FROM unnest(a.keys) 
     INTERSECT ALL 
     SELECT * FROM unnest(b.keys) 
     ) i 
    ) ct ON TRUE 
    ORDER BY a.id, ct.ct DESC, b.id -- b.id as tiebreaker 
    ) sub 
WHERE rn < 4 
GROUP BY 1; 

SQL Fiddle（使用整數代替id）。

CTE cte將字符串轉換爲數組。你甚至可以有一個功能GIN指數這樣的...

如果多行並列前3名選秀權，你需要定義一個決勝局。在我的例子中，排名較小的行排在第一位。

在這最近的相關答案詳解：

• Query and order by number of matches in JSON array

  的比較是一個JSON陣列和SQL陣列之間，但它基本上是同樣的問題，燒燬相同的溶液（S）。還比較了幾個類似的替代品。

爲了使這個快，你至少應該對陣列列（而不是逗號分隔的字符串）和查詢將不需要的CTE步驟GIN索引。完全標準化的設計具有其他優點，但不一定比具有GIN索引的數組更快。

Answer 2

您可以以逗號分隔的字符串存儲列表。沒問題，只要這只是一個字符串，而你對其單獨的值不感興趣。只要你是感興趣的獨立的價值，如在你的例子，分開存儲它們。

這就是說，更正您的數據庫設計，然後才考慮查詢。

以下查詢首先選擇所有ID對並計算常用關鍵字。然後通過給其他ID用最常用等級＃1中的關鍵字等進行排列，然後只保留三個最佳匹配的ID。 STRING_AGG列出了按照共同關鍵字數量排序的字符串中最匹配的ID。

select 
    this_article as id, 
    string_agg(other_article, ',' order by rn) as related 
from 
(
    select 
    this_article, 
    other_article, 
    row_number() over (partition by this_article order by cnt_common desc) as rn 
    from 
    (
    select 
     this.id as this_article, 
     other.id as other_article, 
     count(other.id) as cnt_common 
    from keywords this 
    left join keywords other on other.keyword = this.keyword and other.id <> this.id 
    group by this.id, other.id 
) pairs 
) ranked 
where rn <= 3 
group by this_article 
order by this_article; 

這裏是SQL小提琴：http://sqlfiddle.com/#!15/1d20c/9。