Rule-based query rewriting includes subquery-related rewriting, outer join elimination, condition simplification, and non-SPJ query rewriting.
Subquery rewriting
The optimizer generally executes a subquery nested within a parent query. For example, the parent query generates a row of data, and then the optimizer executes the subquery. This process repeats until the optimizer executes the subquery for all rows of data generated by the parent query. Although this execution method ensures correct results, it is inefficient because the subquery is executed multiple times. To improve the efficiency, you can rewrite the subquery into a join operation. The main advantages are as follows:
The subquery is executed fewer times.
The optimizer can choose a better join order and join method based on statistics.
After the join conditions and filter conditions of the subquery are rewritten into those of the parent query, the optimizer can apply further optimizations, such as condition pushing.
You can rewrite a subquery through view merging, subquery unfolding, and rewriting ANY/ALL into MAX/MIN.
View merging
View merging is the process of integrating a subquery that represents a view into the query that contains the view. After view merging, the optimizer can choose the join order, access path, and perform other transformations to find a better execution plan.
OceanBase Database allows view merging for SPJ views. The following example shows how to rewrite query Q1 into query Q2:
obclient> CREATE TABLE t1 (c1 INT, c2 INT);
Query OK, 0 rows affected
obclient> CREATE TABLE t2 (c1 INT PRIMARY KEY, c2 INT);
Query OK, 0 rows affected
obclient> CREATE TABLE t3 (c1 INT PRIMARY KEY, c2 INT);
Query OK, 0 rows affected
Q1:
obclient> SELECT t1.c1, v.c1
FROM t1, (SELECT t2.c1, t3.c2
FROM t2, t3
WHERE t2.c1 = t3.c1) v
WHERE t1.c2 = v.c2;
<==>
Q2:
obclient> SELECT t1.c1, t2.c1
FROM t1, t2, t3
WHERE t2.c1 = t3.c1 AND t1.c2 = t3.c2;
If Q1 is not rewritten, the possible join orders are as follows:
t1,v(t2,t3)t1,v(t3,t2)v(t2,t3),t1v(t3,t2),t1
After view merging, the possible join orders are as follows:
t1,t2,t3t1,t3,t2t2,t1,t3t2,t3,t1t3,t1,t2t3,t2,t1
As we can see, view merging increases the selectivity of the join order. For complex queries, view merging increases the space for path selection and transformation, enabling the optimizer to generate better execution plans.
Subquery expansion
Subquery expansion is the process of moving a WHERE condition containing a subquery to the parent query and rewriting it as a join condition. After the subquery is expanded, it is removed, and the subquery result is obtained through a join between the parent query and the tables in the subquery.
This modification allows the optimizer to consider tables in the subquery during path selection, join method determination, and join order arrangement, thereby enabling the optimizer to generate better execution plans. Subqueries involved in the conversion are typically NOT IN, IN, NOT EXISTS, EXISTS, ANY, and ALL expressions.
The subquery expansion process is as follows:
Write a new join condition based on the original condition to ensure that the same rows are returned by both the original and new queries.
Expand the subquery into a semi join or anti join.
In the following example,
c2in tablet2does not have a unique value. The original statement is rewritten into a semi join, and the execution plan is as follows:obclient> CREATE TABLE t1 (c1 INT, c2 INT); Query OK, 0 rows affected obclient> CREATE TABLE t2 (c1 INT PRIMARY KEY, c2 INT); Query OK, 0 rows affected obclient> EXPLAIN SELECT * FROM t1 WHERE t1.c1 IN (SELECT t2.c2 FROM t2)\G *************************** 1. row *************************** Query Plan: ======================================= |ID|OPERATOR |NAME|EST. ROWS|COST| --------------------------------------- |0 |HASH SEMI JOIN| |495 |3931| |1 | TABLE SCAN |t1 |1000 |499 | |2 | TABLE SCAN |t2 |1000 |433 | ======================================= Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t1.c2]), filter(nil), equal_conds([t1.c1 = t2.c2]), other_conds(nil) 1 - output([t1.c1], [t1.c2]), filter(nil), access([t1.c1], [t1.c2]), partitions(p0) 2 - output([t2.c2]), filter(nil), access([t2.c2]), partitions(p0)After you change the preceding condition to
NOT IN, the original statement can be rewritten into an anti join, and the execution plan is as follows:obclient> EXPLAIN SELECT * FROM t1 WHERE t1.c1 NOT IN (SELECT t2.c2 FROM t2)\G *************************** 1. row *************************** Query Plan: ================================================ |ID|OPERATOR |NAME|EST. ROWS|COST | ------------------------------------------------ |0 |NESTED-LOOP ANTI JOIN| |0 |520245| |1 | TABLE SCAN |t1 |1000 |499 | |2 | TABLE SCAN |t2 |22 |517 | ================================================ Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t1.c2]), filter(nil), conds(nil), nl_params_([t1.c1], [(T_OP_IS, t1.c1, NULL, 0)]) 1 - output([t1.c1], [t1.c2], [(T_OP_IS, t1.c1, NULL, 0)]), filter(nil), access([t1.c1], [t1.c2]), partitions(p0) 2 - output([t2.c2]), filter([(T_OP_OR, ? = t2.c2, ?, (T_OP_IS, t2.c2, NULL, 0))]), access([t2.c2]), partitions(p0)Expand the subquery into an inner join.
In the preceding example, if you change
c2intoc1in tablet2, sincec1is the primary key and the values returned by the subquery are unique, you can directly rewrite the statement into an inner join, as follows:Q1: obclient> SELECT * FROM t1 WHERE t1.c1 IN (SELECT t2.c1 FROM t2)\G <==> Q2: obclient> SELECT t1.* FROM t1, t2 WHERE t1.c1 = t2.c1;After Q1 is rewritten, the execution plan is as follows:
obclient> EXPLAIN SELECT * FROM t1 WHERE t1.c1 IN (SELECT t2.c1 FROM t2)\G *************************** 1. row *************************** Query Plan: ==================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ------------------------------------ |0 |HASH JOIN | |1980 |3725| |1 | TABLE SCAN|t2 |1000 |411 | |2 | TABLE SCAN|t1 |1000 |499 | ==================================== Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t1.c2]), filter(nil), equal_conds([t1.c1 = t2.c1]), other_conds(nil) 1 - output([t2.c1]), filter(nil), access([t2.c1]), partitions(p0) 2 - output([t1.c1], [t1.c2]), filter(nil), access([t1.c1], [t1.c2]), partitions(p0)You can apply a similar transformation to
NOT IN,IN,NOT EXISTS,EXISTS,ANY, andALLsubqueries.
Rewriting ANY/ALL queries using MAX/MIN
If a ANY/ALL subquery does not contain a GROUP BY clause, aggregate functions, or HAVING conditions, the following expression can be rewritten using the aggregate functions MIN or MAX, where col_item represents a single column that cannot be NULL:
val > ALL(SELECT col_item ...) <==> val > (SELECT MAX(col_item) ...);
val >= ALL(SELECT col_item ...) <==> val >= (SELECT MAX(col_item) ...);
val < ALL(SELECT col_item ...) <==> val < (SELECT MIN(col_item) ...);
val <= ALL(SELECT col_item ...) <==> val <= (SELECT MIN(col_item) ...);
val > ANY(SELECT col_item ...) <==> val > (SELECT MIN(col_item) ...);
val >= ANY(SELECT col_item ...) <==> val >= (SELECT MIN(col_item) ...);
val < ANY(SELECT col_item ...) <==> val < (SELECT MAX(col_item) ...);
val <= ANY(SELECT col_item ...) <==> val <= (SELECT MAX(col_item) ...);
After the subquery is rewritten to contain MAX or MIN, you can use MAX or MIN to rewrite the subquery again, thereby reducing the number of scans of the inner table before rewriting. Here is an example:
obclient>SELECT c1 FROM t1 WHERE c1 > ANY(SELECT c1 FROM t2);
<==>
obclient>SELECT c1 FROM t1 WHERE c1 > (SELECT MIN(c1) FROM t2);
After being rewritten to contain MAX or MIN, you can push the LIMIT 1 condition, which is based on the primary key of t2.c1, directly down to TABLE SCAN to return the minimum value. The execution plan is as follows:
obclient> EXPLAIN SELECT c1 FROM t1 WHERE c1 > ANY(SELECT c1 FROM t2)\G
*************************** 1. row ***************************
Query Plan:
===================================================
|ID|OPERATOR |NAME |EST. ROWS|COST|
---------------------------------------------------
|0 |SUBPLAN FILTER | |1 |73 |
|1 | TABLE SCAN |t1 |1 |37 |
|2 | SCALAR GROUP BY| |1 |37 |
|3 | SUBPLAN SCAN |subquery_table|1 |37 |
|4 | TABLE SCAN |t2 |1 |36 |
===================================================
Outputs & filters:
-------------------------------------
0 - output([t1.c1]), filter([t1.c1 > ANY(subquery(1))]),
exec_params_(nil), onetime_exprs_(nil), init_plan_idxs_([1])
1 - output([t1.c1]), filter(nil),
access([t1.c1]), partitions(p0)
2 - output([T_FUN_MIN(subquery_table.c1)]), filter(nil),
group(nil), agg_func([T_FUN_MIN(subquery_table.c1)])
3 - output([subquery_table.c1]), filter(nil),
access([subquery_table.c1])
4 - output([t2.c1]), filter(nil),
access([t2.c1]), partitions(p0),
limit(1), offset(nil)
Elimination of outer joins
Outer joins can be left outer joins, right outer joins, and full outer joins. The optimizer cannot freely exchange the positions of the two tables involved in an outer join, which limits the join orders that the optimizer can choose from. Elimination of outer joins converts outer joins into inner joins, providing the optimizer with more join orders to choose from.
To eliminate an outer join, a "null value rejecting condition" must be met, namely, a WHERE condition exists such that when the inner table generates a NULL value, the condition evaluates to FALSE.
Here is an example:
obclient> SELECT t1.c1, t2.c2 FROM t1 LEFT JOIN t2 ON t1.c2 = t2.c2;
This query statement contains an outer join. The value of the t2.c2 column in the output result set can be NULL. If a WHERE condition t2.c2 > 5 is added, then NULL values cannot appear in the output result set of the t1.c1 column after the condition filters the result set. In this case, the outer join can be converted into an inner join.
obclient> SELECT t1.c1, t2.c2 FROM t1 LEFT JOIN t2 ON t1.c2 = t2.c2 WHERE t2.c2 > 5;
<==>
obclient> SELECT t1.c1, t2.c2 FROM t1 INNER JOIN t2 ON t1.c2 = t2.c2
WHERE t2.c2 > 5;
Simplified condition rewriting
Elimination of the HAVING condition
If the query does not contain an aggregate operation or a GROUP BY clause, the HAVING condition can be combined with the WHERE condition and removed. This way, the HAVING condition can be managed and optimized together with the WHERE condition.
obclient> SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1 HAVING t1.c2 > 1;
<==>
obclient> SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1 AND t1.c2 > 1;
The following example shows a rewritten execution plan. The t1.c2 > 1 condition is pushed down to the TABLE SCAN operator.
obclient> EXPLAIN SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1 HAVING t1.c2 > 1\G;
*************************** 1. row ***************************
Query Plan:
=========================================
|ID|OPERATOR |NAME|EST. ROWS|COST|
-----------------------------------------
|0 |NESTED-LOOP JOIN| |1 |59 |
|1 | TABLE SCAN |t1 |1 |37 |
|2 | TABLE GET |t2 |1 |36 |
=========================================
Outputs & filters:
-------------------------------------
0 - output([t1.c1], [t1.c2], [t2.c1], [t2.c2]), filter(nil),
conds(nil), nl_params_([t1.c1])
1 - output([t1.c1], [t1.c2]), filter([t1.c2 > 1]),
access([t1.c1], [t1.c2]), partitions(p0)
2 - output([t2.c1], [t2.c2]), filter(nil),
access([t2.c1], [t2.c2]), partitions(p0)
Derivation of equivalent conditions
Based on the transitivity of comparison operators, equivalent condition expressions can be derived. This reduces the number of rows to be processed or helps select a more efficient index.
OceanBase Database can derive equivalent conditions for value-based joins. For example, in a table with columns a and b, the condition a = b AND a > 1 can be derived into a = b AND a > 1 AND b > 1. If an index exists on column b and the selectivity of the b > 1 condition is low for the index, the performance of accessing the table with column b can be significantly improved.
Consider the condition t1.c1 = t2.c2 AND t1.c1 > 2. After equivalent condition derivation, it becomes t1.c1 = t2.c2 AND t1.c1 > 2 AND t2.c2 > 2. As we can see in the plan below, the t2.c2 > 2 condition is pushed down to the TABLE SCAN operator and uses the index on t2.c2.
obclient> CREATE TABLE t1(c1 INT PRIMARY KEY, c2 INT);
Query OK, 0 rows affected
obclient> CREATE TABLE t2(c1 INT PRIMARY KEY, c2 INT, c3 INT, KEY IDX_c2(c2));
Query OK, 0 rows affected
/*This command needs to be run in MySQL mode.*/
obclient> EXPLAIN EXTENDED_NOADDR SELECT t1.c1, t2.c2 FROM t1, t2
WHERE t1.c1 = t2.c2 AND t1.c1 > 2\G
*************************** 1. row ***************************
Query Plan:
==========================================
|ID|OPERATOR |NAME |EST. ROWS|COST|
------------------------------------------
|0 |MERGE JOIN | |5 |78 |
|1 | TABLE SCAN|t2(IDX_c2)|5 |37 |
|2 | TABLE SCAN|t1 |3 |37 |
==========================================
Outputs & filters:
-------------------------------------
0 - output([t1.c1], [t2.c2]), filter(nil),
equal_conds([t1.c1 = t2.c2]), other_conds(nil)
1 - output([t2.c2]), filter(nil),
access([t2.c2]), partitions(p0),
is_index_back=false,
range_key([t2.c2], [t2.c1]), range(2,MAX ; MAX,MAX),
range_cond([t2.c2 > 2])
2 - output([t1.c1]), filter(nil),
access([t1.c1]), partitions(p0),
is_index_back=false,
range_key([t1.c1]), range(2 ; MAX),
range_cond([t1.c1 > 2])
Elimination of tautologies and contradictions
You can eliminate tautologies and contradictions:
false and expr= Always Falsetrue or expr= Always True
As shown in the following example, for the WHERE 0 > 1 AND c1 = 3 condition, since 0 > 1 is a contradiction, the AND condition is always false. Therefore, the SQL query does not need to be executed and can be directly returned, thus accelerating the query.
obclient> EXPLAIN EXTENDED_NOADDR SELECT * FROM t1 WHERE 0 > 1 AND c1 = 3\G
*************************** 1. row ***************************
Query Plan:
===================================
|ID|OPERATOR |NAME|EST. ROWS|COST|
-----------------------------------
|0 |TABLE SCAN|t1 |0 |38 |
===================================
Outputs & filters:
-------------------------------------
0 - output([t1.c1], [t1.c2]), filter([0], [t1.c1 = 3]), startup_filter([0]),
access([t1.c1], [t1.c2]), partitions(p0),
is_index_back=false, filter_before_indexback[false,false],
range_key([t1.__pk_increment], [t1.__pk_cluster_id], [t1.__pk_partition_id]),
range(MAX,MAX,MAX ; MIN,MIN,MIN)always false
Non-SPJ rewriting
Elimination of redundant sorting
Elimination of redundant sorting involves removing unnecessary items from the ORDER BY clause to reduce sorting overheads. You can eliminate sorting in the following three scenarios:
The ORDER BY clause contains duplicate columns. In this case, you can eliminate duplicate columns and sort the deduplicated result.
obclient> SELECT * FROM t1 WHERE c2 = 5 ORDER BY c1, c1, c2, c3 ; <==> obclient> SELECT * FROM t1 WHERE c2 = 5 ORDER BY c1, c2, c3;The column for sorting contains a single-valued condition in the WHERE clause. In this case, you can eliminate the sorting on that column.
obclient> SELECT * FROM t1 WHERE c2 = 5 ORDER BY c1, c2, c3; <==> obclient> SELECT * FROM t1 WHERE c2 = 5 ORDER BY c1, c3;If the outer query has an ORDER BY clause without a LIMIT clause and is a set-based operation, you can eliminate the ORDER BY clause of the outer query. The result of the
UNIONoperation on two ordered sets is unordered. However, if the ORDER BY clause has a LIMIT clause, it specifies to retrieve the largest or smallest N records. In this case, you cannot eliminate the ORDER BY clause to avoid semantic errors.obclient> (SELECT c1,c2 FROM t1 ORDER BY c1) UNION (SELECT c3,c4 FROM t2 ORDER BY c3); <==> obclient> (SELECT c1,c2 FROM t1) UNION (SELECT c3,c4 FROM t2);
Pushdown of the LIMIT clause
Limit clause pushdown is the process of moving the LIMIT clause to a subquery. OceanBase Database now supports pushing down the LIMIT clause to views (example 1) or subqueries corresponding to UNION operations (example 2) without changing the semantics.
Example 1: Pushdown of the LIMIT clause to a view.
obclient> SELECT * FROM (SELECT * FROM t1 ORDER BY c1) a LIMIT 1;
<==>
obclient> SELECT * FROM (SELECT * FROM t1 ORDER BY c1 LIMIT 1) a LIMIT 1;
Example 2: Pushdown of the LIMIT clause to subqueries corresponding to UNION.
obclient> (SELECT c1,c2 FROM t1) UNION ALL (SELECT c3,c4 FROM t2) LIMIT 5;
<==>
obclient> (SELECT c1,c2 FROM t1 LIMIT 5) UNION ALL (SELECT c3,c4 FROM t2 limit 5) LIMIT 5;
Elimination of the DISTINCT operator
If the select item contains only constants, you can eliminate the DISTINCT operator and add the
LIMIT 1clause.obclient> SELECT DISTINCT 1,2 FROM t1 ; <==> obclient> SELECT 1,2 FROM t1 LIMIT 1; obclient> CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT); Query OK, 0 rows affected obclient> EXPLAIN EXTENDED_NOADDR SELECT DISTINCT 1,2 FROM t1\G *************************** 1. row *************************** Query Plan: =================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ----------------------------------- |0 |TABLE SCAN|t1 |1 |36 | =================================== Outputs & filters: ------------------------------------- 0 - output([1], [2]), filter(nil), access([t1.c1]), partitions(p0), limit(1), offset(nil), is_index_back=false, range_key([t1.c1]), range(MIN ; MAX)always trueIf the select item contains a column that ensures uniqueness, you can eliminate the DISTINCT operator. For example, in the following example,
(c1, c2)is the primary key and ensures the uniqueness ofc1,c2, andc3.obclient> CREATE TABLE t2(c1 INT, c2 INT, c3 INT, PRIMARY KEY(c1, c2)); Query OK, 0 rows affected obclient> SELECT DISTINCT c1, c2, c3 FROM t2; <==> obclient> SELECT c1, c2 c3 FROM t2; obclient> EXPLAIN SELECT DISTINCT c1, c2, c3 FROM t2\G *************************** 1. row *************************** Query Plan: =================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ----------------------------------- |0 |TABLE SCAN|t2 |1000 |455 | =================================== Outputs & filters: ------------------------------------- 0 - output([t2.c1], [t2.c2], [t2.c3]), filter(nil), access([t2.c1], [t2.c2], [t2.c3]), partitions(p0)
Rewriting of MIN/MAX
If the parameter of the
MINorMAXfunction is an index prefix column and does not contain aGROUP BYclause, you can convert thescalar aggregatefunction into an indexed scan that reads only one row, as shown in the following example:obclient> CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT, c3 INT, KEY IDX_c2_c3(c2,c3)); Query OK, 0 rows affected obclient> SELECT MIN(c2) FROM t1; <==> obclient> SELECT MIN(c2) FROM (SELECT c2 FROM t1 ORDER BY c2 LIMIT 1) AS t; obclient> EXPLAIN SELECT MIN(c2) FROM t1\G *************************** 1. row *************************** Query Plan: ================================================== |ID|OPERATOR |NAME |EST. ROWS|COST| -------------------------------------------------- |0 |SCALAR GROUP BY| |1 |37 | |1 | SUBPLAN SCAN |subquery_table|1 |37 | |2 | TABLE SCAN |t1(idx_c2_c3) |1 |36 | ================================================== Outputs & filters: ------------------------------------- 0 - output([T_FUN_MIN(subquery_table.c2)]), filter(nil), group(nil), agg_func([T_FUN_MIN(subquery_table.c2)]) 1 - output([subquery_table.c2]), filter(nil), access([subquery_table.c2]) 2 - output([t1.c2]), filter([(T_OP_IS_NOT, t1.c2, NULL, 0)]), access([t1.c2]), partitions(p0), limit(1), offset(nil)If the
SELECT MINorSELECT MAXstatement's parameter is a constant and contains aGROUP BYclause, you can replace theMINorMAXfunction with the constant to reduce the computation overheads of theMINorMAXfunction.obclient> SELECT MAX(1) FROM t1 GROUP BY c1; <==> obclient> SELECT 1 FROM t1 GROUP BY c1; obclient> EXPLAIN EXTENDED_NOADDR SELECT MAX(1) FROM t1 GROUP BY c1\G *************************** 1. row *************************** Query Plan: =================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ----------------------------------- |0 |TABLE SCAN|t1 |1000 |411 | =================================== Outputs & filters: ------------------------------------- 0 - output([1]), filter(nil), access([t1.c1]), partitions(p0), is_index_back=false, range_key([t1.c1]), range(MIN ; MAX)always trueIf the
SELECT MINorSELECT MAXstatement's parameter is a constant and does not contain aGROUP BYclause, you can rewrite it as shown in the following example to scan only one row during index access.obclient> SELECT MAX(1) FROM t1; <==> obclient> SELECT MAX(t.a) FROM (SELECT 1 AS a FROM t1 LIMIT 1) t; obclient> EXPLAIN EXTENDED_NOADDR SELECT MAX(1) FROM t1\G *************************** 1. row *************************** Query Plan: ================================================== |ID|OPERATOR |NAME |EST. ROWS|COST| -------------------------------------------------- |0 |SCALAR GROUP BY| |1 |37 | |1 | SUBPLAN SCAN |subquery_table|1 |37 | |2 | TABLE SCAN |t1 |1 |36 | ================================================== Outputs & filters: ------------------------------------- 0 - output([T_FUN_MAX(subquery_table.subquery_col_alias)]), filter(nil), group(nil), agg_func([T_FUN_MAX(subquery_table.subquery_col_alias)]) 1 - output([subquery_table.subquery_col_alias]), filter(nil), access([subquery_table.subquery_col_alias]) 2 - output([1]), filter(nil), access([t1.c1]), partitions(p0), limit(1), offset(nil), is_index_back=false, range_key([t1.c1]), range(MIN ; MAX)always true
