內置SQL函數的時間複雜性函數如sum，count，avg

什麼是函數的時間複雜度，如count，sum，avg或mysql，sql server中的內置「數學」函數的任何其他函數， oracle和其他？內置SQL函數的時間複雜性函數如sum，count，avg

有人會認爲調用sum（myColumn）將是Linear。

但是count（1）不是。怎麼回事，什麼是真正的時間複雜性？

在一個完美的世界中，我想總和，平均值和數值爲O（1）。但我們不住在其中之一，是嗎？

2009-10-07 Filip Ekberg

您可以通過預先計算您的聚合並將其保存在查找表中來交換空間速度。 ;） – Juliet 2009-10-07 21:11:50

@Filip你是什麼意思count（1）不是線性的？線性關於什麼？ – spinkus 2014-07-26 03:37:24

在SQL中，聚合的數學函數複雜性是完全相關的。唯一真正重要的是數據承諾的複雜性：選擇什麼訪問路徑（表掃描，索引範圍掃描，索引搜索等）以及讀取多少頁面。每個聚合的內部可能會有細微的差異，但它們的工作方式幾乎相同（保持運行狀態並計算每個輸入值的運行聚合），並且絕對有兩次查看輸入的聚合，所以它們所有O（n）作爲內部實現，其中'n'是饋送給聚合的記錄數（不一定是表中記錄的數量！）。

某些聚合具有內部快捷鍵，例如。如果可能，COUNT（*）可能會從返回某些系統上的元數據計數。

來源

2009-10-07 21:51:13

我認爲假設主要聚合函數爲O（n）是合理的。澄清這一點很有用。但是你聲明「某些聚合內部有快捷方式，例如，如果可能，COUNT（*）可能會從某些系統的元數據中返回計數。」這是更有趣的部分。在這些類型的優化方面常見的RDB實現有哪些可用的功能？例如，人們會認爲max（），min（），average（）也可能是O（1）操作，但它們是否合理？ – spinkus 2014-07-26 03:48:56

注意：這是基於我對SQL查詢規劃器的工作原理的推測，可能並不完全準確。

我相信所有的聚合函數，或者至少是上面提到的「數學」函數應該是O（n）。如下的查詢將被大致執行：

讀取行，匹配連接謂詞和過濾謂詞（即，「WHERE子句」）
根據GROUP BY子句創建行組。爲沒有GROUP BY的查詢創建單個行組
對於每個行組，將聚合函數應用於組中的行。對於像SUM，AVG，MIN，MAX這樣的東西以及像CONCAT這樣的非數字函數，都有簡單的O（n）算法，我懷疑這些算法是被使用的。在輸出在步驟＃2
創建的每個行組集合創建一行如果HAVING謂詞存在時，使用濾波器輸出行這個謂詞

但是請注意，即使在聚合函數是O（n），操作可能不是。如果你創建一個查詢笛卡兒將自己的表加入到表中，那麼你將會看到O（n * n）的最小值來創建初始行集（步驟＃1）。排序以創建行組（步驟＃2）可能是O（n lg n），並且可能需要磁盤存儲以進行排序操作（而不是僅針對內存操作），因此，如果您的查詢性能仍然很差操縱許多行。

來源

2009-10-07 21:08:40 dcrosta

對於大數據倉庫風格的查詢，主要數據庫可以並行化任務，因此有多個CPU可以處理它。因此，由於協調並行線程的成本與使用多個CPU的好處相互影響，所以會存在閾值點，因爲它不是線性的。

來源

2009-10-09 08:38:25

什麼是一個函數的時間複雜度，如計數，總和，平均或任何其他內置的「數學」函數在MySQL，SQL服務器，甲骨文等？

在MySQL與MyISAM，COUNT(*)而不GROUP BY是O(1)（常數）

它存儲在該表的元數據。
在所有系統中，MAX和MIN上沒有GROUP BY的索引表達式都是O(log(n))（對數）。

它們是通過單個索引查找獲取的。
集合函數是O(n)（線性），而不GROUP BYGROUP BY或使用時使用HASH
集合函數是O(n log(n))當GROUP BY使用SORT。

所有值應該被提取，計算並存儲在狀態變量中（可以存儲在散列表中）。

另外，當使用SORT時，它們也應該排序。

來源

2009-10-09 11:14:57 Quassnoi

謝謝你的精確總結。你是否知道一本能夠詳細證明這些觀察結果的書或論文？ – Juve 2015-08-21 10:26:32

內置SQL函數的時間複雜性函數如sum，count，avg

回答

相關問題