DynQ: a dynamic query engine with query-reuse capabilities embedded in a polyglot runtime

LINQ was first introduced in Microsoft .NET 3.5 to extend the C\(^\sharp \) language with an SQL-like query comprehension syntax and a set of query operators [6]. The following is an example of a LINQ query:

LINQ implements a lazy evaluation strategy by converting query operators to iterators, a so-called pull-based model [58], i.e., each operator pulls the next row from its source operator. In the example query, the where and select clauses in the query comprehension are de-sugared into calls to the methods Where and Select defined in the IEnumerable interface.

Another important feature of LINQ is its extensibility to new data formats. LINQ can execute queries not only on in-memory object collections, but also on any data type that extends the generic types IEnumerable or IQueryable; indeed, from a theoretical point of view, LINQ queries can be executed on any data type that exhibits the properties of a monad [20]. This great flexibility is obtained through so-called LINQ providers, i.e., data-source specific implementations of the mentioned generic types. Relevant examples of LINQ providers are LINQ-to-XML (that queries XML documents) and LINQ-to-SQL, which converts query expressions into SQL queries and sends them to an external DBMS. Despite the benefits it provides, LINQ was explicitly designed targeting statically typed languages, and it is currently not available in dynamic languages. Our work overcomes this limitation.

The C\(^\sharp \) implementation of LINQ executes queries by leveraging the pull-based model, which shares many similarities with the Volcano [17] query execution model in use by many popular relational databases, such as PostgreSQL [5]. It has been shown [32] that the main performance drawbacks of this execution model are virtual calls to the interface methods (e.g., MoveNext() and Current() in C\(^\sharp \), or hasNext() and next() in Java), which introduce non-negligible overhead, since they are executed for each input row of each operator in the query plan. In the context of relational databases, the most relevant optimizations for removing such overhead are vectorization [7] and data-centric query compilation [44].

Vectorized query execution, similarly to the Volcano model, uses a pull-based approach. However, the query interpretation overhead is mitigated by leveraging a columnar data representation and batched execution, i.e., instead of evaluating a single data item at a time, query operators work on a vector of items which represents multiple input rows. Data-centric query execution completely removes the interpretation overhead by generating executable code for a given query. Code generation commonly happens at runtime, using schema and type information to generate code that is specialized for the tables used in a query. Data-centric query compilation adopts a so-called push-based model, i.e., each operator pushes a row to its destination operators. Both pull-based and push-based models have been studied from the point of view of compilers and program transformations [29, 41, 42]. Interestingly, it has been shown [58] that, by leveraging compiler optimization techniques such as loop fusion, method inlining, and scalar replacement, neither model clearly outperforms the other.

A well-known disadvantage of query compilation is the overhead introduced by the compilation itself. For statically typed and compiled languages, query compilation can take place at different times, namely at application compilation time (e.g., in SBQL4J [68]) or during its execution (e.g., in Steno [41]). While the former approach has the advantage of hiding the query compilation cost during the compilation of the application, it imposes serious limitations: the queries must be expressed in the application code, meaning that a system that accepts queries as user input cannot leverage such an approach. In the context of dynamic languages (such as JavaScript or Python), this approach cannot be used in general, because the application source code is directly executed by the runtime. On the other hand, runtime query compilation does not suffer from these limitations, but the compilation cost can shadow the benefits obtained by the optimization passes, in particular for short-running queries. Recent research [30] addresses this issue with an adaptive query compilation model. With such a compilation model, the engine first quickly generates an executable representation of the query and executes it in an interpreter. Then, during query execution, the engine performs adaptive decisions whether to compile a query operator based on execution-time estimations. This approach is inspired by the implementation of JIT compilers in language VMs and shares similarities with the query execution model adopted by DynQ. Unlike existing SQL-query compilation approaches, DynQ needs to generate machine code that is specialized to access objects located in the memory space of a running language VM. This scenario presents unique challenges that are not found in existing SQL execution runtimes, as we will discuss in the rest of this article.

DynQ is implemented targeting the GraalVM [72] platform, i.e., a polyglot language runtime compatible with the Java Virtual Machine (JVM). GraalVM is capable of executing programs developed in a variety of popular programming languages, such as Java, JavaScript, Ruby, Python, and R. At its core, GraalVM relies on a state-of-the-art dynamic compiler (called Graal [71]), which brings JIT compilation to all GraalVM languages. Language runtimes for GraalVM (including DynQ) are implemented using the Truffle [70] language implementation framework. Unlike other code-generation frameworks for the JVM or the .NET platform, Truffle does not rely on bytecode generation, but rather on the concept of self-optimizing interpreters [70], i.e., language interpreters that use custom API and data structures enabling explicit and direct interaction with the underlying language VM components (including the JIT compiler). The Graal optimizing compiler has special knowledge of such API, and is capable of generating efficient machine code by means of partial evaluation [25].

In addition to JIT compilation, the Truffle framework provides mechanisms to interact with any of the dynamic languages supported by GraalVM. Thanks to these interoperability mechanisms, DynQ can effectively inline machine code used by GraalVM language runtimes into its own query execution code. For example, DynQ can use the very same machine code used by the GraalVM JavaScript VM to read JavaScript heap-allocated objects, thereby enabling efficient access to in-memory data during SQL query execution. This approach to SQL execution allows DynQ to efficiently exploit runtime information, to benefit from optimizations that are normally used in high-performance language VMs, such as dynamic loop unrolling and polymorphic inline caching [22].

At its core, DynQ is a dynamic query engine for GraalVM that exploits advanced dynamic compilation techniques to optimize query execution. DynQ is exposed to users by means of a language-agnostic API, and is capable of executing queries on any object representation supported by GraalVM languages. Unlike the popular LINQ implementation for the .NET platform, DynQ does not extend its supported programming languages with a query-comprehension syntax, but rather relies on SQL queries expressed as plain strings. The LINQ query-comprehension syntax allows query validation at program compilation time. However, as already discussed in the literature [24], in a dynamically typed language, where syntactic validation and type checking take place at runtime, lacking this form of compile-time validation is not an issue. Moreover, since one of the main goals of DynQ is language independence, extending the syntax of multiple languages would not be a practical approach.

