Split Theorems for Join Reporting and Sampling

The box-tree technique is an elegant and powerful tool for natural join processing. Recently developed by the database theory community, it yields simple algorithms and data structures for solving three fundamental problems - join reporting, small-delay enumeration, and join sampling - with performance matching the best known bounds, up to polylogarithmic factors. This article presents the technique's theoretical foundation in a form accessible to the broader database community. At the core of this foundation are the so-called split theorems, which uncover a combinatorial and intrinsically geometric structure underlying natural joins. Two versions of these theorems are proved using elementary, self-contained arguments.