摘 要：復雜事件處理技術是在持續(xù)不斷的流數(shù)據(jù)中檢測滿足特定事件序列或對匹配的事件進行統(tǒng)計的一種流數(shù)據(jù)處理技術。在處理帶有Kleene操作符的事件趨勢聚合查詢時，需緩存中間結果來實現(xiàn)不定數(shù)量事件序列的匹配，故對查詢系統(tǒng)的資源需求較大。利用多個查詢之間存在的共享機會，生成用于指導查詢處理的共享計劃，可以有效提高事件趨勢聚合查詢的處理效率。但現(xiàn)有的聚合查詢處理方法生成的共享計劃無法做到隨執(zhí)行環(huán)境的變化而進行實時調整，來支持查詢系統(tǒng)的持續(xù)高效處理。針對上述問題，提出了一種可以動態(tài)更新的多聚合查詢共享方法，以支持實時變化的復雜事件檢測的持續(xù)高效處理。通過提出共享圖數(shù)據(jù)結構和代價模型，實現(xiàn)對所生成共享計劃的實時調整，并引入在線增量聚合執(zhí)行共享方法，進一步提升帶有Kleene操作符的事件趨勢聚合查詢的處理效率。在真實數(shù)據(jù)集和模擬數(shù)據(jù)集上分別進行實驗，并與其他處理聚合查詢的方法進行了實驗對比。實驗結果表明，提出方法能夠有效降低查詢延遲，提高整體查詢的處理性能。

關鍵詞：復雜事件處理； 增量聚合； 多查詢共享； 事件趨勢

中圖分類號：TP315 文獻標志碼：A

文章編號：1001-3695（2024）10-031-3100-10

doi：10.19734/j.issn.1001-3695.2024.02.0037

Multi-aggregate query sharing method in complex event processing

Dong Panpan， Su Hang， Gao Hongyu

（Faculty of Information， Beijing University of Technology， Beijing 100124， China）

Abstract：Complex event processing technology is a streaming data processing technique that detects specific event sequences or performs statistics on matching events in continuously flowing data. When processing trend aggregation queries with Kleene operators， caching intermediate results is necessary to match an indefinite number of event sequences， thus requiring significant resources from the query system. Exploiting opportunities for sharing among multiple queries， generating shared plans to guide query processing can effectively enhance the processing efficiency of trend aggregation queries. However， existing me-thods for handling aggregate queries do not dynamically adjust the generated shared plans in real-time to support continuous and efficient processing of complex event detection in response to changes in the execution environment. Addressing these issues， this paper proposed a dynamically updatable method for multiple aggregate query sharing to support the continuous and efficient processing of real-time changing complex event detection. By introducing the shared graph data structure and cost model， this method achieved real-time adjustment of the generated shared plans. And by using the online incremental aggregation execution sharing method， it further enhanced the processing efficiency of event trend aggregation queries with Kleene operators. This paper conducted experiments on both real and simulated datasets， compared the method with other approaches for handling aggregate queries. The results of the experiments indicate that the method effectively reduces query latency and improves the overall processing performance of queries.

Key words：complex event processing（CEP）; incremental aggregate; multi-query sharing; event trend

0 引言

復雜事件處理（CEP）是一種在事件存儲前對連續(xù)的事件流進行處理的技術［1］，其目的是根據(jù)一組預定義的模式實時地識別有意義的事件或者事件組合［2，3］。CEP廣泛應用于股票、交通運輸和公共衛(wèi)生等領域［4］。這些應用通常依賴于使用包含Kleene操作符的復雜查詢模式。用Kleene操作符表示的子模式能夠匹配一個或者多個與該模式匹配的事件序列（稱為事件趨勢）［5］。由于事件趨勢是任意長度的，所以帶來的計算成本非常高，對于這類查詢的大量工作負載，實時響應難以保證［6，7］。

在實際應用中，CEP往往需要同時處理多個查詢，并且查詢之間存在大量共享數(shù)據(jù)［8］。事件趨勢的多查詢優(yōu)化技術涵蓋了對聚合函數(shù)的處理和多查詢的共享優(yōu)化。作為復雜事件處理的核心研究方向之一，其主要目標是通過共享工作負載中的查詢計算，以有效降低并發(fā)查詢的處理成本［9］。在處理事件趨勢聚合查詢時，優(yōu)化技術首先需識別Kleene模式的共享機會，其次需要確定如何充分利用這些共享機會以加快指定工作負載的執(zhí)行過程。

在聚合查詢處理領域，已經(jīng)有了豐富的研究成果。最初的兩步法首先構造所有的事件趨勢，再從這些事件趨勢中統(tǒng)計聚合值［6］。Poppe等人［2］為應對CET（complex event trend）中共享公共事件子序列導致的性能問題，提出了CET圖的概念，對所有查詢匹配的CET進行編碼。接收到新事件時，系統(tǒng)從每個結束事件節(jié)點向前遍歷以查找與新事件匹配的事件。因此這種設計方法在新事件發(fā)生時會增加CET圖遍歷的成本，存在因部分結果呈指數(shù)增長而導致內存爆炸的問題。Zhang等人［10］對CEP中的模式查詢進行了深入分析，詳細闡述了導致趨勢聚合代價高昂的查詢特征。并將現(xiàn)有的CEP系統(tǒng)映射到相同的層次結構中，為比較不同系統(tǒng)提供了一致的理論框架。這種兩步法處理聚合查詢時需要先進行模式匹配，生成所有的事件序列之后進行統(tǒng)計。尤其是在處理Kleene操作符時，相同的事件可能會被存儲上百至千次，不僅需要大量的內存存儲中間結果，還需要額外的時間開銷用于統(tǒng)計聚合值，導致處理效率較低。

在線聚合方法［11］將聚合操作整合到模式匹配階段，避免了先構建事件趨勢的復雜性，將計算復雜度從指數(shù)級降低到線性。然而在線聚合方法在處理特定場景下存在兩個關鍵限制。表1按照三個維度對現(xiàn)有的在線聚合方法進行了優(yōu)劣對比。

首先，模式中可以包含SEQ和Kleene操作符，在對包含Kleene模式的查詢處理上，現(xiàn)有方法大多限制或完全禁止事件趨勢聚合中的Kleene模式［13］。MCEP［10］僅支持共享非嵌套Kleene模式，而Sharon［6］僅支持共享固定長度的SEQ模式，不支持共享Kleene模式。對Kleene模式的這種限制降低了共享方法的適用性。其次，現(xiàn)有方法對共享決策施加嚴格的限制。Sharon引入了共享沖突的概念，限制一個子模式參與多個共享查詢組。Hamlet［12］和Static［13］方法是事件趨勢聚合查詢處理方法，均對Kleene操作符和查詢之間的共享執(zhí)行進行了優(yōu)化，是目前處理效果較好的兩個方法，但是分別具有不同的局限性。Hamlet僅關注非嵌套Kleene子模式的單一事件類型的共享機會。Static方法通過預先生成共享計劃，然后按照生成的共享計劃嚴格執(zhí)行聚合計算。這種不關注動態(tài)變化信息的方法通常會導致次優(yōu)的共享計劃，錯過潛在的共享機會。

