The labs on this site need JavaScript to run. The same content is written out below.

Learn › Database › Indexes and execution plans

Join algorithms

How does the database find matching rows when the join column has no index?

A join reads one table first and, for each of its rows, finds the matching rows in the other table. If an index can be used to find the matches, only the rows needed are read. If not, the whole table must be read. In that case, MySQL 8 uses a different method called a hash join.

Checked against real execution · Seven combinations were run on MySQL 8.4 with EXPLAIN, EXPLAIN FORMAT=TREE, and EXPLAIN ANALYZE and checked against the join method and the number of reads

Concepts in this lab

Nested-loop join

A join method that reads the rows of one table one at a time and, for each row, finds the matching rows in another table. It has the same shape as a double loop (nested loops) in a program, which is where the name comes from. The amount read is the number of rows in the table read first multiplied by the number of rows read per lookup. If the join column of the table read later has an index, only the rows needed are read, but if it does not, the whole table must be read each time.

Hash join

A join method that builds in memory a hash table keyed on the join column values of the rows of one table, and then reads the other table once, finding the matches in that hash table. Each table is read only once, so it reads far less than joining with a nested loop without an index. MySQL supports it from 8.0.18, and chooses it when there is no index that can be used for the join column. Compared with a join that uses an index, it has the disadvantages that the hash table takes memory and that the table is read in full even when only some of its rows are needed.

Driving table

The table that is read first in a join. In a nested-loop join, the rest of the tables are looked up for each row of this table. Which table becomes the driving table is decided not by the order written in FROM but by the optimizer calculating costs. The one chosen is usually the table that has fewer rows after filtering by conditions and whose counterpart table can then be reached through an index. In MySQL, the table on the upper line of the EXPLAIN result is the driving table.

Optimizer

The database component that chooses, among the several ways a SQL statement can be executed, the one that is expected to cost the least. It decides based on statistics such as the number of rows in a table and the distribution of values. If the statistics differ from the real data, it can choose an inefficient way.

Query execution plan (EXPLAIN)

The plan that the database decides on for how to run a query. It shows which indexes are used, in what order the tables are joined, and how many rows the database expects to read. You view it by putting EXPLAIN in front of the query, and it is the starting point for finding the cause when a query is slow.

Try these

• Default settings — The join column has no index. A hash join is chosen instead of a nested-loop join.
• Creating an index on the join column — It becomes a nested-loop join, which looks up each row through the index.
• No index and no hash join — For each row of member, the whole of orders is read. That is 10,000,000 rows.
• Reading orders first — member is looked up one row at a time by primary key.
• Leaving it to the optimizer (no index) — It sets the order so that the table that can be reached through an index is read later.
• Leaving it to the optimizer (with an index) — It reads member, which has fewer rows, first.

Running with the default settings

1. The query: it pairs member and orders by member number and retrieves each member name and order amount. member has 1,000 rows and orders has 10,000 rows, with 10 orders per member. The result is 10,000 rows.
2. Deciding which table to read first: STRAIGHT_JOIN makes the tables be read in the order written, so member is read first. The table that is read first is called the driving table.
3. Deciding how to find matches: the join column member_id of orders, the table read later, has no index. With a nested loop, all 10,000 rows of orders would have to be read for every row of member. In this case, MySQL 8 chooses a hash join. The first line of EXPLAIN FORMAT=TREE shows Inner hash join.
4. Hash join step 1, build the hash table: the 1,000 rows of member are read once, and a hash table keyed on id is built in memory. A hash table is a structure in which an entry is put directly into a position calculated from its key value and is found directly from the same calculation.
5. Hash join step 2, find matches: the 10,000 rows of orders are read once from beginning to end, and for each row, member_id is looked up in the hash table. Each lookup checks only the calculated position instead of scanning a table. Times orders was read: 1.
6. The result, 10,000 rows, is produced. The rows read from the two tables: member 1,000 rows and orders 10,000 rows, 11,000 rows in total.

Result of this run

• A hash join builds a hash table from one table and reads the other table only once. Where a nested-loop join without an index would have read 1,000 × 10,000 = 10,000,000 rows, it finishes with 11,000 rows. In EXPLAIN, the Extra column shows Using join buffer (hash join).
• Even so, indexes do not become unnecessary. A hash join reads the whole of orders, so even if you only look for the orders of 10 members, it reads all 10,000 rows of orders. With an index, it would look up 10 times and read only 100 rows.

Code

-- member: 1,000 rows (primary key id)
-- orders: 10,000 rows (10 orders per member)
-- no index on orders.member_id

EXPLAIN FORMAT=TREE
SELECT m.name, o.amount
  FROM member m
  STRAIGHT_JOIN orders o ON o.member_id = m.id;   -- read the tables in the order written

Assumptions of this model

For all seven combinations that can be chosen on the screen, the same tables (member with 1,000 rows and orders with 10,000 rows) were created in MySQL 8.4 on the PC used to write this lab, ANALYZE TABLE was run, and the results were checked against the model. The type, key, and Extra of the table read first and the table read later were checked with EXPLAIN, the join method with the first line of EXPLAIN FORMAT=TREE, and the number of times the later table was read and the rows read each time with loops and rows of EXPLAIN ANALYZE, which counts while it actually runs the query. In the five cases where the hash join setting is hidden, it was also confirmed that adding the NO_BNL hint does not change the plan. The order chosen when the choice is left to the optimizer is the result of a cost calculation, so it can differ depending on the amount and distribution of the data. "Rows read" is the number of rows taken out of the tables or indexes. It does not include the cost of descending an index, the cost of building and searching a hash table, or the time taken. Hash joins were introduced in MySQL 8.0.18, and from 8.0.20 they replace the block nested-loop join that was used for joins without an index. If the hash table does not fit in memory (join_buffer_size), disk is used as well. These two points were not confirmed by running them; they follow the explanation of hash join optimization in the MySQL documentation. The diagram is reduced to 3 members and 6 orders.

Previous lab: Reading the execution plan · Next lab: Transaction basics