我們提供的服務(wù)有：網(wǎng)站制作、做網(wǎng)站、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、南城ssl等。為上千家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的南城網(wǎng)站制作公司
本次我們學(xué)習(xí)《如何編寫更好的SQL查詢》系列的最后一篇文章。
通過前兩篇文章，我們已經(jīng)對查詢計(jì)劃有了一定了解。接下來，我們還可以借助計(jì)算復(fù)雜度理論，來進(jìn)一步深入地挖掘和思考性能的提升。理論計(jì)算機(jī)科學(xué)這一領(lǐng)域聚焦于：根據(jù)難度來對計(jì)算問題進(jìn)行分類。這些計(jì)算問題可以是算法問題，也可以是查詢問題。
對于查詢，我們可以不按照難度進(jìn)行分類，而是按照運(yùn)行查詢并得到結(jié)果所需的時間來進(jìn)行分類。這種方式也被稱為按照時間復(fù)雜度進(jìn)行分類。
使用大O符號，可以根據(jù)輸入的增長速度來表示運(yùn)行時間，因?yàn)檩斎肟梢匀我獯?。大O符號不包括系數(shù)和低階項(xiàng)，以便可以專注于查詢運(yùn)行時間的重要部分：增長率。使用這種方式時，會丟棄系數(shù)和低階項(xiàng)，時間復(fù)雜度是逐漸描述出的，這意味著輸入會變?yōu)闊o窮大。
在數(shù)據(jù)庫語言中，復(fù)雜性衡量了查詢運(yùn)行時間的長短。
請注意，數(shù)據(jù)庫的大小不僅隨著表中存儲數(shù)據(jù)的增加而增加，數(shù)據(jù)庫中的索引也會影響數(shù)據(jù)庫大小。
執(zhí)行計(jì)劃定義了每個操作所使用的算法，這也使得每個查詢的執(zhí)行時間可以在邏輯上表示為查詢計(jì)劃中數(shù)據(jù)表大小的函數(shù)。換句話說，可以使用大O符號和執(zhí)行計(jì)劃來估算查詢的復(fù)雜性和性能。
在下面的小結(jié)中，我們將會了解四種類型的時間復(fù)雜度概念。
通過這些示例，可以看到查詢的時間復(fù)雜度會根據(jù)運(yùn)行的查詢內(nèi)容不同而有所不同。
對于不同的數(shù)據(jù)庫，需要考慮不同的索引方式、不同的執(zhí)行計(jì)劃和不同的實(shí)現(xiàn)方式。
因此以下所列出的時間復(fù)雜度概念非常普遍。
有一種查詢算法，不論輸入的大小如何，都需要相同的時間來執(zhí)行，這種方式就是恒定時間查詢。這些類型的查詢并不常見，下面是一個例子：
SELECT TOP 1 t.* FROM t
這種算法的時間復(fù)雜度是一個常數(shù)，因?yàn)橹皇菑谋碇羞x擇任意一行。因此，時間長度與表的大小無關(guān)。
如果一個算法的時間執(zhí)行與輸入大小成正比，那么算法的執(zhí)行時間會隨著輸入大小的增加而增加。對于數(shù)據(jù)庫，這意味著查詢執(zhí)行時間與表大小成正比：隨著表中數(shù)據(jù)行數(shù)的增加，查詢時間也會相應(yīng)增加。
一個示例就是在非索引列上使用WHERE子句進(jìn)行查詢：這就需要使用全表掃描或順序掃描，這將導(dǎo)致O（n）的時間復(fù)雜度。這意味著需要讀取表中的每一行，以便找到正確ID的數(shù)據(jù)。即使第一行就查找到了正確的數(shù)據(jù)，查詢還是會對每一行數(shù)據(jù)進(jìn)行讀取。
如果沒有索引，那么這個查詢的復(fù)雜度為O（n）i_id：
SELECT i_idFROM item;
這也意味像COUNT(*) FROM TABLE這樣的計(jì)數(shù)查詢，具有O（n）的時間復(fù)雜度，除非存儲了數(shù)據(jù)表的總行數(shù)，否則就會進(jìn)行全表掃描。此時，復(fù)雜度將更像是O（1）。
與線性執(zhí)行時間密切相關(guān)的是，所有線性執(zhí)行計(jì)劃的時間總和。下面是一些例子：
哈希連接（hash join）的復(fù)雜度為O（M + N）。兩個內(nèi)部數(shù)據(jù)表連接的經(jīng)典哈希連接算法是，首先為較小的數(shù)據(jù)表準(zhǔn)備一個哈希表。哈希表的入口由連接屬性和行組成。通過將hash函數(shù)應(yīng)用于join屬性，來實(shí)現(xiàn)哈希表的訪問。一旦構(gòu)建了哈希表，就會掃描較大的表，并通過查看哈希表來查找較小表中的相關(guān)行。
合并連接（merge join）的復(fù)雜度為O（M + N），但是這種連接嚴(yán)重依賴于連接列上的索引，并且在沒有索引的情況下，會根據(jù)連接中使用的key對行先進(jìn)行排序：
如果根據(jù)連接中使用的key，對兩個表進(jìn)行了排序，那么查詢的復(fù)雜度為O（M + N）。
如果兩個表都有連接列上的索引，則索引會按順序維護(hù)這些列，同時也不需要進(jìn)行排序。此時復(fù)雜度為O（M + N）。
如果兩個表都沒有連接列上的索引，則需要先對兩個表進(jìn)行排序，因此復(fù)雜度會是O（M log M + N log N）。
如果一個表的連接列上有索引，而另一個表沒有，則需要先對沒有索引的表進(jìn)行排序，因此復(fù)雜度會是O（M + N log N ）。
對于嵌套連接，復(fù)雜度通常為O（MN）。當(dāng)一個或兩個表非常小（例如，小于10個記錄）時，這種連接方式特別有效。
請記得：嵌套連接是將一個表中的每個記錄與另一個表中的每個記錄進(jìn)行比較的連接方式。
如果算法的執(zhí)行時間與輸入大小的對數(shù)成比，則算法被稱為對數(shù)時間算法; 對于查詢，這意味著執(zhí)行時間與數(shù)據(jù)庫大小的對數(shù)成正比。
執(zhí)行索引掃描（index Scan）或聚集索引掃描的查詢計(jì)劃時間復(fù)雜度，就是對數(shù)時間。聚集索引是索引的葉級別包含表的實(shí)際數(shù)據(jù)行的索引。聚集與其他索引非常相似：它是在一個或多個列上定義的。這也形成了索引主鍵。聚集主鍵是是聚集索引的主鍵列。聚集索引掃描是聚集索引中RDBMS從頭到尾一行一行讀取的基本操作。
以下的示例中存在一個i_id的索引，這也導(dǎo)致O（log（n））的復(fù)雜度：
SELECT i_stockFROM itemWHERE i_id = N;
如果沒有索引，則時間復(fù)雜度是O（n）。
如果算法的執(zhí)行時間與輸入大小的平方成正比，則算法被稱為對數(shù)時間算法。對于數(shù)據(jù)庫，這意味著查詢的執(zhí)行時間與數(shù)據(jù)庫大小的平方成正比。
具有二次時間復(fù)雜度的查詢的示例如下：
SELECT * FROM item, authorWHERE item.i_a_id=author.a_id
最小復(fù)雜度為O（n log（n）），但是基于連接屬性的索引信息，最大復(fù)雜度會是O（n ^ 2）。
下圖是一張根據(jù)時間復(fù)雜度來估算查詢性能的圖表，通過圖表可以查看每個算法的性能表現(xiàn)。
可以從以下方面衡量查詢計(jì)劃和時間復(fù)雜性，并進(jìn)一步調(diào)優(yōu)SQL查詢：
用索引掃描替換不必要的大數(shù)據(jù)表的全表掃描;
確保表的連接順序?yàn)樽罴秧樞?
確保以最佳方式使用索引;
將小數(shù)據(jù)表的全表掃描緩存起來。
《如何編寫更好的SQL查詢》教程的所有內(nèi)容就介紹到這里，希望通過本教程的介紹，能夠幫助大家編寫出更好、更優(yōu)的SQL查詢。
原文鏈接：https://www.datacamp.com/community/tutorials/sql-tutorial-query#importance
轉(zhuǎn)載請注明出自：葡萄城控件
重慶分公司
重慶分公司
