分布式順序表類SQL技術的實現和優化

摘 要： 針對DOT系統，設計實現并優化了類SQL的查詢技術，首先分析了傳統數據庫在查詢上的優化策略，比較了傳統數據庫和DOT系統在查詢方面的異同。通過參考一般數據庫的SQL語句的設計規范，為DOT設計了一套類SQL語句。后續對設計的類SQL語句進行詞法語法分析，構建查詢樹。同時，借鑒傳統數據庫的查詢優化策略，結合DOT系統的特點對查詢進行優化。最后在開源的ApacheHBase典型的DOT系統的基礎上，實現了上述類SQL語句的所有解析和優化內容。

關鍵詞： 分布式順序表； 類SQL語句； 查詢優化； HBase索引優化

中圖分類號： TN911?34； TM417 文獻標識碼： A 文章編號： 1004?373X（2016）15?0103?05

Abstract： Aiming at the distributed ordered table （DOT） system， the SQL?like query technology was designed， implemented and optimized. In this paper， the optimization strategy of the traditional database is analyzed for query， and the query differences between the DOT system and traditional database are compared. Referring to the design specifications of the general database′s SQL statement， a set SQL?like statement was designed for DOT. The designed SQL?like statement is analyzed with morphology and grammar to establish the query tree. In combination with the query optimization scheme of the traditional database and cha?racteristics of DOT system， the query was optimized. All analysis and optimization contents of SQL?like statement were realized based on the open source ApacheHBase.

Keywords： distributed ordered table； SQL?like statement； query optimization； HBase index optimization

0 引 言

網絡應用的普及對海量數據的存儲和操作處理以及各種處理能力的可擴展性、可靠性和高效性提出了很大的挑戰，而現有數據模型和相關技術已不能勝任[1]。為了應對上述挑戰，業界提出了NoSQL數據庫。這些NoSQL數據庫可以模型化為分布式順序表（DOT）系統，但是DOT系統對SQL規范中查詢特性的支持并不完美[2]。

隨著網絡的發展，數據量出現爆炸式的增長，現有的關系型數據庫處理這些大數據已經出現瓶頸。進而有了DOT系統的出現，但現有的DOT系統對SQL查詢特性的支持并不是特別的理想[3]。

1 類SQL語句的設計與解析實現

在實現過程中首先根據SQL的設計規范，設計出一套適用于DOT系統的類SQL語句。用戶根據類SQL規范提交查詢請求，然后系統對類SQL查詢語句進行詞法分析、語法分析和語義分析，建立原始查詢樹。最后根據DOT的特點實現查詢樹的優化。對于語法分析中各操作語句類型的判斷，采取保留類SQL語句第一個關鍵詞的方法進行查詢類型的匹配來識別具體的查詢類型的方法來實現。類SQL語句解析流程如圖1所示。

1.1 查詢關系式的詞法分析

利用有限自動機的方法對識別過程進行建模。通過詞法分析自動機對where_list查詢條件進行分析后就能夠得到查詢條件中的所有關鍵詞，然后根據關鍵字出現的順序確定輸入是否符合語法分析的語法規定。根據需求，本自動機識別的關鍵字有關系符號、括號、整數、浮點數、字符串值、變量名[6]。

詞法分析的結果記錄在下面三個數組中：

keyWordList[wordIndex]，記錄condition條件中的查詢列。

keyValueList[valueIndex]=searSQL.substring（begIndex，endIndex），記錄查詢列的起始范圍的值。

keyValueType[valueIndex]=DataType，記錄查詢列的范圍值的數據類型。

stokenList[listIndex++]，記錄condition條件中出現的每一個字符的標記token，token分為五類：邏輯與或非，查詢條件列，條件列范圍的起始值，范圍起始值的類型和比較符號。

1.2 查詢關系式的語法分析

類SQL語句和傳統的SQL語句類似，包含固定的關鍵字和各關鍵字的出現順序，并且每個關鍵字所起的引導作用也很清晰。本系統中的類SQL的語法表即是通過正則表達式實現的。語法中定義了類SQL語句的各關鍵詞的出現順序，并根據不同的關鍵字觸發不同的動作。

在語法分析中還包括對查詢條件中括號的匹配。待整個SQL語句的語法語義分析正確后，將語句中涉及的語法正確的tablename，select_list，condition等信息存儲到響應的string數組里面。在詞法語法分析正確的基礎上對SQL語句中涉及的表和列是否存在部分完整性檢查，如有錯誤，即時反饋錯誤信息。

1.3 查詢樹的構建

文中類SQL的查詢關系式查詢樹的構建是用二叉查詢樹構建的。建立的二叉查詢樹為中序遍歷二叉樹，通過對查詢樹進行中序遍歷可以得到查詢關系式。在查詢樹的構建中，根據二叉樹的特點采用遞歸算法，先判斷出左右子樹的范圍并完成構建，然后完成其父節點的構建，組成樹結構。

2 查詢樹的優化

