Maybe I am missing something but I think O(N * N) is the correct complexity for a nested loop implementation. If you believe that is wrong, can you explain a bit more?
Well that assumes the same cardinality for both sides of the join, which may be far from the case, especially if selections can be pushed down to scans.
Comments
Maybe I am missing something but I think O(N * N) is the correct complexity for a nested loop implementation. If you believe that is wrong, can you explain a bit more?
Well that assumes the same cardinality for both sides of the join, which may be far from the case, especially if selections can be pushed down to scans.
Pretty sure nested loops are O(^2).