深度 | 如何玩轉PG查詢處理與執行器算法

作者介紹

孫旭,騰訊云高級工程師。10年數據庫內核研發經驗,熟悉PostgreSQL、Tera>

一、導語

數據庫查詢處理(Query Processing)是數據庫比較核心的技術,也是距離用戶最近的子系統。數據庫系統在除了實現事務的隔離界別外,還需要在SQL上做到一定程度的兼容,因為數據庫本身就是在做查詢處理,很多的內核模塊工作都是為了支持這個功能。本文將簡要介紹一下PostgreSQL的查詢處理過程。 

二、關系代數與SQL(結構化查詢語言)

大家在學校學到的可能更多的是關系代數(Relational Algebra),它定義了一組在關系(Relation)上進行操作的操作符。關系代數的操作數是關系(即,數據庫中的二維表),其結果也是關系。操作符包含如下幾類:

  • 集合操作符:交,并,差;

  • 過濾/投影;

  • 連接;

  • 別名(alias);

  • 一些擴展的操作符,例如:分組,去重,Aggregate。

除了關系代數,還有一種描述二維關系表的操作方法:DataLog(Database Logic)。這種方式相對來說比較強大,關系代數的操作符都可以用它來表述,但是有些關系的操作是關系代數表示不了的,只能用DataLog來表述,比如:遞歸查詢。

直接使用關系代數對數據庫操作比較晦澀,難度比較高,因此,今天的商業數據庫都實現了一種更高級的查詢語言——SQL(Structured Query Language),在表達上更加簡潔易懂,也更容易學習。

實際上,在數據庫系統內部,SQL語句也是被轉化成對應關系代數的操作符,然后再進行處理,只是這些工作對最終用戶來說是不可見的。其實,關系型數據庫直接的“本地語言”是關系代數,SQL語言只是人類與關系數據庫進行交流的“更加便捷的”橋梁。

可能大家有疑問,為何使用SQL作為交流橋梁,而不是用C、Java或者Python作為數據庫的查詢語言?

因為一個較短的SQL可以完成千百行C或者Java的工作,特別是在訪問一些層次化的數據模型(例如:Oracle的層次查詢,一條語句可以把層次結構輸出出來;PostgreSQL的WITH-RECURSIVE語句也可以完成類似的功能)。

更加重要的是,數據庫內核在實現SQL查詢的時候,可以對SQL進行特定的優化,產生更加有效的訪問方法,這些都是高級語言不太可能具備的功能。

三、PostgreSQL查詢處理流程

從用戶在客戶端發送一條SQL語句,經過網絡傳輸給PostgreSQL進行處理、執行,其流程經過如下幾個步驟:

1、語法分析

SQL字符串可以認為是一個大的正則式,語法分析來檢查這個大的“正則式”是否match定義好的規則。

在PostgreSQL中,pg_parse_query是語法分析的入口函數,實際上由scan.l(Flex文件)以及gram.y(Bison文件)完成語法檢查。

scan.l是詞法分析,將輸入SQL分解一個個的Token,輸入到gram.y中進行規則匹配。gram.y中定義了所有SQL類型的語法規則以及操作符的優先級和結合律,例如,下段代碼定義了操作符的優先級和結合規則:

下段代碼定了語法規則:

語法分析結束后,以查詢(SELECT)為例,返回的結構體是SelectStmt,它會作為作為語義分析模塊的輸入。SelectStmt保存了SQL語句中的各個語法子部分,例如:from子句,投影列,group子句等,從其定義可以看出更多細節:

2、語法檢查

parse_analyze()函數是這一步的入口函數,根據不同的語句類型調用transformXXXXStmt()函數進行分析處理。對于SelectStmt,調用的transformSelectStmt(),對于DeleteStmt調用transformDeleteStmt()。在這一步將會:

  • 檢查表是否存在,列是否合法,將表、排序列、投影列等轉化為內部對象ID;

  • SQL語義是否正確合法。

比如:Aggregate 函數不能用在WHERE中。如下查詢:

select 1 from x where max(x2) > 1;

調整聚集函數在適當的層次中計算,如下查詢:

select (select max(x.x2) from y) from x;

max(x.x2)在SQL語義上應該是在最外層查詢中計算,而不是將x.x2傳入到內層子查詢,在內層子查詢中計算Aggregate函數max()的值。而對于如下查詢:

select (select max(x.x2+y.x2) from y) from x;

max(x.x2+y.x2)是在內層子查詢中被計算,而不是作為外層查詢的Aggregate函數。