DOT系統為分布式結構，所有的數據均存儲在集群中，在并行操作中具有很強的性能優勢。為了提高查詢統計的速度，讓查詢開啟多線程進行并行化查詢是較好的解決方案。本文并行化的解決方案是將查詢關系式解析成析取范式的形式，程序為每一個析取項啟動一個查詢線程，首先將查詢關系式轉化成析取范式矩陣。為了不讓并行化執行的查詢進程之間出現重復的結果，即并行化執行的析取查詢項之間沒有交集，最后需要將查詢關系式解析成等價的主析取范式矩陣。

2.1 查詢關系式并行化優化

2.1.1 查詢關系式優化成析取范式矩陣

對整個二叉查詢樹的優化算法思想為：

（1） 自根節點遍歷整個查詢樹；

（2） 如果沒有發現父節點是and節點或or節點則優化完成，程序返回；否則，定義發現的or節點為當前節點，跳轉到（3）；

（3） 對當前節點的各個分支按下文中三種邏輯節點（與或非）中的一種進行方式轉換，對查詢樹進行旋轉，完成后跳轉到（1）。

對查詢樹的優化采用遞歸調用的流程來實現，對于每一個節點采用先優化左子樹，再優化右子樹，后優化當前節點的優化流程。

2.1.2 查詢關系式邏輯“或”節點的優化

邏輯“或”節點的優化和邏輯“與”節點的優化不同。它只有當其左右孩子都為數據節點且數據節點為同一個變量的表達式的情況下，邏輯“或”節點才需要進行優化。如圖2為整棵樹的一部分，節點[B]為邏輯節點，節點[m]和[n]為數據節點，[A]節點為[B]節點的父節點。