在查詢優(yōu)化方面，主要涉及對多個查詢的共享和對嵌套查詢的處理［14］。多查詢共享技術通常利用查詢操作符的交換性和結合性來支持查詢中的語義等價［15］，即原始查詢可能會更改為不同的形式，但輸出應保持不變。SASE［16］和ZStream［17］分別利用自動機和樹結構處理單一查詢模式，在處理包含Kleene操作符的查詢和嵌套查詢時性能較差且不支持查詢共享。MOTTO［15］利用合并、分解和操作符轉換共享三種技術減少模式查詢的冗余計算，設計多查詢優(yōu)化器提高并發(fā)模式查詢的性能，但不支持包含Kleene操作符的查詢。處理嵌套查詢時，存在兩個主要問題：首先，某些可共享的內部查詢的完整結果可能在共享結果前被直接丟棄［18］；其次，嵌套否定子表達式中只需檢測到其中一個事件即可否定整個結果，但是執(zhí)行時仍需要生成完整的結果［19］，導致資源浪費。大多數(shù)CEP系統(tǒng)通常通過轉變操作符來處理包含嵌套模式的查詢［20］。NEEL［20］使用查詢重寫技術處理嵌套模式查詢，使用基于堆棧的查詢評估策略和迭代嵌套執(zhí)行策略處理嵌套查詢。但在處理帶有Kleene操作符的查詢時仍存在指數(shù)級時間復雜度。

針對以上問題，給定包含SEQ和Kleene操作符以及嵌套模式的事件趨勢聚合查詢工作負載。本文設計共享圖數(shù)據(jù)結構，將共享優(yōu)化問題映射為圖路徑搜索問題，獲取所有可能的共享計劃。設計生成和修剪圖的代價模型，考慮事件流和工作負載的特征，確定查詢在子模式上的共享方案，并實時調整共享計劃。引入在線增量聚合執(zhí)行共享方法，提升事件趨勢聚合查詢的處理效率。

綜上所述，本文的主要貢獻如下：

a）提出了一種共享優(yōu)化方法，用于處理包含Kleene模式的事件趨勢聚合查詢。將涉及Kleene子模式工作負載的共享問題抽象為加權有向無環(huán)圖的最短路徑搜索問題，為工作負載提供了靈活的共享策略。在生成圖的過程中進行修剪，以降低后續(xù)路徑搜索的時間復雜度，從而提高執(zhí)行效率。

b）設計了一種綜合考慮事件流和工作負載特征的代價模型，將其引入到共享圖的生成和路徑搜索過程中，在這些特征發(fā)生變化時高效更新共享計劃，并應用于執(zhí)行過程。

c）引入在線趨勢聚合方法，使用動態(tài)更新的共享計劃指導多聚合查詢結果的增量計算。

d）在真實和模擬數(shù)據(jù)集上對本文方法進行對比實驗和分析，驗證了動態(tài)更新共享計劃方法的適用性和高效性。

1 相關概念

1.1 基本概念

定義1 事件流。事件流I由事件源［21］（如車輛和移動設備）生成的一組連續(xù)的事件組成。事件e是描述應用程序所關注事件的數(shù)據(jù)元組，每個事件含有一個由事件源分配的時間戳e.time［22］。原始事件e屬于一個特定的事件類型E，表示為e.type=E，由指定該事件屬性集及值域的模式來描述該事件。E的特定屬性attr表示為E.attr。本文假定事件按時間戳順序到達，文中的符號和解釋如表2所示。

定義2 事件序列模式P。事件序列模式P定義事件流中的特定事件序列或結構，由操作符和事件類型組成。模式P的形式可以包含E，P1+，（NOT P1），SEQ（P1，P2），（P1∨P2），（P1∧P2），其中E是一個事件類型、P1和P2是模式、+表示Kleene操作符，NOT表示否定，SEQ是事件序列，∨是析取，∧是合取，P1和P2稱為P的子模式。

定義3 Kleene模式。在定義2中的事件序列模式P中，如果P中包含Kleene操作符，那么P就是一個Kleene模式，如果P中的一個Kleene模式的結果應用于另一個Kleene模式，那么P就是一個嵌套Kleene模式［23］。否則，P是一個平坦Kleene模式。

定義4 聚合。在數(shù)據(jù)庫和數(shù)據(jù)處理領域，聚合是指通過匯總、組合或計算數(shù)據(jù)集的值，生成單一的結果。這個結果可以是一個總和、平均值、計數(shù)，或者其他統(tǒng)計性質的值。

定義5 事件趨勢聚合查詢。事件趨勢聚合查詢由5個子句組成。

RETURN子句：返回的聚合結果值；

PATTERN子句：定義2中介紹的事件序列模式；

WHERE子句：謂詞（可選）；

GROUPBY子句：分組（可選）；

WITHIN/SLIDE子句：窗口。

定義6 可共享的模式。一個工作負載Q由一組查詢組成。如圖1所示，工作負載Q1={qa，qb，qc}。給定一個事件趨勢聚合查詢的模式P和一個工作負載Q，如果P出現(xiàn)在至少兩個查詢的模式子句中，則這個模式P是可共享的。在圖1中，三個查詢都包含子模式（P，T）+，（P，T）+即可共享的子模式。

Uber（主要業(yè)務是提供網(wǎng)約車服務和食品配送服務）和Door Dash（在線食品配送平臺）使用復雜的事件趨勢聚合查詢來進行價格計算、預測和路線選擇［12］。由于每個地區(qū)有數(shù)百名用戶、數(shù)千次交易和全國數(shù)百萬個地區(qū)，實時事件分析成為一項具有挑戰(zhàn)性的任務。

如圖1所示，查詢工作負載計算各種行程統(tǒng)計信息，例如每個地區(qū)的訂單總數(shù)、總持續(xù)時間和平均速度。工作負載Q1包含qa，qb，qc三個事件趨勢聚合查詢，每個查詢匹配不同的訂單事件趨勢。每個事件類型對應客戶或送餐員的操作，例如AppOrder和WebOrder分別表示來自APP和網(wǎng)頁上的訂單。事件流中的每個事件都是由客戶和送餐員標識符、操作、地區(qū)和時間戳組成的元組。實際應用中，送餐員通常會在附近接多個訂單，以縮短行駛路程，因此事件趨勢中可出現(xiàn)任意次數(shù)的（P，T）+。查詢qa的返回值為在任意平臺下單并在30 min內完成配送的訂單數(shù)量。謂詞［driver_id］要求訂單中的所有事件必須具有相同的送餐員標識符。查詢qb返回在APP下單且送餐地點為泳池的訂單數(shù)量。查詢qc的返回值為在APP下單但是送餐員行駛速度小于10，因此客戶取消的訂單數(shù)量。三個查詢都包含可共享的子模式SEQ（R，（P，T）+），然而共享SEQ（R，（P，T）+）并不是唯一的共享方案。qa和qb可以共享更長的子模式SEQ（R，（P，T）+，D），而qb和qc包含另一個更長的子模式SEQ（A，R，（P，T）+）。因此在實際應用中，共享包含SEQ和Kleene子模式的查詢，并解決多個相互沖突的共享機會，以最大化共享收益，是一項復雜的任務［24］。

聚合函數(shù)。本文關注可以遞增計算的聚合函數(shù)，對一組值執(zhí)行計算并返回單一的統(tǒng)計結果值［25］。令e為E事件類型的事件，attr為e的屬性。COUNT（*）返回事件趨勢的數(shù)量，MIN/MAX（E.attr）返回所有事件趨勢中事件e的attr最?。ㄗ畲螅┲?，SUM（E.attr）/AVG（E.attr）計算事件趨勢事件e的attr值的總和或平均值。本文使用COUNT（*）作為默認聚合函數(shù)。

1.2 事件趨勢聚合共享問題

為了便于分析多個查詢之間的共享機會，采用SASE中的方法將查詢工作負載表示為有限狀態(tài)自動機，稱為模板。模板中的每個節(jié)點表示查詢中的事件類型E，結束事件類型的節(jié)點加粗表示。模板中的“→”（轉換）對應事件序列模式P中的操作符，連接P中的兩個相鄰的事件類型Ei和Ej，表示為convert（Ei，Ej）。在查詢q中，Ej之前的事件類型Ei表示為pe（Ej，q）。查詢工作負載Q2由四個查詢組成，Q2={q1，q2，q3，q4}，分別為：q1=SEQ（F， D），q2=SEQ（ D），q3=SEQ（E，C，D），q4=SEQ（B，C，D，G）。

