The Data World is Not Flat: Efficient Factorized Execution for Relational Systems

Abstract

Relational database management systems (RDBMSs) struggle with efficient execution of graph workloads, particularly those involving many-to-many joins with large intermediate results. Such joins are common in modern applications such as social networks, recommendation engines, and knowledge graphs. Traditional RDBMSs are optimized for selective joins, while the typical result blow-up in graph analytics leads to exceptionally long query times or even system crashes due to out-of-memory errors. Since graph and relational data are often intertwined, a unified solution can simplify system architecture and improve performance. To address this, we propose a novel code-generating engine with factorization, which represents tuples in a hierarchical form. Our approach enables intra-query-parallelized query execution on factorized representations and generates code to overcome their CPU-unfriendly layout. Additionally, we extend current factorized approaches by bottom-inserts to make joins reorderable. Our factorized approach can outperform traditional tuple representations and state-of-the-art RDBMSs by orders of magnitude on synthetic workloads and benchmarks as our experiments show. Moreover, its potential integrability into traditional RDBMSs enables efficient processing of complex, highly redundant queries, offering a unified and scalable solution for modern workloads.