基于云計算的多重查詢優化系統

葛 星,沈 耀,徐常亮

(1.上海交通大學計算機科學與工程系,上海200240;2.阿里云計算有限公司,杭州310099)

基于云計算的多重查詢優化系統

葛 星1,沈 耀1,徐常亮2

(1.上海交通大學計算機科學與工程系,上海200240;2.阿里云計算有限公司,杭州310099)

在常規海量數據分析作業中,CPU/IO密集型的查詢語句通常復雜、耗時并存在大量可復用的公共部分。如何檢測、共享和復用回歸查詢集中語句間的公共部分成為亟需解決的問題。為此,提出特征值索引方法,并構建適用于云計算場景的LSShare多重查詢優化系統。基于查詢語句的抽象語法樹將語句劃分為不同的查詢層次,針對每個查詢層次抽取特征向量并計算特征值。建立簡單高效的特征值索引表以識別多重查詢語句間的公共部分,并結合SQL重寫技術來復用其中的公共部分。隨著運行迭代次數的增加,LSShare系統將逐步優化云計算場景中的回歸查詢集。實驗結果表明,該系統在運行效率上優于傳統查詢語句系統,可節約近1/3的執行時間。

云計算;多重查詢優化;查詢處理;子表達式識別;海量數據處理;回歸查詢集

1 概述

多重查詢優化(Multiple Query Optimization, MQO)是數據庫領域的典型問題,它描述了如何高效地利用公共任務來優化多個查詢語句從而產生執行結果。給定一個查詢語句集,每個查詢語句都將產生一個包含若干執行計劃的候選集合。其中,每個執行計劃又有一個包含若干任務的候選集合。MQO問題旨在為每個查詢語句選擇適當的執行計劃,從而通過高效復用各執行計劃間的公共任務(一次執行)來最小化整個語句集合的執行時間。對MQO問題的研究可以追溯到20世紀80年代, Sellis[1]首次系統地定義了該問題,同時也證明了該問題是一個 NP-Hard問題[2]。此后,大量啟發式[3-5]和基于遺傳算法[6]的近優解法被提出。

MQO問題在關系數據庫領域已經得到了廣泛深入的研究[7-9],但近期基于云計算海量數據處理中的MQO問題逐漸成為熱點[10-11]。隨著云計算的出現,網絡點擊流、網絡爬蟲、服務日志等應用每天持續不斷地產生海量數據[12]。云計算應用通常維護一個數量巨大且持續增長的查詢語句集來處理每天例行性的數據作業。傳統MQO問題的解決方案通過構建每個語句的執行計劃候選集來共享少量語句之間的公共任務,而針對大量語句將造成冗雜龐大的候選集和極其耗時的檢測代價。同時,這些解法通常要求查詢集以批處理方式進行,因而無法統一處理不定期加入到集合中的語句。針對關系數據庫系統,僅在一個很小的范圍內(不超過10條)近似最優算法[13]才能產生高效的全局計劃。文獻[14]針對類似的多重查詢腳本場景,通過收集本地歷史數據進行研究優化。然而,如何在云計算中解決回歸查詢集場景下的MQO問題依然十分具有挑戰性。云場景中的查詢語句集包含如下特征:(1)該集合包含大量結構相近、操作相似的語句;(2)該集合是參數化的;(3)該集合是回歸化的;(4)該集合是動態增長的。稱包含上述4種特征的集合為回歸查詢集。以Alibaba云計算系統數據存儲與分析平臺開放數據處理服務(Open Data Processing Service,ODPS)的日常回歸查詢集為例:該集合包含超過2 000條結構相近的查詢語句;依據簡單的字符串規則定期修改其中的時間字段或地域字段;通常按時或天為單位周期性運行以支持關鍵性的應用決策;根據不斷變化的業務需求,將不定期有新的查詢語句加入其中。ODPS平臺每天處理該回歸查詢集以產生相關部門的日常數據報表。

現代企業通常使用回歸查詢集以支持PB級的海量數據處理應用。傳統數據庫中的MQO問題已經有了大量的近優解法,但并不適用于云計算場景。在云計算場景中,如何定義、檢測和復用回歸查詢集中語句間的公共部分成為研究的關鍵。本文針對云場景下的多重查詢優化問題,詳細介紹了該問題的基本概念、查詢語句間特征值抽取與特征值計算、LSShare系統的實現。

2 基于云計算的特征值索引方法

本文基于云計算場景的MQO問題,提出了特征值索引方法并構建了LSShare多重查詢優化系統。首先,基于查詢語句的抽象語法樹(Abstract Syntax Tree,AST)將語句劃分為不同的查詢層次,針對每個查詢層次抽取特征向量并計算特征值。然后,建立簡單高效的特征值索引表以識別多重查詢語句間的公共部分。最后,結合SQL重寫技術來復用其中的公共部分。通過迭加運行次數,本文系統將隨時間逐步優化云計算場景中的回歸查詢集。

