的內蒙古大哦性能上的兩個指標

我想弄清楚以下查詢的大哦性能加入：的內蒙古大哦性能上的兩個指標

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

table1.a是表的主鍵。 table2.b在它上面有一個非唯一索引。

我的想法是，因爲可以在O（log n）中搜索每個索引，則此查詢在O（log n * log m）中執行，其中n是表1中的行數，m是行數在表2中。

任何輸入，將不勝感激。

來源

2013-05-16 tlovett1

在發佈之前編寫一個有效的查詢。這不是有效的ANSI/ISO SQL語法，即使在MySQL中也會拋出錯誤（使用['ONLY_FULL_GROUP_BY'設置]（http://dev.mysql.com/doc/refman/5.5/en/server-sql-mode）。 html＃sqlmode_only_full_group_by）） –

你的想法有點偏離。可以在O（log n）中搜索索引進行單個查找。你的查詢可能會做這些「n」或「m」。

讓我假設查詢通過掃描一個表格並在另一個表格中查找值來將兩個表格連接起來。然後它會對order by進行基於排序的聚合。

的「匹配」塊查詢的是那麼大：

O（N日誌米）
O（米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-16 15:17:25

你說「匹配」部分是「更大」的。你不是指「小」嗎？如果一個表有2行，其他表有2行，查詢優化器應該選擇小表，然後對較大的表進行查找。對？ – BMiner

@Biner。。。「大哦」是上限，這就是爲什麼它是更大的。 –

對不起，你的意思是？你是說（對於「大哦」），你不能假設查詢優化器算法會選擇「更便宜」的路線來計算連接？ – BMiner

查詢的性能取決於SQL語句如何在內部執行。

也許您可以在這裏查看EXPLAIN（對於MySQL：http://dev.mysql.com/doc/refman/5.1/en/explain.html）以獲取有關您的查詢如何執行的更多信息，因爲這可能比查看Big-Oh產生更準確的結果。

btw：如果您真的在尋找Big-Oh，Gordon Linoff的回答看起來不錯！

來源

2013-05-16 15:16:19 lorey

的內蒙古大哦性能上的兩個指標

回答

相關問題