CN114637775A - Query optimization system, method and equipment based on Monte Carlo tree search and reinforcement learning - Google Patents

Abstract

Query optimization system, method and equipment based on Monte Carlo tree search and reinforcement learning, and belongs to the technical field of computers. In order to solve the problems of weak compatibility and poor stability of the conventional NEO query optimization method, the system of the invention adopts the same framework as an NEO query optimization model, wherein a value model unit: predicting the cost of the query plan by utilizing the characteristics corresponding to the query plan based on the value model; the value model is a neural network model; the input of the value model is a vector tree used for representing a query plan needing to estimate the overhead, the topological structure of the vector tree is a binary tree structure, and the node codes are sequentially spliced according to the sequence traversal order of the tree; the node characteristics of the nodes consist of the codes of the node information; the query plan searching unit adopts a Monte Carlo tree searching method to search a query plan according to the prediction of query plan- > time cost, and generates an execution plan from a search space. The method is mainly used for query optimization in the computer.

Description

Query optimization system, method and device based on Monte Carlo tree search and reinforcement learning

technical field

The invention relates to a query optimization system and method, and belongs to the technical field of computers.

Background technique

At present, query optimization algorithms are divided into two categories, namely traditional query optimization algorithms and AI-based query optimization algorithms. The former usually use cardinality/cost estimation techniques to filter query plans from several candidate plans, or use predefined rules to optimize the initial query plan. This type of technology is currently the most widely used, but it is relatively backward. The latter uses AI techniques for cardinality/cost estimation, or directly uses machine learning techniques to generate optimized query plans. Among such methods, the most advanced and representative ones are NEO and BAO technologies.

NEO technology is an end-to-end learning-based query optimization method that optimizes join order, index selection, and physical operator selection in relational databases. It models the query plan generation problem as a Markov model, uses a reinforcement learning algorithm to train a deep learning model based on a tree convolutional neural network, and uses the output of the model to gradually generate the equivalent of the input SQL query language query plan tree. The input to this Markov model (i.e., the "state" in reinforcement learning) is divided into two parts: query-level encoding and plan-level encoding. The encoding scheme is shown in Figures 1 and 2. You can refer to the paper "Neo: A Learned Query Optimizer", or related descriptions of the paper, such as https://blog.csdn.net/cuirise/article/details/111466631, https://zhuanlan.zhihu.com/p/ 80233443 etc.

The query-level encoding contains the relationship of the join operation (red vector) of each table in the database, and the predicates used in the join (blue vector). The plan level code contains the structure of the entire query (ie, the structure of the query plan tree), and the access mode information (index or direct access table) of each operator.

NEO uses the above two codes as input through a tree convolutional neural network to predict the "value" of a query plan. The value model (value model) uses the historical query plans stored in the experience pool and their corresponding costs for training. The loss function uses MSE, and the label is the minimum cost of different query plans of the same query in the experience pool.

As shown in Figure 3, the main flow of NEO is as follows:

