Batched Key Access
Contents |
[edit] Introduction
The Batched Key Access (BKA) Join is a new implementation schema of multi-way join operations employed by the MySQL Server. Like the schema of Nested Loop Join (NLJ) it does not use external disk memory no matter how big the joined tables are. At the same time BKA Join can efficiently utilize main memory to speed up the execution time of multi-way joins for conventional disk-based databases by an order of magnitude. Using BKA Join for such engines as MySQL NDB Cluster is beneficial as well because here the algorithm allows to minimize the number of round-trips between the Server and cluster nodes.
The idea of BKA Join is rather simple: following the main path of Nested Loops Join not to look for possible matches for a partial record as soon as this record has been constructed but rather first accumulate several such records in a memory buffer and then optimize the search for matching extensions for the entire set.
Possible gains here are the following:
- If some partial records in the set have the same key we can perform only one look-up for them.
- We can perform index look-ups in the key order which should be more beneficial than random index look-ups.
- If we sort rowids / primary keys for the matching records that we find in index entries then instead of random fetches of matching extensions we'll perform a so-called file sweep access that should be much cheaper (especially for the modern HD devices).
Theoretically at least the impact of the third optimization must be the most significant that surely overweights the gain of two first optimizations.
When working with an NDB Cluster by the BKA Join algorithm the MySQL Server sends packages with many keys for lookups to the Cluster. The Cluster finds the records for all these keys and sends them back to the Server. As each key 'remembers' from what record in the join buffer it has been built the received records easily can be joined with the matching records in the buffer. As a result the number of packages sent to the Cluster and backward is reduced significantly.
[edit] References
The algorithmic background for BKA Join can be found in the WorkLog task WL#2771.
Slides for the presentation on Batched Key Access at MySQL User Conference 2008 are available here BatchedKeyAccess-UC2008.pdf.
[edit] Download
[edit] Binary packages
BKA is part of MySQL as of MySQL 6.0.9.
Older binary packages for Solaris, Linux and Windows are available at the BKA preview download page.
[edit] Sources
Batched Key Access is now part of MySQL 6.0. You can obtain the source code from here:
https://code.launchpad.net/~mysql/mysql-server/mysql-6.0 . That is, install bazaar and issue bzr branch lp:mysql-server/6.0 command.