一種面向海量分布式數(shù)據(jù)庫的嵌套查詢策略

裴歐亞， 劉文潔， 李戰(zhàn)懷， 田 征

（西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，西安 710129）

0 引 言

隨著云計(jì)算、Web2.0等技術(shù)的進(jìn)一步發(fā)展，NoSQL數(shù)據(jù)庫不斷發(fā)展壯大.NoSQL數(shù)據(jù)庫放棄了傳統(tǒng)關(guān)系型數(shù)據(jù)庫嚴(yán)格的事務(wù)一致性和范式約束，采用弱一致性模型，支持分布式和水平擴(kuò)展，滿足了海量數(shù)據(jù)管理的需求.

為了信息安全及降低數(shù)據(jù)庫系統(tǒng)升級(jí)維護(hù)費(fèi)用，國內(nèi)銀行開始推進(jìn)“去IOE化”戰(zhàn)略.NoSQL數(shù)據(jù)庫相較于傳統(tǒng)關(guān)系型數(shù)據(jù)，具有超高的性價(jià)比和良好的可擴(kuò)展性.這些特質(zhì)促使NoSQL數(shù)據(jù)庫成為國內(nèi)銀行業(yè)應(yīng)對(duì)海量數(shù)據(jù)的首選數(shù)據(jù)庫.

OceanBase是阿里集團(tuán)研發(fā)的一個(gè)海量分布式關(guān)系數(shù)據(jù)庫系統(tǒng)，采用了NoSQL數(shù)據(jù)庫的架構(gòu)，基于橫向擴(kuò)展模式，可以通過動(dòng)態(tài)在線增加／減少服務(wù)器的方式調(diào)整系統(tǒng)負(fù)載，具有良好的可擴(kuò)展性.而且，系統(tǒng)實(shí)現(xiàn)了關(guān)系數(shù)據(jù)庫的重要特征，支持SQL語言查詢，相對(duì)于其它的NoSQL數(shù)據(jù)庫，更好地滿足了金融業(yè)務(wù)的需求.

OceanBase的可擴(kuò)展性、標(biāo)準(zhǔn)SQL查詢和事務(wù)的強(qiáng)一致性功能，在應(yīng)對(duì)銀行業(yè)的金融業(yè)務(wù)上，具有很大優(yōu)勢.金融業(yè)務(wù)的一個(gè)特點(diǎn)是大量使用嵌套子查詢，但是目前，OceanBase只支持簡單的非嵌套的SQL，對(duì)于復(fù)雜的的嵌套子查詢尚未實(shí)現(xiàn)，因此阻礙了金融業(yè)務(wù)的導(dǎo)入.

本文通過分析OceanBase的架構(gòu)及現(xiàn)有查詢策略，提出了一種基于BloomFilter和HashMap的子查詢實(shí)現(xiàn)策略，以改進(jìn)現(xiàn)有查詢策略在查詢性能上的不足和SQL功能上的缺陷，為金融業(yè)務(wù)提供更好的支持.實(shí)驗(yàn)驗(yàn)證該策略與現(xiàn)有的Oceanbase的查詢策略相比，能更好提高查詢速度并支持大數(shù)據(jù)查詢.

1 相關(guān)研究進(jìn)展

嵌套子查詢是標(biāo)準(zhǔn)SQL的一個(gè)非常重要的功能.正是由于嵌套層數(shù)的任意性，才使得標(biāo)準(zhǔn)SQL具有強(qiáng)大的功能.

