[MDEV-9457] Poor query plan chosen for ORDER BY query by a recent 10.1 Created: 2016-01-23  Updated: 2016-02-03  Resolved: 2016-01-24

Status: Closed
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.1.10
Fix Version/s: 10.1.11

Type: Bug Priority: Major
Reporter: Sergei Petrunia Assignee: Sergei Petrunia
Resolution: Fixed Votes: 0
Labels: optimizer, order-by-optimization, regression


 Description   

Discovered as part of MDEV-9420. See these comments:

https://mariadb.atlassian.net/browse/MDEV-9420?focusedCommentId=80164&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-80164

https://mariadb.atlassian.net/browse/MDEV-9420?focusedCommentId=80165&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-80165

Copying here:
Checking problem #1.

MariaDB 10.0:

MariaDB [j10]> explain select * from point_activite 
WHERE `id_activity_list` = 1479 AND `id_contact_Script` = 2075347 AND `id_contact_campaign_pass` = 1920183 \G
 
*************************** 1. row ***************************
 
           id: 1
 
  select_type: SIMPLE
 
        table: point_activite
 
         type: index_merge
 
possible_keys: id_contact_Script,id_activity_list,id_contact_campaign_pass
 
          key: id_contact_campaign_pass,id_contact_Script
 
      key_len: 9,9
 
          ref: NULL
 
         rows: 1
 
        Extra: Using intersect(id_contact_campaign_pass,id_contact_Script); Using where
 

MariaDB [j10]> explain select * from point_activite 
WHERE `id_activity_list` = 1479 AND `id_contact_Script` = 2075347 AND `id_contact_campaign_pass` = 1920183 
ORDER BY `IDPoint_Activite`\G
 
*************************** 1. row ***************************
 
           id: 1
 
  select_type: SIMPLE
 
        table: point_activite
 
         type: index_merge
 
possible_keys: id_contact_Script,id_activity_list,id_contact_campaign_pass
 
          key: id_contact_campaign_pass,id_contact_Script
 
      key_len: 9,9
 
          ref: NULL
 
         rows: 1
 
        Extra: Using intersect(id_contact_campaign_pass,id_contact_Script); Using where; Using filesort

So, in 10.0, the plan is always to use index_merge to produce one row. Actually, two rows are produced and the query finishes in 0.05 sec or less.

In 10.1.10:

MariaDB [j10]> explain select * from point_activite 
WHERE `id_activity_list` = 1479 AND `id_contact_Script` = 2075347 AND `id_contact_campaign_pass` = 1920183\G
 
*************************** 1. row ***************************
 
           id: 1
 
  select_type: SIMPLE
 
        table: point_activite
 
         type: index_merge
 
possible_keys: id_contact_Script,id_activity_list,id_contact_campaign_pass
 
          key: id_contact_campaign_pass,id_contact_Script
 
      key_len: 9,9
 
          ref: NULL
 
         rows: 1
 
        Extra: Using intersect(id_contact_campaign_pass,id_contact_Script); Using where

The same so far. Adding ORDER BY:

explain select * from point_activite 
WHERE `id_activity_list` = 1479 AND `id_contact_Script` = 2075347 AND `id_contact_campaign_pass` = 1920183 
ORDER BY `IDPoint_Activite`\G
 
*************************** 1. row ***************************
 
           id: 1
 
  select_type: SIMPLE
 
        table: point_activite
 
         type: index
 
possible_keys: id_contact_Script,id_activity_list,id_contact_campaign_pass
 
          key: PRIMARY
 
      key_len: 8
 
          ref: NULL
 
         rows: 1997722
 
        Extra: Using where

And the plan becomes much worse. It wants to read nearly 2M rows. Execution takes 1 min 39 sec.

 Comments   
Comment by Sergei Petrunia [ 2016-01-23 ]

Copying a comment:
Trying to figure out why 10.0 works and 10.1 doesnt.

Both versions enter test_if_cheaper_ordering() and reach this line:

        if ((ref_key < 0 && (group || table->force_index || is_covering)) ||
 
            index_scan_time < read_time)

