[發(fā)明專利]一種非等值關聯(lián)子查詢的優(yōu)化方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201810097136.7
• 申請日: 2018-01-31
• 公開（公告）號: CN108874849B
• 公開（公告）日: 2020-12-25
• 發(fā)明（設計）人: 何文婷;程學旗;鄭天祺;張志斌;郭嘉豐;趙鵬
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F16/2453
• 分類號: G06F16/2453
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權代理有限公司 11006
• 代理人: 祁建國;梁揮

本發(fā)明公開了一種非等值關聯(lián)子查詢的優(yōu)化方法和系統(tǒng)，其特征在于，包括：獲取關聯(lián)子查詢的外表關聯(lián)列的取值集；根據(jù)該關聯(lián)子查詢中操作符的類型和該取值集，建立該關聯(lián)子查詢的外表關聯(lián)列到內表關聯(lián)列分區(qū)的映射關系；根據(jù)得到的分區(qū)集合，對該關聯(lián)子查詢的內表進行分區(qū)，同時依據(jù)該關聯(lián)子查詢中內表的查詢聚合函數(shù)，獲取關聯(lián)子查詢在各分區(qū)的中間結果狀態(tài)信息；根據(jù)該映射關系，遍歷該外表關聯(lián)列，通過聚合對應的分區(qū)集的中間結果狀態(tài)信息，得到外表中各關聯(lián)列對應的子查詢結果。本發(fā)明具有的技術效果包括：通過對內表進行分區(qū)，并重復利用各分區(qū)的中間結果從而得到最終的子查詢結果集，以提升查詢性能。

技術領域

本發(fā)明涉及數(shù)據(jù)庫關系系統(tǒng)領域，特別涉及一種非等值關聯(lián)子查詢的優(yōu)化方法和系統(tǒng)。

背景技術

子查詢是指查詢語句作為另一個語句的查詢條件出現(xiàn),關聯(lián)子查詢是指子查詢的查詢條件依賴于父查詢。典型的非等值關聯(lián)子查詢如下：

select X.a,X.b from X where X.c

(select avg(Y.c)from Y where Y.d【OPERATOR】X.d)

其中關聯(lián)子查詢和外查詢的關聯(lián)列的操作符即上述【OPERATOR】包括：?。?,＝,,＝,in,not in,between and等。由于子查詢用到外查詢的結果，所以目前現(xiàn)有的實現(xiàn)技術包括以下三種實現(xiàn)方案：

1、tuple-at-a-time(nested iterator):從外表X中每得到一個d的值，傳給子查詢，再執(zhí)行子查詢得到子查詢的結果。對于X.d中有重復值的情況，有以下兩種方式來避免計算：一種是對外表列到子查詢結果進行緩存，當有重復的外表關聯(lián)列出現(xiàn)時則能緩存命中，從而避免計算；另一種方式是對外表關聯(lián)列進行排序，以將相同值的外表列放在一起，一次性識別，該方法也能避免重復計算。若內表的關聯(lián)列有索引時，能起到一定的加速作用。

2、semi join/anti join/outer join:將外表X和內表Y做笛卡爾積，從中篩選出滿足關聯(lián)條件的記錄，再獲得子查詢對應的結果列。

3、sort-merge join:若OPERATOR為,＝,,＝且子查詢的select列為max取最大值/min取最小值的聚合函數(shù)，那么可以先將外表和內表的關聯(lián)列分別進行排序，再通過類似歸并排序比較的方法得到子查詢的結果，通過一些緩存策略可以實現(xiàn)部分結果的復用。例如子查詢?yōu)閟elect max(Y.c)from Y where Y.dX.d當X和Y表分別對d列進行降序排序，假設X.d的第k-1行已處理完時，Y.d處理到m行，內查詢結果為maxk，則處理到X.d第k行時，其內查詢結果為max(maxk,Y.d(m-n行)的max(Y.c))其中n行是Y.d中X.d第k行值最小的值所在的行數(shù)。

而以上現(xiàn)有技術均存在各自的問題：

第一種方法性能較差，雖然能避免相同值的外表列重復計算子查詢，但是對于子查詢的計算，不同值的外表列仍然需要全部掃描內表，則得到所有子查詢結果的時間開銷為外表關聯(lián)列的不同值個數(shù)*掃描內表對比及最終計算的時間開銷。而本發(fā)明由于利用了子查詢的中間結果，只需要掃描一次內表即可，因此極大的提升了性能。

第二種方法同樣存在1)中的問題。

第三種方法使用條件有限：首先內外表的關聯(lián)條件只能為一個表達式，且類型只能為,＝,,＝四種，不支持集合操作in,not in，不支持beween and及不等于！＝操作及多個表達式的組合例如Y.dX.d and Y.dX.d+10。其次子查詢的查詢列只支持max/min/sum/count。再者，該技術需要對內外表按照關聯(lián)列進行排序，時間消耗大。而本發(fā)明支持的子查詢關聯(lián)操作符的種類多包括集合且支持多種比較操作符表達式的組合，更具有通用性。