MySQL Bugs: #71804: Unnecessary filesort when joining on unique column using group by.

Bug #71804	Unnecessary filesort when joining on unique column using group by.
Submitted:	22 Feb 2014 22:29	Modified:	20 Oct 2014 8:53
Reporter:	Jan Filipiak	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	5.6.6 m9, 5.5.32, 5.1.61	OS:	Any (sqlfiddle.com)
Assigned to:	Assigned Account	CPU Architecture:	Any

Description:
Dear reader,

joining two tables like shown in the "how to repeat" - section. The optimizer chooses to use a filesort.
The fact that "ORDER BY NULL" is present and that the column joined on is the Primary key of the table that is scanned first it should not need todo the sorting.

An index providing the order of the group by clause would remove the filesort. But this can not always be specified by the user as range queries may want to be performed.

Thank you very much for thinking about this.

How to repeat:
I set up a sqlfiddle.com link here:

http://sqlfiddle.com/#!9/16498/2

in case that this is gone:

CREATE TABLE `master_record` (
  `master_id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `a` varchar(100) DEFAULT NULL,
  `b` varchar(100) DEFAULT NULL,
  PRIMARY KEY (`master_id`),
  KEY `master_record_a_b_IDX` (`a`,`b`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE `detail_record` (
  `master_id` bigint(20) unsigned NOT NULL,
  `detail_id` smallint(5) unsigned NOT NULL,
  `c` varchar(100) DEFAULT NULL,
  PRIMARY KEY (`master_id`,`detail_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

explain select master_id, group_concat(c) from master_record left join detail_record using (master_id)
where a = "11aabb"
group by master_id
order by null

extra column will say "using filesort"

Suggested fix:
The optimizer could skip the sorting step and just retrieve the values in the order given by the index.

Hi ,

Can you do two things. First,  "group by master_id" replace by "group by table.master_id", where "table" should be replaced by one of two tables in the query.

Second, please provide us with the output from EXPLAIN EXTENDED on the query.

Thanks.

Hello,

This is the changed query

select master_id, group_concat(b) from master_record left join detail_record using (master_id)
where a = "11%"
group by master_record.master_id
order by null;

this is the output of explain extended:
| ID | SELECT_TYPE |         TABLE | TYPE |       POSSIBLE_KEYS |                 KEY | KEY_LEN |                                REF | ROWS | FILTERED |                                    EXTRA |
|----|-------------|---------------|------|---------------------|---------------------|---------|------------------------------------|------|----------|------------------------------------------|
|  1 |      SIMPLE | master_record |  ref | master_record_a_IDX | master_record_a_IDX |     303 |                              const |    1 |      100 | Using where; Using index; Using filesort |
|  1 |      SIMPLE | detail_record |  ref |             PRIMARY |             PRIMARY |       8 | db_9_16498.master_record.master_id |    1 |      100 |                              Using index |
		
Thank you for looking into this.

Best Jan

Hi Jan. In the first post your query had group_concat(c), in the second poqt it had group_concat(b). c vs b. Which is the important query for you? If it's the group_concat(c), could you please post the EXPLAIN ? If it's group_concat(b), no need to do so, you already posted it. Thanks.

Hi,

sorry wasnt carefull enough, our use is indeed c as b does not make to much sense. anyways there is no difference between them.

| ID | SELECT_TYPE |         TABLE | TYPE |       POSSIBLE_KEYS |                 KEY | KEY_LEN |                                REF | ROWS |                                    EXTRA |
|----|-------------|---------------|------|---------------------|---------------------|---------|------------------------------------|------|------------------------------------------|
|  1 |      SIMPLE | master_record |  ref | master_record_a_IDX | master_record_a_IDX |     303 |                              const |    1 | Using where; Using index; Using filesort |
|  1 |      SIMPLE | detail_record |  ref |             PRIMARY |             PRIMARY |       8 | db_9_16498.master_record.master_id |    1 |                                   (null) |

A filesort is still performed. "c" is just the much more usefull information to concat. The only purpose of "b" is to make clear there is only a prefix of the index used. The ticket also applies for the cases where you want to repeat b for every detail record.

Thank you for your fast replies. Maybe we can start approaching the core of the issue. If some things are still not clear, please let me know. 

Best jan

Hello Jan. I fear you indeed found a bug.

EXPLAIN says that for the first table, master_record, it's doing "ref" access on index (a,b) (which is actually (a,b,master_id) as this is an InnoDB table). key_len=303 so it's doing the lookup only by value of 'a' ('a' is varchar(100) in utf8, takes ~300 bytes). All fine. It's "using index", so it reads only index entries (does not jump to rows), from them it gets the value of 'a' and 'master_id'. Only one row can have a certain value of master_id because it's a primary key (* this is an important argument, otherwise I would close this report as "not a bug", because then you could have two rows with the same master_id and not coming one after the other *). Then it does the join to detail_record. It's not using join buffering, so in the output of the join, all rows with the same value of master_record.master_id are still together. So the grouping could, in theory, operate immediately on the join's result, without need to sort.
To sum up, if:
- it's a grouped query
- final result does not have to be sorted (ORDER BY NULL)
- grouping is on the primary key of the first table 
- join buffering is not used for any joined table (otherwise it would shuffle rows),
then filesort has no added value and should not be done. No matter if the first table is read with an index, a table scan.

I'll transfer it inside the team for further evaluation of the difficulty/priority.

Hello Guilhem,

I am very happy that you came to this conclusion! Thank you for taking the time of looking into it and further evaluating it. thank you also for summing up the issue in a very clean and expressive way! 

I quickly want to add that the optimization can be carried out if the used index can be used to satisfy the order by clause like in the cases mentioned here: http://dev.mysql.com/doc/refman/5.0/en/order-by-optimization.html. I tried to focus on the simpler case first, but if it really gets implemented I think skipping the filesort as often as possible is a good idea. 

Thank you for further handling the issue and being awesome for putting effort into open source products!

Hello Jan. So, taking your suggestion into account, the idea becomes:

If:
- it's a grouped query
- grouping is on the primary key of the first table 
- the access method on the first table guarantees that ORDER BY will be satisfied (if there is ORDER BY it is an index-based method; but if there is ORDER BY NULL it can also be full table scan)
- join buffering is not used for any joined table (otherwise it would
shuffle rows),
then filesort has no added value and should not be done.

Hello everyone,

I just wanted to ping this issue. Did someone already do some investigations on how hard it will be to implement it?

best Jan

Hello Jan,

Yes, the complexity factor has been assessed, but scheduling of new features and bug fixes can not be advertised, according to company policy.

Hello Jan. One workaround:

alter table master_record add index master_record_id_a_b_IDX (master_id,a,b);

and then:

explain select master_id, group_concat(c) from master_record force index (master_record_id_a_b) left join detail_record using (master_id) where a = "11aabb" group by master_record.master_id order by null;

Not ideal, but avoids filesort for this query.

Or just this:
alter table master_record add index master_record_a_IDX (a);
then no "force index" is needed in the SELECT, MySQL picks this index up, and no filesort.

Hi  Guilhem,

thank you for pointing out a possible solution. The example I used was a simplified example. In reality we have a multicolumn index that is sometimes used with in() clauses. 

We ended up with more application logic that separates everything into single selects that get unioned using "union all". This works for us currently. But we would prefer to drop this peace of code. 

I can understand that the internal estimations of resources and complexity are disclosed, but I was happy to hear that this ticket is addressed :)

Best,
Jan