Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-20301

InnoDB's MVCC has O(N^2) behaviors

    XMLWordPrintable

    Details

      Description

      Originally described here: https://bugs.mysql.com/bug.php?id=84958

      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.

      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*

      Analysis

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              midenok Aleksey Midenkov
              Reporter:
              midenok Aleksey Midenkov
              Votes:
              1 Vote for this issue
              Watchers:
              4 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: