TY - GEN
T1 - Transforming Query Sequences for High-Throughput B+ Tree Processing on Many-Core Processors
AU - Tian, Ruiqin
AU - Qiu, Junqiao
AU - Zhao, Zhijia
AU - Liu, Xu
AU - Ren, Bin
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2019/3/5
Y1 - 2019/3/5
N2 - The throughput of B+ tree query processing is critical to many databases, file systems, and cloud applications. Based on bulk synchronous parallel (BSP), latch-free B+ tree query processing has shown promise by processing queries in small batches and avoiding the use of locks. As the number of cores on CPUs increases, it becomes possible to process larger batches in parallel without adding any extra delays. In this work, we argue that as the batch size increases, there will be more optimization opportunities exposed beyond parallelism, especially when the query distributions are highly skewed. These include the opportunities of avoiding the evaluations of a large ratio of redundant or unnecessary queries. To rigorously exploit the new opportunities, this work introduces a query sequence analysis and transformation framework - QTrans. QTrans can systematically reason about the redundancies at a deep level and automatically remove them from the query sequence. QTrans has interesting resemblances with the classic data-flow analysis and transformation that have been widely used in compilers. To confirm its benefits, this work integrates QTrans into an existing BSP-based B+ tree query processing system, PALM tree, to automatically eliminate redundant and unnecessary queries1. Evaluation shows that, by transforming the query sequence, QTrans can substantially improve the throughput of query processing on both real-world and synthesized datasets, up to 16X. 1Artifact available at: https://doi.org/10.5281/zenodo.1486393
AB - The throughput of B+ tree query processing is critical to many databases, file systems, and cloud applications. Based on bulk synchronous parallel (BSP), latch-free B+ tree query processing has shown promise by processing queries in small batches and avoiding the use of locks. As the number of cores on CPUs increases, it becomes possible to process larger batches in parallel without adding any extra delays. In this work, we argue that as the batch size increases, there will be more optimization opportunities exposed beyond parallelism, especially when the query distributions are highly skewed. These include the opportunities of avoiding the evaluations of a large ratio of redundant or unnecessary queries. To rigorously exploit the new opportunities, this work introduces a query sequence analysis and transformation framework - QTrans. QTrans can systematically reason about the redundancies at a deep level and automatically remove them from the query sequence. QTrans has interesting resemblances with the classic data-flow analysis and transformation that have been widely used in compilers. To confirm its benefits, this work integrates QTrans into an existing BSP-based B+ tree query processing system, PALM tree, to automatically eliminate redundant and unnecessary queries1. Evaluation shows that, by transforming the query sequence, QTrans can substantially improve the throughput of query processing on both real-world and synthesized datasets, up to 16X. 1Artifact available at: https://doi.org/10.5281/zenodo.1486393
KW - B+ tree
KW - Latch-free processing
KW - Many-core processors
KW - Query analysis and transformation
UR - http://www.scopus.com/inward/record.url?scp=85063769655&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85063769655&origin=recordpage
U2 - 10.1109/CGO.2019.8661166
DO - 10.1109/CGO.2019.8661166
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781728114361
T3 - CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization
SP - 96
EP - 108
BT - CGO 2019 - Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization
PB - IEEE
T2 - 17th IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2019
Y2 - 16 February 2019 through 20 February 2019
ER -