Optimizing complex queries with multiple relational instances

Abstract

It is not uncommon that analytical database queries contain multiple instances of the same (base or derived) relation. Unfortunately, almost all of the conventional relational query processing techniques are oblivious to these instances and instead deal with them as independent relations. As a result, the query evaluation performance would be suboptimal.

This thesis describes our research on the problem of optimizing complex queries with multiple relational instances, which surprisingly has never received systematic or specialized public studies in the past. We investigate three fundamental query execution operations, i.e., table scan, table sorting and table join, to exploit the corresponding optimization opportunities when these operations involve multiple instances. First, we present a light-weight multi-instance-aware plan evaluation engine that enables multiple instances of a relation to share one physical table scan. Second, we develop a sort-sharing-aware query processing framework to maximize the effects of sharing and collaboration during achieving different sorting requirements for multiple instances. Third, we propose an efficient algorithm for performing self-join operations between two instances and with join predicates involving two distinct attributes.