一種交互感知的并行查詢優(yōu)化策略研究

1、ISSN 1673-9418 CODEN JKYTA8Journal of Frontiers of Computer Science and Technology1673-9418/2012/06（00）-0000-00DOI: 10.3778/j.issn.1673-9418.2012.00.000E-mail: fcst Tel: +86-10-51616056一種交互感知的并行查詢優(yōu)化策略An Interaction-Aware Optimizing Strategy of Parallel QueryAbstract: While optimizi

2、ng d atabase performance； parallel query technology can significantly improve the throughput and resource utilization of the database server. Interactions among d ifferent quer iesthat run concurrently can have a great impact on system performance. However, current optimizing strategies of parallel

3、query often only focus on individual queries rather than their interactions. In order to capture the impact of parallel query interactions and reduce the negative interactions, we propose an interaction-aware optimizing strategy of parallel query. Compared with other methods, the experimental result

4、s demonstrate that our optimizing strategy can effectively improve t he database performance. Finally, some future trends in this area are prospected and discussed.Key words: Parallel query; Query interactions; Performance optimization; Performance modeling摘 要：在數(shù)據(jù)庫(kù)性能優(yōu)化時(shí)，通過(guò)并行查詢技術(shù)可以顯著提高數(shù)據(jù)庫(kù)服務(wù)器的吞吐率和資源利用

5、率。不 同的查詢?nèi)蝿?wù)并行執(zhí)行時(shí)會(huì)產(chǎn)生復(fù)雜的交互作用，這些交互作用會(huì)對(duì)系統(tǒng)性能產(chǎn)生非常巨大的影響。然而,目前的并行查詢性能優(yōu)化策略往往只關(guān)注單個(gè)查詢?nèi)蝿?wù)的優(yōu)化而忽略了彼此交互作用的影響。為了捕獲并行查詢之間的交互作用，減小交互作用帶來(lái)的消極影響，提出了一種交互感知的并行查詢優(yōu)化策略。通過(guò)實(shí)驗(yàn)與其它進(jìn)行了比較，證明交互感知的優(yōu)化策略可以較好地提升數(shù)據(jù)庫(kù)性能，最后對(duì)未來(lái)的研究工作進(jìn) 行了展望和討論。關(guān)鍵詞：并行查詢；查詢交互；性能優(yōu)化；性能建模文獻(xiàn)標(biāo)識(shí)碼：A中圖分類號(hào)：*The * Foundation of China under Grant No.*, * （基金中文完整名稱 ）;the * F

6、oundation of China under GrantNo.*, *（基金中文完整名稱）.需中英文齊全.Received 2000-00, Accepted 2000-00.張青峰 等：一種交互感知的并行查詢優(yōu)化策略91引言在數(shù)據(jù)庫(kù)系統(tǒng)應(yīng)用中，查詢?nèi)蝿?wù)往往占絕大多 數(shù)，因此查詢優(yōu)化是數(shù)據(jù)庫(kù)性能優(yōu)化的一項(xiàng)最為重 要的技術(shù)手段。隨著數(shù)據(jù)庫(kù)變得越來(lái)越大，大量業(yè) 務(wù)數(shù)據(jù)被收集和存儲(chǔ)以便用于更加智能的分析和 決策，為了提高數(shù)據(jù)庫(kù)服務(wù)器的資源利用率和吞吐 率，并行計(jì)算技術(shù)被引入到了數(shù)據(jù)庫(kù)系統(tǒng)中，通過(guò) 并行查詢技術(shù)，使用更少的時(shí)間來(lái)完成相同數(shù)量的 查詢?nèi)蝿?wù)。因?yàn)椴樵內(nèi)蝿?wù)并行時(shí)共享內(nèi)存、CPU和磁盤等底

7、層硬件資源，因此并行查詢的優(yōu)化策略比 傳統(tǒng)數(shù)據(jù)庫(kù)的查詢優(yōu)化要復(fù)雜的多，在優(yōu)化時(shí)必須 考慮底層資源沖突等問(wèn)題。在本文中我們主要研究并行查詢的優(yōu)化策略， 具體來(lái)說(shuō)我們要解決的問(wèn)題可以描述如下：“給定一組查詢?nèi)蝿?wù) Q1,Q2,Q3Qn,隨機(jī)并發(fā) 執(zhí)行訪問(wèn)同一個(gè)數(shù)據(jù)庫(kù)服務(wù)器，假定數(shù)據(jù)庫(kù)允許并 行執(zhí)行的查詢數(shù)即并發(fā)級(jí)別(Multi ProgrammingLevel,MPL )是固定不變的，選擇合適的并行查詢 優(yōu)化策略，使完成所有查詢?nèi)蝿?wù)的總時(shí)間最小?！贬槍?duì)以上問(wèn)題，本文提出了一種交互感知的并 行查詢優(yōu)化策略。在我們的方法中，和傳統(tǒng)查詢優(yōu) 化方法的主要區(qū)別是我們考慮了并行查詢之間的 交互作用。實(shí)驗(yàn)發(fā)現(xiàn)當(dāng)大