2.1 基本概念

本文以SQL語句Q1為例說明本文方法中的基本定義。每個SQL語句都可以處理為一棵抽象語法樹AST,該抽象語法樹描述了SQL語句的語法結構。一個SQL語句依據其AST樹結構,可以劃分為不同的查詢層次。查詢層次描述了一顆抽象語法樹或抽象語法子樹。

(select*from src)a where id＞10 group by id

如圖1所示,Q1包含2個查詢層次:Q1外層L1和Q1的子句L2,并且邏輯上前者包含后者。一個查詢層次描述了其查詢參數在該查詢對象上的計算、操作和抽取的結果。Q1外層 L1中“from (select*from src)a where id＞10 group by id”為其查詢對象,“id,sum(value)as cnt”則是該查詢層次的查詢參數。查詢參數描述了針對查詢對象的列抽取和列計算操作,而查詢對象則包含了完整的特征值抽取的信息。更詳細地,“where id＞1”和“group by id”組成了該查詢對象的過濾特征,而“select*from src”則描述了該查詢對象的流特征。

圖1 Q1語句結構分析

過濾特征描述了一個查詢中所有行相關的過濾操作。通過定義過濾特征來保證行信息在數據流過程中的完整性。過濾特征包含了許多SQL的操作。比如語法“WHERE”描述了行的刪除操作,語法“ORDER BY”描述了行的排序操作,語法“LIMIT”描述了行的排序和刪除操作。這些都作為數據流的過濾特征信息進行保存。

流特征則描述了數據的分支來源結構。查詢語句可以根據其數據源的流特征分為如下類型: (1)TABREF類型,描述了數據來源于物理表; (2)SUBQUERY類型,描述了數據來源于一個子查詢,又可分為一般的 SUBQUERY和 UNION_ SUBQUERY;(3)JOIN類型,描述了數據源于兩表或多表JOIN操作。

2.2 特征向量抽取

特征向量是一個查詢層次邏輯結構的抽象定義。它包含了完整的數據流向和過濾操作信息,因此,可以作為公共部分的特征標識。

圖2詳細描述了特征值索引算法針對一個查詢層次的特征值定義。首先,將查詢層次中的表達式進行標準化處理。然后,將查詢層次的AST樹拍平為包含完整信息的SqlData對象。遞歸遍歷該對象并根據需要進行必要的信息提取和擴展。SqlData對象包含了一個查詢對象所應具備的流特征和過濾特征。過濾特征由諸如“ORDER BY”和“WHERE”等條件構成。流特征則由不同的數據流結構諸如“SUBQUERY”和“UNION_SUBQUERY”構成。其中,“SUBQUERY”和“UNION_SUBQUERY”遞歸地使用其子查詢的特征值結果。如圖2所示,本文將一個查詢層次的查詢對象抽取為一個特征向量。

圖2 特征向量定義

在具體實現上,選擇開源工具 ANTLR來對SQL語句進行詞法分析和語法分析,生成一顆AST樹。針對每個查詢層次依據其查詢對象信息來遞歸構造特征向量。該特征向量使用JSON格式字符串存儲。例如對于查詢語句Q1,根據其AST樹可以劃分為2個QUERY層次,通過算法處理可以抽取出如下2個特征向量(由JSON串來表示):

此為內層SUBQUERY(即圖1中的L2層次)的特征向量,通過MD5算法計算得特征值Sig1為: e960c2b5a542fca4feb4c0e549caf6ff。

此為外層QUERY(即圖1中的L1層次)的特征向量,通過特征值計算其值Sig2為e960c2b5a 542fca4feb4c0e549caf6ff。需要注意的是,特征向量Vector_2中使用了 Vector_1的特征值 Sig1作為sourceValue。

2.3 特征值計算

特征值是特征向量計算后的固定長度的數值結果。最終以特征值為標準來比較和識別單個SQL語句內不同查詢層次間的公共部分,以及不同SQL語句間的不同查詢層次間的公共部分。

在實現上使用實際應用廣泛的MD5算法將JSON格式定義的特征向量計算為特征值。然后,將這些特征值用 Hibernate持久化為特征值索引表。對于新加入的語句,計算其特征值并查找索引表,如果命中,則說明兩者包含公共部分,結合SQL語句重寫技術來復用兩者之間的公共部分。

3 系統實現

針對云計算中的回歸查詢集場景實現了一個高效的多重查詢優化系統,如圖3所示,該系統可以方便地集成和擴展到其他分布式系統中。