按照SASE中的模板生成方法，Q2生成的模板如圖2所示。模版中存在多個共享機會，查詢q1，q2可以共享SEQ（A，B，C）的轉換，查詢q1，q2，q4可共享SEQ（B，C，D）的轉換。

每個convert上的共享方案將一個工作負載中具有該convert的所有查詢劃分為一個查詢集QS，以確保每個QS中的查詢可以分別共享由該convert建模的執(zhí)行過程。圖2中convert（B，C）上的（1，2），4分別表示查詢q1，q2，q4，若查詢q1，q2在執(zhí)行時進行共享，那么convert（B，C）的一個Qs為{q1，q2}。

定義7 工作負載共享計劃。給定工作負載Q的模板，模板中所有convert的共享方案組成一個工作負載共享計劃。

2 動態(tài)共享方法

給定事件趨勢聚合查詢工作負載Q和高速事件流I，多事件趨勢聚合查詢問題就是在事件流I上評估工作負載Q，使得Q中所有查詢的平均查詢延遲時間最?。?2］。

2.1 動態(tài)共享方法框架

聚合查詢的動態(tài)共享方法分為共享計劃生成方法和聚合查詢執(zhí)行方法兩部分。共享計劃生成方法首先將查詢工作負載轉換成模板，并分析潛在的共享機會。分析事件流和工作負載的特征以及共享收益，構建出代價模型。根據(jù)模板和代價模型生成加權有向無環(huán)圖，編碼所有可能的共享機會。在生成圖的過程中對圖進行修剪，最優(yōu)的共享計劃對應圖中權重最小的路徑。圖3展示了動態(tài)共享方法的框架。

執(zhí)行方法使用共享計劃生成方法生成的共享計劃，在事件流I上評估工作負載Q。引入在線聚合方法［12］，將中間聚合從已經(jīng)匹配過的事件傳播到新的事件，利用快照維護每個查詢的中間聚合值，以增量方式計算趨勢聚合值，避免中間結果的構造。當事件流統(tǒng)計信息或者工作負載發(fā)生變化時，將信息反饋回共享計劃生成方法中，根據(jù)當前事件流狀態(tài)更新共享計劃并重新作用于執(zhí)行過程中。

2.2 執(zhí)行方法

執(zhí)行過程采用在線增量聚合的方法支持非共享和共享執(zhí)行。通過以下例子說明執(zhí)行代價，工作負載Q3={q2，q4}，其中q2=SEQ（ D），q4=SEQ（B，C，D，G），兩個查詢的返回值均為COUNT（*）。Q3在事件流S（a1，a2，b1，c1，c2，d1，d2，g1）上進行查詢，并且Q3中有一個共享查詢集QS={q2，q4}。

a）非共享執(zhí)行聚合。在執(zhí)行過程中，對于匹配事件e的每個查詢，維護一個中間聚合值，表示q匹配的以e結尾的聚合數(shù)。在執(zhí)行過程中e的值遞增，遞增的值為由q匹配的e的前驅事件的中間聚合的總和。如果e是q的結束事件類型，則將此聚合值作為查詢q的最終結果輸出。

圖4為工作負載Q3在事件流I上的非共享執(zhí)行情況。當b1到達時，分別為q2和q4創(chuàng)建新的計數(shù)，其中間聚合值對于查詢q2和q4來說分別為2和1。當事件c1到達時，其對于q2和q4的中間聚合從它的前置事件b1傳播得到。對于后續(xù)每個事件，在為每個查詢傳播聚合值時將前置事件的聚合值求和得到其中間聚合值。最后當d1到達時，其中間聚合結果4作為查詢q2的最終聚合值輸出。查詢q2和q4的執(zhí)行成本在于將中間聚合值從前置事件傳播到新到達事件的聚合值中。例如：cost（c1，q2）=cost（c1，q4）=1，cost（c2，q2）=cost（c2，q4）=1。對于工作負載Q3，所有C類事件的非共享執(zhí)行代價為cost（C，Q3）=1×2+1×2=4（由b1指向c1和c2均有兩個箭頭）。

因此得出對于給定的工作負載Q，事件類型E非共享執(zhí)行時的代價為

costnonshare（E，Q）=∑q∈Q ∑Ep∈pe（E，q）|E|×|Ep|（1）

其中：q為工作負載Q中的查詢；|E|和|Ep|分別表示E的事件統(tǒng)計信息和E的前置事件Ep的事件統(tǒng)計信息。

b）共享執(zhí)行聚合。非共享在線聚合會導致對多個查詢的公共子模式進行重復計算，如圖4所示，對于q2和q4來說，b1到c1的中間聚合均需要被傳播一次。為了避免這種重復計算，利用快照來支持高效共享?？煺湛梢允桥c查詢的中間聚合相對應的一個變量，也可以是一個由多個快照值組成的表達式。執(zhí)行方法在傳播過程中通過對其前置快照進行求和不斷更新快照值。共享快照的所有查詢對應的中間聚合值以map的形式存儲在快照中，執(zhí)行時只需要從前置事件到當前事件進行一次快照傳播。如果e的事件類型為查詢q的結束事件類型，則會進行快照值的計算，并輸出聚合結果。

圖5為Q3的共享執(zhí)行情況。查詢q2和q4在共享公共子模式SEQ（B，C，D）時使用事件類型B的快照進行共享，表示為（2，4）B。b1到達時，q2和q4的中間聚合值分別為2和1，將每個查詢對應的值存儲到新的快照spb1，之后將spb1插入到快照數(shù)組中。對于共享查詢集QS即整個工作負載Q3，到事件類型C的傳播由4次減為2次：cost（C，QS）=cost（C，Q3）=2。

得出一個查詢集QS將快照傳播到事件類型E的代價為

costshare（E，QS）=|Ep|×|snap（Ep，Qs）|=

（Ep==Esn）？|Ep|：|Ep|×|Esn|（2）

其中：Ep表示事件類型E的前置事件；snap（Ep，QS）為Ep對于QS的快照事件表達式，表示為Esn；|Esn|為其事件發(fā)生頻率。滿足括號中的等式時選取“：”前的表達式進行計算，不滿足時選取冒號后的表達式進行計算。若一個工作負載Q中有多個QS，則Q對于事件類型E的共享執(zhí)行代價為

costshare（E，Q）=∑QSQcostshare（E，QS）（3）

其中：Q表示工作負載;QS為Q中的共享查詢集;costshared（E，QS）為式（2）中QS對事件類型E的執(zhí)行代價。

如果E是查詢q的結束事件類型或者需要創(chuàng)建新的快照，就會觸發(fā)對快照表達式的求值。對于事件類型D，當d1到達時，需要為q2輸出聚合結果：costeval（D，Q4）=cost（D，q2）=|B|×|D|=2。

對于一個工作負載Q，快照表達式的計算代價為

costeval（E，Q）=∑q∈Q|Ep|×|snap（E，q）|（4）

3 動態(tài)更新圖方法

本文設計共享計劃圖模型，將工作負載共享計劃問題轉換為最佳路徑搜索問題。給定工作負載模板，分析模板中每個轉換的共享機會。根據(jù)模板生成共享計劃圖，涵蓋工作負載中所有可能的共享計劃，為生成最優(yōu)的共享計劃提供搜索空間，使共享收益最大化。

3.1 共享計劃圖模型