為了支持嵌套子查詢，傳統(tǒng)的關(guān)系數(shù)據(jù)庫做了大量工作.IBM的WON KIM最早于1982年將嵌套SQL分為不同的嵌套類型，并為每一種嵌套類型提出了轉(zhuǎn)化算法，將嵌套SQL盡可能轉(zhuǎn)換為等價(jià)的非嵌套SQL，提升查詢性能［1］.加州大學(xué)伯克利分校的Harry K T Wong對(duì)WON KIM的轉(zhuǎn)換算法進(jìn)行了研究，發(fā)現(xiàn)了轉(zhuǎn)換算法中關(guān)于聚合函數(shù)和數(shù)據(jù)重復(fù)計(jì)算的BUG，并給出了改進(jìn)的轉(zhuǎn)換算法［2］.WON KIM和Harry K T Wong的研究主要集中在重寫SQL，即將嵌套子查詢改寫為等價(jià)的非嵌套查詢，為SQL重寫技術(shù)的研究奠定了重要基礎(chǔ).突飛猛進(jìn)的并行計(jì)算技術(shù)促進(jìn)了SQL查詢優(yōu)化的另一個(gè)研究分支－查詢分解策略，即將查詢SQL按一定的策略拆分為一系列可并行執(zhí)行的子查詢.Kim，T.K等人充分利用網(wǎng)格計(jì)算和集群計(jì)算的并行能力，將嵌套子查詢拆分為多個(gè)子查詢，子查詢被分發(fā)至網(wǎng)格／集群的不同節(jié)點(diǎn)并行執(zhí)行［3－5］.Kang，Y.J等人同樣提出了復(fù)雜SQL分解策略，并構(gòu)建了多l(xiāng)inux PCs的OLAP引擎HyperDB.TPC－R benchmark測試驗(yàn)證了HyperDB的優(yōu)異性能［6］.

NoSQL數(shù)據(jù)庫為了追求查詢的高性能，都不內(nèi)置支持嵌套子查詢功能.NoSQL將嵌套子查詢留給應(yīng)用層實(shí)現(xiàn)，主要采用MapReduce框架實(shí)現(xiàn)［7－8］.但是，也有一些NoSQL系統(tǒng)提供了比較好的機(jī)制來實(shí)現(xiàn)復(fù)雜查詢，例如，MongoDB可以設(shè)定復(fù)雜的查詢條件［9］.部分NoSQL系統(tǒng)通過運(yùn)行MapReduce，或者與Hadoop結(jié)合來支持大規(guī)模數(shù)據(jù)分析［10］.

OceanBase為了高效查詢，只支持簡單的非嵌套SQL，包含IN后接確定值的查詢SQL.OceanBase的Filter條件過濾方式是逐一比對(duì)，因此如果表掃描策略為GET，在有主鍵索引的條件下，逐一比對(duì)不會(huì)耗費(fèi)大量時(shí)間，具有很高的性能.但是如果表掃描策略為SCAN，數(shù)據(jù)表的每條記錄都會(huì)和Filter過濾條件逐一比對(duì)，會(huì)耗費(fèi)大量的時(shí)間，性能較差.除此之外，OceanBase不支持子查詢，嵌套SQL的實(shí)現(xiàn)只能由應(yīng)用程序負(fù)責(zé)，這不僅不方便使用，還耗費(fèi)大量時(shí)間.

本文基于OceanBase的架構(gòu)及設(shè)計(jì)思想，提出了一種基于HashMap和BloomFilter的嵌套子查詢實(shí)現(xiàn)策略：當(dāng)子查詢結(jié)果集不大于閾值K時(shí)，直接將結(jié)果集綁定至主查詢的Filter內(nèi)，按OceanBase現(xiàn)有策略即可處理，其性能取決于OceanBase現(xiàn)有查詢策略的性能，因?yàn)楫?dāng)閾值K足夠小時(shí)，不大于K的子查詢結(jié)果集的綁定耗時(shí)可忽略不計(jì)；當(dāng)子查詢結(jié)果集大于K時(shí)，啟用BloomFilter和HashMap，BloomFilter和HashMap的構(gòu)建會(huì)耗費(fèi)一些時(shí)間，但是BloomFilter和HashMap在數(shù)據(jù)檢索方面具有非常高的效率；當(dāng)表掃描策略為SCAN、子查詢結(jié)果集大于K且小于OceanBase現(xiàn)有的IN上限時(shí)，假定結(jié)果集大小為N，嵌套查詢策略只需經(jīng)過數(shù)次計(jì)算即可判定一行記錄是否符合要求，而OceanBase現(xiàn)有的查詢策略則需要每條記錄平均比對(duì)N／2次（最差情況N次，最好情況1次）.因此在子查詢結(jié)果集較大時(shí)，嵌套查詢策略具有較好的性能.

