問題定義

為了獲取最近一年內(nèi)有訂單的用戶信息，可以使用以下的三種寫法去實(shí)現(xiàn)，它們在語義上是等價(jià)的。那它們的性能如何，適用場景是什么？這是本文討論的主題。

Query1 - IN子查詢(= ANY)

select * from customer where c_custkey in (select o_custkey from orders where O_ORDERDATE>=current_date - interval 1 year)

Query2 - EXISTS子查詢

select * from customer where exists (select * from orders where c_custkey = o_custkey and O_ORDERDATE>=current_date - interval 1 year)

Query3 - JOIN方式

select c.* from customer c join (select distinct o_custkey from orders where O_ORDERDATE>=current_date - interval 1 year) o where o.o_custkey = c.custkey

IN子查詢

IN子查詢并不一定是非相關(guān)子查詢，但是為了討論方便，本文所述的IN子查詢?yōu)榉窍嚓P(guān)子查詢。

Query1- IN子查詢(= ANY)

【資料圖】

select * from customer where c_custkey in (select o_custkey from orders where O_ORDERDATE>=current_date - interval 1 year)

IN子查詢的偽代碼實(shí)現(xiàn)邏輯：執(zhí)行子查詢語句，并得到結(jié)果集并去重，并將結(jié)果集存儲在臨時(shí)表中。將主查詢中的值逐一與子查詢結(jié)果集中的值進(jìn)行比較，如果匹配成功，則返回該行數(shù)據(jù)。在第二步的比較時(shí)?？梢詫⒆硬樵兊慕Y(jié)果集轉(zhuǎn)化為一個(gè)哈希表，然后對于主查詢中的每一行，都在哈希表中查找該行的值是否存在?？梢栽谏厦娼⒁粋€(gè)唯一性索引，通過此索引和外表進(jìn)行關(guān)聯(lián)。不論適用哪一種方式，它的實(shí)際復(fù)雜度都為O(1)時(shí)間復(fù)雜度

它的時(shí)間復(fù)雜度為O(max(m,n)) + nlogn， 其中，m是外表的記錄數(shù)，n為子查詢的記錄數(shù)。

可以看到，如果子查詢的記錄數(shù)比較大時(shí)，其時(shí)間復(fù)雜度較大，性能較差。

EXISTS子查詢

Query2- EXISTS子查詢

select * from customer where exists (select * from orders where c_custkey = o_custkey and O_ORDERDATE>=current_date - interval 1 year)

實(shí)現(xiàn)邏輯如下：對于主查詢中的每一行，都執(zhí)行一次子查詢。如果子查詢返回的結(jié)果集不為空，則保留該行數(shù)據(jù)。時(shí)間復(fù)雜度

因此它的時(shí)間復(fù)雜度為O(m*n), 其中m為外表的記錄數(shù)，n為子查詢的訪問的記錄數(shù)。

如果子查詢中的orders沒有索引，則n為orders表的行數(shù)。如果orders上有篩選率比較大的索引，則n為索引所篩選出的記錄數(shù)。

可以看出，如果EXISTS的子查詢中有篩選率非常高的索引，使用EXISTS子查詢的性能比較好。

Join方式

為了保證語義一致性，使用join方式需要先進(jìn)行去重操作。

Query3 - JOIN方式：

select c.* from customer c join (select distinct o_custkey from orders where O_ORDERDATE>=current_date - interval 1 year) o where o.o_custkey = c.custkey

對比IN子查詢的執(zhí)行計(jì)劃，可以看到Join方式就是IN子查詢的執(zhí)行計(jì)劃的SQL化表達(dá)。

如果如果子查詢中的查詢列是唯一的，那么可以將其轉(zhuǎn)換為內(nèi)連接，從而獲得更好的性能。

數(shù)據(jù)庫中的IN子查詢優(yōu)化

事實(shí)上，MySQL和PostgreSQL都可以對IN和EXISTS采取最優(yōu)的執(zhí)行計(jì)劃。

