一種面向分布式數據庫的多并發OLAP型查詢性能預測方法

劉驥超，杜建華，謝寒生，劉霄燕，謝召干

(1.海南省氣象信息中心，海口 570203；2.海南省南海氣象防災減災重點實驗室，海口 570203；3.海南省澄邁縣氣象局，海南 澄邁 571900)

0 引言

數據庫中并行執行查詢能夠帶來許多優勢。例如，它能夠縮短多個查詢的整體運行時間并且提高硬件的利用率，但是，對于并發查詢中的某一個查詢，相較于其單獨執行，它的執行時間可能會延長或縮短。主要原因是多個查詢之間相互影響[1]，有些查詢能夠促進該查詢的執行，有些則由于與該查詢存在資源競爭而延長查詢執行。

并發查詢性能預測對于查詢調度控制[2-6]等具有很大的應用價值，例如，如果事先能夠知道查詢執行時間，那么就可以改變多個查詢的順序，繼而達到用戶SLA要求。準確的查詢性能預測技術還能夠用于查詢進度顯示[7]，以便了解當前查詢的執行進度，然后DBA就可以做下一步的決策，等待該查詢執行完畢或殺死該查詢。查詢性能預測還對查詢優化器具有一定的指導作用，比如：查詢優化器可以更好地創建并發查詢感知的查詢計劃，以此來縮短查詢的整體執行時間。

由于查詢性能預測技術具有很大價值，所以，針對該方面有很多研究，這些研究主要面向兩類查詢，一是OLTP型查詢[8]，OLTP主要指在關系型數據庫中一些對時間要求比較高的事務型查詢，通常該類查詢的執行時間較短；二是OLAP型查詢[9]，OLAP型查詢主要運用于數據倉庫，這種類型的查詢面對的數據量比較大，執行時間比較長。本文主要面向OLAP型查詢。當前已經有一些技術能夠對分析型查詢做性能預測[10]，但這些技術在實用性和擴展性方面存在一定的局限。

本文提出了一種能夠量化多個查詢之間的資源競爭并根據資源競爭情況預測并發查詢的延遲時間的方法。在現實情況中，同一個查詢在不同的并發查詢組合下，執行時間等性能指標將產生差異，主要原因在于多個查詢要競爭使用I/O和網絡等資源。在I/O資源方面，分析型查詢通常包含許多表連接操作，每個表的數據都需要從磁盤中讀取，這會引發大量的I/O操作，而且若幾個查詢掃描不同的數據表，則會爭用I/O，導致 I/O時間變長，繼而使得查詢變慢。對于網絡資源，數據存放在分布式數據庫集群的各個節點中，這些節點位于不同的物理機器上，在執行查詢時，數據需要通過網絡在節點間遷移，因此，網絡帶寬資源的爭用也是影響性能的重要元素。模型能夠根據不同的查詢組合情況，量化資源(I/O、網絡)的使用和爭用情況，從而預測查詢延遲時間。

本文提出了兩個模型，分別是：查詢干擾度(CQI,concurrent query interference)和查詢敏感度(QS, query sensitivity)。查詢干擾度是指多個并發查詢對主查詢(要預測的查詢)的干擾程度，干擾度越大說明資源競爭越激烈,主查詢的執行延遲也越大。查詢敏感度是指主查詢在不同的查詢資源競爭情況下所表現出來的敏感程度即查詢性能，不同的查詢組合會引起不同程度的資源競爭。本文利用CQI和QS模型預測分布式數據庫中并發OLAP型查詢延遲。

1 相關工作

當前已有一些針對查詢性能預測的研究，并且有較好的效果。另外，查詢進度顯示通常也需要預測執行時間。所以，接下來，本文將介紹關于這兩面的研究并比較與本文技術的區別。

1.1 查詢進度指示器

查詢進度指示器(QPI, query progress indicators)用于指示一個查詢的進度，這樣可以直觀地了解查詢已經花費了多少時間和還需要多少時間能夠執行完畢。當前，針對QPI已經有了一些研究，Surajit等人[11]對查詢完成的比例建模，他們沒有考慮并發查詢的情況，只是針對單個查。G.Luo等人[12-13]把磁盤I/O、運行時間、消息字節數等作為度量，運用機器學習預測長查詢的進度，但是他們在預測查詢的延遲時間時，該查詢必須是在運行中，而本文的方法在查詢執行前就能夠得知查詢需要多少時間，且主要考慮并發查詢的情況，相對機器學習方法來說，更加簡單。

