批處理在內(nèi)存數(shù)據(jù)處理系統(tǒng)中的應(yīng)用

周 烜， 薛忠斌

（中國人民大學(xué) 數(shù)據(jù)工程與知識工程教育部重點實驗室，北京 100872）

0 引 言

內(nèi)存計算近年來在工業(yè)界和學(xué)術(shù)界都備受關(guān)注.隨著存儲技術(shù)和工藝的發(fā)展，內(nèi)存的容量幾乎以每年一倍的速度增長.如今的高端服務(wù)器已經(jīng)可以配備4TB甚至更高容量的內(nèi)存.在很多應(yīng)用領(lǐng)域，幾乎可以將全部業(yè)務(wù)數(shù)據(jù)放入內(nèi)存，從而明顯提升整個軟件系統(tǒng)的性能.可以推測，在不久的將來，基于磁盤的傳統(tǒng)數(shù)據(jù)庫系統(tǒng)將逐漸被內(nèi)存數(shù)據(jù)庫系統(tǒng)取代.對內(nèi)存數(shù)據(jù)庫而言，針對磁盤I／O的優(yōu)化策略將不再是系統(tǒng)設(shè)計的重點；如何提高內(nèi)存的訪問效率成為了提升系統(tǒng)性能的關(guān)鍵.

眾所周知，CPU訪問內(nèi)存的速度遠遠滯后于CPU訪問寄存器的速度；CPU與內(nèi)存之間的多級緩存機制（即L1、L2、L3 Cache）成為緩解這一速度差異的主要機制.因此，為了提升內(nèi)存計算的性能，首先需要提升多級緩存的命中率.為了提升緩存命中率，就必須提升指令和數(shù)據(jù)訪問的局部性.近期的一些研究表明［14］，在去除I／O瓶頸之后，傳統(tǒng)數(shù)據(jù)庫系統(tǒng)的指令和數(shù)據(jù)訪問局部性并不理想，存有較大優(yōu)化空間.這促使研究人員開始重新思考數(shù)據(jù)庫系統(tǒng)的設(shè)計方案.可以預(yù)見，代碼和內(nèi)存訪問的效率會成為今后數(shù)據(jù)庫系統(tǒng)研發(fā)的重點，并推動數(shù)據(jù)庫性能的進一步提升.

本文著重探討用于提升內(nèi)存數(shù)據(jù)庫性能的一類策略 — 批處理優(yōu)化.常用于衡量數(shù)據(jù)庫性能的指標(biāo)包括響應(yīng)時間和吞吐率.除一些特殊領(lǐng)域外（如金融領(lǐng)域的自動交易），大部分領(lǐng)域?qū)憫?yīng)時間的要求并不十分苛刻，只要它能跟上用戶的反應(yīng)速度即可；而普通應(yīng)用往往對系統(tǒng)吞吐率的要求很高，希望系統(tǒng)能夠承受盡量多用戶帶來的高強度工作負(fù)載，從而獲取軟硬件的最佳性價比.當(dāng)內(nèi)存取代磁盤成為數(shù)據(jù)的主要存儲介質(zhì)后，系統(tǒng)的性能得到大幅提升，大大緩解了響應(yīng)時間方面的壓力，使得吞吐率成為了衡量系統(tǒng)性能的主要指標(biāo).批處理作為一種優(yōu)化系統(tǒng)吞吐率的常用方案就變得尤其有效.批處理優(yōu)化的主要目標(biāo)是將多個查詢請求合并，同時處理；一方面，如果多個請求共享公共的數(shù)據(jù)操作，合并后可以減少這些操作的重復(fù)調(diào)用，減輕系統(tǒng)的負(fù)載；另一方面，系統(tǒng)可以調(diào)整批處理作業(yè)的執(zhí)行次序，對位于同一區(qū)域的數(shù)據(jù)盡量一起訪問，對位于同一區(qū)域的代碼也盡量一并執(zhí)行，這有利于提高數(shù)據(jù)和指令的局部性，提升系統(tǒng)效率.雖然批處理優(yōu)化可能增加單個查詢的響應(yīng)時間，但能夠有效提升系統(tǒng)的吞吐率，這與內(nèi)存數(shù)據(jù)庫對吞吐率的偏重相契合.

近年來的一些學(xué)術(shù)研究［3，5］已經(jīng)開始關(guān)注批處理在內(nèi)存數(shù)據(jù)庫中的應(yīng)用.ETH的系統(tǒng)團隊（System Team）開發(fā)的SharedDB系統(tǒng)和EPFL的數(shù)據(jù)庫團隊（DB Team）開發(fā)的StagedDB都是典型的例子.本文將對這些相關(guān)的研究成果作概要介紹，也提出一些作者本人對批處理優(yōu)化的初步思考.本文還將介紹一個將批處理優(yōu)化用于移動對象管理的案例，通過實際應(yīng)用對批處理優(yōu)化的有效性做初步驗證.