圖3 多重查詢優化系統架構

使用標準查詢語句集模擬了真實生產集群上的日常作業行為。該語句集包含大量結構復雜的查詢語句,這些語句每天都會被自動化替換其中的日期或地點參數。每天不定期會有一些新的查詢語句加入到該固有查詢集中。本文系統使用特征值索引方法來初始化該查詢語句集并依此生成特征值索引表。運行時它處理不定期新加入的查詢語句并計算該單個語句的特征值。如果該語句的特征值命中特征值索引表中某一項,即說明新加入的查詢語句與原有的查詢語句集有公共部分可以復用。基于該特征值的重復頻度與復用深度的權衡,為用戶提供可選的SQL重寫語句。將改寫后的語句加入該日常回歸查詢集并同時優化該集合中的剩余部分。

4 實驗結果與分析

本文原型系統LSShare基于Alibaba云平臺的離線數據處理服務ODPS實現。使用MapReduce框架針對每個查詢語句的不同查詢層次進行特征向量抽取和特征值計算,并據此建立特征值索引表。實驗集群包含 114個服務器節點,每個節點配置2.40 GHz CPU和24 GB內存。特征索引表方法的具體算法基于Java語言實現。

使用基于TPC-H測試標準2種典型的查詢語句集:阿里金融離線數據測試機和淘寶離線數據測試集。每個查詢集包含近10 000條復雜耗時的類SQL語句。為縱向對比不同規模的查詢集之間的效率差異,實驗從規模較大的語句集中隨機抽取小規模數量的查詢語句并構建成一個新的語句集合。

4.1 覆蓋率分析

覆蓋率分析目的在于分析回歸查詢集中公共部分所占的百分比。圖4橫向比較顯示,相同類型的回歸查詢集有大致相同的公共部分覆蓋率。縱向比較顯示,不同規模的查詢集均有近30%的公共部分可以復用,并且隨著語句數量的增長,本文系統在一定限度內能檢測到更高的公共部分覆蓋率。

圖4 覆蓋率分析

以圖4中包含2 000條SQL語句的查詢集為例,經過特征值索引方法,這些語句被拆分為7 515個查詢層次,每個查詢層次抽取為一個特征向量并依此計算為特征值。即一個查詢語句平均包含4個查詢層次,這說明這些查詢語句通常比較復雜和耗時。實驗數據顯示,該集合在索引表中有2 631個重復特征值,即說明公共部分的覆蓋率在31.24%。其中,單個索引重復的最大次數為72次。結果表明,該特征值索引方法針對回歸查詢集的公共部分檢測具有極高的效率。

4.2 可擴展性分析

可擴展性分析的目的在于分析本文系統在查詢語句集不斷增長的情況下的性能。通過特征值索引表的初始化時間來度量本文系統的可擴展性。本文系統利用MapReduce框架并行處理上萬條查詢語句,重復進行實驗并記錄不同規模的語句集耗費的平均時間。

圖5表明不同規模的查詢語句集構建特征值索引表的時間緩慢增長。其主要原因是隨著語句集規模的增加,查詢語句長尾的出現概率不斷增加,從而導致執行時間緩慢增長。剔除個別查詢語句的長尾現象,結果表明本文系統隨查詢語句集規模的增長有著良好的可擴展性。

圖5 可擴展性分析

4.3 優化性能分析

優化性能分析的目的在于度量本文系統在時間維度上的優化效益。此外,將本文系統與傳統的Hive系統進行對比實驗,并著重探討了不同語句類型的加速比。

為模擬回歸查詢集場景,實驗中使用一個包含5 000條語句的查詢語句集,每次都新加入近1%的查詢語句。實驗重復進行100次,對本文系統和Hive系統的執行時間進行比較,如圖6所示。

圖6 LSShare與Hadoop/Hive系統優化性能對比

從圖6中可以得到以下結論:(1)隨著運行迭代次數的增加,本文系統針對固定查詢語句集的查詢速度將逐漸加快。而Hive系統的運行時間則隨迭代次數的增加基本恒定。這意味著基于反饋機制的系統優化效益將隨著迭代次數的增加逐漸均攤到整個查詢集上。(2)當迭代次數較少時,本文系統的執行時間較高。反之,當迭代次數較多時本文系統的執行效率將遠超Hive。實驗結果表明,在均攤分析意義上LSShare性能優于Hive。

圖7針對不同類型的查詢語句進行對比,發現查詢語句中最有優化價值的是包含“UNION”或“JOIN”結構的復雜子查詢。本文系統通過復用其中的公共部分能夠節約大概20% ～50%的執行時間。

圖7 不同類型的查詢語句優化性能對比

5 結束語

