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

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

本文插图
使用 SPL 创建一个满足以上数据结构的行存组表：

本文插图
用键值 id ，建立索引：
分页标题

本文插图
利用索引进行批量键值查找：

本文插图
A1：这里待查找键值没有排序，因为 A4 的 T.icursor 中的 A.contain 会自动对 A 进行排序。
A3：其中 @3 的意思是将 id 键的多级索引的更多级缓存预先加载进内存。经过 index@3 预处理，第一遍查询时间就能达到索引被缓存后才能达到的极限值。另外，还有 index@2 ，相比 @3 缓存的索引层级更少，占用内存也更小。
三、复杂键值
3.1 非整数键值
非整数键值，比如车牌号，通常是由字符与数字组合成的字符串。因为字符串比较要比整数的比较复杂得多，比较速度也更慢。所以可以把这种有规律或者可枚举的字符串转为简单的整数类型，提升性能。
3.2 多字段键值
多字段键值，可以直接利用多个字段键进行查找，但集合的存储和比较都要慢一些。为了获取高性能，更常用的办法是把多字段键拼成单字段键。对于有规律或者可枚举的串，可以将串数字化后，与其他数字化后的键值合并为一个新的整数键值。
3.3 举例

本文插图
其中 pnum 和 pdate 两个字段作为联合主键确定一条记录。
3.3.1 多字段键直接查找
使用 SPL ，按以上数据结构，创建组表（和单键值类似，多键值也需要确保键值有序，可以使用cs.sortx()函数排序，具体方法详见函数参考。）：

本文插图
多字段键组表建立索引时需要包含多个维。例如，以上数据结构中的 pnum 和 pdate 两个维：

本文插图
多字段键组表查询时可以使用 n 元组。例如，以上数据结构中的 [pnum,pdate]：

本文插图
3.3.2 数字化合并键值
用以上的数据结构做个例子，来说明如何进行数字化合并键值。
pnum是个串，一共 7 位，第一位是一个随机大写英文字母，后六位都是数字，可以将字母用 ACS 码值表示，与后六位数字拼接后转为整数。 pdate 是一个日期类型字段，可以将 2007-01-01 定为起始日期， pdate 与起始日期间隔的天数可以作为该字段的数字化后的值。
pnum中大写英文字母的 ACS 码是两位数，与后面的 6 位数加起来是 8 位数，而日期 pdate 的跨度范围为 10 年，换算成天是个 4 位数，将数字化后的 pnum*10000+pdate ，就得到了一个新的 12 位的数字化字段， pid 。

本文插图
这样就得到了一个单字段键的组表“conbi.ctx” ，其数据结构如下：

本文插图
然后按照 ''单一整数键值'' 中的做法就可以处理了。
四、并行技术
4.1 数据拆分
多线程并行，是把数据分成 N 份，用 N 个线程查询。但如果只是随意地将数据分成 N 份，很可能无法真正地提高性能。因为将要查询的键值集是未知的，所以理论上也无法确保希望查找的数据能够均匀分布在每一份中。比较好的处理方式是先观察键值集的特征，从而尽可能地进行数据的均匀拆分。分页标题
如果键值数据有比较明显的业务特征，我们可以考虑按照实际业务场景使用日期、部门之类的字段来对数据进行拆分。如：将属于部门 A 的 1000 条记录均分在 10 份数据中，每份数据就有 100 条记录。在利用多线程查询属于部门 A 的记录时，每个线程就会从各自对应的数据中取数相应的这 100 条记录了。
对于没有什么特征的数据，尤其是随机数，可以考虑按整数的尾数取余数来分成 N 份数据。这样可以尽可能地确保每份数据中数据量的均匀分配。
4.2 举例

本文插图
基于以上数据结构，数据拆分以及建立组表：

本文插图
A2：使用循环函数，创建名为“键值名 _ 键值取 N 的余数.ctx”的组表文件，其结构同为 (#id,data) 。
A3：用循环函数将游标数据分别追加到 N 个原组表上。此处 N 为参数，假设 N=4 ，当循环第一次时，拼出的 eval 函数参数为：channel(A1).select(id%4==0).attach(A2(1).append(~.cursor())) 。意思是对游标 A1 创建管道，将管道中记录按键值 id 取 4 的余数，将余数值等于 0 的记录过滤出来。 attach 是对当前管道的附加运算，表示取和当前余数值对应的原组表，将当前管道中筛选过滤出的记录，以游标记录的方式追加到 A2(1) ，即第 1 个组表。
多线程并行创建索引：

本文插图
A1：使用 fork 执行多线程时，需要注意环境中的并行限制数是否设置合理。
多线程并行查询：

本文插图
需要注意的是，将待查找的批量键值用和拆分组表数据同样的规则拆分后，在各自对应的组表中进行查找。并且取数动作应当在多线程并行内完成，而不是将各自的游标返回后再取数。
五、数据追加
对于大数据来说，新数据的追加是不可避免的。数据追加通常要考虑原数据与追加数据的关系，较简单的情况是连续有序的数据，直接在原数据尾部追加新数据，对追加后的数据，还需要更新索引。如果新数据与原数据，整体不是连续有序，就需要在追加数据时做归并运算，并随后更新索引。尤其是当原数据变得很大时，原数据与新数据的频繁归并、每次追加后更新索引，都会带来极高的时间成本和磁盘损耗问题。
这种情况可以建立一份临时数据区来存放每次追加的新数据，当这个临时数据区达到一定规模（在数据增量较为稳定的情况下也可以按时间来决定，比如每个月初），就将临时数据区（小数据）与原数据（大数据）进行一次归并，并更新索引。查找时可以将大小两份数据在逻辑上合并为一份数据后进行查找。
无序的数据追加时，因为索引就是排序的，要重建索引也会面临以上有序数据追加时的问题，还是需要大小两份数据的办法，等积累多了再重建索引。
5.1 举例

本文插图
SPL提供了补文件的功能，可以方便地应对复杂的数据追加场景。
单个文件时，利用补文件追加数据：

本文插图
A1：add.txt 是新增数据（这里假设数据来自文本文件，实际也可能来自数据库等其他数据来源），与已有文件结构相同，均为 (#id,data) ，其中 id 有序。分页标题
A2：判断为当前系统时间是否为月初。
B2：若是月初， f.reset 函数将补文件有序归并到主文件，同时清空补文件，并更新索引。
A3：每天对补文件进行归并运算， append 的 @a 代表归并追加到补文件上，若没有补文件则自动创建，并更新索引。
多个文件时，利用补文件追加数据：

本文插图
查找时，代码不变。 open 函数，当存在补文件时，会连带补文件的数据一同查找。
六、索引冗余
同一份数据不能在遍历运算（通常为列存）和随机取数（通常为行存）这两方面都达到最优性能。如果这份数据还想用于遍历运算，可以把数据冗余多份，以空间换时间。
6.1 举例

本文插图
对需要遍历的数据，通常采用列存。 SPL 中创建列存组表，只需要将 f.create@r 的 @r 去掉，就是以列存方式创建组表。
对于列存组表，在建立索引时，还可以建立带值索引，把需要获取的数据复制进索引，基于以上的数据结构：

本文插图
对于多字段键的场景，组表建索引时，对应参数部分也有类似的写法：index(ids_data_idx;id1,id2,…,idN;data1,data2,…,dataN) 。
【|批量随机键值的查询优化】SPL的带值索引的查询与不带值索引使用一样。需要注意的是，使用带值索引，读取数据时将不再访问原数据文件，取数速度会更快。但是另一方面，因为在索引中做了冗余，索引文件也会较大。