多个关键字反向索引搜索

Question

我要寻找一个建筑解决以下问题：

的问题

一般说明我有很多不同的数据实体（约1500万元）的。每个实体都与某些关键字（或标签）相关联（在最坏的情况下，从几个关键字到每个实体的hunderds）。

鉴于N不同的关键词，我的任务就是中检索以下顺序如下结果：

• 它们与所有N给出的关键字相关联的所有实体;
• 实体，其中包含给定关键字N-1的任意组合的实体;
• 实体，其中包含给定关键字的N-2的任意组合;
• 等等（可能正好限制到某个N-K-限制，但在一般情况下，可降至1个关键字匹配）。

朴素方法

我来的幼稚的解决方案是为使用MySQL/PostgreSQL的RDBMS每个关键字创建简单的反向索引。一般来说，将包含两个表：

Table Keywords    Table Entities 
---------------------  --------------------- 
    id  keyword   id  keyword_id 
---------------------  --------------------- 
    1   tag1    1    1 
    2   tag2    1    2    
    3   tag3    2    3 

• 表Keywords存储关键词;
• 表Entities存储实体间的关系id-s和keyword_id-s。

对于每个keyword1 & keyword2 & ... & keywordN查询我准备中检索所有实体的id集的每个查询的关键字，然后执行手动搜索N -keywords，N-1 -keywords等符合项目上的应用水平。

问题

显然，这种做法会遇到两个问题：

1. 从数十亿项Entities表（即使指数的使用）接收数据集的时间长;
2. 长时间执行应用程序级别搜索N -keywords在应用程序级匹配。

对于这两个问题，认为一个标签可与几百万在一般情况下，项目的关联。

如何有效处理这些问题？

Answer 1

您提出的模式没有多大意义。您在调用实体的东西之间存在N：M关系（相当困惑，因为这通常用于关系数据库中的单个表示的任何数据结构）。我认为事端已经在重新讲述迷路了，你居然说你有三个表：

keywords {id, keyword} 
entities {id, ....} 
entity_words {keyword_id, entity_id} 

这个架构显著改善的唯一途径是进行非规范化的比赛算入“实体”记载：

UPDATE entities e 
SET e.matches = (SELECT COUNT(DISTINCT ew.keyword_id) 
    FROM entity_words ew 
    WHERE ew.entity_id=e.id); 

....而你也可以在关键字表添加触发器时在关键字的数据改变为更新相关的实体唱片，这似乎矫枉过正时，你必须有一个机制creaing映射首先。

Answer 2

我会使用the intarray extension并为此梗概指数。

Store的实体标签阵列，例如：

SELECT 
    *, 
    ARRAY[1,3] & tags AS matched_tags 
FROM entity 
WHERE ARRAY[1,3] && tags 
ORDER BY array_length(ARRAY[1,3] & tags,1) DESC; 

该指数将用于排除不具有任何匹配的标签行：

CREATE EXTENSION intarray; 

CREATE TABLE entity(
    entity_id BIGSERIAL PRIMARY KEY, 
    tags integer[] not null 
); 

INSERT INTO entity(tags) values (ARRAY[1,2,3]); 
INSERT INTO entity(tags) values (ARRAY[1,3,5]); 
INSERT INTO entity(tags) values (ARRAY[1]); 
INSERT INTO entity(tags) values (ARRAY[]::integer[]); 

CREATE INDEX entity_tags_idx ON entity USING GIST(tags); 

和查询的东西隐约像。然后结果集将按照降序排列匹配标签的数量。在具有相同数量的匹配标签的组内不会强加任何订单，但您可以为其添加第二个排序键。

这应该只要每个实体没有一个真正巨大的标签列表工作。如果你不需要，不要计算“matched_tags”。如果您确实需要它，请考虑将其计算包装到子查询中，然后使用ORDER BY中的计算值而不是在那里重新计算。

您可能需要有足够的内存的机器，以适应要点指数在里面。如果UPDATE/INSERT率很低，则可以使用GIN索引代替; GIN的性能对于变化非常小的数据更好，对于变化很大的数据非常不利。

Answer 3

，你就能把所有合并到1台，如果我理解正确的模式。 我为冗长的模式创建事先道歉，但我想向自己证明它实际上会使用索引。这个例子使用了postgres，如果你安装了intarray扩展，你可以在关系上创建gist或者gin索引。我对Postgres的测试9.3

create table keyword (id serial primary key, tag varchar, relation integer[]); 

