按两个集合交集大小排序的数据库搜索结果

Question

我希望能够搜索我的数据库，找到与我的搜索集相交的集合。希望结果按照交集大小的顺序返回给我。

数据库中的集合将大约有10,000个。搜索集大约有500个。数据库中的行数大约为1,000,000。

示例查询：

search_set = [这个集合有500个ID]
SELECT rows WHERE "find_set" INTERSECTS "search_set" 
    ORDER BY "intersection的大小"

示例数据库：

index         find_set
1             [有10,000个ID的集合]
2             [有5,000个ID的集合]
...
1,000,000     [有15,000个ID的集合]

• 我可以期望这个查询需要多长时间？
• 是否有特定的数据库或数据库库应该使用？
• 我需要进行一些预处理吗？
• 数据库如何实现这种类型的查询？它们会针对"search_set"中的每个500个ID执行一次搜索吗？
• 还有哪些其他事情需要了解这种类型的问题以及它是如何解决的？

非常感谢！

- Chris Dutrow

---

请问您能否发布表的DDL？ - srini.venigalla

@srini.venigalla - 我还没有创建表格。不过可以安全地假设“find_set”和“search_set”的内容将是小字符串或64位整数。 - Chris Dutrow

Answer 1

这个查询的性能强烈依赖于数据库优化引擎和您执行查询的方式。

首先，数据库通常不会在一列中拥有15,000个ID的表。相反，您需要像这样一对表：

set
---
id

set_entry
-----------
id
set_id
entry

第一张表将有一百万行。第二张表则更多，大约有一百亿行。在set_entry.entry上建立索引。

通常最好的方法是安排一个临时表，其行是查询集的值。然后执行以下查询：

SELECT set_entry.id, COUNT(*)
FROM set_entry
  JOIN query_entry
    ON set_entry.entry = query_entry.entry
GROUP BY set_entry.id
ORDER BY count(*) DESC

你想要的查询计划是对于每个元素，它应该在索引上进行查找，返回所有匹配的行，然后继续执行分组操作，以确定每个交集集合中有多少个。在第一步中，您将执行500次查找，然后返回0到500万行之间的数据。假设您返回了500万行。分组操作将通过构建哈希表或对数据进行排序（数据库可以使用任一种方式）来完成，这两种方法都应该非常快速。

虽然存在许多未知因素，但是这个计划可能需要几秒钟的时间。

您需要注意的是像这样的查询：

SELECT set_entry.id, COUNT(*)
FROM set_entry
WHERE entry IN (id1, id2, ....)
GROUP BY set_entry.id
ORDER BY count(*) DESC

根据我的经验，大多数数据库引擎会查看这个索引，然后决定不能使用它。相反，它们将扫描所有的set_entry（有100亿行），并为每个元素扫描那组500个元素，进行成对比较。这意味着大约需要进行5万亿次成对比较的初始步骤。这个计划将轻松让您的CPU忙碌数小时。

- btilly

---

谢谢您的回复。听起来搜索时间的瓶颈是需要进行500次查找，对吗？ - Chris Dutrow