Adaptive interpretation and compilation of database queries

Patent metadata

Field	Value
Publication number	US-11704347-B2
Application number	US-202117368767-A
Country	US
Kind code	B2
Filing date	Jul 6, 2021
Priority date	Nov 6, 2016
Publication date	Jul 18, 2023
Grant date	Jul 18, 2023

Abstract

A method executes at a computer system to retrieve data from a database. Upon receiving a database query, the computer system translates the query into an intermediate representation, and estimates a compilation time to compile the intermediate representation into machine executable code. The query execution time to retrieve a result set is also estimated. In accordance with a determination that the query execution time and compilation time satisfy an interpretation criterion, the computer system invokes a byte code interpreter to interpret the intermediate representation and retrieve the result set from the database. In accordance with a determination that the query execution and compilation times satisfy one of a plurality of compilation criteria, the computer system compiles the intermediate representation to form machine code and executes the machine code to retrieve the result set from the database. In some cases, the query intermediate representation is optimized prior to compilation.

First claim

What is claimed is:

1. A method for retrieving data from a database, comprising:
at a computer system having one or more processors and memory storing one or more programs configured for execution by the one or more processors:
receiving a database query;
determining an estimated query execution time for executing the database query and an estimated compilation time for at least partially compiling the database query;
in accordance with a determination that the estimated query execution time and the estimated compilation time satisfy an interpretation criterion, invoking a byte code interpreter to retrieve a result set from the database;
in accordance with a determination that the estimated query execution time and the estimated compilation time satisfy a compilation criterion, compiling an intermediate representation of the database query, and executing a compiled representation to retrieve the result set from the database; and
in accordance with a determination that the estimated query execution time and the estimated compilation time satisfy an optimized compilation criterion, optimizing and compiling the intermediate representation of the database query, and executing an optimized and compiled representation to retrieve the result set from the database.

2. The method of claim 1 , further comprising translating the database query into the intermediate representation, wherein the intermediate representation is specified in low level virtual machine (LLVM) code.

3. The method of claim 1 , wherein computing the estimated compilation time is based on at least one of a number of instructions, types of instructions, a number of functions, and a number of execution blocks in the intermediate representation, wherein each block comprises a maximal contiguous sequence of instructions without a jump instruction.

4. The method of claim 1 , wherein the interpretation criterion, the compilation criterion, and the optimized compilation criterion are determined using one or more test databases and a plurality of test database queries prior to receiving the database query.

5. The method of claim 1 , wherein the estimated query execution time is determined according to an estimated number of rows that will be accessed to retrieve the result set corresponding to the database query, and the interpretation criterion is satisfied when the estimated number of rows that will be accessed to retrieve the result set is less than or equal to a first threshold.

6. The method of claim 5 , wherein the compilation criterion is satisfied when the estimated number of rows that will be accessed to retrieve the result set is greater than the first threshold but less than a second threshold.

7. The method of claim 6 , wherein the optimized compilation criterion is satisfied when the estimated number of rows that will be accessed to retrieve the result set is greater than the second threshold.

8. The method of claim 1 , wherein the interpretation criterion, the compilation criterion, and the optimized compilation criterion are mutually exclusive.

9. The method of claim 1 , wherein, when the interpretation criterion is satisfied, the compilation criterion and the optimized compilation criterion are not evaluated.

10. The method of claim 1 , further comprising computing a ratio of the estimated execution time and the estimated query compilation time, wherein:
the interpretation criterion comprises a rule that the ratio is less than a first threshold;
the compilation criterion comprises a rule that the ratio is greater than a first threshold but less than a second threshold; and
the optimized compilation criterion comprises a rule that the ratio is greater than the second threshold.

11. The method of claim 1 , wherein the interpretation criterion, the compilation criterion, and the optimized compilation criterion partition a set of all pairs (e, c) of estimated query execution time and estimated compilation time into three disjoint regions.

12. The method of claim 1 , wherein the database query is written in SQL.

13. A computer system having one or more computing devices, each computing device having one or more processors and memory, wherein the memory stores one or more programs configured for execution by the one or more processors, the one or more programs comprising instructions for:
receiving a database query;
determining an estimated query execution time for executing the database query and an estimated compilation time for at least partially compiling the database query;
in accordance with a determination that the estimated query execution time and the estimated compilation time satisfy an interpretation criterion, invoking a byte code interpreter to retrieve a result set from the database;
in accordance with a determination that the estimated query execution time and the estimated compilation time satisfy a compilation criterion: compiling an intermediate representation of the database query, and executing a compiled representation to retrieve the result set from the database; and
in accordance with a determination that the estimated query execution time and the estimated compilation time satisfy an optimized compilation criterion: optimizing and compiling the intermediate representation of the database query, and executing an optimized and compiled representation to retrieve the result set from the database.

14. The computer system of claim 13 , wherein computing the estimated compilation time is based on a number of execution blocks in the intermediate representation, wherein each block comprises a maximal contiguous sequence of instructions without a jump instruction.

15. The computer system of claim 13 , wherein:
the estimated query execution time is determined according to an estimated number of rows that will be accessed to retrieve the result set corresponding to the database query;
the interpretation criterion is satisfied when the estimated number of rows that will be accessed to retrieve the result set is less than or equal to a first threshold;
the compilation criterion is satisfied when the estimated number of rows that will be accessed to retrieve the result set is greater than the first threshold but less than a second threshold; and
the optimized compilation criterion is satisfied when the estimated number of rows that will be accessed to retrieve the result set is greater than the second threshold.

16. The computer system of claim 13 , further comprising computing a ratio of the estimated execution time and the estimated query compilation time, wherein:
the interpretation criterion comprises a rule that the ratio is less than a first threshold;
the compilation criterion comprises a rule that the ratio is greater than a first threshold but less than a second threshold; and
the optimized compilation criterion comprises a rule that the ratio is greater than the second threshold.

17. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer system having one or more processors and memory, the one or more programs comprising instructions for:
receiving a database query;
determining an estimated query execution time for executing the database query and an estimated compilation time for at least partially compiling the database query;
in accordance with a determination that the estimated query execution time and the estimated compilation time satisfy an interpretation criterion, invoking a byte code interpreter to retrieve a result set from the database;
in accordance with a determination that the estimated query

Assignees

• Tableau Software Inc

Inventors

• Neumann Thomas
• Leis Viktor
• Kemper Alfons
• Muehlbauer Tobias
• Finis Jan

Classifications

• G06F16/3332 Primary

  Query translation · CPC title

• G06F16/23

  Updating · CPC title

• G06F16/334

  Query execution (filtering based on additional data G06F16/335) · CPC title

• G06F16/24534 Primary

  Query rewriting; Transformation · CPC title