HorseIR: bringing array programming languages together with database query processing
- 6 April 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 53 (8), 37-49
- https://doi.org/10.1145/3393673.3276951
Abstract
Relational database management systems (RDBMS) are operationally similar to a dynamic language processor. They take SQL queries as input, dynamically generate an optimized execution plan, and then execute it. In recent decades, the emergence of in-memory databases with columnar storage, which use array-like storage structures, has shifted the focus on optimizations from the traditional I/O bottleneck to CPU and memory. However, database research so far has primarily focused on CPU cache optimizations. The similarity in the computational characteristics of such database workloads and array programming language optimizations are largely unexplored. We believe that these database implementations can benefit from merging database optimizations with dynamic array-based programming language approaches. Therefore, in this paper, we propose a novel approach to optimize database query execution using a new array-based intermediate representation, HorseIR, that resides between database queries and compiled code. Furthermore, we provide a translator to generate HorseIR from database execution plans and a compiler that optimizes HorseIR and generates efficient code. We compare HorseIR with the MonetDB RDBMS, by testing standard SQL queries, and show how our approach and compiler optimizations improve the runtime of complex queries.Keywords
This publication has 15 references indexed in Scilit:
- In-Memory Big Data Management and Processing: A SurveyIEEE Transactions on Knowledge and Data Engineering, 2015
- Automatic Parallelization of Array-oriented Programs for a Multi-core MachineInternational Journal of Parallel Programming, 2012
- Efficiently compiling efficient query plans for modern hardwareProceedings of the VLDB Endowment, 2011
- DBToasterProceedings of the VLDB Endowment, 2009
- Query optimizationACM Computing Surveys, 1996
- Q'Nial: A portable interpreter for the nested interactive array language, NialSoftware: Practice and Experience, 1989
- Join indicesACM Transactions on Database Systems, 1987
- Query Optimization in Database SystemsACM Computing Surveys, 1984
- Optimizing the performance of a relational algebra database interfaceCommunications of the ACM, 1975
- On the criteria to be used in decomposing systems into modulesCommunications of the ACM, 1972