8、量查詢?nèi)蝿?wù)并發(fā)執(zhí)行共享 計(jì)算資源和數(shù)據(jù)的時(shí)候會(huì)出現(xiàn)非常復(fù)雜的交互作 用，這些復(fù)雜的交互作用將對(duì)系統(tǒng)性能產(chǎn)生非常大 的影響，并且這些影響可能是積極的，也可能是消 極的。因此我們認(rèn)為在進(jìn)行并行查詢優(yōu)化時(shí)，考慮 并行查詢之間的交互作用是非常重要的。本文的主要工作有以下幾個(gè)方面：1、提出了一個(gè)影響并行查詢?nèi)蝿?wù)性能的度量 指標(biāo)：交互成本率(Interaction Cost Rate, ICR )。2、提出了一種新的交互感知的并行查詢優(yōu)化 策略交互成本最小優(yōu)先(ICRMF : ICR Minimum First)策略。3、通過(guò)對(duì)MySQL/TPC-H研究的實(shí)驗(yàn)結(jié)果證 明了 ICRMF優(yōu)化策略的有效性。通過(guò)

9、利用 ICRMF 優(yōu)化策略，查詢?nèi)蝿?wù)整體執(zhí)行時(shí)間比 SJF算法和 FIFO算法減少了很多。本文的主要內(nèi)容組織如下：第二節(jié)介紹了并發(fā) 查詢優(yōu)化的相關(guān)研究工作；第三節(jié)通過(guò)實(shí)驗(yàn)說(shuō)明了 交互作用對(duì)查詢性能的影響；第四節(jié)介紹了交互感 知的并行查詢優(yōu)化策略；第五節(jié)對(duì)并行查詢優(yōu)化策 略進(jìn)行試驗(yàn)評(píng)估；最后是對(duì)本論文的研究工作進(jìn)行 總結(jié)和展望。2相關(guān)研究工作2.1 查詢優(yōu)化所謂查詢優(yōu)化，就是在查詢執(zhí)行引擎生成一個(gè) 執(zhí)行策略的過(guò)程中，盡量使查詢的總開銷和總時(shí)間 達(dá)到最小。一般來(lái)說(shuō)，查詢優(yōu)化可以歸納為四個(gè)步 驟：(1)將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹。(2)根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹換成優(yōu)化(標(biāo)準(zhǔn))形式。

10、(3)選擇底層的操作算法。對(duì)于語(yǔ)法樹中 的每一個(gè)操作需要根據(jù)存取路徑、數(shù)據(jù)的存儲(chǔ)分 布、存儲(chǔ)數(shù)據(jù)的聚簇等信息來(lái)選擇具體的執(zhí)行算 法。(4)生成查詢計(jì)劃。查詢計(jì)劃是由一系列內(nèi)部 操作組成的，這些內(nèi)部操作按照一定的次序構(gòu)成查 詢的一個(gè)執(zhí)行方案，通常這樣的執(zhí)行方案有很多 個(gè)，需要對(duì)每個(gè)執(zhí)行計(jì)劃計(jì)算代價(jià)，從中選擇代價(jià) 最小的一個(gè)。目前關(guān)于查詢優(yōu)化的研究主要集中在兩個(gè)方 面：SQL查詢重寫和查詢優(yōu)化算法。查詢重寫是查 詢優(yōu)化器的重要組成部分，它將一個(gè)查詢表示根據(jù)一定的規(guī)則，轉(zhuǎn)換為另一個(gè)效率更高或更易于優(yōu)化 的查詢表達(dá)式。如何發(fā)現(xiàn)更多而有效的重寫規(guī)則， 也是當(dāng)前查詢優(yōu)化研究的主要研究?jī)?nèi)容。對(duì)于查詢 優(yōu)化算

11、法的研究仍然是查詢優(yōu)化研究的一個(gè)難點(diǎn) 和熱點(diǎn)。在數(shù)據(jù)庫(kù)中，最難處理和優(yōu)化的多連接查 詢，由于多個(gè)關(guān)系連接時(shí)可以有很多不同的次序， 因此對(duì)應(yīng)的查訊執(zhí)行計(jì)劃的數(shù)目會(huì)隨著該查詢包 含的關(guān)系個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)，當(dāng)關(guān)系個(gè)數(shù)很多時(shí)， 將導(dǎo)致搜索空間極度膨脹，這將使得傳統(tǒng)的搜索算 法無(wú)能為力。現(xiàn)在越來(lái)越多成熟的優(yōu)化算法被引入 到多連接查詢優(yōu)化中來(lái)，如爬山算法、模擬退火算 法、遺傳算法，都在一定程度上提高了查詢優(yōu)化的 性能。2.2 并行查詢優(yōu)化目前并行查詢優(yōu)化的研究主要是基于兩階段 的并行查詢優(yōu)化策略。兩階段優(yōu)化方法是最有影響 的縮減并行查詢優(yōu)化空間的方法。其基本思想是把 查詢優(yōu)化劃分為兩個(gè)階段，第一階段采用傳

