SQL 提速:二值标签

【摘要】
从原理上分析 SQL 语句慢的原因,用代码示例给出提速办法。点击了解SQL 提速:二值标签

问题描述

我们把用来实现某种标记的“是否”型数据称为二值标签。在二值标签总数不太多,只有几个到几十个时,可以用数据表的布尔型字段来存储。

例如,表 T 包含 id 字段、flag1、flag2、…、flagN 和其他字段,其中 flagi 是“是否”型标签,存成布尔类型。针对二值标签的统计 SQL 大体是如下形式:

select … from T where flag2 and flag18 and flag25 and …

数据库过滤出第 2 个二值标签(简称标签 2)、标签 18 和标签 25 都为“是”,且满足其他条件的数据再做统计。

 

在实际应用中,二值标签的总数会达到几百个甚至几千个,而且还在动态增加中。数据库不支持几千个列的表,无法用一个表存储这么多二值标签,也很难动态增加字段,所以上述方案就不可行了。

首先想到的解决办法,是将几千个字段分成多个表存储,比如每个表存 100 个字段,20 个表就可以存储两千个。计算时,将需要的表用主键 id 关联起来。SQL 大体如下:

select … from T1 left join T2 on T1.id = T10.id left join T15 on T1.id=T15.id

where T1.flag2 and T10.flag913 and T15.flag1462 and …

这些表参与计算的总行数通常是很大的,需要外存。几个大表做外存连接运算的性能会很差。而且,数据库一般是行式存储,即使只有一个字段参与计算,也要把对应数据表的全部上百个字段都遍历到,非常耗时。

 

为避免大表 JOIN,也可以用一个字段、多条记录来存储二值标签。例如,表 T 包含 id(编号)、flag(标签号)和其他字段。id 和 flag 构成联合主键,每个 id 有最多几十个 flag。二值标签的总数有几千个,实际计算用到的一般都只有几个。

这样的存储结构可以更方便地应对标签的增加,上述计算 SQL 要改写:

select … from T

where (flag=2 or flag=18 or flag=25) and …

group by id

having count(flag)=3

数据库过滤出 flag 为 2 或 18 或 25 且满足其他条件的数据,按照 id 分组后,过滤出包含 3 条记录的组。一般来说,T 表按 id 分组结果集会很大,而大分组需要外存缓存,所以数据库计算的性能会比较差。而且,同一个 id 的其他字段值一般都是相同的,由于 flag 的原因出现了冗余,导致数据量增加一个数量级,也会使性能出现明显下降。

 

还可以将 id 和其他字段另存一个数据表 T1,T 表只保留 id 和 flag 字段以避免冗余,两表通过 id 关联后再计算。这样也能获得更好的通用性,SQL 要改写成:

select id,… from T t left join T1 t1 on t.id=t1.id

              where t.flag in (2,18,25) and …

              group by t.id

              having count(t.flag)=3

)

这种方案仍解决不了大分组的问题,还要对两个大表做关联,性能仍然很差。

 

提速方案

一、按位存储、计算

为了提高性能,需要预先处理原数据,将二值标签按位存储。一个小整数是 16 位,每一位都可以存储一个二值标签,1 代表标签值为“是”,0 代表值为“否”。也就是说一个小整数可以存储 16 个二值标签,100 个就可以存储 1600 个二值标签。我们可以采用列式存储几百个小整型字段,包含的字段为 id,f1,f2,…,fn,…。其中,小整型字段 fi 包含 16 个二值标签的值,对应标签号是 (i-1)*16+1 到 i*16。

数据预处理完成后,就可以用按位计算来实现二值标签分析。例如:计算标签 2、18 和 25 都为“是”的情况,标签 2 在 f1 中对应第 2 位,需要将 f1 和小整数 2 做“按位与”,如果结果也是 2 就满足条件。这是因为小整数 2 写成二进制数是 10,只要 f1 的第 2 位是 1,按位与的结果就仍然是 2。

标签 18 和 25 大于 16 小于 32,所以都在第二个小整型字段 f2 中,标签 18 对应 f2 的第 2 位,标签 25 对应第 9 位。我们要将 f2 和小整数 258(二进制 100000010)做“按位与”,如果结果也是 258 就满足条件。最后,将两次按位与的结果做逻辑与计算,结果为真就表示满足二值标签条件。

