MySQL 8 query doesn't prefer index with higher cardinality

Question

I have a query similar to the following:

FROM example_table
WHERE 
    `date` BETWEEN '2023-11-26' AND '2023-11-28'
    AND location_id IN (3, 4, 6, 7, 8, 10, 11, 12, 14, 18, 19, 22, 23, 24, 28, 29, 30, 31, 32, 36, 39, 40, 41, 43, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 59, 60, 61, 62, 68, 69, 75, 121)
    AND ( `type` IS NULL OR ( `type` IN ('type1', 'type2', 'type3') ) )
GROUP BY location_id;

My understanding is that, while creating a multi column index, the column with higher cardinality / selectivity goes first. I tried testing the performance with two index keys:

1. (date, location_id, type, amount)
2. (location_id, date, type, amount)

In my actual table, I have 11,833 unique values in the date column, and only 99 in location_id. Currently, there are 63+ million rows.

Nevertheless, MySQL 8 prefers to use the one starting with location_id. Even when I try FORCE INDEX and EXPLAIN ANALYZE, it shows a higher cost / time on the one starting with date.

What could be going on?

EDIT:

EXPLAIN ANALYZE:

1. date first index

    -> Group aggregate: sum(ledger_entries.amount_cents)  (cost=1897 rows=6236) (actual time=0.167..4.67 rows=43 loops=1)
        -> Filter: ((ledger_entries.`date` = DATE'2023-11-28') and (ledger_entries.location_id in (3,4,6,7,8,10,11,12,14,18,19,22,23,24,28,29,30,31,32,36,39,40,41,43,45,46,48,49,50,51,52,54,55,56,57,59,60,61,62,68,69,75,121)) and ((ledger_entries.`type` is null) or (ledger_entries.`type` in ('Procedure','Adjustment','AncillarySale'))))  (cost=1273 rows=6236) (actual time=0.0221..4.09 rows=6192 loops=1)
            -> Covering index range scan on ledger_entries using index_le_date_location_type_amount_cents over (date = '2023-11-28' AND location_id = 3 AND type = NULL) OR (date = '2023-11-28' AND location_id = 3 AND type = 'Adjustment') OR (170 more)  (cost=1273 rows=6236) (actual time=0.02..2.83 rows=6192 loops=1)

2. location first index

    -> Group aggregate: sum(ledger_entries.amount_cents)  (cost=1888 rows=6236) (actual time=0.171..4.74 rows=43 loops=1)
        -> Filter: ((ledger_entries.`date` = DATE'2023-11-28') and (ledger_entries.location_id in (3,4,6,7,8,10,11,12,14,18,19,22,23,24,28,29,30,31,32,36,39,40,41,43,45,46,48,49,50,51,52,54,55,56,57,59,60,61,62,68,69,75,121)) and ((ledger_entries.`type` is null) or (ledger_entries.`type` in ('Procedure','Adjustment','AncillarySale'))))  (cost=1265 rows=6236) (actual time=0.0244..4.15 rows=6192 loops=1)
            -> Covering index range scan on ledger_entries using ledger_entries_location_date_type_amount_cents over (location_id = 3 AND date = '2023-11-28' AND type = NULL) OR (location_id = 3 AND date = '2023-11-28' AND type = 'Adjustment') OR (170 more)  (cost=1265 rows=6236) (actual time=0.022..2.91 rows=6192 loops=1)

Answer 1

My understanding is that, while creating a multi column index, the column with higher cardinality / selectivity goes first.

That makes sense if you also want to reuse that index with queries that don't use all the indexed columns. If you have an index on (a,b,c) it will also serve as index on (a,b) and (a) for free. These "free" indices are much more useful if (a) and/or (a,b) have good selectivity (high cardinality). Otherwise if (a) has low cardinality then an index on (a) alone is useless.

Now your query does:

date BETWEEN date1 and date2
AND location_id IN (big list)
GROUP BY location_id

With a btree index on (location_id,date) it's pretty simple, the algo would be like:

for loc_id in (big_list):
    range query on (location_id,date) BETWEEN (loc_id,date1) AND (loc_id,date2)

A btree index on (a,b,c) is ordered by (a,b,c) so it supports range queries on any subset of columns as long as they're (a), (a,b) or (a,b,c). But not any other combination or any other order.

Hmm... Now I have to explain tuple ordering... It's like ordering by (last_name,first_name). In this case a range query on (location_id,date) between (1,'2022-01-02') and (1,'2022-01-04') will select these rows:

loc   date
-----------
1     2023-01-01
1     2023-01-02 <-range start and read next
1     2023-01-03 <-read next
1     2023-01-04 <-read and stop
2     2023-01-01
2     2023-01-02
2     2023-01-03
2     2023-01-04

...all it does is find the first row of the range then read the index rows in order until the end of the range, which is very fast. So you have one index lookup per loc_id, then read range. As a bonus, data is already ordered by location_id so it doesn't need to do any extra work for the group by. Looks good.

With a btree index on (date,location_id), it's a lot more complicated. Let's take the previous data and make an ordered index again.

date         loc
----------------
2023-01-01   1
2023-01-01   2
2023-01-02   1
2023-01-02   2
2023-01-03   1
2023-01-03   2
2023-01-04   1
2023-01-04   2

The problem here is that the index columns are swapped but the range query is still on the same column as before. It's still the date. If you have an index on (date,loc) it can efficiently do a range query on (date) but the index will not filter by loc. That has to be done after reading the rows from the index. Let's do the range query on date between '2022-01-02' and '2022-01-04':

date         loc
----------------
2023-01-01   1
2023-01-01   2
2023-01-02   1 <- range start and read next
2023-01-02   2 <- read next
2023-01-03   1 <- read next
2023-01-03   2 <- read next
2023-01-04   1 <- read next
2023-01-04   2 <- read and stop

So it will scan and read through many rows with location_id's that are not in your (big list), then throw them away. This is still good if the date range is small, it's better to read 1% of the table and throw away most of it than to not have the index, read the whole the table and also throw away most of it to end up with the same result.

In addition the resulting rows are not ordered by location_id so the group by needs extra work.

Therefore the query plan choice is logical.

Indices can also be used to avoid sorting, so an index on (loc,date) will optimize "WHERE loc=... AND date BETWEEN ... ORDER B date", but it will not work if the query has "loc IN (...)" because then it would indeed read several chunks in date order, but it would still have to sort the whole result.

Answer 2

GROUP BY location_id.

• If the chosen index starts with location_id, processing can hop through the index,

• Otherwise, there will need to be a temp table and a sort.

The Optimizer does not have enough info to know for sure which execution plan would really be faster, but the above bullet items are the best it has to work with.

If you want to discuss this further, please provide SHOW CREATE TABLE and the EXPLAIN ANALYZEs.