12、統(tǒng)的查 詢優(yōu)化方法產(chǎn)生一個(gè)高效的順序查詢執(zhí)行計(jì)劃；第 二階段稱為并行化階段，對(duì)第一階段產(chǎn)生的順序查 詢執(zhí)行計(jì)劃進(jìn)行并行化，產(chǎn)生一個(gè)優(yōu)化的并行查詢 執(zhí)行計(jì)劃。兩階段優(yōu)化能夠明顯地縮減搜索空間， 并且可以直接利用傳統(tǒng)的、成熟的順序優(yōu)化技術(shù)， 系統(tǒng)設(shè)計(jì)人員只需將精力集中于并行化階段。但兩 階段優(yōu)化技術(shù)有一個(gè)重要的假設(shè)：對(duì)最優(yōu)順序計(jì)劃 的并行化可以得到最優(yōu)的并行計(jì)劃。但我們認(rèn)為并 行查詢操作具有不同的處理特性，對(duì)資源的競(jìng)爭(zhēng)使 用模式也不同，并行查詢之間的交互作用將使得最 優(yōu)順序計(jì)劃并行后不再最優(yōu)。由于并行查詢系統(tǒng)的性能因素繁多，因此目前 關(guān)于并行查詢的性能分析和評(píng)估大多是通過(guò)實(shí)驗(yàn) 的方法進(jìn)行。并行查詢

13、的性能模型大致可分為：白 盒模型和黑盒模型。白盒模型通常需要找出應(yīng)用程 序負(fù)載特征（輸入）和性能（輸出）之間的定量函 數(shù)關(guān)系。數(shù)據(jù)庫(kù)系統(tǒng)常見的負(fù)載特征包括緩沖池請(qǐng) 求、I/O數(shù)、查詢隊(duì)列長(zhǎng)度、查詢到達(dá)順序等等。 常見性能指標(biāo)包括吞吐率、延遲、資源利用率等。然而，由于負(fù)載特征和性能輸出之間的關(guān)系非常復(fù) 雜， 是很難給出明確的函數(shù)表達(dá)的。黑盒模型把 整個(gè)系統(tǒng)看成一個(gè)黑盒子，不考慮系統(tǒng)的內(nèi)在邏 輯，避開去尋找負(fù)載特征和性能輸出之間的定量關(guān) 系，而是通過(guò)概率統(tǒng)計(jì)、機(jī)器學(xué)習(xí)等方法去預(yù)測(cè)性 能輸出。目前，由于黑盒模型自身的特點(diǎn)，越來(lái)越 受到人們的關(guān)注，已廣泛應(yīng)用于一些復(fù)雜的數(shù)據(jù)庫(kù) 系統(tǒng)性能分析和建模中。黑

14、盒模型主要有以下幾類：分析模型、基于機(jī)器學(xué)習(xí)的模型、線性回歸、 回歸樹、局部加權(quán)線性回歸、高斯處理等。本文中基于黑盒模型方法對(duì)并行查詢之間的 交互影響進(jìn)行量化分析，從而避開了對(duì)復(fù)雜的底層 物理系統(tǒng)進(jìn)行建模。這個(gè)模型是從單獨(dú)運(yùn)行和兩兩 并發(fā)執(zhí)行查詢的樣本中推導(dǎo)出來(lái)的。2.3 查詢交互目前，在數(shù)據(jù)庫(kù)研究領(lǐng)域?qū)Σ樵儍?yōu)化的研究非 常多，但令人意外的是，關(guān)于普通意義上的查詢交 互的研究目前還非常少。在國(guó)外一些研究機(jī)構(gòu)，已 經(jīng)有一些學(xué)者開始針對(duì)查詢交互進(jìn)行一些探索，主 要基于查詢交互進(jìn)行延遲預(yù)測(cè)和性能評(píng)估。而在國(guó) 內(nèi)，據(jù)我們所知，還沒有發(fā)現(xiàn)有學(xué)者進(jìn)行這方面的 研究，我們的工作是國(guó)內(nèi)第一次在并行查詢優(yōu)化研

15、究中引入了查詢交互的分析。目前一些具體的研究 工作例如多查詢的優(yōu)化、事務(wù)組合優(yōu)化等，都沒有 考慮這些并行查詢以及并發(fā)執(zhí)行中的一些交互影 響。這些不考慮交互作用的性能模型通常被用來(lái)進(jìn) 行性能預(yù)測(cè)、容量規(guī)劃和異常檢測(cè)等。在本文中，A Ti/jICR詢之間的并行交互成本率。表2列出了幾對(duì)兩兩查我們將證明被這些研究工作忽略的交互作用會(huì)對(duì) 性能產(chǎn)生非常巨大的影響。3查詢交互對(duì)系統(tǒng)性能的影響分析為了描述并發(fā)查詢的交互作用會(huì)對(duì)數(shù)據(jù)庫(kù)系統(tǒng)性能產(chǎn)生巨大的影響，我們用TPC-H測(cè)試基準(zhǔn)中 的查詢語(yǔ)句在大小為 10G的數(shù)據(jù)庫(kù)上進(jìn)行了一系列 實(shí)驗(yàn)研究。我們的數(shù)據(jù)庫(kù)系統(tǒng)用的是MySQL5.1 ,我們的實(shí)驗(yàn)運(yùn)行在雙核3.

