批量随机键值的查询优化
一、 问题描述
键值查询是很常见的查询场景，在数据表上建有索引后，即使表中数据记录数巨大（几亿甚至几十亿行），用键值查询出单条记录也会很快，因为建立索引后的复杂度只有 O(log2N)， 10 亿行数据大概只要比较 30 几次（10 亿约等于 2^30），在现代计算机上是个毫秒级别的事务。
不过，如果需要查询的键值很多，比如多达几千甚至几万的时候，如果每次都独立查找，那读取和比较也会累积到几万甚至几十万次，时间延迟由此也会涨到几十秒甚至几十分钟的级别，简单地使用数据库索引对于用户体验必然是难以容忍的了。
本文将讨论大批量键值查询的性能优化方法，示例代码将用集算器 SPL 完成。SPL 代码简洁易懂，且提供了丰富的算法支持，非常适合实现这种高性能计算。
二、 单一整数键值
我们先考虑最简单的单一整数键值情况，即用作键的字段只有一个，且为整数。
2.1 存储
与大多数分析场景不同，键值查找更适合使用行式存储而非列式存储。因为行存是按记录，一条条连续存储的。而列存是按列存储的，对整条记录来说并不连续，读取单条记录时，需要从更多的数据块中读取数据，访问量反而更多。
对于超大规模数据下的随机批量键值查找，不适合对数据进行压缩。因为命中的结果分布有可能很分散，大概率出现解压一个数据块仅能获取一条记录的情况，浪费很多解压缩时间，使得查询效率变低。
2.2 索引
通常我们会针对查找键建立索引，这样指定键值可以迅速定位，而不必遍历数据。我们知道，索引的本质也是排序，利用键值有序可以快速用二分法找到指定记录。那么，如果数据本身对键值就有序，是不是可以不建索引了？
键值有序的数据本身往往过大，不能放在内存中，即使利用二分法查找时，也多次读取外存用以对比。建立索引后，可以预加载索引到内存，在内存中对索引查找，相比多次读取外存效率高很多。所以，即使数据有序，再建立索引对于高速查找仍然有意义。
反过来，建立了索引后，还要求数据对键值有序吗？
对于键值无序并建有索引时，读取数据时需要再按物理位置排序, 因为外存数据是按块存储的, 在大批量查找时，同一块有可能涉及多条找到的记录，而如果按键值次序去读取时，物理次序如果键值次序不同，就可能发生同一块被读多次的情况，性能损失严重，所以一定要在读取前将欲读数据按物理位置排序。而取出的数据还要再按原顺序排序，来回就多两个排序步骤。读取的数据量大的时候会有些影响效率，若数据有序存放则可以省去这两次排序的开销。如果每次读取的数据量不大时，额外排序损失的性能也很少，可以不必按键值有序。
2.3 索引缓存
当数据量很大时，索引本身也会很大，无法全部放入内存，这样每一次的查找都需要从硬盘上读取索引。如果对索引再建立外层索引（可能有多级），再在进行批量查找之前，尽可能多地预先加载多级索引缓存，减少重复读取索引的次数，就可以提升查询效率。
2.4 查找
查找时，将待查找的键值集有序排序，当查完一个键值后，由于键值是有序（升序）的，下一个键值肯定不小于上一个键值，这样就不会重复读取比上一个索引区间更小的索引块，少走回头路。
2.5 举例
字段名称 |
类型 |
是否主键 |
说明 |
id |
long |
是 |
从 1 开始自增 |
data1 |
string |
需要获取的数据 1 |
|
data2 |
int |
需要获取的数据 2 |
使用 SPL 创建一个满足以上数据结构的行存组表：
A |
B |
|
1 |
=file("single.ctx") |
|
2 |
=A1.create@r(#id,data1,data2) |
|
3 |
for 600 |
=to((A3-1)*1000000+1,A3*1000000).new(~:id,rands("qwertyuiopasdfghjklzxcvbnm",rand(20)+180):data1,rand(60000)+1:data2) |
4 |
=A2.append(B3.cursor()) |
|
5 |
>A2.close() |
用键值 id，建立索引：
A |
|
1 |
=file("single.ctx") |
2 |
=A1.open() |
3 |
=A2.index(id_idx;id;) |
利用索引进行批量键值查找：
A |
|
1 |
=10000.(rand(600000000)+1) |
2 |
=file("single.ctx").open() |
3 |
=A2.index@3(id_idx) |
4 |
=A2.icursor(A1.contain(id),id_idx).fetch() |
A1：这里待查找键值没有排序，因为 A4 的 T.icursor 中的 A.contain 会自动对 A 进行排序。
A3：其中 @3 的意思是将 id 键的多级索引的更多级缓存预先加载进内存。经过 index@3 预处理，第一遍查询时间就能达到索引被缓存后才能达到的极限值。另外，还有 index@2，相比 @3 缓存的索引层级更少，占用内存也更小。
三、 复杂键值
3.1 非整数键值
非整数键值，比如车牌号，通常是由字符与数字组合成的字符串。因为字符串比较要比整数的比较复杂得多，比较速度也更慢。所以可以把这种有规律或者可枚举的字符串转为简单的整数类型，提升性能。
3.2 多字段键值
多字段键值，可以直接利用多个字段键进行查找，但集合的存储和比较都要慢一些。为了获取高性能，更常用的办法是把多字段键拼成单字段键。对于有规律或者可枚举的串，可以将串数字化后，与其他数字化后的键值合并为一个新的整数键值。
3.3 举例
字段名称 |
类型 |
是否主键 |
说明 |
pnum |
string |
车牌号 |
|
pdate |
date |
日期 |
|
data |
string |
需要获取的数据 |
其中 pnum 和 pdate 两个字段作为联合主键确定一条记录。
3.3.1 多字段键直接查找
使用 SPL，按以上数据结构，创建组表（和单键值类似，多键值也需要确保键值有序，可以使用cs.sortx()函数排序，具体方法详见函数参考。）：
A |
B |
|
1 |
=file("multi.ctx") |
|
2 |
=A1.create@r(#pnum,#pdate,data) |
|
3 |
for 600 |
=to(1000000). new(rands("QWERTYUIOPASDFGHJKLZXCVBNM",1)+rands("1234567890",6):pnum,date("2007-01-01")+rand(3000):pdate,rands("qwertyuiopasdfghjklzxcvbnm",rand(20)+180):data) |
4 |
=A2.append(B3.cursor()) |
|
5 |
>A2.close() |
多字段键组表建立索引时需要包含多个维。例如，以上数据结构中的 pnum 和 pdate 两个维：
A |
|
1 |
=file("multi.ctx") |
2 |
=A1.open() |
3 |
=A2.index(p_idx;pnum,pdate) |
多字段键组表查询时可以使用 n 元组。例如，以上数据结构中的 [pnum,pdate]：
A |
|
1 |
=file("multi.ctx") |
2 |
=A1.open() |
3 |
=[["R263547",2010-06-09],["A762573",2008-03-22]] |
4 |
=A2.icursor(;A3.contain([pnum,pdate]),p_idx).fetch() |
3.3.2 数字化合并键值
用以上的数据结构做个例子，来说明如何进行数字化合并键值。
pnum是个串，一共 7 位，第一位是一个随机大写英文字母，后六位都是数字，可以将字母用 ACS 码值表示，与后六位数字拼接后转为整数。pdate 是一个日期类型字段，可以将 2007-01-01 定为起始日期，pdate 与起始日期间隔的天数可以作为该字段的数字化后的值。
pnum中大写英文字母的 ACS 码是两位数，与后面的 6 位数加起来是 8 位数，而日期 pdate 的跨度范围为 10 年，换算成天是个 4 位数，将数字化后的 pnum*10000+pdate，就得到了一个新的 12 位的数字化字段，pid。
A |
|
1 |
=file("multi.ctx").open().cursor() |
2 |
=A1.run(pnum=int(asc(pnum)/right(pnum,6)),pdate=interval@d(date("2007-01-01"),pdate)) |
3 |
=A1.new(pnum*10000+pdate:pid,data) |
4 |
=A3.sortx(pid) |
5 |
=file("conbi.ctx").create@r(#pid,data) |
6 |
=A5.append(A4) |
7 |
>A5.close() |
这样就得到了一个单字段键的组表“conbi.ctx”，其数据结构如下：
字段名称 |
类型 |
是否主键 |
说明 |
pid |
long |
是 |
包含 pnum 和 pdate 信息的唯一主键 |
data |
string |
需要获取的数据 |
然后按照 "单一整数键值" 中的做法就可以处理了。
四、 并行技术
4.1 数据拆分
多线程并行，是把数据分成 N 份，用 N 个线程查询。但如果只是随意地将数据分成 N 份，很可能无法真正地提高性能。因为将要查询的键值集是未知的，所以理论上也无法确保希望查找的数据能够均匀分布在每一份中。比较好的处理方式是先观察键值集的特征，从而尽可能地进行数据的均匀拆分。
如果键值数据有比较明显的业务特征，我们可以考虑按照实际业务场景使用日期、部门之类的字段来对数据进行拆分。如：将属于部门 A 的 1000 条记录均分在 10 份数据中，每份数据就有 100 条记录。在利用多线程查询属于部门 A 的记录时，每个线程就会从各自对应的数据中取数相应的这 100 条记录了。
对于没有什么特征的数据，尤其是随机数，可以考虑按整数的尾数取余数来分成 N 份数据。这样可以尽可能地确保每份数据中数据量的均匀分配。
4.2 举例
字段名称 |
类型 |
是否主键 |
说明 |
id |
long |
是 |
从 1 开始自增 |
data |
string |
需要获取的数据 |
基于以上数据结构，数据拆分以及建立组表：
A |
|
1 |
=file("single.ctx").open().cursor() |
2 |
=N.(file("id_"+string(~-1)+".ctx").create@r(#id,data)) |
3 |
=N.(eval("channel(A1).select(id%N=="+string(~-1)+").attach(A2("+string(~)+").append(~.cursor()))")) |
4 |
for A1,500000 |
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 个组表。
多线程并行创建索引：
A |
B |
|
1 |
fork directory@p("id*.ctx") |
=file(A1).open().index(id_idx;id;) |
A1：使用 fork 执行多线程时，需要注意环境中的并行限制数是否设置合理。
多线程并行查询：
A |
B |
|
1 |
=10000.(rand(600000000)+1) |
|
2 |
=A1.group(~%N) |
|
3 |
fork N.(~-1),A2 |
=A3(2) |
4 |
=file("id_"/A3(1)/".ctx").open().icursor(;B3.contain(id),id_idx) |
|
5 |
return B4.fetch() |
|
6 |
=A3.conj() |
|
7 |
=A6.fetch() |
需要注意的是，将待查找的批量键值用和拆分组表数据同样的规则拆分后，在各自对应的组表中进行查找。并且取数动作应当在多线程并行内完成，而不是将各自的游标返回后再取数。
五、 数据追加
对于大数据来说，新数据的追加是不可避免的。数据追加通常要考虑原数据与追加数据的关系，较简单的情况是连续有序的数据，直接在原数据尾部追加新数据，对追加后的数据，还需要更新索引。如果新数据与原数据，整体不是连续有序，就需要在追加数据时做归并运算，并随后更新索引。尤其是当原数据变得很大时，原数据与新数据的频繁归并、每次追加后更新索引，都会带来极高的时间成本和磁盘损耗问题。
这种情况可以建立一份临时数据区来存放每次追加的新数据，当这个临时数据区达到一定规模（在数据增量较为稳定的情况下也可以按时间来决定，比如每个月初），就将临时数据区（小数据）与原数据（大数据）进行一次归并，并更新索引。查找时可以将大小两份数据在逻辑上合并为一份数据后进行查找。
无序的数据追加时，因为索引就是排序的，要重建索引也会面临以上有序数据追加时的问题，还是需要大小两份数据的办法，等积累多了再重建索引。
5.1 举例
字段名称 |
类型 |
是否主键 |
说明 |
id |
long |
是 |
从 1 开始自增 |
data |
string |
需要获取的数据 |
SPL提供了补文件的功能，可以方便地应对复杂的数据追加场景。
单个文件时，利用补文件追加数据：
A |
B |
|
1 |
=file("add.txt").cursor@t() |
|
2 |
if day(now())==1 |
=file("single.ctx").reset() |
3 |
=file("single.ctx").open().append@a(A1) |
|
A1：add.txt 是新增数据（这里假设数据来自文本文件，实际也可能来自数据库等其他数据来源），与已有文件结构相同，均为 (#id,data)，其中 id 有序。
A2：判断为当前系统时间是否为月初。
B2：若是月初，f.reset 函数将补文件有序归并到主文件，同时清空补文件，并更新索引。
A3：每天对补文件进行归并运算，append 的 @a 代表归并追加到补文件上，若没有补文件则自动创建，并更新索引。
多个文件时，利用补文件追加数据：
A |
B |
|
1 |
=file("add.txt").cursor@t() |
=directory@p("id*.ctx").(file(~)) |
2 |
if day(now())==1 |
=B1.(~.reset()) |
3 |
=N.(eval("channel(A1).select(id%N=="+string(~-1)+").attach(B1("+string(~)+").open().append([~.cursor()]))")) |
|
4 |
for A1,500000 |
|
查找时，代码不变。open 函数，当存在补文件时，会连带补文件的数据一同查找。
六、 索引冗余
同一份数据不能在遍历运算（通常为列存）和随机取数（通常为行存）这两方面都达到最优性能。如果这份数据还想用于遍历运算，可以把数据冗余多份，以空间换时间。
6.1 举例
字段名称 |
类型 |
是否主键 |
说明 |
id |
long |
是 |
从 1 开始自增 |
data1 |
string |
需要获取的数据 1 |
|
… |
… |
… |
|
num1 |
int |
需要聚合的字段 |
|
data2 |
int |
需要获取的数据 2 |
|
odate |
date |
日期字段 |
|
… |
… |
… |
对需要遍历的数据，通常采用列存。SPL 中创建列存组表，只需要将 f.create@r 的 @r 去掉，就是以列存方式创建组表。
对于列存组表，在建立索引时，还可以建立带值索引，把需要获取的数据复制进索引，基于以上的数据结构：
A |
|
1 |
=file("multi.ctx") |
2 |
=A1.open() |
3 |
=A2.index(id_data_idx;id;data1,data2) |
对于多字段键的场景，组表建索引时，对应参数部分也有类似的写法：index(ids_data_idx;id1,id2,…,idN;data1,data2,…,dataN)。
SPL的带值索引的查询与不带值索引使用一样。需要注意的是，使用带值索引，读取数据时将不再访问原数据文件，取数速度会更快。但是另一方面，因为在索引中做了冗余，索引文件也会较大。
