[MDEV-6672] Performance degradation on a query with joins and ORDER BY .. LIMIT Created: 2014-08-31  Updated: 2014-09-02  Resolved: 2014-09-02

Status: Closed
Project: MariaDB Server
Component/s: None
Affects Version/s: 10.1.1
Fix Version/s: N/A

Type: Bug Priority: Major
Reporter: Elena Stepanova Assignee: Sergei Petrunia
Resolution: Won't Fix Votes: 0
Labels: optimizer, order-by-optimization, tbfl

Attachments: File mdev6454-1.dump    
Issue Links:
Relates
relates to MDEV-6634 Wrong estimates for ref(const) and ke... Closed

 Description   

Observed on bb-10.1-orderby-fixes commit f8f8a59c189254baeb7f90920b6b23da227984e8

The query:

SELECT alias2.pk 
  FROM A 
  LEFT JOIN B AS alias1 
  INNER JOIN B AS alias2 
    ON alias1.col_int_key = alias2.col_int_key 
    ON alias2.col_varchar_10_latin1 = A.col_varchar_1024_utf8_key 
ORDER BY alias2.pk LIMIT 10;

Execution times and EXPLAINs
bb-10.1-orderby-fixes: 0.20 sec

+------+-------------+--------+-------+---------------+-------------+---------+-------------------------+------+----------+---------------------------------+
 
| id   | select_type | table  | type  | possible_keys | key         | key_len | ref                     | rows | filtered | Extra                           |
 
+------+-------------+--------+-------+---------------+-------------+---------+-------------------------+------+----------+---------------------------------+
 
|    1 | SIMPLE      | A      | ALL   | NULL          | NULL        | NULL    | NULL                    |  100 |   100.00 | Using temporary; Using filesort |
 
|    1 | SIMPLE      | alias2 | range | col_int_key   | col_int_key | 5       | NULL                    |   59 |   100.00 | Using where                     |
 
|    1 | SIMPLE      | alias1 | ref   | col_int_key   | col_int_key | 5       | test.alias2.col_int_key |    1 |   100.00 | Using index                     |
 
+------+-------------+--------+-------+---------------+-------------+---------+-------------------------+------+----------+---------------------------------+
 
3 rows in set, 1 warning (0.00 sec)
 
 
 
MariaDB [test]> SHOW WARNINGS;
 
+-------+------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
| Level | Code | Message                                                                                                                                                                                                                                                                                                                                                                                      |
 
+-------+------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
| Note  | 1003 | select `test`.`alias2`.`pk` AS `pk` from `test`.`A` left join (`test`.`B` `alias1` join `test`.`B` `alias2`) on(((`test`.`alias1`.`col_int_key` = `test`.`alias2`.`col_int_key`) and (convert(`test`.`alias2`.`col_varchar_10_latin1` using utf8) = `test`.`A`.`col_varchar_1024_utf8_key`) and (`test`.`alias2`.`col_int_key` is not null))) where 1 order by `test`.`alias2`.`pk` limit 10 |
 
+-------+------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

10.1: 0.08 sec

+------+-------------+--------+------+---------------+-------------+---------+-------------------------+------+----------+---------------------------------+
 
| id   | select_type | table  | type | possible_keys | key         | key_len | ref                     | rows | filtered | Extra                           |
 
+------+-------------+--------+------+---------------+-------------+---------+-------------------------+------+----------+---------------------------------+
 
|    1 | SIMPLE      | A      | ALL  | NULL          | NULL        | NULL    | NULL                    |  100 |   100.00 | Using temporary; Using filesort |
 
|    1 | SIMPLE      | alias2 | ALL  | col_int_key   | NULL        | NULL    | NULL                    |  100 |   100.00 | Using where                     |
 
|    1 | SIMPLE      | alias1 | ref  | col_int_key   | col_int_key | 5       | test.alias2.col_int_key |    1 |   100.00 | Using index                     |
 
+------+-------------+--------+------+---------------+-------------+---------+-------------------------+------+----------+---------------------------------+
 
3 rows in set, 1 warning (0.00 sec)
 
 
 
MariaDB [test]> SHOW WARNINGS;
 
+-------+------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
| Level | Code | Message                                                                                                                                                                                                                                                                                                                                                                                      |
 
+-------+------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
 