1 相關(guān)研究

批處理在傳統(tǒng)數(shù)據(jù)庫中已經(jīng)得到了一定程度的應(yīng)用.一個典型例子是數(shù)據(jù)庫的批量插入操作（用于將大量數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫）.但類似的批處理操作與本文涉及的批處理優(yōu)化有所區(qū)別.前者是可被單獨調(diào)用的數(shù)據(jù)庫操作，后者則是對多個操作的整體優(yōu)化.傳統(tǒng)數(shù)據(jù)庫的查詢結(jié)果緩存和多查詢優(yōu)化更符合批處理優(yōu)化的模式.本節(jié)將對批處理優(yōu)化的一些已知方法做簡單的概括和分析.這些方法可以分為三大類：查詢結(jié)果緩存、多查詢優(yōu)化、分階段查詢處理.

1.1 查詢結(jié)果緩存

查詢結(jié)果緩存是數(shù)據(jù)庫系統(tǒng)的一項常見功能.當(dāng)某查詢執(zhí)行完畢并返回結(jié)果后，系統(tǒng)一般不急于丟棄查詢結(jié)果，而是先將其在緩存中保留一段時間；若用戶又提交相同的查詢，在不違背時效性的前提下，系統(tǒng)無需重新執(zhí)行查詢，可直接返回緩存的結(jié)果給用戶.對于數(shù)據(jù)訪問方式有限且用戶眾多的應(yīng)用，查詢結(jié)果緩存的優(yōu)化效果非常明顯.因此，幾乎所有的數(shù)據(jù)庫系統(tǒng)都不同程度地實現(xiàn)了查詢結(jié)果緩存的功能.

查詢結(jié)果緩存可以有不同的實施粒度，各自的效果不同.最粗粒度的實施方法僅緩存整個查詢的最終結(jié)果；在這種粒度下，只有在用戶重復(fù)提交相同查詢時，緩存的結(jié)果才可以被重用.更細粒度的實施方法是將查詢的中間結(jié)果也一并緩存（中間結(jié)果可以是子查詢的結(jié)果，也可以是查詢計劃）；當(dāng)后續(xù)查詢涉及相同的中間結(jié)果時，緩存中的內(nèi)容就可以被重用.此外，查詢結(jié)果的重用機制也有多種.最直接的重用機制要求用戶提交的查詢或子查詢與緩存中的查詢或子查詢完全一致，否則不執(zhí)行結(jié)果重用.更復(fù)雜的機制則將緩存中的查詢結(jié)果物化為視圖；當(dāng)用戶新提交的查詢與該物化視圖不完全一致，但被該視圖包含時，系統(tǒng)將新查詢改寫為可直接實施于該物化視圖的查詢，在一定程度上達到重用的目的.很明顯，以上的各種查詢結(jié)果緩存的實現(xiàn)方案各有優(yōu)缺點.簡單的方法可重用率低，復(fù)雜的方法本身也可能成為系統(tǒng)的負(fù)擔(dān).方案的執(zhí)行效率往往取決于應(yīng)用負(fù)載的特點.由于不同數(shù)據(jù)庫廠商的考慮不同，采取的實施方法也不盡相同.

作為批處理優(yōu)化的一類方法，查詢結(jié)果緩存可以實現(xiàn)查詢之間相同數(shù)據(jù)訪問操作的重用，節(jié)省數(shù)據(jù)訪問和計算的開銷.這種方法同樣適用于內(nèi)存數(shù)據(jù)庫.然而，這種重用機制的粒度較粗（一般以查詢或子查詢?yōu)閱挝?，并無法達到指令級），并且不能針對性地提高指令和數(shù)據(jù)訪問的局部性.方法雖然簡單實用，但并不是一種徹底的批處理優(yōu)化方式.

1.2 多查詢優(yōu)化

相比查詢結(jié)果緩存，多查詢優(yōu)化（Multi－Query Optimization）［4］實現(xiàn)了更加徹底的查詢間的操作重用和資源共享.多查詢優(yōu)化更加符合批處理的模式，它并不逐個執(zhí)行用戶提交的查詢，而是先積累一批查詢后再對其進行統(tǒng)一執(zhí)行.通常，多查詢優(yōu)化會為若干查詢構(gòu)建一個統(tǒng)一的查詢計劃，通過執(zhí)行這個查詢計劃完成所有查詢.在統(tǒng)一的查詢計劃中，多個查詢公用的數(shù)據(jù)盡量做到一次性訪問，公用的代碼盡量做到一次性執(zhí)行，從而盡可能避免查詢間的重復(fù)工作.這種重用機制比查詢結(jié)果緩存機制粒度更細.

