### ?“神秘”的r和d **單從數據結構來看的話**，我們可以這樣解釋r和d的含義。r代表著當前字段與前一字段的關系，是在哪一層合并的，即公共的父結點在哪？舉例來說，假如我們重建到了Code='en'，通過r=2可以知道是在Language那一層發生了重復。  為了保持原紀錄的結構，我們會保存一些NULL數據，而d就是用于重建NULL字段。通過d的值，就能知道NULL的結構。例如下圖，通過r=1知道應該合并到Name那一層。而通過d=1則知道路徑上只有一個字段，即不僅僅是Code字段不存在，Language也不存在。這樣就把NULL正確地重建出來了，那么接下來的Code='en-gb'的層級也就不會亂了。  然而這只是從靜態的數據結構來解釋，而r和d的深層次含義還是要看FSM是如何執行的。**真正的因果關系是FSM的執行方式決定了數據結構的設計**。 ### 3?記錄查詢 ### 3.1?從FSM角度看r和d 先看一下前面例子的完整FSM的樣子。如果把Protocol Buffer中對數據格式定義的schema看作是編譯原理中的語法定義的話，那么一般可以使用工具如antlr,?yacc自動生成自動機，手寫的話是相當恐怖的吧。  對列數據的完整遍歷就是這個樣子的：  在討論查詢如何執行之前，先繼續剛才未完成的題目，r和d的本質，這次通過動態的FSM的角度來分析，而不是靜態的數據結構了： ???**FSM狀態機只是定義了狀態的變更，即處理流程應當如何在各個列的存儲表之間跳轉，而實際數據還是在表中保存**。有點像數據庫索引，遍歷時是根據FSM進行跳轉，然后對某一列的表進行table scan。但索引是靠字段值的順序組織，因為數據庫表之間沒什么嵌套關系，而Dremel的FSM則是靠字段之間的嵌套關系來組織。  ???狀態機中線條上的數字表示什么？回憶一下，數字表示的是：字段的數據表中當前行的下一行的r值。通過檢測下一個r值來決定跳轉。因為**r=0，則說明下一行與當前行所表示的字段一定不在同一路徑，否則必然會在某一Level上有共同的字段(路徑的部分重疊)**。注意這是由于Protocol Buffer的schema不是樹，沒有共同的根所導致，否則所有字段必然都會在根重復，上面對r的解釋也就沒意義了。以repeated的Forward為例，檢查到下一行r=1說明40、60都是接在20字段下面的。Code字段也是同樣道理。  ???Name.Language.Code到Name.Language.Country之間的線上為什么是0，1，2？因為Name.Language.Code是required不是repeated，讀取后不管下一行的r值是多少都要去讀Name.Language.Country。同理Name.Language.Country也是讀完不管怎樣都跳到下一字段。 ???最復雜的要屬Name.Url了，因為它是schema里定義的最后一個字段。在Name.Url這要決定到底是繼續下一文檔如r2的處理，還是跳回到本文檔的其他字段繼續處理。具體分析一下：**r=0說明當前文檔中沒有Name字段了**。為什么這么說？因為如果文檔后面真有Name字段，假如下面有Url，則當前表中的下一條應該是r=1；**假如下面沒有Url，則當前表的下一條應該是r=0的NULL。這里NULL又發揮用處了！所以中間部分的NULL能保持結構無損，而后面部分的NULL能提示文檔是否結束**。 ### 3.2?查詢引擎 至此，我們已經徹底摸清Dremel數據模型以及FSM的基本運行方式了。現在終于可以分析Dremel是如何解析和執行類SQL查詢的了。查詢語言類似SQL，輸出也是個嵌套式的記錄，以及schema定義。  那么查詢引擎如何執行呢？首先為查詢語句中涉及到的每個字段都打開一個Reader來讀取數據，然后就是根據WHERE中的條件過濾以及根據SELECT中的條件投影并聚合了。難點在于：**重建出層次關系，再進行過濾和聚合**。例如，過濾掉DocId=20很容易，但其實文檔r2的所有記錄都應被過濾。因為WHERE中兩個條件是AND關系，同時DocId又是最底層的字段，所以相當于r2這一整棵樹都被裁剪掉了。Code=en-gb也是由于所在的Name字段下沒有滿足http開頭的Url字段，而被間接的過濾掉了。 聚合也是同樣道理，有了層次關系，才能正確的聚合。例如Code=en-us，en和Url=http://A是同一個Name下的，COUNT和字符串拼接時會一起處理。而Url=http://B則是另一個Name下的，要分開處理。  ### 參考資料 1?Dremel: Interactive Analysis of Web-Scale?DataSets