BACKGROUND

The present invention, in some embodiments thereof, relates to an apparatus for processing database management system (DBMS) queries, and, more specifically, but not exclusively, to pre-compiling DBMS queries using tracing just-in-time compilation technology.

Mobile devices and computer operating systems often require a DBMS, but do not have the resources to run a client-server DBMS. In these cases, an embedded DBMS is used. However, embedded DBMS generally have much longer latency than a client server DBMS. Improving the efficiency of embedded DBMS would improve the user experience of Smartphone users as well as numerous web sites that employ an embedded DBMS.

Since embedded DBMS software often executes in an interpreted environment, one existing approach to reducing latency is translating a DBMS query into a query execution plan rather than interpreting it directly. This approach eliminates interpretation overhead and increase the speed of the query execution.

Usually, the query execution plan comprises compiling the query to some intermediate representation (IR), sometimes referred to as a physical execution plan. The IR may be executed in the three ways. The IR may be executed directly, it may be further translated by query engine to a Query Plan and executed by a virtual machine (VM), and/or it may be translated to a machine code. Any combination of the three is possible. Translation to machine code may be performed by using some general purpose compiler like C/C++ or Low Level Virtual Machine (LLVM) compiler.

The first and second approaches have suboptimal execution speed, but allow further optimization since the code remains in a high level language. Translating to machine code may execute more quickly than IR or the VM, but it requires the chain of compilation tool to run at target computer, which are often not available in devices that use an embedded DBMS, for example Smartphones, handheld devices, internet-of- things devices etc. Additional limitations of machine code are that it is generally not understandable to programmers, which makes further optimization and maintenance virtually impossible. In addition, a change to a single parameter requires recompiling the entire code.

Existing solutions differ in how they solve these limitations. However, no existing solution offers both machine code efficiency and the flexibility and maintainability of a high level computer language.

SUMMARY

The present invention, in some embodiments thereof, relates to an apparatus for processing database management system (DBMS) queries, and, more specifically, but not exclusively, to pre-compiling DBMS queries using tracing just-in-time (TJIT) compilation technology.

The current invention, in some embodiments thereof, is applicable to any DBMS, for example SQLite, MySQL, NoSQL, Key-Value, Geo-spacial store, and/or any database engine where a query is expressed in a domain specific language (DSL). The current invention may implement any DBMS configuration, for example client-server DBMS, embedded DBMS, and the like. The current invention may be implemented on any computing platform that is adapted to executing a DBMS, for example a computer, a server, a wireless computing device, a mobile computing device, and the like.

For example, mobile devices may require an embedded DBMS, referred to herein as a DBMS, in order to perform such tasks as providing access to data bases of customers, and customer relationship management (CRM) systems. However, due to limited memory and computational resources, DBMS on mobile devices may not provide acceptable performance for computationally intensive queries. In the case of a battery powered device, the computation of DBMS requests may shorten the battery life and thereby degrade the user experience.

Loops are often the most computationally intensive code of a DBMS query, and are particularly slow to execute in DBMS. As is known in the art, a loop is a sequence of instructions within a computer program that are repeated until a condition is met. Therefore, a major improvement in execution speed may be accomplished by compiling machine code for the loops. TJIT addresses this issue by identifying loops, and compiling loops into machine code at run time. Any version of TJIT may be utilized, including LuaJIT, TraceMonkey, HotPathVM, SPUR for CIL, and the like.

Traditional just in time (JIT) compilation is based on "Method-at-a-time" and implements higher-order runtime primitives that are understandable to engineers, and may be further optimized. However, traditional JIT compilers cannot always optimize higher-order primitives of the source language, which may lead to suboptimal machine code. TJIT compilation optimizes higher-order runtime primitives, and generates machine code fragments for loops, which are close to optimal performance.

Pre-compiling queries into a TJIT source code, referred to herein as a Kernel Code, and executing the resulting code in a TJIT VM, reduces compilation and execution overhead. Since the Kernel Code is a high level source code, the Kernel Code is easier to generate, it may be further optimized by a TJIT compiler and the Kernel Code generator is easier to maintain. Also, TJIT source code allows passing different input parameters for each execution without the need to recompile. For example, a single Kernel Code may be used to retrieve different ranges of parameters without recompiling.