經過語義檢查,會將SelectStmt變形為Query結構,作為查詢重寫的輸入。Query結構包含的部分與SelectStmt類似,只不過內容更加豐富:

  • 保存的都是數據庫內部的對象信息;

  • 一些flag標記,表明是否包含:Aggregate函數、窗口函數、SubLink子查詢等;

  • 確定了表達式所在的Query層次。

之前提到過,數據庫內核處理SQL時都是轉化成關系代數相關的元素,這個在Query結構體中可以看到這點:

例如:

  • 關系代數的投影是:targetList;

  • 關系代數的過濾/join是:jointree;

  • 關系代數的Aggregate是:targetList;

  • 關系代數的分組:groupClause;

  • 關系代數的sort是:sortClause。

后續所有的工作都是基于上面的元素進行。

3、查詢重寫

根據用戶定義的規則對查詢進行重寫,實際是對Query結構里面的成員進行修改或替換,這些規則可以使用CREATE RULE創建。如果用戶在查詢對應的表上沒有規則,此步跳過。

4、查詢優化

查詢優化是比較復雜子系統,通常稱這個模塊是“優化器”,也用來衡量數據庫系統優秀的一個方面。在數據庫領域另一個復雜的子系統是事務處理,這里也不做展開。

PostgreSQL在這一步的輸入是Query對象,入口函數是planner(),輸出查詢計劃(Query Plan),查詢計劃是指導查詢如何被執行以及用何種方法執行的一種結構,通常是樹形結構。

優化器做的主要工作就是對Query結構的各個語法部分,選擇較優的執行算法,輸出較優的執行計劃。在PostgreSQL中,通常分成如下幾步:

1)子查詢處理

在PostgreSQL內部有2類的子查詢:一種在from語句后面稱為SubQuery,另一種在作為表達式的一部分,可以出現在targetList,過濾條件,連接條件中,稱為sub-link。

這兩種都可以統稱為Sub-Select,而優化器在這一步會進行Sub-Select Elimination:將子查詢上拉到頂層查詢,消除子查詢。

這樣做可以減少查詢層數,增加上層表的個數,從而增加join順序的搜索空間,有助于找到較優的連接順序。以sub-link為例,說明一下這個步驟的工作。對于查詢:

select * from x where x.x2 in (select y.x2 from y);

PostgreSQL在這步可以將IN語句轉化成Semi-Join,原來的O(m*n)的查找算法簡化為O(1)HASH-JOIN算法。

這里執行計劃并沒有使用Hash Semi-Join,是因為inner plantree用了group hashagg進行了去重,所以原來的Semi-Join可以進一步優化為Hash Join,這種優化進一步擴大了Join順序搜索空間。

2)執行表達式預處理

在這一步,會將targetList,過濾條件等列修改為對基表的引用;對表達式里面的SubLink遞歸調用優化器優先進行優化;計算表達式里面的常量表達式等。

3)移除無用的GROUP BY列

如果內核可以確定GROUP BY中的一些屬性集合Y函數依賴于其他屬性集合X,那么可以刪除GROUP BY中的屬性集合Y。函數依賴檢查工作由check_functional_grouping完成。這樣可以減少分組計算代價。

4)Reduce outer join

將某些OUTER JOIN轉化為INNER JOIN。

5)選擇優化的Join順序

在這一步完成主要完成:條件的下推,基于連接條件生成等價類,以及通過動態規劃選擇較優的JOIN順序。從整體來看,JOIN順序的選擇是Condition-Driven,而不是完全的對所有的表進行排列組合求解。例如對于查詢:

select * from r, p, q where r1 = (p1+q1) and r2=q2;

通常我們可能認為r和q在r2=q2的條件進行連接,然后與p在r1 = (p1+q1)上進行連接;但是PostgreSQL內核在也會做這樣的嘗試:將p和q進行product join,再與r在條件r1 = (p1+q1) and r2=q2;進行連接,p和q之所以可以連接完全是由r1 = (p1+q1)決定的。

6)其他子句優化處理

做完Join Plan之后,再針對GROUP BY、Aggregate、ORDER BY、LIMIT等子句進行處理。以GROUP BY為例,在PostgreSQL內部,實現GROUP BY的有2個算法:Sort Group By以及 HashAgg Group By,通過函數cost_group以及cost_agg分別來計算二者代價,選擇較優的算法執行。

完成這些這些步驟后,調用set_plan_references()以及SS_finalize_plan()函數最后處理參數和變量引用后,就可以輸出最終的查詢計劃(Execution Query Plan)了。查詢計劃由很多節點組成:投影、掃描、連接、Aggregate、GROUP BY、排序等,從這些名稱也可以看出他們就是關系代數的操作符,它們會被傳給查詢執行組件進行執行。如下查詢計劃示例:

