First futamura projection in the context of SQL expression evaluation
US11461324B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 29, 2019 |
| Grant date | Oct 4, 2022 |
| Priority date | — |
| Expiry date | Apr 18, 2040 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2455
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention relates to execution optimization of database queries. Herein are techniques for optimal execution based on query interpretation by translation to a domain specific language (DSL), with optimizations such as partial evaluation, abstract syntax tree (AST) rewriting, just in time (JIT) compilation, dynamic profiling, speculative logic, and Futamura projection. In an embodiment, a database management system (DBMS) that is hosted on a computer generates a query tree that represents a database query that contains an expression that is represented by a subtree of the query tree. The DBMS generates a sequence of DSL instructions that represents the subtree. The sequence of DSL instructions is executed to evaluate the expression during execution of the database query. In an embodiment, an AST is generated from the sequence of DSL instructions. In an embodiment, the DSL AST is optimally rewritten based on a runtime feedback loop that includes dynamic profiling information.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.