{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:11Z","timestamp":1773481991604,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p>We present new hash tables for joins, and a hash join based on them, that consumes far less memory and is usually faster than recently published in-memory joins. Our hash join is not restricted to outer tables that fit wholly in memory. Key to this hash join is a new concise hash table (CHT), a linear probing hash table that has 100% fill factor, and uses a sparse bitmap with embedded population counts to almost entirely avoid collisions. This bitmap also serves as a Bloom filter for use in multi-table joins.<\/jats:p>\n          <jats:p>We study the random access characteristics of hash joins, and renew the case for non-partitioned hash joins. We introduce a variant of partitioned joins in which only the build is partitioned, but the probe is not, as this is more efficient for large outer tables than traditional partitioned joins. This also avoids partitioning costs during the probe, while at the same time allowing parallel build without latching overheads. Additionally, we present a variant of CHT, called a concise array table (CAT), that can be used when the key domain is moderately dense. CAT is collision-free and avoids storing join keys in the hash table.<\/jats:p>\n          <jats:p>We perform a detailed comparison of CHT and CAT against leading in-memory hash joins. Our experiments show that we can reduce the memory usage by one to three orders of magnitude, while also being competitive in performance.<\/jats:p>","DOI":"10.14778\/2735496.2735499","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"353-364","source":"Crossref","is-referenced-by-count":74,"title":["Memory-efficient hash joins"],"prefix":"10.14778","volume":"8","author":[{"given":"R.","family":"Barber","sequence":"first","affiliation":[{"name":"IBM Research, Almaden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Lohman","sequence":"additional","affiliation":[{"name":"IBM Research, Almaden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I.","family":"Pandis","sequence":"additional","affiliation":[{"name":"IBM Research, Almaden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"Raman","sequence":"additional","affiliation":[{"name":"IBM Research, Almaden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Sidle","sequence":"additional","affiliation":[{"name":"IBM Research, Almaden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Attaluri","sequence":"additional","affiliation":[{"name":"IBM Software Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Chainani","sequence":"additional","affiliation":[{"name":"IBM Software Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Lightstone","sequence":"additional","affiliation":[{"name":"IBM Software Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Sharpe","sequence":"additional","affiliation":[{"name":"IBM Software Group"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Full experimental results. http:\/\/researcher.ibm.com\/person\/us-ravijay.  Full experimental results. http:\/\/researcher.ibm.com\/person\/us-ravijay."},{"key":"e_1_2_1_2_1","unstructured":"Understanding hash joins. Microsoft TechNet SQL Server.  Understanding hash joins. Microsoft TechNet SQL Server."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367892"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336678"},{"key":"e_1_2_1_5_1","volume-title":"PVLDB","author":"Balkesen C.","year":"2014","unstructured":"C. Balkesen , G. Alonso , J. Teubner , and T. \u00d6zsu . Multi-core, main-memory joins : Sort vs. hash revisited . PVLDB , 2014 . C. Balkesen, G. Alonso, J. Teubner, and T. \u00d6zsu. Multi-core, main-memory joins: Sort vs. hash revisited. PVLDB, 2014."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544839"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213851"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989328"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272747"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602261"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687564"},{"key":"e_1_2_1_12_1","volume-title":"Application of hash to data base machine and its architecture. New Generation Computing, 1(1)","author":"Kitsuregawa M.","year":"1983","unstructured":"M. Kitsuregawa , H. Tanaka , and T. Moto-Oka . Application of hash to data base machine and its architecture. New Generation Computing, 1(1) , 1983 . M. Kitsuregawa, H. Tanaka, and T. Moto-Oka. Application of hash to data base machine and its architecture. New Generation Computing, 1(1), 1983."},{"key":"e_1_2_1_13_1","volume-title":"IMDM","author":"Lang H.","year":"2013","unstructured":"H. Lang Massively parallel NUMA-aware hash joins . In IMDM , 2013 . H. Lang et al. Massively parallel NUMA-aware hash joins. In IMDM, 2013."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610507"},{"key":"e_1_2_1_15_1","volume-title":"CIDR","author":"Li Y.","year":"2013","unstructured":"Y. Li NUMA-aware algorithms: the case of data shuffling . In CIDR , 2013 . Y. Li et al. NUMA-aware algorithms: the case of data shuffling. In CIDR, 2013."},{"key":"e_1_2_1_16_1","volume-title":"VLDB","author":"Mackert L. F.","year":"1986","unstructured":"L. F. Mackert and G. M. Lohman . R* Optimizer Validation and Performance Evaluation for Distributed Queries . In VLDB , 1986 . L. F. Mackert and G. M. Lohman. R* Optimizer Validation and Performance Evaluation for Distributed Queries. In VLDB, 1986."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780000031"},{"key":"e_1_2_1_18_1","volume-title":"VLDB","author":"Manegold S.","year":"2000","unstructured":"S. Manegold , P. A. Boncz , and M. L. Kersten . What happens during a join? Dissecting CPU and memory optimization effects . In VLDB , 2000 . S. Manegold, P. A. Boncz, and M. L. Kersten. What happens during a join? Dissecting CPU and memory optimization effects. In VLDB, 2000."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/647911.740481"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536233"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368997"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2735496.2735499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:32:04Z","timestamp":1672219924000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735496.2735499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.14778\/2735496.2735499"],"URL":"https:\/\/doi.org\/10.14778\/2735496.2735499","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}