论文翻译-The-Design-and-Implementation-of-Modern-Column-Oriented-Database-Systems

阅读更多

摘要

近期，我们对列存储数据库系统（column-oriented database systems），或者称为列存储（column-stores），做了一个调研，这些系统最显著的特征就是：一个数据表中的不同属性分别存放在不同的文件或存储区域中。伴随着海量数据的扫描、聚合需求的激增，列存储数据库在近几年又重新进入了人们的视野中。列存储的最主要优势在于：仅需要访问、读取查询条件中的那些属性。特别地，我们重点关注三种比较流行的原型，分别是：MonetDB[46]、VectorWise[18]、C-Store[88]。一些著名的商业化列存储系统的实现以这些原型作为理论基石。我们会讨论这三种原型的相似性与差异性，以及针对compression、late materialization、join processing、vectorization、adaptive indexing这几个方面的架构特点

1 Introduction

物理介质（例如磁盘）上的存储效率，以及数据在存储介质与CPU寄存器之间拷贝移动的速率，直接关系到数据库的性能。出于这个原因，数据库社区长期以来都在探索物理存储的不同方案，包括sophisticated indexing（复杂索引），materialized views（物化视图）以及垂直分区或者水平分区

近几年，列存储重新火了起来。早期有学术影响力的系统包括：Monet DB[46]、VectorWise[18]、C-Store[88]。知名商业化列存储系统包括Sybase IQ[66]。VectorWise以及C-Store分别演化成了商业化系统Ingres VectorWise[99]以及Vertica[60]。到2013年底，所有主要供应商（包括IBM[11]、微软[63]、SAP[26]以及Oracle）都遵循了这一趋势，并在其数据库系统产品中提供了列存储实现，突出了这项技术的重要性

列存储系统将数据库划分成由独立存储的列值的集合。将每个列独立存储在磁盘上，列存储系统在执行查询任务时，仅需读取所需的列，而不用读取整行（包含不需要的字段，且需要在返回结果前在内存中进行过滤和丢弃）。一个显而易见的优势就是，列存储可以大大提高I/O以及内存的使用效率。在列存储的性能优化这一方向上，可以进行大量的数据库架构方面的创新。在这篇文章中，我们将讨论现代化的列存储系统，包括它们的架构、演进方向以及在数据分析上的优势

数据布局与访问模式。Figure 1.1说明了列存储以及传统行存储（row oriented databases/row stores）在物理存储上的差异。上图表明，存在三种方式来存储一张包含多个属性的sales数据表。在两种列存储的方法中（Figure 1.1(a)和Figure 1.1(b)），每个列独立地存放在不同的存储单元中。数据通常以数据块的形式在存储介质中进行读写操作，而列存储意味着某个存储单元的每个数据块都包含着sales数据表中的某个特定的列值。在这个例子中，如果要查询某个产品在7月的销量，那么仅需访问prodid以及date这两列，因此只有这两列相关的数据块会被读取（后面会讨论Figure 1.1(a)和Figure 1.1(b)这两种存储方式的差异）。而对于行存储（Figure 1.1(c)），所有的数据都被存放在同一个存储单元中，这就意味着，每个数据块都包含sales数据表的所有列。因此在查询时，没有办法仅仅读取所需的列值，而不得不读取整行数据。数据传输效率通常是数据库系统中的主要性能瓶颈，与此同时，数据库表结构的设计也变得越来越复杂，通常一个大表会包含几百个属性，针对这种场景，列存储系统在数据查询中将会表现得异常优异

权衡。数据的访问模式决定了如何选择列存储和行存储。假设数据存储在磁盘上。若需要查询单条记录（每条记录都包含了全部的属性值），列存储通常会花费数倍于行存储的时间（每个属性至少得访问一个存储单元，具体数量取决于属性的数量）。若需要查询多条纪录的某几个属性，列存储可以读取大量整列，将搜索分摊到到不同的列。在传统的行存储中，作为对比，若需要查询单条纪录，由于数据是连续存储的，通常只需要一次读取便可读取到所有的列值，并且相比于读取相关列值，读取所有列值带来的整体开销相比于搜索时间来说是微不足道的。然而，当查询的记录不断增大时，读取更多列值带来的整体开销将会逼近甚至超过搜索时间，此时列存储在性能上会比行存储更好。由于这种原因，列存储更适用于数据分析性应用，这些应用通常会查询扫描单表并计算它们的聚合或其他统计信息

列存储架构。尽管最近的列存储系统采用了与早期垂直分区研究提案[12, 22, 55, 65]中的概念相似的高级概念，但它们包含了许多超出垂直分区以外的架构特性，旨在最大限度地提高列存储系统的性能。本文的主要目标是调研近些年的研究成果，架构演进趋势，以及优化手段。我们主要关注以下几个方面

• Virtual ID[46]：在列存储中表示列的最简单方法就是将元组标识符（例如，数字主键）与每一列相关联。显式地存储此元组标识符会使得磁盘数据膨胀，从而降低I/O效率。相反地，现代列存储系统使用元组标识符的偏移量来作为该列的虚拟元组标识符，从而避免额外的存储（Figure 1.1(a)和Figure 1.1(b)）。在一些列存储系统中，每个属性都存储为固定宽度的密集数组，并且每个记录都存储在表的所有列中的相同（数组）位置。另外，宽度固定的列仅需要通过偏移量就能实现数据访问，极大地简化了数据访问的过程。举个例子，若要访问列A的第$i$个列值，只需要访问起始位置为$startOf(A) + i * width(A)$的数据，不需要其他的间接引用。然而，正如我们稍后将在第4节中详细讨论的那样，相比于行存储而言，列存储的一个优势就是提高了压缩率，许多压缩算法以非固定长度的方式压缩数据，因此数据不能简单地存储在数组中。一些列存储系统会放弃部分压缩性能从而保持固定宽度的特性，另一些列存储系统仍然利用非固定宽度的压缩算法
• Block-oriented and vectorized processing[18, 2]：通过在算子间传递缓存快大小的元组块（cache-line sized blocks of tuples），算子同时并发操作多个值而非使用传统的元组迭代器，列存储可以显著提高缓存利用率和CPU使用效率。使用向量化CPU指令对这些值块进行选择、表达式和其他类型的算术运算可以进一步提高吞吐量
• Late materialization[3, 50]：Late materialization或者late tuple reconstruction（把从各个列中获取的数据重新组装为行的过程称之为tuple construction）指的是延迟元组的物化。事实上，针对某些查询，列存储可以完全避免这种物化行为。因此，Late materialization意味着列存储不仅一次存储一列数据，而且还以列格式处理数据。举个例子，选择算子使用for循环，一次扫描一列，并以缓存/CPU友好的格式输出（与首先构造包含当前查询所需的所有属性的元组，并将它们提供给传统的行存储选择算子相反，该算子只需要访问这些属性中的一个）。通过这种方式，列存储能极大的提升内存利用率（避免浪费内存资源）
• Column-specific compression[100, 2]：通过对每一列使用针对该列最有效的压缩算法，能够大幅度地降低整体的磁盘使用量。由于列存储的特性，即便利用简单的压缩算法也能得到较好的压缩率
• Direct operation on compressed data[3]：许多现代的列存储系统仅在必要时对数据进行解压缩，理想情况下，直到结果需要呈现给用户时才进行解压缩。处理压缩数据能够极大地提升内存利用率，这也是主要的瓶颈。Late materialization允许数据以压缩的形式存储在内存中，而创建更宽的元组通常需要先进行解压缩
• Efficient join implementations[67, 2]：由于列值独立存储，类似于半连接（semi-join[13]）的连接策略也是可能的。对于某些特定的连接类型，其性能远远优于传统的hash join或merge join
• Redundant representation of individual columns in different sort orders[88]：根据特定属性排序的列可以在该属性上更快地过滤。通过存储按不同属性排列的多个副本，可以大幅度地提高性能。C-Store将按照某个特定属性排序的不同列称为投影。Virtual ID是每列基于自身的投影。此外，列值有序存储还能进一步提高压缩率
• Database cracking and adaptive indexing[44]：Database cracking避免排序整个列。具有cracking特性的列存储可以自适应地以及增量地对列进行排序（排序这一结果是作为查询的副作用），workloads无额外的开销。每个查询操作都可能会重组对应的列，从而加速后续查询的速度。定宽列存储能够加速列重组的速率，同时向量处理意味着我们可以一次性有效地重组整个列，从而使得自适应索引成为现代列存储架构的重要特性
• Efficient loading architectures[41, 88]：最后，列存储的一个问题是它们的加载和更新速度可能比行存储慢，这是因为列存储中，每个列是单独存储，一行数据的写入要分别写入不同的列存储单元中，以及数据是以压缩的形式存储。由于加载性能可能是数据仓库系统中的一个重要问题，因此优化的加载器很重要。例如，在C-Store系统中，数据首先被写入一个未压缩的，写优化的缓冲区中（WOS），后续再进行批量的压缩和写入磁盘。这种方法避免了对每个属性、每行进行一次磁盘搜索，并且不必将新数据插入压缩列中；而是一次写入和压缩许多记录

上述特性是列存储所特有的吗？上面讨论的这些特性以及概念，稍加改变便也应用到行存储系统当中。事实上，大部分设计特征都受到了早期针对行存储研究的启发。多年来，学术界和工业界在传统的行存储领域，通过一些附加设计达到了相似的效果。这些附加设计旨在不干扰行存储的基础架构

举个例子，IMB DB2中的EVI功能早在1997年就允许数据以列的方式进行存储[14]。相似地，过去针对fractured mirrors[78]的研究提出系统存储数据的两个副本，一个副本以行的形式存储，另一个副本以列的形式存储，或者更复杂的存储形式，例如PAX[5]，每个关系元组都像普通行存储一样存储在单个页中，但是每个页内部都按列进行组织，这种方式对磁盘I/O并无益处，但是会降低数据在磁盘、主存、和CPU寄存器之间的传输。传统数据库的索引技术也与Late materialization有异曲同工之妙，它允许算子在某一个时刻仅处理部分相关的数据，能够更好地优化内存使用。现代索引指导工具[21]，总是尝试提出一套“覆盖”索引，它指的是一组索引，在理想情况下，任何查询操作都可以使用到这些索引，从而避免直接访问数据（行存储）。早期的系统，例如Model 204[72]严重依赖位图索引[71]来降低I/O以及处理成本。与向量化（vectorization）类似的概念最早出现在行存储中。另外，压缩技术也是最早出现在行存储中[30, 82]，同时还研究了一些设计原则，例如尽可能晚地解压缩数据[30]以及同时压缩数据以及索引[31, 47]等

本文对于列存储的贡献是（除了提出新的数据存储和访问技术）：一种全新的为上述分析型应用设计的架构。从零开始，我们可以毫无顾忌地将这些理念、想法推向极致，而无需担心与传统设计的兼容性。在过去几年中，这些设计理念的一些变体各自被独立地试验过，主要集中在传统行存储的原型设计。相比之下，从数据库存储开始，沿着技术栈往上，包括查询执行引擎和查询优化器，列存储系统从设计上与传统的行存储系统存在巨大差异，因此在数据库的各个方面，能够在创新的同时最大限度地发挥这些想法的好处。我们会在4.9节重新讨论行存储与列存储

