Meet the Walkers: Accelerating Index Traversals for In-memory Databases

Onur Kocberber, Boris Grot, Javier Picorel, Babak Falsafi, Kevin Lim, Parthasarathy Ranganathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The explosive growth in digital data and its growing role in real-time decision support motivate the design of high-performance database management systems (DBMSs). Meanwhile, slowdown in supply voltage scaling has stymied improvements in core performance and ushered an era of power-limited chips. These developments motivate the design of DBMS accelerators that (a) maximize utility by accelerating the dominant operations, and (b) provide flexibility in the choice of DBMS, data layout, and data types.
We study data analytics workloads on contemporary in-memory databases and find hash index lookups to be the largest single contributor to the overall execution time. The critical path in hash index lookups consists of ALU-intensive key hashing followed by pointer chasing through a node list. Based on these observations, we introduce Widx, an on-chip accelerator for database hash index lookups, which achieves both high performance and flexibility by (1) decoupling key hashing from the list traversal, and (2) processing multiple keys in parallel on a set of programmable walker units. Widx reduces design cost and complexity through its tight integration with a conventional core, thus eliminating the need for a dedicated TLB and cache. An evaluation of Widx on a set of modern data analytics workloads (TPC-H, TPC-DS) using full-system simulation shows an average speedup of 3.1x over an aggressive OoO core on bulk hash table operations, while reducing the OoO core energy by 83%.
Original languageEnglish
Title of host publicationProceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture
Place of PublicationNew York, NY, USA
Number of pages12
Publication statusPublished - 2013

Publication series



  • database indexing, energy efficiency, hardware accelerators


Dive into the research topics of 'Meet the Walkers: Accelerating Index Traversals for In-memory Databases'. Together they form a unique fingerprint.

Cite this