{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:23:38Z","timestamp":1746264218044,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T00:00:00Z","timestamp":1670371200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T00:00:00Z","timestamp":1670371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002957","name":"Technische Universit\u00e4t Dresden","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002957","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Datenbank Spektrum"],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Single Instruction Multiple Data (SIMD) paradigm became a\u00a0core principle for optimizing query processing in columnar database systems. Until now, only the  instructions are considered to be efficient enough to achieve the expected speedups, while avoiding  is considered almost imperative. However, the  instruction offers a\u00a0very flexible way to populate SIMD registers with data elements coming from non-consecutive memory locations. As we will discuss within this article, the  instruction can achieve the same performance as the  instruction, if applied properly. To enable the proper usage, we outline a\u00a0novel access pattern allowing fine-grained, partition-based SIMD implementations. Then, we apply this partition-based SIMD processing to two representative examples from columnar database systems to experimentally demonstrate the applicability and efficiency of our new access pattern.<\/jats:p>","DOI":"10.1007\/s13222-022-00431-0","type":"journal-article","created":{"date-parts":[[2022,12,7]],"date-time":"2022-12-07T14:02:40Z","timestamp":1670421760000},"page":"53-63","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Partition-based SIMD Processing and its Application to Columnar Database Systems"],"prefix":"10.1007","volume":"23","author":[{"given":"Juliana","family":"Hildebrandt","sequence":"first","affiliation":[]},{"given":"Johannes","family":"Pietrzyk","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Krause","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8671-5466","authenticated-orcid":false,"given":"Dirk","family":"Habich","sequence":"additional","affiliation":[]},{"given":"Wolfgang","family":"Lehner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,7]]},"reference":[{"issue":"3","key":"431_CR1","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1561\/1900000024","volume":"5","author":"D Abadi","year":"2013","unstructured":"Abadi D, Boncz PA, Harizopoulos S et al (2013) The design and implementation of modern column-oriented database systems. Found Trends Databases 5(3):197\u2013280. https:\/\/doi.org\/10.1561\/1900000024","journal-title":"Found Trends Databases"},{"key":"431_CR2","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1145\/1142473.1142548","volume-title":"SIGMOD","author":"DJ Abadi","year":"2006","unstructured":"Abadi DJ, Madden S, Ferreira M (2006) Integrating compression and execution in column-oriented database systems. In: SIGMOD, pp 671\u2013682 https:\/\/doi.org\/10.1145\/1142473.1142548"},{"issue":"2","key":"431_CR3","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.14778\/1687553.1687625","volume":"2","author":"DJ Abadi","year":"2009","unstructured":"Abadi DJ, Boncz PA, Harizopoulos S (2009) Column oriented database systems. Proc VLDB Endow 2(2):1664\u20131665 (http:\/\/www.vldb.org\/pvldb\/vol2\/vldb09-tutorial6.pdf)","journal-title":"Proc VLDB Endow"},{"issue":"1","key":"431_CR4","doi-asserted-by":"publisher","first-page":"85","DOI":"10.14778\/2732219.2732227","volume":"7","author":"C Balkesen","year":"2013","unstructured":"Balkesen C, Alonso G, Teubner J et al (2013) Multi-core, main-memory joins: Sort vs. hash revisited. Proc VLDB Endow 7(1):85\u201396 (http:\/\/www.vldb.org\/pvldb\/vol7\/p85-balkesen.pdf)","journal-title":"Proc VLDB Endow"},{"issue":"7","key":"431_CR5","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1109\/TKDE.2014.2313874","volume":"27","author":"C Balkesen","year":"2015","unstructured":"Balkesen C, Teubner J, Alonso G et al (2015) Main-memory hash joins on modern processor architectures. IEEE Trans Knowl Data Eng 27(7):1754\u20131766. https:\/\/doi.org\/10.1109\/TKDE.2014.2313874","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"431_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/1989323.1989328","volume-title":"SIGMOD","author":"S Blanas","year":"2011","unstructured":"Blanas S, Li Y, Patel JM (2011) Design and evaluation of main memory hash join algorithms for multi-core cpus. In: SIGMOD, pp 37\u201348 https:\/\/doi.org\/10.1145\/1989323.1989328"},{"key":"431_CR7","first-page":"225","volume-title":"CIDR","author":"PA Boncz","year":"2005","unstructured":"Boncz PA, Zukowski M, Nes N (2005) Monetdb\/x100: Hyper-pipelining query execution. In: CIDR, pp 225\u2013237 (http:\/\/cidrdb.org\/cidr2005\/papers\/P19.pdf)"},{"issue":"2","key":"431_CR8","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.14778\/1454159.1454171","volume":"1","author":"J Chhugani","year":"2008","unstructured":"Chhugani J, Nguyen AD, Lee VW et al (2008) Efficient implementation of sorting on multi-core SIMD CPU architecture. Proc VLDB Endow 1(2):1313\u20131324 (http:\/\/www.vldb.org\/pvldb\/vol1\/1454171.pdf)","journal-title":"Proc VLDB Endow"},{"issue":"3","key":"431_CR9","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/3323991","volume":"44","author":"P Damme","year":"2019","unstructured":"Damme P, Ungeth\u00fcm A, Hildebrandt J et al (2019) From a\u00a0comprehensive experimental survey to a\u00a0cost-based selection strategy for lightweight integer compression algorithms. ACM Trans Database Syst 44(3):9:1\u20139:46. https:\/\/doi.org\/10.1145\/3323991","journal-title":"ACM Trans Database Syst"},{"issue":"11","key":"431_CR10","doi-asserted-by":"publisher","first-page":"2396","DOI":"10.14778\/3407790.3407833","volume":"13","author":"P Damme","year":"2020","unstructured":"Damme P, Ungeth\u00fcm A, Pietrzyk J et al (2020) Morphstore: analytical query engine with a\u00a0holistic compression-enabled processing model. Proc VLDB Endow 13(11):2396\u20132410 (http:\/\/www.vldb.org\/pvldb\/vol13\/p2396-damme.pdf)","journal-title":"Proc VLDB Endow"},{"key":"431_CR11","series-title":"Synthesis lectures on computer architecture","doi-asserted-by":"publisher","DOI":"10.2200\/S00581ED1V01Y201405CAC028","volume-title":"A\u00a0primer on hardware prefetching","author":"B Falsafi","year":"2014","unstructured":"Falsafi B, Wenisch TF (2014) A\u00a0primer on hardware prefetching. Synthesis lectures on computer architecture. Morgan & Claypool https:\/\/doi.org\/10.2200\/S00581ED1V01Y201405CAC028"},{"key":"431_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/2723372.2747642","volume-title":"SIGMOD","author":"Z Feng","year":"2015","unstructured":"Feng Z, Lo E, Kao B et al (2015) Byteslice: pushing the envelop of main memory data processing with a\u00a0new storage layout. In: SIGMOD, pp 31\u201346 https:\/\/doi.org\/10.1145\/2723372.2747642"},{"key":"431_CR13","doi-asserted-by":"publisher","first-page":"8:1","DOI":"10.1145\/3209950.3209957","volume-title":"DBTest@SIGMOD","author":"D Habich","year":"2018","unstructured":"Habich D, Damme P, Ungeth\u00fcm A et al (2018) Make larger vector register sizes new challenges?: Lessons learned from the area of vectorized lightweight compression algorithms. In: DBTest@SIGMOD, pp 8:1\u20138:6 https:\/\/doi.org\/10.1145\/3209950.3209957"},{"key":"431_CR14","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/3533737.3535089","volume-title":"DaMoN@SIGMOD","author":"D Habich","year":"2022","unstructured":"Habich D, Pietrzyk J, Krause A et al (2022) To use or not to use the SIMD gather instruction? In: DaMoN@SIGMOD, pp 9:1\u20139:5 https:\/\/doi.org\/10.1145\/3533737.3535089"},{"key":"431_CR15","series-title":"Synthesis lectures on computer architecture","doi-asserted-by":"publisher","DOI":"10.2200\/S00647ED1V01Y201505CAC032","volume-title":"Single-instruction multiple-data execution","author":"CJ Hughes","year":"2015","unstructured":"Hughes CJ (2015) Single-instruction multiple-data execution. Synthesis lectures on computer architecture. Morgan & Claypool https:\/\/doi.org\/10.2200\/S00647ED1V01Y201505CAC032"},{"issue":"13","key":"431_CR16","doi-asserted-by":"publisher","first-page":"2209","DOI":"10.14778\/3275366.3284966","volume":"11","author":"T Kersten","year":"2018","unstructured":"Kersten T, Leis V, Kemper A et al (2018) Everything you always wanted to know about compiled and vectorized queries but were afraid to ask. Proc VLDB Endow 11(13):2209\u20132222 (http:\/\/www.vldb.org\/pvldb\/vol11\/p2209-kersten.pdf)","journal-title":"Proc VLDB Endow"},{"key":"431_CR17","first-page":"74","volume-title":"ADMS@VLDB","author":"T Kissinger","year":"2014","unstructured":"Kissinger T, Kiefer T, Schlegel B et al (2014) ERIS: A numa-aware in-memory storage engine for analytical workload. In: ADMS@VLDB, pp 74\u201385 (http:\/\/www.adms-conf.org\/2014\/adms14_kissinger.pdf)"},{"key":"431_CR18","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1145\/3183713.3183756","volume-title":"SIGMOD","author":"T Kissinger","year":"2018","unstructured":"Kissinger T, Habich D, Lehner W (2018) Adaptive energy-control for in-memory database systems. In: SIGMOD, pp 351\u2013364 https:\/\/doi.org\/10.1145\/3183713.3183756"},{"issue":"1","key":"431_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/spe.2203","volume":"45","author":"D Lemire","year":"2015","unstructured":"Lemire D, Boytsov L (2015) Decoding billions of integers per second through vectorization. Softw Pract Exp 45(1):1\u201329. https:\/\/doi.org\/10.1002\/spe.2203","journal-title":"Softw Pract Exp"},{"issue":"1","key":"431_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.14778\/3151113.3151114","volume":"11","author":"P Menon","year":"2017","unstructured":"Menon P, Pavlo A, Mowry TC (2017) Relaxed operator fusion for in-memory databases: Making compilation, vectorization, and prefetching work together at last. Proc VLDB Endow 11(1):1\u201313 (http:\/\/www.vldb.org\/pvldb\/vol11\/p1-menon.pdf)","journal-title":"Proc VLDB Endow"},{"key":"431_CR21","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1109\/MCHPC51950.2020.00012","volume-title":"MCHPC@SC","author":"MAH Monil","year":"2020","unstructured":"Monil MAH, Lee S, Vetter JS et al (2020) Understanding the impact of memory access patterns in intel processors. In: MCHPC@SC, pp 52\u201361 https:\/\/doi.org\/10.1109\/MCHPC51950.2020.00012"},{"issue":"1","key":"431_CR22","doi-asserted-by":"publisher","first-page":"928","DOI":"10.14778\/1920841.1920959","volume":"3","author":"I Pandis","year":"2010","unstructured":"Pandis I, Johnson R, Hardavellas N et al (2010) Data-oriented transaction execution. Proc VLDB Endow 3(1):928\u2013939 (http:\/\/www.vldb.org\/pvldb\/vldb2010\/pvldb_vol3\/R83.pdf)","journal-title":"Proc VLDB Endow"},{"key":"431_CR23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.18420\/btw2019-04","volume-title":"BTW","author":"J Pietrzyk","year":"2019","unstructured":"Pietrzyk J, Ungeth\u00fcm A, Habich D et al (2019) Fighting the duplicates in hashing: conflict detection-aware vectorization of linear probing. In: BTW, pp 35\u201353 https:\/\/doi.org\/10.18420\/btw2019-04"},{"key":"431_CR24","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/3399666.3399923","volume-title":"DaMoN@SIGMOD","author":"J Pietrzyk","year":"2020","unstructured":"Pietrzyk J, Habich D, Lehner W (2020) To share or not to share vector registers? In: DaMoN@SIGMOD, pp 12:1\u201312:10 https:\/\/doi.org\/10.1145\/3399666.3399923"},{"issue":"6","key":"431_CR25","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1007\/s00778-022-00744-2","volume":"31","author":"J Pietrzyk","year":"2022","unstructured":"Pietrzyk J, Krause A, Habich D et al (2022) To share or not to share vector registers? VLDB\u00a0J 31(6):1215\u20131236. https:\/\/doi.org\/10.1007\/s00778-022-00744-2","journal-title":"VLDB J"},{"key":"431_CR26","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1145\/2588555.2610522","volume-title":"SIGMOD","author":"O Polychroniou","year":"2014","unstructured":"Polychroniou O, Ross KA (2014a) A\u00a0comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort. In: SIGMOD, pp 755\u2013766 https:\/\/doi.org\/10.1145\/2588555.2610522"},{"key":"431_CR27","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/2619228.2619234","volume-title":"DaMoN@SIGMOD","author":"O Polychroniou","year":"2014","unstructured":"Polychroniou O, Ross KA (2014b) Vectorized bloom filters for advanced SIMD processors. In: Kemper A, Pandis I (eds) DaMoN@SIGMOD, pp 6:1\u20136:6 https:\/\/doi.org\/10.1145\/2619228.2619234"},{"key":"431_CR28","doi-asserted-by":"publisher","first-page":"10:1","DOI":"10.1145\/3329785.3329928","volume-title":"DaMoN@SIGMOD","author":"O Polychroniou","year":"2019","unstructured":"Polychroniou O, Ross KA (2019) Towards practical vectorized analytical query engines. In: DaMoN@SIGMOD, pp 10:1\u201310:7 https:\/\/doi.org\/10.1145\/3329785.3329928"},{"issue":"6","key":"431_CR29","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1007\/s00778-020-00621-w","volume":"29","author":"O Polychroniou","year":"2020","unstructured":"Polychroniou O, Ross KA (2020) VIP: A SIMD vectorized analytical query engine. VLDB\u00a0J 29(6):1243\u20131261. https:\/\/doi.org\/10.1007\/s00778-020-00621-w","journal-title":"VLDB J"},{"key":"431_CR30","doi-asserted-by":"publisher","first-page":"1493","DOI":"10.1145\/2723372.2747645","volume-title":"SIGMOD","author":"O Polychroniou","year":"2015","unstructured":"Polychroniou O, Raghavan A, Ross KA (2015) Rethinking SIMD vectorization for in-memory databases. In: SIGMOD, pp 1493\u20131508 https:\/\/doi.org\/10.1145\/2723372.2747645"},{"key":"431_CR31","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1109\/ICDE.2014.6816692","volume-title":"ICDE","author":"D Porobic","year":"2014","unstructured":"Porobic D, Liarou E, T\u00f6z\u00fcn P et al (2014) Atrapos: Adaptive transaction processing on hardware islands. In: ICDE, pp 688\u2013699 https:\/\/doi.org\/10.1109\/ICDE.2014.6816692"},{"key":"431_CR32","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1145\/1807167.1807207","volume-title":"SIGMOD","author":"N Satish","year":"2010","unstructured":"Satish N, Kim C, Chhugani J et al (2010) Fast sort on cpus and gpus: a\u00a0case for bandwidth oblivious SIMD sort. In: SIGMOD, pp 351\u2013362 https:\/\/doi.org\/10.1145\/1807167.1807207"},{"key":"431_CR33","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/1869389.1869394","volume-title":"DaMoN@SIGMOD","author":"B Schlegel","year":"2010","unstructured":"Schlegel B, Gemulla R, Lehner W (2010) Fast integer compression using SIMD instructions. In: DaMoN@SIGMOD, pp 34\u201340 https:\/\/doi.org\/10.1145\/1869389.1869394"},{"issue":"2","key":"431_CR34","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/MM.2016.25","volume":"36","author":"A Sodani","year":"2016","unstructured":"Sodani A, Gramunt R, Corbal J et al (2016) Knights landing: Second-generation intel xeon phi product. IEEE Micro 36(2):34\u201346. https:\/\/doi.org\/10.1109\/MM.2016.25","journal-title":"IEEE Micro"},{"issue":"1","key":"431_CR35","doi-asserted-by":"publisher","first-page":"385","DOI":"10.14778\/1687627.1687671","volume":"2","author":"T Willhalm","year":"2009","unstructured":"Willhalm T, Popovici N, Boshmaf Y et al (2009) Simd-scan: ultra fast in-memory table scan using on-chip vector processing units. Proc VLDB Endow 2(1):385\u2013394 (http:\/\/www.vldb.org\/pvldb\/vol2\/vldb09-327.pdf)","journal-title":"Proc VLDB Endow"},{"key":"431_CR36","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/3466752.3480091","volume-title":"MICRO","author":"X Xin","year":"2021","unstructured":"Xin X, Guo Y, Zhang Y et al (2021) SAM: accelerating strided memory accesses. In: MICRO, pp 324\u2013336 https:\/\/doi.org\/10.1145\/3466752.3480091"},{"issue":"3","key":"431_CR37","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2735629","volume":"33","author":"WX Zhao","year":"2015","unstructured":"Zhao WX, Zhang X, Lemire D et al (2015) A\u00a0general simd-based approach to accelerating compression algorithms. Acm Trans Inf Syst 33(3):15:1\u201315:28. https:\/\/doi.org\/10.1145\/2735629","journal-title":"Acm Trans Inf Syst"},{"key":"431_CR38","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1145\/564691.564709","volume-title":"SIGMOD","author":"J Zhou","year":"2002","unstructured":"Zhou J, Ross KA (2002) Implementing database operations using SIMD instructions. In: SIGMOD, pp 145\u2013156 https:\/\/doi.org\/10.1145\/564691.564709"},{"key":"431_CR39","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/1457150.1457160","volume-title":"DaMoN@SIGMOD","author":"M Zukowski","year":"2008","unstructured":"Zukowski M, Nes N, Boncz PA (2008) DSM vs. NSM: CPU performance tradeoffs in block-oriented query processing. In: DaMoN@SIGMOD, pp 47\u201354 https:\/\/doi.org\/10.1145\/1457150.1457160"}],"container-title":["Datenbank-Spektrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13222-022-00431-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13222-022-00431-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13222-022-00431-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T15:43:19Z","timestamp":1684165399000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13222-022-00431-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,7]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["431"],"URL":"https:\/\/doi.org\/10.1007\/s13222-022-00431-0","relation":{},"ISSN":["1618-2162","1610-1995"],"issn-type":[{"type":"print","value":"1618-2162"},{"type":"electronic","value":"1610-1995"}],"subject":[],"published":{"date-parts":[[2022,12,7]]},"assertion":[{"value":"23 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2022","order":3,"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 that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}