Title: LevelHeaded: Making Worst-Case Optimal Joins Work in the Common Case,
Abstract: Pipelines combining SQL-style business intelligence (BI) queries and linear
algebra (LA) are becoming increasingly common in industry. As a result, there
is a growing need to unify these workloads in a single framework.
Unfortunately, existing solutions either sacrifice the inherent benefits of
exclusively using a relational database (e.g. logical and physical
independence) or incur orders of magnitude performance gaps compared to
specialized engines (or both). In this work we study applying a new type of
query processing architecture to standard BI and LA benchmarks. To do this we
present a new in-memory query processing engine called LevelHeaded. LevelHeaded
uses worst-case optimal joins as its core execution mechanism for both BI and
LA queries. With LevelHeaded, we show how crucial optimizations for BI and LA
queries can be captured in a worst-case optimal query architecture. Using these
optimizations, LevelHeaded outperforms other relational database engines
(LogicBlox, MonetDB, and HyPer) by orders of magnitude on standard LA
benchmarks, while performing on average within 31% of the best-of-breed BI
(HyPer) and LA (Intel MKL) solutions on their own benchmarks. Our results show
that such a single query processing architecture is capable of delivering
competitive performance on both BI and LA queries.