2 OceanBase現(xiàn)狀

2.1 OceanBase架構(gòu)

OceanBase的整體架構(gòu)如圖1所示.

圖1 OceanBase整體架構(gòu)圖Fig.1 Architecture of OceanBase

OceanBase根據(jù)其設(shè)計(jì)目的，并結(jié)合淘寶業(yè)務(wù)特點(diǎn)，采用了“主—從”系統(tǒng)架構(gòu).

主節(jié)點(diǎn)，即RootServer，唯一，管理集群中的所有從節(jié)點(diǎn)服務(wù)器，子表數(shù)據(jù)分布以及副本管理.為了規(guī)避單主節(jié)點(diǎn)宕機(jī)的風(fēng)險(xiǎn)，RootServer采用了一主一備的結(jié)構(gòu)，主備之間采用數(shù)據(jù)強(qiáng)同步策略，并通過心跳實(shí)現(xiàn)軟件高可用性.

從節(jié)點(diǎn)被分為以下三種類型的節(jié)點(diǎn)：

（1）更新服務(wù)器，即UpdateServer，唯一，存儲(chǔ)增量數(shù)據(jù)，其實(shí)現(xiàn)類似單機(jī)的內(nèi)存數(shù)據(jù)庫，高效支持跨行跨表事務(wù).為了保證高可用性，UpdateServer同樣采用了一主一備的結(jié)構(gòu).為了保證系統(tǒng)的高性能，UpdateServer主備間可配置不同的模式，異步模式主要用于異地容災(zāi)，異步模式支持最終一致性.

（2）基線數(shù)據(jù)服務(wù)器，即ChunkServer，多臺(tái)，存儲(chǔ)基線數(shù)據(jù).

（3）合并服務(wù)器，即 MergeServer，對(duì)外提供標(biāo)準(zhǔn)的SQL訪問接口，對(duì)內(nèi)合并多臺(tái)ChunkServer返回的數(shù)據(jù)集.

2.2 OceanBase現(xiàn)有查詢策略

Oceanbase將數(shù)據(jù)分為基線數(shù)據(jù)和增量數(shù)據(jù)，分別存儲(chǔ)在ChunkServer和UpdateServer.對(duì)于任何一次查詢SQL請(qǐng)求，OceanBase都需要執(zhí)行ChunkServer和MergeServer相關(guān)數(shù)據(jù)的合并.

OceanBase關(guān)于查詢SQL的數(shù)據(jù)庫結(jié)構(gòu)如圖2所示.

圖2 Oceanbase數(shù)據(jù)庫功能層整體結(jié)構(gòu)Fig.2 Overall structure of OceanBase database function layer

用戶通過MySQL客戶端、ODBC等方式將SQL請(qǐng)求發(fā)送給某臺(tái)MergeServer，MergeServer的MySQL協(xié)議模塊從SQL請(qǐng)求中解析出SQL語句，并交給MS－SQL模塊進(jìn)行詞法／語法解析，并生成邏輯計(jì)劃和物理計(jì)劃.MergeServer首先根據(jù)物理計(jì)劃定位請(qǐng)求的數(shù)據(jù)所在的ChunkServer，接著將物理計(jì)劃發(fā)往相應(yīng)的ChunkServer.每個(gè)ChunkServer調(diào)用各自的CS－SQL模塊完成SQL查詢.如果需要增量數(shù)據(jù)，ChunkServer的CS－SQL模塊自動(dòng)從UpdateServer讀取修改增量，完成增量數(shù)據(jù)與本地基線數(shù)據(jù)的融合.ChunkS－erver最終將查詢結(jié)果返回給請(qǐng)求的MergeServer.MergeServer的CS－SQL模塊執(zhí)行多個(gè)ChunkServer返回結(jié)果的合并，獲取最終結(jié)果.

OceanBase支持的SQL語句比較簡單，絕大部分針對(duì)單張表格，只有很少一部分操作涉及多張表格，例如join操作.OceanBase目前只對(duì)主鍵有索引，OceanBase表掃描策略分為GET和SCAN兩種，GET策略當(dāng)且僅當(dāng)過濾條件包含全部主鍵列時(shí)啟用.SQL執(zhí)行本地化亦是OceanBase查詢策略的基本設(shè)計(jì)原則，即盡量支持SQL計(jì)算本地化，保持?jǐn)?shù)據(jù)節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)一致.

