Efficient Execution of Sliding-Window Queries Over Data Streams
Moustafa A. Hammad, Walid G. Aref, Michael J. M. Franklin, Mohammed P. Mokbel, Ahmed K. Elmagarmid · Purdue e-Pubs (Purdue University System) · 2003
EmcT!Jing dala stnm.m processing systems rely on windowing /0 enable em-lhe-fly processing oj continuous queries Dvcr unbounded streams.A~' a resuU, swe1ll.1 recent efforL<; have developed window-aware implemcrltations of Query operators such as joins Gnd ag,qregates.'This focus em individual operators, however, ignores the larger issuc of how to coordinate the pipelined execution of such operators when combined into a full windowed query plan.In this paper, we first show how the slmightjonJJurn application oj traditional pipclincd que111 processing techniques to sliding window queries call I"CSlllt in inefficient and incorrect behavior.We then present three alternative execution techniques that guarantee correct behamor Jar pipelined sliding window querie.~anddevelop new algorilhms for correclly evaluating window-based duplicateelimination, Group-By and Set operators in lhis context.We implemented all of the~'e teclmiques in a prololype data stream system and report lhe results of a detailed performance study of the system.