Bug #88103 Contribution by Facebook: Support loose index range scans for low cardinali ...
Submitted: 16 Oct 2017 2:07 Modified: 31 Jul 17:27
Reporter: FBContrib Admin Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.6 OS:Any
Assigned to: Sergey Glukhov CPU Architecture:Any
Triage: Needs Triage: D5 (Feature request)

[16 Oct 2017 2:07] FBContrib Admin
Description:
Background innformation provided by Facebook:
Abstract:

This diff improves the optimizer range scans for certain queries. Suppose we have the following:

  CREATE TABLE tbl (

    a int,

    b int,

    c int,

    primary key (a, b, c)

  );

  SELECT * FROM tbl WHERE a = 5 AND c > 100 ORDER BY a, b, c;

The current behavior in MySQL is to do a range scan on the whole range where a = 5, and then filter using the c > 100 predicate. However, we can be smarter than this.

Instead, we do a loose index scan by scanning over distinct (a, b), and then doing a subrange scan on that distinct prefix for c > 100.

The implementation is heavily inspired by the existing loose index scan done for GROUP BY and DISTINCT queries. A new TABLE_READ_PLAN and QUICK_SELECT_I that implements this strategy was added. We check before creating the TABLE_READ_PLAN whether this plan is applicable or not. After that, we execute the loose index scan in the QUICK_LOOSE_RANGE_SELECT::get_next method.

Repo: https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_mysql_mysql-2Dserver&d=DwI... 

Patch on top of 5.6.35: https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_mysql_mysql-2Dserver_tree_... 

Facebook mysql-5.6 commit: https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_facebook_mysql-2D5.6_commi... 

How to repeat:
See description

Suggested fix:
See contribution code attached
[16 Oct 2017 2:07] FBContrib Admin
Support loose index range scans for low cardinality column predicates 
(*) This code is contributed under the Facebook agreement

Contribution: fb_patch_3.txt (text/plain), 142.95 KiB.

[17 Oct 2017 23:28] Omer Barnir
Thanks for your contribution, we will incorporate the patch into MySQL.
[24 Jun 0:06] monty solomon
What the patch added to MySQL?
[31 Jul 17:27] Paul Dubois
Posted by developer:
 
Fixed in 8.0.13.

The optimizer now supports a Skip Scan access method that enables range access to be used in previously inapplicable situations to improve query performance. For more information, see https://dev.mysql.com/doc/refman/8.0/en/range-optimization.html. Thanks to Facebook for the patch on which this access method is based.