Evaluating window joins over unbounded streams

J. Kang, J. F. Naughton, S. D. Viglas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We investigate algorithms for evaluating sliding window joins over pairs of unbounded streams. We introduce a unit-time-basis cost model to analyze the expected performance of these algorithms. Using this cost model, we propose strategies for maximizing the efficiency of processing joins in three scenarios. First, we consider the case where one stream is much faster than the other. We show that asymmetric combinations of join algorithms, (e.g., hash join on one input, nested-loops join on the other) can outperform symmetric join algorithm implementations. Second, we investigate the case where system resources are insufficient to keep up with the input streams. We show that we can maximize the number of join result tuples produced in this case by properly allocating computing resources across the two input streams. Finally, we investigate strategies for maximizing the number of result tuples produced when memory is limited, and show that proper memory allocation across the two input streams can result in significantly lower resource usage and/or more result tuples produced.
Original languageEnglish
Title of host publicationData Engineering, 2003. Proceedings. 19th International Conference on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Print)0-7803-7665-X
Publication statusPublished - Mar 2003


Dive into the research topics of 'Evaluating window joins over unbounded streams'. Together they form a unique fingerprint.

Cite this