The MySQL Volcano model iterator has a 1400+ fold performance increase.

This article is shared by Huawei Cloud community “Huawei Cloud database kernel expert reveals the secrets of MySQLVolcano model iterator performance improvement by a thousand times” by GaussDB database.

More than 20 years database kernel development experience. Former IBMDB2 database kernel expert, specializing in database kernel performance optimization, SQL query optimization, MPP distributed data warehouse technology, etc. Now I am working for Huawei Research Institute in Canada. I am fully involved in the research and development of RDS for MySQL and GaussDB(for MySQL), and familiar with GaussDB(for MySQL) full stack technology. Responsible for the overall architecture design and implementation of NDP, and successfully launched it. He has a number of technical invention patents and co-authored SIGMOD 2020 Taurus(GaussDB(forMySQL)) Paper. He is currently focusing on the research of the next generation intelligent optimizer for cloud database.

I. Background introduction

MySQL 8.0.18 introduces a new SQL execution engine that follows the Volcano model. The key idea of this model is to model all operations as “iterators”. Iterators provide the basic components of iteration: initialization, iteration, and termination. All iterators provide the same interface as above, so iterators can be arbitrarily stacked together to form an execution plan.

MySQL 8.0.18 also includes a new connection method: hash join. Hash connections have probe and build ends. Hash tables are built using join columns on the build side as hash keys; The join columns on the probe side are then used to find matching rows in the hash table.

Details about the Volcano model and hash joins are beyond the scope of this article. This article focuses on the problem that predicates for hash joins are not attached to appropriate hash join iterators, which can cause serious performance degradation. Note: This is not a functional issue because the final query results are correct despite the significant performance degradation.

Huawei cloud database kernel expert Lin Shu submitted this error report and the corresponding patch to the MySQL official. For details, see bugs.mysql.com/? Id = 104760. …

The queries in this article were tested on MySQL 8.0.26, using a 100MB TPC-H database. To illustrate, Index hints are used in the query statement to force the SQL optimizer to select a hash join.

Ii. Problem description

The query used for this problem and its execution plan are as follows:

Question query:

explain format=tree
select avg(case ps_partkey when null then 1 else l_quantity end)
from lineitem left outer join 
( partsupp ignore index (primary) join part ignore index (primary) on ps_partkey = p_partkey and p_name like '%snow%')
on ps_suppkey = l_suppkey and ps_partkey = l_partkey
Copy the code

Execution Plan:

-> Aggregate: Avg ((case partsup.ps_partkey when NULL then 1 else lineitem.l_quantity end)) (cost=179829230844583.70) rows=899131908749360) -> Left hash join (part.P_PARTKEY = lineitem.L_PARTKEY), (partsupp.PS_PARTKEY = lineitem.L_PARTKEY), (partsup.ps_suppkey = lineItem.l_suppkey) (cost=89916039969647.67 rows=899131908749360) -> Table scan on lineitem (cost=61043.00 rows=596410) -> Hash -> Filter: (part.p_name like '%snow%') (cost=2849092735.78 rows=1507573496) -> Inner Hash JOIN (no condition) (cost=2849092735.78 Rows =1507573496) -> Table scan on partsupp (cost=0.23 rows=77726) -> Hash -> Table scan on part (cost=0.01 rows=19396)Copy the code

Note that in the Inner Hash join part of the query plan above, the join between partsupp and part is “unconditional” and the predicate (part.p_name like “%snow%”) is applied to filter the result set after the Inner hash join is complete. Looking at the original query, we notice that there is a join predicate (ps_partkey = p_partkey) between partsupp and part. Where is this predicate? It is implicit in the join predicate of the outer Left Hash join, P_PARTKEY = lineItem.l_partkey) and partupp.ps_partkey = lineitem.l_partkey. The absence of predicates in an inner hash join causes performance problems because it causes join operations with predicates to be replaced with Cartesian products, and the result set is magnified by the lack of join conditions to filter. In addition, the local predicate (part.p_name like “%snow%”), which can be applied before an inner hash join, filters out invalid rows in advance.