定義7 共享計劃圖。共享計劃圖（簡稱為共享圖）是一個具有節(jié)點集和有向邊集的加權有向無環(huán)圖。圖6（c）為一個共享圖模型，圖中的節(jié)點nk表示convert（Ei，Ej）的一個共享方案，Ei和Ej為兩個相鄰的事件類型，Eh為Ej的后置事件。開始節(jié)點nqst指示一個查詢q的開始，結束節(jié)點nqed指示一個查詢q的結束，如果部分查詢Qe具有相同的結束事件類型，則可以為Qe生成同一個結束節(jié)點nQeed。convert（Ei，Ej）的所有候選共享方案節(jié)點（candidate sharing node，CSN）組成CSN（Ei，Ej）。如果存在nk和nm屬于相鄰的兩個CSN，則有向加權邊edge（nk，nm）連接nk到nm。設QS為nk（convert（Ei，Ej））和nm（convert（Ej，Eh））的一個共享查詢集，那么edge（nk，nm）的代價w代表在執(zhí)行nk到nm的共享方案時整個工作負載Q中所有的QS對Ej的執(zhí)行代價（cost（Ej，Q））。

工作負載Q4包含3個查詢，Q4={q1，q2，q3}，其中q1=SEQ（F， D），q2=SEQ（ D），q3=SEQ（E，C，D）。圖6（c）中CSN（A，B）對應的convert（A，B）的共享方案有n2和n3，CSN（B，C）對應的convert（B，C）的共享方案有n4，n5，n6。n2上的（1，2）A表示查詢q1和q2通過共享事件類型A的快照執(zhí)行快照的傳播，n3上的（1）（2）表示查詢q1和q2各自執(zhí)行聚合結果的計算。nq1st，nq2st，nq3st分別表示查詢q1，q2，q3的開始。

CSN（A，B）和CSN（B，C）這樣的連續(xù)CSN中的節(jié)點相連，每個nk∈CSN（A，B）都有一條出邊指向nm∈CSN（B，C）。圖6（b）中convert（A，B）上有兩個查詢q1和q2，在圖6（c）中n2到n5的共享方案中兩個查詢共享執(zhí)行，因此edge（n2，n5）.w=costshare（B，Q4）=cost（B，q1）（或cost（B，q2））。n3到n6查詢q1和q2非共享執(zhí)行，因此edge（n3，n6）.w=costnonshare（B，Q4）=cost（B，q1）+cost（B，q2）。由于工作負載Q4中的三個查詢具有相同的結束事件，所以nQ4ed表示整個工作負載的結束。

共享圖中的所有開始節(jié)點到結束節(jié)點的路徑表示整個工作負載中的所有共享計劃，代價最小的路徑對應當前情況下的最優(yōu)共享計劃。圖6（c）中當前最優(yōu)共享計劃為加粗表示的路徑。

3.2 共享圖生成

3.2.1 節(jié)點生成原則

如果兩個連續(xù)的節(jié)點共享不同的查詢或者快照，執(zhí)行時需要按照式（4）不斷進行快照的計算和更新，以適應具有不同QS和快照的共享計劃，從而損害共享收益。為了使共享收益最大化，為盡可能多的convert保留一個QS。因此在生成節(jié)點時，不是在每個CSN中獨立枚舉節(jié)點［18］，而是從一個節(jié)點nk∈CSN（Ei，Ej）生成下一個節(jié)點nm∈CSN（Ej，Eh）。CSN（Ei，Ej）中的節(jié)點nk可以在CSN（Ej，Eh）中生成多個節(jié)點，但是并非所有節(jié)點都值得生成。如果已知生成的節(jié)點nm∈CSN（Ej，Eh）的入邊和出邊的權重大于同一個CSN中的其他節(jié)點，與其他節(jié)點相比，這樣的局部高代價節(jié)點nm不會生成。

假設在節(jié)點nk中，工作負載Q5={q5，q6，q7，q8}中有兩個共享查詢集：Q1S={q5，q6}，Q2S={q7，q8}。nk的共享方案為查詢q5和q6共享事件類型E0的快照，查詢q7和q8共享事件類型E1的快照，在圖7中表示為節(jié)點nk上的（5，6）E0，（7，8）E1。由節(jié)點nk∈CSN（Ei，Ej）生成CSN（Ej，Eh）中的節(jié)點有四種可能，如圖7所示。case 1繼承所有來自nk的查詢集和快照；case 2保持nk的查詢集不變，為查詢集Q2S生成新的快照；case 3合并所有的查詢集并為新的查詢集生成新的快照；case 4更新了nk的所有查詢集。根據(jù)式（4）得出，case 4生成的節(jié)點對應的入邊和出邊權重都很大，這樣的局部高代價節(jié)點沒有潛在的共享收益，因此不會生成這樣的節(jié)點。下面根據(jù)case 1到case 3的三種情況，提出了三個節(jié)點生成原則。

a）節(jié)點生成原則1（繼承原則）。給定一個節(jié)點nk∈CSN（Ei，Ej），生成節(jié)點nm∈CSN（Ej，Eh），nm繼承所有來自nk的QS和快照。

對于這種情況生成的節(jié)點，如圖7中的case 1所示，nm1維持nk的共享方案，繼承來自nk的共享查詢集和快照事件類型。在按照該計劃執(zhí)行時，只需要將快照傳播到后續(xù)事件，不必按照代價模型計算式（4）進行快照表達式的計算。因此生成的節(jié)點只需要考慮共享成本，根據(jù)式（2）得出，nm1的入邊權重為Q1s和Q2s的共享代價。繼承原則生成的節(jié)點具有最小的入邊權重：

edge（nk，nm1）.w=cost（Ej，Q5）=

costshare（Ej，Q1s）+costshare（Ej，Q2s）

b）節(jié)點生成原則2（更新快照原則）。給定一個節(jié)點nk∈CSN（Ei，Ej），當Ej的發(fā)生頻率小于之前的快照事件類型的發(fā)生頻率時，生成節(jié)點nm∈CSN（Ej，Eh），nm重用來自nk的QS并創(chuàng)建Ej的快照。

使用繼承原則生成的節(jié)點沒有考慮出邊權重，經(jīng)過nm1節(jié)點的路徑可能在nm1之前具有較輕的權重但是在nm1之后具有較重的權重，導致后續(xù)利用該共享方案執(zhí)行時具有較大的代價。因此需要考慮入邊權重較大但是出邊權重變小的情況，降低后續(xù)的執(zhí)行代價。使用更新快照原則生成的節(jié)點需要額外的代價為共享查詢集創(chuàng)建當前事件類型的快照，但是具有較小的出邊權重。如case 2生成的節(jié)點nm2所示，nm2繼承nk的共享查詢集，當|Ej|<|E1|時，為Q2s創(chuàng)建事件類型Ej的快照。因此根據(jù)式（4），nm2的入邊權重還需加上為Q2s生成Ej的新快照的代價。但是使用nm2這種共享方案在后續(xù)將快照傳播到Eh時，Q2s的共享執(zhí)行代價由式（2）中“：”前的計算表達式確定，具有較小的后續(xù)執(zhí)行代價。nm2入邊權重為

edge（nk，nm2）·w=cost（Ej，Q5）=costshare（Ej，Q1s）+

costshare（Ej，Q2s）+costeval（Ej，Q2s）

c）節(jié)點生成原則3（合并原則）。給定一個節(jié)點nk∈CSN（Ei，Ej），生成節(jié)點nm∈CSN（Ej，Eh），nm合并nk的QS并創(chuàng)建Ej的快照。

另一種降低執(zhí)行代價的情況是工作負載中的所有查詢都可以共享Ej的快照，可以合并所有的QS并為其創(chuàng)建Ej的快照。使用這種原則生成的節(jié)點雖然入邊權重較大，但是后續(xù)只需要為一個共享查詢集傳播快照，降低后續(xù)事件Eh的執(zhí)行成本。如case 3生成的節(jié)點所示，nm3合并所有的QS，因此不僅需要對Q1s和Q2s分別輸出前一個共享查詢集的聚合值，還要為新的共享查詢集創(chuàng)建新的快照。得出nm3的權重代價為

edge（nk，nm3）·w=cost（Ej，Q5）=costshare（Ej，Q1s）+

