{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:19:39Z","timestamp":1779175179880,"version":"3.51.4"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>\n            The open-source FastLanes project aims to improve big data formats, such as Parquet, ORC and columnar database formats, in multiple ways. In this paper, we significantly accelerate decoding of all common Light-Weight Compression (LWC) schemes: DICT, FOR, DELTA and RLE through better data-parallelism. We do so by re-designing the compression layout using two main ideas: (i) generalizing the\n            <jats:italic>value interleaving<\/jats:italic>\n            technique in the basic operation of bit-(un)packing by targeting a virtual 1024-bits SIMD register, (ii) reordering the tuples in all columns of a table in the same Unified Transposed Layout that puts tuple chunks in a common \"04261537\" order (explained in the paper); allowing for maximum independent work for all possible basic SIMD lane widths: 8, 16, 32, and 64 bits.\n          <\/jats:p>\n          <jats:p>We address the software development, maintenance and future-proofness challenges of increasing hardware diversity, by defining a virtual 1024-bits instruction set that consists of simple operators supported by all SIMD dialects; and also, importantly, by scalar code. The interleaved and tuple-reordered layout actually makes scalar decoding faster, extracting more data-parallelism from today's wide-issue CPUs. Importantly, the scalar version can be fully auto-vectorized by modern compilers, eliminating technical debt in software caused by platform-specific SIMD intrinsics.<\/jats:p>\n          <jats:p>Micro-benchmarks on Intel, AMD, Apple and AWS CPUs show that FastLanes accelerates decoding by factors (decoding &gt;40 values per CPU cycle). FastLanes can make queries faster, as compressing the data reduces bandwidth needs, while decoding is almost free.<\/jats:p>","DOI":"10.14778\/3598581.3598587","type":"journal-article","created":{"date-parts":[[2023,7,10]],"date-time":"2023-07-10T22:19:06Z","timestamp":1689027546000},"page":"2132-2144","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["The FastLanes Compression Layout: Decoding &gt; 100 Billion Integers per Second with Scalar Code"],"prefix":"10.14778","volume":"16","author":[{"given":"Azim","family":"Afroozeh","sequence":"first","affiliation":[{"name":"CWI, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Boncz","sequence":"additional","affiliation":[{"name":"CWI, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Apache Parquet. http:\/\/parquet.apache.org\/.  [n.d.]. Apache Parquet. http:\/\/parquet.apache.org\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142548"},{"key":"e_1_2_1_3_1","unstructured":"A Afroozeh. 2020. Towards a New File Format for Big Data: SIMD-Friendly Composable Compression. https:\/\/homepages.cwi.nl\/~boncz\/msc\/2020-AzimAfroozeh.pdf  A Afroozeh. 2020. Towards a New File Format for Big Data: SIMD-Friendly Composable Compression. https:\/\/homepages.cwi.nl\/~boncz\/msc\/2020-AzimAfroozeh.pdf"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1184\/R1\/6608579.v1"},{"key":"e_1_2_1_5_1","unstructured":"Peter A. Boncz Marcin Zukowski and Niels Nes. 2005. MonetDB\/X100: Hyper-Pipelining Query Execution. In CIDR.  Peter A. Boncz Marcin Zukowski and Niels Nes. 2005. MonetDB\/X100: Hyper-Pipelining Query Execution. In CIDR."},{"key":"e_1_2_1_6_1","volume-title":"Nikita Mikhaylin, Hung ching Lee, Xiaoyan Zhao, Guanzhong Xu, Luis Antonio Perez, Farhad Shahmohammadi, Tran Bui, Neil McKay, Vera Lychagina, and Brett Elliott.","author":"Chattopadhyay Biswapesh","year":"2019","unstructured":"Biswapesh Chattopadhyay , Priyam Dutta , Weiran Liu , Ott Tinn , Andrew McCormick , Aniket Mokashi , Paul Harvey , Hector Gonzalez , David Lomax , Sagar Mittal , Roee Aharon Ebenstein , Nikita Mikhaylin, Hung ching Lee, Xiaoyan Zhao, Guanzhong Xu, Luis Antonio Perez, Farhad Shahmohammadi, Tran Bui, Neil McKay, Vera Lychagina, and Brett Elliott. 2019 . Procella : Unifying serving and analytical data at YouTube. PVLDB 12(12) (2019), 2022--2034. Biswapesh Chattopadhyay, Priyam Dutta, Weiran Liu, Ott Tinn, Andrew McCormick, Aniket Mokashi, Paul Harvey, Hector Gonzalez, David Lomax, Sagar Mittal, Roee Aharon Ebenstein, Nikita Mikhaylin, Hung ching Lee, Xiaoyan Zhao, Guanzhong Xu, Luis Antonio Perez, Farhad Shahmohammadi, Tran Bui, Neil McKay, Vera Lychagina, and Brett Elliott. 2019. Procella: Unifying serving and analytical data at YouTube. PVLDB 12(12) (2019), 2022--2034."},{"key":"e_1_2_1_7_1","unstructured":"Patrick Damme Dirk Habich Juliana Hildebrandt and Wolfgang Lehner. 2017. Lightweight Data Compression Algorithms: An Experimental Survey (Experiments and Analyses). In EDBT.  Patrick Damme Dirk Habich Juliana Hildebrandt and Wolfgang Lehner. 2017. Lightweight Data Compression Algorithms: An Experimental Survey (Experiments and Analyses). In EDBT."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747642"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/645483.656226"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209950.3209957"},{"key":"e_1_2_1_11_1","first-page":"12","article-title":"Data Parallel","volume":"29","author":"Daniel Hillis W.","year":"1986","unstructured":"W. Daniel Hillis and Guy L. Steele . 1986 . Data Parallel Algorithms. Commun. ACM 29 , 12 (dec 1986), 1170--1183. W. Daniel Hillis and Guy L. Steele. 1986. Data Parallel Algorithms. Commun. ACM 29, 12 (dec 1986), 1170--1183.","journal-title":"Algorithms. Commun. ACM"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275366.3284966"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882925"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00547-y"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3380479.3380481"},{"key":"e_1_2_1_16_1","volume-title":"Decoding billions of integers per second through vectorization. Software: Practice and Experience 45 (01","author":"Lemire Daniel","year":"2015","unstructured":"Daniel Lemire and Leonid Boytsov . 2015. Decoding billions of integers per second through vectorization. Software: Practice and Experience 45 (01 2015 ). Daniel Lemire and Leonid Boytsov. 2015. Decoding billions of integers per second through vectorization. Software: Practice and Experience 45 (01 2015)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2326"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465322"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/69.591455","article-title":"Block-Oriented Compression Techniques for Large Statistical Databases","volume":"9","author":"Ng Wee Keong","year":"1997","unstructured":"Wee Keong Ng and Chinya V. Ravishankar . 1997 . Block-Oriented Compression Techniques for Large Statistical Databases . IEEE Trans. on Knowl. and Data Eng. 9 , 2 (March 1997), 314--328. Wee Keong Ng and Chinya V. Ravishankar. 1997. Block-Oriented Compression Techniques for Large Statistical Databases. IEEE Trans. on Knowl. and Data Eng. 9, 2 (March 1997), 314--328.","journal-title":"IEEE Trans. on Knowl. and Data Eng."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554829"},{"key":"e_1_2_1_21_1","unstructured":"Johannes Pietrzyk Annett Ungeth\u00fcm Dirk Habich and Wolfgang Lehner. 2018. Beyond Straightforward Vectorization of Lightweight Data Compression Algorithms for Larger Vector Sizes. In Grundlagen von Datenbanken.  Johannes Pietrzyk Annett Ungeth\u00fcm Dirk Habich and Wolfgang Lehner. 2018. Beyond Straightforward Vectorization of Lightweight Data Compression Algorithms for Larger Vector Sizes. In Grundlagen von Datenbanken."},{"key":"e_1_2_1_22_1","volume-title":"Vectorized VByte Decoding. ArXiv","author":"Plaisance Jeff","year":"2015","unstructured":"Jeff Plaisance , Nathan Kurz , and Daniel Lemire . 2015. Vectorized VByte Decoding. ArXiv ( 2015 ). Jeff Plaisance, Nathan Kurz, and Daniel Lemire. 2015. Vectorized VByte Decoding. ArXiv (2015)."},{"key":"e_1_2_1_23_1","volume-title":"Ross","author":"Polychroniou Orestis","year":"2015","unstructured":"Orestis Polychroniou , Arun Raghavan , and Kenneth A . Ross . 2015 . Rethinking SIMD Vectorization for In-Memory Databases. In ACM SIGMOD, Timos K. Sellis, Susan B. Davidson, and ZacharyG. Ives (Eds.). ACM , 1493--1508. Orestis Polychroniou, Arun Raghavan, and Kenneth A. Ross. 2015. Rethinking SIMD Vectorization for In-Memory Databases. In ACM SIGMOD, Timos K. Sellis, Susan B. Davidson, and ZacharyG. Ives (Eds.). ACM, 1493--1508."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 11th International Workshop on Data Management on New Hardware","author":"Polychroniou Orestis","unstructured":"Orestis Polychroniou and Kenneth A. Ross . 2015. Efficient Lightweight Compression Alongside Fast Scans . In Proceedings of the 11th International Workshop on Data Management on New Hardware ( Melbourne, VIC, Australia) (DaMoN'15). Association for Computing Machinery, New York, NY, USA, Article 9, 6 pages. Orestis Polychroniou and Kenneth A. Ross. 2015. Efficient Lightweight Compression Alongside Fast Scans. In Proceedings of the 11th International Workshop on Data Management on New Hardware (Melbourne, VIC, Australia) (DaMoN'15). Association for Computing Machinery, New York, NY, USA, Article 9, 6 pages."},{"key":"e_1_2_1_25_1","volume-title":"10th Conference on Innovative Data Systems Research, CIDR","author":"Raasveldt Mark","year":"2020","unstructured":"Mark Raasveldt and Hannes M\u00fchleisen . 2020. Data Management for Data Science - Towards Embedded Analytics . In 10th Conference on Innovative Data Systems Research, CIDR 2020 , Amsterdam, The Netherlands , January 12--15, 2020, Online Proceedings . www.cidrdb.org. http:\/\/www.duckdb.org Mark Raasveldt and Hannes M\u00fchleisen. 2020. Data Management for Data Science - Towards Embedded Analytics. In 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12--15, 2020, Online Proceedings. www.cidrdb.org. http:\/\/www.duckdb.org"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases","author":"Raman Vijayshankar","year":"2006","unstructured":"Vijayshankar Raman and Garret Swart . 2006 . How to Wring a Table Dry: Entropy Compression of Relations and Querying of Compressed Relations . In Proceedings of the 32nd International Conference on Very Large Data Bases ( Seoul, Korea) (VLDB '06). VLDB Endowment, 858--869. Vijayshankar Raman and Garret Swart. 2006. How to Wring a Table Dry: Entropy Compression of Relations and Querying of Compressed Relations. In Proceedings of the 32nd International Conference on Very Large Data Bases (Seoul, Korea) (VLDB '06). VLDB Endowment, 858--869."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Benjamin Schlegel Rainer Gemulla and Wolfgang Lehner. 2010. Fast integer compression using SIMD instructions. 34--40.  Benjamin Schlegel Rainer Gemulla and Wolfgang Lehner. 2010. Fast integer compression using SIMD instructions. 34--40.","DOI":"10.1145\/1869389.1869394"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526132"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 20th ACM International Conference on Information and Knowledge Management (Glasgow","author":"Stepanov Alexander A.","unstructured":"Alexander A. Stepanov , Anil R. Gangolli , Daniel E. Rose , Ryan J. Ernst , and Paramjit S. Oberoi . 2011. SIMD-Based Decoding of Posting Lists . In Proceedings of the 20th ACM International Conference on Information and Knowledge Management (Glasgow , Scotland, UK) (CIKM '11). Association for Computing Machinery, New York, NY, USA, 317--326. Alexander A. Stepanov, Anil R. Gangolli, Daniel E. Rose, Ryan J. Ernst, and Paramjit S. Oberoi. 2011. SIMD-Based Decoding of Posting Lists. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management (Glasgow, Scotland, UK) (CIKM '11). Association for Computing Machinery, New York, NY, USA, 317--326."},{"key":"e_1_2_1_30_1","volume-title":"The ARM Scalable Vector Extension. CoRR abs\/1803.06185","author":"Stephens Nigel","year":"2018","unstructured":"Nigel Stephens , Stuart Biles , Matthias Boettcher , Jacob Eapen , Mbou Eyole , Giacomo Gabrielli , Matt Horsnell , Grigorios Magklis , Alejandro Martinez , Nathanael Pr\u00e9millieu , Alastair Reid , Alejandro Rico , and Paul Walker . 2018. The ARM Scalable Vector Extension. CoRR abs\/1803.06185 ( 2018 ). Nigel Stephens, Stuart Biles, Matthias Boettcher, Jacob Eapen, Mbou Eyole, Giacomo Gabrielli, Matt Horsnell, Grigorios Magklis, Alejandro Martinez, Nathanael Pr\u00e9millieu, Alastair Reid, Alejandro Rico, and Paul Walker. 2018. The ARM Scalable Vector Extension. CoRR abs\/1803.06185 (2018)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Annett Ungeth\u00fcm Johannes Pietrzyk Patrick Damme Dirk Habich and Wolfgang Lehner. 2018. Conflict Detection-Based Run-Length Encoding - AVX-512 CD Instruction Set in Action. 96--101.  Annett Ungeth\u00fcm Johannes Pietrzyk Patrick Damme Dirk Habich and Wolfgang Lehner. 2018. Conflict Detection-Based Run-Length Encoding - AVX-512 CD Instruction Set in Action. 96--101.","DOI":"10.1109\/ICDEW.2018.00023"},{"key":"e_1_2_1_32_1","volume-title":"10th Conference on Innovative Data Systems Research, CIDR","author":"Ungeth\u00fcm Annett","year":"2020","unstructured":"Annett Ungeth\u00fcm , Johannes Pietrzyk , Patrick Damme , Alexander Krause , Dirk Habich , Wolfgang Lehner , and Erich Focht . 2020. Hardware-Oblivious SIMD Parallelism for In-Memory Column-Stores . In 10th Conference on Innovative Data Systems Research, CIDR 2020 , Amsterdam, The Netherlands , January 12--15, 2020, Online Proceedings . www.cidrdb.org. Annett Ungeth\u00fcm, Johannes Pietrzyk, Patrick Damme, Alexander Krause, Dirk Habich, Wolfgang Lehner, and Erich Focht. 2020. Hardware-Oblivious SIMD Parallelism for In-Memory Column-Stores. In 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12--15, 2020, Online Proceedings. www.cidrdb.org."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2595639"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/362084.362137"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687671"},{"key":"e_1_2_1_36_1","volume-title":"Parallel Prefix Sum with SIMD. (09","author":"Zhang Wangda","year":"2020","unstructured":"Wangda Zhang , Yanbin Wang , and Kenneth Ross . 2020. Parallel Prefix Sum with SIMD. (09 2020 ). Wangda Zhang, Yanbin Wang, and Kenneth Ross. 2020. Parallel Prefix Sum with SIMD. (09 2020)."},{"key":"e_1_2_1_37_1","volume-title":"A General SIMD-Based Approach to Accelerating Compression Algorithms. ACM Transactions on Information Systems 33 (02","author":"Zhao Wayne","year":"2015","unstructured":"Wayne Zhao , Xudong Zhang , Daniel Lemire , Dongdong Shan , Jian-yun Nie, Hongfei Yan , and Ji-Rong Wen . 2015. A General SIMD-Based Approach to Accelerating Compression Algorithms. ACM Transactions on Information Systems 33 (02 2015 ). Wayne Zhao, Xudong Zhang, Daniel Lemire, Dongdong Shan, Jian-yun Nie, Hongfei Yan, and Ji-Rong Wen. 2015. A General SIMD-Based Approach to Accelerating Compression Algorithms. ACM Transactions on Information Systems 33 (02 2015)."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data","author":"Zhou Jingren","unstructured":"Jingren Zhou and Kenneth A. Ross . 2002. Implementing Database Operations Using SIMD Instructions . In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data ( Madison, Wisconsin) (SIGMOD '02). Association for Computing Machinery, New York, NY, USA, 145--156. Jingren Zhou and Kenneth A. Ross. 2002. Implementing Database Operations Using SIMD Instructions. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data (Madison, Wisconsin) (SIGMOD '02). Association for Computing Machinery, New York, NY, USA, 145--156."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3--8","author":"Zukowski Marcin","year":"2006","unstructured":"Marcin Zukowski , S\u00e1ndor H\u00e9man , Niels Nes , and Peter A. Boncz . 2006. Super-Scalar RAM-CPU Cache Compression . In Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3--8 April 2006 , Atlanta, GA, USA, Ling Liu, Andreas Reuter, Kyu-Young Whang, and Jianjun Zhang (Eds.). IEEE Computer Society, 59. Marcin Zukowski, S\u00e1ndor H\u00e9man, Niels Nes, and Peter A. Boncz. 2006. Super-Scalar RAM-CPU Cache Compression. In Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3--8 April 2006, Atlanta, GA, USA, Ling Liu, Andreas Reuter, Kyu-Young Whang, and Jianjun Zhang (Eds.). IEEE Computer Society, 59."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3598581.3598587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T22:59:15Z","timestamp":1689807555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3598581.3598587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":39,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["10.14778\/3598581.3598587"],"URL":"https:\/\/doi.org\/10.14778\/3598581.3598587","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,5]]},"assertion":[{"value":"2023-07-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}