MySQL Index Merge Optimization Explained

This article explores how the MySQL query optimizer evaluates and applies index merge optimizations to improve query performance. It covers the different types of index merges—intersection, union, and sort-union—how the cost-based optimizer decides to use them, and the practical limitations of this execution strategy.

What is MySQL Index Merge?

The Index Merge optimization method allows MySQL to retrieve rows from a single table using multiple index scans. The optimizer merges the row IDs (or primary keys) retrieved from these different index scans into a single result set before fetching the actual row data from the table.

Historically, MySQL could only use one index per table access in a query. Index Merge relaxes this limitation, allowing the database to resolve complex AND and OR queries more efficiently without relying solely on composite indexes.

How the Optimizer Evaluates Index Merge

MySQL uses a Cost-Based Optimizer (CBO) to determine the most efficient execution plan for a query. To evaluate whether to use an Index Merge, the optimizer performs the following steps:

1. Candidate Index Identification: The optimizer analyzes the WHERE clause to identify which columns have indexes and can be used to filter the query.
2. Cost Estimation of Single Indexes: The optimizer calculates the estimated cost (in terms of disk I/O and CPU cycles) of using the single best-performing index.
3. Cost Estimation of Index Merge: The optimizer calculates the cost of scanning multiple indexes, sorting the retrieved row IDs (if necessary), and merging them. The cost formula factors in:
   • The number of index rows to be scanned.
   • The CPU cost of intersecting or unionizing the keys.
   • The memory buffer requirements for the merge operation.
4. Comparison and Selection: If the calculated cost of the Index Merge plan is lower than a single index scan, a full table scan, or a range scan, the optimizer selects the Index Merge strategy.

Index Merge Algorithms

Depending on the structure of the query and the logical operators used, the optimizer applies one of three index merge algorithms:

1. Intersection Algorithm

This algorithm is applied when the query filters data using AND conditions on different indexed columns.

• How it works: MySQL performs simultaneous range scans on the candidate indexes. It retrieves the primary keys from each scan and finds the intersection (the keys present in all scans). Only the rows matching the intersected keys are fetched from the table.
• Condition: All used indexes must have their scanned parts fully covered, or the query must be looking for primary key values.

2. Union Algorithm

This algorithm is used when the query contains OR conditions on different indexed columns.

• How it works: MySQL scans the designated indexes, retrieves the matching row IDs, combines them, and filters out duplicates.
• Condition: The query must be structured such that the row IDs retrieved from the index scans are already sorted (e.g., when scanning a primary key or a covering index).

3. Sort-Union Algorithm

This algorithm is similar to the Union algorithm but is utilized when the retrieved row IDs are not guaranteed to be in sorted order.

• How it works: MySQL performs the individual index scans, retrieves the row IDs, explicitly sorts the row ID lists, and then merges them to remove duplicates.
• Why it is used: It is necessary when the query contains range conditions on multiple columns combined by OR where the index scans do not naturally produce sorted row IDs.

Limitations of Index Merge

While Index Merge can improve performance, it is not always the optimal choice. The optimizer may bypass it or suffer performance penalties due to the following factors:

• Resource Overhead: Merging and sorting row IDs requires CPU and memory buffers (configured via sort_buffer_size). If the merge involves millions of rows, the overhead can exceed the cost of a simple table scan.
• Deep OR Nesting: Highly complex, deeply nested OR clauses can confuse the optimizer, causing it to default to a full table scan instead of an Index Merge.
• Composite Indexes are Often Better: A single composite (multi-column) index designed specifically for the query is almost always faster than an Index Merge. Composite indexes allow the database to filter on multiple columns in a single B-tree traversal without the overhead of merging.