优化Join运算的系列方法（2）

3 半内存时的外键表

外键指针化的前提是事实表和维表都可以装入内存，但实际业务中涉及的数据量可能很大，那就不能采用这种方法了。

3.1 维表内存化

如果只是事实表很大，而维表仍然可以全部装入内存，那么仍然可以采用上面的外键指针化方法处理，只要修改一下对事实表的访问，使用游标的方式取从集文件里分批取数进行处理即可。不过因为这种指针是在游标取数时才临时建立的，所以就不象全内存时那样可以复用已经建立过的指针了。

我们仍然按照用户级别和卖家信用等级汇总订单数量，而订单表太大无法导入内存，那么用集算器实现如下：

	A
1	=file("订单表")
2	=A1.cursor@b()
3	=file("用户信息表").import@b().keys(用户编号).index()
4	=file("卖家信息表").import@b().keys(卖家编号).index()
5	=A2.switch(用户编号,A3:用户编号;卖家编号,A4:卖家编号)
6	=A5.groups(用户编号.VIP级别:用户级别,卖家编号.信用等级:卖家等级;sum(订单编号):订单数)

这个实现跟外键指针化的实现原理相同，只不过订单表的数据没有一次性导入内存,而是通过游标的方式访问。由于事实表会不断增长，所以事实表很大而维表较小会是实际业务中常见的情况。

这是个多外键的例子。多层外键的情况和单层外键类似，只是在内存化某外键表时，该表的外键表也必须内存化，从而可以事先建立内存的外键指针。临时基于游标建立的外键关联只会针对最下层的外键表。

游标也可以实现并行计算，上面的代码只要改成这样：

	A
1	=file("订单表").cursor@bm(;4)
2	=file("用户信息表").import@b().keys(用户编号).index()
3	=file("卖家信息表").import@b().keys(卖家编号).index()
4	=A1.switch(用户编号,A2:用户编号;卖家编号,A3:卖家编号)
5	=A4.groups(用户编号.VIP级别:用户级别,卖家编号.信用等级:卖家等级;sum(订单编号):订单数)

把来自集文件的订单表数据分成4段游标取出，在执行groups函数就会以并行的方式进行计算了。这里之所以可以进行分段取数，是因为数据已经导出到集文件中了，如果数据仍然在数据库中则无法做到这一点的，这也是我们为什么要把数据导出到集文件的原因之一。

如果维表太大也无法装入内存怎么办？这种情况就要使用集群或者优化过的外存HASH JOIN技术了，后面的篇章中我们会详细讲解。

 

3.2 外键序号化

外键序号化的思路是，如果维表的主键是从1开始的自然数，那么就可以用序号直接定位维表记录，而不再需要计算和比对HASH值了。这可以看做是在外存实现了外键指针化，从而进一步提升性能。按照外键序号化思路，前面订单表和用户表的关联处理可以改成这样：

	A
