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

Igor Babaev (MySQL)

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.

Igor Babaev

MySQL

Igor joined MySQL in 2002 after several years of work at Raima/Centura on different SQL processors. In 2003 he headed a group of developers focusing on optimizer problems. Igor is the author of pipeline implementation for nested outer joins. He also has implemented a full set of optimizations based on equality predicates.

Sponsors
  • Kickfire
  • Zmanda, Inc.
  • Continuent
  • EDS
  • JasperSoft
  • Sun Microsystems
  • Symantec Anti-Virus Software
  • XAware
  • Data Direct Technologies
  • Dolphin Interconnect Solutions
  • Hewlett Packard
  • Infobright, Inc
  • Linagora
  • Microsoft
  • OpSource
  • Oracle
  • Pentaho
  • R1Soft
  • Red Hat
  • Ticketmaster
  • TechRepublic

Contact Us

View a complete list of MySQL contacts.