数据库搜索以返回按两个集合之间的交集大小排序的结果

Question

我想在我的数据库中搜索与我的搜索集相交的集。我希望结果按交集大小的顺序返回给我。

数据库行内的集合大约为 10,000。搜索集在500个左右。数据库中的行数约为1,000,000。

示例查询:

search_set = [ This set has 500 id's ]SELECT rows WHERE "find_set" INTERSECTS "search_set"     ORDER BY "size of the intersection"

示例数据库:

index         find_set1             [set with 10,000 ids]2             [set with  5,000 ids]...1,000,000     [set with 15,000 ids]

• 我预计此查询需要多长时间？
• 是否有我应该使用的特定数据库或数据库库？
• 我需要做一些预处理吗？
• 数据库如何实现这种类型的查询？他们是否对“search_set”中的 500 个 ID 中的每一个进行一次搜索？
• 关于此类问题及其解决方法，我还需要了解哪些其他信息？

非常感谢!

Answer 1

此查询的性能在很大程度上取决于数据库优化引擎和您执行查询的方式。

首先，数据库通常不会在一列中包含 15,000 个 id 的表。相反，您需要像这对表这样的东西:

set
---
id

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

第一个表将有一百万行。第二个更像是100亿。在 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 到 5 亿行之间的某处。假设您要撤回 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 忙上几个小时。