Index Nested-Loop Join
This join uses the query:
select * from t1 straight_join t2 on (t1.a=t2.a);The process involves traversing table t1 first, then based on each row's 'a' value from table t1, records satisfying the conditions are looked up in table t2. This process is similar to a nested query in programming and can make use of the index on the driven table, hence it's called "Index Nested-Loop Join," or NLJ.
During this join process, the driving table goes through a full table scan, whereas the driven table undergoes a tree search.
If the driven table has M rows, each lookup in the driven table requires searching index 'a' first, then the primary index. The time complexity for looking up a row in the driven table is 2*log2M.
If the driving table has N rows, the execution process needs to scan N rows in the driving table, and for each row, it matches once in the driven table. Therefore, the total complexity of the execution process is roughly N + N2log2M. Because the influence of N on the number of row scans is larger, the smaller table should be chosen as the driving table.
Simple Nested-Loop Join
This join uses the query:
select * from t1 straight_join t2 on (t1.a=t2.b);Since table t2 doesn't have an index on field 'b', every time a match is made on t2, a full table scan needs to be performed.
Block Nested-Loop Join
This join works as follows when there is no usable index on the driven table:
- The data from table t1 is read into the thread's memory join_buffer. In our case where we use
select *, the entire table t1 is placed into memory.
- Table t2 is scanned, with each row from t2 taken out and compared with the data in join_buffer. Rows that satisfy the join conditions are returned as part of the result set.
In this process, a full table scan is conducted on tables t1 and t2, so the total number of scanned rows is 1100. Since the join_buffer is organized as an unordered array, every row in table t2 has to be checked 100 times. The total number of checks performed in memory is 100*1000 = 100,000. These 100,000 checks are memory operations, so the speed will be much faster, and the performance is also better.
For the Block Nested-Loop Join algorithm:
- When the join_buffer_size is large enough, the operation remains the same.
- When the join_buffer_size is not large enough (which is more common), the smaller table should be selected as the driving table.
Optimization
The Multi-Range Read optimization primarily aims to make use of sequential disk reads. If the query is executed in an increasing order of the primary key, the disk read operation becomes more sequential, thereby enhancing the read performance.
- Based on index 'a', records that meet the conditions are located, and their id values are placed into read_rnd_buffer.
- The ids in read_rnd_buffer are sorted in ascending order.
- After sorting, each id in the array is used to lookup records in the primary index 'id' and returned as results.
The core reason that MRR can enhance performance is that this query statement conducts a range query on index 'a', which can provide a sufficient number of primary key 'id'. After sorting, the subsequent operation of searching data from the primary index can demonstrate the advantage of "sequentiality".
Batched Key Access (BKA) Algorithm
The BKA algorithm is essentially an optimization of the NLJ algorithm. By reusing the join_buffer in the NLJ algorithm, it becomes the BKA algorithm. It can be enabled with the following command:
set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';Impact of the BNL algorithm on the system:
- It may scan the driven table multiple times, occupying disk IO resources.
- The join condition needs to execute M*N comparisons (where M and N are the number of rows in the two tables respectively). For large tables, this can use up a lot of CPU resources.
- It may lead to the elimination of hot data in the Buffer Pool, affecting memory hit rate.
