![Java BitSet
? bit运算 & | b | 000001
? Java.util.BitSet
– Get(index)
– Set(index)
– Or
– And
– Xor
– AndNot
? boolean[]?
? 用Long存储，未压缩](https://image.slidesharecdn.com/random-170426012133/85/-32-320.jpg)
列式存储、位图技术研究及应用
- 2. 永远年轻的古老技术 ? 传统： – 关系数据库(sybaseIQ) – 数据仓库 – 数据分析 ? 新兴： – Nosql： cassandra等 – 大数据时代 ? hadoop领域：hive，hbase ? 实时分析：storm，spark
- 3. 目录 ? 列式存储 ? 位图 ? 应用
- 4. 行式存储 ? 表按行存储 ? 表<=Block<=Row ? 索引 – B+索引 – 位图索引 – Hash索引
- 5. 列式存储 ? 表按列存储 ? 表<=Block<=Column ? 列式存储数据及索引
- 6. 行式 VS 列式 ? 行式存储，行记录数据差 异大 ? 列式存储，列值重复多 ? 列式优势： – 易于压缩 – 易于索引 – 易于统计 ? 列式劣势： – Insert/update – 查询结果Tuple(行)重组 类别 颜色 性别 上衣 红色 女 裤子 蓝色 女 上衣 黑色 女 裙子 红色 女 上衣 红色 男 裤子 蓝色 女 上衣 黑色 女 裙子 红色 女
- 7. 行式 VS 列式 ? Select a,d,h from t ? 行式需要遍历所有行所有列IO ? 列式只要访问3列的IO
- 8. 行式 VS 列式 ? Where a=xxx ? 行式依赖于是否有索引 ? 列式每列都天然带索引 ? Where a=xxx or/and b=yyy ? 行式依赖于是否有索引及索引 类型 ? 列式每列都天然带索引， and/or只要bit and/or操作， cpu指令支持
- 9. 行式 VS 列式 ? 性能提升10*N倍 ? 节约空间N倍
- 12. 列式存储格式 ? 位图 ? Where 颜色=‘红色’ ? Where 颜色=‘红色’ and 类别=‘上衣’ 类 别 颜 色 性 别 上衣 红色 女 裤子 蓝色 女 上衣 黑色 女 裙子 红色 女 上衣 红色 男 裤子 蓝色 女 上衣 黑色 女 裙子 红色 女 上 衣 裤 子 裙 子 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 红 色 蓝 色 黑 色 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 男 女 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 类别 颜色 性别 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 and 1 0 0 0 1 0 0 0 =
- 13. 列式存储格式 ? 值偏移
- 14. 列式存储格式 ? Bitwise ? Quick sum
- 15. 位图索引 ? 数据库索引 – Btree – Hash – Bitmap – 空间索引 ? Rtree ? KDTree
- 16. 索引解决什么问题 ? 等值查询Equality： where a=xxx ? 范围查询Range: where a<200 and a>100 ? 距离查询（只针对空间索引）
- 17. 什么时候使用位图索引 ? Low cardinality，即一列中包含distinct value 个数少 ? 查询为主
- 19. 位图编码 ? 等值编码Equality Encoding – Basic Bitmap – Bit Sliced Bitmap ? 范围编码Range encoding
- 21. bit sliced Bitmap ? SybaseIQ使用 ? X = 4 * y + z： 11 = 4 * 2 + 3 ? X = 10 * y + z：96 = 10 * 9 + 6 月份由：12个变成7个 同理0-99由100个变成20个
- 22. Range Encoding ? Month>=a: v(a) ? Month<=a: v(a)-v(a+1) ? a<=month<=b: V(a) -V(b+1)
- 24. 位图压缩 ? 轻量压缩，不解压也能参与计算 – RLE（Run Length Encoding） – BBC（Oracle） – WAH（spark，hive等） RLE： 0001 00000000000001 1 01 000 (0,3) (0,13) (0,0) (0,1) 1011 11101101 00 01 重型压缩：GZIP, ZLIB等
- 25. 应用 ? 传统数据库 – Create bitmap index ? 列式数据库 – SybaseIQ – Cstore，Monet，Vetica – SAP加速器 – SAP HANA ? Hadoop体系 ? 内存数据库内置列式存储
- 26. SAP HANA ? 分布式数据库 ? 内存数据库 ? 融合行式 + 列式 ? SAP Cloud
- 27. Hadoop体系文件格式 TextFile SequenceFile RCF Record Columnar File ORCFile Optimized Row Columnar File 淳朴的行式存储 行式存储，加入重型压缩 行列组合，先行分组，再列式存储 列式存储比较粗暴，只有重型压缩zip等 行列组合，先行分组，再列式存储 列式存储比较精细，多数据类型，轻量级压缩 (RLE，Directory)， ProtoBuf压缩，索引，预先统 计(sum,count)等
- 29. ORCFile Index data:对于列的元数据 row data：列数据存储 stripe footer：辅助信息，统计信息 Encoding Variable-width Encoding:from protobuf Run Length encoding Directory encoding Delta encoding
- 30. Parquet
- 31. Apache Spark对列式的支持 ? 流式计算框架 ? In Memory Columnar Storage，内存缓存表 ? 表数据扫描支持列式优化特性： – Column Pruning – Predicate pushdown ? External datasource api接入其他数据源 ? Spark和Hadoop MapReduce的比较： – http://wenku./view/02acb4f1af1ffc4fff 47ac2a.html?from=search
- 32. Java BitSet ? bit运算 & | b | 000001 ? Java.util.BitSet – Get(index) – Set(index) – Or – And – Xor – AndNot ? boolean[]? ? 用Long存储，未压缩
- 33. 开源bitset ? Roaringbitmap：www.roaringbitmap.org ? 号称最高效压缩，性能最优，超越 – RLE – WAH，EWAH – CONCISE – BBC ? 广泛被使用： apache lucene，apache Spark， apache kylin
- 34. 开源项目 ? 列式存储数据集 – Apache Arrow：内存列式数据集 – Apache Parquet：列式存储格式 ? 列式数据库： – Monet ? No sql： cassandra ? Hadoop：hive, hbase
- 35. ERP领域应用 ? 扩展数据库索引：Create bitmap index ? 报表 ? 统计分析 ? OLAP/预算 ? 数据交换，列式存储，记录集 RowSet ? 磁盘缓存： – 按列存储 – Bitmap index ? 基础算法应用 – bitset – Hash index – Bitmap index
- 36. 讨论 ? 提高编程技巧 ? 业务功能 – 位图索引 – 列式数据库：读写分离，数据仓库 – 报表
- 37. 填写反馈 云之家扫一扫
Editor's Notes
- #30: ORCFile? ORCFile是一种列式存储的文件，对于分析型应用来说列存有非常大的优势。 原来的RCFile中把每一列看成binary blob，没有任何语义，所以只能用通用的zlib,LZO,Snappy等压缩方法。ORCFile能够获取每一列的类型(int还是string)，那么就可以使用诸如dictionary encoding, bit packing, delta encoding, run-length encoding等轻量级的压缩技术。这种压缩技术的优势有两点：一是提高压缩率；二是能够起到过滤无关数据的效果。 Predicate Pushdown:原来的Hive是把所有的数据都读到内存中，然后再判断哪些是符合查询需求的。在ORCFile中数据以Stripe为单元读取到内存，那么ORCFile的RecordReader会根据Stripe的元数据(Index Data，常驻内存)判断该Stripe是否满足这个查询的需求，如果不满足直接略过不读，从而节省了IO。