[MDEV-13275] Query optimizer not picking optimal ORDER BY PRIMARY in case of INNER JOIN on PRIMARY like it does for similar WHERE condition Created: 2017-07-07  Updated: 2024-01-25

Status: Stalled
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: 10.1.24, 10.2, 10.3
Fix Version/s: 10.4, 10.5

Type: Bug Priority: Major
Reporter: Joey Mart (Inactive) Assignee: Sergei Petrunia
Resolution: Unresolved Votes: 2
Labels: order-by-optimization, server
Environment:

centos 6

Attachments: File MDEV-13275.sql    
Issue Links:
Relates
relates to MDEV-8306 Complete cost-based optimization for ... Stalled

 Description   

Order by a column that isn't the first column in the join list requires a temporary table.

A query that INNER JOINs two tables on their Primary keys with a WHERE clause on a particular key value properly optimizes to target the first table in the join order for the WHERE clause, presumably based on the logical equivalence of the values implied by the INNER JOIN:

Query second table's id (PRIMARY):

SELECT first.id FROM first INNER JOIN second ON first.id = second.id WHERE second.id > '5E1215B77BB14DA4DD7C9D4DDD26501A';

Optimized query (from EXPLAIN EXTENDED warning) points the WHERE clause to the first table:

select `db`.`first`.`id` AS `id` from `db`.`first` join `db`.`second` where ((`db`.`second`.`id` = `db`.`first`.`id`) and (`db`.`first`.`id` > '5E1215B77BB14DA4DD7C9D4DDD26501A'))

The same thing does not happen for the ORDER BY, and so changing which table's Primary key we order by makes the difference between requiring a temporary table and not:

This query (ORDER BY first) is basically just an index retrieval:

> ANALYZE SELECT first.id FROM first INNER JOIN second ON first.id = second.id ORDER BY first.id;
 
+------+-------------+--------+--------+---------------+---------+---------+------------------------+------+--------+----------+------------+-------------+
 
| id   | select_type | table  | type   | possible_keys | key     | key_len | ref                    | rows | r_rows | filtered | r_filtered | Extra       |
 
+------+-------------+--------+--------+---------------+---------+---------+------------------------+------+--------+----------+------------+-------------+
 
|    1 | SIMPLE      | first  | index  | PRIMARY       | PRIMARY | 96      | NULL                   |  100 | 100.00 |   100.00 |     100.00 | Using index |
 
|    1 | SIMPLE      | second | eq_ref | PRIMARY       | PRIMARY | 96      | huff_20170614.first.id |    1 |   1.00 |   100.00 |     100.00 | Using index |
 
+------+-------------+--------+--------+---------------+---------+---------+------------------------+------+--------+----------+------------+-------------+

But if you change the ORDER BY to the second table, it now requires a temporary table:

> ANALYZE SELECT first.id FROM first INNER JOIN second ON first.id = second.id ORDER BY second.id;
 
+------+-------------+--------+--------+---------------+---------+---------+------------------------+------+--------+----------+------------+----------------------------------------------+
 
| id   | select_type | table  | type   | possible_keys | key     | key_len | ref                    | rows | r_rows | filtered | r_filtered | Extra                                        |
 
+------+-------------+--------+--------+---------------+---------+---------+------------------------+------+--------+----------+------------+----------------------------------------------+
 
|    1 | SIMPLE      | first  | index  | PRIMARY       | PRIMARY | 96      | NULL                   |  100 | 100.00 |   100.00 |     100.00 | Using index; Using temporary; Using filesort |
 
|    1 | SIMPLE      | second | eq_ref | PRIMARY       | PRIMARY | 96      | huff_20170614.first.id |    1 |   1.00 |   100.00 |     100.00 | Using index                                  |
 
+------+-------------+--------+--------+---------------+---------+---------+------------------------+------+--------+----------+------------+----------------------------------------------+

In our real-life example, the table was ~2GB and tmp_table_size was 64MB, so this meant that the temp table actually went to disk.

Notable status counter differences:

Handler_commit	1	1
 
Handler_read_first	1	1
 
Handler_read_key	906	906
 
Handler_read_next	906	906
 
