列式数据库的简单分析

2月 3rd, 2010 | Posted by | Filed under 数据库

本文内容遵从CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明
网址: http://www.penglixun.com/tech/database/column-oriented_dbms_analyse.html

这些天看数据仓库的内容,发现一个新内容——列式存储。曾经有想过把数据库行列转置作成索引,不过没有深想,没想到列式数据库已经开始发展起来了。
首先看下WIKI上对列式数据库的解释:

列式数据库是以列相关存储架构进行数据存储的数据库,主要适合与批量数据处理和即席查询。相对应的是行式数据库,数据以行相关的存储体系架构进行空间分配,主要适合与小批量的数据处理,常用于联机事务型数据处理。
数据库以行、列的二维表的形式存储数据,但是却以一维字符串的方式存储,例如以下的一个表:
EmpId Lastname Firstname Salary
1 Smith Joe 40000
2 Jones Mary 50000
3 Johnson Cathy 44000
这个简单的表包括员工代码(EmpId), 姓名字段(Lastname and Firstname)及工资(Salary).
这个表存储在电脑的内存(RAM)和存储(硬盘)中。虽然内存和硬盘在机制上不同,电脑的操作系统是以同样的方式存储的。数据库必须把这个二维表存储在一系列一维的“字节”中,又操作系统写到内存或硬盘中。
行式数据库把一行中的数据值串在一起存储起来,然后再存储下一行的数据,以此类推。
1,Smith,Joe,40000;2,Jones,Mary,50000;3,Johnson,Cathy,44000;
列式数据库把一列中的数据值串在一起存储起来,然后再存储下一列的数据,以此类推。
1,2,3;Smith,Jones,Johnson;Joe,Mary,Cathy;40000,50000,44000;
这是一个简化的说法。

昨天装了下两个基于MySQL的数据仓库,infindb和infobright,看了文档发现它们都是列式数据库,把40多M的数据导入infobright,没想到数据文件只有1M多,压缩比令我惊讶!
然后测试了下选择某一列,在列上做计算,都比MyISAM和InnoDB要快,看了一些原理文档,就自己模拟了一下,写了个程序测试。
从内存中读取效率很高,但是从磁盘中读取(假设行式数据库的索引在内存中)比行式数据库要慢(开始在Twitter上说比行式快是程序写错了),不过我觉得还是我设计上的问题,至少Infobright就比MyISAM/InnoDB快,列式应该也有其特殊的索引机制和缓存机制,例如每列分开存在不同的文件,这样文件指针转移会更快。
2010-02-04补充:采用了多个文件指针后,列式存储明显加速,如果给每个列一个文件指针,效率会非常高,也可以肯定,如果每个列单独存储一个文件,效率还会提高。现在文件中列式表读取效率降低了4/5,接近行式表了。继续优化还能提高。

代码请展开:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define MAXINT RAND_MAX
#define MAXROWS 1000000
#define MINVAL 1
#define MAXVAL 150000000

using namespace std;


/*计时器*/
class Timer {
public :
    //构造函数
    Timer ();
    //析构函数
    ~Timer ();
    //开始计时
    void begin();
    //计时结束
    void end();
    //获取时间,ms
    double get_time();
private :
    clock_t start, finish;
    double time;
};

Timer::Timer () {
    start = 0;
    finish = 0;
}

Timer::~Timer () {
    start = 0;
    finish = 0;
}

void Timer::begin () {
    start = clock();
}

void Timer::end () {
    finish = clock();
}

double Timer::get_time() {
    time = (double)(finish-start)/CLOCKS_PER_SEC*1000;
    return time;
}

//计时器
Timer timer;

/*记录各种结构表的空间占用*/
struct Size {
    struct {
        struct {
            int _static;
            int _dynamic;
        } col,row;
    } mem,file;
} size;

/*记录各种结构表的文件指针*/
struct File {
    struct {
        struct {
            fstream _static;
            fstream _dynamic;
        } table,index;
    } col,row;
} file;

/*静态行式表结构*/
struct StaticRowTable {
    int     id;
    char    name[255];
    int     num;
    double  score;
    bool    flag;
} * static_row_table;

/*静态行式表索引*/
struct StaticRowTableIndex {
    multimap    id;
    multimap  name;
    multimap    num;
    multimap score;
    multimap   flag;
} static_row_table_index;

/*静态列式表结构*/
struct StaticColTable {
    int*     id;
    char     (*name)[255];
    int*     num;
    double*  score;
    bool*    flag;
} static_col_table;

/*动态行式表结构*/
struct DynamicRowTable {
    int    id;
    int    char_len;
    char   *name;
    int    num;
    double score;
    bool   flag;
} * dynamic_row_table;