According to a first aspect of the present invention there is provided an apparatus for processing database management system (DBMS) queries, comprising a processor adapted to receive a DBMS query and to extract a query signature from the received DBMS query. Further, the processor is adapted, when the query signature extracted from the DBMS query is matched with an existing record in a Tracing just in time (TJIT) kernels dataset, to execute a TJIT kernel associated with the query signature in the TJIT kernels dataset by accessing the existing record from the TJIT kernels dataset, and to generate, during the execution of the TJIT kernel, a machine code for executing the DBMS query by interpreting a source code of the TJIT kernel. The processor is further adapted, when the extracted query signature is not matched with an existing record in the TJIT kernels dataset, to extract from the received DBMS query a structured query language (SQL) text, to generate, based on the extracted SQL text, a query execution plan for processing the received DBMS query, to execute the query execution plan; and to store the SQL text in association with the query signature as a new record in the TJIT kernels dataset. Furthermore, a new query signature for the SQL text may be generated. Through this application, the source code of the TJIT kernel is also referred to as Kernel Code. In a first possible implementation form of the apparatus according to the first aspect, the processor is further adapted, when the query signature extracted from the DBMS query is matched with an existing record in the Tracing just in time (TJIT) kernels dataset, to parse the DBMS query to acquire the query execution plan for the DBMS query and replace the query execution plan or at least one fragment of the query execution plan with at least one kernel instruction code to create a patched query execution plan; wherein the processor is adapted to execute the source code of the TJIT kernel based on the patched query execution plan.

In a second possible implementation form of the apparatus according to the first implementation form of the first aspect, the at least one kernel instruction code is generated according to arguments extracted from the query execution plan.

In a third possible implementation form of the apparatus according to one of the first or second implementation forms of the first aspect, the at least one kernel instruction code is adapted to be executed in a TJITed language execution environment.

In a fourth possible implementation form of the apparatus according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, the processor is adapted to generate the source code of the TJIT kernel by converting the extracted SQL text to an intermediate representation (IR) of a Domain- specific language (DSL) compiler.

In a fifth possible implementation form of the apparatus according to the fourth implementation form of the first aspect, the processor is adapted to execute a compilation pipeline according to the IR.

In a sixth possible implementation form of the apparatus according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, the source code of the TJIT kernel is executed using a library of DB- configuration-aware higher-order primitives.

In a seventh possible implementation form of the apparatus according to the sixth implementation form of the first aspect, the DB-configuration-aware higher-order primitives are functional combinators selected from a group consisting of a map function, a filter function, a reduce function, map Reduce, groupBy and a join function.

In an eight possible implementation form of the apparatus according to the seventh implementation forms of the first aspect, the higher order primitives are generated by a domain specific language (DSL) compiler, wherein the functional combinators are adapted to a specific DBMS. In a ninth possible implementation form of the apparatus according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, the source code of the TJ1T kernel is executed by Iterator-like objects executing in a TJITed language endowed with a TJIT compiler supporting tracing of execution paths and compilation of traces in machine code.

According to a second aspect of the present invention there is provided a method for processing database management system (DBMS) queries, the method comprising the steps of: receiving a DBMS query; extracting a query signature from the received DBMS query. Further, the method comprises, when the query signature extracted from the DBMS query is matched with an existing record in a Tracing just in time (TJIT) kernels dataset, executing a TJIT kernel associated with the query signature in the TJIT kernels dataset by accessing the existing record from the TJIT kernels dataset; and generating, during the execution of the TJIT kernel, a machine code for executing the DBMS query by interpreting a source code of the TJIT kernel. Further, the method comprises, when the extracted query signature is not matched with an existing record in the TJIT kernels dataset, extracting from the received DBMS query a structured query language (SQL) text, generating, based on the extracted SQL text, a query execution plan for processing the received DBMS query, executing the query execution plan; and storing the SQL text in association with the query signature as a new record of the TJIT kernels dataset. Furthermore, a new query signature for the SQL text may be generated.

Unless otherwise defined, all technical and/or scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the invention pertains. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of embodiments of the invention, exemplary methods and/or materials are described below. In case of conflict, the patent specification, including definitions, will control. In addition, the materials, methods, and examples are illustrative only and are not intended to be necessarily limiting.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

Some embodiments of the invention are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments of the invention. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments of the invention may be practiced.

In the drawings:

FIG. 1 A is a schematic illustration of components and flow of actions therebetween of an embedded SQL DBMS query processing system, as is known in the art.;

FIG. IB is a schematic illustration of components and flow of actions therebetween for processing DBMS queries, according to some embodiments of the current invention;

FIG. 2 is a schematic illustration of an exemplary system for pre-compiling and executing DBMS queries, according to some embodiments of the present invention;