Two important differences between DynQ and existing LINQ systems are its dynamic type system and the tight integration with the underlying GraalVM platform. The flexibility of dynamic languages imposes additional performance challenges compared with query engines that process data with a known type, as the engine has to take into account that a value may be missing in an object and that runtime types of the objects in a single collection (e.g., an array) can be different from each other. JIT compilation is crucial in this context, as it allows DynQ to generate machine code that is specialized for the data types observed at runtime. For example, DynQ can emit offset-based machine code when accessing R data frames, or hash-lookup-based access code when reading data from JavaScript (map-like) dynamic objects. Close interaction with the platform’s JIT compiler is a peculiar feature of DynQ and a key architectural difference w.r.t. other popular language-integrated approaches. Existing systems (e.g., .NET LINQ or Java 8 Streams) do not interact with the underlying language runtime; in these systems, queries are compiled to an intermediate representation (e.g., .NET CLR or Java bytecode) like any other language construct (e.g., Java 8 Streams are converted to plain Java bytecode with virtual method calls and loops). Query compilation to such intermediate representations happens statically, before program execution. At runtime, the language VM might (or might not) generate machine code for a specific query. However, the lack of domain knowledge of the underlying JIT compiler could limit the class and scope of optimizations that the language VM can perform. For example, a language VM might (or might not) decide to inline certain methods into hot method bodies depending on runtime heuristics that have nothing to do with the structure of the actual query being executed.

DynQ, on the contrary, takes a radically different approach as it explicitly interacts with the underlying VM’s JIT compiler to drive query compilation. In this way, DynQ can effectively propagate its runtime knowledge of any given query to machine code generation, resulting in high performance. As an example, DynQ can effectively force the inlining of the predicates of a given query expression into table-scan operators, ensuring efficient data access. Moreover, the tight integration with the language VM’s JIT compiler unlocks a class of optimization that are not achievable with existing LINQ-like systems, namely, dynamic speculative optimizations: not only can DynQ apply an optimization (e.g., inlining) when it sees potential performance gains, but it can also de-optimize the generated machine code when certain runtime assumptions get invalidated, giving the query execution engine the chance to re-profile the code that is being executed, possibly leading to the generation of new machine code that now takes different runtime assumptions into account.

Thanks to its design, DynQ is able to outperform hand-optimized implementations of queries written in dynamic languages. Internally, the type system of DynQ’s query engine handles two main types, namely primitive types and structured types. Primitive types include all Java primitive types as well as String and Date. Structured types include arrays and nested data structures, i.e., objects with properties of any of the mentioned types; multiple nesting levels are supported as well. As expressions, DynQ supports logical and arithmetic operators, the SQL LIKE function on strings, and the EXTRACT function on dates. Moreover, DynQ seamlessly supports user-defined functions (UDFs), as it can directly inline code from any GraalVM language into its SQL execution code. In this way, UDFs from any of the GraalVM languages can be called during SQL evaluation with minimal runtime overhead. In particular, it is not required that a UDF is written in the same language as the application that is using DynQ, e.g., it is possible to use DynQ from JavaScript, executing a query with a UDF written in R.

As GraalVM is compatible with Java, DynQ can leverage existing Java-based components to perform SQL query parsing and initial query planning. To this end, our implementation leverages the state-of-the-art SQL query parser and planner Apache Calcite [4]. While using Calcite as an SQL front end has the notable advantage that DynQ’s implementation can focus on runtime query optimization after query planning, DynQ’s design is not bound to Calcite’s API, and other SQL parsers and planners could be used as well.

A high-level overview of the life cycle of a query executed with DynQ from a dynamic language (JavaScript in the example) is depicted in Fig. 1. As the figure shows, as soon as a developer has defined a dataset in the form of an object collection (e.g., an array) it is possible to execute an SQL query on the in-memory data. DynQ is invoked from the host dynamic language, passing (as parameters) a string representation of the query and a reference to the input data. DynQ leverages Calcite for parsing and validating the SQL query; if successful, the validated query is converted into an optimized query plan. Then, DynQ traverses the query plan, generating an equivalent executable representation (i.e., Truffle nodes [70]), which is our form of a physical plan. By generating Truffle nodes, the code generation phase of DynQ is very efficient, as Truffle nodes are ready to be executed by GraalVM. Query execution thus begins by executing the Truffle nodes generated by DynQ. As soon as the DynQ runtime detects that the AST (or parts of it) are frequently executed, it delegates the JIT compilation to GraalVM. Dynamic compilation is triggered by DynQ, which also takes possible runtime de-optimizations and re-compilations into account. Finally, the result of query execution, i.e., a language-independent data structure accessible by any GraalVM language, is returned to the application.

Query compilation in DynQ uses a push-based approach and takes place by visiting the query plan generated by Calcite and converting it into Truffle nodes. The push-based query execution approach used by DynQ is inspired by the model introduced in LB2 [63]. In this model, each operator produces a result row that is consumed by an executable callback function. Rather than relying on statically generated callback functions, however, DynQ propagates result rows to Truffle nodes. In this way, those nodes can specialize themselves on the actual data types observed at runtime. Internally, DynQ relies on two classes of Truffle nodes, namely (1) Expressions and (2) Query-operators.

Expression nodes represent the supported SQL expressions and UDF functions introduced in Sect. 3.1. Since DynQ is a schema-less query engine, each expression node used in a query has initial unknown input (and output) type. During query execution, Truffle nodes rewrite themselves to specialized versions capable of handling the actual types observed during query execution. This specialization mechanism is natively supported by the Truffle framework and allows DynQ to handle type polymorphism in a way analogous to language runtimes, resorting to runtime optimization techniques such as polymorphic inline caches [22]. In this way, an expression can be specialized during query execution to handle multiple data types.

