[MDEV-9457] Poor query plan chosen for ORDER BY query by a recent 10.1 - Jira

Details

Type: Bug
Status: Closed (View Workflow)
Priority: Major
Resolution: Fixed
Affects Version/s: 10.1.10
Fix Version/s: 10.1.11
Component/s: Optimizer
Labels:

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.

Attachments

Activity

Ascending order - Click to sort in descending order

Sergei Petrunia added a comment - 2016-01-23 18:21

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.

Sergei Petrunia added a comment - 2016-01-23 18:21 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.

Sergei Petrunia added a comment - 2016-01-23 18:25

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.

Sergei Petrunia added a comment - 2016-01-23 18:25 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.

Sergei Petrunia added a comment - 2016-01-23 19:19

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.

Sergei Petrunia added a comment - 2016-01-23 19:19 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.

Sergei Petrunia added a comment - 2016-01-23 19:54

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)

Sergei Petrunia added a comment - 2016-01-23 19:54 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)

Sergei Petrunia added a comment - 2016-01-23 22:14

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".

Sergei Petrunia added a comment - 2016-01-23 22:14 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".

Sergei Petrunia added a comment - 2016-01-24 11:31

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

Sergei Petrunia added a comment - 2016-01-24 11:31 http://lists.askmonty.org/pipermail/commits/2016-January/008860.html

People

Assignee:: Sergei Petrunia

Reporter:: Sergei Petrunia

Votes:: 0 Vote for this issue

Watchers:: 2 Start watching this issue

Dates

Created:: 2016-01-23 18:21

Updated:: 2016-02-03 12:36

Resolved:: 2016-01-24 16:00

Git Integration

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

MariaDB Server