Chavy, thanks for the update. I tried with the data and agreed that there is a bug with DELETE query when the WHERE clause has conditions on >1 columns. I would suggest you to open a bug with MySQL at http://bugs.mysql.com.
Here are what I observed on community v5.6.19. The EXPLAIN plan to find the rows to delete is:
mysql> explain select * from db_test_table where regtime != 1407760802 and bid = 2;
+----+-------------+---------------+-------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+---------------+-------+---------------+------+---------+------+--------+-------------+
| 1 | SIMPLE | db_test_table | range | idx | idx | 8 | NULL | 139179 | Using where |
+----+-------------+---------------+-------+---------------+------+---------+------+--------+-------------+
1 row in set (0.00 sec)
The SELECT query ran fast and examined relevant rows as expected:
# Query_time: 1.023239 Lock_time: 0.000159 Rows_sent: 1 Rows_examined: 135667
SET timestamp=1409205734;
select count(*) from db_test_table where regtime != 1407760802 and bid = 2;
DELETE query took a long time and examined hundreds of millions of rows, same as you observed. I guess there is a faulty repeat of loops. However DELETE with only one criteria rans fast:
# Query_time: 1.922281 Lock_time: 0.000127 Rows_sent: 0 Rows_examined: 135551
SET timestamp=1409205948;
delete from db_test_table where regtime != 1407760802;
I suspected the culprit had to do with composite index, but problem remained after I changed the composite index to a single column index.
mysql> show create table db_test_table\G *************************** 1. row ***************************
Table: db_test_table
Create Table: CREATE TABLE `db_test_table` (
`bid` smallint(5) unsigned NOT NULL,
`pid` smallint(5) unsigned NOT NULL,
`regtime` bigint(20) unsigned NOT NULL,
`vid` mediumint(9) NOT NULL AUTO_INCREMENT,
PRIMARY KEY (`vid`),
KEY `idx` (`regtime`) USING BTREE
) ENGINE=MEMORY AUTO_INCREMENT=142064 DEFAULT CHARSET=binary ROW_FORMAT=DYNAMIC;
------ Kill the query since it took too long
# Query_time: 266.423611 Lock_time: 0.000125 Rows_sent: 0 Rows_examined: 38114863
SET timestamp=1409207983;
delete from db_test_table where regtime != 1407760802 and bid = 2;
-------- Delete on single column remains fast
# Query_time: 2.225477 Lock_time: 0.000119 Rows_sent: 0 Rows_examined: 136506
SET timestamp=1409206867;
delete from db_test_table where regtime != 1407760802;