| Note  | 1003 | select `test`.`alias2`.`pk` AS `pk` from `test`.`A` left join (`test`.`B` `alias1` join `test`.`B` `alias2`) on(((`test`.`alias1`.`col_int_key` = `test`.`alias2`.`col_int_key`) and (convert(`test`.`alias2`.`col_varchar_10_latin1` using utf8) = `test`.`A`.`col_varchar_1024_utf8_key`) and (`test`.`alias2`.`col_int_key` is not null))) where 1 order by `test`.`alias2`.`pk` limit 10 |
 
+-------+------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

With increasing the number of rows in tables the approximate ratio holds.

Tables:

CREATE TABLE `A` (
 
  `col_datetime` datetime DEFAULT NULL,
 
  `col_varchar_10_latin1` varchar(10) DEFAULT NULL,
 
  `col_datetime_key` datetime DEFAULT NULL,
 
  `col_varchar_1024_utf8_key` varchar(1024) CHARACTER SET utf8 DEFAULT NULL,
 
  `col_int_key` int(11) DEFAULT NULL,
 
  `col_varchar_1024_utf8` varchar(1024) CHARACTER SET utf8 DEFAULT NULL,
 
  `col_date_key` date DEFAULT NULL,
 
  `pk` int(11) NOT NULL AUTO_INCREMENT,
 
  `col_varchar_1024_latin1` varchar(1024) DEFAULT NULL,
 
  `col_date` date DEFAULT NULL,
 
  `col_varchar_1024_latin1_key` varchar(1024) DEFAULT NULL,
 
  `col_varchar_10_latin1_key` varchar(10) DEFAULT NULL,
 
  `col_int` int(11) DEFAULT NULL,
 
  `col_varchar_10_utf8_key` varchar(10) CHARACTER SET utf8 DEFAULT NULL,
 
  `col_varchar_10_utf8` varchar(10) CHARACTER SET utf8 DEFAULT NULL,
 
  PRIMARY KEY (`pk`),
 
  KEY `col_datetime_key` (`col_datetime_key`),
 
  KEY `col_varchar_1024_utf8_key` (`col_varchar_1024_utf8_key`(333)),
 
  KEY `col_int_key` (`col_int_key`),
 
  KEY `col_date_key` (`col_date_key`),
 
  KEY `col_varchar_1024_latin1_key` (`col_varchar_1024_latin1_key`(1000)),
 
  KEY `col_varchar_10_latin1_key` (`col_varchar_10_latin1_key`),
 
  KEY `col_varchar_10_utf8_key` (`col_varchar_10_utf8_key`)
 
) ENGINE=MyISAM AUTO_INCREMENT=101 DEFAULT CHARSET=latin1
 

+-------+------------+-----------------------------+--------------+-----------------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
 
| Table | Non_unique | Key_name                    | Seq_in_index | Column_name                 | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
 
+-------+------------+-----------------------------+--------------+-----------------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
 
| A     |          0 | PRIMARY                     |            1 | pk                          | A         |         100 |     NULL | NULL   |      | BTREE      |         |               |
 
| A     |          1 | col_datetime_key            |            1 | col_datetime_key            | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
| A     |          1 | col_varchar_1024_utf8_key   |            1 | col_varchar_1024_utf8_key   | A         |         100 |      333 | NULL   | YES  | BTREE      |         |               |
 
| A     |          1 | col_int_key                 |            1 | col_int_key                 | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
| A     |          1 | col_date_key                |            1 | col_date_key                | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
| A     |          1 | col_varchar_1024_latin1_key |            1 | col_varchar_1024_latin1_key | A         |         100 |     1000 | NULL   | YES  | BTREE      |         |               |
 
| A     |          1 | col_varchar_10_latin1_key   |            1 | col_varchar_10_latin1_key   | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
| A     |          1 | col_varchar_10_utf8_key     |            1 | col_varchar_10_utf8_key     | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
+-------+------------+-----------------------------+--------------+-----------------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
 

