{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:15:39Z","timestamp":1779174939880,"version":"3.51.4"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T00:00:00Z","timestamp":1494547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2017,5,12]]},"abstract":"<jats:p>Joins are expensive, and online aggregation is an effective approach to explore the tradeoff between query efficiency and accuracy in a continuous, online fashion. However, the stateof- the-art approach, in both internal and external memory, is based on ripple join, which is still very expensive and needs strong assumptions (e.g., the 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. Selection predicates and group-by clauses can be handled as well. We have developed an online engine called XDB by integrating wander join in the latest version of PostgreSQL. Extensive experiments using the TPC-H benchmark have shown the superior performance of wander join. The XDB implementation has demonstrated its practicality in a full-fledged database system.<\/jats:p>","DOI":"10.1145\/3093754.3093763","type":"journal-article","created":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T12:13:58Z","timestamp":1494850438000},"page":"33-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Wander Join and XDB"],"prefix":"10.1145","volume":"46","author":[{"given":"Feifei","family":"Li","sequence":"first","affiliation":[{"name":"University of Utah"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Wu","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhuoyue","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of Utah"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Statistical Inference","author":"Casella G.","year":"2001","unstructured":"G. Casella and R. L. Berger . Statistical Inference . Duxbury Press , 2001 . G. Casella and R. L. Berger. Statistical Inference. Duxbury Press, 2001."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687675"},{"key":"e_1_2_1_3_1","first-page":"401","volume-title":"NSDI","author":"Dragojevic A.","year":"2014","unstructured":"A. Dragojevic , D. Narayanan , M. Castro , and O. Hodson . FaRM: Fast remote memory . In NSDI , pages 401 -- 414 , 2014 . A. Dragojevic, D. Narayanan, M. Castro, and O. Hodson. FaRM: Fast remote memory. In NSDI, pages 401--414, 2014."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1997.621151"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1952.10483446"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247560"},{"key":"e_1_2_1_10_1","volume-title":"Article 23","author":"Jermaine C.","year":"2008","unstructured":"C. Jermaine , S. Arumugam , A. Pol , and A. Dobra . Scalable approximate query processing with the DBO engine. ACM TODS, 33(4) , Article 23 , 2008 . C. Jermaine, S. Arumugam, A. Pol, and A. Dobra. Scalable approximate query processing with the DBO engine. ACM TODS, 33(4), Article 23, 2008."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298540"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.93611"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1965724.1965751"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093754.3093763","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3093754.3093763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:16Z","timestamp":1750217416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3093754.3093763"}},"subtitle":["Online Aggregation via Random Walks"],"short-title":[],"issued":{"date-parts":[[2017,5,12]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,5,12]]}},"alternative-id":["10.1145\/3093754.3093763"],"URL":"https:\/\/doi.org\/10.1145\/3093754.3093763","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2017,5,12]]},"assertion":[{"value":"2017-05-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}