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

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

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

          causes

          Bug - A problem which impairs or prevents the functions of the product. MDEV-20389 The test innodb.innodb_bug84958 fails intermittently

          • Major - Major loss of function.
          • Closed

          Bug - A problem which impairs or prevents the functions of the product. MDEV-22924 Warning InnoDB: Index 'Marvão_idx3' contains 36 entries, should be 37.

          • Blocker - Blocks development and/or testing work, production could not run.
          • Closed
          is blocked by

          Bug - A problem which impairs or prevents the functions of the product. MDEV-20341 Unstable innodb.innodb_bug14704286

          • Major - Major loss of function.
          • Closed
          relates to

          New Feature - A new feature of the product, which has yet to be developed. MDEV-17598 InnoDB index option for per-record transaction ID

          • Major - Major loss of function.
          • Open

          Bug - A problem which impairs or prevents the functions of the product. MDEV-31589 Secondary index MVCC access is unnecessarily inefficient

          • Critical - Crashes, loss of data, severe memory leak.
          • Stalled
          links to

          Web Link How small changes impact complex systems – MySQL example

          Activity

            Transition Time In Source Status Execution Times
            Aleksey Midenkov made transition -
            Open In Progress
            		12h 43m 1
            Aleksey Midenkov made transition -
            In Progress In Review
            		46s 1
            Thirunarayanan Balathandayuthapani made transition -
            In Review Stalled
            		3d 6h 53m 1
            Aleksey Midenkov made transition -
            Stalled In Progress
            		1d 3h 46m 1
            Aleksey Midenkov made transition -
            In Progress Closed
            		22h 18m 1

            People

              midenok Aleksey Midenkov
              midenok Aleksey Midenkov
              Votes:
              1 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Git Integration

                  Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.