Exact Selectivity Computation (ESC) for In-Memory 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. Our approach interacts with the query execution engine, while the synopses-driven solution only accesses the system catalog. The optimizer instructs the execution engine to first perform selectivity sub-queries in order to compute the cardinality of selection predicates exactly. These values are used together with the cardinalities of the base tables to compute the best join order in the optimal query plan. Moreover, the results of the selectivity sub-queries are temporarily materialized and reused in the optimal execution plan. This avoids re-executing the selections during the complete query execution. In order to make the process efficient, we propose optimizations targeting the selection of tables and predicates to which ESC is applied. While it is clear that the plan computed by ESC is better, the impact on query execution time depends on the ratio between the execution time for the selectivity sub-query and the original plan. The assumption we make is that the sub-query execution is relatively negligible - valid for in-memory databases. We consider two cases. First, if the new query plan is improved by a larger margin than the sub-query time, the total execution time is reduced. We argue that exact selectivities are likely to achieve this for queries over many tables and with complex predicates. In the second case, the optimal query plan, i.e., join order, does not change even when selectivities are exact. Materialization minimizes the overhead incurred by the sub-query through subsequent reuse further up in the plan.

Our contributions can be summarized as follows:

The results are published in the following papers:
  1. Exact Selectivity Computation for Modern In-Memory Database Query Optimization by J.H. Shin, F. Rusu, and A. Suhan
  2. Selectivity Computation for In-Memory Query Optimization by J.H. Shin, F. Rusu, and A. Suhan
  3. Novel Selectivity Estimation Strategy for Modern DBMS by J.H. Shin

UC Merced | EECS | Home | Query Optimization

Last updated: Friday, July 26, 2019