数据库内核月报

数据库内核月报 - 2022 / 01

SQL Server · 引擎特性 · 从SQL Server看列式存储

Author: 柒沐

1. SQL SERVER Column Index存储进展

自2012年以来,SQL Server的Column Index在存储层设计上有了几个大方向上的进展:

  Functional Performance Paper
2012 只读secondary column index 《SQL Server Column Store Indexes》
2014 可更新primary column index;归档压缩,压缩率好一些,但查询慢一些; 《Enhancements to SQL Server Column Stores》
2016 1.可更新secondary column index;2.可以在primary column index上架secondary btree index来做unique check和seek;3.可根据filter针对部分行加secondary column index; 1.Snapshot Isolation;2.Defragment(碎片整理);可以在Replica上访问column index; 《Real-Time Analytical Processing with SQL Server》
2017
2019 可merge多个空洞的row group (Compaction & Flush)

2. Updateable Columnstore Index设计概述

列存和行存不同的点在于数据的物理组织形式,主要体现在以下两点:

  1. 列存数据数据按列分割存放
  2. 列存数据一组连续存放的数据数据量比较大

基于这两点就可以充分发挥基于单列的压缩能力。同时执行从存储fetch数据时,可以精准fetch某一列的数据,memory和IO的利用效率更高。也更适合batch execution,batch execution一般来说有10倍以上的性能提升。

为支持更新,列存也需要索引结构辅助,列存可以用和行存一样的索引组织形式。行存的索引组织形式可以分为:

  1. 非聚簇索引:HeapTable,也就是非聚簇索引(一般是btree)加无序数组
  2. 按PK聚簇索引:
    • Clustered Btree Index
    • LSM

2.1 列式HeapTable

2.2 列式Clustered Btree Index

2.3 列式LSM

2.4 Unordered Array+Delete Map

思路:还有一种更简单粗暴的方式是简单维护按列为单位的无序数组和一个delete map,数据不会按照键值聚簇,写入时直接追加到数组末尾,现在内存中缓存到一个row group的数据后再压缩写盘。但这种方式的更新删除能力很差,需要扫描全表定位出要删除的行,因此只适合于以插入查询为主的数仓场景。 ​

例子:SQL Server Column Index

3. 删除与更新

删除与更新是列式存储的难点。列式存储往往将一大批数据作为一个row group进行压缩再落盘,因此列式存储的删除往往是标记删除,更新是删除加插入,来避免频繁的解压压缩和写放大。

3.1 列式HeapTable

3.1.1 As Primary Index

和行式Heap Table一样我们需要一个额外的索引结构来定位要删除的行号,得到行号后可以通过delete mask或者已删除行号集合来过滤不需要的行。

3.1.2 As Secondary Index

此时列存作为行存主键索引的二级索引,我们不再需要额外的索引结构来定位要删除的行,只需要将行号维护在主索引的记录里,删除时先根据主键在主键索引中定位到行号,然后再通过delete mask或已删除行号集合来过滤被删除的行。SQL Server基于全内存行存表的列存二级索引就是这种实现方式。

3.2 列式LSM

Clickhouse无法支持实时更新,这里就介绍支持实时更新的列式LSM Hologres和TiFlash,并对两者进行一下对比。

3.2.1 Hologres

Hologres支持KV接口和AP查询,存储层类LSM,主键是主键映射记录,二级索引是二级索引列加主键列为key,value为null。和SQL Server一样,主键索引和二级索引都支持行存形式和列存形式。行存形式就是典型LSM架构,

下面主要介绍下列存形式(以主键索引为例)。Hologres的shard file可以理解为RocksDB的sstable,且只是每列的datablock是单独连续存放的。同时有个delete map的LSM组件用于维护delete操作,该LSM的key为shard file的ID,value中包括了bitmap表示该shard file中哪些记录被删除。读取shard file时会根据read sequence产生一个visible bitmap,同时merge delete map中该shard file ID的bitmap生成一个delete bitmap,merge visible bitmap和delete bitmap来过滤不可见和已删除数据。更新时先seek到旧行,然后还原出更新的新行,按照删除流程删除旧行,然后将新行从前台写入。

并且,shard file间不会有primary key的overlap,因此Hologres扫描时不需要对shard file进行归并,只需要根据bitmask过滤,也就可以并行扫描。 ​

image.png

3.2.2 TiFlash

TiFlash的可更新列存引擎DeltaTree设计思路:

  1. 首先数据会按照主键排序来分区,每个分区如下图所示,当分区物理大小超过阈值时会分裂
  2. 更新append到内存的buffer后会flush到delta space中,因此delta分片里的数据是按照append顺序排布的,并非根据主键聚簇
  3. delta分片积累到一定量后会被排序归并到stable space中
  4. 因此扫描是需要归并stable space、delta space以及memory中的数据,由于delta数组组织是无序的,归并前就必须先进行排序,为避免scan前对delta的排序,在内存中维护了一个btree index来维护delta数据的逻辑顺序