costshare（Ej，Q2s）+costeval（Ej，Q1s）+costeval（Ej，Q2s）

使用合并原則生成的節(jié)點入邊權重均大于繼承和更新快照原則，但是后續(xù)執(zhí)行時只需要為一個共享查詢集傳播快照，其執(zhí)行代價由式（2）中“：”前的表達式確定。

綜上所述，在構造共享圖時，從開始節(jié)點按照生成原則1～3構造每個CSN中的節(jié)點。為每個節(jié)點nk∈CSN（Ei，Ej），生成多個nm∈CSN（Ej，Eh）并為其生成邊和相應的代價，直至生成結束節(jié)點。

3.2.2 修剪原則

在構造圖的過程中通過修剪邊和每個CSN中的節(jié)點以減少圖中的節(jié)點數(shù)量，這種策略雖然可能修剪掉更新時需要用到的節(jié)點，但是可以避免共享圖在早期出現(xiàn)節(jié)點爆炸的現(xiàn)象，有利于初始共享計劃的路徑搜索［12，18］。以圖6（a）所示的工作負載Q4為例，說明在生成共享圖時的修剪過程。初始流統(tǒng)計信息為：|A|=3， |B|=5，|C|=8，|D|=4，|E|=3，|F|=5，工作負載Q4={q1，q2，q3}，對應的開始事件分別為A、B、F，因此為三個查詢各生成一個開始節(jié)點，并為查詢q1和q2生成共享計劃。如圖8（a）所示。

節(jié)點nq1st→n1需要考慮查詢q1的開始事件F，由圖6（b）可知F并未與任何查詢共享，因此cost（F，q1）=|F|=5。由convert（F，A）可知下一步需要將聚合值傳播到事件類型A并生成下一個共享方案節(jié)點n1。節(jié)點n1→n2需要為查詢q1將聚合值傳播到事件類型A并創(chuàng)建事件類型A的快照。因此cost（A，q1）=costshare（A，q1）=|F|×|A|。

生成的后置節(jié)點如圖8（b）所示，在由節(jié)點n2生成后繼節(jié)點的時候按照3.2.1節(jié)所述有兩種選擇。原則1：繼續(xù)維持事件類型A的快照（節(jié)點n4）；原則2：創(chuàng)建事件類型B的快照（節(jié)點n5）。對于n2→n4，由于事件類型B的前置事件就是A，所以只需要對A的快照進行統(tǒng)計即可，且q1和q2共享A的快照，有cost（B，Q4）=costshare（B，Q4）=|A|=5；對于n2→n5，不僅需要將A的快照傳播到B，還需要分別為q1和q2生成B的快照，因此cost（B，Q4）=costshare（B， Q4）+costeval（B，Q4）=|A|+2×|A|×|B|=33。后續(xù)節(jié)點根據(jù)節(jié)點生成原則生成整個共享圖，結果如圖9（a）所示。

如圖9中的n5所示，nq2st到n5有兩條路徑，對于n2→n5，nq2st到n5的代價為36；對于n3→n5，nq2st到n5的代價為103。因此n3→n5的邊可以修剪，修剪的邊不影響共享計劃的最優(yōu)性。

邊修剪原則：給定一個節(jié)點nm，當從起始節(jié)點到nm有多條路徑時，只需保留權重最小的最優(yōu)路徑，其他路徑通過的邊可以安全地修剪。

命題1 按照邊修剪原則修剪邊之后，不會影響共享計劃的最優(yōu)性。

證明 通過反證法證明命題一，給定一個節(jié)點nm∈CSN（Ej，Eh），n0和n1分別是來自CSN（Ei，Ej）的兩個節(jié)點，對應的邊分別為edge（n0，nm）和edge（n1，nm），假設n0.ds+edge（n0，nm）.w<n1.ds+edge（n1，nm）.w。如果最優(yōu)路徑P沿edge（n1，nm）經(jīng)過n1和nm，將P分為兩部分，第一部分P1為所有的開始節(jié)點到節(jié)點nm，第二部分P2為nm到所有的結束節(jié)點。路徑P的代價為：P.w=P1.w+P2.w=n1.ds+edge（n1，nm）.w+P2.w。當經(jīng)過n0訪問nm時對應的路徑為代價為：.w=n0.ds+edge（n0，nm）.w+P2.w，得出.w<P.w，因此P不是最優(yōu)路徑，edge（n1，nm）可以安全地修剪。

節(jié)點n4和n5屬于相同的QS={q1，q2}，但是分別具有不同事件類型的快照A和B，由于|A|<|B|，由式（2）和（4）得出n4.ds<n5.ds，并且n4.de<n5.de，節(jié)點n5可以安全地修剪，并且節(jié)點n9完全由n5生成，所以n9也會被安全地修剪。修剪后每個節(jié)點代價如圖9（b）所示，根據(jù)兩個修剪原則，圖9（a）中的虛線部分的邊和n5，n9，n10節(jié)點可以安全地被修剪。

給定同一個CSN中的兩個節(jié)點，如果這兩個節(jié)點屬于同一個共享查詢集，那么這兩個節(jié)點是可比節(jié)點。

節(jié)點修剪原則：給定兩個可比節(jié)點nm和nk，如果nm到所有開始節(jié)點和結束節(jié)點的權重都比nk大，那么節(jié)點nm可以安全地修剪，并且該節(jié)點的出邊和完全由該節(jié)點生成的后置節(jié)點也可以安全地修剪。

命題2 按照節(jié)點修剪原則修剪節(jié)點之后，不會影響共享計劃的最優(yōu)性。

證明 通過代價模型證明命題2，給定CSN（Ej，Eh）中分別共享事件類型A和B的兩個節(jié)點nk和nm，其中|A|<|B|。根據(jù)式（2）得出，由于nk的快照事件發(fā)生頻率較小，應用nm的共享成本小于應用nk的成本。后續(xù)如果需要進行快照計算，根據(jù)式（4）得出A快照的計算成本小于B的計算成本，因此從nk到所有結束節(jié)點的路徑權重比nm都小，并且nk.ds<nm.ds。因此節(jié)點nm可以安全地修剪。

3.2.3 對Kleene模式的優(yōu)化

在執(zhí)行過程中，Kleene模式可以匹配任意多個滿足模式的事件趨勢，其匹配的事件數(shù)量呈指數(shù)增長。因此本節(jié)重點關注對Kleene模式的共享優(yōu)化，將Kleene模式的優(yōu)化同其他部分隔離，為其構建Kleene子圖。若需要同其他部分連接，則將Kleene子圖的最優(yōu)共享計劃插入到共享圖的相應位置，并在整個圖中進一步修剪，得到全局最優(yōu)共享計劃。

為了更有效地展示對Kleene模式的優(yōu)化方法，本節(jié)以工作負載Q6={q9，q10}的共享計劃生成過程為例進行介紹。假設工作負載Q6中的兩個查詢需要共享子模式SEQ（A，（B，C）+，D）+。圖10（a）為Q6的工作負載模板，在該模板中存在兩條可以構成循環(huán)的convert，分別為convert（C，B）和convert（D，A），將這種convert稱為Kleene convert。

在共享圖模型中，連續(xù)的兩個CSN中的節(jié)點相連。圖10（a）中的兩個Kleene convert為convert（C，B）和convert（D，A），這兩個convert的候選共享方案分別為CSN（C，B）和CSN（D，A）。兩個CSN中的節(jié)點同樣在Kleene子圖也會構成循環(huán)。為方便區(qū)分，將Kleene子圖的路徑稱為循環(huán)路徑。在Kleene子圖的所有循環(huán)路徑中，具有不同的共享方案的路徑會導致較高的執(zhí)行代價，這樣的路徑?jīng)]有必要生成。

命題3 具有不同共享方案節(jié)點的循環(huán)路徑可以安全地修剪。

