Detailed explanation of database hash connection (new feature of MySQL)

Overview

For a long time, the only algorithm MySQL used to perform joins was the nested loop algorithm. algorithm), but the nested loop algorithm is very inefficient in certain scenarios, which is also a problem that MySQL has been criticized for.

With the release of MySQL 8.0.18, MySQL Server can use hash join. This article will briefly introduce how to implement hash join and see how it works in MySQL. , when to use it, and what are the restrictions.

Recommended study: MySQL tutorial

Introduction to hash connection

What is a hash connection?

Hash join is a join algorithm used in relational databases and can only be used for joins with equal join conditions (on a.b = c.b). It is generally more efficient than the nested loop algorithm (except when the probe end is very, very small), especially if no index is hit.

To put it simply, the hash connection algorithm is to first load a small table into the memory hash table, then traverse the data of the large table, match the qualified data in the hash table row by row, and return it to the customer end.

(The hash table is just an example, for understanding, the key of the actual hash is the value of the connection, and the value is the data row linked list)

Usually the hash The connection is divided into two phases, the build phase and the probe phase. In the construction phase, the appropriate table is first selected as the "build input", the hash table is built, and then the records of another "detection input" table are traversed in order to detect the hash table to find records that meet the connection conditions.

The above picture is an example to query the province corresponding to the city. We assume that city is the construction input. During the construction phase, the server builds a city hash table, traverses the city table, and puts the rows into the hash table in sequence. The key is hash(province_id) and the value is the corresponding city row. `

During the probe phase, the server starts reading lines from the probe input (province). For each row the hash table is probed for matching rows using the hash(province.province_id) value as the lookup key.

That is, when the construction input can all be loaded into memory, each detection line is scanned only once, and a matching line between the two inputs can be found using a constant-time search.

What should I do if there is too much data that cannot be put into the memory?

Loading all the build input into memory is undoubtedly the most efficient, but in some cases, the memory is not enough to load the entire table into memory, so it needs to be processed in batches.

There are two common methods:

Loading into memory for processing in batches

1. Reading the maximum memory can Create a hash table to accommodate the records, construct the input, and generate a hash table;

2. Traverse the detection input to conduct a full detection of this part of the hash table;

3. Clean up the hash table and restart Continue this process until all processing is complete.

This method will cause the entire detection input table to be scanned multiple times.

Write to File Processing

1. When the memory runs out during the build hash table phase, the server will write the remaining build input to many disks In small files, all small file blocks can be read into the memory after calculation and a hash table is created (to avoid that the file blocks are too large and cannot be loaded into the memory later and need to be separated again);

2. In the detection phase, due to The detection line may match a line of the build input written to disk, so the detection input also needs to be written to disk;

3. After the detection phase is completed, the block file is read from disk and loaded into memory In the hash table, read the corresponding block file from the detection input and detect the matching item;

4. After processing, move to the next pair of block files until all processing is completed.

Hash join implementation in MySQL

MySQL will select the smaller of the two inputs as the build input (calculated in bytes), and when there is enough memory In some cases, the build input is loaded into memory for processing, and in cases where it is not enough, it is processed by writing to a file.

You can use the join_buffer_size system variable to control the memory usage of hash connections. The memory used by hash connections cannot exceed this amount. When this amount is exceeded, MySQL will use files for processing.

If memory exceeds join_buffer_size and files exceed open_files_limit, execution may fail.

You can use the following two solutions:

● Increase join_buffer_size to avoid hash connection overflow to disk

● Increase open_files_limit

Under what circumstances will MySQL use hash joins?

In MySQL version 8.0.18, if tables are joined together using one or more equal join conditions, and there are no indexes available for the join conditions, a hash join will be used. MySQL prefers to use index lookups to support nested loops if an index is available.

By default, MySQL will use hash joins whenever possible, which can be enabled or disabled in the following two ways:

● Set global or session variables (hash_join = on or hash_join = off);

SET optimizer_switch="hash_join=off";

● Use hints (HASH_JOIN or NO_HASH_JOIN).

We will use the following query as an example:

EXPLAIN FORMAT = tree
SELECT
  city.name AS city_name,
  province.name AS province_name
FROM
  city
  JOIN province
    ON city.province_id = province.province_id;

The output is:

| -> Inner hash join (city.province_id = province.province_id)  (cost=1333.82 rows=1329)
    -> Table scan on city  (cost=0.14 rows=391)
    -> Hash
        -> Table scan on province  (cost=3.65 rows=34)

Hash joins can also be used in multiple join queries, as long as there is an equal value join , you can use hash connection.

For example, the following query:

EXPLAIN FORMAT= TREE
SELECT
  city.name AS city_name,
  province.name AS province_name,
  country.name AS country_name
FROM
  city
  JOIN province
    ON city.province_id = province.province_id
    AND city.id < 50
  JOIN country
    ON province.province_id = country.id

The output is:

| -> Inner hash join (city.province_id = country.id)  (cost=23.27 rows=2)
    -> Filter: (city.id < 50)  (cost=5.32 rows=5)
        -> Index range scan on city using PRIMARY  (cost=5.32 rows=49)
    -> Hash
        -> Inner hash join (province.province_id = country.id)  (cost=4.00 rows=3)
            -> Table scan on province  (cost=0.59 rows=34)
            -> Hash
                -> Table scan on country  (cost=0.35 rows=1)

Hash connection is also applicable to "Cartesian product", that is, no query conditions are specified, as follows:

EXPLAIN FORMAT= TREE
SELECT
  *
FROM
  city
  JOIN province;

The output is:

| -> Inner hash join  (cost=1333.82 rows=13294)
    -> Table scan on city  (cost=1.17 rows=391)
    -> Hash
        -> Table scan on province  (cost=3.65 rows=34)

Under what circumstances will MySQL not use hash joins?

1. Currently, MySQL hash join only supports inner joins. Anti-joins, semi-joins and outer joins are still executed using block nested loops.

2. If the index is available, MySQL will prefer to use index lookup to support nested loops;

3. When there is no equivalent query, nested loops will be used.

is as follows:

EXPLAIN FORMAT=TREE
SELECT
  *
FROM
  city
  JOIN province
    ON city.province_id < province.province_id;

The output is:

| <not executable by iterator executor>

How to check whether statement execution uses hash connection?

EXPLAIN FORMAT= TREE can be used in MySQL 8.0.16 and later versions. TREE provides tree-like output and describes query processing more accurately than the traditional format. It is the only display format. The format of the Greek connection usage.

In addition, you can also use EXPLAIN ANALYZE to view hash connection information.

---

The above is based on MySQL community Server 8.0.18.

The above is the detailed content of Detailed explanation of database hash connection (new feature of MySQL). For more information, please follow other related articles on the PHP Chinese website!