16、4GHz的Intel Xeon CPUs和12G內(nèi)存，WindowsServer2003的機(jī)器。數(shù)據(jù)庫(kù) 的緩沖池大小設(shè)置為 2.4G。我們假設(shè)相關(guān)的數(shù)據(jù)庫(kù) 配置參數(shù)都已經(jīng)進(jìn)行了很好的優(yōu)化。我們用Q1,Q2,Q22來(lái)表示TPC-H的22個(gè)查 詢類型。查詢組合就是包含了不同數(shù)量的不同的 TPC-H查詢類型實(shí)例，這些實(shí)例中TPC-H規(guī)范定義了需要的不同的參數(shù)值（這些查詢實(shí)例可以用 TPC-H的QGEN程序生成）。因?yàn)門PC-H使用均勻 分布的數(shù)據(jù)和查詢參數(shù)，因此對(duì)一個(gè)特定的查詢類 型來(lái)說(shuō)，不同參數(shù)的查詢實(shí)例的執(zhí)行時(shí)間會(huì)有一些 微小的差異。因?yàn)槲覀冞x擇了10G的數(shù)據(jù)庫(kù)規(guī)模，因此為了實(shí)驗(yàn)方便我們從TPC

17、-H查詢類型中選擇10個(gè)較小量級(jí)的查詢類別為研究對(duì)象，這 10個(gè)查 詢類的執(zhí)行時(shí)間在所有22個(gè)查詢類中也都是相對(duì)較短的。首先，我們用 QGEN程序?yàn)檫@個(gè)10個(gè)查詢類 分別生成10個(gè)實(shí)例，然后在 10G數(shù)據(jù)庫(kù)上單獨(dú)運(yùn) 行這100個(gè)查詢語(yǔ)句，記錄每個(gè)查詢的執(zhí)行時(shí)間， 從而可以得到每個(gè)查詢類單獨(dú)運(yùn)行時(shí)的平均運(yùn)行 時(shí)間。表1顯示了這些查詢類在 10G數(shù)據(jù)庫(kù)上運(yùn)行 時(shí)的平均花費(fèi)時(shí)間。Tj代表了特定的查詢類型的10個(gè)實(shí)例的平均運(yùn)行時(shí)間。Tj將作為我們以后研究交互作用的基準(zhǔn)時(shí)間。表1 : TPC-H查詢單獨(dú)運(yùn)行時(shí)的平均完成時(shí)間查詢類型平均運(yùn)行時(shí)間Tj （秒）Q3210.76Q4163.43Q6174.92Q

18、7349.77Q8167.90Q10290.45Q1227.25Q1650.49Q1714.88Q19158.73在下一節(jié)中，我們將分別通過(guò)實(shí)驗(yàn)來(lái)描述不同 類型的查詢交互，以及不同并發(fā)級(jí)別產(chǎn)生的交互作 用對(duì)查詢性能的影響。3.1 兩兩查詢之間的交互分析為了更好地描繪查詢之間是如何交互的，我們 首先來(lái)研究?jī)蓚€(gè)查詢之間的交互作用。我們選擇 TPC-H中運(yùn)行時(shí)間較短的10個(gè)查詢類，執(zhí)行所有查詢類之間的唯一的兩兩組合，共有n*（n+1）/2 = 55個(gè)查詢組合。分別執(zhí)行55個(gè)查詢組合，并記錄相應(yīng)的查詢執(zhí)行時(shí)間的變化。用Ti表示Qi單獨(dú)運(yùn)行時(shí)的執(zhí)行時(shí)間，Ti/j表示Qi與Qj并發(fā)時(shí)的執(zhí)行時(shí) 間，則可以

19、A Ti/j來(lái)表示Qi與Qj并發(fā)時(shí)的變化。A Ti/j = Ti/j - Ti如果A Ti/j是正的，說(shuō)明速度變慢了，如果是 負(fù)值，說(shuō)明速度變快了。需要注意的是兩兩查詢之 間的交互不是對(duì)稱的（A Ti/j 豐 A Tj/i）為了定量的分析并行交互成本，我們定義了一個(gè)新的度量指標(biāo)：并行交互成本率ICR（InteractionCost Rate):Ti通過(guò)實(shí)驗(yàn)，我們可以得到10個(gè)查詢類兩兩查詢交互的并行交互成本率:表2:兩兩交互的并行交互成本率序號(hào)QiQjTi/jTj/iICR(i/j)ICR(j/i)1Q3Q72Q4Q83Q6Q144Q7Q195Q10Q16實(shí)驗(yàn)分析：當(dāng)Q3和Q7 一起并行時(shí)，Q

20、3獲 得了 10秒的加速，而 Q7的執(zhí)行時(shí)間卻增加了30秒。當(dāng)Q6和Q14一起運(yùn)行時(shí)，他們都會(huì)獲得平 均10秒的加速。這是因?yàn)樗鼈兊牟樵儓?zhí)行計(jì)劃都 主要是進(jìn)行事實(shí)表的順序掃描。當(dāng)Q19和Q7并發(fā)運(yùn)行時(shí)，他們的運(yùn)行時(shí)間分別增加了大約50秒和30秒。由此可見，并行查詢之間的交互作用會(huì)對(duì)查詢 性能產(chǎn)生非常顯著的影響，有時(shí)這些影響會(huì)是積極 的，但有時(shí)也會(huì)是消極的。而交互作用的產(chǎn)生又是 非常復(fù)雜的，其原因也是多種多種多樣的。例如， 一個(gè)查詢 Q1會(huì)把數(shù)據(jù)加載到緩沖池中，然后一個(gè) 并行查詢 Q2會(huì)用到這個(gè)數(shù)據(jù)，那就會(huì)產(chǎn)生積極的 交互作用。而相對(duì)應(yīng)的，在硬件資源使用上的沖突 會(huì)使Q1和Q2會(huì)互相競(jìng)爭(zhēng)，例如對(duì)

