SQL 改写系列十：半连接转内连接

2022 年 9 月 16 日
浙江
本文字数：3041 字
阅读完需：约 10 分钟

引言

查询分析中经常使用子查询语句，数据库为了提高子查询的执行性能，往往会把子查询语句改写成半连接（子查询提升方法参见本系列第二篇：子查询提升首篇）。

例如，我们需要查询 2022-08-01 到 2022-08-02 之间已排片的电影，可以通过 IN 子查询检查电影是否在排片期内。查询 SQL 如 Q1 所示。

-- 影片表MOVIE(movie_id primary key， movie_name, release_date)-- 排片表PLAY(play_id, movie_id, play_time, price, seats)
Q1:SELECT movie_nameFROM   movieWHERE  movie_id IN (SELECT movie_id                    FROM   play                    WHERE  play_time BETWEEN DATE'2022-08-01'                                       AND DATE'2022-08-02');                    Q2:SELECT movie_nameFROM   movie LEFT SEMIJOIN   (              SELECT movie_id              FROM   play              WHERE  play_time BETWEEN date'2022-08-01'                                 AND    date'2022-08-02' )playON     movie.movie_id = play.movie_id;

复制代码

对于查询 Q1，OceanBase 会做子查询提升改写，改写成等价的查询 Q2，使用半连接来计算子查询。对于新的查询，优化器可以选择 hash left semi join、hash right semi join、merge left semi join、merge right semi join、nested loop left semi join 五种连接算法执行。下图展示了其中一种执行计划。

Query Plan: ==========================================|ID|OPERATOR      |NAME |EST. ROWS|COST  |------------------------------------------|0 |HASH SEMI JOIN|     |30       |910000||1 | TABLE SCAN   |MOVIE|1000000  |460000||2 | SUBPLAN SCAN |PLAY |30       |46    ||3 |  TABLE SCAN  |PLAY |30       |46    |==========================================

复制代码

考虑一种业务场景：movie 表的数据量达 100w，2022-08-01 到 2022-08-02 之间已排片的电影约 30 部。上面五种连接算法都需要扫描 movie 表的全部数据，扫描成本比较高。而我们知道 movie 表的主键为 movie_id，如果我们能够先查询出 2022-08-01 到 2022-08-02 之间已排片的 movie_id，再去 movie 表查询 movie_name，就能够使用 movie 表的主键索引，执行 30 次主键索引扫描即可完成查询。

为了能够按照最优计划执行 Q1 查询，我们需要以 play 表作为驱动表，并且使用 index nested loop join 的算法，把 movie_id 的连接条件转换为 movie 表的索引扫描条件。计划如下所示。

Query Plan: =====================================================|ID|OPERATOR                   |NAME |EST. ROWS|COST|-----------------------------------------------------|0 |NESTED LOOP RIGHT SEMI JOIN|     |30       |91  ||1 | SUBPLAN SCAN              |PLAY |30       |96  ||2 |  TABLE SCAN               |PLAY |30       |96  ||3 | TABLE GET                 |MOVIE|1        |46  |=====================================================

复制代码

但我们知道，数据库没有 NESTED LOOP RIGHT SEMI JOIN 的算法实现，那我们要怎样改写这条 SQL，使数据库能够支持这种优化计划呢？为此，OceanBase 引入了一个改写规则：半连接转内连接，将满足一定条件的半连接查询转换为内连接查询，优化器就可以针对上述场景生成最优的 index nested loop join 计划。

半连接转内连接

介绍半连接转内连接规则前，我们先了解下半连接的执行逻辑。还是以 Q1 为例进行说明，从 movie 表中读取一行数据，然后从 play 表内查找指定 movie_id 的数据，如果存在，则执行数据，否则不输出。从描述中我们可以知道，对于 movie 表中给定的一行数据，无论 play 表存在多少条数据与指定的 movie_id 相同，查询都只输出一行数据。

