Query Optimization in Relational Database Systems - Automated Physical Database Design and Tuning - page 26

intersected list of RIDs can be much smaller than either of the original lists,
and thus much fewer RID lookups are needed, and (3) if the predicates use
equalities, specialized intersection algorithms can be used that return RIDs
in order of the clustered index, which accelerates subsequent lookups.
In general, we can intersect several indexes to answer complex single-table
predicates, although at some point the benefit from additional index intersec-
tions is outweighed by its cost. Additionally, there are analogous strategies to
handle disjunctive predicates using RID unions, and negation predicates using
RID differences or two seek operations (e.g., employees who are not engineers).
Considering these alternatives certainly increases the search space consider-
ably, so some optimizers use heuristics (similar to those for join reordering)
to limit the number of such alternatives.
2.1.3 Query Decorrelation
Suppose that table Dept has a column ContactId , which corresponds to the
employee, in table Emp that is the contact for each department in Dept . Con-
sider the following SQL query that obtains the employees who are the contacts
for the departments they work in (we add column ContactId to the schema
of the Dept table):
SELECT Emp.Name
FROM Emp
WHERE Emp.DeptId IN ( SELECT Dept.DId
FROM Dept
WHERE Emp.EId = Dept.ContactId )
The traditional strategy to process this query would evaluate the inner
subquery for each tuple of table Emp in the outer query block (this is sometimes
called tuple iteration semantics ). An obvious optimization applies when the
inner subquery references no variables from the outer query block. In such
cases, the inner query block can be evaluated only once. Instead, if the inner
subquery mentions a variable from the outer query block, we say that the
query blocks are correlated . For example, in the previous query, Emp.EId acts
as the correlated variable in the inner query block. Much work in the literature
has identified techniques to decorrelate (or unnest ) such correlated nested
queries by “flattening” them into a single-block alternative. For example, since
Dept.Did is unique for each department, the nested query is equivalent to the
following alternative that does not use subqueries:
SELECT E.Name
FROM Emp E, Dept D
WHERE E.DeptId = D.DeptId
AND E.EmpId = D.ContactId
The complexity of the unnesting problem depends on the structure of the
query (e.g., whether the nested subquery has aggregates). The simplest case, of