21、 CPU、內(nèi)存或 者數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)部資源例如存取鎖的使用上產(chǎn)生 的沖突，都會(huì)產(chǎn)生消極的交互作用。3.2 高并行級(jí)別的查詢交互分析在分析了兩兩并行查詢之間的交互影響之后， 我們將對(duì)更高級(jí)別(并行級(jí)別大于2)的查詢交互進(jìn)行研究和分析。我們用MPL ( multiprogramminglevel)來(lái)表示數(shù)據(jù)庫(kù)系統(tǒng)的并行級(jí)別，MPL是指在任何時(shí)候在系統(tǒng)中并發(fā)執(zhí)行的查詢語(yǔ)句的數(shù)量。那 么我們將系統(tǒng)中并行執(zhí)行的一組查詢定義為一個(gè) 查詢組合Mi ,我們假設(shè)有t個(gè)查詢類型，那么查詢 組合 Mi可以被表示為一個(gè)矢量 , 這兒Nij是查詢組合Mi中查詢類型Qj的實(shí)例數(shù)量， 我們把組合 Mi中的查詢類型 Qj的平均運(yùn)

22、行時(shí)間表 示為Aij。從以上定義我們可以知道：Ni1+Ni2 + Ni3 + +Nit = M我們通過(guò)不同的實(shí)驗(yàn)來(lái)分析高并行級(jí)別情況 下查詢交互對(duì)查詢組合中每個(gè)查詢?nèi)蝿?wù)的的完成 時(shí)間的影響。首先，我們對(duì)M=5的兩個(gè)查詢類型的不同組合 的交互作用進(jìn)行分析，如表3所示。在表3中我們依次減少Q(mào)19的實(shí)例數(shù)量，同時(shí)增加 Q6的實(shí)例數(shù) 量，從而觀察 Q6和Q19的執(zhí)行時(shí)間的變化情況。表3:兩個(gè)查詢類型的不同組合的交互作用分析MixQ6 Nij )Q19(Nij )Q6(Aij )Q19 (Aij )M1050M214M323M432M541M6500從以上數(shù)據(jù)可以看出，即使只有兩個(gè)查詢類型 時(shí)，僅僅用一

23、個(gè)查詢類型的實(shí)例來(lái)替換另一個(gè)查詢 類型的實(shí)例也會(huì)顯著地改變查詢執(zhí)行時(shí)間，這也進(jìn) 一步證明了查詢交互的重要性。接下來(lái)，我們將分析多種查詢類型的組合中交 互作用。在表4中我們對(duì)不同查詢組合中其它實(shí)例 的變化對(duì)同一查詢執(zhí)行時(shí)間的影響。表4:不同查詢組合對(duì)同一查詢的不同影響MixQ4(Nij )Q7 (Nij )Q16(Nij )Q16 (Aij )M7041172.49M8131140.24M9221129.62M10311M11401在表4中，首先Q16的完成時(shí)間因?yàn)橐粋€(gè)Q4的實(shí)例的加入而減少，然后當(dāng)我們繼續(xù)增加Q4的實(shí)例數(shù)量和減少 Q7的實(shí)例數(shù)量時(shí)，Q16完成時(shí)間 出現(xiàn)不規(guī)則的變化，有降低也有增

24、加。這也說(shuō)明，并行查詢的交互作用是相當(dāng)復(fù)雜的， 在查詢組合中的一個(gè)小的改變有時(shí)會(huì)對(duì)性能有巨下面，我們將對(duì)多種查詢類型的組合進(jìn)行試驗(yàn)，如表5所示。我們選擇 4個(gè)查詢類型的實(shí)例進(jìn)行變化組合，保持組合的實(shí)例數(shù)量 M=5不變，即保持并 行級(jí)別不變。大的影響，但這些可能是非常難預(yù)測(cè)的。表5:不同查詢組合的實(shí)例數(shù)量和平均運(yùn)行時(shí)間MixQ3Q7Q10Q16NijAijNijAijNijAijNijAijM121386.851560.903425.180386.85M131352.111501.962380.411352.11M141332.051469.64003332.05M15所有的 mi構(gòu)成了一個(gè)查詢

