TL;DR
This paper introduces LARA, a minimalist algebra that unifies relational algebra (RA) and linear algebra (LA) computations. By providing a common framework, LARA enables unified reasoning and optimization for analytics tasks that traditionally fall into separate RA or LA paradigms. Their implementation, LARADB, demonstrates competitive performance against MapReduce, especially at smaller scales, and highlights the effectiveness of LARA-driven optimizations.
What Problem Does This Paper Address?
Modern data analytics tasks often blend two distinct computational paradigms: relational algebra (RA) for structured data manipulation (like ETL) and linear algebra (LA) for numerical computations (like machine learning). While systems exist for each, they often struggle to seamlessly integrate both. RA-oriented systems can obscure LA properties crucial for optimization, while LA-oriented systems can make simple relational queries awkward. This creates a need for a unified programming model that can express both RA and LA operations, allowing for more effective reasoning and optimization across the spectrum of analytics tasks. The authors argue that existing systems either force users into awkward "gymnastics" or obscure important algebraic properties, hindering optimization.
Methods
The paper proposes a two-level approach:
- LARA (Logical Algebra): A minimalist algebra with three core operators (UNION, JOIN, EXT) designed to express both RA and LA operations. It models data as "associative tables" (key-value mappings) and leverages semiring structures to capture LA properties. LARA aims to be more explicit than MapReduce but more general than pure RA or LA.
- PLARA (Physical Algebra): A physical algebra built on top of "partitioned sorted maps." This abstraction models the underlying storage and access mechanisms of various systems (databases, key-value stores, etc.). PLARA focuses on low-level optimizations like operator fusion and efficient data access through range scans.
The authors also introduce a set of rewrite rules that can be applied to PLARA plans to optimize query execution, such as pushing filters into data loads or eliminating unnecessary sorting.
Datasets
The paper uses two main datasets for evaluation:
- Sensor Quality Control Data: Real-world data from "Array of Things" sensors, spanning 1.5 months. This dataset is used to demonstrate LARA's ability to express complex mixed RA/LA tasks and to evaluate the impact of PLARA optimizations.
- Power Law Graph Generator Data: Synthetically generated matrices based on the Graph500 power law graph generator. This data is used to compare the performance of LARADB against MapReduce for matrix multiplication (MxM), a common benchmark for both RA and LA.
Key Insights and Ideas
- Unifying RA and LA is Achievable and Beneficial: The core insight is that a single, minimalist algebra (LARA) can effectively capture the essence of both RA and LA, paving the way for unified reasoning and optimization.
- Minimalism Aids Optimization: By limiting the number of core operators, LARA simplifies the optimization process and makes it easier to reason about complex query plans.
- Partitioned Sorted Maps are a Powerful Abstraction: The physical algebra (PLARA) demonstrates that a common abstraction of partitioned sorted maps can support efficient implementations of LARA operators and enable significant optimizations.
- Optimization Opportunities Abound in Mixed-Mode Analytics: The paper showcases numerous optimization rules (e.g., pushing filters, eliminating sorts, leveraging symmetry) that are specific to the mixed RA/LA nature of the computations, leading to substantial performance gains.
- Startup Costs are a Major Bottleneck for MapReduce: The experiments highlight that for smaller-scale computations, the overhead of starting MapReduce jobs significantly hinders performance compared to systems like LARADB that run within an existing infrastructure.
Key Results
- Sensor Quality Control Task: LARA and PLARA were successfully used to express a complex sensor calibration task involving filtering, binning, residuals calculation, and covariance estimation. Optimizations like (A) (pushing aggregations into sorts) and (S) (leveraging symmetry) provided significant speedups, with the combined optimizations reducing runtime by up to 4x.
- Matrix Multiplication (MxM) Performance: LARADB demonstrated competitive performance against MapReduce for MxM. At smaller problem sizes (scale 10-13), LARADB was significantly faster (dominating MapReduce) due to lower startup costs. At larger scales (scale 19), performance converged, indicating that LARADB can achieve comparable efficiency to established systems.
Limitations and Future Work
- Manual Optimization Implementation: The optimizations discussed and evaluated were implemented manually. The authors acknowledge that building an automatic optimizer that applies these rules is a direction for future work.
- Limited Scope of RA/LA Operations: While LARA covers many core RA and LA operations, the paper mentions that more advanced operations (e.g., outer join, difference, division, pivot, masks, convolution) are expressible but not fully explored in this work.
- Focus on Specific Backend: The implementation was demonstrated on Apache Accumulo. While the authors believe the approach is generalizable to other BigTable-like systems, further work could explore broader backend integrations.
- Future Work: The authors aim to use LARA as a conduit for studying and exploiting the relationship between LA and RA, particularly within database optimizers for joint linear-relational analytics. They also suggest exploring more sophisticated partitioning schemes beyond horizontal partitioning.
Summary updated