EXPLAIN EXTENDED

From Stack Overflow:

I have a table of blog posts, each with a foreign key back to it's author. There are less than 15,000 entries in this table.

This query scans over 19,000 rows (per EXPLAIN), requires a filesort (that might be regular MySQL behavior), and takes over 400ms to return 5 rows. possibly because of the complicated WHERE used to check if the item is actually published.

SELECT  blog_post.id,
blog_post.title,
blog_post.author_id,
blog_post.has_been_fact_checked,
blog_post.published_date,
blog_post.ordering,
auth_user.username,
auth_user.email
FROM    blog_post
INNER JOIN
auth_user
ON      auth_user.id = blog_post.author_id
WHERE   blog_post.is_approved = 1
AND blog_post.has_been_fact_checked = 1
AND blog_post.published_date <=  '2010-10-25 22:40:05'
ORDER BY
        blog_post.published_date DESC,
        blog_post.ordering ASC,
        blog_post.id DESC
LIMIT 5

How can I wrangle this query under control?

This query is quite simple: a filtering condition with two equalities and a range and an order by. The range in the filter fits the ORDER BY perfectly, so the whole query could be executed using an index scan without any filesorts.

The only problem is that we have the mixed directions in ORDER BY, and MySQL does not support ASC / DESC clauses for the indexes.

With a simple table redesign, the problem could easily be solved: we would just need to reverse the order in the ordering column, say, by creating its copy and storing negative values in it. This way, we could just create a composite index (with all columns ascending) and rewrite the query to use the reverse column instead. That's what many engines do, MediaWiki (which Wikipedia runs on) being one of the most well-known examples.

This solution is nice, I hear people saying, but requires a database redesign which as we all know is never as simple as some development pundits on their blogs seem to think.

OK, this is a good point. Let's see what we can do with the current design, and, as always, create a sample table to do it:

Table creation details