FIG. 3 is a schematic flowchart of a process for executing a source code of the TJIT kernel (that is, a Kernel Code) according to some embodiments of the present invention;

FIG. 4 is a schematic flowchart of a process for pre-compiling a Kernel Code, according to some embodiments of the present invention; and

FIG. 5 is a schematic flowchart of a process for generating Kernel Codes for a specific TJIT compiler and a specific DBMS, according to some embodiments of the present invention.

DETAILED DESCRIPTION

The present invention, in some embodiments thereof, describes an apparatus that pre-compiles DBMS queries into Kernel Code and stores the resulting code for later execution. When a new query is received, the corresponding Kernel Code is executed, and loop code fragments are compiled into machine code at runtime and executed.

By reducing compilation overhead and execution time, the present invention, in some embodiments thereof, may provide a more responsive user experience for mobile computing devices, and extend battery life as a direct result of using less energy to perform DBMS queries. A further advantage of the present invention is that support for existing applications within an embedded DBMS is maintained, while compilation overhead and execution time is reduced.

Before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not necessarily limited in its application to the details of construction and the arrangement of the components and/or methods set forth in the following description and/or illustrated in the drawings and/or the Examples. The invention is capable of other embodiments or of being practiced or carried out in various ways.

The present invention may be a system, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention.

The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing.

Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network.

The computer readable program instructions may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention.

Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions.

The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions.

Reference is now made to FIG. 1A, a schematic illustration of components and flow of actions therebetween of an embedded SQL DBMS query processing system, as is known in the art. FIG. 1 A may be any SQL DBMS, for example SQL Server Compact, Advantage Database Server, SQLite, MySQL, and/or any other DBMS. The present invention, in some embodiments thereof, comprises extensions to an embedded DBMS as shown in FIG. 1 A. As shown in DBMS 101 , a DBMS comprises Query Compiler 102, Query Engine 103, and data access layer (DAL) application programming interface (API) 104 to a database, as is known in the art.

Reference is now made to FIG. IB, a schematic illustration 100 of components and flow of actions therebetween for processing DBMS queries, according to some embodiments of the current invention.

As shown in FIG. IB, schematic illustration 100 comprises two functional units, 100A and 100B. 100A comprises components and flow of action therebetween for executing a pre-compiled query. 100A may be implemented by code modules executing on processor 204, for example Query Selector 210, Plan Patcher 21 1 , Kernel Executor 212, and TJIT VM 213.

100B comprises components and flow of action therebetween for generating Kernel Codes. 100B may be implemented by code modules executing on processor 204, for example SQL to IR Converter 215, DAL API 216, and Application Specific Kernel Generator 217.

The extensions to FIG. 1A to execute a query, as shown in 100A, comprise generating a signature for each received DBMS query and comparing the signature with TJIT kernels dataset. When a matching signature is found, context information is identified in the received query to be passed into the Kernel Code as input parameters. At least some segments of the Kernel Code are executed in a TJIT VM, which supports tracing of execution paths, compilation of traces of loops into machine code, and executing the machine code. Segments of Kernel Code may also execute in a traditional SQL execution environment. 100A may be executed by a system, for example System 200 as described below. The functionality of 100A may be described by a process, for example as described in FIG. 3 below.

When a matching signature is not found, selected received queries are stored with corresponding signatures in a table, referred to herein as a TJIT kernel dataset. A Kernel Code is later generated from the stored query, as described below.

The extensions to FIG. IB for generating Kernel Codes, as shown in 100B, comprises translating the received query from SQL into a TJIT source code, including higher-order primitives that replace SQL operators. 100B may be executed by a system, for example System 200 as described below. The functionality of 100B may be described by a process, for example as described in FIG. 4 and FIG. 5 below. According to some embodiments of the present invention, schematic illustration 100 is an extension of a DBMS, for example as shown in FIG. 1A. FIG IB illustrates an extension of SQLite, however any embedded DBMS may be used. The TJIT shown in FIG. I B is LuaJIT, however other TJIT compilers may be used.

Reference is now made to FIG. 2, a schematic illustration of an exemplary system for pre-compiling and executing DBMS queries, for example as shown in FIG. I B, according to some embodiments of the current invention.