1.2 查詢性能預測

文獻[14-16]都是運用機器學習的方法來預測查詢性能，但都沒有處理并發查詢的情形。對于多并發查詢，文獻[9,17-19]首先對性能預測技術進行了研究，他們的共同點都是針對分析型查詢，而且考慮查詢之間的交互作用并建立回歸模型，即能夠預測不同并發度下的查詢性能。Mumtaz等人[20-21]擴展了上述的研究，他們考慮了不同組合中查詢的相互影響，根據實驗數據建立模型，從而得到了較高的準確率。Muhammad等人[7]對運行中的查詢進行預測，而Barzan等人[8]主要對OLAP型的查詢進行預測。Chetan等人[22]主要研究在數據倉庫中，查詢延遲如何隨著工作負載的改變而改變。Jennie等人[23]對并發查詢的資源競爭建模，使得預測的誤差較低。文獻[24]預測了在查詢在大數據量下的單獨執行時間，它把SQL查詢映射為一系列基礎操作符并計算操作符消耗時間之和來計算總執行時間。文獻[25]主要針對OLTP型并發查詢，運行機器學習方法以系統狀態的36個指標為基礎進行性能預測。

上述研究既有對OLAP型查詢的研究，也有對OLTP型查詢的研究，在OLAP型并發查詢的情形下，都是基于單機數據庫，并沒有考慮分布式數據庫的環境，即查詢分布在多個機器上的情形，這種查詢有網絡開銷。本文提出的查詢干擾度模型考慮了網絡資源開銷，能更準確地預測分布式數據庫并發查詢的性能。

2 分析型任務

2.1 分布式數據庫

本文使用分布式數據庫Greenplum存儲數據并查詢。分布式數據庫和單機數據庫最大的區別在于分布式數據庫是一個集群，集群中有多個節點，節點分為主節點和從節點，主節點用來管理從節點并生成查詢計劃，從節點存放數據并按照查詢計劃查詢數據。當客戶端提交一個SQL查詢到Greenplum后，Greenplum中的主節點首先解析查詢語句并生成一個代價最小的查詢計劃，然后，發送給各從節點，從節點根據查詢計劃執行查詢，并將得到的結果返回給主節點，最后，主節點得到從各從節點發送來的結果，匯總結果并返回給客戶端。

分布式數據庫能夠存儲海量的數據，且能夠通過增加節點來擴展存儲量，但由于數據分布在多個節點上，執行表連接查詢時，通常需要遷移數據，所以，相較于單機數據庫，影響查詢性能的因素不僅包含從節點的CPU，內存和I/O性能，還包括節點間網絡的性能。

2.2 分析型任務特征

分布式數據庫執行查詢時，影響查詢性能有4個重要的因素，分別為：CPU、內存、I/O和網絡，在這4個因素當中，CPU和內存相較于I/O和網絡，影響較小，因為通過實驗觀察到，在多個查詢并行執行的時候，集群中各個節都有足夠的CPU資源。另外，對于每個數據庫實例，配置充足的內存。當有多個查詢執行時，如果分配給該實例的內存耗盡，操作系統會將內存中的部分數據移到磁盤中，也就是發生頁置換，引起I/O操作。分布式數據庫最耗時的操作是掃描表，即發生I/O，其次是節點間數據傳輸。所以，本文主要研究磁盤I/O和節點間網絡因素對查詢性能的影響。

在本文的研究中，主要針對分析型查詢，其特點是包含大量的join操作，每個join需要通過I/O和網絡讀寫數據和傳輸數據，其查詢時間一般較長。多個查詢爭用I/O和網絡資源，這必然會對查詢產生影響。

本文用到的查詢是由TPC-DS中的10個模板生成[26]。選取的查詢模板分別：17，20、25、26、32、33、61、62、65、71，它們都為IO敏感型查詢，即花在I/O上的時間較多或占整個查詢時間的比例較大，有些查詢的I/O時間占整個執行時間的90%以上。

2.3 取樣

