<div id="docs-body">
 <div class="section">
  <div class="titlepage">
   <div>
    <div>
     <h4 class="title">
      <a name="bnl-bka-optimization">
      </a>
      10.2.1.12 Block Nested-Loop and Batched Key Access Joins
     </h4>
    </div>
   </div>
  </div>
  <a class="indexterm" name="idm46045229279376">
  </a>
  <a class="indexterm" name="idm46045229277920">
  </a>
  <a class="indexterm" name="idm46045229276432">
  </a>
  <a class="indexterm" name="idm46045229274944">
  </a>
  <p>
   In MySQL, a Batched Key Access (BKA) Join algorithm is
          available that uses both index access to the joined table and
          a join buffer. The BKA algorithm supports inner join, outer
          join, and semijoin operations, including nested outer joins.
          Benefits of BKA include improved join performance due to more
          efficient table scanning. Also, the Block Nested-Loop (BNL)
          Join algorithm previously used only for inner joins is
          extended and can be employed for outer join and semijoin
          operations, including nested outer joins.
  </p>
  <p>
   The following sections discuss the join buffer management that
          underlies the extension of the original BNL algorithm, the
          extended BNL algorithm, and the BKA algorithm. For information
          about semijoin strategies, see
   <a class="ulink" href="/doc/refman/8.0/en/semijoins.html" target="_top">
    Optimizing IN and EXISTS Subquery Predicates with Semijoin Transformations
   </a>
  </p>
  <div class="itemizedlist">
   <ul class="itemizedlist" style="list-style-type: disc; ">
    <li class="listitem">
     <p>
      <a class="xref" href="bnl-bka-optimization.html#join-buffer-management" title="Join Buffer Management for Block Nested-Loop and Batched Key Access Algorithms">
       Join Buffer Management for Block Nested-Loop and Batched Key Access
Algorithms
      </a>
     </p>
    </li>
    <li class="listitem">
     <p>
      <a class="xref" href="bnl-bka-optimization.html#bnl-optimization" title="Block Nested-Loop Algorithm for Outer Joins and Semijoins">
       Block Nested-Loop Algorithm for Outer Joins and Semijoins
      </a>
     </p>
    </li>
    <li class="listitem">
     <p>
      <a class="xref" href="bnl-bka-optimization.html#bka-optimization" title="Batched Key Access Joins">
       Batched Key Access Joins
      </a>
     </p>
    </li>
    <li class="listitem">
     <p>
      <a class="xref" href="bnl-bka-optimization.html#bnl-bka-optimizer-hints" title="Optimizer Hints for Block Nested-Loop and Batched Key Access Algorithms">
       Optimizer Hints for Block Nested-Loop and Batched Key Access Algorithms
      </a>
     </p>
    </li>
   </ul>
  </div>
  <div class="simplesect">
   <div class="titlepage">
    <div>
     <div class="simple">
      <h5 class="title">
       <a name="join-buffer-management">
       </a>
       Join Buffer Management for Block Nested-Loop and Batched Key Access
