转自：列式数据库的简单分析
这些天看数据仓库的内容，发现一个新内容——列式存储。曾经有想过把数据库行列转置作成索引，不过没有深想，没想到列式数据库已经开始发展起来了。
首先看下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 <iostream>
#include <fstream>
#include <cstdlib>
#include <memory>
#include <string>
#include <cstring>
#include <time.h>
#include <map>
#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<int,int> id;
multimap<char*,int> name;
multimap<int,int> num;
multimap<double,int> score;
multimap<bool,int> 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<int,int> id;
multimap<char*,int> name;
multimap<int,int> num;
multimap<double,int> score;
multimap<bool,int> 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<len; ++i) {
col[i] = randChar();
}
}
/*初始化表数据*/
void init_StaticTable() {
double time;
cout << "+-----静态数据-----+" << endl;
//分配空间
cout << "分配空间中......" << endl;
timer.begin();
static_row_table = new StaticRowTable[MAXROWS];
static_col_table.id = new int[MAXROWS];
static_col_table.name = new char[MAXROWS][255];
static_col_table.num = new int[MAXROWS];
static_col_table.score = new double[MAXROWS];
static_col_table.flag = new bool[MAXROWS];
timer.end();
time = timer.get_time();
cout << "空间分配完毕!" << endl
<< "分配空间耗时: "
<< time << "ms" << endl;
//产生随机数据和索引
cout << "生成数据中......" << endl;
timer.begin();
for(int i=0; i<MAXROWS; ++i) {
static_col_table.id[i] =
static_row_table[i].id = i;
static_row_table_index.id.insert(pair<int,int>(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<char*,int>(static_col_table.name[i],i));
static_col_table.num[i] =
static_row_table[i].num = rand();
static_row_table_index.num.insert(pair<int,int>(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<double,int>(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<bool,int>(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<MAXROWS; ++i) {
file.row.table._static.write(reinterpret_cast<char *>(&static_row_table[i]),
sizeof(StaticRowTable));
}
file.row.table._static.close();
for(int i=0; i<MAXROWS; ++i) {
file.row.index._static.write(reinterpret_cast<char *>(&static_row_table_index),
sizeof(StaticRowTableIndex));
}
file.row.index._static.close();
for(int i=0; i<MAXROWS; ++i) {
file.col.table._static.write(reinterpret_cast<char *>(&static_col_table.id[i]),
sizeof(int));
}
for(int i=0; i<MAXROWS; ++i) {
file.col.table._static.write(reinterpret_cast<char *>(static_col_table.name[i]),
sizeof(char[255]));
}
for(int i=0; i<MAXROWS; ++i) {
file.col.table._static.write(reinterpret_cast<char *>(&static_col_table.num[i]),
sizeof(int));
}
for(int i=0; i<MAXROWS; ++i) {
file.col.table._static.write(reinterpret_cast<char *>(&static_col_table.score[i]),
sizeof(double));
}
for(int i=0; i<MAXROWS; ++i) {
file.col.table._static.write(reinterpret_cast<char *>(&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<int,int>::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<int,int>::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<char *>(&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; i<MAXROWS; ++i) {
int num = static_col_table.num[i];
if(num>MINVAL and num<MAXVAL) {
//结果
//cout << i;
/*cout << ‘\t‘ << */static_col_table.name[i];
//cout << ‘\t‘ << static_col_table.num[i];
//cout << endl;
//计数
++count;
}
}
timer.end();
time = timer.get_time();
cout << "内存中列式静态存储表读取测试完毕!" << endl;
cout << "读取耗时:" << time << " ms" << endl;
return count;
}
/*测试磁盘中静态列存储*/
int File_Static_testCol() {
double time;
int count = 0;
int id;
int num;
char *name = new char[255];
int pos_num;
int pos_name;
int pos;
cout << "正在测试磁盘中列式静态表读取......" << endl;
timer.begin();
file.col.table._static.open("col_table_static.dat", ios::binary | ios::in);
fstream tmpfile("col_table_static.dat", ios::binary | ios::in);
if(!file.col.table._static || !tmpfile) {
cout << "打开文件失败" << endl;
}
pos_name = sizeof(int)*MAXROWS;
pos_num = (sizeof(int)
+sizeof(char[255]))*MAXROWS;
file.col.table._static.seekg(pos_num);
for(int i=0; i<MAXROWS; ++i) {
file.col.table._static.read(reinterpret_cast<char *>(&num),
sizeof(int));
if(num>MINVAL and num<MAXVAL) {
//结果
id = i;
//cout << id;
pos = pos_name+sizeof(char[255])*id;
tmpfile.seekg(pos);
tmpfile.read(reinterpret_cast<char *>(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!