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

SLN

JOIN是关系数据库中常用运算，用于把多个表进行关联，关联条件一般是判断某个关联字段的值是否相等。随着关联表的增多或者关联条件越来越复杂，无论理解查询含义、实现查询语句，还是在查询的性能方面，可以说JOIN都是最具挑战的SQL运算，没有之一。
特别是JOIN的性能，一直是个老大难问题。下面我们将基于数据计算中间件（DCM）——集算器，来提供一些提升运算性能的方法。
当然，我们不是介绍如何在写SQL语句时怎么写JOIN，也就是我们假设已经对查询需求有了正确的理解并且能正确地实现SQL。这种情况下，要提升性能，就必须从最基本的提升数据IO配合算法及并行等手段做起。正因如此，如果数据仍然存储在数据库中，那也没什么好办法提速，因为数据库的IO效率很低，又几乎无法并行，即使把运算写得再精巧也无济于事。所以，要提高性能，一定要把数据搬出数据库，我们下面的讨论都是基于这个思路，而集算器正是实现这个思路的利器，甚至神器！
把数据表搬出数据库存储到集算器的集文件中很简单，只要用两行代码：

	A
1	=db.cursor("select * from 订单表")
2	=file("Order.btx").export@b(A1)

这两行代码把数据库里订单表的数据导出到集文件Order.btx。
因为数据库IO性能不佳，而且数据量也可能很大，所以这个“搬家”动作可能时间也不短，但还好是一次性的。后面我们的计算都将从集文件中取数。
1 判断 JOIN 的类型 在将数据搬出数据库后，我们需要首先判断JOIN的类型，然后才能采取有针对性的优化措施。
JOIN运算大家都很熟悉，按照SQL的语法定义划分，包括INNER JOIN(内连接)、LEFT JOIN(左连接)、RIGHT JOIN（右连接）、FULL JOIN（全连接）几个类型，这是根据在运算中对空值的处理规则进行划分的。而我们的分析和优化，则会从更贴近需求的语义角度出发，根据各个表的主键参与关联的情况进行划分，总体来说有这么三种：外键表、同维表、主子表。
外键表
当表A的某些字段与表B的主键关联，B称为A的外键表，A表中与B表主键关联的字段称为A指向B的外键。此时A表也称为事实表，B表也称为维表。

表A：Order订单表
ID	订单编号
CustomerID	客户编号
SellerID	销售编号
OrderDate	订购日期
Amount	订单金额
表B：Customer客户表
ID	客户编号
Name	客户名称
Area	所在区域

  

表C：seller销售人员表
ID	员工编号
Name	姓名
Age	年龄
……

  
这是一个典型的例子，订单表的客户编号与客户表的主键客户编号进行关联，此时A指向B是多对一的关系，即A表有可能存在多条记录指向B表的同一条记录。
这种情况，我们可以把外键字段（例子中的“CustomerID”）的值理解成指向外键表中对应记录的“指针”，而外键表中对应的记录就可以理解成一个对象，而外键表的字段就可以理解为对象的属性， “指针”的作用只是用于找到外键表中对应那条记录。例子中对表A和表B做关联，一定是想获得某些订单的客户的姓名或所在区域等详细信息，这样，如果能写成customerID.name和customerID.area就会更容易理解，这种语法在集算器中也得到了完美的支持。
同时，表A还可以有多个外键表，例如表A的销售编号（SellerID）可以指向一个销售人员信息表C，从而获得该订单销售人员的属性信息。
  
同维表
表A的主键与表B的主键关联，A和B相互称为同维表。同维表是一对一的关系，JOIN、LEFT JOIN和FULL JOIN的情况都会有，例如：员工表和经理表。
  

表A：employee员工表
ID	员工编号
Name	姓名
Salary	工资

  

表B：manager客户表
ID	编号
Allowance	补贴
……

这两个表的主键都是员工编号ID，也就是经理也是员工之一，不过因为经理比普通员工多了一些属性，所以需要另用一个经理表来保存。对于这种一对一的情况，逻辑上可以简单地看成一个表来对待。同维表JOIN时两个表都是按主键关联，相应记录是唯一对应的。

主子表
表A的主键与表B的部分主键关联，A称为主表，B称为子表。主子表是一对多的关系，只有JOIN和LEFT JOIN，不会有FULL JOIN，如：订单和订单明细。
  

表A：Order订单表
ID	订单编号
CustomerID	客户编号
OrderDate	订购日期
……

  

表B：OrderDetail订单明细表
ID	订单编号
NO	订单序号
Product	订购产品
Price	价格
……

  
表A的主键是ID，表B的主键是ID和NO，表A里的一条记录会对应表B里的多条记录。此时，可以把订单明细表里的相关记录看成是订单表的一条记录的属性，该属性的取值是一个集合，而且常常需要使用聚合运算把集合值计算成单值。例如查询每个订单的总金额，可以描述为：
         SELECT ID, SUM(OrderDetail.Price) FROM Order
显然，主子表关系是不对等的，而且从两个方向的引用都有意义。从主表引用子表的情况就是通过聚合运算得到一个单值，而从子表引用主表则和外键表类似。
  
那么，这样划分三种JOIN运算，外键表、同维表、主子表，有什么用处呢？当然是为了优化性能！对于需要优化的JOIN运算，在准确判断是哪种类型基础上，后面的优化才会更加有效。另外，有必要说明一下，这里提到的表A和表B不要求必须是一个实体表，也可能是一个子查询产生的“逻辑表”。
下面我们就开始针对这三种类型以及实际的业务情况进行分析和提速。


2 全内存时的外键表 如果所有参与运算的数据都能装入内存，那么就可以使用“外键指针化”技术来实现外键式JOIN运算的优化。
  
