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.
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.