FIELD OF THE INVENTION

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.

BACKGROUND

Recent advances in research and industry generate low level virtual machine (LLVM) bitcode for a given query plan. The LLVM bitcode is compiled by the LLVM compiler (LLC) into machine code by going through a code generation step and by compiling the generated code at compile time of the query.

The code generation and LLVM compilation approach has major limitations. The generated code is statically compiled, meaning only information available at compile time has been considered. That has notable limitations, as current runtime information cannot be taken into account. There are several reasons why current research and industry solutions cannot exploit dynamic profiling information.There is no profiling infrastructure build in into the SQL expression operands. Even if there were, this would have major runtime overhead.A priori knowledge at compile-time is not available either, since a whole query plan would need to be evaluated, including all intermediate results.Speculative logic is unsupported.

