{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:11:27Z","timestamp":1750306287451,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,10,23]],"date-time":"2015-10-23T00:00:00Z","timestamp":1445558400000},"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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2015,10,23]]},"abstract":"<jats:p>\n            Antijoin cardinality estimation is among a handful of problems that has eluded accurate efficient solutions amenable to implementation in relational query optimizers. Given the widespread use of antijoin and subset-based queries in analytical workloads and the extensive research targeted at join cardinality estimation\u2014a seemingly related problem\u2014the lack of adequate solutions for antijoin cardinality estimation is intriguing. In this article, we introduce a novel\n            <jats:italic>sampling-based estimator<\/jats:italic>\n            for antijoin cardinality that (unlike existent estimators) provides sufficient accuracy and efficiency to be implemented in a query optimizer. The proposed estimator incorporates three novel ideas. First, we use prior workload information when learning a\n            <jats:italic>mixture superpopulation model<\/jats:italic>\n            of the data offline. Second, we design a\n            <jats:italic>Bayesian statistics framework<\/jats:italic>\n            that updates the superpopulation model according to the live queries, thus allowing the estimator to adapt dynamically to the online workload. Third, we develop an efficient algorithm for sampling from a hypergeometric distribution in order to generate\n            <jats:italic>Monte Carlo trials<\/jats:italic>\n            , without explicitly instantiating either the population or the sample. When put together, these ideas form the basis of an efficient antijoin cardinality estimator satisfying the strict requirements of a query optimizer, as shown by the extensive experimental results over synthetically-generated as well as massive TPC-H data.\n          <\/jats:p>","DOI":"10.1145\/2818178","type":"journal-article","created":{"date-parts":[[2015,10,24]],"date-time":"2015-10-24T18:27:12Z","timestamp":1445711232000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Workload-Driven Antijoin Cardinality Estimation"],"prefix":"10.1145","volume":"40","author":[{"given":"Florin","family":"Rusu","sequence":"first","affiliation":[{"name":"University of California, Merced, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zixuan","family":"Zhuang","sequence":"additional","affiliation":[{"name":"University of California, Merced, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingxi","family":"Wu","sequence":"additional","affiliation":[{"name":"GraphSQL, Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chris","family":"Jermaine","sequence":"additional","affiliation":[{"name":"Rice University, Houston, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,10,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304198"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593667"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066171"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v032.i06"},{"key":"e_1_2_1_6_1","unstructured":"J.A. Bilmes. 1998. A Gentle Tutorial of the EM algorithm and its application to parameter estimation for gaussian mixture and hidden markov models. ftp:\/\/ftp.icsi.berkeley.edu\/pub\/techreports\/1997\/tr-97-021.pdf. (Last accessed September 2014.)  J.A. Bilmes. 1998. A Gentle Tutorial of the EM algorithm and its application to parameter estimation for gaussian mixture and hidden markov models. ftp:\/\/ftp.icsi.berkeley.edu\/pub\/techreports\/1997\/tr-97-021.pdf. (Last accessed September 2014.)"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375686"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275492"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_10_1","unstructured":"M. Colgan. 2010. Optimizer transformations: Subquery unesting Part 2. https:\/\/blogs.oracle.com\/optimizer\/entry\/optimizer_transformations_subquery_unesting_part_2. (Last accessed September 2014.)  M. Colgan. 2010. Optimizer transformations: Subquery unesting Part 2. https:\/\/blogs.oracle.com\/optimizer\/entry\/optimizer_transformations_subquery_unesting_part_2. (Last accessed September 2014.)"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"A. P. Dempster N. M. Laird and D. B. Rubin. 1977. Maximum-likelihood from incomplete data via the EM algorithm. J. Royal Statist. 39 (1977).  A. P. Dempster N. M. Laird and D. B. Rubin. 1977. Maximum-likelihood from incomplete data via the EM algorithm. J. Royal Statist. 39 (1977).","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687675"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233340"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"A. Gelman J. B. Carlin H. S. Stern and D. B. Rubin. 2003. Bayesian data analysis. Chapman & Hall\/CRC.  A. Gelman J. B. Carlin H. S. Stern and D. B. Rubin. 2003. Bayesian data analysis. Chapman & Hall\/CRC.","DOI":"10.1201\/9780429258480"},{"volume-title":"Proceedings of the VLDB International Conference on Very Large Data Bases. 541--550","year":"2001","author":"Gibbons P.B.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","first-page":"19","article-title":"The cascades framework for query optimization","volume":"18","author":"Graefe G.","year":"1995","journal-title":"IEEE Data Eng. Bulle."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.v1:4"},{"volume-title":"Proceedings of the VLDB International Conference on Very Large Data Bases. 311--322","author":"Haas P.J.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130335"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/234313.234367"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315455"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/169725.169708"},{"volume-title":"Proceedings of the VLDB International Conference on Very Large Data Bases. 745--756","author":"Jermaine C.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","unstructured":"N.L. Johnson S. Kotz and N. Balakrishnan. 1996. Discrete Multivariate Distributions. John Wiley & Sons Inc.  N.L. Johnson S. Kotz and N. Balakrishnan. 1996. Discrete Multivariate Distributions. John Wiley & Sons Inc."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0095-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276315"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114251"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687723"},{"key":"e_1_2_1_30_1","unstructured":"G.M. Lohman. 2014. Is query optimization a \u201csolved\u201d problem? http:\/\/wp.sigmod.org\/?p=1075. (Last accessed May 2014.)  G.M. Lohman. 2014. Is query optimization a \u201csolved\u201d problem? http:\/\/wp.sigmod.org\/?p=1075. (Last accessed May 2014.)"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.421.0098"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007642"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_34_1","unstructured":"K.P. Murphy. 2006. Binomial and multinomial distributions. http:\/\/www.cs.ubc.ca\/&sim;murphyk\/Teaching\/CSE40-Fall06\/reading\/bernoulli.pdf. (Last accessed September 2014.)  K.P. Murphy. 2006. Binomial and multinomial distributions. http:\/\/www.cs.ubc.ca\/&sim;murphyk\/Teaching\/CSE40-Fall06\/reading\/bernoulli.pdf. (Last accessed September 2014.)"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066224"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233342"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"C.P. Robert and G. Casella. 2005. Monte Carlo Statistical Methods. Springer.   C.P. Robert and G. Casella. 2005. Monte Carlo Statistical Methods. Springer.","DOI":"10.1007\/978-1-4757-4145-2"},{"key":"e_1_2_1_38_1","unstructured":"R. Schrag. 2005. Speeding up queries with semi-joins and anti-joins: How Oracle evaluates EXISTS NOT EXISTS IN and NOT IN. http:\/\/www.dbspecialists.com\/files\/presentations\/semijoins.html. (Last accessed September 2014.)  R. Schrag. 2005. Speeding up queries with semi-joins and anti-joins: How Oracle evaluates EXISTS NOT EXISTS IN and NOT IN. http:\/\/www.dbspecialists.com\/files\/presentations\/semijoins.html. (Last accessed September 2014.)"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1508857.1508860"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.84"},{"volume-title":"Proceedings of the VLDB International Conference on Very Large Data Bases. 19--28","author":"Stillger M.","key":"e_1_2_1_42_1"},{"volume-title":"Proceedings of the EDBT Extended Database Technology Conference. 287--300","author":"Swami A.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463701"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588579"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818178","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:01Z","timestamp":1750221541000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,23]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,10,23]]}},"alternative-id":["10.1145\/2818178"],"URL":"https:\/\/doi.org\/10.1145\/2818178","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2015,10,23]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}