Query-operator nodes are responsible for executing SQL operators, eventually producing a concrete result value. DynQ relies on two categories of query-operator nodes, namely consumer nodes and executable nodes. Intuitively, each query operator (excluding table scans) has its own consumer node, while only table-scan and join operators implement an executable node. The main executable node of a query, i.e., the one containing the root operator, takes care of producing the result set for that query.

DynQ generates a query’s root executable node by visiting the plan generated by Calcite. In particular, DynQ generates a consumer node \({C}\) for the currently visited operator \({O}\). If \({O}\) is not a join (i.e., it has only one child), \({C}\) will consume the rows produced by the child of \({O}\). If \({O}\) is a table scan, DynQ generates an executable node which iterates over a data structure (which acts as a table), invoking the generated chain of consumer nodes for each row. The implementation of the consumer nodes generated by visiting a join operator depends on the join type. DynQ supports nested-loop joins and hash-joins (possibly with non-equi conditions). In case of nested-loop joins, DynQ creates a left consumer which inserts all rows into a list \({L}\), and a right consumer that finds matching pairs of rows by iterating over the elements in \({L}\) for each row. In case of hash-joins, the left consumer inserts the rows in a hash-map, which is used by the right consumer to find matching pairs. The corresponding Java interfaces ExpressionNode, ConsumerNode, and ExecutableNode are shown in Fig. 2. When the query root operator is not a materializer (e.g., for queries composed of projections and predicates), DynQ adds a custom consumer which fills a list of rows, since DynQ always outputs an array data structure. On the other hand, when the root operator is a sort or an aggregation, DynQ returns the sorted (or aggregated) data, which is already a list of rows.

Note that stateful operators do not need any specific executable node, since they are implemented using the ConsumerNode methods consume(row) and getResult(). As an example, if a query has a group-by operator (which is not the root operator in the query plan), its implementation of consume(row) updates the internal state (a hash-map) and the implementation of getResult(), which is invoked by its source operator once all input tuples have been consumed, sends all tuples from the aggregated hash-map to its destination (a ConsumerNode), calling the consume(row) method for each aggregated row, and finally returns the value obtained by calling the getResult() method on its destination consumer. Since push engines do not allow terminating the source iteration, i.e., an operator cannot control when data should not be produced anymore by its source operator, DynQ implements early exits for the limit query operator by throwing a special EndOfExecution exception.

Query compilation example. Consider the DynQ query targeting a JavaScript array of objects shown in Fig. 3. The query execution plan for the example query is composed of a table-scan operator, a predicate operator, and an aggregation operator that counts the number of rows that satisfy the predicate. The AST of Truffle nodes generated by DynQ for the example query is depicted in Fig. 4. A simplified implementation of the nodes that compose the query is depicted in Fig. 5. As shown in Fig. 5, the LessThanNode node leverages Truffle specializations for implementing the less-than operation. The LessThanNode implementation shown in Fig. 5 presents only the specializations for Int and Date types, because those types are the ones used in the example. The actual implementation contains specializations for all types supported in DynQ as well as their possible combinations (e.g., Int/Double and Double/Int). In particular, DynQ specializations with mixed types respect the implicit type conversion (i.e., type cast) semantics commonly integrated in a query planner, but in DynQ the detection of such casts must take place during data processing (instead of during query planning), since at query planning time types are not known in DynQ. Consider the method execute(Object row) defined in the class LessThanNode. This method first executes the left and right children expression nodes (i.e., property reads in the example query). Then, the method call to executeSpecialized (internally) performs a type check for the two arguments (i.e., fst and snd). If both values have type int, the specialization execute(int, int) is executed; if they are both dates, the method execute(LocalDate, LocalDate) is executed; otherwise, the current tuple is discarded. Note that, although our current implementation is permissive, i.e., it does not stop the query execution throwing an exception in case a malformed row is encountered, implementing different error handling strategies would be trivial.

Consider again the AST generated by DynQ for the example query depicted in Fig. 4. If the query is executed on an R data frame, DynQ would generate the same tree, but the TableScan executable node and the ReadMember expression nodes would specialize in different ways, depending on the runtime types. The flexible design of DynQ allows reusing the very same query-operator nodes for executing queries on different data structures, like a JavaScript array of objects or an R data frame. Thanks to this design, we achieve all the three goals listed in the beginning of this section. In particular, the extensibility and modularity of our design allow adding new data sources (e.g., a data structure in a dynamic language or an external source like a JSON file) by integrating only the expression nodes which take care of accessing data from such a data source, without requiring any modification to the query-operator nodes.

Dynamic machine code generation. By implementing DynQ on top of Truffle, DynQ has fine-grained control over Graal, the GraalVM’s JIT compiler. Dynamic compilation is triggered based on the runtime profiling information collected during query execution, and the Graal JIT compiler applies (to DynQ queries) all optimizations that are commonly used in dynamic language runtimes. Examples of optimizations applied by Graal include aggressive inlining, loop unrolling, and partial escape analysis. JIT compilation is performed by GraalVM using a configurable number of parallel compiler threads. This leads to short compilation times, as we will further discuss in Sect. 5.2.

