Wander Join
Authors:
Open Access
- 14 June 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 615-629
Abstract
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-fledged database system.Keywords
Funding Information
- NSFC (61428204)
- HKRGC (GRF-621413 GRF-16211614 and GRF-16200415)
- NSF (1251019 1302663 and 1443046)
This publication has 53 references indexed in Scilit:
- Scalable approximate query processing with the DBO engineACM Transactions on Database Systems, 2008
- Confidence bounds for sampling-based group by estimatesACM Transactions on Database Systems, 2008
- Sampling-based estimators for subset-based queriesThe VLDB Journal, 2008
- Ripple joins for online aggregationACM SIGMOD Record, 1999
- On random sampling over joinsACM SIGMOD Record, 1999
- Random sampling for histogram constructionACM SIGMOD Record, 1998
- New sampling-based summary statistics for improving approximate query answersACM SIGMOD Record, 1998
- Online aggregationACM SIGMOD Record, 1997
- Practical selectivity estimation through adaptive samplingACM SIGMOD Record, 1990
- A Generalization of Sampling Without Replacement from a Finite UniverseJournal of the American Statistical Association, 1952