Towards an efficient OLAP engine based on linear algebra
João M. Afonso · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · 2018
Relational database engines associated to the widely used Structured Query Language (SQL) are suffering unsatisfactory performance results in complex business queries, due to ever increasing volumes of stored data. To retrieve and process data in a more efficient way, Online Analytical Processing (OLAP) models have been proposed with an increased focus on attributes (measures and dimensions) over records. OLAP is based on a row-oriented theory, while a columnar-oriented theory could considerably improve the performance of analytical systems. The Typed Linear Algebra (TLA) approach is an example of such theory: it encodes each database attribute in a distinct matrix. These matrices are combined in a single Linear Algebra (LA) expression to obtain the result of a query. This dissertation combines concepts of relational databases, OLAP, TLA and performance engineering to design, implement and validate an efficient TLA-DB engine: SQL queries are converted into its equivalent LA expression, using Type Diagrams (TDs), which represent each matrix as an arrow pointing from the number of columns to the number of rows, TDs are converted to a LA expression encoded in Linear Algebra Query language (LAQ) and the LAQ script of a query is automatically coded in C Plus Plus (C++). An efficient TLA-DB engine required the encoding of the sparse matrices in an adequate format, namely Compressed Sparse Column (CSC), while the operations specified in LAQ expressions had their performance improved by optimised algorithms and an optimised query processor. The functionality of the resulting LAQ engine was validated with several TPC Benchmark H (TPC-H) queries for various dataset sizes. A comparative evaluation of the TLA-DB with two popular Database Management Systems (DBMSs), PostgreSQL and MySQL, showed that the developed framework outperforms both DBMSs in most TPC-H queries.