Hash join in MySQL 8.0
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Grøvlen, Øystein
Hash join was introduced in MySQL 8.0.18 and was presented for the first time at FOSDEM 2020. Since then, the performance of hash join has been improved, and I will present results that show this. We will also discuss what kind of queries benefit from hash join, what you need to do for hash join to be used, and how to tune your system for optimal hash join performance.
 Hi, my name is Eisling Gröven and I'm working on MySQL at Oracle. And today I will talk about hash join in MySQL 8.0. First I will give an overview of what hash join is before I go into details of the hash join implementation in MySQL 8.0. Then I will discuss when it's beneficial to use hash join and what you need to do to take advantage of these benefits. So first an introduction into hash join. So hash join is a method for performing the join of two tables. What I will describe here is often called classic hash join. Here we have an example where we join the two tables Auras and Customers to find information about Auras with a total price above half a million. Hash join has two phases, the build phase and the probe phase. In the build phase we find the rows from the Auras table that qualifies. We call this the build input. We put these rows into a hash table by applying a hash function to the join key. In the probe phase we read from the customer table and apply the same hash function to its join key to find matches in the hash table. Any matches are added to the result. So one big advantage of hash join is that we only need to read each input once. Note that the hash table must fit in memory. So when we normally choose the smallest input as the build input. If the build input does not fit into memory it is possible to split it and do multiple scans over the probe input but as we will see there are more efficient ways. Hybrid hash join is an alternative to handle build input that is too large for the allocated memory. The build phase starts as earlier described by building a hash table from the build input. However, when the hash table is full the rest of the build input is stored in a set of chunk files. A different hash function will be used to determine which chunk file is always added to. In the probe phase in addition to checking for matches in the hash table all rows of the probe input will be added to another set of chunk files using the same hash function as was used when populating the build chunk files. After the probe input has been processed one repeat the process for each pair of chunk files. That is first a hash table is built from build input from chunk file number one, number zero and probe with the content of the probe input chunk file number zero. Then the same is done for files number one and two and so on all the files have been completed. So MySQL has supported hash joins as MySQL 8.0.18. In earlier versions of MySQL the only way to execute joins were so called nested loop joins. In nested loop joins we will for each row of the left input find all rows matching the rows in the right table before continuing with the same process for the next row of the left input. This can be very efficient when one can use an index to find matches. One will not need to read all the rows of the table and there is relatively few matches per row. Nested loop joins is also not that well suited if IO is needed to access the rows of the right table since that will generate a lot of random IO. In MySQL 8.0 both nested loop joins and hash join is supported and both classic in-memory hash join and hybrid hash join has been implemented. How much memory we can use for the hash table is determined by the join buffer size variable. And for hybrid hash join the max number of chunk files is 128. This means that a build chunk file may become larger than what the hash table can support. With that it is the case one will have to load the hash table in multiple steps for each build chunk file and one will have to scan each probe chunk file multiple times. Note that hash join will usually only be selected automatically when no indexes are available for nested loop join. This means that in some cases in order to force hash join to be used we need to load it to disable indexes for example by using the no index hint. Then there are no indexes that can be used for nested loop join, hash join is much faster. Here we show what happens if you do not create an index at all for the queries of the TPCH benchmark. Many of the queries will then be more than 1000 times faster with hash join than the nested loop join. However, hash join can also be faster than indexed nested loop join. For this simple query where we vary the size of the build input we see that if more than 30% of the queries of the rows from the order table is selected hash join will be faster than nested loop join. Note also that the performance of hash join in MySQL has been improved since it was first introduced. As we can see from this diagram a new hash table implementation has improved both memory usage and efficiency of hash join. So when should we use hash join? As already mentioned if indexes are not available MySQL 8.0 will automatically use hash join instead of nested loop join. In this case we have a query where we want to find those that are registered as both supplier and customer and we will do that by comparing phone numbers. And since the phone number columns are not indexed we see that from explain that hash join is used in MySQL 8.0. And the performance difference is enormous. While this query takes over 2.5 hours in MySQL 5.7 it can be done in 1.5 seconds in MySQL 8. Hash join is also very different efficient than queries are Iobond. So these curves I have shown earlier it shows the performance than the database before is big enough to hold all the data. If you have a much smaller database buffer so that IO is needed things are quite different. As you can see hash join takes only a constant factor longer when storage is involved. But for nested loop join things are quite different. The main reason is that the nested loop join you may have to read the same page multiple times from storage since the access pattern is random. While for hash join you save a lot by only doing sequential access. So in this case hash join was faster when more than 1.5% of the orders table is accessed. Query 13 from TPCH benchmark is a case that shows that if we access large part of a table hash join is better. So in this case we will access the entire customer table. There is no conditions on columns in the customer. And we need to make this the building but because it is the left side of a left outer join and when you have left outer join you cannot switch the order of the two tables involved. And we see that if you use hash join we will use 45% less time than with nested loop join. Another benefit of hash join is that the filtering may be done before the join also for the program input. For nested loop join you will access the right hand table before you evaluate any conditions on rows of this table. For hash join you can do this filtering before you check any matches. And one example to illustrate this is query 5 of TPCH. In this case we have two conditions on two tables, region and orders. For the join order chosen by the optimizer we can apply the conditions on region before the join since it is on the left hand of a join, the first join. However since order is a right hand up-went the conditions on order date will be applied after the join for nested loop join. But if you switch to use hash join instead we can evaluate the conditions earlier. And as we see if you do that for this query the execution time is reduced from 14 to 8 seconds. So what can you do to benefit from the improvements enabled by hash join? First in order to check whether hash join is used you should check explain. Traditional explain will show using join buffer hash join on the line of the probe input. And the new three explain you get even more details. Here you can see that the hash join operation has two operands. The top one is the probe input while the bottom one contains the build input. As already mentioned if the hash join is not automatically chosen one can make it be used by disabling the use of indexes for nested loop join. For query 13 that we looked at earlier we see that there is one possible index IO cast key. So we can use an index no index hint to disable this index and now we see that hash join will be used. For the other example from TPCH query 5 we wanted to replace the hash join involved with the orders table so that the filtering on order date could be applied earlier. Since there is in this case are multiple tables involved things become a bit more complex in order to avoid that the optimizer change the join order of the first tables when we disable indexes on orders we will use the join prefix hint to make sure that the join order for the first tables do not change. So from explain we can see that the build and the probe inputs and that the filtering is now applied to the orders table before the join condition is evaluated. As you see from this example the forcing hash join can become a big compass and they are working on solutions to support a cost based selection of hash join in for these cases. The size of the join buffer will impact the performance of hash join. So in this diagram we show the performance for our query for different sizes of the join buffer. If the join buffer is 1 gigabyte we can do in memory hash join for all sizes of the build input. If the join buffer is 256 megabyte we will need to use hybrid hash join when more than 40 percent of the rows are selected. With a 16 megabyte hybrid hash join we see that hybrid hash join is used in all cases. If the join buffer is only 4 megabyte each of the 128 build chunk files will not fit in the join buffer if more than 90 percent of the rows are selected. So in that case there will be an extra overshad since each probe chunk file will have to be read twice. However, I think the main message from this diagram is that the overhead of hybrid hash join is not that very high and so that a big join buffer is not necessary to give good performance of hash join. So how can we check if our join buffer is big enough for in memory hash join to be used? We can check the performance schema table that have information about memory allocation. It has a special event for hash join and if the count alloc and the is equal to high count use for hash join we know that a single hash table was used which means that it was able to do the hash join entirely in memory. Otherwise hybrid hash join has been used. Here you have allocated memory for multiple hash tables. In order to be able to estimate how many chunk files are needed MySQL will try to estimate the size of the build input. Without histograms this estimate will often be less accurate especially when we disable indexes since then it cannot use information from the indexes to do the estimation. So this diagram shows what happens to our query if I remove the histogram on Ocastkey. We see that the performance becomes much less predictable without histograms. So to sum up there are many cases where hash join will improve the performance. If indexes are not available there can be an enormous benefit but hash join is often better choice when queries are eye-abound or when large part of a table will be accessed or when there are selective conditions on multiple of the involved tables. I have shown how you can use no index hint to force hash join to be used and increasing the join buffer size may often improve the performance of hash join. And finally remember to create histograms.
 Hi, my name is Eisling Gröven and I'm working on MySQL at Oracle.  And today I will talk about hash join in MySQL 8.0.  First I will give an overview of what hash join is before I go into details of the hash  join implementation in MySQL 8.0.  Then I will discuss when it's beneficial to use hash join and what you need to do to  take advantage of these benefits.  So first an introduction into hash join.  So hash join is a method for performing the join of two tables.  What I will describe here is often called classic hash join.  Here we have an example where we join the two tables Auras and Customers to find information  about Auras with a total price above half a million.  Hash join has two phases, the build phase and the probe phase.  In the build phase we find the rows from the Auras table that qualifies.  We call this the build input.  We put these rows into a hash table by applying a hash function to the join key.  In the probe phase we read from the customer table and apply the same hash function to  its join key to find matches in the hash table.  Any matches are added to the result.  So one big advantage of hash join is that we only need to read each input once.  Note that the hash table must fit in memory.  So when we normally choose the smallest input as the build input.  If the build input does not fit into memory it is possible to split it and do multiple  scans over the probe input but as we will see there are more efficient ways.  Hybrid hash join is an alternative to handle build input that is too large for the allocated  memory.  The build phase starts as earlier described by building a hash table from the build input.  However, when the hash table is full the rest of the build input is stored in a set of chunk  files.  A different hash function will be used to determine which chunk file is always added  to.  In the probe phase in addition to checking for matches in the hash table all rows of  the probe input will be added to another set of chunk files using the same hash function  as was used when populating the build chunk files.  After the probe input has been processed one repeat the process for each pair of chunk  files.  That is first a hash table is built from build input from chunk file number one, number zero  and probe with the content of the probe input chunk file number zero.  Then the same is done for files number one and two and so on all the files have been  completed.  So MySQL has supported hash joins as MySQL 8.0.18.  In earlier versions of MySQL the only way to execute joins were so called nested loop  joins.  In nested loop joins we will for each row of the left input find all rows matching the  rows in the right table before continuing with the same process for the next row of  the left input.  This can be very efficient when one can use an index to find matches.  One will not need to read all the rows of the table and there is relatively few matches  per row.  Nested loop joins is also not that well suited if IO is needed to access the rows of the  right table since that will generate a lot of random IO.  In MySQL 8.0 both nested loop joins and hash join is supported and both classic in-memory  hash join and hybrid hash join has been implemented.  How much memory we can use for the hash table is determined by the join buffer size variable.  And for hybrid hash join the max number of chunk files is 128.  This means that a build chunk file may become larger than what the hash table can support.  With that it is the case one will have to load the hash table in multiple steps for  each build chunk file and one will have to scan each probe chunk file multiple times.  Note that hash join will usually only be selected automatically when no indexes are  available for nested loop join.  This means that in some cases in order to force hash join to be used we need to load  it to disable indexes for example by using the no index hint.  Then there are no indexes that can be used for nested loop join, hash join is much faster.  Here we show what happens if you do not create an index at all for the queries of the TPCH  benchmark.  Many of the queries will then be more than 1000 times faster with hash join than the nested  loop join.  However, hash join can also be faster than indexed nested loop join.  For this simple query where we vary the size of the build input we see that if more than  30% of the queries of the rows from the order table is selected hash join will be faster  than nested loop join.  Note also that the performance of hash join in MySQL has been improved since it was first  introduced.  As we can see from this diagram a new hash table implementation has improved both memory  usage and efficiency of hash join.  So when should we use hash join?  As already mentioned if indexes are not available MySQL 8.0 will automatically use hash join  instead of nested loop join.  In this case we have a query where we want to find those that are registered as both  supplier and customer and we will do that by comparing phone numbers.  And since the phone number columns are not indexed we see that from explain that hash  join is used in MySQL 8.0.  And the performance difference is enormous.  While this query takes over 2.5 hours in MySQL 5.7 it can be done in 1.5 seconds in MySQL  8.  Hash join is also very different efficient than queries are Iobond.  So these curves I have shown earlier it shows the performance than the database before is  big enough to hold all the data.  If you have a much smaller database buffer so that IO is needed things are quite different.  As you can see hash join takes only a constant factor longer when storage is involved.  But for nested loop join things are quite different.  The main reason is that the nested loop join you may have to read the same page multiple  times from storage since the access pattern is random.  While for hash join you save a lot by only doing sequential access.  So in this case hash join was faster when more than 1.5% of the orders table is accessed.  Query 13 from TPCH benchmark is a case that shows that if we access large part of a table  hash join is better.  So in this case we will access the entire customer table.  There is no conditions on columns in the customer.  And we need to make this the building but because it is the left side of a left outer  join and when you have left outer join you cannot switch the order of the two tables  involved.  And we see that if you use hash join we will use 45% less time than with nested loop join.  Another benefit of hash join is that the filtering may be done before the join also for the program  input.  For nested loop join you will access the right hand table before you evaluate any conditions  on rows of this table.  For hash join you can do this filtering before you check any matches.  And one example to illustrate this is query 5 of TPCH.  In this case we have two conditions on two tables, region and orders.  For the join order chosen by the optimizer we can apply the conditions on region before  the join since it is on the left hand of a join, the first join.  However since order is a right hand up-went the conditions on order date will be applied  after the join for nested loop join.  But if you switch to use hash join instead we can evaluate the conditions earlier.  And as we see if you do that for this query the execution time is reduced from 14 to 8  seconds.  So what can you do to benefit from the improvements enabled by hash join?  First in order to check whether hash join is used you should check explain.  Traditional explain will show using join buffer hash join on the line of the probe input.  And the new three explain you get even more details.  Here you can see that the hash join operation has two operands.  The top one is the probe input while the bottom one contains the build input.  As already mentioned if the hash join is not automatically chosen one can make it be used  by disabling the use of indexes for nested loop join.  For query 13 that we looked at earlier we see that there is one possible index IO cast  key.  So we can use an index no index hint to disable this index and now we see that hash join will  be used.  For the other example from TPCH query 5 we wanted to replace the hash join involved with  the orders table so that the filtering on order date could be applied earlier.  Since there is in this case are multiple tables involved things become a bit more complex  in order to avoid that the optimizer change the join order of the first tables when we  disable indexes on orders we will use the join prefix hint to make sure that the join  order for the first tables do not change.  So from explain we can see that the build and the probe inputs and that the filtering  is now applied to the orders table before the join condition is evaluated.  As you see from this example the forcing hash join can become a big compass and they are  working on solutions to support a cost based selection of hash join in for these cases.  The size of the join buffer will impact the performance of hash join.  So in this diagram we show the performance for our query for different sizes of the join  buffer.  If the join buffer is 1 gigabyte we can do in memory hash join for all sizes of the build  input.  If the join buffer is 256 megabyte we will need to use hybrid hash join when more than  40 percent of the rows are selected.  With a 16 megabyte hybrid hash join we see that hybrid hash join is used in all cases.  If the join buffer is only 4 megabyte each of the 128 build chunk files will not fit  in the join buffer if more than 90 percent of the rows are selected.  So in that case there will be an extra overshad since each probe chunk file will have to be  read twice.  However, I think the main message from this diagram is that the overhead of hybrid hash  join is not that very high and so that a big join buffer is not necessary to give good  performance of hash join.  So how can we check if our join buffer is big enough for in memory hash join to be used?  We can check the performance schema table that have information about memory allocation.  It has a special event for hash join and if the count alloc and the is equal to high count  use for hash join we know that a single hash table was used which means that it was able  to do the hash join entirely in memory.  Otherwise hybrid hash join has been used.  Here you have allocated memory for multiple hash tables.  In order to be able to estimate how many chunk files are needed MySQL will try to estimate  the size of the build input.  Without histograms this estimate will often be less accurate especially when we disable  indexes since then it cannot use information from the indexes to do the estimation.  So this diagram shows what happens to our query if I remove the histogram on Ocastkey.  We see that the performance becomes much less predictable without histograms.  So to sum up there are many cases where hash join will improve the performance.  If indexes are not available there can be an enormous benefit but hash join is often  better choice when queries are eye-abound or when large part of a table will be accessed  or when there are selective conditions on multiple of the involved tables.  I have shown how you can use no index hint to force hash join to be used and increasing  the join buffer size may often improve the performance of hash join.  And finally remember to create histograms.
