C-Store论文阅读笔记

C-Store论文由今年的图灵奖获得者Mike Stonebraker提出来，整体架构在数据库领域相当不错。数据库采用读写分开存的架构，只写块的数据定期会和只读块儿的数据进行合并，产生新的只读块儿。而C-Store在只读块儿部分做了读优化操作，这一点相当不错。

1. 数据模型

猜想商业数据库的Clustrix的存储数据模型就是收到了这篇论文的影响，所以才会有C-Store论文中提到的这样的数据模型构造。首先需要明确的一点是，C-Store本身是列数据库，所以存储数据是按照列为单位来进行存储，这样就可以玩出很多花样来，比如列压缩，列索引之类的。对于查询方面的优化是无疑的。

在数据模型方面，有两个重要的概念，一个是projection，一个是Segment。可以这么理解，projection是对表的纵切，而Segment是对表的横切。举一个实际的例子：

Name	Age	Dept	Salary
Bob	25	5	Math
Bill	27	EECS	50K
Jill	24	Biology	80K

那么一个projection可以是这样

一个Segement可以是这样
| Name | Age |
| -------- | ----- |
| Bob | 25 | 5 |

projection更类似与一个列族的概念，而Segement更像是一个行表的概念，只是对一个projection进行切分。

列数据相对于行数据库而言，最大的优势就是压缩了，在C-Store这篇论文里面，针对RS(Rea-optimized Store)这一块儿的数据进行了压缩，论文里面探讨了四种情况下的压缩方案：

Self-order，few distinct values：内排序并且少许不一样的数据，也就是说，这一列的数据是排好序的同时，重复数据比较多，那么压缩方案就好办了。利用一个三维向量表示(v,f,n)，其中v表示value，f表示该value出现的位置，n表示该value重复的次数，例如在12-18号位置出现了4，那么就可以表示为（4,12,7）。
Foreign-order，few distinct values：这种情况下，采用位图压缩的方式对这一列进行压缩，例如一个列的值序列如下为 0,0,1,1,2,1,0,2,1，那么压缩的方式为（0,110000100），（1,001101001），（2,000010010）也就是如果该value出现在哪一号位置，就在对应的位图位置上置1。
Self-order，many distinct values： vaues：在这种情况下，前面的两种压缩方案都不会适用了，在C-Sotre论文中提到了一种增量压缩的方式，在一列数据中，每一个值都可以由他的前一项进行推导出来，例如一个列数据序列1,4,7,7,8,12，那么压缩之后，这个序列变为：1,3,3,0,1,4。
Foreign-order，many distinct values：在这种情况下，压缩基本不可能实现，但是可以用一颗紧凑的B+树对其进行索引。