周 烜， 薛忠斌

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

0 引 言

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

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

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

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

1 相關(guān)研究

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

1.1 查詢結(jié)果緩存

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

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

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

1.2 多查詢優(yōu)化

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

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

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

1.3 分階段查詢處理

圖1 SharedDB針對(duì)TPC－W生成的查詢計(jì)劃（摘自文獻(xiàn)［3］）Fig.1 Query plan generated by SharedDB for TPC－W

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

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

2 批處理優(yōu)化面對(duì)的基本問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 并行方案

對(duì)于對(duì)象和查詢的聚集操作，我們參考了文獻(xiàn)［8］中的多核并行方案，通過(guò)使用數(shù)據(jù)分布直方圖的方式，使操作可以充分并行執(zhí)行，發(fā)揮了多核的性能.執(zhí)行過(guò)程中對(duì)數(shù)據(jù)進(jìn)行兩次順序掃描，避免了使用鎖機(jī)制，消除了執(zhí)行過(guò)程中空間競(jìng)爭(zhēng).對(duì)于連接操作，每個(gè)線程處理一個(gè)單元格的數(shù)據(jù)，多個(gè)線程并行執(zhí)行，線程間不存在競(jìng)爭(zhēng)，充分發(fā)揮了多核的性能.除了范圍查詢，這種方式也適用于KNN查詢，因?yàn)楹笳吆苋菀讖姆秶樵冎械玫浇Y(jié)果.

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 多核擴(kuò)展性Fig.5 The scalability of multi－core

4.3 對(duì)比試驗(yàn)

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

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

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

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

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

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

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

5 結(jié) 論

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

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