  Worst-case optimal join algorithms have gained a lot of attention in the
database literature. We now count with several algorithms that are optimal in
the worst case, and many of them have been implemented and validated in
practice. However, the implementation of these algorithms often requires an
enhanced indexing structure: to achieve optimality we either need to build
completely new indexes, or we must populate the database with several
instantiations of indexes such as B$+$-trees. Either way, this means spending
an extra amount of storage space that may be non-negligible.
  We show that optimal algorithms can be obtained directly from a
representation that regards the relations as point sets in variable-dimensional
grids, without the need of extra storage. Our representation is a compact quad
tree for the static indexes, and a dynamic quadtree sharing subtrees (which we
dub a qdag) for intermediate results. We develop a compositional algorithm to
process full join queries under this representation, and show that the running
time of this algorithm is worst-case optimal in data complexity. Remarkably, we
can extend our framework to evaluate more expressive queries from relational
algebra by introducing a lazy version of qdags (lqdags). Once again, we can
show that the running time of our algorithms is worst-case optimal.
