[Solved] SQL Query Performance (Complexity Analysis?)

EverSQL Database Performance Knowledge Base

SQL Query Performance (Complexity Analysis?)


Hello, I am wondering if anyone has a good perspective of the complexities of SQL queries. I would find it particularly helpful if you can phrase queries similar to algorithms Big O notation (if this is not ideal or possible an explanation would be appreciated!) Here is an example of two queries, the second having a particularly higher complexity. Although, my naive view of SQL Performance is confused by that as it seemingly should mean fewer comparisons between the two tables, and fewer comparisons == higher performance.

Query 1

SELECT DISTINCT m.Title, m.movieId
FROM Categorizes c, Movies m
WHERE m.movieId = c.movieId AND c.genre = '<user_input>'

Query 2

SELECT DISTINCT m.Title, m.movieId
FROM (SELECT movieId FROM Categorizes WHERE c.genre ='<user_input>') c, 
     Movies m
WHERE c.movieId = m.movieId

My perspective

This tells me since we only are comparing the movies across the tables that have the genre we want, inherently we are making fewer comparisons (assuming not all movies contain the genre we are filtering by). Analyzing this in Complexity Analysis notation we should see. Subquery time O(n), n the length of the genre table. The WHERE statement must loop through each iteration of the table and see if it is a match for each iteration in the other table, therefore, O(nm) time, given m the length of the movie table. In Query one, we see the same definition, minus the subquery, but adding the genre comparison to the where. Now we Are comparing two tables O(nm) such that n is strictly larger in query1 than query2. Although, query2's execution time is around 100 times slower in the application.


Since my logic is proven wrong, what am I missing? Where am I wrong? How do you look at SQL performance? Can you apply Complexity Analysis to Query Performance?

Thank you!

How to optimize this SQL query?

The following recommendations will help you in your SQL tuning process.
You'll find 3 sections below:

  1. Description of the steps you can take to speed up the query.
  2. The optimal indexes for this query, which you can copy and create in your database.
  3. An automatically re-written query you can copy and execute in your database.
The optimization process and recommendations:
  1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.
Optimal indexes for this query:
ALTER TABLE `Categorizes` ADD INDEX `categorizes_idx_genre_movieid` (`genre`,`movieId`);
ALTER TABLE `Movies` ADD INDEX `movies_idx_movieid` (`movieId`);
The optimized query:
        DISTINCT m.Title,
        Categorizes c,
        Movies m 
        m.movieId = c.movieId 
        AND c.genre = ''

Related Articles

* original question posted on StackOverflow here.