mysql_hash_join_0_167.png mysql_hash_join_168_419.png mysql_hash_join_420_863.png mysql_hash_join_864_971.png mysql_hash_join_972_3431.png mysql_hash_join_3432_4451.png mysql_hash_join_4452_5015.png mysql_hash_join_5016_5891.png mysql_hash_join_5892_6179.png mysql_hash_join_6180_7475.png mysql_hash_join_7476_9335.png mysql_hash_join_9336_9383.png mysql_hash_join_9384_9659.png mysql_hash_join_9660_9887.png mysql_hash_join_9888_10031.png mysql_hash_join_10032_11147.png mysql_hash_join_11148_11315.png mysql_hash_join_11316_12371.png mysql_hash_join_12372_12755.png mysql_hash_join_12756_14603.png mysql_hash_join_14604_15899.png mysql_hash_join_15900_16679.png mysql_hash_join_16680_18047.png mysql_hash_join_18048_18239.png mysql_hash_join_18240_19931.png mysql_hash_join_19932_21995.png mysql_hash_join_21996_24383.png mysql_hash_join_24384_25631.png mysql_hash_join_25632_27023.png mysql_hash_join_27024_27095.png mysql_hash_join_27096_28163.png mysql_hash_join_28164_28211.png mysql_hash_join_28212_28336.png