sqlite中对于group by的处理

一、除重
在一些数据库查询中，我们希望一些记录是唯一的，比如希望查找某一项的最大值，由于table中可能有多条记录他们的值相同，都是最大值，例如一些有上限的属性，很容易出现多条record的属性值都达到上限的情况，此时我们可能只需要一条，验证它的确曾经达到过上限，此时比较好的办法就是使用group by，这个修饰天生具有消除冗余的特征。即使加上其它属性，即使其它属性不重复，此时每个group也只会显示一个，此时比较好奇的是数据库是如何处理一个group的，而对于一个group的非by属性，在最终的展示过程中将会显示成什么样的结果。
二、例子
文档的描述没有代码准确，文字的描述没有图形的描述直观，但是前者成本较低。这里还是用最原始的方式说明一下问题：
sqlite> create table tsecer(F1 int, F2 int, F3 int, F4 int);
sqlite> .tables
tsecer
sqlite> .explain
sqlite> explain select F1 , max(F2), avg(F3), sum(F4)  from tsecer where F3>0 group by 888*F4 , 999*F1;
addr  opcode         p1    p2    p3    p4             p5  comment      
----  -------------  ----  ----  ----  -------------  --  -------------
0     Trace          0     0     0                    00               
1     OpenEphemeral  1     7     0     keyinfo(2,BINARY,BINARY)  00       Open a new cursor P1 to a transient table   P2 is the number of columns in the virtual table
2     Integer        0     9     0                    00  clear abort flag
3     Integer        0     8     0                    00  indicate accumulator empty
4     Gosub          11    60    0                    00               
5     Integer        0     16    0                    00               
6     Goto           0     69    0                    00               
7     OpenRead       0     2     0     4              00  tsecer       
8     Rewind         0     25    0                    00               
9     Column         0     2     17                   00  tsecer.F3    每个列编号从0开始，所以F3编号为2
10    Le             16    24    17    collseq(BINARY)  6c               
11    Integer        888   17    0                    00               
12    Column         0     3     18                   00  tsecer.F4    
13    Multiply       18    17    19                   00               888*F4放入新record的第一个成员中
14    Integer        999   17    0                    00               
15    Column         0     0     26                   00  tsecer.F1    26寄存器放入F1值
16    Multiply       26    17    20                   00               F1×999放入新record的第二个成员中
17    Sequence       1     21    0                    00              Find the next available sequence number for cursor P1.Write the sequence number into register P2 The sequence number on the cursor is incremented after this instruction  定义处内容 i64 seqCount;         /* Sequence counter */ 表示在cursor中添加的元素的添加序列号，应该是一个内部结构，对于此次查询透明。
18    SCopy          26    22    0                    00               22放入F1
19    Column         0     1     23                   00  tsecer.F2    
20    Column         0     2     24                   00  tsecer.F3    
21    SCopy          18    25    0                    00               F4
22    MakeRecord     19    7     17                   00               Convert P2 registers beginning with P1 into a single entry suitable for use as a data record in a database table or as a key in an index，17为输出地址
23    IdxInsert      1     17    0                    00               
24    Next           0     9     0                    01               
25    Close          0     0     0                    00               
26    Sort           1     68    0                    00  GROUP BY sort
27    Column         1     0     14                   00               888*F4
28    Column         1     1     15                   00               999*F1
29    Compare        12    14    2     keyinfo(2,BINARY,BINARY)  00     Compare to vectors of registers in reg(P1)..reg(P1+P3-1) (all this one "A") and in reg(P2)..reg(P2+P3-1) ("B").  Save the result of  the comparison for use by the next OP_Jump instruct.P4 is a KeyInfo structure that defines collating sequences and sort orders for the comparison.  The permutation applies to registers only.  The KeyInfo elements are used sequentially.        12开始和14开始的两个寄存器逐个比较，所有想等才认为一个相同的group。 
30    Jump           31    35    31                   00               如果键值想等，执行累加输出，否则
31    Move           14    12    2                    00               将当前值保存在前一个值中
32    Gosub          10    49    0                    00  output one row
33    IfPos          9     68    0                    00  check abort flag
34    Gosub          11    60    0                    00  reset accumulator
//执行所有agg中指定的函数
35    Column         1     4     19                   00             F2放入19寄存器
36    CollSeq        0     0     0     collseq(BINARY)  00               
37    AggStep        0     19    2     max(1)         01               
38    Column         1     5     20                   00               F3
39    AggStep        0     20    3     avg(1)         01               
40    Column         1     6     21                   00               F4
41    AggStep        0     21    4     sum(1)         01               
42    Column         1     3     1                    00               F1放入reg1中，<1,0>存放888*F4 <1,1>存放F1×999 <1,2>存放未使用的sequence number，接下来从3到6为F1到F4
43    Integer        1     8     0                    00  indicate data in accumulator  The 32-bit integer value P1 is written into register P2.
44    Next           1     27    0                    00               Advance cursor P1 so that it points to the next key/data pair in its table or index.  If there are no more key/value pairs then fall through  to the following instruction.  But if the cursor advance was successful,jump immediately to P2.
45    Gosub          10    49    0                    00  output final row
46    Goto           0     68    0                    00               
47    Integer        1     9     0                    00  set abort flag
48    Return         10    0     0                    00      
49    IfPos          8     51    0                    00  Groupby result generator entry point
50    Return         10    0     0                    00               
51    AggFinal       2     1     0     max(1)         00               
52    AggFinal       3     1     0     avg(1)         00               
53    AggFinal       4     1     0     sum(1)         00               
54    SCopy          1     27    0                    00               Make a shallow copy of register P1 into register P2. 将寄存器1中的值拷贝到寄存器2中
55    SCopy          2     28    0                    00               
56    SCopy          3     29    0                    00               
57    SCopy          4     30    0                    00               
58    ResultRow      27    4     0                    00               输出从27开始的四个值 The registers P1 through P1+P2-1 contain a single row of results This opcode causes the sqlite3_step() call to terminate with an SQLITE_ROW return code and it sets up the sqlite3_stmt structure to provide access to the top P1 values as the result row
59    Return         10    0     0                    00  end groupby result generator
清空accumulator
60    Null           0     1     0                    00               
61    Null           0     5     0                    00               
62    Null           0     6     0                    00               
63    Null           0     7     0                    00               
64    Null           0     2     0                    00               
65    Null           0     3     0                    00               
66    Null           0     4     0                    00               
67    Return         11    0     0                    00               
68    Halt           0     0     0                    00               
69    Transaction    0     0     0                    00               
70    VerifyCookie   0     1     0                    00               
71    TableLock      0     2     0     tsecer         00               
72    Goto           0     7     0                    00               
sqlite> 
三、大致方法
在sqlite的实现中，它首先会创建一个内存中的record集合结构，这个结构用sqlite的属于terminology来说就是cursor。记得有一句谚语所说：to the man with a hammer every problem looks like a nail，每种系统都尝试用自己最擅长的工作来解决自己所有的问题，例如gcc用自己来编译自己，linux用文件系统来虚拟一切，而sqlite则用BTree来组织所有记录。sqlite创建的临时cursor同样适用bTree来管理自己所有的record。
对于上面的命令，sqlite为每个group by指定的表达式创建一个对应的新属性，然后把所有结果中需要的其他原始属性一起组合成一个新的record，然后插入新创建的临时cursor中。
之后遍历临时创建的cursor结构，之后的操作应该是比较直观的，就好象之前完成的是sort的功能，接下来的处理就是相当于uniq工具的作用了，因为record已经按照group by的公式排序，所以具有相同值编号一定是相邻的。对于具有多列的group by属性，在之前的compare中比较是一组数值比较的，所以对于group by的字段只有全部相等时，才能算作一组。
从这个实现中来看，在输出结果中不受avg影响的列应该是最后一个record中的字段，但是这个是sqlite的实现，而且没有验证。mysql会不会进行优化，例如不在每个agg循环中更新这个和agg无关的字段，而只在开始更新一次，想来也是极好的。