MySQL Bugs: #84958: InnoDB's MVCC has O(N^2) behaviors

Bug #84958	InnoDB's MVCC has O(N^2) behaviors
Submitted:	10 Feb 2017 23:18	Modified:	3 Aug 2018 17:13
Reporter:	Domas Mituzas	Email Updates:
Status:	Closed	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

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.

Hello Domas,

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

Thanks,
Umesh

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.

Submitted a partial fix through OCA. Patch author Alexey Midenkov

Thank you for your contribution :-)

Posted by developer:
 
Fixed as of the upcoming 8.0.13 release, and here's the changelog entry:

A helper class was introduced to improve performance associated with
reading from secondary keys when there are multiple versions of the same
row.

Posted by developer:
 
Closing again. No change to changelog entry.