25、組合集在表5中我們可以得到以下幾個(gè)方面的結(jié)論： 一個(gè)包含了多種查詢類的組合并行運(yùn)行時(shí)可能 既包含積極的交互，也包含消極的交互。一些查 詢類，在并行環(huán)境下他們的查詢執(zhí)行時(shí)間表現(xiàn)出更 多的不確定性，他們對(duì)一起并行的其他查詢的影響 更加的敏感。相反，其它一些查詢類就更加的穩(wěn)定, 這個(gè)查詢可能就是一個(gè)簡(jiǎn)單的查詢?nèi)蝿?wù)，例如僅僅 包含一個(gè)數(shù)據(jù)表的掃描和一個(gè)輕量級(jí)的合計(jì)。以上這些實(shí)驗(yàn)也說(shuō)明了除非我們能夠?qū)Σ樵兘M 合中的并行交互影響進(jìn)行建模，否則我們不可能得 到最優(yōu)化的查詢性能，如果只關(guān)注單獨(dú)的查詢類型 而忽略并行交互作用，我們將不能夠得出關(guān)于性能 的準(zhǔn)確的結(jié)論。因此，我們認(rèn)為開發(fā)基于查詢組合 的交互作用的性

26、能模型對(duì)我們更好地進(jìn)行性能優(yōu) 化是非常重要的。4交互感知的并行查詢優(yōu)化策略通過(guò)第三節(jié)的分析，我們知道了并行查詢的交 互對(duì)性能有著非常大的影響。因此，為了實(shí)現(xiàn)最優(yōu) 化的并行查詢性能，我們下一步將基于查詢交互進(jìn) 行性能分析，并提出一個(gè)交互感知的性能優(yōu)化策 略，使并行任務(wù)能夠按照一定的順序執(zhí)行，從而達(dá) 到任務(wù)完成總時(shí)間最小的目標(biāo)。查詢?nèi)蝿?wù)完成的總 時(shí)間可以定義為從第一個(gè)查詢開始啟動(dòng)到所有查 詢都完成時(shí)總共消耗的時(shí)間。4.1交互成本最低優(yōu)先算法我們已知并行負(fù)載W由N個(gè)查詢?nèi)蝿?wù) Q1,Q2,Q3 Qn構(gòu)成，每個(gè)查詢所屬的 TPC-H查詢 類型是已知的，數(shù)據(jù)庫(kù)的并發(fā)級(jí)別為 Mo通過(guò)分析 我們可以知道在并行

27、過(guò)程中， 同時(shí)只有M個(gè)查詢?cè)?執(zhí)行，這M個(gè)查詢就構(gòu)成了一個(gè)查詢組合 mi,由X=m1,m2,，mi。此外，我們做了以下兩個(gè)假設(shè)：1、所有特定類型的查詢都有著相同的性能；2、數(shù)據(jù)庫(kù)可以以任意的順序執(zhí)行隊(duì)列中的查詢?nèi)蝿?wù)。查詢之間的優(yōu) 先級(jí)限制可以在系統(tǒng)外進(jìn)行強(qiáng)行控制?；谝陨戏治龊图僭O(shè)，我們的性能優(yōu)化算法的 主要目標(biāo)就是優(yōu)先執(zhí)行交互成本低的查詢組合，避 免執(zhí)行交互成本高的查詢組合，從而使整個(gè)并行任 務(wù)的交互成本最低，也就是任務(wù)總執(zhí)行時(shí)間最少。 優(yōu)化策略的執(zhí)行步驟可以描述如下：1) 從N個(gè)查詢?nèi)蝿?wù)中選擇M個(gè)查詢組成一個(gè)并行交互成本最小的查詢組合Mmin啟動(dòng)并行任務(wù)；2)在任意一個(gè)查詢 Qmin最先結(jié)

28、束時(shí)，得到 Mmin中的其他(M-1 )個(gè)查詢?nèi)蝿?wù)；3)對(duì)每一個(gè)等待隊(duì)列中的查詢，計(jì)算其與正 在執(zhí)行的(M-1 )個(gè)查詢組成的查詢組合 的并行交互成本；4)獲得新的并行交互成本最小的查詢Qnext;5)重新從2)開始循環(huán)執(zhí)行；6)以此類推，直到完成所有的查詢?nèi)蝿?wù)。以上算法用形式化語(yǔ)言可以表示如下：輸入：并行負(fù)載 W,由N個(gè)查詢組成；輸出：并行交互成本最小優(yōu)先的查詢執(zhí)行順 序。Algorithm ICRMF (W)BeginselectMminFromW(W);runMmin();while (Qmin is end) dorunQM = getRunQueryMix(M-1);for each

29、 Qi in arrival queue doICR(i) = EstimateICR(Qi,runQM);end forsortArrivalQuery(ICR with runQM ); getTheMinICRQueryToAdd();end WhileEnd要實(shí)現(xiàn)以上的性能優(yōu)化算法，我們要選擇交互 成本最小的查詢組合就必須選擇一個(gè)適合的性能 模型，對(duì)查詢組合的交互成本進(jìn)行建模分析。對(duì)不 同的并發(fā)級(jí)別需要進(jìn)行分別建模，當(dāng)并發(fā)級(jí)別為 2 時(shí)，我們可以直接用實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析；當(dāng)并發(fā)級(jí) 別大于2時(shí)，我們需要建立更復(fù)雜的性能模型，從 而能夠更好地估計(jì)并行查詢組合的交互成本。而對(duì) 于高級(jí)別的并發(fā)查

