BinDex: A Two-Layered Index for Fast and Robust Scans
在现代分析数据库系统中，数据扫描操作的性能对查询执行的性能至关重要。现有的扫描方法可分为索引扫描和顺序扫描。然而，这两种方法都有固有的低效率。事实上，顺序扫描可能需要访问大量不需要的数据，特别是在选择性较低的查询中。相反，当查询选择性很高时，索引扫描可能涉及大量昂贵的随机内存访问。此外，随着数据库查询工作负载的日益复杂，很难预测哪种方法更适合特定的查询。
为了在所有选择项下获得快速且鲁棒的扫描，提出了一种基于分箱位图的双层索引结构BinDex，用于显著加速内存列存储的扫描操作。BinDex的第一层由一组分箱位图组成，它过滤掉了列中大多数不需要的值。第二层提供一些辅助信息来纠正有错误值的比特位。通过改变第一层位向量的数量，BinDex可以在内存空间和性能之间做出权衡。实验结果表明，与B+树相比，BinDex具有更好的性能和更少的内存开销。通过扩大内存空间，BinDex可以获得高达2.9倍的性能提升，无需在顺序扫描或索引扫描之间进行选择。
背景：1）在这种情况下，因为满足谓词的值可能散布在所有列上，索引扫描可能涉及对基本数据和索引数据结构的多次随机内存访问。众所周知，随机存储器访问的操作时间比顺序存储器访问的操作时间大一个数量级。因此，随机访问的开销会抵消顺序扫描在选择性变高时避免访问不必要数据所带来的好处，而顺序扫描的性能将优于索引扫描。总的来说，索引扫描和顺序扫描都有其固有的低效率。
总之：如果存在大量的满足查询条件的对象，他们大部分会散列在不同的磁盘列上，导致index-based方法的性能时间对大于顺序扫描的时间
方法：
我们提出了BinDex，这是一个两层索引，它通过采用现有索引扫描和顺序扫描的主要优点，在所有选择条件下健壮地显著提高了内存列存储的扫描性能。
BinDex的主要思想是:(1)避免访问大多数不需要的、不满足谓词的值;(2)避免或减轻随机内存访问造成的开销。
为了实现这些目标，BinDex采用了一个两层的数据结构，两层协同工作来执行扫描操作。BinDex的第一层使用位图和分箱。分箱是一种将属性值划分为若干范围的技术，并使用位向量来表示每个范围。
在BinDex中，第二层使用一些辅助信息以较低的开销对所选位向量进行校正。 具体来说，第二层按顺序存储所有rowid，其对应值按升序排列
这两层紧密协作以提高扫描操作的总体性能。
bindex的一个重要特征是它能够在性能和内存使用之间进行权衡。由于位向量的数量较多，第二层需要探测的值较少，这将带来更高的性能，但更大的内存使用量。我们引入内存空间作为扫描方法选择的主要维度。
BinDex Data Structure
1. virtual value space
用BinDex索引的列有一个virtual value space，其中所有值都按升序排序。每个虚拟区域作为一个箱子，包含大约N/K个排序值。在图3中，虚拟值空间中的16个值被划分为4个虚拟区域，每个虚拟区域包含4个值。请注意，列中的值仍然以原始顺序存储，其中虚拟值空间只是BinDex中的一个概念，并不是单独存储的。
基于virtual value space，BinDex中主要有三种数据结构，即区域图、一组滤波位向量和位置数组。
2.
The first layer ofBinDex is called filter layer
它利用二进制来构造一组位向量。位向量用于为谓词生成草稿扫描结果。基于虚拟区域，滤波层由k−1个滤波位向量组成，记为F = {F1, F2，…}。第i个滤波位向量Fi是一个由n个比特组成的保序数组，如果对应的值小于Si .value，则将滤波器位向量Fi中的一个比特置为1
The second layer is called refine layer
第二层称为细化层。它对来自滤波层的草稿结果进行细化和修正，以交付最终结果位向量。在细化层中，虚拟值空间中所有值的rowid依次存储在一个称为位置数组的数据结构中。在候选结果位向量中，虚拟区域中只有部分值不满足谓词。
总的来说，BinDex保持了传统索引的优点，因为它避免了访问大多数不满足过滤器层谓词的数据。细化层通过重新组织数据的rowid以进行顺序访问，减轻了随机内存访问的开销。这两层紧密协作以加速扫描操作
EXPERIMENTAL ANALYSIS
Benchmark 在实验中，我们创建了一个表，每列有10亿个值。均匀负载和偏斜负载都被用于评估。1）均匀工作负载，值是在[0,2k)之间均匀分布的整数，其中k是代码宽度，范围从4位到32位。2）偏斜工作负载中的Zipf分布。
1. Performance with Uniform Data Distribution
图5比较了BinDex与其他方法在不同代码宽度下的选择性。对于所有工作负载，BinDex明显优于所有竞争对手的方法。例如，对于32位代码宽度，BinDex的性能分别是Column sketch、Byteslice和Zone map的2.1倍、2.9倍和5.6倍。
2. Performance with Skewed Data Distributions
倾斜系数从zipf = 0(均匀分布)到zipf = 2(严重倾斜分布)不等
3. Other Operators
3. TPC-H Evaluation
我们将BinDex集成到MonetDB中，并在TPC-H基准测试集上对其性能改进进行了评估。
图15比较了BinDex带来的性能提升。在TPC-H测试集上，与原始的MonetDB相比，使用BinDex的MonetDB在Q1和Q6上分别取得了4.9%和7.1倍的性能提升。由于Q1的大部分查询执行时间花费在执行聚合上，因此其性能提升并不明显。相比之下，对于Q6，更多的时间花在执行扫描上，因此有更高的性能提升。