CREATE TABLE `B` (
 
  `col_int` int(11) DEFAULT NULL,
 
  `col_varchar_1024_utf8` varchar(1024) CHARACTER SET utf8 DEFAULT NULL,
 
  `col_varchar_1024_utf8_key` varchar(1024) CHARACTER SET utf8 DEFAULT NULL,
 
  `col_varchar_10_utf8_key` varchar(10) CHARACTER SET utf8 DEFAULT NULL,
 
  `col_varchar_10_latin1` varchar(10) DEFAULT NULL,
 
  `col_datetime` datetime DEFAULT NULL,
 
  `col_date_key` date DEFAULT NULL,
 
  `pk` int(11) NOT NULL AUTO_INCREMENT,
 
  `col_varchar_1024_latin1_key` varchar(1024) DEFAULT NULL,
 
  `col_varchar_10_utf8` varchar(10) CHARACTER SET utf8 DEFAULT NULL,
 
  `col_int_key` int(11) DEFAULT NULL,
 
  `col_varchar_10_latin1_key` varchar(10) DEFAULT NULL,
 
  `col_datetime_key` datetime DEFAULT NULL,
 
  `col_date` date DEFAULT NULL,
 
  `col_varchar_1024_latin1` varchar(1024) DEFAULT NULL,
 
  PRIMARY KEY (`pk`),
 
  KEY `col_varchar_1024_utf8_key` (`col_varchar_1024_utf8_key`(255)),
 
  KEY `col_varchar_10_utf8_key` (`col_varchar_10_utf8_key`),
 
  KEY `col_date_key` (`col_date_key`),
 
  KEY `col_varchar_1024_latin1_key` (`col_varchar_1024_latin1_key`(767)),
 
  KEY `col_int_key` (`col_int_key`),
 
  KEY `col_varchar_10_latin1_key` (`col_varchar_10_latin1_key`),
 
  KEY `col_datetime_key` (`col_datetime_key`)
 
) ENGINE=InnoDB AUTO_INCREMENT=101 DEFAULT CHARSET=latin1
 

+-------+------------+-----------------------------+--------------+-----------------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
 
| Table | Non_unique | Key_name                    | Seq_in_index | Column_name                 | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
 
+-------+------------+-----------------------------+--------------+-----------------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
 
| B     |          0 | PRIMARY                     |            1 | pk                          | A         |         100 |     NULL | NULL   |      | BTREE      |         |               |
 
| B     |          1 | col_varchar_1024_utf8_key   |            1 | col_varchar_1024_utf8_key   | A         |         100 |      255 | NULL   | YES  | BTREE      |         |               |
 
| B     |          1 | col_varchar_10_utf8_key     |            1 | col_varchar_10_utf8_key     | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
| B     |          1 | col_date_key                |            1 | col_date_key                | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
| B     |          1 | col_varchar_1024_latin1_key |            1 | col_varchar_1024_latin1_key | A         |         100 |      767 | NULL   | YES  | BTREE      |         |               |
 
| B     |          1 | col_int_key                 |            1 | col_int_key                 | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
| B     |          1 | col_varchar_10_latin1_key   |            1 | col_varchar_10_latin1_key   | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
| B     |          1 | col_datetime_key            |            1 | col_datetime_key            | A         |         100 |     NULL | NULL   | YES  | BTREE      |         |               |
 
+-------+------------+-----------------------------+--------------+-----------------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

The dump is attached.



 Comments   
Comment by Sergei Petrunia [ 2014-09-01 ]

So, the difference is how table alias2 is accessed:

  • bb-10.1-orderby-fixes: uses type=range, rows=59
  • 10.1: uses type=ALL, rows=100

ORDER BY optimization should not matter: this is a LEFT JOIN ... ORDER BY inner_table, i.e. the only way to resolve the ORDER BY is "Using temporary; Using filesort".

Comment by Sergei Petrunia [ 2014-09-01 ]

it is important to NOT run "analyze table B". If you do it, the difference goes away.

Comment by Sergei Petrunia [ 2014-09-01 ]

I can get this plan on 10.1 tree: 

MariaDB [test4]> explain SELECT alias2.pk    FROM A    LEFT JOIN B AS alias1    INNER JOIN B AS alias2      ON alias1.col_int_key = alias2.col_int_key      ON alias2.col_varchar_10_latin1 = A.col_varchar_1024_utf8_key  ORDER BY alias2.pk LIMIT 10;
 
+------+-------------+--------+------+---------------+-------------+---------+--------------------------+------+---------------------------------+
 
| id   | select_type | table  | type | possible_keys | key         | key_len | ref                      | rows | Extra                           |
 
+------+-------------+--------+------+---------------+-------------+---------+--------------------------+------+---------------------------------+
 
|    1 | SIMPLE      | A      | ALL  | NULL          | NULL        | NULL    | NULL                     |  100 | Using temporary; Using filesort |
 
|    1 | SIMPLE      | alias2 | ALL  | col_int_key   | NULL        | NULL    | NULL                     |    6 | Using where                     |
 
|    1 | SIMPLE      | alias1 | ref  | col_int_key   | col_int_key | 5       | test4.alias2.col_int_key |    1 | Using index                     |
 
