Efficient data decoding using runtime specialization

Computer-implemented techniques described herein provide efficient data decoding using runtime specialization. In an embodiment, a method comprises a virtual machine executing a body of code of a dynamically typed language, wherein executing the body of code includes: querying a relational database, and in response to the query, receiving table metadata indicating data types of one or more columns of a first table in the relational database. In response to receiving the table metadata: for a first column of the one or more columns, generating decoding machine code to decode the first column based on the data type of the first column, and executing the decoding machine code to decode the first column of the one or more columns.

FIELD OF THE INVENTION

Embodiments relate generally to techniques for optimizing decoding operations.

BACKGROUND

When reading data from a relational database (e.g., the result set of a query), a driver first receives metadata about the structure and constraints of the data followed by a stream of raw data blocks from the database. The driver then decodes the received raw data into data items that can be delivered to the user. This step must be done for each value of each row of every column in the result set of a query.

Database drivers for statically typed programming languages such as Java require the user to provide the expected output type when decoding a value. The following code snippet shows an abstract example in Java using the Java Database Connectivity (JDBC) API:

In the above example, a query is submitted to a database system through JDBC and a result set handle is returned. With that handle, a user can explore the metadata and fetch data into the user's Java program. When fetching data from a result set, a driver is responsible for getting the raw data of rows from the database systems (e.g. “rs.next( )”) and for decoding values into a form that can be represented in Java. In statically typed languages, the specification of how to decode a value is given by the user. For example, the call “rs.getInt(2)” explicitly tells the driver to get the value of the column with index2in form of a Java integer.

In contrast, dynamically typed programming languages (e.g., JavaScript, Ruby, Python) do not provide ways to specify the data type that a column of a row should be converted into. Data types are dynamically inferred and verified by the language at runtime. The following code snippet shows how reading a column value might look like in JavaScript:

In contrast to statically typed programming languages such as Java where the user provides the expected output type when decoding a value, the type of the “studentId” column in the above code example is decided by the driver at runtime and is typically based on some well-documented default mapping between the database types and the language types. The driver exploits the metadata (e.g. database types, column constraints) provided by the database to automatically decode the received raw bytes into a value of the appropriate type.

The interpretation of metadata to select the correct data decoding method is a performance critical part of a database driver. It typically involves interpretation cost on every retrieval of a column from a result set, e.g., the implementation would have to use lookups at run-time and might look like as follows:

As shown in the above code example, when a user requests a value from the driver, the driver performs several lookups to determine the specific function that performs the correct decoding for the value. For example, if the source data type of a requested value is VARCHAR with the constraint NOT NULL, the function get(1) would dispatch to getString(1) that decodes the raw data into a JavaScript string.

The key issue with this approach to decoding for dynamic programming languages is that determining the correct decoding function must be done for every value a user requests, imposing significant overhead as result.

Based on the foregoing, an approach for reducing overhead of decoding operations using dynamically typed languages is desired.

DETAILED DESCRIPTION

General Overview

Computer-implemented techniques described herein provide efficient data decoding using runtime specialization.

When a user queries a relational database, a driver first receives metadata about the structure and constraints of the requested data followed by a stream of raw data blocks from the database. The driver then decodes the received raw data into data items that can be delivered to the user.

Dynamically typed programming languages (e.g., JavaScript, Ruby, Python) do not provide ways to specify the data type that a column of a row should be converted into for the user. Instead, datatypes are dynamically inferred and verified by the language at runtime. Typically, when a user requests a value from a driver, a database driver for a dynamically typed programming language performs several lookups to determine a specific function that performs the correct decoding for the requested value. Determining the correct decoding function must be done for every value a user requests from the database.

Instead of performing a function lookup each time a value of a row of a column is accessed, the metadata for each column can be used to generate a decoder, during runtime, for each column that is accessed by a query. A “decoder” as referred to herein is an executable program that performs the translation of formatted data into a different format. The generated decoders may then be automatically in-lined into the program that triggers the decoding operation by a JIT compiler and used each time a row is accessed from a column for which a decoder has been generated. Decoders may be further specialized at runtime based on assumptions drawn from the column metadata.

References to “runtime” in the paper may refer to several instances of runtime. First, the initial generation and use of a decoder occurs at runtime of a user program. Second, each decoder has a creation time at which the decoder is generated and statically specialized/concretized but not yet used. Third, each decoder has its own runtime at which the decoder is used and modified through using runtime specialization.

Using this approach, the overall efficiency of decoding operations for dynamic programming languages may benefit from generating decoders at runtime for each column of a table that is accessed. Whenever a user reads a value of a column for which a decoder has already been generated, the generated decoder is directly invoked instead of performing a computationally expensive function lookup, and overhead is reduced.