In both versions:

  • is_covering= true
  • read_time=2
  • index_scan_time=~2M

ref_key=64 in 10.0, while in 10.1 ref_key=-1.
Not sure what this difference means it's causing the bad query plan to be
chosen by 10.1 regardless its apparently very high cost.

Comment by Sergei Petrunia [ 2016-01-23 ]

The difference in passed ref_key value is caused by these lines in
test_if_skip_sort_order():

10.0:

    /* 
      assume results are not ordered when index merge is used 
      TODO: sergeyp: Results of all index merge selects actually are ordered 
      by clustered PK values.
 
    */
 
  
    if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
 
        quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT ||
 
        quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || 
        quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)
 
      ref_key= MAX_KEY;

10.1:

    /* 
      assume results are not ordered when index merge is used 
      TODO: sergeyp: Results of all index merge selects actually are ordered 
      by clustered PK values.
 
    */
 
  
    if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
 
        quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT ||
 
        quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || 
        quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)
 
      ref_key= -1;

The change was introduced by this commit:

commit 7ec655850397a0edfcea8c1fd82650824297e564
 
Author: Nirbhay Choubey <nirbhay@mariadb.com>
 
Date:   Fri Nov 6 14:38:03 2015 -0500
 
 
 
    MDEV-9021: MYSQLD SEGFAULTS WHEN BUILT USING --WITH-MAX-INDEXES=128

Here, Nirbhay and me were fixing the optimizer to work with MAX_KEY > 64, and also changed ref_key. That had an unintended consequence.

Comment by Sergei Petrunia [ 2016-01-23 ]

It is not clear what is the exact meaning of the difference in test_if_cheaper_ordering()'s behavior when invoked with ref_key=MAX_KEY or ref_key=-1.

test_if_cheaper_ordering() was introduced into mysql-5.5 by Gleb Schepa in 2010.

MySQL doesn't have hash join, so they don't have "hash_join_key_no=MAX_KEYS".

Looking at MySQL-5.5 code. The piece of code that we're having problem with looked like this:

    if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE || 
        quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || 
        quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)
 
      DBUG_RETURN(0);

other parts of test_if_skip_sort_order() use ref_key=-1 to denote "no key". MAX_KEY constant is not used anywhere.

The other place where test_if_cheaper_ordering called is get_index_for_order(). That function always passes ref_key=-1 as a parameter.

Comment by Sergei Petrunia [ 2016-01-23 ]

The ref_key=MAX_KEY in

    if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
 
        quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT ||
 
        quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || 
        quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)
 
      ref_key= MAX_KEY;

was introduced in

commit 7714739b2d6a50c4ca69421c0e19a9e08ff3b5c7
 
Author: Igor Babaev <igor@askmonty.org>
 
Date:   Thu Nov 1 14:54:33 2012 -0700
 
 
 
    Fixed bug mdev-585 (LP bug #637962)

Comment by Sergei Petrunia [ 2016-01-23 ]

Getting back to the condition in test_if_cheaper_ordering():

        if ((ref_key < 0 && (group || table->force_index || is_covering)) ||
 
            index_scan_time < read_time)

We here check if we should consider switching to using a different index. Line #2 says we should do it if using the new index is cheaper.

Line #1 gives some cases where we should do it regardless of what cost calculations say. My hypothesis is that the criteria are:
1. no index is used (ref_key < 0) and
2. one of the following:
2.1 group - doing a GROUP BY, where LIMIT doesn't help and we scan the whole table.
2.2 table->force_index - FORCE INDEX hint is used.
2.3 is_covering - the new index is covering. Doing full scan on a covering index is not much worse than doing a full table scan.

one can question these criteria, but at least the condition looks meaningful now.

Then let's look at the ref_key=-1 vs ref_key=MAX_KEY difference again. ref_key=-1 means "no index is used" while ref_key=MAX_KEY means "some index is used but not any particular index".

Comment by Sergei Petrunia [ 2016-01-24 ]

http://lists.askmonty.org/pipermail/commits/2016-January/008860.html

Generated at Thu Feb 08 07:34:49 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.