[RFC] Rewrite in subquery to inner join with aggregation

[jackwener]

Enhancement

Related issue: #13709

Some rewriting method applied in plan building phase:

• Rewrite in subquery to inner join with aggregation [hard]

Example

• Scalar Subquery
• Subquery Within the IN Clause
• Subquery in the Clause NOT IN
• Correlated Subqueries in EXISTS and in NOT EXISTS

Scalar Subquery

SELECT name, cost
FROM product
WHERE id=(SELECT product_id
  FROM sale
    WHERE price=2000
    AND product_id=product.id
  );

rewrite to

SELECT p.name, p.cost
FROM product p
JOIN sale s ON p.id=s.product_id
WHERE s.price=2000;

Subquery Within the IN Clause

SELECT name, cost
FROM product
WHERE id IN (SELECT product_id FROM sale);

rewrite to

SELECT DISTINCT p.name, p.cost
FROM product p
JOIN sale s ON s.product_id=p.id;

Subquery in the Clause NOT IN

SELECT name, cost
FROM product
WHERE id NOT IN (SELECT product_id FROM sale);

rewrite to

SELECT DISTINCT p.name, p.cost
FROM product p
LEFT JOIN sale s ON s.product_id=p.id
WHERE s.product_id IS NULL;

Correlated Subqueries in EXISTS and in NOT EXISTS

SELECT name, cost, city
FROM product 
WHERE NOT EXISTS ( SELECT id 
  FROM sale WHERE year=2020 AND product_id=product.id );

rewrite to

SELECT p.name, p.cost, p.city FROM product p
LEFT JOIN  sale s ON s.product_id=p.id
WHERE s.year!=2020 OR s.year IS NULL;

[ti-chi-bot]

@jackwener: The label(s) sig-planner cannot be applied. These labels are supported: challenge-program, compatibility-breaker, first-time-contributor, contribution, require-LGT3, good first issue, correctness, duplicate, proposal, security, needs-more-info, needs-cherry-pick-3.0, needs-cherry-pick-3.1, needs-cherry-pick-4.0, needs-cherry-pick-5.0, needs-cherry-pick-5.1, needs-cherry-pick-5.2, affects-4.0, affects-5.0, affects-5.1, affects-5.2, backport-4.0.14, backport-4.0.15, backport-5.0.3, backport-5.0.4, backport-5.1.0, backport-5.1.1, backport-5.1.2.

In response to [this](https://github.com/pingcap/tidb/issues/29046#issuecomment-950325277): >/label sig-planner Instructions for interacting with me using PR comments are available [here](https://prow.tidb.io/command-help). If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.

[jackwener]

/label challenge-program /label sig/planner

[ti-chi-bot]

@jackwener: The label(s) sig/planner cannot be applied. These labels are supported: challenge-program, compatibility-breaker, first-time-contributor, contribution, require-LGT3, good first issue, correctness, duplicate, proposal, security, needs-more-info, needs-cherry-pick-3.0, needs-cherry-pick-3.1, needs-cherry-pick-4.0, needs-cherry-pick-5.0, needs-cherry-pick-5.1, needs-cherry-pick-5.2, affects-4.0, affects-5.0, affects-5.1, affects-5.2, backport-4.0.14, backport-4.0.15, backport-5.0.3, backport-5.0.4, backport-5.1.0, backport-5.1.1, backport-5.1.2.

In response to [this](https://github.com/pingcap/tidb/issues/29046#issuecomment-950325836): >/label challenge-program >/label sig/planner > > > Instructions for interacting with me using PR comments are available [here](https://prow.tidb.io/command-help). If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.

[ti-chi-bot]

@jackwener: The label(s) sig-planner cannot be applied. These labels are supported: challenge-program, compatibility-breaker, first-time-contributor, contribution, require-LGT3, good first issue, correctness, duplicate, proposal, security, needs-more-info, needs-cherry-pick-3.0, needs-cherry-pick-3.1, needs-cherry-pick-4.0, needs-cherry-pick-5.0, needs-cherry-pick-5.1, needs-cherry-pick-5.2, affects-4.0, affects-5.0, affects-5.1, affects-5.2, backport-4.0.14, backport-4.0.15, backport-5.0.3, backport-5.0.4, backport-5.1.0, backport-5.1.1, backport-5.1.2.

In response to [this](https://github.com/pingcap/tidb/issues/29046#issuecomment-950325277): >/label sig-planner Instructions for interacting with me using PR comments are available [here](https://prow.tidb.io/command-help). If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.

[jackwener]

/label sig/planner

[ti-chi-bot]

@jackwener: The label(s) sig/planner cannot be applied. These labels are supported: challenge-program, compatibility-breaker, first-time-contributor, contribution, require-LGT3, good first issue, correctness, duplicate, proposal, security, needs-more-info, needs-cherry-pick-3.0, needs-cherry-pick-3.1, needs-cherry-pick-4.0, needs-cherry-pick-5.0, needs-cherry-pick-5.1, needs-cherry-pick-5.2, affects-4.0, affects-5.0, affects-5.1, affects-5.2, backport-4.0.14, backport-4.0.15, backport-5.0.3, backport-5.0.4, backport-5.1.0, backport-5.1.1, backport-5.1.2.

In response to [this](https://github.com/pingcap/tidb/issues/29046#issuecomment-950325883): >/label sig/planner Instructions for interacting with me using PR comments are available [here](https://prow.tidb.io/command-help). If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.

[jackwener]

I have some questions. Why is in plan building phase in the task description?

builder.Build(ctx, node) is used for both plan.core and cascades plan.

Perhaps this task works on both plans and not just for cascades plan?

[jackwener]

What's more, if it's implemented in planBuilder, subquery will be handle both in planBuilder and optimizer in plan.core