PostgreSQL的查詢處理過(guò)程是什么

這篇文章主要講解了“PostgreSQL的查詢處理過(guò)程是什么”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“PostgreSQL的查詢處理過(guò)程是什么”吧！

一、導(dǎo)語(yǔ)

數(shù)據(jù)庫(kù)查詢處理（Query Processing）是數(shù)據(jù)庫(kù)比較核心的技術(shù)，也是距離用戶最近的子系統(tǒng)。數(shù)據(jù)庫(kù)系統(tǒng)在除了實(shí)現(xiàn)事務(wù)的隔離界別外，還需要在SQL上做到一定程度的兼容，因?yàn)閿?shù)據(jù)庫(kù)本身就是在做查詢處理，很多的內(nèi)核模塊工作都是為了支持這個(gè)功能。

二、關(guān)系代數(shù)與SQL（結(jié)構(gòu)化查詢語(yǔ)言）

大家在學(xué)校學(xué)到的可能更多的是關(guān)系代數(shù)（Relational Algebra），它定義了一組在關(guān)系（Relation）上進(jìn)行操作的操作符。關(guān)系代數(shù)的操作數(shù)是關(guān)系（即，數(shù)據(jù)庫(kù)中的二維表），其結(jié)果也是關(guān)系。操作符包含如下幾類(lèi)：

• 集合操作符：交，并，差；

• 過(guò)濾/投影；

• 連接；

• 別名（alias）；

• 一些擴(kuò)展的操作符，例如：分組，去重，Aggregate。

除了關(guān)系代數(shù)，還有一種描述二維關(guān)系表的操作方法：DataLog（Database Logic）。這種方式相對(duì)來(lái)說(shuō)比較強(qiáng)大，關(guān)系代數(shù)的操作符都可以用它來(lái)表述，但是有些關(guān)系的操作是關(guān)系代數(shù)表示不了的，只能用DataLog來(lái)表述，比如：遞歸查詢。

直接使用關(guān)系代數(shù)對(duì)數(shù)據(jù)庫(kù)操作比較晦澀，難度比較高，因此，今天的商業(yè)數(shù)據(jù)庫(kù)都實(shí)現(xiàn)了一種更高級(jí)的查詢語(yǔ)言——SQL（Structured Query Language），在表達(dá)上更加簡(jiǎn)潔易懂，也更容易學(xué)習(xí)。

實(shí)際上，在數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)部，SQL語(yǔ)句也是被轉(zhuǎn)化成對(duì)應(yīng)關(guān)系代數(shù)的操作符，然后再進(jìn)行處理，只是這些工作對(duì)最終用戶來(lái)說(shuō)是不可見(jiàn)的。其實(shí)，關(guān)系型數(shù)據(jù)庫(kù)直接的“本地語(yǔ)言”是關(guān)系代數(shù)，SQL語(yǔ)言只是人類(lèi)與關(guān)系數(shù)據(jù)庫(kù)進(jìn)行交流的“更加便捷的”橋梁。

可能大家有疑問(wèn)，為何使用SQL作為交流橋梁，而不是用C、Java或者Python作為數(shù)據(jù)庫(kù)的查詢語(yǔ)言？

因?yàn)橐粋€(gè)較短的SQL可以完成千百行C或者Java的工作，特別是在訪問(wèn)一些層次化的數(shù)據(jù)模型（例如：Oracle的層次查詢，一條語(yǔ)句可以把層次結(jié)構(gòu)輸出出來(lái)；PostgreSQL的WITH-RECURSIVE語(yǔ)句也可以完成類(lèi)似的功能）。

更加重要的是，數(shù)據(jù)庫(kù)內(nèi)核在實(shí)現(xiàn)SQL查詢的時(shí)候，可以對(duì)SQL進(jìn)行特定的優(yōu)化，產(chǎn)生更加有效的訪問(wèn)方法，這些都是高級(jí)語(yǔ)言不太可能具備的功能。

三、PostgreSQL查詢處理流程

從用戶在客戶端發(fā)送一條SQL語(yǔ)句，經(jīng)過(guò)網(wǎng)絡(luò)傳輸給PostgreSQL進(jìn)行處理、執(zhí)行，其流程經(jīng)過(guò)如下幾個(gè)步驟：

1、語(yǔ)法分析

SQL字符串可以認(rèn)為是一個(gè)大的正則式，語(yǔ)法分析來(lái)檢查這個(gè)大的“正則式”是否match定義好的規(guī)則。

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

