在MySQL中查找中位數和計數的複雜性是什麼？

Question

我想知道以下兩個操作的複雜程度。第一種情況是一個計數，其中我被列順序，我上有一個索引，並要求低於或高於特定數量的這樣的所有值的計數：是關於中值運算

SELECT count(*) FROM tbl WHERE col1 > 10 ORDER BY col1; 

另一種情況。按照中位數我的意思是找到（int）n/2的行值，其中n是表中的行數。這方面的例子可能是由以下（同樣有在col1的索引）：

SELECT median(col1) FROM tbl ORDER BY col1; 

什麼是這些案件的最壞情況的複雜性？

Answer 1

ORDER BY條款是不必要的 - 或混淆，或兩者兼而有之。

SELECT COUNT(*)將返回一行（通常）。由於您在搜索中有一個標準，因此優化程序可能必須對col1執行索引掃描（如果存在索引col1作爲索引的前導列）或表掃描。這是一個O（N）操作，其中N是表中的行數。

SELECT MEDIAN(col1)也將返回單行（通常）。這將是O（N）操作，再次使用索引掃描或表掃描。

'正常'限定符在那裏，因爲我並不完全確定優化器將如何處理ORDER BY子句。一種可能性是優化器將確定它是多餘的並忽略它。另一種可能性是，它會以某種方式將 ORDER BY添加到投影列中，將其包含在其他操作中，然後在返回結果之前將其刪除。但是，如果沒有GROUP BY子句，那麼混合聚合和非聚合就會出現混淆 - 所以我認爲優化器會忽略它，或者拒絕查詢。但是，我還沒有用MySQL做過實驗。

FWIW，IBM Informix Dynamic Server（IDS）產生錯誤-19828：在此上下文中，ORDER BY列或表達式必須位於SELECT列表中。

沒有ORDER BY子句，上面的分析足夠準確。請注意，對於沒有條件的SELECT COUNT（*），服務器通常可以使用它保留的表的元數據來在O（1）時間內回答查詢。