5、查詢執行

這是查詢處理的最后一步,將優化器輸出的執行計劃,進行初始化、執行。查詢執行子系統我們一般稱為執行器。執行過程有ExecutorStart、ExecutorRun、ExecutorFinish這三個入口函數,分別完成對查詢計劃的初始化,執行,以及清理。在這個過程中會訪問數據庫的其他子系統,如:事務系統、存儲系統、日志系統。

以上就是在PostgreSQL內核中對一個查詢處理的整個生命周期,基本可以了解到一個SQL字符串在數據庫內核中是如何一步步被解析,直到到執行的基本過程。

上文中描述的一些方法和理論不僅僅在PostgreSQL數據庫有效,也可以推導到其他數據庫系統中。

四、PostgreSQL執行器算法之SeqScan

上文講述了數據庫內核中查詢處理的基本流程,現在我們先展開講述執行器算法。

數據庫的執行器包含了很多個算子的執行算法,比較簡單的一種就是SeqScan,就是從按照順序(一般是存儲順序)對表進行掃描。

1、頁面結構

PostgreSQL頁面存儲與大多數數據庫的類似,包含:頁面頭,ItemId 數組,以及Item(元組),布局如下:

其中PageHeader包含了頁面LSN,ItemId數組最后一個元素的頁面偏移(pd_lower),第一條元組在頁面內偏移(pd_upper),以及其他字段。

2、順序掃描算法

PostgreSQL的順序掃描的入口函數是SeqNext,每次執行這個函數會返回一條元組,主要工作是由heapgettup:

1)初始化掃描過程

初始化掃描過程就是設置HeapScanDesc對象,主要設置初始掃描的頁面,一般從0號頁面的第一個元組開始,即scan->rs_startblock是0。

在PostgreSQL的掃描過程有一個優化,即sync_scan,這個特性允許當前的掃描從表的中間頁面開始掃描,這個頁面是其他掃描進程填寫到共享內存,由ss_report_location完成,代表這些頁面剛剛被訪問過,如果當前掃描從這些頁面開始,那么可以直接在內存中訪問到,從而減少存儲讀取頁面的IO次數,提升性能。

每次更新表的sync start page時,需要遍歷整個list。為了減少這個list的訪問,每隔SYNC_SCAN_REPORT_INTERVAL個頁面才去更新list,這個數值是128 * 1024 / BLCKSZ。

2)讀取頁面進行掃描

按照頁面結構掃描頁面。首先讀取頁面頭(PageHeaderData)的pd_linp成員,這是一個Offset數組(ItemIdData),記錄了元組在頁面上的偏移(lp_off)。

后續的主要邏輯是遍歷pd_linp數組,通過offset+page地址獲取到元組內存地址。然后對元組做可見性判斷。邏輯如下:

HeapTupleSatisfiesVisibility進行元組可見性判斷,PostgreSQL是MVCC實現的事務隔離,這個函數就是MVCC的入口邏輯。

3)讀取下一個頁面繼續進行掃描

繼續讀取后續頁面進行掃描。

所有的掃描狀態保存在HeapScanDesc,下次掃描的時候,可以從上次的狀態開始。


江湖召集令

9月27日-11月6日,騰訊云數據庫王者挑戰賽(點擊查看詳情) 等你挑戰!花幾分鐘參加比賽免費將??抱回家!

 

  • MacBook/iPhone 11/AirPods

  • 25臺Kindle

  • 8萬元騰訊云創業基金

  • MySQL之父 Michael Widenius 面對面交流

擁有與殿堂級大神的合影和親筆簽名書籍的你,

能讓隔壁碼農羨慕到流淚!

 

轉發下方海報參與活動可以獲得騰訊公仔和騰訊云數據庫購買直抵代金券,詳情請添加海報上機器人二維碼咨詢。

 

 比賽詳情&報名入口

請掃下方二維碼

↓↓活動報名直達 

免責聲明:本文僅代表文章作者的個人觀點,與本站無關。其原創性、真實性以及文中陳述文字和內容未經本站證實,對本文以及其中全部或者部分內容文字的真實性、完整性和原創性本站不作任何保證或承諾,請讀者僅作參考,并自行核實相關內容。

http://image99.pinlue.com/thumb/img_jpg/XS2esJew19aGAUfPQreNG0akqzyWUm3d9aJU91nAbTQw7t6vEOmxotPsIvXxJF9RWN1Flezsltg9n4BDvM1IOQ/0.jpeg
我要收藏
贊一個
踩一下
分享到
?
七星彩17142期号码预测