Use of join buffer is now visible in EXPLAIN

UPDATE:
* s/Using join cache/Using join buffer/, changed to show the final variants of EXPLAIN output as described here
* s/join_buff_size/join_buffer_size/



Starting from 5.1.18, EXPLAIN output may show “Using join cache“, like in this example:

mysql> explain select * from t1, t2 where t1.col < 10 and t2.col < 'bar';
+----+-------------+-------+-------+-...-+--------------------------------+
| id | select_type | table | type  |     | Extra                          |
+----+-------------+-------+-------+-...-+--------------------------------+
|  1 | SIMPLE      | t1    | range |     | Using where                    |
|  1 | SIMPLE      | t2    | range |     | Using where; Using join buffer |
+—-+————-+——-+——-+-…-+——————————–+

The join cache is actually not a new feature. It has been available in MySQL at least since version 4.0, and for all this time it has remained invisible and undocumented. The only thing that indicated its presense was the @@join_buffer_size server variable.

We’re trying to gradually make EXPLAIN show more information. Georgi Kodinov was fixing BUG#27531 and has used that occasion to make join buffering show up in EXPLAIN output.

If you already know how MySQL’s join buffering works, that’s all the news. If not, the remainder of this post has a hopefully readable explanation of how join buffering works and when it is used.

How join buffering works

Let’s start with regular Nested Loops Join. Suppose we have a join query

select * from t1, t2, t3 where t2.key1=t1.col1 and t3.key1<40;

and the query plain is like shown in this EXPLAIN output:

...-+-------+-------+---------------+------+---------+--------------+------+-------------+
    | table | type  | possible_keys | key  | key_len | ref          | rows | Extra       |
...-+-------+-------+---------------+------+---------+--------------+------+-------------+
    | tbl1  | ALL   | NULL          | NULL | NULL    | NULL         |   10 |             |
    | tbl2  | ref   | key1          | key1 | 5       | db.tbl1.col1 |    2 | Using where |
    | tbl3  | range | key1          | key1 | 5       | NULL         |   40 | Using where |
...-+-------+-------+---------------+------+---------+--------------+------+-------------+

When no join buffering is used, the query will be executed as follows:

  for each record t1rec in table tbl1
  {
    for each record t2rec in tbl2 such that t2rec.key1=t1rec.col
    {
      for each record t3rec in tbl3 such that t3rec.key1<40
      {
        pass the (t1rec, t2rec, t3rec) row combination to output;
      }
    }
  }

Graphically the execution flow can be depicted as follows (yellow are the table scans, blue are the table rows):

nl-join-no-buffering.png

From the code and picture we see that:

  • Table tbl2 is scanned several times, but each scan accesses a different part of the table
  • Table tbl3 is scanned many times, and all performed scans are identical

It is apparent that the second and the third scans of table tbl3 bring no new information and can be removed. We do not have to re-scan tbl3 for any row combination from tables tbl1, tbl2. Instead, we could accumulate a back of such row combination, and then do one tbl3 scan for all of them. And this is what join buffering is.

In pseudo-code, the execution will look as follows:

  for each record t1rec in table tbl1
  {
    for each record t2rec in tbl2 such that t2rec.key1=t1rec.col
    {
      put (t1rec, t2rec) into the buffer
      if (buffer is full)
        flush_buffer();
    }
  }

  flush_buffer() {
    for each record t3rec in tbl3 such that t3rec.key1<40
    {
      for each record in the buffer
        pass (t1rec, t2rec, t3rec) row combination to output;
    }
    empty the buffer;
  }

And graphically it will look as follows:

nl-join-buffering.png

The EXPLAIN output will be as follows:

explain select * from t1,t2,t3 where t2.key1 = t1.col1 and t3.key1<40;
...-+-------+-------+---------------+------+---------+--------------+------+--------------------------------+
    | table | type  | possible_keys | key  | key_len | ref          | rows | Extra                          |
...-+-------+-------+---------------+------+---------+--------------+------+--------------------------------+
    | t1    | ALL   | NULL          | NULL | NULL    | NULL         |   10 |                                |
    | t2    | ref   | key1          | key1 | 5       | test.t1.col1 |    2 | Using where                    |
    | t3    | range | key1          | key1 | 5       | NULL         |   40 | Using where; Using join buffer |
…-+——-+——-+—————+——+———+————–+——+——————————–+

In this example join buffering is used for one table, but it can be used for several tables as well. MySQL uses join buffering whenever it can, access to some table tbl_x will be bufferred if

  • The SELECT does not have an ORDER BY clause
  • We’re not at top level “select” of a multi-table UPDATE
  • tbl_x is accessed using an “independent” access method: ALL, index, range, or index_merge.
  • tbl_x is not inner w.r.t. some outer join

The server variable @@join_buffer_size specifies how much MySQL should allocate for each buffer. That is, if two tables use buffering, MySQL will allocate two buffers of @@join_buffer_size bytes each.

Posted in EXPLAIN, how-it-works on May 16th, 2007 by spetrunia | |

6 Responses to ' Use of join buffer is now visible in EXPLAIN '

Subscribe to comments with RSS or TrackBack to ' Use of join buffer is now visible in EXPLAIN '.


  1. on June 10th, 2007 at 5:13 am

    […] As soon as I’ve finished writing this post about “Using join cache”, it was apparent that “Using join cache” is poor wording. First, the corresponding server variable is called @@join_buffer_size, not join cache size, and second, there is really no cache involved. […]


  2. on July 29th, 2007 at 10:14 pm

    […] MySQL themselves, and many community members, have sometimes discussed the need for a tree view of EXPLAIN. I sincerely hope they implement that feature and make this little tool obsolete in future versions of MySQL. I also understand MySQL is trying to add more information to EXPLAIN. Currently it’s not possible to get a complete query execution plan from EXPLAIN, because it doesn’t show you everything the server does while executing the query. If MySQL adds information, I’ll update this tool. I have a feature request pending to show when a GROUP BY happens, for example. […]

  3. Robert said,

    on November 22nd, 2008 at 12:01 pm

    Are there any hints for properly sizing the @@join_buffer_size variable relative to the table being buffered?

  4. sergey said,

    on November 27th, 2008 at 2:42 am

    > Are there any hints for properly sizing the @@join_buffer_size variable relative to the table being buffered?

    There are many factors in play:
    - join buffer stores only columns used by the query;
    - join buffer isn’t actually used to buffer tables. As the picture above shows, join buffer stores (tbl1.*, tbl2*) pairs, or more precisely, (used_columns(tbl1), used_columns(tbl2)) pairs that satisfy the part of the WHERE clause that refers to tbl1 and tbl2.

    So it doesn’t directly depend on the table size. If you have very big tables but highly selective conditions in the WHERE clause, you are in the same situation as those with small tables and conditions with poor selectivity.

    To get a rough estimate, I’d calculate how many record combinations the join is going to enumerate (product of “rows” columns in EXPLAIN output), and divide that by the number of tables in the join to account for records being filtered out. This roughly gives the maximum useful size.

    The speedup obtained from using bigger join buffer tends to diminish as buffer size increases, so you only need to set it to a reasonably big value.

  5. ever027 said,

    on June 18th, 2010 at 4:07 am

    you said “tbl_x is not inner w.r.t. some outer join”,
    what is the meaning of “w.r.t.”?

  6. ex-government cars for sale in perth said,

    on February 20th, 2013 at 11:28 pm

    ex-government cars for sale in perth…

    Sergey Petrunia’s blog » Use of join buffer is now visible in EXPLAIN…

Leave a reply

You must be logged in to post a comment.