为了说明列存储和这些优化的好处，我们简要总结了最近一篇论文[1]的结果。在这篇文章中，我们比较了学术原型C-Store以及一个商业化行存储系统。我们研究了各种列存储优化对SSBM[73]（TPC-H数据仓库基准测试的简化版本）的整体查询性能的影响。Figure 1.2显示了基准测试中规模为10的数据库（6000万个元组）中所有查询的平均运行时间。左边的条形图显示了C-Store中各种优化手段的性能增益。baseline代表包含所有优化项，需要花费4s来响应所有的查询，而不含所有优化项的需要花费40s来响应所有的查询。右边的条形图显示了传统的商业化行存储系统。基于这些结果，可以发现经过充分优化的列存储系统的性能是传统商业化行存储系统性能的5倍。但是未经过优化的列存储系统的性能要落后于行存储系统，其表现较差的可能原因是SSBM基准测试使用了相对较小（列少）的表格，因此列存储所带来的的增益也会被削减。在大多数的现实系统中，列的数量会比较大，因此，列存储带来的性能增益会更加显著

尽管比较成熟的商业系统和学术原型之间的绝对性能数字很棘手，但这些数字表明，未优化的列存储与选择大部分列的查询提供了与行存储系统相当的性能，并且前面提到的优化项可以带来非常大的性能提升

在本文的剩余篇幅中，我们会展示上述架构创建如何带来巨大的性能提升。特别地，我们会详细的讨论C-Store、MonetDB、VectorWise，介绍他们的异同点，以及三种架构的核心创新点

在下一节中，我们追踪了数据库文献中垂直分区和列存储系统的演变，讨论面向列的架构更适用于分析型场景这一技术趋势。在第3节和第4节中，我们将介绍C-Store、MonetDB、VectorWise的顶层架构以及详细设计，以及一些商业化实现。最后在第5节，我们讨论未来的发展趋势以及进行总结

2 History, trends, and performance tradeoffs

尽管列存储技术在1970年就已问世，但是直至2003年，列存储相关的研究才被大家认可，商业化列存储才开始出现。在本小节中，我们将追踪列存储的发展历史，技术以及应用的发展趋势。最后总结了最近关于列存储以及行存储之间基本性能如何权衡的研究结果

2.1 History

列存储技术的起源可以追溯到1970年代，那时转置文件（transposed files）刚刚问世[65, 12]。TOD（Time Oriented Database）是一种基于转置文件，专为病例管理而设计的系统[90]。最早出现的与现代列存储系统类似的系统叫做Cantor[55, 54]。它具备整数压缩技术，包括zero suppression、delta encoding、RLE (run length encoding)以及delta RLE，所有这些技术都应用在现代的列存储系统当中（我们会在后续小节中详细讨论这些技术）。使用动态规划算法选择压缩方法和相关参数

紧跟着转置文件的研究热潮，又兴起了针对表属性类聚的垂直分区技术的研究。于此同时，行存储技术成为了关系型数据库的架构标准。页内存储的典型实现是slotted-page approach，如Figure 2.1左半部分所示。这种存储模型被称为是N-ary Storage Model（NSM）。1985年，Copeland、Khoshafian共同提出了NSM的替代方案Decomposition Storage Model（DSM），这是列存储的前身[22]，如Figure 2.2右半部分所示。对于许多人来说，这项工作标志着行存储和列存储的第一次全面比较。在随后的20年间，术语NSM以及DSM更常用于替代行存储和列存储这两个术语。在DSM中，表的每一列都单独存储，并且对于列中的每个属性值，存储surrogate key（类似于记录id）的副本，如Figure 1.1(b)。由于surrogate key冗余存储，因此相比于NSM需要更多的存储空间。以与原始表相同的顺序存储每一列（在surrogate key上使用聚集索引），作者提议为每列的属性存储一个非聚集索引，从而提供可以将任何属性快速映射到surrogate key的能力

一项分析（基于当时可用的技术）表明，当仅查询几列时，DSM的扫描性能优于NSM，但是以额外的存储空间为代价。当查询的列的数量增多时，DSM的性能逐渐下降，作者重点介绍了DSM简单性和灵活性方面的优势。他们推测基于DSM的存储的物理设计决策会更简单（因为不需要做索引创建的决策），并且更容易构建DSM的查询执行引擎。最早的DSM论文并没有涉及压缩算法，也没有评估除了扫描算子外的其他算子的优势。后续论文侧重于研究DSM架构之上的算子的并行性[59]，而随后对连接和投影索引的研究[58]则进一步加强了DSM相对于NSM的优势

尽管上述研究尽可能地围绕着DSM指出了列存储相比于行存储的优势，直到很久以后，大约在2000年左右，技术和应用层面的发展趋势才为列存储技术的发展铺平了道路

2.2 Technology and Application Trends

就其核心而言，关系数据库管理系统的基本设计至今仍与1980年代开发的系统非常接近[24]。然而硬件确发生了翻天覆地的变化。在1980年，Digital VAX 11/780具有1 MIPSCPU、1KB高速缓存、8 MB最大主内存、1.2 MB/s传输速率和80MB容量的磁盘驱动器，标价25万美元。而到了2010年，服务器的CPU通常快5000到10000倍，更大的缓存和RAM大小，以及更大的磁盘容量。硬盘驱动器的磁盘传输时间提高了大约100倍，平均磁盘磁头寻道时间提高了10倍（30毫秒与3毫秒）。这些趋势的差异（10000倍与100倍与10倍）对数据库的性能产生了重大影响

磁盘容量增长与磁盘传输和磁盘寻道次数的性能提升之间的不平衡可以通过两个指标来查看：a) 每个可用字节的传输带宽（假设整块磁盘都被占用），多年依赖已经降低了2个数量级；b) 顺序存取速度与随机存取速度之比，多年依赖已经提高了1个数量级。这两个指标清晰地表明，DBMSs不仅需要尽可能避免随机磁盘I/O，而且最重要的是要保留磁盘带宽

随着整个内存层次结构的随机访问变得越来越昂贵，查询处理技术开始越来越依赖于顺序访问模式，大多数DBMS架构都是围绕着应该尽可能进行完全顺序访问的前提而构建的。然而，随着数据库的体积增大，扫描变得越来越慢。大多数数据库供应商并不认为DSM是NSM的可行替代品，这是由于早期DSM实现中发现的局限性[22]，其中DSM仅在查询访问很少的列时优于NSM。为了让基于列 (DSM) 的存储方案优于基于行 (NSM) 的存储方案，它需要有一种快速重建元组的机制（因为DBMS的其余部分仍将在行上运行），并且还需要能够在访问磁盘上的多个列时分摊磁盘搜索的成本。高性能CPU能够实现前者，而大容量的内存能够实现后者

尽管现代列存储因能够高效地处理基于磁盘的数据而广受欢迎，在1990年代，列存储技术广泛用于内存系统。在90年代末期，人们对研究内存数据布局以解决CPU和内存之间日益增长的速度差异产生了浓厚的兴趣。大约在1980年代，内存访问与指令执行的速度相当。但是到了90年代中期，内存访问的周期是指令执行周期的数百倍。MonetDB[46]是学术界第一个主要的列存储项目。MonetDB最初的动机，是为了解决内存带宽问题，同时通过避免表达式解析提高计算效率[19]。一种新的查询执行代数是在类似于具有Virtual ID的DSM的存储格式上开发的。随后的研究，研究了缓存敏感查询处理算法（MonetDB的全面介绍在第3.2 节之后）

PAX（Partition Attributes Across）采用混合NSM/DSM方法，其中每个NSM页面组织为一组迷你列[5]。它延续了NSM的I/O模式的同时优化了缓存和RAM之间的通信（seeking to obtain the cache latency benefits identified in Monet without the disk-storage overheads of DSM with its explicit row IDs）。后续的项目包括data morphing[39]（PAX的动态版本）、Clotho[84]，研究了采用scatter-gather I/O的自定义页面

Fractured Mirrors[78]利用镜像来提高可靠性和可用性。它的思路是，一份数据以NSM的格式存储，另一份数据以DSM的格式存储，因此，能够同时得到两者的优势

大约在1996年左右，第一个商业化的列存储系统SybaseIQ[28, 29, 66]问世，展示了压缩的，面向列的存储能够为多种分析型应用带来好处。尽管它在商业上获得了成功，但是它未能吸引其他数据库供应商或者学术界的关注，可能原因包括，由于它进入市场为时过早，有利于列存储的硬件进步（触发数据库架构创新），例如大容量内存、SIMD instructions，在当时并未问世；也可能是因为它缺乏一些架构创新，后来证明这些创新对于列存储的性能优势至关重要

行业中一些值得注意的例子包括IBM BLU[79]，它起源于IBM Blink项目[11]，主要在提供与处理压缩列的能力紧密集成的架构上进行创新，以及存储数据的SAP HANA[26]，它以行格式和列格式将在线分析处理和在线事务处理结合在一个系统中。此外，微软很快就对SQL Server行存储的架构进行了扩展，带来了面向列的存储、向量化处理和压缩等功能[62, 61]。最初列存储仅用于辅助加速器架构，例如列索引[62]，但是后续的版本提供了更通用的架构，它允许以列的形式存储基础数据

2.3 Fundamental Performance Tradeoffs

尽管DSM使得快速扫描单列成为可能，但是扩展到扫描多个列，甚至扫描全表，其性能远远落后于NSM。这是由于多列的元组重建、更多的磁盘访问、处理无关信息等会带来大量的性能开销。为了使得列存储能够获得与行存储相当的性能，需要在DSM的各个工作负载上都保持良好的性能，包括查询多列甚至整行的这种情况。随着CPU处理速度的增长远远大于磁盘带宽的增长，以及在软件层面针对I/O的优化，使得列存储在读取多列时的性能慢慢接近行存储。这一点，在过去十年中，被许多学术研究所证明

• 在Fractured Mirrors[78]中，作者针对DSM提出了多个优化项。每个DSM列以B-tree的方式存储，每个叶节点包含了列的所有属性值。此外，淘汰了每列的ID属性，将开销分摊到多个不同的列中（Graefe还提出了一种在B-tree中高效存储列值的方法[33]），以及使用了基于块的元组重建
• 在文献[40]中，作者基于一种全新的实现（一个独立的存储管理器，读优化的存储方式，大型预选单元来隐藏跨列的磁盘查找），对比了列扫描器和行扫描器。在2006年，在查询整行数据的情况下，列存储扫描的速率仅比行存储慢20-30%
• 最后，在文献[89]中，作者提出了闪存固态存储器是数据库系统的主要介质，并证明了基于列的存储模型对磁盘存储的有效性。由于SSD的随机访问速度远优于HDD，列存储在这种介质上，进行整行全表扫描的I/O开销与行存储相当

Figure 2.2将上述研究成果都整合到一张图中。展示了列存储（或称DSM）的扫描时间与行存储的扫描时间（I/O开销是个常量）在不同投影比例（读取元组/列的百分比）下的对比。DSM的基线取自于2001年的参考文献[5]，该基线同样被PAX以及NSM的性能对比所引用。随着时间的推移，在最差的情况下（投影比例是100%），列存储的性能开销在慢慢逼近行存储的性能开销。当存储介质是SSD时，列存储的性能不再若于行存储，当仅查询少数列时，列存储的性能要远远优于行存储。如果选择性很高，那么列存储可以最大限度地减少它们创建的中间结果的数量，否则会产生显着的开销

3 Column-store Architectures

在本小节中，我们将讨论C-Store、MonetDB以及Vector-Wise三种研究原型的顶层架构。这些架构衍生出了现代列存储系统的主要设计原则。本文高度赞扬这些系统的设计，大部分设计原则三种系统都遵循，少部分设计原则是各自系统所独有的。下一节更详细地讨论这些特性和设计原则，并提供查询处理和性能示例

3.1 C-Store

在C-Store中，数据在磁盘中的主要组织形式是一组列文件。每个列文件包含了某列的所有数据，这些数据是通过一些列压缩算法压缩过的，并且以与列相关联的一些属性排序过后的。这一组文件被称为ROS（read-optimized store）。此外，新数据是通过WOS（write-optimized store）方式存储（数据未压缩，且未分区）。WOS支持高效地加载数据，并且能够分摊压缩和搜索的时间开销。一个被称为tuple mover的进程会定期的将WOS的数据转换成ROS的数据，执行的操作包括排序、压缩、将数据重新写入等等操作

