原論文：High-PerformanceComplex Event Processing over Streams
本篇論文的算法是基于SASE語言。對該語言不作詳細介紹，這裡隻描述模式比對的算法。
1. 基于查詢計劃的方法
1.1 基本查詢計劃
SASE中的查詢計劃由6個操作符的某個子集組成：
Ø 序列掃描(sequencescan)
Ø 序列構造(sequenceconstruction)
Ø 選擇(selection)
Ø 視窗(window)
Ø 否定(negation)
Ø 轉換(transformation)
考慮一個具體的例子，查詢Q3：
在該查詢中，A、B、C、D表示四種不同的事件類型。WHERE子句包含了3個謂詞：(1)兩個等值測試，attr1和attr2是A、B、C、D 共有的屬性；(2)A類型事件屬性attr3的一個簡單謂詞；(3)比較A和B類型事件的attr4屬性的謂詞。大寫字母T表示指定的視窗大小。
圖1顯示了Q3的基本查詢計劃和一個事件流的例子。
圖1 查詢Q3的執行計劃
在圖1下方的事件流中，小寫字母表示事件，對應的大寫字母表示事件類型，每個事件底下的數字是事件的時間戳。圓角矩形表示查詢計劃中的操作符，從下往上，它們依次是：
序列掃描和構造(Sequence Scan and Construction,簡寫為SSC)
序列掃描和序列構造總是一起使用。對于使用了SEQ結構的查詢來說，SSC處理SEQ的正元件，這些正元件組成了原SEQ中一個“子序列類型”。例如，Q3的子序列類型是(A,B,D)，其中删除了“!C”。
SSC把事件流轉換進入一個事件流序列中；每個事件序清單示唯一的SSC子序列類型比對。在圖1中，SSC的輸出建立了7個事件序列。
SSC包含序列掃描操作符(SS->)，它掃描事件流，檢測子序列類型中對應的比對序列；還包含序列構造操作符(SC<-),用來建立所有的事件序列。之後會詳細介紹它們。
選擇(Selection)
選擇操作符通過使用所有的謂詞，過濾每個事件序列，将滿足條件的序列輸出。圖1中，選擇操作符過濾出了7個輸入事件序列中的3個。
視窗(Window)
視窗操作符把WITHIN子句的限制條件加到了模式比對中。對于每個事件序列，它檢查第一個和最後一個事件的時間戳的內插補點是否小于視窗大小T。在圖1中，T的值是6，結果第二個輸入事件序列被過濾掉了。
否定(Negation)
否定操作符處理SEQ結構中的負元件，就是被SSC忽略的元件。在圖1中，對于每個輸入的事件序列，否定操作符檢查在序列中b和d事件的中間是否存在c事件，且c的屬性與b的相同(同樣，這個屬性也與a和d的相同)。如果這樣的c存在，事件序列就被删除。在圖1中，第二個輸入事件序列被過濾掉了。
轉換(Transformation)
最後，轉換操作符通過把輸入序列中所有事件的屬性連接配接在一起，進而把每個事件序列轉換成一個組合事件。
在餘下的部分，我們詳細闡述SSC和否定操作符的實作。
1.2 序列掃描和構造
序列掃描(SS->)
對于每個SSC子序列類型，通過把連續的事件類型映射到連續的NFA狀态上，進而建立一個NFA。例如，圖2展示了由子序列類型(A,B,D)建立的NFA，狀态0是起始狀态。狀态1是識别出A事件之後的狀态，狀态2是識别出事件B之後的狀态，狀态3是識别出事件D之後的狀态。狀态3用兩層圓圈畫出，表示它是NFA的“接受狀态(即最終狀态)”(此狀态隻有一個)。注意狀态1和狀态2包含了帶有通配符“*”的循環箭頭。給定一個事件，這種狀态允許NFA在該狀态上循環轉換，當然，也可以同時向後一個狀态轉換。
圖2 基于NFA的序列掃描和構造
為了跟蹤這些同時發生的狀态，我們使用運作時棧來記錄在特定時間點上産生的活動的狀态集合，并記錄當一個事件到達時，這個集合怎樣導緻了一個新的活動狀态集合的産生。圖2展示了運作時棧(從左到右)的變化，圖的下方是事件流。棧中每個活動狀态執行個體有一個或兩個前向指針，這個指針指向該狀态來自于哪個狀态。每當有a事件到達時，狀态0就要被激活，用以初始化一次新的搜尋。
序列構造(SC<-)
在序列掃描期間，一旦到達接受狀态，就會調用序列構造來建立事件序列。序列構造的一種方法是從運作時棧中提取出一個單源的有向無環圖(Directed Acyclic Graph，DAG)，這個圖從棧最右側單元的接受狀态開始，沿着前向指針周遊，直到到達了起始狀态。在圖2中，粗體數字和箭頭辨別出了這樣的DAG，這個圖是當到達時産生的。通過枚舉從DAG的源點到終點的所有可能路徑，就能得到事件序列。對于每條路徑，連接配接相同狀态的兩個執行個體的邊(也就是“自循環邊”)被删除了；剩下的邊産生了唯一的事件序列。圖2展示了由DAG建立的三個事件序列。
一個搜尋DAG的簡單算法的複雜度是O(P)。P是DAG中路徑的數量，最壞的情況将是指數級的。我們使用深度優先搜尋來進行改善，其複雜度是O(E)，E是DAG中邊的數量。因為每個活動狀态執行個體有至多兩個指針，E的上限是O(2LS)，L是子序列類型的長度(即NFA中狀态的數量)，S是事件的數量。實際上，S可以被設定為視窗大小W，這樣就要在DAG的搜尋中動态檢查視窗的條件限制，是以複雜度就是O(2LW)。
1.3 否定
如前所述，否定操作符(NG)處理SEQ 結構中被SSC忽略的負元件。對于每個輸入事件序列，NG對每個負元件執行兩個任務：(1)檢查負元件中指定的事件是否出現在特定的時間段中；(2)如果這樣的事件存在，檢查它是否滿足所有的相關謂詞。通過了這兩個檢查的任意事件，都會把目前事件序列辨別為False。在以下部分，我們關注于對任務(1)的編輯時和運作時的支援。對于任務(2)的支援是直覺的，我們不再進一步讨論。
在編輯時，任務(1)的時間段按如下方式産生：對于序列(A,!B,C)，時間段定義為(A.timestamp, C.timestamp)；對于序列(!A,B)，使用視窗大小T來定義時間段(B.timestamp-T,B.timestamp)；對于序列(A,!B)的處理有些特殊，給定視窗大小T，查詢不允許a事件之後的T時間内出現b事件，那麼時間段就是(A.timestamp, A.timestamp+T)。
2. 優化技術
2.1 優化序列掃描和構造
當使用的視窗很大時，我們前面描述的算法是極其低效的。為此，我們使用一種輔助資料結構，Active Instance Stack(AIS)，來促進序列構造。算法描述如下。
序列掃描
在序列掃描中，NFA的執行方式與之前相同。除此之外，在每個NFA狀态處建立一個AIS，用來存儲觸發了轉換到目前狀态的事件；這樣的事件就是目前狀态的活動執行個體(active instance)。對應于圖2，圖3展示了三個AIS的内容。在每個棧中，從上到下，活動執行個體(粗體字辨別)表示了它們當時出現的順序。從左到右，在兩個相鄰的棧之間，我們使用每個活動執行個體e的一個額外字段，其中存儲的是當e到達時“前一個棧中最近的執行個體(most recent instance in the previous stack, 簡寫為RIP)”。以B棧中活動執行個體為例，在A棧中位于之前的最近的執行個體是，是以的RIP字段設定為。RIP字段的意思是，如果與有關的序列需要被建立時，那麼在A棧中出現在之前的任何執行個體(也就是)都要與作比對。
圖3 使用AIS的SSC
序列構造
這個方法中不需要使用指針記錄路徑，圖中的箭頭隻是為了友善檢視路徑。當從開始搜尋時，因為的RIP字段是，是以要比對前一個棧中出現在之前的所有b事件，也就是和。
2.2 向下推進謂詞
為了減小中間結果集的大小，我們将謂詞的條件判斷放到SSC中。
2.2.1 把一個等值測試放到SSC中
等值測試實際上起到了“分組”的作用。一個等值測試會把一個大的事件流分成多個小的事件流；每個分組中事件具有相同的屬性值。一個直覺的解決方案是，先把事件流分組，然後對每個分組執行查詢計劃。為了獲得更好的性能，我們使用一種進階的技術，稱為PAIS(Partitioned Active Instance Stack)，它有兩個優點：(1)同時建立多個分組，在序列掃描階段為每個分組建立一個AIS序列；(2)不會對那些與查詢無關的事件類型産生額外開銷(也就是分組的開銷)。
PAIS的基本思想是，在每個狀态中，基于等值測試的屬性對活動執行個體(Active Instance)分組，在同一個分組中建立一個AIS。并且，一個狀态的棧必須與相同分組中前一個狀态中棧連接配接(使用2.1節的算法)。圖4展示了這樣一個例子。放到SSC中的等值測試基于屬性。每個事件的屬性值顯示在圖4下方。
圖4 PAIS
PAIS算法對AIS算法進行了兩點修改：
1) 基于屬性的轉換過濾：在任意一個非起始狀态中，當NFA決定對目前事件作轉換時(例如，從狀态1對進行轉換)，PAIS從目前事件中取得等值測試的屬性值(從中取得’2’)，然後檢查目前狀态的相應分組(狀态1的分組’2’)的AIS是否為空。如果AIS是非空的，就說明具有相等屬性值的前一個事件存在，是以轉換到新的狀态是必要的；否則(狀态1的分組2的AIS是空的)，就把目前事件丢棄。
2) 棧的維護：一旦作出轉換，目前事件就被添加到新狀态的AIS中(被添加到狀态2的分組2的棧裡)，它的RIP字段被設定為前一個狀态的對應的分組中的最後一個執行個體(的RIP字段設為)。
使用PAIS，隻需要在同一個分組的棧中執行序列構造，是以産生的結果數量将大大減少。在圖4中，為執行序列構造隻産生了一個事件序列，而之前的方法産生了三個。
2.2.2 把多個等值測試放到SSC中
查詢中可以包含多個等會測試，如果等值測試被放到SSC中，那麼中間結果的數量可以進一步減少。對PAIS算法的擴充是建立多個屬性分組，并為每個分組建立一個AIS序列。這裡，我們提出兩種可選的方法。
2.2.2.1 Eager Filtering in SS->
第一種方法稱為Multi-PAIS，把所有的等值測試放到序列掃描中，目的是為了在PAIS算法的“轉換過濾”階段過濾掉更多的事件。我們考慮一個簡單的子序列類型(A, B)和兩個等值測試屬性和。圖5展示了這個例子。
圖5 多分組AIS(Multi-PAIS)
在每個NFA狀态中，是針對一個屬性建立的一個PAIS。為了了解這些棧裡的内容，我們描述一下棧是如何構造的：
1) 交叉屬性的轉換過濾：在每個非起始狀态，當NFA決定對目前事件作轉換時(例如，從狀态1對進行轉換)，分兩步進行：
(1)對于每個屬性，找到目前狀态的(狀态1對應的)，根據屬性值取得相應的棧(， )；
(2)對所有的求交集(結果是)。
如果交集是非空的，就說明存在一個之前的事件與目前事件的所有測試的屬性值都相等。
2) 多棧的維護：在轉換之後的新狀态中，根據目前事件的值，把它添加到的合适的棧中。例如，在狀态2中，被添加到的分組’1’的棧中，同時也被添加到的分組’3’的棧中。
當對執行序列構造時，在中都會得到兩個事件序列，盡管最終隻有一個正确的結果序列。于是，選擇操作符還需要進一步過濾掉其餘3個序列。
2.2.2.2 Dynamic Filtering in SC<-
第二種方法稱為DynamicFiltering，把一個等值測試放到序列掃描中，把其他等值測試放到序列構造中。當在AIS中搜尋DAG時，再執行其他的等值測試。與Multi-PAIS相比，Dynamic Filtering不會在序列掃描中過濾掉很多的事件，是以在棧中存在更多的執行個體，但是它不需要在“交叉屬性的轉換過濾”和“多棧的維護”上産生開銷。
SASE也可以把簡單謂詞(應用于單個事件的謂詞，如)放到序列掃描中。
2.3 優化後的查詢計劃
圖6 優化後的查詢計劃
圖6是采用了優化技術之後的查詢計劃，它與基本的查詢計劃相比，具有以下不同點：
Ø 視窗操作符被放到了SS->和SC<-中；
Ø 關于的等值測試被放到了SS->中；
Ø 簡單謂詞被放到了SS->中；
Ø 關于的等值測試被放到了SC<-中。
另外，圖6也展示了一個事件流，優化後的查詢計劃隻産生兩個事件序列(基本查詢計劃産生7個)，是以中間結果的數量大幅度減少了。