Skip navigation links
7.4.5 The MyISAM Key Cache »
Section Navigation      [Toggle]

7.4.4. 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 Section 12.1.11, “CREATE INDEX Syntax”.

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. MySQL can use indexes on columns more efficiently if they are declared as the same type and size. In this context, VARCHAR and CHAR are considered the same if they are declared as the same size. For example, VARCHAR(10) and CHAR(10) are the same size, but VARCHAR(10) and CHAR(15) are not.

    Comparison of dissimilar columns may prevent use of indexes if values cannot be compared directly without conversion. Suppose that a numeric column is compared to a string column. For a given value such as 1 in the numeric column, it might compare equal to any number of values in the string column such as '1', ' 1', '00001', or '01.e1'. This rules out use of any indexes for the string column.

  • 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 Section 7.2.14, “ORDER BY Optimization”, and Section 7.2.15, “GROUP 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 will attempt to use the Index Merge optimization (see Section 7.2.6, “Index Merge Optimization”), or attempt 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 an 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.)

MySQL Enterprise.  Often, it is not possible to predict exactly what indexes will be required or will be most efficient — actual table usage is the best indicator. The MySQL Enterprise Monitor provides expert advice on this topic. For more information, see http://www.mysql.com/products/enterprise/advisors.html.


User Comments

Posted by Michael Schröpl on July 23 2002 11:42am[Delete] [Edit]

One case when mySQL 3.23 does not use an index is
if it has to implicitly convert types.

Imagine you have a column of a VARCHAR type but
query this in the form "SELECT * FROM tablename
WHERE columnname = 123"; mySQL implicitly converts
123 to "123" but then does a full table scan.

Posted by Ed Soniat on November 1 2002 6:03am[Delete] [Edit]

This section should include information about the cost of indexes. The size of an index and the cost of keeping an index current. An over view of how to determine when to use an index would be good too.

Posted by Scott James on June 18 2003 1:13am[Delete] [Edit]

With 3.28.56 I was able to use a composite index on two columns, in one special case:

mysql> create table t(a int, b int, c int);
mysql> create index t_idx on t (a,b,c);
mysql> insert into t values (1, 1, 1);
... (load 10 more test rows like this) ...

mysql> explain select * from t where a=1 or b=1;

| table | type  | possible_keys | key   | key_len | ref  
| t     | index | t_idx         | t_idx |      15 | NULL

However, notice that the composite index is on ALL columns of the table (rarely practical). So, lets create an index on only the first two columns:

mysql> drop index t_idx from t;
mysql> create index t_idx on t(a,b);
mysql> explain select * from t where a=1 or b=1;
| table | type | possible_keys | key  | key_len | ref
| t     | ALL  | t_idx         | NULL |    NULL | NULL

So, if you absolutely need to use OR to join multiple rows, consider creating a smaller in-memory table (CREATE ... SELECT ... TYPE=HEAP). This could help if you do this kind of join multiple times in a single transaction.


Posted by Donny Simonton on November 4 2003 12:56pm[Delete] [Edit]

Instead of using OR, just use IN. For example, you would write your query like:

select MembershipNumber, MemberID from Member where MemberID IN ('123896920', '1029540');

I'm running 4.1 currently and the difference between an OR and IN are nothing. But on an older 3.x box we have IN makes a huge difference.

Posted by Martin Mokrejs on November 5 2003 1:06am[Delete] [Edit]

Scott James above gave us nice examples. Unfortunately,
the syntax to drop the index needs `ON' instead of `FROM'.

DROP INDEX index_name ON tbl_name

Posted by [name withheld] on December 15 2003 5:31am[Delete] [Edit]

Hi,

Not sure what version of MYSQL you are talking about, looking at the docs here -> http://www.mysql.com/doc/en/ALTER_TABLE.html

This is the correct pseudo syntax:

alter table test drop index I_TEST;

[edited]
Looks like this link might explain some of the confusion http://www.mysql.com/doc/en/DROP_INDEX.html

I would suggest using the alter table statement.

greetings,

glenn

Posted by Mike Chirico on April 16 2004 12:14pm[Delete] [Edit]

An index can be used to surgically remove duplicate entries.

For updated example, reference:
http://osdn.dl.sourceforge.net/sourceforge/souptonuts/README_mysql.txt

Assume the following table and data.

CREATE TABLE IF NOT EXISTS dupTest (
pkey int(11) NOT NULL auto_increment,
a int,
b int,
c int,
timeEnter timestamp(14),
PRIMARY KEY (pkey)

);

insert into dupTest (a,b,c) values (1,2,3),(1,2,3),
(1,5,4),(1,6,4);