scan.l是詞法分析，將輸入SQL分解一個(gè)個(gè)的Token，輸入到gram.y中進(jìn)行規(guī)則匹配。gram.y中定義了所有SQL類(lèi)型的語(yǔ)法規(guī)則以及操作符的優(yōu)先級(jí)和結(jié)合律，例如，下段代碼定義了操作符的優(yōu)先級(jí)和結(jié)合規(guī)則：

下段代碼定了語(yǔ)法規(guī)則：

語(yǔ)法分析結(jié)束后，以查詢（SELECT）為例，返回的結(jié)構(gòu)體是SelectStmt，它會(huì)作為作為語(yǔ)義分析模塊的輸入。SelectStmt保存了SQL語(yǔ)句中的各個(gè)語(yǔ)法子部分，例如：from子句，投影列，group子句等，從其定義可以看出更多細(xì)節(jié)：

2、語(yǔ)法檢查

parse_analyze()函數(shù)是這一步的入口函數(shù)，根據(jù)不同的語(yǔ)句類(lèi)型調(diào)用transformXXXXStmt()函數(shù)進(jìn)行分析處理。對(duì)于SelectStmt，調(diào)用的transformSelectStmt()，對(duì)于DeleteStmt調(diào)用transformDeleteStmt()。在這一步將會(huì)：

• 檢查表是否存在，列是否合法，將表、排序列、投影列等轉(zhuǎn)化為內(nèi)部對(duì)象ID；

• SQL語(yǔ)義是否正確合法。

比如：Aggregate 函數(shù)不能用在WHERE中。如下查詢：

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

調(diào)整聚集函數(shù)在適當(dāng)?shù)膶哟沃杏?jì)算，如下查詢：

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

max(x.x2)在SQL語(yǔ)義上應(yīng)該是在最外層查詢中計(jì)算，而不是將x.x2傳入到內(nèi)層子查詢，在內(nèi)層子查詢中計(jì)算Aggregate函數(shù)max()的值。而對(duì)于如下查詢：

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

max(x.x2+y.x2)是在內(nèi)層子查詢中被計(jì)算，而不是作為外層查詢的Aggregate函數(shù)。

經(jīng)過(guò)語(yǔ)義檢查，會(huì)將SelectStmt變形為Query結(jié)構(gòu)，作為查詢重寫(xiě)的輸入。Query結(jié)構(gòu)包含的部分與SelectStmt類(lèi)似，只不過(guò)內(nèi)容更加豐富：

• 保存的都是數(shù)據(jù)庫(kù)內(nèi)部的對(duì)象信息；

• 一些flag標(biāo)記，表明是否包含：Aggregate函數(shù)、窗口函數(shù)、SubLink子查詢等；

• 確定了表達(dá)式所在的Query層次。

之前提到過(guò)，數(shù)據(jù)庫(kù)內(nèi)核處理SQL時(shí)都是轉(zhuǎn)化成關(guān)系代數(shù)相關(guān)的元素，這個(gè)在Query結(jié)構(gòu)體中可以看到這點(diǎn)：

例如：

• 關(guān)系代數(shù)的投影是：targetList；

• 關(guān)系代數(shù)的過(guò)濾/join是：jointree；

• 關(guān)系代數(shù)的Aggregate是：targetList；

• 關(guān)系代數(shù)的分組：groupClause；

• 關(guān)系代數(shù)的sort是：sortClause。

后續(xù)所有的工作都是基于上面的元素進(jìn)行。

3、查詢重寫(xiě)

根據(jù)用戶定義的規(guī)則對(duì)查詢進(jìn)行重寫(xiě)，實(shí)際是對(duì)Query結(jié)構(gòu)里面的成員進(jìn)行修改或替換，這些規(guī)則可以使用CREATE RULE創(chuàng)建。如果用戶在查詢對(duì)應(yīng)的表上沒(méi)有規(guī)則，此步跳過(guò)。

4、查詢優(yōu)化

查詢優(yōu)化是比較復(fù)雜子系統(tǒng)，通常稱這個(gè)模塊是“優(yōu)化器”，也用來(lái)衡量數(shù)據(jù)庫(kù)系統(tǒng)優(yōu)秀的一個(gè)方面。在數(shù)據(jù)庫(kù)領(lǐng)域另一個(gè)復(fù)雜的子系統(tǒng)是事務(wù)處理，這里也不做展開(kāi)。

PostgreSQL在這一步的輸入是Query對(duì)象，入口函數(shù)是planner()，輸出查詢計(jì)劃（Query Plan），查詢計(jì)劃是指導(dǎo)查詢?nèi)绾伪粓?zhí)行以及用何種方法執(zhí)行的一種結(jié)構(gòu)，通常是樹(shù)形結(jié)構(gòu)。

