如何編寫(xiě)更好的SQL查詢：終極指南-第三部分

本次我們學(xué)習(xí)《如何編寫(xiě)更好的SQL查詢》系列的最后一篇文章。

時(shí)間復(fù)雜度和大O符號(hào)

通過(guò)前兩篇文章，我們已經(jīng)對(duì)查詢計(jì)劃有了一定了解。接下來(lái)，我們還可以借助計(jì)算復(fù)雜度理論，來(lái)進(jìn)一步深入地挖掘和思考性能的提升。理論計(jì)算機(jī)科學(xué)這一領(lǐng)域聚焦于：根據(jù)難度來(lái)對(duì)計(jì)算問(wèn)題進(jìn)行分類(lèi)。這些計(jì)算問(wèn)題可以是算法問(wèn)題，也可以是查詢問(wèn)題。

對(duì)于查詢，我們可以不按照難度進(jìn)行分類(lèi)，而是按照運(yùn)行查詢并得到結(jié)果所需的時(shí)間來(lái)進(jìn)行分類(lèi)。這種方式也被稱(chēng)為按照時(shí)間復(fù)雜度進(jìn)行分類(lèi)。

使用大O符號(hào)，可以根據(jù)輸入的增長(zhǎng)速度來(lái)表示運(yùn)行時(shí)間，因?yàn)檩斎肟梢匀我獯?。大O符號(hào)不包括系數(shù)和低階項(xiàng)，以便可以專(zhuān)注于查詢運(yùn)行時(shí)間的重要部分：增長(zhǎng)率。使用這種方式時(shí)，會(huì)丟棄系數(shù)和低階項(xiàng)，時(shí)間復(fù)雜度是逐漸描述出的，這意味著輸入會(huì)變?yōu)闊o(wú)窮大。

在數(shù)據(jù)庫(kù)語(yǔ)言中，復(fù)雜性衡量了查詢運(yùn)行時(shí)間的長(zhǎng)短。

請(qǐng)注意，數(shù)據(jù)庫(kù)的大小不僅隨著表中存儲(chǔ)數(shù)據(jù)的增加而增加，數(shù)據(jù)庫(kù)中的索引也會(huì)影響數(shù)據(jù)庫(kù)大小。

估算查詢計(jì)劃的時(shí)間復(fù)雜性

執(zhí)行計(jì)劃定義了每個(gè)操作所使用的算法，這也使得每個(gè)查詢的執(zhí)行時(shí)間可以在邏輯上表示為查詢計(jì)劃中數(shù)據(jù)表大小的函數(shù)。換句話說(shuō)，可以使用大O符號(hào)和執(zhí)行計(jì)劃來(lái)估算查詢的復(fù)雜性和性能。

在下面的小結(jié)中，我們將會(huì)了解四種類(lèi)型的時(shí)間復(fù)雜度概念。

通過(guò)這些示例，可以看到查詢的時(shí)間復(fù)雜度會(huì)根據(jù)運(yùn)行的查詢內(nèi)容不同而有所不同。

對(duì)于不同的數(shù)據(jù)庫(kù)，需要考慮不同的索引方式、不同的執(zhí)行計(jì)劃和不同的實(shí)現(xiàn)方式。

因此以下所列出的時(shí)間復(fù)雜度概念非常普遍。

O（1）：恒定時(shí)間

有一種查詢算法，不論輸入的大小如何，都需要相同的時(shí)間來(lái)執(zhí)行，這種方式就是恒定時(shí)間查詢。這些類(lèi)型的查詢并不常見(jiàn)，下面是一個(gè)例子：

SELECT TOP 1 t.*
FROM t

這種算法的時(shí)間復(fù)雜度是一個(gè)常數(shù)，因?yàn)橹皇菑谋碇羞x擇任意一行。因此，時(shí)間長(zhǎng)度與表的大小無(wú)關(guān)。

線性時(shí)間：O（n）

如果一個(gè)算法的時(shí)間執(zhí)行與輸入大小成正比，那么算法的執(zhí)行時(shí)間會(huì)隨著輸入大小的增加而增加。對(duì)于數(shù)據(jù)庫(kù)，這意味著查詢執(zhí)行時(shí)間與表大小成正比：隨著表中數(shù)據(jù)行數(shù)的增加，查詢時(shí)間也會(huì)相應(yīng)增加。

一個(gè)示例就是在非索引列上使用WHERE子句進(jìn)行查詢：這就需要使用全表掃描或順序掃描，這將導(dǎo)致O（n）的時(shí)間復(fù)雜度。這意味著需要讀取表中的每一行，以便找到正確ID的數(shù)據(jù)。即使第一行就查找到了正確的數(shù)據(jù)，查詢還是會(huì)對(duì)每一行數(shù)據(jù)進(jìn)行讀取。

如果沒(méi)有索引，那么這個(gè)查詢的復(fù)雜度為O（n）i_id：

SELECT i_idFROM item;

• 這也意味像COUNT(*) FROM TABLE這樣的計(jì)數(shù)查詢，具有O（n）的時(shí)間復(fù)雜度，除非存儲(chǔ)了數(shù)據(jù)表的總行數(shù)，否則就會(huì)進(jìn)行全表掃描。此時(shí)，復(fù)雜度將更像是O（1）。

