标题：面向结构化和非结构化数据混合查询的分析引擎

编者的总结

1. 本文设计了一套标量向量综合查询的完整解决方案，从存储到查询，包括索引和查询优化技术。文章质量很高。
2. 改进了PQ的索引方式，做的粒度更细了。
3. 归纳了4种混合查询的执行：暴搜、筛选后暴搜量化码、筛选后PQ搜索、PQ搜索后再筛选，做了一定的代价分析。

编者的思考

1. VGPQ似乎将PQ和上层的索引彻底分开来看待了，仅把PQ当做一个能做近似距离计算的压缩技术来使用。但实际上PQ也是用k-means来做的，所以索引结构VGPQ本身可以利用PQ的Centroids，不需要自己额外去做k-means。这样最终就不需要存储那么多PQ code了。【不知道是否自己理解有误，欢迎大佬指正】
2. 若离query距离较近的点不满足筛选条件，本文提出的第三种和第四种物理执行计划都会有些问题，如何通过代价评估避免尚不清楚。
3. 超参选择中的accuracy-aware没有讲的很清楚，什么样的参数组合能满足accuracy的条件，这个条件具体怎么来定的不太清楚。实际查询时候是平滑地，根据query来定的超参选择空间，还是默认几套固定参数来选。如何去做智能参数调控是一个非常有意义的问题。
4. 实验方面，不清楚是否是首先做了k-means partition然后测定的，正如文中所说，通过将向量k-means partition在实践中并不常用。

1. INTRODUCTION

• 本文重点关注的问题是标量向量联合查询，查询模式如下图所示。
• 作为一篇Industrial track的文章，本文可以理解为ADB的增强版，如何在现有的OLAP数仓上引入对向量的支持，包括存储、查询、索引、优化等等。这一部分目前的学术和工业界仍然是个空缺。
• 作者总结本文的核心技术挑战有以下三点：
  1. 高位向量的实时数据管理；
  2. 混合查询优化；
  3. 扩展性和并发度，即性能方面；
• 与之对应，本文的技术贡献也有三点：
  1. 介绍了ADBV的数据管理流程，一个lambda架构；
  2. 改良了IVFPQ算法，提高了性能；
  3. 设计了面向准确性的基于代价的混合查询优化。

image.png

2. SQL dialects

在传统数仓中引入向量数据，首先是设计SQL接口。这一部分其实非常自然，包括增删改查。下图放了一个查询的推荐式SQL。

image.png

3. SYSTEM DESIGN

3.1 Architecture overview

• 批量数据和索引都放在分布式文件系统Pangu上面（类似HDFS），另有一个资源管理和任务调度器Fuxi（类似Yarn）；
• coordinator负责接收请求，分发任务，回收结果等等；

• 写节点负责增删改，读节点专门负责查。

  
  image.png
• 存储方面采用一个lambda架构，将实时侧和离线侧分开处理；
• 增删改的请求会落入实时侧，在内存维护向量数据和一个图索引HNSW（图索引可以流式支持读和写请求），以及一个bitset来管理删除的数据；
• 实时侧的索引会周期性地封装，然后离线整合入批处理侧的VGPQ索引（本文提出）；
  • 注意封装时会立即生成一个新的HNSW用以接收新的向量数据，老版本先留在内存慢慢去merge，此时查询到来两个HNSW都要去查。
• 读请求由两侧共同完成，实时侧查询HNSW，离线侧查PQ，最后整合结果；不过实时侧由于数据量很少，查询速度是很快的，在代价评估时可以忽略。
• 实时侧读写请求都要接收，所以同时由读节点和写节点共同服务；离线侧不需要服务写请求，因此只位于读节点。

image.png

4. VECTOR PROCESSING ALGORITHMS

从内存消耗方面考虑，批量数据的索引选择是一个改良版PQ。
PQ方面的介绍可以参考我这篇博客https://www.jianshu.com/p/533ac746748b。

4.2 Voronoi graph product quantization

• 本文对PQ的改造思想也比较简单：PQ会定位Query所在的和最近邻的几个Voroni cells，然后扫描其中的数据点算近似距离；VGPQ则认为没有必要把这些Cell内的点全搜一遍，只搜靠近query的几个subcells即可。
  • 如何划分subcells呢？首先找到和当前centroid C0最近的几个Centroids，某个点插进来时，计算C0和Ck连线中点的距离，选择最近的一个，即坐落在一个subcell里面。【注意图中黑色线段上的点距离周围两个centroid距离相等】