System Overview

FIG. 1illustrates an example system100in which the described techniques may be practiced, according to an embodiment.FIG. 1is but one example of a system in which the described techniques may be practiced. Other systems may include fewer or additional elements in varying arrangements.

System100comprises an execution platform126that includes a runtime environment102. The runtime environment102includes a virtual machine104comprising various components, such as a just-in-time (JIT) compiler110for producing optimized machine code such as a decoder108. A “decoder” as referred to herein is an executable program that performs the translation of formatted data into a different format. By way of non-limiting example, runtime environment102may be Node.js for executing JavaScript-based applications, or a runtime for executing code written in any other suitable language.

In an embodiment, the computing system100includes source code files122that contain code that has been written in a particular programming language, such as Java, JavaScript, C, C++, C#, Ruby, Perl, and so forth. Thus, the source code files122adhere to a particular set of syntactic and/or semantic rules for the associated language. For example, code written in JavaScript adheres to the JavaScript Language Specification. Source code files122or representations thereof may be executed by the execution platform.

In an embodiment, the components or processes of runtime environment102are invoked in response to an operating system114receiving a request to execute source code122that is associated with runtime environment102. For instance, the operating system114may be configured to automatically start executing the runtime environment102when receiving requests from database120or a client associated with the runtime environment102. In an embodiment, the runtime environment102may be implemented by compiled code that is embedded directly within a file or files that contain program code. In an embodiment, runtime environment102may be a set of components or processes that an operating system114persistently executes, or may even be the operating system114itself.

In an embodiment, runtime environment102may be or include a virtual machine104configured to interpret program code in a platform independent language, and issue instructions to a processor, such as processor116, that cause the processor116to implement the source code112or execute the decoder108. Runtime environment102may therefore compile, translate, or otherwise convert higher-level instructions found in source code112into lower-level instructions executable by processor116and/or by an intermediate component such as an operating system114.

In an embodiment, the virtual machine104includes at least a dynamic compiler or translator, such as the just-in-time compiler110. The dynamic compiler translates certain portions of source code122to compiled code as the source code122is being executed. In some embodiments, the runtime system102will begin executing source code122by interpreting the source code122. The dynamic compiler will monitor the execution of source code122for portions that are frequently repeated, and generate compiled versions of those portions.

In other embodiments, the just-in-time compiler110may be used during runtime to dynamically compile an executable decoder108. Using techniques described herein, the decoder108may be dynamically compiled by the just-in-time compiler110and may be optimized to decode data received from the database120into an appropriate format to be delivered to a client.

In other embodiments, some or all of source code122may be code that is already compiled in a form that is directly executable by a processor116or intermediate operating system114. In an embodiment, processor116or an intermediate component such as an operating system114allocates a managed memory area118for use by the runtime environment102.

In an embodiment, source code122may include commands to query the database120. The database122or a database driver may deliver result sets of data to the execution platform126based on the query. A driver in the execution platform126may receive metadata describing the structure and constraints of the requested data specified in the query, followed by a stream of raw data blocks. The driver in the execution platform126may then decode the received raw data into data items that can be delivered to a client in the appropriate format.

In an embodiment, database120includes a relational database that stores data in the form of tables and maintains metadata for each column of a table. In general, metadata includes information about the source data types of the values of each column of a table (e.g., NUMBER, STRING). The metadata may also include information such as: a flag or other information that indicates whether there can be NULL values in a column, a value range of numeric columns, a character set of a textual column, and a statically known size of specific database types.

Dynamically Typed Languages

A dynamic language is a programming language, which, at runtime, can execute many common programming behaviors that statically typed programming languages perform during compilation. These behaviors could include extending the program by adding new code, extending objects and definitions, or by modifying the type system. Some examples of dynamic languages include JavaScript, Python, PHP, and Ruby.

A programming language is dynamically typed if it performs type checking at runtime. Type checking is the process of verifying that a program is type safe. A program is type safe if the arguments of all of its operations are the correct type. Dynamic languages such as JavaScript, Python, PHP, and Ruby verify types at runtime, rather than at compile time, that values in an application conform to expected types. These languages typically do not have any type information available at compile time. The type of an object can be determined only at runtime.

In contrast, a programming language is statically typed if it performs type checking at compile time. Java is a statically typed language. All typed information for class and instance variables, method parameters, return values, and other variables is available when a program is compiled. The compiler for the Java programming language uses this type information to produce strongly typed bytecode, which can then be efficiently executed by the JVM at runtime.

Just in Time Compilation

