Index Condition Pushdown Based on Cost Estimation

How ICP Improves Performance

During a secondary index scan, if the query needs to access columns not covered by the index (a non-covering index scenario), InnoDB must perform a lookup in the clustered index for every matching index row to retrieve the complete record. The SQL layer then evaluates the WHERE condition row by row.

When the WHERE condition involves trailing key columns of the index (such as c = 9 on idx_abc(a, b, c)), these column values are already present in the index records. This means that the storage engine can directly evaluate the condition before initiating a row lookup.

ICP leverages this characteristic. It pushes the WHERE condition down to the storage engine layer. The engine evaluates the pushed-down predicates during the index scan, skipping row lookups for any records that fail to meet the condition.

Performance benefits of ICP are driven by two main factors:

• Reduced lookup I/O: Rows filtered out by ICP do not require clustered index lookups. This reduces disk I/O and buffer pool access overhead. For highly selective conditions, the number of table lookups can be drastically reduced.
• Reduced CPU overhead: The storage engine evaluates conditions directly on the index record's key values. This avoids the overhead of constructing complete expression trees, invoking virtual functions, and performing type conversions at the SQL layer.

For example, given the query with WHERE a = 4 AND c = 9, during an index scan on idx_abc: The engine first locates the index records using a = 4 and then evaluates the condition on column c (checks if c is equal to 9) in the index records. Rows that fail to satisfy the condition are skipped and do not require clustered index lookups. For rows satisfying the condition, the engine performs lookups. Without ICP, the engine performs a row lookup for every row matching a = 4 before the SQL layer evaluates the predicate c = 9. With ICP enabled, it reduces the number of row lookups from all rows matching a = 4 to only those matching a = 4 AND c = 9.

Application Scenarios

This feature is applied during the optimizer planning phase, specifically during the candidate comparison stage for both equality access path selection and range access path selection. The optimizer first checks whether the index supports ICP, whether there are pushdown-eligible conditions on trailing key columns, and whether the filtering threshold is satisfied. If all conditions are met, the optimizer deducts the estimated ICP benefit from the original cost and uses the adjusted cost for candidate comparison. After enabling this feature, you may observe that a wider index is selected in the execution plan and that Using index condition appears in the Extra column in the EXPLAIN output.

• Equality access scenarios
  Consider the following query:

  SELECT * FROM t WHERE a = 4 AND c = 9;

  Assume that the table has two indexes: idx_a(a) and idx_abc(a, b, c). In MySQL Community Edition, both indexes scan the same number of rows for a = 4 but idx_a is selected because it is narrower. However, idx_abc can push down the condition c = 9 to the storage engine layer using ICP, reducing the number of row lookups. With this feature enabled, the optimizer estimates the ICP benefit for idx_abc, allowing idx_abc to win the candidate comparison.

• Range scan scenarios
  Consider the following query:

  SELECT * FROM t WHERE a BETWEEN 2 AND 2.5 AND c = 7;

  In MySQL Community Edition, range scan candidates are compared based on their original costs. When the costs of different indexes are similar, the narrowest index is selected. However, the wider idx_abc can use ICP to filter out rows matching c = 7, reducing both row lookups and row evaluation overhead. With this feature enabled, the optimizer incorporates the ICP filtering benefit into cost estimation, allowing idx_abc to become the optimal choice.

Cost Model and Protection Mechanisms

• Cost Model

  ICP provides performance benefits through both I/O and CPU savings, consistent with MySQL's existing cost formulas:

  • I/O savings: Rows filtered out by ICP bypass clustered index lookups, reducing I/O overhead.
  • CPU savings: Evaluating conditions at the storage engine layer is less expensive than evaluation at the SQL layer. Rows filtered out do not require complete expression evaluation at the SQL layer.
  • Benefit cap: ICP benefits are capped to ensure that they do not exceed the proportion of cost that ICP can actually influence, preventing distorted cost adjustments.
• Protection Mechanisms

  To prevent index selection deviation from overly optimistic ICP benefit estimation, the feature implements several protection mechanisms.

  • Filtering threshold: Cost adjustments are applied only when the selectivity of the pushdown-eligible conditions of ICP is sufficiently low, ensuring that ICP can filter out a sufficient proportion of rows. This threshold excludes conditions with unreliable selectivity estimates (such as inequalities or multiple OR combinations) to prevent poor index choices.
  • Benefit cap: ICP benefits cannot exceed the proportion of cost ICP can influence, ensuring that adjusted costs remain non-negative and reasonable.
  • Engine-side cost factor: Condition evaluation at the engine side is modeled as cheaper than evaluation at the SQL side, preventing overestimation of CPU savings.