Exploitation of Uniqueness Properties for the Optimization of SQL Queries Using a 1-Tuple Condition

In a SELECT-FROM-WHERE query, a 1-tuple condition refers to the situation where it can be proven that at most one tuple will be returned upon evaluation of the query. This information ca be exploited in various query optimization techniques in both the query rewrite and plan generation phases. For example, the 1-tuple condition can be exploited in a query rewrite technique which allows us to convert a scalar subquery into a join. It can also be utilized in a technique which results in the avoidance of unnecessary duplicate elimination when DISTINCT is specified on the select clause. These optimization techniques can result in significantly improved query performance. The performance improvement can sometimes be measured in orders of magnitude. In this paper, we present an algorithm for detecting a 1-tuple condition during query compilation. This algorithm has been generalized so that it can also be used to determine if a set of columns form a unique key for a select-where-from query. We give examples of its use in two query optimization techniques.