[發明專利]基于列式存儲的流水排序方法

在審

• 申請號: 202210930836.6
• 申請日: 2022-08-04
• 公開（公告）號: CN115309837A
• 公開（公告）日: 2022-11-08
• 發明（設計）人: 李曉鵬;賈宗秀;劉堯;姬濤濤;蔣旭;張昕堯;趙冬偉;朱亞楠;吳嵩;周勇亮;劉勇生;桑國彪;樂承予
• 申請（專利權）人: 天津神舟通用數據技術有限公司
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06F16/2457;G06Q30/02
• 代理公司: 天津盛理知識產權代理有限公司 12209
• 代理人: 王利文

本發明涉及一種基于列式存儲的流水排序方法，其技術特點是：包括異步IO線程、流水化線程和排序線程，其根據所有CU的元信息構建CU序列，并根據CU序列的最小值信息構造邊界序列，在排序過程中，將CU視為一個數據集合，對于相鄰的兩個CU，使用后一個CU的最小值做邊界將數據劃分為兩部分，前一部分可以作為子集合單獨排序，后一部分和第二個CU組成一個新的集合，再和后面的CU繼續進行相同的處理，實現流水排序。本發明設計合理，實現了對采用列式存儲并且近似有序的數據集合進行快速排序功能，具有處理速度快、占用資源小等特點。

技術領域

本發明屬于數據庫技術領域，尤其是一種基于列式存儲的流水排序方法。

背景技術

數據倉庫通常存儲有海量的原始數據，為用戶通過報表、看板等工具從數據中獲得洞察力、決策指導。數據倉庫中的事實表是指保存了大量業務度量數據的表，也是數據倉庫最核心的表。通常最有用的事實就是數字類型的事實和可加類型的事實，例如：銷售金額、成本等。通常事實表中的數據不允許修改，新的數據只是簡單地添加進去。事實表的特點是：數據量龐大、屬性列數少、持續增長，通俗理解實事表就是一張完整詳盡的業務表，而且會持續不斷有新的數據加進來。

圖1給出了一個比較典型的用于記錄商品銷售記錄的事實表結構。事實表的記錄通常會按照時間、主鍵等字段近似有序，或稱為具有有序趨勢，比如圖1中的“銷售時間”。而數據倉庫提供的很多操作也會基于這些近似有序的字段進行排序，以圖1的商品銷售記錄事實表為例，典型的業務有：

(1)繪制編號為1010的商品的銷售額曲線圖。這需要在檢索并計算得到該商品的結果后按照銷售時間排序。SQL語句如下：

SELECT銷售時間,實時價格*折扣*銷售數量

FROM商品銷售記錄

WHERE商品編號＝1010

ORDER BY銷售時間；

(2)以小時為單位生成所有商品銷售額的報表。這需要用到分組操作，因為分組結果集非常大，必須要采用排序聚合的分組算法。SQL語句如下：

SELECT to_char(銷售時間,'yyyy-mm-dd,hh24'),sum(實時價格*折扣*銷售數量)

FROM商品銷售記錄

GROUP BYto_char(銷售時間,'yyyy-mm-dd,hh24')。

由于數據倉庫處理的數據范圍跨度通常非常大，這也就意味著待排序的數據量也會非常大，甚至會超出物理內存，因此對超出物理內存的龐大規模數據集合排序，通常采用歸并排序算法，因為歸并排序需要進行頻繁的IO讀寫，所以排序性能也會奇慢無比。即使待排序的數據集合可以完全裝入物理內存并采用更高效的快速排序算法，也會因為巨大的數據集合而產生非常大的內存和計算開銷。另外，排序算法需要借助物化在完全排序后才可以返回結果(堆排序算法可以提前返回，但仍需要預先比較判斷一遍所有數據)，在數據倉庫中通常稱為啟動代價大，因此，看似簡單的繪制曲線圖和制作報表會涉及到很大的資源開銷。

數據倉庫中的時間、主鍵這些字段近似有序，主要是因為雖然這些數據是順序產生的，但由于并發裝載入庫和補錄歷史記錄操作，使得最終存儲的數據并不完全有序。再觀察商品銷售記錄事實表的銷售時間字段，會發現比較少量的無序記錄，通常稱為“異常”值，如圖2所示。

目前，數據倉庫為了優化統計查詢性能經常會采用列式存儲方式，圖3給出了一種商品銷售記錄表的列式存儲示意圖。列式存儲通常由多個被稱為Compress Unit(壓縮單元，簡稱：CU)的存儲單元構成。每一個CU由元信息和壓縮數據組成，元信息包括該CU單元的統計信息，包括最小值、最大值以及記錄數，壓縮數據部分包含實際的數據。列式存儲結構的數據倉庫同樣存在排序速度慢、占用資源大等的問題，如何對列式存儲結構的排序操作進行性能優化是目前迫切需要解決的問題。