编者按:本文详细介绍 Milvus 2.0 如何对查询节点的数据进行管理,以及如何提供查询能力。
如下图所示,Milvus 运用 EBNF 语法,此处用等式和语法图体现了 Milvus 所支持的查询表达式的整体规则。
表达式 LogicalExpr 有四种组合来进行表示,比如通过二元的逻辑运算符,在逻辑表达式前加一元的逻辑运算符,或者用一些比较简单的 Single Expr 等。
由于 EBNF 本身就是一个递归的结构,LogicalExpr 既可以是这四条组合起来的整体,也可以是其中单独的某个节点,并且可以继续嵌套下去。也就是说,Milvus 支持的表达式规则是可以无限的递归嵌套的。如果有很多属性需要过滤,就可以通过不同的组合和嵌套,进而表示出需要的过滤条件。
上图是前文提到的几种表达式。首先可以在表达式前面加单元的逻辑运算符,目前 Milvus 支持的是添加 “not”,表示在表达式做出计算以后取它的非。其次二元逻辑运算符就是与和或的两种不同表现方法。然后 Single Expr 目前实现的是 Term 和 Compare 。
另外如基本的加减乘除等其他运算也是支持的。下图是操作服务的优先级,由 1 - 9 递减。
ANTLR 可以理解为解析器或者生成器,它能够对结构化文本或者二进制文件做读处理,包括执行和翻译的过程。具体来说,ANTLR 可以根据定义的文法规则进行解析,也可以生成解析器来构建解析数;同时它内部也提供了 WALKER 的一些 API,可以帮助遍历解析数。例如图中的表达式 “SP =100;" ,ANTLR 自带的语言识别器 LEXER 会生成四个 token,再各自进行解析生成 Parse-Tree。
其中比较重要的功能是给生成的 Parse-Tree 提供了 WALKER 的机制,通过 WALKER 对这解析数进行遍历。比如每个节点是否符合文法规则、单词有无涉及敏感词汇,都可以得到合法性检查。从右边列出的 Parse-Tree 遍历的 API 可以看出,ANTLR 从 根节点一直到最末端的子节点,是按照一种深度遍历的顺序来进行遍历的,由此也不需要人为区分多叉树的前序、中序、后序,直接看API即可。
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)。
Milvus 里定义了一种 proto 结构来表示前文提及的 plan AST 抽象语法树。如图中右上角定义的一个 protobuf 结构的 message,查询方式就是通过 expression 得到,且 Expr 有六种选择,其中 BinaryExpr 和 UnaryExpr 存在进一步递归的 LogicalExpr。
上图为表达式的一个 UML 的图,是 C++ 中根据 proto 结构去实现类的继承关系结构图,包含各个 Expr 的基类与派生类。每个类下面都实现了一个 accept 的方法,接受的是 visitor 的参数。这就是典型的访问者设计模式(Visitor design pattern),以此对前面生成的查询语法树进行遍历的执行。这一模式的优势在于用户不需要对 Expr 原始进行操作,可以直接通过访问的方法对其中一些具体的类与元素进行修改。
上图总结了查询语法树执行的工作流程。首先从 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 基金会的毕业项目,能够管理大量非结构化数据集,在新药发现、推荐系统、聊天机器人等方面具有广泛的应用。