原文 https://15721.courses.cs.cmu.edu/spring2023/papers/04-olapindexes/p1177-larson.pdf

背景

微软在 SQL Server 11.0 版本,推出了一款纯的列数据库,代号 Denali
从测试效果看非常不错,对 TPC-DS 的 1T 数据做了测试,包含冷数据,和温数据
从结果看,列存场景比 行存有 10 - 20倍的提升

Table 1: Observed CPU and elapsed times (in sec)

SQL Server 早期有两种存储组织

  • heap,未排序的
  • B树,排序的

这两种都是面向行的,表或者物化视图总是包含一个主存储结构、以及二级搜因
主存储是 heap、B树,二级索引只能是 B树
也支持 filtered 索引,只存储满足选择谓词的行
任何索引都可以当做 列存索引,做的事情也没有限制

列存的物理数据组织方式,首先是将行分组,然后每组再分成若干个列
这里一共 3个行组,每个3 个列,一共 9个列segments
这里没每个行存都是独立的,所以不同组的列数据都是可以独立压缩的
Figure 1: Converting rows to column segments

索引存储结构

每个 column segment 当做 独立的 blob存储
segment 可能很大,会被自动分成多个 page
这里还有一个 directory 来跟踪每个 segment,directory 可以通过系统 catalog sys.column_store_segments 获取
directory 也包含了一些元信息,行数量、size、多少数据被编码,min、max等

Figure 2: Storing column segments

这种存储方式 列存储索引,好处是

  • 使用现有的 blob存储和 catalog 实现,无需新的存储机制
  • 很多机制都是自动可用的,如lock、日志、恢复、分区、镜像、复制
  • 以及其他一些特定对新的索引类型都是立刻可用的

编码列包含三个阶段

  • 对所有列中的值进行编码。
  • 确定最优的行排序。
  • 压缩每个列

编码方式有两种

  • 字典编码
  • 基于值的编码

字典编码本质上是一个按数据id索引的数组,每个字典按 blob 存储
并存储到系统表中 sys.column_store_dictionaries
基于值的编码,是将一个大范围的值转换为一个更小的值
比如 0.5、10.77、1.333,应用指数 3(1000)后,就变成了500、10700、1333
也可以应用负指数,如 -2(1/100),对于值500、1700、133300 就变成了: 5,17、13330
首先选择一个一个基数作为最小数,然后每个数都减去这个最小数
比如基数为500、则调整后的值为:0、10270、833

还可以对数据做压缩,如采用 run-length 编码,RLE,这样可以直接基于压缩数据读取,首先对行组做排序,然后压缩
SQL Server 使用的是专利技术:Vertipaq
RLE 被存储为 <value, count> 对
数据从磁盘 -> 内存,不再是面向page的布局,而是连续的 buffer pool 布局
另外 column segment 分成一个一个的page,可以应用预读取技术

查询处理和优化

在这种新的索引基数上需要有新的引擎,但这种引擎不是重新设计的,而是基于现有技术改进的

  • 对于客户来说他们使用的还是原有技术,但是新索引类型会加速查询
  • 减少了实现成本,并且很多成熟的技术都是可以立刻使用的,如查询计划图、查询执行统计、SQL profiling、SQL debug等
  • 查询计划可能会混合多个算子,查询优化会扩展选择最优算子类型
  • 查询可以在运行时动态的从 批量操作 转换为 一次一行的操作
  • 新操作类型也可以帮助现有技术提升效率

虽然说 一次一批 比一次行提高不少性能,但也达不到数量级的提升,论文中还有几点改进,可以有数量级性能提升

  • 利用最新CPU的特性,多核
  • bitmap filter
  • 算子之间的内存共享

在SQL Server中采用了一种“混合”模式来处理查询:

  • 首先将原始行格式转换为批(即按块)格式,并利用批处理操作符等新特性快速完成相关计算
  • 然后再根据需要将结果转换回行格式并返回给用户或其他应用程序