證明 設nk和nm是循環(huán)路徑P中的兩個節(jié)點，共享查詢集為QS，證明共享方案：nk=nm。若nk和nm通過不同事件類型的快照對QS進行共享（分別為E0和E1）。假設|E0|>|E1|，則根據(jù)節(jié)點生成原則（更新快照），由于nk的快照多于nm的快照，nk到nm之間一定存在一條具有潛在收益的路徑。然而，由于P是一個循環(huán)，從nm到nk也存在一條路徑。根據(jù)節(jié)點生成原則（更新快照原則），將快照數(shù)量從E0和增加到E1伴隨著額外的計算成本，并不會帶來共享好處。因此P.w一定會大于P′.w（P′經(jīng)過的所有節(jié)點均通過事件類型E1的快照對QS進行共享）。P不是最優(yōu)路徑，循環(huán)路徑P可以被安全地修剪。

排除上述不會生成的循環(huán)路徑之后。提出循環(huán)路徑生成原則：假設模板中存在平坦的Kleene子模式SEQ（E0，E1，…，Ek）+，該子模式的Kleene子圖有k+1個CSN，其中k個是SEQ的CSN（Ei，Ei+1）（0≤i<k），一個是Kleene循環(huán)CSN（Ek，E0）。Kleene子圖中的路徑P是一個循環(huán)，包含每個CSN中的一個節(jié)點。當且僅當路徑P經(jīng)過的所有節(jié)點使用的是相同事件類型的快照共享相同的QS時，才會生成循環(huán)路徑P，否則，所有節(jié)點上的共享方案均是非共享執(zhí)行。

循環(huán)路徑生成原則同樣適用于嵌套Kleene子模式的Kleene子圖，對應的路徑是嵌套循環(huán)路徑。由于每個單循環(huán)路徑中的節(jié)點具有相同的共享方案，那么嵌套循環(huán)路徑中的所有節(jié)點同樣具有相同的共享方案。

以工作負載Q6為例，事件流統(tǒng)計信息分別為：|A|=10，|B|=5，|C|=3，|D|=15。圖10（b）表示從節(jié)點nk∈CSN（Ei，Ej）生成節(jié)點nm∈CSN（Ej，Eh）時需要傳播的事件類型的執(zhí)行代價，圖10（e）（f）分別為選取不同事件類型的快照進行共享的嵌套循環(huán)路徑。路徑中的每條邊都用代價模型計算的權重進行標記。

同樣對Kleene子圖采用修剪原則，對高代價的節(jié)點進行修剪。對于每條路徑，都有一條來自Kleene子圖前一部分共享圖的邊，以及作為后續(xù)延伸的源節(jié)點nk，令nk.ds為各路徑的權重。工作負載Q6都從事件類型A開始，n1到n4來自同一個節(jié)點，入邊權重均為10。各節(jié)點到開始節(jié)點的代價如表3所示。

選取事件類型C為快照事件類型時，整個共享執(zhí)行過程代價最小，因此選擇C為此工作負載的快照事件類型。

3.3 共享計劃更新方法

在處理事件趨勢聚合查詢時，可能發(fā)生變化的信息有事件流統(tǒng)計信息和工作負載信息。當工作負載減少時，直接從當前共享計劃中刪除對應的查詢，并且不再為該查詢傳播聚合值以及生成最后結果。當工作負載增加時，由于在已經(jīng)生成的共享圖中搜索可共享的節(jié)點需要消耗大量的內存，所以只為新的工作負載單獨生成共享計劃，不再參與之前的共享。

本文設計了檢測更新計劃的代價模型，用于實時更新共享計劃方法，提高事件趨勢聚合查詢的處理性能。當事件流統(tǒng)計信息發(fā)生變化時，對于帶有Kleene操作符的工作負載，在3.2.3節(jié)已經(jīng)詳細闡述過Kleene模式和SEQ模式單獨分析共享機會，因此只需單獨進行更新。

在事件流信息發(fā)生變化時，需要考慮以下兩個問題：a）是否需要更新共享計劃；b）需要更新計劃時，如何更新節(jié)點的信息。分析發(fā)現(xiàn)，未參與共享的事件類型頻率發(fā)生變化，或者快照事件類型的發(fā)生頻率變小時，根據(jù)式（2）得出不會更改共享的快照事件類型，因此不需要更新共享計劃，按照原計劃執(zhí)行；參與共享的快照事件類型頻率變大或者快照事件類型的后置事件頻率變小，則需要考慮更新共享計劃，并將新的共享計劃應用到后續(xù)的執(zhí)行過程中。判斷條件如下。

以SEQ模式為例，在一個共享的查詢集QS中，查詢的數(shù)量為|QS|。圖11為QS的共享圖中的一部分，節(jié)點n1處的共享方案是以Ej為QS的快照事件類型進行共享，之后需要將快照傳播到事件類型Eh。P1和P2分別為虛線表示的初始路徑和實線表示的更新后的路徑。

圖11中三部分的代價計算如表4所示。

在初始條件為|Ej|<|Eh|時，每個部分的代價均有P1.w<P2.w，得出總路徑代價P1.w<P2.w，因此選取P1為共享計劃。但是當Ej和Eh的事件頻率發(fā)生變化之后，三部分的代價均發(fā)生變化。當P1.w>P2.w時，該查詢集的共享計劃需要進行調整。

表4中|QS|為共享查詢 集中查詢的數(shù)量，|Ej|、|Eh|和|Es|分別為QS 共享的快照事件類型Ej、Eh和Eh的所有后綴事件Es的事件發(fā)生頻率，Eed為當前QS共享的最后一個事件類型。

本文設計了動態(tài)更新共享計劃的算法以適應實時變化的事件流信息，如算法1所示。

算法1具有四個輸入?yún)?shù)。P為原始路徑，SE為事件流統(tǒng)計信息，工作負載模板T中存儲了工作負載中查詢的信息，E1為檢測到事件發(fā)生頻率產生變化的事件類型。

算法1首先將原始路徑P以及對應的路徑代價賦值給更新后的路徑P′（第1行）。之后在模板T中通過廣度優(yōu)先搜索算法得到事件發(fā)生頻率變化的事件類型E1對應的convert，得到其前置和后置事件類型，并分別將前置和后置事件類型存儲在對應的集合中（第2～4行）。

第5行中snapSet為當前QS的快照事件類型集合，檢測E1是否在snapSet中。若E1是快照事件類型，則檢測E1是否比后置事件類型Es的事件發(fā)生頻率大（第6，7行），當E1的事件發(fā)生頻率大于Es的時候，需要檢測E1和Es是否滿足式（5）以更新共享計劃（第8行）。如果滿足不等式，則在原始路徑P中找到convert（E1，Es）對應的節(jié)點n1（第9行）。在n1之后按照節(jié)點生成原則（更新快照）生成以Es為快照事件類型的共享方案節(jié)點（第10行）。updatePath（）方法將生成的節(jié)點插入到新的共享計劃P′中，并更新相應的代價，之后按照節(jié)點生成原則（繼承）生成后續(xù)節(jié)點直至得到新的共享計劃P′（第11行）。

若E1不是快照事件類型，需要在路徑P中搜索到convert（E0，Es）對應的共享方案節(jié)點n2，在n2中得到共享查詢集QS以及共享的快照事件類型Esn（第12～15行）。當|E1|<|Esn|時，需要檢測Esn和E1是否滿足式（5）以更新共享計劃（第16行）。如果滿足不等式，則在n2之后按照節(jié)點生成原則（更新快照）生成以E1為快照事件類型的共享方案節(jié)點，直至得到新的共享計劃P′（第17，18行）。最后返回新的共享計劃P′（第19行）。

算法1 共享計劃更新算法updateSharingPlan

輸入：原始路徑P；事件流統(tǒng)計信息SE；工作負載模板T；事件發(fā)生頻率產生變化的事件類型E1。

