Index only

A problem with SQL is SQL. It is easy to write queries that require random IO in the worst case. It is usually easy to find queries that do too much random IO on a NoSQL system as you must code the extra data fetches manually.

Digg has begun to write about their reasons for migrating from MySQL to Cassandra. They provide an excellent summary and then describe a performance problem fixed by the migration. I think Cassandra and a few other members of the NoSQL family are amazing technology but I don't think a migration was needed to fix this performance problem. A better index on the Diggs table would have done that. Others have said the same thing. Maybe I don't have all of the details. I can only go on what was written in the blog.

You can learn more about the power of indexes at the MySQL conference.

The Diggs table was the source of the problem:

CREATE TABLE Diggs (
  id      INT(11),
  itemid  INT(11),
  userid  INT(11),
  digdate DATETIME,
  PRIMARY KEY (id),
  KEY user  (userid),
  KEY item  (itemid)
) ENGINE=InnoDB;

It supported an important query that was too slow. A simple form of this query is:

SELECT digdate, id
FROM Diggs
WHERE userid in (10, 20, 30) AND itemid = 50
ORDER BY digdate DESC, id DESC LIMIT 4;

This query requires too much random IO because it isn't index only. The query can use either the index on itemid or the index on userid. In both cases it will scan more entries than it needs to from the secondary index and then lookup the remaining columns from the primary index. Each lookup on the primary index can do one disk seek. On my test server the plan for this query is:

id    select_type    table    type    possible_keys    key    key_len    ref    rows    Extra
1    SIMPLE    Diggs    ref    user,item    item    5    const    8960    Using where; Using filesort

After running the query I ran SHOW SESSION STATUS LIKE "Handler_read%" and the result from that is below. The query scanned 5000 entries from the secondary index and would have done more than 5000 disk seeks in the worst case to lookup columns from the primary key index.

Variable_name    Value
Handler_read_first    0
Handler_read_key    3
Handler_read_next    5000
Handler_read_prev    0
Handler_read_rnd    0
Handler_read_rnd_next    0

The query is much faster for a table with different indexes

CREATE TABLE DiggsFast (
  id      INT(11),
  itemid  INT(11),
  userid  INT(11),
  digdate DATETIME,
  PRIMARY KEY (itemid,userid,digdate,id),
  UNIQUE KEY (id)
) ENGINE=InnoDB;

The query has a better plan:

id    select_type    table    type    possible_keys    key    key_len    ref    rows    Extra
1    SIMPLE    DiggsFast    range    PRIMARY    PRIMARY    8    NULL    149    Using where; Using index; Using filesort

 It also is much better in reality. The output from SHOW SESSION STATUS LIKE "Handler_read%" is listed below. With a better index the query scans 150 entries from 5 range scans of the index. It should do about 5 disk seeks in the worst case. It is also index only so it doesn't have to lookup other columns after the index scan. Although that doesn't matter much in this case because the query uses the primary key index which has all columns for an InnoDB table. This query will be much faster than the previous one (5 disk seeks versus 5000).

Note that this query uses the first two columns in the primary index for the predicates on itemid and userid. InnoDB stores all columns in the primary key index entries so any query that uses the PK index is index only.

Variable_name    Value
Handler_read_first    0
Handler_read_key    5
Handler_read_next    150
Handler_read_prev    0
Handler_read_rnd    0
Handler_read_rnd_next    0

 UPDATE

I created another variant of the Diggs table that uses a secondary index for the query. InnoDB includes all columns from a PK index in the secondary index to serve as the pointer to the row. Note there is a difference between being 'in the index' and being indexed.

CREATE TABLE DiggsFast2 (
  id      INT(11),
  itemid  INT(11),
  userid  INT(11),
  digdate DATETIME,
  KEY itemuserdig (itemid,userid,digdate),
  PRIMARY KEY (id)
) ENGINE=InnoDB;

From the query plan:

id    select_type    table    type    possible_keys    key    key_len    ref    rows    Extra
1    SIMPLE    DiggsFast2    range    itemuserdig    itemuserdig    10    NULL    150    Using where; Using index; Using filesort
digdate    id

And SHOW SESSION LIKE "Handler_read%"

Variable_name    Value
Handler_read_first    0
Handler_read_key    5
Handler_read_next    150
Handler_read_prev    0
Handler_read_rnd    0
Handler_read_rnd_next    0