基于 PostgreSQL 数据库的表压缩技术研究与实现.ppt

表压缩方案介绍 数据表压缩：基于排序的字典生成方案 1 A ROWID01 1 B ROWID02 2 A ROWID03 1 B ROWID04 3 C ROWID05 3 C ROWID06 3 D ROWID07 1 A ROWID08 1 A ROWID09 1 C ROWID10 3 A ROWID11 3 C ROWID12 3 C ROWID13 字典条目生成算法 ①扫描连续若干条记录 ②返回字典条目数组 字典条目1 … … 字典条目N ③扫描下一组记录 表压缩方案介绍 数据表压缩：基于排序的字典生成方案 ID Name Country 1001 Jack US 1002 Jack JP 1003 John US … … … 001JackUS 002JackJP 003JohnUS 01JackUS 02JackJP 03JohnUS … … 001JackUS 003JohnUS subStr1 002JackJP 01JackUS subStr2 … … MaxSubStr = Longest(subStr1, subStr2, … …) 预读取N条记录 生成后缀数组并排序 判断连续N个后缀 是否同源 动态规划法获取首尾两个记录的最长公共子串 表压缩方案介绍 数据表压缩：字典生成方案算法对比 抽样算法： record ? 待插入记录 offset ? 插入记录在item数组中的偏移量 frequency ? 生成字典条目的频率 if (offset % frequency == 0) { //插入字典条目 insertDict(dict, record); //调整字典插入指针 resetDictPtr(dict, record.getLength()); } 排序算法：生成一个字典条目 subStr = null; s = 0; while(s + RD_NUM– 1 = N) { if(suffix[s] to suffix[s + RD_NUM - 1] are from different records) { str = getCommonPrefix(suffix[s], suffix[s + RD_NUM - 1]); if(str.len subStr.len) subStr = str; } s++； //后移，处理下一组后缀记录 } //end while insertDict(subStr); replace(suffix[], subStr，’\xFF’); qsort(suffix[]); 抽样算法：时间复杂度O(1) 空间复杂度O(1) 排序算法：时间复杂度O(C*N*M) 空间复杂度O(N*M) C:所需字典条目数；N：记录个数； M：记录长度 补充工作 基于字典的Btree索引压缩方案 Page Header Item1 … ItemN 索引字典 Special Space flags IndTup1 IndTup2 … … IndTupN 抽样方式产生字典条目； 按字段对其寻找匹配子串； 替代重复字段只需要两个字节，记录在字典中的偏移量即可。 Header int bigint bigint Header dict_off bitmap 压缩 压缩率：16 / 28 = 57.14% 补充工作 基于字典的Btree索引压缩方案 原页面规模 压缩页面规模 压缩率 1000条记录 7页，56 KB 6页，48 KB 85.71% 10000条 记录 10_10_100 46页，368 KB 47页，376 KB 102.17% 10_100_10 46页，368 KB 40页，320 KB 86.96% 100_10_10 46页，368 KB 42页，336 KB 91.30% CREATE TABLE test ( C1 bigint, C2 int, C3 bigint ) CREATE INDEX test_index on test (C1, C2, C3); 测试数据： for (i=1; i10; i++) for(j=1; j10; j++) for(k=1; k100; k++) output(i, j, k); 补充工作 基于字典的Btree索引压缩方案 10000条记录 10_10_100 46页，368 KB 47页，376