而内连接对于符合条件的每一条数据都会输出，也就是说，如果半连接直接转内连接，执行结果可能会重复输出多次。为了保证改写不改变查询语义，我们需要对 play 的 movie_id 去重，保证 movie 表的每行数据在 play 表中只匹配一行数据，改写后的查询如 Q3 所示。

Q3:SELECT movie_nameFROM   movie INNER JOINJOIN   (              SELECT DISTINCT movie_id              FROM   play              WHERE  play_time BETWEEN date'2022-08-01'                                 AND    date'2022-08-02' )playON     movie.movie_id = play.movie_id;

复制代码

对于新的查询 Q3，优化器可以尝试 movie hash join play、play hash join movie、movie merge join play、 play merge join movie、movie nested loop join play、play nested loop join movie 这六种连接算法执行，比原来多了一种。此时，优化器可以生成之前描述的最优计划。

================================================|ID|OPERATOR              |NAME |EST. ROWS|COST|------------------------------------------------|0 |NESTED-LOOP JOIN      |     |30       |46  ||1 | SUBPLAN SCAN         |PLAY |30       |46  ||2 |  MERGE DISTINCT      |     |30       |46  ||3 |   SORT               |     |30       |46  ||4 |    TABLE SCAN        |PLAY |30       |46  ||5 | TABLE GET            |MOVIE|1        |7   |================================================

复制代码

注意到改写之后的查询比原来的查询多了一次去重计算，Q3 查询并不是在所有场景下都比 Q2 查询更优，因此，OceanBase 的半连接转内连接改写是一种基于代价的改写，即优化器会对比改写前后最优计划的代价，如果代价降低了，才会应用改写，否则不会改写查询。

优化点

上文我们介绍了半连接转内连接主要是增加去重计算来保证语义的正确性，也正因为增加了去重计算，改写之后的查询并不总是比改写之前的查询更优。

我们可以思考一下，是否所有场景都需要加去重计算？答案是否定的，在有些场景下，我们可以把半连接直接转成内连接，例如：play 表的 movie_id 本身就有唯一约束，或者 play 表只有一行数据满足条件。在这些场景下，我们可以不添加去重计算，这也意味着改写之后的查询总是比改写之前的查询更优，不需要额外比较代价。

改写陷阱

在之前的介绍中，我们没有说明数据类型对改写规则的影响，实际上半连接转内连接对数据类型是有要求的。通过一个例子说明，对于查询 Q4，如果需要改写成内连接，改写的 SQL 如 Q5 所示。

create table t1(c1 int);insert into t1 values(0);create table t2(c1 varchar(20));insert into t2 values('0.0');insert into t2 values('0.1');
Q4:SELECT *FROM   t1WHERE  c1 IN (SELECT c1              FROM   t2); Q5:SELECT t1.c1FROM   t1       INNER JOIN (SELECT DISTINCT c1                   FROM   t2)t2               ON t1.c1 = t2.c1;

复制代码

上面的改写正确吗？对于 Q4，结果是一行数据：0，对于 Q5，结果是两行数据：0, 0。为什么呢？在对 t2 表的 c1 列去重时，使用的是 varchar(20)类型，'0.0'与'0.1'属于不同的数据，不会发生去重操作，与 t1 表连接时需要把 varchar(20)类型的数据转换成 int 类型比较，此时'0.0'与'0.1'转换成了 0 与 0，导致执行结果不正确。

为了避免数据类型影响改写的正确性，我们需要在改写时，对数据类型做适当的处理，你可以思考一下怎样是正确的改写查询。

总结

本文主要介绍 OceanBase 的半连接转内连接改写，以及这个改写的优化点、容易被忽略的错误。OceanBase 会把满足一定条件的半连接转换成内连接，使优化器能够尝试更多的计划，生成的查询计划可能更优。

发布于: 刚刚阅读数: 3

OceanBase 数据库

关注

企业级原生分布式数据库 2020.05.06 加入

github：https://github.com/oceanbase/oceanbase 欢迎大家

发布

暂无评论

创作场景

SQL 改写系列十：半连接转内连接

引言

半连接转内连接

优化点

改写陷阱

总结

OceanBase 数据库

评论