Code generation for queries in a database system

• US 10,620,925 B2
• Filed: 03/30/2017
• Issued: 04/14/2020
• Est. Priority Date: 03/13/2017
• Status: Active Grant

• Current Assignee: Singlestore, Inc.
• Original Assignee: MemSQL, Inc.
• Inventors: Paroski, Andrew John, Andrews, Michael Adams, Hanson, Eric Norman
• Primary Examiner(s): Nguyen, Duy Khuong T
• Application Number:
  US15/474,787
• Publication Number:
  US 20180260437A1
• Time in Patent Office: 1,111 Days
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 8/447 Target code generation

Abstract

A method for generating code for queries in a database system includes obtaining a user query in a first programming language, the user query comprising at least one query parameter for selecting data from a content database. The method includes obtaining machine code corresponding to a compiled version of the user query. Obtaining the machine code includes generating code in a second programming language corresponding to a compiled version of the user query, generating byte code defining a plurality of functions corresponding to a compiled version of the code in the second programming language, and obtaining the machine code corresponding to the compiled version of the user query based on the byte code. The method further comprises executing the machine code using the at least one query parameter, thereby returning a result satisfying the at least one query parameter. A related non-transitory computer-readable medium and system are also provided.

Claims

1. A method, comprising:

obtaining a user query in a query language, the user query comprising at least one query parameter for selecting data from a content database;

obtaining machine code that is executable directly by a processing system, corresponding to a compiled version of the user query, by;

parsing the user query to identify a skeletal form of the user query in the structured query language;

generating byte code defining a plurality of functions corresponding to a compiled version of the skeletal form of the user query, and

obtaining the machine code corresponding to the compiled version of the user query based on the byte code, by retrieving compiled machine code for the byte code defining one or more of the plurality of functions if available or generating machine code for the byte code defining one or more of the plurality of functions when not available;

wherein the machine code corresponding to the compiled version of the user query comprises at least one unresolved symbol and obtaining the machine code comprises;

retrieving a memory address at which additional machine code corresponding to the at least one unresolved symbol is stored;

replacing the at least one unresolved symbol with the corresponding memory address; and

executing the machine code corresponding to the compiled version of the user query using the at least one query parameter, thereby returning a result of the user query satisfying the at least one query parameter.

2. The method of claim 1, wherein obtaining the machine code corresponding to the compiled version of the user query based on the byte code comprises:

for at least a subset of respective functions defined by the byte code, if machine code corresponding to a compiled version of the respective function is not stored in a code database;

generating an intermediate representation of the respective function; and

generating the machine code corresponding to the compiled version of the respective function based on the intermediate representation of the function; and

generating the machine code corresponding to the compiled version of the user query by aggregating the machine code corresponding to the compiled version of each respective function defined by the byte code.

3. The method of claim 1, wherein obtaining the machine code corresponding to the compiled version of the user query based on the byte code comprises:

for at least a subset of respective functions defined by the byte code, if the machine code corresponding to a compiled version of the respective function is stored in a code database, retrieving the machine code corresponding to the compiled version of the respective function; and

generating the machine code corresponding to the compiled version of the user query by aggregating the machine code corresponding to the compiled version of each respective function defined by the byte code.

4. The method of claim 1, wherein the user query conforms to a Structured Query Language (SQL) query.

5. The method of claim 1, further comprising storing the machine code corresponding to the compiled version of at least one respective function defined by the byte code in a code database.

6. The method of claim 1, wherein a code database is stored in at least one of a local memory, a local storage, and a server cache.

7. A non-transitory computer readable medium comprising instructions which, when executed by a processing system, causes the processing system to:

obtain a user query in a query language, the user query comprising at least one query parameter for selecting data from a content database;

obtain machine code that is executable directly by a processing system, corresponding to a compiled version of the user query, by;

parsing the user query to identify a skeletal form of the user query in the structured query language;

generating byte code defining a plurality of functions corresponding to a compiled version of the skeletal form of the user query, and

obtaining the machine code corresponding to the compiled version of the user query based on the byte code, by retrieving compiled machine code for the byte code defining one or more of the plurality of functions if available or generating machine code for the byte code defining one or more of the plurality of functions when not available;

wherein the machine code corresponding to the compiled version of the user query comprises at least one unresolved symbol and obtaining the machine code comprises;

retrieving a memory address at which additional machine code corresponding to the at least one unresolved symbol is stored;

replacing the at least one unresolved symbol with the corresponding memory address; and

execute the machine code corresponding to the compiled version of the user query using the at least one query parameter, thereby returning a result of the user query satisfying the at least one query parameter.

8. The medium of claim 7, wherein obtaining the machine code corresponding to the compiled version of the user query based on the byte code comprises the processing system:

for at least a subset of respective functions defined by the byte code, if machine code corresponding to a compiled version of the respective function is not stored in a code database;

generating an intermediate representation of the respective function; and

generating the machine code corresponding to the compiled version of the respective function based on the intermediate representation of the function; and

generating the machine code corresponding to the compiled version of the user query by aggregating the machine code corresponding to the compiled version of each respective function defined by the byte code.

9. The medium of claim 7, wherein obtaining the machine code corresponding to the compiled version of the user query based on the byte code comprises the processing system:

for at least a subset of respective functions defined by the byte code, if the machine code corresponding to a compiled version of the respective function is stored in a code database, retrieving the machine code corresponding to the compiled version of the respective function; and

generating the machine code corresponding to the compiled version of the user query by aggregating the machine code corresponding to the compiled version of each respective function defined by the byte code.

10. The medium of claim 7, wherein the instructions, when executed by the processing system, cause the processing system to further store the machine code corresponding to the compiled version of the user query in a code database.

11. The medium of claim 7, wherein the instructions, when executed by the processing system, cause the processing system to further store the machine code corresponding to the compiled version of at least one respective function defined by the byte code in a code database.

12. A system comprising:

a code database;

a content database; and

a processing system configured to;

obtain a user query in a query language, the user query comprising at least one query parameter for selecting data from a content database;

obtain machine code that is executable directly by a processing system, corresponding to a compiled version of the user query, by;

parsing the user query to identify a skeletal form of the user query in the structured query language;

generating byte code defining a plurality of functions corresponding to a compiled version of the skeletal form of the user query, and

obtaining the machine code corresponding to the compiled version of the user query based on the byte code, by retrieving compiled machine code for the byte code defining one or more of the plurality of functions if available or generating machine code for the byte code defining one or more of the plurality of functions when not available;

wherein the machine code corresponding to the compiled version of the user query comprises at least one unresolved symbol and obtaining the machine code comprises;

retrieving a memory address at which additional machine code corresponding to the at least one unresolved symbol is stored; and

replacing the at least one unresolved symbol with the corresponding memory address; and

execute the machine code corresponding to the compiled version of the user query using the at least one query parameter, thereby returning a result of the user query satisfying the at least one query parameter.