30、詢交互的性能模型，可以從單獨(dú)(非并發(fā))運(yùn)行和兩兩并發(fā)執(zhí)行的樣本中推導(dǎo)出 來(lái)。4.2并行查詢交互的性能模型在本節(jié)中，我們將探討如何對(duì)高并行級(jí)別的查 詢交互建立性能模型。因?yàn)椴樵兘换プ饔玫漠a(chǎn)生因 素是非常復(fù)雜的，為了避免建立如此復(fù)雜的模型而 需要的監(jiān)控需求，我們采用了實(shí)驗(yàn)驅(qū)動(dòng)的黑盒模 型。實(shí)驗(yàn)驅(qū)動(dòng)的模型使我們能夠粗略地估計(jì)并行狀 態(tài)下查詢之間是如何進(jìn)行交互的。當(dāng)一個(gè)新的查詢 Qj加入到一個(gè)查詢組合Mi中時(shí)，由于Qj的加入而產(chǎn)生的并行交互成本率可以 計(jì)算如下：ICRAi1-T1Ai2-T2=Ni1 x1 + Ni2 x T2 + Ni3 xAi3-T3Ait -TtT3 + + Nit x Tt A

31、ij-Tj=N Nij jJ Tj其中，Tj是Qj在單獨(dú)執(zhí)行時(shí)的運(yùn)行時(shí)間，而 Aij是Qj在Mi中執(zhí)行時(shí)的平均運(yùn)行時(shí)間，Nij是組合Mi中Qj的實(shí)例數(shù)量。有很多著名的模型結(jié)構(gòu)，例如線性回歸、回歸 樹、局部加權(quán)線性回歸、高斯處理等等，都可以用 來(lái)描述并行查詢之間的交互作用。此外，利用機(jī)器 學(xué)習(xí)技術(shù)可以對(duì)查詢交互進(jìn)行性能建模。在我們的 研究中，我們發(fā)現(xiàn)多元線性回歸模型和機(jī)器學(xué)習(xí)是 一個(gè)非常適合對(duì)查詢組合的性能進(jìn)行描述的模型 結(jié)構(gòu)，因此下一步我們將利用多元線性回歸模型和 機(jī)器學(xué)習(xí)技術(shù)進(jìn)行相關(guān)方面的深入研究。5實(shí)驗(yàn)評(píng)估與分析本章將交互感知的優(yōu)化(Interaction Cost Minimum Fir

32、st, ICMF)算法和傳統(tǒng)數(shù)據(jù)庫(kù)的最短時(shí)間優(yōu) 先(Shortest Job First, SJF)算法和先到先服務(wù)(First Come First Served, SCSF)算法進(jìn)行對(duì)比實(shí)驗(yàn)。首先 介紹了實(shí)驗(yàn)環(huán)境，然后給出實(shí)驗(yàn)結(jié)果，并進(jìn)行了結(jié) 果的評(píng)估和分析。5.1 實(shí)驗(yàn)環(huán)境實(shí)驗(yàn)使用的硬件配置是：Intel Core 2 Pentium 4Duo CPU 2.83 GHz , 12 GB 內(nèi)存。操作系統(tǒng)為 Windows 2008 ,數(shù)據(jù)庫(kù)采用的是開源的MySQL5.0 ,使用的存儲(chǔ)引擎是 MyISAM ,有10G大小的數(shù)據(jù)。 我們用C+語(yǔ)言實(shí)現(xiàn)了我們的優(yōu)化算法，作為一個(gè)獨(dú)立的組件來(lái)進(jìn)行查

33、詢?nèi)蝿?wù)的優(yōu)化調(diào)度，調(diào)度組件 在查詢?nèi)蝿?wù)啟動(dòng)之前工作，和數(shù)據(jù)庫(kù)服務(wù)器在邏輯 上是獨(dú)立的。5.2 實(shí)驗(yàn)分析我們從TPC-H中選擇了 6個(gè)運(yùn)行時(shí)間較短的查詢類型，每個(gè)查詢類型生成了30個(gè)查詢語(yǔ)句實(shí)例，總共180個(gè)查詢語(yǔ)句。假設(shè) 180個(gè)查詢語(yǔ)句按照每 個(gè)類型依次加載 n個(gè)實(shí)例的順序到達(dá)，優(yōu)化器提前 可以知道即將到來(lái)的 30個(gè)查詢?nèi)蝿?wù)。實(shí)驗(yàn)一：將數(shù)據(jù)庫(kù)的并發(fā)級(jí)別MPL分別設(shè)置為10, 20, 30,依次加載n=6個(gè)，然后分別用ICMF 算法、SJF算法和SCSF算法進(jìn)行調(diào)度，并記錄整 個(gè)查詢?nèi)蝿?wù)所消耗的總時(shí)間。通過(guò)實(shí)驗(yàn)可以知道， 我們的考慮了并行交互作用的優(yōu)化策略比傳統(tǒng)的 查詢調(diào)度算法優(yōu)化了很多。14

