Bug #67044 Secondary index updates make consistent reads do O(N^2) undo page lookups
Submitted: 2 Oct 2012 0:21 Modified: 29 Dec 2012 16:37
Reporter: Yoshinori Matsunobu (OCA) Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: InnoDB Plugin storage engine Severity:S5 (Performance)
Version:5.1, 5.5, 5.6 OS:Any
Assigned to: CPU Architecture:Any

[2 Oct 2012 0:21] Yoshinori Matsunobu
Description:
See how to repeat section

How to repeat:
create table t1 (id int primary key, value int, value2 int, value3 int, index(value,value2)) engine=innodb;

insert into t1 values (1,1,1,1),(2,2,2,2),(3,3,3,3),(4,4,4,4),(5,5,5,5),(6,6,6,6),(7,7,7,7),(8,8,8,8),(9,9,9,9),(10,10,10,10),(11,11,11,11),(12,12,12,12),(13,13,13,13),(14,14,14,14),(15,15,15,15),(16,16,16,16),(17,17,17,17),(18,18,18,18),(19,19,19,19),(20,20,20,20);

client1:
start transaction with consistent snapshot;

client2: (updating a secondary indexed column for 1,000 times)
mysqlslap --query="update test.t1 set value2=value2+1, value3=value3+1 where id=2" --iterations=1000

client1:
show global status like 'innodb_buffer_pool_read_requests';
# forcing lookups by using secondary index
select * from t1 force index(value) where value=2;
show global status like 'innodb_buffer_pool_read_requests';

Then innodb_buffer_pool_read_requests increases around 1,000,000 (1,000^2).

If you update 100,000 times from client2, select from client1 will take very very long time, and can't be killed.

The select internally did the following O(N^2) steps. I verified on 5.1/5.5.27 and 5.6.7.
row_search_for_mysql
-> row_sel_get_clust_rec_for_mysql (called N times)
-> row_vers_build_for_consistent_read
-> for loop: trx_undo_prev_version_build() (called N times)
-> buf_page_get()

The real problem is the select can not be terminated from outside (KILL QUERY) because it takes N*N at row_search_for_mysql function call.
If the select does not use seconary index, it did not cost O(N^2) and finished more quickly. But not using secondary index is not always possible.
[29 Dec 2012 16:37] Erlend Dahl
This was fixed in 5.1.67, 5.5.29 and 5.6.9.