傳統(tǒng)的多查詢優(yōu)化的研究成果并不多，其方法一般以優(yōu)化I／O操作為主，且只針對于只讀查詢.新近的一些研究則開始將多查詢優(yōu)化向內(nèi)存數(shù)據(jù)庫擴展，并且逐步納入了數(shù)據(jù)更新的操作.SharedDB［1，2，3］就是一個典型的實行多查詢優(yōu)化的內(nèi)存數(shù)據(jù)庫系統(tǒng).這一系統(tǒng)不僅僅實現(xiàn)了傳統(tǒng)多查詢優(yōu)化的計算資源共享，而且還納入了數(shù)據(jù)流的查詢方式 — 它根據(jù)應(yīng)用需求生成一個統(tǒng)一的查詢計劃，用于滿足應(yīng)用中遇到的所有查詢需求；這一查詢計劃常駐系統(tǒng)，每次都被用于對若干查詢請求進行同時處理.圖1為SharedDB針對TPC－W應(yīng)用生成的一個查詢計劃，用于同時處理TPC－W中的若干查詢.

實驗證明，多查詢優(yōu)化在某些情況下可以明顯提升系統(tǒng)的吞吐率.從理論上講，這種方式也有利于提升指令和數(shù)據(jù)訪問的局部性，從而提高CPU緩存的命中率.然而，現(xiàn)有研究成果對多查詢優(yōu)化中的操作重用問題探討得更多，對指令和數(shù)據(jù)局部性問題涉及得不多.另外，多查詢優(yōu)化如何合理地利用多核處理器，還是一個有待深入探討的問題.

1.3 分階段查詢處理

圖1 SharedDB針對TPC－W生成的查詢計劃（摘自文獻［3］）Fig.1 Query plan generated by SharedDB for TPC－W

傳統(tǒng)數(shù)據(jù)庫系統(tǒng)對單個查詢或事務(wù)的執(zhí)行是線性的.一個事務(wù)請求的執(zhí)行通常經(jīng)過多個階段，包括查詢解析、查詢優(yōu)化、以及查詢執(zhí)行過程中的選擇、投影、連接等多個操作.傳統(tǒng)數(shù)據(jù)庫一般使用單線程依次執(zhí)行這些階段，執(zhí)行完畢后立即將結(jié)果返回給用戶.這種執(zhí)行方式的指令局部性和數(shù)據(jù)訪問局部性都是有限的，并不能很好地發(fā)揮CPU緩存的效率.而分階段查詢處理則將事務(wù)執(zhí)行的多個階段分配給不同的模塊，每個模塊享有獨占的CPU和內(nèi)存資源.這樣，事務(wù)執(zhí)行的過程不再是絕對線性的，而是將任務(wù)分配給各個模塊；當(dāng)所有模塊完成任務(wù)后，事務(wù)即執(zhí)行完畢.每個模塊可以自行決定任務(wù)的執(zhí)行方式，可以按照先進先出的方式順序執(zhí)行，也可以將多個任務(wù)按批處理的方式執(zhí)行.總之，分階段查詢處理的方式有利于在模塊內(nèi)實現(xiàn)較高的指令和數(shù)據(jù)局部性.如果系統(tǒng)對模塊的資源分配是合理的，就可以獲得較高的緩存命中率和系統(tǒng)性能.分階段查詢處理雖然不是顯式的批處理優(yōu)化，但其使用的效果與批處理優(yōu)化相似，都涉及多個查詢的資源共享.

分階段查詢處理的思想最早在CMU的StagedDB項目［5－7］中提出.該方法除了有助于提升指令和數(shù)據(jù)訪問的局部性之外，還具備模塊化、并行度高等優(yōu)點.雖然這些優(yōu)勢在理論上是成立的，但至今還沒有實際系統(tǒng)完整地采用這種方法.因此，分階段查詢處理的實現(xiàn)技術(shù)還需要進一步探索，它的實用性也有待檢驗.

2 批處理優(yōu)化面對的基本問題

