4

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

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

示例查询:

search_set = [这个集合有500个id]

选择行 WHERE "find_set" INTERSECTS "search_set"
    ORDER BY "交叉点的大小"

示例数据库:

索引查找集
1 [设置有 10,000 个 ID]
2 [设置 5,000 个 ID]
...
1,000,000 [设置有 15,000 个 ID]
  • 我希望这个查询需要多长时间?
  • 是否有我应该使用的特定数据库或数据库库?
  • 我需要做一些预处理吗?
  • 数据库如何实现这种类型的查询?他们是否对“search_set”中的 500 个 id 中的每一个进行一次搜索?
  • 关于此类问题以及如何解决,我还需要了解哪些其他信息?

非常感谢!

4

1 回答 1

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 忙碌几个小时。

于 2012-06-26T22:02:37.907 回答