+------+-------------+--------+------+---------------+-------------+---------+--------------------------+------+---------------------------------+

note that alias2.rows=6...
Moreover, on bb-10.1-orderby-fixes: if I run the query multiple times I get different query plans:

MariaDB [test2]> explain SELECT alias2.pk 
    ->   FROM A 
    ->   LEFT JOIN B AS alias1 
    ->   INNER JOIN B AS alias2 
    ->     ON alias1.col_int_key = alias2.col_int_key 
    ->     ON alias2.col_varchar_10_latin1 = A.col_varchar_1024_utf8_key 
    -> ORDER BY alias2.pk LIMIT 10;
 
+------+-------------+--------+------+---------------+-------------+---------+--------------------------+------+---------------------------------+
 
| id   | select_type | table  | type | possible_keys | key         | key_len | ref                      | rows | Extra                           |
 
+------+-------------+--------+------+---------------+-------------+---------+--------------------------+------+---------------------------------+
 
|    1 | SIMPLE      | A      | ALL  | NULL          | NULL        | NULL    | NULL                     |  100 | Using temporary; Using filesort |
 
|    1 | SIMPLE      | alias2 | ALL  | col_int_key   | NULL        | NULL    | NULL                     |    5 | Using where                     |
 
|    1 | SIMPLE      | alias1 | ref  | col_int_key   | col_int_key | 5       | test2.alias2.col_int_key |    1 | Using index                     |
 
+------+-------------+--------+------+---------------+-------------+---------+--------------------------+------+---------------------------------+
 
3 rows in set (0.00 sec)
 
 
 
MariaDB [test2]> explain SELECT alias2.pk    FROM A    LEFT JOIN B AS alias1    INNER JOIN B AS alias2      ON alias1.col_int_key = alias2.col_int_key      ON alias2.col_varchar_10_latin1 = A.col_varchar_1024_utf8_key  ORDER BY alias2.pk LIMIT 10;
 
+------+-------------+--------+-------+---------------+-------------+---------+--------------------------+------+---------------------------------+
 
| id   | select_type | table  | type  | possible_keys | key         | key_len | ref                      | rows | Extra                           |
 
+------+-------------+--------+-------+---------------+-------------+---------+--------------------------+------+---------------------------------+
 
|    1 | SIMPLE      | A      | ALL   | NULL          | NULL        | NULL    | NULL                     |  100 | Using temporary; Using filesort |
 
|    1 | SIMPLE      | alias2 | range | col_int_key   | col_int_key | 5       | NULL                     |   59 | Using where                     |
 
|    1 | SIMPLE      | alias1 | ref   | col_int_key   | col_int_key | 5       | test2.alias2.col_int_key |    1 | Using index                     |
 
+------+-------------+--------+-------+---------------+-------------+---------+--------------------------+------+---------------------------------+
 
3 rows in set (1 min 40.05 sec)

this seems to be caused by innodb's table statistics update.

Comment by Sergei Petrunia [ 2014-09-02 ]

Conclusions after exchange with elenst : the difference is caused by fix for MDEV-6634. it made IS [not] NULL predicates sargable, and the following started to happen:

-nulls filtering added "IS NOT NULL" condition.
-make_join_select()/test_quick_select() made use of the IS NOT NULL predicate, produced a range access.

Comment by Sergei Petrunia [ 2014-09-02 ]

Another thing:

the call from make_join_select() looks like this:

  #0  SQL_SELECT::test_quick_select (this=0x7fffc7573b58, thd=0x7fffd131e070, keys_to_use=..., prev_tables=13835058055282163713, limit=10, force_quick_range=false, ordered_output=false) at /home/psergey/dev-git/10.1/sql/opt_range.cc:2945

it has limit=10 (which is stupid - the query uses "Using temporary; using filesort", which means we will have to scan all rows, not 10)
It causes this branch to be take in SQL_SELECT::test_quick_select:

  if (limit < records)
 
    read_time= (double) records + scan_time + 1; // Force to use index

which causes a change in full table scan cost:

(gdb) print read_time
 
  $10 = 27.100000000000001
 
(gdb) next
 
(gdb) print read_time
 
  $11 = 122

and this is why we pick to use range access even if it expects to read 59 records of 100.

Comment by Sergei Petrunia [ 2014-09-02 ]

Closing as Not a Bug, the slowdown is not as big, and the cost model is known to be not fully adequate.

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