[發明專利]基于數據模式轉換和并行框架的關系數據查詢優化方法

有效

• 申請號: 201710249567.6
• 申請日: 2017-04-17
• 公開（公告）號: CN107169033B
• 公開（公告）日: 2020-03-31
• 發明（設計）人: 聶鐵錚;申德榮;寇月;于戈;高晶;房俊;楊冬菊
• 申請（專利權）人: 東北大學;北方工業大學
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/28
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 梁焱

1.一種基于數據模式轉換和并行框架的關系數據查詢優化方法，其特征在于：包括以下步驟：

步驟1：對關系模型數據上復雜查詢語句進行結構分析；

首先對執行性能較低的關系數據庫上的結構化查詢語句，即SQL查詢語句，轉化為SQL語法解析樹結構，以進行下一步分析，找出關系數據庫上的SQL查詢語句中能夠通過轉換為新的數據模式存儲數據和并行查詢方式進行優化以提高查詢效率的查詢語句結構，以用于在下一個步驟中生成數據的鍵值模型存儲結構；要找出的能進行優化的查詢語句結構包括基于關系表關鍵字作為連接屬性的多表連接查詢結構、能聚合文本屬性值的嵌套查詢結構、能并行執行的嵌套查詢結構和查詢謂詞中包含的編碼屬性匹配查詢；

其中，找出基于關系表關鍵字作為連接屬性的多表連接查詢結構的方法為：對關系模式數據上的SQL查詢語句構建關系代數形式的查詢樹，在關系代數查詢樹上通過關系運算操作符的等價變換，找出多個關系表的連接查詢結構，其中關系表表示為T1＝{K1,A1},T2＝{K2,A2},...,Tn＝{Kn,An}，Ti表示一個關系表，Ki表示關系表Ti的連接屬性集合且為表Ti的主鍵，Ai表示關系表Ti的非連接屬性集合，i＝1,2,…,n，即Qs＝T1∞T2∞...∞Tn，記錄這個基于關系表關鍵字作為連接屬性的多表連接查詢結構Qs；

找出可聚合文本屬性值的嵌套查詢結構的方法為：查找SQL查詢語句中在關系表文本屬性上的文本模糊匹配查詢，判斷這個文本模糊匹配查詢是否在一個exists操作符的嵌套相關子查詢結構中，如果該子查詢結構中符合查詢結構“SELECT*FROM T WHERE T.Ak＝U.Aand Ct”，其中T表示子查詢關系表，U表示父查詢關系表，Ak表示相關子查詢連接屬性，Ct表示在文本屬性At上的文本模糊匹配查詢謂詞，則標記該子查詢為可聚合文本屬性值的查詢結構；

找出能并行執行的嵌套查詢結構中，在查詢語句中發現并標記不相關子查詢，先執行不相關子查詢，同時將父查詢的中間結果數據進行分片，然后將子查詢結果發送到各個中間結果數據；

找出查詢謂詞中包含的編碼屬性匹配查詢的方法為：在SQL查詢語句中，如果一個查詢謂詞的查詢屬性A為基于一個代碼表Rc的屬性，即該屬性上A的屬性值W依賴于代碼表Rc中的有限個編碼值，屬性值W為單個編碼值或由多個編碼值和分隔符拼接而成的文本，同時查詢條件為基于一個或多個編碼值的“邏輯或”匹配方式，即假設屬性值為“a1,a2,…,an”，查詢謂詞中待匹配值為“b1,b2,…,bm”，如果存在ai＝bj，i∈1,2,…,n，j∈1,2,…,m，則記錄該查詢謂詞的查詢屬性；所述代碼表指一個記錄數量固定且表示一種編碼規則的關系表，關系表中包含編碼屬性和語義屬性；

步驟2：構建新的數據存儲結構；

基于對數據模式上的SQL查詢語句的分析，結合查詢所涉及關系表的關系模式結構，進一步構建新的數據模式存儲結構，以實現通過新的數據模式的數據存儲提高查詢執行效率，新的數據模式為關系模型或鍵值模型；

構建新的數據模式存儲結構的具體步驟包括：

步驟2-1：合并關系表以生成新的數據模式結構；

對于在找出基于關系表關鍵字作為連接屬性的多表連接查詢結構的過程中標記出的SQL查詢語句中所包含的關鍵字作為連接屬性的多表連接查詢結構，將其中的多個關系表涉及的關系表集合{T1,T2,...,Tn}合并為新的數據模式結構，表示為Ts(Key,V),其中Key為關鍵字，其結構由關系表中的連接屬性{K1,K2,...,Kn}中所包含的屬性構成，V為新關系表中的非主屬性集合，對應關系表集合中的非主屬性集合{A1,A2,...,An}；

步驟2-2：使用位向量編碼方式優化基于代碼表存儲的屬性；

