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

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

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

 

 

學(xué)習(xí)一個(gè)想要的模型

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

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

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

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

過渡擬合很好

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

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

例如，考慮一下論文《學(xué)習(xí)索引結(jié)構(gòu)的案例》中的 RMI 模型：

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

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

3. 重復(fù)該過程，直到葉模型進(jìn)行最終預(yù)測

 

 

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

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

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

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

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

 

 

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

 

 

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

進(jìn)一步的分析表明，學(xué)習(xí)型索引幾乎可以在每種類型的查詢中擊敗聚簇索引——當(dāng)聚簇索引中的聚簇維度是查詢中的唯一維度時(shí)除外。

執(zhí)行查詢

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

 

 

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

 

 

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

作者還嘗試了工作負(fù)載感知調(diào)度程序，使用圖神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)基于強(qiáng)化學(xué)習(xí)的調(diào)度系統(tǒng)：

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

在 10 個(gè) TPC-H 查詢的示例中，學(xué)習(xí)的調(diào)度程序比 Spark 的默認(rèn) FIFO 調(diào)度程序?qū)⑵骄�作業(yè)完成時(shí)間提高了 45%。

 

 

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

查詢優(yōu)化器

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

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

其他領(lǐng)域

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

最后總結(jié)

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

作者：Adrian Colyer 譯者：吳少杰

原文鏈接：

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

論文鏈接：

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

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

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