MySQL数列求和

问题

2016年年终时，呵呵保险公司要对其销售人员的业绩做汇总和评估，以便为员工发放年终奖。而每个销售人员分属不同小组，每个小组由各自组长管理。每个小组分属不同部门，每个部门有部门经理。部门经理向总监汇报工作，总监又要向总裁、副总裁等汇报工作。所以，在统计每个销售人员时，公司希望同时对组长、经理、总监等业绩做统计。除销售人员外，其它职位的业绩等于其直属下的业绩之和，再加上自身的业绩。

比如，下表展示了一份简单的年度业绩表，每条记录描述了某位员工的年度业绩，name是员工的姓名，position是其所属职位，office代表其所属单位，performance即业绩数额。比如Tom属于保险部门的财产险推广小组，Jerry属于保险部门的事故险服务小组。

name	position	office	performance
Tom	salesman	insurance_belongings_promotion	$600
Jerry	salesman	insurance_accident_service	$300
Bob	leader	insurance_belongings	$1200
Alice	leader	insurance_accident	$800
Susan	manager	insurance	$2000

由上表的销售业绩，公司希望得到对其统计汇总后的结果，正确的结果如下表

name	performance
Tom	$600 (= Tom)
Jerry	$300 (= Jerry)
Bob	$1800 (= Tom + Bob)
Alice	$1100 (= Jerry + Alice)
Susan	$4900 (= Bob + Alice + Susan)

由于呵呵公司一直倡导人人平等的理念，所以在年终奖分配上，虽然奖金数额是由按照员工业绩的多少来决定，但公司不希望这件事情被大家所知。因此，公司的另一个需求是，尽可能使用少的资源和工具，来对业绩做统计，以来减少大家对此事的关注度。在和呵呵公司的技术人员沟通后，决定仅使用SQL语言。也就是说，上述所有逻辑的实现，不能借助例如Python、Java等代码，只能够使用数据库（MySQL 5.7）支持的SQL语言。

解决方案

如果公司仅仅是统计每个单位的自身业绩和，那么只要 GROUP BY office就可以了。然而这个问题，更多的是按照office的规则，统计自身及所有下级单位的业绩之和。

首先，通过观察样例，可以发现position字段是没有用的，可以直接剔除掉。那么会转化成下表

name	office	performance
Tom	insurance_belongings_promotion	$600
Jerry	insurance_accident_service	$300
Bob	insurance_belongings	$1200
Alice	insurance_accident	$800
Susan	insurance	$2000

然后，由于office的字段规则不直观，所以再对office列进行改写和抽象。首先考虑一个更为简单的模型，如下表

name	office	performance
Tom	1	$600
Bob	2	$1200
Susan	3	$2000

假设现在的需求依旧是统计不同office的业绩。而每个office的业绩，即为自身的业绩加上所有比自己数值小的office的业绩。我们可以证明，简化后的模型，与原问题没有本质区别，只不过对office的规则逻辑进行了简化，使用int型的大小来表明所属关系。简化模型的好处是，可以省掉不必要的精力，使我们更关注问题最需要解决的部分。

通过对模型的简化，我们可以发现，这个问题被转化为一个数列求和的问题。其中，office代表了某条记录在数列A中的位置，我们想要得到数列任意位置的前序和SUM。例如

• 数列

  • A[1] = {Tom, 600}
  • A[2] = {Bob, 1200}
  • A[3] = {Susan, 2000}

• 前序和

  • SUM[1] = {600}

  • SUM[2] = {1800}

  • SUM[3] = {4400}

除去无关的文本属性name，我们再次对模型进行抽象，假设有下表A，代表数列A，包含key和value

key	value
1	4
2	1
3	6

我们希望得到下表SUM，代表前序和SUM，包含key和sum

key	sum
1	4
2	5
3	11

一个很容易想到的方法是通过分组，将每个(key, value)划分到其参与求和的组中，如(1, 4)仅会分配到第1组，(2, 1)会分配到第1和第2组。但是，通过GROUP BY操作，仅仅使用一张A表，是没有办法完成上述分组。

那么，能不能通过自身JOIN的方法，来完成上述的分组呢，答案是肯定的。通过A表与自身的JOIN，得到下表

a0_key	a1_key	a1_value
1	1	4
2	1	4
2	2	1
3	1	4
3	2	1
3	3	6

SQL语句呼之欲出，如下

SELECT a0.key as a0_key, a1.key as a1_key, a1.value as a1_value
FROM a as a0, (SELECT * FROM a) as a1
WHERE a0.key >= a1.key 

而后，只要按a0_key分组就可以得出前序和

SELECT a0_key as key, SUM(a1_value) as sum
FROM a0_a1

到此，MySQL求前序和的问题被完美解决。

后记

这种解决方案，由于用到了join操作，所以在性能和空间消耗上，或许不是特别理想。通过分析发现，若原表有N条记录，那么运行中需要占用的空间复杂度为O(N²)，那么，假设原表有10条记录，在join时

a0	a1	a0_a1
10	10	O(10 x 10 = 100)

同样的，假设原表有100MB记录，那么在join时

a0	a1	a0_a1
100MB	100MB	O(100 x 100 = 10000MB)

不过，这里存在一个优化方法。我们可以设定数据的度量单位为GB，这样，在join时，就会占用更小的内存空间，如下

a0	a1	a0_a1
100MB ≈ 0.1GB	100MB ≈ 0.1GB	O(0.1 x 0.1 = 0.01GB ≈ 10MB)

所以，通过单位的转化，可以极大的缩小中间计算的空间资源使用，这也符合呵呵公司的最初需求。