In traditional machine learning pipelines, there is a fundamental mismatch between how data is stored and how models are trained. Enterprise data is typically stored in highly structured, normalized relational databases across multiple tables (such as Users, Orders, and Products) to eliminate redundancy. However, standard machine learning algorithms universally demand a single, flat "design matrix" where each row represents an independent observation.
To bridge this gap, the standard engineering fix is to execute a database JOIN query, flattening the multi-table schema into a single file before training begins. This step introduces a massive computational barrier known as the join explosion or materialization bottleneck.
The Join Explosion Problem
When you join multiple tables containing one-to-many or many-to-many relationships, data volume expands combinatorially. For example, if a single user has 100 orders, and each order contains 10 products, joining these tables duplicates that user's demographic features 1,000 times in the resulting matrix.
As Abo Khamis et al. and Ngo et al. observe, this materialization step frequently yields intermediate datasets that are orders of magnitude larger than the sum of the original input tables. A few megabytes of normalized tables can easily balloon into gigabytes or trillions of rows of highly redundant data, leading to memory exhaustion and prohibitive processing times (Yang et al.).
Normalized Tables (Small, Efficient)
[Users] ───► [Orders] ───► [Products]
│
▼ (Standard Database JOIN)
Materialized Design Matrix (Exponentially Larger, Redundant Rows)
[ User_1 | Order_1 | Product_1 ]
[ User_1 | Order_1 | Product_2 ]
[ User_1 | Order_2 | Product_3 ] <-- User_1 features duplicated repeatedly
To bypass this bottleneck, a powerful research direction has emerged: In-Database Factorized Learning. Instead of exporting and flattening the data, these techniques rewrite machine learning algorithms to operate directly on the underlying normalized tables, computing models asymptotically faster than the time it would take to simply materialize the join.
The Core Insight: Pushing Aggregates Down
Why is it possible to train a model without looking at the full, flattened dataset? The key insight is that most machine learning algorithms do not actually need to inspect individual rows of a design matrix. Instead, during optimization (such as calculating gradients or loss functions), they rely on aggregates—sums, counts, and inner products of features.
Because basic algebraic operations like addition and multiplication follow the distributive law ($a \cdot b + a \cdot c = a \cdot (b + c)$), we can push the mathematical operations of our machine learning model directly down into the database tables before any join occurs.
A Simple Mathematical Intuition
Imagine we want to compute a basic feature interaction—the sum of a user attribute $x$ multiplied by a product attribute $y$ across all purchases:
$$\text{Result} = \sum_{\text{all purchases}} (x \times y)$$
If we materialize the join first, and a user has bought 1,000 products, we must perform 1,000 multiplications and 1,000 additions on a massive, duplicated table.
However, using factorization, we can rewrite the expression by grouping the products by user:
$$\text{Result} = \sum_{\text{users}} \left( x \times \sum_{\text{products bought by user}} y \right)$$
Now, we compute the sum of $y$ within the small Products table first, and then multiply the result by $x$ in the Users table. We achieve the exact same mathematical result, but the computational complexity drops from a multiplicative relationship ($O(\text{Users} \times \text{Products})$) to an additive one ($O(\text{Users} + \text{Products})$).
Frameworks and Implementations
This core insight has been generalized across a wide variety of machine learning tasks through several foundational frameworks:
Functional Aggregate Queries (FAQ)
The mathematical abstraction of pushing aggregates past joins is formalized by Abo Khamis et al. as Functional Aggregate Queries with Additive Inequalities (FAQ-AI). The authors prove that by combining database theory with geometric data structures, complex optimization problems can be solved directly over relational structures (Abo Khamis et al.).
Specialized In-Database Engines
To execute these factorized operations efficiently, researchers developed specialized query engines like LMFAO (Layered Multiple Functional Aggregate Optimization) (Schleich et al.) and AC/DC (Abo Khamis et al.). These engines decouple data-dependent aggregates from the machine learning optimization solver. They use specialized code-generation stacks to compute massive batches of aggregates directly over relational joins, outperforming traditional machine learning libraries by several orders of magnitude without ever creating flat intermediate files.
Relational Clustering and Regression
The benefits of factorized computing extend well beyond linear models:
- Clustering: Traditional $k$-means requires calculating distances to cluster centers across flat rows. The Rk-means algorithm, introduced by Curtin et al., builds a "grid coreset" (a small, weighted summary of the data) directly from individual normalized tables. This achieves massive memory savings while maintaining provable theoretical guarantees on clustering quality. Chen et al. similarly demonstrated that coresets can be constructed for relational data to scale support vector machines (SVMs) without join materialization.
- Regression: By utilizing sketching and sampling techniques, Jayaram et al. showed that high-accuracy linear regression can be performed in "input-sparsity time." This means the algorithm's runtime depends strictly on the size of the original, small relational tables rather than the astronomical size of the joined result.
Joint Distribution and Density Estimation
The paradigm also applies to learning probabilistic models over databases. Instead of denormalizing tables to learn joint distributions, frameworks like NeuroCard (Yang et al.) and FactorJoin (Wu et al.) treat the database schema as a factor graph or use deep autoregressive models combined with join sampling. This allows them to accurately estimate query cardinalities and correlations across dozens of tables simultaneously without explicit materialization.
Why It Works: A Paradigm Shift
In-database factorized learning works because it exploits the structural properties of relational data—such as functional dependencies and schema topology—to optimize mathematical computations.
| Feature | Traditional ML Pipeline | In-Database Factorized Learning |
|---|---|---|
| Data State | Denormalized & Flattened | Normalized & Distributed |
| Memory Footprint | Exponential ($O(\prod \text{Tables})$) | Linear ($O(\sum \text{Tables})$) |
| Redundancy | High (Row duplication) | Zero (Maintains database normalization) |
| Computation Time | Bound by Join Materialization | Bound by Input Sparsity |
By shifting the workflow from "extract, join, and train" to "factorize and compute in-database," this research direction eliminates the storage and memory walls that have long plagued multi-table analytics. It proves that the structure of a database is not an obstacle to machine learning, but rather an asset that can be leveraged for faster, more efficient computation.
Key Foundational Work
Efficiently Instantiating View-Objects From Remote Relational Databases (1994) — contributed 1 concept elements to this direction.
Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases (1994) — contributed 1 concept elements to this direction.
Knowledge Discovery in Databases: An Attribute-Oriented Approach (1992) — contributed 1 concept elements to this direction.