数据库如何理解和执行您的查询?
封面图片
本文由Angela Ni 译。
在 Milvus 中,向量查询是通过基于布尔表达式的标量过滤检索向量的过程。通过标量过滤,用户可以根据数据属性的某些条件限制查询结果。例如,如果用户查询 1990-2010 年间上映且评分高于 8.5 分的电影,那么只有属性(上映年份和评分)符合条件的电影才能被查询到。
本文章旨在探讨 Milvus 如何完成从输入查询表达式到生成查询计划和执行查询的整个查询过程。
跳转到
查询表达式
Milvus 中带有属性过滤的查询表达式采用 EBNF(Extended Backus-Naur form)语法。下图是 Milvus 中的表达规则。
表达式语法
逻辑表达式可以使用二元逻辑操作符、一元逻辑操作符、逻辑表达式和单表达式的组合来创建。由于 EBNF 语法本身具有递归性,因此逻辑表达式可以是更大逻辑表达式的组合结果或一部分。一个逻辑表达式可以包含许多子逻辑表达式。同样的规则也适用于 Milvus。如果用户需要用许多条件来筛选结果的属性,用户可以通过组合不同的逻辑操作符和表达式来创建自己的筛选条件集。
布尔表达式
上图显示了 Milvus 中布尔表达式规则的一部分。一元逻辑操作符可以添加到表达式中。目前 Milvus 只支持一元逻辑操作符 "not",表示系统需要取标量域值不满足计算结果的向量。二元逻辑操作符包括 "和 "和 "或"。单表达式包括项表达式和比较表达式。
在 Milvus 查询过程中,还支持加、减、乘、除等基本算术计算。下图展示了操作符的优先级。操作符从上到下按优先级降序排列。
优先级
Milvus 如何处理对某些胶片的查询表达式?
假设 Milvus 中存储了大量影片数据,用户想查询某些影片。举例来说,Milvus 中存储的每部影片数据都有以下五个字段:影片 ID、上映年份、影片类型、配乐和海报。在本例中,电影 ID 和上映年份的数据类型为 int64,而电影分数则为浮点数据。另外,电影海报以浮点向量格式存储,电影类型以字符串数据格式存储。值得注意的是,支持字符串数据类型是 Milvus 2.1 的一项新功能。
例如,如果用户想查询得分高于 8.5 分的电影。这些电影还必须是在 2000 年之前的十年到 2000 年之后的十年间上映的,或者它们的类型必须是喜剧片或动作片,那么用户需要输入以下谓词表达式:score > 8.5 && (2000 - 10 < release_year < 2000 + 10 || type in [comedy,action])
。
收到查询表达式后,系统将按以下优先顺序执行:
- 查询得分高于 8.5 分的电影。查询结果称为 "result1"。
- 计算 2000 - 10,得到 "result2"(1990)。
- 计算 2000 + 10,得到 "result3"(2010 年)。
- 查询
release_year
的值大于 "result2 "且小于 "result3 "的电影。也就是说,系统需要查询 1990 年至 2010 年上映的电影。查询结果称为 "result4"。 - 查询喜剧片或动作片。查询结果称为 "result5"。
- 将 "result4 "和 "result5 "合并,得到在 1990 年至 2010 年间上映或属于喜剧片或动作片类别的影片。结果称为 "result6"。
- 取 "result1 "和 "result6 "中的公共部分,得到满足所有条件的最终结果。
电影示例
生成计划 AST
Milvus 利用开源工具ANTLR(ANother Tool for Language Recognition)来生成计划 AST(抽象语法树)。ANTLR 是一种功能强大的解析器生成器,用于读取、处理、执行或翻译结构文本或二进制文件。更具体地说,ANTLR 可以生成一个解析器,用于根据预定义的语法或规则构建和行走解析树。下图是一个输入表达式为 "SP=100; "的示例。ANTLR 内置的语言识别功能 LEXER 会为输入表达式生成四个标记--"SP"、"="、"100 "和";"。然后,该工具将进一步解析这四个词素,生成相应的解析树。
解析树
走读机制是 ANTLR 工具的关键部分。它的作用是遍历所有解析树,检查每个节点是否符合语法规则,或检测某些敏感词。下图列出了一些相关的 API。由于 ANTLR 从根节点开始,通过每个子节点一直走到底部,因此无需区分解析树的行走顺序。
解析树行走器
Milvus 生成查询用 PlanAST 的方式与 ANTLR 类似。不过,使用 ANTLR 需要重新定义相当复杂的语法规则。因此,Milvus 采用了一种最普遍的规则--布尔表达式规则,并依赖于 GitHub 上开源的Expr包来查询和解析查询表达式的语法。
在带属性过滤的查询过程中,Milvus 会在接收到查询表达式后使用 Expr 提供的解析方法 ant-parser 生成一棵原始的未解计划树。我们将得到的原始计划树是一棵简单的二叉树。然后,Expr 和 Milvus 内置的优化器会对计划树进行微调。Milvus 中的优化器与前述的步行者机制颇为相似。由于 Expr 提供的计划树优化功能相当复杂,因此在很大程度上减轻了 Milvus 内置优化器的负担。最终,分析器会以递归方式分析优化后的计划树,以协议缓冲区(protobuf)的结构生成计划 AST。
计划 AST 工作流程
查询执行
查询执行的根本是执行前面步骤中生成的计划 AST。
在 Milvus 中,计划 AST 是在 proto 结构中定义的。下图是带有 protobuf 结构的信息。有六种表达式,其中二进制表达式和一元表达式可以进一步分为二进制逻辑表达式和一元逻辑表达式。
原语 1
protobuf2
下图是查询表达式的 UML 图像。它展示了每个表达式的基本类和派生类。每个类都有一个接受访问者参数的方法。这是一种典型的访问者设计模式。Milvus 使用这种模式来执行计划 AST,因为它的最大优点是用户不必对原始表达式做任何操作,而是可以直接访问模式中的某个方法来修改某些查询表达式类和相关元素。
UML
在执行计划 AST 时,Milvus 首先接收一个原型计划节点。然后,通过内部 C++ 原型解析器获得 segcore 类型的计划节点。获得这两种类型的计划节点后,Milvus 会接受一系列类访问,然后在计划节点的内部结构中进行修改和执行。最后,Milvus 对所有执行计划节点进行搜索,获得过滤后的结果。最终结果以位掩码的格式输出。位掩码是一个位数数组("0 "和 "1")。满足筛选条件的数据在位掩码中标记为 "1",不满足筛选条件的数据在位掩码中标记为 "0"。
执行工作流程
关于深度学习系列
随着 Milvus 2.0正式宣布全面上市,我们精心策划了这个 Milvus 深度剖析系列博客,对 Milvus 架构和源代码进行深入解读。本系列博客涉及的主题包括
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word