Adbean's BlogPaper Reading: AnalyticDB-V
AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data
ABSTRACT
随着非结构化数据的爆炸性增长（例如图像，视频和音频），非结构化数据分析在真实世界应用的丰富脉络中广泛存在。许多数据库系统开始合并非结构化数据分析以满足此类需求。但是，在大多数系统中，对非结构化和结构化数据的查询通常被视为 disjoint tasks，在大多数系统中，混合查询（即涉及两种数据类型）尚未得到充分支持。
在本文中，我们在阿里巴巴（AnalyticDB-V（ADBV））提出了一种混合分析引擎，以满足这种新兴需求。ADBV 提供一个接口，该接口通过将非结构化数据转换为高维 vectors，以使用 SQL 语义来表达混合查询。ADBVA 采用 lambda 框架并利用了近似最近的邻居搜索（ANN）技术的优点来支持混合数据分析。此外，提出了一种新颖的 ANNS 算法来提高代表大量非结构化数据的大型向量的准确性。所有 ANNS 算法均在 ADBV 中作为物理运营商实施，同时提出了基于成本的优化技术，以确定有效的执行计划。对公共和内部数据集的实验结果表明，ADBV 及其有效性所取得的出色性能。ADBVHA 已成功部署在阿里巴巴云上，为各种现实世界应用提供了混合查询处理服务。
INTRODUCTION
由于智能手机，监视设备和社交媒体的流行，每天都会生成大量的非结构化数据，例如图像，视频和音频。例如，在 2019 年单身日的全球购物节期间，高达 500％的非结构化数据被纳入阿里巴巴的核心存储系统。为了促进对非结构化数据的分析，通常利用基于内容的检索系统。在这些系统中，首先将每个非结构化数据（例如，图像）转换为高维特征向量，然后在这些向量上进行后续检索。这种向量检索在各种领域都广泛，例如面部识别，人/车辆重新识别，推荐和语音识别识别。在阿里巴巴，我们还在生产系统中采用这种方法。
尽管基于内容的检索系统支持未经检测的数据分析，但在许多情况下，由于各种原因，都应 jointly queried 非结构化和结构化数据（我们称它们为混合查询）。首先，对非结构化数据的查询可能不足以描述所需的对象，其中混合查询有助于证明其表现力。例如，在淘宝（Taobao）等电子商务平台上，一个潜在的客户可以寻找价格（不到 100 美元），发货（free-shipping），评级（超过 4.5）和样式的连衣裙（视觉上类似电影明星穿着的衣服）。其次，最先进的特征矢量提取算法的准确性远非令人满意，尤其是在大型数据集上，混合查询有助于提高准确性。对于检查，当图像数量从 0.64 milion 缩放到 1200 万时，false-negative 识别率增加了 40 倍。因此，对结构化属性（例如性别，年龄，图像捕获的位置，时间戳）对矢量搜索空间缩小并有效提高准确性可以施加约束。总而言之，混合查询对大量新兴应用程序具有很高的价值。
但是，大多数现有系统不提供混合查询的 native support。开发人员必须依靠两个隔离引擎来进行混合查询处理：矢量相似性搜索引擎用于非结构化数据和用于结构化数据的数据库系统。这种做法具有固有的局限性。首先，我们必须在两个系统上实现额外的逻辑和 post-processing 后期处理步骤，以确保数据一致性和查询正确性。其次，混合查询不能联合优化，因为子查询是在两个引擎上独立执行的。
为了应对这一挑战，我们在 Alibaba Cloud 的 OLAP System AnalyticDB（ADB）内设计和实施了一个新的分析引擎，称为 AnalyticDB-V（ADBV），该引擎在 Alibaba Cloud 上进行了管理，该引擎可以管理大量功能向量和结构化数据并且本机支持混合查询。在系统的设计和开发过程中，我们遇到并解决了几个重大的挑战：
- 高维向量的实时管理。从非结构化数据中提取的特征向量通常具有极高的维数。例如，在阿里巴巴，非结构化数据的向量在许多场景中可以达到 500 多个维度，例如在线购物应用程序。此外，这些向量是实时生成的。对这些高维向量的实时管理(即 CRUD 操作)对于现有的数据库和向量搜索引擎来说是繁重的。一方面，只支持相似度搜索的在线数据库系统 (例如 Post-greSQL 和 MySQL) 仅适用于多达数十维的向量。另一方面，向量相似性搜索引擎（例如 faiss）采用 ANN（大约最近的邻居搜索）方法以离线方式处理和索引高维向量，这些方式无法处理实时更新
- 混合查询优化。混合查询为 joint execution and optimization 提供了新的机会，并考虑了特征向量和结构化属性。但是，混合查询优化本质上比现有优化更为复杂。支持 TOP-K 运营的经典优化器不必考虑准确性问题，即所有查询计划都会带来相同的结果。但是，对于混合查询，ANN（在向量上）返回近似结果，以避免进行过度搜索，因此 Top-K 操作的准确性随 ANN 方法和参数设置的选择而变化。要平衡近似结果的质量和查询处理速度，还有一项非常重要的任务
- 高扩展性和并发性。在我们的许多生产环境中，向量以极大的规模进行管理。例如，在智能城市运输方案中，我们必须每天管理超过 117 亿道路或车辆快照，每天有 1 亿个新插入的记录。此外，至少需要每秒处理 5,000 个查询，其中 90％以上是新兴的查询。在 Freshippo 超市的另一种应用程序方案中，阿里巴巴集团的数字化零售商店，8 亿 512 维矢量存储在 ADBV 中。峰值负载为每秒 4000 个查询（QPS），高于 80％的查询是混合查询。分布式体系结构对于如此大规模的工作负载至关重要。此外，必须维持大量矢量和新摄入数据的快速索引
在 ADBV，我们解决了上述挑战，并做出了以下主要贡献：
-
用于混合查询的实时分析引擎。我们提出了一种分析引擎，该引擎本地支持融合结构化和非结构化的实时更新的数据。为了满足实时需求，我们采用了带有不同 ANN 索引的 Lambda 框架，用于流层和批处理层。流层中基于邻域的 ANNS 方法支持实时插入，但会消耗大量内存。批处理层中基于编码的 ANN 方法消耗的内存较少，但需要在 construction 之前离线训练。Lambda 框架可以定期合并从流层中新摄入的数据中，并将其从分批层中。
-
一种新的 ANNS 算法。为了提高代表大量非结构化数据的大规模矢量的准确性，提出了一种新的 ANNS 索引，称为 Voronoi Graph Product Quantization (VGPQ)。与 IVFPQ 相比，该算法可以有效地缩小矢量空间中的搜索 scope。根据实证研究，VGPQ 比 IVFPQ 更有效地对 massive vectors 进行快速索引和查询更有效
-
Accuracy-aware 的基于成本的混合查询优化。在 ADBV 中，ANNS 算法被包裹为 physical operators。因此，我们可以依靠查询优化器来有效地支持混合查询过程。关系数据库中的物理运算符始终返回确切的结果。但是，这些新引入的物理运营商可能不会严格遵循关系代数，而是输出近似结果。由于近似的性质，我们提供了新的操作规则，以达到最佳的查询效率。这些规则自然嵌入了 ADBV 的优化器中
在以下各节中，我们将提供 ADBV 的详细信息。§2 介绍了混合查询和 SQL dialects 的背景。§3，§4 和§5 介绍了我们的设计和实现，即总体系统设计，矢量处理（ANNS）算法和基于准确性的基于成本的混合查询优化。实验评估是在§6 中进行的。相关工作将在§7 中讨论，并在第 8 节中得出结论。
BACKGROUND
Motivation
为了准确地检索感兴趣的记录，典型的混合查询包括特征向量上的相似性约束(从非结构化数据中提取)和结构化数据上的值约束。考虑图 1 所示的示例，目标是检索在视觉上与查询图像相似的衣服，但是是红色的。传统地，这两种约束由两个独立的系统处理。开发人员需要查询使用矢量搜索引擎（例如 Faiss，Vearch）的 Top-K 图像，同时从数据库中检索颜色信息。之后，从两个系统获得的记录结合合并以得出最终结果。
这种实践引起了额外的发展工作和构成成本。可能会遇到少于 k 记录（从矢量搜索引擎返回）成功地传递用户查询中表达的颜色或样式约束，因此无法构造顶部的结果以满足用户中明确提及的量子要求询问。因此，开发人员必须仔细设置矢量搜索引擎要检索的记录数量。此外，执行效率具有优化的巨大潜力。例如，如果只有一小部分衣服满足结构化的结构（即红色），则首先使用结构化约束来检索记录，然后直接从检索到的设置中识别出最接近的特征向量，将会更有效。因此，ADBV 的动机是解决上述问题。
ADBV 允许用户将混合查询作为 SQL 语句表示，并在无需手动调整的情况下有效地执行它。请注意，非结构化和结构化数据都可以存储在一个表中。特别是，在插入阶段将非结构化数据转换为向量（通过特征提取功能），并存储在列中。
SQL dialects
ADBV 提供灵活且易于使用的 SQL 接口。开发人员可以轻松将其应用程序移植到最小的努力中
略
SYSTEM DESIGN
ADBV 建立在阿里巴巴的 PB-scale OLAP 数据库系统 AnalyticDB 之上，该系统依赖于两个基本组件，即盘古，用于可靠和永久的分布式存储。伏羲，用于资源管理和计算作业调度。ADBV 增强了 AnalyticDB 的向量支持和混合查询功能。在本节中，我们介绍了改进矢量管理和混合查询处理的功能和有效性的关键系统设计
Architecture overview
图 2 中介绍的 ADBV 的架构，主要由三种类型的节点组成：Coordinator 协调器，Write Node, and Read Node。 Coordinators 接受，解析，优化 SQL 语句，并将其派遣以读/写节点。ADBV 采用典型的读/写解耦合，它以低查询延迟和高写入量的一致性进行了交易。因此，写节点仅用于写请求（即插入，删除和更新），而读取节点则用于精选查询。新摄入的数据在承诺后将其冲入 盘古。ADBV 在存储层（第 3.2 节）中采用 LAMBDA 框架有效地管理 vectors：streaming 层涉及实时数据插入和修改；批处理层周期从压缩新插入的向量和重建 ANN 索引。此外，ADBV 将几个昂贵的谓词 push down 到存储层，以便充分利用这些节点的 计算 能力
Lambda framework
由于搜索整个矢量数据集的复杂性是不可接受的，因此必须建立索引来降低成本。 然而，在低维中广泛使用的传统索引技术，如 KD-tree 和 ball-tree ，对于深度学习模型生成的高维向量来说效果不佳。 经验证明，此类解决方案对于高维向量表现出线性复杂性。 因此，提出了 HNSW（Hierarchical Navigable Small World）和 LSH（Locality-SensitiveHash）等算法，以近似的方式在向量上进行实时索引构建。 然而，现有的算法要么由于内存消耗大而无法处理大量数据，要么无法提供足够准确的结果。 以 HNSW 为例，它需要将索引数据和特征向量持久存储在内存中以避免磁盘 I/O，否则其性能将显着下降。 除了原始数据之外，每条记录还需要大约 400 bytes 的内存用于其索引。
我们采用 lambda 框架来解决支持实时插入的挑战。 在此框架下，ADBV 使用 HNSW 实时为新插入的向量（即增量数据）建立索引。 ADBV 根据建议的 VGPQ 算法（第 4.2 节）定期将增量数据与基线数据合并到全局索引（第 3.2.2 节）中，并丢弃 HNSW 索引。
图 3 描述了 lambda 框架，它由三层组成：批处理层、流处理层和服务层。 这些层共同处理每个传入的查询。 批处理层根据基线数据返回搜索结果（第 3.2.2 节中讨论）。 对于流层，它执行两项任务：处理数据修改（即 INSERT、DELETE 和 UPDATE），以及在增量数据上生成搜索结果。 对于 SELECT 语句，批处理层和流处理层的部分结果由协调器合并以得出最终结果。 服务层负责向批处理层和流处理层发出请求并将结果返回给客户端。 不同的层驻留在不同类型的节点中，即协调器中的服务层、读取节点中的批处理层以及读取节点和写入节点中的流层。