目录
一、概述
传统的关系型数据库，如 Oracle、DB2、MySQL、SQL SERVER 等采用行式存储法(Row-based)，在基于行式存储的数据库中， 数据是按照行为基础逻辑存储单元进行存储的， 一行中的数据在存储介质中以连续存储的形式存在。
列式存储(Column-based)是相对于行式存储来说的，比如：Hbase、Doris、Clickhouse等分布式数据库均采用列式存储。在基于列式存储的数据库中， 数据是按照列为基础逻辑存储单元进行存储的，一列中的数据在存储介质中以连续存储形式存在。
二、行存储
行式存储的适用场景：
1、适合随机的增删改查操作;
2、需要在行中选取所有属性的进行查询操作;
3、需要频繁插入或更新的操作，其操作与索引和行的大小更为相关。
行式数据库在读取数据的时候会存在一个固有的“缺陷”，比如，所选择查询的目标即使只涉及少数几项属性，但由于这些目标数据在各行数据单元中，而行单元往往又特别大，应用程序必须读取每一条完整的行记录，从而使得读取效率大大降低。对此，行式数据库给出的优化方案是加“索引”。在OLTP类型的应用中，通过索引机制或给表分区等手段，可以简化查询操作步骤，并提升查询效率。
但针对海量数据背景的OLAP应用(例如分布式数据库、数据仓库等等)，行式存储的数据库就有些吃力了，行式数据库建立索引和物化视图，需要花费大量时间和资源，因此还得不偿失，无法从根本上解决查询性能和维护成本等问题，也不适用于数据仓库等应用场景，所以后来出现了基于列式存储的数据库。
三、列式存储
对于数据仓库和分布式数据库来说，大部分情况下它会从各个数据源汇总数据。然后进行分析和反馈。其操作大多是围绕同一列属性的数据进行的，而当查询某属性的数据记录时，列式数据库只需返回与列属性相关的值，在大数据量查询场景中，列式数据库可在内存中高效组装各列的值，最终形成关系记录集，因此可以显著减少IO消耗，并降低查询响应时间，非常适合数据仓库和分布式的应用。
列式存储引擎的适用场景包括：
1、查询过程中，可针对各列的运算并发执行，最后在内存中聚合完整记录集，最大可能降低查询响应时间;
2、可在数据列中高效查找数据，查询过程中能够尽量减少无关IO，避免全表扫描;
3、因为各列独立存储，且数据类型已知，可以针对该列的数据类型、数据量大小等因素动态选择压缩算法，以提高物理存储利用率；如果某一行的某一列没有数据，那在列存储时，就可以不存储该列的值，这将比行式存储更节省空间。
当然，跟行数据库一样，列式存储也有不太适用的场景，主要包括：
1、数据需要频繁更新的交易场景
2、表中列属性较少的小量数据库场景
3、不适合做含有删除和更新的实时操作
四、列式查询
789.90KB
列式存储针对分析场景，有几大关键的优化点：向量化查询处理（vectorized query processing）、压缩（compression）、隐式连接（invisible join）、延迟物化（late materialization）等。
而这些技术的应用，需要从存储层到计算层的全面支持才行。
而这些技术的应用，需要从存储层到计算层的全面支持才行。
4.1 延迟物化（late materialization）
要理解延迟物化(Late Materialization), 首先解释一下什么是物化：为了能够把底层存储格式(面向Column的), 跟用户查询表达的意思(Row)对应上，在一个查询的生命周期的某个时间点，一定要把数据转换成Row的形式，这在Column-Store里面被称为物化(Materization)。
延迟物化就很好理解了，意思是把这个物化的时机尽量的拖延到整个查询生命周期的后期。延迟物化意味着在查询执行的前一段时间内，查询执行的模型不是关系代数，而是基于Column的。下面看个例子, 比如下面的查询:
SELECT name
FROM person
WHERE id > 10
and age > 20
一般的做法是从文件系统读出三列的数据，马上物化成一行行的person数据，然后应用两个过滤条件: id > 10 和 age > 20 , 过滤完了之后从数据里面抽出 name 字段，作为最后的结果，大致转换过程如下图:
而延迟物化的做法则会先不拼出行式数据，直接在Column数据上分别应用两个过滤条件，从而得到两个满足过滤条件的bitmap, 然后再把两个bitmap做位与(bitwise AND)的操作得到同时满足两个条件的所有的bitmap，因为最后用户需要的只是 name 字段而已，因此下一步我们拿着这些 position 对 name 字段的数据进行过滤就得到了最终的结果。如下图:
整个过程中我们压根没有进行物化操作，从而可以大大的提高效率。
总结起来延迟物化有四个方面的好处:
关系代数里面的 selection 和 aggregation 都会产生一些不必要的物化操作，从一种形式的tuple, 变成另外一种形式的tuple。如果对物化进行延迟的话，可以减少物化的开销(因为要物化的字段少了)，甚至直接不需要物化了。
如果Column数据是以面向Column的压缩方式进行压缩的话，如果要进行物化那么就必须先解压，而这就使得我们之前提到的可以直接在压缩数据上进行查询的优势荡然无存了。
操作系统Cache的利用率会更好一点，因为不会被同一个Row里面其它无关的属性污染Cache Line。
块遍历 的优化手段对Column类型的数据效果更好，因为数据以Column形式保存在一起，数据是定长的可能性更大，而如果Row形式保存在一起数据是定长的可能性非常小(因为你一行数据里面只要有一个是非定长的，比如VARCHAR，那么整行数据都是非定长的)。
4.2 块式迭代（Block iteration）
块遍历(Block Iteration)是相对于单记录遍历(per-tuple iteration)而言的，其实说白了就是一种批量化的操作。单记录遍历的问题在于对于每个条数据，我们都要从Row数据里面抽取出我们需要的column(针对Row-Store来说)，然后调用相应的函数去处理，函数调用的次数跟数据的条数成是 1:1的，在大数据量的情况下这个开销非常大的。而块遍历，因为是一次性处理多条数据，函数调用次数被降下来，当然可以提高性能。
而如果column的值是字节意义上等宽的，比如数字类型，Column-Store可以进一步提高性能，因为查询引擎要从一个Block里取出其中一个值进行处理的时候直接用数组下标就可以获取数据，进一步提升性能。而且以数组的方式对数据进行访问使得我们可以利用现代CPU的一些优化措施比如SIMD(Single Instruction Multiple Data)来实现并行化执行，进一步提高性能。
4.3 压缩
压缩这种优化的方法对于Column-Store比对Row-Store更有效.
对数据进行更高效的编码, 使得我们可以以更少的空间表达相同的意思。
而能够进行更高效编码的前提是这个数据肯定要有某种规律，比如有很多数据一样，或者数据的类型一样。而Column-Store正好符合这个特点，因为Column-Store是把同一个Column -- 也就是相同类型的数据保存在一起，当然比Row-Store把一条记录里面不同类型的字段值保存在一起更有规律，更有规律意味着可以有更高的压缩比。
但是为什么压缩就能带来查询的高效呢？压缩首先带来的硬盘上存储空间的降低，但是硬盘又不值钱。它的真正意义在于：数据占用的硬盘空间越小，查询引擎花在IO上的时间就越少(不管是从硬盘里面把数据读入内存，还是从内存里面把数据读入CPU)。同时要记住的是数据压缩之后，要进行处理很多时候要需要解压缩(不管是Column-Store还是Row-Store), 因此压缩比不是我们追求的唯一，因为后面解压也需要花时间，因此一般会在压缩比和解压速度之间做一个权衡。
前面提到解压缩，有的场景下解压缩这个步骤可以彻底避免掉，比如对于采用Run-Length编码方式进行压缩的数据，我们可以直接在数据压缩的格式上进行一些计算:
Run-Length的大概意思是这样的, 对于一个数字序列: 1 1 1 1 2 2 2, 它可以表达成 1x4, 2x3
4.4 Invisible Join
一个具有创新性的性能优化措施: Invisible Join,Invisible Join 针对的场景是数仓里面的星型模型(Star Schema), 如果用户查询符合下面的模式就可以应用Invisible Join:
星型模型（Star-Schema）是分析场景最常用的模型：一个事实表基于主键和外键关系关联多个维度表，针对维度表做条件过滤，最后再针对事实表做聚合、排序等
我们要先介绍一下传统的方案，通过对比我们才能看Invisible Join方案的优点。
传统方案: 按Selectivity依次JOIN
传统的做法一般是找到过滤性最强的维度表来关联事实表并过滤，然后再与其他维度表一一关联，得到最终的结果。
need-to-insert-img
Invisible Join详解
join过程，主要分三个步骤：1）下推相关条件到各个维度表，提炼出被事实表关联的主键列表（也就是事实表的外键），并构建对应的hash table（key是外键值，value是外键在维度表中的position）；2）对多个事实表以外键关联维度表的列进行探测，查找对应的hash table，过滤出多个position list（与被关联的列相关），然后对多个position list求交集（比如前文提到的bitmap的AND计算等），得到一个最终的position list；3）基于前面的position list，最终从事实表中找到需要投影的其他列，而通过hash table从维度表找到需要投影的其他列，hash table中的value是维度表中的position，所以可以快速定位维度表的其他列。
need-to-insert-img
need-to-insert-img
need-to-insert-img
考虑到事实表行数非常多，多路探测+hash table查找，整体的开销也是不少的；如果hash table数据存在一些特征的话，可以继续优化：Between-Predicate Rewriting。如果从维度表中得到的主键列表值是完全连续的，那就可以从hash查找改写成范围查找，加速性能。即使维度表的主键列不连续，可以再通过directory encoding方式，重新将这些值按序编码，又可以继续做Between-predicate改写了（这招以前经常使用，比如将string编码成int，后续存储、查找、比较等都非常高效）。
总结来看，这里的“隐式”是指，没有通过传统的join方式（两两表迭代，生成两个表联合在一起的宽行数据，再做过滤）来实现join，而是通过维持不同列的相同行之间的position对应关系，类似于dfp+拉链合并算法的思路来完成多个表join。拉链合并算法，与倒排索引很类似。
??????不是特别理解感觉是一样的可以看一下论文
4.5 性能对比
性能对比数字来看，这几大优化策略里面延迟物化的效果最好，能够提升性能3倍以上；压缩的优化效果次之: 两倍以上；Invisible JOIN 再次之：50% 到 70%；块遍历则能性能 5% 到 50%。
need-to-insert-img
Column-Store的优点不止在于它的存储格式，查询引擎层的各种优化也同样关键，而由于Row-Store本身存储格式的限制，即使在Row-Store上使用这些优化，效果也不好。
五、Parquet
Parquet 是面向分析型业务的列式存储格式，由 Twitter 和 Cloudera 合作开发，2015 年 5 月从 Apache 的孵化器里毕业成为 Apache 顶级项目，Parquet 就是基于 Dremel 的数据模型和算法实现的。
5.1.Parquet数据模型
Parquet的数据模型特点：
元组的Schema可以转换成树状结构，根节点可以理解为repeated类型
所有叶子结点都是基本类型(int double string等)
没有Map、Array这样的复杂数据结构，但是可以通过repeated和group组合来实现这样的需求
demo:
message AddressBook {
required string owner;
repeated string ownerPhoneNumbers;
repeated group contacts {
required string name;
optional string phoneNumber;
}
}
这个schema中每条记录表示一个人的AddressBook。有且只有一个owner，owner可以有0个或者多个ownerPhoneNumbers，owner可以有0个或者多个contacts。每个contact有且只有一个name，这个contact的phoneNumber可有可无。
每个schema的结构是这样的：根叫做message，message包含多个fields。每个field包含三个属性：repetition, type, name。repetition可以是以下三种：required（出现1次），optional（出现0次或者1次），repeated（出现0次或者多次）。type可以是一个group或者一个primitive类型。
Parquet格式的数据类型不需要复杂的Map, List, Set等，而是使用repeated fields 和 groups来表示。例如List和Set可以被表示成一个repeated field，Map可以表示成一个包含有key-value 对的repeated group，而且key是required的。
List(或Set)可以用repeated field来表示：
need-to-insert-img
Map可以用包含key-value对且key是required的repeated group来表示：
need-to-insert-img
5.2 列存储格式
列存储通过将相同基本类型（primitive type）的值存储在一起来提供高效的编码和解码。为了用列存储来存储如上嵌套的数据结构，我们需要将该schema用某种方式映射到一系列的列使我们能够将记录写到列中并且能读取成原来的嵌套的数据结构。
在Parquet格式的存储中，一个schema的树结构有几个叶子节点（叶子节点都是primitive type），实际的存储中就会有多少column。
上面的schema的树结构如图所示：
need-to-insert-img
上面这个schema的数据存储实际上有四个column，如下图所示：
need-to-insert-img
5.3 Striping/Assembly算法
Parquet的一条记录的数据如何分成多少列，又如何组装回来？是由Striping/Assembly算法决定的。
在该算法中，列的每一个值都包含三个部分：
value : 字段值
repetition level : 重复级别
definition level : 定义级别
5.3.1 Repetition Levels
repetition level的设计目标是为了支持repeated类型的节点：
在写入时该值等于它和前面的值从哪一层节点开始是不共享的。
在读取的时候根据该值可以推导出哪一层上需要创建一个新的节点。
例子：对于这样的schema和两条记录：
message nested {
repeated group leve1 {
repeated string leve2;
}
}
r1:[[a,b,c,] , [d,e,f,g]]
r2:[[h] , [i,j]]
计算一下各个值的repetition level。
repetition level计算过程：
value=a是一条记录的开始，和前面的值在根结点上是不共享的，因此repetition level=0
value=b和前面的值共享了level1这个节点，但是在level2这个节点上不共享，因此repetition level=2
同理，value=c的repetition value=2
value=d和前面的值共享了根节点，在level1这个节点是不共享的，因此repetition level=1
同理，value=e,f,g都和自己前面的占共享了level1，没有共享level2，因此repetition level=2
value=h属于另一条记录，和前面不共享任何节点，因此，repetition level=0
value=i跟前面的结点共享了根，但是没有共享level1节点，因此repetition level=1
value-j跟前面的节点共享了level1，但是没有共享level2，因此repetition level=2
在读取时，会顺序读取每个值，然后根据它的repetition level创建对象
当读取value=a时，repeatition level=0，表示需要创建一个新的根节点，
当读取value=b时，repeatition level=2，表示需要创建level2节点
当读取value=c时，repeatition level=2，表示需要创建level2节点
当读取value=d时，repeatition level=1，表示需要创建level1节点
剩下的节点依此类推
几点规律：
repetition level=0表示一条记录的开始
repetition level的值只是针对路径上repeated类型的节点，因此在计算时可以忽略非repeated类型的节点
在写入的时候将其理解为该节点和路径上的哪一个repeated节点是不共享的
读取的时候将其理解为需要在哪一层创建一个新的repeated节点
5.3.2 Definition level
Definition level指明该列的路径上多少个可选field被定义了。
嵌套数据类型的特点是有些field（optional field 和 repeated field）可以是空的，也就是没有定义。如果一个field是定义的，那么它的所有的父节点都是被定义的。从根节点开始遍历，当某一个field的路径上的节点开始是空的时候我们记录下当前的深度作为这个field的Definition Level。如果一个field的definition Level等于这个field的最大definition Level就说明这个field是有数据的。对于required类型的field必须是有定义的，所以这个Definition Level是不需要的。在关系型数据中，optional类型的field被编码成0表示空和1表示非空（或者反之）。
注：definition Level是该路径上有定义的repeated field 和 optional field的个数，不包括required field，因为required field是必须有定义的。
例子：对于这样的schema：
message ExampleDefinitionLevel {
optional group a {
optional group b {
optional string c;
}
}
}
它包含一个列a.b.c，这个列的的每一个节点都是optional类型的，当c被定义时a和b肯定都是已定义的，当c未定义时我们就需要标示出在从哪一层开始时未定义的
一条记录的definition level的几种可能的情况如下表：
ValueDefinition Level
a:null0
a:{b:null}1
a:{b:{c:null}}2
a:{b:{c:”foo”}}3(全部定义了)
由于definition level只需要考虑未定义的值，对于required类型的节点，只要父亲节点定义了，该节点就必须定义，因此计算时可以忽略路径上的required类型的节点，这样可以减少definition level的最大值，优化存储。
5.4 一个完整的例子
下面使用Dremel论文中给的Document示例和给定的两个值展示计算repeated level和definition level的过程，这里把未定义的值记录为NULL，使用R表示repeated level，D表示definition level。
need-to-insert-img
首先看DocId这一列，r1和r2都只有一值分别是：
id1=10,由于它是记录开始，并且是已定义的，因此R=0,D=0
id2=20,由于是新记录的开始，并且是已经定义的，因此R=0,D=0
对于Name.Url这一列，r1中它有三个值，r2中有一个值分别是：
url1=’http://A'，它是r1中该列的第一个值，并且是定义的，所以R=0,D=2
url2=’http://B'，它跟上一个值在Name这层是不同的，并且是定义的，所以R=1,D=2
url3=NULL，它跟上一个值在Name这层是不同的，并且是未定义的，所以R=1,D=1
url4=’http://C'，它跟上一个值属于不同记录，并且是定义的，所以R=0,D=2
对于Links.Forward这一列，在r1中有三个值，在r2中有1个值，分别是：
value1=20，它是r1中该列的第一个值，并且是定义的，所以R=0,D=2
value2=40，它跟上一个值在Links这层是相同的，并且是定义的，所以R=1,D=2
value3=60，它跟上一个值在Links这层是相同的，并且是定义的，所以R=1,D=2
value4=80，它是一条新的记录，并且是定义的，所以R=0,D=2
对于Links.Backward这一列，在r1中有一个空值，在r2中两个值，分别是：
value1=NULL，它是一条新记录，并且是未定义的，父节点Links是定义的，所以R=0,D=1
value2=10，是一条新记录，并且是定义的，所以R=0,D=2
value3=30,跟上个值共享父节点，并且是定义的，所以R=1,D=2
5.5 Parquet文件格式
Parquet文件是二进制方式存储的，文件中包含数据和元数据，可以直接进行解析。
先了解一下关于Parquet文件的几个基本概念：
行组(Row Group)：每一个行组包含一定的行数，一般对应一个HDFS文件块，Parquet读写的时候会将整个行组缓存在内存中。
列块(Column Chunk)：在一个行组中每一列保存在一个列块中，一个列块中的值都是相同类型的，不同的列块可能使用不同的算法进行压缩。
页(Page)：每一个列块划分为多个页，一个页是最小的编码的单位，在同一个列块的不同页可能使用不同的编码方式。
need-to-insert-img
Parquet文件组成：
文件开始和结束的4个字节都是Magic Code，用于校验它是否是一个Parquet文件
结束MagicCode前的Footer length是文件元数据的大小，通过该值和文件长度可以计算出元数据Footer的偏移量
再往前推是Footer文件的元数据，里面包含：
文件级别的信息：版本，Schema，Extra key/value对等
每个行组的元信息，每个行组是由多个列块组成的：
每个列块的元信息：类型，路径，编码方式，第1个数据页的位置，第1个索引页的位置，压缩的、未压缩的尺寸，额外的KV
文件中大部分内容是各个行组信息：
一个行组由多个列块组成
一个列块由多个页组成，在Parquet中有三种页：
数据页
一个页由页头、repetition levels\definition levles\valus组成
字典页
存储该列值的编码字典，每一个列块中最多包含一个字典页
索引页
用来存储当前行组下该列的索引，目前Parquet中还不支持索引页，但是在后面的版本中增加
5.6 计算时间优化
Parquet的最大价值在于，它提供了一中把IO奉献给查询需要用到的数据。主要的优化有两种：
映射下推(Project PushDown)
谓词下推(Predicate PushDown)
5.6.1 映射下推
列式存储的最大优势是映射下推，它意味着在获取表中原始数据时只需要扫描查询中需要的列。
Parquet中原生就支持映射下推，执行查询的时候可以通过Configuration传递需要读取的列的信息，在扫描一个行组时，只扫描对应的列。
除此之外，Parquet在读取数据时，会考虑列的存储是否是连接的，对于连续的列，一次读操作就可以把多个列的数据读到内存。
5.6.2 谓词下推
在RDB中谓词下推是一项非常通用的技术，通过将一些过滤条件尽可能的在最底层执行可以减少每一层交互的数据量，从而提升性能。
例如，
select count(1)
from A Join B
on A.id = B.id
where A.a > 10 and B.b < 100
SQL查询中，如果把过滤条件A.a > 10和B.b < 100分别移到TableScan的时候执行，可以大大降低Join操作的输入数据。
无论是行式存储还是列式存储，都可以做到上面提到的将一些过滤条件尽可能的在最底层执行。
但是Parquet做了更进一步的优化，它对于每个行组中的列都在存储时进行了统计信息的记录，包括最小值，最大值，空值个数。通过这些统计值和该列的过滤条件可以直接判断此行组是否需要扫描。
另外，未来还会增加Bloom Filter和Index等优化数据，更加有效的完成谓词下推。
在使用Parquet的时候可以通过如下两种策略提升查询性能：
类似于关系数据库的主键，对需要频繁过滤的列设置为有序的，这样在导入数据的时候会根据该列的顺序存储数据，这样可以最大化的利用最大值、最小值实现谓词下推。
减小行组大小和页大小，这样增加跳过整个行组的可能性，但是此时需要权衡由于压缩和编码效率下降带来的I/O负载。
六、参考
《Column-Stores vs. Row-Stores》读后感
https://www.the-paper-trail.org/post/2013-01-30-columnar-storage/
