分布式順序表類SQL技術(shù)的實(shí)現(xiàn)和優(yōu)化

摘 要： 針對(duì)DOT系統(tǒng)，設(shè)計(jì)實(shí)現(xiàn)并優(yōu)化了類SQL的查詢技術(shù)，首先分析了傳統(tǒng)數(shù)據(jù)庫(kù)在查詢上的優(yōu)化策略，比較了傳統(tǒng)數(shù)據(jù)庫(kù)和DOT系統(tǒng)在查詢方面的異同。通過(guò)參考一般數(shù)據(jù)庫(kù)的SQL語(yǔ)句的設(shè)計(jì)規(guī)范，為DOT設(shè)計(jì)了一套類SQL語(yǔ)句。后續(xù)對(duì)設(shè)計(jì)的類SQL語(yǔ)句進(jìn)行詞法語(yǔ)法分析，構(gòu)建查詢樹(shù)。同時(shí)，借鑒傳統(tǒng)數(shù)據(jù)庫(kù)的查詢優(yōu)化策略，結(jié)合DOT系統(tǒng)的特點(diǎn)對(duì)查詢進(jìn)行優(yōu)化。最后在開(kāi)源的ApacheHBase典型的DOT系統(tǒng)的基礎(chǔ)上，實(shí)現(xiàn)了上述類SQL語(yǔ)句的所有解析和優(yōu)化內(nèi)容。

關(guān)鍵詞： 分布式順序表； 類SQL語(yǔ)句； 查詢優(yōu)化； HBase索引優(yōu)化

中圖分類號(hào)： TN911?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

網(wǎng)絡(luò)應(yīng)用的普及對(duì)海量數(shù)據(jù)的存儲(chǔ)和操作處理以及各種處理能力的可擴(kuò)展性、可靠性和高效性提出了很大的挑戰(zhàn)，而現(xiàn)有數(shù)據(jù)模型和相關(guān)技術(shù)已不能勝任[1]。為了應(yīng)對(duì)上述挑戰(zhàn)，業(yè)界提出了NoSQL數(shù)據(jù)庫(kù)。這些NoSQL數(shù)據(jù)庫(kù)可以模型化為分布式順序表（DOT）系統(tǒng)，但是DOT系統(tǒng)對(duì)SQL規(guī)范中查詢特性的支持并不完美[2]。

隨著網(wǎng)絡(luò)的發(fā)展，數(shù)據(jù)量出現(xiàn)爆炸式的增長(zhǎng)，現(xiàn)有的關(guān)系型數(shù)據(jù)庫(kù)處理這些大數(shù)據(jù)已經(jīng)出現(xiàn)瓶頸。進(jìn)而有了DOT系統(tǒng)的出現(xiàn)，但現(xiàn)有的DOT系統(tǒng)對(duì)SQL查詢特性的支持并不是特別的理想[3]。

1 類SQL語(yǔ)句的設(shè)計(jì)與解析實(shí)現(xiàn)

在實(shí)現(xiàn)過(guò)程中首先根據(jù)SQL的設(shè)計(jì)規(guī)范，設(shè)計(jì)出一套適用于DOT系統(tǒng)的類SQL語(yǔ)句。用戶根據(jù)類SQL規(guī)范提交查詢請(qǐng)求，然后系統(tǒng)對(duì)類SQL查詢語(yǔ)句進(jìn)行詞法分析、語(yǔ)法分析和語(yǔ)義分析，建立原始查詢樹(shù)。最后根據(jù)DOT的特點(diǎn)實(shí)現(xiàn)查詢樹(shù)的優(yōu)化。對(duì)于語(yǔ)法分析中各操作語(yǔ)句類型的判斷，采取保留類SQL語(yǔ)句第一個(gè)關(guān)鍵詞的方法進(jìn)行查詢類型的匹配來(lái)識(shí)別具體的查詢類型的方法來(lái)實(shí)現(xiàn)。類SQL語(yǔ)句解析流程如圖1所示。