因為數據節點[m]和[n]為同一個變量的關系式，這樣的話數據節點[m]和[n]與邏輯節點[B]就可能存在合并成一個數據節點[mn]的情況，從而可以簡化樹結構。例如，[B]節點為“或”節點，[m]節點為[-6

2.1.3 查詢關系式邏輯“非”節點的優化

邏輯“非”節點的優化目標是消除非節點，將非節點等價轉化成邏輯“與或”節點連接數據節點的形式。在建立查詢樹時，規定了邏輯“非”節點的孩子為左子樹，并且邏輯“非”節點的孩子只是一個節點。根據孩子節點的類型可以將非節點的優化分為兩種情況：該邏輯“非”的孩子節點為數據節點；該邏輯“非”的孩子節點為邏輯節點。為便于后續繼續優化處理，在本類SQL查詢技術中用矩陣表示最終的析取范式，具體實現算法如下：

（1） 讀入要轉換的樹結構；

（2） 若當前節點為“或”節點，則對左右子樹分別轉入（1）；

（3） 若當前節點為“與”節點，則開始遍歷該節點下的所有子節點，組成一個條件的“與”集合；

（4） 作為數組的一行。若當前節點為葉子節點，則當前節點為一個“與”集合；

（5） 最后收集所有的“與”集合，構成所要的析取范式。

2.2 查詢關系式算術優化

當一個用戶的輸入含有冗余的where查詢條件，如a>1 or a>3或者b<3 and b>4時，底層根據這些條件也可以執行查詢并返回正確結果。對于數據少的情況下，查詢速度可以忽略，但當數據量很龐大時，查詢的速度就會受影響。本系統中實現的條件冗余優化分為以下幾種情形：or節點的左右子節點是同一變量并且變量的數據范圍集合有交集；and節點的左右子節點是同一變量并且變量的數據范圍有交集；在從析取范式轉化成主析取范式的過程中，冗余條件的產生。

具體的實現方法和過程如下：在處理三種邏輯節點“與或非”的過程中，冗余節點的合并剪枝；在析取范式向主析取范式的轉化過程中，表示各析取項的數組中，數組行與行之間的重復項的優化和行內析取項的代數冗余優化。

3 多種數據類型查詢優化

3.1 Int，Long類型數據的正負號支持優化

Int和Long類型的數據在轉換成Bytes之后，會造成所有負數比所有正數大的情況。通過對原有關系式進行變換來保證查詢條件在轉換成Bytes之后與原數據進行比較的正確性。

為保證查詢關系式轉換成字節流之后可以直接通過字節流進行比較就能得到正確的結果，將原來的一個關系式單元分成兩個關系式單元，并且這兩個關系式單元之間是邏輯“或”的關系。在真實比較的過程中首先將int數據轉換成字節流存儲到數據庫中，然后將轉換后的比較條件轉換成字節流與掃描到數據庫中的字節流進行比較，如表1所示。

5 系統優化結果的實驗和驗證

實驗 1：查詢計劃優化效果分析

查詢語句條件中無rowkey情況的查詢語句如下，其設計用意在于驗證類SQL語句的解析和三種優化能夠正確執行，其中：查詢語句為selectf1：c2，f3：c8fromt6where（f3：c8>2andf3：c8<7）；數據總量為10億；優化前的查詢時間為40 789 238 ms；優化后的查詢時間為92 596 ms。

按照查詢條件where_list，f1：c3>1000andf1：c3>100andf3：c9>10存在冗余的情況下，在沒有優化前的查詢平均時間為395 266 ms，經過冗余和并行化優化后，速度明顯提高了一個數量級，查詢平均時間是97 025 ms，優化后查詢時間減少了75.45%。

實驗2：索引優化效果分析

（1） 優化后選擇CCIndex索引表

該查詢的數據分布情況為：數據分布f1：c1<10 000的數據占列數據總量的1%，f3：c8<10 000的數據占f3：c8列數據總量的1%，f2：c5=’Maria’的數據量占f2：c5列數據總量的4%。

如圖4查詢結果顯示，優化后的時間和f2：c5列建立的CCIndex索引表的時間接近，可以認為經過優化后，查詢條件結果集預估算法選擇了以f2：c5列建立的索引表進行了掃描和條件篩選。其查詢速度只占f3：c8和f1：c1建立的ImpSecondaryindex索引表和Secondaryindex索引表查詢時間的0.192%和0.195%，分別提高了521.6倍和512.3倍。

（2） 優化后選擇部分聚簇索引表

選擇部分聚簇索引表的結果，如圖5所示。查詢語句中數據的分布情況為：數據分布f1：c1<10 000的數據占列數據總量的10%，f3：c8=195的數據占f3：c8列數據總量的0.000 1%，f2：c5=’Maria’的數據量占f2：c5列數據總量的4%。測試結果中，符合查詢條件的數據共有3 781條。優化后的時間和f3：c8列建立的Imp Secon daryindex索引表的時間接近，可以認為經過優化后，查詢條件結果集預估算法選擇了以f3：c8列建立的索引表進行了掃描和條件篩選。其查詢速度占f2：c5和f1：c1建立的CCIndex索引表和Secondaryindex索引表查詢時間的4.2%和0.004 09%，分別提高了23.91倍和13 349.337倍。

（3） 優化后選擇二級索引表

選擇二級索引表的查詢語句中數據分布情況為數據分布f1：c1=1 624的數據占列數據總量的0.000 1%，f3：c8<10 000的數據占f3：c8列數據總量的1%，f2：c5=’Maria’的數據量占f2：c5列數據總量的4%。優化后的時間和f1：c1列建立的Secondaryindex索引表的時間接近，可以認為經過優化后，查詢條件結果集預估算法選擇了以f1：c1列建立的索引表進行了掃描和條件篩選。其查詢速度占f2：c5和f3：c8建立的CCIndex索引表和ImpSecondaryindex索引表查詢時間的4.47%和0.007 6%，分別提高了22.37倍和13 027.32倍。

綜合上面三組實驗，索引優化后的查詢結果和中等索引時間提高的倍數分別是512.3，23.91和22.37倍，取三者的平均值為186倍。

6 結 論

本文完成了分布式順序表類SQL查詢技術的實現和優化工作。給DOT系統設計了一套類似SQL的查詢語句，并結合傳統數據庫和DOT系統的特點，實現了該套類SQL查詢語句的語法語義分析，構建查詢樹并對查詢關系式進行了算術優化、并行化優化和加多種數據類型查詢優化三方面的優化內容。最后在典型的DOT系統，即ApacheHBase上實現了整個類SQL的解析和優化，并針對中科院在DOT系統上實現的三種索引機制進行了優化，使得整個系統的查詢性能得到了顯著的提升。最后通過實驗，分析驗證了查詢優化和索引優化后查詢速度明顯提升。

參考文獻

[1] 郭珉.Oracle數據庫SQL優化原則[J].計算機應用系統，2010，19（4）：171?173.

[2] SILBERSCHATZ A， KORTH H F.數據庫系統概念[M].北京：機械工業出版社，2006：293?400.

[3] CHANG F， DEAN J， GIHEMAWAT S， et al. Bigtable： a distributed storage system for structured data [C]// Proceedings of 2006 USENIX Symposium on Operation System Design and Implementation. Berkeley： ACM， 2006： 205?218.

[4] COOPER B F， RAMAKRISHNAN R， SRIVASTAVA U， et al. PNUTS： Yahoo！'s hosted data serving platform [J]. Proceedings of the VLDB endowment， 2008， 1（2）： 1277?1288.

[5] ZOU Y Q， LIU J， WANG S， et al. CCIndex： a complemental clustering index on distributed ordered tables for multi?dimensional range queries [C]// Proceedings of 2010 IFIP International Conference on Network and Parallel Computing. Zhengzhou， China： Springer， 2010： 247?261.

[6] 江凌，楊平利，楊梅，等.基于ADO.NET技術訪問SQL Server數據庫的編程實現[J].現代電子技術，2014，37（8）：95?98.

[7] 譚龍丹，郭睿志，王帥，等.基于C#與SQL Server的裝備電子檔案系統的設計與實現[J].現代電子技術，2014，37（14）：40?42.

[8] 任詩兵，鄒海.基于關系代數的分布式數據庫的查詢優化[J].福建電腦，2008（2）：4?5.