PostgreSQL 源碼解讀（42）- 查詢(xún)語(yǔ)句#27（等價(jià)類(lèi)）

上一小節(jié)介紹了函數(shù)query_planner中子函數(shù)子函數(shù)build_base_rel_tlists/find_placeholders_in_jointree/find_lateral_references的實(shí)現(xiàn)邏輯,本節(jié)介紹下一個(gè)子函數(shù)deconstruct_jointree函數(shù)中涉及的數(shù)學(xué)知識(shí):等價(jià)類(lèi)以及等價(jià)類(lèi)在PG中的應(yīng)用實(shí)例。

一、數(shù)學(xué)基礎(chǔ)

等價(jià)關(guān)系
等價(jià)關(guān)系（equivalence relation）即設(shè)R是某個(gè)集合A上的一個(gè)二元關(guān)系。若R滿(mǎn)足以下條件：
1.自反性:?x∈A,xRx
2.對(duì)稱(chēng)性:?x,y∈A,xRy ? yRx
3.傳遞性:?x,y,z∈A,(xRy ∧ yRz) ? xRz
則稱(chēng)R是一個(gè)定義在A上的等價(jià)關(guān)系。習(xí)慣上會(huì)把等價(jià)關(guān)系的符號(hào)由R改寫(xiě)為～
詳細(xì)的說(shuō)明和例子詳見(jiàn)維基百科

等價(jià)類(lèi)
假設(shè)在一個(gè)集合A上定義一個(gè)等價(jià)關(guān)系（用～表示），則A中的某個(gè)元素x的等價(jià)類(lèi)就是在A中等價(jià)于x的所有元素所形成的子集:
[x] = {y∈A,y～x}
詳細(xì)的說(shuō)明和例子詳見(jiàn)維基百科

二、應(yīng)用

PG在函數(shù)deconstruct_jointree中對(duì)約束條件子句（qual clauses）進(jìn)行掃描,可能會(huì)在非外連接的連接條件中找到等式,如A=B,這時(shí)候會(huì)創(chuàng)建一個(gè)等價(jià)類(lèi)（記作{A,B}）.如果在后面發(fā)現(xiàn)另一個(gè)等式,如B=C,則把C加到已存在的等價(jià)類(lèi){A,B}中,即{A,B,C}。通過(guò)這個(gè)步驟,就產(chǎn)生了一些等價(jià)類(lèi),這些等價(jià)類(lèi)中任何一對(duì)成員的等值關(guān)系都可以作為約束或者連接的條件.
這樣做的好處,一是可以通過(guò)這樣的簡(jiǎn)化,只需要驗(yàn)證部分等值條件，而不需要驗(yàn)證所有的等值條件,就可以去掉一些多余的等價(jià)類(lèi)條件約束;二是從相反的方向上考量,優(yōu)化器在準(zhǔn)備一個(gè)約束或者連接條件列表的時(shí)候,檢查每個(gè)等價(jià)類(lèi)是否能夠派生新的滿(mǎn)足當(dāng)前約束或者連接的隱式條件。例如在上面的例子中,可以依據(jù)等價(jià)類(lèi){A,B,C}產(chǎn)生一個(gè)A=C的條件,這樣優(yōu)化器就可以嘗試探索新的優(yōu)化連接路徑。

例一:

testdb=# explain verbose select t1.dwbh,t2.grbh
testdb-# from t_dwxx t1,t_grxx t2
testdb-# where t1.dwbh = t2.dwbh and t1.dwbh = '1001';
                               QUERY PLAN                               
------------------------------------------------------------------------
 Nested Loop  (cost=0.00..16.06 rows=2 width=76)
   Output: t1.dwbh, t2.grbh -- 連接,無(wú)需執(zhí)行filter操作
   ->  Seq Scan on public.t_dwxx t1  (cost=0.00..1.04 rows=1 width=38)
         Output: t1.dwmc, t1.dwbh, t1.dwdz
         Filter: ((t1.dwbh)::text = '1001'::text) -- 連接前完成選擇操作
   ->  Seq Scan on public.t_grxx t2  (cost=0.00..15.00 rows=2 width=76)
         Output: t2.dwbh, t2.grbh, t2.xm, t2.xb, t2.nl
         Filter: ((t2.dwbh)::text = '1001'::text) -- 連接前完成選擇操作
(8 rows)

約束條件:t1.dwbh = t2.dwbh and t1.dwbh = '1001',其相應(yīng)的等價(jià)類(lèi)可以簡(jiǎn)略的理解為:{t1.dwbh,t2.dwbh,'1001'},根據(jù)傳遞性,那么可以推導(dǎo)出隱性約束條件:t2.dwbh='1001',在連接前把謂詞t1.dwbh='1001'和t2.dwbh='1002'下推到基表掃描中,減少連接的元組數(shù)量,從而實(shí)現(xiàn)查詢(xún)優(yōu)化.從查詢(xún)計(jì)劃來(lái)看,PG實(shí)際也是這樣處理的.
下面的SQL語(yǔ)句則不具備以上條件,因此在連接過(guò)程中還需要執(zhí)行join filter.

testdb=# explain verbose select t1.dwbh,t2.grbh
testdb-# from t_dwxx t1,t_grxx t2
testdb-# where t1.dwbh = t2.dwbh and t1.dwdz like '廣東省%';
                                QUERY PLAN                                