對于在找出查詢謂詞中包含的編碼屬性匹配查詢過程中找出的查詢謂詞涉及的編碼屬性，基于代碼表中的編碼順序將屬性值基于位向量形式進行重新編碼，生成新的編碼屬性Ac；編碼方式為，對于一個記錄在找出的查詢謂詞涉及的編碼屬性上的屬性值構建一個與代碼表中記錄數量相同長度的二進制位向量，如果在原屬性值中包含對應二進制位上的編碼值，則該位上標記為1，否則標記為0；轉換后數據模式中位向量編碼的屬性值以二進制位向量或整型存儲；

步驟2-3：生成具有聚合文本屬性值的模式結構；

對于在找出能聚合文本屬性值的嵌套查詢結構過程中找出的聚合文本屬性值的嵌套查詢結構，生成相關屬性的符合結構屬性，通過聚合同一個查找鍵值下多個記錄的多個文本屬性值，實現在查詢執行過程中一次訪問全部文本屬性值內容并進行模糊匹配，從而提高查詢效率；新的具有聚合文本屬性值的模式結構的構建方式為，對于相關子查詢“SELECT*FROM T WHERE T.Ak＝U.A and Ct”中的關系表T，文本屬性At為文本匹配查詢謂詞Ct所包含的查詢屬性，創建新的關系表T'，T'中使用屬性Ak作為主關鍵字，對于關系表T中屬性Ak上具有相同取值的多個記錄，使用指定分隔符將多個記錄中文本屬性At的屬性值進行拼接，生成新關系表T'中新文本屬性At'的對應屬性值；

步驟3：基于步驟2中所生成的新的數據模式存儲結構，實現在數據存儲上的轉換處理，將關系模型數據庫中存儲的數據轉存到新的數據模式存儲系統中；

所述步驟2中構建的新的數據模式為關系模型時，數據存儲上的轉換處理方式為：

(1)執行合并關系表數據模式的數據轉換，基于合并后的關系表創建新表T'，新表數據從合并前的關系表導入；(2)對于關系模式中進行位向量編碼轉換的屬性，對于一個記錄中屬性值的編碼轉換方式是為該屬性值構建一個與代碼表中記錄數量相同長度的二進制位向量Bv，如果在原屬性值中包含對應二進制位上的編碼值，則該位上標記為1否則標記為0，再將該位向量按照64位長度整數進行分割和補位生成有一個或多個整數表示的位向量值，如果用多個整數表示，則轉換后可生成多個位向量屬性；(3)對于具有聚合文本屬性值的數據模式的數據存儲轉換，在新的關系表T'中增加屬性At'，子查詢中關系表的文本屬性為At，屬性At'的屬性值由其對應的主鍵在子查詢關系表中對應記錄分組在屬性At上的值集合使用分隔符進行拼接生成；(4)其它不涉及模式轉換的關系表保持原結構不變；

所述步驟2中構建的新的數據模式為鍵值模型時，數據存儲上的轉換處理方式為：

(1)對于合并關系表所生成的新的表結構創建列族CF(Colunm Family)，如果作為連接屬性的主鍵為單屬性主鍵，則主鍵Ak作為行鍵(Row Key)，行鍵取值為主鍵屬性值；如果連接屬性的主鍵為屬性組，則屬性組組合作為行鍵，行鍵取值為主鍵屬性結合連接符的拼接文本，同時主鍵中包含的每個屬性轉換為一個列；原始關系表中的每個普通屬性轉換為列族CF中的一個列，數據由原關系表導入；(2)對于位向量編碼方式屬性的數據轉換，如果底層存儲引擎支持整型數據類型的定義，則采用與關系模型存儲轉換中相同的方法對屬性值進行編碼轉換，如果底層存儲引擎只支持文本屬性存儲，則不進行屬性編碼的轉換；(3)對于具有聚合文本屬性值的數據模式的數據存儲轉換，在列族CF(Colunm Family)中增加一個文本數據列Rt(即Colunm)，Rt列上的值同樣由具有多個相關子查詢連接屬性Ak的屬性值記錄的文本屬性At的屬性值拼接生成；(4)對于其它關系表都將轉換為列族，將關系表的主鍵轉換為行鍵，關系表的其它屬性和屬性值轉換為對應的列和列值；

步驟4：進行查詢語句的轉換，由于SPARK SQL能夠直接支持SQL查詢語句，因此查詢語句的轉換僅針對數據模式的變化做出相應修改；

步驟5：基于SPARK SQL查詢生成SPARK任務并執行該任務，SPARK SQL查詢任務的生成基于查詢語句轉換的結果進行，基于步驟4的轉換結果進行判斷，如果沒有生成不相關子查詢的獨立任務，則整體執行轉換后的查詢語句，直接將轉換后的查詢語句作為查詢任務提交給SPARK SQL引擎執行查詢操作，執行后結果數據以SchemaRDD形式返回，如果生成了不相關子查詢的獨立任務，則基于SPARK SQL查詢的構建并執行查詢處理任務。