郑州市建设厅网站,wordpress 主题大全,陵水网站建设价格,如何删除首页wordpress作者#xff1a;袁洋 | StoneData 技术架构师
审核#xff1a;王博 论文链接#xff1a;columnstoresfntdbs.pdf (harvard.edu) 列存四先驱和 MIT 知名教授 Samuel Madden 于 2013 年在某期刊上写的一篇当时列存相关技术的综述。文章还挺全面也很经典#xff0c;通过剖析三… 作者袁洋 | StoneData 技术架构师
审核王博 论文链接columnstoresfntdbs.pdf (harvard.edu) 列存四先驱和 MIT 知名教授 Samuel Madden 于 2013 年在某期刊上写的一篇当时列存相关技术的综述。文章还挺全面也很经典通过剖析三个经典的现代列存的数据库 C-store、MonetDB、VectorWise阐述了各项单独技术的来龙去脉和相辅相成的关系。 行式存储 vs 列式存储
在数据库存储引擎侧通常有两类存储模型 行式存储 NSMN-ary Storage Model 列式存储 DSMDecomposition Storage Model 1.1 NSM
一般是将一行数据完整的从头到尾连续存储超长的字段一般会单独存储行内记录逻辑地址连续多行构成一个页页的尾部通常会存储索引来解决 record 不定长时的快速查找问题。 以行为单位存储再配合以 B 树或 SS-Table 作为索引就能快速通过主键找到相应的行数据。 行式存储对于 OLTP 场景是很自然的大多数操作都以实体entity为单位即大多为 增删改查 一整行记录显然把一行数据存在物理上相邻的位置是个很好的选择。 优点 行存在 insert/update/delete/point lookup query (点查)的场景是占优的因为涉及的行数据是连续存储的理论上不存在读写放大。 缺点 在读取时由于会读取大量无效列数据譬如 select name from R where age 40那么对于每次 age 的遍历除了会将无用的其他数据一起读入每次读取 record都可能会引起 cache miss。对 cpu cache 非常不友好。 1.2 DSM
在存储时将多行数据的相同 column 连续存储在一起相同 column 的数据组成一个一个的块(Block)。 优点 列式存储非常适用于大量复杂查询的数据分析场景列式数据库相较于传统的行式数据库具有以下优点
1更高的查询效率。由于数据按列存储当需要查询某一列的数据时列式数据库只需要读取该列的数据而不需要读取整行数据因此查询速度更快。
2更好的数据压缩。由于同一列的数据类型相同因此可以采用更加有效的数据压缩方式减少存储空间的占用。
3更快的并行处理能力。列式数据库可以同时处理多个列因此可以更好地利用多核处理器和并行计算资源提高数据处理效率。 缺点 列存在更新场景明显存在缺陷
每 insert/update/delete 一行数据需要同时修改多个列(会去更新存在不同位置的 column)带来 IO 放大且为随机 IO。 1.3 PAX一个 Cache 友好高效的行列混存方案
可以看到NSM 和 DSM 都有各自的优劣所以如何将它们和优点结合起来就是 PAX 考虑的问题。 NSM 能更快速的取出一行记录这是因为一行的数据相邻保存在同一页 DSM 能更好的利用 CPU Cache 以及使用更紧凑的压缩 PAX 全称是 Partition Attributes Across它的核心思路是尝试将 DSM 的一些优点引入 NSM将两者的优点相结合。将一个页划分成多个 minipageminipage 内按列存储而一页中的各个 minipage 能组合成完整的若干 relation。
假设有 n 个 attributesPAX 就会将 page 分成 n 个 mini pages然后将第一个 attribute 的放在第一个 mini page 上面第二个放在第二个 mini page以此类推。 在每个 page 的开头会存放每个 mini page 的 offsetmini page 对于 Fixed-length attribute 的数据会使用 F-minipage 而对于 variable-length attribute 的数据则会使用 V-minipage。对于 F-minipage 来说最后会有一个 bit vector 来存放 null value。而对于 V-minipage 来说最后会保存每个每个 value 的在 mini page 里面的 offset。
一篇关于 PAX 的 paper 供大家进一步学习和研究。
Paper: https://www.vldb.org/conf/2001/P169.pdf 怎么让列式数据库更快
仅仅将数据存储在列中并不足以让基于列的存储获得全部性能。该论文中花了大量篇幅来分析几个关键的列存数据库加速技术 如下图所示 根据论文中的这些技术特性下面我们逐步分析向量化计算数据压缩延迟物化 连接优化几个部分。 向量化计算 3.1 概念
火山模型Volcano-style execution是最早的查询执行引擎也叫做迭代模型 (iterator model)或 one-tuple-at-a-time。在这种模型中查询计划是一个由 operator 组成的 DAG其中每一个 operator 包含三个函数opennextclose。Open 用于申请资源比如分配内存打开文件close 用于释放资源next 方法递归的调用子 operator 的 next 方法生成一个元组tuple即行 row 在物理上的表示。
目前主要有两种关于向量化执行引擎的实现方法 仍然使用火山模型只不过一次返回一组列。这种模型的优势是仍然使用火山模型这个优化器于执行器模型已经很成熟剩下需要的工作量就在于如何将一次一 tuple 的处理模式修改为一次向上返回一组列存行值例如100-1000 行处理方式难度相对较小 将整个模型改造成为层次型的执行模式这种模式需要将优化好的执行计划树最终转换为编译执行即一次调用下来之后每一层都完成后才向上返回数据这样能够最大程度的减少各层次节点间的调用次数提高 CPU 的有效计算效率 上图描述的就是火山模型实现的行存执行引擎与列存执行引擎其中左边代表的是当前比较流行的传统行存火山模型右边代表的是列存实现的火山模型从上图我们可以看到火山模式是从执行计划树的根节点开始向叶子节点递归调用然后有叶子节点通常是各种的扫描节点返回一条符合过滤条件的 tuple 给上层节点处理每一层节点在处理完该 tuple 之后继续网上层节点传递记录Agg 节点不是立刻往上层节点返回数据它需要计算完所有的 Tuple才能继续往上层节点返回所以这里 AGG 算子在处理好这个 Tuple 之后又会往下调用扫描算子返回下一条符合过滤条件的记录。这样处理完整个表的记录之后AGG 算子会把数据返回到上一层节点继续处理在整个过程中需要 AGG 算子缓存中间结果。右边列存执行引擎执行逻辑基本上与左边行存执行引擎一致但是每次扫描处理的是一组组以 col 组织的列数据集合这样我们最为直观的观察就是从上层节点向下层节点的调用次数少了。相应的 CPU 的利用率得到了提高另外数据被组织在一起。可以利用硬件发展带来的一些收益如 SIMD, 循环优化将所有数据加载到 CPU 的缓存当中去提高缓存命中率提升效率。在列存储与向量化执行引擎的双重优化下查询执行的速度会有一个非常巨大的飞跃大约 3-5 倍。 向量化执行流程 将查询进度控制逻辑与数据处理逻辑分开 每个操作符的 next()方法返回 N 个图元的矢量 避免产生大量中间结果
论文中阐述了一种观点在面向块和矢量化处理的视线中通过在运算符之间传递 缓存行 大小的 元组 块并且一次对多个值进行操作而不是使用传统的 一次一个元组 的迭代器列存储可以实现大幅提高缓存利用率和 CPU 效率。 3.2 向量化执行的优势
1. 降低解释开销 减少了解释的开销, 与 tuple-at-a-time 模型相比查询解释器执行的函数调用量减少了一个与矢量大小相等的系数。在 TPC-H Q1 的查询中可以将性能提高两个数量级。 2. 缓存局部性 列数据是连续的分配的内存块也是连续的所以在第一次访问时大块的内存块会被加载到高速缓存中。这使得后续访问数组中的元素变得相对较快。
3. 编译器优化的可能性
自动内存预取、触发编译器来生成 SIMD 指令、有效使用 CPU 缓冲机制
4. 并行内存访问
并行内存访问。通过无序推测生成多个并行未命中的代码的执行速度通常是非矢量化内存查找的四倍
3.5 向量化执行比传统模式的优势 减少了函数调用的开销调用次数减少 N 倍 通过调整向量大小来提高缓存局部性能力 避免分支预测提高并行内存访问速度 编译器有机会进行编译器优化可以利用 SIMD 指令集加速计算 基于块的算法优化 可以以更小的代价做 Profiling(面向性能分析开销)
适应性执行动态选择最优实现(多臂老虎机问题) 数据压缩 4.1 Compression Perspectives
同一列的数据放一起信息熵要远低于来自不同列的数据。信息熵越低数据越高度有序。 压缩算法在信息熵低 (即具有高数据值局部性) 的数据上表现更好来自同一列的值往往比来自不同列的值有更多的值局部性。value locality 的意思就是某个数据 (数据的内容或者逻辑地址) 被访问地更频繁。
通常情况下数据库系统的底线目标是性能即尽可能快地处理一个或多个查询而不是压缩率。压缩通过减少花在 I/O 上的时间来提高性能。
4.2 压缩带来的优势 按列压缩压缩率远高于按行压缩如果数据是排序的压缩率会更高 数据库系统的终极目标是性能而不是压缩率。但是数据被压缩后能减少磁盘 IO减少从内存到 CPU 带宽的使用。从而进一步提高了性能 一些压缩算法会把数据压缩为固定宽度fixed-width数组这样就可以进一步利用 SIMD 来加速 基于频率的分段压缩每一段数据有更低的信息熵 4.3 压缩算法 4.3.1 RLE, 游程长度压缩算法
RLE, 游程长度压缩算法, 是一种无损数据压缩的形式, 使用值、起始位置、运行长度三要素。其中同一数据值被存储为单一的数据值和计数而不是作为原始值存储。如果一列的前 42 个元素含有值 M也就说起始位置为 1 42 个 M 的长度 那么这 42 个元素可以被替换成 (M, 1, 42) 的三要素信息。在列式存储中由于列的数据是连续的相同值的情况很常见因此会出现较多的 RLE encoding 机会。 4.3.2 Bit-Vector Encoding 位向量编码算法
位向量编码是为每一个不同的取值生成一个位向量, 根据位向量( 串)中不同的位置取值 0 或 1 来对应并确定不同的原始值。位向量编码算法其实就是位图索引算法适用于低基数的列相对于 B 树索引它的 count,and,or 操作更有效位图索引位存放的是 0,1 的 bit相对于 B 树索引占字节数特别少,不适合 update、insert、delete 频繁的列-因为要一个数据的更新可能会导致 2 个位图向量的更新。bitmap 的思想就是数据压缩。用一个二进制 bit(0 或者 1)去标记某个元素对应的 value 这就是 bit map。适用于低基数的列相对于 B 树索引它对 count, and, o r 操作更有效位图索引位存放的是 0,1 的 bit相对于 B 树索引占字节数特别少。不适合 update、insert、delete 频繁的列因为一个数据的更新可能会导致 2 个位图向量的更新。 举例如下 4.3.3 字典编码算法
字典编码就是生成一个“原始值替代值”的对照字典。为了起到压缩的作用, 替代值的长度小于原始值的长度。存储的时候, 只存储替代值而不是原始值, 从而压缩了存储空间
字典编码算法把唯一值编入字典每一个唯一值都匹配一个序号而序号用于索引字典通过存储序号来压缩数据。如果数据表中存在大量的重复/频繁值那么使用字典编码压缩率高效果非常好。 关于字典编码的 Paper, 可以看看这个。
Paper: Dictionary Compression for a Scan-Based, Main-Memory Database System
https://publications.systems.ethz.ch/sites/default/files/publications/BernetJanickSpring2010.pdf
举例如下: 延迟物化 5.1 什么是物化
物化,即将常用元组或可能会用到的逻辑元组从实际物理存储的状态生成为实体化的元组, 也称为物化, 存储在内存中是包括一个查询结果的数据库对像它是远程数据的的本地副本是一个物理表。在随后查询时, 直接读取已经物化的元组, 以提高查询的效率。 5.2 延迟物化
而元组物化有两种方案, 分别是提前物化: 在提交查询之前物化元组; 延时物化: 尽量推迟物化元组的时间, 在查询中间的某个时刻物化元组。对于列数据库来说, 提前物化需要解压所有已经压缩的数据, 其时间和空间的开销是很大的。同时, 提前物化会涉及到很多不必要的列, 有悖列数据库按列存储、按需取用的初衷。因此, 在列数据库领域, 提出了延时物化的思想。 把从各个列中获取的数据重新组装为行的过程称之为 tuple construction延迟物化的目的就是尽可能推迟 tuple construction 的时机。把这个物化的时机尽量的拖延到整个查询生命周期的后期。 延迟物化意味着在查询执行的前一段时间内查询执行的模型不是关系代数而是基于 Column 的。 5.3 延迟物化的收益? 减少物化的 tuple 数量 降低 IO、网络、计算压力 可以在列存(压缩)数据上进行高效计算 减少内存访问带来的开销 在扫描数据相对较少的情况下需要 cache 的数据量更少此时也会提高整个计算的 cache 命中率减少 cpu 的消耗 5.4 一个 延迟物化的例子
SQL:
select name from person where id 10 and age 20 5.4.1 行存做法 从文件中读出三列的所有数据物化成行数据一行行的 person 数据。然后应用两个过滤条件id 10 and age 20Filter 之后从数据里面抽出 name 字段作为最后的结果进行 output 5.4.2 列存上延迟物化的做法
延迟物化的做法是 直接在每一个 Column 数据上分别应用过滤条件从而得到两个满足过滤条件的 bitmap 然后再把两个 bitmap 做位与操作得到同时满足两个条件的所有的 bitmap 因为最后需要的是 name 字段因此拿着这些 position 对 name 字段的数据进行过滤就得到了最终的结果 5.4.3 普通物化和延迟物化对比
这两者的权衡在于虽然延迟加载能够减少数据的加载量但需要维护原始数据的位置 这样才能找到对应行的其他列的值。然而如果筛选条件person.id 10 and person.age 20不能大量过滤数据延迟加载反而低效。 对于这种情况就需要根据一些统计信息选择合适的加载算法来最大限度的提高效率。 延迟物化带来的好处 关系代数里面的 selection 和 aggregation 都会产生一些不必要的物化操作从一种形式的 tuple, 变成另外一种形式的 tuple。如果对物化进行延迟的话可以减少物化的开销(因为要物化的字段少了)甚至直接不需要物化 如果数据是被压缩过的物化的过程就必须对数据进行解压这会影响压缩带来的好处 列式的内存组织形式对 CPU Cache 非常友好从而提高计算效率相反行式的内存组织形式因为非必要的列占用了 Cache Line 的空间Cache 效率低 块遍历的优化手段对 Column 类型的数据效果更好因为数据以 Column 形式保存在一起数据是定长的可能性更大。而如果 Row 形式保存在一起数据是定长的可能性非常小因为你一行数据里面只要有一个是非定长的比如 VARCHAR那么整行数据都是非定长的 延迟物化的缺点
延迟物化且多表 Join 连接后 许多 Join Algorithms 会对左外侧输入位置关系排序右内侧输出位置不会排序(准确的说至少有一侧不会被排序)因为以这种无序的方式从列中提取值需要为每个位置跳转存储 产生了随机访问相比顺序访问会产生较大的开销。 对左外侧输入位置关系排序也有例外对两组输入进行排序或重新分区的 Join 算法不会对左右位置列表进行排序。但无论哪种方式至少有一组输出位置不会被排序。 从下图可以看出延迟物化在列式数据库优化中可以带来巨大的收益 表连接 6.1 更加有效地表连接
Hash-join 以 Hash-join (散列连接典型连接算法) 为例column store 可以让 probe 探测表更紧凑会产生更紧凑的散列表从而在探测期间 during probing 产生更好的访问模式 a smaller hash table leads to less cache misses 更小的散列表导致了更少的缓冲区丢失 Jive-Join
Jive-Join (两次排序) 解决 Unordered positional lookups。基本思想是在我们想要提取的位置列表中添加一个额外的列这是一个密集有序递增的整数序列。
Invisible Join
在延迟物化缺点部分提到Join 后许多 Join Algorithms 会对左外侧输入位置关系排序右内侧输出位置不会排序这是因为左列中的位置通常按顺序迭代而右列中的位置会被探测以查找连接谓词匹配项。因此需要添加一个排序列。
为了解决这个问题又提出了一个新的 Join 算法Invisible Join 隐式连接。
更多 Join 实现
当然还有 BroadcastJoinLookupJoinSortJoin...
6.2 Jive-Join
对于 Join 而言运算的核心在于两表中 Joinkey 的匹配上。对于其他列数据匹配上了就复制匹配不上就丢弃。结合延迟物化匹配后再加载其他列数据从而减小不必要的 IO。
举个例子 如下 SQL
SELECT emp.age, dept.name FROM emp, dept WHERE emp.dept_id dept.id
假设原始数据值如下 根据上面延迟物化部分我们可以已知数据的查询过程中我们先抽出 emp 表的 dept_id 和 dept 表的 id 列数据进行匹配并输出匹配结果对应原表的位置信息。(黄色文字部分是指 position 指向的值 在实际 Join 中不会出现)
会得到如下的数据 然后根据输出的位置信息就可以从原始数据中抽取 age、name 列的数据得到 Join 最后的结果。 由于上图右侧输出无序如果回表查必然造成大量随机 IO 为了解决这个问题Jive Join[参考文献 Fast Joins Using Join Indices]采用了对其进行排序之后再查询即将随机 IO 转化为顺序 IO 的方法进行优化。 实现方式为在右侧表 position 列上添加一个额外的列(一个密集递增的整数序列)。 排序输出 最后为了保持原 SQL 语义的一致性我们对数据结构再次排序这次是按最初添加到连接输出的列将当前数据结构恢复为原始连接顺序以便与另一个表的连接输出相匹配 6.3 Jive-Join 进一步的优化思路 不需要完全排序整个列数据, 来减少 join 值中列输出的随机访问性能开销 存储介质被分成连续的存储块块内的随机访问比跨块的随机访问代价小得多 因此只需要在存储或其近似值上划分为可以找到这些位置的块。在每个分区内位置可以保持无序因为存储块内的随机访问要便宜得多 保证块维度的顺序访问块内的数据可以保持无序来替代全局列按精确的位置顺序访问。这个也就是一个新的概念: Radix Hash Join
https://nan01ab.github.io/2019/03/Hash-Joins.html 总结 7.1 列式存储优点 数据压缩确定一列数据的规律 查询时可以时读的数据量更少在 IO 密集型计算中获得更多的性能优势 相同类型压缩效率更高 可以针对不同类型使用不同的压缩算法。LZ4run-length encodingdelta encoding 高效的压缩可以减少磁盘 IO 数据量但是高效的压缩都必须遵循某种特殊的规律比如数据的长度类型等一致基于列式的查询数据库正好遵循这一点此外某些特别的数据压缩格式比如 RUN-Length 编码甚至可以在不做解压时便可以对数据过滤减少无关的 IO 数据选择优势大 可以选择特定的列做计算而不是读所有列 对聚合计算友好 更容易向量化 向量化基于 SIMD (single instruction multiple data) 。对于现代多核 CPU其都有能力用一条指令执行多条数据 向量化对数据格式有要求要处理的数据需要是连续内存需要明确数据类型 执行模型要求数据需要按批读取函数的调用需要明确数据类型 列存数据库本身按列存储和读取可以保证数据按批读取在内存中连续可以根据列的类型定义数据读写逻辑函数按列类型处理 更适合做延迟物化 物化: 将列数据转换为可以被计算或者输出的行数据或者内存数据结果的过程物化后的数据通常可以用来做数据过滤聚合计算Join 缓存友好节省 CPU / 内存带宽可以利用到执行计划和算子的优化例如 filter可以直接在压缩列做计算 7.2 写在最后
实际上列存数据库不只是列式存储的存储格式问题底层存储的变化往往牵一发而动全身如何适应性的修改计算引擎、存储引擎、存取方式等来达到更高更快的性能并适应不同的 workload 或者硬件发展的趋势都是基于列式存储数据库要关心的问题。
