两个指标的内在联接的大哦表现

Question

我试图找出以下查询的Big-Oh性能:

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

table1.a是表的主键.table2.b上有一个非唯一索引.

我的想法是,因为每一个索引可以在O(log n)的被搜索,然后这个查询为O执行(日志的n*log m),其中n是行的表1中,且m的数量的行的表2中的数量.

任何输入将不胜感激.

Answer 1

你的想法有点过时了.可以在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)),这将主导其他项.big-O将是O((n*m)log(n*m)).