A hybrid B+-tree as solution for in-memory indexing on CPU-GPU heterogeneous computing platforms

Amirhesam Shahvarani, Hans Arno Jacobsen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

41 Scopus citations

Abstract

An in-memory indexing tree is a critical component of many databases. Modern many-core processors, such as GPUs, are offering tremendous amounts of computing power making them an attractive choice for accelerating indexing. However, the memory available to the accelerating co-processor is rather limited and expensive in comparison to the memory available to the CPU. This drawback is a barrier to exploit the computing power of co-processors for arbitrarily large index trees. In this paper, we propose a novel design for a B+-tree based on the heterogeneous computing platform and the hybrid memory architecture found in GPUs. We propose a hybrid CPU-GPU B+-tree,-H B+-tree,-which targets high search throughput use cases. Unique to our design is the joint and simultaneous use of computing and memory resources of CPU-GPU systems. Our experiments show that our H B+-tree can perform up to 240 million index queries per second, which is 2.4X higher than our CPU-optimized solution.

Original languageEnglish
Title of host publicationSIGMOD 2016 - Proceedings of the 2016 International Conference on Management of Data
PublisherAssociation for Computing Machinery
Pages1523-1538
Number of pages16
ISBN (Electronic)9781450335317
DOIs
StatePublished - 26 Jun 2016
Event2016 ACM SIGMOD International Conference on Management of Data, SIGMOD 2016 - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
Volume26-June-2016
ISSN (Print)0730-8078

Conference

Conference2016 ACM SIGMOD International Conference on Management of Data, SIGMOD 2016
Country/TerritoryUnited States
CitySan Francisco
Period26/06/161/07/16

Keywords

  • B-tree
  • Heterogeneous Computing
  • In-memory database
  • Indexing

Fingerprint

Dive into the research topics of 'A hybrid B+-tree as solution for in-memory indexing on CPU-GPU heterogeneous computing platforms'. Together they form a unique fingerprint.

Cite this