View article

Query optimization, and in particular the problem of join ordering, has a huge impact on the performance of database systems. Accordingly, it has been widely studied in the literature, but there is a, perhaps surprising, gap between techniques that have been proposed in venues like PODS and the techniques that are used in typical systems. There are several reasons for that, but one of them is that many theoretical approaches look at asymptotic complexity, while systems tends to primarily care about the performance of a query for a given database instance in absolute terms. This tutorial looks at the differences and tries to bring both worlds closer together.