[發明專利]一種基于向量化執行的數據庫排序方法及系統

有效

• 申請號: 201810588554.6
• 申請日: 2018-06-08
• 公開（公告）號: CN109002467B
• 公開（公告）日: 2021-04-27
• 發明（設計）人: 申毅杰;熊勁
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F16/2455
• 分類號: G06F16/2455
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國;梁揮

本發明涉及一種向量化執行的數據庫排序方法，包括：將輸入數據向量化為多個輸入數據行組；在計算節點的內存中開辟大小為最適粒度的緩沖區；將該輸入數據行組依次追加至該緩沖區的末尾空位；僅當該緩沖區滿或所有該輸入數據行組均已追加至該緩沖區時，將存入該緩沖區的輸入數據行組調入該計算節點的處理器緩存進行排序以得到緩存輸出數據行組，將該緩存輸出數據行組輸出至該內存并清空該緩沖區；當該內存滿或所有該緩存輸出數據行組均已輸出至該內存時，將該內存中的該緩存輸出行組排序以生成輸出數據行組，將該輸出數據行組保存至該計算結點的磁盤并釋放內存；合并所有該輸出數據行組以得到順序排列的全序輸出數據行組。

技術領域

本發明涉及數據管理領域，具體涉及一種基于向量化執行的數據庫排序方法及系統。

背景技術

在數據庫領域中，排序(Sort)是最為重要的操作之一，廣泛被用于實現：分組(grouping)、聚合(aggregation)、連接(join)和shuffle等操作。為了處理任意大小的數據集(可能大于內存容量)，數據庫中的sort一般均指的是外部排序(external sort)。外部排序算法可分為兩個階段，被稱為兩階段多路歸并排序(Two-phase,Multiway Merge-sort,TPMMS)，其過程如下：

1)基于內存的排序，將需要排序的數據在內存中進行緩存，當無更多可用內存時，進行一次基于內存數據的局部排序，并將結果溢寫(spill)到磁盤文件中。

2)當所有需要排序的數據都進行完內存排序，形成多個局部序時，采用多路歸并算法同時處理多個局部序，并生成最終的、全局的序。

向量化執行(Vectorized Execution)是最早在分析型數據庫MonetDB中提出的，提升分析類(analytical)查詢執行性能的執行引擎優化技術。

為了執行一條SQL查詢，執行引擎會按照其語義將執行邏輯組織成一棵算子樹，如圖1A所示，傳統執行引擎的算子樹每次處理一條記錄最終產生結果，而Vectorizedexecution將迭代粒度從一行變成了行組(Record Batch)，如圖1B所示，在Record Batch內邏輯數據行Record(如圖2A所示)逐列組織在一起(如圖2B所示)，并逐列處理。

通過將迭代粒度變為每次處理Record Batch，Record Batch內按列組織、逐列處理，Vectorized execution被證明可以有效提升分析類查詢的執行效率。其優勢具體在于減少解釋執行開銷：從每次處理一行變為每次處理行組(N行)，函數調用數目減少為原來的1/N；更好的數據局部性和代碼局部性，因而可以更好地利用到CPU Cache；為編譯器和CPU提供了進一步自動優化的可能性。

為了在分析型數據庫中實現向量執行，其關鍵問題之一就在于如何高效地實現向量化Sort。

TimSort是結合了合并排序(merge sort)和插入排序(insertion sort)的混合排序算法，這種算法首先識別數據中已經存在的順序，而后利用這些局部序的知識來更高效地排出全序。概括地說，TimSort分成了兩個過程：1)識別(排列)大于最小個數序列(identifyruns)，順序掃描要sort的序列，識別其中的有序部分(或對無序數據進行插入排序)，使得有序部分長度達到算法設定的最小值(minimum size)；2)將識別出的最小序兩兩合并(merge sort)最終拿到全序。

針對Sort的優化當前有：