Big-Oh Performance of an Inner Join on Two Indexes

Question

I am trying to figure out the Big-Oh performance of the following query:

SELECT * 
FROM table1 INNER JOIN table2 ON table1.a = table2.b
GROUP BY table1.a

table1.a is the primary key of the table. table2.b has a non-unique index on it.

My thought is since each index can be searched in O(log n), then this query performs in O(log n * log m) where n is the number of rows in table 1 and m is the number of rows in table 2.

Any input would be appreciated.

Answer 1

Your thinking is a bit off. An index can be searched in O(log n) for a single lookup. Your query would presumably be doing "n" or "m" of these.

Let me assume that the query processes by joining the two tables together by scanning one table and looking up the values in the other. It then does sort-based aggregation for the order by.

The "matching" piece of the query is then the larger of:

• O(n log m)
• O(m log n)

This assumes that the query engine decides to scan one table and look up values in the index in the other.

To continue, once you look up values, you need to fetch the data in the pages for the table where you used the index. Fetching data is technically O(n). Our estimate so far is O((n log m) + n + ).

The aggregation should be O(n log n) for a sort followed by a scan. But, how many records do you have for the aggregation? You could have as many as n*m matches to the join. Or, as few as 0 (it is an inner join).

This is big-O, which is an upper bound. So, we have to use the bigger estimate. This results in O((n*m)log(n*m)) for the aggregation, which would dominate other terms. The big-O would be O((n*m) log(n*m)).

Answer 2

The performance of the query depends on how the SQL statement is executed internally.

Maybe you could look into EXPLAIN (for MySQL: http://dev.mysql.com/doc/refman/5.1/en/explain.html) here to get more info on how your query gets executed as this could yield more accurate results than looking at Big-Oh.

Btw: Gordon Linoff's answer looks good if you're really looking for Big-Oh!