mysql> select * from dupTest;
select * from dupTest;
+------+------+------+------+---------------------+
| pkey | a | b | c | timeEnter |
+------+------+------+------+---------------------+
| 1 | 1 | 2 | 3 | 2004-04-16 10:55:35 |
| 2 | 1 | 2 | 3 | 2004-04-16 10:55:35 |
| 3 | 1 | 5 | 4 | 2004-04-16 10:55:35 |
| 4 | 1 | 6 | 4 | 2004-04-16 10:55:35 |
+------+------+------+------+---------------------+
4 rows in set (0.00 sec)

mysql>

Note, the first two rows contains duplicates in columns a and b. It contains
other duplicates; but, leave the other duplicates alone.



mysql> ALTER IGNORE TABLE dupTest ADD UNIQUE INDEX(a,b);


mysql> select * from dupTest;
select * from dupTest;
+------+------+------+------+---------------------+
| pkey | a | b | c | timeEnter |
+------+------+------+------+---------------------+
| 1 | 1 | 2 | 3 | 2004-04-16 11:11:42 |
| 3 | 1 | 5 | 4 | 2004-04-16 11:11:42 |
| 4 | 1 | 6 | 4 | 2004-04-16 11:11:42 |
+------+------+------+------+---------------------+
3 rows in set (0.00 sec)



Regards,

Mike Chirico


Posted by Peter Brodersen on June 7 2004 9:42am[Delete] [Edit]

Selecting data using OR on two different columns with individual indices could be optimized using UNION (thereby creating two separate queries). UNION was introduced in MySQL 4.0.

From the above example: (notice that two different fields are used - MemberID and MembershipNumber - if the field was the same, IN() or OR would be optimized)

Before:
select MembershipNumber, MemberID from Member where MemberID = 123896920 or MembershipNumber = 1029540;

After:
select MembershipNumber, MemberID from Member where MemberID = 123896920
UNION
select MembershipNumber, MemberID from Member where MembershipNumber = 1029540;


Two fast selects will be performed where indices are used. UNION will remove a possible duplicate (and UNION ALL would leave the duplicate).

Posted by Stephen Dewey on October 24 2006 1:12am[Delete] [Edit]

I was seriously confused by the following line from this section, but I'm pretty sure I've figured it out and I think it would be helpful for somebody else if I explained it here.

"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."

I thought at first that that sentence meant that every element of an AND clause had to be in the index, so the above examples didn't make any sense.

What they actually mean by an "AND group" is a set of statements connected by AND operators, which have precedence over OR operators. Within each *set* connected by those operators, there must be at least *one* element that can form an index prefix (as defined above), but additional elements in the set do not have to be in the index at all.

So, to explain some of the examples:

WHERE index_part1=1 AND index_part2=2 AND other_column=3

The index will be used in this case because index_part1 and index_part2 combine to form a prefix for the index. It's ok that other_column is not part of the index, because the entire WHERE clause is a single AND group, and the index requirement has already been fulfilled.

WHERE index_part1=1 OR index_part2=10

This example could be confusing because there is no AND keyword anywhere here. However, all they mean by an "AND group" is a single set of one or more statements which must all be true in order to evaluate as true. In this case, index_part1=1 is **its own** AND group, and index_part2=10 is also **its own** AND group. They are separated into 2 AND groups by the OR clause.

So, the above example fails the test because there is no single index with a prefix in both AND groups. The index does have a prefix in the first AND group, index_part1. However, the second AND group has no prefix because index_part2 cannot be a prefix because it is the second part of the index. (In the first example above, of course, there were both index_part1 and index_part2. But they were both part of a single AND group, so index_part1 fulfilled the requirement. Actually, they probably combined and were evaluated together as a longer prefix (index_parts1+2), but the point is that the fact that index_part2 cannot be a prefix on its own did not matter in that case).

If you step back and think about the reason for this rule, it makes sense. Indexing is done in order to remove rows from consideration so that MySQL has to do less work to find the right rows. The only way it can do this efficiently is when it can say definitively based on what **it itself** knows that a certain row should not be part of the result set. Because the index needs to be used before any other evaluations take place (in order to have the effect of reducing the number of those evaluations), it cannot supplement its data by doing unrelated queries. That would defeat the purpose because it would involve a call to the table for every row.

When you add an OR statement, and don't include any fields of the index in the clause after the OR statement, the index cannot do its job anymore because it cannot definitively exclude any given row from the result set. This is because even if it determines that a row does not meet the condition it has to test, the row might *still* match the other clause after the OR statement, and thereby fulfill the WHERE condition.

The only way to get around this, then, is if a usable index prefix is also in the second clause after the OR statement. Then the index can evaluate whether each row meets either of the 2 conditions it is now testing for, and throw out the ones that match NEITHER condition. This is valid because if the row fails the test that the index conducts, it fails the entire AND group. And the index is now testing every AND group.

It is best to think of the AND keyword not as having any inherent power over the index itself, but as specifying which clauses should all be lumped together as a group such that a single failure of one of the conditions would cause the entire group to fail.

I hope that makes sense... it's hard to explain. Hopefully they will clarify that part of the manual in future editions.

Add your own comment.