Bug #50939 Loose Index Scan unduly relies on engine to remember range endpoints

• Submitted: 5 Feb 2010 9:10
• Modified: 14 Oct 2010 14:09
• Reporter: Martin Hansson
• Status: Closed
• Category: MySQL Server: Optimizer
• Severity: S5 (Performance)
• Version: all
• OS: Any
• Assigned to: Martin Hansson
• CPU Architecture: Any
• Tags: GROUP BY, loose index scan, partition, performance

[5 Feb 2010 9:10] Martin Hansson

Description:
This bug was found while examining Bug#48229. The impact of the bug is similar; performance degradation of GROUP BY on partitioned tables. However, the cause of said bug was an error inside the partitioning engine, causing it to report too high a cost for the best plan which led to a suboptimal plan (Loose Index Scan) being chosen, all other things being equal. But the performance of loose index scan in that case was suspiciously poor. When considering the case in which loose index scan *is* the optimal plan, the performance is much worse on partitioning tables than any other. This is because the implementation of LIS relies on the engine to remember each "skip target", i.e. the local maximum for each group. This works by coincidence in MyISAM but not in Partition, causing LIS to degenerate into an index scan.

How to repeat:
See attached test case

Suggested fix:
Coming shortly.

[5 Feb 2010 9:21] Martin Hansson

test case

Attachment: bug50939.test (application/octet-stream, text), 1.21 KiB.

[19 Mar 2010 10:49] Bugs System

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/103806

3407 Martin Hansson	2010-03-19
      Bug#50939: Loose Index Scan unduly relies on engine to
      remember range endpoints
      
      The Loose Index Scan optimization keeps track of a sequence
      of intervals. For the current interval it maintains the
      current interval's endpoints. But the maximum endpoint was
      not stored in the SQL layer; rather, it relied on the
      storage engine to retain this value in-between reads. By
      coincidence this holds for MyISAM and InnoDB. Not for the
      partitioning engine, however.
      
      Fixed by making the key values iterator 
      (QUICK_RANGE_SELECT) keep track of the current maximum endpoint.
      This is also more efficient as we save a call through the
      handler API in case of open-ended intervals.
      
      The code to calculate endpoints was extracted into 
      separate methods in QUICK_RANGE_SELECT, and it was possible to
      get rid of some code duplication as part of fix.

[6 Apr 2010 14:05] Bugs System

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/105090

3444 Martin Hansson	2010-04-06
      Bug#50939: Loose Index Scan unduly relies on engine to
      remember range endpoints
      
      The Loose Index Scan optimization keeps track of a sequence
      of intervals. For the current interval it maintains the
      current interval's endpoints. But the maximum endpoint was
      not stored in the SQL layer; rather, it relied on the
      storage engine to retain this value in-between reads. By
      coincidence this holds for MyISAM and InnoDB. Not for the
      partitioning engine, however.
      
      Fixed by making the key values iterator 
      (QUICK_RANGE_SELECT) keep track of the current maximum endpoint.
      This is also more efficient as we save a call through the
      handler API in case of open-ended intervals.
      
      The code to calculate endpoints was extracted into 
      separate methods in QUICK_RANGE_SELECT, and it was possible to
      get rid of some code duplication as part of fix.

[7 May 2010 13:31] Bugs System

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/107756

3373 Martin Hansson	2010-05-07
      Bug#50939: Loose Index Scan unduly relies on engine to
      remember range endpoints
      
      The Loose Index Scan optimization keeps track of a sequence
      of intervals. For the current interval it maintains the
      current interval's endpoints. But the maximum endpoint was
      not stored in the SQL layer; rather, it relied on the
      storage engine to retain this value in-between reads. By
      coincidence this holds for MyISAM and InnoDB. Not for the
      partitioning engine, however.
      
      Fixed by making the key values iterator 
      (QUICK_RANGE_SELECT) keep track of the current maximum endpoint.
      This is also more efficient as we save a call through the
      handler API in case of open-ended intervals.
      
      The code to calculate endpoints was extracted into 
      separate methods in QUICK_RANGE_SELECT, and it was possible to
      get rid of some code duplication as part of fix.

[7 May 2010 15:08] Bugs System

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/107768