本文定義MPL(multi-programming level)為同時運行的查詢個數，當MPL=3時，表示當前有3個查詢同時執行，且這3個查詢構成一個查詢組合。由于一共有10個查詢，當MPL為2時，可以兩兩結合組成查詢組合，但當MPL等于大于3時，手工設計查詢組合會變得越來越復雜，所以，選用LHS(latin hypercube sampling)技術取樣，下面以一個例子說明如何使用該方法構建查詢組合。以MPL等于3為例，在python中，運行X=lhs(3,10)生成抽樣矩陣X：

矩陣X中的元素都位于0～1之間，然后把這些元素化為整數。變換的過程是將矩陣X中的每個元素擴大10倍，然后再向上取整得到整數矩陣Y：

Y包含10種整數，并且Y中的每行每列的數字都不重復，接下來把這10個數字映射成具體的查詢ID，映射的關系如下：

根據映射表最終得到在MPL為3下的查詢組合為：

在矩陣Z中，每一行代表一個查詢組合，每一行的第一個查詢代表該查詢組合的主查詢，其余都是并發查詢。在每個查詢組合中，每個查詢構成一個查詢流，查詢流就是讓每個查詢運行n次，這樣就得到n個樣本數據，這里只取后n-1次的數據。

2.4 預測評價

為了測量預測模型質量，本文使用平均相對誤差MRE(mean relative error)來衡量，該度量的定義如下：

(1)

observedi為實際運行的時間，predictedi為預測的時間，MRE越低，說明預測模型越準確。

3 預測模型

該部分講述如何對主查詢和并發查詢的I/O和網絡資源爭用進行建模。本文提出了查詢干擾度和查詢敏感度兩個模型，查詢干擾度用來描述主查詢當前執行環境的優劣，也即描述資源的爭用情況，而查詢敏感度是描述主查詢在不同并發查詢執行時，它的性能如何變化。

3.1 查詢干擾度

I/O和網絡是影響數據庫查詢性能最重要的兩個因素，在一定程度上能夠決定查詢總延遲。假定一個查詢組合為m，它包括主查詢q和與主查詢并行執行的查詢C={c1,c2,…,cn}，并發查詢的個數為n。首先，得到每個并發查詢ci單獨運行時需要的I/O和網絡資源，此時，沒有發生資源競爭。然后，估計每個并發查詢與主查詢爭用資源對主查詢的影響。最后，評估由于并發查詢之間爭用資源對主查詢的影響。定義變量如表2所示。

表2 主要符號含義

3.1.1 Baseline I/O

Baseline I/O指的是查詢的基準I/O，即當一個查詢獨立執行時，它的I/O時間占用執行總時間的百分比，所占百分比越大，則表示此查詢需要越多的I/O資源。用表示一個并發查詢中I/O所占的百分比。

3.1.2 Positive I/O

當主查詢與并發查詢共同執行時，如果一個并發查詢與主查詢掃描不同的表，并發查詢會對主查詢產生“干擾”，這是因為不同查詢會爭用I/O。當并發查詢與主查詢掃描相同的表時，這種“干擾”會大大減小，甚至會對主查詢產生“促進”作用，因為在數據庫中，當頻繁掃描一個表時，會把這個表的數據存入到共享緩存中，此后再請求這個表的數據，會直接從共享緩存中取，從而避免了重復性的I/O操作。下面通過模型來量化并發查詢與主查詢的相互作用。

假設表t是主查詢q與并發查詢ci共同掃描的表。定義如下值：

(2)

可以看到htci取值只有0和1，下面計算共享的I/O時間。

(3)

上述公式中，n表示主查詢和并發查詢需要掃描表的總個數，St表示掃描表t花費的時間。本文用select * from[table]形式的查詢語句獲取掃描表[table]花費的總時間，即該查詢語句執行時間中的掃描表的時間。在Greenplum中，表的數據分布到各個節點中，查詢在各個節點中執行，所以，多個查詢如果包含共同的表，則可“省去”重復在磁盤上掃描表的時間。公式(3)計算由于共享I/O的而節省的時間。

3.1.3 Concurrent I/O

除了考慮主查詢和并發查詢的共享I/O之外，還需要度量并發查詢之間的I/O影響。即主查詢與兩個并發查詢a和b共同執行時，a和b由于并發執行所節省的I/O時間。首先定義表t為并發查詢和其他非主查詢共同掃描的表：

(4)

