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.