insert into keyword(id, tag,relation) values(1,'tag1',array[1]); 
insert into keyword(id, tag,relation) values(2,'tag2',array[1,2]); 
insert into keyword(id, tag,relation) values(3,'tag3',array[1,2,3]); 
insert into keyword(id, tag,relation) values(4,'tag4',array[1,2,3,4]); 
insert into keyword(id, tag,relation) values(5,'tag5',array[1,2,3,4,5]); 
insert into keyword(id, tag,relation) values(6,'tag6',array[1,2,3,4,5,6]); 
insert into keyword(id, tag,relation) values(7,'tag7',array[1,2,3,4,5,6,7]); 
insert into keyword(id, tag,relation) values(8,'tag8',array[1,2,3,4,5,6,7,8]); 
insert into keyword(id, tag,relation) values(9,'tag9',array[1,2,3,4,5,6,7,8,9]); 
insert into keyword(id, tag,relation) values(10,'tag10',array[1,2,3,4,5,6,7,8,9,10]); 
insert into keyword(id, tag,relation) values(11,'tag11',array[11]); 
insert into keyword(id, tag,relation) values(12,'tag12',array[12]); 
insert into keyword(id, tag,relation) values(13,'tag13',array[13]); 
insert into keyword(id, tag,relation) values(14,'tag14',array[14]); 
insert into keyword(id, tag,relation) values(15,'tag15',array[15]); 
insert into keyword(id, tag,relation) values(16,'tag16',array[16,13,12]); 
insert into keyword(id, tag,relation) values(17,'tag17',array[17,10,9,5,2,1]); 
insert into keyword(id, tag,relation) values(18,'tag18',array[18,1,2,3]); 
insert into keyword(id, tag,relation) values(19,'tag19',array[19,1]); 
insert into keyword(id, tag,relation) values(20,'tag20',array[20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]); 
insert into keyword(id, tag,relation) values(21,'tag21',array[21]); 
insert into keyword(id, tag,relation) values(22,'tag22',array[22]); 
insert into keyword(id, tag,relation) values(23,'tag23',array[23]); 
insert into keyword(id, tag,relation) values(24,'tag24',array[24]); 
insert into keyword(id, tag,relation) values(25,'tag25',array[25]); 
insert into keyword(id, tag,relation) values(26,'tag26',array[26]); 
insert into keyword(id, tag,relation) values(27,'tag27',array[27]); 
insert into keyword(id, tag,relation) values(28,'tag28',array[28]); 
insert into keyword(id, tag,relation) values(29,'tag29',array[29]); 
insert into keyword(id, tag,relation) values(30,'tag30',array[30]); 
insert into keyword(id, tag,relation) values(31,'tag31',array[30]); 
insert into keyword(id, tag,relation) values(32,'tag32',array[30]); 
insert into keyword(id, tag,relation) values(33,'tag33',array[30]); 
insert into keyword(id, tag,relation) values(34,'tag34',array[30]); 
insert into keyword(id, tag,relation) values(35,'tag35',array[30]); 
insert into keyword(id, tag,relation) values(36,'tag36',array[30]); 
insert into keyword(id, tag,relation) values(37,'tag37',array[30]); 
insert into keyword(id, tag,relation) values(38,'tag38',array[30]); 
insert into keyword(id, tag,relation) values(39,'tag39',array[30]); 
insert into keyword(id, tag,relation) values(40,'tag40',array[30]); 
insert into keyword(id, tag,relation) values(41,'tag41',array[30]); 
insert into keyword(id, tag,relation) values(42,'tag42',array[30]); 
insert into keyword(id, tag,relation) values(43,'tag43',array[30]); 
insert into keyword(id, tag,relation) values(44,'tag44',array[30]); 
insert into keyword(id, tag,relation) values(45,'tag45',array[30]); 
insert into keyword(id, tag,relation) values(46,'tag46',array[30]); 
insert into keyword(id, tag,relation) values(47,'tag47',array[30]); 
insert into keyword(id, tag,relation) values(48,'tag48',array[30]); 
insert into keyword(id, tag,relation) values(49,'tag49',array[30]); 
insert into keyword(id, tag,relation) values(50,'tag50',array[30]); 
insert into keyword (id, tag) (select generate_series, 'tag'||generate_series from generate_series(51,500)); 

create index on keyword(array_length(relation,1)); 
/*Uncomment the line below if you have intarray installed */ 
/*create index on keyword using gist(relation);*/ 
analyze keyword; 

因此，发现与其他标签5间的关系的所有元素，只需运行以下命令：

select * from keyword where array_length(relation,1)=5 

要查找与标签17相关的所有元素，运行以下内容：

select * from keyword where relation @> array[17] 

的关系阵列列可能持有这会搞砸重复的值，所以你可以写一个函数和一个检查约束，以防止这个，或者将这些代码写入应用程序 - 检查约束可能会大大增加插入的成本。

随意玩弄此架构上SQLFiddle，我已经在这里创造的模式：SqlFiddle