Python社区  »  机器学习算法

机器学习能革了数据库索引的命吗?

码农翻身 • 3 月前 • 48 次点击  

本文来自峰峰max的投稿,老刘做了修改。

关系数据库帝国已经独孤求败几十年了!


自从1970年E.F.Codd 的《大型共享数据库的关系模型》论文横空出世,为关系型数据库奠定了坚实的理论基础,一众关系数据库System R,DB2 ,Oracle,MySQL,Postgres相继诞生,一举推翻了层次和网状数据库的统治。


在过去的几十年中, 对象数据库, NoSQL等相继挑战,但是依然无法撼动它的地位。


当然关系数据库也不是停滞不前,它也在进化,统一的SQL标准,强大的事务支持,更加聪明的查询优化器......


但是帝国也有一个巨大的硬伤,数据都保存在硬盘上,比起内存和CPU来,硬盘实在是太慢了。 如果说内存是火箭的话,硬盘就是驴车。


帝国想出了很多办法,但总是不能彻底解决问题,到目前为止,一个比较好的办法就是使用B+树。


比如有一张表User, 假设它只有两列(id, age),ID为主键Key。

图1


那么它的B+树存储结构为:


 (图2:B+树中节点也保存在磁盘块中)


最后一层为有序的数据页,每个页包含指向下一个数据页的页号(也就是地址),这里假设一条记录占据一个数据页,那么第一条记录在1号数据页,第二条记录在2号数据页,依次类推。


这样以来,如果用户想获取ID = 4的记录,数据库只需要读取三次磁盘就可以找到记录所在的数据的页号(page)为4。 

 

图3


机器学习大使


这一天, 帝国的早朝上来了一位神秘的客人,号称是机器学习王国的大使,他自称带来了一个咒语,能够根据一个数据库记录的索引列的值(比如主键Key=4),瞬间定位到记录的页号( page = 4),连那三次硬盘读写都不需要


这绝对是个革命性的技术,国王非常感兴趣,下旨让大使详细讲述。


B+树大臣马上就感受到了威胁,如果真有这个咒语,自己官位不保,于是他赶紧阻止:“陛下,老夫有所耳闻,机器学习虽然风靡IT世界,但是也有很多招摇撞骗,不着边际的故事,这个大使,很有可能就是想推销几个鬼都看不懂的数学模型来骗钱!”


国王把没有说话,把目光射向大使。 


机器学习大使脸微微一沉,心中想到,不把这个老头子搞定,也就无法说服国王, 既然你送上门来,我就拿你开刀吧。 


他主意打定,胸有成竹,先给B+树大臣戴高帽挖个坑: “大人误会了,小人知道您在数据库王国是绝对的中流砥柱, 您采用多叉平衡树的方式,降低了索引层次,减少了硬盘I/O时间,并在叶子节点上维护一个根据key(索引列)排序的线性表(S),获得了范围查询的能力....”


B+树微微一笑,心想这小子是有备而来啊,懂得不少。


从key直接找到page


然而大使话锋一变:“但是,说白了,它就是一个通过key获取数据记录页面(page)一个映射关系!而这和机器学习中的回归要干的事情是一样的,都是通过一些特征预测目标值,比如通过每个人的年龄,收入等信息预测你的潜力值,只不过说在数据库这个场景下key是特征,page是目标值。” 


B+树不屑道:“难道机器学习只要是映射就可以学吗?有点忽悠了吧!”


大使忍住这当面的嘲讽,平心静气地说:“您要知道,这个key和page之间是有关系的!而您正是忽略它两者可能存在的强关联!。”


说到这里,大使不知道从哪里变出一块小黑板,在上面画了图2,然后说:“比如说我现在有一堆数据,每条记录占一个数据页,他们的key和page之间的关系是这样的 ”



机器学习大使清了清嗓子:“对于机器学习模型,比如我用一个简单的线性回归算法,假定模型为page=a * key + b,而我们当前训练集,也就是这棵B+树中key与之对应page数据(1,1),(2,2)…(12,12),也就是说a,b必须得满足1=a+b,2=2a+b…12=12a+b这12个等式,就相当于我们小时候求解二元一次方程组一般,我们得到a = 1,b = 0, 于是乎我们得到了最终模型page = key!”


应对复杂情况


B+树大臣冷笑一声,转向国王:“陛下,别被他的数学公式蒙蔽,这是骗小孩的把戏!哪有page = key这么简单的情况! 再说了,这种简单的情况,还用得着机器学习? 我用肉眼都看出来他们的关系是page=key!  来来来,机器学习大使,我给你说个复杂点儿的情况,如果有些数据页能装两条记录呢?你给我说说page 和key 之间的关系是啥?”