優(yōu)化器做的主要工作就是對(duì)Query結(jié)構(gòu)的各個(gè)語(yǔ)法部分，選擇較優(yōu)的執(zhí)行算法，輸出較優(yōu)的執(zhí)行計(jì)劃。在PostgreSQL中，通常分成如下幾步：

1）子查詢處理

在PostgreSQL內(nèi)部有2類(lèi)的子查詢：一種在from語(yǔ)句后面稱為SubQuery，另一種在作為表達(dá)式的一部分，可以出現(xiàn)在targetList，過(guò)濾條件，連接條件中，稱為sub-link。

這兩種都可以統(tǒng)稱為Sub-Select，而優(yōu)化器在這一步會(huì)進(jìn)行Sub-Select Elimination：將子查詢上拉到頂層查詢，消除子查詢。

這樣做可以減少查詢層數(shù)，增加上層表的個(gè)數(shù)，從而增加join順序的搜索空間，有助于找到較優(yōu)的連接順序。以sub-link為例，說(shuō)明一下這個(gè)步驟的工作。對(duì)于查詢：

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

PostgreSQL在這步可以將IN語(yǔ)句轉(zhuǎn)化成Semi-Join，原來(lái)的O(m*n)的查找算法簡(jiǎn)化為O(1)HASH-JOIN算法。

這里執(zhí)行計(jì)劃并沒(méi)有使用Hash Semi-Join，是因?yàn)閕nner plantree用了group hashagg進(jìn)行了去重，所以原來(lái)的Semi-Join可以進(jìn)一步優(yōu)化為Hash Join，這種優(yōu)化進(jìn)一步擴(kuò)大了Join順序搜索空間。

2）執(zhí)行表達(dá)式預(yù)處理

在這一步，會(huì)將targetList，過(guò)濾條件等列修改為對(duì)基表的引用；對(duì)表達(dá)式里面的SubLink遞歸調(diào)用優(yōu)化器優(yōu)先進(jìn)行優(yōu)化；計(jì)算表達(dá)式里面的常量表達(dá)式等。

3）移除無(wú)用的GROUP BY列

如果內(nèi)核可以確定GROUP BY中的一些屬性集合Y函數(shù)依賴于其他屬性集合X，那么可以刪除GROUP BY中的屬性集合Y。函數(shù)依賴檢查工作由check_functional_grouping完成。這樣可以減少分組計(jì)算代價(jià)。

4）Reduce outer join

將某些OUTER JOIN轉(zhuǎn)化為INNER JOIN。

5）選擇優(yōu)化的Join順序

在這一步完成主要完成：條件的下推，基于連接條件生成等價(jià)類(lèi)，以及通過(guò)動(dòng)態(tài)規(guī)劃選擇較優(yōu)的JOIN順序。從整體來(lái)看，JOIN順序的選擇是Condition-Driven，而不是完全的對(duì)所有的表進(jìn)行排列組合求解。例如對(duì)于查詢：

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

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

6）其他子句優(yōu)化處理

做完Join Plan之后，再針對(duì)GROUP BY、Aggregate、ORDER BY、LIMIT等子句進(jìn)行處理。以GROUP BY為例，在PostgreSQL內(nèi)部，實(shí)現(xiàn)GROUP BY的有2個(gè)算法：Sort Group By以及 HashAgg Group By，通過(guò)函數(shù)cost_group以及cost_agg分別來(lái)計(jì)算二者代價(jià)，選擇較優(yōu)的算法執(zhí)行。

完成這些這些步驟后，調(diào)用set_plan_references()以及SS_finalize_plan()函數(shù)最后處理參數(shù)和變量引用后，就可以輸出最終的查詢計(jì)劃（Execution Query Plan）了。查詢計(jì)劃由很多節(jié)點(diǎn)組成：投影、掃描、連接、Aggregate、GROUP BY、排序等，從這些名稱也可以看出他們就是關(guān)系代數(shù)的操作符，它們會(huì)被傳給查詢執(zhí)行組件進(jìn)行執(zhí)行。如下查詢計(jì)劃示例：

5、查詢執(zhí)行

這是查詢處理的最后一步，將優(yōu)化器輸出的執(zhí)行計(jì)劃，進(jìn)行初始化、執(zhí)行。查詢執(zhí)行子系統(tǒng)我們一般稱為執(zhí)行器。執(zhí)行過(guò)程有ExecutorStart、ExecutorRun、ExecutorFinish這三個(gè)入口函數(shù)，分別完成對(duì)查詢計(jì)劃的初始化，執(zhí)行，以及清理。在這個(gè)過(guò)程中會(huì)訪問(wèn)數(shù)據(jù)庫(kù)的其他子系統(tǒng)，如：事務(wù)系統(tǒng)、存儲(chǔ)系統(tǒng)、日志系統(tǒng)。

