關(guān)系數(shù)據(jù)庫(kù)帝國(guó)已經(jīng)獨(dú)孤求敗幾十年了!

[[265264]]

自從1970年E.F.Codd 的《大型共享數(shù)據(jù)庫(kù)的關(guān)系模型》論文橫空出世，為關(guān)系型數(shù)據(jù)庫(kù)奠定了堅(jiān)實(shí)的理論基礎(chǔ)，一眾關(guān)系數(shù)據(jù)庫(kù)System R，DB2 ，Oracle，MySQL，Postgres相繼誕生，一舉推翻了層次和網(wǎng)狀數(shù)據(jù)庫(kù)的統(tǒng)治。

在過(guò)去的幾十年中， 對(duì)象數(shù)據(jù)庫(kù)， NoSQL等相繼挑戰(zhàn)，但是依然無(wú)法撼動(dòng)它的地位。

當(dāng)然關(guān)系數(shù)據(jù)庫(kù)也不是停滯不前，它也在進(jìn)化，統(tǒng)一的SQL標(biāo)準(zhǔn)，強(qiáng)大的事務(wù)支持，更加聰明的查詢(xún)優(yōu)化器......

但是帝國(guó)也有一個(gè)巨大的硬傷，數(shù)據(jù)都保存在硬盤(pán)上，比起內(nèi)存和CPU來(lái)，硬盤(pán)實(shí)在是太慢了。 如果說(shuō)內(nèi)存是火箭的話(huà)，硬盤(pán)就是驢車(chē)。

帝國(guó)想出了很多辦法，但總是不能徹底解決問(wèn)題，到目前為止，一個(gè)比較好的辦法就是使用B+樹(shù)。

比如有一張表User, 假設(shè)它只有兩列(id, age)，ID為主鍵Key。

圖1

那么它的B+樹(shù)存儲(chǔ)結(jié)構(gòu)為：

(圖2：B+樹(shù)中節(jié)點(diǎn)也保存在磁盤(pán)塊中)

***一層為有序的數(shù)據(jù)頁(yè)，每個(gè)頁(yè)包含指向下一個(gè)數(shù)據(jù)頁(yè)的頁(yè)號(hào)(也就是地址)，這里假設(shè)一條記錄占據(jù)一個(gè)數(shù)據(jù)頁(yè),那么***條記錄在1號(hào)數(shù)據(jù)頁(yè)，第二條記錄在2號(hào)數(shù)據(jù)頁(yè)，依次類(lèi)推。

這樣以來(lái)，如果用戶(hù)想獲取ID = 4的記錄，數(shù)據(jù)庫(kù)只需要讀取三次磁盤(pán)就可以找到記錄所在的數(shù)據(jù)的頁(yè)號(hào)(page)為4。

圖3

機(jī)器學(xué)習(xí)大使

這一天， 帝國(guó)的早朝上來(lái)了一位神秘的客人，號(hào)稱(chēng)是機(jī)器學(xué)習(xí)王國(guó)的大使，他自稱(chēng)帶來(lái)了一個(gè)咒語(yǔ)，能夠根據(jù)一個(gè)數(shù)據(jù)庫(kù)記錄的索引列的值(比如主鍵Key=4)，瞬間定位到記錄的頁(yè)號(hào)( page = 4)，連那三次硬盤(pán)讀寫(xiě)都不需要。

這絕對(duì)是個(gè)革命性的技術(shù)，國(guó)王非常感興趣，下旨讓大使詳細(xì)講述。

B+樹(shù)大臣馬上就感受到了威脅，如果真有這個(gè)咒語(yǔ)，自己官位不保，于是他趕緊阻止：“陛下，老夫有所耳聞，機(jī)器學(xué)習(xí)雖然風(fēng)靡IT世界，但是也有很多招搖撞騙，不著邊際的故事，這個(gè)大使，很有可能就是想推銷(xiāo)幾個(gè)鬼都看不懂的數(shù)學(xué)模型來(lái)騙錢(qián)!”

