Elimination of Redundant Conditions in Range Queries

Scenarios

When MySQL Community Edition processes predicates such as WHERE col = const or WHERE col > const, if an index exists on the column and the optimizer chooses a range scan access method, the upper and lower bounds of the range scan already guarantee that the predicates are true. However, the SQL layer still repeatedly evaluates these predicates for each row, resulting in unnecessary CPU overhead. In large-scale scanning scenarios, this redundant evaluation can lead to significant performance losses.

For example, in the query SELECT * FROM t WHERE a = 5 AND b > 3, if the index is (a, b), the min_key of the range scan is [5, 3] and the max_key is [5, +∞]. The predicate a = 5 is fully guaranteed by the lower bound of the range, so row-by-row evaluation is unnecessary. However, MySQL Community Edition only supports equality elimination for REF access (test_if_ref) and does not eliminate equality or inequality predicates in range scan scenarios.

Theoretically, a mechanism similar to equality elimination for REF access can be introduced to handle range scans, but this approach faces several challenges:

• Security of bound access: The bounds of range scans are stored in the QUICK_RANGE structure and must be securely read and compared with predicate constants. If the comparison semantics differ from those of the storage engine, predicates may be removed by mistake, leading to incorrect query results.
• Semantic loss during interval merging: The merged intervals generated by OR clauses may not align with the forms of the original predicates. For example, c=3 OR c>2 will be merged into a single interval of c>2 (with no upper bound). In this case, it is impossible to determine whether c=3 is redundant. Forcibly eliminating it will cause semantic errors.
• Impact on near-data processing (NDP) pushdown: NDP pushdown relies on WHERE conditions. Eliminating redundant predicates may reduce the number of conditions that can be pushed down, which in turn degrades overall performance.

To address these challenges, TaurusDB supports the elimination of redundant conditions in range queries. When a table is accessed using a range scan, the optimizer automatically identifies and removes predicates that are already guaranteed by the upper and lower bounds of the range. This reduces repeated evaluation overhead at the SQL layer and improves query performance.

Conversion Process

Original query

SELECT * FROM t WHERE a = 5 AND b > 3

If the index is (a, b), the min_key of the range scan is [5, 3] and the max_key is [5, +∞]:

• a = 5: The value of a in both min_key and max_key is 5, which is guaranteed by the range and does not need to be evaluated. Therefore, this predicate is eliminated.
• b > 3: The value of b in min_key is 3. However, the lower bound for b is >= 3, whereas the predicate requires > 3. Because their semantics differ, this predicate cannot be eliminated and is retained.

After conversion

The condition actually evaluated at the SQL layer (where a = 5 has been eliminated):

SELECT * FROM t WHERE b > 3

Prerequisites

• The TaurusDB kernel version is 2.0.42.230600 or later. For details about how to check the kernel version, see How Can I Check the Version of a TaurusDB Instance?
• The rds_empty_redundant_check_in_range_scan parameter is set to ON. For details, see Modifying TaurusDB Instance Parameters.

Supported Predicate Types

Supported Query Statements

• SELECT
• INSERT ... SELECT
• REPLACE ... SELECT
• Views and prepared statements
• Non-leading columns in composite indexes
• DESC indexes
• NULL-byte processing for nullable columns

Constraints

• Only simple range scans (single-interval scans) are supported. Index merge and skip scans are not supported.
• Only a single interval (ranges.size() == 1) is supported. Multiple disjoint intervals generated by OR clauses are not supported.
• Prefix indexes (where a prefix length is defined for the index column, such as col(10)) are not supported.
• Columns of the BIT type are not supported.
• Dynamic range scans (where the scan range is determined only at execution time) are not supported.
• Predicate elimination is not supported within OR clauses. Redundancy check is temporarily disabled for OR clauses to ensure correctness.
• NOT BETWEEN is not supported.
• Predicate elimination is not supported for NULL-complemented tables in outer joins.
• When NDP might be enabled, redundant condition elimination is automatically disabled to prioritize the performance of NDP pushdown.
• The EXPLAIN output of the Hypergraph optimizer has not yet been adapted for this feature.

How to Use

This feature is controlled by the session parameter rds_empty_redundant_check_in_range_scan.

Examples

1. Create a test table and insert data.

   CREATE TABLE t1 (a INT, b INT, INDEX(a, b));
   INSERT INTO t1 VALUES (1,2),(2,3),(3,3),(4,3),(5,5),(2,5),(3,7);

2. Disable redundant condition elimination and view the execution plan.

   SET SESSION rds_empty_redundant_check_in_range_scan = OFF;
   EXPLAIN FORMAT=TREE SELECT * FROM t1 WHERE a = 5 AND b > 3;

   The execution plan retains the Filter layer. The SQL layer must evaluate both predicates a = 5 and b > 3 for every row.

   mysql> EXPLAIN FORMAT=TREE SELECT * FROM t1 WHERE a = 5 AND b > 3;
   +-----------------------------------------------------------------------------------------------------------------------+
   | EXPLAIN                                                                                                               |
   +-----------------------------------------------------------------------------------------------------------------------+
   | -> Filter: ((t1.a = 5) and (t1.b > 3))  (cost=0.46 rows=1)
       -> Index range scan on t1 using a  (cost=0.46 rows=1)
   +-----------------------------------------------------------------------------------------------------------------------+

3. Enable redundant condition elimination and view the execution plan.

   SET SESSION rds_empty_redundant_check_in_range_scan = ON;
   EXPLAIN FORMAT=TREE SELECT * FROM t1 WHERE a = 5 AND b > 3;

   The Filter layer disappears. Both predicates (a = 5 and b > 3) are implicitly guaranteed by the upper and lower bounds of the range scan, so the SQL layer does not need to re-evaluate them.

   mysql> EXPLAIN FORMAT=TREE SELECT * FROM t1 WHERE a = 5 AND b > 3;
   +--------------------------------------------------------+
   | EXPLAIN                                                |
   +--------------------------------------------------------+
   | -> Index range scan on t1 using a  (cost=0.46 rows=1)
   +--------------------------------------------------------+