以下是一些需要在行和批之间进行转换的具体场景:

  • 执行聚合操作,如SUM、AVG等;
  • 进行连接操作,如JOIN、UNION等;
  • 对大型表进行扫描或筛选时(例如数据仓库中的事实表);
  • 在查询结果集较大时(例如返回数百万条记录)。

为了支持列存储索引,SQL Server做了以下查询优化方面的改进:

  1. 引入新算法用于构建最大尺寸批处理哈希连接管道以提高性能
  2. 引入位图过滤器和批处理操作符等新特性来减少I/O并提高CPU利用率
  3. 通过估计成本选择最佳执行计划,并对代价模型进行增强

列存索引的 IndexScan 支持下推 predicate 以及 bitmap(可能由 HashJoin 生成)
此外,还有 delayed materialization(延迟物化)、SIMD 指令集等支持
通过估算 CPU 和 IO 代价,判断使用 列索引,还是 B树索引

为支持行批混合操作,引入了一个新算子:BatchHashTableBuild
接收行、批输入,输出为 批,这个算子还带有 bitmap(Bloom filter),在scan 的早期阶段过滤更多的行
同时还引入了一个物理算子,实现行、批转换,还可以过滤掉不需要的转换

batch 与 row 看作一种 physical property:

  • 所有 batch 算子都要求它的子节点是 batch 的
  • 所有 row 算子都要求它的子节点是 row 的
  • HashJoinBuild 是独立的一个算子,所以 batch 的 HashJoin 只会要求 probe-side 是 batch 的

snowflake 模型下启发式地构建 join order 的算法

  • 这个算法会尽可能将 dimension table 作为 HashJoin 的 build side
  • 从而构建出 bitmap 下推给 fact table 的 Index Scan(假设含有列式索引)
  • 减少 Index Scan 输出的数据量

实验

数据压缩比例如下

Table 2: Column store compression on real data sets

四个 TPC-DS 查询

  • 一个事实表 + 两个维度表的星型查询
  • 下钻查询
  • 单表的聚合查询
  • 带子查询的复杂查询 行存 vs 列存,在温数据的情况下对比,4个 TPC-DS 查询
    Table 3: Observed query times (sec) with warm buffer pool

行存 vs 列存,在冷数据的情况下对比,4个 TPC-DS 查询
Table 4: Observed query times (sec) with cold buffer pool

Q1 的查询计划如下

  • 扫描两个维度表建立 hash-table
  • 然后多个线程扫描多个 catalog_sales 的 segment 列存索引
  • 并行的探测hash 表
  • 最终聚合在每个流上并行完成,最后将结果元组聚集到单个输出流中
  • 这里查询计划说明了 行、批是如何混合完成的,大部分处理是在批下完成的,只有最后的处理时在行下完从,那时只有 5416行

Q3的查询计划

  • 批+行混合模式,跟行模式的查询计划差不多,但性能提高很多
  • 因为使用了批处理
  • 谓词下推过滤,可以减少很多数据扫描

在SQL的Denali版本中不支持直接更新和加载带有列存储索引的表

  • 如果表足够小,可以删除它的列存储索引,执行更新,然后重建索引
  • 于较大的表,可以使用分区加载staging表,用列存储索引对其进行索引,然后将其切换为最新的分区

关于列存的一些实例

关于列存的一些历史

  • 1970年代就有相关研究了,把数据拆分成更小的子集
  • 1975年有论文研究如何分解优化数据为更小的子集
  • 1979年有研究如何在这小文件上做查询优化
  • 1985年研究了如何完全分解存储,其中每个列存储在单独的文件中,也就是列存
  • 沉寂了 20年,到2005年,Stonebraker 发表了 C-Store论文,之后又开始了列存研究的热潮
  • Sybase IQ、MonetDB是最早的纯列式数据库
  • 新玩家包括:Vertica、Exasol、Paraccel、InfoBright、SAND
  • SQL Server是第一个将列存储和处理完全集成到系统中的通用数据库系统
  • Ingres VectorWise是纯列数据库,但是跟 Ingres不兼容
  • Greenplum、Aster Data是面向数仓的,最初是行存,然后增加了列存功能整合进来了

参考