CREATE TABLE filler (
id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

CREATE TABLE blog_post
(
id INT NOT NULL PRIMARY KEY,
title TEXT NOT NULL,
is_approved BOOLEAN NOT NULL,
has_been_fact_checked BOOLEAN NOT NULL,
published_date DATETIME,
ordering INT,
author_id INT NOT NULL,
KEY ix_blogpost_approved_checked_published_ordering_id
(
is_approved,
has_been_fact_checked,
published_date,
ordering
)
)
ENGINE=InnoDB;

CREATE TABLE auth_user
(
id INT NOT NULL PRIMARY KEY,
username VARCHAR(32) NOT NULL,
email VARCHAR(256) NOT NULL
)
ENGINE=InnoDB;

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
DECLARE _cnt INT;
SET _cnt = 1;
WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(500000);
COMMIT;

INSERT
INTO    auth_user
SELECT  id, CONCAT('author', id), CONCAT('author', id, '@example.com')
FROM    filler
LIMIT 1000;

INSERT
INTO    blog_post
SELECT  id, CONCAT('Post ', id),
        RAND(20101102) > 0.05,
RAND(20101102 << 1) > 0.05,
CAST('2010-11-02' AS DATE) - INTERVAL RAND(20101102 << 2) * 100000 HOUR,
        CEILING(RAND(20101102 << 3) * 100),
        CEILING(RAND(20101102 << 4) * 1000)
FROM    filler;

There are 1,000 authors and 500,000 blog posts in the respective tables. The blog posts intentionally have duplicates on published_date.

The original query:

SELECT  blog_post.id,
blog_post.title,
blog_post.author_id,
blog_post.has_been_fact_checked,
blog_post.published_date,
blog_post.ordering,
auth_user.username,
auth_user.email
FROM    blog_post
INNER JOIN
auth_user
ON      auth_user.id = blog_post.author_id
WHERE   blog_post.is_approved = 1
AND blog_post.has_been_fact_checked = 1
AND blog_post.published_date <= '2010-10-25 22:40:05'
ORDER BY
        blog_post.published_date DESC,
        blog_post.ordering ASC,
        blog_post.id DESC
LIMIT 5

select `20101102_desc`.`blog_post`.`id` AS `id`,`20101102_desc`.`blog_post`.`title` AS `title`,`20101102_desc`.`blog_post`.`author_id` AS `author_id`,`20101102_desc`.`blog_post`.`has_been_fact_checked` AS `has_been_fact_checked`,`20101102_desc`.`blog_post`.`published_date` AS `published_date`,`20101102_desc`.`blog_post`.`ordering` AS `ordering`,`20101102_desc`.`auth_user`.`username` AS `username`,`20101102_desc`.`auth_user`.`email` AS `email` from `20101102_desc`.`blog_post` join `20101102_desc`.`auth_user` where ((`20101102_desc`.`auth_user`.`id` = `20101102_desc`.`blog_post`.`author_id`) and (`20101102_desc`.`blog_post`.`has_been_fact_checked` = 1) and (`20101102_desc`.`blog_post`.`is_approved` = 1) and (`20101102_desc`.`blog_post`.`published_date` <= '2010-10-25 22:40:05')) order by `20101102_desc`.`blog_post`.`published_date` desc,`20101102_desc`.`blog_post`.`ordering`,`20101102_desc`.`blog_post`.`id` desc limit 5

As the asker said, this query takes 455 ms and the filesort is used.

Now, as we cannot use a single index on mixed ASC / DESC ordering conditions, we should squeeze the most from our existing index.

The longest common prefix of the index and the ORDER BY expression (which implicitly includes all columns from the WHERE clause) is (is_approved, has_been_fact_checked, published_date).

What does it mean? It means that the chunks of data sharing the distinct values of these three columns will always go in the same order both in the index and in the query, though the order may and will differ within each chunk.

See the queries below, first one with the initial ORDER BY sorting:

SELECT  published_date, id, ordering
FROM    blog_post
WHERE   is_approved = 1
AND has_been_fact_checked = 1
ORDER BY
published_date DESC,
ordering ASC,
id DESC
LIMIT 16

, the second one with the index sorting:

SELECT  published_date, id, ordering
FROM    blog_post
WHERE   is_approved = 1
AND has_been_fact_checked = 1
ORDER BY
published_date DESC,
ordering DESC,
id DESC
LIMIT 16

As you can see, the chunks of data occupy the same places within both recordsets. Post dated 2010-11-02 00:00:00 is at row 1. Those dated 2010-11-01 23:00:00 are at rows 2 — 10 etc. The orders differ only within the chunks, but not between chunks.

This means that if we select the same chunks as the original query does and reorder them, we get the same order.

And the chunks we can select quite efficiently using the index, since their order, as we shown above, is the same for both queries.

The original query had LIMIT 5, this means we have to select at most 5 chunks. To do this, we just need to count off 5 distinct dates satisfying the condition.

This can be done using a technique I described in one of my earlier posts:

• 20 latest unique records

Selecting 5 dates

Here's a query to select 5 distinct dates less than the given one:

SELECT  bp.published_date
FROM    blog_post bp
WHERE   bp.is_approved = 1
AND bp.has_been_fact_checked = 1
AND bp.published_date < '2010-10-25 22:40:05'
        AND bp.id =
        (
        SELECT  id
        FROM    blog_post bpi
        WHERE   bpi.is_approved = 1
                AND bpi.has_been_fact_checked = 1
                AND bpi.published_date = bp.published_date
        ORDER BY
                bpi.is_approved DESC, bpi.has_been_fact_checked DESC, bpi.published_date DESC
        LIMIT 1
        )
ORDER BY
        bp.is_approved DESC, bp.has_been_fact_checked DESC, bp.published_date DESC
LIMIT 5

Field or reference '20101102_desc.bp.published_date' of SELECT #2 was resolved in SELECT #1
select `20101102_desc`.`bp`.`published_date` AS `published_date` from `20101102_desc`.`blog_post` `bp` where ((`20101102_desc`.`bp`.`has_been_fact_checked` = 1) and (`20101102_desc`.`bp`.`is_approved` = 1) and (`20101102_desc`.`bp`.`published_date` < '2010-10-25 22:40:05') and (`20101102_desc`.`bp`.`id` = (select `20101102_desc`.`bpi`.`id` from `20101102_desc`.`blog_post` `bpi` where ((`20101102_desc`.`bpi`.`has_been_fact_checked` = 1) and (`20101102_desc`.`bpi`.`is_approved` = 1) and (`20101102_desc`.`bpi`.`published_date` = `20101102_desc`.`bp`.`published_date`)) order by `20101102_desc`.`bpi`.`is_approved` desc,`20101102_desc`.`bpi`.`has_been_fact_checked` desc,`20101102_desc`.`bpi`.`published_date` desc limit 1))) order by `20101102_desc`.`bp`.`is_approved` desc,`20101102_desc`.`bp`.`has_been_fact_checked` desc,`20101102_desc`.`bp`.`published_date` desc limit 5

This uses the index access and is very efficient.

Selecting chunks of data

Now we need to select all records within the chunks defined by the dates. This can be done with a simple BETWEEN condition. The upper bound of the BETWEEN will be the date that we used as the parameter to the query, and the lower one will be the last date of those selected on the previous stage.

Since it should be a scalar, we will just replace LIMIT 5 (which returns 5 records) with LIMIT 4, 1 (which returns the last of these 5 records) and put it into a scalar subquery:

SELECT  *
FROM    blog_post bpo
WHERE   is_approved = 1
AND has_been_fact_checked = 1
AND published_date BETWEEN
(
SELECT  bp.published_date
FROM    blog_post bp
WHERE   bp.is_approved = 1
AND bp.has_been_fact_checked = 1
AND bp.published_date < '2010-10-25 22:40:05'
                AND bp.id =
                (
                SELECT  id
                FROM    blog_post bpi
                WHERE   bpi.is_approved = 1
                        AND bpi.has_been_fact_checked = 1
                        AND bpi.published_date = bp.published_date
                ORDER BY
                        bpi.is_approved DESC, bpi.has_been_fact_checked DESC, bpi.published_date DESC
                LIMIT 1
                )
        ORDER BY
                bp.is_approved DESC, bp.has_been_fact_checked DESC, bp.published_date DESC
        LIMIT 4, 1
        )
        AND '2010-10-25 22:40:05'

Field or reference '20101102_desc.bp.published_date' of SELECT #3 was resolved in SELECT #2
select `20101102_desc`.`bpo`.`id` AS `id`,`20101102_desc`.`bpo`.`title` AS `title`,`20101102_desc`.`bpo`.`is_approved` AS `is_approved`,`20101102_desc`.`bpo`.`has_been_fact_checked` AS `has_been_fact_checked`,`20101102_desc`.`bpo`.`published_date` AS `published_date`,`20101102_desc`.`bpo`.`ordering` AS `ordering`,`20101102_desc`.`bpo`.`author_id` AS `author_id` from `20101102_desc`.`blog_post` `bpo` where ((`20101102_desc`.`bpo`.`has_been_fact_checked` = 1) and (`20101102_desc`.`bpo`.`is_approved` = 1) and (`20101102_desc`.`bpo`.`published_date` between (select `20101102_desc`.`bp`.`published_date` from `20101102_desc`.`blog_post` `bp` where ((`20101102_desc`.`bp`.`has_been_fact_checked` = 1) and (`20101102_desc`.`bp`.`is_approved` = 1) and (`20101102_desc`.`bp`.`published_date` < '2010-10-25 22:40:05') and (`20101102_desc`.`bp`.`id` = (select `20101102_desc`.`bpi`.`id` from `20101102_desc`.`blog_post` `bpi` where ((`20101102_desc`.`bpi`.`has_been_fact_checked` = 1) and (`20101102_desc`.`bpi`.`is_approved` = 1) and (`20101102_desc`.`bpi`.`published_date` = `20101102_desc`.`bp`.`published_date`)) order by `20101102_desc`.`bpi`.`is_approved` desc,`20101102_desc`.`bpi`.`has_been_fact_checked` desc,`20101102_desc`.`bpi`.`published_date` desc limit 1))) order by `20101102_desc`.`bp`.`is_approved` desc,`20101102_desc`.`bp`.`has_been_fact_checked` desc,`20101102_desc`.`bp`.`published_date` desc limit 4,1) and '2010-10-25 22:40:05'))

This query returns (almost instantly) 20 records in 5 chunks of different size (split for readability). Note that the chunks are arranged in order reverse to the order the dates were returned on the previous step: we omitted the ORDER BY clause and, by default, the index is traversed in forward (ASC) direction.

Ordering and joining

Now, all that's left to do is to add the correct ORDER BY condition to rearrange the data within the chunks, join the authors table and apply the LIMIT:

SELECT  bpo.id,
bpo.title,
bpo.author_id,
bpo.has_been_fact_checked,
bpo.published_date,
bpo.ordering,
au.username,
au.email
FROM    blog_post bpo
JOIN    auth_user au
ON      au.id = bpo.author_id
WHERE   bpo.is_approved = 1
AND bpo.has_been_fact_checked = 1
AND bpo.published_date BETWEEN
(
SELECT  bp.published_date
FROM    blog_post bp
WHERE   bp.is_approved = 1
AND bp.has_been_fact_checked = 1
AND bp.published_date < '2010-10-25 22:40:05'
                AND bp.id =
                (
                SELECT  id
                FROM    blog_post bpi
                WHERE   bpi.is_approved = 1
                        AND bpi.has_been_fact_checked = 1
                        AND bpi.published_date = bp.published_date
                ORDER BY
                        bpi.is_approved DESC, bpi.has_been_fact_checked DESC, bpi.published_date DESC
                LIMIT 1
                )
        ORDER BY
                bp.is_approved DESC, bp.has_been_fact_checked DESC, bp.published_date DESC
        LIMIT 4, 1
        )
        AND '2010-10-25 22:40:05'
ORDER BY
        bpo.published_date DESC,
        bpo.ordering ASC,
        bpo.id DESC
LIMIT 5

Field or reference '20101102_desc.bp.published_date' of SELECT #3 was resolved in SELECT #2
select `20101102_desc`.`bpo`.`id` AS `id`,`20101102_desc`.`bpo`.`title` AS `title`,`20101102_desc`.`bpo`.`author_id` AS `author_id`,`20101102_desc`.`bpo`.`has_been_fact_checked` AS `has_been_fact_checked`,`20101102_desc`.`bpo`.`published_date` AS `published_date`,`20101102_desc`.`bpo`.`ordering` AS `ordering`,`20101102_desc`.`au`.`username` AS `username`,`20101102_desc`.`au`.`email` AS `email` from `20101102_desc`.`blog_post` `bpo` join `20101102_desc`.`auth_user` `au` where ((`20101102_desc`.`au`.`id` = `20101102_desc`.`bpo`.`author_id`) and (`20101102_desc`.`bpo`.`has_been_fact_checked` = 1) and (`20101102_desc`.`bpo`.`is_approved` = 1) and (`20101102_desc`.`bpo`.`published_date` between (select `20101102_desc`.`bp`.`published_date` from `20101102_desc`.`blog_post` `bp` where ((`20101102_desc`.`bp`.`has_been_fact_checked` = 1) and (`20101102_desc`.`bp`.`is_approved` = 1) and (`20101102_desc`.`bp`.`published_date` < '2010-10-25 22:40:05') and (`20101102_desc`.`bp`.`id` = (select `20101102_desc`.`bpi`.`id` from `20101102_desc`.`blog_post` `bpi` where ((`20101102_desc`.`bpi`.`has_been_fact_checked` = 1) and (`20101102_desc`.`bpi`.`is_approved` = 1) and (`20101102_desc`.`bpi`.`published_date` = `20101102_desc`.`bp`.`published_date`)) order by `20101102_desc`.`bpi`.`is_approved` desc,`20101102_desc`.`bpi`.`has_been_fact_checked` desc,`20101102_desc`.`bpi`.`published_date` desc limit 1))) order by `20101102_desc`.`bp`.`is_approved` desc,`20101102_desc`.`bp`.`has_been_fact_checked` desc,`20101102_desc`.`bp`.`published_date` desc limit 4,1) and '2010-10-25 22:40:05')) order by `20101102_desc`.`bpo`.`published_date` desc,`20101102_desc`.`bpo`.`ordering`,`20101102_desc`.`bpo`.`id` desc limit 5

The records have been rearranged (using a filesort) and a LIMIT was applied.

Since the records are only taken from 5 chunks with 20 records in total, the filesort is not a problem at all and the query completes in only 4 ms.

Conclusion

MySQL does not support ASC / DESC clauses in the indices.

However, with an ORDER BY / LIMIT condition that mixes the orders of columns, it is possible to use an index.

To do that, we should limit the recordset to the minimal set that would still retain the order on the leading columns that share one direction. This can be done by selecting distinct set of those leading columns up to the original limit, and filtering on them using the index.

Then we can revert to a filesort to order this (much smaller) set on the remaining columns, which would be much more efficient.