  Cost-based query optimizers remain one of the most important components of
database management systems for analytic workloads. Though modern optimizers
select plans close to optimal performance in the common case, a small number of
queries are an order of magnitude slower than they could be. In this paper we
investigate why this is still the case, despite decades of improvements to cost
models, plan enumeration, and cardinality estimation. We demonstrate why we
believe that a re-optimization mechanism is likely the most cost-effective way
to improve end-to-end query performance. We find that even a simple
re-optimization scheme can improve the latency of many poorly performing
queries. We demonstrate that re-optimization improves the end-to-end latency of
the top 20 longest running queries in the Join Order Benchmark by 27%,
realizing most of the benefit of perfect cardinality estimation.
