數(shù)據(jù)庫(kù)性能優(yōu)化之IN子查詢優(yōu)化
問題定義
為了獲取最近一年內(nèi)有訂單的用戶信息，可以使用以下的三種寫法去實(shí)現(xiàn)，它們?cè)谡Z(yǔ)義上是等價(jià)的。那它們的性能如何，適用場(chǎng)景是什么？這是本文討論的主題。
- 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.custkeyIN子查詢
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í)行子查詢語(yǔ)句，并得到結(jié)果集并去重，并將結(jié)果集存儲(chǔ)在臨時(shí)表中。
- 將主查詢中的值逐一與子查詢結(jié)果集中的值進(jìn)行比較，如果匹配成功，則返回該行數(shù)據(jù)。
- 在第二步的比較時(shí)。
- 可以將子查詢的結(jié)果集轉(zhuǎn)化為一個(gè)哈希表，然后對(duì)于主查詢中的每一行，都在哈希表中查找該行的值是否存在。
- 可以在上面建立一個(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)邏輯如下：
- 對(duì)于主查詢中的每一行，都執(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方式
為了保證語(yǔ)義一致性，使用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對(duì)比IN子查詢的執(zhí)行計(jì)劃，可以看到Join方式就是IN子查詢的執(zhí)行計(jì)劃的SQL化表達(dá)。
如果如果子查詢中的查詢列是唯一的，那么可以將其轉(zhuǎn)換為內(nèi)連接，從而獲得更好的性能。
數(shù)據(jù)庫(kù)中的IN子查詢優(yōu)化
事實(shí)上，MySQL和PostgreSQL都可以對(duì)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 <subquery2> using <auto_distinct_key> (o_custkey=customer.C_CUSTKEY)
-> Materialize with deduplication (cost=22471.48..22471.48 rows=19949)
-> Filter: (orders.O_ORDERDATE = <cache>((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 = <cache>((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ù)庫(kù)會(huì)將其轉(zhuǎn)換為內(nèi)連接。
譬如對(duì)于下面的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ù)庫(kù)中，使用IN或是EXISTS的寫法是等價(jià)的，數(shù)據(jù)庫(kù)總是可以根據(jù)索引和統(tǒng)計(jì)信息采用最優(yōu)的執(zhí)行計(jì)劃。
PawSQL中的IN子查詢優(yōu)化
PawSQL中會(huì)將IN子查詢重寫為EXISTS子查詢或是內(nèi)連接查詢，從而幫助索引推薦引擎推薦合適的索引，促使優(yōu)化器采用最優(yōu)的執(zhí)行計(jì)劃。
IN子查詢轉(zhuǎn)換為EXISTS
原SQL：
select *
from tpch.customer
where 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.customer
where 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ū)動(dòng)表時(shí), 索引PAW_IDX1072908633可以被用來(lái)進(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 <subquery2> using <auto_distinct_key> (o_custkey=customer.C_CUSTKEY)
-> Materialize with deduplication (cost=13874.51..13874.51 rows=66733)
-> Filter: (orders.O_ORDERDATE >= <cache>((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 <subquery2> using <auto_distinct_key> (o_custkey=customer.C_CUSTKEY)
-> Materialize with deduplication (cost=1150.65..1150.65 rows=3812)
-> Filter: (orders.O_ORDERDATE >= <cache>((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ū)動(dòng)表時(shí), 索引PAW_IDX0455857015可以被用來(lái)進(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ù)庫(kù)性能優(yōu)化的自動(dòng)化和智能化，支持MySQL，PostgreSQL，Opengauss等，提供的SQL優(yōu)化產(chǎn)品包括
- PawSQL Cloud，在線自動(dòng)化SQL優(yōu)化工具，支持SQL審查，智能查詢重寫、基于代價(jià)的索引推薦，適用于數(shù)據(jù)庫(kù)管理員及數(shù)據(jù)應(yīng)用開發(fā)人員。
- PawSQL Advisor，IntelliJ 插件, 適用于數(shù)據(jù)應(yīng)用開發(fā)人員，可以IDEA/DataGrip應(yīng)用市場(chǎng)通過名稱搜索“PawSQL Advisor”安裝。
- PawSQL Engine, 是PawSQL系列產(chǎn)品的后端優(yōu)化引擎，可以獨(dú)立安裝部署，并通過http/json的接口提供SQL優(yōu)化服務(wù)。PawSQL Engine以docker鏡像的方式提供部署安裝。
