名稱：A Tutorial on Learned Multi-dimensional Indexes
會議：SIGSPATIAL（2020）
機構(gòu)：Purdue University
摘要
最近桑包，機器學(xué)習(xí)（簡稱 ML）已成功地應(yīng)用于數(shù)據(jù)庫索引轧抗。對學(xué)習(xí)型索引的初步實驗表明，與傳統(tǒng)的數(shù)據(jù)庫索引相比汰瘫，它們具有更好的查找性能和更低的空間代價嫡秕。為了將學(xué)習(xí)的索引擴展到多維空間捏浊，學(xué)界已經(jīng)做出許多嘗試皮官，使得學(xué)習(xí)型索引有可能賦能空間數(shù)據(jù)庫領(lǐng)域叭爱。本教程的目標(biāo)是在單維和多維空間中提供學(xué)習(xí)型索引的最新內(nèi)容撮躁。本教程涵蓋了 25 個學(xué)習(xí)型索引技術(shù)。本教程分類了當(dāng)前不同的學(xué)習(xí)型索引买雾。
回答兩個問題
- Can one use ML techniques to guide data indexing?
- Can ML techniques replace and act in place of a multi-dimensional index?
作者的意圖顯而易見把曼，答案是“可以”。但是我認(rèn)為更多得還是展現(xiàn)了無限的潛力漓穿，當(dāng) 1-D 拓展為 M-D 時嗤军，更多的應(yīng)用將會推動該領(lǐng)域的發(fā)展，也會引起更多學(xué)者的探索晃危，我相信一定會有大有可為之日叙赚。
什么是學(xué)習(xí)型索引？
學(xué)習(xí)型索引是 ML4DB 的一個方向僚饭，由于數(shù)據(jù)庫的基本訴求是穩(wěn)定震叮、確定性等，所以很少有組成構(gòu)件（存儲鳍鸵、查詢優(yōu)化器苇瓣、索引等）被機器學(xué)習(xí)盯上。但是索引這一塊的發(fā)掘開辟了很有意思的科研空間偿乖。
學(xué)習(xí)型索引的基本思想是“索引即模型”击罪，原有數(shù)據(jù)庫中 B 樹的索被認(rèn)為是最廣泛使用數(shù)據(jù)庫索引哲嘲。第一個學(xué)習(xí)型索引（Tim Kraska 等提出）本質(zhì)上就是想替換這個結(jié)構(gòu)，通過累積分布函數(shù)（CDF）訓(xùn)練媳禁，最后得到一個可以預(yù)測上下界的回歸模型撤蚊。具體來說，整套機器學(xué)習(xí)的模型叫 RMI损话，通過多個簡單神經(jīng)網(wǎng)絡(luò)模型以決策樹的形式組合侦啸，將原有一維索引構(gòu)建的問題，轉(zhuǎn)換為 KV 對的回歸預(yù)測模型丧枪。這篇開山之作 The Case for Learned Index Structures 雖然褒貶不一光涂，通過巧妙地構(gòu)建索引問題，作者展示了在數(shù)據(jù)管理系統(tǒng)內(nèi)部使用機器學(xué)習(xí)的潛力拧烦。
痛點
- 針對更新的時候很無力忘闻。大部分工作只支持 Read-only 環(huán)境，如何支持更新恋博？
- 沒有簡單的一維轉(zhuǎn)多維的方法齐佳。多維數(shù)據(jù)沒有總序（Total Order），如果簡單用空間填充曲線债沮，效率不高炼吴，問題也大。
- 數(shù)據(jù)類型不同疫衩。有一維硅蹦、多維度、時序等數(shù)據(jù)類型
面向多維數(shù)據(jù)的學(xué)習(xí)型索引技術(shù)總結(jié)
Flood
Vikram Nathan, Jialin Ding, Mohammad Alizadeh, and Tim Kraska. Learning Multi-dimensional Indexes. SIGMOD (2020). 985–1000.
- 內(nèi)存
- 多維數(shù)據(jù)
- 考慮數(shù)據(jù)集（data）和查詢（query）的負(fù)載均衡
IF-Index
AliHadian, AnkitKumar, and ThomasHeinis. Hands-off Model Integration in Spatial Index Structures. AIDB (2020).
- 插值友好
LISA
PengfeiLi, HuaLu, QianZheng, LongYang, and GangPan. LISA:ALearned Index Structure for Spatial Data. SIGMOD (2020).
- 基于磁盤
Learned ZM Index
Haixin Wang, Xiaoyi Fu, Jianliang Xu, and Hua Lu. 2019. Learned Index for Spatial Queries. In 2019 20th IEEE International Conference on Mobile Data Management (MDM). IEEE, 569–574.
- Z-Order 空間填充曲線
Taxonomy
文章歸納總結(jié)了一下闷煤，但是我認(rèn)為不是完全的區(qū)分童芹，而且目前（2021年）來看，這種各司其職的格局已經(jīng)打破鲤拿，比如 PGM-Index 這種的存在無疑是“超級大國”假褪。
- 是否支持更新？
- Updatable
- Static
- Data layout is fixed or arranged by model
- Fix data layout
- Arrange data layout
- 模型結(jié)構(gòu)
- RMI
- 強化學(xué)習(xí)
- 簡單機器學(xué)習(xí)模型（例如插值友好）
- 數(shù)據(jù)類型
- 一維
- 多維
- 時序
收獲
作者還是直接點明了多維數(shù)據(jù)的學(xué)習(xí)型索引基本還是多維數(shù)據(jù)投影到一維 key近顷，繼而用原有學(xué)習(xí)型索引技術(shù)生音。但是不同的研究者提供了很多思路，比如 LISA 作者從磁盤數(shù)據(jù)的角度來化解天然多維數(shù)據(jù)學(xué)習(xí)型索引性能上的詬病幕庐，因為和磁盤 IO 比起來久锥，這點學(xué)習(xí)成本或者 trade-off 成本簡直是小巫見大巫。
再者异剥，F(xiàn)lood 極有可能是第一篇將學(xué)習(xí)型索引技術(shù)應(yīng)用到多維數(shù)據(jù)主體上的文獻(xiàn)瑟由，作者在 Flood 投稿后也很快完成更深入的工作——Tsunami。首先要佩服作者在數(shù)據(jù)庫學(xué)術(shù)角度的深厚知識儲備，而且他英語口音特別好歹苦，真不愧是 MIT 大神青伤。有感興趣的可以在 B 站或 Youtube 看一下 Slide。但是我認(rèn)為這兩個工作的動機還是很清晰的殴瘦，就是仍用 RMI 來套空間數(shù)據(jù)狠角。我覺得我缺乏的是對空間數(shù)據(jù)的敏感性，不知道如何去建模（Cost Model）蚪腋，同時也沒有充分的實驗角度（這取決于認(rèn)知的儲備欠缺）丰歌。所以我覺得科研者還是需要將一個領(lǐng)域踏踏實實學(xué)好，如果有一個新技術(shù)誕生的時候屉凯，才能加速內(nèi)化并擴展成為自己的工作點立帖。
總得來說，以上工作存在一個通病悠砚，即只針對 Read-only 數(shù)據(jù)集晓勇，這是不能在實際生產(chǎn)中容忍的。但是 Updatable 這個點在這兩年也做了更多的工作如 ALEX 與其后續(xù)工作灌旧，還有 PGM-Index 等绑咱，都需要仔細(xì)閱讀，探索和利用現(xiàn)有經(jīng)驗開辟自己的一個“世外桃源”枢泰。
