Shulou(Shulou.com)06/02 Report--

This article mainly explains "What are the usages of Join of Nested Loop". The explanation in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian and go deep into it slowly to study and learn "What are the usages of Join of Nested Loop" together!

We all know how to use SQL join association tables, but this time we are talking about the algorithm to implement join. There are three algorithms for join, namely Nested Loop Join, Hash Join, and Sort Merge Join.

MySQL official documentation mentions that MySQL only supports the Nested Loop Join algorithm.

MySQL resolves all joins using a nested-loop join method. This means that MySQL reads a row from the first table, and then finds a matching row in the second table, the third table, and so on. explain-output

This article is about Nested Loop Join.

NLJ is a two-layer loop, using the first table as the Outer Loop, the second table as the Inner Loop, comparing each record of the Outer Loop with the records of the Inner Loop, and outputting those that meet the conditions. NLJ has three subdivision algorithms:

1、Simple Nested Loop Join（SNLJ） //pseudocode for (r in R) { for (s in S) { if (r satisfy condition s) { output ; } } }

SNLJ is a two-layer circular full-scan connection of two tables, two records that meet the conditions are output, which is to make the two tables do Cartesian product, the number of comparisons is R * S, is a more violent algorithm, will be more time-consuming.

2、Index Nested Loop Join（INLJ） //pseudocode for (r in R) { for (si in SIndex) { if (r satisfy condition si) { output ; } } }

INLJ is optimized on the basis of SNLJ, which determines the available index through the connection condition, scans the index in the Inner Loop instead of scanning the data itself, thus improving the efficiency of the Inner Loop. INLJ also has a disadvantage, that is, if the index scanned is a non-clustered index and needs to access non-indexed data, it will generate an operation to read the data back to the table, which will result in an additional random I/O operation.

3、Block Nested Loop Join（BNLJ）

In general, the MySQL optimizer prefers INLJ when an index is available, but it does not choose SNLJ when no index is available, or when it judges that full scan may be faster than using an index. BNLJ algorithm appears here. BNLJ uses a join buffer on the basis of SNLJ, and will read the records required by Inner Loop into the buffer in advance to improve the efficiency of Inner Loop.

//pseudocode for (r in R) { for (sbu in SBuffer) { if (r satisfy condition sbu) { output ; } } }

In MySQL, the parameter name that controls the size of the join buffer is join_buffer_size.

We only store the used columns in the join buffer, not the whole rows.join-buffer-size

According to the MySQL manual, join_buffer_size buffers columns that are used.

Algorithm comparison (outer size R, inner size S):

\algorithm

comparison\

Simple Nested Loop JoinIndex Nested Loop JoinBlock Nested Loop JoinAppearance scans 111 Inner table scans R0

Number of comparisons R * SR * IndexHeight R * S Number of returns 0RS_Matches0

In MySQL 5.6, INLJ's table return operation has been optimized, and Batched Key Access Join has been added. and Multi Range Read (mrr) feature, cache rowid of required data in join operation, and then obtain its data in batches, optimize I/O from multiple scattered operations to fewer batch operations, and improve efficiency.

Thank you for your reading. The above is the content of "What are the usages of Join of Nested Loop". After studying this article, I believe everyone has a deeper understanding of what the usages of Join of Nested Loop are. The specific usage needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.