國(guó)王把沒(méi)有說(shuō)話(huà)，把目光射向大使。

機(jī)器學(xué)習(xí)大使臉微微一沉，心中想到，不把這個(gè)老頭子搞定，也就無(wú)法說(shuō)服國(guó)王， 既然你送上門(mén)來(lái)，我就拿你開(kāi)刀吧。

他主意打定，胸有成竹，先給B+樹(shù)大臣戴高帽挖個(gè)坑： “大人誤會(huì)了，小人知道您在數(shù)據(jù)庫(kù)王國(guó)是絕對(duì)的中流砥柱， 您采用多叉平衡樹(shù)的方式，降低了索引層次，減少了硬盤(pán)I/O時(shí)間，并在葉子節(jié)點(diǎn)上維護(hù)一個(gè)根據(jù)key(索引列)排序的線(xiàn)性表(S)，獲得了范圍查詢(xún)的能力....”

B+樹(shù)微微一笑，心想這小子是有備而來(lái)啊，懂得不少。

從key直接找到page

然而大使話(huà)鋒一變：“但是，說(shuō)白了，它就是一個(gè)通過(guò)key獲取數(shù)據(jù)記錄頁(yè)面(page)一個(gè)映射關(guān)系!而這和機(jī)器學(xué)習(xí)中的回歸要干的事情是一樣的，都是通過(guò)一些特征預(yù)測(cè)目標(biāo)值，比如通過(guò)每個(gè)人的年齡，收入等信息預(yù)測(cè)你的潛力值，只不過(guò)說(shuō)在數(shù)據(jù)庫(kù)這個(gè)場(chǎng)景下key是特征，page是目標(biāo)值。”

B+樹(shù)不屑道：“難道機(jī)器學(xué)習(xí)只要是映射就可以學(xué)嗎?有點(diǎn)忽悠了吧!”

大使忍住這當(dāng)面的嘲諷，平心靜氣地說(shuō)：“您要知道，這個(gè)key和page之間是有關(guān)系的!而您正是忽略它兩者可能存在的強(qiáng)關(guān)聯(lián)!。”

說(shuō)到這里，大使不知道從哪里變出一塊小黑板，在上面畫(huà)了圖2，然后說(shuō)：“比如說(shuō)我現(xiàn)在有一堆數(shù)據(jù)，每條記錄占一個(gè)數(shù)據(jù)頁(yè)，他們的key和page之間的關(guān)系是這樣的 ”

機(jī)器學(xué)習(xí)大使清了清嗓子：“對(duì)于機(jī)器學(xué)習(xí)模型，比如我用一個(gè)簡(jiǎn)單的線(xiàn)性回歸算法，假定模型為page=a * key + b，而我們當(dāng)前訓(xùn)練集，也就是這棵B+樹(shù)中key與之對(duì)應(yīng)page數(shù)據(jù)(1,1),(2,2)…(12,12)，也就是說(shuō)a,b必須得滿(mǎn)足1=a+b,2=2a+b…12=12a+b這12個(gè)等式，就相當(dāng)于我們小時(shí)候求解二元一次方程組一般，我們得到a = 1,b = 0, 于是乎我們得到了最終模型page = key!”

應(yīng)對(duì)復(fù)雜情況

B+樹(shù)大臣冷笑一聲，轉(zhuǎn)向國(guó)王：“陛下，別被他的數(shù)學(xué)公式蒙蔽，這是騙小孩的把戲!哪有page = key這么簡(jiǎn)單的情況! 再說(shuō)了，這種簡(jiǎn)單的情況，還用得著機(jī)器學(xué)習(xí)? 我用肉眼都看出來(lái)他們的關(guān)系是page=key! 來(lái)來(lái)來(lái)，機(jī)器學(xué)習(xí)大使，我給你說(shuō)個(gè)復(fù)雜點(diǎn)兒的情況，如果有些數(shù)據(jù)頁(yè)能裝兩條記錄呢?你給我說(shuō)說(shuō)page 和key 之間的關(guān)系是啥?”

