Exact Selectivity Computation for Modern In-Memory Database Query Optimization

Jun Hyung Shin, Florin Rusu, Alex Suhan
University of California Merced
arXiv:1901.01488 [cs.DB], (6 Jan 2019)


   title={Exact Selectivity Computation for Modern In-Memory Database Query Optimization},

   author={Shin, Jun Hyung and Rusu, Florin and Suhan, Alex},






Download Download (PDF)   View View   Source Source   Source codes Source codes



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 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.
No votes yet.
Please wait...

You must be logged in to post a comment.

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: