Unable to optimize MySQL query which uses a ORDER BY clause

Question

I'm using Drupal 6 with MySQL version 5.0.95 and at an impasse where one of my queries which displays content based on most recent article date slows down and because of the frequency of being used kills the site performance altogether. The query in question is as below:

     SELECT n.nid, 
            n.title, 
            ma.field_article_date_format_value, 
            ma.field_article_summary_value
       FROM node n 
 INNER JOIN content_type_article ma ON n.nid=ma.nid
 INNER JOIN term_node tn            ON n.nid=tn.nid 
      WHERE tn.tid= 153 
        AND n.status=1 
   ORDER BY ma.field_article_date_format_value DESC 
      LIMIT 0, 11;

The EXPLAIN of the query shows the below result:

+----+-------------+-------+--------+--------------------------+---------+---------+----------------------+-------+---------------------------------+
| id | select_type | table | type   | possible_keys            | key     | key_len | ref                  | rows  | Extra                           |
+----+-------------+-------+--------+--------------------------+---------+---------+----------------------+-------+---------------------------------+
|  1 | SIMPLE      | tn    | ref    | PRIMARY,nid              | PRIMARY | 4       | const                | 19006 | Using temporary; Using filesort |
|  1 | SIMPLE      | ma    | ref    | nid,ix_article_date      | nid     | 4       | drupal_mm_stg.tn.nid |     1 |                                 |
|  1 | SIMPLE      | n     | eq_ref | PRIMARY,node_status_type | PRIMARY | 4       | drupal_mm_stg.ma.nid |     1 | Using where                     |
+----+-------------+-------+--------+--------------------------+---------+---------+----------------------+-------+---------------------------------+

This query seemed relatively simple and straight forward and retrieves articles which belong to a category (term) 153 and are of status 1 (published). But apparently Using temporary table and Using filesort means the query is bound to fail from what I've learnt browsing about it.

Removing field_article_date_format_value from the ORDER BY clause solves the Using temporary; Using filesort reduces the query execution time but is required and cannot be traded off, unfortunately same holds equally true for the site performance.

My hunch is that most of the trouble comes from the term_node table which maps articles to categories and is a many-many relationship table meaning if article X is associated to 5 categories C1....C5 it will have 5 entries in that table, this table is from out-of-the-box drupal.

Dealing with heavy DB content is something new to me and going through some of the similar queries ( When ordering by date desc, "Using temporary" slows down query, MySQL performance optimization: order by datetime field) I tried to create a composite index for the content_type_article whose datetime field is used in the ORDER BY clause along with another key (nid) in it and tried to FORCE INDEX.

    SELECT n.nid, n.title,
           ma.field_article_date_format_value, 
           ma.field_article_summary_value 
      FROM node n 
INNER JOIN content_type_article ma FORCE INDEX (ix_article_date) ON n.nid=ma.nid 
INNER JOIN term_node tn ON n.nid=tn.nid 
     WHERE tn.tid= 153 
       AND n.status=1 
  ORDER BY ma.field_article_date_format_value DESC 
     LIMIT 0, 11;

The result and the following EXPLAIN query did not seem to help much

+----+-------------+-------+--------+--------------------------+-----------------+---------+----------------------+-------+---------------------------------+
| id | select_type | table | type   | possible_keys            | key             | key_len | ref                  | rows  | Extra                           |
+----+-------------+-------+--------+--------------------------+-----------------+---------+----------------------+-------+---------------------------------+
|  1 | SIMPLE      | tn    | ref    | PRIMARY,nid              | PRIMARY         | 4       | const                | 18748 | Using temporary; Using filesort |
|  1 | SIMPLE      | ma    | ref    | ix_article_date          | ix_article_date | 4       | drupal_mm_stg.tn.nid |     1 |                                 |
|  1 | SIMPLE      | n     | eq_ref | PRIMARY,node_status_type | PRIMARY         | 4       | drupal_mm_stg.ma.nid |     1 | Using where                     |
+----+-------------+-------+--------+--------------------------+-----------------+---------+----------------------+-------+---------------------------------+

The fields n.nid, ca.nid, ma.field_article_date_format_value are all indexed. Querying the DB with Limit 0,11 takes approximately 7-10 seconds with the ORDER BY clause but without it the query barely takes a second. The database engine is MyISAM. Any help on this would be greatly appreciated.

Any answer that could help me in getting this query like a normal one (at the same speed as a query without sort by date) would be great. My attempts with creating a composite query as a combination of nid and field_article_date_format_value and use in the query did not help the cause. I'm open to providing additional info on the problem and any new suggestions.

Answer 1

