There are some records in the dataset which trigger the table scan effect, and other which do not: dbcache05>explain DELETE FROM BIG_STORAGE_TOKU WHERE HASH_ID = SHA2('30398', 256); +----+-------------+------------------+------+---------------+------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+------------------+------+---------------+------+---------+------+--------+-------------+ | 1 | SIMPLE | BIG_STORAGE_TOKU | ALL | HASH_ID_IX | NULL | NULL | NULL | 100014 | Using where | +----+-------------+------------------+------+---------------+------+---------+------+--------+-------------+ 1 row in set (0.00 sec) dbcache05>explain DELETE FROM BIG_STORAGE_TOKU WHERE HASH_ID = SHA2('70164', 256); +----+-------------+------------------+-------+---------------+------------+---------+-------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+------------------+-------+---------------+------------+---------+-------+------+-------------+ | 1 | SIMPLE | BIG_STORAGE_TOKU | range | HASH_ID_IX | HASH_ID_IX | 64 | const | 14 | Using where | +----+-------------+------------------+-------+---------------+------------+---------+-------+------+-------------+ 1 row in set (0.00 sec) dbcache05>SET optimizer_trace='enabled=on'; Query OK, 0 rows affected (0.00 sec) dbcache05>DELETE FROM BIG_STORAGE_TOKU WHERE HASH_ID = SHA2('70164', 256); Query OK, 1 row affected (0.00 sec) dbcache05>SELECT trace FROM information_schema.optimizer_trace \G *************************** 1. row *************************** trace: { "steps": [ { "condition_processing": { "condition": "WHERE", "original_condition": "(`BIG_STORAGE_TOKU`.`HASH_ID` = sha2('70164',256))", "steps": [ { "transformation": "equality_propagation", "resulting_condition": "multiple equal(sha2('70164',256), `BIG_STORAGE_TOKU`.`HASH_ID`)" }, { "transformation": "constant_propagation", "resulting_condition": "multiple equal(sha2('70164',256), `BIG_STORAGE_TOKU`.`HASH_ID`)" }, { "transformation": "trivial_condition_removal", "resulting_condition": "multiple equal(sha2('70164',256), `BIG_STORAGE_TOKU`.`HASH_ID`)" } ] } }, { "table": "`BIG_STORAGE_TOKU`", "range_analysis": { "table_scan": { "rows": 100022, "cost": 53347 }, "potential_range_indices": [ { "index": "HASH_ID_IX", "usable": true, "key_parts": [ "HASH_ID" ] }, { "index": "EXPIRE_DATE_IX2", "usable": true, "key_parts": [ "EXPIRE_DATE" ] } ], "setup_range_conditions": [ ], "group_index_range": { "chosen": false, "cause": "no_join" }, "analyzing_range_alternatives": { "range_scan_alternatives": [ { "index": "HASH_ID_IX", "ranges": [ "ffff925a44dfc908915841bdafe81d3ee3b5238610e4901d0d806e4740881084 <= HASH_ID <= ffff925a44dfc908915841bdafe81d3ee3b5238610e4901d0d806e4740881084" ], "index_dives_for_eq_ranges": true, "rowid_ordered": true, "using_mrr": false, "index_only": false, "rows": 14, "cost": 17.81, "chosen": true } ] }, "chosen_range_access_summary": { "range_access_plan": { "type": "range_scan", "index": "HASH_ID_IX", "rows": 14, "ranges": [ "ffff925a44dfc908915841bdafe81d3ee3b5238610e4901d0d806e4740881084 <= HASH_ID <= ffff925a44dfc908915841bdafe81d3ee3b5238610e4901d0d806e4740881084" ] }, "rows_for_plan": 14, "cost_for_plan": 17.81, "chosen": true } } } ] } 1 row in set (0.00 sec) dbcache05>DELETE FROM BIG_STORAGE_TOKU WHERE HASH_ID = SHA2('30398', 256); Query OK, 1 row affected (2.40 sec) dbcache05>SELECT trace FROM information_schema.optimizer_trace \G *************************** 1. row *************************** trace: { "steps": [ { "condition_processing": { "condition": "WHERE", "original_condition": "(`BIG_STORAGE_TOKU`.`HASH_ID` = sha2('30398',256))", "steps": [ { "transformation": "equality_propagation", "resulting_condition": "multiple equal(sha2('30398',256), `BIG_STORAGE_TOKU`.`HASH_ID`)" }, { "transformation": "constant_propagation", "resulting_condition": "multiple equal(sha2('30398',256), `BIG_STORAGE_TOKU`.`HASH_ID`)" }, { "transformation": "trivial_condition_removal", "resulting_condition": "multiple equal(sha2('30398',256), `BIG_STORAGE_TOKU`.`HASH_ID`)" } ] } }, { "table": "`BIG_STORAGE_TOKU`", "range_analysis": { "table_scan": { "rows": 100021, "cost": 53347 }, "potential_range_indices": [ { "index": "HASH_ID_IX", "usable": true, "key_parts": [ "HASH_ID" ] }, { "index": "EXPIRE_DATE_IX2", "usable": true, "key_parts": [ "EXPIRE_DATE" ] } ], "setup_range_conditions": [ ], "group_index_range": { "chosen": false, "cause": "no_join" }, "analyzing_range_alternatives": { "range_scan_alternatives": [ { "index": "HASH_ID_IX", "ranges": [ "ffff8ed56f65caf0019f90d65b7f158b862efcab5c4517a76c01c73acf92d99b <= HASH_ID <= ffff8ed56f65caf0019f90d65b7f158b862efcab5c4517a76c01c73acf92d99b" ], "index_dives_for_eq_ranges": true, "rowid_ordered": true, "using_mrr": false, "index_only": false, "rows": 181860, "cost": 218233, "chosen": false, "cause": "cost" } ] } } } ] } 1 row in set (0.01 sec)