一道SQL面試題,為什麼能淘汰494位候選人

數據分析那些事
10 min readSep 2, 2021

--

文章轉載自公眾號:有关SQL

文章來源:https://mp.weixin.qq.com/s/1xowxoxaU5GH0z345W1_JQ

一覺醒來,發現大家在討論一道來自外企面試時的 SQL 題,聽說刷掉了很多人。

我對程式碼有潔癖,看到扭捏成一坨的 SQL, 忍不住拿到 Visual Studio Code 裡,用 poorman’s sql formatter 給 PS 下。

就像發網路動態,任何不經濾鏡圖,從不發。男孩女孩子們都懂的!
以下是整理後的程式碼,顏值高很多:

面試官提問,把第一段 SQL 改為第二段後,為什麼效能會有如此之大的提高,最佳化邏輯是什麼。

數據君獻給你十秒鐘思考一下

…..

OK,彙總一下,大家對這道題的最佳化邏輯:

1. user 表上有 age 的索引
2.user 表上有 age 的索引,還有 id 覆蓋索引
3.第二段的子查詢不用回表
4.第一段 SQL 執行了全表掃描
5.更有朋友質疑了第二段的效能提高:
6.沒有 order by,結果亂序,易產 bug
7.第一段 SQL 重跑下,應該 0 秒就出結果
8.除非是查詢快取,第二段效率未必高
9.MySQL最佳化器真笨,為什麼不直接跳到第 100000 條,白白浪費讀取那麼多資料

回答都很精彩,質疑也都有理有據。可以看得出來,能回答出一二的朋友,資料庫功底都很棒。

回到題目上來,要回答好這道 SQL,特別考驗資料庫的底層認知。僅僅從語法角度,這一題不難,無非是子查詢 + inner join 的考察。

從資料庫體系結構上回答,這一題就比較複雜。還要考慮到 MySQL 的產品特性,比如 MySQL 8 , 有些關係型資料庫的理論,在這裡就行不通,比如查詢快取。

據我有限的認識,這道題考察了這些方面:

資料庫的資料頁結構
資料庫的索引頁結構
查詢最佳化器的原理
資料頁,索引頁訪問演算法
資料庫快取設計
資料庫併發控制
資料庫引導最佳化器的方法
資料庫執行計劃

在繼續閱讀之前,請各位看官,自備清茶或咖啡,以免讀到乾渴而放棄。準備好了,咱們就開始。

資料庫的資料頁結構

資料頁是資料庫的底層儲存單元,資料庫的資料頁結構,並非想象的那麼難。用作業本來比喻,就很好理解。小時候寫作業,大家都用的本子,應該都還印象挺深吧。

田字格語文字與數學用作業本

在這樣的本子裡寫字的大小小,或者隔行寫,都會影響這一頁的資訊密度。明明可以用一頁紙寫完,寫的字兒大了,寫的稀疏了,行與行之間還有空一兩行,就會加大資訊密度的間隙。

資料庫的資料頁也一樣。它從上到下,寫滿了byte(位元組),或者為了 insert 速度和減少行溢位,中間空幾行。

這樣的資料頁,組合起來,就成了儲存一張表的結構。資料量越大,資料頁也越多。如果沒有很好的設計欄位長度,儲存的時候,也沒有安排的緊密些,那麼原本儲存1萬行的資料,就有可能需要10萬行的空間。

上兩圖就很好的解釋了,空間安排的重要性,這和在作業本上寫作業一個道理。

寫作業講完了,我們來講講讀。

如果你打算從頭到尾去讀你的作業本,想必會花很多時間,才能找到你想要的曾經寫過的特別佩服自己的那段話,或者公式推理。此時,有兩種方法,可以幫你:

1. 一種,一開始寫作業,就把字兒寫得小一些,把空行都寫上字兒,這樣把 14 頁的作業本,濃縮成 2 頁,自然翻的頁數少了;

2. 另外拿一個本子,把每頁的關鍵字記下來,比如螃蟹在第1,3,5頁;冰激淋在第2,4,6頁;遊戲機在7,8,9頁。這樣,找起來就少翻幾頁。

類比回到題目中,第一段 SQL 和第二段 SQL,在沒有索引的情況下(假設你沒有索引的概念),那麼第二種寫法,反而更慢一些。大家都是在尋找 age=10 的資料,而第二段SQL,找完之後,還要再找這 10 條資料所在資料頁上的其他資料。相當於你翻遍作業本,好不容易找到你想到的那段話,和數學公式,發現老師還要求你把那一頁上的其他段落或者應用例子,都找出來這樣你需要重複去讀,耗時會更多。

事實上,經過實驗,也的確如此。在 MySQL 5.5 中,emp_info 有588萬資料,沒有任何索引和主鍵。

這兒,我用 employees 庫代替。我並沒有原問題一模一樣的資料。

細心的朋友會發現,兩段 SQL 中都加了 SQL_NO_CAHE. 這是為了防止 Query Cache 的發生,增加說服力。MySQL 5.6 及以下版本都支援 Query Cache, 也就是查詢快取。

解釋下為什麼要設計 Query Cache。當二段 SQL 一模一樣,連續執行兩次時,第二次查詢耗時為0.。這是因為,最佳化器充分利用第一次的快取資料,秒出結果

這是怎麼做到的?

簡單來說,第一次執行的某條 SQL 會被最佳化器編譯為一段 hash 文字,且它的執行結果,會被儲存在記憶體中。

