3 ms·
Do we mean different things by "merge join" and "nested loop join" ? For me "merge join" is O(n) (but requires the data to be sorted by key) whereas "nested loo
by School-Cotton 4y ago
Do we mean different things by "merge join" and "nested loop join" ? For me "merge join" is O(n) (but requires the data to be sorted by key) whereas "nested loop join" is O(n^2).
- mountainreason 4y agoWouldn't you at least be looking at nlog(n) for the sort in the merge join?
- School-Cotton 4y agoYes, if the data is not already sorted. Thus it's O(n) for already sorted data and O(n log(n) + n) -- which simplifies to O(n log(n)) -- for arbitrary data.
- mountainreason 4y agoYeah. I know. Why would the data already be sorted?
- School-Cotton 4y agoIn a database you might have already built an index on that data.