現(xiàn)在的對(duì)應(yīng)關(guān)系不是那么簡(jiǎn)單了。

機(jī)器學(xué)習(xí)大使不僅不慢不緊不慢地回答道：“線(xiàn)性模型只是我們大家族中最簡(jiǎn)單的地模型罷了，不管你一個(gè)數(shù)據(jù)頁(yè)能存儲(chǔ)幾條記錄， 只要給出(key,page)對(duì)應(yīng)的數(shù)據(jù)集合,我們都可以訓(xùn)練神經(jīng)網(wǎng)絡(luò)，找到滿(mǎn)足他們之間關(guān)系的一個(gè)函數(shù) page = f(key)!通過(guò)這個(gè)函數(shù)，只要你給出key的值，立刻就能得出page! ”

B+樹(shù)有點(diǎn)明白了，這機(jī)器學(xué)習(xí)就是為了找到一個(gè)key和頁(yè)面之間的關(guān)系啊，以后訪(fǎng)問(wèn)起來(lái)就方便了，他背上開(kāi)始冒汗了。

機(jī)器學(xué)習(xí)大使窮追不舍，亮出了***殺招：“使用B+樹(shù)， 存儲(chǔ)開(kāi)銷(xiāo)是O(n/m)(m為樹(shù)的出度)，查詢(xún)開(kāi)銷(xiāo)是O(log(n))， 而使用神經(jīng)網(wǎng)絡(luò)，查詢(xún)開(kāi)銷(xiāo)是O(1) !”

O(1) !

聽(tīng)到這句話(huà)， 全場(chǎng)一片嘩然，所有人都知道這意味著什么，這就是革命呀，革B+樹(shù)的命呀!

大臣們開(kāi)始竊竊私語(yǔ)：“這神經(jīng)網(wǎng)絡(luò)很厲害啊!”

“是啊!神經(jīng)網(wǎng)絡(luò)最擅長(zhǎng)干這個(gè)事情了!從一堆數(shù)據(jù)中找到關(guān)聯(lián)關(guān)系。”

“聽(tīng)說(shuō)神經(jīng)網(wǎng)絡(luò)在兩層的情況下就能夠擬合一切函數(shù)!”

B+樹(shù)大臣有點(diǎn)慌，語(yǔ)氣也弱了下來(lái)：“你們機(jī)器學(xué)習(xí)是很牛逼，但像LR，GBDT，SVR，包括你說(shuō)的這些神經(jīng)網(wǎng)絡(luò)，一些深度學(xué)習(xí)的方法，哪個(gè)不是有一定錯(cuò)誤率的，位置預(yù)測(cè)錯(cuò)誤，難道要全部掃描一遍數(shù)據(jù)不成，你們懂不懂我們索引的業(yè)務(wù)呀!”

機(jī)器學(xué)習(xí)大使早就預(yù)料到了會(huì)有這個(gè)問(wèn)題， 他一字一句鄭重道：“將機(jī)器學(xué)習(xí)賦能數(shù)據(jù)庫(kù)，我們是認(rèn)真的! 傳統(tǒng)這些預(yù)測(cè)算法的應(yīng)用場(chǎng)景，都是在訓(xùn)練數(shù)據(jù)數(shù)據(jù)集里做訓(xùn)練，然后對(duì)未知的數(shù)據(jù)做預(yù)測(cè)。但索引這個(gè)場(chǎng)景，嘿嘿，它是一個(gè)封閉場(chǎng)景，沒(méi)有新的數(shù)據(jù)，只需要對(duì)數(shù)據(jù)庫(kù)中存在的數(shù)據(jù)做預(yù)測(cè)即可，這種場(chǎng)景下，就像我剛才提到的神經(jīng)網(wǎng)絡(luò)完全可以勝任，直接就在當(dāng)前數(shù)據(jù)上，訓(xùn)練到做到***的正確率即可。”

