列存储

行存储与列存储

传统的关系数据库如 Oracle、DB2、Mysql 等都是将数据以行记录为单位进行组织，所以数据读写操作需要遍历行记录中所有的列，在存储机制上，行存储将行记录中各列的数据值串在一起进行存储，并且先存完第一行再存第二行。而列存储是一种区别于传统行存储的新型读写模式，列存储以列数据集合为单位进行存储，是把一列中的数据值串在一起进行存储，先存完第一列，再存第二列。

如果事实表中有万亿行和数 PB 的数据，那么高效地存储和查询它们就成为一个具有挑战性的问题。维度表通常要小得多（数百万行），尽管事实表通常超过 100 列，但典型的数据仓库查询一次只能访问 4 个或 5 个查询（SELECT * 查询很少用于分析）。譬如下例中它访问了大量的行（在 2013 日历年中每次都有人购买水果或糖果），但只需访问 fact_sales 表的三列：date_key, product_sk, quantity。查询忽略所有其他列。

SELECT
  dim_date.weekday,
  dim_product.category,
  SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
  JOIN dim_date ON fact_sales.date_key = dim_date.date_key
  JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
  dim_date.year = 2013 AND
  dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
  dim_date.weekday, dim_product.category;

在大多数 OLTP 数据库中，存储都是以面向行的方式进行布局的：表格的一行中的所有值都相邻存储。文档数据库是相似的：整个文档通常存储为一个连续的字节序列。您可能在 fact_sales.date_key，fact_sales.product_sk 上有索引，它们告诉存储引擎在哪里查找特定日期或特定产品的所有销售情况。但是，面向行的存储引擎仍然需要将所有这些行（每个包含超过 100 个属性）从磁盘加载到内存中，解析它们，并过滤掉那些不符合要求的条件。这可能需要很长时间。

面向列的存储背后的想法很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如果每个列存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列，这可以节省大量的工作。

行存储与列存储比较

行存储，顾名思义即是将数据是按行存储，行存储的写入是一次性完成，消耗的时间比列存储少，并且能够保证数据的完整性；其插入与更新操作更为容易。但是其缺陷在于建立索引需要花费大量时间和资源，没有索引的话查询会产生大量的 IO，导致效率低下；并且数据库必须被大量膨胀才能满足性能的需求。

列存储，数据按列存储，每一列单独存放，数据即是索引。只查询涉及的列，会大量降低系统 IO,适合并发查询；数据类型一致，数据特征相似，能对数据进行高效压缩，并且非常适合做聚合操作。不过列存储缺乏数据完整性保证，写入效率低，因此不适合频繁的删除与更新操作。

	行式存储	列式存储
优点	数据被保存在一起，INSERT/UPDATE 容易	查询时只有涉及到的列会被读取，投影(Projection)很高效，任何列都能作为索引
缺点	选择(Selection)时即使只涉及某几列，所有数据也都会被读取	选择完成时，被选择的列要重新组装，INSERT/UPDATE 比较麻烦
场景	适合数据存储写入、更新较多的场景，比如 OLTP。当数据量很大时，查询性能远不及列存储	不适合数据频繁写入、更新的场景，主要适合频繁查询的场景，大数据环境下优势更明显，比如分布式实时查询

从写方面来看，行存储的写入是一次完成，也就是说行存储各字段写入是在一次 IO 中完成，而列存储由于需要把一行记录拆分成单列保存，写入次数明显比行存储多，也就是说要多次 IO 才能完成，而字段越多，IO 次数越多，所以在写入上行存储具有明显的优势。再从读方面来看，行存储通常将一行数据完全读出，如果只需要其中几列数据的情况，就会存在冗余列，出于缩短处理时间的考量，消除冗余列的过程通常是在内存中进行的，而列存储读取则只需要读取关心的几个列数据，明显减少了读取的数据量，如果行记录字段越多性能优势就越明显。

另外由于列存储的每一列数据类型是同质的，不存在二义性问题，比如说某列数据类型为整型（int），那么它的数据集合一定是整型数据。这种情况使数据解析变得十分容易，而且因为存储单元的数据结构一致，可以很容易利用差值编码等压缩方法来进行压缩存储而且压缩比可以非常高。相比之下，行存储则要复杂得多，因为在一行记录中保存了多种类型的数据，数据存储不容易压缩，数据解析需要在多种数据类型之间频繁转换，这个操作很消耗 CPU，增加了解析的时间。另外列存储相对行存储更为灵活，逻辑上一行数据可以按列将数据存放到不同的地方，也可以是不同机器上，这样可以在执行查询分析任务时可以按机器节点并行进行查询计算，而行存储不容易进行并行查询，需要一定中间件的支持。