现在的对应关系不是那么简单了。



机器学习大使不仅不慢不紧不慢地回答道:“线性模型只是我们大家族中最简单的地模型罢了,不管你一个数据页能存储几条记录, 只要给出(key,page)对应的数据集合,我们都可以训练神经网络,找到满足他们之间关系的一个函数 page = f(key)!通过这个函数,只要你给出key的值,立刻就能得出page! ”


B+树有点明白了,这机器学习就是为了找到一个key和页面之间的关系啊,以后访问起来就方便了,他背上开始冒汗了。


机器学习大使穷追不舍,亮出了最大杀招:“使用B+树, 存储开销是O(n/m)(m为树的出度),查询开销是O(log(n)), 而使用神经网络,查询开销是O(1) !” 


O(1) ! 


听到这句话, 全场一片哗然,所有人都知道这意味着什么,这就是革命呀,革B+树的命呀! 


大臣们开始窃窃私语:“这神经网络很厉害啊!”


“是啊!神经网络最擅长干这个事情了!从一堆数据中找到关联关系。”


“听说神经网络在两层的情况下就能够拟合一切函数!”


B+树大臣有点慌,语气也弱了下来:“你们机器学习是很牛逼,但像LR,GBDT,SVR,包括你说的这些神经网络,一些深度学习的方法,哪个不是有一定错误率的,位置预测错误,难道要全部扫描一遍数据不成,你们懂不懂我们索引的业务呀!”


机器学习大使早就预料到了会有这个问题, 他一字一句郑重道:“将机器学习赋能数据库,我们是认真的! 传统这些预测算法的应用场景,都是在训练数据数据集里做训练,然后对未知的数据做预测。但索引这个场景,嘿嘿,它是一个封闭场景,没有新的数据,只需要对数据库中存在的数据做预测即可,这种场景下,就像我刚才提到的神经网络完全可以胜任,直接就在当前数据上,训练到做到百分百的正确率即可。”


全场再次哗然,众位大臣齐刷刷地看着国王,似乎等待着最终的宣判。


绝地反击


B+树大臣顿时印堂发黑,心想几十年的风光就要今日终结吗,本来随着SSD等新型硬件的诞生我的日子就不好过了, 难道今日命丧机器学习之手?悲伤难以平复,摇摇欲坠。 


这个时候,CBO(基于代价的优化器)从后面走过来,一把扶住B+树,看着这个日益苍老的老头,说道:“大人莫慌,别看他和嚣张,但是有巨大漏洞,看我来对付他。”


CBO大臣说道:“你之前说的只是查找和存储性能,索引的维护(增/删/改)代价难道不用考虑吗,如果索引发生了变化,之前的page= f(key)这个函数还有效吗? 是不是还得重新训练神经网络,找到新的函数 page = f1(key)?  这还是O(1)的时间复杂度吗?我们数据库面对的是通用场景,不要以为只考虑几个case就觉得可以替代我们了!”


机器学习大使大惊,功败垂成!自己已经隐藏的这么深,还是被发现了缺陷,顿时红了个脸:“您说的对,我们在索引的更新上还没有很好的解决方案,但我们只是想为数据库索引带来一些新鲜想法,做现在的技术选项的补充,并没有想着取代谁。”


B+树一听,立刻满血复活:“陛下,您看看,这是一个不成熟的方案,对于数据查找能做到O(1), 但是对于数据更新就完全不行了,居然还想替代我!我就说这机器学习是招摇撞骗嘛!” 


数据库国王摇摇头:“爱卿所言差矣,这个机器学习的思路还是非常新奇的,我们还是要学习一下的, 来人,给机器学习大使送上白银千两,好好安顿。”


后记


这篇文章的灵感来源于一篇论文《The Case for Learned Index Structures》,实际上真正要把机器学习应用的索引上,就算考虑只读场景,往往也会因为数量太大,关系太多复杂,导致计算量、模型复杂度方面的问题,所以提出这个论文的作者提到通过建立层次模型的方式解决:根节点的分类器将记录划分成n份,给下一层分类器进行分类,这样节点的预测器学习的数据少而简单,总体的时间成本也能够保证。


最新热门文章

为什么996工作制只提互联网公司?

四次面试:程序员越来越悲催了

必须要裁掉那些老家伙

为什么学习编程要从Web开始?

我是一个线程

我是一个Java Class

CPU阿甘

面向对象圣经

TCP/IP之大明邮差

负载均衡的原理

一个故事讲完HTTPs

编程语言的巅峰

JavaScript:一个屌丝的逆袭


Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/32914
 
48 次点击  
分享到微博