Batched Key Access: a Significant Speed-up for Join Queries

The talk introduces a new advanced technique to execute queries with equi-joins. The technique called Batched Key Access (BKA) effectively employs efficient implementations of the Multi-Range Read (MRR) interface for different storage engines – MyISAM, InnoDB, NDB Cluster – that appeared in MySQL 6.0. BKA can be applied when a join operation is executed with index lookups. The main idea behind BKA is to accumulate several keys in a buffer and only then access the joined table possibly changing the order of lookups to optimize the sequence of disk seeks. While MRR handler functions are responsible only for an optimal access to the data of the table to be joined the BKA code has to do all the remaining job: to generate a sequence of keys for index lookups and to put together the matched rows after each lookup. BKA can also eliminate duplicate keys in some cases reducing the total number of lookups. The first experiments with BKA showed that it could improve the performance of join queries up to 2-5 times depending on the size of the used join buffer. It also improved the execution of joins on NDB cluster as it reduced significantly the number of round trips between MySQL Server and Cluster storage nodes. The technique will be supported in full measure starting from version 6.1.