In contrast to many engines based on query compilation, DynQ does not need to generate machine code before executing a query. Query execution in DynQ begins as soon as the Truffle nodes have been instantiated. First, the execution starts by interpreting those nodes; during this phase the runtime collects type information for the nodes that leverage Truffle specializations (e.g., LessThanNode in the previous example). Then, once the runtime detects that some nodes are frequently executed (e.g., the main loop in TableScanNode), it initiates machine-code generation. Once the runtime has collected type information for those rows which have been executed in the interpreter, it speculatively generates machine code assuming that the subsequent rows will have the same types. If such speculative assumptions get invalidated (e.g., because a subsequent row has an unexpected type), the compiled code gets invalidated and the execution falls back to interpreted mode. Then, the runtime can update the collected type information and later re-compile the nodes to machine code accordingly. It is important to note that, even if triggering recompilation has a cost, specializations stabilize quickly [71], typically incurring only minor overhead. By leveraging a state-of-the-art dynamic compiler like Graal, DynQ can selectively compile single components of the query’s physical plan. In particular, each table-scan executable node can be selectively compiled to self-contained machine code. Thanks to this approach, a query does not need to be fully compiled to machine code to achieve high performance, since, e.g., executing a join operator could lead to the evaluation of one child node in the interpreter (if it has few elements) and another child in compiled machine code.

Figure 6 shows the pseudo-code equivalent to the machine code generated by DynQ for the example query of Fig. 3, once both types in the example are encountered (i.e., both x and y properties have either type Int or Date). As the figure shows, all the calls to the interface methods are aggressively inlined by the compiler. The operations listed at the beginning of the while loop that interact with the host dynamic language (i.e., reading the current array element and its properties x and y) are inlined by the compiler as well. Moreover, the predicate node is compiled into two if statements that check whether in the current row the fields x and y have one of the expected types. If this is not the case, in general, the generated code would be invalidated as described above, while in this specific example, since there is no other specialization in the less-than node, the current row is discarded and the generated code does not need to be invalidated.

As introduced in Sect. 2.1, LINQ queries are not limited to object collections, instead they can be executed on any data format for which a so-called LINQ provider (i.e., a data-source specific implementation of the enumerable and queryable interfaces) is available. Such flexibility is an appealing feature for developers, since it allows executing federated queries within the same programming model, leaving the complexity of orchestrating different data sources to the system. In the context of DBMS, orchestration of federated queries is a widely studied topic, pioneered by systems like Garlic [26] and TSIMMIS [10]. As an example of custom providers in DynQ, consider a scenario where a developer needs to analyze a web-server log file in JSON format, counting the number of accesses for each user who registered to the website after a specific date, with user registration data however stored in a database. Figure 7 shows how such a log analysis can be executed with DynQ. As the figure shows, developers do not have to deal with opening/closing any file or database connection; they only need to provide a file name and configurations for accessing the database (e.g., the URL, credentials, and database name) to DynQ, which takes care of everything else. Moreover, the Calcite query planner detects the operators that can be pushed to external data sources. When executing the example query, DynQ sends (to the database) the SQL query with the predicate on the date field and retrieves only user names of the rows matching the predicate. Hence, the operation can be executed more efficiently (i.e., exploiting database optimizations) and communication overhead is reduced.

Implementing a DynQ provider requires defining a specific table-scan operator, which takes care of iterating over the rows in the input data source, and a data-accessor operator, which takes care of accessing the fields of each row. Our JSON provider builds on Jackson [16], an efficient JSON parser for Java, for accessing fields in JSON objects. This approach can be further extended with more complex parsers that integrate predicate execution during data-scan operations, which is an approach already explored in the literature [33, 56].

Besides the query parser and planner, Apache Calcite has another appealing feature for DynQ, namely its flexibility in integrating new data sources by defining specific adapters. A Calcite adapter takes care of representing a data source as tables within a schema, i.e., a representation that can be processed by the query planner. Similarly to LINQ providers, from a query execution point of view, a Calcite adapter takes care of converting the data from a specific source to a Calcite enumerable that can be integrated into the query engine, allowing the execution of federated queries.

Although GraalVM allows efficient interactions among different languages [18], it may introduce overhead related to data conversion operations. As an example, dates are represented as LocalDate instances once shared among different languages, but the internal representation in a specific language may be different, e.g., in JavaScript dates are represented as long values, as the number of milliseconds from the epoch day January 1, 1970-01-01, UTC [13]. As an example, consider the following simple query:

Suppose DynQ executes such a query (without language-specific type conversions) on JavaScript objects, in a first step (before query execution) it would create a LocalDate instance for the constant date (2000-01-01), then during predicate evaluation, for each row:On the other hand, evaluating the predicate in JavaScript would require only the first step above (i.e., checking that the field exists and has type date), if so the date comparison is executed using the JavaScript internal representation of dates, that is, a single comparison of two primitive longs, which is of course much more efficient than the steps above.

The reason for those data conversions is that different languages may internally represent the same data type differently, but exposing those types to other languages requires a common representation. To overcome these inefficiencies related to the type conversions introduced by language interoperability, DynQ provides an extension mechanism that can be used to implement language-specific type conversions. As discussed in Sect. 3.2, DynQ relies on two main categories of nodes, namely expression nodes and query operator nodes. Language-specific type conversions can be implemented by extending expression nodes with new specializations for types of a certain language.

Considering for example JavaScript dates, language-specific type conversions can be implemented to extend comparison nodes by taking care of checking if the objects to be compared are actually JavaScript dates. If so, the comparison can be executed more efficiently by delegating it to the JavaScript engine, an operation that could be inlined by the Graal compiler into DynQ’s query operator nodes. Note that language-specific type conversions do not break the high modularity of DynQ, since only expression nodes are extended with such optimizations, while adding new query operators, data sources, or features of the query engine (e.g., parallel query execution) would impact only query operator nodes. Moreover, language-specific type conversions are an optional extension, i.e., DynQ can execute queries on objects of a language for which no language-specific type conversions are implemented. In this case, depending on the data type of the processed objects, DynQ may have to execute data-conversion operations.

