原文：[Column-Stores vs. Row-Stores: How Different Are They Really](http://www.cs.umd.edu/~abadi/papers/abadi-sigmod08.pdf) # ABSTRACT 列存不仅仅只是 IO 更高效（分析场景下读操作）。 列存与行存两者在查询执行层面也有着很大的不同，如 vectorized、compression 以及 join 算法等。 结论：**两个层次** storage layer 和 query executor 都必须改变才能完整发挥列存的优势。 -------------------- # 1. INTRODUCTION - 尝试在 row-store 中模拟 column-store 的物理结构： - 垂直切分 table 为多个只有两列（key，attribute）的 tables - 为查询涉及到的所有列建立索引 - 为每个查询需要的列建立物化视图 结果是查询性能仍然很差。 - column-oriented DBMS 专用的优化技术： - Late materialization ( [[12-query-execution-1#Late Materialization | Late Materialization]] ) - Block iteration（[[12-query-execution-1#2.3 Vectorization Model | Vectorization Access Model]] ) - 列存专用的压缩技术如 run-length encoding，以及 Late materialization 时直接在压缩数据上操作 - 提出新优化：invisible joins - 对不同的优化项的提升效果分别对比： - compression：一些场景下有**数量级**的提升，但有些场景却提升很小 - late materialization：3 倍性能提升 - 其他：平均 1.5 倍 简单的列存（没有 compression 和 late materialization）**不能**比优化过的行存好太多。 ----- # 2. BACKGROUND AND PRIOR WORK - [MonetDB](https://dl.acm.org/doi/pdf/10.1007/s007780050076) 和 [MonetDB/X100](https://www.cidrdb.org/cidr2005/papers/P19.pdf) ：现代列存数据库和向量化执行的先锋 它们证明了列存设计带来了更好的 CPU 和 cache 性能（除了减少 IO），TPC-H 上打败了其他商用和开源的数据库 - fractured mirrors：行列混合 行存处理更新，后台迁移到列存。 - [C-Store](https://web.stanford.edu/class/cs345d-01/rl/cstore.pdf)：更新的列存数据库 可以直接在压缩后的数据上进行操作 --------- # 3. STAR SCHEMA BENCHMARK SSBM 是从 TPC-H 衍生而来的数仓 benchmark。 ## Schema 只有一个 fact table - LINE-ORDER 表 合并了 TPC-H 中的 LINEITEM 和 ORDERS 两个表。 17列，主键：( ORDERKEY， LINENUMBER) 通过外键引用其他维表 ------- # 4. ROW-ORIENTED EXECUTION 几种可以用来用行存模拟列存的技术。 - Vertical Partitioning - Index-only plan - Materialized Views -------- # 5. COLUM-ORIENTED EXECUTION ## 5.1 Compression - 按列存储数据，可以达到**更高**的压缩率。 - 压缩能提升性能的关键在于能**节省IO** - 如果可以在**压缩数据上直接进行操作**，则可以进一步提升性能 - 如果列是**排序**过的，则压缩的优势更大（可能出现连续多个values都是相同的） 每个列都排序开销太大，按照多个列组合排序也有较好效果 ## 5.2 Late Materialization - **tuple construction** 列存中，tuple 的数据分布在不同的位置 大多数查询需要访问多个列，就需要在某个时间点组装分散的列，还原为 tuple - **late materialization** operator 之间传递 position lists - **late materialization 的优势** 1. 许多 selection 和 agg 计算，不需要整个 tuple 3. construction 必须**解压**（然后才能跟其他列值合并），失去了直接对压缩数据进行操作的优势 4. cache 性能更好，因为 cache line 不会被其他无关的列污染 5. block iteration 处理固定长度的列值更高效。而 construction 可能引入其他变长的列，导致 tuple 成为变长的。 > 思考：如果内存中组织成列存，某些点的优势可能不再存在 ## 5.3 Block Iteration 在列存下，将同一列的一批 values 在一个函数调用内发生给 operator。 进一步地，如果列是**固定长度**的，values 可以直接通过数组下标迭代，在当代 CPU 下能发挥潜在的并行能力。 ## 5.4 Invisible Join - 适用场景：列存数据库，星型表的外键/主键 join - invisible join 也是一种 late materialized join，但是最小化需要乱序提取的 values - 工作原理： 将 join 重写为在 fact table 的外键列执行 predicates