近日，谷歌聯(lián)合 MIT、布朗大學的研究人員共同推出了新型數(shù)據(jù)庫系統(tǒng) SageDB，并撰寫了一篇論文詳述 SageDB 的設計原理和性能表現(xiàn)。他們在論文中提出了一個觀點：學習模型可以滲透到數(shù)據(jù)庫系統(tǒng)的各個方面，“基于機器學習的組件可以完全取代數(shù)據(jù)庫系統(tǒng)的核心組件，例如索引結構、排序算法，甚至是查詢執(zhí)行器。”

你或許還記得 17 年底 AI 前線發(fā)布的熱點報道《Jeff Dean 出品：用機器學習索引替代 B-Trees，3 倍性能提升，10-100 倍空間縮小》 。當時谷歌 Jeff Dean 等人出品的一篇題為《學習索引結構的案例》的論文讓整個業(yè)界為之振奮，同時也引發(fā)了大量的爭論。在 17 年的論文中，谷歌研究團隊嘗試通過實驗論證：與基于緩存優(yōu)化的 B-tree 結構相比，使用神經網(wǎng)絡在速度上可以提高 70%，并且大大節(jié)省了內存。“機器學習模型有可能比目前最先進的數(shù)據(jù)庫索引有更顯著的好處”。而今天我們要介紹的 SageDB，就是研究團隊在該研究基礎之上得出的更進一步的成果。

SageDB 背后的核心思想是構建一個或多個關于數(shù)據(jù)和工作負載分布的模型，并基于它們自動為數(shù)據(jù)庫系統(tǒng)的所有組件構建最佳數(shù)據(jù)結構和算法。我們稱之為“數(shù)據(jù)庫融合”的這種方法，將使我們能夠通過將每個數(shù)據(jù)庫組件的實現(xiàn)專門化到特定的數(shù)據(jù)庫、查詢工作負載和執(zhí)行環(huán)境來實現(xiàn)前所未有的性能。

 

 

學習一個想要的模型

在缺乏運行時學習和適應的情況下，數(shù)據(jù)庫系統(tǒng)是為通用目的而設計的，不能充分利用現(xiàn)有工作負載和數(shù)據(jù)的特定特性。SageDB 的出現(xiàn)能夠彌補二者之間的鴻溝，它在了解數(shù)據(jù)分布和工作負載的情況下，可以在特定時間設計一種可能的專用解決方案。

考慮一個極端的案例：我們希望使用連續(xù)整數(shù)鍵來存儲和查詢固定長度記錄。這里使用傳統(tǒng)索引沒有意義，因為鍵本身可以用作偏移量。AC 程序將 100M 整數(shù)加載到一個數(shù)組中，并在一個范圍內求和，運行時間約為 300ms。在 Postgres 中執(zhí)行相同的操作大約需要 150 秒，這是通用設計開銷的 500 倍。

…我們可以利用精確數(shù)據(jù)分布的知識，來優(yōu)化數(shù)據(jù)庫使用的幾乎任何算法或者數(shù)據(jù)結構。這些優(yōu)化有時甚至可以改變眾所周知的數(shù)據(jù)處理算法的復雜性。

數(shù)據(jù)分布的知識以學習模型的形式出現(xiàn)。有了這樣的模型，作者認為我們可以自動合成索引結構、排序和連接算法，甚至整個查詢優(yōu)化器，利用數(shù)據(jù)分布模式來提高性能。

過渡擬合很好

什么樣的模型有意義?舉個例子，直方圖是一個非常簡單的模型，但對于這里討論的用例，要么太粗糙，要么太大而無法使用。另一方面，深度和寬度神經網(wǎng)絡的成本很高(盡管隨著硬件的進步，這些成本可能會降低)。結合這個事實，對于這個使用場景，“過渡擬合”是好的!我們希望盡可能精確地捕捉精確數(shù)據(jù)的精確細微差別。(迄今為止的研究計劃主要集中在分析工作負載上，一旦我們開始考慮更新，一定程度的概括顯然是有益的)。

截至今天，我們發(fā)現(xiàn)我們經常需要生成特殊模型才能看到顯著的效益。

例如，考慮一下論文《學習索引結構的案例》中的 RMI 模型：

1. 在數(shù)據(jù)上擬合簡單模型(線性回歸、簡單神經網(wǎng)絡等)

2. 使用模型的預測來挑選另外一個模型，即專家，它可以更準確地模擬數(shù)據(jù)子集合

3. 重復該過程，直到葉模型進行最終預測

 

 

RMI 只是一個起點。例如，可以使頂部模型或底部模型更復雜，在特定級別階段用其他類型的模型替換部分模型，使用量化方法、改變特征表示、將模型與其他數(shù)據(jù)結構組合等。因此，我們相信我們將看到關于如何最有效地為數(shù)據(jù)庫組件生成一個模型來完成精度、低延遲、空間和執(zhí)行時間之間平衡的新想法。

數(shù)據(jù)訪問

