Please use this identifier to cite or link to this item:

Wander Join: Online Aggregation via Random Walks

Authors Li, Feifei
Wu, Bin HKUST affiliated (currently or previously)
Yi, Ke View this author's profile
Zhao, Zhuoyue
Issue Date 2016
Source Proceedings of the ACM SIGMOD International Conference on Management of Data , v. 26-June-2016, June 2016, p. 615-629
Summary Joins are expensive, and online aggregation over joins was proposed to mitigate the cost, which offers users a nice and flexible tradeoff between query efficiency and accuracy in a continuous, online fashion. However, the state-of-the-art approach, in both internal and external memory, is based on ripple join, which is still very expensive and even needs unrealistic assumptions (e.g., tuples in a table are stored in random order). This paper proposes a new approach, the wander join algorithm, to the online aggregation problem by performing random walks over the underlying join graph. We also design an optimizer that chooses the optimal plan for conducting the random walks without having to collect any statistics a priori. Compared with ripple join, wander join is particularly efficient for equality joins involving multiple tables, but also supports θ-joins. Selection predicates and group-by clauses can be handled as well. Extensive experiments using the TPC-H benchmark have demonstrated the superior performance of wander join over ripple join. In particular, we have integrated and tested wander join in the latest version of PostgreSQL, demonstrating its practicality in a full-edged database system. © 2016 ACM.
Note 2016 ACM SIGMOD International Conference on Management of Data, SIGMOD 2016; Hyatt Regency HotelSan Francisco; United States; 26 June 2016 through 1 July 2016; Code 122411
Conference 2016 ACM SIGMOD International Conference on Management of Data, SIGMOD 2016, San Francisco, CA, USA, 26 June 2016 - 01 July 2016
ISSN 0730-8078
ISBN 9781450335317
Language English
Format Conference paper
Access View full-text via DOI
View full-text via Scopus