Milvus 向量数据库如何实现属性过滤

Zilliz RDS

发布于 2022-05-25 16:37:32

1.4K0

发布于 2022-05-25 16:37:32

文章被收录于专栏：Reinvent Data ScienceReinvent Data Science

编者按：本文详细介绍 Milvus 2.0 如何对查询节点的数据进行管理，以及如何提供查询能力。

查询表达式的文法规则
- Milvus 支持的查询表达式
- 底层操作服务及具体表达式
查询语法的生成
- 开源工具 ANTLR 介绍
- PlanAST generation
语法树的解释和执行
- PlanAST & Expr definition
- PlanAST execution

查询表达式的文法规则

Milvus 支持的查询表达式

如下图所示，Milvus 运用 EBNF 语法，此处用等式和语法图体现了 Milvus 所支持的查询表达式的整体规则。

表达式 LogicalExpr 有四种组合来进行表示，比如通过二元的逻辑运算符，在逻辑表达式前加一元的逻辑运算符，或者用一些比较简单的 Single Expr 等。

由于 EBNF 本身就是一个递归的结构，LogicalExpr 既可以是这四条组合起来的整体，也可以是其中单独的某个节点，并且可以继续嵌套下去。也就是说，Milvus 支持的表达式规则是可以无限的递归嵌套的。如果有很多属性需要过滤，就可以通过不同的组合和嵌套，进而表示出需要的过滤条件。

底层操作服务及具体表达式

上图是前文提到的几种表达式。首先可以在表达式前面加单元的逻辑运算符，目前 Milvus 支持的是添加 “not”，表示在表达式做出计算以后取它的非。其次二元逻辑运算符就是与和或的两种不同表现方法。然后 Single Expr 目前实现的是 Term 和 Compare 。

另外如基本的加减乘除等其他运算也是支持的。下图是操作服务的优先级，由 1 - 9 递减。

查询语法的生成

开源工具 ANTLR 介绍

ANTLR 可以理解为解析器或者生成器，它能够对结构化文本或者二进制文件做读处理，包括执行和翻译的过程。具体来说，ANTLR 可以根据定义的文法规则进行解析，也可以生成解析器来构建解析数；同时它内部也提供了 WALKER 的一些 API，可以帮助遍历解析数。例如图中的表达式 “SP =100;" ，ANTLR 自带的语言识别器 LEXER 会生成四个 token，再各自进行解析生成 Parse-Tree。

其中比较重要的功能是给生成的 Parse-Tree 提供了 WALKER 的机制，通过 WALKER 对这解析数进行遍历。比如每个节点是否符合文法规则、单词有无涉及敏感词汇，都可以得到合法性检查。从右边列出的 Parse-Tree 遍历的 API 可以看出，ANTLR 从根节点一直到最末端的子节点，是按照一种深度遍历的顺序来进行遍历的，由此也不需要人为区分多叉树的前序、中序、后序，直接看API即可。

PlanAST generation

Milvus 的运作方法和 ANTLR 较为相似，但后者比较原始化，需要根据需求重新定义相对复杂的文法规则。Milvus 使用的 expression 这种同样常见的语法规则，并且依靠 GitHub上 ant-expr 这一开源工具来实现生成语法的查询与解析。

首先用户会传过来一个表达式 expression ，然后通过 ant-parser（这个包含在 ant-expr 里）的 Parse 方法，可以生成一个比较原始的 Unsolved Plantree 。就是前面提及的通过四大分析和简单的 Parse 后生成一个简单的二叉树，这个二叉树都是 ant-expr 内部的一些结构来表示。接下来对这个 Plantree 做一些 optimizer ，这个 optimizer 是 Milvus 自己实现的。类似于前面讲的 WALKER 的机制，遍历并且给每种节点实现一些优化器。由于 ant-expr 本身生成的优化树功能已经较好，对后续做执行、解析都比较友好，此处的 optimizer 工作也较为简单。

最后一个这个虚线节点的 analyzer 过程是将已经优化好的 Plantree 进行递归遍历分析。在二叉树的遍历过程中，每个节点对应到定义的 protobuf 的语法树的结构，进而生成一个 protobuf 结构的一个 plan AST （abstract syntax tree）。

语法树的解释和执行

PlanAST & Expr definition

Milvus 里定义了一种 proto 结构来表示前文提及的 plan AST 抽象语法树。如图中右上角定义的一个 protobuf 结构的 message，查询方式就是通过 expression 得到，且 Expr 有六种选择，其中 BinaryExpr 和 UnaryExpr 存在进一步递归的 LogicalExpr。

上图为表达式的一个 UML 的图，是 C++ 中根据 proto 结构去实现类的继承关系结构图，包含各个 Expr 的基类与派生类。每个类下面都实现了一个 accept 的方法，接受的是 visitor 的参数。这就是典型的访问者设计模式（Visitor design pattern），以此对前面生成的查询语法树进行遍历的执行。这一模式的优势在于用户不需要对 Expr 原始进行操作，可以直接通过访问的方法对其中一些具体的类与元素进行修改。

PlanAST execution

上图总结了查询语法树执行的工作流程。首先从 C++ 接收到一个 proto 类型的 PlanNode，经过 C++ 内部的 ProtoParse 得到 segcore 类型的 PlanNode。在此基础上，通过 accept 的方法接受一系列的访问者类，再对 PlanNode 内部的结构进行修改、执行。最后对每个具体的ExecPlanNode进行递归遍历，得到过滤的结果 Filtered_result，以下图的Bitmap作为具体形式。