從以上的相關(guān)研究成果，我們看到，批處理優(yōu)化對數(shù)據(jù)庫系統(tǒng)的性能提升可以歸結(jié)于兩個方面：首先，由于普通應(yīng)用對數(shù)據(jù)庫的訪問模式是相對單一的，在時序上相鄰的訪問請求往往共享一定的數(shù)據(jù)庫操作或中間結(jié)果；通過批處理優(yōu)化，我們可以讓不同的查詢和事務(wù)共享這些操作和中間結(jié)果，減少數(shù)據(jù)庫的工作量，提升系統(tǒng)效率；其次，通過使用批處理優(yōu)化，系統(tǒng)可以靈活調(diào)整程序執(zhí)行和數(shù)據(jù)訪問的順序，提高內(nèi)存訪問的局部性，提升緩存的利用率.批處理優(yōu)化對吞吐率的提升是明顯的，但會延長單個請求的響應(yīng)時間，因為每個查詢通常需要等待同一批查詢?nèi)客瓿珊蟛拍芊祷亟Y(jié)果.這一點也是制約批處理優(yōu)化應(yīng)用的主要因素.在內(nèi)存數(shù)據(jù)庫中，由于查詢和事務(wù)的響應(yīng)時間已經(jīng)被壓縮得很短，這就擴大了批處理優(yōu)化的應(yīng)用空間.因此，內(nèi)存數(shù)據(jù)庫適合更深入的批處理優(yōu)化.

通過總結(jié)批處理優(yōu)化的相關(guān)技術(shù)，我們認(rèn)為批處理優(yōu)化需要考慮以下問題：

（1）查詢相似性：批處理優(yōu)化要求被同時處理的查詢或事務(wù)具有一定的相似性，否則就難以達到操作共享或提升內(nèi)存訪問局部性的效果.查詢和事務(wù)或者具有相似的數(shù)據(jù)訪問模式（使得查詢計劃或指令可以共享），或者它們會訪問相同或相鄰的數(shù)據(jù)（使得數(shù)據(jù)操作可以共享）.如果查詢之間不具備以上的特性，批處理優(yōu)化只能在一定程度上提升程序的指令局部性，優(yōu)化效果有限.單一領(lǐng)域的應(yīng)用對數(shù)據(jù)庫的訪問模式有限，查詢之間一般具有較高的相似性，通常適合使用批處理優(yōu)化.但對于一些復(fù)雜應(yīng)用，由于其數(shù)據(jù)模式復(fù)雜且訪問方式多樣，查詢可能表現(xiàn)出較弱的相似性，不一定適合批處理優(yōu)化.

（2）執(zhí)行順序改變帶來的影響：批處理優(yōu)化的核心步驟是改變原有的查詢或事務(wù)執(zhí)行次序，盡量將相同或相似的操作放在一起執(zhí)行，從而達到操作共享的目的并提升內(nèi)存訪問局部性.執(zhí)行順序的改變使得傳統(tǒng)數(shù)據(jù)庫系統(tǒng)的很多設(shè)計方案需要做出調(diào)整，比如鎖管理和并發(fā)控制的實現(xiàn)方法等，因為這些模塊大都是按照單事務(wù)單線程模式實現(xiàn)的.與此對應(yīng)，系統(tǒng)的一些優(yōu)化技術(shù)也需做出相應(yīng)調(diào)整化.如何對整個系統(tǒng)進行改造以適應(yīng)批處理方式是批處理優(yōu)化的關(guān)鍵問題.

（3）多核利用率：傳統(tǒng)數(shù)據(jù)庫系統(tǒng)在大多數(shù)情況下使用順序的事務(wù)執(zhí)行模式，并發(fā)事務(wù)通過操作系統(tǒng)的線程調(diào)度被自動分配到不同的處理核心，從而自然地實現(xiàn)了多核擴展（雖然這樣的多核擴展受到臨界資源的種種限制）.當(dāng)使用批處理優(yōu)化后，這樣的多核擴展模式被打破，如何分配多核處理器資源，成為另一個關(guān)鍵問題.由于批處理可以比較自由地調(diào)整查詢和事務(wù)的執(zhí)行順序，這有利于系統(tǒng)減少臨界資源的競爭，從而獲取更高的多核擴展性.然而，如果系統(tǒng)不能有效地控制負(fù)載均衡，多核資源也難以獲得充分利用.部分使用批處理優(yōu)化的系統(tǒng)（如SharedDB和StagedDB）都給出了各自的多核并行方案.但這些方案都有待進一步驗證.

我們認(rèn)為，任何批處理優(yōu)化方案都需要對以上問題做出回答，否則其優(yōu)化效果就難以得到保證.當(dāng)然，批處理優(yōu)化在具體實施時還會遇到其他各式問題，本文無法一一列舉.本文以空間移動物體數(shù)據(jù)管理為場景，對批處理優(yōu)化做一些初步嘗試，并匯報一些對該領(lǐng)域的研究可能有參考意義的實驗結(jié)果.

