PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees

Download Now
Provided by: Association for Computing Machinery
Topic: Big Data
Format: PDF
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.
Download Now

Find By Topic