  We present a simple geometric framework for the relational join. Using this
framework, we design an algorithm that achieves the fractional hypertree-width
bound, which generalizes classical and recent worst-case algorithmic results on
computing joins. In addition, we use our framework and the same algorithm to
show a series of what are colloquially known as beyond worst-case results. The
framework allows us to prove results for data stored in Btrees,
multidimensional data structures, and even multiple indices per table. A key
idea in our framework is formalizing the inference one does with an index as a
type of geometric resolution; transforming the algorithmic problem of computing
joins to a geometric problem. Our notion of geometric resolution can be viewed
as a geometric analog of logical resolution. In addition to the geometry and
logic connections, our algorithm can also be thought of as backtracking search
with memoization.
