Factorized Analytics to Avoid Relational Join Explosion

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 251 papers58 conceptsfrozen 2026-10-04

In modern data science, there is a fundamental friction between how data is stored and how it is analyzed. Databases are normalized: they store information across multiple tables (Users, Orders, Products) to minimize redundancy. However, machine learning models and analytical tools typically require a denormalized view: a single, flat "design matrix" where every observation is a row and every feature is a column.

The standard bridge between these two worlds is the relational join. But as Yuyan Wang describes in Relational Algorithms for k-means Clustering, this bridge often leads to a Join Trap. When you join multiple tables with many-to-many relationships, the resulting dataset can be exponentially larger than the input tables—a phenomenon known as "join explosion."

Factorized analytics is a research direction dedicated to performing complex computations—regression, clustering, and logic induction—directly on the normalized tables, bypassing the need to ever materialize the massive joined result.

The Intuition: Computation over Structure

To understand why we can avoid the join, consider a simple aggregate query like a sum. If you want to calculate the total revenue from a join of Orders and Products, you don't need to create a new table where every order row is physically glued to a product row. You can instead sum the products of prices and quantities directly.

This "distributive" property is the core intuition behind factorized learning. Matthias Lanzinger, Alexander Selzer, and Reinhard Pichler demonstrate this in Avoiding Materialisation for Guarded Aggregate Queries by propagating tuple frequencies up a join tree. Instead of duplicating data, they treat the join as a virtual structure and pass only the necessary statistics through it.

By treating the database schema as a "factorization" of the larger design matrix, researchers like Rihan Hai and Wenbo Sun have developed frameworks like Ilargi (Ilargi: a GPU Compatible Factorized ML Model Training Framework). Ilargi represents the relationships between tables as sparse matrices, allowing machine learning models to be trained on GPUs without the data movement bottlenecks caused by flattening.

In-Database Machine Learning

The most significant impact of this approach is in "In-Database" machine learning. Traditionally, data must be exported from a database to a tool like Scikit-learn. If the join is too large, this export fails.

Researchers have solved this by redesigning specific algorithms to be "join-aware":

  • Linear Regression: Rajesh Jayaram and colleagues in In-Database Regression in Input Sparsity Time show that you can compute high-accuracy regressions in time proportional to the size of the original small tables, rather than the astronomical size of the joined result.
  • Functional Aggregate Queries (FAQ): Mahmoud Abo Khamis, Dan Olteanu, and others developed the FAQ-AI framework (Functional Aggregate Queries with Additive Inequalities). This framework uses geometric data structures to solve queries involving inequalities (like $x + y \le z$) asymptotically faster than traditional join-based methods.
  • Clustering: As noted by Yuyan Wang, k-means can be performed by calculating centroids using aggregates that are computed over the join tree, avoiding the "Join Trap" entirely.

Sampling and Sketching the Join

When an exact answer isn't required, or the query is too complex for pure factorization, researchers use sampling over joins. The challenge here is that you cannot simply sample the input tables; a uniform sample of Users does not result in a uniform sample of the Users JOIN Orders result.

To solve this, Graham Cormode and his team in Weighted Random Sampling over Joins use weight-based techniques to prioritize records. Similarly, Aryan Esmailpour and Xiao Hu introduced algorithms for subset sampling (Subset Sampling over Joins) that achieve near-optimal complexity by using specialized indexing to "see" the join's distribution without building it.

Beyond Performance: Privacy and Logic

The benefits of avoiding materialization extend beyond speed. In Classification Spanning Private Databases, Ke Wang and Philip S. Yu demonstrate that factorized approaches allow for building decision trees across private databases. Because the data is never joined into a single table, sensitive information remains localized while the model learns from the global relationships.

Furthermore, in the realm of formal logic, Jonni Virtema and colleagues argue in Polyteam Semantics that reducing multi-table structures to a single table via Cartesian products is fundamentally inefficient. They propose reasoning directly on multi-relational structures, bridging the gap between database theory and complex logical dependencies.

Summary

The "Join Explosion" is a self-inflicted wound of traditional data pipelines. By recognizing that the information in a join is already implicitly present in the normalized tables, factorized analytics allows us to scale machine learning and complex reasoning to datasets that would otherwise be physically impossible to process. As Michael Stonebraker argued in One Size Fits All?, specialized architectures that respect the underlying structure of data will always outperform generic "flat" approaches.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 33 papers
  2. Version 1 · 2026-10-04 · 51 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_relational_join_explosion_fa26ced2,
  title = {relational join explosion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-join-explosion/rdr_fa26ced29fa44bd599ae848daaae3b8f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_factorized_analytics_to_avoid_relational_fa26ced2_v1,
  title = {Factorized Analytics to Avoid Relational Join Explosion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/factorized-analytics-to-avoid-relational-join-explosion/rdr_fa26ced29fa44bd599ae848daaae3b8f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}