本篇是TUM的記憶體資料庫HyPer針對compile-based執行架構的改進。其中涉及到HyPer的動态編譯和并行執行架構
動态編譯文章的結尾提到了編譯執行系統存在的2個問題，其中之一就是：不可控的編譯時間。
背景
在具體的應用中，基于LLVM的compiler framework雖然已經是比較快速的了，但對于複雜的查詢語句，其編譯的時間還是很長的，如果處理的資料量比較少，導緻執行時間很短，則編譯/執行的比例将會非常高，産生非常差的使用者體驗，可能不如解析執行的響應速度快。有些非常複雜的（自動生成）SQL，甚至無法編譯出來，是以如果沒有自适應編譯執行的能力，compile-based的系統在實用性上是有很大缺陷的。
可以看到，整個optimize的過程+code generation的過程，相對于LLVM opt+compile，占比極低，大概是50 - 100倍的差異。
總體思路
為此HyPer中引入了解析執行的能力，它總是要先把query plan通過Codegen生成LLVM IR的表示，但可以通過快速的translation轉換成一種自定義的LLVM bytecode，然後使用解析器進行解析執行，進而避免編譯過程。
基于這種機制，提出了自适應切換execution mode的framework，可以有3種執行mode：
- 基于LLVM bytecode解析執行（高效），這是預設模式。
- 基于LLVM IR做無優化的編譯，生成machine code
- 基于LLVM IR做有優化的編譯，生成更高效的machine code
可以看到，3種執行模式，bytecode的translation是很快的，而非優化編譯/優化+編譯，則要慢很多。
這樣其實編譯執行 vs 解析執行，本質就是吞吐量 vs 延遲， 編譯時間會增加單條query的rt，但編譯的代碼執行效率更高可以産生更高計算吞吐，解析執行可以快速響應是以對rt影響更小，但代碼效率低會影響吞吐。
此外，由于HyPer的mosel-driven的并行執行架構，在compile期間是串行的，所有worker thread都要等待直到編譯完成，而解析方式可以立即開始并行執行。
理想情況下，應該是：
- 對于小型的query(資料量小），使用解析執行，保證低延遲
- 對于大型的query，使用優化編譯執行，保證高吞吐量
- 對于中型的query，使用非優化編譯執行，相當于前兩者的折中
自适應方案
HyPer中基于動态編譯 + morsel驅動的并行執行可以用下圖了解：
plan會被優化器編譯為多個pipeline job(上圖中右側各顔色所示），每個線程Tx針對各個morsel粒度的資料，執行編譯生成的一個個的pipeline job。
在執行過程中，針對每個pipeline job，動态利用feedback進行推斷，選擇後續是否需要切換到編譯模式來更快速的的執行，這種基于morsel的方式是細粒度的，這樣可以使一個query中，長時間的part和短時間的part，使用不同的execution mode，效率達到最優。
為了實作自适應編譯架構，需要3個基本元件：
- 高效的bytecode 解析器
- Track 執行過程中的資訊，進而動态決定是否切換，而不是提前利用optimizer的cost/card estimation來靜态決定
- 根據推斷動态切換execution mode
基本模式是，所有query總是以解析模式開始，多worker threads并行執行，在執行中通過收集+推斷，當判斷後續采用compile方式更有益時，則使用一個worker thread開始異步編譯過程，其他worker繼續解析執行，當編譯完成時，後續所有worker都切換到compiled function繼續執行。這種處理方式是以pipeline為單元的，并以morsel為監控+推斷+切換的基本機關。
- Track Query progress
基于HyPer morsel-driven的并行執行方式，一個pipeline一個pipeline的處理，每個pipeline中，各個worker thread在處理完一個morsel後，要更新相關的執行timing資訊，而由一個特定的worker thread，在完成每個morsel後，要進行推斷過程。
- 切換
由于各個worker thread在處理morsel時是互相獨立的，他們各自使用什麼mode來來執行時無關的，是以隻要執行的語義相同，切換就會很自然，各種執行方式都是等價的，HyPer中使用一個handle結構來做了抽象，其中包含了不同execution mode的執行函數，通過切換執行函數的指針，即可很自然完成切換，如下圖所示
- 切換規則
在每個morsel處理完成時，一個worker thread要判斷是否進行切換，就是通過feedback估計目前pipeline中，tuple的處理速率，由于每個pipeline的起點 -> 終點都是物化點，morsel的資料量已知，是以可以根據目前速率，預估剩餘的執行時間，也會估計compilation time + compiled code的執行加速比（經驗估計），然後計算其他2種mode的執行時間，如果更優則開始啟動編譯。在編譯的同時，其他worker thread繼續解析執行，具體算法如下：
這裡r0/r1/r2是處理tuple的速率，c1/c2是編譯時間，t0/t1/t2是計算的剩餘執行時間。
- 高效的解析執行
HyPer使用了一種對LLVM IR進行對等translation的方式，轉換為bytecode的形式（類似informix stored procedure），解析器通過對OPCODE的解析來做switch case的執行邏輯，相當于java的VM。
上圖是HyPer VM中解析OPCODE并執行的代碼片段，可以看到有大量的指令類型。
性能
上圖是對TPCH Q11的3種執行mode下的性能profiling，optimized compilation沒有給出因為編譯時間實在太長。從圖中可以看到這種細粒度(morsel)的控制，可以讓長的執行部分(scan partsupp1, scan partsupp2) 使用compiled code，短的(hash table scan)則是解析執行，混合起來得到最佳效果。