Re:Learn SQL, dammit
by michaelt on Wednesday May 08, 2013 @04:08PM
(#5676548)
Let's say your inner query returns n rows and wherever contains m rows. And your index is a B-tree, so you can hit it once in O(log m).
If you use a nested loop join, where you hit the index once for each inner query result, that's O(n*log m). If on the other hand you do a hash join, skipping the index but doing a full table scan of wherever, the complexity is O(m+n). So which is the faster choice depends on how many rows the inner query returns.
If you want to plan up front, before you know what m is, how would you decide which join to use?
If you use a nested loop join, where you hit the index once for each inner query result, that's O(n*log m). If on the other hand you do a hash join, skipping the index but doing a full table scan of wherever, the complexity is O(m+n). So which is the faster choice depends on how many rows the inner query returns.
If you want to plan up front, before you know what m is, how would you decide which join to use?