C-Store中的每列，可能会以不同的排序方式存储多次。一组以相同排序方式排序的列，被称为投影（projections）。通常来说，至少包含一个投影（包含所有列）用以响应所有的查询请求。包含少量列，且按照不同排序方式的投影，主要是为了优化热点数据的查询性能。举个例子，在特定时间段内，特定区域每个月的销售数量的查询，可以受益于包含产品id、日期、地域且以地域、时间进行排序的投影。排序能够对相关的记录进行有效的子集化，且可以一次聚集一个月的结果，而无需维护聚合的中间状态。作为对照，在特定时间段内，每个月的销售数量的查询，则可以受益于包含日期且以日期进行排序的投影。Figure 3.1展示了两种不同的投影。在C-Store中，我们使用saleid, date, region | date来表示包含saleid、date、region这三列，且以date进行排序的投影。注意到，这些投影可以包含不同的列，且无需包含所有的列。

C-Store中的每列都是经过压缩处理的，且不同数据可能使用不同的压缩算法。如何选择压缩算法，取决于：a) 数据是否排序；b) 数据类型；c) 该列不同取值的数量。举个例子，product class的可能取值就很少，当数据经过排序后，使用using run-length encoding（RLE）便可对其进行有效压缩。在RLE中，连续X个相同的数值，可以被表示为(X, product class)，而不是X个记录。更多压缩算法的细节将在第4节中进行讨论

C-Store不支持二级索引，但是通过使用稀疏索引（sparse indexes）支持对排序投影的有效索引。稀疏索引是一种基于树的小型索引，用于存储列的每个物理页上的第一个数据。通常来说，C-Store的每个物理页的大小在几兆字节。给定投影中的某个数值，查询会返回第一个包含该值的物理页。然后在物理页中扫描来查询该值。C-Store中另一种相似的稀疏索引以元组的下标来进行排序，当数据以压缩的形式存储，或者存储的是可变长度的属性值时，允许通过元组偏移量来快速地查询某个元组信息

此外，C-Store使用无覆盖（no-overwrite）的存储形式。在这种模式下，更新操作就会被等价表示为先删除再插入，删除操作就会等价表示为在删除列（delete column）中增加一条记录

C-Store中的查询执行过程，同时包含访问ROS以及WOS数据，并整合这两者的结果。在特定时间范围内的查询，需要过滤掉存在于删除列中的数据。因此，C-Store允许查询过去某个时间段的数据（由于数据并未删除，而是记录在删除列中，那么就可以通过比较删除的时间点与查询的时间点来判断数据是否可见）。修改数据库的查询使用传统的两阶段锁定运行。如果只读查询可以容忍读取稍微过时的数据，则可以通过在最近的某个时间执行它们而无需设置锁来运行它们。最后，C-Store查询执行器使用了一系列先进的技术，包括物化技术、列连接技术，批处理技术。这些技术将在第4节中详细讨论

最后，除了完整的垂直分区之外，C-Store被认为是一个无共享的大规模并行分布式数据库系统，尽管学术原型从未包含这些功能（商业版本则包含）。C-Store中的并发设计指的是投影以hash或者range-partitioning的方式散列在不同的节点上，查询尽可能地在每个节点上执行，然后聚合成一个结果并返回。大多数C-Store的并行设计都是基于早期的共享非并行系统的设计，例如Gamma[23]。因此，并行不是这里讨论的重点

3.2 MonetDB and VectorWise

在本小节，我们先讨论MonetDB的架构设计，然后再讨论VectorWise的架构设计

MonetDB。MonetDB是从头开始设计的，专注于在现代硬件上执行高效的分析任务。MonetDB同时将数据存放在内存以及磁盘上，并且使用了批处理以及物化技术。它完全依赖于内存映射文件，避免了管理缓冲池的开销和复杂性。MonetDB与传统的RDBMS在许多方面上存在差异，包括

• 执行引擎，使用a column at-a-time-algebra[19]
• 处理算法，旨在最大限度地提高缓存命中率而非I/O效率
• 索引，这不是DBA的任务，而是作为查询执行的副产品（写查询的人得明白如何利用索引高效地查询数据），即database cracking
• 查询优化，这是在运行时完成的，在查询的过程中会对数据进行一些处理，包括排序等等
• 事务管理，使用显式的附加表以及代数运算实现，因此只读的工作负载可以省略并避免所有事务开销

传统的查询过程采用的是每次一个元组（tuple-at-a-time）、拉模式（pull-based）的方式，每个算子通过调用next()方法从上下游中的相关算子中获取下一个输入元组，并以此方式进行迭代处理。而MonetDB中的每个算子工作在列上。通过这种方式，MonetDB旨在模仿计算机在提升CPU执行效率方面取得的成功，通过在列上的处理模式优化（例如tight loops over fixed-width and dense arrays）获取性能增益。这些优化需要编译技术的支持，通过各种手段从CPU中获取最大的性能，这些手段包括strength reduction（将一个算子替换为另一个低成本的算子）、array blocking（对数组的子集进行分组以增加缓存局部性）以及loop pipelining（将循环映射为流水线的执行方式）。MonetDB的column-at-a-time这一原语，不仅可以使用更少的指令来完成同样的任务，而且由于消除了tuple-at-a-time，指令执行的效率会更高。换言之，就是MonetDB查询计划为CPU提供了更多的动态指令，使得流水线满负荷运行、可以进行分支预测以及提高CPU缓存命中率。并且在编译器的帮助下允许数据库系统从SIMD中获得指示

column-at-a-time处理过程，通过BAT Algebra来实现，允许算子处理一部分BAT并产生新的BAT。BAT代表二进制关联表Binary Association Table，指的是DSM中的<surrogate, value>表。其中surrogate就是Virtual ID，它实际上是列的数组索引，并没有具体化。基础数据以及中间结果都会存储在BAT中，最终结果其实是一组BAT。因此MonetDB将late tuple materialization发挥到了极致。BAT本质上是内存中的（或者内存映射）数组。算子产生或者消费BAT，例如选择算子将一个BAT作为输入，对该BAT中的数据进行筛选过滤，然后产生一个新的包含所有合法元组的BAT作为输出

元组重建的缺失正符合MonetDB的另一个目标，即用一个内部的数据表示形式（即BAT）来处理其他不同模式的数据。MonetDB遵循了frontend/back-end的设计，其中front-end负责维护存储在一些逻辑数据模型中的数据的视图；MonetDB中的front-end适用于存储和查询纯关系型数据，包括面向对象的，XML RDF以及图数据。front-end将终端用户输入的查询语句（SQL、OQL、XQuery、SPARQL）转换成BAT代数，执行计划，并将结果BAT转换成最终的结果。Figure 3.2展示了不同的front-end产生的查询计划都会在back-end中进行执行

BAT代数效率背后的原因是它的硬编码语义，导致所有算子都是无谓词的。作为对照，在传统数据库系统的关系代数中，连接以及选择算子采用布尔表达式来确定哪些元组应该被连接或选择。由于这些布尔表达式，在查询时才能确定，意味着RDBMS必须在选择和连接算子的执行过程中使用一些表达式解释器来对表达式进行解释。这样的谓词不会出现在BAT代数中。因此我们也称其为「零自由度」。零自由度意味着算子将不再需要表达式解释器。因此，所有的BAT代数中的算子的执行代码都是固化的。从而，查询中不同的查询条件将会被映射成不同的算子。MonetDB中表达式解析的粒度发生在column-at-a-time这个维度，因此分摊了解析带来的开销

BAT代数背后的理念也可以解释为：RISC方法在数据库查询语言上的引用。通过简化代数，提供了优化执行效率的可能性

近期的研究表明，通过走极端路线并即时编译代码（即在查询处理期间），可以获得进一步的优势。理由是编译后的代码最适合特定查询的查询模式和数据布局，从而提高扫描密集型工作负载的性能[43, 70]，使用针对这次特定扫描所关联的算子，可以进一步减少函数调用，增加缓存命中率

在执行数据更新时，MonetDB为数据库中的每个基本列都使用了一组pending column。每个更新操作仅影响pending column，也就是说每个更新操作，会转换成针对pending column的操作。每个查询都会从基础列以及pending column中读取数据，并聚合成最终的值。举个例子，当针对X列进行一次过滤动作时，会执行两个算子，其中一个算子针对X列进行过滤；而另一个算子对该列对应的pending column组进行过滤，随后对两个算子的结果进行合并，pending column中的数据会定期的与基础列中的数据进行合并

VectorWise。MonetDB开创了多个列存储的核心设计原则，后续的VectorWise以及C-Store又补充了一些标志性的设计。MonetDB将数据以非压缩的方式存储在磁盘上，BAT代数算子通过内存映射来访问磁盘，不受任何API的阻碍。由于缺少buffer，MonetDB依赖操作系统的虚拟内存访问，系统本身对I/O调度没有绝对控制权。column-at-a-time的另一个缺点是它对中间结果的全物化。举个例子，如果选择算子将全部数据作为一次输入，那么该算子需要一次性物化所有的结果，这会导致额外的开销，特别是处理海量数据的时候。上述缺点综合在一起，就导致了，当MonetDB工作空间（内存等）超过RAM时，就极易发生swap（该操作性能极差）

上述问题被同一个位于CWI的研究小组开发的系统VectorWise[96]所攻克。VectorWise另起炉灶，重新实现一整套系统，以解决MonetDB的缺陷，并提供为现代化硬件量身定制的架构。VectorWise的核心创新点它的向量执行模型。在MonetDB（对中间结果的全物化）以及传统的行存储系统（tuple-at-a-time迭代模式带来的函数开销）之间找到了平衡点。本质上来说，VectorWise一次处理某列的一部分，而不是一次处理整列，或一次处理整行

VectorWise以更加高级的方式执行显式I/O操作，自适应地为并发查询在Active Buffer Manager（ABM）以及Cooperative Scans[98]等方面进行优化。VectorWise提供了一种新颖的更新数据的方法（Positional Delta Trees[41]），以及一种高效率的压缩算法[100]。我们将在下一小节讨论这些细节

3.3 Other Implementations

来自行业的后续设计，基本共享了VectorWise以及C-Store的基本原则（我们将在下一节中详细讨论）。这里有2个在列存储领域，广泛被工业界采纳的核心架构

Columnar Storage Only。第一范式：以列的方式存储数据，但依赖于标准的行存储执行引擎来处理查询。这意味着，每个查询仅访问相关的列，在I/O层面节省了一些开销，但是一旦所有数据到达内存，它就会立刻拼接成N元组并送入经典的行存储引擎。因此，这种设计容易被现有系统所兼容，因为只需要在列存储中读出数据之后，将其映射成元组即可，但是这种方式不能发挥列存储的全部优势。此类设计的典型实现包括Teradata、Asterdata and EMC、Greenplum。这种设计的好处就是它允许更平滑的过度到一个全新的架构中去，并且他允许数据同时以行存储以及列存储的方式存储，且仍然可以由同一个执行引擎处理这两种数据

Native Column-store Designs。第二范式：全方位地接纳列存储这一设计理念。它不仅以列的方式存储数据，而且为column-at-a-time的算子以及延迟物化等技术量身打造了一个执行引擎。然后，这个新的引擎将与传统的行存储引擎集成到一起

IBM BLU/BLINK。第二范式的一个主要例子是源自IBM BLINK项目[11, 52]的IBM BLU[79]。本质上，IBM BLU位于标准行存储DB2引擎的一侧，负责处理部分数据。优化器知道何时将数据输入到传统的标准引擎，以及何时将数据输入到BLU引擎。通过这种方式，查询可以从列存储中获益，反之亦然，实际上查询可以从面向行和面向列的表中扫描数据

