Principles

Parallel query involves two key events: table splitting and execution plan reconstruction.

• Table splitting

  

  The data to be scanned is split into partitions to enable multiple threads to scan the data in parallel. The InnoDB engine is an index-organized table that stores data in B-tree index structure. The partitioning logic is as follows: The system scans the root node page layer by layer. When the number of branches at a layer exceeds the configured threads, the system stops splitting. The partitioning process consists of two partitioning operations. In the first partitioning operation, partitioning is performed according to the quantity of branches of a root node page. A record of a leftmost leaf node of each branch is a lower left bound, and the record is denoted as an upper right bound of an adjacent upper branch. In this way, the B-tree is split into multiple subtrees, and each subtree is a scanning partition. After the first partitioning operation, the threads may not be fully used. For example, if the number of parallel scanning threads is set to 3 and 4 partitions are generated after the first partitioning, at most one thread is used to scan the fourth partition after the first three partitions are processed in parallel. In this case, multi-core resources cannot be fully utilized.

  To solve the load imbalance caused by the first partitioning operation, the fourth partition is partitioned for the second time. After the second partitioning operation, multiple smaller blocks are obtained. In this way, the scanning data of each thread is more balanced.

• Reconstructing execution plans

  The MySQL execution plan is a left-deep tree. Before parallel execution, MySQL uses a thread to recursively execute the left-deep tree, and then performs sorting or aggregation on the join result. Parallel execution aims to use multiple threads to execute the execution plan tree in parallel. The first non-const primary table is split. The execution plan of each thread is the same as the original execution plan, but the first table is only part of the table. In this way, each thread executes part of the execution plan. These threads are called worker threads. After the execution is complete, the results are submitted to the leader for summary, and then sorted and aggregated, or the results are directly sent to the client.