关系数据库帝国已经独孤求败几十年了!
自从 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 份, 给下一层分类器进行分类, 这样节点的预测器学习的数据少而简单, 总体的时间成本也能够保证.
来源: http://zhuanlan.51cto.com/art/201905/596430.htm