primary indexes Vs secondary indexes: performance differences

Question

I've got a little question: what is the difference in performance between the primary and secondary indexes? what causes this difference?

I'm googling around, and I've seen that secondary indexes are stored in another table, so this slows down all operations.. but there are some other reasons that justify this decrease in performance?

Thanks a lot

Answer 1

A clustered table is a B-Tree without "heap" portion - rows are stored directly in the B-Tree structure of the clustering index (primary key). Nodes of the B-Tree can be split or coalesced, so the physical location or rows can change, so we can't have a simple "pointer" from a secondary index to the rows, so the secondary index must include a complete copy of the primary index fields to be able to reliably identify rows.

This is true for Oracle, MS SQL Server and is also true for InnoDB.

Which means secondary indexes in clustered tables are "fatter" than secondary indexes in heap-based tables, which:

• lowers the data clustering,
• lowers the effectiveness of the cache,
• makes them more expensive to maintain,
• and most importantly, has consequences on query performance:
  • Querying through a secondary index may require double lookup - one lookup through the secondary index to locate the "key" data and one through the primary, to locate the row itself (Oracle has some interesting optimizations for avoiding the second lookup, but InnoDB does not, to my knowledge).
  • On the other hand, the secondary index naturally covers more fields, so the second lookup could be avoided altogether where a traditional heap-based index would require a table access. However, the same effect can be achieved in the heap-based index, by simply adding more fields to it.

Let me quote Use The Index, Luke!: "The advantages of index-organized tables and clustered indexes are mostly limited to tables that do not need a second index."

Which is shame, since MySQL doesn't let you choose the clustering independently from the storage engine.