3 批處理優(yōu)化一個應(yīng)用實例

我們將批處理優(yōu)化應(yīng)用到移動對象查詢上.考慮與人群相關(guān)的移動對象，例如：手機用戶或者車輛.移動對象周期性地向中央服務(wù)器報告位置，更新各自的位置信息.為了方便描述，我們將每個移動對象當(dāng)做空間中的一個點，用OID進行標(biāo)識，其位置為二維歐氏空間中一個坐標(biāo)（X，Y）.用戶對移動對象的查詢主要包括范圍查詢和KNN查詢兩類.我們著重考慮范圍查詢.一個范圍查詢一個矩形區(qū)域，通過區(qū)域的左下角坐標(biāo)（Xlow；Ylow）和右上角坐標(biāo)（Xhigh；Yhigh）定義.查詢結(jié)果為當(dāng)前落在查詢區(qū)域的移動對象.

移動對象在空間內(nèi)自由移動，位置信息持續(xù)更新，范圍查詢持續(xù)不斷的到來.對移動對象管理系統(tǒng)而言，這些都是較高的負(fù)載.為了保證查詢的實時性，傳統(tǒng)的方法是在移動物體上建立高效的索引，既有利于快速更新，也能夠快速響應(yīng)查詢.然而，如此高性能的索引的設(shè)計難度是很大的.如果將移動對象信息完全存放在內(nèi)存中，批處理優(yōu)化則可以派上用場.

3.1 批處理優(yōu)化的實施

為了利用批處理優(yōu)化，將位置更新請求和范圍查詢請求看做兩個數(shù)據(jù)流，分別稱為更新流和查詢流.當(dāng)更新和查詢抵達時，系統(tǒng)并不立即對其做出響應(yīng)，而是將它們緩存起來.當(dāng)一個時間窗口結(jié)束時，將所有緩存的更新以批處理的方式進行實施，然后再統(tǒng)一對緩存中的查詢進行應(yīng)答.只要保證時間窗口的大小滿足應(yīng)用對實時性的要求，就可以達到批處理優(yōu)化的效果.

由于我們的方法未使用索引，位置更新的批處理實現(xiàn)很簡單，這里不再贅述.我們主要考慮對多個范圍查詢進行批處理應(yīng)答的方法.假設(shè)移動對象和查詢分別被存放在兩張表中，整個批處理過程可以通過對兩張表的一個連接操作完成.連接的結(jié)果是將移動對象與它們所滿足的查詢進行配對.空間對象連接算法的相關(guān)研究成果已經(jīng)非常豐富.參考這些研究成果，我們制定出以下的批處理方法.

批處理方法分為三個階段.第一個階段為索引移動對象階段，創(chuàng)建一個臨時Grid索引結(jié)構(gòu)，把移動對象用Grid進行索引.第二階段為索引查詢階段，用Grid結(jié)構(gòu)索引所有的查詢.經(jīng)過前兩個階段，對象和查詢分別映射到相應(yīng)的單元格中，在每個單元格中通過把移動對象和查詢執(zhí)行連接操作，得到查詢結(jié)果.

圖2 連接算法示例Fig.2 DSJ example

圖2為一個查詢示例，首先索引移動對象，對移動對象進行聚類操作.如圖2所示，對象O1和O2都位于格網(wǎng)索引的單元格（2，2）中，通過聚類操作，把兩個對象聚集在對象表的相鄰位置.然后處理查詢.對查詢進行聚類操作時，算法在查詢所涉及的每個單元格中保存一個副本，避免了執(zhí)行過程中，跨單元格訪問導(dǎo)致的cache miss.通過上面的兩步操作，完成對對象和查詢的聚類，提高了訪問查詢索引時數(shù)據(jù)的空間局部性，進而提高cache命中率.例如處理Q1后，接著處理Q2，則不會將單元格（2，2）中的數(shù)據(jù)從cache中替換出去，從而提高cache的命中率.

3.2 并行方案

對于對象和查詢的聚集操作，我們參考了文獻［8］中的多核并行方案，通過使用數(shù)據(jù)分布直方圖的方式，使操作可以充分并行執(zhí)行，發(fā)揮了多核的性能.執(zhí)行過程中對數(shù)據(jù)進行兩次順序掃描，避免了使用鎖機制，消除了執(zhí)行過程中空間競爭.對于連接操作，每個線程處理一個單元格的數(shù)據(jù)，多個線程并行執(zhí)行，線程間不存在競爭，充分發(fā)揮了多核的性能.除了范圍查詢，這種方式也適用于KNN查詢，因為后者很容易從范圍查詢中得到結(jié)果.

用來索引移動對象和查詢的Grid結(jié)構(gòu)中，每個單元格作為一個數(shù)組結(jié)構(gòu)，被放在不同的內(nèi)存頁中.內(nèi)存頁頻繁的換入換出，保存虛擬內(nèi)存到物理內(nèi)存映射的頁表被保存在TLB中.文獻［13］指出，劃分會產(chǎn)生大量頁表，若頁表數(shù)量超過TLB size，查找過程中會產(chǎn)生TLB miss.因此，TLB size限定了劃分?jǐn)?shù)目的上限.我們在Grid索引創(chuàng)建過程中為了消除TLB miss，采用了層次Grid的方式.在第一層Grid中單元格的數(shù)目小于TLB size，消除了TLB miss.在構(gòu)建第二層Grid時，確保單元格中數(shù)據(jù)能夠完全放在內(nèi)存中，消除cache miss.

當(dāng)Grid結(jié)構(gòu)構(gòu)建完成后，通過多線程并行執(zhí)行的方式，索引移動對象.移動對象被存儲在連續(xù)的數(shù)組中.在構(gòu)建索引時，充分考慮cache conscious特性，把位于相同單元格中的對象放在一起，減少后續(xù)調(diào)用時cache miss.

通過前兩步操作，查詢和移動對象分別存放在對應(yīng)的單元格中，各個單元格中數(shù)據(jù)相互獨立，可以多線程并行執(zhí)行.在執(zhí)行過程中，采用round－robin的方式，每個線程處理一個單元格，把單元格中的對象和查詢執(zhí)行連接操作，最后把結(jié)果匯總.在單元格中連接運算，為計算密集型操作.對于連接運算，我們首先采用了傳統(tǒng)的算法：桶鏈連接算法（bucket－chaining－join）和嵌套循環(huán)連接（nested－loops－join）算法.桶鏈連接算法在文獻［13］中提出，其主要思路是把單個元組串聯(lián)形成一個桶結(jié)構(gòu)，然后用數(shù)組位置作為指針（而不是內(nèi)存中實際的指針），通過這種方式提高內(nèi)存算法的效率.

由于移動對象的用戶訪問方式單一，查詢的相似性高，適合使用批處理優(yōu)化.我們提出的批處理優(yōu)化方法使得系統(tǒng)在兩個方面獲得性能提升：首先，相鄰的移動對象和查詢被聚集到相同的Grid單元里，使得它們能夠共享大量計算和數(shù)據(jù)訪問操作，提升了內(nèi)存訪問的局部性；其次，更新的查詢之間的沖突被規(guī)避，使得程序可以充分利用多核并行提升效率.

圖3 范圍查詢的劃分（左）和賦值（右）Fig.3 Partition and assignment for range query

4 初步實驗結(jié)果

4.1 數(shù)據(jù)集

在實驗中，我們使用了基于德國實際路網(wǎng)生成的數(shù)據(jù)集.實際數(shù)據(jù)集中包含了整個德國的路網(wǎng)，由3.8億個節(jié)點和4億個路段構(gòu)成，覆蓋641 km×864 km的面積.用開源的移動對象路徑生成器 MOTO［10］生成數(shù)據(jù).MOTO是在數(shù)據(jù)生成器Brinkhoff［9］的基礎(chǔ)上形成的.MOTO中采用了一個基于路網(wǎng)的對象布局方式，所有的移動對象都隨機分布在一個給定的路網(wǎng)中，設(shè)定的移動對象的最大車速Smax＝60 m／s＝216 km／h.數(shù)據(jù)生成器還按照現(xiàn)實中城市人口的分布進行了修改，一半的對象分布在5個主要的德國城市，因此能夠確保更新最頻繁的區(qū)域同時也是查詢最多的區(qū)域.

我們的算法用C／C＋＋實現(xiàn)，用g＋＋在最高的優(yōu)化等級下進行編譯.實驗運行在32核（4 Intel E5－2670＠2.6GHz）的計算機上，使用了 SUSEOS 11 （64－bit）系統(tǒng)，有256G RAM，片上的內(nèi)存被所有的線程共享.若無特別說明，所有的實驗都在32核中完成.

4.2 批處理優(yōu)化的性能表現(xiàn)

圖4中顯示不同數(shù)量的移動對象執(zhí)行500百萬個查詢時，查詢的響應(yīng)時間.橫坐標(biāo)表示移動對象的數(shù)量，縱坐標(biāo)為查詢的響應(yīng)時間.通過圖中可以發(fā)現(xiàn)，隨著數(shù)據(jù)量的增加，查詢的響應(yīng)時間呈線性增長.在不同的移動對象的數(shù)據(jù)量下，所有查詢的響應(yīng)時間小于2秒.對于一般應(yīng)用而言，移動對象的數(shù)量都在百萬級別.即同時處理500萬的查詢，對大多數(shù)應(yīng)用而言，都可以獲得亞秒級的響應(yīng)，完全可以應(yīng)對大部分用戶對響應(yīng)時間的要求.因此，移動對象應(yīng)用是非常適合使用批處理優(yōu)化的.

圖4 查詢執(zhí)行時間Fig.4 The response time of range query

圖5顯示了我們的批處理算法隨線程數(shù)增加吞吐量的變化趨勢.算法在對對象和查詢構(gòu)建索引時，通過建立數(shù)據(jù)分布直方圖，提前計算出對象所在位置，避免了線程間的空間競爭問題.同時，每個查詢所在單元格都保存一個副本.當(dāng)執(zhí)行連接操作時，通過round－robin的方式，每個線程處理一個單元格中的數(shù)據(jù)，各個線程獨立執(zhí)行，避免了線程間的競爭.通過圖5可以看到，隨線程數(shù)的增加算法的吞吐量呈線性增長.當(dāng)超過系統(tǒng)的物理核數(shù)16時，算法的吞吐量仍緩慢增長.總之，算法對多核的利用是很充分的.

圖5 多核擴展性Fig.5 The scalability of multi－core

4.3 對比試驗

我們進一步對比了批處理優(yōu)化和傳統(tǒng)非批處理方法的性能.對比對象為PGrid算法［12］和TwinGrid算法［11］.兩者將數(shù)據(jù)完全存儲在內(nèi)存中，且都使用動態(tài)索引，是目前文獻中性能最好的算法.

圖6對比了不同方法執(zhí)行一批查詢的響應(yīng)時間.通過圖中可以看出，當(dāng)執(zhí)行500個查詢時，TwinGrid算法的查詢總體響應(yīng)時間最長.在TwinGrid算法中，查詢和更新分別在兩個Grid結(jié)構(gòu)中，每隔一定的時間間隔，需要把write－store復(fù)制到read－store中，復(fù)制操作占用大量的時間.隨著查詢數(shù)量的增加，PGrid算法的查詢性能逐漸下降.PGrid算法中，查詢和更新在同一個Grid結(jié)構(gòu)中，為了避免沖突，查詢執(zhí)行過程中采用了加鎖機制，增加了查詢的處理時間.對于TwinGrid算法在執(zhí)行過程中，更新和查詢分別在兩個Grid結(jié)構(gòu)中，不存在沖突的問題.當(dāng)查詢數(shù)量增加時，其性能優(yōu)勢逐漸明顯.對于批處理優(yōu)化的方法，性能表現(xiàn)是最優(yōu)的，隨著查詢數(shù)量的增加，優(yōu)勢更加明顯.我們的批處理優(yōu)化采用了每次執(zhí)行一組查詢的方法，在執(zhí)行過程中，通過索引查詢的方式，增加了數(shù)據(jù)的局部性，實現(xiàn)查詢內(nèi)的并行，提高了算法的效率.

圖6 更改查詢數(shù)量的性能表現(xiàn)Fig.6 Performance of changing the number of queries

圖7中顯示了查詢范圍變化時，兩個算法的吞吐率表現(xiàn).隨著查詢范圍的增加，需要涉及到更多的單元格和對象，對索引的性能會有影響.圖7中看到，TwinGrid算法和PGrid算法隨著查詢范圍的增加，吞吐量保持平穩(wěn).批處理優(yōu)化方法隨著查詢范圍的增大，需要進行更多的比較，致使性能有所下降，但其吞吐量仍比TwinGrid算法和PGrid算法高一到兩個數(shù)量級.

圖7 更改查詢范圍的性能表現(xiàn)Fig.7 Performance of changing the query range size of queries

圖8顯示改變更新和查詢的比例，從2000∶1到1∶4時，PGrid算法、TwinGrid算法和批處理優(yōu)化方法在執(zhí)行過程中吞吐量變化.隨著查詢數(shù)量的不斷增加，需要進行更多的運算，三個算法的吞吐量都會下降.通過圖中可以看到，當(dāng)查詢增加時，PGrid算法的吞吐量下降更快.PGrid算法中采用鎖機制去保持?jǐn)?shù)據(jù)一致性，隨著查詢數(shù)量的增加，競爭更激烈，導(dǎo)致性能下降.TwinGrid算法在執(zhí)行過程中，查詢和更新分別在兩個結(jié)構(gòu)中，執(zhí)行過程中不存在沖突，提高了查詢的效率.批處理優(yōu)化方法采用每次處理一組查詢的方式，充分利用數(shù)據(jù)的局部性，提高了算法效率.批處理優(yōu)化方法將更新進行緩存，消除了查詢和更新過程中沖突.因此，當(dāng)大數(shù)據(jù)量下，查詢和更新大量涌入時，該方法也能保持較高的系統(tǒng)吞吐量.