本文提出了特征值索引方法來解決回歸查詢集中的 MQO問題。結合 SQL語句重寫技術,在Alibaba的云計算平臺上實現了該優化系統。實驗結果表明,該優化系統簡單高效。今后將通過改進特征值定義以識別更多的公共部分,使得該優化系統更智能化和自動化,并將其擴展應用到其他分布式系統中。

[1] Sellis T K.Multiple-query Optimization[J].ACM Trans.on Database System,1988,13(1):23-52.

[2] Sellis T K,Ghosh S.On the Multiple-query Optimization Problem[J].IEEE Trans.on Knowledge and Data Engineering,1990,2(2):262-266.

[3] Shim K,Sellis T K,Nau D.Improvements on a Heuristic Algorithm for Multiple-query Optimization[J].Data and Knowledge Engineering,1994,12(2):197-222.

[4] Roy P,Seshadri S,Sudarshan S,et al.Efficient and Extensible Algorithms for Multi Query Optimization [J].ACM SIGMOD Record,2000,29(2):249-260.

[5] Cosar A,Lim E P,Srivastava J.Multiple Query Optimization with Depth-firstBranch-and-bound and Dynamic Query Ordering[C]//Proceedings of the 2nd International Conference on Information and Knowledge Management.New York,USA:ACM Press,1993:433-438.

[6] Bayir M A,Toroslu I H,Cosar A.Genetic Algorithm for the Multiple-query Optimization Problem[J].IEEE Trans.on Systems,Man,and Cybernetics,2007,37(1): 147-153.

[7] Nykiel T,Potamias M,MishraC,etal.MRShare: Sharing Across Multiple Queries in MapReduce[J]. Proceedings of the VLDB Endowment,2010,3(1/2): 494-505.

[8] Elghandour I,Aboulnaga A.Restore:Reusing Results of MapReduce Jobs[J].Proceedings of the VLDB Endowment,2012,5(6):586-597.

[9] Herodotou H,Lim H,Luo G,et al.Starfish:A Selftuning System for Big Data Analytics[C]//Proceedings of the 5th Biennial Conference on Innovative Data Systems Research.Asilomar,USA:[s.n.],2011: 261-272.

[10] Bruno N,Agarwal S,Kandula S,et al.Recurring Job Optimization in Scope[C]//Proceedings of 2012 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2012:805-806.

[11] Lee R,Luo T,Huai Y,et al.YSmart:Yet Another SQL-to-MapReduce Translator[C]//Proceedings of the 31st InternationalConference on Distributed Computing Systems.Washington D.C.,USA:IEEE Computer Society,2011:25-36.

[12] Dean J,Ghemawat S.MapReduce:Simplified Data Processing on Large Clusters[J].Communications of the ACM,2008,51(1):107-113.

[13] Kalnis P,Papadias D.Multi-query Optimization for Online Analytical Processing[J].Information Systems, 2003,28(5):457-473.

[14] Bruno N,Agarwal S,Kandula S,et al.Recurring Job Optimization in Scope[C]//Proceedings of 2012 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2012:805-806.

編輯 陸燕菲

Multiple Query Optimization System Based on Cloud Computing

GE Xing1,SHEN Yao1,XU Chang-liang2
(1.Department of Computer Science and Engineering,Shanghai Jiaotong University,Shanghai 200240,China;
2.Alibaba Cloud Computing Co.,Ltd.,Hangzhou 310099,China)

In routine massive data analysis queries,the CPU/IO intensive analysis queries are complex and timeconsuming,but share common components.It is challenging to detect,share and reuse the common components among thousands of SQL-like queries.Aiming at these problems,this paper proposes the signature-index approach and implements the LSShare system to solve the Multiple Query Optimization(MQO)problem in the cloud with a recurring query set.It generates signatures for each query based on Abstract Syntax Tree(AST).Then it makes a simple but efficient index for further identifying and sharing common components of multiple queries combined with SQL-rewriting techniques.LSShare system gradually optimizes regression query set in the cloud computing scene as the superposition of run number.Experimental results demonstrate,the system is superior to the traditional query optimization in share equally,and it can save nearly a third of the execution time.

cloud computing;Multiple Query Optimization(MQO);query processing;subexpression identification; massive data processing;recurring query set

1000-3428(2014)09-0046-05

A

TP311.13

10.3969/j.issn.1000-3428.2014.09.010

國家“863”計劃基金資助重大項目“以支撐電子商務為主的網絡操作系統研制”(2011AA01A202)。

葛 星(1987-),男,碩士研究生,主研方向:云計算,分布式計算;沈 耀(通訊作者),副教授;徐常亮,博士。

2013-09-25

2013-11-11E-mail:gexing111@126.com