Why doesn't MySQL's query planner rewrite some ORDER BY.. LIMIT queries to use a UNION strategy? No clue.

I had always assumed that if we had a table widgets with an index on (gid, id) that all queries that filtered for gid and then ordered by id with a limit would be fast. Oops!

The simple case with we have a single id is fast: SELECT * FROM widgets WHERE gid = 1 ORDER BY id LIMIT 10. MySQL is able to consult the (gid, id) index to get the first ten documents, then use the id to look up the original documents. Here's what that looks like with explain analyze:

| -> Limit: 10 row(s)  (cost=3588 rows=10) (actual time=0.332..0.334 rows=10 loops=1)
    -> Covering index lookup on widgets using gid_id (gid=1)  (cost=3588 rows=35740) (actual time=0.303..0.305 rows=10 loops=1)

The key thing to notice is that it only needed to look up 10 rows (actual ...rows=10), just like we'd expect.

But things immediately start to go awry when we add a second gid: SELECT * FROM widgets WHERE gid IN (1, 2) ORDER BY id LIMIT 10. Naively, I would expect this to look up twice as many rows as the previous query. That's not what happens:

| -> Limit: 10 row(s)  (cost=13870 rows=10) (actual time=9.93..9.93 rows=10 loops=1)
    -> Sort: widgets.id, limit input to 10 row(s) per chunk  (cost=13870 rows=69214) (actual time=9.9..9.9 rows=10 loops=1)
        -> Filter: (widgets.gid in (1,2))  (cost=13870 rows=69214) (actual time=0.56..7.08 rows=40000 loops=1)
            -> Index range scan on widgets using gid_id over (gid = 1) OR (gid = 2)  (cost=13870 rows=69214) (actual time=0.512..4.84 rows=40000 loops=1)

It's looking up 40,000 rows (actual ... rows=40000)! It needs to look up every single row that matches either gid=1 or gid=2. That's a lot more than the 20 rows that it should need.

I tried various query planner optimization settings and hints, but none of those settings let me convince MySQL to choose a better query plan. I ended up needing to rewrite the query to use a union:

(SELECT * FROM widgets WHERE gid = 1 ORDER BY id LIMIT 10)
UNION ALL
(SELECT * FROM widgets WHERE gid = 2 ORDER BY id LIMIT 10)
ORDER BY ID
LIMIT 10;

The plan for this looks up only 20 rows, sorts them, and then filters them down to 10 rows:

| -> Limit: 10 row(s)  (cost=6959..6959 rows=10) (actual time=0.525..0.526 rows=10 loops=1)
    -> Sort: id, limit input to 10 row(s) per chunk  (cost=6959..6959 rows=10) (actual time=0.525..0.525 rows=10 loops=1)
        -> Table scan on <union temporary>  (cost=6951..6954 rows=20) (actual time=0.463..0.465 rows=20 loops=1)
            -> Union all materialize  (cost=6951..6951 rows=20) (actual time=0.462..0.462 rows=20 loops=1)
                -> Limit: 10 row(s)  (cost=3588 rows=10) (actual time=0.265..0.267 rows=10 loops=1)
                    -> Covering index lookup on widgets using gid_id (gid=1)  (cost=3588 rows=35740) (actual time=0.264..0.265 rows=10 loops=1)
                -> Limit: 10 row(s)  (cost=3361 rows=10) (actual time=0.188..0.189 rows=10 loops=1)
                    -> Covering index lookup on widgets using gid_id (gid=2)  (cost=3361 rows=33474) (actual time=0.188..0.188 rows=10 loops=1)

As we'd expect, it's faster than the version that looks up 40,000 rows (actual time=0.525..0.526 vs. actual time=9.93..9.93), even though it needs to create a temporary table to do the union all.

If we wanted, we could slightly reduce the work we needed to for this query if we did the parts of the union one at a time and used the results to restrict possible values for subsequent queries. I wouldn't want to do this in SQL or when I only had two values, but here's what that might look like:

drop table if exists results;
SET @start_time = sysdate(6);
CREATE TEMPORARY TABLE results AS (
    SELECT * FROM widgets WHERE gid = 1 ORDER BY id LIMIT 10
);

INSERT INTO results
SELECT *
FROM widgets
WHERE gid = 2
ORDER BY id LIMIT 10;

SELECT *
FROM results
ORDER BY id
LIMIT 10;

SELECT TIMESTAMPDIFF(MICROSECOND, sysdate(6), @start_time); -- ~2ms

Am I missing something totally obvious in the MySQL docs? Is there a query hint I can use to force these queries to use a better query plan without totally rewriting them? And am I missing something about the rationale here? This doesn't feel like a crazy query pattern to me; why isn't it better-supported by the query planner?

Appendix: Table Setup

Creating the widgets table and index

DROP TABLE IF EXISTS widgets;
CREATE TABLE widgets (
  id INT UNSIGNED AUTO_INCREMENT PRIMARY KEY,
  gid INT UNSIGNED,
  INDEX gid_id (gid, id)
);
INSERT INTO widgets (gid)
SELECT
    num % 5 as gid
FROM numbers
WHERE num BETWEEN 0 and 99999;

Creating the nums view

create or replace view digits as
    select 0 as d
    union select 1
    union select 2
    union select 3
    union select 4
    union select 5
    union select 6
    union select 7
    union select 8
    union select 9;
create or replace view numbers as
    select
        ten_thou * 10000 + thou * 1000 + hun * 100 + ten * 10 + one as num
    from (
        select ten_thou.d as ten_thou, thou.d as thou, hun.d as hun, ten.d as ten, one.d as one
        FROM
            digits as ten_thou,
            digits as thou,
            digits as hun,
            digits as ten,
            digits as one
    ) nums
    ORDER BY 1 ASC;