[[213014]]

一棵完成 transform 和 rewrite 操作的查詢樹是否是一棵***的查詢樹？如果不是，那么又該如何對(duì)該查詢樹進(jìn)行優(yōu)化？而優(yōu)化所使用的策略正是本文要討論的重點(diǎn)內(nèi)容，而且優(yōu)化部分也是整個(gè)查詢引擎的難點(diǎn)。

子鏈接（SubLink）如何優(yōu)化？子查詢（SubQuery）又如何處理？對(duì)表達(dá)式（Expression）如何進(jìn)行優(yōu)化？如何尋找***的查詢計(jì)劃（Cheapest Plan）？哪些因素會(huì)影響 JOIN 策略（Join Strategies）的選擇，而這些策略又是什么？查詢代價(jià)（Cost）又是如何估算的？何時(shí)需對(duì)查詢計(jì)劃進(jìn)行物化（Plan Materialization）處理等一系列的問題。

在查詢計(jì)劃的優(yōu)化過(guò)程中，對(duì)不同的語(yǔ)句類型有著不同的處理策略：

（1）對(duì)工具類語(yǔ)句（例如，DML、DDL 語(yǔ)句），不進(jìn)行更進(jìn)一步的優(yōu)化處理。

（2）當(dāng)語(yǔ)句為非工具語(yǔ)句時(shí)，PostgreSQL 使用 pg_plan_queries 對(duì)語(yǔ)句進(jìn)行優(yōu)化。

與前面一樣，PostreSQL 也提供定制化優(yōu)化引擎接口，我們可以使用自定義優(yōu)化器 planner_hook，或者使用標(biāo)準(zhǔn)化優(yōu)化器 standard_planner。

Pg_plan_queries 的函數(shù)原型如下所示。

邏輯優(yōu)化——整體架構(gòu)介紹

在未使用第三方提供的優(yōu)化器時(shí)，PostgreSQL 將 planner 函數(shù)作為優(yōu)化的入口函數(shù)，并由函數(shù) subquery_planner 來(lái)完成具體的優(yōu)化操作。從下圖中的 Call Stack 我們可以看出 planner 與 subquery_planner 之間的調(diào)用關(guān)系。

函數(shù)以查詢樹作為輸入?yún)?shù)，并以優(yōu)化后語(yǔ)句作為返回值。

在 standard_planner 中，首先處理 “DECLARE CURSOR stmt” 形式的語(yǔ)句，即游標(biāo)語(yǔ)句，并設(shè)置 tuple_fraction 值。那么 tuple_fraction 又是什么呢？

tuple_fraction 描述我們期望獲取的元組的比例，0 代表我們需要獲取所有的元組；當(dāng) tuple_factionÎ(0,1) 時(shí)，表明我們需要從滿足條件的元組中取出 tuple_faction 這么多比例的元組；當(dāng) tuple_factionÎ [1,+¥ ) 時(shí)，表明我們將按照所指定的元組數(shù)進(jìn)行檢索，例如，LIMIT 語(yǔ)句中所指定的元組數(shù)。

完成對(duì) tuple_faction 的設(shè)置后，進(jìn)入后續(xù)優(yōu)化流程，subquery_planner 的函數(shù)原型如下所示。

這里也許你也許會(huì)迷惑，為什么是 subquery_planner 呢？從名字上看該函數(shù)像是用來(lái)處理子查詢，那么為什么用來(lái)作為整個(gè)查詢語(yǔ)句優(yōu)化的入口呢（Primary Entry Point）？

子查詢語(yǔ)句作為查詢語(yǔ)句的一部分，很大程度上與父查詢具有相似的結(jié)構(gòu)，同時(shí)兩者在處理方式和方法上也存在著一定的相似性：子查詢的處理流程可以在對(duì)其父查詢的過(guò)程中使用。例如，本例中的子查詢語(yǔ)句 SELECT sno FROM student WHERE student.classno = sub.classno，其處理方式與整個(gè)查詢語(yǔ)句一樣。因此，使用 subquery_planner 作為我們查詢優(yōu)化的入口，雖然從函數(shù)名上來(lái)看其似乎是用于子查詢語(yǔ)句的處理。 

由 gram.y 中給出的 SelectStmt 的定義可以看出，其中包括了諸如 WINDOWS、HAVING、ORDER BY、GROUP BY 等子句。那du么 subquery_planner 函數(shù)似乎也應(yīng)該有相應(yīng)于這些語(yǔ)句的優(yōu)化處理。就這點(diǎn)而言，subquery_planner 與原始語(yǔ)法樹到查詢樹的轉(zhuǎn)換所采取的處理方式相似。根據(jù)上述分析，我們可給出如下所示的 subquery_planner 的函數(shù)原型。

按照上述給出的原型，只要完成假定的 process_xxx 函數(shù)，就可以實(shí)現(xiàn)對(duì)查詢語(yǔ)法樹的優(yōu)化工作。是不是覺得很簡(jiǎn)單？當(dāng)然不是，原理很簡(jiǎn)單，但是理論與實(shí)際還有一定的距離。

例如，如何處理查詢中大量出現(xiàn)的子鏈接？如何對(duì) d 算子執(zhí)行 “下推”？如何選擇索引？如何選擇 JOIN 策略？這些都需要我們仔細(xì)處理。

PostgreSQL 給出的 subquery_planner 如下所示。

由 PostgreSQL 給出的實(shí)現(xiàn)可以看出，核心處理思想與我們討論的相一致：依據(jù)類型對(duì)查詢語(yǔ)句進(jìn)行分類處理。

這里需要注意的一點(diǎn)就是查詢計(jì)劃的生成部分，PostgreSQL 將查詢計(jì)劃的生成也歸入 subquery_planner 中，但為了方便問題的討論，我們并未將查詢計(jì)劃的生成部分在 subquery_planner 中給出。我們將查詢優(yōu)化的主要步驟總結(jié)如下：

處理 CTE 表達(dá)式，ss_process_ctes；

上提子鏈接，pull_up_sublinks；

FROM 子句中的內(nèi)聯(lián)函數(shù)，集合操作，RETURN 及函數(shù)處理，inline_set_returning_ functions；

上提子查詢，pull_up_subqueries；

UNION ALL 語(yǔ)句處理，flatten_simple_union_all；

處理 FOR UPDATE（row lock）情況，preprocess_rowmarks；

繼承表的處理，expand_inherited_tables；

處理目標(biāo)列（target list），preprocess_expression；

處理 withCheckOptions，preprocess_expression；

處理 RETURN 表達(dá)式，preprocess_expression；

處理?xiàng)l件語(yǔ)句 - qual，preprocess_qual_conditions；

處理 HAVING 子句，preprocess_qual_conditions；

處理 WINDOW 子句，preprocess_qual_conditions；

處理 LIMIT OFF 子句，preprocess_qual_conditions；

WHERE 和 HAVING 子句中的條件合并，如果存在能合并的 HAVING 子句則將其合并到 WHERE 條件中，否則保留在 HAVING 子句中； 

消除外連接（Outer Join）中的冗余部分，reduce_outer_joins；

生成查詢計(jì)劃，grouping_planner。