在多維索引表格（multi－dimensional table）上進(jìn)行掃描和篩選是現(xiàn)代分析型數(shù)據(jù)庫(kù)引擎的關(guān)鍵技術(shù)。為了對(duì)這些操作進(jìn)行優(yōu)化，數(shù)據(jù)庫(kù)常建立起聚類的索引結(jié)構(gòu)（indexes），如R－Trees，Z－ordering等，然而這些索引結(jié)構(gòu)在不同的數(shù)據(jù)集以及查詢集合（query workload）下很難進(jìn)行統(tǒng)一優(yōu)化。在本篇論文中，提出了名為Flood的多維學(xué)習(xí)索引結(jié)構(gòu)。通過(guò)同時(shí)優(yōu)化索引結(jié)構(gòu)以及存儲(chǔ)布局，這種結(jié)構(gòu)自動(dòng)地調(diào)整自身以適應(yīng)具體數(shù)據(jù)集和查詢集合。該工作用來(lái)為端到端學(xué)習(xí)型數(shù)據(jù)庫(kù)系統(tǒng)構(gòu)建索引模塊。

論文背景

在多維索引表格上進(jìn)行掃描和篩選是現(xiàn)代分析型數(shù)據(jù)庫(kù)引擎的關(guān)鍵技術(shù)之一。如果數(shù)據(jù)完全根據(jù)其中某一個(gè)屬性（attribute）進(jìn)行組織，即不會(huì)涉及到多個(gè)屬性同時(shí)被訪問(wèn)的情況，那么通過(guò)建立平衡樹(shù)或者進(jìn)行簡(jiǎn)單二分搜索的方法已經(jīng)足夠。然而，如果數(shù)據(jù)需要通過(guò)不同屬性進(jìn)行篩選，那么通過(guò)建立多層索引的方法是不足以解決問(wèn)題的。多層索引所帶來(lái)的存儲(chǔ)代價(jià)是的這項(xiàng)技術(shù)只能被應(yīng)用在很小的范圍內(nèi)。另一種解決方案是建立起多維索引（multi－dimensional indexes）對(duì)數(shù)據(jù)進(jìn)行組織管理。如Redshift以及Spark－SQL使用Z－ordering技術(shù)來(lái)對(duì)數(shù)據(jù)進(jìn)行布局，一些空間數(shù)據(jù)庫(kù)則嘗試使用R－tree來(lái)進(jìn)行索引。然而，現(xiàn)有的多維索引技術(shù)有著顯著的缺點(diǎn)。首先，這些技術(shù)都非常難以根據(jù)實(shí)際的數(shù)據(jù)集進(jìn)行優(yōu)化。其次，沒(méi)有一項(xiàng)方案可以作為所有問(wèn)題的統(tǒng)一解決方法。不同的數(shù)據(jù)集以及查詢集合將會(huì)決定使用不同的多維索引技術(shù)。

為了解決上述缺點(diǎn)，本文提出了名為Flood的基于內(nèi)存的學(xué)習(xí)多維索引。該索引方案的重點(diǎn)在于自動(dòng)地同時(shí)優(yōu)化數(shù)據(jù)存儲(chǔ)布局以及索引的結(jié)構(gòu)，以此來(lái)獲得優(yōu)于其他所有多維索引的索引速度。Flood框架有以下兩個(gè)重點(diǎn)idea：

1． 使用一個(gè)下采樣的查詢集合，即一小部分查詢樣例構(gòu)成的查詢集合樣本，以此來(lái)學(xué)習(xí)不同維度屬性在查詢過(guò)程中的使用頻率?；谠?a target="_blank">信息，F(xiàn)lood框架自動(dòng)地調(diào)節(jié)數(shù)據(jù)存儲(chǔ)布局，以此優(yōu)化索引性能。

2． 使用一個(gè)累計(jì)分布函數(shù)CDF（Calculative Distribution Function）模型來(lái)將多維上可能的傾斜數(shù)據(jù)映射到一個(gè)均勻空間中。這個(gè)平滑（Flatten）過(guò)程使得每一個(gè)存儲(chǔ)的存儲(chǔ)單元儲(chǔ)存的數(shù)據(jù)量基本一致。以此更快地進(jìn)行索引。

