How Does the Database Understand and Execute Your Query?

How a Query Expression on Certain Films Is Processed in Milvus?

Suppose there is an abundance of film data stored in Milvus, and the user wants to query certain films. For example, each film data stored in Milvus has the following five fields: film ID, release year, film type, score, and poster. In this example, the data type of film ID and release year is int64, while film scores are float point data. Also, film posters are stored in the format of float-point vectors and film types in string data format. Notably, support for the string data type is a new feature in Milvus 2.1.

For instance, if a user wants to query the movies with scores higher than 8.5. The films should also be released during a decade before 2000 to a decade after 2000, or their types should be either comedy or action movie; the user needs to input the following predicate expression: score > 8.5 && (2000 - 10 < release_year < 2000 + 10 || type in [comedy,action]).

Upon receiving the query expression, the system will execute it in the following precedence:

1. The query for films with scores higher than 8.5. The query results are called "result1".
2. Calculate 2000 - 10 to get "result2" (1990).
3. Calculate 2000 + 10 to get "result3" (2010).
4. The query for films with the value of release_year greater than "result2" and smaller than "result3". That is to say; the system needs to query for films released between 1990 and 2010. The query results are called "result4".
5. The query for films that are either comedies or action movies. The query results are called "result5".
6. Combine "result4" and "result5" to obtain films that are either released between 1990 and 2010 or belong to the category of comedy or action movies. The results are called "result6".
7. Take the common part in "result1" and "result6" to obtain the final results satisfying all the conditions.

Plan AST Generation

Milvus leverages the open-source tool ANTLR (ANother Tool for Language Recognition) for plan AST (abstract syntax tree) generation. ANTLR is a powerful parser generator for reading, processing, executing, or translating structured text or binary files. ANTLR can generate a parser for building and walking parse trees based on pre-defined syntax or rules. The following image is an example of the input expression being "SP=100;". LEXER, the built-in language recognition functionality in ANTLR, generates four tokens for the input expression - "SP", "=", "100", and ";". Then the tool will further parse the four tokens to generate the corresponding parse tree.

The walker mechanism is a crucial part of the ANTLR tool. It is designed to walk through all the parse trees to examine whether each node obeys the syntax rules or detects certain sensitive words. Some of the relevant APIs are listed in the image below. Since ANTLR starts from the root node and goes down through each sub-node to the bottom, there is no need to differentiate the order of how to walk through the parse tree.

Milvus generates the PlanAST for query in a similar way to the ANTLR. However, using ANTLR requires redefining rather complicated syntax rules. Therefore, Milvus adopts one of the most prevalent rules - Boolean expression rules, and depends on the Expr package open sourced on GitHub to query and parse the syntax of query expressions.

During a query with attribute filtering, Milvus will generate a primitive unsolved plan tree using ant-parser, the parsing method provided by Expr, upon receiving the query expression. The primitive plan tree we will get is a simple binary tree. Then the plan tree is fine-tuned by Expr and the built-in optimizer in Milvus. The optimizer in Milvus is quite similar to the aforementioned walker mechanism. Since the plan tree optimization functionality provided by Expr is pretty sophisticated, the burden of the Milvus built-in optimizer is alleviated to a great extent. Ultimately, the analyzer analyzes the optimized plan tree in a recursive way to generate a plan AST in the structure of protocol buffers (protobuf).

Query Execution

Query execution is at root, the execution of the plan AST generated in the previous steps.

In Milvus, a plan AST is defined in a proto structure. For example, the image below is a message with the protobuf structure. There are six types of expressions, among which are binary expression, and unary expression can further have binary logical expression and unary logical expression.

The image below is a UML image of the query expression. It demonstrates the basic class and derivative class of each expression. In addition, each class comes with a method to accept visitor parameters. This is a typical visitor design pattern. Milvus uses this pattern to execute the plan AST as its biggest advantage is that users do not have to do anything to the primitive expressions but can directly access one of the methods in the patterns to modify certain query expression classes and relevant elements.

When executing a plan AST, Milvus first receives a proto-type plan node. Then a segcore-type plan node is obtained via the internal C++ proto parser. Upon obtaining the two types of plan nodes, Milvus accepts a series of class access and then modifies and executes the internal structure of the plan nodes. Finally, Milvus searches through all the execution plan nodes to obtain the filtered results. The final results are output in the format of a bitmask. A bitmask is an array of bit numbers ("0" and "1"). Those data satisfying filter conditions are marked as "1" in the bitmask, while those that do not meet the requirements are marked as "0" in the bitmask.