當一模一樣的 SQL 再次傳送到最佳化器時,會和儲存的 hash 值做個對比,如果一樣,就直接返回記憶體中的結果,而不需要再次執行。

這功能,想想都興奮。但也有弊端,能重複利用快取,必須是底層資料沒有變化,一旦變化了,那麼結果就會不對,對於第二次傳送 SQL 命令的使用者來說,就產生了資料不一致。

在一個非常繁忙的 OLTP 應用中,資料更新出乎你想象的快,查詢快取往往頃刻間就會失效。與其維護這麼段失效的記憶體,不如不維護,空出來乾點別的事,多好。於是 MySQL 8 就廢棄了它。

在本例中,加上 SQL_NO_CACHE 這樣的 hint 後,就是要排除利用查詢快取帶來最佳化的可能。這樣,每次執行都重新走一遍解析,最佳化到取數。保證實驗的公平性。

我把這 588萬資料,匯入 MySQL 8 版本中,同樣執行上面的 SQL,奇蹟就來了

沒想到 MySQL 8 在預設配置下,比 MySQL 5.5 還 “健忘”。翻過的作業,居然一點都不記得。

看執行計劃知曉,子查詢和外層查詢,雖然訪問同一個表,但卻當成兩個表來處理。至此,大家可以清楚的看到,第二種 SQL 不經最佳化,效能還不如第一種寫法。

資料庫的索引頁結構

剛剛,在講述提高查詢效率的時候,用到了 2 個方法。這兩個方法,在資料庫中,用索引來實現了。

假設,在作業本上,每一頁都寫了一篇小散文。我用另外一個本兒,按照關鍵字,記錄這些關鍵字在作業本中對應出現的頁碼和行號:

螃蟹:
第 1 頁,第 4 行;
第 3 頁,第 6 行;
第 5 頁,第 8 行

冰激淋:
第 2 頁,第 1 行;
第 4 頁,第 9 行;
第 6 頁,第 5 行

於是,原本按照從作業本,一頁頁尋找螃蟹,需要翻完所有頁,才能找全,現在有了索引本,一頁3行,就搞定。回到面試題來,看第二段 SQL,要找100010 行資料,在索引中找,和在全表中找,消耗的時間,就不在同一個數量級了。

具體來細說。在作業本上寫小作文,除了螃蟹,冰激淋等關鍵字,肯定還有很多很多其他詞語,比如“小妹生日那天,我送給她 2 盒冰激凌,6 只螃蟹,還有 10 多玫瑰”。這樣一來,一頁上只出現一個螃蟹,翻完整個本兒,才知道有 5 頁是包含螃蟹兩字的。

那 user 這張表,也一樣,可能有 10 個欄位,每個資料頁能存上 100 條資料,而每過 10 頁,才有一個 age=20 的使用者,那麼 100000 條資料,可能就被稀釋在 1000000 個數據頁中。

但索引頁就不一樣了,100000 個 age=10, 就在 100000行上,每個索引頁能存 1000 條,那麼 1000 頁索引頁也就存完了。

透過對比,至少有 1000000/1000 即 1000 倍的時間節省了。

以上只是假設,真實情況,要複雜的多。

有索引的地方,並不簡單。因為索引最大的風險,在於回表。

什麼是回表?

根據關鍵字”螃蟹”,去找哪一頁出現過它,這是索引乾的活。但依據”螃蟹”這個關鍵字,進一步找到作文中的主角,比如”小妹”,那索引就做不到了。只能翻開作業本,去每一頁包含”螃蟹”的作文中,去找。這種情況,就是回表。

可見,回表又增加了一次操作,會增加耗時。

而第一段 sql, 比起第二段,增加了回表的次數。因為並沒指定按照什麼去排序,這就是最佳化器矛盾的地方了。假如加上按照 id 排序,就和第二段一樣了。

舉個例子:

看來 MySQL 5.5 最佳化器在這裡做了判斷,以 age 為排序,這樣最大的消耗在索引訪問上。

假設要以 employees_info 其中另外的 from_date 來排序,看下結果:

這樣一來,不僅僅要把索引 age=20 的資料全部找遍,還需回表抓下 from_date 的值。這就是回表的代價。

在 MySQL 8 上,這段 SQL 已經無法跑了,52s 才出結果。

回到寫法的對比上來:

比起 63ms, 快1倍。於是,第二種寫法,在有索引的情況下,優勢就來了。
無論在 MySQL 5.5 還是 MySQL 8, 第二種寫法,都具有效能優勢。但是,這道題,是具有歧義的。沒有 Order By, Limit 的意義在這兩種寫法中,就不同。

改成這樣,就有對比性了:

這樣,第二段 SQL 的優勢才能說得清楚。相信看完上面的解釋,原理就很清晰了。

文章轉載自公眾號:有关SQL

文章來源:https://mp.weixin.qq.com/s/1xowxoxaU5GH0z345W1_JQ

我是「數據分析那些事」。常年分享數據分析乾貨,不定期分享好用的職場技能工具。各位也可以關注我的Facebook,按讚我的臉書並私訊「10」,送你十週入門數據分析電子書唷!期待你與我互動起來~

--

--

數據分析那些事

這是一個專注於數據分析職場的內容部落格,聚焦一批數據分析愛好者,在這裡,我會分享數據分析相關知識點推送、(工具/書籍)等推薦、職場心得、熱點資訊剖析以及資源大盤點,希望同樣熱愛數據的我們一同進步! 臉書會有更多互動喔:https://www.facebook.com/shujvfenxi/