System 200 includes an input/output (I/O) interface 202 for receiving user queries and outputting query results, a processor(s) 204, and a storage 208. I/O 202 may include one or more input interfaces, for example a keyboard, a soft keyboard, a voice to text system, and/or any other data input interface. I/O 202 may comprise one or more output interfaces, for example a screen, a touch screen, video display, and or any other visual display device. Processor(s) 204 may comprise one or more processors, multi-core processors, and/or any other type of core processing unit (CPU). Storage 208 may include one or more non-transitory persistent storage devices, for example, a hard drive, a Flash array and the like. Storage 208 may comprise a database, for example database 104, and a table of records, for example TJIT kernel dataset 1 15.

100A and 100B may be executed by processor 204 executing code from by one or more software modules in storage 208, for example Query Selector 210, Plan Patcher 21 1 , Kernel Executor 212, TJIT VM 213, and/or DSL Compiler 214. Wherein a software module refers to a plurality of program instructions stored in a non-transitory medium such as the storage 208 and executed by a processor such as the processor(s) 204. DSL Compiler 214 may comprise one or more software modules, for example SQL to IR converter 215, DAL API 216, and Application Specific Kernel Code Generator 217.

Reference is now made to FIG. 3, a schematic flowchart of a process for executing a Kernel Code, according to some embodiments of the present invention. As described above, FIG. 3 describes the functionality as shown in 100A. As shown in 301, 100A starts with receiving a DBMS query, for example from I/O 202, and query selector 210 computes a signature for the received query, as is known in the art. As shown in 302, query selector 210 searches TJIT kernel dataset 1 15 for a Kernel Code with a signature matching the received query. Optionally, each TJIT kernel dataset record comprises either a Kernel Code or a received query. In addition, each record comprises an associated signature, metadata, and a field with value of either "active" or "inactive". Inactive TJIT dataset records comprise DBMS queries that have not yet been pre-compiled into Kernel codes. Active TJIT dataset records comprise DBMS queries that have been pre-compiled into a Kernel Code. The process of pre-compiling Kernel Codes is described in FIG. 4 below. Metadata comprises information that describes the Kernel Code, for example database columns and/or fields from different tables, indexes that are accessed by the Kernel Code, information that characterizes Kernels, lists of tables and columns which are accessed by the Kernel Code, and the database schema. Metadata and the schema are used in retrieving information from the database, as described below.

When a match is detected, the received query is marked for further processing, for example by plan patcher 21 1.

Optionally, query selector 210 computes a signature only for loops detected in the received query, and not for the entire received query.

Optionally, query selector 210 may identify a plurality of Kernel Codes with matching signatures. Optionally each of the plurality of matching signatures each corresponds to a loop identified in the received query.

As shown in 303, context information from the received query is identified, for example by plan patcher 21 1 , and is supplied as input parameters to the Kernel Code. The context information may comprise Cursorld, Tableld, Databaseld, and the like, as is known in the art. An execution plan is generated, as is known in the art, and a patched plan is generated from the execution plan. Optionally, the patched plan comprises identifying loops in the execution plan, and replacing those loops with a special instruction, referred to herein as a kernel instruction. Optionally, loops are identified and replaced with a kernel instruction when the execution plan is generated. See code fragment 7 below for an example of the kernel instruction.

The patched plan may be generated using a "hot path stiching" mechanism, which facilitates stitching of execution paths which are otherwise separated by control-flow passing between kernel code and DBMS system code. This in particular means that the fragment of the query execution plan being replaced with at least one kernel instruction code might not be the whole loop, but only the body of the loop. When only loop bodies are considered, special mechanism for stitching together compiled traces can be used.

The execution control flow in the case of loop body fragments may comprise the following steps:

1 ) The loop is started execution in DBMS

2) During execution of the loop body on every iteration kernel code is executed a) control flow is passed to TJITed VM using setjmp/longjmp or equivalent instructions supported by path- stitching mechanism of TJIT-ed VM. b) kernel code is executed

c) control flow is passed back to DBMS using setjmp/longjmp or equivalent instructions supported by path-stitching mechanism of TJITed VM.

3) After the kernel code is executed the execution of the loop body is finished and the DBMS steps to the next iteration of the loop.

Path-stitching mechanism is special in TJIT-ed VM, to handle such kind of situations when the loop is defined outside of the TJITed VM, but the body of the loop is executed in TJIT VM.

As shown in 304, the Kernel Code from the corresponding TJIT dataset record is instantiated and the extracted context information is provided to the Kernel Code as input parameters, for example by kernel executor 212. The Kernel Code is executed, for example by kernel executor 212. Kernel executor 212 may call TJIT VM 213 that executes the Kernel Code, for example by calling a designated method of the kernel instance object. Kernel executor 212 further comprises a standard SQL execution environment.

