申请试用
HOT
登录
注册
 
账号已存在
Deep dive#6 Milvus如何实现属性过滤
Milvus.io
/
发布于
/
56
人观看

Deep dive是由Milvus社区发起的代码解析系列直播,针对开源数据库 Milvus 整体架构开放式解读,与社区交流与分享 Milvus 最核心的设计理念。

对本期内容感兴趣的小伙伴,想要和讲师实时QA,欢迎大家添加小助手微信:Zilliz-tech 备注”直播“加入讨论群与大家共同交流!

  1. Milvus属性过滤支持的查询表达式
  2. 属性过滤表达式生成查询语法树
  3. 查询语法树的解释和执行
  4. QA
展开查看详情

1 .Milvus Deep Dive #5 How does milvus enable scalar field filtering?

2 .Speaker bio Kun Yu Software Engineer Milvus contributer • Education: bachlor, Huazhong University of Science and Technolog • Homepage: https://github.com/fishpenguin • Interests: Soccer/FPS games y

3 .Agenda • Milvus supported query expressions • PlanAST generation • PlanAST execution • Q&A

4 . 01 Milvus supported query expressions

5 .Boolean Expression Rules EBNF Syntax LogicalExpr = LogicalExpr BinaryLogicalOp LogicalExpr | UnaryLogicalOp LogicalExpr | “(” LogicalExpr “)” | SingleExpr

6 .Boolean Expression Rules

7 .Boolean Expression Rules Precedence Operator Description Associativity 1 +- UnaryArithOp Left-to-right 2 not UnaryLogicOp Right-to-left 3 ** BinaryArithOp Left-to-right 4 */% BinaryArithOp Left-to-right 5 +- BinaryArithOp Left-to-right 6 < <= > >= CmpOp Left-to-right 7 == != CmpOp Left-to-right 8 && and BinaryLogicOp Left-to-right 9 || or BinaryLogicOp Left-to-right

8 .Boolean Expression Rules Collection film: Example: score > 8.5 && field_name field_type (2000 - 10 < release_year < 2000 + 10 || type in [ 0,1 ]) film_id int64 Execution Order: release_year int64 Score > 8.5 —> result1 2000 - 10 —> result2 type int32 2000 + 10 —> result3 result2 < release_year < result3 —> result4 score float type in [0, 1] —> result5 result4 || result5 —> result6 poster float_vector result1 && result6 —> result

9 . 02 PlanAST Generation

10 .ANTLR(ANother Tool for Language Recognition) • A powerful parser generator for reading, processing, executing, or translating structured text or binary files. • ANTLR generates a parser that can build and walk parse trees.

11 .ANTLR(ANother Tool for Language Recognition) Parse-Tree Walker

12 .ANTLR(ANother Tool for Language Recognition) Parse-Tree Walker

13 .PlanAST generation Tools: https://github.com/antonmedv/expr • Optimizer: Self-implemented optimizer rules as ParseTreeListne • Analyzed PlanTree: Proto format of PlanTree r

14 .PlanAST generation Example: score > 8.5 && (2000 - 10 < release_year < 2000 + 10 || type in [ 0,1 ])

15 . 03 PlanAST execution

16 .PlanAST & Expr definition • PlanTree is a recursive proto structure • Expr is the C++ definition of PlanAST that interpreted from PlanTree

17 . PlanAST & Expr definition Expr UML

18 .PlanAST execution ● Visitor design pattern: Define a new operation for classes of an object structure without changing the classes.

19 . PlanAST execution PlanAST execution workflow

20 .Bitmap ● Bitmap: Mapping from offsets to bits. Using uint8 to represent 8 bits. • PlanAST execution result is a bitmap • Knowhere use bitmap to do filtering for vector search . .

21 . Optimizer(TODO) • Case 1: Harsh filters, few entries remaining after filterin Strategy: Filter out the items that meet the scalar field filtering condition, do brute search in original vector file • Case 2: Medium filters, some entries remaining after filterin Strategy: Generate bitmap from filtering, then do search in the index with bitmap • Case 3: Loose filters, many entries remaining after filterin Strategy: Enlarge topK to search in the index, and filter the topK answers from the results with attributes . . g g g .

22 .Thank You https://milvus.i https://github.com/milvus-io/milvu 扫码加⼊直播交流群 关注 Milvus 视频号 https://twitter.com/milvusi 与讲师实时Q 直播视频早知道 o A o s

0 点赞
0 收藏
3下载
确认
3秒后跳转登录页面
去登陆