前半有序的大資料排序

最近碰到這麼一個案例，情況可以簡化總結成這樣：資料庫中有表T，其中有兩個重要的字段a和b，a是一個時間戳，精确到秒；b是使用者号；其它字段用來表示使用者b在時刻a發生的事件屬性。

現在任務是：把資料按a,b排序導出。簡單來講，就是把SELECT * FROM T ORDER BY a,b的結果集寫出到檔案。

但是，這個T表有幾十億條記錄，這個SQL發出去之後，資料庫就象死了一樣，一個多小時都沒有任何反應。

這也難怪，幾十億記錄的大排序确實非常慢，上T的資料量記憶體裝不下，而外存排序需要分段讀入資料，在記憶體将每段排序後再緩存到硬碟，然後将這些緩存資料一起再歸并。這樣，必須把所有資料都周遊過一遍且分段排序後才能開始輸出。

還有什麼别的辦法麼？

通用的大排序可以說已經被全世界研究到極緻了，再想出一個更優的辦法幾乎沒有可能性了。但是，如果我們能找到這些資料的一些可得特征，說不定就能有辦法了。

了解到一些業務資訊後，我們發現這批資料有這樣一些特征：

1. 資料是按發生時刻（也就是a）為次序插入的，這樣實體存儲次序也就會接近于按a有序，而且資料庫已經為字段a建好了索引；

2. 從某個起始時刻到終止時刻，幾乎每一秒都會有資料插入；

3. 資料按時間分布比較平均，大概每秒數萬條，沒有某一秒的資料量特别多；

利用這些特征，我們可以設計這樣的算法（用SPL寫成），其中start,end分别是資料的起止時刻。

A	B
1	for interval@s(start,end)+1	=elapse@s(start,A1-1)
2	=db.query(“SELECT * FROM T WHERE a=?”,B1)
3	=B2.sort(b)
4	>outputfile.export@a(B3)

基本邏輯是：循環所有的秒，從資料庫取出某一秒的記錄按b排序後再寫出到檔案。因為資料庫為a建有索引，而資料也接近于按a有序存儲，用索引取數就非常快。每一秒内的資料量并不大，可以在記憶體中排序，速度很快。容易證明這個算法傳回的結果集就是按a,b有序的，這樣就不需要緩存資料就可以完成這個大排序了。

這個算法執行後立即就有資料開始輸出，數小時内就完成了按序導出資料的任務，之是以需要數小時，主要還是從資料庫中取數以及寫入檔案的時間（幾十億行和上T的資料量），排序本身幾乎沒有占用時間。

針對這批資料，我們還有一個任務：想知道字段a,b是否可以用作T的主鍵，也就是說字段a,b的取值在T表是否是唯一的。

本來用SQL做這個判斷也很簡單，隻要看看

SELECT COUNT(*) FROM T

和

SELECT COUNT(*) FROM (SELECT a,b FROM T GROUP BY a,b)

是否相等就可以了（有些資料庫不支援COUNT(DISTINCT a,b)寫法，這裡寫成子查詢形式）。

COUNT(*)容易算，但面對數十億行的大資料做GROUP BY運算，其方法和外存排序是差不多的，成本也差不多，也是跑了一個多小時沒動靜。

但是，如果我們利用上述特征，就很容易計算出這個值：

	=db.query@1(“SELECT COUNT(DISTINCT b) FROM T WHERE a=?”,B1)
	=@+B2

類似地，循環每一秒，針對每一條記錄一個COUNT(DISTINCT B)，然後都加起來就是我們要的答案了（容易證明這個算法的正确性）。這段代碼幾分鐘就完成了運算（和上例相比，這裡不導出也就不需要取出明細資料了，也不必寫檔案，而且還能并行計算，不象上例中要有序寫出就隻能串行）。

細心的讀者可能要問，這兩個例子都是講如何利用索引來快速計算，為什麼本文标題要叫“前半有序”呢？

實際上我們就是利用了這批資料已經有的次序資訊。這兩個問題的關鍵點都是需要按a,b排序，而在索引的作用下，這批資料看起來已經對a有序了，也就是待排序字段中的前一部分字段已有序了。而如果前面字段相同時的記錄數都沒有大到記憶體放不下的地步，那麼就可以不使用緩存實作大排序了。

如果資料已經存儲在可以保持次序的檔案中，則這個方法的适應面會更寬泛一些，不需要事先知道a的起止時刻并循環每一秒，代碼也會更簡單些。

假如資料檔案T中按a的次序寫入了T表的記錄，則上面的兩個問題的算法可以分别寫出來是這樣：

	for file(T).cursor();a	=A1.sort(b)
	>outputfile.export@a(B1

		=@+A1.id(b).len()

SPL中提供了針對遊标的有序取出方法，上面兩段代碼中A1格的意思是針對檔案T的資料遊标循環，每次讀到字段a的值發生變化時則進入循環體，然後再讀下一批a相同的記錄，...。

基于檔案的運算比上述使用索引從資料庫取數的效果又好了數倍。而且這幾段代碼對記憶體占用也非常少。本來大排序是個很耗用記憶體的動作，因為後一步歸并的性能嚴重依賴于分段的數量，要減少分段，就要讓每一段盡量大，是以記憶體越大的性能就越好。而利用前半有序的特征後，隻要一點點記憶體（本例中隻要能裝入數萬行記錄）就可以高速完成運算了。

最後再溫習一下我們的觀點：性能優化要因地制宜，根據資料和運算的特征想辦法。

我們不能解決通用的大排序問題，但在特定場合下卻能設計出好算法提高性能。而資料庫過于透明，看起來程式員不用操心了，但資料庫并沒有那麼智能，經常不會利用資料特征來自動優化。而且，在SQL體系下，即使人為想出好算法，也幾乎無法實作。

原文釋出時間為：2018-11-13

本文作者：蔣步星

本文來自雲栖社群合作夥伴“

資料蔣堂

”，了解相關資訊可以關注“

”。