The Kernel Code comprises SQL instructions, TJIT source code, and/or kernel instructions. Kernel instructions are pre-compiled into TJIT source code from a loop extracted from a received query and/or pre-compiled from the query itself. At runtime, a TJIT VM, for example TJIT VM 213, traces the loop, compiles the trace into machine code, and executes the machine code. The patched execution plan and/or the Kernel Code send queries and receive replies from a database, for example database 104.

As shown in 305, when the received query signature does not match a Kernel Code signature of a TJIT dataset record, an execution plan is prepared by plan patcher 21 1 , as is known in the art. The execution plan is executed by kernel executor 212, including accessing the DAL API of the database, as is known in the art. As described above, a received query that does not have a matching Kernel Code may be stored in TJIT dataset table along with a corresponding signature to be pre-compiled. Optionally, query selector 210 comprises code instructions to compute, based on user provided parameters or other criteria, which DBMS queries to store as a record in the TJIT dataset for pre-compilation.

Reference is now made to FIG. 4, a flow chart of a process for pre-compiling and storing Kernel Codes, for example 100B, according to some embodiments of the present invention.

As shown in 401 , a record in TJIT dataset that has a value "inactive" is identified, for example by code instructions in DSL compiler 214. As shown in 402, when an inactive record is found, the pre-compilation process continues as shown in 403 below. Optionally, execution of 100B may be triggered by query selector 210 storing an inactive record, by a timing trigger, and/or the like.

As shown in 403, the query text is parsed; the SQL text is extracted and converted into a graph-based intermediate representation (IR), for example by SQL to IR converter 215. As shown in 404, a Kernel Code is generated from the IR. The process of generating the Kernel Code is described below referencing again FIG. 5.

As shown in 405, the generated Kernel Code is copied to the corresponding kernel dataset record, and the record is set to "active", for example by DSL Compiler 214. As shown in 402, Steps 403, 404, and 405 are repeated until all records in TJIT dataset are marked active.

Reference is now made to FIG. 5, a process for generating Kernel Codes for a specific TJIT compiler and a specific DBMS, for example 100B, according to some embodiments of the current invention. The operations for calculating the Kernel Code may be executed by code instructions, for example by SQL to IR 215, DAL API 216, and Application Specific Generator 217. As shown in 501 , a query is sent to a database, for example database 104 by DAL API 216, and a reply is received comprising the database schema, as is known in the art. See code fragment 4 below for an example of a DBMS schema. DAL API 216 transfers the received schema configuration to a Kernel generator 502.

As shown in 503, a query is sent to TJIT dataset 1 15, for example by SQL to IR Converter 215, and a reply is received comprising a TJIT dataset record that is marked "inactive", and converts the query to an IR. SQL to IR Converter 215 transfers the IR to a Kernel Code generator 502.

Optionally, Kernel Code Generator 502 performs the following operations, for example by Application Specific Generator 217. The SQL operators that are present in the IR are translated into the higher order primitives, as described below. The compilation pipeline of Application Specific Kernel Code Generator 41 1 is executed on the IR which generates TJIT source code. Optionally, a loop present in the IR is compiled into a kernel instruction, as described above. The resulting TJIT source code is the Kernel Code.

Optionally, prior to generating the first Kernel Code, a library of higher order primitives and a DBMS abstraction layer is created, for example by DSL compiler 214 and/or by manually writing source code, which allows the Kernel Code to access data in the DBMS. Optionally, the generated higher order primitives are specialized combinators that are associated with the specific DBMS. The library of higher order primitives is translated from SQL operators. For example SQL "SELECT" is translated to higher order primitive "map", "WHERE" is translated to "filter", and "JOIN" is translated to "join".

Optionally, the library of higher order primitives is compiled into the Kernel Code source code by Application Specific Kernel Code Generator 41 1 to replace SQL operators found in the received query.

Optionally, the higher order primitives, when executed, call software functions that are implemented by the aforementioned DBMS abstraction layer. The DBMS abstraction layer provides the library of higher order primitives with underlying code that provides access to a DBMS, and for this reason is DBMS specific. For example, different DBMS abstraction layers would be written for SQLite and MySQL. Reference is now made again to FIG. IB, comprising 100A and 100B. User application 240 may send query 250 to a system, for example system 200. As described above, selected new queries are stored and then pre-compiled into Kernel Codes, and when a corresponding Kernel Code is stored, the Kernel Code is executed in place of the received query. As shown in 1 16, the process of processing a query request, for example as described in FIG. 3, is illustrated with solid arrows between components of 100A. As shown in 1 17, the process of generating a Kernel Code, for example as described in FIG. 4 and FIG. 5, is illustrated with hollow arrow between components of 100B.