以上就是在PostgreSQL內(nèi)核中對(duì)一個(gè)查詢處理的整個(gè)生命周期，基本可以了解到一個(gè)SQL字符串在數(shù)據(jù)庫(kù)內(nèi)核中是如何一步步被解析，直到到執(zhí)行的基本過(guò)程。

上文中描述的一些方法和理論不僅僅在PostgreSQL數(shù)據(jù)庫(kù)有效，也可以推導(dǎo)到其他數(shù)據(jù)庫(kù)系統(tǒng)中。

四、PostgreSQL執(zhí)行器算法之SeqScan

上文講述了數(shù)據(jù)庫(kù)內(nèi)核中查詢處理的基本流程，現(xiàn)在我們先展開(kāi)講述執(zhí)行器算法。

數(shù)據(jù)庫(kù)的執(zhí)行器包含了很多個(gè)算子的執(zhí)行算法，比較簡(jiǎn)單的一種就是SeqScan，就是從按照順序（一般是存儲(chǔ)順序）對(duì)表進(jìn)行掃描。

1、頁(yè)面結(jié)構(gòu)

PostgreSQL頁(yè)面存儲(chǔ)與大多數(shù)數(shù)據(jù)庫(kù)的類(lèi)似，包含：頁(yè)面頭，ItemId 數(shù)組，以及Item（元組），布局如下：

其中PageHeader包含了頁(yè)面LSN，ItemId數(shù)組最后一個(gè)元素的頁(yè)面偏移（pd_lower），第一條元組在頁(yè)面內(nèi)偏移（pd_upper），以及其他字段。

2、順序掃描算法

PostgreSQL的順序掃描的入口函數(shù)是SeqNext，每次執(zhí)行這個(gè)函數(shù)會(huì)返回一條元組，主要工作是由heapgettup：

1）初始化掃描過(guò)程

初始化掃描過(guò)程就是設(shè)置HeapScanDesc對(duì)象，主要設(shè)置初始掃描的頁(yè)面，一般從0號(hào)頁(yè)面的第一個(gè)元組開(kāi)始，即scan->rs_startblock是0。

在PostgreSQL的掃描過(guò)程有一個(gè)優(yōu)化，即sync_scan，這個(gè)特性允許當(dāng)前的掃描從表的中間頁(yè)面開(kāi)始掃描，這個(gè)頁(yè)面是其他掃描進(jìn)程填寫(xiě)到共享內(nèi)存，由ss_report_location完成，代表這些頁(yè)面剛剛被訪問(wèn)過(guò)，如果當(dāng)前掃描從這些頁(yè)面開(kāi)始，那么可以直接在內(nèi)存中訪問(wèn)到，從而減少存儲(chǔ)讀取頁(yè)面的IO次數(shù)，提升性能。

每次更新表的sync start page時(shí)，需要遍歷整個(gè)list。為了減少這個(gè)list的訪問(wèn)，每隔SYNC_SCAN_REPORT_INTERVAL個(gè)頁(yè)面才去更新list，這個(gè)數(shù)值是128 * 1024 / BLCKSZ。

2）讀取頁(yè)面進(jìn)行掃描

按照頁(yè)面結(jié)構(gòu)掃描頁(yè)面。首先讀取頁(yè)面頭（PageHeaderData）的pd_linp成員，這是一個(gè)Offset數(shù)組（ItemIdData），記錄了元組在頁(yè)面上的偏移（lp_off）。

后續(xù)的主要邏輯是遍歷pd_linp數(shù)組，通過(guò)offset+page地址獲取到元組內(nèi)存地址。然后對(duì)元組做可見(jiàn)性判斷。邏輯如下：

HeapTupleSatisfiesVisibility進(jìn)行元組可見(jiàn)性判斷，PostgreSQL是MVCC實(shí)現(xiàn)的事務(wù)隔離，這個(gè)函數(shù)就是MVCC的入口邏輯。

3）讀取下一個(gè)頁(yè)面繼續(xù)進(jìn)行掃描

繼續(xù)讀取后續(xù)頁(yè)面進(jìn)行掃描。

所有的掃描狀態(tài)保存在HeapScanDesc，下次掃描的時(shí)候，可以從上次的狀態(tài)開(kāi)始。

感謝各位的閱讀，以上就是“PostgreSQL的查詢處理過(guò)程是什么”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)PostgreSQL的查詢處理過(guò)程是什么這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！