輸出：更新后的路徑P′。

1 P′←P，P′.w←P.w；

2 在模板T中搜索到convert（Ep，E1）以及convert（E1，Es）；

3 prefixSet←Ep；

4 suffixSet←Es；

5 if E1 in snapSet

6 for each Es in suffixSet

7 if |E1|>|Es| then

8 if E1和Es滿足式（5） then

9 在P中找到convert（E1，Es）對應的節(jié)點n1；

10 n1.rightNode←generateNode（n′，Es）；

11 updatePath（P′，P′.w，n′）；

12 else for each Ep in prefixSet

13 在P中找到convert（Ep，E1）對應的節(jié)點n2；

14 QS←node.getSet（）；

15 Esn←snap（Ep，QS）；

16 if |E1|<|Esn| then

17 n2.rightnode←generateNode（n′，E1）；

18 updatePath（P′，P′.w，n′）；

19 return P′；

4 實驗

通過實驗對本文提出的動態(tài)更新共享計劃方法的有效性進行了分析和驗證。硬件環(huán)境為12th Gen Intel CoreTM i7-1260P，64 GB內存，2.5 GHz頻率。軟件平臺為Ubuntu 22.04，編程語言是Java，使用OpenJDK 16.0.1實現(xiàn)了方法的編寫并運行實驗。從多個維度對實驗結果進行分析說明，每個實驗平均運行15次。通過性能對比證明本文方法的有效性。

4.1 實驗設置

4.1.1 事件流數(shù)據(jù)集

在三個數(shù)據(jù)集上進行了實驗，兩個數(shù)據(jù)集是真實的股票和公交車數(shù)據(jù)集，一個數(shù)據(jù)集是通過事件流生成方法生成的模擬數(shù)據(jù)流，事件的變化頻率為3～5倍。

股票數(shù)據(jù)集包含NASDAQ 20年的股票價格歷史記錄。每條記錄代表一個事件，包含公司標識符、時間戳（分鐘）、開盤價和收盤價、最高價和最低價以及交易量。事件類型與3 258個唯一的公司標識符相對應。

公交車GPS數(shù)據(jù)集為2018年收集的都柏林公交車GPS記錄組成。每條記錄都是帶有時間戳的元組（微秒），包含線路ID、車輛行程ID、擁堵指示、坐標和延遲時間。有4 368個唯一行程ID。

模擬數(shù)據(jù)流是ABC類型的事件流，每個事件都帶有時間戳以及各自的屬性值。根據(jù)自定義的事件類型數(shù)量、屬性個數(shù)和屬性值的范圍生成相應的事件流，事件流中的每個事件都根據(jù)指定的頻率隨機生成和變化，包含5 000個原始事件。

4.1.2 工作負載數(shù)據(jù)集

為了評估共享計劃更新方法在不同查詢負載下的有效性，在每個數(shù)據(jù)集上設置了三種類型的工作負載。SEQ工作負載具有不同的可共享SEQ模式、分組、謂詞和聚合函數(shù)（count（*）、max等）。Kleene模式的工作負載分為可共享的平坦Kleene模式和嵌套Kleene模式，Kleene子模式的長度為2～10；嵌套Kleene子模式的嵌套層數(shù)為1～5層，謂詞、時間窗口和聚合設置與SEQ工作負載相同?；旌瞎ぷ髫撦d包括SEQ子模式和Kleene子模式，Kleene模式占比由20%調整到100%。

4.1.3 衡量指標

對于執(zhí)行工作負載的優(yōu)化，以秒為單位度量執(zhí)行時間，即接收工作負載與生成聚合結果的平均時間差。包括模板構建、圖構建、路徑搜索、圖更新和生成聚合結果值的時間。峰值內存是執(zhí)行過程中消耗的最大內存。執(zhí)行時，使用以秒為單位的延遲時間作為產生聚合結果的時間與最后一個相關事件到達時間的平均時間差。吞吐量是所有查詢每秒處理的平均事件數(shù)。

4.2 實驗分析

實驗1 首先比較了本文方法Dynamic和當前處理聚合查詢效果較好的兩個方法（Static［12］和Hamlet［11］）執(zhí)行的延遲時間和吞吐量。這兩種方法均支持處理Kleene操作符以及共享查詢之間的執(zhí)行。但是Static方法所生成的共享計劃并不適用于實時變化的動態(tài)數(shù)據(jù)流。在事件流或工作負載出現(xiàn)波動時，Static方法的性能顯著下降。Hamlet方法只針對E+這種平坦的Kleene模式進行了優(yōu)化，將短時間內發(fā)生的同一事件類型的事件視為突發(fā)事件。每次發(fā)生突發(fā)事件時，都需要進行共享決策，導致執(zhí)行效率不高。

Kleene模式占比為固定的60%，將工作負載查詢數(shù)量從12增加至120在股票數(shù)據(jù)集上進行了實驗。圖12（a）（b）分別為延遲時間和吞吐量的對比。在延遲時間上本文方法分別比Hamlet和Static方法性能提升大約9倍和3倍，吞吐量上分別比Hamlet和Static提高了80%和50%。Dynamic方法在動態(tài)數(shù)據(jù)流環(huán)境下，不斷分析當前的執(zhí)行信息和共享計劃，評估共享收益以選擇不同事件類型的快照，進行動態(tài)調整。因此能夠更高效地評估工作負載。

實驗2 比較了本文的Dynamic方法和由嚴格的共享計劃指導方法的整體運行時間，包括生成圖和共享計劃，處理聚合查詢工作負載并生成最后的結果值。并對修剪和未修剪的方法分別進行了對比實驗。

對于SEQ工作負載，分別評估了對修剪和不修剪的共享圖上更新共享計劃的延遲時間。工作負載中的查詢數(shù)量由40增加到200，事件頻率變化為3～5倍，評估了對公交車數(shù)據(jù)集的處理時間。執(zhí)行過程中，判斷是否需要更新共享計劃需要占用一定的時間和內存空間，未修剪共享圖的路徑搜索時間大于修剪之后的搜索時間，但是如果需要更新共享計劃，修剪的共享圖在生成圖時可能會刪除更新之后的候選共享計劃中的節(jié)點，因此需要重新生成新的節(jié)點并重新對圖進行修剪。如圖13（a）所示，本文方法始終優(yōu)于靜態(tài)共享計劃執(zhí)行的3～5倍。綜上所述，動態(tài)更新共享計劃有效地加快了聚合查詢的執(zhí)行速度。

對于Kleene子模式，比較了在包含9lyT4iOY4zEq1w5wDJ5fT7Zh61UhSOP1c5/tEvMOal0=平坦Kleene子模式的100個查詢的工作負載，將Kleene子模式的長度由2變化到10。本文方法對于給定的Kleene工作負載，如圖13（b）所示，為Kleene子模式生成的子圖總是很小，因此在更新共享計劃時會消耗更少的時間和更低的內存。對于嵌套的Kleene子模式，將Kleene子模式的嵌套層數(shù)從1層調整到5層進行了對比實驗，如圖13（c）所示，隨著嵌套層數(shù)的增加，靜態(tài)方法的執(zhí)行時間增加得越多，而本文方法可以對共享計劃進行動態(tài)調整，因此對比靜態(tài)方法，執(zhí)行時間顯著減少。

對于混合工作負載，圖13（d）展示了在包含100個查詢的混合工作負載下動態(tài)更新和靜態(tài)共享計劃的執(zhí)行時間。將包含Kleene模式的查詢（以下簡稱為Kleene查詢）所占百分比從20%調整到100%。隨著Kleene查詢數(shù)量的增加，本文方法的優(yōu)化性能達到靜態(tài)執(zhí)行方法的3倍。當Kleene查詢的比例增加到40%時，SEQ查詢的數(shù)量減少，降低了SEQ查詢處理的復雜度。當Kleene查詢的比例大于50%時，優(yōu)化時間主要用于優(yōu)化Kleene查詢共享的時間。由于對Kleene子圖采用了修剪原則，所以優(yōu)化性能隨著Kleene查詢的增多而減少。

