Fast query performance with MySQL Hypergraph Optimizer for HeatWave

 

Overview

MySQL HeatWave is a fully managed service that enables developers and database administrators to run OLTP and OLAP workloads directly from their MySQL database without the need of ETL. HeatWave accelerates MySQL query performance by order of magnitudes and allows user to analyze real-time data.

To provide a single service for 2 different workloads, MySQL HeatWave consists of two query processing engines with two completely different physical data layouts, query processing models, supported query processing algorithms and performance characteristics:

  1. MySQL InnoDB storage engine – a row major, single threaded, transactional processing database engine
  2. HeatWave – a columnar major, in-memory, vectorized, and massively parallel pushed based query processing engine. OLAP queries or other queries which require significant acceleration are offloaded to HeatWave, while rest of the queries are executed on the existing MySQL InnoDB engine.

Queries coming to MySQL HeatWave first go through MySQL optimizer, based on cost and certain other factors, MySQL optimizer routes these queries to MySQL InnoDB storage engine or HeatWave. The queries selected for HeatWave acceleration are passed to the HeatWave optimizer. For such queries, MySQL optimizer is still responsible for logical optimizations such as deciding join order, filter push down etc., while the HeatWave optimizer is responsible for physical optimizations such as finalizing the join algorithm, selecting degree of parallelism, deciding number of partitions before a join etc. See figure 1 below for the high level query flow.

Query flow in MySQL HeatWave

Figure 1 – Query flow in MySQL HeatWave

There are several limitations with this framework and approach:

  1. Join order optimization algorithm is designed for MySQL InnoDB storage engine, it is not suitable for HeatWave in-memory OLAP engine. For example, a join order which includes cartesian product can work well with MySQL InnoDB storage engine, but it can lead to out of memory error in HeatWave.
  2. The logical optimizations carried out by MySQL optimizer is completely oblivious of Heatwave characteristics and costs, this can lead to sub-optimal plans. The logical optimization decisions are not influenced by possible physical optimizations that HeatWave optimizer can perform.
  3. Statistics estimations such as cardinality estimates for joins, distribution of data etc. can be inaccurate resulting in poor join order decisions for the HeatWave engine.

 

MySQL Hypergraph Optimizer

Solution

To achieve efficient, true cost-based join optimization for MySQL HeatWave, a new MySQL hypergraph optimizer is introduced in 8.0.31. It extends the MySQL optimizer to support hypergraph-based join optimization framework. The new MySQL hypergraph optimizer can now use HeatWave cost model to guide the join search space to produce optimized join query plans for HeatWave.

Hypergraph is a generalized graph data structure, where an edge can connect any number of vertices. The edges represent join predicates and the vertices the tables involved in the join query. Thus, a hypergraph provides an easy way of representing join with complex predicates and reason about them during join order enumeration.

Hypergraph concept illustration

Figure 2 – Hypergraph concept illustration

 

Integration with HeatWave

The MySQL hypergraph optimizer is integrated and enabled in MySQL HeatWave for queries offloaded to HeatWave engine. Such queries, after going through the MySQL parser, passes through hypergraph optimizer for join optimization.  

 

MySQL hypergraph optimizer integration with HeatWave

Figure 3 – MySQL hypergraph optimizer integration with HeatWave

The MySQL hypergraph optimizer is responsible for join order optimization, while HeatWave optimizer is for the physical optimization and cost estimation specific to HeatWave engine.

Instead of going through logical and physical optimizations for MySQL and HeatWave in two distinct phases and thereby decreases the chances of finding optimal query plans, the new hypergraph graph optimization framework supports an iterative cross-engine logical & physical optimization. For every possible join order candidate, a physical optimization & cost estimation is performed in HeatWave optimizer and the corresponding expected cost, estimated cardinalities and feasibility information is passed back to MySQL hypergraph optimizer. This allows MySQL hypergraph optimizer to find the optimal join order search space for HeatWave. Once the optimal join order is found , HeatWave optimizer continues to process the query to a full-blown physical optimization query plan. In this way, the join order decisions are guided by the physical properties of HeatWave query processing engine.

 

HeatWave cost model and intermediate relation cardinality estimation plays an important role in guiding MySQL hypergraph optimizer to determine the optimal join order.

  1. Cost model: HeatWave cost model is an analytical cost model composed of reasonably accurate fine grained cost functions.
  2. Cardinality estimation: Cardinalities from actual query runs are cached which is used for cardinality estimation of an exact query, a sub-set of a query or a similar query.

HeatWave uses MySQL Autopilot (Auto query plan improvement) to automatically collect cardinality statistics and to calculate costs.  Cardinality accuracy improves when more queries are run in the system, making cost model more accurate.

 

Improved User Experience & Performance

Elimination of STRAIGHT JOIN hints & Improved Query Plan Quality: With MySQL hypergraph optimizer enabled for HeatWave, join order optimization step in MySQL optimizer is now HeatWave aware . It uses cost estimation from HeatWave optimizer to avoid

  1. infeasible join plans causing HeatWave to run out of memory
  2. bad join order causing poor performance & scalability

This eliminates the need for user to manually optimize the join order using STRAIGHT JOIN hints. For example, with TPCH benchmark, MySQL HeatWave now runs all 22 TPCH queries without STRIGHT JOIN hints.

TPCH results using MySQL hypergraph optimizer with HeatWave

 

Improved Search Space & Join Query Performance: With the new MySQL hypergraph optimizer, more query plans can be generated which were not feasible with the old MySQL optimizer. The search space explored by hypergraph optimizer is larger, and it considers more join patterns.

For example, hypergraph optimizer considers numerous patterns of bushy join plans in the search space, which cannot be done by the old MySQL optimizer. If cost estimation of such bushy join plans is cheaper than the traditional left-deep join plans, then busy join plans are selected by the optimizer.

Hypergraph optimizer explores larger search space for optimal query plan for HeatWave

Figure 4 – Hypergraph optimizer explores larger search space for optimal query plan for HeatWave

 

Conclusion

The HeatWave team at Oracle continues to innovate and deliver features that improve the user experience, performance, and scalability of the HeatWave query processing engine.

The integration of MySQL hypergraph optimizer with HeatWave allows MySQL optimizer to consider the characteristics of the HeatWave engine when determining the best join order for a query. As a result, it eliminates the need for manual query optimization (through STRAIGHT JOIN hints) to avoid out of memory errors and to improve join query performance. This makes it easier for users to take advantage of the performance benefits offered by the HeatWave engine without any changes to the queries.

Additionally, hypergraph optimizer helps in expanding the search space which results in optimal join queries outperforms same queries optimized by experienced DBA/developer using STRAIGH JOIN hint.

 

Addition Resources