MySQL Binary Tree Index order

I have a query like this:

SELECT * FROM mytable WHERE
((num=8198747 AND class='A') OR
 (num=1646463 AND class='B') OR
 (num=4099442 AND class='C') OR
 (num=1176312 AND class='A') OR
 (num=2146847 AND class='B') OR
 (num=7000296 AND class='F') OR
 --...about 400 more clauses like this
)

SHOW INDEXES FROM mytable;开发者_如何学编程
+---------+------------+----------+--------------+---------------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name   |
+---------+------------+----------+--------------+---------------+
| mytable |          0 | PRIMARY  |            1 | id            |
| mytable |          1 | nc_idx   |            1 | num           |
| mytable |          1 | nc_idx   |            2 | class         |
+---------+------------+----------+--------------+---------------+
3 rows in set (0.00 sec)

My understanding is that for each of the ~400 clauses in the query, it will do a separate BTREE lookup on num=XXXXXXXX. Is there any value in changing the query to:

SELECT * FROM mytable WHERE
((class='A' AND num IN (8198747, 1176312, ...)) OR
 (class='B' AND num IN (1247910, 1248192, ...)) OR
 (class='F' AND num IN (7244626, 9084903, ...)) OR
 --...for each class in the query
)

after adding a new index cn_idx on class and num, in that order? I think it won't be much faster, since class is just one char, and thus the number of BTREE lookups will be the same. But, each subtree will be shorter. Thoughts?

In short

• just stick to OR
• the index on num is the only index that will help this query
• an composite index on (num,class) has negligible effect, since num is already very selective

Two other ways to write it, using UNION ALL

SELECT * FROM mytable
WHERE (num=8198747 AND class='A')
UNION ALL
SELECT * FROM mytable
WHERE (num=1646463 AND class='B')
UNION ALL
SELECT * FROM mytable
WHERE (num=4099442 AND class='C')
UNION ALL
... etc ...

This may work well if you don't have too many num/class pairs, as each one will individually perform an index seek. (A composite index on num/class will work better than num and class indexes single-field indexes. class/num is less selective)

The second way uses JOIN mechanics, by making a virtual table out of the num/class pairs:

SELECT t.*
FROM mytable t
JOIN (
    select 8198747 as num, 'A' as class union all
    select 1646463, 'B' union all
    select 4099442, 'C' union all
    ... etc ...
    ) v on v.num=t.num and v.class=t.class

Performance comparison

Create a table

create table mytable (
id int auto_increment primary key,
num int, 
class char(1), 
other varchar(10), 
date timestamp default current_timestamp) ENGINE InnoDB;

Fill it up with 1 million records
(Note: data properties - selectivity: num ~ 1, class ~ 1/26)

insert into mytable(num, class, other)
select rand()*100000000, char(rand()*26+65), concat('',rand()*10000000)
from
(select 1 a union all select 2 union all select 3 union all select 4
union all select 5 union all select 6 union all select 7
union all select 8 union all select 9 union all select 0) a,
(select 1 a union all select 2 union all select 3 union all select 4
union all select 5 union all select 6 union all select 7
union all select 8 union all select 9 union all select 0) b,
(select 1 a union all select 2 union all select 3 union all select 4
union all select 5 union all select 6 union all select 7
union all select 8 union all select 9 union all select 0) c,
(select 1 a union all select 2 union all select 3 union all select 4
union all select 5 union all select 6 union all select 7
union all select 8 union all select 9 union all select 0) d,
(select 1 a union all select 2 union all select 3 union all select 4
union all select 5 union all select 6 union all select 7
union all select 8 union all select 9 union all select 0) e,
(select 1 a union all select 2 union all select 3 union all select 4
union all select 5 union all select 6 union all select 7
union all select 8 union all select 9 union all select 0) f

Create the indexes

create index nc_num on mytable(num);
create index nc_class on mytable(class);

Select using OR

select * from mytable
WHERE
(num=38142659 and class='T') OR
(num=42476845 and class='E') OR
(num=45205882 and class='B') OR
(num=84861596 and class='K') OR
..... 100 in total

Output of Show profiles: (run set profiling=1; once. then run the queries. run show profiles to see the last timings)

Duration: 0.00003025

Explain extended (add explain extended before the query)

"id";"select_type";"table";"type";"possible_keys";"key";"key_len";"ref";"rows";"Extra"
"1";"SIMPLE";"mytable";"range";"nc_num,nc_class";"nc_num";"5";NULL;"125";"Using where"

Select using UNION ALL between num/class

SELECT * FROM mytable WHERE (num=38142659 AND class='T') UNION ALL
SELECT * FROM mytable WHERE (num=42476845 AND class='E') UNION ALL
SELECT * FROM mytable WHERE (num=45205882 AND class='B') UNION ALL
SELECT * FROM mytable WHERE (num=84861596 AND class='K') UNION ALL
.... 100 in total

Show Profile

Duration: 0.00069525

Explain extended

"id";"select_type";"table";"type";"possible_keys";"key";"key_len";"ref";"rows";"Extra"
"1";"PRIMARY";"mytable";"ref";"nc_num,nc_class";"nc_num";"5";"const";"1";"Using where"
"2";"UNION";"mytable";"ref";"nc_num,nc_class";"nc_num";"5";"const";"1";"Using where"
"3";"UNION";"mytable";"ref";"nc_num,nc_class";"nc_num";"5";"const";"1";"Using where"
"4";"UNION";"mytable";"ref";"nc_num,nc_class";"nc_num";"5";"const";"1";"Using where"
... etc

Select using Union All to build up a virtual table

SELECT t.*
FROM mytable t
JOIN (
select 41805446 num, 'X' collate utf8_general_ci class union all
select 84867135, 'P' union all
select 52747446, 'R' union all
.... etc...
) v on v.num=t.num and v.class=t.class

Show profile

Duration: 0.00026100

Explain extended

"id";"select_type";"table";"type";"possible_keys";"key";"key_len";"ref";"rows";"Extra"
"1";"PRIMARY";"<derived2>";"ALL";NULL;NULL;NULL;NULL;"100";""
"1";"PRIMARY";"t";"ref";"nc_num";"nc_num";"5";"v.num";"1";"Using where"
"2";"DERIVED";NULL;NULL;NULL;NULL;NULL;NULL;NULL;"No tables used"
"3";"UNION";NULL;NULL;NULL;NULL;NULL;NULL;NULL;"No tables used"
"4";"UNION";NULL;NULL;NULL;NULL;NULL;NULL;NULL;"No tables used"
....
"101";"UNION";NULL;NULL;NULL;NULL;NULL;NULL;NULL;"No tables used"
NULL;"UNION RESULT";"<union2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,...>";"ALL";NULL;NULL;NULL;NULL;NULL;""

Select using IN

SELECT * FROM mytable WHERE
(class='A' and num in (28538065
)) or (class='B' and num in (70851926
,90457823
,94804149
)) or (class='C' and num in (74179050
,43280101
,24562525
,56859448
,38226813
,33532373
,93501613
,28634136
,8204338
,15636810
)) or (class='D' and num in (26672499
.... etc

Show profile

Duration: 0.00003125

Explain extended

"id";"select_type";"table";"type";"possible_keys";"key";"key_len";"ref";"rows";"Extra"
"1";"SIMPLE";"mytable";"range";"nc_num,nc_class";"nc_num";"5";NULL;"136";"Using where"