如果沒有O_ORDERDATE上的索引，Query1和Query2在MySQL上的執(zhí)行計(jì)劃都是采用IN子查詢的偽代碼實(shí)現(xiàn)邏輯：

-> Nested loop inner join  (cost=19847117.66 rows=198449671)   -> Table scan on customer  (cost=1155.80 rows=9948)   -> Single-row index lookup on  using  (o_custkey=customer.C_CUSTKEY)       -> Materialize with deduplication  (cost=22471.48..22471.48 rows=19949)           -> Filter: (orders.O_ORDERDATE = ((curdate() - interval 1 year)))  (cost=20476.61 rows=19949)               -> Table scan on orders  (cost=20476.61 rows=199487)

如果在O_ORDERDATE建立一個(gè)索引，那么它們的執(zhí)行計(jì)劃都是采用EXISTS子查詢的偽代碼實(shí)現(xiàn)邏輯：

-> Nested loop semijoin  (cost=22777.29 rows=5705)   -> Table scan on customer  (cost=1155.80 rows=9948)   -> Filter: (orders.O_ORDERDATE = ((curdate() - interval 1 year)))  (cost=0.92 rows=1)       -> Index lookup on orders using o_idx_key (O_CUSTKEY=customer.C_CUSTKEY)  (cost=0.92 rows=6)

如果子查詢中的查詢列是唯一的，那么數(shù)據(jù)庫會將其轉(zhuǎn)換為內(nèi)連接。

譬如對于下面的SQL。

select * from orders where o_custkey in (select c_custkey from customer where c_phone like "139%")

MySQL的執(zhí)行計(jì)劃是這樣的（PostgreSQL也是類似的）：

-> Nested loop inner join  (cost=3541.61 rows=6313)   -> Filter: (customer.C_PHONE like "139%")  (cost=1148.89 rows=1099)       -> Table scan on customer  (cost=1148.89 rows=9888)   -> Index lookup on orders using idx_orders_ckey (O_CUSTKEY=customer.C_CUSTKEY)  (cost=1.60 rows=6)

可以看出，在MySQL和PostgreSQL數(shù)據(jù)庫中，使用IN或是EXISTS的寫法是等價(jià)的，數(shù)據(jù)庫總是可以根據(jù)索引和統(tǒng)計(jì)信息采用最優(yōu)的執(zhí)行計(jì)劃。

PawSQL中的IN子查詢優(yōu)化

PawSQL中會將IN子查詢重寫為EXISTS子查詢或是內(nèi)連接查詢，從而幫助索引推薦引擎推薦合適的索引，促使優(yōu)化器采用最優(yōu)的執(zhí)行計(jì)劃。

IN子查詢轉(zhuǎn)換為EXISTS

原SQL：

select *from tpch.customerwhere customer.c_custkey in (          select orders.o_custkey          from tpch.orders          where orders.O_ORDERDATE >= current_date - interval "1" YEAR)

應(yīng)用重寫優(yōu)化，轉(zhuǎn)換為：

select /*QB_1*/ *from tpch.customerwhere exists (select /*QB_2*/ orders.o_custkey            from tpch.orders            where orders.O_ORDERDATE >= current_date - interval "1" YEAR        and orders.o_custkey = customer.c_custkey)

基于轉(zhuǎn)換后的SQL，推薦索引：

CREATE INDEX PAW_IDX1072908633 ON tpch.ORDERS(O_ORDERDATE,O_CUSTKEY);-- 當(dāng)QB_2中引用的表ORDERS作為驅(qū)動表時(shí), 索引PAW_IDX1072908633可以被用來進(jìn)行索引范圍查找,過濾條件為(orders.O_ORDERDATE >= current_date - interval "1" YEAR); 該索引是個(gè)覆蓋索引，可以避免回表.

性能驗(yàn)證：

執(zhí)行計(jì)劃（優(yōu)化前）

