AC/DC: In-Database Learning Thunderstruck

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

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.

1. Introduction

Most machine learning (ML) 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 suffers from three major flaws: the "export tax" (slow data movement), extreme redundancy (especially with one-hot encoded categorical features), and suboptimality (ignoring relational structures like functional dependencies).

The authors introduce AC/DC (Alternating/Discrete Currents) to solve optimization problems directly where the data lives. By using the database's own logic, AC/DC avoids materializing giant joins and exploits relational properties to accelerate the learning process.

2. Methodology

AC/DC rethinks gradient calculation over relational data through several core innovations.

2.1 Factorized Computation and Massive Sharing

Instead of materializing a join, AC/DC "pushes" aggregates down into the join process. This factorized approach allows for lower theoretical complexity than the join itself. To handle the thousands of aggregates required for a single gradient descent step, AC/DC uses a unified variable order—a tree-based execution plan. This structure enables shared computation and maximizes cache locality.

Variable order and aggregate registers for shared computation

As shown in Figure 3, the variable order $\Delta$ organizes the dependencies between variables, while aggregate registers ($\mathcal{R}$ and $\Lambda$) store intermediate results to be reused across different aggregate computations.

2.2 Sparse Representation and Update Logic

Categorical variables are represented compactly using "group-by" aggregates rather than expanding into sparse one-hot encoded columns. The update logic is recursive over the variable order tree.

Factorized computation of aggregates over a tree structure

Figure 2 illustrates how aggregates $\alpha$ are updated by combining local values $\alpha_0$ with results from child subtrees $\Delta_j$. This recursive structure ensures that computation is shared effectively across the entire model.

2.3 Functional Dependency (FD) Exploitation

AC/DC uses functional dependencies (e.g., zip_code $\to$ city) to reparameterize the model. By recognizing these dependencies, the system reduces the number of variables, effectively performing dimensionality reduction that simplifies the underlying optimization problem.

3. Experimental Evaluation

The system was evaluated using a real-world Retailer dataset comprising 5 relations (Inventory, Census, Location, Item, Weather) with up to 86 million tuples and 154,000 features.

Key results include:

  • Performance: AC/DC is up to 1,000x faster than R, MADlib, libFM, and TensorFlow.
  • Scalability: On the largest dataset variants, all other systems failed due to memory or timeout constraints, while AC/DC finished in under 30 minutes on a single 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 due to its superior data handling.

4. Conclusion

AC/DC demonstrates that in-database learning can significantly outperform external ML frameworks by exploiting relational structure. While the system currently faces challenges with compilation overhead for extremely high-degree models, its ability to handle massive, normalized datasets without an "export tax" marks a significant advancement in scalable machine learning. Future work focuses on hybrid indexing strategies to balance 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},
}
Figure