TY - GEN
T1 - Performance of point and range queries for in-memory databases using radix trees on GPUs
AU - Alam, Maksudul
AU - Yoginath, Srikanth B.
AU - Perumalla, Kalyan S.
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2017/1/20
Y1 - 2017/1/20
N2 - In in-memory database systems augmented by hardware accelerators, accelerating the index searching operations can greatly increase the runtime performance of database queries. Recently, adaptive radix trees (ART) have been shown to provide very fast index search implementation on the CPU. Here, we focus on an accelerator-based implementation of ART. We present a detailed performance study of our GPU-based adaptive radix tree (GRT) implementation over a variety of key distributions, synthetic benchmarks, and actual keys from music and book data sets. The performance is also compared with other index-searching schemes on the GPU. GRT on modern GPUs achieves some of the highest rates of index searches reported in the literature. For point queries, a throughput of up to 106 million and 130 million lookups per second is achieved for sparse and dense keys, respectively. For range queries, GRT yields 600 million and 1000 million lookups per second for sparse and dense keys, respectively, on a large dataset of 64 million 32-bit keys.
AB - In in-memory database systems augmented by hardware accelerators, accelerating the index searching operations can greatly increase the runtime performance of database queries. Recently, adaptive radix trees (ART) have been shown to provide very fast index search implementation on the CPU. Here, we focus on an accelerator-based implementation of ART. We present a detailed performance study of our GPU-based adaptive radix tree (GRT) implementation over a variety of key distributions, synthetic benchmarks, and actual keys from music and book data sets. The performance is also compared with other index-searching schemes on the GPU. GRT on modern GPUs achieves some of the highest rates of index searches reported in the literature. For point queries, a throughput of up to 106 million and 130 million lookups per second is achieved for sparse and dense keys, respectively. For range queries, GRT yields 600 million and 1000 million lookups per second for sparse and dense keys, respectively, on a large dataset of 64 million 32-bit keys.
KW - GPGPU
KW - High performance computing
KW - Index searching
KW - Main memory database
UR - http://www.scopus.com/inward/record.url?scp=85013684716&partnerID=8YFLogxK
U2 - 10.1109/HPCC-SmartCity-DSS.2016.0212
DO - 10.1109/HPCC-SmartCity-DSS.2016.0212
M3 - Conference contribution
AN - SCOPUS:85013684716
T3 - Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016
SP - 1493
EP - 1500
BT - Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016
A2 - Yang, Laurence T.
A2 - Chen, Jinjun
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016
Y2 - 12 December 2016 through 14 December 2016
ER -