OLAP 一些扯淡

行存(NSM) VS 列存(NSM)

两种存储方式各有各的好处，行存就像写日志一样一行一行的存，更新相对来说会方便一些。列存是一列数据放在一起，相对来说更新不太方便，但是压缩可能会更好一些。

假设有一个超大宽的表，有100个列，但是你的某个查询只涉及2-3个列。如果是行存那你可能需要把所有的列都读出来。但是对于列存，你可以只读取对应的几个列

基于Tuple的计算 VS 基于Column的计算

基于Tuple的计算

基于Tuple的计算大概可以理解为基于行的计算。在计算中数据是以行的模式进行处理的。

一个tuple中可能有多个元素

对于一个Tuple 结构是 (int,int64,int128)的来说，想要执行一次计算大概是这样 (一个Copy操作)

TupleDescriptor desc = xxxx; // 用于描述这个tuple的结构
RowBatch src = xxx;
RowBatch dst = xxx;
for(int i = 0;i < rows; ++i) {
    Tuple tuple = batch->get_row(i); // 获取这一样对应的tuple数据
    for(int j = 0;j < desc.slots().size();++j) {
        void *data = tuple.get_data(desc.slots(j).offset); // 获取某一行的数据
        switch(desc.slots(j)) { // 通过desc中的描述类型来解释执行
            case TYPE_INT: xxxx;
            case TYPE_STRING: xxxx;
            ....;
        }
    }
}

所以对于基于Tuple的计算模型来说因为运行时需要采取类似解释执行的问题效率不太理想，所以很多基于Tuple计算的引擎实现都是通过一些Codegen(例如Impala)或者是通过中间码(SQLite)

生成的代码类似这样:

for(int i = 0;i < rows; ++i) {
    Tuple tuple = batch->get_row(i); // 获取这一样对应的tuple数据
    int *data_col0 = (int*)tuple.get_data(0); // offset 以及具体的类型会在生成中间代码的时候确定
    int64* data_col1 = (int64*)tuple.get_data(4);
    int128* data_col2 = (int128*)tuple.get_data(12);
    // handle copy
    ....
}

这样执行生成的代码会少很多的branch miss

基于Column的计算

基于column的计算一般没有类型判断这种开销。而且通常情况下，一次计算的数据大概率是在一个cache中进行计算的(对比一般实现占主要的提升)，而且比较容易应用一些SIMD指令(对INT类型提升不大，远远没cache和inline的提升明显，对于浮点数提升比较可观)。

一般代码长这样 (一个Copy操作)

DataTypes types;
Columns columns;
Columns dst_columns;
for i in range(types.size())
	switch(types[i]) {
		TYPE_INT:
			for(j = 0; j < rows < ++j) {
				(*(int*)dst_column->data() + j) = (*(int*)column->data() + j);
			}
		TYPE_STRING: xxx;
        ...
	}

虽然也有类型判断，但是这些判断在每一列中只会判断一次，可以忽略不计了

向量化执行和短路执行

向量化执行在处理分支的时候会把所有的分支结果都运行一下

例如:

Size sz = 1024;
float dst[sz];
float src[sz] = xxxx;
for(int i = 0;i < sz; ++i) {
    if (src > 100) {
        dst[i] = src[i] * 4 - 2;
    } else {
        dst[i] = src[i] / 2;
    }
} 

这段代码的向量化实现大概是这样

Size sz = 1024 / 8;
vec_flt dst[sz];
vec_flt src[sz] = xxxx;

for(int i = 0;i < sz; ++i) {
    flt_vec tmp_v0 = src[i] * 4 - 2;
    flt_vec tmp_v1 = src[i] / 2;
    flt_vec mask = src[i] > 100;
    
    dst[i] = select_if(mask, tmp_v0, tmp_v1);
}

select_if 大概意思就是如果mask[k] 为1,那么 dst[i][k] 是tmp_v0[k]否则是 tmp_v1[k]

向量化实现会有更少的branch miss，但是如果条件比较多，或者某些分支是比较重的操作，向量化实现可能会有更差的性能表现。

控制依赖和数据依赖

控制依赖

// select input > val 的元素
for (i = 0, found = 0; i < n; i++)
	if (input[i] > val)
		result[found++] = i;
return found;

数据依赖

for (i = 0, found = 0; i < n; i++) {
	result[found] = i;
	found += (input[i] > val);
}
return found;

数据依赖在编译的时候虽然不能产生SIMD指令，但是由于有较少的branch miss，实际表现会比控制依赖好一些。