3 基于OceanBase的嵌套IN子查詢策略

本文主要針對(duì)非相關(guān)的嵌套IN子查詢.非相關(guān)的嵌套IN子查詢是指外查詢依賴于內(nèi)查詢，內(nèi)查詢不依賴外查詢且可以獨(dú)立先執(zhí)行（下文的嵌套查詢策略就是嵌套IN子查詢策略）.

嵌套查詢策略包含：嵌套查詢SQL的查詢樹構(gòu)建；查詢樹的執(zhí)行引擎；兩階段數(shù)據(jù)過濾.

3.1 查詢樹

策略沒有采用傳統(tǒng)關(guān)系數(shù)據(jù)庫的SQL重寫技術(shù)，而是采用“內(nèi)查詢先執(zhí)行，外查詢綁定內(nèi)查詢的結(jié)果（集）后執(zhí)行”的方案.該方案實(shí)現(xiàn)簡便，而且相較于SQL重寫技術(shù)，降低了傳送到MergeServer的數(shù)據(jù)量，節(jié)省了帶寬，減小了嵌套查詢對(duì)并發(fā)查詢的影響.

查詢樹的節(jié)點(diǎn)的部分主要數(shù)據(jù)結(jié)構(gòu)如下.

注：phy內(nèi)保｝存子節(jié)點(diǎn)執(zhí)行結(jié)果填充位置標(biāo)記；phy內(nèi)的位置標(biāo)記和next＿child一一對(duì)應(yīng).

查詢樹可以借助傳統(tǒng)關(guān)系型數(shù)據(jù)庫的SQL語句解析結(jié)果進(jìn)行構(gòu)建.示例嵌套SQL和其查詢樹如圖3所示.

圖3 示例SQL及其查詢樹Fig.3 Sample SQL and its query tree

3.2 執(zhí)行引擎

執(zhí)行引擎的主要功能就是按照一定的策略執(zhí)行查詢樹.依據(jù)策略構(gòu)建的查詢樹，具有“兄弟節(jié)點(diǎn)相互獨(dú)立”和“父節(jié)點(diǎn)依賴子節(jié)點(diǎn)”的特性.查詢引擎根據(jù)查詢樹的特性，采用從葉節(jié)點(diǎn)到根節(jié)點(diǎn)的遞歸計(jì)算算法.

遞歸算法如下：

算法的核心：串行執(zhí)行每個(gè)節(jié)點(diǎn)；除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)執(zhí)行結(jié)束，將本節(jié)點(diǎn)從查詢樹移除，以確保查詢樹的正確執(zhí)行.

算法中的threshold控制著是否啟用HashMap和BloomFilter.threshold為可變參數(shù)，可變化范圍為（0，511］，因?yàn)镺ceanBase的IN操作符支持的操作數(shù)上限不大于511組.當(dāng)子查詢結(jié)果集不大于threshold時(shí)，直接將子查詢結(jié)果集寫入主查詢的物理計(jì)劃內(nèi)，接下來的物理計(jì)劃的執(zhí)行等處理遵循OceanBase現(xiàn)有的查詢處理流程.當(dāng)子查詢結(jié)果集大于threshold時(shí)，將主查詢的物理計(jì)劃連同子查詢結(jié)果集生成的BloomFilter一起發(fā)送至ChunkServer處理，MergeServer利用子查詢結(jié)果集生成的HashMap過濾以獲取最終的結(jié)果集.

3.3 兩階段數(shù)據(jù)過濾

兩階段數(shù)據(jù)過濾：首先ChunkServer進(jìn)行非嚴(yán)格的BloomFiter過濾，獲得最終結(jié)果集的超集；其次MergeServer進(jìn)行嚴(yán)格的HashMap過濾，獲得最終結(jié)果集.

兩階段數(shù)據(jù)過濾如圖4所示.

圖4 兩階段數(shù)據(jù)過濾Fig.4 Two－phase data filtering

