高级数据库二十二：矢量化运行（二）

谁践踏了优雅 2022-06-01 01:06 155阅读 0赞

# Vectorized Execution (Part II) #

上一次将的哥大的论文的矢量化算法在没有四五个SIMD寄存器的情况下是没法运行的。因为DBMS需要将64位的地址和64位的数据存入寄存器

考虑到数据压缩技术，我们不能改变64位的地址，但是我们不一定要全部存储64位的数据。

这样产生的问题是，压缩数据的位宽不一定自然地适合SIMD寄存器插槽。如你压缩前128位的寄存器存储了4个32位的数据，压缩后变成了64+12位，所以有一部分空间被浪费了。

这意味着DBMS必须做额外的工作来将数据转换成适当的格式。

## [BITWEAVING][] ##

我们上次说过，DBMS希望能够充分地利用lane。

Bitweaving是列数据库的替代存储布局，旨在使用SIMD对压缩数据进行有效的谓词评估。

*  顺序保留字典编码。
 *  位级并行化。
 *  只需要通用指令（不需要scatter/gather）

### 方法1：水平 ###

*  位级面向行的存储

![Image 1][]

对于整个存储，我们假设这是8位，实际也可以是64位。

排序顺序是按列顺序来的。注意图中t0、t1、t2的排序。

![Image 1][]

对于一个向量，只有两个tuple，所以只要执行两个比较即可。这儿没有用到任何SIMD的操作。

只需要三个操作就能够得到结果；适用于任何长度；论文中有别的操作的讲解。

![Image 1][]

那么我们对所有的数据都采用这样的操作。最简单的办法是写循环。

![Image 1][]

但是用到了矢量化的一些方法，就可以更加简单地得到mask。

SIMD比较运算符产生一个mask码，指定哪些元组满足限制。必须将其转换成偏置/位置。

*  方法1：扫描
 *  方法＃2：预计算位置表，通过暴力构造得出一个类hash表，以mask码作为key直接得出位置信息。

![Image 1][]

### 方法2：垂直 ###

*  位级的面向列的存储

![Image 1][]

每一列是一个数据。

![Image 1][]

对于如上的SQL语句，将常数平铺，并和向量进行SIMD比较，得出了第一位的mask码。

然后类似的方式处理第二位，并和第一位的mask码进行逻辑且操作。可以像在BitMap索引中一样执行剪枝操作。

所以跳过了最后一位数字。

### 性能比较 ###

![Image 1][]

## [HYPER – DATA BLOCKS][HYPER _ DATA BLOCKS] ##

在一个高层次上，BitWeaving本质上是一个BitMap索引。这对OLAP很好，因为是可以很快地进行范围查询。但是对OLTP不友好，尽管有冷热数据分离的方法，但是如果有人就要访问冷数据，这样就会造成一些坏影响。

如何压缩数据的方式仍然允许有效的点查询？

单独确定每个块的最佳合适压缩方案。

*  热元组未压缩存储（OLTP）
 *  冷元组存储在压缩的数据块（OLAP）

每个数据块使用其元组的最佳方案进行压缩。

多个存储布局和压缩方案意味着DBMS必须为每个查询计划生成多个特殊的代码路径。

这增加了每个查询的编译时间和查询计划缓存的总大小。

压缩数据：矢量化执行

*  使用Vectorwise中的预编译的代码。
 *  对每种格式都预编译一段，应该是50+个。

未压缩的数据：LLVM编译

*  数据总是以相同的格式存储，因此只需要编译一条代码路径。

[BITWEAVING]: http://15721.courses.cs.cmu.edu/spring2016/papers/li-sigmod2013.pdf
[Image 1]: 
[HYPER _ DATA BLOCKS]: https://dl.acm.org/citation.cfm?id=2882925

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

相关谷粒商城高级篇 (二十二) --------- 支付

目录一、加密二、什么是公钥、私钥、加密、签名和验签？三、支付宝官方demo测试四、支付宝支付流程五、内网穿透 ------

谁践踏了优雅/ 2024年04月06日 12:30/ 0 赞/ 41 阅读

相关十二.JPQL高级查询

一. criteria查询：编译期发现错误 select u from user u where u.old>20 //拼装其工厂 CriteriaB

╰半橙微兮°/ 2022年06月15日 23:07/ 0 赞/ 190 阅读

相关高级数据库十六：查询优化器（二）

Optimizer Implementation(Part II) 在这儿解释一下，逻辑查询计划或者逻辑计划指的是关系代数层面的查询语句；物理查询计划或者物理计划指的是具

客官°小女子只卖身不卖艺/ 2022年06月02日 06:55/ 0 赞/ 211 阅读

相关高级数据库十二：数据库压缩

Database Compression 背景如果数据库需要从硬盘中获得数据，那么数据的I/O操作才是数据库的瓶颈。所以需要对数据进行压缩。内存中的数据库管理

Dear 丶/ 2022年06月02日 00:49/ 0 赞/ 159 阅读

相关高级数据库二十五：不易失内存数据库

Non-Volatile Memory Databases 背景新兴的存储技术提供像DRAM一样的低延迟读取/写入，但具有永久写入和大容量等类似SSD的特性。

小灰灰/ 2022年06月01日 01:54/ 0 赞/ 236 阅读

相关高级数据库二十二：矢量化运行（二）

Vectorized Execution (Part II) 上一次将的哥大的论文的矢量化算法在没有四五个SIMD寄存器的情况下是没法运行的。因为DBMS需要将64位的地

谁践踏了优雅/ 2022年06月01日 01:06/ 0 赞/ 156 阅读

相关高级数据库二十二：矢量化运行

Vectorized Execution (Part I) 说实话，这节课有点没听明白。上节课说到了通过矢量化来加速查询的优化，需要这么做的原因是： 1. 构建一

布满荆棘的人生/ 2022年06月01日 00:58/ 0 赞/ 136 阅读

相关高级数据库二十：并行JOIN算法（Sorting）

Parallel Join Algorithms (Sorting) 背景关于Join的其他背景可以查看上一篇讲[Hash Join][]的文章。 SINGL

我会带着你远行/ 2022年05月31日 23:35/ 0 赞/ 213 阅读

相关 oracle sql 高级编程学习笔记（二十二)

一、model 空值 model 子句存在空值的原因有两个 1、单员格存在，但值为空 2、单元格不存在 1、实例演示 nav select pro

曾经终败给现在/ 2022年05月12日 04:36/ 0 赞/ 188 阅读

相关 MongoDB数据库（二：高级操作）

练习一、完成使用Java代码连接MOngoDB，创建集合，获取集合，插入文档，检索所有文档，更新文档，删除第一个文档。 a）连接MOngoDB ![watermark

缺乏、安全感/ 2022年01月28日 10:21/ 0 赞/ 174 阅读