除了利用标准的列存储设计，例如延迟物化。IBM BLINK/BLU在压缩领域引入了新的技术。Frequency partitioning[81]在提升压缩的空间效率的同时遵循了列存储的设计原则。总体思路是重新组织列，以减少数据在每个数据页中的变化度。也就是说，通过字典压缩，并通过最小化页面内的可能值来分别压缩每个页面。IBM BLINK/BLU降低了数据表示的成本（每个数据以更少的bit来存储）

Frequency partitioning意味着，与其他系统不同，IBM BLU可以存储非定宽的列。每个页面有独立的字典以及编码长度；在每个页面中，所有的数值/编码都是定长的，但是同一列的不同页面可能采用不同长度的编码。因此，与其他列存储系统相似，IBM BLU可以利用依赖于紧密for循环并且对缓存和CPU友好的算子的设计。只不过在处理不同的页面时，需要进行一些微调。这会导致页面的设计更加复杂一些，它不是纯粹的基于数组的存储，而是需要存储一些额外的信息，包括每个页面独立的字典以及元数据信息（元组与全局顺序的映射关系）。鉴于Frequency partitioning重新组织数据且通常发生在单个列的维度，这意味着，不同的列可能以不同的顺序存储，因此需要有一种方法能够将一张表中的所有列关联起来。我们将在下一节中讨论Frequency partitioning以及其他核心的设计原则

Microsoft SQL Server Column Indexes。这个设计范式，被由Microsoft[62]研发的SQL Server系统所采用。SQL Server对列存储和列执行提供了原生的支持，同时采用了许多列存储中的重要设计，例如向量处理，并且大量利用压缩。SQL Server将这些设计与传统的行存储系统进行了有效的整合，允许根据使用场景灵活地选择使用行存储还是列存储。列可以用作“列索引”，即辅助数据，增强对特定属性的扫描性能，或者它们可以作为扫描密集型场景的首选

4 Column-store internals and advanced techniques

在前几小节中，我们大概掌握了列存储的基本概念，在本小节中，我们将详细讨论列存储的设计细节，不仅局限于数据存储方式以及列存储与传统行存储的差异，而会介绍向量处理（vectorized processing）、延迟物化（late materialization）、压缩（compression）、database cracking等技术

4.1 Vectorized Processing

数据库的相关文献通常会对比两种搜索执行策略，火山式（Volcano-style）的迭代模式[32]（该模式也被称为tuple-at-a-time pipeline），以及全物化模式（full materialization）。在tuple-at-a-time pipeline中，元组在整个查询计划树中流转。算子通过自身的next()方法产生一个新的元组，通过调用子算子的next()来获取当前算子的下一个输入元组。这种方式，除了在软件工程层面来看比较优雅之外，还具有尽量避免物化中间结果的优势

在full materialization方式中，每个算子独立工作，算子从存储介质中（磁盘或者内存）获取输入，并且将结果写入存储介质中。MonetDB是少数使用full materialization的数据库系统，它的BAT代数设计，能够使得算子的执行更加简单以及高效。然而，MonetDB之所以能够高效执行，是因为在执行的过程中产生了大量的中间结果

为了更好地说明上述两种方法的差异，假设有如下的查询$select\ avg(A)\ from\ R\ where\ A \lt 100$。在tuple-at-a-time pipeline中，选择算子会将符合条件的元组，一个个地推送给聚合算子。在full materialization中，选择算子会先扫描整列A，创建一个包含所有符合条件的元组的中间结果，然后将这个中间结果推送给聚合算子。选择算子和聚合算子可以用非常高效的方式来实现，但是由于产了一个巨大的中间结果，会消耗大量的内存，这也是一个问题

我们现在转向另一种由VectorWise开创的方法，叫做vectorized execution，这种方式在tuple-at-a-time pipeline以及full materialization这两种方式之间找到了良好的平衡点。该方法将查询进度控制逻辑与数据处理逻辑分开。抛开控制逻辑来看，vectorized processing与tuple-at-a-time pipeline比较类似，唯一的区别就是next()方法返回的是N个元组还是一个元组。抛开处理逻辑来看，算子的工作方式类似于MonetDB中的BAT代数，一次处理一组数据。因此vectorized execution能够结合两者的优势，既能够避免产生较大的中间结果，也能够提高算子的执行效率

通常来说，vectorized processing中向量vector的大小最好能够匹配L1 cache的容量（在VectorWise中，取值为1000），这样能够避免在整个内存层级结构中进行读写操作。考虑到现代的列存储系统通常在某一个时刻处理某列的一组数据，这意味着，处理过程所包含的vector（输入和输出）以及辅助数据必须要适合L1 cache。例如，具有多个谓词和多列的查询通常会在每一列上单独应用谓词，因此，单列的一个vector必须适合缓存（在4.4节中会详细介绍延迟物化）

vectorized processing有很多优势，我们总结了如下几个主要的优势

• Reduced interpretation overhead。降低表达式解析的整体开销。解释器调用的次数，相比于tuple-at-a-time模式（每个迭代都会执行），会降低到与vector大小相关的一个数值上。在CPU密集型的查询场景中，这种方式能够将性能提高两个数量级
• Better cache locality。VectorWise将vector的容量调整为与CPU缓存相匹配的一个数值，如果vector的容量过大（极限情况下就退化成了MonetDB，容量就是表的大小），会降低查询的速率。不考虑缓存这个因素，vector模式也在tuple-at-a-time processing以及full materialization之间找到了平衡，对vector进行循环处理，根据局部性原理，也能够提高执行令的执行效率
• Compiler optimization opportunities。正如MonetDB中提到的，循环会提高执行效率，且容易被编译器优化，并且通常还会触发编译器生成SIMD指令
• Block algorithms。数据处理算法现在处理N个元组的事实，通常会导致逻辑算法的优化。举个例子，若要检查某些条件（例如输出buffer是否已满），tuple-at-a-time模式下，将会在每次处理元组时都执行一次检查动作，而在vector模式下，算法可以先检查输出buffer是否能够容纳N个结果
• Parallel memory access。在现代CPU上循环执行内存访问的算法可以协助缓存构建。这是因为现代CPU可以在缓存未命中的时候，可以对后续的循环进行推测，并构建缓存。这在tuple-at-a-time架构中是是无法实现的，因为需要通过next()方法调用获取下一个输入，CPU无法提前做出预测。在现代计算机上，生成多个并发缓存是获得良好内存带宽的必要条件。文献[96]表明，可以在所有主要关系数据库算子中向量化内存查找，例如排序、哈希表查找以及哈希表探测。这种查找方式，会导致缓存未命中，在这种场景下，指令通过乱序推测生成的缓存将会使得查询效率比非向量化的内存访问快4倍左右。
• Profiling。相关算子在处理一组元组时，只需要执行一次表达式解析的动作，分析该过程的开销会很小（整体开销会分摊到每个元组上）。这允许向量化引擎提供对CPU周期消耗的详细性能指标
• Adaptive execution。详细的性能指标也可以在运行时，即执行查询的时候采集到。例如，对向量进行算数运算，其中某些谓词只选择向量中值的一个子集，VectorWise会自适应地决定只为选定的元组计算结果，还是为数组中的所有元组计算结果。后者虽然做了一些额外的工作（非匹配的元组也进行了计算），但是循环逻辑是没有条件判断的，这样就为使用SIMD指令提供了可能，整体的效率可能反而比只计算选中的元组来的更高。VectorWise的微自适应机制[77]概括了使用运行时统计来优化查询处理的概念。Multi Armed Bandid算法的作用是在运行时为算子选择最佳的执行路径。在一段时间后，经过数以万计的执行查询任务，几乎尝试了所有的可能路径，因此在后续的执行过程中，总是会选择最优的执行路径。这种方法可以抵抗编译器和编译器标志的差异（通过多次链接同一函数、以不同方式编译、以不同风格提供）以及硬件差异，并且还可以对查询期间数据分布的变化做出反应

vectorized execution主要涉及算子以及元组流在执行树之间的流转。算子中使用的数据布局可以与在存储介质中的数据布局有所不同。尽管vectorized execution是在VectorWise这一列存储系统的上下文中被提出以及使用的，但是这一设计原则可以被应用到行存储系统中，因为它和底层的存储管理并无耦合关系。事实上，上述概念早在1994年就在行存储系统中进行了试验[85]，当时是为了提高缓存命中率和指令命中率。随后进行了更进一步的尝试，在行存储系统上使用了block based query processing[74]以及buffer operators[95]，通过缓存来达到批处理的效果（缓存满了才流转到下个算子中）

文献[101]指出，一个采用了vectorized query execution设计的系统可以通过一个简单的执行器同时支持行存储和列存储。此外，还指出了存储格式对算子的执行效率影响巨大，其中算子特性、硬件参数、数据分布决定了哪种存储格式最有效。通常来说，顺序访问算子（投影、选择）在vertical vectors效果最佳（利用自动内存预取和SIMD）；随机访问算子（hash-joinoraggregation）在blocks of horizontal records效果最佳（cache locality）。由于通过vectorized execution来对水平或者垂直格式的数据进行转换的成本较低的，这使得在执行查询任务时，进行数据转换成为可能（很可能会转换多次），这为查询布局规划的查询优化器开辟了新天地，该优化器应该使用基于成本估计为查询执行计划的每个阶段确定最佳数据布局

4.2 Compression

起初，存储在列中的数据会比存储在行中的数据更容易进行压缩。压缩算法通常更容易压缩信息熵更小的数据（数据的局部性）或者说来自同一列的数据会比来自不同列的数据更具有局部性

Compressing one column-at-a-time。举个例子，假设一个数据表包含客户的一些信息，包括姓名、电话号码、e-mail地址、snail-mail地址等等。行存储，意味着每个数据页包含了姓名、电话号码等信息，我们需要对这些信息一起进行压缩处理。另一方面，列存储，意味着所有的姓名被存储在一起，所有的电话号码被存储在一起。具体来说，某个电话号码肯定是与另一个电话号码更相似，而不是与e-mail地址相似。这就引出了列存储在压缩中的两个优势：第一，当仅存储一个属性的数据时，压缩算法能够使用相同的常见模式压缩更多的数据；第二，相似的数据意味着相似的数据结构，能够达到更好的压缩效果。此外，如果数据是已排序的，那么可以达到更好的压缩效果，例如可以使用RLE压缩算法

Exploiting extra CPU cycles。通常来说，数据库系统的最基础的目标就是高性能，尽可能地快速处理查询请求，而不是追求压缩效率，因为存储介质很便宜且变得愈发便宜。然而，压缩确实能够提供数据库的性能（同时还能降低磁盘空间），因为如果数据是经过压缩的，那么可以降低I/O成本，包括（磁盘到内存、内存到寄存器）。另一个动机是因为CPU的执行效率将远远大于内存的带宽，数据访问相比于过去占用了更多的CPU周期。直觉上来说，这意味着我们有更多的CPU资源可以用于数据的解压缩，但是在过去更倾向于传输未压缩的数据（会占用更多的内存资源）

