2020 SIGMOD:BinDex A Two-Layered Index for Fast and Robust Scan 笔记

简介: 目前的查询扫描主要归类为两种方法,一种是顺序扫描 如全表扫描,一种是通过索引扫描 如b-tree等。1. 顺序扫描可能需要访问大量的无用的数据,特别是当选择率低的时候。2. 索引扫描在选择率较高的时候,可能会导致大量的随机内存访问。这些都会导致性能的下降,所以在执行查询操作时,需要根据具体的查询情况(如选择率的高低),选择合适的方法(选择顺序扫描,还是索引扫描)用于查询。但随着数据库查询负载变得复杂,很难去选择合适的方法应对特定的查询(到底是选顺序扫描?还是索引扫描?)。因此本文提出了一种新的索引方案—BinDex(后面简称BD),可在不同的选择率情况下,同样能够快速地进行查询。BinDe

所以,BD的目标有两个:

  1. 如何减少 像顺序扫描那样访问大量的无用的数据(在低选择率的情况下)
  2. 如何减少 像索引扫描那样,带来的大量随机内存访问(在高选择率的情况下)
  3. 如何适用于所有的选择率场景?

背景知识

  1. 本文的Binning是指将多个属性值划分到不想交的多个范围当中,然后使用是一个bit vetcor(bit map→0-1组成的数组)来代表每个范围。值在这个范围内的标为1,不在则标为0 。

BinDex overview

本文介绍一下Bindex的结构:

1. BinDex的数据结构

virtual value space:注意这只是一个虚拟的结构,并没有真正存放在内存中(构建完之后就丢弃了)。其中存放的是按升序排好的N个元素。在原来的base data数据列中仍然是没有顺序的。
virtual areas:根据virtual value space中的元素划分为K个分区,每个分区包含N/K个排好序的元素。如这里的A1,A2。。每个Ai都包含4个值。每个Ai都作为一个bin,后续会用到。
基于上述两个虚拟的结构,设有K个Virtual area(k个bin),在BD中存在三个主要数据结构:Area Map,a set of filter bit vector,Position Array。如上图
Area Map:map S = {S1,S2,S3..Sk-1},Si对应着Ai+1,如这里的S1对应着A2。每个Si包含(value,count)这样一对值,如其中Si.value表示对应的Ai+1的第一个起始位置的值,Si.count表示Ai+1之前(A1到Ai)有多少个元素。如这里的S1包含(54,4),则54表示A2的第一个元素值为54,A2之前(A1)有个4个元素。若常量c满足,Si-1.value ≤ c < Si.value,则c落在Ai这个区间上。后面会经常用到这个结论来定位区间。
Filter Layer:第一层由a set of filter bit vector一组bit的vector组成,这些vector用于生成扫描的大概结果。基于k个virtual areas,生成k-1的filter bit vector {F1,F2...Fk-1}。即F1→A1,F2→A2...。如F1表示值落在A1中的结果(0≤x<52),对应的位置下标(在position array中)在F1中相应的位置设置为1。最终会生成K-1个bit vector,则进行谓词评估时,选择最接近结果的一个候选的vector(后面推导公式),这个vector中只有一小部分的值需要进行矫正。
Refine Layer:第二层是由Position Array组成。Position Array是基于上面提到的virtual value space中排好序的值的下标组成。该层的作用是将第一层生成的bit vector中某些需要矫正的值进行矫正,以生成最终的结果。矫正流程是这样的,首先通过对Area Map进行二分查找,定位到需要矫正的某个Virtual Area(即分区范围)。然后通过某个Virtual Area对应的Position Array一部分进行二分查找,取出Position Array中的下标,然后根据该下标在(Base Data)原来的数据列取出下标对应的值进行比较,找出需要矫正的值的下标(也即在bit vector中0-1的位置)。

相关文章
|
3月前
|
机器学习/深度学习 算法
【文献学习】Meta-Learning to Communicate: Fast End-to-End Training for Fading Channels
把学习如何在衰落的噪声信道上进行通信的过程公式化为对自动编码器的无监督训练。该自动编码器由编码器,信道和解码器的级联组成。
41 2
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(7)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(7)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals  for 3D Lookup Tables on Real-time  Image Enhancement(7)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(2)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(2)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(11)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(11)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(5)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(5)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(6)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(6)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(10)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(10)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(9)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(9)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(3)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(3)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(13)
带你读《2022技术人的百宝黑皮书》——AdaInt: Learning Adaptive Intervals for 3D Lookup Tables on Real-time Image Enhancement(13)