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。