Taking a look at your query and the explain, it seems like having the n.status=1 in the where clause is making the search very inefficient because you need to return the whole set defined by the joins and then apply the status = 1. Try starting the join from the term_node table that is inmediately filtered by the WHERE and then make the joins adding the status condition immediately. Give it a try and please tell me how it goes.

 SELECT n.nid, n.title,
           ma.field_article_date_format_value, 
           ma.field_article_summary_value 
      FROM term_node tn
INNER JOIN node n ON n.nid=tn.nid AND n.status=1
INNER JOIN content_type_article ma FORCE INDEX (ix_article_date) ON n.nid=ma.nid 
     WHERE tn.tid= 153 
  ORDER BY ma.field_article_date_format_value DESC 
     LIMIT 0, 11;

Answer 2

Using temporary; Using filesort means only that MySQL needs to construct a temporary result table and sort it to get the result you need. This is often a consequence of the ORDER BY ... DESC LIMIT 0,n construct you're using to get the latest postings. In itself it's not a sign of failure. See this: http://www.mysqlperformanceblog.com/2009/03/05/what-does-using-filesort-mean-in-mysql/

Here are some things to try. I am not totally sure they'll work; it's hard to know without having your data to experiment with.

Is there a BTREE index on content_type_article.field_article_date_format_value ? If so, that may help.

Do you HAVE to display the 11 most recent articles? Or can you display the 11 most recent articles that have appeared in the last week or month? If so you could add this line to your WHERE clause. It would filter your stuff by date rather than having to look all the way back to the beginning of time for matching articles. This will be especially helpful if you have a long-established Drupal site.

   AND ma.field_article_date_format_value >= (CURRENT_TIME() - INTERVAL 1 MONTH)

First, try to flip the order of the INNER JOIN operations. Second, incorporate the tid=153 into the join criterion. This MAY reduce the size of the temp table you need to sort. All together my suggestions are as follows:

    SELECT n.nid, 
           n.title, 
           ma.field_article_date_format_value, 
           ma.field_article_summary_value
      FROM node n 
INNER JOIN term_node tn            ON (n.nid=tn.nid AND tn.tid = 153) 
INNER JOIN content_type_article ma ON n.nid=ma.nid
     WHERE n.status=1 
       AND ma.field_article_date_format_value >= (CURRENT_TIME() - INTERVAL 1 MONTH)
  ORDER BY ma.field_article_date_format_value DESC 
     LIMIT 0, 11;

Those are

Answer 3

1) Covering indexes

I think the simple answer may be "covering indexes".

Especially on the content_type_article table. The "covering index" has the expression in the ORDER BY as the leading column, and includes all of the columns that are being referenced by the query. Here's the index I created (on my test table):

CREATE INDEX ct_article_ix9 
    ON content_type_article 
       (field_article_date_format_value, nid, field_article_summary_value);

And here's an excerpt of the EXPLAIN I get from the query (after I build example tables, using the InnoDB engine, including a covering index on each table):

_type  table type  key              ref          Extra                     
------ ----- ----- --------------   -----------  ------------------------
SIMPLE  ma   index ct_article_ix9   NULL         Using index
SIMPLE  n    ref   node_ix9         ma.nid       Using where; Using index
SIMPLE  tn   ref   term_node_ix9    n.nid,const  Using where; Using index

Note that there's no 'Using filesort' shown in the plan, and the plan shows 'Using index' for each table referenced in the query, which basically means that all of the data needed by the query is retrieved from the index pages, with no need to reference any pages from the underlying table. (Your tables have a lot more rows than my test tables, but if you can get an explain plan that looks like this, you may get better performance.)

---

For completeness, here's the entire EXPLAIN output:

+----+-------------+-------+-------+---------------+----------------+---------+---------------------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key            | key_len | ref                 | rows | Extra                    |
+----+-------------+-------+-------+---------------+----------------+---------+-------- ------------+------+--------------------------+
|  1 | SIMPLE      | ma    | index | NULL          | ct_article_ix9 | 27      | NULL                |    1 | Using index              |
|  1 | SIMPLE      | n     | ref   | node_ix9      | node_ix9       | 10      | testps.ma.nid,const |   11 | Using where; Using index |
|  1 | SIMPLE      | tn    | ref   | term_node_ix9 | term_node_ix9  | 10      | testps.n.nid,const  |   11 | Using where; Using index |
+----+-------------+-------+-------+---------------+----------------+---------+---------------------+------+--------------------------+
3 rows in set (0.00 sec)

---

I made no changes to your query, except to omit the FORCE INDEX hint. Here are the other two "covering indexes" that I created on the other two tables referenced in the query:

CREATE INDEX node_ix9
    ON node (`nid`,`status`,`title`);

CREATE INDEX term_node_ix9
    ON term_node (nid,tid);

(Note that if nid is the clustering key on the node table, you may not need the covering index on the node table.)

---

2) Use correlated subqueries in place of joins?

