[MDEV-6672] Performance degradation on a query with joins and ORDER BY .. LIMIT - JIRA

Details

Type: Bug
Status: Closed
Priority: Major
Resolution: Won't Fix
Affects Version/s: 10.1.1
Fix Version/s: N/A
Component/s: None
Labels:

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.

Gliffy Diagrams

Attachments

Options
- Sort By Name
- Sort By Date
- Ascending
- Descending
- Thumbnails
- List
- Download All

Attachments

mdev6454-1.dump
121 kB
2014-08-31 15:05

Issue Links

relates to

MDEV-6634 Wrong estimates for ref(const) and key IS NULL predicate

Closed

Activity

Ascending order - Click to sort in descending order

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-01 21:44

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

Show

Sergei Petrunia added a comment - 2014-09-01 21:44 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".

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-01 22:43

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

Show

Sergei Petrunia added a comment - 2014-09-01 22:43 it is important to NOT run "analyze table B". If you do it, the difference goes away.

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-01 22:54

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.

Show

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-02 00:32

Conclusions after exchange with Elena Stepanova : 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.

Show

Sergei Petrunia added a comment - 2014-09-02 00:32 Conclusions after exchange with Elena Stepanova : 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.

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-02 00:43

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.

Show

Sergei Petrunia added a comment - 2014-09-02 00:43 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.

Hide

Permalink

Sergei Petrunia added a comment - 2014-09-02 00:44

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

Show

Sergei Petrunia added a comment - 2014-09-02 00:44 Closing as Not a Bug, the slowdown is not as big, and the cost model is known to be not fully adequate.

Performance degradation on a query with joins and ORDER BY .. LIMIT

Details

Description

Gliffy Diagrams

Attachments

Attachments

Issue Links

Activity

People

Dates

Agile