34、 ICMF SJF SCSFMPL=10MPL=20MPL=30122實(shí)驗(yàn)二：將數(shù)據(jù)庫(kù)的并發(fā)級(jí)別 MPL設(shè)置為20, 變化n的值，依次設(shè)置為n=3,6,9,然后分別用ICMF 算法、SJF算法和SCSF算法進(jìn)行調(diào)度，觀察實(shí)驗(yàn) 結(jié)果并記錄整個(gè)查詢?nèi)蝿?wù)所消耗的總時(shí)間。通過(guò)實(shí)驗(yàn)證明，我們的算法比最短時(shí)間優(yōu)先算 法和先到先執(zhí)行算法優(yōu)化了很多。1）對(duì)并發(fā)級(jí)別為10的數(shù)據(jù)庫(kù)系統(tǒng)，執(zhí)行100 個(gè)查詢?nèi)蝿?wù)的總時(shí)間比較。2）提高并發(fā)級(jí)別為 20,證明隨著并發(fā)級(jí)別的 提升，ICMF算法的優(yōu)勢(shì)更加明顯。6結(jié)束語(yǔ)在本論文中，介紹了一種數(shù)據(jù)庫(kù)系統(tǒng)的基于交 互感知的并行查詢優(yōu)化策略。首先回顧了查詢優(yōu)化 領(lǐng)域的相關(guān)研究工作

35、。在此基礎(chǔ)上發(fā)現(xiàn)在進(jìn)行性能 優(yōu)化時(shí)往往忽略了并行查詢之間的交互影響，而通 過(guò)實(shí)驗(yàn)我們證明了并行查詢之間的交互作用會(huì)對(duì) 系統(tǒng)性能產(chǎn)生非常巨大的影響。因此，我們認(rèn)為在 進(jìn)行并行查詢性能優(yōu)化時(shí)考慮這些交互作用是有 必要的。引入了一個(gè)并行查詢組合的性能指標(biāo)（IC）來(lái)度量查詢之間的交互成本，并提出了一個(gè)交互成 本最低優(yōu)先（ICMF）的執(zhí)行算法，通過(guò)本算法可以 對(duì)數(shù)據(jù)庫(kù)系統(tǒng)中并行查詢實(shí)現(xiàn)較為理想的任務(wù)調(diào) 度。通過(guò)實(shí)驗(yàn)證明，交互成本最低優(yōu)先算法是一種 有效的任務(wù)調(diào)度算法，比傳統(tǒng)的查詢優(yōu)化策略在整 體性能上有了較大的提升。在本文的研究中，還存在很多不足之處，這些 將是我們進(jìn)一步研究工作的方向。在本文中，我們

36、假設(shè)預(yù)先知道所有的查詢，但在實(shí)際的應(yīng)用系統(tǒng) 中，用戶提交的查詢都是隨機(jī)的，預(yù)先無(wú)法獲得， 因此就需要一種在線的查詢優(yōu)化方法，隨著用戶查 詢的實(shí)時(shí)變化，進(jìn)行不斷遞增的性能分析和優(yōu)化。 我們還計(jì)劃用更高級(jí)的機(jī)器學(xué)習(xí)的方法來(lái)研究查 詢交互對(duì)性能的影響，從而進(jìn)一步提高我們模型的 準(zhǔn)確性。另外，基于交互感知的優(yōu)化策略是對(duì)固定 的并發(fā)級(jí)別進(jìn)行建模分析，下一步我們將研究自適應(yīng)調(diào)整的并發(fā)級(jí)別，從而最大化提高系統(tǒng)的吞吐率 和性能?？傊覀冋J(rèn)為并行查詢之間的交互影響 是一個(gè)值得我們進(jìn)行深入研究的課題，是一個(gè)挑戰(zhàn) 和機(jī)遇并存的領(lǐng)域，未來(lái)將在數(shù)據(jù)庫(kù)性能預(yù)測(cè)、負(fù) 載調(diào)度和資源分配等領(lǐng)域?qū)⒂蟹浅V闊的應(yīng)用前 景。Ref

37、erences:1 J. Duggan, U.Cetintemel, O.Papaemmanouil, et al. Performance prediction for concurrent database workloads。/ In SIGMOD Conference, 2011:337-348.2 M. Ahmad, A.Aboulnaga, S.Babu, et al. Modeling and exploiting query interactions in database sys- temsC/ In proceedings of CIKM, 2008:183-192.3 M

38、. Ahmad, S.Duan, A.Aboulnaga, et al. Interaction -aware prediction of business intelligence workload completion timesC/ In proceedings of ICDE, 2010: 413-416.4 TPC-H benchmark specification, /tpch/5 A. Ganapathi, H. Kuno, U. Dayal, et al. Predicting multiple metrics for queries: Bet

39、ter decisions enabled by machine learningC/ In proceedings of ICDE, 2009: 592-603.6 M. B. Sheikh, U. F. Minhas, O. Z. Khan, et al. A bayesian approach to online performance modeling for database appliances using gaussian modelsC/ International Conference on Autonomic Computing, June 2011.7 C. Hauff,

40、 L. Azzopardi, and D. Hiemstra. The combination and evaluation of query performance prediction methodsC/ In Proceedings of ECIR, 2009:301-312.8 C. Gupta, A. Mehta, and U. Dayal. PQR: Predicting Query Execution Times for Autonomous Workload ManagementC/International Conference on Autonomic Computing, 2008:13-