ChunkServer進(jìn)行數(shù)據(jù)表掃描時(shí)，每讀取一行，都執(zhí)行BloomFilter檢查，檢查通過則發(fā)送至MergeServer，否則繼續(xù)讀取下一行，直至讀取完畢.MergeServer對(duì)ChunkServer發(fā)送來的每一條數(shù)據(jù)，都執(zhí)行HashMap過濾，將過濾生成的結(jié)果返回給用戶.因?yàn)锽loomFilter的固有的誤報(bào)特性，ChunkServer發(fā)送給MergeServer的結(jié)果集是包含最終結(jié)果集的超集，因此MergeServer必須進(jìn)行一次嚴(yán)格過濾，去除誤報(bào)記錄，獲取最終結(jié)果.

3.3.1 BloomFilter過濾

分布式架構(gòu)下，將作為主查詢過濾條件的超大的子查詢結(jié)果集分發(fā)至不同的數(shù)據(jù)節(jié)點(diǎn)的方案會(huì)占用大量傳輸帶寬.為了降低帶寬占用率且加速查找，嵌套查詢策略使用了一種多哈希函數(shù)映射的快速查找數(shù)據(jù)結(jié)構(gòu)——布隆過濾器.相較于其他的數(shù)據(jù)結(jié)構(gòu)，布隆過濾器在空間和時(shí)間方面都有巨大的優(yōu)勢，特別適合于海量數(shù)據(jù)集的表示和查找.

策略所構(gòu)建的BloomFilter采用如下的公式：

其中p：誤判率.m：位數(shù)組大小.n：總數(shù)據(jù)數(shù)目.k：所需哈希函數(shù)數(shù)目.

BloomFilter的構(gòu)建由MergeServer負(fù)責(zé)，構(gòu)建算法如下.

Input：子查詢結(jié)果集S

①依據(jù)上述公式及S、誤報(bào)率p（默認(rèn)），計(jì)算BloomFilter所需位數(shù)組大小m，所需哈希函數(shù)數(shù)目k.

②讀取S的一條記錄R，如果R為NULL，轉(zhuǎn)⑤.

③將R依次帶入k個(gè)哈希函數(shù)H1（R），...，Hk（R）得到k個(gè)值V1，...，Vk.

④將BloomFilter的位數(shù)組的V1，...，Vk位設(shè)置為True，轉(zhuǎn)②.

⑤構(gòu)建結(jié)束，返回BloomFilter.

BloomFilter的查找算法如下.

①讀入一條記錄R.

②將R依次帶入k個(gè)哈希函數(shù)H1（R），...，Hk（R）得到k個(gè)值V1，...，Vk.

③比對(duì)BloomFilter的位數(shù)組的V1，...，Vk位.如果k個(gè)位全為True，則返回查找成功，否則返回查找失敗.

3.3.2 HashMap過濾

由于BloomFilter的誤報(bào)特性，MergeServer得到的結(jié)果集是最終結(jié)果集的超集.因此MergeServer必須進(jìn)行嚴(yán)格的數(shù)據(jù)過濾，以獲得最終結(jié)果集.

MergeServer嚴(yán)格的數(shù)據(jù)過濾條件就是海量的子查詢結(jié)果集.如何組織子查詢結(jié)果集，以提供高效的查找是一個(gè)關(guān)乎性能的重要問題.在當(dāng)今服務(wù)器普遍支持大內(nèi)存的狀況下，嵌套查詢策略采用全內(nèi)存的HashMap存儲(chǔ)子查詢結(jié)果集.

HashMap的高效查找依賴于哈希函數(shù)的均勻散列和低沖突率.均勻散列保證每一個(gè)桶內(nèi)的數(shù)據(jù)檢索時(shí)間大致相同；低沖突率保證快速定位.本文設(shè)計(jì)的HashMap采用鏈表法解決地址沖突，鏈表的每一個(gè)節(jié)點(diǎn)只保存key.

MergeServer負(fù)責(zé)構(gòu)建HashMap，且利用構(gòu)建的HashMap進(jìn)行嚴(yán)格的數(shù)據(jù)過濾.

