數據庫性能優化之IN子查詢優化
作者：PawSQL
PawSQL Cloud，在線自動化SQL優化工具，支持SQL審查，智能查詢重寫、基于代價的索引推薦，適用于數據庫管理員及數據應用開發人員。
問題定義
為了獲取最近一年內有訂單的用戶信息，可以使用以下的三種寫法去實現，它們在語義上是等價的。那它們的性能如何，適用場景是什么？這是本文討論的主題。
- 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子查詢并不一定是非相關子查詢，但是為了討論方便，本文所述的IN子查詢為非相關子查詢。
Query1 - IN子查詢(= ANY)
select * from customer where c_custkey in (select o_custkey from orders where O_ORDERDATE>=current_date - interval 1 year)IN子查詢的偽代碼實現邏輯：
- 執行子查詢語句，并得到結果集并去重，并將結果集存儲在臨時表中。
- 將主查詢中的值逐一與子查詢結果集中的值進行比較，如果匹配成功，則返回該行數據。
- 在第二步的比較時。
- 可以將子查詢的結果集轉化為一個哈希表，然后對于主查詢中的每一行，都在哈希表中查找該行的值是否存在。
- 可以在上面建立一個唯一性索引，通過此索引和外表進行關聯。不論適用哪一種方式，它的實際復雜度都為O(1)
時間復雜度
它的時間復雜度為O(max(m,n)) + nlogn， 其中，m是外表的記錄數，n為子查詢的記錄數。
可以看到，如果子查詢的記錄數比較大時，其時間復雜度較大，性能較差。
EXISTS子查詢
Query2 - EXISTS子查詢
select * from customer where exists (select * from orders where c_custkey = o_custkey and O_ORDERDATE>=current_date - interval 1 year)實現邏輯如下：
- 對于主查詢中的每一行，都執行一次子查詢。
- 如果子查詢返回的結果集不為空，則保留該行數據。
時間復雜度
因此它的時間復雜度為O(m*n), 其中m為外表的記錄數，n為子查詢的訪問的記錄數。
- 如果子查詢中的orders沒有索引，則n為orders表的行數。
- 如果orders上有篩選率比較大的索引，則n為索引所篩選出的記錄數。
可以看出，如果EXISTS的子查詢中有篩選率非常高的索引，使用EXISTS子查詢的性能比較好。
Join方式
為了保證語義一致性，使用join方式需要先進行去重操作。
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子查詢的執行計劃，可以看到Join方式就是IN子查詢的執行計劃的SQL化表達。
如果如果子查詢中的查詢列是唯一的，那么可以將其轉換為內連接，從而獲得更好的性能。
數據庫中的IN子查詢優化
事實上，MySQL和PostgreSQL都可以對IN和EXISTS采取最優的執行計劃。
如果沒有O_ORDERDATE上的索引，Query1和Query2在MySQL上的執行計劃都是采用IN子查詢的偽代碼實現邏輯：
-> 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建立一個索引，那么它們的執行計劃都是采用EXISTS子查詢的偽代碼實現邏輯：
-> 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)如果子查詢中的查詢列是唯一的，那么數據庫會將其轉換為內連接。
譬如對于下面的SQL。
select * from orders where o_custkey in (select c_custkey from customer where c_phone like '139%')MySQL的執行計劃是這樣的（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數據庫中，使用IN或是EXISTS的寫法是等價的，數據庫總是可以根據索引和統計信息采用最優的執行計劃。
PawSQL中的IN子查詢優化
PawSQL中會將IN子查詢重寫為EXISTS子查詢或是內連接查詢，從而幫助索引推薦引擎推薦合適的索引，促使優化器采用最優的執行計劃。
IN子查詢轉換為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)應用重寫優化，轉換為：
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)基于轉換后的SQL，推薦索引：
CREATE INDEX PAW_IDX1072908633 ON tpch.ORDERS(O_ORDERDATE,O_CUSTKEY);
-- 當QB_2中引用的表ORDERS作為驅動表時, 索引PAW_IDX1072908633可以被用來進行索引范圍查找,過濾條件為(orders.O_ORDERDATE >= current_date - interval '1' YEAR); 該索引是個覆蓋索引，可以避免回表.性能驗證：
- 執行計劃（優化前）
-> 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)- 執行計劃（優化后）
-> 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)本次優化實施后，預計本SQL的性能將提升 1648.67%。
IN子查詢轉換為內連接
原SQL，c_custkey是customer表的主鍵。
select *
from tpch.orders
where orders.o_custkey in (
select customer.c_custkey
from tpch.customer)應用重寫優化，轉化為內連接。
select orders.*
from tpch.orders, tpch.customer
where customer.c_custkey = orders.o_custkey基于轉換后的SQL，推薦索引。
CREATE INDEX PAW_IDX0455857015 ON tpch.ORDERS(O_CUSTKEY,O_CLERK);
-- 當ORDERS作為被驅動表時, 索引PAW_IDX0455857015可以被用來進行索引查找, 過濾條件為(customer.c_custkey = orders.o_custkey).性能驗證。
- 執行計劃（優化前）
-> 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)- 執行計劃（優化后）
-> 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)本次優化實施后，預計本SQL的性能將提升 1064.60%
關于PawSQL
PawSQL專注數據庫性能優化的自動化和智能化，支持MySQL，PostgreSQL，Opengauss等，提供的SQL優化產品包括
- PawSQL Cloud，在線自動化SQL優化工具，支持SQL審查，智能查詢重寫、基于代價的索引推薦，適用于數據庫管理員及數據應用開發人員。
- PawSQL Advisor，IntelliJ 插件, 適用于數據應用開發人員，可以IDEA/DataGrip應用市場通過名稱搜索“PawSQL Advisor”安裝。
- PawSQL Engine, 是PawSQL系列產品的后端優化引擎，可以獨立安裝部署，并通過http/json的接口提供SQL優化服務。PawSQL Engine以docker鏡像的方式提供部署安裝。
責任編輯：姜華
來源：
PawSQL
