[發(fā)明專利]一種基于向量化執(zhí)行的數(shù)據(jù)庫排序方法及系統(tǒng)

有效

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

1.一種向量化執(zhí)行的數(shù)據(jù)庫排序方法，其特征在于，包括：

步驟1，將輸入數(shù)據(jù)向量化為多個輸入數(shù)據(jù)行組；

步驟2，在計算節(jié)點的內存中開辟大小為最適粒度的緩沖區(qū)；該最適粒度的大小為該計算節(jié)點的處理器緩存大小除以最大排序/重排寬度所得的值；其中該最大排序/重排寬度為所有該輸入數(shù)據(jù)行組的所有排序列寬度總和與最大單列寬度中的最大值；

步驟3，將該輸入數(shù)據(jù)行組依次追加至該緩沖區(qū)的末尾空位；僅當該緩沖區(qū)滿或所有該輸入數(shù)據(jù)行組均已追加至該緩沖區(qū)時，將存入該緩沖區(qū)的輸入數(shù)據(jù)行組調入該處理器緩存進行排序以得到緩存輸出數(shù)據(jù)行組，將該緩存輸出數(shù)據(jù)行組輸出至該內存并清空該緩沖區(qū)；重復步驟3直到所有該輸入數(shù)據(jù)行組均已完成排序；

步驟4，當該內存滿或所有該緩存輸出數(shù)據(jù)行組均已輸出至該內存時，將該內存中的該緩存輸出行組排序以生成輸出數(shù)據(jù)行組，將該輸出數(shù)據(jù)行組保存至該計算節(jié)點的磁盤并釋放該內存；重復步驟4直到所有該緩存輸出數(shù)據(jù)行組均已完成排序；

步驟5，合并所有該輸出數(shù)據(jù)行組以得到順序排列的全序輸出數(shù)據(jù)行組。

2.如權利要求1所述的數(shù)據(jù)庫排序方法，其特征在于，所述步驟3的排序過程具體包括：

步驟31，以該緩沖區(qū)中的輸入數(shù)據(jù)行組為第一行組，將該第一行組調入該處理器緩存，并對該第一行組進行排序獲得對應該第一行組的每行的排序行號以生成第一行號數(shù)組；

步驟32，根據(jù)該第一行號數(shù)組對該第一行組進行重新組織，以生成順序排列的該緩存輸出行組；

步驟33，將該緩存輸出行組輸出至內存并清空該緩沖區(qū)。

3.如權利要求1所述的數(shù)據(jù)庫排序方法，其特征在于，所述步驟4的排序過程具體包括：

步驟41，以該內存中的緩存輸出行組為第二行組，對該第二行組進行排序以獲得對應該第二行組的每行的排序行號并生成第二行號數(shù)組；

步驟42，根據(jù)該第二行號數(shù)組對該第二行組進行重新組織，以生成順序排列的該輸出數(shù)據(jù)行組；

步驟43，將該輸出數(shù)據(jù)行組保存至該磁盤并釋放該內存。

4.如權利要求1所述的數(shù)據(jù)庫排序方法，其特征在于，步驟3中采用逐列拷貝將該輸入數(shù)據(jù)行組追加至該緩沖區(qū)。

5.一種向量化執(zhí)行的數(shù)據(jù)庫排序系統(tǒng)，其特征在于，包括：

向量化模塊，用于將輸入數(shù)據(jù)向量化為多個輸入數(shù)據(jù)行組；

緩沖區(qū)模塊，用于在計算節(jié)點的內存中開辟大小為最適粒度的緩沖區(qū)；該最適粒度的大小為該計算節(jié)點的處理器緩存大小除以最大排序/重排寬度所得的值；其中該最大排序/重排寬度為所有該輸入數(shù)據(jù)行組的所有排序列寬度總和與最大單列寬度中的最大值；

數(shù)據(jù)輸入模塊，用于將該輸入數(shù)據(jù)行組拷貝并依次追加至該緩沖區(qū)的末尾空位；

緩沖區(qū)數(shù)據(jù)排序模塊，用于對緩沖區(qū)內的輸入數(shù)據(jù)行組進行排序；其中僅當該緩沖區(qū)滿時，對存入該緩沖區(qū)的輸入數(shù)據(jù)行組進行排序以得到緩存輸出數(shù)據(jù)行組，將該緩存輸出數(shù)據(jù)行組輸出至該內存并清空該緩沖區(qū)；

緩沖區(qū)數(shù)據(jù)輸出模塊，用于將該緩沖區(qū)數(shù)據(jù)排序模塊獲得的多個該緩存輸出數(shù)據(jù)行組輸出至該內存；其中將該緩存輸出數(shù)據(jù)行組依次追加至該內存的末尾空位；

內存數(shù)據(jù)排序模塊，用于對該內存中的緩存輸出行組進行排序以生成輸出數(shù)據(jù)行組；其中當該內存滿或所有該緩存輸出數(shù)據(jù)行組均已追加至該內存時，將該內存中的緩存輸出行組排序以生成輸出數(shù)據(jù)行組。

6.如權利要求5所述的數(shù)據(jù)庫排序系統(tǒng)，其特征在于，該緩沖區(qū)數(shù)據(jù)排序模塊包括：

緩存排序模塊，用于對該緩沖區(qū)中的輸入數(shù)據(jù)行組進行排序；其中以該緩沖區(qū)中的輸入數(shù)據(jù)行組為第一行組，將該第一行組調入該處理器緩存，并對該第一行組進行排序獲得對應該第一行組的每行的排序行號以生成第一行號數(shù)組；

緩存重排序模塊，用于獲取該緩存輸出行組；其中根據(jù)該第一行號數(shù)組對該第一行組進行重新組織，以生成順序排列的該緩存輸出行組；

緩存輸出模塊，用于將該緩存輸出行組輸出至內存并清空該緩沖區(qū)。