定義dt為掃描表t的并發查詢的個數，這里dt必須大于1。另外，由于只考慮并發查詢之間的表掃描情況，所以這里的表t不能出現在主查詢當中。計算由于并發查詢共享I/O而節省的時間為：

(5)

上面公式中的n同樣是主查詢和并發查詢需要掃描表的總數。

3.1.4 網絡爭用

本文面向的是分布式數據庫，數據分布在集群中的各個節點中，SQL查詢中的表連接操作一定會發生數據傳輸，即把在一個節點上的數據遷移到另一個節點上。Greenplum中數據遷移的方式有兩種：廣播和重分布。廣播就是把一個節點上的數據傳輸給其他所有節點，從而每個節點都有一個表的完整數據。重分布就是把表的數據根據關聯鍵計算哈希值，然后再重新分布到各個節點上。假設一個表的記錄數為N，那么重分布的數據量為N，廣播的數據量為N*節點數，通過上述的方式就可以計算一個連接操作的數據遷移量。主查詢的數據遷移總量為tq，并發查詢的遷移數據量為，tci定義并發查詢對主查詢的網絡干擾為：

(6)

從上式可以看出，并發查詢ci的數據遷移量越大，對主查詢的干擾就越大；反之，則越小。這是由于系統的網絡帶寬是一定的，當網絡中有其他查詢傳輸數據時，必然會影響主查詢的數據傳輸。

3.1.5 查詢干擾度模型

得到上述各個變量以后，就可以定義并發查詢對主查詢的影響。

(7)

公式(7)可以理解為并發查詢ci與主查詢直接競爭I/O和網絡的激烈程度，公式(7)的前半部分是主查詢減去了并發查詢與主查詢共享I/O的時間，在網絡爭用確定的情況下，當γci越大，則表示并發查詢與主查詢共享I/O的時間越短，競爭I/O的時間越長，在這種情況下，會延長主查詢的查詢延遲。當γci越小，則表示并發查詢與主查詢的資源競爭越小，對主查詢的延遲影響越小。

在一個查詢組合中，定義主查詢的CQI值為γq,m，計算公式如下：

(8)

上述公式即取各并發查詢的γci平均值。

3.2 查詢敏感度

查詢敏感度是指主查詢對不同執行環境的敏感程度，這里不同的執行環境就是不同的MPL以及在相同MPL下的不同查詢組合。敏感程度指主查詢的性能變化，不同的執行環境會引起不同的資源競爭，進而導致主查詢的性能變化。下面詳細介紹該模型。

3.2.1 查詢性能區間

查詢性能區間PR(performance range)指的是一個查詢延遲時間范圍，這個區間中的值表示查詢在不同環境中的執行時間，區間的最大值為τmaxci，表示查詢在最惡劣的資源環境下的執行時間。本文通過不斷讀取大文件并在不同節點間交換傳輸這些文件模擬最差的環境。最小值為τminci，表示在當前環境中，只有這個查詢在執行時的延遲時間。上述兩個值表示在極端執行環境中的執行查詢，在其余環境下的查詢執行時間都位于該查詢性能區間中，主查詢的PRP(performance range point)值定義如下：

(9)

當知道了cq,m的值以后，將該值代入公式(9)反推可得到τq,m，即主查詢的查詢延遲。接下來，介紹如何預測cq,m的值。

3.2.2 查詢敏感度模型

在3.1節介紹了CQI模型，該模型可以用于預測查詢延遲(后面通過實驗具體驗證)。這意味著，給定一個查詢組合m和一個主查詢q，可以利用公式(8)來計算CQI值，然后使用線性回歸模型預測查詢的性能。為了進一步說明查詢性能和CQI之間的線性關系，本文引入查詢敏感度QS(query sensitivity)。

假定CQI和PRP存在線性的關系，定義如下公式：

cq,m=μq*γq,m+bq

(10)

上述公式中，μq為斜率，bq為截距，cq,m與γq,m是一種線性關系。

3.2.3 預測流程

在Greenplum中，利用QS模型預測查詢q的流程如圖1所示。

圖1 利用QS預測查詢延遲

4 實驗評估

4.1 實驗環境