去年關于《學習索引結構的案例》的論文表明，基于 RMI 索引可以比最先進的 B-Tree 實現(xiàn)性能提高兩倍，同時規(guī)模更小(注：研究人員已經更新了 arXiv 上的論文以包含最新測試結果，論文連接：https://arxiv.org/abs/1712.01208 )。后續(xù)工作已將其擴展到存儲磁盤、壓縮插入和多維的數(shù)據(jù)。

對于多維數(shù)據(jù)，基線是 R 樹(與 B 樹相對)。R-Tree 將矩陣映射到索引范圍列表，使得位于矩陣中的每個點索引包含在這個范圍的并集中。就像 B-Tree 一樣，我們可以用學習模型替換 R-Tree。使 RMI B-Trees 替換工作得以實現(xiàn)的一個技巧是模型足以使我們“在正確的位置”，然后我們可以圍繞預測完成本地搜索工作。對于 R-Trees，我們還需要一種能夠實現(xiàn)高效本地化搜索的布局。

雖然存在許多可能的投影策略，但我們發(fā)現(xiàn)沿著一系列維度、連續(xù)排序和分割點到相同大小的單元格，這樣計算、學習(例如，與 z-order 相比，這很難學習)、合成(即，索引范圍聯(lián)合中的幾乎所有點都滿足查詢)起來非常高效。

 

 

作者通過壓縮在內存中的列存儲上實現(xiàn)了這樣的學習索引，并將其與完整列掃描、聚簇索引(按提供最佳整體性能的列排序)和 R-Tree 進行了比較。使用 TPC-H 基準的 lineitem 表中的 6000 萬條記錄來作為基準測試，查詢選擇性為 0.25%。

 

 

學習型索引以高達 34 倍的優(yōu)勢，擊敗了下一個性能最佳的實現(xiàn)(注意圖表上的日志比例)，與聚簇解決方案相比，其空間開銷很小。

進一步的分析表明，學習型索引幾乎可以在每種類型的查詢中擊敗聚簇索引——當聚簇索引中的聚簇維度是查詢中的唯一維度時除外。

執(zhí)行查詢

這是論文中我最喜歡的一部分，因為它展示了學習模型如何能夠幫助處理這種不起眼的古老的排序問題。排序方法是使用學習模型將記錄大致按正確的順序排列，然后在最后階段再糾正為幾乎完美的排序數(shù)據(jù)。為此，可以使用非常高效的局部排序算法，比如：插入排序。

 

 

下圖顯示了從正態(tài)分布中隨機采樣 64 位雙精度數(shù)據(jù)，隨著數(shù)據(jù)量越來越大，不同排序方法的結果比較。其中，Timsort 是 Java 和 Python 的默認排序，std::sort 來自 C++ 庫。學習后的變體平均比下一個最佳(在這種情況下為 Radix 排序)快 18%。

 

 

學習的模型也可用于改善連接操作。例如，考慮一個具有兩個存儲連接列和一個模型列的合并連接。我們可以使用模型跳過不會連接的數(shù)據(jù)(作者沒有詳細說明“local patching”在這種情況下是如何工作的，這一點對于我來說理解的并不深刻)。

作者還嘗試了工作負載感知調度程序，使用圖神經網(wǎng)絡實現(xiàn)基于強化學習的調度系統(tǒng)：

我們的系統(tǒng)將調度算法表示為神經網(wǎng)絡，其采用關于數(shù)據(jù)的輸入信息(例如，使用 CDF 模型)和查詢工作負載(例如，使用在先前執(zhí)行的查詢上訓練的模型)來做出調度決策。

在 10 個 TPC-H 查詢的示例中，學習的調度程序比 Spark 的默認 FIFO 調度程序將平均作業(yè)完成時間提高了 45%。

 

 

調度器學會的策略是將快速完成短任務與最大限度地提高集群效率相結合，學習在并行性“最佳點”附近運行作業(yè)。

查詢優(yōu)化器

傳統(tǒng)的查詢優(yōu)化器非常難以構建，維護并且通常會產生次優(yōu)的查詢優(yōu)化。優(yōu)化器的脆弱性和復雜性使其成為一個很好的模型可學習的候選者…

最初的實驗從傳統(tǒng)的成本模型開始，并通過學習進行改進，結果表明模型質量可以得到改善，但要獲得大幅收益，則需要對基數(shù)估算進行重大改進。目前的研究方向(尚未報告結果)是探索基于混合模型的基數(shù)估計方法。這些混合模型結合了底層數(shù)據(jù)模式和相關性的學習模型，以及使用監(jiān)聽器(exception/outlier)來捕獲特定數(shù)據(jù)實例的極端(和難以學習)異常。

其他領域

論文提出，未來學習模型可能在以下領域也會被證明是有益的，包括近似查詢處理、預測建模和工作負載(包括插入和更新)。

最后總結

SageDB 提供了一種構建數(shù)據(jù)庫系統(tǒng)的全新方法，通過使用 ML 模型與程序合成相結合來生成系統(tǒng)組件。如果成功，我們相信這種方法將產生新一代大數(shù)據(jù)處理工具，可以更好地利用 GPU 和 TPU，在存儲消耗和空間方面提供顯著的優(yōu)勢，在某些情況下甚至可以改變某些數(shù)據(jù)操作的復雜性。

作者：Adrian Colyer 譯者：吳少杰

原文鏈接：

https://blog.acolyer.org/2019/01/16/sagedb-a-learned-database-system/

論文鏈接：

http://cidrdb.org/cidr2019/papers/p117-kraska-cidr19.pdf

標簽： 大數(shù)據(jù) 大數(shù)據(jù)處理 谷歌 數(shù)據(jù)庫 搜索 網(wǎng)絡

版權申明：本站文章部分自網(wǎng)絡，如有侵權，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權歸原作者所有，如需使用，請與原作者聯(lián)系。