隨著網際網路資料的爆炸性增長，傳統資料庫系統在單表資料容量方面承受了越來越大的壓力。以前公司內部的資料庫，存放的主要是來自公司業務或內部管理系統的資訊，中小型公司甚至一個MySQL例項就搞定了。但現在資料來源不僅更豐富，資料量也在指數級增長，從業務的角度，基於hash/range的分割槽表變得越來越有吸引力。

為了能夠對分割槽表有優異的處理能力，對於查詢最佳化系統來說一個最基本的能力就是做partition pruning，將query中並不涉及的分割槽提前排除掉，可想而知這可以節省大量的IO/CPU/Network資源，帶來成本的降低和效能的提升。

簡單圖示下什麼叫partition pruning，例如下圖的Orders表，在date列上按照month做了range分割槽，每個月單獨作為一個partition。

SELECT avg（amount）

FROM orders

WHERE date BETWEEN ‘10-01-2013’ AND ‘12-31-

2013’；

如上SQL，由於單表謂詞在parititon key上，在最佳化期間即可確定哪些可以分割槽可以避免訪問，即靜態pruning。

上例中的資料也可以改寫為star schema的形態：

SELECT avg（amount）

FROM orders

WHERE date id IN

（SELECT date id

FROM date_dim

WHERE year = 2013 AND

month BETWEEN 10 AND 12）；

這時Orders的值將需要根據date_dim表的動態輸出決定，因此對Orders表的partition pruning只能在執行期完成，類似的例子還有動態繫結變數，稱為動態pruning。

這篇paper主要介紹了一種基於Cascades框架規範且統一的分割槽消除方法，支援根據單表/join謂詞，靜態/動態的做partition pruning，並在Orca中做了實現。關於Cascades和Orca在之前的文章中已有過介紹，如果不熟悉的同學，可以參考如下2篇文章：

之所以要介紹這篇paper是由於PolarDB的並行最佳化框架也參考了Cascades，因此這裡提到的方法可以很自然的應用於PolarDB對分割槽表的最佳化處理中，我們也在做這方面的規劃。

基本演算法

引入了3個新的運算元來做pruning，且不區分是動態還是靜態的：

PartitionSelector

PartitionSelector根據謂詞生成相關partition ids，主要實現了做partition選擇的功能，並將篩選後的ids傳遞給DynamicScan。

DynamicScan

物理scan運算元，基於PartitionSelector傳遞的ids，在做table scan時跳過不需要的partition。

Sequence

是一個同步的概念，用於描述PartitionSelector->DynamicScan的生產消費關係，確定誰先執行。

三者的配合有多種方式，如下圖：

（a）表示做full table scan，這時是沒有filter的，PartitionSelector直接生成全量partition T1 -> T100給DynamicScan。

（b/c）表示在partition key（PK）上有單表條件（PK=5/PK<30），這時可以只選出目標分割槽給DynamicScan。

（d）表示了兩表 R join T on R。A = T。PK，由於T表是partition table，其scan運算元是DynamicScan。這裡有所不同的是，對T的過濾需要基於R。A列的值，因此PartitionSelector要

加在R的scan上方

，用來獲取R。A列的value用於過濾分割槽，並傳遞給右側T的DynamicScan。另外可以看到這裡不再有Sequence運算元了，由於這裡Join運算元已經保障了R和T執行的先後順序（先R後T），也就保證了PartitionSelector->DynamicScan的順序，Sequence不再必要。

瞭解了這3個運算元，其實基本思路就有了：

在原有的physical plan tree中，選擇PartitionSelector的放置位置，應放置在可幫助消除分割槽的謂詞(select/join)下方，並利用謂詞中pkey相關的部分做分割槽消除，此外應儘量往下推，靠近對應的DynamicScan，在初期過濾掉更多的分割槽。

輸入：已包含了DynamicScan（對應partition table）的physical operator tree，其中每個DynamicScan運算元有其唯一編號partScanID。

輸出：插入了PartitionSelector的新tree。

先描述下PartSpec的概念，用來描述partition select的行為，包含三元組，分別表示對應哪個DynamicScan，其分割槽列，分割槽選擇謂詞。

針對select(單表條件)的放置演算法：

看起來有些亂，但其實非常簡單，面對當前plan tree的selection node（過濾條件）時：

如果其partScanId對應的DynamicScan不在子樹中，留在node上方，作為終止位置。

如果在子樹中但selection node中沒有和PKey相關的謂詞，則只是推入op下方，進一步遞迴處理。

如果在子樹中且selection node中有PKey相關謂詞，將相關謂詞合入到PartSpec的partPredicate中，然後推入op下方進一步遞迴處理。