2.1 单个外键 以上面的订单表和客户表为例，要查询每一笔订单的客户名称和所在地区：

我们需要查询所有订单的订单编号、用户名、用户级别和下单时间， SQL是这么写的：
SELECT 订单编号,用户名,VIP级别,下单时间 FROM 订单表,用户信息表 WHERE 订单表.用户编号 = 用户信息表.用户编号
用集算器实现则是这样：

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

A1，从集文件中查询用户数据；
A2，设置用户信息表的键为用户编号；
A3，以用户编码字段建立索引；
A4，从集文件中查询订单数据；
A5，关联，在A4订单表的用户编码字段上建立指向用户信息表记录的指针；
A6，外键指针化之后，将外键表字段作为用户名、用户级别属性使用。
实际有效运算的也就是A5和A6这两格，别的都是数据准备。
  
再来看一个例子，这次需要计算各个VIP级别用户的订单的总数，SQL是这么写的：
SELECT VIP级别,count(订单编号) 订单数 FROM 订单表,用户信息表 WHERE 订单表.用户编号 = 用户信息表.用户编号 GROUP BY VIP级别
使用集算器则是这样的：

	A
1	=file("用户信息表").import@b()
2	=A1.keys(用户编号)
3	=A1.index()
4	=file("订单表").import@b()
5	=A4.switch(用户编号,A3:用户编号)
6	=A5.new(订单编号, 用户编号.用户名:用户名, 用户编号.VIP级别:用户级别, 下单时间)
7	=A5.groups(用户编号.VIP级别; count(订单编号):订单数)

这个计算跟上一个例子的处理步骤大部分都一样，只是在上一个例子的计算后接着再执行一下A7，对关联的结果进行汇总，能这么做是因为外键的指针关联在上一次计算里已经完成，这里可以对A5的结果进行复用。实际使用中这两个计算放在一个DFX文件里执行，所以整个过程只需要进行一次关联。
这也是集算器的另一大特点，可以对中间计算结果进行复用，从而提高整体查询性能。复用的次数越多，性能的优化就越明显。这一点在SQL中就做不到，两个查询要执行两次SQL语句，每次执行都要做一次关联，整体性能自然就差了。
  
此外，还可能存在多字段外键的情况，事实表的多个字段关联到一个维表，这种情况略有些复杂，在以后的篇章中再做详细介绍。
2.2 一层多个外键 下面再看一个多外键的例子，假设数据库中有订单表、用户信息表、卖家信息表三个表：

我们需要按照用户级别和卖家信用等级来汇总订单数量，SQL是这么写的：
SELECT VIP级别 用户级别, 信用等级 卖家等级,count(订单编号) 订单数
FROM 订单表,用户信息表,卖家信息表
WHERE 订单表.用户编号 = 用户信息表.用户编号 AND 订单表.卖家编号 = 卖家信息表.卖家编号
GROUP BY VIP级别, 信用等级
使用集算器则是这样：

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

A1，中查询订单数据；
A2，中查询用户数据；
A3，中查询卖家数据；
A4，一次性关联用户信息表、卖家信息表这两个维表；
A5，对关联的结果进行汇总。
2.3 多层外键 外键表还可能会有多层的情况，下面这个例子中，假设数据库中有订单明细表、商品信息表、类别信息表三个表：

我们要查询按照商品的大类名称汇总的售出商品数量，SQL是这么写的：
SELECT 大类名称, SUM (商品编号) 商品数
FROM 订单明细表,商品信息表,类别信息表
WHERE 订单明细表.商品编号 = 商品信息表.商品编号 AND 商品信息表.类别编号 = 类别信息表.类别编号
GROUP BY 大类名称
使用集算器则是这样：

	A
1	=file("订单明细表").import@b()
2	=file("商品信息表").import@b().keys(商品编号).index()
3	=file("类别信息表").import@b().keys(类别编号).index()
4	=A2.switch@i(类别编号,A3:类别编号)
5	=A1.switch@i(商品编号,A4:商品编号)
6	=A5.groups(商品编号.类别编号.大类名称:大类名称;sum(数量):商品数)

A1，查询订单明细数据；
A2，查询商品信息数据；
A3，查询类别信息数据；
A4，通过switch函数在A2建立指向类别信息记录的指针，实现关联；
A5，通过switch函数在A1建立指向商品信息记录的指针，实现关联，这样就得到了一个三层关联；
A6，对关联的结果进行汇总。
  
用外键指针化的办法解决JOIN，对事实表遍历一次就可以解析所有外键。而数据库的HASH JOIN算法每执行一次（意味着遍历一次数据）只能解析掉一个JOIN。
同时，如果全部使用内存，这个指针一旦建立后就可以复用，如果我们还要针对这个关联情况再次计算 ，就不需要再去建立关联了。而数据库SQL则不行，还要再做HASH JOIN，即便是基于SQL体系的内存数据库，在这方面也做不快。
2.4 并行计算 外键指针化之后，还可以通过并行方式进一步优化性能。对已经装入内存的事实表，我们可以对它进行分段访问，从而以并行计算的方式明显地提升计算的性能。
还是用上面多外键的情形为例，仍然是按照用户级别和卖家信用等级汇总订单数量，我们来看看如何用集算器实现并行访问事实表：

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

这段代码和前面的基本一样，只是对订单表这个事实表的访问方式有所不同。A2使用@m选项把订单表数据分为了4段，得到一个多路游标，后面的计算都是基于这个多路游标进行的。groups函数内部会自动判断，如果A2是多路游标那么就会自动进行计算。这里分为4段游标，是假定CPU的个数是4个，实际使用中可以根据CPU的数量来决定分几段。
并行在单任务时有很明显的效果，主要是因为充分利用了CPU资源，如果并发较多时没有太多空闲的CPU可用，那么意义就不大了。