-> Nested loop inner join  (cost=65987720.69 rows=659855821) -> Table scan on customer  (cost=1149.80 rows=9888) -> Single-row index lookup on  using  (o_custkey=customer.C_CUSTKEY)     -> Materialize with deduplication  (cost=13874.51..13874.51 rows=66733)         -> Filter: (orders.O_ORDERDATE >= ((curdate() - interval "1" year)))  (cost=7201.21 rows=66733)             -> Table scan on orders  (cost=7201.21 rows=200219)

執(zhí)行計(jì)劃（優(yōu)化后）

-> Nested loop inner join  (cost=3771444.20 rows=37693056) -> Table scan on customer  (cost=1149.80 rows=9888) -> Single-row index lookup on  using  (o_custkey=customer.C_CUSTKEY)     -> Materialize with deduplication  (cost=1150.65..1150.65 rows=3812)         -> Filter: (orders.O_ORDERDATE >= ((curdate() - interval "1" year)))  (cost=769.45 rows=3812)             -> Covering index range scan on orders using PAW_IDX1072908633 over ("2022-03-28" <= O_ORDERDATE)  (cost=769.45 rows=3812)

本次優(yōu)化實(shí)施后，預(yù)計(jì)本SQL的性能將提升 1648.67%。

IN子查詢轉(zhuǎn)換為內(nèi)連接

原SQL，c_custkey是customer表的主鍵。

select *  from tpch.orders  where orders.o_custkey in (             select customer.c_custkey             from tpch.customer)

應(yīng)用重寫優(yōu)化，轉(zhuǎn)化為內(nèi)連接。

select orders.*  from tpch.orders, tpch.customer  where customer.c_custkey = orders.o_custkey

基于轉(zhuǎn)換后的SQL，推薦索引。

CREATE INDEX PAW_IDX0455857015 ON tpch.ORDERS(O_CUSTKEY,O_CLERK);  -- 當(dāng)ORDERS作為被驅(qū)動表時(shí), 索引PAW_IDX0455857015可以被用來進(jìn)行索引查找, 過濾條件為(customer.c_custkey = orders.o_custkey).

性能驗(yàn)證。

執(zhí)行計(jì)劃（優(yōu)化前）

-> Nested loop inner join  (cost=240790.71 rows=200219) -> Table scan on orders  (cost=20549.81 rows=200219) -> Single-row covering index lookup on customer using key_idx (C_CUSTKEY=orders.O_CUSTKEY)  (cost=1.00 rows=1)

執(zhí)行計(jì)劃（優(yōu)化后）

-> Nested loop inner join  (cost=21289.23 rows=53135) -> Index scan on customer using key_idx  (cost=1149.80 rows=9888) -> Index lookup on orders using PAW_IDX0455857015 (O_CUSTKEY=customer.C_CUSTKEY)  (cost=1.50 rows=5)

本次優(yōu)化實(shí)施后，預(yù)計(jì)本SQL的性能將提升 1064.60%

關(guān)于PawSQL

PawSQL專注數(shù)據(jù)庫性能優(yōu)化的自動化和智能化，支持MySQL，PostgreSQL，Opengauss等，提供的SQL優(yōu)化產(chǎn)品包括

PawSQL Cloud，在線自動化SQL優(yōu)化工具，支持SQL審查，智能查詢重寫、基于代價(jià)的索引推薦，適用于數(shù)據(jù)庫管理員及數(shù)據(jù)應(yīng)用開發(fā)人員。PawSQL Advisor，IntelliJ 插件, 適用于數(shù)據(jù)應(yīng)用開發(fā)人員，可以IDEA/DataGrip應(yīng)用市場通過名稱搜索“PawSQL Advisor”安裝。PawSQL Engine, 是PawSQL系列產(chǎn)品的后端優(yōu)化引擎，可以獨(dú)立安裝部署，并通過http/json的接口提供SQL優(yōu)化服務(wù)。PawSQL Engine以docker鏡像的方式提供部署安裝。

關(guān)鍵詞：