How to Stop Playing “Hop and Seek”: MySQL Cluster and TokuDB, Part 2

In my last post, I wrote that I observed many similarities between TokuDB and MySQL Cluster. Many features that benefit TokuDB also benefit MySQL Cluster, and vice versa, with Hot Column Addition and Deletion (HCAD) being an example. Over my next few posts, I expand on some more of these possibly unexpected similarities.

Today I want to focus on optimizer support for clustering keys. Both MySQL Cluster and TokuDB can benefit from the MySQL optimizer supporting clustering keys. For TokuDB, the benefit is obvious, as TokuDB supports clustering keys. A non-negligible part of our effort is changing the optimizer.

MySQL Cluster can benefit as well. In fact, a member of the MySQL Cluster team filed a feature request ( for this two years ago. Here is the benefit as I understand it. In MySQL Cluster, a clustered index has very similar performance characteristics to a non-clustered index. In both cases, the number of network hops to answer the query is the same, so having MySQL cluster treat every index as clustering may yield better query plans.

This leads to two points, one narrow, and one broad:

  • implementing clustering keys in the optimizer is beneficial (any engine is then able to implement clustering keys if they want to)
  • letting the storage engine (be it TokuDB, NDB, or anyone else) define the access costs of an index is better than the MySQL optimizer doing so assuming it understands the cost.

As best as I can tell, MariaDB 5.5 has solved this problem, partly thanks to some of our suggestions, but mostly thanks to improvements to the storage engine API and its usage in the optimizer. In some places, MariaDB has taken some of our patches to make parts of the optimizer aware of clustering keys. In many other places, they have replaced hard coded cost estimates with one of these handler APIs:

  • handler::scan_time
  • handler::read_time
  • handler::keyread_time

The only new API is handler::keyread_time, that asks the storage engine for the access cost of reading N rows from a secondary index without accessing the primary key.

With these APIs, much of the guesswork in determining costs of certain access patterns are taken out of the optimizers hands and put into the storage engines, which mostly solved our problem of how do we tell the optimizer to treat clustering keys appropriately. We think it would be beneficial of MySQL to consider this approach as well for MySQL v5.6.

Share this post

Comments (2)

  • Justin Swanhart Reply

    You can emulate multiple ‘clustering keys’ in InnoDB like the following:
    create table t1(
    c1 bigint auto_increment primary key,
    c2 int not null,
    c3 int not null,
    key(c3,c2) , — carry all the columns except the PK columns for a clustering index
    key(c2, c3)

    July 3, 2012 at 5:48 pm
    • Zardosht Reply

      Hi Justin,

      Thanks for the comment.

      That method sometimes works, but can be somewhat cumbersome. With that method, you need to list ALL columns. In addition, if you add columns, you need to also remember to change indexes.

      There are also some cases where it would fail:
      – if the table has more than 16 columns that are not in the primary key, then this method fails, because InnoDB indexed have at most 16 columns per key
      – if the table has blob fields or text fields, then this method fails, because blobs cannot be fully indexed
      – if the user adds a column, the index will need to be redefined and rebuilt.

      I elaborate a bit more on this in

      July 5, 2012 at 1:28 pm

Leave a Reply