In this section, we focus on data-processing libraries for dynamic languages which allow developers to query heap-allocated objects using a data-frame-like API, i.e., expressing query operators as a chain of method calls. Examples of this syntax are the Spark DataFrame API [2] and LINQ queries when used with the de-sugared method-call syntax [35]. The following is an example of a pipeline built with method chaining, which is a de-sugared version of the LINQ query written with the comprehension syntax in Sect. 2.1.

Such a chained method-call syntax is used by many existing data-processing libraries. Using this syntax, developers invoke an operator on enumerable objects (also called pipeline builders), passing as parameters the expressions to be evaluated by the operator. The invocation results in a new enumerable object on which another operator can be invoked, forming a chain of method calls. The method chain will result in a materialized result once the developer makes use of a terminal operator, e.g., on the de-sugared LINQ query in the example, evenSquares.ToArray() is called to materialize the query result into an array. From now on, we will refer to this syntax as fluent APIs. As an example of fluent APIs usage with DynQ, Fig. 8 shows how the de-sugared LINQ query in the example above can be executed with DynQ.

Note that, in contrast to SQL queries, using a fluent API developers can fragment the definition of a single query. As an example, using a fluent API one can define a function which returns an enumerable object, e.g., the representation of a table scan followed by a predicate, and then call such a function in two different contexts, appending a different terminal operator in each context. This feature greatly improve modularity; indeed, it is often offered by Object-Relational Mapping (ORM) systems [65].

Existing data-processing systems which offer fluent APIs and that are based on query compilation are implemented similarly to SQL query compilers. In particular, those systems lazily keep track of the operators composing a pipeline as well as their parameters (e.g., UDFs). Once a terminal operator is called, the sequence of operators are considered as a single, standalone query, which is then compiled as a single unit. From now on, we will refer to this approach which triggers compilation for each query execution per-query compilation.

Per-query compilation has the well-known advantage of generating code which is specialized as much as possible for a given query, which means that the generated code is, in principle, the best possible implementation of that query. DynQ offers developers the fluent APIs leveraging the described per-query compilation approach. However, as further analyzed in the next section and shown in our evaluation, while the per-query compilation approach performs very well on analytical workloads, it is suboptimal for high-throughput workloads which perform many queries on small batches of data. In the next section we will present an extension of DynQ to efficiently deal with high-throughput workloads, too.

Figure 9 shows an example of a prepared statement with DynQ. The prepared statement in the example is very similar to the example query in Fig. 3, with the only difference that the expression x< y in Fig. 3 is now x< ?. Figure 10 shows the AST generated from the prepared statement in Fig. 9. As expected, the AST is very similar to the one shown in Fig. 4, the only difference is the node PlaceHolder$0, i.e., the placeholder for the prepared statement variable, which replaces the node ReadMember(y). Note that also the compiled code for the AST depicted in Fig. 10 is very similar to the one shown in Fig. 6, with the only difference that the generated function now takes a parameter to be compared with the property x of each row.

As we will show in Sect. 5.3, using prepared statements, DynQ shows performance in line with an equivalent handwritten function which takes the variables of the prepared statement as arguments.

In the implementation of DynQ, we generalize the notion of prepared statement in the context of a fluent API. To this end, we introduced a special marker in our fluent API: DynQ.par, as well as a special operator: prepare. The parameter marker DynQ.par acts as the question mark symbol in prepared statement. However, in contrast to prepared statements, parameters are not limited to placeholder replacements for raw values, since placeholder nodes in the fluent API can represent any UDF. When a UDF is provided as argument to an operator appended into a pipeline-builder, e.g., .map(x => x*x), as with per-query compilation DynQ forces the inlining of the UDF into the query code, de-virtualizing the call to such UDF. On the other hand, when the marker DynQ.par is used to indicate that a parameter will be provided at query execution time, DynQ introduces a virtual call into the generated code pointing to the placeholder location, where DynQ will place the reference to the UDF provided at query execution. Consider again the DynQ fluent API example in Fig. 8, which selects the squares of the even numbers in a given array. Figure 11 shows an example of parametricity defining a similar query which is parametric for the predicate expression. Such a parametric fluent API can be later invoked by passing (as parameter) an arbitrary UDF as predicate expression. Indeed, as the figure shows, the same compiled query can be used to evaluate the squares of even numbers as well as the squares of the numbers which pass any given predicate, e.g., the odd numbers.

As we will show in Sect. 5.3.3, both prepared statements and parametric fluent API are efficient solutions for query reuse, since the query compilation happens only once and its overhead is mitigated by multiple executions of the same compiled code with different parameters. However, unfortunately, even if parametric fluent API offer a great performance benefit, its usage has many limitations in comparison with a traditional (i.e., nonparametric) fluent API. This is motivated by the fact that both prepared queries and parametric fluent API offer parametricity in an explicit manner. First, all queries must be expressed in the application code, meaning that a system that accepts queries as user input cannot leverage such an approach. Moreover, reusing queries requires developers to carefully refactor each code location in the application which makes use of a fluent API. As an example, in order to leverage the benefit of parametric fluent API, a developer needs to be aware of all the possible code locations within an application which are suitable for being expressed with parametric fluent API, which may not be the case for large applications. Moreover, the process of switching from a common data-processing library with a fluent API to a parametric fluent API version as offered by DynQ may require rewriting a large part of the application. Finally, parametric fluent API cannot be used for cross-library optimizations. In particular, suppose an application makes use of multiple libraries that internally use the same pipeline. To execute that pipeline on the same compiled code, a developer should create a separate module with the definition of the pipeline and refactor those libraries’ code such that they all make use of the introduced pipeline in the shared module. In the next sections, we will describe a novel approach for implementing a fluent API which does not require developers to make explicit use of parametricity, without suffering from the query compilation overhead for each single query execution as done using the tradition per-query compilation approach.

