What is a "Loose Index Scan"?

I was reading that MySQL can not use an index on 2 range conditions due to not having a "loose index scan".

What exactly does "Loose Index Scan" mean?

From High Performance MySQL Third Edition,


Loose Index Scans
MySQL has historically been unable to do loose index scans, which scan noncontiguous ranges of an index. MySQL’s index scans generally require a defined start point and a defined end point in the index, even if only a few noncontiguous rows in the middle are really desired for the query. MySQL will scan the entire range of rows within these
end points.

A loose index scan is simply a scan that skips over part of the index. How does it do that? Assuming an index on (a,b) a loose index scan allows you to query for specific values of b without scanning all values of b. It does this by starting at the beginning of the range of b searching, and then skipping backward to find a new a. Compare this with a (tight) index scan where the whole index is scanned and there is no backtracking.

Backtracking in this context usually means moving up on a tree (back) to the previous position.


I was reading that MySQL can not use an index on 2 range conditions due to not having a "loose index scan"

I don't think that was ever true. It (most RDBMS) can use an index, but without an implementation of a loose index scan they would have had to scan the entire index, as in an Index-only scan. This saves having to visit the table. This may or may not be the desirable action (in the cases where it would have to visit the table anyway), when the selectivity is low, or when the index is close enough to the size of the table that it simply doesn't matter.

See also

• MySQL 8: Group by Optimization - Loose Index Scan

• PostgreSQL Method (with a Recursive CTE)

Footnotes

• I'm not sure whether the book's statement about MySQL is still accurate as the book was printed in 2012 and covers MySQL 5.5.

StackExchange Database Administrators Q#63293, answer score: 3