Handler_read_rnd	0	906
 
Handler_read_rnd_next	0	907
 
Handler_tmp_write	0	906



 Comments   
Comment by Joey Mart (Inactive) [ 2017-07-07 ]

Attached mysqldump for test tables.

Comment by Alice Sherepa [ 2017-08-04 ]

Joey Mart, thanks for the report.
Confirmed with a test case below. Execution of query with "using temprorary" takes longer.

CREATE TABLE `t1` (id char(32) NOT NULL PRIMARY KEY);
 
CREATE TABLE `t2` (id char(32) NOT NULL PRIMARY KEY);
 
 
 
INSERT INTO t1 SELECT seq FROM seq_1_to_1000000;
 
INSERT INTO t2 SELECT seq FROM seq_5000_to_500000;
 
 
 
ANALYZE FORMAT=JSON SELECT t1.id FROM t1 INNER JOIN t2 ON t1.id = t2.id order by t1.id ;
 
ANALYZE FORMAT=JSON SELECT t1.id FROM t1 INNER JOIN t2 ON t1.id = t2.id order by t2.id ;


  ANALYZE FORMAT=JSON SELECT t1.id FROM t1 INNER JOIN t2 ON t1.id = t2.id order by t1.id ;


  {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 5401.8,
 
    "filesort": {
 
      "sort_key": "t1.`id`",
 
      "r_loops": 1,
 
      "r_total_time_ms": 156.94,
 
      "r_used_priority_queue": false,
 
      "r_output_rows": 495001,
 
      "r_sort_passes": 4,
 
      "r_buffer_size": "2047Kb",
 
      "temporary_table": {
 
        "table": {
 
          "table_name": "t2",
 
          "access_type": "index",
 
          "possible_keys": ["PRIMARY"],
 
          "key": "PRIMARY",
 
          "key_length": "32",
 
          "used_key_parts": ["id"],
 
          "r_loops": 1,
 
          "rows": 484131,
 
          "r_rows": 495001,
 
          "r_total_time_ms": 886.6,
 
          "filtered": 100,
 
          "r_filtered": 100,
 
          "using_index": true
 
        },
 
        "table": {
 
          "table_name": "t1",
 
          "access_type": "eq_ref",
 
          "possible_keys": ["PRIMARY"],
 
          "key": "PRIMARY",
 
          "key_length": "32",
 
          "used_key_parts": ["id"],
 
          "ref": ["test.t2.id"],
 
          "r_loops": 495001,
 
          "rows": 1,
 
          "r_rows": 1,
 
          "r_total_time_ms": 4122.1,
 
          "filtered": 100,
 
          "r_filtered": 100,
 
          "using_index": true
 
        }
 
      }
 
    }
 
  }
 
} 


 ANALYZE FORMAT=JSON SELECT t1.id FROM t1 INNER JOIN t2 ON t1.id = t2.id order by t2.id ;


 {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 2471.7,
 
    "table": {
 
      "table_name": "t2",
 
      "access_type": "index",
 
      "possible_keys": ["PRIMARY"],
 
      "key": "PRIMARY",
 
      "key_length": "32",
 
      "used_key_parts": ["id"],
 
      "r_loops": 1,
 
      "rows": 484131,
 
      "r_rows": 495001,
 
      "r_total_time_ms": 163.77,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    },
 
    "table": {
 
      "table_name": "t1",
 
      "access_type": "eq_ref",
 
      "possible_keys": ["PRIMARY"],
 
      "key": "PRIMARY",
 
      "key_length": "32",
 
      "used_key_parts": ["id"],
 
      "ref": ["test.t2.id"],
 
      "r_loops": 495001,
 
      "rows": 1,
 
      "r_rows": 1,
 
      "r_total_time_ms": 2235,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
}

Comment by Sergei Petrunia [ 2018-03-28 ]

Still reproducible on the current MariaDB 10.2 (and I expect that on MariaDB 10.3 it will be reproducible, too).

This case should be handled by "orderby_uses_equalities" optimization. However, I have orderby_uses_equalities=on on my server, and I still observe the following

ANALYZE FORMAT=JSON SELECT t1.id FROM t1 INNER JOIN t2 ON t1.id = t2.id order by t1.id ;
 
| {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 13620,
 
    "filesort": {
 
      "sort_key": "t1.`id`",
 
      "r_loops": 1,
 
      "r_total_time_ms": 461.05,
 
      "r_used_priority_queue": false,
 
      "r_output_rows": 495001,
 
      "r_sort_passes": 4,
 
      "r_buffer_size": "2047Kb",
 
      "temporary_table": {
 
        "table": {
 
          "table_name": "t2",
 
          "access_type": "index",
 
          "possible_keys": ["PRIMARY"],
 
          "key": "PRIMARY",
 
          "key_length": "32",
 
          "used_key_parts": ["id"],
 
          "r_loops": 1,
 
          "rows": 425764,
 
          "r_rows": 495001,
 
          "r_total_time_ms": 1768.8,
 
          "filtered": 100,
 
          "r_filtered": 100,
 
          "using_index": true
 
        },
 
        "table": {
 
          "table_name": "t1",
 
          "access_type": "eq_ref",
 
          "possible_keys": ["PRIMARY"],
 
          "key": "PRIMARY",
 
          "key_length": "32",
 
          "used_key_parts": ["id"],
 
          "ref": ["test.t2.id"],
 
          "r_loops": 495001,
 
          "rows": 1,
 
          "r_rows": 1,
 
          "r_total_time_ms": 9524.7,
 
          "filtered": 100,
 
          "r_filtered": 100,
 
          "using_index": true
 
        }
 
      }
 
    }
 
  }
 
} |

