Composite Primary Key and Secondary Covering Index: Does the Secondary Index Ever Need to Include a Primary-Key Column?

Question

MySQL. InnoDB.

Say there's a composite primary key 'a, b'. There is another column 'c.' I have a query hitting 'a, c.' Consider two claims. (A) "A secondary index on 'c' gets me a covering index." (B) "A secondary index on 'a, c' is required to cover."

Which is true?

For background, InnoDB adds the primary key to every secondary index.

Answer 1

Covering; yes, "A". Useful; it depends. The effective secondary index will be (c,a,b), in that order.

That is "covering" for a SELECT that contains only a,b,c in any combination and any arrangement.

But that index may not otherwise useful.

WHERE c=32   -- the secondary index will probably be used, even if not covering
WHERE a=12   -- will prefer the PK
WHERE b=22   -- can't use that index for filtering, but may be able to "cover".
WHERE a > 55 AND c > 55  -- may use `c` part of secondary, or `a` part of PK
WHERE DATA(c) = CURDATE()  -- will scan whole index (cf "sargable")

etc, etc

InnoDB includes the PK columns' values (a,b in your case) in each secondary key's BTree so that it can locate the entire row in the data's BTree.

(The above info os correct for InnoDB, but not for MyISAM.)

Leftmost vs Covering

The leftmost rule says that, when evaluating WHERE or GROUP BY or ORDER BY, only the leftmost columns will be used. Once a column (in the index) is encountered that is not useful, the ordering and lookup capabilities of the index are mostly ignore.

WHERE b = 888 AND c = 999

will use only the c part of INDEX(c,a,b). This is because all the rows with c=999 are nicely next to each other in the index. But the b=888 rows are sprinkled among them.

Covering focuses on a different technique.

The data is stored in a BTree (see Wikipedia) ordered by the PRIMARY KEY. Each 'secondary' index is stored in a different BTree, but ordered according to the column(s) of the secondary index plus the PK column(s). That is, think of your INDEX(c) as being a BTree ordered by c,a,b. The purpose of a,b so so that any other columns you might need can be fetched by using a,b to lookup the full rows in the data BTree.

If only those 3 columns are needed by the query, the index is called "covering". This avoids the extra step of reaching into the other data BTree for other columns. That extra step is the expense that is saved by "covering".

Note that "leftmost" cares about the order of the columns; "covering" does not care". Either or both might come into play in any particular query.

(I just made up that term.) Suppose you have:

SELECT d FROM tbl WHERE c = 123

For efficient lookup, you need INDEX(c). For that matter, any index starting with c will make that WHERE efficient.

To make a "covering" index, notice that only d and c exist in the query. So, INDEX(d,c) or INDEX(c,d) or even INDEX(x,y,d,c) would be covering.

Putting the two together:

INDEX(c, d)  -- is optimal

or

INDEX(c, d, ...) -- You may have other queries that would benefit from this.

Another example:

SELECT *        -- may as well forget about "covering"
    FROM tbl
    WHERE user_id = 888
    ORDER BY post_date DESC
    LIMIT 10

This query is beautiful because it gives an example of where even the LIMIT can be handled by the index:

INDEX(user_id,     -- is a simple "=" and completely handles the WHERE
      post_date)   -- the index can be used for ordering
                   -- it can stop after 10 items  :)