13

I am trying to figure out the Big-Oh performance of the following query:

SELECT * 
FROM table1 INNER JOIN table2 ON table1.a = table2.b
GROUP BY table1.a

table1.a is the primary key of the table. table2.b has a non-unique index on it.

My thought is since each index can be searched in O(log n), then this query performs in O(log n * log m) where n is the number of rows in table 1 and m is the number of rows in table 2.

Any input would be appreciated.

4

2 回答 2

16

你的想法有点不对劲。可以在 O(log n) 中搜索索引以进行单个查找。您的查询可能是其中的“n”或“m”个。

让我假设查询通过扫描一个表并查找另一个表中的值将两个表连接在一起来进行处理。然后它为order by.

查询的“匹配”部分是以下两者中的较大者：

  • O(n log m)
  • O(m log n)

这假设查询引擎决定扫描一个表并在另一个表的索引中查找值。

要继续，一旦您查找值，您需要在页面中为您使用索引的表获取数据。获取数据在技术上是 O(n)。到目前为止，我们的估计是 O((n log m) + n + )。

对于排序后跟扫描，聚合应该是 O(n log n)。但是，您有多少条记录用于聚合？您可以有多达 n*m 匹配到联接。或者，少至 0（它是内部连接）。

这是大O，它是一个上限。所以，我们必须使用更大的估计。这导致聚合的 O((n*m)log(n*m)) ，这将支配其他术语。大 O 将是 O((n*m) log(n*m))。

于 2013-05-16T15:17:25.257 回答
2

查询的性能取决于 SQL 语句在内部的执行方式。

也许您可以在此处查看 EXPLAIN（对于 MySQL：http ://dev.mysql.com/doc/refman/5.1/en/explain.html ），以获取有关如何执行查询的更多信息，因为这可能会产生更准确的结果比看着大哦。

顺便说一句：如果您真的在寻找 Big-Oh，Gordon Linoff 的答案看起来不错！

于 2013-05-16T15:16:19.383 回答