圖8 改變查詢更新比率的性能表現(xiàn)Fig.8 Performance of changing the query update rates of quering

5 結(jié) 論

當(dāng)使用內(nèi)存作為數(shù)據(jù)存儲設(shè)備后，數(shù)據(jù)管理系統(tǒng)擺脫了I／O操作的性能瓶頸，并且迎來了新的性能優(yōu)化空間.我們認(rèn)為，批處理優(yōu)化對于內(nèi)存數(shù)據(jù)庫而言是一種行之有效的優(yōu)化方法.本文以移動對象管理的案例，對批處理優(yōu)化在內(nèi)存數(shù)據(jù)管理中的應(yīng)用進行了初步探討和驗證.還總結(jié)了批處理優(yōu)化獲得性能提升的兩個基本途徑：操作共享和內(nèi)存訪問局部性.同時也分析了批處理優(yōu)化的適用范圍和實施過程中面臨的潛在問題.通過在移動對象管理上的一些初步實驗，我們發(fā)現(xiàn)批處理優(yōu)化可以帶來相當(dāng)明顯的性能提升.

如何將批處理優(yōu)化應(yīng)用到通用的關(guān)系數(shù)據(jù)庫是一個更加復(fù)雜且更具有實用價值的問題.人們對此已經(jīng)做了一些初步探索，但還存在大量未解決的問題，也尚未出現(xiàn)完整的系統(tǒng)原型.我們認(rèn)為，批處理優(yōu)化將是一個會出現(xiàn)豐富實用成果的研究領(lǐng)域.

［1］ GIANNIKIS G，MAKRESHANSKI D，ALONSO G，et al.Shared workload optimization［C］／／PVLDB2014，7（6）：429－440.

［2］ GIANNIKIS G，MAKRESHANSKI D，ALONSO G，et al.DEMO：Workload optimization using sharedDB［C］／／SIGMOD2013，New York，2013，USA，June 22－27：［s.n.］

［3］ GIANNIKIS G，ALONSO G，KOSSMANN D.SharedDB：Killing one thousand queries with one stone［C］／／PVLDB，2012，5（6）：526－537.

［4］ SELLIS T K.Multiple－Query Optimization［J］.ACM Trans.Database Systems，1988，13（1）：23－52.

［5］ HARIZOPOULOS S，AILAMAKI A.StagedDB：Designing Database Servers for Modern Hardware［J］.IEEE Data Eng Bull，2005，28（2）pp.11－16.

［6］ HARIZOPOULOS S，SHKAPENYUK V，AILAMAKI A.QPipe：A simultaneously pipelined relational query engine［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data，Baltimore，Maryland：［s.n.］，2005：383－394.

［7］ HARIZOPOULOS S，AILAMAKI A.Improving instruction cache performance in OLTP［J］.ACM Transactions on Database Systems，2006，31（3）：887－920.

［8］ BALKESEN C，ALONSO G，TEUBNER J，et al.Main－memory hash joins on modern processor architectures［J］.IEEE Transactions on Knowledge and Data Engineering（TKDE），2014.

［9］ BRINKHOFF T.A framework for generating network－based moving objects.GeoInformatica 6.2（2002）：153－180.

［10］ DITTRICH J，BLUNSCHI L，VAZSALLES M A.Indexing moving objects using short－lived throwaway indexes.Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg，2009.189－207.

［11］ ?IDLAUSKAS D.Thread－level parallel indexing of update intensive moving－object workloads.Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg，2011.186－204.

［12］ ?IDLAUSKAS D，?ALTENIS S，CHRISTIAN S.JENSEN S.Parallel main－memory indexing for moving－object query and update workloads［C］／／Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM，2012.

［13］ MANEGOLD S，BONCZ P A，KERSTEN M L.Optimizing main－memory join on modern hardware［J］.IEEE Trans Knowl Data Eng，vol.14，no.4，pp.709－730，2002.

［14］ T?ZüN P，GOLD B，AILAMAKI A.（2013）OLTP in Wonderland－Where do cache misses come from in major OLTP components？［C］／／Proceedings of the 9th International Workshop on Data Management on New Hardware，pp.8：1－8：6.