Two-column index (pretty unequal columns) and database optimisation

Question

I'm thinking about creating an index on a table like this:

primary | type | id
      1   a      10001
      2   a      10002
      3   b      10001
      n   b      1....

type will contain four values, ~ 95 % will be "a" (or 1, please don't care about the exact value/normalization). Also, 95 % of all queries will be looking for "a", too, in combination with a list of ids (~ one to five or so), like:

SELECT id FROM table WHERE type = 'a' AND id IN (...)

Basic task is to check a list of given id's for existence, so a "covering index" is the thing I basically want.

Now, as far as I understood, it's better to have the column first which reduces the result set most, which would be id. But on the other hand, an intelligent database engine could detect that most of the queries are about "a" and could keep only this branch of the index tree in memory, or, enough memory provided, all three indices as a "different" index each, as it would be better not to bother with all the "b" values.

Is a MySQL/MariaDB (just InnoDB backend) doing this kind of optimizations? Or any other thoughts? I'm not so interested in this table, more a general view on this case.

Thx in advance for all your comments ;)

Answer 1

There are many details missing. InnoDB? Is SELECT id FROM table WHERE type = 'a' AND id IN (...) exactly the query in question? (It is rare to get only id, especially when you specify it in the WHERE.) id is not the PK? That is confusing. Please change the question.

Regardless of cardinality, it is often better, and rarely worse, to use

INDEX(type, id)

for this and similar queries.

For one thing, this particular SELECT can be performed entirely in the BTree index. Thus it is a "covering" index. The EXPLAIN SELECT... will indicate such by saying "Using index".

For further discussion, please provide SHOW CREATE TABLE and EXPLAIN SELECT ... with the actual query.

(Yes, I disagree with Károly Nagy.)

More

A "covering" index is an index that contains all the columns mentioned anywhere in the SELECT.

The best order for the columns is

1. First lay out the columns that are optimal for locating the rows.
2. Then add any extra columns (to "cover"), in any order.

I discuss step 1 in my Index cookbook . Note that it says to put the '=' columns first.

So...

• type comes first because of '=';
• id comes next because it is needed to find the desired rows;
• Finally, there are no extra columns needed to "cover".

I will admit that there is a trade-off concerning "95% of the rows have type='a'". Let me dig into details of two approaches:

Approach 1: Secondary key INDEX(id, type):

This will reach into the BTree index several times (one per id), then scan forward skipping over any (very few) rows that are not type='a'. (In the documentation, see "MRR" for a discussion of this leapfrogging.)

Approach 2: Secondary key INDEX(type, id):

This will reach into the BTree index several times (one per combination ('a', id), then scan forward. But it does not need to skip over any. This Approach is not significantly faster when using 'a', but is significantly faster for type='b'.

Approach 3: Secondary key INDEX(id):

This is definitely slower than the others. It must locate each id in the index, then reach over into the data to check type. This bouncing back and forth between the index and the data will make it roughly twice as slow. The optimizer notices this and may decide it would be faster to simply ignore the index and scan the entire table.

Answer 2

You're right. The more selective column should come first unless it happens to be in a range condition.

Having type in the index will provide absolutely no benefits on the performance when you query for type='a'. It will however put some extra overhead on your indexes which may result in actual degradation of performance.

If id is always in the query with this cardinality I wouldn't bother having type in your index at all. Especially if id is unique.