Fixed-width arrays and SIMD。鉴于性能是数据库系统最重要的指标，这意味着追求压缩率的重量级压缩方案（Lempel-Ziv、Huffman、arithmetic encoding）的优先级要小于牺牲压缩率但是具有较好解压缩性能的轻量级压缩方案。轻量级压缩方案中可以将列值进行等宽压缩的算法会更受到青睐，因为压缩后的数据可以当成一个数组来处理（元素宽度相同）。此类数组的遍历（解压缩）可以利用现代CPU的SIMD指令，可以极大地提高解压缩的性能。利用SIMD指令，我们可以使用一个指令解压缩或者处理多个数据，只要这些数据以定宽的形式存储在数组中，最大程度地提高并行性。由于列存储无论如何都会使用定宽的密集数组，因此在处理未压缩的数据时，也能使用SIMD指令。此外，由于经过了压缩，相比于未压缩的数据，我们可以在相同容量的SIMD寄存器中存储更多的数据，等效于在相同时间内处理了更多的数据。举个例子，现代处理器的SIMD寄存器通常可以存储4个4-byte大小的整数，那么我们在同一时刻可以处理4个未压缩的数据（假设数据大小就是4byte）。若数据经过压缩后大小变为2byte，那么SIMD寄存器便可以容纳8个压缩后的数据，因此提高了并发度

总之，压缩能够极大地提升列存储系统的性能，并且已经作为工业界中不可或缺的一部分。另外，由于压缩节省下来的磁盘空间可以用于存储物化的附属信息或者数据结构等等，例如C-Store中的投影。反过来，这进一步提高了性能，因为现在查询可以享受更好的访问模式。针对列存储中的压缩算法的研究有很多[2, 100, 43, 15]，大部分都由C-Store以及VectorWise开创并由工业界进一步完善。特别地，IBM BLINK项目[11]所提出的frequency partitioning方案更是将压缩和列存储技术紧密的结合在了一起

Frequency partitioning。frequency partitioning的主要动机是提高压缩率的同时，保持定宽数组的特性并可以利用vectorization架构。这要求针对系统架构进行更加紧密的压缩设计。由于frequency partitioning会重新组织列，因此在列的每个页面的熵都比较低。IBM BLINK以数据出现的频率为依据对列进行重组，相同的数据被尽可能地存放在同一个物理页中，这允许系统对每个页面使用更为紧凑的字典进行字典压缩，省下来的空间可以用于存储字典，尽管如此，相比于使用一个全局的字典，仍然能够得到更好的压缩率。举个例子，如果一列中仅有两个不同的数值，针对某个页面（假设都是同样的值），字典仅需占用1个bit。在每个页面中，所有的数值都具有相同的宽度，这允许算子使用CPU以及缓存友好的方式访问数据，就像典型的列存储架构一样，系统以page-at-a-time进行vectorized processing

Compression algorithms。针对列存储中的压缩算法的研究有很多[2, 100, 43, 42, 15]。某些通用算法可以在列存储以及行存储场景中使用；某些特定算法只能在列存储场景中使用，可以压缩同一列中的多个连续值（在行存储中，这是行不通的，相同的列值是不连续存储的）

接下来我们将详细讨论上述压缩算法，包括run-length encoding、bit-vector encoding、dictionary compression、patching

4.2.1 Run-length Encoding

run-length encoding（RLE）适用于经过排序且包含大量重复数据的场景。元数据被编码成一个个三元组，每个三元组可表示为(value, start position, runLength)。举个例子，若一列中的前42个元素都是字母M，那么这前42个元素便可压缩为('M', 1, 42)

在行存储的场景中，RLE只能用于压缩包含大量空白和重复子串的大string。但是在列存储系统中，RLE能够得到更广泛的应用，列值单独存储，且经过排序，会存在大量的重复数据。特别是列值的不同取值仅有少数几个的时候。举个例子，C-Store中的的列在不同投影中以不同的顺序存储，且大多数情况下是经过排序的，因此特别适合于RLE算法

鉴于RLE会将包含相同取值的任意长度的数据块映射成一个三元组，会导致压缩后的数据不是定长的。这意味着我们不能对压缩后的数据采用上面提到过的依赖于定长数据的算法，且在这种情况下，元组重建也会更加复杂。我们需要在磁盘空间以及I/O效率的提升以及该算法对数据分布的影响之间做好权衡

4.2.2 Bit-Vector Encoding

bit-vector encoding经常用于列值空间较小（可取的值比较少）的情况（比如美国的州等等）。但是，如果bit-vector可以被进一步压缩的话，还能适用于列值空间特别大的场景。bit-string（包含的bit数量与列的总大小相同），列中的每个可能的元素都有一个bit-string。如果列中的第i个元素是X，那么将X对应的bit-string的第i个位置的bit置为1，否则置为0。例如，对于列1 1 3 2 2 3 1，由于该列存在3种独立的取值（1、2、3），因此会包含3个bit-string，其中

• 1对应的bit-string：1100001
• 2对应的bit-string：0001100
• 3对应的bit-string：0010010

由于bit-vector encoding的一个变体可用于索引行存储（被称为bit-map indices[71]），在进一步压缩这些bit-map以及进一步压缩对查询性能的影响方面已经做了很多工作[68, 8, 7, 53, 91, 93, 92]

4.2.3 Dictionary

dictionary encoding适用于数据分布异常分散的场景，且同样可以用于string的压缩。将按照列值频率排序的列，构造成一个字典是最简单的形式，字典的值表示关键词在列中的序号。这些整数值可以通过整数压缩算法进行进一步的压缩。全局的字典体积太大，且不同区域的数值分布也不同。针对这种场景，且为了简化更新操作，有时候我们会在数据页的维度使用字典[76, 11]。字典压缩通常有助于将字符串谓词映射成整数谓词来优化查询，在这一点上，全局字典更容易实现

dictionary encoding的好处之一是：它能够将列改造成固定宽度的格式，这是CPU、缓存友好型的访问模式，但是需要在存储收益上作出一些牺牲。事实上，值得注意的是，MonetDB从架构上并未使用压缩（压缩是由VectorWise引入的），但是它仍然使用字典压缩来将string（不定宽）类型的列映射成定宽的列

一个实际的考量点是如何高效地进行字典压缩，这取决于散列速度。一种特别高效的散列技术是cuckoo hashing[97]

4.2.4 Frame Of Reference (FOR)

列值的分布如何含有局部性，那么列值可以表示为一个基础值加上差值。范围可以是整个磁盘也可以是磁盘的一部分。于是列值就映射成了一个很小的值（相比于很大的值来说，仅需要更少的bit即可表示该值，因此可以节省存储空间）。因此FOR就可以表示为基值加上陪集（陪集表示原值与基值的差值构成的集合）的形式[31]。举个例子，1003, 1001, 1007, 1006, 1004可以表示为：1000, 3, 1, 7, 6, 4。其中陪集还可以结合delta coding，当前值可以表示为前一个值的delta，这在前后数值具有强关联的场景下特别有效。一个典型的例子就是经过排序后的整数

4.2.5 The Patching Technique

dictionary以及FOR这两种压缩方案要求列值空间不能太大。如果值域分布及其不均匀，那么我们仍然可以通过这种方式来压缩高频数据

dictionary以及FOR的一种简单扩展思路是：我们允许少部分值不被压缩。这种技术通常会将磁盘分成相邻的两部分，其中一部分用于存放正常压缩的数据（从起始位置，正向移动）；另一部分用于存放未压缩的数据（从末位置，逆向移动）。由于这种存储方式，在进行解码操作的时候，需要判断数据属于哪个部分，这种判断逻辑会降低在现代CPU上的执行效率（因为无法有效地预测执行分支，跳转指令会成为性能开销）

于是，patching方案应运而生[100]，它是通过链表来维护未压缩的数据。于是，在处理正常压缩数据的时候，是无需考虑这些未压缩的异常值的，整个处理过程是平坦的（无分支）。在第二个阶段，会将这个链表中的所有未压缩的值再添加到解压后的数据集中。虽然在处理异常值上做了更多的工作，但是它将处理过程分成两个分支，能够提升解压的效率。这种patching技术还被用于优化block-wise processing

4.3 Operating Directly on Compressed Data

在很多情况下，上面讨论的这些面向列的压缩算法（以及包括一些面向行的压缩算法），都支持在未解压的情况下进行操作。由于直接操作压缩数据能够有效地降低I/O开销。特别地，当压缩算法是RLE时，这种增益会进一步被放大。举个例子，连续1000个42将会被编码成一个三元组（'42', pos, 1000），如果对这1000个数据进行求和运算的话，完全不需要解压缩，会大大降低性能开销。另一个例子是，当dictionary使用了保持比较顺序的编码方式时，这意味着两个原始数据的比较关系，在压缩前后保持不变。因此，选择算子可以直接使用压缩数据来进行比较，在这种方式下，我们只需要对被用于判断条件的值进行压缩即可，例如，判断条件是where x > 100，那么我们只需要将100进行压缩，得到压缩后的数据，这样就可以与所有已压缩的数据进行比较

然而，直接操作压缩数据要求查询执行引擎理解正在被处理的数据是如何被压缩的。这会导致产生一些不可扩展的代码（一个算子需要通过if statements语句或者switch来对不同的压缩算法进行分支处理）。这个问题的一般解决思路是抽象出压缩算法的一般特性，并且让算子针对这些通用特性进行操作（在工程上来说，这种特性以接口的方式体现）。顺着这个思路，就需要研究那些不需要修改查询执行引擎代码的压缩算法

可以在查询执行引擎中添加一个模块来实现，该模块负责维护一个压缩数据块（compression block）（包含了所有经过压缩后的中间数据）。该模块提供一个缓冲区，用于存储压缩数据，并提供多种不同的访问API以供算子使用。压缩数据块无需与实际的存储数据块一一对应。事实上，压缩数据块占用的空间可能非常小（例如RLE）。通常来说，一个存储数据块会被分解成多个压缩数据块。这些压缩数据块会将一些关键属性暴露给算子。举个例子，RLE以及bit-vector会包含列值的一些位置信息，某些聚合算子（例如COUNT算子）可以直接通过直接调用压缩数据块的getSize方法来获取该信息，而无需访问压缩数据块中的数据。相关的属性还包括isSorted()、isPositionContiguous()、isOneValue()、getFirstValue()、getEndPosition()等等，这些属性都有助于算子无需遍历压缩数据，便可直接获取相关信息

通过抽象压缩算法的一些通用接口，允许算子在不改变代码的情况下直接操作压缩数据，这有利于进一步扩展压缩算法的种类。当需要添加一种新的压缩算法时，那么需要实现这些通用接口，包括：a) 数据压缩接口；b) 从存储中扫描压缩数据，并将分解成多个压缩块的接口；c) 迭代并解压数据的接口；d) 查询压缩算法本身的一些相关信息的接口；e) 查询压缩块相关的概要信息的接口（比如长度，第一个元素，是否排序等等）

试验表明，压缩不仅能够节省存储空间，还能大幅度提升性能。如果不直接操作压缩后的数据，很少能够获得三倍以上的性能提升[2]。如果查询执行引擎能够额外感知压缩相关的一些信息，便可能获得超过一个数量级的性能提升，特别是针对那些经过排序的数据

4.4 Late Materialization

在列存储中，逻辑实体的信息是存储在磁盘的多个位置中的（例如名字、e-mail、地址、电话号码等，这些信息都被存储在不同的列中），而在行存储中，这些信息是存放在同一行中的。然而，大部分的查询都会查询多个属性。此外，大多数数据库的输出标准（例如ODBC以及JDBC）以实体的形式返回结果（而不是以列的形式）。因此，在大多数的查询计划中，来自不同列的数据需要被整合成一个数据行。这个将多个列值物化成一行数据，类似的过程被称为元组物化（materialization of tuples），或者被称为元组构建（tuple construction），这也是列存储中最常见的操作

朴素的列存储[38, 40]将数据以列的形式存储在磁盘（或者内存）中，一次特定的查询只需要读取那些与查询相关的列（读到CPU寄存器或者内存中），将这些列值构建成一个元组，然后用面向行的算子来处理这些元组。尽管，在数据分析领域（例如仓储）中，列存储的性能要优于行存储，上述在查询计划的早期进行元组重建的方法存在巨大的优化空间