Wide Column | 宽表

BigTable 及其他类似的数据库也提出了所谓宽表（Wide Column）模型的概念，目前很多半结构化或者结构化的数据都是基于该模型。这里以阿里云的表存储为例：

关系型数据库中往往是二维模型，并且包含了固定的 Schema；而上述宽表模型而包含了三个维度，除了标准的行、列之外，其还可以根据时间维度来存放数据，即根据不同的时间戳来保存不同的版本。

Primary Key & Partition Key: 每行都有一个主键，由多个（1-4）列组成。主键使用固定模式定义，主要用于唯一标识一行数据。主键的第一列称为分区键，用于对表进行分区。每个分区都分配给不同的机器进行维护。在同一分区键中，提供了跨行事务。
Attribute column: 除行中的主键列之外的所有列都是属性列。属性列对应于多个值，不同的值对应于不同的版本，行可以存储无限数量的属性列。

我们还可以针对 Attribute Column 中的值定义不同的属性：

生存时间：可以为每个表定义生存时间。例如，如果将生存时间配置为一个月，则将自动清除在一个月之前写入表数据的数据。数据的写入时间由版本确定，版本通常由数据写入服务器端的服务器时间确定，也可以由应用程序指定。
最大版本号：可以为每个表定义每列中保存的最大版本数，用于控制列中的版本数；系统会自动清除超过最大版本数的数据。

列压缩

除了仅从磁盘加载查询所需的列以外，我们还可以通过压缩数据来进一步降低对磁盘吞吐量的需求。幸运的是，面向列的存储通常很适合压缩。它们通常看起来是相当重复的，这是压缩的好兆头。根据列中的数据，可以使用不同的压缩技术。在数据仓库中特别有效的一种技术是位图编码，如下图所示：

通常情况下，一列中不同值的数量与行数相比较小（例如，零售商可能有数十亿的销售交易，但只有 100,000 个不同的产品）。现在我们可以得到一个有 n 个不同值的列，并把它转换成 n 个独立的位图：每个不同值的一个位图，每行一位。如果该行具有该值，则该位为 1，否则为 0。

如果 n 非常小（例如，国家/地区列可能有大约 200 个不同的值），则这些位图可以每行存储一位。但是，如果 n 更大，大部分位图中将会有很多的零（我们说它们是稀疏的）。在这种情况下，位图可以另外进行游程编码，如上图底部所示。这可以使列的编码非常紧凑。

这些位图索引非常适合数据仓库中常见的各种查询。例如：

WHERE product_sk IN（30，68，69）

加载 product_sk = 30, product_sk = 68, product_sk = 69 的三个位图，并计算三个位图的按位或，这可以非常有效地完成。

WHERE product_sk = 31 AND store_sk = 3

加载 product_sk = 31 和 store_sk = 3 的位图，并逐位计算 AND 这是因为列按照相同的顺序包含行，因此一列的位图中的第 k 位对应于与另一列的位图中的第 k 位相同的行。

对于不同种类的数据，也有各种不同的压缩方案，譬如 Cassandra 和 HBase 有一个列族的概念，他们从 Bigtable 继承。然而，把它们称为面向列是非常具有误导性的：在每个列族中，它们将一行中的所有列与行键一起存储，并且不使用列压缩。因此，Bigtable 模型仍然主要是面向行的。

内存带宽和向量处理

对于需要扫描数百万行的数据仓库查询来说，一个巨大的瓶颈是从磁盘获取数据到内存的带宽。但是，这不是唯一的瓶颈。分析数据库的开发人员也担心有效利用主存储器带宽到 CPU 缓存中的带宽，避免 CPU 指令处理流水线中的分支错误预测和泡沫，以及在现代中使用单指令多数据（SIMD）指令 CPU。

除了减少需要从磁盘加载的数据量以外，面向列的存储布局也可以有效利用 CPU 周期。例如，查询引擎可以将大量压缩的列数据放在 CPU 的 L1 缓存中，然后在紧密的循环中循环（即没有函数调用）。一个 CPU 可以执行这样一个循环比代码要快得多，这个代码需要处理每个记录的大量函数调用和条件。列压缩允许列中的更多行适合相同数量的 L1 缓存。前面描述的按位“与”和“或”运算符可以被设计为直接在这样的压缩列数据块上操作。这种技术被称为矢量化处理。

