{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T02:25:03Z","timestamp":1767925503554,"version":"3.49.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p>Indexing is a core technique for accelerating predicate evaluation in databases. After many years of effort, the indexing performance has reached its peak on the existing hardware infrastructure. We propose to use ray tracing (RT) cores to move the indexing performance and efficiency to another level by addressing the following technical challenges: (1) the lack of an efficient mapping of predicate evaluation to a ray tracing job and (2) the poor performance by the heavy and imbalanced ray load when processing skewed datasets. These challenges set obstacles to effectively exploiting RT cores for predicate evaluation.<\/jats:p>\n          <jats:p>In this paper, we propose RTScan, an approach that leverages RT cores to accelerate index scans. RTScan transforms the evaluation of conjunctive predicates into an efficient ray tracing job in a three-dimensional space. A set of techniques are designed in RTScan, i.e., Uniform Encoding, Data Sieving, and Matrix RT Refine, which significantly enhances the parallelism of scans on RT cores while lightening and balancing the ray load. With the proposed techniques, RTScan achieves high performance for datasets with either uniform or skewed distributions and queries with different selectivities. Extensive evaluations demonstrate that RTScan enhances the scan performance on RT cores by five orders of magnitude and outperforms the state-of-the-art approach on CPU by up to 4.6\u00d7.<\/jats:p>","DOI":"10.14778\/3648160.3648183","type":"journal-article","created":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T21:52:53Z","timestamp":1714773173000},"page":"1460-1472","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["RTScan: Efficient Scan with Ray Tracing Cores"],"prefix":"10.14778","volume":"17","author":[{"given":"Yangming","family":"Lv","sequence":"first","affiliation":[{"name":"Fudan University"}]},{"given":"Kai","family":"Zhang","sequence":"additional","affiliation":[{"name":"Fudan University"}]},{"given":"Ziming","family":"Wang","sequence":"additional","affiliation":[{"name":"Fudan University"}]},{"given":"Xiaodong","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Ohio State University"}]},{"given":"Rubao","family":"Lee","sequence":"additional","affiliation":[{"name":"Freelance Researcher"}]},{"given":"Zhenying","family":"He","sequence":"additional","affiliation":[{"name":"Fudan University"}]},{"given":"Yinan","family":"Jing","sequence":"additional","affiliation":[{"name":"Fudan University"}]},{"given":"X. Sean","family":"Wang","sequence":"additional","affiliation":[{"name":"Fudan University"}]}],"member":"320","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3559009.3569681"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559877"},{"key":"e_1_2_1_3_1","article-title":"Fast radius search exploiting ray-tracing frameworks","volume":"10","author":"Evangelou I","year":"2021","unstructured":"I Evangelou, G Papaioannou, K Vardis, and AA Vasilakis. 2021. Fast radius search exploiting ray-tracing frameworks. Journal of Computer Graphics Techniques Vol 10, 1 (2021).","journal-title":"Journal of Computer Graphics Techniques"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747642"},{"key":"e_1_2_1_5_1","volume-title":"Elements of distributed computing","author":"Garg Vijay K","unstructured":"Vijay K Garg. 2002. Elements of distributed computing. John Wiley & Sons, 150--151."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732280"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93.","author":"Joseph","unstructured":"Joseph M. Hellerstein and Michael Stonebraker. 1993. Predicate migration: optimizing queries with expensive predicates. In Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93."},{"key":"e_1_2_1_8_1","volume-title":"RTIndeX: Exploiting Hardware-Accelerated GPU Raytracing for Database Indexing. arXiv preprint arXiv:2303.01139","author":"Henneberg Justus","year":"2023","unstructured":"Justus Henneberg and Felix Schuhknecht. 2023. RTIndeX: Exploiting Hardware-Accelerated GPU Raytracing for Database Indexing. arXiv preprint arXiv:2303.01139 (2023)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196911"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"RowWise Parallel Predicate Evaluation","volume":"1","author":"Johnson Ryan","year":"2008","unstructured":"Ryan Johnson, Vijayshankar Raman, Richard Sidle, and Garret Swart. 2008. RowWise Parallel Predicate Evaluation. Proc. VLDB Endow. 1, 1 (aug 2008), 622--634.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_11_1","volume-title":"2020 IEEE 27th international conference on high performance computing, data, and analytics (HiPC). IEEE, 11--20","author":"J\u00fcnger Daniel","year":"2020","unstructured":"Daniel J\u00fcnger, Robin Kobus, Andr\u00e9 M\u00fcller, Christian Hundt, Kai Xu, Weiguo Liu, and Bertil Schmidt. 2020. Warpcore: A library for fast hash tables on gpus. In 2020 IEEE 27th international conference on high performance computing, data, and analytics (HiPC). IEEE, 11--20."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994529"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380563"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data","author":"Li Yinan","unstructured":"Yinan Li and Jignesh M. Patel. 2013. BitWeaving: Fast Scans for Main Memory Data Processing. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (New York, New York, USA) (SIGMOD '13). Association for Computing Machinery, New York, NY, USA, 289--300."},{"key":"e_1_2_1_15_1","volume-title":"Quezada","author":"Meneses Enzo","year":"2023","unstructured":"Enzo Meneses, Crist\u00f3bal A. Navarro, H\u00e9ctor Ferrada, and Felipe A. Quezada. 2023. Accelerating Range Minimum Queries with Ray Tracing Cores. arXiv:2306.03282 [cs.DC]"},{"key":"e_1_2_1_16_1","volume-title":"Proc. VLDB Endow. 476--487","author":"Moerkotte Guido","year":"1998","unstructured":"Guido Moerkotte. 1998. Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. In Proc. VLDB Endow. 476--487."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Vani Nagarajan and Milind Kulkarni. 2023. RT-DBSCAN: Accelerating DBSCAN using Ray Tracing Hardware. arXiv:2303.09655 [cs.DC]","DOI":"10.1109\/IPDPS54959.2023.00100"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3577193.3593738"},{"key":"e_1_2_1_19_1","volume-title":"21st International Conference on Data Engineering (ICDE'05)","author":"Neumann Thomas","year":"2005","unstructured":"Thomas Neumann, Sven Helmer, and Guido Moerkotte. 2005. On the optimal ordering of maps and selections under factorization. In 21st International Conference on Data Engineering (ICDE'05). IEEE, 490--501."},{"key":"e_1_2_1_20_1","unstructured":"NVIDIA. 2018. NVIDIA Turing GPU architecture. (2018) 25--29 30--32. https:\/\/images.nvidia.cn\/aem-dam\/en-zz\/Solutions\/design-visualization\/technologies\/turing-architecture\/NVIDIA-Turing-Architecture-Whitepaper.pdf"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536364"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453924"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543628"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4842-4427-2_2"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1995441.1995446"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Mike Stonebraker Daniel J Abadi Adam Batkin Xuedong Chen Mitch Cherniack Miguel Ferreira Edmond Lau Amerson Lin Sam Madden Elizabeth O'Neil et al. 2018. C-store: a column-oriented DBMS. In Making Databases Work: the Pragmatic Wisdom of Michael Stonebraker. 491--518.","DOI":"10.1145\/3226595.3226638"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025123"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064007"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"2803","DOI":"10.1109\/TKDE.2019.2958672","article-title":"Understanding and Optimizing Conjunctive Predicates Under Memory-Efficient Storage Layouts","volume":"33","author":"Wang Zeke","year":"2019","unstructured":"Zeke Wang, Xue Liu, Kai Zhang, Haihang Zhou, and Bingsheng He. 2019. Understanding and Optimizing Conjunctive Predicates Under Memory-Efficient Storage Layouts. IEEE Transactions on Knowledge and Data Engineering 33, 6 (2019), 2803--2817.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","author":"Zhu Yuhao","year":"2022","unstructured":"Yuhao Zhu. 2022. RTNN: Accelerating Neighbor Search Using Hardware Ray Tracing. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Seoul, Republic of Korea) (PPoPP '22). Association for Computing Machinery, New York, NY, USA, 76--89."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.148"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3648160.3648183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T21:59:04Z","timestamp":1714773544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3648160.3648183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.14778\/3648160.3648183"],"URL":"https:\/\/doi.org\/10.14778\/3648160.3648183","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,2]]},"assertion":[{"value":"2024-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}