# Optimizing a join where each table has a selection

Consider the following query:

SELECT Customer.Name FROM Customer
INNER JOIN Order on Order.CustomerId = Customer.Id
WHERE Customer.Preferred = True AND
Order.Complete = False


Let's suppose all of the relevant attributes (Customer.Preferred, Order.Complete, Order.CustomerId and Customer.Id) are indexed. How can I evaluate this as quickly as possible?

Standard optimization advice would say that I should do the select on each table first, then the join using sort-merge or whatever the cardinality would imply. But this involves two passes through the data - I'm wondering if there's a better way.

EDIT: I think asking if there was a "better way" was too ill-defined. Suppose we are trying to find $\sigma_a(A)\bowtie_j\sigma_b(B)$. Observe that we can find this in $O(\alpha)$ (where $\alpha$ is the cardinality of $\sigma_a(A)$) with the following pseudocode:

for each a in A:
find foreign tuple in B  // constant-time, if using hash table
check if foreign tuple meets foreign constraint  // again, constant time


As mentioned by some answerers, there are various minor permutations (do the for loop over B instead, etc.). But they all seem to be $O(\alpha)$ or $O(\beta)$. Is there a better way?

Note that if it the query were a self join, we could just do the merge part of a sort-merge join, (since our indexes would already be sorted) which would run in time proportional to the number of results. So I ask if a similar thing can be done here.

I am more than happy to accept a proof that there is no better method as an answer. I believe that there is no faster algorithm, but I'm unable to prove it.

• You mean if you were implementing the database? Or how to write the SQL more efficiently? – svick May 21 '12 at 22:22
• @svick: I am writing the (query optimizer for) the database. – Xodarap May 22 '12 at 1:42

When an SQL statement is turned into an execution plan, several optimization techniques are used. The use of indices allow to efficiently (without a full scan) select tuples that agree with a selection condition. Another technique in use is semantic optimization, id est, to turn a query into an equivalent one with better behaviour. To do so, identities of relational algebra are used.

For specifically, in the example, the identity between selection and product

$\qquad \displaystyle \sigma_{\alpha}(C \times O) = \sigma_{\beta \wedge \gamma \wedge \delta}(R \times P) = \sigma_{\delta}(\sigma_{\beta}(R) \times \sigma_{\gamma}(P))$

(with $\beta$ being the part of the condition $\alpha$ which refers only to attributes from $C$ and $\gamma$ the one with attributes from $O$) can be used. Informally worded this identity is "pushing selection through joins/product" (the identity holding for join too). The identity can be thought as a kind of rewrite rule, reading it from left to right. So the following identity holds in the example :

\qquad \displaystyle \begin{align} &\pi_{Name}(\sigma_{Preferred=True \wedge Complete=False}(C \Join_{CustomerId = Id} O)) \\ = &\pi_{Name}(\sigma_{Preferred=True}(C) \Join_{CustomerId = Id} \sigma_{Complete=False}(O)) \end{align}

Doing so, you do not waste time computing the product of irrelevant tuples of $C$ and $O$. The more selective the $\beta$ and $\gamma$ predicates are, the larger the gain is. And IMO, I don't think you can ever lose some time using this rule. For a more formal treatment of this aspect of optimization, one can look at the Static Analysis and Optimization chapter of the Foundation of Databases book.

• Isn't this just my statement "do the select on each table first, then the join" rewritten in relational algebra? Thank you for the link though, I will see if something in there can help. – Xodarap May 23 '12 at 15:09
• By the way, I think you can lose time with this rewrite (even though it's a good idea in general). Consider the case when the join is indexed and restrictive, and the selects are neither. – Xodarap May 23 '12 at 15:11
• I agree that the relational algebra is a re-statement of your question. Actually, i don't understand precisely how index-based is "weaved" with algebra-based optimization in the query planner. Anyway, the algebra-based approach is generic, but the index-based one is not, because it needs pre-defined indices (at schema definition time). When such ones are available, is it always worth to use algebra-based optim. ? I don't know yet. I'd ask some of my colleagues :) – Romuald May 24 '12 at 8:59

There are different schools of thought. The prevailing wisdom, originated with System R, is calculate cost of every execution strategy and select the minimal one. This leaves you at the mercy of optimizer calculating/guessing statistics and costing everything properly. Some people believe that this is almost never done reliably for any query of moderate complexity. Even in your simple case, there is overwhelming number of possible execution scenarios:

1. Perform single table predicate selection (indexed or not) on Customer.Preferred = True first, then join with Order.

2. Perform single table predicate selection on Order.Complete = True first, then join with Customer.

Then there are 3 types of join, and even more if we take into account indexed nested loops leveraging different compound indexes.

Hence, heuristics like you suggest: "apply single table predicate first, then join". One can argue that heuristics, failing to deliver optimal plan, would, at least, guarantee some "good enough" solution. In your particular case an execution plan that leverages Indexed Nested loops is certainly be not the worst. Please keep in mind, that unless you leverage compound index, such as (Order.Complete, Order.CustomerId) when joining with Order table, you would have to apply single table predicate on it the last.

• Thanks, I realize that I can apply each of the predicates using various methods individually, but I'm wondering if there's a more clever way (which would e.g. require only one pass through the data). – Xodarap Jun 11 '12 at 4:38