Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources Stratis Viglas, Jeffrey F. Naughton, and Josef Burger   View Paper (PDF)   Return to Streaming (Session A8) Abstract Recently there has been a growing interest in join query evaluation for scenarios in which inputs arrive at highly variable and unpredictable rates. In such scenarios, the focus shifts from completing the com- putation as soon as possible to producing a prefix of the output as soon as possible. To handle this shift in focus, most solutions to date rely upon some combi- nation of streaming binary operators and "on-the-fly" execution plan reorganization. In contrast, we con- sider the alternative of extending existing symmetric binary join operators to handle more than two inputs. Toward this end, we have completed a prototype im- plementation of a multi-way join operator, which we term the "MJoin" operator, and explored its perfor- mance. Our results show that in many instances the MJoin produces outputs sooner than any tree of bi- nary operators. Additionally, since MJoins are com- pletely symmetric with respect to their inputs, they can reduce the need for expensive runtime plan reor- ganization. This suggests that supporting multi-way joins in a single, symmetric, streaming operator may be a useful addition to systems that support queries over input streams from remote sites. ©2004 Association for Computing Machinery