A Simple Algorithm for Worst-Case Optimal Join and Sampling

Florent Capelli, Oliver Irwin, Sylvain Salvati

We present an elementary branch and bound algorithm with a simple analysis of why it achieves worstcase optimality for join queries on classes of databases defined respectively by…