Join order is (t2, t1), ORDER BY t1.id causes filesort to be used (why is orderby_uses_equalities not working?)

ANALYZE FORMAT=JSON SELECT t1.id FROM t1 INNER JOIN t2 ON t1.id = t2.id order by t2.id ;
 
| {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 13234,
 
    "table": {
 
      "table_name": "t2",
 
      "access_type": "index",
 
      "possible_keys": ["PRIMARY"],
 
      "key": "PRIMARY",
 
      "key_length": "32",
 
      "used_key_parts": ["id"],
 
      "r_loops": 1,
 
      "rows": 425764,
 
      "r_rows": 495001,
 
      "r_total_time_ms": 1751.9,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    },
 
    "table": {
 
      "table_name": "t1",
 
      "access_type": "eq_ref",
 
      "possible_keys": ["PRIMARY"],
 
      "key": "PRIMARY",
 
      "key_length": "32",
 
      "used_key_parts": ["id"],
 
      "ref": ["test.t2.id"],
 
      "r_loops": 495001,
 
      "rows": 1,
 
      "r_rows": 1,
 
      "r_total_time_ms": 10387,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
} |

Join order is (t2, t1), ORDER BY t2.id uses the index in t2 (as expected).

Comment by Sergei Petrunia [ 2018-03-28 ]

varun, please investigate.

Comment by Varun Gupta (Inactive) [ 2018-04-01 ]

Observation:

If i change the type field id of table t1 and t2 from char(32) to int, then i see the orderby_uses_equalities being used , so we don't see any temporary table while sorting.

Output for ANALYZE format=json with order by using t1.id

ANALYZE FORMAT=JSON SELECT t1.id FROM t1 INNER JOIN t2 ON t1.id = t2.id order by t1.id ;
 
| {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 0.6928,
 
    "table": {
 
      "table_name": "t2",
 
      "access_type": "index",
 
      "possible_keys": ["PRIMARY"],
 
      "key": "PRIMARY",
 
      "key_length": "4",
 
      "used_key_parts": ["id"],
 
      "r_loops": 1,
 
      "rows": 10,
 
      "r_rows": 10,
 
      "r_total_time_ms": 0.1476,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    },
 
    "table": {
 
      "table_name": "t1",
 
      "access_type": "eq_ref",
 
      "possible_keys": ["PRIMARY"],
 
      "key": "PRIMARY",
 
      "key_length": "4",
 
      "used_key_parts": ["id"],
 
      "ref": ["test.t2.id"],
 
      "r_loops": 10,
 
      "rows": 1,
 
      "r_rows": 1,
 
      "r_total_time_ms": 0.4508,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
} |

Comment by Sergei Petrunia [ 2018-04-03 ]

Ok, so `orderby_uses_equalities` is unable use this equality because of its datatype.

Comment by Sergei Petrunia [ 2018-04-03 ]

A little background about equality propagation. There are two kinds of equality propagation.
1. Full substitution - this allows to make inferences like X=Y AND cond(X) -> X=Y AND cond(Y).
2. Substitution for the purpose of comparison (S4PC) allows to make inferences like X=Y and X < expr -> X=Y and Y < expr

Full substitution is often unusable for [VAR]CHAR. The common reasons are case-insensitive comparisons ( 'a'='A' ) and padding ('A' = 'A '). However, they don't prevent S4PC.

My point is that orderby_uses_equalities should use S4PC. While this bug looks like it is relying on Full Substitution instead.

Comment by Sergei Petrunia [ 2018-04-03 ]

Example of S4PC in action:

MariaDB [test]> show create table t1;
 
+-------+-----------------------------------------------------------------------------------------------------------+
 
| Table | Create Table                                                                                              |
 
+-------+-----------------------------------------------------------------------------------------------------------+
 
| t1    | CREATE TABLE `t1` (
 
  `id` char(32) NOT NULL,
 
  PRIMARY KEY (`id`)
 
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
 
+-------+-----------------------------------------------------------------------------------------------------------+
 
1 row in set (0.000 sec)

10:45

MariaDB [test]> show create table t2;
 
+-------+-----------------------------------------------------------------------------------------------------------+
 
| Table | Create Table                                                                                              |
 
+-------+-----------------------------------------------------------------------------------------------------------+
 
| t2    | CREATE TABLE `t2` (
 
  `id` char(32) NOT NULL,
 
  PRIMARY KEY (`id`)
 
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
 
+-------+-----------------------------------------------------------------------------------------------------------+
 
1 row in set (0.000 sec)


analyze format=json select * from t1,t2 where t1.id > 'a' and t2.id=t1.id
 
| {
 
  "query_block": {
 
    "select_id": 1,
 
    "r_loops": 1,
 
    "r_total_time_ms": 0.5222,
 
    "table": {
 
      "table_name": "t2",
 
      "access_type": "range",
 
      "possible_keys": ["PRIMARY"],
 
      "key": "PRIMARY",
 
      "key_length": "32",
 
      "used_key_parts": ["id"],
 
      "r_loops": 1,
 
      "rows": 3,
 
      "r_rows": 3,
 
      "r_total_time_ms": 0.1872,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "attached_condition": "t2.`id` > 'a'",
 
      "using_index": true
 
    },
 
    "table": {
 
      "table_name": "t1",
 
      "access_type": "eq_ref",
 
      "possible_keys": ["PRIMARY"],
 
      "key": "PRIMARY",
 
      "key_length": "32",
 
      "used_key_parts": ["id"],
 
      "ref": ["test.t2.id"],
 
      "r_loops": 3,
 
      "rows": 1,
 
      "r_rows": 1,
 
      "r_total_time_ms": 0.1543,
 
      "filtered": 100,
 
      "r_filtered": 100,
 
      "using_index": true
 
    }
 
  }
 
} |

Comment by Sergei Petrunia [ 2018-04-03 ]

varun, please find the code that does S4PC and then let's

  • verify that orderby_uses_equalities uses full substitution instead
  • discuss whether it could use S4PC also.

(TODO: does orderby_uses_equalities handle cases where full substitution applies while S4PC does not? e.g. {{ t1.datetime_col=t2.datetime_col ORDER BY MONTH(t1.datetime_col)}} ? )

Comment by Varun Gupta (Inactive) [ 2018-04-03 ]

For S4PC we will not have a problem even if we have a function in the order by list.
lets take a query for example:

select * from t1,t2 where t1.id = t2.id order by length(t1.id)

so the substitution of t1.id with t2.id would not happen inside the length(..) function. In the optimization orderby_uses_equalites we do substitution only for the top level items(not functional items).

Generated at Thu Feb 08 08:04:18 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.