问题
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(N2)，那么，假设原表有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) |
所以，通过单位的转化，可以极大的缩小中间计算的空间资源使用，这也符合呵呵公司的最初需求。
