Adding ORDER BY significantly slows down JOIN query even though all relevant columns are indexed. How can I make it faster?

Question

I have the following JOIN query:

SELECT
    table1.*, 
    table2.*
FROM 
    Table1 AS table1 
LEFT JOIN 
    Table2 AS table2 
USING 
    (col1)
LEFT JOIN 
    Table3 as table3 
USING 
    (col1) 
WHERE 
    3963.191 * 
    ACOS(
    (SIN(PI() * $usersLatitude / 180) * SIN(PI() * table3.latitude / 180)) 
    +
    (COS(PI() * $usersLatitude / 180) * COS(PI() * table3.latitude / 180) * COS(PI() * table3.longitude / 180 - PI() * 37.1092162 / 180))
    ) <= 10 
AND 
    table1.col1 != '1' 
AND 
    table1.col2 LIKE 'A' 
AND 
    (table1.col3 LIKE 'X' OR table1.col3 LIKE 'X-Y') 
AND 
    (table2.col4 = 'Y' OR table2.col5 = 'Y') 

It executes in under 0.15 seconds.

However, if I simply add:

ORDER BY 
    table1.col6 DESC 

It executes in over 3 seconds.

All columns in the query are indexed, including the table1.col6 used in the ORDER BY.

I tried this solution, but it did not work.

How can I get this query to run fast with the ORDER BY.

---

EDIT:

RESULTS OF EXPLAIN EXTENDED WITHOUT ORDER BY:

id  select_type table   type    possible_keys   key key_len ref rows    filtered    Extra
1   SIMPLE  table1  ALL PRIMARY,col2,col3   NULL    NULL    NULL    140101  72.61   Using where
1   SIMPLE  table2  eq_ref  PRIMARY,col4,col5   PRIMARY 4   table1.col1 1   100 Using where
1   SIMPLE  table3  eq_ref  PRIMARY PRIMARY 4   table1.col1 1   100 Using where

RESULTS OF EXPLAIN EXTENDED WITH ORDER BY:

id  select_type table   type    possible_keys   key key_len ref rows    filtered    Extra
1   SIMPLE  table1  ALL PRIMARY,col2,col3   NULL    NULL    NULL    140101  72.61   Using where; Using filesort
1   SIMPLE  table2  eq_ref  PRIMARY,col4,col5   PRIMARY 4   table1.col1 1   100 Using where
1   SIMPLE  table3  eq_ref  PRIMARY PRIMARY 4   table1.col1 1   100 Using where

---

EDIT 2:

Data Types of all columns in the query (as requested):

col1: int(11)
col2: char(1)
col3: varchar(3)
col4: char(1)
col5: char(1)
col6: int(11)
latitude: varchar(25)
longitude: varchar(25)

All 3 tables (table1, table2, and table3) are MyISAM.

Answer 1

This isn't a solution, but it will likely help: avoid using '*' to specify the columns you want and specify them explicitly. When you use * to specify all columns, MySQL has to do more work shunting data around when it's sorting the data, thus more likely to do a filesort, which is slow.

Also, indexing has little or no impact on how easily MySQL can order data, though you should check that it's using BTREE indexes as it's more likely they'll be kept relatively well-ordered.

Worst comes to worst, you might want to take a read of what the MySQL manual has to say about ORDER BY optimisation if you haven't done so already. I can't see anything that would be applicable, but you might see something that I'm missing.

Answer 2

The only other way I can think off to get around this would be to alter the table to default the order by - and then remove the order by from your query all together.

http://dev.mysql.com/doc/refman/5.1/en/alter-table.html

Answer 3

If your query is as fast as you indicated, I would expect it is returning a rather small data set. If that's the case, I would wrap yours as-is and put the ORDER BY OUTIDE it such as...

select
      PreQuery.*
   from
      ( Your Entire Query Without the order by clause ) as PreQuery
   order by
      PreQuery.Col6 Desc

This way, the outer query has nothing to do with existing indexes and just returns the data... then that result will have the order applied per the raw results.

Hope that resolves it for you.

Answer 4

Aside from my other answer offering to wrap your existing query inside a select, then order the results. Here's another option for the query... Correct me if my interpretation is incorrect.

You are doing a LEFT-JOIN to table 2, yet requiring Col4 or Col5 = 'Y' thus indicating an INNER JOIN (record MUST exist on Table1 AND Table2) due to the where clause.

Similarly on your Table 3 joined to table 1, but restricting the distance <= 10, so a LEFT-JOIN is not really accurate as it was part of the WHERE, indicating REQUIRED.

So, my revised query is listed below. I've basically moved the "WHERE" components to the respective table JOIN command. If you really DID mean to have as LEFT-JOIN and want all Table 1 records REGARDLESS of Table2/Table3 records, then you can simply change these to LEFT JOINs.

SELECT STRAIGHT_JOIN
      T1.*, 
      T2.*
   FROM 
      Table1 AS T1
         JOIN Table2 AS T2
            ON T1.Col1 = T2.Col1
            AND ( T2.Col4 = 'Y' OR T2.Col5 = 'Y' )
         JOIN Table3 as T3
            ON T1.Col1 = T3.Col1
            AND 3963.191 
               * ACOS(  (SIN(PI() * $usersLatitude / 180) * SIN(PI() * T3.latitude / 180)) 
                                + (  COS(PI() * $usersLatitude / 180) * COS(PI() * T3.latitude / 180) 
                                   * COS(PI() * table3.longitude / 180 - PI() * 37.1092162 / 180)
                        )   
                     ) <= 10 
   WHERE
          T1.Col2 LIKE 'A'
      AND ( T1.col3 LIKE 'X' OR T1.col3 LIKE 'X-Y') 
      AND T1.Col1 != '1'
   ORDER BY
      T1.Col6

Add Column 6 to table 1's index if applying the order by clause directly

On Table 1, I would have an index on ( Col2, Col3, Col1, Col6 )
On Table 2 on ( Col1, Col4, Col5 )
On Table 3 on ( Col1 )   <-- assume already had this.

Answer 5

Why are you doing LIKEs on non-wildcard values? That's going to be making the planner be more pessimistic. But mostly, you need to look at what the query planner is showing.

Also, have you done an ANALYZE on the tables recently? If the row statistics are off, the planner will make poor choices.