Bug #84958 InnoDB's MVCC has O(N^2) behaviors
Submitted: 10 Feb 2017 23:18 Modified: 13 Feb 2017 7:47
Reporter: Domas Mituzas Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: InnoDB storage engine Severity:S2 (Serious)
Version:5.6.*, 5.6.35 OS:Any
Assigned to: CPU Architecture:Any

[10 Feb 2017 23:18] Domas Mituzas
Description:
if there're multiple row versions in InnoDB, reading one row from PK may have O(N) complexity and reading from secondary keys may have O(N^2) complexity.

Also, is this https://bugs.mysql.com/bug.php?id=67044 ? 

How to repeat:
setup: create table t1 (a int, b int, c int, primary key(a,b), key (b,c)) engine=InnoDB;

T1: BEGIN; SELECT * FROM t1;

T2: 10000 * INSERT INTO t1 VALUES (1,2,3) ON DUPLICATE KEY UPDATE c=c+1

T1: SELECT * FROM t1 FORCE INDEX (PRIMARY)
(this will be immediate and bump Innodb_buffer_pool_read_requests by ~10k)

T1: SELECT * FROM t1 FORCE INDEX (b)
(this will be not immediate and bump Innodb_buffer_pool_read_requests by ~100000k or ~100m or....)

Operator: *weep* *sob* *weep*

Suggested fix:
Do O(N) or O(log(N)) or something. Will take O(1) complexity solutions too.

O(N^2) is too painful, as it may take minutes to read one row in moderate conditions.
[10 Feb 2017 23:21] Domas Mituzas
.
[13 Feb 2017 7:47] Umesh Shastry
Hello Domas,

Thank you for the report and feedback.
Observed this with 5.6.35 build.

Thanks,
Umesh
[2 Nov 2017 8:49] Laurynas Biveinis
A partial fix for bug 84985

(*) I confirm the code being submitted is offered under the terms of the OCA, and that I am authorized to contribute it.

Contribution: bug84985_partial.diff (application/octet-stream, text), 5.61 KiB.

[2 Nov 2017 8:50] Laurynas Biveinis
Submitted a partial fix through OCA. Patch author Alexey Midenkov
[8 Nov 2017 23:37] Sunny Bains
Thank you for your contribution :-)