3373 Martin Hansson	2010-05-07
      Bug#50939: Loose Index Scan unduly relies on engine to
      remember range endpoints
      
      The Loose Index Scan optimization keeps track of a sequence
      of intervals. For the current interval it maintains the
      current interval's endpoints. But the maximum endpoint was
      not stored in the SQL layer; rather, it relied on the
      storage engine to retain this value in-between reads. By
      coincidence this holds for MyISAM and InnoDB. Not for the
      partitioning engine, however.
      
      Fixed by making the key values iterator 
      (QUICK_RANGE_SELECT) keep track of the current maximum endpoint.
      This is also more efficient as we save a call through the
      handler API in case of open-ended intervals.
      
      The code to calculate endpoints was extracted into 
      separate methods in QUICK_RANGE_SELECT, and it was possible to
      get rid of some code duplication as part of fix.

[10 May 2010 7:23] Bugs System

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/107818

3376 Martin Hansson	2010-05-10
      Bug#50939: Loose Index Scan unduly relies on engine to
      remember range endpoints
      
      The Loose Index Scan optimization keeps track of a sequence
      of intervals. For the current interval it maintains the
      current interval's endpoints. But the maximum endpoint was
      not stored in the SQL layer; rather, it relied on the
      storage engine to retain this value in-between reads. By
      coincidence this holds for MyISAM and InnoDB. Not for the
      partitioning engine, however.
      
      Fixed by making the key values iterator 
      (QUICK_RANGE_SELECT) keep track of the current maximum endpoint.
      This is also more efficient as we save a call through the
      handler API in case of open-ended intervals.
      
      The code to calculate endpoints was extracted into 
      separate methods in QUICK_RANGE_SELECT, and it was possible to
      get rid of some code duplication as part of fix.

[10 May 2010 12:26] Bugs System

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/107837

4064 Martin Hansson	2010-05-10 [merge]
      Merge of fix for Bug#50939.

[28 May 2010 6:14] Bugs System

Pushed into mysql-next-mr (revid:[e-mail]-20100524190136-egaq7e8zgkwb9aqi) (version source revid:[e-mail]-20100512070920-xgpmqeytp0gc183c) (pib:16)

[28 May 2010 6:42] Bugs System

Pushed into 6.0.14-alpha (revid:[e-mail]-20100524190941-nuudpx60if25wsvx) (version source revid:[e-mail]-20100514054548-91z72f0mcskr84kj) (merge vers: 6.0.14-alpha) (pib:16)

[28 May 2010 7:10] Bugs System

Pushed into 5.5.5-m3 (revid:[e-mail]-20100524185725-c8k5q7v60i5nix3t) (version source revid:[e-mail]-20100511082753-a4r5a38fe9nuf5fw) (merge vers: 5.5.5-m3) (pib:16)

[2 Jun 2010 8:50] Bugs System

Pushed into 5.1.48 (revid:[e-mail]-20100602084411-2yu607bslbmgufl3) (version source revid:[e-mail]-20100510072323-5333n2u5u0mgkwu1) (merge vers: 5.1.47) (pib:16)

[9 Jun 2010 0:47] Paul DuBois

Noted in 5.1.48, 5.5.0, 6.0.14 changelogs.

The Loose Index Scan optimization method assumed that it could on the
storage engine to maintain interval endpoint information, which was
not true for the partitioning engine.

[10 Aug 2010 8:51] Bjørn Munch

See Bug #54444 for an unintended side effect of the test additions.

[14 Oct 2010 8:37] Bugs System

Pushed into mysql-5.1-telco-7.0 5.1.51-ndb-7.0.20 (revid:[e-mail]-20101014082627-jrmy9xbfbtrebw3c) (version source revid:[e-mail]-20100513074652-0cvlhgkesgbb2bfh) (merge vers: 5.5.5-m3) (pib:21)

[14 Oct 2010 8:52] Bugs System

Pushed into mysql-5.1-telco-6.3 5.1.51-ndb-6.3.39 (revid:[e-mail]-20101014083757-5qo48b86d69zjvzj) (version source revid:[e-mail]-20100513074652-0cvlhgkesgbb2bfh) (merge vers: 5.5.5-m3) (pib:21)

[14 Oct 2010 9:07] Bugs System

Pushed into mysql-5.1-telco-6.2 5.1.51-ndb-6.2.19 (revid:[e-mail]-20101014084420-y54ecj85j5we27oa) (version source revid:[e-mail]-20100513074652-0cvlhgkesgbb2bfh) (merge vers: 5.5.5-m3) (pib:21)

[14 Oct 2010 14:09] Jon Stephens

Already documented in the 5.1.48 changelog; no additional changelog entries required. Set back to Closed state.