近期的列存储系统，包括VectorWise、C-Store、Vertica、SybaseIQ，选择保持以列的形式存储数据，并且直接访问这些列值，直至查询计划的最后（极限情况：返回结果的时候，必须进行元组重建操作）。为了达到这样的目的，通常需要构建intermediate 'position' list以匹配已在不同列上执行的操作。举个例子，一个将谓词应用于两列并在应用谓词后投影同一表中的第三列的查询。在列存储中需要用到延迟物化late materialization，谓词将会独立地应用到每个列上，在这个过程中需要用到一个包含列值位置信息（列值在列中的原始的偏移量）的向量。针对不同类型的谓词，这个向量的形式可以是一个简单数组或者bit-string（bit-string中位置为$i^{th}$的值为1代表列中第$i^{th}$个元素被谓词选中）、或者一组区间。将这些位置向量进行交集运算（如果是bit-string，那么可以用位于运算来求交集）来得到最终的位置向量。然后根据这个位置向量，从第三列中取出指定位置的元素

Example。Figure 4.1展示了现代列存储中延迟物化的简单示例。在这里，为了更好地关注于延迟物化技术本身，我们假设中间结果以位置向量的形式存储。且为了易于演示，过程中不涉及到压缩。Figure 4.1中是一个select-project-join查询，该查询需要从两张独立表（R以及S）中的三列作为过滤条件，并且将两张表连接在两列上，随后在其中一张表（R）中进行求和运算。Figure 4.1展示了响应本次查询的多个具体的操作，并显示了MAL代数查询计划，以及MAL算子的行为

延迟物化意味着我们将总是直接操作独立的列。在Figure 4.1中，选择算子独立地过滤每个列，由于每个算子只读取相关的数据，因此能最大程度的利用内存带宽。这样，在Figure 4.1中的Step 1过滤列R.a后，产生了一个包含所有选中列值的位置向量。位置向量可以理解成行id。Figure 4.1所有位置向量都以虚线的形式标出。接着，在Step 2中，我们依据位置向量重新构建R.b。接着，在Step 3中，我们可以根据R.b的谓词来创建另一个中间结果inter2，同样它也是一个位置向量，并且该位置向量会在Step 4中用于重新构建R.c

随后，我们以同样的方式来过滤S表中的S.a，然后提取出S.b用于后续的连接操作。在Step 7中，我们重新调整这个中间结果，以便于后续的连接操作。Step 8中进行连接操作，该操作会产生两个位置向量，便于投影各自表中的列值。在这个例子中，我们只需要R表的位置向量，因此我们在Step 9去除了S表的位置向量，然后用这个位置向量来重新构建R.a，并基于此列执行sum函数。最后，在Step 11中，我们执行聚合函数，得益于column-at-a-time，可以用CPU以及缓存友好的模式访问这些数据，以达到较高的性能

我们将根据位置向量（由前一个算子产生）从列中取值的过程被称为元组重建，该过程在一次查询计划中可能执行多次，最多N-1次。其中，N指的是一次查询中相关的列的数量。跨列的元组对齐以及顺序访问模式降低了元组重建的开销。在Figure 4.1中，中间结果以行id的形式组织（位置）。然而，正如我们早先讨论的那样，这里存在很多的可替代方案，例如使用位向量（bit-vector）、或者像文献[80]中描述的一样，先独立地过滤列，然后再进行merge

值得注意的是，在C-Store的投影中，元组重建的开销更低。鉴于每个投影都经过排序，查询操作会将后续的元组重建限定在相同的范围内。由于投影是根据当前属性排序的，该投影中的其他列也以此属性排序，因此，确定位置信息后，只需要在不同的列中用同一个位置信息来获取列值，并进行元组构建即可。这种方式能够进一步的优化访问模式，以及增大缓存命中。database cracking采用了自组织的形式达到了相同的效果（我们将在后面详细讨论）。即随着工作负载的发展对列进行部分排序，适应工作负载模式并避免先验地创建整个投影

Advantages of late materialization。延迟物化有4重优势。第一，选择和聚合算子减少了不必要的元组重建操作。因此，如果算子在重建元组前等待了足够长的时间，它可能能够完全避免构造它的开销。第二，如果数据是被压缩过的（尤其是RLE这种压缩方式），在元组重建的时候必须进行解压缩，并且与其他列值共同组成一个元组，这消除了直接操作压缩数据带来的优势

第三，当直接操作列值数据时，缓存性能较高（命中率高），因为缓存中的数据没有被算子中其他相关的属性所污染[5]。这一点至关重要，因为CPU与内存之间的带宽是现代计算机系统的主要性能瓶颈。举个例子，在谓词算子中（例如$WHERE\ salary \gt 100,000$，由于算子仅对salary这一个属性进行操作，因此不会浪费带宽

第四，在定宽列值的场景中，之前提到的vectorized optimizations能够进一步优化性能。在行存储当中，如果某个属性的宽度是可变的，那么整个元组就是可变的。在延迟物化的列存储中，定宽的列可以被独立处理

在某些情况下，延迟物化的性能要比早期物化差。举个例子，如果在多列上使用非限制性谓词（例如，$WHERE\ salary \gt 100\ AND\ age \gt 5\ AND...$），那么需要在多组中间结果（每个谓词一个）间进行交集以及物化操作，整体开销会比简单的元组构造过程大得多

Multi-column blocks。有几个方向可以进一步提高元组重建的性能，甚至在某些情况下甚至完全消除它。其顶层设计是将数据存储在一组列中而不是一个列中，这种方式被称为多列块（multi-column blocks）、列向量块（vector blocks）或列组column-groups

列向量块将属性关系等相关信息存储在原始的压缩信息中。如Figure 4.2所示，一种理解列向量块存储方式的方法是，将其与PAX进行对比，差别是，并非所有相关的属性都必须存储在同一个页面中。列向量块允许谓词单独应用于每一列，然后位置向量会被输送到交集算子并进行交集运算，并将结果输出到位置解释器中（Figure 4.2最左边），用以表示哪些元组满足了所有的谓词，这些结果可以输送到更上层的算子进行进一步的处理

尽管，列向量块并不能消除位置交叉的需要，但是一次只对每列的一个小子集进行操作，可以以流水线的形式产生谓词判断的结果（位置向量），并将其直接输送到交集算子中，从而实现元组的构造。这意味着，只要不涉及到join操作，在大部分情况下，延迟物化都要优于早期物化。然而，在有join操作的场景中，如果不经过优化处理，延迟物化反而会带来问题，我们将在下一节中讨论

IBM Blink[11]中使用的列向量块，提出了一种更加灵活的布局：存储在列向量块某个页面的数据，可能以面向行的形式存储。需要注意的是，这里的面向行的格式与传统的行存储中的格式（例如槽页）不同，它仍然以列的形式存储（定宽密集数组），但是某个页面中的数据可能会“粘”在一起，形成矩阵。这对于那些工作在列向量块中的所有列上的算子大有裨益，因为完全避免了中间结果以及元组重建（只要查询过程中不涉及列向量块以外的列）

类似的想法还被应用于行存储中，例如multi-resolutions blocks[94]。该方案中，每个页面可能仅包含一张表中的部分属性，这样可以避免从磁盘中加载与本次查询无关的属性。在内部，页面仍然以槽页的方式进行组织，并且以标准的行执行引擎进行处理

Figure 4.3展示了，列存储中多种不同的存储方式，每个页面可能存储了一个列，或者多个列。内部以列的方式组织或者定宽行的形式组织

列向量块以及多种变体，被现代化列存储系统所使用，包括Vertica、VectorWise以及IBM BLU。列向量块的一个劣势是：我们必须事先做好决策，决定哪些列需要被组织在一起。这需要了解工作负载的相关特点以及一个相对稳定的访问模式（业务场景固化）。针对VectorWise的研究表明，当访问模式的收益超过转换成本时[101]，在查询处理期间即时构建此类列向量块甚至是有益的，而视觉系统需要能够根据查询模式实时自适应地调整存储模式

4.5 Joins

连接算子为列存储系统提供了大量的优化机会，但是如果不妥善处理的话，同样会导致性能瓶颈以及复杂度的提升。如果在连接操作的同时使用了早期物化策略，数据在输送到连接算子之前就会进行元组物化操作，因此连接算子会和行存储系统中的连接算子一样进行处理，并输出连接后的元组（因此与行存储中的连接算子性能相似）。然而，可以将几种可替代的连接算法与延迟物化策略一起使用。最直接的方式是，将仅与连接谓词相关的列作为连接算子的输入。以hash-join（一种常见的连接算法）为例，这使得hash表更为紧凑，从而可以进一步优化访问模式；hash表越小，缓存命中率越高。连接算子的输出是一对位置向量（符合连接谓词）。举个例子，下面这张图展示了长度为5的列和长度为4的列的连接过程

对于大多数连接算法，连接算子输出的2个位置向量中，左边（或者外面）的这个位置向量会被排序，而右侧（内侧）的将不会。这是因为，左边的这个位置向量经常会被遍历访问，而右边的这个位置向量通常用于判断列值是否符合连接谓词。对于其他连接算法（例如，对两组输入进行排序或重新分区的算法）都不会对位置向量进行排序，无论哪种方式，至少有一个位置向量不会被排序。这个未排序的位置向量可能会成为一个问题，因为通常在连接操作之后，还需要获取其他列的数据，例如以下查询

在连接后需要从emp表中提取age属性，以及需要从dept表中提取name属性。基于未排序的位置向量的查询动作将会造成性能能问题，因为在列中乱序的取值会导致在不同的位置上跳跃，这将导致严重的性能问题，因为大部分的存储驱动，其随机访问的表现要远远低于顺序访问

幸运的是，多个文献中提到了针对依据未排序的位置向量，在存储中跳跃取值的多个优化项。其中一种方法就是Jive join[64, 89]。举个例子，当我们连接一个长度为5的列和一个长度为4的列的时候，我们会得到如下的输出

上图中右侧（内侧）的位置向量是未排序的。现在假设我们将会根据右边这个位置向量从表中取出name属性，该属性包含如下几个数值

Jive join的核心思路是：我们在位置向量之外，额外添加一列，该列是一个连续递增的整数

然后按我们要提取的位置向量进行排序（排序会导致我们新添加的这一列变成无序），如下

于是，可以以顺序的访问访问需要提取数据的这一列，然后添加到当前的数据结构中

最后将数据重新依据额外添加的那一列进行排序，以恢复其原始的顺序

该算法使得任何列都可以被顺序访问，代价就是两次排序。这些额外排序的成本随着连接算子输出的大小而增加。由于大部分的数据库系统都有一个非常高效的排序算法（与顺序访问的开销相近）。该算法可以显著优化由延迟物化连接算法带来的性能问题

进一步的研究使上述算法得到了进一步的改进。研究表明，为了降低随机访问性能开销，而在连接操作后对列值进行全排序是不必要的。这是因为，大部分的物理介质会将数据存放到连续的多个存储块中，在一个数据块中的随机访问的开销要远低于在所有数据块中随机访问。因此，数据库无需在提取列值前对位置向量进行全排序。只需将其以存储块的形式进行划分即可。在每个分区中，位置向量仍然是无序的，正如前面介绍的，在块中的随机访问的性能开销是很低的。我们所提取的列值在数据块维度仍然是有序的，但并不是整体有序。Radix Join就应用了这种方法，并提供了一种机制，用于在列值提取之前对位置向量进行分块操作，然后在提取操作结束后，恢复原始顺序

实际上，由于额外的工程复杂度，大多数商业化的列存储系统的实现并未采用单纯的延迟物化连接技术，尽管这些技术在学术上已被证明了非常有效。有些则使用了混合物化方法，依赖左侧有序输入来遍历、依赖右侧无需输入来探测。对于右侧（内侧）的表，会将所有相关的列（连接所涉及的所有列），而不仅仅作为连接谓词的列，先进行物化操作，然后再输送到连接算子中；同时对于左侧（外侧）的表，仅会将与连接谓词相关的列输送到连接算子中。连接算子的输出是来自右侧的一组元组和来自左侧的一个位置向量，然后会以依照位置向量，从右侧的元组集合中提取对应的列值信息，并完成元组构建。这种方法的优势在于，对于不同的列值，仅执行了一次提取操作。对于那些需要无序访问连接相关列的连接算法，通常会在连接操作之前进行元组物化

多列向量提供了右侧关系组的替代方案，相关列会以多列向量的形式而非元组的形式输送到连接算子中去。与连接谓词匹配的位置信息会用于检索其他相关的列值，并动态构建元组。当连接选择性低且需要构造的元组很少时

最后，自从列存储技术在2000年初复兴依赖，针对MonetDB以及C-Store连接的研究催生了一大批针对内存连接的优化方式的研究，例如[9, 10, 6]。所有这些努力的共同点是，它们遵循列存储算子最先采用的顶层设计，例如关注主存性能、对硬件属性和趋势敏感、有缓存意识、利用SIMD指令、避免随机访问模式等

4.6 Group-by, Aggregation and Arithmetic Operations

到目前为止，我们讨论了选择、连接以及元组重建的相关内容。在本小节中，我们将讨论列存储中的分组（group by）、聚合（aggregation）以及算数（arithmetic）算子。总的来说，这些算子利用了延迟物化、vectorization等基于列存储数据布局的技术，因此这些算子只需要工作在相关的数据上（无需存取额外的数据），并且具有CPU、缓存友好的访问模式，能够有效利用SIMD指令

Group-by。在列存储中，分组算子通常基于散列表（hash-table）来实现。具体来说，我们会使用一个小型的散列表，仅存储于分组相关的属性，这样有助于提高性能

Aggregations。聚合算子深度依赖列存储数据布局。具体来说，他们以紧密循环的方式工作在相关的列上。举个例子，以sum()、min()、max()、avg()算子为例，它们仅需要扫描相关的列（或者中间结果，也是基于列），这样能够提高内存带宽的利用率，如Figure 4.1中的Step 11所示

Arithmetic operations。算数算子会在select子句中用到，例如+、-、*、/等数学算子，同样能够借助列存储的特性以获得更高的执行效率。但是算数算子通常工作在一组列上，例如$select\ A+B+C\ From\ R...$，并且需要为每个动作产生中间结果。在这个例子中，一个中间结果就是$inter=add(A, B)$，算子会工作在列A和列B上，并且产生中间结果并输送到另一个$res=add(C, inter)$算子中，并产生最终结果。Vectorization能够任何给定时间最小化中间结果的内存占用，并且将中间结果即时转换为列向量以便处理多列（的向量）也可能是有益的[101]，从而避免一次性物化所有中间结果。在上面的例子中，我们可以为$(A, B, C)$创建一个列向量，以便在一次运算中就能得到最终结果

4.7 Inserts/updates/deletes

列存储相比于行存储对数据变更操作更加敏感。不同的列独立存储在不同的文件中，这意味着一张数据表被存储在多个不同的文件中。正因如此，针对某一条数据的更新操作，就会涉及到多次I/O。而与此相反，行存储只需要一次数据更新操作即可。通过列向量能够有效降低I/O次数，但仍然会涉及到多次I/O操作

列存储除了垂直分片，还大量使用压缩，并且还可能以不同的顺序存储多个表副本或投影，目的都是为了提高查询性能。即使用户想要一次插入多个元组，由于有序或聚集存储，这些磁盘I/O也是分散的（随机）I/O。最后，压缩还使得更新操作更加复杂，因为需要解压缩数据，然后进行数据变更，再将压缩后的数据重新写回磁盘。如果更新的数据不再适合原始位置，则会出现额外的复杂情况

一些分析型列存储数据库系统，例如C-Store、MonetDB，通过将其架构拆分为管理所有数据的read-store和管理最近进行的更新的write-store来处理更新。于是，所有查询都会从read-store获取基础信息，从write-store获取差量信息，并即时进行合并。为了尽量保持write-store处于一个较小的容量（通常来说都在内存中）。write-store中的数据都会被定期地刷入read-store中

一个比较自然的方式就是，将所有差量的数据（插入、删除、更新）写入位于内存中。MonetDB使用普通列，即对于模式中的每个基本列，都有两个辅助列来存储插入和删除的数据（更新可以由删除和插入操作组成）。C-Store采用了类似于行存储的存储方式，能够加速数据的更新，因为只需要一次I/O（但是会导致将数据合并到列存储中的开销变得更大）。将增量单独存储的缺点是，每次查询都要在基础列和差量列之间进行一次合并操作。然而，这里存在许多的优化点。举个例子，我们可以仅在最后进行合并操作，而不需要每次都进行合并操作。再举个例子，一个选择算子会独立地作用于基础列和差量列，但是只有那些满足谓词的元组才需要进行合并操作。此外，我们还可以通过一个布尔值来标识列值是否被删除，并且可以通过一个bitmap来保存和更新该布尔值

VectorWise采用了一种更加新颖的数据结构，被称为Positional Delta Trees（PDTs），来存储差量。其主要优势在于，合并操作主要依赖差量的位置信息，而不是用于排序的关键词，后者会更加复杂。当查询提交时，它会立即找出哪些表位置受到影响。因此，它将合并过程从查询时间移动到更新时间，这符合读取优化处理的议程。相反，如果没有PDTs，我们将需要使用开销更高的MergeUnion以及MergeDiff处理过程，该过程在每次查询时都会执行。此外，它使每个查询都读取排序键列，如果这些属性不是查询所必需的，则会导致额外的I/O

跟踪有序表中的位置是很棘手的，因为插入、删除会在中途改变所有后续元组的位置，PDT是一种计数类型B树，以对数更新成本（$log\ cost_{update}$）跟踪位置信息

差分数据结构PDT以及之前提到的差分文件，可以进一步分层：我们对差分进行差分，对差分的差分进一步差分，等等。这种分层架构可以利用操作下通内存的分层架构的特性。例如可以将最小的差分存储在CPU cache中，大一点的差分存储在RAM中，再大一点的差分存储在磁盘上。此外，分层增量是实现隔离和事务管理的工具。这个想法是一个新的事务将一个最初为空的顶层PDT添加到已经存在的基层PDT上。通过共享不可变的基层PDT，可以提供廉价的快照以及隔离性。当有数据发生变更时，差量会被写入到顶层的PDT中，它有效地捕获了事务的写集。在[41]中展示了在并发事务下保持PDT位置跟踪一致的算法，正是实现乐观并发控制所需的算法

最后，一个最新的研究表明，现在的趋势是在单个系统中同时支持OLTP和OLAP。通过采用列存储中首创的许多原则来实现快速OLAP处理。System Hyper[57, 56]是在这个领域中最有代表性的例子，它的主要设计特点是它依靠硬件辅助的页面阴影来避免在更新过程中锁定页面。此外，SAP HANA[26]以列和行格式存储数据，以启用这两种功能

4.8 Indexing, Adaptive Indexing and Database Cracking

在本小节中，我们将讨论列存储当中的索引以及自适应索引。尽管列存储提供了远好于行存储的扫描性能，仍然可以通过索引来进一步优化。列存储中的扫描可以通过一个循环来实现，其性能表现非常好，但是使用索引可以能够将进一步提高性能，大约1个或几个数量级[44]。关于列存储索引的形状，研究表明在完全排序的列上工作比在列顶部维护内存树结构（例如 AVL树）更有益[44]。树结构同时支持遍历以及随机访问，另一方面，如果我们完全复制和排序基列，我们可以在范围查询时利用有效的二分搜索操作

Indexing。C-Store引出了投影的概念。每个表可能以不同的排序方式存储了多个副本。此外，每个副本不需要包含表中的所有列，而仅包含投影相关的列。查询可以使用单个覆盖投影，该投影用于谓词最相关的属性进行排序（理想情况下），用于降低查询开销以及元组重建的开销。相比于传统行存储系统，鉴于列可以被充分压缩，实现这些额外的投影不会带来非常显著的存储开销。当然，投影的数量取决于工作负载，并且会为数据变更带来额外的复杂度（与传统行存储数据库中的索引相似）

另一个在列存储中经常用到的索引形式是zonemaps。在每个页面上存储一些轻量的元数据，比如min/max等。举个例子，Netezza使用这种形式的索引来提高扫描的性能，因为可以通过min/max这些元数据来快速判断当前页面中是否包含符合查询条件的数据。其他有有创意的想法包括使用缓存敏感位图索引[86]，它为每个区域创建一个bitmap，而不仅仅是在每个页面中记录min/max等信息

Database Cracking and Adaptive Indexing。所有形式的索引都需要人为进行设置，并且需要工作负载相关的知识作为输入，但是这些通常都是稀缺资源。在本小节余下的部分，我们将讨论列存储中有关database cracking的一些早期的尝试[44]，database cracking在MonetDB系统的背景下开创了现代数据库系统中自适应索引的概念，并引入了为自适应索引量身定制的列存储架构[48, 49, 50, 51, 37, 35, 36, 83]。我们将讨论这些工作的基础知识，以及这些工作通过利用列存储架构的关键特性在列存储环境中蓬勃发展的原因

传统（即非自适应）索引的基本问题之一是：我们需要就我们将要创建的索引做出固定的预先决定（说白了，索引就是开发者根据业务特点以及工作负载手动创建的）。考虑到时间以及空间因素，创建所有可能的索引是不切实际的，因为既没有足够的空间来容纳这些索引，也没有足够的时间来创建和维护这些索引。因此，我们需要决定如何调整数据库系统，选择要创建的索引集。然而，对工作负载充分了解后，才能作出上述决策，包括如何使用数据库，常用查询模式是怎样的，对用户来讲哪些是关键数据等等。随着我们进入大数据时代，越来越多的应用场景表现出不可预测的行为（ad-hoc），这意味着无法依赖工作负载来作出选择。此外，越来越多的应用要求在尽可能短的时间内对新的数据达到较高的查询性能，换句话说，没有时间来研究特定工作负载然后作出如何创建索引的决策，于是发展为由数据库系统自己决定如何创建索引

这种动态和在线的场景是自适应索引的主要动机。其主要思想是：数据库仅会自动创建必须的索引。a) 仅在必要时创建；b) 仅创建必要的索引；c) 持续调整索引。通过database cracking，一旦有数据，数据库立即变得可用（无需额外的时间来创建索引）。系统使用得越多，如果有足够的空闲时间和工作负载相关的信息来充分准备当前工作负载所需的所有索引，则性能就越接近最佳性能

主要创新是物理数据存储会随着查询而发生变化，对于每个查询$q, using\ q\ as\ a\ hint\ on\ how\ data\ should\ be\ stored$，

假设有一个查询的查询条件是$A \lt 10$，DBMS会将所有满足$A \lt 10$的元组放到最前面，将所有满足$A \ge 10$的元组放到最后面。当后续查询的查询条件是$A \ge v_1, v_1 \ge 10$，那么只需要在后半部分进行搜索即可（即$A \ge 10$的那部分）。同样，当后续查询的查询条件是$A \lt v_2, v2 \le 10$，那么只需要在前半部分进行搜搜即可（即$A \lt 10$的那部分）。crach动作作为查询算子的一部分，无需额外的管理。Figure 4.4展示了通过以选择谓词作为分区的边界，将列进行分解的例子。其中查询Q1将列分解成三部分，查询Q2进行进一步分解