實驗3 圖14（a）（b）分別為在股票和公交車數(shù)據(jù)集上將工作查詢負載中的查詢從12增加到120的峰值內存的對比結果。由于動態(tài)調整了共享計劃，減少了不必要的快照傳播的代價，本文方法在兩個數(shù)據(jù)集上的峰值內存消耗占靜態(tài)方法內存消耗的50%～70%。

上述實驗表明，本文提出的動態(tài)更新共享計劃的方法能夠有效適應實時變化的事件流和工作負載，無論是在SEQ模式還是在Kleene模式下，都表現(xiàn)出較好的性能。

5 結束語

本文研究了應對動態(tài)變化的數(shù)據(jù)信息時處理聚合查詢的問題。針對包含Kleene操作符的多個聚合查詢，設計了共享圖模型，將查詢之間的共享問題抽象為加權有向無環(huán)圖的最佳路徑搜索問題。綜合考慮了實時變化的事件流和工作負載信息，設計出代價模型，以最大化共享收益。將代價模型應用到圖生成過程，并在生成圖時對其進行修剪，加快了生成共享計劃的時間。降低了處理聚合查詢的延遲時間，提高了系統(tǒng)的吞吐量，實現(xiàn)了高效的更新共享計劃。實驗結果驗證了動態(tài)更新共享計劃方法對執(zhí)行性能的有效提升，在處理動態(tài)數(shù)據(jù)的聚合查詢時提供了有力的解決方案。

參考文獻：

［1］邱濤， 謝沛良， 鄧國鵬， 等. 面向實時事件流的復雜事件處理方法［J］. 計算機應用研究， 2022， 39（9）： 2677-2682， 2688. （Qiu Tao， Xie Peiliang， Deng Guopeng， et al. Complex event processing method over real-time event streams［J］. Application Research of Computers， 2022， 39（9）： 2677-2682，2688.）

［2］Poppe O， Lei Chuan， Ahmed S， et al. Complete event trend detection in high-rate event streams［C］//Proc of the ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2017： 109-124.

［3］夏秀峰， 武孟達， 張楊， 等. 基于動態(tài)匹配策略的復雜事件處理方法［J］. 計算機應用研究， 2023， 40（11）： 3341-3347. （Xia Xiu-feng， Wu Mengda， Zhang Yang， et al. Efficient complex event processing based on dynamic matching strategy［J］. Application Research of Computers， 2023， 40（11）： 3341-3347.）

［4］喬雅正， 程良倫， 王濤，等. 地鐵列車環(huán)境中多依賴復雜事件處理研究［J］. 計算機應用研究， 2019， 36（8）： 2355-2358， 2367. （Qiao Yazheng， Cheng Lianglun， Wang Tao， et al. Study on multi-dependency complex event processing in subway train environment［J］. Application Research of Computers， 2019， 36（8）： 2355-2358，2367.）

［5］Kolchinsky I， Schuster A. Real-time multi-pattern detection over event streams［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2019： 589-606.

［6］Poppe O， Rozet A， Lei Chuan， et al. Sharon： shared online event sequence aggregation［C］//Proc of the 34th ICDE International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2018： 737-748.

［7］Poppe O， Lei Chuan， Rundensteiner E A， et al. GRETA： graph-based real-time event trend aggregation［J］. The VLDB Endowment， 2017， 11（1）： 80-92.

［8］Perera K P D， Ahangama S. A review of query optimization techniques for complex event processing［C］//Proc of the 4th ICITR International Conference on Information Technology Research. Piscata-way， NJ： IEEE Press， 2019： 1-7.

［9］Hong M， Riedewald M， Koch C， et al. Rule-based multi-query optimization［C］//Proc of the 12th ACM EDBT International Conference on Extending Database Technology： Advances in Database Techno-logy. New York： ACM Press， 2009： 120-131.

［10］Zhang Haopeng， Diao Yanlei， Immerman N. On complexity and optimization of expensive queries in complex event processing［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2014： 217-228.

［11］Qi Yingmei， Cao Lei， Ray M， et al. Complex event analytics： online aggregation of stream sequence patterns［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2014： 229-240.

［12］Poppe O， Lei Chuan， Ma Lei， et al. To share， or not to share online event trend aggregation over bursty event streams［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2021： 1452-1464.

［13］Mei Huiyao， Chen Hanhua， Jin Hai， et al. Efficient complete event trend detection over high-velocity streams［C］//Proc of the 50th ACM ICPP International Conference on Parallel Processing. New York： ACM Press， 2021： 1-12.

［14］趙會群， 李會峰， 劉金鑾. RFID物聯(lián)網(wǎng)復雜事件模式聚類算法研究［J］. 計算機應用研究， 2018， 35（2）： 339-341. （Zhao Huiqun， Li Huifeng， Liu Jinluan. Study on RFID complex event pattern clustering algorithm of Internet of Things［J］. Application Research of Computers， 2018， 35（2）： 339-341.）

［15］Zhang Shuhao， Vo H T， Dahlmeier D， et al. Multi-query optimization for complex event processing in SAP ESP［C］//Proc of the 33rd ICDE International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2017： 1213-1224.

［16］Wu E， Diao Yanlei， Rizvi S. High-performance complex event processing over streams［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2006： 407-418.

［17］Mei Yuan， Madden S. Zstream： a cost-based query processor for adaptively detecting composite events［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2009： 193-206.

［18］Ma Lei， Lei Chuan， Poppe O， et al. Gloria： graph-based sharing optimizer for event trend aggregation［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2022： 1122-1135.

［19］Liu Mo， Rundensteiner E， Dougherty D， et al. High-performance nested CEP query processing over event streams［C］//Proc of the 27th International Conference on Data Engineering. Piscataway， NJ： IEEE Press， 2011： 123-134.

［20］Liu Mo， Ray M， Rundensteiner E A， et al. Processing nested complex sequence pattern queries over event streams［C］//Proc of the 7th ACM DMSN International Workshop on Data Management for Sensor Networks. New York： ACM Press， 2010： 14-19.

［21］邱濤， 丁建麗， 夏秀峰，等. 基于有序事件列表的高效復雜事件匹配算法［J］. 計算機應用， 2023， 43（2）： 423-429. （Qiu Tao， Ding Jianli， Xia Xiufeng， et al. Efficient complex event matching algorithm based on ordered event lists［J］. Journal of Computer App-lication， 2023， 43（2）： 423-429.）

［22］施建明， 王偉， 王功. 基于Flink復雜事件處理的空間站實驗柜排廢氣安全監(jiān)測［J］. 載人航天， 2023， 29（1）： 102-109. （Shi Jianming， Wang Wei， Wang Gong. Safety monitoring of exhaust gas discharge of experimental rack onboard space station based on Flink CEP［J］. Manned Spaceflight， 2023， 29（1）： 102-109.）

［23］Schultz-Mller N P， Migliavacca M， Pietzuch P. Distributed complex event processing with query rewriting［C］//Proc of the 3rd ACM DEBS International Conference on Distributed Event-Based Systems. New York： ACM Press， 2009： 1-12.

［24］Ray M， Lei Chuan， Rundensteiner E A. Scalable pattern sharing on event streams［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2016： 495-510.

［25］Liu Mo， Rundensteiner E， Greenfield K， et al. E-cube： multi-dimensional event sequence analysis using hierarchical pattern query sharing［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2011： 889-900.

［26］Poppe O， Lei Chuan， Rundensteiner E A， et al. Event trend aggregation under rich event matching semantics［C］//Proc of ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2019： 555-572.