image.png

3.2.3 小结

Hologres相比于TiFlash的更新开销更大,但扫描时不需要归并,且可以并行扫描。

3.3 Unordered Array+Delete Map

SQL Server的columnstore index作为主索引或者磁盘行存表的二级索引时就是以这种方式实现的。SQL Server做了几点优化来缓解这种设计的删除劣势:

  1. delta store是内存里的clustered btree index,用来缓存最热的数据,这部分数据删除是update-in-place的
  2. 由于column store只是简单的数组,没有索引用来定位要删除的行,每次删除必须要扫描整个column store,删除效率很低。为此,引入了delete buffer,要被删除的primary key会先缓存在delete buffer,然后批量scan更新到delete bitmap上
  3. scan时就merge rowgroup、delete buffer、delta store三部分的数据。 image.png

4. 列存实现选型

4.1 两大列存场景

4.1.1 HTAP

如果我们需要针对一个现有的行存表上的数据做分析,ETL到data warehouse是最常规的操作模式,但其中有几个挑战点:

  1. Complexity: 需要定期将增量数据从TP ETL到warehouse,这个增量判断比较麻烦
  2. Cost: 这个ETL有额外的通道开销,比如阿里的DTS
  3. Data Latency: 分析至少要delay一个ETL的时间

这时我们可以选择在现有的行存表上加一个secondary column index支持实时的AP分析。secondary column index和普通的二级索引一样,会跟着primary index保持实时更新。 这种方式的代价是多了一份列式存储数据,但由于列式存储的压缩能力强很多(压缩率基本在10倍以上),column index这份额外的空间开销不是1倍,几乎只是十分之一。带来的优势是:

  1. 不需要ETL,列存数据基本可以认为是实时同步的
  2. 甚至我们可以把行存数据和列列存数据放在不同的节点上,来进一步地隔离TP更新任务和AP分析任务的资源,比如SQL Server可以在Replica上跑AP分析,Oracle在standby上跑AP分析。

列存二级索引与普通行存二级索引的区别? 列存二级索引适合scan,不需要保序,maintain cost也更小一点,行存二级索引则更适合seek。

4.1.2 Data Warehouse

workload以insert和query为主,更新较少,此时我们可以只用一份columnstore index作为primary index,同时支持大量insert/query和少量更新。

4.2 实现选型

理论上上文介绍的几种列存实现都既可以作为primary index也可以作为secondary index,那么我们针对这两种不同的列存实现要如何进行列存实现的选型(列式HeapTable/列式LSM/无序数组+delete map)。

4.2.1 HTAP

HTAP下会有频繁的数据更新,因此我们可以首先排除无序数组加delete map这种更新能力很差的实现方式。接下来我们就需要对比列式HeapTable和列式LSM。 由于在HTAP场景,列存只是作为行存表的一个二级索引,seek/small range query可以回退到行存上,因此从查询角度上来说我们只需要关注columnstore index的scan能力。 ​

因此,我们只需要从scan/maintain cost两个角度来衡量对比即可:

  1. 全量Scan:取决于列式LSM的删除实现,Hologres的扫描方式和列式堆表基本相同,TiFlash扫描需要归并效率就比列式堆表低。总的而言,列式HeapTable的扫描能力大于等于列式LSM
  2. 基于某个partition/order key的扫描:列式LSM可以按照order key进行聚簇,比如Clickhouse,此时列式LSM只需要扫描一段数据,但列式堆表就需要全量扫描
  3. maintain cost: 列式堆表和列式LSM的maintain cost类似于行式,insert比较多时列式LSM maintain cost更小,删除更新比较多时列式LSM maintain cost更小

小结:除了分区对聚簇有依赖,列式堆表比列式LSM更适合HTAP场景

4.2.2 Data Warehouse

在dataware house场景下,我们以columnstore index为主索引,在这种场景下,我们可以先忽略列存的更新能力的强弱,只要能更新即可,那么这三种实现方式都符合要求。 其次在单一存储上,seek/small range query没有行存能够回退。因此,我们衡量时也需要考虑下seek/小范围查询的能力。因此,我们从seek&small range query/scan/maintain cost三个角度来衡量对比:

  1. seek/小范围查询:列式堆表虽然不是物理有序的,但是是逻辑全局有序的,且由于seek/小范围查询涉及的行比较少,能力上来说列式堆表 >= 列式LSM >= 无序数组+delete map
  2. 全量Scan:不考虑删除更新,全量扫描这三者的能力是一样的
  3. 基于某个partition/order key的扫描:能力上列式LSM > 列式堆表 == 无序数组+delete map
  4. maintain cost:不考虑更新,cost上 无序数组+delete map < 列式LSM < 列式堆表

SQL Server在无序数组+delete map的实现上添加了nonclustered btree index来弥补seek/小范围查询能力。

小结:在data warehouse场景下,数据量比较大,因此需要对数据分区的可能性更大,也就更适合用列式LSM。此外就需要从各个角度衡量综合判断考量。

Reference