Deep dive#6 Milvus如何实现属性过滤

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