Consider the following query:SELECT Customer.Name FROM CustomerINNER JOIN Order on Order.CustomerId = Customer.IdWHERE Customer.Preferred = True AND      Order.Complete = FalseLet'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 timeAs 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.
Optimizing a join where each table has a selection
optimization;database theory;relational algebra;databases