If the previous idea doesn't improve anything, then, as another alternative, since the original query is returning a maximum of 11 rows, you might try rewriting the query to avoid the join operations, and instead make use of correlated subqueries. Something like the query below.

Note that this query differs significantly from the original query. The difference is that with this query, a row from the context_type_article table will be returned only one time. With the query using the joins, a row from that table could be matched to multiple rows from node and term_node tables, which would return that same row more than once. This may be viewed as either desirable or undesirable, it really depends on the cardinality, and whether the resultset meets the specification.

 SELECT ( SELECT n2.nid
            FROM node n2 
           WHERE n2.nid = ma.nid
             AND n2.status = 1
           LIMIT 1
        ) AS `nid`
      , ( SELECT n3.title 
            FROM node n3
           WHERE n3.nid = ma.nid
             AND n3.status = 1
           LIMIT 1
        ) AS `title`
      , ma.field_article_date_format_value
      , ma.field_article_summary_value
   FROM content_type_article ma
  WHERE EXISTS 
        ( SELECT 1
            FROM node n1
           WHERE n1.nid = ma.nid
             AND n1.status = 1
         )                 
     AND EXISTS
         ( SELECT 1
             FROM term_node tn
            WHERE tn.nid = ma.nid
             AND tn.tid = 153
         )
   ORDER BY ma.field_article_date_format_value DESC
   LIMIT 0,11

(Sometimes, a query using this type of "orrelated subquery" can have considerably WORSE performance than an equivalent query that does join operations. But in some cases, a query like this can actually perform better, especially given a very limited number of rows being returned.)

Here's the explain output for that query:

+----+--------------------+-------+-------+---------------+----------------+---------+---------------------+------+--------------------------+
| id | select_type        | table | type  | possible_keys | key            | key_len | ref                 | rows | Extra                    |
+----+--------------------+-------+-------+---------------+----------------+---------+---------------------+------+--------------------------+
|  1 | PRIMARY            | ma    | index | NULL          | ct_article_ix9 | 27      | NULL                |   11 | Using where; Using index |
|  5 | DEPENDENT SUBQUERY | tn    | ref   | term_node_ix9 | term_node_ix9  | 10      | testps.ma.nid,const |   13 | Using where; Using index |
|  4 | DEPENDENT SUBQUERY | n1    | ref   | node_ix9      | node_ix9       | 10      | testps.ma.nid,const |   12 | Using where; Using index |
|  3 | DEPENDENT SUBQUERY | n3    | ref   | node_ix9      | node_ix9       | 10      | testps.ma.nid,const |   12 | Using where; Using index |
|  2 | DEPENDENT SUBQUERY | n2    | ref   | node_ix9      | node_ix9       | 10      | testps.ma.nid,const |   12 | Using where; Using index |
+----+--------------------+-------+-------+---------------+----------------+---------+---------------------+------+--------------------------+
5 rows in set (0.00 sec)

Note that again, each access is 'Using index', which means the query is satisfied directly from index pages, rather than having to visit any data pages in the underlying table.

---

Example tables

Here are the example tables (along with the indexes) that I built and populated, based on the information from your question:

CREATE TABLE `node` (`id` INT PRIMARY KEY, `nid` INT, `title` VARCHAR(10),`status` INT);
CREATE INDEX node_ix9 ON node (`nid`,`status`,`title`);
INSERT INTO `node` VALUES (1,1,'foo',1),(2,2,'bar',0),(3,3,'fee',1),(4,4,'fi',0),(5,5,'fo',1),(6,6,'fum',0),(7,7,'derp',1);
INSERT INTO `node` SELECT id+7,nid+7,title,`status` FROM node;
INSERT INTO `node` SELECT id+14,nid+14,title,`status` FROM node;
INSERT INTO `node` SELECT id+28,nid+28,title,`status` FROM node;
INSERT INTO `node` SELECT id+56,nid+56,title,`status` FROM node;

CREATE TABLE content_type_article (id INT PRIMARY KEY, nid INT, field_article_date_format_value DATETIME, field_article_summary_value VARCHAR(10));
CREATE INDEX ct_article_ix9 ON content_type_article (field_article_date_format_value, nid, field_article_summary_value);
INSERT INTO content_type_article VALUES (1001,1,'2012-01-01','foo'),(1002,2,'2012-01-02','bar'),(1003,3,'2012-01-03','fee'),(1004,4,'2012-01-04','fi'),(1005,5,'2012-01-05','fo'),(1006,6,'2012-01-06','fum'),(1007,7,'2012-01-07','derp');
INSERT INTO content_type_article SELECT id+7,nid+7, DATE_ADD(field_article_date_format_value,INTERVAL 7 DAY),field_article_summary_value FROM content_type_article;
INSERT INTO content_type_article SELECT id+14,nid+14, DATE_ADD(field_article_date_format_value,INTERVAL 14 DAY),field_article_summary_value FROM content_type_article;
INSERT INTO content_type_article SELECT id+28,nid+28, DATE_ADD(field_article_date_format_value,INTERVAL 28 DAY),field_article_summary_value FROM content_type_article;
INSERT INTO content_type_article SELECT id+56,nid+56, DATE_ADD(field_article_date_format_value,INTERVAL 56 DAY),field_article_summary_value FROM content_type_article;

