Sorting with multi-column indexes in MySQL

In a previous video, we discussed composite indexes, or indexes over multiple columns. We reviewed the various rules on when and how to use them, including the column order and access patterns. In this video, we'll dive into the topic of sorting using multi-column indexes and discuss how the same rules apply. We'll be using MySQL as our database management system.

Creating a composite index

As a quick refresher, let's start by creating a composite index over three columns: first name, last name, and birthday. Here's the SQL command to create the index:

SQL

ALTER TABLE people ADD INDEX composite_idx(first_name, last_name, birthday);

Note that the order of columns in the index matters. We cannot skip columns or read them out of order when creating or using the index.

Sorting with multi-column indexes

Now that we have our multi-column index set up, let's explore sorting with it. We'll use the SELECT statement and order by first name, then limit the output to the first ten entries:

SQL

SELECT 
 * 
FROM 
  people 
ORDER BY 
  first_name 
LIMIT 10;

We should see that the query executes without any file sorting. This is because the multi-column index allows the database to efficiently sort and retrieve the requested data.

Unlocking key parts for sorting

Let's say we want to sort by last_name but skip over first_name. According to our rules, this is not allowed. However, we can unlock the last_name key part for sorting by adding an equality condition on the first_name column. Here's the query:

SQL

SELECT 
  * 
FROM 
  people 
WHERE 
  first_name = 'John' 
ORDER BY 
  last_name;

The database can now use the unlocked last_name key part to sort the data. However, note that the birthday column is still locked behind the last_name key part and is not available for sorting or filtering.

Using all key parts for sorting

To use all three key parts of our index, we need to form a left prefix using the ordering in our query. We can do this by adding first_name back into our SELECT and WHERE clauses. Here's our new query:

SQL

SELECT 
  * 
FROM 
  people 
WHERE 
  first_name = 'John' 
ORDER BY 
  last_name, birthday;

Now we can sort by all three columns without file sorting. Once again, note that the order of columns in the index and query must match. Also, the id column is always appended to the end of the index but is subject to the same access rules.

Sorting direction and key parts

Finally, let's discuss sorting direction and how it relates to our multi-column indexes. We can sort each key part in ascending or descending order, but we must make sure that the ordering matches our query. If we sort one key part differently from our query, we may end up with file sorting.

Here are some examples:

If both key parts are sorted as ascending or descending, we get no file sort.
If one key part is sorted as ascending and the other as descending, we get a file sort.
If we swap the order of key parts in our index, we may get a backward index scan.

Remember that it's not the order of columns in the index that matters, but the relationship between them and the sorting direction in the query.

Conclusion

Sorting with multi-column indexes can be a powerful tool for improving database performance. It's important to follow the established rules on index creation and access patterns. By unlocking key parts and forming left prefixes, we can avoid file sorting and make use of all key parts in our index. Additionally, we must ensure that the sorting direction in our query matches the ordering of our key parts. With these techniques, we can take full advantage of multi-column indexes in MySQL.