Spark MaxCompute

这里以 Spark MaxCompute 为例，阐述列存储模式的压缩与检索技巧，经过字典表进行数据压缩后，表中的字符串才都变成数字了。正因为每个字符串在字典表里只出现一次了，所以达到了压缩的目的:

在查询过程中，查询引擎仅去字典表里找到字符串对应数字(只进行一次字符串比较)，然后用数字去列表里匹配，匹配上的位置设为 1；把不同列的匹配结果进行位运算得到符合所有条件的记录下标，使用这个下标组装出最终的结果集。

列存储中的排序顺序

在列存储中，存储行的顺序并不一定很重要。按插入顺序存储它们是最简单的，因为插入一个新行就意味着附加到每个列文件。但是，我们可以选择强制执行一个命令，就像我们之前对 SSTables 所做的那样，并将其用作索引机制。

注意，每列独自排序是没有意义的，因为那样我们就不会知道列中的哪些项属于同一行。我们只能重建一行，因为我们知道一列中的第 k 项与另一列中的第 k 项属于同一行。

相反，即使按列存储数据，也需要一次对整行进行排序。数据库的管理员可以使用他们对常见查询的知识来选择表格应该被排序的列。例如，如果查询通常以日期范围为目标，例如上个月，则可以将 date_key 作为第一个排序键。然后，查询优化器只能扫描上个月的行，这比扫描所有行要快得多。

第二列可以确定第一列中具有相同值的任何行的排序顺序。例如，如果 date_key 是图中的第一个排序关键字，那么 product_sk 可能是第二个排序关键字，因此同一天的同一产品的所有销售都将在存储中组合在一起。这将有助于需要在特定日期范围内按产品对销售进行分组或过滤的查询。

排序顺序的另一个好处是它可以帮助压缩列。如果主要排序列没有多个不同的值，那么在排序之后，它将具有很长的序列，其中相同的值连续重复多次。一个简单的运行长度编码可以将该列压缩到几千字节：即使表中有数十亿行。

第一个排序键的压缩效果最强。第二和第三个排序键会更混乱，因此不会有这么长时间的重复值。排序优先级下面的列以基本上随机的顺序出现，所以它们可能不会被压缩。但前几列排序仍然是一个整体。

几个不同的排序顺序

这个想法的巧妙扩展在 C-Store 中引入，并在商业数据仓库 Vertica 中被采用。不同的查询受益于不同的排序顺序，为什么不以相同的方式存储相同的数据呢？无论如何，数据需要复制到多台机器，这样，如果一台机器发生故障，您不会丢失数据。您可能还需要存储以不同方式排序的冗余数据，以便在处理查询时，可以使用最适合查询模式的版本。

在一个面向列的存储中有多个排序顺序有点类似于在一个面向行的存储中有多个二级索引。但最大的区别在于面向行的存储将每一行保存在一个地方（在堆文件或聚簇索引中），二级索引只包含指向匹配行的指针。在列存储中，通常在其他地方没有任何指向数据的指针，只有包含值的列。

写入列存储

这些优化在数据仓库中是有意义的，因为大多数负载由分析人员运行的大型只读查询组成。面向列的存储，压缩和排序都有助于更快地读取这些查询。然而，他们有写更加困难的缺点。

使用 B 树的更新就地方法对于压缩的列是不可能的。如果你想在排序表的中间插入一行，你很可能不得不重写所有的列文件。由于行由列中的位置标识，因此插入必须始终更新所有列。

幸运的是，本章前面已经看到了一个很好的解决方案：LSM 树。所有的写操作首先进入一个内存中的存储，在这里它们被添加到一个已排序的结构中，并准备写入磁盘。内存中的存储是面向行还是列的，这并不重要。当已经积累了足够的写入数据时，它们将与磁盘上的列文件合并，并批量写入新文件。这基本上是 Vertica 所做的。

查询需要检查磁盘上的列数据和最近在内存中的写入，并将两者结合起来。但是，查询优化器隐藏了用户的这个区别。从分析师的角度来看，通过插入，更新或删除操作进行修改的数据会立即反映在后续查询中。

最近更新于 0001-01-01