優化：WHERE x IN（1，2 ..，100.000）vs INNER JOIN tmp_table USING（x）？

Question

我最近訪問過一個有趣的求職面試。在那裏我被問了一個關於使用包含長標量列表（即成千上萬個值）的WHERE..IN子句來優化查詢的問題。這個問題不是關於IN子句中的子查詢，而是關於簡單的標量列表。

我馬上回答，這可使用INNER JOIN與另一個表（可能臨時一個），這將僅包含那些標量進行優化。我的回答被接受了，並且有評論者的一條評論說，「目前沒有數據庫引擎可以優化足夠高性能的條件」。我點了頭。

但是，當我走了出來，我開始有些懷疑。這種情況似乎相當微不足道，廣泛用於現代RDBMS，無法對其進行優化。所以，我開始了一些挖掘。

的PostgreSQL：

看來，PostgreSQL所parse scalar IN() constructions into ScalarArrayOpExpr structure，這是sorted。此結構稍後將在索引掃描期間用於查找匹配的行。 EXPLAIN ANALYZE這樣的查詢只顯示一個循環。沒有連接完成。所以，我期望這樣的查詢比INNER JOIN更快。我對我現有的數據庫進行了一些查詢，我的測試證明了這一點。但我不在乎測試純度，Postgres處於Vagrant之下，所以我可能是錯的。

MSSQL服務器：

MSSQL服務器builds a hash structure from the list of constant expressions and then does a hash join with the source table。即使沒有排序似乎完成，我認爲這是一場表演賽。我沒有做任何測試，因爲我對這個RDBMS沒有任何經驗。

MySQL服務器：這個問題

The 13th of these slides說，這5.0之前的確發生在MySQL的一些情況。但除此之外，我沒有發現任何其他與治療不良有關的其他問題。不幸的是，我沒有找到任何反證的證據。如果你有，請踢我。

SQLite的：

Documentation page暗示了一些問題，但我傾向於相信事情說明真的有在概念層面。沒有其他信息被發現。因此，我開始認爲我誤會了我的面試官或誤用了Google;）或者，也許是因爲我們沒有設置任何條件，我們的談話變得有點模糊（我們沒有具體說明任何具體情況RDBMS或其他條件，這只是抽象的談話）。

它看起來像天，其中數據庫改寫IN()爲一組OR報表（可以在列表中與NULL值有時會造成問題，順便說一句）是很久以前。或不？

當然，在情況下，標量的列表長於允許數據庫協議包，INNER JOIN可能是唯一的解決方案。

我認爲在某些情況下，查詢解析時間（如果沒有準備的話）單獨可以殺死性能。

此外，數據庫可能無法準備IN(?)查詢，這將導致一次又一次地重新分析（這可能會導致性能下降）。實際上，我從來沒有嘗試過，但我認爲即使在這種情況下，與查詢執行相比，查詢解析和規劃並不是很大。

但除此之外，我沒有看到其他問題。那麼，除了有這個問題的問題。如果您有查詢，其中包含數千個ID，則您的架構出現問題。

是嗎？

Answer 1

只有在列表中建立一個索引（最好是主鍵索引）時，您的答案纔是正確的，除非列表非常小。

對優化的任何描述都明確是數據庫特定的。然而，MySQL是相當具體談談它是如何優化in：

返回1如果expr等於任何IN列表中的值，否則 返回0。如果所有的值都是常數，它們是根據 評估到expr的類型並排序。然後使用二分搜索完成 的搜索。這意味着如果IN值 列表完全由常量組成，則IN非常快。

這肯定會是使用IN比使用另一個表更快的情況 - 並且可能比使用主鍵索引的另一個表更快。

我認爲SQL Server用OR的列表替換了IN。這些將作爲順序比較來實施。請注意，如果某些元素比其他元素更爲常見，並且這些元素首先出現在列表中，則順序比較可能比二元搜索更快。

Answer 2

我認爲這是不好的應用程序設計。那些使用IN運算符的值很可能不是硬編碼的，而是動態的。在這種情況下，我們應該始終使用預準備語句來防止SQL注入。 在每種情況下，它都會導致動態格式化準備好的語句（因爲佔位符的數量也是動態的），並且還會導致過度的硬解析（像我們有多少個IN值 - IN (?),IN (?,?)，。 ..）。 我會加載這些值到表中作爲你提到的使用連接（除非加載太開銷）或使用Oracle流水線功能IN foo(params)其中params參數可以是來自內存（PLSQL/Java等）的複雜結構（數組）。 如果值的數量較大，我會考慮使用EXISTS (select from mytable m where m.key=x.key)或EXISTS (select x from foo(params)而不是IN。在這種情況下，EXISTS提供比IN更好的性能。