编者按：本文详细介绍 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作为具体形式。
完整版视频讲解请戳：https://www.bilibili.com/video/BV1h44y1v7S8/
如果你在使用的过程中，对 Milvus 有任何改进或建议，欢迎在 GitHub 或者各种官方渠道和我们保持联系～
Zilliz 以重新定义数据科学为愿景，致力于打造一家全球领先的开源技术创新公司，并通过开源和云原生解决方案为企业解锁非结构化数据的隐藏价值。
Zilliz 构建了 Milvus 向量数据库，以加快下一代数据平台的发展。Milvus 数据库是 LF AI & Data 基金会的毕业项目，能够管理大量非结构化数据集，在新药发现、推荐系统、聊天机器人等方面具有广泛的应用。
