Extensible Database Simulator for Fast Prototyping In-Database Algorithms

The architecture of DBSim is presented in Figure 1. It consists of two parts, the kernel (yellow box) and interfaces (pink boxes). The kernel includes several critical database components (white boxes) from query parser to physical plan executor, while interfaces are the GUI (for interactive querying and analyzing) and APIs (for programmatic querying and building extensions).

There are two workflows in DBSim, one is querying workflow and another is extension workflow, where the former is the steps of query processing and the latter shows how to create an extension and how the extension works in DBSim. We describe more details about them in Section 2.2 and  2.3.

Similar to the query engine in general RDBMS, the kernel of DBSim includes five components, query parser, operators, query optimizer, query compiler and physical plan executor. Though a real, complete RDBMS normally has more modules like storage engine, it is not necessary to integrate them into DBSim, because most studies about in-database analytics in data science community focus on the query engine. The components of DBSim kernel serve as follows during query processing: (1) query parser parses the input query and generates an abstract syntax tree(AST), (2) operators module resolves the schema information for each node in AST and transforms AST into logical plan, (3) query optimizer applies a series of rules to transform the query plan in order to find the best equivalent plan, (4) query compiler transforms the logical plan into physical plan, and finally (5) physical plan executor executes the plan and outputs results. Based on them, the query processing workflow is same as general RDBMS: as shown in Figure 1, the queries (grey box) are input to the query engine kernel through APIs, then they are passed through the kernel components one by one, from query parser to executor, and finally the executor returns the results to users via APIs. Note that we currently implement a heuristic query optimizer (which is more rule-based) instead of the most commonly used volcano-style optimizer (which is more cost-based) in mainstream databases, because rule-based optimizer allows users to fully control the optimization process like the order for applying the rules, which gives users a much clearer insight about how each rule contributes to the optimization. This is important in analyzing the performance and finding bottlenecks of in-database algorithms.

In DBSim, the basic unit for organizing the implementations is Syntax, which is a larger concept than the query language syntax. It refers to a scope or name space that manages a collection of implementations ranging from query syntax parsing to query execution functions. We call the native implementations of DBSim Standard Syntax. Similarly, the unit of organizing extensions is also Syntax, named as Extended Syntax, which is a suite of the implementations for all the extended items scoped in the Syntax. Comparing to Standard Syntax, Extended Syntax is incremental, i.e., it only includes the extended implementations based on Standard Syntax, like adding new operators or overwriting existing functions, instead of re-implementing everything in Standard Syntax.

As one of the most important features of DBSim, flexible extension is supported by a registry-based extension mechanism. As illustrated in Figure 2, the mechanism is centered at a registry that acts as a middleware between the kernel and extensions. Each row in the registry includes the identity of an Extended Syntax and a registry entry which maintains the interfaces for the Syntax to mount its implementations. Specifically, a registry entry provides several entry points for the implementations of different purposes, including adding query keywords, adding data types and operators, inserting optimization rules, customizing the translation from logical to physical plan, etc. To make an Extended Syntax be in effect, users just need to register the implementations of the Syntax to the corresponding entry points in a registry entry and fill the Syntax name and the entry into the registry as a new row. For each registered Extended Syntax, the registry offers an option to enable/disable it, and each registry entry also provides options to enable/disable each entry point. When DBSim starts, the kernel will read in the registry and use the enabled extended implementations to replace the corresponding parts of the Standard Syntax, essentially by the flexible runtime function overwriting in Python.

The Syntax suite and registry-based mechanism guarantee flexible creation and management of the extensions. Users can enable/disable a whole Extended Syntax simply by turning it on/off in the registry, or manage the extensions in a finer level by manipulating each entry point individually in the registry entry. Such features of DBSim make it quite flexible to apply any one or combination of more than one Extended Syntax (as long as they have no conflict), which has not been achieved by prior works. Figure 2 shows an example: user creates two Extended Syntax, namely “SpatialSyntax” and “SimSelection”, to support spatial and similarity queries respectively. The user can freely disable either Syntax or enable both, or disable them partially and let the rests of them co-exist.

DBSim provides three methods of query processing cost estimation for users to evaluate the algorithm performance. First, DBSim integrates a built-in cost estimator that calculates the query cost based on multiple factors including data types, operator types, number of input rows, etc. Second, to make the cost estimation more accurate, DBSim also supports connecting and using the cost estimator of real DBMS which is well-developed and verified in real-world application. Specifically, DBSim translates its query plan and related tables to those of the real DBMS, then feeds them to the DBMS. The translated plan is not exactly executable in the real DBMS, but is normally a valid input for only calling the cost estimator module in the DBMS. Currently DBSim supports SQLite, and the support for PostgreSQL is under development. Third, users can evaluate the performance improvement by comparing the actual query execution time in DBSim with and without their extensions.

There are two types of interfaces, APIs and GUI, for programmatic and visual access to DBSim respectively. Major APIs are the registry, registry entries and entry points in the entries as discussed in Section 2.3. In this section we mainly introduce the GUI.