實驗的環境為Greenplum分布式集群，Greenplum版本為5.0.0-alpha+79a3598。集群中共有4個節點，一個主節點和3個從節點，從節點主要用來存放數據并執行查詢，主節點則負責分配查詢和匯總結果。主節點的硬件配置為32 GB的內存，CPU為4核Intel(R)Xeon(R)CPU E5-2630 v2 @ 2.60 GHz，從節點的內存16 GB，CPU的核數和型號與主節點相同，在每個從節點中有4個數據庫實例，每個數據庫實例相當于一個完整PostgreSQL的數據庫，用于處理一部分的數據。主節點和從節點的操作系統均為CentOS 7.4，linux內核版本為3.10。

表和數據通過TPC-DS生成，TPC-DS是一個決策支持的benchmark。實驗所用數據量大小為50 G，選取TPC-DS中的10個模板生成10個查詢用于訓練和測試模型，這10個查詢主要是I/O敏感型查詢，執行時間較長，有利于提高預測模型的精度。

4.2 實驗過程

在第3節詳細講述了如何利用查詢干擾度和查詢敏感度模型預測一個查詢的延遲時間，下面通過實驗驗證上述的模型方法。具體實驗過程說明如下：

在實驗環境中，基于Greenplum數據庫集群的默認配置，執行TPC-DS基準測試。并通過設置Greenplum的并行度參數，控制同時執行的查詢數分別指定的MPL(例如：1-5)。與此同時，通過性能監控工具Telegraf采集服務器的各項資源開銷數據，并結合Greenplum返回的查詢執行時間等性能數據，構建下述提到的查詢干擾度模型和查詢敏感度模型，并據此進行分析型查詢的性能預測。

4.2.1 查詢干擾度模型

3.1節介紹了主查詢q在查詢組合m中的查詢干擾度，接下來，通過實驗驗證通過該模型預測查詢延遲是否有效。

1)查詢干擾度模型分量：

查詢干擾度評估了并發查詢對主查詢的干擾程度，干擾程度越大，對主查詢的延遲也就越大。在查詢干擾度模型中，下面分別對干擾度模型中的4個分量進行驗證。

首先是基準I/O(baseline I/O)，當模型中只有baseline I/O時，計算一個并發查詢的干擾度會變成如下形式：

γci=(τminci*Pci)/τminci

(11)

公式只計算了并發查詢與主查詢競爭的I/O帶寬，相當于并發查詢與主查詢是完全競爭的關系。

其次，在基準I/O的基礎上，加入并發查詢與主查詢的正向交互作用因素,即positive I/O，得到如下形式：

γci=(τminci*Pci-ρci)/τminci

(12)

式(12)從爭用的I/O時間中減去了由于共享表掃描所節省的時間，該公式主要考慮了并發查詢對主查詢的影響。

然后，再進一步考慮并發查詢之間的交互,即concurrent I/O，所得模型如下：

γci=(τminci*Pci-ρci-φci)/τminci

(13)

式(13)即在式(12)的基礎上加入了在一個查詢組合中，并發查詢之間的共享I/O時間。并發查詢之間的作用會間接影響主查詢的I/O操作。

最后，再加入網絡爭用的因素，得到CQI模型：

(14)

2)查詢干擾度模型驗證：

首先評估CQI的各個分量對誤差率的影響，然后利用CQI預測查詢延遲。當MPL為3時，上述各個變量對查詢延遲的預測誤差如下：

從圖2可以看到，只利用baseline I/O(對應公式(11))預測查詢延遲的時候，它的誤差較大，當加入并發查詢交互(對應公式(12))的因素后，對誤差率有明顯的降低。考慮concurrent I/O(對應公式(13))和網絡爭用因素(對應公式(14))，對預測的準確率沒有明顯提高，說明positive I/O是影響預測模型準確率的主要因素，其他因素能夠小幅度的提升準確率。綜上，CQI考慮了并發查詢之間的主要影響因素，是一個較好的預測模型。接下來，驗證CQI模型對各個查詢的誤差。

圖2 各個查詢在不同度量下的誤差

對于一個給定的查詢組合，其中有一個主查詢，其他查詢為并發查詢。實驗產生的數據分為訓練集和測試集。假設主查詢的查詢延遲和CQI存在線性關系，則通過訓練集能夠得到這個線性關系，然后，利用該線性模型對主查詢進行預測，再與測試集數據比較并計算誤差，從而得到圖3。

圖3 各個查詢在MPL等于3時的誤差