3. Cause analysis

This problem occurs when a statement uses an outer join, which is done using a hash join, and part of the outer join involves more than one table. When these conditions are present at the same time, the problem may arise.

In a hash join, the builder is unable to access any columns on the probe, and vice versa. A predicate that references both ends can only be placed on a hash join iterator. When the MySQL optimizer assigns predicates to tables, it assumes that the predicates can refer to all tables that appear before the table, however this obviously does not apply to hash joins. Therefore, when the optimizer’s plan is converted to an iterator plan, the optimizer-to-iterator conversion code needs to make an additional remedy, which is now missing in MySQL’s conversion code, causing the problems in this article.

Four, how to repair

Fixes for this issue focus on the main function in the optimizer structure-to-iterator conversion code: ConnectJoins(). The basic idea is to let the function know which tables are not currently available because they are on the other side of the hash join. When the function places the predicate on the iterator, the predicates that have not yet been applied are pushed up the iterator and applied as soon as the required table becomes available.

The following is the execution plan after the fix is applied on MySQL 8.0.26. The inner hash join between partupp and part now has a join predicate: partupp.ps_partkey = part.p_key. In addition, the local predicate (part.p_namelike “%snow%”) now appears below the inner join, which is applied before the inner hash join.

-> Aggregate: Avg ((case partsup.ps_partkey when NULL then 1 else lineitem.l_quantity end)) (cost=179829230844583.70) rows=899131908749360) -> Left hash join (part.P_PARTKEY = lineitem.L_PARTKEY), (partsup.ps_suppkey = lineItem.l_suppkey) (cost=89916039969647.67 rows=899131908749360) -> Table scan on lineitem (cost=61043.00 rows=596410) -> Hash -> Inner Hash JOIN (partsup.ps_partkey = part.p_partkey) (cost=2849092735.78) Rows =1507573496) -> Table scan on partsupp (cost=0.23 rows=77726) -> Hash -> Filter: (part.p_name like '%snow%') (cost=0.01 rows=19396) -> Table scan on part (cost=0.01 rows=19396)Copy the code

The following compares the query time before and after patch application: Before patch installation, the query time was 11 minutes and 37 seconds

After the patch is installed, the query takes only 0.49 seconds

11 minutes 37 seconds vs 0.49 seconds, the performance difference before and after modification is more than 1400 times, the difference is huge. Hopefully this will be addressed in the next MySQL release.

As we know, the development of MySQL community is inseparable from the efforts of every database practitioner. Huawei Cloud GaussDB has always attached importance to the development of open source community, actively optimized and improved the community version, and made contributions to the community. The predicate position optimization of the MySQLVolcano model iterator helps improve MySQL query performance by a factor of 1000, which is the positive feedback of Huawei Cloud GaussDB to community development.

In addition, tell everyone a good news, huawei cloud special database activity is ongoing, cloud database MySQL 19.9 yuan in package, help enterprise safe on the cloud, more activity details stamp: activity.huaweicloud.com/dbs_Promoti…

References:

[1] g. Graefe, “Volcano — An Extensible andParallel Query Evaluation System,” IEEE Transactions on Knowledge and DataEngineering, pp. 120-135, 1994.

11785: [2] “WL# Volcano iteratordesign,” [Online]. Available:dev.mysql.com/worklog/tas… .

12074: [3] “WL# Volcano iterator executorbase,” [Online]. The Available: dev.mysql.com/worklog/tas… .

12470: [4] “WL# Volcano iteratorsemijoin,” [Online]. Available:dev.mysql.com/worklog/tas… .

[5] “Hash Join Optimization,” [Online]. The Available: dev.mysql.com/doc/refman/… .

[6] WL# “2241: a Hash join,” [Online]. The Available: dev.mysql.com/worklog/tas… .

“TPC-HHomepage,” [Online]. Available: www.tpc.org/tpch/.

Click to follow, the first time to learn about Huawei cloud fresh technology ~