1.1 查詢關(guān)系式的詞法分析

利用有限自動(dòng)機(jī)的方法對(duì)識(shí)別過(guò)程進(jìn)行建模。通過(guò)詞法分析自動(dòng)機(jī)對(duì)where_list查詢條件進(jìn)行分析后就能夠得到查詢條件中的所有關(guān)鍵詞，然后根據(jù)關(guān)鍵字出現(xiàn)的順序確定輸入是否符合語(yǔ)法分析的語(yǔ)法規(guī)定。根據(jù)需求，本自動(dòng)機(jī)識(shí)別的關(guān)鍵字有關(guān)系符號(hào)、括號(hào)、整數(shù)、浮點(diǎn)數(shù)、字符串值、變量名[6]。

詞法分析的結(jié)果記錄在下面三個(gè)數(shù)組中：

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

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

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

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

1.2 查詢關(guān)系式的語(yǔ)法分析

類SQL語(yǔ)句和傳統(tǒng)的SQL語(yǔ)句類似，包含固定的關(guān)鍵字和各關(guān)鍵字的出現(xiàn)順序，并且每個(gè)關(guān)鍵字所起的引導(dǎo)作用也很清晰。本系統(tǒng)中的類SQL的語(yǔ)法表即是通過(guò)正則表達(dá)式實(shí)現(xiàn)的。語(yǔ)法中定義了類SQL語(yǔ)句的各關(guān)鍵詞的出現(xiàn)順序，并根據(jù)不同的關(guān)鍵字觸發(fā)不同的動(dòng)作。

在語(yǔ)法分析中還包括對(duì)查詢條件中括號(hào)的匹配。待整個(gè)SQL語(yǔ)句的語(yǔ)法語(yǔ)義分析正確后，將語(yǔ)句中涉及的語(yǔ)法正確的tablename，select_list，condition等信息存儲(chǔ)到響應(yīng)的string數(shù)組里面。在詞法語(yǔ)法分析正確的基礎(chǔ)上對(duì)SQL語(yǔ)句中涉及的表和列是否存在部分完整性檢查，如有錯(cuò)誤，即時(shí)反饋錯(cuò)誤信息。

1.3 查詢樹(shù)的構(gòu)建

文中類SQL的查詢關(guān)系式查詢樹(shù)的構(gòu)建是用二叉查詢樹(shù)構(gòu)建的。建立的二叉查詢樹(shù)為中序遍歷二叉樹(shù)，通過(guò)對(duì)查詢樹(shù)進(jìn)行中序遍歷可以得到查詢關(guān)系式。在查詢樹(shù)的構(gòu)建中，根據(jù)二叉樹(shù)的特點(diǎn)采用遞歸算法，先判斷出左右子樹(shù)的范圍并完成構(gòu)建，然后完成其父節(jié)點(diǎn)的構(gòu)建，組成樹(shù)結(jié)構(gòu)。

2 查詢樹(shù)的優(yōu)化

DOT系統(tǒng)為分布式結(jié)構(gòu)，所有的數(shù)據(jù)均存儲(chǔ)在集群中，在并行操作中具有很強(qiáng)的性能優(yōu)勢(shì)。為了提高查詢統(tǒng)計(jì)的速度，讓查詢開(kāi)啟多線程進(jìn)行并行化查詢是較好的解決方案。本文并行化的解決方案是將查詢關(guān)系式解析成析取范式的形式，程序?yàn)槊恳粋€(gè)析取項(xiàng)啟動(dòng)一個(gè)查詢線程，首先將查詢關(guān)系式轉(zhuǎn)化成析取范式矩陣。為了不讓并行化執(zhí)行的查詢進(jìn)程之間出現(xiàn)重復(fù)的結(jié)果，即并行化執(zhí)行的析取查詢項(xiàng)之間沒(méi)有交集，最后需要將查詢關(guān)系式解析成等價(jià)的主析取范式矩陣。