--------------------------------------------------------------------------
 Nested Loop  (cost=0.00..20.04 rows=2 width=76)
   Output: t1.dwbh, t2.grbh
   Join Filter: ((t1.dwbh)::text = (t2.dwbh)::text)
   ->  Seq Scan on public.t_dwxx t1  (cost=0.00..1.04 rows=1 width=38)
         Output: t1.dwmc, t1.dwbh, t1.dwdz
         Filter: ((t1.dwdz)::text ~~ '廣東省%'::text)
   ->  Seq Scan on public.t_grxx t2  (cost=0.00..14.00 rows=400 width=76)
         Output: t2.dwbh, t2.grbh, t2.xm, t2.xb, t2.nl
(8 rows)

例二:
測(cè)試腳本如下:

testdb=# explain verbose select t1.dwbh,t2.grbh
from t_dwxx t1,t_grxx t2
where t1.dwbh = t2.dwbh 
order by t2.dwbh;
                                    QUERY PLAN                                     
-----------------------------------------------------------------------------------
 Sort  (cost=20.18..20.19 rows=6 width=114)
   Output: t1.dwbh, t2.grbh, t2.dwbh
   Sort Key: t1.dwbh
   ->  Hash Join  (cost=1.07..20.10 rows=6 width=114)
         Output: t1.dwbh, t2.grbh, t2.dwbh
         Inner Unique: true
         Hash Cond: ((t2.dwbh)::text = (t1.dwbh)::text)
         ->  Seq Scan on public.t_grxx t2  (cost=0.00..14.00 rows=400 width=76)
               Output: t2.dwbh, t2.grbh, t2.xm, t2.xb, t2.nl
         ->  Hash  (cost=1.03..1.03 rows=3 width=38)
               Output: t1.dwbh
               ->  Seq Scan on public.t_dwxx t1  (cost=0.00..1.03 rows=3 width=38)
                     Output: t1.dwbh
(13 rows)

從執(zhí)行計(jì)劃來(lái)看,雖然明確指定按t2.dwbh進(jìn)行排序,但實(shí)際上按t1.dwbh進(jìn)行排序.原因是存在等價(jià)類(lèi){t1.dwbh,t2.dwbh},不管在t1.dwbh還是t2.dwbh上排序,結(jié)果都是一樣的,但t1.dwbh上排序,成本更低,因此優(yōu)先選擇此Key.

值得注意的是:PG的等價(jià)類(lèi)只有在有等式條件（不包括外連接）和排序的情況下才產(chǎn)生,作為優(yōu)化的一個(gè)方向可以考慮存在不等式時(shí),把謂詞進(jìn)行下推.

testdb=# explain verbose select t1.dwbh,t2.grbh
from t_dwxx t1,t_grxx t2
where t1.dwbh = t2.dwbh and t1.dwbh > '1001';
                                QUERY PLAN                                
--------------------------------------------------------------------------
 Nested Loop  (cost=0.00..20.04 rows=2 width=76)
   Output: t1.dwbh, t2.grbh
   Join Filter: ((t1.dwbh)::text = (t2.dwbh)::text) -- 這一步必不可少
   ->  Seq Scan on public.t_dwxx t1  (cost=0.00..1.04 rows=1 width=38)
         Output: t1.dwmc, t1.dwbh, t1.dwdz
         Filter: ((t1.dwbh)::text > '1001'::text) -- Filter過(guò)濾
   ->  Seq Scan on public.t_grxx t2  (cost=0.00..14.00 rows=400 width=76)
         Output: t2.dwbh, t2.grbh, t2.xm, t2.xb, t2.nl -- 全表掃描,可以考慮加入Filter
(8 rows)

三、參考資料

等價(jià)關(guān)系
等價(jià)類(lèi)
關(guān)系代數(shù)
查詢(xún)優(yōu)化基礎(chǔ)

附:query_planner中的代碼片段

     //...
     /*
      * Examine the targetlist and join tree, adding entries to baserel
      * targetlists for all referenced Vars, and generating PlaceHolderInfo
      * entries for all referenced PlaceHolderVars.  Restrict and join clauses
      * are added to appropriate lists belonging to the mentioned relations. We
      * also build EquivalenceClasses for provably equivalent expressions. The
      * SpecialJoinInfo list is also built to hold information about join order
      * restrictions.  Finally, we form a target joinlist for make_one_rel() to
      * work from.
      */
     build_base_rel_tlists(root, tlist);//構(gòu)建"base rels"的投影列
 
     find_placeholders_in_jointree(root);//處理jointree中的PHI
 
     find_lateral_references(root);//處理jointree中Lateral依賴(lài)
 
     joinlist = deconstruct_jointree(root);//分解jointree

     /*
      * Reconsider any postponed outer-join quals now that we have built up
      * equivalence classes.  (This could result in further additions or
      * mergings of classes.)
      */
     reconsider_outer_join_clauses(root);//已創(chuàng)建等價(jià)類(lèi),那么需要重新考慮被下推后處理的外連接表達(dá)式
 
     /*
      * If we formed any equivalence classes, generate additional restriction
      * clauses as appropriate.  (Implied join clauses are formed on-the-fly
      * later.)
      */
     generate_base_implied_equalities(root);//等價(jià)類(lèi)構(gòu)建后,生成因此外加的約束語(yǔ)句
 
     //...