假設我想在給定一些分組屬性 G 的情況下計算一些數據的中位數，例如每天銷售的所有產品的中位數價格（假設星型模式）

SELECT T.day_id, MEDIAN(price) 
FROM sales S, time T
WHERE T.day_id = S.day_id 
GROUP BY T.day_id;

中位數是一個整體聚合函式，即我們只有知道屬於某一天的所有記錄才能計算它。如果一天的記錄不適合主記憶體，如何計算？

**編輯：**我知道中位數是什麼以及一般如何計算。我感興趣的是如何在使用 GROUP BY 時有效地計算它，即不產生太多 IO。此外，中位數只是使問題更具體的整體功能的一個例子。我還可以使用其他整體聚合函式，例如排名、百分位數等。

我所說的整體功能是什麼意思：

如果您只能從它們的基本元素或從許多事先不知道的預聚合計算它，那麼聚合函式就是整體的。一個反例是平均值。它不是整體的，因為您總是通過儲存計數和總和而不是儲存所有以前的記錄來計算它。

中值是來自總體的值，其中有相同數量的值小於中值和大於中值。要執行該計算，您不需要將所有值都保存在 main memory 中。您只需按升序或降序對值進行排序，然後選擇位於中間的值。

即使不使用複雜的 DBMS，通過實現冒泡排序，在處理每個值時從磁碟讀取和寫入每個值，計算一組值的中值也很容易。即使對於數万億行的列表，這也可以在遠小於 1 兆字節的 RAM 中實現。你需要澄清你的問題。

“有沒有其他解決方案”的答案在我看來與“P-NP”問題的答案相同，目前尚未解決，比我大腦大得多的人已經研究了很長時間。簡而言之，我無法最終證明沒有其他“更好”的方法可以解決這個問題。如果你有一個你想要解決的特定問題，例如“這個聚合的性能太慢”，那麼你應該問一個新的問題，包括具體的細節，包括有問題的 DBMS、表定義和你的程式碼已經建成。

SQL的“有序集函式”

使用 PostgreSQL，您可以使用規範的Ordered-Set Aggregate Functions來確定諸如中位數之類的東西。

## Returns 2
SELECT percentile_disc(0.50) WITHIN GROUP (ORDER BY x)
FROM ( VALUES (1),(1),(2),(2),(3),(3),(3),(3) ) AS t(x);

## Returns 3
SELECT percentile_disc(0.50) WITHIN GROUP (ORDER BY x)
FROM ( VALUES (1),(1),(2),(2),(3),(3),(3),(3),(3) ) AS t(x);

這裡沒有什麼必須“適合主記憶體”？至少不會超過任何其他順序掃描所需要的。

微軟也嘗試實現“有序集聚合”

引用自：https://dba.stackexchange.com/questions/198121