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

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

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

示例查询:

search_set = [该集合有500个ID]

在“find_set”与“search_set”相交的地方选择行
ORDER BY“十字路口的大小”

示例数据库:

索引find_set
1 [设置10,000个ID]
2 [设置了5,000个ID]
...
1,000,000 [设置15,000个ID]

我希望此查询花费多长时间？

我应该使用特定的数据库或数据库库吗？

我需要做一些预处理吗？

数据库如何实现这种类型的查询？他们是否对“search_set”中的500个ID分别进行一次搜索？

关于这种类型的问题以及如何解决，我还需要了解什么其他内容？

非常感谢!

最佳答案

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

首先，数据库通常没有一列包含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忙几个小时。