AC/DC: In-Database Learning Thunderstruck

Mahmoud Abo Khamis, Hung Q. Ngo, XuanLong Nguyen, Dan Olteanu, Maximilian Schleich

TL;DR

AC/DC is a high-performance gradient descent solver designed to train machine learning models directly inside normalized databases. By factorizing computations and exploiting database structures like functional dependencies, it outperforms traditional frameworks like TensorFlow and MADlib by up to three orders of magnitude while avoiding the "data export tax."

What Problem Does This Paper Address?

Most machine learning workflows follow a "pull-and-process" pattern: data is joined across multiple database tables, exported into a massive flat file (the design matrix), and then fed into an ML framework. This approach has three major flaws:

  1. The Export Tax: Moving millions of rows out of a database is incredibly slow.
  2. Redundancy: Joining tables creates massive amounts of redundant data, especially when dealing with one-hot encoded categorical features.
  3. Suboptimality: Traditional ML tools treat the design matrix as a "black box," ignoring the underlying relational structure (like functional dependencies) that could simplify the math.

The authors introduce AC/DC (Alternating/Discrete Currents—a nod to its handling of both continuous and categorical data) to solve these optimization problems where the data lives, using the database's own logic to speed up the learning process.

Methods

AC/DC isn't just a wrapper; it’s a fundamental rethink of how gradients are calculated over relational data. Its core innovations include:

  • Factorized Computation: Instead of materializing a giant join and then calculating aggregates, AC/DC "pushes" the aggregates down into the join process. This allows it to achieve a lower theoretical complexity than even the join itself.
  • Sparse Representation: Rather than expanding categorical variables into thousands of one-hot encoded columns (which crashes many systems), AC/DC uses "group-by" aggregates to represent these features compactly.
  • Massive Sharing: A single gradient descent step requires hundreds or thousands of different aggregates. AC/DC uses a unified "variable order" (a tree-based execution plan) to compute all these aggregates in a single pass, maximizing cache locality.
  • Functional Dependency (FD) Exploitation: If a database knows that zip_code determines city, AC/DC uses this FD to mathematically reparameterize the model, reducing the number of variables the solver needs to track.

Datasets

The researchers evaluated AC/DC using a real-world Retailer dataset.

  • Structure: 5 relations (Inventory, Census, Location, Item, Weather).
  • Scale: Up to 86 million tuples and 154,000 features.
  • Variants: They created four fragments ($v_1$ to $v_4$) with increasing sizes and numbers of categorical features to test the limits of various systems.

Key Insights and Ideas

  • The "Aha" Moment on Complexity: The authors point out a counter-intuitive truth: computing the aggregates needed for ML can be asymptotically faster than computing the underlying join. This means any system that joins data before learning is fundamentally suboptimal.
  • FDs as Dimensionality Reduction: While FDs are usually a database normalization tool, AC/DC proves they are powerful for ML. By recognizing that some features are functionally determined by others, they can invert smaller matrices and solve lower-dimensional problems.
  • Bulk vs. Individual Processing: AC/DC found that it is more efficient to compute 37 million sum aggregates in bulk than to compute 43 count aggregates individually, provided they share the same relational structure.

Key Results

The performance gains are, quite literally, "thunderstruck":

  • Speed: AC/DC is up to 1,000x faster than competitors like R, MADlib, libFM, and TensorFlow.
  • Scalability: On the largest dataset ($v_4$ with 154K features), every other system failed due to memory limits, 24-hour timeouts, or internal design constraints (like MADlib’s 1600-column limit). AC/DC finished in under 30 minutes on a single commodity core.
  • FD Impact: Exploiting functional dependencies provided an additional 3.5x to 3.8x speedup for complex models by reducing the feature space.
  • Convergence: AC/DC’s batch gradient descent (BGD) was often faster than a single epoch of Stochastic Gradient Descent (SGD) in other frameworks because of its superior data handling.

Limitations and Future Work

The authors identify a few "growing pains" for the system:

  • Compilation Overhead: To achieve maximum speed, AC/DC generates specific C++ code for aggregate updates. For very high-degree models, this code becomes so large that it can cause C++ compilers to crash.
  • Model Scope: Currently, the system is optimized for a specific class of problems (ridge linear regression, polynomial regression, and factorization machines).
  • Future Directions: The team is working on a "hybrid" approach to resolve indices at compile-time without exploding the code size, aiming to balance extreme performance with manageable binary sizes.

Summary updated

Abstract

We report on the design and implementation of the AC/DC gradient descent solver for a class of optimization problems over normalized databases. AC/DC decomposes an optimization problem into a set of aggregates over the join of the database relations. It then uses the answers to these aggregates to iteratively improve the solution to the problem until it converges.The challenges faced by AC/DC are the large database size, the mixture of continuous and categorical features, and the large number of aggregates to compute. AC/DC addresses these challenges by employing a sparse data representation, factorized computation, problem reparameterization under functional dependencies, and a data structure that supports shared computation of aggregates.To train polynomial regression models and factorization machines of up to 154K features over the natural join of all relations from a real-world dataset of up to 86M tuples, AC/DC needs up to 30 minutes on one core of a commodity machine. This is up to three orders of magnitude faster than its competitors R, MadLib, libFM, and TensorFlow whenever they finish and thus do not exceed memory limitation, 24-hour timeout, or internal design limitations.
BibTeX
@inproceedings{khamis2018ac,
  author = {Mahmoud Abo Khamis and Hung Q. Ngo and XuanLong Nguyen and Dan Olteanu and Maximilian Schleich},
  title = {{AC/DC: In-Database Learning Thunderstruck}},
  booktitle = {DEEM@SIGMOD},
  year = {2018},
  url = {https://openreview.net/forum?id=Bdd0U0fGIk},
}

Loading related content...

Figure