Flood框架的主要貢獻(xiàn)有三：

1． 提出了第一個(gè)學(xué)習(xí)型多維索引，F(xiàn)lood框架。Flood從一個(gè)篩選斷言集合，即一個(gè)下采樣的查詢集合中學(xué)習(xí)查詢集合的分布函數(shù)，以此調(diào)節(jié)數(shù)據(jù)存儲(chǔ)布局。

2． 使用三個(gè)真實(shí)數(shù)據(jù)集評(píng)估了多個(gè)不同的多維索引結(jié)構(gòu)，實(shí)驗(yàn)顯示Flood框架大大優(yōu)于其他的多維索引結(jié)構(gòu)。

3． 實(shí)驗(yàn)顯示出Flood框架在不同的Filter Predicates上都實(shí)現(xiàn)了搜索加速，其索引結(jié)構(gòu)的建立速度與其他多維索引的建立速度相當(dāng)。

論文模型

多維索引查詢的難點(diǎn)在于同時(shí)對(duì)Y和Z兩個(gè)屬性進(jìn)行篩選，對(duì)其中某一個(gè)維度進(jìn)行排序的二分搜索無(wú)法順利完成該任務(wù)。

數(shù)據(jù)布局

如果把整個(gè)多維空間看作一個(gè)歐幾里得空間的話，不同于單維數(shù)據(jù)，多維數(shù)據(jù)不可以基于一個(gè)維度，或者屬性進(jìn)行排序，這導(dǎo)致很多單維上可以使用的索引方法在多維索引上并不適用。但是如果將整個(gè)空間分成一個(gè)個(gè)小的格子，在單獨(dú)一個(gè)格子內(nèi)使用統(tǒng)一維度進(jìn)行排序，則在訪問(wèn)該格子內(nèi)的數(shù)據(jù)中就可以通過(guò)使用單維索引技術(shù)加速索引。

模型基本操作

1． 映射查找存儲(chǔ)塊（Projection）：通過(guò)查詢中的篩選條件得到需要遍歷的數(shù)據(jù)網(wǎng)格，并且將索引范圍約束在這些網(wǎng)格當(dāng)中。

2． 凝練查找范圍（Refinement）：對(duì)按照某一維度進(jìn)行排序的網(wǎng)格數(shù)據(jù)進(jìn)行進(jìn)一步篩選，根據(jù)查找篩選條件對(duì)排序維度的限制進(jìn)一步縮小檢索的范圍。

3． 進(jìn)行搜索。

網(wǎng)格優(yōu)化

網(wǎng)格分割需要決定每一個(gè)維度所應(yīng)該分割的子空間個(gè)數(shù)。Flood框架可以通過(guò)學(xué)習(xí)選擇合適的網(wǎng)格個(gè)數(shù)以及決定哪一個(gè)維度作為排序維度，即在網(wǎng)格內(nèi)對(duì)數(shù)據(jù)進(jìn)行排序的維度。

數(shù)據(jù)學(xué)習(xí)優(yōu)化索引結(jié)構(gòu)

1． 數(shù)據(jù)平滑化

根據(jù)CDF模型，對(duì)空間進(jìn)行不均勻的劃分，達(dá)到每一個(gè)網(wǎng)格的數(shù)據(jù)點(diǎn)數(shù)量基本一致。實(shí)驗(yàn)顯示當(dāng)數(shù)據(jù)量方差較小時(shí)，索引的速度有所加快。

2． 快速查找范圍凝練（使用機(jī)器學(xué)習(xí)方法）

在凝練搜索范圍的過(guò)程中，通過(guò)使用學(xué)習(xí)索引模型，RMI（Recursive Model Index），這一個(gè)多層線性回歸模型的索引結(jié)構(gòu)，加速范圍索引的速度。論文中稱之為piecewise linear model。

實(shí)驗(yàn)

本文在Sales，OSM，Perform三個(gè)真實(shí)數(shù)據(jù)上進(jìn)行了試驗(yàn)。

同時(shí)，還驗(yàn)證了數(shù)據(jù)扁平化等優(yōu)化方法在提升索引速度上的有效性。

責(zé)任編輯：gt