JOINed ORDERed LIMITed query not optimized enough - need help

Hi all,

I need to retrieve 13 rows from a 100,000-row JOIN, starting with a row
with given values.
All required indexes are available AFAICT, yet EXPLAIN tells me mysql is
"Using index; Using temporary; Using filesort" on the first table it's
touching.

I don't know where I'm going wrong, or whether I'm hitting a limitation
of mysql's query optimizer. Any help appreciated.

DETAILS

mysql version is 5.0.15.

Tables are set up like this:

-- Main categories. An ID and a name.
CREATE TABLE main (
   id int(9),
   name varchar(40),
   PRIMARY KEY (id),
   KEY name (name)
) TYPE = InnoDB;
-- Sample categories. Choose random numbers so that id order and name
-- order are different.
INSERT INTO main VALUES
   (0, CONCAT(RAND(), ' main 0')),
   ...
   (9, CONCAT(RAND(), ' main 9'));
-- Just not to leave this stone unturned:
ANALYZE TABLE main;

-- Subcategories. ID-plus-name.
-- An additional foreign key that links up with the 'main' table.
CREATE TABLE sub (
   id int(9),
   name varchar(40),
   main_id int(9),
   PRIMARY KEY (id),
   KEY name_main (name, main_id),
   KEY main_name (main_id, name)
) TYPE = InnoDB;
INSERT INTO sub VALUES
   (000, CONCAT(RAND(), ' main 0 sub 000'), 0),
   ...
   (999, CONCAT(RAND(), ' main 0 sub 099'), 9);
ANALYZE TABLE sub;

-- Finally, detail records, all 100,000 of them.
CREATE TABLE detail (
   id int(9),
   name varchar(40),
   sub_id int(9),
   PRIMARY KEY (id),
   KEY name_sub (name, sub_id),
   KEY sub_name (sub_id, name)
) TYPE = InnoDB;
INSERT INTO detail VALUES
   (00000, CONCAT(RAND(), ' sub 000 detail 00000'), 000),
   ...
   (99999, CONCAT(RAND(), ' sub 999 detail 99999'), 999);
ANALYZE TABLE detail;


Now I want to present a detail-sub-main list to the end user:

SELECT * FROM
   main
   JOIN sub ON main.id = sub.main_id
   JOIN detail ON sub.id = detail.sub_id

I want this to be sorted by detail name, then sub name, finally main name:

SELECT * FROM
   main
   JOIN sub ON main.id = sub.main_id
   JOIN detail ON sub.id = detail.sub_id
   ORDER by detail.name, sub.name, main.name

The user isn't supposed to see the entire list, he's scrolling through 
it. Let's say he's at the record with detail name '0.5xxxx' and needs to 
see the next 12 records, then I have

SELECT * FROM
   main
   JOIN sub ON main.id = sub.main_id
   JOIN detail ON sub.id = detail.sub_id
   WHERE detail.name > '0.5'
   ORDER by detail.name, sub.name, main.name
   LIMIT 12

This takes just 0.46-0.54 seconds to complete on my machine, but the 
real thing with 150,000 detail records and four additional JOINs to 
produce auxiliary information is unbearably slow: 25-40 seconds.

Now EXPLAIN tells me mysql started with the 'main' table - that's just 
backwards, it should have started with 'detail' to find just the first 
twelve rows, then work up through 'sub' to 'main'!
It's no surprise that it then needed to "use temporary; use filesort".

Well, to speed up this particular case, I might be able to use a 
STRAIGHT JOIN. However, that would require reordering the JOIN part of 
the query, and I'd like to avoid that if possible - I'd have to do some 
serious rewriting of the dynamic SQL part of the application.

Hints, tips, improvements very much appreciated.

Regards,
Jo

> Well, to speed up this particular case, I might be able to use a 

Update: I just tried STRAIGHT_JOIN.
It doesn't help either.

Strangely enough, the mysql manual says this on 
 http://www.**--****.com/ :
"If you use LIMIT row_count with ORDER BY, MySQL ends the sorting as 
soon as it has found the first row_count rows of the sorted result, 
rather than sorting the entire result. If ordering is done by using an 
index, this is very fast."

That's exactly what I hoped for.
However, the text goes on to say:

"If a filesort must be done, all rows that match the query without the 
LIMIT clause must be selected, and most or all of them must be sorted, 
before it can be ascertained that the first row_count rows have been found."

Now EXPLAIN indeed says that it's using a filesort:

id: 1
select_type: SIMPLE
table: detail
type: range
possible_keys: name_sub, sub_name
key: name_sub
key_len: 43
ref: NULL
rows: 50231 (that's probably the number of rows that are >= '0.5')
Extra: Using where; Using index; Using temporary; Using filesort


... but why?


Regards,
Jo

table main:        10 rows
table sub:      1.000 rows
table detail: 100.000 rows

This is potentially a 1.000.000.000 row JOIN result.



If you ORDER BY columns from different tables, then MySQL always uses
external sorting of the result set:
 http://www.**--****.com/ 


LIMIT doesn't help here. Before LIMIT can be applied, sorting has to be
done. Before sorting can be done, the complete result set must be known.


Nope. The first 12 rows in table detail may not have corresponding rows
in the sub table and may thus not be part of the unLIMITed join result.
If the first N rows from detail all have the same value in name, then
the sort order is unknown unless MySQL looks at the other JOINed tables.

LIMIT is done last, with one exception: if MySQL can retrieve rows in
sort order, that is: if there is an index that can be used for finding
rows in the specified result order - then MySQL will stop retrieving
rows when the LIMIT is reached. This is not the case here.


Also the decision of the optimizer depends on many things. The main
goal of the optimizer is to keep the intermediate JOIN result small.
If MySQL JOINs in order main -> sub -> detail there are [10], [at most
10.000], [final] rows in the intermediate results table.

For order sub -> detail -> main this is [100.000 * filter selectivity],
[at most 100.000 * filter selectivity], [final].

Now all depends on how selective your filter on the details table is
(or rather: what the optimizer thinks how selective it is). I guess
detail.name > '0.5' is not very selective. But even if your filter
would yield just 10.000 rows from the detail table, the overall query
cost would still be higher than with the original plan.

It would be interesting to see the query plan when the filter finds
only very few (say 10) rows from the detail table.



This is quite old. I recommend to upgrade to latest 5.0. There have
been many bugfixes and probably optimizer improvements since.


XL
Online User Manual:  http://www.**--****.com/ 
MySQL User Forums:   http://www.**--****.com/