任务
实现支持INSERT INTO DB VALUES(...)和SELECT a, b, c FROM x, y WHERE a=b AND b<100 AND c='a'的SQL引擎。
系统架构
程序的架构如下：
存储模型
行数据
所有记录中的integer类型及varchar类型字符串的hash储存在行(类型为Record，即int*的别名)中，每个表用一个vector<Row>记录它的所有行。使用int*而不是单独的类表示行的原因是节省内存以及减少复杂性。
字符串
注意到varchar的大小通常很大，故不把字符串与integer行数据存储在一起，而是用单独的数据结构保存。程序中使用了一个内存映射器(见下文)存储字符串。
索引
使用内存映射器存储。
内存映射器
内存映射器MemoryMap负责分配内存以及把文件抽象为虚拟内存。MemoryMap有一个容量值，代表当前加载的所有数据的大小之和。因为它使用malloc分配内存，内存的精确计算比较复杂，所以实现中假设malloc再分配所需内存外的额外开销是16字节。
当需要分配更多内存或者试图获取的页未被加载时(即产生了page
fault)，内存映射器使用LRU的缓存策略，把最近使用时刻最久的节点卸载，反复执行卸载操作直到有足够的内存加载新数据。卸载时会确定该数据是否为脏页，如果为是则保存到文件中。
索引结构
程序中实现了Size-balanced tree和B+ tree两种索引结构。当索引可以完整放在内存中时使用前者，否则就使用B+ tree。
Size-balanced tree
根据子树大小实现平衡的binary search tree，属于一类weight-balanced
tree，网上盛传由陈启峰发明，但我曾发现更早时可能即有出处，但陈启峰当初的Pascal程序影响深远，尤其是他的maintain函数写法。选用这个树结构的原因是它不会引入额外的satellite
data (比如red-black tree的颜色、AVL
tree的平衡信息等)，节省内存占用，对于节点较小时4字节的差异可能对性能有不小的影响。
B+ tree
MemoryMap是管理虚拟内存的类，调用者可以向它申请分配一段内存或者要求访问指定虚拟内存地址处的页。MemoryMap使用LRU缓存调用者访问的页，当请求的页过多时会把脏页写入文件并从内存中卸载该页。MemoryMap中的_head双链表管理内存中加载的页，新访问的页会被插入到链表头。需要卸载页时就从链表末尾取出页。
Cache策略
实现了Least recently
used缓存算法，它被内存映射器使用。MemoryMap中的_head为双向循环链表，链表中的元素按照最近使用时刻从小到大顺序从前到后排列。当内存映射器加载新数据时，把对应的节点移动到链表头部。
写策略使用write-back，即当该cache line即将被替换时写入支撑文件。
考虑过使用adapative replacement cache、multi-queue等高级的缓存策略，但考虑到单次操作的开销可能比较大，没有采用。
查询执行策略
由执行器处理查询。
单表查询
单表查询时，执行器选取该表限制最紧的列(即满足该列条件的记录数最少)，使用Size-balanced tree或B+ tree的range query操作从索引中取出所有满足条件的记录，然后滤去在其他列上不满足条件的记录。
多表JOIN
对于select操作涉及的每个表，考察只考虑关于这个表，有多少条记录满足查询要求，记这个值为
之后每次迭代选取一个表加入到生成树中，每一轮迭代选取的表
对于
中的每条记录，从 的索引中查找等值的记录，从 与 的笛卡尔积中选择这些满足条件的记录作为新的 和 两个有序表做合并操作 对于
条件，把 的所有记录，以 为关键字组织为散列表。对于 的每条记录，在散列表里查找键值为 的记录。 这里使用的自己写的散列表，用了一个小技巧使散列表的清空操作时间复杂度为 。
遇到的问题
gcc 4.6.1处理模板类构造函数时的bug
类模板A的构造函数里如果引用了之前定义的某个全局类实例的方法，A的多个实例只会调用该方法一次。本地测试发现gcc 4.7.3不存在该问题。
Runtime Error
遇到了一些数组下标越界的segfault，比如memcpy越界。
内存用溢后的segfault往往之后才会显现出来，比如在之后的某次free(可能是在clear某个vector时)segfault，
使用valgrind结合gdb，把这些问题都找出来了。
另外因为内存占用难以估算，我把很多数据结构都从可能使用malloc的STL容器换成自制的使用静态存储空间的类。
其他
网站调用外部命令
tar xf filename解压文件，当文件名为-时tar会读取stdin而产生Invalid Submission。服务器使用
make -C client编译选手代码，容易执行不可预料命令评测系统是将选手代码和评测代码链接在一起的，评测系统
new的字符串等对象会影响到堆中对象存储，导致program break增大， 会影响到resident set size占用。以后开课时内存限制我觉得把load等方法的参数改成const char *[]比较好，并声明它使用的是静态存储空间.bss或.data段，从而不会在运行时产生不可预知的内存占用，使选手对内存占用的估计更加准确。不知道服务器的内存有多少，但是选手可以通过把文件储存在
/dev/shm/下，这个目录在很多Linux发行版里默认挂载为tmpfs文件系统，并且权限为1777， 读写它有近似于访问内存的性能。选手代码如果把临时文件存储到里面会有巨大的性能提升，甚至可以完全胜过算法上带来的提升。新开的服务器
http://166.111.71.204:18080/course/index.jsp，从提交结果上来看，感觉应该没有安装g++-multilib，所以不支持-m32命令行选项，无法产生32位ELF可执行文件。
遗憾是期间有很多考试，没有足够的时间做大作业，离完善还差很远。我的JOIN性能较低，记录换用列储存模式后可能会快一些。最后达到这一令人满意的分数后也有一些压力，不敢继续优化了，因为会影响到他人。比如并行的代码没有添加，也没有尝试其他的缓存算法。最初设想过使用OpenMP加速，但是LRU使用的双链表以及B+
tree使用的节点可能从磁盘读，并发的话感觉会产生很多冲突，可能还要换上lock-free数据结构。B+
tree的节点数也没调整过，没有对磁盘读写性能做调整，比如考虑磁盘的/sys/class/block/sda/queue/minimum_io_size等，以及使用open(2)的O_DIRECT进行直接IO。JOIN算法的框架还是生成树，还没有对表的限制做进一步的分析。B+
tree和Size-balanced
tree外也没有考虑过其他的数据结构。表信息存储也没考虑到其他方式，比如当字符串较小时和行数据内联从而减少潜在的page
faults数目以及提升缓存命中率，
可能带来性能提升。另外代码没有采用严谨的软件工程式写法，因为对于这样的Online
Judge形式测评网站，增大耦合度、减少文件数目而不去理会可复用性对性能的提升和开发时间的减少都有好处。所以这里也算是一个遗憾吧，如果换成严谨的写法，花的时间应该会乘以2，可能还不止。
课程建议
增设程序实现类的作业。
一次提交的周期太长了，特别是要考虑后几个测试点时，通常要一个小时以上的等候时间。而网站是顺序评测的，一个测试点不通过就不予以评测之后的，同学要花费很大的精力等待。即使写出来了但因为调试的困难性，可能还是要和网站交互很多次，影响效率。如果服务器内存大的话可以把加载的数据放到
/dev/shm/里，提示选手可以把临时文件写进去，但要注意容量不要超额，mount -o remount,size=4000M /dev/shm类似这样修改这个目录的大小限制。本质上选手还是在读写文件，但能大幅减少等待时间。Course Project for Database System网站提供具体的编译错误信息。
Group ID使用版本号排序而非字典序……
大作业说明文档中阐述服务器端程序的构建方式(选手程序如何链接，使用的gcc、glibc版本，编译选项等)
明确进程限制的各项参数含义：如内存是指maximum resident set size(
setrlimit的资源号RLIMIT_RSS)还是其他的，或者ulimit -m，后者的话本质上还是setrlimit，但是只修改了soft limit，选手程序可以调用setrlimit轻易绕过。应该同时指定-H修改hard limit，hard limit非特权用户是不能提升的。服务器用的Ubuntu 8.04比较旧了，漏洞很多，包括很多local root exploit。
参考资料
Handbook of Data Structures and Applications
The Multi-Queue Replacement Algorithm for Secon Level Buffer Caches
助教同学是我三年大学生涯碰到的最好的助教了，1月2日大家都还没动时还打电话通知，以及碰到的各种问题都会很快回复。还会给我们发程序的coredump，耐心解释评测系统(比如我询问是不是用setrlimit(RLIMIT_RSS, ...)做内存限制的，都很快答复了。程序的Runtime
Error也会来通知我们……