The subsets of calls that are ensured to be de-virtualized with reusable compiled queries are all the calls to DynQ’s Truffle nodes of type ConsumerNode, i.e., consume(row) and getResult(). We avoid forcing inlining of calls to nodes of type Expression, leaving the inlining decisions of expression nodes to the underlying JIT compiler (i.e., Graal), as done with all methods during the execution of an application on a VM with hot-code compilation. Consider again the even-squares example query in Fig. 8, the sequence of operators which composes such a query starts with a source table scan operator, followed by a predicate, a projection, and finally a sink toArray operator which materializes the rows into an array. The representation of this query partially specialized by de-virtualizing the calls to nodes of type ConsumerNode is equivalent to the following parametric fluent API.

Let’s now consider a similar query to the one in the example, i.e., a query which returns the cubes (instead of squares) of the odd numbers (instead of even) in a given array. Since the sequence of operators which composes this query is exactly the same as the even-square query in the example, the partially specialized function shown above can be used for executing both queries, even if their predicate and projection expressions are different. In particular, the odd-cubes pipeline can be executed on the existing compiled code for the function partiallySpecialized, passing as parameters xs, x => x % 2 == 1 and x => x * x * x.

Reusable compiled queries are an optional feature of our fluent API, which developers can enable globally as well as for a single query. We implemented the caching strategy behind reusable compiled queries within the pipeline builders, leveraging the parametric fluent API described in Sect. 4.1. In particular, the reusable compiled queries are stored with a tree shape in a memory location which is shared among the whole application. The pipeline tree is composed of two kinds of nodes, intermediate nodes and leaves nodes. Each leaf contains a prepared query generated with a parametric fluent API, while each intermediate node represents a query operator. Thus, a path from the root to a leaf represents a sequence of operators, i.e., a pipeline, and such a leaf contains a reference to the compiled representation of that pipeline, i.e., a DynQ executable node. Since there must be a single root in a tree and there can be multiple scan implementation, the root of pipelines tree is an empty operator; all scan operators are children of the empty root.

Reusable compiled queries are transparently created by DynQ through the pipeline builder instances created when developers make use of a fluent syntax. Figure 12 shows the internal (simplified) Java implementation of the pipeline builders. As the figure shows, each pipeline-builder object contains two fields, a reference to a (shared) node in the pipeline tree, and an array of actual parameters. Each node in the pipeline tree contains three fields, a reference to a (partially) prepared query using a parametric fluent API, a map which stores the children nodes by operator, and a reference to an executable node generated by the (fully) prepared query, which is non-null only for leaf nodes. Note that the empty root of the pipeline tree is created with an empty map and a reference to a prepared query with parametric fluent API without any operator, i.e., root.query = DynQ.prepare().

