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

OceanBase数据库星球 2022-09-21

255

查询优化器是关系型数据库系统的核心模块，是数据库内核开发的重点和难点，也是衡量整个数据库系统成熟度的“试金石”。为了帮助大家更好地理解 OceanBase 查询优化器，我们将撰写查询改写系列文章，带大家更好地掌握查询改写的精髓，熟悉复杂 SQL 的等价性，写出高效的 SQL。本文是 OceanBase 改写系列第十篇，将重点和大家介绍半连接转内连接，欢迎探讨～

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

例如，我们需要查询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_name
FROM   movie
WHERE  movie_id IN (SELECT movie_id
                    FROM   play
                    WHERE  play_time BETWEEN DATE'2022-08-01' 
                                      AND DATE'2022-08-02');


Q2:
SELECT movie_name
FROM   movie LEFT SEMI
JOIN   (
              SELECT movie_id
              FROM   play
              WHERE  play_time BETWEEN date'2022-08-01' 
                                AND    date'2022-08-02' )play
ON     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_name
FROM   movie INNER JOIN
JOIN   (
              SELECT DISTINCT movie_id
              FROM   play
              WHERE  play_time BETWEEN date'2022-08-01' 
                                AND    date'2022-08-02' )play
ON     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   t1
WHERE  c1 IN (SELECT c1
              FROM   t2); 
Q5:
SELECT t1.c1
FROM   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，导致执行结果不正确。