The process of generating a Kernel Code from a received query, as shown in FIG. 4 and FIG. 5, is shown by way of example by the following Code Fragments. An exemplary received query, in this example SQL DBMS query Ql from the benchmark Transaction Processing Council standard H (TPC-H) is shown now in Code Fragment 1.

CODE FRAGMENT 1 : "TPC-H Ql "

Ql :

select

l_returnflag, l_linestatus,

sum(l quantity) as sum_qty,

sum(l_extendedprice) as sum_base_price,

sum(l_extendedprice*(l -l_discount)) as sum_disc_price,

sum(l_extendedprice* ( 1 -l discount)* ( 1 +l_tax)) as

sum_charge, avg(l_quantity) as avg_qty,

avg(l_extendedprice) as avg_price,

avg(l_discount) as avg_disc, count(*) as count_order

from lineitem

where l shipdate <= Ί 998-12-0 Γ

group by l_returnflag, l_linestatus

order by l_returnflag, inestatus;

Of special interest in Code Fragment 1 is table lineitem (shown in italics), which is implemented according to the db schema as shown in Code Fragment 4, and SQL operative where, that is shown in Code Fragment 2 to be translated into the higher order primitive "filter".

Code Fragment 2 is the TJIT source code the output from pre-compiling of Ql into the Kernel Code, as described above in FIG 5.

Code Fragment 2: Ql translated into TJIT Source Code function projectLineitem(li) return {

l extendedprice = li.l_extendedprice, l_discount = li.l_discount, l_tax = li.l_tax, l_quantity = li.l_quantity, l_shipdate = li.l shipdate, Meturnflag = li.l_returnflag, Minestatus = li. Minestatus, }

end

function projectLineitemU(out, li)

out.l_extenedprice = li.l_extendedprice; out.l_discount = li.l_discount out.l_tax = li.l tax; out.l_quantity = li.l_quantity

out.l_shipdate = li.l shipdate; out.l_returnflag = li.l_returnflag out.Minestatus = li.l_linestatus; return out

end

function predicate(lineitem) return lineitem.l shipdate <= 19981201 ; end function mapKey(key, lineitem)

key. eturnflag = lineitem. l_returnflag; key.l_linestatus = lineitem. Minestatus;

end

function newKey()

local key = ffi.new("GroupBy"); key. Meturnflag = 0; key.Minestatus = 0; return key

end

function mapValue(value, lineitem)

value, sumjqty = lineitem. l_quantity; value. sum_base_pnce = lineitem. l_extendedprice; value. sum_disc_price lineitem. l_extendedprice*(l- lineitem.l_discount); value. sum_charge lineitem. l_extendedprice * ( 1 - 1 i neitem . l_di scount) * ( 1 +lineitem. Max) ; value.sum_disc = lineitem.l_discount; value. count_order = 1 ;

end

function newValue()

local value = ffi.new("Aggregate"); value.sum_qty = 0; value. sum_base_price

= 0;

value.sum_disc_price = 0; value.sum_charge = 0; value.sum disc = 0;

value. count_order = 0; return value

end

function value2Table(value)

local res = { } ; res.sum_qty = value. sum_qty;res.sum_base_price = value. sum_basej>rice; res.sum_disc_price = value. sum_disc_price;

res.sum_charge = value. sum_charge; res.sum_disc = value. sum_disc; res.count_order = value. count_order; return res

end

function packKey(key)

return key.l_returnflag .. ',' ·· key. inestatus

end

function reduceValue(dst, src)

dst.sum_qty = dst.sum_qty + src.sum_qty;

dst.sum_base_price = dst.sum_base_price + src.sum_base_price;

dst.sum_disc_price = dst.sum_disc_price + src.sum_discjprice;

dst.sum_charge = dst.sum_charge + src.sum_charge;

dst.sum_disc = dst.sum_disc + src.sum_disc;

dst.count_order = dst.count_order + src.count_order;

End

function projectionU(out, key, value)

out.l_returnflag = key.l_returnflag;

out.l linputestatus = key.Minputestatus;

out.sum_qty = value. sum_qty;

out.sum_base_price = value. sum_base_price;

out.sum_disc_price = value. sum_disc_price; out.sum_charge = value. sum_charge;

