论文研读-SIMD系列-利用BMI指令进行选择下推

利用位操作指令BMI在列存中进行选择下推

Selection Pushdown in Column Stores using Bit Manipulation Instructions

列存能够提供高效的压缩能力，所以当前分析型数据库系统都基于列存储。然而，查询处理时，压缩会面临解码速率的挑战。以往研究探索了编码列上进行谓词下推，以避免解码，但这些技术仅限于特定的编码schemes和谓词，限制了实际应用。本文提出一种通用谓词下推方法，支持任意谓词，利用选择下推减少解码代价。我们方法的核心是一个快速选择操作符，能够使用位操作指令BMI（X86体系架构的指令扩展集）直接提取选定的编码值而无需解码。使用TPCH和micro-benchmark在Parquet上进行测试，结果显示针对代表性的扫描查询，我们的技术能够提高一个数量级。使用Spark进一步实现表明，即使对于涉及复杂join的端到端查询，速度也可以提高5.5倍。

其实他这里的下推指：多个谓词时，将前面谓词的过滤结果下推到后面一个谓词中，仅针对前面谓词满足条件的值先decoding然后进行后面谓词计算。话说，现在数据库的多谓词计算不都是这样吗？至少对于PgSQL和GPDB数据库是这样处理的。

该论文的价值在于通过BMI指令将过滤后的结果并行拷贝到结果寄存器中。Doris、Clickhouse、OceanBase等数据库都是通过SIMD指令并行进行谓词计算后，利用bitmap来标记哪些值符合条件，从而依次将满足条件的值拷贝到结果缓存中。这就是该论文的优势。

话不多说，我们看下该论文。

1、什么是BMI指令

BMI指令集是X86指令集架构的扩展，为了提高位操作的性能。所有的指令都是非SIMD的，在通用寄存器中进行操作。文中主要用到了PEXT（parallel bit extract）和PDEP指令。

1）PEXT：格式：PEXT r32a, r32b, r/m32。PEXT根据r/m32中指定的掩码将r32b中的比特位传输到r32a的低比特位中。

PEXT：其实是根据掩码将源寄存器值存入目标寄存器。源寄存器的高位放到目标寄存器的低位。目前寄存器连续存放。源寄存器根据mask值分散取值。

2）PDEP ：格式：PDEP r32a, r32b, r/m32，使用r/m32的掩码，将r32b中的低比特位传输并散列到r32a中：

PDEP：其实是根据掩码将源寄存器值存入目标寄存器。源寄存器的高位放到目标寄存器的低位。源寄存器值连续取，根据mask，将连续值分散存入目标寄存器。当然，也是将源寄存器高位存入目标寄存器低位。

指令的使用参考：

https://www.intel.com/content/www/us/en/docs/cpp-compiler/developer-guide-reference/2021-9/pext-u32-64.html

4、BIT-PARALLEL SELECT算子

SELECT算子将一个字节数组（由k位的值组成）和一个n位的选择bitmap作为输入。将选择bitmap中位为1的对应值提取出来，并拷贝到连续位的输出字节数组中，也就是输出字节数组仅包含满足条件的值，并且连续。

一个明显的解决方案：扫描所有bit-packed值，并一次提取出一个被选择的值。考虑到，每个值通常仅有几位，比处理器word（比如64位）要小，这样简单处理并不能充分利用处理器word的宽度，因此浪费了处理器可用的并行性。

因此本文的目标就是设计一个bit-parallel的选择算子。这就是说，该算子可同时处理被打包到一个处理器字中的所有值，并将所选定的值并行地移动到合适的位置。

因此，给定一个word的大小为w，处理n个k位值的指令复杂度位O(nk/w)。

4.1 简化的算法

图3的例子：从8个4位值选择3个值。通过不同背景色区分不同值。该算法分为2步。1）将输入的选择bitmap：11000100扩展转成成1111 1111 0000 0000 0000 1111 0000 0000。2）这样就可以使用PEXT指令将所有选择的bits拷贝到输出中了。

首先，设计了一个优雅的方式仅使用3个指令（两个PDEP和一个减法）就可以将一个bitmap转换位扩展的bitmap。扩展bitmap的方法：1）mask:0k1...0k1(该案例中mask为0001，即4-1个0和1个1)；2）通过PDEP指令将1100 0100通过mask值分散到目标寄存器中，得到low值；3）mask-1,即0001 0001 0001 0001 0001 0001 0001 0000，再将bitmap通过该值进行分散，得到hight值：

4）high - low得到扩展的bitmap。最后利用扩展的bitmap通过PEXT指令即可从values中并行选出值。

4.2 通用算法

4.1中的案例仅针对一个字节能正好能放满值的例子，即值位数为2的倍数，也就是值不会有跨边界的情况。这一节介绍，如果跨边界怎么办。

1）需要移动mask进行字节对齐。图4中，word 2中mask左移两位，因为v21的部分值还有两位。同样，word 1左移一位，v10的部分值有1位。

2）mask中的最小位必须是1，即使对应于一个值的中间位。最右边的1确保了减法指令能够扩展位图中的部分值生成1的序列。

这样就能保证扩展位的正确生成。

5、论文

2023 ACM SIGMOD Conference：

https://www.microsoft.com/en-us/research/publication/selection-pushdown-in-column-stores-using-bit-manipulation-instructions/