4. Verify query result consistency.

   SET SESSION rds_empty_redundant_check_in_range_scan = OFF;
   SELECT * FROM t1 WHERE a = 2 AND b > 2;

   SET SESSION rds_empty_redundant_check_in_range_scan = ON;
   SELECT * FROM t1 WHERE a = 2 AND b > 2;

   The query results are identical in both modes:

   +------+------+
   | a    | b    |
   +------+------+
   |    2 |    3 |
   |    2 |    5 |
   +------+------+

Performance Test

The following test is performed on a 10-million-row wide table using equality-plus-range predicates on a composite primary key. This test aims to verify the query performance benefits of redundant condition elimination during range scans.

1. Prepare test data.

   SET SESSION cte_max_recursion_depth = 10000001;

   DROP TABLE IF EXISTS big_test;
   CREATE TABLE big_test (
   a INT NOT NULL,
   b INT NOT NULL,
   c INT NOT NULL,
   d INT NOT NULL,
   e INT NOT NULL,
   f1 VARCHAR(200),
   f2 VARCHAR(200),
   f3 VARCHAR(200),
   PRIMARY KEY (a, b, c, d, e)
   ) ENGINE=InnoDB ROW_FORMAT=COMPACT;

   INSERT INTO big_test (a, b, c, d, e, f1, f2, f3)
   WITH RECURSIVE seq AS (
   SELECT 1 AS n
   UNION ALL
   SELECT n+1 FROM seq WHERE n < 10000000
   )
   SELECT
   (n-1) DIV 2000000 + 1 AS a,
   (n-1) DIV 200000 MOD 10 + 1 AS b,
   (n-1) DIV 20000 MOD 10 + 1 AS c,
   (n-1) DIV 200 MOD 100 + 1 AS d,
   n AS e,
   REPEAT(CONCAT('val', n MOD 1000), 5) AS f1,
   REPEAT(CONCAT('key', n MOD 500), 5) AS f2,
   REPEAT(CONCAT('dat', n MOD 200), 5) AS f3
   FROM seq;

2. Compare execution plans.

   The query WHERE a = 3 AND b > 3 matches approximately 2 million rows. Here, a = 3 is a redundant predicate because it is already guaranteed by the lower bound of the range.

   • When redundant condition elimination is disabled, the EXPLAIN output displays Using where, indicating that the SQL layer must evaluate a = 3 AND b > 3 row by row.

     SET SESSION rds_empty_redundant_check_in_range_scan = OFF;

     EXPLAIN SELECT SUM(LENGTH(f1)) FROM big_test WHERE a = 3 AND b > 3;
     +----+-------------+----------+-------+---------------+---------+---------+------+---------+----------+-------------+
     | id | select_type | table    | type  | possible_keys | key     | key_len | ref  | rows    | filtered | Extra       |
     +----+-------------+----------+-------+---------------+---------+---------+------+---------+----------+-------------+
     |  1 | SIMPLE      | big_test | range | PRIMARY       | PRIMARY | 8       | NULL | 2719004 |   100.00 | Using where |
     +----+-------------+----------+-------+---------------+---------+---------+------+---------+----------+-------------+

   • When redundant condition elimination is enabled, a = 3 is eliminated and the Extra column in the EXPLAIN output no longer displays Using where.

     SET SESSION rds_empty_redundant_check_in_range_scan = ON;

     EXPLAIN SELECT SUM(LENGTH(f1)) FROM big_test WHERE a = 3 AND b > 3;
     +----+-------------+----------+-------+---------------+---------+---------+------+---------+----------+-------+
     | id | select_type | table    | type  | possible_keys | key     | key_len | ref  | rows    | filtered | Extra |
     +----+-------------+----------+-------+---------------+---------+---------+------+---------+----------+-------+
     |  1 | SIMPLE      | big_test | range | PRIMARY       | PRIMARY | 8       | NULL | 2719004 |   100.00 | NULL  |
     +----+-------------+----------+-------+---------------+---------+---------+------+---------+----------+-------+

3. Compare query execution times.

   SET SESSION rds_empty_redundant_check_in_range_scan = OFF;
   SELECT SUM(LENGTH(f1)) FROM big_test WHERE a = 3 AND b > 3;

   SET SESSION rds_empty_redundant_check_in_range_scan = ON;
   SELECT SUM(LENGTH(f1)) FROM big_test WHERE a = 3 AND b > 3;

   • Redundant condition elimination disabled

     mysql> SELECT SUM(LENGTH(f1)) FROM big_test WHERE a = 3 AND b > 3;
     +-----------------+
     | SUM(LENGTH(f1)) |
     +-----------------+
     |        41230000 |
     +-----------------+
     1 row in set (0.69 sec)

   • Redundant condition elimination enabled

     mysql> SELECT SUM(LENGTH(f1)) FROM big_test WHERE a = 3 AND b > 3;
     +-----------------+
     | SUM(LENGTH(f1)) |
     +-----------------+
     |        41230000 |
     +-----------------+
     1 row in set (0.51 sec)

   Table 3 Query time comparison

   Mode	Extra	Time Required	Description
   OFF	Using where	0.69s	The SQL layer evaluates a = 3 AND b > 3 row by row for about 2 million rows.
   ON	NULL	0.51s	a = 3 is eliminated and only b > 3 is evaluated. Performance improves by about 26%.