LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation

Dylan Hutchison, Bill Howe, Dan Suciu

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

Abstract

Analytics tasks manipulate structured data with variants of relational algebra (RA) and quantitative data with variants of linear algebra (LA). The two computational models have overlapping expressiveness, motivating a common programming model that affords unified reasoning and algorithm design. At the logical level we propose Lara, a lean algebra of three operators, that expresses RA and LA as well as relevant optimization rules. We show a series of proofs that position Lara %formal and informal at just the right level of expressiveness for a middleware algebra: more explicit than MapReduce but more general than RA or LA. At the physical level we find that the Lara operators afford efficient implementations using a single primitive that is available in a variety of backend engines: range scans over partitioned sorted maps. To evaluate these ideas, we implemented the Lara operators as range iterators in Apache Accumulo, a popular implementation of Google's BigTable. First we show how Lara expresses a sensor quality control task, and we measure the performance impact of optimizations Lara admits on this task. Second we show that the LaraDB implementation outperforms Accumulo's native MapReduce integration on a core task involving join and aggregation in the form of matrix multiply, especially at smaller scales that are typically a poor fit for scale-out approaches. We find that LaraDB offers a conceptually lean framework for optimizing mixed-abstraction analytics tasks, without giving up fast record-level updates and scans.
BibTeX
@inproceedings{hutchison2017laradb,
  author = {Dylan Hutchison and Bill Howe and Dan Suciu},
  title = {{LaraDB: A Minimalist Kernel for Linear and Relational Algebra Computation}},
  booktitle = {BeyondMR@SIGMOD},
  year = {2017},
  doi = {10.1145/3070607.3070608},
}
Figure