Association for Computing Machinery
Online aggregation is a promising solution to achieving fast early responses for interactive ad-hoc queries that compute aggregates on a large amount of data. Essential to the success of online aggregation is a good non-blocking join algorithm that enables both high early result rates with statistical guarantees and fast end-to-end query times. The authors analyze existing non-blocking join algorithms and find that they all provide sub-optimal early result rates and those with fast end-to-end times achieve them only by further sacrificing their early result rates. They propose a new non-blocking join algorithm, Partitioned expanding Ripple Join (PR-Join), which achieves considerably higher early result rates than previous non-blocking joins, while also delivering fast end-to-end query times.