圖3為10個查詢在MPL為3時的預測情況，從圖中可以看到，查詢延遲預測的誤差大部分在25%以下。此處的誤差是平均相對誤差(MRE),其定義已經在公式(1)中給出。查詢61和62的誤差相對較高，這是由于這兩個查詢相對較為簡單，查詢時間較短，因而其它因素查詢預測的干擾較大，導致誤差相對較大。在實驗中，查詢71的誤差也相對較高。該查詢較為復雜，主要用于“對于指定的經理及其關聯的所有3個銷售渠道，找出其一個月內在早餐或晚餐時間段營收最高的產品”，其執行時間較長，因而誤差相對率偏高。該查詢的標準SQL形式如下：

select i_brand_id brand_id, i_brand brand,t_hour,t_minute,

sum(ext_price)ext_price

from item,(select ws_ext_sales_price as ext_price,

ws_sold_date_sk as sold_date_sk,

ws_item_sk as sold_item_sk,

ws_sold_time_sk as time_sk

from web_sales,date_dim

where d_date_sk = ws_sold_date_sk

and d_moy=12

and d_year=2002

union all

select cs_ext_sales_price as ext_price,

cs_sold_date_sk as sold_date_sk,

cs_item_sk as sold_item_sk,

cs_sold_time_sk as time_sk

from catalog_sales,date_dim

where d_date_sk = cs_sold_date_sk

and d_moy=12

and d_year=2002

union all

select ss_ext_sales_price as ext_price,

ss_sold_date_sk as sold_date_sk,

ss_item_sk as sold_item_sk,

ss_sold_time_sk as time_sk

from store_sales,date_dim

where d_date_sk = ss_sold_date_sk

and d_moy=12

and d_year=2002

)tmp,time_dim

where

sold_item_sk = i_item_sk

and i_manager_id=1

and time_sk = t_time_sk

and(t_meal_time = ‘breakfast’ or t_meal_time = ‘dinner’)

group by i_brand, i_brand_id,t_hour,t_minute

order by ext_price desc, i_brand_id

總體而言，除去類似于查詢61和查詢62這類因查詢任務簡單、執行時間短，易受干擾的查詢，以及查詢71這類非常復雜的查詢，TPC-DS的代表性查詢在MPL為2、4和5時的資源預測情況與MPL為3時類似，大部分查詢誤差率仍在25%以下。

4.2.2 查詢敏感度模型

前面的實驗驗證了CQI可以較準確地預測查詢延遲，而CQI是針對特定的查詢組合，為此，本文提出了QS模型，它能夠感知查詢所處的不同環境(不同的查詢組合)，并做出預測。

對于一個特定的查詢q，找到包含這個查詢的查詢組合，然后以q為主查詢構建QS模型，利用該模型預測執行時間，并與實際執行時間比較，得到結果如圖4所示。

圖4 各個查詢在不同MPL時的誤差

從圖4可以看出，不同的MPL，除去查詢61和62，查詢的誤差都在25%以下，有的甚至能夠達到20%以下。同樣的，查詢61和62的誤差較高的原因在于它們的執行時間較短，從而造成誤差較大。由此實驗結果表明，QS模型能夠適應不同的查詢執行環境(不同MPL下的不同查詢組合)，從而能夠較準確地預測查詢的執行延遲。

5 結束語

本文主要研究在分布式數據庫中預測一個查詢在多個其他查詢并行執行的情況下其執行時間的技術，考慮了I/O和網絡因素，這與其他基于機器學習的在單機數據庫上的性能預測技術有明顯不同。

本文主要提出了兩個模型，分別為：查詢干擾度和查詢敏感度。查詢干擾度(CQI)用于建立資源競爭的衡量模型，而查詢敏感度(QS)用于衡量主查詢對其他并發查詢的感知度。查詢敏感度是建立在查詢干擾度的基礎上，通過實驗發現CQI與查詢延遲存在線性關系，而QS則在CQI的基礎上建立這種線性模型，從而利用QS預測查詢延遲。

最后，實驗結果表明模型的預測誤差率大部分能夠維持在25%以下，能夠較準確地預測查詢的延遲時間。在此后的工作中，可以考慮如何使用更有效的指標來量化資源的競爭，以及如何利用查詢執行計劃輔助來建立預測模型。