Fast Matrix Multiplication for Database Query Processing

Motivation : Modern data analytical workloads – from graph processing to machine learning – have evolved significantly, increasingly combining JOIN with additional relational-algebra operators and aggregate functions (e.g., PROJECT and COUNT). Traditionally, database query processing has been dominated by discrete, logicbased primitives such as for-loops [9, 10, 13], tree decompositions [4], and data partitioning [6, 8], which are fundamentally combinatorial . However, the landscape changes when examining graph analytics, where algebraic algorithms – which treat query processing as a series of high-dimensional tensor or matrix operations – have achieved strictly lower theoretical complexity than the best-known combinatorial counterparts. Fast matrix multiplication (FMM) bridges this gap. As modern data systems increasingly integrate dedicated linear algebra kernels (e.g., for ML), repurposing these optimized algebraic engines for classical query processing offers immense potential. This drives the core insight of our research: a comprehensive exploration of FMM within database query engines, bringing the theoretical power of algebraic techniques to practical data systems.