全場(chǎng)再次嘩然，眾位大臣齊刷刷地看著國(guó)王，似乎等待著最終的宣判。

絕地反擊

B+樹(shù)大臣頓時(shí)印堂發(fā)黑，心想幾十年的風(fēng)光就要今日終結(jié)嗎，本來(lái)隨著SSD等新型硬件的誕生我的日子就不好過(guò)了， 難道今日命喪機(jī)器學(xué)習(xí)之手?悲傷難以平復(fù)，搖搖欲墜。

這個(gè)時(shí)候，CBO(基于代價(jià)的優(yōu)化器)從后面走過(guò)來(lái)，一把扶住B+樹(shù)，看著這個(gè)日益蒼老的老頭，說(shuō)道：“大人莫慌，別看他和囂張，但是有巨大漏洞，看我來(lái)對(duì)付他。”

CBO大臣說(shuō)道：“你之前說(shuō)的只是查找和存儲(chǔ)性能，索引的維護(hù)(增/刪/改)代價(jià)難道不用考慮嗎，如果索引發(fā)生了變化，之前的page= f(key)這個(gè)函數(shù)還有效嗎? 是不是還得重新訓(xùn)練神經(jīng)網(wǎng)絡(luò)，找到新的函數(shù) page = f1(key)? 這還是O(1)的時(shí)間復(fù)雜度嗎?我們數(shù)據(jù)庫(kù)面對(duì)的是通用場(chǎng)景，不要以為只考慮幾個(gè)case就覺(jué)得可以替代我們了!”

機(jī)器學(xué)習(xí)大使大驚，功敗垂成!自己已經(jīng)隱藏的這么深，還是被發(fā)現(xiàn)了缺陷，頓時(shí)紅了個(gè)臉：“您說(shuō)的對(duì)，我們?cè)谒饕母律线€沒(méi)有很好的解決方案，但我們只是想為數(shù)據(jù)庫(kù)索引帶來(lái)一些新鮮想法，做現(xiàn)在的技術(shù)選項(xiàng)的補(bǔ)充，并沒(méi)有想著取代誰(shuí)。”

B+樹(shù)一聽(tīng)，立刻滿(mǎn)血復(fù)活：“陛下，您看看，這是一個(gè)不成熟的方案，對(duì)于數(shù)據(jù)查找能做到O(1)， 但是對(duì)于數(shù)據(jù)更新就完全不行了，居然還想替代我!我就說(shuō)這機(jī)器學(xué)習(xí)是招搖撞騙嘛!”

數(shù)據(jù)庫(kù)國(guó)王搖搖頭：“愛(ài)卿所言差矣，這個(gè)機(jī)器學(xué)習(xí)的思路還是非常新奇的，我們還是要學(xué)習(xí)一下的， 來(lái)人，給機(jī)器學(xué)習(xí)大使送上白銀千兩，好好安頓。”

后記

這篇文章的靈感來(lái)源于一篇論文《The Case for Learned Index Structures》，實(shí)際上真正要把機(jī)器學(xué)習(xí)應(yīng)用的索引上，就算考慮只讀場(chǎng)景，往往也會(huì)因?yàn)閿?shù)量太大，關(guān)系太多復(fù)雜，導(dǎo)致計(jì)算量、模型復(fù)雜度方面的問(wèn)題，所以提出這個(gè)論文的作者提到通過(guò)建立層次模型的方式解決：根節(jié)點(diǎn)的分類(lèi)器將記錄劃分成n份，給下一層分類(lèi)器進(jìn)行分類(lèi)，這樣節(jié)點(diǎn)的預(yù)測(cè)器學(xué)習(xí)的數(shù)據(jù)少而簡(jiǎn)單，總體的時(shí)間成本也能夠保證。

【本文為51CTO專(zhuān)欄作者“劉欣”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過(guò)作者微信公眾號(hào)coderising獲取授權(quán)】

戳這里，看該作者更多好文