{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T08:56:21Z","timestamp":1773392181968,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,2]]},"abstract":"<jats:p>Scalable join processing in a parallel shared-nothing environment requires a partitioning policy that evenly distributes the processing load while minimizing the size of state maintained and number of messages communicated. Previous research proposes static partitioning schemes that require statistics beforehand. In an online or streaming environment in which no statistics about the workload are known, traditional static approaches perform poorly.<\/jats:p>\n          <jats:p>This paper presents a novel parallel online dataflow join operator that supports arbitrary join predicates. The proposed operator continuously adjusts itself to the data dynamics through adaptive dataflow routing and state repartitioning. The operator is resilient to data skew, maintains high throughput rates, avoids blocking behavior during state repartitioning, takes an eventual consistency approach for maintaining its local state, and behaves strongly consistently as a black-box dataflow operator. We prove that the operator ensures a constant competitive ratio 3:75 in data distribution optimality and that the cost of processing an input tuple is amortized constant, taking into account adaptivity costs. Our evaluation demonstrates that our operator outperforms the state-of-the-art static partitioning schemes in resource utilization, throughput, and execution time.<\/jats:p>","DOI":"10.14778\/2732279.2732281","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"441-452","source":"Crossref","is-referenced-by-count":62,"title":["Scalable and adaptive online joins"],"prefix":"10.14778","volume":"7","author":[{"given":"Mohammed","family":"Elseidy","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdallah","family":"Elguindy","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksandar","family":"Vitorovic","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,2]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"The TPC-H benchmark. http:\/\/www.tpc.org\/tpch\/.  The TPC-H benchmark. http:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_2_1","first-page":"277","volume-title":"CIDR","author":"Abadi D.","year":"2005","unstructured":"D. Abadi , Y. Ahmad , M. Balazinska , U. \u00c7etintemel , M. Cherniack , J. Hwang , W. Lindner , A. Maskey , A. Rasin , E. Ryvkina , N. Tatbul , Y. Xing , and S. Zdonik . The design of the Borealis stream processing engine . In CIDR , pages 277 -- 289 , 2005 . D. Abadi, Y. Ahmad, M. Balazinska, U. \u00c7etintemel, M. Cherniack, J. Hwang, W. Lindner, A. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. Zdonik. The design of the Borealis stream processing engine. In CIDR, pages 277--289, 2005."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739056"},{"key":"e_1_2_1_4_1","volume-title":"Stanford InfoLab","author":"Arasu A.","year":"2004","unstructured":"A. Arasu , B. Babcock , S. Babu , J. Cieslewicz , M. Datar , K. Ito , R. Motwani , U. Srivastava , and J. Widom . STREAM: The Stanford data stream management system. Technical report , Stanford InfoLab , 2004 . A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, M. Datar, K. Ito, R. Motwani, U. Srivastava, and J. Widom. STREAM: The Stanford data stream management system. Technical report, Stanford InfoLab, 2004."},{"key":"e_1_2_1_5_1","first-page":"480","volume-title":"VLDB","author":"Arasu A.","year":"2004","unstructured":"A. Arasu , M. Cherniack , E. Galvez , D. Maier , A. Maskey , E. Ryvkina , M. Stonebraker , R. Tibbetts . Linear road: a stream data management benchmark . In VLDB , pages 480 -- 491 , 2004 . A. Arasu, M. Cherniack, E. Galvez, D. Maier, A. Maskey, E. Ryvkina, M. Stonebraker, R. Tibbetts. Linear road: a stream data management benchmark. In VLDB, pages 480--491, 2004."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335420"},{"key":"e_1_2_1_7_1","first-page":"238","volume-title":"CIDR","author":"Babu S.","year":"2005","unstructured":"S. Babu and P. Bizarro . Adaptive query processing in the looking glass . In CIDR , pages 238 -- 249 , 2005 . S. Babu and P. Bizarro. Adaptive query processing in the looking glass. In CIDR, pages 238--249, 2005."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807273"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465282"},{"key":"e_1_2_1_10_1","unstructured":"S. Chaudhuri and V. Narasayya. TPC-D data generation with skew.  S. Chaudhuri and V. Narasayya. TPC-D data generation with skew."},{"key":"e_1_2_1_11_1","first-page":"10","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . MapReduce: simplified data processing on large clusters . In OSDI , pages 10 -- 10 , 2004 . J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. In OSDI, pages 10--10, 2004."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316771"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000001"},{"key":"e_1_2_1_14_1","first-page":"299","volume-title":"VLDB","author":"Dittrich J.","year":"2002","unstructured":"J. Dittrich , B. Seeger , D. Taylor , and P. Widmayer . Progressive merge join: a generic and non-blocking sort-based join algorithm . In VLDB , pages 299 -- 310 , 2002 . J. Dittrich, B. Seeger, D. Taylor, and P. Widmayer. Progressive merge join: a generic and non-blocking sort-based join algorithm. In VLDB, pages 299--310, 2002."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646104.681201"},{"issue":"1","key":"e_1_2_1_17_1","first-page":"211","article-title":"Adaptive query processing in distributed settings","volume":"36","author":"Gounaris A.","year":"2012","unstructured":"A. Gounaris , E. Tsamoura , and Y. Manolopoulos . Adaptive query processing in distributed settings . Advanced Query Processing , 36 ( 1 ): 211 -- 236 , 2012 . A. Gounaris, E. Tsamoura, and Y. Manolopoulos. Adaptive query processing in distributed settings. Advanced Query Processing, 36(1):211--236, 2012.","journal-title":"Advanced Query Processing"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367860"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_1_21_1","volume-title":"Adaptive query processing: Technology in evolution","author":"Hellerstein J.","year":"2000","unstructured":"J. Hellerstein , M. Franklin , S. Chandrasekaran , A. Deshpande , K. Hildrum , S. Madden , V. Raman , and M. Shah . Adaptive query processing: Technology in evolution . IEEE Data Engineering Bulletin , 23(2), 2000 . J. Hellerstein, M. Franklin, S. Chandrasekaran, A. Deshpande, K. Hildrum, S. Madden, V. Raman, and M. Shah. Adaptive query processing: Technology in evolution. IEEE Data Engineering Bulletin, 23(2), 2000."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/115790.115835"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2007.4401048"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978115"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989423"},{"key":"e_1_2_1_27_1","first-page":"43","volume-title":"Berkeley DB. In Annual Technical Conference, USENIX","author":"Olson M.","year":"1999","unstructured":"M. Olson , K. Bostic , and M. Seltzer . Berkeley DB. In Annual Technical Conference, USENIX , pages 43 -- 43 , 1999 . M. Olson, K. Bostic, and M. Seltzer. Berkeley DB. In Annual Technical Conference, USENIX, pages 43--43, 1999."},{"key":"e_1_2_1_28_1","first-page":"267","volume-title":"Annual Technical Conference, USENIX","author":"Olston C.","year":"2008","unstructured":"C. Olston , B. Reed , A. Silberstein , and U. Srivastava . Automatic optimization of parallel dataflow programs . In Annual Technical Conference, USENIX , pages 267 -- 273 , 2008 . C. Olston, B. Reed, A. Silberstein, and U. Srivastava. Automatic optimization of parallel dataflow programs. In Annual Technical Conference, USENIX, pages 267--273, 2008."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0090-x"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66937"},{"key":"e_1_2_1_31_1","first-page":"25","volume-title":"ICDE","author":"Shah M.","year":"2002","unstructured":"M. Shah , J. Hellerstein , S. Chandrasekaran , and M. Franklin . Flux: An adaptive partitioning operator for continuous query systems . In ICDE , pages 25 -- 36 , 2002 . M. Shah, J. Hellerstein, S. Chandrasekaran, and M. Franklin. Flux: An adaptive partitioning operator for continuous query systems. In ICDE, pages 25--36, 2002."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.250116"},{"key":"e_1_2_1_33_1","first-page":"19","volume-title":"VLDB","author":"Stillger M.","year":"2001","unstructured":"M. Stillger , G. Lohman , V. Markl , and M. Kandil . LEO - DB2's learning optimizer . In VLDB , pages 19 -- 28 , 2001 . M. Stillger, G. Lohman, V. Markl, and M. Kandil. LEO - DB2's learning optimizer. In VLDB, pages 19--28, 2001."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066200"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315481"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989350"},{"issue":"2","key":"e_1_2_1_37_1","first-page":"27","article-title":"XJoin: A reactively-scheduled pipelined join operator","volume":"23","author":"Urhan T.","year":"2000","unstructured":"T. Urhan and M. Franklin . XJoin: A reactively-scheduled pipelined join operator . IEEE Data Engineering Bulletin , 23 ( 2 ): 27 -- 33 , 2000 . T. Urhan and M. Franklin. XJoin: A reactively-scheduled pipelined join operator. IEEE Data Engineering Bulletin, 23(2):27--33, 2000.","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516396"},{"key":"e_1_2_1_39_1","first-page":"68","volume-title":"Parallel and Distributed Information Systems","author":"Wilschut A.","year":"1991","unstructured":"A. Wilschut and P. Apers . Dataflow query execution in a parallel main-memory environment . In Parallel and Distributed Information Systems , pages 68 -- 77 , 1991 . A. Wilschut and P. Apers. Dataflow query execution in a parallel main-memory environment. In Parallel and Distributed Information Systems, pages 68--77, 1991."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.53"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247602"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350238"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.54"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732279.2732281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:09:30Z","timestamp":1672225770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732279.2732281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.14778\/2732279.2732281"],"URL":"https:\/\/doi.org\/10.14778\/2732279.2732281","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,2]]}}}