US 11,386,086 B2Granted

Permutation-based machine learning for database query optimization

AssigneeInternational Business Machines Corporation

InventorsTerence P. Purcell, Thomas A. Beavin, Martin Dinh, Brian L. Baggett

Life of this patent

Estimating the term…

Loading patent…

Abstract

A DBMS query-optimization module receives a corpus of training data that contains data-access requests, such as SQL queries. Each request specifies data to be accessed but does not specify a query plan that the database should use to generate the requested data. The module identifies, in each received request, parameters, such as join methods and access methods, that can vary among query plans; and variables that cannot be assigned values until the query is actually processed. The system generates a set of queries, each of which implements a distinct query plan, that specify every viable permutation of values of the parameters and of the variables. The generated queries are added to the received corpus, which is forwarded to a machine-learning module in order to train the query-optimizer to select query plans that incur the lowest resource costs when servicing a particular type of query.

Claims15

Dependent claims

A database-optimizer training system comprising a processor, a memory coupled to the processor, and a computer-readable hardware storage device coupled to the processor, the storage device containing program code configured to be run by the processor via the memory to implement a method for permutation-based machine learning for database query optimization, the method comprising:

the system receiving a data-access request that specifies a result to be retrieved from a database by a database-management system (DBMS), where the received request specifies a plurality of variables but does not specify a sequence of DBMS data-retrieval steps capable of generating the result;
the system enumerating a plurality of candidate query plans,
where each plan of the plurality of candidate query plans identifies a distinct set of data-retrieval steps that, when performed by the DBMS, are capable of generating the result,
where each plan of the plurality of candidate query plans specifies a distinct permutation of all possible values of each parameter of a plurality of data-access parameters,
and
where no two plans of the plurality of candidate query plans specify identical permutations;
the system generating a plurality of permuted data-access requests,
where each request of the plurality of permuted data-access requests is a rewritten version of the received data-access request that has been revised so as to direct the DBMS to use a corresponding plan of the plurality of candidate query plans,
where the enumerating further comprises the system choosing a set of representative values for each variable of the plurality of variables,
where each plan of the plurality of candidate query plans assigns a value to each variable of the plurality of variables,
where each assigned value of a first variable of the plurality of variables is selected from the set of representative values chosen for the first variable, and
where each distinct permutation of the all possible values identifies one possible value of each parameter of the plurality of data-access parameters and one chosen representative value of each variable of the plurality of variables,
where the plurality of candidate query plans in aggregate comprises all possible permutations of all possible values of each parameter of the plurality of data-access parameters and further comprises all possible permutations of the sets of representative values of all variables of the plurality of variables, and
where the plurality of permuted data-access requests in aggregate directs the DBMS to use all plans of the plurality of candidate query plans;
and
the system submitting the plurality of data-access requests, as a machine-learning corpus, to a training module that uses the corpus to improve automated training of a query-optimization component of the DBMS, such that the improved training teaches the query-optimization to provide improved query-optimization functionality to the DBMS.

13 more elements

A method for permutation-based machine learning for database query optimization, the method comprising:

receiving a data-access request that specifies a result to be retrieved from a database by a database-management system (DBMS), where the received request specifies a plurality of variables but does not specify a sequence of DBMS data-retrieval steps capable of generating the result;
enumerating a plurality of candidate query plans,
where each plan of the plurality of candidate query plans identifies a distinct set of data-retrieval steps that, when performed by the DBMS, are capable of generating the result,
where each plan of the plurality of candidate query plans specifies a distinct permutation of all possible values of each parameter of a plurality of data-access parameters,
and
where no two plans of the plurality of candidate query plans specify identical permutations;
generating a plurality of permuted data-access requests,
where each request of the plurality of permuted data-access requests is a rewritten version of the received data-access request that has been revised so as to direct the DBMS to use a corresponding plan of the plurality of candidate query plans,
where the enumerating further comprises choosing a set of representative values for each variable of the plurality of variables,
where each plan of the plurality of candidate query plans assigns a value to each variable of the plurality of variables,
where each assigned value of a first variable of the plurality of variables is selected from the set of representative values chosen for the first variable, and
where each distinct permutation of the all possible values identifies one possible value of each parameter of the plurality of data-access parameters and one chosen representative value of each variable of the plurality of variables,
where the plurality of candidate query plans in aggregate comprises all possible permutations of all possible values of each parameter of the plurality of data-access parameters and further comprises all possible permutations of the sets of representative values of all variables of the plurality of variables, and
where the plurality of permuted data-access requests in aggregate directs the DBMS to use all plans of the plurality of candidate query plans;
and
submitting, by the database-optimizer training system, the plurality of data-access requests, as a machine-learning corpus, to a training module that uses the corpus to improve automated training of a query-optimization component of the DBMS, such that the improved training teaches the query-optimization to provide improved query-optimization functionality to the DBMS.

13 more elements

A computer program product, comprising a computer-readable hardware storage device having a computer-readable program code stored therein, the program code configured to be executed by a database-optimizer training system comprising a processor, a memory coupled to the processor, and a computer-readable hardware storage device coupled to the processor, the storage device containing program code configured to be run by the processor via the memory to implement a method for permutation-based machine learning for database query optimization, the method comprising:

the system receiving a data-access request that specifies a result to be retrieved from a database by a database-management system (DBMS), where the received request specifies a plurality of variables but does not specify a sequence of DBMS data-retrieval steps capable of generating the result;
the system enumerating a plurality of candidate query plans,
where each plan of the plurality of candidate query plans identifies a distinct set of data-retrieval steps that, when performed by the DBMS, are capable of generating the result,
where each plan of the plurality of candidate query plans specifies a distinct permutation of all possible values of each parameter of a plurality of data-access parameters,
where each plan of the plurality of candidate query plans specifies a distinct permutation of all possible values of each parameter of a plurality of data-access parameters,
and
where no two plans of the plurality of candidate query plans specify identical permutations;
the system generating a plurality of permuted data-access requests,
where each request of the plurality of permuted data-access requests is a rewritten version of the received data-access request that has been revised so as to direct the DBMS to use a corresponding plan of the plurality of candidate query plans,
where the enumerating further comprises the system choosing a set of representative values for each variable of the plurality of variables,
where each plan of the plurality of candidate query plans assigns a value to each variable of the plurality of variables,
where each assigned value of a first variable of the plurality of variables is selected from the set of representative values chosen for the first variable, and
where each distinct permutation of the all possible values identifies one possible value of each parameter of the plurality of data-access parameters and one chosen representative value of each variable of the plurality of variables,
where the plurality of candidate query plans in aggregate comprises all possible permutations of all possible values of each parameter of the plurality of data-access parameters and further comprises all possible permutations of the sets of representative values of all variables of the plurality of variables, and
where the plurality of permuted data-access requests in aggregate directs the DBMS to use all plans of the plurality of candidate query plans;
and
the system submitting the plurality of data-access requests, as a machine-learning corpus, to a training module that uses the corpus to improve automated training of a query-optimization component of the DBMS, such that the improved training teaches the query-optimization to provide improved query-optimization functionality to the DBMS.

14 more elements

Dependencies are inferred from the claim text.