> Photo by Franki Chamaki on Unsplash
OLAP數據庫的唯一問題是查詢可以一次在多個列上完成，例如 查詢以按用戶，日期和城市獲得訂單總數。 從技術上講，您也可以在多個維度上創建索引，但是您必須假設用戶將遵循哪種查詢模式。 您還必須假設每列將保留的數據量才能做出有效的索引決策。
如果數據庫本身根據插入的數據調整其索引怎麼辦？ 學習型多維索引是為解決此特定問題而做出的努力。 在此博客中，我們將介紹其中一種算法。
泛洪算法
泛洪算法已針對內存中索引進行了設計。 也可以對其進行修改以在OLTP數據庫中使用。 Flood背後有兩個主要思想：
使用樣本查詢過濾器工作負載來確定使用某些維度的頻率，將哪些維度一起使用以及哪些維度比其他維度更具選擇性。 根據此信息，自定義整個佈局以優化性能。
使用經驗CDF模型將多維偏斜的數據展平為統一的空間。
讓我們假設需要在d維數據上創建索引。 在此類數據中，沒有自然的排序順序。 因此，該算法首先選擇將用於排序的維。 然後，該算法會創建一個d-1維網格，其中每個維都分為等距的列。 這樣的網格中的每個單元都包含多個數據點。
為確保數據點均勻分佈，請使用特定維度的最小值和最大值對它們進行歸一化。 最後一個維度用於對每個單元格內的數據進行排序。
查詢
查詢通常由k個維度組成，其中k
對於具有部分重疊的單元格，我們可以使用對它們中的數據進行排序的事實，並使用二分查找來選擇相關數據。 僅當您將排序維度作為查詢的一部分時，才有可能。 此步驟稱為優化。
擁有所有數據後，我們可以進一步優化它以檢查是否存在任何超出範圍的數據，然後將結果返回給用戶。 此步驟稱為掃描。
佈局優化
FLOOD的主要優勢在於其優化數據佈局以最小化查詢延遲的能力。 為了最大程度地減少延遲，您首先需要一個代理來確定查詢性能。 該算法使用自定義成本函數來達到目的。 成本函數由三部分組成：
wpNc，其中wp是對一個單元執行優化的平均時間，Nc是網格中單元的總數。
wrNc其中wr是對一個單元執行優化的平均時間，而Nc是網格中單元的總數。
wsNs，其中ws是執行每次掃描的平均時間，Ns是掃描的數據點的總數。
然後，查詢時間的模型可以計算為-
wpNc + wrNc + wsNs
下一步是計算權重wp，wr和ws。 為此，Flood使用一個簡單的模型，該模型具有以下特徵：諸如細胞總數，可過濾細胞大小的均值，中位數和尾部分位數，維數等。Flood僅訓練一次權重模型並重復使用 適用於多種數據佈局。
最後一步是優化佈局，其中包括擺弄排序維的維和每個維中的列數。
在每次迭代中，算法都會選擇d維之一作為排序維。 其餘所有尺寸均用於創建d-1尺寸網格。 然後，它運行梯度下降算法來確定使查詢時間最短的列數。
Flood為每個新工作負載重新調整數據佈局。 由於數據庫管理員無法生成最可能的查詢作為模型的輸入，因此Flood本身會通過隨機分配一些維度進行分組，另一些維度進行過濾並保留其餘維度來生成用於訓練的查詢。 聚合函數分組也是隨機的。
結論
泛洪算法標誌著自學習索引道路上的重要里程碑。 如本文所示，它非常實用，可以在實際數據庫中使用。 但是，Flood仍然存在一些缺陷，需要對其進行修復以使其成為完全通用的算法。 其中一些缺點是-
它不支持插入新數據。 如果有新數據到達，則需要重新擬合整個數據集。 當前版本只能用於只讀工作負載。
它是單線程的，在當前的實現中不支持併發。
儘管Floodlight會將自身重新調整為新的工作負載，但仍難以確定何時工作負載已發生足夠的變化以觸發重新調整操作。
最後，我希望這些問題將來會得到解決，並且OLAP數據庫最終將變得至少快一個數量級，如本文中所示。
您可以使用以下參考資料來了解有關Learned數據結構和索引的更多信息：
Vikram Nathan，丁嘉琳，Mohammad Alizadeh，Tim Kraska學習多維索引
Tim Kraska，Alex Beutel，Ed H. Chi，Jeffrey Dean，Neoklis Polyzotis所學的索引結構案例
(本文翻譯自Kartik Khare的文章《Learning Multi-dimensional indices: The next big thing in OLAP DBs》，參考：https://towardsdatascience.com/learning-multi-dimensional-indices-a7aaa2044d8e)