这样做,每个 id 只有一行数据,不会出现冗余,也不会出现大分组,只要对数据遍历一遍即可,可以有效提高性能。按位存储的性能优势还体现在下面两个方面:

1、由于参加计算的二值标签很少,所以只需要读取几百个列中的几个,可以充分发挥列存的优势,大幅度降低外存数据的读取量。

2、标签总数有几千个,但是每个 id 对应的标签只有几个到几十个。所以这几百个小整型字段总体上是比较稀疏的,可以做到较高的列存压缩比,在进一步降低外存数据读取量的同时,CPU 解压时间的增加值可以忽略不计。

 

二、数据更新

在二值标签的场景中,数据的更新一般是标签值的改变。列存压缩的存储方式可以提高性能,但是压缩之后的数据无法直接修改。更新时只能重新生成数据,虽然耗时比较长,但可以保证标签计算的高性能。

如果更新的数据量小且不频繁,可以将改动的数据写到单独的数据区(补区)。补区数据和正常数据都按照主键(id)有序,在读取数据时归并计算。虽然补区对性能有影响,但是可以解决经常生成全量数据的耗时问题。

经过多次修改后,补区会越来越大,对性能的影响也会更大,我们要定期将补区数据混入正常存储区,重写部分数据(从补区最小的主键 id 开始,之前的数据不用改变),同时清理补区。

代码示例

一、数据预处理,转换为按位存储。

假设原数据保存在 T-original.ctx 中,包括 id(编号)、flag(标签号)和其他字段。id 和 flag 构成联合主键。实际应用中,原数据可能要从数据库中取得,需要将代码修改为连接数据库取数。


A

B

1

="#id,"/to(500).("f"/~).concat@c()

="id,"/to(500).("f"/~).concat@c()

2

=to(16).(int(bits(pad@r("1","0",~))))

=A2.m(16,1:15)

3

=file("T-original.ctx").open()

=A3.cursor().sortx(id)

4

=file("T.ctx").create@y(${A1})

=create(${B1})

5

for B3;id

=B4.reset()

6


=B5.record(A5.id|to(500).(0))

7


=A5.new(int(ceil(~.flag/16)):position,B2(~.flag%16+1):value)

8


=B7.group(position;int(or(~.(value))):value)

9


=B8.(B4(1).field(~.position+1,~.value))

10


=A4.append(B4.cursor())

11

>A3.close(),A4.close()


A1、B1:根据小整数字段的个数,动态生成新组表的结构和中间结果序表的结构:

#id,f1,f2,… ,f500

id,f1,f2,…,f500

小整数字段是 500 个,最多可以存储 8000 个标签。

这里只列出了 id 和小整数字段,需要其他字段的时候要加上字段名,后边的计算也同样处理,不再赘述。

 

A2、B2:生成“位存储转换表”,如果用 env() 函数放到全局变量,这里就可以省去计算。“位存储转换表”对性能优化的主要作用将在后面讲述。

A3、B3:打开原组表,对 id 做外存排序。

A4、B4:建立新组表和保存中间计算过程的序表。

A5:对 B3 游标做循环,每次从游标读取数据至 id 有变化。也就是说每次读取一个 id 的所有数据。第一次循环如下:

..

B5:清空 B4 的序表,准备用来保存当前 id 的按位存储结果。

B6:B4 中填入当前 id 和 f1 到 f500 的初始值 0,计算结果如下:

..

B7:根据 A5 中 flag 与 16 的商和余数,计算是第几个小整数的哪一位,再用余数 +1 查“位存储转换表”B2,得到小整数的值。例如:flag 的值 48,对应第 3 个小整数的第 16 位,position 是 3,余数是 0,value 是 32768(二进制 1000 0000 0000 0000)。

当前循环是在遍历原数据的游标,数据量很大。如果在循环中计算位存储的转换,计算的次数也会非常多。我们提前算好了“位存储转换表”,这里直接查表就可以了,对性能的提升会非常明显。

计算结果为:

..

B8:B7 的结果中合并相同的 position。例如标签 122 和 125 都在第八个小整数中,那么两个 value 就要做“按位或“,合并成一个。结果如下图:

