3

涉及多个条件的 SQL 选择查询的时间复杂度是多少？

SELECT * 
  FROM products 
 WHERE price > 100 
   AND width > 100 
   AND rating > 100

例如，数据库引擎 (InnoDB) 如何使用价格、宽度和评级索引来处理此查询？

引擎会先处理价格，然后按宽度和评级过滤结果吗？这意味着首先 O(log(n)+k)，其中 k 是结果数，n 是产品表中的条目数，然后是 O(n)，然后是 O(n)，n 是每个最后的结果数过滤操作？？

4

1 回答 1

3

您基本上是在询问 SQL 优化器是如何工作的，并且正如所指出的，它因 SQL 版本而异，并且取决于。

通常（非常广泛），优化器保留有关表的元数据，以便它可以选择哪个索引有意义。例如，如果一个表包含学生性别和 GPA，您会期望优化器始终使用 GPA 上的索引。但是，如果您在一所全是男性的学校运行查询并搜索女性，优化器可能会意识到先搜索性别列会更快（因为返回的记录很少）。此外，如果您的表非常小，优化器可能会说，“见鬼的索引，我将只扫描整个该死的表”......

在您的示例中，请考虑有多少不同的值。该列都是整数吗？如果是这样，优化器可以查询元数据并说“嗯，只有 300 行评级超过 100，而 10,000 行价格超过 100，我想我会使用评级开始”...... .

但是，正如 OMG 小马指出的那样，这取决于...

于 2013-01-20T16:22:45.187 回答