查詢優化器是關系型數據庫系統的核心模塊，是數據庫內核開發的重點和難點，也是衡量整個數據庫系統成熟度的“試金石”。為了幫助大家更好地理解 OceanBase 查詢優化器，我們撰寫了查詢改寫系列文章，帶大家更好地掌握查詢改寫的精髓，熟悉復雜 SQL 的等價性，寫出高效的 SQL。本文將重點和大家介紹半連接轉內連接，更多文章歡迎進入【OceanBase SQL 查詢改寫專題】?查看。
引言
查詢分析中經常使用子查詢語句，數據庫為了提高子查詢的執行性能，往往會把子查詢語句改寫成半連接（子查詢提升方法參見本系列第二篇：子查詢提升首篇）。
例如，我們需要查詢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_idFROM? ?playWHERE? play_time BETWEEN DATE'2022-08-01'?AND DATE'2022-08-02');Q2: SELECT movie_name FROM? ?movie LEFT SEMI JOIN? ?(SELECT movie_idFROM? ?playWHERE? 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_idFROM? ?playWHERE? 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 c1FROM? ?t2);?
Q5:
SELECT t1.c1
FROM? ?t1INNER JOIN (SELECT DISTINCT c1FROM? ?t2)t2ON 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會把滿足一定條件的半連接轉換成內連接，使優化器能夠嘗試更多的計劃，生成的查詢計劃可能更優。
