(mysql.info) mysql-indexes
Info Catalog
(mysql.info) multiple-column-indexes
(mysql.info) optimizing-database-structure
(mysql.info) myisam-key-cache
7.4.5 How MySQL Uses Indexes
----------------------------
Indexes are used to find rows with specific column values quickly.
Without an index, MySQL must begin with the first row and then read
through the entire table to find the relevant rows. The larger the
table, the more this costs. If the table has an index for the columns
in question, MySQL can quickly determine the position to seek to in the
middle of the data file without having to look at all the data. If a
table has 1,000 rows, this is at least 100 times faster than reading
sequentially. If you need to access most of the rows, it is faster to
read sequentially, because this minimizes disk seeks.
Most MySQL indexes (`PRIMARY KEY', `UNIQUE', `INDEX', and `FULLTEXT')
are stored in B-trees. Exceptions are that indexes on spatial data
types use R-trees, and that `MEMORY' tables also support hash indexes.
Strings are automatically prefix- and end-space compressed. See
create-index.
In general, indexes are used as described in the following discussion.
Characteristics specific to hash indexes (as used in `MEMORY' tables)
are described at the end of this section.
MySQL uses indexes for these operations:
* To find the rows matching a `WHERE' clause quickly.
* To eliminate rows from consideration. If there is a choice between
multiple indexes, MySQL normally uses the index that finds the
smallest number of rows.
* To retrieve rows from other tables when performing joins.
* To find the `MIN()' or `MAX()' value for a specific indexed column
KEY_COL. This is optimized by a preprocessor that checks whether
you are using `WHERE KEY_PART_N = CONSTANT' on all key parts that
occur before KEY_COL in the index. In this case, MySQL does a
single key lookup for each `MIN()' or `MAX()' expression and
replaces it with a constant. If all expressions are replaced with
constants, the query returns at once. For example:
SELECT MIN(KEY_PART2),MAX(KEY_PART2)
FROM TBL_NAME WHERE KEY_PART1=10;
* To sort or group a table if the sorting or grouping is done on a
leftmost prefix of a usable key (for example, `ORDER BY KEY_PART1,
KEY_PART2'). If all key parts are followed by `DESC', the key is
read in reverse order. See order-by-optimization.
* In some cases, a query can be optimized to retrieve values without
consulting the data rows. If a query uses only columns from a
table that are numeric and that form a leftmost prefix for some
key, the selected values may be retrieved from the index tree for
greater speed:
SELECT KEY_PART3 FROM TBL_NAME
WHERE KEY_PART1=1
Suppose that you issue the following `SELECT' statement:
mysql> SELECT * FROM TBL_NAME WHERE col1=VAL1 AND col2=VAL2;
If a multiple-column index exists on `col1' and `col2', the appropriate
rows can be fetched directly. If separate single-column indexes exist on
`col1' and `col2', the optimizer tries to find the most restrictive
index by deciding which index finds fewer rows and using that index to
fetch the rows.
If the table has a multiple-column index, any leftmost prefix of the
index can be used by the optimizer to find rows. For example, if you
have a three-column index on `(col1, col2, col3)', you have indexed
search capabilities on `(col1)', `(col1, col2)', and `(col1, col2,
col3)'.
MySQL cannot use a partial index if the columns do not form a leftmost
prefix of the index. Suppose that you have the `SELECT' statements
shown here:
SELECT * FROM TBL_NAME WHERE col1=VAL1;
SELECT * FROM TBL_NAME WHERE col1=VAL1 AND col2=VAL2;
SELECT * FROM TBL_NAME WHERE col2=VAL2;
SELECT * FROM TBL_NAME WHERE col2=VAL2 AND col3=VAL3;
If an index exists on `(col1, col2, col3)', only the first two queries
use the index. The third and fourth queries do involve indexed columns,
but `(col2)' and `(col2, col3)' are not leftmost prefixes of `(col1,
col2, col3)'.
A B-tree index can be used for column comparisons in expressions that
use the `=', `>', `>=', `<', `<=', or `BETWEEN' operators. The index
also can be used for `LIKE' comparisons if the argument to `LIKE' is a
constant string that does not start with a wildcard character. For
example, the following `SELECT' statements use indexes:
SELECT * FROM TBL_NAME WHERE KEY_COL LIKE 'Patrick%';
SELECT * FROM TBL_NAME WHERE KEY_COL LIKE 'Pat%_ck%';
In the first statement, only rows with `'Patrick' <= KEY_COL <
'Patricl'' are considered. In the second statement, only rows with
`'Pat' <= KEY_COL < 'Pau'' are considered.
The following `SELECT' statements do not use indexes:
SELECT * FROM TBL_NAME WHERE KEY_COL LIKE '%Patrick%';
SELECT * FROM TBL_NAME WHERE KEY_COL LIKE OTHER_COL;
In the first statement, the `LIKE' value begins with a wildcard
character. In the second statement, the `LIKE' value is not a constant.
If you use `... LIKE '%STRING%'' and STRING is longer than three
characters, MySQL uses the Turbo Boyer-Moore algorithm to initialize
the pattern for the string and then uses this pattern to perform the
search more quickly.
A search using `COL_NAME IS NULL' employs indexes if COL_NAME is
indexed.
Any index that does not span all `AND' levels in the `WHERE' clause is
not used to optimize the query. In other words, to be able to use an
index, a prefix of the index must be used in every `AND' group.
The following `WHERE' clauses use indexes:
... WHERE INDEX_PART1=1 AND INDEX_PART2=2 AND OTHER_COLUMN=3
/* INDEX = 1 OR INDEX = 2 */
... WHERE INDEX=1 OR A=10 AND INDEX=2
/* optimized like "INDEX_PART1='hello'" */
... WHERE INDEX_PART1='hello' AND INDEX_PART3=5
/* Can use index on INDEX1 but not on INDEX2 or INDEX3 */
... WHERE INDEX1=1 AND INDEX2=2 OR INDEX1=3 AND INDEX3=3;
These `WHERE' clauses do _not_ use indexes:
/* INDEX_PART1 is not used */
... WHERE INDEX_PART2=1 AND INDEX_PART3=2
/* Index is not used in both parts of the WHERE clause */
... WHERE INDEX=1 OR A=10
/* No index spans all rows */
... WHERE INDEX_PART1=1 OR INDEX_PART2=10
Sometimes MySQL does not use an index, even if one is available. One
circumstance under which this occurs is when the optimizer estimates
that using the index would require MySQL to access a very large
percentage of the rows in the table. (In this case, a table scan is
likely to be much faster because it requires fewer seeks.) However, if
such a query uses `LIMIT' to retrieve only some of the rows, MySQL uses
an index anyway, because it can much more quickly find the few rows to
return in the result.
Hash indexes have somewhat different characteristics from those just
discussed:
* They are used only for equality comparisons that use the `=' or
`<=>' operators (but are _very_ fast). They are not used for
comparison operators such as `<' that find a range of values.
* The optimizer cannot use a hash index to speed up `ORDER BY'
operations. (This type of index cannot be used to search for the
next entry in order.)
* MySQL cannot determine approximately how many rows there are
between two values (this is used by the range optimizer to decide
which index to use). This may affect some queries if you change a
`MyISAM' table to a hash-indexed `MEMORY' table.
* Only whole keys can be used to search for a row. (With a B-tree
index, any leftmost prefix of the key can be used to find rows.)
Info Catalog
(mysql.info) multiple-column-indexes
(mysql.info) optimizing-database-structure
(mysql.info) myisam-key-cache
automatically generated byinfo2html