cracking能够有效提高列存储系统的性能。Sloan Digital Sky Surve最近的实验表明，开启了cracking的MonetDB可以完成160000次查询，而未开启cracking的MonetDB还在创建索引，且仅创建了一半，因此无法响应任何查询。另外，在TPC-H基准测试中，MonetDB创建所有索引、投影等耗费了3个小时，而开启了cracking的MonetDB，则在无任何准备工作的前提下，几秒内就响应了所有的查询[50]。Figure 4.5展示了一些分析结果。普通的列存储（MonetDB）相比于行存储系统（MySQL）具有更好的性能，即便在行存储系统使用了B-tree的情况下（Mysql presorted）。在列存储系统开启投影后，能够进一步带来性能增益（MonetDB/presorted），但是以巨大的初始化开销作为代价，在此次TPC-H基准实验中，花费了3小时来创建投影。另一方面，当MonetDB开启cracking后，系统能够在无准备的情况下，立即响应查询请求，并且在几次查询后就会达到一个较好的性能，且性能与花费了大量时间进行前置准备工作（例如创建索引等）的系统的查询性能接近

cracking技术会将数据库分解成多个较小且易于管理的片段（类似快排的分区）。cracking通过逐渐改善数据的访问，并最终提升查询性能[48, 50]，甚至可以提升更新的性能[49]。cracking在列存储系统中，仅作用于列这个维度，查询导致的数据重组仅限定在与查询相关的列中，而不是整张表。cracking根据查询需要在多个列中进行传播，其中一些cracker是根据存储限制动态创建和删除的。在文献[35]中，作者展示了如何通过有限的并发控制来启用并发查询，具体来说就是仅依赖latch，因为cracking仅改变索引结构而不会改变索引内容。另外，stochastic cracking[37]通过不太严格地遵循查询边界来执行非确定性的cracking动作。通过这种方式，它使得列的分区更加均匀，避免产生大块的未分区的区域，降低未来分区的成本

后续的研究[51]扩展了最初的cracking，采用了具有显式排序或者非显式分区的分区/合并逻辑。原始的cracking可以看做是增量快速排序（分区动作是由查询驱动的），而这些最新的cracking介于增量快速排序和增量归并排序之间，并设计了一系列索引自适应算法

cracking采用了完全不同的方法。到目前为止，查询处理所耗费时间被认为是极其宝贵的，除了处理当前查询之外不会发生任何其他事情。而cracking另辟蹊径，会持续优化索引，同时获得短期或者长期的增益。这是利用某些列存储架构特性的直接副作用。特别地，批量处理和列式存储使这些自适应索引的思想成为可能。通过一次存储一列数据，以定宽密集数组的形式存储在连续的内存区域中，意味着cracking能以最小代价重组这个数组（相比于将数据存放在槽页中的行存储系统，定位单个值可能都需要进行重定向）。此外，批量处理意味着每个算子在查询计划继续执行下一个算子之前完全消耗其输入列，对于cracking来说，这意味着每个算子工作在单一的列上，有助于有效地执行所有细化操作。vectorized processing同样有效，主要区别是每个向量是独立破解的，并且根据策略数据也可能跨向量移动[51]

前面讨论的C-Store中的投影是另一种形式的索引，它存储了按照不同属性排序的多个副本。从上层的视角来说，cracking架构与C-Store中的投影起到了相似的作用，只不过以一种更加自动化、动态的方式来实现。我们无需事先决定需要创建哪些投影，自然也无需为创建投影花费额外的时间成本

除了无需工作负载相关的信息以及额外的时间之外，cracking还允许用户在使用数据库系统的时候无需进行过多的调优。它能够降低使用数据的配置成本，且无需配置数据库管理员来进行索引相关的决策以及对索引的维护以及调优

过去针对数据库的研究中并没有针对自适应索引相关的研究。其中，与cracking概念最接近的是partial indexes[87]，它允许只在表的一部分上创建传统的非自适应索引。从而避免索引数据中包含与查询无关的数据（需要基于工作负载相关的信息）

4.9 Summary and Design Principles Taxonomy

本章中提到的设计原则被大多数列存储系统所使用，并为所有后续的主内存和缓存设计提供了共同的基础。

从上述众多功能中可以看出，现代列存储不仅仅是一次一列存储数据。它们提供了为现代硬件和数据分析量身定制的全新数据库架构和执行引擎

在许多场景中，列存储有助于最大限度地利用这些新设计原则。从这个意义上说，我们可以说主要由VectorWise和C-Store重新定义的现代列存储系统是一个包含所有这些设计原则的系统，而不仅仅是面向列的存储布局

正如我们在本节和前几节中所讨论的，现代列存储的一些设计原则，过去曾在传统行存储的背景下以某种形式进行过研究。然而，在MonetDB、VectorWise和 C-Store被提出之前，没有任何系统可以提供具有所有这些设计原则的完整DBMS的设计和实现。本质上，它们标志着对数据库内核进行全面重新设计的必要性，其灵感来自于数据库社区对DBMS架构进行了数十年的研究

Figure 4.6展示了上述章节中讨论的一些特性以及设计原则，这些特性以及设计原则共同定义了现代列存储系统，并且指出了这些特性以及设计原则与在行存储背景下独立提出的一些特性以及设计原则的相似性

5 Discussion, Conclusions, and Future Directions

在本节中，我们简单对比MonetDB、VectorWise、C-Store。我们还讨论了在面向行的数据库中模拟列存储的可行性，并提出了结论和未来的工作

5.1 Comparing MonetDB/VectorWise/C-Store

读取优化的数据库系统显然受益于CPU高效的查询执行效率。上述这三种架构：MonetDB、VectorWise、C-Store，以不同的方式用到了block-oriented execution[74]。MonetDB将column-at-a-time的执行模式贯彻到极致，从而引出了延迟物化这一技术。C-Store以及VectorWise都允许流水线执行，在算子之间传递元组块而不是单个元组。其中，C-Store中元组块会被尽可能地以压缩的形式存在，VectorWise在整个执行以及存储架构中使用了vectorized

对于存储和更新，MonetDB以及C-Store使用了一个简单的方法，使用deletion bitmap以及临时表来表示插入（WOS）。尤其在大型的连接查询中，在元组流被送入连接算子之前需要对插入和删除的数据进行合并操作，这会导致大量的合并开销。VectorWise中提出的PDT数据结构能够大幅降低这种开销，尽管PDT的实现较为复杂，且插入和删除操作的开销更大

普通的MonetDB不会使用压缩，也不会以任何顺序存储数据表。VectorWise以及C-Store大量使用压缩，且只有C-Store提供了压缩执行。C-Store以不同顺序存储了投影中的多个副本。VectorWise使用了一个稀疏索引来存储一个范围内元组的最大以及最小值，从而降低范围谓词匹配的开销，且能进一步降低扫描带来的I/O开销

5.2 Simulating Column/Row Stores

关于面向列的数据库的一个常见问题是是否可以使用传统的面向行的系统来模拟基于列的系统。这里有两种方法可以用于实现这个仿真：使用完全垂直分区的设计以及为每列创建一个索引。我们将会挨个讨论这两种方法，并列出每种方法的劣势

Vertical Partitioning。在行存储系统中模拟列存储的最直接的方法是对所有关系进行垂直分区，正如在上述讨论的早期列存储中所做的那样[58]。如果进行了彻底的垂直分区，那么需要有一些机制来为一行的多个字段之间建立联系（在列存储系统中，同一行的不同列以相同的顺序存储，这就是一种隐式的联系，但是在行存储系统中，并不存在这种联系）。最简单的方式就是为每个表增加一个整数列，用于保存位置信息（position），这通常比使用主键更可取，因为主键可能很大并且有时是复合的）。例如，给定如下的employee表：

我们增加一列position

于是，我们为这张物理表的每列都创建了一个单独的表。其中第$i^{th}$张表包含两列，其中一列是employee中的第$i^{th}$列，另一列是position（取值从1开始）

然后将包含employee表的多个属性的查询操作改写为多个表的连接操作

下面是这种方式的主要劣势：1) position列会占用额外的存储空间，并会带来额外的I/O开销；2) 需要增加一个适配层用于转换查询语句；3) 由于查询语句改写会引入连接操作，而连接的数量将会使得大多数DBMS实现的优化器不堪重负，并且会对查询性能造成灾难性的影响；4) 由于每个列存储在独立的表中，因此每个列包含一个元组头，它的大小可能远远大于数据本身的大小；5) 无法使用面向列的压缩算法，例如RLE

Creating an index on every column。这种方法是为数据表的每个列都创建一个索引。这种方式解决了上述垂直分区带来的大部分问题（至少问题2、3、4），但是它也存在自己的劣势。其最主要的问题就是大量索引带来的空间成本以及更新所需的开销。然而，更严重的问题是，数据在每个索引中的顺序可能与其在行中的顺序并不一致。因此，将两个（或多个）属性物化为行（如第4.4节所述，需要在查询执行期间的某个时刻发生）需要对tuple-id进行完整的连接（与垂直分区的情况不同，垂直分区可以通过简单地将两列合并在一起来执行，而这里两组值完全未对齐）。因此，在实践中，数据库优化器将使用原始行存储表进行列投影，这将完全抵消列存储仅读取相关列所带来的性能增益

5.3 Conclusions

我们描述了许多架构创新，它们使MonetDB、VectorWise和C-Store等现代列存储能够在分析工作负载上提供非常好的性能。包括压缩、vectorization、延迟物化、高效的连接方法等等。这些方法被一些商业化的系统所采用，包括学术项目的直系后代（VectorWise和Vertica）以及一些其他项目（Aster Data、Greenplum、Infobright、Paraccel等）。甚至行存储的坚定拥护者Oracle也已在其数据库Exadata中实施了一些面向列的技术（特别是，他们实施了PAX页面布局和面向列的压缩）。据称，这些产品在典型的数据仓库和分析工作负载上提供比老一代面向行的系统高1到2个数量级的性能，并且在商业上非常成功（VectorWise、Vertica、Greenplum和Aster Data都已被收购）

尽管列存储在学术和商业上都取得了成功，仍然存在几个有趣的研究方向。特别地，部分面向列的混合系统有很大的机会。举个例子，将经常访问的多个列存储在一起能够比单纯的列存储达到更高的性能。此外，随着时间的推移，根据访问模式自适应地选择面向列和面向行的存储方式的系统可能会变得很重要，因为要求用户确定哪种类型的存储方式并不合理[45]。Microsoft在SQLServer产品中增加了一个列存储的选项用以支持vectorized查询处理。尽管这些功能仍然有限（系统只读、只有部分算子和数据类型支持了vectorized处理，且不能动态作出存储方式的决策）但这是朝这个方向迈出的一步

我们同样期望列存储的一些想法能够进入其他的数据处理系统，例如Hadoop、MapReduce[27]，它们在海量数据的分析型处理中被广泛使用

6 参考

• The Design and Implementation of Modern Column-Oriented Database Systems.pdf

7 todo

1. OLAP、OLTP
2. Database cracking的定义：数据库分解，就是在查询的过程中，对列进行分区（类似快排的partition）
3. EVI
4. transposed files
5. 列存储和行存储是数据库系统最底层的部分，这部分的差异，顺着技术栈往上走，如何影响上层模块的架构？
6. DBMS、RDBMS
7. Disk Bandwidth的定义
8. 在数据库的上下文中，load指的是存储数据还是读取数据？
9. WOS支持高效地加载数据，并且能够分摊压缩和搜索的时间开销？为什么
10. 什么是BAT？
11. 算子的谓词是指什么？
12. RISC
13. SIMD指令是什么？
14. Parallel memory access，不知所云，翻译稀烂