Differences and Collaborative Optimization between Index Condition Pushdown (ICP) and Storage Engine Filtering in Database Query Optimization

1. Problem Context and Core Concepts
In database queries, when using indexes for data retrieval, the traditional process is: the storage engine scans index entries based on index location conditions (e.g., WHERE key_part1 = 'a'), retrieves the corresponding full row primary key (or row data), returns it to the Server layer, which then filters based on the remaining non-index column conditions (e.g., WHERE key_part1 = 'a' AND non_indexed_column = 10). This leads to a large number of unnecessary row data reads and transfers, especially when the index condition has low selectivity. Index Condition Pushdown (ICP) and Storage Engine Filtering are two key optimization techniques aimed at "pushing down" filter conditions to lower, earlier stages of execution, but they operate at different levels and have distinct principles.

2. Detailed Workflow of Index Condition Pushdown (ICP)
The core idea of ICP is: To push query conditions that involve columns present in the index but cannot be used for index range scanning from the Server layer down to the storage engine layer, allowing the storage engine to filter during index scanning (before row retrieval).

• Applicable Conditions: The query uses a composite index, but not all conditions in the WHERE clause can be used for index range scanning. For example, with a composite index (zipcode, lastname, firstname) and a query:

  SELECT * FROM people WHERE zipcode='95054' AND lastname LIKE '%etrunia%' AND address LIKE '%Main Street%';
  

  • zipcode='95054' can serve as the index location condition (defining the starting point of the index scan).
  • lastname LIKE '%etrunia%' also involves the index column lastname, but because it uses a leading wildcard LIKE, it cannot narrow the index scan range; it is a index column condition that can be pushed down.
  • address LIKE '%Main Street%' involves a non-index column and cannot be pushed down.
• Traditional Process (without ICP):
  1. The storage engine uses the index location condition zipcode='95054' to scan the index, finding all index entries where zipcode='95054'.
  2. For each index entry, the storage engine retrieves the complete row data (including all columns like address) based on its primary key value (row lookup).
  3. The retrieved complete row data is returned to the Server layer.
  4. The Server layer applies all WHERE conditions (lastname LIKE ... and address LIKE ...) for filtering.
• ICP Optimized Process:
  1. The storage engine similarly scans the index using zipcode='95054', finding the index entries.
  2. Key Difference: After reading an index entry but before performing the row lookup, the storage engine first checks if the column values already contained in this index entry (here, lastname) satisfy the pushable condition (lastname LIKE '%etrunia%').
  3. If not satisfied, the storage engine skips this index entry and proceeds to the next one, avoiding an unnecessary row lookup operation.
  4. If satisfied, the storage engine then performs the row lookup based on the primary key in the index entry to read the full row, and returns the row data to the Server layer.
  5. The Server layer then applies the remaining non-index column condition (address LIKE ...) for final filtering.
• Core Benefit: Significantly reduces unnecessary row lookups and I/O operations by the storage engine, especially when the pushable condition (e.g., lastname LIKE) can filter out a large number of records.

3. Detailed Workflow of Storage Engine Filtering
Storage Engine Filtering is a broader concept, referring to the storage engine filtering out data that does not meet conditions while reading data blocks (Pages), based on its internal data structures or metadata, without even needing to decode the entire row of data. This is fundamentally different from ICP's "filtering at the index layer".

• Common Forms:
  1. Block/Page Level Filtering: In columnar storage (e.g., Apache Parquet, ORC), each data block (Row Group/Stripe) stores statistical information about its internal data (e.g., Min/Max values, Bloom filters). During queries, the storage engine can first check these statistics. If the query condition definitely falls outside the value range of a block (e.g., WHERE column = 100, and the block's Min=200, Max=300), it skips reading and parsing the entire data block.
  2. Predicate Pushdown to Scan Layer: In some modern analytical databases (e.g., ClickHouse) or big data frameworks (e.g., Spark), predicates can be pushed directly down to file scanners. For example, when reading Parquet files, filter conditions are passed to the Parquet Reader, enabling it to decode only relevant columns and apply filter conditions as early as possible, reducing the amount of data materialized in memory.
  3. Zone Maps: Similar to block-level statistics, these are pre-calculated and stored data ranges used to quickly skip irrelevant data blocks before I/O.
• Core Benefit: Dramatically reduces the amount of data that needs to be processed at the early stages of data reading and decoding, saving I/O bandwidth and CPU decoding overhead, particularly suitable for analytical queries scanning large volumes of data.

4. Differences and Relationship Between the Two

Example of Collaborative Workflow:
For the same table, with both ICP and columnar storage engine filtering enabled, a query might undergo:

1. Storage Engine Filtering (Block Level): Query WHERE date = '2023-10-01' AND amount > 100. Each block of the columnar file records the Min/Max for date and amount. The storage engine directly skips all data blocks that do not contain date='2023-10-01' or where the maximum amount <= 100.
2. Index Scan + ICP: For the remaining blocks, if an index (date, customer_id) exists and the query also includes customer_id LIKE 'A%', the storage engine uses date='2023-10-01' to scan the index, and for each index entry uses ICP to check if customer_id satisfies LIKE 'A%', skipping the row lookup if not satisfied.
3. Row Lookup + Final Filtering: Index entries satisfying the ICP condition trigger row lookups (where, due to columnar storage, only required columns might be read), and the data is returned to the Server layer for any remaining filtering.

5. Summary
Index Condition Pushdown (ICP) is an optimization for the index access path, leveraging column values within the index to filter early before row lookup, with the core goal of reducing random I/O. Storage Engine Filtering is an optimization for underlying data storage and scanning, leveraging metadata of data files to filter early at the I/O and decoding layers, with the core goal of reducing sequential I/O and CPU overhead. The two can work collaboratively, forming filtering barriers at different levels to jointly "discard unnecessary data as early as possible." They are crucial two-tier filtering mechanisms in modern database query optimization. Understanding their differences helps in making better decisions during table design (index design, storage format selection) and query writing.