{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T02:46:44Z","timestamp":1783738004706,"version":"3.55.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T00:00:00Z","timestamp":1682294400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T00:00:00Z","timestamp":1682294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SA 465\/51-2"],"award-info":[{"award-number":["SA 465\/51-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["PI 447\/9-2"],"award-info":[{"award-number":["PI 447\/9-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012320","name":"Otto-von-Guericke-Universit\u00e4t Magdeburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012320","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib Parallel Databases"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Using heterogeneous processing devices, like GPUs, to accelerate relational database operations is a well-known strategy. In this context, the  operation is highly interesting for two reasons. Firstly, it incurs large processing costs. Secondly, its results (i.e., aggregates) are usually small, reducing data movement costs whose compensation is a major challenge for heterogeneous computing. Generally, for  computation on GPUs, one relies either on sorting or hashing. Today, empirical results suggest that hash-based approaches are superior. However, by concept, hashing induces an unpredictable memory access pattern conflicting with the architecture of GPUs. This motivates studying why current sort-based approaches are generally inferior. Our results indicate that current sorting solutions cannot exploit the full parallel power of modern GPUs. Experimentally, we show that the issue arises from the need to synchronize parallel threads that access the shared memory location containing the aggregates via . Our quantification of the optimal performance motivates us to investigate how to minimize the overhead of atomics. This results in different variants using atomics, where the best variants almost mitigate the atomics overhead entirely. The results of a large-scale evaluation reveal that our approach achieves a 3x speed-up over existing sort-based approaches and up to 2x speed-up over hash-based approaches.<\/jats:p>","DOI":"10.1007\/s10619-023-07424-2","type":"journal-article","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T13:03:08Z","timestamp":1682341388000},"page":"387-409","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Novel insights on atomic synchronization for sort-based group-by on GPUs"],"prefix":"10.1007","volume":"41","author":[{"given":"Bala","family":"Gurumurthy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Broneske","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Sch\u00e4ler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thilo","family":"Pionteck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gunter","family":"Saake","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,4,24]]},"reference":[{"key":"7424_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s11036-013-0489-0","volume":"2","author":"M Chen","year":"2014","unstructured":"Chen, M., Mao, S., Liu, Y.: Big data: a survey. Mob. Netw. Appl. 2, 171\u2013209 (2014)","journal-title":"Mob. Netw. Appl."},{"key":"7424_CR2","doi-asserted-by":"crossref","unstructured":"Bakkum, P., Skadron, K.: Accelerating SQL database operations on a GPU with CUDA. GPGPU 94\u2013103 (2010)","DOI":"10.1145\/1735688.1735706"},{"key":"7424_CR3","doi-asserted-by":"crossref","unstructured":"Govindaraju, N.K., Lloyd, B., Wang, W., Lin, M., Manocha, D.: Fast computation of database operations using graphics processors. In: SIGMOD, pp. 215\u2013226 (2004)","DOI":"10.1145\/1007568.1007594"},{"key":"7424_CR4","unstructured":"Wu, H.: Acceleration and execution of relational queries using general purpose graphics processing unit. In: GPGPU (2015)"},{"key":"7424_CR5","doi-asserted-by":"crossref","unstructured":"Arefyeva, I., Broneske, D., Campero, G., Pinnecke, M., Saake, G.: Memory management strategies in CPU\/GPU database systems: a survey. In: BDAS, pp. 128\u2013142. Springer, New York (2018)","DOI":"10.1007\/978-3-319-99987-6_10"},{"key":"7424_CR6","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s13222-018-0294-9","volume":"18","author":"A Becher","year":"2018","unstructured":"Becher, A., Bg, L., Broneske, D., et al.: Integration of FPGAs in database management systems: challenges and opportunities. Datenbank-Spektrum 18, 145\u2013156 (2018)","journal-title":"Datenbank-Spektrum"},{"key":"7424_CR7","doi-asserted-by":"crossref","unstructured":"Bre\u00df, S., Funke, H., Teubner, J.: Robust query processing in co-processor-accelerated databases. In: SIGMOD, pp. 1891\u20131906 (2016)","DOI":"10.1145\/2882903.2882936"},{"key":"7424_CR8","doi-asserted-by":"crossref","unstructured":"Boncz, P., Neumann, T., Erling, O.: TPC-H analyzed: hidden messages and lessons learned from an influential benchmark. In: TPCTC, pp. 61\u201376 (2013)","DOI":"10.1007\/978-3-319-04936-6_5"},{"key":"7424_CR9","doi-asserted-by":"crossref","unstructured":"Gurumurthy, B., Broneske, D., Pinnecke, M., Durand, G.C., Saake, G.: SIMD vectorized hashing for grouped aggregation. In: ADBIS, pp. 113\u2013126 (2018)","DOI":"10.1007\/978-3-319-98398-1_8"},{"key":"7424_CR10","unstructured":"Behrens, T., Rosenfeld, V., Traub, J., Bre\u00df, S., Markl, V.: Efficient SIMD vectorization for hashing in OpenCL. In: EDBT, pp. 489\u2013492 (2018)"},{"issue":"4","key":"7424_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1620585.1620588","volume":"34","author":"B He","year":"2009","unstructured":"He, B., Lu, M., Yang, K., Fang, R., Govindaraju, N.K., Luo, Q., Sander, P.V.: Relational query coprocessing on graphics processors. ACM Trans. Database Syst. 34(4), 1\u201339 (2009)","journal-title":"ACM Trans. Database Syst."},{"key":"7424_CR12","unstructured":"Karnagel, T., M\u00fcller, R., Lohman, G.M.: Optimizing GPU-accelerated group-by and aggregation. In: ADMS, pp. 1\u201312 (2015)"},{"key":"7424_CR13","doi-asserted-by":"crossref","unstructured":"Gurumurthy, B., Broneske, D., Sch\u00e4ler, M., Pionteck, T., Saake, G.: An investigation of atomic synchronization for sort-based group-by aggregation on gpus. In: ICDE Workshops 2021, pp. 48\u201353. IEEE (2021)","DOI":"10.1109\/ICDEW53142.2021.00016"},{"key":"7424_CR14","doi-asserted-by":"crossref","unstructured":"Owens, J.: Gpu architecture overview. SIGGRAPH 10 (2007)","DOI":"10.1145\/1281500.1281643"},{"issue":"2","key":"7424_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-031-01759-9","volume":"13","author":"TM Aamodt","year":"2018","unstructured":"Aamodt, T.M., Fung, W.W.L., Rogers, T.G.: General-purpose graphics processor architectures. Synth. Lect. Comput. Architect. 13(2), 1\u2013140 (2018)","journal-title":"Synth. Lect. Comput. Architect."},{"key":"7424_CR16","unstructured":"Glasco, D.B., Holmqvist, P.B., Lynch, G.R., Marchand, P.R., Mehra, K., Roberts, J.: Cache-based control of atomic operations in conjunction with an external ALU block. Google Patents. US Patent 8135926 (2012)"},{"key":"7424_CR17","unstructured":"Rosenfeld, V., Heimel, M., Viebig, C., Markl, V.: The operator variant selection problem on heterogeneous hardware. In: ADMS (2015)"},{"issue":"2","key":"7424_CR18","doi-asserted-by":"publisher","first-page":"1378","DOI":"10.14778\/1687553.1687564","volume":"2","author":"C Kim","year":"2009","unstructured":"Kim, C., Kaldewey, T., Lee, V.W., Sedlar, E., Nguyen, A.D., Satish, N., Chhugani, J., Di Blas, A., Dubey, P.: Sort vs. hash revisited: fast join implementation on modern multi-core CPUs. Proc. VLDB Endow. 2(2), 1378\u20131389 (2009)","journal-title":"Proc. VLDB Endow."},{"key":"7424_CR19","doi-asserted-by":"crossref","unstructured":"Hauck, M., Paradies, M., Fr\u00f6ning, H.: Software-based buffering of associative operations on random memory addresses. In: IPDPS, pp. 943\u2013952 (2019)","DOI":"10.1109\/IPDPS.2019.00102"},{"key":"7424_CR20","doi-asserted-by":"crossref","unstructured":"Hoseini, F., Atalar, A., Tsigas, P.: Modeling the performance of atomic primitives on modern architectures. In: ICPP, pp. 1\u201311 (2019)","DOI":"10.1145\/3337821.3337901"},{"key":"7424_CR21","doi-asserted-by":"crossref","unstructured":"Tome, D.G., Gubner, T., Raasveldt, M., Rozenberg, E., Boncz, P.A.: Optimizing group-by and aggregation using GPU-CPU co-processing. In: ADMS, pp. 1\u201310 (2018)","DOI":"10.1145\/3329785.3329934"},{"issue":"10","key":"7424_CR22","doi-asserted-by":"publisher","first-page":"817","DOI":"10.14778\/2536206.2536210","volume":"6","author":"Y Yuan","year":"2013","unstructured":"Yuan, Y., Lee, R., Zhang, X.: The yin and yang of processing data warehousing queries on GPU devices. Proc. VLDB Endow. 6(10), 817\u2013828 (2013)","journal-title":"Proc. VLDB Endow."},{"issue":"12","key":"7424_CR23","doi-asserted-by":"publisher","first-page":"2999","DOI":"10.14778\/3476311.3476378","volume":"14","author":"R Lee","year":"2021","unstructured":"Lee, R., Zhou, M., Li, C., Hu, S., Teng, J., Li, D., Zhang, X.: The art of balance: a RateupDB experience of building a CPU\/GPU hybrid database product. Proc. VLDB Endow. 14(12), 2999\u20133013 (2021)","journal-title":"Proc. VLDB Endow."},{"key":"7424_CR24","doi-asserted-by":"crossref","unstructured":"Lauer, T., Datta, A., Khadikov, Z., Anselm, C.: Exploring graphics processing units as parallel coprocessors for online aggregation. In: DOLAP, pp. 77\u201384 (2010)","DOI":"10.1145\/1871940.1871958"}],"container-title":["Distributed and Parallel Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-023-07424-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10619-023-07424-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-023-07424-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T14:53:20Z","timestamp":1694703200000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10619-023-07424-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,24]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["7424"],"URL":"https:\/\/doi.org\/10.1007\/s10619-023-07424-2","relation":{},"ISSN":["0926-8782","1573-7578"],"issn-type":[{"value":"0926-8782","type":"print"},{"value":"1573-7578","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,24]]},"assertion":[{"value":"10 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}