Shown by Figure 3, the GUI includes 6 blocks: (1) query input box, (2) table for showing query execution results , (3) query plan visualization panel, (4) interactive optimization rule list, (5) history records of the input queries, rules applied, estimated plan costs (original and optimized) and real execution time, and (6) the “Manage datasets” button for selecting, uploading and deleting datasets. After some datasets are uploaded, when users input a query, it will be automatically executed, with the results reported in block 2 and query plans visualized in panel 3. Panel 3 is spilt into two parts, where the left part presents the initial plan generated directly from the input query and the right part shows the best plan after optimization using the rules in block 4. Block 4 is a menu listing optimization rules being used currently. Users can add/remove rules by clicking the “+” or “-” buttons, they can also change the order of rules by clicking one of the two arrow signs to move a rule up or down. The query will be optimized by repeatedly applying the listed rules in the given order until no more rules can be applied or a maximum number of iterations is reached. Once a query is executed successfully, the query itself, the rules applied on it, the query cost estimation of the original and optimized plans and the real elapsed time for the execution by DBSim will be recorded and presented in block 5, along with all the previous records. The estimated query cost can be calculated by either DBSim built-in estimator or the real DBMS estimator, depending on the configuration.

With this GUI, users can easily test and analyze whether the Extended Syntax works as their expectation. For example, by the query plan visualization panel, users can know if an extended operator was parsed correctly, and by interactively changing the rules and the order in block 4 and comparing the current plan cost/execution time with the history records, users will acquire a straightforward insight about how the extended rules contribute to the optimization, etc. Furthermore, the GUI can also be used as a teaching tool for users to learn the internal of general RDBMS.

We will present this demo based on a use case of in-database movie recommendation. Supposing data scientists are implementing an extended relational algebra that supports in-database similarity search with multi-dimensional embeddings. Based on it they will build an in-database movie recommendation application to recommend movies to users which are similar to their favorites and satisfy some boolean conditions. For example, given an embedding of a user’s favorite movie and the fact that the user often watched musical animation movies, the application can use an extended SQL query to find all those movies whose genres include both of “Musical” and “Animation” and with an embedding similar enough to the given embedding. We will use the MovieLens 20M dataset¹¹1available at https://grouplens.org/datasets/movielens/20m/ in this demo. And the embeddings will be generated by some state-of-the-art neural model over the dataset.

This is the first phase of this demo. We first introduce the example scenario to the audience as follows: similarity search on vector data is a very commonly used operation in data science algorithms. But it is not supported natively by RDBMS. To implement an in-database similarity search, normally data scientists use user-defined functions (UDF). The problem is that the flexibility of UDF is very limited and its performance is not optimal since query optimizer does not pay as much attention as regular operators to it. Therefore, a better way is extending the relational algebra to add a vector data type and a similarity selection operator which can be seamlessly mixed and optimized with other relational operators.

After the scenario introduction, we present the major steps to implement an Extended Syntax (named as “SimSelection Syntax”) with the new data type “Vector”, the new similarity selection operator “SimSelect”, the new distance computing operator “To”, and some new optimization rules considering the operators together with other relational operators. The first step is implementing the necessary functions from new query syntax parsing to new execution behaviours. To avoid waste of time, we make the functions ready before this demo and browse them together with the audience at the demo time. If the audience is interested in some details, we will make a further explanation to them, like how the functions parse such a literal “[1,2,3,4]” into a Vector. The second step is registering the SimSelection Syntax into the registry. We present this step by writing the code at demo time, because it is one of the most important features of DBSim and only a few lines of code need to be written. We show how to create a registry entry, how to mount the functions implemented in the first step onto the entry points, how to enable/disable the whole Syntax or an individual entry point, etc. Finally we load data, execute example queries (with both the extended and standard relational operators, e.g., SIMSELECT * FROM t1, t2 WHERE t1.c=t2.c AND t1.v TO [1,2,3,4] ¡ 10) end-to-end through the APIs and show the correct results printed on terminal.

In the first phase of this demo, we present to the audience about how to implement an Extended Syntax, the SimSelection Syntax, in DBSim. Then here in the second phase, we guide the audience to experience the GUI with the SimSelection Syntax. In this section all the block numbers refer to the numbers shown in Figure 3.

First the audience click the “Manage datasets” button to select and upload the example datasets we prepare. Then they input a query that mixes up similarity search and regular relational operators into the input box (block 1) and after a while the query will be executed automatically. The audience see the results are printed as a table in result output box (block 2), the initial and optimized query plan trees are visualized in the query plan panel (block 3), and one new record is appended in the history list (block 5), including the current query, the applied rules, the estimated query costs and the real execution time. Then we guide the audience to see the rule menu (block 4). Initially it is blank, therefore the two plans drawn in plan panel are identical. We let the audience click the “+” button to browse and select some rules to add into the optimizer. Particularly, we will suggest they to add both of the standard rules and extended rules to see how the extended rules contribute to the optimization. Once it is done, the audience observe that the panel is refreshed, the optimized plan changes and is re-executed, and a new history record is generated accordingly showing a probably lower optimized plan cost and shorter execution time. Then we let the audience try to remove some rules and change the order, and observe how the plan, cost and time change to better understand the optimization process.