Decorrelation of Correlated Subquery

Subquery related optimizations describes how TiDB handles subqueries when there are no correlated columns. Because decorrelation of correlated subquery is complex, this article introduces some simple scenarios and the scope to which the optimization rule applies.

Introduction

Take select * from t1 where t1.a < (select sum(t2.a) from t2 where t2.b = t1.b) as an example. The subquery t1.a < (select sum(t2.a) from t2 where t2.b = t1.b) here refers to the correlated column in the query condition t2.b=t1.b, this condition happens to be an equivalent condition, so the query can be rewritten as select t1.* from t1, (select b, sum(a) sum_a from t2 group by b) t2 where t1.b = t2.b and t1.a < t2.sum_a;. In this way, a correlated subquery is rewritten into JOIN.

The reason why TiDB needs to do this rewriting is that the correlated subquery is bound to its external query result every time the subquery is executed. In the above example, if t1.a has 10 million values, this subquery would repeat 10 million times, because the condition t2.b=t1.b varies with the value of t1.a. When the correlation is lifted somehow, this subquery would execute only once.

Restrictions

The disadvantage of this rewriting is that when the correlation is not lifted, the optimizer can use the index on the correlated column. That is, although this subquery may repeat many times, the index can be used to filter data each time. After using the rewriting rule, the position of the correlated column usually changes. Although the subquery is only executed once, the single execution time would be longer than that without decorrelation.

Therefore, when there are few external values, do not perform decorrelation, which might bring better execution performance. In this case, you can disable this optimization by using the NO_DECORRELATE optimizer hint or by disabling the “subquery decorrelation” optimization rule in the blocklist of optimization rules and expression pushdown. In most cases, it is recommended to use the optimizer hint along with SQL Plan Management to disable the decorrelation.

