mysql - 多个关键字搜索的反向索引

Question

我正在寻找以下问题的架构解决方案:

问题的一般描述

我有很多不同的数据实体(大约 1500 万)。每个实体都与某些关键字(或标签)相关联(在最坏的情况下，从几个到每个实体数百个)。

给定 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 执行手动搜索-关键字、N-1-关键字等应用程序级别的数学。

问题

显然这种方法会遇到两个问题:

1. 从十亿条目的 Entities 表中接收数据集的时间很长(即使使用索引)；
2. 长时间执行应用程序级搜索以在应用程序级搜索 N 关键字匹配项。

对于这两个问题，请考虑在一般情况下一个标签可以与数百万 条目相关联。

如何高效处理这些问题？

Answer 1

我会使用 the intarray extension和一个 GiST 索引。

使用标签数组存储您的实体，例如:

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

并用一些模糊的东西来查询:

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;

索引将用于排除没有任何匹配标签的行。结果集将按匹配标签的数量降序排列。在具有相同数量的匹配标签的组内没有顺序，但您可以为此添加第二个排序键。

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

您可能需要一台有足够 RAM 的机器来容纳 GiST 索引。如果 UPDATE/INSERT 率很低，您可以使用 GIN 索引； GIN 的性能对于变化很小的数据更好，而对于变化很大的数据非常糟糕。