In general, a compiler is a computer program(s) that transforms source code written in a programming language into binary object codes such as assembly language or machine code. Dynamic languages feature a type of compilation called just in time compilation (“JIT”). Just in time compilation is compilation done during execution of a program—at run time—rather than prior to execution. Most often this consists of translation to machine code, which is then executed directly, but can also refer to translation to another format. A system implementing a JIT compiler typically continuously analyses the code being executed and identifies parts of the code where the speedup gained from compilation would outweigh the overhead of compiling that code.

A JIT compiler offers an API to generate code at runtime. The code generator may be a low-level code generator, such as LLVM, or a more elaborate JIT-compiler, such as the Graal compiler from Oracle, wherein generated code is first described as an abstract syntax tree that is JIT-compiled at run-time. A JIT-compiler can be utilized to generate aggressively specialized code. A JIT-compiler may also be utilized to invalidate and replace specialized code. A JIT-compiler may be utilized to in-line generated decoders into a program that triggers a decoding operation. The capabilities of a JIT-compiler are further described below.

Data Decoder Generator

When a client (e.g., a user program written in a dynamically typed programming language) queries a relational database, a database driver first computes the metadata of the result table and sends it to the client. The metadata for a result table may include information about the source data types of the values of each column of a table (e.g., NUMBER, STRING). The metadata may also include information such as: a flag or other information that indicates whether there can be NULL values in a column, a value range of numeric columns, a character set of a textual column, and a statically known size of specific database types. The client can then request, via the driver, the next row of the result table until all rows of the table are consumed.

For example, consider the code snippet below:

The code snippet includes a while loop that retrieves values from columns with indexes “1” and “2” of the “students” table. The term “code snippet” referred to herein is defined as a re-usable source code (e.g. a block, set, or sequence of statements written in a computer language) or intermediate code (byte code). This particular example requires numerous column read operations (i.e., the get( ) function calls) for the query. Because of the nature of dynamically typed programming languages, type checking is performed at runtime for each value access.

Thus, in this example, each time the “get( )” function is called, metadata for the referenced column index (e.g. “1” or “2”) is accessed by a driver and the driver performs several lookups to determine a specific function that performs the correct decoding for a client.

Instead of performing a lookup each time a value of a row of a column is accessed, the metadata for each column can be used to generate a specialized decoder for each column that is accessed by a query. The generated decoders may then be automatically in-lined into the program that triggers the decoding operation by a JIT compiler and used each time a row is accessed from a column for which a decoder has been generated.

FIG. 2is a flow chart that illustrates the initial generation of a decoder at runtime. In general, a data decoder generator creates and installs specialized decoding code based on the metadata for a set of values (e.g., a table column). Steps204-210are intended to illustrate the generation of pieces of code (e.g. code snippets) that serve as building blocks to compose a final decoder.

In step202, metadata is received from a database. The metadata may be received in response to a read operation transmitted to the database.

In step204, a basic column converter code snippet is generated that provides the needed “boiler plate” code for a new decoder being generated at runtime of a user program. In other words, a new decoder gets instantiated.

FIG. 3illustrates the generation and specialization of a decoder at different points in time. The basis column converter302is shown inFIG. 3in form of an Abstract Syntax Tree (AST), which can be used to implement the decoder generation process. A basic column converter302consists only of a node for reading a raw value and does not contain any code for doing actual conversions.

In step206, a configured column converter code snippet is generated based on the metadata received in step202and added to the basic column converter code snippet generated in step204. For example, based on the received metadata, the data type/encoding of the raw data from the database is known (e.g. VARCHAR), as well as the data type/encoding required as output by the client (e.g. JavaScript string). Based on this knowledge, a code snippet is generated that implements the desired decoding from input data type to output data type.

The configured column converter304shown inFIG. 3illustrates step206fromFIG. 2. For example, in addition to the node for reading a raw value as discussed with respect to the basic column converter302, a generic conversion node is added to the AST. Generic means that the added conversion code is capable of correctly converting every possible raw input value. During execution time when the generated decoder already is in use, the generic conversion node as well as any other node of the AST can be replaced by a more specialized node based on assumptions made while using the decoder for an extended period of time. For example, the generic conversion node may be replaced by a conversion node that operates faster but can only convert integer values between 0 and 127.

In step208, a specialized column converter code snippet is generated based on the metadata received in step202and added to the configured column converter code snippet generated in step206. The metadata is analyzed to determine if additional code snippets must be added to further concretize the decoder at creation time. For example, if the metadata does not contain any information regarding potential NULL values of a column (e.g. the column is NULLable), a code snippet must be added that implements a check that tests each input value for NULL and handles them accordingly. However, if the metadata states that there cannot be NULL values for a column (e.g. the column is not NULLable), the NULL handling is omitted from the decoder.