HashMap的構(gòu)建算法如下.

Input：子查詢結(jié)果集S

①初始化HashMap，分配哈希桶空間.

②讀取S的一條記錄R，如果R為NULL，轉(zhuǎn)⑤.

③將R帶入哈希函數(shù)H（R），依據(jù)得到的哈希值確定待插入的哈希桶BUCKET BT.

④將R以鏈表的形式掛在BT的鏈表末尾，轉(zhuǎn)②.

⑤構(gòu)建結(jié)束，返回HashMap.

HashMap的查找算法如下.

①讀入一條記錄R.

②將R帶入哈希函數(shù)H（R），依據(jù)得到的哈希值確定待查詢的哈希桶BUCKET BT.

③遍歷BT內(nèi)的鏈表節(jié)點(diǎn)，逐個(gè)比對(duì).如果相同則返回查找成功，否者返回查找失敗.

查詢樹的每一個(gè)非葉子節(jié)點(diǎn)的執(zhí)行都需要兩階段數(shù)據(jù)過濾，即首先根據(jù)孩子節(jié)點(diǎn)的結(jié)果集構(gòu)建HashMap和BloomFilter，接著將BloomFilter連同本節(jié)點(diǎn)的物理計(jì)劃分發(fā)至數(shù)據(jù)節(jié)點(diǎn)，數(shù)據(jù)節(jié)點(diǎn)依據(jù)物理計(jì)劃及過濾條件BloomFilter，將最終結(jié)果集的超集返回給MergeServer，最后MergeServer利用HashMap執(zhí)行最后的嚴(yán)格的數(shù)據(jù)過濾，獲得最終結(jié)果集.

4 實(shí)驗(yàn)結(jié)果

OceanBase單服務(wù)器部署.服務(wù)器由1T硬盤，16 G內(nèi)存，16核CPU，一塊網(wǎng)卡組成.服務(wù)器操作系統(tǒng)是Red Hat6.2，內(nèi)核是2.6.32－220.el6.x86＿64.

4.1 實(shí)驗(yàn)一

該實(shí)驗(yàn)衡量小規(guī)模子查詢數(shù)據(jù)集狀況下嵌套IN子查詢策略的性能.測試表test，共計(jì)100萬條記錄，包含id、name共計(jì)兩個(gè)字段，其中id為主鍵列.啟用BloomFilter和Hash－Map的閾值設(shè)置為20，即子查詢結(jié)果集不大于20條.

測試SQL語句模板如下所示.

①：一層嵌套SQL：Select count（＊）from test where［id／name］in（select［id／name］from test Where id＜ConstValue）

②：與①等價(jià)SQL：Select count（＊）from test where［id／name］in（ConstValue，ConstValue，...）

①和②等價(jià)：如果①的子查詢結(jié)果和②綁定的ConstValue完全相同.

OceanBase現(xiàn)有查詢策略由于不支持子查詢，為了和嵌套查詢策略作對(duì)比，因此執(zhí)行嵌套子查詢的等價(jià)SQL，即②形式的SQL.

小規(guī)模子查詢數(shù)據(jù)集下，有主鍵索引的OceanBase已有查詢策略性能測試結(jié)果及嵌套查詢策略性能測試結(jié)果如表1所示.嵌套查詢SQL已轉(zhuǎn)化為OceanBase支持的非嵌套SQL.

表1 小規(guī)模子查詢數(shù)據(jù)集下兩種策略的結(jié)果，有主鍵索引Tab.1 Results of two strategies with small subquery dataset，primary key index

小規(guī)模子查詢數(shù)據(jù)集下，無主鍵索引的OceanBase已有查詢策略性能測試結(jié)果及嵌套查詢策略性能測試結(jié)果如表2所示.

表2 小規(guī)模子查詢數(shù)據(jù)集下兩種策略的結(jié)果，無主鍵索引Tab.2 Results of two strategies with small subquery dataset，without primary key index

表1和表2表明：嵌套IN子查詢的性能雖然低于OceanBase現(xiàn)有的有主鍵索引的查詢性能，但是卻遠(yuǎn)遠(yuǎn)高于OceanBase現(xiàn)有的非主鍵列的查詢性能.

