MySQL using a multi-column index even when the first column isn't being queried

Question

I have MySQL version 8.0.37.

From what I understand about a multi-column index in this version, it will be used by MySQL ONLY if the query contains a subset of all the columns, starting from the first.

For ex, I have this index in my InnoDB table

mysql> show indexes from my_table;
+------------------------+------------+------------------------------------------------------------+--------------+-----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table    | Non_unique | Key_name                        | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+------------------------+------------+------------------------------------------------------------+--------------+-----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| my_table |          0 | PRIMARY                         |            1 | id          | A         |       32643 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| my_table |          1 | my_table_entity_id              |            1 | entity_id   | A         |       20160 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| my_table |          1 | my_table_entity_id_sub_id_value |            1 | entity_id   | A         |       18222 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| my_table |          1 | my_table_entity_id_sub_id_value |            2 | sub_id      | A         |       32985 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| my_table |          1 | my_table_entity_id_sub_id_value |            3 | value       | A         |       32545 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+------------------------+------------+------------------------------------------------------------+--------------+-----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+

With my_table_entity_id_sub_id_value index, I can run queries over entity_id, or both entity_id and sub_id or all the 3 columns. This is also what the MySQL documentation says.

However, this is the explain analyze output of a query over only the 2nd and 3rd columns, i.e., sub_id and value, and still the index is being used.

mysql> explain analyze select distinct entity_id from my_table where sub_id = 107 and value  = 'd90e7a26-2fc5-4e16-87c5-a2e9da5a26f7';
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Group (no aggregates)  (cost=3552 rows=330) (actual time=3.52..14.7 rows=3103 loops=1)
    -> Filter: ((my_table.`value` = 'd90e7a26-2fc5-4e16-87c5-a2e9da5a26f7') and (my_table.sub_id = 107))  (cost=3519 rows=330) (actual time=3.44..14.3 rows=3103 loops=1)
        -> Covering index scan on my_table using my_table_entity_id_sub_id_value  (cost=3519 rows=32985) (actual time=0.0741..10.4 rows=33202 loops=1)
 |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.39 sec)

I realise it's a "covering index" scan. What I understand about them is that they're used for retrieving values directly from the index, so I understand entity_id which I'm selecting is in that index. However, the where is still over only the 2nd and 3rd columns, and that is the filtration criteria.

Am I missing something here? What am I not understanding about covering index scans?

Answer 1

Because your query does not reference the left-most column of the index, it executes a covering index scan, which means that although it is able to read from the index alone, it must read every entry in that index.

If you were to include the left-most column of the index in the query conditions, you get an index lookup, which allows the query to examine only the entries that match.

mysql> explain analyze select distinct entity_id from my_table where entity_id = 123 and sub_id = 107 and value  = 'd90e7a26-2fc5-4e16-87c5-a2e9da5a26f7'\G

*************************** 1. row ***************************
EXPLAIN: -> Group (no aggregates)  (cost=0.45 rows=1) (actual time=0.0187..0.0187 rows=0 loops=1)
    -> Filter: ((my_table.sub_id = 107) and (my_table.`value` = 0))  (cost=0.35 rows=1) (actual time=0.0177..0.0177 rows=0 loops=1)
        -> Index lookup on my_table using entity_id (entity_id=123)  (cost=0.35 rows=1) (actual time=0.017..0.017 rows=0 loops=1)
                 ^^^^^^

Answer 2

"Covering" (aka "Using index") means that all the columns are found in a single INDEX. This avoids the back and forth between then index BTree and the data BTree, which is a performance benefit.

The quote you found is incomplete. It mentions only the optimal situations where "covering" is beneficial. (See my 3rd bullet item below.)

I would expect the following:

• Look at every 'row' in the index ("Covering index scan")
• Not touch the data BTree.
• Check each index row for value = 'd90e7a26...' and sub_id = 107`
• Gather the entity_id values from the index BTree.
• Possibly it is realizing that the index is ordered by entity_id, and hence can avoid a de-dup pass. But I cannot read the Explain well enough to deduce that.

Tips:

• INDEX(entity_id) is redundant with the other index and can be removed.

• If the pair entity_id, sub_id is unique and you have no use for id other than being the PK, then get rid of id and have PRIMARY KEY(entity_id, sub_id)

• The following would be faster for your query:

  `INDEX(sub_id, value,  -- either order
         entity_id)      -- last
  

