Skip navigation links
7.2.6.1 The Index Merge Intersection Access Algorithm »
Section Navigation      [Toggle]

7.2.6. Index Merge Optimization

[+/-]

7.2.6.1. The Index Merge Intersection Access Algorithm
7.2.6.2. The Index Merge Union Access Algorithm
7.2.6.3. The Index Merge Sort-Union Access Algorithm

The Index Merge method is used to retrieve rows with several range scans and to merge their results into one. The merge can produce unions, intersections, or unions-of-intersections of its underlying scans. This access method merges index scans from a single table; it does not merge scans across multiple tables.

Note

If you have upgraded from a previous version of MySQL, you should be aware that this type of join optimization is first introduced in MySQL 5.0, and represents a significant change in behavior with regard to indexes. (Formerly, MySQL was able to use at most only one index for each referenced table.)

In EXPLAIN output, the Index Merge method appears as index_merge in the type column. In this case, the key column contains a list of indexes used, and key_len contains a list of the longest key parts for those indexes.

Examples: 

SELECT * FROM tbl_name WHERE key1 = 10 OR key2 = 20;

SELECT * FROM tbl_name
  WHERE (key1 = 10 OR key2 = 20) AND non_key=30;

SELECT * FROM t1, t2
  WHERE (t1.key1 IN (1,2) OR t1.key2 LIKE 'value%')
  AND t2.key1=t1.some_col;

SELECT * FROM t1, t2
  WHERE t1.key1=1
  AND (t2.key1=t1.some_col OR t2.key2=t1.some_col2);

The Index Merge method has several access algorithms (seen in the Extra field of EXPLAIN output):

  • Using intersect(...)

  • Using union(...)

  • Using sort_union(...)

The following sections describe these methods in greater detail.

Note

The Index Merge optimization algorithm has the following known deficiencies:

  • If a range scan is possible on some key, the optimizer will not consider using Index Merge Union or Index Merge Sort-Union algorithms. For example, consider this query: 

    SELECT * FROM t1 WHERE (goodkey1 < 10 OR goodkey2 < 20) AND badkey < 30;

    For this query, two plans are possible:

    • An Index Merge scan using the (goodkey1 < 10 OR goodkey2 < 20) condition.

    • A range scan using the badkey < 30 condition.

    However, the optimizer considers only the second plan.

  • If your query has a complex WHERE clause with deep AND/OR nesting and MySQL doesn't choose the optimal plan, try distributing terms using the following identity laws: 

    (x AND y) OR z = (x OR z) AND (y OR z)
(x OR y) AND z = (x AND z) OR (y AND z)

  • Index Merge is not applicable to full-text indexes. We plan to extend it to cover these in a future MySQL release.

The choice between different possible variants of the Index Merge access method and other access methods is based on cost estimates of various available options.


User Comments

Posted by Ratheesh Bhat on March 1 2007 6:20am[Delete] [Edit]

Beware of having low selectivity indexes on your table. A complex AND/OR WHERE clause will surely make your query very very slow if Index_Merge optimization is being used with an intersect() algorithm.

Add your own comment.