{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T05:01:11Z","timestamp":1768453271858,"version":"3.49.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,12,9]]},"abstract":"<jats:p>\n            Despite decades of research on AQP (approximate query processing), our understanding of sample-based joins has remained limited and, to some extent, even superficial. The common belief in the community is that joining random samples is futile. This belief is largely based on an early result showing that the join of two\n            <jats:italic>uniform<\/jats:italic>\n            samples is not an independent sample of the original join, and that it leads to quadratically fewer output tuples. Unfortunately, this early result has little applicability to the key questions practitioners face. For example, the success metric is often the final approximation's accuracy, rather than output cardinality. Moreover, there are many non-uniform sampling strategies that one can employ. Is sampling for joins still futile in all of these settings? If not, what is the best sampling strategy in each case? To the best of our knowledge, there is no formal study answering these questions.\n          <\/jats:p>\n          <jats:p>This paper aims to improve our understanding of sample-based joins and offer a guideline for practitioners building and using real-world AQP systems. We study limitations of offline samples in approximating join queries: given an offline sampling budget, how well can one approximate the join of two tables? We answer this question for two success metrics: output size and estimator variance. We show that maximizing output size is easy, while there is an information-theoretical lower bound on the lowest variance achievable by any sampling strategy. We then define a hybrid sampling scheme that captures all combinations of stratified, universe, and Bernoulli sampling, and show that this scheme with our optimal parameters achieves the theoretical lower bound within a constant factor. Since computing these optimal parameters requires shuffling statistics across the network, we also propose a decentralized variant in which each node acts autonomously using minimal statistics. We also empirically validate our findings on popular SQL and AQP engines.<\/jats:p>","DOI":"10.14778\/3372716.3372726","type":"journal-article","created":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T20:19:37Z","timestamp":1578341977000},"page":"547-560","source":"Crossref","is-referenced-by-count":10,"title":["Joins on samples"],"prefix":"10.14778","volume":"13","author":[{"given":"Dawei","family":"Huang","sequence":"first","affiliation":[{"name":"University of Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dong Young","family":"Yoon","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barzan","family":"Mozafari","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,1,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"The instacart online grocery shopping dataset 2017. https:\/\/www.instacart.com\/datasets\/grocery-shopping-2017. Accessed: 2019-07-20.  The instacart online grocery shopping dataset 2017. https:\/\/www.instacart.com\/datasets\/grocery-shopping-2017. Accessed: 2019-07-20."},{"key":"e_1_2_1_2_1","unstructured":"Security on-demand announces acquisition of Infobright analytics & technology assets. https:\/\/tinyurl.com\/y6ctn4vs.  Security on-demand announces acquisition of Infobright analytics & technology assets. https:\/\/tinyurl.com\/y6ctn4vs."},{"key":"e_1_2_1_3_1","unstructured":"TPC-H Benchmark. http:\/\/www.tpc.org\/tpch\/.  TPC-H Benchmark. http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_4_1","volume-title":"https:\/\/www.cloudlab.us","year":"2019","unstructured":"Cloudlab. https:\/\/www.cloudlab.us , 2019 . Cloudlab. https:\/\/www.cloudlab.us, 2019."},{"key":"e_1_2_1_5_1","volume-title":"VLDB","author":"Acharya S.","year":"1999","unstructured":"S. Acharya , P. B. Gibbons , and V. Poosala . Aqua: A fast decision support system using approximate query answers . In VLDB , 1999 . S. Acharya, P. B. Gibbons, and V. Poosala. Aqua: A fast decision support system using approximate query answers. In VLDB, 1999."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593667"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_9_1","volume-title":"PVLDB","author":"Agarwal Sameer","year":"2012","unstructured":"Sameer Agarwal , Aurojit Panda , Barzan Mozafari , Anand P. Iyer , Samuel Madden, and Ion Stoica. Blink and it's done: Interactive queries on very large data . PVLDB , 2012 . Sameer Agarwal, Aurojit Panda, Barzan Mozafari, Anand P. Iyer, Samuel Madden, and Ion Stoica. Blink and it's done: Interactive queries on very large data. PVLDB, 2012."},{"key":"e_1_2_1_10_1","first-page":"64","author":"Alon Noga","year":"2002","unstructured":"Noga Alon , Phillip B Gibbons , Yossi Matias , and Mario Szegedy . Tracking join and self-join sizes in limited storage. Journal of Computer and System Sciences , 64 , 2002 . Noga Alon, Phillip B Gibbons, Yossi Matias, and Mario Szegedy. Tracking join and self-join sizes in limited storage. Journal of Computer and System Sciences, 64, 2002.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_2_1_11_1","first-page":"58","author":"Alon Noga","year":"1999","unstructured":"Noga Alon , Yossi Matias , and Mario Szegedy . The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. , 58 , 1999 . Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58, 1999.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872822"},{"key":"e_1_2_1_14_1","volume-title":"Boyd and Lieven Vandenberghe. Convex Optimization","author":"Stephen","year":"2014","unstructured":"Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization . Cambridge University Press , 2014 . Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2014."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242526"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007602"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035921"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085514"},{"key":"e_1_2_1_20_1","volume-title":"NSDI","author":"Condie Tyson","year":"2010","unstructured":"Tyson Condie , Neil Conway , Peter Alvaro , Joseph M. Hellerstein , Khaled Elmeleegy , and Russell Sears . Mapreduce online . In NSDI , 2010 . Tyson Condie, Neil Conway, Peter Alvaro, Joseph M. Hellerstein, Khaled Elmeleegy, and Russell Sears. Mapreduce online. In NSDI, 2010."},{"key":"e_1_2_1_21_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","year":"2009","unstructured":"Thomas H Cormen , Charles E Leiserson , Ronald L Rivest , and Clifford Stein . Introduction to algorithms . MIT press , 2009 . Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009."},{"key":"e_1_2_1_22_1","first-page":"4","author":"Cormode Graham","year":"2012","unstructured":"Graham Cormode , Minos Garofalakis , Peter J Haas , and Chris Jermaine . Synopses for massive data: Samples , histograms, wavelets, sketches. Foundations and Trends in Databases , 4 , 2012 . Graham Cormode, Minos Garofalakis, Peter J Haas, and Chris Jermaine. Synopses for massive data: Samples, histograms, wavelets, sketches. Foundations and Trends in Databases, 4, 2012.","journal-title":"Foundations and Trends in Databases"},{"key":"e_1_2_1_23_1","volume-title":"PVLDB","author":"Crotty Andrew","year":"2015","unstructured":"Andrew Crotty , Alex Galakatos , Emanuel Zgraggen , Carsten Binnig , and Tim Kraska . Vizdom : Interactive analytics through pen and touch . PVLDB , 2015 . Andrew Crotty, Alex Galakatos, Emanuel Zgraggen, Carsten Binnig, and Tim Kraska. Vizdom: Interactive analytics through pen and touch. PVLDB, 2015."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564699"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687675"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.61"},{"key":"e_1_2_1_27_1","volume-title":"VLDB","author":"Ganti Venkatesh","year":"2000","unstructured":"Venkatesh Ganti , Mong-Li Lee , and Raghu Ramakrishnan . Icicles : Self-tuning samples for approximate query answering . In VLDB , 2000 . Venkatesh Ganti, Mong-Li Lee, and Raghu Ramakrishnan. Icicles: Self-tuning samples for approximate query answering. In VLDB, 2000."},{"key":"e_1_2_1_28_1","unstructured":"Deepak Goyal. Approximate query processing at WalmartLabs. https:\/\/fifthelephant.talkfunnel.com\/2018\/43-approximate-query-processing.  Deepak Goyal. Approximate query processing at WalmartLabs. https:\/\/fifthelephant.talkfunnel.com\/2018\/43-approximate-query-processing."},{"key":"e_1_2_1_29_1","first-page":"287","volume-title":"Hellerstein. Ripple Joins for Online Aggregation. In SIGMOD","author":"Peter","year":"1999","unstructured":"Peter J. Haas and Joseph M . Hellerstein. Ripple Joins for Online Aggregation. In SIGMOD , pages 287 -- 298 , 1999 . Peter J. Haas and Joseph M. Hellerstein. Ripple Joins for Online Aggregation. In SIGMOD, pages 287--298, 1999."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007601"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453883"},{"key":"e_1_2_1_32_1","volume-title":"TIIS","author":"Maxwell Harper F","year":"2016","unstructured":"F Maxwell Harper and Joseph A Konstan . The movielens datasets: History and context . TIIS , 2016 . F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. TIIS, 2016."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_34_1","first-page":"47","author":"Horvitz Daniel G","year":"1952","unstructured":"Daniel G Horvitz and Donovan J Thompson . A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association , 47 , 1952 . Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47, 1952.","journal-title":"Association"},{"key":"e_1_2_1_35_1","volume-title":"Seth Pettie, and Barzan Mozafari. Joins on samples: A theoretical guide for practitioners. https:\/\/arxiv.org\/abs\/1912.03443","author":"Huang Dawei","year":"2019","unstructured":"Dawei Huang , Dong Young Yoon , Seth Pettie, and Barzan Mozafari. Joins on samples: A theoretical guide for practitioners. https:\/\/arxiv.org\/abs\/1912.03443 , 2019 . Dawei Huang, Dong Young Yoon, Seth Pettie, and Barzan Mozafari. Joins on samples: A theoretical guide for practitioners. https:\/\/arxiv.org\/abs\/1912.03443, 2019."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066222"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882940"},{"key":"e_1_2_1_38_1","volume-title":"Learned cardinalities: Estimating correlated joins with deep learning. arXiv:1809.00677","author":"Kipf Andreas","year":"2018","unstructured":"Andreas Kipf , Thomas Kipf , Bernhard Radke , Viktor Leis , Peter Boncz , and Alfons Kemper . Learned cardinalities: Estimating correlated joins with deep learning. arXiv:1809.00677 , 2018 . Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. Learned cardinalities: Estimating correlated joins with deep learning. arXiv:1809.00677, 2018."},{"key":"e_1_2_1_39_1","volume-title":"CIDR","author":"Leis Viktor","year":"2017","unstructured":"Viktor Leis , Bernhard Radke , Andrey Gubichev , Alfons Kemper , and Thomas Neumann . Cardinality estimation done right: Index-based join sampling . In CIDR , 2017 . Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper, and Thomas Neumann. Cardinality estimation done right: Index-based join sampling. In CIDR, 2017."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284551"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564721"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056098"},{"key":"e_1_2_1_44_1","volume-title":"SIGMOD","author":"Mozafari Barzan","year":"2015","unstructured":"Barzan Mozafari , Eugene Zhen Ye Goh , and Dong Young Yoon . CliffGuard : A principled framework for finding robust database designs . In SIGMOD , 2015 . Barzan Mozafari, Eugene Zhen Ye Goh, and Dong Young Yoon. CliffGuard: A principled framework for finding robust database designs. In SIGMOD, 2015."},{"key":"e_1_2_1_45_1","volume-title":"A handbook for building an approximate query engine","author":"Mozafari Barzan","year":"2015","unstructured":"Barzan Mozafari and Ning Niu . A handbook for building an approximate query engine . IEEE Data Eng. Bull ., 2015 . Barzan Mozafari and Ning Niu. A handbook for building an approximate query engine. IEEE Data Eng. Bull., 2015."},{"key":"e_1_2_1_46_1","volume-title":"CIDR","author":"Mozafari Barzan","year":"2017","unstructured":"Barzan Mozafari , Jags Ramnarayan , Sudhir Menon , Yogesh Mahajan , Soubhik Chakraborty , Hemant Bhanawat , and Kishor Bachhav. SnappyData : A unified cluster for streaming, transactions, and interactive analytics . In CIDR , 2017 . Barzan Mozafari, Jags Ramnarayan, Sudhir Menon, Yogesh Mahajan, Soubhik Chakraborty, Hemant Bhanawat, and Kishor Bachhav. SnappyData: A unified cluster for streaming, transactions, and interactive analytics. In CIDR, 2017."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594554"},{"key":"e_1_2_1_48_1","first-page":"4","author":"Pansare Niketan","year":"2011","unstructured":"Niketan Pansare , Vinayak R. Borkar , Chris Jermaine , and Tyson Condie . Online aggregation for large mapreduce jobs. PVLDB , 4 , 2011 . Niketan Pansare, Vinayak R. Borkar, Chris Jermaine, and Tyson Condie. Online aggregation for large mapreduce jobs. PVLDB, 4, 2011.","journal-title":"PVLDB"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498287"},{"key":"e_1_2_1_50_1","volume-title":"SIGMOD","author":"Park Yongjoo","year":"2018","unstructured":"Yongjoo Park , Barzan Mozafari , Joseph Sorenson , and Junhao Wang . VerdictDB : universalizing approximate query processing . In SIGMOD , 2018 . Yongjoo Park, Barzan Mozafari, Joseph Sorenson, and Junhao Wang. VerdictDB: universalizing approximate query processing. In SIGMOD, 2018."},{"key":"e_1_2_1_51_1","volume-title":"SIGMOD","author":"Park Yongjoo","year":"2017","unstructured":"Yongjoo Park , Ahmad Shahab Tajik , Michael Cafarella , and Barzan Mozafari . Database Learning : Towards a database that becomes smarter every time . In SIGMOD , 2017 . Yongjoo Park, Ahmad Shahab Tajik, Michael Cafarella, and Barzan Mozafari. Database Learning: Towards a database that becomes smarter every time. In SIGMOD, 2017."},{"key":"e_1_2_1_52_1","volume-title":"QuickSel: Quick selectivity learning with mixture models. CoRR, abs\/1812.10568","author":"Park Yongjoo","year":"2018","unstructured":"Yongjoo Park , Shucheng Zhong , and Barzan Mozafari . QuickSel: Quick selectivity learning with mixture models. CoRR, abs\/1812.10568 , 2018 . Yongjoo Park, Shucheng Zhong, and Barzan Mozafari. QuickSel: Quick selectivity learning with mixture models. CoRR, abs\/1812.10568, 2018."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497485"},{"key":"e_1_2_1_54_1","volume-title":"Distributed and Parallel Databases","author":"Qin Chengjie","year":"2013","unstructured":"Chengjie Qin and Florin Rusu . Pf-ola : a high-performance framework for parallel online aggregation . Distributed and Parallel Databases , 2013 . Chengjie Qin and Florin Rusu. Pf-ola: a high-performance framework for parallel online aggregation. Distributed and Parallel Databases, 2013."},{"key":"e_1_2_1_55_1","volume-title":"PVLDB","author":"Rahman Sajjadur","year":"2017","unstructured":"Sajjadur Rahman , Maryam Aliakbarpour , Hidy Kong , Eric Blais , Karrie Karahalios , Aditya G. Parameswaran , and Ronitt Rubinfeld . I've seen \"enough\" : Incrementally improving visualizations to support rapid decision making . PVLDB , 2017 . Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya G. Parameswaran, and Ronitt Rubinfeld. I've seen \"enough\": Incrementally improving visualizations to support rapid decision making. PVLDB, 2017."},{"key":"e_1_2_1_56_1","volume-title":"Approximate aggregates in oracle 12c","author":"Su Hong","year":"2016","unstructured":"Hong Su , Mohamed Zait , Vladimir Barri\u00e8re , Joseph Torres , and Andre Menck . Approximate aggregates in oracle 12c , 2016 . Hong Su, Mohamed Zait, Vladimir Barri\u00e8re, Joseph Torres, and Andre Menck. Approximate aggregates in oracle 12c, 2016."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57818-8_58"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807238"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882914"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196890"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588579"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3372716.3372726","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:00:28Z","timestamp":1672221628000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3372716.3372726"}},"subtitle":["a theoretical guide for practitioners"],"short-title":[],"issued":{"date-parts":[[2019,12,9]]},"references-count":63,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,9]]}},"alternative-id":["10.14778\/3372716.3372726"],"URL":"https:\/\/doi.org\/10.14778\/3372716.3372726","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,12,9]]}}}