與線性執(zhí)行時(shí)間密切相關(guān)的是，所有線性執(zhí)行計(jì)劃的時(shí)間總和。下面是一些例子：

• 哈希連接（hash join）的復(fù)雜度為O（M + N）。兩個(gè)內(nèi)部數(shù)據(jù)表連接的經(jīng)典哈希連接算法是，首先為較小的數(shù)據(jù)表準(zhǔn)備一個(gè)哈希表。哈希表的入口由連接屬性和行組成。通過(guò)將hash函數(shù)應(yīng)用于join屬性，來(lái)實(shí)現(xiàn)哈希表的訪問(wèn)。一旦構(gòu)建了哈希表，就會(huì)掃描較大的表，并通過(guò)查看哈希表來(lái)查找較小表中的相關(guān)行。

• 合并連接（merge join）的復(fù)雜度為O（M + N），但是這種連接嚴(yán)重依賴于連接列上的索引，并且在沒(méi)有索引的情況下，會(huì)根據(jù)連接中使用的key對(duì)行先進(jìn)行排序：

  • 如果根據(jù)連接中使用的key，對(duì)兩個(gè)表進(jìn)行了排序，那么查詢的復(fù)雜度為O（M + N）。

  • 如果兩個(gè)表都有連接列上的索引，則索引會(huì)按順序維護(hù)這些列，同時(shí)也不需要進(jìn)行排序。此時(shí)復(fù)雜度為O（M + N）。

  • 如果兩個(gè)表都沒(méi)有連接列上的索引，則需要先對(duì)兩個(gè)表進(jìn)行排序，因此復(fù)雜度會(huì)是O（M log M + N log N）。

  • 如果一個(gè)表的連接列上有索引，而另一個(gè)表沒(méi)有，則需要先對(duì)沒(méi)有索引的表進(jìn)行排序，因此復(fù)雜度會(huì)是O（M + N log N ）。

• 對(duì)于嵌套連接，復(fù)雜度通常為O（MN）。當(dāng)一個(gè)或兩個(gè)表非常?。ɡ?，小于10個(gè)記錄）時(shí)，這種連接方式特別有效。

請(qǐng)記得：嵌套連接是將一個(gè)表中的每個(gè)記錄與另一個(gè)表中的每個(gè)記錄進(jìn)行比較的連接方式。

對(duì)數(shù)時(shí)間：O（log（n））

如果算法的執(zhí)行時(shí)間與輸入大小的對(duì)數(shù)成比，則算法被稱(chēng)為對(duì)數(shù)時(shí)間算法; 對(duì)于查詢，這意味著執(zhí)行時(shí)間與數(shù)據(jù)庫(kù)大小的對(duì)數(shù)成正比。

執(zhí)行索引掃描（index Scan）或聚集索引掃描的查詢計(jì)劃時(shí)間復(fù)雜度，就是對(duì)數(shù)時(shí)間。聚集索引是索引的葉級(jí)別包含表的實(shí)際數(shù)據(jù)行的索引。聚集與其他索引非常相似：它是在一個(gè)或多個(gè)列上定義的。這也形成了索引主鍵。聚集主鍵是是聚集索引的主鍵列。聚集索引掃描是聚集索引中RDBMS從頭到尾一行一行讀取的基本操作。

以下的示例中存在一個(gè)i_id的索引，這也導(dǎo)致O（log（n））的復(fù)雜度：

SELECT i_stockFROM itemWHERE i_id = N;

如果沒(méi)有索引，則時(shí)間復(fù)雜度是O（n）。

二次時(shí)間：O（n ^ 2）

如果算法的執(zhí)行時(shí)間與輸入大小的平方成正比，則算法被稱(chēng)為對(duì)數(shù)時(shí)間算法。對(duì)于數(shù)據(jù)庫(kù)，這意味著查詢的執(zhí)行時(shí)間與數(shù)據(jù)庫(kù)大小的平方成正比。

具有二次時(shí)間復(fù)雜度的查詢的示例如下：

SELECT *
FROM item, authorWHERE item.i_a_id=author.a_id

最小復(fù)雜度為O（n log（n）），但是基于連接屬性的索引信息，最大復(fù)雜度會(huì)是O（n ^ 2）。

下圖是一張根據(jù)時(shí)間復(fù)雜度來(lái)估算查詢性能的圖表，通過(guò)圖表可以查看每個(gè)算法的性能表現(xiàn)。

SQL調(diào)優(yōu)

可以從以下方面衡量查詢計(jì)劃和時(shí)間復(fù)雜性，并進(jìn)一步調(diào)優(yōu)SQL查詢：

• 用索引掃描替換不必要的大數(shù)據(jù)表的全表掃描;

• 確保表的連接順序?yàn)樽罴秧樞?

• 確保以最佳方式使用索引;

• 將小數(shù)據(jù)表的全表掃描緩存起來(lái)。

《如何編寫(xiě)更好的SQL查詢》教程的所有內(nèi)容就介紹到這里，希望通過(guò)本教程的介紹，能夠幫助大家編寫(xiě)出更好、更優(yōu)的SQL查詢。

原文鏈接：https://www.datacamp.com/community/tutorials/sql-tutorial-query#importance

轉(zhuǎn)載請(qǐng)注明出自：葡萄城控件