Is there such thing as Index "hopping" in MySQL?

user_13668802 0
Viewed 62

Let's say we have an index on (A, B) and an index on (B, C). When doing a Query like:

SELECT * FROM table WHERE A = const AND B = const ORDER BY C DESC

Will the query optimizer first search in the (A,B) index to filter the rows for the WHERE class and then subsequently use the (B, C) index to sort quickly?

Or are queries restricted to one index? No B-tree hopping?

indexing database-design mysql sql database
3 Answers

No, MySQL does not do what you're describing.

It will do one of the following:

  • Read from the (A, B) index, which will use the index to examine only rows that match, but it requires extra work to do the filesort to sort the rows by C.

  • Read from the (B, C) index, which will read the rows in the correct order and therefore skip the filesort. But it will examine lots of extra rows that have values of A that don't match, and it will have to evaluate those rows one by one and discard those that don't match.

You can optimize for both by replacing the (A, B) index with an index on (A, B, C) this will both examine only the matching rows, and read them in the desired order, so no filesort is needed.

InnoDB always reads rows in some index order. Either a secondary index, or the clustered index.

Re your questions:

In general, MySQL only reads from one index per table reference. This allows for example queries with a self-join so there's more than one table reference for the same table. Each table reference might read using a different index.

For example, a self-join of managers to their employees:

SELECT ...
FROM employees AS m
JOIN employees AS e ON e.manager_id = m.id
WHERE m.hire_date = '2020-01-01'

In this example, it might use an index on hire_date to select the manager(s), and an index on manager_id for the managers' subordinates. These are two different table references, so they are read separately.

There's also a feature of MySQL called an index merge optimization, where it might read two subsets of the table, potentially using different indexes, and then merge the results using either union or intersection. But I find this doesn't happen as often as you might think it would.

Regarding ORDER BY DESC, https://dev.mysql.com/doc/refman/8.0/en/descending-indexes.html says:

previously, indexes could be scanned in reverse order but at a performance penalty.

In MySQL 8.0, they implemented support for declaring an index to be built in descending order, to support ORDER BY DESC queries. But then the index is tailored to those queries, and using the same index for ASC queries would suffer. So you might need to create both indexes on the same columns of the same table. Read the doc page I linked to for more details.

Bill_Karwin_208600

You can, of course, test on your data. But in my experience, the index is going to first match the where clause. So, it will match on the (A, B) index.

It will then perform a sort for the ordering.

user_11440350

You ask:

Will the query optimizer first search in the (A,B) index to filter the rows for the WHERE class?

Yes, MySQL will probably use the first index to retrieve the rows using an "Index Range Scan" with start & stop predicates, or an "Index Seek", if the predicate matches a UNIQUE constraint.

...and then subsequently use the (B, C) index to sort quickly?

Nope. This second index does not include the rows filtered using the first index. The engine will retrieve all rows (no pipelining anymore), sort them, and then will provide them to you. If there are many rows, this phase will be resource intensive and slow. Hopefully the filtering predicate results in few rows only.

user_64361910
Related