It is common for machine learning applications to have complex operator pipelines, with several steps before and after the main execution of the core machine learning algorithm. Consequently, data movement between processes has a performance cost for the execution of the application. In this paper, we propose an end-to-end machine learning framework based on the principle of homoiconicity: data and code are represented in a single unified syntax. This approach allows the eficient interpretation of custom operators at the core of a relational database system. We also present the implementation of a data cleaning framework as an initial milestone. This work is a part of a larger research project to implement BOSS, a novel, general-purpose relational database system that stores and processes homoiconic data. relational database, homoiconicity, symbolic expressions, machine learning, data cleaning, data imputation
the model to be learned during training and executed during inference. It is, thus, not surprising that this is the most extensively researched and optimized aspect of ML applications.
However, the model training and inference is not the only component of the data processing pipeline that plays a role in the application’s overall performance. Many applications move large amounts of data as inputs and produce large output datasets. This data movement is costly and, often, principally unnecessary.
In addition, many applications perform internal data movement for various data operations, such as data augmentation or data normalisation. Some of these steps
increases not only the overhead for data movement but nance of the logic to connect them.
Data cleaning is a particularly interesting example of such data movement-intensive components in the case cause the model learning and the inference process are extremely sensitive to the data quality. Input data is puting missing values and searching and fixing incorrect values (based on common sense, expert knowledge, and user-defined constraints). Algorithms for these tasks
system. DBMS are designed to store, retrieve and proinvolve the usage of dedicated libraries and even systems. the data movement overhead out of the DBMS. With also the engineering cost of implementation and mainte- and can still be significant for large-scale data movement. of an ML pipeline. Cleaning the data is necessary be- retrieval and transformation steps in the same process or therefore generally cleaned using methods such as im- eliminated due to the additional transformations needed cess a large amount of data eficiently, taking advantage of strategies and technologies studied, developed and improved over several decades. P A R T I T I O N I N G
However, implementing all the desired features in the DBMS requires new data representations, operators and logic, which are not standard in typical DBMS. This is challenging to implement while preserving the advan- int + + tages of the DBMS (such as the query optimizer). int int symbol x wfuinItmhctpiaolentmrsae(dUnetD-ionFf.gs)tIhimsespdtlreeasmiigreehndttffioenragwtuatrhredesmbinuatashdauasstaeabrh-adsigeehfinceoodmveers- batch 1 .1. batch 2 .1. 2.. batch 3 A.. i.n2.t f1lo...a5t head and prevents query optimizations; implementing C O L U M N S T O R A G E them at the core of the DBMS backend is more eficient but requires significant efort and expert knowledge. Figure 1: shape-wise partitioning mechanism and storage
Instead, we propose implementing a more generic ex- representation example. tensible system that is flexible and takes advantage of the DBMS eficiency to manipulate data. To achieve that, the DBMS stores as data the executable code that extends • ease for the user to implement new ML algorithms the DBMS functionality. Storing the code as data means and tools by assembling them from operators that the code is an integral part of the relational repre- using symbolic expression logic with flexibility sentation and can be manipulated by the DBMS kernel. while keeping native performance This method is fundamentally diferent from UDFs and triggers, which exist only in the schema and are be re- • with the logic as data paradigm, the approach trieved and run as a black box at query time. With our opens new possibilities for optimizations, unified approach, the DBMS handles this custom logic eficiently, for both the data (as usually handled by the query taking advantage of the optimization strategies produced optimizer) and for the logic (as usually handled by by DBMS research. the compiler) by exposing the logic as symbolic
Fundamentally, homoiconicity refers to this idea that data to the database at every level, from query
code can be read, modified and stored like data. The plan to storage layers.
practically most common forms of homoiconic data are
symbolic expressions (s-expressions). An s-expression is • symbolic expressions are not used only to express
represented as a (potentially nested) list and can, there- the logic of the queries. They are also stored in the
fore, be modified as well as evaluated. For example, ’1 database and evaluated eficiently at query time,
+ 2’ would be represented by the list ’(Plus 1 2)’. Lisp- whose benefits and implementation are detailed
like languages use s-expressions to represent all code as in the use case in the next section.
s-expressions and allow Turing-complete programming
[
Inspired by these homoiconic languages, we are implementing a DBMS called BOSS for Bulk-Oriented SymbolStore. This database stores symbolic expressions in the form of symbols and complex expressions. However, in our implementation, the evaluation of the expressions is performed for a large batch of data at once, thus amortizing interpretation overhead.
Applied to the ML domain, native operators are implemented in the database only for the basic blocks of the ML operations (e.g. transformations, activations). Only the logic of the ML algorithm, less generic, is left to be implemented in userspace with symbolic expressions.
The benefits of this approach are:
selected the decomposed storage model (DSM) [
To amortize this overhead, we developed a novel technique called shape-wise partitioning & decomposition as shown in Figure 1. First, collections of expressions are (horizontally) partitioned by shape, i.e., all expressions (ittcrnhiotetaimceotugnpore.onsrislsSvye,eedwcdlyoifhfe)onirdrldemei,ncbt.ohtamhIetncepchiroFo2sibmgeasudpst,reooetrnhtey1eusp,nseeetsxs.atgpoor.r,grfeiubntsahmsgtiecoebhnneaxtss1septfrhsdoetaarosttmsraaieodisanndppsatalaawrdir-enoe- 110010i()rsyTeeuQmm00100.0001000.11010000 i()rsyTeeuQmm1010.00010.111000 iinntteeggeerrss aanndd abdadtcthh3emstotoreastehxirpdr.esAssiosnhsatphea-twmisuelptiaprltyittiwono- 0.S0F01 .0010 .100 .01 1 2 5 01 .0100 .100 .01 1 2 5 01 B0u.0lk0B1OSS IHmypAuIteDB ing ensures homogeneous partitions, entire partitions Q1 Q6 Wolfram can be processed with a minimal number of function calls (one per subexpression). This ensures highly CPU- Figure 2: Performance comparison tests for TPC-H Q1/Q6 eficient processing. (relational), and HyAI (imputation). The missing bars for Wolfram are caused by the engine running out of memory.
to the user and benefits from the optimizations allowed by the bulk evaluation method.
We implemented a data imputation framework in the context of a project called HyAI1. The project’s overall goal was to optimize the decisions to charge or consume hydrogen batteries using machine learning technologies 4. Evaluation that model future electricity consumption from the analysis of many diferent data sources. Because the batteries All the experiments have run on a PC with an Intel i9were intended to be deployed in areas where data trans- 10990K CPU and 32GB RAM DDR4 3600MHz. ferred from these sources might be unreliable, a robust To confirm that relational operators in BOSS are perimputation framework was implemented in the database forming competitively with state-of-the-art DBMS, we management system so that the user could define custom compared the performance of BOSS with MonetDB using and potentially complex imputation logic. the TPC-H queries Q1 and Q6 with various scale factors.
Missing data is commonly handled in database systems The results in Figure 2 shows that BOSS performs on the
by inserting null values and internally defining an arbi- same magnitude with MonetDB without an impact from
trary value as null or using a boolean flag. This method having to support homoiconicity in our implementation.
does not allow to specify why the data is missing and Also shown in Figure 2, we compared the handling of
to let the data cleaning process decide how the value is missing data with another implementation, ImputeDB
imputed. However, there are multiple reasons why data [
One approach for the user to handle missing values column. BOSS performs better with a factor of x261. This is by calling the imputation method on the fly before in- result shows that the bulk approach to implementing imserting the data into the database. However, this method putation operators is highly eficient. Our method to does not allow the use of future data for the imputation. evaluate expressions eficiently could also benefit more For example, both previous and subsequent values may advanced imputation techniques. be needed for the interpolation of time series data. In addition, the comparison for both relational opera
Alternatively, the user could handle missing values tors and missing data evaluation with another backend as part of the query logic by detecting the missing val- based on the Wolfram engine shows that our implementaues and using nested queries or UDFs. However, this tion outperforms by several orders of magnitude the commethod usually incurs an execution overhead that afects mercial homoiconic engine. It confirms that evaluating performance and increases the queries’ complexity. homoiconic data comes with a high cost for interpreting
With the imputation framework that we implemented, the expressions, which is solved with the technique we
the user stores missing data as complex expressions. The have implemented in BOSS.
expressions describes the logic to use for the data
imputation, e.g. instead of inserting a ’null’ value, the user
inserts the expression ’(PreviousValue() + NextValue()) 5. Related Work
/ 2’ to do a simple local average. As presented in the
previous section, this approach provides more flexibility
Data cleaning is a critical aspect of many decision-making
and analytics applications, particularly in ML-based
software. Some solutions have been proposed to automate
the process, such as HoloClean [
For the future, we plan to extend the system with
additional features for data processing pipelines: operators
to support additional data cleaning use cases, algebraic
operators needed for model training and inference and
even domain-specific operators. The system will, further,
benefit from relational components such as query
optimization, transactional semantics and data visualization.
side-by-side with the DBMS. Alternative solutions have
been proposed to integrate the data cleaning operators
as part of the database query, such as ImputeDB as an
imputation module for the Data Civilizer framework [
Both approaches do not allow the user to make decisions during the data cleaning, except for some initial setup in the case of HoloClean. They difer from our method, which performs data imputation during query but is based on the information provided by the user during data insertion.
Most research on accelerating the ML pipeline and
using a unified data management solution focuses on the
acceleration of the training step. The approach in [
Tupleware [
In addition, there is research work on integrating ML
operators as part of database kernel ([