Does join take O(M+N) time complexity? and does sub-querytake O(M*N)?
Am I wrong to think this way?
Yes, with respect, you are wrong to think this way. SQL is declarative. You use it to state the result you want, and the server figures out the best way to deliver that result -- to satisfy your query -- based on available indexes and data structures.
Thousands of years -- really! -- of developer effort have gone into figuring out all sorts of algorithms, optimizations, and hacks to reduce the complexity of the processes the servers use to satisfy queries.
As the thousands of years of experience accumulate the performance distinction between correlated subqueries and join queries gets less important.
Your thinking is wrong for a specific reason: you are thinking procedurally, not declaratively. When you assert that a particular type of query can be satisfied in, for example, O(m*n)
time, you are making assumptions about procedures used to satisfy it. Generations of developers have been dedicated to making your assumptions wrong.
Certainly it's possible to create tables, indexes, and queries with pathological performance characteristics. It happens all the time. But somebody fixes an index and the problem is solved.