2.1 查詢關(guān)系式并行化優(yōu)化

2.1.1 查詢關(guān)系式優(yōu)化成析取范式矩陣

對(duì)整個(gè)二叉查詢樹(shù)的優(yōu)化算法思想為：

（1） 自根節(jié)點(diǎn)遍歷整個(gè)查詢樹(shù)；

（2） 如果沒(méi)有發(fā)現(xiàn)父節(jié)點(diǎn)是and節(jié)點(diǎn)或or節(jié)點(diǎn)則優(yōu)化完成，程序返回；否則，定義發(fā)現(xiàn)的or節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)，跳轉(zhuǎn)到（3）；

（3） 對(duì)當(dāng)前節(jié)點(diǎn)的各個(gè)分支按下文中三種邏輯節(jié)點(diǎn)（與或非）中的一種進(jìn)行方式轉(zhuǎn)換，對(duì)查詢樹(shù)進(jìn)行旋轉(zhuǎn)，完成后跳轉(zhuǎn)到（1）。

對(duì)查詢樹(shù)的優(yōu)化采用遞歸調(diào)用的流程來(lái)實(shí)現(xiàn)，對(duì)于每一個(gè)節(jié)點(diǎn)采用先優(yōu)化左子樹(shù)，再優(yōu)化右子樹(shù)，后優(yōu)化當(dāng)前節(jié)點(diǎn)的優(yōu)化流程。

2.1.2 查詢關(guān)系式邏輯“或”節(jié)點(diǎn)的優(yōu)化

邏輯“或”節(jié)點(diǎn)的優(yōu)化和邏輯“與”節(jié)點(diǎn)的優(yōu)化不同。它只有當(dāng)其左右孩子都為數(shù)據(jù)節(jié)點(diǎn)且數(shù)據(jù)節(jié)點(diǎn)為同一個(gè)變量的表達(dá)式的情況下，邏輯“或”節(jié)點(diǎn)才需要進(jìn)行優(yōu)化。如圖2為整棵樹(shù)的一部分，節(jié)點(diǎn)[B]為邏輯節(jié)點(diǎn)，節(jié)點(diǎn)[m]和[n]為數(shù)據(jù)節(jié)點(diǎn)，[A]節(jié)點(diǎn)為[B]節(jié)點(diǎn)的父節(jié)點(diǎn)。