1. Use a "weak" optimizer (such as PostgreSQL's optimizer) to generate an initial execution plan, called bootstrap.

2. Experience represents a set of (execution plan -> time cost), which is the training sample of the value model.

3. Featurizer extracts two types of features: query features and execution plan features.

4. Use the extracted features to train the value model, and establish a query plan -> time cost prediction model.

5. Do a query plan search on this model. Here, a simple greedy search is used to select an execution plan.

The search part of the query plan maintains a small top heap, the elements in the heap are sub-query plans, and the priority is the value model. Expand all its legal sub-plans (expand the child nodes of the query plan tree), predict the minimum cost of the complete query plan that can be generated by each expanded sub-plan (the query execution time is used here), and select the plan with the smallest cost Insert a small top heap. This process is repeated until the subplan is expanded to obtain a complete query plan.

So it has the following problems:

1. This technology can only support a limited number of in-database relational operations, specifically, only selection, projection, equi-join and aggregation queries.

2. The performance is unstable. On some query loads, the query plan optimized by this solution takes a long time to execute, and there is a long-tail distribution problem.

SUMMARY OF THE INVENTION

The invention aims to solve the problems of weak compatibility and poor stability in the existing NEO query optimization method.

A query optimization system based on Monte Carlo tree search and reinforcement learning, which adopts the same framework as the NEO query optimization model, including a value model unit and a query plan search unit;

Value model unit: Based on the value model, the cost of the query plan is predicted by using the characteristics corresponding to the query plan;

The value model is a neural network model; the input of the value model is a vector tree, which is used to represent the query plan that needs to estimate the cost, the topology structure of the vector tree is a binary tree structure, and the coding of each node is in the order of the tree traversal order. Splicing; the node characteristics of the node are composed of the encoding of the node information; the node information includes the node type, the table involved in the operation, the index type involved in the operation, the predicate involved in the operation, and the cardinality estimation result of the node;

Query plan search unit: Using Monte Carlo tree search method, query plan search is performed according to the prediction of query plan -> time cost, and an execution plan is generated from the search space.

Further, the encoding of the node information is as follows:

The node type is one-hot encoding; the table involved in the operation is one-hot encoding; the index type involved in the operation is one-hot encoding; the predicate involved in the operation is one-hot encoding; the cardinality estimation result of the node is an integer value .

Further, the neural network model as the value model adopts the architecture of multi-layer stacked tree convolutional layers.

Further, when the query plan search unit uses the method of Monte Carlo tree search to search, the process of generating a better query plan is modeled as a Markov process, the Monte Carlo tree search is used to expand the sub-query plan, and the semantic consistency is adopted. The vector tree code corresponding to the sub-query plan of is used as the tree node in the Monte Carlo tree search, and the cost model of the sub-query plan is used to evaluate the cost of the sub-query plan in each search, and then the Monte Carlo tree search is realized.

Further, the search process of the query plan search unit using the method of Monte Carlo tree search includes the following steps:

(1) Selection: Starting from the root node R, use the UCT algorithm to recursively select the optimal child node until the leaf node L is reached;

(2) Extension: if L is not a termination node, then create one or more sub-nodes that do not contradict the semantics of the query, and select one of the sub-nodes C;

(3) Simulation: starting from C, randomly select a non-contradictory child node until the current query plan is completely expressed;

(4) Backpropagation: Use the value model to predict the cost of the simulated complete query plan, and reversely update the simulation times and rewards of all its parent nodes from this leaf node;

(5) Steps (1)-(4) are executed cyclically, and the sub-query plan is continuously expanded until a complete query plan is generated.

A query optimization method based on Monte Carlo tree search and reinforcement learning, including the following steps:

Use the value model as the prediction model of query plan -> time cost; do query plan search on the prediction model of query plan -> time cost;

The value model is a neural network model; the input of the value model is a vector tree, which is used to represent the query plan that needs to estimate the cost, the topology structure of the vector tree is a binary tree structure, and the coding of each node is in the order of the tree traversal order. Splicing; the node characteristics of the node are composed of the encoding of the node information; the node information includes the node type, the table involved in the operation, the index type involved in the operation, the predicate involved in the operation, and the cardinality estimation result of the node;

The query plan search uses the Monte Carlo tree search method to search, and performs query plan search according to the query plan->time cost prediction, and generates an execution plan from the search space.

Further, the training process of the described value model includes the following steps:

S1. Use the execution plan and time cost corresponding to the query as experience, and construct an experience set; use the execution plan and time cost corresponding to each experience in the experience combination as a training sample of the value model;

S2, characterize the training samples, that is, extract features, and the features include query features and execution plan features;

S3. Use the extracted features to train the value model, and the trained value model is the established query plan -> the prediction model of time cost.

A query optimization device based on Monte Carlo tree search and reinforcement learning, the device is a storage medium, and the storage medium stores at least one instruction, and the at least one instruction is loaded and executed by a processor to realize the A query optimization method based on Monte Carlo tree search and reinforcement learning.

A query optimization device based on Monte Carlo tree search and reinforcement learning, the device includes a processor and a memory, the memory stores at least one instruction, and the at least one instruction is loaded and executed by the processor to implement the Query Optimization Methods for Monte Carlo Tree Search and Reinforcement Learning.

Beneficial effects:

By improving the Value Model (value model) used in NEO and improving the greedy-based Plan Search method in NEO, the present invention realizes the compatibility of all relational operations in the relational database, and has higher and more stable performance than NEO.

Description of drawings

Figure 1 is a schematic diagram of NEO query level coding;

Figure 2 is a schematic diagram of NEO plan level coding;

Figure 3 is a schematic diagram of the NEO system framework;

Fig. 4 is a query plan vector tree coding example of the present invention;

Figure 5 is an example of the value model structure of the present invention;

Figure 6 is a schematic diagram of the Monte Carlo tree search process.

Detailed ways

Specific implementation one:

This embodiment is a query optimization method based on Monte Carlo tree search and reinforcement learning, and the process of query optimization is realized by a query optimization system based on Monte Carlo tree search and reinforcement learning. The present invention and NEO are both cost-based and AI-based query optimization methods, so the framework of the system of the present invention (a query optimization system based on Monte Carlo tree search and reinforcement learning) is also shown in Figure 3, both of which use the value of pre-training The model (ie, the Value Model) predicts the cost of the query plan and guides the search for the query plan. The difference between the two lies in the network structure of the value model and the query plan search (Plan Search) method; that is: the system of the present invention has the same framework as the NEO query optimization model, including a value model unit and a query plan search unit;

Value model unit: Based on the value model, the cost of the query plan is predicted by using the characteristics corresponding to the query plan;

The value model is a neural network model; the input of the value model is a vector tree, which is used to represent the query plan that needs to estimate the cost, the topology structure of the vector tree is a binary tree structure, and the coding of each node is in the order of the tree traversal order. Splicing; the node characteristics of the node are composed of the encoding of the node information; the node information includes the node type, the table involved in the operation, the index type involved in the operation, the predicate involved in the operation, and the cardinality estimation result of the node;

Query plan search unit: The method of Monte Carlo tree search is used to search the query plan according to the prediction of query plan -> time cost, and generate an execution plan from the search space.

A query optimization method based on Monte Carlo tree search and reinforcement learning described in this embodiment includes the following steps:

1. Use a "weak" optimizer (such as PostgreSQL's optimizer) to generate an initial execution plan, called bootstrap.

2. Experience represents a set of (execution plan -> time cost), which is the training sample of the value model.

3. Featurizer extraction features: query features, execution plan features.

4. Use the neural network proposed by the present invention as a value model, train the value model with the extracted features, and establish a query plan->time cost prediction model.

5. Query plan search is performed on the prediction model of query plan->time cost. Different from NEO, the present invention adopts the method of Monte Carlo tree search to generate an execution plan from the search space.

In terms of the value model, since the query cardinality and the query cost are usually in a linear relationship, an accurate query cardinality estimation result will effectively improve the prediction accuracy of the query cost. Therefore, the present invention introduces the cardinality estimation strategy based on the data distribution into the value model as a feature; When estimating the cost of a given query plan, the cardinality of each node in the query plan is estimated using the most efficient Naru scheme among cardinality estimation techniques. The estimation results are encoded into a vector tree as input to the value model.

The input to the value model is a vector tree representing the query plan that requires an estimated cost. As shown in Figure 4, the inputs to the value model are as follows:

Topological structure: binary tree structure, each node code is spliced in sequence according to the traversal order of the tree;

Node feature: a one-dimensional vector of 1; the node feature consists of the encoding of the following information;

One-hot encoding of node type (supports all physical relationship operations, including empty nodes);

Tables involved in the operation: one-hot encoding;

The index type involved in the operation: one-hot encoding;

Predicates involved in operations: one-hot encoding;

The cardinality estimation result of the node: integer value;

Through this encoding, the present invention expresses the query-level encoding and the plan-level encoding in NEO in a unified and combined manner, which is more conducive to feature extraction by the machine learning model. Due to the change of input, the network architecture of the value model is also different from NEO, adopting the architecture of multi-layer stacked tree convolutional layers, and introducing residual connections and batch normalization-full connection layer (BN) for stabilization training, as shown in Figure 5.

Finally, the prediction target of the value model is also different from that of NEO. The prediction target of NEO is the minimum cost of the complete query plan that can be generated by each extended sub-plan, while the present invention simply predicts the cost of the input query plan.

In terms of query plan search (Plan search), the present invention models the process of generating a better query plan as a Markov process, uses Monte Carlo Tree Search (MCTS) to expand the sub-query plan, and adopts the above-mentioned value model as the Monte Carlo tree search (MCTS). Heuristic function for Los Angeles search. Note: During the search process, the query optimizer of a traditional database (such as PostgreSQL) is used to determine the search space each time, that is, which expandable child nodes there are in this search, so that the final generated query plan can be semantically consistent with the initial query plan . All existing cost-based query optimizers currently support this feature and will not be repeated here. The present invention adopts the vector tree code corresponding to the sub-query plan with consistent semantics as the tree node in the Monte Carlo tree search, and uses the value model to evaluate the cost of the sub-query plan in each search.

As shown in Figure 6, the Monte Carlo tree search process is as follows:

(1) Selection: Starting from the root node R, use the UCT algorithm to recursively select the optimal child node until the leaf node L is reached.

(2) Expansion: If L is not a termination node (that is, it cannot fully express the entire query plan), then create one or more sub-nodes that do not contradict the semantics of the query based on the rules, and select one of them child node C.

(3) Simulation: Starting from C, using the same rules as in step (2) above, randomly select a non-contradictory child node until the current query plan is completely expressed.

(4) Backpropagation: Use the value model to predict the cost of the simulated complete query plan, and reversely update the number of simulations and reward (ie average cost) of all its parent nodes from this leaf node.

(5) Steps (1)-(4) above are executed in a loop, and the sub-query plan is continuously expanded until a complete query plan is generated.

Specific implementation two:

This embodiment is a query optimization device based on Monte Carlo tree search and reinforcement learning, the device is a storage medium, and at least one instruction is stored in the storage medium, and the at least one instruction is loaded and executed by a processor to Implement the query optimization method based on Monte Carlo tree search and reinforcement learning as claimed in one of claims 6 to 8.

The storage medium in this embodiment includes, but is not limited to, a U disk, a hard disk, and the like.

Specific implementation three:

This embodiment is a query optimization device based on Monte Carlo tree search and reinforcement learning, the device includes a processor and a memory, the memory stores at least one instruction, and the at least one instruction is loaded and executed by the processor to achieve The query optimization method based on Monte Carlo tree search and reinforcement learning according to one of claims 6 to 8.

The devices in this embodiment include, but are not limited to, mobile terminals, PCs, servers, workstations, and the like.

The present invention can also have other various embodiments. Without departing from the spirit and essence of the present invention, those skilled in the art can make various corresponding changes and deformations according to the present invention, but these corresponding changes and deformations are all It should belong to the protection scope of the appended claims of the present invention.

Claims (10)

1. a query optimization system based on Monte Carlo tree search and reinforcement learning, the system adopts the same framework as the NEO query optimization model, including a value model unit and a query plan search unit; it is characterized in that, Value model unit: Based on the value model, the cost of the query plan is predicted by using the characteristics corresponding to the query plan; The value model is a neural network model; the input of the value model is a vector tree, which is used to represent the query plan that needs to estimate the cost, the topology structure of the vector tree is a binary tree structure, and the coding of each node is in the order of the tree traversal order. Splicing; the node characteristics of the node are composed of the encoding of the node information; the node information includes the node type, the table involved in the operation, the index type involved in the operation, the predicate involved in the operation, and the cardinality estimation result of the node; Query plan search unit: Using Monte Carlo tree search method, query plan search is performed according to the prediction of query plan -> time cost, and an execution plan is generated from the search space. 2. the query optimization system based on Monte Carlo tree search and reinforcement learning according to claim 1, is characterized in that, the coding of described node information is as follows: The node type is one-hot encoding; the table involved in the operation is one-hot encoding; the index type involved in the operation is one-hot encoding; the predicate involved in the operation is one-hot encoding; the cardinality estimation result of the node is an integer value . 3. The query optimization system based on Monte Carlo tree search and reinforcement learning according to claim 2, is characterized in that, the neural network model as the value model comprises a stacking tree convolution unit and two batch-based normalizations connected afterward The fully connected layer; the stacked tree convolution unit is composed of multiple stacked tree convolution layers. 4. The query optimization system based on Monte Carlo tree search and reinforcement learning according to claim 1, 2 or 3, characterized in that, when the query plan search unit searches by the method of Monte Carlo tree search, it will generate The process of a better query plan is modeled as a Markov process. The Monte Carlo tree search is used to expand the sub-query plan, and the vector tree code corresponding to the semantically consistent sub-query plan is used as the tree node in the Monte Carlo tree search. Monte Carlo tree search is implemented by evaluating the cost of subquery plans using a value model when searching. 5. the query optimization system based on Monte Carlo tree search and reinforcement learning according to claim 4, is characterized in that, the process that the query plan search unit adopts the method of Monte Carlo tree search to search comprises the following steps: (1) Selection: Starting from the root node R, use the UCT algorithm to recursively select the optimal child node until the leaf node L is reached; (2) Extension: If L is not a termination node, then create one or more sub-nodes that do not contradict the semantics of the query, and select one of the sub-nodes C; (3) Simulation: starting from C, randomly select a non-contradictory child node until the current query plan is completely expressed; (4) Backpropagation: Use the value model to predict the cost of the simulated complete query plan, and reversely update the simulation times and rewards of all its parent nodes from this leaf node; (5) Steps (1)-(4) are executed cyclically, and the sub-query plan is continuously expanded until a complete query plan is generated. 6. A query optimization method based on Monte Carlo tree search and reinforcement learning, characterized in that it comprises the following steps: Use the value model as the prediction model of query plan -> time cost; do query plan search on the prediction model of query plan -> time cost; The value model is a neural network model; the input of the value model is a vector tree, which is used to represent the query plan that needs to estimate the cost, the topology structure of the vector tree is a binary tree structure, and the coding of each node is in the order of the tree traversal order. Splicing; the node characteristics of the node are composed of the encoding of the node information; the node information includes the node type, the table involved in the operation, the index type involved in the operation, the predicate involved in the operation, and the cardinality estimation result of the node; The query plan search uses the Monte Carlo tree search method to search, and performs query plan search according to the query plan->time cost prediction, and generates an execution plan from the search space. 7. The query optimization method based on Monte Carlo tree search and reinforcement learning according to claim 6, is characterized in that, the training process of described value model comprises the following steps: S1. Use the execution plan and time cost corresponding to the query as experience, and construct an experience set; use the execution plan and time cost corresponding to each experience in the experience combination as a training sample of the value model; S2, characterize the training samples, that is, extract features, and the features include query features and execution plan features; S3. Use the extracted features to train the value model, and the trained value model is the established query plan -> the prediction model of time cost. 8. The query optimization method based on Monte Carlo tree search and reinforcement learning according to claim 7, wherein the process of using the Monte Carlo tree search method to search comprises the following steps: (1) Selection: Starting from the root node R, use the UCT algorithm to recursively select the optimal child node until the leaf node L is reached; (2) Extension: If L is not a termination node, then create one or more sub-nodes that do not contradict the semantics of the query, and select one of the sub-nodes C; (3) Simulation: starting from C, randomly select a non-contradictory child node until the current query plan is completely expressed; (4) Backpropagation: Use the value model to predict the cost of the simulated complete query plan, and reversely update the simulation times and rewards of all its parent nodes from this leaf node; (5) Steps (1)-(4) are executed cyclically, and the sub-query plan is continuously expanded until a complete query plan is generated. 9. A query optimization device based on Monte Carlo tree search and reinforcement learning, wherein the device is a storage medium, and the storage medium stores at least one instruction, and the at least one instruction is loaded by the processor and executed. Executed to implement the Monte Carlo Tree Search and Reinforcement Learning based query optimization method as claimed in one of claims 6 to 8. 10. A query optimization device based on Monte Carlo tree search and reinforcement learning, characterized in that the device comprises a processor and a memory, the memory stores at least one instruction, and the at least one instruction is loaded and executed by the processor In order to realize the query optimization method based on Monte Carlo tree search and reinforcement learning as described in one of claims 6 to 8.

Images