7.2.5.1. The Range Access Method for Single-Part Indexes
For a single-part index, index value intervals can be
conveniently represented by corresponding conditions in the
WHERE clause, so we speak of
range conditions rather than
“intervals.”
The definition of a range condition for a single-part index is
as follows:
For both BTREE and
HASH indexes, comparison of a key part
with a constant value is a range condition when using the
=, <=>,
IN, IS NULL, or
IS NOT NULL operators.
For BTREE indexes, comparison of a key
part with a constant value is a range condition when using
the >, <,
>=, <=,
BETWEEN, !=, or
<> operators, or LIKE
'pattern' (where
'pattern'
does not start with a wildcard).
For all types of indexes, multiple range conditions
combined with OR or
AND form a range condition.
“Constant value” in the preceding descriptions
means one of the following:
A constant from the query string
A column of a const or
system table from the same join
The result of an uncorrelated subquery
Any expression composed entirely from subexpressions of
the preceding types
Here are some examples of queries with range conditions in the
WHERE clause:
SELECT * FROM t1
WHERE key_col > 1
AND key_col < 10;
SELECT * FROM t1
WHERE key_col = 1
OR key_col IN (15,18,20);
SELECT * FROM t1
WHERE key_col LIKE 'ab%'
OR key_col BETWEEN 'bar' AND 'foo';
Note that some non-constant values may be converted to
constants during the constant propagation phase.
MySQL tries to extract range conditions from the
WHERE clause for each of the possible
indexes. During the extraction process, conditions that cannot
be used for constructing the range condition are dropped,
conditions that produce overlapping ranges are combined, and
conditions that produce empty ranges are removed.
Consider the following statement, where
key1 is an indexed column and
nonkey is not indexed:
SELECT * FROM t1 WHERE
(key1 < 'abc' AND (key1 LIKE 'abcde%' OR key1 LIKE '%b')) OR
(key1 < 'bar' AND nonkey = 4) OR
(key1 < 'uux' AND key1 > 'z');
The extraction process for key key1 is as
follows:
-
Start with original WHERE clause:
(key1 < 'abc' AND (key1 LIKE 'abcde%' OR key1 LIKE '%b')) OR
(key1 < 'bar' AND nonkey = 4) OR
(key1 < 'uux' AND key1 > 'z')
-
Remove nonkey = 4 and key1
LIKE '%b' because they cannot be used for a
range scan. The correct way to remove them is to replace
them with TRUE, so that we do not miss
any matching rows when doing the range scan. Having
replaced them with TRUE, we get:
(key1 < 'abc' AND (key1 LIKE 'abcde%' OR TRUE)) OR
(key1 < 'bar' AND TRUE) OR
(key1 < 'uux' AND key1 > 'z')
-
Collapse conditions that are always true or false:
Replacing these conditions with constants, we get:
(key1 < 'abc' AND TRUE) OR (key1 < 'bar' AND TRUE) OR (FALSE)
Removing unnecessary TRUE and
FALSE constants, we obtain:
(key1 < 'abc') OR (key1 < 'bar')
-
Combining overlapping intervals into one yields the final
condition to be used for the range scan:
(key1 < 'bar')
In general (and as demonstrated by the preceding example), the
condition used for a range scan is less restrictive than the
WHERE clause. MySQL performs an additional
check to filter out rows that satisfy the range condition but
not the full WHERE clause.
The range condition extraction algorithm can handle nested
AND/OR constructs of
arbitrary depth, and its output does not depend on the order
in which conditions appear in WHERE clause.