Example

  1. create table t1(a int, b int);
  2. create table t2(a int, b int, index idx(b));
  3. explain select * from t1 where t1.a < (select sum(t2.a) from t2 where t2.b = t1.b);
  1. +----------------------------------+----------+-----------+---------------+-----------------------------------------------------------------------------------------+
  2. | id                               | estRows  | task      | access object | operator info                                                                           |
  3. +----------------------------------+----------+-----------+---------------+-----------------------------------------------------------------------------------------+
  4. | HashJoin_11                      | 9990.00  | root      |               | inner join, equal:[eq(test.t1.b, test.t2.b)], other cond:lt(cast(test.t1.a), Column#7)  |
  5. | ├─HashAgg_23(Build)              | 7992.00  | root      |               | group by:test.t2.b, funcs:sum(Column#8)->Column#7, funcs:firstrow(test.t2.b)->test.t2.b |
  6. | │ └─TableReader_24               | 7992.00  | root      |               | data:HashAgg_16                                                                         |
  7. | │   └─HashAgg_16                 | 7992.00  | cop[tikv] |               | group by:test.t2.b, funcs:sum(test.t2.a)->Column#8                                      |
  8. | │     └─Selection_22             | 9990.00  | cop[tikv] |               | not(isnull(test.t2.b))                                                                  |
  9. | │       └─TableFullScan_21       | 10000.00 | cop[tikv] | table:t2      | keep order:false, stats:pseudo                                                          |
  10. | └─TableReader_15(Probe)          | 9990.00  | root      |               | data:Selection_14                                                                       |
  11. |   └─Selection_14                 | 9990.00  | cop[tikv] |               | not(isnull(test.t1.b))                                                                  |
  12. |     └─TableFullScan_13           | 10000.00 | cop[tikv] | table:t1      | keep order:false, stats:pseudo                                                          |
  13. +----------------------------------+----------+-----------+---------------+-----------------------------------------------------------------------------------------+

The above is an example where the optimization takes effect. HashJoin_11 is a normal inner join.

Then, you can use the NO_DECORRELATE optimizer hint to tell the optimizer not to perform decorrelation for the subquery:

  1. explain select * from t1 where t1.a < (select /*+ NO_DECORRELATE() */ sum(t2.a) from t2 where t2.b = t1.b);
  1. +------------------------------------------+-----------+-----------+------------------------+--------------------------------------------------------------------------------------+
  2. | id                                       | estRows   | task      | access object          | operator info                                                                        |
  3. +------------------------------------------+-----------+-----------+------------------------+--------------------------------------------------------------------------------------+
  4. | Projection_10                            | 10000.00  | root      |                        | test.t1.a, test.t1.b                                                                 |
  5. | └─Apply_12                               | 10000.00  | root      |                        | CARTESIAN inner join, other cond:lt(cast(test.t1.a, decimal(10,0) BINARY), Column#7) |
  6. |   ├─TableReader_14(Build)                | 10000.00  | root      |                        | data:TableFullScan_13                                                                |
  7. |   │ └─TableFullScan_13                   | 10000.00  | cop[tikv] | table:t1               | keep order:false, stats:pseudo                                                       |
  8. |   └─MaxOneRow_15(Probe)                  | 10000.00  | root      |                        |                                                                                      |
  9. |     └─StreamAgg_20                       | 10000.00  | root      |                        | funcs:sum(Column#14)->Column#7                                                       |
  10. |       └─Projection_45                    | 100000.00 | root      |                        | cast(test.t2.a, decimal(10,0) BINARY)->Column#14                                     |
  11. |         └─IndexLookUp_44                 | 100000.00 | root      |                        |                                                                                      |
  12. |           ├─IndexRangeScan_42(Build)     | 100000.00 | cop[tikv] | table:t2, index:idx(b) | range: decided by [eq(test.t2.b, test.t1.b)], keep order:false, stats:pseudo         |
  13. |           └─TableRowIDScan_43(Probe)     | 100000.00 | cop[tikv] | table:t2               | keep order:false, stats:pseudo                                                       |
  14. +------------------------------------------+-----------+-----------+------------------------+--------------------------------------------------------------------------------------+

Disabling the decorrelation rule can also achieve the same effect:

  1. insert into mysql.opt_rule_blacklist values("decorrelate");
  2. admin reload opt_rule_blacklist;
  3. explain select * from t1 where t1.a < (select sum(t2.a) from t2 where t2.b = t1.b);
  1. +------------------------------------------+-----------+-----------+------------------------+--------------------------------------------------------------------------------------+
  2. | id                                       | estRows   | task      | access object          | operator info                                                                        |
  3. +------------------------------------------+-----------+-----------+------------------------+--------------------------------------------------------------------------------------+
  4. | Projection_10                            | 10000.00  | root      |                        | test.t1.a, test.t1.b                                                                 |
  5. | └─Apply_12                               | 10000.00  | root      |                        | CARTESIAN inner join, other cond:lt(cast(test.t1.a, decimal(10,0) BINARY), Column#7) |
  6. |   ├─TableReader_14(Build)                | 10000.00  | root      |                        | data:TableFullScan_13                                                                |
  7. |   │ └─TableFullScan_13                   | 10000.00  | cop[tikv] | table:t1               | keep order:false, stats:pseudo                                                       |
  8. |   └─MaxOneRow_15(Probe)                  | 10000.00  | root      |                        |                                                                                      |
  9. |     └─StreamAgg_20                       | 10000.00  | root      |                        | funcs:sum(Column#14)->Column#7                                                       |
  10. |       └─Projection_45                    | 100000.00 | root      |                        | cast(test.t2.a, decimal(10,0) BINARY)->Column#14                                     |
  11. |         └─IndexLookUp_44                 | 100000.00 | root      |                        |                                                                                      |
  12. |           ├─IndexRangeScan_42(Build)     | 100000.00 | cop[tikv] | table:t2, index:idx(b) | range: decided by [eq(test.t2.b, test.t1.b)], keep order:false, stats:pseudo         |
  13. |           └─TableRowIDScan_43(Probe)     | 100000.00 | cop[tikv] | table:t2               | keep order:false, stats:pseudo                                                       |
  14. +------------------------------------------+-----------+-----------+------------------------+--------------------------------------------------------------------------------------+

After disabling the subquery decorrelation rule, you can see range: decided by [eq(test.t2.b, test.t1.b)] in operator info of IndexRangeScan_42(Build). It means that the decorrelation of correlated subquery is not performed and TiDB uses the index range query.