..

B9:依据 B8,将序表 B4 中 position 对应的小整数值设置为 value。例如 position 为 3,就要将 f3 的值设置为 32768。执行后 B4 如下:

..

B10:B4 转换为游标,追加到 T.ctx 的最后。

 

A11:循环结束后关闭两个组表。

 

二、数据按位存储在组表 T.ctx 中,计算标签 2、18 和 25 都为“是”的数据。

完成了数据预处理后,对于这个需求,只要写很简单的代码就可以实现:

=file("T.ctx").open().cursor(id,…;and(f1,2)==2&&and(f2,258)==258&&…)

 

但是,实际应用中前端的传入参数一般都是 "2,18,25" 这样的标签号列表,所以还要写一些代码来转换成“按位于”的过滤条件。完整的示例如下:


A

B

1

="2,18,25"

=A1.split(",").(int(~))

2

=to(16).(int(bits(pad@r("1","0",~))))

=A2.m(16,1:15)

3

=B1.new(int(ceil(~/16)):position,B2(~%16+1):value)

4

=A3.group(position;or(~.(value)):value)


5

=A4.("and(f"/position/","/value/")=="/value)

=A5.concat("&&")/"&&…"

6

=file("T.ctx").open()

=A6.cursor(id,…;${B5})

A1:多个标签号,实际应用中应为传入参数。

B1:标签号拆分为序列,并转换为整形。计算结果为:

..

A2:生成第 1、2、…、16 位为 1,其他位为 0 的 16 个小整数,结果如下:

..

B2:将 A2 的成员调整位置如下:

..

B2 的结果在标签计算、数据转换的代码中会反复用到,我们这里称之为“位存储转换表”。如果在系统初始化时预先算好,用 env() 函数放到全局变量中,这里就能直接使用,可以进一步提高性能。

 

B3:计算 B1 中的标签号,对应第几个小整数(position)以及在这个小整数中对应的值(value)。例如标签号 18 除以 16,商是 1 且余数不为零,那么标签 18 对应第 2 个小整数(position 为 2);又因为余数是 2,所以在“位存储转换表”B2 中查到第 3 个成员(余数 +1)就是标签 18 对应的小整数的值 2。B3 的计算结果为:

..

B4:B3 的结果中合并相同的 position。例如标签 18 和 25 都在第二个小整数中(position 为 2),18 的 value 是 2(二进制 10)、25 的 value 是 256(二进制 1 0000 0000),要对 2 和 25 做“按位或”运算,得到第二个小整数的最终值是 258(二进制 1 0000 0010)。结果如下图:

..

A5、B5:用 B4 的结果生成过滤条件序列,再用 && 连接成字符串。B5 中的“…”处可以写其他的过滤条件。结果为:

and(f1,2)==2&&and(f2,258)==258&&…

 

A6、B6:打开组表,建立带过滤条件的游标。后面继续写代码在游标的基础上完成统计。

统计过程中要对组表做遍历,读入的数据量是比较大的。我们之所以一直强调用小整数存储,是因为 SPL 是 Java 开发的,Java 产生对象很慢,SPL 将所有 16 位整数(0-65535)都事先产生了。如果发现读出来的整数在这个范围内,则不会新产生对象了,能减少很多运算量,还能减少内存的占用。

 

三、数据更新

如果修改数据量较少,而且不频繁,可以做组表 T.ctx 的更新,否则要重新计算生成组表。在更新之前,变动的数据也要转换成按位存储。假设转换后保存在 update.btx 中,结构和 T.ctx 相同。


A

B

1

=file("update.btx").import@b()


2

=file("T.ctx").open()

=A2.update(A1)

A1:读入有变动的数据,变动的数据量不大,所以可以全部读入内存。

A2:打开组表。

B2:更新组表,数据写入补区。

 

定期清理补区的代码:


A

B

1

=file("T.ctx").open()


2

if (day(now()))==1

=A1.reset()

A1:打开组表。

A2:判断是否是每个月第一天。是则执行 B2。本例中每月清理一次,如果是其它时间周期可以用相应的判断方法。

B2:快速重置组表,将补区混入列区。