out.avg_qty = value. sum_qty / value. count_order;

out.avg_price = value. sum_base_price / value. count_order;

out.avg_disc = value. sum_disc / value. count_order;

out.count_order = value. count_order;

end

function Ql (lineitems)

return lineitems

:mapU(projectLineitemU, ffi.new("LineitemProjection"))

:/z/ier(predicate)

:mapReduceU(mapKey, mapValue, reduceValue, packKey, newKey, newValue)

end

Of special interest in Code Fragment 2 is the "filter" and "mapReduceU" higher order primitives (shown in italics), which are translated from the "WHERE" and "GROUP BY" SQL operators. In the exemplary case of Code Fragment 2, the received SQL query has been the source code is the LuaJIT.

As shown in Code Fragment 3, an exemplary loop, for example from Code Fragment 2, is compiled by TJIT VM into machine code at runtime, as described above.

Code Fragment 3: Machine code compiled at run time from Code Fragment 2

fa6ffa9f and byte [r 12+0x4], Oxfb

fa6ffaa5 mov edi, [0x0965f3f4]

->LOOP:

fa6ffab9 movsd [rsp+0x50], xmm3

fa6ffaf3 cmp edi, [0x0965Ddc]

fa6ffafajb 0xfa6ffbl3

fa6ffb01 mov edi, 0x0965f3b8

fa6ffb06 call 0xl 094337a0 ->lj_gc _stepjit fa6ffb0b test eax, eax

fa6ffb0d jnz 0xfa6f0058 ->18

fa6ffc76 cvttsd2si rl2, xmm7

fa6ffc7b imul rl l , rl2, 0x98

fa6ffc82 mov [rsp+0x48], rl 1

fa6ffc87 mov rl2, rl l

fa6ffc8a add rl2, rbp

fa6ffc8d add rl2, 0x98

fa6ffc94 mov [rsp+0x38], rl2

fa6ffc99 mov esi, 0x10

fa6ffc9e call 0xl 094338c0 ->lj_mem_newgco

fa6ffe27 mov [0x0965Df4], rl2d

fa6ffe2f mov [rl2+0xc], edi

fa6ffe34 jmp 0xfa6ffab9 ->LOOP

An example of the implementation of the "lineitem" table from the TPC-H Ql is shown in Code Fragment 4, which comprises part of the schema that is used by Application Specific Kernel Generator 217 to enable the generated TJIT source code to perform read access to the database, for example database 104.

Code Fragment 4: schema implementation.

create table lineitem(

l_orderkey integer,

1 _partkey integer,

l_suppkey integer,

inenumber integer,

l_quantity real,

l_extendedprice real, discount real,

tax real,

returnflag char,

linestatus char,

shipdate date,

commitdate date,

receiptdate date,

shipinstruct varchar,

shipmode varchar,

comment varchar);

create index lineitem_pk on lineitem(l_orderkey, l_linenumber);

create index lineitem_order_fk on lineitem(l_orderkey);

create index lineitem_supp_fk on lineitem(l_suppkey);

create index lineitem__part_fk on lineitem(l_partkey);

create index lineitem_ps_fk on lineitem(l_partkey, l_suppkey);

create index part_pk on part(p_partkey);

An exemplary fragment of a DBMS abstraction layer, as described above is shown in Code Fragment 5. Code Fragment 5 comprises an implementation of the higher order primitive "filter" for SQLite. As described above, the DBMS abstraction layer is DBMS specific, and this implementation would vary for a different DBMS.

Code Fragment 5: Implementation of "filter" higher-order combinator function Filterlter:next()

local elem = self.source:next()

while elem and not self.predicateFunc(elem) do

elem = self.source:next() end

return elem end

A section of the DBMS abstraction layer comprising an implementation of an interface to an iterator like object, as is known in the art is shown in Code Fragment 6. Code Fragment 6 demonstrates how the Iterator like interface hides from higher order combinators any functions derived from SQLite namespace.

Code Fragment 6: implementation of iterator like interface

function createSQLiteTableIter(tableInfo, pCrsr, rowParser, initFieldsPtrs)

local max_column = tablelnfo. columnsNum

local res = SQLiteTableIter:new({ tablelnfo = tablelnfo,

max column = max_column,

rowBuffer = ffi.new(tablelnfo.bufferCTypeName), - e.g. "LineitemProjection" pCrsr = pCrsr, finish = nil,

rowParser = rowParser,

initFieldsPtrs = initFieldsPtrs,

res64 = ffi.new("long[l]"), res32 = ffi.new("int[l]"), aOffset = ffi.new("int[?]", max_column+l),

aType = ffi.new("int[?]", max_column+l),

pChunk = ffi.new("str_chunk"),

} )