Algorithms
      </h5>
     </div>
    </div>
   </div>
   <p>
    MySQL can employ join buffers to execute not only inner
            joins without index access to the inner table, but also
            outer joins and semijoins that appear after subquery
            flattening. Moreover, a join buffer can be effectively used
            when there is an index access to the inner table.
   </p>
   <p>
    The join buffer management code slightly more efficiently
            utilizes join buffer space when storing the values of the
            interesting row columns: No additional bytes are allocated
            in buffers for a row column if its value is
    <code class="literal">
     NULL
    </code>
    , and the minimum number of bytes is
            allocated for any value of the
    <a class="link" href="char.html" title="13.3.2 The CHAR and VARCHAR Types">
     <code class="literal">
      VARCHAR
     </code>
    </a>
    type.
   </p>
   <p>
    The code supports two types of buffers, regular and
            incremental. Suppose that join buffer
    <code class="literal">
     B1
    </code>
    is employed to join tables
    <code class="literal">
     t1
    </code>
    and
    <code class="literal">
     t2
    </code>
    and the result of this operation is
            joined with table
    <code class="literal">
     t3
    </code>
    using join buffer
    <code class="literal">
     B2
    </code>
    :
   </p>
   <div class="itemizedlist">
    <ul class="itemizedlist" style="list-style-type: disc; ">
     <li class="listitem">
      <p>
       A regular join buffer contains columns from each join
                operand. If
       <code class="literal">
        B2
       </code>
       is a regular join
                buffer, each row
       <em class="replaceable">
        <code>
         r
        </code>
       </em>
       put into
       <code class="literal">
        B2
       </code>
       is composed of the columns of a
                row
       <em class="replaceable">
        <code>
         r1
        </code>
       </em>
       from
       <code class="literal">
        B1
       </code>
       and the interesting columns of a
                matching row
       <em class="replaceable">
        <code>
         r2
        </code>
       </em>
       from table
       <code class="literal">
        t3
       </code>
       .
      </p>
     </li>
     <li class="listitem">
      <p>
       An incremental join buffer contains only columns from
                rows of the table produced by the second join operand.
                That is, it is incremental to a row from the first
                operand buffer. If
       <code class="literal">
        B2
       </code>
       is an
                incremental join buffer, it contains the interesting
                columns of the row
       <em class="replaceable">
        <code>
         r2
        </code>
       </em>
       together with a link to the row
       <em class="replaceable">
        <code>
         r1
        </code>
       </em>
       from
       <code class="literal">
        B1
       </code>
       .
      </p>
     </li>
    </ul>
   </div>
   <p>
    Incremental join buffers are always incremental relative to
            a join buffer from an earlier join operation, so the buffer
            from the first join operation is always a regular buffer. In
            the example just given, the buffer
    <code class="literal">
     B1
    </code>
    used to join tables
    <code class="literal">
     t1
    </code>
    and
    <code class="literal">
     t2
    </code>
    must be a regular buffer.
   </p>
   <p>
    Each row of the incremental buffer used for a join operation
            contains only the interesting columns of a row from the
            table to be joined. These columns are augmented with a
            reference to the interesting columns of the matched row from
            the table produced by the first join operand. Several rows
            in the incremental buffer can refer to the same row
    <em class="replaceable">
     <code>
      r
     </code>
    </em>
    whose columns are stored in the
            previous join buffers insofar as all these rows match row
    <em class="replaceable">
     <code>
      r
     </code>
    </em>
    .
   </p>
   <p>
    Incremental buffers enable less frequent copying of columns
            from buffers used for previous join operations. This
            provides a savings in buffer space because in the general
            case a row produced by the first join operand can be matched
            by several rows produced by the second join operand. It is
            unnecessary to make several copies of a row from the first
            operand. Incremental buffers also provide a savings in
            processing time due to the reduction in copying time.
   </p>
   <p>
    The
    <a class="link" href="switchable-optimizations.html#optflag_block-nested-loop">
     <code class="literal">
      block_nested_loop
     </code>
    </a>
    flag
            of the
    <a class="link" href="server-system-variables.html#sysvar_optimizer_switch">
     <code class="literal">
      optimizer_switch
     </code>
    </a>
    system variable controls hash joins.
   </p>
   <p>
    The
    <a class="link" href="switchable-optimizations.html#optflag_batched-key-access">
     <code class="literal">
      batched_key_access
     </code>
    </a>
    flag controls how the optimizer uses the Batched Key Access
            join algorithms.
   </p>
   <p>
    By default,
    <a class="link" href="switchable-optimizations.html#optflag_block-nested-loop">
     <code class="literal">
      block_nested_loop
     </code>
    </a>
    is
    <code class="literal">
     on
    </code>
    and
    <a class="link" href="switchable-optimizations.html#optflag_batched-key-access">
     <code class="literal">
      batched_key_access
     </code>
    </a>
    is
    <code class="literal">
     off
    </code>
    . See
    <a class="xref" href="switchable-optimizations.html" title="10.9.2 Switchable Optimizations">
     Section 10.9.2, “Switchable Optimizations”
    </a>
    . Optimizer hints
            may also be applied; see
    <a class="xref" href="bnl-bka-optimization.html#bnl-bka-optimizer-hints" title="Optimizer Hints for Block Nested-Loop and Batched Key Access Algorithms">
     Optimizer Hints for Block Nested-Loop and Batched Key Access Algorithms
    </a>
    .
   </p>
   <p>
    For information about semijoin strategies, see
    <a class="ulink" href="/doc/refman/8.0/en/semijoins.html" target="_top">
     Optimizing IN and EXISTS Subquery Predicates with Semijoin Transformations
    </a>
   </p>
  </div>
  <div class="simplesect">
   <div class="titlepage">
    <div>
     <div class="simple">
      <h5 class="title">
       <a name="bnl-optimization">
       </a>
       Block Nested-Loop Algorithm for Outer Joins and Semijoins
      </h5>
     </div>
    </div>
   </div>
   <a class="indexterm" name="idm46045229230288">
   </a>
   <a class="indexterm" name="idm46045229228832">
   </a>
   <p>
    The original implementation of the MySQL BNL algorithm was
            extended to support outer join and semijoin operations (and
            was later superseded by the hash join algorithm; see
    <a class="xref" href="hash-joins.html" title="10.2.1.4 Hash Join Optimization">
     Section 10.2.1.4, “Hash Join Optimization”
    </a>
    ).
   </p>
   <p>
    When these operations are executed with a join buffer, each
            row put into the buffer is supplied with a match flag.
   </p>
   <p>
    If an outer join operation is executed using a join buffer,
            each row of the table produced by the second operand is
            checked for a match against each row in the join buffer.
            When a match is found, a new extended row is formed (the
            original row plus columns from the second operand) and sent
            for further extensions by the remaining join operations. In
            addition, the match flag of the matched row in the buffer is
            enabled. After all rows of the table to be joined have been
            examined, the join buffer is scanned. Each row from the
            buffer that does not have its match flag enabled is extended
            by
    <code class="literal">
     NULL
    </code>
    complements
            (
    <code class="literal">
     NULL
    </code>
    values for each column in the
            second operand) and sent for further extensions by the
            remaining join operations.
   </p>
   <p>
    The
    <a class="link" href="switchable-optimizations.html#optflag_block-nested-loop">
     <code class="literal">
      block_nested_loop
     </code>
    </a>
    flag
            of the
    <a class="link" href="server-system-variables.html#sysvar_optimizer_switch">
     <code class="literal">
      optimizer_switch
     </code>
    </a>
    system variable controls hash joins.
   </p>
   <p>
    See
    <a class="xref" href="switchable-optimizations.html" title="10.9.2 Switchable Optimizations">
     Section 10.9.2, “Switchable Optimizations”
    </a>
    , for more
            information. Optimizer hints may also be applied; see
    <a class="xref" href="bnl-bka-optimization.html#bnl-bka-optimizer-hints" title="Optimizer Hints for Block Nested-Loop and Batched Key Access Algorithms">
     Optimizer Hints for Block Nested-Loop and Batched Key Access Algorithms
    </a>
    .
   </p>
   <p>
    In
    <a class="link" href="explain.html" title="15.8.2 EXPLAIN Statement">
     <code class="literal">
      EXPLAIN
     </code>
    </a>
    output, use of BNL
            for a table is signified when the
    <code class="literal">
     Extra
    </code>
    value contains
    <code class="literal">
     Using join buffer (Block Nested
            Loop)
    </code>
    and the
    <code class="literal">
     type
    </code>
    value is
    <a class="link" href="explain-output.html#jointype_all">
     <code class="literal">
      ALL
     </code>
    </a>
    ,
    <a class="link" href="explain-output.html#jointype_index">
     <code class="literal">
      index
     </code>
    </a>
    , or
    <a class="link" href="explain-output.html#jointype_range">
     <code class="literal">
      range
     </code>
    </a>
    .
   </p>
   <p>
    For information about semijoin strategies, see
    <a class="ulink" href="/doc/refman/8.0/en/semijoins.html" target="_top">
     Optimizing IN and EXISTS Subquery Predicates with Semijoin Transformations
    </a>
   </p>
  </div>
  <div class="simplesect">
   <div class="titlepage">
    <div>
     <div class="simple">
      <h5 class="title">
       <a name="bka-optimization">
       </a>
       Batched Key Access Joins
      </h5>
     </div>
    </div>
   </div>
   <a class="indexterm" name="idm46045229208224">
   </a>
   <a class="indexterm" name="idm46045229206768">
   </a>
   <p>
    MySQL implements a method of joining tables called the
            Batched Key Access (BKA) join algorithm. BKA can be applied
            when there is an index access to the table produced by the
            second join operand. Like the BNL join algorithm, the BKA
            join algorithm employs a join buffer to accumulate the
            interesting columns of the rows produced by the first
            operand of the join operation. Then the BKA algorithm builds
            keys to access the table to be joined for all rows in the
            buffer and submits these keys in a batch to the database
            engine for index lookups. The keys are submitted to the
            engine through the Multi-Range Read (MRR) interface (see
    <a class="xref" href="mrr-optimization.html" title="10.2.1.11 Multi-Range Read Optimization">
     Section 10.2.1.11, “Multi-Range Read Optimization”
    </a>
    ). After submission of the
            keys, the MRR engine functions perform lookups in the index
            in an optimal way, fetching the rows of the joined table
            found by these keys, and starts feeding the BKA join
            algorithm with matching rows. Each matching row is coupled
            with a reference to a row in the join buffer.
   </p>
   <p>
    When BKA is used, the value of
    <a class="link" href="server-system-variables.html#sysvar_join_buffer_size">
     <code class="literal">
      join_buffer_size
     </code>
    </a>
    defines
            how large the batch of keys is in each request to the
            storage engine. The larger the buffer, the more sequential
            access is made to the right hand table of a join operation,
            which can significantly improve performance.
   </p>
   <p>
    For BKA to be used, the
    <a class="link" href="switchable-optimizations.html#optflag_batched-key-access">
     <code class="literal">
      batched_key_access
     </code>
    </a>
    flag of
            the
    <a class="link" href="server-system-variables.html#sysvar_optimizer_switch">
     <code class="literal">
      optimizer_switch
     </code>
    </a>
    system
            variable must be set to
    <code class="literal">
     on
    </code>
    . BKA uses MRR,
            so the
    <a class="link" href="switchable-optimizations.html#optflag_mrr">
     <code class="literal">
      mrr
     </code>
    </a>
    flag must also
            be
    <code class="literal">
     on
    </code>
    . Currently, the cost estimation for
            MRR is too pessimistic. Hence, it is also necessary for
    <a class="link" href="switchable-optimizations.html#optflag_mrr-cost-based">
     <code class="literal">
      mrr_cost_based
     </code>
    </a>
    to be
    <code class="literal">
     off
    </code>
    for BKA to be used. The following
            setting enables BKA:
   </p>
   <div class="copytoclipboard-wrapper">
    <pre class="programlisting one-line language-sql"><div class="docs-select-all right" id="sa59527405"><div class="copy-help left">Press ⌘+C to copy</div> <div class="right"><button class="clipboard-btn" title="Copy to Clipboard"><span class="icon-clipboard"></span></button></div></div><code class="language-sql"><span class="token prompt">mysql&gt;</span> <span class="token keyword">SET</span> optimizer_switch<span class="token operator">=</span><span class="token string">'mrr=on,mrr_cost_based=off,batched_key_access=on'</span><span class="token punctuation">;</span></code></pre>
   </div>
   <p>
    There are two scenarios by which MRR functions execute:
   </p>
   <div class="itemizedlist">
    <ul class="itemizedlist" style="list-style-type: disc; ">
     <li class="listitem">
      <p>
       The first scenario is used for conventional disk-based
                storage engines such as
       <a class="link" href="innodb-storage-engine.html" title="Chapter 17 The InnoDB Storage Engine">
        <code class="literal">
         InnoDB
        </code>
       </a>
       and
       <a class="link" href="myisam-storage-engine.html" title="18.2 The MyISAM Storage Engine">
        <code class="literal">
         MyISAM
        </code>
       </a>
       . For these engines,
                usually the keys for all rows from the join buffer are
                submitted to the MRR interface at once. Engine-specific
                MRR functions perform index lookups for the submitted
                keys, get row IDs (or primary keys) from them, and then
                fetch rows for all these selected row IDs one by one by
                request from BKA algorithm. Every row is returned with
                an association reference that enables access to the
                matched row in the join buffer. The rows are fetched by
                the MRR functions in an optimal way: They are fetched in
                the row ID (primary key) order. This improves
                performance because reads are in disk order rather than
                random order.
      </p>
     </li>
     <li class="listitem">
      <p>
       The second scenario is used for remote storage engines
                such as
       <a class="link" href="mysql-cluster.html" title="Chapter 25 MySQL NDB Cluster 8.4">
        <code class="literal">
         NDB
        </code>
       </a>
       . A package of
                keys for a portion of rows from the join buffer,
                together with their associations, is sent by a MySQL
                Server (SQL node) to MySQL Cluster data nodes. In
                return, the SQL node receives a package (or several
                packages) of matching rows coupled with corresponding
                associations. The BKA join algorithm takes these rows
                and builds new joined rows. Then a new set of keys is
                sent to the data nodes and the rows from the returned
                packages are used to build new joined rows. The process
                continues until the last keys from the join buffer are
                sent to the data nodes, and the SQL node has received
                and joined all rows matching these keys. This improves
                performance because fewer key-bearing packages sent by
                the SQL node to the data nodes means fewer round trips
                between it and the data nodes to perform the join
                operation.
      </p>
     </li>
    </ul>
   </div>
   <p>
    With the first scenario, a portion of the join buffer is
            reserved to store row IDs (primary keys) selected by index
            lookups and passed as a parameter to the MRR functions.
   </p>
   <p>
    There is no special buffer to store keys built for rows from
            the join buffer. Instead, a function that builds the key for
            the next row in the buffer is passed as a parameter to the
            MRR functions.
   </p>
   <p>
    In
    <a class="link" href="explain.html" title="15.8.2 EXPLAIN Statement">
     <code class="literal">
      EXPLAIN
     </code>
    </a>
    output, use of BKA
            for a table is signified when the
    <code class="literal">
     Extra
    </code>
    value contains
    <code class="literal">
     Using join buffer (Batched Key
            Access)
    </code>
    and the
    <code class="literal">
     type
    </code>
    value is
    <a class="link" href="explain-output.html#jointype_ref">
     <code class="literal">
      ref
     </code>
    </a>
    or
    <a class="link" href="explain-output.html#jointype_eq_ref">
     <code class="literal">
      eq_ref
     </code>
    </a>
    .
   </p>
  </div>
  <div class="simplesect">
   <div class="titlepage">
    <div>
     <div class="simple">
      <h5 class="title">
       <a name="bnl-bka-optimizer-hints">
       </a>
       Optimizer Hints for Block Nested-Loop and Batched Key Access Algorithms
      </h5>
     </div>
    </div>
   </div>
   <p>
    In addition to using the
    <a class="link" href="server-system-variables.html#sysvar_optimizer_switch">
     <code class="literal">
      optimizer_switch
     </code>
    </a>
    system
            variable to control optimizer use of the BNL and BKA
            algorithms session-wide, MySQL supports optimizer hints to
            influence the optimizer on a per-statement basis. See
    <a class="xref" href="optimizer-hints.html" title="10.9.3 Optimizer Hints">
     Section 10.9.3, “Optimizer Hints”
    </a>
    .
   </p>
   <p>
    To use a BNL or BKA hint to enable join buffering for any
            inner table of an outer join, join buffering must be enabled
            for all inner tables of the outer join.
   </p>
  </div>
 </div>
 <br/>
</div>
