在多維索引表格（multi－dimensional table）上進(jìn)行掃描和篩選是現(xiàn)代分析型數(shù)據(jù)庫引擎的關(guān)鍵技術(shù)。為了對這些操作進(jìn)行優(yōu)化，數(shù)據(jù)庫常建立起聚類的索引結(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)。通過同時(shí)優(yōu)化索引結(jié)構(gòu)以及存儲布局，這種結(jié)構(gòu)自動地調(diào)整自身以適應(yīng)具體數(shù)據(jù)集和查詢集合。該工作用來為端到端學(xué)習(xí)型數(shù)據(jù)庫系統(tǒng)構(gòu)建索引模塊。

論文背景

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

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

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

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

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

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

2． 使用三個真實(shí)數(shù)據(jù)集評估了多個不同的多維索引結(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í)對Y和Z兩個屬性進(jìn)行篩選，對其中某一個維度進(jìn)行排序的二分搜索無法順利完成該任務(wù)。

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

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

模型基本操作

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)

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

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

責(zé)任編輯：gt