When a developer makes use of a fluent API with reusable compiled queries, DynQ internally creates a new pipeline builder composed of an empty array as actual parameters and a reference to the (shared) root of the pipeline tree. Then, every time an operator Op with parameters \((p_1,..., p_n)\) is appended on a pipeline builder \(P_0\) through method call, the method \(P_0.appendOperator\) is called, and a new pipeline-builder instance \(P_1\) is created (line 44 in Fig. 12). The actual parameters of \(P_1\) are defined as \(P_0.actualParameters\) \(++\) \([p_1,..., p_n]\), where \(++\) denotes the array concatenation (line 45 in Fig. 12). The reference to a the pipelines-tree node in \(P_1\) (i.e., \(P_1.sharedNode\)) will be evaluated as follows. If the node \(P_0.sharedNode\) has already a child node for the operator Op (say \(node'\)), then we define \(P_1.sharedNode = node'\) (line 18 in Fig. 12). Otherwise, a new (shared) node \(node''\) is created for the operator O as a child of \(P_0.sharedNode\) in the pipeline tree, and \(P_1.sharedNode\) will be assigned to \(node''\) (lines 20-32 in Fig. 12). Finally, if the operator Op is a terminal operator, then \(P_1.sharedNode\) is a leaf in the pipeline tree. If such a leaf was freshly created, DynQ creates the ExecutableNode through the parametric fluent API instance in the tree node and cache it in the tree node itself. Otherwise DynQ reuses the already generated (i.e., cached) ExecutableNode. Note that the generated AST does not contain any expression node but parameters, since all actual parameters provided by the developer are internally stored in the pipeline-builder instances and replaced with DynQ.par within the generated executable node, making that node reusable for any other query composed of the same sequence of operator. Once the ExecutableNode has been retrieved (either cached or freshly created) it is automatically invoked by passing as parameters the array \(P_1.actualParameters\) (line 54 in Fig. 12). It is important to note that reusable compiled queries do not prevent additional speculative compiler optimizations, e.g., the compiler could decide to speculatively inline a UDF in a query as in hot-code compilation.

Thanks to the normal (i.e., nonparametric) fluent syntax offered by reusable compiled queries, a developer can switch from using a typical data-processing library implemented in a dynamic language to DynQ with minimal effort. In particular, there is no need to take care of rewriting the pipelines with explicit parametricity leveraging the parametric fluent API. Moreover, as we will show in Sect. 5.3.3, thanks to reusable compiled queries, DynQ outperforms Lodash [36], a popular data-processing library for JavaScript, making DynQ an attractive drop-in replacement for existing data-processing libraries.

On R, we evaluate DynQ against the data.table API, DuckDB [53], and MonetDB [23]. In this setting, we import the TPC-H tables into R data frames. Since TPC-H is based on a strict (relational) schema, and the data is imported into R data frames, which is a typed data structure, the evaluation on R does not highlight the DynQ peculiarity of efficiently accessing data with unknown schema. Indeed, for all the experiments in this setting, DynQ uses the schema information from the data frames. However, DynQ currently uses the schema only for the data-access operations, all the query operators nodes as well as the other expression nodes share the same implementations as in the case of unknown schema, as described in Sect. 3.4. The main goal of this evaluation is to show that on relational database workloads the flexibility of DynQ in accessing data formats which are not directly managed by the query engine does not impair performance, in contrast to other data-processing systems.

On JavaScript, we evaluate DynQ in very different settings. First, we evaluate DynQ against AfterBurner [14] using AfterBurner’s memory layout, i.e., a columnar layout composed of typed JavaScript arrays. In this setting we use TPC-H and the microbenchmark queries as workloads. Since AfterBurner is a relational database, also this setting uses a strict schema, and similarly to the evaluation on R the goal of this evaluation is to show that query execution performance with DynQ on relational data is in line with a query engine which reads data using its own memory layout.

Then, we evaluate DynQ on datasets stored as JavaScript object arrays. For all the experiments in this setting, no schema information is provided to DynQ. Here, we first evaluate DynQ against Lodash [36] and handwritten implementations using the microbenchmarks. Then, we evaluate DynQ on existing code bases (the npm module cities [12]), leveraging prepared statements (Sect. 5.3.2) to implement a web-service backend module to search locations based on user input. Those experiments highlight the ability of DynQ to efficiently process dynamic objects with unknown schema. Finally, we evaluate reusable compiled queries (Sect. 5.3.3) on a JavaScript implementation of two relevant benchmarks that use a fluent API for data processing that we recasted from the Renaissance [50] benchmark suite, which was originally implemented in Java. One of these two latter experiments also show the ability of DynQ to handle efficient query execution on polymorphic types, since the engine needs to deal with mixed types of input arrays.

In this section, we evaluate DynQ with the R programming language. Here, we use the dataset from the TPC-H benchmark generated with the original dbgen tool [66] loaded into an R data frame. Since, like DynQ, DuckDB [53] allows executing SQL queries directly on R data frames, we evaluate DynQ on the TPC-H benchmark queries and the micro-benchmark queries against DuckDB, on a dataset of scale factor 10; the dataset size is 10GB in a text format. In particular, we use DuckDB (version 0.3.0), executed on GnuR [51] (version 3.6.3). Since the measured execution time with DynQ does not take into account query planning time, we slightly modified the DuckDB R plugin so that queries can be planned and executed in two different steps, so that the measured execution time on DuckDB does not take into account query planning as well. DuckDB provides two ways for executing queries on R data frames, i.e., directly on the data-frame data structure, and in a managed table, which is much more efficient but requires an ingestion phase. We refer to the former setting as DuckDB(df), and to the latter one as DuckDB(preload). Note that, by comparing DynQ against DuckDB, the fair comparison is with DuckDB(df), since the data is accessed directly on R data frames, as in DynQ. Moreover, in evaluating DuckDB(preload), we do not measure the time spent in the ingestion phase. In this evaluation, we measure the median of 10 executions.

Due to the different query planners and implementation choices in DynQ and DuckDB (DuckDB is vectorized and interpreted while DynQ is tuple-at-a-time and JIT compiled), the goal of this performance evaluation is not to compare two very different systems, but rather to demonstrate that DynQ achieves performance competitive with an established, state-of-the-art data-processing system. We consider the micro-benchmark queries important in our evaluation, since, due to their simplicity, the query plans are the same in DynQ and in other systems. Moreover, since the micro-benchmark queries are rather simple, they stress data-access operations, showing that the extensibility of DynQ in accessing data in different formats does not impair query execution performance, which we consider a great achievement.

Micro-benchmarks. Due to the simplicity of the queries in the micro-benchmarks listed in Table 2, we manually implement them using the data.table API, which is arguably the most efficient library for processing R data frames. The benchmark results are depicted in Fig. 14. As the figure shows, DynQ is slower than the data.table API only on MQ7 and outperforms it on all other queries by speedup factors ranging from 1.16x (MQ4) to 27.8x (MQ5). The speedup on MQ6 against data.table (i.e., 826x) is because DynQ chains query operators and stops the computation once it finds the first 1000 elements that satisfy the predicate (i.e., the limit operator). On MQ6, DynQ performs comparably with DuckDB, with speedup factors of about 1.18x against DuckDB(df) and 0.63x against DuckDB(preload), with a query execution time of about 1ms, showing the effectiveness of our exception-based approach for implementing early exits for the LIMIT operator. We consider such a low query execution time a great achievement for DynQ, since the existing query engines based on compilation commonly suffer from a latency overhead due to query compilation. DynQ outperforms DuckDB(df) in all other queries as well, with speedup factors ranging from 4.38x (MQ7) to 48.14x (MQ1). Those speedups against DuckDB(df) are motivated by the fact that the micro-benchmark queries are simple and mostly dominated by table scans. DuckDB(df) requires table-scan operations to convert data on-the-fly from data frames into the DuckDB physical data representation, which introduces high overhead. On the other hand, DynQ can execute queries on R data frames in-situ, i.e., without any conversion. Indeed, DynQ performance is closer to DuckDB(preload), which significantly outperforms DuckDB(df), showing that the great flexibility of DynQ in accessing data in different formats does not impair performance. In particular, DynQ is slower than DuckDB(preload) only on queries MQ6 (factor 0.63x) and MQ7 (factor 0.65x), and outperforms DuckDB(preload) on all other queries, with speedup factors ranging from 1.11x (MQ1) to 1.77x (MQ3).

TPC-H Benchmark. Here, we evaluate DynQ using the TPC-H benchmark. Like in our previous experiment, we compare DynQ against DuckDB executing queries directly on the data frame, i.e., DuckDB(df) and with data loaded into a managed memory space, i.e., DuckDB(preload). The benchmark results are depicted in Fig. 13.

As the figure shows, DynQ is slower than DuckDB(df) only on Q13 (factor 0.81x) and Q16 (factor 0.71x), in all other queries DynQ outperforms DuckDB(df), with speedup factors ranging from 1.27x (Q9) to 26.55x (Q15). In comparison with DuckDB(preload), DynQ is faster on 12 queries (i.e., Q1, Q2, Q4, Q6, Q7, Q10, Q12, Q14, Q15, Q17, Q18, Q19).

Latency Benchmarks. As discussed in Sect. 3.2, even if DynQ is an engine based on query compilation, it is able to start executing a query before compiling it, by executing the Truffle nodes which represent the query in the interpreter. This feature is crucial for obtaining high throughput when executing queries on small datasets. Here, we evaluate the throughput of DynQ against DuckDB. Since DuckDB is based on interpretation and vectorization, it does not spend any time on code generation and query compilation. On small datasets, this approach is commonly faster than compiling queries, since the compilation overhead may not be paid off.

For this evaluation, we consider an experiment similar to the one performed in the context of Umbra [45]. Such an experiment [28] evaluates the throughput (by calculating the geometric mean of queries per second for all TPC-H queries) over different scale factors. In our experiment we evaluate the throughput over scale factors 0.001, 0.01, 0.1, 1, and 10, first on the micro-benchmark queries and then on the TPC-H queries.

The benchmark results are depicted in Fig. 16 for the micro-benchmark and in Fig. 15 for TPC-H. As the figures show, for both the micro-benchmark and TPC-H, DynQ outperforms DuckDB(df) on all evaluated scale factors. In particular, on the micro-benchmark DynQ outperform DuckDB(df) of factors 9.17x (SF 0.001), 5.94x (SF 0.01), 6.51x (SF 0.1), 11.02x (SF 1) and 14.29x (SF 10). On TPC-H, DynQ outperform DuckDB(df) of factors 5.59x (SF 0.001), 3.56x (SF 0.01), 2.65x (SF 0.1), 4.31x (SF 1) and 4.4x (SF 10).

In comparison with DuckDB(preload), the evaluation shows interesting trends. On the smallest scale factors (SF 0.001 and 0.01), DynQ fully executes all queries in the interpreter and it never triggers compilation. On scale factor 0.001, the DynQ throughput differs from DuckDB(preload) by a factor of 4.08x on the micro-benchmark, and of 2.7x on TPC-H. On scale factor 0.01, the DynQ throughput is in line with DuckDB(preload), in particular, DynQ shows a throughput factor improvement of 1.06x on the micro-benchmark, and of 0.95x on TPC-H. On scale factors 0.1, DynQ starts compiling parts of the queries; however, since the datasets are still small, most of the query execution is still in the interpreter. On such scale factor, the DynQ throughput is smaller than the one of DuckDB(preload), by factors 0.58x on the micro-benchmark, and of 0.56x on TPC-H. Then, on scale factor 1, in DynQ query compilation is paid off on the micro-benchmark, reaching a throughput in line with the one of DuckDB(preload), i.e., 0.96x factor. This is not the case for TPC-H, where the throughput of DynQ is factor 0.84x compared with DuckDB(preload). The reason is that the TPC-H queries are much more complex than the micro-benchmark queries, leading to longer query compilation times. Finally, on scale factor 10, DynQ outperforms DuckDB(preload) on the micro-benchmark by a factor of 1.15x, and becomes comparable with DuckDB(preload) on the TPC-H queries, by a factor of 0.98x.

Our evaluation on the query latency shows that JIT compilation in DynQ is not a source of performance concerns, differently from most existing query engines based on compilation.

Comparison with Native DBMS. In this section, we evaluate DynQ against MonetDB [23], a modern, interpreter-based, RDBMS featuring high-performance vectorized execution. Although we do not consider MonetDB a direct competitor to DynQ, this evaluation should be considered an indication of how DynQ performs in comparison with a native RDBMS. For this evaluation, we use MonetDB Database Server Toolkit 11.43.9 (Jan2022-SP1), executing the queries with mclient. We measure the end-to-end query execution time, taking into account the cost of inter-process communication for sending result sets from the server to the client process. For fairness, we configure MonetDB for executing in a single-thread, since we have not yet implemented parallel query execution in DynQ. For this experiment, we evaluate DynQ on R data frames, using a scale factor of 10 for both the micro-benchmark and TPC-H; we present the median of 10 executions.

The benchmark results are depicted in Fig. 17 for TPC-H and in Fig. 18 for the micro-benchmark. As the figures show, MonetDB outperforms DynQ in all queries containing the join operator, i.e., in MQ7 and in all TPC-H queries but Q1 and Q6, with the only exception of Q12, where MonetDB and DynQ show very similar execution times. All remaining queries are rather simple and mostly dominated by table scans. For those queries, DynQ is faster than MonetDB; in particular DynQ outperforms MonetDB by a speedup factor of 3.3x on Q1 and 1.3x on Q6. Concerning the remaining micro-benchmark queries, on MQ6 DynQ shows a speedup of 438x; this is because MonetDB (like the data.table R package) does not stop the query execution once the first 1000 elements (i.e., the limit operator) have been found. On MQ4, DynQ outperforms MonetDB by a speedup factor of 9.16x, because MQ4 returns a large result set that MonetDB needs to serialize and transfer to the client process, whereas DynQ (being an embedded query engine) does not incur such an overhead. Finally, on MQ1, MQ2, and MQ3, MQ5 DynQ outperforms MonetDB by speedup factors of 1.43x, 2.55x, 2.01x, and 1.38x.

Here, we evaluate DynQ using the JavaScript programming language. For this evaluation, we first compare DynQ against AfterBurner [14], which is an in-memory database entirely written in JavaScript, on both the micro-benchmark and on TPC-H. Then, we evaluate DynQ querying data loaded into a JavaScript array of objects, like in the example of Fig. 3. In this setting, we evaluate DynQ on the micro-benchmark against handwritten implementations in JavaScript and implementations that rely on Lodash [36], which is arguably the most efficient and popular data-processing library for JavaScript. Finally, we evaluate DynQ on existing code bases, comparing the performance of a JavaScript library against equivalent implementations using DynQ.