The specialized column converter306shown inFIG. 3illustrates step208fromFIG. 2. For example, the specialized column converter306depicts a case where a check for NULL values is needed. In addition to the node for reading a raw value as discussed with respect to the basic column converter302and the generic conversion node as discussed with respect to the configured column converter304, a check NULL value node is added to the AST. The check NULL value node first uses the read raw value node to read a raw value and checks if the raw value is a NULL value. If the raw value is not a NULL value, the generic conversion node is used to create the output value. Otherwise, the NULL value is reported as the output value without performing a conversion.

Other specializations may be added via speculations on assumptions that can be invalidated in mid-flight (i.e., during runtime). For example, the metadata might indicate that a column contains numbers but does not specify a value range. In this case, a code snippet can be generated that is capable of decoding any value with number type. However, when the generated decoder already has been used for some time, an additional assumption can be made that all numbers of a specific table column are positive integers because all values processed so far fulfill that assumption. In this case, a code snippet is generated that specializes in decoding positive integers for the specific table column, further optimizing the decoding operation.

In such a case, any previously generated decoder for the specific table column is replaced by a new decoder that only can decode positive integer numbers. If the speculative assumptions are true for each row value access, the new, specialized decoder can be used to achieve a higher performance. The specialized column converter308shown inFIG. 3illustrates such a case. For example, based on true speculative assumptions as discussed above, the generic conversion node, as discussed with respect to the specialized column converter306, is replaced by a specialized conversion node for positive integers during runtime.

However, when a value is accessed that violates the speculative assumptions embedded in the decoder (e.g. a value is accessed that is not a positive integer), the new specialized decoder is invalidated and a new decoder is generated and utilized that is not based on the invalidated speculative assumptions. For the generated decoder, the conversion node gets replaced again by another specialized, but less aggressive, conversion node or is reverted back to the generic conversion node, such as illustrated in the specialized column converter306.

The de-optimization capability of a speculative JIT-compiler (such as the Graal JIT-compiler from Oracle) can be utilized to generate aggressively specialized code. For example, a decoder may be generated based on assumptions that might not hold true for each row of a column (e.g., “all numeric values of a column are positive”). As soon as such an assumption becomes invalid, a speculative JIT-compiler provides the capability to invalidate and replace the aggressively specialized code with code that is not based on the invalid assumptions.

For example, following invalidation of a first version of decoding machine code, a second version of decoding machine code is generated that guarantees that the assumption that was violated is removed to avoid invalidation because of the assumption. For example, if a first version of decoding machine code was generated to decode positive number values between 0 and 99, a value of 111 would invalidate the assumption that all number values being decoded are between 0 and 99. The second version of decoding machine code would be modified to decode positive value between 0 and 999, so that if the database sends a value of 111, the assumption for the second version of decoding machine code will not be invalidated.

The new generated code may also be totally generic, i.e., to cover the whole range of number (e.g., if too many different values need to be handled for example).

In step210, a decoder is compiled based on the code snippets generated in steps204-208. The code snippets generated by steps204-208are compiled into machine code. The decoder may be compiled by a JIT compiler during runtime.

Thus, by exploiting metadata received from a database, decoders can be generated and utilized during runtime that can be used to decode an entire dataset, because the underlying assumptions (e.g., a column has the data type NUMBER and no NULL values) cannot change.

Example Process

FIG. 4shows an example process flow400for efficient data decoding using runtime specialization. Flow400is one example of a flow for efficient data decoding using runtime specialization. Other flows may comprise fewer or additional elements, in varying arrangements.

In an embodiment, flow400is performed by a virtual machine that is part of a runtime environment as discussed inFIG. 1. In an embodiment, a body of code of a dynamically typed language is executed, wherein executing said body of code includes the following steps of flow400:

In step402, a relational database is queried. The query may include a table access.

In step404, in response to querying the relational database, table metadata is received. The table metadata includes information indicating data types of one or more columns of a table in the relational database. In an embodiment, the table metadata includes information such as: a flag to indicate whether there can be NULL values in a column, the value range of numeric columns, the character set of a textual column, and the statically known size of specific database types.

In step406, in response to receiving the table metadata, for a first column of the one or more columns, decoding machine code is generated to decode the first column based on the data type of the first column. As discussed above with respect toFIG. 2, decoding machine code is generated at runtime based on the received table metadata.