CREATE TABLE term_node (id INT, tid INT, nid INT);
CREATE INDEX term_node_ix9 ON term_node (nid,tid);
INSERT INTO term_node VALUES (2001,153,1),(2002,153,2),(2003,153,3),(2004,153,4),(2005,153,5),(2006,153,6),(2007,153,7);
INSERT INTO term_node SELECT id+7, tid, nid+7 FROM term_node;
INSERT INTO term_node SELECT id+14, tid, nid+14 FROM term_node;
INSERT INTO term_node SELECT id+28, tid, nid+28 FROM term_node;
INSERT INTO term_node SELECT id+56, tid, nid+56 FROM term_node;

Answer 4

MySQL is "optimizing" your query so that it selects from the term_node table first, even though you are specifying to select from node first. Not knowing the data, I'm not sure which is the optimal way. The term_node table is certainly where your performance issues are since ~19,000 records is being selected from there.

Limits without ORDER BY are almost always faster because MySQL stops as soon as it finds the specified limit. With an ORDER BY, it first has to find all the records and sort them, then get the specified limit.

The simple thing to try is moving your WHERE condition into the JOIN clause, which is where it should be. That filter is specific to the table being joined. This will make sure MySQL doesn't optimize it incorrectly.

INNER JOIN term_node tn ON n.nid=tn.nid AND tn.tid=153

A more complicated thing is to do a SELECT on the term_node table and JOIN on that. That's called a DERIVED TABLE and you will see it defined as such in the EXPLAIN. Since you said it was a many-to-many, I added a DISTINCT parameter to reduce the numbers of records to join on.

SELECT ...
FROM node n
INNER JOIN content_type_article ma FORCE INDEX (ix_article_date) ON n.nid=ma.nid
INNER JOIN (SELECT DISTINCT nid FROM term_node WHERE tid=153) tn ON n.nid=tn.nid
WHERE n.status=1
ORDER BY ma.field_article_date_format_value DESC 
LIMIT 0,11

MySQL 5.0 has some limitations with derived tables, so this may not work. Although there are work arounds.

Answer 5

You really want to avoid the sort operation happening at all if you can by taking advantage of a pre-sorted index.

To find out if this is possible, imagine your data denormalised into a single table, and ensure that everything that must be included in your WHERE clause is specifiable with a SINGLE VALUE. e.g. if you must use an IN clause on one of the columns, then sorting is inevitable.

Here's a screenshot of some sample data:

So, if you DID have your data denormalised, you could query on tid and status using single values and then sort by date descending. That would mean the following index in that case would work perfectly:

create index ix1 on denormalisedtable(tid, status, date desc);

If you had this, your query would only hit the top 10 rows and would never need to sort.

So - how do you get the same performance WITHOUT denormalising...

I think you should be able to use the STRAIGHT_JOIN clause to force the order that MySQL selects from the tables - you want to get it to select from the table you are SORTING last.

Try this:

SELECT n.nid, 
        n.title, 
        ma.field_article_date_format_value, 
        ma.field_article_summary_value
FROM node n 
STRAIGHT_JOIN term_node tn            ON n.nid=tn.nid 
STRAIGHT_JOIN content_type_article ma ON n.nid=ma.nid
WHERE tn.tid= 153 
    AND n.status=1 
ORDER BY ma.field_article_date_format_value DESC 
LIMIT 0, 11;

The idea is to get MySQL to select from the node table and then from the term_node table and THEN FINALLY from the content_type_article table (the table containing the column you are sorting on).

This last join is your most important one and you want it to happen using an index so that the LIMIT clause can work without needing to sort the data.

This single index MIGHT do the trick:

create index ix1 on content_type_article(nid, field_article_date_format_value desc);

or

create index ix1 on content_type_article(nid, field_article_date_format_value desc, field_article_summary_value);

(for a covering index)

I say MIGHT, because I don't know enough about the MySQL optimiser to know if it's clever enough to handle the multiple 'nid' column values that will be getting fed into the content_type_article without having to resort the data.

Logically, it should be able to work quickly - e.g. if 5 nid values are getting fed into the final content_type_article table, then it should be able to get the top 10 of each directly from the index and merge the results together then pick the final top 10, meaning a total of 50 rows read from this table insted of the full 19006 that you're seeing currently.

Let me know how it goes.

If it works for you, further optimisation will be possible using covering indexes on the other tables to speed up the first two joins.