對單表條件做PartSelector放置

上圖很好的說明了這個例子，左側是初始plan tree，右側上方是初始PartSelector的描述資訊（可以從謂詞中獲取到）。由於select中沒有date_id這個表不在子樹中，編號為2的PartitionSelector保留在了Select運算元上方，而編號為1的則推到了Select下方，並把謂詞條件“month >= 10 and month <= 12”加入到了下推的PartSpec中。

針對Join的放置演算法

面對當前以join node為根節點的子樹時：

如果其partScanId對應的DynamicScan不在子樹中，留在join node上方，作為終止位置。

在子樹中，但對應的分割槽表是Join的外表，由於

外->內的驅動順序

，PartitionSelector沒法用內表的資料來驅動外表的pruning，只能推到外表側，看是否可以進一步遞迴處理（比如利用外表單表謂詞）

在子樹中，且對應的分割槽表在內表側，但join條件本身和partKey無關，則這個join條件對分割槽消除無幫助，可以推入內表側，看是否可以進一步遞迴處理

在子樹中，對應的分割槽表在內表側，且join條件和partKey相關，則

可以推入外表側

，其將join條件中partkey相關的部分融入partPredicate。

對join放置PartSelector

join的處理流程要更復雜些，主要受限於PartitionSelector->DynamicScan的這種先後依賴順序，因此如果想根據join condition做動態pruning（如上圖），必須要求分割槽表在被驅動側（如NL join的內表，HashJoin的probe表）。上圖示例中，由於date_dim是驅動側（build側），1，2兩個PartitionSelector都推下來。

一個完整的示例包含了針對單表條件的PartitionSelector和針對Join條件的PartitionSelector，可以看到他們都放到了正確的最低位置。尤其注意，2號PartitionSelector所對應的DynamicScan表甚至不是同層的join table，這也充分顯示了這種方法的靈活性，可以在更大的子樹範圍內做pruning。

Greenplum中實現

這套演算法實現在了Greenplum的大資料查詢最佳化器Orca中。注意從本質上，distribution和partition是兩個正交的概念，在Greenplum這種share-nothing的MPP系統中，每個segment上都可以有對應的多個partitions。

基於Orca已有Physical Property概念，將partition擴充套件為新一維的physical property來實現，資訊用PartSpec來描述，這樣就從擴充套件到了三元組。

DynamicScan則是針對分割槽表的一種physical operator。

PartitionSelector實現為enforcer，放置在合適的group中，某些group expr（scan。。）上方，來滿足PartSpec的屬性要求，具體放置演算法如上節所述。

上圖給出了R HJ S時的4種可能的PartitionSelector enforcer放置方式（灰色是group expression，表示物理演算法實現，黑色表示enforcer，用來施加特定物理屬性，例如Replicate表示要廣播資料）。其中R是probe側，S是build側。

Plan 1 表示用PartitionSelector基於R。PK做裁剪，但由於R是被驅動側，PartitionSelector沒法用join condition對R做pruning，因此沒有partPredicate。

Plan 2/3 也是類似的處理，只是後續的join方式不同

Plan 4 則使用了不同的hash join順序，S變為驅動側（build），R變為被驅動側（probe），因此這時可以將PartitionSelector推入到S上方，並基於partPredicate： R。PK = S。a對R做過濾！

對於Plan 4可能大家有疑問，為什麼不是先做PartitionSelector再做Replicate呢？不是應該儘量下推嗎？這是由於為了避免多一次的網路互動，在Greenplum的實現中這種PartitionSelector->DynamicScan的資訊傳遞是

不跨segment

的，因此是在Replicate後，基於分發後的資料，和R在各個segment內部做區域性的partition pruning。

如上圖所示，上方是無效plan因為PartitionSelector和DynamicScan在不同process中（PG的多程序模型），而下圖則有效。為了保證這一點，在考慮每個group中的多種可能enforcer組合時（Motion/PartitionSelector），需要約束Motion不能在PartitionSelector上方。

總結

雖然本篇寫了不少，但基本思路還是非常簡單的，partition pruning是一種價效比非常高的最佳化策略，一般實現不會太複雜，但卻可以大幅度提升查詢質量。因此各類系統提出了不同的pruning方案，例如Snowflake，由於其IO/事務的基本單元都是micro-partition，每個micro-partition是immutable的，因此可以維護精確統計資訊，利用這種精確統計資訊可以更好的實現靜/動態的pruning。

對於PolarDB來說，除了最佳化階段基於sargable filter的靜態剪枝外，也實現了基於hash join的bloom filter做動態pruning，本篇提到的方法實際上是一種補充，不僅適用於hash join，也可用於nest loop join。