4.2 實(shí)驗(yàn)二

該實(shí)驗(yàn)衡量大規(guī)模子查詢數(shù)據(jù)集狀況下嵌套子查詢策略的性能，實(shí)驗(yàn)環(huán)境同實(shí)驗(yàn)一.大規(guī)模子查詢數(shù)據(jù)集下的嵌套查詢策略的性能測試結(jié)果及Mysql5.1.52的性能測試結(jié)果如表3所示.

表3 大規(guī)模子查詢數(shù)據(jù)集下嵌套查詢策略的結(jié)果Tab.3 Results of nested query strategy with massive subquery dataset

表3驗(yàn)證了嵌套IN子查詢的高性能，在同等條件下，其耗時(shí)遠(yuǎn)遠(yuǎn)低于Mysql耗時(shí).

5 總 結(jié)

NoSQL數(shù)據(jù)庫內(nèi)置復(fù)雜SQL語句查詢功能是一個(gè)重要的趨勢.本文的主要目的就是提出一種查詢策略，用于支持復(fù)雜SQL的子集——嵌套子查詢，且改進(jìn)OceanBase現(xiàn)有的查詢策略.

嵌套查詢策略通過構(gòu)建查詢樹和查詢引擎實(shí)現(xiàn)了嵌套子查詢功能.嵌套子查詢策略還通過兩階段數(shù)據(jù)過濾，即HashMap過濾和BloomFilter過濾，改善了OceanBase現(xiàn)有的查詢策略，并保證了查詢的高效.實(shí)驗(yàn)一和實(shí)驗(yàn)二結(jié)果表明，通過采用嵌套子查詢策略，Ocean－Base實(shí)現(xiàn)了對(duì)嵌套子查詢功能的支持，同時(shí)其嵌套查詢性能優(yōu)于Mysql的嵌套查詢.

當(dāng)然，嵌套查詢策略在小規(guī)模子查詢數(shù)據(jù)集且有主鍵索引的條件下，相較于OceanBase現(xiàn)有策略有明顯的性能差異，雖然嵌套查詢語句的復(fù)雜性是一個(gè)重要因素，但是嵌套查詢策略在查詢優(yōu)化方面的不足也是一個(gè)重要因素.因此，未來的一個(gè)重要工作就是優(yōu)化嵌套查詢策略.

［1］ KIM W.On optimizing an SQL－like nested query［J］.ACM Transactions on Database Systems（TODS），1982，7（3）：443－469.

［2］ GANSKI R A，WONG H K T.Optimization of nested SQL queries revisited［C］／／ACM SIGMOD Record.ACM，1987，16（3）：23－33.

［3］ KIM T K，JUNG S H，KIM K R，et al.：HyperDB：A PC－based database cluster system for efficient OLAP query processing［C］／／Proc of 19th IASTED International Conference on Parallel and Distributed Computing and Systems（PDCS2007）.Cambridge，USA（November 2007）.

［4］ KIM T K，OH S K，CHO W S，et al.：A lanlinux－based grid system for bioinformatics applications［C］／／Proc.of International Conference on Advanced Communication Technology（ICACT）.2006，3：2187－2192.

［5］ KIM T K，KIM K R，OH S K，et al.A Hybrid Grid and Its Application to Clustering Orthologous Groups for Multiple Genomes［C］／／Proc International Symposium on Computational Life Science.2006：20－10.

［6］ KANG Y J，TIM T K，YANG K E，et al.：An OLAP query decomposition technique for PC－based database cluster systems［C］／／Proc of the 18th IASTED International Conference on Parallel and Distributed Computing and Systems(PDCS2009).Innsbruck，Austria(February 2009).

［7］申德榮，于戈，王習(xí)特，等.支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述［Ｊ］.軟件學(xué)報(bào)，2013，8：008.

［8］POKORNY Y.NoSQL databases:a step to database scalability in web environment[C]//The 13th International Conference on Information Integration and Web-based Applications＆Services(iiWAS).2011:278-283.

[9]BROWN A，WILSON G.The Architecture of Open Source Applications[M].Lulu.com,2011.