Adaptive and Robust Query Processing with SHARP

Abstract

Database catalogs often do not contain enough statistical information to correctly cost all possible physi-cal plans. In their absence, the optimizer can produce incorrect estimates and select suboptimal plans for execution. To address this problem for a subclass of queries, we propose SHARP, a new multijoin, adaptive, relational operator that joins three or more relations of a star-join. SHARP reduces the possible impact of optimizer mistakes by determining which plan to execute independently of optimization estimates. During normal query processing, SHARP collects statistics, and by using a combination of late-binding plan decisions and tuple routing strategies, it is able to change join order and table access methods. However, unlike previous tuple routing operators used for in memory stream processing, SHARP was designed to process local relations with sizes much larger than available memory. We have implemented SHARP in the open-source DBMS Predator, and we present an extensive experimental evaluation showing the significant performance benefits of SHARP.