江苏龙网

  1. 首页 > 资讯 > 科技 > >

|批量随机键值的查询优化


一、 问题描述
键值查询是很常见的查询场景 ， 在数据表上建有索引后 ， 即使表中数据记录数巨大（几亿甚至几十亿行） ， 用键值查询出单条记录也会很快 ， 因为建立索引后的复杂度只有 O(log2N) ，10 亿行数据大概只要比较 30 几次（10 亿约等于 2^30） ， 在现代计算机上是个毫秒级别的事务 。
不过 ， 如果需要查询的键值很多 ， 比如多达几千甚至几万的时候 ， 如果每次都独立查找 ， 那读取和比较也会累积到几万甚至几十万次 ， 时间延迟由此也会涨到几十秒甚至几十分钟的级别 ， 简单地使用数据库索引对于用户体验必然是难以容忍的了 。
本文将讨论大批量键值查询的性能优化方法 ， 示例代码将用集算器 SPL 完成 。 SPL 代码简洁易懂 ， 且提供了丰富的算法支持 ， 非常适合实现这种高性能计算 。
二、 单一整数键值
我们先考虑最简单的单一整数键值情况 ， 即用作键的字段只有一个 ， 且为整数 。
2.1 存储
与大多数分析场景不同 ， 键值查找更适合使用行式存储而非列式存储 。 因为行存是按记录 ， 一条条连续存储的 。 而列存是按列存储的 ， 对整条记录来说并不连续 ， 读取单条记录时 ， 需要从更多的数据块中读取数据 ， 访问量反而更多 。
对于超大规模数据下的随机批量键值查找 ， 不适合对数据进行压缩 。 因为命中的结果分布有可能很分散 ， 大概率出现解压一个数据块仅能获取一条记录的情况 ， 浪费很多解压缩时间 ， 使得查询效率变低 。
2.2 索引
通常我们会针对查找键建立索引 ， 这样指定键值可以迅速定位 ， 而不必遍历数据 。 我们知道 ， 索引的本质也是排序 ， 利用键值有序可以快速用二分法找到指定记录 。 那么 ， 如果数据本身对键值就有序 ， 是不是可以不建索引了？
键值有序的数据本身往往过大 ， 不能放在内存中 ， 即使利用二分法查找时 ， 也多次读取外存用以对比 。 建立索引后 ， 可以预加载索引到内存 ， 在内存中对索引查找 ， 相比多次读取外存效率高很多 。 所以 ， 即使数据有序 ， 再建立索引对于高速查找仍然有意义 。
反过来 ， 建立了索引后 ， 还要求数据对键值有序吗？
对于键值无序并建有索引时 ， 读取数据时需要再按物理位置排序, 因为外存数据是按块存储的, 在大批量查找时 ， 同一块有可能涉及多条找到的记录 ， 而如果按键值次序去读取时 ， 物理次序如果键值次序不同 ， 就可能发生同一块被读多次的情况 ， 性能损失严重 ， 所以一定要在读取前将欲读数据按物理位置排序 。 而取出的数据还要再按原顺序排序 ， 来回就多两个排序步骤 。 读取的数据量大的时候会有些影响效率 ， 若数据有序存放则可以省去这两次排序的开销 。 如果每次读取的数据量不大时 ， 额外排序损失的性能也很少 ， 可以不必按键值有序 。
2.3 索引缓存
当数据量很大时 ， 索引本身也会很大 ， 无法全部放入内存 ， 这样每一次的查找都需要从硬盘上读取索引 。 如果对索引再建立外层索引（可能有多级） ， 再在进行批量查找之前 ， 尽可能多地预先加载多级索引缓存 ， 减少重复读取索引的次数 ， 就可以提升查询效率 。
2.4 查找
查找时 ， 将待查找的键值集有序排序 ， 当查完一个键值后 ， 由于键值是有序（升序）的 ， 下一个键值肯定不小于上一个键值 ， 这样就不会重复读取比上一个索引区间更小的索引块 ， 少走回头路 。
2.5 举例
|批量随机键值的查询优化
本文插图

使用 SPL 创建一个满足以上数据结构的行存组表：
|批量随机键值的查询优化
本文插图

用键值 id ， 建立索引：


推荐阅读


上一篇：宋清辉|宋清辉：期待数字人民币早日广泛使用

下一篇：|高中端产品分层或有助于化解成本困境