1	=file("用户信息表").import@b()
2	=file("订单表").cursor@b()
3	=A2.switch(用户编号,A1:#)
4	=A3.new(订单编号, 用户编号.用户名:用户名, 用户编号.VIP级别:用户级别, 下单时间)

A1，将客户表全部导入内存；

A2，将订单表使用游标导入；

A3，在A2订单表中把用户编号的值作为序号，用这个序号去用户信息表找相应的记录，建立关联；

A4，通过外键属性化的方式，将外键表字段作为用户名、用户级别属性使用。

3.3 序号化准备

但维表的主键不一定是序号值，那么就无法直接使用外键序号化进行性能优化。这时，可以把维表的主键转换成序号后再使用外键序号化。处理的步骤是这样的：

1）新建一个键值-序号对应表，保存维表的键值和自然序号的对应关系；

2）把维表的键值替换为自然序号，得到一个新的维表文件；

3）把事实表里的外键值修改为序号，修改的依据是键值-序号对应表，修改后得到一个新的事实表；

这样就得到了新的维表和事实表文件，旧的表文件也可以删除了。

 

如果维表增加了新数据，那么就按照如下步骤处理：

1）先追加键值-序号对应表；

2）再把新数据追加到新的维表，追加时依据键值-序号对应表；

3）最后追加事实表，追加时依据键值-序号对应表；

当完成了外键的序号化以后就可以使用外键序号化的方式来提高性能了。序号化这种方法适用于维表基本不变的情况，事实表数据则可以不断追加。

下面仍以订单表、用户信息表为例来说明一个序号化的具体实现：

1）新建一个用户信息表的键值-序号对应表，保存到集文件中，同时生成一个用户信息表文件；

	A
1	=db.query("select *,0 AS NEW_ID from 用户信息表 order by 用户编号")
2	=A1.run(#:NEW_ID)
3	=file("OldKey_NewID").export@b(A2,   用户编号, NEW_ID)
4	=file("用户信息表").export@b(A2, NEW_ID:用户编号, 用户名,联系手机,VIP级别)

A1从数据库的用户信息表取出所有字段，并增加一个用来保存序号的字段NEW_ID；

A2将NEW_ID赋值为从1开始的自然数；

A3是保存旧的用户编号和序号到集文件；

A4用NEW_ID字段值作为用户编号字段的值，其它字段不改变，把数据保存到用户信息表文件。

2）根据订单表，得到新的订单表；

	A
1	=file("OldKey_NewID").import@b()
2	=db.cursor("select * from 订单表")
3	=A2.switch(用户编号,A1:用户编号)
4	=A3.run( 用户编号.NEW_ID:用户编号)
5	=file("新订单表").export@ba(A4)

A1把对应关系表导入内存；

A2用游标从订单表取出数据；

A3把订单表里的用户编号字段根据对应表进行替换；

A4把替换后的用户编号字段的值做一个转换（A3得到的用户编号字段值是记录类型，所以在A4转变为字段）；

A5把游标数据导出到新订单表文件里（实际中可能要分多次导出）；

 

通过这两步，就可以完成对数据库里已有数据的序号化，并导出到用户信息表、订单表这两个集文件，同时还得到了一个键值-序号对应表文件，命名为OldKey_NewID。

 

前面提到过，序号化适用于维表数据基本不变的情况，如果维表变化了，那就需要重造这些数据后再使用序号化。不过，如果能够明确知道事实表和维表上新追加的数据（例如通过时间等条件），那么也可以用下面的办法来实现。

1）先追加用户信息表和键值-序号对应文件；

	A
1	=db.query("select *,0 AS NEW_ID from 用户信息表 where 注册时间>’2018-01-01’ order by 用户编号")
2	=file("用户信息表").cursor@b().skip()
3	=A1.run(A2+#:NEW_ID)
4	=file("OldKey_NewID").export@ab(A3,   用户编号, NEW_ID)
5	=file("用户信息表").export@ab(A3, NEW_ID:用户编号, 用户名,联系手机,VIP级别)

A1得到用户信息表要追加的新数据，这里是从数据库里取2018年以来新注册的用户数据；

A2得到用户信息表已有记录条数；

A3填写新数据里的NEW_ID值，从A2开始继续计数；

A4把用户编号和序号追加到键值-序号对应的文件；

A5追加新数据到用户信息表文件。

3）追加订单表；

	A
1	=db.query("select * from订单表 where 下单时间>=’2018-01-01’ order by 订单编号")
2	=file("OldKey_NewID").cursor@b()
3	=A1.switch(用户编号,A2:用户编号)
4	=A3.run( 用户编号.NEW_ID:用户编号)
5	=file("订单表").export@ba(A4)

A1得到订单表要追加的新数据的游标，这里是从数据库取出2018年以来的订单作为新数据；

A2是得到键值序号的对应表；

A3把新数据游标里的用户编号字段根据对应表进行替换；

A4把替换后的用户编号字段的值做一个转换；

A5使用循环方式从游标取数，追加到订单表文件，这个过程和用户信息表的追加是类似的。

上面是一个单外键做序号化的例子，对多外键的序号化处理也是一样的，只是有多个维表要处理。如果是多层外键，那么上层的就没有必要做序号化了，只要对最下层的维表做个序号化就可以了，因为上层已经全内存指针化了。

外键序号化处理本质是优化了查找外键的方法，把外键值作为序号直接去维表找记录，所以经过外键序号化的数据仍然可以使用并行计算，实现方式跟前面讲的一样，在此不再详述。

 

4 同维表和主子表

在这里我们把同维表和主子表两种情况一起来分析，因为这两种情况的提速手段是一样的，那就是有序归并。

4.1 有序归并

我们先看简单的情况，如果两个表对关联键都已经是有序的，那么就可以直接使用归并算法来处理关联。来看一个例子，

订单表

订单编号

用户编号

卖家编号

下单日期

 

订单明细表

订单编号

商品编号

数量

金额

 

卖家信息表

卖家编号

名称

……

 

用户信息表

用户编号

用户名

……

 

此时订单表是主表，订单明细表是子表，这是一个典型的一对多的情况，现在要查询订单及其明细，那么就要把两个表按照订单编号字段进行关联。先来看一下数据量不大时的例子，计算目标是汇总每个卖家的销售额：

	A
1	=file("订单表").import@b()
2	=file("订单明细表").import@b()
3	=join@m(A1:订单,订单编号;A2:明细,订单编号)
4	=A3.groups(订单.卖家编号 :卖家编号; sum(明细.金额):总销售额 )

A1将订单表全部导入内存。

A2将订单明细表全部导入内存。

A3通过有序归并算法（@m选项）对两个表按照订单编号关联。

A4对join的结果进行分组汇总。

集算器的join操作的结果与SQL不同，SQL里join的结果是两个表的字段，而集算器join的结果是把两个表的记录作为结果字段，所以做groups时的语法需要写成“字段.子字段”这样（类似“对象.属性”），例如访问卖家编号就要写成“订单.卖家编号”。

如果数据很大无法导入内存，则可以使用游标方式进行有序归并。

	A
1	=file("订单表").cursor@b()
2	=file("订单明细表"). cursor@b()
3	=joinx(A1:订单,订单编号;A2:明细,订单编号)
4	=A3.groups(订单.卖家编号:卖家编号; sum(明细.金额):总销售额 )

注意，这里进行有序归并的前提是订单表、订单明细表已经是对订单编号字段有序的。

A1将订单表通过游标导入；

A2将订单明细表通过游标导入；

A3通过有序归并算法对两个游标按照订单编号关联；

A4对joinx的结果进行分组汇总。同样地，joinx的结果的字段也是记录，所以在groups时对卖家编号的访问语法就变成了订单.卖家编号，对金额的访问语法就成了明细.金额。

 

有序归并还可以和游标外键一起使用，例如我们要计算消费总金额大于1000的用户名：

	A
1	=file("订单表").cursor@b()
2	=file("订单明细表"). cursor@b()
3	=file("用户信息表"). import@b()
4	=A1.switch@i(用户编号, A3:用户编号)
5	=joinx(A4:订单,订单编号;A2:明细,订单编号)
6	=A5.groups(订单.用户编号.用户名; sum(明细.金额):总额) .select(总额>1000)

A1将订单表通过游标导入；

A2将订单明细表通过游标导入；

A3将用户信息表导入内存；

A4使用用户编号字段和用户信息表做外键关联；

A5通过有序归并算法对两个游标按照订单编号关联；

A6 通过用户名字段（订单.用户编号.用户名）进行分组汇总，并选出总额大于1000的。

 

4.2 有序归并的数据准备

不过，如果数据事先没有按主键有序呢？那么就需要事先进行排序。同维表和主子表可以在数据准备阶段就做好排序，这是因为对于同维表或主子表的关联，用到的字段都是那一个（一组），即主键（的部分）；而对于外键表，事实表有可能要跟多个维表做关联，每次关联的字段都可能是不同的，而一个表是不可能同时对所有的外键都有序的。

因此，对于数据库中并不保证次序的原始数据，我们可以在做数据外置时同时进行排序。本节将描述如何排序以及排序后如何有序地更新数据。

先看原始数据的导出。如果要排序的同维表或主子表的数据源都是数据库，那么就用数据库排序。如果数据源不是数据库，那么可以使用集算器的sortx函数进行排序。排序后用export函数保存到一个新的文件里。如果要采用分段并行，还要注意在导出的时候加上选项@z。处理流程是这样的：

	A
1	=db.query("select * from 订单表 order by 订单编号").cursor()
2	=file("订单表").export@z(A1;订单编号)
3	=db.query("select * from 订单明细表order by 订单编号").cursor()
4	=file("订单明细").export@z(A1;订单编号)

A1，从数据库将订单表通过游标导入，并且排序；

A2，将排序后的游标数据写入集文件；

A3、A4同样将数据库的订单明细表排序后写入集文件。

 

再来看看如果这两个表又追加了新数据时该怎么处理，我们仅以订单表的追加为例：

	A
1	=file("订单表"). cursor @b()
2	=db.query("select * from 订单表 where 下单日期>=’2018-01-01’ order by 订单编号").cursor()
3	=[A1,A2].mergex(订单编号)
4	=file("新订单表").export@z(A1;订单编号)

A1，将订单表通过游标导入；

A2，从数据库中将2018年以来产生的新数据取出；

A3，两个游标按照订单编号字段进行有序归并；

A4，将归并后的游标数据写入新的文件。

后续使用时用新的文件替换旧的订单表文件，这样就完成了新增数据和历史数据的有序归并，就可以按照有序的情况进行处理了。

新增数据和历史数据的混合，是个有序归并的过程，并不需要全部重新排序，只是把数据再读写一遍，时间成本并不高。

 

4.3 并行计算

如果数据量确实特别大，频繁重写的成本太高，这时可以每隔一个相对合适的周期才重写所有数据，未到周期点时先把数据保存到一个较小文件，到了周期节点再把小文件和历史全文件做归并，具体的周期根据实际业务来设定。这样就会有两个文件：历史全文件和周期内小文件。可以使用多路游标来一起访问这两个文件。

例如，可以计划每隔一个月才重写所有数据，每天追加的数据合在一个当月的小文件中，在月中只用这个小文件和当日数据归并，到了月末才把当月文件和历史全文件全部归并，这样就能够减少全量归并的次数，减少总的处理时间。这种方式下两个文件就是历史文件和当月文件。

当然，还可以保留以前每个月的文件，作为历史数据不再改动，然后使用多路游标来访问这多套数据，这样性能可能会更好。这是以日期为例的情况，还可以根据其它的字段来进行分段方案的设计，比如按地区等。

下面用每个月保留一个文件的方法来举例说明，先实现对当日新产生的数据的处理，仍然以订单表为例：

	A
1	=file("订单表8月").import@b().cursor()
2	=db.query("select * from 订单表 where 下单日期>=’2018-08-XX’ order by 订单编号").cursor()
3	=[A1,A2].mergex(订单编号)
4	=file("新订单表8月").export@z(A1;订单编号)

A1，将8月份的订单表月文件通过游标导入；

A2，从数据库中将2018年8月某一天以来产生的新数据取出；

A3，两个游标按照订单编号字段进行有序归并；

A4，将归并后的游标数据写入新的8月份的文件。

处理后得到每个月份的订单表集文件，同理也可以得到每个月份的订单明细表的集文件。每个月份的两个集文件（订单和明细）都是根据订单时间产生的，对应的主子表记录（订单及其对应订单明细）都在同一月份的文件中，这样就可以并行地针对每个月的数据做有序归并来实现主子表连接，进一步提速。仍以统计卖家销售总额为例，下面是具体实现：

	A
1	=12.(file("订单表"/~/"月").cursor@b())
2	=12.(file("订单明细表"/~/"月").cursor@b())
3	=12.(joinx(A1(#):订单,订单编号;A2(#):明细 ,订单编号))
4	=A3.mcursor()
5	=A4.groups(订单.卖家编号 :卖家编号; sum(明细.金额):总销售额 )

A1，创建12个月份的订单表游标；

A2，创建12个月份的订单明细表游标；

A3，使用joinx对12个月份数据进行归并，得到游标；

A4，合并为多路游标；

A5，对多路游标进行分组汇总。