In step408, in response to receiving the table metadata, the decoding machine code is executed to decode the first column of the one or more columns. In an embodiment, the decoding machine code is in-lined into a program that triggers the decoding operation. For example, the dynamically typed language, e.g., JavaScript, in-lines all calls to data decoding such that the decoder generation occurs on the first access of a value of a column and does not require any overhead on subsequent accesses of values of the column. Additionally, as discussed above with respect toFIG. 2, decoding machine code is executed at runtime.

Thus, for each specific configuration of data type and constraints specified by the table metadata, a decoder is generated on demand, installed for the column that has triggered its creation, and cached in memory for future decoding operations of other columns with the same configuration. Whenever a user reads a value of a column for which a decoder has already been generated, the installed decoder is directly invoked without using any kind of dispatching mechanism.

In an embodiment, the generated decoding machine code may be shared across equal columns (i.e., columns that have the same data type and constraints) of the same or a different result set. For example, decoding machine code generated for a specific column can be used to decode a column that has the same datatype as the specific column. Additionally, decoding machine code generated for a specific column can be used to decode a column from a different table of the same or different relational database that has the same datatype as the specific column.

Using techniques discussed by flow400, the overall efficiency of decoding operations for dynamic programming languages may benefit. Whenever a user reads a value of a column for which a decoder has already been generated, the generated decoder is directly invoked instead of performing a computationally expensive function lookup. Without generating decoders for each column, the metadata for each row and each column must be processed in order to decide how to decode the data in dynamically typed programming languages. Thus, techniques discussed by flow400improve processing overhead by reducing computation time, memory usage, and bandwidth required to perform decoding operations.

Software Overview

FIG. 5is a block diagram of a basic software system500that may be employed for controlling the operation of computing system600ofFIG. 6. Software system500and its components, including their connections, relationships, and functions, is meant to be exemplary only, and not meant to limit implementations of the example embodiment(s). Other software systems suitable for implementing the example embodiment(s) may have different components, including components with different connections, relationships, and functions.

Software system500is provided for directing the operation of computing system600. Software system500, which may be stored in system memory (RAM)606and on fixed storage (e.g., hard disk or flash memory)610, includes a kernel or operating system (OS)510.

The OS510manages low-level aspects of computer operation, including managing execution of processes, memory allocation, file input and output (I/O), and device I/O. One or more application programs, represented as502A,502B,502C . . .502N, may be “loaded” (e.g., transferred from fixed storage610into memory606) for execution by the system500. The applications or other software intended for use on computer system600may also be stored as a set of downloadable computer-executable instructions, for example, for downloading and installation from an Internet location (e.g., a Web server, an app store, or other online service).

Software system500includes a graphical user interface (GUI)515, for receiving user commands and data in a graphical (e.g., “point-and-click” or “touch gesture”) fashion. These inputs, in turn, may be acted upon by the system500in accordance with instructions from operating system510and/or application(s)502. The GUI515also serves to display the results of operation from the OS510and application(s)502, whereupon the user may supply additional inputs or terminate the session (e.g., log off).

OS510can execute directly on the bare hardware520(e.g., processor(s)604) of computer system600. Alternatively, a hypervisor or virtual computer monitor (VCM)530may be interposed between the bare hardware520and the OS510. In this configuration, VCM530acts as a software “cushion” or virtualization layer between the OS510and the bare hardware520of the computer system600.

VCM530instantiates and runs one or more virtual machine instances (“guest machines”). Each guest machine comprises a “guest” operating system, such as OS510, and one or more applications, such as application(s)502, designed to execute on the guest operating system. The VCM530presents the guest operating systems with a virtual operating platform and manages the execution of the guest operating systems.

In some instances, the VCM530may allow a guest operating system to run as if it is running on the bare hardware520of computer system600directly. In these instances, the same version of the guest operating system configured to execute on the bare hardware520directly may also execute on VCM530without modification or reconfiguration. In other words, VCM530may provide full hardware and CPU virtualization to a guest operating system in some instances.

In other instances, a guest operating system may be specially designed or configured to execute on VCM530for efficiency. In these instances, the guest operating system is “aware” that it executes on a virtual machine monitor. In other words, VCM530may provide para-virtualization to a guest operating system in some instances.

Multiple threads may run within a process. Each thread also comprises an allotment of hardware processing time but share access to the memory allotted to the process. The memory is used to store content of processors between the allotments when the thread is not running. The term thread may also be used to refer to a computer system process in multiple threads are not running.

Cloud Computing

Hardware Overview

Computer system600further includes a read only memory (ROM)608or other static storage device coupled to bus602for storing static information and instructions for processor604. A storage device610, such as a magnetic disk or optical disk, is provided and coupled to bus602for storing information and instructions.