Select Page

How Does the Database Understand and Execute Your Query?

Angela Ni
Published: May 12, 2022

Cover image.

A vector query in Milvus is the process of retrieving vectors via scalar filtering based on a boolean expression. With scalar filtering, users can limit their query results with certain conditions applied to data attributes. For instance, if a user queries for films released during 1990-2010 and scores higher than 8.5, only films whose attributes (release year and score) fulfill the condition.
This post aims to examine how a query is completed in Milvus 2.0 from the input of a query expression to query plan generation and query execution.

Query Expression

Expression of the query with attribute filtering in Milvus adopts the EBNF(Extended Backus–Naur form) syntax. The image below is the expression rules in Milvus.

 Expression syntax.

The EBNF syntax of a logical expression.

Logical expressions can be created using the combination of binary logical operators, unary logical operators, logical expressions, and single expressions. Since EBNF syntax is itself recursive, a logical expression can be the outcome of the combination or part of a bigger logical expression. A logical expression can contain many sub-logical expressions. The same rule applies in Milvus. Suppose a user needs to filter the attributes of the results with many conditions. In that case, the user can create his own set of filtering conditions by combining different logical operators and expressions.

Boolean expression.

Boolean expression rules in Milvus.

The image above shows part of the Boolean expression rules in Milvus. Unary logical operators can be added to an expression. Currently, Milvus only supports the unary logical operator “not,” which indicates that the system needs to take the vectors whose scalar field values do not satisfy the calculation results. Binary logical operators include “and” and “or.” Single expressions include term expressions and compare expressions.

Basic arithmetic calculation like addition, subtraction, multiplication, and division is also supported during a query in Milvus. The following image demonstrates the precedence of the operations. Operators are listed from top to bottom in descending precedence.


The precedence of operations in Milvus.

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.

Film example.

Querying films in the database.

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.

Parse tree.

Generating a parse tree for the input expression.

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.

Parse tree walker

The parse-tree walker mechanism in ANTLR.

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).

Plan AST workflow.

The workflow of generating a plan AST in Milvus.

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.

A query message with the protobuf structure.

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.

A UML image of the query expression.

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.

The workflow of executing a plan AST in Milvus.