  Selectivity estimation remains a critical task in query optimization even
after decades of research and industrial development. Optimizers rely on
accurate selectivities when generating execution plans. They maintain a large
range of statistical synopses for efficiently estimating selectivities.
Nonetheless, small errors -- propagated exponentially -- can lead to severely
sub-optimal plans---especially, for complex predicates. Database systems for
modern computing architectures rely on extensive in-memory processing supported
by massive multithread parallelism and vectorized instructions. However, they
maintain the same synopses approach to query optimization as traditional
disk-based databases. We introduce a novel query optimization paradigm for
in-memory and GPU-accelerated databases based on \textit{exact selectivity
computation (ESC)}. The central idea in ESC is to compute selectivities exactly
through queries during query optimization. In order to make the process
efficient, we propose several optimizations targeting the selection and
materialization of tables and predicates to which ESC is applied. We implement
ESC in the MapD open-source database system. Experiments on the TPC-H and SSB
benchmarks show that ESC records constant and less than 30 milliseconds
overhead when running on GPU and generates improved query execution plans that
are as much as 32X faster.