res :initFieldPtrs(res. rowBuffer)

res.rc = C.sqlite3BtreeFirst(pCrsr, res.res32)

return res

end function SQLiteTableIter:next()

if self.fmish then return nil end

C.sqlite3BtreeKeySize(self.pCrsr, self.res64) local row = C.sqlite3BtreeDataFetch(self.pCrsr, self.res32);

C.vdbe_ParseHeader(row, self.aOffset, self.aType, self.max_column)

sel f :rowParser(row)

self.res32[0] = 0

self.rc = C.sqlite3BtreeNext(self.pCrsr, self.res32) if self.rc ~= 0 then error("SQLITE_ERROR") end self.fmish = self.res32[0] ~- 0 return selfrowBuffer end

function SQLiteTableIter:parseDouble(row, columnid, pBuf)

C.sqlite3VdbeSerialGetDouble(row + self.aOffset[columnId], self.aType [columnid], pBuf)

end

function SQLiteTableIter:parseChunk(row, columnid, pBuf, columnName)

C.sqlite3VdbeSerialGetChunk(row + self.aOffset[columnId], iter.aType[columnId], pBuf)

self.rowBuffer[columnName] = pBuf.ptr[0]

end An example of plan patcher 21 1 replacing a loop with a kernel instruction, as described above, is shown in Code Fragment 7.

Code Fragment 7: plan patcher substitutes kernel instruction for loop SQL commands.

Cursorld Tableld Databaseld

As shown on the left side of code fragment 7, a received query comprises SQL loop shown within the inner blue arrows. As shown on the right side of code fragment

7, the "kernel" instruction replaces the SQL loop instructions.

The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

It is expected that during the life of a patent maturing from this application many relevant TJIT will be developed and the scope of the term TJIT is intended to include all such new technologies a priori.

As used herein the term "about" refers to ± 10 %. The terms "comprises", "comprising", "includes", "including", "having" and their conjugates mean "including but not limited to". This term encompasses the terms "consisting of and "consisting essentially of.

The phrase "consisting essentially of means that the composition or method may include additional ingredients and/or steps, but only if the additional ingredients and/or steps do not materially alter the basic and novel characteristics of the claimed composition or method.

As used herein, the singular form "a", "an" and "the" include plural references unless the context clearly dictates otherwise. For example, the term "a compound" or "at least one compound" may include a plurality of compounds, including mixtures thereof.

The word "exemplary" is used herein to mean "serving as an example, instance or illustration". Any embodiment described as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments and/or to exclude the incorporation of features from other embodiments.

The word "optionally" is used herein to mean "is provided in some embodiments and not provided in other embodiments". Any particular embodiment of the invention may include a plurality of "optional" features unless such features conflict.

Throughout this application, various embodiments of this invention may be presented in a range format. It should be understood that the description in range format is merely for convenience and brevity and should not be construed as an inflexible limitation on the scope of the invention. Accordingly, the description of a range should be considered to have specifically disclosed all the possible subranges as well as individual numerical values within that range. For example, description of a range such as from 1 to 6 should be considered to have specifically disclosed subranges such as from 1 to 3, from 1 to 4, from 1 to 5, from 2 to 4, from 2 to 6, from 3 to 6 etc., as well as individual numbers within that range, for example, 1 , 2, 3, 4, 5, and 6. This applies regardless of the breadth of the range.

Whenever a numerical range is indicated herein, it is meant to include any cited numeral (fractional or integral) within the indicated range. The phrases "ranging/ranges between" a first indicate number and a second indicate number and "ranging/ranges from" a first indicate number "to" a second indicate number are used herein interchangeably and are meant to include the first and second indicated numbers and all the fractional and integral numerals therebetween.

It is appreciated that certain features of the invention, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the invention, which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable subcombination or as suitable in any other described embodiment of the invention. Certain features described in the context of various embodiments are not to be considered essential features of those embodiments, unless the embodiment is inoperative without those elements.

All publications, patents and patent applications mentioned in this specification are herein incorporated in their entirety by reference into the specification, to the same extent as if each individual publication, patent or patent application was specifically and individually indicated to be incorporated herein by reference. In addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention. To the extent that section headings are used, they should not be construed as necessarily limiting.