Answer 3

It is doing a covering index scan. Per the docs:

In some cases, a query can be optimized to retrieve values without consulting the data rows. (An index that provides all the necessary results for a query is called a covering index.) If a query uses from a table only columns that are included in some index, the selected values can be retrieved from the index tree for greater speed

Your query uses only columns in that index. The optimizer must have concluded that using that index and doing a scan was faster than using one of the other indexes to do a lookup and then doing reads directly into the full data rows. I cannot be sure why this is the case. Certainly if you had an index that started with sub_id and value but included entity_id as well that would be used instead and a lookup would have been done instead of a scan.

But think about the case where your table has very large rows. Say 100 various columns and a few large strings or binary data. Say it nears the maximum row size of 64k, and your index only takes 32 bytes per row. And guessing from your output, there are 33,000 total rows and 330 rows or 1% matching your criteria. Say there are also different matches of sub_id and value, so that sub_id 107 has 10 different value values associated with it for 800 total rows and the single value you specified has 4 different sub_id values associated with it for 500 total rows.

If doing the lookup using the index on sub_id, it will find 800 rows it needs to check. What you get is a list of the rows and how to access them on disk. It would then load all the data for those 800 rows because it needs more data than the index contains. These rows could be spread out on disk since that index is not clustered, and if they are each 60k then each would involve reading multiple sectors, a total of 48mb of data. It then has to check on each value to filter based on the other criteria and capture the unique entity_id values.
These operations are not very friendly to the CPU cache because the data is spread out. Future queries using different values for sub_id and value will access hundreds of other areas on disk and take another 48mb. This instance isn't that bad because the numbers are low, but in a larger system that could end up being a lot of data and not very good cache-wise.

If doing a scan using the index that contains all the data, it has to load the entire index. That's 33,000 rows instead of just 800, but each row is much smaller, maybe just 32 bytes. That's just 1mb it has to read from disk and probably in more like 250 reads instead of 13,000. It's easy to cache 1mb and scanning those 33,000 rows for the data you need isn't hard on the CPU.

Here's an imperfect analogy. Imagine you have files on 33,000 people employed by your company. The primary key is EmployeeID. The employee file has a lot of data including address, phone numbers, dates for employment events, social security numbers, biometric data, etc. Each employee file takes up a whole page, and they are stored in filing cabinets ordered by EmployeeID for easy access (the primary key).

You are tasked with finding the unique LastName of employees with blue eyes. You have two other filing cabinets. Cabinet A has lists of employees organized by eye color. This list simply contains EyeColor and EmployeeId. It's very fast to find the EmployeeId values you are looking for, but for each one you have to then go to the main file cabinet and pull the employee's file and get the LastName from there. Cabinet B has lists of employees organized by last name, but each line has LastName, EyeColor, and EmployeeId. You can fit about 120 of these records on each page. To perform your task you have to pull out the entire file with 275 pages, but you don't have to look at anything else. You can just scan each page and look for EyeColor = 'blue' and record the last name because it is right there. No running over to the main filing cabinet to pull each file.

Answer 4

A database can actually make use of the indexes as specified for an index query, and it may improve performance. I'm not sure if mysql will do this for you.

The trick is to use one index access to enumerate all possible values of entity_id, and a second (or at least one that one interfere with the first), on my_table_entity_id_sub_id_value, to check if the triplet is in your table. This will save time if there are few enough values of entity_id that the index lookups are faster than the full index scan. Because of your redundant index on entity_id, this information should be available.

You might be able to force this behavior with something like:

select distinct entity_id from my_table 
        where sub_id = 107 
        and value  = 'd90e7a26-2fc5-4e16-87c5-a2e9da5a26f7' 
        and entity_id in (select distinct entity_id from my_table);

You might need to cache the inner select...