• VGPQ本质上就是对Voroni diagram做了更细一些的空间划分。【编者注：但注意，实际上我们不能完全知道一个cell到底和几个其他cell相邻，只能定义为一个参数，然后人工划分为几个subcells。理想情况如图中所示，但实际有可能出现某个cell和当前Cell在空间上不相邻，比如C7是C1的邻居，但和C0不相邻的情况出现】

  
  image.png
• VGPQ的具体存储见下图，整体布局是个倒排链表（Indexing data），每个cell内部划分为和邻居接壤的若干subcell，每个subcell内部为若干磁盘page的指针，page里面包含固定数量的PQ Code。【编者注：个人理解这里的PQ code是单独的一套codebook和编码，图中所划分区域是在pq之上额外做了一层K-means】

• 同时额外存储一个向量id和PQ code的双向对应表，方便查询时和标量属性对应。

  
  image.png
  

  如下是索引构建的伪码：

  
  image.png
• 索引查询部分则是以subcell为单位的，首先找到若干最近的centroids，再在这些centroids中，选出和qeury较近的subcells，以此子集作为查询候选集。

5. HYBRID QUERY OPTIMIZATION

本节讲向量和标量向量混合查询时的查询优化问题。示例query如下。

image.png

• 逻辑计划很简单，如下图，首先筛选出合适的tuple（Scan node），然后投影算距离，最终排序取topk。

• 核心问题在于Scan node如何设计，如何和VGPQ相结合。

  
  image.png
• scan node的物理查询计划如下图，提供了四种可选方案。

1. 第一种直接走标量的B-tree索引，选出所有标量满足条件的tuple，算距离，取topK。这种方法小批量数据还可以，而且能给出精确结果；但满足条件的数据量一旦变大，用于取数的I/O量将会变得非常多，则延迟极大。
2. 第二种是在scan node内部，首先走标量的B-tree索引，对于每个满足条件的tuple，用双向对应表取出PQ码，计算近似距离，然后取出比个tuple，返回给上层做具体的距离计算和排序。
   • 相比于第一种是把距离计算改成了PQ码的计算，适合数据量稍大的情况。
3. 第三种也是首先通过标量过滤，但是直接进入VGPQ的搜索，只不过在取PQ code的时候验证一下是否有标记，满足条件的再取。
   • 由于使用了索引，这种方法的速度将明显提升，但潜在的问题在于，如果库里和query较近的数据点都不满足筛选条件，满足筛选条件都较远时就比较麻烦，会逐步退化为第二种计划。
4. 第四种最为激进，首先通过VGPQ做了“过度”的kNN，然后进行属性筛选。
   • 由于首先使用了索引，所以无需生成bitmap，后续操作的数据量基数也大大减少，速度是最快的。

   • 不过和第三种有相似的问题，面临的后果也比第三种更严重。第三种尚可以不断向远处搜索满足候选集基数，第四种则无法弥补。

     
     image.png

5.2 Cost model for optimization

作者根据上述四种方案，设计了代价模型，如下图。

image.png

模型很简单，但关键是在查询时要确定模型中的参数，主要是下面3个。

• 即第三种和第四种方法到底有搜多少subcells？

• 以及除暴搜外三种方法要额外准备多少候选集？

  
  image.png

5.3 Accuracy-aware hyperparameter tuning

• 要确定这三个参数，和属性筛选过后的数据量非常相关，大抵来说，满足条件的数据如果特别少，可以选第一种，多一些选第二种，然后是第三种和第四种。
• 如何知道这个数据量可以采用经典的基数估计算法。
• 实际上，仅凭这个基数去选的话有些粗糙，本文的做法是按照数据量分成四个桶，每个桶内离线的去做参数搜索（grid search），找最优的超参数，再评估哪个方案代价最低而选择。
• 参数的组合选择要满足精度的要求，但是如何估计精度本文没有详细展开。

6. EXPERIMENTS

6.2 VGPQ

• VGPQ相比于IVFPQ构建速度和查询性能略有提升。

  
  image.png
  image.png

6.4 Hybrid query optimization

从图中看出在任何精度限制下，ADBV的参数选择都是不错的，而且CBO确实可以定位到最快的物理计划；

image.png

6.6 Scalability and mixed read & write

• 可伸缩性还是很强的

  
  image.png