因?yàn)閿?shù)據(jù)節(jié)點(diǎn)[m]和[n]為同一個(gè)變量的關(guān)系式，這樣的話數(shù)據(jù)節(jié)點(diǎn)[m]和[n]與邏輯節(jié)點(diǎn)[B]就可能存在合并成一個(gè)數(shù)據(jù)節(jié)點(diǎn)[mn]的情況，從而可以簡(jiǎn)化樹(shù)結(jié)構(gòu)。例如，[B]節(jié)點(diǎn)為“或”節(jié)點(diǎn)，[m]節(jié)點(diǎn)為[-6

2.1.3 查詢關(guān)系式邏輯“非”節(jié)點(diǎn)的優(yōu)化

邏輯“非”節(jié)點(diǎn)的優(yōu)化目標(biāo)是消除非節(jié)點(diǎn)，將非節(jié)點(diǎn)等價(jià)轉(zhuǎn)化成邏輯“與或”節(jié)點(diǎn)連接數(shù)據(jù)節(jié)點(diǎn)的形式。在建立查詢樹(shù)時(shí)，規(guī)定了邏輯“非”節(jié)點(diǎn)的孩子為左子樹(shù)，并且邏輯“非”節(jié)點(diǎn)的孩子只是一個(gè)節(jié)點(diǎn)。根據(jù)孩子節(jié)點(diǎn)的類型可以將非節(jié)點(diǎn)的優(yōu)化分為兩種情況：該邏輯“非”的孩子節(jié)點(diǎn)為數(shù)據(jù)節(jié)點(diǎn)；該邏輯“非”的孩子節(jié)點(diǎn)為邏輯節(jié)點(diǎn)。為便于后續(xù)繼續(xù)優(yōu)化處理，在本類SQL查詢技術(shù)中用矩陣表示最終的析取范式，具體實(shí)現(xiàn)算法如下：

（1） 讀入要轉(zhuǎn)換的樹(shù)結(jié)構(gòu)；

（2） 若當(dāng)前節(jié)點(diǎn)為“或”節(jié)點(diǎn)，則對(duì)左右子樹(shù)分別轉(zhuǎn)入（1）；

（3） 若當(dāng)前節(jié)點(diǎn)為“與”節(jié)點(diǎn)，則開(kāi)始遍歷該節(jié)點(diǎn)下的所有子節(jié)點(diǎn)，組成一個(gè)條件的“與”集合；

（4） 作為數(shù)組的一行。若當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則當(dāng)前節(jié)點(diǎn)為一個(gè)“與”集合；

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

2.2 查詢關(guān)系式算術(shù)優(yōu)化

當(dāng)一個(gè)用戶的輸入含有冗余的where查詢條件，如a>1 or a>3或者b<3 and b>4時(shí)，底層根據(jù)這些條件也可以執(zhí)行查詢并返回正確結(jié)果。對(duì)于數(shù)據(jù)少的情況下，查詢速度可以忽略，但當(dāng)數(shù)據(jù)量很龐大時(shí)，查詢的速度就會(huì)受影響。本系統(tǒng)中實(shí)現(xiàn)的條件冗余優(yōu)化分為以下幾種情形：or節(jié)點(diǎn)的左右子節(jié)點(diǎn)是同一變量并且變量的數(shù)據(jù)范圍集合有交集；and節(jié)點(diǎn)的左右子節(jié)點(diǎn)是同一變量并且變量的數(shù)據(jù)范圍有交集；在從析取范式轉(zhuǎn)化成主析取范式的過(guò)程中，冗余條件的產(chǎn)生。

具體的實(shí)現(xiàn)方法和過(guò)程如下：在處理三種邏輯節(jié)點(diǎn)“與或非”的過(guò)程中，冗余節(jié)點(diǎn)的合并剪枝；在析取范式向主析取范式的轉(zhuǎn)化過(guò)程中，表示各析取項(xiàng)的數(shù)組中，數(shù)組行與行之間的重復(fù)項(xiàng)的優(yōu)化和行內(nèi)析取項(xiàng)的代數(shù)冗余優(yōu)化。

3 多種數(shù)據(jù)類型查詢優(yōu)化

3.1 Int，Long類型數(shù)據(jù)的正負(fù)號(hào)支持優(yōu)化

Int和Long類型的數(shù)據(jù)在轉(zhuǎn)換成Bytes之后，會(huì)造成所有負(fù)數(shù)比所有正數(shù)大的情況。通過(guò)對(duì)原有關(guān)系式進(jìn)行變換來(lái)保證查詢條件在轉(zhuǎn)換成Bytes之后與原數(shù)據(jù)進(jìn)行比較的正確性。

為保證查詢關(guān)系式轉(zhuǎn)換成字節(jié)流之后可以直接通過(guò)字節(jié)流進(jìn)行比較就能得到正確的結(jié)果，將原來(lái)的一個(gè)關(guān)系式單元分成兩個(gè)關(guān)系式單元，并且這兩個(gè)關(guān)系式單元之間是邏輯“或”的關(guān)系。在真實(shí)比較的過(guò)程中首先將int數(shù)據(jù)轉(zhuǎn)換成字節(jié)流存儲(chǔ)到數(shù)據(jù)庫(kù)中，然后將轉(zhuǎn)換后的比較條件轉(zhuǎn)換成字節(jié)流與掃描到數(shù)據(jù)庫(kù)中的字節(jié)流進(jìn)行比較，如表1所示。

5 系統(tǒng)優(yōu)化結(jié)果的實(shí)驗(yàn)和驗(yàn)證

實(shí)驗(yàn) 1：查詢計(jì)劃優(yōu)化效果分析

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

按照查詢條件where_list，f1：c3>1000andf1：c3>100andf3：c9>10存在冗余的情況下，在沒(méi)有優(yōu)化前的查詢平均時(shí)間為395 266 ms，經(jīng)過(guò)冗余和并行化優(yōu)化后，速度明顯提高了一個(gè)數(shù)量級(jí)，查詢平均時(shí)間是97 025 ms，優(yōu)化后查詢時(shí)間減少了75.45%。

實(shí)驗(yàn)2：索引優(yōu)化效果分析

（1） 優(yōu)化后選擇CCIndex索引表

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

如圖4查詢結(jié)果顯示，優(yōu)化后的時(shí)間和f2：c5列建立的CCIndex索引表的時(shí)間接近，可以認(rèn)為經(jīng)過(guò)優(yōu)化后，查詢條件結(jié)果集預(yù)估算法選擇了以f2：c5列建立的索引表進(jìn)行了掃描和條件篩選。其查詢速度只占f3：c8和f1：c1建立的ImpSecondaryindex索引表和Secondaryindex索引表查詢時(shí)間的0.192%和0.195%，分別提高了521.6倍和512.3倍。

（2） 優(yōu)化后選擇部分聚簇索引表

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

（3） 優(yōu)化后選擇二級(jí)索引表

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

綜合上面三組實(shí)驗(yàn)，索引優(yōu)化后的查詢結(jié)果和中等索引時(shí)間提高的倍數(shù)分別是512.3，23.91和22.37倍，取三者的平均值為186倍。

6 結(jié) 論

本文完成了分布式順序表類SQL查詢技術(shù)的實(shí)現(xiàn)和優(yōu)化工作。給DOT系統(tǒng)設(shè)計(jì)了一套類似SQL的查詢語(yǔ)句，并結(jié)合傳統(tǒng)數(shù)據(jù)庫(kù)和DOT系統(tǒng)的特點(diǎn)，實(shí)現(xiàn)了該套類SQL查詢語(yǔ)句的語(yǔ)法語(yǔ)義分析，構(gòu)建查詢樹(shù)并對(duì)查詢關(guān)系式進(jìn)行了算術(shù)優(yōu)化、并行化優(yōu)化和加多種數(shù)據(jù)類型查詢優(yōu)化三方面的優(yōu)化內(nèi)容。最后在典型的DOT系統(tǒng)，即ApacheHBase上實(shí)現(xiàn)了整個(gè)類SQL的解析和優(yōu)化，并針對(duì)中科院在DOT系統(tǒng)上實(shí)現(xiàn)的三種索引機(jī)制進(jìn)行了優(yōu)化，使得整個(gè)系統(tǒng)的查詢性能得到了顯著的提升。最后通過(guò)實(shí)驗(yàn)，分析驗(yàn)證了查詢優(yōu)化和索引優(yōu)化后查詢速度明顯提升。

參考文獻(xiàn)

[1] 郭珉.Oracle數(shù)據(jù)庫(kù)SQL優(yōu)化原則[J].計(jì)算機(jī)應(yīng)用系統(tǒng)，2010，19（4）：171?173.

[2] SILBERSCHATZ A， KORTH H F.數(shù)據(jù)庫(kù)系統(tǒng)概念[M].北京：機(jī)械工業(yè)出版社，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技術(shù)訪問(wèn)SQL Server數(shù)據(jù)庫(kù)的編程實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2014，37（8）：95?98.

[7] 譚龍丹，郭睿志，王帥，等.基于C#與SQL Server的裝備電子檔案系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2014，37（14）：40?42.

[8] 任詩(shī)兵，鄒海.基于關(guān)系代數(shù)的分布式數(shù)據(jù)庫(kù)的查詢優(yōu)化[J].福建電腦，2008（2）：4?5.