在成熟領先的企業級資料庫系統中，并行查詢可以說是一大利器，在某些場景下它可以顯著地提升查詢的相應時間，提升使用者體驗。如sql server、oracle等， mysql目前還未實作，而postgresql在2015實作了并行掃描，相信他們也在朝着更健壯的企業級資料庫邁進。rdbms中并行執行的實作方式大抵相同，本文将通過sql server為大家詳細解析sql server并行執行的原理及一些實踐。
硬體環境——在深入并行原理前，我們需要一些準備知識，用以後面了解并行。
首先是當下的硬體環境，社會資訊化建設，網際網路的普及，硬體工藝的大發展……我們現在的硬體裝置的性能雖然已經不複摩爾定律的神奇，但已經相當豐富了，存儲上15k rpm的硬碟，ssd，pci-e ssd使得磁盤作為資料庫系統的”終極”瓶頸得到了一定的緩解，而記憶體上百g記憶體也早已不是小機的”特性”了，pc server上已經很普遍。在處理能力上，由于現今實體工藝上的極限，單顆cpu處理能力提升困難，系統架構已經朝着多顆多核的架構上迅猛發展，如8路cpu的伺服器也已經有一定的使用案例了。
總之我們的硬體資源越來越豐富，而本文所講的并行查詢查詢主要是針對上面叙述的多個cpu協同工作，用以提升sql查詢中的cpu-bound響應時間。(雖然在并行掃描(scan)的時候實際中同樣可以提升查詢的響應時間，但這我們就不細述了)
sql server關于”任務”的相關知識——schedulers，tasks，workers。
schedulers是指sql server中sqlos識别到的硬體環境中的邏輯cpu，它是管理sql server計算工作的基本機關，它提供”線程”(workers)用于配置設定相應的”cpu”資源用于計算。tasks實際就是sql server中的工作單元，本質上就是一個函數針(c++)，用于指向需要執行的代碼。
比如lazywriter實際上就是去調用相應的function(sqlmin!lazywriter())。workers 如果說tasks是指向工作的地方，那麼workers是處理相應的工作，它綁定到windows線程的方式用于計算。ok，現在說一條sql請求sql request=task+worker應該能了解了吧。為了加深了解，我們可以看圖1-1：
圖1-1
最終回到我們的并行查詢，實際就是多個tasks在多個schedulers上同時運作，提升響應速度！
關于sqlos，微軟在sql server 2005引入，可以說是個重大的突破，就像michael stonebraker（2014圖靈獎得主）老爺子的早年paper” operating system support for database management”中叙述的那樣，sqlos，比os更懂資料庫，感興趣的朋友自行搜尋下。限于篇幅這裡就不細深入sqlos了，給出一張簡單架構圖大家感受下。 如圖1-2：
圖1-2
ok準備知識完畢，我們進入并行查詢執行吧。
串行執行計劃——在了解并行執行之前，我們先了解下串行執行計劃的相關知識。
其實很簡單，關于執行計劃本身這裡就不介紹了，隻是介紹下與本文相關重要元素。
串行執行計劃實際就是由單個線程(thread)執行完成，單個執行上下文(execution context)。
執行上下文就是指執行計劃中用于執行的一些資訊，如對象id，如執行計劃中使用到的臨時表等等。在執行中實際上就是單個(核)cpu在工作，如圖2-1：
圖2-1
而并行執行計劃，顧名思義，就是多個(核)cpu在同時工作，用于提升cpu-bound的響應時間，對應串行，它有多個線程，多個執行上下文，但也會消耗更多的資源。但對于磁盤io，sql server認為是木有幫助的，我們通過一個簡單的執行個體看下：
注：文章中使用的adventureworks，網上可以自行搜尋下載下傳
---串行執行
--并行執行
通過觀察上面兩條簡單語句的執行計劃可以發現，在預估subtree cost中 (資源消耗量)實際上單cpu與雙cpu相比隻是cpu預估減半，io預估不變。如圖2-1-a：
圖2-1-a
讓我們真正的進入并行執行計劃，每個并行執行計劃都有一個主的交換操作(root exchange)，即圖形執行計劃中最左面的gather stream運算符(後面會講到)(sql server有圖形執行計劃，不小小夥伴很羨慕吧)。
而所有的并行執行計劃都會有一個固定的串行部分—即最左邊gather stream運算符中所有靠左的部分(包含gather中消費者，後面會講到生産-消費模型)的所有操作，他是由主線程thread zero控制，同時它的執行上下文也是context zero，如圖2-2所示：
圖2-2
而并行區域，顧名思義就是root exchange所有靠右的部分，而并行部分又有可能有多個分支(branches)，每個branch都可以同時執行(分支有自己的tasks)，分支自身可以是并行，也可以是串行。但分支不會使用主線程thread zero。關于分支大家可以用如下語句自己看下相關執行計劃屬性(sql server 2012版本及之後版本可以顯現) 如圖2-3所示。
如圖2-3-2，我的最大并行度設定為4，有三個branches，而這裡我使用的線程數就是4*3=12，再加上一個主線程 thread zero 這個并行查詢我所使用的線程總數為13個。
圖2-3-1
圖2-3-2
而并行和串行的差別聯系，大家可以了解成下圖2-4。
主線程在串行中實際就是他的執行線程：
圖2-4
圖2-4中，并行的表掃描後聚合，實際上是等于兩個串行的表掃描聚合。這個提到并行表掃描table scan(range scan)就稍微展開下：在sql server 2005及以前版本中并行掃描實際上是”parallel page supplier”及每個線程掃描的機關是資料頁，掃描多少有資料頁中含有的資料行多少決定，而在sql server 2008及以後是”range enumerators” 每個線程掃描的資料實際上是由資料的區間分布決定的，至此也就有了我們在08及以後版本中經常看到的“access_methods_dataset_parent”闩鎖等待，你可能會疑問怎麼高版本還帶來新問題，實際上在 ” parallel page supplier”中的問題也是不少的，比如在快照隔離級别下的資料頁掃描确認問題等等，總得來說還是更高效了。
這裡需要大家注意的是并行掃描隻支援前滾掃描(forward)，不支援反向掃描(backward)感興趣的朋友可以根據下面代碼自行測試。
看到這裡不少朋友可能有疑惑了，上文中又是串行，又是并行，又是多tasks，到底什麼時候用串行，什麼時候并行，用多少個tasks啊，實際上sql server執行個體級有兩個設定:并行門檻值”cost threshold for parallelism” 即當subtree cost(前面提到的估計資源消耗)大于設定值時優化器才會觸發并行優化，進而可能生成并行執行計劃。二:最大并行度(max degree of parallelism)用于設定分支(branches)中到底可以多少個cpu同時工作。這裡給大家畫個簡單的圖，大家就一目了然了。如圖2-5：
圖2-5
至此，并行相關的基本概念已經介紹完畢，接下來讓我們深入并行。
exchanges，顧名思義，就是交換，在并行裡指的是threads間的資料交換，這也是在隻有并行執行的情況下才會有的操作符。具體到sql server中有三種exchanges 操作，分别為gather streams， repartition streams，以及distribute streams其對應起到的作用就是聚集，重定向，分發threads間的資料，操作符如圖3-1所示：
圖3-1
而實際上上述運算符每一個都是兩個運算符的”合集”這裡就是我們之前提到的生産者與消費者操作。操作符中右邊為生産者，将生成的資料放入packets中，而左邊為消費者，從packets中将資料取出。如圖3-2所示：
圖3-2-1
圖3-2-2
這裡解釋下我們在sql server中常見的cxpacket等待，不少同學都将這個等待看做并行中某些線程工作快，某些線程工作慢而産生的差異，這個對，但說法不專業，實際上根據生産者消費者模型來看分析是:
cxpacket=class exchange packet
針對生産者：所有的 buffer packets 都已經被填滿，無法繼續生産(填充)。
針對消費者：所有的buffer packets都是空的，沒有資料可以消費
在生産者與消費者的模型中，資料是通過一定規則由生産者流動到消費者那裡，在sql server有如下5種規則：
broadcast：廣播，當資料量較小時将生産者的所有資料都廣播到所有的消費者中。阿裡的朋友在分布式中間件中小表廣播應該有不少應用吧。
hash：通過哈希函數将制定的資料一個或多個欄位哈希化(簡單的如取模)，根據不同的值填充到不同的buffer packets中供消費者使用。
round robin：顧名思義，将資料順序逐條地添加到每個buffer packets中。
demand：之前的都是發送資料，而這個是消費者從生産者中拉資料，如某個消費者拉某個常量的資料，這個隻在分區表中采用。
range：顧名思義，根據資料中某些欄位的分布，分别填充到不同的buffer packets中，這個一般在并行索引，統計資訊重建時采用。
有了生産者和消費者的資料使用方式，你可能覺得還差點什麼吧？沒錯，資料是否是有序的呢，sql server中exchange分别merge exchange 和non-merge exchange，分别對應資料在exchage時是否要求有序，當然大家也都知道了有序的成本merge exchange明顯高于無序。
如圖3-3所示：
圖3-3
最後我們來談談sql server中的并行join。sql server中對于三種基本join: nested loop join ，merge join， hash join都支援，我們分别說明下他們的優缺點，在今後的并行優化時，你可能用到。在這裡我就不複述三類join連結的基本算法了，不懂的同學wikipedia下。
parallel merge join 如圖4-1：
将參與join的key(兩個表)都進行hash化，然後同時進行比對。
并行merge join幾乎無優點，缺點倒是不少，首先是需要merge exchange，其次增加cpu本身對性能幫助實際不大(參考相應算法)，而且merge join還會增加并行死鎖的幾率。是以實際生産中我們還是應盡量避開merge join。
圖4-1
parallel hash joinbuild階段，如果資料量小，所有broadcast到所有threads中 如圖4-2-1，否則就将join key 哈希化，進行比對，如圖4-2-2。
這裡應注意parallel hash join是non-merge exchanges，且随着cpu的增加，性能是線性擴充的(具體參考相應算法)，但在parallel hash join中應注意可能由于統計資訊問題，複雜join導緻的hash join在建構，探測階段都有可能因為記憶體不足而溢出的現象，進而拖慢查詢。關于溢出可以使用跟蹤，擴充事件捕捉等。
圖4-2-1
圖4-2-2
parallel nested loop join外表多個threads同時運作(如掃描資料)，而内表則在每個thread上串行同時進行比對。
parallel nested loop join在實際生産中可能為我們解決許多一些棘手問題，比如他會減少并行計劃中的exchange使用，使用更少的記憶體等等。但也應注意可能由于資料分布傾斜，nested loop預讀等情形導緻的性能提升有限，而消耗反而相比串行提高等問題。而且sql server的優化器本身是”不喜歡并行循環嵌套的”，有時我們需要特定的寫法才能實作他。如圖4-3：
圖4-3
最後我們再提下bitmap過濾吧，sql server是沒有位圖索引的，這個也頗為诟病，但實際sql在執行時是有可能用到位圖過濾的。
簡單說下sql server位圖過濾實作方式。（具體大家也可以wikipedia bloom filter）
實作方式：通過建構一個長度x的位數組(bit array)(所有位為0)，将要比對的集合通過哈希函數映射到位數組中的相應點中(相應位為1)，當判斷一個值是否存在時找bit array中對應位是否為1就可以了。這個過程由sql server内部自己完成。 如圖4-4-1，圖4-4-2我将一個現有數組哈希化，然後在其中搜尋 ”悟空”是否在數組中。
圖4-4-1
圖4-4-2
好了，sql server相關的并行知識就給大家介紹這麼多吧，後面有時間給大家帶來相關的實踐應用。
作者介紹 高繼偉
易車網進階dba，資料架構師；
負責易車網整體資料平台架構，疑難問題解決，data platform mvp。
<b></b>
<b>本文來自雲栖社群合作夥伴"dbaplus"，原文釋出時間：2016-05-16</b>