  We transform join ordering into a mixed integer linear program (MILP). This
allows to address query optimization by mature MILP solver implementations that
have evolved over decades and steadily improved their performance. They offer
features such as anytime optimization and parallel search that are highly
relevant for query optimization.
  We present a MILP formulation for searching left-deep query plans. We use
sets of binary variables to represent join operands and intermediate results,
operator implementation choices or the presence of interesting orders. Linear
constraints restrict value assignments to the ones representing valid query
plans. We approximate the cost of scan and join operations via linear
functions, allowing to increase approximation precision up to arbitrary
degrees. Our experimental results are encouraging: we are able to find optimal
plans for joins between 60 tables; a query size that is beyond the capabilities
of prior exhaustive query optimization methods.
