Query optimizers-PolarDB(PolarDB)-阿里云帮助中心

PolarDB-X uses two query optimizers: SQL Rewrite, a rule-based optimizer (RBO), and Plan Enumerator, a cost-based optimizer (CBO). Together, they form a two-stage pipeline that rewrites and then selects the lowest-cost physical execution plan for every query.

How it works

When PolarDB-X receives an SQL statement, it processes the statement in four stages: 查询优化器

The syntax parser parses the SQL text into an abstract syntax tree (AST).
The AST is converted into a logical execution plan based on relational algebra operators.
SQL Rewrite and Plan Enumerator optimize the logical execution plan and produce a physical execution plan.
The executor runs the physical execution plan and returns the result to the client.

Relational algebra operators

In a database system, an SQL query is represented as a tree of relational algebra operators. PolarDB-X uses five operator types:

Operator	Describes	Physical operators
Project	SELECT operation and its functions	—
Filter	WHERE conditions	—
Join	JOIN conditions	HashJoin, BKAJoin, Nested-Loop Join, SortMergeJoin
Aggregate	GROUP BY conditions and aggregate functions	HashAgg, SortAgg
Sort	ORDER BY and LIMIT conditions	TopN, MemSort

Example

The following SQL query joins three tables, filters by market segment and date, and aggregates revenue:

SELECT l_orderkey, sum(l_extendedprice *(1 - l_discount)) AS revenue
FROM CUSTOMER, ORDERS, LINEITEM
WHERE c_mktsegment = 'AUTOMOBILE'
  and c_custkey = o_custkey
  and l_orderkey = o_orderkey
  and o_orderdate < '1995-03-13'
  and l_shipdate > '1995-03-13'
GROUP BY l_orderkey;

Run EXPLAIN to inspect the execution plan PolarDB-X generates:

HashAgg(group="l_orderkey", revenue="SUM(*)")
  HashJoin(condition="o_custkey = c_custkey", type="inner")
    Gather(concurrent=true)
      LogicalView(tables="ORDERS_[0-7],LINEITEM_[0-7]", shardCount=8, sql="SELECT `ORDERS`.`o_custkey`, `LINEITEM`.`l_orderkey`, (`LINEITEM`.`l_extendedprice` * (? - `LINEITEM`.`l_discount`)) AS `x` FROM `ORDERS` AS `ORDERS` INNER JOIN `LINEITEM` AS `LINEITEM` ON (((`ORDERS`.`o_orderkey` = `LINEITEM`.`l_orderkey`) AND (`ORDERS`.`o_orderdate` < ?)) AND (`LINEITEM`.`l_shipdate` > ?))")
    Gather(concurrent=true)
      LogicalView(tables="CUSTOMER_[0-7]", shardCount=8, sql="SELECT `c_custkey` FROM `CUSTOMER` AS `CUSTOMER` WHERE (`c_mktsegment` = ?)")

The following figure shows the same plan as an AST.

Note

The LogicalView operator on the left side joins the ORDERS and LINEITEM tables. The sql attribute in the EXPLAIN output reflects this JOIN operation.

SQL Rewrite

SQL Rewrite is PolarDB-X's rule-based optimizer. It applies a set of heuristic rules to rewrite the logical execution plan into a more efficient form before passing it to Plan Enumerator.

SQL Rewrite performs two main types of operations:

Subquery unnesting

Nested subqueries are converted into semijoin operators or equivalent constructs. This makes them eligible for downstream optimizations, such as pushdown to ApsaraDB RDS for MySQL or algorithm selection in PolarDB-X.

In the following example, an IN subquery is rewritten as a SemiHashJoin:

> explain  select id from t1 where id in (select id from t2 where t2.name = 'hello');
SemiHashJoin(condition="id = id", type="semi")
  Gather(concurrent=true)
    LogicalView(tables="t1", shardCount=2, sql="SELECT `id` FROM `t1` AS `t1`")
  Gather(concurrent=true)
    LogicalView(tables="t2_[0-3]", shardCount=4, sql="SELECT `id` FROM `t2` AS `t2` WHERE (`name` = ?)")

Operator pushdown

Operators are pushed down to ApsaraDB RDS for MySQL to reduce the data that PolarDB-X must process. The table below lists the built-in pushdown rules and their effects.

Rule	Description
Predicate pushdown or column pruning	Pushes filter and project operators to ApsaraDB RDS for MySQL for execution and filters out rows and columns that are not required.
JOIN Clustering	Re-sorts and clusters join operations based on the sharding method and the equality condition of the shard key to facilitate subsequent pushdown of join operations.
Join pushdown	Pushes down join operations that meet specific conditions to ApsaraDB RDS for MySQL for execution.
Aggregate pushdown	Splits each aggregate operation into operations that use the FinalAgg and LocalAgg operators and then pushes down the LocalAgg operator to ApsaraDB RDS for MySQL.
Sort pushdown	Splits each sort operation into operations that use the MergeSort and LocalSort operators and then pushes down the LocalSort operator to ApsaraDB RDS for MySQL.

For more information about query pushdown, see Push down and rewrite queries.

Plan Enumerator

Plan Enumerator is PolarDB-X's cost-based optimizer. It receives the rewritten logical plan from SQL Rewrite and selects the physical execution plan with the lowest estimated cost. The execution plan generated by SQL Rewrite may be better or worse than the original execution plan. Plan Enumerator compares the costs of both and selects whichever costs less.

Core components

Plan Enumerator has five core components:

Statistics — per-table and per-column statistics collected from the data
Cardinality estimation — estimates the number of rows and selection rate for each operator, based on statistics
Transform rules — rules used to convert the logical plan into alternative physical representations
Cost model — assigns a cost value to each candidate physical plan
Plan space search engine — enumerates the candidate plans and selects the one with the lowest cost

How Plan Enumerator selects a plan

The search engine applies transform rules to the logical execution plan to construct a search space of candidate physical execution plans.
The cost model estimates the cost of each candidate plan in the search space.
During cost estimation, the cardinality estimation component uses table and column statistics to estimate the input row count, selection rate, and other information for each operator. It feeds those estimates into the cost model.
Plan Enumerator selects the physical execution plan with the lowest estimated cost.