結構化查詢語言（SQL）是數據科學行業中一項不可或缺的技能，一般來說，學習這個技能是挺容易的。不過，很多人都忘記了寫查詢只是SQL的第一步。更多內容關注
公眾號“全階魔方”我們還得確保查詢性能優異，或者符合正在工作的上下文環境。正因為如此，本SQL教程將讓你瞧瞧某些步驟，我們可以通過這些步驟來評估查詢：
· 首先，我們從簡要介紹數據科學工作中開始；
· 接下來，我們將首先學習更多有關的信息，這樣就可以正確理解編寫高質量查詢的重要性：更具體地說，就是我們將看到查詢被解析、重寫、優化和最終求值；
· 考慮到這一點，我們不僅會重溫初學者在編寫查詢時所做的一些，而且還會學習更多針對那些可能的錯誤的替代方案和解決方案；還會學到更多有關的知識。
· 我們還會看到，這些反模式源於性能考慮，並且除了用"手動"方法來提升SQL查詢之外，還可以通過使用能幫助我們查看查詢計劃的一些其他工具，以更結構化、更深入的方式；並且，
· 我們會大致進一步深入，從而在執行查詢之前，搞清楚執行計劃的時間複雜度；最後，
· 我們會大致獲得一些關於如何進一步的指示。
數據科學為什麼要學SQL？
SQL遠沒有死亡：它是我們從數據科學行業的職業描述中找到的最需要的技能之一，無論你是申請數據分析師、數據工程師、數據科學家，還是。2016年O'Reilly數據科學薪資調查報告時，70％的受訪者證實了這一點，他們都表明在其專業背景中用到了SQL。此外，在本次調查中，SQL遠勝於R（57％）和Python（54％）編程語言。
所以你明白了吧：如果要在數據科學行業謀求一份差事，那麼SQL就是一項必備的技能。
這對一門在20世紀70年代初就被開發出來的語言來說還不賴，對吧？
那麼到底SQL為什麼被這樣頻繁地使用呢？為什麼它即使已經存在了這麼長時間還不死呢？
這裡有幾個原因：首要原因之一是公司大多將數據存儲在關係型數據庫管理系統（RDBMS）或關係型數據流管理系統（RDSMS）中，而我們需要SQL才能訪問其中的數據。SQL是數據的通用語言：它能讓我們與幾乎任何數據庫進行交互，甚至可以在本地建立自己的數據庫！
如果這還不夠，那麼請記住，不少廠商之間的SQL實現並不兼容，而且不一定遵循標準。因此，瞭解標準SQL是我們在（數據科學）行業中找條活路的一個需求。
除此之外，可以肯定地說，較新的技術也已經擁抱了SQL，比如Hive（一種用於查詢和管理大數據集的類SQL查詢語言接口）和Spark SQL（可用於執行SQL查詢）。當然，這些地方出現的SQL依然會與我們學過的標準有所不同，但學習曲線會容易得多。
如果想做個對比的話，可以把學SQL當成學線性代數：把所有精力都投入到線性代數這一個主題上，你知道你也能用它來掌握機器學習！
簡而言之，如下就是為什麼我們應該學習這種查詢語言的原因：
· 它相當易學，即使對完全的新手來說也是如此。學習曲線很容易並且是循序漸進，這樣我們馬上就可以寫查詢。
· 它遵循"一次學習，到處可用"的原則，所以這是一項不錯的時間投資！
· 它是對編程語言的極好補充；在某些情況下，寫查詢甚至優於寫代碼，因為它性能更佳！
· ...
你還在等什麼？:)
SQL處理和查詢執行
為提高SQL查詢的性能，我們首先必須知道當我們按快捷方式運行查詢時，內部會發生什麼。
首先，查詢被解析成一個"解析樹"；查詢被分析，看看它是否滿足語法和語義要求。解析器為輸入的查詢創建一個內部表示，然後將此內部表示作為輸出，傳給重寫引擎。
然後，優化器的任務是找到給定查詢的最優執行或查詢計劃。執行計劃準確地定義了每個操作使用什麼算法，以及如何協調操作的執行。
為了找到最優執行計劃，優化器會列舉所有可能的執行計劃，確定每個計劃的質量或成本，獲取有關當前數據庫狀態的信息，然後選擇最好的一個作為最終的執行計劃。由於查詢優化器可能不完善，因此數據庫用戶和管理員有時需要手動檢查並調整優化器生成的計劃，以獲得更好的性能。
現在你可能想知道什麼才算一個"好的查詢計劃"。
正如我們所讀過所見，計劃的成本質量起著重要的作用。更具體地說，就是評估計劃所需的磁盤I/O數量、計劃的CPU成本以及數據庫客戶端可以觀察到的整體響應時間和總執行時間等因素至關重要。而那就是時間複雜度的概念會出現的地方。稍後我們會閱讀更多。
接下來，執行所選擇的查詢計劃，由系統的執行引擎進行求值，並返回查詢結果。
寫SQL查詢
這時候，從上一節到現在可能還沒有變得清晰的一件事，即進來的是垃圾，出去的也是垃圾（GIGO）原則，在查詢處理和執行過程中就自然而然地浮出水面：制定查詢的人也握有SQL查詢性能的鑰匙。如果優化器得到一個制定得糟糕的查詢，那麼它也只能優化得糟糕...
這意味著我們在寫查詢時可以做一些事情。正如在簡介中已經看到的那樣，責任是雙重的：它不僅與寫出符合某一標準的查詢有關，而且還與收集查詢中性能問題可能潛伏在何處的想法有關。
一個理想的起點是在查詢中考慮問題可能潛入的"點"。而且，一般來說，新手可能會出現性能問題的地方有四個子句和關鍵字：
· WHERE子句；
· 任何INNER JOIN或LEFT JOIN關鍵字；以及，
· HAVING子句；
我承認，這種做法簡單而粗暴，但是作為初學者，這些子句和語句是很好的指示器。而且，可以肯定地說，我們剛開始學習寫查詢時，這些地方就是錯誤發生的地方，並且，具有諷刺意味的是，這些地方在哪裡也很難發現。
不過，我們還要明白，性能是需要一個上下文背景才變得有意義：簡單地說，在考慮SQL性能時，這些子句和關鍵字並不一定會導致性能糟糕。查詢中有WHERE或HAVING子句不一定意味著這是一個糟糕的查詢...
看看一下小節，瞭解有關構建查詢的反模式以及替代方法的更多信息。這些提示和技巧僅作指導。實際怎樣重寫查詢取決於數據量、數據庫和執行查詢所需的次數等等。它完全取決於查詢的目標，並且對要查詢的數據庫有一些先驗知識也是至關重要的！
1.僅取回需要的數據
在寫SQL查詢時，不應該有"數據越多越好"的心態。如果這樣有這樣的心態的話，不僅會有由於獲得了比實際需要更多的數據從而矇蔽了觀察力的風險，而且還會因為查詢提取太多數據而影響性能。
這就是為什麼一般來說，留心SELECT語句、DISTINCT子句和LIKE運算符是一個好主意的原因。
· SELECT 語句
查詢編寫完後，首先應該檢查的是SELECT語句是否儘可能緊湊。目標應該是從SELECT中刪除不必要的列。這樣就可以強制自己只提取用於查詢目標的數據。
如果有含有EXISTS的相關子查詢，就應試試在該子查詢的SELECT語句中使用常量，而不是選擇一個實際列的值。這在只檢查值是否存在時特別方便。
請記住，相關子查詢是使用來自外部查詢中的值的子查詢。並且注意，甚至NULL也可以在此上下文背景中作為一個"常量"，這是非常令人困惑的！
為理解使用常量的含義，請考慮以下示例：
1. SELECT driverslicensenr, name
2. FROM Drivers
3. WHERE EXISTS (SELECT '1' FROM Fines
4. WHERE fines.driverslicensenr = drivers.driverslicensenr);
sql
提示：要知道有相關子查詢並不總是一個好主意。你可以隨時考慮去掉相關子查詢，比如，用 INNER JOIN 重寫：
1. SELECT driverslicensenr, name
2. FROM drivers
3. INNER JOIN fines ON fines.driverslicensenr = drivers.driverslicensenr;
· DISTINCT 子句
SELECT DISTINCT語句用於僅返回有區別的（不同的）值。應該儘可能避免使用DISTINCT子句；就像在其他示例中讀過的那樣，如果將此子句添加到查詢中，執行時間只會增加。因此，考慮是否真的需要執行DISTINCT操作來獲取要完成的結果，總是一個好主意。
· LIKE 運算符
在查詢中使用LIKE運算符時，如果模式以％或_開頭，就不會用到索引。它會阻止數據庫使用索引（如果有索引的話）。當然，從另一個角度來看，你也可以認為這類的查詢可能會導致獲取太多不一定滿足查詢目標的記錄。
再一次，對存儲在數據庫中的數據的瞭解可以幫助我們制定一個模式，該模式會對所有數據正確過濾，這樣就只查找對查詢至關重要的行。
2.限制查詢結果
當無法避免要在SELECT語句中過濾一些數據時，可以考慮以其他方式限制結果。如下是LIMIT子句和數據類型轉換等方法出現的地方：
· TOP、LIMIT 和 ROWNUM 子句
可以將LIMIT或TOP子句添加到查詢中，來設置結果集的最大行數。例如：
1. `SELECT TOP 3 * FROM Drivers;`
請注意，可以進一步指定PERCENT，例如，通過SELECT TOP 50 PERCENT *更改查詢的第一行。
1. `SELECT driverslicensenr, name FROM Drivers LIMIT 2;`
此外，還可以添加ROWNUM子句，相當於在查詢中使用LIMIT：
1. SELECT *
2. FROM Drivers
3. WHERE driverslicensenr = 123456 AND ROWNUM <= 3;
· 數據類型轉換
應該始終儘可能使用最有效率（即最小）的數據類型。當一個較小的數據類型就足夠時，用大的數據類型總是一個風險。
不過，當給查詢添加數據類型轉換時，只會增加執行時間。
一個替代方案是儘可能避免數據類型轉換。還要注意，並不總是可以從查詢中刪除或省略數據類型轉換，但是包含它們的時候一定要小心，並且在包含它們時，在運行查詢之前應該測試添加了它們後的效果。
3. 不要讓查詢變得比所需要的更復雜
數據類型轉換又帶來下一點：不要過度設計查詢。儘量保持簡單高效。這作為一個訣竅可能看起來太簡單或愚蠢，特別是因為查詢本來就可能變複雜。
不過，在下一小節中提到的示例中我們會看到，我們很容易會從一開始就讓簡單查詢變得比需要的更復雜。
· OR 運算符
當在查詢中使用OR運算符時，我們很可能沒有用索引。
請記住，索引是一種數據結構，可以提高數據庫表中數據獲取的速度，但會帶來成本：會需要額外的寫入和額外的存儲空間來維護索引數據結構。索引用於快速定位或查找數據，而不用在每次訪問數據庫表時必須搜索數據庫中的每一行。索引可以用在數據庫表中的一個或多個列來創建。
如果不使用數據庫包含的索引，那麼查詢就會不可避免地需要更長時間運行。這就是為什麼最好在使用OR運算符的查詢中尋找替代方法的原因；
考慮以下查詢：
1. SELECT driverslicensenr, name
2. FROM Drivers
3. WHERE driverslicensenr = 123456 OR driverslicensenr = 678910 OR driverslicensenr = 345678;
可以通過用以下方式替換 OR 運算符：
· 帶有 IN的條件；或者
1. SELECT driverslicensenr, name
2. FROM Drivers
3. WHERE driverslicensenr IN (123456, 678910, 345678);
· 帶有UNION的兩個SELECT語句。
提示：在這裡，需要注意不要不必要地使用UNION操作，因為這樣做會多次遍歷同一個表。同時，必須意識到，當在查詢中使用UNION時，執行時間將會增加。UNION操作的替代方法是：重新規劃查詢，把所有條件都放在一個SELECT指令中，或者使用OUTER JOIN來代替UNION。
提示：在這裡也要記住，儘管OR以及下面幾節中提到的其他運算符可能不使用索引，索引查找並非總是首選！
· NOT 運算符
當查詢包含NOT運算符時，很可能不使用索引，就像使用OR運算符一樣。這會不可避免地減慢查詢。如果不知道這是什麼意思，請考慮以下查詢：
1. `SELECT driverslicensenr, name FROM Drivers WHERE NOT (year > 1980);`
這個查詢肯定會比你預期的更慢，主要是因為它規劃的比想像的複雜得多：像這種情況，最好是找一個替代方案。考慮用比較運算符替換NOT，如>，或!>；上面的例子可能會被重寫，變成這樣：
1. `SELECT driverslicensenr, name FROM Drivers WHERE year <= 1980;`
這樣看起來更整潔，對吧？
· AND 運算符
AND運算符是另一個不使用索引的運算符，如果以過於複雜和低效的方式使用，可能會降低查詢速度，如下例所示：
1. SELECT driverslicensenr, name
2. FROM Drivers
3. WHERE year >= 1960 AND year <= 1980;
最好用BETWEEN運算符重寫：
1. SELECT driverslicensenr, name
2. FROM Drivers
3. WHERE year BETWEEN 1960 AND 1980;
· ANY 和 ALL 運算符
此外，ALL和ANY運算符應該小心使用，因為如果將它們包含在查詢中，索引也不會被使用。這裡可以使用的替代方法是聚合函數，如MIN或MAX。
提示：在用上面推薦的替代方案時，必須注意：所有聚合函數（如SUM、AVG、MIN、MAX）在作用於很多行時，都會導致查詢長時間運行。在這種情況下，可以試試要麼最小化要處理的行數，要麼預先計算這些值。我們可以再次看到，當決定使用哪個查詢時，重要的是要注意環境和查詢目標...
· 隔離條件中的列
另外，如果列被用在計算或標量函數中，也不會使用索引。一個可能的解決方案是僅隔離指定列，使其不再是計算或函數的一部分。請考慮以下示例：
1. SELECT driverslicensenr, name
2. FROM Drivers
3. WHERE year + 10 = 1980;
這看起來很噁心，對吧？那就試試重新考慮計算，並將查詢重寫為如下所示：
1. SELECT driverslicensenr, name
2. FROM Drivers
3. WHERE year = 1970;
4. 不要用蠻力
最後一個提示實際上就是不應該試圖過份限制查詢，因為會影響查詢性能。對於連接和HAVING子句尤其如此。
· 連接
· 表的順序 當連接兩個表時，考慮連接中表的順序可能很重要。如果注意到一個表比另一個表大得多，可能就需要重寫查詢，把最大的表放在連接的最後。
· 連接中的冗餘條件
當給連接添加太多條件時，本質上是強迫SQL來選擇某個路徑。不過，這條路徑並非總是性能較好的。
· HAVING 子句
HAVING子句添加到SQL中，原本是因為WHERE關鍵字不能與聚合函數一起使用。HAVING通常與GROUP BY子句一起使用，將返回行的組限制為僅滿足某些條件的行。不過，如果在查詢中使用此子句，就會不使用索引，而我們已經知道這可能會導致查詢不能很好地執行。
如果正在尋找替代方案，那就考慮使用WHERE子句。考慮如下查詢：
1. SELECT state, COUNT(*) FROM Drivers WHERE state IN ('GA', 'TX') GROUP BY state ORDER BY state
2.
3. SELECT state, COUNT(*) FROM Drivers GROUP BY state HAVING state IN ('GA', 'TX') ORDER BY state
第一個查詢使用WHERE子句來限制需要統計的行數；而第二個查詢對錶中的所有行計數，然後使用HAVING過濾計算出來的計數。在這些類型的情況下，使用WHERE子句的替代方案顯然是更好的，因為不會浪費任何資源。
我們可以看到，這不是限制結果集，而是限制查詢中記錄的中間數。
請注意，這兩個子句之間的區別在於WHERE子句是在每一行上引入一個條件，而HAVING子句是在一個選擇（selection）的聚合或者結果上（這裡單個結果，比如MIN、MAX、SUM，已經從多行中生成了）引入一個條件。
所以說，在要儘可能考慮性能時，評估質量、寫以及重寫查詢並非易事；當編寫要在專業環境中的數據庫上運行的查詢時，避免反模式以及考慮替代方案也會成為職責的一部分。
這個列表只是一些有望幫助初學者的反模式和技巧的簡單概述；如果想了解更多高級開發人員認為最常見的反模式的話，請查看。
基於集合的查詢方法與過程式查詢方法
上述反模式中隱含的事實是，它們實際上歸結為基於集合的方法創建查詢與過程式方法創建查詢之間的區別。
過程式方法創建查詢是一種非常類似於編程的方法：我們可以告訴系統該做什麼以及如何做。
一個例子是連接中的冗餘條件，或者像上例中一樣濫用HAVING子句的情況下，通過執行一個函數然後調用另一個函數來查詢數據庫，或者使用包含循環、條件、用戶定義函數（UDF）、光標等等邏輯來得到最終結果。在這種方法中，會經常發現自己要請求數據的一個子集，然後從該數據中請求另一個子集等等。
所以，毫不奇怪，這種方法通常被稱為"逐步"或"逐行"查詢。
另一種方法是基於集合的方法，這裡我們只需指定要執行的操作。我們的任務包括為想從查詢中得到的結果集指定條件或需求。將如何獲取數據留給確定查詢實現的內部機制：讓數據庫引擎確定執行查詢的最佳算法或處理邏輯。
由於SQL是基於集合的，所以不出意料，這種方法比過程式方法更有效，這也解釋了為什麼在某些情況下，SQL能比代碼工作的更快。
提示：基於集合的查詢方法也是數據科學行業最頂尖的僱主將要求你掌握的方法！你會經常需要在這兩類方法之間切換。
請注意，如果你發現自己有過程式查詢，就應考慮重寫或重構它。
從查詢到執行計劃
反模式並非一成不變的，會隨著我們作為SQL開發人員的發展而發展，並且在考慮替代方案時需要考慮良多，知道這個事實，也就意味著避免查詢反模式以及重寫查詢可能會是一件相當棘手的任務。這時候任何輔助手段都可以派上用場，這就是為什麼用一些工具以更加結構化的方式來優化查詢也是條可取的路徑。
還要注意，上一節中提到的一些反模式源於性能問題，如AND、OR和NOT運算符以及它們缺少索引使用。對性能的思考不僅需要更結構化的方法，而且還需要更深入的方法。
不過，這種結構化和深入的方法將主要是基於查詢計劃，而查詢計劃是首先被解析為"解析樹"的查詢結果，並且定義每個操作用什麼算法以及操作的執行如何協調。
查詢優化
正如在介紹中所看到的那樣，我們可能需要手動檢查和調整優化器生成的計劃。在這種情況下，我們將需要通過查看查詢計劃來再次分析查詢。
要控制此計劃，我們得用數據庫管理系統提供的工具。可以使用的一些工具如下：
· 某些軟件包有工具可以生成查詢計劃的圖形表示。看看這個例子：
· 其他工具能提供查詢計劃的文本描述。一個例子是Oracle中的EXPLAIN PLAN語句，不過指令的名稱根據正在用的RDBMS而有所不同。比如，MySQL、PostgreSQL中是EXPLAIN，SQLite中是EXPLAIN QUERY PLAN。
請注意，如果是在用PostgreSQL，那麼EXPLAIN和 EXPLAIN ANALYZE 之間是有區別的。前者只得到一個說明計劃器要如何執行查詢的描述，但是不會執行查詢；而後者會實際執行查詢，並返回一個預期與實際查詢計劃的分析。一般來說，實際的執行計劃是實際執行查詢時用的那個計劃，而估算的執行計劃是在不執行查詢的情況下算出執行計劃會做什麼。雖然二者在邏輯上差不多，但是實際執行計劃更為有用，因為它包含執行查詢時實際發生的其他細節和統計信息。
，我們將瞭解有關EXPLAIN和ANALYZE的更多信息，以及如何使用這兩個語句來了解有關查詢計劃的更多信息以及查詢的可能性能。為此，我們會從幾個示例開始。示例中要用到兩個表：one_million 和 half_million。
我們可以藉助 EXPLAIN 獲取表 one_million的當前信息；確保把 EXPLAIN放在查詢的最上面，運行後，就會返回查詢計劃：
1. EXPLAIN
2. SELECT *
3. FROM one_million;
4.
5. QUERY PLAN
6. ____________________________________________________
7. Seq Scan on one_million
8. (cost=0.00..18584.82 rows=1025082 width=36)
9. (1 row)
markdown
在本例中，我們可以看到查詢的成本是 0.00..18584.82，行數為 1025082，行平均寬度為 36。
然後我們還可以藉助 ANALYZE更新統計信息。
1. ANALYZE one_million;
2. EXPLAIN
3. SELECT *
4. FROM one_million;
5.
6. QUERY PLAN
7. ____________________________________________________
8. Seq Scan on one_million
9. (cost=0.00..18334.00 rows=1000000 width=37)
10. (1 row)
markdown
除了 EXPLAIN 和 ANALYZE 外，我們還可以藉助 EXPLAIN ANALYZE 獲取實際執行時間：
1. EXPLAIN ANALYZE
2. SELECT *
3. FROM one_million;
4.
5. QUERY PLAN
6. ___________________________________________________________
7. Seq Scan on one_million
8. (cost=0.00..18334.00 rows=1000000 width=37)
9. (actual time=0.015..1207.019 rows=1000000 loops=1)
10. Total runtime: 2320.146 ms
11. (2 rows)
markdown
這裡用EXPLAIN ANALYZE的缺點顯然是查詢被實際執行了，所以要小心！
迄今為止，我們所看到的算法都是 Seq Scan（順序掃描）或者全表掃描：這是在數據庫上進行的掃描，其中被掃描的表的每一行以按（串行）順序讀取，並且檢查找到的列是否滿足條件。在性能方面，順序掃描顯然不是最佳的執行計劃，因為我們依然是在進行全表掃描。 然而，當表沒法剛好放入內存時，這並不太糟糕：即使使用慢磁盤，順序讀取也會很快。
當討論索引掃描時，我們會看到更多信息。
不過，還有一些其他的算法。比如，為連接採用的這個查詢計劃：
1. EXPLAIN ANALYZE
2. SELECT *
3. FROM one_million JOIN half_million
4. ON (one_million.counter=half_million.counter);
5. QUERY PLAN
6. _________________________________________________________________
7. Hash Join (cost=15417.00..68831.00 rows=500000 width=42)
8. (actual time=1241.471..5912.553 rows=500000 loops=1)
9. Hash Cond: (one_million.counter = half_million.counter)
10. -> Seq Scan on one_million
11. (cost=0.00..18334.00 rows=1000000 width=37)
12. (actual time=0.007..1254.027 rows=1000000 loops=1)
13. -> Hash (cost=7213.00..7213.00 rows=500000 width=5)
14. (actual time=1241.251..1241.251 rows=500000 loops=1)
15. Buckets: 4096 Batches: 16 Memory Usage: 770kB
16. -> Seq Scan on half_million
17. (cost=0.00..7213.00 rows=500000 width=5)
18. (actual time=0.008..601.128 rows=500000 loops=1)
19. Total runtime: 6468.337 ms
jboss
可以看到這裡查詢優化器選擇的是 哈希連接（Hash Join）！記住這個操作，因為我們會需要它來評估查詢的時間複雜度。現在，請注意half_million.counter上沒有索引，可以在下一個例子中添加：
1. CREATE INDEX ON half_million(counter);
2. EXPLAIN ANALYZE
3. SELECT *
4. FROM one_million JOIN half_million
5. ON (one_million.counter=half_million.counter);
6. QUERY PLAN
7. ________________________________________________________________
8. Merge Join (cost=4.12..37650.65 rows=500000 width=42)
9. (actual time=0.033..3272.940 rows=500000 loops=1)
10. Merge Cond: (one_million.counter = half_million.counter)
11. -> Index Scan using one_million_counter_idx on one_million
12. (cost=0.00..32129.34 rows=1000000 width=37)
13. (actual time=0.011..694.466 rows=500001 loops=1)
14. -> Index Scan using half_million_counter_idx on half_million
15. (cost=0.00..14120.29 rows=500000 width=5)
16. (actual time=0.010..683.674 rows=500000 loops=1)
17. Total runtime: 3833.310 ms
18. (5 rows)
sql
可以看到，通過創建索引，查詢優化器現在決定選擇 Merge join（合併連接），而合併連接的時候是用 索引掃描。
注意索引掃描與全表掃描或順序掃描之間的區別：前者，也稱"表掃描"，是掃描數據或索引頁以找到適當的記錄，而後者掃描表的每一行。
可以看到總運行時已經減少了，性能應該更好，但是有兩個索引掃描，這使得內存在這裡變得更加重要，特別是如果表沒法剛好放入內存中時。 在這種情況下，我們首先必須執行全索引掃描，這是快速的順序讀取，不會引起任何問題，但是隨後有很多隨機讀來通過索引值獲取行。 而這些隨機讀取通常比順序讀取慢一個數量級。 在這種情況下，全表掃描實際上比全索引掃描更快。
提示：如果想了解更多關於EXPLAIN的信息或者更詳細地查看示例，請考慮閱讀Guillaume Lelarge寫的一書。
時間複雜度和大O表示法
現在我們已經大致複習了查詢計劃，可以在計算複雜度理論的幫助下開始深入挖掘，並以更正式的方式思考性能。理論計算機科學的這個領域，重點是根據難度對計算問題進行分類；這些計算問題可以是算法，也可以是查詢。
但是，對於查詢，我們不一定根據其難度對其分類，而是根據運行它並返回一些結果所花的時間來分類。具體來說，這被稱為時間複雜度，而且表達或測量這種類型的複雜度，我們可以使用大O表示法。
用大O表示法，我們可以依據運行時間隨著輸入變得無窮大，相對於輸入的增長速度，來表達運行時間。大O表示法排除掉係數和低階項，這樣我們就可以專注於查詢運行時間的重要部分：其增長率。當以這種方式表示時，丟棄係數和低階項，時間複雜度被認為是漸近地描述的。也就是說，輸入大小達到無窮大。
在數據庫語言中，複雜度衡量了隨著數據表的大小增長以及隨之帶來的數據庫增長，查詢運行時間的長短。
請注意，數據庫的大小不僅會隨著更多的數據存儲在表中而增長，而且存在於數據庫中的索引也會對大小增長起作用。
估算查詢計劃的時間複雜度
如前所述，除了做其他事情外，執行計劃還定義了每個操作用什麼算法，讓每個查詢執行時間可以被邏輯地表示為一個查詢計劃中表大小的函數，這個函數被稱為複雜度函數。換句話說，可以用大O表示法和執行計劃來估算查詢的複雜度和性能。
在以下小節中，您將得到有關四種類型的時間複雜性的一般概念，您將看到一些示例，說明查詢的時間複雜度如何根據您運行它的上下文而有所不同。
提示：索引是故事的一部分！
但是請注意，考慮到有不同類型的索引、不同的執行計劃以及不同數據庫的不同實現，所以下面列出的時間複雜度是一個非常總體的概括，可能會根據具體設置而有所不同。
常數時間: O(1)
如果一個算法不管輸入有多大，總是需要相同的時間量，那麼就說該算法以常數時間運行。對於查詢，如果不管表有多大，總是需要相同的時間量，那麼該查詢就會以常數時間運行。
這類查詢並不常見，不過這裡有這麼一個例子：
1. SELECT TOP 1 t.*
2. FROM t
這裡時間複雜度是常數，因為只從表中選擇一個任意行。 因此，時間長度應該與表的大小無關。
線性時間: O(n)
如果一個算法的時間執行與輸入大小成正比，即隨著輸入大小的增加，時間線性增長，那麼該算法就是以線性時間運行。對於數據庫，這意味著時間執行與表大小成正比：隨著表中行數的增加，查詢的時間增長。
一個示例是在未索引的列上使用WHERE子句的查詢：將需要全表掃描或Seq Scan，這會導致時間複雜度為O(n)。 這意味著需要讀取每一行以找到具有正確ID的數據。 你根本沒有限制，所以每行都需要讀取，即使第一行就匹配條件也是如此。
還可以考慮以下示例，如果i_id上沒有索引，那麼這個查詢的複雜度就為O(n)：
1. SELECT i_id
2. FROM item;
· 這也意味著其他查詢，例如COUNT（*）FROM TABLE;這樣的計數查詢的時間複雜度為O(n)，因為將需要全表掃描，除非存儲表的總行數，那麼複雜度會更像O(1)。
與線性執行時間密切相關的是其中有連接的執行計劃的執行時間。 這裡有些例子：
· 哈希連接（hash join）具有預期的複雜度O(M + N)。 用於兩個表內連接的經典哈希連接算法首先準備較小表的哈希表。哈希表項由連接屬性及其行組成。 通過將一個哈希函數應用於連接屬性來訪問哈希表。 一旦構建了哈希表，就會掃描較大的表，並通過查看哈希表來查找較小表中的相關行。
· 合併連接（merge join）通常具有複雜度O(M + N)，但這個複雜度將嚴重依賴於連接列上的索引，並且在沒有索引的情況下，依賴於行是否根據連接中所用的鍵排序：
· 如果兩個表都根據連接中所用的鍵排序過了，那麼查詢的複雜度就為O(M+N) 。
· 如果兩個表都在連接列上有索引，那麼索引就已經按次序維護這些列了，不需要排序。複雜度就會是O(M + N)。
· 如果兩個表在連接列上都沒有索引，那麼首先就要對兩個表排序，所以複雜度就會類似於O(M log M + N log N)。
· 如果只有一個表在連接列上有索引，那麼只有沒有索引的表會需要在合併步驟發生之前排序，所以複雜度就會類似於O(M + N log N)。
· 對於嵌套連接，複雜度通常是O(MN)。當一個或兩個表非常小（例如，小於10個記錄）時，這種連接是高效的，這是評估查詢時非常常見的情況，因為某些子查詢被寫為僅返回一行。
記住：嵌套連接是將一個表中的每個記錄與另一個表中的每個記錄進行比較的連接。
對數時間: O(log (n))
如果一個算法的時間執行與輸入大小的對數成比例，則該算法被稱為以對數時間運行; 對於查詢，這意味著如果執行時間與數據庫大小的對數成正比，它們將以對數時間運行。
這種對數時間複雜度對於執行"索引掃描"或聚簇索引掃描的查詢計劃是真實的。聚簇索引是索引的葉級別包含表的實際數據行的索引。聚簇索引與其他索引非常相似：它在一個或多個列上定義。這些列形成索引鍵。 聚簇鍵是聚簇索引的關鍵列。聚簇索引掃描基本上是RDBMS從上到下讀取聚簇索引中的行的操作。
考慮如下的查詢示例，這裡在 i_id 上有一個索引，通常會得到複雜度O(log(n))：
1. SELECT i_stock
2. FROM item
3. WHERE i_id = N;
注意 ：如果沒有索引，那麼時間複雜度就變成了 O(n)。
平方時間: O(n^2)
如果一個算法的時間執行與輸入大小的平方成正比，那麼該算法就被稱為以平方時間運行。再次，對於數據庫，這意味著查詢的執行時間與數據庫大小的平方成正比。
具有平方時間複雜度的查詢的一個示例如下：
1. SELECT *
2. FROM item, author
3. WHERE item.i_a_id=author.a_id
基於連接屬性的索引信息，最小複雜度將是O(n log(n))，但是最大複雜度可能是O(n^2)。
總而言之，我們還可以查看來根據時間複雜度及其執行情況來估算查詢的性能：
SQL調優
搞清楚查詢計劃和時間複雜度後，我們就可以考慮進一步調整SQL查詢。我們可以從特別注意以下幾點開始：
· 用索引掃描替代不必要的大表全表掃描；
· 確保正在應用最佳表連接順序；
· 確保最佳地使用索引；以及
· 緩存小表全表掃描。
進一步深入 SQL
恭喜！你已經到了這篇博文的末尾，這只是讓你大致瞭解SQL查詢性能。希望你對反模式、查詢優化器以及可用於查看、估算和解釋查詢計劃的複雜度的工具有更多見解。不過，還有更多需要去探索！如果想了解更多，請考慮閱讀由R. Ramakrishnan和J.Gehrke寫的《數據庫管理系統》一書。
最後，我不想隱瞞StackOverflow用戶的這條引文：
"我最喜歡的反模式是不要測試查詢。
這適用於：
· 你的查詢涉及多個表。
· 你認為你有一個優化的查詢設計，不想費心測試你的假設。
· 你接受第一個查詢是有效的，沒有關於它是否接近優化的線索。"
閱讀更多 全階魔方 的文章
