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:
-
We introduce ESC as a novel paradigm to query optimization that is applicable independent of the predicate complexity and data distribution. ESC does not rely on any database synopses. It can be applied to any modern in-memory and GPU-accelerated database.
-
We implement ESC in the open-source MapD database with minimal changes to the query optimizer. The code is adopted by the MapD core engine.
-
We perform extensive experiments over the TPC-H and Star-Schema (SSB) benchmarks. The results 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 for queries with complex predicates.
The results are published in the following papers:
-
Exact Selectivity Computation for Modern In-Memory Database Query Optimization
by J.H. Shin, F. Rusu, and A. Suhan
-
Selectivity Computation for In-Memory Query Optimization
by J.H. Shin, F. Rusu, and A. Suhan
-
Novel Selectivity Estimation Strategy for Modern DBMS
by J.H. Shin
UC Merced |
EECS |
Home |
Query Optimization
Last updated: Friday, July 26, 2019