/*动态行式表索引*/
struct DynamicRowTableIndex {
    multimap    id;
    multimap  name;
    multimap    num;
    multimap score;
    multimap   flag;
} dynamic_row_table_index;

/*动态列式表结构*/
struct DynamicColTable {
    int*    id;
    int*    char_len;
    char**  name;
    int*    num;
    double* score;
    bool*   flag;
} * dynamic_col_table;

/*随机字符*/
char randChar() {
    return rand()%26+'A';
}

/*随机字符串*/
void randString(char col[], int len) {
    for(int i=0; i(static_row_table[i].id,i));
        
        randString(static_row_table[i].name, rand()%20+1);
        strcpy(static_col_table.name[i],static_row_table[i].name);
        static_row_table_index.name.insert(pair(static_col_table.name[i],i));
        
        static_col_table.num[i] =
        static_row_table[i].num = rand();
        static_row_table_index.num.insert(pair(static_row_table[i].num,i));
        
        static_col_table.score[i] = 
        static_row_table[i].score = rand()/rand();
        static_row_table_index.score.insert(pair(static_row_table[i].score,i));
        
        static_col_table.flag[i] = 
        static_row_table[i].flag = rand()%2;
        static_row_table_index.flag.insert(pair(static_row_table[i].flag,i));
    }
    timer.end();
    time = timer.get_time();
    cout << "数据生成完毕!" << endl;
    cout << "生成数据耗时: " 
         << time << "ms" << endl;
    
    
    //初始化文件指针
    timer.begin();
    file.row.table._static.open("row_table_static.dat", ios::binary | ios::out);
    file.row.index._static.open("row_index_static.dat", ios::binary | ios::out);
    file.col.table._static.open("col_table_static.dat", ios::binary | ios::out);
    
    if( !file.row.table._static ||
        !file.row.index._static ||
        !file.col.table._static) {
        cout << "打开文件失败" << endl;
    }
    
    cout << "正在将数据写入文件......" << endl;
    for(int i=0; i(&static_row_table[i]),
                                    sizeof(StaticRowTable));
    }
    file.row.table._static.close();
    for(int i=0; i(&static_row_table_index),
                                    sizeof(StaticRowTableIndex));
    }
    file.row.index._static.close();
    
    for(int i=0; i(&static_col_table.id[i]),
                                    sizeof(int));
    }
    for(int i=0; i(static_col_table.name[i]),
                                    sizeof(char[255]));
    }
    for(int i=0; i(&static_col_table.num[i]),
                                    sizeof(int));
    }
    for(int i=0; i(&static_col_table.score[i]),
                                    sizeof(double));
    }
    for(int i=0; i(&static_col_table.flag[i]),
                                    sizeof(bool));
    }
    file.col.table._static.close();
    timer.end();
    time = timer.get_time();
    cout << "数据写入完毕!" << endl;
    cout << "写入数据耗时: " 
         << time << "ms" << endl;

    //计算总占用空间
    size.mem.row._static = sizeof(*static_row_table)*MAXROWS
                    +sizeof(static_row_table_index)*MAXROWS;
    size.mem.col._static = (sizeof(int)*2+sizeof(double)
                    +sizeof(bool)
                    +sizeof(char)*255)*MAXROWS;
    
    cout << "静态行式存储耗费空间: " 
         << size.mem.row._static/1024/1024 << "M" << endl;
    cout << "静态列式存储耗费空间: " 
         << size.mem.col._static/1024/1024 << "M" << endl;
}

void init_DynamicTable() {
    double time;
    
    cout << "+-----动态数据-----+" << endl;
}

void init() {
    double time1, time2;
    
    srand(time(0));
    
    cout << "======生成数据======" << endl;
    
    init_StaticTable();
    init_DynamicTable();
}

/*
SELECT name
FROM table 
WHERE num BETWEEN MINVAL AND MAXVAL;
*/


/*测试内存中静态行存储*/
int Mem_Static_testRow() {
    double time;
    int count = 0;
    int id;
    multimap::iterator it,itlow,itup;
    
    cout << "正在测试内存中读取行式静态表......" << endl;
    timer.begin();
    itlow = static_row_table_index.num.lower_bound (MINVAL);
    itup = static_row_table_index.num.upper_bound (MAXVAL);
    
    for (it=itlow; it!=itup; ++it) {
        id = (*it).second;
        StaticRowTable row = static_row_table[id];
        //结果
        //cout << row.id;
        /*cout << '\t' << */row.name;
        //cout << '\t' << row.num;
        //cout << endl;
        //计数
        ++count;
    }
    timer.end();
    time = timer.get_time();
    cout << "内存中行式静态表读取测试完毕!" << endl;
    cout << "读取耗时:" << time << " ms" << endl;
    
    return count;
}

/*测试磁盘中静态行存储*/
int File_Static_testRow() {
    double time;
    int count = 0;
    int id;
    char *name;
    int num;
    int pos;
    StaticRowTable row;
    multimap::iterator it,itlow,itup;
    
    //初始化文件指针
    cout << "正在测试磁盘中读取行式静态表......" << endl;
    timer.begin();
    file.row.table._static.open("row_table_static.dat", ios::binary | ios::in);
    //file.row.index._static.open("row_index_static.dat", ios::binary | ios::in);
    
    if(!file.row.table._static) {
        cout << "打开文件失败" << endl;
    }
    //假设索引在内存中
    itlow = static_row_table_index.num.lower_bound (MINVAL);
    itup = static_row_table_index.num.upper_bound (MAXVAL);
    
    for (it=itlow; it!=itup; ++it) {
        id = (*it).second;
        pos = sizeof(StaticRowTable)*id;
        file.row.table._static.seekg(pos);
        file.row.table._static.read(reinterpret_cast(&row),
                                    sizeof(StaticRowTable));
        //结果
        //cout << row.id;
        /*cout << '\t' << */row.name;
        //cout << '\t' << row.num;
        //cout << endl;
        //计数
        ++count;
    }
    file.row.table._static.close();
    //file.row.index._static.close();
    timer.end();
    time = timer.get_time();
    cout << "磁盘中行式静态表读取测试完毕!" << endl;
    cout << "读取耗时:" << time << " ms" << endl;
    
    return count;
}

/*测试磁盘中静态列存储*/
int Mem_Static_testCol() {
    double time;
    int count = 0;
    int id;
    int num;
    char *name;
    
    cout << "正在测试内存中列式静态表读取......" << endl;
    timer.begin();
    for(int i=0; iMINVAL and num(&num),
                                    sizeof(int));
        if(num>MINVAL and num(name),
                        sizeof(char[255]));
            /*cout << '\t' << */name;
            //cout << '\t' << num;
            //cout << endl;
            //计数
            ++count;
        }
    }
    file.col.table._static.close();
    timer.end();
    time = timer.get_time();
    cout << "磁盘中列式静态存储表读取测试完毕!" << endl;
    cout << "读取耗时:" << time << " ms" << endl;
    
    return count;
}

void test() {
    int count1, count2, count3, count4;
    
    cout << "=====内存存取测试=====" << endl;
    cout << "+----静态表测试中----+" << endl;
    cout << "*行式存储*" << endl;
    //内存中静态行式存储表
    count1 = Mem_Static_testRow();
    //内存中静态列式存储表
    count2 = Mem_Static_testCol();
    cout << "*列式存储*" << endl;
    //磁盘中静态行式存储表
    count3 = File_Static_testRow();
    //磁盘中静态行式存储表
    count4 = File_Static_testCol();
    
    if (count1==count2 and count2==count3 and count3==count4) {
        cout << "共匹配:" << count1 << " 行" << endl;
    } else {
        cout << "错误:每次匹配行数不同" << endl;
    }
    
}

int main() {
    init();
    test();
    cout << "All OK!" << endl;
    return 0;
}

2010-02-04测试结果:
======生成数据======
+-----静态数据-----+
分配空间中......
空间分配完毕!
分配空间耗时: 0ms
生成数据中......
数据生成完毕!
生成数据耗时: 4180ms
正在将数据写入文件......
数据写入完毕!
写入数据耗时: 2480ms
静态行式存储耗费空间: 495M
静态列式存储耗费空间: 259M
+-----动态数据-----+
=====内存存取测试=====
+----静态表测试中----+
*行式存储*
正在测试内存中读取行式静态表......
内存中行式静态表读取测试完毕!
读取耗时:10 ms
正在测试内存中列式静态表读取......
内存中列式静态存储表读取测试完毕!
读取耗时:0 ms
*列式存储*
正在测试磁盘中读取行式静态表......
磁盘中行式静态表读取测试完毕!
读取耗时:190 ms
正在测试磁盘中列式静态表读取......
磁盘中列式静态存储表读取测试完毕!
读取耗时:210 ms
共匹配:69650 行
All OK!

  1. ike
    6月 8th, 201013:56

    这篇文章不错,请问你是用那个“related post”的plugin?

    [回复]

  2. NOSQL列存 | 杨益的博客
    7月 28th, 201113:00
    #8