在多維索引表格（multi－dimensional table）上進行掃描和篩選是現代分析型數據庫引擎的關鍵技術。為了對這些操作進行優化，數據庫常建立起聚類的索引結構（indexes），如R－Trees，Z－ordering等，然而這些索引結構在不同的數據集以及查詢集合（query workload）下很難進行統一優化。在本篇論文中，提出了名為Flood的多維學習索引結構。通過同時優化索引結構以及存儲布局，這種結構自動地調整自身以適應具體數據集和查詢集合。該工作用來為端到端學習型數據庫系統構建索引模塊。

論文背景

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

為了解決上述缺點，本文提出了名為Flood的基于內存的學習多維索引。該索引方案的重點在于自動地同時優化數據存儲布局以及索引的結構，以此來獲得優于其他所有多維索引的索引速度。Flood框架有以下兩個重點idea：

1． 使用一個下采樣的查詢集合，即一小部分查詢樣例構成的查詢集合樣本，以此來學習不同維度屬性在查詢過程中的使用頻率。基于該信息，Flood框架自動地調節數據存儲布局，以此優化索引性能。

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

Flood框架的主要貢獻有三：

1． 提出了第一個學習型多維索引，Flood框架。Flood從一個篩選斷言集合，即一個下采樣的查詢集合中學習查詢集合的分布函數，以此調節數據存儲布局。

2． 使用三個真實數據集評估了多個不同的多維索引結構，實驗顯示Flood框架大大優于其他的多維索引結構。

3． 實驗顯示出Flood框架在不同的Filter Predicates上都實現了搜索加速，其索引結構的建立速度與其他多維索引的建立速度相當。

論文模型

多維索引查詢的難點在于同時對Y和Z兩個屬性進行篩選，對其中某一個維度進行排序的二分搜索無法順利完成該任務。

數據布局

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

模型基本操作

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

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

3． 進行搜索。

網格優化

網格分割需要決定每一個維度所應該分割的子空間個數。Flood框架可以通過學習選擇合適的網格個數以及決定哪一個維度作為排序維度，即在網格內對數據進行排序的維度。

數據學習優化索引結構

1． 數據平滑化

根據CDF模型，對空間進行不均勻的劃分，達到每一個網格的數據點數量基本一致。實驗顯示當數據量方差較小時，索引的速度有所加快。

2． 快速查找范圍凝練（使用機器學習方法）

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

實驗

本文在Sales，OSM，Perform三個真實數據上進行了試驗。

同時，還驗證了數據扁平化等優化方法在提升索引速度上的有效性。

責任編輯：gt